Internet DRAFT - draft-fujikawa-intserv-cs


INTERNET DRAFT                                              FUJIKAWA Kenji
draft-fujikawa-intserv-cs-00.txt                          FUJIMOTO Yoshito
                                                              IKEDA Katsuo
                                                          Kyoto University
                                                           MATSUFURU Norio
                                                      Hiroshima University
                                                             OHTA Masataka
                                             Tokyo Institute of Technology

                                                  Real Internet Consortium
                                                              4 April 2000

          Comfortable Service: A New Type of Integrated Services 
                     Based on Policed Priority Queuing

Status of this Memo

    This document is an Internet-Draft and is in full conformance
    with all provisions of Section 10 of RFC2026.

    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 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."

    The list of current Internet-Drafts can be accessed at

    The list of Internet-Draft Shadow Directories can be accessed at


    This draft defines Comfortable Service (CS), which realizes 
    statistical end-to-end QoS guarantee in the Internet. CS is 
    based on Policed Priority Queuing (PPQ) which processes packets 
    in a constant time, and statistically guarantee the maximum 
    time of queuing delay.


FUJIKAWA Kenji               Expires on 4 October                [Page 1]

INTERNET DRAFT                      CS                          April 2000

1. Introduction

   Guaranteed service[RFC2212] based on Weighted Fair Queuing
   (WFQ)[WFQ1992] is proposed as a type of Integrated Services (IntServ).
   In guaranteed service, it takes O(log(n)) time to insert each input
   packet into an output queue, or to pick it up from the queue because
   of sorting, where n is the number of flows that should be treated
   individually. WFQ strictly guarantees the maximum delay time, however
   this does not mean all the packets will actually reach the end in the
   maximum delay time, because the network cannot completely be free from
   bit errors or packet loss.
   We define a queuing method, Policed Priority Queuing (PPQ) , in which
   the time to insert each input packet to an output queue and the time
   to pick it up from the output queue are constant, and the maximum
   delay time is guaranteed statistically. We then define a new type of
   IntServ, Comfortable Service (CS) , which is based on PPQ and realizes
   statistical end-to-end QoS guarantee in the Internet.

2. Definition of QoS Guarantee

   In this article, Quality of Services (QoS) guarantee is defined as
   when transmitting packets
     * with the defined traffic pattern,
     * with a specified average bandwidth,
   they reach the end
     * at the defined probability (at the defined packet loss ratio),
     * in a specified maximum delay time.
   This QoS guarantee is necessary and sufficient for multimedia
   applications such as audio and video transmission.

3. Structure of Router Based on PPQ for QoS Guarantee

   A router based on Policed Priority Queuing (PPQ) for QoS guarantee is
   shown in Figure I1.

FUJIKAWA Kenji               Expires on 4 October                [Page 2]

INTERNET DRAFT                      CS                          April 2000

 Input      +----------------------------------------------------+ Output
 Interfaces |          Flow1  +--+                     ----+     | Interfaces
            |           /---> |P1| ------------------>  QQ |     |
            |          /      +--+ \ /--------------->     |     |
            |     +-+ /Flow2  +--+  X                  ----+ --> | ------>
    ------> | --> |C| ------> |P2| / \--------> -----------+ --> |
            |     +-+ \Flow3  +--+ ----------->         BQ |     |
            |      \ \ \----> +--+    /------->            |     |
            |       \ \       |P3| \ / /------> -----------+     |
            |        \ \      +--+ \X /                          |
            |         \ \----------/\X                 ----+     |
            |          \            /\\-------------->  QQ |     |
            |           ----------\/  X-------------->     |     |
            |                     /\ / \               ----+ --> | ------->
            |      +-+ ----------/  X   \-----> -----------+ --> |
    ------> | -->  |C| Flow4  +--+ / \-------->         BQ |     |
            |      +-+ -----> |P4| ----------->            |     |
            |        \        +--+  /---------> -----------+     |
            |         \------------/                             |

            C:     Classifier             QQ: QoS Queue
            P1-P4: Policer                BQ: Best-Effort Queue

                        Figure I1: Router based on PPQ

   The process of packets is as follows:
    1. Packets of multiple flows are input into a router from input
    2. By classifiers, each packet is classified into a QoS-guaranteed
       type (from Flow1 to Flow4 in Figure I1 ) or a best-effort type.
    3. An output interface is determined.
         1. A packet of best-effort flows is queued in the best-effort
            queue at the output interface determined by packet analysis.
         2. In terms of packets of a QoS-guaranteed flow, the policer
            associated with the flow checks if the packets violates the
            bandwidth the flow has requested in advance. Legal packets
            are queued in the QoS queue at the output interface, and
            illegal ones are queued in the best-effort queue at the same
            output interface.
    4. Packets are transmitted.
   The following rules are used when transmitting packets:
     * A QoS queue has an absolutely high priority.
     * The process is executed in First Come First Serve (FCFS) manner.
     * A router transmits packets in a best-effort queue when the
       corresponding QoS queue becomes empty.
     * A packet transmission is not preempted until it is over, when it

