Assignment 2: Air Traffic Control

Outline#

Overview#

You have been commissioned to develop a new Air Traffic Control (ATC) system for Canberra Airport! They would like the system to be able to facilitate network connections between a main “control” server and a distributed network of airport servers, for the purposes of scheduling flight landing times.

They want you to develop a network that is reliable (the program can’t crash) and robust (the program can’t cause planes to crash into each other). As a result, they have asked you to implement it in C.

You have been tasked to create a prototype system that simulates this distributed network over your local machine to act as a proof of concept.

You will need to implement code for both the main “controller” node and each airport node.

Controller#

The controller node will act as a proxy between client requests to your network of airports. You have covered proxies in the Week 8 Networking Lectures already, but here is a graphical reminder nonetheless:

The requirements of the Controller node are that it:

1. Is able to parse requests to schedule flight landing times and query existing flight information.
2. Is able to proxy requests from clients to specific airport servers, based on the parameters of the request.

Airport Nodes#

In this prototype, we use child processes created by the main program to simulate the distributed network of airport nodes. Each airport node contains a variable number of gates and a schedule associated with that gate. The airport nodes contain a schedule associated with each gate.

These gate schedules contain a fixed number of “time slots” that represent the times allocatable to specific aeroplanes. We assume for simplicity that in our prototype we only need to worry about half-hour intervals, and that we only schedule requests for one day (e.g. the number of time slots is 48).

The requests to the airport nodes all require updating or querying these gate schedules.

ATC Network Overview#

The network you will be building consists of a “main” air traffic control process and a variable number of subprocesses representing airport servers. Each airport node server is simulated as a child process created by our main program.

Connecting to Airports#

The program takes in arguments to specify how many airports to create, the specific ports nodes should connect to and how many gates each airport should have. The specifics of the program arguments are described below, but here is a graphical overview for a controller and three airport nodes launched with a starting port of 2310. The list of gates provided (5,10,15) are used to set the number of gates for the 0th, 1st and 2nd airport nodes respectively.

When the program is given a starting port S as an argument (set to 1024 by default), it reserves the port numbers S+1 to S+N for the airport nodes. The controller will keep track of these port numbers to know where to forward different requests.

Request & Response Formats#

The idea of processing a series of commands line by line should hopefully feel approachable and fun by now¹!

Time Slots and Indices#

To simplify the request format, we will specify time slots as indexes into an array of time slots, each of which represents a 30-minute interval. For example, a scheduling request with a starting time given as 5 represents the time 02:30.

Duration values are specified as integer values as well, representing a multiple of 30 minutes.

You may find the following diagram showing the correspondence between index values into the time_slots array useful:

When responses are written as strings, they will need to be converted from these integer values to HH:MM format. We have provided macros in the airport.c file to make this easy for you.

printf("%02d:%02d", IDX_TO_HOUR(idx), IDX_TO_MINS(idx));

Scheduling Requests#

The format of a request to assign a gate at a given airport to specific plane is as follows:

// Format:
SCHEDULE [airport_num] [plane_id] [earliest_time] [duration] [fuel]

// Example:
SCHEDULE 0             1001       2               5          8

The meaning of each of the values (all of which are 4-byte integers) is as follows:

• airport_num: The specific airport to forward the request to (i.e. where the plane wishes to land).
• plane_id: The id number of the plane that wishes to land at the given airport.
• earliest_time: The index of the earliest time slot this plane can land in.
• duration: The number of subsequent slots the plane will need to remain at the gate for.
• fuel: The fuel value is a multiple of thirty minutes that, when added to the starting time, represents the time at which the aeroplane will run out of fuel.

The last three values of the request limit the times at which a flight can be scheduled. Where the “start slot” S is the index at which a flight is first assigned, the following restrictions apply:

1. 0 <= S < NUM_TIME_SLOTS: A flight must be scheduled within the bounds of the schedule.
2. S+duration < NUM_TIME_SLOTS: As we restrict our prototype to scheduling a single day we disallow a plane remaining over midnight into the following day.
3. S <= earliest_time+fuel: Flights must be scheduled (if possible) before they run out of fuel.
4. S >= earliest_time: You cannot schedule a flight earlier than its earliest possible landing time.

In particular, a “fuel” value of 0 means that a plane can only be placed in the time slot specified by “earliest” in a gate, or not at all (we use this fact for testing purposes).

For example, the above schedule request will allow for plane 1001 to be placed at any chunk of 6 adjacent free slots starting at any time between 01:00 and 05:30.

