Electrical computers and digital processing systems: multicomput – Computer-to-computer data routing – Prioritized data routing
Reexamination Certificate
1999-09-08
2002-11-12
Luu, Le Hien (Department: 2152)
Electrical computers and digital processing systems: multicomput
Computer-to-computer data routing
Prioritized data routing
C709S242000
Reexamination Certificate
active
06480899
ABSTRACT:
FIELD OF THE INVENTION
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.
BACKGROUND OF THE INVENTION
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.
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.
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
=
(
MeasuredRate
-
TargetRate
)
MeasuredRate
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.
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.
SUMMARY OF THE INVENTION
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.
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)
2
) if the MeasuredRate at the source edge device>the TargetRate at the source edge device.
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)
2
) if the MeasuredRate at the source edge device>the TargetRate at the source edge device.
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 associ
Nandy Biswajit B.
Pieda Peter S.
Seddigh Nabil N.
Luu Le Hien
Nortel Networks Limited
LandOfFree
Differentiated services IP quality of services round trip... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Differentiated services IP quality of services round trip..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Differentiated services IP quality of services round trip... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2932568