FUJIKAWA Kenji               Expires on 4 October                [Page 3]

INTERNET DRAFT                      CS                          April 2000

       is once started.
   These processes can be executed in a constant time except the process
   at classifiers. By means of hashing or using Content Addressable
   Memory (CAM), the process at classifiers can also be executed in a
   constant time. Note that sice a policer does not configure a queue,
   the queuing delay does not occur at the policer.

4. Queuing Model and Its Analysis

  4.1 Queuing Model M/D/1/K
   In PPQ, QoS-guaranteed flows are being processed, almost whenever
   packets exist in a QoS queue. Thus, QoS-guaranteed flows are
   considered to be independent of best-effort flows. Only the QoS queue
   is discussed hereafter.
   The length of a QoS queue at an output interface is influenced by all
   the QoS-guaranteed flows directed to the interface. Assuming that each
   flow is transmitted from the upstream node at exponential distribution
   intervals, the arrival intervals of mixed flows at the queue in the
   router also becomes exponential distribution.
   We regard the processing time of each packet constant, considering the
   processing time of the longest packet. We also let the MTU be 1280
   bytes, with taking into account IPv6.
   As a result, when let the maximum queue length be K , the behavior of
   a QoS queue can be treated as M/D/1/K.
  4.2 Analysis of Delay and Packet Loss Ratio
   Using an M/D/1/K queuing model, we analyze the behavior of a QoS queue
   and clarify the delay and packet loss ratio.
   We let the processing time of one packet be constant in the above
   discussion. Then, we use packet per second (pps) instead of bit per
   second (bps) for majoring both router's processing capacity and the
   rate of arriving packets of QoS-guaranteed flows.
   Let the processing capacity of a certain output interface be u (stands
   for mu in Greek characters) pps, the packet arrival rate of all the
   flows arriving at a certain QoS queue be l (stands for lambda) pps,
   and the maximum length of the queue be K. Here l equals to the total
   sum of l_i , where the arrival rate of flow i is l_i. The availability
   of the interface is given by p (stands for rho) = l/u.

FUJIKAWA Kenji               Expires on 4 October                [Page 4]

INTERNET DRAFT                      CS                          April 2000

   Generally, it is well known that a probability of queue overflow
   becomes very low, when p is less than 1.
   Though the detailed analysis is omitted here, the packet loss ratio
   for each p and each K is given by numerical analysis. This shows that
   in the case of the maximum queue length of 20, the packet loss ratio
   of 10^-5 is achieved even when 75% of the bandwidth is reserved.
   In other words, under the conditions that the maximum length of the
   queue is set to 20, and that only the reservations that consume 75% of
   the bandwidth are admitted, the packet loss ratio of 10^-5 can be
   guaranteed for every flow.
   Considering use in the Internet, even if only 75% of an output
   interface is utilized for QoS-guaranteed flows, the rest 25% is
   consumed by best-effort flows. This means the interface is fully
   utilized at any time.
   The maximum delay time is given by K/u , independent of the arrival
   time of each flow. For example, in the case of 100 Mbps, the queuing
   delay is 2 msec, while in the case of 10 Gbps, the queuing delay is no
   more than 20 usec. That is, at high-speed links, the queuing delay can
   be ignored against the transmission delay.
   According to PPQ, QoS guarantee can be easily achieved, where the
   packet loss ratio and the queuing delay are easily estimated.

5. ``Comfortable'' Service

   We define Comfortable Service (CS) as a new service for QoS guarantee.
   Here, comfortable means not completely guaranteed but statistically
   guaranteed, and comfortable for actual applications.
   First, we aim at the packet loss ratio of less than 10^-5 at a single
   router. Then, assuming that there is a case that at most 100 routers
   reside on the path, the end-to-end packet loss ratio becomes less than
   about 10^-3.
   Under the condition that the routers on the path of a flow employs
   PPQ, when a sender sends packets
     * at exponential distribution intervals or at less bursty intervals,
     * with an average bandwidth of l , which is reserved in advance,
   end-to-end QoS guarantee
     * with a probability of more than 1-10^-3 (at the packet loss ratio
       of 10^-3 ),
     * and with the queuing delay which is the sum of the transmission

