Packet switching

• US 5,235,595 A
• Filed: 01/06/1989
• Issued: 08/10/1993
• Est. Priority Date: 05/06/1987
• Status: Expired due to Term

• Current Assignee: Micron Technology, Inc.
• Original Assignee: Fischer & Porter Comapny
• Inventors: O'Dowd, Michael B.
• Primary Examiner(s): Safourek, Benedict V.
• Assistant Examiner(s): Hsu, Alpus H.
• Application Number:
  US07/296,524
• Time in Patent Office: 1,677 Days
• Field of Search: 370/60, 370/94.1, 370/85.12, 370/58.1, 370/92, 370/94.3, 370/85.13, 370/85.14, 370/85.15, 370/16, 340/825.5, 340/825.51, 340/825.52
• US Class Current: 370/392
• CPC Class Codes: H04L 12/433 with asynchronous transmission, e.g. token ring, register insertion
• CPC Class Codes: H04L 12/64 Hybrid switching systems
• CPC Class Codes: H04L 2012/5652 Cell construction, e.g. including header, packetisation, depacketisation, assembly, reassembly
• CPC Class Codes: H04L 9/40 Network security protocols

Abstract

This invention is concerned with packet switching techniques, protocols, networks, and equipment for use on a local area or wide area scale. Packets which include a fixed-length data field and memory offset field are employed so that packeting, block data transfer to contiguous memory and depacketing can be effected at the destination by hardware-mediated processes with minimal processor involvement. Multiple sessions can be readily handled by assigning addresses to multiple memory buffers at the destination. Thus, each packet carrying computer data provides three levels of addressing for its data segment corresponding to the destination node or device, the memory buffer for the data block being transfered and the memory location within that buffer into which the segment of data carried by the packet is to be placed. The equipment includes loop-based, collision-free packet switches in which packets are modified and re-circulated when a destination is busy. This allows a high-speed loop to transfer packets to and from devices running at various (lower) speeds. Loop latency is minimized and data transfer rates maximized by the use of fully-buffering parallel forms of the switch. A method for handling broadcasts is also disclosed, together with a technique for preempting low priority packets and exploiting short-cuts on a loop. These improvements allow application of the technique to a high-speed voice/data packet-switching in large wide area networks as well as in small local area networks. By using the methods and equipment disclosed, an extensive, powerful and extremely fast integrated communications subnet can be largely built in hardware with little need for processor intervention.

Claims

1. A packet switched data communications network, which transfers a block of data from a source memory buffer associated with a first node o the network to a destination memory buffer associated with a second node on the network comprising:

a data communications loop including a plurality of switch elements, coupled, respectively, to said first and second nodes to provide a data communications link between said first and second nodes, said data communications loop conveying self-addressed packets from said first node operating as a source to said second nodes operating as a destination wherein;

each of said first and second nodes includes an addressable memory buffer which holds at least a first one of said self-addressed packets when the node is operating as one of said destination nodes;

each of said switch elements comprises a transfer buffer for holding a second one of said self-addressed packets, received from said data communications loop, while the node coupled to said switch element is transmitting a third one of said self addressed packets via said switch element to said data communications loop, and

each of said self addressed packets includes;

a data field for a segment of user data to be conveyed on the data communications loop by the packet;

a first address field for identifying the addressable memory buffer at the destination node; and

a second address field for indicating a starting address in said memory buffer at which to store said data segment; and

said packet switched data communications system further comprises;

means for transferring successive segments of data from the block into the respective data fields of successive ones of said packets,

means for writing an offset of each data segment from a base address in the source buffer into the second address field of the packet containing that segment,

means for identifying the destination memory buffer in the first address field of each packet,

means for transmitting said packets through the system, and

means for writing the data segment of each packet as it arrives at the second node into an address in said identified destination memory buffer, said address being signified by the combination of an offset in the second address field of the respective packet and a base address corresponding to the destination memory buffer.

2. A method according to claim 1 including the steps of:

generating a transmit block checksum for the successive data segments while writing the successive data segments into the successive packets at the source node;

generating a receive block checksum for the successive data segments while writing successive data segments to the destination memory buffer;

sending at least one packet from the source node to the destination node to signify the end of the block transfer and to communicate the transmit block checksum;

comparing the transmit and receive block checksums at the destination node; and

sending a positive or negative acknowledgement in a packet from the destination node to the source node depending on the results of said comparison.

3. A packet-switched system, having a plurality of switch elements interposed in a loop and each having a loop address, for transferring packets around the loop, the switch elements being connected to respective nodes which act to packet and depacket data for transfer between terminal devices connected to the nodes and the switch elements, wherein:

each node has at least one addressable memory buffer;

each packet includes;

a header of predetermined length;

a data field for a segment of user data to be conveyed on the system by the packet;

a first address field for identifying the addressable memory buffer at the node;

a second address field for indicating a destination address in said memory buffer for said data segment; and

a third address field for indicating the loop-address, the switch elements acting to insert and remove the packets onto and off the loop without collision between the packets, whereby

if one of the switch elements is unable to take one of the packets addressed to the one switch element off the loop, the one switch element marks the packet which it is unable to take for returning around the loop; and

each switch element comprises;

a loop input and a loop output and a variable length hold FIFO buffer capable of holding an entire packet connected between said loop input and loop output;

a receive register, of at least the same length as the header of the packet, connected to the loop input and adapted to output packets to the associated node;

an output register switchably connected to the loop output for conveying packets input to the switch element from the associated node; and

control logic means for;

reading the header of each incoming packet in the receive register;

effecting the transfer of originating packets from the output register onto the loop;

effecting the transfer of incoming packets addressed to said element to the associated node;

eliminating packets addressed to upstream elements;

passing on packets addressed to downstream elements or buffering the latter packets in the hold FIFO until the transmission of an originating packet has been completed; and

buffering packets addressed to said switch element but which cannot be passed onto the associated node in the hold FIFO while effecting modification of the header of said packets to ensure their return on the loop, and then transferring said packets to the loop output.

4. A packet-switched system as set forth in claim 3 in which each switch element includes a direct connection in parallel with said hold FIFO so that an incoming packet will proceed substantially directly onto the loop output if an originating packet is not being put on the loop, and wherein the control logic places a modified packet from the hold FIFO on the loop immediately after the original of that packet has proceeded from the switch element onto the loop.

5. A packet-switch according to claim 4 characterised in that one or more loop connections are made between switch elements in the loop that are not adjacent to each other thereby bypassing the intervening elements to produce a by-pass, and that the control logic of the upstream element on the by-pass effect the switching of packets addressed to elements downstream of the other switch element on the by-pass to the other element, the by-passed packets being selected for transfer onto the loop by the control logic of the switch element at the downstream end of the by-pass.

6. In a packet-switched data communications system, having a plurality of nodes associated with respective switch elements which are arranged in a loop, for conveying self-addressed packets from source ones of said nodes to destination ones of said nodes, each switch element comprising:

a loop input port, a loop output port and a variable length hold FIFO buffer connected between said loop input and loop output ports, said hold FIFO buffer having a sufficient number of storage locations to hold an entire packet;

a receive register, connected to the loop input port and adapted to convey packets arriving at the loop input to the node that is associated with the switch element;

an output register switchably connected to the loop output port for conveying packets input to the switch element from the associated node; and

control logic means for;

reading the address of each incoming packet in the receive register;

effecting the transfer of originating packets from the output register onto the loop;

effecting the transfer of incoming packets addressed to said switch element to the associated node;

passing on packets addressed to other switch elements that are downstream of said switch element or buffering the latter packets in the hold FIFO until the transmission of an originating packet has been completed; and

buffering packets, addressed to said switch element but which cannot be passed onto the associated node, in the hold FIFO while effecting modification of said packets to ensure their return on the loop to the switch element, and then transferring said packets to the loop output.