Service Disciplines For Packet-Switching Integrated-Services  Networks

                               Hui Zhang

	                   Ph.D Dissertation                           
                       Computer Science Division
       Department of Electrical Engineering and Computer Sciences
                        University of California

                   email: hzhang@tenet.Berkeley.EDU




           Integrated-services networks will provide the communication  infras-
      tructure  in the future. Unlike traditional communication networks, which
      are designed to offer a single type of service, integrated-services  net-
      works  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  {\m rate-controlled service discip-
      lines.}  This  class  of  service  disciplines  may  be   {\m   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 network-
      ing 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  dis-
      ciplines  also  apply  to  internetworking environments. Moreover, unlike
      existing solutions, which only apply to feed-forward networks and a  res-
      tricted  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  dis-
      tributes  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 pro-
      vide 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 utilization  of  the  network  by  real-time
      traffic,  we  present  new admission control conditions for deterministic
      service, and new stochastic traffic models for statistical service.  Com-
      pared 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  multi-
      fold  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  sta-
      tistical  performance guarantees can be efficiently provided in a general
      networking environment.


           To test our algorithms in real environments, we  have  designed  and
      implemented the Real-Time Internet Protocol, or RTIP. RTIP is the network
      layer data delivery protocol within the Tenet real-time  protocol  suite,
      and  is  the  first  protocol  of  its  kind   that provides host-to-host
      bounded-delay and bounded-delay-jitter  services  in  an  internetworking
      environment.  We  implemented RTIP  in Ultrix on DECstation 5000 worksta-
      tions, in HP/UX  on HP9000/7000 workstations, and in SunOS  on  SPARCsta-
      tions.   The  service  disciplines  used  in the implementation are rate-
      controlled service disciplines.  Results from a  measurement  study  show
      that  the protocol is effective in supporting guaranteed performance ser-
      vices in an internetworking environment.