Apparatus and method for discovering a topology for local area networks connected via transparent bridges

• US 5,734,824 A
• Filed: 12/03/1996
• Issued: 03/31/1998
• Est. Priority Date: 02/10/1993
• Status: Expired due to Term

• Current Assignee: Avaya Holdings Ltd (Avaya Incorporated)
• Original Assignee: Bay Networks, Inc. (Nortel Networks Corporation)
• Inventors: Choi, Isaac P.
• Primary Examiner(s): Shin, Christopher B.
• Application Number:
  US08/758,291
• Time in Patent Office: 483 Days
• Field of Search: 395/200.11, 395/200.02, 395/200.1, 370/85, 370/943, 370/60, 370/254, 370/401, 370/405
• US Class Current: 709/224
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies
• CPC Class Codes: H04L 41/34 Signalling channels for network management communication
• CPC Class Codes: H04L 45/02 Topology update or discovery

Abstract

A system of discovering the active topology of the LANs (local area networks) connected via any apparent bridges that conform to the IEEE 802.1D standard. A discovered active topology of the present invention consists of the active bridges, the LANs and the NMMs (network management modules) that constitute the bridged LAN. The system of the present invention advantageously utilizes the standard (IEEE 802.1D) defined behaviors of transparent bridges to discover the active topology. In so doing, the present invention does not require the bridges to issue any special proprietary frames for development of the active topology. The IEEE 802.1D conforming bridges have the property of forming a path between two conversing end stations. If the two end stations reside in adjacent LANs, the path between these two LANs only has the connecting bridge and no other LAN in between. The present invention utilizes this property in discovering the complete active topology of a bridged LAN via special communications between NMMs located on the LANs. Via cyclic processing and age out functions, the present invention is able to alter the active topology in response to changes within the bridged LAN.

Claims

1. In a bridged local area network (LAN) communication system containing a plurality of LANs communicatively coupled via a plurality of transparent bridges, wherein each LAN includes a network management module (NMM), each NMM for controlling and monitoring communications between devices on its LAN and communications in and out of its LAN, a computer implemented method of determining an active topology of said bridged LAN, said computer implemented method comprising the computer implemented steps of:

constructing communication pathways between NMMs of said plurality of LANs, said step of constructing communication pathways operable within each transparent bridge; and

determining the active topology of said bridged LAN utilizing said communication pathways to send and receive adjacency request messages and adjacency response messages between NMMs of different LANs and wherein adjacency to a particular LAN is determined by examining said adjacency response messages from said NMMs of different LANs resultant from said adjacency request messages sent by said NMMs of different LANs.

2. The method of claim 1 wherein said step of determining the active topology of said bridged LAN is operable within each NMM and further comprises the computer implemented steps of:

a first communication step of communicating an adjacency request message from a sender NMM to a receiver NMM over said communication pathways;

a second communication step of receiving adjacency response messages communicated by said NMMs of said bridged LAN to said sender NMM as a result of said adjacency request message, said adjacency response messages communicated over said communication pathways;

determining if said receiver NMM is adjacent to said sender NMM if only one adjacency response message is received by said second communication step; and

repeating the above steps for a different receiver NMM until an adjacency request message is sent to each NMM of said bridged LAN.

3. The method of claim 1 wherein said step of constructing is implemented according to a spanning tree procedure.

4. The method of claim 3 wherein said spanning tree procedure is approximate to IEEE 802.1D specification standard.

5. The method of claim 1 wherein said step of determining the active topology further comprises the computer implemented step of determining that different receiver NMMs are adjacent to said sender NMM if sets of adjacent response messages received during said second communication step are consistent and are resultant from adjacency request messages sent by said sender NMM to each of said different receiver NMMs associated with a multiported bridge.

6. The method of claim 1 wherein said step of determining the active topology further comprises the computer implemented steps of:

identifying an associated LAN for each receiver NMM determined to be adjacent and for each sender NMM;

compiling an adjacency database for each sender NMM, said adjacency database for recording the associated LAN for each adjacent receiver NMM to each sender NMM; and

multicasting said adjacency database over said bridged LAN to all other NMMs of said bridged LAN.

7. The method of claim 6 further comprising the computer implemented steps of:

compiling an active topology database by collecting and compiling each adjacency database multicasted onto said bridged LAN by each sender NMM; and

displaying a diagrammatic representation of said active topology of said bridged LAN by reading said active topology database and coupling LANs indicated as adjacent by said active topology database.

8. The method of claim 6 further comprising the computer implemented step of initiating each NMM within a communication pathway between said sender NMM and said receiver NMM to generate an echo response message as a result of said adjacency request message sent to said receiver NMM.

9. A method of determining a topology of a network, said network including a first local area network (LAN), a second LAN, and a third LAN, each of said first, second, and third LANs including one or more network management modules (NMMs), each NMM for controlling and monitoring communications between devices on its LAN and communications in and out of its LAN, said method comprising the steps of:

(a) determining a representative first NMM, for said first LAN;

(b) determining a representative second NMM for said second LAN;

(c) determining a representative third NMM for said third LAN;

(d) determining whether said first LAN is one hop away from said second LAN and if so, recording in an adjacency database the one hop away relationship between said first LAN and said second LAN;

(e) determining whether said first LAN is one hop away from said third LAN and if so, recording in an adjacency database the one hop away relationship between said first LAN and said third LAN; and

(f) determining whether said second LAN is one hop away from said third LAN and if so, recording in an adjacency database the one hop away relationship between said second LAN and said third LAN; and

(g) building a topology database based upon said adjacency databases, said topology database containing a representation of the topology of the network.

10. The method as recited by claim 9 wherein said step (d) of determining whether said first LAN is one hop away from said second LAN is carried out by determining if messages communicated from said first LAN to devices on said second LAN are transmitted to said third LAN.

11. The method as recited by claim 9 wherein the step (d) of determining whether said first LAN is one hop away from said second LAN is performed by said representative first NMM and if said first LAN is one hop away from said second LAN, a message is transmitted to a network management station (NMS), said network management station recording the one hop away relationship between said first LAN and said second LAN in a topology database.

12. The method of claim 9 further comprising the step of displaying a graphical representation of the topology of the network on a display.

13. A method of determining a topology of a network, said network comprising a first transparent bridge coupling a first local area network (LAN) and a second LAN and a second transparent bridge coupling said second LAN and a third LAN, each of said first, second, and third LANs including a network management module (NMM) for controlling and monitoring communications between devices on its LAN and communications in and out of its LAN, said method comprising the steps of:

(a) a first NMM determining that said first LAN is one hop away from said second LAN over said first transparent bridge and recording in a topology database the one hop away relationship between said first LAN and said second LAN;

(b) a second determining that said second LAN is one hop away from said third LAN and recording in said topology database the one hop away relationship between said second LAN and said third LAN; and

(c) building a representation of the topology of the network based upon the one hop away relationships.

14. The method as recited by claim 13 wherein said step (a) of a first NMM determining that said first LAN is one hop away from said second LAN is carried out by determining if messages communicated from said first LAN to devices on said second LAN are transmitted to said third LAN.

15. The method of claim 13 further comprising the step of displaying a graphical representation of said topology on a display.

16. In a bridged local area network (LAN) communication system, an improved method of determining an active topology of said bridged LAN, said bridged LAN containing a plurality of LANs communicatively coupled via a plurality of transparent bridges, wherein each LAN includes a network management module (NMM), each NMM for controlling and monitoring communications between devices on its LAN and communications in and out of its LAN, wherein a spanning tree procedure has eliminated communication loops in said bridged LAN, wherein communication pathways have been created between the NMMs of said plurality of LANs based upon filtering databases established at each of said plurality of transparent bridges as a result of the spanning tree procedure, wherein the improvement comprises the computer implemented steps of:

for each of said plurality of LANs

selecting a NMM as a designated NMM for the LAN,

said designated NMM identifying those of said plurality of LANs that are adjacent to the LAN,

said designated NMM storing adjacency information in an adjacency database, said adjacency information resulting from said step of identifying those of said plurality of LANs that are adjacent to the LAN,

said designated NMM multicasting said adjacency information to other NMMs,

said designated NMM receiving the multicast adjacency information sent by other NMMs, and

said designated NMM determining the active topology based upon the multicast adjacency information.

17. The method of claim 16 wherein each of said plurality of LANs includes one or more NMMs, wherein said step of selecting a NMM as a designated NMM further comprises the steps of:

each of said one or more NMMs multicasting an identifier onto the LAN; and

identifying the NMM of said one or more NMMs with the highest priority identifier.

18. The method of claim 17 wherein said identifier includes a media access control (MAC) address.

19. The method of claim 16 further comprising the step of said designated NMM identifying itself to the other NMMs of the plurality of LANs by multicasting a media access control (MAC) address and a LAN ID.

20. The method of claim 16 wherein said step of said designated NMM identifying those of said plurality of LANs that are adjacent to the LAN further comprises the steps of:

said designated NMM sending an adjacency request to the other designated NMMs of said plurality of LANs;

in response to said adjacency requests said designated NMM receiving adjacency responses from the other designated NMMs;

in response to said adjacency requests said designated NMM receiving echo responses from those of the other designated NMMs that hear the adjacency requests yet are not intended recipients of said adjacency requests; and

based upon said echo responses and said adjacency responses, said designated NMM determining which of said plurality of LANs are adjacent to the LAN.

21. The method of claim 16 wherein a network management station (NMS) is coupled to said bridged LAN, said method further comprising the steps of:

said NMS requesting the active topology from one of the plurality of designated NMMs; and

after receiving the active topology, said NMS constructing a graphical representation of said active topology on a display device.