Calculus for Network Delays and a Note on Topologies of Interconnection Networks

摘要

A calculus is developed for obtaining bounds on delay in a buffered communication network which applies to a wide variety of models for network operation. The theory developed is different from traditional approaches to analyzing delay because the model used to describe the entry of data into the network is non-probabilistic. It is assumed that the data stream entered into the network by any given user satisfies 'burstiness constraints'--that is, the quantity of data from the stream contained in any interval of time is less than a value that depends on the length of the interval. Given this model, it is shown that data traffic streams on each internal link of the network satisfy burstiness constraints. This allows attainment of upper bounds on network delay and buffering requirements. A mechanism called regulation is studied for enforcing burstiness constraints on an arbitrary data stream. The effect of employing these regulation mechanisms inside the network is noted. Theoretical design issues for topologies of interconnection networks are examined.