US007330431B2
`
`United States Patent
`US 7,330,431 B2
`(12)
`(10) Patent No.:
`Bruckman
`Feb. 12, 2008
`(45) Date of Patent:
`
`6,442,134 BL
`6,456,407 BL
`6,486,988 BI
`6,507,577 BL
`6,510,141 BL
`6,522,627 Bl
`6,560,231 Bl
`6,580,693 BL*
`6,584,535 BI
`6,624,917 Bl
`
`8/2002 Mitchell
`9/2002 Tammela etal.
`11/2002 Lewiset al.
`1/2003 Maugeret al.
`............. 370/356
`
`1/2003 Ramfelt et al.
`we 370/254
`2/2003) Manger wo... 370/230
`5/2003 Kawakamiet al.
`6/2003 Chernyak et al.
`6/2003 Ouellet et al.
`9/2003 Paschal et al.
`
`............ 370/248
`
`(Continued)
`OTHER PUBLICATIONS
`
`Moy. “OSPF”, Version 2, published as Request for Comments
`(RFC) 2328 ofthe Internet Engineering Task Force (IETF) Network
`Working Group, Apr. 1998,
`
`(Continued)
`
`Primary Examiner—Chi Pham
`Assistant Examiner—Thai Hoang
`(74) Attorney, Agent, or Firm—Weingarten, Schurgin,
`Gagnebin & Lebovici LLP
`
`(57)
`
`ABSTRACT
`
`A method for assigning bandwidth in a network including
`nodes coupled by links arranged in a physical topology, the
`method including: defining between the nodes logical con-
`nections associated with a data transmission service to be
`provided over the network, the logical connections having a
`connection topology different from the physical topology,
`and determining respective bandwidth requirements for the
`logical connections based on parameters ofthe service. The
`method further includes mapping the connection topologyto
`the physical topology, so that eachof the logical connections
`is associated with one or morelinks ofthe physical topology,
`and allocating a bandwidth for the service on each ofthe
`links in response to the bandwidth requirements of the
`logical connections and to the mapping.
`
`30 Claims, 4 Drawing Sheets
`
`(54)
`
`(75)
`
`(73)
`
`MULTIPOINT TO MULTIPOINT
`COMMUNICATION OVER RING
`TOPOLOGIES
`
`Inventor: Leon Bruckman, Petah Tikva (IL)
`
`Assignee: Corrigent Systems Ltd., Tel Aviv (IL)
`
`(*)
`
`Notice:
`
`Subject to anydisclaimer, the termofthis
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 700 days.
`
`(21)
`
`(22)
`
`(65)
`
`(51)
`
`(52)
`(58)
`
`(56)
`
`Appl. No.: 10/933,572
`
`Filed:
`
`Sep. 3, 2004
`
`Prior Publication Data
`
`US 2006/0050665 Al
`
`Mar. 9, 2006
`
`Int. CL.
`(2006.01)
`HO4L 12/26
`UWS. Ch. ceceeceeee 370/232; 370/231; 370/235
`Field of Classification Search........ 370/229-235,
`370/237-238, 395.2-395.21
`See applicationfile for complete search history.
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`.....
`
`eevee 709/249
`
`8/1993
`10/1995
`12/1996
`1/1998
`12/1998
`8/1999
`2/2000
`12/2000
`1/2001
`7/2001
`7/2001
`1/2002
`4/2002
`6/2002
`
`Growet al.
`Drakeet al.
`Baugheret al.
`Changet al.
`Morrison et al.
`Kusanoet al.
`Kujoory et al.
`Davis
`Brookset al.
`Ellis et al.
`McNamara
`Beshai et al.
`Hausman
`Bertin et al.
`
`*
`
`AAAAAAAAB
`
`l
`Bl
`Bl
`Bl
`Bl
`Bl
`
`§,235,593
`5,461,611
`5,581,703
`5,706,516
`5,854,903
`5,933,422
`6,021,263
`6,157,654
`6,169,783
`6,256,292
`6,262,976
`6,339,488
`6,370,121
`6,400,681
`
`50
`MAP LOGICAL TOPOLOGY TO PHYSICAL TOPOLOGY
`TO DETERMINE LINKS USED
`
`SUM BANDWIDTH REQUIREMENTS OF BACH LINK
`TO DETERMINE MAPPING BANDWIDTH
`
`JV,
`
` BANDWIDTH = FULL
`
`
`56
`
`
`
`BANDWIDTH ?
`
`|YES
`
`ACTUAL BANDWIDTH=
`MAPPING BANDWIDTH
`
`|
`3
`ACTUAL BANDIDTH=
`MAPPING BANDWIDTH x DP
`
`UNIFIED PATENTSEXHIBIT 1001
`Page 1 of 15
`
`

`

