Scheduling of multiple files for serving on a server

• US 20020087685A1
• Filed: 02/22/2001
• Published: 07/04/2002
• Est. Priority Date: 11/13/2000
• Status: Active Grant

• Current Assignee: Qualcomm, Inc.
• Original Assignee: Digital Fountain Incorporated (Qualcomm, Inc.)
• Inventors: Lassen, Soren, Luby, Michael G., Horn, Gavin, Persch, Jeffrey J., Haken, Armin
• Granted Patent: US 7,072,971 B2
• Time in Patent Office: Days
• US Class Current: 709/225
• CPC Class Codes: H04L 67/60 Scheduling or organising the servicing of application requests, e.g. requests for application data transmissions using the analysis and optimisation of the required network resources admission control or resource allocation H04L47/70

Abstract

Multiple files a served using a server coupled to a data network. A plurality of files is determined, wherein a file includes an integer number of blocks, and wherein each block includes at least one input symbol. For each file, an indication of at least one channel on which to serve the file is determined, and, for each file, a rate at which to serve the file is determined. Also, a schedule for processing the blocks is determined, and output symbols for the blocks are generated according to the schedule. The output symbols are transmitted on the corresponding at least one channel, wherein the files are concurrently served at their corresponding rates.

Claims

1. A method for serving multiple files using a server coupled to a data network, the method comprising:

determining a plurality of files, wherein a file includes an integer number of blocks, wherein each block includes at least one input symbol;

for each file, determining an indication of at least one channel on which to serve the file;

for each file, determining a rate at which to serve the file;

determining a schedule for processing the blocks;

generating output symbols for the blocks according to the schedule; and

transmitting the output symbols on the corresponding at least one channel, wherein the files are concurrently served at their corresponding rates.

2. The method of claim 1 wherein determining a plurality of files includes:

receiving at least one of the plurality of files; and

partitioning each of the at least one of the plurality of files into at least one block.

3. The method of claim 1 wherein determining a plurality of files includes receiving at least one of the plurality of files, wherein each of the at least one of the plurality of files is partitioned into at least one block.

4. The method of claim 1 further comprising providing at least one storage device on which to store the plurality of files.

5. The method of claim 1 wherein determining a rate includes receiving an aggregate rate at which to serve the file on the at least one channel.

6. The method of claim 1 wherein determining a rate includes, for each of the at least one channel on which to serve the file, receiving a rate at which to serve the file on the at least one channel.

7. The method of claim 1 wherein, for at least one file, blocks comprising the file are scheduled in a round robin manner.

8. The method of claim 1 wherein each of the files are processed for a same amount of time.

9. The method of claim 1 wherein each of the blocks are processed for a same amount of time.

10. The method of claim 1 wherein, for at least one of the files, the file is processed for an amount of time based on a length of the file.

11. The method of claim 1 wherein, for at least one of the files, the file is processed for an amount of time based on the corresponding rate of the file.

12. The method of claim 1 wherein determining a schedule includes determining a file schedule in which to generate output symbols for the plurality of files, and for each file, determining a block schedule in which to generate output symbols for the blocks comprising the file.

13. The method of claim 1 wherein determining a schedule includes determining a schedule of time slots, wherein at least one time slot corresponds to each file, and wherein generating output symbols for the blocks according to the schedule includes, during the at least one time slot, generating output symbols for at least one block from the corresponding file.

14. The method of claim 13 wherein a number of the at least one time slot corresponding to each file is based on the corresponding rate of the file.

15. The method of claim 13 wherein a number of the at least one time slot corresponding to each file is based on a length of the file.

16. The method of claim 13 wherein a number of the at least one time slot corresponding to each file is based on a length and the corresponding rate of the file.

17. The method of claim 1 wherein each time output symbols for a block are generated according to the schedule, at least a minimum number of output symbols are generated for the block.

18. The method of claim 1 wherein each time output symbols for a block are generated according to the schedule, at most a maximum aggregate length of output symbols are generated for the block.

