Abstract:
A multicasting network includes a number of routers that are connected together to form a ring. The routers include a source router that identifies incoming multicasting data packets, and forwards the multicasting data packets in both directions on the ring. The routers also include forwarding routers that identify incoming multicasting data packets, and forwards the multicasting data packets in only one direction on the ring. Further, each ring has two terminating routers that receive forwarded data packets on two external nodes, and accept forwarded data packets from only a first external node and not from a second external node. When a fault condition is detected that prevents data packets from being forwarded in a first direction on the ring, the routers down stream of the fault condition reconfigure themselves to receive forwarded data packets from the second direction.

Description:
BACKGROUND OF THE INVENTION  
         [0001]    1. Field of the Invention  
           [0002]    The present invention relates to a multicasting network and, more particularly, to a fault-tolerant multicasting network.  
           [0003]    2. Description of the Related Art  
           [0004]    [0004]FIG. 1 shows a block diagram that illustrates a prior-art communications network  100 . As shown in FIG. 1, network  100  includes a number of customer premises  110 , a central office  112  that is connected to the customer premises  110 , and an ATM network  114  that is connected to the central office  112 .  
           [0005]    In this example, each customer premise  110  has a data device  120 , such as a personal computer, a standard telephone  122 , and a xDSL modem  124  that is connected to the data device  120  and the telephone  122 . In operation, the xDSL modem  124  at each customer premise  110  splits the incoming signals received from central office  112  into incoming data signals for the data device  120  and incoming plain old telephone service (POTS) signals for the telephone  122 . In addition, the modem  124  transmits outgoing signals to central office  112  by combining the outgoing data signals from the data device  120  and the outgoing POTS signals from the telephone  122 .  
           [0006]    Referring again to FIG. 1, central office  112  has a digital subscriber line access multiplexer (DSLAM)  130  that is connected to the xDSL modems  124  in the customer premises  110 , and an asynchronous transfer mode (ATM) switch  132  that is connected to DSLAM  130 . In addition, central office  112  has an ATM router  134  that is connected to ATM switch  132  and the ATM network  114 .  
           [0007]    In operation, DSLAM  130  splits the outgoing signals received from each customer premise  110  into output POTS signals and output data signals. The output POTS signals are sent to the central office telephone switching system, while the output data signals are multiplexed together with the output data signals from the other customer premises to form an outgoing data stream.  
           [0008]    DSLAM  130  also demultiplexes an incoming data stream from ATM switch  132  to form input data signals for each customer premise  110 . Further, DSLAM  130  also combines the demultiplexed input data signals for a customer premise  110  with input POTS signals received from the central office switching system for the customer premise  110  to form the incoming signals for the customer premise  110 .  
           [0009]    In addition, ATM switch  132  receives the incoming data stream from DSLAM  130  and converts the data from a local data format to an ATM format. In the ATM format, data is loaded into fixed length packets known as cells. Each cell has a header section and a data section. The header section, in turn, includes a virtual connection identifier (VCI) that identifies the destination of the cell, and a virtual path identifier (VPI) that also identifies the destination of the cell. ATM switch  132  also converts received data from the ATM format to the local data format.  
           [0010]    Further, router  134  examines the header section of the ATM cell and, based on the destination of the cell, forwards the cell to one of a number of other routers that are connected to ATM network  114 . Router  134  also identifies ATM cells that are addressed to the downstream customer premises  110 , and forwards those cells to ATM switch  132 .  
           [0011]    Central office  112  can be implemented with, for example, the Telliant 5000 Central Office System manufactured by Advanced Fiber Communications. One feature of the Telliant 5000 Central Office System is that router  134  includes a controller that has a multicast forwarding circuit. In the multicast forwarding circuit, router  134  identifies a received multicast data packet (e.g., using the internet group management protocol (IGMP)), and forwards the multicast data packet to one or more predefined outputs.  
           [0012]    [0012]FIG. 2 shows a block diagram that illustrates a prior-art network  200 . As shown in FIG. 2, network  200  has a number of routers  210 , including routers  210 - 1  through  210 - 7 , and a number of high-speed data lines  212  that are connected to the routers  210  to form an ATM ring  214 . In the FIG. 2 example, the routers  210  have a controller that has a multicast forwarding circuit, such as the routers in a Telliant 5000 Central Office System.  
           [0013]    The high-speed data lines  212  can be implemented with, for example, fiber optic cables to form ATM ring  214  as a synchronous optical network (SONET) ATM ring. When implemented as a SONET ATM ring, an OC-12 interface can be used at each router  210  to provide a capacity of approximately 600 Mbps.  
           [0014]    There are two types of SONET ATM rings conventionally used: a unidirectional ATM switched ring (UASR) and a bidirectional ATM switched ring (BASR). The SONET UASR is defined by Bellcore standard GR-1230-CORE, while the SONET BASR is defined by Bellcore standard GR-1400-CORE.  
           [0015]    A SONET UASR utilizes two fiber optic cables that run between the routers  210 : a working fiber and a protective fiber. In operation, the same information is transmitted on the working and protective fibers in opposite directions. When a fault, such as a cut cable or an equipment failure, is detected in or with a segment of a working fiber, the adjacent protective fiber is used to allow data to continue on to the destination routers  210 .  
           [0016]    Similarly, a SONET BASR ring has four fiber optic cables that run between the routers  210 : two working fibers and two protective fibers. One working fiber and one protective fiber are clockwise fibers, while one working fiber and one protective fiber are counter-clockwise fibers. As above, when a working fiber fails, traffic is diverted to the protective fiber. Thus, SONET rings have the ability to heal themselves and are therefore highly survivable.  
           [0017]    Referring again to FIG. 2, since the routers  210  include the multicast forwarding circuit, one router  210  in the ring is logically defined to be a source router  210 S, while the remaining routers  210  in the ring are logically defined to be forwarding routers  210 F. The source router  210 S identifies a received multicast data packet, passes the data packet on to the ATM switch ( 132 ) connected to the DSLAM, and forwards the multicast data packet on in both directions on ring  214  to the other routers  210 .  
           [0018]    One the other hand, the forwarding routers  210 F identify a forwarded multicast data packet, pass the data packet on to the ATM switch connected to the DSLAM, and forward the multicast data packet on in only one direction on the ring. In addition, although a forwarding router  210 F can only forward a multicast data packet in one direction on ring  214 , the forwarding router  210 F can forward the multicast data packet on to other routers  210 .  
           [0019]    Further, two forwarding routers  210 F in ring  214  are also logically defined to be terminating routers  210 T. Terminating routers  210 T receive multicast data packets from two directions on the ring, and only process the multicast data packets from one direction, ignoring the packets from the other direction.  
           [0020]    In the example shown in FIG. 2, router  210 - 1  is logically defined to be source router  210 S, while routers  210 - 2  through  210 - 6  are logically defined to be forwarding routers  210 F. In addition, routers  210 - 3  and  210 - 6  are both logically defined to be terminating routers  210 T.  
           [0021]    In operation, router  210 - 1  receives a data packet, identifies the packet as a multicast data packet, passes the data packet on to the ATM switch connected to the DSLAM, and forwards the multicast data packet to routers  210 - 2  and  210 - 4 .  
           [0022]    Router  210 - 2  receives the data packet, and identifies the packet as a multicast data packet. In addition, router  210 - 2  passes the packet on to the ATM switch connected to the DSLAM, and forwards the multicast data packet to router  210 - 3 . Router  210 - 3  does the same as router  210 - 2 , and forwards the multicast data packet on to router  210 - 6 . However, as a terminating router, router  210 - 6  ignores the multicast data packet output by router  210 - 3 .  
           [0023]    Similarly, router  210 - 4  receives the data packet, and identifies the packet as a multicast data packet. Router  210 - 4  also passes the multicast data packet on to the ATM switch connected to the DSLAM, and forwards the multicast data packet to router  210 - 5 . Router  210 - 5  does the same as router  210 - 4 , and forwards the multicast data packet on to router  210 - 6 . Router  210 - 6  does the same as router  210 - 5 , and forwards the multicast data packet on to router  210 - 3 .  
           [0024]    However, as a terminating router, router  210 - 3  ignores the multicast data packet output by router  210 - 6 . In addition, although router  210 - 5  can only forward the multicast data packet to router  210 - 6  as the next router in ring  214 , router  210 - 5  can also forward the multicast data packet to router  210 - 7 .  
         SUMMARY OF THE INVENTION  
         [0025]    The present invention provides a fault-tolerant multicasting network. The multicasting network includes a plurality of routers that are connected to form a ring. A router in accordance with the present invention includes a plurality of interfaces that include a first interface and a second interface. The first interface is connected to a first medium, while the second interface is connected to a second medium.  
           [0026]    The first interface has a first memory location that stores a value that indicates whether the first interface can accept a data packet received from the first medium, and a first look up table that identifies the second interface. The first interface also has a first controller that identifies the second interface from the look up table when the memory location indicates that the first interface can accept a received data packet from the first medium, and forwards the received data packet to the second interface when the first memory location indicates that the first interface can accept the received data packet from the first medium. The first interface also has first line sense circuitry that is electrically connected to the first medium that detects fault conditions.  
           [0027]    The present invention also includes a router interface that has a memory location that stores a value that indicates whether the router interface can accept a data packet received from a medium. The router interface also has a look up table that can identify a forwarding router interface, and line sense circuitry that is electrically connected to the medium to detect fault conditions. The line sense circuitry generates a back up mode packet when the router interface can accept the received data packet from the medium and the line sense circuitry detects a fault condition.  
           [0028]    Further, the router interface also includes a controller that identifies the forwarding router interface from the look up table when the memory location indicates that the router interface can accept a received data packet from the medium, and forwards the received data packet to the forwarding router interface when the memory location indicates that the router interface can accept the received data packet from the first medium. The controller forwards the back up mode packet to the forwarding router interface, and setsg the memory location to indicate that the router interface can not accept a data packet received from the medium.  
           [0029]    The present invention also includes a method of responding to faults detected by a router that forwards data packets. The router has a plurality of interfaces that include a first interface and a second interface. The first interface is connected to a first medium, while the second interface is connected to a second medium.  
           [0030]    In addition, the first interface has a first memory location that stores a value that indicates whether the first interface can accept a data packet received from the first medium, and first line sense circuitry that is electrically connected to the first medium that detects fault conditions. The method comprises the steps of generating a back up mode packet when the first line sense circuitry detects a fault condition, and forwarding the back up mode packet to the second interface. Further, the method includes the step of setting the first memory location to indicate that the first interface can not accept a data packet received from the first medium.  
           [0031]    A better understanding of the features and advantages of the present invention will be obtained by reference to the following detailed description and accompanying drawings that set forth an illustrative embodiment in which the principles of the invention are utilized. 
       
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0032]    [0032]FIG. 1 is a block diagram illustrating a prior-art communications network  100 .  
         [0033]    [0033]FIG. 2 is a block diagram illustrating a prior-art network  200 .  
         [0034]    [0034]FIG. 3 is a block diagram illustrating an example of a multicasting network  300  in accordance with the present invention.  
         [0035]    [0035]FIG. 4 is a block diagram illustrating an example of router  310  in accordance with the present invention.  
         [0036]    [0036]FIG. 5 is a block diagram illustrating an example of network  300  following a cable cut in accordance with the present invention.  
         [0037]    [0037]FIG. 6 is a block diagram illustrating an example of network  300  after router  310 - 6  has reversed its input and output circuits in accordance with the present invention. 
     
    
     DETAILED DESCRIPTION OF THE INVENTION  
       [0038]    [0038]FIG. 3 shows a block diagram that illustrates an example of a multicasting network  300  in accordance with the present invention. As shown in FIG. 3, network  300  has a number of routers  310 , including routers  310 - 1  through  310 - 7 , and a number of high-speed data lines  312  that are connected to the routers  310  to form an ATM ring  314 .  
         [0039]    Each router  310  can be connected to an ATM switch which, in turn, is connected to a DSLAM as described above with respect to central office  112 . In addition, the high-speed data lines  312  can be implemented with, for example, fiber optic cables to form ATM ring  314  as a synchronous optical network (SONET) ATM ring. Ring  314  can be implemented as, for example, a UASR or a BASR with an OC-12 or higher interface.  
         [0040]    In operation, the routers  310  in ring  314  forward multicast data packets. As a result, one router  310  in ring  314  is logically defined to be a source router  310 S, while the remaining routers  310  in ring  314  are logically defined to be forwarding routers  310 F. The source router  310 S identifies a received multicast data packet, passes the data packet on to the ATM switch connected to the DSLAM, and forwards the multicast data packet on in both directions on ring  314  to the other routers  310 .  
         [0041]    The forwarding routers  310 F identify a received multicast data packet, pass the data packet on to the ATM switch connected to the DSLAM, and forward the multicast data packet on in only one direction on ring  314 . In addition, although a forwarding router  310 F can only forward a multicast data packet in one direction on ring  314 , the forwarding router  310 F can forward the multicast data packet on to other routers  310 .  
         [0042]    Further, two forwarding routers  310 F in ring  314  are also logically defined to be terminating routers  310 T. Terminating routers  310 T receive multicast data packets from two directions on ring  314 , and only process the multicast data packets from one direction, ignoring the packets from the other direction.  
         [0043]    In the example shown in FIG. 3, router  310 - 1  is logically defined to be source router  310 S, while routers  310 - 2  through  310 - 6  are logically defined to be forwarding routers  310 F. In addition, routers  310 - 3  and  310 - 6  are both logically defined to be terminating routers  310 T.  
         [0044]    As a result, router  310 - 1  receives a data packet, identifies the packet as a multicast data packet, passes the data packet on to the ATM switch connected to the DSLAM, and forwards the multicast data packet to routers  310 - 2  and  310 - 4 .  
         [0045]    Router  310 - 2  receives the data packet, and identifies the packet as a multicast data packet. In addition, router  310 - 2  passes the packet on to the ATM switch connected to the DSLAM, and forwards the multicast data packet to router  310 - 3 . Router  310 - 3  does the same as router  310 - 2 , and forwards the multicast data packet on to router  310 - 6 . However, as a terminating router, router  310 - 6  ignores the multicast data packet output by router  310 - 3 .  
         [0046]    Similarly, router  310 - 4  receives the data packet, and identifies the packet as a multicast data packet. Router  310 - 4  also passes the multicast data packet on to the ATM switch connected to the DSLAM, and forwards the multicast data packet to router  310 - 5 . Router  310 - 5  does the same as router  310 - 4 , and forwards the multicast data packet on to router  310 - 6 . Router  310 - 6  does the same as router  310 - 5 , and forwards the multicast data packet on to router  310 - 3 .  
         [0047]    However, as a terminating router, router  310 - 3  ignores the multicast data packet output by router  310 - 6 . In addition, although router  310 - 5  can only forward the multicast data packet to router  310 - 6  as the next router on the ring, router  310 - 5  can also forward the multicast data packet to router  310 - 7 .  
         [0048]    [0048]FIG. 4 shows a block diagram that illustrates an example of router  310  in accordance with the present invention. As shown in the FIG. 4 example, router  310  has a number of interfaces  410  that include a first interface  410 A, a second interface  410 B, a third interface  410 C, and a fourth interface  410 D. (A greater or lesser number of interfaces may be included.) The interfaces  410 A- 410 B are internally connected to each other such that each interface  410 A- 410 D can forward a data packet to any of the remaining interfaces  410 A- 410 D of router  310 .  
         [0049]    The first interface  410 A, which is connected to an external medium E 1 , such as a fiber optic cable, includes a memory location M 1  that stores a value that indicates whether interface  410 A can accept a data packet received from external medium E 1 , and a look up table  412 A that can identify other interfaces  410  of router  310 .  
         [0050]    Further, interface  410 A includes a controller  414 A that has a multicast packet detection circuit, a forwarding circuit, and a transmission circuit. When memory location M 1  indicates that interface  410 A can accept a data packet from external medium E 1 , controller  414 A detects and forwards multicast data packets received from medium E 1  to one of the other internal interfaces  410  as defined in look up table  412 A.  
         [0051]    On the other hand, when memory location M 1  indicates that interface  410 A can not accept a data packet from external medium E 1 , controller  414 A drops multicast packets that are received from medium E 1 . The transmitting circuit, in turn, receives data packets from other interfaces  410  of router  310  and transmits those packets onto external medium E 1 .  
         [0052]    Similarly, the second interface  410 B, which is connected to an external medium E 2 , such as a fiber optic cable, includes a memory location M 2  that stores a value that indicates whether interface  410 B can accept a data packet received from external medium E 2 , and a look up table  412 B that can identify other interfaces  410  of router  310 .  
         [0053]    Further, interface  410 B includes a controller  414 B that has a multicast packet detection circuit, a forwarding circuit, and a transmission circuit. When memory location M 2  indicates that interface  410 B can accept a data packet from external medium E 2 , controller  414 B detects and forwards multicast data packets received from medium E 2  to one of the other internal interfaces  410  as defined in look up table  412 B.  
         [0054]    On the other hand, when memory location M 2  indicates that interface  410 B can not accept a data packet from external medium E 2 , controller  414 B drops multicast packets that are received from medium E 2 . The transmitting circuit, in turn, receives data packets from other interfaces  410  of router  310  and transmits those packets onto external medium E 2 .  
         [0055]    The third interface  410 C, which is connectable to an external medium, includes a memory location M 3  that stores a value that indicates whether interface  410 C can accept a data packet received from an external medium, and a look up table  412 C that can identify other interfaces  410  of router  310 . Further, interface  410 C includes a controller  414 C that has a multicast packet detection circuit, a forwarding circuit, and a transmission circuit.  
         [0056]    The fourth interface  410 D, which is connectable to an external medium, includes a memory location M 4  that stores a value that indicates whether interface  410 D can accept a data packet received from an external medium, and a look up table  412 D that can identify other interfaces  410  of router  310 . Further, interface  410 D includes a controller  414 D that has a multicast packet detection circuit, a forwarding circuit, and a transmission circuit.  
         [0057]    For example, with reference to FIG. 3, during normal multicast operation, the interface of router  310 - 3  that is connected to router  310 - 2  is input enabled (the memory location indicates that packets can be received from router  310 - 2  via the external medium), and has an associated look up table that contains one entry that identifies the interface of router  310 - 3  that is connected to router  310 - 6 . As a result, when the interface receives multicast packets from router  310 - 2 , the controller passes on the packets to the interface that is connected to router  310 - 6 , which then transmits the packets to router  310 - 6 .  
         [0058]    On the other hand, the interface of router  310 - 6  that is connected to router  310 - 3  is not input enabled (the memory location indicates that packets can not be received from router  310 - 3  via the external medium). As a result, when the interface of router  310 - 6  that is connected to router  310 - 3  receives a packet from router  310 - 3 , the controller of the interface of router  310 - 6  that is connected to router  310 - 3  drops the packet.  
         [0059]    Referring back to FIG. 4, interface  410 A also includes line sense circuitry  416 A that detects fault conditions on external medium E 1 . Similarly, interfaces  410 B,  410 C, and  410 D have line sense circuitry  416 B,  416 C, and  416 D, respectively. Line sense circuitry  416 B detects fault conditions on external medium E 2 , while circuitry  416 C and  416 D detect faults of a medium connected to the interfaces.  
         [0060]    For example, assume that interface  410 A can accept a multicast data packet from medium E 1 , interface  410 B can not accept a data packet from medium E 2 , and look up table  412 A identifies interface  410 B. During normal multicasting operation, interface  410 A receives and forwards data packets to interface  410 B, which then transmits the data packets to medium E 2 .  
         [0061]    When a fault condition, such as a cut cable or equipment failure, is detected by interface  410 A, line sense circuitry  416 A generates a back up mode packet, and passes the back up mode packet to controller  414 A. Once received, controller  414 A passes the back up mode packet to interface  410 B, and changes memory location M 1  to indicate that interface  410 A can not accept a data packet from external medium E 1 .  
         [0062]    When interface  410 B receives the back up mode packet, controller  414 B recognizes the back up mode packet, transmits the back up mode packet onto external medium E 2  to the next router  310 , and sets memory location M 2  to indicate that interface  410 B can accept a data packet from external medium E 2 .  
         [0063]    [0063]FIG. 5 shows a block diagram that illustrates an example of a network  300  following a cable cut in accordance with the present invention. As shown in FIG. 5, network  300  has a cut cable segment between routers  310 - 4  and  310 - 5 . During a multicasting session, the line sense circuitry monitors the condition of the fiber optic cable input to router  310 .  
         [0064]    When the line sense circuitry of the interface of router  310 - 5  that is connected to router  310 - 4  detects the fault condition, the interface outputs a back up mode packet BMP to the interface of router  310 - 5  that is connected to router  310 - 6 , and sets its memory location to indicate that the interface can not accept data packets from router  310 - 4 . The interface of router  310 - 5  that is connected to router  310 - 6  then transmits the back up mode packet BMP to router  310 - 6 , and sets its memory location to indicate that the interface can accept data packets from router  310 - 6 .  
         [0065]    The interface of router  310 - 6  that receives the back up mode packet BMP from router  310 - 5  recognizes the packet, forwards the back up mode packet BMP to the interface of router  310 - 6  that is connected to router  310 - 3 , and sets its memory location to indicate that the interface can not accept data packets from router  310 - 5 .  
         [0066]    The interface of router  310 - 6  that is connected to router  310 - 3  recognizes the packet, transmits the back up mode packet BMP to the interface of router  310 - 3  that is connected to router  310 - 6 , and sets its memory location to indicate that the interface can accept data packets from router  310 - 3 .  
         [0067]    The interface of router  310 - 3  that is connected to router  310 - 6  drops the back up mode packet BMP because the interface of router  310 - 3  that is connected to router  310 - 6  is not input enabled (the memory location indicates that packets can not be received from router  310 - 6  via the external medium).  
         [0068]    [0068]FIG. 6 shows a block diagram that illustrates an example of network  300  after router  310 - 6  has reversed its input and output interfaces in accordance with the present invention. As shown in FIG. 6, after the interface of router  310 - 6  that is connected to router  310 - 3  has set its memory location to indicate that data packets can now be receivied, the multicast data packets from router  310 - 3  that were originally ignored by router  310 - 6  are now received by router  310 - 6 .  
         [0069]    The interface of router  310 - 6  that is connected to router  310 - 3  identifies the packet as a multicast data packet, and passes the multicast data packet on to the ATM switch connected to the DSLAM. In addition, the interface checks its look up table, and passes the multicast data packets on to the interface which is connected to router  310 - 5 , which then transmits the packets to router  310 - 5 .  
         [0070]    Router  310 - 5  does the same as router  310 - 6 , and forwards the multicast data packet on to router  310 - 7 . Thus, when a fault condition is detected in a multicasting session, the line sense circuits in the effected routers respond to the condition so that the effected routers can be quickly reconfigured to maintain a continual flow of multicast data to the effected routers.  
         [0071]    Once the broken cable or equipment failure has been fixed and the user wants ring  314  to return to the original normal mode of operation, the user manually configures router  310 - 6  to go back to the normal mode. Specifically, the user sets the memory location to indicate that the interface connected to router  310 - 5  can now accept data packets from router  310 - 5 , while the interface that is connected to router  310 - 3  can no longer accept data packets from router  310 - 3 .  
         [0072]    In addition, as shown in FIG. 3, router  310 - 6  sends out a normal mode packet NMP to router  310 - 5  which, in turn, sets its memory location to indicate that the interface connected to router  310 - 4  can now accept data packets from router  310 - 4 , while the interface connected to router  310 - 6  can no longer accept data packets from router  310 - 6 .  
         [0073]    Further, router  310 - 5  also forwards the normal mode packet NMP to router  310 - 4 . However, since the interface of router  310 - 4  is not input enabled (the memory location indicates that packets can not be received from the external medium), router  310 - 4  ignores the normal mode packet NMP from router  310 - 5 . At this point, the network reverts back to the original operating condition.  
         [0074]    It should be understood that the above descriptions are examples of the present invention, and that various alternatives of the invention described herein may be employed in practicing the invention. Thus, it is intended that the following claims define the scope of the invention and that structures and methods within the scope of these claims and their equivalents be covered thereby.