Copyright © [2003] by The Society for Industrial and Applied Mathematics. All rights reserved
We investigate stability ofpacket routing policies in adversarial queueing networks. We provide a simple classi cation of networks which are stable under any greedy scheduling policy - network is stable if and only if the underlying undirected connected graph contains at most two edges. We also propose a simple and distributed policy which is stable in an arbitrary adversarial queueing network even for the critical value of the arrival rate r = 1. Finally, a simple and checkable network ow type load condition is formulated for adaptive adversarial queueing networks and a policy is proposed which achieves stability under this new load condition. This load condition is a relaxation of the integral network ow type condition considered previously in the literature.
By: David P. Gamarnik
Published in: SIAM Journal on Computing, volume 32, (no 2), pages 371-85 in 2003
LIMITED DISTRIBUTION NOTICE:
This Research Report is available. This report has been submitted for publication outside of IBM and will probably be copyrighted if accepted for publication. It has been issued as a Research Report for early dissemination of its contents. In view of the transfer of copyright to the outside publisher, its distribution outside of IBM prior to publication should be limited to peer communications and specific requests. After outside publication, requests should be filled only by reprints or legally obtained copies of the article (e.g., payment of royalties). I have read and understand this notice and am a member of the scientific community outside or inside of IBM seeking a single copy only.
Questions about this service can be mailed to reports@us.ibm.com .