Method of listener transmitted broadcasting

• US 6,697,365 B1
• Filed: 06/12/2000
• Issued: 02/24/2004
• Est. Priority Date: 06/10/1999
• Status: Expired due to Fees

• Current Assignee: Charles Hayes Messenger
• Original Assignee: Charles Hayes Messenger
• Inventors: Messenger, Charles Hayes
• Primary Examiner(s): Pezzlo, John
• Application Number:
  US09/591,727
• Time in Patent Office: 1,352 Days
• Field of Search: 370/392, 370/400, 370/432, 370/401, 370/216, 370/408, 370/390, 370/473, 370/252, 370/254, 709/252, 709/238, 709/205
• US Class Current: 370/390
• CPC Class Codes: H04L 12/1854 with non-centralised forwarding system, e.g. chaincast

Abstract

The bandwidth of a group of Internet users, called listeners, is pooled, and that bandwidth is employed to broadcast a data stream, substantially concurrently, to those listeners. A broadcast manager coordinates the connections between the originator of the data stream and the listeners. The originator divides the data stream into a number of channels. Each channel is transmitted over a tree of interconnected listeners. A given listener in a given tree receives that channel from its parent in that tree, and retransmits the channel as it is received to its children in that tree. Each listener is present once in each tree, so the listener receives each channel once. Listeners combine the incoming channels to reproduce the originator'"'"'s data stream. The result is that almost the entire transmission bandwidth required for the broadcast is provided by the listeners. In some embodiments, a given listener is required to transmit no more data than it receives. One or more channels may be redundant, providing some ability to bypass non-performing listeners. Feedback statistics are efficiently collected in the reverse direction over the same connections used for transmitting the channels. An application for a file server is described. A distributed broadcast manager is described.

Claims

1. A method of managing a broadcast over a global packet-switched network of a data stream having a bandwidth, the data stream represented as a plurality of data packets, the data stream originating from at least one originator, and received by a plurality of listeners, wherein each listener converts the data stream into a human perceivable form, and at least one listener is capable of deriving a packet from at least one received packet, and sending a derived packet using a unicast protocol over the global packet-switched network to at least one other listener;

comprising the steps of;

a) maintaining a pattern of interconnections between a group of listeners, wherein the pattern is maintained so that at least one listener does not receive any packets directly from the originator;

b) establishing a flow of data from an originator to the group of listeners by the steps of;

i) instructing the originator to send packets to at least one selected listener;

ii) instructing at least one selected listener to derive packets from at least one received packet and to send derived packets to at least one other listener in the group wherein each listener converts the data stream into a human perceivable form; and

iii) repeating step ii until listeners are instructed to derive and send packets so that packets sufficient to reconstruct the data stream will be sent to all listeners in accordance with the pattern;

so that each listener receives the broadcast substantially concurrently as it is transmitted by the originator.

2. The method of claim 1, further comprising the step, after step (b), of revising at least one pattern in response to a change in the group of listeners, and repeating the method from step (b).

3. The method of claim 2, in which the change is a new listener joining the group.

4. The method of claim 2, in which the change is a listener leaving the group.

5. The method of claim 1, in which, in step (b)(ii), at least one of the selected listeners which does not receive packets from the originator is instructed to send to a plurality of other listeners.

6. The method of claim 5, in which at least one pattern of interconnections is in the form of a tree having a root node and a plurality of nodes, with each node in the tree being a listener, and with the originator connected to the root node of the tree.

7. The method of claim 6, in which the tree is substantially balanced, such that the maximum number of listeners through which a packet will pass is substantially minimized.

8. The method of claim 1, further comprising the steps of:

a) at least one listener sending a special packet, containing statistical information, to a listener from which the listener receives packets in the data stream;

b) a selected listener combining the statistical information in received special packets from at least one listener with the selected listener'"'"'s own statistical information, to create combined statistical information for the selected listener and other listeners;

c) the selected listener sending a special packet containing the combined statistical information to a listener from which the selected listener receives packets in the data stream; and

d) repeating steps b) and c), until the originator receives a special packet containing the combined statistical information from a plurality of listeners.

9. The method of claim 8, further comprising the step of computing a network latency from data in the special packet.

10. The method of claim 1, in which:

a) in step (a), a plurality of patterns of interconnections are maintained, each pattern interconnecting the listeners in the group, and at least one listener being connected to a different set of other listeners in each pattern, and the originator being connected to at least one listener in each pattern;

b) the originator produces a plurality of channels, each channel comprising a stream of packets derived from the data stream, each channel having a bandwidth, one channel corresponding to each pattern; and

c) for each channel, the originator transmits the packets for that channel to at least one selected listener according to the pattern corresponding to that channel, and the packets in each channel are sent through the pattern;

