[svn] commit: r3809 - in /branches/trac356/src/lib/nsas/tests: nameserver_entry_unittest.cc random_number_generator_unittest.cc
BIND 10 source code commits
bind10-changes at lists.isc.org
Mon Dec 13 08:13:20 UTC 2010
Author: ocean
Date: Mon Dec 13 08:13:19 2010
New Revision: 3809
Log:
Correct errors in random numbers generator unit tests
Modified:
branches/trac356/src/lib/nsas/tests/nameserver_entry_unittest.cc
branches/trac356/src/lib/nsas/tests/random_number_generator_unittest.cc
Modified: branches/trac356/src/lib/nsas/tests/nameserver_entry_unittest.cc
==============================================================================
--- branches/trac356/src/lib/nsas/tests/nameserver_entry_unittest.cc (original)
+++ branches/trac356/src/lib/nsas/tests/nameserver_entry_unittest.cc Mon Dec 13 08:13:19 2010
@@ -16,6 +16,7 @@
#include <iostream>
#include <algorithm>
+#include <cmath>
#include <limits.h>
#include <boost/foreach.hpp>
@@ -425,6 +426,7 @@
// Select one address from the address list
TEST_F(NameserverEntryTest, AddressSelection) {
+ const int repeats = 100000;
boost::shared_ptr<NameserverEntry> ns(new NameserverEntry(&rrv4_, &rrv6_));
NameserverEntry::AddressVector v4Addresses;
@@ -436,23 +438,32 @@
int c2 = 0;
int c3 = 0;
NameserverAddress ns_address;
- for(int i = 0; i < 10000; ++i){
+ for(int i = 0; i < repeats; ++i){
ns.get()->getAddress(ns_address, AF_INET);
asiolink::IOAddress io_address = ns_address.getAddress();
if(io_address.toText() == v4Addresses[0].getAddress().toText()) ++c1;
else if(io_address.toText() == v4Addresses[1].getAddress().toText()) ++c2;
else if(io_address.toText() == v4Addresses[2].getAddress().toText()) ++c3;
}
- // c1, c2 and c3 should almost be equal
- ASSERT_EQ(1, (int)(c1*1.0/c2 + 0.5));
- ASSERT_EQ(1, (int)(c2*1.0/c3 + 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));
+ ASSERT_TRUE(fabs(c1 - mu) < 4*sigma);
+ ASSERT_TRUE(fabs(c2 - mu) < 4*sigma);
+ ASSERT_TRUE(fabs(c3 - mu) < 4*sigma);
// update the rtt to 1, 2, 3
ns->setAddressRTT(v4Addresses[0].getAddress(), 1);
ns->setAddressRTT(v4Addresses[1].getAddress(), 2);
ns->setAddressRTT(v4Addresses[2].getAddress(), 3);
c1 = c2 = c3 = 0;
- for(int i = 0; i < 100000; ++i){
+ for(int i = 0; i < repeats; ++i){
ns.get()->getAddress(ns_address, AF_INET);
asiolink::IOAddress io_address = ns_address.getAddress();
if(io_address.toText() == v4Addresses[0].getAddress().toText()) ++c1;
@@ -460,17 +471,27 @@
else if(io_address.toText() == v4Addresses[2].getAddress().toText()) ++c3;
}
- // c1 should be (2*2) times of c2
- ASSERT_EQ(4, (int)(c1*1.0/c2 + 0.5));
- // c1 should be (3*3) times of c3
- ASSERT_EQ(9, (int)(c1*1.0/c3 + 0.5));
+ // We expect that the selection probability for each address that
+ // it will be in the range of [mu-4Sigma, mu+4Sigma]
+ double p1 = 1.0/(1.0 + 1.0/4.0 + 1.0/9.0);
+ double p2 = (1.0/4.0)/(1.0 + 1.0/4.0 + 1.0/9.0);
+ double p3 = (1.0/9.0)/(1.0 + 1.0/4.0 + 1.0/9.0);
+ double mu1 = repeats * 0.7347;
+ double mu2 = repeats * 0.18367;
+ double mu3 = repeats * 0.08163;
+ 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 unreachable address
ns->setAddressRTT(v4Addresses[0].getAddress(), 1);
ns->setAddressRTT(v4Addresses[1].getAddress(), 100);
ns->setAddressUnreachable(v4Addresses[2].getAddress());
c1 = c2 = c3 = 0;
- for(int i = 0; i < 100000; ++i){
+ for(int i = 0; i < repeats; ++i){
ns.get()->getAddress(ns_address, AF_INET);
asiolink::IOAddress io_address = ns_address.getAddress();
if(io_address.toText() == v4Addresses[0].getAddress().toText()) ++c1;
@@ -486,7 +507,7 @@
ns->setAddressUnreachable(v4Addresses[1].getAddress());
ns->setAddressUnreachable(v4Addresses[2].getAddress());
c1 = c2 = c3 = 0;
- for(int i = 0; i < 100000; ++i){
+ for(int i = 0; i < repeats; ++i){
ns.get()->getAddress(ns_address, AF_INET);
asiolink::IOAddress io_address = ns_address.getAddress();
if(io_address.toText() == v4Addresses[0].getAddress().toText()) ++c1;
@@ -497,6 +518,12 @@
// All the unreachable servers should be selected with equal opportunity
ASSERT_EQ(1, (int)(c1*1.0/c2 + 0.5));
ASSERT_EQ(1, (int)(c1*1.0/c3 + 0.5));
+ p = 1.0 / 3.0;
+ mu = repeats * p;
+ sigma = sqrt(repeats * p * (1 - p));
+ ASSERT_TRUE(fabs(c1 - mu) < 4*sigma);
+ ASSERT_TRUE(fabs(c2 - mu) < 4*sigma);
+ ASSERT_TRUE(fabs(c3 - mu) < 4*sigma);
// TODO: The unreachable server should be changed to reachable after 5minutes, but how to test?
}
Modified: branches/trac356/src/lib/nsas/tests/random_number_generator_unittest.cc
==============================================================================
--- branches/trac356/src/lib/nsas/tests/random_number_generator_unittest.cc (original)
+++ branches/trac356/src/lib/nsas/tests/random_number_generator_unittest.cc Mon Dec 13 08:13:19 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
More information about the bind10-changes
mailing list