Data communication method, data communication system and program

• US 20040153491A1
• Filed: 09/18/2003
• Published: 08/05/2004
• Est. Priority Date: 04/27/2001
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Harada, Atsushi
• Granted Patent: US 7,418,515 B2
• Time in Patent Office: Days
• US Class Current: 709/200
• 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 12/1868 Measures taken after transmission, e.g. acknowledgments
• CPC Class Codes: H04L 12/1881 with schedule organisation, e.g. priority, sequence management
• CPC Class Codes: H04L 12/5602 Bandwidth control in ATM Networks, e.g. leaky bucket

Abstract

To reduce the total amount of reply messages in broadcasting and to make effective use of the bandwidth of a communication route without assuming an error rate in advance.

Data is broadcasted to a plurality of receivers (step 11), then a maximum message length of reply messages from the receivers is calculated (step 13), and a backoff time of the reply messages is calculated (step 14). The maximum message length and the backoff time is sent to the receivers (step 15), then the reply messages having lengths of up to the specified maximum message length are generated by the receivers (step 17), and the reply messages are sent from the receivers at any time within the specified backoff time (step 19).

Claims

1. ) A data communication method comprising the steps of:

broadcasting data to a plurality of receivers;

calculating a maximum message length and a backoff time of reply messages to be returned from the receivers in response to the broadcasted data;

sending the maximum message length and the backoff time to the receivers; and

receiving from respective receivers the respective reply messages sent at any time within the backoff time and having a length equal to or less than the maximum message length.

2. ) The data communication method according to claim 1, wherein in the step of calculating the maximum message length and the backoff time, the total amount of the reply messages from all the receivers is predetermined, then the maximum message length is calculated by dividing the total amount by the number of the receivers, and the backoff time is calculated by dividing the total amount by the bandwidth of a communication route.

3. ) The data communication method according to claim 2, wherein the total amount of data of the reply messages minus the lengths of their headers is calculated from the number of broadcasted blocks of the data.

4. ) The data communication method according to claim 3, wherein

each reply message is a receipt acknowledgement message or a retransmission request message,

the maximum message length Lrm is calculated based on the following equation

Lrm=Lh+F (Nsb)×

MLnac/Nr, and

the backoff time Tbo is calculated based on the following equation

Tbo=Lrm×

Nr/BW,

in which Lh is a header length of the reply message, F is an arbitrary function with a variable Nsb, Nsb is the number of the broadcasted blocks, MLnac is an average message length of a retransmission request per block, Nr is the number of the receivers, and BW is the bandwidth of the communication route.

5. ) The data communication method according to claim 4, wherein

F (Nsb)=C×

Nsb

in which C is a constant.

6. ) The data communication method according to claim 4, wherein

an allowable message length with the maximum of Lpmax and the minimum of Lpmin is defined for the reply messages,

the maximum message length Lrm is modified as Lrm=Lpmax if Lrm is above Lpmax,

the maximum message length Lrm is modified as Lrm=Lpmin if Lrm is below Lpmin, and

the maximum message length Lrm is modified as Lrm=Lworst if Lrm is above the message length Lworst, which is the longest reply message length among combinations of lost blocks of the data.

7. ) The data communication method according to claim 1, wherein

the reply message includes a retransmission request message, and

the retransmission request message includes retransmission requests only for part of unreceived portions of the data.

8. ) The data communication method according to claim 7, wherein the retransmission requests are made for blocks extracted at random from the unreceived portions of the data.

11. ) The data communication method according to claim 1, wherein

the blocks of the data transmitted or received are clusters including original blocks into which the data has been divided and parity blocks generated from the original blocks, and

the number of the retransmission requests included in the reply message corresponds to the number of required parity blocks for each cluster.

9. ) A data communication method comprising the steps of:

receiving data;

receiving a maximum message length and a backoff time of a reply message to be returned in response to the receipt of the data;

generating the reply message having a length equal to or less than the maximum message length for blocks that could not be received in the data;

