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.

The goal of this project is to build a peer-to-peer system for routing that does not suffer from these drawbacks. The next project will build on this framework to implement a peer-to-peer application.

The insight behind ad hoc networks is that two nodes A and B can communicate in the absence of base stations or a wired network if there is a chain of wireless nodes between them that are willing to ferry their packets. This sort of network is called an ad hoc network. The main problems in ad hoc networking are how to adjust to a changing topology as nodes move around, how to minimize bandwidth consumption due to routing overheads, and how to conserve power. In your routing layer, you will attempt to discover routes as the network changes, and use short routes over longer ones to minimize bandwidth and power consumption. The routing algorithm you have to implement is a simplified version of Ad-hoc On-Demand Distance Vector Routing (AODV), a reactive ad hoc routing algorithm. The ultimate goal of the project is to have a collection of wireless nodes self-organize, discover routes and ferry data packets to support a peer-to-peer application, without recourse to any fixed infrastructure.

Of course, if you had to set up a wireless network and physically move the nodes in order to test your routing algorithm, you would get tired pretty quickly. Further, if you had to use a wired network for testing, say a single ethernet segment, you would not be able to exercise the crucial parts of your code; after all, all hosts are visible to all other hosts in one single-hop on an ethernet, and consequently the packet forwarding code would never get tested. That's why we introduce the concept of a network emulation layer in this project. Your minithreads code has been amended with a new layer that emulates a wireless network, even when you are running on a set of wired hosts. This enables you to create an artificial wireless network on a cluster of wired nodes, on which you can thoroughly test your routing layer. Then you can deploy it on the Tablets, where it should work with a minimum of effort. This emulation creates a multi-hop network in which a host A needs to go through host B to get to C. If the virtual topology says that host A is not within wireless range of C, then packets from A, even when they are sent as broadcasts and even when A and C are on the same ethernet segment, are not visible to C. Only C's direct neighbors in the virtual topology, e.g. B, can get packets through to C. This enables you to build complex networks for experimentation in this project.

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 ad hoc 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 are provided in the header file miniroute.h. These may not be modified, and your implementation should conform to the specification provided in that file. 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.

A packet contains a routing header, communication protocol header(s), and then data, in that order. There are three types of routing packets that have to be supported by the routing protocol:

• Data packets: Data packets contain data from the point of view of the routing layer you are implementing. These data packets may indeed be control packets sent by the minisocket layer; regardless, they are simple data packets as far as the routing layer is concerned. The type field in the header has to be set to ROUTING_DATA; destination contains the network_address of the destination machine, from contains the address of the sender, and the seq_num field is ignored for data packets. The data packets should not be processed by any of the higher level communication protocols on hosts other than the endpoints. The ttl field should be set to MAX_ROUTE_LENGTH initially and decremented every time the packet is forwarded by a node along the way. Packets whose ttl value have reached 0 should be silently discarded. A data packet is sent to the next hop on its route based on the distance vector information in a given node's route cache. These route caches are filled by route discovery mechanisms.
• Route discovery packets: Nodes that wish to send packets discover these routes through route discovery packets. The route discovery consists of flooding the network with route discovery packets until the destination is reached. Flooding is achieved by sending the route discovery packet received or initiated on this machine to all the neighbors via broadcast. Each machine that receives a route request:
  • checks the TTL of the request to see if it gives them a better route to the requestor, and if so, records it in the route table as a route through the last hop.
  • decrement the TTL of the request and rebroadcast it if they are not the intended recipient. Otherwise, they reply
  • If they have already forwarded this sequence numbered request from this node, they do not do so again.

  We had said in class that sequence numbers are critical in avoiding counting-to-infinity problems in this part of the protocol. The protocol proposed there, however, is still vulnerable to counting to infinity. Instead of adding the complexity of responding from the cache (which can lead to interesting circular routes being maintained in the network for long periods of time), we will instead always forward the request, even if we have an answer in the cache. We will still continue to add the reverse route (to the requestor) into our cache, since reception of a request packet gives us evidence that this route is good.

  The sequence number should be set by the sending node and each node will increment its sequence number each time it sends a new discovery request.

  The ttl field should be set to MAX_ROUTE_LENGTH initially. A good value of this for your networks will probably be about 8, since we don't have networks of high diameter. In practical versions of AODV, however, the number is set much higher. To ensure that the routing discovery packets do not live forever in the network, each forwarding host needs to decrement the ttl field by one. If a packet with ttl value 0 of is received and if the current machine is not the destination, the packet should not be forwarded. In order for the host to distinguish between route requests, each route discovery request coming from the same machine has to have a different sequence number. A host should not respond to a second request with the same sequence number. Once a route discovery is initiated, the initiator should not wait indefinitely for a response to arrive, since the broadcast route discovery packets may get lost in the network and never arrive at their destination. Consequently, each route discovery initiator should wait about 12-15 seconds for each flood it initiates. If, after three separate attempts to reach the destination, no route response is received, the destination may be presumed to be unreachable, and an error returned to the application.

