Method and System for Network Migration Scheduling

• US 20090168665A1
• Filed: 12/31/2007
• Published: 07/02/2009
• Est. Priority Date: 12/31/2007
• Status: Active Grant

• Current Assignee: AT&T Labs Incorporated (AT&T, Inc.)
• Original Assignee: AT&T Labs Incorporated (AT&T, Inc.)
• Inventors: Andrade, Diego Vieira, Resende, Mauricio Guilherme de Carvalho
• Granted Patent: US 8,139,502 B2
• Time in Patent Office: Days
• US Class Current: 370/254
• CPC Class Codes: H04W 8/30 Network data restoration; Network data reliability; Network data fault tolerance

Abstract

A method of transforming an ordered list of nodes of a network into one of a plurality of elite ordered lists, the ordered list corresponding to a deloading sequence, the deloading sequence including a temporary capacity requirement, each of the elite ordered lists corresponding to an elite deloading sequence including an elite temporary capacity requirement by generating at least one intermediate ordered list corresponding to an intermediate deloading sequence including an intermediate temporary capacity requirement, selecting one of the intermediate ordered list and the ordered list based on a comparison of the intermediate temporary capacity requirement and the temporary capacity requirement and replacing one of the elite ordered lists with the one of the intermediate ordered list and the ordered list if a value corresponding to one of the intermediate temporary capacity requirement and the temporary capacity requirement is less than a lowest value of the elite temporary capacity requirements.

Claims

1. A method of transforming an ordered list of nodes of a network into one of a plurality of elite ordered lists, the ordered list corresponding to a deloading sequence of the nodes from the network, the deloading sequence including a temporary capacity requirement, each of the elite ordered lists corresponding to an elite deloading sequence including an elite temporary capacity requirement, comprising:

generating at least one intermediate ordered list corresponding to an intermediate deloading sequence including an intermediate temporary capacity requirement;

selecting one of the intermediate ordered list and the ordered list based on a comparison of the intermediate temporary capacity requirement and the temporary capacity requirement; and

replacing one of the elite ordered lists with the one of the intermediate ordered list and the ordered list if a value corresponding to one of the intermediate temporary capacity requirement and the temporary capacity requirement is less than a lowest value of the elite temporary capacity requirements.

2. The method of claim 1, further comprising:

replacing one of the elite ordered lists with the one of the intermediate ordered list and the ordered list if the value corresponding to one of the intermediate temporary capacity requirement and the temporary capacity requirement is less than a greatest value of the elite temporary capacity requirements and the one of the intermediate ordered list and the ordered list differs from each of the elite ordered lists by at least a predetermined value.

3. The method of claim 1, wherein the transforming is based on a greedy randomized process.

4. The method of claim 1, further comprising:

transforming a first one of the elite ordered lists into each of the remaining ones of the elite ordered lists, the transforming generating at least one intermediate elite ordered list for each of the remaining ones of the elite ordered lists, each of intermediate elite ordered lists corresponding to an intermediate elite deloading sequence including an intermediate elite temporary capacity requirement.

5. The method of claim 4, further comprising:

comparing the lowest value of the elite temporary capacity requirements to a lowest value of the intermediate elite temporary capacity requirements; and

outputting the intermediate elite ordered list corresponding to the lowest value of the intermediate elite temporary capacity requirements, if the lowest values are equal.

6. The method of claim 5, further comprising:

repeating the transforming of claim 4 for the intermediate elite ordered lists if the lowest value of the elite temporary capacity requirements is greater than the lowest value of the intermediate elite temporary capacity requirements.

7. The method of claim 6, wherein a number of times the repeating is performed is limited by a predefined threshold.

8. The method of claim 1, further comprising:

generating an original ordered list of nodes, the original ordered list corresponding to an original deloading sequence including an original temporary capacity requirement;

modifying the original ordered list to generate a modified ordered list of the nodes, the modified ordered list corresponding to a modified deloading sequence including a modified temporary capacity requirement; and

selecting, as the ordered list, one of the original ordered list and the modified ordered list based on a comparison of the original temporary capacity requirement and the modified temporary capacity requirement.

