WO2005032064A1

WO2005032064A1 - A call routing method

Info

Publication number: WO2005032064A1
Application number: PCT/EP2004/010979
Authority: WO
Inventors: Miguel Pires
Original assignee: Siemens Aktiengesellschaft
Priority date: 2003-09-30
Filing date: 2004-09-29
Publication date: 2005-04-07
Also published as: GB0322835D0; GB2406739A; GB2406739B

Abstract

A call routing method involves the application of factors to the weights attributed to links in a communications network to provide modified links. The factors take into account the effect of the differing call priorities and requirements to minimise disruption to existing calls and services.

Description

A Call Routing Method

This invention relates to a call routing method for a communications network.

A communications network is made up of a number of network nodes linked by trunks conveying calls and signalling. Many of the nodes are routers concerned with the forwarding of received communications packets or streams, to the next node and thus through the network. Since each router will be connected to a number of other nodes there will be a number of possible routes through the network. Routing .algorithms .are applied by the routers to determine the route to be followed. One such .algorithm known in the .art is Dijkstra shortest path algorithm.

Some calls are more important than others and, in order to engender more flexibility in routing calls, the calls are also assigned different priorities. The priority of the calls is also taken into account by the routing algorithm. Such that a low priority call may be discarded in favour of one having a higher priority. That is to say the lower priority call may be disrupted in order to allow the higher one to be established. The disruption or discarding of the call is termed in the art as preemption.

In some networks, in particular, transport networks, a satisfactory priority based routing algorithm is difficult to implement. The reason for this is that unlike packet cell based networks, transport networks assign resources based on fixed time division or frequency division based slots. This means that the necessary resources are reserved exclusively on set-up of the service and may not be shared by any other service. Pre-emption of a call leads to disruption to the service which is not compatible with most services offered by transport networks.

It would be desirable for a protocol to avoid disruption of established services or to at least minimise the bandwidth being pre-empted on establishment of a higher priority.

The set-up of services in a transport network has been a manual task carried out by the network operator and the problem of pre-empting existing services was not so acute. (As it was a manual task and a human decision)

According to the invention there is provided a method of routing priority assigned calls in a communications network of a plurality of nodes connected by links having weights which method comprising; determining service parameters required by a call, deriving a graph based on the communications network, removing from the graph links which do not meet the service parameters required by the call to provide a resulting graph characterised in that the weights of the links in the resulting graph are modified prior to the application of a routing algorithm to change the probability of the links being chosen by the algorithm.

The preferred embodiment utilises a shortest path routing algorithm although other algorithms may be applicable. The shortest path algorithm may chose a route based on physical path length, the number of hops, the time taken to traverse a path (fastest path) taking into account queuing or other parameters or a combination of these or more normally to cost. Thus it is usual for the shortest path to be in reality the lowest cost route. It is typically referred to as the shortest path for historical reasons. The weights on the links are based on the parameters required by the routing algorithm to be applied and hence in the case of a shortest path algorithm are based on path length parameters The weights of the links are modified in the following manner. Where a link is determined as having insufficient available bandwidth to avoid pre-emption if the call is placed on the link then the weight is modified by a factor termed the aggravation factor to lower the probability of that link being chosen by the routing algorithm.

Preferably, the aggravation factor is based, at least in part, on; the difference between the priority of the new service being routed and the priorities of the services that would be pre-empted should the link be chosen for routing that service and or the amount of bandwidth being pre-empted at each priority.

A specific embodiment will now be described with reference to the drawings in which:

Figure 1 shows a communications network operating in accordance with the invention; and

Figure 2 is an explanatory diagram. As is shown in figure 1, a communications network 1 comprises a number of interlinked network nodes 2 to 11. The nodes are interlinked by links or trunks 12 to 23. The links are used to convey both calls and signalling through the network 1. It will be appreciated that the links will have different parameters. Some will have higher bandwidth than others or have more robustness. The interaction between the nodes and links are also considered to be parameters of the link. The interactions can include queuing time to and from the link at the node. The parameters include path length both physical and also in terms of time and other properties. These are termed the link weights or cost. The nodes are routers with node 2 serving also as a network manager. [In many networks there is no dedicated network manager and all the nodes are able to serve as network manager. For this, topological and resource usage information is constantly being updated on all nodes using specific desimination algorithms and protocols (e.g. OSPF, IS-IS). In some networks, the ingress node of a call (node 9 in this example) would serve as a network manager for the call.]

