Events for January 17, 2008
-
CS Colloquia: Bertrand Competition in Networks
Thu, Jan 17, 2008 @ 11:00 AM - 12:30 PM
Thomas Lord Department of Computer Science
Conferences, Lectures, & Seminars
Title: Bertrand Competition in NetworksSpeaker: Prof. Shuchi Chawla (Wisconsin)ABSTRACT:
The Internet is a unique modern artifact given its sheer size and the
number of its users. Given its continuing distributed and ad-hoc
evolution, there have been growing concerns about the effectiveness of
its current routing protocols in finding good routes and ensuring
quality of service. Imposing congestion-based and QoS-based prices on
traffic has been suggested as a way of combating the ills of this
distributed growth and selfish use of resources. Unfortunately, the
effectiveness of such approaches relies on the cooperation of the
multiple entities implementing them, namely the ISPs or Internet
service providers. The goals of the ISPs do not necessarily align with
the social objectives of efficiency and quality of service; their
primary objective is to maximize their own profit. It is therefore
imperative to study the following question: given a large
combinatorial market such as the Internet, suppose that the owners of
resources selfishly price their product to maximize their own profit,
and consumers selfishly purchase resources to maximize their own
utility, how does this effect the functioning of the market as a
whole?We study this problem in the context of a simple network pricing game,
and analyze the performance of equilibria arising in this game as a
function of the degree of competition in the game, the network
topology, and the demand structure. Economists have traditionally
studied such questions in single-item markets. It is well known, for
example, that monopolies cause inefficiency in a market by charging
high prices, whereas competition has the effect of driving prices down
and operating efficiently. Our work extends the classical Bertrand
model of competition from economics to the network setting. For
example, we ask: is competition in a network enough to ensure
efficient operation? does performance worsen as the number of
monopolies grows? does the answer depend in an interesting way on the
network topology and/or demand distribution? We provide tight bounds
on the performance (efficiency) of the network.This is joint work with Tim Roughgarden.BIO:
Shuchi Chawla is an assistant professor of Computer Science at
University of Wisconsin - Madison. She received her PhD in 2005 from
Carnegie Mellon University and her Bachelor of Technology degree from
the Indian Institute of Technology, Delhi, India in 2000. Her research
interests lie in theoretical computer science, with emphasis towards
approximation algorithms, combinatorial optimization, and game theory.
Shuchi is the recepient of an NSF CAREER award and an IBM Ph.D.
fellowship.Location: Hughes Aircraft Electrical Engineering Center (EEB) - 248
Audiences: Everyone Is Invited
Contact: CS Colloquia
-
CS Colloquia: Network Resilience to Attack and Disaster
Thu, Jan 17, 2008 @ 03:30 PM - 05:00 PM
Thomas Lord Department of Computer Science
Conferences, Lectures, & Seminars
Title: Network Resilience to Attack and DisasterSpeaker: Prof. Dan Rubenstein (Columbia)ABSTRACT:
Traditional network design can compensate for a small number of node
and link failures, but cannot handle attacks or failures on a massive
scale. These massive-scale phenomena may be due to malicious behavior
in the network, such as a denial of service attack, or due to
disaster, such as an emergency sensor network deployed in a
catastrophic location such as a fire or flood. A primary focus of our
research has been to design or enhance routing protocols so that they
are more resilient to these massive-scale challenges. The talk will
first cover the Secure Overlay Services (SOS) architecture we proposed
that utilizes network overlays to proactively protect targeted
Internet sites from distributed denial of service (DDoS) attacks.
Next, we will explore the problem of maximizing the amount of data
that can be extracted to a base-station from a sensor network whose
nodes are undergoing rapid failures. We develop a novel distributed
network coding technique and demonstrate how, in a massive failure
setting, our coding/routing technique outperforms prior state-of-the-art. I
will finish the talk with a brief run-through of other projects that
our lab has focused on.BIO:
Dan Rubenstein is an Associate Professor of Electrical Engineering and
Computer Science at Columbia University. He received a B.S. degree in
mathematics from M.I.T., an M.A. in math from UCLA, and a PhD in computer
science from University of Massachusetts, Amherst. His research interests are
in network technologies, applications, and performance analysis, with a
substantial emphasis on resilient and secure networking, distributed
communication algorithms, and overlay technologies. He has received an NSF
CAREER Award, an IBM Faculty Award, the Best Student Paper award from the ACM
SIGMETRICS 2000 conference, and a Best Paper award from the IEEE ICNP 2003
Conference.Location: Seaver Science Library (SSL) - 150
Audiences: Everyone Is Invited
Contact: CS Colloquia
