Internet DRAFT - draft-azeem-tcpfriendly-diffserv

draft-azeem-tcpfriendly-diffserv



HTTP/1.1 200 OK
Date: Mon, 08 Apr 2002 22:38:40 GMT
Server: Apache/1.3.20 (Unix)
Last-Modified: Wed, 24 Feb 1999 19:22:06 GMT
ETag: "2e6c16-57af-36d4515e"
Accept-Ranges: bytes
Content-Length: 22447
Connection: close
Content-Type: text/plain







Internet Engineering Task Force         Feroz Azeem/ Amit Rao/
INTERNET-DRAFT                          Xiuping Lu/Shiv Kalyanaraman
draft-azeem-tcpfriendly-diffserv-00.txt Rensselaer Polytech Institute
                                                          March, 1999
                                              Expires: September 1999

     TCP-Friendly Traffic Conditioners for Differentiated Services

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 informational draft presents performance problems associated
   with TCP flows running over the assured service. It proposes the use
   of TCP-friendly differentiated services building blocks, specifically
   TCP friendly traffic conditioners to alleviate these problems.

1. Introduction

   This draft initially presents performance analysis of TCP over a
   simplified version of the assured service [af] having a single class
   and one-bit drop preference (called "assured service" henceforth in
   this draft).  These results details problems some of which have also
   been noted  by Ibanez et al [ibanez]. We find that use of TCP-
   friendly building blocks, specifically traffic conditioners using
   shaping, marking and TCP rate increase dampening provide substantial
   improvement in performance.




Azeem, Amit, Lu, Kalyanaraman                                   [Page 1]





INTERNET-DRAFT     TCP-Friendly Traffic Conditioners          March 1998


2. Performance problems of TCP over Assured Service.

   It is well known that TCP Reno (the large installed base of TCP
   implementations) has serious performance problems if it encounters
   "per-connection burst drop" of packets, i.e., if a connection sees a
   number of packets with nearby sequence numbers dropped. Even three
   consecutive packets dropped can lead to a timeout plus multiple
   SSTHRESH reductions [fred]. Also the definition of "burst" varies
   depending upon per-connection window size. For example a new
   connection with a small window may be hurt with a single packet drop
   itself [fred].

   At bottlenecks, packets may be dropped in bursts during congestion
   events. We call these drops "aggregate burst drops" since it may span
   a number of connections. And the number of packets dropped in a burst
   in such cases depends upon the length of the congestion event at the
   bottleneck. Many congestion events last for a short duration which
   results in unfairness (as measured by variance in per-connection
   goodput) even in symmetric configurations (where RTT does not vary)
   because the aggregate burst drop is not spread fairly over all the
   congestion-causing connections. Of course the unfairness is
   exacerbated for high speed links, large number of sources and
   heterogeneous RTT cases [padhye, ibanez, packeteer].


   We also find that the probability of aggregate burst drop high when a
   majority of TCP connections are in the slow start phase (due to the
   super-linear nature of window increase). This is likely for sources
   performing short transfers (as in WWW applications). Further the
   probability of per-connection burst drop increases since packets each
   source tends to arrive in batches rather than being interleaved with
   other connection packets.

   Finally we find that optimization of what we call "service provider
   metrics" (utilization, queue length, drop rate) does not necessarily
   lead to optimization of "user metrics" (average goodput and variance
   in per-connection goodput).

   We find that an important reason for these problems is the lack of
   TCP friendly building blocks (droppers, markers, shapers, PHBs) in
   the network.  By "TCP-friendly" we mean the capability of these
   building blocks to: a) provide for packet interleaving, b) protect
   small-window connections from drop, c) convert aggregate burst drop
   into interleaved non-bursty per-connection drop and d) reduce packet
   burstiness created by TCP.

   We present results of our preliminary work on developing such
   components and find that TCP-friendly components allow a marked



Azeem, Amit, Lu, Kalyanaraman                                   [Page 2]