generating a transmission timing for the reply message at random within the backoff time; and

transmitting the reply message with the transmission timing.

10. ) The data communication method according to claim 9, wherein blocks for which retransmission requests are to be made in the reply message are extracted at random from the blocks that could not be received.

12. ) The data communication method according to claim 9, wherein

the blocks of the data transmitted or received are clusters including original blocks into which the data has been divided and parity blocks generated from the original blocks, and

the number of the retransmission requests included in the reply message corresponds to the number of required parity blocks for each cluster.

13. ) A data communication system comprising:

a unit for broadcasting data to a plurality of receivers;

a unit for calculating a maximum message length and a backoff time of reply messages to be returned from the receivers in response to the broadcasted data;

a unit for sending the maximum message length and the backoff time to the receivers; and

a unit for receiving from respective receivers the respective reply messages sent at any time within the backoff time and having a length equal to or less than the maximum message length.

14. ) The data communication system according to claim 13, wherein in the unit for calculating the maximum message length and the backoff time, the total amount of the reply messages from all the receivers is predetermined, then the maximum message length is calculated by dividing the total amount by the number of the receivers, and the backoff time is calculated by dividing the total amount by the bandwidth of a communication route.

15. ) The data communication system according to claim 14, wherein the total amount of data of the reply messages minus the lengths of their headers is calculated from the number of broadcasted blocks of the data.

16. ) The data communication system according to claim 15, wherein

each reply message is a receipt acknowledgement message or a retransmission request message,

the maximum message length Lrm is calculated based on the following equation

Lrm=Lh+F (Nsb)×

MLnac/Nr, and

the backoff time Tbo is calculated based on the following equation

Tbo=Lrm×

Nr/BW,

in which Lh is a header length of the reply message, F is an arbitrary function with a variable Nsb, Nsb is the number of the broadcasted blocks, MLnac is an average message length of a retransmission request per block, Nr is the number of the receivers, and BW is the bandwidth of the communication route.

17. ) The data communication system according to claim 16, wherein

F (Nsb)=C×

Nsb

in which C is a constant.

18. ) The data communication system according to claim 16, wherein

an allowable message length with the maximum of Lpmax and the minimum of Lpmin is defined for the reply message,

the maximum message length Lrm is modified as Lrm=Lpmax if Lrm is above Lpmax,

the maximum message length Lrm is modified as Lrm=Lpmin if Lrm is below Lpmin, and

the maximum message length Lrm is modified as Lrm=Lworst if Lrm is above the message length Lworst, which is the longest message length among combinations of lost blocks of the data.

19. ) The data communication system according to claim 13, wherein

the reply message includes a retransmission request message, and

the retransmission request message includes retransmission requests only for part of unreceived portions of the data.

20. ) The data communication system according to claim 19, wherein the retransmission requests are made for blocks extracted at random from the unreceived portions of the data.

23. ) The data communication system according to claim 13, wherein

the blocks of the data sent or received are clusters including original blocks into which the data has been divided and parity blocks generated from the original blocks, and

the number of the retransmission requests included in the reply message corresponds to the number of required parity blocks for each cluster.

24. ) The data communication system according to claim 23, wherein

the blocks of the data sent or received are clusters including original blocks into which the data has been divided and parity blocks generated from the original blocks, and

the number of the retransmission requests included in the reply message corresponds to the number of required parity blocks for each cluster.

21. ) A data communication system comprising:

a unit for receiving data;

a unit for receiving a maximum message length and a backoff time of a reply message to be returned in response to the receipt of the data;

a unit for generating the reply message having a length equal to or less than the maximum message length for blocks that could not be received in the data;

a unit for generating a transmission timing of the reply message at random within the backoff time; and

a unit for transmitting the reply message with the transmission timing.

22. ) The data communication system according to claim 21, wherein blocks for which retransmission requests are to be made in the reply message are extracted at random from the blocks that could not be received.