Electrical
Computer
and Systems Engineering ECSE  Computer Communication Networks CCN September
 
Laboratory
 Implementing a Reliable Transport Protocol Due Friday October th Due Wednesday October
th ONLY for tapedelayed students
Overview In this laboratory programming assignment
you will be writing the sending and receiv
ing transport
level code for implementing a simple reliable data transfer protocol There are two versions of this lab
the Alternating
Bit
Protocol aka stopandwait version and the Go
Back
N version This lab should be fun since your implementation will dier very little from what would be required in a realworld situation Since you probably don t have standalone machines with an OS that you can modify
your code will have to execute in a simulated hardware software environment However
the programming interface provided to your routines
ie
the code that would call your entities from above and from below is very close to what is done in an actual UNIX environment Stopping starting of timers are also simulated
and timer interrupts will cause your timer handling routine to be activated  The routines you will write The procedures you will write are for the sending entity A and the receiving entity B Only unidirectional transfer of data from A to B is required Of course
the B side will have to send packets to A to acknowledge positively or negatively receipt of data Your routines are to be implemented in the form of the procedures described below These procedures will be called by and will call procedures which emulate a network environment The unit of data passed between the upper layers and your transport layer protocols is a message
which is declared as struct msg
char data  This declaration
and all other data structure and emulator routines
as well as stub routines ie
those you are to complete are in the le
progc
described later Your sending entity will thus receive data in byte chunks from layer ie the application layer your receiving entity should deliver byte chunks of correctly received data to layer ie application layer at the receiving side The unit of data passed between your routines and the network layer is the packet
which is declared as struct pkt
int seqnum int acknum int checksum char payload  Your routines will ll in the payload eld from the message data passed down from layer The other packet elds will be used by your protocols to insure reliable delivery
as we have studied in class The routines you will write are detailed below As noted above
such procedures in reallife would be part of the operating system
and would be called by other procedures in the operating system The relationship between some of these routines is shown in Figure  layer 5 Message from B_input Packets from layer 3 e.g., ACKs A_output A_input HOST A HOST B LAYER 4 LAYER 4 LAYER 3 (part of the simulator) Packets to layer 5 Packets to layer 3 Packets from layer 3 Packets to layer 3 (e.g., ACKs) LAYER 5 (part of the simulator) LAYER 3 (part of the simulator) LAYER 5 (part of the simulator) Figure  Relationship between various routines
A outputmessage
where message is a structure of type msg
containing data to be sent to the Bside This routine will be called whenever the upper layer at the sending side A has a message to send It is the job of your protocol to insure that the data in such a message is delivered inorder
and correctly
to the receiving side upper layer
A inputpacket
where packet is a structure of type pkt This routine will be called whenever a packet sent from the Bside ie
as a result of a tolayer being done by a Bside procedure arrives at the Aside packet is the possibly corrupted packet sent from the Bside
A timerinterrupt This routine will be called when A s timer expires thus gen erating a timer interrupt You ll probably want to use this routine to control the retransmission of packets See starttimer and stoptimer below for how the timer is started and stopped
A init This routine will be called once
before any of your other Aside routines are called It can be used to do any required initialization
B inputpacket
where packet is a structure of type pkt This routine will be called whenever a packet sent from the Aside ie
as a result of a tolayer being done by a Aside procedure arrives at the Bside packet is the possibly corrupted packet sent from the Aside
B init This routine will be called once
before any of your other Bside routines are called It can be used to do any required initialization  Software Interfaces The procedures described above are the ones that you will write The following routines which can be called by your routines
starttimercalling entityincrement
where calling entity is either  for starting the Aside timer or  for starting the B side timer
and increment is a oat value indicating the amount of time that will pass before the timer interrupts A s timer should only be started or stopped by Aside routines
and similarly for the Bside timer To give you an idea of the appropriate increment value to use a packet sent into the network takes an average of  time units to arrive at the other side when there are no other messages in the medium
stoptimercalling entity
where calling entity is either  for stopping the Aside timer or  for stopping the B side timer
tolayercalling entitypacket
where calling entity is either  for the Aside send or  for the B side send
and packet is a structure of type pkt Calling this routine will cause the packet to be sent into the network
destined for the other entity
tolayercalling entitymessage
where calling entity is either  for Aside deliv ery to layer  or  for Bside delivery to layer 
and message is a structure of type msg With unidirectional data transfer
you would only be calling this with call ing entity equal to  delivery to the Bside Calling this routine will cause data to be passed up to layer   The simulated network environment A call to procedure tolayer sends packets into the medium ie
into the network layer Your procedures A input and B input are called when a packet is to be delivered from the medium to your protocol layer The medium is capable of corrupting and losing packets It will not reorder packets When you compile your procedures and the prede ned procedures together and run the resulting program
you will be asked to specify values regarding the simulated network environment
Number of messages to simulate The emulator and your routines will stop as soon as this number of messages have been passed down from layer 
regardless of whether or not all of the messages have been correctly delivered Thus
you need not worry about undelivered or unACK ed messages still in your sender when the emulator stops Note that if you set this value to 
your program will terminate immediately
before the message is delivered to the other side Thus
this value should always be greater than 
Loss You are asked to specify a packet loss probability A value of  would mean that one in ten packets on average are lost
Corruption You are asked to specify a packet loss probability A value of  would mean that one in ve packets on average are corrupted Note that the contents of payload
sequence
ack
or checksum elds can be corrupted Your checksum should thus include the data
sequence
and ack elds
Tracing Setting a tracing value of  or  will print out useful information about what is going on inside the emulation eg
what s happening to packets and timers A tracing value of  will turn this o A tracing value greater than  will display all sorts of odd messages that are for the emulatordebugging purposes A tracing value of  may be helpful to you in debugging your code You should keep in mind that real implementors do not have underlying networks that provide such nice information about what is going to happen to their packets
Average time between messages from sender
s layer You can set this value to any nonzero
positive value Note that the smaller the value you choose
the faster packets will be be arriving to your sender  The AlternatingBitProtocol For the AlternatingBitProtocol part of the lab
you are to write the procedures
A output
A input
A timerinterrupt
A init
B input
and B init which together will imple ment a stopandwait ie
the alternating bit protocol
which we referred to as rdt in the text unidirectional transfer of data from the Aside to the Bside Your protocol should use both ACK and NACK messages You should choose a very large value for the average time between messages from sender s layer
so that your sender is never called while it still has an outstanding
unacknowledged message it is trying to send to the receiver We would suggest you choose a value of  You should also perform a check in your sender to make sure that when A output is called
there is no message currently in transit If there is
you can simply ignore drop the data being passed to the A output routine You should put your procedures in a le called progc You will need the initial version of this le
containing the emulation routines we have writen for you
and the stubs for your pro cedures You can obtain this program from http gaia cs umass edu kurose transport prog c This lab can be completed on any machine supporting C PLEASE SEE SECTION  FOR PLATFORM SPECIFIC DETAILS Make sure you read the helpful hints for this lab in the online version of the book The deliverables for this part of the lab and next are described in Section   GoBackN Protocol For the GoBackN protocol part of the lab
you are to write the procedures
A output
A input
A timerinterrupt
A init
B input
and B init which together will imple ment a GoBackN unidirectional transfer of data from the Aside to the Bside
with a window size of  Your protocol should use both ACK and NACK messages Consult the alternatingbitprotocol version of this lab above for information about how to obtain the network emulator We would STRONGLY recommend that you rst implement the easier lab Alter nating Bit and then extend your code to implement the harder lab GoBackN However
some new considerations for your GoBackN code which do not apply to the Alternating Bit protocol are 
A outputmessage
where message is a structure of type msg
containing data to be sent to the Bside Your A output routine will now sometimes be called when there are outstanding
unacknowledged messages in the medium  implying that you will have to buer multiple messages in your sender Also
you ll also need buering in your sender because of the nature of GoBackN sometimes your sender will be called but it won t be able to send the new message because the new message falls outside of the window Rather than have you worry about buering an arbitrary number of messages
it will be OK for you to have some nite
maximum number of buers available at your sender say for  messages and have your sender simply abort give up and exit should all  buers be in use at one point Note using the values given below
this should never happen In the realworld
 of course