INTERNET-DRAFT     TCP-Friendly Traffic Conditioners          March 1998


   improvement in performance. The most critical component we found was
   the shaper.

3. TCP-Friendly Building Blocks

   In general each and every building block along the connection path
   could be made TCP friendly. We identify some components which
   particularly relate to diff-serv.

   a) Shaping: Shaping is part of the traffic conditioner in diff-serv.
   We develop a simple shaper which shapes output rate to be a scaled
   factor of the measured, smoothed input rate. In this sense, it is not
   dependent upon a predefined peak rate or average rate and requires
   just a measurement interval and averaging parameter to be defined.
   This shaping can be done at a per-flow or per-behavior aggregate
   level.

   The idea is to reduce packet burstiness by simply smoothing out the
   input burst while roughly preserving the input rate. If done at a
   per-flow level or over an aggregate of a small number of flows, the
   shaping mechanism also interleaves packets of multiple flows. The
   cost of shaping is delay at the shaper. We find that even this simple
   shaping mechanism provides a substantial improvement in performance
   and we are working on new versions of the shaper which counter the
   delay penalty using adaptive parameter settings.


   b) Packet marking: Packet marking is part of the traffic conditioner
   in diff-serv. We develop a simple TCP friendly packet marking
   strategy which extends the leaky bucket technique. Given a set of
   tokens in an interval, it marks consecutive packets in the beginning
   of the interval as "in-profile" until it hits either the middle of
   the interval or finishes half the available tokens. In the latter
   case, it marks every other subsequent packet as "in-profile" and
   transfers excess tokens to the next interval.

   The goal is not to have high probability of dropping consecutive
   packets in a flow (i.e. convert an "aggregate burst drop" into an
   "interleaved per-connection drop"), and also protect flows with small
   windows. But this scheme suffers from the fact that packets with
   nearby sequence numbers can be dropped with high probability. It also
   does not provide complete protection for small window connections.
   There is room for significant improvement of this scheme and we are
   working on several variants. Accordingly, our performance analysis
   indicated that the marking strategy did not significantly explain
   variation in metrics, except for the fact that the total number of
   packets dropped was usually smaller when this marker was used.




Azeem, Amit, Lu, Kalyanaraman                                   [Page 3]





INTERNET-DRAFT     TCP-Friendly Traffic Conditioners          March 1998


   c) TCP Rate Increase Dampers: This is a new sub-component of the
   traffic conditioner which can limit the rate of increase of TCP
   windows by limiting the rate of release of acknowledgements. We
   approximated this functionality by implementing it in the source TCP
   simulation code itself. The limiting of TCP rate increase is most
   effective in smaller RTT configurations (small WANs or MANs) which
   also have high bandwidth and a large number of flows. This is a very
   crude type of TCP rate increase limiter. Packeteer Inc. [packeteer]
   builds sophisticated TCP rate-control components. These components
   can check TCP performance more tightly and over a wider range of RTTs
   through control of the left, right edges of the TCP window in
   addition to control of the ack rate as suggested here.

   d) Drop policies: Drop policies are part of the per-hop behavior
   (PHB). Examples of superior drop policies are FRED, ERED [fred,ered]
   which can allocate loss probabilities during a congestion event in a
   more controlled TCP-friendly manner. While we have work-in-progress
   in this area, we do not present results about this dimension in this
   draft.

   e) Edge-to-edge feedback control: Edge-to-edge feedback control
   introduced in an earlier work by our group [edge-to-edge] involves a
   simple protocol between ingress and egress conditioners. Though our
   initial work in the mentioned reference involves participation of
   interior router, our current work involves only the two edge
   conditioners. In this sense, edge-to-edge control is very similar to
   end-to-end control and it does not require standardization or
   interior router participation. Edge-to-edge control is TCP-friendly
   in ths sense that it allows better use of distributed buffer
   resources in the network to reduce packet drop rate and probability
   of burst drops. It also provides limited protection against denial of
   service attacks and improves fairness in resource allocation. We are
   developing it to provide a basis for some forms of traffic
   engineering and congestion-sensitive pricing. The key issue is the
   control overhead required for achieving the different goals just
   mentioned. This is work-in-progress and simulation results are not
   reported in this draft.

   Observe that these solutions can work at different levels of
   granularity: from per-microflow to per-behavior-aggregate. The former
   solutions tradeoff somewhat increased complexity for tighter control
   over performance. These are just examples of components which can be
   adapted to accomodate TCP especially and non-TCP type of flows.



