Reconfiguration system and method for high-speed mesh connected local area network

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 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;
• said multiplicity of point to point link means including spanning tree links and a multiplicity of additional links;
• said multiplicity of switch means and said spanning tree links jointly forming 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;
• stability denoting means for denoting a stability value which indicates whether said tree position is stable;
• 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;
• reconfiguration initiation means, coupled to said configuration change detection means, for sending a reconfiguration initiation message to switch means neighboring said switch means when a change in the configuration of said network is detected by said configuration change detection means;
• reconfiguration computation means, coupled to said position denoting means, for redetermining the tree position of said switch means in said spanning tree, said reconfiguration computation means including means for (A) sending and receiving configuration messages to and from switch means neighboring said switch means and (B) storing in said position denoting means a derived tree position derived from said received configuration messages;
• each said configuration message including said tree position and said stability value;
• said reconfiguration computation means including stability evaluating means for setting said stability value to denote that said tree position is stable when said switch means has sent at least one configuration message to and has received at least one configuration from each neighboring switch means, and (1) the last configuration message received from each of said neighboring switch means includes a better tree position than said tree position denoted by said position denoting means, or (2) the last configuration message received from at least one of said neighboring switch means includes a worse tree position than said tree position denoted by said position denoting means and the switch's stability value in the last configuration message received from each such neighboring switch means with a worse tree position denotes a stable tree position for said neighboring switch means;
• said reconfiguration means including completion detecting means for determining when said tree position denotes that said switch means is the root of said spanning tree and said stability denoting means denotes that said tree position is stable, and for sending a reconfiguration completion message to said neighboring switch means indicating that all said switch means are stable;
• said multiplicity of switch means including means for transmitting to all of said switch means network configuration data indicating the tree positions of all said switch means in said spanning tree;
• and
• each switch means including route selection means for routing received data packets to specified network members in accordance with said network configuration data and predefined route selection criteria;
• whereby changes in the configuration of the network automatically cause the switch means in said network to redetermine their tree positions in said spanning tree.