|
Computer Science 461Distributed Computing and NetworkingFall 1997 |
In this assignment you will implement reliable communication on top of the unreliable AcmeNet network.
AcmeNet, like the Internet on which it is built, is unreliable: it is not guaranteed to deliver all packets that are sent. A packet may vanish into oblivion, or multiple copies of a packet may be delivered to the destination, or packets may be received in a different order than they were sent. Your job is to fix this: to build a software layer that ensures that every packet is delivered exactly once, and that packets are delivered in the same order they were sent.
Before you start, take some time to learn about AcmeNet, and read the documentation for the AcmeNet Utility Library (Java package AcmeNet.Util).
If you're not used to writing network software, there is one other thing to get used to: interoperability. This means that the code you write must be able to communicate with code written by others. To do this, you all must follow agreed-upon conventions about things like how packets are formatted. The assignment will specify these details, and you should be sure to follow them. We won't consider your code to be correct until it can communicate properly across the network with our code.
Your code for this assignment should be in the AcmeNet.Assn1 package. Your goal is to write a working implementation of the AcmeNet.Assn1.ReliableNI class. You will probably need to write some auxiliary classes; these classes should be non-public and in the AcmeNet.Assn1 package. We have provided you with the class AcmeNet.Assn1.PacketTypeCode, which defines some constants you will need.
The description below talks about "the sender" and "the receiver". Of course, a typical process engages in both sending and receiving, interacting with several other processes. Thus a process must be prepared to play different roles at different times; part of your job is to keep separate information about these roles so the process knows how to interact with each of its peers.
Your solution must use two kinds of AcmeNet packets: Data packets (which carry data), and Ack packets (which acknowledge the receipt of Data packets). Every Data packet must be given a 31-bit sequence number (encoded as a Java int). The first packet sent from a particular sender to a particular destination must have sequence number 0, the next packet from that same sender to that same destination must have sequence number 1, and so on.
You should use a "stop and wait" protocol. This means that a sender must not send a packet until it is sure that all previous packets to the same destination have been delivered. How does a sender know when a packet has been delivered? It knows because the receiver acknowledges receipt of a Data packet by sending an Ack packet. If an Ack packet arrives back at the original sender, the original sender learns that the corresponding Data packet has definitely reached its definition. If a Data packet is not acknowledged for a long time, the sender should retransmit it. (More on retransmission below.)
A receiver should keep track of the largest Data-packet sequence number it has received from each sender.
Every Ack packet should contain the sequence number of the packet that is being acknowledged. (In other words, if I send you a packet with sequence number 42, your acknowledgement of that packet should also have sequence number 42.)
A sender should keep track of all of the Data packets it has sent that have not yet been acknowledged. If a Data packet remains unacknowledged for more than AcmeNet.Assn1.ReliableNI.TimeoutSeconds seconds, that packet should be retransmitted, using the same sequence number the packet had the first time it was sent. If the packet remains unacknowledged, it should be retransmitted every AcmeNet.Assn1.ReliableNI.TimeoutSeconds until it is acknowledged. (You don't have to retransmit after exactly the required interval every time, but the time between retransmissions should be in the general neighborhood of the required interval.)
There's one more unpleasant problem to deal with. Suppose processes A and B have carried on a long conversation, using fairly big sequence numbers. Then process B crashes, and process C is started on the same machine where B was. Unfortunately C is given the same NetAddress that B was using.
What happens when C tries to talk to A? A will think it is still talking to B, since B and C are at the same NetAddress. So A will use large sequence numbers, but C will be expecting to use sequence numbers starting at zero. The result is that A and C will be unable to communicate --- ever. This isn't a big problem now, but later in the course we will have server processes that will run for days at a time. If your process happens to get the same NetAddress as a process that talked to the server two days ago, you'll be unable to talk to the server. That's unacceptable.
To deal with this problem, we will have each process keep track of when it started running. Specifically, the ReliableNI class will have a static variable called bootTime that is initialized to the current time when the ReliableNI class is loaded (obtained by calling System.currentTimeMillis). Different processes will have different bootTime values, even if they are at the same NetAddress.
Every packet will contain the bootTime of the process that sent it. Each process will keep track of the bootTimes of the NetAddresses it has communicated with. This will allow process A to notice that C is different from B, because the bootTime in C's packets will be different than the bootTime A was expecting to see. When A sees this, it will forget the sequence numbers it was using with B, and start over with sequence number zero.
There's one more detail to get right. Process A might have sent a Data packet to B that was never acknowledged. When A determines that another process has popped up at B's old NetAddress, A should be sure to stop retransmitting any packets intended for B.
Every packet starts with the same three fields:
An Ack packet contains only these three fields. In a Data packet, these three fields are followed by some bytes of data. The number of data bytes can range from one up to AcmeNet.Assn1.ReliableNI.MaxPacketLength.
Since an outgoing packet is represented by a java.io.DataOutputStream, you can build a packet by using the writeByte, writeLong, and writeInt methods of DataOutputStream. Similarly, since an incoming packet is represented by an AcmeNet.Util.PacketInputStream, and PacketInputStream extends java.io.DataInputStream, you can use the readByte, readLong, and readInt methods of DataInputStream to extract the fields of a packet header. Once you've extracted the three header fields, the packet will be ready to have the data bytes read.
You can start testing your solution by creating two processes that send packets to each other, or by having one process that allocates two ReliableNI objects and sends packets between them.
We will also set up a "Reliable Echo Server" process at NetAddress("idea.cs.princeton.edu", 9004). When you send this process a properly formatted packet, it should send an identical packet right back to you.
Last modified: Tuesday, September 09, 1997 07:07 AM