`
`
`
`US 7,330,431 B2
`Page 2
`
`
`
`
`
`
`
`
`
`
`
`
`
`6,625,155
`
`6,639,893
`
`6,639,896
`
`6,647,008
`
`6,678,241
`
`6,680,912
`
`6,711,125
`
`6,731,597
`
`6,757,286
`
`6,763,025
`
`6,778,494
`
`6,795,394
`
`6,801,506
`
`6,820,210
`
`6,826,147
`
`6,826,158
`
`6,922,394
`
`6,934,259
`
`6,952,397
`
`6,965,612
`
`6,992,975
`
`7,035,279
`
`7,042,846
`
`7,058,008
`
`7,158,486
`
`7,161,899
`
`7,184,402
`
`2002/0133756
`
`
`2002/0181479
`
`2002/018666|
`
`2003/0002443
`
`2003/0055920
`
`2003/0145108
`
`2003/0158930
`
`2003/0223428
`
`2004/0052274
`
`
`
`
`
`
`U.S. PATENT DOCUMENTS
`
`
`
`Bl
`9/2003
`
`
`Bl
`10/2003
`
`
`Bl
`10/2003
`
`
`Bl
`11/2003
`
`
`Bl
`1/2004
`
`
`Bl
`1/2004
`
`
`Bl
`3/2004
`
`
`Bl
`5/2004
`
`
`Bl
`6/2004
`
`
`B2
`7/2004
`
`
`
`Bl
`8/2004
`
`
`Bl
`9/2004
`
`
`Bl
`10/2004
`
`
`Bl
`11/2004
`
`
`Bl
`11/2004
`
`
`B2
`11/2004
`
`
`B2
`7/2005
`
`
`B2
`8/2005
`
`
`B2
`10/2005
`
`
`B2
`11/2005
`
`
`Bl
`1/2006
`
`
`B2
`4/2006
`
`
`B2
`5/2006
`
`
`Bl
`6/2006
`
`
`B2
`1/2007
`
`
`B2
`1/2007
`
`
`Bl
`2/2007
`
`
`Al
`9/2002
`
`
`Al
`12/2002
`
`
`Al
`12/2002
`
`
`Al
`1/2003
`
`
`Al
`3/2003
`
`
`Al
`7/2003
`
`
`
`Al
`8/2003
`
`
`Al
`12/2003
`
`
`Al
`3/2004
`
`
`
`Dziong
`
`Chikenji et al.
`
`
`Goodeet al.
`
`
`
`Galandetal.
`
`
`
`Gaiet al.
`
`
`
`Kalmanetal.
`
`
`
`Walrandet al.
`
`
`
`Batchellor et al,
`
`
`Stone
`
`Leatherburyet al.
`
`
`
`................
`Mauger
`
`Swinkelset al.
`
`
`
`Dey
`
`Daruwalla et al,
`
`
`Nandyet al.
`
`
`
`Seamanetal.
`
`
`
`Kajiwara
`
`Klincewicz et al.
`
`
`Moretal.
`tenes 370/223
`
`
`
`
`
`Chohan et al.
`
`
`
`..
`Daniel et al.
`. 370/222
`
`
`
`
`
`Bruckman ...,
`
`
`
`
`Bauer
`
`Wilson et al,
`
`
`Rhodes
`
`Limayeet al.
`
`
`Sharmaet al.
`
`
`Jain
`
`
`Okuno
`
`Santiago et al,
`
`
`Bassoetal.
`
`
`
`Kakadia etal.
`
`
`Joseph et al.
`
`
`Mc Bride
`
`
`Blanqueret al.
`
`
`Wang et al.
`
`
`
`
`cesses 370/230
`
`
`
`
`
`
`
`
`
`
`
`cesses 714/43
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`4/2004 Baueret al.
`2004/0071089 Al
`
`
`
`
`
`4/2004 Kfir
`2004/0076176 Al
`
`
`
`
`6/2004 Mannam
`2004/0105459 Al
`
`
`
`
`2/2005 Wyatt
`2005/0030948 Al
`
`
`
`
`OTHER PUBLICATIONS
`
`
`Awduche, et al., “Requirement
`for Traffic Engineering Over
`
`
`
`
`
`
`
`
`MPLS”, published as IETF RFC 2702, Sep. 1999.
`
`
`
`
`
`
`
`
`Blake,S. et al., “Architecture for Differentiated Services”, Internet
`
`
`
`
`
`
`
`
`
`Engineering Task Force, Network Working Group, RFC 2457, Dec.
`
`
`
`
`
`
`
`
`
`1998.
`
`Seddigh, N. et al., “An Assured Rate Per-Domain Behaviour for
`
`
`
`
`
`
`
`
`
`
`Differentiated Services”, Internet Engineering Task Force, Network
`
`
`
`
`
`
`
`Working Group, Jul. 2001.
`
`
`
`
`D. Tsianget al., Request for Comments (RFC) 2892 of the Internet
`
`
`
`
`
`
`
`
`
`
`
`
`Enginecring Task Force (IETF), Aug. 2000.
`
`
`
`
`
`
`Braden,etal., in IETF RFC 2205, “Resource ReServation Protocol
`
`
`
`
`
`
`
`
`
`
`(RSVP) Version | Functional Specification”, Sep. 1997.
`
`
`
`
`
`
`Andersson, et al.,
`in IETF RIC 3036, “I.DP Specification” Jan.
`
`
`
`
`
`
`
`
`
`
`2001.
`
`Yavatkar ct al., RFC 2814 “A Protocol for RSVP—Based Admis-
`
`
`
`
`
`
`
`
`
`sion Control Over IEEE 802-Style Networks”, May 2000, pp. 1-56.
`
`
`
`
`
`
`
`
`
`
`Official Action dated Nov. 28. 2005, which issued during the
`
`
`
`
`
`
`
`
`
`
`prosecution of US Assignee/Tsraeli Applicant’s U.S. Appl. No.
`
`
`
`
`
`
`
`
`10/054,845, filed Jan. 25, 2002.
`
`
`
`
`
`Office Action dated Mar. 21, 2006 which issued in Applicant’s U.S.
`
`
`
`
`
`
`
`
`
`
`
`Appl. No. 10/128,454, filed Apr. 24, 2002.
`
`
`
`
`
`
`
`
`
`
`An Official Action dated Sep. 29, 2006, which issued during the
`
`
`
`
`
`
`
`
`
`
`
`prosecution of Applicant’s U.S. Appl. No. 10/211,066.
`
`
`
`
`
`
`
`Dziong,et al., “A Framework For Bandwidth Management In ATM
`
`
`
`
`
`
`
`
`
`
`Networks—Aggregate Equivalent Estimation Approach”,
`IEEE/
`
`
`
`
`
`ACMwansaclions on networking. vol. 5, No. 1, Feb. 1997.
`
`
`
`
`
`
`
`
`
`
`Inverse Multiplexing over ATM,Strategic Technologies Group,Jul.
`
`
`
`
`
`
`
`12, 2001.
`
`
`The PPP Multilink Protocol (MP) Standard, RFC 1990, The Internet
`
`
`
`
`
`
`
`
`
`
`Engineering ‘lask Force, www.ietforg, Aug. 1996.
`
`
`
`
`
`
`* cited by examiner
`
`
`
`
`
`
`
`UNIFIED PATENTS EXHIBIT 1001
`Page 2 of 15
`
`UNIFIED PATENTS EXHIBIT 1001
`Page 2 of 15
`
`

`

