SYSTEM FOR UTILIZING GENETIC ALGORITHM TO PROVIDE CONSTRAINT-BASED ROUTING OF PACKETS IN A COMMUNICATION NETWORK

• US 20100103937A1
• Filed: 12/27/2009
• Published: 04/29/2010
• Est. Priority Date: 12/10/2001
• Status: Active Grant

• Current Assignee: AT&T Corporation (AT&T, Inc.)
• Original Assignee: AT&T Corporation (AT&T, Inc.)
• Inventors: O'NEIL, JOSEPH THOMAS
• Granted Patent: US 8,064,432 B2
• Time in Patent Office: Days
• US Class Current: 370/392
• 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 one or more links, 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 system comprising:

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

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

2. The system of claim 1, wherein the PG comprises a Web interface.

3. The system of claim 1, wherein said PG is controlled by a user to create and manage one or more tasks.

4. The system of claim 3, wherein said one or more tasks include a description.

5. The system of claim 3, wherein said one or more tasks include a selection of a network model.

6. The system of claim 3, wherein the one or more tasks include a selection of flow requirements.

7. The system of claim 3, wherein said one or more tasks include a selection of policy constraints.

8. The system of claim 3, wherein said one or more tasks include a selection of performance measurements and traffic measurements.

9. The system of claim 3, wherein said one or more tasks include a selection of a genetic algorithm.

10. The system of claim 3, wherein said one or more tasks include a specification of an output report.

11. The system of claim 3, wherein said user control of the PG further includes an ability for the user to start and stop the one or more tasks.

12. The system of claim 3, wherein said user control of the PG further includes an ability for the user to view intermediate flow-to-path assignments calculated by the one or more tasks.

13. The system of claim 3, wherein the user control of the PG further includes an ability for 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 network nodes.

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

17. The system of claim 5, wherein said network model includes network links and definitions of attributes associated with the network links including at least one of:

a bandwidth, a delay, a jitter, a termination, and a cost.

18. The system of claim 6, wherein the flow requirements are defined by at least one of:

a peak bandwidth, an average bandwidth, a number of protection paths, a source address, a destination address, and a priority.

19. The system of claim 1, wherein said 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 one or more links, 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 (PG) with data from the communication network that pertains to one or more flows, wherein the PG designates flow-to-path assignments in the communications network by using a genetic algorithm, wherein said genetic algorithm determines a fitness of a genotype from a plurality of constraint fitness functions, wherein said fitness is determined by using a genotype fitness function that is calculated as a weighted sum of said plurality of constraint fitness functions, wherein a coefficient is used to adjust a relative importance of each of said plurality of constraint fitness functions; and

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