[Search] [txt|pdf|bibtex] [Tracker] [Email] [Nits]

Versions: 00                                                            
Internet  Engineering Task  Force                     Flaminio Borgonovo
INTERNET-DRAFT                                            Antonio Capone
Expires: February 1999                                      Luigi Fratta
                                                          Mario Marchese
                                                         Chiara Petrioli
                                                  Politecnico  di Milano
                                                            29 July 1998



   End-to-end QoS provisioning mechanism for Differentiated Services
                   <draft-borgonovo-qos-ds-00.txt>


Status of this Memo

   This  document  is  an Internet-Draft.  Internet-Drafts  are  working
   documents  of the Internet Engineering Task Force (IETF), its  areas,
   and  its working groups. Note that other groups may  also  distribute
   working  documents  as  Internet-Drafts.  Internet-Drafts  are  draft
   documents  valid  for  a maximum of six months and  may  be  updated,
   replaced,  or  obsoleted  by  other documents  at  any  time.  It  is
   inappropriate to use Internet-Drafts as reference material or to cite
   them other than as ``work in progress.''

   To  view the entire list of current Internet-Draft, please check  the
   ``1id-abstracts.txt'' listing contained in the Internet-Drafts Shadow
   Directories   on  ftp.is.co.za  (Africa),   ftp.nordu.net   (Northern
   Europe),  ftp.nis.garr.it (Southern Europe),  munnari.oz.au  (Pacific
   Rim), ftp.ietf.org (US East Coast), or ftp.isi.edu (US West Coast).


Abstract

   This document presents an end-to-end mechanism to guarantee bandwidth
   and delay into the Differentiated Services mechanism to constant rate
   traffic  such  as  voice and video. The  mechanism  requires  network
   routers  to  be able to serve packets according to three  classes  of
   priority.  The needed call admission control is performed by an  end-
   to-end  signaling  procedure that implicitly looks for  the  required
   bandwidth and seizes it, if available. Short delays are guaranteed by
   the  regular  structure of constant rate traffic. No  entities  other
   than  source  and destination are involved  and  multicast  operation
   comes  at no further cost, which makes the mechanism  fully  scalable
   and integrable into the existing Internet.


1. Introduction

   The transport mechanism capable of guaranteeing demanding Quality  of
   Service  (QoS)  requirements  is under  discussion  in  the  INTERNET
   community.  The  Differentiated  Services  architecture  [1]  is  the
   approach  that has recently gained more credit. The goal is to  offer
   an  alternative to carry voice, video and multimedia with respect  to
   classic Telephone/ISDN and ATM networks. The basic problem is how  to
   guarantee  bandwidth,  delay and packet dropping  probability,  in  a

Borgonovo                       Expires:02/99                   [Page 1]


INTERNET-DRAFT       <draft_borgonovo_qos_ds_00.txt>        29 July 1998


   datagram  network  architecture where the only service  is  the  Best
   Effort packet transmission.

   In  this  contribution  we  consider  only  approaches  that  can  be
   completely  implemented at the IP level and do not assume  any  lower
   level QoS guarantee capability. In this context, an existing approach
   is represented by RSVP (Resource reSerVation Protocol) [2][3].

   RSVP  is a signaling mechanism among routers and hosts that  includes
   support to ``flows'' of packets with different QoS and the ability to
   dedicate end-to-end capacity to real-time traffic by means of hop-by-
   hop  resource  reservation  protocols.  In  practice,  this  solution
   changes  the  entire network architecture by relying on  the  virtual
   circuit  connection mechanism, the paradigm of the  telephony  world,
   today  extended  to the B-ISDN. During the set-up  phase,  needed  to
   install a virtual circuit, the network nodes cooperate, using complex
   protocols,  to  determine a path within the network  and  to  reserve
   network  resources such as bandwidth and buffers. The  implementation
   of  such  a  signaling  and its related  features  over  the  layered
   structure  of a pure datagram network will require large  investments
   because  of  the  heavy software and  hardware  modifications  to  be
   introduced in the already worldwide installed networks.

   A  much  simpler  alternative is represented  by  the  Differentiated
   Services approach. The basic idea is to use the IPv4  header TOS bits
   or  the  IPv6 Traffic Class  octet, the "DS  byte" to  designate  the
   "per-hop  behaviors"  that  packets are  to  receive.  By   carefully
   aggregating a multitude of QoS-enabled flows into a reasonable number
   of  differentiated  services offered by the network it is  no  longer
   necessary  to recognize and store information about  each  individual
   flow  in the core routers. Though some signaling mechanism is  needed
   to  manage  the service assignment to individual flows,  the  network
   mechanism  still  remains purely datagram and scales  well.  However,
   since the control on packets is performed hop-by-hop, it is not  easy
   to design a suitable call acceptance policy that is able to guarantee
   end-to-end QoS.

   As  the result of our research work in this field we have gained  the
   belief  that if one only wants to enforce QoS control over  constant-
   rate or almost-constant-rate streams, simple procedures based on non-
   preemptive  priority  mechanisms  and  simple  end-to-end   signaling
   procedures are effective. One such procedure has been investigated in
   the  framework of deflection networks, i.e., data networks with  very
   small or no queuing at nodes [4].

   The  Bandwidth Guaranteed Service (BGS) mechanism, presented in  this
   document,  guarantees  constant  rate  traffic  bandwidth  and  delay
   requirements in datagram networks such as the Internet. BGS is  based
   on three priority levels. It integrates and completes the DS approach
   and  allows  a  QoS  control as  in  RSVP,  without  adding  explicit
   signaling  protocols. No entities other than source  and  destination
   are involved and multicast operation is obtained at no further  cost,
