- add sources.
[platform/framework/web/crosswalk.git] / src / net / url_request / url_request_throttler_simulation_unittest.cc
1 // Copyright (c) 2012 The Chromium Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4
5 // The tests in this file attempt to verify the following through simulation:
6 // a) That a server experiencing overload will actually benefit from the
7 //    anti-DDoS throttling logic, i.e. that its traffic spike will subside
8 //    and be distributed over a longer period of time;
9 // b) That "well-behaved" clients of a server under DDoS attack actually
10 //    benefit from the anti-DDoS throttling logic; and
11 // c) That the approximate increase in "perceived downtime" introduced by
12 //    anti-DDoS throttling for various different actual downtimes is what
13 //    we expect it to be.
14
15 #include <cmath>
16 #include <limits>
17 #include <vector>
18
19 #include "base/environment.h"
20 #include "base/memory/scoped_vector.h"
21 #include "base/rand_util.h"
22 #include "base/time/time.h"
23 #include "net/base/request_priority.h"
24 #include "net/url_request/url_request_test_util.h"
25 #include "net/url_request/url_request_throttler_manager.h"
26 #include "net/url_request/url_request_throttler_test_support.h"
27 #include "testing/gtest/include/gtest/gtest.h"
28
29 using base::TimeDelta;
30 using base::TimeTicks;
31
32 namespace net {
33 namespace {
34
35 // Set this variable in your environment if you want to see verbose results
36 // of the simulation tests.
37 const char kShowSimulationVariableName[] = "SHOW_SIMULATION_RESULTS";
38
39 // Prints output only if a given environment variable is set. We use this
40 // to not print any output for human evaluation when the test is run without
41 // supervision.
42 void VerboseOut(const char* format, ...) {
43   static bool have_checked_environment = false;
44   static bool should_print = false;
45   if (!have_checked_environment) {
46     have_checked_environment = true;
47     scoped_ptr<base::Environment> env(base::Environment::Create());
48     if (env->HasVar(kShowSimulationVariableName))
49       should_print = true;
50   }
51
52   if (should_print) {
53     va_list arglist;
54     va_start(arglist, format);
55     vprintf(format, arglist);
56     va_end(arglist);
57   }
58 }
59
60 // A simple two-phase discrete time simulation. Actors are added in the order
61 // they should take action at every tick of the clock. Ticks of the clock
62 // are two-phase:
63 // - Phase 1 advances every actor's time to a new absolute time.
64 // - Phase 2 asks each actor to perform their action.
65 class DiscreteTimeSimulation {
66  public:
67   class Actor {
68    public:
69     virtual ~Actor() {}
70     virtual void AdvanceTime(const TimeTicks& absolute_time) = 0;
71     virtual void PerformAction() = 0;
72   };
73
74   DiscreteTimeSimulation() {}
75
76   // Adds an |actor| to the simulation. The client of the simulation maintains
77   // ownership of |actor| and must ensure its lifetime exceeds that of the
78   // simulation. Actors should be added in the order you wish for them to
79   // act at each tick of the simulation.
80   void AddActor(Actor* actor) {
81     actors_.push_back(actor);
82   }
83
84   // Runs the simulation for, pretending |time_between_ticks| passes from one
85   // tick to the next. The start time will be the current real time. The
86   // simulation will stop when the simulated duration is equal to or greater
87   // than |maximum_simulated_duration|.
88   void RunSimulation(const TimeDelta& maximum_simulated_duration,
89                      const TimeDelta& time_between_ticks) {
90     TimeTicks start_time = TimeTicks();
91     TimeTicks now = start_time;
92     while ((now - start_time) <= maximum_simulated_duration) {
93       for (std::vector<Actor*>::iterator it = actors_.begin();
94            it != actors_.end();
95            ++it) {
96         (*it)->AdvanceTime(now);
97       }
98
99       for (std::vector<Actor*>::iterator it = actors_.begin();
100            it != actors_.end();
101            ++it) {
102         (*it)->PerformAction();
103       }
104
105       now += time_between_ticks;
106     }
107   }
108
109  private:
110   std::vector<Actor*> actors_;
111
112   DISALLOW_COPY_AND_ASSIGN(DiscreteTimeSimulation);
113 };
114
115 // Represents a web server in a simulation of a server under attack by
116 // a lot of clients. Must be added to the simulation's list of actors
117 // after all |Requester| objects.
118 class Server : public DiscreteTimeSimulation::Actor {
119  public:
120   Server(int max_queries_per_tick, double request_drop_ratio)
121       : max_queries_per_tick_(max_queries_per_tick),
122         request_drop_ratio_(request_drop_ratio),
123         num_overloaded_ticks_remaining_(0),
124         num_current_tick_queries_(0),
125         num_overloaded_ticks_(0),
126         max_experienced_queries_per_tick_(0),
127         mock_request_(GURL(), DEFAULT_PRIORITY, NULL, &context_) {}
128
129   void SetDowntime(const TimeTicks& start_time, const TimeDelta& duration) {
130     start_downtime_ = start_time;
131     end_downtime_ = start_time + duration;
132   }
133
134   virtual void AdvanceTime(const TimeTicks& absolute_time) OVERRIDE {
135     now_ = absolute_time;
136   }
137
138   virtual void PerformAction() OVERRIDE {
139     // We are inserted at the end of the actor's list, so all Requester
140     // instances have already done their bit.
141     if (num_current_tick_queries_ > max_experienced_queries_per_tick_)
142       max_experienced_queries_per_tick_ = num_current_tick_queries_;
143
144     if (num_current_tick_queries_ > max_queries_per_tick_) {
145       // We pretend the server fails for the next several ticks after it
146       // gets overloaded.
147       num_overloaded_ticks_remaining_ = 5;
148       ++num_overloaded_ticks_;
149     } else if (num_overloaded_ticks_remaining_ > 0) {
150       --num_overloaded_ticks_remaining_;
151     }
152
153     requests_per_tick_.push_back(num_current_tick_queries_);
154     num_current_tick_queries_ = 0;
155   }
156
157   // This is called by Requester. It returns the response code from
158   // the server.
159   int HandleRequest() {
160     ++num_current_tick_queries_;
161     if (!start_downtime_.is_null() &&
162         start_downtime_ < now_ && now_ < end_downtime_) {
163       // For the simulation measuring the increase in perceived
164       // downtime, it might be interesting to count separately the
165       // queries seen by the server (assuming a front-end reverse proxy
166       // is what actually serves up the 503s in this case) so that we could
167       // visualize the traffic spike seen by the server when it comes up,
168       // which would in many situations be ameliorated by the anti-DDoS
169       // throttling.
170       return 503;
171     }
172
173     if ((num_overloaded_ticks_remaining_ > 0 ||
174          num_current_tick_queries_ > max_queries_per_tick_) &&
175         base::RandDouble() < request_drop_ratio_) {
176       return 503;
177     }
178
179     return 200;
180   }
181
182   int num_overloaded_ticks() const {
183     return num_overloaded_ticks_;
184   }
185
186   int max_experienced_queries_per_tick() const {
187     return max_experienced_queries_per_tick_;
188   }
189
190   const URLRequest& mock_request() const {
191     return mock_request_;
192   }
193
194   std::string VisualizeASCII(int terminal_width) {
195     // Account for | characters we place at left of graph.
196     terminal_width -= 1;
197
198     VerboseOut("Overloaded for %d of %d ticks.\n",
199                num_overloaded_ticks_, requests_per_tick_.size());
200     VerboseOut("Got maximum of %d requests in a tick.\n\n",
201                max_experienced_queries_per_tick_);
202
203     VerboseOut("Traffic graph:\n\n");
204
205     // Printing the graph like this is a bit overkill, but was very useful
206     // while developing the various simulations to see if they were testing
207     // the corner cases we want to simulate.
208
209     // Find the smallest number of whole ticks we need to group into a
210     // column that will let all ticks fit into the column width we have.
211     int num_ticks = requests_per_tick_.size();
212     double ticks_per_column_exact =
213         static_cast<double>(num_ticks) / static_cast<double>(terminal_width);
214     int ticks_per_column = std::ceil(ticks_per_column_exact);
215     DCHECK_GE(ticks_per_column * terminal_width, num_ticks);
216
217     // Sum up the column values.
218     int num_columns = num_ticks / ticks_per_column;
219     if (num_ticks % ticks_per_column)
220       ++num_columns;
221     DCHECK_LE(num_columns, terminal_width);
222     scoped_ptr<int[]> columns(new int[num_columns]);
223     for (int tx = 0; tx < num_ticks; ++tx) {
224       int cx = tx / ticks_per_column;
225       if (tx % ticks_per_column == 0)
226         columns[cx] = 0;
227       columns[cx] += requests_per_tick_[tx];
228     }
229
230     // Find the lowest integer divisor that will let the column values
231     // be represented in a graph of maximum height 50.
232     int max_value = 0;
233     for (int cx = 0; cx < num_columns; ++cx)
234       max_value = std::max(max_value, columns[cx]);
235     const int kNumRows = 50;
236     double row_divisor_exact = max_value / static_cast<double>(kNumRows);
237     int row_divisor = std::ceil(row_divisor_exact);
238     DCHECK_GE(row_divisor * kNumRows, max_value);
239
240     // To show the overload line, we calculate the appropriate value.
241     int overload_value = max_queries_per_tick_ * ticks_per_column;
242
243     // When num_ticks is not a whole multiple of ticks_per_column, the last
244     // column includes fewer ticks than the others. In this case, don't
245     // print it so that we don't show an inconsistent value.
246     int num_printed_columns = num_columns;
247     if (num_ticks % ticks_per_column)
248       --num_printed_columns;
249
250     // This is a top-to-bottom traversal of rows, left-to-right per row.
251     std::string output;
252     for (int rx = 0; rx < kNumRows; ++rx) {
253       int range_min = (kNumRows - rx) * row_divisor;
254       int range_max = range_min + row_divisor;
255       if (range_min == 0)
256         range_min = -1;  // Make 0 values fit in the bottom range.
257       output.append("|");
258       for (int cx = 0; cx < num_printed_columns; ++cx) {
259         char block = ' ';
260         // Show the overload line.
261         if (range_min < overload_value && overload_value <= range_max)
262           block = '-';
263
264         // Preferentially, show the graph line.
265         if (range_min < columns[cx] && columns[cx] <= range_max)
266           block = '#';
267
268         output.append(1, block);
269       }
270       output.append("\n");
271     }
272     output.append("|");
273     output.append(num_printed_columns, '=');
274
275     return output;
276   }
277
278  private:
279   TimeTicks now_;
280   TimeTicks start_downtime_;  // Can be 0 to say "no downtime".
281   TimeTicks end_downtime_;
282   const int max_queries_per_tick_;
283   const double request_drop_ratio_;  // Ratio of requests to 503 when failing.
284   int num_overloaded_ticks_remaining_;
285   int num_current_tick_queries_;
286   int num_overloaded_ticks_;
287   int max_experienced_queries_per_tick_;
288   std::vector<int> requests_per_tick_;
289
290   TestURLRequestContext context_;
291   TestURLRequest mock_request_;
292
293   DISALLOW_COPY_AND_ASSIGN(Server);
294 };
295
296 // Mock throttler entry used by Requester class.
297 class MockURLRequestThrottlerEntry : public URLRequestThrottlerEntry {
298  public:
299   explicit MockURLRequestThrottlerEntry(URLRequestThrottlerManager* manager)
300       : URLRequestThrottlerEntry(manager, std::string()),
301         mock_backoff_entry_(&backoff_policy_) {}
302
303   virtual const BackoffEntry* GetBackoffEntry() const OVERRIDE {
304     return &mock_backoff_entry_;
305   }
306
307   virtual BackoffEntry* GetBackoffEntry() OVERRIDE {
308     return &mock_backoff_entry_;
309   }
310
311   virtual TimeTicks ImplGetTimeNow() const OVERRIDE {
312     return fake_now_;
313   }
314
315   void SetFakeNow(const TimeTicks& fake_time) {
316     fake_now_ = fake_time;
317     mock_backoff_entry_.set_fake_now(fake_time);
318   }
319
320   TimeTicks fake_now() const {
321     return fake_now_;
322   }
323
324  protected:
325   virtual ~MockURLRequestThrottlerEntry() {}
326
327  private:
328   TimeTicks fake_now_;
329   MockBackoffEntry mock_backoff_entry_;
330 };
331
332 // Registry of results for a class of |Requester| objects (e.g. attackers vs.
333 // regular clients).
334 class RequesterResults {
335 public:
336   RequesterResults()
337       : num_attempts_(0), num_successful_(0), num_failed_(0), num_blocked_(0) {
338   }
339
340   void AddSuccess() {
341     ++num_attempts_;
342     ++num_successful_;
343   }
344
345   void AddFailure() {
346     ++num_attempts_;
347     ++num_failed_;
348   }
349
350   void AddBlocked() {
351     ++num_attempts_;
352     ++num_blocked_;
353   }
354
355   int num_attempts() const { return num_attempts_; }
356   int num_successful() const { return num_successful_; }
357   int num_failed() const { return num_failed_; }
358   int num_blocked() const { return num_blocked_; }
359
360   double GetBlockedRatio() {
361     DCHECK(num_attempts_);
362     return static_cast<double>(num_blocked_) /
363         static_cast<double>(num_attempts_);
364   }
365
366   double GetSuccessRatio() {
367     DCHECK(num_attempts_);
368     return static_cast<double>(num_successful_) /
369         static_cast<double>(num_attempts_);
370   }
371
372   void PrintResults(const char* class_description) {
373     if (num_attempts_ == 0) {
374       VerboseOut("No data for %s\n", class_description);
375       return;
376     }
377
378     VerboseOut("Requester results for %s\n", class_description);
379     VerboseOut("  %d attempts\n", num_attempts_);
380     VerboseOut("  %d successes\n", num_successful_);
381     VerboseOut("  %d 5xx responses\n", num_failed_);
382     VerboseOut("  %d requests blocked\n", num_blocked_);
383     VerboseOut("  %.2f success ratio\n", GetSuccessRatio());
384     VerboseOut("  %.2f blocked ratio\n", GetBlockedRatio());
385     VerboseOut("\n");
386   }
387
388  private:
389   int num_attempts_;
390   int num_successful_;
391   int num_failed_;
392   int num_blocked_;
393 };
394
395 // Represents an Requester in a simulated DDoS situation, that periodically
396 // requests a specific resource.
397 class Requester : public DiscreteTimeSimulation::Actor {
398  public:
399   Requester(MockURLRequestThrottlerEntry* throttler_entry,
400             const TimeDelta& time_between_requests,
401             Server* server,
402             RequesterResults* results)
403       : throttler_entry_(throttler_entry),
404         time_between_requests_(time_between_requests),
405         last_attempt_was_failure_(false),
406         server_(server),
407         results_(results) {
408     DCHECK(server_);
409   }
410
411   virtual void AdvanceTime(const TimeTicks& absolute_time) OVERRIDE {
412     if (time_of_last_success_.is_null())
413       time_of_last_success_ = absolute_time;
414
415     throttler_entry_->SetFakeNow(absolute_time);
416   }
417
418   virtual void PerformAction() OVERRIDE {
419     TimeDelta effective_delay = time_between_requests_;
420     TimeDelta current_jitter = TimeDelta::FromMilliseconds(
421         request_jitter_.InMilliseconds() * base::RandDouble());
422     if (base::RandInt(0, 1)) {
423       effective_delay -= current_jitter;
424     } else {
425       effective_delay += current_jitter;
426     }
427
428     if (throttler_entry_->fake_now() - time_of_last_attempt_ >
429         effective_delay) {
430       if (!throttler_entry_->ShouldRejectRequest(server_->mock_request())) {
431         int status_code = server_->HandleRequest();
432         MockURLRequestThrottlerHeaderAdapter response_headers(status_code);
433         throttler_entry_->UpdateWithResponse(std::string(), &response_headers);
434
435         if (status_code == 200) {
436           if (results_)
437             results_->AddSuccess();
438
439           if (last_attempt_was_failure_) {
440             last_downtime_duration_ =
441                 throttler_entry_->fake_now() - time_of_last_success_;
442           }
443
444           time_of_last_success_ = throttler_entry_->fake_now();
445           last_attempt_was_failure_ = false;
446         } else {
447           if (results_)
448             results_->AddFailure();
449           last_attempt_was_failure_ = true;
450         }
451       } else {
452         if (results_)
453           results_->AddBlocked();
454         last_attempt_was_failure_ = true;
455       }
456
457       time_of_last_attempt_ = throttler_entry_->fake_now();
458     }
459   }
460
461   // Adds a delay until the first request, equal to a uniformly distributed
462   // value between now and now + max_delay.
463   void SetStartupJitter(const TimeDelta& max_delay) {
464     int delay_ms = base::RandInt(0, max_delay.InMilliseconds());
465     time_of_last_attempt_ = TimeTicks() +
466         TimeDelta::FromMilliseconds(delay_ms) - time_between_requests_;
467   }
468
469   void SetRequestJitter(const TimeDelta& request_jitter) {
470     request_jitter_ = request_jitter;
471   }
472
473   TimeDelta last_downtime_duration() const { return last_downtime_duration_; }
474
475  private:
476   scoped_refptr<MockURLRequestThrottlerEntry> throttler_entry_;
477   const TimeDelta time_between_requests_;
478   TimeDelta request_jitter_;
479   TimeTicks time_of_last_attempt_;
480   TimeTicks time_of_last_success_;
481   bool last_attempt_was_failure_;
482   TimeDelta last_downtime_duration_;
483   Server* const server_;
484   RequesterResults* const results_;  // May be NULL.
485
486   DISALLOW_COPY_AND_ASSIGN(Requester);
487 };
488
489 void SimulateAttack(Server* server,
490                     RequesterResults* attacker_results,
491                     RequesterResults* client_results,
492                     bool enable_throttling) {
493   const size_t kNumAttackers = 50;
494   const size_t kNumClients = 50;
495   DiscreteTimeSimulation simulation;
496   URLRequestThrottlerManager manager;
497   ScopedVector<Requester> requesters;
498   for (size_t i = 0; i < kNumAttackers; ++i) {
499     // Use a tiny time_between_requests so the attackers will ping the
500     // server at every tick of the simulation.
501     scoped_refptr<MockURLRequestThrottlerEntry> throttler_entry(
502         new MockURLRequestThrottlerEntry(&manager));
503     if (!enable_throttling)
504       throttler_entry->DisableBackoffThrottling();
505
506       Requester* attacker = new Requester(throttler_entry.get(),
507                                         TimeDelta::FromMilliseconds(1),
508                                         server,
509                                         attacker_results);
510     attacker->SetStartupJitter(TimeDelta::FromSeconds(120));
511     requesters.push_back(attacker);
512     simulation.AddActor(attacker);
513   }
514   for (size_t i = 0; i < kNumClients; ++i) {
515     // Normal clients only make requests every 2 minutes, plus/minus 1 minute.
516     scoped_refptr<MockURLRequestThrottlerEntry> throttler_entry(
517         new MockURLRequestThrottlerEntry(&manager));
518     if (!enable_throttling)
519       throttler_entry->DisableBackoffThrottling();
520
521     Requester* client = new Requester(throttler_entry.get(),
522                                       TimeDelta::FromMinutes(2),
523                                       server,
524                                       client_results);
525     client->SetStartupJitter(TimeDelta::FromSeconds(120));
526     client->SetRequestJitter(TimeDelta::FromMinutes(1));
527     requesters.push_back(client);
528     simulation.AddActor(client);
529   }
530   simulation.AddActor(server);
531
532   simulation.RunSimulation(TimeDelta::FromMinutes(6),
533                            TimeDelta::FromSeconds(1));
534 }
535
536 TEST(URLRequestThrottlerSimulation, HelpsInAttack) {
537   Server unprotected_server(30, 1.0);
538   RequesterResults unprotected_attacker_results;
539   RequesterResults unprotected_client_results;
540   Server protected_server(30, 1.0);
541   RequesterResults protected_attacker_results;
542   RequesterResults protected_client_results;
543   SimulateAttack(&unprotected_server,
544                  &unprotected_attacker_results,
545                  &unprotected_client_results,
546                  false);
547   SimulateAttack(&protected_server,
548                  &protected_attacker_results,
549                  &protected_client_results,
550                  true);
551
552   // These assert that the DDoS protection actually benefits the
553   // server. Manual inspection of the traffic graphs will show this
554   // even more clearly.
555   EXPECT_GT(unprotected_server.num_overloaded_ticks(),
556             protected_server.num_overloaded_ticks());
557   EXPECT_GT(unprotected_server.max_experienced_queries_per_tick(),
558             protected_server.max_experienced_queries_per_tick());
559
560   // These assert that the DDoS protection actually benefits non-malicious
561   // (and non-degenerate/accidentally DDoSing) users.
562   EXPECT_LT(protected_client_results.GetBlockedRatio(),
563             protected_attacker_results.GetBlockedRatio());
564   EXPECT_GT(protected_client_results.GetSuccessRatio(),
565             unprotected_client_results.GetSuccessRatio());
566
567   // The rest is just for optional manual evaluation of the results;
568   // in particular the traffic pattern is interesting.
569
570   VerboseOut("\nUnprotected server's results:\n\n");
571   VerboseOut(unprotected_server.VisualizeASCII(132).c_str());
572   VerboseOut("\n\n");
573   VerboseOut("Protected server's results:\n\n");
574   VerboseOut(protected_server.VisualizeASCII(132).c_str());
575   VerboseOut("\n\n");
576
577   unprotected_attacker_results.PrintResults(
578       "attackers attacking unprotected server.");
579   unprotected_client_results.PrintResults(
580       "normal clients making requests to unprotected server.");
581   protected_attacker_results.PrintResults(
582       "attackers attacking protected server.");
583   protected_client_results.PrintResults(
584       "normal clients making requests to protected server.");
585 }
586
587 // Returns the downtime perceived by the client, as a ratio of the
588 // actual downtime.
589 double SimulateDowntime(const TimeDelta& duration,
590                         const TimeDelta& average_client_interval,
591                         bool enable_throttling) {
592   TimeDelta time_between_ticks = duration / 200;
593   TimeTicks start_downtime = TimeTicks() + (duration / 2);
594
595   // A server that never rejects requests, but will go down for maintenance.
596   Server server(std::numeric_limits<int>::max(), 1.0);
597   server.SetDowntime(start_downtime, duration);
598
599   URLRequestThrottlerManager manager;
600   scoped_refptr<MockURLRequestThrottlerEntry> throttler_entry(
601       new MockURLRequestThrottlerEntry(&manager));
602   if (!enable_throttling)
603     throttler_entry->DisableBackoffThrottling();
604
605   Requester requester(
606       throttler_entry.get(), average_client_interval, &server, NULL);
607   requester.SetStartupJitter(duration / 3);
608   requester.SetRequestJitter(average_client_interval);
609
610   DiscreteTimeSimulation simulation;
611   simulation.AddActor(&requester);
612   simulation.AddActor(&server);
613
614   simulation.RunSimulation(duration * 2, time_between_ticks);
615
616   return static_cast<double>(
617       requester.last_downtime_duration().InMilliseconds()) /
618       static_cast<double>(duration.InMilliseconds());
619 }
620
621 TEST(URLRequestThrottlerSimulation, PerceivedDowntimeRatio) {
622   struct Stats {
623     // Expected interval that we expect the ratio of downtime when anti-DDoS
624     // is enabled and downtime when anti-DDoS is not enabled to fall within.
625     //
626     // The expected interval depends on two things:  The exponential back-off
627     // policy encoded in URLRequestThrottlerEntry, and the test or set of
628     // tests that the Stats object is tracking (e.g. a test where the client
629     // retries very rapidly on a very long downtime will tend to increase the
630     // number).
631     //
632     // To determine an appropriate new interval when parameters have changed,
633     // run the test a few times (you may have to Ctrl-C out of it after a few
634     // seconds) and choose an interval that the test converges quickly and
635     // reliably to.  Then set the new interval, and run the test e.g. 20 times
636     // in succession to make sure it never takes an obscenely long time to
637     // converge to this interval.
638     double expected_min_increase;
639     double expected_max_increase;
640
641     size_t num_runs;
642     double total_ratio_unprotected;
643     double total_ratio_protected;
644
645     bool DidConverge(double* increase_ratio_out) {
646       double unprotected_ratio = total_ratio_unprotected / num_runs;
647       double protected_ratio = total_ratio_protected / num_runs;
648       double increase_ratio = protected_ratio / unprotected_ratio;
649       if (increase_ratio_out)
650         *increase_ratio_out = increase_ratio;
651       return expected_min_increase <= increase_ratio &&
652           increase_ratio <= expected_max_increase;
653     }
654
655     void ReportTrialResult(double increase_ratio) {
656       VerboseOut(
657           "  Perceived downtime with throttling is %.4f times without.\n",
658           increase_ratio);
659       VerboseOut("  Test result after %d trials.\n", num_runs);
660     }
661   };
662
663   Stats global_stats = { 1.08, 1.15 };
664
665   struct Trial {
666     TimeDelta duration;
667     TimeDelta average_client_interval;
668     Stats stats;
669
670     void PrintTrialDescription() {
671       double duration_minutes =
672           static_cast<double>(duration.InSeconds()) / 60.0;
673       double interval_minutes =
674           static_cast<double>(average_client_interval.InSeconds()) / 60.0;
675       VerboseOut("Trial with %.2f min downtime, avg. interval %.2f min.\n",
676                  duration_minutes, interval_minutes);
677     }
678   };
679
680   // We don't set or check expected ratio intervals on individual
681   // experiments as this might make the test too fragile, but we
682   // print them out at the end for manual evaluation (we want to be
683   // able to make claims about the expected ratios depending on the
684   // type of behavior of the client and the downtime, e.g. the difference
685   // in behavior between a client making requests every few minutes vs.
686   // one that makes a request every 15 seconds).
687   Trial trials[] = {
688     { TimeDelta::FromSeconds(10), TimeDelta::FromSeconds(3) },
689     { TimeDelta::FromSeconds(30), TimeDelta::FromSeconds(7) },
690     { TimeDelta::FromMinutes(5), TimeDelta::FromSeconds(30) },
691     { TimeDelta::FromMinutes(10), TimeDelta::FromSeconds(20) },
692     { TimeDelta::FromMinutes(20), TimeDelta::FromSeconds(15) },
693     { TimeDelta::FromMinutes(20), TimeDelta::FromSeconds(50) },
694     { TimeDelta::FromMinutes(30), TimeDelta::FromMinutes(2) },
695     { TimeDelta::FromMinutes(30), TimeDelta::FromMinutes(5) },
696     { TimeDelta::FromMinutes(40), TimeDelta::FromMinutes(7) },
697     { TimeDelta::FromMinutes(40), TimeDelta::FromMinutes(2) },
698     { TimeDelta::FromMinutes(40), TimeDelta::FromSeconds(15) },
699     { TimeDelta::FromMinutes(60), TimeDelta::FromMinutes(7) },
700     { TimeDelta::FromMinutes(60), TimeDelta::FromMinutes(2) },
701     { TimeDelta::FromMinutes(60), TimeDelta::FromSeconds(15) },
702     { TimeDelta::FromMinutes(80), TimeDelta::FromMinutes(20) },
703     { TimeDelta::FromMinutes(80), TimeDelta::FromMinutes(3) },
704     { TimeDelta::FromMinutes(80), TimeDelta::FromSeconds(15) },
705
706     // Most brutal?
707     { TimeDelta::FromMinutes(45), TimeDelta::FromMilliseconds(500) },
708   };
709
710   // If things don't converge by the time we've done 100K trials, then
711   // clearly one or more of the expected intervals are wrong.
712   while (global_stats.num_runs < 100000) {
713     for (size_t i = 0; i < ARRAYSIZE_UNSAFE(trials); ++i) {
714       ++global_stats.num_runs;
715       ++trials[i].stats.num_runs;
716       double ratio_unprotected = SimulateDowntime(
717           trials[i].duration, trials[i].average_client_interval, false);
718       double ratio_protected = SimulateDowntime(
719           trials[i].duration, trials[i].average_client_interval, true);
720       global_stats.total_ratio_unprotected += ratio_unprotected;
721       global_stats.total_ratio_protected += ratio_protected;
722       trials[i].stats.total_ratio_unprotected += ratio_unprotected;
723       trials[i].stats.total_ratio_protected += ratio_protected;
724     }
725
726     double increase_ratio;
727     if (global_stats.DidConverge(&increase_ratio))
728       break;
729
730     if (global_stats.num_runs > 200) {
731       VerboseOut("Test has not yet converged on expected interval.\n");
732       global_stats.ReportTrialResult(increase_ratio);
733     }
734   }
735
736   double average_increase_ratio;
737   EXPECT_TRUE(global_stats.DidConverge(&average_increase_ratio));
738
739   // Print individual trial results for optional manual evaluation.
740   double max_increase_ratio = 0.0;
741   for (size_t i = 0; i < ARRAYSIZE_UNSAFE(trials); ++i) {
742     double increase_ratio;
743     trials[i].stats.DidConverge(&increase_ratio);
744     max_increase_ratio = std::max(max_increase_ratio, increase_ratio);
745     trials[i].PrintTrialDescription();
746     trials[i].stats.ReportTrialResult(increase_ratio);
747   }
748
749   VerboseOut("Average increase ratio was %.4f\n", average_increase_ratio);
750   VerboseOut("Maximum increase ratio was %.4f\n", max_increase_ratio);
751 }
752
753 }  // namespace
754 }  // namespace net