CN103081416B - Automated Traffic Engineering of Multiprotocol Label Switching (MPLS) with Link Utilization as Feedback into Tie-Breaking Mechanisms - Google Patents

Abstract

A method implemented in a node of a multiprotocol label switching (MPLS) network for improved load distribution, the method comprising determining a first set of one or more shortest paths between each MPLS node pair, selecting at least a first shortest path by applying a common algorithm tie-breaking process, calculating a link utilization value for each link of the MPLS network, determining a second set of one or more shortest paths between each MPLS node pair, generating a path utilization value for each shortest path in the second set of shortest paths based on the link utilization value corresponding to each shortest path, and selecting a second shortest path from the second set of shortest paths based on the path utilization values, whereby the selection of the second shortest path in view of path utilization minimizes a standard deviation of load distribution across the entire MPLS network.

Description

Multiprotocol Label Switching with Link Utilization as Feedback into Tie-Breaking Mechanisms (MPLS) automation business engineering

Related Application Cross Reference

This application is cross-referenced to co-pending patent application "802.1AQ Based Automated Traffic Engineering Using Link Utilization as Feedback into a Tie Breaking Mechanism" by David Ian Allen and Scott Andrew Mansfield filed on the same date as this application and jointly owned (AUTOMATED TRAFFIC ENGINEERING FOR 802.1AQ BASED UPON THE USE OF LINK UTILIZATION AS FEEDBACK INTO THE TIE BREAKING MECHANISM). The cross-referenced applications are hereby incorporated by reference.

technical field

Embodiments of the invention relate to methods and devices for improving load distribution in a network. In particular, embodiments of the invention relate to methods for load distribution in a network with multiple equal cost paths between nodes in a Multiprotocol Label Switching (MPLS) network.

Background technique

Load distribution or load distribution is a method of using bandwidth more efficiently and improving overall performance in a network. Most of the automated load distribution and load distribution techniques deployed today operate only with a very local view, taking into account only the path or number of subsequent hops to a given destination, and do not take into account the overall volume of traffic in the network distribution.

Equal-cost multipath (ECMP) is a common strategy for load distribution of unicast traffic in a routed network, where a decision about how to forward a packet to a given destination can resolve to multiple "equal-cost" paths (which is exploited in the case of a tie on the shortest path when running a database calculation). ECMP is capable of combining most unicast routing protocols with supporting data plane hardware nodes to use. By using ECMP at any given node in the network, the load is pseudo-equally divided across a set of equal-cost subsequent hops. This process is accomplished independently at each hop of the network where there is more than one path to a given destination.

In many implementations, each packet is checked against an entropy source such as an Internet Protocol (IP) header when there are multiple equal-cost subsequent hops, and a hash of the header information modulo the number of paths is used for a specific The group selects the next hop. For highly aggregated businesses, this approach will evenly distribute the load evenly in regular topologies (i.e., symmetric topologies), and does provide some improvement in less regular topologies.

Multiprotocol Label Switching (MPLS) is a combination of data plane and control plane technologies used to forward traffic over a network. MPLS uses per-hop labels assigned to traffic flows to forward traffic across the network using standard lookups and translations (called "switches"). Each node of the network supports MPLS by examining incoming traffic received through the network and forwarding that traffic based on its label, which is typically switched or "switched" at each hop.

MPLS networks can improve the distribution of routed traffic in the network using per-hop ECMP to distribute or distribute load across equal cost paths. In an MPLS network, a Label Switched Path (LSP) to each next hop is set up by each node in the network for each equal cost path. Each node in the network computes the forwarding path for a given destination in the network using the Shortest Path First (SPF) algorithm, maps it to local label bindings in the node, and the resulting connectivity is shown as multipoint-to-many point grid. When presented with traffic destined for multiple equal cost paths, each node utilizes the payload information as part of the path selection mechanism in order to maximize the uniformity of flow distribution across the set of paths. The establishment of a multipoint-to-multipoint LSP is automatic.

The Label Distribution Protocol (LDP) or similar protocol is used to provide a complete set of label bindings for all possible forwarding equivalence class excesses in the network, and then each Label Switching Router (LSR) independently computes the following for each forwarding equivalence class A collection of hops and selects which label binding it will actually use at any given moment.

Contents of the invention

A method for improved load distribution implemented in a node of a Multiprotocol Label Switching (MPLS) network, wherein said node is one of a plurality of nodes in the MPLS network, each node implementing a common algorithmic tie-breaking process to Generate the lowest cost shortest path tree, the node includes a topology database to store the topology of the MPLS network, wherein the topology of the MPLS network includes a plurality of nodes and links between the nodes, the method comprises the following steps: by analyzing the MPLS stored in the topology database The topology of the network executes a shortest path search algorithm to determine a first set of one or more shortest paths between each pair of MPLS nodes in the MPLS network; by applying a common algorithm tie-breaking process, from said first set of shortest paths selecting at least a first shortest path for each MPLS node pair; calculating a link utilization value for each link of the MPLS network based on a count of the selected shortest paths through each link; The topology of the MPLS network executes a shortest path search algorithm to determine a second set of one or more shortest paths between each pair of MPLS nodes in the MPLS network; based on the link utilization value corresponding to each shortest path, one or more Each shortest path in the second set of shortest paths generates a path utilization value; the second shortest path is selected from a second set of one or more shortest paths on the basis of the path utilization value, wherein, among one or more When there are multiple shortest paths with equal path utilization values in the set of shortest paths, selecting a tie-breaking process using a common algorithm; and storing at least the first shortest path and the second shortest path for each MPLS node pair in the label information database. The shortest path, wherein the label information database indicates where to forward traffic entering the MPLS node, whereby selection of the second subset in view of path utilization minimizes a standard deviation of load distribution across the entire MPLS network.

