`Holender et al.
`
`54
`
`ENHANCEMENT OF NETWORK
`OPERATION AND PERFORMANCE
`
`(75)
`
`73)
`
`Inventors: Wlodek Holender, deceased, late of
`Lund, Sweden, by Kerstin Korning,
`legal representative, David Holender,
`heir; Tamas Henk, Budapest, Hungary;
`Soren Blaabjerg, Allerod, Denmark;
`András Faragó, Budapest, Hungary;
`Bengt Stavenow, Lund, Sweden
`Assignee: Telefonaktiebolaget LM Ericsson,
`Stockholm, Sweden
`Appl. No.:
`08/765,106
`PCT Fed:
`Jun. 12, 1995
`PCT No.:
`PCT/SE95/00704
`S371 Date:
`Apr. 21, 1997
`S 102(e) Date: Apr. 21, 1997
`PCT Pub. No.: WO95/34981
`PCT Pub. Date: Dec. 21, 1995
`Int. Cl. .............................................. H04Q 11/04
`U.S. Cl. .......................... 370/397; 370/399; 370/409;
`370/468
`Field of Search ..................................... 370/232, 248,
`370/252, 253,338, 347, 388, 397, 400,
`409, 465, 468,399, 396
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`4,744,028 5/1988 Karmarkar .............................. 364/402
`4,763,319 8/1988 Rozenblit .....
`... 370/397
`5,166,927 11/1992 Iida et al...
`... 370/238
`5,854,903 12/1998 Morrison et al. ....................... 370/388
`FOREIGN PATENT DOCUMENTS
`0631 413 A2 12/1994 European Pat. Off. ........ HO4L 12/56
`
`US006069894A
`Patent Number:
`11
`(45) Date of Patent:
`
`6,069,894
`May 30, 2000
`
`OTHER PUBLICATIONS
`
`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 (1991).
`G. Gopal et al., “Algorithms for reconfigurable networks,”
`Teletraffic and Datatraffic in a period of change, ITC 13
`(1991).
`F.P. Kelly, “Routing and Capacity Allocation in Networks
`with Trunk Reservation,” Mathematics of Operations
`Research, vol. 15, No. 4(1990).
`F.P. Kelly, “Fixed Point Models of Loss Networks” in J.
`Austral. Math. Soc. Ser. B31 (1989) pp. 204–218.
`A. Farago et al., Resource Separation. An Efficient Tool for
`Optimizing ATM Network Configuration, Networks 94
`(Sep.1994).
`
`(List continued on next page.)
`
`Primary Examiner Douglas W. Olms
`ASSistant Examiner Shick Hom
`Attorney, Agent, or Firm-Burns, Doane, Swecker &
`Mathis, L.L.P.
`ABSTRACT
`57
`A Set of logical networks is established on top of a physical
`network Next, a predefined objective function, closely
`related to the operation and performance of the physical
`network, which physical network is viewed as the Set of
`logical networks, is optimized with respect to at least one Set
`of decision variables. Finally, the decision variables in
`accordance with the optimization are used to control the
`operation of the overall network System. Physical transmis
`Sion resources are partitioned among logical networkS. Traf
`fic loads are distributed among routes interconnecting the
`nodes of node pairs.
`
`45 Claims, 10 Drawing Sheets
`
`ESTABLISHING ASET OF
`LOGICALNETWORKS ON TOP
`OF A PHYSICALNETWORK
`
`
`
`OPTIMIZING AN OBJECTIVE
`FUNCTION WHICH IS CLOSELY
`RELATED TO THE OPERATION OF
`THE PHYSICAL NETWORK WITH
`RESPECT TO DECISION
`VARIABLES
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`CONTROLLING THE OPERATION OF
`THE PHYSICAL NETWORKVIEWED
`AS THE SET OF LOGICAL NETWORKS
`USING THE DECISION VARIABLES
`
`Arista Networks, Inc.
`Ex. 1020, p. 1
`
`
`
`6,069,894
`Page 2
`
`OTHER PUBLICATIONS
`
`Labourdette et al., Blocking Probabilities in Multitrafic
`LOSS Systems. Insensitivity Asymptotic Behavior and
`Approximations, IEEE Trans. Communications, Vol. 40, pp.
`1355–1366 (Aug. 1992).
`
`G. Gopal et al., “Dynamic Network Configuration Manage
`ment.” IEEE International Conference on Communications,
`vol. 2 (Apr. 1990).
`T. Hadnong, B. Stavenow, J. Dejean “Stratified Reference
`Model An Open Architecture Approach for B-ISDN” ISS
`1990.
`Patent Abstracts of Japan, vol. 17, No. 652 (E-1466),
`Abstract of JP-A-5-207068 (Aug. 13, 1993).
`
`Arista Networks, Inc.
`Ex. 1020, p. 2
`
`
`
`U.S. Patent
`
`May 30, 2000
`
`Sheet 1 of 10
`
`6,069,894
`
`
`
`
`
`
`
`
`
`
`
`
`?pON
`
`dn019
`
`| | | |
`
`
`
`
`
`?00uu00 SSOJO HOS
`
`Arista Networks, Inc.
`Ex. 1020, p. 3
`
`
`
`U.S. Patent
`
`May 30, 2000
`
`Sheet 2 of 10
`
`6,069,894
`
`
`
`NODE PAIR
`IN THE
`LOGICAL
`NETWORK
`
`LOGICAL
`NETWORK
`
`PHYSICAL
`NETWORK
`
`FIG. 2
`PRIOR ART
`
`Arista Networks, Inc.
`Ex. 1020, p. 4
`
`
`
`U.S. Patent
`
`May 30, 2000
`
`Sheet 3 of 10
`
`6,069,894
`
`
`
`APPLICATIONS
`
`CIRCUIT EMULATION
`SMDS
`FRAME RELAY etc.
`
`ATM VP/VC
`
`ATM
`
`SDH/ATM
`
`SDH
`
`
`
`FIG. 3
`PRIOR ART
`
`Arista Networks, Inc.
`Ex. 1020, p. 5
`
`
`
`U.S. Patent
`
`May 30, 2000
`
`Sheet 4 of 10
`
`6,069,894
`
`ESTABLISHING ASET OF
`LOGICAL NETWORKS ON TOP
`OF A PHYSICALNETWORK
`
`
`
`OPTIMIZING AN OBJECTIVE
`FUNCTION WHICH IS CLOSELY
`RELATED TO THE OPERATION OF
`THE PHYSICAL NETWORK WITH
`RESPECT TO DECISION
`VARIABLES
`
`CONTROLLING THE OPERATION OF
`THE PHYSICAL NETWORKVIEWED
`AS THE SET OF LOGICALNETWORKS
`USING THE DECISION VARIABLES
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`FIG. 4
`
`Arista Networks, Inc.
`Ex. 1020, p. 6
`
`
`
`U.S. Patent
`
`May 30, 2000
`
`Sheet 5 of 10
`
`6,069,894
`
`ESTABLISHA SET OF
`LOGICALNETWORKS
`
`F G 5
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`SELECT AN INITIAL
`DESIGN POINT
`initial
`C
`SOLVE THE FIXED
`POINT ECRUATIONS
`
`SOLVE THE SET OF
`LINEAR EOUATIONS
`
`CALCULATE THE REVENUE DERVATIVES
`WITH RESPECT TO THE PRESENT
`LOGICAL LINK CAPACITIES
`
`DETERMINE THE ASCEND DIRECTION
`BY PROJECTING THE REVENUE GRADENT
`TO THE FEASIBLE REGION
`
`PERFORMA ONE-DMENSIONAL
`LINE SEARCH IN ORDER TO REACH
`A NEW DESIGN POINT
`C
`
`
`
`W
`C
`
`ALLOCATE THE
`PHYSICAL LINK
`CAPACTIES AMONG
`YES
`--THE LOGICALLINKS OF
`THE CORRESPONDING
`LOGICALNETWORKS
`ACCORDING TO C;
`
`Ci
`
`Arista Networks, Inc.
`Ex. 1020, p. 7
`
`
`
`U.S. Patent
`
`May 30, 2000
`
`Sheet 6 of 10
`
`6,069,894
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`A PHYSICALNETWORK TO WHICH
`THE METHOD ACCORDING TO A FIRST
`PREFERREDEMBODIMENT OF THE
`INVENTION HAS BEEN APPLIED
`
`
`
`
`
`
`
`NO
`
`
`
`CHANGES
`IN THE LOGICAL
`NETWORK TOPOLOGY
`OR FACILITY
`FAILURE
`
`
`
`APPLY THE
`COMPLETE
`METHOD
`AGAIN
`TAKING
`THE NEW
`CONDITIONS
`AND
`DEMANDS
`INTO
`ACCOUNT
`
`
`
`
`
`
`
`
`
`
`
`
`
`REPEAT THE
`STEPS OF
`OPTIMIZING
`AND ALLOCATING
`TAKING THE
`TRAFFIC
`CHANGES INTO
`ACCOUNT
`
`CHANGING NYES
`TRAFFIC
`CONDITIONS
`
`
`
`
`
`
`
`F.G. 6
`
`Arista Networks, Inc.
`Ex. 1020, p. 8
`
`
`
`U.S. Patent
`
`May 30, 2000
`
`Sheet 7 of 10
`
`6,069,894
`
`ESTABLISHA SET OF
`LOGICAL NETWORKS
`
`F G 7
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`SELECT AN INITIAL
`DESIGN POINT
`initial
`initial
`V
`r
`C
`SOLVE THE FIXED
`POINT ECRUATIONS
`
`SOLVE THE SET OF
`LINEAR EOUATIONS
`
`CALCULATE THE REVENUE DERVATIVES
`WITH RESPECT TO THE PRESENT
`LOGICAL LINK CAPACITES AND THE
`PRESENT ROUTE OFFERED TRAFFIC
`
`DETERMINE THE ASCEND DIRECTION
`BY A PROJECTION PROCEDURE
`USING THE ABOVE REVENUEDERVATIVES
`
`
`
`PERFORMA ONE-DIMENSIONAL
`LINE SEARCH TO FIND AN OPTIMAL E.R.
`POINT IN THE STEPDIRECTION
`| cABATESSNs
`CVr
`THE LOGICAL LINKS
`OF THE LOGICAL
`NETWORKS
`ACCORDING TOC
`YES
`civ, ANDAECRTION
`THE TRAFFIC LOAD
`AMONG ROUTES
`ACCORDING TO v.
`
`Civr
`
`Arista Networks, Inc.
`Ex. 1020, p. 9
`
`
`
`U.S. Patent
`
`May 30, 2000
`
`Sheet 8 of 10
`
`6,069,894
`
`A PHYSICAL NETWORK TO WHICH
`THE METHOD ACCORDING TO ASECOND
`PREFERREDEMBODIMENT OF THE
`NVENTION HAS BEEN APPLIED
`
`
`
`
`
`
`
`
`
`
`
`APPLY THE
`COMPLETE
`METHOD
`AGAIN
`TAKING
`THE NEW
`CONDITIONS
`AND
`DEMANDS
`INTO
`ACCOUNT
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`CHANGES
`IN THE LOGICAL
`NETWORK TOPOLOGY
`OR FACILITY
`FAyRE
`
`
`
`NO
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`TRAFFIC
`
`
`
`REPEAT THE STEPS
`
`OK
`
`ALLOCATING AND
`APPORTIONING
`TAKING THE
`TRAFFIC
`CHANGES INTO
`ACCOUNT
`
`FIG. 8
`
`OK
`
`OK
`
`Arista Networks, Inc.
`Ex. 1020, p. 10
`
`
`
`U.S. Patent
`
`May 30, 2000
`
`Sheet 9 of 10
`
`6,069,894
`
`FIG. 9
`
`SELECT AN INITIAL
`DESIGN POINT
`initial
`Vr
`SOLVE THE FIXED
`POINTEGRUATIONS
`
`SOLVE THE SET OF
`LINEAR EOUATIONS
`
`CALCULATE THE REVENUEDERVATIVES
`WITH RESPECT TO THE PRESENT
`ROUTE OFFERED TRAFFIC VALUES
`
`DETERMINE THE ASCEND DIRECTION
`BY APROJECTION PROCEDURE
`USING THE ABOVE REVENUE DERVATIVES
`
`PERFORMA ONE-DIMENSIONAL
`LINE SEARCH TO FINDAN OPTIMAL
`POINT IN THE STEP DIRECTION
`
`
`
`APPORTION THE
`TRAFFIC LOAD
`AMONG ROUTES
`ACCORDING TO
`V
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Arista Networks, Inc.
`Ex. 1020, p. 11
`
`
`
`U.S. Patent
`
`May 30, 2000
`
`Sheet 10 of 10
`
`6,069,894
`
`
`
`
`
`
`
`
`
`ŽXSWS WSWS
`N Š 2.É.
`N 2
`Š%NW 2
`N% 3.53% S
`ÉS
`
`
`
`
`
`N
`N N
`
`
`
`
`
`Arista Networks, Inc.
`Ex. 1020, p. 12
`
`
`
`1
`ENHANCEMENT OF NETWORK
`OPERATION AND PERFORMANCE
`
`6,069,894
`
`2
`to the Same logical network, i.e. a route have to live in a
`Single logical network. Note that it can be an arbitrary Subset
`that Is not necessarily a path in the graph theoretic Sense.
`Nevertheless, for practical purposes, routes are typically
`conceived as simple paths. The conception of a route is used
`to define the way a connection follows between nodes in a
`logical network. A node pair in a logical network, the nodes
`of which are associated with acceSS points, is called an
`origin-destination (O-D) pair. In general, all node pairs in a
`logical network are not O-D pairs, but instead Some nodes
`in a logical network may be intermediate nodes to which no
`access points are associated. A logical link is a Subset of
`physical linkS.
`Information, Such as voice, Video and data, is transported
`In logical networks by means of different bearer Services.
`Examples of bearer services are STM 64 (Synchronous
`Transmission Mode with standard 64 kbit/s), STM 2 Mb
`(Synchronous Transmission Mode with 2 Mbit/s) and ATM
`(Asynchronous Transfer Mode). From a service network,
`such as PSTN (Public Switched Telephone Network) and
`B-ISDN (Broadband Integrated Services Digital Network) a
`request is Sent to a logical network that a connection should
`be set up in the corresponding logical network.
`Although the physical network is given, it is necessary to
`decide how to establish logical networks on top of the
`physical network and how to distribute or partition Said
`physical network resources among logical networks by
`Subdividing physical link capacities into logical link 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. It is a highly non-trivial
`task to find the partitioning of resources So as to optimize the
`overall network performance, in particular when considering
`a large and complex network. Furthermore, the network
`performance is also affected by the distribution of offered
`traffic load among the routes which can realize communi
`cation even within a single network. It is the management
`and dimensioning of a resource Separated network to which
`the present invention is directed.
`RELATED TECHNIOUE
`A method for adaptive link capacity control, and the
`integration of call admission control and link capacity
`control, by using distributed neural networks is disclosed in
`the article entitled “Integration of ATM Call Admission
`Control and Link Capacity Control by Distributed Neural
`Networks” by A. Hiramatsu in IEEE Journal on Selected
`Areas in Communications, vol. 9, no. 7 (1991). At first
`neural networks are trained to estimate the call loSS rate
`given the link capacity and observed traffic. Next, an objec
`tive function of the link capacity assignment optimization
`problem, constituted by the maximum call loSS rate in the
`network, is optimized by a simple random optimization
`method according to the estimated call loSS rate.
`The method of Hiramatsu only considers the optimization
`problem on the level of logical links. The concept of logical
`networks is not at all incorporated in the approach of
`Hiramatsu. Besides, the optimization method, the Matyas
`random optimization method, is a simple method generally
`leading to a Suboptimal Solution. Also, only one bit-rate
`class is considered in the model.
`The article “Algorithms for reconfigurable networks” in
`Teletraffic and Datatraffic in a period of change, ITC 13
`
`TECHNICAL FIELD OF THE INVENTION
`The present invention relates to telecommunication net
`WorkS and in particular to overall network performance.
`BACKGROUND ART
`A main characteristic of a modern telecommunication
`network is its ability to provide different services. One
`efficient way of providing Said Services is to logically
`Separate the resources of a physical network-resource
`separation (see FIG. 1). On top of a physical network PN
`there is established a number of logical networks LN, also
`referred to as logical or virtual Subnetworks, each of which
`comprises nodes N and logical 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 and computer modems, are connected. Each
`physical link has limited transmission capacity.
`FIG. 2 is a simple Schematic drawing explaining the
`relationship between physical links, logical links and also
`routes. A simple underlying physical network with physical
`Switches S and trunk groupS TG, i.e. physical links, 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 the figures, the links and
`the routes may be interpreted as being bidirectional.
`In order to avoid misconceptions the following definitions
`will be used: A route is a Subset of logical links which belong
`
`15
`
`25
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`Arista Networks, Inc.
`Ex. 1020, p. 13
`
`
`
`6,069,894
`
`3
`(1991) by G. Gopal et al. relates to an optimal logical
`network design method for a reconfigurable network, i.e. a
`network which can change between logical networks. The
`weighted blocking averaged over all Source-destination
`pairs, is minimized by a simple heuristic algorithm.
`Subsequently, the logical network is reconfigured according
`to this minimization.
`According to the method of Gopal et al. there exists a
`number of possible logical network configurations.
`However, only one logical network can be used in a certain
`traffic Situation. This Single logical network can be recon
`figured in accordance with the heuristic minimization algo
`rithm. Furthermore, the configuration of the Single logical
`network is not at all based on e.g. traffic types, but is instead
`closely related to the given physical network. Besides,
`Gopal uses a very simple estimation of route blocking which
`is adequate only for Small networks. Moreover, in the
`method of Gopal et al. the problem is formulated as a
`non-linear integer problem and due to this fact the results are
`in general Suboptimal.
`In the article “Routing and Capacity Allocation in Net
`works with Trunk Reservation” in Mathematics of Opera
`tions Research, vol. 15., no. 4, (1990) by F. P. Kelly the
`derivatives of an implicitly defined revenue function are
`calculated. The use of these derivatives in the management
`of a single Service network carrying Single rate traffic with
`the emphasis on trunk reservation is Suggested.
`In the U.S. Pat. No. 4,744,028 a method and apparatus for
`optimizing resource allocation is disclosed. More
`Specifically, a linear programming approach is described
`which proceeds in the interior of a polytope Solution Space.
`Each Successive approximation of the Solution point, and the
`polytope, is normalized Such that the Solution point is at the
`center of the normalized polytope. The objective function of
`the linear programming model is then projected into the
`normalized space and the next step is taken in the direction
`of the Steepest decent of the objective function gradient and
`such as to remain within the interior of the polytope. The
`proceSS is repeated until the optimum Solution is closely
`approximated.
`The method described in the above U.S. Patent assumes
`that the resource allocation problem can be adequately
`described by a linear programming model. In its application
`to resource allocation, Such a model consists of a number of
`linear expressions representing the quantitative relationships
`between the various possible allocations, their constraints
`and their costs, i.e. the objective function is a linear function
`of the allocated resources. Moreover, the method according
`to the above U.S. patent does not take teletraffic models,
`Such as e.g. Erlang's B formula, describing the Statistical
`fluctuation of traffic, into consideration. Consequently, the
`linear programming model described in the above U.S.
`patent is quite unsatisfactory. The partitioning problem that
`the present invention considers gives rise to an objective
`function that depends on the allocated resources in an
`indirectly defined non-linear way. The dependence is defined
`through a complicated non-linear System of equations that
`follows from a teletraffic model.
`
`SUMMARY OF THE INVENTION
`On top of a physical network a number of logical 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
`
`4
`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 addition, the distribution of
`offered traffic load among routes interconnecting the nodes
`of node pairs in the logical networks will also affect the
`overall network performance.
`In accordance with the present invention a set of logical
`networks is established on top of a physical network, which
`physical network comprises physical transmission and
`Switching resources. The logical networks comprise nodes
`and logical links extending between the nodes So as to form
`the logical networks. The logical links are used by routes
`interconnecting the nodes of node pairs in the logical
`networkS. Next, in accordance with a main aspect of the
`present Invention, an objective function which is closely
`related to the operation and Overall performance of the
`resource Separated physical network is optimized with
`respect to at least one set of decision variables, given
`physical network parameters and the requirements of each
`logical network. Examples of objective functions are the
`carried traffic in the complete network, the link utilization
`and the network revenue or Some other function representing
`resource utilization or network performance. Two Sets of
`decision variables are the logical link capacities, and the
`load sharing variables controlling the distribution of offered
`traffic load among routes.
`Each Set of decision variables is related to a separate
`aspect of the invention. If the objective function have been
`optimized with respect to the logical link capacities then the
`physical transmission resources of the physical network are
`allocated among the logical links of the various logical
`networks in accordance with the optimization. On the other
`hand, if the objective function have been optimized with
`respect to the load sharing variables, then the offered traffic
`load is distributed, for each individual node pair in each one
`of the logical networks, among the routes interconnecting
`the nodes of the individual node pair, in accordance with the
`optimization.
`Furthermore, optimizing with respect to both the logical
`link capacities and the load Sharing variables relates to yet
`another aspect of the present invention. In this particular
`case, the physical transmission resources of the physical
`network are allocated among the logical links of the various
`logical networks and the offered traffic load is distributed,
`for each individual node pair in each one of the logical
`networks, among the routes interconnecting the nodes of the
`individual node pair, in accordance with the optimization.
`In accordance with a first aspect of the present invention
`there is provided a method and device for partitioning
`physical transmission resources among logical networkS.
`In accordance with a Second aspect of the present inven
`tion there is provided a method and device for distributing
`offered traffic load among routes interconnecting the nodes
`of node pairs.
`In accordance with a third aspect of the present invention
`there is provided a method and device for partitioning Said
`physical transmission resources among logical networks and
`distributing offered traffic load among routes interconnect
`ing the nodes of node pairs.
`BRIEF DESCRIPTION OF THE DRAWINGS
`The novel features believed characteristic of the invention
`are set forth in the appended claims. The invention itself,
`
`15
`
`25
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`Arista Networks, Inc.
`Ex. 1020, p. 14
`
`
`
`S
`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,
`FIG. 7 is a flow diagram illustrating a method in accor
`dance with a Second preferred embodiment of the invention,
`FIG. 8 is a schematic flow diagram illustrating how the
`method in accordance with a Second 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,
`FIG. 9 is a flow diagram illustrating a method in accor
`dance with a third preferred embodiment of the invention,
`FIG. 10 presents experimental results illustrating how
`much gain is achieved by the proposed invention in com
`parison to initial valueS obtained from a convex optimization
`method (COM).
`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
`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
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`6,069,894
`
`1O
`
`15
`
`25
`
`6
`multiplexing, priority queuing and other mechanisms can
`Still be applied among Service classes that already have not
`too different characteristics,
`Important Structures Such as virtual leased networks,
`required by large business users, and Virtual 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
`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.
`
`Arista Networks, Inc.
`Ex. 1020, p. 15
`
`
`
`6,069,894
`
`15
`
`7
`Preferably, the present invention is applied in the B-ISDN
`(Broadband Integrated Services Digital Network) environ
`ment. A fully developed B-ISDN network will have a very
`complex structure with a number of overlaid networks. One
`conceptual model Suitable of describing overlaid networks is
`the Stratified Reference Model as described in “The strati
`fied 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 infrastruc
`ture. In one particular embodiment of the present invention
`it is the infrastructure network modelling the croSS connect
`stratum in a B-ISDN overlaid network that is considered. In
`general, this infrastructure network is referred to as a physi
`cal network.
`Of course, it is to be understood that the present invention
`can be applied to any physical telecommunication network.
`FIG. 4 shows a Schematic flow diagram illustrating a
`method in accordance with a general inventive concept of
`the present invention. In accordance with the present 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
`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. Nex
Accessing this document will incur an additional charge of $.
After purchase, you can access this document again without charge.
Accept $ ChargeStill Working On It
This document is taking longer than usual to download. This can happen if we need to contact the court directly to obtain the document and their servers are running slowly.
Give it another minute or two to complete, and then try the refresh button.
A few More Minutes ... Still Working
It can take up to 5 minutes for us to download a document if the court servers are running slowly.
Thank you for your continued patience.
This document could not be displayed.
We could not find this document within its docket. Please go back to the docket page and check the link. If that does not work, go back to the docket and refresh it to pull the newest information.
Your account does not support viewing this document.
You need a Paid Account to view this document. Click here to change your account type.
Your account does not support viewing this document.
Set your membership
status to view this document.
With a Docket Alarm membership, you'll
get a whole lot more, including:
- Up-to-date information for this case.
- Email alerts whenever there is an update.
- Full text search for other cases.
- Get email alerts whenever a new case matches your search.
One Moment Please
The filing “” is large (MB) and is being downloaded.
Please refresh this page in a few minutes to see if the filing has been downloaded. The filing will also be emailed to you when the download completes.
Your document is on its way!
If you do not receive the document in five minutes, contact support at support@docketalarm.com.
Sealed Document
We are unable to display this document, it may be under a court ordered seal.
If you have proper credentials to access the file, you may proceed directly to the court's system using your government issued username and password.
Access Government Site