Method and system for constructing a loop free multicast tree in a data-center fabric

Patent metadata

Field	Value
Publication number	US-10164782-B2
Application number	US-201715585837-A
Country	US
Kind code	B2
Filing date	May 3, 2017
Priority date	Nov 5, 2013
Publication date	Dec 25, 2018
Grant date	Dec 25, 2018

Abstract

Systems, methods and transitory computer-readable storage media for constructing a loop free multicast tree. The methods include observing a network topology transition affecting a first path from the particular node to a root node, calculating a second path from the particular node to the root node and sending a message to an upstream node requesting that the upstream node be a root port in the calculated second path. If the upstream node agrees to be the root port in the calculated second path, the method further includes creating a new FTAG tree topology view that includes the upstream node as the root port in the second path.

First claim

What is claimed is:

1. A method comprising:
observing a network topology transition affecting a first path from a particular network node to a root node through an upstream current root port node;
calculating a second path from the particular network node to the root node;
first requesting by the particular node, that a first upstream node be a new root port in the calculated second path;
second requesting by the particular node, in response to a denial by the first upstream node to the first requesting, that a second upstream node outside the calculated second path be a new root port;
creating, in response to acceptance by the second upstream node to the second requesting, a new forwarding tag (FTAG) tree topology view that includes the second upstream node as the root port; and
sending, in response to the first upstream node achieving a congruent view of the network topology, a message from the first upstream node to the second upstream node, the message requesting that second upstream node be a designated forwarder at a later time.

2. The method of claim 1 , wherein the first requesting that the first upstream node be the root port in the calculated second path includes information corresponding to the calculated second path.

3. The method of claim 1 , further comprising removing a link corresponding to the affected path from the network topology of the particular network node, wherein removing the link corresponding to the affected path occurs before creating the new network topology view that includes the second upstream node as the root port in the second path.

4. The method of claim 1 , wherein creating the new FT AG tree topology view that includes the second upstream node as the root port regardless of a state of the second upstream node.

5. The method of claim 1 , wherein the particular network node and the second upstream node reevaluate their respective network topology views upon receipt of a link state routing protocol update.

6. The method of claim 1 , wherein the calculated second path from the particular network node to the root node is the shortest path from the particular network node to the root node.

7. A system comprising:
a plurality of nodes in a network, the plurality of nodes configured to send and receive packets throughout the network, the plurality of nodes including a root node and a first node; the first node including a memory, and a processor, the processor configured to:
observing a network topology transition affecting a first path from a particular network node to a root node through an upstream current root port node;

 calculating a second path from the particular network node to the root node; first requesting by the particular node that a first upstream node be a root port in the calculated second path;
second requesting by the particular node, in response to a denial by the first upstream node to the first requesting, that a second upstream node outside the calculated second path be a new root port;
creating, in response to acceptance by the second upstream node to the second requesting, a new forwarding tag (FTAG) tree topology view that includes the second upstream node as the root port; and
sending, in response to the first upstream node achieving a congruent view of the network topology, a message from the first upstream node to the second upstream node, the message requesting that second upstream node be a designated forwarder at a later time.

8. The system of claim 7 , wherein the first requesting that the first upstream node be the root port includes information corresponding to the calculated second path.

9. The system of claim 7 , further comprising removing a link corresponding to the affected path from the network topology of the particular network node, wherein removing the link corresponding to the affected path occurs before creating the new network topology view that includes the second upstream node as the root port in the second path.

10. The system of claim 7 , wherein creating the new FT AG tree topology view that includes the second upstream node as the root port occurs regardless of a state of the second upstream node.

11. The system of claim 7 , wherein the particular network node and the second upstream node reevaluate their respective network topology views upon receipt of a link state routing protocol update.

12. The system of claim 7 , wherein the calculated second path from the particular network node to the root node is the shortest path from the particular node to the root node.

13. A non-transitory computer-readable storage medium having stored therein instructions which, when executed by a processor, cause the processor to perform operations comprising:
observing a network topology transition affecting a first path from a particular network node to a root node through an upstream current root port node;
calculating a second path from the particular network node to the root node;
first requesting by the particular node, that a first upstream node be a root port in the calculated second path;
second requesting by the particular node, in response to a denial by the first upstream node to the first requesting, that a second upstream node outside the calculated second path be a new root port;
creating, in response to acceptance by the second upstream node to the second requesting, a new forwarding tag (FTAG) tree topology view that includes the upstream node as the root port in the second path; and
sending, in response to the first upstream node achieving a congruent view of the network topology, a message from the first upstream node to the second upstream node, the message requesting that second upstream node be a designated forwarder at a later time.

14. The non-transitory computer-readable storage medium of claim 13 , wherein the first requesting that the first upstream node be the root port includes information corresponding to the calculated second path.

15. The non-transitory computer-readable storage medium of claim 13 , storing additional instructions which, when executed by the processor, result in operations further comprising:
removing a link corresponding to the affected path from the network topology of the particular network node, wherein removing the link corresponding to the affected path occurs before creating the new network topology view that includes the second upstream node as the root port in the second path.

16. The non-transitory computer-readable storage medium of claim 13 , wherein creating the new FT AG tree topology view that includes the second upstream node as the root port occurs regardless of a state of the second upstream node.

17. The non-transitory computer-readable storage medium of claim 13 , wherein the particular network node and the second upstream node reevaluate their respective network topology views upon receipt of a link state routing protocol update.

Assignees

• Cisco Tech Inc

Inventors

• Pani Ayaskant

Classifications

• H04L41/12

  Discovery or management of network topologies · CPC title

• H04L41/0894

  Policy-based network configuration management · CPC title

• H04L41/082

  the condition being updates or upgrades of network functionality · CPC title

• H04L12/4633

  Interconnection of networks using encapsulation techniques, e.g. tunneling · CPC title

• H04L61/103

  across network layers, e.g. resolution of network layer into physical layer addresses or address resolution protocol [ARP] · CPC title