Constraint-based underlay tree allocation for data centers

Patent metadata

Field	Value
Publication number	US-12476899-B2
Application number	US-202217858215-A
Country	US
Kind code	B2
Filing date	Jul 6, 2022
Priority date	Oct 25, 2021
Publication date	Nov 18, 2025
Grant date	Nov 18, 2025

Abstract

In an example method, a head node connected to a source device transmits a multicast data flow from the source device to receiving devices connected to tail nodes using Default MDT. The example method further includes determining that requirements have been met to begin transmitting the multicast data flow using Data MDT. The method may further include determining whether the tail nodes are able to receive the multicast data flow using Data MDT. In response to determining that all the tail nodes are able to receive the multicast data flow using Data MDT, switch to transmitting the multicast data flow to the tail nodes using Data MDT. In response to determining that at least one of the tail nodes is unable to receive the multicast data flow using the Data MDT, continue transmitting the multicast data flow using Data MDT.

First claim

The invention claimed is:

1 . A method comprising:
transmitting, by a head node connected to a source device, a multicast data flow from the source device to receiving devices connected to tail nodes using Default Multicast Distribution Tree (MDT); determining that requirements have been met to begin transmitting the multicast data flow using Data MDT; receiving, by the head node and from each tail node, a message indicating a maximum number of Data MDT tunnels each tail node is capable of supporting: based at least in part on the receiving, determining whether all the tail nodes are able to receive the multicast data flow using Data MDT; in response to determining that all the tail nodes are able to receive the multicast data flow using Data MDT, switch to transmitting the multicast data flow to the tail nodes using Data MDT; or in response to determining that at least one of the tail nodes is unable to receive the multicast data flow using the Data MDT, continue transmitting the multicast data flow using Default MDT.

2 . The method of claim 1 , further comprising, determining whether a flag is set in an Inclusive-Provider Multicast Service Interface Border Gateway Protocol (I-PMSI BGP) message from each tail node, the flag indicating whether each tail node supports Data MDT.

3 . The method of claim 2 , further comprising:
determining that the flag in the I-PMSI BGP message from at least one tail node is not set; and continuing to transmit the multicast data flow using Default MDT.

4 . The method of claim 2 , wherein the message indicating the maximum number of Data MDT tunnels each tail node is capable of supporting is the I-PMSI BGP message from each tail node.

5 . The method of claim 4 , further comprising:
determining that each tail node is currently not using a maximum number of Data MDT tunnels that each tail node is capable of supporting; and switching from transmitting the multicast data flow using Default MDT to transmitting the multicast data flow using Data MDT.

6 . The method of claim 4 , further comprising:
determining that at least one tail node is currently using a maximum number of Data MDT tunnels that the at least one tail node is capable of supporting; and continuing to transmit the multicast data flow using Default MDT.

7 . The method of claim 1 , further comprising determining a maximum number of Data MDT tunnels that the head node can create, based on a number of available Data MDT tunnels a tail node with a lowest capacity of available Data MDT tunnels, has been created; and
continuing to transmit the multicast data flow using Default MDT.

8 . A system comprising:
one or more processors; and one or more non-transitory computer-readable media storing computer-executable instructions that, when executed by the one or more processors, cause the one or more processors to perform operations comprising:
transmitting, by a head node connected to a source device, a multicast data flow from the source device to receiving devices connected to tail nodes using Default Multicast Distribution Tree (MDT);
determining that requirements have been met to begin transmitting the multicast data flow using Data MDT;
receiving, by the head node and from each tail node, a message indicating a maximum number of Data MDT tunnels each tail node is capable of supporting;
based at least in part on the receiving, determining whether all the tail nodes are able to receive the multicast data flow using Data MDT;
in response to determining that all the tail nodes are able to receive the multicast data flow using Data MDT, switch to transmitting the multicast data flow to the tail nodes using Data MDT; or
in response to determining that at least one of the tail nodes is unable to receive the multicast data flow using the Data MDT, continue transmitting the multicast data flow using Default MDT.

9 . The system of claim 8 , the operations further comprising, determining whether a flag is set in an Inclusive-Provider Multicast Service Interface Border Gateway Protocol (I-PMSI BGP) message from each tail nodes, the flag indicating whether each tail node supports Data MDT.

10 . The system of claim 9 , the operations further comprising:
determining that the flag in the I-PMSI BGP message from at least one tail node is not set; and continuing to transmit the multicast data flow using Default MDT.

11 . The system of claim 9 , wherein the message indicating the maximum number of Data MDT tunnels each tail node is capable of supporting is the I-PMSI BGP message from each tail node.

12 . The system of claim 11 , the operations further comprising:
determining that each tail node is currently not using a maximum number of Data MDT tunnels that each tail node is capable of supporting; and switching from transmitting the multicast data flow using Default MDT to transmitting the multicast data flow using Data MDT.

13 . The system of claim 11 , the operations further comprising:
determining that at least one tail node is currently using a maximum number of Data MDT tunnels that the at least one tail node is capable of supporting; and continuing to transmit the multicast data flow using Default MDT.

14 . The system of claim 8 , the operations further comprising determining a maximum number of Data MDT tunnels that the head node can create, based on a number of available Data MDT tunnels a tail node with a lowest capacity of available Data MDT tunnels, has been created; and
continuing to transmit the multicast data flow using Default MDT.

15 . One or more non-transitory computer-readable media storing instructions that, when executed, cause one or more processors to perform operations comprising:
transmitting, by a head node connected to a source device, a multicast data flow from the source device to receiving devices connected to tail nodes using Default Multicast Distribution Tree (MDT); determining that requirements have been met to begin transmitting the multicast data flow using Data MDT; receiving, by the head node and from each tail node, a message indicating a maximum number of Data MDT tunnels each tail node is capable of supporting: based at least in part on the receiving, determining whether all the tail nodes are able to receive the multicast data flow using Data MDT; in response to determining that all the tail nodes are able to receive the multicast data flow using Data MDT, switch to transmitting the multicast data flow to the tail nodes using Data MDT; or in response to determining that at least one of the tail nodes is unable to receive the multicast data flow using the Data MDT, continue transmitting the multicast data flow using Default MDT.

16 . The one or more non-transitory computer-readable media as claim 15 recites, the operations further comprising, determining whether a flag is set in an Inclusive-Provider Multicast Service Interface Border Gateway Protocol (I-PMSI BGP) message from each tail nodes, the flag indicating whether each tail node supports Data MDT.

17 . The one or more non-transitory computer-readable media as claim 15 recites, the operations further comprising:
determining that the flag in the I-PMSI BGP message from at least one tail node is not set; and
continuing to transmit the multicast data flow using Default MDT.

18 . The one or more non-transitory computer-readable media as claim 16 recites, wherein the message indicating the maximum number of Data MDT tunnels each tail node is capable of supporting is the I-PMSI BGP message from each tail node.

Assignees

• Cisco Tech Inc

Inventors

• Mishra Mankamana Prasad
• Krattiger Lukas
• Kapadia Shyam Nayan
• Kumar Nitin

Classifications

• H04L45/02

  Topology update or discovery · CPC title

• H04L45/48

  Routing tree calculation · CPC title

• H04L45/16 Primary

  Multipoint routing · CPC title