Programming Assignment 4 Solution

For this assignment, you will extend the vote counting idea we have been working on for the last three assignments to a networked vote counter. In the real world, votes have to be transmitted from where they are counted to more central locations to be properly summed and recorded. You will implement this application in a client-server model, meaning that you will have two programs, a client and a server, which will communicate using a protocol we define. Let’s start with a review of the underlying data structure of our vote counter applications, the voting region DAG, and the differences in this assignment.







Don’t let the 14 pages scare you, there’s a lot of tables that take up a lot of space.




1) The DAG







As in previous assignments, we consider a DAG as in the below figure:







Recall from previous assignments, we have the root node, aggregator nodes, and leaf nodes. In previous assignments we have operated under the understanding that votes can only be added to leaf nodes, and are then aggregated until the final root node. We continue this pattern here, but add the concept of polls.




In real life, voting areas have polling places where votes are cast. These polling places are opened to begin voting, then closed at the end of voting. We add this concept here, where each node not only has the summed votes in it, but also a boolean flag indicating whether its polls are open or closed. Polls must be opened prior to adding votes, closed prior to the final count, and cannot be reopened after closing. Even though they cannot have votes added to them, we give aggregator nodes and the root node a flag for polls as well. The polls of an aggregator node or the root node should be open if any of their children have open polls, and closed if they are not. Additionally, any change made to the polls of a node with children should be reflected in its children.







To sum up, all nodes contain the current votes for each candidate and a flag indicating if the polls are open. Votes can only be added directly to leaf nodes, and the votes of an aggregator node are the sum of its children’s votes. While we can open or close the polls of any node, they are affected hierarchically (opening an aggregator node’s polls opens its childrens, closing all of an aggregator children’s polls closes the aggregator’s polls).







2) The Server










The server is responsible for reading a DAG input file (in the same format as in PA3, more info later), maintaining an accurate data representation of the DAG, and properly responding to all requests from clients, as well as printing out relevant information to STD_OUT. The server should be able to operate on any port passed to it from the command line, accept and maintain connections from 1 up to 5 clients.




The usage of your server program should be as follows. You must use the executable name “server”.







./server <DAG FILE <Server Port




Where




<DAG FILE is the file containing the specification of the DAG, under any filename.




<Server Port is any unsigned integer to be used as a port number.




Again, your server is meant to load the DAG into memory, then wait for connections on the specified port. When it receives a connection, it should spawn a new thread to handle that connection, as long as you do not have the maximum number of connections currently active. The thread which handles the connection will be responsible for reading the client’s commands from a socket set up between them, doing the necessary computation on the DAG (including summing votes, opening and closing polls), and sending responses to the client back through that socket. Summing votes and propagating them up the tree will have to be done synchronously, and also done immediately after receiving the request (greedy execution, no waiting). The same applies for opening or closing polls.




The information the server should print out includes:




 
“Server listening on port <PORT_NUMBER”




 
“Connection initiated from client at <CLIENT IP:<CLIENT PORT”




 
“Request received from client at <CLIENT IP:<CLIENT PORT, <REQUEST_CODE”

 
“Sending response to client at <CLIENT IP:<CLIENT PORT, <RESPONSE_CODE”

 
“Closed connection with client at <CLIENT IP:<CLIENT PORT”




<CLIENT_ID should​ be the IP of the client connected. Please follow the format of these prints closely.







3) The Client







The client is responsible for initiating a connection with the server on the IP and port given to it, reading a file containing requests to send to the server (more info later), sending those requests to the server, and printing out the relevant information to STD_OUT. A client only needs to connect to one server at a time.




The usage of your server program should be as follows. You must use the executable name “client”.







./client <REQ FILE <Server IP <Server Port




Where




<REQ FILE is the name of a file containing the requests to be sent to the server.




<Server IP is the IP of the server to connect to.




<Server Port is the port of the server to connect to.




