Method for utilizing a generic algorithm to provide constraint-based routing of packets in a communication network

• US 6,912,587 B1
• Filed: 12/10/2001
• Issued: 06/28/2005
• Est. Priority Date: 12/10/2001
• Status: Expired due to Term

• Current Assignee: AT&T Corporation (AT&T, Inc.)
• Original Assignee: AT&T, Inc.
• Inventors: O'Neil, Joseph Thomas
• Primary Examiner(s): Geckil, Mehmet B.
• Application Number:
  US10/012,990
• Time in Patent Office: 1,296 Days
• Field of Search: 709/232, 709/235, 370351-352, 370230-232, 370/235, 370244-245, 370/328, 370/338
• US Class Current: 709/232
• CPC Class Codes: G06N 3/126 Evolutionary algorithms, e.g. genetic algorithms or genetic programming
• CPC Class Codes: H04L 45/08 Learning-based routing, e.g. using neural networks or artificial intelligence

Abstract

A Path Generator connects to a communication network and uses genetic algorithms to assign flows to paths. Genotypes encode flow to path assignments for working and protection paths. Genotype fitness functions are computed as a weighted sum of constraint fitness functions. Each constraint fitness function evaluates the degrees to which the genotype is a satisfactory solution. The system can be used for network modeling. It can also receive requests for on-demand assignment of flows and on-demand rerouting of flows.

Claims

1. A method for traffic engineering a packet network by assigning flows to working and protection paths within the packet network, each flow having a start point and an end point and comprising a finite number of packets, the method comprising the steps of:

a). receiving input data for use in generating a genetic algorithm,

b). generating candidate paths for each flow,

c). generating a population of genotypes for each flow,

d). evaluating the fitness of the genotypes, and

e). evolving a new population of genotypes for each flow according to the fitness of existing genotypes, and

f). repeating steps c)-e) until an acceptable genotype corresponding to assignment of at least one particular path for each flow is found, and

g). reporting the flow assignments.

2. The method of claim 1 wherein the input data comprises at least one of the following:

network models, flow requirements, policy constraints, performance measurements and traffic measurements.

3. The method of claim 1 wherein each path defines a sequence of network nodes and links for a particular flow.

4. The method of claim 1 wherein each genotype contains one gene for each flow assignment.

5. The method of claim 4 wherein the value of a gene is the path assigned to a particular flow.

6. The method of claim 4 wherein the value of a gene equals NULL if a particular flow is not assigned to any path.

7. The method of claim 4 wherein said step of evaluating the fitness of the genotypes further comprises the step of generating a genotype format table, said genotype format table comprising one row for each gene that comprises the particular genotype.

8. The method of claim 7 wherein each row of the genotype format table specifies a flow, its assigned path, and an indication as to whether the assigned path is a working path or a protection path.

9. The method of claim 1 wherein said step of generating a population of genotypes further comprises the step of randomly assigning each flow to one of its candidate paths.

10. The method of claim 1 wherein the fitness of a genotype is calculated by a genotype fitness function.

11. The method of claim 10 wherein the genotype fitness function comprises a sum of terms where each term is a coefficient multiplied by at least one constraint fitness function.

12. The method of claim 11 wherein a constraint fitness function that comprises a hard constraint is allocated a high coefficient and a constraint fitness function that comprises a soft constraint is allocated a low coefficient.

13. The method of claim 12 wherein each constraint fitness function comprises a value between 0 and 1, inclusive.

14. The method of claim 11 wherein a constraint fitness function evaluates the degree to which a genotype uses mutually exclusive paths for flows at a specified priority.

15. The method of claim 11 wherein a constraint fitness function evaluates the degree to which a genotype uses mutually exclusive paths for specific flows.

16. The method of claim 11 wherein a constraint fitness function evaluates the degree to which a genotype does not overload network elements.

17. The method of claim 11 wherein a constraint fitness function evaluates the degree to which a genotype minimizes the number of network links required to satisfy flow requirements and policy constraints.

18. The method of claim 11 wherein a constraint fitness function evaluates the degree to which a genotype minimizes the cost of the network links required to satisfy flow requirements and policy constraints.

19. The method of claim 11 wherein a constraint fitness function evaluates the degree to which a genotype uses mutually exclusive network elements for protection and working paths.

20. The method of claim 11 wherein a constraint fitness function evaluates the degree to which a genotype does not overload network elements on protection paths.

21. The method of claim 11 wherein a constraint fitness function evaluates the degree to which a genotype provides protection paths for flows at a specific priority.

22. The method of claim 11 wherein a constraint fitness function evaluates the degree to which a genotype provides protection against single node failures.

23. The method of claim 11 wherein a constraint fitness function evaluates the degree to which a genotype provides protection against multiple node failures.

24. The method of claim 1 wherein the step of evolving a population of genotypes comprises using reproduction techniques.

25. The method of claim 1 wherein the step of evolving a population of genotypes comprises using crossover techniques.

26. The method of claim 1 wherein the step of evolving a population of genotypes comprises using mutation techniques.

27. The method of claim 1 wherein genotypes are selected from a population stochastically according to the fitness value for each genotype.

28. The method of claim 1 wherein the genetic algorithm operates in multiple phases.

29. The method of claim 28 wherein the genetic algorithm accepts user input between phases.

30. The method of claim 28 wherein the genetic algorithm expands the size of a genotype between phases.

31. The method of claim 28 wherein the genetic algorithm holds some flow assignments constant during a phase.

32. The method of claim 28 wherein the genetic algorithm expands the size of a genotype to accommodate new flows in a network.