High-speed mesh connected local area network

Claim 2

A mesh connected local area network for interconnecting a multiplicity of hosts, said network comprising: a multiplicity of switch means for simultaneously routing a multiplicity of data packets between hosts in the network; each switch means including a multiplicity of port means for coupling the switch means to other switch means and hosts, and a nonblocking crossbar switch for simultaneously coupling and routing data packets between a multiplicity of selected pairs of said port means; said hosts and switch means together comprising network members; and a multiplicity of point to point link means for interconnecting said switch means and the hosts in said network, each point to point link means providing a communication channel between two of said network members; each said port means including buffer means for buffering data packets received by said switch means at said port means and cut-through means for beginning to retransmit received data packets through said nonblocking crossbar switch before the end of said received data packet has been received.

Claim 3

The mesh connected local area network of claim 1, each said data packet having a specified host to which said data packet is being sent, each said switch means including routing means for defining, in accordance with predefined criteria, legal data packet transmission routes through said network; said routing means defining a subset of said port means of said switch means through which a received data packet can be retransmitted, said subset of port means being a function of the port means of said switch which receives said data packet and the host to which said data packet is being sent.

Claim 4

The mesh connected local area network of claim 1, said multiplicity of link means including spanning tree links and a multiplicity of additional links; said interconnected multiplicity of switch means and said spanning tree links together comprising a spanning tree in which one of said switch means is designated the root of said spanning tree; each said data packet having a specified host to which said data packet is being sent; each said switch means including routing means for defining legal data packet transmission routes through said network; said routing means including switch ordering means for defining which of two specified switch means has a better position in said spanning tree and which has a worse position; said routing means further including configuring means, coupled to said switch ordering means, for denoting each link means coupling a host to said switch as an up link, for denoting each link means coupling said switch to another switch with a better position in said spanning tree as an up link, and for denoting each link means coupling said switch to another switch with a worse position in said spanning tree as a down link; said routing means further including means for forwarding data packets received on any of said up links on a selected one of said up and down links, and means for forwarding data packets received on any of said down links on a selected one of said down links; whereby said routing means provides deadlock free routing of data packets through said mesh connected local area network.

Claim 5

The mesh connected local area network of claim 1, said multiplicity of link means including spanning tree links and a multiplicity of additional links; said interconnected multiplicity of switch means and said spanning tree links together comprising a spanning tree in which one of said switch means is designated the root of said spanning tree; said network further including switch ordering means for defining, for any two specified ones of said switches means, which of said specified switches has a better position in said spanning tree and which has a worse position; each said link means which interconnects two of said switch means including an up channel and a down channel which transmit data packets in opposite directions between said switch means; said up channel transmitting data packets from a switch means in a worse position to a switch means in a better position; each said switch means including routing means for forwarding a packet toward a specified one of said network members so that the path by which said packet is transmitted through said network comprises zero or more up channels followed by zero or more down channels; whereby said routing means provides deadlock free routing of data packets through said mesh connected local area network.

Claim 6

The mesh connected local area network of claim 4, said switch means including port status means for denoting which of said port means is available for retransmitting a data packet; said routing means including route selection means for comparing said subset of said port means of said switch means through which a received data packet can be retransmitted with said port status means and for routing said received data packet through a port means which is included in said subset of said port means and which is available for retransmitting a data packet.

Claim 7

The mesh connected local area network of claim 5, said route selection means including means for periodically comparing said subset of said port means of said switch means through which a received data packet can be retransmitted with said port status means until one of the port means denoted as available matches one of said subset of said port means, and then routing said received data packet through the matching port means; whereby said switch means provides low latency retransmission of data packets.

Claim 8

The mesh connected local area network of Claim 1, said multiplicity of link means including spanning tree links and a multiplicity of additional links; said interconnected multiplicity of switch means and said spanning tree links together comprising a spanning tree in which one of said switch means is designated the root of said spanning tree; said data packets including data packets which are sent to a single specified one of said hosts in said network and broadcast data packets which are to be sent to all said hosts in said network; each said switch means including routing means for defining legal data packet transmission routes through said network; said routing means including configuring means for denoting two broadcast packet transmission routes, including means for designating as an uplink port one port means of said switch means which couples said switch means to another switch means that is closer to said root of said spanning tree, in accordance with predefined criteria, and for denoting as downlink ports each port means which is coupled to the uplink port of other ones of said switch means; said routing means of each said switch means, except said switch means designated as said root of said network, further including route selection means for routing broadcast data packets received by said uplink port to all of said downlink ports, and for routing to said uplink port broadcast data packets received by any of said port means other than said uplink port.

