Abstract:
A new overlay apparatus and method to augment best-effort congestion control and Quality of Service in the Internet called edge-to-edge traffic control (FIG. 3) is disclosed. The basic architecture works at the network layer and involves pushing congestion back from the interior of a network, distributing across edge nodes (202, 206, FIG. 3) where the smaller congestion problems can be handled with flexible, sophisticated and cheaper methods. The edge-to-edge traffic trucking building blocks thus created can be used as basis of the several applications. These applicaitons include controlling TCP and non-TCP flows, improving buffer management scalability, developing simple differentiated services, and isolating bandwidth-based denial-of-service attacks. The methods are flexible, combinable with other protocols (like MPLS and diff-serv), require no standardization and can be quickly deployed.

Description:
BACKGROUND OF THE INVENTION  
         [0001]    I. Field of the Invention  
           [0002]    The present invention generally relates to computer network traffic management and control. In particular, the present invention relates to providing a method to improve computer network traffic congestion and computer network Quality of Service (QoS).  
           [0003]    II. Description of the Related Art  
           [0004]    Computer network traffic congestion is widely perceived as a non-issue today (especially in the ISP industry) because of the dramatic growth in bandwidth and the fact that many of the congestion spots are peering points which are not under the direct control of a single service provider. However, congestion will continue to increase and in some key spots, namely access links, tail circuits (to remote locations), international circuits and peering points, may ultimately pose unacceptable data network delay. As long as congestion exists at any point along an edge-to-edge path, there exists a need to relieve that congestion and to improve the Quality-of-Service (QoS) to avoid more serious delays as Internet usage continues to grow.  
         SUMMARY OF THE INVENTION  
         [0005]    The present invention provides a congestion control and Quality of Service apparatus and method which employ a best-effort control technique for the Internet called edge-to-edge traffic control. (In, the present invention, Congestion control and QoS are implemented together as a unitary apparatus and method.) The basic apparatus and method of the present invention works at the network layer and involves pushing congestion back from the interior of a network, and distributing the congestion across edge nodes where the smaller congestion problems can be handled with flexible, sophisticated and cheaper methods. In particular, the apparatus and method of the present invention provide for edge-to-edge control for isolated edge-controlled traffic (a class of cooperating peers) by creating a queue at potential bottlenecks in a network spanned by edge-to-edge traffic trucking building blocks, herein referred to as virtual links, where the virtual links set up control loops between edges and regulate aggregate traffic passing between each edge-pair, without the participation of interior nodes. These loops are overlaid at the network (IP) layer and can control both Transmission Control Protocol (TCP) and non-TCP traffic.  
           [0006]    The operation of the overlay involves the exchange of control packets on a per-edge-to-edge virtual link basis. To construct virtual links the present invention uses a set of control techniques which break up congestion at interior nodes and distribute the smaller congestion problems across the edge nodes.  
           [0007]    The edge-to-edge virtual links thus created can be used as the basis of several applications. These applications include controlling TCP and non-TCP flows, improving buffer management scalability, developing simple differentiated services, and isolating bandwidth-based denial-of-service attacks. The apparatus and methods of the present invention are flexible, combinable with other protocols (like MPLS and diff-serv), require no standardization and can be quickly deployed.  
           [0008]    Thus, the buffers at the edge nodes are leveraged during congestion in order to increase the effective bandwidth-delay product of the network. Further, these smaller congestion problems can be handled at the edge(s) with existing buffer management, rate control, or scheduling methods. This improves scalability and reduces the cost of buffer management. By combining virtual links with other building blocks, bandwidth-based denial of service attacks can be isolated, simple differentiated services can be offered, and new dynamic contracting and congestion-sensitive pricing methods can be introduced. The above system and method may be implemented without upgrading interior routers or end-systems. 
       
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0009]    The foregoing and other advantages and features of the invention will become more apparent from the detailed description of exemplary embodiments provided below with reference to the accompanying drawings in which:  
         [0010]    [0010]FIG. 1 illustrates a network system for the implementation of the congestion control and Quality of Service methods of the present invention;  
         [0011]    [0011]FIG. 2 illustrates another view of a network system for the implementation of the congestion control and Quality of Service methods for a class of the present invention;  
         [0012]    [0012]FIG. 3 illustrates a detailed network system to for use in describing the congestion control and Quality of Service methods for a class with ingress and egress traffic shown in accordance with the present invention;  
         [0013]    [0013]FIG. 4 shows a chart illustrating dynamic edge-to-edge regulation;  
         [0014]    [0014]FIG. 5( a ) illustrates a queue at a bottleneck; and  
         [0015]    [0015]FIG. 5( b ) illustrates a queue distributed across edges. 
     
    
     DETAILED DESCRIPTION OF THE INVENTION  
       [0016]    Referring now to the drawings, where like reference numerals designate like elements, there is shown in FIG. 1 a network node bottleneck  100 .  
         [0017]    The present invention is based upon the observation that at all times, the sum of the output rates of flows passing through a particular single network node bottleneck  100  is less than or equal to the capacity of (μ)  102  at the bottleneck  100 , as illustrated in FIG. 1. Most importantly, this condition holds during periods of congestion called “congestion epochs”. For purposes of this disclosure a “congestion epoch” is defined as any period when the instantaneous queue length exceeds a queue bound which is larger than the maximum steady state queue fluctuations. Chosen this way, the congestion epoch is the period of full utilization incurred when the mean aggregate load (λ) at a single bottleneck  100  exceeds mean capacity (μ). Congestion epoch does not involve packet loss in its definition and is a basis for “early” detection. In addition, for simplicity of explanation herein, a single bottleneck  100  is used in the following description, although the present invention is applicable to a network of bottlenecks  100  as well.  
         [0018]    The output rates of flows (ν i ) can be measured at the receiver and fed back to the sender. During congestion epochs each sender imposes a rate limit r i  such that r i ←min(βν i, , r i ) where β&lt;1. If each sender consistently constrains its input rate (λ i ) such that λ i ≦r i  during the congestion epoch, the epoch will eventually terminate. This is intuitively seen in an idealized single bottleneck, zero-time delay system because the condition Σβν i &lt;Σν i ≦μ causes queues to drain. In the absence of congestion, additive increase is employed to probe for the bottleneck capacity limits.  
         [0019]    The increase-decrease policy of the present invention is not the same as the well known additive-increase multiplicative-decrease (AIMD) policy, because the decrease policy of the present invention is based upon the output rate (ν i ) and not the input rate (λ i ). The policy of the present invention is hereto referred to as AIMD-ER (Additive Increase and Multiplicative Decrease using Egress Rate).  
         [0020]    The remaining part of the basic approach is a method to detect the congestion epochs in the system. The present invention utilizes two method for this purpose. The first method assumes that the interior routers assist in the determination of the start and duration of a congestion epoch. In the second method, edges detect congestion epochs without the involvement of interior routers. Specifically, in the first method, the interior router promiscuously marks a bit in packets whenever the instantaneous queue length exceeds a carefully designed threshold.  
         [0021]    The second method does not involve support from interior routers. To detect the beginning of a congestion epoch, the edges rely on the observation that each flow&#39;s contribution to the queue length (or accumulation), q i , is equal to the integral ∫(λ i ,(T)−v i (T))dT. If this accumulation is larger than a predefined threshold, the flow assumes the beginning of a congestion epoch. The end of the congestion epoch is detected when a one-way delay sample comes close to the minimum one-way delay.  
         [0022]    The present invention assumes that the network architecture is partitioned into traffic control classes. A traffic control class is a set of networks with consistent policies applied by a single administrative entity or cooperating administrative entities or peers. Specifically, it is assumed that edge-to-edge controlled traffic is isolated from other traffic which is not edge-to-edge controlled. As illustrated in FIG. 2, the architecture has three primary components: the ingress edge  202 , the interior router  204 , and the egress edge  206 . Nodes within a traffic control class that are connected to nodes outside the class and implement edge-to-edge control are known as edge routers  202 ,  206 . Any remaining routers within a class are called interior routers  204 . The methods of the present invention can be implemented on conventional hardware such as that of FIG. 2, where the ingress edge  202 , the interior router  204 , and egress edge  206  employ the means for performing the methods herein described.  
         [0023]    As shown in FIG. 3, under this method, the ingress node  202  regulates each edge-to-edge virtual link to a rate limit of r i . The actual input rate (i.e. departure rate from the ingress  202 , and denoted λ i ) may be smaller than r i . The present invention also assumes that the ingress node  202  uses an observation interval T for each edge-to-edge virtual link originating at this ingress  202 .  
         [0024]    Under the first method, a congestion epoch begins when an interior router promiscuously marks a congestion bit on all packets once the instantaneous queue exceeds a carefully designed queue threshold parameter. Since interior routers  204  participate explicitly, the present invention refers to this as the Explicit Edge Control (EEC) method. The egress node  206  declares the beginning of a new congestion epoch upon seeing the first packet with the congestion bit set. A new control packet is created and the declaration of congestion along with the measured output rate at the egress  206  is fed back to the ingress  202 . The interval used by the egress node  206  to measure and average the output rate is resynchronized with the beginning of this new congestion epoch.  
         [0025]    The congestion epoch continues in every successive observation interval where at least one packet from the edge-to-edge virtual link is seen with the congestion bit set. At the end of such intervals, the egress  206  sends a control packet with the latest value of the exponentially averaged output rate. The default response of the ingress edge  202  upon receipt of control packets is to reduce the virtual link&#39;s rate limit (r i ) to the smoothed output rate scaled down by a multiplicative factor (ν i ×3:0&lt;β&lt;1). The congestion epoch ends in the first interval when no packets from the link are marked with the congestion bit. The egress  206  merely stops sending control packets and the ingress  202  assumes the end of a congestion epoch when two intervals pass without seeing a control packet.  
         [0026]    The ingress node  202  uses a leaky bucket rate shaper whose rate limit (r) can be varied dynamically based upon feedback. The amount of traffic “I” entering the network over any time interval [t, t+T] after shaping is:  
           I[t,t+r]≦∫   t   t+r   r ( T ) dT+σ   (1)  
         [0027]    In inequality 1, r is the dynamic rate limit and σ is the maximum burst size admitted into the network. Assuming that all virtual links are rate-regulated, the queue threshold parameter can be set as Nσ where N is the number of virtual links, not end-to-end flows, passing through the bottleneck. A rough estimate of N, which suffices for this method, can be based upon the number of routing entries, and/or the knowledge of the number of edges whose traffic passes through the node. The objective is to allow at most σ burstiness per active virtual link before signaling congestion.  
         [0028]    The initialization of edge-to-edge virtual links occurs in a manner similar to TCP slow start, and is defined by the present invention as “rate-based slow start.” As long as there are sufficient packets to send the rate limit doubles each interval, when a rate-decrease occurs (in a congestion epoch), a rate threshold “thresh.”, is set to the new value of the rate limit after the decrease. The function of this variable is similar to the “SSTHRESH” variable used in TCP. While the rate-limit r i  tracks the actual departure rate λ i , rthresh i  serves as an upper bound for slow start. Specifically, the rate limit r i  is allowed to increase multiplicatively until it reaches rthresh i  or receives a congestion notification. Once the departure rate λ i  and the rate limit r i  are close to rthresh i  the latter is allowed to increase linearly by σ/T once per measurement interval T. The dynamics of these variables are illustrated in FIG. 4.  
         [0029]    The rate-decrease during a congestion epoch is based upon the measured and smoothed egress rate ν i . The response to congestion is to limit the departure rates (λ i ) to values smaller than ν i  consistently during the congestion epoch. A method for this is to limit λ i  by the rate limit parameter r i  =λ×ν i ,0&lt;β&lt;1 upon receipt of congestion feedback. The rate change (increase or decrease) is not performed more than once per measurement interval T. Moreover when there is a sudden large difference between the load λ i  and the egress rate ν i , the present method adds an additional compensation to drain out the possible queue built up in the interior.  
         [0030]    The measurement interval T used by all edge systems (both ingress  202  and egress  206 ) is set to the class-wide maximum edge-to-edge round-trip propagation and transmission delays, max_ertt, plus the time to mark all virtual links passing through the bottleneck when congestion occurs. The time to mark all virtual links can be roughly estimated as N max σ/μ min  where μmin is the smallest capacity within the class and N max  is a reasonable bound on the number of virtual links passing through the bottleneck. Since all virtual links use the same interval, they increase with roughly the same acceleration and will all backoff within T of being marked. The bound is not a function of RTT partly due to the fact that the rate limit increases by at most σ/T in every interval T, thus “acceleration” varies with the inverse of delay.  
         [0031]    To improve fairness in the system, the method optionally delays backoff through a method known as “delayed feedback response.” Specifically, the feedback received by the ingress node  202  is enforced after a delay of max_ertt−ertt i, , where ertt i  is the edge-to-edge round trip of the i-th virtual link. This step attempts to roughly equalize the time-delay inherent in all the feedback loops of the traffic control class.  
         [0032]    Lasdy, to quickly adjust to sharp changes in demand or capacity, the ingress  202  backs off by μ i /2 when packet loss occurs.  
         [0033]    Under a second method, as discussed above, the present invention also provides for edge-to-edge congestion control without interior router  204  involvement, herein referred to as Implicit Edge Control (IEC). IEC infers the congestion state by estimating the contribution of each virtual link to the queue length q i  by integrating the difference in ingress and egress rates. When the estimate exceeds a threshold, IEC declares congestion. IEC ends the congestion epoch when the delay on a control packet drops to within E of the minimum measured delay. In all other ways, IEC and Explicit Edge Control (EEC) are identical, as described above.  
         [0034]    Using IEC to detect the beginning of a congestion epoch, each virtual link signals congestion when its (contribution (“accumulation”), q i , to the queue length exceeds σ. When all N virtual links contribute an accumulation of σ, the total accumulation is Nσ which is the congestion epoch detection criterion used in the EEC method. The accumulation q i  can be calculated using the following observation: Assume a sufficiently large interval τ. If the average input rate during this period τ is λ i  and the average output rate is ν i , the accumulation caused by this flow during the period τ is (λ i −ν i )×τ. The accumulation measured during this period can be added to a running estimate of accumulation q i  which can then be compared against a maximum accumulation reference parameter. More accurately stated:  
                 q   i          (   t   )       =                q   i          (     t   -   τ     )       +       ∫     t   -   τ     t              λ   i          (   T   )               T         -       ∫     u   -   τ     u              υ   i          (   T   )               T                   (   2   )                            =         q   i          (     t   -   τ     )       +       (           λ   _     i          [       t   -   τ     ,   t     ]       -         υ   _     i          [       u   -   τ     ,   u     ]         )        τ                 (   3   )                               
  u=t +propagation delay  (4)  
         [0035]    The average interval for ν i  is delayed by the propagation delay so that any fluid entering the virtual link by the time t can leave by time u unless it is backlogged. As a result the computation of q i  excludes packets in the bandwidth-delay product, if the bandwidth-delay product is constant.  
         [0036]    The ingress node  202  sends two control packets in each interval T (but no faster than the real data rate). τ is the inter-departure time of control packets at the sender. In each control packet, the ingress inserts a timestamp and the measured average input rate (λ i ). The average output rate ν i  is measured over the time interval between arrivals of consecutive control packets at the egress  206 . The egress node  206  now has all the three quantities required to do the computation: (λ i −ν i )×τ and add it to a running estimate of accumulation. The running estimate of accumulation is also reset at the end of a congestion epoch to avoid propagation of measurement errors.  
         [0037]    One way of implementing the control packet flow required for this mechanism without adding extra traffic is for the ingress  202  to piggy-back rate and timestamp information in a shim header on two data packets in each interval T. Interior IP routers ignore the shim headers, while the egress  206  strips them out.  
         [0038]    The detection of the end of a congestion epoch, or in general an un-congested network is based upon samples of one-way delay. As each control packet arrives at the egress  202 , the egress  202  updates the minimum one-way delay seen so far. Every time a one-way delay sample is withinεof the minimum one-way delay, the egress  206  declares that the network is un-congested and stops sending negative feedback. Note that the minimum one-way delay captures the fixed components of delay such as transmission, propagation and processing (not queuing delays). The delay over and above this minimum one-way delay is a rough measure of queuing delays. Since low delay indicates lack of congestion, the method does not attempt to detect the beginning of a congestion epoch until a control packet has a delay greater thanεabove the minimum delay.  
         [0039]    Below are two illustrative applications for the edge-to-edge control of the present invention: distributed buffer management and an end-to-end low-loss best effort service.  
         [0040]    As already stated, edge-to-edge control can be used to distribute backlog across the edges, as illustrated in FIGS.  5 ( a ) and  5 ( b ). This increases the effective number of buffers allowing more TCP connections to obtain large enough windows to survive loss without timing out. This reduces TCP&#39;s bias against tiny flows and thus improves fairness. Using IEC to distribute the backlog dramatically reduces the coefficient of variation in goodput (“goodput” is defined herein as the number of transmitted payload bits excluding retransmissions per unit time) when many TCP connections compete for the bottleneck. As expected, this improvement increases as congestion is distributed across more edges.  
         [0041]    Edge-to-edge control can also be combined with Packeteer TCP rate control (TCPR) to provide a low-loss-end-to-end service for TCP connections. By “low-loss” it is meant that the method typically does not incur loss in the steady-state. Furthermore as with IEC alone, the combined IED +TCPR method does not require upgrading either end-systems or the interior network.  
         [0042]    In this combined method, IEC pushes the congestion to the edge and then TCP rate control pushes the congestion from the edge back to the source. To accomplish this method, the virtual link ascertains the available capacity at the bottleneck and provides this rate to the TCP rate controller. The TCP rate controller then converts the rate to the appropriate window size and stamps the window size in the receiver advertised window of acknowledge heading back to the source.  
         [0043]    Thus, both the Explicit Edge Control (EEC) and the Implicit Edge Control (IEC) methods can be deployed one class at a time improving performance as the number of edge controlled class increases. For example, deployment can be piggybacked with the roll-out of services or MPLS, since these techniques can work with either architecture. Both methods are transparent to end-systems, but require software components to be installed at the edges of the network. Such edge components can be installed as upgrades to routers or stand-alone units.  
         [0044]    Hence, the above described apparatus and method provide for an improved data network by elevating congestion at network bottlenecks.  
         [0045]    Although the invention has been described above in connection with exemplary embodiments, it is apparent that many modifications and substitutions can be made without departing from the spirit or scope of the invention. Accordingly, the invention is not to be considered as limited by the foregoing description, but is only limited by the scope of the appended claims.