Borgonovo                       Expires:02/99                   [Page 2]


INTERNET-DRAFT       <draft_borgonovo_qos_ds_00.txt>        29 July 1998


   which makes the mechanism fully scalable.

   The   document is organized as follows. In Section 2 we present  BGS,
   its  call  setup  and call acceptance  procedures,  while  Section  3
   illustrates  its  behavior  by  means  of  some  preliminary  results
   obtained by simulation.

2. The BGS mechanism

   In  the  following we assume connections with  constant  rate  packet
   traffic.  The jitter introduced by the network is eliminated  at  the
   destination user by storing the packets in a play-out buffer which is
   emptied at the constant nominal rate, starting with a delay D_b after
   the  reception  of  the first packet of  the  connection.  With  this
   technique the total delivery delay experienced by packets is constant
   and equal to

   W = D_b+d_1                                                       (1)

   where  d_1  is the network delay suffered by the first packet.  If  a
   packet  is  delayed  more  than W, it is  useless  and  is   dropped.
   Therefore the QoS guaranteed traffic requires, besides the  bandwidth
   B,  also  a  maximum packet delay W  and  a  maximum  packet-dropping
   percentage gamma.

   The BGS mechanism requires that each packet in the network belongs to
   one of the three following priority classes.

   Class  0:  (lowest  priority)  if the  packet  requests  best  effort
   service;

   Class  1:  (intermediate priority) if the packet is a  scout  packet,
   used in the set-up procedure as defined below;

   Class  2: (highest priority) if the packet belongs to a constant  ate
   flow that has been granted guaranteed service.

   The  priority information is carried in the TOS field and is used  by
   the routers to serve all packets according to a non-preemptive  head-
   of-the-line  priority  scheme. Class 1 and 2 packets  have  the  same
   constant length.

   The set-up procedure operates end-to-end and is activated when a  new
   connection, characterized by the bandwidth B and the maximum  allowed
   transfer delay W, is requested.

   Upon   reception  of a connection request C_j  addressed  to  NODE_B,
   NODE_A immediately starts transmitting scout packets at the rate  r_j
   corresponding to the requested bandwidth.

   The  scout  packets do not carry data traffic in the  payload,  since
   they are used to perform "bandwidth scouting and seizing" within  the
Borgonovo                       Expires:02/99                   [Page 3]


INTERNET-DRAFT       <draft_borgonovo_qos_ds_00.txt>        29 July 1998


   network.  To  this purpose they only include  set-up  information  to
   signal  to the receiving NODE_B the request for an incoming call  and
   the related service quality parameters.

   Upon  receiving  the  first scout packet,  NODE_B  starts  performing
   bandwidth  measures  and  delay evaluations  to  verify  whether  QoS
   requirements are met. If the outcome is positive NODE_B sends a  call
   acceptance  packet  to  NODE_A.  Otherwise,  either  it  rejects  the
   connection or starts a bandwidth negotiation procedure with NODE_A.

   As far as NODE_A is concerned, it keeps on transmitting scout packets
   until either a time-out occurs or a response from NODE_B is received.
   If  the  time  out expires or the response is negative  the  call  is
   aborted, meaning that the bandwidth has not been found. If a positive
   response  is  received, the connection set-up phase ends  and  NODE_A
   replaces   scout  packets  with  data  packets.  The   bandwidth   is
   automatically released when packets transmission ends.

   The  priority scheme adopted guarantees that new connections can  not
   steal  bandwidth  to  already  established ones.  In  fact,  if  some
   constant bandwidth connections have already been admitted, as soon as
   new connections attempt to steal bandwidth on a link, old connections
   are  delayed, a queue builds up and the priority mechanism  cuts  out
   the newly arrived scout packets.


