Traffic route finder in communications network

• US 6,310,883 B1
• Filed: 03/20/1998
• Issued: 10/30/2001
• Est. Priority Date: 12/24/1997
• Status: Expired due to Term

• Current Assignee: Ciena Corporation
• Original Assignee: Nortel Networks Limited (Nortel Networks Corporation)
• Inventors: White, Anthony Richard Phillip, Turner, John Ian, Mann, Jason Warren
• Primary Examiner(s): VU, HUY DUY
• Application Number:
  US09/044,889
• Time in Patent Office: 1,320 Days
• Field of Search: 370/401, 370/402, 370/407, 370/408, 370/409, 370/410, 370/351, 370/352, 370/254, 370/255, 370/256, 370/257, 370/258, 370/248, 709/223, 709/224, 709/225, 709/226, 709/238, 709/239, 709/240, 709/241, 709/242, 709/243, 709/244, 709/252
• US Class Current: 370/408
• CPC Class Codes: H04J 2203/0053 Routing
• CPC Class Codes: H04J 2203/0069 Channel allocation
• CPC Class Codes: H04L 2012/562 Routing
• CPC Class Codes: H04L 2012/5642 Multicast/broadcast/point-multipoint, e.g. VOD
• CPC Class Codes: H04L 2012/5651 Priority, marking, classes
• CPC Class Codes: H04L 45/12 Shortest path evaluation
• CPC Class Codes: H04L 45/24 Multipath
• CPC Class Codes: H04Q 11/0478 Provisions for broadband connections

Abstract

A route finder for point to multi-point connection requests in a communications network comprising a plurality of nodes connected by a plurality of links. A cost is assigned to each network link. For each connection request a set of all network nodes not included in its source node or its plurality of destination nodes are selected. An array of bits is created with an array element corresponding to a selected node element having a value of 1 if the node is steiner vertex for a steiner tree of nodes not selected, otherwise the array element has a value of 0. Each array is treated as a bit string and considered as population members which are manipulated by genetic algorithms. The fitness of the population members is evaluated by calculating the cost of traversing the routes represented by the bit strings. The method is capable of routing a plurality of multi-point connection requests, and selecting an overall optimum solution.

Claims

1. A method of finding routes of links for a plurality of communications connections over a network comprising a plurality of node elements and link elements, each said connection having a source node element and a plurality of destination node elements, said method comprising the machine executable steps of:

assigning at least one link cost to each said link element;

for each said connection to be routed;

selecting a set of node elements of said network which are not included in a source node element or a plurality of destination node elements of said connection;

determining which of said node elements in said set are Steiner Vertices;

evaluating a route cost of traversing a plurality of link elements between said source node elements and said plurality of destination node elements; and

for all said connections to be routed, evaluating a total cost of said route costs.

2. The method according to claim 1, wherein said set of node elements is represented by a string of bits,

a bit in said string having a value of 1 if said node element it represents is marked as a Steiner Vertex, and

a bit in said string having a value of 0 if said node element it represents is not marked as a Steiner Vertex.

3. The method according to claim 2, wherein said step of evaluating a route cost comprises the steps of:

creating a Steiner tree including nodes in each said connection to be route and nodes in said set which are marked as Steiner Vertices; and

adding costs of traversing each link in said Steiner tree.

4. The method according to claim 2, wherein said string of bits is manipulated using genetic algorithm operations, including reproduction, mutation, crossover and merging.

5. The method according to claim 1, wherein said cost(s) assigned to said link element are associated with a data type, and said method comprises the step of:

assigning a data type to all or some of said connections to be routed.

6. The method according to claim 1, comprising the step of:

selecting one or more of said node elements and/or one or more of said link elements to be included or excluded from said route to be found for one or more of said connections to be routed.

7. The method according to claim 1, comprising the step of:

outputting said routes with minimum total cost.

8. The method according to claim 1, wherein a plurality of routes are found for each said connection to be routed, said route cost of each of said plurality of routes not exceeding said connection cost of said connection to be routed.

9. The method according to claim 1, wherein said routes found for all said connections attempt to utilize as many of said node elements and said link elements of said network as possible.

10. The method according to claim 1, wherein said total cost of said route costs of all said connections to be routed is used as a fitness criteria in a genetic algorithm.

11. A method of determining a plurality of routes for a plurality of connections across a network comprising a plurality of nodes and links, each said connection between a source node and a plurality of destination nodes, said method comprising the steps of:

generating a network representation data of said network, said network representation data describing a plurality of interconnected nodes and links;

for each said connection generating a plurality of bit representations of intermediate nodes between said source node and said destination nodes;

for each said connection, evaluating a cost of a set of routes corresponding to one of said intermediate nodes by decoding one of said bit representations as a minimum spanning tree representation;

for all said connections, evaluating a total cost of all corresponding said routes, from said plurality of costs evaluated for said plurality of minimum spanning trees.

12. The method as claimed in claim 11, wherein said step of generating a plurality of bit representations of nodes comprises operating a genetic algorithm technique to produce a plurality of bit strings, each said bit string containing a plurality of said bit representations of nodes, such that each said bit string contains a bit representation of a node for each said connection request.

13. The method as claimed in claim 11, wherein said intermediate nodes correspond to Steiner Vertices.

14. A method of determining a plurality of routes for a plurality of connections across a network comprising a plurality of nodes and links, each said connection having a source node and a plurality of destinations nodes, said method comprising the steps of:

generating a network representation data of said network, said network representation data describing a plurality of interconnected nodes and links of said network wherein each link is assigned a link cost data;

for each of said plurality of connections, representing a plurality of routes of said connection as a minimum spanning tree of nodes and links connecting said source node and said destination nodes of said connections;

for each said connection evaluating a cost of routes represented by said corresponding minimum spanning tree from a plurality of link costs assigned to links of said minimum spanning tree; and

determining a total cost of all said connections from said plurality of costs evaluated for each said minimum spanning tree.