• Router architecture
  • Forwarding plane are usually implemented in hardware and operates at the nanosecond time scale
    • Input ports
      • Perform the physical layer function of terminating an incoming physical link at a router
      • Perform link-layer functions needed to interoperate with the link layer at the other side of the incoming link
      • The lookup function is also performed at the input port
        • The forwarding table is consulted here to determine the router output port to which an arriving packet will be forwarded via the switching fabric
        • The forwarding table is copied from the routing processor to the line cards over a separate bus
      • Forward control packets to the routing processor
    • Switching fabric
      • Connect the router’s input ports to its output ports
      • Completely contained within the router—a network inside of a network router!
    • Output ports
      • Store packets received from the switching fabric and transmits these packets on the outgoing link
        • When a link is bidirectional, an output port will typically be paired with the input port for that link
  • Control plane operates at the millisecond or second timescale
    • Routing processor
      • Execute routing protocols, maintain routing tables and link state information, and compute the forwarding table
    • A router's control control plane functions are usually implemented in software and execute on the routing processor

Input Processing

• In some designs, a packet may be temporarily blocked from entering the switching fabric and queued at the input port if packets from other input ports are currently using the fabric
• Although "lookup" is arguably the most important action in input port processing, many other actions must be taken: physical- and link-layer processing must occur; the packet's version number, checksum and time-to-live field must be checked and the latter two fields rewritten; and counters used for network management such as the number of IP datagrams received must be updated

Switching

• Implementation
  • Switching via memory
    • An input port with an arriving packet first signaled the routing processor via an interrupt, and 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
    • If the memory bandwidth is such that $B$ packets per second can be written into or read from memory, then the overall forwarding throughput 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
  • Switching via a bus
    • An input port transfers a packet directly to the output port over a shared bus, without intervention by the routing processor, by having the input port pre-pend a switch-internal label (header) to the packet indicating the local output port 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 bus at a time
  • Switching via an interconnection network
    • A crossbar switch is an interconnection network consisting of $2N$ buses connecting $N$ input ports to $N$ output ports
      • Each vertical bus intersects each horizontal bus at a crosspoint, which can be opened or closed at any time by the switch fabric controller
    • 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 busses 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
      • 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

Output Processing

• Take packets that have been stored in the output port's memory and transmits them over the output link
  • Include selecting and de-queueing packets for transmission, and performing the link-layer and physical-layer transmission functions

Where Does Queueing Occur?

• The location and extent of queueing (either at the input port queues or the output port queues) will depend on the traffic load, the relative speed of the switching fabric, and the line speed
• Output port queuing
  • If the packet arrival rate via switch exceeds output line speed, then packet queuing can occur at the output ports
• Buffer amount
  • RFC 3439 specifies that the amount of buffering, $B$, is equal to an average round-trip time times the link capacity, $C$
  • Recent theoretical and experimental efforts suggest that when there are a large number of TCP flows, $N$, passing through a link, the amount of buffering needed is $B=\frac{RTT*C}{\sqrt{N}}$
• Input port queueing
  • If the switch fabric is not fast enough to transfer all arriving packets, then packet queuing can occur at the input ports
  • Head-of-the-Line (HOL) blocking: A queued packet in an input queue must wait for transfer through the fabric because it is blocked by another packet at the head of the line

Two packets (darkly shaded) at the front of their input queues are destined for the same upper-right output port. Suppose that the switch fabric chooses to transfer the packet from the front of the upper-left queue. In this case, the darkly shaded packet in the lower-left queue must wait. But not only must this darkly shaded packet wait, so too must the lightly shaded packet that is queued behind that packet in the lower-left queue even though there is no contention for the middle-right output port.

• Active queue management (AQM) algorithms (packet-dropping and -marking policies)
  • If there is not enough memory to buffer, a decision must be made to either drop the arriving packet (a policy known as drop-tail) or remove one or more already-queued packets to make room for the newly arrived packet
    • The router may drop (or mark the header of) a packet before the buffer is full in order to provide a congestion signal to the sender
  • Random Early Detection (RED) algorithm
    • A weighted average is maintained for the length of the output queue
      • If the average queue length is less than a minimum threshold, $min_{th}$, the packet is admitted when it arrives
      • If the queue is full or the average queue length is greater than a maximum threshold, $max_{th}$, the packet is marked or dropped when it arrives
      • If the packet arrives to find an average queue length in the interval $[min_{th}, max_{th}]$, the packet is marked or dropped with a probability that is typically some function of the average queue length, $min_{th}$, and $max_{th}$

The Routing Control Plane

• Since the routing control plane fully resides and executes in a routing processor within the router, the network-wide routing control plane is decentralized—with different pieces (e.g., of a routing algorithm) executing at different routers and interacting by sending control messages to each other
• The router and switch vendors also bundle their hardware data plane and software control plane together into closed (but inter-operable) platforms in a vertically integrated product