[svn] commit: r3813 - in /branches/trac408: ./ src/lib/nsas/tests/random_number_generator_unittest.cc src/lib/nsas/tests/zone_entry_unittest.cc
BIND 10 source code commits
bind10-changes at lists.isc.org
Mon Dec 13 15:17:34 UTC 2010
Author: vorner
Date: Mon Dec 13 15:17:34 2010
New Revision: 3813
Log:
Sync with #356
Modified:
branches/trac408/ (props changed)
branches/trac408/src/lib/nsas/tests/random_number_generator_unittest.cc
branches/trac408/src/lib/nsas/tests/zone_entry_unittest.cc
Modified: branches/trac408/src/lib/nsas/tests/random_number_generator_unittest.cc
==============================================================================
--- branches/trac408/src/lib/nsas/tests/random_number_generator_unittest.cc (original)
+++ branches/trac408/src/lib/nsas/tests/random_number_generator_unittest.cc Mon Dec 13 15:17:34 2010
@@ -139,54 +139,76 @@
// Test the randomization of the generator
TEST_F(WeightedRandomIntegerGeneratorTest, WeightedRandomization)
{
- {
- vector<double> probabilities;
- probabilities.push_back(0.5);
- probabilities.push_back(0.5);
+ const int repeats = 100000;
+ // We repeat the simulation for N=repeats times
+ // for each probability p, its average is mu = N*p
+ // variance sigma^2 = N * p * (1-p)
+ // sigma = sqrt(N*2/9)
+ // we should make sure that mu - 4sigma < count < mu + 4sigma
+ // which means for 99.99366% of the time this should be true
+ {
+ double p = 0.5;
+ vector<double> probabilities;
+ probabilities.push_back(p);
+ probabilities.push_back(p);
// Uniformly generated integers
WeightedRandomIntegerGenerator gen(probabilities);
int c1 = 0;
int c2 = 0;
- for(int i = 0; i < 100000; ++i){
- int n = gen();
- if(n == 0) ++c1;
- else if(n == 1) ++c2;
- }
- // The probabilities should almost equal
- ASSERT_EQ(1, (int)(c1*1.0/c2 + 0.5));
- }
-
- {
- vector<double> probabilities;
- int c1 = 0;
- int c2 = 0;
- probabilities.push_back(0.2);
- probabilities.push_back(0.8);
- WeightedRandomIntegerGenerator gen(probabilities);
- for(int i = 0; i < 100000; ++i){
- int n = gen();
- if(n == 0) ++c1;
- else if(n == 1) ++c2;
- }
- // The 2nd integer count should be 4 times of 1st one
- ASSERT_EQ(4, (int)(c2*1.0/c1 + 0.5));
- }
-
- {
- vector<double> probabilities;
- int c1 = 0;
- int c2 = 0;
- probabilities.push_back(0.8);
- probabilities.push_back(0.2);
- WeightedRandomIntegerGenerator gen(probabilities);
- for(int i = 0; i < 100000; ++i){
- int n = gen();
- if(n == 0) ++c1;
- else if(n == 1) ++c2;
- }
- // The 1st integer count should be 4 times of 2nd one
- ASSERT_EQ(4, (int)(c1*1.0/c2 + 0.5));
+ for(int i = 0; i < repeats; ++i){
+ int n = gen();
+ if(n == 0) ++c1;
+ else if(n == 1) ++c2;
+ }
+ double mu = repeats * p;
+ double sigma = sqrt(repeats * p * (1 - p));
+ ASSERT_TRUE(fabs(c1 - mu) < 4*sigma);
+ ASSERT_TRUE(fabs(c2 - mu) < 4*sigma);
+ }
+
+ {
+ vector<double> probabilities;
+ int c1 = 0;
+ int c2 = 0;
+ double p1 = 0.2;
+ double p2 = 0.8;
+ probabilities.push_back(p1);
+ probabilities.push_back(p2);
+ WeightedRandomIntegerGenerator gen(probabilities);
+ for(int i = 0; i < repeats; ++i){
+ int n = gen();
+ if(n == 0) ++c1;
+ else if(n == 1) ++c2;
+ }
+ double mu1 = repeats * p1;
+ double mu2 = repeats * p2;
+ double sigma1 = sqrt(repeats * p1 * (1 - p1));
+ double sigma2 = sqrt(repeats * p2 * (1 - p2));
+ ASSERT_TRUE(fabs(c1 - mu1) < 4*sigma1);
+ ASSERT_TRUE(fabs(c2 - mu2) < 4*sigma2);
+ }
+
+ {
+ vector<double> probabilities;
+ int c1 = 0;
+ int c2 = 0;
+ double p1 = 0.8;
+ double p2 = 0.2;
+ probabilities.push_back(p1);
+ probabilities.push_back(p2);
+ WeightedRandomIntegerGenerator gen(probabilities);
+ for(int i = 0; i < repeats; ++i){
+ int n = gen();
+ if(n == 0) ++c1;
+ else if(n == 1) ++c2;
+ }
+ double mu1 = repeats * p1;
+ double mu2 = repeats * p2;
+ double sigma1 = sqrt(repeats * p1 * (1 - p1));
+ double sigma2 = sqrt(repeats * p2 * (1 - p2));
+ ASSERT_TRUE(fabs(c1 - mu1) < 4*sigma1);
+ ASSERT_TRUE(fabs(c2 - mu2) < 4*sigma2);
}
{
@@ -194,53 +216,74 @@
int c1 = 0;
int c2 = 0;
int c3 = 0;
- probabilities.push_back(0.5);
- probabilities.push_back(0.25);
- probabilities.push_back(0.25);
- WeightedRandomIntegerGenerator gen(probabilities);
- for(int i = 0; i < 100000; ++i){
+ double p1 = 0.5;
+ double p2 = 0.25;
+ double p3 = 0.25;
+ probabilities.push_back(p1);
+ probabilities.push_back(p2);
+ probabilities.push_back(p3);
+ WeightedRandomIntegerGenerator gen(probabilities);
+ for(int i = 0; i < repeats; ++i){
int n = gen();
if(n == 0) ++c1;
else if(n == 1) ++c2;
else if(n == 2) ++c3;
}
- // The 1st integer count should be double of 2nd one
- ASSERT_EQ(2, (int)(c1*1.0/c2 + 0.5));
- // The 1st integer count should be double of 3rd one
- ASSERT_EQ(2, (int)(c1*1.0/c3 + 0.5));
+ double mu1 = repeats * p1;
+ double mu2 = repeats * p2;
+ double mu3 = repeats * p3;
+ double sigma1 = sqrt(repeats * p1 * (1 - p1));
+ double sigma2 = sqrt(repeats * p2 * (1 - p2));
+ double sigma3 = sqrt(repeats * p3 * (1 - p3));
+ ASSERT_TRUE(fabs(c1 - mu1) < 4*sigma1);
+ ASSERT_TRUE(fabs(c2 - mu2) < 4*sigma2);
+ ASSERT_TRUE(fabs(c3 - mu3) < 4*sigma3);
}
}
// Test the reset function of generator
TEST_F(WeightedRandomIntegerGeneratorTest, ResetProbabilities)
{
- vector<double> probabilities;
- int c1 = 0;
- int c2 = 0;
- probabilities.push_back(0.8);
- probabilities.push_back(0.2);
- WeightedRandomIntegerGenerator gen(probabilities);
- for(int i = 0; i < 100000; ++i){
- int n = gen();
- if(n == 0) ++c1;
- else if(n == 1) ++c2;
- }
- // The 1st integer count should be 4 times of 2nd one
- ASSERT_EQ(4, (int)(c1*1.0/c2 + 0.5));
-
- // Reset the probabilities
- probabilities.clear();
- c1 = c2 = 0;
- probabilities.push_back(0.2);
- probabilities.push_back(0.8);
- gen.reset(probabilities);
- for(int i = 0; i < 100000; ++i){
- int n = gen();
- if(n == 0) ++c1;
- else if(n == 1) ++c2;
- }
- // The 2nd integer count should be 4 times of 1st one
- ASSERT_EQ(4, (int)(c2*1.0/c1 + 0.5));
+ const int repeats = 100000;
+ vector<double> probabilities;
+ int c1 = 0;
+ int c2 = 0;
+ double p1 = 0.8;
+ double p2 = 0.2;
+ probabilities.push_back(p1);
+ probabilities.push_back(p2);
+ WeightedRandomIntegerGenerator gen(probabilities);
+ for(int i = 0; i < repeats; ++i){
+ int n = gen();
+ if(n == 0) ++c1;
+ else if(n == 1) ++c2;
+ }
+ double mu1 = repeats * p1;
+ double mu2 = repeats * p2;
+ double sigma1 = sqrt(repeats * p1 * (1 - p1));
+ double sigma2 = sqrt(repeats * p2 * (1 - p2));
+ ASSERT_TRUE(fabs(c1 - mu1) < 4*sigma1);
+ ASSERT_TRUE(fabs(c2 - mu2) < 4*sigma2);
+
+ // Reset the probabilities
+ probabilities.clear();
+ c1 = c2 = 0;
+ p1 = 0.2;
+ p2 = 0.8;
+ probabilities.push_back(p1);
+ probabilities.push_back(p2);
+ gen.reset(probabilities);
+ for(int i = 0; i < repeats; ++i){
+ int n = gen();
+ if(n == 0) ++c1;
+ else if(n == 1) ++c2;
+ }
+ mu1 = repeats * p1;
+ mu2 = repeats * p2;
+ sigma1 = sqrt(repeats * p1 * (1 - p1));
+ sigma2 = sqrt(repeats * p2 * (1 - p2));
+ ASSERT_TRUE(fabs(c1 - mu1) < 4*sigma1);
+ ASSERT_TRUE(fabs(c2 - mu2) < 4*sigma2);
}
} // namespace nsas
Modified: branches/trac408/src/lib/nsas/tests/zone_entry_unittest.cc
==============================================================================
--- branches/trac408/src/lib/nsas/tests/zone_entry_unittest.cc (original)
+++ branches/trac408/src/lib/nsas/tests/zone_entry_unittest.cc Mon Dec 13 15:17:34 2010
@@ -18,6 +18,7 @@
#include <boost/shared_ptr.hpp>
#include <boost/foreach.hpp>
#include <boost/lexical_cast.hpp>
+#include <cmath>
#include <dns/rrclass.h>
#include <dns/rdataclass.h>
@@ -647,6 +648,7 @@
// Select one address from the address list
TEST_F(ZoneEntryTest, AddressSelection) {
+ const size_t repeats = 100000;
// Create the zone, give it 2 nameservers and total of 3 addresses
// (one of them is ipv6)
shared_ptr<ZoneEntry> zone(getZone());
@@ -672,13 +674,22 @@
callback_->successes_.clear();
// Test they have the same probabilities when they have the same RTT
- for (size_t i(0); i < 10000; ++ i) {
+ for (size_t i(0); i < repeats; ++ i) {
zone->addCallback(callback_, ANY_OK);
}
countHits(counts, callback_->successes_);
- // They should have about the same probability
- EXPECT_EQ(1, (int)(counts[0]*1.0/counts[1] + 0.5));
- EXPECT_EQ(1, (int)(counts[1]*1.0/counts[2] + 0.5));
+ // We repeat the simulation for N=repeats times
+ // for each address, the probability is p = 1/3, the average mu = N*p
+ // variance sigma^2 = N * p * (1-p) = N * 1/3 * 2/3 = N*2/9
+ // sigma = sqrt(N*2/9)
+ // we should make sure that mu - 4sigma < c < mu + 4sigma
+ // which means for 99.99366% of the time this should be true
+ double p = 1.0 / 3.0;
+ double mu = repeats * p;
+ double sigma = sqrt(repeats * p * (1 - p));
+ for (size_t i(0); i < 3; ++ i) {
+ ASSERT_TRUE(fabs(counts[i] - mu) < 4*sigma);
+ }
// reset the environment
callback_->successes_.clear();
@@ -688,14 +699,21 @@
ns1->setAddressRTT(IOAddress("192.0.2.1"), 1);
ns1->setAddressRTT(IOAddress("2001:db8::2"), 2);
ns2->setAddressRTT(IOAddress("192.0.2.3"), 3);
- for (size_t i(0); i < 10000; ++ i) {
+ for (size_t i(0); i < repeats; ++ i) {
zone->addCallback(callback_, ANY_OK);
}
countHits(counts, callback_->successes_);
- // First should be 2^2 more often then second
- EXPECT_EQ(4, (int)(counts[0]*1.0/counts[1] + 0.5));
- // And it should be 3^2 times more often than third
- EXPECT_EQ(9, (int)(counts[0]*1.0/counts[2] + 0.5));
+ // We expect that the selection probability for each address that
+ // it will be in the range of [mu-4Sigma, mu+4Sigma]
+ double ps[3];
+ ps[0] = 1.0/(1.0 + 1.0/4.0 + 1.0/9.0);
+ ps[1] = (1.0/4.0)/(1.0 + 1.0/4.0 + 1.0/9.0);
+ ps[2] = (1.0/9.0)/(1.0 + 1.0/4.0 + 1.0/9.0);
+ for (size_t i(0); i < 3; ++ i) {
+ double mu = repeats * ps[i];
+ double sigma = sqrt(repeats * ps[i] * (1 - ps[i]));
+ ASSERT_TRUE(fabs(counts[i] - mu < 4 * sigma));
+ }
// reset the environment
callback_->successes_.clear();
@@ -705,7 +723,7 @@
ns1->setAddressRTT(IOAddress("192.0.2.1"), 1);
ns1->setAddressRTT(IOAddress("2001:db8::2"), 100);
ns2->setAddressUnreachable(IOAddress("192.0.2.3"));
- for (size_t i(0); i < 10000; ++ i) {
+ for (size_t i(0); i < repeats; ++ i) {
zone->addCallback(callback_, ANY_OK);
}
countHits(counts, callback_->successes_);
@@ -720,13 +738,14 @@
ns1->setAddressUnreachable(IOAddress("192.0.2.1"));
ns1->setAddressUnreachable(IOAddress("2001:db8::2"));
ns2->setAddressUnreachable(IOAddress("192.0.2.3"));
- for (size_t i(0); i < 10000; ++ i) {
+ for (size_t i(0); i < repeats; ++ i) {
zone->addCallback(callback_, ANY_OK);
}
countHits(counts, callback_->successes_);
// They should have about the same probability
- EXPECT_EQ(1, (int)(counts[0]*1.0/counts[1] + 0.5));
- EXPECT_EQ(1, (int)(counts[1]*1.0/counts[2] + 0.5));
+ for (size_t i(0); i < 3; ++ i) {
+ ASSERT_TRUE(fabs(counts[i] - mu) < 4*sigma);
+ }
// TODO: The unreachable server should be changed to reachable after 5minutes, but how to test?
}
More information about the bind10-changes
mailing list