`U.S. Patent
`
`Sheet1 of 4
`
`US 7,330,431 B2
`
`Feb. 12, 2008
`
`50
`
`19
`
`12
`
`UNIFIED PATENTSEXHIBIT 1001
`Page 3 of 15
`
`

`

`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`U.S. Patent
`
`Feb. 12, 2008
`
`
`
`
`
`
`
`
`Sheet 2 of 4
`
`
`
`
`
`US 7,330,431 B2
`
`
`
`
`
`
`
`
`A
`
`Oo
`
`
`
`
`
`A
`
`oO
`
`
`
`
`
`=
`—
`wm
`=
`RS
`
`=
`—_
`wh
`a
`oS
`
`<< A
`
`<——qq“« 2
`
`
`
`=
`©
`
`
`<o
`oO
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`|<
`
`<
`oO=
`wa
`ms
`Ay
`
`5
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`FIG. Es
`==]
`
`
`
`
`
`
`
`
`
`
`
`=5=
`
`)==
`
`zSo
`
`e w 7
`
`1
`<=
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`UNIFIED PATENTS EXHIBIT 1001
`Page 4 of 15
`
`

`

`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`U.S. Patent
`
`Feb. 12
`
`’
`
`2008
`
`Sheet 3 of 4
`
`US 7,330,431 B2
`
`
`
`
`
`
`
`
`
`
`
`
`
`LIASTYtd———___¥LIAS
`
`
`
`
`
`|Vv
`
`
`
`
`J————0
`
`
`
`
`
`
`
`
`
`
`
`
`
` vy‘Old
`
`
`
`
`
`TVOISAHd
`
`TWOID01
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`<I
`
`94
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`TVOISAHd
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`401=da
`
`
`
`
`
`
`
`dVWALIAILOUNNOODOISVA
`
`UNIFIED PATENTS EXHIBIT 1001
`Page 5 of 15
`
`
`
`
`
`

`

`U.S. Patent
`
`Feb. 12, 2008
`
`Sheet 4 of 4
`
`US 7,330,431 B2
`
`FIG. S
`
`80
`
`JV
`
`MONITOR ACTUAL
`TRAFFIC
`
`82
`
`y
`
`DETERMINE CHANGES
`TO ALLOCATED
`
`CHANGES > GUARD
`VALUE?
`
`
`
`y
`
`>
`
`
`
`
`
`
`
`MAKE CHANGES
`
`VJ
`
`UNIFIED PATENTSEXHIBIT 1001
`Page 6 of 15
`
`