4. Simulation Configuration and Parameters:




Azeem, Amit, Lu, Kalyanaraman                                   [Page 4]





INTERNET-DRAFT     TCP-Friendly Traffic Conditioners          March 1998


   We use a simple symmetric N-source-N-destination configuration where
   the N TCP connections go through a single bottleneck.  The general
   configuration (unless other wise mentioned is shown below). The
   traffic conditioning functionality (shaping, marking etc) is done at
   R0 and R1. R2 is the bottleneck router. All links have a length of
   1000km.


          1.5Mb                                      1.5Mb
        (All links)                           (All links)
   S   s1__                          ______ d1          R
   e   s5__ RO===                   / _____d5           e
   n              \      1.5 Mbps //      .            c
   d                 R2 ---------R3        .            e
   e   s6  __     //              \_____ d6            i
   r   s10 __ R1===                ______ d10          v
   s                                                    e
                                                        r
                 DATA -->          <--- ACKs            s


   We vary the following parameter dimensions:
   - TCP-friendly component (or combination of components)
   - Bottleneck link speed
   - Round trip time
   - Number of connections
   - Staggered connection start times


   We split our metrics into two parts:
   A. Service Provider (or operator) metrics: The operators key
   resources are bandwidth and buffers and hence the metrics which
   measure the tradeoffs among these resources are:
           A1. Average link Utilization: low link utilization, given
           adequate load is unacceptable. [We use the average goodput
           metric as a partial proxy for this metric]
           A2. Average Queue Length: Low average queue lengths imply
           lower average queueing delay experienced by participating
           connections. Prefer low queue lengths combined with high
           utilization.
           A3. Maximum Queue Length: Very high maximum queue lengths
           indicate high buffer requirements.
           A4. Packet drop rate: Packets dropped represent wasted
           bandwidth and buffer resources on upstream links.

   B. User Metrics: The user is interested in per-flow goodput (assuming
   infinite flows). This requires us to use N metrics where N = number
   of flows). But for brevity, we use:



Azeem, Amit, Lu, Kalyanaraman                                   [Page 5]





INTERNET-DRAFT     TCP-Friendly Traffic Conditioners          March 1998


           B1. Average (per-flow) Goodput: This quantity which excludes
               retransmitted packets should be as high as possible.
           B2. Standard deviation in (per-flow) goodput: This quantity
               is a rough measure of fairness. Ideally, for a single
               bottleneck with infinite transfers, this metric should
               be close to zero.

   We conduct a full factorial simulation and use linear regression
   modeling as described in [jain91]. Though we present a small set of
   results in this draft, we expect to expand it shortly.

   We have not examined the effects of dimensions such as:
   - Multiple classes
   - Multiple drop levels
   - Variable capacity bottlenecks
   - Heterogeneous RTT bottlenecks
   - Sharing of assured service class by TCP and non-TCP traffic

   We expect to do this and examine further alternatives in designing
   TCP friendly building blocks in the near future.

