In this project, you will build an ad hoc routing protocol using minithreads, and implement a peer-to-peer messaging application.
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. And 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:
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 and messaging that does not suffer from these drawbacks. Incidentally, as of the writing of this document (March 2003), you cannot find a commercial implementation of such a communication system. Your task is to write one.
Note that two nodes A and B can communicate in the absence of base stations or 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 Dynamic Source Routing (DSR), 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 messaging 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. And 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 Jornadas or 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 is called miniroute. It 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. The miniroute
layer introduces two new primitives that you should use. The
miniroute_send_pkt primitive allows you to send a
unicast packet to a host within wireless range. 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. The
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
function to perform a directed unicast, which is more efficient.
It is crucial that networking stacks interoperate. To interoperate,
all projects need to follow some common conventions and follow the
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.
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:
typefield in the header has to be set to
destinationcontains the network_address of the destination machine,
seq_numfield is ignored for data packets.
routefield contains information about the route this packet has to follow in order to be delivered to the destination. The first element of the field
routeis the network address of the source machine, the second element is the machine the source will forward to message to if it wants to reach the destination, the i'th element contains the network address of the machine the (i-1)'th machine is forwarding the message to. The last entry is the destination address. The data packets should not be processed by any of the higher level communication protocols on hosts other than the endpoints. The
ttlfield should be set to MAX_ROUTE_LENGTH initially and decremented every time the packet is forwarded by a node along the way. Packets whose
ttlvalue have reached 0 should be silently discarded.
ttlfield should be set to MAX_ROUTE_LENGTH initially. To ensure that the routing discovery packets do not live forever in the network, each forwarding host needs to decrement the
ttlfield by one. If a packet with ttl value 0 of is received or if the machine is already in the route path (accumulated in the field
route) 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. 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.
routefield contains the route in the discovery packet that reached the destination. 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 A->B->C in the discovery phase, you can unicast the route reply packet along the route C->B->A. For this, you will need to reverse the route discovered in the discovery phase. The recipient of the route reply, which is the host that initiated the route discovery, will then reverse the route one more time to obtain the route. Nodes that forward route replies should not add themselves to the route field, or modify it in any other way.
ttlshould be set to MAX_ROUTE_LENGTH initially and decremented every time the packet is forwarded. If
ttlhas 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 send through
the network, you have to implement a route cache with
SIZE_OF_ROUTE_CACHE entries. When a message is sent (using the
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
Since every packet in the ad hoc environment has to be routed, you
have to replace any previous call to
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:
that contains the header of routing packets and the declaration of
miniroute_send_pkt and file
miniroute.c where you have to add the definition of the
function. Also you need to change the definition "
BCAST_ENABLED 0" in
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
Jornadas 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 used
the updated version.
Broadcasts can be sent by calling
which sends the packet to all accessible nodes. This is a low-level
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
network.h. A sample
topology.txt, illustrates the format, with
an adjoining network graph:
saranac heineken dosequis kingfisher tecate .xx.x x.xx. xx... .x..x x..x.
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
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
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.
This assignment also provides a new device and a new interrupt that
enables you to read the keyboard. In addition to the asynchronous interrupt
which is invoked every time the user types a line and presses return,
we provided a very simple device driver for you that allows threads to
synchronously read the keyboard. Once you initialize the keyboard
device by calling
int miniterm_initialize(), you can
int miniterm_read(char* buffer, int len) to
read up to len bytes of keypresses from the keyboard.
The final part of this project involves running your routing code, with minithreads, miniports and minisockets, on Jornada and 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. See Tips for running programs on Jornada systems to see what you have to do on Jornada and Tablets to set up an ad-hoc network. You'll need to build a simple interface by which users specify a node and send a one-line message. The recipient should display that message on the screen. Any user-interface, no matter how primitive, will do, as long as it enables the user to specify the destination and payload for the packet.
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.