A network element for improving load distribution in a multiprotocol label switching (MPLS) network, the MPLS network comprising a network element, wherein the network element is one of a plurality of nodes in the MPLS network, wherein the topology of the MPLS network includes multiple A node and the link between the nodes, the network unit includes: a topology database, storing link information for each link in the MPLS network; a label information database, storing label information for each port of the network unit, wherein, The label information database indicates where each forwarding equivalence class (FEC) entering the network element is forwarded; the control processor is coupled to the topology database and the label information database, and the network processor is configured to process data traffic, wherein the network processor Including: MPLS management module, configured to forward data services through label switching path (LSP); label distribution protocol (LDP) module, configured to establish LSP in MPLS network; shortest path search module, configured to perform shortest path through topology database A search algorithm to determine at least one shortest path between each pair of MPLS nodes in the MPLS network, wherein the shortest path search module is configured to assign equal-cost shortest paths to each pair of MPLS nodes with a plurality of equal-cost shortest paths sent to the load distribution module; a ranking module configured to rank each of the plurality of equal-cost shortest paths based on path utilization values derived from link utilization values associated with each of the plurality of equal-cost shortest paths and a load distribution module configured to select a first subset of a plurality of equal-cost shortest paths for the MPLS node pair from a plurality of received equal-cost shortest paths, the first subset to be used between the MPLS node pair sharing the data traffic load between the nodes, and based on the path utilization value, selecting from a plurality of equal-cost shortest paths for the MPLS node pair a second subset to be used for sharing the data traffic load with the first subset of the Ethernet bridge pair , whereby the selection of the second subset of values given the path utilization minimizes the standard deviation of the load distribution across the entire MPLS network.

Description of drawings

The present invention is shown by way of example and not limitation in the figures of the drawings, in which like reference numerals indicate like elements. It should be noted that different references to "an" or "an" embodiment in this disclosure are not necessarily to the same embodiment, and such references mean at least one. Furthermore, when a particular feature, structure or characteristic is described in conjunction with one embodiment, it is considered within the knowledge of those skilled in the art to implement such feature, structure or characteristic in combination with other embodiments whether explicitly described or not.

FIG. 1 is a diagram of an example of a network topology.

Figure 2 is a diagram of one embodiment of a network element implementing automatic traffic engineering for a multiprotocol label switching network (MPLS).

Figure 3 is a flow diagram of one embodiment of a load distribution process including automated traffic engineering involving the use of link utilization as feedback into a tie-breaking mechanism.

Figure 4 is a flowchart of one embodiment of a process for generating a label mapping message as part of a label distribution protocol.

5 is a diagram of an example of a multipoint-to-multipoint network topology.

6 is a diagram of another example of a multipoint-to-multipoint network topology.

Figure 7 is a diagram of one embodiment of the mapping of a set of pseudowires to an underlying packet-switched network to support Operations, Administration and Maintenance (OAM) in an MPLS network.

detailed description

In the following description, numerous specific details are set forth. It is understood, however, that these specific details may not be needed to practice the embodiments of the invention. In other instances, well-known circuits, structures and techniques have not been shown in detail in order not to obscure the understanding of this description. However, it will be appreciated by those skilled in the art that the present invention may be practiced without such specific details. With the included description, one of ordinary skill in the art will be able to implement appropriate functionality without undue experimentation.

Embodiments include a basic tie-breaking procedure with specific properties including the following properties: the procedure will always resolve to a single path, is independent of the order or direction of computation, and has locality properties such that for the paths considered Any part of the draw can be resolved without having to consider the entire path.

The operation of the flowchart will be described with reference to the exemplary embodiment of FIG. 2 . It should be understood, however, that the operations of the flowcharts can be performed by embodiments of the invention different from those described with reference to FIG. 2 and that the embodiments described with reference to FIG . Operations differ from those described in the flowchart. Figures 1 and 5-7 provide example topologies and scenarios illustrating the implementation of the principles and structures of Figures 2 , 3 and 4 .

The techniques shown in the figures can be implemented using code and data stored and executed on one or more electronic devices (eg, end stations, network elements, etc.). Such electronic devices store and transfer (internal and/or over a network with other electronic devices) code and data using non-transitory machine-readable or computer-readable media: non-transitory machine-readable or computer-readable storage media ( For example, magnetic disks, optical disks, random access memory, read only memory, flash memory devices, and phase change memory). Additionally, such electronic devices typically include one or more electronic devices coupled to one or more other components, such as one or more storage devices, user input/output devices (eg, keyboards, touch screens, and/or displays), and network connections. A collection of processors. The coupling of a collection of processors to other components is typically through one or more buses and bridges (also known as bus controllers). The storage device represents one or more non-transitory machine-readable or computer-readable storage media and non-transitory machine-readable or computer-readable communication media. Thus, the storage device of a given electronic device typically stores code and/or data for execution on the set of one or more processors of that electronic device. Of course, one or more portions of an embodiment of the invention may be implemented using different combinations of software, firmware, and/or hardware.