Claim 9

The mesh oonnected local area network of Claim 7, said routing means of said switch means designated as said root of said network further including route selection means for routing all broadcast data packets received by said switch means to all of said downlink ports.

Claim 10

The mesh connected local area network of claim 7, wherein each said switch means includes means for simultaneously retransmitting received broadcast data packets through all of said downlink ports.

Claim 11

The mesh connected local area network of claim 1, said data packets including data packets which are sent to a single specified one of said hosts in said network and broadcast data packets which are to be sent to all said hosts in said network; said broadcast data packets having a predefined maximum size; said buffer means having more than sufficient room to store an entire broadcast data packet of said predefined maximum size and means for indicating when said buffer means has sufficient room to receive an entire broadcast data packet; said port means including flow control means coupled to said buffer means for sending flow control signals to a network member coupled to said port means, said flow control signals including stop flow signals requiring said network member to stop transmitting data packets to said port means and start flow signals allowing said network member to resume sending data packets to said port means; said flow control means including means for sending start flow signals only when said buffer means has sufficient room to receive an entire broadcast data packet.

Claim 12

The mesh connected local area network of claim 1, said port means including means for receiving said flow control signals sent by a network member coupled to said port means, and means for stopping the transmission of a data packet when a stop flow signal is received from said network member, unless said data packet is a broadcast packet.

Claim 13

A mesh connected local area network for interconnecting a multiplicity of hosts, said network comprising: a multiplicity of switch means for simultaneously routing a multiplicity of data packets between hosts in the network; each switch means including a multiplicity of port means for coupling the switch means to other switch means and hosts, and a nonblocking crossbar switch for simultaneously coupling and routing data packets between a multiplicity of selected pairs of said port means; said hosts and switch means together comprising network members; and a multiplicity of point to point link means for interconnecting said switch means and the hosts in said network, each point to point link means providing a communication channel between two of said network members; each said data packet having a specified host to which said data packet is being sent; each said switch means including routing means for defining, in accordance with predefined criteria, legal data packet transmission routes through said network; said routing means defining a subset of said port means of said switch means through which a received data packet can be retransmitted, said subset of port means being a function of the port means of said switch which receives said data packet and the host to which said data packet is being sent.

Claim 14

A mesh connected local area network for interconnecting a multiplicity of hosts, said network comprising: a multiplicity of switch means for simultaneously routing a multiplicity of data packets between hosts in the network; each switch means including a multiplicity of port means for coupling the switch means to other switch means and hosts, and a nonblocking crossbar switch for simultaneously coupling and routing data packets between a multiplicity of selected pairs of said port means; said hosts and switch means together comprising network members; and a multiplicity of point to point link means for interconnecting said switch means and the hosts in said network, each point to point link means providing a communication channel between two of said network members; each said data packet having a specified host to which said data packet is being sent; each said switch means including routing means for defining, in accordance with predefined criteria, legal data packet transmission routes through said network; said routing means defining a subset of said port means of said switch means through which a received data packet can be retransmitted, said subset of port means being a function of the port means of said switch which receives said data packet and the host to which said data packet is being sent.

Claim 15

The mesh connected local area network of claim 12, said multiplicity of link means including spanning tree links and a multiplicity of additional links; said interconnected multiplicity of switch means and said spanning tree links together comprising a spanning tree in which one of said switch means is designated the root of said spanning tree; each said data packet having a specified host to which said data packet is being sent; said routing means including configuring means for denoting as an up port each port means of said switch means which couples said switch means to another switch means that is closer to said root of said spanning tree, in accordance with predefined criteria, and for denoting as down ports all the other port means of said switch means; said routing means further including routing table means for defining a subset of said port means of said switch means through which a received data packet can be retransmitted, said subset of port means being a function of the port means of said switch means which receives said data packet and the host to which said data packet is being sent, wherein said subset of port means includes only selected ones of said port means denoted by said configuring means as down ports when said port means which receives said data packet is denoted as a down port; whereby said routing means provides deadlock free routing of data packets through said mesh connected local area network.

