EE450 Socket Programming Project
11:59pm April 23, 2021
In this project, you will implement a simple application to generate customized resource allocation based on user queries. Specifically, consider that USC students in different locations in LA want to schedule appointments for COVID-19 testing. They would send their queries to the USC health center (i.e., scheduler) and receive the location of an available hospital as the reply from the same scheduler. Nowadays, the medical network is so large that it is impossible to store all the information in a single machine. So we consider a distributed system design where the scheduler is further connected to many (in our case, three) hospitals. Each hospital stores its own capacity, availability and the map of LA. Since users and hospitals are all in LA, they will share the same map. i.e., hospitals A, B and C store the same map. Therefore, once the scheduler receives a client query, it decodes the query and further sends a request to the appropriate hospitals. Each of the hospitals will calculate a score according to its own availability and the distance to the client. Then, each hospital will reply to the scheduler. Finally, the scheduler will assign the client to the hospital with the highest score, and inform the client and the hospitals of the decision.
The detailed operations to be performed by all the parties are described with the help of Figure 1. There are in total 5 communication end-points:
- ● Client: representing a student, who can locate anywhere in LA.
- ● Scheduler: responsible for interacting with the client and the hospitals
- ● Hospital A, Hospital B and Hospital C: responsible for calculating the matching scores
based on the query
○ For simplicity, the map of LA is stored as a single text file, and will be read by all
The full process can be roughly divided into four phases (see also “DETAILED EXPLANATION” section), the communication and computation steps are as follows:
- [Computation]: Hospital A, B and C read the file map.txt, and construct a list of
“graphs” (see “DETAILED EXPLANATION” for description of suggested data structures for graphs).
- ○ Assume a “static” map where contents in map.txt do not change throughout the entire process.
- ○ Hospitals only need to read map.txt once. When Hospitals are handling client queries (in “Scoring” phase), they will refer to the internally represented graphs, not the text files.
- ○ There is only one file map.txt.
- [Communication]: Scheduler will establish the connection to each hospital, and obtain
the initial availability of the hospitals.
- [Computation]: Scheduler will construct a data structure to book-keep the availability
from step 2. When the client queries come, the Scheduler can send a request to the available Hospitals.
1. [Communication]: The client sends its query to the Scheduler.
○ The client can terminate itself only after it receives a reply (in the “Reply” phase). 2. [Computation]: The scheduler decodes the query and decides which hospital(s) should
handle the queries.
1. [Communication] Scheduler constructs a message based on client query, and sends such
a message to those available Hospitals.
- [Computation]: Each Hospital performs some operations on the graph / map for distance calculation (you can choose any shortest path algorithm you like). You need to combine the hospital-client distance and hospital availability to get the final score (see “DETAILED EXPLANATION” for the algorithm of computing the final score).
- [Communication]: Each Hospital sends the score to the Scheduler.
- [Computation]: Scheduler decodes the messages from Hospitals and then decides which
hospital the client should go to.
- [Communication]: Scheduler prepares a reply message and sends it to the Client, and
also sends a message to the selected Hospital to let it update its occupancy / availability.
- [Communication]: Client receives the decision from Scheduler, and then terminates
- [Computation]: Selected Hopital updates its availability.
The format of map.txt is defined as follows.