1. Field of the Invention
The present invention pertains to the field of digital data communications. More particularly, it pertains to methods of transmitting data to multiple recipients over a global computer network.
2. Description of the Prior Art
As the Internet has become ubiquitous, broadcasting over the Internet has become ever more important. Broadcasting involves having a broadcast originator send a data stream (typically representing audio and/or video programming), substantially concurrently, to a large number of listeners. On the Internet, the typical listener is a user with a limited bandwidth connection to her Internet Service Provider, which in turn has a high bandwidth connection to the rest of the Internet. Typically, users are free to receive transmissions from, and send transmissions to, any other user or server on the Internet. In order to broadcast over the Internet, one of two general methods is currently employed. The first method makes use of standard unicast protocols which are universally implemented on the Internet. The second method makes use of a multicast protocol, implemented only on a known set of servers.
The first method, employing only unicast protocols, is illustrated in FIG. 1. Broadcast originator 100 sends the data stream which is to be broadcast to Unicast Server 104 through unicast connection 102a, in a series of unicast IP protocol packets. These packets are replicated on the Unicast Server, and retransmitted as unicast IP packets over individual unicast connections 102b to each listener 108. The main advantage of this method is flexibility. Because standard unicast IP protocols are used, there is no need for special software to run on the servers and routers which transmit data across the Internet. All a broadcaster needs is a Unicast Server with enough transmission bandwidth to support the desired number of listeners. The main drawbacks are cost, because transmission bandwidth is expensive, and scalability, because there may be practical limits to the obtainable transmission bandwidth.
The second method, employing a multicast protocol, is illustrated in FIG. 2. Broadcast originator 100 sends the broadcast data stream to one of a known set of linked Multicast Servers 110 over multicast connection 112a. A multicast connection consists of a series of packets using a multicast protocol. Unlike a unicast packet, which is addressed to a single recipient, a multicast packet is addressed to multiple recipients. When a Multicast Server processes a multicast packet, it may replicate and forward it to one or more other Multicast Servers over multicast connections 112b. Packets are also forwarded directly to listeners 108 over multicast or unicast connections 113. Ideally, packet replication takes place at the server which is closest to a given listener, thus minimizing bandwidth usage. An example of a non-proprietary, non-commercial implementation of multicasting is described by K. Savetz et al. in MBONE Multicasting Tomorrow""s Internet (IDG Books WorldWide, Inc., 1996). An example of a proprietary commercial implementation is provided by the Real Broadcast Network (http://www.realnetworks.com/rbn). The main advantage of IP multicasting is efficient utilization of bandwidth. The main disadvantage is that special software must be run on the servers and routers across which the data is transmitted. There is currently no IP multicasting protocol which is universally implemented on the Internet. As a consequence, non-commercial implementations suffer from a lack of availability. Commercial implementations are costly, and require a burdensome amount of coordination with the commercial provider, thus minimizing flexibility.
There are several programs which are used to disseminate files across the Internet using unicast connections, without the need to host the files on a central server. Examples include Napster (http://www.napster.com), Gnutella (http://gnutella.wego.com), and The Free Network Project (http://freenet.sourceforge.net). Using these programs, a directory is maintained showing which users have which files. When a first user wants to download a specific file, she references the directory, and selects a second user currently hosting the file. The second user transmits the file upon request over a unicast connection to the first user. Once the file has been received, the first user is then generally registered in the directory as having that file. In this manner, files are disseminated between users. While these methods are suitable for distributing files, they are not applicable to disseminating a continuous broadcast.
There is a need for an Internet broadcasting method which benefits from the flexibility and universality of a unicasting system, while avoiding the cost and scalability problems associated with conventional unicast broadcasting methods based on centralized servers; a method which benefits from the advantage of a multicasting system in terms of minimizing the broadcaster""s transmission bandwidth requirements, while avoiding the cost and inflexibility of commercial multicasting methods, and the lack of availability of non-commercial multicasting methods. Such a method would result in a tremendous cost savings to broadcasters, offering them unprecedented freedom of action.
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.
The phrase xe2x80x9csubstantially concurrentlyxe2x80x9d is used with the understanding that there is some delay inherent to each transmission and retransmission step, so that Listeners do not receive the broadcast exactly simultaneously as it is transmitted by an Originator.