Transcript Stochastic Fair Blue: A Queue Management Algorithm for Enforcing

Stochastic Fair Blue: A Queue
Management Algorithm for
Enforcing Fairness
W. Feng, D. Kandlur, D. Saha, and K. Shin
Presented by
King-Shan Lui
BLUE vs RED
• RED relies on queue lengths to estimate
congestion
– Gives little information about number of
competing connections sharing the link
– Requires many parameters
• BLUE relies directly on packet loss and link
utilization
– Maintains a single probability
BLUE
Note: d1 >> d2
Stochastic Fair Blue
• Combines BLUE and Bloom filters
• L * N bins: L levels, each level has N bins
• Each level has a different hash function which
hash a flow to a bin of that level
• Each bin keeps dropping probability, pm, and the
queue occupancy statistics of packets belonging to
that bin
• If queue length > bin size, increase pm; if queue
length = 0, decrease pm
SFB
h0
h1
packet1
packet2
:
:
hL-1

0

1
:
:
:
:

Level 0
Level 1
N-1
Level L-1
Pseudocode
SFB
h0
0.2
h1
Non-responsive
packet1
pmin = 1
normal
1.0
:
:
1.0
Level 0

1.0
0

0.3
1
:
:
packet2
pmin = 0.2
hL-1
Level 1
:
:

N-1
Level L-1
Misclassification Problem
• Well-behaved flows may be misclassified as
non-responsive flows
• Prob. of misclassified – p
• Number of non-responsive flows – M
 
1
p  1  1  
  N 
M



L
Misclassification Problem (cont.)
• Amount of memory available – C
• C=L*N
Moving Hash Functions
• Periodically or randomly reset the bins and
change the hash functions
– Misclassified flows may be remapped
– Non-responsive flows may become responsive
and can be reclassified
• Problem: while reset, non-responsive may
grab more bandwidth
– Solution: Use two sets of bins
Round-Trip Time Sensitivity
• Connections with smaller RTT can
dominate the bandwidth
• When the number of small RTT connections
is small, SFB is still fine
• When the number of small RTT connections
is high, fairness between flows can be
affected
• Amount of unfairness is bounded for TCP
Comparison: RED w. Penalty Box
• Uses a finite log of recent packet loss events
• Identifies misbehaving flows based on log
• Log has to be large in some cases
• Non-responsive flows remain in “penalty
box” even after becoming well-behaved
• Relies on a TCP-friendliness check but is
difficult to determine
Comparison: Flow-RED
• Keeps state based on instantaneous queue
occupancy of a given flow
• If a flow occupies a lot of space, it is rate limited
• Requires a large buffer to work well
• Non-responsive flows are immediately reclassified
after they clear the packets
• When there are many non-responsive flows,
unable to distinguish from normal TCP flows
Comparison: RED with
Per-Flow Queueing
• Keeps per-flow information for active flows
• Requires O(N) states for N flows
Comparison: Stochastic Fair Queuing
• One level hash function
• Flows are mapped to separate queues
• Partitioning of buffers increases packet loss
rate and adversely impacts fairness
• Packets may be re-ordered (not FIFO) when
changing hash functions
Comparison: Core-Stateless
Fair Queueing
•
•
•
•
Attachs the flow rate in the packets at the edge
Intermediate routers calculate a dropping prob.
Requires additional information in the packets
Requires edge and intermediate routers both
understand the information
• Misconfigure of edge significantly impacts the
fairness
Contributions
• A different kind of queue management
• Protect normal TCP flows from nonresponsive flows
Remaining Issues
• How to determine bin_size, delta, L and N?
• Can we change L and N when M changes?
• Processing overhead in enqueue and
dequeue: O(L)