Computer Science 308-435B

Basics of Computer Networks

McGill University, Winter 2001

Assignment 3: Petri Net modelling, coding, and performance analysis of a stop-and-wait ARQ protocol

Due date

UPDATE: deadline moved to Wednesday 28 March, before 23:59 (hard deadline).

Submission medium



The deliverable for this assignment consists of a number of files, all to be submitted via VisualCM:

  1. One HTML file index.html. The document discusses your results, with inline GIF images of your Petri Net as well as of your performance plots. It also includes links to all your result files (.net Petri Net model, .c protocol code, .txt tables with performance data). Make the HTML file as simple as possible (no special effects). There should be no references to files other than those submitted through VisualCM. All files should be in the same directory. At the very top of the HTML file, include your first name, last name, and student ID.
  2. A link to a PNS model file ( as well as an inline GIF image of the PNS model.

    The above example is the starting point. The model needs to be modified to:

    1. model the sender and receiver Network Layer. Set up the model such that there are initially 10 packets waiting to be sent in the sender's Network Layer. Initially, 0 packets have been received in the receiver's Network Layer.
    2. count the total number of frames (of any kind: DATA, ACK, NAK) lost.
    3. use negative acknowledgements (NAK), explicitly modelling the arrival of damaged frames (rather than treating them as lost).
    4. ignore duplicate ACKs (rather than re-sending data).

    Simulating your model long enough (in Sequential Random mode) should eventually leave 0 packets (tokens) in the sender's Network Layer and 10 in the receiver's Network Layer. In your report, mention the number of tokens lost during this process (this is a measure of the efficiency of the protocol).
  3. Modify Tanenbaum's (well, HV's version of) p3.c protocol code to reflect your Petri Net model. Obviously, submit and include a link to your p3.c. Note how there is no provision for a NAK in Tanenbaum's simulator. Explain how you solved this (without modifying the simulator). All files needed to run Tanenbaum's simulator are here.
    UPDATE: Tanenbaum's simulator CAN be made to support NAKs (s.kind=nak) if
           case 3:
            s->kind = (id == 0 ? data : ack);
            if (s->kind == ack) {
    in worker.c is replaced by
           case 3:
            /* s->kind = (id == 0 ? data : ack); */
            if ((s->kind == ack) || (s->kind == nak)) {
    Note how you must now explicitly set the "kind" field when sending frames (as the simulator won't magically do it for you any more) in p3.c !! If this is not done, the simulator will be highly confused.
    You can still choose not to make this change to worker.c and rather "encode" the NAK in some other way.
    To summarize, there are two possible solutions:
    1. Use the original worker.c/p3.c (no longer on the web) which automagically sets the "kind" field. Your modified p3.c must "encode" NAKs.
    2. Use the latest worker.c/p3.c (currently on the web) as the basis of your improvements. Your modified p3.c can now use NAKs.
    These are the only two meaningful combinations. Mention EXPLICITLY which of the two you used in your solution !
  4. Using Tanenbaum's protocol simulator, do a performance analysis:
    1. Timeout 100; 20% packet loss; 0% to 70% checksum errors in increments of 10%.
    2. Timeout 100; 0% to 70% packet loss in increments of 10%; 20% checksum errors.
    Plot efficiency in function of the varying parameter. In one plot, both the efficiency of the original stop-and-wait-ARQ protocol and of your modified version should be shown.
    All of the above for at least 10000 time-ticks (more will make the statistics more relevant).
    Include a link to a data file of parameters and efficiencies as well as an inline GIF image of a plot for both above analyses. Discuss your results.


Check the Class Transparencies page to find more information about PNS.

Hans Vangheluwe