Determining a path through a managed network

• US 6,785,735 B2
• Filed: 10/16/2002
• Issued: 08/31/2004
• Est. Priority Date: 11/12/1999
• Status: Expired due to Term

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Garakani, Mehryar K., Mueller, Kenneth E. II
• Primary Examiner(s): VU, VIET DUY
• Application Number:
  US10/272,790
• Publication Number:
  US 20040034714A1
• Time in Patent Office: 685 Days
• Field of Search: 709/238, 709/239, 709/242, 709/243, 709/244, 709/245, 709/249, 709/311, 370/395.31, 370/395.5, 370/395.51, 370/395.52, 370/401
• US Class Current: 709/238
• CPC Class Codes: H04L 41/12 Discovery or management of network topologies
• CPC Class Codes: H04L 43/00 Arrangements for monitoring or testing data switching networks
• CPC Class Codes: H04L 43/0811 by checking connectivity
• CPC Class Codes: H04L 43/0817 by checking functioning
• CPC Class Codes: H04L 43/10 Active monitoring, e.g. heartbeat, ping or trace-route
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/34 Source routing
• CPC Class Codes: H04L 45/42 Centralised routing

Abstract

A method and apparatus that provides for determining a packet transmission path for a managed network using Internet Protocol is disclosed. A network management station can use a source-routed IP path tracing operation to determine a packet transmission path for a managed network even when an end-station from which the packet emanates (source node) in the managed network does not support source-routed IP path tracing operation by determining a first gateway used by the source node to reach the packet'"'"'s destination (destination node). Further, a second gateway is determined based on the first gateway and destination node. The second gateway is used as the first hop from the source node to the destination node when the subnet associated with the source node is identical to the subnet associated with the second gateway.

Claims

1. A method for determining a route for a data packet from a source node to a destination node, comprising the steps of:

determining a first portion in the route by identifying a first gateway in the route,

wherein the first portion is from the source node to the first gateway,

wherein the first gateway is the next intermediate gateway that a packet send from the source node to the destination node would visit, and

wherein the source node does not support source-route IP path tracing; and

determining a second portion of the route by source-route IP path tracing, and

wherein the second portion is from the first gateway to the destination node,

wherein identifying the first gateway comprises the steps of;

determining a second gateway used by the source node to reach a network management node;

determining a third gateway based on the second gateway and the destination node;

using the second gateway as the first gateway only if the third gateway and the source node are on different subnets; and

using the third gateway as the first gateway only if the third gateway and the source node are on the same subnets.

2. A computer readable medium having stored thereon instructions which when executed by one or more processors, cause the one or more processors to determine a route for a data packet from a source node to a destination node, said computer readable medium comprising:

instructions for determining a first portion in the route by identifying a first gateway in the route, wherein the first portion is from the source node to the first gateway, wherein the first gateway is the next intermediate gateway that a packet send from the source node to the destination node would visit, and wherein the source node does not support source-route IP path tracing; and

instructions for determining a second portion of the route by source-route IP path tracing, wherein the second portion is from the first gateway to the destination node,

wherein identifying the first gateway comprises the steps of;

determining a second gateway used by the source node to reach a network management node;

determining a third gateway based on the second gateway and the destination node;

using the second gateway as the first gateway only if the third gateway and the source node are on different subnets; and

using the third gateway as the first gateway only if the third gateway and the source node are on the same subnets.

3. An apparatus for determining a route for a data packet from a source node to a destination node, comprising:

means for determining a first portion in the route by identifying a first gateway in the route, wherein the first portion is from the source node to the first gateway, wherein the first gateway is the next intermediate gateway that a packet send from the source node to the destination node would visit, wherein the source node does not support source-route IP path tracing; and

means for determining a second portion of the route by source-route IP path tracing, wherein the second portion is from the first gateway to the destination node,

wherein the means for determining a first portion in the route by identifying a first gateway in the route comprises;

means for determining a second gateway used by the source node to reach a network management node;

means for determining a third gateway based on the second gateway and the destination node;

means for using the second gateway as the first gateway only if the third gateway and the source node are on different subnets; and

means for using the third gateway as the first gateway only if the third gateway and the source node are on the same subnets.

4. An apparatus for determining a route for a data packet from a source node to a destination node, comprising:

a processor;

a network interface that is communicatively coupled to the processor and to a network for sending and receiving packet flows on the network; and

a computer-readable medium accessible to the processor and comprising one or more sequences of instructions which, when executed by the processor, cause the processor to perform the steps of;

determining a first portion in the route by identifying a first gateway in the route, wherein the first portion is from the source node to the first gateway, wherein the first gateway is the next intermediate gateway that a packet send from the source node to the destination node would visit, wherein the source node does not support source-route IP path tracing; and

determining a second portion of the route by source-route IP path tracing, wherein the second portion is from the first gateway to the destination node,

wherein determining a first portion in the route by identifying a first gateway in the route comprises;

determining a second gateway used by the source node to reach a network management node;

determining a third gateway based on the second gateway and the destination node;

using the second gateway as the first gateway only if the third gateway and the source node are on different subnets; and

using the third gateway as the first gateway only if the third gateway and the source node are on the same subnets.