|
|
|
|
|
Project 3: Epidemic Routing
- out: Tuesday February 26
- due: Friday March 14 (midnight)
In this phase, you will explore epidemic style algorithms that can be
used to request and fetch files even when there exists no end-to-end
path between the node requesting the file and the node providing the
file at any given point in time. This style of networking is also
referred to delay tolerant networking.
The system is required to work as follows. An user initiates a file
fetch by specifying a regular expression (such as "*matrix*") that
expresses a pattern for the filename of a desired file.
This request is initially stored locally on the node in a
request table, as it is possible that the node has no direct
radio contact with any other node. When the node comes in contact
with another node, it transmits a list of requests, specified by their
corresponding patterns, to its new neighbor. The neighbor could check
the incoming set of requests and if it has files matching the
requested patterns, then it simply transmits the corresponding files
to the other node. The receiving node then removes the corresponding
request from its list of stored requests. If the new neighbor does
not have a file matching the pattern, it stores the unsatisfied
request in its own request table. Eventually, this file will
percolate back to the requesting user assuming that user mobility
patterns are repetitive, which is what we expect them to be.
Okay, that lays out how the system works overall. Let's now dig into
some of the mechanisms and protocol details required to get the system
to work reasonably well in practice.
Policies:
- Limited range propagation: Clearly, requests should be propagated
to only a limited range. Each request should therefore be
propagated with a ttl value that limits its propagation.
- Limited duration propagation of requests: Similar to range, it
does not seem meaningful to keep around requests that were issued a
while back. It is likely that the user has obtained the desired
file or is no longer interested in it. Therefore, the original
point of time at which the request was initiated must also be stored
along with the request.
- Garbage collecting files fetched on behalf of others: In certain
cases not only would results have to be purged but also the files
that were fetched from other nodes.
We will not specify the exact constants that you should use for the
above parameters. Pick some values that you can meaningfully
justify. The protocol should work independent of what constants you
pick (meaning, what policy you use for garbage collection, etc.).
Protocol:
- We will use TCP for implementing the various mechanisms. It
provides reliability and a connection-oriented transfer, both of
which suit the current model. So begin with your solution for phase
1 of the project and extend it in the following ways.
- For request propagation: the TCP client would connect with the
TCP server and send a message whose first byte is 0x03. This means
that the remainder of the message contains the sequence of requests
that the sending node is currently interested in. The first byte is
then followed by a 32-bit integer which indicates the number of
requests that will be propagated as part of the message.
- Each request will have the following format: a) a 32-bit integer
that specifies the length of the string pattern, b) a string pattern
that corresponds to the request, c) a 32-bit TTL value that is
initialized by the requesting user and decremented at every hop
(with the request being dropped when it hits zero), d) a struct
timeval field (as in one returned by gettimeofday) that contains the
time at which the request was initially made, e) the MAC id of the
original requesting node.
- The TCP server will process the above data, check whether it
contains any of the files matching the requests. If it does have
matching requests, it responds back with a stream comprising of the
following: a) number of matching requests, b) data corresponding to
the file as given below.
- For each matching file it sends: a) the original pattern for
which it found a match -- this again comprises of the length of the
pattern string and the pattern string, b) the filename (length of
filename and the actual string), c) the file itself (length of the
file as a 32-bit integer and the file data).
Well, that is about it in terms of the specification. There are of
course a number of other details that you will have to figure out
yourself, such as how to implement the request table and have it be
persistent across client reboots, etc. Have fun!
|
CSE Home 
