- Q:
-
Three input queues, X, Y, and Z.
Their weights are 1, 2, and 1, respectively.
- Packet sizes are identical and equal to 1.
- Packet arrivals are as follows.
- At real time 1, one packet (X1) arrives at queue X and
onen packet (Z1) arrives at queue Z.
- At real time 2, one packet (Y2) arrives at queue Y.
- At real time 3, one packet (X3) arrives at queue X.
- At real time 4, one packet (Z4) arrives at queue Z.
- At real time 5, one packet (Y5) arrives at queue Y.
- Using Weighted Fair Queueing, what are the (logical)
arrival times and the (logical) finish times of these six
packets? Please show your calculations.
- A:
-
First, you must remember that you need to half the packet size of Y, and
whenever queue Y is not empty, you need to count queue Y twice.
- Initially, we have:
| Arrival process (real time): X1, Z1, Y2, X3, Z4, Y5
| | Departure queue: (empty)
| | Active Queues: (none)
|
- At real time 1: X1 and Z1 arrives.
| Arbitrarily set A[X1] = 1 and A[Z1] = 1
| | Calculate F[X1] = 2 and F[Z1] = 2
| |
| | Arrival process (real time): Y2, X3, Z4, Y5
| | Departure queue: (F[X1]=2, F[Z1]=2)
| | Active Queues: (X1, Z1)
| |
| | According to
slide 27 of lecture 15, current point is (1, 1)
| | Slope = 0.5
| |
| | Is next event arrival (Y2) or departure (F[X1] and F[Z1])?
| | Next arrival (Y2) will be (2, 1.5)
| | Next departure (F[X1] and F[Z1]) will be (3, 2)
| | Arrival wins. Next point is (2, 1.5)
|
- At real time 2: Y2 arrives. Current point is (2, 1.5).
| A[Y2] = 1.5
| | Calculate F[Y2] = 2
| |
| | Arrival process (real time): X3, Z4, Y5
| | Departure queue: (F[X1]=2, F[Y2]=2, F[Z1]=2)
| | Active Queues: (X1, Y2, Z1)
| |
| | Slope = 0.25, current point is (2, 1.5)
| |
| | Is next event arrival (X3) or departure (F[X1], F[Y2], and
F[Z1])?
| | Next arrival (X3) will be (3, 1.75)
| | Next departure (at logical time 2) will be (4, 2)
| | Arrival wins. Next point is (3, 1.75)
|
- At real time 3: X3 arrives. Current point is (3, 1.75).
| A[X3] = 1.75
| | Calculate F[X3] = 3
| |
| | Arrival process (real time): Z4, Y5
| | Departure queue: (F[X1]=2, F[Y2]=2, F[Z1]=2, F[X3]=3)
| | Active Queues: (X1|X3, Y2, Z1)
| |
| | Slope = 0.25, current point is (3, 1.75)
| |
| | Is next event arrival (Z4) or departure (F[X1], F[Y2], and
F[Z1])?
| | Next arrival (Z4) will be (4, 2)
| | Next departure (at logical time 2) will be (4, 2)
| | Tie. Next point is (4, 2)
|
- At real time 4: Z4 arrives and X1, Y2, Z1 departs.
Current point is (4, 2).
| A[Z4] = 2
| | Calculate F[Z4] = 3
| |
| | Arrival process (real time): Y5
| | Departure queue: (F[X3]=3, F[Z4]=3)
| | Active Queues: (X3, Z4)
| |
| | Slope = 0.5, current point is (4, 2)
| |
| | Is next event arrival (Y5) or departure (F[X3], and F[Z4])?
| | Next arrival (Y5) will be (5, 2.5)
| | Next departure (at logical time 2) will be (6, 3)
| | Arrival wins. Next point is (5, 2.5)
|
- At real time 5: Y5 arrives. Current point is (5, 2.5).
| A[Y5] = 2.5
| | Calculate F[Y5] = 3
| |
| | Arrival process: (empty)
| | Departure queue: (F[X3]=3, F[Y5]=3, F[Z4]=3)
| | Active Queues: (X3, Y5, Z4)
| |
| | Slope = 0.25, current point is (5, 2.5)
| |
| | Next event can only be departure (F[X3], F[Y5], and F[Z4])?
| | Next departure (at logical time 3) will be (7, 3)
| | Next point is (7, 3)
|
- At real time 7: X3, Y5, and Z4 departs. Current point is (7, 3).
| Arrival process: (empty)
| | Departure queue: (empty)
| | Active Queues: (none)
|
- In summary:
| A[X1]=1 | | F[X1]=2
| | A[Z1]=1 | | F[Z1]=2
| | A[Y2]=1.5 | | F[Y2]=2
| | A[X3]=1.75 | | F[X3]=3
| | A[Z4]=2 | | F[Z4]=3
| | A[Y5]=2.5 | | F[Y5]=3
|
- Sort according to finish times and apply tie breaking rule, the
packet will leave in the following order:
|