Claim 16

The mesh connected local area network of claim 13, said multiplicity of link means including spanning tree links and a multiplicity of additional links; said interconnected multiplicity of switch means and said spanning tree links together comprising a spanning tree in which one of said switch means is designated the root of said spanning tree; said network further including switch ordering means for defining, for any two specified ones of said switches means, which of said specified switches has a better position in said spanning tree and which has a worse position; each said link means which interconnects two of said switch means including an up channel and a down channel which transmit data packets in opposite directions between said switch means; said up channel transmitting data packets from a switch means in a worse position to a switch means in a better position; each said switch means including routing means for forwarding a packet toward a specified one of said network members so that the path by which said packet is transmitted through said network comprises zero or more up channels followed by zero or more down channels; whereby said routing means provides deadlock free routing of data packets through said mesh connected local area network.

Claim 17

The mesh connected local area network of claim 13, said switch means including port status means for denoting which of said port means is available for retransmitting a data packet; said routing means including route selection means for comparing said subset of said port means of said switch means through which a received data packet can be retransmitted with said port status means and for routing said received data packet through a port means which is included in said subset of said port means and which is available for retransmitting a data packet.

Claim 18

The mesh connected local area network of claim 15, said route selection means including means for periodically comparing said subset of said port means of said switch means through which a received data packet can be retransmitted with said port status means until one of the port means denoted as available matches one of said subset of said port means, and then routing said received data packet through the matching port means; whereby said switch means provides low latency retransmission of data packets.

Claim 19

The mesh connected local area network of Claim 12, said multiplicity of link means including spanning tree links and a multiplicity of additional links; said interconnected multiplicity of switch means and said spanning tree links together comprising a spanning tree in which one of said switch means is designated the root of said spanning tree; said data packets including data packets which are sent to a single specified one of said hosts in said network and broadcast data packets which are to be sent to all said hosts in said network; said routing means including configuring means for denoting two broadcast packet transmission routes, including means for designating as an uplink port one port means of said switch means which couples said switch means to another switch means that is closer to said root of said spanning tree, in accordance with predefined criteria, and for denoting as downlink ports each port means which is coupled to the uplink port of other ones of said switch means; said routing means of each said switch means, except said switch means designated as said root of said network, further including route selection means for routing broadcast data packets received by said uplink port to all of said downlink ports, and for routing to said uplink port broadcast data packets received by any of said port means other than said uplink port.

Claim 20

The mesh connected local area network of Claim 17, said routing means of said switch means designated as said root of said network further including route selection means for routing all broadcast data packets received by said switch means to all of said downlink ports.

Claim 21

The mesh connected local area network of claim 18, wherein each said switch means includes means for simultaneously retransmitting received broadcast data packets through all of said downlink ports.

Claim 22

A mesh connected local area network for interconnecting a multiplicity of hosts, said network comprising: a multiplicity of switch means for simultaneously routing a multiplicity of data packets between hosts in the network; each switch means including a multiplicity of port means for coupling the switch means to other switch means and hosts, and a nonblocking crossbar switch for simultaneously coupling and routing data packets between a multiplicity of selected pairs of said port means; and a multiplicity of point to point link means for interconnecting said switch means and the hosts in said network, each point to point link means providing a communication channel between two network members selected from the set consisting of the switch means in said network and the hosts in said network; said multiplicity of link means including spanning tree links and a multiplicity of additional links; said interconnected multiplicity of switch means and said spanning tree links together comprising a spanning tree in which one of said switch means is designated the root of said spanning tree; each said data packet having a specified host to which said data packet is being sent; each said switch means including routing means for defining legal data packet transmission routes through said network; said routing means including configuring means for denoting as an up port each port means of said switch means which couples said switch means to another switch means that is closer to said root of said spanning tree, in accordance with predefined criteria, and for denoting as down ports all the other port means of said switch means; said routing means further including routing table means for defining a subset of said port means of said switch means through which a received data packet can be retransmitted, said subset of port means being a function of the port means of said switch means which receives said data packet and the host to which said data packet is being sent, wherein said subset of port means includes only selected ones of said port means denoted by said configuring means as down ports when said port means which receives said data packet is denoted as a down port; whereby said routing means provides deadlock free routing of data packets through said mesh connected local area network.

Claim 23

