MULTI-OUTPUT PACKET SERVER WITH INDEPENDENT STREAMS

• US 20070233891A1
• Filed: 02/26/2007
• Published: 10/04/2007
• Est. Priority Date: 03/09/2001
• Status: Active Grant

• Current Assignee: Qualcomm, Inc.
• Original Assignee: Digital Fountain Incorporated (Qualcomm, Inc.)
• Inventors: Luby, Michael, Attias, Roberto, Vainish, Ronen, Hernek, Diane, Perrig, Adrian, Rasmussen, Lars, Simu, Serban, Kushi, David, Walfish, Michael, Byers, John
• Granted Patent: US 8,185,809 B2
• Time in Patent Office: Days
• US Class Current: 709/231
• CPC Class Codes: H04L 69/14 Multichannel or multilink protocols

Abstract

A method of serving content to multiple clients via a network is provided. Independent sessions with each of a plurality of clients are maintained, wherein the number of clients in the plurality of clients can vary over time, and wherein the start of each session and the end of each session can be independent of the start and end of other sessions. A stream of packet payloads is received, each packet payload of the stream of packet payloads including data generated from the content, wherein each packet payload in at least a subset of the stream of packet payloads includes a different set of data. Each packet payload in the stream of packet payloads is transmitted to each client of the plurality of clients in corresponding packets, wherein the packet payload transmitted to a client at any particular time is independent of the state of the corresponding session.

Claims

1. A method of serving content from a content server to multiple clients via a network, the method comprising:

maintaining independent sessions between a content server and each of a plurality of clients, wherein the number of clients in the plurality of clients can vary over time, and wherein the start of each session and the end of each session can be independent of the start and end of other sessions;

receiving a stream of packet payloads by the content server, each packet payload of the stream of packet payloads including a random or pseudorandom set of output symbols encoded with data generated from the content, wherein each packet payload in at least a subset of the stream of packet payloads includes a different set of data;

transmitting from the content server each packet payload in the stream of packet payloads to each client of the plurality of clients in corresponding packets, wherein each packet payload transmitted at any particular time to some or all of the plurality of clients is independent of which packet payloads had been previously correctly received by various ones of the clients, and wherein each of the plurality of clients is capable of reconstructing the content after correctly receiving a number of different output symbols sufficient in quantity to reconstruct the data to a desired accuracy from those different output symbols.

2. The method of claim 1 wherein the content comprises an ordered set of input symbols, wherein each packet payload of the stream of packet payloads includes at least one output symbol, wherein output symbols are generated from input symbols, and wherein a client can regenerate the ordered set of input symbols to a desired accuracy from the output symbols included in a set of packet payloads received by the client.

3. The method of claim 2 wherein the set of packet payloads received by the client can be received via a plurality of distinct sessions.

4. The method of claim 2 wherein output symbols are generated from input symbols using a FEC code.

5. The method of claim 2 wherein output symbols are generated from input symbols such that the ordered set of input symbols can be regenerated using any set of N number of the output symbols, wherein N is an integer greater than 1 and less than the number of possible output symbols.

6. The method of claim 2 wherein output symbols are input symbols.

7. The method of claim 1 wherein the packets are unicast packets.

8. The method of claim 7 wherein the unicast packets are UDP unicast packets.

9. The method of claim 7 wherein the unicast packets are TCP packets.

10. The method of claim 1 further comprising maintaining a list of the plurality of clients.

11. The method of claim 10 further comprising:

receiving, via the network, a message from a client not included in the list of the plurality of clients, requesting to be added to the list; and

adding the client to the list.

12. The method of claim 11 further comprising:

receiving, via the network, a message from a client included in the list requesting to be removed from the list; and

removing the client from the list.

14. The method of claim 11 further comprising transmitting to the client not included in the list of the plurality of clients a cookie, and wherein adding the client to the list includes adding the client to the list, only if the message received from the client includes the cookie.

17. The method of claim 10 wherein maintaining the list of the plurality of clients includes:

adding a client to the list upon receiving, via the network, a connect message from the client; and

removing the client from the list at a time subsequent to the time at which the connect message was received from the client.

18. The method of claim 10 wherein maintaining the list of the plurality of clients includes:

receiving, via the network, a first join message from one of the clients in the list; and

removing the corresponding client from the list at a time subsequent to receiving the join message.

19. The method of claim 18 wherein the first join message includes a time value that indicates when to remove the corresponding client from the list, and wherein removing the corresponding client from the list includes removing the corresponding client from the list at a time based on the time value.

20. The method of claim 19 wherein the time value is a length of time.

21. The method of claim 19 wherein the time value is an absolute time.

22. The method of claim 18 further comprising:

receiving, via the network, a second join message from the client prior to the time at which to remove the current client from the list indicated by the first join message; and

setting a new time at which to remove the current client from the list, the new time based on the second join message.

23. The method of claim 1 further comprising, prior to transmitting each packet payload in the stream of packet payloads to one of the clients in the plurality of clients, authenticating the client.

24. The method of claim 23 wherein authenticating the client includes:

transmitting a cookie to the client;

receiving a connect message from the client; and

verifying that the cookie is included in the connect message.

25. The method of claim 23 wherein authenticating the client includes:

transmitting a cookie to the client;

receiving a join message from the client; and

verifying that the cookie is included in the join message.

26. The method of claim 1 wherein maintaining independent sessions with each of the plurality of clients includes maintaining independent channel connections within a session with each of a first plurality of clients and with each of a second plurality of clients;

wherein receiving a stream of packet payloads includes receiving a first stream of packet payloads on a first channel and a second stream of packet payloads on a second channel, wherein each packet payload of the first stream of packet payloads includes data comprising a first subset of the content to be transferred to the first plurality of clients, wherein each packet payload of the second stream of packet payloads includes data comprising a second subset of the content to be transferred to the second plurality of clients;

wherein transmitting each packet payload in the stream of packet payloads includes transmitting each packet payload in the first stream of packet payloads to each client of the first plurality of clients in corresponding packets, and transmitting each packet payload in the second stream of packet payloads to each client of the second plurality of clients in corresponding packets.

29. The method of claim 26 wherein the first subset of the content and the second subset of the content are different subsets of the content.

37. The method of claim 1 wherein the network includes a multicast network, the method further comprising:

maintaining a multicast session, wherein a plurality of multicast clients can join the multicast session, wherein the number of the plurality of multicast clients joined to the multicast session can vary over time;

transmitting, via the multicast network, each packet payload in the stream of packet payloads to each multicast client of the plurality of multicast clients in corresponding multicast packets.

13. (canceled)

15-16. -16. (canceled)

27-28. -28. (canceled)

30-36. -36. (canceled)

38. An apparatus for serving content to multiple clients via a network, the apparatus comprising:

a client manager coupled to the network that maintains independent sessions with each of a plurality of clients;

a buffer coupled to receive a stream of packet payloads, each packet payload of the stream of packet payloads including a random or pseudorandom set of output symbols encoded with data generated from the content, wherein each packet payload in at least a subset of the stream of packet payloads includes a different set of data;

a replication engine coupled to the buffer that, for each packet payload, generates a plurality of packets that include the packet payload, each packet of the plurality of packets corresponding to one of the plurality of clients;

a transmitter coupled to the replication engine that receives the packets and transmits the packets to the corresponding clients via the network;

wherein each packet payload transmitted at any particular time to some or all of the plurality of clients is independent of which packet payloads had been previously correctly received by various ones of the clients, and wherein each of the plurality of client is capable of reconstructing the content after correctly receiving a number of different output symbols sufficient in quantity to reconstruct the data to a desired accuracy from those different output symbols.

39. The apparatus of claim 38 further comprising a memory coupled to the client manager for maintaining a list of the plurality of clients.

40. The apparatus of claim 39 further comprising a connection manager coupled with the network and with the memory, the connection manager configured to receive a request to add a new client to the list and configured to add the new client to the list.

41. The apparatus of claim 39 wherein the client manager is configured to remove a client from the list.

42. The apparatus of claim 38 wherein the client manager is configured to receive a packet lost message from one of the plurality of clients, the packet lost message indicating the one of the plurality of clients did not receive a packet that included one of the plurality of packet payloads, and, in response to the packet lost message, cause the replication engine to generate another packet to replace the lost packet, wherein the payload of the another packet includes data different from the data included in the packet payload that the client did not receive.

43. The apparatus of claim 38 wherein the client manager maintains independent channel connections within a session with each of a first plurality of clients and each of a second plurality of clients;

wherein the stream of packet payloads includes a first stream of packet payloads on a first channel and a second stream of packet payloads on a second channel, wherein each packet payload of the first stream of packet payloads includes data comprising a first subset of the content to be transferred to the first plurality of clients, wherein each packet payload of the second stream of packet payloads includes data comprising a second subset of the content to be transferred to the second plurality of clients;

wherein the replication engine, for each packet payload in the first stream, generates a first plurality of packets that include the packet payload, each packet of the first plurality of packets corresponding to one of the first plurality of clients, and wherein, for each packet payload in the second stream, generates a second plurality of packets that include the packet payload, each packet of the second plurality of packets corresponding to one of the second plurality of clients.

44. An apparatus for serving content to multiple clients via a network, the network including a multicast network, the apparatus comprising:

a client manager coupled to the network that maintains independent sessions with each of a plurality of unicast clients;

a storage device that stores the content to be served;

an encoding system coupled to the storage device that generates a stream of packet payloads, each packet payload of the stream of packet payloads including a random or pseudorandom set of output symbols encoded with data comprising the content to be served to the plurality of unicast clients and a plurality of multicast clients, wherein each packet payload in at least a subset of the stream of packet payloads includes a different set of data, wherein at least a first subset of the packet payloads are included in multicast packets;

a multicast transmitter coupled with the encoding generator and the network that receives the multicast packets from the encoding system and transmits the multicast packets to a plurality of multicast clients via the multicast network;

a replication engine coupled to the encoding system that receives at least a second subset of the packet payloads in the stream of packet payloads, and that, for each received packet payload, generates a plurality of unicast packets that include the received packet payload, each unicast packet of the plurality of unicast packets corresponding to one of the plurality of unicast clients;

a unicast transmitter coupled to the replicator engine that receives the unicast packets and transmits the packets to the corresponding clients via the network;

wherein each multicast packet or unicast packet transmitted at any particular time to some or all of the plurality of multicast clients or the plurality of unicast clients is independent of which multicast packet or unicast packet had been previously correctly received by various ones of the multicast clients or unicast clients, and wherein each of the plurality of multicast clients or unicast clients is capable of reconstructing the content after correctly receiving a number of different output symbols sufficient in quantity to reconstruct the data to a desired accuracy from those different output symbols.

45. The apparatus of claim 44 wherein the content to be served is received as a stream of data and stored on the storage device.

46. The apparatus of claim 44 wherein each packet payload in at least a second subset of the stream of packet payloads received by the replication engine is included in a multicast packet.

47. The apparatus of claim 46 wherein each packet payload in the stream of packet payloads generated by the encoding system is included in a multicast packet.

48. The apparatus of claim 46 wherein the replication engine receives multicast packets via the multicast transmitter.

49. The apparatus of claim 44 wherein each packet payload in the at least a second subset of the stream of packet payloads received by the replication engine is included in a unicast packet.

50. The apparatus of claim 44 wherein the encoding system is coupled with the replication engine via a bus.

51. The apparatus of claim 44 wherein the encoding system is coupled with the replication engine via a local area network.

52. The apparatus of claim 44 wherein the encoding system is coupled with the replication engine via the Internet.

53. The apparatus of claim 44 wherein the content comprises an ordered set of input symbols, wherein each packet payload of the stream of packet payloads includes at least one output symbol, wherein output symbols are generated from input symbols, and wherein a client can regenerated to a desired accuracy the ordered set of input symbols from the output symbols included in the set of packet payloads received by the client.

54. The apparatus of claim 53 wherein output symbols are generated from input symbols using a FEC code.

55. The apparatus of claim 53 wherein output symbols are generated from input symbols such that the ordered set of input symbols can be regenerated using any set of N number of the output symbols, wherein N is an integer greater than 1 and less than the number of possible output symbols.

56. A method of serving content to multiple clients via a network, the content represented by a plurality of input symbols, wherein the network includes a multicast network, the method comprising:

generating output symbols from the input symbols;

assembling output symbols into a stream of packets, wherein each packet in the stream of packets includes of at least one random or pseudorandom set of output symbols, wherein each packet includes a different set of the output symbols; and

transmitting, using multicasting, the stream of packets to a plurality of multicast clients via the multicast network, wherein each packet transmitted at any particular time to some or all of the plurality of clients is independent of which packet had been previously correctly received by various ones of the multicast clients;

wherein the number of multicast clients in the plurality of multicast clients can vary over time, and wherein a multicast client can regenerate the ordered set of input symbols to a desired accuracy from any N number of the output symbols randomly or pseudorandomly included in a set of packets received by the multicast client, wherein N is an integer greater than 1 and less than the number of possible output symbols.

57. The method of claim 56 further including receiving the content to be served as a stream of data.

58. The method of claim 56 wherein a multicast client can join and leave the multicast stream one or more times to receive the set of packets.

59. The method of claim 56 wherein each packet in the stream of packets is a multicast packet.

60. The method of claim 56 wherein the plurality of multicast clients includes a first plurality of multicast clients and a second plurality of multicast clients, wherein the number of multicast clients in the first plurality of multicast clients can vary over time and wherein the number of multicast clients in the second plurality of multicast clients can vary over time;

wherein assembling output symbols into a stream of packets includes assembling output symbols into a first stream of packets and a second stream of packets; and

wherein transmitting the stream of packets to a plurality of multicast clients includes transmitting the first stream of packets to the first plurality of multicast clients and transmitting the second stream of packets to the second plurality of multicast clients.

61. The method of claim 60 wherein at least one multicast client is in the first plurality of multicast clients and the second plurality of multicast clients.

62. The method of claim 61 wherein a multicast client in the first plurality of multicast clients and in the second plurality of multicast clients can regenerate the input symbols to a desired accuracy from any N number of the packets included in a random or pseudorandom set of packets in the first stream of packets and the second stream of packets received by the multicast client, wherein N is an integer greater than 1 and less than the number of possible output symbols.

63-64. -64. (canceled)

65. A server for serving content to multiple clients via a network including a multicast network, the server comprising:

a storage device that stores the content to be served, the content including input symbols;

an encoding generator coupled with the storage device that generates output symbols from of the input symbols;

a transmitter coupled with the encoding generator and with the network that assembles the output symbols into multicast packets, wherein each multicast packet includes a random or pseudorandom set of output symbols and transmits, using multicast, the multicast packets to a plurality of multicast clients via the network, and wherein each multicast packet transmitted at any particular time to some or all of the plurality of muticast clients is independent of which multicast packet had been previously correctly received by various ones of the multicast clients;

wherein the number of multicast clients in the plurality of multicast clients can vary over time, and wherein a multicast client can regenerate the input symbols to a desired accuracy from any N number of the output symbols included in a set of multicast packets received by the multicast client, wherein N is an integer greater than 1 and less than the number of possible output symbols.

66. The server of claim 65 wherein the content to be served is received as a stream of data and stored on the storage device.

67. A distributed apparatus for serving content to multiple clients via a network, the distributed apparatus comprising:

a plurality of replication systems, each replication system including;

a respective client manager coupled to the network that maintains independent sessions with each of a respective plurality of clients;

a respective buffer coupled to receive a respective stream of packet payloads, each packet payload of the respective stream of packet payloads including a random or pseudorandom set of output symbols encoded with data comprising the content to be transferred to the respective plurality of clients, wherein each packet payload in at least a subset of the respective stream of packet payloads includes a different set of data;

a respective replication engine coupled to a respective buffer that, for each packet payload, generates a plurality of packets that include the packet payload;

a respective transmitter coupled to the replication engine that receives the packets and transmits the packets to the corresponding clients via the network;

wherein each packet payload transmitted at any particular time to some or all of the plurality of clients is independent of which packet payload had been previously correctly received by various ones of the clients, and wherein each of the plurality of clients is capable of reconstructing the content after correctly receiving a number of different output symbols sufficient in quantity to reconstruct the data to a desired accuracy from those different output symbols.

68. The distributed apparatus of claim 67 wherein each respective stream of packet payloads is the same stream.

69. The distributed apparatus of claim 67 wherein at least some of the respective streams of packet payloads are different streams.

