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 𝑣1 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 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 two backend servers (Server A and Server B). On the backend server A, there is a file named map.txt storing the map information of the city. The AWS server interfaces with the client to receive his query and to return the computed answer. The backend servers, A and B, perform the actual shortest path and transmission delay computation based on the message forwarded by AWS server.
Detailed computation and communication steps performed by the system is listed below:
1. [Communication] Client -> AWS: client sends the map ID, the source node in the map and the transmission file size (unit: bit) to AWS via TCP.
2. [Communication] AWS -> ServerA: AWS forwards the map ID and source node to serverA via UDP.
3. [Computation] ServerA reads map information from map.txt, uses Dijkstra to find the shortest path from input source to all the other nodes and print them out in a pre-defined format.
4. [Communication] ServerA -> AWS: ServerA sends the outputs of Dijkstra to AWS.
4
5. [Communication] AWS -> ServerB: AWS sends to ServerB the file size as well as the outputs of ServerA.
6. [Computation] ServerB calculates the transmission delay, propagation delay and end to end delay for each path.
7. [Communication] ServerB -> AWS: ServerB sends the calculated delay values to AWS.
8. [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 map.txt, stored in ServerA. The map.txt file contains 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 map.txt is defined as follows:
Note:
1. For each map, number of vertices is between 1 and 10
2. We consider undirected, simple graphs:
a. There are no repeated edges or self-loops
b. An edge (p,q) in the graph means p and q are mutual neighbors
3. Units:
a. Propagation speed: km/s
b. Transmission speed: Bytes/s
c. Distance: km
We provide a sample map.txt for you as a reference. We will use another map.txt for grading, so you are advised to prepare your own map files for testing purposes.
Source Code Files
Your implementation should include the source code files described below, for each component of the system.
1. AWS: The server can be viewed as a much simplified Amazon Web Service server. You must name your code file: aws.c or aws.cc or aws.cpp (all small letters). Also you must name the corresponding header file (if you have one; it is not mandatory) aws.h (all small letters).
2. Backend-Server A and B: You must use one of these names for this piece of code: server#.c or server#.cc or server#.cpp (all small letters except for #). Also you must name the corresponding header file (if you have one; it is not mandatory) server#.h (all small letters, except for #). The “#” character must be replaced by the server identifier (i.e. A or B).
3. Client: The name for this piece of code must be client.c or client.cc or client.cpp (all small letters) and the header file (if you have one; it is not mandatory) must be called client.h (all small letters).
Note: Your compilation should generate separate executable files for each of the components listed above.
6
DETAILED EXPLANATION
Phase 1 (10 points)
Boot up: 5 points
Client -> AWS: 5 points
All three server programs (AWS, Back-end Server A & B) boot up in this phase. While booting up, the servers must display a boot up message on the terminal. The format of the boot up message for each server is given in the onscreen message tables at the end of the document. As the boot up message indicates, each server must listen on the appropriate port for incoming packets/connections.
Once the server programs have booted up, the client program runs. The client displays a boot up message as indicated in the onscreen messages table. Note that the client code takes input arguments from the command line. The format for running the client code is:
./client
Phase 2 (40 points+20 points)
In Phase 1, you read the input arguments from the client and send them to the AWS server over a TCP connection. Now in phase 2, this AWS server will send selected input value(s) to the back- server A and B, depending on their functionalities.
The communication between the AWS server and both the backend servers is via UDP. The port numbers used by servers A and B are specified in Table 3. Since both the servers will run on the same machine in our project, both have the same IP address (the IP address of localhost is usually 127.0.0.1).
In Phase 2A, {map construction} operation will be implemented. In Phase 2B, the {path finding} operation will be implemented. In Phase 2C, the {calculation} operation will be implemented (see Table. 2).
Note that all messages required to be printed for the client, AWS server and backend server A, B can be found in the format given in the ON SCREEN MESSAGES table. You can also check the example output in the following part for reference. Please try your best to follow the exact format when you print out the result.
You are not required to have exact named functions (map construction, path finding, and calculation) in your code. These operation is named and divided to make the process clear. And as shown in the instruction, Phase 2A and 2B will together contribute to 40 points when your project is graded.
Phase 2A (2A + 2B = 40 points)
Phase 2A begins when the backend server A boots up. Afterwards, server A will execute the {map construction} operation and read the map data file (map.txt, see the problem statement section). Reading this file will allow A to construct a list of maps. Every map will be identified by its unique ID. After Phase 2A, backend server A will keep this list so that the client can query on any map in this list. AWS will then wait for appropriate user input to let server A perform the {path finding} operation.
Phase 2B (2A + 2B = 40 points)
Phase 2B is initiated when AWS receives all required data from the client. The AWS will forward the
Once finished, the server A will print out a table to demonstrate the minimum length found. The table will include 2 columns (see an example output table in the “ON SCREEN MESSAGES” table). The first column will be the destination node index, the second column will be the minimum length from start node to the destination. Please format your output so the table is clear and
8
readable. Then server A will send all required map information back to AWS.
Phase 2C (20 points)
Phase 2C starts when the AWS receives the corresponding map information from server A. The AWS server will forward both the result and the
The backend server B is a computing server. It performs the operation {calculation} (see Table 2) based on the data sent by the AWS server (please think carefully on your own what information is necessary from AWS, to enable B to complete the calculation). With the given
Table 2. Server Operations
Map Construction
In this operation, you will read the data file (map.txt) to construct a list of maps (i.e., graphs). For each map, you will book-keep the edge information including length, propagation speed and bit rate.
Path Finding
In this operation, you will find the path of minimum length from a given start vertex to all other vertices in the selected map, using Dijkstra algorithm. You also need to print out a simple 2-columns table to show the result.
Calculation
In this operation, you compute the transmission delay (in ms), the propagation delay (in ms), and the end-to-end delay (in ms) for transmitting a file of given size in the selected map.
9
Phase 3 (15 points)
At the end of Phase 2C, backend server B should have the calculation results ready. Those results should be sent back to the AWS using UDP. When the AWS receives the calculation results, it needs to forward all the result to the client using TCP. The results should include minimum path length to all destination node and 3 delays to transfer the file to corresponding destinations. The clients will print out a table to display the response. The table should include 5 columns. One for destination node index, one for path length and the other three for delays.
Make sure you round the results of three delay time to the 2nd decimal point for display. Round the result after summing 𝑇𝑡𝑟𝑎𝑛𝑠 and 𝑇𝑝𝑟𝑜𝑝 along a path. Do not sum rounded 𝑇𝑡𝑟𝑎𝑛𝑠 and rounded 𝑇𝑝𝑟𝑜𝑝 as your total delay.
See the ON SCREEN MESSAGES table for an example output table.
10
PORT NUMBER ALLOCATION
The ports to be used by the client and the servers are specified in the following table:
Table 3. Static and Dynamic assignments for TCP and UDP ports
Process
Dynamic Ports
Static Ports
Backend-Server (A)
–
1 UDP, 21xxx
Backend-Server (B)
–
1 UDP, 22xxx
AWS
–
1 UDP, 23xxx
1 TCP with client, 24xxx
Client
1 TCP
NOTE: xxx is the last 3 digits of your USC ID. For example, if the last 3 digits of your USC ID are “319”, you should use the port: 21319 for the Backend-Server (A), etc.
11
ON SCREEN MESSAGES
Table 4. Backend-Server A on screen messages
Event
On Screen Message
Booting up (Only while starting):
The Server A is up and running using UDP on
port
For map construction, after constructing the list of maps
The Server A has constructed a list of
maps:
——————————————-
Map ID Num Vertices Num Edges
——————————————-
A 9 15
B 7 25
…
——————————————-
For path finding,
upon receiving the input query:
The Server A has received input for finding
shortest paths: starting vertex
For path finding,
after finis1hing Dijkstra:
The Server A has identified the following
shortest paths:
—————————–
Destination Min Length
—————————–
1 10
2 20
7 21
…
—————————–
For path finding,
after sending to AWS:
The Server A has sent shortest paths to AWS.
12
Table 5. 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 calculation, after receiving data from AWS:
The Server B has received data for calculation:
* Propagation speed:
* Transmission speed
* Path length for destination
* Path length for destination
*…
After calculation:
The Server B has finished the calculation of
the delays:
————————
Destination Delay
————————
1 0.30
2 0.35
7 0.33
…
————————
ending the results to the AWS server:
The Server B has finished sending the output to
AWS
After s
13
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