Abstract
The Distributed Queue Dual Bus (DQDB) system consists of a linear arrangement of N nodes that communicate with each other using two contra-flowing buses. The nodes use an extremely simple protocol to send messages on these buses. This simple, but elegant, system has been found to be very challenging to analyze. We consider a simple and uniform abstraction of this model to highlight the fairness issues in terms of average waiting time. We introduce a new approximation method to analyze the performance of DQDB system in terms of the average waiting time of a node expressed as a function of its position. Our approach abstracts the intimate relationship between the load of the system and its fairness characteristics, and explains all basic behavior profiles of DQDB observed in previous simulation. For the uniform DQDB with equal distance between adjacent nodes, we show that the system operates under three basic behavior profiles and a finite number of their combinations that depend on the load of the network. Consequently, the system is not fair at any load in terms of the average waiting times. We also show that the main theme of the analysis carries over to the general (nonuniform) DQDB. By suitably choosing the inter-node distances, the DQDB can be made fair around some loads, but such system will become unfair as the load changes. In the vicinity of a critical load, the uniform network runs into a state of instability, where its behavior fluctuates from one extreme to the other with small load variations. Our analysis is supported by simulation results.
| Original language | English |
|---|---|
| Pages (from-to) | 1068-1084 |
| Number of pages | 17 |
| Journal | IEEE Transactions on Parallel and Distributed Systems |
| Volume | 6 |
| Issue number | 10 |
| DOIs | |
| State | Published - Oct 1995 |
Funding
The submitted manuscript has been authored by a contractor of the U.S. Government under contract No. DE-AC05-840R21400. Accordingly, the U.S. Government retains a nonexclusive, royalty-free license to publish or reproduce the published form of this contribution, or allow others to do so, for U.S. Government purposes. Stephan Olariu’s work is supported in part by the National Science Foundation under grant CCR-94071 80. This paper is based on “Average waiting time profiles of uniform DQDB model” by N.S.V. Rao, K. Maly, S. Olariu, S. Dharanikota, L. Zhang, and D. Game, which appeared in the Proceedings of IEEE INFOCOM’94: The Conference on Computer Communications, June 14-16, 1994, Toronto, Canada, pp. 1326-1333. A condensed version of parts of this work based on Section VI1 was presented at the 1991 International Conference on Parallel Processing, St. Charles, Illinois, August 1991, and was pubished in the proceedings; the present paper is published by the Permission of CRC Press, Boca Ra-ton, Florida. This project is partially funded by Sun Microsystems Inc. under the grant #596044, Taurus Technologies Inc. under the grant #596046, NASA under the grant #187263 and Virginia’s Center for Innovative Technology under the grant #596045. Dr. Rao’s research is sponsored by the Engineering Research Program of the Office of Basic Energy Sciences, of the U.S. Department of Energy, under Contract No. DE-ACO5-840R21400 with Martin Marietta Energy Systems, Inc.
Keywords
- DQDB
- Network protocols
- distributed queue
- performance analysis
- working window