Patent ID: 8116227

Claim:
In a network comprising a plurality of routers and links interconnecting the routers, wherein a protocol used to setup one or more label switched paths between the plurality of routers is multipath label switching protocol, a method of exploring a label switched path hierarchy, wherein the hierarchy includes a plurality of layers, wherein each layer of the plurality of layers is configured to support at least one respective label switched path, wherein each label switched path corresponds to at least one path used by a class of packets, the method comprising: transmitting a path verification message from an initial router downstream along a path, wherein a label stack of the path verification message includes a plurality of labels, wherein each label of the plurality of labels in the label stack corresponds to a layer of the plurality of layers in the hierarchy of the path, wherein each label of the plurality of labels is associated with a time-to-live field of a plurality of time-to-live fields, wherein a first label of the plurality of labels corresponds to a first layer of the plurality of layers, wherein the first label is associated with a first time-to-live field of the plurality of time-to-live fields, wherein the first layer comprises a current layer, and wherein an initial value of the first time-to-live field for the first label corresponding to the current layer allows the path verification message to travel one hop along the path from the initial router; in response, receiving a reply message transmitted upstream along the path, wherein the reply message includes information indicating whether the path verification message reached its destination, and wherein the reply message is configured to include at least one alternative path to the path when the reply message is from a router, along the path, other than a destination router; in response: determining whether the reply message includes information describing a second layer, the second layer being a layer in the hierarchy that is different from the first layer and corresponding to a second label of the plurality of labels; in response to determining that the reply message does not include information that describes the second layer, incrementing the first time-to-live field associated with the first label corresponding to the first layer; and in response to determining that the reply message includes information that describes the second layer: modifying the label stack of a next transmitted path verification message; and incrementing a second time-to-live field of the plurality of time-to-live fields, the second time-to-live field being associated with the second label and being different from the first time-to-live field.