In Search of a Faster Routing Method
In the early days, routing an IPv4 packet at very high speed posed a big problem for router vendors and network operators. Because of the connectionless nature of the IP network, this IPv4 routing operation is repeated over and over when an IPv4 packet traverses through the network. Therefore, even a small increase of routing speed can produce big gains for network operation.
However, as IPv4 address space is 32-bit, IP routing requires a search into an address space that is 32 bits long. Certainly, it's impossible to perform a linear search into a 4 billion (232) table. So clever table organization and indexing must be employed to speed up the search of the routing table. And obviously, all these methods must work on the basis of a 32-bit space. With the advances in semiconductor technology, we now know that wire speed IPv4 routing can easily be achieved via ASIC and/or network processors. However, in the early-to-mid 1990s, Moore's law had not yet produced a wire speed IPv4 routing chip. So attention was focused on reducing the dimension of the search space. A 10-bit reduction of the bit length would mean a reduction of 1000-fold of the size of the address space. For a linear search, this meant a 1000-fold increase in speed. More gains in speed could be achieved with better algorithm design.
A real Internet routing table size is actually much smaller than 4 billion. In fact, even today the size of the Internet routing table is only in the order of 100,000. Therefore, smart engineers realized that with mapping performed prior to the routing table, and making the indexing key length smaller than 32 bits, much faster routing could be achieved.
Hence, various IP switching technologies emerged in the mid 1990s.