Telephonic communications – Plural exchange network or interconnection – With interexchange network routing
Reexamination Certificate
2001-07-16
2004-11-09
Bui, Bing Q. (Department: 2642)
Telephonic communications
Plural exchange network or interconnection
With interexchange network routing
C379S114020, C379S221010, C379S272000, C379S273000
Reexamination Certificate
active
06816585
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to a method of routing telephone or data calls in modern telecommunication networks, especially under high traffic load conditions.
BACKGROUND OF THE INVENTION
It is becoming more and more complicated to manage telecommunication networks in today's communication environment due to the growing traffic load. One of the complex tasks of networks management is routing calls having different priorities.
Generally, a telecommunication network such as a TDM based telephone network may be represented as comprising nodes and links. Each node constitutes a transfer point that is typically a network element (NE), for example a Digital Cross Connect device. The links are made up of carrier lines, such as E1/T1 lines for transmitting telephone calls say, from a local exchange to an access network. Routing paths between nodes are typically set up in advance and do not change dynamically. In the telephone network, calls addressed to a destination node are simply assigned to the path that connects the ingress node to the egress node and comprises a number of links.
There are known algorithms for setting up the shortest path between two nodes i.e., the algorithms attempting to allocate the network resources efficiently. One of such algorithms is the Dijkstra's algorithm, which can be used to find the shortest path between any two nodes in a particular system. Such algorithms usually allow for a single weighing factor for each link between the nodes, which factor is typically used to compare relative costs of different transmission links. Mathematically, the so-called “shortest path algorithms” use representations of the network as a graph in which nodes are called “vertices” and links (direct connections between two vertices) are called “edges”.
It should be noted that, the traffic in the modern telecommunication networks is typically of different priority levels, which fact is not taken into account in the above-mentioned “shortest path algorithms”.
A common situation which usually takes place in telecommunication networks today is the following: a new call having a particular priority arrives and should be routed through the network, while the network is fully loaded with calls having various priorities. Actually, the problem arises when at least a portion of the network, required for a routine routing, appears to be busy. A similar situation may be raised when one of the links of the system fails and its traffic needs to be rerouted. The goal would be to allocate the new demand using the available resources, or in case there is no enough resources—to insert the new call by dropping some traffic.
Different approaches exist of how to define criteria of dropping the traffic in such cases and how to perform the above task based on the criteria defined.
All the traffic is usually divided into streams having different priorities, and each call usually has an associated priority. Every link of the network can be given a current link priority selected according to the traffic passing through the link.
For example, all lower priority links can be selected to form a pool of available links to be processed by the Djiaekstra algorithm. The algorithm will then find the shortest path, and the links forming the shortest path will be reassigned for the new demand (i.e. the existing lower priority traffic will be dropped and the links will handle the higher priority traffic). This can be done per one priority level at a time until a satisfactory solution is found. The method suffers form a number of disadvantages: firstly, it is multistage and secondly- it is far from optimum because of the criteria chosen, i.e., the priorities are taken into account in a straight-forward way. In other words, if a very convoluted path consisting of many low priority links is found, the algorithm will block all these links irrespective of the number of paths involved. However, there might be a solution that blocks few links of a slightly higher priority—but this solution will not be revealed.
SUMMARY OF THE INVENTION
It is therefore the purpose of the present invention to provide a method allowing optimization of routing and rerouting in a network with traffic characterized by various priorities.
Continuing the topic concerning the criteria of dropping part of existing traffic for embedding a new demand in the network, there have been proposed the following three criteria (in the order of decreasing importance). The criteria are formulated for ensuring the result with producing the smallest perturbation to the network having a number of links:
1. Disable call paths (which are also named calls or connections) with the lowest priority first;
2. Disconnect the smallest number of call paths;
3. Chose the shortest path in the network using links which can be freed from calls according to criteria (1) and (2).
In other words, in the ideal situation, it would be desired to only abandon or block traffic of the lowest priority and at minimal number of paths (i.e. minimal number of calls) and links.
In order to take into account all these criteria in the process of routing one or more calls in a telecommunication network, a new method has been proposed by the Inventors.
The new approach is based on applying an algorithm of finding optimal path(s) to an augmented graph built for a telecommunication network, wherein all edges of the augmented graph are weighed to reflect priority of telecommunication traffic presently taking place there-through.
The calls mentioned above (both those forming the telecommunication traffic, and the new ones) should be considered any of the known types of telecommunication transmission including voice, fax, data, etc.
It should be explained that any telecommunication network comprises a plurality of network elements and a plurality of physical connections each bridging a pair of the network elements. A conventional network may be represented as a connected network graph comprising nodes and links, wherein the nodes respectively correspond to the network elements, while the links interconnect said nodes and respectively correspond to the connections physically existing between the network elements of the network.
The augmented graph, in the frame of the present application, should be understood as a graph built on the basis of the network graph having nodes and real links, by adding to it virtual links; both real and virtual links being considered edges of the augmented graph. The maximal form of the augmented graph is a complete graph where each two nodes are connected by an edge. While weights of the real links reflect real telecommunication traffic presently taking place there-through, weights of the virtual links in the augmented graph are to reflect virtual telecommunication traffic (for purposes which will become apparent from the following description).
In other words, the method of routing calls having priorities in a telecommunication network comprises the following steps:
building an augmented graph of the network, the augmented graph comprising nodes and edges;
weighing 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 (in other words, determining optimal path(s));
if said optimal pathfinder solution is determined, allocating corresponding to it links in the network graph for routing the 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 on changes whenever take place in the network, and
returning to the step of obtaining one or more new calls.
The above-me
Blatt Marcelo
Peled Noga
Browdy and Neimark , P.L.L.C.
Bui Bing Q.
ECI Telecom Ltd.
LandOfFree
Method for routing in loaded telecommunication networks does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for routing in loaded telecommunication networks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for routing in loaded telecommunication networks will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3361891