United States Patent (19)
`Holender et al.
`
`54 METHOD AND DEVICE FOR
`PARTITIONING PHYSICAL NETWORK
`RESOURCES
`
`75 Inventors: Wlodek Holender, deceased, late of
`Lund, Sweden, by Kerstin Korning,
`legal representative; Tamas Henk,
`Budapest, Hungary; Soren Blaabjerg,
`Allerod, Denmark; Andras Faragó,
`Budapest, Hungary; Bengt Stavenow,
`Lund, Sweden
`73 Assignee: Telefonaktiebolget LM Ericsson,
`Stockholm, Sweden
`21 Appl. No.:
`08/765,159
`22 PCT Filed:
`Jun. 12, 1995
`86 PCT No.:
`PCT/SE95/00703
`S371 Date:
`Apr. 29, 1997
`S 102(e) Date: Apr. 29, 1997
`87 PCT Pub. No.: WO95/34973
`PCT Pub. Date: Dec. 21, 1995
`Foreign Application Priority Data
`30
`Jun. 13, 1994 SE Sweden .................................. 94O2O59
`(51) Int. Cl. ............................................... H04L 12/24
`52 U.S. Cl. .......................... 370/235; 370/252; 370/254;
`370/396; 709/221
`58 Field of Search ..................................... 370/225, 228,
`370/229, 235, 237, 238, 254, 255, 351,
`389, 395,396, 400, 401, 409,904, 905,
`252, 522, 524, 397, 465; 340/825.03, 826,
`827; 379/219–221, 271-273; 706/10, 14,
`15, 19, 27; 709/201, 220, 221, 232, 234,
`235, 238, 239, 241
`
`56)
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`USOO6104699A
`Patent Number:
`11
`(45) Date of Patent:
`
`6,104,699
`Aug. 15, 2000
`
`
`
`4,713,806 12/1987 Oberlander et al. .................... 370/358
`5,289.303 2/1994 Cloonan et al. ........................ 359/139
`5,297,137 3/1994 Ofek et al. .............................. 370/403
`5,345,444 9/1994 Cloonan et al. ........................ 370/381
`5,381,404 1/1995 Sugano et al. .......................... 370/238
`5,687,292 11/1997 Boda et al. ............................... 395/11
`5,764,740 6/1998 Holender ................................. 379/112
`5,872,918 2/1999 Malomsoky et al. ................ 395/200.5
`FOREIGN PATENT DOCUMENTS
`O 608 981 A2 8/1994 European Pat. Off..
`O 608 981 A3 8/1994 European Pat. Off..
`635 958 A2 1/1995 European Pat. Off..
`2 253 970 9/1992 United Kingdom.
`OTHER PUBLICATIONS
`T. Haduong et al., “Stratified Reference Model an Open
`Architecture Approach for B-ISDN”, International Switch
`ing Symposium, Stockholm, Sweden, May 27 Jun. 1,
`1990, vol. III, pp. 115-121.
`(List continued on next page.)
`Primary Examiner Alpus H. Hsu
`Attorney, Agent, or Firm-Burns, Doane, Swecker &
`Mathis, L.L.P.
`ABSTRACT
`57
`A method and device partition physical transmission
`resources of a physical network. At first, a Set of logical
`networks is established on top of the physical network. The
`logical networks comprise nodes and logical linkS eXtending
`between the nodes So as to form the logical networks. The
`logical links are used by routes. Next, the capacities of the
`logical links of the logical networks are determined Such that
`the route blocking probability on each individual route in
`each one of the logical networks is less than or equal to a
`maximum allowed blocking probability for each individual
`route. This is realized by distributing, for each individual
`route, the route blocking evenly among the logical linkS used
`by the individual route. Finally, the physical transmission
`resources are allocated among the logical links of the logical
`networks according to the determination.
`
`4,669,113 5/1987 Ash et al. ............................... 379/221
`
`15 Claims, 6 Drawing Sheets
`
`ESABLISHINGA SET OF
`OGICALNETWORKSON TOP OF
`APHYSICANEWORK
`
`DETERMINING OGICANK
`CAPACTIESSUCHTHAT THE
`ROUEBLOCKNG ONEACHROUTE
`NACHOGICALNETWORKS
`SSTHANA MAXIMUMBLOCKING
`WALUE GIVEN FOREACHROUTE,
`BYDSBUTING THEACTUAL
`ROUTELOCKNG EVENLY AMONG
`THE LOGICALINKSUSED BY
`THERSPECTIVE ROUTE
`
`—
`
`ALLOCATING THE PHYSICAL
`TRANSMISSION RESOURCES
`AMONG THELOGICALNETWORKS
`ACCORDINGTOTHEDEERMINED
`LOGICALLINKCAPACTIES
`
`Ex.1007
`CISCO SYSTEMS, INC. / Page 1 of 14
`
`

