A Calculus for Network Delay and a Note on Topologies of Interconnection Networks

141 p.Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 1987.In this thesis we develop a calculus for obtaining bounds on delay in a buffered communication network that applies to a wide variety of models for network operation. The theory we develop is different from traditional approaches to analyzing delay because the model we use to describe the entry of data into the network is nonprobabilistic: we suppose that the data stream entered into the network by any given user satisfies "burstiness constraints." A data stream is said to satisfy a burstiness constraint if 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, we show that data traffic streams on each internal link of the network satisfy burstiness constraints. This allows us to obtain upper bounds on network delay and buffering requirements.We study a mechanism, called regulation, for enforcing burstiness constraints on an arbitrary data stream. The users of the network can therefore employ this mechanism to insure that the traffic that they enter to the network adheres to the model above. We also study the effect of employing these regulation mechanisms inside the network and find that we can derive smaller bounds on network delay than we can otherwise obtain; in some cases such internal regulation allows us to obtain a larger throughput region where we can find finite bounds for delay. We find that employing internal regulation mechanisms can in fact improve maximum delay.Another topic in this thesis is an examination of theoretical design issues for topologies of interconnection networks. Results in this area exist for circuit switching models. Using a packet switching model, we derive analogous results involving parameters that measure the performance and the cost of a topological design. Using convexity and simple information theoretic arguments, we obtain negative results and discuss nearly optimal positive results by means of examples.U of I OnlyRestricted to the U of I community idenfinitely during batch ingest of legacy ETD