Fall 2023 – CSEE W4119 Computer Networks Programming Assignment 2 – Network Protocols Emulation
1 Introduction
In this assignment, you will emulate the operation of a link layer and network layer protocol in a small computer network. The program you write should behave like a single node in the network. You will start several nodes (instances of your program) so that they can send packets to each other as if there are links between them. Running as an independent node, your program should implement a simple version of Go-Back-N Protocol (Link Layer) and the Distance-Vector Routing Algorithm (Network Layer), in order to provide reliable transmissions and efficient routing.
Each section of the assignment will walk you through a different portion on the way to this end goal. Section 2 will have you implement the Go-Back-N protocol whereas Section 3 will have you implement a Distance Vector Routing Algorithm. By the time you get to Section 4, which is to combine these two algorithms, you should have the vast majority of the hard work done and can focus on these two algorithms working in tandem. The assignment is split into these sections not only to make it easier, but also to give you the most opportunity for partial credits. Accomplishing only Sections 2 and 3 will get you 80 of the 100 points available. Please follow the instructions step by step, and submit the programs for whichever sections you attempt/accomplish.
This assignment is meant to be done on your own; do not collaborate with others as this is cheating!
Please start early and read the entire PDF! As with PA1, your submission must work on the Google Cloud VM!
2 Go-Back-N Protocol (40 points) 2.1 Description
This section involves two nodes, a sender and a receiver. The sender sends packets to the receiver through the UDP protocol. You have to implement the Go-Back-N (GBN) protocol on top of UDP on both nodes to guarantee that all packets can be successfully delivered in the correct order to the higher layers. To emulate an unreliable channel, the receiver or the sender will respectively drop an incoming data packet or an ACK with a certain probability.
2.2 Protocol
2.2.1 Packet
The GBN sender wants to send a string of text. For simplicity, each character will be put in a separate data packet, which means that the data in each packet should have the max length of 1 byte. Your own packet header is needed to maintain the order of data packets. There will be no requirements on the format of these headers, so you should come up with your own design. For example, you can add a 32-bit sequence number ahead of the data you want to send (see Figure 1).
Your packet header should be uniform for both ACKs and data packets. It is up to you how to mark a packet as being an ACK. One suitable choice would be to set the data byte to a certain value that will not represent an
Figure 1: GBN Packet Header Example
alphanumeric or punctuation character. Another choice would be to include a 1-byte value in the header set to 0 or 1 to mark an ACK.
2.2.2 Buffer
Each node should have a sending buffer. All data packets (not ACKs) should be put into the buffer before sending, and removed from the buffer once the corresponding ACK is received. The sending buffer should be long enough to avoid the conflict of packet numbers given the window size. If the buffer is full, the sending function simply waits until more space is available.
2.2.3 Window
The window moves along the sending buffer. If you implement the buffer as an array, the window should wrap back around to the beginning of the array after reaching the end. In GBN, packets in the window should be sent out immediately. The size for the window will be passed in as an argument when starting your program.
2.2.4 Timer
There is only one timer for GBN. It starts after the first packet in the window is sent out, and stops when the ACK for the first packet in the window is received. After the window moves, if the first packet of the new window has already been sent out, the timer should simply restart, otherwise it should stop and wait for the first packet to be sent out.
The timeout for the timer should be 500ms and all the packets in the window should be resent after timeout. Your implementation of the timeout in PA1 should come in handy here.
2.3 Emulation
In this section, you should create a program that emulates a GBN node using the specifications above. For emulation purposes, the receiver will deliberately discard data packets (as if the packets are lost and not received) and the sender will deliberately discard ACKs before actually handling them. There are two ways to control the drop of the packets or ACKs – deterministic and probabilistic. The deterministic way is to drop every nth packet, and the probabilistic way is to drop packets randomly with certain probability p (for sanity check, probability of 0 here means no packets are lost, and probability of 1 means all packets are lost). Which method will be used and the value of n or p will be passed in when starting the program.
Figure 2: Packet Loss Example
Command Syntax
Starting Programs
The GBN node should be started with any of the following commands:
C $ ./gbnnode
Java $ java gbnnode
The user should only specify either -d or -p. The square bracket and the vertical line means to choose between the two options.
-d means the GBN node will drop packets (data or ACK) in a deterministic way (for every n packets), and -p means the GBN node will drop packets with a probability of p.
(To make it clear, “gbnnode” is the name of the program. The arguments should be passed in at the launch of the program, not after the program has started to run). The square brackets with a bar in the middle indicate an “either or” command line option.
Sending Messages
After the GBN node has started, node> is prompted for commands. There is only one command allowed: node> send
message is a character string which the sender will send to the
The following messages should be displayed on each node for the situations that have been described above: Sender side:
[
[
[
Receiver side:
[
At the end of the transmission, have both the sender and receiver print out the ratio of total packet failures to total packets received, to see how it relates to the failure rate specified on the command line:
[Summary] <# dropped>/<# total> packets discarded, loss rate =
To test the loss rate emulation, set up a sender and receiver node where:
• No ACKS fail (sender drop rate = 0)
• Packets dropped probabilistically (receiver drops with probability p) • 1000 packets are sent (message of 1000 characters)
• window size is 5
At the end of transmission, the receiver’s summary message should have a loss ratio near the input probability p.
Your program should deal with the following cases:
Normal packet sending An ACK is lost
A packet is dropped Duplicate packets Duplicate ACK’s
Loss rate calculation
2.8 Example
Sender side:
$ ./gbnnode 1111 2222 3 -p 0.2
node> send abcde
[1700539210.011] packet0 a sent
[1700539210.031] packet1 b sent
[1700539210.049] packet2 c sent
[1700539210.062] ACK0 received, window moves to 1
[1700539210.078] packet3 d sent
[1700539210.082] ACK1 received, window moves to 2
[1700539210.088] packet4 e sent
[1700539210.090] ACK1 received, window moves to 2
[1700539210.106] ACK1 discarded
[1700539210.106] ACK1 received, window moves to 2
[1700539210.549] packet2 timeout
[1700539210.551] packet2 c sent
[1700539210.562] packet3 d sent
[1700539210.573] ACK2 received, window moves to 3 [1700539210.575] packet4 e sent
[1700539210.593] ACK3 discarded
[1700539210.573] ACK4 received, window moves to 5 [Summary] 2/8 packets discarded, loss rate = 0.25% Receiver side:
$ ./gbnnode 2222 1111 3 -p 0.2
[1700539210.033] packet0 a received
[1700539210.042] ACK0 sent, expecting packet1
[1700539210.053] packet1 b received
[1700539210.059] ACK1 sent, expecting packet2
[1700539210.072] packet2 c discarded
[1700539210.079] packet3 d received
[1700539210.084] ACK1 sent, expecting packet2
[1700539210.095] packet4 e received
[1700539210.101] ACK1 sent, expecting packet2
[1700539210.559] packet2 c received
[1700539210.562] ACK2 sent, expecting packet3
[1700539210.579] packet3 d received
[1700539210.581] ACK3 sent, expecting packet4
[1700539210.590] packet4 e received
[1700539210.581] ACK4 sent, expecting packet4
[Summary] 1/8 packets dropped, loss rate = 0.125%
Window moves and ACK replied
Following ACK could also move the window
Timer timeout and packets resent
the packet is not delivered and the correct ACK is replied the window will not move
Probabilistic loss rate test converges to input probability
(10pt) (10pt) (5pt) (5pt) (5pt) (5pt)
3 Distance-Vector Routing Algorithm (40pt) 3.1 Description
The objective of this portion of the assignment is to implement a simplified version of a routing protocol in a static network. You are required to write a program which builds its routing table based on the distances (i.e., edge weights) to other nodes in the network. The Bellman-Ford algorithm should be used to build and update the routing tables. The UDP protocol should be used to exchange the routing table information among the nodes in the network.
3.2 Network Model
You may assume that that all the nodes (instances of your program) run on the same machine and they all have the same IP address. Each node can be identified uniquely by a port number, which is specified by the user. The port numbers must be > 1024. The maximum number of nodes to support is 16. The links among the nodes in the network and the distances (non-negative integer) between two directly connected nodes are specified by the user upon the activation of the program and stay static throughout the session. No need to support dynamic link/node status changes. The link distance is the same for either direction (e.g. Between node A and B, DistanceA→B = DistanceB→A.)
3.3 Protocol
For this assignment, we will use the UDP protocol to exchange the routing information among the nodes. Each node will send its most recent routing table by building a UDP packet. The destination port is the listening port of the node to which the packet is being sent. The source port is an arbitrary UDP port the node is using to send the packet. The data field of a packet should include 1) the sending node UDP listening port number (to identify the sending node to its neighbor) and 2) the most recent routing table.
3.4 Routing Information Exchange
You are free to design the format and structure of the routing table kept locally by each node and exchanged among neighboring nodes.
1. Upon the activation of the program, each node should construct the initial routing table from command line info, and keep it locally.
2. Once the link and distance information for all the nodes are specified, the routing table information will be exchanged among network neighbors. Each node should send its routing table information to its neighbors at least once. (See the command syntax section for more detail on how the process starts). This is the base case before there are any table updates.
3. Using the Bellman-Ford algorithm, each node will keep updating its routing table as long as neighboring nodes send their updated routing tables information.
4. If there is any change in the routing table, a node should send the updated information to its neighbors.
Due to the nature of the UDP protocol, packets may be lost or delivered out of order to the application. Thus you may consider to add some kind of time stamp or sequence information to each packet (i.e. each routing table), so that each node can update its own routing table accordingly. Note that if the process is implemented properly, the routing information exchange should converge (stop) as soon as all nodes in the network obtain the routing tables with the shortest path information.
3.5 Command Syntax
The program name should be dvnode. For each node in the network, the command syntax is:
$ dvnode
Status Messages
ctrl+C (exit)
Program name.
The UDP listening port number (1024-65534) of the node.
The UDP listening port number (1024-65534) of one of the neighboring nodes.
This will be used as the link distance to the
It is between 0-1 and represents the probability of a packet being dropped on that link.
For this section of the assignment you do not have to implement dropping of packets.
Keep listing the pair of
Indication of the last node information of the network. The proram should understand this arg as optional (he command with this argument, the routing message exchanges among the nodes should
Use ctrl+C to exit the program.
The following status messages should be displayed at least for the following events. The example of the messages are also shown below.
1. Routing message sent:
[
[
[
– (
Your program should deal with the following cases:
Distance Vector DV Updates Convergence
3.8 Example
Routing tables and their updates should follow DV algorithms
DV updates should be sent out to all neighbors once the routing table is changed Routing tables should eventually converge and all output should cease
(20pt) (10pt) (10pt)
The example below illustrates the command inputs, routing message exchanges and the computation of the routing table at each node, given the network configuration described in Figure 3.
The command to start a program is:
C $ ./dvnode
Java $ java dvnode
From the command line prompts type:
$ ./dvnode 1111 2222 .1 3333 .5
程序代写 CS代考 加QQ: 749389476
Figure 3: Network Configuration Example
$ ./dvnode 2222 1111 .1 3333 .2 4444 .8
$ ./dvnode 3333 1111 .5 2222 .2 4444 .5
$ ./dvnode 4444 2222 .8 3333 .5 last
As soon as the command for node 4444 is entered the following process should kick in.
1. Node 4444 send its routing information to node 2222 and 3333.
2. Node 2222 and 3333 update their routing tables according to the routing information sent from node 4444. Since both node 2222 and 3333 have not sent their routing information to anyone, node 2222 sends its routing information to node 1111, 3333 and 4444. Node 3333 will send its routing information to node 1111, 2222 and 4444.
3. Node 1111 should update its routing table according to the message received either from node 2222 or 3333 whichever came first. Node 1111 will send its updated routing information to node 2222 and 3333. (At this point, all nodes have sent their routing information to their neighbors at least once.)
4. Each node will update its routing table according to the messages received from its neighbors. However, it will send messages only if its routing table is updated.
5. The process converges as each node has the most updated routing table which includes the shortest distances to all the nodes in the network and the next hop on the shortest path to each node.
Once the algorithm converges, there should be no more status messages. The last status message from the nodes will be something like (note: each node will print its own table):
[1700539210.173] Node 1111 Routing Table
– (.1) -> Node 2222
– (.3) -> Node 3333; Next hop -> Node 2222
– (.8) -> Node 4444; Next hop -> Node 2222
[1700539210.192] Node 2222 Routing Table
[1700539210.239] Node 3333 Routing Table
[1700539210.287] Node 4444 Routing Table
Programming Help, Add QQ: 749389476
4 Combination (20pt) 4.1 Description
As an ultimate goal for this assignment, both GBN and DV protocols should be implemented and take effect in the emulated network. The GBN protocol can create reliable links, and the DV algorithms should determine the shortest paths over these GBN links. For this assignment, it is only required to generate the correct routing table for each node using the two protocols. The distance of each link will be the packet loss rate on that link calculated by the GBN protocol.
4.2 Loss Rate Calculation
This is the incorporation of section 2.6, so it should not be additional work. To simplify the problem, we put some more specifications on the GBN protocol:
• Window size is always 5.
• The data packet will only be dropped in a probabilistic way. • ACK will never be dropped.
• Timeout is still 500ms.
The loss rate of each link is calculated by the following equation:
(0, (initial value) if no probe packets have been sent
Link cost = T otal number of dropped packets , otherwise T otal number of sent packets
A counter is needed for every link to get those numbers.
4.3 Probe Packets
To obtain the loss rate quickly, probe packets (data packets with any data) should be sent ”continuously” (in one direction) on all links. You should implement a sending interval. Because each link has two nodes, the user has to specify which node is the probe sender, and which node is the probe receiver. Also, the sender should only start to send probe packets when all nodes in the network have become ready. As described in Section 3, there will be a last node with the word ”last” in the arguments. Once that node is started, the DV update messages should be sent to all that last node’s neighbors, triggering the neighbors to send out DV messages as well. Therefore, the first time a node receives a DV update message, it should know that the network has become ready, and it can start sending probe packets.
4.4 Routing Information Exchange
The requirements for routing information exchange are similar to those in Section 3, except when the routing updates should be sent out to neighbors. The loss rate calculated for each link will keep changing rapidly, but you should not send updates to the network in the same frequency, as those packets would flood the entire network. For this assignment, we have the following requirements:
• The distances in the routing table should be rounded to the second demical place,
• The updates of routing table should only be sent out 1) for every 5 seconds (if there is any change in the rounded distances based on the newly calculated loss rate), or 2) when a DV update is received from a neighbor that changes the local routing table.
• The updates should be sent to all neighboring nodes, including all probe senders and receivers.
• The probe receivers will only get the calculated distance of the corresponding links through the updates sent by the probe senders.
4.5 Command Syntax
Your program in this section should be named ”cnnode” and should be started with the following command:
cnnode
ctrl+C (exit)
Again, the program name.
The UDP listening port number (1024-65534) of the node.
The current node will be the probe receiver for the following neighbors.
The UDP listening port number (1024-65534) of one of the neighboring nodes.
If you are using a different sending port number, you have to add the listening port number
to your own packet header.
The probability to drop the probe packets.
Keep listing the pair of
The current node will be the probe sender for the following neighbors.
Keep listing the pair of
The optional argument. Indication of the last node information of the network. Upon the input of the command with this argument, the routing message exchanges among the nodes should
Use ctrl+C to exit the program.
For example, to start the network shown in Figure 4: The user should use the following commands:
Figure 4: Network Configuration Example
$ ./cnnode 1111 receive send 2222 3333 (receiving list is empty)
$ ./cnnode 2222 receive 1111 .1 send 3333 4444
$ ./cnnode 3333 receive 1111 .5 2222 .2 send 4444
$ ./cnnode 4444 receive 2222 .8 3333 .5 send last (sending list is empty)
When node 4444 is started, it will send DV update (initially all with loss rate of 0) to both node 2222 and node 3333.
After receiving the DV updates, node 2222 and 3333 should both update their routing table, send out the changes, and start sending probe packets. Node 2222 will send DV update to node 1111, 3333, and 4444, and start sending probe packets to 3333 and 4444. Node 3333 will send DV update to node 1111, 2222, and 4444, and start sending probe packets to only 4444.
When node 1111 receives the DV update from either node 2222 or node 3333, it should update its own routing table, send the DV update to node 2222 and 3333, and also start sending probe packets to node 2222 and 3333. After that, there will be no more DV updates as no routing tables will be changed. All nodes have started to count and calculate the loss rate of each link. 5 seconds later, the DV updates will be sent out again and all routing tables will be updated. Note: Routing tables are ignorant of the loss rates input on the command line. The information enters the tables via the ongoing loss rate calculations.
4.7 Status Messages
The status messages should contain those in Section 3.
Also, the packet loss rate for each link should be displayed every 1 second with the following format:
[
[1700539210.259] Link to 2222: 10 packets sent, 5 packets lost, loss rate .50
Your program should deal with the following cases:
Loss Rate Distance Vector DV algorithm
The number of packets should be counted at the sender side
The loss rate calculated at the sender should vary at first but eventually converge
The routing tables should be updated periodically following the DV algorithm
The routing tables should vary at first but eventually converge to the result of Section 3
(5pt) (5pt) (5pt) (5pt)
5 Program Structure
As for PA1, the expectation is that there is an independent gbnnode , dvnode or cnnode process per node. Also as with PA1, the expectation is that you use multithreading to ensure a node is always able to listen and respond to an incoming packet. As user input is not required in the middle of program operation, a single-threaded approach is actually feasible, but you will likely find it more difficult to get it working properly.
The program structure is left for you to design and implement, but make sure you test it thoroughly.
6 Submission Instructions
Please use C/C++, Java, or Python for developing the emulation programs. You should target the same Google Cloud platform as used for PA1. You must make sure that your program compiles and runs on a Google Cloud Ubuntu 20.04 LTS instance before you submit your assignment.
Your final submission should include the following deliverables:
• README: In the README, please report the following information:
– Your packet structure, even if it is the same as the one outlined in this PDF. – An overview of the most important functions/classes implemented
– An overview of any data structures used
– Any bugs that remain in your submission
– Any additional features implemented
The README should be a text file. You will lose points if you submit a PDF, .rtf, Doxygen-generated content
or any other format.
• Makefile: This file is used to build your application. If you have written the programs in C/C++, the output file names should be gbnnode, dvnode, and cnnode. If you used Java, the file names should be gbnnode.class, dvnode.class, cnnode.class. You do not need a Makefile if you used Python, but please name your files gbnnode.py, dvnode.py, and cnnode.py.
• Your source code.
• test.txt: This file should contain some output samples on several test cases. This would help others to understand how your programs work in each test scenario. It is optional to include this, as part of your README document.
The submission should be made via Courseworks. Zip all the deliverables mentioned above, and name the zip file as
In the grading of your work, we will take the following points into account.
• The documentation clearly describes your work and the test result.
• The source code is complied properly by using the Makefile and generate appropriate output files.
• The programs run properly, including 1) take appropriate commands and arguments, 2) handle different situations and support required functions, and 3) display necessary status messages.
• The programs follow the command line formats exactly, and that the deliverables are presented in the format specified by the assignment.
Happy Coding and Good luck!!
CS Help, Email: tutorcs@163.com