- Determine if there is a device behind a Symmetric NAT, if there is a one, chose that first;
- If it is not possible to select a one behind such a Symmetric NAT first, the next candidates would be those behind a Port-restricted NAT.
- Otherwise, devices behind a Full-cone or restricted-cone peer will be selected.

In operation, to avoid overusing or repeatedly designating those behind the Symmetric and port-restricted NATs, the sever is also loaded with a balancing module that facilitates to balance the allocation by making sure that same device is not designated to be a streaming or supplying device too much more often than it should be on average.

Referring now toFIG. 4, there shows, according to one embodiment of the present invention, a flowchart orprocess400 of managing communication between two devices, each being behind a NAT. To facilitate the understanding of the present invention, theprocess400 is presented for peer-to-peer communication between device A and B as shown inFIG. 1. Accordingly,FIG. 4 may be understood in conjunction withFIG. 1. It can be appreciated that the description herein forFIG. 4 may be equally applicable to peer-to-peer communication between any two computing devices.

At402, a computing device, referred herein as a server, updates a database that keeps various parameters, characteristics, surrounding conditions and status of each of the devices registered with the server. There may be many ways to keep the database updated. For example, a device, newly installed or recently put back online, can initiate a discovery process by sending a probing message to a server. Alternatively, the server may send to a device a message requesting certain parameters regarding the device to be updated. According to one embodiment, a STUN protocol (allowing applications to discover the presence and a type of NAT) is used.

The server awaits a request from any one of the devices in service at404. If no request is received or a predefined time period is out, theprocess400 goes back to402 to keep the database updated. It is now assumed that the request form one of the devices is received. According to one embodiment, the request is received from a device that has just been placed an order for a program (e.g., a large collection of data, a movie, an event broadcast). Because the device has none or only some of the data pertaining to the program, the device needs other selected devices to supply all of the data or the remaining part of the data. Accordingly, the ordering device initiates the request to the server.

Upon receiving the request, assuming the device has been authenticated and the user thereof has been authorized, the server is configured to look up at406 in the database to select a set of available candidates. Among the criteria that a candidate device must satisfy is the requirement that the candidate must have some or all of the needed data, and the requirement that any NAT that the candidate device is behind is compatible with the NAT associated with the ordering device. At408, among the selected candidates, a balancing measurement takes place to make sure that a finalist should not be the one that has been selected more often than others and in good condition to supply the needed data to the ordering device.

At410, it is assumed that the server has designated a (supplying) device to supply the needed data, a message or an acknowledgement to the request is sent to the supplying device or the ordering device. Depending on implementation, the ordering device may initiate a request to the supplying device in accordance with the message from the server or the supplying device starts to upload the needed data to the ordering device.

In one embodiment, at412, a special netfilter is used to convert the data conforming to one protocol in the supplying device to a data format conforming to another protocol to facilitate the data transmission through the respective NATs. Theprocess400 then goes to402 to keep updating the database.

It should be noted that theprocess400 is applicable to cases where the ordering device requires more than one supplying devices to supply the needed data. Further it can be appreciated by those skilled in the art that theprocess400 is applicable to synchronize more than one supplying devices to supply the needed data to the ordering device at similar time.

To further understand the present invention,FIG. 5A shows an exemplary configuration of a distributednetwork system500 in which the present invention may be practiced. Aserver502, presumably managed and/or populated by a service provider, is configured to handle the delivery of video (or multimedia) services to users via local machines or boxes506-1,506-2, . . .506-n. Different from the prior art system that delivers video data to a subscriber upon receiving a request therefrom, theserver502 is not responsible for delivering the content in response to a request from a user, and instead is configured to provide source information as to where and how to retrieve at least some of the content from other boxes. In other words, the prior art system requires at least a media storage device to provide the content when any of the client machines is being serviced, while theserver502 does not need necessarily a media storage device to provide the content. Instead, some of the boxes506-1,506-2, . . .506-n are respectively configured to supply part or all of the content to each other.

According to one embodiment, when fulfilling a request from a local machine or a box506-1 (e.g., corresponding to node A ofFIG. 2), communication between the server502 (e.g., corresponding to the server208 ofFIG. 2) and the box506-1 over the network paths508-1 and510 may be limited to small-scale requests and responses (e.g., of small size and very short). A server response to a request from a box may include source information (e.g., identifiers), authorization information and security information. Using the response from theserver502, the box506-1 may be activated to begin playback of a title. Data representing the title may be distributed in other boxes. The data, as will be shown below, is segmented into a number of segments, each is distributed to some boxes in services. Substantially at the same time, the box506-1 may initiate one or more requests to other boxes (e.g.,506-2 and506-n, corresponding respectively to nodes B and C) in accordance with the source identifiers to request the distributed segments (e.g.,507-2 and507-n). Assuming proper authorization, the requesting box506-1 receives the distributed segments concurrently from the other boxes according to theprocess500 ofFIG. 5

