Network optimization

• US 8,832,709 B2
• Filed: 07/18/2011
• Issued: 09/09/2014
• Est. Priority Date: 07/19/2010
• Status: Active Grant

• Current Assignee: Flash Networks, Ltd. (Constellation Software Incorporated)
• Original Assignee: Flash Networks, Ltd. (Constellation Software Incorporated)
• Inventors: Noam, Oded, Daniel, Ilan, Grefen, Stefan, Pattison, Ian
• Primary Examiner(s): Tang, Kenneth
• Application Number:
  US13/184,739
• Publication Number:
  US 20120023504A1
• Time in Patent Office: 1,149 Days
• Field of Search: None
• US Class Current: 718/104
• CPC Class Codes: H04L 65/00 Network arrangements, protocols or services for supporting real-time applications in data packet communication real-time or near real-time messaging, e.g. instant messaging [IM] H04L51/04; selective video distribution H04N21/00
• CPC Class Codes: H04L 65/765 intermediate
• CPC Class Codes: H04L 65/80 Responding to QoS
• CPC Class Codes: H04L 67/5651 Reducing the amount or size of exchanged application data
• CPC Class Codes: H04L 69/04 Protocols for data compression, e.g. ROHC
• CPC Class Codes: H04N 19/12 Selection from among a plurality of transforms or standards, e.g. selection between discrete cosine transform [DCT] and sub-band transform or selection between H.263 and H.264
• CPC Class Codes: H04N 19/149 by estimating the code amount by means of a model, e.g. mathematical model or statistical model
• CPC Class Codes: H04N 19/156 Availability of hardware or computational resources, e.g. encoding based on power-saving criteria
• CPC Class Codes: H04N 19/40 using video transcoding, i.e. partial or full decoding of a coded input stream followed by re-encoding of the decoded output stream

Abstract

A method for handling communication data involving identifying available resources for applying compression tasks and estimating a throughput reduction value to be achieved by applying each of a plurality of different compression tasks to a plurality of media items. A cost of applying the plurality of different compression tasks to the plurality of media items is estimated. The method further includes finding an optimization solution that maximizes the throughput reduction value over possible pairs of the compression tasks and the media items, while keeping the cost of the tasks of the solution within the identified available resources and providing instructions to apply compression tasks according to the optimization solution.

Claims

1. A method for handling communication data, comprising:

identifying, by a processor, available resources for applying compression tasks;

estimating, by the processor, a throughput reduction value to be achieved by applying each of a plurality of different compression tasks to a plurality of media items;

estimating, by the processor, a cost of applying the plurality of different compression tasks to the plurality of media items;

finding an optimization solution that maximizes the throughput reduction value over possible pairs of the compression tasks and the media items, while keeping the cost of the tasks of the solution within the identified available resources;

providing instructions to apply compression tasks according to the optimization solution;

managing, by the processor, look up tables which associate gain values of tasks with media classes; and

updating the look up tables based on actual compression results of media tasks,

wherein estimating the gain comprises estimating the gain using the look up tables,

wherein providing the instructions comprises instructing for at least one media item not to perform at least one compression task, and

wherein updating the look up tables comprises updating by comparing the results of media tasks to which a compression task was applied with results of media tasks to which the compression task was not applied.

2. The method of claim 1, wherein finding the optimization solution comprises selecting media items to be compressed and respective compression tasks to be used in compression of the selected media items and comprising compressing the selected media items by the respective selected tasks, responsive to the instructions.

3. The method of claim 1, wherein finding the optimization solution comprises finding, for each of a plurality of classes of media items, a corresponding task blend to be applied to tasks of the class.

4. The method of claim 1, comprising estimating a blend of media items to be handled in a next time window and wherein finding the optimization solution is performed on the estimated blend of media items.

5. The method of claim 1, wherein finding the optimization solution is performed on a set of media items including at least one media item for which a compression task was previously selected and will not be changed.

6. The method of claim 1, wherein the optimization solution prescribes applying compression tasks to a number of media items, and wherein providing the instructions comprises providing instructions to perform compression tasks in accordance with the optimization solution, for fewer media items than prescribed by the optimization solution.

7. The method of claim 1, wherein estimating the gain comprises estimating a current gain from applying the compression task and estimating a future gain based on an estimation of a number of times a cached version of the compressed media item may be reused in the future.

8. The method of claim 7, wherein estimating the gain comprises estimating based on the current gain and the future gain, while providing a higher weight per byte to the current gain relative to the future gain.

