Provider link state bridging (plsb) computation method

PROVIDER LINK STATE BRIDGING (PLSB) COMPUTATION

METHOD

CROSS-REFERENCE TO RELATED APPLICATIONS

0004[ 0001] This is the first application filed for the present invention.

MICROFICHE APPENDIX

0006[ 0002 ] Not Applicable.

TECHNICAL FIELD

0008[ 0003 ] The present invention relates to traffic forwarding in packet networks, and in particular to a Provider Link State Bridging (PLSB) computation method.

BACKGROUND OF THE INVENTION

0010[ 0004 ] Network operators and carriers are deploying packet-switched communications networks in place of circuit-switched networks. In packet-switched networks such as Internet Protocol (IP) networks, IP packets are routed according to routing state stored at each IP router in the network. Similarly, in Ethernet networks, Ethernet frames are forwarded according to forwarding state stored at each Ethernet switch in the network. The present invention applies to communications networks employing any Protocol Data Unit (PDU) based network and in this document, the terms "packet" and "packet-switched network", "routing", "frame" and "frame-based network", "forwarding" and cognate terms are intended to cover any PDUs, communications networks using PDUs and the selective transmission of PDUs from network node to network node.

0011[ 0005] Multicast forwarding of data packets (w here packets are sent from a source node to multiple destination nodes more or less simultaneously) is of increasing importance as demand for services such as Internet Protocol Television (IPTV) and Video on Demand (VoD) grows.

0012[ 0006 ] Protocols such as Intermediate System - Intermediate System (IS-IS) and Open Shortest Path First (OSPF) and Multicast OSPF are used to distribute topology information to permit distributed calculation of paths that interconnect multiple nodes, resulting in the installation of the forw arding state required to implement those paths OSPF and IS-IS are run in a distributed manner across nodes of the netw ork so that, for example, when a topolog} change occurs in the netw ork such as a node or link failure, this information is flooded to all nodes b} the protocol's operation, and each node will localh recompute paths to circumv ent the failure based on a consistent \ lew of the netw ork topolog}

0013[ 0007 ] In Ethernet netw orks, Pro\ ider Backbone Transport (PBT), also known as Pro\ ider Back-Bone Bridging- Traffic Engineering (PBB-TE), as described in Applicant^'s British patent number GB 2422508 is used to pro\ide a unicast Ethernet transport technology Pro\ ider Link State Bridging (PLSB) as described in Applicant's co-pending United States patent application serial number 11/537,775 will be used to pro\ide a multicast transport capability for Ethernet netw orks using IS-IS to set up both unicast paths and multicast trees in the netw ork Both abo\ e patent documents are hereb} incorporated b} reference

0014[ 0008] While the present inv ention is not limited to the application of a routing sy stem to Ethernet bridging, Ethernet terminology is used in this disclosure where possible So, for example, the term filtering database (FDB) can be considered interchangeable with an} term for an information repositon of packet forw arding information, such as forw arding information base or label information base

0015[ 0009 ] T^ picalh , multicast trees in a PLSB netw ork are computed using an all-pairs shortest path multicast route computation algorithm known, for example, from Applicant^'s co-pending U S Patent Application Publication No 20070165657 In accordance with this method, when a node recerv es either a multicast group membership change or a netw ork topolog} change (for example \ia a Link State Protocol Data Unit - LSP) the node emplo} s algorithms such as Di)kstra's algorithm to compute both unicast connectπ itΛ and the set of pairs of netw ork nodes that are connected b} a shortest path which tra\ erses the computing node For that set of node pairs, the node determines where intersections of multicast group membership occur, and defines the required FDB entries to instantiate its portion of multicast paths accordingly Both Unicast and Multicast forw arding state implementing the computed paths is then installed in the node^'s filtering database (FDB), so that receπ ed packets can be forw arded to the appropriate output port(s) of the node, based on the destination address in the frame [ 0010] As ma} be appreciated, identify ing pairs of nodes for w Inch the respectπ e shortest path trav erses a particular node is computational!} lntensπ e, because it im oh es examining the paths extending from each node to e\ en other node In some cases, the challenge of performing the required computations within an acceptable period of time can impose limitations on the size of the netw ork Clearh , more pow erful processors can be used to increase the speed of computation, but onh b} increasing the cost of each node, which ma} be undesirable

0016[ 0011] Techniques for impro\ ing the efficienc} of multicast route computation in packet switched networks remain highh desirable

SUMMARY OF THE INVENTION

0018[ 0012 ] Thus, an aspect of the present im ention pro\ides a method of multicast route computation in a link state protocol controlled netw ork A spanning tree is computed from a first node to e\ en other node in the netw ork using a known spanning tree protocol The netw ork is then druded into tw o or more partitions, each partition encompassing an immediate neighbour node of the first node and an} nodes of the netw ork subtending the neighbour node on the spanning tree Tw o or more of the partitions are merged w hen a predetermined criterion is satisfied Nodes within all of the partitions except a largest one of the partitions are then identified, and each identified node is examined to ldentif} node pairs for which a respectπ e shortest path tra\ erses the first node

