Multiplex communications – Data flow congestion prevention or control – Flow control of data transmission through a network
Reexamination Certificate
1999-10-12
2003-07-29
Cangialosi, Salvatore (Department: 2661)
Multiplex communications
Data flow congestion prevention or control
Flow control of data transmission through a network
C370S235000
Reexamination Certificate
active
06600722
ABSTRACT:
The present invention relates to telecommunications networks, and more particularly to routing calls in a telecommunications network, in particular a private network, in which calls present passbands that are different.
BACKGROUND OF THE INVENTION
Private telecommunications networks are constituted by communications nodes that are interconnected by links or trunks conveying calls and/or signaling. J. Eldin and K. P. Lathia, “Le RNIS appliqué au Centrex et aux réseaux privés virtuels” [ISDN applied to Centrex and virtual private networks] contains a description of physical private networks and virtual private networks. As explained in that document, in a physical private network, the various sites or nodes are interconnected by specialized circuits, whereas in a virtual private network, each node is connected to the nearest local switch of the public network where appropriate software establishes connections on request. Two varieties of virtual private network are in existence: it is possible firstly to provide semipermanent connections which are set up without dialing, as soon as one of the nodes needs a circuit, and which always interconnect the same two points. This can apply in particular for signaling connections in an application to an integrated services digital network. It is also possible to provide switched connections which can be set up only by dialing. In the description below, consideration is given to private networks which can be physical or virtual, that are made up of nodes interconnected by trunks that can be of any type: trunks comprising dedicated connections or trunks that are set up by traveling over an external network; the external network can be of any type—the public switched telephone network, a terrestrial mobile public network, an integrated services digital network, another private network, etc.
In telecommunications networks, there arises the problem of call routing, i.e. choosing a sequence of trunks enabling a call to be taken through the network, and where necessary with overflows to an external network. The purpose of such call routing is to enable a call to be carried by the network while seeking to even out call loading within the network. In conventional manner, routing calculations are performed by defining a cost function for the trunks of the network. This function makes it possible to give each trunk a function that is representative of the risk of that trunk becoming blocked; it is possible for the calculated cost function to choose the ratio between the resources required and the resources available on the trunk:
cost:=resources required÷resources available
Under such circumstances, the best routing is the routing which minimizes the sum of the costs of the trunks that make up the routing. As a general rule, routing calculation is performed for call-routing purposes at the time that a call is set up.
OBJECTS AND SUMMARY OF THE INVENTION
A novel problem to which the invention provides a solution is that of the frequency at which routing calculations need to be performed. In the prior art solution described above, the cost of routing over a given trunk depends on the resources required and therefore varies from one call to another. It is therefore necessary to repeat a routing calculation for each new call, even if a call has already been routed from the same originating node to the same destination node. That problem does not appear in the prior art where it has been taken for granted that routing calculations need to be performed when setting up a call.
In addition, in private networks there arises the problem of managing passbands. Insofar as networks carrying different types of call (voice, data, or other), different protocols propose, as different qualities of service, calls that have different passbands. For example this applies to the X25, Frame relay, and N×64 Kb/s circuit protocols. In some of those protocols, for example the X25 and Frame relay protocols, it is possible to fall back to narrower passbands if passband is in short supply.
Another novel problem to which the invention provides a solution is that of including passband management in call routing. Prior art solutions provide no guarantee concerning passband in the setting up of a call, and at best provide for falling back to a narrower passband.
The invention proposes a method of routing a call which makes it possible to manage passbands effectively, by making it possible to guarantee some particular quality of service. The solution of the invention also makes it possible to limit the number and the frequency of routing calculations.
To do this, the invention provides a method of routing a call in a network having a plurality of nodes interconnected by trunks, the method comprising calculating the costs of different routes for taking the call, with selection between routes being a function of cost, where the cost of a route is a function:
of the passband available on the trunks constituting the route;
of the resources available on said trunks; and
of the sum of the costs of the trunks constituting the route;
the cost of a trunk being a vector having a first component which is a function of the bandwidth available on the trunk and another component which is a function of the resources available on the trunk;
wherein the cost of a route is also a function of the bandwidth required for the call.
In a first variant, the first component is a function whose value is zero if the available bandwidth is greater than or equal to the bandwidth required for a call, and has a “saturated” value if the available bandwidth is less than the bandwidth required.
In a second variant, the first component is a function having the value zero if the available bandwidth is greater than or equal to the bandwidth required for a call, and a value equal to the difference between the bandwidth required and the bandwidth available if the bandwidth available is less than the bandwidth required.
In which case, the second component has a value that is constant for available resources that are above a predetermined quantity. The method of the invention then makes it possible to limit the number of routing calculations and to avoid performing new routing calculations so long as the topology of the network does not change.
Preferably, the second component is a function that has a finite number of possible values.
In another implementation, the second component is a decreasing function of the quantity of resources available.
Advantageously, the first component is a decreasing function of the bandwidth available.
Preferably, the step of selecting a route is performed in such a manner as to minimize the cost of the routing for an ordering relationship in which a first vector is less than a second vector if the first component of the first vector is less than the first component of the second vector, and if said first components are equal, the second component of the first vector is less than the second component of the second vector.
Advantageously, the vector sum of first and second vectors is defined as the vector whose first component is equal to the smaller of the first components of said first and second vectors, and whose second component is equal to the sum of the second components of the first and second vectors.
In an implementation, the step of calculating the various routes is performed by applying Dijkstra's algorithm.
The invention also provides apparatus for implementing the invention.
REFERENCES:
patent: 4345116 (1982-08-01), Ash et al.
patent: 4931941 (1990-06-01), Krishnan
patent: 5142570 (1992-08-01), Chaudhary et al.
patent: 6016306 (2000-01-01), Le Boudec et al.
patent: 6463051 (2002-10-01), Ford
patent: 6487289 (2002-11-01), Phan et al.
patent: 0 276 754 (1988-08-01), None
patent: 0 830 047 (1998-03-01), None
patent: WO 95/18498 (1995-07-01), None
Z. Wang et al, “Bandwidth-Delay Based Routing Algorithms”, IEEE Proceedings of the Global Telecommunications Conference, Nov. 14-16, 1995, vol. 3, pp. 2129-2133, XP000633662.
A. Bagchi, “Route Selection w
Phan Cao Thanh
Tran Nhut Quan
Alcatel
Cangialosi Salvatore
Sughrue & Mion, PLLC
LandOfFree
Routing calls in a telecommunications network on the basis... 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 in a telecommunications network on the basis..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Routing calls in a telecommunications network on the basis... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3080593