Topics in computer communication and networks

Workshop theme

The Internet raises all sorts of completely new algorithmic questions, and it is these that form the focus for this workshop. An important aspect of communication on the Internet (and in other modern networks) is absence of centralised control: users communicate with each other by sending messages over the net, and use local protocols to control transmissions and to handle collisions.

One would like to study protocols, for example TCP/IP, with the aim of providing a rigorous analysis of the performance of the network. This study combines traditional probabilistic analysis (characterising the long-term behaviour of Markov chains and other stochastic processes, which are used to model protocols) with economic analysis (issues of fairness/utility) and with more traditional network algorithmics (routing methods).

Evaluating the quality of the long-term equilibrium is related to game-theory. One would like to know, for example, how close the Nash equilibrium (which arises from local control) is to the overall optimum. However, the new twist is that issues of computational tractability must be taken into account.

A further category of problems, more combinatorial in nature, arises in the modelling of the web graph and its evolution. For this purpose, standard random-graph models are unsuitable. New models are required which are consistent with empirical observations, for example that the degree-sequence of the web graph apparently obeys a power law.

The application is closed

Timetable

Monday 16th December 2002
08:30 to 10:00	Registration	No Room Required
10:00 to 11:00	Frank Kelly University of Cambridge Congestion pricing and capacity expansion games	Room 1
11:00 to 11:30	Coffee	No Room Required
11:30 to 12:30	Games and computation	Room 1
12:30 to 13:30	Lunch at Wolfson Court	No Room Required
14:00 to 15:00	Berthold Voecking Pricing equilibria for a congestion game with incomplete information	Room 1
15:00 to 15:30	Tea	No Room Required
15:30 to 16:00	Thomasz Luczak Adam Mickiewicz University On the power of two choices: balls and bins in continous time	Room 1
16:00 to 17:00	Jennifer Chayes Microsoft (UK) A model of directed scale-free graphs$^2$	Room 1
17:15 to 18:15	Wine \& Beer Reception	No Room Required
18:45 to 19:30	Dinner at Wolfson Court	No Room Required

Tuesday 17th December 2002
10:00 to 11:00	Christos Papadimitriou Understanding the internet graph	Room 1
11:00 to 11:30	Coffee	No Room Required
11:30 to 12:30	Elias Koutsoupias National and Capodistrian University of Athens Co-ordination mechanisms	Room 1
12:30 to 13:30	Lunch at Wolfson Court	No Room Required
14:00 to 15:00	Vijay Vazirani How intractable is the "invisible hand"	Room 1
15:00 to 15:30	Tea	No Room Required
15:30 to 16:00	Adrian Vetta McGill University On the quality of competitive equilibria in games with submodular social objective functions	Room 1
16:00 to 16:30	Jose Nino-Mora Admission control and routing to parallel queues via Whittle's restless bandit index policy	Room 1
16:30 to 17:00	Ramesh Johari Massachusetts Institute of Technology Internet resource allocation and a network congestion game	Room 1
18:45 to 19:30	Dinner at Wolfson Court	No Room Required

Wednesday 18th December 2002
10:00 to 11:00	Prabhakar Raghavan Measurements on the web graph	Room 1
11:00 to 11:30	Coffee	No Room Required
11:30 to 12:30	Web graphs: models and algorithms	Room 1
12:30 to 13:30	Lunch at Wolfson Court	No Room Required
14:00 to 15:00	Anna Karlin University of Washington Competitive worst-case analysis of truthful auctions: a survey	Room 1
15:00 to 15:30	Tea	No Room Required
15:30 to 16:00	Niclas Carlsson Åbo Akademi University Asymptotic properties of a simple TCP model	Room 1
16:00 to 16:30	Ingemar Kaj A limit process for long-range dependent arrival models under critical scaling	Room 1
19:15 to 18:00	Corpus Christi College - Dining Hall	No Room Required

Thursday 19th December 2002
10:00 to 11:00	Eva Tardos Cornell University Network design with selfish agents	Room 1
11:00 to 11:30	Coffee	No Room Required
11:30 to 12:30	Selfish routing and the price of anarchy	Room 1
12:30 to 13:30	Lunch at Wolfson Court	No Room Required
14:00 to 15:00	Eli Upfal Brown University Building low-diameter peer-to-peer networks	Room 1
15:00 to 15:30	Tea	No Room Required
15:30 to 16:00	Anthony Brooms Assessing routing behaviour into a shared resource: simulation vs. the Nash equilibrium	Room 1
16:00 to 17:00	Jin-Yi Cai University of Wisconsin-Madison On REM and SAM-estimation of congestion price using probabilistic packet marking	Room 1
18:00 to 18:30	Cambridge University Press Bookshop 1 Trinity Street, Cambridge - Wine \& snacks will be served	No Room Required

Friday 20th December 2002
10:00 to 11:00	Adi Rosen Aalborg Universitet Dynamic routing on networks with fixed-size buffers	Room 1
11:00 to 11:30	Coffee	No Room Required
11:30 to 12:30	Richard Gibbens University of Cambridge Fixed point models for performance engineering in enterprise IP networks	Room 1
12:30 to 13:30	Lunch at Wolfson Court	No Room Required
15:00 to 15:30	Tea	No Room Required
18:45 to 19:30	Dinner at Wolfson Court	No Room Required

Speakers

Anthony Brooms
Jin-Yi Cai University of Wisconsin-Madison
Niclas Carlsson Åbo Akademi University
Jennifer Chayes Microsoft (UK)
Richard Gibbens University of Cambridge
Ramesh Johari Massachusetts Institute of Technology
Ingemar Kaj
Anna Karlin University of Washington
Frank Kelly University of Cambridge
Elias Koutsoupias National and Capodistrian University of Athens
Thomasz Luczak Adam Mickiewicz University
Jose Nino-Mora
Christos Papadimitriou
Prabhakar Raghavan
Adi Rosen Aalborg Universitet
Eva Tardos Cornell University
Eli Upfal Brown University
Vijay Vazirani
Adrian Vetta McGill University
Berthold Voecking

Show All

Topics in computer communication and networks

Workshop theme

The application is closed

Timetable

Speakers

Supported By

Register for updates