Provider link state bridging (plsb) computation method

The present invention relates to traffic forwarding in a packet network, and particularly to a method of processing by a provider link state bridging (PLSB).

Network operators and carriers are developing packet-switched networks instead of circuit-switched networks. In the case of a packet exchange network such as the Internet Protocol (IP) network, IP packets are routed according to the routing method stored in each IP router in the network. Similarly, in the case of an Ethernet network, Ethernet frames are transferred according to the transfer method stored in each Ethernet switch of the network. The present invention is applicable to a communication network that uses a network based on an arbitrary protocol data unit (PDU), and in the present application, "packet", "packet switching network", "routing", "frame", and "frame" are used. The terms "network used", "forwarding" and other related terms are intended to include any PDU, communication networks that use PDUs, and the selective transmission of PDUs from network node to network node, and the like. There is.

Multicast forwarding of data packets (the virtual simultaneous transmission of packets from a source node to multiple destination nodes) is becoming more demanding for services such as Internet Protocol Television (IPTV) and Video on Demand (VoD). It becomes more and more important.

IS-IS System-Intermediate System (IS-IS), Open Shortest Path First (OSPF) and Multicast OSPF distribute topology information and distribute the calculation of paths that interconnect multiple nodes. It is used to install the transfer method (transfer state) required to enable IS-IS and realize those paths. OSPF and IS-IS are executed by nodes distributed in the network. For example, when a topology change occurs in a network when a node or link fails, the information is sent to all nodes by protocol processing, and the network is sent. Each node recalculates the path locally so that it is consistent with the topology and avoids glitches.

For Ethernet networks, Provider Backbone Transport (PBT) (or Provider Backbone Bridge Traffic Engineering (PBB-TE)) uses unicast Ethernet transport technology as described in UK Application GB2422508. There is. As described in US Patent Application No. 11 / 537,775 by Applicants, the Provider Link State Bridge (PLSB) uses IS-IS to provide multicast transmission capabilities to Ethernet networks, unicast paths and multicast trees. Used to configure both in the network. Each of the above patent applications is incorporated into the reference of the present application.

Although the term Ethernet is used in the present application where possible, the present invention is not limited to examples of routing systems for Ethernet bridges. For example, the term filtering database (FDB) is synonymous with anything related to information repositories of packet forwarding information, such as information bases or label information bases.

For example, a multicast tree in a PLSB network is calculated using a multicast route calculation algorithm for all shortest pairs, which is described, for example, in US Patent Application Publication No. 20070165657 by the applicant of the present application. With this method, when a node receives a change in multicast group membership or a change in network topology (eg, via the Link State Protocol Data Unit (LSP)), the node uses an algorithm such as Dijkstra's algorithm. Then, both a group of network node pairs (pairs) and unicast connections connected by the shortest route across the calculated node are calculated. For that group of node pairs, the nodes determine where multicast membership intersections occur, determine the required FDB entries, and implement part of the multicast path accordingly. The unicast and multicast forwarding method that achieves the calculated path is then installed in the node's filtering database (FDB) and the received packets are forwarded to the appropriate output port of the node based on the destination address of that frame. To do so.

As will be understood, the computational burden of identifying a node pair in which each shortest path crosses a particular node is very heavy. Because we have to inspect the paths that extend from each node to all the other nodes. In some cases, the size of the network is limited in terms of being able to perform the required calculations within an acceptable time period. Obviously, using a more powerful processor will increase the computing speed, but it is not desired to increase the cost of each node.

<p><patcit num="1"><text>UK Patent Application Publication No. 2422508</text></patcit><patcit num="2"><text>U.S. Patent Application Publication No. 2007-0165657</text></patcit></p>

<p> Therefore, it is still highly desired to improve the calculation efficiency of the multicast route in the packet switching network.</p>

<p> The method according to one embodiment is A method of calculating multicast routes in a network controlled by a link-state protocol. A step of calculating a spanning tree from the first node to all other nodes in the network using a known shortest path tree algorithm. A step of dividing the network into a plurality of partitions, each partition within the network subordinate to the neighboring nodes of the first node in the calculated spanning tree and the neighboring nodes in the calculated spanning tree. Steps and, including nodes of If certain conditions are met, the step of merging two or more of the partitions, and With the step of checking the nodes belonging to all partitions except the largest partition and identifying the node pair whose shortest path passes through the first node. It is a method having.</p>

<figref num="1">The flowchart which shows the principle step of the method by one Example of this invention.</figref><figref num="2a">The figure which shows the process of the step shown in FIG. 1 used in a network.</figref><figref num="2b">The figure which shows the process of the step shown in FIG. 1 used in a network.</figref><figref num="2c">The figure which shows the process of the step shown in FIG. 1 used in a network.</figref><figref num="2d">The figure which shows the process of the step shown in FIG. 1 used in a network.</figref><figref num="2e">The figure which shows the process of the step shown in FIG. 1 used in a network.</figref>

