US20100094965A1 - Erasure-coded content assembly and retransmission - Google Patents

Abstract

Methods and systems for erasure-coded content assembly and retransmission, including assembling servers located at or close to edges of the Internet and spread over a wide area, fractional-storage CDN servers located close to or on the Internet backbone, and client devices spread over a wide area. Each assembling server obtains from the CDN servers erasure-coded fragments associated with segments of streaming content according to an order that enables the assembling server to start streaming the content to its associated clients shortly after reconstructing the first segment.

Description

CROSS-REFERENCE TO RELATED APPLICATIONS
• This application claims the benefit of U.S. Provisional Patent Application No. 61/105,683, filed Oct. 15, 2008.
BACKGROUND
• In computer networks, data may be transmitted directly between the source and destination servers, or transmitted via an intermediary server, such as a proxy server or a gateway server. When using a proxy server, a client connects to the proxy server, and requests data from the proxy server. The proxy server processes the request according to its rules, and may provide the data by requesting the data from a relevant server. The proxy server may modify the client's request or the server's response, and sometimes it may cache responses and provide the data without contacting the relevant server. Some distributed content delivery systems enhance performance by using erasure coding. However, obtaining and decoding the erasure-coded distributed content may require certain capabilities from an end user's device. These capabilities are considered non-standard, and may add complexity to end users' devices.
BRIEF SUMMARY
• In one embodiment, a streaming system comprising: assembling servers located at or close to the edges of the Internet and spread over a wide area, fractional-storage CDN servers located close to or on the Internet backbone, and client devices spread over a wide area; each assembling server is configured to obtain from the CDN servers erasure-coded fragments associated with segments of streaming content according to an order that enables the assembling server to start streaming the content to its associated clients shortly after reconstructing the first segment.
• In one embodiment, a apparatus comprising: an assembling server configured to obtain from fractional-storage CDN servers located close to or on the Internet backbone at least most of the erasure-coded fragments needed to reconstruct a segment of content comprising multiple segments; the assembling server is further configured to reconstruct the segment and transmit the reconstructed segment or a transcoded version of the segment to a client device.
• In one embodiment, a method comprising: receiving, by a first device from fractional-storage servers, erasure-coded fragments associated with segments of streaming content; reconstructing approximately sequential segments from fragments comprising the received fragments; and streaming the reconstructed segments or a transcoded version of the segments to a second device shortly after reconstructing the first segment; wherein the steps of receiving and streaming at least partially overlap in time.
• Implementations of the disclosed embodiments involve performing or completing selected tasks or steps manually, semi-automatically, fully automatically, and/or a combination thereof. Moreover, depending upon actual instrumentation and/or equipment used for implementing the disclosed embodiments, several embodiments could be achieved by hardware, by software, by firmware, or a combination thereof. In particular, with hardware, embodiments of the invention could exist by variations in the physical structure. Additionally, or alternatively, with software, selected functions of the invention could be performed by a data processor, such as a computing platform, executing software instructions or protocols using any suitable computer operating system. Moreover, features of the embodiments may be combined.
BRIEF DESCRIPTION OF THE DRAWINGS
• The embodiments are herein described, by way of example only, with reference to the accompanying drawings. No attempt is made to show structural details of the embodiments in more detail than is necessary for a fundamental understanding of the embodiments. In the drawings:
• FIG. 1 illustrates one embodiment of segmenting content, encoding the segments into erasure-coded fragments, distributing the fragments to fractional-storage servers, and obtaining the fragments by assembling devices and assembling servers.
• FIG. 2 illustrates assembling content utilizing a proxy server.
• FIG. 3 illustrates assembling content utilizing a proxy server.
• FIG. 4 is a flow diagram of one method in accordance with one embodiment.
• FIG. 5 illustrates fractional-storage servers located on the Internet backbone.
• FIG. 6 illustrates an assembling server located at a network juncture.
• FIG. 7 andFIG. 8 illustrate different embodiments of content segmentation.
• FIG. 9 illustrates distribution and storage of erasure-coded fragments on fractional-storage servers.
• FIG. 10 illustrates three examples of changes made to redundancy factors according to changes in demand.
• FIG. 11 illustrates an assembling device obtaining erasure-coded fragments from fractional-storage servers.
• FIG. 12 illustrates real-time content segmentation, encoding, and distribution.
• FIG. 13 illustrates real time fragment retrieval, segment reconstruction, and content presentation.
• FIG. 14 illustrates fast real time fragment retrieval.
• FIG. 15 toFIG. 18 illustrate various embodiments of fragment pull protocols.
• FIG. 19 illustrates various aggregated and non-aggregated fragment request messages.
• FIG. 20 illustrates retrieving fragments and compensating for failures.
• FIG. 21 illustrates fractional-storage servers having the same bandwidth capability.
• FIG. 22 illustrates fractional-storage servers having different bandwidth capabilities.
• FIG. 23 andFIG. 24 illustrate a case where a fractional-storage server has failed.
• FIG. 25 illustrates a server failure due to network congestion.
• FIG. 26 illustrates retrieving fragments according to locality.
• FIG. 27 illustrates a broadcast-like effect.
• FIG. 28 illustrates utilization of the entire aggregated bandwidth of fractional-storage servers for multiple content delivery.
• FIG. 29 toFIG. 31 illustrate changes in content consumption.
• FIGS. 32 to 34 illustrate retrieval and presentation of data objects pointed to by a master object.
• FIG. 35 illustrates HTML code comprising data object identification and a list of associated fractional storage servers.
• FIGS. 36 to 38 illustrate a system comprising fractional-storage servers, contact servers, and assembling devices operating to facilitate data objects retrieval and presentation.
• FIG. 39 illustrates a server array managing a pool of bandwidth amplification devices.
• FIG. 40 illustrates real-time content segmentation, encoding, and distribution.
• FIG. 41 illustrates boosting fractional-storage servers' bandwidth using P2P devices.
• FIG. 42 illustrates operation of hybrid pull and push protocols.
• FIG. 43 illustrates one embodiment of encoding content into erasure-coded fragments, distributing the fragments to fractional-storage servers, and obtaining the fragments from the fractional-storage servers.
DETAILED DESCRIPTION
• FIG. 1 illustrates one embodiment of a fractional-storage system storing erasure-coded fragments.Content100, which may optionally be streaming content, is segmented intocontent segments101a,101bto101j(for brevity referred to as segments). Each of the segments is encoded into erasure-coded fragments. For example,segment101ais encoded into erasure-codedfragments390ato390(N). The erasure-coded fragments are distributed to the fractional-storage servers399ato399(N) and/or to the bandwidth amplification devices610aa. The erasure-coded fragments are then obtained by assembling devices like661 or proxy servers likeproxy server661sfrom the fractional-storage servers399ato399(N) and/or the bandwidth amplification devices610aa. The obtained erasure-coded fragments are decoded to reconstruct the segments. Theproxy server661smay broadcast/multicast and/or re-stream the reconstructed content, optionally using standard streaming technique, to its client(s)6610, optionally overnetwork300n.
• In one embodiment,device6610 is a non-assembling Customer Premises Equipment (CPE), such as an STB, PC or gaming console, capable of performing standard request, reception, and decoding of video over IP network. In one embodiment,server661s—also referred to as proxy server, assembling server, and in some cases assembling device—performs three primary functions: (i) receipt of content requests fromnon-assembling client device6610; (ii) assembly of content, as requested byclient6610, from the fractional-storage servers and optionally from the bandwidth amplification devices; (iii) optionally, conversion of the assembled content into a streaming format; and (iv) transmission of the streaming content to the requesting client661o.Client6610 can then store the content, or present it. In one embodiment, the assembled content is a general web content, including HTML, FLASH or any other data format that can be found in a web-based site.
• In one embodiment, althoughserver661sis illustrated as being connected to network300 on one side and to network300non the other,server661smay also be connected to another network element, such as a router, which makes the topological connection betweennetworks300 and300n. In that case,server661scommunicates with bothnetworks300 and300nvia the other network element.
• Similarly tocontent100, additional contents are segmented, encoded into erasure-coded fragments, and distributed to the fractional-storage servers and/or to the bandwidth amplification devices. Each segment may be reconstructed independently of other segments by obtaining and decoding enough erasure-coded fragments generated from that segment.
• In some embodiments, the encoding scheme is erasure codes and/or rateless codes. In some embodiments, the fractional-storage servers399ato399(N) are Content Delivery Network (CDN) servers, optionally accessed over the public Internet. In some embodiments, the control, management, content reception, content segmentation, segment encoding, erasure-coded fragment distribution, allocation of bandwidth amplification devices, and/or other kind of central supervision and operation may be performed by managing server(s)393, which may be a part of the CDN network. It is noted that the term “fractional-storage server” is not limited to a large server and, according to the context, may include a fractional-storage bandwidth amplification device, a fractional-storage peer server, or other types of fractional-storage servers.
• The term “assembling device” as used herein denotes a computing device that retrieves erasure-coded fragments from servers over a network. The assembling device may perform one or more of the following: (i) Decode the retrieved erasure-coded fragments into segments. (ii) Present the content reconstructed from the retrieved erasure-coded fragments. (iii) Act as a bandwidth amplification device, by receiving, storing, and forwarding erasure-coded fragments. In some embodiments, the assembling device may be any device located at the user premises, like an STB, PC, gaming console, DVD player, PVR device, or any other device able to retrieve erasure-coded fragments from a communication network. In some embodiments, the assembling device may be an assembling server. In some embodiments, the assembling device may be any computational device with access to a communication network, located at a central office, data center, BRAS location, ISP premises, or any other place with direct network connectivity. In one embodiment, the assembling device is coupled to a display device used for content presentation.
• The abbreviation CDN denotes “Content Delivery Network”. The term “CDN server” as used herein denotes a server having one or more of the following characteristics: (i) A bandwidth (CDN_BW) that is much greater than the average bandwidth consumed by a user premises device (User_BW) receiving video streaming content. In some examples, the CDN_BW is at least 10 times, 100 times, 1,000 times, or 10,000 times greater than the User_BW. (ii) The server is located outside the last mile communication infrastructure of the end users, such that the CDN server and the end users are located in different networks. For example, the CDN server is not located under a BRAS, while the end users are located under a BRAS. Moreover, in some embodiments, the CDN servers are deployed over a wide area across the Internet and optionally located close to or on the Internet backbone. In some embodiments, the CDN server does not usually retrieve and play streaming content. In some embodiments, the CDN server has a much greater storage space than the storage space of an average player of streaming content.
• The term “fractional-storage server” in the context of erasure-coded fragments (also applicable to “fractional-storage CDN server”), as used herein denotes a server that (i) stores less than the minimum quantity of erasure-coded fragments required to decode the erasure-coded fragments, and (ii) where at least a meaningful quantity of the stored erasure-coded fragments is not stored in order to be consumed by the fractional-storage server.
• FIG. 2 illustrates one embodiment of assembling content utilizing a proxy server. Theclient6610 requests a specific content fromserver661s(both illustrated inFIG. 1).Server661sthen initiates a real time process of obtaining erasure-codedfragments720ato720(K) at time T1 and subsequent erasure-codedfragments730ato730(K) at time T2.Server661sthen decodes the erasure-coded fragments intosegments710a,710bat time T2band T4. The segments are then integrated into the original requestedcontent763 at time T5. Optionally, theintegrated content763 is made available to the next processes in real time, such that it aggregates segments at an average rate no lower than the rate of segment presentation, in order to keep the entire process in real time. Meaning that since T5, the content is available for continuous on-the-fly presentation, up to the end of the content being assembled. In one embodiment, fragments720ato720(K) and730ato730(K) are retrieved using a fragment pull protocol. In another embodiment, fragments720ato720(K) and730ato730(K) are obtained using a push protocol, wherein multiple sub-transmissions may be used to deliver the fragment sequences toserver661s.
• Optionally, at time T7,server661sstarts aprocess764 oftranscoding content763, optionally into a suitable format supported by the client661o, and then encapsulating the result into a streaming format to be delivered to client661o. This is done in real time, such that since T7, the content is ready to be streamed continuously up to the end of the content. Then, at time T8,content764 is streamed765 to client661o.
• In one embodiment,server661sis co-located with a Broadband Remote Access Server (BRAS). In one embodiment,server661sis located in a Central Office (“CO”) or in an Internet Exchange Point (“IX/IXP”). In one embodiment,server661sis: one ofservers399ato399(N), all or some ofservers399ato399(N) operating in the mode ofserver661s, an IP aggregation network, a last mile network, part ofnetwork300, and/or a private network. In one embodiment,network300nis an ISP network. In one embodiment,network300 belongs to one Internet backbone provider, andnetwork300nbelongs to a second Internet backbone provider. In one embodiment, some or all of clients610aaare connected to network300n, and not to network300. In one embodiment,client6610 requests and controls content interaction withserver661susing standard RTCP. In one embodiment,server661sstreams765content764 toclient6610 using standard RTP/RTSP. In one embodiment,server661sprogressively downloads765content764 toclient6610 using FLASH over TCP/IP.
• In one embodiment,client6610 interacts withserver661sas if the server stores the content locally. In this case, the server converts the standard stream control instructions, received from the client, to corresponding interactions with the fractional-storage CDN servers, and creates a corresponding stream. The instructions may comprise start-stop commands, and trick play commands.
• FIG. 3 illustrates one embodiment similar to the description ofFIG. 1 andFIG. 2, with the following emphasis and differences: (i) the fractional-storage servers399(a) to399(N) are mostly connected to network locations687(a) to687(N). These network locations are connected to theInternet300 on one side, and to operator's last mile networks300(a) to300(N) on the other. Examples of such locations include Central Offices, the location of a BRAS, the location of the last router that spans the last-mile aggregation network, the location at which the ISP is paying transit fees for data going/coming from the Internet on one side and is paying last-mile fees for data going/coming from the aggregation networks belonging to local Cable/Telco/PON/Wireless operators on the other side. (ii) Non-assembling clients661o(a) to661o(N) receive content services from the fractional-storage servers (each one optionally from the corresponding server connected to the corresponding aggregation network). As an example, non-assembling client661o(a) receives standard content streams from server399(a). The content for the non-assembling clients is assembled by the servers, such that each server is both a content assembler and content server (in one embodiment, these two functions can be separated into two different servers. In that case, the assembling part may also stream to the non-assembling clients). (iii) Optionally, some of the fractional-storage servers399(b) do not necessarily function as assemblers and streamers, and just function as erasure-coded fragment suppliers. These servers are not necessarily connected to locations687(a) to687(N). (iv) Assembling devices661(N) and669 do not have to use the assembling and streaming services of servers connected to locations687(a) to687(N) because they are able to assemble the content, with direct access to the fractional-storage servers399(a) to399(N). The non-assembling client and the assembling devices may all operate at the same time.
• Still referring toFIG. 3, in one embodiment, the operator of the fractional-storage servers pays only transit fees for data moving between elements of the fractional-storage system (in use by servers that assemble content for non-assembling clients) and transit fees for data moving between the servers and the assembling devices. No Internet transit fees are paid for streaming data moving from servers to non-assembling clients, since this traffic is contained within networks661o(a) to661(N), which belong to local operators, and not to Internet transit providers.
• FIG. 4 is a flow diagram illustrating one method, comprising the following steps: Instep7320, receiving, by a first device from fractional-storage servers, erasure-coded fragments associated with segments of streaming content. Instep7321, reconstructing approximately sequential segments from fragments comprising the received fragments. Instep7322, streaming the reconstructed segments or a transcoded version of the segments to a second device shortly after reconstructing the first segment; wherein the steps of receiving and streaming at least partially overlap in time. And inoptional step7323, receiving the fragments by the first device comprises receiving the fragments using a fragment pull protocol for high latency; and further comprising the second device interacting with the first device as if the first device stores the content locally; and the first device converting the interactions with the second device into corresponding interactions with the fractional-storage CDN servers. Optionally, the fractional-storage servers are fractional-storage CDN servers located close to or on the Internet backbone. Optionally, the erasure-coding is rateless-coding potentially resulting in fragments having a limitless redundancy factor; and receiving the fragments by the first device comprises receiving the fragments using a fragment pull protocol for high latency. Optionally, the interactions between the second device and the first device comprise requests to start streaming content and trick-play instructions.
• In one embodiment, a CDN is created by the aggregated bandwidth and storage capacity of the participating erasure-coded fractional-storage servers. In one example, a large scale CDN includes several hundreds or thousands of fractional-storage servers connected to the Internet. These servers send erasure-coded fragments to a large number, potentially millions, of assembling devices. In order to keep costs low for sending a large number of fragments from fractional-storage servers to assembling devices, the servers are located on the Internet backbone, or close to it.
• The current Internet backbone primarily comprises different Tier one ISP (or other) networks that interconnect at various Internet Exchange Points (IX or IXP), using peering agreements. Tier one ISPs, or other backbone-forming network entities, can reach any portion of the Internet via other Tier one ISPs or other backbone-forming networks, without paying any Internet transit fee, and solely by utilizing mutual peering agreements. In order to gain access to large amounts of inexpensive bandwidth, the fractional-storage servers are typically located on the Internet backbone. This means that the servers are either co-located (and connected) with a core switching router that interconnects the Internet backbone networks at an IXP, or, alternatively, co-located (and connected) with a router which is part of the backbone network, typically located at a data center or co-location center. Fractional-storage servers can also be located close to the Internet backbone, which means that they are co-located (and connected) with a router which is part of a Tier two ISP network, which has a high bandwidth connection with at least one Tier one operator, to which it pays transit fees in order to potentially reach all portions of the Internet.
• FIG. 5 illustrates one example of a fractional-storage server3001, which is one of a plurality of servers forming a large-scale CDN, located on the Internet backbone by being connected to the Internet backbone viaIXP3091. In a second example, fractional-storage server3002 is located on the Internet backbone by being connected to a Tier onebackbone network3080. In a third example, fractional-storage server3011 is located close to the Internet backbone by being connected to a Tier twoISP network3070, which is connected to the backbone via Tier oneISP network3081. In one embodiment, a typical fractional-storage server is located on the backbone or close to the backbone by being attached to a switching router via a high bandwidth port, such as a 1 Gbps, 10 Gbps, or a higher bandwidth port, such as high-speed Ethernet port, usually carried over a fiber, or suitable short-distance copper lines. In one embodiment, in a typical deployment using high bandwidth connections (in 2009 terms), each of about 1,000 fractional-storage servers is located on the backbone or close to the backbone and is connected to the backbone via a dedicated (guaranteed bandwidth) 1 Gbps Ethernet port, resulting in an aggregated throughput of 1,000 Gbps, which can serve about one million subscribers of standard definition streaming video, such asclient device3020, simultaneously. Such aggregated bandwidths would have required a substantially larger number of fractional-storage servers, had they been connected to other locations in the Internet, such as at edges of the Internet (close to last mile networks),Tier 3 ISPs, or at the user premises. Moreover, in some embodiments, the cost of streaming the mentioned 1,000 Gbps when the fractional-storage servers are located on the Internet backbone, or close to the Internet backbone, is expected to be significantly lower than what is expected when the servers are located elsewhere as mentioned before.
• FIG. 6 illustrates one example where an assemblingserver4020 is located at thejuncture4010 between two networks: the first network is anISP transit network4014 that connects the juncture to the Internet and provides Internet transit via aswitching router4015, and the second is alast mile network4041 that connectsend users4051 to the Internet via a switch4031 (located, for example, inside a Central Office, a Head-End, or a street-level cabinet). In one embodiment, thejuncture4010 is a network operated by a local ISP that pays transit fees for Internet traffic passing through thetransit network4014, and last mile fees for traffic passing through thelast mile network4041. A unique property of thejuncture4010 is that it is possible for an assemblingserver4020 located at the juncture to receive erasure-coded fragments sent by fractional-storage servers, such as4001 and4002, to assemble content, and to stream the content to aclient4051 via thelast mile network4041, without incurring any additional costs in comparison to other scenarios, such as where Internet packets flow from the Internet backbone to a Tier two ISP network to the Internet backbone and to the last mile network. In other words, since the assemblingserver4020 is located at the juncture, it does not create any extra traffic vianetworks4014 and4041. The assembling server can also be located at or close to an edge of the Internet, which may include the juncture, or a point aboveserver4015, such as at thetransit network4014 connecting the juncture to the Internet. When located at or close to an edge of the Internet, the assembling server has the potential not to incur additional transit fees as a result of the relaying operation, since approximately the same traffic would have to pass via the same transit network in a normal scenario. Another beneficial location for the assembling server is at the home premises, since, clearly, a relaying operation performed there does not add any significant traffic to higher levels of the network. In this case, and according to one example, the fragments pass through a network connecting the assembling server to its servicing ISP, and the reconstructed segments are streamed through a home network. In contrast to the above-suggested locations, in some cases an assembling server may be located at an arbitrary point on the backbone, or at other high-level points of the Internet, where it incurs additional transit fees, as fragments assembled by the server flow once over an Internet transit network going from a fractional-storage server to the assembling server, and then a second time when streamed by the assembling server to a destination client over an Internet transit network.
• In one embodiment, an assembling server communicates with a plurality of fractional-storage servers via the Internet on one hand, and with a client device on the other hand. The fractional-storage servers store erasure-coded fragments associated with several contents, such that each content can be completely reconstructed by assembling enough fragments. The assembling server may quickly reconstruct one of the contents, such that from the time it is knows which content to reconstruct, it takes the assembling server no more than several seconds to retrieve enough fragments and reconstruct the specific content. In one example, the assembling server is connected to the Internet via a guaranteed 10 Gbps line, such that it can completely retrieve a 1 GByte standard-definition movie file in approximately 1 [GByte]×8 [bits per byte]/10[Gbps]=0.8 seconds, plus at most 0.3 seconds communication latency=1.2 seconds. In this example, the assembling server communicates approximately in parallel with 1,000 fractional-storage servers (out of a possible several thousands), possibly using a pull protocol or using a push protocol (optionally implemented by multiple sub-transmissions), such that each of the selected 1,000 servers sends a unique 1 MBytes erasure-coded fragment to the assembling server. The entire reconstructed content occupies one segment, and the fractional-storage server needs to send only one erasure-coded fragment to the assembling server. Other configurations in which the content is segmented into multiple segments, and/or in which the 1 MBytes erasure-coded fragment includes many fragments are also possible. After quickly reconstructing the content, the assembling server may stream the 1 GByte content to a requesting client having approximately a 1 Mbps download link over a period of two hours. In the described embodiment, the assembling server quickly obtains a large file stored as multiple erasure-coded fragments over multiple fractional-storage servers, and, potentially, slowly transmits the reconstructed file to a client via a much slower connection than the connection used for assembling the content. In one embodiment, the client requests a file from the assembling server, the assembling server quickly obtains the requested file from fractional-storage servers, and briefly following the client's request (optionally a matter of seconds), starts streaming the newly obtained file to the requesting client. It is noted that the assembling server need not store the requested file internally, as it can quickly fetch it (or part/s of it) when needed. In the above example, the 1,000 fractional-storage servers share the bandwidth load of providing the requested file, such that each fractional-server sends a fragment, or several fragments, to the assembling server at a rate of approximately 10[Gbps]/1,000 [servers]=10 Mbps. The fractional-storage servers, as mentioned in the last example, may serve multiple assembling servers in parallel, each requiring a 10 Mbps bandwidth. In one example, the fractional-storage servers are fractional-storage CDN servers located close to or on the Internet backbone, each servicing dozens of assembling servers in parallel. The placement of the CDN servers close to or on the Internet backbone provides low cost and high bandwidth Internet transit.
• FIG. 43 illustrates one embodiment of a server array including fractional-storage servers399ato399(N) storing erasure-codedfragments390ato390(N) associated with content. In order for assemblingdevice661 to reconstruct the content, it has to retrieve from the N servers sufficient number of erasure-coded fragments, for example390a,390c,390mand390(N), which are noted asgroup574. If theassembling device661 cannot reconstruct the content, it retrieves one or more additional unique erasure-coded fragments, and tries again.
• The term “erasure coding” as used herein denotes a process in which a sequence of erasure-coded fragments can be generated from a segment such that the segment can be reconstructed from any or almost any subset of the erasure-coded fragments of size equal to or somewhat larger than the size of the segment (sometimes may be referred to as “enough erasure-coded fragments” or “sufficient subset of fragments”). Examples of erasure codes include, but are not limited to, rateless codes, Reed-Solomon codes, Tornado codes, Viterbi codes, Turbo codes, any Block codes, any Convolutional codes, and any other codes that are usually used for forward error correction (FEC).
• The term “rateless coding” as used herein denotes a type of erasure coding in which a very long, potentially limitless, sequence of rateless-coded fragments can be generated from a segment such that the segment can be reconstructed from any or almost any subset of the rateless-coded fragments of size equal to or somewhat larger than the size of the segment (sometimes may be referred to as “enough rateless-coded fragments”). Examples of rateless codes include, but are not limited to, Raptor codes, LT codes, online codes, any Fountain codes, and any other Rateless codes.
• The term “erasure-coded fragment” denotes a fragment comprising data encoded with an erasure code (which may also be a rateless code in some embodiments). The term “rateless-coded fragment” denotes a fragment comprising data encoded with a rateless code.
• The term “streaming content” as used herein denotes any type of content that can begin playing as it is being delivered. Streaming content may be delivered using a streaming protocol, a progressive download protocol, or any other protocol enabling a client to begin playing the content as it is being delivered. Moreover, the term “streaming protocol” includes “progressive download protocol”. In addition, the verb “streaming” refers to using a streaming protocol, using a progressive download protocol, or using any other protocol enabling the receiver to begin playing the content as it is being delivered.
• In some embodiments, expressions like “approximately sequential segments” may denote one or more of the following non-limiting options: segments that are sequential (in time or according to a file's order), segments that are approximately sequential (such as segments with some interlace, or segments without a great amount of non-sequential data), segments generated sequentially and/or approximately sequentially from different components of content (such as storing the i-frames and p-frames of a compressed content in different segments), and/or other sequential or approximately sequential segmentation after classification or separation into different components and/or elements.
• The term “redundancy factor” as used herein denotes the following ratio: (total size of the unique erasure-coded fragments generated from a segment and actually stored on the servers)/(size of the segment).
• Assuming all segments have approximately the same size and all fragments generated from the segments have approximately the same size (without limiting any of the embodiments), the term “storage gain” as used herein denotes the following ratio: (size of a segment)/(size of an erasure-coded fragment). If the server stores more than one erasure-coded fragment per segment, the storage gain denotes the following ratio: (size of segment)/((size of erasure-coded fragment)*(number of stored erasure-coded fragments per segment)).
• The term “approximately random” as used herein refers to, but is not limited to, random, pseudo random, and/or based on a long list of numbers featuring very low autocorrelation and very low correlation with other similar lists of numbers.
• In one embodiment, different quantities of erasure-coded fragments are generated per different segments. In one embodiment, some segments store data that is considered more important than data stored in other segments, and relatively more erasure-coded fragments are generated from the segments storing the more important data than from the segments storing the less important data.
• In one example, a compressed video content is segmented into segments storing i-frames and segments storing p-frames. Optionally, all segments are approximately of the same size, and more erasure-coded fragments are generated from the segments storing the i-frames than from the segments storing the p-frames. Alternatively, the segments storing the i-frames are shorter than the segments storing the p-frames, and approximately the same quantity of erasure-coded fragments are generated from the segments storing the i-frames and from the segments storing the p-frames.
• In one example, a DCT content is segmented into segments storing low frequencies and segments storing high frequencies. Optionally, all segments are approximately of the same size, and more erasure-coded fragments are generated from the segments storing the low frequencies than from the segments storing the high frequencies, where in addition, the size of the erasure-coded fragments generated from the segments storing the low frequencies is smaller than the size of the erasure-coded fragments generated from the segments storing the high frequencies. Alternatively, the segments storing the low frequencies are shorter than the segments storing the high frequencies, and approximately the same quantity of erasure-coded fragments are generated from the segments storing the low frequencies and from the segments storing the high frequencies.
• In some embodiments, the content is segmented into a plurality of segments to enable beginning to play the content as it is being obtained, and optionally enable trick play. The different segments may or may not be of the same size.
• The following embodiments discuss different methods for segmenting the content. In one embodiment, at least one portion of the content is segmented into multiple segments in sizes within a first size range, and the remainder of the content is segmented into a plurality of segments in sizes within a second size range (additional size/s may be added similarly). The sizes included in the second size are larger than the sizes included in the first size range. Pluralities of erasure-coded fragments are generated from each of the segments. The segments of sizes within the first size range are better suited for fast retrieval, and the segments of sizes within the second size range are better suited for high-gain storage. In one example, the segments in sizes within the first size range belong to approximately the beginning of the content. In one example, the segments in sizes within the first size range belong to locations within the content requiring trick play access. In one embodiment, the segments of the first type are encoded into fewer fragments than the segments of the second type. This allows a fast retrieval of the shorter segments.
• In one example, thecontent100 is a 1 GByte encoded H.264 file, storing a 2-hour motion picture, and is segmented into approximately 10,000 segments of approximately 100 Kbytes each. In another example, thecontent100 is a 4 MByte web-site information (HTML, FLASH, or any other combination of information that encodes the presentation of a website), and is segmented into 4 segments of approximately 1 MByte each.
• In one example, the content supports streaming presentation, and the segments are small enough to enable presentation shortly after beginning the reception of the first segment(s). For example, each segment may include 96 KByte, allowing a 5 Mbps receiver to download the segment in approximately 0.2 seconds, and optionally begin the presentation shortly thereafter. In one embodiment, the time to play is reduced by segmenting certain portions of the content into smaller segments, while the remaining portions are segmented into larger segments. A smaller segment can be retrieved faster, while a larger segment may be better optimized for storage gain and/or efficient transmission.
• In one embodiment, the short segments are 96 Kbytes in size, and the long segments are 960 Kbytes in size. The redundancy factors used for encoding short and long segments into fragments are 100 and 5 respectively. 1500 Bytes fragments are used for both sizes. The short segments are therefore encoded into (96K/1500)×100=6,400 fragments, from which only about 64 are needed for reconstruction, and the long segments are encoded into (960K/1500)×5=3,200 fragments, from which only about 640 are needed for reconstruction. Short segments are reconstructed more quickly than long ones, as they require fewer fragments to be decoded. Optionally, each fragment is stored on a different server, resulting in a storage gain of64 for short segments, and 640 for long segments.
• FIG. 7 illustrates one example in which thecontent100 is segmented into segments, such that thefirst segment104ais smaller than theconsecutive segment104b, which is smaller than followingsegments104cand104d. In another example, thecontent100 is segmented into segments, such that the first several segments (e.g.104aaand104bb, which are the same size), are smaller than consecutive segments (e.g.104 cc and104dd, which are the same size).
• FIG. 8 illustrates one example in which thecontent100 is segmented into cyclic sets of successive segments increasing in size. For example,105bis equal or larger in size than105a, and so on, up tosegment105d;105fis equal or larger in size than105e, and so on, up tosegment105h. In one example,segment105eis equal in size tosegment105a. Point105EP represents the ending of the first set, and the beginning of the second set.
• In one embodiment, some of the content is segmented approximately sequentially, and the rest non-sequentially. For example, dividing the beginning of a video content sequentially in time, and the rest of the video content non-sequentially in time.
• In one embodiment, a scalable, secured, moderate storage space, and durable wide-area storage system is achieved by erasure-encoding the content, then chopping the encoded content into a plurality of erasure-coded fragments, and then distributing the erasure-coded fragments to the fractional-storage servers. In this embodiment, the retrieving clients may retrieve the stored erasure-coded fragments using their maximum incoming bandwidth until approaching the server's aggregated bandwidth, the content may be any type of data file, and the chopping may be performed according to any reproducible method.
• In one embodiment, segments are created on-the-fly, such as during a live event or when the content is made available to the segmentation process as an on-going stream. In one embodiment, the content supports streaming presentation, and the segments are of the small size, to enable content presentation shortly after beginning the reception of the first segment (or any other segment). In addition, the erasure-coded fragments are kept as small as possible, while still enabling efficient transport over an IP network. For example, each erasure-coded fragment is about 1500 Bytes and can be transported using one IP packet.
• It is to be noted that streaming content may also be manifested as an intermediate product of a process. For example, in a case where a video camera outputs erasure-coded fragments that can be decoded into streaming content, the intermediate data from which the erasure-coded fragments are generated is considered to be streaming content (even if the video camera does not output that intermediate data). Moreover, streaming content may include: content that is produced and then immediately transmitted to a receiving server, content that is produced but stored for any length of time before being transmitted to a receiving server, content that is transmitted to a receiving server and then immediately sent from the receiving server to a client, content that is transmitted to a receiving server, then buffered for some time at the receiving server and then sent from the receiving server to a client, content that is solely played at a client, and content that is manipulated or changed or reacted to at the client while a continuation of the content is still being played at the client.
• FIG. 9 (without the fragments marked with dashed lines) illustrates one example of distributing the erasure-coded fragments to ‘M’CDN servers399ato399(M), connected to anetwork300. Encodedfragments310ato310(M) of a first segment are sent for storage inservers399ato399(M) respectively. Similarly, erasure-codedfragments320ato320(M) of a second segment are sent for storage inservers399ato399(M) respectively. In addition, other erasure-coded fragments associated with other segments of other contents, illustrated as erasure-codedfragments390ato390(M), are sent for storage inservers399ato399(M) respectively. The number of unique erasure-coded fragments from each segment that are stored on the servers (399ato399(M)) is equal to M in this example, where M may be smaller than the maximum number of unique erasure-coded fragments, meaning that only a subset of the potential erasure-coded fragments are actually stored. It is also possible to store the maximum number of unique erasure-coded fragments, or store more than one unique erasure-coded fragment per segment per server. Thenetwork300 may be the Internet for example, or any other data network connecting multiple nodes, such as a private IP network, or a Wide Area Network (“WAN”). In one embodiment, the fragments marked with dashed lines illustrate one example where (N−M) additional servers are added to the array, and (N−M) new unique erasure-coded fragments per segment per content (310(M+1) to310(N),320(M+1) to320(N), and390(M+1) to390(N)) are generated and added to the array. In one embodiment, only M out of the maximum possible erasure-coded fragments (L) are actually generated for storage in the first place. In one embodiment, when the additional N-M erasure-coded fragments are needed for storage (e.g., when additional servers are made available), the remainder of the N-M erasure-coded fragments are actually generated. Any time that additional unique erasure-coded fragments are needed, this process of calculating the additional erasure-coded fragments is repeated, up to the point that all L possible erasure-coded fragments are used.
• In one embodiment, and especially when using rateless coding, L may be chosen as a sufficiently large number to account for any realistic future growth of the server array. For example, a segment of 96 Kbytes is expanded using a rateless code with a ratio of 1 to 2̂16 original symbols to encoded data, into an encoding symbol of potential size 6.29 GBytes. Assuming a 1500 Bytes erasure-coded fragment size, then potentially 4.19 million unique erasure-coded fragments can be generated. Now, it is safe to assume that for all practical uses, the server array will not grow to more than 4.19 million nodes, and may contain several thousands of servers, meaning that the encoded data can be used in all cases where additional unique erasure-coded fragments are needed, by generating new erasure-coded fragments out of the segment. Optionally, a server may store erasure-coded fragments for only some of the segments.
• In one example of redundancy factor and storage gain (without the fragments marked with dashed lines),server399astores only erasure-codedfragment310afrom a first segment, erasure-codedfragment320afrom a second segment, and erasure-codedfragment390afrom a third segment. Assuming that: (i) the segment size is 1024 Kbytes; (ii) the segment is encoded using erasure code into a 4096 KByte encoded segment; (iii) the encoded segment is segmented into 256 erasure-coded fragments of size 4096/256=16 KByte; and (iv) the erasure-coded fragments are stored on 256 servers (M=256); it turns out that each server stores only a 1/64 portion of the original size of the segment. This means that each server can manage with only 1/64 of the storage requirements in comparison to a situation where it had to store the entire segment. In addition, there are 256 erasure-coded fragments altogether from each encoded segment, meaning that an assembling device that is assembling the erasure-coded fragments from the servers need only select slightly more than 64 erasure-coded fragments in order to completely reconstruct the segment, and it can select whichever slightly more than 64 erasure-coded fragments it desires out of the 256 possibly available. The redundancy factor in this example is approximately 256/64=4. All contents in this example enjoy a factor of 64 in storage gains, meaning thatserver399a, for example, stores only 1/64 of the information associated with the first segments and any additional segments belonging to other contents. In one example, each server supports high volume storage of between about 500 GByte and 500 TBytes, optionally utilizing hard drive, Solid State Drive, or any other high volume storage device(s). In these cases, each server may store many millions of erasure-coded fragments, associated with millions of segments, belonging to hundreds of thousands of different contents, and possibly more.
• In one embodiment, new content initially encoded with a low redundancy factor is distributed to an initial number of fractional-storage servers. As the content is distributed to more servers, additional unique fragments are encoded and therefore the redundancy factor increases. Optionally, as the content's popularity increases, and/or as the load on the fractional-storage servers increases, the redundancy factor is increased, and vice versa.
• In one embodiment, multiple unique erasure-coded fragments per segment of a new content are distributed to an initial number of fractional-storage servers with a low storage gain (i.e. each server stores multiple unique erasure-coded fragments per encoded segment). As the content is distributed to more fractional-storage servers, some of the erasure-coded fragments stored on the initial number of fractional-storage servers are removed and thereby the storage gain is increased. Optionally, as the demand for the content increases, the storage gain is decreased, and vice versa.
• FIG. 10 illustrates three examples (each depicted by one of the columns A-C) of changing the redundancy factor according to the demand. Column A illustrates one simplified example of a storage array including 16 servers (1001 to1016). Each server stores up to 2 different erasure-coded fragments, and can service an erasure-coded fragment transmission bandwidth of up to B. Assuming three contents (#1, #2, and #3) processed to segments and erasure-coded fragments with a storage gain of 4.
• Assumingcontent #1 is the most popular, and requires a peak bandwidth of 11×B. Since each server can service up to bandwidth B, at least 11 servers are needed to servicecontent #1 bandwidth requirements.Content #1 is therefore encoded into 11 unique erasure-coded fragments per segment, illustrated as group g1 of erasure-coded fragments stored onservers1001 to1011. Out of these 11 erasure-coded fragments, it is sufficient to obtain slightly more than 4 erasure-coded fragments in order to reconstruct a segment ofcontent #1. Therefore, the resulting redundancy factor of the stored fragments associated withcontent #1 is approximately 11/4=2.75.Content #2 requires less bandwidth, and manages with a peak of 7×B. It is therefore encoded into 7 unique erasure-coded fragments per segment, illustrated as group g2 of erasure-coded fragments onservers1010 to1016. Therefore, the redundancy factor of the stored fragments associated withcontent #2 is 7/4=1.75.Content #3 requires a peak bandwidth of 5×B, but for some reason (for example, being a more critical content), it is encoded into 14 erasure-coded fragments per segment, illustrated as group g3 of erasure-coded fragments onservers1001 to1009 and1012 to1016. Therefore, the redundancy factor of the stored fragments associated withcontent #3 is 14/4=3.5. This concludes the storage availability of the servers in this example, as every server stores two erasure-coded fragments.
• Column B illustrates an example wherecontent #2 becomes more popular thancontent #1, and therefore requires more bandwidth and hence more of a redundancy factor. This is achieved by eliminating5 erasure-coded fragments associated withcontent #1 that were previously stored onservers1001 to1005, and replacing them with 5 new unique erasure-coded fragments g4 associated withcontent #2. This brings the total number of erasure-coded fragments per segments ofcontent #1 and #2 to6 and12 respectively. In column C,new content #4 is stored onservers1001 to1003 and1014 to1016 (illustrated as g5), by eliminating3 erasure-coded fragments ofcontent #1 and3 erasure-coded fragments ofcontent #2.
• Throughout the examples ofFIG. 10, a record of “what erasure-coded fragments are stored where” may be: (i) kept in each of theservers1001 to1016. In this case, when an assembling device is assemblingcontent #2, it will send a query toservers1001 to1016, asking which one is storing erasure-coded fragments ofcontent #2; (ii) kept in a control server. In this case, an assembling device will ask the control server to send back a list of all servers storing erasure-coded fragments of its required content.
• FIG. 11 illustrates one embodiment of a server array including fractional-storage servers399ato399(N) storing erasure-codedfragments390ato390(N) associated with content. In order for assemblingdevice661 to reconstruct asegment101aof the content, it has to retrieve at least K erasure-coded fragments. In one example, k=4 and theassembling device661 chooses approximately randomly from which servers to retrieve the 4 different erasure-coded fragments. It chooses to retrievefragments390a,390c,390(N−1) and390(N), which are noted asgroup573, and reconstruct thesegment101a. Consequent segments of the content are reconstructed in a similar fashion, and the content may eventually be fully retrieved by combining all relevant segments. If theassembling device661 cannot reconstruct thesegment101a, it retrieves one or more additional unique erasure-coded fragments, and tries again.
• In one embodiment, the content being distributed supports stream presentation, andsegment101ais of small size, to enable content presentation by assemblingdevice661 shortly after beginning the reception of the segment (or any other segment of the content). For example,segment101ais 96 KByte, allowing a 5 Mbps download speed receiver to obtain the entire segment (by requesting enough erasure-coded fragments to enable the reconstruction of the segment, and such that the total size received of all requested erasure-coded fragments is slightly larger than the segment) after approximately 0.2 seconds from request, and beginning the presentation shortly or right after the successful decoding and reconstruction ofsegment101a.
• In some embodiments, the fragments are small enough to be contained in one packet. In one embodiment, each fragment is about 1400 bytes, and can fit into one UDP or RTP packet transmitted over Ethernet. The stateless nature of UDP and RTP allows the servers to send one packet with one fragment very quickly, without the need for any acknowledgement or hand shaking. In some embodiments, the fragment pull protocol requests use one stateless packet, like UDP or RTP. In one embodiment, the assembling device requests about 100 fragments approximately in parallel, using 100 separate requests or one or few aggregated requests. About 100 servers respond by sending about 100 fragments, each encapsulated in one stateless packet, after a short delay, and the assembling device receives the fragments within a fraction of a second. Assuming an Internet round trip delay of 100 ms, and server processing latency of 100 ms, then after 200 ms the assembling device starts receiving all 100 fragments. With a modem of 5 Mbps, and assuming 1400 bytes per fragment, all 100 fragments are received 1400×100×8/5 Mbps=224 ms after the initial delay, meaning that content can be presented200+224=424 ms after request (decoding and other process time has been ignored in this example).
• The following embodiments describe processes for on-the-fly erasure-coded fragment retrieval from fractional-storage servers.
• In one embodiment, a method for obtaining erasure-coded fragments from fractional-storage servers to reconstruct a segment includes the following steps: (i) identifying the next segment to be obtained; optionally, the segments are approximately sequential segments of streaming content obtained according to their sequential order; (ii) optionally, determining the minimum number of fragments needed to reconstruct the segment; (iii) are enough identified relevant servers (i.e. servers storing the required fragments) available from the process of obtaining prior segment/s? (iv) if no, identifying enough relevant servers; (v) if yes, requesting enough fragments from the identified relevant servers; if less than enough fragments are obtained from the identified relevant servers, go back to step iv and identify additional relevant server/s; (vi) reconstruct the segment from the obtained fragments; and (vii) optionally, go back to step i to obtain the next segment.
• In one embodiment, a method for obtaining erasure-coded fragments from fractional-storage servers to reconstruct multiple segments includes the following steps: (i) identifying multiple segments to be obtained, optionally according to their sequential order; (ii) optionally, determining the minimum number of fragments needed to reconstruct the segment; (iii) optionally, determining the number of fragments to be obtained approximately in parallel; (iv) are enough identified relevant servers available from the process of obtaining prior segment/s? (v) if no, identifying enough relevant servers; (vi) if yes, requesting enough fragments from the identified relevant servers, optionally in parallel and according to the sequential order of the segments; (vii) if less than enough fragments are obtained from the identified relevant servers, go back to step iv and identify additional relevant server/s; (viii) reconstructing the segment/s from the obtained fragments; and (ix) optionally, go back to step i to obtain the next segments.
• In one embodiment, a method for obtaining erasure-coded fragments from fractional-storage servers to reconstruct a segment in a burst mode includes the following steps: (i) identifying the next segment to be obtained; (ii) optionally, determining the minimum number of fragments needed to reconstruct the segment; (iii) are more than the minimum number of relevant servers available from the process of obtaining prior segment/s? (iv) if no, identifying more than the minimum relevant servers; (v) if yes, requesting more than the minimum number of fragments needed to reconstruct the segment; if less than enough fragments are obtained, go back to step iv and identify additional relevant server/s; (vi) reconstructing the segment from the obtained fragments; and (vii) optionally, go back to step i to obtain the next segment.
• The various methods for obtaining erasure-coded fragments from the fractional-storage servers for reconstructing one or more segments may be combined as needed. In one example, the initial segment/s are obtained using a burst mode and the following segments are retrieved without requesting extra fragments. In another example, the initial segment/s are obtained approximately in parallel and optionally using a burst mode, and the following segments are obtained one by one and optionally without requesting extra fragments. The fragments may be obtained using a pull protocol and/or a push protocol. Moreover, the servers from which to retrieve the fragments may be selected according to one or more of the various discussed methods for selecting the servers and/or load balancing the servers.
• In some embodiments, a push protocol is used to obtain fragments. A push protocol may be implemented using one transmission carrying fragments from a source server to a destination receiver, or may be implemented using a plurality of sub-transmissions. When using sub-transmissions, each sub-transmission transports a fraction of the fragments needed for segment reconstruction. Segments may be reconstructed from fragments received via sub-transmissions after obtaining decodable sets of erasure-coded fragments; optionally one set per segment. A sub-transmission may be transported using an IP stream such as RTP, an HTTPS session, or any other protocol suitable for transporting a sequence of fragments between a source server and a destination assembling device.
• FIG. 11 illustrates one embodiment, in which content is segmented and erasure-coded.Fragments390ato390(N), belonging to a first segment, are distributed toservers399ato399(N) respectively. Other fragments belonging to subsequent segments are similarly distributed toservers399ato399(N). The servers may use a push protocol to transport the fragments to an assembling device. A push protocol sub-transmission may comprise a sequence of fragments associated with multiple segments. In one example, the fragments are ordered according to the sequential order of the segments in a streaming content.Server399asends a first sub-transmission to a destination assembling-device. Optionally, the first sub-transmission comprises a sequence of fragments starting withfragment390a, associated with the first segment, and continuing with fragments belonging to subsequent segments.Server399csends a second sub-transmission to the destination assembling-device, optionally starting withfragment390c, associated with the first segment, and continuing with fragments belonging to subsequent segments. In a similar fashion, servers399(N−1) and399(N) send additional sub-transmissions to the destination assembling-device, each comprising a unique fragment sequence.
• When using a push transmission, the assembling device does not explicitly ask for each fragment, but instead instructs each of the different servers to start sending it a fragment sequence using a sub-transmission. The destination assembling-device receives the sub-transmissions sent byservers399a,399c,399(N−1) and399(N). It gathers573 the first fragment from each sub-transmission to reconstruct thefirst segment101a. In a similar fashion, additional fragments belonging to subsequent segments are obtained from the sub-transmissions, and used to reconstruct the segments. It is noted that any combination of sub-transmissions may be used, as long as a decodable set of fragments is obtained per each segment. It is also noted thatFIG. 11 illustrates a non-limiting embodiment and a sub-transmission may include two or more unique erasure-coded fragments per segment.
• In one embodiment, the push sub-transmissions is synchronous (all servers sending the fragments of each segment at approximately the same time). In another embodiment, the push sub-transmission is asynchronous and the arrival of different fragments associated with a specific segment at the assembling device side may be spread over a long period. This may occur, as an example, when some push servers are faster than others. In one embodiment using asynchronous sub-transmissions, the assembling device aggregates whatever fragments it can before presentation time of each segment, and then optionally supplements fragments using a pull retrieval process. A server that does not send fragments fast enough, and therefore usually causes supplemental requests, may be ordered to stop the sub-transmission. Another server may be requested, optionally by the assembling device, to replace the slow server by initiating a new sub-transmission.
• In one embodiment, the push-transmissions carry more erasure-coded fragments than needed for segment reconstruction. In one embodiment, the push transmissions carry fewer erasure-coded fragments than needed for segment reconstruction, and the remaining fragments are pulled by the assembling device.
• In some embodiments, a broadcast-like effect is achieved by distributing to and retrieving from fractional-storage servers a broadcast channel/live content in real time, using a combination of real time distribution and real time retrieval techniques. In a broadcast-like effect, a given channel or content for broadcasting is distributed to at least one assembling device, optionally by means of pushing relevant fragments to the assembling device, or by pulling the relevant fragments by the assembling device, and potentially to many assembling devices at approximately the same time, which creates a similar effect to traditional broadcasting.
• FIG. 12 illustrates one embodiment of processing acontent source700 for real time presentation. Content examples include, but are not limited to, a live video broadcast event, a pre-recorded show, or any real time conditioned source. Thecontent700 is available at time T1=0. Thecontent700 is segmented in real time into multiple segments, such that thefirst segment710ais available at T3. T3 is determined by the size of the segment and the selected compression scheme. For example, if an H.264 compression is used to generate an average stream of 1 Mbps, and the size of the segment is 96 Kbytes, then T3 minus T2 equals 96 KByte ×8(Bits/Byte)/1 Mbps=0.77 seconds on average, where T2 is the process delay. If T2 is about 0.2 second, then thefirst segment710acan be ready for the next step after about 1 second from the time thatcontent700 is first made available.Subsequent segments710bto710J are made available sequentially in time.
• Next, at T4, erasure-codedfragments720ato720(N) are being encoded fromsegment710a. At T6, the encoding process is performed forsegment710a, and all the erasure-codedfragments720ato720(N) are made available. In one example, the time between T4 and T6 is equal to or less than the average segment creation time, in order to allow the process to maintain real time performance, such that at any point in time during the on-going availability of segments, the encoding process generates all erasure-coded fragments without picking up any delay above T6 minus T3 (which is the latency between segment availability and erasure-coded fragment availability). T6 minus T1 may be typically 2-3 seconds if T3 minus T2 is 0.77 seconds. T4 minus T3 may be typically a fraction of a second. Similarly, erasure-codedfragments730ato730(N) are being encoded fromsegment710b, and are made available at time T9. The process of fragment encoding is repeated in real time up to thelast segment710J ofcontent700.
• Next, at T5 (which can potentially occur before T6, but also after T6) the erasure-codedfragments720ato720(N) are distributed740ato a server array. Thedistribution process740aends at T8. In one example, T8 minus T5 is equal to or less than the average segment creation time, in order not to have delays. The process of distributing the erasure-coded fragment is repeated740bfor erasure-codedfragments730ato730(N), and for all subsequent erasure-coded fragments associated with the next segments.
• Optionally, at T7, the erasure-codedfragments720ato720(N) are distributed750afrom the servers to groups of bandwidth amplification devices. In one example, the distribution ends at T10, such that T10 minus T7 is equal to or less than the average segment creation time, in order not to have delays. Subsequent erasure-coded fragments associated with the next segment are distributed750b, and the process continues until the erasure-coded fragments associated with thelast segment710J are distributed.
• FIG. 13 illustrates one embodiment of real time streaming content retrieval from fractional-storage servers. An assembling device begins a process of obtainingstreaming content700 for presentation. Starting at T1, the assembling device requests erasure-codedfragments720ato720(K). By T2, all K erasure-coded fragments are obtained, and at time T2buntil T4, erasure-codedfragments720ato720(K) are decoded intosegment710a. The retrieval time of the erasure-coded fragments and the segment decoding time should be equal to or faster than the corresponding presentation time, in order to enable a continuous presentation, once presentation begins at T5. T2bminus T2 is a short delay, and can be fractions of a second. Subsequent erasure-codedfragments730ato730(K) are retrieved between T2 and T3, and are decoded intosubsequent segment710bbetween T4 and T6.
• In one example, the streamingcontent700 is encoded at 1 Mbps, and the segment size is 96 Kbytes. The presentation of each segment takes about 0.77 seconds. Retrievingfragments720ato720(K) takes no more than 0.77 seconds, meaning that the assembling device's connection bandwidth must be 1 Mbps or higher. Decodingsegment710atakes no more than 0.77 seconds. If a small delay of 0.2 seconds is assumed for both T2bminus T2 and T5 minus T4, then T5 can start at 0.77+0.2+0.77+0.2=1.94 seconds after T1, meaning that presentation can begin about 2 seconds following request of the first erasure-coded fragment. In another example, the retrieval process and the decoding process are performed faster than the real time presentation bounds, therefore enabling a shorter time to play and a download rate that exceeds the presentation rate.
• In one embodiment, the erasure-codedfragments720ato720(K) are retrieved in approximately random order, or any other order, as long as at least the K erasure-coded fragments needed for decoding thesegment710aare available until time T2.
• In one embodiment, the fragments associated with sequential segments of streaming content are delivered to an assembling device as a plurality of sub-transmissions. In this case, each fractional-storage server participating in the delivery of the fragments to the assembling device sends a transmission to the assembling device comprising a sequence of erasure-coded fragments. This transmission is referred to as a sub-transmission. In one example, each sub-transmission contains at least one fragment per each sequential segment of the streaming content. In one example, the sub-transmission starts at a segment indicated by the assembling device, and continues from that point onwards, approximately according to the sequential order of segments, until the assembling device instructs the server to stop, or until reaching the last segment of the content. Each sub-transmission carries only a fraction of the fragments (per segment) needed to reconstruct the segments of the streaming content, such that the combination of at least two sub-transmissions received by the assembling device from the servers allows the assembling device to obtain enough fragments needed to reconstruct each segment.
• In one embodiment, each sub-transmission is delivered to the assembling device via a streaming session, such as an RTP session, wherein the RTP packets transport the fragment sequence approximately according to the order of the sequential segments. In one embodiment, each sub-transmission is delivered to the assembling device via an HTTP connection, or other closed-loop data transfer mechanisms over TCP/IP. In one embodiment, the assembling device may change one or more transmitting servers on the fly, by instructing the server(s) to stop sending an already active sub-transmission—as may be needed in a case of an RTP session, and initiating new sub-transmissions from other servers instead. Replacement of transmitting servers on the fly may be needed in a case of a server failure, network failure, or high load or latency conditions.
• In one embodiment, a distributed system is located in a few to dozens of data centers (also known as server farm or datacenter), located close to or on the Internet backbone, together housing at least 100 fractional-storage CDN servers. The servers store erasure-coded fragments associated with approximately sequential segments of streaming contents, with a storage gain of at least 5, and transmit the stored fragments on demand to assembling devices approximately according to the sequential order of the segments. In many cases, the data centers provide a convenient place to place the CDN servers close to or on the Internet backbone. A data center can be also a collocation center, or an Internet Exchange Point. In one example, a single data center can house many fractional-storage CDN servers.
• In one example, a streaming system comprising at least several hundreds of fractional-storage CDN servers located close to or on the Internet backbone, storing erasure-coded fragments encoded with a redundancy factor greater than one, and associated with approximately sequential segments of streaming contents. At least 100,000 assembling devices concurrently obtain fragments from the CDN servers, wherein the system achieves efficient load balancing and fault tolerance between the various CDN servers by determining for each of the assembling devices from which servers to obtain the fragments.
• In one example, a system comprising at least 1,000 fractional-storage CDN servers is connected to the public Internet. The servers store erasure-coded fragments associated with approximately sequential segments of streaming contents, with a storage gain greater than 5, and transmit the stored fragments on demand to assembling devices approximately according to the sequential order of the segments. Wherein the aggregated bandwidth utilized by the servers for transmitting the fragments to the assembling devices exceeds 1 Giga bit per second times the number of the CDN servers. In one optional example, the system comprises at least 10,000 fractional-storage CDN servers and the aggregated bandwidth utilized by the servers exceeds 10 Giga bit per second times the number of the CDN servers.
• FIG. 14 illustrates one embodiment of real time streaming content retrieval from fractional-storage servers, wherein erasure-codedfragments720ato720(K) are retrieved in a fast cycle, meaning that several erasure-coded fragments are obtained approximately in parallel. As a result, the interval T2 minus T1 is more or less limited only by the download bandwidth of the assembling device's modem. Referring to the example ofFIG. 13, T2 minus T1 can be reduced from 0.77 seconds to 0.15 seconds, if the modem operates at 5 Mbps (instead of 1 Mbps).
• In one embodiment, T1 to T2 represents a fragment fetch cycle that corresponds to the beginning of streaming content to be presented (in that case,segment710ais the first segment of the content, andpresentation700 corresponds to the beginning of the streaming content), or corresponds to a certain point within the streaming content to be presented starting this point onwards (in that case,segment710ais a segment within the content, andpresentation700 corresponds to playing the content starting not from the beginning, but rather fromsegment710a, located somewhere within the content). This is also known as trick play. In one embodiment, erasure-coded fragments720(a) to720(K) are obtained such as to result in approximately a maximum utilization of the download capabilities of the assembling device, and such that the rate of requesting erasure-coded fragments results in a data arrival rate that on average utilizes the assembling device's maximum download bandwidth.
• FIG. 15 illustrates one embodiment of a fragment pull protocol. Assembling device861 (also represented byprotocol diagram element810b) obtains erasure-coded fragments from fractional-storage servers899ato899(N) (also represented by protocol diagram element898), utilizing the following steps: (i) deciding810awhich segment to retrieve; (ii)device861 sending requests to some of the fractional-storage servers for erasure-coded fragments associated with the desired segment. For example, requests880ato880(K) for erasure-codedfragments890ato890(K), from servers899(a) to899(K), correspondingly; and (iii) the servers respond by sending the requested erasure-coded fragments. For example,servers899ato899(K) send881ato881(K) erasure-codedfragments890ato890(K) todevice861. The fragment request and receipt process begins at T1cand ends at T1d. At time T1d,device861 has enough erasure-coded fragments (K) to reconstruct the segment selected at810a. In one embodiment, the process from T1cto T1doccurs in real time, in support of streaming content presentation.
• FIG. 16 illustrates a similar process toFIG. 15, whererequest890bfails to result in a reception of erasure-codedfragment890bfor any reason (such as a server fault, network congestion, or abnormal latency conditions). Assemblingdevice861 therefore issues another request882(K+1) for erasure-coded fragment890(K+1) in response, and receives883(K+1) the additional erasure-coded fragment890(K+1) needed to reconstruct the segment.
• FIG. 17 illustrates a similar process toFIG. 15, where one or more extra erasure-coded fragments (in addition to the needed K) are requested in advance (illustrated as request880(K+1) for erasure-coded fragment890(K+1)), such that if, as an example, request890bfails to result in a reception of erasure-codedfragment890b, assemblingdevice861 does not have to request new erasure-coded fragments to reconstruct the segment, since there are still at least K erasure-coded fragments that were successfully received and therefore the segment can be reconstructed.
• In one embodiment, more fragments than needed to reconstruct a segment are requested, such that the additional requested fragments approximately compensate for fragment failure conditions. If, statistically, F fragment requests are expected not to result in the reception of a fragment (i.e. fragment loss), out of a total number of K+F fragment requests (wherein K is the minimal number of fragments needed to reconstruct a segment), then it is possible to request K+F fragments instead of just K. In one embodiment, more than K+F fragments are requested, since the quantity of the received fragments is a statistical variable. In this case, K+F+S fragments are requested, wherein S is a safeguard amount of additional requests to assure that at least K fragments are received. In one embodiment, the fragment loss F changes over time, and the assembling device handles the change by increasing or decreasing the number of fragments requested per segment. In one embodiment, the assembling device may determine F based on previous fragment failure rates.
• FIG. 18 illustrates a similar process toFIG. 15, where requests for erasure-coded fragments are loaded into one aggregatedrequest870, that is sent to one of the fractional-storage servers (the receiving server is illustrated asprotocol diagram element888a, and will be also referred to as a “relay server”). In one example, if the relay server is899(N), then, it will forward the request toadditional servers899ato899c(protocol element888b) vianew requests870ato870c(on behalf of assembling device861).Servers899ato899cwill then respond by sending the erasure-codedfragments890ato890c(871ato871c) to theassembling device861. Server899(N) will send871(N) fragment890(N) to the assembling device.
• The term “fragment pull protocol for high latency” as used herein denotes a protocol enabling an assembling device to request one or more fragments from one or more providing sources, wherein the time to transmit the one or more fragments in response to the assembling device request, through the slowest communication link connecting the responding source and the assembling device, is smaller than the round trip communication delay between the assembling device and the responding source, excluding the processing time of the providing source. For example, if the round trip communication delay between Israel and the USA is about 200 ms, the assembling device requests one fragment sized about 1500 bytes, and the slowest communication link is an ADSL line connecting the assembling device at 1.5 Mbps, then the time it takes to transmit the requested fragment through the slowest communication link is about 1500*8/1500000=8 ms, which is much smaller than the round trip delay. Many of the disclosed embodiments using fragment pull protocol may use fragment pull protocol for high latency for retrieving the fragments.
• In one embodiment, a method includes the steps of obtaining, by an assembling device from fractional-storage servers, erasure-coded fragments associated with a segment of streaming content; detecting a first quantity of at least one fragment associated with the segment, which have failed to arrive at the assembling; requesting via a fragment pull protocol for high latency approximately the first quantity fragments; and repeating the steps of detecting and requesting until enough fragments have been obtained for reconstructing the segment. Optionally, the steps are repeated approximately sequentially on the segments. Optionally, the streaming content comprises approximately sequential segments. Optionally, detecting the failure comprises determining which fragment has failed after not obtaining the fragment within a predetermined period from issuing its request, and/or receiving a message that does not contain the actual fragment's payload. And optionally, the fragments are obtained via sub-transmissions transmitted by the servers.
• In one embodiment, a method for retrieving erasure-coded fragments includes the steps of: determining, by an assembling device, the time remaining to reconstruct a segment of streaming content; estimating the probability of receiving a sufficient quantity of already-ordered erasure-coded fragments to reconstruct the segment during the remaining time; and if the estimated probability is below a predefined threshold, issuing one or more additional fragment requests, using a fragment pull protocol, until the estimated probability equals or passes the predefined threshold. Optionally, the already-ordered fragments and the additional fragment requests are received from fractional-storage CDN servers. Optionally, the already-ordered fragments are received via at least two sub-transmissions transmitted by the servers. Optionally, the already-ordered fragments are received via a fragment pull protocol. And, optionally, estimating the probability includes considering the probability of each request to result in a fragment reception during the remaining time.
• In one embodiment, an assembling device may aggregate several fragment requests into one message. The aggregated message is then sent to a fractional-storage server, possibly in a payload of a single packet, and optionally in order to conserve outgoing bandwidth and/or to reduce the number of packets needed to convey the requests. The fractional-storage server may then read the aggregated message and act accordingly by sending a plurality of fragment responses to the assembling device. The fragment responses may include one fragment at each payload, as is the case of responding to a single fragment request, or it may include an aggregated response including multiple fragments at each payload.
• In one embodiment, fragment aggregation is used for retrieving fragments associated with segments of streaming content, and each aggregated message requests fragments associated with a specific segment. For example, three fractional-storage servers store together 12 fragments associated with a certain segment, such that each stores four fragments. The assembling device needs the 12 fragments in order to reconstruct the segment and therefore issues three aggregated fragment request messages—one for each server. The three servers receive the aggregated request messages, and each server responds by sending its four fragments to the assembling device. Therefore, only three aggregated request messages were needed to retrieve the 12 fragments. The assembling device may request fragments associated with the next segment(s) in a similar manner using additional aggregated requests, optionally until receiving all required segments.
• FIG. 19 illustrates various examples of aggregated fragment request messages. In one example, the aggregatedfragment request messages503, which may be transported using one packet payload, uses a format (or a data structure) comprising asegment identification802 and the number-of-fragments803 requested by the assembling device. The receiving fractional-storage server uses the segment identification information to locate the relevant fragments associated with the identified segment, and then uses the number-of-fragments parameter803 to determine how many fragments, out of the located fragments, should be transmitted to the requesting device as a response.
• In one embodiment, the fragments are erasure-coded fragments and the fractional-storage servers store unique erasure-coded fragments. The assembling device receives multiple erasure-coded fragments from multiple servers, such that the number of received fragments is at most the sum of all number-of-fragments803 values as has appeared in all of the aggregated requests messages. In this case, the various fractional-storage servers need no inter-coordination to respond tomessage503, as the assembling device does not care which of the fragments associated with the identified segment were received, as long as at least the requested number of unique erasure-coded fragments were received. In some embodiments, aggregated fragment request messages and single fragment requests are used concurrently.
• In another example, an aggregatedfragment request message502 further comprises acontent identification field801. In still another example, an aggregated fragment request message may comprise requests for fragments associated with different segments of streaming content. In this case, and according to one example, the aggregatedrequest505 comprises a sequence of identifiedsegments902 containing the identification of all segments for which the assembling device requests fragments. Optionally, in the absence of additional information in the aggregated message, the fractional-storage server may assume that one fragment per each of the segments identified insequence902 is required. In this case, the server will locate such fragment per each of the identified segments, and will send them to the requesting device. The requesting device may include information regarding how many fragments are required per identified segment, as a number-of-fragments parameter903. The number-of-fragments903 may be a scalar value that indicates how many fragments are requested per each identified segment, or it may be a vector value, indicating the number of required fragments per each of the identified segments in the sequence.
• In one embodiment, fractional-storage server responds to a message, comprising aggregated requests for fragments associated with multiple segments, by sending all of the requested fragments to the requesting device, or by sending all of the requested fragments to the requesting device in a certain order. The order may follow the sequential order of the segments in streaming content. In one example, the fractional-storage server first sends the fragments associated with the first identified segment, and then sends the fragments associated with the next identified segments.Packet payload505 illustrates one example of an aggregated fragment request message comprising atransmission delay909 instructing the fractional-storage servers to incorporate intended delays while transmitting the different fragment responses. In one example, thetransmission delay909 sets the desired time delay between transmission of each group of fragments associated with the segments identified in thesequence902. In this case, the fractional-storage server responds to the aggregated request message by transmitting a sequence of fragments, associated with the identified segments, at a duty cycle determined by thetransmission delay909. In one example, the segments belong to streaming content and the effective rates at which the servers transmit their responses are controlled using thetransmission delay909.
• In one embodiment, the fragments are erasure-coded fragments and the assembling device uses multiple aggregated fragment request messages for obtaining the required content. Each message comprises multiple fragment requests associated with one sequence of segment(s) and addressed to a different fractional-storage server storing the relevant fragments. Each such sequence of segments may be referred to as a portion of streaming content, whereby the assembling device uses multiple aggregated messages to obtain each portion of the streaming content at a time. In one embodiment, the assembling device uses a wireless interface, such as WiFi, to connect to the Internet and communicate with the fractional-storage servers, and the fragment request aggregation techniques may dramatically reduce the number of time such an assembling device needs to gain access to the outgoing wireless interface. Moreover, the fragment request aggregation techniques may be combined with many of the disclosed embodiments for retrieving erasure-coded fragments.
• Still referring toFIG. 19, in one embodiment, requests for fragments are transmitted via an IP network, in the form of packet payloads. The packet payload may be, as an example, the payload of a UDP packet carried over IP. In one embodiment,packet payload501 contains a fragment request comprisingcontent identification801 andsegment identification802. A server receiving such a request uses the content and segment identifications to locate a relevant erasure-coded fragment, and transmits it back to the requester. Optionally, if no references are made as to how many fragments are requested per the identified segment, the server may assume that only one fragment is requested.
• In one embodiment, the fragment responses are transported over an IP network, using packet payloads. In one example,packet payload701 includes an actual requestedfragment payload602, and, optionally, information regarding thesegment601 to which the fragment payload belongs. The segment information may be needed if the requester retrieves fragments associated with more than one segment, and therefore it must know to which segment the fragment payload belongs. In one example, the fragment response is transported over UDP/IP, or TCP/IP, such that thepayload701 is a UDP or TCP payload.
• In one embodiment, multiple segments of content, which, in one example, is streaming content, are reconstructed by an assembling device retrieving multiple erasure-coded fragments associated with the multiple segments. Since a fragment request does not always result in a reception of the fragment, some requested fragments may fail to arrive at the assembling device. Therefore, the assembling device checks (from each of the segments for which fragments have already been requested) which requested fragments have failed to result in a correct reception of a fragment. For each such failure, the assembling device issues an additional request for a fragment. The additional requests are associated with segments for which fragments have already been requested before, and therefore, in one example, the resulting fragment retrieval process includes the following two sub-processes: a first sub-process of requesting fragments associated with new segments to be reconstructed, and a second sub-process of requesting additional fragments needed to complement already requested fragments, in order to reconstruct the segments. The first and second sub-processes work together, such that the second sub-process may complement fragments associated with a first segment, while the first sub-process runs ahead in an attempt to obtain fragments needed to reconstruct a second segment; wherein the second segment is located ahead of the first segment. The first and the second sub-processes can also be described as two different quantities of fragments being requested: a first quantity associated with the first sub-process requests, and a second quantity associated with the second sub-process requests.
• FIG. 20 illustrates one example of retrieving fragments and compensating the failures.Content100 is segmented intosegments102a,102b, and102c, and each segment is erasure-coded into four fragments, as illustrated forsegment102a, which is coded intofragments391ato391d. This example assumes that each segment can be reconstructed by obtaining any three fragments associated with it. Prior to time T1, the assembling device requests fragments391a,391b, and391cin order to reconstructsegment102a. At time T1, only two of the requestedfragments391aand391chave resulted in fragment reception, and were placed394a,394cin thebuffer398.Fragment391bhas not yet been received at time T1, but can still be received later, and therefore at time T1 the assembling device does not yet try to complete the missing fragment with an additional fragment request. Instead, it proceeds and requests fragments associated withsegment102b. At time T2, all of the fragments requested forsegment102bhave arrived, and have been placed395a,395b,395din thebuffer398. Prior to time T2, the assembling device transmits additional requests for fragments associated withsegment102c, and at time T3 two out of the requested fragments have arrived, and have been placed396b,396cin thebuffer398. At time T3, the assembling device realizes that the chances on receiving the previously requestedfragment391a(associated withsegment102a) are too small. This may be concluded, for example, as a long time having elapsed since the request, or by receiving a message from a fractional-storage server saying it is too loaded to respond with a fragment. Either way, the assembling device chooses to request anadditional fragment391d, instead of the previously requested391b. At time T4, the additional request is met with the reception offragment391d, and with itsplacement394din thebuffer398. At time T5, the third fragment previously requested forsegment102chas finally arrived and has been placed396ain thebuffer398, so there is no need to complement with an additional fragment request. At time T5 all fragments needed to reconstructsegments102ato102care stored in thebuffer398. It is noted that only one additional fragment request was needed in order to account for the lack of reception offragment391b, and that this additional fragment request was issued after consequent fragments had already been requested for consequent segments.
• In one embodiment, significant communication latency and/or other latencies between requesting and receiving a fragment exists. A significant latency may result in a case where the average latency in responding to fragment requests is in the order of magnitude of the total transmission time of all fragments needed to reconstruct a segment. As an example, if a segment needs 64 fragments of 1500 Bytes each to be reconstructed, and the assembling device has a 1.5 Mpbs incoming connection, then it takes about (64(fragments)×1500(bytes per fragment)×8(bits per byte))/1.5 Mbps=0.512 seconds to transmit the fragment via the incoming connection. If the average latency is 0.2 seconds (which is within the order of magnitude of 0.512 seconds), then from the time of requesting the first fragment to the time all fragments have arrived, a period of no less than 0.512+0.2=0.712 seconds may elapse. If the process takes 0.712 seconds, the resulting effective incoming throughput will be only (64(fragments)×1500(bytes per fragment)×8(bits per byte))/0.712(seconds)=1.07 Mbps, which is significantly less than the potentially 1.5 Mbps. In a case where some fragments are lost, and need to be requested again, the total time for segment retrieval may reach as high as 0.512+0.2+0.2=0.912, and the effective incoming throughput down to only 842 Kbps. The significant latency therefore adversely affects the effective incoming throughput. The effective throughput can be made to approach the incoming bandwidth available to the assembling device by utilizing the above-described fragment retrieving process comprising the two sub-processes of requesting fragments and complementing the failures. In this case, the first sub-process can be made to result in an average targeted fragment reception throughput, and span multiple segments, without handling the lost fragments. The second sub-process can then complement with additional needed requests, approximately per each fragment request that seems not to result in an actual fragment reception. According to another view, the first sub-process is an open loop retrieval process, in which the assembling device does not wait to check whether enough fragments have arrived per segment. And the second sub-process is the process, which closes the loop on fragments arrival, in order to make sure that every segment has enough fragments to enable reconstruction.
• In one embodiment, an assembling device may control the erasure-coded fragment reception throughput by controlling the rate of fragment request. For example, each of n fragments has a known size S1 to Sn. Therefore, issuing n requests over a period of T will result in an average fragment reception throughput of (S1+S2 . . . +Sn)/T. In one example, if each fragment is 1500 Bytes, and 64 fragment requests are issued over a period of 0.5 seconds, then the average expected fragment arrival throughput is (64×1500×8)/0.5=1.53 Mbps. The fragment requests do not need to be uniformly spread over the period of 0.5 seconds, although such a spread may result in a more stable throughput, which means that less communication buffering will be needed. Using the above-described rate-control technique may result in one or more of the following: retrieving the content at a target fragment reception throughput; preventing communication buffer spill at the last mile network resulting from uncontrolled fragment requests; and/or reducing fragment loss due to averaging the fragment traffic.
• In one embodiment, an assembling device transmits aggregated messages to a relay server, including the number of fragments needed per certain segment, but without identifying the storage servers from which fragments are to be requested. The relay server selects the appropriate storage servers to which the fragment requests are to be transmitted, and transmits discrete or aggregated fragment requests, corresponding to the number of fragments requested by the assembling device, to the selected storage servers. The storage servers receive the fragment requests from the relay server, and transmit the requested fragment to the assembling device. The relay server may select the storage servers according to one or more criteria, as long as the selected storage servers store relevant fragments. Optionally, the relay server forwards the address of the assembling device to the selected storage servers, and/or adds the address of the assembling device to the fragment requests transmitted to the selected servers, in order to enable the storage servers to transmit the fragment response to the assembling device.
• In one embodiment, shifting the process of selecting the storage servers from the assembling device to the relay server enables the design of a relatively thin and simple assembling device, having a relatively simple software, since all the assembling device has to decide in order to issue an aggregated fragment request to the relay server is how many fragments it needs per segment and, optionally, when it needs them.
• In one embodiment, an assembling device transmits aggregated messages to a relay server, comprising general information regarding a portion of streaming content for which fragments are needed. Optionally, the portion of the streaming content comprises several consecutive segments. In one embodiment, the portion is defined by a starting point and an ending point within the streaming content, and the relay server uses these points to determine the actual segments comprising the portion. Then the relay generates and transmits the corresponding fragment requests to the relevant storage servers.
• FIG. 21 illustrates one example of a fractional-storagesystem comprising servers699ato699(N) having abandwidth capability681. In other words, no server can send data at a rate higher than681. Assemblingdevice661 can select from which servers to obtain erasure-coded fragments for reconstruction of a segment. In one example, each server stores one relevant, unique, erasure-coded fragment. Therefore, from the N servers storing N possible unique fragments, the assembling device needs only K erasure-coded fragments for complete reconstruction of the segment (K<N). Since it is not important which K fragments from the N are retrieved, the assembling device may retrieve from the least loaded servers, so as to keep the load between the different servers balanced. When many assembling devices assemble contents in parallel, and since all assembling devices can select the least loaded servers, the end effect is that the load on the servers is balanced, with the potential for most servers to approach their maximal bandwidth capabilities. Optionally, that load balancing is achieved without significant coordination between the servers.
• In the example ofFIG. 21, assuming that K=3, the assemblingdevice661 may selectservers699b,699(N−1), and699afor fragment retrieval, as they have the lowest load of all N servers.Servers699cand699(N), as an example, will not be chosen, as they have relatively higher loads.
• The assembling device may select the least loaded servers using any appropriate method, such as, but not limited to (i) accessing a central control server having data about the load conditions on the various servers, or (ii) periodically querying the various servers on their load conditions.
• In one embodiment, instead of, or in addition to, selecting the least loaded servers, the assemblingdevice661 tries a random set of K servers from the N, and retrieves erasure-coded fragments from all servers reporting a load below a threshold, while higher loaded servers will be replaced by least loaded servers from the possible N servers. The end result is that the server array is balanced because the K erasure-coded fragments are retrieved from servers loaded below the threshold.
• In one embodiment, the assembling device does not know which of the servers store erasure-coded fragments related to the content to be retrieved, but the assembling device knows over how many servers (from the total number) the erasure-coded fragments are distributed. Therefore, the assembling device compensates for the infertile requests by enlarging the number of requests for erasure-coded fragments. Optionally, the requested servers are selected based on approximately random algorithm.
• FIG. 22 illustrates one embodiment ofdifferent servers698ato698(N) having different bandwidth capabilities of683ato683(N) correspondingly. Assemblingdevice661 selects from which K servers, out of the possible N, to retrieve the fragments for segment reconstruction, wherein each server may have different unutilized bandwidth and different bandwidth capability. When many assembling devices assemble contents in parallel, while rejecting servers with a high load, the end effect is that the server array is approximately balanced and most servers can approach their maximal bandwidth capabilities. In one embodiment, the server array is balanced by enabling many assembling devices to select the least loaded servers. In the example, and assuming that K=3,servers698a,698(N−1) and698(N) will be selected, as they have the highest unutilized bandwidth. In another example, the servers having the highest percentage of unutilized bandwidth will be selected.
• In one embodiment,servers698ato698(N) represent completely different types of server hardware, operating systems and capabilities, all put together in an array, and achieving load balance without the need for significant inter-server coordination. In one example, the fragments are distributed to at least two different classes of servers; the first class comprises high bandwidth CDN servers directly connected to the Internet backbone, and the second class comprises lower bandwidth CDN servers not directly connected to the Internet backbone.
• In one embodiment, the servers are selected for fragment retrieval according to their unutilized fragment delivery bandwidth. For example, the servers report their unutilized bandwidth, and the assembling devices, or a control server, obtain the report and decide which servers to use for fragment delivery based on the unutilized bandwidth of each server.
• In one embodiment, the servers are selected for fragment retrieval according to their ability to support additional fragment delivery load. For example, the servers report their ability to support additional fragment delivery loads. And the assembling devices, or a control server, obtain the report, and select the servers that report an ability to support additional fragment delivery loads.
• In one embodiment, the assembling device, or a control server, looks for a pool of servers that may be used as replacements for servers that are loaded to a degree that does not allow continuation of fragment delivery. For example, the assembling device looks for potential unloaded servers, while retrieving fragments from other servers. The assembling device may sample relevant servers approximately randomly, and/or according to indications from a control server. The sampling process may comprise querying the potential server for load information, or measuring the latency or latency variance to the servers in order to estimate the current load on the server.
• In one embodiment, it is desired to replace one or more servers by other servers for the delivery of erasure-coded fragments, wherein the replacement servers are selected using a second criterion from a pool of servers identified using a first criterion. For example, the first criterion for identifying the pool of replacement servers comprises looking for servers capable of increasing their fragment delivery throughputs, and the second criterion for selecting the replacement servers from the pool comprises selecting the best latency response server from the pool. In one example, the first criterion is a latency criterion, and the second criterion is a load criterion. In another example, the first criterion is a latency criterion, and the second criterion is a latency variance criterion. In another example, the second criterion is an approximately random selection. In one embodiment, a server selected using the second criterion is compared to the server to be replaced based on the second criterion. For example, the second criterion is latency, and the replacing server, selected from the pool, has a smaller latency than the server it replaces.
• In one embodiment, the server to be replaced is identified by comparing the actual performance level of the server with a threshold performance level. For example, when the compared performance is latency, a server having response latency above a certain threshold is replaced. In another example, the compared performance is the load on the server, which may be measured in terms of the amount of the unutilized fragment delivery bandwidth, or in terms of the percent of the server's unutilized fragment delivery bandwidth, or measured by any other appropriate technique.
• In some embodiments, the assembling devices use a fragment pull protocol to retrieve the fragments and approach the servicing servers. In some embodiments, the assembling devices use a push protocol to obtain the fragments and approach the servicing servers, possibly by obtaining multiple sub-transmissions comprising fragment sequences.
• FIG. 23 illustrates one embodiment of a fractional-storage system. Assemblingdevice group661gobtain erasure-coded fragments from the servers, such that the resulting outgoing bandwidth utilizations of each server in the array is682ato682(N) correspondingly.FIG. 24 illustrates a case whereserver698bhas failed, itsbandwidth capability682b1 is zero, and is therefore unable to provide erasure-coded fragments. The assembling devices fromgroup661g, which previously obtained fragments fromserver698b, may attempt to access it again for additional fragments, but are now unable to get a response. These assembling devices therefore obtain fragments from alternative servers. The end effect is thatbandwidth682bis now loaded on the still available servers, such that thetotal bandwidth682a1 to682(N)1 approximately increases by a total amount equal to682b, optionally with no inter-server coordination, and simply by the fact that each assembling device selects alternative available servers for obtaining fragment on-the-fly. In one example, instead of obtaining fromserver682b1, the assembling devices obtain from the least loaded available servers. In one embodiment, a control server selects the alternative server/s for the assembling devices. In one embodiment, the assembling devices use a fragment pull protocol to obtain the fragments, and approach the alternative servers. In one embodiment, the assembling devices use a push protocol to obtain the fragments, and approach alternative servers, possibly by obtaining multiple sub-transmissions comprising fragment sequences. In this case, the sub-transmissions of the faulty server are discontinued and compensated for by other sub-transmissions from the alternative servers.
• FIG. 25 illustrates an example similar toFIG. 24 with the difference thatservers698a,698b, and698cto698(N) reside within, or get serviced via, first, second, and thirdInternet backbone providers300j,300i, and300hcorrespondingly. The group of assemblingdevices661gis connected to the Internet vianetwork300k, which has access to all three backbones, such that communication between the assembling devices andservers698ato698(N) pass via at least one of the backbones, or more. Ifserver698bis made unavailable to the assembling devices, optionally not due to a server failure, but rather due to congestion or a failure of the secondInternet backbone provider300i, assemblingdevices661gcompensate for the lost bandwidth by switching to the available servers on-the-fly. In one embodiment,networks300h,300i, and300j, are different physical sub-nets of one network connected to the Internet. In one embodiment, the assembling devices are connected tonetworks300h,300i, and300j, vianetwork300k, and then via one or more Internet Exchange Points (“IX/IXP”).
• FIG. 26 illustrates a few examples of retrieving fragments according to locality. In one example, the fractional-storage servers are connected to a data network or networks comprising therouters201 to209. Assemblingdevices235,237, and238 are connected to the same data network or networks, and K=3, meaning that any assembling device needs to obtain 3 erasure-coded fragments per segment from optionally 3 different servers out of the 10 in order to successfully reconstruct the segment.
• Each assembling device tries to obtain erasure-coded fragments from fractional-storage servers that are closest to it topologically. In one embodiment, the topological distance is a function of the number of separating routers. Assemblingdevice238 can select three servers fromgroups242,248 or249. According to the minimal path criterion, it retrieves the erasure-coded fragments fromservers399hto399iofgroup248, since they are only onerouter208 away.Groups242 and249 are three (208,202,203) and five (208,202,203,201,209) routers away, and are therefore not selected for retrieval. Similarly,device237 selects three servers out ofgroup242, anddevice235 can select any three servers fromgroups242 and249, since both are located four routers away.
• In one embodiment, if topologically close servers do not respond to the assembling device, or report a bandwidth limitation, the assembling device will attempt to obtain an erasure-coded fragment from the next topologically closest server.
• In one embodiment, an assembling device attempts to obtain erasure-coded fragments from servers featuring the lowest latency. Upon no response, for whatever reason, the assembling device will attempt to retrieve from the next lowest latency server. In one embodiment, the assembling device obtains information regarding the unutilized fragment delivery bandwidths of servers, and then attempts to retrieve from the lowest latency servers out of the servers having enough unutilized bandwidth. In one embodiment, the assembling device obtains information regarding the unutilized fragment delivery bandwidths of the servers, and then attempts to retrieve from the topologically closest servers out of the servers having enough unutilized bandwidth.
• Still referring toFIG. 26, in one embodiment the assembling devices select servers according to a latency criterion, such as selecting servers with the shortest time between fragment request and fragment delivery, or selecting servers having latency below a dynamic or static threshold. Assemblingdevice237 assembles content fromservers399c,399f,399g, and assemblingdevice235 assembles content fromservers399b,399c,399g(both use a mixture of servers fromgroups242 and249). At a certain point in time,router209 becomes congested or blocked, and prevents the erasure-coded fragments fromservers399band399cfrom arriving at assemblingdevices235 and237, or causes the fragments to arrive with an increased delay. Therefore, assemblingdevice235 switches to three servers ofgroup242, and assemblingdevice237 switches fromserver399ctoserver399e.
• In one embodiment, the assembling device selects fractional-storage servers according to the following criterion: first, servers with adequate unutilized fragment delivery bandwidth are considered, then out of these, those with latency below a threshold are considered, and out of these, the servers with minimal topological routing path are selected.
• In some embodiments, the assembling devices use a fragment pull protocol to retrieve the fragments, and approach servers having low latency or low hop count as compared to other servers. In some embodiments, the assembling devices use a push protocol to retrieve the fragments, and approach servers having low latency or low hop count as compared to other servers, optionally by obtaining multiple sub-transmissions comprising fragment sequences.
• In one embodiment, a plurality of unsynchronized retrieving assembling devices, which optionally use fragment pull protocol, choose the least loaded servers from which to retrieve the erasure-coded fragments. Optionally, the servers have almost no inter-communication between them and the load balancing calculation is performed by the retrieving assembling devices. Because the assembling devices can select the least loaded servers, the assembling devices manage the load balancing. When the erasure-coded fragments stored by the servers are unique erasure-coded fragments, the retrieving assembling device may retrieve erasure-coded fragments from any relevant server. Therefore, it may be enough for the retrieving assembling device to have indication of the load on its targeted servers, and retrieve enough erasure-coded fragments from the least loaded servers.
• In one embodiment, a server signals the retrieving assembling device that it is close to its bandwidth limit and the assembling device searches for an alternative server. Optionally, the assembling device selects the server according to one or more of the following parameters: locality, cost, latency, or reliability. In one embodiment, the servers register their loads on a central server, and the assembling device selects the server to retrieve from, from the registered servers. In one embodiment, a central server, holding the loads of the various servers, determines for the assembling devices from which server to retrieve the erasure-coded fragments.
• In one embodiment, assembling devices measure the latency of the different servers in responding to fragment requests, and then use the latency information to estimate the loads on the servers. In one example, a high latency may indicate a high load on the server.
• In one embodiment, the topological router hop count between an assembling device and fragment delivering servers is used to estimate the latency of the servers in responding to fragment requests.
• In one embodiment, the latency of fragment delivering servers in responding to fragment requests by an assembling device is used to estimate the topological router hop count between an assembling device and the servers.
• In one embodiment, the assembling devices perform several latency measurements for the different servers in responding to fragment requests, and then use the latency variance information to estimate the loads on the servers. In one example, a high latency variance may suggest a high load on server.
• In one embodiment, fractional-storage servers, from which the fragments are obtained for reconstructing a segment, are selected based on an approximately random selection algorithm from all of the servers storing the relevant fragments. In one example, an approximately random selection algorithm weighted according to the unutilized bandwidth of the servers is used for the approximately random selection of servers. The weighted random selection algorithm assigns servers with selection probabilities proportional to the amount of unutilized bandwidth for fragment delivery in each of the servers, such that the probability to select a server having a larger amount of unutilized bandwidth is higher than the probability to select a server having a lower amount of unutilized bandwidth.
• The following embodiments describe processes for on-the-fly selection and re-selection of fractional-storage servers from which to obtain erasure-coded fragments.
• In one embodiment, a method for selecting enough new servers from which to obtain fragments, based on the unutilized bandwidth of the servers, includes the following steps: (i) accessing data regarding servers storing relevant fragments (referred to as the relevant servers); (ii) accessing data regarding the unutilized bandwidth of the relevant servers. Optionally, the data is received by the assembling device from the relevant servers; and (iii) obtaining fragments from enough of the relevant servers having approximately the highest unutilized bandwidth; or obtaining fragments from enough of the relevant servers selected randomly and having unutilized bandwidth above a certain threshold.
• In one embodiment, a method for selecting enough new servers from which to obtain fragments, based on latency, includes the following steps: (i) accessing data regarding the relevant servers; (ii) accessing data regarding the latencies from the relevant servers to the assembling device; and (iii) obtaining fragments from enough of the relevant servers having the lowest latencies; or obtaining fragments from enough of the relevant servers selected randomly and having latencies below a certain threshold.
• In one embodiment, a method for selecting enough new servers from which to obtain fragments, based on bandwidth and latency, includes the following steps: (i) accessing data regarding the relevant servers; (ii) accessing data regarding the unutilized bandwidth of the relevant servers; (iii) identifying more than enough relevant servers having the most unutilized bandwidth; or randomly identifying more than enough relevant servers having unutilized bandwidth above a certain threshold; (iv) accessing data regarding the latencies from the identified servers to the assembling device; and (v) obtaining fragments from enough of the identified servers having the lowest latencies; or obtaining fragments from enough of the relevant servers selected randomly and having latencies below a certain threshold.
• In one embodiment, a method for selecting enough new servers from which to obtain fragments, based on latency and bandwidth, includes the following steps: (i) accessing data regarding the relevant servers; (ii) identifying more than enough relevant servers having latencies to the assembling device below a certain threshold; or randomly identifying more than enough relevant servers having latencies to the assembling device below a certain threshold; (iii) accessing data regarding the unutilized bandwidth of the identified servers; and (iv) obtaining fragments from enough of the identified servers having the highest unutilized bandwidth; or obtaining fragments from enough of the relevant servers selected randomly and having the highest unutilized bandwidth.
• In one embodiment, a method for selecting enough new servers from which to obtain fragments, based on locality, includes the following steps: (i) accessing data regarding the relevant servers; (ii) accessing data regarding the network topology distance (locality) from the relevant servers to the assembling device; and (iii) obtaining fragments from enough of the topologically closest relevant servers; or obtaining fragments from enough of the relevant servers that are located in the same sub-network as the assembling device, or located in the closest sub-networks.
• In one embodiment, a method for selecting enough new servers from which to obtain fragments, based on bandwidth and locality, includes the following steps: (i) accessing data regarding the relevant servers; (ii) accessing data regarding the unutilized bandwidth of the relevant servers; (iii) identifying more than enough relevant servers having the most unutilized bandwidth; or randomly identifying more than enough relevant servers having unutilized bandwidth above a certain threshold; (iv) accessing data regarding the network topology distance from the relevant servers to the assembling device; and (v) obtaining fragments from enough of the topologically closest relevant servers; or obtaining fragments from enough of the relevant servers that are located in the same sub-network as the assembling device, or located in the closest sub-networks.
• In one embodiment, a method for selecting enough new servers from which to obtain fragments, based on latency and locality, includes the following steps: (i) accessing data regarding the relevant servers; (ii) identifying more than enough relevant servers having latencies to the assembling device below a certain threshold; or randomly identifying more than enough relevant servers having latencies to the assembling device below a certain threshold; (iii) accessing data regarding the network topology distance from the relevant servers to the assembling device; and (iv) obtaining fragments from enough of the topologically closest relevant servers; or obtaining fragments from enough of the relevant servers that are located in the same sub-network as the assembling device, or located in the closest sub-networks.
• In one embodiment, a method for selecting enough new servers from which to obtain fragments is based on bandwidth, latency, locality, and, optionally, one or more additional relevant parameters. The method may weigh the different parameters in various ways, all of them are intended to be covered by the embodiments. For example, the method may include the following steps: (i) accessing data regarding the relevant servers; (ii) receiving data regarding the unutilized bandwidth latencies to the assembling device, and topology distances to the assembling device; (iii) weighting the received data and identifying a quantity of the most proper relevant servers, which can provide enough fragments to reconstruct content; and (iv) obtaining the fragments from the identified servers. In another example, the method may include the following steps: (i) accessing data regarding the relevant servers; (ii) identifying a set of more than enough relevant servers having the most unutilized bandwidth; or randomly identifying a set of more than enough relevant servers having unutilized bandwidth above a certain threshold; (iii) from the set, identifying a sub-set of more than enough relevant servers having latencies to the assembling device below a certain threshold; or randomly identifying more than enough relevant servers having latencies to the assembling device below a certain threshold; and (iv) obtaining fragments from enough of the topologically closest relevant servers out of the sub-set; or obtaining fragments from enough of the relevant servers out of the sub-sets, which are located in the same sub-network as the assembling device, or located in the closest sub-networks.
• In some embodiments, approximately random selection of fractional-storage servers is utilized for dealing with changes in network conditions, such as packets loss and/or server failure, without affecting the user experience, and optionally without prior knowledge of the type of the change in network condition. Optionally, new erasure-coded fragments are requested from the randomly selected servers instead of failed requests. Optionally, failed servers are replaced with other servers. Optionally, the combination and/or the number of fractional-storage servers from which the fragments are obtained changes over time. Optionally, the number of redundant fragment requests changes over time.
• In one embodiment, a method for reselecting one or more fractional-storage CDN servers on-the-fly, comprising: pulling erasure-coded fragments from the servers; estimating the servers' load, latency, network congestion, and packet loss; and operating a fuzzy algorithm on the estimations in order to replace at least one of the servers with at least one other fractional-storage server. Optionally, the method further comprising operating the fuzzy algorithm based on measurements of many assembling devices and recommendations received from a central server. Optionally, the method further comprising replacing the servers quickly after missing a fragment. And optionally, the fuzzy algorithm weighs many possible solutions and converges to a sufficient one.
• FIG. 27 illustrates one example of creating a broadcast-like effect (i.e. retrieving the content while it is distributed).Streaming content700a, which may be ready in advance or received on-the-fly, is to be received and presented by multiple assembling devices at approximately the same time.Content700ais segmented into segments on-the-fly, such that thefirst segment710ais ready shortly after the data is available, andsubsequent segment710bis ready right after that.Segments710aand710bare sequentially encoded into erasure-codedfragments782aand782bcorrespondingly, such that the average rate of encoding segments into erasure-coded fragments does not fall below the average rate of introducing new segments (ascontent700ais being received for broadcast).
• As the erasure-codedfragments782aare ready, they are distributed783ato the fractional-storage servers. Subsequent erasure-codedfragments782bare similarly distributed783bto the servers, such that the average rate of distributing the erasure-coded fragments associated with each segment does not fall below the rate of introducing new segments (or in other words, such that there is approximately no piling-up of undistributed segments). Optionally, the erasure-codedfragments782aare also distributed784aby the servers to bandwidth amplification devices at an average distribution rate per segment that does not fall below the average rate of introducing new segments.
• The assembling devices obtain erasure-codedfragments785aassociated withsegment710afrom the fractional-storage servers, and optionally also from the bandwidth amplification devices. Subsequent erasure-coded fragments, such as785bassociated withsegment710b, are obtained at an average rate that does not fall below the average rate of introducing the new segments. Thesegment710ais then reconstructed from the obtained erasure-codedfragments785a. Thesubsequent segment710bis reconstructed from the obtained erasure-codedfragments785b, such that reconstructing each segment is performed at an average rate that does not fall below the average rate of introducing the new segments.
• Then, the reconstructed segments are presented, optionally on-the-fly, as reconstructedcontent700b. In one embodiment, the entire process end-to-end is performed in real time, such that the presentation of700bstarts at T2 minus T1 after the availability ofcontent700a, and such that the delay of T2 minus T1 (between the availability of new segments and their subsequent presentation by the assembling device) is kept approximately constant throughout the entire presentation of thestreaming content700b, once begun.
• In one example, thecontent700ais a 4 Mbps video stream, and the segment size is 96 Kbytes, meaning thatnew segments710a,710bare made available at a rate of one every 0.19 seconds. Assuming that each process as described takes 0.19 seconds, and that all processes are performed sequentially (with no overlapping in time, which may be possible for some of the processes), then the accumulated process time, which includes710a,782a,783a,784a,785aand710a, takes about 6×0.19=1.14 seconds. This means that an assembling device may begin with content presentation 1.14 seconds after the content is first made available to the system.
• Still referring toFIG. 27, in one embodiment, the fragments are obtained from the servers using multiple sub-transmissions, such that each transmitting server sends a fraction of the needed fragments to the assembling device, according to the sequential order of segments. Each sub-transmission transmits the fragments approximately at a rate at which the fragments are being created on-the-fly from segments of the content to be received by the assembling device. According to another embodiment, the fragments are obtained from the servers using fragment requests made by the assembling device using a fragment pull protocol.
• The Audio/Video compression utilized in creatingcontent700ais not necessarily a fixed rate compression, meaning that the various resulting segments do not necessarily contain the same amount of presentation time.
• In one embodiment, once starting to retrieve a broadcast-like stream, the assembling device may use one of the following methods to synchronize the retrieval of the stream's segments with the ongoing availability of new segments of the stream: (i) The assembling device retrieves additional segments such that the average rate of obtaining new frames approximately equals the average rate of presenting frames. (ii) The assembling device retrieves additional segments such that it does not try to retrieve segments that are not yet indicated as being available. And (iii) The assembling device retrieves additional segments so as to approximately maintain a constant distance (in segments) between the most currently available segment and the segment currently being retrieved.
• In one embodiment, the assembling device presents the broadcast-like stream at approximately the same frame rate as the rate of producing new frames for the broadcast-like stream. In one example, the frame rate is constant throughout the stream, such as the case of fixed 24, 25, 50, or 60 frames per second.
• In one embodiment, the assembling device obtains an indication regarding the most newly available segment (per specific broadcast-like stream) for retrieval. The assembling device then starts to retrieve from the most newly available segment. In one example, the most newly available segment is the last segment that was distributed to the fractional-storage servers. In another example, the most newly available segment is a segment that was recently distributed to the fractional-storage servers, but wherein there are newer distributed segments, which are not yet indicated as being available.
• In one embodiment, the broadcast-like stream is of a pre-recorded content, such that it is possible to distribute the entire content to the fractional-storage servers, and after any period of time allow the real time consumption of the content by any number of assembling devices. In such a case, an indication is made to the assembling devices regarding the real time allowance to retrieve the related segments. The allowance can start at a certain point in time (which corresponds to the beginning of the broadcast-like “transmission”) for the first segment, and then the allowance may continue for subsequent segments, at a rate that approximately corresponds to sustaining the frame rate of the broadcast-like stream.
• FIG. 28 illustrates one embodiment of using the entire aggregated bandwidth of the fractional-storage servers for delivering multiple contents. Approximately any number of contents having any mixture of bandwidth demand per content may be delivered, as long as the aggregated bandwidth demand does not exceed the aggregated bandwidth of the fractional-storage servers. In one example, broadcast-like streams3101,3102, and3103 are delivered to multiple assembling devices via multiple fractional-storage servers. Each stream is a live TV channel carrying multiple TV programs. For example,stream3101 comprisesTV programs3110 to3112, each spanning a specific time interval. The other streams comprise of multiple TV programs as well. Before time T1,stream3130 has a bandwidth demand of3130′ (meaning that all assembling devices that are currently retrievingstream3130′ use a total bandwidth of3130′ out of the fractional-storage servers). Theother streams3120 and3110 have bandwidth demands of3120′ and3110′ respectively. The total bandwidth demand of the threestreams3130′+3120′+3110′ does not exceed the aggregated bandwidth of the fractional-storage servers3150, and therefore all streams are fully delivered to the assembling devices. The load of the three streams is spread approximately equally among the participating fractional-storage servers, optionally because of a mechanism that selects the least-loaded servers to serve each assembling device, and/or a mechanism that approximately randomly selects servers to serve each assembling device. At time T1,TV program3120 ends, andTV program3121 starts.Program3121′sdemand3121′ is higher than theprevious demand3120′, and therefore a higher aggregated bandwidth is drawn from the fractional-storage servers. Still, the aggregated bandwidth demand of all three streams (3130′+3121′+3110′) is lower than the maximum possible3150, and therefore the newly added bandwidth demand is fully supported by the servers. Optionally, the additional demand created by TV program3121 (3121′ minus3120′) is caused by the addition of new assembling devices that joinstream3102 and retrieving additional erasure-coded fragments. Additionally or alternatively, the additional demand created byTV program3121 is caused by a higher bandwidth demand ofTV program3121, such as 3D data or higher resolution. Newly added assembling devices may choose fractional-storage servers from which to retrieve, according to a least-loaded server selection criterion and/or an approximately random server selection criterion, and therefore the total load is still spread approximately equally among the participating servers. At time T2,TV program3110 ends, and anew program3111 begins, which is less popular, and therefore creates alower bandwidth demand3111′. The result is a decrease in the total delivered bandwidth. At timeT3 TV program3130 ends, andTV program3131 starts with a higher bandwidth demand of3131′. At time T4 bothTV programs3111 and3121 end, and twonew programs3112 and3122 start.TV program3112 is highly popular and therefore generates alarge bandwidth demand3112′.Program3122 is not popular, and therefore generates alimited bandwidth demand3122′. Some of the additional bandwidth needed byprogram3112 is taken from servers that stop serving assembling devices previously retrievingprogram3121, such that the aggregated bandwidth of all three streams (3131′+3122′+3112′) is still below the maximumpossible bandwidth3150, despite the fact thatprogram3112 is generating a large bandwidth demand. This example illustrates how the fractional-storage servers support almost any demand mixture, as long as the aggregated demand of all streams is kept below the aggregated maximum capacity of theservers3150. Consequently, the distribution of all of the streams to the fractional-storage servers is approximately unrelated to the changes in bandwidth demand for programs carried by each stream; each stream can be regarded as a sequence that is segmented, erasure-encoded, and distributed to the participating servers. There is no need to account for demand variations during the distribution of each stream, nor is there a need to know in advance the bandwidth demand for each stream or for each program within each stream. It is noted that the demand variations are illustrated as instant variations, but may also be gradual and may occur during a program and not necessarily when one program ends and the other begins.
• Referring toFIG. 27, in one embodiment, an assembling device is allowed to start assembling the erasure-codedfragments785a, not after the first segment is stored (as illustrated inFIG. 27), but only after several segments are already stored as erasure-coded fragments. In this case, the presentation begins with an intentional delay from the real time content storage process, which may be maintained throughout the content presentation process. In one embodiment, the average rate of assembling erasure-coded fragments is greater than the average rate of the real time content presentation, such that the data that separates the real time storage head from the presentation point is quickly accumulated in the content buffer at the assembling device side, allowing for a short loss of communication between the assembling device and the fractional-storage system without any interference in the continuous presentation process (as long as the loss of communication is resolved within a time shorter than the intentional delay).
• In one embodiment, the intentional delay technique is used with a non-distributed server array, meaning that the fragments are stored on one location. In one embodiment, the intentional delay technique is utilized using a standard push protocol (like TCP/IP), and not a fragment pull protocol as suggested in the embodiments ofFIG. 27.
• Still referring toFIG. 27, in one embodiment the delay between the point that the erasure-coded fragments are distributed to the servers Td, and the point that the erasure-coded fragments begin to be obtained by an assembling device Tg (Tg minus Td), is controlled by the assembling device, such that any content can be viewed after it has been broadcast, constituting a Network Private Video Recording (nPVR). In one embodiment, the delay between the point that the erasure-coded fragments are distributed to servers Td, and the point that the erasure-coded fragments begin to be obtained by an assembling device Tg (Tg minus Td), starts at a minimum (fractions of seconds), and can increase as presentation progresses, at the assembling device's command, giving rise to presentation freeze capabilities and jumping backwards.
• In one embodiment, a method comprising the following steps: distributing in real-time erasure-coded fragments, generated from a streaming input, to fractional-storage servers. And as long as the erasure-coded fragments are still stored on the servers, retrieving the erasure-coded fragments, by a retrieving device, at approximately any time shift relative to the current position of the real time erasure-coded fragment distribution. Optionally, a user controls the time shift. Optionally, the assembling device retrieves the erasure-coded fragments in a first time shift, then pauses the presentation of the reconstructed content, and then continues retrieving erasure-coded fragments in a second time shift, which is longer than the first time shift.
• In one embodiment, the fractional-storage system is approximately insensitive to the mixture of the consumed contents as long as the aggregated throughput is below the total throughput of the fractional-storage servers.
• FIG. 29 illustrates one example of a server array, including N fractional-storage servers (399ato399(N)), and storing content A, which includes erasure-codedfragments310ato310(N), and content B, which includes erasure-codedfragments320ato320(N). Each server is connected to thenetwork300 with a fragment deliverybandwidth capability B339. Therefore, the N servers have an aggregated bandwidth of B×N. A first group of assemblingdevices329aconsumes content A at anaverage bandwidth Ba349a. A second group of assemblingdevices329bconsumes content B at anaverage bandwidth Bb349b. Since all of the servers participate in the transmission of the two contents, the first and second groups can potentially consume all server bandwidth, up to the limit where Ba+Bb=N×B, with any ratio of demand between the first and second contents, and with no special provisions to be made when storing the erasure-coded fragments related to the two contents in the fractional-storage server array.
• FIG. 30 illustrates the case where thefirst group328a, which consumes content A, becomes larger than329a, with alarger bandwidth Ba348a. Thesecond group328b, which consumes content B, becomes smaller than329b, with asmaller bandwidth Bb348b, such that Ba is about the same as Bb. In this case, the array can still be exploited up to the aggregated bandwidth, since, as before, Ba+Bb can still be almost as high as N×B.FIG. 31 illustrates the case where the first group has disappeared, allowing thesecond group327b, which consumes content B, to extract an aggregated bandwidth ofBb347bthat can potentially reach the limits of the server array, such that Bb=N×B. Again, this is achieved without updating the erasure-coded fragments associated with content A and content B, and without using inter-server interaction.
• In some embodiments, the ability to utilize the aggregated bandwidth of approximately all of the participating servers, for the delivery of about any mixture of contents with about any mixture of content bandwidth demand, is made possible by one or more of the following: (i) each assembling device selecting a subgroup of the least loaded fractional-storage servers from which to retrieve the necessary number of erasure-coded fragments to reconstruct a segment or several segments (least-loaded server selection criterion); or (ii) each assembling device approximately randomly selecting a subgroup from which to reconstruct a segment or several segments, such that when many assembling devices select at random, the various fractional-storage servers are selected approximately the same number of times (or in proportion to their available resources, such as unutilized bandwidth), which in turn balances the load between the participating servers (random server selection criterion). It is noted that (i) the selections may be made by either the assembling devices themselves, or may be made for the assembling devices by a control server, which then communicates the selections to each of the assembling devices; (ii) the selections may be made approximately for each segment, or for a group of segments, or only once per content at the beginning of the content; (iii) some assembling devices may use an approximately random server selection criterion, while other assembling devices may use least-loaded server selection criterion; (iv) the least-loaded selected servers may be selected out of a portion of all available fractional-storage servers. For example, the least-loaded servers may be selected from fractional-storage servers with low latency response or with low hop count to the assembling device; (v) the least-loaded servers may include servers having the most unutilized bandwidth. Additionally or alternatively, it may include servers having any unutilized bandwidth left to serve additional assembling devices; (vi) an approximately random or least-loaded selection of servers may be made such that all servers are selected to determine a subgroup, or it can be made such that every time selections are made, only some servers are selected, while the others remain as before. In these cases, the assembling device runs a process in which only a small portion of the servers currently in the serving subgroup are reselected. In the case of approximately random selection, the assembling device may randomly select the number of servers in the serving subgroup for random selection (reselection in this case, since they are replacing other servers already in the serving subgroup of the specific assembling device), such that eventually, over time, all servers within the serving subgroup have the chance to be randomly reselected. In the case of least-loaded server selection, only the most loaded servers within the serving subgroup may be selected and replaced by less-loaded servers.
• In one embodiment, data objects required to render a presentation are reconstructed from erasure-coded fragments gathered from fractional-storage servers. The reconstructed data objects are combined with additional rendering data, to form the presentation. A master data object is used to point to the data objects, and may include addresses of relevant fractional-storage servers from which a renderer can obtain fragments needed to reconstruct the data objects.
• In one embodiment, the additional rendering data required to render the presentation is embedded in the master data object.
• In one embodiment, the addresses of the relevant servers are obtained from a source external to the master data object, such as by making an inquiry to a control server.
• In one embodiment, the master data objects are obtained from one or several contact servers.
• In one embodiment, the functionality of the contact servers is embedded in some of the fractional-storage servers.
• FIG. 32 illustrates one embodiment, in which an HTML master data object3800 (an HTML file) comprises data objects and data object pointers3801 to3808. Object3801 points to a FLASH data object and comprises the identity of the FLASH object, optionally in standard URL notation, and the addresses of fractional-storage servers from which the renderer can obtain erasure-coded fragments needed to reconstruct the FLASH data object; the addresses are embedded in the HTML file optionally as HTML remarks accompanying the identity of the FLASH object. Data object3802 comprises standard HTML text and HTML rendering instructions for the text. Object3803 points to an audio-video data object, and comprises the identity of the audio-video object and addresses of servers from which to obtain relevant fragments. Data objects3804 to3807 comprise standard HTML buttons with all necessary rendering and functional HTML information. Object3808 points to an image or animated image object, optionally a JPEG, GIF animation, or an Ad, and comprises the identity of the image object and addresses of servers from which to obtain relevant fragments.
• FIG. 33 andFIG. 34 illustrate one embodiment, in which a renderer, such as an HTML enabled Internet browser, receives the HTMLmaster data object3800, and starts rendering a presentation of awindow3810 to its user accordingly. Data objects3802 and3804 to3807 are rendered by the browser to following standard HTML visual objects:text window3812, andbuttons3814 to3817 respectively. The general appearance ofwindow3810 and related general rendering information are embedded as standard HTML instructions3809. Data objects pointed to by objects3801,3803,3808 are not rendered until the relevant objects are obtained by the browser, although theirlocations3811,3813,3818 inwindow3810 are already known, since relevant standard HTML window positioning instructions accompany objects3801,3803,3808. The browser obtains erasure-coded fragments from some or all of the fractional-storage servers whose addresses have been specified in masterHTML data object3800. Each of the data objects3801,3803 and3808 is optionally obtained separately from server addresses specified for it. Obtained fragments per each of data objects3801,3803 and3808 are used to reconstruct the objects, which are then rendered and presented aswindows3811′,3813′ and3818′ displaying FLASH multimedia sequences, audio-video content, and images or animated images respectively.
• It is noted that the master HTML data object3800 may be several orders of magnitude smaller than objects3801,3803,3808. In this case, the main load of delivering the objects goes to the fractional-storage servers, and not to the contact server or servers delivering the master data object.
• Audio-video data object3803 may comprise segments. In this case, segments are consecutively reconstructed from fragments in support of streaming presentation in accordance with some embodiments. The streaming presentation inwindow3813′ starts almost instantly after themaster HTML object3800 is obtained by the browser. Other data objects, such as FLASH objects, may be segmented as well in facilitation of streaming presentation.
• FIG. 35 illustrates one embodiment, in which the identification of the data object and the list of fractional-storage server addresses associated with that object are embedded in the master HTML data object as standard HTML text.HTML line4010 describes a JPEG image data object identified by the URL “http://www.somewhere.com/image.JPG”, and includes the standard HTML position information: =“position:absolute; TOP:35px; LEFT: 170px; WIDTH:50px; HEIGHT:50px”. Followingline4010, N fractional-storage server addresses are specified as HTML remarks. AddressesIP_ADDRESS#1 to IP ADDRESS#N are the actual N Internet-Protocol addresses or URLs that can be used by renderers to obtain erasure-coded fragments relevant for reconstructing the image “http://www.somewhere.com/image.JPG”.
• In one embodiment, an Internet browser parses and executesHTML lines4010 to4013 as follows:Line4010 provides the browser with positioning and size information in a standard HTML format. This information is used by the browser to determine the position and size of the presentation window of image “http://www.somewhere.com/image.JPG”. The browser then parseslines4011 to4019, and extracts the N addresses of relevant servers. The browser then contacts the servers, and obtains a sufficient number of fragments needed to reconstruct the image. After reconstruction, the image is presented at the specified size and position.
• In one embodiment, a plug-in to a standard browser performs the non-standard portions of parsing the server addresses, obtaining the fragments, and reconstructing the data object. All other aspects are performed by the standard browser.
• In one embodiment, the URL identifying the data object points to an actual URL storing the data object. In one example, standard browsers that do not have the capability to obtain and decode fragment, parseHTML line4010 and obtain the image “http://www.somewhere.com/image.JPG” from actual URL address http://www.somewhere.com/image.JPG. Standard browsers ignorelines4011 to4013, as they are HTML remarks transparent to standard HTML browsers.
• In one embodiment, the fractional-storage servers are CDN servers. Optionally, the servers are located on the Internet backbone, or close to the backbone.
• In one embodiment, the fractional-storage servers are P2P devices, located at user premises.
• FIG. 36,FIG. 37, andFIG. 38 illustrate one embodiment, in which a large-scale distributed content delivery system is used to store web sites and to deliver web-pages and related content to users. The system comprises at least 100 fractional-storage servers3901 to3909 spread over a wide geographical area. The servers store and deliver erasure-coded fragments belonging to data objects via the Internet. At least onecontact server3929 stores and delivers master data objects tousers3951,3952. The users' browsers approachcontact server3929 with a request for web pages. The contact server replies to approaching browsers with a master HTML or FLASH data object. The browsers, or browser plug-ins, parse the master HTML or FLASH data object, and obtain fragments fromservers3901 to3909 accordingly.
• In one embodiment, severalsmall contact servers3929 are used. These servers can have small communication bandwidths and small storage space as compared to the fractional-storage servers. Small contact servers are possible, as they only need to store and deliver master data objects. Master data objects are very small in comparison to typical media files stored on the fractional-storage servers. The small contact servers can be located anywhere on the Internet, as they do not carry the main traffic load required to transport data objects.
• In one embodiment, manysmall contact servers3931,3932, are located on edges of the Internet or at junctures of Internet transit networks and aggregation networks leading to last mile connections. Location on Internet edges allow these contact servers to be close to the users, and thus allow a quick response to master HTML data objects requested by the users. A user's browser can quickly render HTML texts, background, and sometimes images conveyed as standard HTML data objects and URLs in master data objects. More data-intensive files, FLASH, and Video streams may be obtained from fractional-storage servers, possibly with higher latencies.User3953 will prefer obtaining master data objects fromcontact server3932, as it is closest. Similarly,user3954 will prefer contactingserver3931. Bothusers3953 and3954 potentially use the same pool of fractional-storage servers3901 to3909 as fragment sources.
• In one embodiment, the functionality of a contact server is embedded in a fractional-storage server. Fractional-storage server3909′ includes contact server functionality.User3955contacts server3909′ with a request for a master data object. The master data object and any other standard data objects are sent to the user byserver3909′. Fragments belonging to distributed data objects are sent to the user by fractional-storage servers3901′,3902′,3909′
• In one embodiment, an assembling device external to a standard browser is used to obtain fragments of a data object, reconstruct the data object, and make the resulting data object available to the standard browser. The standard browser looks for the data objects at the identifying URL address, which leads to the assembling device. The assembling device receives the browser's request for the data object on one side, obtains relevant fragments from fractional-storage servers on the other side, reconstructs the data object, and sends it to the browser using standard HTTP.
• In one embodiment, an assembling device starts obtaining fragments and reconstructing segments of the data object after receiving a request from a browser, then immediately starts sending the reconstructed segments to the browser on the fly while more segments are being reconstructed.
• In one embodiment, the external assembling device is a software component residing inside the computer running the standard browser.
• In one embodiment, the external assembling device is a software component residing in some fractional-storage servers.
• In one embodiment, many small assembling devices are located on edges of the Internet or on junctures of Internet transit networks and aggregation networks leading to last mile connections. Location at Internet edges allows these assembling devices to be very close to the users, and thus send data objects via communication links that do not necessarily include Internet transit connections.
• In one embodiment, a method for gathering objects required for content rendering comprising the following steps: identifying at least one data object pointed to by a master data object; obtaining erasure-coded fragments belonging to the identified data object from fractional-storage servers; decoding the fragments; and rendering a presentation using the decoded data object together with additional rendering data. Optionally, the master data object is a Markup Language file, or a FLASH file, and the at least one data object is an image file, a video file, an audio file, a multimedia object, or a FLASH object.
• In one embodiment, a large scale distributed content delivery system comprising at least 100 fractional-storage servers spread over a wide geographical area, storing and delivering erasure-coded fragments belonging to data objects via the Internet, and contact servers delivering master data objects and addresses of the fractional-storage servers from which fragments belonging to data objects pointed to by the master data object can be obtained. Wherein a presentation is rendered based on the combined information obtained from a master data object and from at least one assembled data object. Optionally, the fractional-storage servers deliver fragments to client devices at a throughput of at least an order of magnitude higher than the throughput at which contact servers send master data objects to the client devices.
• In one embodiment, a content delivery system comprising a plurality of fractional-storage servers storing and delivering erasure-coded fragments, and a client device identifying at least one data object pointed to by a master data object, obtaining the erasure-coded fragments belonging to the identified data object from the fractional-storage servers, decoding the fragments, and rendering a presentation using the decoded data object together with additional rendering data. Optionally, the content delivery system further comprising a contact server delivering the master data object to the client device, and providing the client device with data regarding the addresses of the fractional storage servers. Optionally, the master data object is a Markup Language file, or a FLASH file. Optionally, the client device comprises an Internet browser or an Internet browser plug-in that identify at least one data object pointed to by a master data object. The client device obtains erasure-coded fragments belonging to the identified data object from the fractional storage servers, and decodes the fragments. Optionally, the presentation is rendered at least partially by the Internet browser or the Internet browser plug-in.
• By using a pull protocol or a push protocol with multiple sub-transmissions, the assembling device can obtain erasure-coded fragments from one, two or more different arrays of CDN servers and/or bandwidth amplification devices seamlessly.
• FIG. 39 illustrates one embodiment in which fractional-storage servers399aand399bare part of a server array. Fractional-storage servers399aand399bstore erasure-codedfragments310aand310bof a first content, and erasure-codedfragments320aand320bof a second content.Server393 is a control server that manages a pool of twelve registered bandwidth amplification devices surrounded byellipse599. One or more of the twelve bandwidth amplification devices may be assigned to one or more of the fractional-storage servers participating in the array. In the initial stage, no assignments have been made, and the twelve bandwidth amplification devices inpool599 are ready to receive instructions. Next, thecontrol server393 allocates six bandwidth amplification devices of group610aatoserver399a, and six bandwidth amplification devices of group610bbtoserver399b. Registering the bandwidth amplification devices with the servers may be processed using any appropriate method. From groups610aaand610bb, threebandwidth amplification devices610aand610bare allocated to store erasure-codedfragments310aand310brespectively (and, optionally, other erasure-coded fragments associated with consequent segments of the content); and threebandwidth amplification devices620aand620bare allocated to store erasure-codedfragments320aand320brespectively (and, optionally, other erasure-coded fragments associated with consequent segments of the content). After these allocations have been made, fractional-storage server399aforwards erasure-codedfragment310atogroup610a, and erasure-codedfragment320atogroup620a. Fractional-storage server399bforwards erasure-codedfragment310btogroup610b, and erasure-codedfragment320btogroup620b. At the end of the allocation and forwarding process, the bandwidth amplification devices are ready to act as bandwidth amplifiers to the fractional-storage server array399aand399b. Optionally, the allocation of bandwidth amplification devices to specific contents is performed by either thecontrol server393, or each fractional-storage server399aand399b.
• It is noted that each bandwidth amplification device is not restricted to storing and serving erasure-coded fragments associated with a single content, and it is possible for each bandwidth amplification device to store and serve multiple erasure-coded fragments associated with multiple contents. The tradeoff in this case is that the more erasure-coded fragments from more contents are stored and served, the lower the bandwidth amplification factor, since the rate of forwarding fragments from the server to the bandwidth amplification devices increases, while the outgoing bandwidth available for each bandwidth amplification device remains the same.
• In one embodiment, when a CDN server receives a request for an erasure-coded fragment, it may supply the erasure-coded fragment or supply an address of a bandwidth amplification device having an image of the requested erasure-coded fragment. Optionally, a bandwidth amplification device storing one erasure-coded fragment of a specific content also stores an image of some or all other erasure-coded fragments associated with the specific content (which are stored on the specific CDN server). Alternatively, the bandwidth amplification device stores unique erasure-coded fragments generated from the same segments used for generating the erasure-coded fragments stored on the specific CDN server. In these cases, the assembling device may approach the bandwidth amplification devices instead of the CDN server for the relevant erasure-coded fragments of the specific content until (i) the end of the content; (ii) a predefined time period elapses; (iii) receiving an appropriate message; or (iv) a combination of the aforementioned.
• In one embodiment, an assembling device tries to obtain an erasure-coded fragment or sub-transmission from the relevant server, and if the server does not have the necessary bandwidth to respond with fragment/s, the server relays the fragment request/s to relevant bandwidth amplification devices. The relevant bandwidth amplification devices can then send the fragment/s directly to the assembling device.
• In one embodiment, unique erasure-coded fragments can be distributed between two types of devices: (i) high bandwidth fractional-storage servers, such as CDN servers, and (ii) relatively low bandwidth and storage devices acting as bandwidth amplification devices, such as peer-to-peer (P2P) devices. Since the fragments distributed between the two types of devices are unique, any combination of devices, from both types, can be used to obtain a decodable set of fragments, if the combination of devices stores a decodable set of fragments. In one embodiment, there are at least ten times more bandwidth amplification devices than high bandwidth servers, and the redundancy factor used in decoding the fragments is greater than 10. In this case, the servers can be used all or most of the time, and the bandwidth amplification devices can be used from time to time, according to bandwidth requirements, and according to the availability of the bandwidth amplification devices. In one embodiment, the processes of obtaining a fragment from a server and from a bandwidth amplification device are essentially the same, and the fragments are essentially identical in construction and format. In one embodiment, the high redundancy factor needed to support a large hybrid array of servers and bandwidth amplification devices is achieved using rateless coding techniques.
• In one embodiment, the bandwidth amplification devices are used to supplement the streaming capabilities of the servers during peak traffic periods. In this case, the aggregated bandwidth of the fixed bandwidth lines connecting the servers to the Internet need not account for the full bandwidth demand. In one example, 1,000 CDN servers are connected to the Internet via fixed bandwidth lines having a total capacity of 10 Tbps. Demands above 10 Tbps, which occur during a 3-hour period in the evening, are met by utilizing additional fragment delivery bandwidth of P2P devices acting as bandwidth amplification devices.
• In one embodiment, the content is streaming content comprising approximately sequential segments, and the assembling devices attempt to obtain decodable sets of fragments from the servers. Upon failure or an estimated failure to obtain the sets, the assembling devices obtain the additionally needed fragments from one or more of the bandwidth amplification devices.
• In some embodiments, the assembling devices may obtain the fragments from the servers and/or from the P2P devices using a fragment pull protocol, a fragment pull protocol for high latency, and/or multiple sub-transmissions.
• In one embodiment, the bandwidth amplification devices are located at the user premises, and are connected to the Internet via ISPs. In one embodiment, the fractional-storage servers are CDN servers directly connected to the Internet backbone, or located in close topological proximity to the backbone.
• In one embodiment, the bandwidth amplification devices store both unique and replicated fragments.
• In one embodiment, a distributed streaming system comprising: fractional-storage servers and bandwidth amplification devices configured to store, correspondingly, a first and a second portions of rateless-coded fragments associated with approximately sequential segments of streaming content, shortly after the segments are progressively made available by a streaming source. Decodable sets of fragments associated with the segments can be obtained from approximately any combination of servers and bandwidth amplification devices storing fragments associated with the segments shortly after the segments are made available by the streaming source.
• FIG. 40 illustrates one example, in which real-time content source700 is segmented710a,710bon the fly, each segment is rateless-coded on thefly720ato720(N−1) and730ato730(N−1), a first portion of the fragments is distributed on the fly to fractional-storage servers740a′,740b′ and a second portion of the fragments is distributed on the fly toP2P devices750a′,750b′ acting as bandwidth amplification devices. Each distributed fragment is unique. Any combination of fragments out offragments720ato720(N−1) as an example, that comprise a decodable set of fragments, may be used to reconstructsegment710aon the fly. This can be done regardless of whether the fragments belonging to the combination are stored on servers or a P2P device. In one embodiment, the fragments are distributed approximately at the same time, and a short while after being encoded, to both servers and P2P devices.
• In one embodiment, the first and the second portions comprise unique rateless-coded fragments encoded with a redundancy factor that is determined according to the estimated popularity of the content being encoded, whereby the higher the popularity of the content, the higher the redundancy factor used to encode the content into fragments, and the larger the number of bandwidth amplification devices that store the fragments associated with the content.
• In one example, two contents are encoded into fragments using rateless-coding. The first content is encoded with a redundancy factor greater than 100, and the second content, which is estimated to be more popular, with a redundancy factor greater than 1,000. Approximately all fragments are unique. The first content's fragments are distributed to 100 fractional storage servers and to about 10,000 bandwidth amplification devices. The second content's fragments are distributed to the same 100 fractional storage servers and to about 100,000 bandwidth amplification devices. Assuming that the fragment delivery bandwidths of each server and amplification device are 100 Mbps and 1 Mbps respectively, the first content has a potential delivery bandwidth of (100×100 Mbps)+(1,000×1 Mbps)=11 Gbps, and the second content has a potential delivery bandwidth of (100×100 Mbps)+(10,000×1 Mbps)=20 Gbps. If different popularities are expected, or alternatively different popularities are encountered during streaming of the contents, then different redundancy factors may be used, and different numbers of amplification devices per content may be utilized accordingly.
• FIG. 41 illustrates one embodiment in which fractional-storage servers3799ato3799cstore a first portion of rateless-coded fragments; and a large number of P2Pbandwidth amplification devices3799dto3799jstore a second portion of the rateless-coded fragments. Decodable sets of fragments can be obtained from combinations of fragments from the first and second portions of the fragments. Optionally, the fragments are obtained approximately only from P2P devices serviced byISPs3771,3772 having communication lines estimated not to be overloaded by additional fragment traffic.
• In one embodiment, the P2P devices are spread over different time zones spanning at least three hours, and the fragments are obtained approximately only from P2P devices located in time zones in which the current local Internet traffic is relatively low in comparison to peak local traffic.
• In one example,ISP3771 is located on the US west coast, andISP3772 is located in Europe. At 6 PM PST, the general Internet traffic associated withISP3771 is at its peak level, meaning thatcommunication line3781 used byISP3771 is at or close to its maximal traffic capacity. At that time, the local time in Europe is midnight, and the general Internet traffic associated withISP3772 is at a low level, meaning thatcommunication line3782 used byISP3772 has a significant unutilized bandwidth. In this case, fragments are obtained by assembling devices approximately only from devicecombinations comprising servers3799ato3799c, andamplification devices3799hto3799j. Fragment delivered bydevices3799hto3799jpass via theuncongested communication line3782, and thus pose no threat toISP3772.Communication line3781 is not utilized for fragment delivery, and thusdevices3799dto3799gdo not contribute additional traffic loads to the alreadycongested line3781. At a different time of day the situation is reversed, the European ISP becomes congested while the US ISP is at low capacity, and the fragments are obtained accordingly.
• In one embodiment, all fractional-storage servers within the server array are replaced with client devices residing in customers' premises (CPEs). The CPEs perform the exact same functions as the server array, and in that respect may be referred to as a CPE array.
• FIG. 42 illustrates one embodiment, whereinsegment101aofcontent100 is encoded into erasure-codedfragments390ato390(M), such that any sufficient subset of the fragments can be used to reconstructsegment101a.Fragments390ato390(N) are stored in fractional-storage servers399ato399(N) respectively, and fragments390(N+1) to390(M) are stored in streamingserver399S. In one example, fragments390(N+1) to390(M) form a group of fragments which are sufficient to reconstructsegment101a.Subsequent segments101bto101jofcontent100 may be similarly encoded into additional fragments stored on the servers (not illustrated). Assemblingdevice309 uses two different protocols approximately simultaneously to retrieve fragments for segment reconstruction: (i) a push protocol, and (ii) a fragment pull protocol. Thepush protocol301S is used to deliver fragments390(N+1) to390(M) to assemblingdevice309. The push protocol may be RTP based or TCP-connection based, or any other type of transmission that does not require assemblingdevice309 to explicitly ask for each of fragments390(N+1) to390(M). In one example, fragments390(N+1) to390(M) are delivered to the assembling device using asingle RTP stream301S, such that upon reception of the fragments from the stream, the assembling device can immediately reconstructsegment101a. The fragment pull protocol is used by the assembling device to retrieve additional fragments that may be needed to reconstructsegment101aif one or more fragments out of fragments390(N+1) to390(M) fail to reach the assembling device. In one example, fragment390(N+2) fails to reach the assembling device due to Internet packet loss conditions (referred to as fragment loss). The assembling device, after concluding that fragment390(N+2) is missing, uses a fragment pull protocol to retrieve a substitute fragment out of one of the fractional-storage servers390ato390(N), and uses this fragment to complete the reconstruction of thesegment101a(any one offragments390ato390(N) will do). For example, the assembling device choosesfragment390aas the one additional fragment, by requesting and receiving it303afromserver399a, using a fragment pull protocol. If more fragments out of fragments390(N+1) to390(M) fail to reach theassembling device309, it may compensate by pulling substitute fragments from some or all ofservers399ato399(N), illustrated as fragment pull protocol requests andresponses303ato303(N)).
• In one embodiment, the fragment pull protocol requests for additional needed fragments are not made to fractional-storage servers399ato399(N), but are rather made toserver399S. In this case, the assembling device asksserver399S to retransmit the fragment which has failed to arrive. In this embodiment, only fragments that fail to reach the assembling device via thepush transmission301S cause an added communication overhead in the form of explicit fragment pull protocol requests, such that if no fragments are actually lost overtransmission301S, there is no need for fragment pull requests303ato303(N).
• In some embodiments, the push protocol is implemented using one or more sub-transmissions. Optionally, a push protocol transmission is implemented using multiple sub-transmissions, each transporting a fraction of the fragments transmitted by the push protocol transmission. A sub-transmission may be transported using an IP stream such as RTP, an HTTPS session, or any other form of transporting a sequence of fragments between a source server and a destination assembling device.
• In one embodiment, an assembling device starts retrieving fragments using only fragment pull protocol processes, and then, when concluding that a specific server is responsive enough, instructs it to start sending a push-transmission for the remaining segments. In this case, the assembling device may start with pure pull-protocol based fragment retrieval, and gradually switch to push-protocol transmissions, up to the point that approximately all fragments are delivered using push-transmissions, and using the pull requests only as a means to overcome failure of obtaining specific fragments by the assembling device. In one embodiment, the fragment pull protocol and the push protocol are used interchangeably to obtain enough fragments to reconstruct segments. In one embodiment, the assembling device may start to obtain fragments using a push protocol and then switch to a fragment pull protocol. In one embodiment, the assembling device may use both fragment pull protocol and push protocol to obtain fragments at the same time, wherein the assembling device may change the ratio Fpull/Fpush on-the-fly to any value between zero and infinity, where Fpull denotes the number of fragments associated with a certain segment that are obtained using a fragment pull protocol, and Fpush denotes the number of fragments associated with the certain segment that are obtained using a push protocol.
• In the claims, sentences such as “wherein the assembling device is configured to use a fragment pull protocol to obtain the fragments” and “wherein the assembling device is configured to use sub-transmissions to obtain the fragments” are to be interpreted as open claim language. Therefore, an assembling device configured to use a fragment pull protocol to obtain fragments may also obtain fragments using sub-transmissions, and vice-versa.
• In the claims, a sentence such as “the erasure-coded fragments support source-selection diversity” is to be interpreted as fragments encoded using any kind of erasure-code that can produce N unique fragments, from which C combinations of decodable sets of fragments can be selected, wherein C is much greater than N. Standard parity checks, standard checksums, and standard cyclic redundancy checks (CRC) are examples of codes that do not support source-selection diversity.
• In this description, numerous specific details are set forth. However, the embodiments of the invention may be practiced without some of these specific details. In other instances, well-known hardware, software, materials, structures and techniques have not been shown in detail in order not to obscure the understanding of this description. In this description, references to “one embodiment” mean that the feature being referred to may be included in at least one embodiment of the invention. Moreover, separate references to “one embodiment” or “some embodiments” in this description do not necessarily refer to the same embodiment. Illustrated embodiments are not mutually exclusive, unless so stated and except as will be readily apparent to those of ordinary skill in the art. Thus, the invention may include any variety of combinations and/or integrations of the features of the embodiments described herein.
• Although some embodiments may depict serial operations, the embodiments may perform certain operations in parallel and/or in different orders from those depicted. Moreover, the use of repeated reference numerals and/or letters in the text and/or drawings is for the purpose of simplicity and clarity and does not in itself dictate a relationship between the various embodiments and/or configurations discussed. The embodiments are not limited in their applications to the details of the order or sequence of steps of operation of methods, or to details of implementation of devices, set in the description, drawings, or examples. Moreover, individual blocks illustrated in the figures may be functional in nature and do not necessarily correspond to discrete hardware elements. While the methods disclosed herein have been described and shown with reference to particular steps performed in a particular order, it is understood that these steps may be combined, sub-divided, or reordered to form an equivalent method without departing from the teachings of the embodiments. Accordingly, unless specifically indicated herein, the order and grouping of the steps is not a limitation of the embodiments. Furthermore, methods and mechanisms of the embodiments will sometimes be described in singular form for clarity. However, some embodiments may include multiple iterations of a method or multiple instantiations of a mechanism unless noted otherwise. For example, when a controller or an interface are disclosed in an embodiment, the scope of the embodiment is intended to also cover the use of multiple controllers or interfaces.
• Certain features of the embodiments, which may have been, for clarity, described in the context of separate embodiments, may also be provided in various combinations in a single embodiment. Conversely, various features of the embodiments, which may have been, for brevity, described in the context of a single embodiment, may also be provided separately or in any suitable sub-combination.
• Embodiments described in conjunction with specific examples are presented by way of example, and not limitation. Moreover, it is evident that many alternatives, modifications and variations will be apparent to those skilled in the art. It is to be understood that other embodiments may be utilized and structural changes may be made without departing from the scope of the embodiments. Accordingly, it is intended to embrace all such alternatives, modifications and variations that fall within the spirit and scope of the appended claims and their equivalents.

Claims (20)

1) A streaming system comprising: assembling servers located at or close to the edges of the Internet and spread over a wide area, fractional-storage CDN servers located close to or on the Internet backbone, and client devices spread over a wide area; each assembling server is configured to obtain from the CDN servers erasure-coded fragments associated with segments of streaming content according to an order that enables the assembling server to start streaming the content to its associated clients shortly after reconstructing the first segment.

2) The streaming system ofclaim 1, wherein the assembling servers are configured to obtain the fragments using a fragment pull protocol.

3) The streaming system ofclaim 2, wherein at least one of the assembling servers is located at a juncture of an Internet transit network and a last mile network coupled to at least one of the client devices.

4) The streaming system ofclaim 1, wherein the assembling servers are configured to operate a pull protocol to obtain the fragments from the fractional-storage CDN servers, operate a streaming protocol to stream the reconstructed segments to the client devices, and start streaming while obtaining the fragments.

5) The streaming system ofclaim 4, wherein the fragments pass through a transit network connecting an ISP servicing the client device to the Internet, and the reconstructed segments are streamed through a last mile network connecting the ISP to the client device that is located at a user premises.

6) The streaming system ofclaim 4, wherein the fragments pass through a network connecting the assembling server to its servicing ISP, and the reconstructed segments are streamed through a home network.

7) The streaming system ofclaim 4, wherein the erasure-coding is rateless-coding, and the assembling servers and the client devices are located at a user premises.

8) The streaming system ofclaim 1, wherein the client devices are associated with nearby assembling servers.

9) The streaming system ofclaim 8, wherein the erasure-coding is rateless-coding, the client devices are located at a user premises, and the assembling servers are configured to obtain the fragments using push protocol.

