System and method for controlling peer-to-peer connections

BACKGROUND

p-0002Peer-to-Peer (P2P) streaming applications use diverse connectivity between participants in a network and cumulative bandwidth of network participants rather than conventional centralized resources where a relatively low number of servers provide the core value to a service or application. P2P applications are typically used for sharing content files containing content such as audio, video, and/or digital data, for example, over the internet. In addition, P2P streaming applications have been widely used for scalable streaming of live multimedia over the internet. In P2P streaming, participating peers form an overlay and deliver the content on top of the overlay.

p-0003Conventional live P2P streaming applications use random connected overlays among participating peers. For example, <figref idrefs="DRAWINGS">FIG. 1</figref> illustrates conventional overlays that include random connections. Referring to <figref idrefs="DRAWINGS">FIG. 1</figref>, a conventional system <b>100</b> within a P2P streaming application may include peers <b>105</b> in an Internet Service Provider (ISP) network A (ISP A) and an ISP network B (ISP B) that are randomly connected. For example, one of the peers <b>105</b> in the ISP A <b>110</b> may connect to another peer in the ISP A <b>110</b> (e.g., internal) or connect to one of the peers <b>105</b> in ISP B <b>120</b> (external). Because the connections among peers <b>105</b> are random, the connections may be either internal connections or inter-ISP connections (or external connections). The terms inter-ISP connections and external connections are inter-changeable terms. However, costs for inter-ISP connections are usually greater than internal connections. Because the random overlay system uses a significant amount of inter-ISP connections, the cost for implementing such a system may be relatively high.

p-0004To reduce inter-ISP connections among peers <b>105</b>, conventional approaches have focused on localization of overlay connectivity within each ISP network. P2P localization enables individual ISP networks to control the selection of neighbor peers while considering their policies and business relationships with other ISP networks in order to manage and reduce traffic over inter-ISP connections.

p-0005One type of method for localization uses an oracle that directs the local peer to use a selected number of peers. For example, a new local peer may contact a P2P bootstrap node of the P2P application to receive a list of candidate peers (or potential neighbors) participating in the underlay. Next, the local peer transmits the list of candidate peers to an oracle associated with the local peer. The oracle applies connection preferences by sorting the list of candidate peers and returns the sorted list back to the local peer. The local peer uses the sorted list for initiating connections to preferred neighbors. In this method, the ISP has some control over which peers the local peer is attempting to connect. However, localizing P2P traffic potentially can affect the performance of P2P applications by decreasing the diversity of content in each neighborhood of the local peer.

p-0006Another type of localization uses file swarming mechanisms over localized overlays. In the swarm-based approach, video data is divided into multiple sub-streams, and the participating peers are organized into a random mesh overlay, where swarming is used for the delivery of each sub-stream. A parent-child relationship exists between connected peers. Each peer as a parent notifies children peers of the availability of sub-streams. To effectively utilize access link bandwidth of participating peers, incoming and outgoing degrees of peers should be proportional to the incoming and outgoing bandwidth. This implies that all connections have approximately the same average bandwidth. Swarming content delivery combines push content reporting by parent peers with pull content requesting by children peers. Each peer simultaneously receives content from all of its parent peers and provides content to all of its children peers. Parent peers progressively report the availability of their new sub-streams to all of the children peers. Given the available sub-streams among the parent peers, each peer periodically invokes a block scheduling scheme to determine which blocks should be pulled from each parent peer in order to maximize the utilization of bandwidth and the delivered quality.

p-0007However, conventional embodiments of the swarm-based approach take advantage of the relaxed timing constrains of file delivery applications, which have a single requirement only, that is, the delivery of all segments. As a result, studies have demonstrated that playout of live video streams is dramatically increased and the claim of “live streaming” becomes questionable (e.g., tens of seconds, even minutes for larger swarms).

SUMMARY

p-0008The present invention relates to a system and method for controlling peer-to-peer connections in a Peer-to-Peer (P2P) streaming application for individual Internet Service Provider (ISP) networks over a localized overlay.

