Patent Description:
Embodiments of the present invention relate generally to streaming video technology and, more specifically, to techniques for evaluating a video rate selection algorithm over a completed streaming session.

A typical video streaming service provides access to a library of media titles that can be viewed on a range of different client devices, where each client device usually connects to the video streaming service under different connection and network conditions. In many implementations, a client device that connects to a video streaming service executes an endpoint application. The endpoint application implements a video rate selection algorithm that attempts to optimize the visual quality experienced during playback of the media title on the client device while avoiding playback interruptions due to re-buffering events. In these types of implementations, for each source chunk of a media title, the video rate selection algorithm attempts to select the highest possible quality encoded version of the source chunk to stream to the client device based on the available network throughput.

In general, the overall quality of experience (QoE) that the video streaming service provides to viewers depends on the ability of the video rate selection algorithm to select a sequence of encoded chunks that optimizes visual quality without exceeding the available network throughput. Accordingly, being able to evaluate and fine-tune the performance of video rate selection algorithms across a range of intended operating scenarios is an important aspect of providing an effective video streaming service. The intended operating scenarios for a typical video streaming service include permutations across a wide range of network environments, device capabilities, video content complexities, etc..

In one approach to evaluating the performance of a video rate selection algorithm, a benchmark application retrospectively compares the performance of the video rate selection algorithm to the performance of an optimal video rate selection algorithm for numerous completed streaming sessions representing a range of operating scenarios. An optimal video rate selection algorithm identifies a sequence of encoded chunks that provides the best visual quality as measured via a QoE metric value without exceeding the available network throughput. For each of the completed streaming sessions, the benchmark application computes an optimal QoE metric value for a QoE metric based the optimal video rate selection algorithm and a recorded network throughout trace. The benchmark application then computes gaps between the actual QoE metric values achieved via the video rate selection algorithm and the optimal QoE metric values. Subsequently, the video streaming service provider investigates the gaps to identify operating scenarios during which the performance of the video rate algorithm is subpar. Finally, the video streaming service provider fine-tunes the video rate algorithm to improve the performance for the identified operating scenarios.

One drawback of this first approach is that optimal video rate selection is an NP-hard problem, where the abbreviation "NP" stands for non-deterministic polynomial time. As is well-understood, an NP-hard problem cannot be solved efficiently using known techniques. Because executing the optimal video rate selection algorithm for each completed streaming session is highly inefficient in view of the NP-hard problems, computing the numerous optimal QoE metric values required to comprehensively evaluate the video rate selection algorithm is usually prohibitively time consuming.

Given the above drawbacks, many video streaming service providers do not attempt to compare the performance of a video rate selection algorithm to the performance of an optimal video rate selection algorithm. Instead, in an effort to improve the performance of an existing, current video rate selection algorithm, a typical video streaming provider develops a new, candidate video rate selection algorithm. The candidate video rate selection algorithm executes faster than an optimal video rate selection algorithm, but provides sub-optimal visual quality. Subsequently, the video streaming service provider performs A/B testing to compare the performance of the candidate video rate selection algorithm to the current video rate selection algorithm. In A/B testing, two large groups of users are identified. Each group of users is associated with a representative mix of network environments and device capabilities. Group "A" receives the candidate video rate selection algorithm, while group "B" receives the current video rate selection algorithm. Over a period of time (e.g., a week), a comparison application collects and compares the "A" QoE metric values achieved via the candidate video rate selection algorithm to the "B" QoE metric values achieved via the current video rate selection algorithm. If the comparisons indicate that the candidate video rate selection algorithm outperforms the current video rate selection algorithm, then the video streaming service provider replaces the current video rate selection algorithm with the candidate video rate selection algorithm. In this fashion, the video streaming service provider is able to incrementally improve the performance of video streaming service.

One drawback of this second approach is that a current video rate selection algorithm in use as part of a video streaming service may perform reasonably well in many operating scenarios. Consequently, developing a candidate video rate selection algorithm that can outperform the current video rate selection algorithm can be a challenging, time-consuming, and primarily manual process. Further, if the candidate video rate selection algorithm fails to outperform the current video rate selection algorithm, then the process of comparing the candidate video selection algorithm to the current video rate selection algorithm provides no guidance on how to generate a new candidate video rate selection algorithm that actually outperforms the current video rate selection algorithm.

As the foregoing illustrates, more effective techniques for evaluating video rate selection algorithms are what is needed in the art.

Documents <CIT>, <CIT>, and <NPL> describe adaptive bitrate streaming and bitrate selection algorithms.

One embodiment of the present invention sets forth a computer-implemented method for evaluating one or more aspects of a video streaming service. The method includes computing a first feasible download end time associated with a source chunk of a media title based on a network throughput trace and a subsequent feasible download end time associated with a subsequent source chunk of the media title; selecting a first encoded chunk from a set of encoded chunks associated with the source chunk based on the network throughput trace, the first feasible download end time, and a preceding download end time associated with a preceding source chunk of the media title; and computing a total download size associated with a sequence of encoded chunks associated with the media title based on the number of encoded bits included in the first encoded chunk, where the performance of at least one aspect of a streaming video infrastructure is evaluated based on the total download size.

At least one technical advantage of the disclosed techniques relative to prior art solutions is that the disclosed techniques more efficiently determine an upper bound for the visual quality associated with a media title over a completed streaming session. In that regard, the disclosed techniques correlate the upper bound of visual quality to the total download size for a sequence of encoded chunks spanning the duration of the media title. Thus, the upper bound of visual quality can be determined by computing the total download size for the sequence of encoded chunks downloaded during playback of the media title, where each encoded chunk is comprised of a particular number of encoded bits. Notably, determining the total download size is computationally more efficient than prior art approaches that experience NP-hard problems. More specifically, unlike prior art approaches to computing an upper bound for visual quality that are NP-hard, the time required to compute the total download size using the disclosed techniques is on the order of the total number of source chunks making up the media title. Consequently, the time and computational resources required to evaluate the visual quality associated with a given video rate selection algorithm across a wide variety of network environments, device capabilities, and video content complexities using the disclosed techniques can be substantially reduced relative to prior art approaches. These technical advantages provide one or more technological advancements over the prior art.

So that the manner in which the above recited features of the present invention can be understood in detail, a more particular description of the invention, briefly summarized above, may be had by reference to embodiments, some of which are illustrated in the appended drawings. It is to be noted, however, that the appended drawings illustrate only typical embodiments of this invention and are therefore not to be considered limiting of its scope, for the invention may admit to other equally effective embodiments.

In the following description, numerous specific details are set forth to provide a more thorough understanding of the present invention. However, it will be apparent to one of skilled in the art that the present invention may be practiced without one or more of these specific details.