one would have to come up with a more elegant solution to the nite buer problem
A timerinterrupt This routine will be called when A s timer expires thus gener ating a timer interrupt Remember that you ve only got one timer
and may have many outstanding
unacknowledged packets in the medium
so you ll have to think a bit about how to use this single timer The deliverables for this part of the lab and the previous part are described in Section   Helpful Hints and the like
Checksumming You can use whatever approach for checksumming you want Remem ber that the sequence number and ack eld can also be corrupted We would suggest a TCPlike checksum
which consists of the sum of the integer sequence and ack eld values
added to a characterbycharacter sum of the payload eld of the packet ie
treat each character as if it were an  bit integer and just add them together
Global state Note that any shared state among your routines needs to be in the form of global variables Note also that any information that your procedures need to save from one invocation to the next must also be a global or static variable For example
your routines will need to keep a copy of a packet for possible retransmission It would probably be a good idea for such a data structure to be a global variable in your code Note
however
that if one of your global variables is used by your sender side
that variable should NOT be accessed by the receiving side entity
since in real life
communicating entities connected only by a communication channel can not share global variables
Time variable There is a oat global variable called time that you can access from within your code to help you out with your diagnostics msgs
START SIMPLE Set the probabilities of loss and corruption to zero and test out your routines Better yet
design and implement your procedures for the case of no loss and no corruption
and get them working rst Then handle the case of one of these probabilities being nonzero
and then nally both being nonzero
Debugging We d recommend that you set the tracing level to  and put LOTS of printf s in your code while your debugging your procedures
Random Numbers If you get an error message It is likely that random number generation on your machine is different from what this emulator expects Please take a look at the routine jimsrand in the emulator code Sorry  then you ll know you ll need to look at how random numbers are generated in the rou tine jimsrand see the comments in Section  FAQ and other instructions
Frequently Asked Questions The authors of the text book have posted a F AQ at http gaia cs umass edu kurose transport programmingassignmentQA htm
Random Number routine The setting for the variable mmm in the routine jimsrand is platform dependent For Solaris  Windows x and HP
UX it should be set to  For Linux  and FreeBSD   it should be set to  This is basically the value of the maximum random number generated by the rand function on that platform This is usually found in the RAND MAX variable de ned in stdlib h DeliverablesSubmissions NOTE ALL SUBMISSIONS MUST BE DONE VIA WEBCT DROPBOX ON
LINE The lab will count for  of your nal grade  is for the alternating bit version and  is for the gobackN version Partial credit may be awarded only if the code compiles correctly and evidence of progress in the lab is seen in the code You will need to submit
Source code The C le containing the routines you have written
appropriately commented Note that your le MUST compile to qualify for any credit
A text le containing the output Insert printf statements at appropriate places in the code to obtain a text le sample below which outlines the way packets have been transmitted and received in dierent loss settings You should submit output for a run that was long enough so that at least  messages were successfully transfered from sender to receiver ie
the sender receives ACK for these messages transfers in each case
Dierent cases to be considered You will need to run you program under the following settings  Zero probability of loss and packet corruption  
 probability of loss
zero probability of corruption  
 probability of loss and corruption  Trace level set to  for all runs of the program Please direct all technical questions regarding the lab to the bulletin board The TAs and instructors will be able to help you in conceptual matters regarding the lab
but will not be available to debug your code Sample Alternating
Bit Protocol output  Stop and Wait Network Simulator Version    Enter the number of messages to simulate  Enter packet loss probability enter   for no loss  Enter packet corruption probability   for no corruption  Enter average time between messages from senders layer      Enter TRACE A Sending message  B Received message  Recd ACK for message  A Sending message  TOLAYER packet being lost A Timed out retransmitting message  B Received message  Recd ACK for message  A Sending message  Simulator terminated at time   after sending  msgs from layer Sample Go
Back
N output  Stop and Wait Network Simulator Version    Enter the number of messages to simulate  Enter packet loss probability enter   for no loss  Enter packet corruption probability   for no corruption  Enter average time between messages from senders layer      Enter TRACE A Sending message  B Received message  ARecd ACK for message  A Sending message  A Sending message  TOLAYER packet being lost B Received message  TOLAYER packet being lost A Sending message  B Discarding duplicate or out of order message  A Sending message  A Timed out retransmitting message  A Timed out retransmitting message  A Timed out retransmitting message  A Timed out retransmitting message  B Discarding duplicate or out of order message  ARecd ACK for message  A Sending message  A Sending message  B Discarding duplicate or out of order message  B Received message  B Received message  ARecd ACK for message  A Sending pending message  B Received message  A Sending pending message  B Received message  TOLAYER packet being lost B Received message  B Received message  Simulator terminated at time   after sending  msgs from layer