Variable cyclic redundancy coding method and apparatus for use in a multistage network

• US 5,734,826 A
• Filed: 09/17/1992
• Issued: 03/31/1998
• Est. Priority Date: 03/29/1991
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Bruck, Jehoshua, Olnowich, Howard Thomas, Blaum, Miguel Mario
• Primary Examiner(s): Harrity, John E.
• Application Number:
  US07/946,513
• Time in Patent Office: 2,021 Days
• Field of Search: 395/800, 395/200.15, 395/185.05, 370/410, 371/37.1, 371/37.2, 371/37.3, 371/37.4, 371/37.5, 371/37.6, 371/37.7, 364/238.1, 364/242.94, 364/DIG. 1
• US Class Current: 709/238
• CPC Class Codes: G06F 11/261 by simulating additional hardware, e.g. fault simulation
• CPC Class Codes: G06F 13/4022 using switching circuits, e.g. switching matrix, connection or expansion network G06F13/4009 takes precedence
• CPC Class Codes: G06F 15/17337 Direct connection machines, e.g. completely connected computers, point to point communication networks coupling between buses G06F13/4004
• CPC Class Codes: G06F 15/17375 One dimensional, e.g. linear array, ring
• CPC Class Codes: G06F 15/17393 having multistage networks, e.g. broadcasting scattering, gathering, hot spot contention, combining/decombining
• CPC Class Codes: H04J 2203/0005 Switching elements
• CPC Class Codes: H04L 1/0057 Block codes H04L1/0061, H04L1/0064 take precedence
• CPC Class Codes: H04L 12/18 for broadcast or conference , e.g. multicast
• CPC Class Codes: H04L 12/1881 with schedule organisation, e.g. priority, sequence management
• CPC Class Codes: H04L 49/256 Routing or path finding in ATM switching fabrics
• CPC Class Codes: H04L 49/3081 ATM peripheral units, e.g. policing, insertion or extraction
• CPC Class Codes: H04L 49/40 Constructional details, e.g. power supply, mechanical construction or backplane
• CPC Class Codes: H04L 69/08 Protocols for interworking; Protocol conversion
• CPC Class Codes: H04L 69/18 Multiprotocol handlers, e.g. single devices capable of handling multiple protocols
• CPC Class Codes: H04L 7/0338 the correction of the phase error being performed by a feed forward loop
• CPC Class Codes: H04Q 11/0001 using optical switching
• CPC Class Codes: H04Q 11/0066 Provisions for optical burst or packet networks
• CPC Class Codes: H04Q 11/0478 Provisions for broadband connections

Abstract

An error checking method and apparatus for appending a variable number of redundancy coding information at the end of each data message or packet transmitted over a multi-stage network for the purpose of protecting the data by using an error detecting code. The amount of additional redundancy coding information implemented is variable and increases with the size of the data message or packet to provide a consistent level of protection.

Claims

1. A variable cyclic redundancy code apparatus for use by a multi-stage bufferless switching network, the network comprising:

a plurality of bufferless switching apparatuses cascaded into stages, each said switching apparatus including a plurality of switch inputs and a plurality of switch outputs, each of the switch outputs of each said switching apparatus coupled to a different switch input of others of said switching apparatuses, switch outputs of last stage switching apparatuses comprising network output ports and switch inputs of first stage switching apparatuses comprising network input ports; and

a plurality of nodes each coupled to one of the network output ports and to one of the network input ports, each said node comprising means for receiving a data message and means for sending a data message including a connection request;

said switching apparatuses each including;

connection means for establishing a communication path between any one of the network input ports and any one of the network output ports in response to said connection request received at said any one of the network input ports, said communication path for transmitting a data message received at said any one of the network input ports to said any one of the network output ports, said connection means including asynchronous connection means for establishing asynchronously a plurality of simultaneously active communication paths between a plurality of network input ports and a plurality of network output ports in response to a plurality of connection requests received separately or simultaneously at said plurality of network input ports, said simultaneously active communication paths for transmitting a plurality of data messages received separately or simultaneously at said plurality of network input ports to said plurality of network output ports;

said variable cyclic redundancy code apparatus comprising;

first buffer means for storing the data message at a sending node;

first generating means for generating a first cyclic redundancy code at the sending node, the cyclic redundancy code comprising a plurality of error checking bits;

appending means coupled to said means for sending a data message for appending to said data message the cyclic redundancy code;

second buffer means for storing the data message at a receiving node;

second generating means for generating a second cyclic redundancy code at the receiving node, the second cyclic redundancy code comprising a plurality of error checking bits; and

comparing means for comparing the first cyclic redundancy code to the second cyclic redundancy code and for indicating a comparison failure.

2. The variable cyclic redundancy code apparatus according to claim 1 wherein the number of said error checking bits is based on the length of said data message.

3. The variable cyclic redundancy code apparatus according to claim 1 wherein the network input and output ports comprise a plurality of control lines, a first of said control lines for sending back to the sending node an acceptance signal for indicating to the sending node an error-free transmission of the data message, a second of said control lines for sending back to the sending node a rejection signal for indicating to the sending node an erroneous transmission of the data message.

4. The variable cyclic redundancy code apparatus according to claim 1 wherein the cyclic redundancy code is Reed-Solomon code.

5. A variable cyclic redundancy coding method for use in a multi-stage bufferless switching network, the network comprising:

a plurality of bufferless switching apparatuses cascaded into stages, each said switching apparatus including a plurality of switch inputs and a plurality of switch outputs, each of the switch outputs of each said switching apparatus coupled to a different switch input of others of said switching apparatuses, switch outputs of last stage switching apparatuses comprising network output ports and switch inputs of first stage switching apparatuses comprising network input ports; and

a plurality of nodes each coupled to one of the network output ports and to one of the network input ports, each said node comprising means for receiving a data message and means for sending a data message including a connection request;

said switching apparatuses each including;

connection means for establishing a communication path between any one of the network input ports and any one of the network output ports in response to said connection request received at said any one of the network input ports, said communication path for transmitting a data message received at said any one of the network input ports to said any one of the network output ports, said connection means including asynchronous connection means for establishing asynchronously a plurality of simultaneously active communication paths between a plurality of network input ports and a plurality of network output ports in response to a plurality of connection requests received separately or simultaneously at said plurality of network input ports, said simultaneously active communication paths for transmitting a plurality of data messages received separately or simultaneously at said plurality of network input ports to said plurality of network output ports;

said variable cyclic redundancy coding method comprising the steps of;

a) storing the data message in a buffer;

b) generating a cyclic redundancy code at a sending node based on the length of the data message;

c) appending the cyclic redundancy code to the data message;

d) transmitting the data message over the multistage network;

e) regenerating the cyclic redundancy code at a receiving node;

f) comparing the cyclic redundancy code appended to the data message with the cyclic redundancy code regenerated at the receiving node;

g) determining whether the data message is erroneous based on the comparing step.

6. The method according to claim 5, wherein the data message includes a message header and the step of regenerating the cyclic redundancy code is based on information contained in the message header.

7. The method according to claim 5, further comprising the step of:

h) sending back to the sending node a signal indicating whether the data message transmission is successful or erroneous.