10) An apparatus comprising: an assembling server configured to obtain from fractional-storage CDN servers located close to or on the Internet backbone at least most of the erasure-coded fragments needed to reconstruct a segment of content comprising multiple segments; the assembling server is further configured to reconstruct the segment and transmit the reconstructed segment or a transcoded version of the segment to a client device.

11) The apparatus ofclaim 10, wherein the segments are approximately sequential segments of streaming content, the fragments are obtained and the segments are reconstructed according to an order that enables the assembling server to start transmitting the segments to the client device using a streaming protocol shortly after reconstructing the first segment, and the transmission at least partially overlaps in time with the obtainment.

12) The apparatus ofclaim 11, wherein the assembling server is configured to obtain the fragments using a fragment pull protocol, and the transmission starts shortly after reconstructing the first segment.

13) The apparatus ofclaim 11, wherein the assembling server is located at or close to the edge of the Internet, and is configured to obtain the fragments using a fragment pull protocol.

14) The apparatus ofclaim 11, wherein the assembling server is located at a juncture of an Internet transit network and a last mile network coupled to the client device, and is configured to obtain the fragments using a fragment pull protocol.

15) The apparatus ofclaim 10, wherein the erasure-coding is rateless-coding; and the assembling server communicates with the fractional-storage CDN servers via Internet infrastructure that requires an Internet transit fee, and communicates with the client device via a second network that does not require an additional Internet transit fee.

16) A method comprising: receiving, by a first device from fractional-storage servers, erasure-coded fragments associated with segments of streaming content; reconstructing approximately sequential segments from fragments comprising the received fragments; and streaming the reconstructed segments or a transcoded version of the segments to a second device shortly after reconstructing the first segment; wherein the steps of receiving and streaming at least partially overlap in time.

17) The method ofclaim 16, wherein the erasure-coded fragments support source-selection diversity, and the fractional-storage servers are fractional-storage CDN servers located close to or on the Internet backbone.

18) The method ofclaim 17, wherein the erasure-coding is rateless-coding potentially resulting in fragments having a limitless redundancy factor; and receiving the fragments by the first device comprises receiving the fragments using a fragment pull protocol for high latency.

19) The method ofclaim 17, wherein receiving the fragments by the first device comprises receiving the fragments using a fragment pull protocol for high latency; and further comprising the second device interacting with the first device as if the first device stores the content locally; and the first device converting the interactions with the second device into corresponding interactions with the fractional-storage CDN servers.

20) The method ofclaim 19, wherein the interactions between the second device and the first device comprise requests to start streaming content and trick-play instructions.

Images