Routing calls with overflows in a private network

Details Routing calls with overflows in a private network Routing calls with overflows in a private network

1999-07-28

2004-11-02

Ton, Dang (Department: 2666)

Multiplex communications

Data flow congestion prevention or control

Flow control of data transmission through a network

C379S114020

Reexamination Certificate

active

06813246

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention consists in a method of routing a call in a private network with overflow to a public or other network.
The invention concerns private telecommunication networks. Such networks are formed of communication nodes connected by links carrying calls and/or signaling.
2. Description of the Prior Art
The Dijkstra algorithm is described in the literature on algorithms and calculates the shortest path between two nodes in a graph. The algorithm operates as follows: it considers a graph G with N nodes, which is valued, i.e. each existing path of which between two nodes i and j is assigned a value or weight I(i, j). it considers an outgoing node s of the graph G and an incoming node d; it seeks a path minimizing &pgr; (s, d), the distance from s to d, i.e. the sum of the values of the connections connecting s to d. S is the subgraph of G formed of the nodes x for which the minimum path to s is known, and {overscore (S)} is its complement. &Ggr;
i
is the set of nodes adjoining a given node i.
Initially the subgraph S contains only the node s, and {overscore (S)} contains all the other nodes, assigned the following initial values:
&pgr;(s, i)=I(s, i) for i∈&Ggr;
s
, the parent node being s;
&pgr;(s, d)=∞, for the other nodes, which have no parent node.
An iteration of the algorithm is effected in the following manner.
If {overscore (S)} is empty, or if it contains only nodes i with &pgr;(s, i)=∞, the algorithm has finished.
Otherwise, the node n of {overscore (S)} is considered which is nearest the originating node, i.e. the node which minimizes &pgr;(s, i), i∈{overscore (S)}; this node is taken from {overscore (S)} and placed in S.
The nodes adjacent this node n are then considered and the algorithm calculates
&pgr;(
s, n
)+
I
(
n, j
),
j∈&Ggr;
n
and
j∈{overscore (S)};
If this quantity is less than &pgr;(s, j), then &pgr;(s, j) is updated:
&pgr;(
s, j
):=&pgr;(
s, n
)+
I
(
n, j
)
and the parent node of j is also updated, which becomes n.
This operation is carried out for all the nodes of &Ggr;
n
, after which {overscore (S)} is reordered.
In this way, all the nodes of the graph are progressively added to S, in order of increasing path length. To find a path to a given node d, the algorithm can be interrupted before it finishes, since the destination node a has been added to the subgraph S.
The validity of the algorithm is demonstrated by the following reductio ad absurdum argument. Consider the node n nearest {overscore (S)} which must be added to S. If there is a nearer path, that path starts from s and arrives at n and has a first node m in {overscore (S)}. Then:
&pgr;(
s, m
)+&pgr;(
m, n
)<&pgr;(
s, n
)
and, since &pgr;(m, n) is positive or zero:
&pgr;(
s, m
)<
p
(
s, n
)
which contradicts the hypothesis. It is also clear that &pgr;(s, m) has been calculated in a preceding iteration, when adding the parent of m to S.
The document by J. Eldin and K. P. Lathia “Le RNIS appliqué au Centrex et au réseaux privés virtuels” [The ISDN applied to Centrex and to virtual private networks] contains a description of physical private networks and virtual private networks. As explained in the document, in a physical private network the various sites or nodes are connected by dedicated circuits but in a virtual private network each node is connected to the local switch nearest the public network, where appropriate software sets up the connections on demand. There are two variants of the virtual private network: on the one hand, semi-permanent connections can be provided, which are set up without dialing as soon as any of the nodes requires the circuit, and which always connect the same two points. Such may be the case in particular for signaling connections in an application on an integrated services digital network. On the other hand, switched connections can be provided, which can be set up only by dialing.
The remainder of the description considers only physical or virtual private networks formed of nodes connected by links, which can be of any type: dedicated connections, or links using an external network; the latter can be of any type—the public switched network, a public land mobile network, an integrated services digital network, another private network, etc.
FIG. 1
shows one example of a private network of this kind. This network includes, for example, nodes
1
to
6
; nodes
2
to
6
are connected to the public network
8
by circuit groups
12
to
16
. The nodes are interconnected by links formed of private connections, shown in bold in the figure, or, as in the case of the link between nodes
5
and
6
, by a link comprising only a signaling connection. For a digital link, each private connection comprises at least one access, formed by a signaling connection and a plurality of B channels. The link between nodes
5
and
6
in
FIG. 1
comprises a signaling connection and no B channel; this is typical of a node corresponding to a branch office, for which the volume of traffic is not very high.
The problem of overflow, i.e. the problem of a call request that cannot be satisfied by the network because its resources are congested, arises in private networks. This problem can arise if the private links of the private network have a fixed capacity, rather than a capacity which is allocated dynamically and which is less than the possible maximum volume of traffic. Completing the corresponding call using the public network is known in itself. In other words, if a user at node
2
wants to contact a user at node
6
, and if the private network is congested and cannot complete the call, the call is completed via circuit groups
12
and
16
and the public network. This can be the case, for example, if the connection between nodes
2
and
4
is congested. In
FIG. 1
, reference numeral
10
shows schematically a call of this kind via the public network. Overflow may also be necessary if the link in question has no B channel, as in the case of node
6
in FIG.
1
.
This solution gives rise to the following problems. On the one hand, using the public network incurs a cost; on the other hand, it is not certain that there is an access group to the public network for all the nodes; in the
FIG. 1
example, node
1
has no group providing access to the public network and as a result a call via the public network could be routed via group
12
of node
2
or group
13
of node
3
.
The invention proposes a solution to the above problems; it manages overflows from the private network in a way that minimizes the cost of access to the public network and maximizes the use of resources of the private network. It applies not only to overflows to the public network, but also and more generally to overflows to any type of network external to the private network: switched public network, public land or satellite mobile network, another private network, etc.
SUMMARY OF THE INVENTION
To this end, the invention proposes a method of routing a call in a private network, with overflow to another network, which comprises calculating various routes for setting up said call, with one or more overflows to said other network, and choosing a route as a function of the overflow cost and the number of overflows.
In one embodiment of the invention the choice is made from routes having a number of overflows less than a predetermined threshold value.
This predetermined threshold value is advantageously chosen as a function of the maximum call setup time. In one embodiment of the invention the predetermined value is 3.
The choice is preferably made to minimize a cost vector of routing the call, the cost vector having as one component the charge incurred because of the overflows and as one component the load of the links of the private network.
A first vector can be less than a second vector if the cost component of the first vector is less than the cost component of the second vector and, if the cost components are equal, if the load component of the first v

Affiliated with

Also associated with

Rating

Routing calls with overflows in a private network does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Routing calls with overflows in a private network, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Routing calls with overflows in a private network will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3350142