Project 5

Overview

In this project, you will implement an ad hoc routing protocol using minithreads.

Ad hoc networks are an emerging new domain. Typically, nodes in wired networks, like the Internet, or infrastructure-based wireless networks, like the 802.11b network on campus, rely on routers embedded in the networking fabric to ferry their data packets to their destinations. For instance, packets to cnn.com are sent out of campus towards CNN's data center by means of Internet routers over fiberoptic links. Similarly, a wireless host A that wishes to contact wireless host B does so by going through a base station, which sends the data to the base station closest to B, which ultimately forwards it to B. These approaches work fine today, but have some drawbacks:

• The infrastructure (Internet routers, wireless basestations) requires a large initial investment to set up. If the infrastructure is not set up, there is no way for network participants to communicate.
• The infrastructure is costly and difficult to maintain. These devices require expensive administration for their continued proper operation.
• Problems with the infrastructure lead to catastrophic outages.

Similarly, traditional messaging services, such as AOL IM, MSN messenger, Yahoo messenger and others, suffer from the same drawbacks, for analogous reasons. They rely on a single, expensive data center. Every message sent to every user has to go to this single data center, typically somewhere on the west coast, and get sent back to its destination, even if that destination is your best friend sitting next to you.

Every approach to routing has some benefits and drawbacks. We will be taking an approach similar to that used by the internet (BGP), and implementing a simple peer to peer application on top of it.

You will implement a simple datastructure to store mappings from destination to route. You will periodically announce your presence to your peers with a route discovery message. You will append yourself to and forward valid&informative route discovery messages to all of your peers by appending yourself to the route and forwarding it. A valid route discovery message is a message which does not already contain you on the path. An informative route discovery message is one which contains a route that is better than the best you currently have, or which is the same as the one you are using.

In order to test yourcode, we provide you with a simple network emulation layer. This new network emulation layer reads a configuration file that describes the topology of the wireless network to be emulated. If two hosts are not within emulated wireless range of each other, they cannot send packets to each other, even though in reality they may be connected to the same LAN. We have modified network_send_pkt so that when BCAST_ENABLED is enabled, it will only send packets to hosts that are within wireless range. Any other send will fail. The network_bcast_packet() primitive sends a packet to all hosts within wireless range. Broadcasts are useful for route discovery and route reply dissemination; that is, to send packets when you are not sure which way they need to be directed. When you know the destination, you should be using the network_send_pkt function to perform a directed unicast, which is more efficient. When you are ready to run on a real compound network, you will set the BCAST_USE_TOPOLOGY_FILE to 0, and then the broadcasts will be sent using the regular wireless network.

The Details

It is crucial that networking stacks interoperate. To interoperate, all projects need to follow some common conventions and follow the same specification. In order for your implementation to interoperate with those of others in the course, we fixed the format of the packet headers you ought to support in this project. The headers and data-types were provided in project 3. These may not be modified, and your implementation should conform to the specification provided. Routing discovery packets should have type 2 and should contain a single route_msg structure (as defined in minimsg.h) The miniroute layer introduces a new primitive that you should implement. The miniroute_send_pkt primitive allows you to send a unicast packet to a host in the network. It has the exact same signature and provides the exact same functionality as the network_send_pkt function that you are already familiar with from previous projects.

Your routing layer is responsible for interpreting this new message type, dispatching messages of other types to the appropriate handler, and broadcasting your presence to the network. You are also responsible for creating a datastructure to manage known routes.

When a routing discovery message arrives, you should

1. Check to see if the route's size is MAX_ROUTE_LENGTH. If so, discard it and do not process it further.
2. Verify that you are not already on the route. If you are, then you should discard the message and not process it further.
3. Check to see whether the route is shorter than any you have in your route table already (or if it's the one you have in your table already). If the answer to both of these questions is no, discard the message and do not process it further.
4. Insert the route into your route table if necessary.
5. Append yourself to the path (incrementing its length) and forward it to all of your peers.

Your route table should perform the following functions

• Insert route: Add a route to the route table if it is better than the route currently in the table and set a timer to discard it in 30 seconds. If the route is already in the routing table, update the timer so that it goes off 30 seconds from now.
• Get route: Return the best next hop along the best route to the given address.

Finally, you must create a system thread that periodically (every 5s) broadcasts a route discovery packet for yourself.

Since every packet in the ad hoc environment has to be routed, you have to replace any previous call to network_send_pkt with a call to miniroute_send_pkt that, as far as the other levels are concerned, provides the same functionality. Also you have to rewrite the network handler routine. This is the place where you want to deal with the routing issues, such as replying to route discovery requests, propagating data packets along the specified path and forwarding discovery and reply packets).

Four new files were added to this project: miniroute.h that contains the header of routing packets and the declaration of function miniroute_send_pkt and file miniroute.c where you have to add the definition of the function. We also added route_table.h and route_table.cAlso you need to change the definition "#define BCAST_ENABLED 0" in network.h to 1 to enable the broadcast functions in the networking code we have provided. For debugging, you will probably want to use the emulated wireless network, in which case you have to set the value of the symbol BCAST_USE_TOPOLOGY_FILE to 1. When you run the code on Tablets in a real ad hoc network, you will want to set the value of this symbol back to 0. The file network.c is changed slightly to allow the sending of broadcast messages, so please use the updated version.

Broadcasts can be sent by calling network_bcast_packet(), which sends the packet to all accessible nodes. This is a low-level mechanism, like network_send_packet(): it does not know about miniports, and broadcast packets are not distinguished from unicast packets at a receiver. For debugging purposes, nodes accessible by a broadcast are defined by the broadcast topology, which is read from the file named by the constant BCAST_TOPOLOGY_FILE in network.h. A sample topology file, topology.txt, illustrates the format, with an adjoining network graph:

saranac heineken dosequis kingfisher tecate .xx.x x.xx. xx... .x..x x..x.

It is also possible to change the topology at a host at runtime, using the network_bcast_add_link() and network_bcast_remove_link() functions. Changes to the topology are not coordinated between hosts: if tecate removes its link to kingfisher, all the other hosts will have the link recorded. In practice, it doesn't make any sense to remove links for which you're not the source, since it has no effect!

The final part of this project involves running your routing code, with minithreads and miniports to send messages from one machine to another without any kind of infrastructure. If your minisockets do not work, you will have to use minimsgs; under no circumstances should you be sending raw (unencapsulated) data packets at the routing layer.

This will take the form of an Instant Messenging application. Your test program should present the user with a prompt allowing them to send a message to a particular IP address. If that IP address is active and running a copy of your code, the message should appear on the user's screen (with high probability if you're using miniports). As an aside, you should be able to route through a computer running someone else's code (though not necessarily send to this computer).

Extra Credit

Implement proper error reporting and recovery, using a fourth packet type that signals that a particular link in a route was broken. Purge bad entries from the cache in response, and initiate a new route discovery. Make sure you thoroughly test this implementation using dynamic modifications to the virtual topology.

Implement a hybrid routing algorithm, such as SHARP.

Final Word