70. The distributed apparatus of claim 67 wherein at least one client is included in more than one of the respective pluralities of clients.

71. The distributed apparatus of claim 67 further including:

a plurality of storage devices that store the content to be served; and

a plurality of encoding systems coupled with the plurality of storage devices, wherein each encoding system generates a stream of packet payloads, each packet payload of the stream of packet payloads including data comprising the content to be served to the plurality of clients, wherein each packet payload in at least a subset of the stream of packet payloads includes a different set of data;

wherein the plurality of encoding systems are coupled with the respective buffers, wherein each respective buffer receives one or more of the streams of packet payloads generated by the plurality of encoding systems.

72. A server system for serving content to multiple clients via a network including a multicast network, the server system comprising:

a plurality of servers, each of the plurality of servers including;

a respective storage device that stores the content to be served, the content including input symbols;

a respective encoding generator coupled with the respective storage device that generates output symbols from the input symbols;

a respective transmitter coupled with the respective encoding generator and with the network that assembles the output symbols into multicast packets, wherein each multicast packet includes a a random or pseudorandom set of output symbols and transmits, using multicast, the multicast packets to a respective plurality of multicast clients via the network, wherein each multicast packet transmitted at any particular time to some or all of the plurality of multicast clients is independent of which multicast packet had been previously correctly received by various ones of the multicast clients;

wherein the number of multicast clients in the respective plurality of multicast clients can vary over time, and wherein a multicast client can regenerate the input symbols to a desired accuracy from any N number of the output symbols included in a set of multicast packets randomly or pseudorandomly received by the multicast client, wherein N is an integer greater than 1 and less than the number of possible output symbols.

73. The server system of claim 72 wherein at least one multicast client is included in more than one of the respective pluralities of multicast clients.

74. The server system of claim 73 wherein the set of multicast packets received by the multicast client are received from more than one of the plurality of the servers.

75. A method at a client of receiving content comprising an ordered set of input symbols via a network, the method comprising:

requesting a server via the network to transmit the content to the client;

receiving a stream of packets from the server via the network, wherein packets in the stream of packets comprise output symbols, the output symbols generated from the input symbols, wherein each packet in the stream of packets includes a random or pseudorandom set of the output symbols, wherein the number of possible output symbols is N, and wherein each packet received at any particular time to the client is independent of which packets had been previously correctly received by the client;

after randomly or pseudorandomly receiving an N1 number of the output symbols in packets received from the stream of packets, wherein N1 is a positive integer greater than 1 and less than N, regenerating the content to a desired accuracy with the received output symbols.

76. The method of claim 75 wherein regenerating the content includes regenerating a first subset of the content while receiving output symbols generated from input symbols comprising a second subset of the content.

77. The method of claim 76 further comprising playing out the first subset of the content while receiving output symbols generated from input symbols comprising the second subset of the content.

78. The method of claim 75 wherein the ordered set of input symbols comprises first input symbols and second input symbols;

wherein receiving a stream of packets from the server via the network includes receiving a first stream of packets and receiving a second stream of packets;

wherein packets in the first stream of packets comprise first output symbols, the first output symbols generated from the first input symbols, wherein each packet in the first stream of packets includes a random or pseudorandom set of the first output symbols, wherein the number of possible first output symbols is J;

wherein packets in the second stream of packets comprise second output symbols, the second output symbols generated from the second input symbols, wherein each packet in the second stream of packets includes a random or pseudorandom set of the second output symbols, wherein the number of possible second output symbols is K;

wherein regenerating the content to a desired accuracy includes;

after receiving a J1 number of the first output symbols in packets randomly or pseudorandomly received from the first stream of packets, wherein J1 is a positive integer greater than 1 and less than J, regenerating the first input symbols to a desired accuracy with the received first output symbols

after receiving a K1 number of the output symbols in packets received randomly or pseudorandomly from the second stream of packets, wherein K1 is a positive integer greater than 1 and less than K, regenerating the second input symbols to a desired accuracy with the received second output symbols.

79. The method of claim 78 wherein the first input symbols comprise a first subset of the content and wherein the second input symbols comprise a second subset of the content.

80. The method of claim 78 wherein the first input symbols are the same as the second input symbols.

