(12) United States Patent
`Zheng et al.
`
`I 1111111111111111 11111 111111111111111 lllll lllll lllll 111111111111111 11111111
`US006757247Bl
`
`(10) Patent No.:
`(45) Date of Patent:
`
`US 6,757,247 Bl
`Jun.29,2004
`
`(54) CIRCUIT AND METHOD FOR
`CONTROLLING VIRTUAL CONNECTIONS
`IN A RING NETWORK
`
`(75)
`
`Inventors: Dan Zheng, Plano, TX (US); Sheila C.
`Field, Frisco, TX (US)
`
`(73) Assignee: ADC Telecommunications, Inc., Eden
`Prairie, MN (US)
`
`( *) Notice:
`
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by O days.
`
`(21) Appl. No.: 09/026,729
`Feb. 20, 1998
`(22) Filed:
`
`(51)
`
`Int. Cl.7 ............................. H04L 12/26; H04J 3/22
`
`(52) U.S. Cl. ....................... 370/231; 370/403; 370/409;
`370/468
`
`(58) Field of Search ................................. 370/230, 232,
`370/234, 233, 254, 253, 395, 397, 409,
`403,404,405,406,431,442,443,459,
`460, 465, 468, 231, 395.2, 395.21
`
`(56)
`
`References Cited
`U.S. PATENT DOCUMENTS
`
`6/1987 Yanosy, Jr. et al. ........... 370/85
`4,677,611 A
`5,070,498 A * 12/1991 Kakuma et al.
`.............. 370/60
`5,280,475 A * 1/1994 Yanagi et al. ................. 370/60
`5,289,462 A * 2/1994 Ahmadi et al. ............ 370/60.1
`5,339,314 A * 8/1994 Tanaka et al.
`.............. 370/230
`5,347,511 A * 9/1994 Gun ............................ 370/54
`5,390,164 A
`2/1995 Kremer ..................... 370/16.1
`5,394,389 A
`2/1995 Kremer ..................... 370/16.1
`5,412,652 A * 5/1995 Lu .......................... 370/85.12
`5,457,687 A * 10/1995 Newman ................... 370/85.3
`5,490,138 A * 2/1996 Niestegge et al.
`............ 370/56
`5,502,816 A * 3/1996 Gawlick et al.
`....... 395/200.15
`5,515,363 A * 5/1996 Ben-Nun et al.
`............. 370/17
`5,537,411 A
`7/1996 Plas .......................... 370/85.1
`5,557,611 A * 9/1996 Cappellari et al. ......... 370/60.1
`5,583,849 A
`12/1996 Ziemann et al. ............ 370/397
`5,612,959 A
`3/1997 Takase et al. ............... 370/390
`
`5,636,215 A
`5,673,262 A
`
`6/1997 Kubo et al. ................. 370/397
`9/1997 Shimizu ..................... 370/395
`
`(List continued on next page.)
`
`OTHER PUBLICATIONS
`
`"ATM Service Access Multiplexer (SAM) Generic Require(cid:173)
`ments", GR-2842-CORE, Issue 2, (Nov. 1996).
`"ATM Virtual Path Functionally in SONET Rings-Generic
`Criteria", Bellcore Standard GR-2837-CORE, Issue 3, (Oct.
`1996).
`Fritz, J., "Bulletproofing ATM: Part 1", Byte, 22, pp. 59-60,
`(Jun. 1, 1997).
`May, K.P., et al., "A Fast Restoration System for ATM-ring(cid:173)
`based LANS", IEEE Communications Magazine, 33, pp.
`90---98, (Sep. 1995).
`Takase, A., et al., "ATM Transport Node for Flexible and
`Robust Access Networks", Proceedings of the Global Tele(cid:173)
`communications Conference (GLOBECOM), vol. 3, Hous(cid:173)
`ton, TX, pp. 1481-1487, (Nov. 1993).
`
`Primary Examiner---Alpus H. Hsu
`Assistant Examiner-Toan D. Nguyen
`(74) Attorney, Agent, or Firm-Fogg and Associates, LLC;
`David N. Fogg
`
`(57)
`
`ABSTRACT
`
`A method for controlling virtual connections between end(cid:173)
`points over a unidirectional ring network. The network
`includes a number of network elements coupled together to
`form segments of the ring network. The method receives a
`request to create a virtual connection between first and
`second endpoints on the ring network. The method identifies
`the segments of the ring network that would be affected by
`the addition of the connection between the first and second
`endpoints. Further, the method retrieves data that represents
`the currently allocated capacity for each affected segment.
`For each affected segment, the method determines whether
`adding the requested virtual connection would exceed the
`capacity for the segment. The method transmits signals over
`the ring to establish the virtual connection when adding the
`virtual connection does not exceed the capacity for any of
`the affected segments.
`
`19 Claims, 3 Drawing Sheets
`
`8
`
`NETWORK
`ELEMENT
`
`NE1
`
`<N,1>
`
`<1,2>
`
`NETWORK
`ELEMENT
`
`NE2
`
`100
`
`/
`
`<2,3>
`
`CONNECTION
`CONTROLLER
`
`102
`
`A
`
`NETWORK
`ELEMENT
`
`NEN
`
`<N-1,N> 1
`
`'
`L------
`<5,6>
`
`NETWORK
`ELEMENT
`NE3
`
`i
`
`<3,4>
`
`NETWORK
`ELEMENT
`NE5
`
`NETWORK
`ELEMENT
`NE4
`
`<4,5>
`
`TRAFFIC
`SHAPER
`
`104
`
`A
`
`B C
`
`Ex.1008
`CISCO SYSTEMS, INC. / Page 1 of 12
`
`

`

`US 6,757,247 Bl
`Page 2
`
`U.S. PATENT DOCUMENTS
`
`............ 370/401
`11/1997 Dobbins et al.
`5,684,800 A
`5/1998 Uchida ....................... 370/222
`5,754,528 A
`6/1998 Sakagawa .............. 395/200.33
`5,774,662 A
`5,805,568 A * 9/1998 Shinbashi ................... 370/223
`5,805,820 A
`9/1998 Bellovin et al.
`....... 395/200.55
`5,812,525 A * 9/1998 Teraslinna .................. 370/229
`5,838,663 A * 11/1998 Elwalid et al.
`............. 370/233
`5,852,606 A
`12/1998 Prince et al.
`............... 370/393
`5,867,502 A * 2/1999 Chang ........................ 370/477
`
`4/1999 Suzuki et al. .......... 395/200.48
`5,892,912 A
`6/1999 Kanai ......................... 370/395
`5,912,891 A
`5,933,607 A * 8/1999 Tate et al.
`............... 395/200.7
`5,978,356 A * 11/1999 Elwalid et al.
`............. 370/230
`6,069,894 A * 5/2000 Holender et al.
`........... 370/397
`6,108,338 A * 8/2000 Ramfelt et al. ............. 370/403
`6,175,870 Bl * 1/2001 Gawlick et al.
`............ 709/227
`6,400,681 Bl * 6/2002 Bertin et al. ................ 370/218
`
`* cited by examiner
`
`Ex.1008
`CISCO SYSTEMS, INC. / Page 2 of 12
`
`

`

`i-,,.
`~
`-...,l
`,I;;..
`N
`-...,l
`(It
`-...,l
`_,.a-...
`rJ'J.
`e
`
`~
`
`'"""' 0 ....,
`~ ....
`'JJ. =(cid:173)~
`
`,i;;..
`0
`0
`N
`~~
`N
`?
`~
`
`~ = ......
`~ ......
`~
`•
`r:JJ.
`d •
`
`<3,4>
`
`NE3
`
`ELEMENT
`NETWORK
`
`<2,3>
`
`100
`
`/
`
`A B C
`
`SHAPER
`TRAFFIC
`
`NE4
`
`ELEMENT
`NETWORK
`
`<4,5>
`
`NE5
`
`<5,6>
`
`ELEMENT
`NETWORK
`
`L ______
`I
`I
`
`<N-1,N>
`
`NEN
`
`ELEMENT
`NETWORK
`
`A
`
`"'102
`
`CONTROLLER
`CONNECTION
`
`NE2
`
`ELEMENT
`NETWORK
`
`<1,2>
`
`NE1
`
`ELEMENT
`NETWORK
`
`<N,1 >
`
`C
`
`B
`
`F IG. 1
`
`Ex.1008
`CISCO SYSTEMS, INC. / Page 3 of 12
`
`

`

`i,-
`~
`-...,l
`,I;;..
`N
`-...,l
`(It
`-...,l
`_,.a-...
`rJ'J.
`e
`
`~
`
`0 ....,
`N
`~ ....
`'JJ. =(cid:173)~
`
`~
`
`,i;;..
`0
`0
`N
`~~
`N
`
`~ = ......
`~ ......
`~
`•
`r:JJ.
`d •
`
`A B C K
`
`~104
`
`SHAPER
`TRAFFIC
`
`K
`
`<3,4>
`
`NE3
`
`ELEMENT
`NETWORK
`
`NE4
`
`ELEMENT
`NETWORK
`
`<4,5>
`
`..;
`
`NE5
`
`ELEMENT
`NETWORK
`
`<5,6>
`
`L ______
`I
`I
`
`<N-1,N>
`
`NEN
`
`ELEMENT
`NETWORK
`
`A
`
`~102
`
`CONTROLLER
`CONNECTION
`
`<2,3>
`
`NE2
`
`ELEMENT
`NETWORK
`
`<1,2>
`
`NE1
`
`ELEMENT
`NETWORK
`
`<N,1>
`
`C
`
`B
`
`F IG. 2
`
`Ex.1008
`CISCO SYSTEMS, INC. / Page 4 of 12
`
`

`

`i,-
`~
`-...,l
`,I;;..
`N
`-...,l
`(It
`-...,l
`_,.a-...
`rJ'J.
`e
`
`~
`
`~
`
`0 ....,
`~ ....
`'JJ. =-~
`
`~ = ?
`
`,i;;..
`0
`0
`N
`~~
`N
`
`~ = ......
`~ ......
`~
`•
`r:JJ.
`d •
`
`<3,4>
`
`~
`
`K
`
`NE3
`
`ELEMENT
`NETWORK
`
`A B C K
`
`SHAPER
`TRAFFIC
`t
`NE4
`
`ELEMENT
`NETWORK
`
`<4,5>
`
`NE5
`
`ELEMENT
`NETWORK
`
`<2,3>
`
`r--1 02
`
`CONTROLLER
`CONNECTION
`
`NE2
`
`ELEMENT
`NETWORK
`
`t
`
`C
`
`-
`
`<1,2>
`
`NE1
`
`ELEMENT
`NETWORK
`
`'
`B
`
`<5,6>
`
`L ______
`I
`I
`
`<N-1,N>
`
`NEN
`
`ELEMENT
`NElWORK
`
`A
`
`<N,1 >
`
`F IG. 3
`
`Ex.1008
`CISCO SYSTEMS, INC. / Page 5 of 12
`
`

`

`US 6,757,247 Bl
`
`1
`CIRCUIT AND METHOD FOR
`CONTROLLING VIRTUAL CONNECTIONS
`IN A RING NETWORK
`
`TECHNICAL FIELD OF THE INVENTION
`
`The present invention relates generally to the field of
`communications and, in particular, to a circuit and method
`for controlling virtual circuit connections in a ring network.
`
`BACKGROUND OF THE INVENTION
`
`The telecommunications industry traditionally has pro(cid:173)
`vided services to subscribers over narrowband circuits.
`These narrowband circuits provided acceptable performance
`when the bulk of the demand for telecommunications ser(cid:173)
`vices was predominantly for voice traffic. In recent years,
`additional telecommunications services have been devel(cid:173)
`oped that can use much higher bandwidth, e.g., internet
`access, video conferencing, corporate intranets. These
`"broadband" services are increasingly in demand.
`Unfortunately, the existing telecommunications networks
`are not designed to provide quality broadband services.
`As the demand for access to telecommunications services
`increased, the industry used time division multiplexing
`technology to aggregate a number of lower bandwidth
`circuits onto higher bandwidth circuits. By the middle
`1980's, the SONET standard was well established as a time
`division multiplexing technology for fiber optic transport
`systems. However, as anyone who has attempted to down(cid:173)
`load a large data file over the internet can attest, current
`broadband services do not operate well over the existing
`telecommunications infrastructure.
`The telecommunications industry has been developing
`approaches that will allow better use of bandwidth in a
`broadband network. For example, Bellcore has provided
`standards for transmitting asynchronous transfer mode
`(ATM) packets over a SONET ring network. See, e.g.,
`GR-2842 and GR-2837. These Bellcore standards are incor(cid:173)
`porated herein by reference. These standards allow for the
`transmission of data between endpoints in a ring network
`over virtual circuits. However, the standards do not provide
`for determining how to control the generation of connections
`in the ring network. Without adequate control of new
`connections, a system could experience significant problems
`with quality of services provided over the networks high
`demand periods.
`For the reasons stated above, and for other reasons stated
`below which will become apparent to those skilled in the art
`upon reading and understanding the present specification,
`there is a need in the art for controlling the generation of
`virtual connections, e.g., ATM connections, in a ring net(cid:173)
`work.
`
`SUMMARY OF THE INVENTION
`
`The above mentioned problems with broadband ring
`networks and other problems are addressed by the present
`invention and which will be understood by reading and
`studying the following specification. A method for control(cid:173)
`ling access to a broadband ring network is described which
`determines whether a virtual connection will be allowed
`based on the impact that the connection will have on each
`affected segment of the ring network.
`In particular, an illustrative embodiment of the present
`invention includes a method for controlling virtual connec(cid:173)
`tions between endpoints over a unidirectional ring network.
`
`2
`The network includes a number of network elements
`coupled together to form segments of the ring network. The
`method receives a request to create a virtual connection
`between first and second endpoints on the ring network. The
`5 method identifies the segments of the ring network that
`would be affected by the addition of the connection between
`the first and second endpoints. Further, the method retrieves
`data that represents the currently allocated capacity for each
`affected segment. For each affected segment, the method
`10 determines whether adding the requested virtual connection
`would exceed the capacity for the segment. The method
`transmits signals over the ring to establish the virtual con(cid:173)
`nection when adding the virtual connection does not exceed
`the capacity for any of the affected segments. In one
`15 embodiment, the step of determining whether adding the
`requested virtual connection would exceed the capacity for
`the segment depends on the distribution of traffic from a
`traffic shaper. For segments that would transport data pack(cid:173)
`ets for the requested virtual connection, the method deter-
`20 mines whether the segment has sufficient capacity for the
`bandwidth used by the connection and additional over(cid:173)
`allocated bandwidth for a traffic shaper that provides the
`requested virtual connection to the ring network. For seg(cid:173)
`ments that would transport data packets from other virtual
`25 connections originating from the same traffic shaper but not
`the requested virtual connection, the method determines
`whether the segment has sufficient capacity for the addi(cid:173)
`tional over-allocated bandwidth. Finally, for segments that
`would transport data packets from the requested virtual
`30 connection but no other virtual connection of the traffic
`shaper, the method determines whether the segment has
`sufficient capacity for the requested connection and the
`over-allocated bandwidth for the traffic shaper.
`In another embodiment, a method for allocating band-
`35 width for a virtual connection between endpoints over a
`number of network entities that form a ring is provided. The
`method includes receiving a request to create a virtual
`connection between first and second endpoints. The first
`endpoint is associated with a traffic shaper that provides data
`40 packets to the ring network in discrete bandwidth units. The
`method further includes identifying segments of the ring
`network that would be affected by the addition of the
`connection between the first and second endpoints. The
`method determines the over-allocated bandwidth for the
`45 traffic shaper with the addition of the requested virtual
`connection. Further, for each affected segment, the method
`determines whether sufficient bandwidth is available to
`accommodate the requested virtual connection and the over(cid:173)
`allocated bandwidth. Finally, the method includes establish-
`so ing the virtual circuit when it is determined that sufficient
`bandwidth is available on each affected segment.
`In another embodiment, a method for determining the
`bandwidth used by a traffic shaper that controls access to a
`ring network for a number of endpoints of virtual connec-
`ss tions is provided. The method includes determining a band(cid:173)
`width requirement for each virtual connection that is related
`to the peak and sustained rates for delivery of data packets
`for the virtual connection. Further, the method sums the
`bandwidth requirement for each of the virtual connections.
`60 The method determines an integer value that represents the
`number of units of bandwidth deliverable by the traffic
`shaper that are required to at least accommodate the band(cid:173)
`width requirement. The method multiplies the integer value
`by the bandwidth of a unit bandwidth to determine the
`65 delivering bandwidth of the traffic source. The method also
`stores the delivering bandwidth of the traffic shaper to be
`used in allocating bandwidth in a ring network.
`
`Ex.1008
`CISCO SYSTEMS, INC. / Page 6 of 12
`
`

`

`US 6,757,247 Bl
`
`3
`In another embodiment, a communication network that
`transmits data over virtual connections between communi(cid:173)
`cation endpoints is provided. The network includes a num(cid:173)
`ber of network elements coupled together so as to form a
`ring with adjacent network elements communicating over
`ring segments. Each network element is operable to com(cid:173)
`municate data between the network and at least one end(cid:173)
`point. At least one network element includes a connection
`controller that determines whether adding a requested virtual
`connection would exceed the capacity for segments affected
`by the addition of the virtual connection.
`In another embodiment, a circuit that determines whether
`to allow a virtual connection to be established over a ring of
`network elements wherein adjacent network elements are
`coupled together by ring segments is provided. The circuit
`includes a memory that stores instructions. Further, the
`circuit includes a processor that executes the instructions to
`determine, for each affected ring segment, whether adding
`the virtual connection would exceed the bandwidth capacity
`of a segment of the ring network.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`FIG. 1 is a block diagram of an illustrative embodiment
`of the present invention.
`FIGS. 2 and 3 are block diagrams that illustrate an
`embodiment of a method for controlling connections to a
`ring network according to the teachings of the present
`invention.
`
`DETAILED DESCRIPTION OF THE
`INVENTION
`
`5
`
`4
`tual connection begins with a "traffic originating endpoint"
`and terminates at a "traffic terminating endpoint." The traffic
`originating endpoint adds traffic or data packets onto net(cid:173)
`work 100 and the traffic terminating endpoint drops the
`traffic from network 100. There can be many traffic origi(cid:173)
`nating endpoints on each network element of ring network
`100. Each traffic originating endpoint can be viewed as a
`single traffic source. Alternatively, a group of traffic origi(cid:173)
`nating endpoints can be viewed as one traffic source by
`10 multiplexing the traffic originating endpoints into a single
`virtual connection. In this case, the packets from each of the
`endpoints in the group terminates at endpoints on a common
`network entity. In other words, the virtual connections for
`each of the traffic originating endpoints in the traffic source
`15 span the same ring segments of network 100. It is also noted
`that each network entity supports multiple traffic terminating
`endpoints.
`Typically, traffic on a virtual connection is "bursty." In
`other words, the rate at which packets are placed onto the
`20 virtual connection will vary over time. The bandwidth used
`to describe a traffic originating endpoint or source is typi(cid:173)
`cally a mean value of the required bandwidth of the end(cid:173)
`point. Two parameters are used conventionally to define the
`subscribed bandwidth for a virtual connection: a peak rate
`25 (PR), and a sustained rate (SR). The peak rate is the
`maximum bit rate at which data can be placed on network
`100 by an associated traffic originating endpoint. The sus(cid:173)
`tained rate is the average bit rate at which data is added to
`network 100 by the associated endpoint. When multiple
`30 endpoints are grouped into a traffic source, the allocated
`bandwidth for the traffic source can be less than the sum of
`the subscribed bandwidths of all of the endpoints in the
`associated group. This is represented mathematically in
`equation 1, wherein a group j can consist of endpoints
`35 labeled 1 through 1.
`
`In the following detailed description of the preferred
`embodiments, reference is made to the accompanying draw(cid:173)
`ings which form a part hereof, and in which is shown by way
`of illustration specific illustrative embodiments in which the
`invention may be practiced. These embodiments are
`described in sufficient detail to enable those skilled in the art
`to practice the invention, and it is to be understood that other
`embodiments may be utilized and that logical, mechanical 40
`and electrical changes may be made without departing from
`the spirit and scope of the present invention. The following
`detailed description is, therefore, not to be taken in a limiting
`sense.
`FIG. 1 is a block diagram of an illustrative embodiment
`of the present invention. Network 100 is a closed-loop, ring
`network that is formed by a unidirectional connection of
`network elements NE1 through NEN. Network 100 transmits
`data packets or cells between endpoints, e.g., terminals,
`associated with the network elements over virtual connec(cid:173)
`tions using, for example, asynchronous transfer mode
`(ATM), frame relay, or any other appropriate conventional
`virtual connection protocol. Network elements NE1 through
`NEN may comprise, for example, virtual path add/drop
`multiplexers that operate on virtual connection packets.
`Network 100 comprises a number of "ring segments." A
`ring segment is defined as a link that carries data packets or
`cells in a unidirectional path between two adjacent network
`elements. Each ring segment in FIG. 1 is denoted by the
`expression <first network element, second network 60
`element>wherein the first network element and the second
`network element are adjacent network elements in network
`100 in the direction of traffic flow around the network. For
`example, the ring segment connecting network element NE1
`to network element NE2 is denoted <1,2>.
`Communication over network 100 is accomplished
`through virtual connections between "endpoints." Each vir-
`
`l
`
`BJ :;; I PR; and B1 :;; I SR;
`
`l
`
`(1)
`
`i=l
`
`i=l
`
`This grouping of endpoints into a single traffic source with
`a bandwidth allocation that is less of the sum of the
`subscribed bandwidth of each of the endpoints is referred to
`as "statistical multiplexing" in virtual circuit applications.
`Each group of endpoints can be controlled or throttled to
`only deliver data packets with a selected bandwidth onto
`network 100. In other words, data from a traffic source can
`be placed on to network 100 at an approximately constant
`rate even though the rate that the data is produced by the
`traffic source may vary over time. This is referred to as
`"traffic shaping" or "smoothing." This function is performed
`for connections A, B, and C in FIG. 1 by traffic shaper 104.
`
`Controlling Connections in the Ring Network
`
`45
`
`50
`
`55
`
`Each virtual connection in network 100 is allocated a
`portion of the bandwidth on each segment of network 100
`between the network entities where the virtual connection
`originates and terminates. For example, a portion of the
`bandwidth for each segment between network element NE4
`( originating) and network element NE2 (terminating) is
`allocated for connection C. Since the ring segments of
`network 100 have a finite bandwidth, connection controller
`102 is provided to determine whether there is enough
`65 bandwidth on each segment of network 100 that is affected
`by a request for a virtual connection to be established. If a
`connection is established when there is insufficient band-
`
`Ex.1008
`CISCO SYSTEMS, INC. / Page 7 of 12
`
`

`

`5
`width on one or more segments, packets could be lost and
`thus service over network 100 would degrade.
`
`6
`
`(3)
`
`US 6,757,247 Bl
`
`Connection controller 102 is programmed, e.g., using
`hardware, software, firmware or a combination thereof, to 5
`implement functions that determine when a connection can
`be allowed in network 100 without exceeding the bandwidth
`capacity for the ring segments of network 100. For example,
`connection controller 102 is programmed to implement the
`functions described in more detail below. In one 10
`implementation, the connection controller is included on the
`network management interface card (NMIC) of the gateway
`node of network 100. However, the location of the connec(cid:173)
`tion controller in network 100 is not critical.
`
`Essentially, connection controller 102 assures that the
`sum of all the bandwidth required for each connection that
`passes over a segment is less than or equal to the total
`bandwidth available on the physical line connecting adjacent
`network elements of that segment. Connection controller
`102 only allows connections to be established if sufficient
`bandwidth is available on all affected segments. Thus,
`connection controller 102 is advantageously included to
`guarantee that the quality of service over network 100 will
`not degrade by allowing too many connections.
`
`Over-Allocated Bandwidth
`
`In some circumstances, connection controller 102 also
`considers "over-allocated" bandwidth in assessing whether
`to allow a connection to be established. Over-allocated
`bandwidth is bandwidth that is allocated to a virtual con(cid:173)
`nection that exceeds the required or subscribed bandwidth
`for service on the virtual connection. The over-allocated
`bandwidth assures quality of performance in the network.
`Traffic shapers, or other equipment used to control virtual
`connections, can produce over-allocated bandwidth. A traffic
`shaper produces over-allocated bandwidth because it deliv(cid:173)
`ers data to a network in integral multiples of a unit band(cid:173)
`width. For example, a traffic shaper may only be able to
`deliver data to a ring network in multiples of 4 Megabits per
`second up to the line rate of the network. When the sub(cid:173)
`scribed bandwidth is less than an integral multiple of a unit
`bandwidth, excess bandwidth is assigned to the virtual
`connection. This is referred to as "over-allocated" band(cid:173)
`width.
`
`The source of over-allocated bandwidth for traffic shaper
`104 is illustrated with reference to equations 2 through 4
`below. Traffic shaper 104 delivers data with a bandwidth
`defined by equation 2.
`
`(2)
`
`In equation 3, the brackets around the first expression refer
`to the "ceiling function." This means that the result of the
`division inside the brackets is rounded up to the next highest
`integer value. For example, traffic shaper 104 receives inputs
`from three traffic sources with data rates of 3, 7, and 9
`megabits per second, respectively. Thus the summation
`portion of equation 4 results in a total of 19 megabits per
`second. Assuming that the granularity with which traffic
`shaper 104 delivers data packets to ring network 100 is 4
`15 Megabits per second, the result of the division operation of
`equation 3 is 4. 75. The ceiling function raises this value to
`5. Thus equation 3 produces a value of 20 Megabits per
`second for the deliverable bandwidth for traffic shaper 104.
`The deliverable bandwidth of a traffic shaper will often
`20 exceed the bandwidth subscribed for by its associated virtual
`connections. The amount by which the deliverable band(cid:173)
`width exceeds the subscribed bandwidth is the "over(cid:173)
`allocated bandwidth." The amount of over-allocated band(cid:173)
`width for traffic shaper 104 is defined by equation 4.
`
`25
`
`(4)
`
`30
`
`This over allocated bandwidth is not wasted bandwidth. It
`may be used at different times by different traffic sources
`associated with traffic shaper 104 when a traffic source meets
`or exceeds its peak rate. Thus this over allocated bandwidth
`35 is essentially a shared bandwidth that prevents connection
`controller 102 from granting requests for bandwidth that
`would exceed the capacity of any segment of network 100.
`It is noted that traffic sources associated with a single
`traffic shaper may be terminated at different network entities
`40 in network 100. Thus, it is possible that the virtual connec(cid:173)
`tion of a traffic shaper that terminates at the furthest network
`entity in network 100 from the originating network entity
`could use the over allocated bandwidth, e.g., connection C
`in FIG. 1. Thus connection controller 102 carries the over
`45 allocated bandwidth for traffic shaper 104 through each
`affected segment of network 100. For example, as shown in
`FIG. 1, traffic shaper 104 includes three traffic sources
`identified as traffic sources A, Band C. Connection control(cid:173)
`ler 102 of network 100 allocates bandwidth to the various
`50 affected ring segments as shown in Table 1. In this example,
`connections A, B, and Care 3, 7, and 9 Megabits per second,
`respectively, and the "granularity" of traffic shaper 104 is 4
`Megabits per second. All bandwidth indications in Table 1
`are in Megabits per second.
`
`55
`
`TABLE 1
`
`In equation 2, the delivered bandwidth, DB, of traffic shaper
`104 is equal to the sum of the bandwidth, B, of each traffic
`source, j, that is associated with traffic shaper 104.
`Traffic shaper 104 delivers data to network 100 in integral
`multiples of a bandwidth, e.g., 4Megabits per second,
`referred to as a "unit bandwidth" or the "granularity" of the
`traffic shaper. For purposes of this specification, the granu(cid:173)
`larity of a traffic shaper is designated G in the remaining
`equations. With the granularity limitation, deliverable band- 65
`width for traffic shaper 104 is modified as shown in equation
`3:
`
`60
`
`Segment
`
`Allocated bandwidth
`
`Over-allocated Bandwidth
`
`<4,5>
`<5,6>
`<N-1,N>
`<N,1>
`<1,2>
`<2,3>
`<3,4>
`
`19
`19
`19
`16
`11
`0
`0
`
`0
`0
`
`As Table 1 indicates, traffic source 104 uses 19 Megabits per
`second of bandwidth. Since the granularity of traffic shaper
`
`Ex.1008
`CISCO SYSTEMS, INC. / Page 8 of 12
`
`

`

`US 6,757,247 Bl
`
`7
`is 4 Megabits per second, 1 Megabit per second will be
`over-allocated at this time. This over-allocation is carried
`through to network element NE2 since this is where the last
`virtual connection terminates. It is noted that Table 1 only
`indicates the allocated and over-allocated bandwidth for 5
`virtual connections from traffic shaper 104. Network 100
`could transport additional virtual connections.
`
`8
`over-allocated bandwidth does not exceed the line rate (AR)
`for the ring segment.
`Additionally, each ring segment between network element
`NE5 , the network element at which connection K terminates,
`and network element NE2 , the last network element used by
`a virtual connection of traffic shaper 104, must satisfy the
`requirements of equation 7.
`
`Adding a New Traffic Source
`(7)
`AR"';CB+NewOAB-OldOAB
`FIGS. 2 and 3 are block diagrams that illustrate tech- 10 Equation 7 differs from equation 6 in that the term Bk is not
`niques for determining whether to allow an additional traffic
`included. This reflects the fact that virtual connection K
`source, K, to be added to traffic shaper 104 and ring network
`terminated prior to these ring segments. It is noted that these
`100 according to the teachings of the present invention.
`ring segments are affected by the change in over-allocated
`Essentially, connection controller 102 of network 100 looks
`bandwidth, if any.
`at the effect that traffic source K will have on each segment 15
`In the example of FIG. 3, connection K is the furthest
`terminating virtual connection for traffic shaper 104. In this
`that is associated with any traffic source for traffic shaper
`104. First, the subscribed bandwidth, Bk, required by con-
`case, each ring segment that is effected by traffic shaper 104
`nection K is considered for some of the segments in network
`must satisfy either equation 8 or equation 9 for connection
`100. Additionally, any change in the over-allocated band-
`K to be allowed. For example, each effected ring segment
`width for traffic shaper 104 by the addition of traffic source 20 between network element NE4
`, the network element asso-
`ciated with traffic shaper 104, and network element NE2
`K is also considered for some of the segments of network
`,
`100. The following equations provide the basis for this
`previously the furthest network element serviced by traffic
`analysis by connection controller 102.
`shaper 104, must satisfy the requirements of equation 8.
`Two separate cases are illustrated by FIGS. 2 and 3,
`respectively. First, in FIG. 2, connection K is added to traffic
`shaper 104 and terminates at a network element that is not
`the last network element associated with a virtual connection
`for traffic shaper 104. FIG. 3 represents a case in which the
`new connection K terminates at a network entity that 30
`becomes the furthest network entity from traffic shaper 104.
`These two cases are described in turn.
`In order to determine if the connection can be established,
`connection controller 102 determines the change in the
`over-allocated bandwidth by adding connection K. To do 35
`this, the new over-allocated bandwidth (NewOAB) is cal(cid:173)
`culated according to equation 5.
`
`25
`
`AR"';CB+Bk+NewOAB-OldOAB
`
`(8)
`
`This equation is similar in scope to equation 6 above. The
`remaining ring segments that carry traffic from traffic shaper
`104 must meet the requirements of equation 9.
`
`AR"';CB+Bk+NewOAB
`
`(9)
`
`(5)
`
`Equation 9 does not include a term related to the old
`over-allocated bandwidth. This is because each of these
`segments is located after the network element that termi(cid:173)
`nated the last traffic source of traffic shaper 104 prior to the
`addition of traffic source K. Thus, prior to connection K
`there was no over-allocated bandwidth for these segments.
`In one embodiment, connection controller 102 includes a
`40 processor 106 that executes instructions to perform the
`functions described above with respect to determining when
`to allow a virtual connection to be established. As such,
`connection controller 102 includes a combination of hard-
`ware and software to interface with network element NE1 .
`For example, connection controller 102 can be implemented
`in hardware and software on a network management inter-
`face (NMIC) card that interfaces with the network elements
`of network 100 through a backplane of network controller
`NE1 . In one embodiment, connection controller 102 includes
`a memory 108 that stores executable code or instructions to
`implement the functions described above and a processor
`106 that executes the instructions.
`
`In equation 5, j refers to the connections A, B, C, and K, Bj
`represents the bandwidth of each connection, and G is the 45
`granularity of traffic shaper 104.