Back to results
US 8,804,719 B2Granted
In-band multicast trace in IP and MPLS networks
AssigneeCisco Technology, Inc.
InventorsSam K. Aldrin, Azhar M. Sayeed
Life of this patent
Estimating the term…
Abstract
In one embodiment, which may be implemented in either IP networks or MPLS networks, a tree of the network may be constructed at a source network device by sending only a single packet. The remaining network devices in the network replicate the packet so that a copy will reach each of the egress nodes. Along the way, identity information from each node or hop will be added to the replicated packets. As the egress nodes receive the packets, the egress nodes will each send a reply packet to the source network device. The reply packet includes a list of every hop on the path. The source network device is configured to construct a tree of the network based on the reply packets.
Claims22
An apparatus comprising:
- an interface configured to receive a packet from a router in a network, the packet initiated by a source network device;
- a processor configured to identify a plurality of paths from the apparatus to one or more next-hop network devices of the apparatus;
- the processor further configured to replicate the packet for each one of the plurality of paths when the apparatus is a forwarding node, wherein replication of the packet produces a plurality of upstream packets;
- the interface further configured to transmit the upstream packets to the one or more next-hop network devices of the apparatus via the paths when the apparatus is the forwarding node, the paths including a first path to a destination and a second path the destination, wherein the second path is a backup path for the first path, and wherein each of the upstream packets is a replica of the received packet appended with identity information about the forwarding node by the forwarding node;
- the processor further configured to extract from the received packet the identity information of forwarding nodes visited by the received packet when the apparatus is an egress node;
- and
- the interface further configured to transmit to the source network device, when the apparatus is the egress node, a reply packet comprising the extracted identity information of the forwarding nodes visited by the received packet, wherein an egress path is identifiable based on the extracted identity information, the egress path comprising a series of next-hop devices from the source network device to the egress node, the series including the router.
4 more elements
A method comprising:
- receiving a packet at an intermediate network device from a network device, the packet being a replica of a single outbound packet originated at a source network device;
- identifying one or more next hop network devices on a plurality of paths from the intermediate network device to a destination address;
- adding, at the intermediate network device, an upstream type-length-value (TLV) including information regarding an identity of the intermediate network device to the packet;
- replicating the packet for each of the plurality of paths, wherein replicated packets are a plurality of upstream packets that each include the upstream TLV including the information regarding the identity of the intermediate network device, and wherein the paths include a first path to the destination address and a second path to the destination address, wherein the second path is a backup path for the first path;
- and
- forwarding each of the plurality of upstream packets via a respective one of the paths to a respective one of the one or more next hop devices.
3 more elements
An apparatus comprising:
- an interface configured to send an outbound packet to a network and receive a reply packet from each egress node of the network, wherein the reply packet identifies a path from the apparatus to a respective egress node, the path comprising an identity of a transit node of the network;
- a memory configured to store the reply packet received from each egress node, wherein the outbound packet includes a time to live value set to expire at the transit node, and wherein the transit node is configured to:
- suppress a response message to the apparatus acknowledging receipt of the outbound packet,
- reset the time to live value of the outbound packet to expire at a next hop node of the transit node, and
- send a replica of the outbound packet, via a plurality of paths to a destination address, over at least one neighboring network device of the transit node, and wherein the replica comprises identity information of the transit node, and wherein the paths include a primary path to the destination address and a backup path to the destination address;
- and
- a processor configured to construct a tree of the network based on the reply packet from each egress node accessed from the memory, the tree representing regular paths and backup paths from the apparatus to each egress node of the network.
4 more elements
A method comprising:
- sending a single outbound packet from a source network device to a network;
- receiving the single outbound packet at a transit node of the network;
- identifying one or more next hop devices of the transit node on a plurality of paths from the transit node to a destination address, wherein the paths include a first path to the destination and a second path to the destination, and wherein the second path is a backup path for the first path;
- replicating the single outbound packet for each of the paths, wherein the replicating comprises producing replicas of the single outbound packet;
- adding identity information of the transit node to the replicas of the single outbound packet;
- transmitting the replicas of the single outbound packet via the paths from the transit node to the one or more next hop devices;
- receiving, at the source network device, in response to the single outbound packet, a reply packet from each egress node of the network, wherein the reply packet from at least one egress node includes the identity information of the transit node added by the transit node to the single outbound packet;
- and
- constructing, at the source network device, a tree of the network based on path information included in the reply packet received from each egress node of the network.
6 more elements
Dependencies are inferred from the claim text.