p-0009The system may include a tracker local to a first ISP network configured to select edge peers among local peers of the first ISP network. The selected edge peers have external connections to peers outside the first ISP network in order to transfer sub-streams to or from the first ISP network, and the local peers not selected as edge peers have internal connections to other local peers within the first ISP network to transfer the sub-streams over the localized overlay. The tracker may select the edge peers based on bandwidth. Further, the tracker may select an edge peer when an existing edge peer departs from the P2P streaming application. Alternatively, the tracker may select an edge peer based on whether a number of edge peers is below a first threshold.

p-0010In another embodiment, the tracker is configured to select edge peers of a first type and edge peers of a second type. The edge peers of the first type manage incoming external connections and the edge peers of the second type manage outgoing external connections.

p-0011The system further includes a session-level tracker configured to provide a list of potential external peers to the edge peers to establish the external connections in response to an announce message from the edge peers. The edge peers are the only local peers visible to external peers outside the first ISP network. Also, the session-level tracker may be further configured to provide a list of local trackers.

p-0012In one embodiment, the tracker is configured to schedule the transfer of the sub-streams via the external connections between the external peers and the edge peers of the first ISP network. The tracker schedules the transfer of the sub-streams based on available sub-streams at the external peers and an ISP Hop Count (ICH) for each sub-stream. The ICH indicates a number of ISP networks that a sub-stream traversed.

p-0013The local peers of the first ISP network schedule the transfer of the sub-streams via the internal connections based on available sub-streams at internal parent peers and a Peer Hop Count (PHC). The PHC indicates a number of internal peers that a respective sub-stream traversed within a single ISP network. The local peers schedule the transfer of sub-streams which have a minimum PHC count value.

p-0014Each sub-stream includes: (1) ISP Hop Count (ICH) indicating a number of ISP networks that a respective sub-stream traversed, (2) Peer Hop Count (PHC) indicating a number of internal peers that a respective sub-stream traversed within a single ISP network, and (3) Overall Hop Count (OHC) indicating a total number of peers that a respective sub-stream traversed regardless of an ISP network.

p-0015The method includes selecting, by a tracker local to a first ISP network, edge peers among local peers of the first ISP network. The selected edge peers have external connections to peers outside the first ISP network in order to transfer sub-streams to or from the first ISP network, and the local peers not selected as edge peers have internal connections to other local peers within the first ISP network to transfer the sub-streams over the localized overlay. The selecting step selects the edge peers based on bandwidth. Further, the selecting step selects an edge peer when an existing edge peer departs from the P2P streaming application. Alternatively, the selecting step selects an edge peer based on whether a number of edge peers is below a first threshold.

p-0016In another embodiment, the selecting step selects edge peers of a first type and edge peers of a second type. The edge peers of the first type manage incoming external connections and the edge peers of the second type manage outgoing external connections.

p-0017The method further includes providing, by a session-level tracker, a list of potential external peers to the edge peers to establish the external connections in response to an announce message from the edge peers. The method further includes scheduling, by the tracker, the transfer of the sub-streams via the external connections between the external peers and the edge peers of the first ISP network. The scheduling step schedules the transfer of the sub-streams based on available sub-streams at the external peers and an ISP Hop Count (ICH) for each sub-stream. The ICH indicates a number of ISP networks that a sub-stream traversed.

p-0018The method further includes scheduling, by the local peers of the first ISP network, the transfer of the sub-streams via the internal connections based on available sub-streams at internal parent peers and a Peer Hop Count (PHC). The PHC indicates a number of internal peers that a respective sub-stream traversed within a single ISP network.

BRIEF DESCRIPTION OF THE DRAWINGS

Example embodiments will become more fully understood from the detailed description given herein below and the accompanying drawings, wherein like elements are represented by like reference numerals, which are given by way of illustration only and thus are not limiting of the present invention, and wherein:

<figref idrefs="DRAWINGS">FIG. 1</figref> illustrates a conventional overlay showing random connection;

<figref idrefs="DRAWINGS">FIG. 2</figref> illustrates a system for controlling peer-to-peer connections according to an embodiment of the present invention;

