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

• US 7,664,094 B1
• Filed: 08/14/2006
• Issued: 02/16/2010
• Est. Priority Date: 12/10/2001
• Status: Expired due to Fees

• Current Assignee: AT&T Corporation (AT&T, Inc.)
• Original Assignee: AT&T Corporation (AT&T, Inc.)
• Inventors: O'Neil, Joseph Thomas
• Primary Examiner(s): Ahmed, Salman
• Application Number:
  US11/504,209
• Time in Patent Office: 1,282 Days
• Field of Search: 370/351, 370/242, 370/244, 370254-255, 370/230, 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 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;

an input interface, said input interface for connecting the PG and the communication network, the input interface for providing the PG with data from the communication network that pertains to one or more flows; 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 5 wherein the network model is obtained from a dynamic routing protocol.

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

8. 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.

9. 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 bandwidth, delay, jitter, terminations, and cost.

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

11. The system of claim 10 wherein the flow requirements are defined by at least one of the following:

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

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

13. The system of claim 12 wherein the policy constraints are defined by at least one of the following:

requirements to avoid specific network elements or use specific network elements.

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

15. The system of claim 14 wherein the performance measurements and traffic measurements for nodes and links during a specified time interval may be captured and stored.

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

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

18. 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.

19. 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.

20. The system of claim 3 wherein the user control of the PG further includes an ability for the user to define network models.

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

22. The system of claim 1 wherein the PG uses performance data and traffic data to assign flows to paths.

23. The system of claim 1 wherein the PG assigns existing flows to different paths.

24. The system of claim 1 wherein the PG provides on-demand assignment of new flows to paths.

25. The system of claim 1 wherein the PG may instruct the source node for a flow to follow a specific sequence of nodes and links.

26. The system of claim 1 wherein the PG issues commands to each node along a path.

27. The system of claim 1 wherein the PG provides on-demand re-routing of flows.

28. The system of claim 1 wherein the PG receives notification of network failures or topology changes.

29. The system of claim 1 wherein the PG receives notification of network failures via a dynamic routing protocol.

30. The system of claim 1 wherein the PG operates in stand-alone mode.

31. The system of claim 1 wherein the PG performs modeling of an existing network.

32. The system of claim 1 wherein the PG performs modeling of a non-existing network.

33. The system of claim 1 wherein the PG computes a minimum number of links to satisfy flow requirements and policy constraints.

34. The system of claim 1 wherein the PG computes a minimum cost of links to satisfy flow requirements and policy constraints.

35. 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:

connecting a Path Generator (PG) and the communication network via an input interface;

providing the PG with data from the communication network via the input interface 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.