Within the Internet, there exists a packet-switch network which functions to for ward packets from source to destination in order to enable end-to-end connections. The key attribute to enable such a procedure consists of several crucial components, including routing protocol(s), transmission links and routers. While a plethora of literature on routing protocols has been presented in the last decade, the transmission technology is constantly evolving. As a result, provision of tens...
Within the Internet, there exists a packet-switch network which functions to for ward packets from source to destination in order to enable end-to-end connections. The key attribute to enable such a procedure consists of several crucial components, including routing protocol(s), transmission links and routers. While a plethora of literature on routing protocols has been presented in the last decade, the transmission technology is constantly evolving. As a result, provision of tens gigabit iber links is commonly available now. Yet, the research on high-speed routers is limited insofar and, therefore, increases in its importance. To meet the demands of new multimedia applications, multi-tera routers have been designed. A multi-tera router should have enough internal bandwidth to switch packets between its interfaces at multi-tera rates and enough packet processing power to forward multiple millions of packets per second (MPPS). Switching in the router has been well studied. However, the remaining major bottleneck for a high performance router design is to speed up the multi-memory-access IP packet forwarding engine.The rate of the packet forwarding engines can be burdened by several factors. The major obstacle lies in the space limitation of IPv4 which leads to the occurrence of classless interdomain routing (CIDR). The address preix, specifying next-hop for a set of addresses, transforms from ixed length to variable length. Therefore, the packet forwarding engine must be able to derive the best matching preix (BMP) among the variable-length preixes. Unlike exact matching, the procedure of BMP requires more pre-computation to enable fast search. The second obstacle would be the incoming IPv6. Although IPv6 can overcome the problem of exhausting IPv4 address space, its huge space also increases the complexity of BMP search. Other factors affecting the speed of packet forwarding engines include the limited storage of high-speed memory, power consumption and the issues of table updates. Since there is no single solution it under every circumstance, how to select a suitable solution for different applications is thereby important.To solve these difficulties, numerous algorithms are proposed in the last few years. These algorithms address these performance issues via different approaches. For example, some of them try to compress data structures into high-speed SRAMs, while others utilize the architecture of modern processors. There are some others who resort to hardware implementation. Generally, these algorithms can be categorized into software based and hardware based according to the method of implementation. In this book, an introduction of four algorithms will be provided in terms of their major contributions, performance, merits and weaknesses.
