Traffic route finder in communications network

• US 6,314,093 B1
• Filed: 06/02/1998
• Issued: 11/06/2001
• Est. Priority Date: 12/24/1997
• Status: Expired due to Term

• Current Assignee: Apple Inc.
• Original Assignee: Nortel Networks Limited (Nortel Networks Corporation)
• Inventors: Mann, Jason Warren, Turner, John Ian, White, Anthony Richard Phillip
• Primary Examiner(s): TON, DANG T
• Application Number:
  US09/088,805
• Time in Patent Office: 1,253 Days
• Field of Search: 370/351, 370/389, 370/390, 370/391, 370/392, 370/395, 370/396, 370/428, 370/401, 370/467, 370/235, 370/254, 370/252, 370/255, 370/256, 370/352, 370/353, 370/356, 370/355, 370/400, 370/399, 370/394, 370/432, 370/474, 370/475, 370/476, 370/403, 370/406, 370/407, 370/409, 340/825.01, 340/825.03, 340/825.5, 340/927
• US Class Current: 370/351
• 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 means and method for finding routes to satisfy a plurality of 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. Arrays of eight shortest paths of links between each pair of nodes in the network are created. Bit strings comprising for example a 3 bit binary number for each point-to-point connection request are generated. Each 3 bit number is an index to one element of the shortest path array for each connection request'"'"'s source and destination nodes. The bit strings are assembled into 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 route finder means and method has an ability to split traffic over multiple routes, and to handle different traffic types, eg different bit rate traffic types. The route finder means and method is generic to a plurality of different communications network types.

Claims

1. In a network comprising a plurality of nodes and links, a method of simultaneously assigning a plurality of routes to a plurality of connections so as to optimize the links for said plurality of connections comprising the steps:

for each connection, generating data describing a plurality of routes for said connections, each said route represented as a bit representation;

assembling a plurality of said bit representations into a bit string representing a respective route for each of said plurality of connections;

creating a population comprising a plurality of said bit strings;

modifying said population of bit strings to rearrange order of bits within individual bit strings of said population;

for each bit string of said population, determining a utilization of each link in said network; and

selecting said bit string having a relatively more even distribution of utilization across all said links so as to optimize the links for all said connections.

2. The method according to claim 1, comprising the steps of:

for each connection to be routed, generating a binary number representing an index to a list of routes between the source node and destination node of each connection; and

forming a bit string from said binary numbers.

3. The method according to claim 1, wherein said bit strings are manipulated using genetic algorithm operations, including the process of reproduction, mutation, crossover and merging.

4. The method according to claim 1, wherein said step of evaluating a total cost comprises the step of:

adding costs of traversing each link in a selected routes.

5. The method according to claim 4, comprising the step of:

outputting said routes with minimum said total cost.

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