RSS
Twitter
Facebook
*Fair queueing
provides equal access to transmission bandwidth.
*Each user flow
has its own logical queue which prevents hogging and allows differential loss
probabilities
*C bits/sec is
allocated equally among non-empty queues.
*The
transmission rate = C / n bits/second, where n is the total number of flows in
the system and C is the transmission bandwidth.
*Fairness: It
protects behaving sources from misbehaving sources.
*Aggregation:
o Per-flow buffers protect flows from
misbehaving flows
o Full aggregation provides no
protection
o Aggregation into classes provided
intermediate protection
*Drop
priorities:
o Drop packets from buffer according to
priorities
o Maximizes network utilization &
application QoS
o
Examples: layered video, policing at network edge.
The above figure illustrates the differences between ideal or fluid flow and packet-by-packet
fair queueing for packets of equal length.
*Idealized
system assumes fluid flow from queues, where the transmission bandwidth is
divided equally among all non-empty buffers.
*The figure
assumes buffer1 and buffer 2 has single L-bit packet to transmit at t=0 and no
subsequent packet arrive.
*Assuming
capacity of C=L bits/second=1 packet/second.
*Fluid-flow
system transmits each packet at a rate of ½ and completes the transmission of
both packets exactly at time=2 seconds.
*Packet-by-packet
fair queueing system transmits the packet from buffer 1 first and then
transmits from buffer 2, so the packet completion times are 1 and 2 seconds.
The
above figure illustrates the differences between ideal or fluid flow and packet-by-packet
fair queueing for packets of variable length.
*
The fluid flow fair queueing is not suitable, when packets have variable lengths.
*
If the different user buffers are serviced one packet at a time in round-robin
fashion, then we do not obtain fair allocation of transmission bandwidth.
*
Finish tag is number used for the packet and the packet with smallest finish
tag will be served first, and finish tag is computed as follows.
*
Finish tag is used as priorities in packet-by-packet system.
Consider
Bit-by-Bit Fair Queueing
*Assume
n flows, n queues
*
1 round = 1 cycle serving all n queues
*
If each queue gets 1 bit per cycle, then 1 round is the number of opportunities
that each buffer has had to transmit a bit.
*
Round number = number of cycles of service that have been completed
*
If packet arrives to idle queue:
Finishing
time = round number + packet size in bits
*
If packet arrives to active queue:
Finishing
time = finishing time of last packet in queue + packet size
Computing
the Finishing Time
*
F(i,k,t) = finish time of kth packet that arrives at time t to flow i
*
P(i,k,t) = size of kth packet that arrives at time t to flow i
*
R(t) = round number at time t
*
Fair Queueing:
F(i,k,t)
= max{F(i,k-1,t), R(t)} + P(i,k,t)
0 comments