- Note: A "socket identifier string" is a string that reads "srcport-dstport-dstaddr".
- Kernel Variables
NetKernel.postOffice: A PostOffice instance that facilitates Packet communication.NetKernel.pendingConnects: A HashMap that maps local port number integers to an ArrayList of (remote address, remote port) tuples. Entries are added to the HashMap whenever corresponding SYN Packets are received, and this structure is accessed by accept() calls to establish connections with remote machines.NetKernel.sendRequests: A LinkedList of Socket identifier strings, which is populated by write() calls and accessed by the sending thread to determine which Sockets to send packets through.NetKernel.unackedPacket: A class that contains data about packets that have been sent and have yet to be acknowledged. An unackedPacket contains a Long resend time, a local port, a dst port, a dst addr, and a packet sequence number.NetKernel.unackedPackets: A PriorityQueue of unackedPackets, prioritized on unackedPacket.time. Every time a packet is sent, an unackedPacket with the corresponding information is added to this global structure. unackedPacket.time is initialized to the currentTime + 20,000. The timer thread will send all qualifying unackedPackets referenced in this structure. Whenever an ACK is received, we remove the corresponding unackedPacket entry from the structure.NetKernel.socketHash: A HashMap that maps from (local port, dst port, dst addr) to Sockets.
- Process Variables
NetProcess.descToSocket: A HashMap of file descriptor integer to Socket string identifier (local port, dst port, dst addr) mappings. The methods read() and write() will access this HashMap to determine from which Socket to receive and send data.
- Sockets
NetKernel.Socket: A class that contains socket data. The NetKernel.socketHash contains instances of these Sockets, mapped by ports and remote addresses. It stores the process ID, a send-data buffer, a receive-data buffer, a receive sliding window, a send sliding window, an int currentSequenceNumber, and a state enum.
Socket.currentSendSeqNum: This int is initialized to 1. On sending of a Packet, the Packet will be labeled with this integer, and this value will be incremented.Socket.status: An enum that represents the current state of a network connection and dictates what occurs on events. The statuses are the same as those detailed in the Nachos Transport Protocol Specification: CLOSED, SYN_SENT, SYN_RCVD, ESTABLISHED, STP_SENT, STP_RCVD, and CLOSING.Socket.sendBuffer: On writes, byte data will be queued on this String until the sending thread awakens and forms packets out of the data to be sent.Socket.receiveBuffer: On reads, byte data is returned from this String, which is composed of queued data from contiguous blocks of Packets, which are received periodically by the receiving thread.Socket.waitForAccept: A Condition variable that connect() sleeps on until the receiving thread wakes it on the reception of a corresponding SYN/ACK Packet. At that point, the Socket's state is set to ESTABLISHED.Socket.connectLock: The Lock associated with Socket.waitForAccept.
- Sliding Windows
Socket.receiveSlidingWindow:
- An array that holds 16
Packets. This structure keeps track of received packets. Upon packet receipt, the receiving thread adds Packets to the array according to their sequence numbers.
- All
Packet are mapped relative to the currentLowestReceiveSeqNum, with arrayIndex = packetSequenceNumber - currentLowestReceiveSeqNum.
- Once there is a contiguous block of
Packets starting at the beginning of the array, the receiver thread writes all of data in the contiguous block of Packets to the receiveBuffer string.
currentLowestReceiveSeqNum is set to the highest sequence number of the copied block + 1.- The window then "slides" by copying over the remaining
Packets to a new array with updated array indices (arrayIndex = packetSequenceNumber - currentLowestReceiveSeqNum).
Socket.sendSlidingWindow:
- A size 16 array of
<Packet, boolean> tuples. This structure keeps track of Packets that have not yet been acknowledged.
- On the sending of a
Packet, that packet is added to this array in the same fashion as the Socket.receiveSlidingWindow.
- On reception of an ACK packet, the receiver thread flips the
boolean of the corresponding Packet to true.
- Once there is a contiguous block of acknowledged
Packets starting at the beginning of the array, currentLowestSendSeqNum is set to the highest sequence number of the block + 1.
- If any packets are remaining (beyond the contiguous block), they are copied to a new array with their array indices recalculated as for the receiveSlidingWindow.
- An attempt to send
Packets with a sequence number exceeding the range of the currentLowestSendSeqNum+15, inclusive, will fail.
Socket.currentLowestSendSeqNum: This int is initialized to 1. This number indicates at what sequence number the send sliding window begins and limits the range of numbered Packets that can be sent.Socket.currentLowestReceiveSeqNum: This int is initialized to 1. This number indicates at what sequence number the receive sliding window begins and limits the range of numbered Packets that can be received.
Implementation Details
edit
- Note: All packets received that are inappropriate for a particular socket state will be dealt with according to the protocol specification.
- Swap files are uniquely named with the network link address of the Nachos node.
connect()
- Generate random src port. If there is a
Socket corresponding to the src port, dest address, dest port in the NetKernel.socketHash which is CLOSED and has an empty read buffer, use it. Otherwise, continue picking random ports until such a socket can be found or no socket for the chosen src port, dest address, dest port exists. In the latter case, create a new Socket object with the appropriate parameters and add it to NetKernel.socketHash.
- Send a SYN packet to the target machine using
PostOffice.send(), adding it to NetKernel.unackedPackets, so that the timer thread can automatically resend un-ACK'd SYNs. Set the state of the Socket to SYN_SENT.
- Sleep on the
waitForAccept in the created/reused Socket object. On the reception of a SYN/ACK packet, the receive thread will find the appropriate Socket from NetKernel.socketHash and call wake() on its waitForAccept, at which point the Socket is switched to the ESTABLISHED state. A new <fileDescriptor, Socket> mapping will also be added to the NetProcess.descToSocket
accept()
- Upong receipt of SYN
Packets, the receive thread stores the request (local address, remote address, and remote port) in NetKernel.pendingConnects: the local port is mapped to a list of remote addresses/ports.
- An
accept() call searches for a pending request on the requested local port in pendingConnects. If such a request exists, it is removed from NetKernel.pendingConnects. Otherwise, accept() returns -1.
- If a pending connection was found, a new
Socket is created with its information and is initialized with an ESTABLISHED state. A SYN/ACK Packet is sent directly using PostOffice.send(). A new <fileDescriptor, Socket> mapping is added to the NetProcess.descToSocket hash.
write()
NetProcess.descToSocket is checked to determine if the file descriptor is a Socket, retrieving its identifier (if it is), and adding it to the sendRequests list.- The write buffer is copied to the
sendBuffer string and write() returns immediately. The sending thread will take care of the actual communication of Packets.
- The following error checks will be performed at the beginning of this method. Failure of these will return -1:
- The
fileDescriptor maps to a Socket.
- The
Socket's state is CLOSED or STP_RCVD.
read()
read() will retrieve the Socket identifier and then the Socket from the socketHash.- If the
read() sees that there is some data in the receiveBuffer, it will read as much as it can or as much as it has requested. A read() is still able to read from a closed socket, as long as the receiveBuffer still contains data. It will return 0 if there was no data available. The receiving thread will take care of actual communication of Packets.
- The following error checks will be performed at the beginning of this method. Failure of these will return -1:
- The
fileDescriptor maps to a Socket.
- The
Socket is CLOSED. If there is data in receiveBuffer, we read it as detailed above.
close()
- Close translates from file descriptor to socket using
descToSocket.
- If the socket is in an ESTABLISHED state, it will check if the send sliding window is currently empty (all packets have been ACK'd).
- If this is true, it will add a FIN packet to the send sliding window, and a reference entry to the FIN packet to the
unackedPackets structure. Then it will change the Socket's state to CLOSING.
- Otherwise, the send sliding window still has unacked packets, so
close() will send a STP packet using PostOffice.send() and switch the Socket's state to STP_SENT.
- On the reception of more data packets by the receiving thread, if the
Socket is in the STP_SENT state, we retransmit a STP packet. Once all packets have been ACK'd in the send sliding window, if we are in the STP_SENT state, we proceed to the FIN state as detailed earlier.
- On the reception of a STP packet, if a
Socket is in the ESTABLISHED state, we remove all packets from the send sliding window and the unackedPackets structure and change the state to STP_RCVD.
- On the reception of a FIN packet in the STP_RCVD state, we send a FIN/ACK packet and go to the CLOSED state. The
Socket that receives a FIN/ACK packet in the CLOSING state will also go to the CLOSED state.
- When a
Socket is in the CLOSED state, write() calls will not be possible, but read() calls are possible as long as readBuffer still contains data.
- If there is no more data in the
receiveBuffer of a Socket, we remove the file descriptor mapping from descToSocket.
- Sending Thread
- Takes a socket identifier from
NetKernel.sendRequests and verifies that the corresponding Socket is not CLOSED and that its sendSlidingWindow can accommodate more Packets.
- If these conditions are not fulfilled, the socket identifier is put back onto
NetKernel.sendRequests and the thread will work on another request.
- If these conditions are fulfilled, it removes
packetSize amount of bytes from the sendBuffer of the chosen socket and creates a data packet out of those bytes. A MailMessage is then created with the appropriate addressing information and sent using PostOffice.send(). The Packet is also added to the sendSlidingWindow at the appropriate index based on its sequence number.
- This process is repeated until the chosen socket's sending window is filled, at which point the sending thread moves on to another request.
- Receiving Thread
- The receiving thread executes the actual reception and interpretation of data packets. It replaces the receiveInterrupt of the postOffice class. On reception of a packet, it verifies to which socket the packet is bound.
- It then verifies that the
Socket is not CLOSED and that the receive sliding window can accommodate more Packets. If the conditions are not fulfilled, the packet is dropped. Otherwise, if the Packet received is a data packet and the Socket is in a valid state, the Packet is placed at the appropriate index of the sliding window.
- A corresponding ACK
Packet is sent directly with PostOffice.send().
- We continue to receive
Packets in this manner until the receiveSlidingWindow is filled or we drop a Packet.
- If at any time the sliding window has a contiguous block of
Packets starting at index 0, we flush the data of those Packets into the Socket’s receiveBuffer.
- On the reception of specialized
Packets, we follow the Nachos protocol specification and modify the Socket state accordingly.
- On reception of ACK-type
Packets, the corresponding Packet in the sendSlidingWindow is marked as ACK’d and the sliding window is adjusted accordingly.
- On the reception of a SYN/ACK packet by the receive thread, the Socket will be found using information from the packet and wake() will be called on Socket.waitForAccept, at which point the Socket is switched to the ESTABLISHED state.
- Timer Thread
- When the NetKernel initializes, it forks a Timer Thread that runs continuously.
- The timer thread peeks at the top of the
unackedPackets structure and verifies if the currentTime >= unackedPacket.time. If this is true, resend the Packet using information from the Socket corresponding to the unackedPacket.
- Removethe
unackedPacket off the top of unackedPackets and add the unackedPacket entry back onto the structure with a new currentTime + 20,000 value.
- The timer thread will keep resending
Packets as long as entries fulfill the currentTime >= entryTime condition. Otherwise it will go to sleep.
connect(host, port) {
do {
generate random src port
if (src port, dest addr, dest port do not exist in socketHash) {
create newSocket;
add newSocket to socketHash;
break;
}
if (src port, dest addr, dest port refers to a closed, fully-read socket){
newSocket = existingSocket;
break;
}
} while (true);
newSocket.state = SYN_SENT;
send SYN packet and add packet information to unackedPackets and sendSlidingWindow;
sleep on newSocket.waitForAccept, wait for receiving thread to wake on reception of a SYN/ACK;
newSocket.state = ESTABLISHED;
add fileDesc, socket mapping to descToSocket;
return fileDesc;
}
accept(port) {
if port in keys of pendingConnects {
remove one (addr,port) tuple from associated list
} else {
return -1;
}
create newSocket;
newSocket.state = ESTABLISHED;
send SYN/ACK packet;
add new <fileDescriptor, Socket> mapping to descToSocket;
return fileDescriptor;
}
write() {
//only networking code is shown
translate from fileDesc to socket identifier using descToSocket;
add socket identifier to sendRequests list;
copy all data from src buffer to socket's sendBuffer string;
return bytes written; // the sending thread deals with actual packet communication
}
send() { //"Sending Thread"
while (true) {
pop sendRequests;
if (socket is not CLOSED && sendSlidingWindow is open) {
while (sendSlidingWindow is open) {
remove packetSize bytes from socket.sendBuffer;
create a packet with that data;
postOffice.send(packet);
add packet to sendSlidingWindow;
}
} else
continue;
}
}
read() {
translate from fileDesc to socket identifier using descToSocket;
if (socket is closed) {
if (socket still has data to be read) {
read available data from socket.receiveBuffer;
return bytes read;
} else {
return -1;
}
} else {
read as much as needed from socket.receiveBuffer;
return bytes read; //receive thread takes care of actual packet communication.
}
}
receive() { //"Receiving Thread"
while(true){
packet = postOffice.receive();
if (packet is ACK type) {
mark corresponding packet in sendSlidingWindow as ACK;
adjust sendSlidingWindow accordingly;
}
socket = get socket from socketHash with info from packet;
if (packet is SYN/ACK type) {
socket.waitForAccept.wake();
socket.state = ESTABLISHED;
}
if (socket is not CLOSED && receiveSlidingWindow is open) {
if (packet is data packet && socket.state is valid)
put packet at appropriate index of receiveSlidingWindow
PostOffice.send(ACK packet);
} else {
drop packet;
break;
}
if (receiveSlidingWindow is full) {
break;
}
packetsToFlush = [];
for (index i of receiveSlidingWindow starting at 0) {
if (receiveSlidingWindow[i] has packet) {
add packet to packetsToFlush;
remove packet from receiveSlidingWindow;
} else {
break;
}
}
}
}
timer() {
unackedP = unackedPackets.peek();
while (currentTime >= unackedP.time) {
resend unackedP.packet;
unackedP = unackedPackets.pop();
put unackedP in unackedPackets with time = currentTime + 20000;
unackedP = unackedPackets.peek();
}
sleep();
}
close(fileDescriptor) {
get Socket s with given fileDescriptor from descToSocket;
if (s.state == ESTABLISHED) {
if (s.sendSlidingWindow is empty) {
add FIN packet to s.sendSlidingWindow;
add reference to FIN packet to unackedPackets;
s.state = CLOSING;
} else {
send STP packet with PostOffice.send();
s.state = STP_SENT;
}
} else if (s.state == STP_RCVD) {
send FIN packet to s.sendSlidingWindow;
add reference to FIN packet to unackedPackets;
s.state = CLOSING;
} else {
return -1;
}
return 0;
}
- Connection
- Set up two Nachos nodes, named A and B:
- Have A connect and B accept on the same port and verify that a connection has been made with print statements on the information from the two newly created sockets.
- Attempt two connects from A with only 1 accept from B on the same port, verify that only one new socket is created on B, but it has a record of the second connect. A subsequent accept should create a new connection with the 2nd connect from A.
- Create a successful connection between A and B, and close the connection. Verify that both socket states are closed.
- After closing, verify that creation of a connection with the same port and addressing information is successful. Also verify that this same test correctly fails if there is still data to be read from the port.
- Create a connection from Port 1 to Port 2. Create a second connection from Port 3 to Port 1.
- Verify that both connections work properly with print statements.
- Verify the reads and writes succeed from Ports 1 and 2 and Ports 1 and 3.
- Reading and Writing
- Set up two Nachos nodes, named A and B:
- Have A run a program that writes a large amount of text to B. Have B run a program that reads text from the same port and verify that the text is the same sent from A.
- With A and B connected, have A call write three times and have B call read only once. Close A.
- Verify that the connection between A and B is dead.
- Verify that writes from B to A will fail.
- Verify that two more reads from B with retrieve the last two messages sent by A.
- Verify that a subsequent read from B will fail.
chatserver.ClientList: A struct containing an int fileDescriptor, a byte array byte *partialBuffer, and an int bufferLen. Each struct also contains a pointer to the next client. Each server node thus contains a linked list of clients.chatserver.currentClient: A Client pointer to the next Client from which to read input.chatserver.MAX_LINE_SIZE: An int that determines the maximum size of a line.chat.fileDescriptor: An int fileDescriptor that stores the fileDescriptor returned by connect().chat.MAX_LINE_SIZE: An int that determines the maximum size of a line.
Implementation Details
edit
- The main method in
chatserver.c initializes a byte array tmp of length MAX_LINE_SIZE. It then runs a continuous while loop and performs the following actions:
- It checks for standard input. If there is standard input, the method breaks from the while loop and exits.
- It calls
accept on port 15. If there is a chat client waiting to establish a connection, a new Client node is created with the returned fileDescriptor and a new byte array initialized to size 1000. This new client is added to the ClientList.
- For each client in the
ClientList, chatserver does the following:
- It reads up to
MAX_LINE_SIZE from currentClient.socket into buffer tmp.
- It appends the data in
tmp to currentClient.buffer
- It reads from
currentClient.buffer. If this read returns -1, we disconnect. Otherwise, we add the returned value to currentClient.bufferLen.
- While
currentClient.buffer contains a newline, it does as follows:
- It copies
currentClient.buffer up to the newline into tmp.
- It moves the rest of the data in
currentclient.buffer up by however many bytes were copied, subtracting this number from currentClient.bufferLen.
- Finally, for each client in the
ClientList, it sends out the contents of tmp.
- Disconnects are handled by catching -1 return values on reads and writes. Since the client has called close() prior to the disconnect, the socket on the server side should reflect the closing of the connection. When a read or write failure occurs, we remove that particular client from the client list.
- The main method in
chat.c first initializes three byte arrays:currentMsg, tmp, and server. All these arrays are of length MAX_LINE_SIZE. It then calls connect(). It runs a continuous while loop and performs the following actions:
- It reads standard input of length
MAX_LINE_SIZE - length of currentMsg into currentMsg.
- If
currentMsg is not empty, it runs the following while loop on the condition that currentMsg contains a newline:
- It copies the data in
currentMsg up to the first newline character into tmp.
- If the contents of
tmp is ".", it calls close() and breaks out of the while loop, ending this user's chat session.
- It moves the rest of the data in
currentMsg up by however many bytes were copied.
- Then it write the contents of
tmp to the server.
- If
currentMsg is empty, it reads from client's socket into server a length of MAX_LINE_SIZE - length of server byte, before running a while loop on the condition that server contains a newline:
- It copies the data in
server up to the first newline character into tmp.
- It moves the rest of the data in
server up by however many bytes were copied.
- Finally, it prints the contents of
tmp.
chatserver.main() {
byte tmp[MAX_LINE_SIZE];
while (true) {
if there is standard input { break; }
if (newClient = accept(15)) add newClient to clientList;
for (currentClient in clientList) {
read up to MAX_LINE_SIZE from currentClient.socket into tmp;
append the data in tmp to currentClient's buffer
currentClient.bufferLen +=
read(currentClient.socket,
currentClient.buffer + currentClient.bufferLen,
MAX_LINE_SIZE - currentClient.bufferLen)
while (currentClient.buffer contains a newline) {
copy currentClient.buffer up to newline into tmp;
move the rest of currentClient.buffer left by however many bytes were copied;
currentClient.bufferLen -= bytes copied;
for (client in clientList) {
clientList.socket.write(tmp);
}
}
}
}
}
chat.main(int addr) {
byte currentMsg[MAX_LINE_SIZE], tmp[MAX_LINE_SIZE], server[MAX_LINE_SIZE];
socket = connect(addr, 15);
while (true) {
read(stdin, currentMsg + length of currentMsg, MAX_LINE_SIZE - length of currentMsg)
if (currentMsg is not empty) {
while (currentMsg contains a newline) {
copy currentMsg up to newline into tmp;
if (tmp == ".") {
close();
break;
}
move the rest of currentMsg left by however many bytes were copied;
socket.write(tmp);
}
} else {
read(socket, server + length of server, MAX_LINE_SIZE - length of server)
while (server contains a newline) {
copy server up to newline into tmp;
move the rest of server left by however many bytes were copied;
print(tmp);
}
}
}
}
- Two users:
- One instance of Nachos runs chatserver.c, while Users A and B run chat.c on other separate instances.
- Have A send a message and confirm that both A and B receive the same message from the server.
- Have B send a message and confirm that both A and B receive the same message from the server.
- Three users:
- One instance of Nachos runs chatserver.c, while Users A, B, and C run chat.c on other separate instances.
- Execute the same tests used in the situation with two users.
- Have A send 2 messages, B send 1, and C send 2. Verify that all these messages are received by all chat clients. The two messages from both A and C should have been received in the order they were sent by their respective users.
- Have C disconnect from the chat server, then reconnect. Verify that C can still receive and send messages to A and B as before.
- Four or more users:
- Perform the same tests used for three users.
- Run tests with more messages and more complex ordering of sent messages.
- Have users connect to the server after the chat session has already begun and verify that they can interact with the other users normally.
- Have various users disconnect and reconnect to the server and verify that they can still interact with the other users as before.
