Dynamic weighted resource sharing

Details Dynamic weighted resource sharing Dynamic weighted resource sharing

1999-09-24

2004-08-10

Ton, Dang (Department: 2666)

Multiplex communications

Data flow congestion prevention or control

Control of data admission to the network

C370S232000, C370S235000, C370S395410, C370S412000, C370S429000

Reexamination Certificate

active

06775231

ABSTRACT:

BACKGROUND OF THE INVENTION
The present invention relates to data networking and more particularly to providing differentiated services on an Internet Protocol network such as the Internet.
In order to accommodate a mix of traffic that it will include voice, video, and electronic commerce data, it is envisioned that the Internet will require a scalable architecture for service differentiation. An overall architecture for differentiated services on the Internet is described in Blake,
An Architecture for Differentiated Services,
IETF RFC 2475 (December 1998), the contents of which are herein incorporated by reference. In a differentiated service model, packets forwarded via a network belong to one of a plurality of behavior aggregates. Each packet may include a DS (Differentiated Services) field identifying the aggregate to which the packet belongs.
Traffic entering a network which operates according to a differentiated service model, e.g., a Differentiated Services domain, is classified, possibly conditioned, and assigned to one of the behavior aggregates. Each behavior aggregate defines a per hop forwarding behavior to be implemented at nodes internal to the Differentiated Services domain. The Differentiated Services model achieves scalability by implementing complex classification and conditioning function only at the network boundary nodes. Core nodes apply per hop behaviors to aggregates of traffic which have been appropriately marked using the DS field in the packet headers. The term “per hop behavior” refers to the externally observable forwarding behavior of a node in a Differential Services domain.
An important example of a differentiated service is Assured Forwarding Service. Assured Forwarding is described in Heinanen et al.,
Assured Forwarding PHB Group,
IETF RFC 2597 (June 1999), the contents of which are herein incorporated by reference. In the context of a service provider operating a network providing interconnections among various customer networks, Assured Forwarding provides different levels of delivery assurances for IP packets received from customer networks. Four Assured Forwarding classes representing different levels of delivery assurance are defined. Each IP packet employing Assured Forwarding is assigned to one of these Assured Forwarding classes.
To support a Differential Services model such as Assured Forwarding, a network node internal to the service provider network must operate packet schedulers for each of its output interfaces to ensure that each class to be output via the interface receives service corresponding to its defined per hop behavior. It is known to support prioritization among different traffic sources or different classes by using queuing techniques such as Weighted Fair Queuing (WFQ), or Weighted Round-Robin (WRR) queuing. These techniques involve dividing traffic among multiple queues and allocating limited packet forwarding bandwidth among the queues according to weights assigned to each queue.
The difficulty that arises in using either Weighted Fair Queuing or Weighted Round-Robin to support the per hop behaviors required for different Assured Forwarding classes is assigning weights to the different classes. The actual priority levels experienced by different classes at a node will depend on both the weights assigned to those classes and the traffic loads for those classes. The load of each Assured Forwarding class changes over time as flows are created and torn down. However, the prior art Weighted Fair Queuing and Weighted Round-Robin techniques use weights that do not change over time.
If each Assured Forwarding class keeps the same weight as its traffic load varies, relative priority levels may also vary thereby violating the requirements of the IETF specification. For example, Assured Forwarding requires that packets of a class, i, must be forwarded in a more timely fashion than packets of a class, j, when i>j. However, if the weights assigned to class i and class j both stay constant as class i experiences significant increases in traffic load while class j traffic load remains constant, then packets of class i may start experiencing significantly more average delay than packets of class j, contradicting the IETF specification.
Furthermore, statically partitioning link resources among Assured Forwarding classes can result in low resource utilization. If current traffic completely consumes resources statically allocated to a particular class, packet flow may be blocked even though resources statically allocated to other classes are available.
It should also be noted that current specifications do not provide explicit signaling for flow connections and tear down. Therefore, not only will traffic vary among classes at interior nodes but interior nodes will be given no information generally characterizing the traffic distribution. Any scheme to explicitly communicate changes in traffic distribution to interior nodes would not scale with increased numbers of such nodes.
SUMMARY OF THE INVENTION
A packet scheduling technique that supports multiple classes of service is provided by virtue of the present invention. In one embodiment, the technique dynamically adjusts resource allocations for each traffic class based on actual traffic load measured for each service class. In this way, the per hop behavior required of each class by a differentiated service model may be achieved. Core nodes of a network operating according to a differentiated service model dynamically adjust resource allocations for multiple traffic classes without explicit signaling from other network nodes. Policies for sharing resources among multiple service classes can be enforced.
According to one aspect of the present invention, a method is provided for allocating network resources to a plurality of data communication service classes. The method includes measuring packet flow characteristics at a packet forwarding device for each of the plurality of service classes, determining resource allocation weights for each of the plurality of service classes based on the measured packet flow characteristics, and allocating a shared packet forwarding resource among the plurality of service classes according to the weights.


REFERENCES:
patent: 5872769 (1999-02-01), Caldara et al.
patent: 5978356 (1999-11-01), Elwalid et al.
patent: 6304549 (2001-10-01), Srinivasan et al.
patent: 6341134 (2002-01-01), Toutain et al.
patent: 6377583 (2002-04-01), Lyles et al.
patent: 6408005 (2002-06-01), Fan et al.
patent: 6434624 (2002-08-01), Gai et al.
patent: 6504819 (2003-01-01), Fowler et al.
Nichols et al., “Definition of the differential service field (DS Field) in the Ipv4 and Ipv6 headers”, 1998, IEFT RFC 2474.
Jacobson et al., “An expedited forwarding PHB”, 1999, IEFT RFC 2598.
Blake et al., “An architecture for differential services”, 1998, IETF RFC 2475.
Heinanen et al., “Assured forwarding PHB group”, 1999, IETF RFC 2597.
Craig Partridge, “Gigabit networking”, 1994, Addison Wesley Longman, pp. 276-280.

Affiliated with

Also associated with

Rating

Dynamic weighted resource sharing does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Dynamic weighted resource sharing, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Dynamic weighted resource sharing will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3348550