Internetworking with TCP/IP- P21: TCP/IP has accommodated change well. The basic technology has survived nearly two decades of exponential growth and the associated increases in traffic. The protocols have worked over new high-speed network technologies, and the design has handled applications that could not be imagined in the original design. Of course, the entire protocol suite has not remained static. New protocols have been deployed, and new techniques have been developed to adapt existing protocols to new network technologies | 168 Classless And Subnet Address Extensions CIDR Chap. 10 fix merely by looking at the address. The difference is important because it means that data structures and search algorithms used with classful addresses do not work when routing tables contain classless addresses. After a brief review of classful lookup we will consider one of the data structures used for classless lookup. Hashing And Classful Addresses All route lookup algorithms are optimized for speed. When IP permitted only classful addresses a single technique provided the necessary optimization hashing. When a classful address is entered in a routing table the router extracts the network portion N and uses it as a hash key. Similarly given a destination address the router also extracts the network portion N computes a hash function h N and uses the result as an index into a bucket. Hashing works well in a classful situation because addresses are self-identifying. Even if some entries in a table correspond to subnet routes hashing is still efficient because the network portion of the address can be extracted and used as a key. If multiple routes hash to the same bucket in the table entries within the bucket are arranged in decreasing order of specificity - subnet routes precede network routes. Thus if a given destination matches both a network route and a subnet route the algorithm will correctly find and use the subnet route. In a classless world however where addresses are not self-identifying hashing does not work well. Because it cannot compute the division between prefix and suffix a router cannot find a hash key for an arbitrary address. Thus an alternate scheme must be found. Searching By Mask Length The simplest lookup algorithm that accommodates classless addressing merely iterates over all possible divisions between prefix and suffix. That is given a destination address D the algorithm first tries using 32 bits of D then 31 bits and so on down to 0 bits. For each possible .
