Home / Networking Basics / End-to-End Delay Guarantee in Weighted Fair Queueing WFQ

End-to-End Delay Guarantee in Weighted Fair Queueing WFQ

  • Using the simple deterministic queueing model, if the arrival process A(t) grows very large, then we can have at some time Q(t) >= B (where B is the size of the queue). This leads to packet drops. We can not talk about delay guarantees if we have packet drops.
  • To avoid the situation of buffer overflow, we need a way to guarantee that, at any time:

A(t+T) – A(t) <= B + R1*T, where:

    • B is the size of the queue,
    • R1 is the service rate of the queue (i.e. the rate at which the queue is drained)
    • T is any time interval.
  • In more general terms, A(t) must be regulated by the (σ,ϼ) function, which is σ + ϼ*t. This means:
    • A(t) will never exceed (σ,ϼ)(t): A(t) < σ + ϼ*t , and
    • at any time t, the arriving bits have an upper bound of σ + ϼ*t. Taking σ = B and ϼ = R1, we get B + R1*t
(σ,ϼ)-constraint

(σ,ϼ)-constrained A(t). A(t) is plotted in green, while (σ,ϼ)(t) is plotted in blue – © Stanford University

  • The (σ,ϼ) function gives us these interesting values:
    • The maximum queue size Bmax is the vertical distance between (σ,ϼ) function and D(t).
    • the maximum delay a bit takes in the queue dmax is the horizontal distance between (σ,ϼ) function and D(t)
maximum-delay-maximum-queue-occupancy

Determining the upper bounds on the queue delay and the queue occupancy. D(t) is plotted in red – © Stanford University

  • How can we accomplish this in practice? How can we guarantee no packet drops, thus no buffer overflow, thus an end-to-end delay guarantee? This is done by having a WFQ router, applying the (σ,ϼ) constraint and a Leaky Bucket Regulator at the source host, where:
    • σ is the size of the token bucket
    • ϼ is the rate at which the token bucket is filled,
    • each queue delivers packets on the wire only if the size of tokens in the token bucket equals the size of the packet.
leaky-bucket-regulator

How the token bucket regulates the transmission of packets – © Stanford University

  • This (σ,ϼ) constraint is implemented in RSVP. This protocol is not used a lot in networking.

So, in addition to providing rate guarantee, WFQ can provide an end-to-end delay guarantee if at the source flows are leaky bucket-constrained.

Leave a Reply

Your email address will not be published. Required fields are marked *

*