The overall visual experience that a video streaming service provides to viewers depends on the ability of a video rate selection algorithm operating on the user-side device to select a sequence of encoded chunks that optimizes visual quality from the user's perspective without exceeding the available network throughput. Therefore, being able to evaluate the efficacy of different video rate selection algorithms is an important factor in the video streaming service's ability to provide high-quality viewing experiences to customers. Prior art techniques for evaluating the performance of video rate selection algorithms are prohibitively time consuming or provide little or no guidance on how to improve a given video rate selection algorithm.

For example, some prior-art techniques involve comparing an optimal average visual quality obtained using an optimal video rate selection algorithm to the actual average visual quality obtained using a given video rate selection algorithm for numerous completed streaming sessions. The completed streaming sessions represent a wide range of intended operating scenarios, where each operating scenario is a different permutation of a network environment, device capability, video content complexity, etc. However, known techniques for computing the optimal average visual quality for each completed streaming session are NP-hard, where the abbreviation "NP" stands for non-deterministic polynomial time. As is well-understood, an NP-hard problem cannot be solved efficiently using known techniques. Because computing the optimized average visual quality for each completed streaming session is highly inefficient, using such techniques to evaluate the video rate selection algorithm is usually prohibitively time consuming.

To address this problem, the disclosed techniques compute an upper bound on the total number of bits that can be used to encode the video content viewed during a completed streaming session. Notably, the total number of bits that are used to encode the video content correlates to an average visual quality associated with that. Thus, by comparing the total number of bits that are used to encode the video content viewed during the completed streaming session to the upper bound on the total number of bits that can be used to encode that same video content, the disclosed techniques allow the video streaming service to efficiently gauge the effectiveness of a given video rate selection algorithm. Further, the video streaming service provider can perform this type of comparison across numerous completed streaming sessions to identify operating scenarios during which the performance of the video rate algorithm is subpar. Subsequently, the video streaming service provider can fine-tune the video rate selection algorithm to enhance the overall customer viewing experience for the identified operating scenarios going forward.

In some embodiments, a hindsight application includes, without limitation, a feasibility engine and a greedy engine. The feasibility engine sequentially processes each source chunk included in a media title in the reverse playback order. For the nth source chunk, the feasibility engine computes an nth feasible download end time that is the latest possible time that a download of the smallest encoded chunk derived from the nth source chunk can complete during an uninterrupted playback of the media title. In operation, for a given source chunk, the feasibility engine sets a feasible download end time equal to the earlier of a playback start time associated with the source chunk and a feasible download start time associated with the subsequent source chunk. The feasibility engine computes the "subsequent" feasible download start time based on the feasible download end time associated with the subsequent source chunk, the number of bits included in the smallest encoded chunk derived from the subsequence source chunk, and a network throughput trace associated with a completed streaming session.

The greedy engine then sequentially processes each source chunk included in the media title in the playback order. For each source chunk included in the media title, the greedy engine greedily selects an encoded chunk derived from the source chunk. The greedy engine selects the encoded chunk based on a download end time associated with the preceding source chunk, the feasible download end time associated with the source chunk, and the network throughput trace. More precisely, the greedy engine selects the largest encoded chunk derived from the source chunk that allows an uninterrupted playback of the media title. The greedy engine tracks the selected encoded chunks via a version selection sequence. After processing all of the source chunks, the greedy engine sums the total number of bits included in each of the selected encoded chunks to compute a total download size. The total download size is an upper bound on the total number of bits that can be used to encode that media title during the streaming session.

Advantageously, the hindsight application addresses various limitations of conventional techniques for evaluating video rate algorithms. In particular, the hindsight application efficiently determines an upper bound for the visual quality associated with a media title over a completed streaming session. In that regard, as noted above, the hindsight application correlates the upper bound of visual quality to the total download size. Because the time required for the hindsight application to compute the total download size is on the order of the total number of source chunks making up the media title, the time required to evaluate the visual quality associated with a given video rate selection algorithm across a wide variety of operating scenarios using the hindsight application can be substantially reduced relative to prior art approaches. For example, the time required to compute an upper bound on a visual quality score for a movie via the hindsight application could be on the order of thousands of times less than the time required to compute an upper bound of the visual quality score for the movie via an optimal video rate algorithm. In addition, the video streaming service provider can fine-tune the video rate selection algorithm to improve the performance based on the version selection sequence associated with the total download size.

<FIG> is a conceptual illustration of a system <NUM> configured to implement one or more aspects of the present invention. As shown, the system <NUM> includes, without limitation, a compute instance <NUM>. In alternative embodiments, the system <NUM> may include any number of compute instances <NUM>. For explanatory purposes, multiple instances of like objects are denoted with reference numbers identifying the object and parenthetical numbers identifying the instance where needed. In various embodiments, any number of the components of the system <NUM> may be distributed across multiple geographic locations or included in one or more cloud computing environments (i.e., encapsulated shared resources, software, data, etc.) in any combination.

As shown, the compute instance <NUM> includes, without limitation, a processor <NUM> and a memory <NUM>. The processor <NUM> may be any instruction execution system, apparatus, or device capable of executing instructions. For example, the processor <NUM> could comprise a central processing unit (CPU), a graphics processing unit (GPU), a controller, a microcontroller, a state machine, or any combination thereof. The memory <NUM> stores content, such as software applications and data, for use by the processor <NUM> of the compute instance <NUM>.

The memory <NUM> may be one or more of a readily available memory, such as random access memory (RAM), read only memory (ROM), floppy disk, hard disk, or any other form of digital storage, local or remote. In some embodiments, a storage (not shown) may supplement or replace the memory <NUM>. The storage may include any number and type of external memories that are accessible to the processor <NUM>. For example, and without limitation, the storage may include a Secure Digital Card, an external Flash memory, a portable compact disc read-only memory (CD-ROM), an optical storage device, a magnetic storage device, or any suitable combination of the foregoing.

In general, the compute instance <NUM> is configured to implement one or more applications. For explanatory purposes only, each application is depicted as residing in the memory <NUM> of a single compute instance <NUM> and executing on a processor <NUM> of the single compute instance <NUM>. However, as persons skilled in the art will recognize, the functionality of each application may be distributed across any number of other applications that reside in the memories <NUM> of any number of compute instances <NUM> and execute on the processors <NUM> of any number of compute instances <NUM> in any combination. Further, the functionality of any number of applications may be consolidated into a single application or subsystem.

