Index>
./client A 1 3 1024
9
Phase 2 (80 points)
In the previous phase, the client receives the query parameters from the user and sends them to the
AWS server over TCP socket connection. In phase 2, the AWS server will have to query server A
and server B for the corresponding map, and forward the map data to server C for calculation if
the map ID and vertex ID has been found.
The socket connection between AWS and server A, B, and C are established over UDP. Each of
these servers and the AWS have its unique port number specified in Port Number Allocation
section with the source and destination IP address as localhost/127.0.0.1/::1.
AWS, server A, B, and C are required to print out on screen messages after executing each action
as described in the “On Screen Messages” section. These messages will help with grading in the
event that the process did not execute successfully. Missing some of the on screen messages might
result in misinterpretation that your process failed to complete. Please follow the exact format
when printing the on screen messages.
Phase 2 can be subdivided into 2 phases. Phase 2A executes map storage while 2B will take the
results from phase 2A and calculate the shortest path, transmission, and propagation delays if the
map exists. Table 1 describes the implementation in detail.
Table 1. Server Operations
Map Storage and Search
In this operation, you will read the data file (map1.txt and map2.txt)
to their respective servers (serverA and serverB). The server will be
ready for query look up from AWS and return the map data if found.
AWS will send the map data only if the map ID and vertex ID
exists.
Path Finding and
Calculation
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, then compute the transmission delay (in s), the
propagation delay (in s), and the end-to-end delay (in s) for
transmitting a file of given size in the selected map.
You are not required to have exact named functions (map construction, path finding and
calculation) in your code. These operations are named and divided to make the process clear.
Phase 2A (40 points)
Phase 2A starts when server A and server B boots up, each server will execute map lookup against
its own database. Server A will read map1.txt while server B will read map2.txt. These servers
will store the map data in a data structure and will send it to AWS if the queried map ID is found
on its server. If the map ID or vertex ID is not found, the server simply notifies AWS and returns
10
to standby.
Server A reads and stores all maps from map1.txt only while serverB reads and stores all maps
from map2.txt only. The queried map ID might not exist in both servers, or might exist in only one
of the servers, but not both. Refer to the “Download Sample Maps” section to obtain the map1.txt
/ map2.txt files.
Phase 2B (40 points)
Phase 2B starts when AWS has received all required data from the client and the servers A,B.
Depending on the lookup result of servers A and B, AWS will perform one of the two operations.
1. If the queried map ID exists in neither A nor B: in this case, server C has nothing to compute
for the shortest path and delay. AWS will print out a message (see the “On Screen Messages”
section) and will not have any interaction with server C.
2. If the queried map ID exists in one of servers, A or B: AWS will forward to server C: 1).
the graph information received from A or B, and 2). the source and destination vertex
indices and file size received from the client. After server C receives the information from
AWS, it computes the shortest path and delay (from the source to the destination vertex)
using Dijkstra’s algorithm (i.e., the “Path finding and calculation” operation in Table 1).
Upon completing the computation, server C will print out the calculation results (see the
“On Screen Messages” section). Finally, server C will send the results to AWS, and AWS
will print out the received data (see the “On Screen Messages” section). This concludes all
the operations of Phase 2B.
Note:
You should decide on your own what information is required to be sent from AWS to server C.
Similarly, it is your own choice what format / data structure to encode the AWS-to-server C and
server C-to-AWS communication. We will grade based on your print out message only.
The goal of server C is to find the path from source to destination with shortest overall delay
(�#$%"&+�'$('). Since for a given graph, all the links within it have the same transmission rate and
we do not use store and forward transmission, the source-to-destination transmission delay,
�#$%"& = ���� ����/������������ ����, is fixed regardless of the route we choose. Therefore, the
path with shortest overall delay is the same as the path with the shortest distance.
If the client’s query is valid, both server C and AWS should print out the calculation result so that
we can give you partial credit if the server C-to-AWS or AWS-to-client communication fail. The
on-screen message should indicate the vertex indices along the path, the total distance of the
shortest path and the delays. Please format your output so the table is clear and readable.
Phase 3 (10 points)
At the end of Phase 2B, backend server C should have the calculation results ready. Those results
should be sent back to AWS using UDP. When the AWS receives the calculation results, it needs
to forward all the results to the client using TCP. The results should include minimum path length
11
between the source and destination node and 3 delays to transfer the file to corresponding
destination. The clients will print out a path and a table to display the response. The table should
include 6 columns. One for source node index, 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.
12
DOWNLOAD SAMPLE MAPS
Samples of map1.txt and map2.txt for this project are available online for download. The data in
these map.txt files are generated randomly for each download and vary in size, but the structure
and data type of the map.txt files are consistent. map1.txt and map2.txt are expected to be read and
stored into serverA and serverB respectively.
Download a copy of map.txt files here:
http://ee450project.us-west-1.elasticbeanstalk.com/
map1.txt and map2.txt will be archived into a single maps.zip for download. Unzip and put the
files in your program directory before using it.
There are no download limits, but both map1.txt and map2.txt should be used together. Do not mix
map1.txt and map2.txt from different maps.zip downloads!
Similar map.txt files with different contents will be used for grading, but you are expected to read
these files without errors.
13
PORT NUMBER ALLOCATION
The ports to be used by the client and the servers are specified in the following table:
Table 2. Static and Dynamic assignments for TCP and UDP ports
Process Dynamic Ports Static Ports
Backend-Server (A) - 1 UDP, 30xxx
Backend-Server (B) - 1 UDP, 31xxx
Backend-Server (C) - UDP, 32xxx
AWS - 1 UDP, 33xxx
1 TCP with client, 34xxx
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: 30319 for the Backend-Server (A), etc.
Port number of all processes print port number of their own
14
ON SCREEN MESSAGES
Table 3. 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 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
vertex
, destination vertex
ID> and file size from the client
After sending information to
server A
The AWS has sent map ID to server A using UDP
After sending information to
server B
The AWS has sent map ID to server B using UDP
After receiving results from
server A or B
The AWS has received map information from server
Check nodes in graph: src
and dst in graph
The source and destination vertex are in the
graph
Check node in graph: vertex
not in graph
graph, sending error to client using TCP over
After sending information to
server C
The AWS has sent map, source ID, destination ID,
propagation speed and transmission speed to
server C using UDP over port
number>
After receiving results from
server C
The AWS has received results from server C:
Shortest path: -- -- … --
Shortest distance: km
Transmission delay: s
Propagation delay: s
After sending results to client The AWS has sent calculated results to client
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
- QQ:99515681
- 邮箱:99515681@qq.com
- 工作时间:8:00-21:00
- 微信:codinghelp
联系我们 - QQ: 99515681 微信:codinghelp
程序辅导网!