CS204 Fall 2004

Group Project

Due: 11:59pm Friday December 10, 2004

I. Summary

The project will be a non-trivial original piece of work, which is produced by a group of 2 or 3 students working as a team. The project could be structured in any of the following ways: 

• a proposal for modifying some existing network algorithm (for routing, flow control, etc), or a comparison of several related algorithms for solving the same problem, which is supported by a quantitative study of (relative) performance using analytical methods or simulation
• a prototype implementation to demonstrate the feasibility of some proposed network algorithm(s) that you either found in the literature, or came up with yourself.
• a measurement study, or the application of published measurements to study the properties of some existing network component (e.g., queue sizes in a router)
• a critical survey of some network-related topic. (However, they have to be thorough, synthesize the read material, and offer an interesting perspective on the state of the art.)

The end result should be at the level of a decent workshop paper. I will offer several ideas for projects but you are encouraged to find your own topic. Please let me know ASAP when you have chosen a topic so I can offer suggestions on how to proceed before you (attempt to) do all the work.

II. Some Sample Topics

1. Stream Control Transmission Protocol (SCTP). What is it? Who supports it and why? Compare and contrast its features with existing protocols, including TCP and HTTP, for supporting multimedia, mobility, and security. What layer(s) in the OSI reference model does it occupy? What special handing (if any) is needed at the IP routers along the path(s), or at the end nodes? Explain why you think it will or will not become an important protocol in the future.
   
2. Eliminating the IP layer in a LAN cluster. The IP layer serves no useful purpose if both the sender and receiver are on the same IP subnet. In this case, the Ethernet MAC address is the only one that is used to carry the packet between source and destination, and the only value of including the IP header is to allow the hosts to specify which higher-layer protocol they wish to use (e.g., TCP, UDP, etc). What would it take to "skip" the IP header for local traffic? Can you implement it?
3. Use network traces to study the characteristics of Internet traffic. The WIDE project (which monitors Internet traffic between the USA and Japan) has several years of high-quality data available here. You can also find a lot of data from the Abilene network here. These data archives can be used to test how real Internet traffic compares with the various theoretical models we studied in lecture. In particular, you can do either one of the following tasks:
   
1. With respect to network calculus, find the minimal arrival curves for various daily trace files from the WIDE data archive. Are they well-behaved (i.e., smooth, mean-plus-offset shape)? Do the curves generated from traces collected on different days show a consistent structure or does it change significantly (and are the changes unpredictable, or correleated to the days of the week, or other factors)?
2. With respect to long-range dependence, you can use the WIDE archive to find how the autocorrelation function decays over extremely long time separations (i.e., days, weeks, months). Do your results support or contradict the notion that the traffic generation process still has some memory across these long time intervals?
   
4. Design and implement an efficient online algorithm for generating  minimum arrival curves. Imagine that your job is to build a tool for network administrators that will allow them to see how the shape of the arrival curve on some critical link changes over time. Note that they would want to see data that is some sort of "continuously moving average" of the traffic over the most-recent 15 minute period, or perhaps a combination of the results obtained from the last 2 or 3 fixed 15-minute blocks of time.
   
5. Compare UCP versus TCP performance in congested routers. We say that TCP is responsive to network congestion because a TCP sender will reduce its transmission rate if it thinks there is a congested router along the path to its destination, based on packet losses or other forms of congestion notification by the queue management algorithms. (See topic #5.) Conversely, we say that UDP is unresponsive to congestion because it has no built-in mechanism to detect packet loss and/or react by slowing down. (UDP provides a simple, unreliable datagram service, under the assumption that the application either does not care if some data is lost in transit, or it is smart enough to handle reliability issues by itself.) Thus, since routers cannot trust UDP flows to slow down when asked, they often treat UDP traffic as deserving of lower-quality service (i.e., greater chances of being dropped, and subject to higher delay). Generate some controlled tests in which you send a mixture of TCP and UDP traffic through a congested path, and see if you can measure the difference in the quality of service received by these two types of traffic.
6. Memory is so cheap that we can afford to put enough RAM in all routers to hold a complete world-wide IP routing table. How would you use it? Estimate how much memory you would need to construct a complete world-wide Ipv4 routing table, which includes a separate entry for every legal 24-bit prefix (i.e., network number). How much would it cost to buy this much RAM, based on current high-end PC component costs? Describe the route lookup algorithm you would design to take full advantage of this global routing table. Most importantly, how can you keep it up-to-date? Find some information about high-end transaction processing systems, such as credit-card verifications systems, to see if routing updates could be handles from a small number of information repositories. Conversely, find some information about peer-to-peer overlay networks, like Napster, to see whether a hierarchical distributed update scheme would be better able to scale to very large networks.
7. Find the "missing" network layer. Historically, there used to be network-level functions to find a path across a multihop wired network, or to recover from errors and/or prevent congestion within that network. Today, the network layer has essentially disappeared and IP (which is actually an inter-networking layer) has taken over its position in the OSI reference model. However, these network-layer functions are still needed for certain applications, such as IP mobility, or Quality-of-Service improvements for wireless systems, and hence people have been trying to find ways to modify IP and/or TCP to incorporate these extra features. Look at the history of old network layer protocols from the 1970's and 1980's to see how we handled these problems before. Alternately, look at a modern application where there have been proposals to modify IP and/or TCP to add functionality, and see how this could be done by creating a network layer instead.