In particular, the compute instance <NUM> is configured to generate one or more evaluation criteria for an aspect of a video streaming service, such as a quality of a video rate selection algorithm or a quality of a transport (e.g., a network). A typical video streaming service provides access to a library of media titles that can be viewed on a range of different client devices, where each client device usually connects to the video streaming service under different connection and network conditions. In many implementations, a client device that connects to a video streaming service executes an endpoint application. The endpoint application implements a video rate selection algorithm that attempts to optimize the visual quality experienced during playback of the media title on the client device while avoiding playback interruptions due to re-buffering events. In these types of implementations, for each source chunk of a media title, the video rate selection algorithm attempts to select the highest possible quality encoded version of the source chunk to stream to the client device based on the available network throughput.

To address the above problems, the system <NUM> includes, without limitation, a hindsight application <NUM>. The hindsight application <NUM> resides in the memory <NUM> and executes on the processor <NUM> in linear time. The hindsight application <NUM> implements greedy optimization techniques to generate a total download size <NUM> associated with a version selection sequence <NUM> based on a network throughput trace <NUM>, a media title <NUM>, and a chunk map <NUM> associated with the media title <NUM>. The network throughput trace <NUM> indicates the available network bandwidth as a function of time over a completed streaming session.

As shown, the media title <NUM> is partitioned into N source chunks <NUM> of video content. The chunk map <NUM> includes, without limitation, M encodes <NUM>, where each of the encodes <NUM> is a different encoded version of the media title <NUM>. Each of the encodes <NUM> is partitioned into N encoded chunks <NUM>, where each encoded chunk <NUM> includes encoded video content derived from the corresponding source chunk <NUM>. As referred to herein, each of the encoded chunks <NUM> that is derived from a given source chunk <NUM> is associated with the source chunk <NUM>. As persons skilled in the art will recognize, during a streaming session, the endpoint application may select and download different encoded chunks <NUM> of different encodes <NUM> in any combination. For example, the client application could consecutively download the encoded chunk <NUM>(<NUM>) of the encode <NUM>(<NUM>), the encoded chunk <NUM>(<NUM>) of the encode <NUM>(<NUM>), the encoded chunk <NUM>(<NUM>) of the encode <NUM>(<NUM>), etc. In alternate embodiments, the chunk map <NUM> may be specified in any technically feasible fashion.

Typically, one or more of the encoded chunks <NUM> are downloaded before the playback of the media title <NUM> begins. The encoded chunks <NUM>(<NUM>)-<NUM>(P-<NUM>) that are downloaded before the playback of the media title <NUM> begins are also referred to herein as the "pre-buffered" encoded source chunks <NUM>(<NUM>)-<NUM>(P-<NUM>). Further, the source chunks <NUM>(<NUM>)-<NUM>(P-<NUM>) associated with the pre-buffered encoded chunks <NUM>(<NUM>)-<NUM>(P-<NUM>) are also referred to herein as pre-buffered source chunks <NUM>(<NUM>)-<NUM>(P-<NUM>). The remaining encoded chunks <NUM>(P)-<NUM>(N) are also referred to herein as the "playback-buffered" encoded chunks <NUM>(P)-<NUM>(N). Further, the source chunks <NUM>(P)-<NUM>(N) associated with the playback-buffered encoded chunks <NUM>(P)-<NUM>(N) are also referred to herein as playback-buffered source chunks <NUM>(P)-<NUM>(N). For explanatory purposes only, the download of the source chunk <NUM>(P) starts at the same time as the playback start time associated with the media title <NUM>. In alternate embodiments, the download of the source chunk <NUM>(P) may start at any technically feasible time, and the techniques described herein are modified accordingly.

The version selection sequence <NUM> specifies a sequence of playback-buffered encoded chunks <NUM> that could retrospectively be downloaded during the streaming session characterized by the network throughput trace <NUM> to enable uninterrupted playback of the media title <NUM>. As shown, the version selection sequence <NUM> includes, without limitation, version indices <NUM>(P)-<NUM>(N). The version index <NUM>(n) is an integer m in the range of <NUM>-M that specifies the encoded chunk <NUM>(n) of the encode <NUM>(m). For example, a version index <NUM>(<NUM>) that is equal to <NUM> specifies the encoded chunk <NUM>(<NUM>) of the encode <NUM>(<NUM>). In this fashion, for each of the playback-buffered source chunks <NUM>, the version selection sequence <NUM> specifies one of the encoded versions of the source chunk <NUM>. In alternate embodiments, the version selection sequence <NUM> may be specified in any technically feasible fashion.

The total download size <NUM> is the total number of encoded video bits that are downloaded during playback of the media title <NUM> when the playback-buffered encoded chunks <NUM> specified via the version selection sequence <NUM> are streamed to a client device. As described in greater detail below, the hindsight application <NUM> greedily maximizes the total download size <NUM> while ensuring an uninterrupted playback of the media title <NUM>. Notably, the execution time required to compute the total download size <NUM> is on the order of the total number of source chunks <NUM>. And, as persons skilled in the art will recognize, because visual quality typically increases as the number of encoded video bits increases, the total download size <NUM> correlates to an upper bound for visual quality. Consequently, the execution time required to compute an upper bound for visual quality associated with the media title <NUM> is linear. Further, as part of greedily optimizing the total download size <NUM>, the hindsight application <NUM> indirectly optimizes the version selection sequence <NUM> with respect to visual quality.

As shown, the hindsight application includes, without limitation, a feasibility engine <NUM> and a greedy engine <NUM>. The feasibility engine <NUM> includes, without limitation, minimum download sizes <NUM>(P)-<NUM>(N). Upon receiving the media title <NUM>, the chunk map <NUM> and the network throughput trace <NUM>, the feasibility engine <NUM> sequentially processes each of the playback-buffered source chunks <NUM> in the reverse playback order. The reverse playback order starts at the source chunk <NUM>(N) and ends at the source chunk <NUM>(P).

In general, for each playback-buffered source chunk <NUM>, the feasibility engine <NUM> computes a feasible download end time <NUM>. The feasible download end time <NUM> specifies the latest time at which a download of the associated playback-buffered encoded chunk <NUM> can end that allows an uninterrupted playback of the media title <NUM> during the streaming session characterized by the network throughput trace <NUM>. Further, after processing the playback buffered source chunks <NUM>, the feasibility engine <NUM> determines whether an uninterrupted playback of the media title <NUM> is possible during the streaming session characterized by the network throughput trace <NUM>.

During an uninterrupted playback of the media title <NUM>, for each of the source chunks <NUM>(x), the associated playback-buffered encoded chunk <NUM>(x) finishes downloading before the proceeding source chunks <NUM>(<NUM>)-<NUM>(x-<NUM>) finish playing back. Consequently, the feasible download end time <NUM>(x) associated with the source chunk <NUM>(x) is the latest time that satisfies both of two different criteria. The first criterion is that the associated encoded chunk <NUM>(x) finishes downloading prior to an associated download deadline (not shown in <FIG>).

