Routing cost normalizing

• US 8,705,369 B2
• Filed: 04/29/2011
• Issued: 04/22/2014
• Est. Priority Date: 04/29/2011
• Status: Active Grant

• Current Assignee: Verizon Patent and Licensing Incorporated (Verizon Communications Inc.)
• Original Assignee: Verizon Patent and Licensing Incorporated (Verizon Communications Inc.)
• Inventors: Jalil, Luay
• Primary Examiner(s): Faroul, Farah
• Application Number:
  US13/097,113
• Publication Number:
  US 20120275309A1
• Time in Patent Office: 1,089 Days
• Field of Search: 370/238
• US Class Current: 370/238
• CPC Class Codes: H04L 45/124 using a combination of metrics

Abstract

A computing device ranks multiple routing pairs based on a current routing configuration for weighted links in a network, and ranks the multiple routing pairs based on a proposed routing configuration, different than the current routing configuration, for the weighted links in the network. The computing device compares a current rank order of a first routing pair and a second routing pair in the multiple routing pairs with a proposed rank order of the first routing pair and the second routing pair. The computing device identifies a change between the current rank order and the proposed rank order and generates a data structure that indicates the identified change between the current rank order and the proposed rank order for the first routing pair and the second routing pair.

Claims

1. A method, comprising:

receiving, by a computing device, first routing information including multiple routing pairs and current weights for each of the multiple routing pairs;

receiving, by the computing device, second routing information including the multiple routing pairs and proposed new weights for each of the multiple routing pairs;

ranking, by the computing device, the first routing information based on particular criteria;

ranking, by the computing device, the second routing information based on the particular criteria;

comparing, by the computing device, a rank order between a first routing pair of the multiple routing pairs and a second routing pair of the multiple routing pairs using the first routing information and a rank order between the first routing pair and the second routing pair using the second routing information;

identifying, by the computing device, a change from the rank order between the first routing pair and the second routing pair using the first routing information to the rank order between the first routing pair and the second routing pair using the second routing information; and

generating, by the computing device, a data structure that indicates the change in the rank order.

2. The method of claim 1, wherein the first routing information and the second routing information include geographical information of each node in each routing pair, the method further comprising:

assigning a category to the change in the rank order based on differences in a type of geographic information between a node in the first routing pair and a node in the second routing pair.

3. The method of claim 2, wherein the type of geographic information includes:

a city,

a state,

a country, or

a region.

4. The method of claim 1, further comprising:

calculating a revised weight, for the second information, of the first routing pair or the second routing pair, wherein the revised weight restores the first routing pair and the second routing pair to the rank order between the first routing pair and the second routing pair of the first routing information.

5. The method of claim 1, further comprising:

comparing a delay associated with the first routing pair and a delay associated with the second routing pair; and

indicating, in the data structure, when a delay associated with a higher ranked of the first routing pair or the second routing pair, using the second information, is larger than a delay associated with the lower ranked of the first routing pair or the second routing pair, using the second information.

6. The method of claim 5, further comprising:

indicating, in the data structure, the difference in delay between the higher ranked of the first routing pair or the second routing pair and the lower ranked of the first routing pair or the second routing pair.

7. The method of claim 1, wherein the first routing pair and the second routing pair include a same edge node.

8. The method of claim 1, wherein ranking the first routing information and ranking the second routing information both include:

sorting the routing pairs alphabetically based on a name of an entry point node,

sorting the routing pairs numerically based on an assigned routing pair weight,

sorting the routing pairs alphabetically based on a name of an exit point node, and

assigning an ordinal rank to the sorted routing pairs.

9. The method of claim 1, wherein the multiple routing pairs include nodes for an Internet Protocol (IP) or a multiprotocol label switching (MPLS) network.

10. A device comprising:

a memory to store a plurality of instructions;

a processor to execute instructions in the memory to;

rank multiple routing pairs based on a current routing configuration for weighted links in a network,

rank the multiple routing pairs based on a proposed routing configuration, different than the current routing configuration, for the weighted links in the network,

