COMP SCI 3001 - Computer Networks & Applications Assignment 2: Reliable Transport: Alternating Bit
Programming Assignment 2: Reliable Transport (must use commit comments) (Alternating Bit)
Computer Networks & Applications
Programming Assignment 2: Building a Reliable Transport Protocol1
Very Important
Although this practical is marked automatically, all marks will be moderated by a marker using the following information.
You must add a comment explaining the changes you've made to your svn repository commits. In other words, each commit should explain what was changed in the code and why briefly (e.g. it may be a bug fix or a protocol behaviour fix).
We should be able to review your development process and see the changes made to code with each version you have committed. Please keep in mind that we can check the number of lines of code as well as actual code changes made with each commit.
During manual marking and plagiarisms checks, we will look look at your development process. If we do not see a clear path to a solution (i.e. code changes and regular commits and comments reflecting your learning to develop the protocol you will forfeit 50% of the marks allocated for this prac and in the extreme case you will be allocated a mark of 0%. An example case of a 0% would be the sudden appearance of working code passing multiple tests). It is up to you to provide evidence of your development process. I expect this will happen after each submission to the oracle.
Please make use of the emulator to help you learn!
Alternating Bit Protocol
You've been hired by "Net Source", a company specialising in networking software. Their programmer, Mue, who was working on an implementation of the Alternating Bit protocol has caught the flu and the implementation must absolutely be finished in the next week. Most of the implementation is complete and Mue left comments for parts still to be completed. As the code isn't finished, Mue hasn't completed testing yet.
Mue is an experienced C programmer and there is nothing wrong with the C syntax or structure of the code that Mue has written. So you don't have to correct any C syntax errors, your job is to finish the code, correct any protocol errors and test it. Your boss realises you're not a C expert, but at least you've programmed in some language with C like syntax (e.g. Java, C++) before so you're the closest they have as an expert. Mue has written a C hints for programmers of C like languages programmers sheet which explains what you need to know about C that is different than Java. She's confident that if you stick to the sheet, anything else you need to add or change would be the same if you wrote it in Java.
The testing system
To help isolate and demonstrate the behaviour of the sender and receiver, you have a simulation system at your disposal. The overall structure of the environment is shown below:
There are two hosts (A and B). An application on host A is sending messages to an application on host B.
The application messages (layer 5) on host A are sent to layer 4 (transport) on host A, which implements Alternating Bit for reliable delivery. Layer 4 creates packets and sends them to the network (layer 3). The network transfers (unreliably) these packets to host B where they are handed to the transport layer (Alternating Bit receiver) and if not corrupt or out of order, the message is extracted and delivered to the receiving application (layer 5) on host B.
Mue has supplied the code for the Alternating Bit sender procedures A_output(), A_init(), A_input(), and A_timerinterrupt(). She has also written the code for the Alternating Bit receiver procedures B_input() and B_init(). At this stage, only unidirectional transfer of data (from A to B) is required, so B does not need to implement B_timerinterrupt or B_output. Of course, B will have to send ACK packets to A to acknowledge receipt of data.
The routines are detailed below. Such procedures in real-life would be part of the operating system, and would be called by other procedures in the operating system. In the simulator the simulator will call and be called by procedures that emulate the network environment and operating system.
· A_output(message), where message is a structure of type struct msg, containing data to be sent to B. This routine will be called whenever the upper layer application at the sending side (A) has a message to send. It is the job of the Alternating Bit protocol to insure that the data in such a message is delivered in-order, and correctly, to the receiving side upper layer.
· A_input(packet), where packet is a structure of type struct pkt . This routine will be called whenever a packet sent from B (i.e., as a result of a tolayer3() being called by a B procedure) arrives at A. packet is the (possibly corrupted) packet sent from B.
· A_timerinterrupt() This routine will be called when A's timer expires (thus generating a timer interrupt). This routine controls 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 other A-side routines are called. It is used to do any required initialization.
· B_input(packet), where packet is a structure of type struct pkt . This routine will be called whenever a packet sent from A (i.e., as a result of a tolayer3() being called by a A-side procedure) arrives at B. The packet is the (possibly corrupted) packet sent from A.
· B_init() This routine will be called once, before any other B-side routines are called. It is used to do any required initialization.
The unit of data passed between the application layer and the Alternating Bit (transport layer) protocol is a message, which is declared as:
struct msg { char data[20];};
That is, data is stored in a msg structure which contains an array of 20 chars. A char is one byte. The sending entity will thus receive data in 20-byte chunks from the sending application; and the receiving entity should deliver 20-byte chunks to the receiving application.
The unit of data passed between Alternating Bit (transport layer) and the network layer is the packet, which is declared as:
struct pkt { int seqnum; int acknum; int checksum; char payload[20];};
The A_output routine fills in the payload field from the message data passed down from the Application layer. The other packet fields are used by the Alternating Bit protocol to insure reliable delivery, as we've seen in class.
These functions implement what the sender and receiver should do when packets arrive.
Software Interfaces
The procedures described above implement the Alternating Bit tranport layer protocol. The following emulator procedures are called by the Alternating Bit procedures. They are explained here so you know how they fit in. They are not part of the Alternating Bit implementation and these routines work correctly. Do not modify them:
· starttimer(calling_entity,increment), where calling_entity is either A (for starting the A-side timer) or B (for starting the B side timer), and increment 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. You are free to experiment with different timeout values; but when handing in for mark submission linking, the timeout value must be set to 15.0
Note that starttimer() is not restarttimer(). If a timer is already running it must be stopped before it is started. Calling starttimer when the timer is already running, or calling stoptimer when the timer is not running, indicates an error in the protocol behaviour and will result in an error message.
The starttimer() call should occur immediately after the tolayer3() call to send the packet being timed.
· stoptimer(calling_entity), where calling_entity is either A (for stopping the A-side timer) or B (for stopping the B side timer).
· tolayer3(calling_entity,packet), where calling_entity is either A (for the A-side send) or B (for the B side send), and packet is a structure of type struct pkt. Calling this routine will cause the packet to be sent into the network, destined for the other entity.
· tolayer5(calling_entity,message), where calling_entity is either A (for A-side delivery to layer 5) or B (for B-side delivery to layer 5), and message is a structure of type msg. With unidirectional data transfer, you would only be calling this with calling_entity equal to B (delivery to the B-side). Calling this routine will cause data to be passed up to layer 5.
The emulator code is in the file emulator.c Download emulator.c. The incorrect implementation of Alternating Bit is in the file altbit.c Download altbit.c. There are also two header files emulator.h Download emulator.h and altbit.h Download altbit.h, which define the procedures and shared variables used in the program.
You should download the 4 files and examine the code in altbit.c with the description above and your knowledge of Alternating Bit and make sure you understand how the program fits together. You do not need to understand emulator.c; but if you want to know how the emulator works, you are welcome to look at the code.
To build the program use the command: gcc -ansi -Wall -pedantic emulator.c altbit.c
The executable program will be called a.out. To run the program, type: ./a.out
The simulated network environment
The medium is capable of corrupting and losing packets. It will not reorder packets. When you compile and run the resulting program, you will be asked to specify values regarding the simulated network environment:
· Number of messages to simulate.The emulator will stop generating messages as soon as this number of messages have been passed down from layer 5.
· Loss. You are asked to specify a packet loss probability. A value of 0.1 would mean that one in ten packets (on average) are 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) are corrupted. Note that the contents of payload, sequence or ack field can be corrupted.
· Tracing. Setting a tracing value of 1 or 2 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 messages that detail what is happening inside the emulation code as well. A tracing value of 2 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 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 generated.
Take a moment to experiment with the simulated environment and look at the events that occur. Try sending a few packets with no loss or corruption. Does the protocol work properly? Try with just loss. Try with just corruption. Some of the errors with the Alternating Bit implementation should be apparent.
What to do
The implementation of Alternating Bit should be identical to that described in your book (page 244/245, Extended FSM description of Alternating Bit sender and receiver are shown).
There may be errors in the protocol. You will need to test it. The errors are only in the altbit.c file. The other three files are correct and do not need to be modified. None of the mistakes are with the programming language or the data structures, they are all errors in the protocol behaviour. The program will compile and run as written; but the sender and receiver do not follow the Alternating Bit protocol.
· This part has 4 tests which test that you have correctly finished the code.
We have provided an Oracle (see details below in the Submission section) to give you feedback on your solution. However, the Oracle will only tell you if you pass the tests or not; but will give you no other information. There is no penalty to use the Oracle for getting feedback.
· Then, if the Oracle feedback is not enough for you to identify the error. You can sumbmit to the Alternating Bit *SUBMISSION* link. Since the submission link will show you what should have happened if you submit an incorrect solution, there is a tiny 1 mark penalty for each submission you make after the second submission. You should try to test and correct any errors before submission. If you rely on mark submission link to do your testing, then your mark will reflect this. However, if you are really stuck, remember 1 or even several marks as nearly no consequence on your final grade contribution, you can use the feedback from the Alternating Bit *SUBMISSION* link to help clarify any misconception.
I suggest the following strategy for this practical. In each step I'd recommend focussing on getting the receiver behaving correctly first and then turn your attention to the sender (the receiver behaviour is simpler and therefore easier to get right and test). :
1. Compile the code and do a simple test sending just one packet with no corruption or loss. Does both the sender and receiver behave properly in this scenario? If not fix any problems. At this stage you should be able to pass test 1 (you can check with Oracle). If not, look at what your sender and receiver do in your test. (10 marks)
2. Fill in the code items numbered 1. Now run some small tests with loss. Does your sender follow the protocol properly when a packet is lost? If not, fix the behaviour. You should now be able to pass test 2.(10 marks)
3. Fill in the code items number 2 (check if ACK is a duplicate ACK) and 3 (B receives wrong sequence number or corrupt packet). When you have this correct you should be able to pass test 3. (20 marks)
4. Fill in the code item numbered 4. Now run a small test with corruption. Do your sender and receiver detect corruption when it occurs and do they react correctly when a corrupted packet or ACK is received? You should now be able to pass test 4. (10 marks)
PLEASE NOTE: the changes you make to altbit.c must not add, remove or change any comments printed when the trace level is set to 2 or 3 because marking program will use these trace levels and if you change them, the marking programs will fail to give you useful feedback. You can, and should, add comments about what is happening in your code at other trace levels to assist in debugging.
Some Tips to Help You Further
· When you recompile the program. Using the -ansi -Wall -pedantic flags will give you useful warnings if you are doing something that is likely to be wrong (like using = rather than ==, or misusing a data structure). If you get any warnings, fix them before submitting. Warnings indicate that there is something wrong, even if the program compiles. If you can't work out the warning, ask on the discussion board.
· For every behaviour you correct, devise a test case to check that your changes actually work. For example, if you wanted to check that B was responding correctly to a lost packet, send a few (say 2) packets with a loss probability of .2 and see how B responds. If none of the packets are lost, then increase the loss probability until you get a case where one of the packets is lost and a packet arrives out of order so you can see B's response.
· Be sure to commit your changes to svn, or they won't be tested (remember to add commit message that explain your learning and changes, or you will get a zero)
· Once you're confident you have the alternating bit protocol working, or if you are really stuck on what is wrong, submit to marking submission link. Mark Submission Link will run a series of tests specifically designed to identify whether errors have been dealt with. If your corrected program does not pass one of the tests, mark submission link will stop at that point and show you the expected output of the test and your output. By comparing the two you should be able to work out at least one thing that the protocol is still doing incorrectly.
· REMEMBER: The mark Submission Link is not a program with high level reasoning abilities. It simply compares the outputs form a correct implementation with yours but shows you traces that reveal all (the information that would normally be hidden in a network in the real-world).
· Note this programming assignment is in the C language. Most networking system code and many networked applications are written in C, so we consider it important that you have at least seen C and can do some basic reading and debugging in the language. The code is given and the syntax of C, C++ and Java are very similar/same as are the basic structures (if/then, loops, etc), so we do expect that third year students can accomplish this. The main C concepts that you may not have come across in Java will be accessing structures and handling pointers. We have provided a C hints sheet which explains what you need to know that is different than Java. Unless you are familiar with C, please stick to our hints. It's easy to get memory manipulation wrong in C and it can be quite difficult to debug. The hint sheet gives you the easy/clear way of doing the things. Remember that the given code is correct C, so you can use the given code as examples for how to manage the arrays and structures. If you do have any questions still after looking at the examples, please don't hesitate to post questions (even code fragments) on the discussion board
Submitting your assignment and SVN How-To
· You will need to keep your files stored in SVN to allow the submission system to find your work and to be able to submit it for assessment.
· If you aren't familiar with SVN, the following SVN notes will assist you.
· You only need to svn add two files: altbit.c and altbit.h. Since we will not modify the emulator.
· The hand-in key for this assignment is (file names are case sensitive, i.e. please pay attention to upper case and lower-case letters):
<year>/<semester>/cna/AlternatingBit
As, before, you can submit and automatically mark your assignment by following this link to the web-submission.
There are two submission links:
1) **ORACLE** - Alternating Bit link. Oracle to feedback to improve your solution (unlimited submissions): You can submit to the Alternating Bit Oracle with no penalty. This is also done through the web-submission system. This will give tell you what aspects of the protocol are working correctly only. No further feedback is given.
2) Alternating Bit *SUBMISSION* link: You must submit there for final assessment. Your this also provides detailed feedback to help you identify and fix your implementation. Remember that each submission to the marking link after the second will result in a tiny loss of 1 mark.
The marks assigned by mark submission link are provisional. You are responsible for writing a working implementation and for testing your implementation. Any errors discovered during review will reduce your mark for that functionality. We're not hiding anything; but it is possible that you might create an implementation that has an error not exercised by mark submission link.
Understanding the output from the testing displayed by the Websumission system
We use a utility called diff to compare the generated output from your protocol with ours. What you will see after a submission to the Oracle is a diff between the expected output and your output. The comparison results we provide is limited to the last seven lines in the generated output from testing your protocol.
Example of a differences found:
< followed by text indicates lines from the expected output
> followed by a text indicates lines from the output generated with your implementation
2,3c2,3 you may also see numbers like this, you can find out more about these by reading about the diff utility (for example: https://linuxhandbook.com/diff-command/Links to an external site.).
