Premium
Stability of networks and protocols in the adversarial queueing model for packet routing
Author(s) -
Goel Ashish
Publication year - 2001
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.1016
Subject(s) - computer science , fifo (computing and electronics) , queueing theory , computer network , network packet , routing (electronic design automation) , routing protocol , simple (philosophy) , protocol (science) , characterization (materials science) , packet forwarding , distributed computing , medicine , philosophy , materials science , alternative medicine , epistemology , pathology , computer hardware , nanotechnology
The adversarial queueing theory model for packet routing was suggested by Borodin et al. We give a complete and simple characterization of all networks that are universally stable in this model. We show that the same characterization also holds for networks which are stable given that the packet forwarding protocol is FIFO (First in First out). We also show that a specific greedy protocol, SIS (Shortest in System), is stable against 0/1 stochastic adversaries. © 2001 John Wiley & Sons, Inc.