التفاصيل البيبلوغرافية
| العنوان: |
Utilizing Betweenness to Determine Forwarding State in a Routed Network |
| Document Number: |
20120033552 |
| تاريخ النشر: |
February 9, 2012 |
| Appl. No: |
13/250034 |
| Application Filed: |
September 30, 2011 |
| مستخلص: |
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. |
| Inventors: |
Dasylva, Abel (Gatineau, CA); Montuno, Delfin (Kanata, CA); Ashwood Smith, Peter (Gatineau, CA); Blouin, Francois (Gatineau, CA); Drwiega, Tadeusz (Kanata, CA) |
| Claim: |
1-24. (canceled) |
| Claim: |
25. A non-transitory tangible computer readable storage medium having stored thereon a program for utilizing betweenness to determine forwarding state in a routed network, the program comprising a set of instructions which, when executed by a processor on a network element, cause the network element to perform a method comprising the steps of: 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 a 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 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. |
| Claim: |
26. The non-transitory tangible computer readable storage medium of claim 25, wherein 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. |
| Claim: |
27. The non-transitory tangible computer readable storage medium of claim 26, 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. |
| Claim: |
28. The non-transitory tangible computer readable storage medium of claim 25, 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. |
| Claim: |
29. The non-transitory tangible computer readable storage medium of claim 28, 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. |
| Claim: |
30. The non-transitory tangible computer readable storage medium of claim 25, 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. |
| Claim: |
31. The non-transitory tangible computer readable storage medium of claim 25, wherein the critical nodes are selected administratively and advertised on the network. |
| Claim: |
32. The non-transitory tangible computer readable storage medium of claim 25, 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. |
| Claim: |
33. The non-transitory tangible computer readable storage medium of claim 25, wherein the set of critical nodes are self-selected by the nodes on the network. |
| Claim: |
34. The non-transitory tangible computer readable storage medium of claim 25, wherein the set of critical nodes is a subset of the nodes on the network. |
| Claim: |
35. The non-transitory tangible computer readable storage medium of claim 34, wherein the set of critical nodes is less than 10% of the nodes on the network. |
| Claim: |
36. The non-transitory tangible computer readable storage medium of claim 25, wherein the shortest path is based on a cost metric selected from cost, capacity, availability, and reliability. |
| Claim: |
37. The non-transitory tangible computer readable storage medium of claim 36, wherein the shortest path calculation uses link weights that are directionally dependent. |
| Claim: |
38. The non-transitory tangible computer readable storage medium of claim 25, wherein installing forwarding state for the multicast causes duplicate forwarding state to be installed on the network. |
| Claim: |
39. The non-transitory tangible computer readable storage medium of claim 38, further comprising the step of pruning the duplicate forwarding state from the network. |
| Claim: |
40. The non-transitory tangible computer readable storage medium of claim 25, wherein the step of installing forwarding state for the multicast is performed 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. |
| Claim: |
41. The non-transitory tangible computer readable storage medium of claim 25, wherein the node is a critical node. |
| Claim: |
42. The non-transitory tangible computer readable storage medium of claim 25, wherein the node is an intermediate node other than a critical node. |
| Claim: |
43. A network element, comprising: a filtering database; a forwarding function configured to use information from the filtering database to make forwarding decisions for packets of data; and a routing function configured to calculate shortest path trees through the network and install forward state in the filtering database; and a betweenness function configured to: determine a cost of a shortest path from a multicast source to a multicast destination that passes through the network element; determine 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 instruct the routing process to install forwarding state into the filtering database for the multicast, only if the cost of the shortest path from the multicast source to the multicast destination that passes through the network element 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. |
| Current U.S. Class: |
370/230 |
| Current International Class: |
04 |
| رقم الانضمام: |
edspap.20120033552 |
| قاعدة البيانات: |
USPTO Patent Applications |