实现一个程序，快速查找可用的会议安排时间。
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
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.
