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 highquality 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 worsecase input patterns, thus allowing a worsecase 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 siti paths. This is an NPcomplete 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 realtime 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 largescale, highspeed and optical networks. We propose a preliminary Ant Colony Optimization (ACO) approach to solve this problem.
Keywords
Packetswitched networks, Adversarial Queueing Model, Ant Colony Optimization, Disjoint paths
References

A.Borodin, J.Kleinberg, P.Raghavan, M.Sudan and D.Williamson.. (2001)
Adversarial queueing theory,
Journal of the ACM, 48(1):1338.

M.Andrews, B.Awerbuch, A.FernĂˇndez, J.Kleinberg, T.Leighton and Z.Liu. (2001)
Universal stability results for greedy contentionresolution protocols,
Journal of the ACM, 48(1):3969.

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. 183197.

C.Ă€lvarez, M.Blesa and M.Serna. (2003)
A characterization of universal stability in the adversarial queueing model. Manuscript in preparation.

C.Ă€lvarez, M.Blesa, J.Diaz, A.FernĂˇndez and M.Serna. (2003)
Adversarial models for prioritybasednetworks.
In
28th International Symposium on Mathematical Foundations ofComputer Science. Lecture Notes in Computer Science, SpringerVerlag. Accepted for publication.

J.Kleinberg. (1996)
Approximation algorithms for disjoint paths problems. Ph.D. Thesis. MIT, Cambridge.

M.Blesa and C.Blum. (2003)
Ant Colony Optimization for the maximum disjoint paths problem. Manuscript in preparation.

M.Dorigo, G.Di Caro and L.Gambardella. (1999)
Ant algorithms for discrete optimization,
Artificial Life, 5(2):137172.