4.2 Inside a Router

There are four router components:

1. Input Ports: performs several key functions. Terminates incoming physical link at the router, link layer inter - operation, loook - up function (most important). Look up functino consults fw table for determining output port(Physical ports - interfaces of routers).
2. Switching fabric: inter network inside the router that connects input port to output port
3. Output Port: Stores packets from switchgin fabric then transmits to outgoing link. Performs link-layer, physical-layer functions. For bidirectional link, output port is payerd with the input port.
4. Routing processor: performs control-plane functions. In traditional routers, executes routing protocols (5.3,5.4). In SDN, it communicates with remote controller for receiving fw tables and install them at the router’s input port. Also performs network management functions (5.7).

The four components are mostly implemented in hardware for fast processing.

Q. How does router deal with congestion?

4.2.1 Input Port Processing and Destination-Based Forwarding

The forwarding table from processor is compied to line cards over a sepaarate bus(PCI), so forwarding decisions is made locally at the input port → avoid bottleneck. For 32-bit IP address, brute force algorithm cannot serve the look up operation (4billion entries).

By longest matching prefix, can improve efficiency. The lookups must be performedin nanoseconds for Gagiabit transmission rates. Also memory access must be fast, Ternary Content Addressable Memories(TCAM) is practically used.

💡 Input port’s look up (”match”) and sending to switching fabric (”action”) is a general match + action abstraction.

match + action abstraction은 여기서만 쓰는게 아니라 link layer, firewall, network address trasnlator(NAT 4.3) 등 여기저기서 많이 쓰인다.

4.2.2 Switching

Switching fabric is heart of router. There are different ways for switching.

Memory: Simple and early routers were computers done by the CPU. Innput packet arrives, then copied to memory. Then router processor extracts dest. address and looks up in the forwarding table. Then it is copied tot he appropriate output port. This was limited by memory bnadwidth and single operation at a same time since only one memory read/write can be performed at a time.

Bus: Arriving packets with label(header) traverse the output ports and the matching port will keep the packet. This is limited by bus speed, since only one packet can cross the bus at a time.

Interconnection network: Each veritcal bus intersacts horizontal bus at crosspoint, which can be opened or closed. Therefore multiple packets can travel at the same time. Also multiple stages are used to allow multi point transfer of the packets.

4.2.3 Output Port Processing

Packets stored at output port’s memory is transmitted to output link. There are selecting(scheduling), de-queueing packets, link-layer & physical layer transmission functions.

4.2.4 Where does Queueing Occur?

Queueing can occur at both input and output ports. Queueing characteristics will depend on traffic load, speed of switching fabric, and line speeds. When the queue grow too large, the memory will be exhausted and result in packet loss.

Input Queueing

If switch fabric is not fast enough, queue occurs at input ports. Packets can experience HOL blocking.

Output Queueing

Even if the switch is much faster than port line speeds, since each port line speed is limited, queueing can form. Eventually, if the queued packets grow large to cause memory exhaustion, it can cause packet drop.

Output queue at top, packet scheduler must choose one packet for transmission.(priority)

In manaigng buffer overflow, drop-tail policy drops arriving packet. Before the packet gets really full, Explicit Congestion Notification(3.7.2) bit can be used to signal high buffer level. Random Early Detection is widely used active queue management algorithm.

💡 Buffer can absorb short-term flucctuations but also lead increased delay and attendant(user) concerns. Just the right amount is good like salt.

Bufferbloat is a long delay due to persistent buffering.

4.2.5 Packet Scheduling

Q. What order are the queued packets transmitted from output link to the outgoing link?

FCFS, Priority Queue, RoundRobin…

First in First out FIFO

FIFO selects packets in same order they arrived.

assume three time unit for departure

Priority Queueing

Packets at the output link can be classified into priority classes. For example, VoIP packet may receive prioirty over email packets.

Queue within same class is usually done in FIFO.

Round Robin and Weighted Fair Queueing(WFQ)

WFQ is different from RR that each class m ay receive different amount of service time.

So what do we use then?