Method and a device for scheduling and sending data packets from a common sender to a plurality of users sharing a common transmission channel

• US 7,450,602 B2
• Filed: 10/21/2005
• Issued: 11/11/2008
• Est. Priority Date: 10/22/2004
• Status: Expired due to Fees

• Current Assignee: Agence Spatiale Europeenne
• Original Assignee: Agence Spatiale Europeenne
• Inventors: Vazquez Castro, Maria Angeles
• Primary Examiner(s): Cho; Hong Sol
• Application Number:
  US11/254,678
• Publication Number:
  US 20060104299A1
• Time in Patent Office: 1,117 Days
• Field of Search: 370412-418, 370/428, 370/429
• US Class Current: 370/412
• CPC Class Codes: H04B 7/18582 Arrangements for data linking, i.e. for data framing, for error recovery, for multiple access
• CPC Class Codes: H04L 1/0003 by switching between different modulation schemes
• CPC Class Codes: H04L 1/0009 by adapting the channel coding H04L1/1812 takes precedence
• CPC Class Codes: H04L 47/50 Queue scheduling
• CPC Class Codes: H04L 47/521 Static queue service slot or fixed bandwidth allocation
• CPC Class Codes: H04L 47/522 Dynamic queue service slot or variable bandwidth allocation
• CPC Class Codes: H04L 47/6225 Fixed service order, e.g. Round Robin

Abstract

The invention, which applies to satellite digital communications systems in particular, relates to a device and a method of scheduling and sending data packets with a required level of protection from a common sender to a plurality of users sharing a common transmission channel. The method comprises the steps of:

• • receiving a stream of input data packets;
  • splitting the packets between a plurality of queues;
  • extracting the leading packets therefrom using a first scheduling algorithm;
  • storing each packet in a particular buffer as a function of the required level of protection; and
  • extracting data blocks therefrom using a second scheduling algorithm.
    The packets are split between said queues in accordance with a geographical position criterion in respect of the user to whom each packet is addressed.

Claims

1. A method of scheduling and sending data packets with a required level of protection from a common sender to a plurality of users sharing a common transmission channel, the method comprising the steps of:

receiving a stream of input data packets;

splitting said packets between a plurality of queues;

extracting the leading packets from said queues using a first scheduling algorithm;

storing each packet in a particular buffer of a set of buffers as a function of the level of protection required when sending it;

extracting data blocks from said buffers using a second scheduling algorithm; and

sending said data blocks with the required level of protection over said common transmission channel;

wherein the packets are split between said plurality of queues in accordance with a geographical position criterion in respect of the user to whom each packet is addressed.

2. A method according to claim 1, wherein said step of splitting said packets between queues in accordance with a geographical position criterion includes identifying geographical areas such that the time series of values of a quantity representing transmission channel conditions for users situated in the same area are correlated with each other on average.

3. A method according to claim 2, wherein identifying geographical areas takes into account the spatial distribution of users in order to centre said geographical areas on the highest user density regions so that the limits between areas are in regions of lower user density.

4. A method according to claim 2, wherein identifying geographical areas is based on information representing transmission channel conditions.

5. A method according to claim 4, wherein each user sends said information representing transmission channel conditions to the common sender via a backward channel.

6. A method according to claim 4, wherein identifying geographical areas is repeated periodically.

7. A method according to claim 4, wherein said information representing transmission channel conditions indicates the signal to noise plus interference ratio.

8. A method according to claim 1, wherein the level of protection required for sending each data packet is determined as a function of information representing transmission channel conditions sent by each user to the common sender via a backward channel.

9. A method according to claim 1, also including a step of coding said data blocks with a coding weight depending on the required level of protection.

10. A method according to claim 1, further including a step of grouping the bits of said data blocks into symbols with the number of bits per symbol depending on the required level of protection.

11. A method according to claim 10, further including sending said symbols to said users via said shared transmission channel at a constant symbol data rate.

12. A method according to claim 1, wherein said first scheduling algorithm is executed faster than said second scheduling algorithm.

13. A method according to claim 1, wherein said first scheduling algorithm is a round-robin scheduling algorithm.

14. A method according to claim 1, wherein said second scheduling algorithm is a weighted adaptive round-robin scheduling algorithm with time-out.

15. A method according to claim 1, wherein, before extracting a data packet from one of said queues, said first scheduling algorithm verifies the state of occupancy of the buffer for which said packet is intended and extracts said packet only if said buffer can store it.

16. A method according to claim 1, wherein said common transmission channel is a satellite transmission beam.

17. A device for scheduling data packets to be sent with a required level of protection from a common sender to a plurality of users sharing a common transmission channel, the device including:

an input for receiving a stream of data packets to be sent;

a packet classifier for splitting said packets between a plurality of queues;

a set of memory locations for providing a plurality of queues;

a set of buffers;

a first scheduler for extracting leading packets from said queues using a first scheduling algorithm and forwarding them to a particular buffer memory of said set as a function of the level of protection required when sending it; and

a second scheduler for extracting data blocks from said buffers using a second scheduling algorithm;

wherein said packet classifier comprises means for splitting the packets between said queues according to a geographical position criterion in respect of the user to whom each packet is addressed.

18. A device according to claim 17, further including an adaptive coding and modulation unit for coding data blocks and grouping coded bits into modulation symbols as a function of said required protection level.

19. A device according to claim 17, further including an input for receiving information representing transmission channel conditions for each user.

20. A device according to claim 19, wherein said input is connected to a backward channel over which each user sends said information representing transmission channel conditions.

21. A device according to claim 19, further including means for determining the level of protection required for sending each packet on the basis of said information representing transmission channel conditions.

22. A device according to claim 19, further including means for modifying said geographical criterion on the basis of said information representing transmission channel conditions.

23. A device according to claim 17, further including means for modifying the scheduling algorithm of the second scheduler according to a signal representing the state of occupancy of the buffers.

24. A device according to claim 17, further including means for preventing, according to a signal representing the state of occupancy of the buffers, the extraction of a leading packet from one of said queues on behalf of the first scheduler if the buffer to which said packet is addressed does not have sufficient free capacity to store it.

25. A device according to claim 17, further including means for controlling the speed of operation of the first scheduler and the second scheduler so that the first scheduling algorithm is executed faster than the second scheduling algorithm.

26. A device according to claim 17, wherein said common transmission channel is a satellite transmission beam.