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.
Next: Call for Participation
Workshop Index
DIMACS Homepage