<figref idrefs="DRAWINGS">FIG. 3</figref> illustrates an example of the structure of the local tracker according to an embodiment of the present invention;

<figref idrefs="DRAWINGS">FIG. 4A</figref> illustrates a flow diagram for controlling peer-to-peer connections according to a two-tier scheduling scheme according to an embodiment of the present invention;

<figref idrefs="DRAWINGS">FIG. 4B</figref> illustrates the structure of a video stream within a P2P streaming application according to an embodiment of the present invention; and

<figref idrefs="DRAWINGS">FIG. 5</figref> illustrates an example of inter-ISP scheduling according to an embodiment of the present invention.

DETAILED DESCRIPTION OF EXAMPLE EMBODIMENTS

p-0026Various embodiments of the present invention will now be described more fully with reference to the accompanying drawings in which some embodiments of the invention are shown. Like numbers refer to like elements throughout the description of the figures.

p-0027As used herein, the singular forms “a”, “an” and “the” are intended to include the plural forms as well, unless the context clearly indicates otherwise. It will be further understood that the terms “comprises”, “comprising,”, “includes” and/or “including”, when used herein, specify the presence of stated features, integers, steps, operations, elements, and/or components, but do not preclude the presence or addition of one or more other features, integers, steps, operations, elements, components, and/or groups thereof.

p-0028It should also be noted that in some alternative implementations, the functions/acts noted may occur out of the order noted in the figures. For example, two figures shown in succession may in fact be executed substantially concurrently or may sometimes be executed in the reverse order, depending upon the functionality/acts involved.

p-0029Portions of the present invention and corresponding detailed description are presented in terms of software, or algorithms and symbolic representations of operations on data bits within a computer memory. These descriptions and representations are the ones by which those of ordinary skill in the art effectively convey the substance of their work to others of ordinary skill in the art. An algorithm, as the term is used here, and as it is used generally, is conceived to be a self-consistent sequence of steps leading to a desired result. The steps are those requiring physical manipulations of physical quantities. Usually, though not necessarily, these quantities take the form of optical, electrical, or magnetic signals capable of being stored, transferred, combined, compared, and otherwise manipulated. It has proven convenient at times, principally for reasons of common usage, to refer to these signals as bits, values, elements, symbols, characters, terms, numbers, or the like.

p-0030It should be borne in mind, however, that all of these and similar terms are to be associated with the appropriate physical quantities and are merely convenient labels applied to these quantities. Unless specifically stated otherwise, or as is apparent from the discussion, terms such as “selecting” or “providing” or “determining” or “managing” or “displaying” or the like, refer to the action and processes of a computer system, or similar electronic computing device, that manipulates and transforms data represented as physical, electronic quantities within the computer system's registers and memories into other data similarly represented as physical quantities within the computer system memories or registers or other such information storage, transmission or display devices.

p-0031Note also that the software implemented aspects of the invention are typically encoded on some form of program storage medium or implemented over some type of transmission medium. The program storage medium may be magnetic (e.g., a floppy disk or a hard drive) or optical (e.g., a compact disk read only memory, or “CD ROM”), and may be read only or random access. Similarly, the transmission medium may be twisted wire pairs, coaxial cable, optical fiber, or some other suitable transmission medium known to the art. The invention is not limited by these aspects of any given implementation.

p-0032The present invention will now be described with reference to the attached figures. Various structures, systems and devices are schematically depicted in the drawings for purposes of explanation only and so as to not obscure the present invention with details that are well known to those skilled in the art. Nevertheless, the attached drawings are included to describe and explain illustrative examples of the present invention. The words and phrases used herein should be understood and interpreted to have a meaning consistent with the understanding of those words and phrases by those skilled in the relevant art. No special definition of a term or phrase, i.e., a definition that is different from the ordinary and customary meaning as understood by those skilled in the art, is intended to be implied by consistent usage of the term or phrase herein. To the extent that a term or phrase is intended to have a special meaning, i.e., a meaning other than that understood by skilled artisans, such a special definition will be expressly set forth in the specification in a definitional manner that directly and unequivocally provides the special definition for the term or phrase.