Again, your client should connect to the specified server, then send it the requests as defined by the <REQ FILE, print out relevant information to STD_OUT, then close the connection. When the request involves adding votes to an area, the line in the <REQ FILE will contain a filename containing the name of a file which contains the raw votes (candidate names, one vote per line). The client will have to sum the votes and send the total votes per candidate to the server.




The information the client should print out includes:




 
“Initiated connection with server at <SERVER IP:<SERVER PORT”




 
“Sending request to server: <REQUEST_CODE”




 
“Received response from server: <RESPONSE_CODE <RESPONSE_DATA”




 
“Closed connection with server at <SERVER IP:<SERVER PORT”




Please stick closely to this output format.




The overall operation should look like this. The communication between the server and client will be done using our application-layer communication protocol, below.

Figure 1: Example structure with DAG.

4) Communication Protocol










For this assignment, communication protocol is an application-layer protocol formed of requests and responses. Requests will be sent from the client, received by the server, and after the server does any necessary computation, responded to by the server. These requests and responses will be strings with the following structures.




4.1) Requests










The request structure is as follows, with each field being separated from the other by a semi-colon, and the entire string being delimited by the string terminator ‘\0’. This is the single ASCII character ‘\0’.




Table 1: Request Structure




Field Name
Size (chars)
Purpose






Request code
2
Specifies the request. See




Table 2






Region Name
15
Specifies the region the




command should operate




on. Padded with spaces, if




empty, fill with only




spaces






Data
Arbitrary
Relevant data for the




command (i.e. votes to add




or remove). Not necessary




for all commands, may




simply be left empty.






Terminator
1
‘\0’, marks the end of the




command packet.






Table 2: Request Codes




Request Name
Request Code
Uses Region
Uses Data?




Name?










Return_Winner
RW
No
No








Count_Votes
CV
Yes
No








Open_Polls
OP
Yes
No








Add_Votes
AV
Yes
Yes








Remove_Votes
RV
Yes
Yes








Close_Polls
CP
Yes
No











Each request is below, along with the action it represents in relation to the DAG.




 
Return_Winner




 
This request asks for the winner of the election, the candidate with the majority of the votes over all areas. Requires that the polls have been opened and closed in all areas.




 
Count_Votes




 
This request asks for the candidate who has the most votes in the specific region given (and all sub-regions). This does not require that the polls be closed in this area, nor that they be opened, but should return correct data always. If there are no votes yet, return “No votes.”




 
Open_Polls




 
This request opens polls for voting in an area. MUST be called before changing votes or closing polls. Respond with a poll failure (PF) error if already open.




 
Close_Polls




 
This request closes the polls for a given area. Must be called for an area for which polls have been opened. Respond with a poll failure (PF) error if already open.




 
Add_Votes




 
This request adds votes to a given area. Polls must have been opened in this area, and not closed. Candidates that have not been seen before should be added, and not all candidates recorded in the region must be present in the command. Candidates who are neglected should be ignored.




 
Remove_Votes




 
This request removes vote from a given area. Polls must have been opened in this area, and not closed. Candidates that have not been seen

before should be ignored, and not all candidates recorded in the region must be present in the command. Candidates who are neglected should be ignored. If a candidate’s votes are subtracted to 0, set the candidate to 0.







Request format examples:







“RW; ;\0”​-- Return winner overall. No region or data is needed.




“OP;County_1;\0” ​-- Open polls for County_1. No more data besides the region name is needed.




“AV;Count_1;A:1,B:3,C:4,D:5\0” ​-- Add votes to County_1.










4.2) Responses










The form of the responses is below. Again, each field is separated by a semicolon, and the whole command is terminated by a ‘\0’ character.




Table 3: Response Structure




Field Name
Size (chars)
Purpose






Response code
2
Specifies the response, see




Table 4.






Data
Arbitrary
Returned data from the




server.






Terminator
1
‘\0’, marks the end of the




