|Title of Invention||
"A PROVISIONING METHOD, SYSTEM AND APPARATUS FOR A COMMUNICATION NETWORK"
|Abstract||In the area of network provisioning, there is a problem of selecting a suitable traffic-provisioning model for large networks due to the high management complexity of the resource-efficient trunk model and the poor bandwidth efficiency of the easy-to-configure hose model. The invention is based on the idea of partioning (S1) at least part of the network into multi-node clusters, and defining (S2) traffic limitations on at least two levels, including the intra-cluster level and the inter-cluster level, where the traffic limitations include one or more node-to-cluster traffic limitations for inter-cluster traffic. Subsequently, cluster-based provisioning (S3) of the network is performed based on the traffic limitations. The novel node-to-cluster limitations proposed by the invention are preferably applied in a cluster-based trunk or hose model on the inter-cluster level. In other words, for the description of the inter-cluster traffic (traffic between the clusters) cluster-based trunk or hose models can be used preferably depending on the available information about the traffic. The cluster-based provisioning makes it possible to find a trade-off between management complexity and over provisioning.|
|Full Text||TECHNICAL FIELD
The present invention generally relates to network provisioning for networks such as mobile core networks and Virtual Private Networks (VPNs), and more particularly to dimensioning and admission control in such networks.
Network provisioning generally relates to resource allocation and management in a network and often includes issues such as admission control and/or dimensioning of the network.
A substantial tendency is that the number of network nodes that form a network is growing fast, resulting in a large, complex network structure and virtual topology. In parallel with this tendency, the traffic volume between the network nodes is also growing continuously and is often difficult to predict. Traffic between nodes is also hard to measure because of the large number of nodes and traffic trunks. Therefore, the calculation of the traffic matrix is very complicated. In most of the cases it is not even possible to calculate the traffic matrix. Furthermore, the degree of traffic changes, requiring reconfiguration of the network, is also very hard to forecast.
The area of resource management includes some currently open problems. To achieve good network utilization, the best possible characterization of the customer's traffic flows is required. Supporting a variety of customer applications typically requires a Service Level Agreement (SLA) between the network provider and the customer, specifying the Quality of Service (QoS) and bandwidth requirements. Currently there are two ways to define the SLA and exercise admission control, namely the trunk-based (customer-pipe) model and the hose-based model, which both are static models.
Admission control is an essential component of any network provisioning architecture, and is generally a question of controlling the number of connections that utilize a given set of resources in a communication network, thereby ensuring that admitted connections
of Service (QoS)
have access to the resources that are required to fulfil their Quality
requirements. On the link level, admission control normally serves to restrict the number of connections simultaneously present on a transport link in the network. This means that new connections may be rejected in order to protect connections that are already admitted for transport over the link.
complex, and for UMTS), Virtual
main problem is to ame time fulfils
The issue of connection admission control is generally quite networks such as Universal Mobile Telecommunications System Private Networks (VPNs) and similar communication networks the find an efficient admission control strategy that works and at the practical requirements such as limited complexity and high accuracy.
network is to to specify the ir. This model,
A simple service model, or traffic provisioning model, for a transport emulate the private line service. This would require a client nodp bandwidth requirement between every possible source-destination pair the trunk model, is depicted in Fig. 1.
When a transport network is based on the trunk model, then a mesh of trunks is created, each trunk extending from one customer endpoint to another. A customer endpoint must maintain a logical interface for each of its trunks. In the context of a UMTS core transport network for example, the customer endpoint is typically a Media Gateway (MGW) or equivalent node.
For the trunk model it is normally expected to give the point-to-point
In other words, the specification of the traffic matrix is needed. This miodel enables the network provider to utilize the network in the best way, since the known traffic matrix
and routing strategy exactly determine the required link capacities. On the other hand, a critical part of this model is that the communication pattern between the end-points is very difficult to describe. It is a justified assumption that the network provider has very limited information about the traffic matrix, and the customer is unable to exactly predict and define the loads between the nodes. Consequently, in case of an unknown traffic matrix, the application of the trunk or customer-pipe model is quite limited, especially in the VPN context. Another problem with this model is the significant management complexity. In each node, incoming and outgoing traffic description parameters have to be defined for each associated node to define the required capacities in relation to the associated nodes. In case of a full mesh logical network, the sum of parameters to be configured is proportional to the square of the number N of nodes in the considered network or part of the network.
the hose model, which is another traffic provisioning model, a customer specifies a of endpoints to be connected. The connectivity between endpoints in the network is fied by a hose, comprising:
capacity required for aggregate outgoing traffic from the endpoint into the rk (to the other end-points),
The capacity required for aggregate incoming traffic from the network to the endpoint (from the other end-points).
network dimensioning is based on the hose model, then a customer dpoint maintains just one logical interface, a hose, to the provider access router. Fig. exemplary implementation of a hose using edge-to-edge pipes.
Using the hose model, the traffic matrix is not required, only the incoming and outgoing traffic volumes need to be known for each node. These traffic parameters can
model. Thus, the but it is not so uncertainty in that the worst case traffic etwork. From the significantly less incoming and outgoing parameters to be
be measured or predicted in a more exact way compared to the trunk hose model is very attractive from the viewpoint of the customer, advantageous for the network provider since it implies traffic sink nodes are not known. The network must be dimensioned for the distribution, winch may cause significant overdimensioning in the n viewpoint of management complexity, the hose model requires parameters than the trunk model. Since only the aggregated i traffic volumes have to be defined in each node, the number of configured is proportional to the number of nodes in the network.
Based Admission i-to-end  and . In
admission control packet flows per Transfer Protocol gestion in the IP out-of-sequence
the remote site in ays are likely to
Measurement Based Admission Control
Yet another type of traffic provisioning model is Measurement
Control (MB AC). In particular, drop-based MB AC, winch is an example of end
measurement based admission control, is known from references
MBAC, a node measures the network performance to guide the
decisions. For example, the data receiver monitors the user plane
remote site and detects dropped packets by comparing the Real-time
(RTF) sequence numbers. A dropped packet is an indication of con
backbone and RTF provides a mechanism to detect dropped or
packets. The node admits a new call only if the loss rate towards
question is below a given threshold value. Given that the queuing de
be quite small, the quality of service is measured strictly in terms of packet loss
in multiple-fault ocks further calls
Admission control decisions in the case of measurement-based provisioning are always based on the actual performance of the network, so all unexpected situations
are handled properly. For example, if congestion occurs on a link situations then packet loss is measured in the data receiver, winch bl until the congestion disappears.
However, may not be network of applications
measurement-based admission control has the drawback that proper QoS guaranteed if the drop requirement is strict, for example in the backbone UMTS system. Tins may prevent the use of drop-based MB AC in many
The main table below.
of the prior art traffic provisioning models are summarized in the
static admission control can be based on trunk or hose models.
The trunk defined in way, resulting a lot
sink nodes fast, actually therefore car the network, other nodes, is not
model, where admission control is based on virtual point-to-point trunks nodes, enables the network provider to utilize the network in the best in more effective network operation. However, the trunk model requires of configuration parameters in all nodes to describe the traffic towards the other according to the SLA. The complexity of the trunk configuration grows it is proportional to the square of the number of network nodes, and generally not be used in a large-scale network. If a new node is added to a new trunk must be defined and configured with a capacity limit in all Another important problem with the trunk model is that the traffic matrix or just partly known. On the other hand, the main advantage of the trunk model
is that it offers the best bandwidth efficiency among the available methods.
not check the incoming and . Furthermore, . The major overdimensioning in is very simple; a new node is s not affected, that of the trunk
Using the hose model, where admission control in the nodes does destination of the calls, the configuration is much simpler. Only outgoing traffic description entries need to be configured in the nodes the hose parameters can be measured or predicted in a simple drawback of the hose model is that it normally causes significant the network. Configuration of network nodes in the case of hose mode in fact only two parameters should be configured in each node. When added to the system, then the configuration of the other nodes However, bandwidth efficiency of the hose model is worse than model.
Therefore, there could be large core networks, large VPNs or other
where neither trunk nor hose provisioning is applicable due to management complexity or poor bandwidth efficiency, respectively.
In the literature, papers dealing with hose or trunk model based network dimensioning can be found.
The main concept of the hose model has long been present in the literature under the theory of "non-blocking networks". For example, reference  presents a network design methodology based on just the same resource-provisioning concept as the hose model.
Reference  presents an analysis of the bandwidth efficiency of the pose model for provisioning IP Virtual Private Networks. The evaluation is based on trace-driven
simulations of traffic derived from a voice network and from a large corporate They provide numerical results for network-wide capacity demand for lose realizations. The comparison of the bandwidth efficiency of the pipe and hose models is limited to the access links, although the real sioning required by the hose model will be present witinn the backbone
In reference be based hoses (dif erent capacities
 it is argued that an optimal cost solution for hose realizations should a tree topology, and it is proved that the general problem with asymmetric amount of traffic sent and received by the hose) and constrained link is NP-hard (NP, Non-Polynomial). In view thereof, approximation algorithms' with provable performance bounds were presented in .
The most winch pro
recent important contribution in tins field can be found in reference , oses restoration algorithms to improve the tree-based hose realization.
case of tree the size of model for LSPs. CSPF.
Reference  provides a detailed comparison of the resource efficiency of the hose and the trunk resource allocation models. It was concluded that the overprovisioning factor of the hose model can be reasonably low for smaller networks (especially in the routing). However, the overprovisioning factor increases considerably with the network in the case of shortest path routing. It is shown that the hose poor bandwidth efficiency if it is combined with bandwidth reservation Its bandwidth efficiency is further degraded when routing is done with
Reference related to
of representative papers regarding the trunk model are given below.
 provides a detailed survey of various possible network design tasks the trunk model. A general framework is proposed and several special cases
that are relevant in the design of telecommunication networks are method is also able to handle different cost models.
References ,  and  concern methods to solve various telecommunication network design tasks.
Other heuristics were proposed in reference  for designing networks.
Further references , ,  and  deal with the questions of designing Virtual Private Networks with or without failure protection capability.
A common attribute of all the above trunk reservation methods is that they do not take the complexity of the configuration into the account but they aim at designing networks requiring least capacity devices.
admission control o-end resource in inerarcincal scenario The in order establish traffic on a full traffic
In reference , the objective is to implement existing connection (CAC) in a distributed control arcintecture to regulate end-1 provisioning over IP networks. The proposed technique is applicabl networks based on basic domains, especially for the multiple technique is based on the traditional trunk model and clustering is employed to make it possible to implement the distributed CAC method and to aggregation. In particular, they use an admission control strategy based matrix with an aggregate reservation based on a Gaussian traffic predictor
SUMMARY OF THE INVENTION
It is a general object of the invention to provide an improved network provisioning strategy.
It is an well as
object of the invention to provide a new efficient admission control strategy, as a corresponding network dimensioning mechanism.
It is a at the
particular object to provide a scalable (in terms of management complexity) and time resource-efficient admission control and dimensioning strategy.
It is a specific object to provide an improved method and arrangement for provisioning
commu lication networks.
It is another tinngs
specific object to provide a design and/or support tool that among other be used for network dimensioning purposes.
Yet another specific object of the invention is to provide a novel admission controller for operation in a communication network.
In the prior art, as we have seen, there is a general problem of selecting a suitable traffic provisioning model for large networks due to the ingh management complexity of the re source-efficient trunk model and the poor bandwidth efficiency of the easy-to-configure hose model.
The invention is based on the idea of partitioning at least part of the network into
where each cluster has at least two nodes, and defining traffic limitations on
at least two levels, including the intra-cluster level and the inter-cluster level, where the traffic limitations include one or more novel node-to-cluster traffic limitations for the inter-cluster traffic. Finally, cluster-based provisioning of the network is performed based on the defined traffic limitations. Using cluster-based provisioning in tins way makes it possible to find an optimal equilibrium or trade-off between management complexity and overprovisioning.
s, winle in the tations. In the to one or more sion "node-to-given cluster, of general, the
In the traditional trunk model there are node-to-node traffic limitatioi traditional hose model there are only node-to-anywhere traffic lim model proposed by the invention, the traffic can (also) be subjected node-to-cluster limitations. It should be understood that the expre cluster limitation" normally means a limitation, for a given node in a the amount of traffic in relation to at least one other cluster. 1 limitation(s) may be related to traffic in the incoming and/or outgoing direction.
invention are model on •-cluster traffic
can be used, s also possible
The novel node-to-cluster limitation or limitations proposed by th preferably applied in a so-called cluster-based trunk or a cluster-based hose the inter-cluster level. In other words, for the description of the inte (traffic between the clusters) a cluster-based trunk or hose mode' preferably depending on the available information about the traffic. It to group the clusters and independently selecting so-called inter-hosi provisioning for each group of clusters.
mmon cluster) 3ntly cluster by bandwidth allocation providing a
The intra-cluster traffic (traffic between the nodes that belong to a c may be described by the traditional trunk or hose models, independ cluster if desired. Tins implies that a traffic description model or model can be selected independently for each cluster in the netwo ingher degree of flexibility compared to prior art network provisioning.
Selecting between trunk and hose models for intra-cluster provisioning cluster-based trunk and hose models for inter-cluster provisioning givejs basic combinations:
and between the following
mtra-trunk, inter-trunk; intra-hose, inter-trunk; intra-trunk, niter-hose; and intra-hose, inter-hose.
There is trunk model model is proposed
also another trade-off between the traditional trunk and hose models. The is quite sensitive to changes in the structure of the traffic, winle the hose very robust and thus less sensitive to such changes. The provisioning strategy by the invention is also capable of controlling tins trade-off.
Extensive! research and simulations have shown that the infra-hose, inter-trunk provisioning provides the best overall performance in many traffic applications and
service model thus allows us to define service level definitions such as Agreements (SLAs) - based on the concept of site/node clusters - in a way than the pure hose and trunk models. By defining a cluster as a set k sites/nodes, we can differentiate between intra-cluster provisioning and in the service level definition.
The clust r-based provisioning generally relates to resource allocation and/or network management, and preferably includes admission control and/or network dimensioning.
in the the inter-c defined in
For cluster-based admission control, the node-to-cluster traffic limitation or limitations level definition or SLA are preferably applied for admission control on uster level. On the intra-cluster level, supplementary ultra-traffic limitations the SLA may be applied as and when desired.
preferably on the i suppleme
clusteir-based dimensioning, the capacity of a number of links in the network is dimensioned based at least partly on the node-to-cluster traffic limitation(s) r-cluster level. Typically, the dimensioning task is also based on at least one entary traffic limitation on the intra-cluster level.
The dimensioning task is preferably performed by a network design or support tool that calculates the required link capacities based on at least a subset of the traffic
Integrating such admission control SLA ensures that
limitations given in the cluster-based service level definition or SLA. a design tool in a network management module having cluster-based functionality operating based on the same traffic limitations in the the network resources and the CAC configurations are in fact aligned.
Some advantages of the invention:
if the operator
Simple implementation - only a few changes are required in the Scalable management complexity; Near-optimal trade-off between scalability and bandwidth efficiency; The proposed provisioning model is applicable effectively ever has no exact information about the traffic distribution in the network.
BRIEF DESCRIPTION OF THE DRAWINGS
will be best icr with the
The invention, together with further objects and advantages thereof understood by reference to the following description taken togetheer accompanying drawings, in winch:
Fig. 1 is a schematic illustration of the traditional trunk model; Fig. 2 is a schematic illustration of the traditional hose model;
Fig. 3 is a schematic flow diagram of an exemplary provisioning method according to an embodiment of the invention;
Fig. 4 is a schematic diagram showing a simple example of a network divided into clusters;
Fig. 5 is a schematic block diagram of network design tool according to an exemplary embodiment of the invention;
Fig. 6 is a an exempl
schematic simplified block diagram of an admission controller according to iry embodiment of the invention;
Fig. 7 illustrates an exemplary cluster definition for an illustrative core transport network;
Fig. 8 illustrates the number of average CAC entries as a function of number of clusters for an exemplary network;
Fig. 9 illustrates a comparison of the proposed provisioning models on the basis of the summed capacity for an exemplary network;
Fig. 10 illustrates used without network;
the overprovisioning when intra-hose, inter-trunk provisioning is protection, as well as with link and node protection, for an exemplary
Fig. 11 illustrates the overprovisioning factor as a function of the number of clusters with different dimensioning variants, for a large backbone reference network;
Fig. 12 illustrates the management complexity as a function of the number of clusters with different dimensioning variants, for a large backbone reference network;
Fig. 13 illustrates the management complexity as a function of the overprovisioning factor with different dimensioning variants, for a large backbone reference network;
Fig. 14 illustrates the overprovisioning factor as a function of the number of clusters for different routing strategies with the infra-hose, inter-trunk model for a large backbone reference network;
Fig. 15 illustrates the minimal acinevable management complexity 4s a function of link density with different dimensioning variants; and
Fig. 16 illustrates the minimal acinevable management complexity fo networks.
DESCRIPTION OF EMBODIMENTS OF THE INVENTION
The invention proposes cluster-based provisioning, winch implementations basically requires only minor modification to the design and preferably no new functionality in the routers.
in preferred network node
into multi-node at least two oned into basic ifj desired, and so the inerarcincal optional super
A basic idea is to partition the network or at least part of the network clusters or logical resource domains. Each such cluster hence includes nodes. At the bottom level we have the network nodes, winch are parti clusters, winch in turn may be divided into so-called super clusters i forth for any number of ingher levels. In a basic scenario, however, structure comprises network nodes partitioned into basic clusters, wit] clusters.
The idea then is to perform cluster-based provisioning of the network, including at least the intra-cluster level and the inter-cluster level, with the configuration and application of one or more novel node-to-cluster traffic limitations on
level. Tins provisioning strategy applies well to large-scale networks, and the clustering makes it possible to define the node-to-cluster limitations and find an appropriate equilibrium between management complexity and overprovisioning.
SLAs in flexible • network traffic in
The proposed service model allows us to configure service level definitions such as the the VPN context - based on the concept of site/node clusters - in a more 'ay than the pure hose and trunk models. By defining a cluster as a set of ites/nodes, we can differentiate between intra-cluster traffic and inter-cluster the service level definition (e.g. SLAs).
The selection allocatioi
of traffic provisioning model, also commonly referred to as bandwidth or admission control model, is preferably based on the available information about the traffic distribution. As a simple rule of thumb, for "known" traffic, it may be beneficial to use a trunk or trunk-like model, winle for "unknown" traffic a hose or hose-like model can be applied.
We can use trunk and hose models for intra-cluster provisioning. Trunk provisioning witinn a cluster normally means that die service level definitions (e.g. SLAs) include point-to-point limitations between each node pair in the cluster. Hose provisioning for intra-clusier traffic normally means that the total traffic to any other nodes/sites in the same cluster is limited at each node/site.
each clus provision! inter-cluster traffic
If external clusters are considered as if they were a single entity, then we could use so-called chster-based trunk or hose modeling for inter-cluster provisioning. Trunk provisioning in the context of inter-cluster traffic may for example be applied such that bandwidth for traffic aggregates to each cluster from each site/node and/or from er to each site/node is being limited. Hose provisioning for inter-cluster ng may for example be applied to impose bandwidth limitations for the total
One of tine benefits of cluster-based provisioning is that the service level definition such as th SLA can be adjusted to the traffic information available.
ictwork is hence traffic limitations invention associated traffic
As indicated in the schematic exemplary flow diagram of Fig. 3, the divided or partitioned into clusters (SI). In the next step (S2), including the novel node-to-cluster limitation or limitations proposed by the are configured or defined. Based on the clustering and the limitations, cluster-based provisioning of the network is performed (S
o the invention efficiency and e of finding a
As mentioned above, the novel provisioning strategy according typically scales well to large networks with regard to both bandwidllh configuration complexity. The provisioning strategy is also capatl balance between sensitivity to changes in the structure of the traffic anp robustness
independently of flexibility in an initial s defined witinn of intra-given between i-cluster traffic from) any other
In each considered cluster, i.e. for infra-cluster traffic, hose, trunk or a)ny other suitable
traffic provisioning model may be used. Tins implies that a traffic provisioning
sometimes referred to as an admission control model, can be selected
for each cluster in the network if desired, thus providing a ingher degree
compared to prior art network provisioning. Tins is normally performed
configuration phase. Preferably, trunk or hose type characterization
the scope of a cluster for intra-cluster traffic. Trunk-type characterization
cluster traffic typically means that node-to-node traffic demands ar£
each node pair in the cluster. Hose type characterization of intfa
typically means that the total traffic demand from (to) the node to
node in the same cluster is specified.
between the ming model can epending on the trunk or hose Trunk type traffic from (to) a
Similarly, for the description of the inter-cluster traffic (the clusters) a so-called cluster-based hose, trunk or other traffic provisi be used in the network (or for each group of clusters), preferably d available information about the traffic. Tins means that cluster-! type characterization may be applied to inter-cluster traffi characterization of inter-cluster traffic typically means that the total
node to (fi cluster traf Preferably, appropriate provisionii example, a cluster
m) another cluster is specified, winle hose type characterization of inter-c typically specifies the total inter-cluster traffic from (to) a given node, the overall provisioning strategy of the invention enables selection of an provisioning model for both infra-cluster provisioning and inter-cluster . Primarily, static traffic provisioning models are considered. For plying the concept of trunk and/or hose models to intra-cluster and inter-makes it possible to simplify traffic characterization and management without significantly degrading the bandwidth efficiency of the network.
Selecting between trunk and hose models for intra-cluster provisioning and between cluster-based trunk and hose models for inter-cluster provisioning gives the following basic comb nations:
Intra-trunk, inter-trunk: In tins case, the trunk model is used both inside the clusters and between the clusters.
Intra-hose, inter-trunk: Inside clusters, hose-based provisioning is used, and between clusters the cluster-based trunk model is used.
Intra-trunk, inter-hose: Inside clusters the trunk model is used, and for inter-cluster traffic the cluster-based hose model is used.
\ Intra-hose, inter-hose: In tins case, hose-model-based provisioning is
used both inside the clusters and between the clusters.
As previou y mentioned, the novel provisioning strategy is preferably based on a logical divi on of the network into clusters, and a differentiation between inter-cluster andintra-cl Ister traffic.
Consider a given cluster Q and a node « sitting in that cluster. Th
give the infra-cluster traffic of tins node, for example in the follow
Intra-trunk: In tins case we exactly limit the amount of traffic of u inQ.
n it is possible to ig two exemplary
:o/from each node
traffic of node u that sutn of the incoming same cluster.
Intra-hose: In tins case we limit only the sum of the outgoing goes to the other nodes in the same cluster, and the traffic of node u that comes from the other nodes in th
a so introduce two s follows.
of node u to/from erally a weaker
Consider again the node u sitting in cluster Q. Here we can
exemplary ways for describing the traffic of u outside its cluster Ck,
Inter*trunk: In tins case we preferably limit the amount of traffic each of the other clusters. Note, that tins is ge description than the traditional point-to-point trunks.
Inter-hose: In tins case for each node we limit only the sum of t that goes to (any node in) any other cluster, and the su|m traffic that comes from (any node in) any other cluster
outgoing traffic of the incoming
There may be unity between the limitations for incoming traffic an winch basically implies that we have a bi-directional limitation in pr
For the purpose of illustrating how blocks of a cluster-based servi (e.g. SLA) can be built, reference is now made to Fig. 4, winc
outgoing traffic, ctice.
e level definition shows a simple
example of a network divided into clusters. Fig. 4 shows an exemplary network, winch
is divided into three clusters, denoted 10.0.1.0, 10.0.2.0 and 10.0.3.0, respectively. The squares represent nodes such as backbone routers, and next to them the IP addresses
cated. The tables below list exemplary intra-cluster and inter-cluster paramel) rs, winch can be used to specify a service level definition (e.g. SLA) in the
node bearing the IP address 10.0.2.1 (indicated as a gray square in Fig. 4).
onfigurations are made in each concerned node.
One of the benefits of cluster-based provisioning is that the required traffic information in the service level definition such as Ihe SLA can be adjusted to the
i, the number of hose model and 3 limitations for Imitations will be ns. In the novel nitations varies 1) and each of for infra-cluster e model and the trunk model and 2 for ind inter-cluster
traffic information available. In a network with a number N of node bandwidth elements to be specified at a node is 2 for the traditiona 2(N- 1) for the traditional trunk model, assuming that there may both in-bound and out-going traffic. Naturally, the number of li reduced by a factor 2 if a single entry is employed for both directi cluster-based provisioning method, the number of bandwidth 1 between these two extremes. Given that there are M clusters (N M them have the same size (N/M 1), the number of traffic limitation traffic in a node is 2(N/M- 1) for the trunk model and 2 for the ho number of limitations for inter-cluster traffic is 2(M' - 1) for the the hose model. Thus, for the four combinations of the intra-provisioning, the total number of traffic limitations is as follows:
• ultra-trunk and inter-trunk: 2M+ 2N/M- 4.
• intra-hose and inter-trunk: 2M
• infra-trunk and inter-hose: 2N/M.
• infra-hose and inter-hose: 4.
For the specific example of N = 9 nodes and M = 3 clusters, the size N/M = 3 nodes, and the total number of traffic limitations is then e infra-trunk and inter-trunk case, 6 for the infra-hose and inter-frun infra-trunk and inter-hose, and finally 4 for the infra-hose and inter-hc
f each cluster is [ual to 8 for the case, 6 for the e case.
for a bandwidth bandwidth value. In the number of /hen a cluster is than in
If clusters are identified based on DP prefixes, the configuration entrj limitation normally includes a list of IP address prefixes and a such a case, the configuration complexity not only depends or bandwidth values but also on the number of IP address prefixes, mapped to a single IP prefix, the configuration is clearly less cases when a cluster is defined by a number of disjoint IP prefixes.
Definit on of clusters may for example follow the rules below:
A cluster is preferably defined by a set of IP addresses. Tins set can be a single IP subnet or a set of IP subnets. Naturally, other connectionless networks than IP-based networks can be used, with a corresponding cluster definition.
There could be multiple overlapping layers of clusters. In other words, one node may be part of multiple clusters.
A resource cluster is normally not restricted to be mapped to a single part of the network. It may contain multiple network parts. In most cases, a cluster includes nodes in proximity, but cases when a cluster includes disjoint network parts are not excluded.
Resources are preferably provisioned statically.
The cluster-based provisioning generally relates to resource allocation and/or network management, and preferably includes admission control and/or link capacity
The optmal selection of clusters and the corresponding dimensioning is a complex task, winch makes the application of a support tool advantageous. For example, the selectioi/configuration of the clusters may be defined as an optimization task, in winch the objective function has two components: a) minimizing the number of CAC entries/parameters and b) maximizing the bandwidth efficiency. Alternatively, the selection of clusters is preferably chosen such that bandwidth efficiency is better than a predef ned value and the number of CAC configuration parameters is less than a predefined critical value. Note that we then normally assume that the acinevable utilization increases if the number of configuration parameters increases. Note that not
just the number of CAC entries/parameters but also the number definition of clusters affects management complexity.
f subnets in the
such that the below a certain minimize the r 4 parameters in
For example, the number of configuration parameters can be minimised resulting overprovisioning compared to pure trunk provisioning is threshold percentage (say 50%). Another alternative is to overprovisioning with a fixed number of configuration parameters (sa each node).
ptimization task of clusters, and minimum
The tool then preferably includes an algorithm that performs tins given that the requirements on cluster definitions, such as mmiber inerarchy levels, maximum number of CAC entries/parameters bandwidth efficiency are specified.
The cluster selection procedure may consider one or several selecti examples of such criteria are listed below:
Cluster selection on the basis of the traffic distribution b
• IP-subnet address plan:
Cluster selection on the basis of the IP-subnet address p
Cluster selection on the basis of the network topology.
n criteria! Some
Number of CAC entries:
Cluster selection for minimizing the number of CAC entries/parameters
in the nodes.
Cluster selection for maximizing bandwidth efficiency.
gn tool preferably supports any combination of the above possibilities.
Dimensioning is preferably based on an off-line traffic-engineering tool to dimension the network according to the proposed provisioning model. As mentioned above, the cluster selection procedure finds the given number of clusters and splits the nodes betweer them, for example with respect to a well-defined optimization task such as minimizing the number of CAC entries/parameters. Alternatively, clusters are configured more or less directly in accordance with network topology or other similar factors.
In case of hose modeling, the dimensioning should preferably be based on global optimization taking into account all topology information and routing at the same time to provide the best bandwidth efficiency. In case of both hose and trunk model shortest path roui ing may be used.
In a pre
erred embodiment, the dimensioning algorithm calculates the required link
capacities based on the determined inter-cluster and infra-cluster traffic limitations/configurations, and is preferably performed by a dimensioning tool that optimize required traffic values by linear programming.
the nove Typicall traffic m designin
The dimensioning task based on intra- and inter-cluster provisioning models requires node-to-cluster constraints/limitations for computing the required capacities.
, the network dimensioning does not assume the knowledge of the actual
itrix, but only assumes some side constraints on the traffic matrix and aims at
a network that is able to carry any traffic that meets the given side
the traffic or we may set of nodes in case, two values another one for
The side constraints typically express what we know in advance what we can measure. In addition to the traditional hose and trunk li also limit the traffic between a node in a given cluster and an arbitral y another cluster or a set of other clusters. Similarly to the traditional are normally used for describing the traffic, one for the outgoing the incoming traffic.
In the following, a mere illustrative example of how the links capacities required by the cluster based bandwidth reservation method can be computed vrill be described. •The proposed algorithm is an extension of the method proposed in [71
We are given a network represented by a directed graph G = (V, E). The set V of vertices denotes the set of nodes of the network, winle the physical links are represented by the set E of edges. In tins example, it is also assumed that we are given the actual routing between any pair of nodes. Tins would basically be done by giving a for each pair of nodes u and v.
However, we use a more general way to give the routing. For each pair of nodes u and v we introduce the flow function ruv : E - [0, 1], where ruv(e) denotes the portion of the traffic between u and v that goes on the link e. In tins way, we can handle the single path routing (by setting ruv(e) to 1 on the edges of the path between u and v and to 0 on the other edges) and the shared routing as well. Once the routing is given, a given traffic matrix determines the load on the links. If tw denotes Ihe amount of the traffic from u to v then the traffic of a certain link e is:
The approach suggested by the invention does not assume knowledge of the actual traffic matrix, but only assumes a set of side constraints, and the network is preferably
dimensioned in such a way that the capacity will be sufficient for any traffic matrix that meets the side constraints. The invention preferably employs cluster-based side constraints to describe the real traffic in a more exact manner to avoid the unnecessary overdim msioning.
constraints can be classified as follows.
Trunk Parameter. Here we know the maximum amount of the traffic from a certain given node u to another one v. We denote the maximal value with Tu_v. Tins constraint can be formalized as follows.
Hose Parameter. In case of the traditional hose traffic description we limit the traffic originated from and directed to a certain node u, denoted by Tu_,v and TV-.u respectively. In mathematical formulae it means:
Cluster Bcsed Parameter. Here we limit the traffic between a node u and an arbitrary set S of ncdes (regarded as one or more other clusters). Similarly to the previous case, two values used for describing the traffic, one for the outgoing and another one for the incoming traffic, Tu_s and TSUJ respectively. In mathematical formulae:
Note that all the above constraints are linear making it possible to s optimization problems that use these constraints. Our capacity res based on a clustering of the nodes. Thus, the set of the nodes is pre; into k disjoint subsets called clusters, i.e. V = Ct u €2 u...u Ck whenever
The idea is to differentiate between the intra-cluster and the inter previously outlined, in both cases there are two natural possibilities.
Ive efficiently the
Irvation method is
and Q n Cj = 0
cluster traffic. As
Consider a given cluster Ck and a node u sitting in that cluster. Thn we can give the
intra-cluster traffic of tins node in the following two exemplary way|
Intra-trunk: In tins case we preferably limit the amount of traffic node in Q, by using the parameter Tu_v for each v e
of u to/from each
fa U V.
Intra-hose: In tins case we limit only the sum of the outgoing traffic of node u that goes to the other nodes in the same cluster, and the sum of the incoming traffic of node u that comes from the other nodes in ttye same cluster, by using the parameters Tu_,ck and Tck_u.
Inter-clu Considei exemp
again the node u sitting in cluster Q. Here we can also introduce two laiy ways for describing the traffic of u outside its cluster Q, as follows.
Inter-trunk: In tins case, we limit the amount of traffic of node u to each of a first set of other clusters and the amount of traffic of node u from each of a second set of other clusters, e.g. by using the parameters Tu_q and TCj-u for each j * k. Note that is generally a weaker description than the traditional point-to-point trunks. The first set of other clusters and the second set of other clusters are typically equal to each other, but may differ from each other.
In tins case, for each node u we limit only the sum of the outgoing traffic that goes to (any node in) any other cluster, and the sum of the incoming traffic that comes from (any node in) any other cluster than Q, by using the parameters Tu_w\ck and Tv\ck-u, respectively.
The inter-model, based hos
trunk limitations normally correspond to what is called a cluster-based trunk the inter-hose limitations normally correspond to what is called a cluster-model.
As we carry any dimension maximum maximize constraint! efficiently package [
ied, our aim is to dimension the network in such a way that it is able to possible traffic scenario that meets our preconditions. Thus we may each individual link considering the worst-case scenario. To compute tins traffic of a link e, the traffic matrix tuv that meets our preconditions and the traffic value (1) should be found. As the objective function (1) and the (2), (3), and (4) are linear functions, the value of (1) can be maximized by any linear programming method, e.g. the simple lp_solve software 8], Of course we have to repeat tins process for each edge e 6 E in order to
get the total necessary bandwidth.
Note, that ruv(e) is zero for most of the u,v pairs, so the size of the re to solve can be largely reduced by omitting each variable tuv who route does not use the edge e. It is also possible to omit the constr affect any remaining variables.
As an example, let us see the linear program when we use the intra traffic description.
linear program ; corresponding ints that do not
It has been shown that the choice of routing may have a signific bandwidth efficiency, both in trunk and hose dimensioning, dimensioning the best choice is when the traffic is routed via the leas tree routing (i.e. when the traffic is routed via a spanning tree performance for hose dimensioning. In the cluster-based provisioning the clustering divides the network into two levels, winch motivates th
the effect of multi-level routing solutions. Applying for example shorlfest-path and tree routing, gives the following additional routing scenarios:
Shortest path intra-cluster / Shortest path inter-cluster. Shortest path mtra-cluster / Tree inter-cluster. Tree intra-cluster / Shortest path inter-cluster. Tree intra-cluster Tree inter-cluster.
ents and simulations have shown that bandwidth efficiency can be increased if is adjusted to the selected provisioning method. Therefore, routing
also be later in
optimisation in connection with calculation and configuration of explicit routes may function of a design tool. More details on routing optimization will be given
onnection with the VPN context.
Fig. 5 i
a schematic block diagram of network design tool according to an exemplary
embodiment of the invention. The exemplary network design tool 100 is preferably an interact ve design or support tool, and basically comprises a user interface 110, a configurations module 120 and preferably also a dimensioning module 130. The configurations module 120 typically includes a cluster selection unit 122, a provisioning model selection unit 124, a service level definition unit 126 and an
routing scheme selection unit 128. The operator may enter input information
and/or configuration settings via the user interface 110, and information may also be input from the network, including the edge routers. Cluster selection is performed by cluster sslection unit 122 in response to the relevant input information, for example as describe! above. Suitable provisioning model(s) such as (cluster-based) hose and/or trunk models are configured in selection unit 124. Both inter-cluster and intra-cluster service 1 jvel definitions are typically configured (input) in the service level definition unit 126 In the optional routing scheme selector 128, routing may be adjusted to the selected provisioning model(s) to increase bandwidth efficiency. The design tool may then inchde functionality for routing optimization in connection with calculation and configuration of explicit routes. Based on the configuration settings and the cluster-based service level definition, the dimensioning module 130 preferably performs constrained link capacity dimensioning. Tins typically means that the links are
c limitations on ementary traffic eijisioning module gramming. The executed in a Resign tool from
dimensioned based at least partly on one or more node-to-cluster traf the inter-cluster level, and preferably also based on one or more supp limitations on the intra-cluster level. As mentioned above, the dim may be configured to optimize required traffic values by linear pr design tool functionality is typically implemented in software an network management computer, but there is notinng that prevents the being implemented in hardware or firmware.
Her according to n controller )200 fubction 220. The loning model(s), ter definition is mechanism. The ihe service level .dmission control limitations for the s related to real-s processed by the bandwidth •uld be rejected, node or edge
Fig. 6 is a schematic simplified block diagram of an admission contn an exemplary embodiment of the invention. The exemplary admissi includes a configurations module 210 and an admission control configurations module includes means 212 for defining suitable provi and a cluster-based service level definition module 214. The chu normally done manually node by node or centrally by some remote admission control function is assumed to reflect the structure of definitions, such as the SLAs in the VPN context. In other words, the function normally includes or operates based on the same bandwidth same traffic aggregates as the part of the service level definition that time traffic. For admission control, a new connection request identifying the appropriate bandwidth limitation, and then applyin limitation to determine whether the connection can be accepted or sty The CAC functionality is normally arranged in each concerned router.
:o an exemplary
In the following, the invention will be described with reference
icreto, but rather lobile networks,
implementation for so-called media gateway nodes in a mobile core t -ansport network. It should however be understood that the invention is not limited t
applicable to general communication networks including fixed and VPN networks as well as other types of networks.
Exemplary implementation in the context of a mobile core network
In an sxemplary embodiment of the invention, winch is especially adapted for a mobile core network, an integrated combination of trunk, hose and MBAC-based network provisioning is exploited. The admission control is preferably divided in:
dmission during normal conditions and single fault events: Static provisioning visioning of clusters.
nexpected congestion in multiple fault conditions: Preferably, MBAC is d in order to block calls if measured loss ratio exceeds the configured level. '
Static p In the s nodes(
ovisioning of clusters
me way as previously described, the core network with its media gateway
GWs) is divided into clusters or logical resource domains to limit the number
of confijjuration parameters in the MGWs in a large-scale topology. The configuration of the ac mission control preferably comprises entries of the following format:
cluster definition bandwidth limit(s)
where the cluster definition may be a list of IP subnets, and a cluster is defined as a set ofMGWs.
A possible cluster definition for an illustrative core transport network is shown in Fig. 7. It should be understood that more than two levels, i.e. the underlying nodes and the clusters, can be included in the logical network representation. In the example of Fig. 7, w(s have optional super-clusters indicated by ellipses. Note that sites can also be considered as clusters.
A possible set of entries of admission control in MOW 6 (in Site 6) is as
Inter-cluster trunk/intra-cluster trunk model
Cluster A BW ClusterBlBW Cluster B2 BW
Site Router 0 BW Site Router 3 BW Site Router 10 BW
In tins example, Cluster C should be dimensioned according to trunk model. The traffic between cluster A, Bl, B2 and C is also dimensioned according to the trunk model.
If the bandwidth efficiency of hose dimensioning is sufficient for the traffic of Cluster C then the above list can be replaced by:
Inter-cluster trunk/intra-cluster hose model
Cluster A BW ClusterBlBW Cluster B2 BW
Cluster C BW
3S of other provisioning models include:
Inter-cluster hose/intra-cluster trunk model
(common hose parameters)
Site Router 0BW Site Router 3 BW Site Router 10 BW
Inter-cluster hose/intra-cluster hose model
Many oiher combinations of clusters could be configured in the MGWs, winch inherently imply different dimensioning of the links.
Requirements on the MGWs
The basic criterion for using the above network model is to distinguish clusters in the admission control of MGWs. Tins differentiation can for example be done using IP-subnet ad dresses, or based on any other suitable criteria.
e to define a ihould allow the
The addressing plan of the core network can be such that it is impssibl single IP subnet for a whole cluster. Therefore, the MGWs configuration of multiple IP subnets for a single CAC entry.
To use static admission control, bandwidth limits should be configu|red for each CAC entry.
statistics and drop statistics may connection can be limit AND if the
If desired, admission control could take into account packet bandwidth limit for the configured clusters in the MOW. Therefore, still be aggregated for the configured clusters in the CAC. A admitted if the measured loss ratio is smaller than the configured bandwidth of admitted connections does not exceed the configured liinit
From the viewpoint of fault tolerance three redundancy solutions ma;
1. No redundancy
2. Single link failure
3. Single node failure
Results on an exemplary network
In the following, a brief performance analysis of the proposed provisioning model is
presented in case of a realistic mobile core network where the trafjfic parameters are
From the viewpoint of the MGWs it is very important how many CAC entries/parameters should be configured in case of the different provisioning models and cluster numbers. In Fig. 8, the number of average CAC entries can be seen as a function of number of clusters.
In Fig. 9 capacity.
From the best, but importan clusters i
Based on off betwe inter-trun
pasis of Fig. 8 it can be noted that three clusters provide the lowest average f CAC entries per MOW. From the viewpoint of CAC entries, the most ous provisioning method is the intra-hose, inter-hose, but the intra-hose and c is also very suitable, especially in the interval of 2-4 clusters in the
the proposed provisioning models are compared on the basis of the summed
viewpoint of required bandwidth the intra-trunk, inter-trunk model is the be intra-hose, inter trunk-model also provides very attractive results. It is to note that from the viewpoint of summed capacity the suitable number of three, if the target-overprovisioning factor is around 20%.
the results of Figs. 8 and 9, it may be concluded that with regard to a trade-en the number of CAC entries and bandwidth efficiency, the intra-hose, model provides the best overall performance.
The i intra-hose routing o will be on.
of different routing strategies has been investigated. In tins regard, the inter-trunk provisioning model may advantageously be combined with tree the intra-cluster level and shortest path routing on the inter-cluster level, as appreciated from the simulations on routing optimization to be described later
Protection for link and/or node failures may also be provided, e.g. by re-routing or by using back-up paths. The impact of link and node protection has also been investigated.
Fig. 10 sh without pr
ws the overprovisioning when intra-hose, inter-trunk provisioning is used lection, as well as with link and node protection.
A complementary description of the invention for the specific context Network (VPN) will now be described.
Df a Virtual Private
e in the enterprise in operating their
resources and exible bandwidth
goal of VPN ased management . On the other
Exemplary implementation in the VPN context
In general, Virtual Private Networks (WNs) play an important ro business mainly because they provide great flexibility for customers networks. Solutions are also developed to attract customers with limited infrastructure for network management. Offering simple and : management models for customers is also considered as an important providers. Simplicity for the customer, however, often means incr effort and less efficient network utilization for the network operator hand, reduced network efficiency and more management operational costs and yield more expensive services.
models are two me operation and known as trunk ch VPN site pair
each pair of sites.
. , est way, since the
acities if routing ic communication ers may be unable it difficult to Agreement (SLA), is hard to specify
ic management of
As previously mentioned, hose and trunk resource provisionin examples of resolutions of the conflict between efficient backb flexible bandwidth model. In the customer-pipe model, winch is model, point-to-point traffic demands are specified between ea allowing the operator to independently reserve bandwidth between Tins model enables the VPN provider to utilize the network in the known traffic matrix determines exactly the required link ca information is also known. The critical part of tins model is that pattern between the end-points is very difficult to estimate. Custon to exactly predict and define traffic loads between the sites, specify the complete site-to-site traffic matrix for the Service Level Even if the estimation of the traffic matrix is supported by tools, i the proper bandwidth requirement due to traffic fluctuations.
Another drawback of the customer-pipe model is the complexity of
trunks. Resource reservations needs to be configured in each source node to each sink
node, including policing configuration for the provider and shaping/admission control configuration for the customer. If a full mesh logical network is assumed between the customer's sites then the sum of parameters to be configured is proportional to the square of the number of nodes in the VPN. Therefore, configuration complexity may become the main drawback of (he trunk model in case of large-scale networks.
The hose model takes a more pragmatic approach by requiring only the specification of the aggregated incoming and the aggregated outgoing traffic volumes at each node. These traffic parameters can be specified either according to the physical capacity of the link to the provider's network or based on measurements. Winchever approach is used, the estimation of traffic demand is easier and more precise compared to the customer-pipe model. Configuring hose parameters requires much less effort from both customers and providers man configuration of trunks. Only one incoming and one outgoing hose parameter should be configured in each source node. Thus, the number of configuration parameters is proportional to the number of VPN sites. These properties make the hose model definitely attractive for customers. On the other hand, the application of the hose model has a great impact on resource provisioning in the VPN backbone. Network dimensioning based on partial information on the traffic demands yields overdimensioning compared to trunk model, if the same service performance is required in both cases. Furthermore, the required overprovisioning increase! significantly with the size of the network, regarding both the number of nodes and the number of links.
Hence, i well to 1
can be seen that the conventional resource provisioning methods do not scale rge VPN networks.
By dividing the network into multi-node clusters, performing cluster-based provisioning of the network on at least two levels and using cluster-based traffic 0n we can find an appropriate equilibrium between management complexity in the same or similar manner as previously described. Such a
istering makes it nstead of simply and the poiit-to-everywhere to-cluster traffic e as the key to
provisioning strategy applies well to large-scale networks, and the c possible to characterize the VPN traffic by point-to-cluster demands, the point-to-point demands of the traditional trunk model demands of the traditional hose model. These new so-called node limitations are typically applied on the inter-cluster level, and sen improved performance in the VPN networks.
level agreement y has a policing SLA. The VPN same purpose, on for real-time specified in e structure of the aggregates as
For example, consider a QoS-enabled VPN with static service between the VPN provider and customer. The VPN provider typica function that controls the ingress/egress traffic in accordance with th customer may also have a shaper at the network edges for th Furthermore, the customer may operate an admission control func services to avoid QoS degradation due to exceeding the traffic limitations the SLA. The admission control function is also assumed to reflect th SLA, i.e. it includes the same bandwidth limitations for the same traffic the part of the SLA that is related to real-time traffic.
The management of a VPN arcintecture generally includes tasks for ti as well as for the VPN provider. It is often up to the VPN customer in the network and renegotiate SLAs when traffic exceeds a given 1 the admission control and shaping in accordance with the SLA is als of the VPN customer. On the other hand, it is normally the responsi provider to ensure that the bandwidth specified in the SLA is alway backbone. In case of re-negotiation, the provider has to check if he increased traffic or some of the links need to be upgraded. It is also to configure the policing function according to the SLAs.
e VPN customer measure traffic
mit. Configuring usually the task
ilityofthe VPN available in the
an cope with the
5 to the provider
The main interest of the VPN providers is to facilitate the tasks of ti offering simple SLAs. However, under-specified traffic d
sir customers by criptions yield
overprovisioning winch makes the offerings more expensive. Therefore, a reasonable
balance is requir
The prq based or trunk m between allows ti specific simplifie backbon
The firs measurement
etween WN management complexity and overprovisioning in the backbone d.
osed service model allows us to configure the SLAs in the VPN context -the concept of site clusters - in a more flexible way than the pure hoserand dels. By defining a cluster as a set of VPN sites/nodes, we can differentiate intra-cluster provisioning and inter-cluster provisioning in the SLAs. Tins e VPN operator to customize the service offering to the requirements of the VPN customer. Thus, traffic characterization and management could be i without significantly degrading the bandwidth efficiency of the WN
SLA, th previous! information customer
task, winch is affected by the cluster-based provisioning is traffic and SLA re-negotiation. The larger aggregates that are the subject of the easier to identify that the SLA needs to be renegotiated. As indicated , one of the benefits of cluster-based provisioning is that the required traffic in the SLA can be adjusted to the traffic information available for the
The othe mentioned task for the VPN customer is the configuration of admission control f r real-time traffic or shaping for best-effort traffic, shortly management complexiljy. In tins context, another advantage of cluster-based provisioning is its scalable management complexity.
The form cluster-1 elements may be multiple
of SLA considerably affects the management complexity. An SLA for •based provisioning may include point-to-point elements, point-to-single-cluster ind point-to-multi-cluster elements. In other words, bandwidth limitations figured for a set of sites, winch may be a single site, a cluster or even lusters. As shaping and admission control at the customer often identify on the IP prefixes, the configuration entry for a bandwidth limitation in
and one or more ds on the number dress prefixes, as
prefix then the udes ?. number of
any of these functions typically includes a list of IP address prefixe bandwidth values. Thus, the configuration complexity not only depe of bandwidth values but may also depend on the number of IP a already indicated before. When a cluster is mapped to a single configuration is clearly less cumbersome than in the case when it inc disjoint prefixes. Therefore, if clusters are already defined at the then the addressing plan should preferably take them into account.
VPNs are normally implemented with some kind of tunneling usually also assumes that the IP addressing of the VPN is in addressing of the IP backbone. Shaping and admission control a placed at the customer, so that they are based on the addressing independence of backbone and VPN addresses makes it possible to addressing plan tailored to the actual VPN independently of other V definitions can be local to the VPN.
technique, winch dependent of the e assumed to be of the VPN. The define an optimal 3Ns. Thus, cluster
uire slightly more tween IP address from a number tween bandwidth on complexity.
If IP addressing is fixed in the VPN, then cluster definitions should preferably consider the addressing plan. For example, it may be a better choice to req over-provisioning in the backbone to allow one-to-one mapping b prefixes and clusters than defining clusters based on physical topol of disjoint IP prefixes. Anyhow, it is clear that there is a trade-off b efficiency, number of SLA parameters to be estimated and configura
Returning to the responsibilities of the VPN provider. Besides th policing, whose management complexity is similar to that of shap control at the customer, the VPN provider has to check if the backb
configuration of ng and admission ne links can cope
with the traffic limited by ingress policers. In tins respect, the cluster-based method is somewhat similar to hose provisioning in that more complex calculations are needed to fulfill tins task due to the current lack of a resource reservation protocol supporting hose-based and clusters-based reservations. Checking network resources against trunk-
based n source requests is normally easier since all resource reservation protocols, such as aggregate RSVP or future NSIS protocol for routed IP VPNs and RSVP-TE for MPLS VPNs, support trunk reservations. The provider may also manage the task of optimizing routing, as previously described, so that the actually used network resources are minimized. Thus, it is desirable for the VPN provider to try to solve the optimization task with requirements or restrictions on minimum bandwidth efficiency, maximum number of bandwidth limitations and maximum number of IP prefixes. Preferaby, the basic link capacity algorithm described above is implemented in a network design tool by the VPN provider for calculating the necessary link capacities for traffic given by the selected cluster-based description, making it possible to design congestion-free networks.
The applicability and limitations of the proposed methodology and the effect of different routing strategies and fault tolerance have been examined by simulating several t st scenarios for VPN networks. In the following, we will briefly present a limited b t yet illustrative selection of these simulations.
In the simulations, the AT&T reference backbone network with its publicly available topology Iwas used as a basis for the performance analysis. We mainly considered only the part of the network made up of the Gateway nodes, backbone nodes connected with N QC48 and N OC192 links, to obtain our test network comprising 25 sites connecte with 44 links.
First, we compare the proposed cluster based provisioning for the different variants without considering routing optimization and protection methods. We then study how routing optimization can be used to improve the bandwidth efficiency. Finally, we mention tie effect of protection methods on the results.
[umber of clusters iioning variants is jtion methods are lexity are the key ulate theifi fa* the T&T network, as dimensioning for each following names
Fig. 11 illustrates the overprovisioning factor as a function of the with different dimensioning variants. The comparison of the provi here based on shortest path routing and assumes that no protei applied. The capacity of required links and the management com measures characterizing the performance of the methods, so we cal evaluation. The studied network scenario is based on the 25 node mentioned, and a pre-calculated traffic matrix. We performed di possible number of clusters (from 1 to 25). From now on we use th for the cluster-based provisioning variants for short reference:
uster traffic, bster traffic.
• 'tt': Trunk for infra-cluster and inter-cluster traffic.
• 'th1: Trunk for infra-cluster traffic and hose for inter-c
• Tit1: Hose for infra-cluster traffic and trunk for inter-c
• Tin': Hose for infra-cluster and inter-cluster traffic.
k model, i.e. the visioning variant
Fig. 11 shows the overprovisioning factor compared to the frui relative difference between the capacity need for the evaluated pn and the pure trunk model.
, winch is closely hose and trunk he figures, as they ere is one cluster thods 'tt' and 'th1 when there are 25
model and 'tt1 and
Fig. 12 presents the average number of bandwidth limitations per si related to management complexity. Note, that although the pu: provisioning is not displayed explicitly, their results can be seen in are equivalent to specific cases of the cluster-based methods: If th then method 'hf and *hh' is equivalent to hose model and m correspond to trunk model. If each site is in a separate cluster (i.e. clusters in the AT&T network) then Tib' and 'th1 corresponds to "hf is the trunk model.
Results for all of the four variants of the cluster-based method are between the results of hose and trunk provisioning, regarding both link capacity and management
complexity. The figures also inghlight the trade-off between bandwidth efficiency and management complexity. To compare the variants, the real question is the necessary management complexity using a clustering that provides a certain targeted overprovisioning. The management complexity - overprovisioning scatterplot in Fig. 13 ccmpares the variant from tins point view. The dots represent the management comp exity and overprovisioning values for the above cluster configurations. It can be seen that method "hf is the best in tins sense on the AT&T network: it requires the least management complexity for any fixed overprovisioning. For example, by allowing 40% («tra bandwidth in the backbone over the requirement of the trunk model, the needol configuration parameters in a site decreases from 25 to 5. Note that the hose model would require 160% extra bandwidth with a single parameter in each site.
The reason why hose provisioning is better than trunk provisioning on the intra-cluster level is that link capacities inside the cluster are not very sensitive to the provisioning method, but trunk model needs much more configuration parameters than hose. The small difference in capacities is because the topology of a cluster is typically close to a tree, winch is the optimal scenario for the hose model, due to the sparse topology of the example AT&T backbone network.
For inter-cluster provisioning, trunk provisioning significantly overperforms the hose method because traffic to different clusters typically go via different paths. Thus, ignoring the destination clusters in the SLAs (i.e. using hose provisioning for inter-cluster traffic) means that the worst case traffic towards each cluster is the sum of all inter-cluster traffic as opposed to the trunk model where only the traffic of the specific destination cluster need to be considered.
In the f blowing, the main focus will be on the performance of tins intra-hose, inter-trunk variant from different aspects.
Similar tests were made for the other methods as well, and the results confirmed the expectation that using tree routing where hose dimensioning is applied and shortest path routing in network segments dimensioned based on trunk model are the best choices regarding the routing. Thus, there is a best routing type for each of our cluster-based methods, as follows:
• routing 'tt' for method 'hh'
• routing 'ts' for method 'ht'
• routing 'st' for method 'th'
• routing -'ss' for method 'tt'.
Tins confirmed the notion that performance such as bandwidth efficiency can be increased if routing is adjusted to the selected provisioning method.
We also investigated how the four methods perform with their best routing. With regard to management complexity as the function of overprovisioning at different dimensioning methods with optimal routing, the situation is very similar to that of using shortest path routing for each method. The most important difference is that one can not state that method 'ht' is the overall best, because it has been found that if the overprovisioning factor is 50% or ingher, some 'th' and 'hh' configurations requires less management complexity to acineve the same overprovisioning, though the difference is almost negligible.
One may suspect that the efficiency of routing strategies is sensitive to the underlying topology. To investigate tins, the proposed methods were also tested on randomly generated network topologies. First random topologies with the same number of nodes and links as the AT&T network were analyzed. The average link capacities of 10 different random graphs were computed for each of the four methods with their best routing, and it was found that there is no significant difference between the random
Similar tests were made for the other methods as well, and the results confirmed expectation that using tree routing where hose dimensioning is applied and short path routing in network segments dimensioned based on trunk model are the b choices regarding the routing. Thus, there is a best routing type for each of our clust jased methods, as follows:
• routing 'tt1 for method lib'
• routing 'ts1 for method 'ht1
• routing 'st1 for method 'thf
• routing 'ss1 for method 'tt1.
tins confirmed the notion that performance such as bandwidth efficiency can increased if routing is adjusted to the selected provisioning method.
We also investigated how the four methods perform with their best routing. W regard to management complexity as the function of overprovisioning at diffen dimensioning methods with optimal routing, the situation is very similar to mat i sing shortest path routing for each method. The most important difference is that o can not state that method 'ht' is the overall best, because it has been found that if 1 c verprovisioning factor is 50% or ingher, some 'th1 and 'hh' configurations requires 1 management complexity to acineve the same overprovisioning, though the differen in almost negligible.
One may suspect that the efficiency of routing strategies is sensitive to the underlyi topology. To investigate tins, the proposed methods were also tested on random generated network topologies. First random topologies with the same number of nod aid links as the AT&T network were analyzed. The average link capacities of d fferent random graphs were computed for each of the four methods with their b routing, and it was found that there is no significant difference between the randc
case and the AT&T network, the method 'ht1 apparently performs topology as well.
well on a generic
|ed by generating case) winle ic number of links ijom graphs for 11 imputed. Then the Ictor less than 50% best regardless of jurve of 'tt1 as the i' is missing the target 50%
The effect of link density of the network were also investiga topologies with the same number of nodes (it was 25 in our varying the average degree of the nodes (or equivalently varying ti in the network). The average link capacities of 10 different ran different average node degree from 2.5 to 7.5 in 0.5 steps were o minimal management complexity providing an overdimensioning ft was determined. Fig. 15 shows that method Tit' still performs the link density, but its performance gets worse and approaches the number of link in the network increases. Note that the curve because there is no configuration of that method winch could overprovisioning at any network density.
Another important question is how the provisioning methods seal size. So, tins is the next step in the evaluation of the cluster-methods. The studied networks were generated randomly as previo the number of interfaces in a router is limited and networks usuall with similar capabilities, we compared such networks in winch the]
with the network
sly mentioned. As
consist of routers
average degree of
50 nodes in steps
ic average of the
the nodes were kept constant - in our case it was 4 - when changing the number of
nodes. During the test we investigated networks consisting of 10 t of 10. We investigated 10 different topologies and calculated (I network capacities for each scenario. We examined all four cluster]'
methods with their best routing strategy at all possible number of cljisters from 1 to the
number of nodes. We then looked up the minimum management
whole network, cannot fulfill the
those configurations where the resulted overprovisioning factor w|s below 50%. Fig.
16 shows the minimal number of parameters to be configured in The curve of the Tin1 method is missing again, winch means that
target 50% overprovisioning neither in small nor in large networks. The curves of
methods Tit' and 'tt' are linear winch indicates that the number of parameters to be configured increases proportionally to the number of nodes, the difference is that the 'ht1 method provides smaller complexity. In contrast to them, the curve of the 'th1 method is increases rapidly at ingher number of network nodes suggesting that the method should typically not be used in large networks.
In backbone networks one of the most important requirement is fault tolerance. Tins fact motivated some tests to examine how much overprovisioning is needed to provide certain fault tolerance using traditional dimensioning methods and the proposed cluster based i schemes. Tunneling techniques used for VPNs can be different. The major difference regarding protection methods is if the backbone is a routed IP network or an MPLS-based network.
If the VPN backbone is a routed IP network, then the route of packets is normally determined based on the actual content of the routing tables. As a result of a link
the routing tables of the affected routers will be then updated by routing s. When all routing tables are updated based on the changed link state
uiformapon, the packets are routed via the shortest path considering only the remaining links. Tins process may take a few minutes. It also means that the protection path of a given flow depends on the failed link.
If the VPN backbone is an MPLS network, then the advanced failure handling features of MPLS can be used. One of the techniques for protection in MPLS is using backup label switched paths. In other words, two LSPs are usually set up between each pair of sites, a primary and a secondary. When all links are up then the primary LSP is used for communication. Whenever a link along the path of the primary LSP fails, traffic is rerouted to the secondary LSP. To ensure that the secondary LSP can be used in case of any failure along the path of the primary LSP, the two LSPs must be disjoint. As LSPs are set up before the actual link failure, the protection path of a given flow is independent of winch link is failed. An advantage of tins technique is the much faster
fail-over time than IP routing. Note that fast re-route is another protection in MPLS networks, winch is often used in combination w It has even faster fail-over time than switcinng over to the backup L local detour between the nodes connected by the failed link.
The effect of protection methods in routed IP networks and in MP LSPs was also examined, assuming shared protection for single link failures. In other words, network dimensioning was performed in such will support the rerouted traffic in case of any link or any node fails, time. In the case of a link failure the topology of the network and th change. When a node fails, then all of its links are removed from the traffic is also removed from the traffic matrix.
The effect of protection methods in the case of a routed native examined, and the results indicate that applying protection does n relative performance of the four variants of cluster-based provisioning the'effect of routing strategies for method Tit', the results suggest thai strategy among the investigated ones is simple shortest path administrative weights in the backbone are independent of clustering.
possibility for h backup LSPs. P by creating a
S with backup
nd single node
a way that links
ut only one at a
route of flows :opology and its
t influence the
With respect to
the best routing
jvisioning as a thods is similar itrategies on the ed, and here one ifference in the
The effect of a path-protecting redundancy mechanism on the perfonjiance of cluster-based provisioning was also investigated. With respect to overp: function of the number of clusters, the efficiency of the protection rrj
for native IP VPNS and MPLS-based VPNs. The effect of routing required overprovisioning for the cluster-based methods was also stu can see that using different routing strategies makes no significant
e configured to h contrary, path
result. The reason for tins is that the applied routing strategies determ|ine only how the
administrative weights are set on the links in the network. Weights j force the primary route to the aimed path in a routed IP network.
protection is based on Edmonds1 algorithm that chooses the primary and secondary
paths such that the summed costs of the two paths will be minimal, so the shortest path and the primary path could be different.
summary, the cluster-based provisioning method makes it possible to define point-nt(cluster) SLAs between VPN providers and customers. The proposed dimensioning algorithm calculates, preferably using linear programming, link capacities such that none of the links could get congested even at worst case traffic distribution constrained by point-to-cluster traffic limitations at network edges and assuming that routing is known in advance. The congestion-free network design allows the VPN customer to use non-adaptive real-time services over the VPN, winch would be degraded in case of congestion. The dimensioning algorithm is clearly an inevitable tool for the VPN provider offering cluster-based SLAs and QoS guarantees, because the task bf checking the availability of network resources manually is complex and no IP based resource reservation protocol supports it.
the studied network examples, it can be concluded that the best among the variants of the cluster-based-provisioning, winch needs the least number of nfigurajtion parameters to acineve the same overprovisioning target, was the one hose-like limitations for ultra-cluster traffic and trunk-like limitations for er traffic. Tins variant remained the best irrespectively of the network with and without protection and for optimized routing too.
It proved to be the best compromise between hose and trunk model. In the studied 25-node network, using five clusters decreased the number of bandwidth limitations per node froni 24 to 5, and increased the required link bandwidth by 40% without route optimization compared to trunk model. At the same network, the extra capacity needed by the hose model was 160%.
Route optimization further decreased the overdimensioning of the cluster-based provisioning, in the above example of rive clusters from 40% to 25%. A two-level
iter-cluster-tnmk path routing
routing strategy was the best for the selected intra-cluster-hose model, winch applied tree routing inside each cluster and shortest between clusters.
Tolerance for single failures in a routed IP network required 135% the trunk model. By using cluster-based provisioning with five clus capacity increased with another 35% (with 170% compared protection). Simple shortest path routing, winch is independent of and thus the same for all VPNS, was generally the best routing strate
xtra capacity for ;rs, the total link trunk without luster definitions y.
a close-optimal sites. If cluster
can be mapped the SLA can be 'N is rigid, then ch results in less addresses, winch d method can be
It was assumed during the simulations that clusters are selected wi heuristics, winch is followed by IP address allocation for VPN definition and address allocation has the above order then each clust r to a single IP prefix, winch means that each bandwidth limitation i assigned to a single IP prefix. However, if IP addressing of the V either the clusters need to be defined based on the IP addressing, wh gain-in bandwidth efficiency, or cluster definitions include a list of IP increases management complexity. So, the benefits of the cluster-bas fully exploited when IP addressing can be adjusted to clusters.
The embodiments described above are merely given as examples, understood that the present invention is not limited thereto. Furti changes and improvements winch retain the basic underlying principl are also witinn the scope of the invention.
and it should be er modifications, s disclosed herein
ATM Asynchronous Transfer Mode
CAC Connection Admission Control
CSPF Constraint based Shortest Path First
GGSN Gateway GPRS Support Node
HLR Home Location Register
LSP Label Switched Path
MBAC Measurement Based Connection Admission Control
MGW Media Gateway
MPLS Multiple Protocol Label Switcinng
O&M Operation and Maintenance
QoS Quality of Service
RNC Radio Network Controller
RTP Real-time Transfer Protocol
SGSN Serving GPRS Support Node
TIPI Transport IP Infrastructure
UMTS Universal Mobile Telecommunications System
VC/VP Virtual Circuit/ Virtual Path
I. Szab6, "On call Admission Control for IP TelephoW in Best Effort Netwoi'-s", Computer Communications, 26 (2003) pp. 304-313.
Measurement Based Telephony", SCS, of Computer and
I. Szab6, "Performance evaluation of a New End-to-end Call Admission Control Scheme for Supporting IP International Symposium on Performance Evaluation Telecommunication Systems, Orlando, Florida, July 2001.
 J. A. Fingerhut, S. Suri, J. S. Turner, "Designing leas
broadband networks", Journal of Algorithms, Vol. 24, ijo. 2, pp. 287-309, August 1997.
Mishra and K. K. for Resource (fcomm, San Diego,
N. G. Duffield and P. Goyal and A. Greenberg and P. Ramakrishnan and J. E. Van der Merwe, "A Flexible Management in Virtual Private Networks", ACM Sig California, USA, August 1999.
A. Kumar and R. Rastogi and A. Silberschatz and B. Yerer, "Algorithms for Provisioning Virtual Private Networks in the Hose Model", ACM Sigcomm, Cambridge, Massachusetts, USA, August 2001
Algorithms for Virtual York, USA, June
G. Italiano and R. Rastogi and B. Yener, "Restoration Private Networks in the Hose Model", IEEE Infocom, 2002.
Alpar Jttttner, Istvan Szabo, and Aron Szentesi. "On bandwidth efficiency of the hose resource management model in virtual private networks", IEEE Infocom, April 2003.
A. Minoux, "Network synthesis and optimum network design problems: Models, solution methods and applications", Networks, vol. 13, pp. 313-360, 989.
. Pioro, A. Juttner, J. Harmatos, A. Szentesi, P. Gajowniczek, and A. dyslek, "Topological design of telecommunication networks: Nodes and links realization under demand constraints", in 17th International Teletraffic ongress, Salvador de Baina, September 2001.
M.. Pidro, A. Myslek, A. Jiittner, J. Harmatos, and A. Szentesi, "Topological esign of MPLS networks", in Global Communication Conference LOBECOM 2001), San Antonio, Texas, USA, November 2001.
M.. Pioro and P. Gajowniczek, "Solving multicommodity integral flow problems by simulated allocation", Telecommunication Systems, vol. 1, no. 3, pp. 17 28, 1997.
Cinkler, T. Henk, and G. Gordos, "Stochastic algorithms for design of thrifty single-failure-protected networks", DRCN 2000,2000.
1. Maliosz and T. Cinkler, "Methods for Optical VPN Design over Multifiber avelength Routing Networks", in Proc. ONDM, Budapest, Hungary, ebruary2003.
. Maliosz and T. Cinkler, "Optimizing Configuration of Virtual Private etworks", in Proc. Polish-Czech-Hungarian Workshop, September 2001, pp. 241 247.
 T. Cinkler and M. Maliosz, "Configuration of Protected Virtual Private Networks", in Proc. Tinrd International Workshop on DESIGN OF RELIABLE COMMUNICATION NETWORKS, October 2001.
PESIGNER: A , in Proc. 8th 98, Sorrento,
 K. G. Ramakrishnan, D. Mitra, and J. A. Morrison, "VPN Tool for Design of Multiservice Virtual Private Networks International Telecom. Network Planning Symp, NETWORKS Italy, 1998, pp. 153-158.
Resource ', University of
 Chen-Nee Chuah, "A Scalable Framework for IP-Nerwork Provisioning Through Aggregation and inerarcincal Control California, Berkeley, 2001.
 M. Berkelaar and J. Dirks, "lp_solve 4.0", to be found a|t the ftp-server ftp://ftp.es.ele.tue.nl/pub/lp_solve.
1. A method for improving bandwidth efficiency of a communication
network by resource allocation and management, wherein the communication
network has a set of network nodes (1,2, 3, 4, 5, 6, 7, 8, 9, 10), said method
comprising the steps of:
-partitioning a number of said network nodes (1, 2, 3, 4, 5, 6, 7, 8, 9, 10) into clusters (A, B, B1, B2, C1, C2), each cluster having at least two nodes;
-defining traffic limitations on at least two levels, including defining traffic limitations on an intra-cluster level and defining traffic limitations on an inter-cluster level,
-associating traffic limitations on said levels, said traffic limitations including at least one node- to-cluster traffic limitation for inter-cluster traffic;
-allocating and managing resources in the communication network by performing cluster-based provisioning based on said traffic limitations, such that the bandwidth efficiency is improved.
2. The method as claimed in claim 1, wherein said step of allocating and managing resources comprises the step of applying one of a cluster-based trunk model and a cluster-based hose model involves said at least one node-to-cluster traffic limitation on the inter-cluster level.
3. The method as claimed in claim 2, wherein said step of allocating and managing resources comprises the step of applying at least one of a trunk model and a hose model involving at least one supplementary traffic limitation on the intra- cluster level.
4. The method as claimed in claim 1, wherein said step of allocating and managing resources comprises a cluster based service level definition module (214) for
-applying a cluster-based trunk model involving said at least one node-to-cluster traffic limitation on the inter-cluster level; and
-applying a cluster- based hose model involving at least one supplementary traffic limitation in at least one cluster on the intra-cluster level.
5. The method as claimed in claim 1, wherein said at least one node-to-cluster traffic limitation is defined to limit, for at least one given node (1, 2, 3, 4,5, 6, 7, 8, 9, 10) in a given cluster (A, B, B1, B2, C1, C2), the amount of traffic in relation to at least one other cluster.
6. The method as claimed in claim 5, wherein said at least one node-to-cluster traffic limitation includes:
-at least one limitation defined to limit, for a given node (1, 2, 3, 4,5, 6, 7, 8, 9, 10) in a given cluster (A, B, Bl, B2, C1, C2), the amount of traffic to at least one other cluster; and
-at least one limitation defined to limit, for said given node in said given cluster, the amount of traffic from at least one other cluster.
7. The method as claimed in claim 5, wherein a cluster-based hose model is
applied on the inter-cluster level and said at least one node-to-cluster limitation
-a first limitation defined to limit, for a given node (1, 2, 3, 4, 5, 6, 7, 8, 9, 10) in a given cluster (A, B, Bl, B2, C1, C2), the sum of outgoing traffic that goes to any other cluster; and
-a second limitation defined to limit, for said given node in said given cluster, the sum of incoming traffic that comes from any other cluster.
8. The method as claimed in claim 5, wherein a cluster-based trunk model is
applied on the inter-cluster level and said at least one node-to-cluster limitation
-a first set of limitations defined to limit, for a given node (1,2, 3, 4, 5, 6, 7, 8, 9, 10) in a given cluster (A, B, B1, B2, C1, C2), the amount of traffic to each of a first set of other clusters; and
-a second set of limitations defined to limit, for said given node in said given cluster, the amount of traffic from each of a second set of other clusters.
9. The method as claimed in claim 1, comprising the step of implementing cluster-based routing on at least two levels, including intra-cluster routing and inter-cluster routing.
10. The method as claimed in claim 9, wherein said step of allocating and managing resources comprises applying a cluster-based trunk model on the inter-cluster level; and
applying a hose model on the intra-cluster level; and wherein said step of implementing cluster-based routing comprises the steps of: applying shortest path routing on the inter-cluster level; and applying tree routing on the intra-cluster level.
11. The method as claimed in claim 1, wherein said step of partitioning a
number of said network nodes (1,2, 3, 4,5, 6, 7, 8, 9, 10) into clusters (A, B, Bl, B2,
C1, C2) comprises the step of defining said clusters based on at least one of:
- traffic distribution between nodes;
- subnet address planning;
- network topology;
minimization of the number of admission control parameters in the nodes; and maximization of bandwidth efficiency.
12. The method as claimed in claim 1, wherein an admission control unit
(220) exercises cluster-based admission control on at least two levels, including intra-
cluster admission control and inter-cluster admission control, based on the traffic
limitations in said cluster-based service-level definition.
13. A system for resource allocation and management in a communication
network having a set of network nodes (1,2, 3, 4,5, 6, 7, 8, 9, 10) for implementing the method claimed in claim 1, said system comprising:
-a cluster selection unit (122) for partitioning a number of said network nodes into clusters (A, B, Bl, B2, C1, C2), each cluster having at least two nodes;
-a service level definition unit (126; 214) for defining traffic limitations on at least two levels, including intra-cluster level and inter-cluster level, said traffic limitations including at least one node-to-cluster traffic limitation for inter-cluster traffic; and
-a dimensioning module (130; 220) for allocating and managing resources based on said traffic limitations.
|Indian Patent Application Number||4713/DELNP/2006|
|PG Journal Number||10/2012|
|Date of Filing||17-Aug-2006|
|Name of Patentee||TELEFONAKTIEBOLAGET L M ERICSSON (PUBL)|
|Applicant Address||SE-164 83 STOCKHOLM (SE)|
|PCT International Classification Number||H04L 12/56|
|PCT International Application Number||PCT/SE2004/001965|
|PCT International Filing date||2004-12-22|