Assignment #5 - An Open Assignment with Several Default Choices

Submit a project proposal by Tuesday, November 22.

Demo on Monday, December 12.

Assignment Contact: If you work on one of the default choices, you should direct all your questions to the TA. If you design a new assignment outside of the default choices, your contact person is the instructor. Regardless who your assignment contact is, you should always sign up your demo slot with the TA.

This is an open choice assignment. You can choose from five default choices that are given below. But you can also design a brand-new assignment on something that you have particular interests in. If this is what you want, please inform the instructor as soon as possible. If needed, the instructor may help you to define a more specific scope. Any idea can be considered as long as the topic is substantially related to computer networks.

For this assignment, you can choose to work in a team of two if the scope justifies that. If you are not sure if your project warrants a two-person group, please contact the instructor.

In some projects, you will need to work on a wide-area network testbed. If this applies to you, you should arrange with the instructor to set up an account on the PlanetLab testbed.

Demo:
You need to set up a 30-minute demo with the TA. In the demo you need to show us how your project works (or partially works) with your own test cases. (Prepare the testing cases before the demo!) We may ask you to run some of our own test cases and ask some questions about your design & implementation. The demo should occur on Monday, December 12.

Turn-in:
By Tuesday, November 22, you need to submit (using the electronic turn-in) a project proposal. We will not grade the proposal but we need to see evidence that you have started working on it by that time. In the proposal, you should describe a concrete goal of your project, any related materials (papers and web resources) you have read, and anything else you feel relevant. Please keep the proposal within two pages. You need to submit a proposal even if you choose one of the default assignment choices. We only provide rough descriptions for them here and your proposal should list more concrete project goal. The project proposal should be in the PDF format. And note that all turn-ins are done through the electronic turn-in facility. Do NOT send us email attachments.

By the time of your demo, you should turn in your source files, a makefile if needed, and a project report. The project report should clearly describe your overall design, any implementation detail that you deem interesting, how your programs should be compiled and run, and what each member of your group has done. When appropriate (for some assignments), your report should also describe the analysis result for the assignment. In addition to electronically turning in the project report, please also prepare a printed copy at the demo time.

The rest of this page describes the default assignment.

Choice 1: Query Sniffing and Analysis in Gnutella Network
You first need to get a machine in the department lab connected to the global Gnutella Network. Then you need to monitor all the queries forwarded to your machine. Last but not least, after you record a large number of queries, you need to analyze them (using whatever method) and find out if there is any interesting information you can extract from them. For example, do the queries follow any patterns? 50% of your grade will be based on the results/findings of your analysis.

Choice 2: Wide-area Network Bandwidth Measurement
Your task is to develop a tool to measure the network bandwidth between any two nodes in the wide-area network. Your tool should tolerate the unstable nature of wide-area networks. In other words, although the network itself is not stable (with packets loss and cross traffic that affects your measurements), the measured bandwidth between the same two nodes should NOT diverge too much during different runs of your tool and it should correspond well to the actual available bandwidth between the two nodes.

References:

  1. R. L. Carter and M. E. Crovella. Measuring Bottleneck Link Speed in Packet-Switched Networks. Technical Report BUCS-96-006, Computer Science Department, Boston University, March 1996.
  2. V. Paxson. End-to-End Internet Packet Dynamics. In Proc. of the ACM SIGCOMM, pages 139-152, Cannes, France, September 1997.
  3. K. Shen. Structure Management for Scalable Overlay Service Construction (Section 3.2). In Proc. of the First USENIX/ACM Symposium on Networked Systems Design and Implementation (NSDI'04), Pages 281-294, San Francisco CA, March 2004.

Choice 3: Implementation of a Multi-cast Routing Protocol based on RPF and pruning
The requirements are similar to those of Assignment #2, but instead of a unicast routing protocol, you should implement:

  1. A simple mechanism for hosts to join a multicast group.
  2. The reverse path forwarding with pruning protocol to deliver mcast-addressed packets to all hosts that have joined that multicast group.
You can test this assignment using the lab machines.

Choice 4: Web Data Crawling and Collecting
You are asked to build a Web crawler capable of operating in two modes: 1) run at a rate of N pages/second; 2) run at a rate of N bytes/second. With a given starting Web page, your crawler should crawl that page, then follow its hyperlinks to crawl more pages and so on. It should recursively follow the hyperlinks until you stop it or there is no more linked pages to read. In the demo, we will randomly specify a starting page. You should be very carefully in controlling the bandwidth your crawler may use. To avoid undesirable impact on other Web sites, you should not test on pages outside the department until you are quite sure that your program can run properly in the two required modes. After you fetch the pages, you should save them to the local hard drive, e.g., a sub-directory in the "/tmp" partition. Please delete them after you are done with your tests.

Warning: there are some web sites that do NOT welcome crawlers. Before your program tries to crawl on a web site (e.g., www.google.com), it should check if there is a robots.txt file on that site (e.g., www.google.com/robots.txt). See the Robot Exclusion Standard for more information about how robots.txt works.

Choice 5: Application for A Low-power Wireless Router
We have set up a low-power device that consumes about 5 Watts of power. This compares to about 100 Watts power consumption for a conventional computer. This device has limited computing capacity (500MHz CPU) and a small amount of memory (256MB). It contains a compact Flash drive as the storage. It also has a WiFi interface and antennae that allow it to serve as a wireless router. In terms of software, it has a stripped-down Debian Linux distribution that enables it to host most Linux-based applications.

We have installed and experimented with a web proxy cache on this device. Your task in this project is to deploy another network application on this low-power wireless router. It is perfectly fine to port an existing open-source application (originally designed for full-power computer servers). We encourage you to consider an application that is best suited for such a low-power wireless router. In other words, running this application on the router would be better than running it on a full-power machine (typically on a global Internet site). We hope you can identify an appropriate application on your own. But if you need some suggestions, you can consider 1) data transformation to customize for mobile devices and network performance; or 2) interactive multi-player game that requires highly frequent client-server communications. The wireless router provides low-latency to clients (below one millisecond) while an Internet-based server would be at least tens of milliseconds away from the clients.

After deploying the application, if additional time is available, we encourage you to perform experiments to understand and analyze its performance. In particular, we'd like to understand the bottleneck component (CPU, memory space, compact Flash I/O, or network capacity) that limits the application performance.

Due to limited availability of the device, we will only support one team (one or two students) to work on this project.

In the low-power wireless router project, you will work very closely with graduate student researcher Amal Fahad (fahad@cs.rochester.edu). At the same time, you are expected to solve some problems on your own initiative (e.g., installing a needed software tool on the device). If you want to know more about this project or intend to work on it, please contact Amal to discuss more details.