[svn] commit: r3806 - in /branches/trac408/src/lib/nsas: nameserver_entry.cc nameserver_entry.h random_number_generator.h tests/nameserver_entry_unittest.cc tests/zone_entry_unittest.cc zone_entry.cc zone_entry.h
BIND 10 source code commits
bind10-changes at lists.isc.org
Sat Dec 11 20:27:13 UTC 2010
Author: vorner
Date: Sat Dec 11 20:27:13 2010
New Revision: 3806
Log:
Address selection moved to ZoneEntry
NameserverEntry is too low. Who would choose the nameserver to ask?
Modified:
branches/trac408/src/lib/nsas/nameserver_entry.cc
branches/trac408/src/lib/nsas/nameserver_entry.h
branches/trac408/src/lib/nsas/random_number_generator.h
branches/trac408/src/lib/nsas/tests/nameserver_entry_unittest.cc
branches/trac408/src/lib/nsas/tests/zone_entry_unittest.cc
branches/trac408/src/lib/nsas/zone_entry.cc
branches/trac408/src/lib/nsas/zone_entry.h
Modified: branches/trac408/src/lib/nsas/nameserver_entry.cc
==============================================================================
--- branches/trac408/src/lib/nsas/nameserver_entry.cc (original)
+++ branches/trac408/src/lib/nsas/nameserver_entry.cc Sat Dec 11 20:27:13 2010
@@ -120,20 +120,6 @@
return getState();
}
-// Return one address matching the given family
-bool
-NameserverEntry::getAddress(NameserverAddress& address, AddressFamily family) {
- Lock lock(mutex_);
-
- if (addresses_[family].empty()) {
- return (false);
- } else {
- address = NameserverAddress(shared_from_this(),
- addresses_[family][address_selectors_[family]()], family);
- return (true);
- }
-}
-
// Return the address corresponding to the family
asiolink::IOAddress
NameserverEntry::getAddressAtIndex(size_t index, AddressFamily family) const {
@@ -155,8 +141,6 @@
BOOST_FOREACH(AddressEntry& entry, addresses_[family]) {
if (entry.getAddress().equal(address)) {
entry.setRTT(rtt);
- updateAddressSelector(addresses_[family],
- address_selectors_[family]);
return;
}
}
@@ -188,8 +172,6 @@
uint32_t new_rtt = (uint32_t)(old_rtt * UPDATE_RTT_ALPHA + rtt *
(1 - UPDATE_RTT_ALPHA));
addresses_[family][index].setRTT(new_rtt);
-
- updateAddressSelector(addresses_[family], address_selectors_[family]);
}
void
@@ -323,10 +305,6 @@
// TODO: We might want to use recursive lock and get rid of this
void dispatchCallbacks(Lock& lock)
{
- // There was a change (we wouldn't want to notify about it
- // otherwise), so we update it
- entry_->updateAddressSelector(entry_->addresses_[family_],
- entry_->address_selectors_[family_]);
// We dispatch ANY addresses if there is at last one address or
// there's no chance we'll get some in future
bool dispatch_any = entry_->has_address_[ANY_OK] ||
@@ -445,49 +423,5 @@
}
}
-// Update the address selector according to the RTTs
-//
-// Each address has a probability to be selected if multiple addresses are available
-// The weight factor is equal to 1/(rtt*rtt), then all the weight factors are normalized
-// to make the sum equal to 1.0
-void NameserverEntry::updateAddressSelector(
- std::vector<AddressEntry>& addresses,
- WeightedRandomIntegerGenerator& selector)
-{
- vector<double> probabilities;
- for(vector<AddressEntry>::iterator it = addresses.begin();
- it != addresses.end(); ++it){
- uint32_t rtt = (*it).getRTT();
- if(rtt == 0) {
- isc_throw(RTTIsZero, "The RTT is 0");
- }
-
- if(rtt == AddressEntry::UNREACHABLE) {
- probabilities.push_back(0);
- } else {
- probabilities.push_back(1.0/(rtt*rtt));
- }
- }
- // Calculate the sum
- double sum = accumulate(probabilities.begin(), probabilities.end(), 0.0);
-
- if(sum != 0) {
- // Normalize the probabilities to make the sum equal to 1.0
- for(vector<double>::iterator it = probabilities.begin();
- it != probabilities.end(); ++it){
- (*it) /= sum;
- }
- } else if(probabilities.size() > 0){
- // If all the nameservers are unreachable, the sum will be 0
- // So give each server equal opportunity to be selected.
- for(vector<double>::iterator it = probabilities.begin();
- it != probabilities.end(); ++it){
- (*it) = 1.0/probabilities.size();
- }
- }
-
- selector.reset(probabilities);
-}
-
} // namespace dns
} // namespace isc
Modified: branches/trac408/src/lib/nsas/nameserver_entry.h
==============================================================================
--- branches/trac408/src/lib/nsas/nameserver_entry.h (original)
+++ branches/trac408/src/lib/nsas/nameserver_entry.h Sat Dec 11 20:27:13 2010
@@ -34,7 +34,6 @@
#include "fetchable.h"
#include "resolver_interface.h"
#include "nsas_entry.h"
-#include "random_number_generator.h"
#include "nameserver_address.h"
namespace isc {
@@ -136,15 +135,6 @@
Fetchable::State getAddresses(AddressVector& addresses,
AddressFamily family = ANY_OK, bool expired_ok = false);
- /// \brief Return one address
- ///
- /// Return one address corresponding to this nameserver
- /// \param address NameserverAddress object used to receive the address
- /// \param family The family of user request, V4_ONLY or V6_ONLY
- /// \return true if one address is found, false otherwise
- /// \todo What use is this function?
- virtual bool getAddress(NameserverAddress& address, AddressFamily family);
-
/// \brief Return Address that corresponding to the index
///
/// \param index The address index in the address vector
@@ -281,21 +271,6 @@
/// Call unlocked.
void askIP(boost::shared_ptr<ResolverInterface> resolver,
const isc::dns::RRType&, AddressFamily);
- /// \brief Update the address selector according to the RTTs of addresses
- ///
- /// \param addresses The address list
- /// \param selector Weighted random generator
- void updateAddressSelector(std::vector<AddressEntry>& addresses,
- WeightedRandomIntegerGenerator& selector);
-
- /**
- * \short Generate one integer according to different probability.
- *
- * \todo Should this be more global? And it definitely should be
- * inside ZoneEntry, the selection should be done from all
- * that addresses.
- */
- WeightedRandomIntegerGenerator address_selectors_[ANY_OK];
};
} // namespace dns
Modified: branches/trac408/src/lib/nsas/random_number_generator.h
==============================================================================
--- branches/trac408/src/lib/nsas/random_number_generator.h (original)
+++ branches/trac408/src/lib/nsas/random_number_generator.h Sat Dec 11 20:27:13 2010
@@ -110,9 +110,6 @@
// Reset the minimum integer
min_ = min;
-
- // Reset the random number generator
- rng_.seed(time(NULL));
}
/// \brief Generate weighted random integer
Modified: branches/trac408/src/lib/nsas/tests/nameserver_entry_unittest.cc
==============================================================================
--- branches/trac408/src/lib/nsas/tests/nameserver_entry_unittest.cc (original)
+++ branches/trac408/src/lib/nsas/tests/nameserver_entry_unittest.cc Sat Dec 11 20:27:13 2010
@@ -480,85 +480,6 @@
}
}
-// Select one address from the address list
-TEST_F(NameserverEntryTest, AddressSelection) {
- boost::shared_ptr<NameserverEntry> ns(new NameserverEntry(EXAMPLE_CO_UK,
- RRClass::IN()));
- fillNSEntry(ns, rrv4_, rrv6_);
- NameserverEntry::AddressVector v4Addresses;
- NameserverEntry::AddressVector v6Addresses;
- ns->getAddresses(v4Addresses, V4_ONLY);
- ns->getAddresses(v6Addresses, V6_ONLY);
-
- int c1 = 0;
- int c2 = 0;
- int c3 = 0;
- NameserverAddress ns_address;
- for(int i = 0; i < 10000; ++i){
- ns->getAddress(ns_address, V4_ONLY);
- 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
- EXPECT_EQ(1, (int)(c1*1.0/c2 + 0.5));
- EXPECT_EQ(1, (int)(c2*1.0/c3 + 0.5));
-
- // 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){
- ns->getAddress(ns_address, V4_ONLY);
- 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 should be (2*2) times of c2
- EXPECT_EQ(4, (int)(c1*1.0/c2 + 0.5));
- // c1 should be (3*3) times of c3
- EXPECT_EQ(9, (int)(c1*1.0/c3 + 0.5));
-
- // 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){
- ns->getAddress(ns_address, V4_ONLY);
- 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;
- }
-
- // The 3rd address should not be selected again
- EXPECT_EQ(0, c3);
-
- // Test if all the servers are unrachable
- ns->setAddressUnreachable(v4Addresses[0].getAddress());
- ns->setAddressUnreachable(v4Addresses[1].getAddress());
- ns->setAddressUnreachable(v4Addresses[2].getAddress());
- c1 = c2 = c3 = 0;
- for(int i = 0; i < 100000; ++i){
- ns.get()->getAddress(ns_address, V4_ONLY);
- 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;
- }
-
- // All the unreachable servers should be selected with equal opportunity
- EXPECT_EQ(1, (int)(c1*1.0/c2 + 0.5));
- EXPECT_EQ(1, (int)(c1*1.0/c3 + 0.5));
-
- // TODO: The unreachable server should be changed to reachable after 5minutes, but how to test?
-}
-
// Test the RTT is updated smoothly
TEST_F(NameserverEntryTest, UpdateRTT) {
shared_ptr<NameserverEntry> ns(new NameserverEntry(EXAMPLE_CO_UK,
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 Sat Dec 11 20:27:13 2010
@@ -16,6 +16,8 @@
#include <gtest/gtest.h>
#include <boost/shared_ptr.hpp>
+#include <boost/foreach.hpp>
+#include <boost/lexical_cast.hpp>
#include <dns/rrclass.h>
#include <dns/rdataclass.h>
@@ -631,4 +633,102 @@
//@}
+// Count hits of each address
+void
+countHits(size_t *counts, const vector<NameserverAddress>& successes) {
+ BOOST_FOREACH(const NameserverAddress& address, successes) {
+ // We use the last digit as an index
+ string address_string(address.getAddress().toText());
+ size_t index(address_string[address_string.size() - 1] - '0' - 1);
+ ASSERT_LT(index, 3);
+ counts[index] ++;
+ }
+}
+
+// Select one address from the address list
+TEST_F(ZoneEntryTest, AddressSelection) {
+ // Create the zone, give it 2 nameservers and total of 3 addresses
+ // (one of them is ipv6)
+ shared_ptr<ZoneEntry> zone(getZone());
+ zone->addCallback(callback_, ANY_OK);
+ EXPECT_NO_THROW(resolver_->provideNS(0, rrns_));
+ ASSERT_GT(resolver_->requests.size(), 1);
+ Name name1(resolver_->requests[1].first->getName());
+ EXPECT_TRUE(resolver_->asksIPs(name1, 1, 2));
+ resolver_->answer(1, name1, RRType::A(), rdata::in::A("192.0.2.1"));
+ resolver_->answer(2, name1, RRType::AAAA(),
+ rdata::in::AAAA("2001:db8::2"));
+ ASSERT_GT(resolver_->requests.size(), 3);
+ Name name2(resolver_->requests[3].first->getName());
+ EXPECT_TRUE(resolver_->asksIPs(name2, 3, 4));
+ resolver_->answer(3, name2, RRType::A(), rdata::in::A("192.0.2.3"));
+ resolver_->requests[4].second->failure();
+
+ shared_ptr<NameserverEntry> ns1(nameserver_table_->get(HashKey(
+ name1.toText(), RRClass::IN()))),
+ ns2(nameserver_table_->get(HashKey(name2.toText(), RRClass::IN())));
+
+ size_t counts[3] = {0, 0, 0};
+ callback_->successes_.clear();
+
+ // Test they have the same probabilities when they have the same RTT
+ for (size_t i(0); i < 10000; ++ 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));
+
+ // reset the environment
+ callback_->successes_.clear();
+ counts[0] = counts[1] = counts[2] = 0;
+
+ // Test when the RTT is not the same
+ 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) {
+ 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));
+
+ // reset the environment
+ callback_->successes_.clear();
+ counts[0] = counts[1] = counts[2] = 0;
+
+ // Test with unreachable address
+ 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) {
+ zone->addCallback(callback_, ANY_OK);
+ }
+ countHits(counts, callback_->successes_);
+ // The unreachable one shouldn't be called
+ EXPECT_EQ(0, counts[2]);
+
+ // reset the environment
+ callback_->successes_.clear();
+ counts[0] = counts[1] = counts[2] = 0;
+
+ // Test with all unreachable
+ 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) {
+ 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));
+
+ // TODO: The unreachable server should be changed to reachable after 5minutes, but how to test?
+}
+
} // namespace
Modified: branches/trac408/src/lib/nsas/zone_entry.cc
==============================================================================
--- branches/trac408/src/lib/nsas/zone_entry.cc (original)
+++ branches/trac408/src/lib/nsas/zone_entry.cc Sat Dec 11 20:27:13 2010
@@ -255,29 +255,47 @@
from.clear();
}
-// TODO: This 3 functions should not be needed. We should do
-// propper choosing. There's code for it already.
-mutex randMutex;
-
-size_t
-randIndex(size_t count) {
- // We need to lock the global generator
- // TODO If there's contention locking, we might want a generator
- // for each thread?
- mutex::scoped_lock lock(randMutex);
- // This seems to be enough to use pseudo-random generator and according
- // to boost docs, this one is fast.
- static rand48 generator;
- return variate_generator<rand48&, uniform_int<size_t> >(generator,
- uniform_int<size_t>(0, count - 1))();
-}
-
-const NameserverAddress&
-chooseAddress(const NameserverEntry::AddressVector& addresses) {
- // TODO Something little bit more inteligent than just picking random
- // one
- assert(!addresses.empty()); // Should not be called with empty list
- return (addresses[randIndex(addresses.size())]);
+// Update the address selector according to the RTTs
+//
+// Each address has a probability to be selected if multiple addresses are available
+// The weight factor is equal to 1/(rtt*rtt), then all the weight factors are normalized
+// to make the sum equal to 1.0
+void
+updateAddressSelector(std::vector<NameserverAddress>& addresses,
+ WeightedRandomIntegerGenerator& selector)
+{
+ vector<double> probabilities;
+ BOOST_FOREACH(NameserverAddress& address, addresses) {
+ uint32_t rtt = address.getAddressEntry().getRTT();
+ if(rtt == 0) {
+ isc_throw(RTTIsZero, "The RTT is 0");
+ }
+
+ if(rtt == AddressEntry::UNREACHABLE) {
+ probabilities.push_back(0);
+ } else {
+ probabilities.push_back(1.0/(rtt*rtt));
+ }
+ }
+ // Calculate the sum
+ double sum = accumulate(probabilities.begin(), probabilities.end(), 0.0);
+
+ if(sum != 0) {
+ // Normalize the probabilities to make the sum equal to 1.0
+ for(vector<double>::iterator it = probabilities.begin();
+ it != probabilities.end(); ++it){
+ (*it) /= sum;
+ }
+ } else if(probabilities.size() > 0){
+ // If all the nameservers are unreachable, the sum will be 0
+ // So give each server equal opportunity to be selected.
+ for(vector<double>::iterator it = probabilities.begin();
+ it != probabilities.end(); ++it){
+ (*it) = 1.0/probabilities.size();
+ }
+ }
+
+ selector.reset(probabilities);
}
}
@@ -467,6 +485,11 @@
return;
// We have some addresses to answer
} else if (!addresses.empty()) {
+ // Prepare the selector of addresses
+ // TODO: Think of a way how to keep it for a while
+ // (not update every time)
+ updateAddressSelector(addresses, address_selector);
+
// Extract the callbacks
vector<CallbackPtr> to_execute;
// FIXME: Think of a solution where we do not lose
@@ -475,7 +498,7 @@
// Run the callbacks
BOOST_FOREACH(const CallbackPtr& callback, to_execute) {
- callback->success(chooseAddress(addresses));
+ callback->success(addresses[address_selector()]);
}
return;
} else if (!pending) {
Modified: branches/trac408/src/lib/nsas/zone_entry.h
==============================================================================
--- branches/trac408/src/lib/nsas/zone_entry.h (original)
+++ branches/trac408/src/lib/nsas/zone_entry.h Sat Dec 11 20:27:13 2010
@@ -32,6 +32,7 @@
#include "fetchable.h"
#include "resolver_interface.h"
#include "nsas_types.h"
+#include "random_number_generator.h"
namespace isc {
namespace nsas {
@@ -163,6 +164,9 @@
// Put a callback into the nameserver entry. Same ADDR_REQ_MAX means for
// all families
void insertCallback(NameserverPtr nameserver, AddressFamily family);
+ // A random generator for this zone entry
+ // TODO: A more global one? Per thread one?
+ WeightedRandomIntegerGenerator address_selector;
};
} // namespace nsas
More information about the bind10-changes
mailing list