2.1 Call acceptance procedure

   The   call  acceptance  procedure  is  directly  performed   by   the
   destination  node  and  is very simple:  a  new  guaranteed-bandwidth
   connection is accepted only if the connection parameters measured  on
   the N scout packets satisfy the QoS constraints.

   First, a test of significance on the Hypothesis H0 that the bandwidth
   requirement  is satisfied is performed on the sample X_1,  X_2,  ...,
   X_(N-1),  where X_i is the interarrival time between scout  packet  i
   and  i+1.  Under the hypothesis H0 we have E[X]=T,  being  $1/T$  the
   packet  constant rate of each flow. So, the test can be exploited  on
   the sample average

   M_X = (X_1+X_2+...+X_(N-1))/(N-1)                                 (2)

   which  is  assumed  to be normally distributed  with  average  T  and
   variance

   S2_x =[(X_1-T)*(X_1-T)+...+(X_(N-1)-T)*(X_(N-1)-T)]/(N-1)         (3)

   So,  for a given confidence level alpha, a threshold  T_alpha  exists
   such  that  if  M_X < T_alpha the hypothesis  H_0  is  accepted.  The
   threshold value can be obtained as

   T_alpha = T + xi_alpha * sqrt(S2_x/(N-1))                         (4)
Borgonovo                       Expires:02/99                   [Page 4]


INTERNET-DRAFT       <draft_borgonovo_qos_ds_00.txt>        29 July 1998


   where  xi_alpha is the standard normal deviate that is exceeded  with
   probability 1 - alpha. The difference

   Delta B = 1/T - 1/T_alfa                                          (5)

   represents the resolution power of the measure.

   The   precision  of  the  estimate  increases  with  the  number   of
   statistically independent samples. In a network that carries periodic
   packet streams, delay samples can be considered independent if  taken
   at  a  distance  larger than the transmission  period  T_max  of  the
   connection  with  the lowest admissible bandwidth. Thus,  the  set-up
   period  is determined in time rather than by the number of  signaling
   packets. By doing this we guarantee that the measure captures all the
   existing  traffics, including the slowest.

   For example, if we assume that the lowest bandwidth corresponds to 32
   Kb/s  with 640 bit packets, the packet transmission time is 20 ms  so
   that  a  measure  period  of  1-2 seconds  is  needed  to  collect  a
   reasonable number (50-100) of samples.

   The  measure indicated above may be critical since, due to the  error
   (5), the connection could be accepted even if the required  bandwidth
   slightly  exceeds the available one. In this case, more traffic  than
   the  capacity  is accepted and all connections would be  affected.  A
   simple  way  to avoid this unwanted phenomenon is to scout  for  more
   bandwidth  than  needed  in  the set-up phase, and  to  turn  to  the
   required bandwidth once the call is accepted. With this  modification
   links  can not be used up to their capacity, but the unused  fraction
   can be kept very small.

