I 1111111111111111 11111 1111111111 1111111111 111111111111111 IIIIII IIII IIII IIII
`US007330431B2
`
`c12) United States Patent
`Bruckman
`
`(IO) Patent No.:
`(45) Date of Patent:
`
`US 7,330,431 B2
`Feb.12,2008
`
`( 54) MULTIPOINT TO MULTIPOINT
`COMMUNICATION OVER RING
`TOPOLOGIES
`
`(75)
`
`Inventor: Leon Bruckman, Petah Tikva (IL)
`
`(73) Assignee: Corrigent Systems Ltd., Tel Aviv (IL)
`
`( *) Notice:
`
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 700 days.
`
`(21) Appl. No.: 10/933,572
`
`(22) Filed:
`
`Sep. 3, 2004
`
`(65)
`
`Prior Publication Data
`
`US 2006/0050665 Al Mar. 9, 2006
`
`(51)
`
`Int. Cl.
`(2006.01)
`H04L 12126
`(52) U.S. Cl. ....................... 370/232; 370/231; 370/235
`(58) Field of Classification Search ........ 370/229-235,
`370/237-238, 395.2-395.21
`See application file for complete search history.
`
`(56)
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`5,235,593 A
`8/1993 Grow et al.
`10/1995 Drake et al.
`5,461,611 A
`5,581,703 A
`12/1996 Baugher et al.
`5,706,516 A
`1/1998 Chang et al.
`5,854,903 A * 12/1998 Morrison et al.
`5,933,422 A
`8/1999 Kusano et al.
`6,021,263 A
`2/2000 Kujoory et al.
`6,157,654 A
`12/2000 Davis
`6,169,783 Bl
`1/2001 Brooks et al.
`6,256,292 Bl
`7/2001 Ellis et al.
`6,262,976 Bl
`7/2001 McNamara
`6,339,488 Bl
`1/2002 Beshai et al.
`6,370,121 Bl
`4/2002 Hausman
`6,400,681 Bl
`6/2002 Bertin et al.
`
`........... 709/249
`
`6,442,134 Bl
`6,456,407 Bl
`6,486,988 Bl
`6,507,577 Bl
`6,510,141 Bl
`6,522,627 Bl
`6,560,231 Bl
`6,580,693 Bl *
`6,584,535 Bl
`6,624,917 Bl
`
`8/2002 Mitchell
`9/2002 Tammela et al.
`11/2002 Lewis et al.
`. ............ 370/356
`1/2003 Mauger et al.
`1/2003 Ramfelt et al. ............. 370/254
`2/2003 Mauger ...................... 370/230
`5/2003 Kawakami et al.
`6/2003 Chernyak et al. ........... 370/248
`6/2003 Ouellet et al.
`9/2003 Paschal et al.
`
`(Continued)
`
`OTHER PUBLICATIONS
`
`Moy, "OSPF", Version 2, published as Request for Conunents
`(RFC) 2328 of the 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,
`Gagnebin & Lebovici LLP
`
`Schurgin,
`
`(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(cid:173)
`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 of the service. The
`method further includes mapping the connection topology to
`the physical topology, 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 each of the
`links in response to the bandwidth requirements of the
`logical connections and to the mapping.
`
`30 Claims, 4 Drawing Sheets
`
`MAP LOGICAL TOPOLOGY TO PHYSICAL TOPOLOGY
`TO DETERMINE LlNKS USED
`
`SUM BANDWIDTH REQUIREMENTS OF EACH LlNK
`TO DETERMINE MAPPING BANDWIDTH
`
`50
`
`N
`
`52
`
`54
`
`NO
`
`58
`
`ACTUAL BANDWIDTH=
`MAPPING BANDWIDTH x DP
`
`Ex.1001
`CISCO SYSTEMS, INC. / Page 1 of 15
`
`

