Adaptive data link protocol

• US 4,970,714 A
• Filed: 01/05/1989
• Issued: 11/13/1990
• Est. Priority Date: 01/05/1989
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Chen, Mon-Song, Zumbo, Dominick A., Meleis, Hanafy E., Goldstein, Barry C.
• Primary Examiner(s): Olms, Douglas W.
• Assistant Examiner(s): Marcelo, Meluin
• Application Number:
  US07/294,086
• Time in Patent Office: 677 Days
• Field of Search: 370/60, 370/85, 370/94, 370/61, 370/79, 370/85.1, 370/94.1, 370/13, 370/17, 371/32
• US Class Current: 370/216
• CPC Class Codes: H04L 1/0007 by modifying the frame length
• CPC Class Codes: H04L 1/1671 the supervisory signal being transmitted together with control information
• CPC Class Codes: H04L 1/1685 the supervisory signal being transmitted in response to a specific request, e.g. to a polling signal
• CPC Class Codes: H04L 1/1806 Go-back-N protocols
• CPC Class Codes: H04L 1/1825 Adaptation of specific ARQ protocol parameters according to transmission conditions
• CPC Class Codes: H04L 1/1832 Details of sliding window management
• CPC Class Codes: H04L 1/1835 Buffer management
• CPC Class Codes: H04L 1/187 Details of sliding window management
• CPC Class Codes: H04L 1/188 Time-out mechanisms
• CPC Class Codes: H04L 2001/0094 Bus

Abstract

A communication system provides high speed transmission of data over a link, such as a fiber optic link, between a first terminal and a second terminal. The architecture and protocol permits the use of dedicated hardware such as state machines constructed of programmable array logic units, to synchronize the transmission and reception of data packets and the retransmission of designated ones of these packets in the event of a faulty transmission. Packets to be transmitted and received are stored in an array of frames in sub-windows of a memory storage window in each of the termianls, the frame number being equal to the sequence number of the data packet. By embedding sequence and status bits in each packet within control words and bits appended to each packet, the state machine in each terminal can readily track the progress of each packet so as to request acknowledgement of error-free receipt, to send an acknowledgement, to request a retransmission of a packet designated by its serial number and to distinguish a retransmitted packet from an original packet transmitted with error.

Claims

1. A method of adaptively controlling a data link to compensate for variation in error in a transmission of data from a first terminal to a second terminal, the method comprising:

storing data at the first terminal in a transmit memory as an array of data frames arranged in a window of the transmit memory;

dividing the window into sub-windows each having less frames than said window;

transmitting data from successive ones of said frames in a sequence of packets wherein data in a packet is obtained from one frame;

embedding control signals in each of said packets, said control signals identifying packets by sequence number;

receiving said packets at said terminals;

checking said packets by tests for sequence number and bit error for detection of a transmission fault;

storing data of only those packets which pass said tests in a receive memory at said second terminal,

packets which fail at least one of said tests being rejected packets;

retransmitting rejected packets from said first terminal to said second terminal;

counting the number of rejected packets occurring during a transmission of a window of data to obtain a packet error rate; and

altering the sizes of said sub-windows in accordance with the packet error rate to minimize the delay of re-transmission and increase the utilization of the link.

2. A method according to claim 1 further comprising a step of reporting back to said first terminal from said second terminal an error signal designating the sequence number of a rejected packet.

3. A method according to claim 2 wherein, during said step of retransmitting, there is a retransmission of packets which were transmitted subsequent to said rejected packets in accordance with a GO-BACK algorithm.

4. A method according to claim 3 wherein, during said step of retransmitting, there is a step of embedding in each packet of said rejected and said subsequent packets a control signal identifying each packet as a retransmitted packet.

5. A method according to claim 1 wherein, subsequent to the completion of transmission of all frames of a sub-window, there is a step of sending from said first terminal to said second terminal a request signal for acknowledgement, said request signal being embedded as a part of said control signal in a subsequently transmitted packet.

6. A method according to claim 5 further comprising a step of reporting back to said first terminal from said second terminal an acknowledgement signal acknowledging that packets previously received at said second terminal have passed said tests.

7. A method according to claim 6 further comprising a step of timing an interval of time elapsing between said request-for-acknowledgement signal and receipt of an acknowledgement signal.

8. A method according to claim 7 wherein, during said step of transmitting, there is a retransmission of packets which were transmitted subsequent to said rejected packet in accordance with a GO-BACK algorithm.

9. A method according to claim 8 wherein said timing of said interval includes time elapsed for retransmission of a rejected packet and wherein, upon detection of a transmission fault followed by a retransmission, acknowledgement follows said retransmission.

10. A method according to claim 1 wherein the sequence number is equal to the number of the frame in said window containing data of the packet bearing said sequence number.

11. A method according to claim 10 wherein data of said receive memory is stored in an array of frames in a window of said received memory identical to the array of frames in the window of said transmit memory.

12. A method of adaptively controlling a data link to compensate for variation in error in a transmission of data from a first terminal to a second terminal, the method comprising:

storing data at the first terminal in a transmit memory as an array of data frames arranged in a window of the transmit memory;

dividing the window into sub-windows each having less frames than said window;

transmitting data from successive ones of said frames in a sequence of packets wherein data in a packet is obtained from one frame;

embedding control signals in each of said packets, said control signals identifying packets by sequence number;

