Router Architecture

Router Architecture

Router architecture is shown in the figure below :

The four router components can be identified :

1. Input Ports : An input port performs several key functions. It performs the physical layer function of terminating an incoming physical link at a router; this is shown in the leftmost box of the input port and the rightmost box of the output port in the figure above. An input port also performs link-layer functions needed to interoperate with the link layer at the other side of the incoming link; this is represented by the middle boxes in the input and output ports. Perhaps most crucially, the lookup function is also performed at the input port; this will occur in the rightmost box of the input port. It is here that the forwarding table is consulted to determine the router output port to which an arriving packet will be forwarded via the switching fabric. Control packets (for example, packets carrying routing protocol information) are forwarded from an input port to the routing processor. Note that the term port here – referring to the physical input and output router interfaces – is distinctly different from the software ports associated with network applications and sockets.
2. 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!
3. Output Ports : An output port stores packets received from the switching fabric and transmits these packets on the outgoing link by performing the necessary link-layer and physical-layer functions. When a link is bidirectional (that is, carries traffic in both directions), an output port will typically be paired with the input port for that link on the same line card (a printed circuit board containing one or more input ports, which is connected to the switching fabric).
4. Rotating Processor : The routing processor executes the routing protocols, maintains routing tables and attached link state information, and computes for forwarding table for the router. It also performs the network management functions.

A router’s input ports, output ports, and switching fabric together implement the forwarding functions and are almost always implemented in hardware, as shown in the figure above.

These forwarding functions are sometimes collectively referred to as the router forwarding plane. To appreciate why a hardware implementation is needed, consider that with a 10 Gbps input link and a 64-byte IP datagram, the input port has only 51.2 ns to process the datagram before another datagram may arrive. If N ports are combined on a line card (as is often done in practice), the datagram-processing pipeline must operate N times faster – far too fast for software implementation. Forwarding plane hardware can be implemented either using a router vendor’s own hardware designs, or constructed using purchased merchant-silicon chips (e.g. as sold by companies as Intel and Broadcom).

While the forwarding plane operates at the nanosecond time scale, a router’s control functions – executing the routing protocols, responding to attached links that grow up or down, and performing management functions operate at the millisecond or second timescale. The router control plane functions are usually implemented in software and execute on the routing processor (typically a traditional CPU).

Before delving into the details of a router’s control and data plane, let’s return to our analogy where forwarding is compared to cars entering and leaving an interchange. Let’s suppose that the interchange is a roundabout, and that before a car enters the roundabout, a bit of processing is required – the car stops at an entry station and indicates its final destination (not at the local roundabout, but the ultimate destination, of its journey). An attendant at the entry station looks up the final destination, determines the roundabout exit that leads to that final destination, and tells the driver which roundabout exit to take. The car enters the roundabout (which may be filled with other cars entering from other input roads and heading to other roundabout exits) and eventually leavers at the prescribed roundabout exit ramp, where it may encounter other cars leaving the roundabout at that exit.

We can recognize the principal router components in the above figure in this analogy – the entry road and entry station correspond to the input port (with a lookup function to determine to local outgoing port); the roundabout corresponds to the switch fabric; and the roundabout exit road corresponds to the output port. With this analogy, it’s instructive to consider where bottlenecks might occur.

What happens if cars arrive blazingly fast (for example, the roundabout is in Germany or Italy!) but the station attendant is slow? How fast must the attendant work to ensure there’s no backup on an entry road? Even with a blazingly fast attendant, what happens if cars traverse the roundabout slowly – can backups still occur? And what happens if most of the entering cars all want to leave the roundabout at the same exit ramp – can backups occur at the exit ramp or elsewhere? How should the roundabout operate if we want to assign priorities to different cars, or block certain cars from entering the roundabout in the first place? These are all analogous to critical questions faced by router and switch designers.

Input Processing

A detail view of input processing is given in the figure below :

As discussed above, the input port’s line termination function and link-layer processing implement the physical and link layers for that individual input link. The lookup performed in the input port is central to the router’s operation – it is here that the router uses the forwarding table to look up the output port to which an arriving packet will be forwarded via the switch fabric. The forwarding table is computed and updated by the routing processor, with a shadow copy typically stored at each input port. The forwarding table is copied from the routing processor to the line cars over a separate bus (e.g. a PCI bus) indicated by the dashed line from the routing processor to the input line cards.

With a shadow copy, forwarding decision can be made locally, at each input port, without invoking the centralized routing processor on a per-packet basis and thus avoiding a centralized processing bottleneck.

Given the existence of a forwarding table, lookup is conceptually simple –we just search through the forwarding table looking for the longest prefix match. But at Gigabit transmission rates, this lookup must be performed in nanoseconds.

Thus not only must lookup be performed in hardware, but techniques beyond a simple linear search through a large table are needed. Special attention must also be paid to memory access times, resulting in designs with embedded on-chip DRAM and faster SRAM (used as a DRAM cache) memories.  Ternary Content Address Memories (TCAMs) are also often used to lookup. With a TCAM, a 32-bit IP address is presented to the memory, which return the content of the forwarding table entry for that address in essentially constant time.  The Cisco 8500 has a 64K CAM for each input port.

