Automatic data quality adjustment to reduce response time in browsing

• US 6,563,517 B1
• Filed: 01/29/1999
• Issued: 05/13/2003
• Est. Priority Date: 10/02/1998
• Status: Expired due to Term

• Current Assignee: GlobalFoundries, Inc.
• Original Assignee: International Business Machines Corporation
• Inventors: Rubas, James, Bhagwat, Pravin, Han, Richard Yeh-whein, LaMaire, Richard Orville, Mummert, Todd William
• Primary Examiner(s): SAX, STEVEN PAUL
• Application Number:
  US09/236,622
• Time in Patent Office: 1,565 Days
• Field of Search: 345/734-739, 345/745, 345/762, 345/743, 345/742, 709/230, 709/221, 709/236, 709/203, 709/238, 707/10, 707/513
• US Class Current: 715/735
• CPC Class Codes: G06F 16/9577 Optimising the visualization of content, e.g. distillation of HTML documents
• CPC Class Codes: H04L 67/306 User profiles
• CPC Class Codes: H04L 67/56 Provisioning of proxy services store-and-forward switching systems in data switching networks H04L12/54
• CPC Class Codes: H04L 67/565 Conversion or adaptation of application format or content adding application control or application functional data H04L67/561
• CPC Class Codes: H04L 67/60 Scheduling or organising the servicing of application requests, e.g. requests for application data transmissions using the analysis and optimisation of the required network resources admission control or resource allocation H04L47/70
• CPC Class Codes: H04L 69/24 Negotiation of communication capabilities
• 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
• CPC Class Codes: H04N 21/6377 directed to server one-way streaming services wherein the source is controlled by the destination H04L65/613
• CPC Class Codes: H04N 21/658 Transmission by the client directed to the server

Abstract

The present invention provides methods, devices and systems for dynamically adjusting transcoding parameters so as to increase the benefits of transcoding. Methods of adaptation are designed to cope with the variability of network characteristics and of the size of transcoded images. The invention also provides a method and apparatus to enable the transcoding proxy to adjust a quality-size tradeoff on a per-image and/or a per-client basis. The adaptive transcoder chooses different parameters for each object, and provides performance improvements. The invention further provides a general framework for making policy decisions taking into account available bandwidth, content and type of image, and user preferences. The invention also includes methods for generating feedback about the choice of optimal transcoding parameters to the user.

Claims

1. A method for a transcoding proxy to facilitate browsing between a plurality of client devices and a plurality of servers connected via a communication network, the method comprising:

receiving a request from one of the client devices for an object stored at one of the servers,

forwarding the request for the object to said one of the servers,

receiving the object from said one of the servers,

examining preferences specified by a user of said one of the client devices,

examining contents of the object,

examining communication network characteristics, wherein the network characteristics includes bandwidth, and examining network characteristics includes estimating network bandwidth between said one of the servers and the proxy as well as between the proxy and said one of the clients,

choosing a set of transcoding parameters,

forming a transcoded form of the object, and

sending the transcoded form to said one of the clients.

3. A method as recited in claim 1, further comprising providing feedback to the user about a level of transcoding performed on the object to form the transcoded form.

4. A method as recited in claim 1, wherein the step of examining includes determining the size of the object.

5. A method as recited in claim 1, wherein the object is of type image forming an image object, and the method further comprises:

determining dimensions of the image object, and

calculating the compression ratio of the image object.

6. A method as recited in claim 5, wherein the dimensions of the image object are determined by area of the image in square pixels, and the compression ratio is determined by the bpp ratio of the image object.

7. A method as recited in claim 1, wherein the step of forming a transcoded form employs dynamic adaptation.

8. A method as recited in claim 1, wherein the step of forming a transcoded form is started before the step of receiving the object from said one of the servers is complete.

9. A method as recited in claim 8, wherein the received object type is of type JPEG forming a JPEG object.

10. A method as recited in claim 9, wherein the step of forming a transcoded form includes performing JPEG-to-JPEG image transcoding and the step of sending the transcoded form starts writing out at least one MCU of JPEG-encoded output image data before the step of receiving the object is complete.

11. A method as recited in claim 1, wherein the step of sending out the transcoded form is started after processing an initial fraction of the received object, and before the step of receiving the image object from said one of the servers is complete.

12. A method as recited in claim 1, wherein the step of sending out the transcoded form is started before the step of forming a transcoded form of the object is complete.

