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

(σ,ϼ)-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)

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.

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 *