Once a packet’s output port has been determined via the lookup, the packet can be sent into the switching fabric. In some designs, a packet may be temporarily blocked from entering the switching fabric if packets from other input porta are currently using the fabric. A blocked packet will be queued at the input port and then scheduled to cross the fabric at a later point in time.

Although “lookup” is arguably the most important action in input port processing, many other actions must be taken:

1. Physical- and link-layer processing must occur
2. The packet’s version number, checksum and time-to-live filed must be checked and the latter two fields rewritten
3. Counters used for network management (such as the number of IP datagrams needed) must be updated.

The input port steps of looking up an IP address (“match”) then sending the packet into the switching fabric (“action”) is a specific case of a more general “match plus action” abstraction that is performed in many network devices, not just routers.

In link-layer switches, link-layer destination addresses are looked up and several actions may be taken in addition to sending the frame into the switching fabric towards the output port.

In firewalls, devices that filter out selected incoming packets, an incoming packet whose header matches a given criteria (e.g. a combination of source/destination IP and addresses and transport-layer port numbers) may be prevented from being forwarded (action).

In a network address translator (NAT) an incoming packet whose transport-layer port number matches a given value will have its port number rewritten before forwarding (action). Thus, the “match plus action” abstraction is both powerful and prevalent in network devices.

Switching

The switching fabric is at the very heart of a router, as it is through this fabric that the packets are actually switched (that is, forwarded) from an input port to an output port. Switching can be accomplished in a number of ways, as shown in the figure below :

• Switching via memory : The simplest, earliest routers were traditional computers, with switching between input and output ports being done under direct control of the CPU (routing processor). Input and output ports functioned as traditional I/O devices in a traditional operating system. An input port with an arriving packet first signalled the routing processor via an interrupt. The packet was then copied from the input port into processor memory. The routing processor then extracted the destination address from the header, looked up the appropriate output port in the forwarding table, and copied the packet to the output port’s buffers.

In this scenario, if the memory bandwidth is such that B packets per second can be written into, or read from, memory, then the overall forwarding throughput (the total rate at which packets are transferred from input ports to output ports) must be less than B/2. Note also that two packets cannot be forwarded at the same time, even if they have different destination ports, since only one memory read/write over the shared system bus can be done at a time.

Many modern routers switch via memory. A major difference from early routers, however, is that the lookup of the destination address and the storing of the packet into the appropriate memory location are performed by processing on the input line cards. In some ways, routers that switch via memory look very much like shared-memory multiprocessors, with the processing on a line card switching (writing) packets into the memory of the appropriate output port. Cisco’s Catalyst 8500 series switches forward packets via a shared memory.

• Switching via a Bus : In this approach, an input port transfers a packet directly to the output port over a shared bus, without intervention by the routing processor. This is typically done by having the input port pre-pend a switch-internal label (header) to the packet indicating the local output port to which this packet is being transferred and transmitting the packet onto the bus. The packet is received by all output ports, but only the port that matches the label will keep the packet. The label is then removed at the output port, as this label is only used within the switch to cross the bus. If multiple packets arrive to the router at the same time, each at a different input port, all but one must wait since only one packet can cross the bust at a time. Because every packet muss cross the single bus, the switching speed of the router is limited to the bus speed: in our roundabout analogy, this is as if the roundabout could only contain one car at a time. Nonetheless, switching vis a bus is often sufficient for routers that operate in small local area and enterprise networks. The Cisco 5600 switches packets over 32 Gbps backplane bus.
• Switching via an Interconnection Network : One way to overcome the bandwidth limitation of a single, shared bus is to use a more sophisticated interconnection network, such as those that have been used in the past to interconnect processors in a multiprocessor computer architecture. A crossbar switch is an interconnection network consisting of 2N busses that connect N input ports to N output ports, as shown in the figure above. Each vertical bus intersects each horizontal bus at a crosspoint, which can be opened or closed at any time by the switch fabric controller (whose logic is part of the switch fabric itself). When a packet arrives from port A and needs to be forwarded to port Y, the switch controller closes the crosspoint at the intersection of buses A and Y, and port A then sends the packet onto its bus, which is picked up (only) by bus Y. Note that a packet from port B can be forwarded to port X at the same time, since the A-to-Y and B-to-X packets use different input and output busses. Thus, unlike the previous two switching approaches, crossbar networks are capable of forwarding multiple packets in parallel. However, if two packets from two different input ports are destined to the same output port, then one will have to wait at the input, since only one packet can be sent over any given bus at a time.

More sophisticated interconnection networks use multiple stages of switching elements to allow packets from different input ports to proceed towards the same output port at the same time through the switching fabric.

Output Processing

Output port processing, shown in the figure below, takes packets that have been stored in the output port’s memory and transmits them over the output link. This includes selecting and de-queuing packets for transmission, and performing the needed link-layer and physical-layer transmission functions.