Information

Author(s) Bonaventure Olivier
Deadline Geen deadline
Submission limit No limitation

Sign in

Deficit round-robin scheduling

The deficit round-robin scheduler servers packets in the different queues according to a fixed cyclic schedule. For this exercise, we assume that the schedule is Q1, Q2, Q1, Q2, ...

The scheduler is attached to a 1 Mbps link. All incoming flows also arrive on 1 Mbps links.

The packets that arrive in queue Q1 are represented using upper case letters. The packets that arrived in Q2 are represented using lower case letters. A dot (.) in the incoming traffic pattern corresponds to a period of one millisecond without any incoming packet. For this exercise, we assume that Q1 sends 2000 bits long packets while the other queues send 1000 bits long packets.


Question 1: Incoming traffic pattern

Queue Q1 receives the following packets (A is the first received packet) :

  • JIHGFEDCBA

Queue Q2 receives the following packets (a is the first received packet) :

  • jihgfedcba

Assuming the Q1-Q2 schedule, what are the first ten packets sent on the output link ?

Question 2: incoming traffic pattern

Queue Q1 receives the following packets (A is the first received packet) :

  • JIHGFEDCBA

Queue Q2 receives the following packets (a is the first received packet) :

  • edcba.....

Assuming the Q1-Q2 schedule, what are the first ten packets sent on the output link ?

Question 3: Incoming traffic pattern

Queue Q1 receives the following packets (A is the first received packet) :

  • .E.D.C.B.A

Queue Q2 receives the following packets (a is the first received packet) :

  • ..e..d..c..b..a

Assuming the Q1-Q2 schedule, what are the first ten packets sent on the output link ?

Question 4: Incoming traffic pattern

Queue Q1 receives the following packets (A is the first received packet) :

  • D..C..B..A

Queue Q2 receives the following packets (a is the first received packet) :

  • ..e..d..c..b..a

Assuming the Q1-Q2 schedule, what are the first ten packets sent on the output link ?