The format of the response depends on whether the flight could be successfully scheduled or not. A successful response will be of the form:

SCHEDULED [plane_id] at GATE [gate_number]: [HH]:[MM]-[HH]:[MM]

With plane_id and gate_number replaced with the plane id and gate number the two HH:MM values are the starting and ending times reserved in the gate for the specific flight.

For example, SCHEDULED 1001 at GATE 0: 01:00-03:30\n is a possible response

An unsuccessful response will be of the form:

Error: Cannot schedule [plane_id]

The following is a graphical representation of what time slots the above example request could be placed in:

The earliest time slots the plane may occupy are between 01:00 and 03:30 as determined by the starting time. The latest time slot that the plane may first arrive in is 05:00.

Flight Lookup Requests#

Once we’ve scheduled landing times for flights, it will be useful for other clients to be able to find out when we scheduled those flights. These requests will be in the following form:

PLANE_STATUS [airport_num] [plane_id]

The meaning of each of the values (all of which are 4-byte integers) is as follows:

• airport_num: The specific airport to forward the request to (i.e. where the plane wishes to land).
• plane_id: The id number of the plane that the client wishes to look up.

These commands are processed by searching each gate in the airport for time slots that are occupied by the given plane. You may assume that all plane ids will be unique (i.e. there will only ever be one request to schedule a flight with id N).

A successful response, where the plane was found in gate gate_num of the airport, will be in the following form. The two HH:MM values are the starting and ending times for the specific flight.

PLANE [plane_id] scheduled at GATE [gate_num]: [HH]:[MM]-[HH]:[MM]

If there is no gate in which plane_id is scheduled at the given airport, the response should be in the following form:

PLANE [plane_id] not scheduled at airport [airport_num]

Gate Information Requests#

The third request type required will allow clients to request information associated with a specific gate:

TIME_STATUS [airport_num] [gate_num] [start_idx] [duration]

This will return the status of the slots between [start_idx]..[start_idx+duration] (inclusive) in the given gate’s schedule.

The meaning of each of the values (all of which are 4-byte integers) is as follows:

• airport_num: The specific airport to forward the request to.
• gate_num: The gate number to return scheduling information for.
• start_idx: The index of the starting time slot to return information for.
• duration: The number of subsequent slots the plane to include in the returned scheduling information.

The format of the response will follow the same format, for each time slot in the range start_idx to start_idx+duration (inclusive).

AIRPORT [airport_num] GATE [start_idx] [HH]:[MM]: [status] - [flight_id]
AIRPORT [airport_num] GATE [start_idx+1] [HH]:[HH]: [status] - [flight_id]
...
AIRPORT [airport_num] GATE [start_idx+duration] [HH]:[HH]: [status] - [flight_id]

The value of status should be either letter A for “allocated” (i.e. a flight is assigned) and F for “free”. If the slot is free, the flight_id should be printed as the number 0.

Forwarding Requests#

Your controller will need to implement a way of parsing requests in the above format. At the very least it needs to determine which airport each individual request needs to be forwarded to before it can connect to the appropriate airport port.

In this assignment we impose no restrictions on how you format requests that are forwarded from the controller to the airport nodes (just that the requests behave correctly). It is up to you to determine what is appropriate for your implementation. If this limitless freedom seems too open-ended to you, we offer the following suggestions:

1. You forward the request line with the airport id stripped out, as it will be redundant information once forwarded to the correct airport node.
2. You retain the airport id and forward the request verbatim. This may be helpful in determining whether requests are forwarded to the correct location.
3. You perform pre-processing or parsing of the full request line before forwarding in a completely different format (such as sending binary data directly).

Regardless of your choice, make sure you document and justify your choice somewhere in the report.

Error Detection & Response Format#

Your implementation should gracefully handle possible errors that may arise from either network connection issues or invalid parameters included in requests.

Regardless of request type, if a request has an invalid airport identifier provided, the controller should respond with a message of the form:

Error: Airport [airport_num] does not exist

An invalid gate number provided in request types in which this is relevant should respond in the following form:

Error: Invalid 'gate' value ([gate_value])

Other error conditions and their messages returned can be seen in the provided test case basic-3.

Finally, in the case of either an invalid request type or invalid arguments passed, you should return a response of the following form, regardless of the specific cause:

Error: Invalid request provided

Concurrent ATC#

To make the ATC network blazingly fast, you will need to extend your implementation to be able to handle concurrent client connections. There are two main places where concurrency can be applied in this network - in the controller and in the airport nodes.

Multi-Threaded Controller#