BRIEF DESCRIPTION OF THE DRAWINGS

0020[ 0013 ] Further features and ad\ antages of the present im ention will become apparent from the following detailed description, taken in combination with the appended drawings, in w hich

0021[ 0014 ] FIG 1 is a flow chart illustrating principle steps in a method according to a representatπ e embodiment of the present in\ ention.

0022[ 0015] FIGs 2a-e illustrate steps in the process of FIG 1 implemented in a representatπ e netw ork [ 0016 ] It will be noted that throughout the appended drawings, like features are identified by like reference numerals.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT

0024[ 0017 ] The present invention provides a PLSB computation method in which the number of nodes that must be examined, in order to find all of the node pairs for which the respective shortest path traverses a given node, is minimized. In some cases, the number of nodes that must be examined can be reduced to zero. Embodiments of the invention are described below, by w ay of example only, with reference to FIGs. l-2e.

0025[ 0018] As an initial matter, it should be noted that the method of the present invention is valid for networks in which computed shortest paths are symmetric (that is, the network can be represented as an undirected graph) and. if two or more equal-cost paths can be computed between any IΛYO nodes, a tie-breaking method must be implemented which w ill select one of the equal-cost paths in such a way that the selected "shortest^" paths are symmetric and locally consistent. In this respect, "locally consistent^" means that any sub-path of the equal- cost path selected by the tie-breaking method must itself be a shortest path selected by the tie-breaking method. A representative tie-breaking method, which may be used in conjunction with the methods of the present invention, is known from Applicant^'s co- pending United States Patent Application No. 11/964,478, which w as filed on December 26, 2007.

0026[ 0019 ] FIG. 1 is a flow chart illustrating principle steps in a method according to a representative embodiment of the present invention, and FIGs. 2a-e illustrate steps in the process of FIG. 1 implemented in a representative network.

0027[ 0020] Referring first to FIG. 2a, a representative PLSB network comprises a plurality of nodes (labelled as nodes A-R) interconnected by links. As is ty pical in a PLSB network, even node in the network of FIGs. 2a-e is connected to at least IΛYO other nodes, although this is not essential. Preferably, the method of the present invention w ill be implemented to execute in even node, substantially in parallel. In the following description, the method is described by w ay of an example in which shortest paths traversing node "A^" are identified. [ 0021] Referring now to FIGs. 1 and 2b, at a first step, a spanning tree from node "A^" to even other node in the network is computed, for example using a known shortest path tree algorithm such as Dijkstra s algorithm. As may be seen in FIG. 2b, the spanning tree (indicated by bold lines in FIGs. 2b-e) comprises a plurality of branches extending from node "A^" to each of its immediate neighbours (nodes B, C, D and E). By construction, all of the nodes of the network are on one of these branches. Thus it is possible to notionally divide the network into a set of partitions, each of which encompasses a respective branch of the spanning tree.

0028[ 0022 ] By construction, each partition will therefore include a respective one of the neighbour nodes, and all of the nodes that subtend that neighbour node on the spanning tree. For convenience of description, each branch/partition may be referenced using the identifier of the respective neighbour node which serv es as the root of that branch. Thus, in FIG. 2c, the four partitions are identified as partitions "B^", "C^", "D^" and "E^", following the identity of their respective root nodes.

0029[ 0023 ] As may be seen from FIG. 2c, any shortest path that traverses node "A^" must necessarily originate in one partition and terminate in a second partition. Because of path symmetry between node pairs, the number of nodes that need to be examined, in order to find all of the node pairs for which the respective shortest path traverses node "A^", can be reduced by considering the nodes in all but one of the partitions. The benefits of this reduction can be maximized by recognising that the largest partition, in terms of the number of member nodes, can be selected as the omitted partition, so that only paths terminating at nodes in the remaining smaller partitions are considered.

0030[ 0024 ] A further reduction in the number of nodes that must be examined can be obtained by recognising that the shortest path between any node in one partition and any node in any other partition will not traverse node "A^" if, and only if, there is a path between the respective root nodes of the involved partitions that is shorter than the two-hop path through node "A^". For example, consider a path between nodes M and R in the embodiment of FIG. 2, which are respectively located in partitions "D^" and "E^". In this example we will only consider number of hops as the shortest path criterion although other criteria are equally applicable. Inspection of the network reveals that the root nodes "D^" and "E^" are directly connected by a link. Consequently, the shortest path between nodes M and R traverses only root nodes "D^" and "E^", and does not traverse node "A^". Consideration of the other nodes in partitions "D^" and "E^" reveals that, w hile not all of the shortest paths (between a node in partition "D^" and a node in partition "E^") traverse the direct link between root nodes "D^" and "E^", the presence of that direct link guarantees that none of these shortest paths w ill traverse node "A^". Accordingly, partitions "D^" and "E^" can be merged into a single super- partition "DE^" for the purpose of the computations at "A^".

