System and method for determining the physical topology of a network having multiple subnets

• US 20040255184A1
• Filed: 05/27/2003
• Published: 12/16/2004
• Est. Priority Date: 05/27/2003
• Status: Active Grant

• Current Assignee: Alcatel-Lucent USA, Inc. (Nokia Corporation)
• Original Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Bejerano, Yigal, Rastogi, Rajeev, Garofalakis, Minos N., Breitbart, Yuri J.
• Granted Patent: US 7,535,911 B2
• Time in Patent Office: Days
• US Class Current: 714/4
• CPC Class Codes: H04L 12/462 LAN interconnection over a bridge based backbone
• CPC Class Codes: H04L 41/0213 Standardised network management protocols, e.g. simple network management protocol [SNMP]
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies

Abstract

A system for, and method of, determining a physical topology of a network having multiple subnets. In one embodiment, the system includes: (1) a skeleton path initializer that uses addressing information from elements in the network to develop a collection of skeleton paths of direct physical connections between labeled ones of the elements, the skeleton paths traversing multiple of the subnets and (2) a skeleton path refiner, coupled to the skeleton path initializer, that refines the collection by inferring, from the direct physical connections and path constraints derived therefrom, other physical connections in the skeleton paths involving unlabeled ones of the elements.

Claims

1. A system for determining a physical topology of a network having multiple subnets, comprising:

a skeleton path initializer that uses addressing information from elements in said network to develop a collection of skeleton paths of direct physical connections between labeled ones of said elements, said skeleton paths traversing multiple of said subnets; and

a skeleton path refiner, coupled to said skeleton path initializer, that refines said collection by inferring, from said direct physical connections and path constraints derived therefrom, other physical connections in said skeleton paths involving unlabeled ones of said elements.

2. The system as recited in claim 1 wherein said skeleton path refiner iteratively refines said collection until at least one of said skeleton paths consists of singletons.

3. The system as recited in claim 1 wherein said constraints are selected from the group consisting of:

explicit constraints, and

implicit constraints.

4. The system as recited in claim 1 wherein said skeleton path refiner refines said collection by creating a map between said path constraints and contiguity constraints, constructing an auxiliary skeleton path from said map, recursing on each subset of said auxiliary skeleton path to obtain output skeleton subpaths and concatenating the output skeleton subpaths to obtain a final skeleton path.

5. The system as recited in claim 1 wherein said skeleton path refiner further determines an orientation of at least some of said skeleton paths.

6. The system as recited in claim 1 further comprising a connection finder, associated with said skeleton path refiner, that infers connectivity as among adjacent ports on said skeleton paths.

7. The system as recited in claim 1 wherein said network is an Ethernet network and said addressing information is contained in address forwarding tables associated with said labeled ones of said elements.

8. A method of determining a physical topology of a network having multiple subnets, comprising:

using addressing information from elements in said network to develop a collection of skeleton paths of direct physical connections between labeled ones of said elements, said skeleton paths traversing multiple of said subnets; and

refining said collection by inferring, from said direct physical connections and path constraints derived therefrom, other physical connections in said skeleton paths involving unlabeled ones of said elements.

9. The method as recited in claim 8 wherein said skeleton path refiner iteratively refines said collection until at least one of said skeleton paths consists of singletons.

10. The method as recited in claim 8 wherein said constraints are selected from the group consisting of:

explicit constraints, and

implicit constraints.

11. The method as recited in claim 8 wherein said skeleton path refiner refines said collection by creating a map between said path constraints and contiguity constraints, constructing an auxiliary skeleton path from said map, recursing on each subset of said auxiliary skeleton path to obtain output skeleton subpaths and concatenating the output skeleton subpaths to obtain a final skeleton path.

12. The method as recited in claim 8 wherein said skeleton path refiner further determines an orientation of at least some of said skeleton paths.

13. The method as recited in claim 8 further comprising a connection finder, associated with said skeleton path refiner, that infers connectivity as among adjacent ports on said skeleton paths.

14. The method as recited in claim 8 wherein said network is an Ethernet network and said addressing information is contained in address forwarding tables associated with said labeled ones of said elements.

15. A system for determining a physical topology of an Ethernet network having multiple subnets, comprising:

a skeleton path initializer that uses address forwarding information from elements in said network to develop a collection of skeleton paths of direct physical connections between labeled ones of said elements, said skeleton paths traversing multiple of said subnets; and

a skeleton path refiner, coupled to said skeleton path initializer, that refines said collection by inferring, from said direct physical connections and explicit and implicit path constraints derived therefrom, other physical connections in said skeleton paths involving unlabeled ones of said elements.

16. The system as recited in claim 15 wherein said skeleton path refiner iteratively refines said collection until at least one of said skeleton paths consists of singletons.

17. The system as recited in claim 15 wherein said skeleton path refiner refines said collection by creating a map between said path constraints and contiguity constraints, constructing an auxiliary skeleton path from said map, recursing on each subset of said auxiliary skeleton path to obtain output skeleton subpaths and concatenating the output skeleton subpaths to obtain a final skeleton path.

18. The system as recited in claim 15 wherein said skeleton path refiner further determines an orientation of at least some of said skeleton paths.

19. The system as recited in claim 15 further comprising a connection finder, associated with said skeleton path refiner, that infers connectivity as among adjacent ports on said skeleton paths.

20. The system as recited in claim 15 wherein said skeleton path initializer and said skeleton path refiner are embodied in sequences of software instructions executable in a general purpose computer.

21. The system as recited in claim 15 wherein said skeleton path initializer is embodied in an InitSkeletonPaths routine, said skeleton path refiner is embodied in a RefinePath routine and said system further comprises ComputeConstraint and FindConnections routines.