Cisco Technology, Inc.

Stefano Novello

Jean-Philippe Vasseur

Steve Y Chiu

Stefano Benedetto Previdi

Eric Osborne

Helmut Matthias Simonis

Hani El-Sakkout

Vassilios Liatsos

Vassilis Liatsos

Josh Singer

In one embodiment, a target bandwidth, a lower bandwidth boundary constraint, and an upper cost boundary constraint for a constrained path are configured. A set of paths are computed that have bandwidth within the lower bandwidth boundary constraint and cost within the upper cost boundary constraint. A determination is made whether one or more paths of the set of paths has bandwidth that provides at least the target bandwidth and, if so, a path from the one or more paths of the set of paths having bandwidth that provides at least the target bandwidth is selected to use as the constrained path, and, if not, a path from the one or more paths of the set having bandwidth that does not provide at least the target bandwidth that has bandwidth closest to the target bandwidth is selected to use as the constrained path.

Relaxed constrained shortest path first (R-CSPF)

In one embodiment, a tunnel mesh probe, initiated for a computer network having a tunnel mesh, may be received at a first tail-end node of a probed tunnel. In response, the first tail-end node processes the probe, and forwards the probe to another tail-end node of a non-probed tunnel selected from a plurality of tunnels of the tunnel mesh for which the first tail-end node is a head-end node. Illustratively, once the probe is received at its initiating node, and in response to determining that the initiating node is a head-end node for only probed tunnels, the tunnel mesh probe is completed, having probed all tunnels of the tunnel mesh.

OAM tools for meshed tunnels in a computer network

A method of determining traffic paths between one or more source-destination node pairs in a communications network, comprising starting from a first set of paths between said source-destination node pairs, determining a second set of paths between said source-destination node pairs while taking into account a set of constraints, such that said second set of paths emulates said first set of paths.

Traffic flow determination in communications networks

In one embodiment, a routing node (e.g., a head-end node) determines a desire to route a selected tunnel (e.g., reroute), and computes a path for the selected tunnel. The routing node probes the path to discover information about tunnels that would be displaced by the selected tunnel if routed over the path (e.g., a number of tunnels), and correspondingly determines whether to establish the selected tunnel based on the information about the tunnels to be displaced. In another embodiment, intermediate nodes along the probed path of the selected tunnel may receive a probe (e.g., signaling message) requesting information about the tunnels that would be displaced by the selected tunnel. In response, each intermediate node inserts the information about the tunnels to be displaced at the intermediate node into the probe, and forwards the probe (e.g., toward the routing node initiating the probe).

Probing-based mechanism to reduce preemption perturbation caused by higher priority tunnel establishment in a computer network

In an example embodiment, a multicast tree is accessed. The multicast tree defines one or more destination label switch routers and paths from a source label switch router to the destination label switch routers. Multicast addresses are then transmitted to the destination label switch routers. In an example embodiment, upon receipt of the multicast addresses, a request to update the multicast tree is transmitted. The request includes the identifier of the label switch router that originated the request.

Dynamic update of a multicast tree

In one embodiment, a target bandwidth, a lower boundary constraint on bandwidth, and an upper boundary constraint on cost are configured on a path computation device. The device may then compute a set of paths that is within the lower bandwidth boundary and upper cost boundary constraints. If the set of paths contains one or more paths, the device may select a path having a bandwidth value that is closest to the target bandwidth. However if the set of paths contains no paths, the device may search amongst paths that violate either the maximum cost or minimum bandwidth limits, selecting the path closest to the violated constraint (e.g., whose combined violation is minimized). Also, a weighting factor may be configured to establish the relative importance for a cost violation in comparison to a bandwidth violation.

In one embodiment, distributed path computation elements (PCEs) collaboratively build local portions of an inter-domain P2MP path to each path destination or to each ingress border router of one or more respective successor domains based on a cost associated with using one or more local ingress border routers received from each predecessor domain. Once a furthest destination is reached, each PCE may recursively return a list of local ingress border routers used in the P2MP path to each predecessor domain, where each PCE receiving the list correspondingly prunes segments of its computed local portion of the P2MP path that lead to unused successor ingress border routers, and sends a prune message to its predecessor domains accordingly. A root PCE receives the final prune message(s) and a representation of each locally computed portion of the inter-domain P2MP path, and combines the portions into a final inter-domain P2MP path.

Inter-domain point-to-multipoint path computation in a computer network

There is provided a traffic placement method in a communications network, the communications network comprising a plurality of nodes, the nodes being connected to one another by links, the method comprising selecting a (possibly non-strict) subset from a given set of traffic flow demands and calculating a plurality of paths for the selected demands under consideration of a set of constraints using an algorithm hybridization combining backtrack search with local consistency techniques (BT+CS) and guiding search by the use of one or more probe generators, that is, search techniques that solve a routing sub-problem or an arbitrary relaxation of the traffic placement problem. By using a hybrid algorithm that integrates other solvers (search techniques) into BT+CS through the use of probe generators, a more powerful search strategy can be achieved compared to BT+CS or the individual search techniques.

Data networking

A method, apparatus and computer program product for determining a preferred backup path to protect a point-to-multipoint label switching path is presented. A point-to-multipoint backup path is computed for each node located upstream from a branching node, the backup path originating at the node and including a set of nodes downstream from said branching node. A cost metric associated with each backup path is determined, as is a distance metric associated with each backup path. From the cost and distance metrics associated with each backup path a preferred backup path is selected using a distributed algorithm.

Growing community of inventors

Concord, MA, United States of America

Stefano Novello