US 5,088,091 A · High-speed mesh connected local area network · patentgrep

Loading patent…

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.

Claims32

Dependent claims

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 packets have been received.

3 more elements

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, wherein said subset of port means is selected by said routing means in accordance with the port means of said switch which receives said data packet and the host to which said data packet is being sent.

5 more elements

The 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 of said 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 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 of 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, wherein said subset of port means is selected by said routing means in accordance with 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.

8 more elements

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 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.

7 more elements

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 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 non-broadcast 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.

8 more elements

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 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 message 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.

14 more elements

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;
said multiplicity of link means including spanning tree links and a multiplicity of additional links;
said 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 message 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 epoch value overflow detecting means for detecting epoch value overflow when said epoch value is incremented to a predefined overflow value, and for sending a predefined epoch value reset message to said neighboring 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 an epoch value reset message by resetting said epoch value to said predefined initial value, sending said predefined epoch value reset message to said neighbor switch means, ignoring all subsequent epoch value reset 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.

15 more elements

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;
said multiplicity of link means including spanning tree links and a multiplicity of additional links;
said 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;
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;
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;
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.

10 more elements

Dependencies are inferred from the claim text.