Paper Info
Title
Stability preserving transformations: packet routing networks with edge capacities and speeds
Abstract
In the context of an adversarial input model, we consider the effect on stability results when edges in packet routing networks can have capacities and speeds/slowdowns. In traditional packet routing networks, every edge is considered to have the same unit capacity and unit speed. We consider both static modifications (i.e. where the capacity or speed of an edge is fixed) and dynamic modifications where either the capacity or the speed of an edge can be dynamically changing over time. Amongst our results, we show that the universal stability of LIS is not preserved when either the capacity or the speed is changing dynamically whereas many other common scheduling protocols do maintain their universal stability. In terms of universal stability of networks, stability is preserved for dynamically changing capacities and speeds. The situation for static modifications, is not as clear but we are able to show that (in contrast to the dynamic case) that any “well defined” universally stable scheduling rule maintains its universality under static capacities, and common scheduling rules also maintain their universal stability under static speeds.
Year
DOI
Venue
2004
10.1145/365411.365546
Journal of Interconnection Networks
Keywords
Field
DocType
common scheduling rule,stable scheduling rule,unit capacity,edge capacity,common scheduling protocol,static speed,stability result,universal stability,static modification,unit speed,static capacity,edge coloring,dominating set,clique width
Edge coloring,Dominating set,Well-defined,Combinatorics,Static routing,Computer science,Scheduling (computing),Edge dominating set,Clique-width,Universality (philosophy)
Journal
Volume
Issue
ISBN
5
1
0-89871-490-7
Citations 
PageRank 
References 
20
0.89
11
Authors
3
Name
Order
Citations
PageRank
Allan Borodin12947658.84
Rafail Ostrovsky28743588.15
Yuval Rabani32265274.98