A Calculus for Network Delay and a Note on Topologies of Interconnection Networks
Cruz, Rene Leonardo
This item is only available for download by members of the University of Illinois community. Students, faculty, and staff at the U of I may log in with your NetID and password to view the item. If you are trying to access an Illinois-restricted dissertation or thesis, you can request a copy through your library's Inter-Library Loan office or purchase a copy directly from ProQuest.
Permalink
https://hdl.handle.net/2142/69370
Description
Title
A Calculus for Network Delay and a Note on Topologies of Interconnection Networks
Author(s)
Cruz, Rene Leonardo
Issue Date
1987
Doctoral Committee Chair(s)
Hajek, Bruce
Department of Study
Electrical Engineering
Discipline
Electrical Engineering
Degree Granting Institution
University of Illinois at Urbana-Champaign
Degree Name
Ph.D.
Degree Level
Dissertation
Keyword(s)
Engineering, Electronics and Electrical
Abstract
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.
Use this login method if you
don't
have an
@illinois.edu
email address.
(Oops, I do have one)
IDEALS migrated to a new platform on June 23, 2022. If you created
your account prior to this date, you will have to reset your password
using the forgot-password link below.
