Electrical Engineering
      and Computer Sciences

Electrical Engineering and Computer Sciences

COLLEGE OF ENGINEERING

UC Berkeley

Service Disciplines for Packet-Switching Integrated-Services Networks

Hui Zhang

EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-94-788
December 1993

Integrated-services networks will provide the communication infrastructure in the future. Unlike traditional communication networks, which are designed to offer a single type of service, integrated-services networks will offer multiple services, including data, voice, video, and others. Supporting applications with diverse traffic characteristics and performance objectives requires the offered services to be both flexible and guaranteed. To be flexible, integrated-services networks will use packet-switching technology. To provide performance guarantees in terms of throughput, delay, delay jitter, and loss rate, a proactive network control approach is needed. One of the most important components in this architecture is the service discipline at the switching nodes.

We first present a taxonomy and framework for studying and comparing service disciplines in integrated-services networks. Given the framework, we show the limitations of several existing solutions, and propose a new class of service policies called rate-controlled service disciplines. This class of service disciplines may be non-work-conserving, i.e., a server may be idle even when there are packets to be transmitted. Although non-work-conserving disciplines were seldom studied in the past, our research shows that non-work-conserving rate-controlled service disciplines have several advantages that make them suitable for supporting guaranteed performance communication in a high speed networking environment. In particular, rate-controlled service disciplines can provide end-to-end per-connection deterministic and statistical performance guarantees in very general networking environments. Unlike existing solutions, which only apply to simple network environments, rate-controlled service disciplines also apply to internetworking environments. Moreover, unlike existing solutions, which only apply to feed-forward networks and a restricted class of feedback networks, rate-controlled service disciplines can provide guarantees in arbitrary feed-forward and feedback networks.

The key feature of a rate-controlled service discipline is the separation of the server into two components: a rate-controller and a scheduler. This separation has several distinct advantages: it decouples the allocation of bandwidths and delay bounds, uniformly distributed the allocation of buffer space inside the network to prevent packet loss, and allows arbitrary combinations of rate-control policies and packet scheduling policies. Rate-controlled service disciplines provide a general framework under which most of the existing non-work-conserving disciplines can be naturally expressed. One discipline in this class, called Rate-Controlled Static Priority (RCSP), is particularly suitable for providing performance guarantees in high speed networks. It achieves simplicity of implementation as well as flexibility in the allocation of bandwidths and delay bounds to different connections.

To increase the average ultilization of the network by real-time traffic, we present new admission control conditions for deterministic service, and new stochastic traffic models for statistical service. Compared to previous admission control algorithms for deterministic service, our solution ensures that deterministic services can be guaranteed even when the sum of the peak data rates of all connections exceeds the link speed. When the traffic is bursty, the new algorithm results in a multifold increase in the number of accepted connections. Further, to better characterize bursty traffic, we propose a traffic model that captures the interval-dependent behavior of traffic sources. With this traffic model and rate-controlled service disciplines, end-to-end per-connection statistical performance guarantees can be efficiently provided in a general networking environment.

Advisor: Domenico Ferrari


BibTeX citation:

@phdthesis{Zhang:CSD-94-788,
    Author = {Zhang, Hui},
    Title = {Service Disciplines for Packet-Switching Integrated-Services Networks},
    School = {EECS Department, University of California, Berkeley},
    Year = {1993},
    Month = {Dec},
    URL = {http://www.eecs.berkeley.edu/Pubs/TechRpts/1993/6319.html},
    Number = {UCB/CSD-94-788},
    Abstract = {Integrated-services networks will provide the communication infrastructure in the future. Unlike traditional communication networks, which are designed to offer a single type of service, integrated-services networks will offer multiple services, including data, voice, video, and others. Supporting applications with diverse traffic characteristics and performance objectives requires the offered services to be both flexible and guaranteed. To be flexible, integrated-services networks will use packet-switching technology. To provide performance guarantees in terms of throughput, delay, delay jitter, and loss rate, a proactive network control approach is needed. One of the most important components in this architecture is the service discipline at the switching nodes.  <p>We first present a taxonomy and framework for studying and comparing service disciplines in integrated-services networks. Given the framework, we show the limitations of several existing solutions, and propose a new class of service policies called rate-controlled service disciplines. This class of service disciplines may be non-work-conserving, i.e., a server may be idle even when there are packets to be transmitted. Although non-work-conserving disciplines were seldom studied in the past, our research shows that non-work-conserving rate-controlled service disciplines have several advantages that make them suitable for supporting guaranteed performance communication in a high speed networking environment. In particular, rate-controlled service disciplines can provide end-to-end per-connection deterministic and statistical performance guarantees in very general networking environments. Unlike existing solutions, which only apply to simple network environments, rate-controlled service disciplines also apply to internetworking environments. Moreover, unlike existing solutions, which only apply to feed-forward networks and a restricted class of feedback networks, rate-controlled service disciplines can provide guarantees in arbitrary feed-forward and feedback networks.  <p>  The key feature of a rate-controlled service discipline is the separation of the server into two components: a rate-controller and a scheduler. This separation has several distinct advantages: it decouples the allocation of bandwidths and delay bounds, uniformly distributed the allocation of buffer space inside the network to prevent packet loss, and allows arbitrary combinations of rate-control policies and packet scheduling policies. Rate-controlled service disciplines provide a general framework under which most of the existing non-work-conserving disciplines can be naturally expressed. One discipline in this class, called Rate-Controlled Static Priority (RCSP), is particularly suitable for providing performance guarantees in high speed networks. It achieves simplicity of implementation as well as flexibility in the allocation of bandwidths and delay bounds to different connections.  <p>  To increase the average ultilization of the network by real-time traffic, we present new admission control conditions for deterministic service, and new stochastic traffic models for statistical service. Compared to previous admission control algorithms for deterministic service, our solution ensures that deterministic services can be guaranteed even when the sum of the peak data rates of all connections exceeds the link speed. When the traffic is bursty, the new algorithm results in a multifold increase in the number of accepted connections. Further, to better characterize bursty traffic, we propose a traffic model that captures the interval-dependent behavior of traffic sources. With this traffic model and rate-controlled service disciplines, end-to-end per-connection statistical performance guarantees can be efficiently provided in a general networking environment.}
}

EndNote citation:

%0 Thesis
%A Zhang, Hui
%T Service Disciplines for Packet-Switching Integrated-Services Networks
%I EECS Department, University of California, Berkeley
%D 1993
%@ UCB/CSD-94-788
%U http://www.eecs.berkeley.edu/Pubs/TechRpts/1993/6319.html
%F Zhang:CSD-94-788