Electrical computers and digital processing systems: multicomput – Computer-to-computer protocol implementing – Computer-to-computer data streaming
Reexamination Certificate
2000-01-06
2003-12-16
Caldwell, Andrew (Department: 2157)
Electrical computers and digital processing systems: multicomput
Computer-to-computer protocol implementing
Computer-to-computer data streaming
C709S205000, C725S098000
Reexamination Certificate
active
06665726
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Technical Field
The present invention relates generally to digital signal transmission over a computer network and, in particular, to a method and system for streaming content over the Internet in a fault tolerant manner.
2. Description of the Related Art
Most Internet users do not have fast enough access to the Internet to download large multimedia files quickly. Streaming is a technique for delivering web-based video, audio and multimedia files so that these files can be processed as a steady and continuous stream at the requesting client, typically using a browser plug-in, such as Microsoft NetPlayer, Apple QuickTime, Real Networks RealSystem G2, or the like. Streaming video, for example, is an online video distribution mechanism that provides audio and video to Internet users, without the users having to wait while content completely downloads to their hard drives. Through caching, content is played as it is received, and buffering mechanisms ensure that content is played smoothly. Theoretically, streaming video plays to the end user, or viewer, as an immediate and ongoing broadcast.
From a network perspective, traditional approaches to streaming Internet content involve transmitting a streaming signal from a source to a device known as a splitter (or repeater, reflector or mirror), which, in turn, replicates the source signal into multiple signals. Each of the multiple signals is the same, and each is sent on to a different destination. By cascading splitters in a tree-like fashion, a single source stream can be replicated into thousands or more identical copies. In this manner, a large number of viewers on the Internet can receive the same streaming signal simultaneously.
A critical problem with existing streaming methods of this type is that they are not fault tolerant.
FIG. 1
illustrates why this is the case. In this example, a source signal (A) is sent to a splitter (B), which then sends copies of the signal to ten splitters (C
1
, . . . , C
10
). Each of the second level splitters then sends a copy of the signal to five end customers (D
1
, . . . D
50
). Thus, for example, splitter C
1
sends a copy to end users D
1
-D
5
, splitter C
2
sends a copy to end users D
6
-D
10
, and so forth. If communications at a given splitter fail, however, certain users are unable to receive the original signal. In the network of
FIG. 1
, this would be the case with respect to users D
6
-D
10
if C
2
fails. To overcome this problem, it is also known in the art to enable end users to detect they are no longer receiving the streaming signal and to enable such users to attempt to contact an alternative splitter (e.g., C
3
) in an effort to get another copy of the signal. Such approaches, however, can result in an interruption of the signal and are expensive to implement.
Thus, there remains a need in the art to provide improved streaming techniques that are fault tolerant. The present invention solves this important problem.
BRIEF SUMMARY OF THE INVENTION
The present invention provides a replication process to provide fault tolerance for a streaming signal in a computer network. In one embodiment, the original or source signal is sent to several splitters which, in turn, each make copies of the signal and send the copies into a second layer of devices, which are referred to as “concentrators.” A given concentrator receives as input one or more copies of the source signal. In a preferred embodiment, a given concentrator receives two copies of the source signal from at least two different splitters. The concentrators process the incoming streaming signal copies, for example, by merging them into a single or composite copy of the original source signal according to a given processing algorithm. Thus, preferably a given concentrator receives streams from multiple sources, removes duplicate packets, and then outputs a single stream. The output of a given concentrator may then be fed into a splitter, with the process then being repeated if desired to make an arbitrary large number of copies of the signal. At the end of the replication process, the output of a splitter or a concentrator is fed directly or indirectly to an end user. The replication process is fault-tolerant, and thus the end user's signal is not interrupted regardless of signal or equipment problems within the distribution mechanism.
One type of processing algorithm that is implemented at a concentrator simply transmits the first copy of each packet in the signal stream. Copies of packets that have already been transmitted are simply discarded. This algorithm may be implemented by maintaining a data array f(i) that has a first value (e.g., “1”) if packet i in the stream has been forwarded and f(i) that has a second value (e.g., “0”) otherwise. When a copy of packet i is received from one of the incoming streams, it is forwarded if and only if f(i) equals the second value. This technique is advantageous because a complete stream can be reconstructed from two or more partial streams. Thus, as long as the incoming copies of the stream collectively contain all the packets of the original stream, the concentrator produces a copy of the original stream.
Another type of processing algorithm that may be implemented at a concentrator uses a buffering technique. In this approach, a buffer of a given size is kept for each input stream to create an n-dimensional array, where n is the number of input streams. At a given cycle rate, the concentrator transmits a smallest index packet (namely, a packet that is earliest in the stream sequence) contained in any of the stream buffers. As each packet is transmitted, the data in the array is updated so that future copies of the same packet can be discarded. This protocol enables the concentrator to reorder the packets in a stream so that they are output in a correct order.
One or more concentrators as described above enable fault tolerant media streaming over a computer network such as the Internet, an intranet, a virtual private network, or the like.
The foregoing has outlined some of the more pertinent objects and features of the present invention. These objects should be construed to be merely illustrative of some of the more prominent features and applications of the invention. Many other beneficial results can be obtained by applying the disclosed invention in a different manner or modifying the invention as will be described. Accordingly, other objects and a fuller understanding of the invention may be had by referring to the following Detailed Description of the Preferred Embodiment.
REFERENCES:
patent: 5623483 (1997-04-01), Agrawal et al.
patent: 5627822 (1997-05-01), Edmaier et al.
patent: 5627825 (1997-05-01), Barraclough et al.
patent: 5778187 (1998-07-01), Monteiro et al.
patent: 5805785 (1998-09-01), Dias et al.
patent: 5854898 (1998-12-01), Riddle
patent: 5928331 (1999-07-01), Bushmitch
patent: 5946294 (1999-08-01), Stein
patent: 5996001 (1999-11-01), Quarles et al.
patent: 6032189 (2000-02-01), Jinzenji et al.
patent: 6195680 (2001-02-01), Goldszmidt et al.
patent: 6263371 (2001-07-01), Geagan et al.
patent: 6339785 (2002-01-01), Feigenbaum
patent: 6415323 (2002-07-01), McCanne et al.
patent: 6418142 (2002-07-01), Wolf
patent: 6496477 (2002-12-01), Perkins et al.
patent: 6505240 (2003-01-01), Blumenau
patent: 195 09 602 (1995-03-01), None
patent: 0 566 241 (1993-03-01), None
CacheFlow Internet Caching Appliances: Next Generation Proxy Server Solution, CacheFlow, Inc., pp. 1-12, Oct. 1999.*
Streaming Media Optimiation with CacheFlow Internet Caching Appliances, CacheFlow, Inc., pp. 1-12, Oct. 1999.*
RealProxy G2 Administration Guide, Beta One, RealNetworks, Inc., ns3.yar.ru/doc/realproxyg2b1.pdf, pp. 1-124, 1999.*
Yan, Xifeng, Course Notes for CSE-646, Content Distribution Network, www.ecsl.cssunysb.edu/~chiueh/cse646/cn8/cn8.html, pp. 1-9, Nov. 2000.
Leighton F. Thomson
Lewin Daniel M.
Maggs Bruce
Shaw David
Akamai Technologies, Inc.
Caldwell Andrew
Judson David H.
LandOfFree
Method and system for fault tolerant media streaming over... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and system for fault tolerant media streaming over..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for fault tolerant media streaming over... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3103766