`

`6,104,699
`Page 2
`
`OTHER PUBLICATIONS
`J.P. Labourdette, “Blocking Probabilities in Multitraffic Loss
`Systems: Insensitivity, ASymptotic Behavior, and Approxi
`mations”, IEEE Transactions on Communications, vol. 40.,
`No. 8, Aug. 1992, pp. 1355–1366.
`M. MacGregor et al., “Connectability: A Performance Met
`ric For Reconfigurable Transport Networks”, IEEE Journal
`on Selected Areas in Communications, vol. 11., No. 9, Dec.
`1993, pp. 1461–1469.
`
`A. Hiramatsu, “Integration of ATM Call Admission Control
`and Link Capacity Control by Distributed Neural Net
`works', IEEE Journal on Selected Areas in Communica
`tions, vol. 9, No. 7, Sep. 1991, pp. 1131-1138.
`G. Gopal et al., “Dynamic Network Configuration Manage
`ment', IEEE International Conference on Communications,
`Atlanta, vol. 2, Apr. 1990, pp. 295-301.
`
`Ex.1007
`CISCO SYSTEMS, INC. / Page 2 of 14
`
`

`

`U.S. Patent
`
`Aug. 15, 2000
`
`Sheet 1 of 6
`
`6,104,699
`
`
`
`
`
`sureifiold Sure16014
`
`| | | | 1
`
`Ex.1007
`CISCO SYSTEMS, INC. / Page 3 of 14
`
`

`

`U.S. Patent
`
`Aug. 15, 2000
`
`Sheet 2 of 6
`
`6,104,699
`
`Fig.2
`
`
`
`NODE PAIR
`IN THE
`LOGICAL
`NETWORK
`
`LOGICAL
`NETWORK
`
`PHYSICAL
`NETWORK
`
`Ex.1007
`CISCO SYSTEMS, INC. / Page 4 of 14
`
`

`

`U.S. Patent
`
`Aug. 15, 2000
`
`Sheet 3 of 6
`
`6,104,699
`
`Fig.3
`
`APPLICATIONS
`
`CIRCUITEMULATION
`SMDS
`FRAME RELAY etC.
`
`ATMVPWC
`
`ATM
`
`SDH/ATM
`
`
`
`Ex.1007
`CISCO SYSTEMS, INC. / Page 5 of 14
`
`

`

`U.S. Patent
`
`Aug. 15, 2000
`
`Sheet 4 of 6
`
`6,104,699
`
`
`
`ESTABLISHING ASET OF
`LOGICALNETWORKSON TOP OF
`A PHYSICALNETWORK
`
`DETERMINING LOGICAL LINK
`CAPACTIES SUCH THAT THE
`ROUTE BLOCKING ONEACH ROUTE
`NEACH LOGICAL NETWORKS
`LESS THAN A MAXIMUMBLOCKING
`VALUE GIVEN FOREACHROUTE,
`BY DISTRIBUTING THE ACTUAL
`ROUTE BLOCKING EVENLY AMONG
`THE LOGICAL LINKS USED BY
`THE RESPECTIVE ROUTE
`
`ALLOCATING THE PHYSICAL
`TRANSMISSION RESOURCES
`AMONG THE LOGICALNETWORKS
`ACCORDING TO THE DETERMINED
`LOGICAL LINK CAPACTIES
`
`Fig.4
`
`Ex.1007
`CISCO SYSTEMS, INC. / Page 6 of 14
`
`