FUJIKAWA Kenji               Expires on 4 October                [Page 5]

INTERNET DRAFT                      CS                          April 2000

       delay and the queuing delays K/u of all the routers.
   is realized.
   Each router can freely set up the values of K and p as long as it
   achieves the packet loss ratio of 10^-5. Here the packet loss ratio
   caused by bit errors on links should be further lower than 10^-5.

6. Issues

  6.1 Is Packet Loss Ratio of 10^-3 of Use?
   The packet loss ratio of 10^-3 may seem to be no use for communication
   requiring a severe loss ratio such as high-quality video transmission,
   however this is not correct.
   Shanon's theorem shows that channel capacity of a communication
   channel is determined by bandwidth and error probability of the
   channel, and that an error probability can be made as small as wished
   by means of block coding, as long as a transmitting rate is lower than
   the channel capacity. Instead, the theorem also implies that it takes
   more time for coding and decoding.
   Actually, error correction coding can drasticly reduce an error
   probability. Since many packets are handled together in strong error
   correction coding, delay for spooling these packets occurs. However,
   the delay is just 1/30 seconds even when 100 packets of 1280 bytes are
   handled together for error correction in a 30-Mbps communication. This
   can be ignored for humans. In addition, if this is a communication for
   digital video transmission of 30 frame per second, the delay of 1/30
   seconds is originally inevitable for JPEG coding. Error correction
   coding does not cause a new delay in this case.
   Therefore, an error probability can be reduced by sender's elaborate
   process. It is important to give the defined low error probability
   before communication, but is not important to provide various error
   probabilities for various applications.
  6.2 Limitation of PPQ
   PPQ is valid only on fast links, and not on slow links, since the
   delay is in inverse proportion to the rate of an output interface. On
   slow links of less than 10 Mbps, there is a case that WFQ can decrease
   the maximum delay more.

FUJIKAWA Kenji               Expires on 4 October                [Page 6]

INTERNET DRAFT                      CS                          April 2000

  6.3 Is M/D/1/K Model Appropriate?
   Estimation by the M/D/1/K model may be exaggerated, since the actual
   arrival intervals of a flow tends to be less bursty and more periodic
   than exponential distribution. In this case, more bandwidth can be
   assigned to QoS-guaranteed services by means of making p larger.
   However in the Internet, it is required to assign bandwidth to
   best-effort services if any. It is not required to utilize almost all
   the bandwidth for QoS guarantee.
   Consequently, the M/D/1/K model is appropriate and sufficient for QoS
   guarantee on the Internet in the real world.
  6.4 Synchronization Problem
   The synchronization problem where some end hosts come to send packets
   synchronously is sometimes stated. However, this can be easily avoided
   by means that each end host sends a packet with a random delay.


          Shenker, S., Partridge, C., and Guerin, R., ``Specification of
          Guaranteed Quality of Service,'' RFC2212, September 1997.
          Parekh, A., ``A Generalized Processor Sharing Approach to Flow
          Control in Integrated Services Networks,'' MIT Laboratory for
          Information and Decision Systems, Report LIDS-TH-2089, February
          Kleinrock, L., ``Queuing Systems Volume 1 Theory,'' John Wiley,
          Abramson, N., ``Information Theory and Coding,'' McGraw-Hill,


FUJIKAWA Kenji               Expires on 4 October                [Page 7]

INTERNET DRAFT                      CS                          April 2000

Authors' Address

    FUJIKAWA Kenji
    FUJIMOTO Yoshito
    IKEDA Katsuo
    Graduate School of Informatics
    Kyoto University
    Yoshidahonmachi, Sakyo-Ku, Kyoto City, 606-8501, JAPAN
    Phone: +81-75-753-5387
    Fax: +81-75-751-0482

    Graduate School of Engineering
    Hiroshima University
    Kagamiyama 1-4-2 Higashi-hiroshima City, 739-8526, JAPAN
    Phone: +81-824-24-6251
    Fax: +81-824-22-7043

    OHTA Masataka
    Computer Center
    Tokyo Institute of Technology
    2-12-1, O-okayama, Meguro-ku, Tokyo 152, JAPAN
    Phone: +81-3-5734-3299
    Fax: +81-3-5734-3415

FUJIKAWA Kenji               Expires on 4 October                [Page 8]