p-0033Example embodiments of the present invention relate to a system and method for controlling peer-to-peer connections in a Peer-to-Peer (P2P) streaming application for individual Internet Service Provider (ISP) networks over a localized overlay. The embodiments of the present invention effectively control external traffic of individual ISP networks by limiting the number of external connections and revising the scheduling scheme for the swarm-based approach to deliver, for example, quality video streaming. In contrast, the basic assumption in overlay localization is that peers do not have any preference in selecting parent peers as long as the peers can identify a proper number of parent peers. By directing peers in the same ISP network to discover and connect to other peers in the same ISP network, the number of external (incoming and outgoing) connections for each ISP network can be reduced, which in turn proportionally reduces the external traffic (e.g., cost) associated with a P2P application.

p-0034<figref idrefs="DRAWINGS">FIG. 2</figref> illustrates a system <b>200</b> for controlling P2P connections in a P2P streaming application for individual ISP networks according to an embodiment of the present invention. The system <b>200</b> in <figref idrefs="DRAWINGS">FIG. 2</figref> illustrates two ISP networks, ISP A and ISP B, a session-level tracker <b>120</b> that discovers external peers for inter-ISP connections, peers <b>105</b> in ISP A, and peers <b>125</b> in ISP B, which are connected via the internet in a P2P streaming application. P2P streaming applications are used for sharing, among peers, content files containing content such as audio, video, and/or or digital data over the internet. In addition, P2P streaming applications are used for streaming of live multimedia over the Internet.

p-0035Peers <b>105</b> and peers <b>125</b> may be any type of system configured to operate a P2P application such as a personal computer, wireless phone or any other similar device. Peers <b>105</b> are local to ISP A, and peers <b>125</b> are local to ISP B. Peers that are local to an ISP network may be referred to as local peers. Although <figref idrefs="DRAWINGS">FIG. 2</figref> illustrates a finite number of peers, the number of peers in an ISP continuously varies depending on the traffic associated with a P2P application. In addition, ISP A includes edge peers <b>110</b>, which are also peers <b>105</b> local to ISP A, but have been selected as edge peers as explained below.

p-0036ISP A includes a local tracker <b>115</b>, to which peers local to ISP A (e.g., peers <b>105</b> and <b>110</b>) joining the P2P network announce themselves. The connections between the local tracker <b>115</b> and each peer <b>105</b> and <b>110</b> are illustrated by the dotted connection lines between the local tracker <b>115</b> and each peer <b>105</b> and <b>110</b>. As a response, the local tracker <b>115</b> returns a list of candidate peers to each peer <b>105</b> and <b>110</b> for potential connections. In addition, the local tracker <b>115</b> is configured to determine a total number of incoming and outgoing external connections for ISP A and to ensure that the aggregate incoming bandwidth equals at least the stream bandwidth.

p-0037In ISP A, the solid lines among local peers <b>105</b> and <b>110</b> illustrate the transfer of P2P data (internally). Also, the solid lines from the internet to edge peers <b>110</b> illustrate the transfer to P2P data with an outside source such as an external peer or a content provider (externally), which is further explained below. Similarly, in ISP B, the solid lines illustrate the transfer of P2P data. However, in ISP B, each peer <b>125</b> transfers P2P internally and externally. As a result, P2P external control is required for all of the external connections of peers <b>125</b> in ISP B (as shown by the dotted lines with arrows), while P2P external control is only required for connections of edge peers <b>110</b> in ISP A (as shown by the dotted lines with arrows).

p-0038Although only two ISP networks are illustrated in <figref idrefs="DRAWINGS">FIG. 2</figref>, example embodiments of the present invention cover any number of ISP networks. In contrast to ISP A, ISP B does not use localization. Rather, all peers <b>125</b> in ISP B contact the session-level tracker <b>120</b> for external connections to peers <b>105</b> in ISP A. Although the P2P network in ISP B in <figref idrefs="DRAWINGS">FIG. 2</figref> is illustrated as an ISP without localization, ISP B may include localization. In other words, the local tracker <b>115</b> may control external connection to peers outside the ISP A network, which are apart of an ISP network that includes localization or does not include localization (as shown in <figref idrefs="DRAWINGS">FIG. 2</figref>).

