Contribution aware peer-to-peer live streaming service

The present invention relates generally to peer-to-peer networking, and more particularly to incentive-based livestreaming over peer-to-peer networks.

There are two types of peer-to-peer (P2P) livestreaming environments: tree-based and mesh-based. The tree-based approach has taken some steps in providing contribution-aware P2P livestreaming. The mesh-based method does not provide any well-known support for providing contribution-aware P2P livestreaming. However, the mesh-based method is superior to the tree-based method in terms of robustness, efficiency, and the like.

<p> An environmental feature of the mesh-based approach to P2P livestreaming is that peers have constrained outgoing bandwidth. For mesh-based approaches with peer-constrained non-uniform transmission bandwidth, it is desirable to provide contribution-aware P2P livestreaming.</p>

<p> Livestreaming is described herein with respect to video, but can also include any type of livestreaming media, such as digital audio. As used herein, "/" indicates an alternative name for the same or similar component. In mesh-based processing of P2P livestreaming, peers / users receive different levels of service depending on their willingness to contribute to the network, in which case the willingness is the peer's uplink bandwidth for the mesh overlay. It is obtained by dividing the width contribution by the bandwidth per flow.</p><p> Peers wishing to participate in a P2P network are referred to herein as participating peers or requesting peers. A bootstrapping node is a node that acts as a gatekeeper. Participating peers contact the bootstrapping node to join the P2P network. The bootstrapping node informs the participating peers of the total number of peers / users in the P2P network. Alternatively, the participating peer informs the bootstrapping node of the intention value of its contribution, as measured by the bandwidth, that the participating peer is trying to make to the P2P overlay / network. Using the information provided by the bootstrapping node, participating peers calculate the number of parent peers they can connect to.</p><p> Each peer is a qualified parent peer (r) based on the overlay situation and its own bandwidth contribution._i) Is maintained at a certain number. This then determines the bandwidth, which in turn determines the quality that the peer can receive. Each individual peer serves a particular number of other peers as a child, based on its willingness and the availability of its child peers.</p><p> Livestreaming in a peer-to-peer network, including the steps of calculating the peer's entitlement and excess degree, identifying and contacting potential parent peers, and implementing connectivity policies. Contribution recognition method and system for.</p>

The present invention can be best understood by reference to the following detailed description in conjunction with the accompanying drawings. The drawings include the following figures, which are briefly described below.<figref num="1">It is a schematic diagram which shows the diffusion tree.</figref><figref num="2">It is a figure which shows the main basic element of the system by this invention.</figref><figref num="3A">It is a schematic diagram which shows the centralized peer discovery method.</figref><figref num="3B">It is a block diagram which shows the communication between a requesting peer and a bootstrapping node in a centralized peer discovery method.</figref><figref num="3C">It is a schematic diagram which shows the detailed operation of the requesting peer of FIG. 3B.</figref><figref num="3D">It is a block diagram which shows the communication between an existing peer and a bootstrapping node in a centralized peer discovery method.</figref><figref num="3E">FIG. 3 is a schematic diagram showing the detailed operation of the contacted peer in 3D.</figref><figref num="4A">It is a schematic diagram which shows the distributed peer discovery method.</figref><figref num="4B">It is a block diagram which shows the communication between a requesting peer and a bootstrapping node in a distributed peer discovery method.</figref><figref num="4C">It is a schematic diagram which shows the detailed operation of the requesting peer of FIG. 4B.</figref><figref num="4D">FIG. 4B is a schematic diagram showing the detailed operation of the contacted peer.</figref><figref num="5A">It is a schematic diagram which shows the semi-distributed peer discovery method.</figref><figref num="5B">It is a block diagram which shows the communication between a requesting peer and a bootstrapping node in a semi-distributed peer discovery method.</figref><figref num="5C">It is a schematic diagram which shows the detailed operation of the requesting peer of FIG. 5B.</figref><figref num="5D">FIG. 5B is a schematic diagram showing the detailed operation of the contacted peer in FIG. 5B.</figref><figref num="6">It is a flow chart which shows the peer discovery process.</figref>

The selection policy for distributing bandwidth to participating peers is based on the peer's contribution in the P2P network. There are N peers, peer i (p)_i) Is the intention value W_iAssuming that, by the heuristics described herein, its p_iCan have a qualified parent peer r_iDetermine the total number of. Use the generic cost function to determine the number of eligible parents that each peer can have.

