UC San Diego

First-In First-Out (FIFO) queues are widely used in packet switched communication networks and they have been studied extensively, from a probabilistic point of view, in the Queuing Theory field. The Network Calculus framework was proposed as an alternative to the probabilistic approach and provides deterministic bounds provided the inputs do satisfy deterministic constraints (envelopes). In the first part of this dissertation we use service curves to analyze FIFO queues with inputs constrained by sigma-rho envelopes. Using previously known results we show that for the case of a single FIFO queue it's possible to recover known and tight bounds for different Quality of Service (QoS) metrics. For the case of two FIFO queues in tandem we find the smallest possible end-to-end delay bound, with this approach, by choosing the appropriate service curve at each node but we found that, in general, this bound is still not achievable. In order to find a better bound, we define a general service abstraction, which is defined in terms of a ̀s̀ervice mapping," which is a monotone operator that maps an arrival process to a lower bound on the corresponding departure process. For a network element with a shift invariant service mapping, we obtain bounds on the maximum delay, maximum backlog, and a traffic envelope for the departure process, assuming that the arrival process to the network element conforms to a traffic envelope. Using the service mapping abstraction to analyze a network of two FIFO queus in tandem, whose arrival processes conform to traffic envelopes, we obtain achievable upper bounds on end-to-end delay which are smaller than those that can be obtained with previously proposed methods. In the second part we address the problem of worst case average delay for a single FIFO queue with constrained inputs, where the average is over time. We show that if a flow has a piecewise linear and concave envelope and shares a single FIFO queue with another flow that has a concave envelope it's possible to obtain a tight bound on the worst case average delay