p-0039<figref idrefs="DRAWINGS">FIG. 3</figref> illustrates an example of the structure of the local tracker <b>115</b> according to an embodiment of the present invention. The local tracker <b>115</b> includes a central processing unit (CPU) <b>321</b>, random access memory (RAM) <b>322</b>, read only memory (ROM) <b>326</b>, a hard disk drive <b>327</b>, and a network interface <b>328</b>. The local tracker <b>115</b> may also include other components other than shown on <figref idrefs="DRAWINGS">FIG. 3</figref> that are well known to one skilled in the art. The CPU <b>321</b>, the RAM <b>322</b>, the ROM <b>326</b>, the hard disk drive <b>327</b>, and the network interface <b>328</b> communicate with each other via a bus. The hard disk drive <b>327</b> operates in a manner which is well known to one skilled in the art.

p-0040The RAM <b>422</b> may store an operating system <b>323</b> providing instructions for the CPU <b>321</b> to carry out operations of the local tracker <b>115</b>. Any general-purpose operating system may be employed. The network interface unit <b>328</b> allows the CPU <b>321</b> to communicate with the Internet, or some other communications network, which are constructed for use with various communication protocols including the TCP/IP protocol. The network interface unit <b>328</b> may include transceiver(s), transceiving device(s), and/or network interface card(s) (NICs), for example. The network interface unit <b>328</b> is configured to communication with the internet, peers <b>105</b>, <b>110</b>, and <b>125</b>, the session-level tracker <b>120</b>, as well as any other device for performance of the functions of the local tracker <b>115</b>.

p-0041Also, the RAM <b>322</b> may include one or more data storage units, which can be utilized by the local tracker <b>115</b> to store, among other things, applications, as well as database information, for example. For instance, the RAM <b>322</b> may store applications necessary to perform the functions of the local tracker <b>115</b>, which are described below.

p-0042<figref idrefs="DRAWINGS">FIG. 4A</figref> illustrates a flow diagram for controlling peer-to-peer connections according to a two tier scheduling scheme according to an embodiment of the present invention. The local tracker <b>115</b> controls external traffic of ISP A by limiting the number of external connections.

p-0043In particular, referring to S<b>410</b>, the local tracker <b>115</b> is configured to select edge peers <b>110</b>, Peer A<b>1</b> and Peer A<b>2</b>, among the local peers of the ISP A. The selected edge peers <b>110</b> maintain the external connections to peers outside the ISP A network (e.g., peers <b>125</b>) in order to deliver sub-streams of the video stream to the ISP A, while the local peers of ISP A maintain internal connections to other local peers within ISP A to deliver the sub-streams over the localized overlay of ISP A. In other words, edge peers <b>110</b> have external connections and peers internal to ISP A (e.g., peers <b>105</b>) do not have external connections. The selection decision made by the local tracker <b>115</b> may be based on the bandwidth of the edge peer <b>110</b>. For instance, peers local to ISP A with a relatively higher bandwidth are preferred to be selected as edge peers <b>110</b>. However, the selection decision is not limited to only bandwidth of potential edge peers where other types of criteria may be used as a basis for making such a selection decision. For purposes of this invention, the local tracker <b>115</b> selects less than all of the peers local to ISP A as edge peers <b>110</b>. The number of edge peers can be any integer greater or equal to 1, which is less than the total number of peers local to ISP A. In addition, once an edge peer departs from the P2P application, the local tracker <b>115</b> may select another peer local to ISP A as an edge peer based on bandwidth or any other criteria explained above.

p-0044In another embodiment, local tracker <b>115</b> is configured to determine a number of edge peers within an ISP network and select an edge peer based on whether the number of edge peers is below a first threshold. The first threshold may be a desired (or alternatively, a predetermined) number of peers. The desired number of peers may be any number of peers such as 1 or any integer greater than 1.