One embodiment of the present invention provides a method of computing a multicast route in a link state protocol controlled network. A known spanning tree protocol is used to calculate the spanning tree from the first node in the network to all other nodes. The network is then divided into two or more parts (partitions), each partition containing an immediate neighbor node of the first node and any node of the network subordinate to the neighbor in the spanning tree. If certain conditions are met, two or more partitions will be merged. Nodes belonging to all partitions except the largest partition are identified, and each identified node is inspected to identify a node pair whose shortest path passes through the first node.

<p> Further features and advantages of the present invention will become more apparent with reference to the following detailed description along with the accompanying drawings.</p><p> It should be noted that in the accompanying drawings, similar elements are indicated by similar reference numbers.</p><p> The present invention provides a PLSB calculation method that minimizes the number of nodes that need to be inspected when finding all node pairs that provide the shortest path for a given node. In some cases, the number of nodes that need to be inspected can be reduced to zero. Hereinafter, examples of the present invention will be described with reference to FIG. 1-2e as a mere example.</p><p> First, the method according to the invention is useful for networks in which the shortest paths calculated are symmetric (ie, networks that can be represented as undirected graphs) and have the same cost2. If more than one path or route could be calculated between some two nodes, then either path with equal cost so that the selected "shortest" path is symmetric and locally consistent. It is necessary to use the tie breaking method to select. In this case, "locally consistent" means that any partial path of the equal cost path selected by the tie-breaking method is itself selected by the tie-breaking method. It means that it must be the shortest path. The tie-breaking method used with respect to the method of the present invention is described in US Patent Application No. 11 / 964,478 filed by the applicant of the present application on December 26, 2007.</p><p> FIG. 1 is a flowchart showing the principle steps of the method according to the embodiment of the present invention, and FIGS. 2a-e are diagrams for explaining the processing of the steps shown in FIG. 1 used in each network. ..</p><p> With reference to Figure 2a, a typical PLSB network has multiple nodes (indicated as node AR) interconnected by links. Normally, in a PLSB network, all the nodes belonging to the network in Figure 2a-e are connected to at least the other two nodes, but this is not required. Preferably, the method according to the invention is implemented so that it is performed at substantially the same time on all nodes. In the following description, the method will be described in terms of a specific example of finding the shortest path through node "A".</p><p> With reference to Figures 1 and 2b, in the first step, the spanning tree from node "A" to all other nodes in the network is a traditional shortest path tree algorithm, such as Dijkstra's algorithm. Calculated using. As shown in Figure 2b, the spanning tree (shown by the thick solid line in Figure 2b-e) extends from node "A" to each of its neighboring neighboring nodes (nodes B, C, D and E). It has multiple branches that extend. According to this tree structure, all nodes on the network belong to one of these branches. Therefore, it is theoretically possible to divide the network into a group of partitions (parts), each of which contains its own branch in spanning tree.</p><p> Therefore, according to this tree configuration, each of the partitions includes its own corresponding one in the adjacent node and all the nodes subordinate to the adjacent node in the spanning tree. For convenience of explanation, each branch / partition is represented using the identifier of its neighbor node, which acts as the root of the branch. Therefore, in FIG. 2c, the four partitions are shown as partitions "B", "C", "D" and "E" that identify their root nodes.</p><p> As shown in Figure 2c, any shortest path through node "A" must start at one partition and end at another. Due to the symmetry of the path between node pairs or node pairs, when discovering all node pairs whose shortest path passes through "A", the number of nodes to consider considers all nodes in only one partition. It can be reduced by. The advantage of this reduction method is that the largest partition can be selected as the omitted partition in terms of the number of node members, and only the paths terminating at the nodes belonging to the smaller remaining partitions need to be considered. By noticing, it can be maximized.</p><p> The only way to further reduce the number of nodes that need to be inspected is if the route between the root nodes contained in the partition is shorter than the two-hop route through node "A". The shortest path between any node in any node and any node in any other partition is obtained by noticing that it does not pass through node "A". For example, considering the path between nodes M and R in the example of FIG. 2, they belong to partitions "D" and "E", respectively. In this example, only the number of hops will be considered as a criterion for determining the shortest path, but other criteria may be used as well. Examining the network, the root nodes "D" and "E" are directly connected by links. Therefore, the shortest path between nodes M and R passes only through the root nodes "D" and "E", not through the node "A". Considering the other nodes of partitions "D" and "E", not all of the shortest paths go through the direct link between the root nodes "D" and "E", but the existence of a direct link means that there is a direct link. , It can be seen that none of these shortest paths guarantees that they will pass through node "A". Therefore, when performing the calculation focusing on "A", the partitions "D" and "E" can be merged into one large partition (super partition) "DE".</p><p> The above process of discovering shorter routes between root node pairs in a partition or super partition pair and merging partitions whenever a sufficient number of short routes are found is (a) all partitions. Is merged into one superpartition (ie, such a superpartition will cover the entire network except node "A"), or (b) a path shorter than two hops through node "A". It is possible to reverse until there is no partition pair that interconnects all the root nodes belonging to the partition. Whether or not two partitions can be merged can be determined by considering the root node of the partition under consideration for merging. Considering the simple case of a pair of partitions, each of which has one root node, the root nodes of the two partitions are connected by a route shorter than two hops through node "A". Only two partitions can be merged. For a more complex example where there is a partition with one root node and a super partition with N (N&gt; 1) root nodes, between the root node of the partition and the N root nodes of the super partition The two partitions can be merged if none of the shortest paths go through node "A".</p><p> Next, referring to Fig. 2d, if we continue to use the number of hops as the reference for the shortest path, the partition "B" can be merged with the super partition "DE" to generate the super partition "BDE". Is. This is because the root node "B" is directly connected to the two root nodes of the super partition "DE". This ensures that there is no shortest path between any pair of nodes in the superpartition "BDE" through node "A". On the other hand, referring to Figure 2e, it is shown that the partition "C" cannot be merged with the super partition "BDE". This is because there is no direct link between the root node "C" and the root node "E" of the superpartition "BDE". That is, partition "C" cannot be merged with partition "E" and cannot be merged with any superpartition containing partition "E".</p><p> As shown in Figure 2e, the above partition merging process results in a network divided into two partitions, the two partitions being the partition "C" and the super partition "BDE". As mentioned above, all the shortest paths of interest can be found by examining the nodes belonging to each partition except the largest partition. In the case of FIG. 2e, all the shortest paths passing through the node "A" can be found by inspecting the node "C" and examining each of the shortest paths extending from the node "C" passing through the node "A". As you can see, in the case of the current example, this significantly reduces the PLSB computational load required for the network. This is because we only need to consider the path that extends from one node (in this respect, which is very different from the prior art that had to consider 17 nodes).</p><p> It will be understood that the benefits of merging partitions depend on the network topology. If all partitions can be merged into one superpartition that covers the entire network, then the number of nodes to consider (after the overhead step of processing the partitions) will be zero. In the more typical example, the process of merging partitions will result in multiple partitions and / or superpartitions. In the special case where node "A" is a dual connected edge node, the initial number of partitions is 2. If these two partitions can be merged properly, the number of nodes that need to be inspected will be reduced to zero. In the worst case, which could not be merged, the number of nodes that need to be inspected is slightly less than half the number of nodes in the network, which is still a significant improvement over traditional methods.</p><p> As is known in the art, route calculation methods such as IS-IS and Open Shortest Path First (OSPF) and Multicast OSPF provide multiple routes with equal cost between node pairs. May generate. In such cases, the above method of merging partitions may be used without modification: in that case the "cost" of each route is proportional to the number of hops; or directly between the two partitions. The "cost" of a link is less than the "cost" of a two-hop route through the node of interest (node "A" in the example in Figure 2).</p><p> A tie-breaking algorithm should be used to select the "shortest" path or a subset of the shortest paths from a set of paths with equal cost between a pair of nodes. In such cases, it is possible to use the above method of merging partitions. However, it is assumed that the "shortest" path selected by the tie-breaking algorithm is symmetric and locally consistent.</p><p> For example, in the network of FIG. 2, consider the case where the route calculation result shows three routes having the same cost between nodes C and E. In this case, the tie-breaking algorithm is used to select one of these three equal-cost routes as the "shortest" route. In this case, if the tie-breaking method selects either of the two routes that pass through node B or D but not node A as the shortest route, the above method uses partition "C" as the super partition "BDE". May be merged with.</p><p> As will be understood, it is extensible if there is the same methodology, in which case the route calculation algorithm calculates a set of routes with equal costs and the tie-breaking method is two of those routes with equal costs. This is the case when one or more subsets are selected as the shortest path. In this case, the criterion for merging the two partitions is that no shortest path is selected through the node currently under consideration. For example, the tie-breaking method may select any two routes between nodes C and E as the shortest path in a group, and the above method may cause the shortest path in the group to pass through node "A". The partition "C" and the super partition "BDE" can be merged if the route is not included.</p><p> The above embodiments of the present invention are intended to be merely exemplary. Therefore, the scope of the present invention is defined only by the appended claims.</p>