- 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 Packet
s 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 Socket
s 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 Socket
s.
- 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 Socket
s, 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 Packet
s, 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
Packet
s. This structure keeps track of received packets. Upon packet receipt, the receiving thread adds Packet
s 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
Packet
s starting at the beginning of the array, the receiver thread writes all of data in the contiguous block of Packet
s 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
Packet
s 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 Packet
s 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
Packet
s 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
Packet
s 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 Packet
s 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 Packet
s 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
Packet
s, 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 Packet
s.
- 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 Packet
s.
- 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 Packet
s.
- 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 Packet
s. 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
Packet
s 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
Packet
s starting at index 0, we flush the data of those Packet
s into the Socket
’s receiveBuffer
.
- On the reception of specialized
Packet
s, we follow the Nachos protocol specification and modify the Socket
state accordingly.
- On reception of ACK-type
Packet
s, 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
Packet
s 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.