command packet.






Table 4:Response Codes




Response Code
Meaning
Returns Data?
Data Returned








SC
Success
Sometimes
Varies, See Table 5






below.








UE
Unhandled error
No
N/A








UC
Unhandled
Yes
Command


Command












NR
Region does not
Yes
Name of region


exist












RO
Region(s) not
Yes
Name of region


closed. Caused by






Return_Winner






requests with open






regions.












RC
Region(s) not
Yes
Name of region


opened. Caused by






adding or






removing votes






with to a closed






region.












RR
Polls cannot be
Yes
Name of region


reopened. (already






closed or votes






have been added)












PF
Poll failure. Either
Yes
Name of region and


opening an already


its current state,


open region or


i.e. “County_1


closing a closed


open.”


region.












NL
Not leaf region,
Yes
Name of region


cannot add or






remove votes.












IS
Illegal subtraction
Yes
Name of candidate








Table 5:Data Returned on Success




Request Command Name
Data Returned On Success




Return_Winner
“Winner:A”, A being the correct


candidate name.




Count_Votes
Current count of votes for region in


format: “A:12,B:15,C:20”




Open_Polls
No return.




Add_Votes
No return.




Remove_Votes
No return.




Close_Polls
No return.







Response format examples:







“SC;\0” ​-- Returns success, no data.




“SC;Winner:A\0” ​-- Returns success, with data.




“UE;\0” -- Returns general failure, no data.




“NR;Region_99\0” ​-- Returns specific failure code with related data.










This covers the communication protocol. Next we’ll talk about input files.




5) Input Files







In this section, we will cover the input files for the server and client.










5.1) DAG Files (Server)







On the server side, we need to have a format for the DAG file. This will be the format used in Project Assignment 3, where every node is listed followed by its children, delimited by colons. An example, which matches the DAG shown in Figure 1 follows below:







Who_Won:Region_1:Region_2




Region_1:County_1

You can assume that all regions have unique names that are between 1 and 15 characters long, composed of letters, numbers, and underscores, and that a DAG file will always have a Who_Won file.




5.2) Command Files (Client)







On the client side of things, we need a format to define the commands we want the client to send to the server. These commands are stored in a commands.txt file, in the following format:







Each line is a command. The command starts with the name of the command (as in the above table, i.e. Add_Votes), then the relevant data. For all commands except Return_Winner, there is some relevant data. All other commands have a region name, and then Add_Votes and Remove_Votes have filenames for the vote changes after that. These fields are delimited by spaces.




An example follows below. In this example, the same DAG used in the previous examples has each area opened, adds votes to a few areas, gets an intermediate update using Count_Votes, removes votes from one area, then has the areas closed and gets the winner.













Open_Polls Who_Won




Add_Votes County_1 County_1.votes




Add_Votes Region_2 Region_2.votes




Count_Votes Region_1




Count_Votes County_1




Remove_Votes County_1 fake.votes




Count_Votes County_1




Count_Votes County_99




Close_Polls Who_Won




Open_Polls County_1




Return_Winner

Examples







The series of requests and responses produced by the commands above being sent to a server containing the DAG defined above by a client sending the commands defined above would look like this. Exact vote data may not be accurate.




Command In Command File
Request From Client
Response From Client






Open_Polls Who_Won
OP;Who_Won;\0
SC;\0
Add_Votes County_1 County_1.votes
AV;County_1;
SC;\0


A:5,B:1,C:5\0


Add_Votes Region_2 Region_2.votes
AV;Region_2;
SC;\0


A:1,B:5,C:10,D:6\0


Count_Votes Region_1
CV;Region_1\0
SC;No votes.\0






Count_Votes County_1
CV;County_1\0
SC;A:1,B:5,C:10,D:




6\0
Remove_Votes County_1 fake.votes
RV;Count_1;A:1,C:2
SC;\0


\0


