Progressively determining a network topology and using neighbor information to determine network topology

• US 8,805,982 B1
• Filed: 06/29/2007
• Issued: 08/12/2014
• Est. Priority Date: 06/29/2007
• Status: Active Grant

• Current Assignee: World Wide Packets, Inc. (Ciena Corporation)
• Original Assignee: Ciena Corporation
• Inventors: Wilsey, Scott Daniel, Atkinson, K. Gintaras, Oye, Darren William, Wen, Bo, Reis, Louis
• Primary Examiner(s): Tiv, Backhean
• Application Number:
  US11/771,080
• Time in Patent Office: 2,601 Days
• Field of Search: 709/220, 709/223
• US Class Current: 709/223
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: Y02D 30/00 Reducing energy consumption in communication networks

Abstract

An element manager and programming collect a first element topology from a first element among a plurality of elements in a network. The first element topology describes only connections between the first element and other elements of the plurality directly connected to the first element. The element manager and programming collect a second element topology from a second element among the plurality of elements. The second element topology describes only connections between the second element and other elements of the plurality directly connected to the second element. The element manager and programming merge the element topologies collected from the elements into a single network topology describing connections between the plurality of elements.

Claims

1. An element manager operating method comprising:

the element manager collecting a first element topology from a first element among a plurality of elements in a network, the first element topology describing connections between the first element and other elements of the plurality directly connected to the first element;

the element manager determining an address of a second element of the plurality of elements from the first element topology, the second element being one of the other elements of the plurality directly connected to the first element;

using the address determined by the element manager, the element manager collecting a second element topology from the second element among the plurality of elements, the second element topology describing connections between the second element and other elements of the plurality directly connected to the second element;

the element manager merging the element topologies collected from the elements into a single network topology describing connections between the plurality of elements;

wherein the first element topology comprising compiled information compiled by the first element, the compiled information resulting from layer-two (data link layer) communication using at least two different layer-two control protocols between the first element and the elements of the plurality directly connected to the first element;

wherein the compiled information comprises first information describing a first one of the other elements directly connected to the first element, the first information resulting from layer-two communication using a first layer-two control protocol between the first element and the first one of the other elements directly connected to the first element; and

the compiled information comprises second information describing a second one of the other elements directly connected to the first element, the second information resulting from layer-two communication using a second layer-two control protocol between the first element and the second one of the other elements directly connected to the first element.

2. The method of claim 1 wherein the element topologies comprise information gathered by the elements using at least one of Link Layer Discovery Protocol (LLDP) packets conforming to the Institute of Electrical and Electronics Engineers (IEEE) 802.1AB standard;

Operations, Administration, and Maintenance (OAM) packets conforming to the IEEE 802.3ah standard;

or Link Aggregation Control Protocol (LACP) packets conforming to the IEEE 802.3ad standard.

3. The method of claim 1 wherein the element topologies comprise information gathered by the elements using OAM packets conforming to the IEEE 802.3ah standard and LLDP packets conforming to the IEEE 802.1AB standard.

4. The method of claim 1 further comprising:

after the merging, displaying the network topology to a user;

collecting a third element topology from a third element among the plurality of elements, the third element topology describing only connections between the third element and other elements of the plurality directly connected to the third element;

merging the third element topology into the single network topology; and

after the merging the third element topology, displaying the network topology to the user.

5. The method of claim 1 wherein the first element and the elements of the plurality directly connected to the first element are directly connected to each other via electrically conductive cables, fiber-optic cables, or wireless links.

6. The method of claim 1 wherein the collecting comprises collecting via Simple Network Management Protocol (SNMP) messages, eXtensible Markup Language (XML) messages, responses to command line interface (CLI) commands, replies to remote method invocations (RMIs), or NETCONF messages.

