Back to the program.
Decision and Optimization problems in networks: Stability and Disjoint Paths
Maria J. Blesa
Dept. Llenguatges i Sistemes Informàtics;; Universitat Politècnica de Catalunya;; Barcelona, Spain
On 2003-06-06 at 15:00:00 (Brussels Time)

Abstract

Problems in computer science can be classified into decision and optimization problems. The former refer to the checkability of a property and can have a positive or a negative answer. In the latter we have an objective goal to optimize and we are interested in obtaining high-quality solutions. Both types of problems are strongly related and, in network environments, they are often oriented to guarantee some Quality of Service (QoS) issue. In this talk, we deal with a decision and an optimization problem arising in network environments. On one side, we study the stability problem in the context of packet routing. Stability is the property of deciding whether at any time the maximum number of packets in a network system is bounded. The growing complexity of network traffic nowadays makes it increasingly unrealistic to model traffic as, say, a Poisson stream. We will adopt the Adversarial Queueing Model (AQT) to modelize the traffic in the network. This model replaces traditional stochastic arrival assumptions of the classical queueing theory by worse-case input patterns, thus allowing a worse-case analysis. We present some of our recent results on this area, including a characterization for static networks and new adversarial models for dynamic networks. Secondly, we study the maximum disjoint paths problem. Given a graph G and a collection T={(s1,t1)...(sk,tk)} of pairs of vertices in G, the disjoint paths problem consist of determining whether the pairs of vertices in T can be linked in G by disjoint si-ti paths. This is an NP-complete problem. Its optimization version consists of finding a maximum number of pairs in T that can be disjointedly connected in G. This problem has a multitude of applications in areas such as real-time communications, VLSI design, scheduling, bin packing, load balancing, and it has been brought into focus recently in papers discussing applications to routing and admission control in large-scale, high-speed and optical networks. We propose a preliminary Ant Colony Optimization (ACO) approach to solve this problem.

Keywords

Packet-switched networks, Adversarial Queueing Model, Ant Colony Optimization, Disjoint paths

References

  1. A.Borodin, J.Kleinberg, P.Raghavan, M.Sudan and D.Williamson.. (2001) Adversarial queueing theory, Journal of the ACM, 48(1):13-38.
  2. M.Andrews, B.Awerbuch, A.Fernández, J.Kleinberg, T.Leighton and Z.Liu. (2001) Universal stability results for greedy contention-resolution protocols, Journal of the ACM, 48(1):39-69.
  3. C.Àlvarez, M.Blesa and M.Serna. (2002) Universal stability of undirected graphs in the adversarial queueing model. In 14th ACM Symposium on Parallel Algorithms and Architectures. ACM Press New York, USA. pp. 183-197.
  4. C.Àlvarez, M.Blesa and M.Serna. (2003) A characterization of universal stability in the adversarial queueing model. Manuscript in preparation.
  5. C.Àlvarez, M.Blesa, J.Diaz, A.Fernández and M.Serna. (2003) Adversarial models for priority-basednetworks. In 28th International Symposium on Mathematical Foundations ofComputer Science. Lecture Notes in Computer Science, Springer-Verlag. Accepted for publication.
  6. J.Kleinberg. (1996) Approximation algorithms for disjoint paths problems. Ph.D. Thesis. MIT, Cambridge.
  7. M.Blesa and C.Blum. (2003) Ant Colony Optimization for the maximum disjoint paths problem. Manuscript in preparation.
  8. M.Dorigo, G.Di Caro and L.Gambardella. (1999) Ant algorithms for discrete optimization, Artificial Life, 5(2):137-172.