2. A method for a transcoding proxy to facilitate browsing between a plurality of client devices and a plurality of servers connected via a communication network, the method comprising:

receiving a request from one of the client devices for an object stored at one of the servers,

forwarding the request for the object to said one of the servers,

receiving the object from said one of the servers,

examining preferences specified by a user of said one of the client devices,

examining contents of the object,

examining communication network characteristics, wherein the network characteristics includes delay, and examining network characteristics includes estimating delay between said one of the servers and the proxy as well as delay between the proxy and said one of the clients,

choosing a set of transcoding parameters,

forming a transcoded form of the object, and

sending the transcoded form to said one of the clients.

13. A method for a proxy to form a transcoded form of an object received from a server in satisfaction of a request from a client for an object available from the server, the method comprising:

dynamically adapting parameters for transcoding the object for the client, wherein adapting includes examining the contents of the object and gathering present network characteristics between the server and the proxy and between the proxy and client,

forming a transcoded form of the object,

predicting at least one parameter of the transcoded form of the object, and

sending the transcoded form to the client.

14. A method as recited in claim 13, wherein the step of adapting parameters includes determining at least one characteristic of the object.

15. A method as recited in claim 14, wherein one characteristic is an object-header, the object-header providing information about the size and the type of the object.

16. A method as recited in claim 15, further comprising comparing the size of the object to a threshold parameter called “

size_threshold”

.

17. A method as recited in claim 13, wherein one of the characteristics is network bandwidth and the step of adapting includes estimating network bandwidth between the server and the proxy as well as between the proxy and the client.

18. A method as recited in claim 17, wherein the transcoded form is dependent upon the estimated bandwidth.

19. A method as recited in claim 13, wherein the step of adapting includes retrieving preferences of the user, and wherein the transcoded form is dependent upon the preferences.

20. A method as recited in claim 13, wherein the object is of type image forming an image object, and examining the content of the image object includes determining dimensions of the image.

21. A method as recited in claim 20, wherein the step of adapting is dependent upon determining the compression ratio of the image object.

22. A method of claim 21, wherein the type of image object is GIF and wherein the step of adapting is dependent upon comparing the compression ratio against a predetermined policy threshold called “

gif_threshold”

.

23. A method as recited in claim 13, wherein the transcoded form is the same as an original form of the object.

24. A method as recited in claim 13, wherein at least one of the parameters includes a size of the transcoded form.

25. A method as recited in claim 13, wherein at least one of the parameters includes the time spent in transcoding the object.

26. A method for predicting parameters of a transcoded form of an object, the object having an initial size and dimension, and the object being received from a server in satisfaction of a request from a client for the object, the method comprising:

computing the bpp ratio of the object,

gathering a set of statistics of a plurality of previously transcoded objects,

employing the set of statistics and the bpp ratio for predicting the parameters, wherein at least one of the parameters is size and the set of statistics includes sizes of a plurality of previously transcoded objects statistics.

29. A method as recited in claim 26, wherein the step of employing uses dynamically updating the set of statistics using the statistics of the currently transcoded object.

30. A method as recited in claim 26, wherein at least one of the parameters is a duration for forming a transcoded form of an object and the set of statistics includes the duration for forming a plurality of previously transcoded objects.

27. A method for predicting parameters of a transcoded form of an object, the object having an initial size and dimension, and the object being received from a server in satisfaction of a request from a client for the object, the method comprising:

computing the bpp ratio of the object,

gathering a set of statistics of a plurality of previously transcoded objects, wherein the object is of type image and wherein the set of statistics includes image quality,

employing the set of statistics and the bpp ratio for predicting the parameters.

28. A method as recited in claim 27, wherein the plurality of previously transcoded objects are chosen from a predetermined benchmark suite of images.

31. A transcoding proxy system for facilitating browsing between a plurality of clients and a plurality of servers connected via a communication network, the proxy comprising

an HTTP proxy engine to receive a request from one of the clients for an object stored at one of the servers, and to fetch the object from said one of the servers,

an object transcoder to form a transcoded form of the object using a set of parameters for transcoding,

a dynamic policy module to determine the set of parameters of transcoding,

an image size and delay predictor module to gather characteristics of the object,

a user preference module to gather quality preferences specified by a user of said one of the clients, and

