Please use this identifier to cite or link to this item: https://doi.org/10.1007/s00453-005-1162-1
Title: Effective routing and scheduling in adversarial queueing networks
Authors: Sethuraman, J.
Teo, C.-P. 
Keywords: Adversarial networks
Congestion
Fluid model
Multicommodity flow
Scheduling
Issue Date: 2005
Source: Sethuraman, J., Teo, C.-P. (2005). Effective routing and scheduling in adversarial queueing networks. Algorithmica (New York) 43 (1-2) : 133-146. ScholarBank@NUS Repository. https://doi.org/10.1007/s00453-005-1162-1
Abstract: In an adversarial queueing network, the incoming traffic is decided by an adversary, who operates under a reasonable rate restriction. This model provides a valuable, complementary point of view to that of the traditional queueing network model in which arrivals are modeled by stochastic processes. As a result, the adversarial queueing network model has attracted much attention in recent years, especially as a way of modeling packet injections into a communication network. Our main result is a simple, effective packet routing and scheduling algorithm with a provably good performance. Specifically, our algorithm keeps the system stable (bounded number of packets in the system), with the bound on the number of packets in the system that is O((1 - r) -1), where r can be interpreted as the arrival rate of the packets into the communication network. This improves upon the work of Gamarnik, who designed an algorithm for which the number of packets in the system is O((1 - r) -2); moreover, our result matches the traditional queueing-theoretic number-in-system bound. © 2005 Springer Science+Business Media, Inc.
Source Title: Algorithmica (New York)
URI: http://scholarbank.nus.edu.sg/handle/10635/43955
ISSN: 01784617
DOI: 10.1007/s00453-005-1162-1
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

SCOPUSTM   
Citations

1
checked on Dec 6, 2017

WEB OF SCIENCETM
Citations

2
checked on Nov 19, 2017

Page view(s)

55
checked on Dec 10, 2017

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.