When a token arrives at the token bucket, it will add a token into the token bucket

INSTRUCTIONS TO CANDIDATES

ANSWER ALL QUESTIONS

This spec is private (i.e., only for students who took or are taking CSCI 402 at USC). You do not have permissions to display this spec at a public place (such as a public bitbucket/github). You also do not have permissions to display the code you write to implementation this spec at a public place since your code was written to implement a private spec. (If a prospective employer asks you to post your code, please tell them that you do not have permissions to do so; but you can send them a private copy.)

 

To download the spec below in one command (so you can make a backup of the spec in case the class web server is not available due to network or server problem), do the following inside a terminal in Ubuntu 16.04 (preferable in an empty directory) to make a quick and dirty (may be incomplete) backup of our spec:

 

wget -r -l 1 --user=USERID --password=PASSWORD \

http://merlot.usc.edu/cs402-s23/projects/warmup2/index.html

 

where USERID and PASSWORD are the user ID and password used to access protected content from our class web site. Then type the following in the terminal:

firefox merlot.usc.edu/cs402-s23/projects/warmup2/index.html

 

Please remember that I do update the spec occasionally. You should ONLY look at your backup copy when the class web site is unavailable.

 

Assignment Description

(Please check out the Warmup 2 FAQ before sending your questions to the TAs, the course producers, or the instructor.)

 

In this assignment, you will emulate/simulate a traffic shaper that transmits/services packets controlled by a token bucket filter depicted below using multi-threading within a single process. If you are not familiar with pthreads, you should read Chapter 2 of our required textbook.

 

IMPORTANT: Please note that this assignment is posted before all the background materials (e.g., Unix signals) have been covered in lectures. If you do not want to learn about these components on your own (by learning from the textbook), please delay starting this project until they are covered in class. There will be plenty of time to implement this project after the relevant topics are covered in class. If you don't want to wait and don't want to learn about Unix signals and stuff on your own, I would strongly recommend that you do this assignment in two steps. First, you write your code to do the emulation without any <Ctrl+C>-handling code. By the time you get this part to work perfectly,

 

we would have covered everything you need to finish the assignment. Then you follow the recommendations in the lecture to add <Ctrl+C>-handling code.

Figure 1: A system with a token bucket filter.

Figure 1 above depicts the system you are required to emulate. The token bucket has a capacity (bucket depth) of B tokens. Tokens arrive into the token bucket according to an unusual arrival process where the inter-token-arrival time between two consecutive tokens is 1/r. We will call r the token arrival rate (although technically speaking, it's not exactly the token arrival rate; please understand that this is quite different from saying that the tokens arrive at a constant rate of r). Extra tokens (overflow) would simply disappear if the token bucket is full. A token bucket, together with its control mechanism, is referred to as a token bucket filter.

 

Packets arrive at the token bucket filter according to an unusual arrival process where the inter-arrival time between two consecutive packets is 1/lambda. We will call lambda the packet arrival rate (although technically speaking, it's not exactly the packet arrival rate; please understand that this is quite different from saying that the packets arrive at a constant rate of lambda). Each packet requires P tokens in order for it to be eligiable for transmission. (Packets that are eligiable for transmission are queued at the Q2 facility.) When a packet arrives, if Q1 is not empty, it will just get queued onto the Q1 facility. (Please note that, in this case, you do not have to check if there is enough tokens in the bucket so you can move the packet at the head of Q1 into Q2 and you need to understand why you do not need to perform such a check.) Otherwise, it will check if the token bucket has P or more tokens in it. If the token bucket has P or more tokens in it, P tokens will be removed from the token bucket and the packet will join the Q2 facility (technically speaking, you are required to first add the packet to Q1 and timestamp the packet, remove the P tokents from the token bucket and the packet from Q1 and timestamp the packet, before moving the packet into Q2), and wake up the servers in case they are sleeping. If the token bucket does not have enough tokens, the packet gets queued into the Q1 facility. Finally, if the number of tokens required by a packet is larger than the bucket depth, the packet must be dropped (otherwise, it will block all other packets that follow it).

 

The transmission facility (denoted as S1 and S2 in the above figure and they are referred to as the

"servers") serves packets in Q2 in the first-come-first-served order and at a transmission/service rate of mu per second. When a server becomes available, it will dequeue the first packet from Q2 and start transmitting/servicing the packet. When a packet has received 1/mu seconds of service, it leaves the system. You are required to keep the servers as busy as possible.

 

When a token arrives at the token bucket, it will add a token into the token bucket. If the bucket is already full, the token will be lost. It will then check to see if Q1 is empty. If Q1 is not empty, it will see if there is enough tokens to make the packet at the head of Q1 be eligiable for transmission (packets in Q1 in also served in the first-come-first-served order). If it does, it will remove the corresponding number of tokens from the token bucket, remove that packet from Q1 and move it into Q2, and wake

 

up the servers in case they are sleeping. It will then check the packet that is now at the head of Q1 to see if it's also eligiable for transmission, and so on.

 

Technically speaking, the "servers" are not part of the "token bucket filter". Nevertheless, it's part of this assignment to emulation/simulation the severs because the servers are considered part of the "system" to be emulated. (For the purpose of this spec, we will use the term "emulation" and "simulation" interchangeably.)

 

Our system can run in only one of two modes.

 

Deterministic : In this mode, all inter-arrival times are equal to 1/lambda seconds and all service times are equal to 1/mu seconds (both these values must be rounded to the nearest millisecond), and all packets require exactly P tokens. If 1/lambda is greater than 10 seconds, please use an inter-arrival time of 10 seconds. If 1/mu is greater than 10 seconds, please use an service time of 10 seconds.

 

Trace-driven : In this mode, we will drive the emulation using a trace specification file (will be referred to as a "tsfile"). Each line in the trace file specifies the inter-arrival time of a packet, the number of tokens it need in order for it to be eligiable for transmission, and its service time. (Please note that in this mode, it's perfectly fine if an inter-arrival time or a service time is greater than 10 seconds.) If you are running in the trace-drive mode, you must not validate or read the entire tsfile before you start your simulation.

 

In either mode, if 1/r is greater than 10 seconds, please use an inter-token-arrival time of 10 seconds. Otherwise, please round the inter-token-arrival time to the nearest millisecond.

 

Your job is to emulate the packet and token arrivals, the operation of the token bucket filter, the first- come-first-served queues Q1 and Q2, and servers S1 and S2. You also must produce a trace of your emulation for every important event occurred in your emulation. Please see more details below for the requirements.

 

 

Attachments:

Related Questions

. Introgramming & Unix Fall 2018, CRN 44882, Oakland University Homework Assignment 6 - Using Arrays and Functions in C

DescriptionIn this final assignment, the students will demonstrate their ability to apply two ma

. The standard path finding involves finding the (shortest) path from an origin to a destination, typically on a map. This is an

Path finding involves finding a path from A to B. Typically we want the path to have certain properties,such as being the shortest or to avoid going t

. Develop a program to emulate a purchase transaction at a retail store. This program will have two classes, a LineItem class and a Transaction class. The LineItem class will represent an individual

Develop a program to emulate a purchase transaction at a retail store. Thisprogram will have two classes, a LineItem class and a Transaction class. Th

. SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 1 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of

. Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of