`

`
`
`US 7,330,431 B2
`
`
`
`
`1
`MULTIPOINT TO MULTIPOINT
`
`
`
`COMMUNICATION OVER RING
`
`
`
`TOPOLOGIES
`
`
`FIELD OF THE INVENTION
`
`
`
`
`
`
`
`
`
`The present invention relates generally to data commu-
`
`
`
`
`
`
`
`nications within a network, and specifically to optimizing
`
`
`
`
`
`
`
`
`bandwidth allocation for the data in the network.
`
`
`
`
`
`
`
`
`BACKGROUNDOF THE INVENTION
`
`
`
`
`
`
`2
`often required. Although estimation is difficult, it is neces-
`
`
`
`
`
`
`
`
`sary in order for the CAC to be able to function.
`
`
`
`
`
`
`
`
`
`
`
`One method to allocate guaranteed bandwidth in multi-
`
`
`
`
`
`
`
`point cases is to allocate the full required bandwidthfor all
`
`
`
`
`
`
`
`
`
`
`
`possible paths that packets may travel. In this case there will
`
`
`
`
`
`
`
`
`
`
`
`always be sufficient bandwidth, at
`the cxpense of large
`
`
`
`
`
`
`
`
`
`guaranteed bandwidth wastage. Embodimentsofthe present
`
`
`
`
`
`
`
`
`
`invention provide methods and systems for bandwidth allo-
`
`
`
`
`
`
`
`
`
`cation that make more eflicient use of the guaranteed band-
`
`
`
`
`
`
`
`
`
`width available on the ring network.
`
`
`
`
`
`
`In embodiments of the present
`invention, nodes of a
`
`
`
`
`
`
`
`
`
`network, such as a ring network, are coupled by links
`
`
`
`
`
`
`
`
`
`
`according to a physical topology. One or more data trans-
`
`
`
`
`
`
`
`
`
`mission services operate between the nodes. Each service
`
`
`
`
`
`
`
`
`has a logical connection topology that may be different from
`
`
`
`
`
`
`
`
`
`
`the physical
`topology. The service parameters for cach
`
`
`
`
`
`
`
`
`service determine how much bandwidth each of the nodes in
`
`
`
`
`
`
`
`
`
`
`the network participating in the service is required to supply
`
`
`
`
`
`
`
`
`
`
`for that service. For each service, a controller in the network
`
`
`
`
`
`
`
`
`
`
`
`maps the logical connections in the logical connection
`
`
`
`
`
`
`
`
`topologyof the service to corresponding physical links in
`
`
`
`
`
`
`
`
`
`the physical topology. The controller determines howthe
`
`
`
`
`
`
`
`
`bandwidth of each participating node is to be distributed
`
`
`
`
`
`
`
`
`
`among the logical connections in the logical topology, and
`
`
`
`
`
`
`
`
`
`then generates an actual bandwidth requirement for cach of
`
`
`
`
`
`
`
`
`
`the physical links, based on the mapping.
`
`
`
`
`
`
`
`Typically, the logical connection topology for each ser-
`
`
`
`
`
`
`
`vice is chosen from a numberofdifferent logical connection
`
`
`
`
`
`
`
`
`
`
`topologies, such as a hub and spoke topology anda full mesh
`
`
`
`
`
`
`
`
`
`
`topology, depending on the nature of the service (such as
`
`
`
`
`
`
`
`
`
`
`VODSor VPLS). Assigning the actual bandwidths of the
`
`
`
`
`
`
`
`
`
`links in a physical network according to the logical connec-
`
`
`
`
`
`
`
`
`
`tivity of nodes in services carried by the network is a simple
`
`
`
`
`
`
`
`
`
`
`
`and effective way to allocate bandwidth correctly and effi-
`
`
`
`
`
`
`
`
`ciently, particularly guaranteed bandwidth.
`
`
`
`
`In some embodiments, at least some of the actual band-
`
`
`
`
`
`
`
`
`
`widths are multiplied by a correction factor, typically the
`
`
`
`
`
`
`
`
`
`samefor each ofthe links, that allows for deviation from the
`
`
`
`
`
`
`
`
`
`
`
`
`assigned actual bandwidth.
`
`
`
`In a disclosed embodiment, different services operate in
`
`
`
`
`
`
`
`
`the network, each service having a respective logical con-
`
`
`
`
`
`
`
`
`nection topology and corresponding bandwidths for nodes
`
`
`
`
`
`
`
`participating in the service. Bandwidth requirements for
`
`
`
`
`
`
`
`each of the physical links in the network are determined by
`
`
`
`
`
`
`
`
`
`
`
`mapping each of the respective logical topologies to the
`
`
`
`
`
`
`
`
`
`physical topology of the network, and then adding up the
`
`
`
`
`
`
`
`
`
`
`bandwidths required byall the services on eachofthe links.
`
`
`
`
`
`
`
`
`
`
`
`Typically, during operation of the network, actual band-
`
`
`
`
`
`
`
`width usage is monitored, and the assigned bandwidths may
`
`
`
`
`
`
`
`
`
`be altered to reflect the usage.
`
`
`
`
`
`
`There is therefore provided, according to an embodiment
`
`
`
`
`
`
`
`
`of the present invention, a method for assigning bandwidth
`
`
`
`
`
`
`
`
`
`in a network including nodes coupled by links arranged in a
`
`
`
`
`
`
`
`
`
`
`
`physical topology, the method including:
`
`
`
`
`
`defining between the nodes logical connections associated
`
`
`
`
`
`
`
`with a data transmission service to be provided over the
`
`
`
`
`
`
`
`
`
`
`network, the logical connections having a connection topol-
`
`
`
`
`
`
`
`ogy different from the physical topology;
`
`
`
`
`
`
`determining respective bandwidth requirements for the
`
`
`
`
`
`
`logical connections based on parameters of the service;
`
`
`
`
`
`
`
`
`mapping the connection topologyto the physical topol-
`
`
`
`
`
`
`
`ogy, so that each of the logical connections is associated
`
`
`
`
`
`
`
`
`
`
`with one or more links of the physical topology; and
`
`
`
`
`
`
`
`
`
`
`allocating a bandwidth for the service on eachofthelinks
`
`
`
`
`
`
`
`
`
`
`
`in response to the bandwidth requirements of the logical
`
`
`
`
`
`
`
`
`
`comections and to the mapping.
`
`
`
`
`
`
`UNIFIED PATENTS EXHIBIT 1001
`Page 7 of 15
`
`
`
`
`
`
`
`
`
`
`
`
`
`Packet ring networks are typically significantly easier to
`
`
`
`
`
`
`
`
`operate and administer than complex mesh or irregular
`
`
`
`
`
`
`
`
`networks, and a ring network mayalso allow for failure of
`
`
`
`
`
`
`
`
`
`
`
`a link between nodes of the network, if the network is
`
`
`
`
`
`
`
`
`
`
`
`bi-directional. The leading bi-directional protocol for high
`
`
`
`
`
`
`
`speed packet rings is the Resilient Packet Ring (RPR)
`
`
`
`
`
`
`
`
`
`protocol, defined by IEEE Standard 802.17.
`
`
`
`
`
`
`wycS
`If services provided by the ring network do not require 32
`
`
`
`
`
`
`
`
`
`
`guaranteed bandwidth, all nodes (termed stations in RPR)
`
`
`
`
`
`
`
`
`
`operating in the ring may use a “Best Effort” approach to
`
`
`
`
`
`
`
`
`
`
`
`transfer packets. To meet guarantee needs, however, RPR
`
`
`
`
`
`
`
`
`allocates guaranteed bandwidthfor class A traffic and some
`
`
`
`
`
`
`
`
`
`class B traffic. (RPR defines three classes of traffic: class A,
`
`
`
`
`
`
`
`
`
`
`
`class B, and class C. Class A is a low latency, low jitter
`
`
`
`
`
`
`
`
`
`
`
`
`
`class.) Class AO is a subdivision of class A. The bandwidth
`
`
`
`
`
`
`
`
`
`
`
`of a class AO traffic reservation may only be used by the
`
`
`
`
`
`
`
`
`
`
`
`
`station holding the reservation, and any such reserved band-
`
`
`
`
`
`
`
`
`width that is unused is wasted.
`
`
`
`
`
`
`At initiation of an RPR network a station on the RPR
`
`
`
`
`
`
`
`
`
`
`
`network broadcasts reservation requests for its class AQ
`
`
`
`
`
`
`
`
`traffic using topology messages (which are also used for
`
`
`
`
`
`
`
`
`
`stations to notify each other of their existence and position
`
`
`
`
`
`
`
`
`
`
`in the ring). The reservations are typically determined. by
`
`
`
`
`
`
`
`
`
`Service Level Agreements (SLAs) between users and an
`
`
`
`
`
`
`
`
`operator of the ring. A Connection Admission Controller
`
`
`
`
`
`
`
`
`(CAC) in the network allocates bandwidth according to the
`
`
`
`
`
`
`
`
`
`received requests, and all stations on the RPR are informed
`
`
`
`
`
`
`
`
`
`
`of the allocation. For any new service, the CAC must know
`
`
`
`
`
`
`
`
`
`
`
`how much bandwidth has been consumed, and how much is
`
`
`
`
`
`
`
`
`
`
`required by the new service, to verify that the new service
`
`
`
`
`
`
`
`
`
`
`
`can be provisioned according to the new service’s SLA. In
`
`
`
`
`
`
`
`
`
`
`addition, and regardless of the class of traffic, it may be
`
`
`
`
`
`
`
`
`
`
`
`necessary to reserve some bandwidth to avoid traffic star-
`
`
`
`
`
`
`
`
`vation.
`
`
`=)a
`2
`
`30
`
`35
`
`40
`
`
`45
`
`
`
`SUMMARY OF TITLE INVENTION
`
`
`
`
`
`
`
`
`
`
`
`
` n a ring network, bandwidth allocation for guaranteed 5
`
`
`
`
`
`
`
`
`
`
`point-to-pointtraffic can be estimated based on parameters
`
`
`
`
`
`
`
`
`suchas interface type, user requirements, and the path on the
`
`
`
`
`
`
`
`
`
`
`
`
`ring between the two end points. Furthermore, for this
`
`
`
`
`
`
`
`
`
`traffic, the bandwidth consumed by cach link intervening
`
`
`
`
`
`
`
`
`between a start point and an end point on the ring is equal
`
`
`
`
`
`
`
`
`
`
`
`
`
`to the bandwidth required at the start and end points. Thus,
`
`
`
`
`
`
`
`
`
`
`
`for guaranteed point-to-point
`traffic, actual bandwidth
`
`
`
`
`
`
`needed for each link between stations on the ring can be well
`
`
`
`
`
`
`
`
`
`
`
`
`estimated.
`
`
`On the other hand, for guaranteed point-to-multipoint
`
`
`
`
`
`
`
`
`traffic and guaranteed multipoint-to-multipoint traffic, good
`
`
`
`
`
`
`
`
`
`estimation of actual bandwidth needs is difficult. Point-to-
`
`
`
`
`
`
`
`
`
`=e
`
`
`multipoint traffic is characteristic, for example, of Video On
`
`
`
`
`
`
`
`
`
`Demand Service (VODS), while multipoint-to-multipoint
`
`
`
`
`
`traffic is typical in Virtual Private LAN Service (VPLS). In
`
`
`
`
`
`
`
`
`
`
`both of these types of traflic there are multiple paths between
`
`
`
`
`
`
`
`
`
`
`
`the start and the end points, and guaranteed bandwidthis
`
`
`
`
`
`
`
`
`
`
`
`5
`
`
`
`
`
`
`
`
`
`UNIFIED PATENTS EXHIBIT 1001
`Page 7 of 15
`
`

