Project 5

Ad-hoc Networking

Overview

A problem which has stimulated a lot of research in wireless networking is how to allow communication between wireless hosts in the absence of a fixed infrastructure of base stations: typically, for wireless host A to talk to wireless host B, A communicates with a base station on the wired network, which sends the data to the base station closest to B, which forwards it to B. But if there are no base stations or wired network, A and B can still communicate, providing that there is a chain of wireless nodes between them, which are able to communicate with one another. 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 the previous projects the virtual network card was responsible for delivering and receiving a message from any host. Behind the scenes, the virtual network card was using the routing infrastructure of the Internet in order to provide this functionality. In the case of handheld devices equipped with wireless network cards there exists the possibility of communication in the absence of any kind of infrastructure. The goal of this project is to build such an infrastructure that will allow a message from any machine to reach any other machine that is reachable (by means of forwarding the message from machine to machine). The routing algorithm you have to implement is a simplified version of Dynamic Source Routing (DSR).

The datagram and socket based communication that you implemented in the previous projects should be able to use the modified network transport mechanism with a minimum amount of code modification. This can be achieved by providing the function miniroute_send_pkt that has the same signature and provides the functionality identical to the function network_send_pkt that the virtual network card was providing, and by writhing a new network interrupt handler routine that deals with packet routing and, when necessary (i.e. a packet for this machine is received), hands the packet to the old network handler.

In order to allow you to implement the routing algorithm we have provided a network_bcast_packet() function and a set of routines for manipulating a "virtual network topology" in network.h. This function will send a packet to any machine that is within transmission range and it is useful for route discovery and route reply message dissemination. In order to sent a packet to a particular host (that hopefully is within transmission range) function network_send_pkt can be used.

The Details

The successful testing of the code you write in this project depends heavily on the implementation of the same protocol (each implementation has to transmit routing information in the same manner so that machines running some other student's code can collaborate in the routing process). This is the reason why we fixed the information in the routing headers used to exchange routing information and to route messages together with the routing protocol. The headers and data-types are provided in the header file miniroute.h and are fixed. All the information in the header has to be translated to the network representation (using the function htonl) before putting it on the wire and to the host representation when received (using ntohl).

The layout of the information in a packet that is transmitted to another host is the following: routing header, communication protocol header(s) followed by data. There are three types of routing packets that have to be supported by the routing protocol:

In order to avoid the costly process of discovering a route for every packet send 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 (you have to keep track of the time you got the route) the cached route is used to send the data packet; otherwise the route discovery protocol is run to find the route to the destination (the thread calling send_routed_packet) is blocked until the new route is discovered.

Since every packet int 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 (replying to route discovery requests, propagate data packets along the specified path or propagate discovery or 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 purposes you might want to use a synthetic 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 Jornada you might 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 used 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 ("send") 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.
The first section of the topology file gives the names of the computers in the emulated network. After a blank line, the adjacency matrix for broadcasts is given: a dot means there's no link, any other character means there's a link. All links are unidirectional. The diagonal entries are meaningless: whether or not a broadcast at a host is "looped back" and received by the host as well is controlled by the "BCAST_LOOPBACK" constant, by default there is no loopback. Though each host will read the same matrix, only a host's own row is important when sending broadcasts, the rest are ignored. Note that a broadcast is only sent to adjacent nodes, and does not propagate any further! If "saranac" sends a broadcast, it will reach "dosequis", "heineken" and "tecate", but not "kingfisher", unless it is forwarded by heineken or tecate.

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!

Once the code is running on the desktops you have to compile and run it on the Jornadas. To compile the code the Microsoft embedded Tools have to be installed. From the command prompt navigate to the directory where the code for Project 5 is stored and issue the commands: nmake clean; nmake wince. The executable minithreads-arm.exe will be produced (given that you do not have compilation or linking errors) and you can move it on the handheald and run it using ActiveSync.

The final purpose of the project is to have the routing code with miniports of minisockets on top of it on Jornada and to send messages from one machine to another without any kind of infrastructure. You have to do the following on the Jornada to communicate without a central server:

How to get started

Download the new project files.

Submissions

You should follow the generic submission guidelines to submit this project. Make sure you use the correct project number (5).

Final Word

If you need help with any part of the assignment, we are here to help. You may also find the FAQ useful.