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

• US 7,535,911 B2
• Filed: 05/27/2003
• Issued: 05/19/2009
• Est. Priority Date: 05/27/2003
• Status: Expired due to Fees

• Current Assignee: Alcatel-Lucent USA, Inc. (Nokia Corporation)
• Original Assignee: Alcatel-Lucent USA, Inc. (Nokia Corporation)
• Inventors: Breitbart, Yuri J., Bejerano, Yigal, Rastogi, Rajeev, Garofalakis, Minos N.
• Primary Examiner(s): Kizou; Hassan
• Assistant Examiner(s): ZHU, BO HUI ALVIN
• Application Number:
  US10/445,585
• Publication Number:
  US 20040255184A1
• Time in Patent Office: 2,184 Days
• Field of Search: 370/389, 370/395.3, 370/395.31, 370/395.32, 370/400, 370/401, 370/408, 370/411
• US Class Current: 370/395.31
• 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 of skeleton paths 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, wherein said unlabeled ones are not included in said addressing information, wherein a skeleton path from node s to node t in a graph G representing a connective topology of said network is defined as a sequence Q_s,t=<

U₁, U₂, . . . , U_K>

of non-empty port-id sets U₁, . . . , U_K forming a partition of the set of port-ids P_s,t(U_i∩

U_j=φ

,∪

_iU_i=P_s,t) such that;

(1) each U_j contains the port-ids of a contiguous segment of the s-t path; and

, (2) for each i<

j, all the port-ids in U_i precede those in U_j on the s-t path.

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, wherein a skeleton path from node s to node t in a graph G representing a connective topology of said network is defined as a sequence Q_s,t=<

U₁, U₂, . . . , U_K>

of non-empty port-id sets U₁, . . . , U_K forming a partition of the set of port-ids P_s,t(U_i∩

U_j=φ

,∪

_iU_i=P_s,t) such that;

(1) each U_j contains the port-ids of a contiguous segment of the s-t path; and

, (2) for each i<

j, all the port-ids in U_i precede those in U_j on the s-t path; and

refining said collection of skeleton paths 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 that are not included in said addressing information.

9. The method as recited in claim 8 wherein said refining includes iteratively refining 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 refining includes 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 refining further includes orientating at least some of said skeleton paths.

13. The method as recited in claim 8 further comprising inferring connectivity as among adjacent ports on said skeleton paths.

14. 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 of skeleton paths 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, wherein said unlabeled ones are not included in said address forwarding information, wherein a skeleton path from node s to node t in a graph G representing a connective topology of said network is defined as a sequence Q_s,t=<

U₁, U₂, . . . , U_K>

of non-empty port-id sets U₁, . . . , U_K forming a partition of the set of port-ids P_s,t(U_i∩

U_j=φ

,∪

_iU_i=P_s,t) such that;

(1) each U_j contains the port-ids of a contiguous segment of the s-t path; and

, (2) for each i<

j, all the port-ids in U_i precede those in U_j on the s-t path.

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

16. The system as recited in claim 14 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.

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

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

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

20. The system as recited in claim 14 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.