A mesh connected local area network for interconnecting a multiplicity of hosts, said network comprising: a multiplicity of switch means for simultaneously routing a multiplicity of data packets between hosts in the network; each switch means including a multiplicity of port means for coupling the switch means to other switch means and hosts, and a nonblocking crossbar switch for simultaneously coupling and routing data packets between a multiplicity of selected pairs of said port means; and a multiplicity of point to point link means for interconnecting said switch means and the hosts in said network, each point to point link means providing a communication channel between two network members selected from the set consisting of the switch means in said network and the hosts in said network; said multiplicity of link means including spanning tree links and a multiplicity of additional links; said interconnected multiplicity of switch means and said spanning tree links together comprising a spanning tree in which one of said switch means is designated the root of said spanning tree; each said data packet having a specified host to which said data packet is being sent; each said switch means including routing means for defining legal data packet transmission routes through said network; said routing means including configuring means for denoting as an up port each port means of said switch means which couples said switch means to another switch means that is closer to said root of said spanning tree, in accordance with predefined criteria, and for denoting as down ports all the other port means of said switch means; said routing means further including routing table means for defining a subset of said port means of said switch means through which a received data packet can be retransmitted, said subset of port means being a function of the port means of said switch means which receives said data packet and the host to which said data packet is being sent, wherein said subset of port means includes only selected ones of said port means denoted by said configuring means as down ports when said port means which receives said data packet is denoted as a down port; whereby said routing means provides deadlock free routing of data packets through said mesh connected local area network.

Claim 24

The mesh connected local area network of claim 20, each said data packet having address means for denoting a network address; said routing table means including means for denoting for each of multiplicity of predefined network addresses a subset of said port means of said switch means through which a received data packet can be retransmitted; said routing means further including means for discarding data packets having an address means which denotes a network address other than one of said predefined network addresses; whereby data packets with illegal or corrupted network address values are discarded.

Claim 25

A mesh connected local area network for interconnecting a multiplicity of hosts, said network comprising: a multiplicity of switch means for simultaneously routing a multiplicity of data packets between hosts in the network; each switch means including a multiplicity of port means for coupling the switch means to other switch means and hosts, and a nonblocking crossbar switch for simultaneously coupling and routing data packets between a multiplicity of selected pairs of said port means; and a multiplicity of point to point link means for interconnecting said switch means and the hosts in said network, each point to point link means providing a bidirectional communication channel between two network members selected from the set consisting of the switch means in said network and the hosts in said network; said multiplicity of link means including spanning tree links and a multiplicity of additional links; said interconnected multiplicity of switch means and said spanning tree links together comprising a spanning tree in which one of said switch means is designated the root of said spanning tree; means for assigning each said link means an up direction and a down direction; and routing means for transmitting a data packet from a first specified network member to a second specified network member, including means for transmitting said data packet on at least one of said link means in said up direction and then transmitting said data packet on at least one of said link means in said down direction to said second specified network member; whereby said routing means provides deadlock free routing of data packets through said mesh connected local area network.

Claim 26

A mesh connected local area network for interconnecting a multiplicity of hosts, said network comprising: a multiplicity of switch means for simultaneously routing a multiplicity of data packets between hosts in the network; each switch means including a multiplicity of port means for coupling the switch means to other switch means and hosts, and a nonblocking crossbar switch for simultaneously coupling and routing data packets between a multiplicity of selected pairs of said port means; and a multiplicity of point to point link means for interconnecting said switch means and the hosts in said network, each point to point link means providing a bidirectional communication channel between two network members selected from the set consisting of the switch means in said network and the hosts in said network; said multiplicity of link means including spanning tree links and a multiplicity of additional links; said interconnected multiplicity of switch means and said spanning tree links together comprising a spanning tree in which one of said switch means is designated the root of said spanning tree; means for assigning each said link means an up direction and a down direction; and routing means for transmitting a data packet from a first specified network member to a second specified network member, including means for transmitting said data packet on at least one of said link means in said up direction and then transmitting said data packet on at least one of said link means in said down direction to said second specified network member; whereby said routing means provides deadlock free routing of data packets through said mesh connected local area network.

Claim 27