The download deadline associated with the source chunk <NUM>(x) specifies the latest time for the encoded chunk <NUM>(x) to finish downloading that allows an uninterrupted playback of the source chunk <NUM>(x) itself. Consequently, the download deadline associated with the playback-buffered source chunk <NUM>(x) is equal to the time at which the playback of the source chunk <NUM>(x) begins during an uninterrupted playback of the media title <NUM>. Accordingly, the download deadline associated with the source chunk <NUM>(x) is equal to the following summation (<NUM>): <MAT>.

In summation (<NUM>), τ(i) is the playback duration of the source chunk <NUM>(i). As persons skilled in the art will recognize, the playback duration τ(i) of a given encoded chunk <NUM>(i) derived from a given source chunk <NUM>(i) is equal to the playback duration of any other encoded chunk <NUM>(i) derived from the source chunk <NUM>(i).

The second criteria is that the bandwidth remaining after the encoded source chunk <NUM>(x) finishes downloading is larger than the sum of the minimum download sizes <NUM>(x+<NUM>)-<NUM>(N). For each of the source chunks <NUM>(x), the feasibility engine <NUM> sets the associated minimum download size <NUM>(x) equal to the number of encoded bits included in the smallest encoded chunk <NUM>(x). For example, suppose that the chunk map <NUM> includes the three encodes <NUM>(<NUM>)-<NUM>(<NUM>). Further, suppose that the number of encoded bits included in the encoded chunk <NUM>(<NUM>) that is included in the encode <NUM>(<NUM>) is smaller than both the number of encoded bits included in the encoded chunk <NUM>(<NUM>) that is included in the encode <NUM>(<NUM>) and the number of encoded bits included in the encoded chunk <NUM>(<NUM>) that is included in the encode <NUM>(<NUM>). In such a scenario, the feasibility engine <NUM> sets the minimum download size <NUM>(<NUM>) equal to the number of encoded bits included in the encoded chunk <NUM>(<NUM>) that is included in the encode <NUM>(<NUM>).

To determine the latest time at which the download of the encoded chunk <NUM>(x) can end that satisfies the second criteria, the feasibility engine <NUM> determines the feasible download start time (not shown in <FIG>) associated with the source chunk <NUM>(x+<NUM>). As referred to herein, the feasible download start time associated with the source chunk <NUM>(x+<NUM>) is the latest time that a download of the smallest encoded chunk <NUM>(x+<NUM>) can hard before the feasible download end time <NUM>(x+<NUM>). The feasibility engine <NUM> may determine the feasible download start time associated with the source chunk <NUM>(x+<NUM>) in any technically feasible fashion.

For instance, in some embodiments, the feasibility engine <NUM> calculates the time interval required to download the minimum download size <NUM>(x+<NUM>) based on the network throughput <NUM>, where the time interval spans from the feasible download start time associated with the source chunk <NUM>(x+<NUM>) to the feasible download end time <NUM>(x+<NUM>). More precisely, the feasibility engine <NUM> determines the time interval based on the area under the network throughput trace <NUM> ending at the feasible download end time <NUM>(x+<NUM>) that is equal to the minimum download size <NUM>(x+<NUM>).

In other embodiments, the feasibility engine <NUM> solves the following equation (<NUM>) for s to compute the feasible download start time associated with the source chunk <NUM>(x+<NUM>):: <MAT>.

In the equation (<NUM>), t is time, FDE(x+<NUM>) is the feasible download end time <NUM>(x+<NUM>), T(t) is the network throughput trace <NUM>, and MDS(x+<NUM>) is the minimum download size <NUM>(x+<NUM>). Since the feasibility engine <NUM> processes the source chunks <NUM> in the reverse playback order, the feasibility engine <NUM> computes the feasible download end time <NUM>(x+<NUM>) before computing the feasible download end time <NUM>(x).

The feasibility engine <NUM> then combines the first criteria and the second criteria to compute the feasibility deadline <NUM>(x). For instance, in some embodiments, the feasibility engine <NUM> solves the following equations (<NUM>) to compute the feasible download end time <NUM>(x) associated with the source chunk <NUM>(x): <MAT>.

In summation (<NUM>), DD(x) is the download deadline associated with the source chunk <NUM>(x). Note that if x is equal to N, then there is no subsequent source chunk <NUM>(x+<NUM>), consequently, the feasibility deadline <NUM>(x) is equal to the download deadline associated with the source chunk <NUM>(x).

After computing the feasible download end times <NUM>(P)-<NUM>(N), the feasibility engine <NUM> implements equation (<NUM>) to compute the feasible download start time associated with the source chunk <NUM>(P). If the feasible download start time associated with the source chunk <NUM>(P) is earlier than the playback start time associated with the media title <NUM>, then the feasibility engine displays an error message, and the hindsight application <NUM> terminates. The error message indicates that uninterrupted playback of the media title <NUM> is not possible during the streaming session characterized by the network throughput trace <NUM>.

As shown, the greedy engine <NUM> includes, without limitation, the download sizes <NUM>(P)-<NUM>(N) and the download end times <NUM>(P)-<NUM>(N). Upon receiving the feasible download end times <NUM>(P)-<NUM>(N), the greedy engine <NUM> generates the version selection sequence <NUM> and the corresponding total download size <NUM>. In general, the greedy engine <NUM> performs greedy optimization operations to generate the version selection sequence <NUM>,.

More precisely, the greedy engine <NUM> sequentially processes each of the playback-buffered source chunks <NUM> in the playback order. For a given playback-buffered source chunk <NUM>(x), the greedy engine <NUM> selects the largest associated encoded chunk <NUM>(x) that allows uninterrupted playback of the media title <NUM> and then computes the download end time <NUM>(x). The greedy engine <NUM> may select the largest associated encoded chunk <NUM>(x) that allows uninterrupted playback of the media title <NUM> in any technically feasible fashion.

For instance, in some embodiments, the greedy engine <NUM> generates an availability window (not shown in <FIG>) that spans from the download end time <NUM>(x-<NUM>) to the feasible download end time <NUM>(x). The greedy engine <NUM> then computes a maximum download size based on the network throughput trace <NUM>, the download end time <NUM>(x-<NUM>), and the feasible download end time <NUM>(x). The maximum download size is the total number of encoded bits that can be included in the encoded chunk <NUM>(x) that allows an uninterrupted playback of the media title <NUM>. In other embodiments, the greedy engine <NUM> computes the maximum download size associated with the source chunk <NUM>(x) based on the following integral (<NUM>): <MAT>.

In the integral (<NUM>), DE(x-<NUM>) is the download end time <NUM>(x-<NUM>) associated with the source chunk <NUM>(x-<NUM>). Note that the greedy engine <NUM> sets the download end time <NUM>(P-<NUM>) equal to the playback start time associated with the media title <NUM>.

