Stability of multiple access network control schemes with carrier sensing and exponential backoff

摘要

A new approach to determine the stability of multiple access network control schemes is presented. A "busy" network (the precise meaning of the term "busy" will be presented in the text) is modelled as a switched single-server hybrid dynamical system whose switching laws are stochastic and are based on typical multiple access network control protocols such as ALOHA and ethernet. The techniques are used to compute the critical ratio of traffic production per network node to total available bandwidth that ensures that data packets will not accumulate Unboundedly in waiting queues at each node. This is a measure of stability of the network and is an emergent, global, property determined by decentralized, autonomous behavior of each node. The behavior of each individual node is regarded as "microscopic" and the collective behavior of the network as a whole are emergent consequences of such microscopic laws. The results follow from the stationary distribution property of ergodic Markov chains. (c) 2005 Elsevier B.V. All rights reserved.