<maths num="1"><img file="JP2010511348A_D0001.tif" /></maths>

In the formula, r_iIs the qualified parent peer, N is the number of participating peers, W_iIs p_iThe intention value of, t is the cost coefficient. Make sure your system has extra bandwidth by using a cost factor greater than 1.

Number of eligible parent peers r_iAfter determining, execute the parent discovery process. Each peer is at least r_iIt is necessary to find the parent peer to connect (form a connection). The parent discovery process needs to distribute bandwidth in a fair and timely manner. This specification describes three different methods by which a peer can find a suitable parent peer: centralized, distributed, and semi-distributed. The present specification also describes a device capable of finding a suitable parent peer for a participating / requesting peer.

Delivering live multimedia streams via P2P overlays is an effective technique for supporting one-to-many streaming over the Internet. This technique is commonly referred to as P2P streaming. In P2P streaming, participating users (peers) proactively provide their resources (bandwidth and storage space) by transferring their available content to other peers. The total resources available correspond to the total number of users / peers and can potentially accommodate any number of participating peers.

Efforts in designing P2P streaming protocols were often limited to highly resource-provisioned environments in the system. However, some important aspects of actual placement, which have been largely ignored, are the lack of resources in asymmetric and non-uniform bandwidth peers and overlays. The present invention addresses these issues by taking into account a fairly heterogeneous environment in which the host makes disproportionate contributions to overlays due to limited transmit bandwidth or lack of intent. .. Moreover, in such an environment, the total resources in the system may not be sufficient for everyone to receive a stream of sufficient quality.

It is desirable for peers to be able to effectively use all resources in the system while enjoying stream quality in proportion to their contributions. These policies can encourage peers to use the bandwidth of high bandwidth peers more, provide better quality to low bandwidth peers, and contribute more to enjoy higher quality. Possible methods of monitoring overall system resources, including centralized, distributed, and semi-distributed, are scrutinized.

PRIME is a live streaming technology, and each P2P streaming system (i) builds an overlay that bundles participating peers into overlays, and (ii) content delivery that determines the delivery of content to individual peers via overlays. It consists of two main components.

Participating peers form randomly connected overlays or meshes, which are directed graphs. Each peer maintains a certain number of parent peers that retrieve the content from it, and a certain number of child peers that deliver the content. For each peer, the number of parent peers and the number of child peers are shown as incoming and outgoing degrees, respectively. In order to effectively use the access link bandwidth of the participating peers, the incoming and outgoing degrees of each peer shall be its available receive bandwidth b._down, And transmit bandwidth b_upIs set in proportion to. The ratio of receive (or transmit) bandwidth to in (or out) order represents the average bandwidth of each connection, which is called bandwidth per flow or bwpf. bwpf is a configuration parameter that was a priori selected and known by the individual peers. Specifically, the in-degree and out-degree of the peer are b, respectively._down/ bwpf and b_upSet to be / bwpf.

A swarm-like content delivery mechanism is used for content delivery. The main advantage of group content delivery is that it can effectively use the transmit bandwidth of participating peers and is robust against peer participation movements (or drastic changes). Group content delivery combines push-type content reporting with pull-type content requests. As a parent peer, each peer periodically reports its newly received packets to its child peers. As a child peer, each peer parent a subset of the requested packets based on the available packets reported at each parent peer and the available bandwidth from each parent peer to the requesting child peer. Request each of the peers on a regular basis. The packet requested by each parent peer is determined by the packet scheduling algorithm. Each parent peer delivers the packet requested by each child peer via a congestion controlled mechanism such as TCP or RAP.

Content is coded with multi-description coding (MDC) to accommodate bandwidth non-uniformity between peers. The MDC aggregates the streaming content into several substreams, each substream being decrypted separately. The quality delivered to each peer is proportional to the number of separate substreams it receives. MDC coding allows each peer to receive the appropriate number of substreams delivered over its access link bandwidth.

