Utilizing betweenness to determine forwarding state in a routed network

• US 8,040,906 B2
• Filed: 06/23/2009
• Issued: 10/18/2011
• Est. Priority Date: 06/23/2009
• Status: Expired due to Fees

• Current Assignee: RPX Clearinghouse LLC (RPX Corporation)
• Original Assignee: Nortel Networks Limited (Nortel Networks Corporation)
• Inventors: Drwiega, Tadeusz, Blouin, Francois, Ashwood Smith, Peter, Montuno, Delfin, Dasylva, Abel
• Primary Examiner(s): HO, DUC CHI
• Application Number:
  US12/490,187
• Publication Number:
  US 20100322244A1
• Time in Patent Office: 847 Days
• Field of Search: None
• US Class Current: 370/401
• CPC Class Codes: H04L 12/185 with management of multicast group membership
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/03 by updating link state protocols
• CPC Class Codes: H04L 45/12 Shortest path evaluation
• CPC Class Codes: H04L 45/122 by minimising distances, e.g. by selecting a route with minimum of number of hops
• CPC Class Codes: H04L 45/16 Multipoint routing
• CPC Class Codes: H04L 45/48 Routing tree calculation

Abstract

A set of critical nodes or links is identified on the network through which most of the shortest paths on the network occur. Each node compares their distance to end points on the network with a distance between the end points and each of the distinct critical nodes. Where the distance between the end points and the critical nodes is shorter than the distance between the end points and the node, the node is not on the shortest path and does not install forwarding state. Where the distance between the end points and the critical node is larger than or equal to the distance between the end points and the node, the node may be on the shortest path between the pair of end nodes and installs forwarding state. Installation of forwarding state may cause packet duplication, but determining forwarding state is dramatically simplified. The level of duplication may be reduced by selecting a larger number of critical nodes on the network.

Claims

1. A method of installing multicast forwarding state at a node of a routed network, the method comprising the steps of:

receiving, by the node, a link state advertisement containing an indication that a multicast destination would like to join a multicast;

determining a cost of a shortest path from a multicast source to the multicast destination that passes through the node;

determining costs of critical shortest paths from the multicast source to the multicast destination that pass through critical nodes on the network to look for a shorter critical shortest path through the network; and

installing forwarding state for the multicast, by the node, only if the cost of the shortest path from the multicast source to the multicast destination that passes through the node is less than or equal to the shortest critical shortest path through the network between the multicast source and multicast destination via one of the critical nodes.

2. The method of claim 1, wherein the step of determining the cost of the path from the multicast source to the multicast destination comprises determining a first cost of a first path from the node to the multicast source, determining a second cost of a second path from the node to the multicast destination, and summing the first cost of the first path with the second cost of the second path.

3. The method of claim 2, further comprising the step of pre-computing a shortest path tree from the node to each other node on the network, and using the pre-computed shortest path tree to determine the first cost of the first path and the second cost of the second path.

4. The method of claim 1, wherein the step of determining costs of paths from the multicast source to the multicast destination that pass through critical nodes on the network comprises determining, for each such critical node, a first cost of a first path from the critical node to the multicast source, determining a second cost of a second path from the critical node to the multicast destination, and summing the first cost of the first path with the second cost of the second path to determine the critical shortest path for that critical node.

5. The method of claim 4, further comprising the step of pre-computing and storing shortest path trees from each critical node to each other node on the network, and using the pre-computed shortest path trees to determine the first cost of the first path and the second cost of the second path for each critical node.

6. The method of claim 1, wherein the step of determining costs of critical shortest paths between the multicast source and multicast destination that pass through critical nodes on the network is terminated once the node has found a critical shortest path that is shorter than its path between the multicast source and multicast destination.

7. The method of claim 1, wherein the critical nodes are selected administratively and advertised on the network.

8. The method of claim 1, wherein the critical nodes are selected to be a small number of nodes that handles a large percentage of shortest paths between pairs of nodes on the network.

9. The method of claim 1, wherein the set of critical nodes are self-selected by the nodes on the network.

10. The method of claim 1, wherein the set of critical nodes is a subset of the nodes on the network.

11. The method of claim 10, wherein the set of critical nodes is less than 10% of the nodes on the network.

12. The method of claim 1, wherein the shortest path is based on a cost metric selected from cost, capacity, availability, and reliability.

13. The method of claim 12, wherein the shortest path calculation uses link weights that are directionally dependent.

14. The method of claim 1, wherein installing forwarding state for the multicast, by the node, only if the cost of the shortest path from the multicast source to the multicast destination that passes through the node is less than or equal to the shortest critical shortest path through the network between the multicast source and multicast destination via one of the critical nodes causes duplicate forwarding state to be installed on the network.

15. The method of claim 14, further comprising the step of pruning the duplicate forwarding state from the network.

16. The method of claim 1, wherein the step of installing forwarding state for the multicast is performed, by the node, only if the cost of the shortest path from the multicast source to the multicast destination that passes through the node is less than or equal to the shortest critical shortest path through one of the critical nodes.

17. The method of claim 1, wherein the node is a critical node.

18. The method of claim 1, wherein the node is an intermediate node other than a critical node.

19. A routed network, comprising

a plurality of nodes interconnected by links, each of the nodes running a link state routing protocol to enable shortest path forwarding to be implemented on the network, a first set of the plurality of nodes being designated as critical nodes and a remainder of the plurality of nodes being non-critical nodes;

each of the nodes being configured to install forwarding state for a source/destination pair by comparing its betweenness for the source/destination pair with a betweenness for the source/destination pair of each of the critical nodes.

20. The network of claim 19, wherein the critical nodes are selected by looking for nodes on the routed network that are on shortest paths between the most source/destination pairs.

21. The network of claim 19, wherein a number of critical nodes is selected to minimize both computational complexity and traffic duplication.

22. The network of claim 19, wherein betweenness for a node is calculated by looking at a path distance between the source/destination pair that passes through the node.

23. The network of claim 19, wherein the forwarding state is multicast forwarding state.

24. The network of claim 19, wherein the network will install at least one forwarding path between each source/destination pair in connection with implementation of a betweenness calculation for the source/destination pair.