0031[ 0025] This process of identifying shorter paths between pairs of root nodes in the pair of partitions or super-partitions under consideration, and merging partitions whenever a sufficient number of shorter paths is found, can be repeated until either: all of the partitions have been merged into a one super-partition (which in fact encompasses the entire network except node "A^"); or there are no more pairs of partitions for which all the root nodes are interconnected by paths that are shorter than the two-hop paths through node "A^". Whether two partitions can be merged can be determined by considering the root nodes in the proposed merged partition. In the simple case of a pair of partitions each having a single root node, the two partitions can be merged if, and only if, the respective root nodes of the two partitions are connected by a shorter path than the two-hop path through node "A^". For the more complex case of a partition having one root node and a super-partition having N (where N>1) root nodes, the IΛYO partitions can be merged together if none of the shortest paths beiΛYeen the root node of the partition and the N root nodes of the super-partition go throu -'gt>h^L node "A^".

0032[ 0026 ] Thus, continuing the example at FIG. 2d, and continuing to use the number of hops as shortest path criteria, the partition "B^" can be merged with super-partition "DE^" (having N=2 root nodes) to produce super-partition "BDE^", because root node "B^" is directly connected to the IΛYO root nodes of super-partition "DE^". This guarantees that there is no shortest path betw een any pair of nodes in super-partition "BDE^" w hich traverses node "A^". On the other hand, and referring to FIG. 2e, partition "C^" can not be merged with super partition "BDE^", because there is no direct link beiΛYeen root node "C^" and root node E of the super partition "BDE^". In fact, partition "C^" could not be merged with partition "E^" or any super-partition including partition "E^".

0033[ 0027 ] As may be seen in FIG. 2e, completion of the above process of merging partitions results in the neiΛYork being divided into IΛYO partitions, namely partition "C^" and super partition "BDE^". As noted above, all of the shortest paths of interest can be found by examining the nodes within each partition except the largest partition. In the case of FIG. 2e, all of the shortest paths that traverse node "A^" can be discovered by examining node "C^" to identity each shortest path extending from node "C^" which traverses node "A^". As will be appreciated, this dramatically reduces the PLSB computation required for the network in this example, since paths extending from only one node (as opposed to 17 nodes using conventional methods) must be considered.

0034[ 0028] It will be understood that the benefits obtained by merging partitions is dependent on the network topology. In a scenario in which all partitions can be merged into a single super-partition, which therefore encompasses the entire network, then the number of nodes that must be examined is zero (after the initial overhead of the partitioning step). In a more typical scenario, the process of merging partitions w ill result in a plurality of partitions and/or super-partitions. In the special case in which node "A^" is a dual-connected edge node, the initial number of partitions is two. If these two partitions can be merged successfully, the number of nodes that must be subsequently examined is reduced to zero. Otherwise, in the worst case, the number of nodes that must be examined is slightly less than half the number of nodes in the network, which is still a substantial improvement over conventional methods.

0035[ 0029 ] As is known in the art, route computation methods such as Intermediate System - Intermediate System (IS-IS) and Open Shortest Path First (OSPF) and Multicast OSPF can produce multiple equal-cost paths between node pairs. In such cases, the above-described method for merging partitions may be used without modification where either: the "cost^" of each path is proportional to the number of hops; or the "cost^" of a direct link between two partitions is less than the "cost^" of the two-hop path through the node of interest (node "A^" in the example of FIG. 2).

0036[ 0030] A tie-breaking algorithm must be used to select a "shortest^" path or subset of shortest paths from among the set of equal-cost paths between a node pair. In such cases, the above-described method for merging partitions can be used, provided that the "shortest^" path(s) selected by the tie-breaking algorithm are symmetric and locally consistent.

0037[ 0031] For example, in the network of FIG. 2. consider a scenario in which the route computation methods yields three equal cost paths between nodes C and E, and a tie- breaking algorithm is used to select one of these equal-cost paths as the "shortest^" path. In this case, the above-described methods could be used to merge partition "C^" with super- partition "BDE^" if the tie-breaking method selected, as the shortest path, either one of the two paths through nodes B or D, but not the path through node "A^".

0038[ 0032 ] As may be appreciated, this same methodology can be extended to a case w here the route computation algorithm computes a set of equal-cost paths, and the tie breaking mechanism operates to select a subset of IΛYO or more of these equal cost paths as the shortest paths. In this case, the criterion for merging IΛYO partitions is that none of the selected shortest paths traverse the node under consideration. Thus, for example, the tie-breaking mechanism could potentially select any IΛYO of the paths betw een nodes C and E as the set of shortest paths, and the above-described methods could be used to merge partition "C^" with super-partition "BDE^" if this set of shortest paths did not include the path through node "A^".

0039[ 0033 ] The embodiment(s) of the invention described above is(are) intended to be exemplar} only. The scope of the invention is therefore intended to be limited solely by the scope of the appended claims.