DIMACS Workshop on Competitive Algorithms for Packet Scheduling,
Buffering and Routing in the Internet
July 6 - 8, 2011
DIMACS Center, CoRE Building, Rutgers University
Organizers:
Alex Kesselman, Google
Alex Lopez-Ortiz, University of Waterloo, alopez-ou at waterloo.ca
Yishay Mansour, Tel Aviv University
Adi Rosen, CNRS, Paris
Presented under the auspices of the DIMACS Special Focus on
Algorithmic Foundations of the Internet.
************************************************
The Internet employs the store-and-forward packet switching paradigm,
where packets are forwarded in a hop-by-hop manner toward their
destinations, and are stored at each intermediate router until they
can be sent to the next intermediate router, chosen according to the
routing policy. The main advantage of the packet switching paradigm is
the ability to share a common infrastructure for multiple connections
using statistical multiplexing, which allows one to create networks at
much lower cost with greater throughput, flexibility, and robustness.
From the early days of networking there has been great interest in the
study of algorithmic questions such as buffer management, scheduling
and routing, all arising in packet networks such as the
Internet. These problems have, originally, been extensively studied
under average case, distributional settings. Over the past decade,
however, there has been substantial work aiming at understanding these
problems under the worst case assumptions of competitive
analysis. This is motivated by both theoretical interest (what can be
achieved without information on the traffic) and practical
considerations (increasing difficulty to obtain accurate mathematical
(probabilistic) models for network traffic.)
The problems studied in this framework include, for instance,
maximizing the number of packets transmitted by a switch with bounded
buffers without knowing future packet arrivals, or dynamically
maintaining a set of open connections between network nodes without
knowing which connections are needed in the future. Such problems have
input that is gradually disclosed over time, and they thus naturally
fall into the framework of competitive analysis, in which the online
algorithm is compared to an optimal offline algorithm, thus providing
a worst-case performance guarantee (competitive ratio) for all traffic
patterns.
In this workshop we will consider optimization problems under various
parameters that arise in the design and management of packet networks,
and the algorithms to solve them together with their competitive
analysis. We are interested in algorithms that perform the various
tasks needed in a packet network, such as routing, buffering or
scheduling. We are interested both in work that focuses on a single
component of the network, such as a single buffer or a single switch
(router), and in work that considers the network as a whole, such as
work on routing or the interaction of the routing and scheduling
decisions. Finally, we are interested both in work that uses
"classical" competitive analysis, and in work that suggests methods to
render the worst case approach of competitive analysis less worst-case
oriented.
********************************************************************
Call for Participation:
Those wishing to give a contributed talk must submit a one-page
description of their work, with additional material (such as a paper)
optional, to alopez-o@uwaterloo.ca by May 23, 2011. Should there be an
excess of submissions, the organizers will select the contributed
talks according to the summaries submitted.
********************************************************************
Registration:
(Pre-registration deadline: June 29, 2011)
Please see website for complete registration details.
*********************************************************************
Information on participation, registration, accomodations, and travel can be found at:
http://dimacs.rutgers.edu/Workshops/Packet/
**PLEASE BE SURE TO PRE-REGISTER EARLY**
********************************************************************
Posts