19. The method of claim 1 wherein each time output symbols for a block are generated according to the schedule, at most a maximum number of output symbols are generated for the block.

20. The method of claim 1 wherein at least one of the blocks is a compound block.

21. The method of claim 1 further comprising storing the output symbols in a buffer, and wherein transmitting the output symbols includes reading the output symbols from the buffer.

22. The method of claim 21 wherein determining a schedule includes choosing a next block for which to generate output symbols based on when stored output symbols corresponding to the block will be completely read from the buffer.

23. The method of claim 21 further comprising, for at least one of the files, assigning a buffer space to the at least one file, wherein storing the output symbols includes storing output symbols corresponding to the at least one of the files in the buffer space.

24. The method of claim 23 wherein a length of the assigned buffer space is based on the corresponding rate of the file.

25. The method of claim 23 wherein a length of the assigned buffer space is based on a length of the file.

26. The method of claim 23 wherein a length of the assigned buffer space is based on the corresponding rate of the file and a length of the file.

27. The method of claim 23 wherein a length of the assigned buffer space is a same length for each of the at least one of the files.

28. The method of claim 23 wherein a length of the assigned buffer space is based on corresponding lengths and the corresponding rates of the plurality of files being served.

29. The method of claim 23 wherein a length of the assigned buffer space varies over time.

30. The method of claim 23 wherein an aggregate length of the plurality of files is less than or equal to a maximum aggregate file length, wherein a length of the assigned buffer space is based on the maximum aggregate file length.

31. The method of claim 23 wherein an aggregate rate at which the plurality of files is served is less than or equal to a maximum aggregate rate, wherein a length of the assigned buffer space is based on the maximum aggregate rate.

32. The method of claim 21 wherein the buffer is included in a fast access memory.

33. The method of claim 21 wherein the buffer is included on at least one disk.

34. The method of claim 33 further including storing at least one of the files on the at least one disk.

35. The method of claim 33 wherein the buffer and the plurality of files are stored on first and second disks, the method further comprising reading a block to be processed from the first disk while storing output symbols on the second disk.

36. The method of claim 33 wherein the buffer and the plurality of files are stored on first and second disks, the method further comprising reading a block to be encoded from the first disk while reading output symbols from the second disk.

37. The method of claim 33 wherein the buffer and the plurality of files are stored on first and second disks, the method further comprising storing output symbols to the first disk while reading output symbols from the second disk.

38. The method of claim 21 further comprising, prior to transmitting any of the output symbols:

for each of at least some of the blocks, generating an initial aggregate length of output symbols;

wherein, for each of the at least some of the blocks, the initial aggregate length of output symbols is based on the schedule.

39. The method of claim 21 wherein output symbols are stored in the buffer according to a buffer input order, and wherein output symbols are read from the buffer according to a buffer output order.

40. The method of claim 39 wherein the buffer includes rows and columns, wherein, for each block, output symbols are stored in a row corresponding to the block, and wherein output symbols are read from the buffer in a column by column manner.

41. The method of claim 40 wherein output symbols are read from each column in a permuted manner.

42. The method of claim 39 wherein output symbols are read from the buffer in a random or pseudo random order.

43. The method of claim 39 wherein output symbols corresponding to a block are transmitted in a same sequence in which the corresponding output symbols were generated.

44. The method of claim 39 wherein a next output symbol corresponding to a block to be read from the buffer is the last output symbol corresponding to the block stored in the buffer.

45. The method of claim 39 wherein output symbols corresponding to a block are read from the buffer in a random or pseudo random order.

46. The method of claim 21 wherein the buffer is stored on a plurality of disks, and wherein storing output symbols includes, for at least one block, storing output symbols to more than one of the disks.

47. The method of claim 46 further comprising determining a disk on which to store a set of at least one output symbol corresponding to a block that is different from the disk on which a previous set of at least one output symbol corresponding to the block was stored.

48. The method of claim 47 wherein determining a disk includes choosing one of the plurality of disks in a round robin manner.

