System and method for dynamic network topology exploration

• US 5,740,346 A
• Filed: 02/22/1996
• Issued: 04/14/1998
• Est. Priority Date: 02/22/1996
• Status: Expired due to Fees

• Current Assignee: Fujitsu Limited
• Original Assignee: Fujitsu Limited
• Inventors: Weber, Wolf-Dietrich, Helland, Patrick J., Wilcke, Winfried W., Wicki, Thomas M.
• Primary Examiner(s): Beausoliel, Jr., Robert W.
• Assistant Examiner(s): Iqbal, Nadeem
• Application Number:
  US08/605,676
• Time in Patent Office: 782 Days
• Field of Search: 395/182.02, 395/200.17, 395/200.15, 395/200.18, 395/200.21, 395/850, 395/849, 340/825.06, 370/405, 370/248, 370/389, 370/406, 370/352-356, 370/396, 370/404, 370/408, 370/449, 370/450, 370/386
• US Class Current: 714/22
• CPC Class Codes: H04L 45/02 Topology update or discovery

Abstract

A system and method dynamically determines the topology of a source node routing network while having a minimal effect on network performance and without requiring expensive hardware to implement. A source node generates a ping frame. The source node transmits the ping frame to a first source router that is coupled to the source node. The first router transparently identifies the frame as a ping frame and creates an echo frame that is transmitted back to the source node. The first router identifies the port from which the ping frame is received and places this information in the header of the echo frame along with an echo frame identifier. The source node receives the echo frame and identifies routers and nodes to which a ping frame has not been sent based upon the connectivity information in the received echo frame. The source node continue generating and transmitting ping frame to all nodes and routers in the network. The source node identifies loops in the topology to avoid repetitive checking and identifies link and router failures. The topology exploration technique is transparent to the routers The topology exploration techique can be implemented during slow traffic periods with no increase in network latency or the technique can be implemented during high traffic periods and result in only a minimal increase in system latency because ping frames are small and are transparently sent to the control frame handler of the destination router or node.

Claims

1. A method for dynamically a determining network topology information of a network, the network including a plurality of network elements including a first node and a first element coupled to a destination element, comprising the steps of:

(a) generating a ping frame including first routing information identifying a first route from the first node to the destination element, and second routing information identifying a second route from the first element of said network elements to the first node;

(b) transmitting said first ping frame to said destination element via said first route;

(c) receiving a ping frame at the destination element through a first port of said destination element;

d) generating an echo frame in response to said ping frame, said echo frame including first connectivity information, third routing information, and a destination element identifier, said first connectivity information identifying network elements that are adjacent to the destination element and said third routing information including said second routing information and an identifier of said first port;

(e) transmitting said echo frame from said destination element to the first node via said third route;

(f) receiving said echo frame at said first node; and

(g) updating the network topology information by including said destination element identifier and said first connectivity information.

2. The method of claim 1, wherein said destination element is one of a second node and a router.

3. The method of claim 1, further comprising the step of:

(h) repeating steps (a)-(g) for all of said network elements in the network.

4. The method of claim 3, further comprising the step of:

identifying network elements having the same destination element identifier to identify loops in the network topology.

5. The method of claim 1, further comprising the step of:

(i) determining a router table having a plurality of routes through the network, each route from the first node to one of the network elements based upon said network topology information.

6. The method of claim 5, wherein steps (a)-(i) are performed while the network is operating.

7. The method of claim 5, wherein steps (a)-(i) are performed during network initialization.

8. The method of claim 1, wherein step (g) identifies improperly functioning network elements and improperly functioning network links, said network links coupling said network elements.

13. The method of claim 1, further comprising the step of:

(h) repeating steps (a)-(g) for a second of said network elements in the network, wherein said second network element is identified in said first connectivity information.

14. The method of claim 13, wherein said first routing information is derived from previously received connectivity information.

9. A system for determining a network topology information of a network, the network including a plurality of network elements including a first node and a first element coupled to a destination element, the system comprising:

a ping frame generator, located in said first node, for generating a ping frame, said ping frame including first routing information identifying a first route from the first node to the destination element, and second routing information identifying a second route from the first element of said network elements to the first node;

a first node transmitter, coupled to said ping frame generator, for transmitting said first ping frame to said destination element via said first route;

an echo frame generator, located in said destination element, for generating an echo frame in response to said ping frame, said echo frame including first connectivity information, third routing information, and a destination element identifier, said first connectivity information identifying network elements adjacent to the destination element and said third routing information including said second routing information and an identifier of said first port;

a ping frame receiver, located in said destination element, disposed to receive said first ping frame and coupled to said echo frame generator, for receiving a ping frame through a first port of the destination element and for transparently transmitting said ping frame to said echo frame generator;

an echo frame receiver, coupled to said echo frame generator, for transmitting said echo frame from said destination element to the first node via said third route; and

a topology updating unit, coupled to said ping frame identifier and disposed to receive said echo frame, for updating the network topology information by adding said destination element identifier and said first connectivity information.

10. The system of claim 9, further comprising:

a topology loop identifier, coupled to said echo frame receiver, for identifying network elements having the same identifier to identify loops in the network topology.

11. The system of claim 9, further comprising:

a routing table generator, coupled to said topology updating unit, for generating a routing table including a route through the network from the first node to each of the network elements based upon said updated network topology information.

12. The system of claim 9, wherein said destination element is one of a second node and a router.

15. The system of claim 9, wherein said ping frame generator generates a second ping frame addressed to a second destination node identified in said first connectivity information.