Network resource allocation methods and systems

Details Network resource allocation methods and systems Network resource allocation methods and systems

2001-07-31

2004-08-31

Courtenay, III, St. John (Department: 2126)

Electrical computers and digital processing systems: multicomput

Computer-to-computer data routing

Least weight routing

C370S230100, C370S401000

Reexamination Certificate

active

06785737

ABSTRACT:

FIELD OF THE INVENTION
The invention relates to network resource allocation methods and systems, and more particularly to methods and systems of allocating resources to low priority traffic, such as best effort traffic.
BACKGROUND OF THE INVENTION
In current IP (Internet Protocol) networks, packet forwarding is based on connectionless and destination-based SPF (Shortest Path First) routing mechanisms and also in the best effort manner. As a result of this, some links can be heavily utilized and congested while others remain idle, resulting in non-optimal use of network wide resources and poor packet performance. As a remedy to this problem, the explicit routing capability of MPLS (Multi Protocol Label Switching) is being employed to redirect traffic toward under-utilized parts of the network [1, 2]. Such a practice is generally termed “traffic engineering.”
Different levels of QoS (Quality of Service) can also be supported by MPLS explicit LSP (Label Switched Path) setup coupled with constraint based routing protocols (e.g., OSPF-TE (Open Shortest Path First—Traffic Engineering) or ISIS-TE (Intermediate System to Intermediate System Routing exchange Protocol—Traffic Engineering). In such mechanisms, the bandwidth for a certain service class is explicitly reserved along the path, and the link usage information is updated for CAC (Connection Admission Control) purpose. However, in general, BE (Best Effort) class traffic is not associated with any bandwidth reservation, i.e., CIR (Committed Information Rate)=0, hence no performance guarantee.
ECMP (Equal Cost Multi-Path) routing [1] allows flow (e.g., packets with same source and destination IP addresses) or packet level load balancing, but this does not employ the concept of explicit routing.
Typically, explicit routing is a three step process. First, a topology database is maintained which identifies network topology, typically by identifying nodes and links between nodes. IGP (Internal Gateway Protocol) for example, provides such network topologies. A scalar metric or metrics is associated with each link, for example in accordance with OSPF-TE. Then, signalling is employed in the network to reserve resources between a source and a destination, for example employing the RSVP-TE (Resource ReSerVation Protocol—Traffic Engineering) protocol. After resources have been successfully reserved, label distribution is performed to set up the actual label switched paths between the source and destination.
SUMMARY OF THE INVENTION
This invention provides a novel mechanism to ensure both the improved use of network resources and adequate performance of best effort (BE) traffic by intelligently distributing the BE traffic demands at connection level with corresponding scaling weights, and without reserving bandwidth.
A weighted sum of the best effort (BE) class connections (or LSPs in MPLS context) in a link is used as a path selection criterion, where each BE connection is weighted by its service volume (for example 10 Mbps may be assigned an integer value of 10, while 10 Gbps is to 10,000).
Preferably, the traffic engineering extension of IGP (Internal Gateway Protocol) such as OSPF-TE is adapted to advertise the weighted sum of BE connections as one of the link constraints, and a CBR (Constraint Based Routing) algorithm will select a path with the lowest utilization level.
A motivation of embodiments of the invention is to ensure that even the BE class connections can get adequate level of performance by (1) incorporating usage information of BE traffic as part of the traffic engineering extension IGP such as OSPF-TE, and by (2) using such information in calculating paths for BE connections with different service volume. An improved use of network resources is also achieved.
According to one broad aspect, the invention provides a network path selection method involving maintaining a network topology model comprising a plurality of nodes and a plurality of links interconnecting the nodes, the network topology further comprising a weighted BE (best effort) connection metric for each of the plurality of links; to determine a path from a source to a destination having a requested BE service volume: creating a virtual topology in which all links have weighted BE metrics updated to include the effects of the requested BE service volume, and identifying a best path through the virtual topology taking into account the weighted BE metrics.
In one embodiment the weighted BE connection metric takes into account only BE connection service volume. In other embodiments, the weighted BE connection metric for a given link takes into account BE connection service volume on the given link, and a remaining capacity on the given link taking into account other traffic classes with bandwidth commitment.
Preferably, a fraction of each link's capacity to be made available for BE traffic is set aside.
Preferably, the weighted BE connection metrics are computed in a manner which encourages making use of at least a portion of unused bandwidth which is reserved for other traffic classes.
The path selection process may also take into account one or more of administrative costs, edge disjointness, node disjointness, and shared risk link group disjointness for protection/restoration paths.
Preferably, the weighted BE connection metric within a network is advertised as part of a modified OSPF-TE (Open Shortest Path First—Traffic Engineering) link state advertisement.
Another broad aspect of the invention provides a network component adapted to perform path selection. The component has a network topology repository identifying a network topology comprising a plurality of nodes and a plurality of links interconnecting the nodes, the network topology further comprising a weighted BE (best effort) connection metric for each of the plurality of links. There is also a network path selecting component adapted to determine a path from a source to a destination having a requested BE service volume by: a) creating a virtual topology in which all links in the network topology have weighted BE metrics updated to include the effects of the requested BE service volume; and b) identifying a best path through the virtual topology taking into account the weighted BE metrics.
Another broad aspect of the invention provides a network component comprising means for computing a weighted BE connection metric for a link and means for advertising the weighted BE connection metric within a network.


REFERENCES:
patent: 6647428 (2003-11-01), Bannai et al.
patent: 6661775 (2003-12-01), Nakayama et al.
patent: 6680948 (2004-01-01), Majd et al.
“Requirements for Traffic Engineering Over MPLS”, Awduche, et al., RFC 2702, Sep. 1999, pp. 1 to 29.
“Requirements for support of Diff-Serv-aware MPLS Traffic Engineering”, Francois Le Faucheur, et al., IETF Internet Draft, Jan., 2001, pp. 1 to 9.
“Assured Forwarding PHB Group”, Heinanen, RFC 2597, Jun. 1999, pp. 1 to 11.
“An Expedited Forwarding PHB”, Jacobson, et al., RFC 2598, Jun. 1999, pp. 1 to 11.
“The n-Dimensional Superswitch”, Josh McHugh, Wired May 2001.

Affiliated with

Also associated with

Rating

Network resource allocation methods and systems does not yet have a rating. At this time, there are no reviews or comments for this patent.

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

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3343687