A7 - Unreliable Chat Client

650 - 850 points

Run the server

(cd infrastructure; python3 -m unreliable_server)

By default, the server will run in reliable mode, i.e., no bit flips, bursts, delays, or packet drops will occur. To enable unreliable features, experiment with the options below. A more detailed description of the unreliable features can be found in the Unreliability section.

usage: python -m unreliable_server [-h] [-a ADDRESS] [-p PORT] [-d DELAY] [-pb PROBABILITY] [-b BURST] [-s SEED] [-v]

This is an unreliable chat server to be used with A7 Unreliable Chat Client assignment. The default address is 0.0.0.0 and the default port is 5378, using
UDP. Please check the Lab Manual for a detailed specification of the protocol. The maximum number of concurrent connections is 16.

options:
  -h, --help            show this help message and exit
  -a, --address ADDRESS
                        Set server address
  -p, --port PORT       Set server port
  -d, --delay DELAY     Set message delay in seconds
  -pb, --probability PROBABILITY
                        Set the probability of an error to occur when delivering a message.
  -b, --burst BURST     The length of a burst of dropped bits
  -s, --seed SEED       The seed for the random number generator
  -v, --verbose         Enable verbose logging

Run the client (your implementation)

python3 -m a7_unreliable_chat

---

Assignment (650 points)

Your task is to implement a replica of the Transmission Control Protocol as defined in RFC 9293 to tackle possible errors encountered on an unreliable network. TCP is a very large protocol, so you will only be implementing a small set of features required to ensure reliability on our toy example.

Even though we are using an unreliable server to connect our clients, consider it an abstraction of the unreliable network running under the transport layer. In reality, when sending messages from one client to another, you must consider the connection to be a peer-to-peer connection.

The virtual peer-to-peer network interaction

The possible errors that can occur over the network are described in the Unreliability section. To handle the possible errors, you will need to keep track of sequence and acknowledgment numbers for each connection, implement a checksum algorithm for error detection, a retransmission algorithm in case an error is detected, and periodic retransmission in case an acknowledgment is not received.

Protocol

The unreliable chat client follows a protocol similar to the regular chat client, with the significant difference being that we are now working with a binary protocol rather than a text-based protocol.

The spaces present in the protocol message formats are present for readability purposes only. In the actual message, you will not receive any additional spaces. Additionally, it is not guaranteed that the message received is encoded in UTF-8 format. Thus, you are required to extract the given parameters from a bytearray (in binary format) before decoding. For example, the message 0x01 [name] 0x00 could arrive at the server in the format:

# Equivalent of the A1 protocol: HELLO-FROM daniel\n
b'\x01\x100\x97\x110\x105\x101\x108\x00'

Client-side protocol

The client-side protocol represents the set of messages sent by the client to the server. The client shall never expect any of the following messages to come from the server. Message parameters have been marked as [param].

Message format	Description
0x01 [name] 0x00	First-handshake message. The client sends this in an attempt to log in.
0x02 0x00	Request for all currently logged-in users.
0x03 [name] 0x00 [length] [message]	Send a chat message for a user with username name. Note that your client must contain as [length] 4 bytes representing the unsigned integer notation of the length of [message].

Server-side protocol

The server-side protocol represents the set of messages sent by the server to the client, as responses to requests made by the client. The client should only expect these kinds of messages to arrive and handle them properly. Message parameters have been marked as [param], matching the parameters from the client request.

