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. Routers also need to determine when to forward each packet.