Part I. Packet-by-packet GPS (PGPS)
Your task in Part I is to implement the virtual-time based PGPS scheduling algorithm. In the lecture, we
explained that the virtual time advance rate is variable, depending on the flows that are backlogged in
virtual time.
In a PGPS scheduler, an arriving packet at time t (real time), arrives at a virtual time VT(t) where VT(t) is
a virtual time function that maps real time t to its corresponding virtual time. The scheduler then
calculates the virtual start time and virtual finish time of the packet using formula (11) on page 348 of
the paper.
The packet is stamped with the virtual finish time (i.e., the packet carries the virtual finish time). Packets
are ordered in increasing order of the virtual finish time in the packet queue, waiting to be transmitted.
When the PGPS scheduler chooses the next packet to transmit at time t, it selects among all the packets
that are queued at t, the first packet that has the minimum virtual finish time.
 
Part II. Worst-case Fair Fair Queuing (WF2Q)
Part II of this lab builds on Part I. You should make sure that your Part I works correctly first.
In a WF2Q scheduler, when the link chooses the next packet at time t to transmit, it selects only from
the packets queued that have started receiving service in the corresponding GPS scheduler at t, and
furthermore chooses the packet among them that would complete service first in the corresponding
GPS (i.e., with the smallest virtual finish time). Note that different from the PGPS scheduler, the WF2Q
scheduler considers only those eligible packets and then chooses the packet with the minimum virtual
finish time to transmit next.
Add/modify the code of Part I to implement the WF2Q scheduler. Submit the implementation as a
separate Java file.
INPUT FORMAT (file flows.txt):
The format is the same as Part I.
OUTPUT FORMAT (file flowout.txt):
The format is the same as Part I.
SAMPLE INPUT:
The same sample input as Part I
SAMPLE OUTPUT:
nFlows = 6
nPackets = 13
Packet arrTime 0.0 flow id 1 w 0.5 packet length 1.0
Packet arrTime 0.0 flow id 2 w 0.1 packet length 1.0
Packet arrTime 0.0 flow id 3 w 0.1 packet length 1.0
Packet arrTime 0.0 flow id 4 w 0.1 packet length 1.0
Packet arrTime 0.0 flow id 5 w 0.1 packet length 1.0
Packet arrTime 0.0 flow id 6 w 0.1 packet length 1.0
Packet arrTime 1.0 flow id 1 w 0.5 packet length 1.0
Packet arrTime 2.0 flow id 1 w 0.5 packet length 1.0
Packet arrTime 3.0 flow id 1 w 0.5 packet length 1.0
Packet arrTime 4.0 flow id 1 w 0.5 packet length 1.0
Packet arrTime 5.0 flow id 1 w 0.5 packet length 1.0
Packet arrTime 6.0 flow id 1 w 0.5 packet length 1.0
Packet arrTime 7.0 flow id 1 w 0.5 packet length 1.0
Event{type=pgpsDeparture, t=1.0, p=Packet{flowId=1, arrTime=0.0, length=1.0, virtualStarTime=0.0,
virtualFinishTime=2.0}}
Event{type=pgpsDeparture, t=2.0, p=Packet{flowId=3, arrTime=0.0, length=1.0, virtualStarTime=0.0,
virtualFinishTime=10.0}}
Event{type=pgpsDeparture, t=3.0, p=Packet{flowId=1, arrTime=1.0, length=1.0, virtualStarTime=2.0,
virtualFinishTime=4.0}}
Event{type=pgpsDeparture, t=4.0, p=Packet{flowId=4, arrTime=0.0, length=1.0, virtualStarTime=0.0,
virtualFinishTime=10.0}}
Event{type=pgpsDeparture, t=5.0, p=Packet{flowId=1, arrTime=2.0, length=1.0, virtualStarTime=4.0,
virtualFinishTime=6.0}}
Event{type=pgpsDeparture, t=6.0, p=Packet{flowId=2, arrTime=0.0, length=1.0, virtualStarTime=0.0,
virtualFinishTime=10.0}}
Event{type=pgpsDeparture, t=7.0, p=Packet{flowId=1, arrTime=3.0, length=1.0, virtualStarTime=6.0,
virtualFinishTime=8.0}}
Event{type=pgpsDeparture, t=8.0, p=Packet{flowId=5, arrTime=0.0, length=1.0, virtualStarTime=0.0,
virtualFinishTime=10.0}}
Event{type=pgpsDeparture, t=9.0, p=Packet{flowId=6, arrTime=0.0, length=1.0, virtualStarTime=0.0,
virtualFinishTime=10.0}}
Event{type=pgpsDeparture, t=10.0, p=Packet{flowId=1, arrTime=4.0, length=1.0, virtualStarTime=8.0,
virtualFinishTime=10.0}}
Event{type=pgpsDeparture, t=11.0, p=Packet{flowId=1, arrTime=5.0, length=1.0, virtualStarTime=10.0,
virtualFinishTime=12.0}}
Event{type=pgpsDeparture, t=12.0, p=Packet{flowId=1, arrTime=6.0, length=1.0, virtualStarTime=12.0,
virtualFinishTime=14.0}}
Event{type=pgpsDeparture, t=13.0, p=Packet{flowId=1, arrTime=7.0, length=1.0, virtualStarTime=14.0,
virtualFinishTime=16.0}}