`

`
`
`US 7,330,431 B2
`
`
`
`
`
`0
`
`
`
`a 5
`
`
`
`
`
`
`
`30
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`65
`
`
`
`
`
`4
`3
`In an embodiment,thefirst connection topologyincludes
`Typically, the network includes a ring network, the physi-
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`a hub-and-spoke topology and the second connection topol-
`cal topology includes a ring topology, and the connection
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`ogyincludes a full mesh topology.
`topology is chosen from one of a hub-and-spoke topology
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`In a disclosed embodiment, at least one of the first and
`and a full mesh topology.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`In an embodiment, the data transmission service includes
`second data transmission services includes a guaranteed
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`bandwidth service and/or a class of service defined by a
`a guaranteed bandwidth service, and may include a class of
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`protocol under which the network operates.
`service defined by a protocol under which the network
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`operates.
`The method typically includes multiplying at least one of
`
`
`
`
`
`
`
`
`
`
`Tn an alternative embodiment, the method includes mul-
`the first and second bandwidths by a correction factor to
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`determine a corrected bandwidth.
`tiplying the bandwidth bya correction factor to determine an
`
`
`
`
`
`
`
`
`
`
`
`
`
`actual bandwidth.
`In one embodiment, generating the first mapping includes
`
`
`
`
`
`
`
`
`
`
`generating a first bandwidth requirement for each of the
`In a disclosed embodiment, mapping the connection
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`links, and generating the second mapping includes generat-
`topology to the physical
`topology includes generating a
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`ing a second bandwidth requirement for cach of the links.
`bandwidth requirement for cach of the links.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Typically, the first parameters of the first service include
`Typically, parameters of the service include respective
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`respective first node-bandwidths required by each of the
`node-bandwidths required by each of the nodes to provide
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`the service.
`nodesto providethefirst service, and the second parameters
`
`
`
`
`
`
`
`
`
`
`
`
`of the second service include respective second node-band-
`The method may include monitoring traffic generated in
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`widths required by each of the nodes to provide the second
`the network by the data transmission service, and adjusting
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`service.
`the bandwidth in responseto the traffic.
`
`
`
`
`
`
`
`
`In one embodiment,
`the data transmission service
`The method typically includes monitoring traffic gener-
`
`
`
`
`
`
`
`
`
`
`
`
`
`ated in the network bythefirst and second data transmission
`includesa plurality of subclasses oftraffic, and allocating the
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`services, and adjusting the total allocation in response to the
`bandwidth includes allocating a reserved bandwidth to one
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`traffic.
`of the subclasses, and/or comparing a mapping bandwidth
`
`
`
`
`
`
`
`
`
`i]a
`In an alternative embodiment. the first data transmission
`determinedin response to the bandwidth requirements of the :
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`service includes a plurality of subclasses oftraflic, and
`logical connections and to the mapping with a full band-
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`allocating the first bandwidth includesallocating a reserved
`width determined by assuming all possible logical connec-
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`bandwidth to one of the subclasses.
`tions in the network are provided for.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Typically, the first connection topology is di
`Thereis further provided, according to an embodiment of
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`the second connection topology.
`the present invention, a method for assigning, bandwidth in
`
`
`
`
`
`
`
`
`
`
`
`
`
`In a further alternative embodiment, summingthefirst
`a network including nodes coupled by links arranged in a
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`and the second bandwidths to determineatotal allocation for
`physical topology, the method including:
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`each of the links includes:
`defining between the nodesa first set of logical connec-
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`tions associated with a first data transmission service to be
`determining a first mapping bandwidth in response to the
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`provided over the network, and a second set of logical
`first bandwidth requirements of the first set of logical
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`connections associated with a second data transmission
`connections and. to the first mapping;
`
`
`
`
`
`
`
`
`
`
`
`
`
`service to be provided over the network, the first sct of
`determining a second mapping bandwidth in response to
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`logical connections having a first connection topology, the
`the second bandwidth requirements of the second set of
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`second set of logical connections having a second connec-
`logical connections and to the second mapping; and
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`tion topology, the first and second connection topologies
`comparing the first mapping bandwidth and the second
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`being different from the physical topology;
`mapping bandwidth with a full bandwidth determined by
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`determining respective first bandwidth requirements for
`assumingall possible logical connections in the network are
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`the first set of logical connections based on first parameters
`provided for.
`
`
`
`
`
`
`
`
`
`
`
`
`of the first data transmission service and respective second
`There is further provided, according, to an embodiment of
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`bandwidth requirements for the second. set of logical con-
`the present invention, a method for assigning bandwidth in
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`nections based on second parameters of the second data
`a ring network including nodes coupled by links, the method
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`transmission service;
`including:
`
`
`
`generating a first mappingof the first connection topology
`defining between the nodesa first set of logical connec-
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`tions associated with a first data transmission service to be
`to the physical topology, so that eachofthefirst set of logical
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`i2
`connections is associated with one or more links of the 5
`provided over the network, and a second set of logical
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`comnections associated with a second data transmission
`physical topology;
`
`
`
`
`
`
`
`
`
`allocating a first bandwidth for the first data transmission
`service to be provided over the network, the first set of
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`service on eachofthe links in responseto thefirst bandwidth
`logical connections having a hub-and-spokes connection
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`requirementsofthe first set of logical connections and to the
`topology, the secondset of logical connections having a full
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`first mapping;
`mesh connection topology;
`
`
`
`
`
`generating a second mapping of the second connection
`determining respective first bandwidth requirements for
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`topology to the physical topology, so that each of the second
`the first set of logical connections based on first parameters
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`set of logical connections is associated with one or more
`ofthe first data transmission service and respective second
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`links of the physical topology;
`bandwidth requirements for the second set of logical con-
`
`
`
`
`
`
`
`
`
`
`
`
`
`allocating a second bandwidth for the second data trans-
`nections based on second parameters of the second data
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`transmission service:
`mission service on each of the links in response to the
`
`
`
`
`
`
`
`
`
`
`
`
`
`second bandwidth requirements of the second set of logical
`generating a first mappingofthefirst connection topology
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`connections and to the second mapping; and
`to the ring network, so that each of the first set of logical
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`summingthefirst and the second bandwidths to determine
`connections is associated with one or more links of the ring
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`a total allocation for each ofthelinks.
`network;
`
`
`
`
`
`
`
`
`
`Typically, the network includes a ring network, and the
`determining a first bandwidth for the first data transmis-
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`physical topologyincludes a ring topology.
`sion service on each ofthe links in response to the first
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
` erent from
`
`
`
`
`
`
`
`
`UNIFIED PATENTS EXHIBIT 1001
`Page 8 of 15
`
`UNIFIED PATENTS EXHIBIT 1001
`Page 8 of 15
`
`

`

