# US 2018/0026870 A1 · Distributed constrained tree formation for deterministic multicast

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2018/0026870 A1
- Document ID: US20180026870A1
- Status: Published application
- Kind: A1
- Application number: 15/216,007
- Filed: 2016-07-21
- Published: 2018-01-25
- Earliest claimed: 2016-07-21
- Assignees: Cisco Technology, Inc.
- Applicants: Cisco Technology, Inc.
- Inventors: Pascal Thubert; IJsbrand Wijnands; Patrick Wetterwald; Eric Levy-Abegnoli; Jean-Philippe Vasseur
- Web page: https://patentgrep.com/patent/US20180026870A1

## CPC

- H04L 45/02: Topology update or discovery
- H04L 45/121: by minimising delays
- H04L 45/26: {Route discovery packet}
- H04L 45/32: {Flooding (denial of service attacks H04L63/1458)}
- H04L 45/48: Routing tree calculation
- H04L 65/611: for multicast or broadcast (systems for broadcast or conference H04L12/18; arrangements for broadcast or distribution combined with broadcast H04H20/00; arrangements for broadcast applications with a direct linkage to broadcast information or to broadcast space-time H04H60/00; selective distribution of broadcast services, e.g. multimedia broadcast multicast service [MBMS], H04W4/06)
- H04L 45/302: Route determination based on requested QoS
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## Abstract

In one embodiment, a multicast listener device floods a path lookup request to search for a multicast tree, and may then receive path lookup responses from candidate nodes on the multicast tree, where each of the path lookup responses indicates a unicast routing cost from a respective candidate node to the multicast listener device, and where each of the candidate nodes is configured to suppress a path lookup response if a total path latency from a source of the multicast tree to the multicast listener device via that respective candidate node is greater than a maximum allowable path latency. The multicast listener device may then select a particular candidate node as a join point for the multicast tree based on the particular node having a lowest associated unicast routing cost to the multicast listener device from among the candidate nodes, and joins the multicast tree at the selected join point.

## Claims

### Claim 1

A method, comprising:
flooding, from a multicast listener device in a network, a path lookup request into the network to search for nodes on a multicast tree;
receiving, at the multicast listener device, one or more path lookup responses from one or more candidate nodes on the multicast tree, wherein each of the one or more path lookup responses indicates a unicast routing cost from a respective candidate node to the multicast listener device, and wherein each of the one or more candidate nodes is configured to suppress a path lookup response if a total path latency from a source of the multicast tree to the multicast listener device via that respective candidate node is greater than a maximum allowable path latency;
selecting, by the multicast listener device, a particular node of the one or more candidate nodes as a join point for the multicast tree based on the particular node having a lowest associated unicast routing cost to the multicast listener device from among the one or more candidate nodes; and
joining, by the multicast listener device, the multicast tree at the selected join point.

### Claim 2 (depends on 1)

The method as in claim 1, wherein the path lookup request is configured to aggregate and carry return path latency and unicast routing cost along each flooding path while searching for nodes on the multicast tree.

### Claim 3 (depends on 1)

The method as in claim 1, wherein the path lookup request is associated with one or more constraints, and wherein nodes within the network are configured to prevent flooding of the path lookup request on links that do not meet the one or more constraints.

### Claim 4 (depends on 3)

The method as in claim 3, wherein one of the one or more constraints is a minimum available link bandwidth.

### Claim 5 (depends on 1)

The method as in claim 1, wherein the path lookup request is associated with a maximum range, and wherein nodes within the network are configured to prevent flooding of the path lookup request beyond the maximum range.

### Claim 6 (depends on 5)

The method as in claim 5, wherein the maximum range is selected from a group consisting of: the maximum allowable latency; a bounded latency before reaching the multicast tree; a maximum unicast routing cost before reaching the multicast tree; and a maximum hop count before reaching the multicast tree.

### Claim 7 (depends on 5)

The method as in claim 5, further comprising:
retrying the path lookup request with a larger maximum range in the event of a failure to reach the multicast tree.

### Claim 8