Once you have a working sequential controller that handles one client’s requests at a time, you should extend it to simultaneously handle multiple clients. The simplest way to implement a concurrent server is to spawn a new thread to handle each new connection request. However, this method creates a substantial amount of additional overhead by spawning a new thread for every single request. A better approach, and the one you should implement is to use a thread pool, where threads are spawned only once and will wait for work to be assigned.

• Note that your threads should run in detached mode to avoid memory leaks.
• The open_clientfd and open_listenfd functions described in the lectures (and included in the provided network utilities code) are based on the modern and protocol-independent getaddrinfo function, and thus are thread safe.
• You should implement a shared queue to handle allocating connfd’s to different threads. See Exercise 3 of Lab 9 for more details.

Multi-Threaded Airport Nodes#

The second part of the program to introduce multithreading into is the airport nodes. You should now introduce the ability for an individual airport to handle multiple forwarded requests at once. This should follow the same approach as for multi-threading in the controller node - distributing requests between different threads in a thread pool. Sounds simple enough!

Ensuring Thread Safety#

The most difficult (and therefore most interesting) part of this extension will be ensuring that accesses to the schedule are thread-safe! For example, suppose you had a completely empty schedule and were concurrently processing the following two requests from two different clients:

SCHEDULE 0 1001 0 2 3 // Client 1 requests to schedule flight 1001
SCHEDULE 0 1002 0 3 5 // Client 2 requests to schedule flight 1002

If you aren’t careful, processing these requests in different threads could result in both flights being assigned the same gate at the same time! You will need to limit access to the schedule to prevent race conditions from occurring.

There are a few approaches to this, with varying levels of effectiveness:

1. The easiest way (and one that will not be considered a valid attempt when marking your code) is to use a “global lock” on the entire airport’s schedule each time a thread needs to read from or write to it. It should be fairly intuitive why this is inefficient.

2. A somewhat more efficient approach would be to use a locking scheme that allows for multiple threads to be able to read from the schedule simultaneously, and only allow one thread to write to the schedule.²

3. A better approach would be to have a more fine-grained locking scheme. Rather than locking the entire schedule, you only lock the schedule of the gate you are interested in.

   Hint: This could be implemented by adding either a mutex or read-write lock to the gate_t struct, which must be acquired before accessing the time slots associated with that specific gate.

4. An even better approach would be to allow locking specific time slots in the schedule. If you wish to check whether slots [i]..[j] are free, you can associate a lock with each individual slot that must all be acquired

This last approach can be very difficult implement in a way that does not cause threads to deadlock. Think about what would could happen when two threads try to lock overlapping regions of the schedule.

Ordering Requirements#

After introducing multithreading to both the controller and airport nodes, you may find that different requests will be processed in a (mostly) arbitrary order. So it doesn’t become too chaotic, we impose the following requirements on request ordering:

1. Individual requests within a client connection must be processed in order.
2. Requests from distinct clients can be ordered arbitrarily.

In regards to the first point, this means that if a client makes the following two requests in a single transaction:

1. SCHEDULE 1 1234 0 1 2
2. PLANE_STATUS 1 1234

The first request to schedule a gate for flight 1234 needs to be processed (i.e. added to the schedule) before the second request for it’s associated flight information.

If these two requests were made by separate client connections however, we impose no restrictions on whether one is processed before the other.

Testing#

There are two ways to run the ATC Network you have build: either interactively, or from a provided testing script.

Running Interactively#

The arguments accepted by the controller program are of the following form:

./controller -n NUM_AIRPORTS -p STARTING_PORT -- [gate count list...]

All argument parsing code has been provided for you already.

Testing Script#

The tests will likely not work if you are using Windows due to DOS line endings. Run the command find tests -type f -print0 | xargs -0 dos2unix -- as well as dos2unix -f run_tests.sh and dos2unix send_requests.sh to convert all the scripts and testing files to use Unix line endings.

We have also provided a testing script for your code, similar to the one used in checkpoint 2. This will automatically run several tests against your code. The testing script launches the network and uses netcat sessions to send different queries to the controller node. It will capture the response sent from the controller, and then checks the responses against an expected file.

We provide the following options to control the behaviour of the testing script:

Marking#

The code is worth 70% of your grade. The report is worth 30% of your grade. As with assignment 1, code style will contribute a small amount to your code mark. This includes (but is not limited to):

• Having clear names for functions and variables
• Having comments explaining what more complex functions do
• Removing any commented out code before submission
• Removing excessive whitespace
• Avoiding leaving an excessive amount of printf statements in your code

