I am trying to optimize what we call AJAX request polling frequency in the domain of web design. Here's a general version of the problem in simple lingo:

Problem Statement:

Suppose there are 3 persons - consumer (C), producer(P) and a messenger(M). The consumer and producer are some distant apart and can't communicate directly. The messenger - who works for the consumer - takes order from consumer, walks up to producer, places the order and come back to consumer. Messenger needs some finite amount of time to make the travel between P and C.

Now different orders require different amount of time for processing. After an order is placed, the M and C have no way to know how long the order processing will take. Hence, the messenger is required to make repeated trips to the Producer to check if the order is ready. It works in this way:

  • Step 1: Messenger waits for W amount of time
  • Step 2: M Goes to the producer to see if order is ready
  • Step 3: a) Order ready - come back with the produced item b) Not ready - come back and repeat from step 1.

Now, I tabulated the time taken by each orders and plotted them against the number of orders taking that time. I got this:

   |                |  |             
25 |                |  |  |             
   |             |  |  |  |           
20 |             |  |  |  |  |  |         
   |          |  |  |  |  |  |  |  |       
15 |          |  |  |  |  |  |  |  |  |     
   |       |  |  |  |  |  |  |  |  |  |     
10 |    |  |  |  |  |  |  |  |  |  |  |  |  |   
   | |  |  |  |  |  |  |  |  |  |  |  |  |  |  | 
0  +-|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|---
  1  5  10 20 25 30 35 40 45 50 55 60 65 70 75 85 90    

As you can see, most orders take around 35 to 40 units of time (let's say seconds) to complete whereas some orders get completed in 5-10 seconds and some takes 80-90 seconds.

My Goal:

It is costly to have a high-frequency W. Right now my messenger is checking back in every W seconds. Instead of keeping this checking frequency W as constant, can we find some other checking frequency - may be a variable one where we adjust the frequency as we go along - that would ensure the least overall waiting time combining consumer and producer waiting time together.

As you can tell, I am obviously not very good in articulating the problem very well. So, let me know if you need clarifications in comments.

~~~ EDIT - Defining an Evaluation Model ~~~

As some of the comments suggest, it's important to include W in the evaluation model. I think what I am really trying to do here is to minimize unsuccessful pollings (like polling that comes back empty handed as producer hasn't finished producing)

Say, messenger takes W amount of time to do one polling. If I take a given sample set of N pollings and if only S fractions of those polls were successful, then my intuition tells me that,

S = function (N, W)

So the question is - given a specific set of N, how do I find a W that maximizes S

  • $\begingroup$ Is the wait time $W$ required to be a constant? Or can it vary, say, by how much time has elapsed since the initial request? $\endgroup$ – mhum Feb 12 '16 at 1:54
  • $\begingroup$ So what's the question? Is the question, how do I find the optimal frequency $W$, that ensures the least waiting time? The obvious answer is to poll as frequently as possible, as your evaluation criteria doesn't take into account the cost of a high-frequency W. I encourage you to edit your question to clarify exactly what metric you want to optimize, i.e., what quantity you are trying to maximize. Have you tried writing code to simulate the behavior with different values of $W$? (Also, can you say anything about why you selected the linear-programming tag?) $\endgroup$ – D.W. Feb 12 '16 at 5:51
  • $\begingroup$ Is the range 5-90 all you need to consider, or is this just a portion of the distribution of durations taken to complete orders? A specific cost model would be necessary to know what to optimize, like D.W. said. $\endgroup$ – G. Bach Feb 12 '16 at 8:54
  • 1
    $\begingroup$ The way to maximize $S$ is to make $W$ be very low frequency: wait 90 seconds before polling for the first time. That's probably not the answer you wanted, though, which indicates that maximizing $S$ probably isn't the question you want answered. Probably you need to think more on what you're trying to maximize/optimize, i.e., what the cost function is. $\endgroup$ – D.W. Feb 12 '16 at 17:14
  • 2
    $\begingroup$ I agree with @D.W. -- if all you cared about was minimizing the wait time, then you'd likely poll as frequently as possible (unless the minimum polling interval was rather large, for some definition of "rather large") and if all you cared about was unsuccessful polls, you'd just wait a super long time to make sure you'd only poll once. I think if you fleshed out the real reason why you wouldn't just poll as frequently as possible, it might help formulate the problem and tradeoffs better. $\endgroup$ – mhum Feb 12 '16 at 18:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.