Project 5: Full Stack Networking

Overview

In this project, you will take a small departure from PortOS to learn about how to build a full networking stack using the C socket interface. You will first implement the socket level calls in order to form point to point connections. In the starter code, there already exists a flooding (gossip) mechanism that allows you to flood messages to all other nodes in the network. Using this mechanism, you will have to implement a link-state routing protocol. Finally, on top of the link state protocol, you will implement a message sending interface that will allow nodes to send messages using the shortest path. For some bonus points, you can implement an application on top of your send message abstraction.

Note that you are writing this using IP, so nodes do not necessarily have to exist on the same computer. If written correctly, you can actually communicate with your friends' (and the TAs') implementations of this project!

One note: while we give you a good amount of skeleton code, you can (and will probably need to) add or change some of the given code.

The Details

There are several distinct components to this project:

  1. For the first part, you will be working in connect.c. In the main() method, you will have to insert code where indicated that does the following:
    • Create a non-blocking TCP socket using the socket() and fcntl() system calls.
    • Set the SO_REUSEADDR option on the socket using the setsocketop()
    • Use bind() to bind the socket to bind_port

    In addition, you will have to make a nonblocking socket in try_connect and server_handler where indicated. After this part, you should be able to compile and run your code. At the prompt, you should be able to connect two machines together using the connect command, which has the form:
    C192.168.2.248:54292
    This will connect your node to another node with IP address 192.168.2.248 and port 54292. You can also use domain names instead of IP addresses in this command.

    In addition, you should be able to gossip messages to each other. Gossip messages have the form:
    G<src_addr:port>/<counter>/<payload>\n
    For now, you will be able to put arbitrary payloads in them. You may have to put a print statement in gossip.c in order to see the gossip protocol working. Later on, you will be changing the gossip protocol so that only link state messages will be flooded. The counter field in the gossip message is simply there for versioning: a higher counter from the same source means that the message has been updated. A node will only keep track of the most recent gossip.


  2. This next part will be work done in link_state.c. Here, you will first implement Dijkstra's shortest path algorithm. The function signature and some utility functions are given here. In addition, node names are strings. However, we give you ways to convert from a string version of a node name to a sockaddr_in and back.


  3. Now, you must implement a flooding mechanism that will broadcast your active connections every time a new connection is formed. This will use the gossip mechanism from part 1. A gossip message will have the form:
    G<src_addr:port>/<counter>/<payload>\n
    where the payload is
    ";<addr1:port1>;<addr2:port2>;<addr3:port3>...\n"
    From this point onwards, your gossip messages must be of this format in order to be interoperable with other solutions. However, the manner in which you implement it is entirely up to you.


  4. Finally, you must implement a link state routing algorithm and a new 'send' message. The send message has a similar format as the gossip format. The main difference is that the address belongs to the destination, not the source and the TTL is the maximum number of hops for this packet.
    S<dst_addr:port>/<TTL>/<payload>\n
    Remember, the link state algorithm must recompute the shortest path every time it receives a new routing update. When doing a send message, it must do the following:
    1. If the send message belongs to you, then print out the payload.
    2. If the send message belongs to someone else, then decrement the TTL by 1 and forward it according to the shortest path.


  5. (Optional) You can implement an application on top of your message abstraction! In fact, most of the things you use the internet for are built on top of a message abstraction like the one you built in this project. One suggestion would be to build a service that will map names to IP addresses (similar to how DNS works). However, the sky is the limit!

Rules of the Road

  1. You only get one header file for your core project: global.h. You are allowed to modify it at will.
  2. When we test your code, we will simply unzip it, remove your application files (application.{c/h}) and run gcc *.c. After that, each run of ./a.out should open up a new node that follows our specification above.
  3. If you decide to make an application, please let us know how to see how it works by documenting it in the README. Any bugs in your application will not hinder your grade on this project since we will be removing the application files while grading.

How to Get Started

Download the Code

The release code on CMS contains the skeleton code for the entire project.

Submissions

Use CMS to submit your project. You should include a "README" file with your name, your partner's name, and anything you think we should know. This includes documenting any broken functionality.

The files you should upload to CMS are: And optionally

Final Word

Start early and have fun.