CDA 4527: Computer Communication Networks
Home Lecture notes Assignment
Programming Assignment 2: Reliable Data Transfer via Simple Transport Layer Protocol
Due: Tuesday October 23rd before class (late submission with 10~20 points off by Thursday October 25th)
In this second programming assignment, you will be writing the sending and receiving transport-level code for implementing a simple reliable data transfer protocol. The basic assignment will be to implement the Alternating Bit Protocol (rdt3.0); the extra credit assignment will be to implement a Go-Back-N protocol. You should enjoy this assignment, as your implementation will differ very little from what would be required in a real-world situation.
Since we do not have standalone machines (with an Operating System that you can modify), your code will have to execute in a simulated environment. However, the programming interface provided to your routines (i.e., the calls to/from your code from/to the layer above - passing/receiving data to/from the application layer; and the calls to/from your code from/to the layer below - passing/receiving data to/from the layer below) is very close to what is done in an actual UNIX environment. Starting/stopping 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 (node A) and the receiving entity (node 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 as described below. These procedures will be called by (and will also make calls to) procedures that the textbook authors have written which emulate a network environment which can cause packet error and packet loss. The overall structure of the environment is shown in the following:
The unit of data passed between the upper layer and your protocol is a message, which is declared as:Your sending entity will thus receive data in 20-byte chunks from layer 5; your receiving entity should deliver 20-byte chunks of correctly received data to layer 5 at the receiving side.
The unit of data passed between your routines and the network layer is the packet, which is declared as:Your routines will fill in the payload field from the message data passed down from layer 5. The other packet fields will be used by your protocol to insure reliable delivery, as we've seen in class.
The routines you will write are detailed below. As noted above, such procedures in real-life would be part of the operating system, and would be called by other procedures in the operating system.
- where is a structure of type containing data to be sent to the B-side. This routine will be called whenever the upper layer at the sending side (node A) has a message to send. It is the job of your protocol to insure that the data in such a message is delivered in-order, and correctly, to the receiving side upper layer. You should return a value of 1 if this data packet was accepted for transmission and -1 otherwise.
- where is a structure of type This routine will be called whenever a packet sent from the B-side (i.e., as a result of a being done by a B-side procedure) arrives at the A-side. is the (possibly corrupted) packet sent from the B-side.
- This routine will be called when A's timer expires (thus generating a timer interrupt). You'll probably want to use this routine to control the retransmission of packets. See and below for how the timer is started and stopped.
- This routine will be called once, before any of your other A-side routines are called. It can be used to do any required initialization.
- where is a structure of type This routine will be called whenever a packet sent from the A-side (i.e., as a result of a being done by a A-side procedure) arrives at the B-side. is the (possibly corrupted) packet sent from the A-side.
- This routine will be called once, before any of your other B-side routines are called. It can be used to do any required initialization.
The procedures described above are the ones that you will write. The textbook authors have written the following routines which can (and should) be called by your routines:
- where is either 0 (for starting the A-side timer) or 1 (for starting the B side timer), and is a float value indicating the amount of time that will pass before the timer interrupts. A's timer should only be started (or stopped) by A-side routines, and similarly for the B-side timer. To give you an idea of the appropriate increment value to use: a packet sent into the network takes an average of 5 time units to arrive at the other side when there are no other messages in the medium.
- where is either 0 (for stopping the A-side timer) or 1 (for stopping the B side timer).
- where is either 0 (for the A-side send) or 1 (for the B side send), and is a structure of type Calling this routine will cause the packet to be sent into the network, destined for the other entity.
- where is either 0 (for A-side delivery to layer 5) or 1 (for B-side delivery to layer 5), and is a structure of type
Calling this routine will cause data to be passed up to layer 5. With unidirectional data transfer (which is what you have to implement), you would only be calling this routine with equal to 1 (delivery to the B-side).
A call to procedure sends packets into the medium (i.e., into the network layer). Your procedures and 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. However, it will not reorder packets. When you compile your procedures and with the rest of the simulator and run the resulting program, you will be asked to specify values regarding the simulated network environment:
- Number of messages to simulate. The simulator (and your routines) will stop as soon as this number of messages have been passed down from layer 5 to your protocol, 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 or in the channel when the emulator stops. Note that if you set this value to 1, your program will terminate immediately, before the message is delivered to the other side. Thus, this value should always be greater than 1.
- Loss. You are asked to specify a packet loss probability. A value of 0.1 would mean that one in ten packets (on average) is lost.
- Corruption. You are asked to specify a packet corruption probability. A value of 0.2 would mean that one in five packets (on average) have their bits corrupted. Note that the contents of the payload, sequence, ack, or checksum fields can be corrupted. You must implement a checksum mechanism that covers the the data, sequence, and ack fields of the message (see hint for checksum).
- Tracing. Setting a tracing value of 1, 2 or 3 will print out useful information about what is going on inside the emulation (e.g., what's happening to packets and timers). A tracing value of 0 will turn this off. A tracing value greater than 2 will display all sorts of odd messages that are for the emulator-debugging purposes (but that could also help you debug 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 layer5. You can set this value to any non-zero, positive value. Note that the smaller the value you choose, the faster packets will be be arriving to your sender.
You are to write code for the procedures, which together will implement a stop-and-wait (i.e., the Alternating Bit protocol, which we referred to as rdt3.0 on the textbook and class notes), for a unidirectional transfer of data from the node A to node B. Node B should only send back ACK message.
You should choose a somewhat large value for the average time between messages from sender's layer 5, so that your sender is seldom called while it still has an outstanding, unacknowledged message it is trying to send to the receiver. If this occurs, your procedure should return a value of -1 and ignore (drop) that chunk of data, which will inform layer 5 that your protocol is busy trying to send previous data. In this case, layer 5 will reattempt to send this data at a later point in time. If your protocol has space in its window, you should accept the data chunk and return a value of 1.
You should put your procedures inside the file called simulator.c, which contains the simulation engine. You will need the initial version of this file (simulator.c), containing the emulation routines, and the stubs for your procedures.
This assignment can be completed on any machine supporting C, whether Unix or Windows.
What to turn in
- Email me: (1) the source code simulator.c for me to test; (2) your generated executable code and tell me where I can run your program (on Olympus or Windows computer).
- Give me the hardcopy report during class.
- To show me that you did successfully accomplished the assignment, in your hardcopy you hand in: (1) describe in your report your overall program design with explanations for the design choices you might have made; (2) define and run a set of tests, showing me the print out of both the sending side and receiving side of the protocol, and explaining what the tests accomplished.
- For the test case, your procedures should print out some information whenever an event occurs at your sender or receiver (a message/packet arrival, or a timer interrupt) as well as any action taken in response. You should hand in output for a run up to the point (approximately) when 10 messages have been ACK'ed correctly at the receiver, a loss probability of 0.1, and a corruption probability of 0.3, and a trace level of 2. You should annotate your printout with highlighted color (or bald text) showing how your protocol correctly recovered from packet loss and corruption.
- Checksumming. You can use whatever approach for checksumming you want. Remember that the sequence number and ack field can also be corrupted. I would suggest a TCP-like checksum, which consists of the sum of the (integer) sequence and ack field values, added to a character-by-character sum of the payload field of the packet (i.e., treat each character as if it were an 8 bit integer and just add them together).
- 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.
- There is a float global variable called time that you can access from within your code to help you out with your diagnostics msgs (specially during the debugging and test phases).
- 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 first. Then handle the case of one of these probabilities being non-zero, and then finally both being non-zero.
- Debugging. I'd recommend that you set the tracing level to 2 and put lots of printf statements in your code while your debugging your procedures.
Extra Credit Assignment
You are to write the procedures, and which together will implement a Go-Back-N unidirectional transfer of data from the A-side to the B-side, with a window size of 8 (or some other larger fixed number). Your protocol can use cumulative ACK messages.
Some new considerations for your Go-Back-N code (which do not apply to the Alternating Bit protocol) are:
- Your A_output() routine will now sometimes be called when there are outstanding, unacknowledged messages in the medium - implying that you will have to buffer multiple messages in your sender. Also, you'll need buffering in your sender because of the nature of Go-Back-N: 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.
Your sender should buffer only one window worth of packets and use the signaling mechanism (returning a -1 from this procedure) to indicate that the window is full. In order to fill up the sender's window, you should set the average time between messages from sender's layer 5 to a small value, like 2.
- This routine will be called when A's timer expires (thus generating 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.
Consult the basic assignment above for a general description of what to turn in. Besides what is stated there, you should hand in a test case that is at least 20 messages long, showing the window dynamics of your protocol.
Students are encouraged to talk to each other, to the TAs, to the instructors, or to anyone else about any of the assignments. Any assistance, though, must be limited to discussion of the problem and sketching general approaches to a solution. Each student must write out his or her own solutions to the homework.
The project handouts have more detailed information about collaboration when working on the projects, but, basically, each programming project group must write their own code and documentation for the programming projects done as a group.
Consulting another student's or group's solution is prohibited and submitted solutions may not be copied from any source. You may not supply work that you complete during 15-441 to other students in future instances of this course (just as you may not use work completed by students who've taken the course previously). If you have any question about whether some activity would constitute cheating, please feel free to ask the instructors.
Academic IntegrityThe Carnegie Mellon University Policy on Integrity applies. We will strictly follow university policy on reporting cases of cheating.
Take project and homework deadlines seriously. Our experience is that students often seriously underestimate the effort involved in programming assignments and projects. If we give you 4 weeks to complete an assignment, there is typically a reason. In the interest of fairness, we have adopted the following late policy:
- Each student is given a total of 2 "free points" to use during the semester.
- One free point can be used to extend the deadline of any homework assignment or Project 1 by a single day with no penalty.
- Two free points are needed to extend the deadline of Projects 2 or 3 by a single day with no penalty (you and your partner might each contribute a point).
- In the absence of free points, the deadline for any assignment can be extended with a 15% penalty per day.
- No deadline can be extended by more than two days, regardless of how many free points you have saved up. Assignments will NOT be accepted 48 hours after the due date.
- If you are ill: If you have a medical note, you may turn in your assignments late without using free points. Please contact the instructors to arrange a reasonable replacement turn-in time. You must notify us before the due-date. Without a medical note, you must use your free points as you would with any other reason for being late.
If you think we made a mistake in grading, please return the assignment with a note explaining your concern to the course secretary no later than two weeks after the day the assignment was returned. We will have the question re-graded by the person responsible for grading that question.
Please try to avoid having partner problems. Seriously! Share your hopes before they turn into concerns, your concerns before they are problems, and your problems before they inflate into crises.
In order for the course staff to help you and your partner work through issues, or for us to provide an appropriate response to serious partner problems, you must contact us well before the relevant due date! A special case to avoid is coming to us a day or two before a major deadline to tell us that your partner has been ill (etc.) for multiple weeks. We, and thus you, have many more options if you inform us while a problem is developing, instead of after the fact.
Taking Care of Yourself
Do your best to maintain a healthy lifestyle this semester by eating well, exercising, avoiding drugs and alcohol, getting enough sleep and taking some time to relax. This will help you achieve your goals and cope with stress.
All of us benefit from support during times of struggle. You are not alone. There are many helpful resources available on campus and an important part of the college experience is learning how to ask for help. Asking for support sooner rather than later is often helpful.
If you or anyone you know experiences any academic stress, difficult life events, or feelings like anxiety or depression, we strongly encourage you to seek support. Counseling and Psychological Services (CaPS) is here to help: call 412-268-2922 and visit their website at http://www.cmu.edu/counseling/. Consider reaching out to a friend, faculty or family member you trust for help getting connected to the support that can help.