Tutorial On Event Driven Simulations of Network Protocols
Lecture Notes on Selective Repeat
Written by Tom Laramee, Dec. 1995

Written by Tom Laramee for use in the senior level ECE course in Computer Networks 597A, and for use in the graduate-level course ECE671.

Here are the lecture notes I gave out when presenting the simulation of the protocol Selective Repeat. These notes detail the various events involved in the simulation of this protocol, how they are generated, and how they are processed.

[ Tutorial Index | Lecture Notes | Skeleton Simulation Code | Media Access Simulation Code | Data Link Layer Simulation Code ]
How do we expect the simulation to behave?
Here are a couple of scenarios to get an intuitive feel for what is going to happen during the simulation. They focus on 2 critical parameters:
  • W = Window size (in frames)
  • l = Channel length (in frames)

When the channel length is 5, but the window size is only 1 (case 1), the sender may never have more than 1 packet outstanding at any given time. Therefore, most of the time is spent witing for ACKs from the receiver while channel bandwidth is wasted (free bandwidth goes unused).

When the channel length is 5, and W=3 (case 2), the utilization is better -- except time is still wasted because the sender hits the window size before receiving an ACK for it's 1st packet.

So, when channel length is 5, and W=5 (case 3), there is never a time when the sender is idle. Therefore, maximum efficiency is attained here with no channel bandwidth going unused.

Now, in case 1 above, the Window size (W) is help constant and the channel length is varied. It can be seen that the longer the channel length, the lower the efficiency acheived. This is the same picture as in the previous figure, except here we're holding W fixed and varying l (channel length).

Events: Types, generating them, and handling them (processing).

These are the various functions which are directly related to the simulation of the Selective Repeat protocol.

Event Type Function the generates event Function that processes event
FrameArrival gen_arrival processFrameArrvial
Departure gen_depart processDeparture
NodeFree gen_nodefree processNodeFree
AckArrival gen_ackarrival processAckArrival
TimeOut gen_timeout processTimeOut
The non-event functions

These are various functions which can/may be used for simulating all protocols -- they're essentially debugging and utility functions.

Name Description
initParams Parse command line arguments and intialize appropriate variables.
initAll Initialize ALL variables.
showParameters Show values of important parameters before simulating.
showReport Show the report at the end of the simulation.
showEventList Show the current event list.
showCurrentEvent Show the current event.
printQueue Print out the queues contents.
postCycleOP Print OP at the end of processing an event.
queueItUp Take a packet and put it into a node's queue.
Processing of the various events

Before looking at these individual events, it might be helpful to look at a complete event cycle (shown below).

Generating the various events

NOTE: All of the following data is taken from pg 240, Computer Networks, Andrew S. Tannanbaum

gen_arrival

Generate Poisson arrivals. The only parameter you have control over (as the programmer) is lambda - the channel arrival rate.

F = Frame length is bits.
C = Channel capacity in bits / second.
I = Interrupt and service time.
A = Acknowledgement length (in bits).
T = Timeout interval.
  F = D + H;	                    // Number of bits / frame 
  I = (double)(l*F)/C;              // channel length = IC / F 
  timeXPacket = (double)F/C;        // packet transmission time 
  timeXAck = (double)A/C;	    // ACK transmission time
  T = timeXPacket + I;	            // timeout 

   // I = (F/(2.0*C))*(2.0*W + I);     //used to test 50% utilization case
gen_nodefree

The node is free after the last bit of the data packet has been transmitted.This is given by:

    time = F/C

gen_depart

Arrival of a data packet to a receiver. This is after 3 things have happened:

  • Last data bait have arrived to the receiver.
  • The interrupt has been serviced.
  • Receiver is ready to begin transmitting the ACK

This time is given by the expression:

    time = F/C + I

gen_ackarrival

This is when the ACK arrival has been transmitted by the node which sent the data frame. This time is given by the expression:

    time = F/C + I + A/C

gen_timeout

This is when a node has not revied an ACK for an outstanding packet. After a certain time, (Timeout Interval - T), the node times out and requeues the missing packet. This timeout inteval is given by the expression:

    F/C + I

See Timeout event sequence (above) for explanation of why this is so.
Event Sequences

This 1st event sequence (shwon below) shows a typical event sequence for a suuccessfully transmitted data frame and it's ACK. This various times are shown on the figure.

This 2nd event sequence (shown below) is the same as the 1st sequence, except the various events are named.

This shows a typical timeout sequence (shown below):