`

`U.S. Patent
`
`Aug. 15, 2000
`
`Sheet 5 of 6
`
`6,104,699
`
`Fig.5
`
`ESTABLISHA SET OF
`LOGICALNETWORKS
`
`CALCULATEA MAXIMUM
`POSSIBLEVALUE FOR THE BLOCKING
`PROBABILITY ONEACH LOGICAL LINK
`BY DISTRIBUTING THE ROUTE
`BLOCKING EVENLY AMONG THE LOGICAL
`LINKS USED BY THE RESPECTIVE ROUTE
`
`CALCULATE OFFERED TRAFFIC VALUES
`FOREACH LOGICAL LINKIN EACH ONE
`OF THE LOGICAL NETWORKS
`
`NVERT NUMERICALLY ANK
`BLOCKING FUNCTION IN ORDER
`TO DETERMNEA FIRST SET OF
`LOGICAL LINK CAPACITES
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`NORMALIZE THE FIRST SET OF
`LOGICAL LINKCAPACTES SUCH
`THAT THEY SATISFY THE PHYSICAL
`CAPACITY CONSTRAINTS
`
`ALLOCATE THE PHYSICAL TRANSMISSION
`RESOURCES INACCORDANCE WITH
`THE NORMALIZED LOGICAL LINK
`CAPACITIES
`
`Ex.1007
`CISCO SYSTEMS, INC. / Page 7 of 14
`
`

`

`U.S. Patent
`
`Aug. 15, 2000
`
`Sheet 6 of 6
`
`6,104,699
`
`A PHYSICALNETWORK
`TO WHICH THE METHOD
`ACCORDING TO THE INVENTION
`HAS BEEN APPLIED
`
`NO
`
`
`
`
`
`
`
`
`
`
`
`
`
`CHANGES
`IN THE LOGICAL
`NETWORK TOPOLOGY
`OR FACILITY
`FAILURE
`?
`
`YES APPYTHE
`COMPLETE
`METHOD
`AGAN TAKING
`THE NEW
`DEMANDS
`AND CONDITIONS
`INTO ACCOUNT
`
`
`
`
`
`
`
`NO
`
`CHANGING
`TRAFFIC
`CONDITIONS
`
`
`
`YES REPEATHE
`STEPS OF
`DETERMINING
`AND ALLOCATING
`TAKING THE
`TRAFFIC CHANGES
`INTO ACCOUNT
`
`Fig.6
`
`Ex.1007
`CISCO SYSTEMS, INC. / Page 8 of 14
`
`

`

