Automatically detecting roles of nodes in layered network topologies

• US 10,367,686 B2
• Filed: 03/08/2017
• Issued: 07/30/2019
• Est. Priority Date: 03/08/2017
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: White, Russell I., Zandi, Shafagh, Kahn, Zaid A.
• Primary Examiner(s): Agosta, Stephen M D
• Application Number:
  US15/453,438
• Publication Number:
  US 20180262392A1
• Time in Patent Office: 874 Days
• CPC Class Codes: H04L 41/0806 for initial configuration or provisioning, e.g. plug-and-play
• CPC Class Codes: H04L 41/0893 Assignment of logical groups to network elements
• CPC Class Codes: H04L 41/0894 Policy-based network configuration management
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies
• CPC Class Codes: H04L 45/18 Loop-free operations
• CPC Class Codes: H04L 45/48 Routing tree calculation
• CPC Class Codes: H04L 51/18 Commands or executable codes
• CPC Class Codes: H04L 51/214 using selective forwarding

Abstract

The disclosed embodiments provide a system that automatically detects a role of a node in a network with a layered topology. During operation, the system uses a local shortest path tree (SPT) for a node in a network with a layered topology to identify one or more additional nodes in the network that are farthest from the node. Next, the system compares the local SPT with a remote SPT for the one or more additional nodes to identify a position of the node in the layered topology. The system then outputs the position of the node for use in configuring the operation of the node in the network.

Claims

1. A method, comprising:

identifying, by a node in a network with a layered topology, using a local shortest path tree (SPT), one or more additional nodes in the network that are farthest from the node;

calculating a position of the node using a difference in length between a longest loop-free path in the local SPT and an additional longest loop-free path in a remote SPT, wherein the difference in length represents a number of layers between the node and the edge of the layered topology; and

configuring operation of the node in the network by;

identifying a role of the node based on the calculated position and a layer in which the node appears in the layered topology;

obtaining a configuration policy for the role at the node; and

configuring the node according to the configuration policy.

2. The method of claim 1, wherein using the local SPT to identify the one or more additional nodes in the network that are farthest from the node comprises:

identifying the one or more additional nodes from the longest loop-free path in the local SPT.

3. The method of claim 1, wherein the difference in length represents a distance of the node from an edge of the layered topology.

4. The method of claim 1, wherein obtaining the configuration policy for the role at the node comprises:

subscribing the node to a topic associated with the role in a publish-subscribe messaging system; and

receiving the configuration policy in one or more messages assigned to the topic.

5. The method of claim 1, wherein the role is at least one of:

a leaf;

a spine; and

a super-spine.

6. The method of claim 1, wherein the configuration policy comprises at least one of:

a protocol;

a filter;

an access control list;

an interface configuration;

a quality of service (QoS) policy; and

a routing policy.

7. The method of claim 1, further comprising:

outputting the calculated position of the node.

8. An apparatus, comprising:

one or more processors; and

memory storing instructions that, when executed by the one or more processors, cause the apparatus to;

identify, by a node in a network with a layered topology, using a local shortest path tree (SPT), one or more additional nodes in the network that are farthest from the node;

calculate a position of the node using a difference in length between a longest loop-free path in the local SPT and an additional longest loop-free path in a remote SPT, wherein the difference in length represents a number of layers between the node and the edge of the layered topology; and

configure operation of the node in the network by;

identifying a role of the node based on the outputted position and a layer in which the node appears in the layered topology;

obtaining a configuration policy for the role at the node; and

configuring the node according to the configuration policy.

9. The apparatus of claim 8, wherein using the local SPT to identify the one or more additional nodes in the network that are farthest from the node comprises:

identifying the one or more additional nodes from the longest loop-free path in the local SPT.

10. The apparatus of claim 8, wherein obtaining the configuration policy for the role at the node comprises:

subscribing the node to a topic associated with the role in a publish-subscribe messaging system; and

receiving the configuration policy in one or more messages assigned to the topic.

11. The apparatus of claim 8, wherein the memory further stores instructions that, when executed by the one or more processors, cause the apparatus to:

output the calculated position of the node.

12. The apparatus of claim 8, wherein the role is at least one of:

a leaf;

a spine; and

a super-spine.

13. A system, comprising:

a network comprising a set of nodes connected by a set of links; and

a node in the set of nodes, wherein the node comprises a non-transitory computer-readable medium comprising instructions that, when executed, cause the system to;

identify, by a node in a network with a layered topology, using a local shortest path tree (SPT), one or more additional nodes in the network that are farthest from the node;

calculate a position of the node using a difference in length between a longest loop-free path in the local SPT and an additional longest loop-free path in a remote SPT, wherein the difference in length represents a number of layers between the node and the edge of the layered topology; and

configure operation of the node in the network by;

identifying a role of the node based on the outputted position and a layer in which the node appears in the layered topology;

obtaining a configuration policy for the role at the node; and

configuring the node according to the configuration policy.

14. The system of claim 13, wherein using the local SPT to identify the one or more additional nodes in the network that are farthest from the node comprises:

identifying the one or more additional nodes from the longest loop-free path in the local SPT.

15. The system of claim 13, wherein the non-transitory computer-readable medium of the node further comprises instructions that, when executed, cause the system to:

output the calculated position of the node.

16. The system of claim 13, wherein obtaining the configuration policy for the role at the node comprises:

subscribing the node to a topic associated with the role in a publish-subscribe messaging system; and

receiving the configuration policy in one or more messages assigned to the topic.

17. The system of claim 13, wherein the role is at least one of:

a leaf;

a spine; and

a super-spine.