Lesson 6 - Router Design and Algorithms (part 2) Flashcards
Why do we need packet classification?
Packet forwarding based on the longest prefix matching of destination IP addresses is not enough and we need to handle packets based on multiple criteria (TCP flags, source addresses)
Name 3 established variants of packet classification.
- Firewall
- Resource reservation protocols
- Routing based on traffic type:
What are the simple solutions to the packet classification problem?
Linear search - search through rules, keep track of best-match
Cache - cache common rules
Passing Labels
How does fast searching using set-pruning tries work?
First matches the destination IP address in a packet in the destination trie. Then traverse the corresponding source trie to find the longest prefix match for the source IP.
What’s the main problem with the set pruning tries?
High memory cost. Because a source prefix can occur in multiple destination tries.
Pruning approach vs backtracking approach. What’s the difference?
pruning has high memory cost,
backtracking takes more time.
What’s the benefit of grid of tries approach?
reduce the wasted time in the backtracking by using pointers to next solution.
Describe “take the ticket algorithm”.
Each input line requests a ticket from an output line. When an input’s ticket is next, the input is allowed to send a packet on the output line.
What is head-of-line problem?
The entire queue is blocked by the progress of the head of the queue.
How to avoid head-of-line problem using knockout scheme?
instead of queueing, randomly pick which packets can be sent over an output link. ??
How to avoid head-of-line problem using parallel iterative matching?
- Inputs make request on all needed outputs.
- Outputs receiving multiple requests randomly select one to grant access to.
- Input’s with multiple grants randomly pick an output to send to.
- repeat
Explain how FIFO with tail drop works.
- Input links determine which output link a packet is to be sent to by looking up the address.
- The switching system places the packet on the appropriate output queue.
- If the queue is full, the packet is dropped.
- If the packet makes the queue it is served in first-in-first-out order.
What are the reasons to make scheduling decisions more complex than FIFO?
Router support for congestion
Fair sharing of links among competing flows
Providing QoS guarantees to flows
(see Scheduling Introduction)
How does bit-by-bit round robin scheduling method work?
packets are sent in a round robin manner such that the transmission rate is near equal for all flows.
Bit-by-bit round robin provides fairness, but it has a problem. What’s exactly the problem with this method?
Bit-by-bit itself is not possible because you would have to split the packets. It is an imaginary model used to consider Packet-level Fair Queuing. Packet-level Fair Queuing - Requires a priority queue implementation, which has time complexity which is logarithmic in the number of flows! Additionally, if a new queue becomes active, all timestamps may have to change – which is an operation with time complexity linear in the number of flows.
How does deficit round robin work?
A quantum size and deficit counter is incorporated that keeps track of the bandwidth available per flow. For example a deficit round robin with a quantum size of 500 will allow any packet less than or equal to 500 to be sent. For packets less than 500 the remainder is stored in the deficit counter.
(See Deficit Round Robin)
What is a token bucket shaping?
A bucket is filled with tokens at a rate of R. If the bucket is full then packets are dropped. When a packet arrives, it can go through if there are enough tokens (equal to the size of packet in bits). If not, the packet needs to wait until enough tokens are in the bucket.
In traffic scheduling, what is the difference between policing and shaping?
Policer: When traffic rate reaches the maximum configured rate, excess traffic is either dropped, or the setting or “marking” of a packet is changed. The output rate appears as a saw-toothed wave.
Shaper: A shaper typically retains excess packets in a queue or a buffer and this excess is scheduled for later transmission. The result is that excess traffic is delayed instead of dropped. Thus, when the data rate is higher than the configured rate, the flow is shaped or smoothed. Traffic shaping and policing can work in tandem.
What is leaky bucket? How is it used for traffic policing and shaping?
Leaky bucket regulates flow to the network by allowing a constant send rate (shaping). If packet’s overflow the bucket, they’re dropped (policing)
Explain Backtracking
suggest answer
