Lesson 6 - Router Design and Algorithms (Part 2) Flashcards
Why is packet classification needed?
Packet classification is needed to accomplish quality of service guarantees and security guarantees that longest prefix matching based on destination IP alone cannot do. This allows handling packets based on other criteria such as TCP flags and source addresses.
What are three established variants of packet classification?
Firewalls - filter out unwanted traffic and enforce other security policies
Resource reservation protocols - used to reserve bandwidth between source and destination
Routing based on traffic type - used to avoid delays for time-sensitive applications
What are the simple solutions to the packet classification problem?
Linear search, caching, and passing labels. Linear search is reasonable for a few rules (such as in a firewall) but otherwise inefficient. Caching can be useful to save time on future searches but still slow, especially for missed hits (linear search). Passing labels is done in the header and typically at the edges which saves time.
How does fast searching using set-pruning tries work?
Build a trie on destination prefixes and then at every leaf-node we “hang” the source tries that are compatible (or whatever other dimension we are considering for packet classification). To match a prefix, we first traverse the destination trie and then the source trie while keeping track of the lowest-cost matching rule.
What’s the main problem with the set pruning tries?
Memory explosion - a source prefix can occur in multiple destination tries
What is the difference between the pruning approach and backtracking approach for packet classification with a trie?
Set pruning has a high cost in memory with a lower cost in time. Backtracking saves memory but costs more in time. Each rule is only stored once.
What’s the benefit of the grid of tries approach?
It is a middle-ground approach that balances the memory and time costs by using precomputation with switch pointers. These are basically shortcuts.
Describe the “Take the Ticket” algorithm.
Each output line has a distributed queue for all input lines. Input lines request a ticket and wait their turn to connect to the output line.
What is head-of-line problem?
The other lines are stuck in the line waiting for their turn - the entire queue is blocked by the progress of the head of the queue.
How to avoid head-of-line problem using knockout scheme?
Break up the packets into a fixed size (cell). Have the fabric running N times faster than the input links where k is the expected number of cells received by an output link. For cases where the expectation is violated, randomly pick the output that is chosen. Complex to implement.
How to avoid head-of-line problem using parallel iterative matching?
All inputs send requests in parallel to all outputs they want to connect with. This is the request phase.
In the grant phase, the outputs randomly pick an input out of its requestors.
In the accept phase, inputs randomly pick an output to send to. This way, all of the inputs are sending packets from the start.
Describe FIFO with tail drop.
Packets are sent to the output ports. The output ports are FIFO and any packets that overflow the buffer (tail of the queue) are dropped. This results in fast scheduling decisions but loss of packets.
What are the reasons to make scheduling decisions more complex than FIFO?
To provide quality of service (QoS) guarantees on measures such as delay and bandwidth. To provide additional (router) support for congestion. To promote fair sharing of links among competing flows.
Describe Bit-by-bit round Robin scheduling.
Gives bandwidth and delay guarantees. We calculate the packet finishing time for each packet and send the packet with the smallest finishing round number based on the previous round of the algorithm.
Bit-by-bit Round Robin provides fairness, what’s the problem with this method?
Requires introducing extra time complexities such as keeping track of the finishing time (requires priority queue). The extra complexities make it hard to implement at gigabit speeds.
