Enhancement of network operation and performance

A set of logical networks is established on top of a physical network Next, a predefined objective function, closely related to the operation and performance of the physical network, which physical network is viewed as the set of logical networks, is optimized with respect to at least one set of decision variables. Finally, the decision variables in accordance with the optimization are used to control the operation of the overall network system. Physical transmission resources are partitioned among logical networks. Traffic loads are distributed among routes interconnecting the nodes of node pairs.

TECHNICAL FIELD OF THE INVENTION 
The present invention relates to telecommunication networks and in 
particular to overall network performance. 
BACKGROUND ART 
A main characteristic of a modern telecommunication network is its ability 
to provide different services. One efficient way of providing said 
services is to logically separate the resources of a physical 
network--resource separation (see FIG. 1). On top of a physical network PN 
there is established a number of logical networks LN, also referred to as 
logical or virtual subnetworks, each of which comprises nodes N and 
logical links LL interconnecting the nodes. Each logical network forms a 
logical view of parts of the physical network or of the complete physical 
network. In particular, a first logical network LN1 comprises one view of 
parts of the physical network and a second logical network LN2 comprises 
another view, different from that of the first logical network. The 
logical links of the various logical networks share the capacities of 
physical links present in said physical network. 
A physical network comprises switches S (physical nodes) or equivalents, 
physical links interconnecting said switches, and various auxiliary 
devices. A physical link utilizes transmission equipment, such as fiber 
optic conductors, coaxial cables or radio links. In general, physical 
links are grouped into trunk groups TG which extend between said switches. 
There are access points to the physical network, to which access points 
access units, such as telephone sets and computer modems, are connected. 
Each physical link has limited transmission capacity. 
FIG. 2 is a simple schematic drawing explaining the relationship between 
physical links, logical links and also routes. A simple underlying 
physical network with physical switches S and trunk groups TG, i.e. 
physical links, interconnecting the switches is illustrated. On top of 
this physical network a number of logical networks are established, only 
one of which is shown in the drawing. The logical networks can be 
established by a network manager, a network operator or other 
organization. In our Swedish Patent Application 9403035-0, incorporated 
herein by reference, there is described a method of creating and 
configuring logical networks. The single logical network shown comprises 
logical nodes N1, N2, N3 corresponding to physical switches S1, S2 and S3 
respectively. Further, the logical network comprises logical links LL 
interconnecting the logical nodes N1-N3. A physical link is logically 
subdivided into one or more logical links, each logical link having an 
individual traffic capacity referred to as logical link capacity. It is 
important to note that each logical link may use more than one physical 
link or trunk group. To each node in each logical network there is usually 
associated a routing table, which is used to route a connection from node 
to node in the particular logical network starting from the node 
associated with the terminal that originates the connection and ending at 
the node associated with the terminal which terminates said connection. 
Said nodes together form an origin-destination pair. A node pair with two 
routes is also illustrated. One of the routes is a direct route DR while 
the other one is an alternative route AR. In the figures, the links and 
the routes may be interpreted as being bidirectional. 
In order to avoid misconceptions the following definitions will be used: A 
route is a subset of logical links which belong to the same logical 
network, i e. a route have to live in a single logical network. Note that 
it can be an arbitrary subset that Is not necessarily a path in the graph 
theoretic sense. Nevertheless, for practical purposes, routes are 
typically conceived as simple paths. The conception of a route is used to 
define the way a connection follows between nodes in a logical network. A 
node pair in a logical network, the nodes of which are associated with 
access points, is called an origin-destination (O-D) pair. In general, all 
node pairs in a logical network are not O-D pairs, but instead some nodes 
in a logical network may be intermediate nodes to which no access points 
are associated. A logical link is a subset of physical links. 
Information, such as voice, video and data, is transported In logical 
networks by means of different bearer services. Examples of bearer 
services are STM 64 (Synchronous Transmission Mode with standard 64 
kbit/s), STM 2 Mb (Synchronous Transmission Mode with 2 Mbit/s) and ATM 
(Asynchronous Transfer Mode). From a service network, such as PSTN (Public 
Switched Telephone Network) and B-ISDN (Broadband Integrated Services 
Digital Network) a request is sent to a logical network that a connection 
should be set up in the corresponding logical network. 
Although the physical network is given, it is necessary to decide how to 
establish logical networks on top of the physical network and how to 
distribute or partition said physical network resources among logical 
networks by subdividing physical link capacities into logical link 
capacities associated with said logical networks. Since the logical 
networks share the same given physical capacities, there is a trade-off 
between their quality: GoS (Grade of Service) parameters, call blocking 
probabilities etc. can be improved in one of the logical networks only at 
the price of degrading the quality in other logical networks. It is a 
highly non-trivial task to find the partitioning of resources so as to 
optimize the overall network performance, in particular when considering a 
large and complex network. Furthermore, the network performance is also 
affected by the distribution of offered traffic load among the routes 
which can realize communication even within a single network. It is the 
management and dimensioning of a resource separated network to which the 
present invention is directed. 
RELATED TECHNIQUE 
A method for adaptive link capacity control, and the integration of call 
admission control and link capacity control, by using distributed neural 
networks is disclosed in the article entitled "Integration of ATM Call 
Admission Control and Link Capacity Control by Distributed Neural 
Networks" by A. Hiramatsu in IEEE Journal on Selected Areas in 
Communications, vol. 9, no. 7 (1991). At first neural networks are trained 
to estimate the call loss rate given the link capacity and observed 
traffic. Next, an objective function of the link capacity assignment 
optimization problem, constituted by the maximum call loss rate in the 
network, is optimized by a simple random optimization method according to 
the estimated call loss rate. 
The method of Hiramatsu only considers the optimization problem on the 
level of logical links. The concept of logical networks is not at all 
incorporated in the approach of Hiramatsu. Besides, the optimization 
method, the Matyas random optimization method, is a simple method 
generally leading to a suboptimal solution. Also, only one bit-rate class 
is considered in the model. 
The article "Algorithms for reconfigurable networks" in Teletraffic and 
Datatraffic in a period of change, ITC 13 (1991) by G. Gopal et al. 
relates to an optimal logical network design method for a reconfigurable 
network, i.e. a network which can change between logical networks. The 
weighted blocking averaged over all source-destination pairs, is minimized 
by a simple heuristic algorithm. Subsequently, the logical network is 
reconfigured according to this minimization. 
According to the method of Gopal et al. there exists a number of possible 
logical network configurations. However, only one logical network can be 
used in a certain traffic situation. This single logical network can be 
reconfigured in accordance with the heuristic minimization algorithm. 
Furthermore, the configuration of the single logical network is not at all 
based on e.g. traffic types, but is instead closely related to the given 
physical network. Besides, Gopal uses a very simple estimation of route 
blocking which is adequate only for small networks. Moreover, in the 
method of Gopal et al. the problem is formulated as a non-linear integer 
problem and due to this fact the results are in general suboptimal. 
In the article "Routing and Capacity Allocation in Networks with Trunk 
Reservation" in Mathematics of Operations Research, vol. 15., no. 4, 
(1990) by F. P. Kelly the derivatives of an implicitly defined revenue 
function are calculated. The use of these derivatives in the management of 
a single service network carrying single rate traffic with the emphasis on 
trunk reservation is suggested. 
In the U.S. Pat. No. 4,744,028 a method and apparatus for optimizing 
resource allocation is disclosed. More specifically, a linear programming 
approach is described which proceeds in the interior of a polytope 
solution space. Each successive approximation of the solution point, and 
the polytope, is normalized such that the solution point is at the center 
of the normalized polytope. The objective function of the linear 
programming model is then projected into the normalized space and the next 
step is taken in the direction of the steepest decent of the objective 
function gradient and such as to remain within the interior of the 
polytope. The process is repeated until the optimum solution is closely 
approximated. 
The method described in the above U.S. Patent assumes that the resource 
allocation problem can be adequately described by a linear programming 
model. In its application to resource allocation, such a model consists of 
a number of linear expressions representing the quantitative relationships 
between the various possible allocations, their constraints and their 
costs, i.e. the objective function is a linear function of the allocated 
resources. Moreover, the method according to the above U.S. patent does 
not take teletraffic models, such as e.g. Erlang's B formula, describing 
the statistical fluctuation of traffic, into consideration. Consequently, 
the linear programming model described in the above U.S. patent is quite 
unsatisfactory. The partitioning problem that the present invention 
considers gives rise to an objective function that depends on the 
allocated resources in an indirectly defined non-linear way. The 
dependence is defined through a complicated non-linear system of equations 
that follows from a teletraffic model. 
SUMMARY OF THE INVENTION 
On top of a physical network a number of logical networks are established 
in which logical links, used by routes, share the same physical 
transmission and switching resources. There are several reasons for 
logically separating physical resources. Logical resource separation for 
offering different Grade of Service classes, virtual leased networks with 
guaranteed resources and peak rate allocated virtual paths are some 
examples of interesting features in the design, dimensioning and 
management of physical networks. However, it is still necessary to decide 
how to distribute or partition said physical network resources among the 
logical networks. In addition, the distribution of offered traffic load 
among routes interconnecting the nodes of node pairs in the logical 
networks will also affect the overall network performance. 
In accordance with the present invention a set of logical networks is 
established on top of a physical network, which physical network comprises 
physical transmission and switching resources. The logical networks 
comprise nodes and logical links extending between the nodes so as to form 
the logical networks. The logical links are used by routes interconnecting 
the nodes of node pairs in the logical networks. Next, in accordance with 
a main aspect of the present Invention, an objective function which is 
closely related to the operation and overall performance of the resource 
separated physical network is optimized with respect to at least one set 
of decision variables, given physical network parameters and the 
requirements of each logical network. Examples of objective functions are 
the carried traffic in the complete network, the link utilization and the 
network revenue or some other function representing resource utilization 
or network performance. Two sets of decision variables are the logical 
link capacities, and the load sharing variables controlling the 
distribution of offered traffic load among routes. 
Each set of decision variables is related to a separate aspect of the 
invention. If the objective function have been optimized with respect to 
the logical link capacities then the physical transmission resources of 
the physical network are allocated among the logical links of the various 
logical networks in accordance with the optimization. On the other hand, 
if the objective function have been optimized with respect to the load 
sharing variables, then the offered traffic load is distributed, for each 
individual node pair in each one of the logical networks, among the routes 
interconnecting the nodes of the individual node pair, in accordance with 
the optimization. 
Furthermore, optimizing with respect to both the logical link capacities 
and the load sharing variables relates to yet another aspect of the 
present invention. In this particular case, the physical transmission 
resources of the physical network are allocated among the logical links of 
the various logical networks and the offered traffic load is distributed, 
for each individual node pair in each one of the logical networks, among 
the routes interconnecting the nodes of the individual node pair, in 
accordance with the optimization. 
In accordance with a first aspect of the present invention there is 
provided a method and device for partitioning physical transmission 
resources among logical networks. 
In accordance with a second aspect of the present invention there is 
provided a method and device for distributing offered traffic load among 
routes interconnecting the nodes of node pairs. 
In accordance with a third aspect of the present invention there is 
provided a method and device for partitioning said physical transmission 
resources among logical networks and distributing offered traffic load 
among routes interconnecting the nodes of node pairs.

