Abstract:
A method for controlling virtual connections between endpoints 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.

Description:
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 provided services to subscribers over narrowband circuits. These narrowband circuits provided acceptable performance when the bulk of the demand for telecommunications services was predominantly for voice traffic. In recent years, additional telecommunications services have been developed 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&#39;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 download 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 incorporated 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 network. 
     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 controlling 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 connections between endpoints 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. In one 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 packets for the requested virtual connection, the method determines whether the segment has sufficient capacity for the bandwidth used by the connection and additional over-allocated bandwidth for a traffic shaper that provides the requested virtual connection to the ring network. For segments that would transport data packets from other virtual connections originating from the same traffic shaper but not the requested virtual connection, the method determines whether the segment has sufficient capacity for the additional over-allocated bandwidth. Finally, for segments that would transport data packets from the requested virtual 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 bandwidth 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 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 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-allocated bandwidth. Finally, the method includes establishing 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 connections is provided. The method includes determining a bandwidth 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. 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 bandwidth requirement. The method multiplies the integer value by the bandwidth of a unit bandwidth to determine the 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. 
     In another embodiment, a communication network that transmits data over virtual connections between communication endpoints is provided. The network includes a number 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 communicate data between the network and at least one endpoint. 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 
     In the following detailed description of the preferred embodiments, reference is made to the accompanying drawings 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 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 NE 1  through NE N . Network  100  transmits data packets or cells between endpoints, e.g., terminals, associated with the network elements over virtual connections using, for example, asynchronous transfer mode (ATM), frame relay, or any other appropriate conventional virtual connection protocol. Network elements NE 1  through NE N  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 &lt;first network element, second network element&gt;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 NE 1  to network element NE 2  is denoted &lt; 1 , 2 &gt;. 
     Communication over network  100  is accomplished through virtual connections between “endpoints.” Each virtual connection begins with a “traffic originating endpoint” and terminates at a “traffic terminating endpoint.” The traffic originating endpoint adds traffic or data packets onto network  100  and the traffic terminating endpoint drops the traffic from network  100 . There can be many traffic originating 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 originating endpoints can be viewed as one traffic source by 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 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 virtual connection will vary over time. The bandwidth used to describe a traffic originating endpoint or source is typically a mean value of the required bandwidth of the endpoint. Two parameters are used conventionally to define the subscribed bandwidth for a virtual connection: a peak rate (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 sustained rate is the average bit rate at which data is added to network  100  by the associated endpoint. When multiple 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 labeled 1 through l.                B   j     ≤       ∑     i   =   1     l                       PR   i                   and                   B   j         ≤       ∑     i   =   1     l                     SR   i               (   1   )                                
     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 
     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 NE 4  (originating) and network element NE 2  (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 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 bandwidth on one or more segments, packets could be lost and thus service over network  100  would degrade. 
     Connection controller  102  is programmed, e.g., using hardware, software, firmware or a combination thereof, to 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 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 connection 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 connection 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 delivers data to a network in integral multiples of a unit bandwidth. 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 subscribed 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” bandwidth. 
     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.              DB   =       ∑   j                             B   j               (   2   )                                
     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.,  4  Megabits per second, referred to as a “unit bandwidth” or the “granularity” of the traffic shaper. For purposes of this specification, the granularity of a traffic shaper is designated G in the remaining equations. With the granularity limitation, deliverable bandwidth for traffic shaper  104  is modified as shown in equation 3:              DB   =       ⌈         ∑   j                             B   j       G     ⌉     ×   G             (   3   )                                
     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 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 exceed the bandwidth subscribed for by its associated virtual connections. The amount by which the deliverable bandwidth exceeds the subscribed bandwidth is the “over-allocated bandwidth.” The amount of over-allocated bandwidth for traffic shaper  104  is defined by equation 4.              OAB   =       (       ⌈         ∑   j                             B   j       G     ⌉     -         ∑   j                             B   j       G       )     ×   G             (   4   )                                
     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 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 in network  100 . Thus, it is possible that the virtual connection 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 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, B and C. Connection controller  102  of network  100  allocates bandwidth to the various affected ring segments as shown in Table 1. In this example, connections A, B, and C are 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. 
     
       
         
               
               
               
               
             
               
               
               
               
             
           
               
                   
                 TABLE 1 
               
               
                   
                   
               
               
                   
                 Segment 
                 Allocated bandwidth 
                 Over-allocated Bandwidth 
               
               
                   
                   
               
             
             
               
                   
               
             
          
           
               
                   
                 &lt;4,5&gt; 
                 19 
                 1 
               
               
                   
                 &lt;5,6&gt; 
                 19 
                 1 
               
               
                   
                 &lt;N-1,N&gt; 
                 19 
                 1 
               
               
                   
                 &lt;N,1&gt; 
                 16 
                 1 
               
               
                   
                 &lt;1,2&gt; 
                 11 
                 1 
               
               
                   
                 &lt;2,3&gt; 
                 0 
                 0 
               
               
                   
                 &lt;3,4&gt; 
                 0 
                 0 
               
               
                   
                   
               
             
          
         
       
     
     As Table 1 indicates, traffic source  104  uses 19 Megabits per second of bandwidth. Since the granularity of traffic shaper 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 NE 2  since this is where the last virtual connection terminates. It is noted that Table 1 only indicates the allocated and over-allocated bandwidth for virtual connections from traffic shaper  104 . Network  100  could transport additional virtual connections. 
     Adding a New Traffic Source 
     FIGS. 2 and 3 are block diagrams that illustrate techniques for determining whether to allow an additional traffic source, K, to be added to traffic shaper  104  and ring network  100  according to the teachings of the present invention. Essentially, connection controller  102  of network  100  looks at the effect that traffic source K will have on each segment that is associated with any traffic source for traffic shaper  104 . First, the subscribed bandwidth, B k , required by connection K is considered for some of the segments in network  100 . Additionally, any change in the over-allocated bandwidth for traffic shaper  104  by the addition of traffic source K is also considered for some of the segments of network  100 . The following equations provide the basis for this analysis by connection controller  102 . 
     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 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 this, the new over-allocated bandwidth (NewOAB) is calculated according to equation 5.              NewOAB   =       (       ⌈         ∑   j                             B   j       G     ⌉     -         ∑   j                             B   j       G       )     ×   G             (   5   )                                
     In equation 5, j refers to the connections A, B, C, and K, B j  represents the bandwidth of each connection, and G is the granularity of traffic shaper  104 . It is noted that the over-allocated bandwidth may in fact decrease with the addition of connection K. 
     In this case of FIG. 2, each ring segment must satisfy the requirements of either equation 6 or equation 7 below in order for the connection K to be made. Equation 6 relates to the ring segments that are located between network element NE 4 , the originating network element that is associated with traffic source  104 , and network element NE 5 , the network element at which connection K terminates. In this case, both the bandwidth for connection K and the change in over-allocated bandwidth must be considered to determine whether the line rate for the ring segment would be exceeded by addition of the new connection. 
       AR≧CB+B   k +New OAB −Old OAB   (6) 
     In equation 6, the expression CB refers to the currently allocated bandwidth for the segment in question (including over-allocated bandwidth). The value for CB can be derived using equation 3. Thus, equation 6 is satisfied if the combination of the previously allocated bandwidth, the new bandwidth required for connection K and the change in over-allocated bandwidth does not exceed the line rate (AR) for the ring segment. 
     Additionally, each ring segment between network element NE 5 , the network element at which connection K terminates, and network element NE 2 , the last network element used by a virtual connection of traffic shaper  104 , must satisfy the requirements of equation 7. 
     
       
           AR≧CB +New OAB −Old OAB   (7) 
       
     
     Equation 7 differs from equation 6 in that the term B k  is not included. This reflects the fact that virtual connection K terminated prior to these ring segments. It is noted that these ring segments are affected by the change in over-allocated bandwidth, if any. 
     In the example of FIG. 3, connection K is the furthest terminating virtual connection for traffic shaper  104 . In this case, each ring segment that is effected by traffic shaper  104  must satisfy either equation 8 or equation 9 for connection K to be allowed. For example, each effected ring segment between network element NE 4 , the network element associated with traffic shaper  104 , and network element NE 2 , previously the furthest network element serviced by traffic shaper  104 , must satisfy the requirements of equation 8. 
       AR≧CB+B   k +New OAB −Old OAB   (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+B   k +New OAB   (9) 
       
     
     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 terminated 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 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 hardware and software to interface with network element NE 1 . For example, connection controller  102  can be implemented in hardware and software on a network management interface (NMIC) card that interfaces with the network elements of network  100  through a backplane of network controller NE 1 . 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. 
     Conclusion 
     Although specific embodiments have been illustrated and described herein, it will be appreciated by those of ordinary skill in the art that any arrangement which is calculated to achieve the same purpose may be substituted for the specific embodiment shown. This application is intended to cover any adaptations or variations of the present invention. For example, the embodiments are described in terms of unidirectional connections between endpoints. The endpoints are shown as either a traffic originating endpoint or a traffic terminating endpoint. It is understood that each endpoint typically will act both as a terminating and an originating endpoint. This is accomplished by setting up two unidirectional virtual connections between the two endpoints. One connection carries data around the network from a first endpoint to a second endpoint. The second connection carries data packets around the network from the second endpoint to the first endpoint. Thus, a bidirectional link can be established by the combination of two unidirectional virtual connections. 
     In certain implementations, a traffic shaper that controls multiple traffic sources may not be able to deliver the traffic for each traffic source according to the allocated bandwidth for the sources. However, the total delivered bandwidth for the traffic shaper is guaranteed. Thus, in some implementations, a weight can be used with the over-allocated bandwidth. The weight can be for a specific traffic shaper and can be different for various segments of the ring. 
     In some implementations, a traffic source will transmit signals over two complementary paths around the ring, e.g., signals are transmitted over different channels in opposite directions around the ring. In this circumstance, the connection controller makes separate determinations for each path around the ring to determine whether to allow a connection.