p-0045In another embodiment, the local tracker <b>115</b> tracks local peers and status of the local peers as either regular peers or edge peers. For example, when a new peer joins the P2P application in ISP A, the local tracker <b>115</b> transmits the number of edge peers and local peers to the new peer. The newly joined peer decides to become an edge peer based on the number of edge peers reported by the local tracker <b>115</b>. For example, if the number of edge peers is below the first threshold, the peer becomes an edge peer.

p-0046Once the edge peers <b>110</b> are selected, the edge peers <b>110</b> obtain external parent peers (S<b>420</b>), connect to external peers (S<b>430</b>), and start exchanging content information according to an inter-ISP scheduling mechanism (S<b>440</b>), as discussed below. Also, the local peers (e.g., peers <b>105</b> and <b>110</b>) connect to other local peers within the ISP A network (S<b>450</b>), and start exchanging content information according to an intra-ISP scheduling mechanism (S<b>460</b>). The classification of peers of the ISP A network into either edge peers <b>110</b> or local peers <b>105</b> over a localized overlay provides a two tier scheduling mechanism for delivery of, for example, the video stream, which is performed according to intra-ISP scheduling and inter-ISP scheduling. Although the flowchart of <figref idrefs="DRAWINGS">FIG. 4A</figref> illustrates a sequence of steps, these steps may occur out of order and at the same time. For instance, typically intra-ISP scheduling is performed at the same time as inter-ISP scheduling.

p-0047In S<b>420</b>, the session-level tracker <b>120</b> is configured to provide a list of potential external peers (e.g., peers <b>125</b> in ISP B) to establish the external connections in response to an announce message from the edge peers <b>110</b>. In other words, the edge peers <b>110</b> discover external peers (e.g., peers <b>125</b> in ISP B) through the session-level tracker <b>120</b>. The edge peers <b>110</b> signal the session-level tracker <b>120</b> through an announce message and in return receive a list of potential external peers. Based on the list of potential external peers, the edge peers <b>110</b> connect to a sub-set of external peers (S<b>430</b>). Because only the selected edge peers <b>110</b> announce themselves to the session-level tracker <b>120</b>, the edge peers <b>110</b> are the only local peers visible to external peers outside the ISP A network (e.g., peers <b>125</b> in ISP B). Therefore, no other peers than the edge peers <b>110</b> will receive incoming cross-ISP connection requests, which effectively limits and controls the number of incoming connections.

p-0048In another embodiment, the local tracker <b>115</b> is configured to select two different classes of edge peers <b>110</b> to differentiate between external incoming and outgoing connection requests. For instance, the local tracker <b>115</b> selects edge peers of a first type that manage incoming external connection requests and edge peers of a second type that manage outgoing external connection requests. The first type of edge peers selected by the local tracker <b>115</b> are responsible for accepting incoming connections from peers outside the ISP A network (e.g., peers <b>125</b>) and serving the peers outside the ISP A network as parent peers. The second type of edge peers are responsible for connecting to external parent peers for bringing the content information to the ISP A network (e.g. local peers <b>105</b> and <b>110</b>) from the external parent peers.

p-0049In one embodiment, the first type of edge peer announces itself to the session-level tracker <b>120</b>, thus, making the first type of edge peer visible to the external peers. The second type of edge peer contacts the session-level tracker <b>120</b> and requests a list of the first type of edge peers from other ISP networks.

p-0050In another embodiment, no peers from a localization-enabled ISP network (e.g., ISP A) announce themselves to the session-level tracker <b>120</b>. Instead, the local tracker <b>115</b> of ISP A and local trackers of other localization-enabled ISP networks announce themselves to the session-level tracker <b>120</b>. When an external edge peer (or a regular peer in a non-localized ISP network—e.g., from ISP B) contacts the session-level tracker <b>115</b>, the external edge peer or regular peer identifies local trackers in the session-level tracker's response to its request. For example, if the list of local trackers included local tracker <b>115</b> of the ISP A network, the requesting peer from ISP B would subsequently contact local tracker <b>115</b> of ISP A. The local tracker <b>115</b> would then redirect/forward the request to a randomly chosen/a priori selected local peer if the number of outgoing connections is below a threshold. In this case, the external peer connects to the local peer, which effectively becomes an edge peer of the second type. The embodiments discussed below will refer to edge peers <b>110</b> without the distinction between edge peers of the first type and edge peers of the second type for purposes of simplicity. However, the embodiments discussed below may also operate with edge peers of a first type and edge peers of a second type.