so that each of the listeners receives packets from two or more channels, sufficient to reconstruct the data stream.

11. The method of claim 1, in which the data stream represents content selected from a group comprising audio programming, video programming, multimedia programming, and advertising information.

12. A method of managing a broadcast over a global packet-switched network of a data stream having a bandwidth, the data stream represented as a plurality of data packets, the data stream originating from at least one originator, and received by a plurality of listeners, and at least one listener is capable of deriving a packet from at least one received packet, and sending a derived packet using a unicast protocol over the global packet-switched network to at least one other listener;

comprising the steps of;

a) maintaining a plurality of patterns of interconnections between a group of listeners, each pattern interconnecting the listeners in the group, and at least one listener being connected to a different set of other listeners in each pattern, and at least one listener having no connections to the originator, and the originator being connected to at least one listener in each pattern;

b) instructing at least one originator to produce a plurality of channels, each channel comprising a stream of packets derived from the data stream, each channel having a bandwidth less than the bandwidth of the data stream;

c) establishing a flow of data from an originator to the group of listeners by the steps of;

i) instructing the originator to send packets for a channel to at least one selected listener, according to a pattern;

ii) instructing at least one selected listener to derive a channel comprising a stream of packets derived from received packets, the bandwidth of the channel being less than the bandwidth of the data stream, and to send packets for the derived channel to at least one other listener in the group, according to the pattern wherein each listener converts the data stream into a human perceivable form; and

iii) repeating step ii until listeners are instructed to derive and send packets so that packets sufficient to reconstruct the data stream will be sent to all listeners;

wherein at least one listener not connected to any originator receives from no other single listener a set of channels whose combined bandwidth is equal to or greater than the bandwidth of the data stream;

so that each listener receives packets from two or more channels, sufficient to reconstruct the data stream.

13. The method of claim 12, further comprising the step, after step (c), of revising at least one pattern in response to a change in the group of listeners, and repeating the method from step (c).

14. The method of claim 13, in which the change is a new listener joining the group.

15. The method of claim 13, in which the change is a listener leaving the group.

16. The method of claim 12, in which each channel receives a substantially equal portion of the data stream.

17. The method of claim 16, in which each pattern is in the form of a tree having a root node and a plurality of nodes, with each node in the tree being a listener, and with the originator connected to the root node of the tree, so that a majority of the plurality of listeners is a leaf node in at least one tree.

18. The method of claim 17, in which each tree is substantially balanced, such that the maximum number of listeners through which a packet will pass is substantially minimized.

19. The method of claim 12, in which at least one of the listeners can recreate missing packets in a channel by using packets from at least one other channel.

20. The method of claim 12, in which the steps are performed by a broadcast manager separate from the originator and listeners, and the steps are performed by the broadcast manager sending commands over the global packet-switched network to the originator and the listeners.

21. The method of claim 12, in which at least one of the listeners is instructed to send packets to at least one originator, so that the originator receives packets sufficient to reconstruct the data stream.

22. The method of claim 12, further comprising the steps of:

a) at least one listener sending a special packet, containing statistical information, to a listener from which the listener receives packets in the data stream;

b) a selected listener combining the statistical information in received special packets from at least one listener with the selected listener'"'"'s own statistical information, to create combined statistical information for the selected listener and other listeners;

c) the selected listener sending a special packet containing the combined statistical information to a listener from which the selected listener receives packets in the data stream; and

d) repeating steps b) and c), until the originator receives a special packet containing the combined statistical information from a plurality of listeners.

23. The method of claim 22, further comprising the step of computing a network latency from data in the special packet.

24. The method of claim 12, in which the data stream represents content selected from a group comprising audio programming, video programming, multimedia programming, and advertising information.

25. The method of claim 12, in which the data stream represents a data file, and the data file is broadcast a plurality of times, so that listeners may make local copies of the file.

26. A method for a first listener to receive a data stream being broadcast over a global packet switched network, the data stream being represented as a plurality of data packets, the data stream originating from at least one originator, and received by a plurality of listeners other than the first listener, at least one of which retransmits part or all of the data stream over the packet switched network to another listener, comprising the steps of:

a) submitting to a broadcast manager a request to receive a data stream;

b) forming connections with at least one other listener in response to at least one instruction from the broadcast manager;

c) receiving a channel consisting of a stream of packets over each of one or more connections formed in step (b); and

d) reconstructing the data stream from the channels, and converting it into a human perceivable form;

so that the first listener receives the broadcast from other listeners, as received by them from other listeners, and ultimately from the originator, substantially concurrently as the originator transmits the data stream.

27. The method of claim 26, further comprising the steps of:

e) forming connections with at least one other listener in response to at least one instruction from the broadcast manager; and

f) transmitting each of one or more first channels, each first channel consisting of a stream of packets derived from at least one channel received at step (c), to at least one listener connected with at step (e);

so that the first listener participates in transmitting the broadcast to at least one other listener.

28. The method of claim 27, further comprising the step of notifying the broadcast manager of a failure to receive packets expected at step (c).

29. The method of claim 27, further comprising the steps of:

h) notifying the broadcast manager of an intention to leave the broadcast;

i) receiving at least one connection instruction from the broadcast manager;

j) sending at least one connection instruction received at step (i) to one or more other listeners, those listeners in turn either sending those instructions to still other listeners, or forming new connections to one or more listeners based on those instructions; and

k) closing connections to all listeners connected to at steps (b) and (e);

so that the listeners connected to the first listener form new connections over which they continue to receive the data stream, other than from the first listener, and the first listener stops receiving channels from any other listeners.

30. The method of claim 27, wherein at step (e), the first listener forms connections to a plurality of other listeners in response to at least one instruction from the broadcast manager.

31. The method of claim 26, wherein at step (b), the first listener forms connections to a plurality of other listeners in response to at least one instruction from the broadcast manager, and at step (c), the first listener receives a channel over each of a plurality of connections formed.

32. The method of claim 26, wherein at step (c), no single listener provides sufficient packets to reconstruct the data stream.

33. The method of claim 32, wherein the data stream has a bandwidth, and each channel has a bandwidth, and at step (c), the bandwidth of each channel is less than the bandwidth of the data stream, and the sum of the bandwidths of channels being sent by each listener is less than the bandwidth of the data stream.

34. The method of claim 27, further comprising the steps of:

g) reconstructing at least one missing packet of a channel from at least one packet received on at least one other channel; and

h) transmitting at least one reconstructed packet over at least one connection formed at step (e);

so that a channel whose reception is interrupted is reconstructed from other channels, so that the reception and retransmission of the data stream is not interrupted.

35. The method of claim 32, wherein the bandwidth of each channel is substantially equal.

36. The method of claim 26, further comprising the steps of:

e) forming a connection with an originator in response to an instruction from the broadcast manager; and

f) transmitting each of one or more first channels, each first channel consisting of a stream of packets derived from at least one channel received at step (c), to the originator connected with at step (e);

so that the listener participates in transmitting the broadcast back to the originator, so the originator can monitor the broadcast.

37. The method of claim 27, further comprising the steps of:

g) receiving at least one special packet containing statistical information over at least one connection formed at step (e);

h) combining the statistical information received in at least one special packet received at step

(g) with the first listener'"'"'s own statistical information, to create combined statistical information; and

i) sending a special packet containing the combined statistical information over at least one connection formed at step (b);

so that combined statistical information is propagated, and the originator eventually receives combined statistical information from a plurality of listeners.

38. The method of claim 37, wherein the statistical information is derived from a delay between transmission of a portion of the data stream by the originator, to receipt of that portion by the first listener, so that the originator can monitor the latency of the broadcast.

39. The method of claim 26, in which the data stream represents content selected from a group comprising audio programming, video programming, multimedia programming, and advertising information.

40. A method for an originator to broadcast a data stream over a global packet switched network to a plurality of listeners, the data stream being represented as a plurality of data packets, wherein at least one listener is capable of sending a packet over the global packet-switched network to at least one other listener;

comprising the steps of;

a) submitting to a broadcast manager a request to broadcast a data stream;

b) establishing a flow of data to the group of listeners by the steps of;

i) forming connections with two or more listeners in response to at least one instruction from the broadcast manager;

ii) formatting a derivative of the data stream into a stream of packets;

iii) dividing the packets between a plurality of channels, so that the bandwidth of each channel is less than the bandwidth of the data stream; and

iv) transmitting a channel to each of two or more listeners with which connections were formed in step (b)(i), such that no more than one channel is sent to each listener;

wherein at least one listener to which a channel was transmitted in step (b)(iv), sends at least one channel derived from at least one received channel to at least one other listener, until at least one listener receives packets sufficient to reconstruct the data stream and converts the data stream into a human perceivable form.

41. The method of claim 40, wherein at step (b)(i), connections are formed to two or more listeners, and at step (b)(iv), channels are transmitted to two or more listeners with which connections were formed at step (b)(i).

42. The method of claim 41, wherein at step (b)(iii), at least one channel can be derived from two or more other channels, so that redundancy is added to the transmission to provide a degree of error tolerance.

43. The method of claim 42, wherein the bandwidth of each channel is substantially equal.

44. The method of claim 40, wherein the data stream represents a data file, and the data file is broadcast a plurality of times.