Three aspects of packet forwarding in the Internet

This thesis addresses packet forwarding in packet-switching networks such as the Internet. The interconnection points tying transmission links together in such networks are called routers, computers that may be specialized for the task. Routers need to decide where, when, and in what form each packet should be forwarded. This thesis concerns aspects of these three decisions. A router has to decide where an incoming packet is to be sent. Routers need to determine which outgoing link to use and in the case of multi-access links where on the link the packet should go. Packet headers contain addressing information that specifies the destination of the packet. For IP that information has to be matched with topological information, gathered by routing protocols that operate between routers, to determine the next hop in a viable path through the network. A fast algorithm for this matching operation, the IP routing lookup, is presented. When realized in software running on commercially available general-purpose processors such as the Pentium Pro or the DEC Alpha 21164, the algorithm can perform a few million matching operations per second. This is sufficient to support packet streams arriving at speeds of gigabits per second. In contrast, previous solutions to this problem have used special hardware support and/or have relied on traffic locality by caching the results of recent matching operations. Routers also need to determine when to forward each packet. When an outgoing link is busy, packets must be stored temporarily in the router until they can be forwarded. Modern routers use various queuing schemes to change the order in which packets are forwarded relative to the order in which they arrived. This is done to provide bounds on the latency through the network, and/or to guarantee certain transfer capacities to certain network users. Reservation protocols provide the parameters to these queuing schemes and thus allow network users to reserve network capacity for their traffic. The thesis explores mechanisms for advance reservations; resource reservations made potentially weeks or months before the traffic enters the network. It appears possible to keep the high link utilization of services using measurement based admission control algorithms, such as predictive service, even when resource reservations are made in advance. Finally, routers have to decide what form packets should have when forwarded. A problem with today's Internet Protocol is that headers are relatively large. When payloads are small, header overhead can become prohibitive. This thesis presents ways to reduce header sizes significantly, from 28-100 bytes down to 2-6 bytes. The disadvantage of large headers is thereby eliminated. The methods can be used for all IP packet streams and are, in contrast to previous solutions, usable over links with significant packet-loss rates such as wireless links. The techniques are useful for applications such as Internet telephony where voice samples are carried in a stream of many small packets, and for file transfers over highly asymmetrical (satellite) links where the back channel carrying acknowledgements is the bottleneck.Godkänd; 1997; 20061128 (haneit)