# US 6,724,734 B1 · Creating a spanning tree of a network including clusters > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 6,724,734 B1 - Document ID: US6724734B1 - Status: Granted - Kind: B1 - Application number: 09/333,403 - Filed: 1999-06-15 - Granted: 2004-04-20 - Earliest claimed: 1999-06-15 - Assignees: Avaya Communication Israel Ltd. - Inventors: Lior Shabtay; Benny Rodrig - Web page: https://patentgrep.com/patent/US6724734B1 ## CPC - H04L 45/02: Topology update or discovery - H04L 12/462: {LAN interconnection over a bridge based backbone} - H04L 12/4641: {Virtual LANs, VLANs, e.g. virtual private networks [VPN] (LAN interconnection over a bridge based backbone H04L12/462; encapsulation techniques H04L12/4633; routing of packets H04L45/00; packet switches H04L49/00; virtual private networks for security H04L63/0272)} - H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M) ## Abstract A method of implementing a distributed algorithm which is based on sending Bridge Protocol Data Units (BPDUs) only between neighboring bridging-devices in a network. The method includes sending BPDUs from a first bridging-device of the network to at least one non-neighboring second bridging-device, and determining a characteristic of the network responsive to the BPDUs. ## Claims ### Claim 1 A method of implementing a distributed algorithm which is based on sending Bridge Protocol Data Units (BPDUs) only between neighboring bridging-devices in a network, comprising: sending BPDUs from a first bridging-device of the network to at least one second bridging-device; determining, in the second bridging-device, information relating to a topology characteristic of the network responsive to the BPDUs; and forwarding the “BDPUs” from the second bridging-device to at least one third bridging-device; wherein the network comprises at least one cluster having cluster member bridging-devices, the cluster member bridging-devices comprising, at least one of the first bridging-device, second bridging-devices and third bridging-device,” and wherein sending the BPDUs comprises sending the BPDUs from a cluster member bridging-device to substantially all the bridging-devices in the cluster; and wherein sending the BPDUs comprises sending the BPDUs via an emulated port leading to an emulated link which is connected to substantially all the bridging-devices in the cluster. ### Claim 2 (depends on 1) A method according to claim 1, wherein the emulated link has a zero cost. ### Claim 3 (depends on 1) A method according to claim 1, wherein determining the characteristic of the network comprises determining information on a path to a root bridging-device. ### Claim 4 (depends on 3) A method according to claim 3, wherein determining the information on the path to the root comprises selecting the emulated port as a root port if the emulated port is not a designated port of the emulated link. ### Claim 5 (depends on 3) A method according to claim 3, wherein determining the information on the path to the root comprises choosing a path common to substantially all the bridging-devices in the cluster. ### Claim 6 (depends on 1) A method according to claim 1, wherein sending the BPDUs comprises defining a VLAN and sending the BPDUs as a broadcast along the VLAN. ### Claim 7 (depends on 1) A method according to claim 1, wherein sending the BPDUs comprises sending the BPDUs without substantial delay between sending by the first bridging-device and receiving by the at least one second bridging device. ### Claim 8 (depends on 1) A method according to claim 1, wherein sending the BPDUs comprises sending BPDUs with a multicast destination address. ### Claim 9 (depends on 1) A method according to claim 1, wherein sending the BPDUs comprises sending BPDUs substantially compatible with the 802.1D standard tree algorithm. ### Claim 10 A method of activating links which form a spanning tree in a network formed of bridging-devices and links, the network including at least one cluster of cluster-member bridging-devices, external bridging-devices not included in the cluster and external links which directly connect to at least one external bridging-device, comprising: sending messages between bridging-devices of the network; determining a link suitable for being part of the spanning tree which may be activated without forming a path of activated external links between two cluster-member bridging-devices of the at least one cluster; and activating the determined link. ### Claim 11 (depends on 10) A method according to claim 10, wherein determining the link comprises determining a root bridging-device and a lowest cost path to the root bridging-device from each of the bridging-devices in the network, the determined link being along a lowest cost path. ### Claim 12 (depends on 11) A method according to claim 11, wherein determining the lowest cost path comprises assuming a zero cost path between any two cluster-member bridging-devices belonging to the same cluster. ### Claim 13 A method of activating links of a network, comprising: determining a plurality of links which form a spanning tree of the network; and activating at least one link irrespective of the determined plurality of links, wherein activating the at least one link irrespective of the determined plurality of links comprises activating a link which connects two different clusters and further wherein activating the link which connects two different clusters comprises activating the link although it forms a loop in the network. ### Claim 14 (depends on 13) A method according to claim 13, wherein activating the at least one link irrespective of the determined plurality of links comprises activating the at least one link only for some types of messages. ### Claim 15 (depends on 14) A method according to claim 14, wherein activating the at least one link only for some types of messages comprises activating the link for messages of a specific VLAN. ### Claim 16 (depends on 14) A method according to claim 14, wherein activating the at least one link only for some types of messages comprises activating the link for only some types of messages for a predetermined period and thereafter activating the at least one link for substantially all types of messages. ### Claim 17 (depends on 13) A method according to claim 13, wherein activating the at least one link irrespective of the determined plurality of links comprises activating the at least one link before the determining of the plurality of links. ### Claim 18 (depends on 13) A method according to claim 13, wherein activating the at least one link irrespective of the determined plurality of links comprises activating internal links of a cluster. ### Claim 19 A method of activating links which form a spanning tree in a network formed of bridging-devices and links, the network including a cluster of cluster-member bridging-devices, external bridging-devices not included in the cluster and external links which directly connect to at least one external bridging-device, comprising: sending messages between bridging-devices of the network; waiting in each bridging-device a hold-time between sending successive messages from the bridging-device; and activating a plurality of links forming the spanning tree, wherein the total time until the spanning tree is formed is substantially equal to the time required if the cluster were replaced by a single bridging-device. ### Claim 20 (depends on 19) A method according to claim 19, wherein waiting the hold-time comprises waiting in at least one of the bridging-devices, different hold-times dependent on an identity of the bridging-device to which the successive messages are sent. ### Claim 21 (depends on 20) A method according to claim 20, wherein waiting the hold-time comprises waiting in cluster member bridging-devices, a first hold-time for messages sent to another cluster member bridging-device and a second, different, hold-time for messages sent to bridging-devices which are not cluster members. ### Claim 22 (depends on 19) A method according to claim 19, wherein sending the messages comprises sending at least some of the messages by a first bridging device responsive to receiving information in messages from other bridging devices which information induces sending the messages, and waiting the hold-time comprises waiting in the first bridging-device, different hold-times for different messages dependent on the identity of the bridging-device from which the information inducing sending a particular message was received. ### Claim 23 (depends on 24) A method according to claim 24, wherein generating the message comprises generating a BPDU message. ### Claim 24 A method of implementing a distributed spanning tree algorithm in a first bridging-device, comprising: receiving a spanning-tree-algorithm message from a second bridging-device; generating at least one message, including a message to a third bridging-device, responsive to the received message; determining a hold-time to wait before sending the generated message to the third bridging-device, from a plurality of available hold-times; and sending the message after the hold-time, wherein determining the hold-time comprises determining the hold-time responsive to the identity of at least one of the second bridging-device and the third bridging-device. ### Claim 25 (depends on 24) A method according to claim 24, wherein determining the hold-time comprises determining the hold-time responsive to whether the second bridging-device belongs to a common cluster with the first bridging-device. ### Claim 26 (depends on 24) A method according to claim 24, wherein determining the hold-time comprises determining the hold-time responsive to the identity of the third bridging-device. ### Claim 27 (depends on 26) A method according to claim 26, wherein determining the hold-time comprises determining the hold-time responsive to whether the third bridging-device belongs to a common cluster with the first bridging-device. ### Claim 28 A method of implementing a distributed spanning tree algorithm in a first bridging-device, comprising: receiving a spanning-tree-algorithm message from a second bridging-device; generating at least one message, including a message to a third bridging-device, responsive to the received message; determining a hold-time to wait before sending the generated message to the third bridging-device, from a plurality of available hold-times; and sending the message after the hold-time, wherein determining the hold-time comprises determining a standard hold-time if both the second and third bridging-devices do not belong to a common cluster with the first bridging-device. ### Claim 29 (depends on 28) A method according to claim 28, wherein determining the hold-time comprises determining a shortened hold-time if either the second or third bridging-devices belong to a common cluster with the first bridging-device. ### Claim 30 A cluster-member switch, comprising: a forwarding circuit; and a processor which runs a spanning tree algorithm code which generates and receives Bridge Protocol Data Units (BPDUs) in order to configure the forwarding circuit, and an intermediate software which alters at least some of the generated or received BPDUs, wherein the processor further determines a link suitable for being part of the spanning tree which may be activated without forming a path of activated external links between the cluster-member switch and at least one other cluster-member switch. ### Claim 31 (depends on 30) A cluster-member switch according to claim 30, wherein the intermediate software changes a destination address of the generated BPDUs to a broadcast, multicast or unknown unicast address. ### Claim 32 (depends on 30) A cluster-member switch according to claim 30, wherein the intermediate software changes a VLAN field of the generated BPDUs to a predetermined VLAN identity. ### Claim 33 (depends on 30) A cluster-member switch according to claim 30, wherein the intermediate software changes a port indication of some received BPDUs to an emulated port identity. ### Claim 34 (depends on 33) A cluster-member switch according to claim 33, wherein the intermediate software reports a zero cost for the emulated port. ### Claim 35 (depends on 30) A cluster-member switch according to claim 30, wherein the intermediate software changes an indication of the identity of a bridging-device sending at least one received BPDU. ### Claim 36 (depends on 35) A cluster-member switch according to claim 35, wherein the intermediate software changes the indication of the identity of the sending bridging-device responsive to a required selection of a root port. ### Claim 37 (depends on 35) A cluster-member switch according to claim 35, wherein the intermediate software changes the indication of the identity of the sending bridging-device to a minimal or maximal value. ### Claim 38 (depends on 30) A cluster-member switch according to claim 30, wherein the spanning tree algorithm (STA) code comprises a standard STA code. ### Claim 39 (depends on 30) A cluster-member switch according to claim 30, wherein the cluster bridging-device comprises a switch-module of a modular switch. ### Claim 40 (depends on 1) A method according to claim 1, wherein sending the BPDUs to the at least one second bridging-device and forwarding the BPDUs to the third bridging-device comprise sending and forwarding along links belonging to a common VLAN. ### Claim 41 (depends on 1) A method according to claim 1, wherein the at least one second bridging-device comprises a non-neighboring bridging device.