Multiplex communications – Data flow congestion prevention or control
Reexamination Certificate
2000-03-07
2004-04-20
Vanderpuye, Kenneth (Department: 2732)
Multiplex communications
Data flow congestion prevention or control
C370S237000
Reexamination Certificate
active
06724722
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to schemes for managing traffic flow in an information network.
2. Discussion of the Known Art
Recently, network traffic management has become an important subject. For example, dramatic increases in backbone network speeds require precise control over internal network traffic distribution. Yet, Internet Protocol (IP) traffic routing is based typically only on a destination address, and on simple metrics such as hop-count or delay. See C. Huitema, Routing in the Internet, Prentice Hall (1995). Although the simplicity of this routing approach is scalable to very large networks, use of resources within Internet backbone networks currently tends not to be optimal. A destination-based, shortest-path routing approach often results in uneven traffic distribution and, sometimes, in route oscillations.
Recent developments, such as Differentiated Services, Multi-Protocol Label Switching (MPLS), and Virtual Private Networks (VPNs), necessitate greater traffic engineering capabilities in Internet backbones. Under the differentiated services model, data packets are policed on a network edge, and forwarded based on only a DS field within the core. See S. Blake, et al., An Architecture for Differentiated Services, RFC-2475, IETF (December 1998). This approach relies heavily on effective traffic management to provide such resource allocations as needed to meet an existing service level agreement (SLA). Users are now considering IP VPNs for interconnection between different intranet user sites, and traffic must be handled to meet performance guarantees for virtual leased lines.
Multi-Protocol Label Switching (MPLS), recently developed by the Internet Engineering Task Force (IETF), provides essential capabilities for explicit routing in the Internet. See A. Viswanathan, et al., Evolution of Multiprotocol Label Switching, IEEE Communications, May 1998, all relevant portions of which are incorporated by reference. MPLS label distribution protocols can be used to set up explicit routes that differ from those provided by typical destination-based routing procedures. An originator of an explicit route can compute, based on optimization objectives, some or all nodes that will form the explicit route. Within an IP layer in a network, a MPLS explicit route is simply a point-to-point logical connection. Any packets sent onto a MPLS explicit route will travel to the other end of the route. Forwarding of packets over an explicit route is based on the MPLS labels, thus requiring no IP layer processing.
There are currently two protocols in MPLS for establishing label-switched paths (LSPs), and both of them support explicit routes. In addition, the MPLS label distribution protocols also permit Quality of Service (QoS) attributes to be specified. Thus, MPLS label distribution protocols can be used to set up a virtual private network (VPN) with explicit routes and bandwidth guarantees.
Although the MPLS explicit route approach has great flexibility, it requires a full-mesh logical network to be established between all edge nodes. While this is feasible for most reasonable size backbone networks, management complexity and messaging overheads can rise substantially when the number of edge nodes increases.
Topological routing problems have been considered along with assignments of link capacity (network sizing) for optimization of network resources. See T. Ng, et al., Joint Optimization of Capacity and Flow Assignment, IEEE Transactions on Communications, COM-35:202-209 (1987); M. Gerla, et al., Topology Design & Bandwidth Allocation in ATM Networks, IEEE Journal on Selected Areas in Communication, 7:1253-1262 (1989); and M. Lee, et al., A Logical Topology & Discrete Capacity Assignment Algorithm, Operations Research, 43:102-116 (1995).
A conventional approach is to choose average packet delay as a minimization objective, which results in a nonlinear objective function under some queuing assumptions. The optimization problem is then formulated as a nonlinear multi-commodity network flow problem. See D. Bertsekas, et al., Data Networks, Prentice Hall (1987). Because of the nonlinear objective function, the optimization problem becomes very difficult to solve. Many heuristic approaches have been proposed, such as a flow deviation method and a proximal decomposition method. See L. Fratta, et al., The Flow Deviation Method, Networks, 3:97-133 (1973); and J. Chiffet, et al., Proximal Decomposition for Multicommodity Flow Problems, Telecommunications Systems, 3:1-10 (1994).
A rerouting heuristic algorithm is proposed in L. Benmohamed, et al., Designing IP Networks, Bell Labs Technical Journal (December 1998) for a classical network loading problem (linear objective function) with cost minimization in the context of IP networks, which explicitly considers restrictions imposed by the known Open Shortest Path First (OSPF) routing protocol. Another related area is Quality of Service (QoS) routing. Schemes have been proposed to find a path under multiple constraints. See Z. Wang, et al., Quality of Service Routing For Supporting Multimedia Communications, IEEE JSAC (September 1996); Q. Ma, et al., Routing Traffic with QoS Guarantees, NOSSDAV'98 (UK 1998); and R. Guerin, et al., QoS based routing in networks, Infocom'97 (1997). The proposed QoS routing schemes are typically “greedy”, however, in that they try to find a path that meets a particular request without considering potential network-wide impacts.
Because of the commercial and competitive nature of Internet services, ISPs must always improve the perceived quality of network services by reducing delay and packet losses, and by increasing throughput experienced by end users. ISPs must meet their performance objectives and, at the same time, maintain a high level of resource utilization to maximize return of their investment in network assets.
SUMMARY OF THE INVENTION
According to the invention, a method of managing traffic flow across links of an information network includes monitoring traffic demands from a source node of an information network to a destination node of the network, including bandwidths associated with each of the traffic demands, and determining, for each traffic demand, and for a given link of the network, that portion of the bandwidth associated with each traffic demand which portion is provided by the given link. A maximum value of link utilization among all links of the network is determined, wherein link utilization is defined as the amount of bandwidth used by all traffic demands routed through a given link with respect to a total capacity of the link. The traffic demands are routed across the links of the network in such a manner as to minimize the maximum value of link utilization.
For a better understanding of the invention, reference is made to the following description taken in conjunction with he accompanying drawing and the appended claims.
REFERENCES:
patent: 5953338 (1999-09-01), Ma et al.
patent: 6202094 (2001-03-01), Grosser, Jr. et al.
R. Guerin, et al, QoS-based Routing in Networks with Inaccurate Information: Theory & Algorithms, Infocom'97 (1997).
A. Wang, et al, Quality of Service Routing for Supporting Multimedia Applications, IEEE JSAC (Sep. 1996).
Wang Yufei
Wang Zheng
Zhang Leah
LandOfFree
Managing congestion and potential traffic growth in an... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Managing congestion and potential traffic growth in an..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Managing congestion and potential traffic growth in an... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3199915