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.