2.2 The delay issue

   Since  packets  are dropped when their delay  overcame  the  required
   threshold,  it is important, for the effectiveness of the scheme,  to
   derive some conservative peak delay estimate to be used at the set up
   phase.  To  this purpose we use an nD/D/1 queuing model where  the  n
   sources  generate service requests at a constant  inter-arrival  time
   equal to T [5][6].

   To  obtain a conservative estimate under any network load  condition,
   we  evaluate the delay suffered when the utilization factor is  close
   to one.

   Using   the approach in [5], we have considered three cases in  which
   the  channel capacity is M = 25,50,100 connections of the same  rate.
   The  average waiting plus transmission delay suffered by the  packets
   of a connection when all connections are active is shown in Table  I.
   The  delays  are  expressed  in  transmission  time  units  (m),   in
   interarrival time units (m'), in milliseconds (m'') assuming T=30  ms
   (which can model 32 Kb/s voice channels and 1000 bit packets), and in
   milliseconds (m''') assuming T=1 ms (which can model 1 Mb/s  channels
Borgonovo                       Expires:02/99                   [Page 5]


INTERNET-DRAFT       <draft_borgonovo_qos_ds_00.txt>        29 July 1998


   and 1000 bit packets).


                            Table I.
   ---------------------------------------------------------
   |  M  |  m(D)  |  s(D)  |  m'(T)  |  m"(ms)  |  m"'(ms) |
   |     |        |        |         |(T=30 ms) | (T=1 ms) |
   ------------------------------------------------------- -
   |  25 |  3.51  |  1.52  |  0.140  |   4.21   |  0.140   |
   |  50 |  4.88  |  2.09  | 0.0977  |   2.93   | 0.0977   |
   | 100 |  6.85  |  2.79  | 0.0685  |   2.05   | 0.0685   |
   ------------------------------------------------------- -

   Column  two  shows  that, for any  link  bandwidth,  absolute  delays
   decrease  when  the size of connections increases. For  the  case  in
   which  sources  have  different, though constant,  rates  no  general
   solution  exists. However, it is expected that the replacing of  some
   lower  rate connections with an equivalent high rate connection  will
   not  impair  performance since the high rate connection  generates  a
   more  regular arrival pattern than the slower  connections  replaced.
   This conjecture is substantiated by our simulation results, therefore
   we  assume  that  in  an  environment  with  mixed  rate  sources   a
   conservative delay bound is attained by assuming that all connections
   are of the smallest allowed rate.

   Column  four shows that if delay is measured in  interarrival  times,
   the  delay  decreases as the number of  connections  increases.  This
   means  that if a lower bound to the capacity of the path is used  for
   delay evaluations, an upper bound is guaranteed.

   Finally,  a conservative estimate on the connection end-to-end  delay
   can be attained by assuming that delays add hop-by-hop as independent
   random  variables.  Also  this assumption  is   conservative  as  the
   pipeline  effect along the connection path reduces the queuing  delay
   at  nodes other than the first. Thus, the peak delay evaluation of  a
   connection with k hops can be attained assuming a normal distribution
   for the total delay.

   Table  II  shows three examples of peak delay evaluations  using  the
   values in Table I. The first two are based on a minimum allowed  rate
   of  33  packet/sec  (e.g.  voice  channels at  32  kb/s  with  30  ms
   interarrival  time),  and  assuming that at least either  100  or  25
   connections can be accommodated along an 8 hop path.

   The  third  is based on a minimum allowed rate of 1 Mb/s  with  1  ms
   interarrival  time,  representing the case for voice  trunk  channels
   within  a provider domain, and assuming that at least 25  connections
   can be accommodated along an 8 hop path.

   The  results  shown refer only to class 2 traffic.  Class  1  traffic
   (scout  packets) has very little influence on the delay since it  can
   delay  class 2 packets for at most one transmission time, because  of
Borgonovo                       Expires:02/99                   [Page 6]


INTERNET-DRAFT       <draft_borgonovo_qos_ds_00.txt>        29 July 1998


   the  non-preemptive priority. Class 0 packets may alter the  analysis
   shown  if  they  are  allowed a size  considerably  larger  than  the
   constant rate packets.

                              Table II.
   - --------------------------------------------------------------
   |   rate  | mean delay | Standard deviation | 0.999 percentile |
   | capacity|    (ms)    |       (ms)         |       (ms)       |
   - --------------------------------------------------------------
   | 32 kb/s |            |                    |                  |
   |  (100)  |    16.4    |        1.58        |        21.2      |
   | 32 kb/s |            |                    |                  |
   |  (25)   |    33.7    |        5.17        |        49.3      |
   |  1 Mb/s |            |                    |                  |
   |  (25)   |    1.12    |        0.172       |        1.64      |
   ----------------------------------------------------------------

   The set-up procedure uses the values indicated in Table I to evaluate
   the 0.999 percentile, which depends on the number of hops  traversed,
   and to determine whether the delay QoS is met.

   Note,  however, that due to the strong correlation among  packets  of
   the same connection, the fraction 0.001 does not represent the packet
   dropping  probability suffered by any connection, but  it  represents
   the fraction of connections that suffer loss of packets.

3. Measures

   Preliminary simulation results have been obtained by simulating an  8
   node network, interconnected by a unidirectional and homogeneous ring
   structure.  Equal  rate  traffic  is  generated  at  any  nodes,  and
   destination nodes are chosen either 1 or 8 hops apart in the ratio 12
   to  1,  so that at any node a consistent fraction of  traffic  (about
   60%) is renewed. With this structure the complexity of the simulation
   environment is kept low while observing sufficiently long paths  with
   limited pipeline effect, a most critical condition.


                            Table III.
   -------------------------------------------------------------------
   | connection |pck.dropping|     delay thresholds (ms)    | average|
   |   rate     |   classes  |                              | delay  |
   |    1 Mb/s  |            | 1 |  1.1|  1.2|  1.3| 1.4|1.5|  1.11  |
   |   32 Kb/s  |            |30 |  33 |  36 |  39 | 42 | 45|  33.3  |
   | -----------------------------------------------------------------
   |            | 0 - 0.001  | 0 |0.084|0.167|0.417|0.75| 1 |        |
   |            |0.001-0.01  | 0 |   0 |   0 |   0 |  0 | 0 |        |
   |            |0.01 - 0.1  | 0 |   0 |   0 |   0 |  0 | 0 |        |
   |            |  0.1 - 1   | 1 |0.916|0.833|0.583|0.25| 0 |        |
   -----------------------------------------------------------------


Borgonovo                       Expires:02/99                   [Page 7]


INTERNET-DRAFT       <draft_borgonovo_qos_ds_00.txt>        29 July 1998


   In  our simulations the network has been loaded one connection  at  a
   time,  until saturation is reached, using the call  set-up  mechanism
   described in the previous sections. In Table III we report, for a few
   delay   thresholds,  the  percentage  of  8  hop   connections   that
   experienced a packet dropping probability (i.e. a delay greater  than
   the  threshold) within the class indicated in the first  column.  The
   average  delay  is reported in the last column. The capacity  of  the
   links is assumed 25 times the bandwidth required by each connection.

   The bimodal behavior of the distribution in Table III confirms that a
   connection  is either good or bad. Furthermore, the  delay  threshold
   with no packet dropping is within the bound given in Table II.



4. References

   [1]  K.  Nichols, V. Jacobson, L. Zhang, ``A  Two-bit  Differentiated
   Services  Architecture for the Internet'', IETF Internet Draft,  Nov,
   1997.

   [2]  R. Braden, L. Zhang, S. Berson, S. Herzog, S. Jamin,  ``Resource
   ReSerVation Protocol (RSVP)-Version 1 Functional  Specification''IETF
   Request For Comments 2205, Sep. 1997.

   [3]  P.P  White, ``RSVP and Integrated Services in  the  Internet:  A
   Tutorial'',  IEEE  Communication  Magazine,  vol.  35,  no.  5,   May
   1997,pag. 100.

   [4] F. Borgonovo and L. Fratta, `` Deflection Networks: Architectures
   for Metropolitan and Wide Area Networks'', Computer Networks and ISDN
   Systems, Vol. 24, No. 2, April 1992, pp.171-183.

   [5]  A.  E. Eckberg, "The single server queue with  periodic  arrival
   process  and deterministic service time", IEEE Trans. on Comm.,  Vol.
   COM-27, pp. 556-562, 1979.

   [6]  G. Ramamurthy, B. Sengupta, "Delay analysis of the packet  voice
   multiplexer  by the SD_i/D/1 queue", IEEE Trans. on Comm., Vol.  COM-
   39, no. 7, July 1991.












Borgonovo                       Expires:02/99                   [Page 8]

INTERNET-DRAFT       <draft_borgonovo_qos_ds_00.txt>        29 July 1998

5. Authors' Addresses

   Flaminio Borgonovo
   Dipartimento di Elettronica e Informazione
   Politecnico di Milano
   P.zza L. da Vinci 32,
   20133 MILANO, Italy
   Email: borgonov@elet.polimi.it
   Fax: +39 02 2399 3413
   http://www.elet.polimi.it/people/borgonov/

   Luigi Fratta
   Dipartimento di Elettronica e Informazione
   Politecnico di Milano
   P.zza L. da Vinci 32,
   20133 MILANO, Italy
   Email: fratta@elet.polimi.it
   Fax: +39 02 2399 3413
   http://www.elet.polimi.it/people/fratta/

   Antonio Capone
   Dipartimento di Elettronica e Informazione
   Politecnico di Milano
   P.zza L. da Vinci 32,
   20133 MILANO, Italy
   Email: capone@elet.polimi.it
   Fax: +39 02 2399 3413
   http://www.elet.polimi.it/people/capone/

   Mario Marchese
   Dipartimento di Elettronica e Informazione
   Politecnico di Milano
   P.zza L. da Vinci 32,
   20133 MILANO, Italy
   Email: mmarches@elet.polimi.it
   Fax: +39 02 2399 3413

   Chiara Petrioli
   Dipartimento di Elettronica e Informazione
   Politecnico di Milano
   P.zza L. da Vinci 32,
   20133 MILANO, Italy
   Email: chiara@cerbero.elet.polimi.it
   Fax: +39 02 2399 3413