`

`US 7,330,431 B2
`Page 2
`
`U.S. PATENT DOCUMENTS
`
`6,625,155 Bl
`6,639,893 Bl
`6,639,896 Bl
`6,647,008 Bl
`6,678,241 Bl
`6,680,912 Bl
`6,711,125 Bl
`6,731,597 Bl
`6,757,286 Bl
`6,763,025 B2
`6,778,494 Bl
`6,795,394 Bl
`6,801,506 Bl
`6,820,210 Bl
`6,826,147 Bl
`6,826,158 B2
`6,922,394 B2
`6,934,259 B2
`6,952,397 B2
`6,965,612 B2
`6,992,975 Bl
`7,035,279 B2
`7,042,846 B2
`7,058,008 Bl
`7,158,486 B2
`7,161,899 B2
`7,184,402 Bl
`2002/01337 56 Al *
`2002/0181479 Al
`2002/0186661 Al
`2003/0002443 Al
`2003/0055920 Al
`2003/0145108 Al
`2003/0158930 Al
`2003/0223428 Al
`2004/0052274 Al
`
`9/2003 Dziong
`10/2003 Chikenji et al.
`10/2003 Goode et al.
`11/2003 Galand et al.
`1/2004 Gai et al.
`1/2004 Kalman et al.
`3/2004 Walrand et al.
`5/2004 Batchellor et al.
`6/2004 Stone
`7 /2004 Leatherbury et al.
`8/2004 Mauger ...................... 370/230
`9/2004 Swinkels et al.
`10/2004 Dey
`11/2004 Daruwalla et al.
`11/2004 Nandy et al.
`11/2004 Seaman et al.
`7/2005 Kajiwara
`8/2005 Klincewicz et al.
`10/2005 Mor et al ................... 370/223
`11/2005 Chohan et al.
`1/2006 Daniel et al. ............... 370/222
`4/2006 Bruckman .................. 370/460
`5/2006 Bauer
`6/2006 Wilson et al.
`1/2007 Rhodes
`1/2007 Limaye et al.
`2/2007 Sharma et al.
`.. ... ... ... .. ... ... ... ... .. . 714/43
`9/2002 Jain
`12/2002 Okuno
`12/2002 Santiago et al.
`1/2003 Basso et al.
`3/2003 Kakadia et al.
`7 /2003 Joseph et al.
`8/2003 Mc Bride
`12/2003 Blanquer et al.
`3/2004 Wang et al.
`
`2004/0071089 Al
`2004/0076176 Al
`2004/0105459 Al
`2005/0030948 Al
`
`4/2004 Bauer et al.
`4/2004 Kfir
`6/2004 Mannam
`2/2005 Wyatt
`
`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. Tsiang et al., Request for Comments (RFC) 2892 of the Internet
`Engineering Task Force (IETF), Aug. 2000.
`.
`Braden, et al., in IETF RFC 2205, "Resource ReServatJon Protocol
`(RSVP)-Version 1 Functional Specification", Sep. 1997.
`Andersson, et al., in IETF RFC 3036, "LDP Specification" Jan.
`2001.
`Yavatkar et al., RFC 2814 "A Protocol for RSVP-Based Admis(cid:173)
`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/Israeli 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 dunng 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/
`ACM transactions 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 Task Force, www.ietf.org, Aug. 1996.
`
`* cited by examiner
`
`Ex.1001
`CISCO SYSTEMS, INC. / Page 2 of 15
`
`

