Courses


Research


Publications


Home
Scalable Network Architectures for Providing Per-flow Service Guarantees

| Summary | Prototypes | Publications |


Research Summary:

The last decade in providing Internet service was all about building high-bandwidth networks. Two requirements, in contrast, drive the design of next-generation networks:

  1. The need for richer service semantics, which stems from the fact that the Internet has seen a rapid emergence of many applications with stringent timeliness constraints that can greatly benefit from end-to-end guarantees on delay, jitter, and throughput.
  2. The need to support large bandwidth networks, which stems from the projected manifold increase in link speeds.
Unfortunately, these two requirements are often conflicting. Proposals to provide per-flow service guarantees require the use of complex resource management mechanisms in routers; whereas increase in link speeds mandates the simplification of routers to enable them to operate at high link speeds. The goal of this dissertation is to design a network architecture that meets the above requirements of scalability and providing end-to-end per-flow service guarantees simultaneously.

Past efforts design network architectures that are either scalable or rich in their service offerings, but not both. Conventional network architectures use the First-in-First-Out (FIFO) link scheduler in routers which, although scalable, fails to provide per-flow service guarantees in the presence of bursty traffic. The Integrated Services (IntServ) network architecture, in contrast, enables a network to provide per-flow service guarantees by requiring all routers to employ sophisticated per-flow scheduling algorithms. These scheduling algorithms, however, require routers to perform per-packet flow classification and maintain per-flow scheduling state, which limits their scalability, especially in the core of networks that carry a large number of flows. In our research, we explore the following two design philosophies to achieve simultaneously our objectives of scalability and richness.

  • FIFO networks are scalable, but do not provide guarantees on end-to-end delay and throughput in the presence of bursty traffic. A natural approach, therefore, to providing richer services in scalable FIFO networks is to ask:
    Can traffic conditioning mechanisms that prevent bursty traffic from entering the network enable FIFO networks to provide per-flow service guarantees?
  • IntServ networks provide per-flow service guarantees, but impose per-flow computational overheads in routers. The natural question of interest is:
    Is it possible to eliminate complexity from IntServ mechanisms while retaining their strong service semantics?
In our research, we answer both of the questions raised above. First, we evaluate the efficacy in providing per-flow service guarantees of constant bit-rate (CBR) traffic conditioning used in conjunction with FIFO networks. We find that under asymptotic conditions of network utilization and path length, CBR flows may experience significantly high delays in FIFO networks. Our results indicate that CBR shaping is effective in providing performance guarantees to flows, only in environments where the amount of such premium traffic does not exceed a small percentage of the total link capacities. Second, we develop a network architecture that provides per-flow service guarantees similar to IntServ networks, but without requiring per-flow state or per-packet flow classification in the core routers of the network. We do this in two steps: (1) we understand what end-to-end guarantees are provided by core-stateful networks, and (2) we design core-stateless networks that provide similar guarantees. We instantiate our core-stateless architecture on a programmable network testbed and find that it can be implemented in routers with complexity similar to that of current FIFO networks. The key contributions of our research include:
  1. A comprehensive experimental analysis of the performance of CBR flows in FIFO networks.
  2. The first tight end-to-end fairness analysis of fair queuing networks.
  3. A methodology to transform algorithms from the Guaranteed Rate class of core-stateful algorithms to a core-stateless version that provides the same upper bounds on end-to-end delay.
  4. The first work-conserving core-stateless network that provides deterministic end-to-end throughput guarantees.
  5. The first work-conserving core-stateless network that provides deterministic end-to-end fairness guarantees.
  6. The first performance analysis of networks that provides per-flow service guarantees, on a programmable router platform.

Prototypes:



Relevant Publications:

  • J. Kaur and H. Vin, "Providing Deterministic End-to-end Fairness Guarantees in Core-stateless Networks", in Proceedings of the Eleventh International Workshop on Quality of Service (IWQoS'03), Monterey, CA, June 2003.

  • J. Kaur and H. Vin, "Core-stateless Guaranteed Throughput Networks", in Proceedings of IEEE INFOCOM, San Francisco, CA, April 2003.

  • J. Kaur and H. Vin, "End-to-end Fairness Analysis of Fair Queuing Networks", in the 23rd IEEE International Real-Time Systems Symposium (RTSS'02), Austin, TX, Dec 2002.

  • J. Kaur, "Scalable Network Architectures for Providing Per-flow Service Guarantees", Ph.D. Dissertation, Department of Computer Sciences, University of Texas at Austin, Aug 2002.

  • J. Kaur and H. Vin, "Core-Stateless Guaranteed Rate Scheduling Algorithms", in Proceedings of IEEE INFOCOM, Anchorage, AK, April 2001.

  • V. Sundaram, A. Chandra, P. Goyal, P. Shenoy, J. Sahni, and H. Vin, "Application Performance in the QLinux Multimedia Operating System", in Proceedings of the Eighth ACM Conference on Multimedia, Los Angeles, CA, November 2000.

  • J. Sahni, P. Goyal, and H. Vin, "Scheduling CBR Flows: FIFO or Per-Flow Queueing?", in Proceedings of the Ninth IEEE International Workshop on Network and Operating System Support for Digital Audio and Video (NOSSDAV'99), Basking Ridge, NJ, June 1999.