After computing the maximum download size associated with the source chunk <NUM>(x), the greedy engine <NUM> selects the largest encoded chunk <NUM>(x) that is not larger than the maximum download size. The greedy engine <NUM> appends the version index <NUM> associated with the selected encoded chunk <NUM>(x) to the version selection sequence <NUM>. Subsequently, the greedy engine <NUM> sets the download size <NUM>(x) equal to the total number of bits included in the selected encoded chunk <NUM>(x) and computes the download end time <NUM>(x). The greedy engine <NUM> may compute the download end time <NUM>(x) in any technically feasible fashion.

For instance, in some embodiments, the greedy engine <NUM> computes a time interval required to download the selected encoded chunk <NUM>(x), where the time interval spans from the download end time <NUM>(x-<NUM>) to the download end time <NUM>(x). To determine the time interval, the greedy engine <NUM> identifies an area under the network throughput trace <NUM> that is equal to the download size <NUM>(x) and starts at the download end time <NUM>(x-<NUM>).

In other embodiments, the greedy engine <NUM> solves the following equation (<NUM>) for e to compute the download end time <NUM>(x): <MAT>.

In the equation (<NUM>), DS(x) is the download size <NUM>(x).

After processing the chunk <NUM>(N), the greedy engine <NUM> sums the download sizes <NUM>(P)-<NUM>(N) to compute the total download size <NUM>. As persons skilled in the art will recognize, visual quality typically increases as the number of encoded video bits increases. Accordingly, as the greedy engine <NUM> processes the source chunks <NUM>, the greedy engine <NUM> optimizes the version selection sequence <NUM> for total download size and thus indirectly optimizes visual quality. Notably, as part of selecting a given encoded chunk <NUM>, the greedy engine <NUM> attempts to consume any available bandwidth that is not consumed by the preceding encoded chunks <NUM>. In this fashion, the greedy engine <NUM> greedily optimizes the overall visual quality and quality of experience (QoE) associated with the playback of the media title <NUM>.

Subsequently, the greedy engine <NUM> transmits the total download size <NUM> and/or the version selection sequence <NUM> to an application or a device (e.g., a display device) for use in evaluating the performance of an aspect of a video streaming service. For instance, in some embodiments, a video streaming service provider could use the total download size <NUM> as an upper bound for visual quality to retroactively evaluate the performance of a rate selection algorithm. The video streaming service provider could also use the version selection sequence to fine-tune the rate selection algorithm. Because the hindsight engine <NUM> executes in linear time, the time and computational resources required to comprehensively evaluate the visual quality provided via a video rate selection algorithm over a wide variety of network environments, device capabilities, and video content complexities are significantly reduced compared to prior art techniques.

In some embodiments, the video streaming service provider evaluates the performance of one or more networks based on the total download size <NUM>. For instance, the video streaming service provider could perform A/B testing using an "A" network and a "B" network. The hindsight engine <NUM> could compute the total download size <NUM> for a variety of "A" network throughput traces to determine "A" network utilizations. Similarly, the hindsight engine <NUM> could compute the total download sizes <NUM> for a variety of "B" network throughput traces <NUM> to determine "B" network utilizations. The hindsight engine <NUM> could then compare the "A" network utilizations to the "B" network utilizations.

Note that the techniques described herein are illustrative rather than restrictive. As a general matter, the techniques outlined herein are applicable to retrospectively and greedily optimizing a total number of downloaded bits to estimate an upper bound on an overall visual quality over a completed streaming session.

<FIG> illustrates an example of the chunk map <NUM> of <FIG>, according to various embodiments of the present invention. As shown, the media title <NUM> is partitioned into three source chunks <NUM>(<NUM>)-<NUM>(<NUM>). For explanatory purposes, the playback duration of each of the three source chunks <NUM> is visually depicted along a time axis <NUM>. The chunk map <NUM> includes, without limitation, the three encodes <NUM>(<NUM>)-<NUM>(<NUM>). The encode <NUM>(<NUM>) is associated with the version index <NUM> of <NUM>, the encode <NUM>(<NUM>) is associated with the version index <NUM> of <NUM>, and the encode <NUM>(<NUM>) is associated with the version index <NUM> of <NUM>.

Each of the encodes <NUM> includes, without limitation, three different encoded chunks <NUM>(<NUM>)-<NUM>(<NUM>). As described in conjunction with <FIG>, the three encoded chunks <NUM>(x) are all derived from the source chunk <NUM>(x). Consequently, the playback duration associated with each of the encoded chunks <NUM>(x) is equal to the playback duration of the source chunk <NUM>(x) irrespective of the encode <NUM> that includes the encoded chunk <NUM>(x). For example, the three encoded chunks <NUM>(<NUM>) are derived from the source chunk <NUM>(<NUM>). Consequently, the playback duration associated with each of the encoded chunks <NUM>(<NUM>) is equal to the playback duration of the source chunk <NUM>(<NUM>).

Each of the encodes <NUM> is associated with a different bitrate. For explanatory purposes only, the encode <NUM>(<NUM>) is associated with a higher bitrate than the encode <NUM>(<NUM>), and the encode <NUM>(<NUM>) is associated with a higher bitrate than the encode <NUM>(<NUM>). Consequently, the total number of encoded bits included in a given encode <NUM> is different from the total number of encoded bits included in either of the other encodes <NUM>. For each of the encodes <NUM>, the vertical extent of the boxes in the corresponding row depicted in <FIG> reflects the total number of encoded bits associated with the encode <NUM>. In some embodiments, each of the encoded chunks <NUM> included in a given encode <NUM> may be associated with a different bitrate.

Although not shown, as persons skilled in the art will recognize, the visual quality of each of the encoded chunks <NUM> typically varies from the visual quality of the other encoded chunks <NUM>. For instance, the visual quality of a particular encoded chunk <NUM>(x) typically increases as the bitrate increases and typically decreases as the complexity of the associated source chunk <NUM>(x) increases.

<FIG> illustrates an example of the network throughput trace <NUM> of <FIG>, according to various embodiments of the present invention. The value of the network throughput trace <NUM> at any given time along the time axis <NUM> is depicted along a throughput axis <NUM>. As described in conjunction with <FIG>, after selecting the playback-buffered encoded chunk <NUM>(x), the greedy engine <NUM> determines the download end time <NUM>(x) based on the network throughput trace <NUM>, the download end time <NUM>(x-<NUM>) and the download size <NUM>(x). More specifically, the greedy engine <NUM> selects the download end time <NUM>(x) such that the area (depicted with diagonal lines) under the the network throughput trace <NUM> that resides between the download end time <NUM>(x-<NUM>) and the download end time <NUM>(x) is equal to the download size <NUM>(x). As the network throughput trace <NUM> illustrates, the total amount of time required to download the encoded chunk <NUM>(x) varies based on the download end time <NUM>(x-<NUM>) and the download size <NUM>(x).

