HOME    »    PROGRAMS/ACTIVITIES    »    Annual Thematic Program
Spring 2003
IMA Tutorial
Network Management and Design
Sunday, April 6, 2003


Optimization, September 2002 - June 2003

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.

TUTORIAL SCHEDULE
SUNDAY, APRIL 6
All talks are in Lecture Hall EE/CS 3-180 unless otherwise noted.
10:00-10:30 am Coffee and Registration

Reception Room EE/CS 3-176

10:30 am-12:00 pm Martin Grötschel
Konrad-Zuse-Zentrum für Informationstechnik and Technische Universität Berlin, Germany

Mathematical Challenges in Telecommunication

Slides:   html    pdf    ps    ppt

1:30-3:00 pm Jennifer Rexford
AT&T Labs - Research

Traffic Measurement for IP Operations

Slides:   html    pdf    ppt

3:15-4:45 pm Timothy G. Griffin
AT&T Research

What are the Semantics of Interdomain Routing?

Slides:   html    pdf    ppt

Abstracts:

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

As of 4/9/2003
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

Connect With Us:
Go