7. The method of claim 1 wherein the first element topology is derived from communication via a first protocol between the first element and at least one of the other elements of the plurality directly connected to the first element and the second element topology is derived from communication via a second protocol between the second element and at least one of the other elements of the plurality directly connected to the second element, the second protocol being different from the first protocol.

8. The method of claim 1 wherein the address is an Internet Protocol (IP) address of the second element and further comprising the element manager deriving the IP address from a medium access control (MAC) address of the second element comprised by the first element topology collected by the element manager;

wherein the element manager is unaware of the IP address prior to the deriving.

9. The method of claim 1 further comprising the element manager receiving a trap comprising an address of the first element and wherein the collecting of the first element topology comprises collecting using the address of the first element.

10. The method of claim 1 further comprising receiving first connection information describing a connection between a third element of the plurality of elements and a fourth element of the plurality of elements from the third element, the third element being one of the other elements of the plurality directly connected to the first element, the fourth element being directly connected to the third element;

first determining that the first connection information satisfies a condition;

based on the first determining, adding the fourth element to a list of elements awaiting neighbor discovery;

receiving second connection information describing a connection between the third element and a fifth element of the plurality of elements from the third element, the fifth element being directly connected to the third element; and

second determining that the second connection information does not satisfy the condition;

based on the second determining, excluding the fifth element from the list of elements awaiting neighbor discovery.

11. The method of claim 10 wherein the first determining comprises determining that an address of the fourth element belongs to a predetermined set of addresses and the second determining comprises determining that an address of the fifth element does not belong to the predetermined set.

12. A network comprising:

a plurality of network elements, individual network elements being directly connected to at least one other of the network elements;

a plurality of links, individual links directly connecting two of the network elements together and enabling the two directly connected network elements to communicate with each other;

the individual network elements being configured to provide connectivity information describing their neighboring elements, of the plurality of network elements, to which the individual network elements are directly connected and describing the individual links that directly connect the individual network elements to their neighboring elements the individual network elements being configured to gather the connectivity information from their neighboring elements using at least two different layer-two control protocols; and

an element manager configured to;

gather the connectivity information from the network elements;

determine an address of a second element of the plurality of network elements from a portion of the connectivity information gathered from a first element of the plurality, the second element being directly connected to the first element, the first element providing a first element topology; and

use the address determined by the element manager to gather a portion of the connectivity information from the second element comprising a second element topology; and

create a network topology based on the gathered connectivity information comprising the first element topology and the second element topology, the network topology describing the network elements, the links, and an arrangement of the links with respect to the network elements;

wherein the first element topology comprising compiled information compiled by the first element, the compiled information resulting from layer-two (data link layer) communication using at least two different layer-two control protocols between the first element and the elements of the plurality directly connected to the first element;

wherein the compiled information comprises first information describing a first one of the other elements directly connected to the first element, the first information resulting from layer-two communication using a first layer-two control protocol between the first element and the first one of the other elements directly connected to the first element; and

the compiled information comprises second information describing a second one of the other elements directly connected to the first element, the second information resulting from layer-two communication using a second layer-two control protocol between the first element and the second one of the other elements directly connected to the first element.

13. The network of claim 12 wherein the network elements are Ethernet packet switches configured to receive layer-two control packets comprising portions of the connectivity information from the neighboring elements, the layer-two control packets comprising at least one of LLDP packets, OAM packets compliant with the IEEE 802.3ah standard, or LACP packets.

14. The network of claim 12 wherein the element manager is further configured to display the network topology to a user after gathering the connectivity information from a first subset of the network elements and prior to gathering the connectivity information from a second subset of the network elements.

15. The network of claim 12 wherein the address is a medium access control (MAC) address and the element manager is further configured to derive an Internet Protocol (IP) address of the second element from the MAC address.

16. An element manager operating method comprising:

the element manager collecting a first element topology from a first element among a plurality of elements in a network, the first element topology describing connections between the first element and other elements of the plurality directly connected to the first element;

