Priority Based Service Discipline for Switched Networks

Priority based Service Discipline for switched Networks

According to the priority based service discipline, the transmission of ready packets are scheduling priority driven manner. Among this, the well-known are Delay Earliest Due-Date (Delay-EDD), weighted fair queuing, jittered EDD and Rate Controlled Static Priority (RCSF).

Weighted Fair Queuing Discipline

It is a packet by packet generalized processor sharing algorithm. It is a type of rate allocating service discipline that provides each flow with at least it’s proportional fair share of link capacity & isolates the timing between flow.

A packet switch may have several inputs feeding to an output link shared by an established flows. Each flow ‘i’ is allocated to all ‘n’ connections is

……………………….

Assume that an acceptance test reject the connection that will cause the requested bandwidth to execute the available bandwidth.

Scheduling Packets:

Assume that the switch is output buffer. The output buffer comprises of two sets of queues.

1. A set of FIFO queues for the connection
2. A priority ordered shortest finish number (SFN) queue.

The finish number fn_i represents the job completion time and the entry in the queue is represented as fn_i, i) where i is the ID of the connection ‘i’. The entry are sorted in order of the finish numbers. When a packet becomes ready on a FIFO queue, its finish number is calculated and the SFN queue is updated. The currently transmitted packet is never preempted, if the finish number fn is of new packet is lower than the current one. When a packet completes transmission, it is removed from the head of FIFO’s and SFN queues. If the FIFO queue is still backlogged then, the SFN queue is updated with the finish number of new ready packet.

Computing Finish Numbers

Let the total bandwidth of backlogged flows be U_b , the finish number of the link is FN, the current time ‘t’ and the previous time instance t_-1 when FN and U_b were updated.

Rules for comparing the first finish number of a link busy interval

R1 For as long as the link is idle, FN = 0, U_b = 0, t_-1 = 0, and finish number connection i, for every i = 1, 2, … , n is 0.

R2 When the first packet of length e arrives and starts a busy intervals of the link,

1. Set t_-1 = t; and
2. The packet being a connection-i packet, increment U_b by u’, complete fni = fn_i^- + e/u_i’, and insert the entry (fn_i, i) in the SFN queue.

Rules for comparing subsequent finish numbers during a link busy interval

R1 for every i, when a connection-i packet arrives at t during a link busy interval, if connection i was idle prior to this arrival,

1. Increment FN by (t – t_-1)/U_b, computer fn_i = max(FN, Fn_i) + e/u_i’, and insert the entry (fn_i, i) in the SFN queue, and
2. Set t_-1 = t and decrement U_b by u_i’.

R2 for every I, when the transmission of a connection-i packet completes,

1. If the connection remains backlogged, increment fn_i by e/u_i’, where e is the length of the new ready connection-i packet, and insert the entry (fn_i, i) in the SFN queue;
2. If connection i becomes idle,

• increment the link number FN by (t – t_-1)/U_b; and
• Set t_-1 = t, and decrement U_b by u_i’.

Weighted Round Robin Service Discipline

In a round-robin scheduling, the jobs are placed in a FIFO queue. The job at the head of the queue executes for one time slice if it does not complete within the time slice. If it does not complete within a time slice, it is preempted and put at the back of the queue. If there are n jobs in the queue, then each job gets on slice every n time slots.

But in the weighed round robin scheduling, each job gets a weight wt_i. A job with the weight wt_i executes for wt_i time slices each round robin and the length of the round is equal to

………………….

One of the most widely used WRR service discipline is called Greedy WRR. In this discipline during connection establishment, the scheduler at each switch assigns to the new connection i a weight of wt_i.

It means that connection i is allocated wt_i slots in each round during which message packets on all existing connections sharing the same output link are transmitted in turn.

Throughput and Delay guarantees

Consider a constant bit rate periodic message Mi = (pi, ei, Di) where pi is minimum interarrival time of the message, ei is size of each message and Di is maximum acceptable end to end delay.

On each round if more than wt_i packets are backlogged on the queue i, then wti packets are transmitted and each flow is guaranteed wt_i slots each round. But if the scheduling is rate allocating type, then more that wt_i packets can be send if there is nothing else to transmit. A designed parameter in greedy WRR is the maximum number of slots per round denoted by RL called round length. At all times, the sum of weights of all n connections on the output link is no greater than RL, i.e.

…….

It means each flow is guaranteed a throughput rate wt_i/RL of the link capacity provide that RL< p_min (where, p_min is the minimum pi of all the i’s) and wt_i ≥ [ei/(pi/RL)] i.e. wt_i ≥ (e_i RL)/p_i

The messages take at most (e_i/wt_i) * RL. At each subsequent switch round of packets arriving is sent in the next round. It means, one round delay is introduced at each hop. Therefore, the end to end delay for connection i with message size ei and assigned weight wt_i passing through r switches is bounded by

W_i ≤ e_i/wt_i + r-1)RL ≤ p_i + (r-1)RL

Connection Establishment

The weights of all connection on an output link depends on the length and a change of round length may require the changes of the weights. It is too costly to change the round length each time a row flow is established because it will require the adjustment of weights for all preexisting flows. Therefore, a fixed length round RL is used.

1. At each hop, the scheduler computes the weight wt_i required to support the new flow.
2. If the sum of existing weight is less than RL – wt_i, then the flow is accepted at that hop.

In WRR scheduling, the flows get guaranteed capacity and it is efficient to implement but it is unsuitable for scheduling precedence constraint jobs and the end to end delay can be bounded. Similarly, since the scheduler is rate allocating, the jitter is not controlled but can be bounded, it is suitable for scheduling message transmission through switches and for pipelined jobs. It does not require globally synchronized clocks and the sorted queue. It is most suitable constant bit rate message.

References

Liu, J. W. (2003). Real Time System. Pearson Education, Inc. and Doring Kindersley Publishing Inc.