Message format	Description	Response to client message
0x04 [name] 0x00	Second hand-shake message. The server sends this if the handshake (i.e., log-in) is successful.	0x01 [name] 0x00
0x05 0x00	Sent during handshake if the user cannot log in because the chosen username is already in use.	0x01 [name] 0x00
0x06 0x00	Sent during handshake if the user cannot log in because the maximum number of clients has been reached.	0x01 [name] 0x00
0x07 [name1,name2,...] 0x00	A list containing all currently logged-in users.	0x02 0x70
0x08 0x00	A confirmation sent to the client that an outgoing message was sent successfully.	0x03 [name] 0x00 [length] [message]
0x09 0x00	The destination user provided by [name] does not exist.	0x03 [name] 0x00 [length] [message]
0x0A [name] 0x00 [length] [message] This is the only packet that may encounter unreliability.	Represents the incoming message as a result of another client using the SEND protocol message. The [length] parameter will contain the number of bytes in an unsigned 4-byte integer.
0x0B 0x00	Sent if the last message received from the client contains an error in the header.
0x0C 0x00	Sent if the last message received from the client contains an error in the body.

---

Unreliability

There are only four classes of unreliable interaction that can happen over the virtual peer-to-peer connection. Each one of them will occur at a probability $p \in [0, 1)$, defined with the --probability option in the server.

Bit Flips

Bit flips may occur once every 256 bits at random. Namely, if a bit flip error type occurs, every 256 bits of the message will include a bit flip at a random position. For each message, a bit flip error will be triggered with a probability of $p$.

Bit Burst

A bit burst will scramble all bits in a given range of $b$ bits, defined with the --burst option in the server.

A bit burst will choose a random start index to fit the range $b$, and will scramble all of the bits in the range.

For each message there is a $p$ probability that a bit burst may occur, and a bit burst may only occur once per message.

Packet Drop

A packet drop has a probability of $p$ to occur. When it does, the entire packet never leaves the server, thus never reaching its destination.

Packet Delay

Packets may be delayed for a random duration of $[0, d)$ where the delay $d$ is defined with the --delay option in the server. For each message, there is a $p$ probability that a packet delay may occur.

Unreliability is only applied to the [message] parameter of the 0x0A [name] 0x00 [length] [message] packet. Thus, you do not need to worry about control packets such as 0x01 being scrambled. Additionally, you may assume that the 0x00 terminator and packet headers will never be scrambled.

The --seed option of the server allows you to easily reproduce runs using the same parameters in testing. Always keep track of the seed used when encountering an issue.

The automated testing environment will test your code with multiple seeds to ensure correctness, but also with deterministic errors.

---

Specification

The following section contains the required features for the basic part of the assignment. All requirements, apart from Reliability, are identical to A1 - Chat Client; namely, your task is to replicate the reliable client over an unreliable network.

The requirements lightly model the TCP specification as prescribed in RFC 9293. You will not have to implement the entire TCP specification (such as the TCP state machine), but rather a subset of features required to provide reliability in our toy example.

Reliability

The most significant set of requirements are those related to your program's network reliability. The following specification defines the expected (consistent) behavior given the network unreliability simulated by the unreliable server.

1. The client must not make any assumptions about the binary protocol. It is possible that special bytes such as 0x00 are present in the payload of different messages.

2. The client must implement reliability features only for the 0x0A (delivery) message type.

3. The client must be able to correct all types of errors by means of error detection + retransmission or error correction within 0.5 seconds of the original message arriving.

4. The client must implement sequence numbers and acknowledgment numbers in order to deal with possible missing packets, as prescribed by RFC 9293.

5. Messages received on the client must be displayed in the order they were delivered by the sending client, rather than the order they arrived from the network.

6. The client must implement fragmentation. Packets sent over the network should not exceed 512 bytes in size. If a client desires to send a longer message, it must be split accordingly.

7. The bytes sent as part of a 0x0A (delivery) message content must not exceed 35% overhead of the actual delivered message for the maximum packet length of 512 bytes.

Client

The client requirements define the general functionality the program should implement. The technical details are covered in the Technical tab. Please note that your application must follow a strict textual interface, which is defined in the Interface tab.

1. The client must ask the user for a username and attempt to log them in.

2. The client must ask the user for a new username if the provided one is already in use, with an informative message.

3. The client must inform the user if the server is full and exit gracefully.