<FIG> illustrates how the feasibility engine <NUM> of <FIG> computes a set of the feasible download end times <NUM>(<NUM>)-<NUM>(<NUM>), according to various embodiments of the present invention. As shown, the media title <NUM> includes, without limitation, the pre-buffered source chunk <NUM>(<NUM>) and the playback-buffered source chunks <NUM>(<NUM>)-<NUM>(<NUM>). As marked on the time axis <NUM>, a playback start time <NUM> indicates the time at which the pre-buffered source chunk <NUM>(<NUM>) begins playing back. The playback of the media title <NUM> continues uninterrupted until the source chunk <NUM>(<NUM>) finishing playing back, depicted as a playback end time <NUM>.

For explanatory purposes only, <FIG> depicts a series of operations that the feasibility engine <NUM> performs to compute the feasible download end times <NUM>(<NUM>)-<NUM>(<NUM>) as a series of numbered bubbles along a curve representing a cumulative bandwidth <NUM>. At each time along the time axis <NUM>, the associated point on the curve specifies the cumulative bandwidth along a cumulative bits axis <NUM>. The cumulative bandwidth <NUM> is derived from the network throughput trace <NUM>.

Initially, as depicted with the bubble numbered <NUM>, because the source chunk <NUM>(<NUM>) is the final source chunk <NUM> included in the media title <NUM>, the feasibility engine <NUM> sets the feasible download end time <NUM>(<NUM>) equal to a download deadline <NUM>(<NUM>). In general, the download deadline <NUM>(x) specifies the time at which the source chunk <NUM>(x) begins to playback. As depicted with a dashed arrow and the bubble numbered <NUM>, the feasibility engine <NUM> then computes a feasible download start time <NUM>(<NUM>) based on the minimum download size <NUM>(<NUM>) and the feasible download end time <NUM>(<NUM>). As shown, the feasible download start time <NUM>(<NUM>) is later than the download deadline <NUM>(<NUM>). Consequently, as depicted with the bubble numbered <NUM>, the feasibility engine <NUM> sets the feasible download end time <NUM>(<NUM>) equal to the download deadline <NUM>(<NUM>).

As depicted with a dashed arrow and the bubble numbered <NUM>, the feasibility engine <NUM> then computes the feasible download start time <NUM>(<NUM>) based on the minimum download size <NUM>(<NUM>) and the feasible download end time <NUM>(<NUM>). As shown, the feasible download start time <NUM>(<NUM>) is earlier than the download deadline <NUM>(<NUM>). Consequently, as depicted with the bubble numbered <NUM>, the feasibility engine <NUM> sets the feasible download end time <NUM>(<NUM>) equal to the feasible download start time <NUM>(<NUM>).

Subsequently and as depicted with a dashed arrow and the bubble numbered <NUM>, the feasibility engine <NUM> computes the feasible download start time <NUM>(<NUM>) based on the minimum download size <NUM>(<NUM>) and the feasible download end time <NUM>(<NUM>). As shown, the feasible download start time <NUM>(<NUM>) is later than the download deadline <NUM>(<NUM>). Consequently, as depicted with the bubble numbered <NUM>, the feasibility engine <NUM> sets the feasible download end time <NUM>(<NUM>) equal to the download deadline <NUM>(<NUM>). As depicted with a dashed arrow and the bubble numbered <NUM>, the feasibility engine <NUM> then computes the feasible download start time <NUM>(<NUM>) based on the minimum download size <NUM>(<NUM>) and the feasible download end time <NUM>(<NUM>).

Because the playback start time <NUM> is earlier than the feasible download start time <NUM>(<NUM>), the feasibility engine <NUM> determines that an uninterrupted playback of the media title <NUM> is possible. Finally, to determine the version selection sequence <NUM> that greedily maximizes the total download size <NUM> while ensuring an uninterrupted playback, the feasibility engine <NUM> transmits the feasible download end times <NUM>(<NUM>)-<NUM>(<NUM>) to the greedy engine <NUM>.

<FIG> illustrates how the greedy engine <NUM> of <FIG> generates the version selection sequence <NUM>, according to various embodiments of the present invention. Although not shown in <FIG>, the media title <NUM> includes, without limitation, the pre-buffered source chunk <NUM>(<NUM>) and the playback-buffered source chunks <NUM>(<NUM>)-<NUM>(<NUM>). Further, the chunk map <NUM> includes, without limitation, the three encodes <NUM>(<NUM>)-<NUM>(<NUM>) corresponding version indexes <NUM> of, respectively, <NUM>, <NUM>, and <NUM>. Each of the encodes <NUM> includes, without limitation, a different pre-buffered encoded chunk <NUM>(<NUM>) and different playback-buffered encoded chunks <NUM>(<NUM>)-<NUM>(<NUM>).

For explanatory purposes only, <FIG> depicts a series of operations that the greedy engine <NUM> performs to generate the version selection sequence <NUM> as a series of numbered bubbles along a curve representing the cumulative bandwidth <NUM>. At each time along the time axis <NUM>, the associated point on the curve specifies the cumulative bandwidth along the cumulative bits axis <NUM>. The cumulative bandwidth <NUM> is derived from the network throughput trace <NUM>.

Initially, as depicted with the bubble numbered <NUM>, the greedy engine <NUM> generates an availability window <NUM>(<NUM>) for the download of the encoded chunk <NUM>(<NUM>). As shown, the availability window <NUM>(<NUM>) spans from the playback start time <NUM> to the feasible download end time <NUM>(<NUM>). The greedy engine <NUM> then selects the largest encoded chunk <NUM>(<NUM>) that can download within the availability window <NUM>(<NUM>), thereby allowing an uninterrupted playback of the media title <NUM>.

Although not shown, the selected encoded chunk <NUM>(<NUM>) is included in the encode <NUM>(<NUM>) associated with the version index <NUM> of <NUM>. Consequently, the greedy engine <NUM> sets the version index <NUM>(<NUM>) included in the version selection sequence <NUM> equal to <NUM>. The greedy engine <NUM> also sets the download size <NUM>(<NUM>) equal to the number of bits included in the selected encoded chunk <NUM>(<NUM>). As depicted with the bubble numbered <NUM>, the greedy engine <NUM> then computes the download end time <NUM>(<NUM>) based on the network throughput trace <NUM>, the playback start time <NUM>, and the download size <NUM>(<NUM>).