p-0051In S<b>440</b>, the edge peers <b>110</b> exchange information for the video stream being relayed to/from the connected external peers according to an inter-ISP scheduling mechanism, as discussed below.

p-0052In S<b>450</b>, local peers <b>105</b> not selected to become edge peers <b>110</b> will connect only to local peers of the ISP A network. For example, as explained above, when new peers join the P2P network in ISP A, the new peers signal to the local tracker <b>115</b> through an announcement message. In return, the newly joined peers receive a list of potential peers. The newly joined local peers will then connect to other local peers in the ISP A network based on the received list of potential peers. In S<b>460</b>, the local peers <b>105</b> exchange information for the video data being relayed to/from the other local peers in the ISP A network according to an intra-ISP scheduling mechanism, which is discussed below after the inter-ISP scheduling mechanism.

p-0053Embodiments of the present invention provide a scheduling scheme at two levels, from source to individual ISP networks (via inter-ISP scheduling) and from each incoming edge peer <b>110</b> to all internal peers (via intra-ISP scheduling). Inter-ISP scheduling relates to scheduling delivery of sub-streams of, for example, a video stream being relayed from an external peer to an ISP network, where an ISP network is represented as a single peer. In other words, inter-ISP scheduling focuses on delivery of a full quality video stream to individual ISP networks. As a result, inter-ISP scheduling is only concerned with external connections and is thus implemented at edge peers <b>110</b>. In contrast, intra-ISP scheduling focuses on delivery of each sub-stream from edge peers <b>110</b> to all internal peers within individual ISP networks. Intra-ISP scheduling is only responsible for managing internal connections within each ISP and is implemented by any peer with an internal parent peer. In order to achieve effective delivery for both the inter-ISP scheduling level and the intra-ISP scheduling level, a video stream is divided into a plurality of sub-streams.

p-0054<figref idrefs="DRAWINGS">FIG. 4B</figref> illustrates the structure of a video stream <b>300</b> within a P2P streaming application according to an embodiment of the present invention. The video stream <b>300</b> is divided into n sub-streams, where n is any integer greater or equal to 1. Each sub-stream carries the following three counters: ISP Hop Count (IHC), Peer Hop Count (PHC), and Overall Hop Count (OHC). The IHC counter keeps track of the number of ISP networks that a substream has traversed. The PHC counter keeps track of the number of internal peers that a sub-stream has traversed within a single ISP network. The PHC counter is reset by the corresponding edge peer where a sub-stream enters an ISP network. The OHC counter keeps track of the total number of peers (regardless of their ISP) that a sub-stream has traversed.

p-0055<figref idrefs="DRAWINGS">FIG. 5</figref> illustrates an example of inter-ISP scheduling according to an embodiment of the present invention. <figref idrefs="DRAWINGS">FIG. 5</figref> illustrates an example where two sub-streams, S<b>1</b> and S<b>2</b>, are delivered to a group of six ISP networks <b>502</b> (ISP<b>1</b>, ISP<b>2</b>, ISP<b>3</b>, ISP<b>4</b>, ISP<b>5</b> and ISP<b>6</b>) from a source <b>501</b>. Each ISP network <b>502</b> as well as individual peers have incoming and outgoing degrees of 2. Each ISP network <b>502</b> includes a plurality of peers local to their respective ISP network.

