Differentiated services IP quality of services round trip time aware intelligent traffic conditioner in an ingress node of virtual private networks

[0002] The present invention relates generally to traffic conditioners for use in networks. In particular, the present invention relates to differentiated services round trip time aware traffic conditioners for use in over provisioned networks.

[0003] In the traditional IP network model, all user packets compete equally for network resources, particularly bandwidth. The rise in usage and popularity of the Internet coupled with new applications relating to voice, video and the World Wide Web has fuelled research to improve the Quality of Service delivered by best-effort networks. The underlying concept in IP Quality of Service (IP-QoS) is the ability of network operators to offer differing levels of treatment to user traffic based on their requirements.

[0004] Differentiated Services (Diffserv) Traffic Conditioners [Blake, S. et al, “An Architecture for Differentiated Services”, RFC 2475, December 1998] use a scalable means to deliver IP-QoS based on the handling of traffic aggregates. Differentiated Services Traffic Conditioners operate on the premise that complicated functionality should be moved toward the edge of the network with very simple functionality at the core. Edge devices in this architecture are responsible for ensuring that individual user traffic conforms to traffic profiles specified by the network operator and for grouping flows in an aggregated fashion into a small number of classes. Core devices perform differentiated aggregate treatment of these classes based on the marking performed by the edge devices.

[0005] RIO-based [Clark D. and Fang W., “Explicit Allocation of Best Effort Packet Delivery Service”, ACM Transactions on Networking, August 1998] schemes for Traffic Conditioners employ a have been proposed as a simple means of providing Differentiated Services. The basis of the RIO mechanism is RED-based [Floyd, S., and Jacobson, V., “Random Early Detection gateways for Congestion Avoidance”, IEEE/ACM Transactions on Networking, V.1 N.4, August 1993, p. 397-413] differentiated dropping of packets during congestion at the router. In RIO, traffic profiles for end-users are maintained at the edge of the network. When user traffic exceeds the contracted target rate, their packets are marked out-of-profile. Otherwise, packets are marked in-profile. One known traffic conditioner used in this context marks packets “out” with probability: $p=\frac{\left(\mathrm{MeasuredRate}-\mathrm{TargetRate}\right)}{\mathrm{MeasuredRate}}$

