CSE 434, SLN 70608 — Computer Networks — Fall 2020
Instructor: Dr. Violet R. Syrotiuk
Socket Programming Project
Available Sunday 09/13/2020
Milestone due Sunday 09/27/2020; full project due Sunday 10/18/2020
In this project you will implement O-RING, a peer-to-peer application program in which processes communicate using
sockets to build one or more rings, orient each ring and elect a leader in it, and compute functions of a ring.
• You may only write your code in C/C++, in Java, or in Python. Each of these languages has a socket
programming library that you must use for communication among processes. Sample client and server programs
that use sockets written in C will be provided. (The book uses Python.)
• This project may be completed individually or in a group of size at most two people. Each group must restrict
its use of port numbers as described in §5 to prevent application programs from interfering with each other.
• You must use a version control system as you develop your solution to this project, e.g., GitHub or similar.
Your code repository must be private to prevent anyone from plagiarizing your work. It is expected that you
will commit changes to your repository on a regular basis.
The rest of this project description is organized as follows. Following an overview of the O-RING application and
its architecture in §1, the requirements of the client-server protocol, and its peer-to-peer protocol are provided in §2
and §3, respectively. §4 provides some suggestions if you want to multi-thread your project, whereas §5 describes port
assignments. Finally, §6 describes the requirements for the milestone and full project deadlines.
1 O-RING: Computing in Oriented Rings
Figure 1: Architecture of the O-RING application.
The architecture of the O-RING application is illustrated in Figure 1. It shows the server maintaining state information about the processes in the system. In this example, there are five processes/users, three of which are organized
in a ring. They run a distributed ring orientation protocol described in §3.1.1 to consistently label their ports. After
orientation, all subsequent messages in the ring are sent out the port labelled RIGHT and received on the port with
label LEFT. In this example, the orientation results in a counter-clockwise message flow around the ring. A leader of
the ring is elected using a protocol described in §3.1.2; in this example, user4 is elected the leader of the ring. Any
request to compute a function of an O-RING while it is under construction is denied. Peers interact with the server to
establish an O-RING, and to compute functions of it.
1
This socket programming project involves the design and implementation of two programs:
1. The first program implements an “always-on” server of a client-server protocol to support management of the
peer processes implementing the O-RING application, among other functionality. Your server should read one
integer command line parameter giving the port number at which the server listens for messages. The messages
to be supported by the server are described in §2.
2. The second program implements the client-side of the client-server protocol, as well as the peer-to-peer protocol
to construct the O-RING, and to compute functions of a ring. Each client process should read two command
line parameters, the first being a string representing the IPv4 address of the server in dotted decimal, and the
second being the integer port number at which the server is listening. The messages to be supported by peers
interacting with the server, and with other peers are described in §3.
2 The O-Ring Client-Server Protocol
Recall that a protocol defines the format and the order of messages exchanged between two or more communicating
entities, as well as the actions taken on the transmission and/or receipt of a message or other event [1]. This section
describes the client-server protocol of the O-RING protocol. The design of the message format is left to you; see §4.1.
In this project description, when a process communicates with the server it is referred to as a client, and when it
communicates with other peer processes it is referred to as a peer. Commands are read from stdin at a client — no
fancy UI is expected! A client constructs a message that corresponds to the command and sends it to the server over a
UDP socket. Messages to the server always come in pairs; i.e., after sending a message to the server, the client waits
for a response before issuing its next command. Similarly, the server sends a response to each request. Messages sent
among peers are described in §3.
The server process must support messages corresponding to the following commands from a client process:
1. register huser-namei hIPv4-addressi hport(s)i, where user-name is an alphabetic string of
length at most 15 characters naming the process. All users must be registered prior to issuing other any other
commands to the server.
On receipt of a command to register, the server stores the name, IPv4 address, and one or more port numbers
associated with that user in a state information base. Set the state of the user to Free to indicate that it is not a
member of any ring. You are welcome to introduce other states for users if you find it useful.
If the parameters are unique, the server responds to the client with a return code of SUCCESS. Specifically, each
user-name may only be registered once. The IPv4-address of a user need not be unique, i.e., one or
more client processes may run on the same end host. However, the port(s) used for communication by each
process must be unique on an end host.
The server takes no action and responds to the client with a return code of FAILURE if the registration request
is a duplicate, or if there is some other problem with the request.
2. deregister huser-namei. This command returns FAILURE if the user has state InRing. Otherwise,
the record for user-name is removed from the state information base, and the server responds with SUCCESS.
The client process making the request then exits the application, i.e., it terminates.
3. setup-ring hni huser-namei, where n ≥ 3 is an odd integer. This command initiates the construction
of a ring of size n by the named user. In this project, while multiple rings may exist at any time, each user may
only participate in one ring at a time.
This command results in a return code of FAILURE if:
• The user-name is not registered or is not Free. • n 6≥ 3 or is not odd.
• There are not at least n n 1 other Free users, besides user-name, registered with the server.
2
Otherwise, the server selects at random nn1 Free users and updates each one’s state to InRing including
that of user-name. Because you need to support the existence of multiple O-RINGS, assign an identifier for
each ring set up.
The server returns a return code of SUCCESS, a ring-id, the ring size n, and a list of n users that together
will form the O-RING to user-name. The n users are given by tuples consisting of, at a minimum, for each
user its user-name, IPv4-address, two port(s) for communication in an O-RING, with the tuple of
user-name listed first. Receipt of SUCCESS at user-name involves several additional steps to accomplish
the setup of the O-RING. These steps which include ring orientation and leader election are described in §3.1.
4. setup-complete hring-idi huser-namei hporti. Receipt of a setup-complete command from
user-name indicates that all the steps required to setup the O-RING with identifier ring-id have been completed. In addition, it indicates that user-name is the process that was elected the leader of the ring and that,
as the leader, it will listen for compute messages on the port number that is labelled zero (port) on completion of the ring orientation algorithm. The server should set the state of user-name to Leader in the state
information base, and store or mark the port of the process to be used in response to any compute commands.
The server responds to user-name with SUCCESS.
5. compute huser-namei. This command is initiates computation of a function in an O-RING. It returns
FAILURE if no O-RING exists, the user is not registered, or the user is registered but is not Free. Otherwise,
the server chooses an existing O-RING, and returns its ring-id, size n, and a 3-tuple corresponding to the
user-name, IPv4-address, and port of the leader of ring-id. (Clearly, any ring that may be in the
process of being torn down should not be selected!) Finally, the return code is set to SUCCESS and the response
is sent to user-name. Receipt of SUCCESS at the client involves several additional steps to perform the
computation, and the functions to support, described in §3.2.
6. teardown-ring hring-idi huser-namei, where user-name is the leader of O-RING. This command initiates the deletion of the O-RING with identifier ring-id. This command returns FAILURE if the
user is not the leader of the O-RING. Otherwise, the server responds to the user with SUCCESS. Receipt of
SUCCESS at the process involves several steps to delete the O-RING, as described in §3.3. Nothing should
interrupt the tear down of a ring.
7. teardown-complete hring-idi huser-namei, where user-name is the leader of the O-RING. This
command indicates that the O-RING with identifier ring-id has been torn down. The server returns FAILURE
if the process making the request is not the leader of the O-RING. Otherwise, the server changes the state of
each user in the ring to Free; these users may now be used in a future setup-ring or compute functions of
any other existing O-RING. The server responds to the former leader with SUCCESS.
3 The O-RING Peer-to-Peer (P2P) Protocol
A process is acting as a peer when it interacts with any other process other than the server. Several commands sent
to the server involve several additional steps with peer processes to complete. Specifically, each of setup-ring,
compute, and teardown-ring involve additional steps, as described in the following sections.
3.1 Setting up an O-RING
Let p denote the client process that sent a successful setup-ring command to the server. The server’s response also
includes an identifier for the ring ring-id, the ring size n, and a list of n tuples giving information about the peers
that are to form the ring. (Recall that the first tuple in the list is information about p.) Process p is now responsible for
establishing an O-RING of n processes that includes itself.
Suppose that you registered three ports for communication for each process. One is for communication with the
server and the other two for communication in an O-Ring. In that case, Table 1 shows the tuples returned with the
ports for the ring returned.
3
Table 1: Example of n tuples returned in a successful setup-ring command.
user0 IP-addr0 port0,0 port0,1
user1 IP-addr1 port1,0 port1,1
user2 IP-addr2 port2,0 port2,1 ... ... ... ...
usern 1 IP-addrn 1 portn 1,0 portn 1,1
The client now acts as a peer and follows these steps to setup the O-RING:
1. Build the O-RING. First, a logical ring among the n processes returned by the server must be set up. Recall
that process p is the first tuple in the list, i.e., at index position zero in Table 1. It is named user0, has IP
address IP-addr0, and will use the ports numbered port0,0 and port0,1 for communication in the ring. The
construction of the ring is initiated by user0.
For i = 0, . . . , n n 1: • useri stores information to reach its next-hop neighbour on the ring, i.e., the information stored at index
position i + 1 mod n in Table 1. To accomplish this, it sends a setup command on the port numbered
porti,1 to the process named useri+1 mod n that is listening to porti+1 mod n,0 on IP-addri+1 mod n
over a UDP socket. For ease of set up, you can include the index position i+1, and the tuples received
from the server in the setup command.
When the setup is received by the process at index position 0 in the list, i.e., user0, that initiated the construction of the ring, the ring setup is complete.
2. Orient the O-RING. The purpose of the orientation algorithm is to assign labels to port numbers consistently
such that, after orientation, all subsequent messages in the O-RING are sent on the port with label RIGHT and
received on the port with label LEFT. The O-RING will end up either being clockwise or counter-clockwise
oriented. To orient the O-RING, user0 initiates the ring orientation algorithm described in §3.1.1. Once
oriented, all subsequent communication in the O-RING follows the direction of the port labelled RIGHT.
3. Elect a leader of the O-RING. The purpose of the election algorithm is to elect a leader of the O-RING;
any of the n processes in the ring may be elected the leader. To elect a leader of the ring, user0 initiates the
leader election protocol described in §3.1.2. Once elected, the leader is responsible for sending a message for
the setup-complete command to the server with the required parameters; see §2. Subsequently, the leader
should expect to receive compute commands its port with label 0 for this O-RING.
3.1.1 The Distributed Ring Orientation Algorithm1
You are to design a protocol to orient an O-RING. That is, you must define the format and the order of messages
exchanged between the communicating entities, as well as the actions taken on the transmission and/or receipt of a
message or other event [1].
At a high level, the protocol to orient an O-RING of size n consists of three steps. At each process p in the ring:
1. Randomly assign one of the two port numbers used for communication in the ring the label RIGHT, and the other
port the label LEFT.
2. Executes the distributed ring orientation algorithm in Figure 2. The reason that we enforced a ring of odd size n
is to guarantee that the ring orientation algorithm does not have to break possible symmetries that may arise in
even-sized rings.
3. If the outcome of the algorithm is vote > 0 then the majority of the processes in the ring have labelled their
ports in agreement with how p labelled its ports, hence the labelling of port numbers does not change. Otherwise,
the labelling of the port numbers must be interchanged to conform to the majority.
1This protocol is from my very first published paper [2].
4
int Orient( int n ){
// Pseudocode syntax: send( port-label, [ vote, distance ] )
send( RIGHT, [ 1, 1 ] )
repeat {
// Pseudocode syntax: port-label = receive( [ vote, distance ] )
from = receive( [ vote, distance ] )
if( distance == n ) then goto DONE
if( from == LEFT ) then // Labelling agrees
send( RIGHT, [ vote+1, distance+1 ] )
if( from == RIGHT ) then // Labelling disagrees
send( LEFT, [ vote-1, distance + 1 ] )
}
DONE:
if ( vote > 0 ) then "The majority agree" // No change to port labels
if ( vote == 0 ) then "No majority" // Only possible in an even-sized ring
// Otherwise, interchange port labels to conform to majority
}
Figure 2: A distributed ring orientation algorithm [2].
3.1.2 The Distributed Leader Election Algorithm
You are to design a protocol to elect a leader in an O-RING. That is, you must define the format and the order of
messages exchanged between the communicating entities, as well as the actions taken on the transmission and/or
receipt of a message or other event.
Recall that the election is the third step of setting up an O-RING, and it is initiated by process p. At a high level,
the protocol to elect a leader in an O-RING of size n consists of three steps.
1. Each process in the ring selects a random integer as an identifier in the range [0, MAXINT T 1].
2. Starting at process p, a vector of size n is collected at p consisting of the identifiers of each process in the ring.
These identifiers are to be collected by sending messages in the oriented ring, i.e., all messages should flow in
the direction of RIGHT which is consistent at each process in the ring.
3. If there are no duplicate identifiers then:
(a) p distributes the vector to each node in the ring.
(b) The process whose identifier is maximum is elected the leader ` of the ring.
(c) Process ` sends a setup-complete message to the server informing it that ` has been elected the leader
of the ring; see §2 for the parameters.
Otherwise, p repeats steps 1-3 until there is a unique identifier in the vector and a leader is elected.
3.2 Computing a Function of an O-RING
Once established, an O-RING can compute simple functions of the ring. You are to design a protocol to support the
computation of functions in an O-RING. That is, you must define the format and the order of messages exchanged
between the communicating entities, as well as the actions taken on the transmission and/or receipt of a message or
other event.
1. The client issuing a successful compute command to the server receives the ring-id, ring size n, and
a 3-tuple corresponding to the user-name, IPv4-address, and port of the leader of an O-RING as a
response.
2. The same client now acts as a peer process p, and issues a compute function command to the leader of
O-RING at the provided IPv4-address and port. Functions to support include:
5
(a) sum: Each process in the ring, including the leader, selects a random integer in the range [0, MAXINTT1].
The aim of compute sum is to propagate the sum of all the integers selected by each process in the ring
to the leader.
(b) max: Each process in the ring, including the leader, selects a random integer in the range [0, MAXINTT1].
The aim of compute max is to propagate the maximum along the ring to the leader.
All messages must propagate around the oriented ring, i.e., all messages should flow in the direction of RIGHT
which is consistent at each process in the ring.
3. The leader returns a response consisting of the value of the computed function to the process p.
4. On receipt of the response to the compute function command, the process p prints the output of the
function.
3.3 Tearing Down an O-RING
The command tearddown-ring deletes the O-RING with identifier ring-id. This is accomplished by the following steps:
1. The leader must handle any existing compute commands, i.e., the leader must process any and all compute
commands that may be queued in the buffer associated with the socket attached to the port with label 0. Once
the teardown-ring is initiated, any further compute commands for this ring will be rejected by the server,
so once the queue is emptied it should remain empty.
2. The leader send a teardown command out the port with label 1. The teardown propagates around the ring,
back to the leader. The message simply informs to the process to close its socket, and that its state will change
from InRing to Free once the teardown is completed at the server.
3. On receipt of the teardown at the leader, it follow suits, and then sends a message for the teardown-complete
command to the server; see §2 for the parameters of teardown-complete.
4 Implementation Considerations
You need to decide how many port numbers to assign to each client/peer process (the server only listens on one port).
A suggestion is to use one port number for communication with the server, and two additional port numbers in the
event that the process becomes part of an O-RING. This is because once the ring is oriented, one port is to be used for
transmitting messages and the other for receiving messages. You are to use the port that is labelled zero on completion
of the orientation protocol for a peer to use when it computes functions of an O-RING; see command compute in §2.
You must register all the ports with the server for each user.
You may consider using a different thread for handling each socket. Alternatively a single thread may loop,
checking each socket one at a time to see if a message has arrived for the process to handle. If you use a single
thread, you must be aware that by default the function recvfrom() is blocking. This means that when a process
issues a recvfrom() on an empty socket the process blocks and waits for a packet to arrive. Therefore, a call to
recvfrom() will return immediately only if a packet is available on the socket. This may not be what you want.
You can change recvfrom() to be non-blocking, i.e., it will return immediately even if the socket is empty. This
can be done by setting the flags argument of recvfrom() or by using the function fcntl(). See the man pages
for recvfrom() and fcntl() for details; be sure to pay attention to the return codes.
4.1 Defining Message Exchanges and Message Format
The previous sections §2 and §3 have described the order of many message exchanges, as well as the actions taken on
the transmission and/or receipt of a message. As part of this project, you will ultimately have to define these steps for
the ring orientation algorithm, the leader election algorithm, computing a function of an O-RING, and tearing down
an O-RING. 6
In addition, you will need to define the format of all messages used in client-server and in peer-to-peer communication. This is often achieved by defining a structure with all the fields required by the command. For example, you
could define the name of the command as an integer field and interpret it accordingly. Alternatively, you may prefer to
define the command as a string. Indeed, any choice is fine so long as you are able to extract the fields from a message
and interpret them.
You should define reasonable upper bounds on the total number of registered users that your application supports,
among others. It may also useful to define meaningful return codes to, e.g., differentiate SUCCESS and FAILURE,
and/or introduce other meaningful error codes.
Due to their simpler multiplexing and demultiplexing, we will use UDP sockets in this project. That means
there is a possibility that messages may be lost or arrive out-of-order, but it is unlikely. You are not responsible for
implementing reliable communication.
5 Port Numbers
UDP uses 16-bit integer port numbers to differentiate between processes. UDP defines a group of well known ports to
identify well-known services. Clients on the other hand, use ephemeral, or short-lived, ports. These have port numbers
1024 through 655535 and are normally assigned to the client.
In this project, each group G ≥ 1 is assigned a set of 500 unique port numbers to use in the following range. If
G mod 2 = 0, i.e., your group is even, then use the range: G2 × 1000
+ 1000, G2 × 1000
+ 1499 . If G mod
2 = 1, i.e., your group is odd, then use the range: G2 × 1000
+ 500,
G2 × 1000
+ 999 . That is, group 1 has
range [1500, 1999], group 2 has range [2000, 2499], group 3 has range [2500, 2999], group 4 has range [3000, 3499],
and so on. Do not use port numbers outside your assigned range, as otherwise you may send messages to another
group’s server or peer process by accident that it is unlikely to interpret correctly, causing spurious crashes.
If you did not follow the instructions to join a group for Lab 1 with consecutive numbers, or you renamed
your group to a non-integer name, go back to the People/Groups on Canvas and correct this!
6 Submission Requirements for the Milestone and Full Project Deadlines
All submissions are due before 11:59pm on the deadline date.
1. The milestone is due on Sunday, 09/27/2020. See §6.1 for requirements.
2. The full project is due on Sunday, 10/18/2020. See §6.2 for requirements.
It is your responsibility to submit your project well before the time deadline!!! Late projects are not accepted.
Do not expect the clock on your machine to be synchronized with the one on Canvas!
An unlimited number of submissions are allowed. The last submission will be graded.
6.1 Submission Requirements for the Milestone
For the milestone deadline, you are to implement the following commands to the server: register, deregister,
a simplified setup-ring, and setup-complete. Specifically, the setup-ring only needs to implement the
first of the three steps and returns process p as the leader. Your output should verify you can forward a message around
the ring using the prescribed port numbers.
Submit electronically before 11:59pm of Sunday, 09/27/2020 a zip file named Groupx.zip where x is your
group number. Do not use any other archiving program except zip.
Your zip file must contain:
1. Design document in PDF format. 50% Describe the design of your O-RING application program. Include
a description your message format for each command implemented for the milestone. Include a time-space
7
diagram for each command implemented to illustrate the order of messages exchanged between two or more
communicating entities, as well as the actions taken on the transmission and/or receipt of a message or other
event. In addition, describe your choice of data structures and algorithms used, other design decisions such as
the number of sockets you chose to use, and a link to your video demo.
2. Code and documentation. 25% Submit all well-documented source code implementing the milestone of your
O-RING application.
3. Video demo. 25% Upload a video of length at most 10 minutes to YouTube with no splicing or edits. This
video must be uploaded and timestamped before the milestone submission deadline.
The video demo your O-RING application must include:
(a) Compilation of your client and peer programs.
(b) Install and run the freshly compiled programs on at least two (2) distinct end hosts.
(c) First, start your server program. Then start 3 peers that each register with the server.
(d) One of the peers should issue a setup-ring command to establish ring topology with 3 nodes, and set
itself as the leader.
(e) Exit the peers; kill the server process.
You must provide output a well-labelled trace the messages transmitted and received at the client/server/peer
so that it is clear what is happening in your O-RING application program.
6.2 Submission Requirements for the Full Project
For the full project deadline, you are to implement the all commands to the server listed in §2. This also involves
implementation of all commands issued between peers that are associated with these commands as described in §3.
Submit electronically before 11:59pm of Sunday, 10/18/2020 a zip file named Groupx.zip where x is your
group number. Do not use any other archiving program except zip.
Your zip file must contain:
1. Design document in PDF format. 30% Extend the design document for the milestone phase of your O-RING
application program to include details for the remaining commands implemented for the full project. As before,
for each command, include a description your message format, a time-space diagram showing actions taken on
the transmission and/or receipt of a message or other event. In addition, describe your choice of data structures
and algorithms used, and a link to your video demo.
2. Code, demo, and documentation. 20% Submit all well-documented source code implementing the milestone
of your O-RING application.
3. Video demo. 50% Upload a video of length at most 20 minutes to YouTube with no splicing or edits. This
video must be uploaded and timestamped before the full project submission deadline.
You video must demo your O-RING application must include:
(a) Compilation of your client and peer programs.
(b) Run the freshly compiled programs on at least three (3) distinct end hosts.
(c) First, start the server. Then start 6 Free peers p1, . . . , p6 that each register with the server. Then, set up
two rings of size 3.
(d) Start 2 additional Free peers p7, p8 that each register with the server. Each of p7 and p8 issues at least
two compute commands.
(e) Tear down one of the rings. Issue compute commands from p7 and p8 and also from one of the processes
freed by the tear down.
(f) Deregister peers p7, p8, and those freed by the tear down.
(g) Tear down the second ring and deregister the processes involved.
(h) Finally, kill the server process.
8
You must provide output a well-labelled trace the messages transmitted and received at the client/server/peer
so that it is clear what is happening in your O-RING application program.
7 For Honours Project Credit
Extend this socket project to:
1. Handle the creation of rings of any size, even or odd. Hence if there is a tie in the orientation algorithm, it should
be run repeatedly until it the tie is broken and an orientation can be formed.
2. In the compute max function, it’s possible that two or more processes select the same integer in which case
there is no unique maximum. Re-run the computation ensuring that the maximum value is unique.
3. Instead of UDP sockets, revise your project to use TCP sockets, or implement reliability yourself on top of UDP.
The deadline for honours project credit is the last day of the course, not the full project deadline.
References
[1] James F. Kurose and Keith W. Ross. Computer Networking, A Top-Down Approach. Pearson, 7th edition, 2017.
[2] Violet R. Syrotiuk and Jan K. Pachl. A distributed ring orientation algorithm. In Proceedings of the 2nd International Workshop on Distributed Algorithms, in Lecture Notes in Computer Science (LNCS), volume 312, pages
332–336, July 1987.