实现一个程序，快速查找可用的会议安排时间。
Problem Statement
Finding a time that works for everyone to meet is often a headache issue, especially for a group of people. People often need to exchange availability through back-and-forth emails and allow for several days to finally schedule a meeting. With the help of a meeting scheduler that gives a power to book meetings with users efficiently, users can save hours of time on unnecessary emailing and focus on more important things. There exist some survey tools online to help a group find the best meeting time by manually filling a shared table with their availability. It could however be more productive if the scheduler can maintain the availability of all users and schedule the meeting at the time that works for everyone accordingly.
In this project, we are going to develop a system to fasten the meeting scheduling process. The system receives a list of names involved in the meeting and returns the time intervals that work for every participant based on their availability. To maintain the privacy of everyone’s daily schedule, the availability of all users is stored on backend servers and cannot be accessed by any other servers or clients. Due to a large number of users, more than one backend servers are deployed to store their availability. A main server is then needed to manage which backend server a user’s information is stored in. The main server also plays a role of handling requests from clients.
When a user wants to schedule a meeting among a group of people, the user will start a client program, enter all names involved in the meeting and request the main server for the time intervals that works for every participant. Once the main server receives the request, it decides which backend server the participants’ availability is stored in and sends a request to the responsible backend server for the time intervals that works for all participants belonging to this backend server. Once the backend server receives the request from the main server, it searches in the database to get all requested users’ availability, runs an algorithm to find the intersection among them and sends the result back to the main server. The main server receives the time slots from different backend servers, runs an algorithm to get the final time slots that works for all participants, and sends the result back to the client. The scheduler then can decide the final meeting time according to the available time recommendations and schedule it in the involved users’ calendars.
Without the loss of generality, we assume there are one client, one main server and two backend servers in our project, as indicated in Figure 1. The full process can be roughly divided into four phases: Boot-up, Forward, Schedule, Reply (read details in “Application Workflow Phase Description” section).
- Client: used to access the meeting scheduling system.
- Main server (serverM): coordinate with the backend servers.
- Backend server (serverA and serverB): store the availability of all users and get the time slots that work for all meeting participants once receiving requests.
Source Code Files
Your implementation should include the source code files described below, for each component of the system.
- ServerM (Main Server): You must name your code file: serverM.c or serverM.cc or serverM.cpp (all small letters except ‘M’). Also you must include the corresponding header file (if you have one; it is not mandatory) serverM.h (all small letters except ‘M’).
- Backend-Servers 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 include 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), depending on the server it corresponds to. (e.g., serverA.cpp & serverB.cpp)
Note: You are not allowed to use one executable for all four servers (i.e. a “fork” based implementation). - Client: The name of 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).
Input Files
There are two input files provided, a.txt for backend server A and b.txt for backend server B. Each file is accessible by its corresponding backend server only. The main server or client should not be able to access either of the files. Two files share the same format as follows.
The file contains a list of time availability for a group of individuals identified by their usernames. The format of the time availability information stored in the file for a specific user is provided below.
saylor;[[5,10],[11,16]]
The format of each line will always be username;time_availability, ending with a newline character. Username and time availability are always separated by a semicolon. The username contains only small letter alphabets with a maximum length of 20. The usernames present in both the files are completely unique.
The time availability consists of a list of time intervals in the format:
[[t1_start,t1_end],[t2_start,t2_end]... [t10_start,t10_end]]
Each time interval contains a start and an end time which are always non-negative integers. The start and end times are separated by a comma, and the time intervals are also separated by a comma. The end time will always be larger than the start time, i.e., t[i]_start < t[i]_end, and the start time of the next time interval will always be larger than the end time of the current time interval, i.e., t[i]_end < t[i+1]_start. Each username can contain a maximum of 10 time intervals and a minimum of 1 time interval.
If a user has only 1 time interval then the format would be:
Username;[[t1_start,t1_end]]
The minimum start time for each username has to be at least 0 and the maximum end time of each username can not exceed 100. There can be spaces at any point in the line (except inside a username), you have to remove the extra spaces in your preprocessing. Please find the following examples to see what is a valid or invalid line in the input files:
saylor;[[0,100]]
This is a valid line in the input files.
saylor;[[1,2],[3,4],[5,6],[7,8],[9,10],[11,12],[13,14],[15,16],[17,18],[19,20]]
This is a valid line in the input files.
saylor;[[-1,10.5]]
This is an invalid line because only non-negative integer times are allowed. Such a line will not exist in the input files.
sayl!or;[[a,10]]
This is an invalid line because usernames should have only small letters and no special characters, other than the ones specified. Time intervals will have digits only. Such a line will not exist in the input files.
Saylor;[[1,101]]
This is an invalid line because usernames should only have small letters. Such a line will not exist in the input files.
say lor;[[1,10],[11,12]]
This is an invalid line because usernames should have small letters only and no spaces occur between the letters. Such a line will not exist in the input files.
saylor ;[[1 ,10] ,[11,12] ]
This is a valid line. You should consider “saylor” as the username (ignoring all the whitespaces) and t1_start = 1 and t1_end = 10.
saylor;[[1,1]]
This is an invalid line because end time should always be larger than start time.
Such a line will not exist in the input files.
saylor;[[1,2],[2,3]]
This is an invalid line because the start time of the second interval should be greater than the end time of the first interval. Such a line will not exist in the input files.
Example a.txt and b.txt files are provided along with the project document for you to test your code on, these files contain only 10 lines, but the final grading will be performed on files which can contain up to 200 lines in each file. Your code should be able to handle up to 200 lines in both files. You are encouraged to design more cases including edge cases to test your program.
Application Workflow Phase Description
Phase 1: Boot-up
Please refer to the “Process Flow” section to start your programs in order of the main server, server A, server B and Client. Your programs must start in this order. Each of the servers and the client have boot-up messages which have to be printed on screen, please refer to the on-screen messages section for further information.
When two backend servers (server A and server B) are up and running, each backend server should read the corresponding input file and store the information in a certain data structure. You can choose any data structure that accommodates the needs. After storing all the data, server A and server B should then send all usernames they have to the main server via UDP over the port mentioned in the PORT NUMBER ALLOCATION section. Since the usernames are unique the main server will maintain a list of usernames corresponding to each backend server. In the following phases you have to make sure that the correct backend server is being contacted by the main server for corresponding usernames. You should print correct on screen messages onto the screen for the main server and the backend servers indicating the success of these operations as described in the “ON-SCREEN MESSAGES” section.
After the servers are booted up and the required usernames are transferred from the backend servers to the main server, the client will be started. Once the client boots up and the initial boot up messages are printed, the client waits for the usernames to be taken as inputs from the user, The user can enter up to 10 usernames (all of which are separated by a single space).
After booting up. Your client should first show a prompt:
Please enter the usernames to check schedule availability:
Assuming one entered:
theodore callie
You should store the above two usernames (theodore and callie). Once you have the usernames stored in your program, you can consider phase 1 of the project to be completed. You can proceed to phase 2.
Phase 2: Forward
Once usernames involved in the meeting are entered in the client program, the client forms a message with these names and sends it to the main server over the established TCP connection. You can use any format for the message as long as the main server can receive the correct and intact list of usernames and can extract the information properly for the next step.
The main server first examines if all usernames exist in the database of backend servers according to the username list received from two backend servers in Phase 1. For the usernames that do not exist in the username list, it replies the client with a message saying that which usernames do not exist. For those that do exist, the main server splits them into two sublists based on where the user information is located and forwards those names to the corresponding backend server through UDP connection. Each of these servers have its unique port number specified in the “PORT NUMBER ALLOCATION” section with the source and destination IP address as “localhost” or “127.0.0.1”.
Client, main server and two backend servers 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 does not execute successfully. Missing some of the on-screen messages might result in misinterpretation that your process failed to complete. Please follow the format when printing the on screen messages.
Phase 3: Schedule
Once the backend servers receive the usernames, in order to help each participant schedule a common available time, in this phase, you will need to implement an algorithm to find the intersection of time availability of multiple users.
In the case of one participant, the backend server can directly send the time availability (i.e., a list of time intervals) back to the main server.
In the case of two participants, for example Alice and Bob, the backend server should first search in its database and find the time availability of them. The time availability of Alice and Bob are two lists of time intervals as stated in the “Input Files” section, denoted as
Alice_Time_List=[[t1_start,t1_end],[t2_start,t2_end],...]
Bob_Time_List=[[t1_start,t1_end],[t2_start,t2_end],...]
An algorithm should be developed with Alice_Time_List and Bob_Time_List as the input and output the intersection of time intervals of two lists. An illustration of time intervals and some example inputs and outputs are given in Figure 2, in which the intersection between time intervals [5,10] and [8,11] which is [8,10] are considered as a valid intersection (and the two time lists can have more than one valid intersections). However, the intersection between [15,17] and [17,18] which is [17,17] is NOT an intersection in our scenario because the definition of time intervals requires t[i]_start < t[i]_end and t[i]_end < t[i+1]_start as stated in the “Input Files” section.
In the case of more than two participants, you may run the algorithm for two participants iteratively, and each time find the intersection between the previously found intersection result and the time list of a new participant. You can also develop other algorithms that can directly work for multiple users. An example of the whole process is given as follows. A backend server receives the request for the time availability among Alice, Bob and Amy. The backend server first finds in its database the time availability of them obtaining
Alice_Time_List=[[1,10],[11,12]]
Bob_Time_List=[[5,9],[11,15]]
Amy_Time_List=[[4,12]]
An algorithm is then runned to output the intersection result [[5,9],[11,12]].
At the end of this phase, a backend server should have the intersection result among all participants, which is a list of time intervals, and be ready to send it to the main server. If no time interval is found, the result should be [] as shown in figure 2. The backend servers are required to print out on-screen messages after executing each action as described in the “ON-SCREEN MESSAGES” section.
Phase 4: Reply
During this phase, the backend servers send the intersection result among all participants to the main server via UDP. Once the main server receives the results, the main server runs the algorithm for two participants developed in Phase 3 to identify the intersection between two intersection results received from two backend servers. For example, the main server receives the following intersection results which are two lists of time intervals from two backends servers
result_1=[[6,7],[10,12],[14,15]]
result_2=[[3,8],[9,15]]
Then the main server should feed these time intervals to your algorithm and have the result [[6,7],[10,12],[14,15]] ready. Then the main server sends the intersection result which is a list of time intervals back to the client via TCP.
When the client receives the result, it will print out the result and the prompt messages for a new request as follows:
Time intervals <[time intervals]> works for <username1, username2, ...>.
-----Start a new request----
Please enter the usernames to check schedule availability:
All servers and the client are required to print out on-screen messages after executing each action as described in the “ON-SCREEN MESSAGES” section.
Extra Credits
After showing the meeting time recommendations (i.e., the intersection of all time intervals), a user can decide the final meeting time and schedule it in the involved users’ calendars. In this extra credit part, you should develop a functionality to schedule a meeting in the participants’ calendar. This phase happens after the previous four phases but before starting a new request.
The program should ask the user to enter the meeting time by printing the following prompt:
Please enter the final meeting time to register an meeting:
The user should enter an interval [t_start, t_end] chosen from the recommendations, such as [1, 2].
This entered time interval must be one of the intervals in the recommendations. For example, the recommendations are [[1,3],[8,10],[15,16],[21,23]], then the acceptable meeting times are [1,2] or [2,3] or [1,3], etc.. But [2,4] or [3,5] are not acceptable. Your program should check if the entered time period is valid or not. If it is not valid, you should print a message and ask the user to enter again:
Time interval <[t_start, t_end]> is not valid. Please enter again:
If it is valid, the client should pass the interval to the main server and the main server passes it to the corresponding backend server based on the entered username in Phase 1. The backend servers then remove this time interval from the involved users time availability list, indicating that this time slot is occupied by a meeting. For example, the original availability of a user is [[1,5],[7,8]]. After registering [1,2] as a meeting time, the availability in the database becomes [[2,5],[7,8]]. The backend server should print the on-screen messages showing the updates:
Register a meeting at <time slot> and update the availability for the following users:
<username 1>: updated from <original time availability list> to <updated time availability list>
<username 2>: updated from <original time availability list> to <updated time availability list>
For example:
Register a meeting at [1,2] and update the availability for the following users:
Alice: updated from [[1,2],[7,10]] to [[7,10]]
Bob: updated from [[1,5],[7,8]] to [[2,5],[7,8]]
After updating, the backend server sends a message to the main server indicating that the update is finished. And the main server will notify the client so that the client can start a new request.
NOTE: The extra points will be added to the full 100 points. The maximum possible points for this socket programming project is 110 points.
Process Flow/ Sequence of Operations
- Your project grader will start the servers in this sequence: ServerM, ServerA, ServerB and client in 4 different terminals.
- Once all the ends are started, the servers and clients should be continuously running unless stopped manually by the grader or meet certain conditions as mentioned before.
Required Port Number Allocation
The ports to be used by the clients and the servers for the exercise are specified in the following table.
Note: Major points will be lost if the port allocation is not as per the below description.
Submission files and folder structure: (Additionally, refer #2 of submission rules for more details)
Your submission should have the following folder structure and the files (the examples are of .cpp, but it can be .c files as well):
- ee450_lastname_firstname_uscusername.tar.gz
- ee450_lastname_firstname_uscusername
- client.cpp
- serverM.cpp
- serverA.cpp
- serverB.cpp
- Makefile
- readme.txt (or) readme.md
- Any additional header files
The grader will extract the tar.gz file, and will place all the input data files in the same directory as your source files. The executable files should also be generated in the same directory as your source files. So, after testing your code, the folder structure should look something like this:
- ee450_lastname_firstname_uscusername
- client.cpp
- serverM.cpp
- serverA.cpp
- serverB.cpp
- Makefile
- readme.txt (or) readme.md
- client
- serverM
- serverA
- serverB
- a.txt
- b.txt
- Any additional header files
Note that in the above example, the input data files (ee.txt, cs.txt and cred.txt) will be manually placed by the grader, while the ‘make all’ command should generate the executable files.