The contents available in a library being offered in any of the boxes506-1,506-2, . . .506-n are originally provided by one or more content providers. Examples of the content providers include satellite receivers, television relay stations, analog or digital broadcasting station, movie studios and Internet sites. Depending on implementation, the contents may be initially received or originated in theserver502. Instead of maintaining and managing the content in a large storage device, theserver502 is configured to distribute the content or files to a plurality of local machines registered with theserver502. The boxes506-1,506-2, . . .506-n shown inFIG. 5A are examples of local machines in service. Unless there is a need for a backup copy, theserver502 at any time has no need to keep a copy of the content. On the other hand, unless there is a special need to keep a complete copy of an extremely high-demand title in a box, none of the boxes in service has a complete copy of a title until an order is placed. Consequently, with embedded security in the distributed objects, one feature in the present invention may alleviate the concern of electronic piracy and widespread distribution (e.g., by hacking or illegal duplication).

For convenience, it is assumed herein that data or a file pertaining to a title is played back when the title is selected and ordered by a user. When an order for a title is placed, a corresponding file must be available for playback. One of the features in the present invention is that a file, or at least a portion thereof, regardless of its size, can be accessed instantaneously, thereby realizing instantaneous VOD. According to one embodiment, where a file is 840 Mbytes on average and a box includes a storage capacity of 300 Gbytes, a system may offer a large library of titles (e.g., 5000) for access at any time instantly. In the prior art, if the files for the titles must be stored in advance to offer instantaneous playback, the local storage of a box would have to have a capacity of 4,000 Gbytes, consequently, rendering instantaneous VOD economically impractical.

According to one aspect of the present invention, only a beginning portion (referred to as a “header”) and possibly one or more tail segments of a file are locally cached in a box. Such locally cached segments are referred to as residing objects or segments, while segments not residing locally are referred to as distributed objects or segments. When a title is selected, the header of the corresponding file is instantly played back. During the time the header is being played, the distributed segments corresponding to the title are retrieved simultaneously from other boxes. When the header is finished, the received parts of the distributed segments being streamed in from other boxes is combined with residing segments for the title, if any, to enable a continuous playback. Depending on the popularity and concurrent demand for a particular title, the number of residing objects may be increased or decreased to control the dependency of each box on other boxes for playback. Typically, the more residing objects for a title a box has, the more distributed copies of the title there are in the entire system and thus the less dependency of the ordering box on the other boxes.

In one embodiment, the header is always played first to ensure instant playback. In another embodiment, the header size is reduced to zero, in which case, a time-fill program is played first to provide a time frame that is sufficient enough to fetch and assembly the beginning data portion of the segments either locally available or from other boxes. Depending on implementation, the time-fill program may include one or more trailers related to the title being ordered, various notifications/updates or commercial programs. The time-fill program may be locally configured. In one embodiment, the time-fill program is provided to give a time frame in which data being fetched from one or more other devices can be stabilized. In another embodiment, the time-fill program provides a platform for sponsors that hope to display their respective programs to audience. Orders or slot positions for these programs in a time-fill program may be auctioned.

Referring toFIG. 5B, there shows an embodiment in which afile520 is being organized or fragmented in terms of foursegments524. In general, thefile520 representing a collection of all data pertaining to a title may be divided into any number of segments in consideration of a required transmission rate (e.g., related to the encoding and decoding rates for successful playback), and the minimum uploading and downloading capabilities of a network.FIG. 2C shows another embodiment in which afile530 is being organized or fragmented in terms of aheader532 and foursegments524, where theheader532 is always locally cached. One of the advantages of having a header locally cached is to facilitate an instantaneous playback after a movie is order. While the header is being played back, the needed segments are retrieved from other designated boxes. It can be appreciated the length of a header may be predefined or dynamically determined to provide a time buffer (e.g., 5 minutes) sufficiently to retrieve part of the data from the distributed segments for assembling with that of any locally cached segments, if any. As a result, an instantaneous VOD system may be realized.

Regardless whether a header is used or not, a file or a majority of a file will be fragmented and the segments are distributed among the boxes in service. According to one embodiment, given a required transmission rate (e.g., 1 megabit per second or 1 Mbps), the minimum uploading and downloading speeds of a network are considered to determine a number that defines the segmentation, and thus the dependency on other boxes and the support for concurrent demands of a particular title.

It is assumed that a minimum uploading speed is U and a required transmission rate is D, and D/U=K<k, where k is the smallest integer greater than K. In one embodiment, a file or a majority of a file is preferably divided into k segments to optimally utilize the uploading speed of U, assuming that the downloading speed is at least k times faster than the uploading speed. For example, in a POTS-based DSL network for residential areas, the required transmission may be about 1.0 Mbps while the uploading speed may be about 300 kbps. Hence, k=4. Assuming that an ordering box has a downloading speed four times the uploading speed of the other boxes, up to four segments in other boxes can be downloaded concurrently across the network as streaming into the ordering box without interruption.

FIG. 5D shows a data stream540 representing a file or a majority of a file. The file540 is divided into four segments547-550. The segments547-550 are created or formed by respectively sampling the file in a decimated manner. As a result, each of the segments includes a plurality of data blocks. Depending on an exact data length of the file540, an n-th data block in each of the segments547-550 is four successive data blocks in the file. In one embodiment, a data block comprises a chunk of data, for example, 256 Kbytes or 1 Mbyte.

As shown inFIG. 5D, the data stream540 is expressed in data blocks as follows: b11, b21, b31, b41, b12, b22, b32, b42, b13, b23, b33, b43, . . . b1n, b2n, b3n, b4n. With the decimated sampling, the four segments547-550 obtained can be respectively expressed as follows:

- Segment1={b11, b12, b13, b14 . . . };
- Segment2={b21, b22, b23, b24 . . . };
- Segment3={b31, b32, b33, b34 . . . }; and
- Segment4={b41, b42, b43, b44 . . . }.
  where b stands for “data block”, numerals after “b” are mere reference numbers. As used above, the data blocks b11, b21, b31, b41, b12, b22, b32, b42, b13, b23, b33, b43, . . . b1n, b2n, b3n, b4n are sequential while, for example, data blocks b11, b12, b13, b14 . . . b1n inSegment1 are not sequential. In other words, the data blocks in each of the segments are non-consecutive. Data streams from all segments must be multiplexed to reproduce useful data for playback.

It should be noted, however, a header, if used, includes data blocks that must be consecutive so that an instantaneous playback of the header is possible. It is evident that the data blocks in the segments are non-consecutive or interlaced.

FIG. 6A shows exemplary source information shown as amap630 illustrating how a library of 5000 movie titles is distributed across N boxes.Column632 lists all boxes in service. Each box is assigned a unique identifier for identification. Information in thecolumn632 may be viewed as the identifiers for the boxes in service. For example,box1 is assigned a unique identifier of “Box1” or a sequence of alphanumeric characters. Thecolumn634 lists a corresponding IP address for each of the boxes listed incolumn632. TheColumn636 lists predetermined time-fill programs for all titles in the library. Depending on implementation, the time-fill programs may be identical or each of the time-fill programs is self-configured in accordance with what has been ordered. Thecolumn638 lists what segments for title1 are residing in each of the boxes, assuming title1 is required to have two segments cached in each box. Thecolumn640 lists what segment for title2 is residing in each of the boxes, assuming title2 is required to have one segment cached in each of the boxes. Thecolumn642 lists what segment for title5000 is in a selected set of boxes, assuming title5000 is required to have one segment in these selected boxes. As a result, all segments in a box may be uniquely addressed for uploading to another box or playback of an ordered title locally.

FIG. 6B shows an exemplarysource information map650 corresponding toFIG. 6A. There are three other boxes606-n,606-3 and606-1 designated to supply three needed segments that are together assembled with a locally cached segment to facilitate the playback of the ordered movie. Each of the entries (e.g., IPA1) in thesource information map650 may include the port and address information that facilitates the peer-to-peer or box-to-box communication between two devices. It can be appreciated that relying on multiple sources to retrieve distributed segments to support a playback can be advantageously used in the architecture of current networks where the downloading bandwidth is typically a multiple of the uploading bandwidth.

The present invention has been described in sufficient details with a certain degree of particularity. It is understood to those skilled in the art that the present disclosure of embodiments has been made by way of examples only and that numerous changes in the arrangement and combination of parts may be resorted without departing from the spirit and scope of the invention as claimed. Accordingly, the scope of the present invention is defined by the appended claims rather than the foregoing description of embodiments.