|
|
|
|
|
Project 2: Routing
- out: Monday February 4
- due: Friday February 22 (midnight)
In this phase, you will explore flooding and routing using the link
state routing protocol. In order to accomplish this, we are going to
first clarify the values to be used for the identifier field of the
UDP packets that you used in the previous phase. If the identifier
field is BEACON_MSG = 42 (a value inspired by Douglas
Adams), it is a beacon message. If the value is BROADCAST_MSG = 43,
then it is a packet that needs to be flooded. Further, if it is a
BROADCAST_MSG, the packet format is as follows: Identifier = 43, TTL
value (integer), Sequence number of message (integer), Source MAC
address (12 byte string), Size of message
(integer), Payload (sequence of bytes).
Flooding
Your node "floods" packets with the identifier field set
to BROADCAST_MSG
so that it is sent to all other nodes. You must decide exactly how your
flooding function will work (there is probably more than one choice)
but it must be accomplished subject to the following constraints:
- Flooding must deliver a copy of every packet that is
sent by any node to all of the other nodes.
- Flooding will fail to deliver a copy of a packet to
all other nodes that will process it in a couple of situations. First,
packets can be lost during transmission, e.g., corrupted due to noise
on the wireless link. Second, as part
of the flooding, you must implement functionality
to update the TTL field when packets are forwarded. This will cause
packets to be discarded without being forwarded if their TTL reaches
zero.
- Your flooding design must prevent packets from
circulating indefinitely. This requires that your node works out when
it has already performed its flooding work for a given packet and not
flood it again.
Link State Routing
Your node must then implement link-state routing to contruct a routing
table, and use this routing table to forward packets towards their
destination. You should read about link-state routing in Peterson
4.2.3. Note that we are not implementing OSPF, but a different
and simpler link-state protocol. A link-state protocol generally
involves four steps:
- Neighbor discovery. To determine your current set of
neighbors. You will use the neighbor discovery code that you built out
of beacon messages.
- Link-state flooding. To tell all nodes about all
neighbors. You will use the flooding code from the first part
to disseminate link-state packets.
- Shortest-path calculation using Dijkstra's algorithm.
To build and keep up-to-date a routing table that allows you to
determine the next-hop to forward a packet towards its
destination.
Here are your constraints:
- You should use the following format for link-state
information. A LinkState packet is sent as a BROADCAST_MSG. The
payload of the packet is: a packet identifier field indicating
it is a linkstate packet filled with the value LINK_STATE_PKT=1
(integer) the MAC address of the node sourcing the link state
packet (sequence of 12 bytes), the node's IP address (integer),
number of neighbors (integer), and for
each neighbor, a tuple of values containing the neighbors's MAC
address (sequence of 12 bytes), the neighbor's IP address (integer),
and a link metric (integer = 1 for now).
- A key design
choice is when to send out a LinkState packet periodically?
Immediately after the neighbor list changes? A key design criterion is
to distribute link state information using as few packets as possible,
while keeping nodes as up to date as possible.
- See the details in Peterson for a good suggestion on how
to implement Dijkstra's algorithm. The result of this algorithm should be
a routing table containing the next-hop neighbor to send to for each
destination address. Note that you should not use a link in your routes
unless both ends of the link agree that it is available (that they are
neighbors).
- Each node picks a random IP address. If it sees a link
state packet sourced by a different node (indicated by its MAC
address) who has picked the same IP address, the node simply chooses
a new IP address to avoid conflict, if its MAC address is larger (i.e. the
node whose MAC address is smaller retains the IP address it chose).
You can think of this as randomized DHCP. (Define MAC address A to
be smaller than B if strcmp(A,B) < 0).
- Introduce two new UDP packet types: Ping (identifier = 44)
and PingReply (identifier = 45). Each of them carries the following
payload: Source IP address (integer), Destination IP address (integer).
The Ping and PingReply packets need to be forwarded based on the
routing tables computed by the link state routing algorithm. When
the Ping and PingReply reaches the appropriate destination, emit
some indication that the message was received (through a debug statement,
a pop-up window, or by an audible sound).
Discussion Questions
- Why do we use a link for the shortest path computation
only if it exists in our database in both directions? What would happen
if we used a directed link AB when the link BA does not exist?
- Does your routing algorithm produce symmetric routes (that
follow the same path from X to Y in reverse when going from Y to X)?
Why or why not?
- What would happen if a node advertised itself as having
neighbors, but never forwarded packets? How might you modify your
implementation to deal with this case?
- What happens if link state packets are lost or corrupted?
- What would happen if a node alternated between advertising
and withdrawing a neighbor, every few milliseconds? How might you
modify your implementation to deal with this case?
Turn-In
Turn in your code and answers to the above set of question.
Write only a few short sentences for each of these questions!
Notes
The slides from the help session are available in PDF format here.
Extra Credit
Use the code that you developed above to actual route the
TCP connections though which you can issue the file directory
listing and file fetch commands. Here are some hints to
get you started with this part of the assignment. (This part
is just to get you acquainted with the practical aspect of
networking.)
- Setup the interface IP with the following command that ensures
there are no default routes:
ifconfig wlan0 10.0.0.5 netmask 255.255.255.255
- Setup the kernel route tables to make sure that all of your
transmissions go out on the wireless interface:
route add default wlan0
- Enable packet forwarding on every device:
echo 1 > /proc/sys/net/ipv4/ip_forward
- If neighbor IP neigh is the next hop to the destination
IP dest, you can install a route in the routing table
using:
route add -host dest gw neigh
- After every link state update, you need to remove/update the
route table entries. Take a look at man pages for how route
works.
If you got the above steps to work, you can transparently create TCP
connections that go through other intermediate nodes.
|
CSE Home 