The packet scheduling algorithm is to (i) fully use the available bandwidth from each parent peer and (ii) ensure that the packets requested by the child peers are delivered in time. Two goals should be achieved. The pattern of delivery of individual packets through the overlay mesh (the path that packets traverse from the source to each peer) depends on the group behavior of the packet scheduling algorithms on all participating peers and the overlay mesh topology. Each peer tracks the bandwidth available at each parent peer (through passive measurements) and the available content (using regular reports). Given this information, the scheduling algorithm is called periodically to determine which packets are required for each parent peer in two steps. First, the scheduler identifies the new packet with the highest time stamp available in the parent peer during the last reporting period. These new packets are always requested by the child peer to the parent peer. Second, each parent peer is required to have a random subset of the other missing packets in order to fully use its received bandwidth. To achieve load balancing, if packets are available in multiple parent peers, request the packet from the parent with the lowest ratio of requested packets to total packets that can be serviced by the parent peer.

By using the scheduling algorithm described above, each segment of content is in the spreading and swarming stages. It is delivered to each participating peer in two stages (phase). During the spread phase, each peer receives any fragment of the new segment from its parent peer at a higher level (closer to the source). Therefore, the newly generated segment fragments are progressively pulled by different levels of peers. For example, a newly generated segment fragment is taken by a level 1 peer after one period (Δ), by a level 2 peer after 2 * Δ, and so on. After a period of d, all peers in the overlay have one fragment of the new segment. Ideally, each piece of segment is delivered only once by the source. Therefore, a group of peers that receive a fragment of a segment during the diffusion stage form a tree called the diffusion tree, which originates from level 1 peers. The shaded nodes in Figure 1 form a diffuse tree. All connections from a level i peer to its child peers at level i + 1 are called diffuse connections. These connections are on the spread tree.

During the swarming phase, each peer receives all missing fragments of the segment from its parent peer at the same or lower level (far from the source). These parent peers are called swarming parents. The swarming phase can take multiple periods. This is because the swarming parent may not have all the missing fragments of the segment. Except for diffuse connections, all other connections in the overlay mesh are swarming connections. A collection of swarming connections forms a directed mesh called a swarming mesh. Swarming meshes are used to exchange different pieces of each segment between different diffusion trees.

That is, each fragment of any new segment is spread through a particular spread tree during the spread stage of that segment. The available fragments are then exchanged between peers in different diffusion trees via the swarming mesh during the swarming phase of the segment.

To allow peers to receive quality proportional to their contribution in the system, the P2P streaming technology described above is enhanced by the following four mechanisms shown in Figure 2. 1. System level information update and propagation 2. Calculation of peer qualifications and surplus connections 3. Discovery of peers 4. Policy

As shown in Figure 2, the basic element of the policy, "update", is the system-wide parameters N, W._i, And f_iAnd represent the need to propagate its parameters to all peers in the network. Qualified (R_i) And surplus (E_i) Degrees are calculated for each peer according to the formula shown below. Through peer discovery, in distributed peer discovery techniques, in a pool of peers, or in centralized peer discovery techniques, potential peers in a pair / list / queue of peers selected by the bootstrapping node. R with potentially preemptable child peers by contacting_i+ E_iAn attempt is made to find a vacant or parent peer. Finally, if a potential peer has been sought, but already connected, use Table 2 to determine if the potential peer's children are preemptible. If the child is preemptive, preempt the child peer.

System-level parameters need to be updated and propagated throughout livestreaming. These parameters are N, W, as defined in Table 1._i, And f_iIs included. Upon arrival, the participating peer contacts the bootstrapping node and intends to service the other peer (W)._i) To the bootstrapping node. The bootstrapping node is the total number N of peers in the system and the sum of the intention values of all peers Σ (W)._i) Has information. When leaving, the peer must contact the bootstrapping node again to unregister from the overlay. Peers may not unregister from the overlay in the event of corruption or other fatal conditions. Otherwise, the existing peer needs to notify the bootstrapping node of leaving the overlay.

<tables num="1"><img file="JP2010511348A_D0002.tif" /></tables>

Peer's actual contribution f_iChanges over time. Therefore, the system sums up the contributions of all peers Σ (f)_i) Needs to be refreshed regularly to calculate. The calculation can be performed by the following two methods.

· Centralized update: In this approach, the peer contacts the bootstrapping node each time the actual contribution changes.

· Distributed update: In this approach, contribution information is propagated along the diffusion tree. A peer periodically updates its parent peer in the spread tree with respect to its current contribution and the sum of the contributions of its subordinate (child) peers (in the spread tree). First-level peers send updates to bootstrapping nodes throughout. With distributed updates, the information is only updated on a regular basis, so Σ (f)_iThe value of) may not be accurate. However, it is considered that sufficient accuracy can be obtained by adjusting the length of regular updates.

