[ This content is protected and may not be shared, uploaded, or distributed. ]
(Please also check out PA5 FAQ.)
Lab 14 has two parts:
Part A (lab14a) - RDT-3.0, another UDT application (useful for PA5):
In this lab, we will impmlement a TCP-like application for the 353NET.
This part of the lab is based on Section (3.4) of the textbook on the Principles of Reliable Data Transfer.
The description below will follow the slides there.
We will implement RDT-3.0
mentioned on slides 44 through 47 of the lecture slides on the Principles of Reliable Data Transfer.
This protocol is also known as the Alternating Bit Protocol.
In your implementation, you should follow the lecture slides. Since we are using TCP for our assignments, we cannot get bit errors.
Therefore, our messages will not include a checksum.
According to the state transition diagram for the sender, RDT-3.0 would create a message and calls udt_send()
to deliver the message to the destination. Therefore, we will use UCASTAPP message with a UDT payload
to deliver RDT messages. You can assume that for a UCASTAPP message, the maximum value of its "Content-Length" key is 1024
and feel free to drop any UDT payload that's more than 1024 bytes long. (Although for this lab, the maximum payload size is much smaller than that.)
In the state transition diagrams for RDT-3.0, there are only two types of messages.
One is for data and the other is for acknowledgement. For this lab, a data message (which is the message body of a UCASTAPP message)
is a multi-line message that looks like the following:
353UDT/1.0 RDTDATA\r\n
Seq-Number: SEQNUM\r\n
RDT-App-Number: APPNUM\r\n
RDT-Content-Length: CLENGTH\r\n
\r\n
CLENGTH bytes of RDT data
where SEQNUM is either 0 or 1 and APPNUM is an RDT application number.
For this part of the lab, APPNUM is 0 since we only have one "RDT receiver" (i.e., only one "RDT application",
which is just a "test application", that would receive and process RDT messages).
With TCP and UDP, you can use port numbers to demultiplex transport layer segments to applications.
For the 353NET, we don't have port numbers for RDT applications.
Instead, we use APPNUM to demultiplex data to different RDT applications.
For this part of the lab, APPNUM must be 0.
For part B of this lab, we will add two RDT application numbers so we can demultiplex
RDT messages to the correct RDT applications.
An acknowledgement message is a single-line message that looks like the following:
353UDT/1.0 RDTACK SEQNUM APPNUM
where SEQNUM is either 0 or 1 and APPNUM is an RDT application number.
You need to add a the following "rdtsend" console command to send a msg from your node
(i.e., typically referred to as SELF) to a target node:
| Name |
Arguments |
Description |
|---|
| rdtsend |
target msg |
Run the RDT-3.0 sender protocol to send msg
to target one byte at a time per second.
If the last character of msg is not "\n", you must first append a "\n" character to msg
so the receiver knows when to terminate the protocol.
For each character in msg, you must create an UCASTAPP message with
the current node's NodeID as the SRC_NODEID, target as the DEST_NODEID, and
1 as NEXT_LAYER.
(Please note that Lab 12 mentioned that NEXT_LAYER is 2 for RDT,
but since we are following the textbook and building RDT on top of UDT, NEXT_LAYER would always be 1.)
Create an RDTDATA message with an Seq-Number of 0, an RDT-App-Number of 0,
an RDT-Content-Length of 1, and the character being the
RDTDATA message body and encapsulate this RDTDATA message as the message body of an encapsulating UCASTAPP message.
Route this message towards the target and wait for an RDTACK message
with the right sequence number before moving on to the next character.
Before running this command, you must run BFS
to clean up the adjacency list since there may be unreachable nodes in your adjacency list data structure.
If target is not in the adjacency list, you must print the following to the console:
target is not reachable\n
If target is the NodeID of the node whose console you are typing into. You must print the following to the console:
Cannot use rdtsend command to send message to yourself\n
Please note that you must run BFS only once before you start running the
RDT-3.0 sender protocol.
Once you start running the RDT-3.0 sender protocol, RDT must not care if target has become unreachable or not
(i.e., for this lab, RDT cannot fail once it gets started)!
The reason for that is that RDT will simply use udt_send() to send messages. Even if udt_send()
cannot delivery a message because the destination node is unreachable, according to
our lecture slides on reliable data transfer, RDT will not know that this is happening.
Therefore, if the network becomes partitioned, RDT may keep getting timeouts and may wait indefinitely to finish the protocol.
The RDT-3.0 sender has a timer.
You must use the value of the "msg_lifetime" parameter
in the "[params]" section of the configuration file as the timeout value in your implementation of the RDT-3.0 sender.
In order to have a reasonably responsive timer, you must use the countdown technique in Lab 13
to implement the timeout mechanism (and not just simply sleep for msg_lifetime seconds in one shot).
Finally, when you are running this console command, if you get a timeout in the RDT sender, you must print the following to the console
so we can tell that you are getting timeouts:
RDT sender timeout for Seq-Number: SEQNUM and RDT-App-Number: APPNUM
where SEQNUM and APPNUM are from the RDTDATA message that got timed out.
|
You must also implement a simple RDT receiver that implements the
RDT-3.0 receiver protocol to receive RDTDATA messages and send RDTACK messages.
(To make things simple, you can just run an RDT receiver thread in your node.)
If the RDT data is new and it's the "\n" character,
since we don't have the next layer implemented yet, you must print the following in the console:
RDT message 'RDTMSGBODY' received from SRC_NODEID.
where RDTMSGBODY is the concatenated message body of RDTDATA messages that you have received so far
in the RDT-3.0 session, and
SRC_NODEID is the SRC_NODEID in the UCASTAPP messages of the RDT-3.0 session.
For this part of the lab, if the RDT data is the "\n" character, after you send an RDTACK message back to the sender,
you must reset the RDT receiver to the initial state (i.e., go to the "wait for 0 from below state").
In order to be able to see what's going on, you must log UCASTAPP messages to cout a little differently for this lab.
Recall that in Lab 12, the general format for a log entry looks like the following:
[TIMESTAMP] {r|i|d|f} MSGTYPE NEIGHBOR TTL FLOOD CONTENT_LENGTH msg-dependent-data\n
and for a UCASTAPP message, the "msg-dependent-data" must look like the following:
MSGID SRC_NODEID DEST_NODEID NEXT_LAYER MSGBODY
where MSGBODY is the message body of the UCASTAPP message (exactly CLENGTH bytes of data).
We will use the same format for a single-line message.
For an RDTDATA message, which is a multi-line message,
the "msg-dependent-data" must look like the following:
MSGID SRC_NODEID DEST_NODEID 2 SEQNUM APPNUM CLENGTH RDTMSGBODY
where SEQNUM is the value for the "Seq-Number" key,
APPNUM is the value for the "RDT-App-Number" key (although you must print a "-" if the corresponding value is 0 to make it stands out),
CLENGTH is the value for the "RDT-Content-Length" key (which should always be 1),
and RDTMSGBODY is the message body of the RDTDATA message (exactly CLENGTH bytes of data).
For this part of the lab, since CLENGTH is always 1, RDTMSGBODY should always be a single character.
There is a special case that you need to handle in a special way; otherwise, the printout can look like it has gaps.
If CLENGTH is 1 and RDTMSGBODY is the '\n' character, instead of logging the '\n' character,
please log the "\\n" string (so it looks like "\n" and not an extra empty line in the log).
Please note that instead of logging the actual NEXT_LAYER in a UCASTAPP message
(which is always 1), as in the case for a single-line RDT message,
we will always use the number 2 in the place where NEXT_LAYER is logged for a multi-line RDT message.
(Originally, I was thinking about setting Next-Layer to be 2 for RDT messages.
Then I realized that our lectures have RDT-3.0 runs on top of UDT, and therefore, it makes more
sense to not have RDT as a possible Next-Layer.)
The log messages are getting really long!
To make it shorter, you can use the following short-hand notations for log messages (this is not a requirement).
The date part of a TIMESTAMP is not very useful since we don't run our programs for days. You can skip the first 16 characters in TIMESTAMP
(so it starts with hours). MSGID (obtained from GetObjID())
is of the format "*_NUMBER_*". Although you need the entire MSGID for the message cache
to function correctly, you only need the NUMBER part in the printout so you can match things up.
You can write a funciton to extract the NUMBER in the MSGID and just put a pair of parentheses around it and print (NUMBER)
and not print the entire MSGID.
It's important to use the parentheses so we can easily identify it as being a MSGID.
I would recommend that you write a function called rdt_send() to send a line of text reliably to a target node using
RDT-3.0. This can make things easier when you need to implement the next part of this lab.
Although rdt_send() and udt_send() can both be used to send a line of text, the main differences between them are:
- rdt_send() provides reliable data delivery (i.e., when rdt_send() returns, you know that
the entire line of text has been successfully delivered to the target node; while udt_send() does not
(i.e., when udt_send() returns, you have no idea if the line of text has been delivered to the target node or not
- rdt_send() sends data one byte at a time (one byte of application data in each UCASTAPP message)
and wait for an acknowledgement after each byte while udt_send() simply sends that line of text in one UCASTAPP message
I would also recommend that you create an object to keep track of the state of an RDT-3.0 session.
On the sender side, in a sender session, the sender sends a single line of text (terminated by the '\n' character).
On the receiver side, in a receiver session, the receiver receives a single line of text (terminated by the '\n' character).
Since the information being kept at the sender and at the receiver is very similar, we can use the same object.
Here's what it might look like (from slides 45 and 47 of the lecture slides on reliable data transfer):
class RDT30_State {
public:
string peer_nodeid; /* who you are running RDT-3.0 with */
int seq_no; /* 0 or 1 */
int app_no; /* 0 for now */
string sndpkt; /* return from make_pkt() */
string msg_received; /* received from peer so far */
};
Please note that for the sender session, sndpkt is a data "packet" (on slide 45 of reliable data transfer),
while for the receiver session, sndpkt is an ACK "packet" (on slide 47 of reliable data transfer).
You can add more things to it if you need to keep track of more information in your implementation of RDT-3.0.
Since it's possible for multiple source nodes to send different RDT messages to the same destination node,
on the receiver side, you need to have a list of RDT30_State object to keep track of the states of multiple RDT-3.0 receiver sessions.
When you have received an RDT message, you should use SRC_NODEID in the UCASTAPP message
to lookup the corresponding RDT30_State object (and match it against peer_nodeid).
If lookup failed, you should create a new RDT receiver session and create an RDT30_State object and add it to the list.
Please do the following:
- Create an empty directory (call it "lab14") and change directory into it.
- Download lab14data.tar.gz into that directory and type:
tar xvf lab14data.tar.gz
This should create a subdirectory called "lab14data" with several .ini files in it
which we will use as configuration files for our nodes.
The usage information (i.e., commandline syntax) for "lab14a" is as follows:
lab14a CONFIGFILE
where CONFIGFILE is a configuration file similar to the ones that was used in Lab 13.
The only difference is that the value for the "msg_lifetime" parameter for this lab is 6.
When you are done with implementing lab14a, please do the following:
- Change directory into the "lab14" directory mentioned above.
- Open 3 Terminals and change directory into the same directory.
- In the first Terminal window, type "script lab14a-12000.script" to start a transcript.
- In the 2nd Terminal window, type "script lab14a-12002.script" to start another transcript.
- In the 3rd Terminal window, type "script lab14a-12004.script" to start another transcript.
- In the first Terminal window, type:
uname -a
cat /etc/os-release
make clean
make lab14a
./lab14a lab14data/lab14-12000.ini
- In the 2nd Terminal window, type "./lab14a lab14data/lab14-12002.ini".
- In the 3rd Terminal window, type "./lab14a lab14data/lab14-12004.ini".
- Your network should look like the following (from the configuration files):
+-------+ +-------+ +-------+
| 12000 +---+ 12002 +-----+ 12004 |
+-------+ +-------+ +-------+
- Type "netgraph" and "forwarding" in all windows to make sure that they all agree on the same network topology
and all the forwarding tables look correct.
- In the first window (where you are running :12000), type "rdtsend :12000 hello" and you should see:
Cannot use rdtsend command to send message to yourself
- In the first window, type "rdtsend :12012 hello" and you should see:
:12012 is not reachable
- Test case #1: one sender, receiver is neighbor, no failure
- In the 1st window, type "rdtsend :12002 hello" and you should see that it's initiating one message every second.
- In the 1st window, you should see the following printout:
[TIMESTAMP] i UCASTAPP :12002 9 - 80 MSGID1 :12000 :12002 2 0 - 1 h
[TIMESTAMP] r UCASTAPP :12002 9 - 21 MSGID2 :12002 :12000 1 353UDT/1.0 RDTACK 0 0
[TIMESTAMP] i UCASTAPP :12002 9 - 80 MSGID3 :12000 :12002 2 1 - 1 e
[TIMESTAMP] r UCASTAPP :12002 9 - 21 MSGID4 :12002 :12000 1 353UDT/1.0 RDTACK 1 0
...
[TIMESTAMP] i UCASTAPP :12002 9 - 80 MSGID5 :12000 :12002 2 0 - 1 o
[TIMESTAMP] r UCASTAPP :12002 9 - 21 MSGID6 :12002 :12000 1 353UDT/1.0 RDTACK 0 0
[TIMESTAMP] i UCASTAPP :12002 9 - 80 MSGID7 :12000 :12002 2 1 - 1 \n
[TIMESTAMP] r UCASTAPP :12002 9 - 21 MSGID8 :12002 :12000 1 353UDT/1.0 RDTACK 1 0
rdtsend: 'hello' to :12002 have been sent and acknowledged
Please also note that the log entries for RDTDATA messages uses "-" for APPNUM of 0,
while the log entries for RDTACK messages do not because the replacement only needs to be done for RDTDATA messages.
- In the 2nd window, you should see the following printout:
[TIMESTAMP] r UCASTAPP :12000 9 - 80 MSGID1 :12000 :12002 2 0 - 1 h
[TIMESTAMP] i UCASTAPP :12000 9 - 21 MSGID2 :12002 :12000 1 353UDT/1.0 RDTACK 0 0
[TIMESTAMP] r UCASTAPP :12000 9 - 80 MSGID3 :12000 :12002 2 1 - 1 e
[TIMESTAMP] i UCASTAPP :12000 9 - 21 MSGID4 :12002 :12000 1 353UDT/1.0 RDTACK 1 0
...
[TIMESTAMP] r UCASTAPP :12000 9 - 80 MSGID5 :12000 :12002 2 0 - 1 o
[TIMESTAMP] i UCASTAPP :12000 9 - 21 MSGID6 :12002 :12000 1 353UDT/1.0 RDTACK 0 0
[TIMESTAMP] r UCASTAPP :12000 9 - 80 MSGID7 :12000 :12002 2 1 - 1 \n
RDT message 'hello' received from :12000
[TIMESTAMP] i UCASTAPP :12002 9 - 21 MSGID8 :12002 :12000 1 353UDT/1.0 RDTACK 1 0
The last 2 lines may be reversed. It depends on your implementation.
- Test case #2: one sender, receiver is 2 hops away, no failure
- In the 1st window, type "rdtsend :12004 howdy" and you should see that it's initiating one message every second.
- In the 1st window, you should see the following printout:
[TIMESTAMP] i UCASTAPP :12002 9 - 80 MSGID1 :12000 :12004 2 0 - 1 h
[TIMESTAMP] r UCASTAPP :12002 8 - 21 MSGID2 :12004 :12000 1 353UDT/1.0 RDTACK 0 0
[TIMESTAMP] i UCASTAPP :12002 9 - 80 MSGID3 :12000 :12004 2 1 - 1 o
[TIMESTAMP] r UCASTAPP :12002 8 - 21 MSGID4 :12004 :12000 1 353UDT/1.0 RDTACK 1 0
...
[TIMESTAMP] i UCASTAPP :12002 9 - 80 MSGID5 :12000 :12004 2 0 - 1 y
[TIMESTAMP] r UCASTAPP :12002 8 - 21 MSGID6 :12004 :12000 1 353UDT/1.0 RDTACK 0 0
[TIMESTAMP] i UCASTAPP :12002 9 - 80 MSGID7 :12000 :12004 2 1 - 1 \n
[TIMESTAMP] r UCASTAPP :12002 8 - 21 MSGID8 :12004 :12000 1 353UDT/1.0 RDTACK 1 0
rdtsend: 'howdy' to :12004 have been sent and acknowledged
- In the 2nd window, you should see the following printout [BC: fixed 4/16/2023]:
[TIMESTAMP] r UCASTAPP :12000 9 - 80 MSGID1 :12000 :12004 2 0 - 1 h
[TIMESTAMP] f UCASTAPP :12004 8 - 80 MSGID1 :12000 :12004 2 0 - 1 h
[TIMESTAMP] r UCASTAPP :12004 9 - 21 MSGID2 :12004 :12000 1 353UDT/1.0 RDTACK 0 0
[TIMESTAMP] f UCASTAPP :12000 8 - 21 MSGID2 :12004 :12000 1 353UDT/1.0 RDTACK 0 0
[TIMESTAMP] r UCASTAPP :12000 9 - 80 MSGID3 :12000 :12004 2 1 - 1 o
[TIMESTAMP] f UCASTAPP :12004 8 - 80 MSGID3 :12000 :12004 2 1 - 1 o
[TIMESTAMP] r UCASTAPP :12004 9 - 21 MSGID4 :12004 :12000 1 353UDT/1.0 RDTACK 1 0
[TIMESTAMP] f UCASTAPP :12000 8 - 21 MSGID4 :12004 :12000 1 353UDT/1.0 RDTACK 1 0
...
[TIMESTAMP] r UCASTAPP :12000 9 - 80 MSGID5 :12000 :12004 2 0 - 1 y
[TIMESTAMP] f UCASTAPP :12004 8 - 80 MSGID5 :12000 :12004 2 0 - 1 y
[TIMESTAMP] r UCASTAPP :12004 9 - 21 MSGID6 :12004 :12000 1 353UDT/1.0 RDTACK 0 0
[TIMESTAMP] f UCASTAPP :12000 8 - 21 MSGID6 :12004 :12000 1 353UDT/1.0 RDTACK 0 0
[TIMESTAMP] r UCASTAPP :12000 9 - 80 MSGID7 :12000 :12004 2 1 - 1 \n
[TIMESTAMP] f UCASTAPP :12004 8 - 80 MSGID7 :12000 :12004 2 1 - 1 \n
[TIMESTAMP] r UCASTAPP :12004 9 - 21 MSGID8 :12004 :12000 1 353UDT/1.0 RDTACK 1 0
[TIMESTAMP] f UCASTAPP :12000 8 - 21 MSGID8 :12004 :12000 1 353UDT/1.0 RDTACK 1 0
- In the 3rd window, you should see the following printout:
[TIMESTAMP] r UCASTAPP :12002 8 - 80 MSGID1 :12000 :12004 2 0 - 1 h
[TIMESTAMP] i UCASTAPP :12002 9 - 21 MSGID2 :12004 :12000 1 353UDT/1.0 RDTACK 0 0
[TIMESTAMP] r UCASTAPP :12002 8 - 80 MSGID3 :12000 :12004 2 1 - 1 o
[TIMESTAMP] i UCASTAPP :12002 9 - 21 MSGID4 :12004 :12000 1 353UDT/1.0 RDTACK 1 0
...
[TIMESTAMP] r UCASTAPP :12002 8 - 80 MSGID5 :12000 :12004 2 0 - 1 y
[TIMESTAMP] i UCASTAPP :12002 9 - 21 MSGID6 :12004 :12000 1 353UDT/1.0 RDTACK 0 0
[TIMESTAMP] r UCASTAPP :12002 8 - 80 MSGID7 :12000 :12004 2 1 - 1 \n
RDT message 'howdy' received from :12000
[TIMESTAMP] i UCASTAPP :12002 9 - 21 MSGID8 :12004 :12000 1 353UDT/1.0 RDTACK 1 0
The last 2 lines may be reversed. It depends on your implementation.
- Test case #3: two senders, receivers are 2 hops away, no failure
- Type the next two commands as quickly as you can:
- In the 1st window, type "rdtsend :12004 good-day"
- In the 3rd window, type "rdtsend :12000 bye-bye"
- Wait for both senders and receivers to finish.
- In the 1st window, should eventually see (if you ignore all the log messages):
RDT message 'bye-bye' received from :12004
rdtsend: 'good-day' to :12004 have been sent and acknowledged
The order does not matter since it depends on timing.
- In the 3rd window, should eventually see (if you ignore all the log messages):
rdtsend: 'bye-bye' to :12000 have been sent and acknowledged
RDT message 'good-day' received from :12000
The order does not matter since it depends on timing.
- Test case #4: one sender, receiver is 2 hops away, middle node failed and restarted
- In the 1st window, type "rdtsend :12004 hold-on"
- After 1 second, type "quit" in the 2nd window to partition the network.
- In the 1st window, should see timeouts that looks like the following every 6 seconds:
RDT sender timeout for Seq-Number: ? and RDT-App-Number: 0
The "?" can be a 0 or a 1. Where the timeout messages appear and whether you should see a sequence number of 0 or 1 depends
on exactly when you type "quit" in the 2nd window.
- Wait to see at least 3 timeout messages.
- In the 2nd window, type "./lab14a lab14data/lab14-12002.ini" to restart :12002.
- In the 1st window, should eventually see (if you ignore all the log messages):
rdtsend: 'hold-on' to :12004 have been sent and acknowledged
- In the 3rd window, should eventually see (if you ignore all the log messages):
RDT message 'hold-on' received from :12000
- Test case #5: two senders, receiver is 2 hops away, middle node failed and restarted
- Type the next two commands as quickly as you can:
- In the 1st window, type "rdtsend :12004 left-right"
- In the 3rd window, type "rdtsend :12000 high-low"
- After 1 second, type "quit" in the 2nd window to partition the network.
- In the 1st and 3rd windows, should see timeouts every 6 seconds. Wait to see at least 3 timeout messages in both windows.
- In the 2nd window, type "./lab14a lab14data/lab14-12002.ini" to restart :12002.
- In the 1st window, should eventually see (if you ignore all the log messages):
RDT message 'high-low' received from :12004
rdtsend: 'left-right' to :12004 have been sent and acknowledged
The order does not matter since it depends on timing.
- In the 3rd window, should eventually see (if you ignore all the log messages):
rdtsend: 'high-low' to :12000 have been sent and acknowledged
RDT message 'left-right' received from :12000
The order does not matter since it depends on timing.
- Test case #6: two senders, same receiver, no failure
- Type the next two commands as quickly as you can:
- In the 1st window, type "rdtsend :12002 left"
- In the 3rd window, type "rdtsend :12002 right"
- In the 1st window, should eventually see (if you ignore all the log messages):
rdtsend: 'left' to :12002 have been sent and acknowledged
- In the 2nd window, should eventually see (if you ignore all the log messages):
RDT message 'left' received from :12000
RDT message 'right' received from :12004
The order does not matter since it depends on timing.
- In the 3rd window, should eventually see (if you ignore all the log messages):
rdtsend: 'right' to :12002 have been sent and acknowledged
- Type "quit" in all 3 windows.
- In the 3rd Terminal window, type the following to display all the log files (to see that SAYHELLO and LSUPDATE messages are properly logged):
more lab14data/*.log
- Type "exit" in all 3 windows to close the transcripts.
To save typing all some of the commands above, a tmux script, "tmux-lab14a.txt" is provided
in the "lab14data" directory created above and you can run it by typing:
lab14data/tmux-lab14a.txt
Plesae note that it's provided for your convenience (i.e., to save typing) and it may not be exactly the same as the above sequence.
Please see PA2 FAQ regarding how to use tmux in general.
Part B (lab14b) - echo server and client, RDT-3.0 applications (useful for PA5):
In Part A of this lab,
you have implemented a simple RDT receiver to buffer characters it has received in the transport layer.
There was no application layer in Part A of this lab.
When this simple RDT receiver receives a "\n", it simply prints out the line in the buffer on its console and delete the buffer.
In this part of the lab, you will implement two application in the application layer so that the transport layer
can deliver RDT messages to these applications. This is where demultiplexing need to happen.
Each application has its own work queue. When the transport layer has received a full RDT message, it needs to demultiplex
the message by deciding into which work queue to add the RDT message. The two applications you will implement need to behave
similar to the echo server and the echo client in Part D of Lab 3.
For this lab, the echo client sits in an infinite loop to wait for the user to enter a line of text.
It then sends that line of text to the echo server (using rdt_send() developped in Part A above)
and waits for the echo server to echo the line back (the echo server also uses rdt_send() to echo a line of text back to the client).
If the echoed line is an empty line, the echo client self-terminates. Otherwise, it print the echoed line to cout and go back
to the top of the loop to wait for the user to enter another line of text. Below are more details.
Please note that your echo server must not echo characters back to the source node on-the-fly (i.e., when it's receiving these characters
one at a time). The echo server application must buffer the entire line.
When an entire line is received (i.e., when it sees the '\n' character in the message),
it then use RDT-3.0 to send the entire line one character at a time reliably back to the echo client.
The reason for this requirement is that we must not implement the echo server in the "transport layer" of the 353NET;
we must implement the echo server in the "application layer" of the 353NET. Although you don't have to explicitly implement an application "layer",
conceptually, you need to separate the transport layer from the application layer and that's
the whole point of this part of the lab and PA5!
Your echo client (which will also be referred to as an echoapp)
will be similar to the echo client in part D of Lab 3,
but you must not make a TCP connection directly to the echo server.
Instead, you must use RDT-3.0 to send an entire line of text one character at a time reliably to the echo server and
use RDT-3.0 to receive an entire echoed line from the echo server one character at a time reliably.
By reliably, I mean even under network partitioning.
You need to add a the following console command to run an echo client application interactively:
| Name |
Arguments |
Description |
|---|
| echoapp |
target |
In a loop, prompt the user for a line of text and send it to target (the line of text you send must end with a "\n" character),
wait for the message to be echoed back from target, print the echoed line of text to the console, and then go back to the top of the loop.
If the echoed line is an empty line (i.e., only containing a "\n" character), you must terminate this command,
and your console should go back to print its usual prompt. Please see the echoapp pseudo-code for details.
When you are running the echoapp, the prompt you must use is "echoapp> " (there is a space character after the ">" character).
If the user enters a line of text that's longer than 40 characters, you must print:
line too long (40 characters max); please try again\n
Otherwise, use RDT-3.0 you developed in Part A of this lab to send the line to target
one character at a time using 98 as the APPNUM (you are still required to send at a maximum speed of one character per second).
Before running this command, you must run BFS
to clean up the adjacency list since there may be unreachable nodes in your adjacency list data structure.
If target is not in the adjacency list, you must print the following to the console:
target is not reachable\n
If target is the NodeID of the node whose console you are typing into. You must print the following to the console:
Cannot use echoapp command to send message to yourself\n
Similar to the rdtsend console command, once you start running this command,
echoapp will not know whether target has become unreachable or not.
If target become unreachable, RDT may wait indefinitely to finish the protocol.
Similar to the rdtsend console command, whenever you get a msg_lifetime timer timeout,
you must print the following to the console:
RDT sender timeout for Seq-Number: SEQNUM and RDT-App-Number: APPNUM
|
I would recommend that you write a function called rdt_receive_a_line(target,app_no)
to receive a line of text from target with RDT-App-Number equaling app_no (also referred to as APPNUM above)
and use it to implement the echoapp (i.e., echo client).
Please take a look at the echo client pseudo-code to see how the echoapp can be implemented.
In the pseudo-code, the echo client prompts the user for a line of text, then
call rdt_send() to send that line of text to target.
Then call rdt_receive_a_line(target,99) mentioned above to receive a line of text from an RDT application
with APPNUM 99 running on the target node.
When rdt_receive_a_line() returns, print the echoed line to the console if it's not an empty line, then prompt the user for another line of text.
One important aspect of this lab is that you now have two RDT receivers. One is the "echo server" that runs in every node
(you can implement it explicitly by running another thread in your node, or implicitly by modifying the code in your
RDT receiver thread).
Another RDT receive is the echoapp because after sending a line of text, it needs to
receive a line from target. Both of these RDT receivers will receive RDTDATA messages and they all look exactly the same.
How can RDT figure out which RDT receiver should receive an RDTDATA message? Or, how would you demultiplex?
For TCP and UDP, they use port numbers to demultiplex (recall that a "source-destination flow" in the Internet
is identified by a <src_ip,src_port,dest_ip,dest_port> 4-tuple).
For 353NET, we would use a <src_nodeid,src_appnum,dest_nodeid> 3-tuple to identify a "source-destination flow".
Why don't we need a dest_appnum? Well, because it's implied in a toy network like 353NET.
For 353NET, if src_appnum is the echo client/app (i.e., APPNUM=98), we must assume that dest_appnum refers to the echo server,
and if src_appnum is the echo server (i.e., APPNUM=99), we must assume that dest_appnum refers to the echo client/app.
Also, if src_appnum is 0, we must assume that dest_appnum refers to the test application in Part A of this lab.
For this part of the lab, you must use a value of 98 for an echo request message (i.e., sent by an echo client/app) and
a value of 99 for an echo response message (i.e., sent by an echo server).
To implement demultiplexing for this part of the lab, you need to use the app_no field in the RDT30_State object
(this information came from APPNUM in the message).
For this part of the lab, when you have received an RDT message, you should use both the SRC_NODEID in the UCASTAPP message and
the APPNUM to lookup the corresponding RDT30_State object (i.e., use the <src_nodeid,src_appnum,dest_nodeid> 3-tuple to
identify a "source-destination flow").
Please remember that pretty much the only way threads in your node can "communicate" with each other is to
use a work queue! Therefore, when your socket-reading thread wants to deliver an RDT message to
another thread, your socket-reading thread would create some type of a "work" object
and call some sort of an add_work() function while another thread would call a corresponding wait_for_work() function to receive this "work" object.
Also, you should use anything that can distinguish one receiver from another.
In previous labs, we saw that you can demultiplex based on 353NET message types, UDT message types, ORIGIN_NODEID, etc.
Now we have RDT messages, therefore, you can also use RDT message types, SRC_NODEID, and APPNUM to demultiplex.
When you are done with implementing lab14b, please do the following:
To save typing all some of the commands above, a tmux script, "tmux-lab14b.txt" is provided
in the "lab14data" directory created above and you can run it by typing:
lab14data/tmux-lab14b.txt
Plesae note that it's provided for your convenience (i.e., to save typing) and it may not be exactly the same as the above sequence.
Please see PA2 FAQ regarding how to use tmux in general.
All pseudo-code is incomplete and error checking is often left out in pseudo-code.
Since some details are left out, depending on you how write your code, you may create race conditions
and you may need to fix your code so that your program won't freeze or crash.
Feel free to send your questions (and not your code) to the instructor.
This is basically the pseudo-code for rdt_send().
Let's say that you are sending a string s of length N with the last character being "\n" to the target node.
The pseudo-code for the RDT sender should look like the following (please note that the pseudo-code is not necessarily complete):
The code is derived from slide 45 of the lecture slides on the Principles of Reliable Data Transfer.
Please note that you must run BFS only once before you get here (i.e., the target
node is considered reachable at the beginning of this code but may later become unreachable).
[ 1] seq_no = 0
[ 2] for (i=0; i < N; i++) {
[ 3] start_time = gettimeofday();
[ 4] data_packet = make_data_pkt(seq_no,s[i])
[ 5] udt_send(target,data_packet)
[ 6] start msg_lifetime timer
[ 7] done_waiting = false
[ 8] while (!done_waiting) do
[ 9] wait for response or timeout
[10] if (response is RDTACK) then
[11] if (response.seq_no == seq_no) then
[12] cancel timer
[13] done_waiting = true
[14] end-if
[15] else if (msg_lifetime timer expires) then
[16] print timeout message
[17] join with timer thread
[18] udt_send(target,data_packet)
[19] start msg_lifetime timer
[20] end-if
[21] end-while
[22] join with timer thread
[23] now = gettimeofday()
[24] elapsed_time = now -start_time
[25] if (elapsed_time < 1 sec) then
[26] usleep(1 sec - elapsed_time)
[27] end-if
[28] seq_no = !seq_no
[29] }
[30] print finished message
Please note that the code between lines [23] and [27] is to ensure that the string is sent at the maximum speed of one character per second.
(And please don't forget that the argument to usleep() on line [26] must be an integer in the unit of microseconds.)
Although the above code is mainly for part A of this lab, please maintain this maximum sending rate for the rest of this lab and PA5.
In line [30] above, you must print the following to the console:
rdtsend: 'MSG' to TARGET have been sent and acknowledged\n
where MSG is the string (without the trailing "\n") you are sending and TARGET is the node ID of the target node.
Please note that this requirement is only for Part A of this lab). For Part B of this lab,
since APPNUM will not be 0, you can use that information to skip line [30] above.
Please note that when a node is running the rdtsend console command, its console must not respond to any other console commands.
The code above is mainly for Part A of this lab.
For Part B of this lab, it becomes possible to have multiple concurrent RDT senders and you need to make some modifications.
On line [9] above, when you were waiting for either an RDTACK message or a timeout event, you need to make sure that
the correct RDTACK message gets delivered to the correct RDT receiver and the correct timeout event gets delivered to the correct RDT receiver!
Therefore, when you got an RDTACK from the lower level of the protocol stack, you must look at both SRC_NODEID and APPNUM to
deliver/demultiplex it to the correct RDT sender.
This would also mean that each RDT sender should have its own CV and mutex (and this would be a 2nd-level mutex similar to the one inside a Connection object).
An alternative way of doing this is for these RDT senders to share the same work queue and write a slighly
more sophisticated wait_for_work() function to search the work queue for the work for a particular RDT sender. In this case, one way to go about this
is to have wait_for_work() return NULL if the only work in the work queue is for other RDT senders and you need to make sure that you handle this case correctly.
(Another way is noto to return under this condition.)
In previous labs, when wait_for_work() returns NULL, it was treated as a signal to ask a thread to self-terminate.
If you take this 2nd approach, then you need to handle this case correctly (and have ways to make sure that the thread can always self-terminate properly).
If you use a timer reaper thread to join with dead timer threads, then you must not attempt to join with a timer thread anywhere else in your code
(such as in the pseudo-code above and you should probably modify the structure of the pseudo-code).
Below is the pseudo-code for a RDT receiver (as usual, pseudo-code is not necessarily complete).
Please note that your actual code may not look like this at all
and you need to organize your code to implement the essence depicted in the pseudo-code.
This code is derived from slide 47 ("rdt3.0 Receiver") of the lecture slides on the Principles of Reliable Data Transfer.
Please also note that your RDT receiver needs to be able to handle multiple senders simultaneously.
Therefore, the code below is for data coming from a particular SRC_NODEID.
When you have just received the first RDT message for a RDT-3.0 session,
you would be at step [2] of the code below.
When you have received a subsequent RDT message for an already-exist RDT-3.0 session,
you would be at step [20] of the code below.
[ 1] msg_rcvd = ""
[ 2] data_packet = rdt_rcv()
[ 3] seq_no = data_packet.seq_no
[ 4] establish session/state information for SRC_NODEID
[ 5] ack_packet = make_ack_pkt(seq_no)
[ 6] do-forever
[ 7] if (data_packet.seq_no == seq_no) then
[ 8] if (data_packet.data != "\n") then
[ 9] msg_rcvd += data_packet.data
[10] end-if
[11] ack_packet = make_ack_pkt(seq_no)
[12] udt_send(data_packet.src,ack_packet)
[13] if (data_packet.data == "\n") then
[14] break out of infinite loop
[15] end-if
[16] seq_no = !seq_no
[17] else
[18] udt_send(data_packet.src,ack_packet)
[19] end-if
[20] data_packet = rdt_rcv()
[21] end-do
[22] deliver msg_rcvd to application or print msg_rcvd
[23] delete session/state information for SRC_NODEID
Please note that rdt_rcv() on lines [2] and [20] is to delivery a single byte of application data.
Therefore, it is not the same as the rdt_receive_a_line() function mentioned earlier in this lab.
rdt_rcv() is from slides 45 through 47 of the lecture slides on the Principles of Reliable Data Transfer
(and it was first mentioned on slide 5 on that set of lecture slides).
On line [22] above, for Part A of this lab, since there is no RDT receiver for APPNUM 0, you must print the following to the console:
RDT message 'RDTMSGBODY' received from SRC_NODEID\n
where RDTMSGBODY is the msg_rcvd in the above pseudo-code.
Please note that this requirement is only for Part A of this lab). For Part B of this lab,
since APPNUM will not be 0, you can use that information to skip line [22] above.
The above pseudo-code is for an RDT receiver to handle messages from a particular SRC_NODEID.
It starts when the first RDTDATA message was received from SRC_NODEID.
Even though the first RDTDATA message is supposed to have a sequence number of 0, since a node can be restarted without
the sender knowing it, it is possible that the first RDTDATA message seen by the receiver will have a sequence number of 1.
Line [3] above addresses this problem (so our pseudo-code is slightly different from the lecture slide).
From the above, it should be clear that if a node is restarted, it is possible to "drop" earlier RDTDATA messages since you cannot go back in time.
Does this mean that our "reliable data transfer" protocol is not "reliable"? Not really. It's reliable once the sender and
the receiver are synchronized. We may drop the first message due to synchronization problem because we have not implemented a 3-way handshake (i.e., RDT is not TCP).
If you are interested in implementing TCP-like functionalities, you should give it a try (by adding SYN to start with) after the semester is over.
Please note that the above code is written as if it's the first procedure of a thread. For Part A of this lab, there is
no requirement that you implement the above in a separate thread (or one thread for each SRC_NODEID).
Whenever you get an RDTDATA message (this can be done in your socket-reading thread),
you need to execute part of the above code as if you have just returned from rdt_rcv().
The pseudo-code for the echoapp (when the user types the "echoapp target" console command)
looks like the following (please note that the pseudo-code is not necessarily complete):
The code is based on Part D of Lab 3.
[ 1] do-forever
[ 2] line = prompt the user for a line of text
[ 3] rdt_send(target,line,98)
[ 4] echoed_line = rdt_receive_a_line(target,99)
[ 5] if echoed_line is an empty line then
[ 6] break
[ 7] else
[ 8] print message about echoed_line
[ 9] end-if
[10] end-do
[11] print message
On line [3] above, you must use 98 as the RDT-App-Number (to mean that it's from an echo client)
and use RDT-3.0 to send line to the target node one character at a time.
On line [4] above, it's important to specify 99 as the RDT-App-Number because,
as an echo client, you are only interested in echo response messages coming from the target echo server (and not echo request messages).
This is because the target node may also be running an echoapp that's sending you a line of text
(those messages will have 98 as their RDT-App-Number) and you must deliver that line of text to the echo server
running on your node and not here (i.e., you must demultiplex correctly using a combined key of SRC_NODEID and APPNUM).
Please note that the echo client presented above runs inside the console thread and it is not a separate thread.
It simply picks up lines of messages from an RDT receiver demultiplexed from the RDT layer on line [4].
When a message is not fully formed (i.e., have not received a "\n" character), rdt_receive_a_line() stays blocked.
When a message is fully formed (i.e., have received a "\n" character), rdt_receive_a_line() will return to deliver a line of message.
Therefore, rdt_receive_a_line() should be implemented as some sort of a wait_for_work() function while the corresponding add_work()
function is called when a complete line has been received by an RDT receiver.
On line [8] above, you must print the following to the console:
echoed 'MSG' received from target\n
where MSG is the echoed line received from the target node.
On line [11] above, you must print the following to the console:
echoapp: terminated\n
Don't forget to give the console prompt to let the user know that your node is ready for the next console command.
The pseudo-code for the echo server would look like the following (please note that the pseudo-code is not necessarily complete):
The code is based on Part D of Lab 3.
[ 1] do-forever
[ 2] job = rdt_accept(*,98)
[ 3] if (job == NULL) then
[ 4] break;
[ 5] end-if
[ 6] lock mutex
[ 7] create thread to work on job
[ 8] add job to job list
[ 9] unlock mutex
[10] end-do
The job of an echo server is to receive a line of text from an echoapp and echo the line back.
When a line is received from an echoapp, the echo server will return from line [2] above with
a EchoJob object that describes what needs to be done. A EchoJob object may look like the following:
class EchoJob {
public:
int job_number; /* sequence number -- may not be useful */
string peer_nodeid; /* which node you are running RDT-3.0 with */
int app_no; /* 98 or 99 */
string message; /* the line you are supposed to echo back */
shared_ptr thread_ptr; /* the thread that's working on this job */
};
The app_no field should always be 98 if the EchoJob is returned by rdt_accept(*,98).
What is rdt_accept(*,98) anyway? It's simply rdt_receive_a_line(*,98)!
Maybe the right thing to do is to have rdt_receive_a_line() return an EchoJob even in the echoapp pseudo-code
so that the echo client and the echo server can call the same function and use the same object type.
On line [7] above, you create a thread to work on the job by running the RDT-3.0 protocol to echo the message
back to the sender one character at a time (i.e., this thread would simply call rdt_send(job.peer_nodeid,job.message,99)).
Since this can take a long time, if you don't create a thread to echo the message,
your echo server will not be able to communicate with multiple echoapps in parallel!
This should sound very familiar because this is what you are doing in your main thread! rdt_accept() in the above code is kind of like
my_accept(), a EchoJob object is like a Connection object, and a job list is like the connection list!
This also means that you should have a job reaper thread to reap dead job threads.
Here's another perspective... If you compare the pseudo-code above with the echo server code of Lab 3,
then EchoJob would be analogous to a socket file descriptor! Why would that make sense? It's because one of the main purpose of a socket
is for demultiplexing, as described in section (3.1) of the textbook. So, you can think of the job_number insde the EchoJob
as a socket file descriptor that you can used to search for a particular EchoJob in a list of shared pointers to EchoJobs.
(Although I should point out that a TCP socket is bi-directional while our EchoJob is uni-directional.)
It's probably a good idea to implement your echo server as a separate thread.
[ Please ignore this section since we will not grade this lab. Please do not make a submission. ]
Below is the grading breakdown:
- (1 pt) submitted a valid lab14.tar.gz file with all the required files using the submission procedure below
- (1 pt) content in "lab14a-12000.script",
"lab14a-12002.script", and
"lab14a-12004.script" are correct
- (1 pt) content in "lab14b-12000.script",
"lab14b-12002.script", and
"lab14b-12004.script" are correct
- (1 pt) "Makefile" works for "make lab14a" and "make lab14b"
- (1 pt) source code of your server program looks right
Minimum deduction is 0.5 pt for anything that's incorrect.
Please note that for the " Makefile" item, you can only get credit for it if your "source code" is relevant to this lab; therefore, you can only get as many points as the "source code" item
in the best case.
Please keep in mind that even though lab grading is "light", it doesn't mean that you can just put anything
into your submission! It's still your responsibility to make sure that the files in your submission contains
information that's relevant to the tests you were supposed to run.
Use the "more" command to view your script/log files to make sure that they contain the right information.
If a file has the wrong stuff in it, you should delete it and create the file again and verify.
If most of the stuff in your script/log files are wrong and you did not notice it, we will most likely have to take points off.
[ Please ignore this section since we will not grade this lab. Please do not make a submission. ]
To submit your work, you must first tar all the files you want to submit into a tarball and
gzip it to create a gzipped tarfile named "lab14.tar.gz".
Then you upload "lab14.tar.gz" to our Bistro submission server.
Change into the "lab14" directory you have created above and enter the following command
to create your submission file "lab14.tar.gz" (if you don't have any ".h" files, don't include "*.h*" at the end):
tar cvzf lab14.tar.gz lab14*.script Makefile *.c* *.h*
ls -l lab14.tar.gz
The last command shows you how big the created " lab14.tar.gz" file is.
If " lab14.tar.gz" is larger than 1MB in size, the submission server will not accept it.
If you use an IDE, the IDE may put your source code in subdirectories. In that case,
you need to modify the commands above so that you include ALL
the necessary source files and subdirectories (and don't include any binary files)
ane make sure that your code can be compiled without the IDE since the grader is not allowed to use an IDE to compile your code.
You should read the output of the above commands carefully to make sure that "lab14.tar.gz" is created properly.
If you don't understand the output of the above commands, you need to learn how to read it!
It's your responsibility to ensure that "lab14.tar.gz" is created properly.
To check the content of "lab14.tar.gz", you can use the following command:
tar tvf lab14.tar.gz
Please read the output of the above command carefully to see what files were included in " lab14.tar.gz"
and what are their file sizes and make sure that they make sense.
Please enter your USC e-mail address and your submission PIN below. Then click on the Browse button
and locate and select your submission file (i.e., "lab14.tar.gz").
Then click on the Upload button to submit your "lab14.tar.gz".
(Be careful what you click! Do NOT submit the wrong file!)
If you see an error message, please read the dialogbox carefully and fix what needs to be fixed and repeat the procedure.
If you don't know your submission PIN, please visit this web site to have your PIN e-mailed to your USC e-mail address.
When this web page was last loaded, the time at the submission server at (N/A) was
.
Reload this web page to see the current time on (N/A).
If the command is executed successfully and if everything checks out,
a ticket will be issued to you to let you know "what" and "when"
your submission made it to the Bistro server. The next web page you
see would display such a ticket and the ticket should look like
the sample shown in the submission web page
(of course, the actual text would be different, but the format should be similar).
Make sure you follow the Verify Your Ticket instructions
to verify the SHA1 hash of your submission to make sure what you did not accidentally submit the wrong file.
Also, an e-mail (showing the ticket) will be sent to your USC e-mail address.
Please read the ticket carefully to know exactly "what" and "when"
your submission made it to the Bistro server.
If there are problems, please contact the instructor.
It is extreme important that you also verify your submission
after you have submitted "lab14.tar.gz" electronically to make
sure that every you have submitted is everything you wanted us to grade.
If you don't verify your submission and
you ended up submit the wrong files, please understand that due to our fairness policy,
there's absolutely nothing we can do.
Finally, please be familiar with the Electronic Submission Guidelines
and information on the bsubmit web page.
|