• Route reply packet: When a route discovery packet reaches the destination machine, an answer has to be sent back to the source machine. The sequence number has to be identical to the sequence number of the route discovery packet for which this is the reply packet. You can assume that the network consists entirely of bidirectional links (because our physical hardware is based on 802.11b, which cannot send a unicast packet unless the link is bidirectional). Hence, if you discover the route from A to C is along B discovery phase, you can unicast the route reply packet first to B to follow the reverse route. The initiator, when it receives the route reply, will use the last hop as the first hop on its route to the destination. Nodes that forward route replies should not modify it in any way other than that the ttl should be set to MAX_ROUTE_LENGTH initially and decremented every time the packet is forwarded. If ttl has value 0, the message is not forwarded anymore. The destination field is the field of the machine that initiated the route discovery request, not the one that sends the reply.

In order to avoid the costly process of discovering a route for every packet sent through the network, you have to implement a route cache with SIZE_OF_ROUTE_CACHE entries. When a message is sent (using the function miniroute_send_pkt), the route cache is consulted. If an entry is found and if the information is not older than 3 seconds, the cached route is used to send the data packet; otherwise the route discovery protocol is executed to find the route to the destination. Route discovery should be synchronous: if discovery needs to be initiated, the thread calling send_routed_packet should be blocked until the new route is discovered or the discovery is retried three times and times out in all three cases. To be able to purge stale routes from the route cache, you may want to rely on your alarms from project 2 to wake up a handler that eliminates old routes. Note that this 3-second cache timeout is meant solely to simplify your implementation, ease cache management, and help your debugging. A real routing protocol would not time out routes unless errors were detected. It would have some extra packet types to signal errors to the endpoints, perhaps perform local route repair, and purge bad entries from the cache. The three second timeout avoids having to implement any of this, and makes errors obvious by placing a load on the discovery and flooding process (but see the extra credit section below).

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).

Two 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. Also 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!

Recall that hosts may have different representations for multi-byte numeric datatypes, e.g. "int"s and "short"s, depending on the byte ordering used in their CPUs. Some CPUs are big-endian, some are little-endian. For instance, x86's use little-endian representation, while StrongARMs may use either little or big-endian representation, depending on the configuration. A large network might contain a mix of big and little-endian nodes. Your code should work correctly on heterogeneous hosts, e.g. a TTL value of 1 should not be interpreted as 4 billion on a host of the wrong-endianness. Consequently, your packet headers, as seen on the wire, should be of a well-known format. Networking people have arbitrarily selected the big-endian format as the wire lingua franca, also known as the network representation. So, you will have to translate all numeric fields to the network representation. You can use the functions htonl for translating from the host to the network ordering, and ntohl for performing the opposite translation. You need to do this for the seqnum, ttl, len fields, as well as each of two longs that make up a network_address_t.

The final part of this project involves running your routing code, with minithreads, miniports and minisockets, on Tablets 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.

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