Up-tree topology trace for network route tracing

• US 6,704,319 B1
• Filed: 12/21/1998
• Issued: 03/09/2004
• Est. Priority Date: 12/21/1998
• Status: Expired due to Fees

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Durham, David M., Fenger, Russell J.
• Primary Examiner(s): Ton, Dang
• Assistant Examiner(s): Phan, Tri H.
• Application Number:
  US09/217,761
• Time in Patent Office: 1,905 Days
• Field of Search: 709/220, 709/252, 709/242, 370/229, 370/230, 370/235, 370/237, 370/252, 370/254, 370/255, 370/256, 370/351, 370/400, 370/401, 370/408, 370/338, 370/402, 370/241, 370/242, 370/248, 370/249, 370/244, 370/245
• US Class Current: 370/408
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/48 Routing tree calculation

Abstract

A network route tracing system traces a path through a network and identifies network components and communications links affected by the path. According to one embodiment of the present invention, a route is traced between two hosts in a network. The network is represented as a logical tree having a plurality of nodes. Each one of the nodes corresponds to a component in the network and each non-root node has a parent node. Two nodes are identified in the logical tree. A first node corresponds to a first host and a second node corresponding to a second host. If one of the two nodes exists at a lower level of the logical tree, then a first path is traced from the first node at the lower level to the parent node at a higher level until the parent node is at a same level of the logical tree as the second node. The first path is further traced up the logical tree from the parent node and a second path is traced up the logical tree from the second node until the first path and the second path meet at a same node.

Claims

1. A method comprising:

representing a network as a logical tree having a plurality of nodes, each one of the nodes corresponding to a component in the network and each non-root node having a parent node;

identifying two nodes in the logical tree, a first node corresponding to a first host in the network and a second node corresponding to a second host in the network;

detecting if one of the two nodes exists at a lower level of the logical tree, wherein each of the nodes include a data structure identifying each node'"'"'s level within the logical tree;

tracing a first path from the first node at the lower level to the parent node at a higher level until the parent node is at a same level of the logical tree as the second node; and

continuing to trace the first path up the logical tree from the parent node and tracing a second path up the logical tree from the second node until the first path and the second path meet at a same node.

2. The method of claim 1, further comprising performing an operation on data corresponding to each one of the nodes in both paths traced up the logical tree.

3. The method of claim 2, wherein the operation performed comprises managing bandwidth for a link in the network.

4. A computer readable medium having computer executable instructions for performing a method comprising:

representing a network as a logical tree having a plurality of nodes, each one of the nodes corresponding to a component in the network and each non-root node having a parent node;

identifying two nodes in the logical tree, a first node corresponding to a first host in the network and a second node corresponding to a second host in the network;

detecting if one of the two nodes exists at a lower level of the logical tree, wherein each of the nodes includes a data structure identifying each node'"'"'s level within the logical tree;

tracing a first path from the first node at the lower level to a parent node at a higher level until the parent node is at a same level of the logical tree as the second node; and

continuing to trace the first path up the logical tree from the parent node and tracing a second path up the logical tree from the second node until the first path and the second path meet at a same node.

5. The computer readable medium of claim 4, further comprising computer-executable instructions for performing an operation on data corresponding to each one of the nodes in both paths traced up the logical tree.

6. The computer readable medium of claim 5, wherein the operation performed comprises managing bandwidth for a link in the network.