1. A correct implementation of a basic sequential network (i.e. no concurrency) will result in a mark in the pass range. Implementations that successfully communicate with 1 airport node will receive a mark lower in this grade band, and implementations that are able to communicate with multiple will receive a higher mark in this grade band.
2. A correct implementation of a network with a concurrent controller server and sequential airport nodes (or vice-versa) will result in a mark in the credit range.
3. A correct implementation of a network with a concurrency controller and concurrent airport nodes with a “basic” locking scheme to protect accesses and modifications to the schedule will result in a mark in the distinction range.
4. A correct implementation of the previous point, but with a fine-grained locking scheme will result in a mark within the high distinction range.

Note that for point (2) and (3) we expect an implementation of a thread pool, as explained above.

Report#

As with Assignment 1, you are required to include a report that explains the details of your implementation. It should be written in the given report.md file as valid markdown and split up into the following sections.

Some of these will be omitted if you did not complete those specific optimisations:

• Overview of your air traffic control network. (100-500 words)
  • You should make it clear what extension tasks you have attempted in this Overview section, but leave the important details until the relevant section later.
  • You should include a high level explanation of how your controller node parses client requests, forwards them to the correct airport node and returns the correct response.
• Request Format used. (100-500 words)
  • Include an explanation of the format you decided to use when forwarding requests from the controller node to individual airport nodes.
  • Justify your decision. Is your approach better for efficiency, or debug-ability (or both!)?
• Extensions: for each of the following extensions you attempt, include a section going into more detail about how you implemented it and what effect (if any) it had on the performance of your network.
  • Multithreading within the Controller Node (100-500 words)
    • How did you implement a thread pool? How did you decide on the number of threads to use? How do you distribute client connections between threads?
  • Multithreading within Airport Nodes (200-700 words)
    • How did you implement a thread pool? How did you decide on the number of threads to use? How do you distribute client connections between threads?⁴
    • How do you protect accesses to the schedule within an airport node? What “level” of locking did you use? How do you ensure your locking scheme does not cause deadlocks or other issues?
• Testing: (100-500 words)
  • You should include at least one of the following (or multiple if they are relevant):
    • Explanation of an implementation challenge encountered in completing this assignment. This could include a difficult bug you faced or a conceptual problem you got stuck on.
    • Explanation of additional tests you created to verify your implementation.
    • If there are any known bugs in your implementation, list them here in this section.

You may also include any other sections that focus on particular aspects of your implementation not listed above.

Hints, Tips & Tricks#

Debugging Advice#

1. Use assertions in your program, especially in the early stages of development.

2. You may find it useful to connect to an individual airport node via netcat (or some other tool) directly.

   When you launch the controller on port X, airport node 0 is assigned X+1, node 1 is assigned X+1 and so on. You will be able to connect to airport 0 with netcat by running the command nc localhost X+1, for example.

3. If you are trying to debug individual airport nodes crashing, you may find it useful to modify the sigchld_handler handler provided in controller.c to report on the reason for specific nodes exiting.

Help! I’m X weeks behind in this course and have no idea what is going on!#

If you want to quickly catch up on the necessary content to complete this assignment, you can use the following guideline of which labs and lectures we recommend completing to understand the tasks associated with each grade band:

• Pass: Lab 8 and the lectures on building sequential network servers
• Credit: Lab 9 and the lectures on building concurrent servers
• Distinction: Lab 10 and the lectures on synchronisation issues in concurrent programs.
• High Distinction: Lab 10 and lectures up to week 12.

Frequently Asked Questions#

My code don’t work, can I email you for help?#

Sorry, you won’t get help over email or Teams. We provide a course forum which is the only way we are able to help outside of labs.

Forum posts related to your assessment submission must be “private” if they contain code or other sensitive information (as for any individual assessment task).

It’s [5 minutes, 60 minutes, 12 hours] before the deadline and my CI Jobs aren’t finishing!#

Unfortunately on the day that an assessment is due, when many students are pushing updates at once, the CI servers can’t keep up. You may not see your CI jobs finish before the deadline. You will just have to manually check that your files have been submitted correctly and that you are passing tests locally.

The best way to avoid this issue is to start early and finish early 😇

If there’s any issues with your git repository, please let us know through a private forum post and there may be something we can do.

How do I know my assessment has been submitted?#

If:

1. the files in your fork of the assessment are correct (i.e., the files you intend to submit) when checking on the gitlab website
2. the time is before the deadline

then your assessment has been submitted (well done!).

Please don’t ask us to “check”, we would be just doing exactly the same thing as the above steps which you can do yourself.