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

• US 7,092,378 B1
• Filed: 12/10/2001
• Issued: 08/15/2006
• 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
• Primary Examiner(s): Kizou, Hassan
• Assistant Examiner(s): Ahmed, Salman
• Application Number:
  US10/012,976
• Time in Patent Office: 1,709 Days
• Field of Search: 370/351, 370/242, 370/244, 370254-255, 370/230
• 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);

an input interface, said input interface connecting the PG and the communication network, the input interface providing the PG with data from the communication network that pertains to one or more flows;

an output interface, the output interface communicates flow-to-path assignments designated by the PG to the communication network;

wherein said PG is controlled by a user to create and manage one or more tasks; and

wherein the user control of the PG further includes an ability for the user to define a network model via a graphical user interface, the graphical user interface being generated by a web interface of the PG.

2. 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);

an input interface, said input interface connecting the PG and the communication network, the input interface providing the PG with data from the communication network that pertains to one or more flows;

an output interface, the output interface communicates flow-to-path assignments designated by the PG to the communication network;

wherein the PG assigns flows to paths in the communication network by using a genetic algorithm;

wherein said genetic algorithm generates a random set of genotypes which are evaluated using a genotype fitness function; and

wherein the genotype fitness function is defined as a weighted sum of constraint fitness functions.

3. The system of claim 2 wherein constraint fitness functions may be added, deleted, or updated.

4. 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);

an input interface, said input interface connecting the PG and the communication network, the input interface providing the PG with data from the communication network that pertains to one or more flows;

an output interface, the output interface communicates flow-to-path assignments designated by the PG to the communication network;

wherein said PG is controlled by a user to create and manage one or more tasks;

wherein said one or more tasks include specification of an output report; and

wherein the output report include reports pertaining to flow-to-working path assignments, flow-to-protection path assignments, and results from genotype fitness functions.