N, Σ (W) for peers to calculate the number of qualified and surplus receptions, as described below._i) And Σ (f_i) Gathered information also needs to be propagated to all peers. This propagation can also be performed by a centralized method or a distributed method. In the centralized method, the bootstrapping node is N, Σ (W)._i), And Σ (f_i) Notify all peers of the current value on a regular basis. In the distributed method, information is distributed from the root (bootstrapping node) to all peers via a diffusion tree.

Qualified degree R of peer i_iIs calculated using the following formula.

<maths num="2"><img file="JP2010511348A_D0003.tif" /></maths>

In the equation, t is a parameter expressed as a cost factor, t&gt; 1 to ensure that the system has extra bandwidth. R_iIs basically the sum of the two terms. The first term is that the peer is W_iRepresents the minimum bandwidth entitled to receive by providing, and the second term is the average residual bandwidth per peer. The calculated surplus degree of peer i is E_i= Max-R_iIs.

When a peer calculates a qualified order, it tries to find a peer with a surplus order to accommodate it. That is, a peer with a surplus order looks for a parent peer that can help the peer with the surplus order make additional connections so as to improve its contribution and thus its quality. The peer discovery process can be performed using three different methods described below.

In centralized peer discovery, the bootstrapping node maintains a table that keeps track of each peer in the system. Each peer has one input in the table (id, W_i, F_i, E_i, R_i), In this case id is the peer id. W_iAnd f_iThe difference from and indicates the number of empty slots in this peer. Also, each peer in the system maintains a table of all its child peers in the spread tree and their corresponding parameters.

Then, referring to Figure 3, the requesting peer (the peer requesting the discovery of a potential peer to which it can connect) makes the request, r._A, E_A, F_ASend to the bootstrapping node along with its parameters in (1). The bootstrapping node returns a list of all potential parent peers that can potentially accept the requesting peer and become its parent peer (1). The potential parent peer of the requesting peer is defined as follows: 1. If the peer has an empty slot, it is a potential parent peer. 2. Based on the policies defined in Table 2, the parent peer of peer B is a potential peer if the requesting peer (denoted as peer A) can preempt the peer (denoted as peer B). Is.

<tables num="2"><img file="JP2010511348A_D0004.tif" /></tables>

An example of how to use Table 2 to determine if a current connection is preemptible is as follows: Suppose peer B is already connected to a particular parent peer. In the first example, peer a (p_a) And peer b (p)_a) Have qualified orders. p_aThe actual contribution (degree) is f_aIs. p_aThe actual qualified degree of entry is r_aIs. p_aThe actual surplus degree of is e_aIs. p_{b b}The same applies to. f_a= 20, r_a= 2, e_aIf = 0, then (r_a+ e_a) / f_a= 2/20 = 1/10. f_{b b}= 20, r_{b b}= 5, e_{b b}If = 0, then (r_{b b}+ e_{b b}) / f_{b b}= 5/20 = 1/4. p_a&lt;p_{b b}Because it is a calculation of p_aIs p_{b b}Can be preempted. In the second example, p_aHas a qualified degree, p_{b b}Has a surplus order. p_aUsing the same values for the parameters of p_aIs also in this case (r_a+ e_a) / f_aIt has a calculated value of = 2/20 = 1/10. f_{b b}= 5, r_{b b}= 2, e_{b b}If = 1, then (r_{b b}+ e_{b b}) / f_{b b}= 3/5. Again, p_a&lt;p_{b b}Because it is a calculation of p_{b b}Is p_aCan be preempted. In the third example, p_aHas a surplus order, p_{b b}Is a qualified degree. In this case, P_aIs P_{b b}Cannot be preempted. In the fourth example, p_aAnd p_{b b}Has a surplus order. f_a= 5, r_a= 2, e_aIf = 0, e_a/ f_a= 0/5 = 0. f_{b b}= 5, r_{b b}= 2, e_{b b}If = 2, e_{b b}/ f_{b b}= 2/5, so p_aIs P_{b b}Can be preempted. Because the ratio e_a/ f_aIs the ratio e_{b b}/ f_{b b}Because it is smaller. r_aAnd r_{b b}Note that is not used in this example.

When the requesting peer receives the list from the bootstrapping node (2), it contacts the peers in the list in sequence (2). The contacted peer accepts the requesting peer if it has an empty slot, and this peer becomes a child of this contacted peer. If the contacted peer does not have an empty slot, Table 2 shows whether the requesting peer can preempt one of the contacted peer's child peers. Use the stated policy. If the requesting peer can preempt any of the contacted child peers, the contacted peer disconnects the child peer selected to preempt and assigns a connection / slot to the requesting peer. If not, notify the requesting peer that it cannot be accepted. All peers in the returned list are potential parent peers, but may not be able to accept the requesting peer for the following reasons: 1. Parameters maintained on the bootstrapping node may not be up to date due to the delay between state changes and the time the parameters are updated. 2. As the requesting node gets more parent peers, r_A, E_A, F_AThe value of changes over time.

The process of contacting the peers in the list continues until the requesting peer gets the requested number of peers or the list is exhausted. In the latter case, the requesting peer pauses for a period of T and restarts the above process.

FIG. 3B is a block diagram of communication between the requesting peer and the bootstrapping node in a centralized peer discovery scheme. For each peer, there is one entry in the peer information table (id, W_i, F_i, E_i, R_i). The requesting peer sends a join request to peer contact interface 305 in the bootstrapping node (1). Peer communication interface 305 then forwards the reference request to peer information table module 310 (2). The peer information table module 310 performs a browse operation on the peer information table and returns a list of potential parent peer lists to peer contact interface 305 (3). Peer contact interface 305 then returns a list containing the peer information requested to the requesting peer.

FIG. 3C is a schematic diagram of the detailed operation of the requesting peer in FIG. 3B. The requesting peer contacts the bootstrapping node with a join request (1). The bootstrapping node returns a list of potential parent peers (2). The requesting peer queues potential / candidate parent peers with a list of potential parent peers. The requesting peer can then sequentially retrieve each potential parent peer from the queue, contact the potential parent peer, and accept the requesting peer, thus its child peers (or of their child peers). Check if it can be one) (3).

Figure 3D is a block diagram of communication between an existing peer and a bootstrapping node in a centralized peer discovery scheme. The existing peer updates its associated information with the bootstrapping node by sending an update message to the bootstrapping node's peer contact interface 305 (1). The peer communication interface 305 forwards the update information to the peer information table module 310 that updates the peer information table (2). The bootstrapping node returns a message to existing peers through the peer contact interface indicating that the information has been updated (3).

FIG. 3E is a schematic diagram of the detailed operation of the peer contacted in Figure 3D. The contacted peer (potential parent peer) receives a request from the requesting peer to join it as a child peer (1). The contacted peer may meet the participation request by inspecting its child peer information table and either by any empty slot it can have or by preempting one of the current child peers. Decide if you can. The contacted peer returns a response to the requesting peer indicating the outcome of the decision (2).

Then, referring to Figure 4, in the distributed discovery method, the requesting peer first contacts the bootstrapping node (1). The bootstrapping node returns the address / location of the content source node at the root of all spread trees (1). The requesting node maintains a waiting queue, puts the content source node in that queue, and the requesting peer first contacts the source node (2), which returns its child list to the requesting peer. (2). All peers in the content source node and system maintain their child peer's table in the spread tree and its corresponding parameters.

Each time the requesting peer dequeues one potential parent peer and contacts this potential parent peer to see if it can be accepted (3). Each contacted peer returns a list of its child peers (4). Acceptance is based on the same policies as described above. The contacted peer accepts the requesting peer if it has an empty slot, the requesting peer becomes a child of this contacted peer, and the contacted peer is a list of its child peers. Is returned to the requesting peer (4). In this way, the requesting peer contacts the peer further down the diffusion tree (5), and then the requesting peer contacts the children of each accepted and contacted peer, while Continue until the requested number of peers that the requesting peer can connect to is retrieved or the list and peers are exhausted (6). If the contacted peer does not have an empty slot, Table 2 shows whether the requesting peer can preempt one of the contacted peer's child peers. Use the stated policy. If the requesting peer can preempt any of the contacted child peers, the contacted peer disconnects the child peer selected to be preempted and connects / slots to the requesting peer. assign. If not, notify the requesting peer that it cannot be accepted. At the end of the process, the contacted peer also returns to the requesting peer a list of its child peers in the spread tree. The requesting peer attaches the returned list to the end of the waiting queue. This process continues until the requesting peer acquires the requested number of peers or the list is exhausted. In the latter case, the requesting peer pauses for a period of T and restarts the above process.

The third method is a semi-distributed method. To reduce signaling overhead, peers maintain some local information about their parent peers that are two hops apart. Each parent peer has the number of empty slots W_i, Actual contribution f_i, And the number of surplus connections to its child peers e_iPiggie back information about in a content packet. In addition, the parent peer has information about that parent peer (W)._i, F_i, E_i) To its child peers. Therefore, a node has information about its parent peer and grandparent peer.

FIG. 4B is a block diagram of communication between the requesting peer and the bootstrapping node in the distributed peer discovery method. The requesting peer sends a join request to peer contact interface 405 on the bootstrapping node (1). The bootstrapping node returns the address / location of the content source node (2). The requesting peer contacts the content source node (3).

FIG. 4C is a schematic diagram showing the detailed operation of the requesting peer in FIG. 4B. The requesting peer contacts the bootstrapping node (1). The requesting peer receives the content source node information from the bootstrapping node (2). The requesting peer contacts the content source node and receives a list / queue of its child peers, which are the potential parent peers of the requesting peer (2). The requesting peer stores the returned child peer list at the end of its potential / candidate parent peer's queue. The requesting peer then queues each potential parent peer's input to the potential / candidate parent peer and contacts it to see if the requesting peer can become its child peer. Confirm (4). The contacted potential parent peer returns a list / queue of its child peers, and the requesting peer stores it at the end of its potential / candidate parent peer's queue.

FIG. 4D is a schematic diagram of the detailed operation of the peer contacted in FIG. 4B. Upon receiving a join request from the requesting peer (1), the contacted peer inspects its child peer information table and either by any empty slot it can have, or of its current child peers. Determine if the participation request can be met by anticipating one of the above. The contacted peer returns a response indicating the outcome of the decision, along with its child peer list, to the requesting peer (2).

Then, referring to Figure 5A, the requesting node returns a waiting queue for potential peers (1) to contact the bootstrapping node (1). Note that the bootstrapping node has a list of all peers in the system. However, it does not maintain a table that tracks the parameters of each peer. The bootstrapping node randomly selects a predetermined number of potential parent peers from the list and returns the list as a waiting queue to the requesting node.

The requesting node then contacts each peer in the list (2) and receives its adjacency list (2). All of these lists are put together to form a single waiting queue. The requesting peer dequeues one peer each time and contacts this potential peer to see if it can be accepted (3). Acceptance is based on the same policies as described above. The contacted peer accepts the requesting peer if it has an empty slot, and this peer becomes a child of this contacted peer. If the contacted peer does not have an empty slot, Table 2 shows whether the requesting peer can preempt one of the contacted peer's child peers. Use the stated policy. If the requesting peer can preempt one of the contacted child peers, the contacted peer disconnects the child peer selected to be preempted and requests a connection / slot. Assign to the side peer. If not, notify the requesting peer that it cannot be accepted.

This process continues until the requesting peer acquires the requested number of peers or the list is exhausted. In the latter case, the requesting peer pauses for a period of T and restarts the above process.

FIG. 5B is a block diagram of communication between the requesting peer and the bootstrapping node in the semi-distributed peer discovery method. The peer information table maintains a list of all peers in the system. The requesting peer sends a join request to the bootstrapping node's peer contact interface 505 (1). The peer communication interface 505 then forwards the reference request to the peer information table module 510 (2). The peer information table module 510 performs a lookup operation on the peer information table and returns a list of randomly selected potential parent peers to peer contact interface 505 (3). The peer contact interface 505 then returns a list of randomly selected potential parent peers and their peer information to the requesting peer.

FIG. 5C is a schematic diagram of the detailed operation of the requesting peer of FIG. 5B. The requesting peer contacts the bootstrapping node (1). The requesting peer receives a list of randomly selected potential parent peers (2) and queues the randomly selected potential parent peers to its potential / candidate parent peers. The requesting peer sequentially contacts the peers in its potential / candidate parent peer's queue (3). The requesting peer then sends an adjacency request message to the contacted (potential parent) peer (3). Each contacted peer returns a list of its neighbors. The requesting peer stores a list of neighboring peers in its potential / candidate parent peer's queue. The requesting peer contacts the next potential parent peer in its potential / candidate parent peer's queue to see if the requesting peer can become its child peer (4).

