ARIZONA STATE UNIVERSITY
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 infor- mation 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.
Leader user4
user0
R
LR
L
State information
O-Ring Server
Oriented ring
Query to ring
Message interaction with server
R
L
user3
user1
user2
L, port labelled left R, port labelled right
1
2
This socket programming project involves the design and implementation of two programs:
1.
2.
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. Thesecondprogramimplementstheclient-sideoftheclient-serverprotocol,aswellasthepeer-to-peerprotocol 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.
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 ⟨user-name⟩ ⟨IPv4-address⟩ ⟨port(s)⟩, 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 ⟨user-name⟩. 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 ⟨n⟩ ⟨user-name⟩, 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̸≥3orisnotodd.
• There are not at least n − 1 other Free users, besides user-name, registered with the server.
2
3
4.
5.
6.
7.
Otherwise, the server selects at random n−1 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.
setup-complete ⟨ring-id⟩ ⟨user-name⟩ ⟨port⟩.Receiptofasetup-completecommandfrom user-name indicates that all the steps required to setup the O-RING with identifier ring-id have been com- pleted. 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 comple- tion 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.
compute ⟨user-name⟩. 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.
teardown-ring ⟨ring-id⟩ ⟨user-name⟩, where user-name is the leader of O-RING. This com- mand 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.
teardown-complete ⟨ring-id⟩ ⟨user-name⟩,whereuser-nameistheleaderoftheO-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.
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 user1 user2
.
IP-addr0 IP-addr1 IP-addr2
.
port0,0 port0,1 port1,0 port1,1 port2,0 port2,1
. .
usern−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 − 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 con- struction 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. RandomlyassignoneofthetwoportnumbersusedforcommunicationintheringthelabelRIGHT,andtheother 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].
IP-addrn−1
portn−1,0 portn−1,1
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 − 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 l of the ring.
(c) Processlsendsasetup-completemessagetotheserverinformingitthatlhasbeenelectedtheleader
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
3. 4.
3.3
(a) sum:Eachprocessinthering,includingtheleader,selectsarandomintegerintherange[0,MAXINT−1]. Theaimofcompute sumistopropagatethesumofalltheintegersselectedbyeachprocessinthering to the leader.
(b) max:Eachprocessinthering,includingtheleader,selectsarandomintegerintherange[0,MAXINT−1]. Theaimofcompute maxistopropagatethemaximumalongtheringtotheleader.
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.
The leader returns a response consisting of the value of the computed function to the process p.
On receipt of the response to the compute function command, the process p prints the output of the function.
Tearing Down an O-RING
The command tearddown-ring deletes the O-RING with identifier ring-id. This is accomplished by the fol- lowing steps:
4
1.
2.
3.
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.
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.
Onreceiptoftheteardownattheleader,itfollowsuits,andthensendsamessagefortheteardown-complete command to the server; see §2 for the parameters of teardown-complete.
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 communi- cation. 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: G × 1000 + 1000, G × 1000 + 1499 . If G mod
2 = 1, i.e., your group is odd, then use the range: G × 1000 + 500, G × 1000 + 999 . That is, group 1 has 22
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
22
6.2
2. 3.
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.
Code and documentation. 25% Submit all well-documented source code implementing the milestone of your O-RING application.
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.
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. InsteadofUDPsockets,reviseyourprojecttouseTCPsockets,orimplementreliabilityyourselfontopofUDP.
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 Inter- national Workshop on Distributed Algorithms, in Lecture Notes in Computer Science (LNCS), volume 312, pages 332–336, July 1987.
9