9. The method of claim 1, wherein estimating the gain comprises associating different weights to a nominal throughput reduction according to the congestion state of a transmission path of the media item for which the gain is estimated.

10. The method of claim 9, wherein estimating the gain comprises assigning at least three different weights to different congestion states.

11. The method of claim 1, wherein estimating the gain comprises estimating the gain in monetary units.

12. The method of claim 1, wherein estimating the cost comprises estimating the cost in units comparable to the units of the estimated gain.

13. The method of claim 12, wherein finding an optimization solution comprises excluding from consideration pairs of tasks and media items for which the cost is larger than the gain.

14. The method of claim 1, comprising repeating the estimating of gain and cost and the finding of an optimization solution, a plurality of times during the transmission of a single media item.

15. A method for handling communication data, comprising:

determining, by a processor, available resources for applying compression tasks;

estimating, by the processor, for a plurality of pairs of compression task and media item, a gain from applying the compression task to the media item for a current transmission of the media item and for expected future transmissions of the media item;

estimating, by the processor, for the pairs of compression task and media item, a cost of applying the compression task;

determining an optimization solution that maximizes the gain over the possible pairs of compression tasks and media items, while keeping a cost of the tasks of the solution within the determined available resources;

providing instructions to apply at least one compression task to at least one media item responsive to the determined optimization solution;

managing, by the processor, look up tables which associate gain values of tasks with media classes; and

updating the look up tables based on actual compression results of media tasks,

wherein estimating the gain comprises estimating the gain using the look up tables,

wherein providing the instructions comprises instructing for at least one media item not to perform at least one compression task, and

wherein updating the look up tables comprises updating by comparing the results of media tasks to which a compression task was applied with results of media tasks to which the compression task was not applied.

16. The method of claim 15, wherein estimating the gain comprises estimating a duration for which the results of applying the compression task to the media item will be held in a cache memory.

17. The method of claim 16, wherein estimating the gain comprises estimating an average number of times the media item will be requested while the results of applying the compression task to the media item are stored in the cache.

18. The method of claim 15, wherein estimating the gain comprises associating a greater value to current gains than to future gains.

19. The method of claim 15, wherein providing instructions to apply at least one compression task to at least one media item comprises providing instructions to apply a first compression task to a specific media item, although a result of applying a second compression task to the specific media item is available in a cache for use by the processor.

20. A communication apparatus, comprising:

an input interface configured to receive media items;

a processor configured to determine available resources for applying compression tasks, to estimate a gain in reduced transmissions from applying each of a plurality of different compression tasks on a plurality of media items, to estimate a cost of applying the plurality of different compression tasks on the plurality of media items, to determine an optimization solution which maximizes a gain over the possible pairs of compression tasks and media items, while keeping a cost of the tasks of the solution within available resources, to manage look up tables which associate gain values of tasks with media classes and to update the look up tables based on actual compression results of media tasks; and

a compression unit configured to apply compression tasks to media items responsive to determined optimization solutions of the processor,

wherein the processor is configured to estimate the gain using the look up tables,

wherein the processor is configured to instruct for at least one media item not to perform at least one compression task, and

wherein the processor is configured to update the look up tables by comparing the results of media tasks to which a compression task was applied with results of media tasks to which the compression task was not applied.

21. The apparatus of claim 20, wherein the compression unit is configured to operate in a plurality of modes which utilize different numbers of processor units according to a load on the compression unit, and wherein the processor is configured to determine an amount of resources to be used in order to match one of the modes of the compression unit.

22. The apparatus of claim 21, wherein the processor is configured to determine an amount of resources to be used responsive to a value of throughput gain that can be achieved by using a higher level of resources.

23. A computer software product, comprising a tangible computer-readable medium in which program instructions are stored, which instructions, when read by a computer, cause the computer to:

determine available resources for applying compression tasks;

estimate a gain in reduced transmissions from applying each of a plurality of different compression tasks on a plurality of media items;

estimate a cost of applying the plurality of different compression tasks on the plurality of media items;

determine an optimization solution which maximizes the gain over the possible pairs of compression tasks and media items, while keeping a cost of the tasks of the solution within the determined available resources;

provide instructions to apply at least one compression task to at least one media item responsive to the determined optimization solution;

manage look up tables which associate gain values of tasks with media classes; and

update the look up tables based on actual compression results of media tasks,

wherein the program instructions estimate the gain using the look up tables,

wherein the program instructions instruct for at least one media item not to perform at least one compression task, and

wherein the program instructions update the look up tables by comparing the results of media tasks to which a compression task was applied with results of media tasks to which the compression task was not applied.