Count_Votes County_1
CV;County_1\0
SC;B:5,C:8,D:6\0






Count_Votes County_99
CV;County_99\0
NR;County_99\0






Close_Polls Who_Won
CP;Who_Won;\0
SC;\0






Open_Polls County_1
OP;Count_1\0
RR;County_1\0






Return_Winner
RW;;\0
SC;Winner:C\0






Convenient Assumptions and Hints










 
We will release synchronized multithreading code examples to help you. They will not be for copy-and paste, however.




 
You should use TCP sockets, because the order for messages matter.




 
A client only needs to connect to a single server at any time.




 
A server needs to consider multiple clients at a time.




 
Candidate names have an upper bound of 100 characters.




 
Region names have an upper bound of 15 characters.




 
A max of 100 candidates and 100 regions is permissible.




 
You will need to keep your DAG in memory. There are no files to output.




 
You will need to synchronize your DAG.




 
To pick your port number, use the last four digits of your student number




 
First get a single client and server pair working, then try multiple clients




 
Start on local host, then later work on multiple machines.




Useful Functions










You will use the standard socket functions, including ​socket(), bind(), connect(), listen(), accept(), send(), recv(), close(), shutdown().​ You will also need to use pthread functions, including synchronization structures such as mutex locks. It is important that you ensure synchronized behavior for the DAG so that you don’t get incorrect vote sums.













Extra Credit










For the extra credit, you will also implement a command which adds a new region to the DAG on the fly. You can only add a region as a leaf (the child of a region, no children of its own). Once the region is added, you should print a message to STD OUT, and the region should function properly. To test this, use a DAG input file with only the Who_Won region, and add every other region using this command. You do not need to consider adding a node if there are no nodes, you can assume that there will at least always be a Who_Won region.







The command will be as follows:

Command Name
Command Code
Uses Region?
Uses Data?








Add_Region
AR
Yes
Yes











The region should be the region which will be the parent of the new region, and the Data will be the name of the new region. So, to add a Subcounty_1 to County_1, the following command should be used.




“AR;County_1;Subcounty_1\0”







Submission










For your submission, please turn in all of the files needed to compile your client and server. Do not turn in the executables, turn in the source files. Also turn in a Makefile, and a README with the following format:




Names: <Student_1, <Student_2




X500’s: <Student_1, <Student_2




Lecture Section: Student 1 is in section 01, student 2 is in lection 10.




Extra Credit: <Put whether you are doing the extra credit here




Additionally, put any other information about your submission here.




Files you should be turning in:




 
Client source files




 
Server source files




 
Makefile




 
README




Put all of your files in the root of your zip file. Save yourself points: unzip the folder and make sure everything is in the root, then try to compile and run it. Do not turn in any unnecessary files, do not turn in any test cases.




Again, only one member of your group should turn in the zip.




Grading










A complete rubric will be released at a later date. You should expect some points to depend on a proper submission, some for your makefile and readme, and then the rest of your points to be split evenly between the client and the server. Most of these points will be based on functionality testing, but some will be given for coding style and comments. The rubric will follow the form:




5 pts -- Submission format




5 pts -- ReadMe




5 pts -- Makefile




10 pts -- Client source file(s), style and comments.




10 pts -- Server source file(s), style and comments.




Single-Client Case




5 pts -- Client operates (Reads commands.txt,connects, sends and receives.)




5 pts -- Server operates (Reads DAG.txt, connects,receives and sends.)




5 pts -- Server handles error cases.




Multi-Client Case




5 pts -- Server maintains multiple client connections (Maintains order)




5 pts -- Server maintains synchronization.




Test Cases




40 pts -- Test cases, evenly weighted, variety of command orders and DAG complexities




10 pts -- Extra Credit




-------------------




Possible 110 points.




A complete rubric, the testing server and client executables, and some test cases will be released at a later date. You should be able to use our server to test your client and vice versa.




Have fun!