- 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
- 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)
- 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.
- 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.