4. The client must inform the user if their username was rejected for any other reason and ask for a new username. The list of forbidden characters in the username is !@#$%^&*, and spaces.

5. The client must inform the user if their username was rejected for any other reason and ask for a new username. Examples include commands (@username, !who)

6. The client should not have to be restarted after a failed log-in attempt.

7. The client must be able to send messages to other authenticated users.

8. The client must be able to list all logged in users.

9. The client should only respond to messages received from the server. Specifically, the client should not store any state other than the connection's socket.

Commands

The client must support as user input several commands. The input must originate from stdin (standard input) and follow the specific format described below. Any input that does not match one of the formats must be ignored.

1. Typing the command !quit at any point must exit the client. No additional steps should be required to exit (e.g., Ctrl+C).

2. Typing the command !who must print a list of users.

3. An authenticated user should be able to send messages to other authanticated users by using the command @[username] [message], replacing the two parameters accordingly.

Technical

We define several technical requirements serving as a qualitative standard for your implementation. We acknowledge that several implementations may work or be correct, however, to facilitate your learning process, we limit the accepted correct implementations to a subset solely making use of basic interfaces.

1. The client must use the UDP transport layer protocol for all network communication. For this, you will be using the Python socket interface. Using any other libraries for network communcations is not allowed.

2. The client must not use the sendall() or exit() Python functions.

3. The client must not print incomplete messages.

4. The client must support the sending and receiving of messages of any nonzero length.

5. Awaiting user keyboard input should not prevent newly incoming messages from being displayed.

6. Receiving any protocol header from the server at any point in the client's lifetime must be handled appropriately.

7. Your implementation must not make any assumptions about the data received from the network. The only specification that should be followed is that of the provided protocol.

Interface

The application must print messages to stdout (standard output) and follow a strict format. Failing to meet the exact format described below will result in failing the automated testing.

Make sure to pay close attention to spaces, punctuation and commas. Some automated tests may fail if the messages do not include spaces that may be deemed redundant.

Interface Type	Format
Prompt for authentication.	Welcome to Chat Client. Enter your login:
Successful authentication.	Successfully logged in as [username]!
Username already in use detected during authentication.	Cannot log in as [username]. That username is already in use.
Illegal characters detected in name during authentication.	Cannot log in as [username]. That username contains disallowed characters.
Server is full error encountered during authentication.	Cannot log in. The server is full!
Message sent to another use successfully, after executing the corresponding command.	The message was sent successfully
Message failed to send due to the destination user not existing.	The destination user does not exist
Incoming message from another user.	From [username]: [message]
Result of a successful execution of the !who command.	There are [user count] online users: [username_1] [username_2] ... [username_n]
Server detected an error in the previous message's header.	Error: Unknown issue in previous message header.
Server detected an error in the previous message's body.	Error: Unknown issue in previous message body.

---

Bonus (200 points)

The bonus assignment consists of two parts. Both parts must be completed to obtain the 200 points. Consider networks that are extremely unreliable but only produce one-bit errors. Your task is to optimize for such networks, without sacrificing your protocol's effectiveness in regular, unreliable scenarios.

Part 1 - Hamming Codes

Implement Hamming codes in your delivery protocol to correct 1-bit errors in blocks of 256 bits. The goal is to reduce the reliance on retransmissions to correct small errors. Implementing Hamming codes should result in your client correcting the errors without requesting any additional information from the peer.

Burst errors may render Hamming codes redundant for specific unreliability configurations. Make sure to fall back to retransmissions and error detection in such cases.

Part 2 - Max Overhead

Using Hamming codes might increase the number of bytes you have to include to provide error correction. Your task is to optimize your protocol to utilize at most 10% overhead of the actual delivered message for the maximum packet length of 512 bytes.

It might be useful to consider smaller integer sizes, unsigned integer interpretation, and other binary tricks to reduce the number of bytes needed to provide error correction and detection. Clearly define your protocol's header overhead before continuing with this task.