CS 791: Project Suggestions, Part One
September 19, 1999
Prof. John Byers
Overview
The projects listed below give an overview of some appropriate and hopefully
interesting projects for CS 791. All sketch a current research
avenue that is relevant to one or more of the Case Studies we are covering
in the class, and are cross-listed according to those topics. In
all cases, the description of the project is just a sketch -- in some cases,
I have thought in detail about the research problem stated, while in others,
I have given the problem only a small amount of thought. You
are by no means required to choose one of the projects listed here, but
your project should fit in clearly with the theme(s) of the course.
Project Organization
I prefer that students work individually on projects, but I will allow
students to work in groups of two, in which case I will expect the scope
of the project to be considerably larger, and the finished product to be
more polished than if you work alone. Please get started early on
your projects and come talk to me frequently to discuss what you are working
on. Teaching this course is one of my main responsibilities this
semester, so I have plenty of time to discuss your projects.
"Improved Skyscraper Broadcasting" (Real-Time / Multicast)
In the Hua and Sheu paper [HS 97], the authors present a new scheme
for transmitting video-on-demand in metropolitan-area networks. Their
technique judiciously uses "channels" to transmit portions of a popular
video, where each channel corresponds to a separate segment of the transmission.
Users maintain the invariant that they play out the contents of segment
i while subscribing to channel i + 1. The
novelty in their work lies in the choices of the segment sizes so as to
minimize the number of channels, while keeping both the latency perceived
by clients and client buffer sizes to a minimum. Using fast
forward error correcting techniques, the number of channels needed can
be compressed even further while simultaneously making the system more
resilient to packet loss without much additional overhead at the clients.
Various Projects on Multimedia Streams (Real-time / Future
Service Models / Multicast)
A multimedia session typically consists of a diverse ensemble of concurrent
streams (audio, video, file transfer, shared whiteboard)
which have distinct application-level requirements, i.e. audio is inelastic
to delay and jitter while the shared whiteboard may be able to tolerate
fluctuations of this kind. In order to enable the network to provide
reasonable service for such an application, the application must be able
to specify its requirements.
-
From a future service models perspective, open questions about multimedia
applications include how best to specify these application-level requirements,
and how the network should provision for concurrent connections with different
QoS requirements.
-
From a multicast perspective, a partial solution for transport of multimedia
streams is the use of multiple multicast groups. But understanding
how best to lay out the transmission over a small number of groups has
not been studied extensively.
-
Techniques (not widely known in the networking community) are known for
generating a priority encoding of a collection of data items. When
this encoding is transmitted over a lossy network, the items can always
be recovered in order of their priority, provided that a sufficiently
large fraction of the encoding has been received by the client. The
application of this idea to an ensemble of streams in a multimedia session
should be direct.
"Measurement Collection in the Internet" (Modeling)
At the BU/NSF IMIC workshop on 8/30, Sugih Jamin gave a talk
advocating placement of measurement collection nodes inside the Internet
to gather statistics about the usage of the Internet at large. His
group has so far been focusing on the theoretical and practical aspects
of the question of where to place these measurement nodes and how to gather
the measurements efficiently. Another interesting question is to
consider how effective a small number of measurement nodes can possibly
be? For instance, what fraction of the nodes and edges of a "representative
topology" (see pitfalls below) can be observed by running experiments from
a set of k measurement boxes. What value of k is at
the "knee of the curve" with respect to capturing a representative slice
of the entire topology.
"Exploring Internet Power Laws" (Modeling)
A paper at this year's SIGCOMM [FFF99] observes that recent maps of
the Internet topology exhibit power laws, including the observation that
the distribution of nodes with a given outdegree follows a power law, i.e.
the degrees follow a heavy-tailed distribution. In contrast, existing
tools to construct "Internet-like topologies" all use much more regular
distributions, thus it can be argued that the graphs they generate are
not representative. Two challenges are to work on graph generation
tools which actually exhibit the properties observed by [FFF99] and (perhaps
more importantly) to provide explanations for why they arise.
"Maximizing Utility of Transport on Sensor Networks" (Wireless)
In future wireless sensor networks, nodes will be expected to self-organize
into an ad hoc network, gather information about their surroundings and
relay that information back to a destination in an adjoining wired network.
Reliable delivery of this data is made difficult by virtue of the fact
that some nodes may be faulty, and all are operating under (very) limited
power constraints, which may cause nodes to become incapacitated.
An interesting challenge is to develop distributed transport algorithms
which maximize the expected amount of valuable information safely transmitted
onto the wired network before the sensor network fails. (Sensor
networks are a particularly rich source of interesting problems that can
be explored in simulation).