a bandwidth estimation module to estimate available network bandwidth, wherein dynamic policy module dynamically adjusting the parameters of transcoding using the input received from the image size and delay predictor module, user preferences module, and bandwidth estimation module for the purpose of improving satisfaction for the user, and the transcoding system providing feedback to the user about the level of transcoding performed.

32. A system as recited in claim 31, wherein the user preferences module further

collecting the characteristics such as display size, resolution, &

CPU speed of said one of the devices, and

providing those characteristics to the dynamic policy module.

33. A system as recited in claim 31, wherein the bandwidth estimation module

collecting traces of previously established network connections between said one of the servers &

the proxy,

collecting traces of previously established network connections between the proxy and said one of the clients, and

estimating the object download time by performing statistical analysis on the collected traces.

34. A system as recited in claim 33, wherein the statistical analysis used for estimating bandwidth between said one of the servers and the proxy is based on computing a statistical measure such as median, mean, or mode of download times of previously fetched objects as determined from the collected traces.

35. A system as recited in claim 33, wherein the statistical analysis used for estimating bandwidth between the proxy and said one of the clients is based on computing aggregate bandwidth of all active connections between the proxy and said one of the clients.

36. A system as recited in claim 31, further comprising displaying a slide bar on said one of the client'"'"'s display for collecting the user specified preferences.

37. A system as recited in claim 31, wherein the user of said one of the clients can specify the tradeoff between download time and data quality through the use of a graphical user interface with a slide bar.

38. A system as recited in claim 36, whereby the user of said one of the clients can specify through the use of a graphical user interface with a slide bar the tradeoff between download time and image quality including a specific switch to select color or gray scale as the desired output form.

39. A system as recited in claim 36, whereby the user of said one of the clients can specify through the use of a graphical user interface with a slide bar, the desire to maintain a target response time such that the system automatically reduces data quality (and hence data download size) to compensate for dynamic variations in bandwidth to said one of the clients.

40. A system as recited in claim 36, whereby the graphical user interface slider bar is also used as an output interface for showing the optimal choice of transcoding parameters to the user.

41. An article of manufacture comprising a computer usable medium having computer readable program code means embodied therein for causing dynamic adaptation of transcoded form of an object in a transcoding proxy, the computer readable program code means in said article of manufacture comprising computer readable program code means for causing a computer to effect:

a proxy receiving an object associated with a user from a server,

determining parameters of the object,

retrieving preferences of the user,

gathering present network characteristics,

obtaining transcoding policy thresholds,

performing a policy decision based upon object parameters, user preferences, network characteristics, and policy thresholds,

forming a transcoded object,

providing feedback of a level of transcoding performed on the object to the user,

sending the transcoded object to the user.

42. An article of manufacture comprising a computer usable medium having computer readable program code means embodied therein for causing a transcoding proxy to facilitate browsing between a plurality of client devices and a plurality of servers connected via a communication network, the computer readable program code means in said article of manufacture comprising computer readable program code means for causing a computer to effect:

receiving a request from one of the client devices for an object stored at one of the servers,

forwarding the request for the object to said one of the servers,

receiving the object from said one of the servers,

examining preferences specified by a user of said one of the client devices,

examining contents of the object,

examining communication network characteristics,

choosing a set of transcoding parameters,

forming a transcoded form of the object,

providing feedback to the user about a level of transcoding performed on the object to form the transcoded form, and

sending the transcoded form to said one of the clients.

43. An article of manufacture as recited in claim 42, the computer readable program code means in said article of manufacture further comprising computer readable program code means for causing a computer to effect determining dimensions of the object, and calculating the compression ratio of the object.

44. An article of manufacture as recited in claim 42, the computer readable program code means in said article of manufacture further comprising computer readable program code means for causing a computer to effect starting the step of forming a transcoded form before the step of receiving the object from said one of the servers is complete.

45. A computer program product comprising a computer usable medium having computer readable program code means embodied therein for causing a proxy to form a transcoded form of an object received from a server in satisfaction of a request from a client for an object available from the server, the computer readable program code means in said computer program product comprising computer readable program code means for causing a computer to effect:

dynamically adapting parameters for transcoding the object for the client,

forming a transcoded form of the object,

gathering present network characteristics between the server and the proxy and between the proxy and the client

adapting parameters for transcoding based upon the estimated bandwidth and preferences of the user, and

sending the transcoded form to the client.