Utilizing Betweenness to Determine Forwarding State in a Routed Network
First Claim
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 paths 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.
8 Assignments
0 Petitions
Accused Products
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.
31 Citations
24 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 paths 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18)
-
-
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. - View Dependent Claims (20, 21, 22, 23, 24)
Specification