The mesh connected local area network of claim 22, said data packets including data packets which are sent to a single specified one of said hosts in said network and broadcast data packets which are to be sent to all said hosts in said network; said broadcast data packets having a predefined maximum size; each said port means including buffer means for buffering data packets received by said switch means at said port means; said buffer means having more than sufficient room to store an entire broadcast data packet of said predefined maximum size and means for indicating when said buffer means has sufficient room to receive an entire broadcast data packet; said port means including flow control means coupled to said buffer means for sending flow control signals to a network member coupled to said port means, said flow control signals including stop flow signals requiring said network member to stop transmitting data packets to said port means and start flow signals allowing said network member to resume sending data packets to said port means; said flow control means including means for sending start flow signals only when said buffer means has sufficient room to receive an entire broadcast data packet.

Claim 28

The mesh connected local area network of claim 23, said port means including means for receiving said flow control signals sent by a network member coupled to said port means, and means for stopping the transmission of a data packet when a stop flow signal is received from said network member, unless said data packet is a broadcast packet.

Claim 29

A mesh connected local area network for interconnecting a multiplicity of hosts, said network comprising: a multiplicity of switch means for simultaneously routing a multiplicity of data packets between hosts in the network; each switch means including a multiplicity of port means for coupling the switch means to other switch means and hosts, and a nonblocking crossbar switch for simultaneously coupling and routing data packets between a multiplicity of selected pairs of said port means; said hosts and switch means together comprising network members; and a multiplicity of point to point link means for interconnecting said switch means and the hosts in said network, each point to point link means providing a communication channel between two of said network members; said multiplicity of link means including spanning tree links and a multiplicity of additional links; said interconnected multiplicity of switch means and said spanning tree links together comprising a spanning tree in which one of said switch means is designated the root of said spanning tree; said data packets including data packets which are sent to a single specified one of said hosts in said network and broadcast data packets which are to be sent to all said hosts in said network; each said switch means including routing means for defining, in accordance with predefined criteria, legal data packet transmission routes through said network; said routing means including means for designating as an uplink port one port means of said switch means which couples said switch means to another switch means that is closer to said root of said spanning tree, in accordance with predefined criteria, and for denoting as downlink ports each port means which is coupled to the uplink port of other ones of said switch means; said routing means of each said switch means, except said switch means designated as said root of said network, further including route selection means for routing broadcast data packets received by said uplink port to all of said downlink ports, and for routing to said uplink port broadcast data packets received by any of said port means other than said uplink port.

Claim 30

A mesh connected local area network for interconnecting a multiplicity of hosts, said network comprising: a multiplicity of switch means for simultaneously routing a multiplicity of data packets between hosts in the network; each switch means including a multiplicity of port means for coupling the switch means to other switch means and hosts, and a nonblocking crossbar switch for simultaneously coupling and routing data packets between a multiplicity of selected pairs of said port means; said hosts and switch means together comprising network members; and a multiplicity of point to point link means for interconnecting said switch means and the hosts in said network, each point to point link means providing a communication channel between two of said network members; said multiplicity of link means including spanning tree links and a multiplicity of additional links; said interconnected multiplicity of switch means and said spanning tree links together comprising a spanning tree in which one of said switch means is designated the root of said spanning tree; said data packets including data packets which are sent to a single specified one of said hosts in said network and broadcast data packets which are to be sent to all said hosts in said network; each said switch means including routing means for defining, in accordance with predefined criteria, legal data packet transmission routes through said network; said routing means including means for designating as an uplink port one port means of said switch means which couples said switch means to another switch means that is closer to said root of said spanning tree, in accordance with predefined criteria, and for denoting as downlink ports each port means which is coupled to the uplink port of other ones of said switch means; said routing means of each said switch means, except said switch means designated as said root of said network, further including route selection means for routing broadcast data packets received by said uplink port to all of said downlink ports, and for routing to said uplink port broadcast data packets received by any of said port means other than said uplink port.

Claim 31

The mesh connected local area network of Claim 25,

Claim 32

said routing means of said switch means designated as said root of said network further including route selection means for routing all broadcast data packets received by said switch means to all of said downlink ports.

Claim 33

said routing means of said switch means designated as said root of said network further including route selection means for routing all broadcast data packets received by said switch means to all of said downlink ports.

Claim 34

The mesh connected local area network of claim 26, wherein each said switch means includes means for simultaneously retransmitting received broadcast data packets through all of said downlink ports.

Claim 35

