Some of the applications in modern data networks are delay sensitive (e.g., video and voice).
An end-to-end delay analysis is needed to estimate the required network resources of delay
sensitive applications. The schedulers used in the network can impact the resulting delays to
the applications. When multiple applications are multiplexed in a switch, a scheduler is used
to determine the precedence of the arrivals from different applications.
Computing the end-to-end delay and queue sizes in a network of schedulers is difficult and
the existing solutions are limited to some special cases (e.g., specific type of traffic). The theory
of Network Calculus employs the min-plus algebra to obtain performance bounds. Given an
upper bound on the traffic arrival in any time interval and a lower bound on the available service
(called the service curve) at a network element, upper bounds on the delay and queue size of
the traffic in that network element can be obtained. An equivalent end-to-end service curve of a
tandem of queues is the min-plus convolution of the service curves of all nodes along the path.
A probabilistic end-to-end delay bound using network service curve scales with O(H logH)
in the path length H. This improves the results of the conventional method of adding per-node
delay bounds scaling with O(H^3).
We have used and advanced Network Calculus for end-to-end delay analysis in a network of
schedulers. We formulate a service curve description for a large class of schedulers which we
call Delta-schedulers. We show that with this service curve, tight single node delay and backlog
bounds can be achieved. In an end-to-end scenario, we formulate a new convolution theoii
rem which considerably improves the end-to-end probabilistic delay bounds. We specify our
probabilistic end-to-end delay and backlog bounds for exponentially bounded burstniess (EBB)
traffic arrivals. We show that the end-to-end delay varies considerably by the type of schedulers
along the path. Using these bounds, we also show that a if the number of flows increases, the
queues inside a network can be analyzed in isolation and regardless of the network effect.
| Identifer | oai:union.ndltd.org:TORONTO/oai:tspace.library.utoronto.ca:1807/32719 |
| Date | 21 August 2012 |
| Creators | Ghiassi-Farrokhfal, Yashar |
| Contributors | Liebeherr, Jorg |
| Source Sets | University of Toronto |
| Language | en_ca |
| Detected Language | English |
| Type | Thesis |
Page generated in 0.0017 seconds