Main navigation | Main content
HOME » PROGRAMS/ACTIVITIES » Annual Thematic Program
IMA Tutorial
Network Management and Design
Speakers:
Timothy G. Griffin, Martin Grötschel, and Jennifer Rexford
This tutorial serves as an introduction to the IMA workshop on Network Management and Design.
What are the Semantics of Interdomain Routing? Slides: html pdf ppt
Timothy G. Griffin (AT&T Research) griffin@research.att.com
Inter-domain routing in the Internet is currently implemented with the Border Gateway Protocol (BGP). This protocol allows every autonomous administrative domain to define local routing policies that are consistent with its own interests. The first part of this tutorial is a basic introduction to interdomain routing issues, and how BGP is used to implement typical routing policies in the Internet. No previous knowledge of BGP will be assumed. Locally defined routing policies can interact in ways that cause various kinds of global routing anomalies --- nondeterministic routing and protocol divergence. These anomalies can span multiple autonomous domains, making them very difficult to debug and correct. Analysis of BGP is complicated by the fact that routing messages carry a number of semantically rich attributes that play a role in the rather complex BGP route selection algorithm and in the implementation of local routing policies.
The second part of this tutorial presents a simple formal model of BGP routing policies called the Stable Paths Problem (SPP). This formalism can be viewed as a simple kind of game or as a generalization of the stable matching problem. I'll argue that the BGP protocol can be modeled as a distributed algorithm that attempts to solve instances of the Stable Paths Problem. If the Stable Paths Problem has no solution, the protocol will not converge. The protocol can also diverge when there is a solution but it gets "trapped" down a blind alley. Nondeterministic routing is associated with Stable Path Problems that have multiple solutions. I'll also show that several interesting questions related to SPP (and BGP) solvability are NP-complete.
Bio: Tim Griffin received a B.S. in Mathematics from the University of Wisconsin, Madison. He went on to earn a Ph.D. in Computer Science from Cornell. He has done research in the areas of programming languages, database theory, and internet routing.
Mathematical Challenges in Telecommunication Slides: html pdf ps ppt
Martin Grötschel (Konrad-Zuse-Zentrum für Informationstechnik and Technische Universität Berlin, Germany) groetschel@zib.de http://www.zib.de/groetschel/
This talk will begin with a survey of mathematical challenges that arise in telecommunication. Mathematics is involved, e. g., in the design and manufacturing of chips, devices and network components, the choice of locations, the planning of the network topology, and the dimensioning of the equipment involved. Adequate cryptography, the need of fast data processing, demand routing and failure handling require efficient and reliable mathematical algorithms on the operational side.
The presentation will focus on the problem of designing low-cost telecommunication networks that provide sufficient capacity to serve a given demand, are based on a chosen technology mix, satisfy various technical side constraints, and survive certain failure situations. This problem is difficult in theory and practice. It will be indicated how algorithms integrating polyhedral combinatorics, linear and integer programming, and various heuristic ideas can help solve real-world instances within reasonable quality guarantees in acceptable running times.
The lecture will also address issues such as: balancing the load of signaling transfer points, issues arising in packet switching, modeling optical switches and all optical networks.networks
This talk is based on work of the telecommunications research group at ZIB, the examples discussed and the computational results reported are from joint projects with several telecommunication companies.
Traffic Measurement for IP Operations Slides: html pdf ppt
Jennifer Rexford (AT&T Labs - Research) jrex@research.att.com http://www.research.att.com/~jrex/Traffic measurement is an essential tool to guide the operators of large IP networks in detecting and diagnosing performance problems, and evaluating potential control actions. Measurements help operators identify under provisioned links, denial-of-service attacks, flash crowds, and shifts in user demands. This tutorial focuses on measurement techniques and traffic models that provide a comprehensive view of large IP networks where the operator has full administrative control. The tutorial starts with a brief overview of the basic tasks involved in operating a large IP network and derives requirements for network measurement. We argue that the very properties responsible for the Internet's success also make it difficult to control and manage.
LIST OF CONFIRMED PARTICIPANTS
| Name | Department | Affiliation |
|---|---|---|
| Montaz Ali | Computational And Applied Mathematics | Witwatersrand University |
| Beth E. Allen | Economics | University of Minnesota |
| Pietro Belotti | Electronics and Information | Polytecnic of Milan |
| Andreas Bley | Optimization | Konrad-Zuse-Zentrum, Takustr. 7, Berlin, Germany |
| Olga Brezhneva | Institute for Mathematics and its Applications | University of Minnesota |
| Tami Carpenter | Research | Telcordia Technologies |
| Christine Cheng | Computer Science | University of Wisconsin at Milwaukee |
| Collette Coullard | Industrial Eng. & Mgmt. Sciences | Northwestern University |
| Yingfei Dong | Computer Science | University of Minnesota |
| Andreas Eisenblaetter | Optimization | Konrad-Zuse-Zentrum, Takustr. 7, Berlin, Germany |
| Lisa Evans | Institute for Mathematics and its Applications | University of Minnesota |
| Luis A. Goddyn | Mathematics | Simon Fraser University |
| Olivier Goldschmidt | Opnet Technologies, Inc. | |
| Balaji Gopaladrishnan | Institute for Mathematics and its Applications | University of Minnesota |
| Tim Griffin | Network Management & Performance | AT&T Labs-Research |
| Joan Hutchinson | Mathematics & Computer Science | Macalester College |
| Martin Groetschel | Bereich Scientific Computing | Konrad-Zuse-Zentrum fur Informationstech, Berlin |
| George Karakostas | Computing & Software | University, Canada |
| Howard Karloff | AT&T Labs-Research | |
| Herve Kerivin | Institute for Mathematics and its Applications | University of Minnesota |
| Tong Li | Mathematics | University of Iowa |
| Adam Meyerson | Carnegie-Mellon University | |
| Peh Ng | Mathematics | University of Minnesota - Morris |
| Jennifer Rexford | AT&T Labs-Research | |
| M. Nuri Sendil | Industrial Eng. & Mgmt. Sciences | Northwestern University |
| David Shallcross | Telecordia Technologies | |
| Esam Sharafuddin | Computer Science | University of Minnesota |
| Bruce Shepherd | Bell Laboratories | Lucent Technologies |
| Tamon Stephen | Institute for Mathematics and its Applications | University of Minnesota |
| Rongqing Tu | Computer Science | University of Wisconsin, Milwaukee |
| Adrian Vetta | Computer Science | McGill University-Canada |
| Jens Vygen | Forschungsinstitut fur Diskrete Mathematik | University of Bonn |
| Jing Wang | Institute for Mathematics and its Applications | University of Minnesota |
| Bill Yurcuk | National Center for Supercomputing Applic. (NCSA) | University of Illinois at Urbana-Champaign |
|
|
|
|
|