CSE logo University of Washington Computer Science & Engineering
 CSE 461: Computer Communication and Networks (Winter 2008)
  CSE Home   About Us    Search    Contact Info 

Course home
 Using course email
 Email archive
 Lectures and readings
 Section and tutorials
 Midterms and exams
Lab information
 Getting lab accounts
 Unix tutorials

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.


  1. 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.

  2. 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.

  3. 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.).


  1. 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.

  2. 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.

  3. 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.

  4. 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.

  5. 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 logo Computer Science & Engineering
University of Washington
Box 352350
Seattle, WA  98195-2350
(206) 543-1695 voice, (206) 543-2969 FAX