US Patent No. 9,270,426

CONSTRAINED MAXIMALLY REDUNDANT TREES FOR POINT-TO-MULTIPOINT LSPS


Patent No. 9,270,426
Issue Date February 23, 2016
Title Constrained Maximally Redundant Trees For Point-to-multipoint Lsps
Inventorship Alia Atlas, Arlington, MA (US)
Maciek Konstantynowicz, Haddenham (GB)
Assignee Juniper Networks, Inc., Sunnyvale, CA (US)

Claim of US Patent No. 9,270,426

15. A network device comprising:
a processor;
a constrained maximally redundant tree module configured for execution by the processor to calculate a plurality of maximally
redundant trees from the network device to a plurality of egress network devices based on a network graph, in which each of
the plurality of maximally redundant trees comprises a spanning tree to the plurality of egress network devices rooted at
the network device, wherein each of the maximally redundant trees is calculated to comprise a point to multipoint (P2MP) path
from the network device to the plurality of egress network devices that is as disjoint as possible from a respective P2MP
path from the network device to the plurality of egress network devices for each other one of the plurality of maximally redundant
trees, and wherein the maximally redundant trees are calculated such that each link along each of the plurality of maximally
redundant trees satisfies a specified traffic-engineering constraint,

wherein the constrained maximally redundant tree module is configured to, in response to determining that the plurality of
maximally redundant trees includes at least one node whose removal partitions a network represented by the network graph:

modify the specified traffic-engineering constraint to have a less restrictive value;
modify the network graph to add links to the network graph that satisfy the modified traffic-engineering constraint to obtain
a modified network graph; and

re-calculate at least a portion of the plurality of maximally redundant trees based on the modified network graph to obtain
a plurality of maximally redundant trees in which at least two nodes must be removed before the network is partitioned; and

a resource reservation protocol module configured for execution by the processor to establish a plurality of P2MP label switched
paths (LSPs) from the network device as an ingress network device to the plurality of egress network devices along each of
the plurality of maximally redundant trees in which at least two nodes must be removed before the network is partitioned,
wherein each of the P2MP LSPs corresponds to a different one of the plurality of maximally redundant trees in which at least
two nodes must be removed before the network is partitioned.