INTELLIGENT CONNECTION MANAGEMENT
FIELD OF THE INVENTION
This invention relates to methods and apparatus for intelligent connection s management of connections in a network.
BACKGROUND TO THE INVENTION
Currently, control planes for telecommunication networks are being developed based on protocols derived from IP networking. The main control plane function that is of interest here is automated flexible connection provisioning, where setting up and tearing down connections becomes an automated task.
Within the control plane protocol suite, a routing protocol is used to identify the most suitable route for a connection request. A protocol such as Open Shortest Path First (OSPF) is being extended to provide this functionality. OSPF was originally developed as a dynamic routing protocol for the packet-switched IP network. In this protocol, each link between two nodes is assigned an integer weight; identifying the optimal route simply involves a shortest path calculation on the resulting graph. The connection is then automatically provisioned by the control plane using a signaling protocol such as RSVP-TE or CR-LDP.
In a distributed system, every node where connection requests arrive (edge nodes) has an up-to-date picture of at least part of the network, and will be able to run a routing algorithm, and initiate the provisioning of the connection. Such a distributed control mechanism is very suitable for a dynamic environment where all connections will only exist for a limited time. However, it poses some serious traffic engineering (TE) problems when applied to a more static environment, for example with a circuit-switched optical network where some connections will persist for a long time or with MPLS networks where MPLS tunnels are established for bunking. Firstly, the mechanism calculates the shortest path with respect to link weight for a single connection at a time, without taking into account other connections. The resulting placement can differ significantly from an optimal global solution for the network. Secondly, inaccuracies or partial network views in the distributed topology databases and to route connections can result in sub-optimal or erroneous path calculations. Furthermore, unlike in ... . ..
a ., . ' . - 2 connectionless networks, updating link weights will not affect existing connections that may remain on paths that may become far from optimal.
In both incremental and dynamic connection deployments, the limited predictability of new connection requests leads to sub-optimal deployment.
In existing networks, there comes a point when the existing deployment of connections can cause a loss of significant revenue as the distribution of consumed resources conflicts with the requirements of newly arriving connection requests.
OBJECT TO THE INVENTION
The invention seeks to provide methods and apparatus for intelligent connection management which mitigates at least one of the problems of known methods.
SUMMARY OF THE INVENTION
The invention proposes to add an extra mechanism to regulate a distributed network. On top of routing performed by an algorithm such as OSPF, a mechanism is added that will improve the global performance of the network.
This mechanism uses an optimization procedure to divert established connections from congested links to under-utilized links to achieve a better overall network performance thus leading to more bandwidth being available in the network, or more connections that can be provisioned in the network.
Additionally, or alternatively, the mechanism influences the deployment of new connections (for example by changing link weights used by the routing algorithm) to redress imbalances. The former procedure is fast but intrusive. The latter procedure is slow but unintrusive.
According to a first aspect of the invention there is provided a method of managing connections established across a telecommunication network comprising a plurality of nodes and a plurality of links between nodes, the method comprising the steps of:- categorizing connections into longerand shorter-lived categories; using a routing algorithm to determine routes for connections across the network, the routing algorithm using weights associated with the pluralityof links or nodes; and controlling the establishment of new connections or redeploying existing connections to balance utilization of said links or nodes by said longer-lived connections.
e ea. sa.
. 1 ca a a an a C J a ace cat Advantageously, the present invention enables more efficient use of network resources, lower costs and improved network performance and availability.
According to a second aspect of the invention there is provided apparatus for managing connections established across a telecommunication network s comprising a plurality of nodes and a plurality of links between nodes, the apparatus comprising:- means for categorising connections into longerand shorter-lived categories; a route calculator arranged to determine routes for connections across the network using a routing algorithm, the routing algorithm using weights associated with the plurality of links or nodes; and means for controlling the establishment of new connections or redeploying existing connections to balance utilization of said links or nodes by said longer-lived connections.
The method may be performed by software in machine readable form on a storage medium. This acknowledges that software can be a valuable, separately tradable commodity. It is intended to encompass software, which runs on or controls "dumb" or standard hardware, to carry out the desired functions, (and therefore the software essentially defines the functions of the register, and can therefore be termed a register, even before it is combined with its standard hardware). For similar reasons, it is also intended to encompass software which "describes" or defines the configuration of hardware, such as HDL (hardware description language) software, as is used for designing silicon chips, or for configuring universal programmable chips, to carry out desired functions.
The preferred features may be combined as appropriate, as would be apparent to a skilled person, and may be combined with any of the aspects of the invention.
BRIEF DESCRIPTION OF THE DRAWINGS
An embodiment of the invention will now be described with reference to the accompanying drawings, in which: Figure 1 is a schematic diagram showing the prior art subsumption principle; Figure 2 is a schematic diagram showing an embodiment of the present invention; : . '. : ear Figure 3 is a schematic diagram showing the ACM function of Figure 2; Figure 4 is a diagram showing how the intrusive and non-intrusive mechanisms of the present invention correlate with the existing routing algorithm.
DETAILED DESCRIPTION OF INVENTION
Embodiments of the present invention are described below by way of example only. These examples represent the best ways of putting the invention into practice that are currently known to the Applicant although they are not the only ways in which this could be achieved.
The present invention provides a mechanism to actively redeploy "live" connections. This requires an assessment of the utility versus the disruption as the effected connections may suffer a limited outage. Disruption is normally only caused with working path relocations but not for the protection paths - though there are consequences for "extra" traffic using these links.
Additionally, the present invention provides a mechanism to influence the deployment of new connections such as to redress any imbalance in connection deployment.
Connections may be characterized as "long" connections or "short' connections depending on the time for which they are likely to exist. Long and short connections may be treated in the same way, however, alternatively they may be considered separately due to the very different nature of the links and the effect that they have on the network.
The management of the connections may be done in a centralised manner either for the whole network or a part of the network (i.e. on a scale larger than a single link). This management is performed in an offline manner such that it does not affect the performance of the network.
The deployment of new connections is influenced using weights for the links.
These weights may be determined on the basis of a number of different criteria, including: cost, capacity available (or load), length (or delay) .
ë - e.
. . - 5 The utility assessment comprises assessing the benefits of the redeployment and comparing this to the disruption that would be caused by the actual redeployment process. This assessment may also take into consideration whether outage can be scheduled and disruption managed in a coordinated fashion to minimise the s overall network disruption.
This may be indicated in part of the connection request process, and may be measured or modelled. How connections are so characterized is outside the scope of the present invention.
An optimization procedure is preferred at specific intervals where ideally all long 0 lived connections are taken into account. The optimization procedure identifies the global optimal routing for all connections together. This implies a global parameter is optimized, for example the maximum fill or occupancy (as far as the long-lived connections are concerned) of any link in the network is minimized.
The mechanics of this can be achieved by rerouting the connections, which could mean provisioning the new route as a protection route or doing a forced protection switch from the current route to the new route and deleting the previously existing route. The existing route could always be used as a protection route if that is required.
In practice some constraints will be used in the optimization procedure. For example only a limited number of routes will be re-routed to minimize the risk of something going wrong in the rerouting procedure versus the benefit achieved.
This can be based on different approaches. One could for example identify a limited (fixed percentage for example) number of routes where rerouting will bring the most benefit. Another approach would be to apply a threshold, and re-route 2s only when a minimal improvement in the parameter that needs to be optimized will be achieved by re-placing the connection.
When more information is available this can be used - for example planned future upgrades to the network, known traffic behaviour, known future demands.
These can be taken into account in the optimization procedure to allow for better planning - for example by taking them as "existing" connections.
.. . . . . . : : . :' .. .e . . To achieve a more optimal routing for any connection the mechanism can review the weights for the links. It is for example desirable to have a more even distribution of connections, making it such that all links have a similar fill. It is shown elsewhere that for example applying link-weights inverse to the load of a s link can result in the desired more even load - making it possible to provide more connections.
These optimal weights can be calculated using a suitable optimization procedure.
Such a re-weighting of links can take place at regular intervals.
As part of the optimization of the network different weights can be used for long lived and short-lived connections at the moment of provisioning. This can be used to achieve different targets for the ratio of long-lived versus short-lived traffic on a link, depending for example on economic factors (for example when it is seen as more desirable to route the longlived traffic away from the busiest links).
1S These possible management architectures will now be described for implementing the invention. Note that the aim is not to add a new control plane but to add intelligence to better manage connection deployment.
Thus, existing control planes such as ASON/ASTN should be compatible.
However, the existing control plane needs to provide: a) Automatic Neighbour Discovery through a Neighbour Discovery Protocol and a Link Management Protocol; b) Topology Discovery through OSPF (with optical extensions for ASON/ASTN), IS-IS (with optical extensions for ASON/ASTN), Signalling for path establishment RSVP-TE, CR-LDP (with optical extensions for ASON/ASTN).
Possible Management Architectures include e ëe e eee e e e e e e e e e e ëe e e c e e ë e e e e ee e e e e e a) Centralized Network Management which is Suitable for small networks with static provisioning. High latency and poor robustness make it less desirable for dynamic provisioning in more complex networks.
b) Distributed Network Management which exhibits s i) High reliability (provision / routing decision is taken by each node - not a central control point ii) Control message flooding and transit latency can affect stability / performance due to inaccurate database information iii) Provisioning decision is made by each node without close coordination with others. This can result in sub-optimal deployment. Or
c) A hybrid solution in which layered management system provides fast acting distributed reactive layer coupled with a slower centralized strategic layer - arranged as a subsumption architecture to be described below. The hybrid solution will now be described in greater detail.
The Classical Subsumption Principle with reference to Figure 1, was described in an unrelated field in Brooks, R. A., "A Robust Layered Control System for A Mobile Robot", IEEE Journal of Robotics and Automation, April 1986. Its characteristics include: a) Lets a certain condition NOT produce a reaction directly, but only NOTIFY that the specific reaction should happen; b) Arbitration-task(s) decide according to the hierarchy of the notifications which of the reaction requests must be fulfilled; c) Every running task informs the arbiter of the reaction it requests. The arbiter checks all the requests and discerns the most important reaction, then activates the appropriate output control; and * * . . * . ë ::: : *:: . . . . * . - 8 d) The higher layer affects the lower layer through subsuming the input data and inhibiting the output data.
Embodiments of the present invention utilise the subsumption principle.
Figure 2 shows a schematic diagram of an embodiment of the invention. The abstract control model (ACM), which may be alternatively called the optimisation module performs the management process. This optimisation may be performed by a number of techniques, for example, Integer Linear Programming. The optimisation may be performed continuously or periodically depending on the requirements of the particular network. It is the ACM which performs the assessment of utility versus disruption described earlier.
The optional predictive mechanism may be used to predict future traffic loads on the network and these may be taken into consideration by the optimisation module (or ACM) in making its optimisation decisions. This has the benefit that the optimisation is done anticipating the future which reduces the likelihood that the optimisation will need to be done very frequently.
The ACM has two outputs, firstly it provides weight values (via path "Influence Path Calculation") to the elements in the network which perform the deployment (which may be a distributed function) using these weights. The regularity with which these weights are updated will depend on the degree of change within the network. Secondly it provides redeployment instructions to the elements in the node that can perform these redeployment operations.
It may be beneficial to have two sets of weights calculated by the ACM one for the short circuits and one for the long circuits. This may provide benefits as the two have significantly different effects on the loading of the network so optimising 2s them separately may lead to a better overall optimisation.
Failure of the slow predictive mechanism leads to progressive deterioration in performance - NOT catastrophic failure.
Higher layer control can anticipate changes based on prediction mechanisms and then adjust or inhibit the path calculation behaviour of the lower layer.
. .- . * - . . . : . e.: - 9 - It can be seen that the above approach subsumes the input by Influence Path Calculation (i.e. optimizes the network by changing OSPF weights) and inhibits the output using Intrusive Redeployment (i.e. optimizes the network by redeploying some existing long-lived connections).
s Figure 3 shows an example of the operation of the ACM. The optimization process may be performed on a number of different levels of complexity (two levels are shown by way of example only) and each level may operate in parallel but may operate at different speeds (e.g. more complex levels operating at a slower speed due to the increased complexity, therefore providing updates to the to lower levels less frequently than the lower levels).
The Centralized Higher Layer amends the inefficient deployment result using sophisticated offline optimization algorithms.
The Distributed Control Lower Layer provides reliable, real-time solution using simplified algorithms (e.g. CSPF).
The distributed database synchronization requirement restricts data to aggregated information for the distributed control layer.
With a focus on network optimization rather than real-time solutions, more detailed network information can be made available to the strategic higher layer.
Note that data injected into the inhibition point can be used to force the redeployment of a connection. It could also be used to alter the deployment of new connections that are expected to be long-lived.
In the above description, two types of traffic are considered: connections with long holding time / short holding time.
However, multiple traffic-related optimization variants exist. In one embodiment, assume all connections are short-lived when initial deployment is made. If connections exist beyond a certain time they are re-classified as long-lived and may be eligible for redeployment.
e.-. e ee e e e e ë e , e e e e ee. .e e 10 The redeployment assessment attempts to maximize the residual capacity of the network. This can be based on the current status or some measure of predicted traffic loading (i.e. via F-ARIMA: Fractional Auto-Regressive Moving Average).
Redeployment takes into account the degree of disruption that would arise and s the capabilities of the infrastructure.
Intrusive redeployment only affects connections with long holding time.
Redeployment is not needed for connections with short holding time.
In a more advanced embodiment, assume a method exists to classify traffic as either short-lived or long-lived at connection setup. This could be inferred or explicitly concluded from an SLA (Service Level Agreement).
Influence-based path calculation only applies to connections with short holding time. Connections with long holding time use a set of optimized static OSPF weights to minimize network resource consumption.
With reference to Figure 4, the goal of OSPF weight optimization is to make sure there is certain capacity C1 in each link.
The goal of intrusive redeployment is to make sure there is certain capacity C2 in each link.
Note that there may be a number of different sets of weights, e.g. one set for short connections and one set for long connections. Alternatively it may be beneficial to have different sets of weights based on other categories where the links have a specific effect on the network.
It may be important in the network to ensure that there is always some free capacity on each link in case of network problems.
It will be appreciated that the present invention provides mechanisms for: balancing loads, improving service levels, and/or improving failure resilience. ...
* . * - 11 The invention is relevant to any type of network, including but not limited to wireline, wireless and optical networks.
It will be understood that the above description of a preferred embodiment is given by way of example only and that various modifications may be made by s those skilled in the art without departing from the spirit and scope of the invention.
* .. .e * * * . . . .. . CC C . * *as e - 12