9. The method of claim 8, wherein the selecting is based on the one of the original ordered list and the modified ordered list that corresponds to a lower value of one of the original temporary capacity requirement and the modified temporary capacity requirement.

10. The method of claim 8, wherein the generating is based on a greedy randomized search procedure.

11. A system to transform an ordered list of nodes of a network into one of a plurality of elite ordered lists, the ordered list corresponding to a deloading sequence of the nodes from the network, the deloading sequence including a temporary capacity requirement, each of the elite ordered lists corresponding to an elite deloading sequence including an elite temporary capacity requirement, comprising:

a memory storing the ordered list of nodes and the elite ordered lists; and

a processor generating at least one intermediate ordered list corresponding to an intermediate deloading sequence including an intermediate temporary capacity requirement, selecting one of the intermediate ordered list and the ordered list based on a comparison of the intermediate temporary capacity requirement and the temporary capacity requirement, and replacing one of the elite ordered lists with the one of the intermediate ordered list and the ordered list if a value corresponding to one of the intermediate temporary capacity requirement and the temporary capacity requirement is less than a lowest value of the elite temporary capacity requirements.

12. The system of claim 11, wherein the processor replaces one of the elite ordered lists with the one of the intermediate ordered list and the ordered list if the value corresponding to one of the intermediate temporary capacity requirement and the temporary capacity requirement is less than a greatest value of the elite temporary capacity requirements and the one of the intermediate ordered list and the ordered list differs from each of the elite ordered lists by at least a predetermined value.

13. The system of claim 11, wherein the processor transforms the ordered list based on a greedy randomized process.

14. The system of claim 11, wherein the processor transforms a first one of the elite ordered lists into each of the remaining ones of the elite ordered lists, the transforming generating at least one intermediate elite ordered list for each of the remaining ones of the elite ordered lists, each of intermediate elite ordered lists corresponding to an intermediate elite deloading sequence including an intermediate elite temporary capacity requirement.

15. The system of claim 14, wherein the processor compares the lowest value of the elite temporary capacity requirements to a lowest value of the intermediate elite temporary capacity requirements and outputs the intermediate elite ordered list corresponding to the lowest value of the intermediate elite temporary capacity requirements, if the lowest values are equal.

16. The system of claim 15, wherein the processor repeats the transforming of claim 14 for the intermediate elite ordered lists if the lowest value of the elite temporary capacity requirements is greater than the lowest value of the intermediate elite temporary capacity requirements.

17. The system of claim 11, wherein the processor generates an original ordered list of nodes, the original ordered list corresponding to an original deloading sequence including an original temporary capacity requirement, modifies the original ordered list to generate a modified ordered list of the nodes, the modified ordered list corresponding to a modified deloading sequence including a modified temporary capacity requirement and selects, as the ordered list, one of the original ordered list and the modified ordered list based on a comparison of the original temporary capacity requirement and the modified temporary capacity requirement.

18. The system of claim 17, wherein the processor selects the ordered list based on the one of the original ordered list and the modified ordered list that corresponds to a lower value of one of the original temporary capacity requirement and the modified temporary capacity requirement.

19. The system of claim 17, wherein the processor generates the original ordered list of nodes based on a greedy randomized search procedure.

20. A memory storing a set of instructions executable by a processor to transform an ordered list of nodes of a network into one of a plurality of elite ordered lists, the ordered list corresponding to a deloading sequence of the nodes from the network, the deloading sequence including a temporary capacity requirement, each of the elite ordered lists corresponding to an elite deloading sequence including an elite temporary capacity requirement, the set of instructions being operable to:

generate at least one intermediate ordered list corresponding to an intermediate deloading sequence including an intermediate temporary capacity requirement;

select one of the intermediate ordered list and the ordered list based on a comparison of the intermediate temporary capacity requirement and the temporary capacity requirement; and

replace one of the elite ordered lists with the one of the intermediate ordered list and the ordered list if a value corresponding to one of the intermediate temporary capacity requirement and the temporary capacity requirement is less than a lowest value of the elite temporary capacity requirements.