the element manager determining an address of a second element of the plurality of elements from the first element topology, the second element being one of the other elements of the plurality directly connected to the first element;

using the address determined by the element manager, the element manager collecting a second element topology from the second element among the plurality of elements, the second element topology describing connections between the second element and other elements of the plurality directly connected to the second element;

the element manager merging the element topologies collected from the elements into a single network topology describing connections between the plurality of elements;

wherein the first element topology comprising compiled information compiled by the first element, the compiled information resulting from layer-two (data link layer) communication using at least two different layer-two control protocols between the first element and the elements of the plurality directly connected to the first element;

receiving first connection information describing a connection between a third element of the plurality of elements and a fourth element of the plurality of elements from the third element, the third element being one of the other elements of the plurality directly connected to the first element, the fourth element being directly connected to the third element;

first determining that the first connection information satisfies a condition;

based on the first determining, adding the fourth element to a list of elements awaiting neighbor discovery;

receiving second connection information describing a connection between the third element and a fifth element of the plurality of elements from the third element, the fifth element being directly connected to the third element; and

second determining that the second connection information does not satisfy the condition;

based on the second determining, excluding the fifth element from the list of elements awaiting neighbor discovery.

17. The method of claim 16 wherein the element topologies comprise information gathered by the elements using at least one of Link Layer Discovery Protocol (LLDP) packets conforming to the Institute of Electrical and Electronics Engineers (IEEE) 802.1AB standard;

Operations, Administration, and Maintenance (OAM) packets conforming to the IEEE 802.3ah standard;

or Link Aggregation Control Protocol (LACP) packets conforming to the IEEE 802.3ad standard.

18. The method of claim 16 wherein the element topologies comprise information gathered by the elements using OAM packets conforming to the IEEE 802.3ah standard and LLDP packets conforming to the IEEE 802.1AB standard.

19. The method of claim 16 further comprising:

after the merging, displaying the network topology to a user;

collecting a third element topology from a third element among the plurality of elements, the third element topology describing only connections between the third element and other elements of the plurality directly connected to the third element;

merging the third element topology into the single network topology; and

after the merging the third element topology, displaying the network topology to the user.

20. The method of claim 16 wherein the first element and the elements of the plurality directly connected to the first element are directly connected to each other via electrically conductive cables, fiber-optic cables, or wireless links.

21. The method of claim 16 wherein the collecting comprises collecting via Simple Network Management Protocol (SNMP) messages, eXtensible Markup Language (XML) messages, responses to command line interface (CLI) commands, replies to remote method invocations (RMIs), or NETCONF messages.

22. The method of claim 16 wherein the first element topology is derived from communication via a first protocol between the first element and at least one of the other elements of the plurality directly connected to the first element and the second element topology is derived from communication via a second protocol between the second element and at least one of the other elements of the plurality directly connected to the second element, the second protocol being different from the first protocol.

23. The method of claim 16 wherein the address is an Internet Protocol (IP) address of the second element and further comprising the element manager deriving the IP address from a medium access control (MAC) address of the second element comprised by the first element topology collected by the element manager;

wherein the element manager is unaware of the IP address prior to the deriving.

24. The method of claim 16 further comprising the element manager receiving a trap comprising an address of the first element and wherein the collecting of the first element topology comprises collecting using the address of the first element.

25. The method of claim 16 wherein the first determining comprises determining that an address of the fourth element belongs to a predetermined set of addresses and the second determining comprises determining that an address of the fifth element does not belong to the predetermined set.

26. The method of claim 16 wherein the compiled information comprises first information describing a first one of the other elements directly connected to the first element, the first information resulting from layer-two communication using a first layer-two control protocol between the first element and the first one of the other elements directly connected to the first element;

and

the compiled information comprises second information describing a second one of the other elements directly connected to the first element, the second information resulting from layer-two communication using a second layer-two control protocol between the first element and the second one of the other elements directly connected to the first element.