Balanced sequences and optimal routing
Authors:
Open Access
- 1 July 2000
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 47 (4) , 752-775
Abstract
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.Keywords
This publication has 23 references indexed in Scilit:
- Optimal Allocation Sequences of Two Processes Sharing a ResourceDiscrete Event Dynamic Systems, 1997
- Free-choice Petri nets-an algebraic approachIEEE Transactions on Automatic Control, 1996
- Complexity of trajectories in rectangular billiardsCommunications in Mathematical Physics, 1995
- Optimality of monotonic policies for two-action Markovian decision processes, with applications to control of queues with delayed informationQueueing Systems, 1995
- Optimization of static traffic allocation policiesTheoretical Computer Science, 1994
- Complexity of sequences defined by billiard in the cubeBulletin de la Société Mathématiques de France, 1994
- Morphismes de SturmBulletin of the Belgian Mathematical Society - Simon Stevin, 1994
- Distributed routing for load balancingProceedings of the IEEE, 1989
- Covering the positive integers by disjoint sets of the form {[nα + β]: n = 1, 2,…}Journal of Combinatorial Theory, Series A, 1973
- Complementing and exactly covering sequencesJournal of Combinatorial Theory, Series A, 1973