Assignment #5 - Multiple Choices
Submit a preliminary report by November 25 (Tuesday).
Demo on December 9 (Tuesday).
Optional presentation on December 10 (Wednesday).
This is an individual assignment, so each person should work on his/her own.
In this assignment, you can choose one of four topics that are given below.
Choice 1: Web data crawling
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 it is explicitly stopped.
In the demo, we will randomly specify a set of starting pages. You should
be very careful 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
While search engines like Google broadly crawl data on the Web, most often
Web crawlers are used to collect data on a specific topic (e.g. golf,
computer science, or network security). To obtain the full credit, your
crawler should be able to focus the crawling on Web pages of a chosen
topic (specified by a word or a multi-word phrase). This requires an
intelligent prioritization on which pages to crawl first.
Warning: Many Web sites
do NOT welcome crawlers or request crawlers to behave in restrictive ways.
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
Exclusion Standard for more information about how robots.txt works.
Choice 2: Implementation of a multi-cast routing protocol
The requirements are similar to those of Assignment #2, but instead of
a unicast routing protocol, you should implement:
You can test your multicast system using a set of lab machines.
- a multicast routing protocol,
- a simple mechanism for new hosts to join the multicast group,
- a fault tolerance mechanism to automatically repair the multicast group when a node suddenly leaves the multicast (e.g. due to a machine crash).
Choice 3: Wireless network performance measurement
If you have a programmable wireless device (e.g. a laptop), you can conduct
some interesting performance measurements over the wireless network link
(e.g. between your laptop and another machine over wireless connection).
You should measure both latency and bandwidth performance. Your solution
should tolerate the unstable nature of wireless networks. In other words,
although the network itself is not stable (with packets loss and cross
traffic that affects your measurements), the measured latency and bandwidth
between two nodes should NOT diverge too much during different runs of your
Accurate bandwidth measurement can be particularly challenging in unstable
networks. While a naive approach is to transfer a large amount of data
in measurement, a good performance measurement approach should not place
too much load on the network. Below are some examples of efficient network
bandwidth measurement. While these techniques are designed for wide-are
Internet, they might be suitable to be used in wireless networks.
- 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.
- V. Paxson. End-to-End Internet Packet Dynamics. In Proc. of the ACM SIGCOMM,
pages 139-152, Cannes, France, September 1997.
- 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 4: Query sniffing and analysis in peer-to-peer networks
It is possible to connect to some production peer-to-peer networks and
collect/analyze data exchanged in such a network. For instance, you
may try to get a Gnutella client connected to the
global Gnutella Network. Then you should monitor all the queries
forwarded to your Gnutella client. 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?
Half of your grade will be based on the results/findings of your analysis.
Warning: this assignment may be more
challenging than what it seems. In particular, it can be quite difficult
to connect a Gnutella client under your control (so you can log queries etc.)
to the global Gnutella Network.
By November 25 (Tuesday), you need to submit (using the electronic turn-in)
a preliminary report. We will not grade the preliminary report but we need to
see evidence that you have made good progress by that time. In the preliminary report, you should
indicate your assignment topic. Since we've only provided rough descriptions
for these topics above, we would also like to see specific design and work
scope you've developed
(e.g., the prioritization strategy in your focused-topic Web crawler,
the fault tolerance design of your multicast system,
your bandwidth measurement algorithm for unstable wireless networks,
and how you plan to connect your Gnutella client to the global Gnutella
The preliminary report should be in the PDF format.
Please indicate your name and email address in the report.
And note that all turn-ins are done through the electronic turn-in facility.
Do NOT send us email attachments.
You need to set up a 30-minute demo with the TA on December 9 (Tuesday).
We will open up the demo signup process shortly after we see your preliminary project reports.
In the demo you need to show us
how your solution 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.
By the time of your demo, you should turn in your source files, a makefile if needed,
and a final report. The final report should be expanded from your preliminary
report. It should clearly describe your overall design, any implementation detail
that you deem interesting, as well as how your programs should be compiled and run.
appropriate (for some assignments), your report should also describe the analysis
result for the assignment. In addition to electronically turning in the final
report, please also prepare a printed copy ready at the beginning of your demo.
There may be an opportunity to present the results of your project at the class
on December 10 (Wednesday). The class time is limited so we will only be able to
accommodate a few presentations. Please let the instructor know your interests in
making a project presentation. Presentation slots will be given out on a first-come-first-serve
basis. A successful presentation will earn you up to
10% extra credit on the assignment grade.
Late turn-in policy:
At the absence of any emergency, you must make your arranged demo time. Otherwise
you will get no points for this assignment.