Methods and apparatus to determine an alternate route in a network

• US 8,514,859 B2
• Filed: 12/14/2010
• Issued: 08/20/2013
• Est. Priority Date: 12/14/2010
• Status: Active Grant

• 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:
  US12/967,968
• Publication Number:
  US 20120147883A1
• Time in Patent Office: 980 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. An example method disclosed herein to route a data packet to a destination in a network comprises determining multiplicity values for a set of neighbor nodes, a multiplicity value representing a number of times the data packet has been routed to a respective neighbor node in the set of neighbor nodes, and selecting, based on the multiplicity values, a first neighbor node from the set of neighbor nodes to which to send the data packet to route the data packet to the destination.

Claims

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

determining multiplicity values for a set of neighbor nodes, a multiplicity value representing a number of times the data packet has been routed to a respective neighbor node in the set of neighbor nodes; and

selecting, based on the multiplicity values, a first neighbor node from the set of neighbor nodes to which to send the data packet to route the data packet to the destination.

2. A method as defined in claim 1 further comprising processing labels included in a label stack of the data packet to determine the multiplicity values for the set of neighbor nodes, the labels to indicate that the data packet is undergoing alternative routing to the destination, a label to identify a respective node to which the data packet has been routed.

3. A method as defined in claim 2 wherein the labels include fields representing the multiplicity values.

4. A method as defined in claim 2 wherein processing the labels included in the label stack comprises counting the labels associated with the set of neighbor nodes to determine the multiplicity values for the set of neighbor nodes.

5. A method as defined in claim 1 wherein a first multiplicity value of the first neighbor node and a second multiplicity value of a second neighbor node of the set of neighbor nodes are the same, and further comprising:

determining a first routing cost associated with routing the data packet to the destination via the first neighbor node;

determining a second routing cost associated with routing the data packet to the destination via the second neighbor node;

selecting the first neighbor node to which to send the data packet when the first routing cost is less than the second routing cost; and

selecting the second neighbor node to which to send the data packet when the second routing cost is less than the first routing cost.

6. A method as defined in claim 5 wherein determining the first routing cost comprises:

determining a third routing cost associated with routing the data packet to the first node;

determining a fourth routing cost associated with routing the data packet from the first node to the destination; and

combining the third routing cost and the fourth routing cost to determine the first routing cost.

7. A method as defined in claim 1 wherein selecting the first neighbor node based on the multiplicity values comprises:

determining a subset of the set of neighbor nodes associated with a minimum multiplicity value;

when the subset includes only the first neighbor node, selecting the first neighbor node; and

when the subset includes a plurality of neighbor nodes including the first neighbor node, selecting the first neighbor node based on routing costs determined for the plurality of neighbor nodes.

8. A tangible article of manufacture storing machine readable instructions which, when executed, cause a machine to at least:

determine multiplicity values for a set of neighbor nodes, a multiplicity value representing a number of times a data packet has been routed to a respective neighbor node in the set of neighbor nodes; and

select, based on the multiplicity values, a first neighbor node from the set of neighbor nodes to which to send the data packet to route the data packet to a destination.

9. A tangible article of manufacture as defined in claim 8 wherein the machine readable instructions, when executed, further cause the machine to process labels included in a label stack of the data packet to determine the multiplicity values for the set of neighbor nodes, the labels to indicate that the data packet is undergoing alternative routing to the destination, a label to identify a respective node to which the data packet has been routed.

10. A tangible article of manufacture as defined in claim 9 wherein the labels include fields representing the multiplicity values.

11. A tangible article of manufacture as defined in claim 8 wherein the machine readable instructions, when executed, further cause the machine to count the labels associated with the set of neighbor nodes to determine the multiplicity values for the set of neighbor nodes.

12. A tangible article of manufacture as defined in claim 8 wherein a first multiplicity value of the first neighbor node and a second multiplicity value of a second neighbor node of the set of neighbor nodes are the same, and wherein the machine readable instructions, when executed, further cause the machine to:

determine a first routing cost associated with routing the data packet to the destination via the first neighbor node;

determine a second routing cost associated with routing the data packet to the destination via the second neighbor node;

select the first neighbor node to which to send the data packet when the first routing cost is less than the second routing cost; and

select the second neighbor node to which to send the data packet when the second routing cost is less than the second routing cost.

13. A tangible article of manufacture as defined in claim 12 wherein the machine readable instructions, when executed, further cause the machine to:

determine a third routing cost associated with routing the data packet to the first node;

determine a fourth routing cost associated with routing the data packet from the first node to the destination; and

combine the third routing cost and the fourth routing cost to determine the first routing cost.

14. A tangible article of manufacture as defined in claim 8 wherein the machine readable instructions, when executed, further cause the machine to:

determine a subset of the set of neighbor nodes associated with a minimum multiplicity value;

when the subset includes only the first neighbor node, select the first neighbor node; and

when the subset includes a plurality of neighbor nodes including the first neighbor node, select the first neighbor node based on routing costs determined for the plurality of neighbor nodes.

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

a multiplicity determiner to determine multiplicity values for a set of neighbor nodes, a multiplicity value representing a number of times the data packet has been routed to a respective neighbor node in the set of neighbor nodes; and

a neighbor selector to select, based on the multiplicity values determined by the multiplicity determiner, a first neighbor node from the set of neighbor nodes to which to send the data packet to route the data packet to a destination.

16. An apparatus as defined in claim 15 wherein the multiplicity determiner is to process labels included in a label stack of the data packet to determine the multiplicity values for the set of neighbor nodes, the labels to indicate that the data packet is undergoing alternative routing to the destination, a label to identify a respective node to which the data packet has been routed.

17. An apparatus as defined in claim 16 wherein the labels include fields representing the multiplicity values.

18. An apparatus as defined in claim 16 wherein the multiplicity determiner is to count the labels associated with the set of neighbor nodes to determine the multiplicity values for the set of neighbor nodes.

19. An apparatus as defined in claim 15 wherein a first multiplicity value of the first neighbor node and a second multiplicity value of a second neighbor node of the set of neighbor nodes are the same, and the apparatus further comprises a routing cost calculator to:

determine a first routing cost associated with routing the data packet to the destination via the first neighbor node; and

determine a second routing cost associated with routing the data packet to the destination via the second neighbor node, the neighbor selector to select the first neighbor node to which to send the data packet when the first routing cost is less than the second routing cost, the neighbor selector to select the second neighbor node to which to send the data packet when the second routing cost is less than the first routing cost.

20. An apparatus as defined in claim 19 wherein the routing cost calculator is to:

determine a third routing cost associated with routing the data packet to the first node;

determine a fourth routing cost associated with routing the data packet from the first node to the destination; and

combine the third routing cost and the fourth routing cost to determine the first routing cost.