What are the basic components of a router?
- input/output ports
- switching fabric
- routing processor
Explain the forwarding (or switching) function of a router.
transfer a packet from an input link interface to the appropriate output link interface, occurs at very short timescales (typically a few nanoseconds) and is typically implemented in hardware.
The switching fabric moves the packets from input to output ports. What are the functionalities performed by the input and output ports?
Input Ports:
1. physically terminate the incoming links to the router
2. data link processing unit decapsulates the packets.
3. perform the lookup function, consult the forwarding table to ensure that each packet is forwarded to the appropriate output port through the switch fabric.
Output Ports:
1. receive and queue the packets from the switching fabric
2. send them over to the outgoing link
What is the purpose of the router’s control plane?
implementing the routing protocols, maintaining the routing tables, computing the forwarding table. All these functions are implemented in software in the routing processor (or remote controller)
What tasks occur in a router?
Time-sensitive:
1. Lookup - at input link, router looks at the destination IP address and determines the output link by looking at the forwarding table (Forwarding Information Base or FIB).
2. Switching - transfer the packet from the input link to the output link. Modern fast routers use crossbar switches
3. Queuing - at output link
Time in-sensitive:
1. Header validation and checksum
2. Route processing - use routing protocol to build FIB
3. Protocol Processing - e.g. SNMP, TCP/UDP
List and briefly describe each type of switching. Which, if any, can send multiple packets across the fabric in parallel?
- Switching via memory - when input port receives packet, it is copied to processor’s memory, it consults forwarding table, then copies packet to output port buffer
- Switching via bus - packet at input port adds a header that designates which output port, then “rides the bus” (*1 packet *at a time), stops at each port until desired port.
- Switching via interconnection network - crossbar switch, connects N input ports to N output ports with 2N buses, switching fabric will close the crosspoints so packet travels directly to intended output port. can carry* multiple packets* simulatenously, if different input and output
What are two fundamental problems involving routers, and what causes these problems?
1.Bandwidth and Internet population scaling - caused by caused by: increasing number of devices that connect to the Internet, increasing volumes of network traffic due to new applications, and new technologies such as optical links that can accommodate higher volumes of traffic.
2. Services at high speeds - caused by new applications requiring protection services against failure or traffic
What are the bottlenecks that routers face, and why do they occur?
- Longest prefix matching - routers group destinations by prefix, but require complex algorithms for efficient matching
- Service differentiation - routers have different service garauntees for different packets, but this requires more packet classification for complex criteria
- Switching limitations - parallelism by crossbar switching handles high speed traffic, but this comes with limitations such as blocking
Convert between different prefix notations (dot-decimal, slash, and masking).
- dot - 132.234
- slash - 132.238.0.0/16 (address/length)
- 255.255.0.0 - tells which bits are important
What is CIDR, and why was it introduced?
Classless Internet Domain Routing - assigns IP addresses using arbitrary-length prefixes, goal was to reduce the router table size, but this introduced longest prefix matching problem
Name 4 takeaway observations around network traffic characteristics. Explain their consequences.
- network traffic has an increasing large number of concurrent flows of short duration; caching solutions will not work efficiently.
- A large part of the cost of computation for lookup is accessing memory
- unstable router can have slow update time in forwarding table impacting lookup speed
- memory trade-off; use expensive fast memory (cache in software, SRAM in hardware) or cheaper but slower memory (e.g., DRAM, SDRAM).
Why do we need multibit tries?
technique for prefix lookup; unibit takes up too much memory, multibit uses a stride - number of bits to check at each step, each node has 2k children, k = stride.
What is prefix expansion, and why is it needed?
strategy that expands a given prefix to more prefixes, ensures that the expanded prefix is a multiple of the stride length, gives us more speed with an increased cost of the database size.
Perform a prefix lookup given a list of pointers for unibit tries, fixed-length multibit ties, and variable-length multibit tries.
- unibit - follow trie until no match, last successful prefix is the value to use
- fixed-length multibit - fixed stride length (e.g. 001 = 3), follow trie to the pointer with the matching bits
- variable-length multibit - saves prefix database memory; every node can have different numer of bits (e.g. 3 vs. 2), dynamic programming
Perform a prefix expansion. How many prefix lengths do old prefixes have? What about new prefixes?
the expanded prefix is a multiple of the chosen stride length.
e.g. substitue (expand) P3 = 1100* with 110010* and 110011*, stride = 6
old prefixes have more types of lengths, new prefixes have less types of lengths, but more prefixes
What are the benefits of variable-stride versus fixed-stride multibit tries?
variable stride uses less memory