`6,104,699
`
`1
`METHOD AND DEVICE FOR
`PARTITIONING PHYSICAL NETWORK
`RESOURCES
`
`TECHNICAL FIELD OF THE INVENTION
`The present invention relates to telecommunication net
`WorkS and in particular to the partitioning of physical
`network resources.
`
`5
`
`BACKGROUND ART
`
`A main characteristic of a modern telecommunication
`network is its ability to provide different services. One
`efficient way of providing Said Services is to logically
`Separate the resources of a physical network-resource
`separation (see FIG. 1). On top of a physical network PN
`there is established a number of logical networks LN, also
`referred to as logical or virtual Subnetworks, each of which
`comprises nodes N and logical linkSLL interconnecting the
`nodes. Each logical network forms a logical view of parts of
`the physical network or of the complete physical network. In
`particular, a first logical network LN1 comprises one view of
`parts of the physical network and a Second logical network
`LN2 comprises another view, different from that of the first
`logical network. The logical links of the various logical
`networks share the capacities of physical linkS present in
`Said physical network.
`A physical network comprises Switches S (physical
`nodes) or equivalents, physical links interconnecting said
`Switches, and various auxiliary devices. A physical link
`utilizes transmission equipment, Such as fiber optic
`conductors, coaxial cables or radio links. In general, physi
`cal links are grouped into trunk groups TG which extend
`between said Switches. There are access points to the physi
`cal network, to which access points access units Such as
`telephone Sets, computer modems are connected. Each
`physical link has limited transmission capacity.
`FIG. 2 is a simple Schematic drawing explaining the
`relationship between physical links, logical links and also
`routes. A simple underlying physical network with physical
`Switches S and trunk groupS TG, i.e. physical links, inter
`connecting the Switches is illustrated. On top of this physical
`network a number of logical networks are established, only
`one of which is shown in the drawing. The logical networks
`can be established by a network manager, a network operator
`or other organization. In Our Swedish Patent Application
`9403035-0, incorporated herein by reference, there is
`described a method of creating and configuring logical
`networks. The Single logical network shown comprises
`logical nodes N1, N2, N3 corresponding to physical
`Switches S1, S2 and S3 respectively. Further the logical
`network comprises logical linkS LL interconnecting the
`logical nodes N1-N3. A physical link is logically subdivided
`into one or more logical links, each logical link having an
`individual traffic capacity referred to as logical link capacity.
`It is important to note that each logical link may use more
`than one physical link or trunk group. To each node in each
`logical network there is usually associated a routing table,
`which is used to route a connection from node to node in the
`particular logical network Starting from the node associated
`with the terminal that originates the connection and ending
`at the node associated with the terminal which terminates
`Said connection. Said nodes together form an origin
`destination pair. A node pair with two routes is also illus
`trated. One of the routes is a direct route DR while the other
`one is an alternative route AR. In general, the links and the
`routes should be interpreted as being bidirectional.
`
`15
`
`25
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`2
`In order to avoid misconceptions the following definitions
`will be used: A route is a Subset of logical links which belong
`to the same logical network, i.e. a route have to live in a
`Single logical network. Note that it can be an arbitrary Subset
`that is not necessarily a path in the graph theoretic Sense.
`Nevertheless, for practical purposes, routes are typically
`conceived as simple paths. The conception of a route is used
`to define the way a connection follows between nodes in a
`logical network. A node pair in a logical network, the nodes
`of which are associated with acceSS points, is called an
`origin-destination (O-D) pair. In general, all node pairs in a
`logical network are not O-D pairs, but instead Some nodes
`in a logical network may be intermediate nodes to which no
`access points are associated. A logical link is a Subset of
`physical linkS.
`Information, Such as voice, Video and data, is transported
`in logical networks by means of different bearer Services.
`Examples of bearer services are STM 64 (Synchronous
`Transmission Mode with standard 64 kbit/s), STM 2 Mb
`(Synchronous Transmission Mode with 2 Mbit/s) and ATM
`(Asynchronous Transfer Mode). From a service network,
`such as PSTN (Public Switched Telephone Network) and
`B-ISDN (Broadband Integrated Services Digital Network),
`a request is Sent to a logical network that a connection
`should be set up in the corresponding logical network.
`Although the physical network is given, it is necessary to
`decide how to define a set of logical networks on top of the
`physical network and how to distribute or partition Said
`physical network resources among the logical networks by
`Subdividing physical link capacities into logical link capaci
`ties associated with Said logical networks. Since the logical
`networks share the same given physical capacities, there is
`a trade-off between their quality: GoS (Grade of Service)
`parameters, call blocking probabilities etc. can be improved
`in one of the logical networks only at the price of degrading
`the quality in other logical networks. When considering a
`large and complex physical telecommunication network a
`considerable amount of logical links will exist, Said logical
`links sharing the capacities of the physical network. It is not
`at all an easy task to design a method for partitioning
`physical network resources among logical networks which
`does not require Substantial computational power. In accor
`dance with the present invention there is proposed a Strik
`ingly simple and Straightforward method for resource
`partitioning, the computational complexity of which method
`is very Small.
`
`SUMMARY OF THE INVENTION
`On top of a physical network a number of logical net
`Works are established in which logical links, used by routes,
`share the same physical transmission and Switching
`resources. There are Several reasons for logically Separating
`physical resources. Logical resource Separation for offering
`different Grade of Service classes, virtual leased networks
`with guaranteed resources and peak rate allocated virtual
`paths are Some examples of interesting features in the
`design, dimensioning and management of physical net
`works. However, it is still necessary to decide how to
`distribute or partition Said physical network resources
`among the logical networks. In general, the determination of
`this resource partitioning requires Substantial computational
`power.
`In accordance with a main aspect of the present invention
`there is provided a computationally very simple method for
`partitioning physical network resources among logical net
`WorkS.
`
`Ex.1007
`CISCO SYSTEMS, INC. / Page 9 of 14
`
`

`

`3
`In accordance with a first aspect of the invention there is
`provided a method for resource partitioning, in which a Set
`of logical networks is established on top of a physical
`network comprising physical transmission and Switching
`resources, Said logical networks comprising nodes and logi
`cal links extending between the nodes So as to define the
`topology of Said logical networks. The logical links are used
`by routes interconnecting the nodes of node pairs in the
`logical networks. Logical link capacities are determined
`such that the route blocking probability on each individual
`route in each one of the logical networks is less than or
`possibly equal to a maximum allowed blocking probability,
`given for each individual route, by distributing the route
`blocking evenly among the logical links used by the respec
`tive route. Finally, the physical transmission resources are
`allocated among the logical links of the logical networks
`according to the determined logical link capacities.
`In accordance with a Second aspect of the invention there
`is provided a device for partitioning physical transmission
`resources among logical networks.
`
`15
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`The novel features believed characteristic of the invention
`are set forth in the appended claims. The invention itself,
`however, as well as other features and advantages thereof,
`will be best understood by reference to the detailed descrip
`tion of the specific embodiments which follows, when read
`in conjunction with the accompanying drawings, wherein:
`FIG. 1 shows a physical network, on top of which a
`number of logical networks are established, and an operation
`and support system (OSS) which controls the operation of
`the overall network,
`FIG. 2 is a Schematic drawing explaining the relationship
`between physical links and Switches, logical links and
`nodes, and also routes,
`FIG. 3 is a schematic drawing of a B-ISDN network from
`the viewpoint of the Stratified Reference Model,
`FIG. 4 is a Schematic flow diagram illustrating a method
`in accordance with a general inventive concept of the
`present invention,
`FIG. 5 is a flow diagram illustrating, in more detail, a
`method in accordance with a first preferred embodiment of
`the invention,
`FIG. 6 is a schematic flow diagram illustrating how the
`method in accordance with a first preferred embodiment of
`the present invention flexibly adapt the overall network
`System to changing traffic conditions, but also to facility
`failures and demands for new logical network topologies,
`PREFERRED EMBODIMENTS OF THE
`INVENTION
`An important tool in network management, particularly
`the management and dimensioning of large ATM networks,
`is the distribution of resources of a physical network among
`logical networks that share the capacity of the physical
`network. There are Several advantages of logical resource
`Separation:
`It has gradually been recognized in the last couple of years
`that it is not at all easy to integrate Services with very
`different demands to e.g. bandwidth, grade of Service or
`congestion control functions. In Some cases it turn out
`to be better to support different services by offering
`Separate logical networks, and limiting the degree of
`integration to only partial rather than complete Sharing
`of physical transmission and Switching resources. Net
`
`25
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`6,104,699
`
`4
`work management can be simplified if Service classes
`are arranged into groups in Such a way that only those
`of Similar properties are handled together in a logical
`network. For example, delay Sensitive and loSS Sensi
`tive Service classes can possibly be managed and
`Switched easier if the two groups are handled Separately
`in different logical Subnetworks, rather than all mixed
`on a complete Sharing basis. Moreover, in this way they
`can be safely handled on call level without going down
`to cell level as e.g. in priority queues. Of course, within
`a logical network Statistical multiplexing, priority
`queuing and other mechanisms can Still be applied
`among Service classes that already have not too differ
`ent characteristics,
`Important Structures Such as virtual leased networks,
`required by large business users, and Virtual LANs are
`much easier to implement;
`A Virtual Path (VP), a standardized element of ATM
`network architecture, can be considered as a special
`logical network;
`The physical network operates more Safely.
`A physical network, e.g. a large telecommunication
`network, with physical resources is considered. In FIG. 1
`there is illustrated a physical network PN on top of which a
`set of logical networks LN1, LN2, . . . , LNX (assuming
`there are X logical networks) is established. Each logical
`network comprises nodes N and logical linkS LL intercon
`necting the nodes. The topology of these logical or virtual
`networks will in general differ from the topology of the
`underlying physical network.
`The network System is preferably controlled by an opera
`tion and Support System OSS. An operation and Support
`System OSS usually comprises a processor System PS,
`terminals T and a control program module CPM with a
`number of control programs CP along with other auxiliary
`devices. The architecture of the processor System is usually
`that of a multiprocessor System with Several processors
`working in parallel. It is also possible to use a hierarchical
`processor Structure with a number of regional processors and
`a central processor. In addition, the Switches themselves can
`be equipped with their own processor units in a not com
`pletely distributed System, where the control of certain
`functions are centralized. Alternatively, the processor Sys
`tem may consist of a Single processor, often a large capacity
`processor. Moreover, a database DB, preferably an interac
`tive database, comprising e.g. a description of the physical
`network, traffic information and other useful data about the
`telecommunication System, is connected to the OSS. Special
`data links, through which a network manager/operator con
`trols the Switches, connect the OSS with those Switches
`which form part of the network system. The OSS contains
`e.g. functions for monitoring and controlling the physical
`network and the traffic.
`From this operation and support system OSS the network
`manager establishes a number of logical networks on top of
`the physical network by associating different parts of the
`traffic with different parts of the transmission and Switching
`resources of the physical network. This can e.g. be realized
`by controlling the port assignment of the Switches and croSS
`connect devices of the physical network, or by call admis
`Sion control procedures. The process of establishing logical
`networks means that the topology of each one of the logical
`networks is defined. In other words, the structure of the
`nodes and logical links in each logical network is deter
`mined.
`Conveniently, traffic classes are arranged into groups in
`such a way that those with similar demands to bandwidth are
`
`Ex.1007
`CISCO SYSTEMS, INC. / Page 10 of 14
`
`

`

`6,104,699
`
`15
`
`25
`
`35
`
`40
`
`S
`handled together in a separate logical network. By way of
`example, all traffic types requiring more than a given amount
`of bandwidth can be integrated in one logical network, and
`those traffic types that require leSS bandwidth than this given
`amount can be integrated in another logical network. In
`other words, the two traffic groups are handled Separately in
`different logical Subnetworks. In particular, this is advanta
`geous for an ATM network carrying a wide variety of traffic
`types. However, in one embodiment of the present
`invention, each individual traffic type is handled in a sepa
`rate logical network.
`Preferably, the present invention is applied in the B-ISDN
`(Broadband Integrated Services Digital Network) network
`environment. A fully developed B-ISDN network will have
`a very complex Structure with a number of overlaid net
`WorkS. One conceptual model Suitable of describing overlaid
`networks is the Stratified Reference Model as described in
`“The Stratified Reference Model: An Open Architecture to
`B-ISDN" by T. Hadoung, B. Stavenow, J. Dejean, ISS'90,
`Stockholm. In FIG. 3 a schematic drawing of a B-ISDN
`network from the viewpoint of the Stratified Reference
`Model is illustrated (the protocol viewpoint to the left and
`the network viewpoint to the right). Accordingly, the
`B-ISDN will consist of the following strata. A transmission
`stratum based on SDH (Synchronous Digital Hierarchy) or
`equivalent (SONET) at the bottom, a cross connect stratum
`based on either SDH or ATM (Asynchronous Transfer
`Mode) on top of that, which acts as an infrastructure for the
`ATM VP/VC stratum with Switched connections. Finally,
`the large Set of possible applications uses the croSS connect
`Stratum as an infrastructure. In one particular embodiment of
`the present invention it is the infrastructure network mod
`elling the croSS connect Stratum in a B-ISDN overlaid
`network that is considered. In general, this infrastructure
`network is referred to as a physical network.
`Of course, it is to be understood that the present invention
`can be applied to any physical telecommunication network.
`The physical transmission resources, i.e. the transmission
`capacities of the physical links, have to be partitioned or
`distributed among the logical links of Said logical networks
`in some way. Since ATM has similarities with both packet
`Switched and circuit Switched networks it is not a priori
`obvious which properties should have the greatest impact on
`a partitioning or dimensioning model. In the data transfer
`phase the Similarities to packet Switched networks are the
`largest. However, at the connection Setup phase the Simi
`larities to circuit Switching dominate, especially if a preven
`tive connection control concept with small ATM Switch
`buffers has been adopted together with the equivalent band
`width concept. In an approach which models the call Scale
`phenomenon, it is natural to View an ATM network as a
`multirate circuit Switched network in which the most impor
`tant quality of Service parameter is the connection blocking
`probability, i.e. the route blocking probability. In this
`context, there is provided a method in accordance with the
`present invention which designs the capacity values of the
`logical links of the various logical networkS Such that the
`route blocking probability on any route in any of the logical
`networks does not exceed a maximum allowed blocking
`value, given in advance for each route.
`FIG. 4 shows a Schematic flow diagram illustrating a
`method in accordance with a general inventive concept of
`the present invention. In accordance with the present inven
`tion a set of logical networks is established on top of a
`physical network comprising physical transmission and
`Switching resources, Said logical networks comprising nodes
`and logical links extending between the nodes So as to define
`
`45
`
`50
`
`55
`
`60
`
`65
`
`6
`the topology of Said logical networkS. Preferably, the logical
`networks are completely Separated from each other. The
`logical links are used by routes interconnecting the nodes of
`node pairs in the logical networks. Logical link capacities
`are determined Such that the route blocking probability on
`each individual route in each one of the logical networks is
`less than or equal to a maximum allowed blocking
`probability, given for each individual route, by distributing
`the actual route blocking evenly among the logical links
`used by the respective route. Finally, the physical transmis
`Sion resources are allocated among the logical links of the
`logical networks according to the determined logical link
`capacities.
`AS indicated in FIG. 3 the cross connect stratum can be
`realized by either SDH or ATM. If the cross connect stratum
`is based on SDH and the infrastructure network is realizing
`e.g. different quality of Service classes by resource
`Separation, the partitioning can only be performed in integer
`portions of the STM modules of the SDH structure. On the
`other hand, if the cross connect is realized by ATM virtual
`paths then no integrality restriction exists and the partition
`ing can be performed in any real portions. Therefore,
`whether the cross connect stratum is based on SDH or ATM
`will have important implications for the partitioning of the
`physical network resources. The SDH cross connect solution
`gives rise to a model that is discrete with regard to the logical
`link capacities, while the ATM croSS connect Solution gives
`rise to a continuous model. The continuous model requires
`that the ATM Switches support partitioning on the individual
`input and output ports. For example, this is realized by
`multiple logical buffers at the output ports. In a preferred
`embodiment of the invention an infrastructure network
`modelling the ATM croSS connect Stratum is considered
`while in an alternative embodiment an infrastructure mod
`elling the SDH croSS connect is considered, as can be seen
`in FIG. 1.
`At the first glance it might appear that partitioning, as
`opposed to complete sharing, is a reduction of the full
`flexibility of ATM. This is however not the case if the
`partitioning is considered on a general level. On a concep
`tual level the complete Sharing Schemes, e.g. priority
`queuing, Virtual Spacing etc. tell uShow to realize resource
`Sharing on the cell level, while the partitioning approach
`SeekS for the call Scale characteristics, e.g. how to assign
`rates to various logical links, that is then to be realized on the
`cell level. In this Sense the complete partitioning approach
`complements, rather than excludes, the complete Sharing
`approaches.
`Mathematical framework and dimensioning model
`Consider a fixed physical network with N nodes and K
`physical links, on top of which a number of logically
`Separated logical networks are established. If the total num
`ber of logical links over all logical networks is denoted by
`J, and the capacity of an individual logical linki is denoted
`C, then the vector of logical link capacities over all logical
`networks can be written as C=(C,C,..., C). These logical
`link capacities are not known in advance. In fact it is desired
`to dimension the logical links of the logical networks with
`respect to capacity.
`The incidence of physical links and logical linkS is
`expressed by a KXJ matrix S in which the j:th entry in the
`k:th row is equal to 1 if logical linki needs capacity on the
`k:th physical link, otherwise said entry is 0. Naturally, the
`Sum of logical link capacities on the same physical link
`cannot exceed the capacity of the physical link. This physi
`cal constraint can be expressed as
`SCS Chs,
`
`Ex.1007
`CISCO SYSTEMS, INC. / Page 11 of 14
`
`

`

`6,104,699
`
`8
`This can also be expressed as:
`
`7
`where C is defined above, and C refer to the vector of
`given physical link capacities. In addition it is required that
`CSO.
`ASSume that I traffic types are carried in the complete
`network. The role of these traffic types is primarily to handle
`different bandwidth requirements, but traffic types can be
`distinguished also with respect to different holding times or
`even priorities (trunk reservation). By convention, each
`route carries only a Single type of traffic. This means that if
`Several traffic types are to be carried, they are represented by
`parallel routes.
`Let R be the total set of routes over all logical networks,
`that is,
`R =UUU, Rip
`
`(1)
`
`5
`
`15
`
`1-Bsmax, (1–B(r))"
`
`O S.
`
`(3)
`
`(4)
`B,s 1-max, (1-B(r))"
`This means that the maximum possible value for the
`blocking probability on logical linki, under the assumption
`of evenly distributed blocking, can be expressed as follows:
`
`By" = 1 - max, (1 - B(r))"
`
`(5)
`
`Once the maximum possible value for the link blocking
`probability is calculated for each logical link in each one of
`the logical networks, the offered traffic to logical linki can
`be approximated as:
`
`pi = A, (1-B.")^ir
`iii
`reRi
`
`(6)
`
`where A is the amount of bandwidth that route r requires
`on logical linki. If router does not traverse logical link then
`A is equal to Zero.
`Since the value of B," and the corresponding value of p,
`are known for all j, the capacity C, of logical link j can be
`calculated for all by inverting numerically a blocking
`function:
`
`B" = E(p., C.)
`
`(7)
`
`Preferably, the Simple analytic extension of Erlang's
`B-formula to any non-negative real value is used as blocking
`function. However, to preserve generality, any blocking
`function is allowed, that is jointly Smooth in all variables.
`Having obtained the logical link capacities C, from the
`above model, it is necessary to normalize them Such that
`they satisfy the physical capacity constraints, SCsC. If
`the capacity of the physical link k is C.", and the
`capacities of the logical links that need capacity on the k:th
`physical link are C, . . . , C, then the normalized logical
`link capacities associated with physical link k are
`
`Ci =
`
`Cki
`
`XEC 1
`=
`
`hys .
`
`C", i = 1,..., n.
`
`(8)
`
`This normalization procedure is performed for all k.
`The normalized logical link capacities Satisfy the require
`ments on route blocking for each route in each one of the
`various logical networks. In other words, if the physical
`transmission resources are allocated among the logical links
`of the logical networks in accordance with the above nor
`malized logical link capacities, then the blocking probability
`of any route r does not exceed B(r).
`An efficient way of handling the co-existence of many
`different bandwidth demands (traffic types) is to model a
`non-unity bandwidth call by a Sequence of independent
`unity bandwidth calls. In the article “Blocking Probabilities
`in Multitraffic Loss Systems: Insensitivity, Asymptotic
`Behavior and Approximations” by Labourdette and Hart in
`IEEE Trans. Communications, 40 (1992/8) pp. 1355–1366.
`it is proven that this approximation is correct in the asymp
`totic Sense.
`
`25
`
`where R' is the set of routes in logical network U
`realizing communication between node pair p regarding
`traffic type i. It is important to understan