81. The method of claim 75 further comprising:

detecting whether each packet in the stream of packets is received;

transmitting a packet acknowledgment message to the server for at least some of the packets received by the client;

if a packet in the stream of packets is not received, receiving a replacement packet from the server, wherein the replacement packet includes different output symbols than the output symbols included in the packet that was not received.

82. The method of claim 81 wherein the package acknowledgment messages are TCP package acknowledgment messages, wherein the packet not received and the replacement packet are TCP packets;

and

wherein the sequence number of the replacement packet is the sequence number of the packet not received.

83. The method of claim 75 wherein requesting the server to transfer the content includes sending a first join message to the server, the method further comprising ending reception of the packets at a time subsequent to sending the first join message.

84. The method of claim 83 wherein the first join message includes a time value that indicates to the server when to stop transmitting the first packets to the client.

85. The method of claim 84 wherein the time value is a length of time.

86. The method of claim 84 wherein the time value is an absolute time.

87. A method at a client of receiving content comprising an ordered set of input symbols via a multicast network, the method comprising:

joining a multicast session;

receiving a stream of packets via the multicast network, wherein packets in the stream of packets comprise output symbols, the output symbols generated from the input symbols, wherein each packet in the stream of packets includes a random or pseudorandom set of the output symbols, wherein the number of possible output symbols is N, and wherein each packet received by the client at any particular time is independent of which packets had been previously correctly received by the client;

after randomly or pseudorandomly receiving an N1 number of the output symbols in packets received from the stream of packets, wherein N1 is a positive integer greater than 1 and less than N, regenerating the content to a desired accuracy with the received output symbols.

88. The method of claim 87 wherein regenerating the content includes regenerating a first subset of the content while receiving output symbols generated from input symbols comprising a second subset of the content.

89. The method of claim 88 further comprising playing out the first subset of the content while receiving output symbols generated from input symbols comprising the second subset of the content.

90. The method of claim 87 wherein the ordered set of input symbols comprises first input symbols and second input symbols;

wherein receiving a stream of packets via the multicast network includes receiving a first stream of packets and receiving a second stream of packets;

wherein packets in the first stream of packets comprise first output symbols, the first output symbols generated from the first input symbols, wherein each packet in the first stream of packets includes a random or pseudorandom set of the first output symbols, wherein the number of possible first output symbols is J;

wherein packets in the second stream of packets comprise second output symbols, the second output symbols generated from the second input symbols, wherein each packet in the second stream of packets includes a random or pseudorandom set of the second output symbols, wherein the number of possible second output symbols is K;

wherein regenerating the content to a desired accuracy includes;

after receiving J1 first output symbols in packets received randomly or pseudorandomly from the first stream of packets, wherein J1 is a positive integer greater than 1 and less than J, regenerating the first input symbols to a desired accuracy with the received first output symbols

after receiving K1 output symbols in packets received randomly or pseudorandomly from the second stream of packets, wherein K1 is a positive integer greater than 1 and less than K, regenerating the second input symbols to a desired accuracy with the received second output symbols.

91. The method of claim 90 wherein the first input symbols comprise a first subset of the content and wherein the second input symbols comprise a second subset of the content.

92. The method of claim 90 wherein the first input symbols are the same as the second input symbols.

93. A method of receiving content from a server, the method comprising:

requesting to join a multicast session, wherein the multicast session includes a stream of multicast packets served by a server, the multicast packets in the stream of multicast packets including a random or pseudorandom set of output symbols encoded with data comprising the content; and

if the client does not receive multicast packets in the stream of multicast packets, requesting the server to send a stream of unicast packets, the unicast packets in the stream of unicast packets including another random or pseudorandom set of output symbols encoded with data comprising the content, wherein each multicast packet received by the client at any particular time is independent of which multicast packets had been previously correctly received by the client and wherein each of the plurality of clients is capable of reconstructing the content after correctly receiving a number of different output symbols sufficient in quantity to reconstruct the data to a desired accuracy from those different output symbols.

94. The method of claim 93 wherein requesting a server to send unicast packets includes:

requesting the server to send UDP unicast packets; and

if the client does not receive the UDP unicast packets, requesting the server to send TCP packets.