A mesh connected local area network for interconnecting a multiplicity of hosts, said network comprising: a multiplicity of switch means for simultaneously routing a multiplicity of data packets between hosts in the network; said hosts and switch means together comprising network members; a multiplicity of point to point link means for interconnecting said switch means and the hosts in said network, each point to point link means providing a communication channel between two of said network members; switch means coupled to one another by said link means comprising neighboring switch means; said multiplicity of link means including spanning tree links and a multiplicity of additional links; said interconnected multiplicity of switch means and said spanning tree links together comprising a spanning tree in which one of said switch means is designated the root of said spanning tree; each switch means including reconfiguration means for determining the position of said switch means in said spanning tree, said reconfiguration means including: position denoting means for denoting a tree position within said spanning tree; epoch denoting means for denoting an epoch value associated with said tree position; configuration change detection means for detecting a change in the configuration of said network, including means for detecting the existence of a new connection between said switch means and another one of said network members and for detecting the breaking of a connection between said switch means and another one of said network members; said configuration change detection means including means for incrementing said epoch value when a change in the configuration of said network is detected; message sending means coupled to said position denoting means for sending a configuration message to each switch means neighboring said switch means; said configuration message including said tree position and said epoch value; message receiving means for receiving configuration messages from neighboring switch means, for generating a derived tree position which is a function of the tree position in each received configuration message, and for replacing the tree position denoted by said position denoting means with said derived tree position when said derived tree position is better than the tree position denoted by said position denoting means; said message receiving means including means for replacing said tree position with said derived tree position and replacing said epoch value with the epoch value in said received configuration message when said epoch value in said received ' configuration messages is larger than the epoch value denoted by said epoch denoting means; said message sending means including means for sending a configuration message to said neighboring switch means when said tree position denoted by said position denoting means is replaced by said derived tree position; whereby changes in the configuration of the network automatically cause the switch means in said network to redetermine their relative tree positions in said spanning tree.

Claim 36

A mesh connected local area network for interconnecting a multiplicity of hosts, said network comprising: a multiplicity of switch means for simultaneously routing a multiplicity of data packets between hosts in the network; said hosts and switch means together comprising network members; a multiplicity of point to point link means for interconnecting said switch means and the hosts in said network, each point to point link means providing a communication channel between two of said network members; switch means coupled to one another by said link means comprising neighboring switch means; said multiplicity of link means including spanning tree links and a multiplicity of additional links; said interconnected multiplicity of switch means and said spanning tree links together comprising a spanning tree in which one of said switch means is designated the root of said spanning tree; each switch means including reconfiguration means for determining the position of said switch means in said spanning tree, said reconfiguration means including: position denoting means for denoting a tree position within said spanning tree; epoch denoting means for denoting an epoch value associated with said tree position; configuration change detection means for detecting a change in the configuration of said network, including means for detecting the existence of a new connection between said switch means and another one of said network members and for detecting the breaking of a connection between said switch means and another one of said network members; said configuration change detection means including means for incrementing said epoch value when a change in the configuration of said network is detected; message sending means coupled to said position denoting means for sending a configuration message to each switch means neighboring said switch means; said configuration message including said tree position and said epoch value; message receiving means for receiving configuration messages from neighboring switch means, for generating a derived tree position which is a function of the tree position in each received configuration message, and for replacing the tree position denoted by said position denoting means with said derived tree position when said derived tree position is better than the tree position denoted by said position denoting means; said message receiving means including means for replacing said tree position with said derived tree position and replacing said epoch value with the epoch value in said received configuration message when said epoch value in said received ' configuration messages is larger than the epoch value denoted by said epoch denoting means; said message sending means including means for sending a configuration message to said neighboring switch means when said tree position denoted by said position denoting means is replaced by said derived tree position; whereby changes in the configuration of the network automatically cause the switch means in said network to redetermine their relative tree positions in said spanning tree.

Claim 37

