Lesson 5: Study Guide

Question 1

What are the basic components of a router?

Answer 1

1. input/output ports
2. switching fabric
3. routing processor

Question 2

Explain the forwarding (or switching) function of a router.

Answer 2

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.

Question 3

The switching fabric moves the packets from input to output ports. What are the functionalities performed by the input and output ports?

Answer 3

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

Question 4

What is the purpose of the router’s control plane?

Answer 4

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)

Question 5

What tasks occur in a router?

Answer 5

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

Question 6

List and briefly describe each type of switching. Which, if any, can send multiple packets across the fabric in parallel?

Answer 6

1. 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
2. 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.
3. 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

Question 7

What are two fundamental problems involving routers, and what causes these problems?

Answer 7

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

Question 8

What are the bottlenecks that routers face, and why do they occur?

Answer 8

1. Longest prefix matching - routers group destinations by prefix, but require complex algorithms for efficient matching
2. Service differentiation - routers have different service garauntees for different packets, but this requires more packet classification for complex criteria
3. Switching limitations - parallelism by crossbar switching handles high speed traffic, but this comes with limitations such as blocking

Question 9

Convert between different prefix notations (dot-decimal, slash, and masking).

Answer 9

1. dot - 132.234
2. slash - 132.238.0.0/16 (address/length)
3. 255.255.0.0 - tells which bits are important

Question 10

What is CIDR, and why was it introduced?

Answer 10

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

Question 11

Name 4 takeaway observations around network traffic characteristics. Explain their consequences.

Answer 11

1. network traffic has an increasing large number of concurrent flows of short duration; caching solutions will not work efficiently.
2. A large part of the cost of computation for lookup is accessing memory
3. unstable router can have slow update time in forwarding table impacting lookup speed
4. memory trade-off; use expensive fast memory (cache in software, SRAM in hardware) or cheaper but slower memory (e.g., DRAM, SDRAM).

Question 12

Why do we need multibit tries?

Answer 12

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.

Question 13

What is prefix expansion, and why is it needed?

Answer 13

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.

Question 14

Perform a prefix lookup given a list of pointers for unibit tries, fixed-length multibit ties, and variable-length multibit tries.

Answer 14

1. unibit - follow trie until no match, last successful prefix is the value to use
2. fixed-length multibit - fixed stride length (e.g. 001 = 3), follow trie to the pointer with the matching bits
3. variable-length multibit - saves prefix database memory; every node can have different numer of bits (e.g. 3 vs. 2), dynamic programming

Question 15

Perform a prefix expansion. How many prefix lengths do old prefixes have? What about new prefixes?

Answer 15

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

Question 16

What are the benefits of variable-stride versus fixed-stride multibit tries?

Answer 16

variable stride uses less memory