Dear friends,
I believe I have the answer. Bear with me as I explain.
In a standard ACL, the entries (we call them Access Control Entries, ACEs) are of two types: fastitem and fasthash. The fasthash entries are those whose wildcard mask is 0.0.0.0, in other words, fasthash entries are host entries. The fastitem entries are ACEs that have a wildcard mask different from 0.0.0.0; you could call them network entries, as they are commonly used to describe entire ranges of addresses.
For efficiency reasons, fasthash entries are internally stored in a hash table. This allows them to be searched very quickly when searching for a match. However, due to hashing, their order will appear to be different from the order in which they have been entered when printing out the ACL.
Consider the following ACL:
Router(config)#access-list 1 permit 10.10.10.1
Router(config)#access-list 1 permit 10.10.10.2
Router(config)#access-list 1 permit 10.10.10.3
Router(config)#access-list 1 permit 10.10.10.4
Router(config)#access-list 1 permit 10.10.10.5
Router(config)#access-list 1 permit 10.10.10.6
Router(config)#access-list 1 permit 10.10.10.7
Router(config)#access-list 1 permit 10.10.10.8
Router(config)#do show access-list 1
Standard IP access list 1
80 permit 10.10.10.8
20 permit 10.10.10.2
30 permit 10.10.10.3
10 permit 10.10.10.1
60 permit 10.10.10.6
70 permit 10.10.10.7
40 permit 10.10.10.4
50 permit 10.10.10.5
Router(config)#do show run | i access-list
access-list 1 permit 10.10.10.8
access-list 1 permit 10.10.10.2
access-list 1 permit 10.10.10.3
access-list 1 permit 10.10.10.1
access-list 1 permit 10.10.10.6
access-list 1 permit 10.10.10.7
access-list 1 permit 10.10.10.4
access-list 1 permit 10.10.10.5Obviously, it has been reordered from the order I have used when creating it. The ordering corresponds to the internal ordering of the hash table in which these fasthash items have been indexed, and as it turns out, the hash function that determines the ordering is a simple XOR of all four octets of the IP address.
I've concocted a quick and dirty Python script XORing the four octets of an IP address together:
#!/usr/bin/python
while True:
IP=raw_input('Enter IP to be hashed: ').split(".")
print "Hashing index is: ",int(IP[0])^int(IP[1])^int(IP[2])^int(IP[3])
printAnd this is what it tells me when I enter the IP addresses in the order they show up in the outputs above:
Enter IP to be hashed: 10.10.10.8
Hashing index is: 2
Enter IP to be hashed: 10.10.10.2
Hashing index is: 8
Enter IP to be hashed: 10.10.10.3
Hashing index is: 9
Enter IP to be hashed: 10.10.10.1
Hashing index is: 11
Enter IP to be hashed: 10.10.10.6
Hashing index is: 12
Enter IP to be hashed: 10.10.10.7
Hashing index is: 13
Enter IP to be hashed: 10.10.10.4
Hashing index is: 14
Enter IP to be hashed: 10.10.10.5
Hashing index is: 15
Note that the hashing index computed here creates a monotonous increasing sequence that perfectly corresponds to the ordering of entries as displayed in the show outputs above.
It is important to realize here that even though the fasthash entries are reordered, it has no impact on the logic of the access list. This is because the fasthash entries are entries that match the complete address, they do not overlap, and so their mutual order does not matter.
When fasthash (host entries) and fastitem (network entries) are combined, the CLI will not allow entering a host ACE placed after an existing network ACE that would also match the host address in the host ACE:
Router(config)#access-list 2 permit 10.0.0.0 0.255.255.255
Router(config)#access-list 2 deny 10.10.10.10
% Access rule can't be configured at higher sequence num as it is part of the existing rule at sequence num 10
Why is this? Obviously, a host ACE can either select the same action (permit or deny) for a packet that would be taken by a more general network ACE later, in which case it is not necessary for that host ACE to be entered at all but not prohibited at the same time, or it can override that action. In the second case, it is necessary for this host ACE to be placed in the ACL first, before the network ACE, otherwise it will never be reached. This leads us to a general logic in standard ACLs - it only makes sense to put all host (fasthash) ACEs first, and network (fastitem) ACEs last. Of course, the network ACEs can not be easily optimized in their ordering anymore because their potential overlaps may be very complicated. For network ACEs, their ordering as configured must be preserved.
So a standard ACL indeed consists of the set of fasthash host ACEs sorted by their hashing values and evaluated first (and also printed out first), and the fastitem network ACEs evaluated after the host ACEs in the order they have been entered:
Router(config)#access-list 3 permit 10.15.0.0 0.0.255.255
Router(config)#access-list 3 deny 10.14.0.0 0.0.255.255
Router(config)#access-list 3 permit 10.13.0.0 0.0.255.255
Router(config)#access-list 3 deny 10.12.0.0 0.0.255.255
Router(config)#access-list 3 permit 10.11.0.0 0.0.255.255
Router(config)#access-list 3 deny 10.10.0.0 0.0.255.255
Router(config)#access-list 3 permit 10.0.0.1
Router(config)#access-list 3 permit 10.0.0.2
Router(config)#access-list 3 permit 10.0.0.3
Router(config)#access-list 3 permit 10.0.0.4
Router(config)#access-list 3 deny 10.0.0.5
Router(config)#access-list 3 deny 10.0.0.6
Router(config)#access-list 3 deny 10.0.0.7
Router(config)#access-list 3 deny 10.0.0.8
Router(config)#
Router(config)#do show access-list 3
Standard IP access list 3
140 deny 10.0.0.8
80 permit 10.0.0.2
90 permit 10.0.0.3
70 permit 10.0.0.1
120 deny 10.0.0.6
130 deny 10.0.0.7
100 permit 10.0.0.4
110 deny 10.0.0.5
10 permit 10.15.0.0, wildcard bits 0.0.255.255
20 deny 10.14.0.0, wildcard bits 0.0.255.255
30 permit 10.13.0.0, wildcard bits 0.0.255.255
40 deny 10.12.0.0, wildcard bits 0.0.255.255
50 permit 10.11.0.0, wildcard bits 0.0.255.255
60 deny 10.10.0.0, wildcard bits 0.0.255.255
Router(config)#do show run | i access-list 3
access-list 3 deny 10.0.0.8
access-list 3 permit 10.0.0.2
access-list 3 permit 10.0.0.3
access-list 3 permit 10.0.0.1
access-list 3 deny 10.0.0.6
access-list 3 deny 10.0.0.7
access-list 3 permit 10.0.0.4
access-list 3 deny 10.0.0.5
access-list 3 permit 10.15.0.0 0.0.255.255
access-list 3 deny 10.14.0.0 0.0.255.255
access-list 3 permit 10.13.0.0 0.0.255.255
access-list 3 deny 10.12.0.0 0.0.255.255
access-list 3 permit 10.11.0.0 0.0.255.255
access-list 3 deny 10.10.0.0 0.0.255.255Once again, this reordering has no impact on the overall logic of the ACL and does not change the resulting fate of the packets.
I hope this helps - and my sincere thank you if you got this far in reading this lengthy post :)
Best regards,
Peter
For backward compatibility with previous releases, if entries with no sequence numbers are applied, the first entry is assigned a sequence number of 10, and successive entries are incremented by 10. The maximum sequence number is 2147483647. If the generated sequence number exceeds this maximum number, the following message is displayed:
