Abstract:
A method and apparatus for load balancing and protecting data traffic in an optical ring is described. A method comprises configuring multiple spanning trees in a set of one or more network elements of an optical ring, load balancing with the multiple spanning trees data traffic transmitted in unprotected data channels provisioned through the optical ring, and protecting the unprotected data channels with the multiple spanning trees.

Description:
CROSS-REFERENCE TO RELATED APPLICATIONS 
     This application claims the benefit of U.S. Provisional Patent Application No. 60/376,039, entitled “Method and Apparatus for Load Balancing and Protecting Data Traffic in an Optical Ring” filed on Apr. 26, 2002. 
    
    
     BACKGROUND OF THE INVENTION 
     1. Field of the Invention 
     The invention relates to the field of communication. More specifically, the invention relates to communication networks. 
     2. Background of the Invention 
     Current networks must satisfy consumer demand for more bandwidth and a convergence of voice and data traffic. The increased demand of bandwidth by consumers combines with improved high bandwidth capacity of core networks to make edge networks a bottleneck despite the capacity of optical networks. 
     Multiplexing is used to deliver a variety of traffic over a single high speed broadband line. An optical standard such as Synchronous Optical Network (SONET) or Synchronous Digital Hierarchy (SDH) in conjunction with a multiplexing scheme is used to deliver various rates of traffic over a single high speed optical fiber. SONET/SDH is a transmission standard for optical networks which corresponds to the physical layer of the open standards institutes (OSI) network model. One of the protection schemes for SONET/SDH involves automatic protection switching (APS) in a bi-directional line switched ring (BLSR) architecture. BLSR utilizes linear switching to implement APS. 
     High speed optical rings offer large amounts of bandwidth, but the protection scheme utilizes 50% of that bandwidth. This 50% of total bandwidth for a protection channel typically goes unused while there is not a failure. It is typically unused because traffic transmitted in the protection channel would be preempted by the working TDM traffic when a failure occurs. 
     An alternative to unprotected preemptable traffic in a protection channel is to provide a non-preemptable unprotected traffic (NUT) channel. A NUT channel allows for an implementation that runs a unidirectional path switched ring (UPSR) over a BLSR. Unfortunately, the traffic carried in a NUT channel may be dropped if a failure occurs in the BLSR. Hence, certain customers will not purchase NUT channels. 
     BRIEF SUMMARY OF THE INVENTION 
     A method and apparatus for utilization of spanning trees in an optical ring is described. According to one aspect of the invention, a method in a network element provides for configuring multiple spanning trees in a set of one or more network elements of an optical ring, load balancing with the multiple spanning trees data traffic transmitted in unprotected data channels provisioned through the optical ring, and protecting the unprotected data channels with the multiple spanning trees. 
     These and other aspects of the present invention will be better described with reference to the Detailed Description and the accompanying Figures. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
       The invention may best be understood by referring to the following description and accompanying drawings that are used to illustrate embodiments of the invention. In the drawings: 
         FIG. 1A  is an exemplary diagram illustrating provisioning of an unprotected data channel in an optical ring according to one embodiment of the invention. 
         FIG. 1B  is an exemplary diagram illustrating configuration of metrics and creation of spanning trees in an optical ring according to one embodiment of the invention. 
         FIG. 2A  is an exemplary diagram illustrating failure in an optical ring with spanning trees according to one embodiment of the invention. 
         FIG. 2B  is an exemplary diagram illustrating active links of a newly created spanning tree in an optical ring according to one embodiment of the invention. 
         FIG. 3  is an exemplary diagram illustrating binding a spanning tree to VLANs according to one embodiment of the invention. 
         FIG. 4  is an exemplary diagram illustrating VLAN circuits and spanning trees in a optical ring according to one embodiment of the invention. 
         FIG. 5A  is an exemplary diagram illustrating MAC address learning in an optical ring according to one embodiment of the invention. 
         FIG. 5B  is an exemplary diagram illustrating MAC address learning in an optical ring continuing from  FIG. 5A  according to one embodiment of the invention. 
     
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
     In the following description, numerous specific details are set forth to provide a thorough understanding of the invention. However, it is understood that the invention may be practiced without these specific details. In other instances, well-known circuits, structures, standards, and techniques have not been shown in detail in order not to obscure the invention. 
       FIGS. 1A-1B  are exemplary diagrams illustrating creation of a spanning tree for an unprotected data channel in an optical ring according to one embodiment of the invention.  FIG. 1A  is an exemplary diagram illustrating provisioning of an unprotected data channel in an optical ring according to one embodiment of the invention. In  FIG. 1A , network elements  101 A- 101 D comprise an optical ring. The optical ring illustrated in  FIG. 1A  is connected in the following manner: the link  111 A connects the network elements  101 A and  101 B; the link  111 B connects the network elements  101 B and  101 C; the link  111 C connects the network elements  101 C and  101 D; and a link  111 D connects the network elements  101 D and  101 A. The links illustrated in  FIG. 1A  are bi-directional links, but the described invention can also be applied to a uni-directional ring. 
     The network element  101 A includes a switching fabric  103 A and a data traffic switching medium  105 A. Edge lines  107 A- 107 C connect the network element  101 A to non-core network elements, which are not illustrated. At a time  1 , the set of subchannels  113 A and a set of sub-channels  113 B are selected. At a time  2 , the set of selected sub-channels  113 A are concatenated. Likewise, the set of selected sub-channels  113 B are concatenated. Although this illustration describes sets of subchannels, another example can involve a single subchannel that does not get concatenated. At a time  3 , the concatenated set of selected subchannels  113 A and the concatenated set of selected subchannels  113 B are aggregated and terminated on the data traffic switching medium  105 A. The same set of operations are performed for each trunk port of the optical ring of the network elements  101 C and  101 D. 
     The network element  101 B does not include a data traffic switching medium. Therefore, the concatenated set of selected subchannels  113 A and the concatenated selected set of subchannels  113 B are not terminated and aggregated in the network element  101 B. In the network element  101 B, the concatenated selected set of subchannels  113 A are cross connected through a switch fabric  103 B. Similarly, the concatenated set of selected subchannels  113 B are cross connected through the switch fabric  103 B. 
       FIG. 1B  is an exemplary diagram illustrating configuration of metrics and creation of spanning trees in an optical ring according to one embodiment of the invention. In  FIG. 1B , the aggregated concatenated selected set of subchannels  113 A and  113 B are illustrated as an unprotected data channel  121 A- 121 C. The unprotected data channel  121 A begins at the network element  101 A and terminates at the network element  101 C, traversing the network element  101 B. The unprotected data channel  121 B runs between the network elements  101 C and  101 D. The unprotected data channel  121 C runs between the network elements  101 D and  101 A. 
     In creating a spanning tree, metrics are defined for the spanning tree. Defining metrics includes assigning bridge priorities and defining path costs. At a time  1 , a bridge priority is defined for network elements  101 A,  101 C, and  101 D. The bridge priority for the network element  101 C is defined as 1. The bridge priority for the network element  101 D is defined as 3. The bridge priority for the network element  101 A is defined as 2. In this illustration, the lower number has a higher priority. At a time  2 , the path costs are defined. The path costs are shown in Table 1 below. 
     
       
         
               
             
               
               
               
             
           
               
                 TABLE 1 
               
             
             
               
                   
               
               
                 Path Costs 
               
             
          
           
               
                 LINK 
                 PORT 
                 PATH COSTS 
               
               
                   
               
               
                 101A → 101C 
                 123A 
                 1 
               
               
                 101C → 101D 
                 123G 
                 5 
               
               
                 101D → 101A 
                 123J 
                 2 
               
               
                 101A → 101D 
                 123K 
                 4 
               
               
                 101D → 101C 
                 123H 
                 1 
               
               
                 101C → 101A 
                 123E 
                 1 
               
               
                   
               
             
          
         
       
     
     Once the path costs are defined, the root bridge is determined. The root bridge is determined by the network elements  101 A,  101 C, and  101 D sending out bridge protocol data units announcing themselves as the root bridge. Upon determining that a different network element has a higher priority, a network element will identify the network element with the higher priority as the root bridge. In  FIG. 1B , the network element  101 C has the highest priority. Therefore, the network element  101 C will be the root bridge. Once the root bridge is determined and the path costs are defined, root path costs are calculated. Root path cost is the sum path cost to reach the root bridge. The root path costs are calculated as shown in Table 2. 
     
       
         
               
               
               
             
           
               
                   
               
               
                 LINK 
                 PORT 
                 ROOT PATH COSTS 
               
               
                   
               
             
             
               
                 101A → 101C 
                 123A 
                 1 
               
               
                 101A → 101B 
                 123K 
                 5 
               
               
                 101D → 101C 
                 123H 
                 1 
               
               
                 101D → 101B 
                 123J 
                 3 
               
               
                   
               
             
          
         
       
     
     Table 2 
     Root Path Costs 
     The spanning tree that is created from defined metrics are presented by a graph  135 . The graph  135  shows the network element  101 C as root of a tree. The left branch of the tree connects the network element  101 A and the right branch of the tree connects the network element  101 B. Since the root path cost to network element  101 A through port  123 A is cheaper than the root path cost through port  123 K, the spanning tree of the network element  101 A blocks the port  123 K (discards the link  121 C and does not forward through traffic the port  123 K). The spanning tree of the network element  101 D selects port  123 H to reach the root path bridge and blocks port  123 J, which is more expensive. 
       FIGS. 2A-2B  are exemplary diagrams illustrating protection of data traffic with spanning trees in an optical ring according to one embodiment of the invention.  FIG. 2A  is an exemplary diagram illustrating failure in an optical ring with spanning trees according to one embodiment of the invention. In  FIG. 2A , network elements  201 A- 201 D comprise an optical ring. The optical ring is connected in the following manner: the link  205 A connects to a network element  201 D and  201 A, the link  205 B connects the network elements  201 A and  201 B, the link  205 C connects the network elements  201 B and  201 C and link  205 D connects network elements  201 C and  201 D. 
     In  FIG. 2A , the network element  201 A has been designated as the root bridge. A spanning tree  215  in the network element  201 D forwards traffic to the port  202 A along the link  205 A to the root bridge network element  201 A. A graph  210  illustrates the spanning tree  215 . The root bridge network element  201 A forwards the traffic to a port  202 C where the traffic exits the ring. The root path costs throughout the ring are shown in Table 3 below. When the link  205 A fails, root path costs are recalculated and a new spanning tree is created at each network element throughout the ring. 
     
       
         
               
               
               
             
           
               
                   
               
               
                 LINK 
                 PORT 
                 ROOT PATH COSTS 
               
               
                   
               
             
             
               
                 1D → 1A 
                 202A 
                 1 
               
               
                 1D → 1A 
                 202K 
                 6 
               
               
                 1C → 1A 
                 202J 
                 3 
               
               
                 1C → 1A 
                 202H 
                 2 
               
               
                 1B → 1A 
                 202E 
                 1 
               
               
                 1B → 1A 
                 202G 
                 8 
               
               
                   
               
             
          
         
       
     
     Table 3 
     Root Path Costs 
       FIG. 2B  is an exemplary diagram illustrating active links of a newly created spanning tree in an optical ring according to one embodiment of the invention. In  FIG. 2B , the link  205 A has been discarded due to a failure. Now traffic is forwarded from the network element  201 D in accordance with a spanning tree  217  through the previously blocked port  202 K and along the previously discarded link  205 D. The root path costs used for new spanning trees at each network element are shown in Table 4 below. Based on Table 4, the network element  201 D is the only network element that creates a new spanning tree. The graph  213  illustrates the new spanning tree  217 . 
     
       
         
               
             
               
               
               
             
           
               
                 TABLE 4 
               
             
             
               
                   
               
               
                 Root Path Costs 
               
             
          
           
               
                 LINK 
                 PORT 
                 ROOT PATH COSTS 
               
               
                   
               
               
                 205D → 205A 
                 202A 
                 200 (default for failed link) 
               
               
                 205D → 205A 
                 202B 
                 6 
               
               
                 205C → 205A 
                 202I 
                 202 
               
               
                 205C → 205A 
                 202G 
                 2 
               
               
                 205B → 205A 
                 202D 
                 1 
               
               
                 205B → 205A 
                 202F 
                 207 
               
               
                   
               
             
          
         
       
     
       FIG. 3  is an exemplary diagram illustrating binding a spanning tree to VLANs according to one embodiment of the invention. In  FIG. 3 , a network element  301  includes a VLAN switch  311 , edge ports  305 A- 305 C, and trunk ports  307 A- 307 B. 
     The edge ports  305 A- 305 C respectively connect the network element to local area networks (LANs)  303 A- 303 C. The LAN  303 A includes a host  304 A with a MAC address  7 . The LAN  303 B includes a host  304 B with a MAC address  11 . The LAN  303 C includes a host  304 C with a MAC address  5  and a host  304 D with a MAC address  9 . 
     At a time  1 , spanning trees  315 A- 315 B are created. At a time  2 , the spanning tree  315 A is coupled to the VLAN switch  311  and bound to the trunk port  307 A. The spanning tree  315 B is coupled to the VLAN switch  311  and bound to the trunk port  307 B. At a time  3 , a generic attribute registration protocol (GARP) virtual local area network (VLAN) registration protocol (GVRP) module  317  is enabled on the trunk port  307 A- 307 B. At a time  4 , VLANs are defined in the VLAN switch  311 . A VLAN  21  is defined as including MAC addresses  5  and  7 . A VLAN  22  is defined as including MAC addresses  9  and  11 . At a time  5 , VLAN circuits are created between the edge ports  305 A- 305 C and the VLAN switch  311 . A VLAN circuit  309 A is created from the VLAN switch  311  to the edge port  305 A for the VLAN  21 . A VLAN circuit  309 B is created from the VLAN switch  311  to the edge port  305 B for the VLAN  22 . A VLAN circuit  309 C is created for each of the VLANs  21  and  22  between the port  305 C and the VLAN switch  311 . At a time  6 , the GVRP module  317  creates a VLAN circuit between the spanning tree  315 A and an unprotected data channel  341 A on the trunk port  307 A for the VLAN  21 . The GVRP module  317  also creates a VLAN circuit between the spanning tree  315 B and an unprotected data channel  341 B on the trunk port  307 B. 
       FIG. 4  is an exemplary diagram illustrating VLAN circuits and spanning trees in a optical ring according to one embodiment of the invention. In  FIG. 4 , an optical ring includes network elements  401 A- 401 D. The network elements  401 A- 401 D are connected with links having an unprotected data channel in the following manner: a link  403 A connects the network elements  401 A and  401 B, a link  403 B connects the network elements  401 B and  401 C, a link  403 C connects the network elements  401 A and  401 D, and a link  403 B connects the network elements  401 D and  401 A. 
     The network element  401 A includes a GVRP module  425 A, spanning trees  421 A- 421 B, a VLAN switch  423 A, trunk ports  409 A- 409 B, and an edge port  429 A. The trunk port  409 A connects to the link  403 A. The trunk port  409 B connects to the link  403 D. The edge port  429 A connects to a LAN  405 A. 
     The network element  401 B includes a GVRP module  425 B, spanning trees  421 C- 421 D, a VLAN switch  423 B, and trunk ports  409 C- 409 E. The trunk port  409 C connects the network element  401 D to the link  403 A. The trunk port  409 D connects the network element  401 C to the link  403 B. The trunk port  409 E connects the network element  401 B to another core network element in a different ring. 
     The network element  401 C includes a GVRP module  425 C, spanning trees  421 E- 421 F, a VLAN switch  423 C, trunk ports  409 F- 409 G, and an edge port  429 B. The edge port  429 B connects the network element  401 C to a local area network  405 C. The trunk ports  409 F connects the network element  401 C to the link  403 B. The trunk port  409 G connects the network element  401 C to the link  403 C. 
     The network element  401 D includes a GVRP module  425 D, spanning trees  421 G- 421 H, a VLAN switch  423 D, trunk ports  409 H- 409 I, and an edge port  429 C. The edge port  429 C connects the network element  401 D to a LAN  405 D. The trunk port  409 H connects the network element  401 D to the link  403 C. The trunk port  409 I connects the network element  401 D to the link  403 D. 
     In the network element  401 A, the spanning tree  421 A is bound to the trunk port  409 B and the spanning tree  421 B is bound to the trunk port  409 A. As described in  FIG. 3 , the spanning tree  421 B is associated with a VLAN  21  and the spanning tree  421 A is associated with a VLAN  22 . The VLAN switch  423 A creates VLAN circuits for the VLAN  21  and  22  to the edge port  429 A. The GVRP module  425 A creates VLAN circuits on the trunk ports  409 A and  409 B for the VLANs  21  and  22 . In the network elements  401 B- 401 D, the VLANs are learned from the network element  401 A. After learning the VLANs from the network element  401 A, the network elements  401 B- 401 D will create circuits in the same fashion that the network element  401 A created VLAN circuits. Alternatively, each of the VLANs are defined in the VLAN switches  423 B- 423 D respectively on the network elements  401 B- 401 D. After defining the VLANs within the network elements  401 B- 401 D, the VLAN circuits are created as described with respect to the network element  401 A. 
       FIGS. 5A-5B  are exemplary diagrams illustrating network elements in an optical ring learning MAC addresses for VLANs associated with different spanning trees according to one embodiment of the invention.  FIG. 5A  is an exemplary diagram illustrating MAC address learning in an optical ring according to one embodiment of the invention. In  FIG. 5A , an optical ring is comprised of network elements  501 A- 501 D. The network elements  501 A and  501 B are connected with a link  505 A. The network elements  501 B and  501 C are connected with a link  505 B. The network elements  501 C and  501 D are connected with a link  505 C. The network elements  501 D and  501 A are connected with a link  505 D. The network element  501 A is connected with a LAN  503 A via an edge port  502 A. The LAN  503 A includes a host  506 A of a VLAN  26  with a MAC address  6 . The network element  501 A utilizes a VLAN table  513 A. At a time  1 , the host  506 A sends a packet  509  addressed to a host with a MAC address of  9 . The packet  509  is received by the edge port  502 A at the network element  501 A. At a time  2 , the spanning tree associated with the VLAN  26  forwards the packet  509  to the trunk port  504 A, since the trunk port  504 B is blocked by the spanning tree. At a time  3 , the packet  509  is received at the network element  501 B via a trunk port  504 D and forwarded out the edge port  502 B and the trunk port  504 C. At this time, the network element  501 B modifies a VLAN table  513 B to indicate the MAC address  6  and trunk port  504 D for the VLAN  26 . At a time  4 , the packet  509  is received by the network element  501 C at a trunk port  504 E. The packet  509  is forwarded out the trunk port  504 F to eventually be received by a host  506 E with a MAC address  9 . The network element  501 C modifies a VLAN table  513 C to indicate MAC address  6  and the trunk port  504 E. 
       FIG. 5B  is an exemplary diagram illustrating MAC address learning in an optical ring continuing from  FIG. 5A  according to one embodiment of the invention. In  FIG. 5B , the machine  506 E responds to the machine  506 A with a packet  510 . At a time  1 , the network element  501 C receives the packet  510  and modifies the VLAN table  513 C. The network element  501 C modifies the VLAN table  513 C to include an entry for VLAN  26  indicating a MAC address of  9  and the trunk port  504 F. At a time  2 , the network element  501 B receives the packet  510  on the trunk port  504 C and forwards the packet to the trunk port  504 C and the edge port  502 B. The network element  501 B modifies the VLAN table  513 B to include an entry for the VLAN  26  that indicates MAC address  9  and trunk port  504 C. At a time  3 , the network element  501 A receives the packet  510  via the trunk port  504 A and forwards it to the edge port  502 A. The network element  501 A modifies the VLAN table  513 A to include an entry for the VLAN  26  that indicates MAC address  9  and the trunk port  504 A. 
     The network elements described in the Figures include memories, processors, and/or ASICs. Such memories include a machine-readable medium on which is stored a set of instructions (i.e., software) embodying any one, or all, of the methodologies described herein. Software can reside, completely or at least partially, within this memory and/or within the processor and/or ASICs. For the purpose of this specification, the term “machine-readable medium” shall be taken to include any mechanism that provides (i.e., stores and/or transmits) information in a form readable by a machine (e.g., a computer). For example, a machine-readable medium includes read only memory (“ROM”), random access memory (“RAM”), magnetic disk storage media, optical storage media, flash memory devices, electrical, optical, acoustical, or other forms of propagated signals (e.g., carrier waves, infrared signals, digital signals, etc.), etc. 
     While the invention has been described in terms of several embodiments, those skilled in the art will recognize that the invention is not limited to the embodiments described. For example, unprotected channels are described within the context of a single optical ring, but an unprotected channel may traverse multiple optical rings within an optical network. The method and apparatus of the invention can be practiced with modification and alteration within the spirit and scope of the appended claims. The description is thus to be regarded as illustrative instead of limiting on the invention.