Reconfiguration system and method for high-speed mesh connected local area network
First Claim
1. 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;
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 stability 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 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;
stability evaluating means, coupled to said message receiving means and said stability denoting 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;
whereby the switch means in said network determine their relative tree positions in said spanning tree and when the process of determining those tree positions has been completed.
5 Assignments
0 Petitions
Accused Products
Abstract
A mesh connected local area network provides automatic packet switching and routing between host computers coupled to the network. The network has a multiplicity of cut-through, nonblocking switches, each capable of simultaneously routing a multiplicity of data packets. Low host-to-host latency is achieved through the use of cut-through switches with separate internal buffers for each packet being routed. The switches are interconnected with one another and are coupled to the host computers of the network by point to point full duplex links. While each switch can be coupled to ten or more network members, i.e., switches and hosts, each link is coupled to only two network members and is dedicated to carrying signals therebetween. Whenever a new switch or link is added to the network, and whenever a switch or link fails, the switches in the network automatically reconfigure the network by recomputing the set of legal paths through the network.
435 Citations
4 Claims
-
1. 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; 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 stability 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 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; stability evaluating means, coupled to said message receiving means and said stability denoting 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; whereby the switch means in said network determine their relative tree positions in said spanning tree and when the process of determining those tree positions has been completed. - View Dependent Claims (2, 3)
-
-
4. 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.
-
Specification