Method for determining the topology of a mixed-media network

• US 5,850,397 A
• Filed: 04/10/1996
• Issued: 12/15/1998
• Est. Priority Date: 04/10/1996
• Status: Expired due to Term

• Current Assignee: RPX Clearinghouse LLC (RPX Corporation)
• Original Assignee: Bay Networks, Inc. (Nortel Networks Corporation)
• Inventors: Nguyen, Nam N., Raab, Ilan, Hadagali, Guruprasad S., Ho, Gilbert D., Chang, Ai-Lan
• Primary Examiner(s): Chin, Wellington
• Assistant Examiner(s): Carman, Melissa Kay
• Application Number:
  US08/630,384
• Time in Patent Office: 979 Days
• Field of Search: 370/389, 370/392, 370/401, 370/407, 370/410, 370/395, 370/254, 370/257, 370/400, 395/183.01, 1/1
• US Class Current: 370/392
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing
• CPC Class Codes: H04L 45/42 Centralised routing

Abstract

A method for determining the topology of a mixed-media network is provided. According to the method, the network is divided into communities of devices that support a common topology mechanism ("spheres"). On each sphere, one or more sphere topology agents generate and accumulate topology data for the devices on the sphere using the topology mechanism that is supported by the devices within the sphere. A global topology agent collects the topology data for each sphere from the various sphere agents and assembles the data to determine the global topology of the mixed-media network. The global topology agent begins by collecting data from a current sphere and identifies additional spheres based on data stored in boundary devices within the current sphere. The global topology agent then repeats the same process with the additional spheres until topology data has been collected from all of the spheres in the mixed-media network.

Claims

1. A method for determining a global topology of a global network, the method comprising the steps of:

partitioning the global network into a plurality of spheres;

determining interconnections between devices within each sphere of said plurality of spheres;

determining intersections between said plurality of spheres; and

determining said global topology based on said interconnections between devices within each sphere of said plurality of spheres and said intersections between said spheres.

2. The method of claim 1 wherein the step of partitioning the global network into a plurality of spheres comprises the steps of:

a) establishing a network within said global network as a current network;

b) identifying a boundary device that belongs to said current network;

c) reading connection information stored in the boundary device that identifies a local area network to which said boundary device is connected;

d) establishing said a local area network as said current network; and

e) repeating steps b) through d) until all local area networks within said global network have been established as spheres.

3. The method of claim 1 wherein the step of determining interconnections between devices within each sphere of said plurality of spheres comprises the steps of:

determining a network media that is associated with a selected sphere;

selecting a sphere agent that corresponds to said network media;

causing said sphere agent to collect topology data from devices in said sphere; and

collecting topology information from said sphere agent.

4. The method of claim 1 wherein the step of determining intersections between said plurality of spheres comprises detecting when a logical device that belongs to a first sphere has an identical physical device identifier as a logical device that belongs to a second sphere.

5. The method of claim 3 wherein the step of causing said sphere agent to collect topology data from devices in said sphere comprises the steps of:

sending special messages between devices that belong to said sphere; and

restricting transmission of said special messages to devices that belong to said sphere.

6. The method of claim 2 further comprising the step of determining interconnections between devices of said current network prior to performing the step of establishing said local area network as said current network.

7. The method of claim 6 wherein the step of determining interconnections between devices of said current network comprises the steps of:

determining a network media that is associated with said current network;

selecting a sphere agent that corresponds to said network media;

causing said sphere agent to collect topology data from devices in said sphere; and

collecting topology information from said sphere agent.

8. A method for determining interconnections between devices within a mixed-media network, the method comprising the steps of:

identifying a first set of devices which implement a first topology mechanism;

determining interconnections between the devices in said first set of devices using said first topology mechanism;

identifying one or more boundary devices that belong to said first set of devices;

identifying, based on information stored in said one or more boundary devices, one or more other sets of devices which implement topology mechanisms that are different from said first topology mechanism; and

determining interconnections between devices in said one or more other sets of devices using topology mechanisms implemented by said one or more other sets of devices.

9. The method of claim 8 wherein:

the mixed-media network includes a frame switched network and a cell switched network;

the step of determining interconnections between the devices in said first set of devices is performed by determining interconnections between devices in said frame switched network; and

the step of determining interconnections between devices in said one or more other sets of devices includes determining interconnections between devices in said cell switched network.

10. The method of claim 8 wherein the step of determining interconnections between the devices in said first set of devices using said first topology mechanism comprises transmitting special messages among devices that belong to said first set of devices.

11. The method of claim 10 wherein the step of determining interconnections between the devices in said first set of devices is performed without transmitting said special messages to devices that do not belong to said first set of devices.