Lesson 6: Study Guide

Question 1

Why is packet classification needed?

Answer 1

as internet increases, networks require service garauntees for traffic; packet classification allows handling of packets based on criteria

Question 2

What are three established variants of packet classification?

Answer 2

1. Firewalls: Routers implement firewalls at the entry and exit points of the network to filter out unwanted traffic or enforce security policies.
2. Resource reservation protocols: DiffServ has been used to reserve bandwidth between a source and a destination.
3. Routing based on traffic type: Routing based on the specific type of traffic helps avoid delays for time-sensitive applications.

Question 3

What are the simple solutions to the packet classification problem?

Answer 3

1. Linear Search : Firewall implementations perform a linear search of the rules database, pick best match rule.
2. Caching : cache the results so that future searches can run faster.
3. Passing Labels : intermediate routers between A and B apply a label header without having to redo packet classification. Used by Multiprotocol Label Switching (MPLS) and DiffServ

Question 4

How does fast searching using set-pruning tries work?

Answer 4

build a trie on the destination prefixes in the database, and then for every leaf-node at the destination trie to “hang” source tries.

Question 5

What’s the main problem with the set pruning tries?

Answer 5

memory explosion; a source prefix can occur in multiple destination tries.

Question 6

What is the difference between the pruning approach and the backtracking approach for packet classification with a trie?

Answer 6

backtracking has high lookup cost (time), but lower memory requirements

Question 7

What’s the benefit of a grid of tries approach?

Answer 7

reduce the wasted time in the backtracking search by using precomputation of switch pointers that take us directly to the next possible source trie containing a matching rule.

Question 8

Describe the “Take the Ticket” algorithm.

Answer 8

inside a crossbar switch, a scheduling algorithm, when an input line intends to send a packet to a specific output line, it requests a ticket. input line waits for the ticket to be served, then connects to the output line, the crosspoint is turned on, and the input line sends the packet.

Question 9

What is the head-of-line problem?

Answer 9

in take the ticket algo, when entire queue is blocked by the progress of the head of the queue.

Question 10

How is the head-of-line problem avoided using the knockout scheme?

Answer 10

it has the switching fabric running N times faster than the input links by breaking up packets into cells, it is complex

Question 11

How is the head-of-line problem avoided using parallel iterative matching?

Answer 11

break down the single queue into virtual queues, with one virtual queue per output link. more efficient than take a ticket. 3 phases:
1. request - all inputs send requests in parallel to outputs
2. grant - outputs pick a random request
3. accept - input randomly picks a grant, sends packet

Question 12

Describe FIFO with tail drop.

Answer 12

packets enter a router on input links, they are then looked up using the address lookup component, switching system places the packet in the corresponding output port. This port is a FIFO (first-in, first-out) queue. If output link buffer is full, incoming packets are dropped. Simple, fast scheduling decisions but potential loss in packets.

Question 13

What are the reasons for making scheduling decisions more complex than FIFO?

Answer 13

1. Router support for congestion
2. Fair sharing of links among competing flows
3. Providing QoS (quality of service) guarantees to flows

Question 14

Describe Bit-by-bit Round Robin scheduling.

Answer 14

it is used to avoid packet loss and introduce fairness in servicing different flows. ideally split packet up bit-by-bit, so this stratefy uses an imaginary bit-by-bit system to calculate the packet-finishing time and send a packet as a whole. packet with smallest finishing round number is sent

Question 15

Bit-by-bit Round Robin provides fairness; what’s the problem with this method?

Answer 15

time complexity is hard to implement with increased number of flows

Question 16

Describe Deficit Round Robin (DRR).

Answer 16

a quantum size (Qi) is assigned that determines the share of bandwidth allocated to a flow, and a deficit counter (Di). For each turn of round-robin, the algorithm will serve as many packets in the flow i with size less than (Qi + Di). If packets remain in the queue, it will store the remaining bandwidth in Di, otherwise Di will clear for next round.

Question 17

What is a token bucket shaping?

Answer 17

Used to limit the burstiness of a flow by
1. Limiting the average rate
2. Limiting maximum burst size

If the bucket is full with tokens, additional tokens are dropped. If bucket isn’t full, then packet waits until enough tokens are in the bucket

Problem: one queue per flow

Question 18

In traffic scheduling, what is the difference between policing and shaping?

Answer 18

both limit the output rate of a link.
Policer: at max traffic rate, excess traffic is dropped, or the packet’s setting or “marking” is changed. rate is a saw-toothed wave.
Shaper: retains excess packets in a queue or a buffer, and this excess is scheduled for later transmission. excess traffic is delayed instead of dropped. flow is shaped or smoothed when the data rate is higher than the configured rate

Question 19

How is a leaky bucket used for traffic policing and shaping?

Answer 19

leak rate of packets is constant, uniform distribution of packets sent to the network regardless of input rate.
conforming packet - does not overflow bucket
non-conforming- overflows bucket, is discarded