49. The method of claim 47 wherein determining a disk includes choosing one of the plurality of disks that is not being currently accessed.

50. The method of claim 1 wherein generating output symbols includes using a chain reaction code.

51. The method of claim 1 wherein generating output symbols includes using a FEC code.

52. The method of claim 1 wherein first and second output symbols are generated for first and second blocks, respectively, using a same key.

53. The method of claim 52 wherein the first and second output symbols are generated in series.

54. The method of claim 52 wherein the first and second output symbols are generated in parallel.

55. The method of claim 1 further comprising:

storing a first block for which output symbols are to be generated in a first buffer; and

storing a second block for which output symbols are to be generated in a second buffer while output symbols are generated from the first block stored in the first buffer;

wherein the first and second buffers are included in a memory.

56. The method of claim 1 wherein the plurality of files are stored on a plurality of disks, wherein determining the plurality of files includes reading blocks from the plurality of disks, and wherein the schedule according to which blocks are processed is based on positions at which the blocks are stored on the plurality of disks.

57. The method of claim 1 wherein the plurality of files are stored on a plurality of disks, wherein determining the plurality of files includes, for each block in a file, accessing one of the plurality of disks on which the block is stored to read the block, wherein the schedule according to which blocks are processed is based on an order in which each of the plurality of disks is accessed.

58. The method of claim 1 wherein a length of each block is at most a maximum block length.

59. The method of claim 1 wherein a length of each block is at least a minimum block length.

60. The method of claim 1 wherein a length of each input symbol la same length.

61. The method of claim 1 wherein a length of each input symbol is a power of two.

62. The method of claim 1 wherein a length of each input symbol is at most a maximum input symbol length.

63. The method of claim 1 wherein a length of each input symbol is at least a minimum input symbol length.

64. The method of claim 1 wherein, for each block, a length of each input symbol and a length of each output symbol generated for the block is a same length.

65. The method of claim 1 wherein at least one of the files comprises one block.

66. The method of claim 1 wherein each block of a file has a same length.

67. The method of claim 1 further comprising, for each file, appending input symbols of a fixed value to the file, if needed, such that the file comprises a desired number of input symbols.

68. The method of claim 1 further comprising, for each block of a file, appending input symbols of a fixed value to the block, if needed, such that the block comprises a desired number of input symbols.

69. The method of claim 1 wherein each block includes a prime number of input symbols.

70. The method of claim 1 wherein each file includes 2ⁿ blocks, wherein n is an integer greater than or equal to zero.

71. The method of claim 1 further comprising assembling output symbols into packets for transmission.

72. The method of claim 71 wherein a key for each output symbol in the packet is included in each packet.

73. The method of claim 71 wherein each packet includes a packet key, wherein a key for each output symbol in the packet is obtainable as a function of the packet key.

74. The method of claim 73 wherein the function is a random or a pseudo-random function.

75. A method for serving a file using a server coupled to a data network, the method comprising:

determining a file, wherein the file includes an integer number of compound blocks, wherein each compound block includes at least one basic block, wherein each basic block includes at least one input symbol;

determining an indication of at least one channel on which to serve the file;

determining a rate at which to serve the file;

determining a schedule for processing the basic blocks;

generating output symbols for the basic blocks according to the schedule, wherein basic blocks comprising each compound block are generated using a same set of operations;

assembling basic blocks into compound output symbols; and

transmitting the compound output symbols on the corresponding at least one channel, such that the file is served at the corresponding rate.

76. The method of claim 75 wherein generating output symbols includes using a chain reaction code.

77. The method of claim 75 wherein generating output symbols includes using a FEC code.

78. The method of claim 75 wherein generating output symbols includes generating basic output symbols for at least two basic blocks corresponding to the same compound block in sequence.

79. The method of claim 75 wherein generating output symbols includes generating basic output symbols for at least two basic blocks corresponding to the same compound block concurrently.

