Understanding Router Functions and Components

• Routers implement forwarding and control plane functions.
• Forwarding transfers packets between input and output link interfaces, occurring in nanoseconds and implemented in hardware.
• A router's main components include input/output ports, a switching fabric, and a routing processor.

Router Components

• Input ports terminate incoming links, decapsulate packets, and perform lookup functions using forwarding tables to direct packets through the switching fabric.
• The switching fabric moves packets between input and output ports via memory, bus, or crossbar.
• Output ports receive and queue packets from the switching fabric before sending them over outgoing links.

Control Plane Functions

• Control plane functions implement routing protocols, maintain routing tables, and compute forwarding tables.
• These functions are implemented in software within the routing processor or by a remote controller.

Router Operation

• Routers switch packets from input to output links, using the destination address.
• Time-sensitive tasks include lookup, switching, and scheduling.
• Lookup involves determining the output link using the destination IP address and the forwarding table (FIB), which maps destination prefixes to output links.
• Routers use longest prefix matching algorithms.

Additional Router Tasks

• Header validation and checksum: Checks packet version, decrements TTL, and recalculates header checksum.
• Route processing: Builds forwarding tables using routing protocols like RIP, OSPF, and BGP.
• Protocol processing: Implements protocols like SNMP, TCP/UDP, and ICMP.

Switching Methods

• Switching via memory involves the routing processor copying packets to memory and then to the output port buffer.
• Switching via bus uses an internal header to designate the output port before sending the packet over a shared bus.
• Switching via interconnection network uses a crossbar switch to connect input and output ports.

Router Challenges

• Routers face challenges related to bandwidth and Internet population scaling due to increasing devices, traffic, and technologies like optical links.
• Providing services at high speeds, such as protection against delays and attacks, is also a challenge.

Scaling Challenges

• Bottlenecks in exact lookups are addressed through link speed scaling and parallel hashing.
• Prefix lookups use link speed scaling and prefix database size scaling, solved with compressed multibit tries.
• Packet classification employs service differentiation, link speed, and size scaling, using decision tree algorithms and hardware parallelism (CAMs).
• Switching addresses optical-electronic speed gaps and head-of-line blocking, using crossbar switches and virtual output queues.
• Fair queueing tackles service differentiation, link speed scaling, and memory scaling, employing weighted fair queueing, deficit round robin, DiffServ, and core statelessness.
• Internal bandwidth copes with scaling of internal bus speeds through reliable striping.
• Measurement addresses link speed scaling with Juniper's DCU.
• Security scales with the number and intensity of attacks, using traceback with bloom filters and extracting worm signatures.

Prefix-Match Lookups

• Routers use prefix-match lookups to group multiple IP addresses by the same prefix due to Internet growth.

Prefix Notation

• Dot decimal: e.g., 132.234
• Slash notation: A/L (Address/Length), e.g., 132.238.0.0/16
• Masking: Using a mask to indicate relevant bits, e.g., 123.234.0.0 with mask 255.255.0.0

Variable Length Prefixes

• Classless Internet Domain Routing (CIDR) assigns IP addresses using arbitrary-length prefixes to decrease router table size, leading to longest-matching-prefix lookup.

Lookup Algorithm Challenges

• Routers perform lookups to determine the output port, facing challenges in lookup speed, memory, and update time.

Network Traffic Observations

• High concurrent short-duration flows make caching inefficient.
• Lookup speed is critical, with memory access being a significant cost.
• Unstable routing protocols impact update time.
• Memory usage is a trade-off between fast (SRAM) and slower (DRAM, SDRAM) memory.

Unibit Tries

• A simple prefix lookup technique using a binary tree structure.
• Every node has a 0 or 1 pointer to subtries for prefixes starting with 0 or 1.

Optimizing Prefix Matching

• The search traces the trie path until a match fails, returning the last known successful prefix.
• One-way branches are compressed for efficiency.

Multibit Tries

• Used to reduce memory accesses by checking multiple bits at each step (stride).

Prefix Expansion

• Used to ensure that prefixes are a multiple of the chosen stride length.

Multibit Tries: Fixed-Stride

• Each node represents multiple bits, and the prefix search moves ahead by the preset stride length.

Multibit Tries: Variable Stride

• Allows a different number of bits to be examined each time to save trie memory and minimize memory access, selected using dynamic programming.