Methods and apparatus to determine an alternate route in a network

• US 8,934,485 B2
• Filed: 08/13/2013
• Issued: 01/13/2015
• Est. Priority Date: 12/14/2010
• Status: Expired due to Fees

• Current Assignee: AT&T Intellectual Property I LP (AT&T, Inc.)
• Original Assignee: AT&T Intellectual Property I LP (AT&T, Inc.)
• Inventors: Uttaro, James, Rosenberg, Eric, Sundt, Mark Richard
• Primary Examiner(s): Jaroenchonwanit, Bunjob
• Application Number:
  US13/965,986
• Publication Number:
  US 20130329737A1
• Time in Patent Office: 518 Days
• Field of Search: None
• US Class Current: 370/389
• CPC Class Codes: H04L 45/22 Alternate routing
• CPC Class Codes: H04L 45/50 using label swapping, e.g. multi-protocol label switch [MPLS]

Abstract

Methods and apparatus to determine an alternate route in a network are disclosed. Example methods disclosed herein include processing a label stack of a data packet at a first node to determine whether the data packet is undergoing alternative routing to a destination. Such example methods also include, in response to determining that the data packet is undergoing alternative routing, processing the label stack to determine multiplicity values for neighbor nodes of the first node, respective ones of the multiplicity values representing respective numbers of times the data packet has been routed to respective ones of the neighbor nodes while undergoing alternative routing to the destination. Such example methods further include updating the label stack to increase a respective multiplicity value associated with the first node prior to routing the data packet from the first node to a first one of the neighbor nodes selected based on the multiplicity values.

Claims

1. A method to route a data packet, the method comprising:

processing a label stack of the data packet at a first node to determine whether the data packet is undergoing alternative routing to a destination;

in response to determining that the data packet is undergoing the alternative routing, processing the label stack at the first node to determine multiplicity values for neighbor nodes of the first node, respective ones of the multiplicity values representing respective numbers of times the data packet has been routed to respective ones of the neighbor nodes while undergoing the alternative routing to the destination; and

updating the label stack to increase a respective multiplicity value associated with the first node prior to routing the data packet from the first node to a first one of the neighbor nodes selected based on the multiplicity values.

2. The method as defined in claim 1, wherein processing the label stack to determine whether the data packet is undergoing alternative routing comprises determining whether the label stack includes a backup label assigned to a second node to which the data packet has already been routed, the backup label being different from a primary label also assigned to the second node, the backup label identifying the second node and indicating that the data packet is undergoing alternative routing.

3. The method as defined in claim 1, wherein processing the label stack at the first node to determine the multiplicity values comprises:

accessing, from the label stack, respective labels identifying the neighbor nodes; and

reading the respective ones of the multiplicity values associated with the respective ones of the neighbor nodes from fields of the labels.

4. The method as defined in claim 3, wherein updating the label stack to increase the respective multiplicity value associated with the first node comprises incrementing a field of a first label included in the label stack, the first label identifying the first node, the field of the first label representing the respective multiplicity value associated with the first node.

5. The method as defined in claim 1, wherein the label stack includes labels identifying a plurality of nodes to which the data packet has already been routed, and processing the label stack at the first node to determine the multiplicity values comprises:

counting respective ones of the labels identifying the respective ones of the neighbor nodes to determine respective numbers of labels included in the label stack for the respective ones of the neighbor nodes; and

setting the respective ones of the multiplicity values associated with the respective ones of the neighbor nodes from fields to be equal to the respective numbers of labels included in the label stack for the respective ones of the neighbor nodes.

6. The method as defined in claim 5, wherein updating the label stack to increase the respective multiplicity value associated with the first node comprises adding a first label to the label stack, the first label identifying the first node.

7. The method as defined in claim 1, further comprising:

in response to determining that the data packet is not undergoing alternative routing, determining, at the first node, whether a primary route from the first node towards the destination is available; and

in response to determining that the primary route is unavailable, adding a backup label to the label stack prior to routing the data packet from the first node to the destination along an alternate path, the backup label (1) identifying the first node, (2) indicating that the data packet is undergoing alternative routing, and (3) representing that the respective multiplicity value for the first node is equal to one.

8. A tangible machine readable storage medium comprising machine readable instructions which, when executed, cause a machine to perform operations comprising:

determining whether a data packet is undergoing alternative routing to a destination based on a label stack of the data packet;

in response to determining that the data packet is undergoing the alternative routing, processing the label stack at a first node to determine multiplicity values for neighbor nodes of the first node, respective ones of the multiplicity values representing respective numbers of times the data packet has been routed to respective ones of the neighbor nodes while undergoing the alternative routing to the destination; and