As used herein, a network element (e.g., router, switch, bridge, etc.) is a piece of networking equipment, including hardware and software, that communicates with other devices on the network (e.g., other network elements, end-stations, etc.) interconnection. Some network elements are "multi-service network elements" that provide support and/or Provides support for multiple application services such as data, voice, and video. Subscriber end stations (e.g., servers, workstations, laptops, palmtops, mobile phones, smart phones, multimedia phones, Voice over Internet Protocol (VOIP) phones, portable media players, GPS units, gaming systems, set-top boxes (STB, etc.) to access content/services offered over the Internet and/or over a Virtual Private Network (VPN) overlaid on the Internet. The content and/or services are typically provided by one or more end stations belonging to the service or content provider (e.g. server end stations) or participating in peer-to-peer services and may include public web pages (free content, storefront , search services, etc.), private webpages (for example, webpages that provide username/password access to email services, etc.), VPN-based corporate networks, IPTV, etc. Typically, a subscriber end station is coupled (e.g., via customer premises equipment coupled to the access network (either wired or wirelessly)) to an edge network element that is coupled (e.g., via a or multiple core network elements) to other end stations (for example, server end stations).

Embodiments of the present invention provide systems, networks and methods for avoiding the disadvantages of the prior art, including: poor performance in asymmetric topologies, lack of support for Operations, Administration and Management (OAM) protocols, High resource requirements per packet inspection, high degree of dilution to achieve reasonable network utilization, multiple metric sets to generate and maintain, and making small changes to state require considerable resources.

Embodiments of the present invention overcome these disadvantages by allowing dynamic traffic engineering while minimizing the number of traversals of the topology database for the network. The load distribution method involves dynamic traffic engineering and instantiation using multiple sets of equal-cost paths in the forwarding plane, which can be aggregated into a set of equal-cost trees, whereby each The cumulative number of shortest paths for links will be considered in the tie-breaking for generating the next set of paths. Once a node has performed initial path selection using the tie-breaking process, and all node pairs in the topology database have been processed, the number of shortest paths through each link is determined and referred to as the link utilization value. For each subsequent pass through the database to generate an additional set of paths, truncation between any two nodes by arranging a lexicographically ordered list of link utilization values for each link in each path considered A collection of shortest paths between . If the permuted list has a unique lowest utilized path, that path is selected. If the permuted list has no unique lowest-utilized paths, the basic tie-breaking process is applied to the subset of shortest paths that also have the lowest link utilization.

In the load distribution method and system, a model of network load is computed at each iteration of path generation, taking tie breaking from previous iterations into account in order to balance the load of links in the network. The improved algorithm inherently favors the selection of less loaded links in each iteration after the first iteration.

The load distribution process utilizes a tie-breaking process with different properties such that for any path between two points, it resolves to a single symmetric path, regardless of the direction of computation, the order of computation or checking, for any subset of paths, described is the property that "any part of the shortest path is also the shortest path". Or in other words, where a tie occurs along any part of the shortest path, those nodes will resolve the tie for a subset of paths with the same choice, and the result is a tree of lowest-cost shortest paths. This is referred to in this paper as "common algorithm tie-breaking (common algorithm tie-breaking)” process.

During load distribution, initial experience of the topology database with a common algorithm tie-breaking process results in the generation of a first set of trees. This is because the load on any link has not been recorded, so all equal cost paths will be in an exploited tie, where equal cost is defined by the lowest metric and the lowest number of hops. An initial step requires determining the shortest path between each pair of MPLS nodes in the network, and in case more than one shortest path is found between any two MPLS nodes, utilizing a common algorithmic tie-breaking procedure for tie-breaking, so that A unique path selection between each pair of MPLS nodes in the network is generated, as well as one or more sets of equal cost forwarding trees called "ECT sets".

The load distribution process can rank equal cost paths and determine low and high ranked paths or "bookend" paths, where both paths exhibit sets of precondition attributes. This load distribution process is thus capable of selecting more than one path from a single "all pair" of databases. The load distribution process also calculates the number of shortest paths to traverse each link based on the paths actually selected by the previous tie-breaking process. This value is called the "link utilization" value, which can be used in subsequent calculations. The link utilization value can be a count of pairs of MPLS nodes whose shortest paths traverse the link. In other embodiments, there are more sophisticated possibilities that can be used instead of link utilization considering additional information in the topology database.

In other collections that are subsequently traversed through the database to generate paths or trees, by generating a path utilization that can include a lexicographically ordered link utilization value for each path or simply the sum of the utilizations of each link in the path value, and then rank the resulting paths based on the path utilization value to first rank the set of shortest paths between any two MPLS nodes. It is also possible to utilize two or more permutations since it is advantageous to minimize the number of times the same path is chosen when more than one path is chosen in generating a set of equal cost paths or trees. Using multiple link permutations exhibiting diversity can minimize the number of iterations required to select multiple paths. When the ranking process generates a single least utilized path, that path can be selected without further processing. When more than one ranking is considered (eg, lowest ranking and highest ranking), the lowest utilization path is selected as the lowest and highest ranking path. When more than one equal least exploited path exists, a common algorithm tie-breaking process is applied to the set of least exploited paths to make a choice. In one embodiment, more than one permutation may be selected from this step. When utilizing more than one load permutation mechanism (eg sum of loads and lexicographic sort as permutations), it is also possible to extract multiple permutations from each mechanism when a tie occurs.

Additional runs or iterations of the topology database can be performed, and in each iteration the link utilization value assigned to each link in the path is the shortest path through the links selected during all previous runs of the topology database Cumulative measure or indication.

Figure 1 is a diagram of one embodiment of an example network topology. The example network topology includes 6 nodes with corresponding identifiers 1-6. Path pair not determined for network topology. An exemplary common algorithm tie-breaking process that uses node identifiers to lexicographically rank paths is utilized. Examining the set of equal-cost paths between node 1 and node 4 produces the following permuted set of path identifiers (note that the path identifiers have been sorted lexicographically so that the node identifiers are not shown as passing lists):

1-2-3-4

1-2-4-6

1-3-4-5

1-4-5-6

This initial application of the tie-breaking process would select 1-2-3-4 and 1-4-5-6 as the low and high ranked paths between these nodes. For brevity, in this example, only node pairs 1 and 4 are considered to determine the path count for the network, rather than the shortest path tree from all 6 nodes. In this example, the links in the selected link path are thus each assigned a path pair count of 1. For the next pass through the topology database, the load distribution process will produce the following lexicographic ordering of link loads associated with each path ID.

Load 0, 1, 1 for path 1-2-4-6

Load 0, 1, 1 for path 1-3-4-5

Load 1, 1, 1 for path 1-2-3-4

Load 1, 1, 1 for path 1-4-5-6

A lexicographical ordering of link loads would yield a tie for paths 1-2-4-6 and 1-3-4-5, since each has a load of 0-1-1. Similarly, the sum of link loads will yield:

Load 2 for path 1-2-4-6

Load 2 for path 1-3-4-5

Load 3 for path 1-2-3-4

Load 3 for path 1-4-5-6

As a result for both permutation styles, a secondary tiebreaker of lexicographic sort path IDs is employed. In both cases, the low path (1-2-4-6) was chosen thus aiding the tie breaker. Similarly, 1-3-4-5 can be selected as the highest ranked path ID for the set of lowest loaded paths. In one embodiment, when utilizing low-high selection, two paths are selected. These paths can be identical or have substantial overlap. For example, if path 1-3-4-5 does not exist in the permuted list above, then path 1-2-4-6 would qualify as the lowest cost low and high permuted path. In other embodiments, the initial input to low routing can be from a load-based lexicographically ordered permutation, and the primary input to high routing can be from a load-sum based permutation.

While this example only considers link utilization from examining one path, one of ordinary skill in the art will appreciate that there is a comprehensive view of possible traffic distribution after a single pass through the database, and that tie-breaking of subsequent passes will inherently avoid the most A large number, and thus the load is distributed more evenly across the network. The degree of modification of load distribution decreases proportionally with each new set of paths considered, since the effects are additive.

The number of paths selected per iteration of the process and the cumulative number of paths the network is configured to utilize can vary as a priori the forwarding state vs. required computational power analysis. Choosing the lowest and highest ranked paths with the lowest cost will minimize the amount of computing power required for a given improvement in the standard deviation of link utilization, but will therefore require more forwarding since two sets of equal cost trees are generated per iteration state. Selecting a single path permutation from each iteration will require more computational power, but will reduce the forwarding database required for a given reduction in the standard deviation exploited since minimizing the number of times two paths must be selected from the single lowest exploited candidate state quantity. The overall number of paths generated is determined based on a combination of network element states and computing power considerations for network efficiency balance. Permuting path loads with multiple schemes allows more paths to be selected from a given experience of the database because it reduces the probability of selecting the same path more than once for a given number of path selections. In the examples above, two techniques for permuting path loads are described that will produce consistent results across network applications. In other embodiments, additional or alternative methods of alignment can be utilized. For example, other mechanisms and combinations of such permutations can utilize permutation loads that also have the property of locality (when combined with a common algorithmic tie-breaking process, any part of the lowest load path is also the lowest load).

Also, in the above example, the link is represented by the count of the shortest path that has passed through the link. Many variations are possible to represent link utilization with more detail and increased accuracy. Within the label information and topology database, there is enough information to enable each node in the network to determine the number of service instances using a particular shortest path. A link utilization value can be determined based on this utilization to appropriately weight the corresponding link. Additional bandwidth profiling information per service is available for use in load distribution calculations by augmenting the tag information or data stored by the topology database. In another embodiment, only the minimum link metric of the link set in the path is used as a representative of the maximum load that can be provided between the pair of nodes. In other embodiments, similar metrics or more detailed metrics can be utilized.

In one embodiment, all but the last experience of the topology database involves an "all pairs" computation of the shortest paths between all pairs of nodes in the network. This can be computationally expensive due to complexity. However, the load distribution process does not require a significant amount of experience via the topology database in order to yield measurable benefits, and as a result, the load distribution process provides valuable overall improvements in network resource allocation, which justify these "all pairs" calculations of.

In the experimental example using random graph generation, a single pass through the database after building the initial ECT set yielded approximately an average of 45% coefficient of variation in link load measured as the count of the shortest paths through each link in the network reduce. Three additional experiences across the topological database continued to reduce the coefficient of variation to the point of an average 75% reduction, but most of the benefit came from the first experience after the baseline was established. Therefore, most of the benefits in load distribution are gained in the first two passes of the database. When the second set is explicitly placed to avoid the load of the first set, the number of paths through the network doubles. However, the rate of improvement in the coefficient of variability decreases experience-by-experience much faster than the 1/2, 1/3, 1/4 rate that the cumulative path counts would suggest. Thus, remarkable results can be achieved while keeping the load distribution process traceable in terms of both computation and forwarding state.

Since the method is connection-oriented in nature and seeks the least loaded link, any perturbation of the traffic matrix by a fault tends to be isolated and local in nature. Once constraints in the network have been circumvented, the load distribution process will tend to direct data traffic back into the original distribution. This approach is also applicable to emerging MPLS-TP technology bases such as Operations, Administration and Management (OAM) protocols that can be utilized without modification and preserve the architecture and service guarantees of MPLS networks.

The load balancing process and system also enables an administrator to "pre-bias" links by a load factor, which will have the effect of shifting a certain load away from a particular link. This allows for more subtle gradations for manipulating routing behavior than simple metric modification, much simpler administration than multi-topology routing, and eliminates the need for link virtualization ( as per RFC 4206 MPLS "forwarding proximity" (forwarding adjacencies) to artificially promote the need to increase the grid density. For two-phase sequencing, the timing of when to apply the link bias has an impact. It is generally only considered for the second and subsequent iterations. In an implementation where all equal cost paths are tied to a tie (zero) of utilization in the first iteration, immediately applying the bias factor will tend to move all loads away from the link, biased towards other paths by the first iteration.

Figure 2 is a diagram of one embodiment of a network element implementing a load distribution method involving link utilization as feedback into a tie-breaking mechanism. The network unit 200 can include a label information database 215 , a topology database 217 , an ingress module 203 , an egress module 205 and a control processor 207 . The ingress module 203 is capable of handling the processing of data packets received by the network element 200 at the physical link and data link layers. Egress module 205 handles the processing of data packets transmitted by network element 200 at the physical link and data link layers. Control processor 207 handles routing, forwarding and higher level processing of data traffic. The control processor 207 can execute or include a shortest path search module 209 , a load distribution module 215 , a label distribution protocol (LDP) module 213 , an MPLS management module 217 and a sorting module 211 .

The label information database 215 includes tables with label forwarding entries defining the manner in which data packets are to be forwarded. Label forwarding entries associate labels with the underlying FEC and virtual topology with the network interface of the network element 200 . This information can be used by the control processor 207 to determine what to do with the data packet, ie to which network interface the data packet should be forwarded. As described herein below, load distribution methods and systems create label forwarding entries via Label Distribution Protocol (LDP) that enable load distribution.

The topology database 217 stores a network model or similar representation of the topology of the network to which the network element 200 is connected. In one embodiment, the nodes in the network are each Label Switching Router (LSR), and the links between LSRs can utilize a number of underlying protocols and technologies. Nodes can be identified by unique node identifiers such as node loopback addresses and links by pairs of node identifiers. Those skilled in the art will understand that this network model representation is provided as an example and that other representations of network topologies can be utilized by the load distribution method and system.

The shortest path search module 209 is a component of the control processor 207 or a module executed by the control processor 207 . The shortest path search module 209 traverses the topology database to determine the shortest path between any two nodes in the network topology. If there are multiple paths with equal distance or cost between two nodes in the network, and these multiple paths are all shortest paths, then these multiple equal cost paths can be provided to the ordering module 211 and the load distribution module 215 to Determine which path to utilize. The shortest path search module 209 is capable of determining the shortest paths between all nodes in the network topology, which is referred to herein as an "all pairs" computation.

The shortest path search module 209 provides a set of shortest paths for each node pair, and the load distribution module 215 selects a subset of the shortest paths and updates the tag information database to include the subset of each shortest path that enables traversal of the network element 200 entry.

After the first experience, the shortest path search module 209 calculates the link utilization value for each link in the network topology resulting from the first experience via the topology database. A link utilization value is a count of the number of selected shortest paths that traverse a given link. Separate link utilization values are calculated and recorded for each link. These link utilization values are used to generate path utilization values which in turn are used to bias the permutation of paths for subsequent experience via the topology database, where the initial tie breaker is a permuted list of lexicographically ordered link utilization values or is the sum of link utilization values (ie, in the form of path utilization values), and where this results in a tie, the common algorithm tie-breaking process is used as a subsequent tie-breaker.

The ranking module 211 is a component of the control processor 207 or a module executed by the control processor 207 . Ranking module 211 assists load distribution module 215 by performing an initial ranking of load sets of equal cost trees based on path utilization values in the second pass and in subsequent passes.

For each node pair with multiple equal cost paths, ranking module 211 generates a permutation of each of these equal cost paths based on the path utilization values, and load distribution module 215 selects at least one path from this permutation. In other embodiments, the highest ranked and lowest ranked paths can be selected to divide the load between corresponding pairs of nodes. The load distribution module 215 is a component of the control processor 207 or a module executed by the control processor 207 .

This process can be repeated through any number of iterations or iterations, in which the link utilization value is updated as a cumulative indication of the set of shortest paths traversed. Path utilization values are also updated with changes to link utilization values. The standard deviation in variation among paths generally decreases with each iteration, but as the number of path sets rises, the overall impact of each additional set decreases proportionally, indicating that using more than two or three passes or Iterating is not worth the computational effort or instantiated forwarding state. The number of passes or iterations is specified by the administrator and configured network-wide.

The MPLS management module 217 is a component of the control processor 207 or a module executed by the control processor 207 . MPLS management module 217 examines incoming packets and determines associated labels, and performs a lookup of the packets in label information database 219 to determine the network interface through which to forward the packets. MPLS management module 217 also performs any necessary label switching, label addition, or label removal to effect proper traversal of the LSP for each data packet.

The LDP module 213 is a component of the control processor 207 or a module executed by the control processor 207 . The LDP module 213 generates the messages needed to establish forwarding equivalence class (FEC) and virtual topology-to-label bindings in the network, bindings are used to create those LSPs, and LSPs are used to distribute the load of the network. The LDP module 213 generates a label mapping message including an FEC type length value (TLV) field, a label TLV field and a virtual topology TLV field. The Topology TLV field includes a topology index indicating which iteration of the load distribution process the label and FEC are associated with. The LDP module 213 also performs other conventional functions to enable label distribution.

3 is a flowchart of one embodiment of a process for load distribution that supports automated traffic engineering for multiprotocol label switching based on using link utilization as feedback to a tie-breaking mechanism for equal cost paths. In one embodiment, the process can be run at startup of a network element such as a link switch router, when a network connected to the router is notified of a topology change, at defined intervals, or at similar events or times. The topology database is maintained at each network element in the network as a separate process from the load distribution process and is assumed to be a current representation of the true topology of the network.

In one embodiment, the load distribution process begins by determining a set of shortest paths between a network element or MPLS node (eg, LSR) in the network and another network element or MPLS node in the network (block 301 ). The set of shortest paths can be viewed as a set of individual paths or a tree with each network element as the root of its corresponding tree. A check is made to determine if there are multiple shortest paths, ie if there is a tie of shortest paths between MPLS nodes (block 303). If the MPLS node pair has a single shortest path between them, then the label information database is updated to reflect that shortest path (block 306). In one embodiment, the label information database is updated to reflect each path that traverses the network element that maintains it. Every network element in the network performs this same calculation. The load distribution method is deterministic, and thus each network element will produce the same result. Unless there is a change in topology, no further processing of those MPLS node pairs with a single shortest path is necessary.

If the MPLS node pair does not have a unique shortest path, typically measured as the lowest number of hops and lowest cost, a common algorithm tie-breaking approach is used to permit selection of a unique shortest path or set of shortest paths (block 305). In one embodiment, the first and last ranked paths may be selected. After paths are selected, they are stored in the label information database or used to update the label information database so that all pairs of MPLS nodes have at least one path selected between them.

After the shortest path is selected, a check is made to determine if all MPLS node pairs already have the path selected (block 307). If additional MPLS node pairs do not already have the path or set of paths selected, the process continues by selecting the next MPLS node pair to process (block 309). If all MPLS node pairs already have shortest paths selected, the process continues to a second pass or iteration.

A link utilization value for each link is calculated due to or after the update of the forwarding database for all MPLS node pairs has been completed (block 310). A link utilization value is a count of the number of paths that traverse each corresponding link in the network's topology. Calculate link utilization values for each link in the network. Link utilization values provide an indication of the level of use and potential bottlenecks in the network that should be avoided when additional paths are to be formed.

For subsequent generation of shortest paths, tie breaking is initially performed by generating path utilization values as a lexicographically ordered list or sum of link utilization values where the path utilization values include link utilization values. The all node process begins again by selecting pairs of MPLS nodes and determining the set of shortest paths between the pairs of MPLS nodes (block 311 ). This process includes path utilization values based on the link utilization values corresponding to each path (block 313). Path utilization values can represent the overall load for each path, as a sum of link utilization values, or can be a lexicographically ordered arrangement of link utilization values, highlighting the most or least loaded link in each path, or similar arrangement and presentation. The shortest paths are ranked by their path utilization values (block 315). A check is made to determine if there is more than one shortest path for a given pair of MPLS nodes with equal path utilization values.

Where there is a unique lowest loaded path, that path can be selected without further processing of all path permutations (eg lowest and highest). When there is more than one shortest path with the same load (ie, same path utilization value), the common algorithm tie-breaking process is then used to perform path selection in this subset of the lowest loaded set of shortest paths (block 321 ). Ranking takes into account link utilization values such that the path with the lowest or least used link is most likely to be chosen, which takes into account the overall load of the network and not just the next hop in the network, and consequently, the Routing is more balanced. The tag information database is then updated to reflect the selected path (block 318).

Then, a check is made to determine if all pairs of MPLS nodes have the selected shortest path or set of shortest paths (block 319). If not, the process continues by selecting the next MPLS node pair to process (block 323). If all MPLS node pairs have been calculated, then a check is made to determine if additional trees are required (block 325). If no further trees are required (this may be a parameter set by the network administrator or similarly determined), the load distribution process ends. If additional paths are required, the process continues through a third experience or iteration similar to the second experience or iteration but constructed on the use of links determined in previous iterations. This process can have any number of iterations.

Figure 4 is a flowchart of one embodiment of a process for generating a label mapping message as part of a label distribution protocol. In one embodiment, the process is initiated in response to a change in topology or a change in the label information database for the network. In another embodiment, the process is initiated periodically to maintain the state of the MPLS network. The process is initiated by each node generating a label mapping message to be sent to one of its peers (block 401).

The Tag Mapping message includes a number of Type Length Value (TLV) fields. A separate label mapping message is generated for each forwarding equivalence class (FEC) and each topological path or tree in the network's topology as represented in the host node's label information base. For each label mapping message, a corresponding field equivalence class is defined in the FEC TLV field of the label mapping message (block 403).

The label TLV field of each label mapping message is also defined according to the label assigned to the LSP for each interface in the path (block 405). The topology index is also defined in the label map message (block 407). The topology index indicates the iteration of the selection process for the LSP defined by the Label Mapping message. For example, if the label mapping message corresponds to a first selected tree or path, a topological index of 0 or 1 may be selected and inserted into the label mapping message. Similarly, if the second path or tree corresponds to a message, 1 or 2 may be assigned as the value. Once each label mapping message has been defined and specified each of its values, the label mapping message can be sent to each label distribution protocol peer (block 409). In one embodiment, the topology index is included in the existing TLV of the label mapping message. In another embodiment, a topology TLV is defined for label mapping messages.

Figure 5 is a diagram of one embodiment of a multipoint-to-multipoint network including a collection of label switched routers (LSRs) 1-18. The graph shows, for a given example, the set of paths or trees defined by the first iteration of the procedure defined above. The diagram assumes that the ingress to this network can be distributed within nodes 1-4 and similarly within 13-18, in other words these LSRs are at the edge of the network but have the same external interface. In this example, in the first run, the process would be all node pairs from 1-13 to 4-18 (e.g., 1-5, 5-9, 9-13 and 4-8, 8-12, 12 -18) Generating a lexicographically ordered set of unique paths, from this set of unique paths the example assumes that low and high paths corresponding to trees 501 and 503 are selected from permutations of these unique path identifiers.

Figure 6 shows the paths or trees selected in the second iteration of the load distribution method set out above. In this example, the load distribution method finds two paths where a lexicographical ordering of the link loads associated with each path produces a tie between the two paths, and an exemplary lexicographical ordering of node IDs as path identifiers sort is called to authoritatively resolve the tie. The lowest ranked tree 605 and highest ranked tree 607 from the second iteration also distribute traffic between nodes 1-4 and nodes 13-18 and complement the lowest ranked tree 601 and highest ranked tree 601 from the first iteration shown in FIG . tree 603. By including link usage values in the lexicographic ordering, the second iteration selects the equal cost path with the least utilized link, thereby increasing bandwidth utilization and topology diversity of the "all pairs" paths selected.

Figure 7 is a diagram of one embodiment of the mapping of a set of pseudowires to an underlying packet-switched network to support Operations, Administration and Maintenance (OAM) in an MPLS network. By virtue of covering a full mesh of peer-to-peer LSPs between endpoints equivalent to a set of pseudowires, performance monitoring and compatibility can be maintained by the traffic engineering system. Packet-switched networks scale order (N), and fault management can scale accordingly, but the overlay layer has the required peer properties for performance monitoring. The FEC of the pseudowire is modified to bind the pseudowire FEC to the PSN virtual topology index. Since the PSN topology is logically peered between the pseudo-endpoints, the pseudowire label provides means for source disambiguation of the OAM counters.

Thus, methods, systems and apparatus have been described for load distribution in MPLS networks that take link usage into account. It is to be understood that the above description is intended to be illustrative rather than restrictive. Many other embodiments will be apparent to those of skill in the art upon reading and understanding the above description. The scope of the invention should, therefore, be determined with reference to the appended claims, along with the full scope of equivalents to which such claims are entitled.

Claims (18)

1. one kind in the node of multiprotocol label switching MPLS network for the load distribution improved and the method realized, wherein said node is one of multiple nodes in described MPLS network, each node realizes common algorithm draw break-ing process to produce minimum cost shortest path tree, described node includes that topological database is to store the topology of described MPLS network, the topology of wherein said MPLS network includes multiple node and link between the nodes, said method comprising the steps of:

By the topology of the described MPLS network of storage in described topological database is performed Shortest Path Searching Algorithm, determine in described MPLS network each MPLS node between the first set of one or more shortest paths；

By applying described common algorithm draw break-ing process, from described first set of shortest path, select at least the first shortest path for each MPLS node pair；

The counting of shortest path based on the selection through each link, for each link calculation link utilization value of described MPLS network；

By the topology of the described MPLS network of storage in described topological database is performed described Shortest Path Searching Algorithm, determine in described MPLS network each MPLS node between the second set of one or more shortest paths；

Based on the link utilization value corresponding to each shortest path, generate path utilization value for each shortest path in described second set of one or more shortest paths；

Incompatible selection the second shortest path is collected from described the second of one or more shortest paths on the basis of described path utilization value, when wherein there is multiple shortest path with equal path utilization value in this set of one or more shortest paths, common algorithm draw break-ing process described in described Selection utilization；And

In label information data base, storage is used at least the first shortest path and second shortest path of each MPLS node pair, and the business entering described MPLS node is forwarded to where by wherein said label information data base instruction,

The described selection of the second subset thus utilized in view of path minimizes the standard deviation of the load distribution across whole MPLS network.

2. the method for claim 1, the described step wherein generating described path utilization value also includes:

The link utilization value that would correspond to each path is added, or

The link utilization value that would correspond to each path carries out dictionary formula sequence.

3. method as claimed in claim 2, further comprising the steps of:

The link amendment factor is received from manager；And

Combine described link the amendment factor and described link utilization value with by one of corresponding with path for described link weighting, in order to reduce the probability of selection by affecting the arrangement of the set in minimum load path, thus reduce the use of described link.

4. method as claimed in claim 2, further comprising the steps of:

Based on respective path utilization value, each shortest path in described second set of ranked shortest path,

The described step wherein selecting the most described second shortest path also includes:

The shortest path of the highest and minimum arrangement is selected from described arrangement.

5. method as claimed in claim 2, further comprising the steps of:

Select other shortest path iteratively to carry out load sharing distribution with described first shortest path and the second shortest path, until it reaches the reflection Virtual network operator management quantity to the desired path of the general improvements of ethernet network.

6. the method for claim 1, wherein MPLS node between the described set of shortest path be implemented as the label switched path in described MPLS network.

7. the method for claim 1, further comprising the steps of:

Generate label mapping message；

Define the FEC type lengths values TLV field in described label mapping message；

Define the label TLV field in described label mapping message；

Definition is selecting the iteration at least the first shortest path of each MPLS node pair and the described step of the second shortest path for the topological Index of described label mapping message, the instruction of wherein said topological Index；And

Each tag distribution protocol peer-to-peer that described label mapping message is sent in described MPLS network.

8. method as claimed in claim 7, wherein label mapping message is sent to each LDP peer to realize each combination of FEC and topological Index value.

9. the NE being used for improving load distribution in multiprotocol label switching MPLS network, described MPLS network includes described NE, wherein said NE is one of multiple nodes in described MPLS network, the topology of wherein said MPLS network includes that the link between multiple node and described node, described NE include:

Topological database, stores link information for each link in described MPLS network；

Label information data base, for each port stored tag information of described NE, each forwarding equivalence class FEC entering described NE is forwarded to where by wherein said label information data base instruction；

Controlling processor, be coupled to described topological database and described label information data base, described control processor is configured to process data service, and wherein said control processor includes:

MPLS manages module, is configured through label switching path LSP and forwards data service；

Tag distribution protocol LDP module, is configured to set up LSP in described MPLS network；

Shortest Path Searching module, be configured through that described topological database is performed Shortest Path Searching Algorithm and determine in described MPLS network each MPLS node between at least one shortest path, wherein said Shortest Path Searching module is configured to, and is sent to load distribution module for each MPLS node with multiple equivalent cost shortest paths to by described equivalent cost shortest path；

Order module, is configured to arrange each path of the plurality of equivalent cost shortest path based on the path utilization value derived from the link utilization value being associated with each path in the plurality of equivalent cost shortest path；And

Described load distribution module, it is configured to select the first subset of the plurality of equivalent cost shortest path for this MPLS node pair from the plurality of equivalent cost shortest path received, described first subset to be used for described MPLS node between sharing data service load, and based on described path utilization value, select to be used for and the second subset of the described first subset sharing data service load for this MPLS node pair from the plurality of equivalent cost shortest path for this MPLS node pair

Thus minimize the standard deviation of the load distribution across whole MPLS network in view of the described selection of the second subset of described path utilization value.

10. NE as claimed in claim 9, wherein said order module is configured to the arrangement described link utilization value carrying out dictionary formula sequence to create the plurality of equivalent cost shortest path.

11. NEs as claimed in claim 9, wherein said Shortest Path Searching module is configured to, for link utilization value described in each link calculation in described topology.

12. NEs as claimed in claim 9, wherein said control processor be configured to generate label switching path LSP with real presently described MPLS network interior nodes between the shortest path of each selection.

13. NEs as claimed in claim 9, wherein said load distribution module is configured to receive the link amendment factor from manager, and combine the described link amendment factor and link use value with by link weight corresponding in path, reduce the probability of selection will pass through the dictionary formula sequence affecting this path, thus reduce the use of described link.

14. NEs as claimed in claim 9, wherein said load distribution module is configured to the highest and lowest term in the described arrangement by selection equivalent cost shortest path, from the first subset described in each Path selection of the plurality of equivalent cost shortest path.

15. NEs as claimed in claim 9, wherein said load distribution module is configured to by applying common algorithm draw break-ing process to select the highest and lowest term, from the second subset described in each Path selection of the plurality of equivalent cost shortest path to the described equivalent cost shortest path with minimum load.

16. NEs as claimed in claim 9, wherein said order module and load distribution module are configured to select other subset iteratively to distribute with described first subset and the second subset load sharing.

17. NEs as claimed in claim 9, wherein said LDP module is configured to generate label mapping message, label TLV field in the FEC type lengths values TLV field being included in described label mapping message, described label mapping message, the topological Index for described label mapping message, wherein said topological Index instruction iteration in selecting described first subset and the second subset, and described LDP module is configured to each tag distribution protocol peer-to-peer of being sent in described MPLS network by described label mapping message.

18. NEs as claimed in claim 17, wherein said LDP module is configured to each combination label mapping message being sent to each LDP peer to realize FEC and topological Index.