Lab2-GPS Scheduling in Java - Solution

Total points: 10


Warning: Students are members of a learning community committed to the search for knowledge and truth. Essential to that search is the faithful adherence by all students to the highest standards of honesty and integrity. A grade of “0” or “F” will be assigned to assignments on which cheating, plagiarism or any other form of academic dishonesty is committed or determined to have occurred. Using source code for your assignments from anywhere is considered plagiarism/cheating and is therefore prohibited. For details, see Wright State University Student Handbook under “Academic Dishonesty”.


You must not attempt to get help from external sources such as online sites that offer solutions. Any submission for grading must be your own work. You must not copy from others or allow your work to be copied. We will check for similarities of code. Any violation will result in your receiving zero for this assignment. No exception.


This project needs to be completed using Java and is an individual project. Naming of your programs must strictly follow the following convention: (1) one file for each part; (2) Lab2 followed by your Uid and I for part I (for example Lab2U00998499I.java). Upload only your source code (one file for each part) to the Pilot dropbox.


In class lectures, we discussed the packet scheduling algorithm – Generalized Processor Sharing (GPS). GPS cannot be directly applied in a real network for ordering packets for transmission because it assumes a fluid packet/traffic model. Real-world packets consist of bits/bytes, and they must be transmitted atomically, i.e., a packet must be transmitted as a single entity. Packet-by-packet GPS approximates the GPS scheduler closely using a virtual time-based implementation. Refer to the paper for details on GPS/PGPS: Abhay K. Parekh and Robert Gallager, ``A generalized processor sharing approach to flow control in integrated services networks: the single node case,'' IEEE/ACM Trans. on Networking, Vol. 1, No. 3, pages 344--357, June 1993.


A good object-oriented programming style for this lab is a consideration in grading. Therefore, you should design and implement your solutions carefully. Code must be commented. Your report must adequately describe your implementation. Test cases will exercise your programs thoroughly. Therefore, your programs should efficiently handle potentially large problems.


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.

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 backlogge