Method for routing in loaded telecommunication networks

• US 6,816,585 B1
• Filed: 07/16/2001
• Issued: 11/09/2004
• Est. Priority Date: 12/07/1999
• Status: Expired due to Term

• Current Assignee: ECI Telecom Limited (Shaul Shani)
• Original Assignee: ECI Telecom Limited (Shaul Shani)
• Inventors: Blatt, Marcelo, Peled, Noga
• Primary Examiner(s): Bui, Bing Q.
• Application Number:
  US09/889,387
• Time in Patent Office: 1,212 Days
• Field of Search: 379/114.02, 379/221.01, 379/221.03, 379/272, 379/273, 379/909, 379/112.02, 379/112.08
• US Class Current: 379/221.03
• 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/122 by minimising distances, e.g. by selecting a route with minimum of number of hops
• CPC Class Codes: H04L 45/302 Route determination based on requested QoS

Abstract

A method for routing of incoming prioritized telecommunication traffic in a telecommunication network by applying an algorithm of finding optimal path to an augmented graph built for said telecommunication network. The telecommunication network is represented as a network graph comprising nodes (A, B, C, D, E) and real links (AB, BC, CD, ED, AE) bridging the nodes, while the augmented graph is a graph built on the basis of the network graph by adding to it virtual links (ABC1, . . . , EDC3). The augmented graph comprises nodes and edges, wherein the edges of the augmented graph are weighed to reflect priority of the telecommunication traffic presently taking place there-through. For placing a new call according to the method, a pathfinder optimization algorithm is applied to the augmented graph to determine an optimal pathfinder solution, having the minimal total weight, for routing the new call in the augmented graph. When the optimal pathfinder solution is determined, links in the network graph corresponding to the solution can be allocated for real routing, and the augmented graph can be updated to reflect changes in the network.

Claims

1. A method for routing of incoming telecommunication traffic, having priority, in a telecommunication network, the method comprising applying an algorithm of finding optimal path(s) to an augmented graph built for said telecommunication network and comprising nodes and edges, wherein the edges of the augmented graph are weighted to reflect priority of telecommunication traffic presently taking place there-through.

2. The method according to claim 1, wherein said telecommunication traffic comprises one or more calls of at least one type selected from a non-exhaustive list comprising voice, fax and data.

3. The method according to claim 1 or 2, wherein

said telecommunication network being represented as a network graph comprising nodes and real links each bridging a pair of the nodes, and

said augmented graph being a graph built on the basis of the network graph by adding to it virtual links;

the nodes of the augmented graph constituting the nodes of the network graph;

both real and virtual links being considered the edges of the augmented graph.

4. The method according to claim 2, comprising the following steps:

building the augmented graph of the telecommunication network,

weighting each edge of the augmented graph to reflect the priority of calls presently taking place there-through;

obtaining one or more new calls, each defined by end-point nodes and a particular priority;

applying a pathfinder optimization algorithm to the augmented graph to determine an optimal pathfinder solution, having the minimal total weight, for routing said one or more new calls in the augmented graph;

if said optimal pathfinder solution is determined, allocating corresponding to it links in the network graph for routing said one or more new calls in the telecommunication network;

providing for placing said one or more new calls via the allocated links by ensuring that, if necessary, call(s) having lower priorities and currently held by the allocated links be dropped therefrom;

updating the augmented graph to reflect changes in the network, and

returning to the step of obtaining one or more new calls.

5. The method according to claim 4, wherein the step of building the augmented graph includes building an optimal augmented graph by

defining call paths respectively used by the calls currently taking place in the network, said call paths being formed by nodes connected with real links, and

converting said call paths into complete sub-graphs, wherein each two nodes of any of said complete sub-graphs are connected with an edge being either a real link or a virtual link.

6. The method according to one of claims 4 and 5, wherein said changes in the network include at least one, selected from the following non-exhaustive list comprising:

adding said one or more new calls routed via one or more links;

dropping said one or more of previously held calls due to placing said one or more new calls,

terminating currently existing calls,

a failure of at least one link in the network,

reconsidering the length parameter of the links.

7. The method according to one of claims 4 and 5, comprising routing of one new call at a time, and wherein said pathfinder optimization algorithm is a shortest path algorithm for determining a shortest path between the end-point nodes, said path comprising one or more component edges and being characterized by the minimal weight and the priority lower than that of the new call.

8. The method according to claim 7, wherein the weight of the shortest path is a sum of weights of the component edges, and the priority of the shortest path is considered to be the maximal among the priorities of the component edges.

9. The method according to claim 1, wherein lower priorities are designated with smaller numbers, and the absence of traffic is designated with the lowest priority, so that the less intensive and less significant the traffic via an edge, the smaller the priority and weight of the edge.

10. The method according to any one of claims 4 to 9 wherein the weighing is performed to also reflect a length parameter of the edges.

11. The method according to claim 10, wherein the length parameter is a function of at least one argument associated with a link and being selected from a non-exhaustive list comprising distance, tariff and administrative cost.

12. The method according to claim 9, wherein priority of any of the edges of the network is the minimal priority among those of calls passing or able to pass through the edge.

13. The method according to claim 9, wherein edges having the priority higher than that of a new call are considered non-existent in the augmented graph.

14. The method according to claim 1, wherein the weighting of edges of the augmented graph comprises determining a current weight W to each edge connecting nodes “

x” and

“

y”

, wherein the current weight being considered the minimal weight among component weights of calls passing and able to pass via the edge;

each of the component weights being a function of the respective call priority P and the length parameter L of the edge;

15. The method according to claim 14, wherein the coefficient “

k”

reflects rules empirically set for the network, for managing calls having different priorities;

the maximal value of said coefficient being calculated as the maximal number of possible calls of priority P in the network;