Distributed and On‐Line Routing on Tori

Distributed and On‐Line Routing on Tori

0.00 Avg rating0 Votes
Article ID: iaor20121103
Volume: 32
Issue: 4
Start Page Number: 562
End Page Number: 593
Publication Date: Apr 2002
Journal: Algorithmica
Authors: , , ,
Keywords: networks: scheduling, combinatorial optimization
Abstract:

In this paper we study the problem of assigning paths to packets on N imes N tori in an on‐line and distributed fashion. By on‐line we mean that the routing decisions must be made without any knowledge of future requests. Being distributed is an equally important feature of our design, for such algorithms need not know the global configuration of the network in the process of routing packets. We use the technique of competitive analysis to measure the performance of our design. In addition to showing an Ωlog N) lower bound on the competitive ratio, we present both deterministic and randomized algorithms which are O(log N) competitive with respect to the maximum load (i.e., congestion ) on communication links.

Reviews

Required fields are marked *. Your email address will not be published.