FIG. 5D is a schematic diagram showing the detailed operation of the peer contacted in FIG. 5B. When the contacted peer receives an adjacency request message from the requesting node, it returns its adjacency peer list to the requesting node (1). If the incoming message is to look for an empty slot, the contacted peer inspects its child peer information table and either by any empty slot it can have, or by the current child peer. Determine if the requirement can be met by anticipating one of them. The contacted peer returns a response to the requesting peer indicating the outcome of the decision (2).

Next, refer to FIG. 6, which is a flow chart showing the peer discovery process. At 605, p_iContact the bootstrapping node. At 610, tests are done to determine if centralized peer discovery is to be used. If you are supposed to use centralized peer discovery, at 615, the bootstrapping node causes an empty slot / connection to p with a list / queue of potentially preemptable child peers._iProvided to. Then p_iIs 635, r of the potential peers as qualified peers_iAnd e of the potential peers as surplus peers_iContact. If you are not supposed to use centralized peer discovery, the 620 will be tested to determine if you are supposed to use distributed peer discovery. If you are supposed to use distributed peer discovery, at 625, the random list / queue identification (id) is p._iProvided to. At 630, p_iSearches for all peers in the list / queue of peers for empty slots / connections and potentially preemptive peers. Then p_iIs 635, r of the potential peers as qualified peers_iAnd e of the potential peers as surplus peers_iContact. If you are not supposed to use distributed peer discovery, by default you will use semi-distributed peer discovery. At 640, the number N of peers in the network is p_iProvided to. Then at 645, I explores all N peers and is a child or p of these N peers._iFind an empty slot or a potentially preemptive child peer among the children of a potential peer one hop away from. Then p_iIs 635, r of the potential peers as qualified peers_iAnd e of the potential peers as surplus peers_iContact.

It should be noted that the present invention can have a longer start-up delay / latency than the traditional non-contributory peer-to-peer streaming scheme. The process of finding the parent peer results in longer startup delays. In addition, the waiting time will be different depending on the different peer discovery method. The centralized peer discovery method and the semi-distributed peer discovery method have shorter start / join latency than the distributed peer discovery method that traverses the diffusion tree starting from the root. However, the contribution recognition peer-to-peer livestreaming method of the present invention uses MDC (Multiple Descriptive Coding) to encode the underlying data, so that the peer replays each time it receives the first description. Can be started. This can potentially reduce the startup wait time.

The peer preemption policy can lead to the participation and withdrawal of extra peers in the present invention. For example, if the requesting peer preempts a child peer that is already connected to the parent peer, the preempted child peer must try to join another parent peer and therefore systemizes extra joins and exits. Will be added to. This process continues until the preempted child peer finds an empty slot for it in another parent peer.

This has little effect if the preempted connection is a "surplus connection", as it is unlikely that the peer will have this connection first. One way to mitigate this issue is to change the lien policy. In the lien policy of the present invention, a "qualified connection" cannot preempt another "qualified connection". Also, since MDC (Multiple Description Coding) is used to encode the stream data, the effects of joining and leaving may not be significant. If the peer loses some description, the display quality will be degraded, but the stream will still be visible.

It should be understood that the present invention can be implemented in various forms of hardware, software, firmware, dedicated processors, or combinations thereof. It is desirable to implement the present invention as a combination of hardware and software. Furthermore, the software should be implemented as an application program that is tangibly embedded in the program storage device. The application program can be uploaded to and executed by a machine that contains any suitable architecture. The machine should be implemented on a computer platform with hardware, such as one or more central processing units (CPUs), random access memory (RAM), and input / output (I / O) interfaces. The computer platform also includes an operating system and microinstructions. The various steps and functions described herein can be part of a microinstruction code, or part of an application program (or a combination thereof), which is performed through an operating system. .. In addition, various other peripherals can be connected to the computer platform, such as additional data storage and printing devices.

Since it is desirable to implement some of the component system components and method steps shown in the accompanying drawings in software, the actual connections between the system components (or process steps) are programmed by the present invention. It should be further understood that it can vary depending on the method. Given the teachings herein, the parties may intend to implement or configure these and similar of the present invention.