Let us consider a call being established from telecommunications equipment served by node 9 to equipment served by node 3. As is apparent from figure 1, there are a number of possible routes that may be utilised. For example, links 15, 17, 18,19; and 12, 13,16, 18, 21, 22, 20.

The network manger 2 carries out the route selections. As is shown in figure 2, in a first step 20 a graph of the possible routes from the calling node 9 to the receiving node 3 is derived. In essence this is as depicted in figure 1, nodes and links. Each of the links will be described by a weight and bandwidth available on the link. In a next step 21, the network manger 2 determines the type of service required by the new call and the parameters required of the link to support the call. This will include robustness of the link and bandwidth. The graph is then trimmed to remove all the links that could not meet the requirements of the call. In this particular case link 20 is unable to support the new call. Accordingly, the graph is trimmed to remove link 20, 22 and 21 and nodes 4 and 5.

In a next step 22, the aggravation factor is determined. For a priority scheme of x different priorities ranging from 0 (highest) to pmin (lowest, x-1) the fairness policy is expressed by pmax configurable aggravation factors which are called the Pre-emption Aggravation Factors (PAF[l..pmin]) to compute a Total Pre-emption Aggravation for one as follows: i) Let ReqBw be the bandwidth requested for a service at priority p and ResvBW[k] be the bandwidth reserved by services at priority k (all bandwidth expressed in an integer number), ii) At a given priority k, pmin>=k>p, let AffectedBw[k] be the .amount of bandwidth that would be pre-empted by the new service of higher priority. That is the bandwidth needed after the unreserved bandwidth and the one reserved at even lower priorities n, pmin>=n>k have been consumed. The AffectedBw[k] may be 0. iii) With the affected bandwidth found then the Total Pre-emption Aggravation is found from, TPA=sum_k=p+1..pmin(AffectedBw[k]*PAF[k-p]). The TPA accounts for the bandwidth at all lower priorities that may suffer by the fulfilment of the new call request. To distinguish between the importance of lower and higher priority services a multiplication factor is applied which varies with the separation of k and p. The PAF factor decays with increasing priority difference.

In the next step 23 the aggravation factor is applied to the weights on the links to modify them. In this the link will have an original weight, Orig Weight and it is aggravated by the TPA derived in step 22 to provide LinkWeight.

LinkWeight=OrigWeight*TPA.

The modified links .are then used in step 24 by a shortest path first routing algorithm to determine the best path to use. In this case the Dijkstra shortest path algorithm is used.

In carrying out this method a fair routing effort will result to preserve the largest bandwidth possible of those priorities closest to the priority of the request. By choosing the correct parameters, PAF free routes are chosen and links that would lead to pre-emption will be avoided. If pre-emption occurs, the method will minimise the impact on existing services.

In alternative forms of the invention, for some networks it may be appropriate to instead of letting the PAF factors depend only on the priority difference k-p, specific factors PAF[p,k] for each combination of p and k, p<k may be used. The TPA may also be applied to the original weight to give a modified weight in ways other than by multiplication. For example, by addition thus: LinkWeight= OrigWeight+TPA.

Claims

1. A method of routing priority assigned calls in a communications network of a plurality of nodes connected by links having weights which method comprising; determining service parameters required by a call, deriving a graph based on the communications network, removing from the graph links which do not meet the service parameters required by the call to provide a resulting graph characterised in that the weights of the links in the resulting graph are modified prior to the application of a routing algorithm to change the probability of the links being chosen by the algorithm.

2. A method as claimed in claim 1 wherein weights of the links are modified such that where a link is determined as having insufficient available bandwidth to avoid pre-emption if the call is placed on the link then the weight is modified by a factor termed the aggravation factor to lower the probability of that link being chosen by the routing algorithm.

3. A method as claimed in claim 2 wherein the aggravation factor is based, at least in part, on; the difference between the priority of the new service being routed and the priorities of the services that would be pre-empted should the link be chosen for routing that service and or the amount of bandwidth being pre-empted at each priority.

4. A method of routing priority assigned calls in a communications network of a plurality of nodes connected by links having weights substantially as hereinbefore described with reference to and as illustrated by the drawings.