Balanced sequences and optimal routing

The objective pursued in this paper is two-fold. The first part addresses the following combinatorial problem: is it possible to construct an infinite sequence over n letters where each letter is distributed as “evenly” as possible and appears with a given rate? The second objective of the paper is...

Full description

Saved in:
Bibliographic Details
Published in:Journal of the ACM 2000-07, Vol.47 (4), p.752-775
Main Authors: ALTMAN, EITAN, GAUJAL, BRUNO, HORDIJK, ARIE
Format: Article
Language:English
Subjects:
Computer programming
Computer Science
Numbers
Queuing
Routing
Series, Infinite
Stochastic models
Stochastic processes
Studies
Theory
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The objective pursued in this paper is two-fold. The first part addresses the following combinatorial problem: is it possible to construct an infinite sequence over n letters where each letter is distributed as “evenly” as possible and appears with a given rate? The second objective of the paper is to use this construction in the framework of optimal routing in queuing networks. We show under rather general assumptions that the optimal deterministic routing in stochastic event graphs is such a sequence.
ISSN:0004-5411
1557-735X
DOI:10.1145/347476.347482