top of page

Lab 2 GPS Packet Scheduling - Part I. Packet-by-packet GPS (PGPS) Java Solution

Updated: Sep 17, 2023

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.

For the virtual time-based implementation to work, we need to keep track of the virtual time function VT(t). This is accomplished by noting that the set of backlogged flows does not change between two consecutive events. An event is a packet arrival, or a packet departure. There are two kinds of packet departure events: (1) packet departure in the PGPS scheduler (in real time) when a packet is transmitted; (2) packet departure in virtual time (we need to know when packets depart in virtual time to track the set of backlogged flows). A flow is considered backlogged if it has a packet to transmit in virtual time. The packet arrival event and the second type of departure event may change the set of backlogged flows and therefore impact the virtual time advancement rate.


Notice that there is no event (no arrivals and departures) between two consecutive events, and the set of backlogged flows will remain constant between 2 consecutive events. Let Bj be the set of backlogged flows during the (real time) interval (tj-1, tj). We will call the interval (tj-1, tj) the jth event interval. There is a one-to-one correspondence between the real time clock value and the virtual clock time value, but the correspondence is rather complicated. The real time is denoted by t and the virtual time that corresponds to the real time t is denoted by VT(t). The time keeping is done as follows. The real time clock starts running when the first packet of a busy period arrives, i.e.: t1 = 0. This makes sense. Before the first packet arrival, the link is idle, and we do not to do any time keeping exercise. When the first packet of a busy period arrives, the virtual time clock also starts running: VT(0) = 0. So, the real time clock and the virtual time clock begin to run when the first packet of a busy period arrives. The virtual time changes with a constant rate within each event interval (tj-1, tj) in which Bj remains unchanged. The virtual time may advance with different rates in different event intervals. The virtual time advances in the jth event interval using formula (10) on page 348 of the paper.


Also note one more time that the set B of backlogged flows may change when a flow goes from idle to active when a packet of that flow arrives (in real time) or goes from being backlogged to idle in virtual time. However, we need to update the set B in real time. This is a challenge when a flow becomes idle because we need to map the virtual time (when the flow become idle) back to the real time at which time we can then update the set B. Fortunately, we can map the virtual time when a packet departs to its corresponding real time given the packet’s virtual finish time. This is the time when B may change because a flow may become not backlogged when the last packet departs from the flow. Mapping from the virtual finish time of a packet to real time given a minimum virtual finish time Fmin of the packet that departs can be done using the formula that calculates Next(t) given on page 348 of the paper. At Next(t) the set B may be adjusted to remove the flow that is no longer backlogged.


Suggestions of implementation: as described above, we see that the PGPS scheduler must process events: packet arrivals, packet departures. This immediately suggests event-driven based implementation. You can define various classes, such as Packet, Flow, Event etc.

INPUT FORMAT (file flows.txt):

The first line of input contains an integer N (i.e., N flows of packets). The next N lines each contain the GPS weight for each flow. These are then followed by a line of input that contains an integer M (i.e., the number of packets that will arrive from the N flows). Each of the next M lines contains three numbers: time of packet arrival, flow id, and packet length. The packet length has been normalized by link transmission rate.

OUTPUT FORMAT (file flowout.txt):

Output the order of packet transmission using the PGPS scheduler. The specific format is shown in the sample output below.

SAMPLE INPUT:

6

0.5

0.1

0.1

0.1

0.1

0.1

13

0 1 1

0 2 1

0 3 1

0 4 1

0 5 1

0 6 1

1 1 1

2 1 1

3 1 1

4 1 1

5 1 1

6 1 1

7 1 1

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=1, arrTime=1.0, length=1.0, virtualStarTime=2.0, virtualFinishTime=4.0}}

Event{type=pgpsDeparture, t=3.0, p=Packet{flowId=1, arrTime=2.0, length=1.0, virtualStarTime=4.0, virtualFinishTime=6.0}}

Event{type=pgpsDeparture, t=4.0, p=Packet{flowId=1, arrTime=3.0, length=1.0, virtualStarTime=6.0, virtualFinishTime=8.0}}

Event{type=pgpsDeparture, t=5.0, p=Packet{flowId=4, arrTime=0.0, length=1.0, virtualStarTime=0.0, virtualFinishTime=10.0}}

Event{type=pgpsDeparture, t=6.0, p=Packet{flowId=1, arrTime=4.0, length=1.0, virtualStarTime=8.0, virtualFinishTime=10.0}}

Event{type=pgpsDeparture, t=7.0, p=Packet{flowId=3, arrTime=0.0, length=1.0, virtualStarTime=0.0, virtualFinishTime=10.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=2, arrTime=0.0, length=1.0, virtualStarTime=0.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}}

In the example above, a line that starts with “Event” gives the transmission of one packet at time t, p indicates the packet being transmitted.


For 100% Accurate and Plagiarism free Solution:

Please txt at WhatsApp Number : +91-995 314 1035


Solution Includes: AI writing Detection and Plagiarism report with 100% Accuracy.



27 views0 comments

Comments


bottom of page