updating the label stack to increase a respective multiplicity value associated with the first node prior to routing the data packet from the first node to a first one of the neighbor nodes selected based on the multiplicity values.

9. The storage medium as defined in claim 8, wherein determining whether the data packet is undergoing alternative routing comprises determining whether the label stack includes a backup label assigned to a second node to which the data packet has already been routed, the backup label being different from a primary label also assigned to the second node, the backup label identifying the second node and indicating that the data packet is undergoing alternative routing.

10. The storage medium as defined in claim 8, wherein processing the label stack at the first node to determine the multiplicity values comprises:

accessing, from the label stack, respective labels identifying the neighbor nodes; and

reading the respective ones of the multiplicity values associated with the respective ones of the neighbor nodes from fields of the labels.

11. The storage medium as defined in claim 10, wherein updating the label stack to increase the respective multiplicity value associated with the first node comprises incrementing a field of a first label included in the label stack, the first label identifying the first node, the field of the first label representing the respective multiplicity value associated with the first node.

12. The storage medium as defined in claim 8, wherein the label stack includes labels identifying a plurality of nodes to which the data packet has already been routed, and processing the label stack at the first node to determine the multiplicity values comprises:

counting respective ones of the labels identifying the respective ones of the neighbor nodes to determine respective numbers of labels included in the label stack for the respective ones of the neighbor nodes; and

setting the respective ones of the multiplicity values associated with the respective ones of the neighbor nodes from fields to be equal to the respective numbers of labels included in the label stack for the respective ones of the neighbor nodes.

13. The storage medium as defined in claim 12, wherein updating the label stack to increase the respective multiplicity value associated with the first node comprises adding a first label to the label stack, the first label identifying the first node.

14. The storage medium as defined in claim 8, wherein the operations further comprise:

in response to determining that the data packet is not undergoing alternative routing, determining, at the first node, whether a primary route from the first node towards the destination is available; and

in response to determining that the primary route is unavailable, adding a backup label to the label stack prior to routing the data packet from the first node to the destination along an alternate path, the backup label (1) identifying the first node, (2) indicating that the data packet is undergoing alternative routing, and (3) representing that the respective multiplicity value for the first node is equal to one.

15. An apparatus to route a data packet, the apparatus comprising:

a memory having machine readable instructions stored thereon; and

a processor to execute the instructions to perform operations comprising;

determining whether a data packet is undergoing alternative routing to a destination based on a label stack of the data packet;

in response to determining that the data packet is undergoing the alternative routing, processing the label stack at a first node to determine multiplicity values for neighbor nodes of the first node, respective ones of the multiplicity values representing respective numbers of times the data packet has been routed to respective ones of the neighbor nodes while undergoing the alternative routing to the destination; and

updating the label stack to increase a respective multiplicity value associated with the first node prior to routing the data packet from the first node to a first one of the neighbor nodes selected based on the multiplicity values.

16. The apparatus as defined in claim 15, wherein processing the label stack at the first node to determine the multiplicity values comprises:

accessing, from the label stack, respective labels identifying the neighbor nodes; and

reading the respective ones of the multiplicity values associated with the respective ones of the neighbor nodes from fields of the labels.

17. The apparatus as defined in claim 16, wherein updating the label stack to increase the respective multiplicity value associated with the first node comprises incrementing a field of a first label included in the label stack, the first label identifying the first node, the field of the first label representing the respective multiplicity value associated with the first node.

18. The apparatus as defined in claim 15, wherein the label stack includes labels identifying a plurality of nodes to which the data packet has already been routed, and processing the label stack at the first node to determine the multiplicity values comprises:

counting respective ones of the labels identifying the respective ones of the neighbor nodes to determine respective numbers of labels included in the label stack for the respective ones of the neighbor nodes; and

setting the respective ones of the multiplicity values associated with the respective ones of the neighbor nodes from fields to be equal to the respective numbers of labels included in the label stack for the respective ones of the neighbor nodes.

19. The apparatus as defined in claim 18, wherein updating the label stack to increase the respective multiplicity value associated with the first node comprises adding a first label to the label stack, the first label identifying the first node.

20. The apparatus as defined in claim 15, wherein the operations further comprise:

in response to determining that the data packet is not undergoing alternative routing, determining, at the first node, whether a primary route from the first node towards the destination is available; and

in response to determining that the primary route is unavailable, adding a backup label to the label stack prior to routing the data packet from the first node to the destination along an alternate path, the backup label (1) identifying the first node, (2) indicating that the data packet is undergoing alternative routing, and (3) representing that the respective multiplicity value for the first node is equal to one.