5. Simulation Results

   We have mentioned some the effects of the alternatives in section 2
   itself. Our main finding was that the simple shaper (esp when
   implemented at a per-flow granularity) provided for the maximum
   improvement across a wide variety of dimensions. The preliminary
   marker design reduced the total number of dropped packets (a provider
   metric), but did not significantly affect user metrics. The TCP rate
   limiter positively affected user metrics in small and medium RTT
   configurations.

   In the following sections we present a subset of simulations. More
   simulations will be presented in a revision of this draft and if
   possible in the IETF meeting. Each section has a table where the
   numbers in the table represent percentage of variation in the metric
   (denoted by the row header) which is explained by the given parameter
   (denoted by the column header). These numbers are generated by a
   linear regression fit to the results obtained [jain91]. A larger
   percentage (closer to 100%) denotes profound dependency of the metric
   on that parameter. A "-" denotes no perceptable dependency.

   The table also uses acronyms. The TCP rate increase limiter is
   denoted by "T", the shaping scheme is denoted by "S", Marking scheme
   by "M" and staggering of connection start times by "U". The notation
   "M+S" for example denotes the effect of interaction between marking
   and staggering. The notation TSMU denotes the interaction between all
   the four factors. Only the factors which show significant effects



Azeem, Amit, Lu, Kalyanaraman                                   [Page 6]





INTERNET-DRAFT     TCP-Friendly Traffic Conditioners          March 1998


   (above 5%) for more than one metric (row) are chosen in the columns.

5.1 Low speed bottleneck, Small Number of Sources

   The link speeds (including the bottleneck) are 1.5Mbps.  The
   configuration has 10 connections, which is split into two parts and
   shaping is done on 5 connections as an aggregate.


       TCP-Rate  Shaping  Marking Stagger T+S S+M  TSMU
           (T)   (S)       (M)    (U)
    Avg Q   -    62        16      -       -   18    -
    Max Q   -    63        -       9       -    8    -
   Drops    -     -        39      -       -   48    -
   Avg G/put -    -        8       7       7    7    7
   SD G/put -    26        -      10       11   7    7


         Table 1: Low speed bottleneck, Small Number of Sources
         ------------------------------------------------------


   Scanning through the columns, we observe that shaping has the maximum
   effect on metrics such as queue lengths and fairness (standard
   deviation in goodput). But we note that a high percentage dependency
   does not mean that the parameter gives improvement in performance.
   For example, the larger queue sizes were the result of shaping
   parameters.

   Marking tends to reduce the total number of drops, especially in
   conjunction with shaping, while TCP rate increase damping has almost
   no effect.


5.2 LAN Access Links, Low speed bottleneck


       TCP-Rate Shaping  Marking Stagger  M+U  T+S  TM  SMU
          (T)    (S)      (M)    (U)
   Avg Q   10      -       -       -      8    10   -    -
   Max Q   10      -       -       -     16     9  11   12
   Drops    -     31       19      -      -     -   -    -
   Avg G/put-     46       36      -      -     -   -    -
   SD G/put 78    12       23      -      -     -   -   24


         Table 2: LAN Access Links, Low speed bottleneck
         -----------------------------------------------



Azeem, Amit, Lu, Kalyanaraman                                   [Page 7]





INTERNET-DRAFT     TCP-Friendly Traffic Conditioners          March 1998


   Again scanning through the columns we observe that shaping still has
   a significant effect. However, the effects of marking and TCP rate
   increase damping have increased in this situation. Specifically, TCP
   rate dampening accounts for nearly 78% of variation in fairness. The
   reason for the increased effect of the TCP rate dampening is because
   smaller RTTs imply faster window increases, which in turn leads to
   burstiness, and variance in throughput. Now, with rate increase
   dampening, the probability of burstiness is reduced leading to better
   fairness.


5.3 Effect of high speed bottleneck

   In this simulation set, we use link speeds of 150 Mbps for all links.

          TCP-Rate  Shaping  Marking Stagger M+U T+S  SM  SMU  SU
              (T)    (S)     (M)      (U)
    Avg Q      -     31       -        -     25  8    -   25   -
    Max Q      -     68       -        -      -  9    -   -    -
    Drops      -     57       15       -      -  10   7   -    -
   Avg G/put   -     43       7        28     -  -    -   -   28
   SD G/put    -     55       -        -      -  -    -   -   14

       Table 3: WAN links, High Speed links
       ------------------------------------


   We observe that shaping again has considerable impact on all metrics.
   We do note that the impact is somewhat negative on the provider
   metrics (queue lengths and drops), but at the same time results in a
   substantial goodput increase. Effects of other parameters are nominal
   and scattered in terms of metrics affected.

