saranac heineken dosequis kingfisher tecate .xx.x x.xx. xx... .x..x x..x. |
|
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.
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:
type field in the header has to be set to
ROUTING_DATA; destination contains the
network_address of the destination machine, seq_num field
is ignored for data packets. route field contains
information about the route this packet has to follow in order to be
delivered to the destination. The first element of the field
path of route is 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 field ttl for data packets
contains the index in the route path array of the current machine
(that received the message). If the machine that received the packet
is not the destination machine, it must forward the message to the
next machine, as specified by the route path (the ttl
field has to be incremented to preserve the meaning). The
forwarding of messages should not involve any of the higher level
communication protocols.ttl. If a packet with value 0 of the field
ttl 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 is not forwarded
anymore. This will ensure that the routing discovery packets do not
live forever in the network (thus using most of the bandwidth). Each
route discovery request coming from the same machine has to have a
different sequence number, in order for the host to distinguish
between route requests.route field contains the route in the
discovery packet that reached the destination and is not modified
along the way back. ttl should be set to MAX_ROUTE_LENGTH
initially and decremented every time the packet is forwarded (by
broadcasting it). If ttl has value 0, the message is not
forwarded anymore (thus allowing the flooding to die out). 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
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. |
|
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: