Note: Descriptions are shown in the official language in which they were submitted.
CA 02346182 2001-04-03
WO OO/Z27$8 1 PCT/AU99/00873 .
MANAGEMENT OF PATH SELECTION IN
A COMMUNICATIONS NETWORK
FIELD OF THE INVENTION
5 This invention relates to the management of connections in a large scale
heterogeneous communications network, such as those operated by
telecommunications utility companies and utilised by different carriers and
service
providers. In particular the invention relates to a method and apparatus for
selecting
paths in a broadband network that may be provided to customers requiring a
io communications service.
BACKGROUND TO THE INVENTION
The term "communications network" as used in the specification, is meant
to encompass networks suitable for voice telephony and for data
communications.
15 Such communications networks may be suitable for switching and transporting
voice, data, sound and/or image traffic, otherwise referred to as broadband or
"multimedia" communications.
Existing communications networks are characterised by a number of
transmission mediums using a variety of network technologies, protocols,
software
2o applications and equipment sourced from different vendors. Whilst much of
the
equipment includes management functions, such as monitoring, test and alarm
features; the centralising, handling and controlling of network management
functions in a complex multi-vendor environment is a significant problem.
A further problem in a heterogeneous network - which might include
25 customer access technologies (ADSL, HFC), core network technologies (ATM,
frame relay) and transmission technologies (SONET/SDH, WD1V1) - is that the
management of end-to-end connections is typically conducted according to a
lowest
common denominator philosophy. The services provided by the network are
limited to those able to be supported by the least capable equipment in the
network.
3o This philosophy is very ineffective in utilising the full capability of the
diverse
communications paths available in a network to meet particular service
requirements of customers.
CA 02346182 2001-04-03
WO 00/22788 . PCT/AU99/00873
2
Glo s
AAD: ATM access device
ADSL: advanced digital subscriber line
ATM: asynchronous transfer mode
5 CMIP: common management information protocol
CORBA: common object request broker architecture
EMS: element management system
HFC: hybrid fibre-optic co-axial
NMS: network management system
to NTU: network terminal unit
OSS: operational support system
VPC: virtual path connection
SDH: synchronous digital hierarchy
SNMP: simple network management protocol
15 SONET: synchronous optical network
TCP/1P: transmission control protocol / Internet
protocol
TL/l : Bellcore interface protocol for network
management
VCI: virtual circuit identifier
VPI: virtual path identifier
20 WDM: wave division multiplexing
OBJECT OF THE INVENTION
It is an object of the present invention to provide a connection manager for
selecting paths from a plurality of paths available in a communications
network to
25 route broadband traffic between predetermined locations in the network
which
ameliorates or overcomes at least some of the problems associated with the
prior
art.
It is another object of the invention to provide a path selection method for
use in a communications network contributing to cost effective use of path
features
3o for routing broadband traffic between predetermined locations in the
network.
Further objects will be evident from the following description.
CA 02346182 2001-04-03
WO 00/22788 PCT/AU99/00873
3
DISCLOSURE OF THE INVENTION
In a form, the invention resides in a connection manager for selecting paths
from a plurality of paths available from service providers in a communications
network to route broadband traffic in the network, wherein the connection
manager
5 includes:
(a) a connection model indicating functional features supported by each path
in
the network and locations of terminations for respective paths;
(b) a cost model associated with the connection model that exposes to clients
the cost of using the functional features for each path; and
1o (c) processing means, operated in response to a client requirement for a
connection with desired features between two locations in the network, to -
(i) identify, from the connection model in light of the desired features,
candidate paths for routing communications traffic between the two
locations and
15 (ii) determine, from the candidate paths and on the basis of cost exposed
by the cost model, an optimal selection of paths connecting said
locations.
Preferably the functional features indicated by the connection model include
one or more of the following:
20 (i) communications protocol;
(ii) transmission rate;
(iii) availability of the path; andlor
(iv) average error rate.
Preferably the cost exposed by the cost model reflects the resources required
25 to implement a path having a particular set of features.
The path cost may be determined in accordance with the service provider's
business rules or technical requirements, including one or more of
(i) number of network elements involved in the path;
(ii) reduction in network capacity experienced in implementing the path;
30 and/or
(iii) funds required to implement the path.
In one arrangement the cost model represents path cost as a data structure
which is interpreted by the processing means.
CA 02346182 2001-04-03 PCT/AU99/00873
Received 18 September 2000
4
Suitably the data structure comprises a graph of cost nodes wherein each
node specifies the cost of particular features or sets of features for
respective paths.
The cost nodes in the graph may be either internal for representing links
between internal terminations in the connection model or external for the
terminations at said predetermined locations.
In another arrangement the cost model represents path cost as code which is
executed by the processing means.
Suitably the processing means for executing the code is an implementation
of a Turing machine.
to If required the cost model further exposes to clients the delay in
implementing functional features supported by the path.
Where the cost model indicates implementation delay, the client requirement
for a connection may include a desired minimum delay.
Suitably, individual terminations at the same location that have common
attributes are represented as termination groups.
In another form the invention resides in a connection manager for selecting
paths from a plurality of paths available from seance promders m a
communications network to route broadband traffic in the network, wherein the
connection manager includes:
(a) a cost model provided by each service provider that exposes to clients the
cost of using functional features supported by each path; and
(b) processing means, operated in response to a client requirement for a
connection with desired features involving a plurality of terminations in the
network, to -
(i) identify, in light of the desired features, candidate paths for routing
communications traffic amongst said plurality of terminations and
(ii) determine, from the candidate paths and on the basis of cost exposed
by the cost model, a least cost selection of paths connecting said
terminations.
3o The cost model suitably also exposes to clients delay in the respective
service provider making a path available.
The available paths may include paths pre-existing in the network and/or
paths which can be created by the respective service provider.
nnn- . ,
~~~11~:1.:: -... ... . , m.::W
~i"e_:~.a.
CA 02346182 2001-04-03 PCT/AU99/00873
Received 18 September 2000
If required, the cost model suitably exposes usage cost depending on
functional features required of each path by making cost offers to the client,
which
cost offers are valid for a predetermined time.
Most suitably the cost model is transferred to the connection manager from
5 each service provider.
The service providers may include network managers for management of
network elements.
The connection manager may be installed in an environment wherein its
client is a superior connection manager and a superior cost model is
constructed
from an aggregate of cost models transferred by subordinate connection
managers.
In a further form, the invention resides in a selection method for selecting
paths from a plurality of paths available from service providers in a
communications network, to route broadband traffic in the network, said method
including the steps of:
(a) creating a connection model that indicates functional features supported
by
each path in the network and locations of terminations for respective paths;
(b) creating a cost model associated with the connection model that exposes to
clients the cost of using the functional features for each path; and
(c) processing a client requirement for a connection with desired features
2o between two locations in the network by -
(i) identifying, from the connection model in light of the desired
features, candidate paths for routing communications traffic between
the two locations and
(ii) determining, from the candidate paths and on the basis of the cost
exposed by the cost model, an optimal selection of paths connecting
said locations.
Suitably the step of creating the connection. model reflects attributes of
network elements deployed by the service provider.
In a yet further form the invention resides in a method of managing selection
of a path from a plurality of paths available fiom service providers in a
communications network to route broadband traffic in the network, said method
including the steps of:
., ,. .. . ;v~ 4 ~.
CA 02346182 2001-04-03
PCT/AU99/00873
Received 18 September 2000
6
(a) providing a cost model whereby each service provider exposes to clients
the cost of using functional features supported 'by each path in the network;
and
(b) processing a client requirement for a connection with desired features
involving a plurality of terminations by -
(i) identifying, in light of desired features, candidate paths for routing
communications traffic amongst said plurality of terminations, and
(ii) determining, from the candidate paths and on the basis of cost
exposed by the cost model, a least cost selection of paths connecting
1o said terminations.
The method of managing selection may be undertaken in an environment
wherein the client is a superior connection manager and a superior cost model
is
constructed from an aggregate of cost models transferred by subordinate
connection
managers.
BRIEF DETAILS OF THE DRAWINGS
To assist in understanding the invention preferred embodiments will now be
described with reference to the following figures in which:
FIG. 1 is a diagram of a heterogeneous communications network including a
hierarchy of connection managers;
2o FIG. 2A is a diagram illustrating the structure of a connection manager of
a
first embodiment;
FIG. 2B is a diagram illustrating interaction of a connection manager of a
further embodiment with service providers;
FIG. 3 is a diagram of a world view from the perspective of the abstract
connection model of the first embodiment;
FIG. 4 is an illustration of the physical architecture of an example network;
FIG. 5 is a top level view of a connection model for the network of FIG. 4;
FIG. 6A is a schematic diagram of an access device;
FIG. 6B is a cost graph for the access device of FIG. 6A;
3o FIG. 7A is a schematic diagram of a multiplexer;
FIG. 7B is a cost graph for the multiplexer of FIG. 7A;
FIG. 8A is a schematic diagram of an edge switch;
FIG. 8B is a cost graph of the edge switch of FIG. 8A;
-,~.',~.. .. .-.
F
CA 02346182 2001-04-03
WO 00/22788 PCT/AU99/00873
7
FIG. 9 is a cost graph of a core switch supporting local switching;
FIG. 10 is an alternative cost graph of the core switch of FIG. 9;
FIG. 11 is shows a proposed (cost-free) link between two cost graphs;
FIG. 12 is shows a link between the cost graphs of FIG. 11;
5 FIG. 13A shows a proposed link between two further cost graphs;
FIG. 13B shows an aggregated cost graph of the two further cost graphs;
FIG. 14 shows a aggregated cost graph for the core domain of the network
of FIG. 4;
FIG. 15 shows a cost graph used for modeling the network of FIG. 4;
to FIG. 16 shows the cost graph of FIG. 15 re-shaped to illustrate a preferred
path selection method;
FIG. 17 illustrates the principles of the path selection method; and
FIG. 18 illustrates the path selection method applied to the re-shaped cost
graph of FIG. 16.
15
DETAILED DESCRIPTION OF THE DRAWINGS
The embodiment of the invention is described in the environment of a
heterogeneous communications network 10 as illustrated in FIG. 1. The
connection
manager of the embodiment participates in the service activation and service
2o assurance processes of large communications networks. The connection
manager is
suited to use in relation to broadband communications products which have
significant complexity at the "Network Layer" (as defined by the ITU-T layered
management model) - such as ATM, SDH, IP and bundled broadband products.
The connection manager supports configuration and security activities at the
25 Network Layer and can cooperate with other systems performing these
functions for
subsets of the communications network. The connection manager of the
embodiment resides in a network management layer 30 between the service layer
20
and the network element layer 40.
The service layer 20 typically includes service order systems 21 which
3o institute the creation of new connections and facilitates the query,
modification and
deletion of existing connections and pre-sales systems 23 which support pre-
sales
activities including inquiries regarding available connection characteristics,
CA 02346182 2001-04-03
WO 00122788 PCT/AU99/00873
8
connection cost and time frame. Examples of service layer systems include
service
order, customer network management (CNM) or wholesale gateway.
The network element layer 40 typically includes the hardware for providing
network services such as switching or transmission, for example ADSLII~C
5 customer access technologies 41, ATM core network broadband technologies 42,
and transport technologies 43 such as SONET/SDH or WDM. The network
element hardware may be conceptually considered to reside in different
"domains"
and is typically also proprietary in nature. Accordingly, the network element
hardware generally uses proprietary or compatible network element managers
1o which act as proxies for many of the network elements.
Examples of network element managers are EMS systems 44 and 45 for the
ADSL/HFC hardware, the NMS 46 for the ATM core hardware and the vendor
specific NMS 47, 48 for the transport domain. Although the network element
managers manage many network elements, they expose each network element as an
15 individual entity. Thus in other embodiments, the connection manager may
interface directly to the network elements.
The network management layer 30 of the embodiment illustrates the
flexibility of the connection manager. A first connection manager 31 is
interfaced
to the EMS systems 44 and 45 for managing the customer access domain 40A. The
2o functional flexibility of the connection manager arises from its ability to
manage the
functionally different requirements of the switch matrix EMS 44 and the AAD
EMS
45. A second connection manager 32 manages the core domain 40C and a third
connection manager 33 is interfaced to the vendor NMS systems 47 and 48 in the
transport domain 40T. The transport domain illustrates the ability of the
connection
25 manager to handle disparate vendor equipment. The connection managers
include
interfaces which communicate using the CMIP, SNMP, TL/1 or proprietary
protocols as required. These interfaces may be adapted to suit particular
vendors'
equipment, current or future.
A fourth superior connection manager 34 is interfaced with the three domain
3o connection managers 31, 32 and 33 for the purpose of cross-domain
connection
management. The superior or cross-domain manager 34 level accepts end-to-end
connection instructions for the entire network, it determines which paths
through
the underlying networks are available and issues connection instructions to
the
CA 02346182 2001-04-03
WO 00/22788 PCT/AU99/00873
9
domain connection managers as appropriate. The connection task is thus
delegated
to the appropriate domain connection managers.
Although shown as four separate managers, the network management layer
30 may be viewed as undertaking the overall connection management function for
the network, with the cross-domain connection and domain connection being
managed at different levels. Thus the network wide connection requirement is
simplified step by step so that each level of connection management can be
optimised to manage the portions of the network under its control. However,
the
separate connection managers illustrate the distributed nature of a network
wide
1o connection manager 35 which may be geographically distributed across a
large
number of sites and network operations centres.
Network Models
The connection manager provides flexible network modeling tools for
representing a service provider or network owner's view of broadband
connections.
The key concepts for these representations are:
(i) "paths" which represent the network owner's view of a connection having
the ability to transmit data over a communications network, such as ATM
PVC;
(ii) "terminations" where the path is manifest outside of a network, such as
an
2o ATM VPI, VCI and cable, or a customer NTU; and
(iii) "features" which are the external selectable characteristics of the path
visible
at its terminations, such as quality of service, bit rate or path diversity.
Conceptually a path can negotiate many network elements and protocols, such as
end-to-end SDH connections implemented using SDH switches and WDM
transmission.
Connection Manager Structure
The structure of a generic connection manager 35 of one embodiment is
described in relation to FIG. 2A, as it might be deployed in relation to a
particular
network. A connection model 36 is used to expose to clients the network and
its
3o services, which model may be implemented by the core software 37 for
execution
by a processor (not shown) or a series of distribute processors. Network
adapters
38 are provided to interface with network elements, EMS or other NMS; whilst
service adaptors 39 are provided to interface to existing service OSS.
CA 02346182 2001-04-03
WO 00/22788 PCT/AU99/00873
10
The connection manager 35 supports several fundamental operations
relating to the life cycle of a path. The service provider or network owner
may
instruct that a path be reserved, created or changed, which results in the
automatic
selection, allocation and configuration of appropriate network equipment to
5 implement a connection with the specified features between specified
terminations.
A remove operation frees the allocated network equipment.
The connection manager allows the determination of which features are
supported, in what combinations and at what localities in the network.
Terminations
and paths may be searched and listed, and the termination which best supports
a
to given set of features in a locality suggested to a client by the connection
manager.
The connection manager 3 5 of the embodiment preferably uses a COR.BA
IIOP architecture to interface to both the service layer and the network
layer. The
service layer interface and the network model can be adapted to present some
standard data models, such as ETSI 600-653 or ATM Forum M4, or adapted to
15 existing service layer interfaces. All connection manager objects can be
annotated
with the names and identifiers required by external systems, for example
customer
circuit identifiers.
The connection manager is a high-availability system supporting on-line
changes to configuration with back-out, on-line database backup, replicated
2o databases and redundant hardware. Depending on configuration, the
connection
manager will support 10,000 transactions per hour on one mid-range server
machine
(for example Hewlett Packard J-class). This typically corresponds to a network
with 50 million installed paths with a typical operational latency is 0.3
seconds.
One connection manager installation can be distributed, as indicated above,
25 over a number of server machines. A distributed installation on up to 10
machines
would be typical, as transaction processing scales approximately linearly over
this
range. Such installation can suitably support HP UX or Solaris on SUN Solaris,
Microsoft's NT on Intel or PA-RISC operating systems. Oracles database and
OrbixTM ORB are also used in the preferred embodiment.
3o FIG. 3 shows a view of the world from the perspective of a connection
model, considered in the abstract. A connection model is a framework for
describing communications systems involving connections. In particular, the
abstract connection model 50 of the embodiment is a distributed, object
oriented
CA 02346182 2001-04-03
WO 00/227$8 PCT/AU99/00$73
11
way of representing the state and operations required to manage the network
layer
30 of a broadband communications network. The service layer 20 is effectively
the
driver for the connection model in that providing function to the service
layer is the
role of the connection model.
5 In order to address requests from the service layer the connection model
delegates to either the network element layer 40 - in the form of either
network
elements 53 or network element managers 54 or other providers at the network
management layer - for example workflow managers 51, network managers 52,
other connection managers 55 or network service providers {NSP) 56. The
choices
io involved in performing delegation include: (a) to which subordinates are
functions
delegated? (b) how are super-functions mapped to subordinates? (c) what is the
sequencing of subordinate operations? and (d) what actions occur when a
subordinate operation fails?
The abstract connection model 50 is suitably instantiated for operational use,
15 with the instantiation depending on:
(i) the particular networking technology employed by the network
owner;
(ii) the network owner's engineering rules; and
(iii) the network owner's service level requirements.
2o It is the model's instantiation 36 that gives meaning to the components of
the
model, such as path, feature and termination. When a connection model is
instantiated, each of the abstract concepts that it presents will have a
precise
meaning. Furthermore, a model instantiation will have objects instantiated
against
it which objects will conform to both the abstract connection model and the
25 instantiated model.
The development of a connection manager application normally includes the
following three stages:
~ Network analysis and design - the focus of this stage is to define the
architecture of the network to be managed and to analyse the characteristics
of
3o each component of the network.
~ Connection manager installation - the focus of this stage is to use the
mechanisms supported by the core software to specify how the network should
be managed. The installation is the outcome of this stage.
CA 02346182 2001-04-03
WO 00/22788 PCT/AU99/00873
12
~ Run time - once a connection management system is installed, paths can be
created through the network to provide communications services.
Basic Concepts
The basic concepts for connection management used by the connection
model are the path-termination-feature concepts, as introduced briefly above.
A
feature is a characteristic of a path that is required by a client or
customer, and is
manifest to the client of the path. Typical features include data transfer
protocol,
bandwidth, reliability and error rate; for example: ATM protocol, 64kb/s data
rate
and unavailability for less than 1 minute/year. Characteristics of paths such
as
1o routing via a particular network element, or implementation using a
particular
technology are not features, because the client cannot detect those
characteristics.
Features may apply to particular terminations of a path or installed on
connections,
which often requires feature values. The feature Maximum Bit Rate has a value
specifying what the maximum bit rate is, for example Maximum Bit Rate = 256
kb/s. A feature with values applied to a connection is referred to as an
installed
feature.
A path is provided by a network and is fully characterised by the installed
features of the path (the path features), a set of terminations exposed to the
client
and a set of installed features for each termination (the termination
features). A path
may be permanent, that is the ability to transmit exists at all times after
the path is
established by a connection manager, until it is torn down by the connection
manager. A path may be switched, in which case there are two phases,
'configuration' and 'signalling'. The signalling phase initiates and finalises
the
ability to transfer data. Signalling emanates from network equipment connected
to
the path. The configuration phase is performed by a connection manager and
establishes the bounds of data transfer that can be requested by signalling.
For
example, configuration may allow data transfer anywhere within a national
network, with speed up to 20Mb/s. This would prevent signalling requesting an
international transfer, or a 100Mb/s transfer.
3o A path typically has two terminations, but may have one or many.
Examples of paths are ATM PVCs and SVCs, SDH connections, or customer access
networks (ie. local loop). The term path as used herein includes the ITU-T
concepts
CA 02346182 2001-04-03
WO 00/22788 PCT/AU99/00873
13
of connection and trail, as well as further concepts such as Switched Virtual
Connection.
A network represents the ability to manage paths and is used to create new
paths and list existing paths. Paths are always totally contained within
exactly one
5 network. A network may be conceptualised as a factory of paths, and a
collection
of the paths that it has created. In is also a collection of the terminations
at which
the paths will or could be manifest. Example networks include an ATM switch, a
Main Distribution Frame, a SONET ring, a ATM domain manager, a regional SDH
network manager. The term 'network' includes the ITU-T concepts of network,
to sub-network and network element.
A network is typically implemented by calling on the services of other
networks, termed sub-networks. For example, an ATM network may use the
services of a DSL and Core ATM network. The term 'sub-network' may imply a
client-server relationship between the network and the sub-network. Generally,
15 there is nothing inherent in a network that makes it a sub-network. All sub-
networks are fully fledged networks in their own right. Therefore all the
properties
and functions of networks are also properties and functions of sub-networks
A termination is where a path is, or may be, manifest to the client of a
network. A termination can also include a grouping of terminations. A
termination
2o grouping may or may not be capable of establishing paths. Example
terminations
may be an physical port, an ATM VPI on a physical port, or a cable pair at a
customer's premises. The term 'termination', includes the ITU-T concepts of
trail
termination point, connection termination point and access group. A
termination can
participate in a finite number of paths, typically one, but potentially more.
25 A path in a network will have one or more (usually two) terminations.
Single termination paths may represent loop-back and multiple terminations may
represent multiple drop (for example CSMA) or a closed user group (for example
a
voice private network). Paths may share terminations, this may express a multi-
serving capability (such as the set of customers using a billing server).
3o Connection Manager
The connection manager 35, as depicted in FIG 2A, presents an architecture
for assembling a working network management system. The core software 37
provides, in one embodiment, connection model abstractions that can be
configured
CA 02346182 2001-04-03
WO 00/22788 PCT/AU99/00873
14
to reflect the characteristics of the particular network equipment deployed by
the
network owner. The operative connection model 36, once configured, will
substantially reflect the business and engineering policies of the network
owner, in
other words the knowledge that a human operator would apply if they were
5 performing the connection manager functions manually. The core software 37
assumes that the interface to the network supports the connection model 36,
preferably expressed in CORBA.
The network adaptors 38 are developed, typically using stack products, such
as those provided by Vertel or Hewlett-Packard, in order to provide simple
to interfaces into complex protocols such as CMIS or TL/1. The service
adaptors 39
provide an interface between the network's service management layer OSS.
Existing operation support systems generally have a proprietary interface,
although
there are some emerging standards including the US Federal Communications
Commission's "Gateway". Printed paper or a character terminal are common
15 interfaces. The deployed connection manager 35 preferably has an adaptor to
automate the interface between the service management layer 20 and the core
software 37.
Distributed Object Model
As the connection manager is a network layer manager, it is only concerned
2o with modeling network-level concepts. The first network level concept is
"connection". The connection model 36 of the embodiment is a distributed
object
model, preferably expressed in CORBA interface definition language (>I?L). In
accordance with the concepts introduced earlier, there are three types of
objects in
the model, namely:
25 (i) path objects that represent connections;
(ii) termination objects that represent where the connections are
physically manifest; and
(iii) network objects which are the fabric that can create connections.
Network Objects
3o The network object is a container of path objects and termination objects.
Network objects form a hierarchy, where some network objects are superior to
others. Network objects will typically form a strict containment hierarchy,
though
the connection manager allows any non-cyclic structure. Network objects can
CA 02346182 2001-04-03
WO 00/22788 PCT/AU99/00873
15
represent: individual network element instances, groups of network elements
organised by some owner determined criteria, such as geographic domains or
functional domains; sub-networks that are managed by some other NMS, such as a
vendor NMS; cross-domain networks that aggregate several domain network
5 objects, such as those identified 40A, 40C and 40T in FIG. 1.
Network objects support the following operations: listing the capabilities of
the network object; listing the characteristics of the paths that the network
objects
can create; creating paths having specified terminations and features;
previewing
path creation; searching for paths, terminations and sub-networks having
specified
to characteristics. Network objects may be configured as follows: assigning
identity,
description, meaning; defining the relationships between the network objects
(for
example, a containment tree structure); defining the connections between
subordinate network objects; and the characteristics of the paths they can
create.
Path Obiects
15 Path objects represent the connections formed by network objects. They
correspond to some real-world connection concept. This could be for example:
(i) a physical connection, such as a bearer distribution frame;
(ii) a switched connection, such as an ATM virtual circuit; or
(iii) some abstract relationship, such as the relationship between a
2o customer and their Internet service provider (ISP).
A path object is always contained within one network object. When network
objects form a hierarchy, a network object may implement that path by
delegating
portions of the implementation to sub-paths in its subordinate networks. Paths
are
characterised by terminations and features. Terminations describe where the
path is
25 manifest, features describe externally visible characteristics. A path
generally has
two terminations.
A feature has a name and optionally a value. Features are applied to either
the path itself, or terminations on the path. This permits termination-
specific
features to be modelled - as required for asymmetrical paths.
30 Paths support life-cycle type operations. This allows for several levels of
completeness of the path's implementation. The typical levels of
implementation of
paths are:
CA 02346182 2001-04-03
WO 00/22788 PCT/AU99/00873
16
(a) design - the path consumes no resources, other than those minimally
needed to record its characteristics;
(b) reserve - the path is fully implemented, except the last step which
would enable service;
5 (c) installed - the path is implemented into the equipment to enable
service; and
{d) deleted - the path no longer exists, but the memory of it is kept for
audit purposes.
Paths have a cost, which represents the amount of resource required to
implement
to the path. The cost allows a client to rationally choose between several
candidate
paths, each of which is capable of supporting their needs. Path objects
support the
following operations: deletion; changing the features, terminations or
implementation completeness; preview operations for the above; and listing the
path
attributes.
15 Termination Objects
Termination objects represent where path objects are (or may be) manifest.
They correspond to some real-world concept for example: a physical
termination,
such as a cable; one channel multiplexed over some bearer such as an ATM
virtual
circuit or SDH container; a grouping of multiplexed channels, such as an ATM
2o virtual path. A termination object within one network object. A network may
express an effectively infinite number of terminations, for example an ATM
network may model each VPI/VCI as a termination. Even coarser grained
modelling than the ATM example will have large numbers of terminations.
Termination objects support the following operations: describe the
25 termination; find the lowest cost free termination capable of supporting a
particular
set of features.
Conceits of Cost
When the core software is implementing a path, or changing an existing
path, it may have several alternate methods. Each alternate will require a
certain
3o amount of the network owner's or service provider's equipment resource. For
example, bandwidth on a optical fibre, dedicated use of a port card, or share
of
switch capacity. The core suitably implements a path using the alternative
that
requires the least resource. To allow the connection manager to determine
least
CA 02346182 2001-04-03
WO 00/x2788 PCT/AU99/00873
17
resource, the core software uses the concept of "cost". Each candidate path
has a
cost and each candidate termination has a cost. The connection manager
suitably
makes the simple choice of 'least cost'. The power comes from the meaning
assigned to, and the method of calculating the cost.
5 Network objects close to the service layer typically have a huge number of
candidate paths. One approach that such an object could use, is to execute the
preview-path-creation operation on for each of the candidate paths, then
choose the
one that has the lowest overall cost. This direct approach is practically
infeasible
when, as is typical, there are mufti-millions of candidate paths. To bypass
this
to practical difficulty, the connection manager implements the concept of cost
modelling. A cost model is a way for a network's client to efficiently predict
the
cost of paths. This allows the client to check the millions of options,
without doing
millions of requests.
Cost Model
15 A cost model preferably predicts the cost of paths based on termination
groups, rather than individual terminations. It supports feature-dependent
costs.
Cost models may be arbitrarily complex and precise. For example, a highly
precise
model would specify the cost for paths between each termination group pair. A
coarse model would specify a single cost for all paths. Intermediate models
that
2o exhibit a arbitrary mixture of termination dependent cost and fixed cost
may also be
supported.
A cost offer is a named cost model that applies for a specified period of
time.
A cost offer is the mechanism by which a network exposes the cost model for
its
paths. As a cost offer includes a validity time, clients can restrict the
number of
25 enquiries for cost model that they make. The present embodiment of the
connection
manager supports validity times from the order of seconds upwards - shorter
times
need higher computing resource.
FIG 2B is a representation of a connection manager 60 of a further
embodiment showing the interaction with service providers 61, 62 in response
to a
3o requirement issued by a client 63 for a connection in a communications
network.
Each service provider has a plurality of paths 64, 65 available in the
communications network. The connection manager 60 includes a connection model
66, 67 which indicates functional features supported by each path, along with
CA 02346182 2001-04-03
WO 00/22788 PCT/AU99/00873
18
locations of terminations for the paths in respective sub-networks. The
connection
manager 60 further includes a cost model 68 that is associated with the
connection
model and exposes the cost of using the functional features to the client 63.
In a
preferred arrangement the cost model is transferred 71, 72 from a service
provider
5 into the connection manager 60. The connection manager processing means 69,
operates in response to the client requirement to first identify from the
connection
model 66, 67 candidate paths relevant to the specified locations and, secondly
to
determine on the basis of cost exposed by the cost model 68 an optimal
selection
from the candidate paths, which suitably meet a 'least cost' criterion.
Further
1o details about a preferred cost model, explained with reference to a network
fragment, follow.
There are two options available for determining costs for a network object,
namely:
(i) fixed cost - where a configured cost is returned; and
15 (ii) mapped cost - where a value for cost is returned that is derived
from the costs of its subordinate networks.
The mapped cost option converts the units of cost and features in each
subordinate
network into the units of cost and features for the present network.
The mapped cost offer is a particularly powerful mechanism, as it allows a
2o network to express a very precise and up-to-date cost model (that is, one
that
reflects details of its subordinate networks) for zero operator cost. In
general,
mapped cost is a very effective way to transferring rational decision making
capability from subordinate networks to superior networks. This is necessary
because the subordinate networks, close to the equipment, understand the
25 equipment-related intricacies, while the superior networks, close to the
service
layer, have a sufficiently broad view to perform network-wide optimum resource
allocation.
The cost model 68 of the embodiment, which uses a data structure in the
form of a traversable graph of cost nodes, includes three major aspects. Each
aspect
3o is designed to solve cost-related problems in the different stages of the
management
application development. The aspects of a preferred modelling process are:
CA 02346182 2001-04-03
WO 00/Z2788 PCT/AU99/00873
19
~ Cost graph creation - a cost graph notation is defined. This notation can be
used during the design stage to assist system integrators and network
engineers to analyse the cost model at different network levels.
~ Cost model specification - during specification stage, the core software can
5 be used to translate the cost graph representation of the network cost model
to the format that can be loaded into a connection manager system.
~ Route selection algorithm - based on the internal representation of the cost
model, the route selection algorithm and the cost-based routing algorithm
are used for path creation.
to Here the term route means a set of sub-paths that together implement a path
between terminations at two selected locations in the network.
Cost Graph
A cost graph is a graphical representation of a cast model. In some cases, a
cost
model can be represented by a single cost graph; in some other cases, a number
of
15 disconnected cost graphs are needed to represent a single cost model. In
order to
understand the cost model and how it may be used to assist the selection of a
path
route, an example network is used. The physical architecture of the example
network is illustrated in FIG.4.
The physical network contains a number of access devices, such as
2o multiplexers, marked as Al to A4; a number of edge switches marked as E1 to
E3
and two core switches, C1 and C2. These physical components form two logic
groups: an access domain, which provides the customer access front end to the
network, and a core domain, which provides the communication back bone of the
network. Each access device has a number of customer termination points, such
as
25 A to H, and is linked to an edge switch. An access device cannot switch,
that is, no
path can be created between two terminations connected to the same access
device
without going out to an edge switch. In the above example network, all
possible
paths contain one of the following sub-paths: A;-E~-Ak, A;-E~-Ek-Ai", A; E~-Ck-
EI-
Am, A;-E~-Ck-Cl-Em-A". (i, j, k, l, m, n = 1 to 4). Using the connection model
3o discussed earlier, the network can be modelled as a cross-domain network
containing two domain sub-networks, an access domain sub-network and a core
domain sub-network. Each sub-network contains a number of items of equipment
as
CA 02346182 2001-04-03
WO 00/22788 PCTlAU99/00873
20
its sub-networks. A view of the connection model for the network is
illustrated in
FIG. 5, and it will be appreciated that this network could itself be a sub-
network of
the larger network illustrated in FIG. 1.
The cost model of each network can be represented wing a cost graph or a
5 set of cost graphs. A cost graph contains the following three basic
elements, as
follows:
"Cost node" - the basic element in a cost graph. Each cost node has a name
and the following information associated with the cost node:
~ a set of features this cost node supports, derived from the connection
model;
to ~ the cost of using these features; and
~ the delay in implementing these features.
"Termination" - a special node in the cost graph indicating the potential
starting and ending point of a path. It could be a single termination,
although
15 typically it is a termination group.
"Edge" - a line between a termination point and a cost node or between two
cost nodes.
An important aspect of constructing a cost graph is to identify a set of cost
nodes for the network. Potentially, any network resource or abstract of such
2o resource can be a cost node. Example network resources include network
equipment, connections, sub-networks, and even the network itself. Manually
building a cost graph to represent a cost model of an entire network is a
complex
task. Therefore the connection manager allows the cost model of a network to
be an
aggregation of the cost models of the sub-networks. Hence, the cost model of a
25 network can be composed from a set of cost models of sub-networks or even a
cost
model of a group of network equipment, with negligible configuration ei~ort.
In the
example network shown in FIG. 4, a simple cost model can be constructed for
each
piece of network equipment, such as access devices and switches.
FIG. 6 shows the multiplexer Al and its corresponding cost graph. On the
3o customer side of A1, there two termination points, A and B. Both A and B
can be
grouped as a termination group. The access device does not support local
switching, so there are is no direct connection between A and B. On the
network
CA 02346182 2001-04-03
WO 00/22788 PCT/AU99/00873
21 _
side, A1 has a termination a connected to an edge switch in the core domain.
Multiplexer A1 can be modeled as a single cost node with two terminations, TGl
(termination group 1 containing terminations A and B) and a. Turning to
consider a
mulitplexer with reference to FIG. 7. In general, an m-to-n multiplexer has
one
5 customer side containing m terminations and one core side containing n
terminations. The terminations on each side can be grouped into one group.
Such a
multiplexer can be represented as a single cost node with two termination
groups as
shown in FIG. 7B.
The cost model for an edge switch and a core switch is similar to the one for
to an access device, except that both the edge switch and the core switch
support local
switching. That is a path can be created from one termination point to itself
(it may
in fact go through different virtual channels or virtual paths). In the case
of an edge
switch E 1 as shown in FIG. 8A, paths m-E 1-m, n-E 1-n, m-E 1-n, m-E 1-q and n-
E 1-
q can be created. To represent this, double edges to the same termination
should be
15 used. The cost graph of the edge switch E1 can be represented as shown in
FIG. 8B.
Because the physical capabilities of a core switch are similar to that of the
edge switch E1, the cost model of a core switch should be similar to the cost
model
of the edge switch E1. For example, core switch CI is capable of performing
local
switching. To represent this, duplicated terminations should be used as shown
in
2o FIG. 9. However, a business rule may specify that based on the network
architecture
given in Figure 1, the local switching capability supported by core switches
does
not add any value to the path creation, and hence should be ignored during
cost
modelling. For example, because edge switch El supports local switching, a
path
A1-El-A2 can be created. This basically eliminates the requirement of having a
25 path Al-E1-C1-E1-Al. To enforce this business rule, the cost model of core
switch
C1 should really be modelled shown in FIG. 10. This is an example of how, in
the
cost model, a business rule can override physical capability in the network.
Cost Model A.g~regation
Generally a physical network contains a number of sub-networks and for
3o mapped cost models, the connection manager performs the aggregation. In
some
embodiments, the cost model may be partially mapped as required. If each sub-
network's cost model contains only a single cost graph and a link between a
CA 02346182 2001-04-03
WO 00/22788 PCT/AU99/00873
22
termination of a cost graph to another termination of another cost graph is
specified
by a system integrator, then connection manager does the aggregation by
replacing
the terminations and associated edges with a single edge. For example, if a
link is
specified between the termination q of cost graph E1 and the termination r of
cost
5 graph C1, as shown in FIG. I1. The terminations involved in the link q and r
become internal terminations (sometimes also referred to as intermediate
terminations) of the current network. These terminations will be required by
the
creation of sub-paths during routing.
If the connections between different sub-networks bear significant cost, then
to a cost can be specified for the links. In the above example, if the
connection
between E1 and CI bears a cost, a new cost node CN L1 is introduced when
aggregating these two cost models, as shown in FIG. 12. If a link involves
duplicated terminations (e.g. in the case of support local switching), then
the other
cost graph (the one without duplicated terminations) should be duplicated and
each
15 linked to one of the duplicated terminations. For example, a link between
termination a of cost graph for A1 (see Figure 6B) and termination m in cost
graph
for E1 (see Figure 8B) will lead to the aggregated cost graph illustrated by
FIG. 13.
Applying these aggregation techniques to all cost models in the core
domain, the domain cost model shown in FIG. 14 can be obtained. Whilst FIG. 15
2o illustrates the cost model for the network obtained, after accounting for
duplicated
terminations, for the cross domain corresponding to the physical network shown
in
FIG. 4.
Cost Based Route Selection
The method for route selection involves creating an aggregate cost graph of
25 the relevant sub-networks, as described above, and keeping a record of
which sub-
network is responsible for each cost node. The second part of the method
involves
finding the lowest-cost of path through the cost nodes between terminations
available at the desired locations. A system for allowing exclusion of certain
types
of sub-networks may, in some cases, be used to "filter" the cost model prior
to
3o using the route selection method of the embodiment.
A routing method which may be used to select a route with the lowest cost
will now be described. During the selection process, the feature set
associated with
each cost node provides another level of filtering. If the required features
are not
CA 02346182 2001-04-03
WO 00/22788 PCT/AU99/00873
23
supported by a sub-network, then any paths involving that sub-network are not
selected. In the following discussion, in order to describe the routing method
clearly, a cost graph is re-shaped according to the starting location (or
termination
group) specified in a path creation request. For example, to create a cross
domain
5 path from termination point E to H as indicated in Figure 4, the cross
domain cost
graph in FIG. 15 can be re-shaped as a tree structure with the starting
termination
group as the root, and the ending termination group and other terminations as
the
leaves. The re-shaped cost graph is shown in FIG. 16. Such shaped cost graph
shows all the possible routes starting with the given termination. If multiple
routes
to from the starting termination to the ending termination exist, then the
ending
termination will appear more than once.
The diagram in FIG. 17 illustrates one form of the path selection method.
Starting from C1, which is the cost node directly linked to the starting
termination
A, a first wave is generated. The wave contains all the cost nodes that
support the
15 required feature and are directly connected to C 1. Three cost nodes
involved in the
frontage of the first wave are C2, C3 and C4. From the starting termination A
to
each frontage cost node forms a candidate route. By adding the current sub-
total
cost of each candidate route, a lowest-cost candidate route (from A to C2) is
selected. Progress will only be made with the currently selected route by
pushing
2o the wave one step further to form a second wave. The frontage cost nodes of
the
second wave include two groups:
~ all frontage cost nodes of the unselected routes in the last wave, e.g. C3
and C4; and
~ all cost nodes directly connected to the selected cost node in last wave,
25 e.g. CS and C6.
Here it is assumed that both C3 and C4 support the required feature.
The above process can be repeated until the paths from A to B with the
lowest cost are selected. In the example the selected route is A-C1-C2-C6-C10-
H.
The cost of the selected route is 7, which cost is lower than the current sub-
total of
3o any other single candidate route. Applying the method for route selection
from E to
H in FIG. 16, a route from E-CN_A3-CN E2- CN E3-CN A4-H will be selected
as follows with reference to FIG. 18. Apart from the feature parameter, that
may
CA 02346182 2001-04-03
WO 00/22788 PCT/AU99/00873
24
affect the route selection, another parameter "delay" may also affect the
selection
of a route. The routing algorithm can also be optionally arranged to reject
paths
having delays greater than a required maximum delay.
Once a route is selected using the cost model, it provides a reference of how
5 the required connection can be created in the physical network. If the
selected route
only involves one sub-network the connection can be created over the sub-
network.
If the route involves more than one sub-network, then a number of paths need
to be
created over the relevant sub-networks. In order to make the necessary
connections,
the current network must find the intermediate terminations at the boundary of
each
to sub-network. These terminations are those used to form links, as discussed
above in
relation to FIG. 11.
It will be appreciated that implementations of the cost model, other than a
selection method that uses static data in nodes on a traversible graph as
described
above in relation to the preferred embodiment, are possible. In general terms,
the
15 selection method of the embodiment is one implementation of a cost model
wherein
a delegate offers a data structure that is capable of representing complex or
subtle
cost predictions when interpreted by a method pre-agreed by the delegate and
delegator. Though such data structures are complex, they are not general
purpose,
in the sense of being Turing machines. This means that there will always be
some
2o cost predicates that cannot be conveniently represented in the model.
An alternate approach is to pass a piece of data that is the program for a
Turing machine. The delegator and delegate must still agree of the semantic of
the
data (that is, the implementation of the Turing machine). However there will
no
longer be intrinsic limitations of the ability to represent any cost model.
For
25 example, it is unlikely that a data structure approach could model a cost
prediction
that involves the calculation of B-spline interpolation (unless the data
structure
designer foresaw that need). The Turing machine approach does not suffer such
a
limitation. A practical implementation of the Turing machine approach is to
agree
on an implementation that is well understood in the industry. One such example
is
3o to use a JavaTM Virtual Machine implementation, and the cost model is then
transferred as a sequence of Java byte codes.
The cost model allows the connection manager to expose or publish a
comprehensive estimate of what a path between two locations will cost, without
the
CA 02346182 2001-04-03
WO 00/22788 PCT/AU99/00873
25
client having to make a vast number of queries about the cost of each possible
choice. It is the service provider's or network owner's choice as to how
comprehensive a cost model is provided. They may publish a detailed cost model
without exposing the underlying structure of the network.
5 By automating the routing and configuration of connections across complex
networks, the connection manager substantially reduces the need for manual
management at the network and element levels. Connections can be provisioned
in
real time and the connection manager will scale to process increasing volumes
of
new connections as broadband communications networks grow.
10 The object oriented approach to modeling aspects of the network in the
connection manager, wherein the abstract connection model is differentiated
from
the connection model instantiations result in a high degree of reuse of
clients and
servers. This approach also allows for, but does not enforce, very flexible
client
and server implementations, which can match a rapidly changing business
scenario.
15 Throughout the specification the aim has been to describe the preferred
embodiments of the invention without limiting the invention to any one
embodiment or specific collection of features.