`

`U.S. Patent
`
`Feb.12,2008
`
`Sheet 1 of 4
`
`US 7,330,431 B2
`
`14
`
`14
`
`I
`I
`
`I
`
`I FIG. 1
`~16
`I
`I
`
`18
`
`I
`I
`I
`I
`I
`I 20
`I
`I
`
`I
`I
`I 18
`I
`16~ 20
`I
`I
`I
`
`14
`
`20
`
`-----------
`20
`18
`----z._ ------
`22
`16
`\
`10
`
`19 12
`/
`16
`/
`~---,_--~-----------~
`20
`18
`B
`A
`-----------
`\
`
`C
`
`14
`
`BCM
`
`28
`
`FIG. 2
`
`START
`
`MAP LOGICAL TOPOLOGY TO PHYSICAL TOPOLOGY
`TO DETERMINE LINKS USED
`
`SUM BANDWIDTH REQUIREMENTS OF EACH LINK
`TO DETERMINE MAPPING BANDWIDTH
`
`50
`
`/V
`
`52
`
`54
`
`NO
`
`--r58
`
`ACTUAL BANDWIDTH=
`ACTUAL BANDWIDTH=
`MAPPING BANDWIDTH MAPPING BANDWIDTH x DP
`
`END
`
`Ex.1001
`CISCO SYSTEMS, INC. / Page 3 of 15
`
`

