The present invention relates to communication networks and in particular to broadcast protocols in local area networks.
Standard local communication networks comprise a plurality of bridging-devices and communication links. Each communication link connects between two or more bridging-devices or between a bridging-device and an end-station, e.g., a computer. Each bridging-device comprises a plurality of ports which serve as interfaces between the bridging-device and the links to which it is connected. When a source station sends a message to a destination station, the source station parses the message into frames and sends the frames to a nearest bridging-device which forwards the frames to one of its neighboring bridging-devices (bridging-devices which are directly connected by a common link are referred to herein as neighbors). The neighboring bridging-device forwards the frames to another bridging-device (which is its neighbor) until the frames finally reach the bridging-device connected to the destination station. In many cases, frames are broadcast to all the bridging-devices in a local network. In the context of the present application and claims the term xe2x80x9cbroadcast framesxe2x80x9d refers to any frames which are to be distributed throughout the network, including broadcast and multicast frames and frames with a unicast address for which a bridging-device does not recognize the address.
One requirement imposed in many cases on bridging-devices is modularity, i.e., they do not require changes when the topology of the network changes, for example, by adding new bridging-devices. A standard broadcast scheme involves having a bridging-device, which receives a broadcast frame, forward the frame through all its ports, except for the port through which the frame was received. This broadcast scheme operates properly only if the bridging-devices and links do not form a loop in the network. If the network includes a loop, a single frame may be repeatedly sent through the network and the network will fail. Such a situation is commonly referred to as a broadcast storm. The term loop is taken to mean in the following description and claims, at least three bridging-devices connected by links which forward data, such that there are at least two different paths along non-parallel links between each pair of the bridging-devices.
In many cases redundant links are added to networks, to be used in case one or more of the bridging-devices and/or links fail. A spanning tree algorithm is commonly used to dynamically block the ports leading to the redundant links and thus prevent the formation of loops. One common spanning tree algorithm is the 802.1D standard spanning tree algorithm (STA) which is described in xe2x80x9cInformation technologyxe2x80x94Telecommunications and information exchange between systemsxe2x80x94Local and metropolitan area networksxe2x80x94Media access control (MAC) bridgesxe2x80x9d, International Standard ISO/IEC 15802-3, 1998, ANSI/IEEE Std 802.1D, 1998 edition, the disclosure of which is incorporated herein by reference.
However, blocking the redundant links is wasteful in bandwidth since the redundant links could be used to pass messages and thus speed up the network operation. The blocking of redundant links is especially wasteful in networks which have a full-mesh topology and therefore may have many blocked links.
Many modem LAN bridging-devices support a feature named virtual local area networks (VLANs). Some or all of the messages sent through the network are given a VLAN ID which represents the VLAN to which the messages belong. The ports of the bridging-devices of the network are configured as active or blocking for each VLAN separately. VLANs allow a single physical network to operate as a plurality of independent networks. For example, a station may be connected to a network through a port in which only a VLAN X is enabled. The station therefore can only forward packets to, and receive packets from, stations which are connected to VLAN X. An emerging standard for VLANs is described in xe2x80x9cDraft Standard P802.1Q/D9, IEEE Standards for Local and Metropolitan Area Networks: Virtual Bridged Local Area Networksxe2x80x9d, 1998, the disclosure of which is incorporated herein by reference.
xe2x80x9cIEEE draft P802.3ad/D0.1, Supplement to Carrier Sense Multiple Access with Collision Depiction (CSMA/CD), Access Method and Physical Layer Specification: Link Aggregationxe2x80x9d, Dec. 30, 1998, pages 1-62, the disclosure of which is incorporated herein by reference, describes a scheme in which a plurality of parallel links, referred to as a Link Aggregation Group (LAG), connect between a pair of bridging-devices (and/or end stations). Broadcast frames sent between the pair of bridging-devices are always sent on only one of the links of the LAG, regardless of the source of the frame. A broadcast frame received through one of the parallel links is not forwarded through any of the parallel links so as to prevent the occurrence of a broadcast storm. This draft, however, only discusses broadcasting through parallel point to point links and does not describe avoidance of broadcast storms in bridged networks which include a plurality of links which connect between more than two bridging-devices and/or end stations.
It is an object of some preferred embodiments of the invention to provide a method for forwarding broadcast frames in a full-mesh-topology network, which method does not require blocking of links.
It is an object of some preferred embodiments of the invention to provide a method for forwarding broadcast frames in a network which includes loops, which method is free of the possibility of a broadcast storm.
It is an object of some preferred embodiments of the invention to provide a method for forwarding broadcast frames in a network which includes loops, which method is modular.
It is an object of some preferred embodiments of the invention to provide a method for aggregation of non-parallel links.
One aspect of some preferred embodiments of the present invention relates to restricting the distribution of broadcast frames, in full-mesh-topology networks and/or full-mesh-topology sub-networks (referred to herein as clusters). Bridging-devices, belonging to the full-mesh-topology cluster, forward broadcast frames according to the origin of the frames. Broadcast frames received by a cluster bridging-device from another cluster bridging-device are forwarded only to non-cluster bridging-devices. On the other hand, broadcast frames received from external bridging-devices (not belonging to the cluster) are preferably forwarded as usual through substantially all the ports of the receiving bridging-device (except the port through which the frame was received). Since the cluster bridging-devices are all connected to each other, when a first cluster bridging-device forwards a frame to a second cluster bridging-device the frame is also forwarded to all the other cluster bridging-devices. Therefore, the second cluster bridging-device does not need to send the frame to any of the cluster bridging-devices. The broadcast method described above avoids the generation of broadcast storms although the network includes physical loops.
One aspect of some preferred embodiments of the present invention relates to a broadcast protocol which operates in a cluster of a frame based local area network (LAN) which includes loops. Each bridging-device in the network forwards broadcast frames to neighboring bridging-devices according to a specific distribution table of the bridging-device. The bridging-devices to which the broadcast frames are forwarded are preferably determined responsive to the bridging-device from which the frames were received. The distribution tables are planned such that broadcast frames are forwarded to each of the bridging-devices in the cluster only once.
There is therefore provided in accordance with a preferred embodiment of the present invention, a method of distributing a broadcast frame within a network, including receiving the broadcast frame in a bridging-device of the network through a receiving port, and forwarding the frame to a group of bridging-devices selected responsive to whether the receiving port is an internal port which leads to bridging-devices included in a common cluster with the receiving bridging-device.
Preferably, forwarding to the group of bridging-devices includes forwarding through all the ports of the receiving bridging-device not including the receiving port, when the receiving port is not an internal port.
Preferably, forwarding to the group of bridging-devices includes forwarding through a group of ports which does not include internal ports of the receiving bridging-device, when the receiving port is an internal port.
Preferably, the bridging-devices of the cluster are connected with a full mesh topology. In a preferred embodiment, the cluster includes a stacked switch. Preferably, the bridging-devices of the cluster are controlled by a single processor. Alternatively, the bridging-devices of the cluster are each controlled by a separate processor.
Preferably, the group of bridging-devices is selected according to an entry to a forwarding table, which entry corresponds to an identity of the receiving port.
Preferably, forwarding to the group of bridging-devices includes, for frames received from a first bridging-device, forwarding to a second bridging-device which is not connected directly by an operative link to the first bridging-device. Preferably, the first and second bridging-devices are connected by an inoperative link.
Preferably, the group of bridging-devices is selected responsive to data with respect to connections between bridging-devices of the network, preferably, data on the failure of links. Preferably, the group of bridging-devices is selected according to an entry to a forwarding table which entry is selected responsive to the data with respect to connections of the network.
In a preferred embodiment, the group of bridging-devices is selected responsive to an identity of a bridging-device forwarding the frame to the receiving port.
There is further provided in accordance with a preferred embodiment of the present invention, a method of managing a cluster of bridging-devices and links including at least one loop of bridging-devices, including determining connectivity data with respect to connections between bridging-devices of the cluster, and blocking at least one link of the cluster for transmission of data frames, if the connectivity data fulfills a first condition, and not blocking any of the links of the cluster if the connectivity data fulfills a second condition.
Preferably, determining the connectivity data includes determining whether the cluster has a full mesh topology. Alternatively or additionally, determining the connectivity data includes determining a number of inoperable links in the cluster. Preferably, the first condition includes failure of at least a predetermined number of links in the cluster.
Preferably, blocking at least one link includes blocking a sufficient number of links so as to eliminate loops of unblocked links from the cluster.
There is further provided in accordance with a preferred embodiment of the present invention, a method of distributing a broadcast frame within a cluster of bridging-devices which includes at least one loop of unblocked nonparallel links and bridging-devices, including receiving the broadcast frame in a bridging-device belonging to the cluster, which bridging-device is part of the at least one loop, and forwarding the frame from the receiving bridging-device over at least one link which is part of the loop to neighboring bridging-devices.
Preferably, receiving the frame includes receiving the frame from a bridging-device external to the cluster. In a preferred embodiment, the cluster includes an entire local area network. Preferably, forwarding the link includes forwarding over a plurality of links which are part of the loop.
There is further provided in accordance with a preferred embodiment of the present invention, a method of distributing broadcast frames within a network by a bridging-device which has a plurality of ports leading to a plurality of neighboring bridging-devices, including receiving a broadcast frame through a receiving port, selecting fewer than all of the active ports in a group including one port for each neighboring bridging-device except for the bridging-device connected to the receiving port, independent of the contents of the frame, and forwarding the received broadcast frame through the selected ports.
Preferably, receiving the frame includes receiving the frame from a bridging-device included in a common cluster with the receiving bridging-device, the common cluster including at least one active loop.
Preferably, forwarding the frame includes forwarding the frame only to bridging-devices not included in the cluster.
Preferably, selecting the ports includes selecting responsive to an identity of the receiving port. Alternatively or additionally, selecting the ports includes selecting responsive to data regarding connections between bridging-devices of the network.
There is further provided in accordance with a preferred embodiment of the present invention, a method of distributing broadcast frames within a network by a bridging-device having a plurality of ports, including running at least one procedure which determines identities of ports which should be blocked to avoid having an unblocked loop in the network, and forwarding data broadcast frames through the ports which should be blocked according to all of the at least one procedures.
Preferably, running the at least one procedure includes running a single procedure.
Preferably, forwarding the frames includes forwarding through the links which should be blocked independent of the contents of the frames. Further preferably, forwarding the frames includes forwarding through the links which should be blocked independent of a VLAN with which the frames are associated.
Preferably, running the at least one procedure includes running a procedure which implements a spanning tree algorithm. Preferably, running the at least one procedure includes running a procedure which is implemented on substantially all the bridging-devices of the network.
Preferably, forwarding the data frames includes forwarding through ports of which identities were determined by the procedure only when a connectivity condition of the network is fulfilled. Further preferably, only when the network has a full mesh topology.
Preferably, the network has links and forwarding the data frames includes forwarding through ports of which identities were determined by the procedure only when all the links of the network are operative. Alternatively, forwarding the data frames includes forwarding through ports of which identities were determined by the procedure only if less than a predetermined number of links are inoperative.
There is further provided in accordance with a preferred embodiment of the present invention, a method of managing a cluster of bridging-devices within a network, including determining connectivity data with respect to connections between bridging-devices of the network, and changing the bridging-devices belonging to the cluster responsive to the connectivity data. Preferably, determining the connectivity data includes determining a failure of a link of the cluster.
Preferably, changing the bridging-devices included in the cluster includes removing a bridging-device from the cluster. Preferably, removing the bridging-device includes blocking ports of the removed bridging-device such that only a single port leads to the bridging-devices of the cluster.
Preferably, determining the connectivity data includes running a procedure which determines groups of bridging-devices which have a full mesh topology. Preferably, changing the bridging-devices included in the cluster includes adding a bridging-device to the cluster. Preferably, the bridging-devices of the cluster belong to a modular switch.