Subsequently, as depicted with the bubble numbered <NUM>, the greedy engine <NUM> generates the availability window <NUM>(<NUM>) for the download of the encoded chunk <NUM>(<NUM>). As shown, the availability window <NUM>(<NUM>) spans from the download end time <NUM>(<NUM>) to the feasible download end time <NUM>(<NUM>). The greedy engine <NUM> then selects the largest encoded chunk <NUM>(<NUM>) that can download within the availability window <NUM>(<NUM>), thereby allowing an uninterrupted playback of the media title <NUM>.

Although not shown, the selected encoded chunk <NUM>(<NUM>) is included in the encode <NUM>(<NUM>) associated with the version index <NUM> of <NUM>. Consequently, the greedy engine <NUM> sets the version index <NUM>(<NUM>) included in the version selection sequence <NUM> equal to <NUM>. The greedy engine <NUM> also sets the download size <NUM>(<NUM>) equal to the number of bits included in the selected encoded chunk <NUM>(<NUM>). As depicted with the bubble numbered <NUM>, the greedy engine <NUM> then computes the download end time <NUM>(<NUM>) based on the network throughput trace <NUM>, the download end time <NUM>(<NUM>), and the download size <NUM>(<NUM>).

As depicted with the bubble numbered <NUM>, the greedy engine <NUM> then generates the availability window <NUM>(<NUM>) for the download of the encoded chunk <NUM>(<NUM>). The availability window <NUM>(<NUM>) spans from the download end time <NUM>(<NUM>) to the feasible download end time <NUM>(<NUM>). The greedy engine <NUM> selects the largest encoded chunk <NUM>(<NUM>) that can download within the availability window <NUM>(<NUM>), thereby allowing an uninterrupted playback of the media title <NUM>.

Although not shown, the selected encoded chunk <NUM>(<NUM>) is included in the encode <NUM>(<NUM>) associated with the version index <NUM> of <NUM>. Consequently, the greedy engine <NUM> sets the version index <NUM>(<NUM>) included in the version selection sequence <NUM> equal to <NUM>. The greedy engine <NUM> also sets the download size <NUM>(<NUM>) equal to the number of bits included in the selected encoded chunk <NUM>(<NUM>). As depicted with the bubble numbered <NUM>, the greedy engine <NUM> computes the download end time <NUM>(<NUM>) based on the network throughput trace <NUM>, the download end time <NUM>(<NUM>) and the download size <NUM>(<NUM>).

Subsequently and as depicted with the bubble numbered <NUM>, the greedy engine <NUM> generates the availability window <NUM>(<NUM>) for the download of the encoded chunk <NUM>(<NUM>). As shown, the availability window <NUM>(<NUM>) spans from the download end time <NUM>(<NUM>) to the feasible download end time <NUM>(<NUM>). The greedy engine <NUM> then selects the largest encoded chunk <NUM>(<NUM>) that can download within the availability window <NUM>(<NUM>), thereby allowing an uninterrupted playback of the media title <NUM>.

Finally, as depicted with the bubble numbered <NUM>, the greedy engine <NUM> sums the download sizes <NUM>(<NUM>)-<NUM>(<NUM>) to compute the total download size <NUM>. Advantageously, by greedily maximizing the total download size <NUM>, the greedy engine <NUM> indirectly optimizes the overall visual quality associated with the version selection sequence <NUM>. Further, the encoded chunks <NUM>(<NUM>)-<NUM>(<NUM>) specified via the version selection sequence <NUM> allow an uninterrupted playback of the media title <NUM>. Notably, there is a gap of unused time <NUM> between the time at which the download of the encoded chunk <NUM>(<NUM>) completes and the time at which the playback of the encoded chunk <NUM>(<NUM>) begins. The time following the time at which the playback of the encoded chunk <NUM>(<NUM>) begins is depicted as unavailable time <NUM>.

<FIG> set forth a flow diagram of method steps for evaluating one or more aspects of a video streaming service, according to various embodiments of the present invention. Although the method steps are described with reference to the systems of <FIG>, persons skilled in the art will understand that any system configured to implement the method steps, in any order, falls within the scope of the present invention.

As shown, a method <NUM> begins at step <NUM>, where the feasibility engine <NUM> selects the last source chunk <NUM> included in a media title <NUM> and sets a subsequent feasible download start time equal to the playback end time <NUM>, where the "subsequent feasible download start time" is a variable. At step <NUM>, the feasibility engine <NUM> sets the download deadline <NUM> associated with the selected source chunk <NUM> equal to a playback start time associated with the selected source chunk <NUM> that ensures an uninterrupted playback of the media title <NUM>. As persons skilled in the art will recognize, the playback start time associated with the selected source chunk <NUM> is independent of the version of the encoded chunk <NUM> that is downloaded.

At step <NUM>, the feasibility engine <NUM> sets the feasible download end time <NUM> associated with the selected source chunk <NUM> equal to the minimum of the download deadline <NUM> and the subsequent feasible download start time. At step <NUM>, the feasibility engine <NUM> computes the feasible download start time based on the feasible download end time <NUM> associated with the selected source chunk <NUM> and the network throughput trace <NUM>. More precisely, the feasibility engine <NUM> selects the smallest encoded chunk <NUM> derived from the selected source chunk <NUM>. The feasibility engine <NUM> then computes the feasible download start time for which a download of the selected encoded chunk <NUM> completes at the feasible download end time <NUM> associated with the selected source chunk <NUM>.

At step <NUM>, the feasibility engine <NUM> sets the subsequent feasible download start time equal to the feasible download start time and selects the source chunk <NUM> that precedes the selected source chunk <NUM> with respect to a playback of the media title <NUM>. At step <NUM>, the feasibility engine <NUM> determines whether the selected source chunk <NUM> is pre-buffered <NUM>. If, at step <NUM>, the feasibility engine <NUM> determines that the selected source chunk <NUM> is not pre-buffered, then the method <NUM> returns to step <NUM>, where the feasibility engine <NUM> continues to process the source chunks <NUM> in the reverse playback order.

If, however, at step <NUM>, the feasibility engine <NUM> determines that the selected source chunk <NUM> is pre-buffered, then the method <NUM> continues to step <NUM>. At step <NUM>. the feasibility engine <NUM> determines whether the feasible download start time is less than the playback start time <NUM>. If, at step <NUM>, the feasibility engine <NUM> determines that the feasible download start time is earlier than the playback start time <NUM>, then the method <NUM> proceeds to step <NUM>. At step <NUM>, the feasibility engine <NUM> displays an error message, and the method <NUM> terminates.