`
`6
`set of logical connections is associated with one or more
`
`
`
`
`
`
`
`
`
`
`links of the physical topology,
`
`
`
`
`
`allocate a second bandwidth for the second data trans-
`
`
`
`
`
`
`
`
`mission service on each of the links in response to the
`
`
`
`
`
`
`
`
`
`
`
`second bandwidth requirements of the second set of logical
`
`
`
`
`
`
`
`
`
`connections and to the second mapping, and
`
`
`
`
`
`
`
`sum the first and the second bandwidths to determine a
`
`
`
`
`
`
`
`
`
`total allocation for each ofthe links.
`
`
`
`
`
`
`
`Typically,
`the controller is in one of the nodes or is
`
`
`
`
`
`
`
`
`
`
`external to the network.
`
`
`
`
`The present invention will be more fully understood from
`
`
`
`
`
`
`
`
`
`the following detailed description of the preferred embodi-
`
`
`
`
`
`
`
`ments thereof,
`taken together with the drawings, a brief
`
`
`
`
`
`
`
`
`
`description of which follows.
`
`
`
`
`BRILI DESCRIPTION OF TITE DRAWINGS
`
`
`
`
`
`
`
`
`
`
`
`
`FIG. 1 is a schematic representation of a data communi-
`
`
`
`
`
`
`
`
`
`calion system, according to an embodiment of the present
`
`
`
`
`
`
`
`
`
`invention;
`
`FIG.2 is a flow chart showing steps of a process applied
`
`
`
`
`
`
`
`
`
`
`
`
`by a Connection Admission Controller (CAC)in allocating
`
`
`
`
`
`
`
`
`bandwidths to links in the system of FIG. 1, according to an
`
`
`
`
`
`
`
`
`
`
`
`
`embodiment of the present invention;
`
`
`
`
`
`VIG. 3 is a schematic illustration of a first example of the
`
`
`
`
`
`
`
`
`
`
`
`process of FIG. 2, according to an embodiment of the
`
`
`
`
`
`
`
`
`
`
`present invention;
`
`
`FIG.4 is a schematic illustration of a second example of
`
`
`
`
`
`
`
`
`
`
`
`the process of FIG. 2, according to an embodiment ofthe
`
`
`
`
`
`
`
`
`
`
`
`present invention; and
`
`
`
`FIG. 5 is a flow chart showing an automatic management
`
`
`
`
`
`
`
`
`
`
`process performed by a manager node during operation of
`
`
`
`
`
`
`
`
`
`the system of FIG. 1, according to an embodiment of the
`
`
`
`
`
`
`
`
`
`
`
`present invention.
`
`
`
`
`DETAIL ED DESCRIPTION OF EMBODIMENTS
`
`
`
`
`
`
`5
`bandwidth requirements of the first set of logical connec-
`
`
`
`
`
`
`
`
`tions and to the first mapping;
`
`
`
`
`
`
`generating a second mapping of the second connection
`
`
`
`
`
`
`
`
`topology to the ring topology, so that each of the second set
`
`
`
`
`
`
`
`
`
`
`
`
`of logical connections is associated with one or more links
`
`
`
`
`
`
`
`
`
`
`of the ring network;
`
`
`
`
`determining a second bandwidth for the second data
`
`
`
`
`
`
`
`
`transmission service on each ofthe links in response to the
`
`
`
`
`
`
`
`
`
`
`
`second bandwidth requirements of the second set of logical
`
`
`
`
`
`
`
`
`
`connections and to the second mapping;
`
`
`
`
`
`
`summingthefirst and the second bandwidthsto determine
`
`
`
`
`
`
`
`
`
`a total bandwidth for each of the links; and
`
`
`
`
`
`
`
`
`
`allocating one ofthe first bandwidth, the second band-
`
`
`
`
`
`
`
`
`width, and the total bandwidth to cach of the links in
`
`
`
`
`
`
`
`
`
`
`
`response to respectively providing the first service,
`the
`
`
`
`
`
`
`
`
`second service, and both services, over the network.
`
`
`
`
`
`
`
`
`There is further provided, according to an embodiment of
`
`
`
`
`
`
`
`
`
`the present invention, apparatus for assigning bandwidth in
`
`
`
`
`
`
`
`
`a network including nodes coupled by links arranged in a
`
`
`
`
`
`
`
`
`
`
`physical topology, the apparatus including:
`
`
`
`
`
`a controller which is adapted to:
`
`
`
`
`
`
`receive a definition of logical connections between the
`
`
`
`
`
`
`
`
`nodes, the logical connections being associated with a data
`
`
`
`
`
`
`
`
`
`transmission service to be provided over the network, the
`
`
`
`
`
`
`
`
`
`logical connections having a connection topology different
`
`
`
`
`
`
`
`from the physical topology,
`
`
`
`
`determine respective bandwidth requirements for the logi-
`
`
`
`
`
`
`cal connections based on parameters of the service,
`
`
`
`
`
`
`
`
`map the connection topology to the physical topology, so
`
`
`
`
`
`
`
`
`
`that eachof the logical connectionsis associated with one or
`
`
`
`
`
`
`
`
`
`
`
`more links of the physical topology, and
`
`
`
`
`
`
`
`allocate a bandwidth for the service on each ofthe links
`
`
`
`
`
`
`
`
`
`
`
`in response to the bandwidth requirements of the logical
`
`
`
`
`
`
`
`
`
`connections and to the mapping.
`
`
`
`
`
`Typically, the controller is included in one ofthe nodes or
`
`
`
`
`
`
`
`
`
`
`
`is external to the network.
`
`
`
`
`
`Thereis further provided, according to an embodiment of
`
`
`
`
`
`
`
`
`
`Reference is now made to FIG. 1, which is a schematic
`
`
`
`
`
`
`
`
`
`
`
`the present invention, apparatus for assigning bandwidth in
`
`
`
`
`
`
`
`
`representation of a data communication system 10, accord-
`
`
`
`
`
`
`
`a network including nodes coupled by links arranged in a
`
`
`
`
`
`
`
`
`
`
`ing to an embodimentofthe present invention. System 10 is
`
`
`
`
`
`
`
`
`
`
`
`physical topology, the apparatus including:
`
`
`
`
`
`built around a high-speed ring network 12, such as aSONET
`
`
`
`
`
`
`
`
`
`
`
`a controller which is adapted to:
`
`
`
`
`
`
`or SDH network, having data nodes 14, also herein termed
`
`
`
`
`
`
`
`
`
`
`receive a definition of a first set of logical connections,
`
`
`
`
`
`
`
`
`
`
`between the nodes, associated with a first data transmission
`nodes A, B, C, D. Each pair of nodes is connected by a
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`physical network link 16, which typically comprises a pair
`
`
`
`
`
`
`
`
`
`service to be provided over the network, and a secondset of
`
`
`
`
`
`
`
`
`
`
`
`
`
`of wired, fiberopti