PREFERRED EMBODIMENTS OF THE INVENTION 
An important tool in network management, particularly the management and 
dimensioning of large ATM networks, is the distribution of resources of a 
physical network among logical networks that share the capacity of the 
physical network. There are several advantages of logical resource 
separation: 
It has gradually been recognized in the last couple of years that it is not 
at all easy to integrate services with very different demands to e.g. 
bandwidth, grade of service or congestion control functions. In some cases 
it turn out to be better to support different services by offering 
separate logical networks, and limiting the degree of integration to only 
partial rather than complete sharing of physical transmission and 
switching resources. Network management can be simplified if service 
classes are arranged into groups in such a way that only those of similar 
properties are handled together in a logical network. For example, delay 
sensitive and loss sensitive service classes can possibly be managed and 
switched easier if the two groups are handled separately in different 
logical subnetworks, rather than all mixed on a complete sharing basis. 
Moreover, in this way they can be safely handled on call level without 
going down to cell level as e.g. in priority queues. Of course, within a 
logical network statistical multiplexing, priority queuing and other 
mechanisms can still be applied among service classes that already have 
not too different characteristics; 
Important structures such as virtual leased networks, required by large 
business users, and virtual LAN's are much easier to implement; 
A Virtual Path (VP), a standardized element of ATM network architecture, 
can be considered as a special logical network; 
The physical network operates more safely. 
A physical network, e.g. a large telecommunication network, with physical 
resources is considered. In FIG. 1 there is illustrated a physical network 
PN on top of which a set of logical networks LN1, LN2, . . . , LNX 
(assuming there are X logical networks) is established. Each logical 
network comprises nodes N and logical links LL interconnecting the nodes. 
The topology of these logical or virtual networks will in general differ 
from the topology of the underlying physical network. 
The network system is preferably controlled by an operation and support 
system OSS. An operation and support system OSS usually comprises a 
processor system PS, terminals T and a control program module CPM with a 
number of control programs CP along with other auxiliary devices. The 
architecture of the processor system is usually that of a multiprocessor 
system with several processors working in parallel. It is also possible to 
use a hierarchical processor structure with a number of regional 
processors and a central processor. In addition, the switches themselves 
can be equipped with their own processor units in a not completely 
distributed system, where the control of certain functions are 
centralized. Alternatively, the processor system may consist of a single 
processor, often a large capacity processor. Moreover, a database DB, 
preferably an interactive database, comprising e.g. a description of the 
physical network, traffic information and other useful data about the 
telecommunication system, is connected to the OSS. Special data links, 
through which a network manager/operator controls the switches, connect 
the OSS with those switches which form part of the network system. The OSS 
contains e.g. functions for monitoring and controlling the physical 
network and the traffic. 
From this operation and support system OSS the network manager establishes 
a number of logical networks on top of the physical network by associating 
different parts of the traffic with different parts of the transmission 
and switching resources of the physical network. This can e.g. be realized 
by controlling the port assignment of the switches and cross connect 
devices of the physical network, or by call admission control procedures. 
The process of establishing logical networks means that the topology of 
each one of the logical networks is defined. In other words, the structure 
of the nodes and logical links in each logical network is determined. 
Conveniently, traffic classes are arranged into groups in such a way that 
those with similar demands to bandwidth are handled together in a separate 
logical network. By way of example, all traffic types requiring more than 
a given amount of bandwidth can be integrated in one logical network, and 
those traffic types that require less bandwidth than this given amount can 
be integrated in another logical network. In other words, the two traffic 
groups are handled separately in different logical subnetworks. In 
particular, this is advantageous for an ATM network carrying a wide 
variety of traffic types. However, in one embodiment of the present 
invention, each individual traffic type is handled in a separate logical 
network. 
Preferably, the present invention is applied in the B-ISDN (Broadband 
Integrated Services Digital Network) environment. A fully developed B-ISDN 
network will have a very complex structure with a number of overlaid 
networks. One conceptual model suitable of describing overlaid networks is 
the Stratified Reference Model as described in "The stratified Reference 
Model: An Open Architecture to B-ISDN" by T. Hadoung, B. Stavenow, J. 
Dejean, ISS'90, Stockholm. In FIG. 3 a schematic drawing of a B-ISDN 
network from the viewpoint of the Stratified Reference Model is 
illustrated (the protocol viewpoint to the left and the network viewpoint 
to the right). Accordingly, the B-ISDN will consist of the following 
strata. A transmission stratum based on SDH (Synchronous Digital 
Hierarchy) or equivalent (SONET) at the bottom, a cross connect stratum 
based on either SDH or ATM (Asynchronous Transfer Mode) on top of that, 
which acts as an infrastructure for the ATM VP/VC stratum with switched 
connections. Finally, the large set of possible applications uses the 
cross connect stratum as an infrastructure. In one particular embodiment 
of the present invention it is the infrastructure network modelling the 
cross connect stratum in a B-ISDN overlaid network that is considered. In 
general, this infrastructure network is referred to as a physical network. 
Of course, it is to be understood that the present invention can be applied 
to any physical telecommunication network. 
FIG. 4 shows a schematic flow diagram illustrating a method in accordance 
with a general inventive concept of the present invention. In accordance 
with the present invention a set of logical networks is established on top 
of a physical network comprising physical transmission and switching 
resources, said logical networks comprising nodes and logical links 
extending between the nodes so as to define the topology of said logical 
networks. Preferably, the logical networks are completely separated from 
each other. The logical links are used by routes interconnecting the nodes 
of node pairs in the logical networks. Next, a predefined objective 
function, closely related to the operation and performance of the physical 
network, which physical network is viewed as the set of logical networks, 
is optimized with respect to decision variables. Finally, the decision 
variables in accordance with the optimization are used to control the 
operation of the overall network system. 
The physical transmission resources, i.e. the transmission capacities of 
the physical links, have to be partitioned or distributed among the 
logical links of said logical networks in some way. In this context, a 
natural objective is to partition the physical transmission resources so 
as to optimize the operation of the complete physical network, viewed as 
the set of logical networks, according to a given predefined objective 
function. 
It is important to note that the logical networks share the same given 
physical transmission and switching resources, which means that the 
operation of the physical network has to be optimized with respect to all 
the logical networks, i.e. the complete set of logical networks, at the 
same time. 
As indicated in FIG. 3 the cross connect stratum can be realized by either 
SDH or ATM. If the cross connect stratum is based on SDH and the 
infrastructure network is realizing e.g. different quality of service 
classes by resource separation, the partitioning can only be performed in 
integer portions of the STM modules of the SDH structure. On the other 
hand, if the cross connect is realized by ATM virtual paths then no 
integrality restriction exists and the partitioning can be performed in 
any real portions. Therefore, whether the cross connect stratum is based 
on SDH or ATM will have important implications for the partitioning of the 
physical network resources. The SDH cross connect solution gives rise to a 
model that is discrete with regard to the logical link capacities, while 
the ATM cross connect solution gives rise to a continuous model. The 
continuous model requires that the ATM switches support partitioning on 
the individual input and output ports. For example, this is realized by 
multiple logical buffers at the output ports. In a preferred embodiment of 
the invention an infrastructure network modelling the ATM cross connect 
stratum is considered while in an alternative embodiment an infrastructure 
modelling the SDH cross connect is considered, as can be seen in FIG. 1. 
At the first glance it might appear that partitioning, as opposed to 
complete sharing, is a reduction of the full flexibility of ATM. This is 
however not the case if the partitioning is considered on a general level. 
On a conceptual level the complete sharing schemes, e.g. priority queuing, 
Virtual Spacing etc. tell us how to realize resource sharing on the cell 
level, while the partitioning approach seeks for the call scale 
characteristics, e.g. how to assign rates to various logical links, that 
is then to be realized on the cell level. In this sense the complete 
partitioning approach complements, rather than excludes, the complete 
sharing approaches. 
In accordance with a preferred embodiment of the present invention, it is 
considered as a reasonable goal to achieve maximum carried traffic in the 
complete physical network. The advantages of using this quantity is that 
it is well expressed in analytical form and also closely related to the 
practical aspects of network operation. Therefore, the objective function 
according to the present invention is preferably defined as the total 
carried traffic, although other objective functions can be used. Examples 
of other objective functions are the link utilization in the complete 
network, the network revenue or some other function representing resource 
utilization or network performance. 
In other words, the optimization associated with resource partitioning is 
to calculate, given a description of the physical network, the topology of 
the logical networks, the traffic types, the routes in each of the logical 
networks and also the offered traffic to each route or to each node pair 
in each logical network, the logical link capacities for the corresponding 
logical networks so as to maximize the total carried traffic or the 
network revenue. 
Mathematical Framework 
Consider a fixed physical network with N nodes and K physical links, on top 
of which a number of logically separated logical networks are established. 
If the total number of logical links over all logical networks is denoted 
by J, and the capacity of an individual logical link j is denoted C.sub.j, 
then the vector of logical link capacities over all logical networks can 
be written as C=(C.sub.1, C.sub.2, . . . , C.sub.j). These logical link 
capacities are not known in advance. In fact it is desired to optimize 
them. 
The incidence of physical and logical links is expressed by a K.times.J 
matrix S in which the J:th entry in the k:th row is equal to 1 if logical 
link j needs capacity on the k:th physical link, otherwise said entry is 
0. Naturally, the sum of logical link capacities on the same physical link 
cannot exceed the capacity of the physical link. This physical constraint 
can be expressed as 
EQU SC.ltoreq.C.sub.phys, 
where C is defined above, and C.sub.phys refer to the vector of given 
physical link capacities. In addition it is required that C24 0. 
Assume that I traffic types are carried in the complete network. The role 
of these traffic types is primarily to handle different bandwidth 
requirements, but traffic types can be distinguished also with respect to 
different holding times or even priorities (trunk reservation). By 
convention, each route carries only a single type of traffic. This means 
that if several traffic types are to be carried, they are represented by 
parallel routes. In what follows, .upsilon. denotes logical networks, p 
denotes node pairs (O-D pairs) and i (sometimes also g) denotes traffic 
types. 
The incidence of routes, logical links and traffic types is expressed by 
the variables A.sub.ijr which are equal to 1 when route r uses logical 
link J and carries traffic type i, otherwise said variables are 0. 
A.sub.ijr is not to be interpreted as the amount of bandwidth that route r 
requires on logical link J. For that purpose other variables are used: 
a.sub.ij will denote the amount of bandwidth (capacity) that a call 
belonging to traffic type i requires on logical link j. By this notation 
it is implicitly assumed that all routes that carry a given traffic type i 
require the same amount of bandwidth on link j. Since the bandwidth 
requirement is associated with the traffic type, this is not seen as a 
restriction. On the other hand, the bandwidth requirement of calls on a 
given route is allowed to vary along the logical links of the route. In 
fact, this is needed if the concept of effective or equivalent bandwidth 
is adopted and the involved logical links have different capacities. 
A number of fixed routes in each one of the logical networks is assumed 
given in advance. Let R be the total set of routes over all logical 
networks, that is, 
##EQU1## 
where R.sup.(.upsilon.,p,i) is the set of routes in logical network 
.upsilon. realizing communication between node pair p regarding traffic 
type i. It is important to understand that a route is not associated with 
more than one logical network. Each logical network is assumed to operate 
under fixed non-alternate routing. 
Let .kappa..sub.r be the Poissonian call arrival rate to route r, let 
1/.mu..sub.r be the average holding time of calls on route r and let 
.nu..sub.r =.kappa..sub.r /.mu..sub.r be the offered traffic to route r. 
Let .nu..sub.(.upsilon.,p,i) be the aggregated offered traffic of type i 
to node pair p in logical network .nu.. In a preferred embodiment the 
offered traffic for each route in each logical network is given while in 
another preferred embodiment of the invention the above aggregated offered 
traffic is given for all logical networks, node pairs and traffic types. 
In the latter case, the load is e.g. distributed on shortest paths. 
Optimization Model 
In order to speak about optimality in a well-defined sense it is necessary 
to define a reasonable objective function. A natural and well motivated 
choice is the total carried traffic or the network revenue due to their 
tractability and the obvious practical importance. Let w.sub.r be the 
revenue coefficient parameter for route r, meaning that one unit of 
carried traffic on route r is associated with revenue w.sub.r. The revenue 
coefficients can easily be incorporated into the total carried traffic 
function so as to obtain the network revenue function. In the hereinafter 
described embodiments of the invention we will consider the network 
revenue as the objective function. However, it should be understood by 
those skilled in the art that from the technical point of view the total 
carried traffic is the main objective function and the network revenue is 
an extension which is a weighted version of the total carried traffic. 
On the basis of this mathematical framework the objective function 
according to a preferred embodiment of the invention can be expressed as 
the total network revenue summed up over all routes in all the logical 
networks: 
##EQU2## 
where L.sub.r is the end-to-end blocking probability for traffic on route 
r. Clearly, this route blocking probability is defined as the probability 
of the event that at least one logical link is blocked along the route. 
The objective function to be optimized is inherently difficult to deal 
with, since it requires knowledge of the carried traffic and thereby route 
blocking probabilities which can only be computed in an exact way for very 
small networks. The objective function depends on the allocated resources 
in an indirectly defined non-linear way. The dependence is defined through 
a complicated non-linear system of equations that follows from a 
teletraffic model, as will be described below. 
The objective of the optimization task associated with the partitioning of 
physical network resources is to maximize the total network revenue, as 
defined above, subject to the physical constraints SC.ltoreq.C.sub.phys, 
C.gtoreq.0. In accordance with a first preferred embodiment of the present 
invention, this is achieved by computing the partial derivatives of the 
network revenue with respect to the logical link capacities and 
subsequently using them in a gradient method. 
To be able to obtain analytical results the well known reduced load and 
link independence assumption is applied, which yields the following fixed 
point equations, taking different traffic classes into account: 
##EQU3## 
for all i and k, where 
EQU .lambda..sub.r =.nu..sub.r (1-L.sub.r) (5) 
and 
##EQU4## 
for all i and j. B.sub.ik denotes the blocking probability for traffic 
type i on logical link k. Let .rho..sub.ik be the offered bandwidth demand 
from traffic type i to logical link k when blocking elsewhere is taken 
into account. For each logical link k and traffic type i it is assumed 
that there exists a blocking function E.sub.ik which, given the logical 
link offered classwise bandwidth demand .rho..sub.1k, . . . , .rho..sub.Ik 
and logical link capacity C.sub.k, returns the blocking probability on 
logical link k regarding traffic type i. In order to preserve generality 
any blocking function is allowed that is jointly smooth in all the 
variables. 
Based on this assumption the partial derivatives of the total network 
revenue can be found in a tractable form suitable for a gradient based 
hill climbing. 
The basic idea of finding the partial derivatives of the network revenue at 
the point (.nu., C), where .nu.= (.nu..sub.1, .nu..sub.2, . . . , 
.nu..sub.R), can be formulated as follows: 
Work on the smooth surface defined by the fixed point equations in a 
neighborhood of (.nu., C). 
Define appropriate one-dimensional smooth curves and apply the fact that 
the directional derivative of a differentiable multivariable function in 
the direction of the tangent of such a curve is equal to the derivative of 
the function seen as a function of the single variable parametrising the 
curve. 
The partial derivatives of the total network revenue are calculated for the 
multirate case, as calls on different routes are allowed to have different 
bandwidth requirements. The formulas are presented in the following and it 
is useful to have the usual notion of a differential like dW as a small 
change in W. 
The revenue derivative with respect to logical link capacity C.sub.k can be 
formulated as: 
##EQU5## 
where 
##EQU6## 
and where the set of auxiliary parameters c.sub.ik is defined by the 
following system of linear equations: 
##EQU7## 
where 
##EQU8## 
Two important terms in the expression for the revenue derivatives are the 
partial derivatives of the link blocking function: 
##EQU9## 
In the simplest case with Poisson input and homogeneous traffic, the 
blocking function is Erlang's B formula that is defined for integer 
capacity values but has a simple analytic extension to any non-negative 
real capacity value. 
However, the present invention considers the multirate case. It is possible 
to use Kaufman and Robert's recursive blocking formula from the stochastic 
knapsack problem. Unfortunately it is quite complicated to find explicitly 
a smooth extension to real capacity values. Therefore, in a preferred 
embodiment of the present invention, in order to enhance computational 
feasibility, a normal approximation is used for the blocking function (see 
Appendix A for details): 
##EQU10## 
where it is assumed that the amount of offered bandwidth at logical link k 
follows a normal distribution with mean .rho..sub.k and variance 
.sigma..sub.k.sup.2, where .rho..sub.k =.SIGMA..sub.i .rho..sub.ik and 
.sigma..sub.k.sup.2 =.SIGMA..sub.i .sigma..sup.2.sub.ik. .PHI. denotes the 
standard normal distribution function, and since .PHI. is smooth, 
therefore E.sub.hk will be smooth in all variables. Note that this normal 
approximation approach should be viewed as an example in order to 
illustrate one way of dealing with the link blocking function. 
By differentiation of (11), applying the well known chain rule, the partial 
derivatives of the blocking function can be explicitly expressed as: 
##EQU11## 
where .phi. denotes the standard normal density function. 
Now, all the expressions needed to obtain an expression, although very 
complicated, for the partial derivatives of the network revenue with 
respect to the logical link capacities are presented. The combination of 
the expressions (7), (8), (9), (10), (12) and (13) yields this expression 
for the revenue derivatives. 
One of the oldest and most widely known methods for minimizing or 
maximizing a function of several variables is the method of steepest 
descent (or ascent as in the present case) which is often referred to as 
the gradient method. The gradient method is an iterative method capable of 
solving both linear and non-linear problems. It is based on the fact that 
the gradient of a multivariable function, i.e. the vector of partial 
derivatives for the function, points, at each point, in the direction in 
which the function changes (increases or decreases) at the highest rate. 
In addition, the optimal step size in this direction is determined by a 
line search. Hence, the method is appropriately designed for climbing 
towards a maximum of a multivariable function. 
In accordance with a first preferred embodiment of the invention the 
partial derivatives for the network revenue with respect to the logical 
link capacities, as defined above, are applied in a gradient based hill 
climbing procedure in order to maximize the total network revenue as 
defined by (2). Let .gradient.W(C.sub.1, C.sub.2, . . . , C.sub.J) denote 
the gradient vector of the total network revenue with respect to the 
logical link capacities. 
The physical constraints of the optimization problem, SC.ltoreq.C.sub.phys 
and C.gtoreq.0, define a feasibility region which is a convex polyhedron. 
These physical constraints have to be taken into account in the gradient 
based hill climbing procedure, since each step in the actual hill climbing 
must end within the feasibility region. 
At first, an initial design point for the logical link capacities 
associated with the various logical networks is selected. Subsequently, 
the logical link capacities are iteratively calculated by an alternating 
sequence of calculating the optimal ascend or step direction using the 
revenue gradient vector .gradient.W(C.sub.1, C.sub.2, . . . , C.sub.J) and 
performing a one-dimensional line search to find an optimal point. Each 
step in the actual hill climbing must be in consistency with the 
feasibility region defined by the physical constraints. The iteration 
process is terminated when convergence is achieved with a required level 
of accuracy. The physical link capacities are then allocated among the 
logical links of the various logical networks in accordance with the 
finally calculated logical link capacities. 
For a better understanding of the invention a method according to a first 
preferred embodiment will be described in more detail with reference to 
the schematic flow diagram of FIG. 5. In the first step, a set of logical 
networks is established on top of a physical network by associating 
different parts of the traffic with different parts of the physical 
transmission and switching resources. Next, initial values for the logical 
link capacities C.sub.j.sup.initial (for all j), which can be seen as an 
initial design point, are selected. Then, the fixed point equations 
defined by (3)-(6) are solved by successive substitutions, thereby 
computing a set of blocking probabilities B.sub.ik to be used in 
subsequent steps. In order to calculate the partial derivatives for the 
network revenue the set of linear equations that is defined by (9) and 
(10) has to be solved. The solution will yield the set of auxiliary 
parameters c.sub.ik that is needed for calculating the revenue 
derivatives. Now, the present logical link capacities, the blocking 
probabilities and the auxiliary parameters are known. Next, the actual 
calculation of the revenue derivatives with respect to the present values 
of the logical link capacities takes place. Thus, the gradient vector for 
the network revenue is known and the optimal ascend or step direction at 
the present design point can be determined. If the present design point is 
situated at the boundary of the feasibility region and the calculated 
gradient vector points out from the feasibility region, then the direction 
of the next step in the hill climbing is calculated by projecting the 
gradient vector so that it follows the boundary. In fact, if identity 
projections (i.e. projections of the gradient which coincides with the 
gradient) are included, one could say that the next step in the actual 
hill climbing is always taken in the direction of the projection of the 
gradient of the network revenue to the feasibility region. Alternatively, 
in this particular case, a penalty function procedure can be utilized to 
determine the direction of the next step. Furthermore, a one-dimensional 
line search is performed along the ascend or step direction to optimize 
the size of the step to be taken in the actual hill climbing. Of course, 
as mentioned above, every step, determined by the direction and the step 
size, in the hill climbing has to be consistent with the feasible region. 
When the ascend direction, the step size and the physical constraints all 
are taken into account a new design point is reached, representing a new 
set of logical link capacities C.sub.j ' (for all j). Now, a convergence 
test is carried out. If the convergence conditions are not satisfied, the 
procedure will be repeated, but now the steps of establishing the logical 
networks and selecting an initial design point are omitted. Instead, the 
new set of logical link capacities C.sub.j ' is used as a new design point 
in the fixed point equations. This will lead to the computation of a new 
set of blocking probabilities, auxiliary parameters, revenue derivatives 
and subsequently also of a yet another set of logical link capacities. 
However, if the convergence conditions are satisfied, the physical link 
capacities are allocated among the logical links of the corresponding 
logical networks according to the finally calculated logical link 
capacities. 
If the cross connect is based on SDH, the partitioning can only be 
performed in integer portions of the STM modules of the SDH structure, as 
mentioned above. In this particular case, the real capacity values 
obtained from the method according to the first preferred embodiment of 
the invention are preferably rounded into integer values such that the 
physical constraints are satisfied. In one embodiment of the invention 
this is realized by independently repeated random rounding trials. 
The method according to the first preferred embodiment of the invention is 
preferably performed by one or more control programs CP of the control 
program module of the operation and support system OSS. These control 
programs, in turn, are executed by one or more of the processors in the 
processor system PS described above. The operation and support system OSS 
collects the required information from the network system and uses this 
information together with the database DB information as input to the 
respective control programs CP. Furthermore, the OSS controls the network 
switches through the data links so as to partition the physical link 
capacities among the logical links of the logical networks. 
Accordingly, the network manager can flexibly adapt the overall network 
system to changing traffic conditions, such as changes in offered traffic, 
but also to facility failures and new demands on the logical network 
topology from e.g. business users, as is illustrated in the schematic flow 
diagram of FIG. 6. Once the method or device according to the first 
preferred embodiment of the invention has been applied to a physical 
network, the partitioning is optimal. However, if, at a later time, the 
topology of one or more logical networks have to be changed for some 
reason (facility failure or demands for new topologies) or additional 
logical networks are requested, then the complete set of steps according 
to the first preferred embodiment of the present invention has to be 
performed in order to optimize the overall network configuration. If no 
changes regarding the topology of the logical networks is necessary, but 
e.g. the offered traffic varies, then only the optimization and allocation 
steps of the first preferred embodiment of the present invention have to 
be carried out. That is, the optimization step and the allocation step are 
repeated in response to changing traffic conditions so as to change the 
logical link capacities of the various logical networks in a flexible and 
optimal way. This is realized by the switches and cross connect devices of 
the physical network in a very short period of time. Thus, the realization 
of the present invention renders the operation of the complete physical 
network both safe and flexible. 
The method in accordance with the present invention regards the logical 
link capacities as fixed in each iteration step. Of course, from the 
viewpoint of the whole optimization procedure the logical link capacities 
are not fixed parameters since it is desired to optimize them. Moreover, 
in each iteration step, the strictly non-linear objective function is 
approximated as a linear function valid in a neighborhood of the fixed 
point, but seen from the whole procedure the objective function is 
non-linear since the objective function itself is changing in an 
indirectly non-linear way in each iteration step. 
Since the gradient method in general converges towards a local optimum the 
selection of initial values for the logical link capacities has to be 
correctly performed in a suitable way. By a careful choice of initial 
design point the risk of finding a local optimum that falls far from the 
global optimum is negligible. One choice of initial values is the solution 
of the corresponding deterministic flow problem that can be seen as the 
limiting case where logical link capacities and offered traffic values 
tend to infinity. However, in accordance with a preferred embodiment of 
the invention, the initial point is selected as the solution of a 
convexification of the problem. 
The article "Resource separation--an Efficient Tool for Optimizing ATM 
Network Configuration" by A. Farago, S. Blaabjerg, W. Holender, T. Henk, 
A. Szentesi and Z. Ziaja in Networks '94, (September 1994) relates to an 
approximative method which finds a global optimum for a modified concave 
network revenue function by convex optimization. 
In general, the complexity of computing blocking probabilities is much 
larger in the case where many different bandwidth demands (traffic types) 
co-exist. An efficient way of avoiding the increased complexity is to 
approximate the blocking probability for a traffic type requiring d units 
of bandwidth by grabbing d times one unit independently. In other words, a 
non-unity bandwidth call is modelled by a sequence of independent unity 
bandwidth calls. In the article "Blocking Probabilities in Multitraffic 
Loss Systems: Insensitivity, Asymptotic Behavior and Approximations" by 
Labourdette and Hart in IEEE Trans. Communications, 40 (1992/8) pp. 
1355-1366. it is proven that this approximation is correct in the 
asymptotic sense. 
Adopting the approximation in the above paragraph and assuming all revenue 
coefficients are the same, independently of traffic types, and utilizing 
the convex optimization method (COM) of Farago et al. referred to above, a 
global optimum is guaranteed. 
Although the convex optimization method (COM) yields a global optimum, it 
is obtained in a relatively rough model. In accordance with the present 
invention a gradient based hill climbing is used to come from the initial 
point obtained from the COM method to an improved value in the more 
refined model of the present invention. 
In the regime where the capacities are large, and if the approximation of 
modelling a non-unity bandwidth call with a sequence of unity bandwidth 
calls is adopted, a device as described in our Patent Application 
9500838-9 can be used to obtain an initial design point for the logical 
link capacities. The device comprises two artificial neural networks 
interworking to compute a set of logical link capacities representing a 
global optimum. In this case also, the global optimum is obtained in a 
model which is relatively rougher than the model of the present invention. 
It is evident that in many practical circumstances a solution with a 
minimum guaranteed resource and possibility to use a certain number of 
extra resources will be applied. By way of example, the physical 
constraint C.gtoreq.0 can be altered to C.gtoreq.C.sub.constant, where 
C.sub.constant is a constant capacity vector representing a minimum 
guaranteed resource for each individual logical link. Of course, the 
physical constraint SC.ltoreq. C.sub.phys can not be violated. 
As mentioned above, in a preferred embodiment of the invention, the 
aggregated offered traffic of type i to node pair p in logical network 
.upsilon. is given for all logical networks, node pairs and traffic types. 
However, the total network revenue depends also on the offered traffic to 
each route, .nu..sub.r, and hence the overall network performance is 
affected by the distribution of offered traffic among the routes which can 
realize the communication even within a single logical network. It may 
appear natural to distribute the offered traffic load uniformly among 
parallel routes, but in general this distribution is far from optimal. 
Therefore, in accordance with a second preferred embodiment of the present 
invention, the distribution of the offered traffic load of type i to node 
pair p in logical network .upsilon., for all i, p and .upsilon., is 
determined together with the partitioning of the physical link capacities 
among the logical links of the various logical networks, such that the 
overall network performance is optimized. In addition, by distributing, 
for each individual node pair in each one of the logical networks, the 
offered traffic load among the routes carrying traffic between the nodes 
of the individual node pair, overload situations are avoided and in 
general load balancing is achieved. 
The distribution of the offered traffic between the possible routes is 
termed load sharing, and the parameters according to which it takes place 
is called load sharing coefficients. For a given logical network 
.upsilon., node pair p and traffic type i let s.sup.(.upsilon.,p,i) 
=(S.sub.r1.sup.(.upsilon.,p,i), S.sub.r2.sup.(.upsilon.,p,i), . . . ) 
denote the load sharing vector. The components of S.sup.(.upsilon.,p,i) 
tell us in what proportion the load is distributed among the routes that 
carry traffic type i between the O-D pair p in logical network .upsilon.. 
Naturally, the components of each load sharing vector are non-negative and 
their sum is equal to 1. 
Now, the optimization task according to a second preferred embodiment of 
the invention is to determine the logical link capacities of the various 
logical networks and the typewise load sharing coefficients for the node 
pairs in each one of the logical networks so that the total expected 
network revenue is maximized, while the physical constraints are 
satisfied. In mathematical terms this can be formulated as follows: 
Maximize 
##EQU12## 
subject to 
##EQU13## 
On the basis of the mathematical framework set forth above, the revenue 
derivative with respect to offered traffic along route r can be expressed 
as: 
##EQU14## 
where the set of auxiliary parameters c.sub.ik is defined by the system of 
linear equations given by (9) and (10). Together with the partial 
derivatives for the network revenue with respect to the logical link 
capacities, as given above, the revenue derivatives with respect to the 
route offered traffic values are applied in a gradient based hill climbing 
procedure in order to maximize the network revenue function. Once again 
the physical constraints define a convex feasibility region, which has to 
be considered in the actual hill climbing. 
With reference to the flow diagram of FIG. 7 a method in accordance with a 
second preferred embodiment of the invention is illustrated. At first, a 
set of logical networks is established on top of a physical network. Next, 
an initial design point for the logical link capacities 
C.sub.j.sup.initial and the route offered traffic values 
.nu..sub.r.sup.initial in each one of the logical networks is selected. 
Preferably, the offered load is distributed along shortest paths as a good 
initial choice for the route offered traffic values. Subsequently, logical 
link capacities and route offered traffic values are iteratively 
calculated by an alternating sequence of calculating the optimal ascend or 
step direction using the revenue gradient vector with respect to both the 
logical link capacities and the route offered traffic and performing a 
one-dimensional line search to find an optimal point. The partial 
derivatives with respect to the present logical link capacities and the 
present route offered traffic values, constituting the revenue gradient 
vector in this particular embodiment, have to be calculated in each 
iteration step. This means that the fixed point equations (3)-(6) and the 
set of linear equations (9)-(10) also have to be solved in each iteration. 
Each step along the ascend or step direction in the actual hill climbing 
must be in consistency with the feasibility region defined by the physical 
constraints given in (15). This is achieved by a projection procedure as 
mentioned above. The iteration process is terminated when convergence is 
achieved with a required level of accuracy. In all other regards the 
gradient based hill climbing procedure is similar to the one in which only 
the revenue derivatives with respect to the logical link capacities were 
considered. Now, the logical link capacities for the various logical 
networks and the route offered traffic values in each logical network 
which maximizes the revenue function are known. Consequently, the optimal 
distribution of the offered traffic load of type i to node pair p in 
logical network .upsilon. is known for all i, p and .upsilon., and the 
corresponding load sharing coefficients are calculated in a 
straightforward way. The physical link capacities are then allocated among 
the logical links of the various logical networks in accordance with the 
finally calculated logical link capacities. Similarly, the traffic load is 
apportioned, for each individual node pair in each one of the logical 
networks, among the routes which can realize communication between the 
nodes of the individual node pair, in accordance with the finally 
calculated set of load sharing coefficients. 
The second preferred embodiment is preferably realized by one or more 
control programs CP which are executed by the processor system PS 
incorporated in the operation and support system OSS described above. The 
operation and support system OSS collects the required information from 
the network system and uses this information together with the database DB 
information as input to the respective control programs CP. Furthermore, 
the OSS controls the overall network system through the data links. 
In one embodiment of the invention the apportioning is preferably realized 
by routing decision means. For example, assume that there are two 
different routes between a node pair. The load sharing coefficients for 
the first and second route are 0,6 and 0,4 respectively. When a call 
request comes to the node pair a random number between 0 and 1 is 
generated by random number generator means. If the random number is less 
than 0,6 then the first route is to be used, and if the random number is 
greater or equal to 0,6 then the second route is to be used. 
In similarity to the first preferred embodiment of the invention, the 
second preferred embodiment allows the network manager to flexibly adapt 
the overall network system to changing traffic conditions, such as changes 
in offered traffic, but also to facility failures and new demands on the 
logical network topology from e.g. business users. This is illustrated in 
the schematic flow diagram of FIG. 8. Once the method or device according 
to the second preferred embodiment of the invention has been applied to a 
physical network, the partitioning of physical resources and the 
distribution of offered traffic load is optimal. However, if, at a later 
time, the topology of one or more logical networks have to be changed for 
some reason (facility failure or demands for new topologies) or additional 
logical networks are requested, then the complete set of steps according 
to the second preferred embodiment of the present invention has to be 
performed in order to optimize the overall network configuration. If no 
changes regarding the topology of the logical networks are necessary, but 
the traffic varies, then only the optimizing, allocating and apportioning 
steps of the second preferred embodiment of the present invention have to 
be carried out. That is, the optimizing step, the allocating step and the 
apportioning step are repeated in response to changing traffic conditions 
so as to change the logical link capacities and the route offered traffic 
values of the various logical networks in a flexible and optimal way. 
It is evident that it is equally possible to optimize the network revenue 
or the other objective functions mentioned above with respect to the route 
offered traffic values alone without considering the logical link 
capacities. In other words, determining the optimal distribution of the 
offered traffic load of type i to node pair p in logical network .upsilon. 
for all i, p and .upsilon.. 
Therefore, in accordance with a third preferred embodiment of the 
invention, the typewise load sharing coefficients for each node pair in 
each one of the logical networks are determined so that the total expected 
network revenue is maximized, while the physical constraints are 
satisfied. In mathematical terms this is formulated in the following way: 
Maximize 
##EQU15## 
In FIG. 9 there is illustrated a schematic flow diagram of a third 
preferred embodiment of the present invention. First, initial values for 
the route offered traffic in each one of the logical networks are selected 
as an initial design point. Preferably, the offered load is distributed 
along shortest paths as an initial choice. Subsequently, route offered 
traffic values are iteratively calculated by an alternating sequence of 
calculating the optimal ascend or step direction using the revenue 
gradient vector with respect to the route offered traffic (using 
expression (16)) and performing a one-dimensional line search to find an 
optimal point by optimizing the step size. 
Since the route offered traffic is changed in the actual hill climbing, the 
fixed point equations (3)-(6) have to be solved in each iteration. 
Furthermore, the set of linear equations (9)-(10) has to be solved in each 
iteration in order to calculate the partial derivatives of the network 
revenue with respect to the present route offered traffic values. Each 
step along the ascend or step direction in the actual hill climbing must 
be in consistency with the feasibility region defined by the physical 
constraints. This is achieved by a projection procedure similar to the one 
in the first and second preferred embodiments of the invention. The 
iteration process is terminated when convergence is achieved with a 
required level of accuracy. In all other regards the gradient based hill 
climbing procedure is similar to the one in the second preferred 
embodiment. Now, the route offered traffic values for each logical network 
which maximizes the network revenue function are known. Consequently, the 
optimal distribution of the offered traffic load of type i to node pair p 
in logical network .upsilon. is known for all i, p and .upsilon., and the 
corresponding load sharing coefficients are calculated in a 
straightforward way. Then, the offered traffic load is apportioned, for 
each individual node pair in each one of the logical networks, among the 
routes which can realize communication between the nodes of the individual 
node pair, in accordance with the finally calculated load sharing 
coefficients. 
The third preferred embodiment is preferably realized by one or more 
control programs CP which are executed by the processor system PS 
incorporated in the operation and support system OSS. 
In one embodiment, the apportioning of offered traffic load Is performed by 
routing decision means using random number generator means. 
Note that the accompanying drawings are simple illustrative examples 
illustrating the inventive concept of the present invention. In practice, 
the physical network and the logical networks are, in general, very 
extensive with e.g. intermediate logical nodes which are not directly 
associated with access points and logical links using more than one 
physical link. 
The embodiments described above are merely given as examples, and it should 
be understood that the present invention is not limited thereto. It is of 
course possible to embody the invention in specific forms other than those 
described without departing from the spirit of the invention. Further 
modifications and improvements which retain the basic underlying 
principles disclosed and claimed herein are within the scope and spirit of 
the invention. 
Experimental Results 
The present invention was tried on a very simple network. It was a 
four-node ring network on top of which two logical networks with one 
traffic class in each were established. These traffic classes were 
different, so there were altogether two traffic classes. Two parameters 
were varied: the ratio of the single-call bandwidth demand in the two 
traffic classes (bandwidth ratio--BR) and the ratio of the offered traffic 
load in the two classes (offered traffic ratio--OTR). 
In order to see how much gain is achieved by the proposed invention in 
comparison to the initial values obtained from the convex optimization 
method (COM), the revenue ratio--RR, i.e. the revenue achieved by the COM 
method divided by the revenue achieved by the second preferred embodiment 
of the present invention, was measured. The result is shown in FIG. 10. If 
the varied ratios were below 10, the present invention improved the result 
insignificantly. On the other hand, as the traffic scenario gets more 
inhomogeneous, the additional gain obtained by the present invention 
becomes more and more substantial. Consequently, if the proposed invention 
is applied to large telecommunication networks, such as an ATM network, 
with several logical networks carrying a number of widely different 
traffic types it is very likely that the invention will considerably 
improve the result, as is shown by the overall tendency of the 
experiments. 
APPENDIX A 
In order to enhance computational feasibility, a normal approximation is 
used for the blocking function. Assume that the amount of offered 
bandwidth at logical link k follows a normal distribution with mean 
.rho..sub.k and variance .sigma..sub.k.sup.2, where .rho..sub.k 
=.SIGMA..sub.i .rho..sub.ik and .sigma..sub.k.sup.2 =.SIGMA..sub.i 
.sigma..sup.2.sub.ik. From the reduced load approximation, we have 
##EQU16## 
and 
##EQU17## 
By applying the renormalizing procedure that is valid for time reversible 
Markovian systems and from the assumption of a normal distribution we 
arrive at 
##EQU18## 
where .PHI. denotes the standard normal distribution function. Since .PHI. 
is smooth, therefore E.sub.hk will be smooth in all variables.