System for utilizing genetic algorithm to provide constraint-based routing of packets in a communication network

• US 8,064,432 B2
• Filed: 12/27/2009
• Issued: 11/22/2011
• Est. Priority Date: 12/10/2001
• Status: Expired due to Fees

• Current Assignee: AT&T Corporation (AT&T, Inc.)
• Original Assignee: AT&T Intellectual Property II LP (AT&T, Inc.)
• Inventors: O'Neil, Joseph Thomas
• Primary Examiner(s): Ahmed, Salman
• Application Number:
  US12/647,533
• Publication Number:
  US 20100103937A1
• Time in Patent Office: 695 Days
• Field of Search: 370/351, 370/242, 370/244, 370254-255, 370/239, 370/428, 370/466
• US Class Current: 370/351
• 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
• CPC Class Codes: H04L 45/50 using label swapping, e.g. multi-protocol label switch [MPLS]

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 system for assigning flows to paths in a communication network, the communication network comprising a plurality of nodes, each node being connected to at least one other node by at least one link, each path in the communication network comprising a sequence of the nodes and links for a particular flow, the path starting with a source node and ending with a destination node, the system comprising:

a path generator, wherein the path generator designates flow-to-path assignments in the communication network by using a genetic algorithm, wherein the genetic algorithm determines a fitness of a genotype from a plurality of constraint fitness functions, wherein the fitness is determined by using a genotype fitness function that is calculated as a weighted sum of the plurality of constraint fitness functions, wherein a coefficient is used to adjust a relative importance of each of the plurality of constraint fitness functions; and

an output interface, the output interface for communicating the flow-to-path assignments designated by the path generator to the communication network.

2. The system of claim 1, wherein the path generator comprises a web interface.

3. The system of claim 1, wherein the path generator is configured to process a user request to create and manage a task.

4. The system of claim 3, wherein the task includes a description.

5. The system of claim 3, wherein the task includes a selection of a network model.

6. The system of claim 3, wherein the task includes a selection of flow requirements.

7. The system of claim 3, wherein the task includes a selection of policy constraints.

8. The system of claim 3, wherein the task includes a selection of performance measurements and traffic measurements.

9. The system of claim 3, wherein the task includes a selection of a genetic algorithm.

10. The system of claim 3, wherein the task includes a specification of an output report.

11. The system of claim 3, wherein the path generator is further configured to enable the user to start and stop the task.

12. The system of claim 3, wherein the path generator is further configured to provide intermediate flow-to-path assignments calculated by the task to the user for viewing.

13. The system of claim 3, wherein the path generator is further configured to enable the user to define network models.

14. The system of claim 5, wherein the network model is obtained from a dynamic routing protocol.

15. The system of claim 5, wherein the network model is obtained by reading configuration data from the nodes.

16. The system of claim 5, wherein the network model includes the nodes and definitions of attributes associated with the nodes including maximum packets received per second.

17. The system of claim 5, wherein the network model includes the links and definitions of attributes associated with the links including a bandwidth.

18. The system of claim 6, wherein the flow requirements are defined by a peak bandwidth.

19. The system of claim 1, wherein the genetic algorithm generates a random set of genotypes which are evaluated using a genotype fitness function.

20. A method of assigning flows to paths in a communication network, the communication network comprising a plurality of nodes, each node being connected to at least one other node by at least one link, each path in the communication network comprising a sequence of network nodes and links for a particular flow, the path starting with a source node and ending with a destination node, the method comprising:

providing a path generator with data from the communication network that pertains to at least one flow, wherein the path generator designates flow-to-path assignments in the communications network by using a genetic algorithm, wherein the genetic algorithm determines a fitness of a genotype from a plurality of constraint fitness functions, wherein the fitness is determined by using a genotype fitness function that is calculated as a weighted sum of the plurality of constraint fitness functions, wherein a coefficient is used to adjust a relative importance of each of the plurality of constraint fitness functions; and

communicating the flow-to-path assignments designated by the path generator to the communication network via an output interface.