Home / Networking Basics / A Simple Deterministic Queueing Model

# A Simple Deterministic Queueing Model

Contents

Queues can be studied with a simple deterministic model. A Deterministic queueing model helps to learn about the dynamics of a packet in a network. This model defines these functions:

A(t):  the cumulative number of bits (or bytes) that arrived at instant “t”. It’s the arrival rate.

D(t): the cumulative number of bits (or bytes) that departed from the queue, at instant “t”. It’s the departure rate.

Q(t): the cumulative number of bits or bytes in a queue, at instant “t”. Q(t) is also called the occupancy of the queue.

d(t): the time spent by a bit (or a byte) in the queue. It’s the queueing delay of one bit

Q(t) = A(t) – D(t)

– Sending smaller packets instead of big ones helps reduce end-to-end delay, because with smaller packets we can send many consecutively (pipelining)

– when sending a packet of size M over i links with rates ri and length Li (and queueing delays are null) the end-to-end delay is the sum of the propagation delays and the packetization delays

end-to-end delay = sum(M/ri + Li/c)

– suppose the packet is divided into smaller chunks of size p. The end-to-end delay becomes the sum of the propagation delays and the packetization delays of the first small packet, plus the packetization delay of the remaining small packets

end-to-end delay= sum (p/ri + Li/c) + (M-p)/rmin,

where rmin is the rate of the slowest link

– Statistical multiplexing helps reduce the rate of the egress link:

suppose we have N ingress flows at C rate each, and the egress link is at C rate also. Without statistical multiplexing, N*C > C, which means if all ingress flows arrive at full capacity, there will be packet loss at the egress interface. Even if we have a buffer, there still are lost packets because the size of the buffer is finite.

→ However, with statistical multiplexing, the egress rate R is smaller than N*C, with the following assumptions:

• the ingress average rate is sufficiently low
• the ingress rates are bursty

The reduction of the egress rate compared to the initial N*C rate is called Statistical Multiplexing Gain and this definition is true for systems with or without buffers

Adsense black background: