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. 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 http://www.ietf.org/ietf/1id-abstracts.txt The list of Internet-Draft Shadow Directories can be accessed at http://www.ietf.org/shadow.html. Abstract 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 follows: 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 interfaces. 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. References [RFC2212] Shenker, S., Partridge, C., and Guerin, R., ``Specification of Guaranteed Quality of Service,'' RFC2212, September 1997. [WFQ1992] 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 1992. [QST1975] Kleinrock, L., ``Queuing Systems Volume 1 Theory,'' John Wiley, 1976. [ITC1963] Abramson, N., ``Information Theory and Coding,'' McGraw-Hill, 1963. 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 EMail: fujikawa@real-internet.org EMail: yoshito@bio.i.kyoto-u.ac.jp EMail: ikeda@i.kyoto-u.ac.jp MATSUFURU Norio 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 Email: matu@net.ipc.hiroshima-u.ac.jp 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 EMail: mohta@necom830.hpcl.titech.ac.jp FUJIKAWA Kenji Expires on 4 October [Page 8]