`

`"'""' = N
`= ~ w
`
`w
`w
`'-"--...l
`
`d r.,;_
`
`....
`0
`N
`.....
`=- ('D
`
`('D
`
`rJJ
`
`.i;...
`
`QO
`0
`0
`N
`j'-J
`....
`?'
`('D
`"f'j
`
`~ = ~
`
`~
`~
`~
`•
`00
`
`e •
`
`j~
`
`C
`
`D
`
`"21
`l I >
`
`B
`
`c:-C
`
`D
`
`j
`
`A -.::::i
`
`EB
`
`RESULT
`
`66
`
`PHYSICAL
`
`63
`
`> 17
`
`C
`
`c::,.,-B
`
`RESULT
`
`D
`
`A
`
`64
`
`PHYSICAL
`
`I
`
`"19
`!
`
`C
`
`c:,. B
`
`l
`
`D<::J
`
`A
`
`EB
`
`62
`
`/
`
`28
`
`60
`
`BASIC CONNECTMTY MAP
`
`DP = 10%
`
`R/
`
`B (R)I
`
`C(R)
`~
`R
`t
`A(3R)
`~ /
`R
`
`D~
`
`I
`
`LOGICAL
`
`FIG. 3
`
`Ex.1001
`CISCO SYSTEMS, INC. / Page 4 of 15
`
`

`

`~
`
`('D
`
`0 ....
`.....
`rJJ =- ('D
`
`.i;...
`
`QO
`0
`0
`N
`
`N
`....
`?'
`('D
`"f'j
`
`~
`
`~ = ~
`
`~
`~
`~
`•
`00
`
`e •
`
`"'""' = N
`~ w
`=
`-....l w w
`d r.,;_
`
`> !7LJ
`
`A~
`
`B
`
`RESULT
`
`76
`
`> 171
`
`~
`
`D -=:i
`
`-
`
`e>-B
`
`A
`
`I
`
`I
`
`RESULT
`
`74
`
`PHYSICAL
`
`72 I
`
`FIG. 4
`
`,21
`C
`1
`
`B
`
`!
`
`D
`
`A
`
`EB
`
`/
`
`28
`
`70..:::,
`
`BASIC CONNECTMTY MAP
`
`DP = 10%
`
`PHYSICAL
`
`63
`
`,19
`1 l
`
`C
`
`D -:::i
`
`C>-B
`
`A
`
`EB
`
`~B (R)
`3 \,,_
`1R
`
`D (R)-cl-½R
`
`~R
`
`/3
`lR
`
`LOGICAL
`
`'1 11/
`){\
`
`C (R)
`~/
`3R
`3R
`
`Ex.1001
`CISCO SYSTEMS, INC. / Page 5 of 15
`
`

`

`U.S. Patent
`
`Feb. 12, 2008
`
`Sheet 4 of 4
`
`US 7,330,431 B2
`
`80
`
`/V
`
`88
`
`SET ALARM
`
`82
`
`84
`
`NO
`
`NO
`
`FIG. 5
`
`MONITOR ACTUAL
`TRAFFIC
`
`DETERMINE CHANGES
`TO ALLOCATED
`BANDWIDTH
`
`YES
`
`YES
`
`MAKE CHANGES
`
`END
`
`Ex.1001
`CISCO SYSTEMS, INC. / 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 connnu(cid:173)
`nications within a network, and specifically to optimizing
`bandwidth allocation for the data in the network.
`
`BACKGROUND OF THE INVENTION
`
`2
`often required. Although estimation is difficult, it is neces(cid:173)
`sary in order for the CAC to be able to function.
`One method to allocate guaranteed bandwidth in multi(cid:173)
`point cases is to allocate the full required bandwidth for all
`5 possible paths that packets may travel. In this case there will
`always be sufficient bandwidth, at the expense of large
`guaranteed bandwidth wastage. Embodiments of the present
`invention provide methods and systems for bandwidth allo(cid:173)
`cation that make more efficient use of the guaranteed band-
`10 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(cid:173)
`mission services operate between the nodes. Each service
`15 has a logical connection topology that may be different from
`the physical topology. The service parameters for each
`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
`20 maps the logical connections in the logical connection
`topology of the service to corresponding physical links in
`the physical topology. The controller determines how the
`bandwidth of each participating node is to be distributed
`among the logical connections in the logical topology, and
`25 then generates an actual bandwidth requirement for each of
`the physical links, based on the mapping.
`Typically, the logical connection topology for each ser(cid:173)
`vice is chosen from a number of different logical connection
`topologies, such as a hub and spoke topology and a full mesh
`30 topology, depending on the nature of the service (such as
`VODS or VPLS). Assigning the actual bandwidths of the
`links in a physical network according to the logical connec(cid:173)
`tivity of nodes in services carried by the network is a simple
`and effective way to allocate bandwidth correctly and effi-
`35 ciently, particularly guaranteed bandwidth.
`In some embodiments, at least some of the actual band(cid:173)
`widths are multiplied by a correction factor, typically the
`same for each of the 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(cid:173)
`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
`45 mapping each of the respective logical topologies to the
`physical topology of the network, and then adding up the
`bandwidths required by all the services on each of the links.
`Typically, during operation of the network, actual band(cid:173)
`width usage is monitored, and the assigned bandwidths may
`50 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(cid:173)
`ogy different from the physical topology;
`determining respective bandwidth requirements for the
`logical connections based on parameters of the service;
`mapping the connection topology to the physical topol(cid:173)
`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 each of the links
`in response to the bandwidth requirements of the logical
`connections and to the mapping.
`
`Packet ring networks are typically significantly easier to
`operate and administer than complex mesh or irregular
`networks, and a ring network may also 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.
`If services provided by the ring network do not require
`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 bandwidth for 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(cid:173)
`width that is unused is wasted.
`At initiation of an RPR network a station on the RPR
`network broadcasts reservation requests for its class AO
`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 40
`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.
`
`SUMMARY OF THE INVENTION
`
`In a ring network, bandwidth allocation for guaranteed
`point-to-point traffic can be estimated based on parameters
`such as interface type, user requirements, and the path on the
`ring between the two end points. Furthermore, for this
`traffic, the bandwidth consumed by each 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 60
`traffic and guaranteed multipoint-to-multipoint traffic, good
`estimation of actual bandwidth needs is difficult. Point-to(cid:173)
`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 65
`both of these types of traffic there are multiple paths between
`the start and the end points, and guaranteed bandwidth is
`
`55
`
`Ex.1001
`CISCO SYSTEMS, INC. / Page 7 of 15
`
`

`

`US 7,330,431 B2
`
`3
`Typically, the network includes a ring network, the physi(cid:173)
`cal topology includes a ring topology, and the connection
`topology is chosen from one of a hub-and-spoke topology
`and a full mesh topology.
`In an embodiment, the data transmission service includes
`a guaranteed bandwidth service, and may include a class of
`service defined by a protocol under which the network
`operates.
`In an alternative embodiment, the method includes mul(cid:173)
`tiplying the bandwidth by a correction factor to determine an
`actual bandwidth.
`In a disclosed embodiment, mapping the connection
`topology to the physical topology includes generating a
`bandwidth requirement for each of the links.
`Typically, parameters of the service include respective
`node-bandwidths required by each of the nodes to provide
`the service.
`The method may include monitoring traffic generated in
`the network by the data transmission service, and adjusting
`the bandwidth in response to the traffic.
`In one embodiment,
`the data
`transmission service
`includes a plurality of subclasses of traffic, and allocating the
`bandwidth includes allocating a reserved bandwidth to one
`of the subclasses, and/or comparing a mapping bandwidth
`determined in response to the bandwidth requirements of the 25
`logical connections and to the mapping with a full band(cid:173)
`width determined by assuming all possible logical connec(cid:173)
`tions in the network are provided for.
`There is further provided, according to an embodiment of
`the present invention, a method for assigning bandwidth in 30
`a network including nodes coupled by links arranged in a
`physical topology, the method including:
`defining between the nodes a first set of logical connec(cid:173)
`tions associated with a first data transmission service to be
`provided over the network, and a second set of logical 35
`connections associated with a second data transmission
`service to be provided over the network, the first set of
`logical connections having a first connection topology, the
`second set of logical connections having a second connec(cid:173)
`tion topology, the first and second connection topologies 40
`being different from the physical topology;
`determining respective first bandwidth requirements for
`the first set of logical connections based on first parameters
`of the first data transmission service and respective second
`bandwidth requirements for the second set of logical con- 45
`nections based on second parameters of the second data
`transmission service;
`generating a first mapping of the first connection topology
`to the physical topology, so that each of the first set oflogical
`connections is associated with one or more links of the
`physical topology;
`allocating a first bandwidth for the first data transmission
`service on each of the links in response to the first bandwidth
`requirements of the first set oflogical connections and to the
`first mapping;
`generating a second mapping of the second connection
`topology to the physical topology, so that each of the second
`set of logical connections is associated with one or more
`links of the physical topology;
`allocating a second bandwidth for the second data trans(cid:173)
`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
`summing the first and the second bandwidths to determine
`a total allocation for each of the links.
`Typically, the network includes a ring network, and the
`physical topology includes a ring topology.
`
`4
`In an embodiment, the first connection topology includes
`a hub-and-spoke topology and the second connection topol(cid:173)
`ogy includes a full mesh topology.
`In a disclosed embodiment, at least one of the first and
`5 second data transmission services includes a guaranteed
`bandwidth service and/or a class of service defined by a
`protocol under which the network operates.
`The method typically includes multiplying at least one of
`the first and second bandwidths by a correction factor to
`10 determine a corrected bandwidth.
`In one embodiment, generating the first mapping includes
`generating a first bandwidth requirement for each of the
`links, and generating the second mapping includes generat(cid:173)
`ing a second bandwidth requirement for each of the links.
`15 Typically, the first parameters of the first service include
`respective first node-bandwidths required by each of the
`nodes to provide the first service, and the second parameters
`of the second service include respective second node-band(cid:173)
`widths required by each of the nodes to provide the second
`20 service.
`The method typically includes monitoring traffic gener(cid:173)
`ated in the network by the first and second data transmission
`services, and adjusting the total allocation in response to the
`traffic.
`In an alternative embodiment, the first data transmission
`service includes a plurality of subclasses of traffic, and
`allocating the first bandwidth includes allocating a reserved
`bandwidth to one of the subclasses.
`Typically, the first connection topology is different from
`the second connection topology.
`In a further alternative embodiment, summing the first
`and the second bandwidths to determine a total allocation for
`each of the links includes:
`determining a first mapping bandwidth in response to the
`first bandwidth requirements of the first set of logical
`connections and to the first mapping;
`determining a second mapping bandwidth in response to
`the second bandwidth requirements of the second set of
`logical connections and to the second mapping; and
`comparing the first mapping bandwidth and the second
`mapping bandwidth with a full bandwidth determined by
`assuming all possible logical connections in the network are
`provided for.
`There is further provided, according to an embodiment of
`the present invention, a method for assigning bandwidth in
`a ring network including nodes coupled by links, the method
`including:
`defining between the nodes a first set of logical connec(cid:173)
`tions associated with a first data transmission service to be
`50 provided over the network, and a second set of logical
`connections associated with a second data transmission
`service to be provided over the network, the first set of
`logical connections having a hub-and-spokes connection
`topology, the second set oflogical connections having a full
`55 mesh connection topology;
`determining respective first bandwidth requirements for
`the first set of logical connections based on first parameters
`of the first data transmission service and respective second
`bandwidth requirements for the second set of logical con-
`60 nections based on second parameters of the second data
`transmission service;
`generating a first mapping of the first connection topology
`to the ring network, so that each of the first set of logical
`connections is associated with one or more links of the ring
`65 network;
`determining a first bandwidth for the first data transmis(cid:173)
`sion service on each of the links in response to the first
`
`Ex.1001
`CISCO SYSTEMS, INC. / Page 8 of 15
`
`

`

`US 7,330,431 B2
`
`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(cid:173)
`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 of the links.
`Typically, the controller is in one of the nodes or is
`10 external to the network.
`The present invention will be more fully understood from
`the following detailed description of the preferred embodi(cid:173)
`ments thereof, taken together with the drawings, a brief
`description of which follows.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`5
`bandwidth requirements of the first set of logical connec(cid:173)
`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 5
`of the ring network;
`determining a second bandwidth for the second data
`transmission 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;
`summing the first and the second bandwidths to determine
`a total bandwidth for each of the links; and
`allocating one of the first bandwidth, the second band(cid:173)
`width, and the total bandwidth to each of the links in
`response to respectively providing the first service, the 15
`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 25
`from the physical topology,
`determine respective bandwidth requirements for the logi(cid:173)
`cal connections based on parameters of the service,
`map the connection topology to the physical topology, so
`that each of the logical connections is associated with one or 30
`more links of the physical topology, and
`allocate a bandwidth for the service on each of the links
`in response to the bandwidth requirements of the logical
`connections and to the mapping.
`Typically, the controller is included in one of the nodes or 35
`is external to 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 a first set of logical connections,
`between the nodes, associated with a first data transmission
`service to be provided over the network, and a second set of
`logical connections, between the nodes, associated with a 45
`second data transmission service to be provided over the
`network, the first set of logical connections having a first
`connection topology, the second set of logical connections
`having a second connection topology, the first and second
`connection topologies being different from the physical 50
`topology,
`determine respective first bandwidth requirements for the
`first set of logical connections based on first parameters of
`the first data transmission service and respective second
`bandwidth requirements for the second set of logical con- 55
`nections based on second parameters of the second data
`transmission service,
`generate a first mapping of the first connection topology
`to the physical topology, so that each of the first set oflogical
`connections is associated with one or more links of the 60
`physical topology,
`allocate a first bandwidth for the first data transmission
`service on each of the links in response to the first bandwidth
`requirements of the first set oflogical connections and to the
`first mapping,
`generate a second mapping of the second connection
`topology to the physical topology, so that each of the second
`
`FIG. 1 is a schematic representation of a data communi(cid:173)
`cation system, according to an embodiment of the present
`20 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;
`FIG. 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 of the
`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.
`
`DETAILED DESCRIPTION OF EMBODIMENTS
`
`Reference is now made to FIG. 1, which is a schematic
`representation of a data communication system 10, accord-
`40 ing to an embodiment of the present invention. System 10 is
`built around a high-speed ring network 12, such as a SO NET
`or SDH network, having data nodes 14, also herein termed
`nodes A, B, C, D. Each pair of nodes is connected by a
`physical network link 16, which typically comprises a pair
`of wired, fiberoptic, and/or wireless links 18, 20, that are
`configured to carry data traffic in clockwise and counter-
`clockwise directions around the ring. Thus network 12
`comprises a clockwise network 19 and a counterclockwise
`network 21. One of the data nodes also serves as a manager
`node 22, comprising a connection admission controller
`(CAC) 24 which performs functions that are described
`hereinbelow. Alternatively, CAC 24 is implemented external
`to the network.
`The topology of network 12, as of networks 19 and 21, is
`shown here by way of example, to illustrate aspects of the
`present invention. It will be understood, however, that the
`present invention is in no way limited in its applicability to
`this topology, and may equally be applied to other network
`topologies, as well. It will also be understood that in the
`context of the present patent application and in the claims,
`the terms "clockwise" and "counterclockwise" are used
`arbitrarily to distinguish between two opposing directions of
`packet flow in a ring network. These terms are chosen solely
`for convenience of explanation, and do not necessarily bear
`65 any relation to the physical characteristics of the network.
`Network 12 serves as the infrastructure for a virtual
`packet communication network, such as a virtual private
`
`Ex.1001
`CISCO SYSTEMS, INC. / Page 9 of 15
`
`

`

`US 7,330,431 B2
`
`7
`LAN. For example, nodes 14 may be connected to external
`Ethernet networks (not shown in the figure), and may
`package the Ethernet packets in virtual-concatenated con(cid:173)
`tainers provided by network 12. Alternatively or addition(cid:173)
`ally, system 10 may be configured to support traffic of other 5
`types, in accordance with other protocols that are known in
`the art. Hereinbelow, by way of example, network 12 is
`assumed to be configured as a bi-directional Resilient Packet
`Ring (RPR) network, as defined by IEEE standard 802.17,
`wherein nodes are also referred to as stations and networks 10
`19 and 21 are referred to as ringlets 0 and 1.
`On setup of network 12, an operator of the network inputs
`a basic connectivity map (BCM) 28 to manager node 22. As
`explained below, BCM 28, also herein termed the applied
`BCM, is used to determine actual bandwidths that are to be 15
`applied to each of the links in network 12. The applied BCM
`is one of a number of different connectivity maps, each
`having a different logical topology and bandwidth relations,
`that the operator may input to node 22. Alternatively or
`additionally, more than one of the basic connectivity maps 20
`are stored in node 22, and the operator chooses one of the
`stored maps as the applied BCM. Each basic connectivity
`map comprises and defines a logical topology that connects
`nodes 14 of the network, required bandwidths for each of the
`nodes when operating in the logical topology, and a correc- 25
`tion parameter, herein termed a deviation parameter (DP),
`that is used to formulate the actual bandwidths used by each
`link.
`Except as stated below, the following description assumes
`that the bandwidths referred to are for traffic of a data 30
`transmission service requiring guaranteed bandwidths.
`FIG. 2 is a flow chart showing steps of a process 50
`applied by CAC 24 in allocating bandwidths to links 16 in
`network 12, according to an embodiment of the present
`invention. Examples of the application of process 50 are 35
`described in more detail below, with reference to FIGS. 3
`and 4.
`In a first step 52, CAC 24 maps the logical topology of the
`applied BCM to the existing physical topology of network
`12. Performing the mapping generates actual links 16 and 18 40
`used in network 12.
`In a step 54, for each of the links the bandwidth require(cid:173)
`ments are summed to determine a mapping bandwidth,
`described in more detail below.
`In a comparison step 56, the mapping bandwidths are
`compared with "full" bandwidths. In the specification and in
`the claims,