A method, comprising:
receiving, at a node in a network, a path lookup request flooded into the network from a multicast listener device to search for nodes on a multicast tree;
determining, by the node, if the node is on the multicast tree;
in response to determining, by the node, that the node is on the multicast tree:
determining a total path latency from a source of the multicast tree to the multicast listener device via the node;
in response to determining, by the node, that the total path latency is less than or equal to a maximum allowable path latency:
determining a unicast routing cost from the candidate node to the multicast listener device; and
returning a path lookup response as a candidate node on the multicast tree, wherein the path lookup response indicates the unicast routing cost, the path lookup response causing the multicast listener device to select a particular node of one or more candidate nodes as a join point for the multicast tree based on the associated unicast routing cost to the multicast listener device from among the one or more candidate nodes; and
in response to determining, by the node, that the total path latency is greater than the maximum allowable path latency, suppressing the path lookup response.

### Claim 9 (depends on 8)

The method as in claim 8, further comprising:
in response to determining, by the node, that the node is not on the multicast tree, flooding the path lookup request further into the network.

### Claim 10 (depends on 9)

The method as in claim 9, wherein the path lookup request is associated with one or more constraints, the method further comprising:
preventing flooding of the path lookup request on links that do not meet the one or more constraints.

### Claim 11 (depends on 10)

The method as in claim 10, wherein one of the one or more constraints is a minimum available link bandwidth.

### Claim 12 (depends on 9)

The method as in claim 9, wherein the path lookup request is associated with a maximum range, the method further comprising:
preventing flooding of the path lookup request beyond the maximum range.

### Claim 13 (depends on 12)

The method as in claim 12, wherein the maximum range is selected from a group consisting of: the maximum allowable latency; a bounded latency before reaching the multicast tree; a maximum unicast routing cost before reaching the multicast tree; and a maximum hop count before reaching the multicast tree.

### Claim 14 (depends on 8)

The method as in claim 8, wherein the path lookup request is configured to aggregate and carry return path latency and unicast routing cost along each flooding path while searching for nodes on the multicast tree.

### Claim 15

An apparatus, comprising:
one or more network interfaces to communicate within a network as a multicast listener device;
a processor coupled to the network interfaces and adapted to execute one or more processes; and
a memory configured to store a process executable by the processor, the process when executed operable to:
flood a path lookup request into the network to search for nodes on a multicast tree;
receive one or more path lookup responses from one or more candidate nodes on the multicast tree, wherein each of the one or more path lookup responses indicates a unicast routing cost from a respective candidate node to the multicast listener device, and wherein each of the one or more candidate nodes is configured to suppress a path lookup response if a total path latency from a source of the multicast tree to the multicast listener device via that respective candidate node is greater than a maximum allowable path latency;
select a particular node of the one or more candidate nodes as a join point for the multicast tree based on the particular node having a lowest associated unicast routing cost to the multicast listener device from among the one or more candidate nodes; and
join the multicast tree at the selected join point.

### Claim 16 (depends on 15)

The apparatus as in claim 15, wherein the path lookup request is configured to aggregate and carry return path latency and unicast routing cost along each flooding path while searching for nodes on the multicast tree.

### Claim 17 (depends on 15)

The apparatus as in claim 15, wherein the path lookup request is associated with one or more constraints, and wherein nodes within the network are configured to prevent flooding of the path lookup request on links that do not meet the one or more constraints.

### Claim 18 (depends on 15)

The apparatus as in claim 15, wherein the path lookup request is associated with a maximum range, and wherein nodes within the network are configured to prevent flooding of the path lookup request beyond the maximum range.

### Claim 19

An apparatus, comprising:
one or more network interfaces to communicate within a network;
a processor coupled to the network interfaces and adapted to execute one or more processes; and
a memory configured to store a process executable by the processor, the process when executed operable to:
receive a path lookup request flooded into the network from a multicast listener device to search for nodes on a multicast tree;
determine if the apparatus is a node on the multicast tree; and
in response to determining that the node is on the multicast tree:
determine a total path latency from a source of the multicast tree to the multicast listener device via the node;
determine a unicast routing cost from the candidate node to the multicast listener device in response to the total path latency being less than or equal to a maximum allowable path latency;
return a path lookup response as a candidate node on the multicast tree in response to the total path latency being less than or equal to the maximum allowable path latency, wherein the path lookup response indicates the unicast routing cost, the path lookup response causing the multicast listener device to select a particular node of one or more candidate nodes as a join point for the multicast tree based on the associated unicast routing cost to the multicast listener device from among the one or more candidate nodes; and
suppress the path lookup response in response to the total path latency being greater than the maximum allowable path latency.

### Claim 20 (depends on 19)

The apparatus as in claim 19, wherein the process when executed is further operable to:
flood the path lookup request further into the network in response to determining that the node is not on the multicast tree.