6. Summary

   In summary we make a case for developing TCP-friendly building blocks
   in diff-serv by looking at generic TCP problems and demonstrating
   that simple enhancements in some of the building blocks can lead to
   significant performance enhancements (especially using shaping in
   traffic conditioners).


7. Acknowledgements

   Thanks are due to DARPA-ITO, NSF Special Projects in Networking,
   Packeteer Inc., and Nortel Networks Inc. for supporting our work in
   this and related areas.




Azeem, Amit, Lu, Kalyanaraman                                   [Page 8]





INTERNET-DRAFT     TCP-Friendly Traffic Conditioners          March 1998


8. References


   [af] J. Heinanen, et al., Assured Forwarding PHB Group.
   Internet draft draft-ietf-diffserv-af-05.txt, February 1999.


   [ibanez] J. Ibanez, K. Nichols, "Preliminary Simulation Evaluation of
   an Assured Service" <draft-ibanez-diffserv-assured-eval-00.txt>,
   August, 1998.

   [fred] Dong Lin and Robert Morris, "Dynamics of Random Early
   Detection," Proceedings of SIGCOMM'97, August 1997.


   [ered] W. Feng, D. Kandlur, D. Saha, K. Shin,
   "Techniques for Eliminating Packet Loss in Congested TCP/IP Networks,"
   U. Michigan CSE-TR-349-97, November 1997.


   [padhye] Jitendra Padhye, Victor Firoiu, Don Towsley, and Jim Kurose,
   "Modeling TCP Throughput: A Simple Model and its Empirical
   Validation," Proceedings of SIGCOMM'98, Vancouver, August 1998.


   [packeteer] Prasad Bagal, Shivkumar Kalyanaraman, Bob Packer,
   "Comparative study of RED, ECN and TCP Rate Control,"
   preprint. To become available in: http://www.packeteer.com/tcprate/

   [edge-to-edge] S. Kalyanaraman, D. Harrison, S. Arora, K. Wanglee,
   G. Guarriello, "One-bit Feedback Enhanced Differentiated Services
   Architecture," IETF Internet Draft,
   draft-shivkuma-ecn-diffserv-00.txt, March 1998. Available from:
   http://www.ecse.rpi.edu/Homepages/shivkuma/research/papers-rpi.html


   [jain91] Raj Jain, "The Art of Computer Systems Performance Analysis,"
   John Wiley and Sons Inc., 1991.


   [RFC2474] K. Nichols, et al., Definition of the Differentiated
    Services Field (DS Field) in the IPv4 and IPv6 Headers.  RFC 2474,
    December 1998.

   [RFC2475] S. Blake, et al., An Architecture for Differentiated
   Services. RFC 2475, December 1998.





Azeem, Amit, Lu, Kalyanaraman                                   [Page 9]





INTERNET-DRAFT     TCP-Friendly Traffic Conditioners          March 1998


Authors:

   Feroz Azeem , Amit Rao, Xiuping Lu and Shivkumar Kalyanaraman
   Dept of Electrical, Computer and Systems Engg,
   Rensselaer Polytechnic Institute (RPI)
   110, 8th Street, Room JEC 6003,
   Troy NY 12180-3590
   Phone: +1 (518) 276 8979
   Fax: +1 (518) 276 2433
   Email: {feroza@rpi.edu, amit@networks.ecse.rpi.edu, lux2@rpi.edu,
           shivkuma@ecse.rpi.edu}

   This internet draft expires on September 1999






































Azeem, Amit, Lu, Kalyanaraman                                  [Page 10]