CS516 Assignment 5

Due: In Class
November 18, 1999
Weight: 15% of final mark

Write a program, in any programming language on UNIX, which simulates a token ring similar to that specified in IEEE Standard 802.5. You should write your program so that it is flexible, allowing system parameters and even functional behavior of the protocol to be changed easily.

Specifications:

• The ring is to consist of an arbitrary number of stations connected by unidirectional 4 million bps links. The number of stations is specified in the input file, which is further described below.
• Each link has a propagation delay of 0.25 usec.
• Each station buffers a single byte (eight bits).
• No station, link, or transmission errors occur and you need not simulate anything that has to do with the monitor station.
• The token consists of three bytes: SD, AC, and ED. The start and end delimiters (SD and ED) have constant values. The AC byte encodes the following quantities: a token/frame bit, a three bit priority, and a three-bit reservation priority.
• The frame consists of the components [SD, AC, DA, SA, DATA, ED, FS], in that order. The fields SD, AC, and ED are as in the token. The fields DA and SA are each two bytes and represent the destination and source address. The DATA field is the actual data; it will be no longer than 2048 bytes. The frame status byte (FS) encodes two one-bit quantities: whether the destination address recognized the frame and whether the frame was copied to the destination. A station can transmit no more than one frame before giving up the token (i.e., the token holding time is not used).
• You are to implement two priority schemes: a single priority scheme and the eight-level priority scheme described in Section 13.2 (pp. 416-418 in DCC). Your program should by default use the eight-level priority scheme. A command line flag of "-sp" should run using a single priority.
• Assume that, when a station transmits a frame, it waits for the last bit of the frame to return before transmitting the first bit of a token.
• You may assume that the minimum number of stations in the ring is 3. This guarantees that the token will fit on the ring and you do not need to simulate delays for rings with fewer stations.
• The specification of frames to be transmitted is read from an input file. The first (non-comment) line consists of a single integer that represents the number of stations. Each remaining line consists of a sequence of five integers, separated by spaces:

       time  source destination length priority

  where time is the time (in units of 0.25 usec) at which the frame arrives at the station for transmission, source is the source address, destination is the destination address, length is the message length, and priority is the message priority. You may assume that the input is ordered by arrival time. The input may include comment lines; any line beginning with "#" is to be ignored by the program.
• Assume that at time 0, the first bit of the token begins to leave station 0 for station 1. Also assume that if a frame arrives for transmission at the same time or after the first bit of the token begins to arrive at a station, nothing can be done with the frame until the next time a token arrives. That is, the frame must arrive for transmission strictly before the token arrives.
• At the conclusion of the simulation your program should print the average elapsed transmission time for frames at each priority and overall. In the output, you should indicate whether the single or multiple priority scheme was used. (The transmission time is the elapsed time between the arrival of a frame at the source station and the arrival of the last bit in the FS byte at the destination station.)

  Also, if a -t flag occurs on the command line, print detailed trace information, including the time of each of the following events: the arrival of a frame at the source, the transmission of a frame, raising or lowering priority, and receiving a frame at the destination. These events must be printed in an ascending order of time. (Do not print sending or receiving times for every token.)

  All times should be reported in multiples of 0.25 usec.

Hints:

Your simulation must accurately determine transmission times, but you should avoid simulating irrelevant details. In particular, the bit patterns of various control and data bytes are not relevant--you need to know how many such bytes there are, but you can simply maintain a data structure for each frame which stores all the needed information in a form convenient to your program. Similarly, you need not simulate the bit-by-bit movement of the token or frame, but rather compute when it will arrive at a place where something significant will happen.

I suggest you maintain a list of events, sorted in ascending order of time. The list will initially contain the arrival times of frames to be transmitted, read from the input file. Successive events are removed from the list and processed. During processing, future events may be generated; the exact time of each future event is calculated and the event is inserted into the list in its proper place.

Other useful hints are:

• the propogation delay should not be applied to every bit in a message - only the first bit should experience the delay.
• the token is not actually removed from the ring by the station wishing to send. The SD and AC byte of the token and frame are the same, so the station simply should flip the token/frame id bit in the AC field when it grabs the token.
• the station delay is 8 bits or 8 time units per station.
• the stacking station is responsible for lowering the priority of a token to its original level if the priority of a waiting message is lower than the priority of the ring.

Make sure to state assumptions, if you are making any other than those specified above, for this assignment.

Submissions:

You should hand in a similar documentation as you have done for ASN3 (i.e., an external documentation describing how the program was implemented, the source listing and test outputs with the -t flag off). We will shortly provide the test cases you must use for submission.

In order for the TA to verify your program, please do the following:

• Put the source code for your program in a directory named Ring directly under your home directory in HEMOS.
• The directory Ring should contain the (well documented) source code for your program. In addition, it should include a Makefile that creates an executable named ring.
• Under the directory Ring should be a directory named Test. This directory should include the input files you used to test your program, a script file for each test (so that the TA can simply execute each) and the output for each test. If the input file is named file, the output should be named either file.sp or file.mp, depending on whether the single or multiple priority scheme was used.
• Add the TAs' HEMOS usernames in the ACL of your assignment directories (Ring and Ring\Test):
  % fs sa . shryu all
% fs sa . mine all
• The hand-in time of your assignment depends not only on the documentation you hand in, but the last-modified time of the files in your Ring directory, so do not touch the files in your Ring directory after the time you consider your assignment to be "handed in".

Marking Scheme:

This assignment is worth a total of 15% of the final mark. Documentation is worth 5%. The remaining 10% will be awarded roughly as follows:

• for no program or a program that demonstrates little effort: 0 points,
• for a program that shows considerable effort but doesn't work: 3 points,
• for a program that implements the single-priority scheme correctly, but doesn't work at all on the multiple-priority scheme: 6 points,
• for a program that implements both the single and multiple priority schemes correctly: 8 points, and
• for a program that works correctly, is neat, logically structured, easy to understand, and has been well tested: 10 points.

So, get the single-priority scheme working first, then add the multiple priority scheme. Neatness and understandability count. Good-luck!