A mesh connected local area network for interconnecting a multiplicity of hosts, said network comprising: a multiplicity of switch means for simultaneously routing a multiplicity of data packets between hosts in the network; said hosts and switch means together comprising network members; a multiplicity of point to point link means for interconnecting said switch means and the hosts in said network, ach point to point link means providing a communication channel between two of said network members; said multiplicity of link means including spanning tree links and a multiplicity of additional links; said interconnected multiplicity of switch means and said spanning tree links together comprising a spanning tree in which one of said switch means is designated the root of said spanning tree; each switch means including reconfiguration means for determining the position of said switch means in said spanning tree, said reconfiguration means including: position denoting means for denoting a tree position within said spanning tree; epoch denoting means for denoting an epoch value associated with said tree position; configuration change detection means for detecting a change in the configuration of said network, including means for detecting the existence of a new connection between said switch means and another one of said network members and for detecting the breaking of a connection between said switch means and another one of said network members; said configuration change detection means including means for incrementing said epoch value when a change in the configuration of said network is detected; message sending means coupled to said position denoting means for sending a configuration message to each switch means neighboring said switch means; said configuration message including said tree position and said epoch value; message receiving means for receiving configuration messages from neighboring switch means, for generating a derived tree position which is a function of the tree position in each received configuration message, and for replacing the tree position denoted by said position denoting means with said derived tree position when said derived tree position is better than the tree position denoted by said position denoting means; said message receiving means including means for replacing said tree position with said derived tree position and replacing said epoch value with the epoch value in said received configuration message when said epoch value in said received configuration messages is larger than the epoch value denoted by said epoch denoting means; said message sending means including means for sending a configuration message to said neighboring switch means when said tree position denoted by said position denoting means is replaced by said derived tree position; said configuration change detection means including suicide pact means for detecting epoch value overflow when said epoch value is incremented to a predefined overflow value, and for sending a predefined suicide pact message to said neighbor switch means and for resetting said epoch value to a predefined initial value when epoch value overflow is detected; said message receiving means including means for responding to the receipt of a suicide pact message by resetting said epoch value to said predefined initial value, sending said predefined suicide pact message to said neighbor switch means, ignoring all subsequent suicide pact messages received from said neighboring switch means for a predefined period of time, and then sending configuration messages to said neighboring switch means; whereby changes in the configuration of the network automatically cause the switch means in said network to redetermine their relative tree positions in said spanning tree.

Claim 38

A mesh connected local area network for interconnecting a multiplicity of hosts, said network comprising: a multiplicity of switch means for simultaneously routing a multiplicity of data packets between hosts in the network; said hosts and switch means together comprising network members; a multiplicity of point to point link means for interconnecting said switch means and the hosts in said network, ach point to point link means providing a communication channel between two of said network members; said multiplicity of link means including spanning tree links and a multiplicity of additional links; said interconnected multiplicity of switch means and said spanning tree links together comprising a spanning tree in which one of said switch means is designated the root of said spanning tree; each switch means including reconfiguration means for determining the position of said switch means in said spanning tree, said reconfiguration means including: position denoting means for denoting a tree position within said spanning tree; epoch denoting means for denoting an epoch value associated with said tree position; configuration change detection means for detecting a change in the configuration of said network, including means for detecting the existence of a new connection between said switch means and another one of said network members and for detecting the breaking of a connection between said switch means and another one of said network members; said configuration change detection means including means for incrementing said epoch value when a change in the configuration of said network is detected; message sending means coupled to said position denoting means for sending a configuration message to each switch means neighboring said switch means; said configuration message including said tree position and said epoch value; message receiving means for receiving configuration messages from neighboring switch means, for generating a derived tree position which is a function of the tree position in each received configuration message, and for replacing the tree position denoted by said position denoting means with said derived tree position when said derived tree position is better than the tree position denoted by said position denoting means; said message receiving means including means for replacing said tree position with said derived tree position and replacing said epoch value with the epoch value in said received configuration message when said epoch value in said received configuration messages is larger than the epoch value denoted by said epoch denoting means; said message sending means including means for sending a configuration message to said neighboring switch means when said tree position denoted by said position denoting means is replaced by said derived tree position; said configuration change detection means including suicide pact means for detecting epoch value overflow when said epoch value is incremented to a predefined overflow value, and for sending a predefined suicide pact message to said neighbor switch means and for resetting said epoch value to a predefined initial value when epoch value overflow is detected; said message receiving means including means for responding to the receipt of a suicide pact message by resetting said epoch value to said predefined initial value, sending said predefined suicide pact message to said neighbor switch means, ignoring all subsequent suicide pact messages received from said neighboring switch means for a predefined period of time, and then sending configuration messages to said neighboring switch means; whereby changes in the configuration of the network automatically cause the switch means in said network to redetermine their relative tree positions in said spanning tree.