p-0056Peer A in ISP<b>1</b> would be considered as a parent peer of Peer C in ISP<b>3</b>, and Peer B in ISP<b>1</b> would be considered a parent peer of Peer D in ISP<b>4</b>. Peer C in ISP<b>3</b> and Peer D in ISP<b>4</b> are edge peers <b>110</b>. Referring to the parent peer A in ISP<b>1</b>, the two sub-streams, S<b>1</b> and S<b>2</b>, are available to Peer C in ISP<b>3</b>. In this particular example, both sub-streams, S<b>1</b> and S<b>2</b>, at Peer A illustrate their respective OHC and IHC values. For sub-stream S<b>1</b>, OHC=7 and IHC=1. For sub-stream S<b>2</b>, OHC=5 and IHC=3. The IHC for substream S<b>1</b> is 1 because ISP<b>1</b> receives this sub-stream directly from the source <b>501</b>. On the other hand, sub-stream S<b>2</b> has traversed two more ISPs (e.g., ISP <b>2</b> and ISP <b>5</b>) to arrive at Peer A in ISP<b>1</b>. Thus, the IHC for substream <b>2</b> at Peer A is 3. Furthermore, at Peer B, both sub-streams, S<b>1</b> and S<b>2</b>, illustrate their respective OHC and IHC values. For sub-stream S<b>1</b>, OHC=6 and IHC=1. For sub-stream S<b>2</b>, OHC=5 and IHC=3.

p-0057In order to schedule which sub-stream children peers (e.g., Peer C in ISP<b>3</b> and Peer D in ISP<b>4</b>) pull from their respective parent peer (e.g., Peer A in ISP<b>1</b> and Peer B in ISP<b>1</b>) to ensure that all sub-streams are delivered to each ISP, the local tracker <b>115</b> periodically or after departure of an edge peer performs a coordination by polling all edge peers <b>110</b> to obtain the available sub-streams at their corresponding external parent peers as well as the associated IHC for each sub-stream. In this case, the local tracker <b>115</b> of ISP<b>3</b> would obtain identifying information for sub-streams S<b>1</b> and S<b>2</b> at Peer A, and IHC values for each of the sub-streams at Peer A. The local tracker <b>115</b> of ISP<b>3</b> also obtains identifying information, for other sub-streams at edge peers of ISP<b>3</b> other than Peer A.

p-0058After the local tracker <b>115</b> receives the information from the edge peers regarding the availability of the sub-streams at their respective parent peers and the IHC values, the local tracker <b>115</b> then coordinates the delivery of the sub-streams to the edge peers to ensure that all of the sub-streams are delivered to the ISP. The coordination mechanism of the local tracker <b>115</b> may employ any well-known means to coordinate the delivery of sub-streams to edge peers to ensure that all sub-streams are delivered to the ISP.

p-0059In contrast, intra-ISP scheduling delivers each sub-stream from its corresponding edge peer to all other peers in the ISP network. Each internal peer independently schedules different sub-streams based on the available sub-streams and the internal parent peer and PHC value at each parent peer. In other words, each internal peer considers the available sub-streams along with the PHC value at each parent and selects the sub-stream that has the minimum PHC (e.g., minimum distance from the entry point in to the ISP). If more than one sub-stream with minimum PHC are available at a particular parent peer, then the sub-stream with shorter overall hop count (OHC) is selected. This scheduling scheme is invoked periodically (e.g., once per Δ second) at each internal peer.

p-0060The Intra-ISP scheduling and the inter-ISP scheduling have been described above upon the assumption that all connection have the same bandwidth. However, both intra-scheduling and inter-scheduling may have to deal with the dynamics of peer participating (or churn) and short and long term in variation of congestion controlled bandwidth across different connections.

p-0061In another embodiment, each edge peer identifies non-designated sub-streams if the edge peer has bandwidth above a bandwidth threshold. For example, non-designated sub-streams are sub-streams that have not been assigned to a connection, which imply that the non-designated sub-streams have not been requested by their corresponding edge peer or regular peer. On the other hand, each edge peer is responsible for requesting a particular sub-stream from its external parent peer which is called a designated sub-stream. Among the non-designated sub-streams, an edge peer identifies unavailable blocks of those sub-streams in its neighborhood and requests the unavailable blocks from its external parent peer in case of extra bandwidth.

p-0062Variations of the example embodiments of the present invention are not to be regarded as a departure from the spirit and scope of the example embodiments of the invention, and all such variations as would be apparent to one skilled in the art are intended to be included within the scope of this invention.