If, however, at step <NUM>, the feasibility engine <NUM> determines that the feasible download start time is not earlier than the playback start time <NUM>, then the method <NUM> proceeds directly to step <NUM>. At step <NUM>, the greedy engine <NUM> selects the source chunk <NUM> that follows the selected source chunk <NUM> and sets a download start time equal to the playback start time <NUM>. At step <NUM>, the greedy engine <NUM> selects the largest encoded chunk <NUM> derived from the selected source chunk <NUM> for which a download of the encoded chunk <NUM> that starts at the download start time completes no later than the feasible download end time <NUM> associated with the selected source chunk <NUM>. At step <NUM>, the greedy engine <NUM> sets the version index <NUM> to specify the selected encoded chunk <NUM> and then appends the version index <NUM> to the version selection sequence <NUM>.

At step <NUM>, the greedy engine <NUM> computes the download end time <NUM> associated with the selected source chunk <NUM> based on the number of encoded bits included in the selected encoded chunk <NUM>, the download start time, and the network throughput trace <NUM>. At step <NUM>, the greedy engine <NUM> determines whether the selected source chunk <NUM> is the last source chunk <NUM> included in the media title <NUM>. If, at step <NUM>, the greedy engine <NUM> determines that the selected source chunk <NUM> is not the last source chunk <NUM> included in the media title, then the method <NUM> proceeds to step <NUM>. At step <NUM>, the greedy engine <NUM> sets the download start time equal to the download end time <NUM> associated with the selected source chunk <NUM> and selects the source chunk <NUM> that follows the selected source chunk <NUM> with respect to the playback order. The method <NUM> then returns to step <NUM>, where the greedy engine <NUM> continues to process the source chunks <NUM> in the playback order.

If, however, at step <NUM>, the greedy engine <NUM> determines that the selected source chunk <NUM> is the last source chunk <NUM> included in the media title <NUM>, then the method <NUM> proceeds directly to step <NUM>. At step <NUM>, the greedy engine <NUM> computes the total download size <NUM> that corresponds to the version selection sequence <NUM>. At step <NUM>, the greedy engine <NUM> transmits the total download size <NUM> and/or the version selection sequence <NUM> for retrospective evaluation of a video streaming service. In some embodiments, the total download size <NUM> and the version selection sequence <NUM> may be used to evaluate and fine-tune a rate selection algorithm. In the same or other embodiments, the total download size <NUM> may be used to evaluate the efficacy associated with the completed streaming session. Advantageously, the hindsight application <NUM> executes in linear time.

In sum, the disclosed techniques may be used to efficiently and reliably evaluate one or more aspects of a video streaming service based on a network throughput trace that characterizes a completed streaming session. A hindsight application includes, without limitation, a feasibility engine and a greedy engine. First, in reverse playback order for each playback-buffered source chunk included in a media title, the feasibility engine computes a feasible download end time based on a feasible download end time associated with the subsequent source chunk and the network throughput trace. More specifically, for a given source chunk, the feasibility engine selects the smallest encoded chunk derived from the subsequent source chunk. The feasibility engine then computes a "subsequent" feasible download start time based on the throughout trace, the feasible download end time associated with the subsequent source chunk, and the size of the selected encoded chunk. The feasibility engine then sets the feasible download end time associated with the source chunk equal to the earlier of the subsequent feasible download start time and the playback start time associated with the source chunk.

Second, in playback order for each playback-buffered source chunk included in the media title, the greedy engine selects an associated encoded chunk and computes an associated download end time. For a given source chunk, the greedy engine computes a maximum download size based on the network throughput trace, the associated feasible download end time, and a download end time associated with the preceding source chunk. The greedy engine then selects the largest encoded chunk derived from the source chunk that is not larger than the maximum download size. The greedy engine then appends the version index associated with the selected encoded chunk to a version selection sequence. Subsequently, the greedy engine computes the download end time associated with the source chunk based on the network throughput trace and, the size of the selected encoded chunk, and the "preceding" download end time. After processing all of the playback-buffered source chunks, the greedy engine sums the sizes of the encoded chunks specified via the version selection sequence to compute the total download size. The greedy engine then transmits the total download size and/or the version selection sequence to an application or a device (e.g., a display device) for use in evaluating the performance of an aspect of a video streaming service, such as a rate selection algorithm or a network.

At least one technical advantage of the disclosed techniques relative to prior art solutions is that the hindsight application more efficiently determines an upper bound for the visual quality associated with a media title over a completed streaming session. In that regard, the hindsight application correlates the upper bound of visual quality to the total download size. Notably, determining the total download size is computationally more efficient than prior art approaches that experience NP-hard problems. More specifically, unlike prior art approaches to computing an upper bound for visual quality that are NP-hard, the time required for the hindsight application to compute the total download size is on the order of the total number of source chunks making up the media title. Consequently, the time and computational resources required to evaluate the visual quality associated with a given video rate selection algorithm across a wide variety of network environments, device capabilities, and video content complexities using the hindsight application can be substantially reduced relative to prior art approaches. Further, the version selection sequence enables efficient fine-tuning of the video selection algorithm. Yet another advantage is that the disclosed techniques may be used to compare additional aspects of the video streaming service, such as the efficacy of a network. These technical advantages provide one or more technological advancements over the prior art.

Aspects of the present embodiments may be embodied as a system, method or computer program product. Accordingly, aspects of the present disclosure may take the form of an entirely hardware embodiment, an entirely software embodiment (including firmware, resident software, micro-code, etc.) or an embodiment combining software and hardware aspects that may all generally be referred to herein as a ""module" or "system. " Furthermore, aspects of the present disclosure may take the form of a computer program product embodied in one or more computer readable medium(s) having computer readable program code embodied thereon.

Claim 1:
A computer-implemented method (<NUM>), comprising:
computing (<NUM>) a first feasible download end time (<NUM>) associated with a source chunk (<NUM>) of a media title based on a network throughput trace (<NUM>) and a subsequent feasible download end time (<NUM>) associated with a subsequent source chunk (<NUM>) of the media title;
selecting (<NUM>) a largest encoded chunk (<NUM>) from a plurality of encoded chunks (<NUM>) associated with the source chunk (<NUM>) based on the network throughput trace (<NUM>), the first feasible download end time (<NUM>), and a preceding download end time (<NUM>) associated with a preceding source chunk (<NUM>) of the media title; and
computing (<NUM>) a total download size (<NUM>) associated with a sequence of encoded chunks (<NUM>) associated with the media title based on the number of encoded bits included in the sequence of encoded chunks (<NUM>), wherein the performance of at least one aspect of a streaming video infrastructure is evaluated based on the total download size;
wherein the at least one aspect of the streaming video infrastructure comprises at least one of an efficacy of a video rate selection algorithm and an efficacy of a network; and wherein the network throughput trace indicates available network bandwidth as a function of time over a completed streaming session.