receiving said packets at said terminals;

checking said packets by tests for sequence number and bit error for detection of a transmission fault;

storing data of only those packets which pass said tests in a receive memory at said second terminal, packets which fail at least one of said tests being rejected packets;

retransmitting rejected packets from said first terminal to said second terminal;

counting the number of rejected packets occurring during a transmission of a window of data to obtain a packet error rate;

altering the sizes of said sub-windows in accordance with the packet error rate to maximize a speed of data transmission along said data link;

reporting back to said first terminal from said second terminal an error signal designating the sequence number of a rejected packet;

wherein, during said step of retransmitting, there is a retransmission of packets which were transmitted subsequent to said rejected packets in accordance with a GO-BACK algorithm;

during said step of retransmitting, there is a step of embedding in each packet of said rejected and said subsequent packets a control signal identifying each packet as a retransmitted packet;

the sequence number is equal to the number of the frame in said window containing data of the packet bearing said sequence number; and

data of said receive memory is stored in an array of frames in a window of said received memory identical to the array of frames in the window of said transmit memory.

13. A method according to claim 12 wherein

subsequent to the completion of transmission of all frames of a sub-window, there is a step of sending from said first terminal to said second terminal a request signal for acknowledgement, said request signal being embedded as a part of said control signal in a subsequently transmitted packet;

the method further comprising a step of reporting back to said first terminal from said second terminal an acknowledgement signal acknowledging that packets previously received at said second terminal have passed said tests.

14. A method of adaptively controlling a data link to compensate for variation in error in a transmission of data from a first terminal to a second terminal, the method comprising:

storing data at the first terminal in a transmit memory as an array of data frames arranged in a window of the transmit memory;

dividing the window into sub-windows each having less frames than said windows;

transmitting data from successive ones of said frames in a sequence of packets wherein data in a packet is obtained from one frame;

embedding control signals in each of said packets, said control signals identifying packets by sequence number;

receiving said packets at said terminals;

checking said packets by tests for sequence number and bit error for detection of a transmission fault;

storing data of only those packets which pass said tests in a receive memory at said second terminal, packets which fail at least one of said tests being rejected packets;

retransmitting rejected packets from said first terminal to said second terminal;

reporting back to said first terminal from said second terminal an error signal designating the sequence number of a rejected packet;

counting the number of error signals occurring during the transmission of a window of data to obtain a packet error rate;

wherein the sequence number is equal to the number of the frame in said window containing data of the packet bearing said sequence number;

data of said receive memory is stored in an array of frames in a window of said received memory identical to the array of frames in the window of said transmit memory;

subsequent to the completion of transmission of all frames of a sub-window, there is a step of sending from said first terminal to said second terminal a request signal for acknowledgement, said request signal being embedded as a part of said control signal in a subsequently transmitted packet;

said method further comprising reporting back to said first terminal from said second terminal an acknowledgement signal acknowledging that packets previously received at said second terminal have passed said tests; and

wherein an error signal is produced by comparing sequence numbers of stored data in said receive memory with frame numbers of frames storing data;

said method

further comprising a step of altering a repetition frequency of the acknowledgement - request signals in accordance with the packet error rate to maximize a speed of data transmission along said data link.

15. A method of adaptively controlling a data link to compensate for variation in error in a transmission of data from a first terminal to a second terminal, the method comprising:

transmitting a sequence of data packets from said first terminal to said second terminal to be received at said second terminal;

sending a request signal from said first terminal for acknowledgement of receipt of the data packets by said second terminal, said sending being done periodically after a predetermined number of data packets;

reporting back to said first terminal from said second terminal, in response to said acknowledgement - request signal, a response signal acknowledging receipt of error - free packets, said response signal being an error signal in the case of receipt of a packet with error;

retransmitting packets which were received with error in accordance with a GO-BACK algorithm;

formulating a packet error rate by comparing the number of error signals with the number of packets transmitted; and

altering a repetition frequency of said acknowledgement - request signals in accordance with said packet - error rate, an increase in error rate producing an increase in said repetition frequency so as to increase the transmission speed of a sequence of data packets.

16. A method according to claim 15 further comprising:

identifying each packet with a sequence number;

rejecting a packet having an error;

reporting back to said first terminal from said second terminal an error signal designating the sequence number of a rejected packet;

embedding control signals in each of said packets, said control signals identifying packets by sequence number; and

wherein, during said step of retransmitting, there is a step of embedding in each packet a control signal identifying each packet as a retransmitted packet.

17. A method of adaptively controlling a data link to compensate for variation in error in a transmission of data from a first terminal to a second terminal, the method comprising:

storing data at the first terminal in a transmit memory as an array of data frames arranged in a window of the transmit memory;

dividing the window into sub-windows each having less frames than said window;

transmitting data from successive ones of said frames in a sequence of packets wherein data in a packet is obtained from one frame;

embedding control signals in each of said packets, said control signals identifying packets by sequence number;

receiving said packets at said terminals;

checking said packets by testing for a transmission fault;

storing data of only those packets which pass said testing in a receive memory at said second terminal, packets which fail said testing being rejected packets;

retransmitting rejected packets from said first terminal to said second terminal;

obtaining a packet error rate by monitoring rejected packets occurring during a transmission of a window of data; and

altering the sizes of said sub-windows in accordance with the packet error rate to maximize a speed of data transmission along said data link.