What's Inside a Router

What's Inside a Router

Now that we've seen an overview of the functions and services of the network layer, let's turn our attention to the network layer's forwarding function - the actual transfer of packets from a router's incoming links to the appropriate outgoing links. We already took a brief look at a few forwarding issues in "Virtual Circuit and Datagram Networks", namely, addressing and longest prefix matching. In this section we'll examine particular router architectures for transferring packets from incoming links to outgoing links. Our coverage here is necessarily brief, as an entire course would be required to cover router design in depth. Therefore, we'll make a special effort in this section to provide pointers to material that covers this topic in more depth. We mention here in passing that the words forwarding and switching are frequently used interchangeably by computer-networking researchers and practitioners; we'll use both terms in this blog.

A high-level view of a generic router architecture is shown in Figure 1. Four components of a router can be identified:

●  Input ports. The input port performs many functions. It performs the physical-layer functions (the leftmost box of the input port and he rightmost box of the output port in Figure 1) of terminating an incoming physical link to a router. It performs the data link-layer functions (represented by the middle boxes in the input and output ports) required to interoperate with the data link-layer functions at the remote side of the incoming link. It also performs a lookup and forwarding function (the rightmost box of the input port and the leftmost box of the output port)

Router architecture

so that a packet forwarded into the switching fabric of the router emerges at the appropriate output port. Control packets (for instance, packets carrying routing protocol information) are forwarded from an input port to the routing processor. In practice, multiple ports are frequently gathered together on a single line card within a router.

●  Switching fabric. The switching fabric connects the router's input ports to its output ports. This switching fabric is completely contained within the router - a network inside of a network router.

●  Output ports. An output port stores the packets that have been forwarded to it through the switching fabric and then transmits the packets on the outgoing link. The output port thus performs the reverse data link - and physical-layer functionality of the input port. When a link is bidirectional (that is, carries traffic in both directions), an output port to the link will typically be paired with the input port for that link, on the same line card.

●  Routing processor. The routing processor executes the routing protocols (for instance, the protocols we study in "Routing in the Internet"), maintains the routing information and forwarding tables, and performs network management functions within the router.

In the following subsections, we'll Iook at input ports, the switching fabric, and output ports in more detail. [Chuang 2005; Keslassy 2003; Chao 2001; Turner 1988; Giacopelli 1990; McKeown 1997a; Partridge 1998] provide a discussion of some particular router architectures. [McKeown 1997b] provides a particularly readable overview of modern router architectures, using the Cisco 12000 router as an example. For concreteness, the ensuing discussion assumes that the computer network is a packet network, and that forwarding decisions are based on the packet's destination address (rather than a VC number in a virtual-circuit network). Though, the concepts and techniques are similar for a virtual-circuit network.

Input Ports


A more detailed view of input port functionality is given in Figure 2. As discussed above, the input port's line termination function and data link processing implement the physical and data link layers associated with an individual input link to the router. The lookup/forwarding module in the input port is central to the forwarding function of the router. In many routers, it is here that the router determines the output port to which an arriving packet will be forwarded via the switching fabric. The choice of the output port is made using the information contained in the forwarding table. Although the forwarding table is computed by the routing processor, a shadow copy of the forwarding table is typically stored at each input port and updated, as required, by the routing processor. With local copies of the forwarding table, the forwarding decision can be made locally, at each input port, without invoking the centralized routing processor. Such decentralized forwarding avoids creating a forwarding processing bottleneck at a single point within the router. 

In routers with limited processing capabilities at the input port, the input port may simply forward the packet to the centralized routing processor, which will then perform the forwarding table lookup and forward the packet to the appropriate output port. This is the approach taken when a workstation or a server serves as a router; here, the routing processor is really just the workstation's CPU, and the input port is really just a network interface card (for instance, an Ethernet card).

Given the existence of a forwarding table, table lookup is conceptually simple - we just search through the forwarding table looking for the longest prefix match, as described in "Datagram Networks". In practice, though, life is not so simple.

Input port processing

Perhaps the most important complicating factor is that backbone routers must operate at high speeds, performing millions of lookups per second. In reality, it is desirable for the input port processing to be able to proceed at line speed, that is, for a lookup to be performed in less than the amount of time required to receive a packet at the input port. In this case, input processing of a received packet can be completed before the next receive operation is complete. To get an idea of the performance requirements for a lookup, consider that an OC-48 link runs at 2.5 Gbps. With packets 256 bytes long, this implies a lookup speed of approximately 1 million lookups per second.

Given the need to operate at today's high link speeds, a linear search through a large forwarding table is impossible. A more reasonable technique is to store the forwarding table entries in a tree data structure. Each level in the tree can be thought of as corresponding to a bit in the destination address. To look up an address, one simply starts at the root node of the tree. If the first address bit is a zero, then the left subtree will contain the forwarding table entry for the destination address; otherwise it will be in the right subtree. The appropriate subtree is then traversed using the remaining address bits - if the next address bit is a zero, the left subtree of the initial subtree is chosen; otherwise, the right subtree of the initial subtree is chosen. In this manner, one can look up the forwarding table entry in N steps, where N is the number of bits in the address. (Note that this is essentially a binary search through an address space of size 2N). An improvement over binary search techniques is described in [Srinivasan 1999], and a general survey of packet classification algorithms can be found in [Gupta 2001].

But even with N = 32 (for example, a 32-bit IP address) steps, the lookup speed via binary search is not fast enough for today's backbone routing requirements. For instance, assuming a memory access at each step, fewer than a million address lookups per second could be performed with 40 ns memory access times. Many techniques have thus been explored to increase lookup speeds. Content addressable memories (CAMs) allow a 32-bit IP address to be presented to the CAM, which returns the content of the forwarding table entry for that address in essentially constant time. The Cisco 8500 series router has a 64K CAM for each input port.

Another technique for speeding up lookup is to keep recently accessed forwarding table entries in a cache [Feldmeier 1988].  Here, the concern is the potential size of the cache. Fast data structures, which allow forwarding table entries to be located in log(N) steps [Waldvogel 1997], or which compress forwarding tables in novel ways [Brodnik 1997], have been proposed. A  hardware-based approach to lookup that is optimized for the common case that the address being looked up has 24 or fewer  significant bits is discussed in [Gupta 1998]. For a survey and taxonomy of high-speed IP address lookup algorithms, see [Ruiz-Sanchez 2001].

Once the output port for a packet has been determined via the lookup, the packet can be forwarded into the switching fabric.  However, a packet may be temporarily blocked from entering the switching fabric (due to the fact that packets from other input ports are currently using the fabric). A blocked packet must thus be queued at the input port and then scheduled to cross the switching fabric at a later point in time. We'll examine the blocking, queuing and scheduling of packets (at both input ports and output ports) within a router in "Where Does Queuing Occur".


Tags

network layer, line card, router, switching fabric, forwarding table, line speed

Copy Right

The contents available on this website are copyrighted by TechPlus unless otherwise indicated. All rights are reserved by TechPlus, and content may not be reproduced, published, or transferred in any form or by any means, except with the prior written permission of TechPlus.