Traffic routing in a telecommunications network

• US 6,349,090 B1
• Filed: 06/01/1998
• Issued: 02/19/2002
• Est. Priority Date: 09/26/1995
• Status: Expired due to Term

• Current Assignee: Benhov GmbH, LLC (Intellectual Ventures LLC)
• Original Assignee: Nortel Networks Limited (Nortel Networks Corporation)
• Inventors: Lewis, Kevin, Mace, Bertrund Gerard Christian
• Primary Examiner(s): Nguyen, Chau
• Assistant Examiner(s): MEHRA, INDER P
• Application Number:
  US09/043,765
• Time in Patent Office: 1,359 Days
• Field of Search: 370/238, 370/254, 370/255, 370/256, 370/351, 370/389, 370/392, 370/400, 370/401, 709/238, 709/241
• US Class Current: 370/238
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/26 Route discovery packet
• CPC Class Codes: H04L 45/34 Source routing

Abstract

In a telecommunications network comprising a plurality of nodes (N1, N2. . . ) interconnected by communications links (L1, L2. . . ) each incorporating one or more communications channels, traffic routing between network nodes is determined by providing a map or model of the network and determining in the model first and second nodes between which a communications path or route is to be established across the network. A set or colony of exploratory agents is created at the first node, and explores the model network via the links and nodes between the first and second nodes, each agent recording the results of its exploration. From this exploration, a route favoured by a significant number of the agents is determined and is set up on the telecommunications network.

Claims

1. A method of operating a telecommunications network whereby to determine traffic routing, said network comprising a plurality of nodes interconnected by communications links and each said link incorporating one or more communications channels, wherein the method includes, providing a model of the network, determining in the model first and second nodes between which a communications path or route comprising a chain of links is to be established across the network, allocating to each said link a cost value representative of the operational cost of that link, creating a set or colony of exploratory agents at said first node, permitting the agents at said first node to explore the model network via the links and nodes between said first and second nodes, determining for each said agent the nodes and links visited by that agent whereby to inhibit more than one traversal of a said link by that agent, recording the results of exploration of the model network by providing on each traversed path a marker whose value relates to the total cost of the path and the number of agents selecting that path, and determining from said results a route favoured by a significant number of said agents and setting up said route on the telecommunications network, wherein each said agent arriving via a link at a network node selects a link by which to leave that node on a probability based choice weighted with the respective cost and marker values of the respective links whereby to select preferentially a link of lower cost.

2. A method as claimed in claim 1, wherein the marker has a value which is inversely proportional to the total cost associated with the traversed path.

3. A method as claimed in claim 2, wherein a further set of exploratory agents is created at said second node.

4. A method as claimed in claim 2, wherein said agents are created as successive generations, and wherein the response of said successive generations of agents to the cost of a link and the value of a marker on a path is developed via a genetic algorithm.

5. A method as claimed in any one of the preceding claims wherein the marker value decays with time.

7. A method as claimed in claim 3, wherein said agents are created as successive generations, and wherein the response of said successive generations of agents to the cost of a link and the value of a marker on a path is developed via a genetic algorithm.

6. Apparatus for operating a telecommunications network whereby to determine traffic routing within the network, said network comprising a plurality of nodes interconnected by communications links and each said link incorporating one or more communications channels, wherein the apparatus includes, means for providing a model of the network, means for determining in the model first and second nodes between which a communications path or route comprising a chain of links is to be established across the network, means for allocating to each said link a cost value representative of the operational cost of that link, means for creating a set or colony of exploratory agents at said first node and for permitting the agents at said first node to explore the model network via the links and nodes between said first and second nodes, means for determining for each said agent the nodes and links visited by that agent whereby to inhibit more than one traversal of a said link by that agent, means for recording the results of exploration of the model network by providing on each traversed path a marker whose value relates to the total cost of the path and the number of agents selecting that path, and means for determining from said results a route favoured by a significant number of said agents and setting up said route on the telecommunications network, wherein each said agent arriving via a link at a network node has means for selecting a link by which to leave that node on a probability based choice weighted with the respective cost and marker values of the respective links whereby to select preferentially a link of lower cost.