[0006] Recent studies of RIO-based schemes [Nandy B, Seddigh N, Pieda P, “Diffserv's Assured Forwarding PHB: What Assurance does the Customer Have?”, Presented at NOSSDAV 99, Boston, June 1999][Seddigh, N., Nandy B., Pieda, P., “Bandwidth Assurance Issues for TCP flows in a Differentiated Services Network”, To be Presented at GLOCECOM 99, Rio de Janeiro, December 1999] indicate that in an over-provisioned network, target rates for all customers are achieved. However, excess bandwidth can be unfairly divided between equal-paying customers. This unfairness is caused by at least five different factors: Round Trip Time (RTT), packet size, size of target rate, number of microflows sharing target aggregate and presence of non-responsive flows. These same five factors also play a role in unfair degradation of service in under provisioned networks.

[0007] Thus, there is a need to mitigate the effect of the above five factors. The present invention is, in particular, directed to the need to mitigate the effect of RTT in dividing excess bandwidth among equal paying customers in an over provisioned network.

[0008] The present invention is directed to an RTT aware traffic conditioner (RTT-TC) for mitigating the effect of disparate RTTs in the distribution of excess bandwidth in over provisioned networks. The present invention is a traffic conditioner that accounts for varied RTTs on a network by marking lower RTT aggregates with a higher probability than higher RTT aggregates.

[0009] According to one aspect of the present invention, there is provided a traffic conditioner for use in a source edge device, i.e., an ingress node, in a carrier network. The carrier network includes: a plurality of virtual private networks, each virtual private network comprising a plurality of edge devices; and at least one core device for routing data between edge devices within the virtual private networks. Each plurality of edge devices includes: at least one source edge device; and at least one destination edge device, i.e., an egress node, associated with each source edge device. The carrier network also includes edge device communication means for determining the minimum aggregateRTT (minRTT) for the carrier network. The source edge device includes: means for estimating the rate of data flow (MeasuredRate) from the source edge device to each destination edge device associated therewith; means for estimating the round trip time (aggregateRTT) between the source edge device and each destination edge device associated therewith; and a memory element containing a predetermined target rate of data flow (TargetRate) between the source edge device and each destination edge device associated therewith. The traffic conditioner includes: in-marking means for marking a packet “in” if the MeasuredRate at the source edge device<=the TargetRate at the source edge device; and out-marking means for marking a packet “out” with probability of a function of ((MeasuredRate−TargetRate)/MeasuredRate)*((minRTT/aggregateRTT)²) if the MeasuredRate at the source edge device>the TargetRate at the source edge device.

[0010] According to a further aspect of the present invention, there is provided a carrier network including: at least one virtual private network, each virtual private network including a plurality of edge devices; and at least one core device for routing data between edge devices within a virtual private network. Each plurality of edge devices includes: at least one source edge device; and at least one destination edge device associated with each source edge device. Each source edge device includes: a bandwidth estimator for estimating the rate of data flow (MeasuredRate) from the source edge device to each destination edge device associated therewith; a round trip time estimator for estimating the round trip time (aggregateRTT) between the source edge device and each destination edge device associated therewith; and a memory element containing a predetermined target rate of data flow (TargetRate) between the source edge device and each destination edge device associated therewith. The carrier network also includes an edge device communication mechanism for determining the minimum aggregateRTT (minRTT) for the carrier network. The carrier network also includes a traffic conditioner at each source edge device. The traffic conditioner includes: an in-marker for marking a packet “in” if the MeasuredRate at the source edge device<=the TargetRate at the source edge device; and an out-marker for marking a packet “out” with probability of a function of ((MeasuredRate−TargetRate)/MeasuredRate)*((minRTT/aggregateRTT)²) if the MeasuredRate at the source edge device>the TargetRate at the source edge device.

[0011] According to a further aspect of the present invention, there is provided a virtual private network for use in a carrier network. The carrier network includes at least one core device for routing data between edge devices on the carrier network, and edge device communication means for determining the minimum aggregateRTT (minRTT) for the carrier network. The virtual private network includes: at least one source edge device; at least one destination edge device associated with each source edge device; means at each source edge device for estimating the rate of data flow (MeasuredRate) from the source edge device to each destination edge device associated therewith; means at each source edge device for estimating the round trip time (aggregateRTT) between the source edge device and each destination edge device associated therewith; a memory element at each source edge device containing a predetermined target rate of data flow (TargetRate) between the source edge device and each destination edge device associated therewith. A traffic conditioner at each source edge device includes: in-marking means for marking a packet “in” if the MeasuredRate at the source edge device<=the TargetRate at the source edge device; and out-marking means for marking a packet “out” with probability of a function of ((MeasuredRate−TargetRate)/MeasuredRate)*((minRTT/aggregateRTT)²) if the MeasuredRate at the source edge device>the TargetRate at the source edge device.

[0012] Other aspects and features of the present invention will become apparent to those ordinarily skilled in the art upon review of the following description of specific embodiments of the invention in conjunction with the accompanying figures.

[0013] Embodiments of the invention will now be described with reference to the accompanying drawings, in which:

[0014] FIG. 1 illustrates a carrier network embodying an RTT-TC in accordance with the present invention;

[0015] FIG. 2 is a block diagram of a source-destination pair in accordance with the present invention; and

[0016] FIG. 3 is a flowchart illustrating a method in accordance with the present invention.

[0017] FIG. 1 illustrates a carrier network. The carrier network includes two virtual private networks. Customer A's virtual private network includes edge devices #1, #9 and #10. Customer B's virtual private network includes edge devices #2, #3, #5 and #8. Edge devices #4, #6 and #7 are part of neither Customer A's nor Customer B's virtual private network. The carrier network includes three core devices C1, C2 and C3 for routing data between edge devices. In the illustrated embodiment, each edge device in each virtual private network is a source edge device, i.e., an ingress node. Each edge device in each virtual private network is also a destination edge device, i.e., an egress node. For example, the source-destination pairs in which edge device #3 is the source edge device are: #3 and #5; #3 and #8; #3 and #2. Thus, edge devices #5, #8 and #2 are the destination edge devices associated with source edge device #3.

[0018] With reference to FIGS. 2 and 3, each source edge device includes a bandwidth estimator for measuring the rate of data flow (MeasuredRate) from the source edge device to each destination edge device associated therewith. Each source edge device also includes a round trip time estimator for estimating the round trip time (aggregateRTT) between the source edge device and each destination edge device associated therewith. Each source edge device also includes a memory element containing a predetermined target rate of data flow (TargetRate) between the source edge device and each destination edge device associated therewith. The carrier network includes an edge device communication mechanism for determining the minimum aggregateRTT (minRTT) for the carrier network. At each source edge device is a traffic conditioner. Each traffic conditioner includes an in-marker for marking a packet “in” if the MeasuredRate at the source edge device<=the TargetRate at the source edge device. Each traffic conditioner also includes out-marker for marking a packet “out” with probability of a function of ((MeasuredRate−TargetRate)/MeasuredRate)*((minRTT/aggregateRTT)²) if the MeasuredRate at the source edge device>the TargetRate at the source edge device. In the preferred embodiment, the out-marker marks a packet “out” with probability of ((MeasuredRate−TargetRate)/MeasuredRate)*((minRTT/aggregateRTT)²) if the MeasuredRate at the source edge device>the TargetRate at the source edge device.

[0019] RTT-TCs embodying the present invention may be used to mitigate the effect of disparate RTTs in the distribution of excess bandwidth among equal paying customers in certain types of over provisioned networks. Carrier networks with cross-continental or international access points will find it easiest to utilize the RTT-TC. The key services offered by such carriers to its customers would be virtual private network (VPN) like services. In such a scheme, each customer would typically access no more than a handful of other nodes in its VPN; i.e., generally in the tens or hundreds.

[0020] The service contract between the customer and the carrier is that virtual connection between specific source-destination pairs will generally have a base target rate with soft guarantees. There will also be fair sharing of the excess bandwidth amongst all customers. “Fair” implies that factors such as RTT and packet size will not bias throughput for or against particular customers.

[0021] Thus, such a network can yield significant savings over traditional “leased line” services. End-customers can contract minimal bandwidth soft guarantees with knowledge that they will compete fairly for the excess bandwidth and pay a lower rate for that portion of the bandwidth.

[0022] FIG. 1 shows a network in which customer B has four sites and Customer A has three sites. Customer A has sites that are close together while customer B has sites that have varying transmission delays. The varying distances between the sites for Customer B will result in Customer A picking up a greater share of the excess bandwidth for nodes that are oversubscribed. This is due to the RTT impact on TCP's self-clocking mechanism.

[0023] The preferred embodiment of the present invention is applicable in the following situation.

[0024] End customers contract a service agreement with a carrier network. Each customer has multiple nodes on the carrier network. Each customer site accesses the carrier network via an access point.

[0025] Service contracts between the carrier and customer consist of soft guarantees for a particular target rate between a source access point and destination access point. There is further assurance for fair competition for excess bandwidth beyond the “soft guarantee”. This excess bandwidth is sold at a lesser cost.

[0026] The implication of source-destination contracts is that classification, policing and marking at the edge of the network will be on the source-destination pair for which a policy will exist locally.

[0027] Each access point has a means of tracking RTT from itself to all other access points in the network. This can either be calculated dynamically on the fly or pre-calculated and stored in a table. If there is concern that node delay can affect RTT results, then RTT must be calculated dynamically.

[0028] Across the network, there is a means of inter-accesspoint communication such that the maximum RTT (maxRTT) and minimum RTT (minRTT) in the network are determined. There is one maxRTT and one minRTT value for the whole carrier network.

[0029] At each access point, for each source-destination aggregate, the RTT is tracked to determine the aggregate RTT (aggregateRTT).

[0030] The following RTT-TC is applied:

[0031] If(measuredRate<=TargetRate)

[0032] Mark Packet “In”

[0033] Else

[0034] Mark Packet “Out” with probability: ${\left(\frac{\min \mathrm{RTT}}{\mathrm{aggregateRTT}}\right)}^2\times p$

[0035] where: $p=\frac{\left(\mathrm{MeasuredRate}-\mathrm{TargetRate}\right)}{\mathrm{MeasuredRate}}$

[0036] The above algorithm is also illustrated in FIG. 2.

[0037] The above algorithm (FIG. 2) assists in alleviating the effects of RTT in causing biassed sharing of excess bandwidth. However, this algorithm is the general case. In the preferred embodiment, exception cases are considered in order to make the algorithm more robust.

[0038] Exception cases include those where the ratio between maxRTT and minRTT is so large that flows with large RTT hardly have any packets marked out-of-profile due to a low probability calculation.

[0039] Exception cases also include a bound for minimum and maximum RTTs to make the approach more realistic.

[0040] In addition to determining the system minimum and maximum RTTs, the more robust algorithm requires configurable values for baseRTT and maxRTTRatio:baseRTT is the minimum desired RTT in the network, and maxRTTRatio is the largest RTT ratio desired in the network.

[0041] In accordance with the preferred embodiment, values of 20 msec and 10 for baseRTT and maxRTTRatio values respectively are used. 20 msec is chosen because of results from [Fei A, Pei G, Liu R and Zhang L, “Measurements on Delay and Hop-Count of the Internet”, Dept. of Computer Science, University of California]. In that paper, the authors study delays (RTT) in the Internet and show the histogram of RTTs observed. From their results, it can be gauged that there are not many RTTs below 20 msec on the Internet. 10 is chosen as the maxRTTRatio because the same paper showed that 95% of RTTs measured fell under 160 msec. 40 msec is added for buffer

[0042] There are six different scenarios that the robust algorithm of the preferred embodiment seeks to address. The six scenarios are described below in the context of the robust algorithm. In implementation, the six scenarios can be reduced to four conditions for efficiency. However, in the description of the algorithm, all six scenarios are listed and described separately below.

[0043] Scenario 1 is the case where the ratio of maxRTT and minRTT is less than maxRTTRatio. This is the regular condition. In this case, packet marking is carried out in accordance with the general case algorithm (FIG. 2). If the ratio of maxRTT to minRTT is greater than maxRTTRatio then packets will be treated according to one of the following five cases. For Scenario 1, the robust algorithm is as follows:

[0044] /* Mark packet “Out” with probability */

[0045] X=maxRTTRatio

[0046] /* Regular Case */

[0047] if ((if maxRTT/minRTT)<X)

[0048] mark packet out with probability (minRTT/aggregateRTT)²*X

[0049] Scenario 2 is the case where both minRTT and maxRTT are below baseRTT. In this case, transmission delays across the network are not very large. In order to bound the minRTT:maxRTT ratio, a pseudo minRTT is calculated with value maxRTT/X. All aggregateRTTs with values less than the newMinRTT have their aggregateRTT set to the value of newMinRTT. Packets are marked out of profile in accordance with the general case algorithm (FIG. 2) except that newMinRTT is substituted instead of minRTT. For Scenario 2, the robust algorithm is as follows:

[0050] /* Special Case—If both min and max RTT are below baseRTT */

[0051] Else if ((minRTT<baseRTT) and (maxRTT<baseRTT))

[0052] NewMinRTT=maxRTT/X

[0053] If (aggregateRTT<newMinRTT) then aggregateRTT=newMinRTT

[0054] Mark packet “out” with probability (NewMinRTT/aggregateRTT)²*p

[0055] Scenario 3 is the case both minRTT and maxRTT are above baseRTT*X. In this case, transmission delays in the network are large. In this case, it is the maxRTT that needs to be bounded. Thus, a new pseudo maxRTT (newMaxRTT) is set to have the value of minRTT*X. All aggregateRTT values above newMaxRTT are reset to newMaxRTT. Packets are marked out of profile in accordance with the general case algorithm (FIG. 3). For Scenario 3, the robust algorithm is as follows:

[0056] /* Special Case—if both min and max RTT are above baseRTT*X */

[0057] Else if ((minRTT>baseRTT*X) and (maxRTT>baseRTT*X))

[0058] NewMaxRTT=minRTT*X

[0059] If (aggregateRTT>newMaxRTT) then aggregateRTT=newMaxRTT

[0060] Mark packet “out” with probability (minRTT/aggregateRTT)²*p

[0061] Scenario 4 is the case where minRTT is less than the baseRTT and maxRTT is greater than baseRTT*X. This a network with widely varying RTTs. Both the min and max RTT need to be bounded, newMinRTT is set to baseRTT, newMaxRTT is set to newMinRTT*X. All aggregateRTT values above maxRTT are set to newMaxRTT while all aggregateRTT values below minRTT are set to minRTT. Packets are marked out of profile in accordance with the general case algorithm (FIG. 2) except that newMinRTT is substituted instead of minRTT. For Scenario 4, the robust algorithm is as follows:

[0062] /* Special Case—min less than base RTT and max greater than base*X */

[0063] Else if ((minRTT<baseRTT) and (maxRTT>(baseRTT*X)))then

[0064] NewMinRTT=baseRTT

[0065] NewMaxRTT=baseRTT*X

[0066] If (aggregateRTT>newMaxRTT) then aggregateRTT=newMaxRTT

[0067] If (aggregateRTT<newMinRTT) then aggregateRTT=newMinRTT

[0068] Mark packet “out” with probability (newMinRTT/aggregateRTT)²*p

[0069] Scenario 5 is the case where minRTT is less than the baseRTT. At the same time, maxRTT is less than baseRTT*X but greater than baseRTT. In this case, it is the minRTT that needs to be bounded. Thus, newMinRTT is set to maxRTT/X. All aggregate RTTs less than newMinRTT are set to have values of newMinRTT. Packets are marked out of profile in accordance with the general case algorithm (FIG. 2) except that newMinRTT is substituted instead of minRTT. For Scenario 5, the robust algorithm is as follows:

[0070] /* Special Case */

[0071] Else if ((minRTT<baseRTT) and (maxRTT<(baseRTT*X)) then

[0072] NewMinRTT—maxRTT/X

[0073] If (aggregateRTT<newMinRTT) then aggregateRTT=newMinRTT

[0074] Mark packet “out” with probability (newMinRTT/aggregateRTT)²*p

[0075] Scenario 6 is the case where minRTT is greater than baseRTT and less than baseRTT*X. At the same time, maxRTT is greater than baseRTT*X. In this case it is maxRTT that needs to be bounded. As such, newMaxRTT is set to minRTT*X. All aggregateRTT values greater than newMaxRTT are set to the value newMaxRTT. Packets are marked out of profile in accordance with the general case algorithm (FIG. 2). For Scenario 6, the robust algorithm is as follows:

[0076] /* Special Case */

[0077] Else if ((minRTT>baseRTT) and (maxRTT>(baseRTT*X))) then

[0078] NewMaxRTT=minRTT*X

[0079] If (aggregateRTT>newMaxRTT) then aggregateRTT=newMaxRTT

[0080] Mark packet “out” with probability (minRTT/aggregateRTT)²*p

[0081] Scrutinizing the six scenarios more closely, one observes that scenarios 3 and 6 are treated in the same manner while scenarios 2 and 5 are also treated in the same way. Thus, the total number of cases is reduced to four. The conditions for the four cases are summarized below:

[0082] if ((maxRTT/minRTT)<X)

[0083] [Mark packet out with probability (minRTT/aggregateRTT)²*X]

[0084] Else if ((minRTT<baseRTT) and (maxRTT>(baseRTT*X)))

[0085] [NewMinRTT=baseRTT

[0086] NewMaxRTT=baseRTT*X

[0087] If (aggregateRTT>newMaxRTT) then aggregateRTT=newMaxRTT

[0088] If (aggregateRTT<newMinRTT) then aggregateRTT=newMinRTT

[0089] Mark packet “out” with probability (newMinRTT/aggregateRTT)²*p]

[0090] Else if (minRTT<baseRTT)

[0091] [NewMinRTT=maxRTT/X

[0092] If (aggregateRTT<newMinRTT) then aggregateRTT=newMinRTT

[0093] Mark packet “out” with probability (NewMinRTT/aggregateRTT)²*p]

[0094] Else if (maxRTT>(baseRTT*X))

[0095] [NewMaxRTT=minRTT*X

[0096] If (aggregateRTT>newMaxRTT) then aggregateRTT—newMaxRTT

[0097] Mark packet “out” with probability (minRTT/aggregateRTT)²*p

[0098] The actions based on the above four conditions remain the same as outlined in the previous section.

[0099] The present invention does not address issues associated with different RTTs for microflows within an aggregate and ensuring fairness for such microflows. In the context of the present invention, it is assumed that between any source-destination pair, all microflows within the aggregate will have more or less the same RTT. The present invention does not take into account RTT variation within the customer premises. It is assumed that delay times within a customer's end network is minimal relative to the transmission delay of the Wide Area Network (WAN).

[0100] While the present invention has been described in connection with what is presently considered to be the most practical and preferred embodiments, it is to be understood that the invention is not limited to the disclosed embodiments. To the contrary, the present invention is intended to cover various modifications, variations, adaptations and equivalent arrangements included within the spirit and the scope of the appended claims. The scope of the claims is to be accorded the broadest interpretation so as to encompass all such modifications and equivalent structures and functions.