Socket代写 | EE450 Socket Programming Project

这个作业是实现一个分布式系统，根据内容计算最短路径
EE450 Socket Programming Project
Spring 2020
Due Date:
Friday, April 24, 2020 11:59PM
(Hard Deadline, Strictly Enforced)
The deadline is for both on-campus and DEN off-campus students.
2
ACADEMIC INTEGRITY
All students are expected to write all their code on their own.
Copying code from friends is called plagiarism not collaboration and will result in an “F” for the
entire course. Any libraries or pieces of code that you use and you did not write must be listed in
your README file. All programs will be compared with automated tools to detect similarities;
examples of code copying will get an “F” for the course.
IF YOU HAVE ANY QUESTIONS ABOUT WHAT IS OR ISN’T ALLOWED ABOUT
PLAGIARISM, TALK TO THE TA. “I didn’t know” is not an excuse.
3
OBJECTIVE
The objective of this assignment is to familiarize you with UNIX socket programming. This
assignment is worth 15% of your overall grade in this course. It is an individual assignment and
no collaborations are allowed. Any cheating will result in an automatic F in the course (not
just in the assignment).
If you have any doubts/questions, post your questions on Piazza. You must discuss all project
related issues on Piazza. We will give those who actively help others out by answering questions
on Piazza up to 10 bonus points to the project.
You can ask TAs any question about the content of the project but TAs have the right to
reject your request for debugging.
4
PROBLEM STATEMENT
Many network related applications require fast identification of the shortest path between a pair of
nodes to optimize routing performance. Given a weighted graph �(�, �) consisting of a set of
vertices � and a set of edges �, we aim at finding the path in � connecting the source vertex �!
and the destination vertex �”, such that the total edge weight along the path is minimized. Dijkstra
Algorithm is a procedure of finding the shortest path between a source and destination nodes. This
algorithm will be discussed later in the semester.
In this project, you will implement a distributed system to compute the shortest path based on
client’s query. Suppose the system stores maps of a city, and the client would like to obtain the
shortest path and the corresponding transmission delay between two points in the city. The figure
below summarizes the system architecture. The distributed system consists of three computation
nodes: a main server (AWS), connected to three backend servers (Server A, Server B and Server
C). The backend server A and B has access to a file named map1.txt and map2.txt, respectively,
storing the map information of the city. For simplicity, there is no overlap of map ID between
map1.txt and map2.txt. The AWS server interfaces with the client to receive his query and to return
the computed answer. Upon the request from the client, the AWS server will initiate the search
work in backend Server A and Server B. After searching, AWS server will send the map result to
Server C to calculate the shortest path and different types of delays(propagation delay,
transmission delay and total delay). After calculation, server C will send back the result to AWS.
Then AWS will get it back to the client. If there is no matched map ID, AWS will send
corresponding messages to the client.
Detailed computation and communication steps performed by the system is listed below:
1. [Communication] Client -> AWS: client sends the map ID, the source node and destination
node in the map and the transmission file size (unit: KB) to AWS via TCP.
5
2. [Communication] AWS -> Server A: AWS forwards the map ID to server A via UDP.
3. [Search] Server A searches for the map ID from map1.txt.
4. [Communication] Server A -> AWS: Server A sends the search result via UDP.
5. [Communication] AWS -> Server B: AWS forwards the map ID to server B via UDP.
6. [Search] ServerB searches for the map ID from map2.txt.
7. [Communication] Server B -> AWS: Server B sends the search result via UDP.
8. [Communication] AWS -> ServerC: AWS sends the map information to server C via UDP.
9. [Calculation] Server C calculates the shortest path using Dijkstra Algorithm and
propagation/transmission/total delay.
10. [Communication] Server C -> AWS: Server C sends the shortest path and delay values to AWS
via UDP.
11. [Communication] AWS -> client: AWS sends to client the shortest path and delay results, and
client prints the final results.
The map information of the city is stored in a file named map1.txt and map2.txt. The map1.txt and
map2.txt files contain information of multiple maps (i.e. graphs), where each map can be
considered as a community of the city. Within each map, the edge and vertex information are
further specified, where an edge represents a communication link. We assume edges belonging to
the same map have identical propagation speed and transmission speed.
The format of map1.txt or map2.txt is defined as follows:

For graph finding,
upon receiving the input
query:
The Server A has received input for finding graph
of map
For graph finding, no
graph found
The Server A does not have the required graph id

For graph finding, no
graph found after sending
to AWS:
The Server A has sent “Graph not Found” to AWS
For graph finding,
after sending to AWS: The Server A has sent Graph to AWS
Table 4. Backend-Server B on screen messages
Event On Screen Message
Booting up (Only while
starting):
The Server B is up and running using UDP on port

For graph finding,
upon receiving the input
query:
The Server B has received input for finding graph
of map
For graph finding, no graph
found
The Server B does not have the required graph id

For graph finding, no graph
found after sending to
AWS:
The Server B has sent “Graph not Found” to AWS
For graph finding,
after sending to AWS: The Server B has sent Graph to AWS
15
Table 5. Backend-Server C on screen messages
Event On Screen Message
Booting up (Only while
starting):
The Server C is up and running using UDP on port

For calculation, after
receiving data from
AWS:
The Server C has received data for calculation:
* Propagation speed: km/s;
* Transmission speed KB/s;
* map ID: ;
* Source ID: Destination ID: ;
After calculation:
The Server C has finished the calculation:
Shortest path: — — … —

Shortest distance: km
Transmission delay: s
Propagation delay: s
After Sending the results to the
AWS server: The Server C has finished sending the output to AWS
16
Table 6. AWS on screen messages
Event On Screen Message
Booting up (only while
starting): The AWS is up and running.
Upon Receiving the input
from the client:
The AWS has received map ID

Shortest distance: km
Transmission delay: s
Propagation delay: s
After sending results to client The AWS has sent calculated results to client
using TCP over port
17
Table 7. Client on screen messages
Event On Screen Message
Booting Up: The client is up and running
After
sending
query to
AWS
The client has sent query to AWS using TCP: start vertex
; destination vertex , map

TAs will first compile all codes using make all. They will then open 5 different terminal windows.
On 4 terminals they will start servers A, B, C and AWS using commands make serverA, make
serverB, make serverC, and make aws. Remember that servers should always be on once
started. Client can connect again and again with different input query arguments. On the 5th
terminal they will start the client as “./client