compare a current rank order of a first routing pair and a second routing pair of the multiple routing pairs using the current routing configuration with a proposed rank order of the first routing pair and the second routing pair of the multiple routing pairs using the proposed routing configuration,

identify a change between the current rank order and the proposed rank order for the first routing pair and the second routing pair, and

generate a data structure that indicates the identified change between the current rank order and the proposed rank order for the first routing pair and the second routing pair.

11. The device of claim 10, wherein the processor is further configured to execute instructions in the memory to:

assign a category to the identified change between the current rank order and the proposed rank order based on differences in a type of geographic information associated with nodes in the first routing pair and the second routing pair.

12. The network device of claim 10, wherein the processor is further configured to execute instructions in the memory to:

calculate a revised weight for a one of the first routing pair or the second routing pair in the proposed routing configuration, wherein the revised weight would conform the first routing pair and the second routing pair to the rank order based on the current routing configuration.

13. The network device of claim 10, wherein the processor is further configured to execute instructions in the memory to:

compare a delay associated with the first routing pair and a delay associated with the second routing pair, and

use the proposed routing configuration to determine when the delay associated with a higher ranked of the first routing pair or the second routing pair is larger than the delay associated with the lower ranked of the first routing pair or the second routing pair.

14. The network device of claim 13, wherein the processor is further configured to execute instructions in the memory to:

indicate, in the data structure, an amount of difference in the delay associated with a higher ranked of the first routing pair or the second routing pair is larger than the delay associated with the lower ranked of the first routing pair or the second routing pair.

15. The network device of claim 10, wherein the first routing pair and the second routing pair include a common edge node.

16. The network device of claim 10, where, when rank multiple routing pairs based on a current routing configuration for weighted links in a network, the processor is further configured to execute instructions in the memory to:

sort the multiple routing pairs alphabetically based on a name of an entry point node,

sort the multiple routing pairs numerically based on an assigned routing pair weight,

sort the multiple routing pairs alphabetically based on a name of an exit point node, and

assign an ordinal rank to the sorted multiple routing pairs.

17. The network device of claim 10, wherein the processor is further to execute instructions in the memory to

compare a current rank order of the first routing pair and a third routing pair of the multiple routing pairs using the current routing configuration with a proposed rank order of the first routing pair and the third routing pair of the multiple routing pairs using the proposed routing configuration,

identify a change between the current rank order and the proposed rank order for the first routing pair and the third routing pair, and

adding, to the data structure, an indication of the identified change between the current rank order and the proposed rank order for the first routing pair and the third routing pair.

18. A method comprising:

receiving, by a computing device, a current ranked listing of multiple routing pairs based on a current routing configuration for weighted links in a network;

receiving, by the computing device, a proposed ranked listing of multiple routing pairs based on a proposed routing configuration for weighted links in the network;

comparing, by the computing device, a rank order between a first routing pair of the multiple routing pairs and a second routing pair of the multiple routing pairs from the current ranked listing with a rank order between the first routing pair and the second routing pair using the proposed ranked listing;

identifying, by the computing device, a change in the rank order between the first routing pair and the second routing pair using the current ranked listing and the rank order between the first routing pair and the second routing pair using the proposed ranked listing;

assigning a priority category to the identified change in the rank order based on differences in a geographic location associated with a node in the first routing pair and a geographic location associated with a node in the second routing pair; and

generating, by the computing device, a data structure that indicates the change in the rank order and the assigned priority.

19. The method of claim 18, further comprising:

calculating a revised weight, for the second information, of the first routing pair or the second routing pair, wherein the revised weight restores the first routing pair and the second routing pair to the rank order between the first routing pair and the second routing pair of the first routing information.

20. The method of claim 19, further comprising:

comparing a delay associated with the first routing pair and a delay associated with the second routing pair; and

indicating, in the data structure, when the delay associated with a higher ranked of the first routing pair or the second routing pair, using the second information, is larger than the delay associated with the lower ranked of the first routing pair or the second routing pair, using the second information.