Systems and methods for determining network topologies

• US 9,654,380 B1
• Filed: 11/03/2015
• Issued: 05/16/2017
• Est. Priority Date: 02/07/2013
• Status: Active Grant

• Current Assignee: Arista Networks, Inc.
• Original Assignee: Big Switch Networks, Inc. (Arista Networks, Inc.)
• Inventors: Ramasubramanian, Srinivasan, Zhou, Shudong, Appenzeller, Guido, Dhami, Mandeep Singh, Hersey, Daniel C.
• Primary Examiner(s): Nano, Sargon
• Application Number:
  US14/931,274
• Time in Patent Office: 560 Days
• CPC Class Codes: H04L 12/462 LAN interconnection over a bridge based backbone
• CPC Class Codes: H04L 12/4625 Single bridge functionality, e.g. connection of two networks over a single bridge
• CPC Class Codes: H04L 12/4641 Virtual LANs, VLANs, e.g. virtual private networks [VPN] LAN interconnection over a bridge based backbone H04L12/462; encapsulation techniques H04L12/4633; routing of packets H04L45/00; packet switches H04L49/00; virtual private networks for security H04L63/0272
• CPC Class Codes: H04L 41/02 Standardisation; Integration
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies
• CPC Class Codes: H04L 41/122 of virtualised topologies, e.g. software-defined networks [SDN] or network function virtualisation [NFV]
• CPC Class Codes: H04L 43/04 Processing captured monitoring data, e.g. for logfile generation
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: Y02D 30/00 Reducing energy consumption in communication networks

Abstract

A controller may control client switches in a network including client and non-client switches. The controller may maintain a link discovery table including entries that identify links between client switches. The controller may classify the links as direct or broadcast links. To classify links of the link discovery cable, the controller may direct client switches to send broadcast and directed discovery packets from switch ports. Client switches that receive the discovery packets from other client switches may forward the discovery packets to the controller. The controller may use the discovery packets to classify the links of the link discovery table. The controller may classify ports as broadcast or regular ports based on the classified links. Non-client broadcast domains of the network topology may be identified from the broadcast ports using the broadcast and direct links of the link discovery table.

Claims

1. A method of using a controller that controls client switches in a network having non-client switches and end hosts that are coupled to the client and non-client switches, wherein the client switches include ports, the method comprising:

adding ports to a maintenance queue;

periodically selecting some of the ports of the maintenance queue;

performing network discovery operations on the selected ports;

receiving network packets from the client switches that identify flagged ports to be excluded from network discovery operations, wherein adding ports to the maintenance queue comprises adding non-flagged ports to the maintenance queue;

adding the non-flagged ports to a quarantine queue;

controlling the client switches to block network traffic at the non-flagged ports of the quarantine queue;

periodically selecting some of the non-flagged ports of the quarantine queue; and

performing network discovery operations on the selected ports of the quarantine queue.

2. The method defined in claim 1, wherein adding the ports to the maintenance queue comprises adding only the non-flagged ports to the maintenance queue.

3. The method defined in claim 2 wherein performing the network discovery operations on the selected ports of the quarantine queue comprises:

identifying links between client switches that include the selected ports of the quarantine queue; and

in response to identifying the links between the client switches that include the selected ports of the quarantine queue, removing the selected ports of the quarantine queue from the quarantine queue.

4. The method defined in claim 3 wherein adding only the non-flagged ports to the maintenance queue comprises:

adding only the selected ports that have been removed from the quarantine queue to the maintenance queue.

5. The method defined in claim 1 wherein performing network discovery operations on the selected ports comprises:

directing the client switches to send broadcast discovery packets from the selected ports.