80. The method of claim 79 further comprising storing in a storage device basic output symbols for the at least two encoded basic blocks in an interleaved manner.

81. The method of claim 75 wherein each basic block comprising a compound block is a same length.

82. The method of claim 75 wherein each compound block comprises a power of 2 basic blocks.

83. The method of claim 75 wherein transmitting the compound output symbols includes transmitting the compound output symbols in packets.

84. The method of claim 83 wherein each packet includes an integer number of compound output symbols.

85. The method of claim 83 wherein each packet includes a key for each compound output symbol included in the packet.

86. The method of claim 83 wherein each packet includes a plurality of compound output symbols, and wherein the packet includes a packet key from which keys for all the compound output symbols within the packet can be derived.

87. A method for recovering a file using a client coupled to a data network, wherein the file includes an integer number of blocks, wherein each block includes at least one input symbol, the method comprising:

receiving a plurality of output symbols generated from each of the blocks;

for each block, storing output symbols corresponding to the block in a fast access memory; and

for each block, decoding the output symbols corresponding to the block in place in the fast access memory to recover the block.

88. The method of claim 87 wherein the output symbols are generated using a chain reaction code.

89. The method of claim 87 wherein the output symbols are generated using a FEC code.

90. The method of claim 87 further comprising:

storing output symbols corresponding to a first block in a first buffer of the fast access memory; and

storing output symbols corresponding to a second block in a second buffer of the fast access memory while decoding the output symbols in the first buffer.

91. The method of claim 87 wherein the plurality of blocks are recovered in a block order.

92. A method for recovering a compound block using a client coupled to a data network, wherein a compound block includes a grouping of one or more basic blocks, the method comprising:

receiving a plurality of compound output symbols generated from the compound block, wherein each compound output symbol includes a plurality of basic output symbols generated from at least one basic block using a same set of operations;

determining at least one schedule of operations based on the compound output symbols; and

for each basic block, applying one of the at least one schedule of operations to the basic output symbols corresponding to the basic block to recover the basic block.

93. The method of claim 92 wherein the compound output symbols are generated using a chain reaction code.

94. The method of claim 92 wherein the compound output symbols are generated using a FEC code.

95. The method of claim 92 wherein the compound block comprises a file.

96. The method of claim 92 wherein the compound block is one of a plurality of compound blocks that comprise a file.

97. The method of claim 92 wherein for at least two of the basic blocks the same schedule of operations is applied.

98. The method of claim 92 wherein for all of the basic blocks the same schedule of operations is applied.

99. The method of claim 92 wherein a first schedule of operations is applied to the basic output symbols corresponding to a first basic block, and the first schedule of operations is subsequently applied to the basic output symbols corresponding to a second basic block.

100. The method of claim 92 wherein one of the at least one schedule of operations is concurrently applied to the basic output symbols corresponding to a first basic block and to the basic output symbols corresponding to a second basic block.

101. The method of claim 100 wherein the basic output symbols corresponding to the first block are stored in a storage device in an interleaved manner with the basic output symbols corresponding to the second block while the schedule of operations is applied.

102. The method of claim 92 further comprising storing the basic output symbols corresponding to at least one basic block in a fast access memory, wherein applying one of the at least one schedule of operations includes decoding the at least one basic block in place in the fast access memory.

103. The method of claim 92 further comprising:

storing basic output symbols corresponding to a first basic block in a first buffer of a fast access memory; and

storing basic output symbols corresponding to a second basic block in a second buffer of the fast access memory while one of the at least one schedule of operation is applied to the basic output symbols in the first buffer.

104. The method of claim 92 wherein the plurality of basic blocks are recovered in a basic block order.

105. The method of claim 104 wherein the compound block is one of a plurality of compound blocks that comprise a file, wherein the basic block order includes basic blocks from at least one other compound block.

106. The method of claim 104 wherein the basic block order is according to an order in which basic blocks are grouped within the compound block.

107. The method of claim 104 wherein the basic block order is according to an order in which the basic blocks will be used by an application.