[#969] Random allocator

8 files changed, 596 insertions, 4 deletions

diff --git a/src/lib/dhcpsrv/Makefile.am b/src/lib/dhcpsrv/Makefile.am
index 6a952c8b6f..57dbd0cca4 100644
--- a/src/lib/dhcpsrv/Makefile.am
+++ b/src/lib/dhcpsrv/Makefile.am
@@ -144,6 +144,7 @@ endif
 
 libkea_dhcpsrv_la_SOURCES += pool.cc pool.h
 libkea_dhcpsrv_la_SOURCES += random_allocation_state.cc random_allocation_state.h
+libkea_dhcpsrv_la_SOURCES += random_allocator.cc random_allocator.h
 libkea_dhcpsrv_la_SOURCES += resource_handler.cc resource_handler.h
 libkea_dhcpsrv_la_SOURCES += sanity_checker.cc sanity_checker.h
 libkea_dhcpsrv_la_SOURCES += shared_network.cc shared_network.h
diff --git a/src/lib/dhcpsrv/ip_range.cc b/src/lib/dhcpsrv/ip_range.cc
index 1ca617948d..271d553089 100644
--- a/src/lib/dhcpsrv/ip_range.cc
+++ b/src/lib/dhcpsrv/ip_range.cc
@@ -1,4 +1,4 @@
-// Copyright (C) 2020 Internet Systems Consortium, Inc. ("ISC")
+// Copyright (C) 2020-2022 Internet Systems Consortium, Inc. ("ISC")
 //
 // This Source Code Form is subject to the terms of the Mozilla Public
 // License, v. 2.0. If a copy of the MPL was not distributed with this
@@ -52,7 +52,8 @@ PrefixRange::PrefixRange(const asiolink::IOAddress& prefix, const uint8_t length
 
 PrefixRange::PrefixRange(const asiolink::IOAddress& start, const asiolink::IOAddress& end,
                          const uint8_t delegated)
-    : start_(start), end_(end), prefix_length_(0), delegated_length_(delegated) {
+    : start_(start), end_(end), prefix_length_(prefixLengthFromRange(start, end)),
+      delegated_length_(delegated) {
     if (!start_.isV6() || !end_.isV6()) {
         isc_throw(BadValue, "IPv6 prefix required for prefix delegation range but "
                   << start_ << ":" << end_ << " was specified");
diff --git a/src/lib/dhcpsrv/ip_range_permutation.cc b/src/lib/dhcpsrv/ip_range_permutation.cc
index ad622d6abd..54f7acc508 100644
--- a/src/lib/dhcpsrv/ip_range_permutation.cc
+++ b/src/lib/dhcpsrv/ip_range_permutation.cc
@@ -50,7 +50,7 @@ IPRangePermutation::next(bool& done) {
     // addresses between the cursor and the end of the range have been already
     // returned by this function. Therefore we focus on the remaining cursor-1
     // addresses. Let's get random address from this sub-range.
-    std::uniform_int_distribution<int> dist(0, cursor_ - 1);
+    std::uniform_int_distribution<uint64_t> dist(0, cursor_ - 1);
     auto next_loc = dist(generator_);
 
     IOAddress next_loc_address = IOAddress::IPV4_ZERO_ADDRESS();
diff --git a/src/lib/dhcpsrv/random_allocator.cc b/src/lib/dhcpsrv/random_allocator.cc
new file mode 100644
index 0000000000..049ba97c5a
--- /dev/null
+++ b/src/lib/dhcpsrv/random_allocator.cc
@@ -0,0 +1,105 @@
+// Copyright (C) 2022 Internet Systems Consortium, Inc. ("ISC")
+//
+// This Source Code Form is subject to the terms of the Mozilla Public
+// License, v. 2.0. If a copy of the MPL was not distributed with this
+// file, You can obtain one at http://mozilla.org/MPL/2.0/.
+
+#include <config.h>
+
+#include <dhcpsrv/random_allocator.h>
+#include <dhcpsrv/subnet.h>
+#include <algorithm>
+#include <random>
+
+using namespace isc::asiolink;
+using namespace std;
+
+namespace isc {
+namespace dhcp {
+
+RandomAllocator::RandomAllocator(Lease::Type type, const WeakSubnetPtr& subnet)
+    : Allocator(type, subnet), generator_() {
+    random_device rd;
+    generator_.seed(rd());
+}
+
+IOAddress
+RandomAllocator::pickAddressInternal(const ClientClasses& client_classes,
+                                     const DuidPtr&,
+                                     const IOAddress&) {
+    auto subnet = subnet_.lock();
+    auto pools = subnet->getPools(pool_type_);
+
+    // Let's first iterate over the pools and identify the ones that
+    // meet client class criteria. Then, segragate these pools into
+    // the ones that still have available addresses and exhausted
+    // ones.
+    std::vector<uint64_t> available;
+    std::vector<uint64_t> exhausted;
+    for (auto i = 0; i < pools.size(); ++i) {
+        // Check if the pool is allowed for the client's classes.
+        if (pools[i]->clientSupported(client_classes)) {
+            // Get or create the pool state.
+            auto state = getPoolState(pools[i]);
+            if (state->getPermutation()->exhausted()) {
+                // Pool is exhausted. It means that all addresses from
+                // this pool have been offered. It doesn't mean that
+                // leases are allocated for all these addresses. It
+                // only means that all have been picked from the pool.
+                exhausted.push_back(i);
+            } else {
+                // There are still available addresses in this pool. It
+                // means that not all of them have been offered.
+                available.push_back(i);
+            }
+        }
+    }
+    // Find a suitable pool.
+    PoolPtr pool;
+    if (!available.empty()) {
+        // There are pools with available addresses. Let's randomly
+        // pick one of these pools and get next available address.
+        pool = pools[available[getRandomNumber(available.size()-1)]];
+
+    } else if (!exhausted.empty()) {
+        // All pools have been exhausted. We will start offering the same
+        // addresses from these pools. We need to reset the permutations
+        // of the exhausted pools.
+        for (auto e : exhausted) {
+            getPoolState(pools[e])->getPermutation()->reset();
+        }
+        // Get random pool from those we just reset.
+        pool = pools[exhausted[getRandomNumber(exhausted.size()-1)]];
+    }
+
+    // If pool has been found, let's get next address.
+    if (pool) {
+        auto done = false;
+        return (getPoolState(pool)->getPermutation()->next(done));
+    }
+
+    // No pool available. There are no pools or client classes do
+    // not match.
+    return (IOAddress::IPV4_ZERO_ADDRESS());
+}
+
+PoolRandomAllocationStatePtr
+RandomAllocator::getPoolState(const PoolPtr& pool) const {
+    if (!pool->getAllocationState()) {
+        pool->setAllocationState(PoolRandomAllocationState::create(pool));
+    }
+    return (boost::dynamic_pointer_cast<PoolRandomAllocationState>(pool->getAllocationState()));
+}
+
+uint64_t
+RandomAllocator::getRandomNumber(uint64_t limit) {
+    // Take the short path if there is only one number to randomize from.
+    if (limit == 0) {
+        return 0;
+    }
+    std::uniform_int_distribution<uint64_t> dist(0, limit);
+    return (dist(generator_));
+}
+
+} // end of namespace isc::dhcp
+} // end of namespace isc
diff --git a/src/lib/dhcpsrv/random_allocator.h b/src/lib/dhcpsrv/random_allocator.h
new file mode 100644
index 0000000000..37cf253a00
--- /dev/null
+++ b/src/lib/dhcpsrv/random_allocator.h
@@ -0,0 +1,79 @@
+// Copyright (C) 2022 Internet Systems Consortium, Inc. ("ISC")
+//
+// This Source Code Form is subject to the terms of the Mozilla Public
+// License, v. 2.0. If a copy of the MPL was not distributed with this
+// file, You can obtain one at http://mozilla.org/MPL/2.0/.
+
+#ifndef RANDOM_ALLOCATOR_H
+#define RANDOM_ALLOCATOR_H
+
+#include <dhcpsrv/allocator.h>
+#include <dhcpsrv/random_allocation_state.h>
+#include <dhcpsrv/lease.h>
+#include <cstdint>
+#include <random>
+
+namespace isc {
+namespace dhcp {
+
+/// @brief An allocator offering addresses in a random order.
+///
+/// This allocator uses @c IPRangePermutation to select random
+/// addresses or delegated prefixes from the pools. It guarantees
+/// that all offered addresses are unique (do not repeat).
+///
+/// The allocator also randomly picks pools to ensure that the
+/// leases are offered uniformly from the entire subnet rather than
+/// from the same pool until it exhausts. When all pools exhaust,
+/// the allocator resets their permutations and begins offering
+/// leases from these pools again.
+class RandomAllocator : public Allocator {
+public:
+
+    /// @brief Constructor.
+    ///
+    /// @param type specifies the type of allocated leases.
+    /// @param subnet weak pointer to the subnet owning the allocator.
+    RandomAllocator(Lease::Type type, const WeakSubnetPtr& subnet);
+
+private:
+
+    /// @brief Returns a random address from the pools in the subnet.
+    ///
+    /// Internal thread-unsafe implementation of the @c pickAddress.
+    ///
+    /// @param client_classes list of classes client belongs to.
+    /// @param duid client DUID (ignored).
+    /// @param hint client hint (ignored).
+    ///
+    /// @return next offered address.
+    virtual asiolink::IOAddress pickAddressInternal(const ClientClasses& client_classes,
+                                                    const DuidPtr& duid,
+                                                    const asiolink::IOAddress& hint);
+
+    /// @brief Convenience function returning pool allocation state instance.
+    ///
+    /// It creates a new pool state instance and assigns it to the pool
+    /// if it hasn't been initialized.
+    ///
+    /// @param pool pool instance.
+    /// @return allocation state instance for the pool.
+    PoolRandomAllocationStatePtr getPoolState(const PoolPtr& pool) const;
+
+    /// @brief Convenience function returning a random number.
+    ///
+    /// It is used internally by the @c pickAddressInternal function to
+    /// select a random pool.
+    ///
+    /// @param limit upper bound of the range.
+    /// @returns random number between 0 and limit.
+    uint64_t getRandomNumber(uint64_t limit);
+
+    /// @brief Random generator used by this class.
+    std::mt19937 generator_;
+};
+
+} // end of namespace isc::dhcp
+} // end of namespace isc
+
+#endif // RANDOM_ALLOCATOR_H
diff --git a/src/lib/dhcpsrv/tests/Makefile.am b/src/lib/dhcpsrv/tests/Makefile.am
index 8ef2476920..ea2d29b5f9 100644
--- a/src/lib/dhcpsrv/tests/Makefile.am
+++ b/src/lib/dhcpsrv/tests/Makefile.am
@@ -123,6 +123,7 @@ libdhcpsrv_unittests_SOURCES += pgsql_host_data_source_unittest.cc
 endif
 libdhcpsrv_unittests_SOURCES += pool_unittest.cc
 libdhcpsrv_unittests_SOURCES += random_allocation_state_unittest.cc
+libdhcpsrv_unittests_SOURCES += random_allocator_unittest.cc
 libdhcpsrv_unittests_SOURCES += resource_handler_unittest.cc
 libdhcpsrv_unittests_SOURCES += sanity_checks_unittest.cc
 libdhcpsrv_unittests_SOURCES += shared_network_parser_unittest.cc
diff --git a/src/lib/dhcpsrv/tests/ip_range_permutation_unittest.cc b/src/lib/dhcpsrv/tests/ip_range_permutation_unittest.cc
index 339f53e3a6..bae361aa21 100644
--- a/src/lib/dhcpsrv/tests/ip_range_permutation_unittest.cc
+++ b/src/lib/dhcpsrv/tests/ip_range_permutation_unittest.cc
@@ -1,4 +1,4 @@
-// Copyright (C) 2020 Internet Systems Consortium, Inc. ("ISC")
+// Copyright (C) 2020-2022 Internet Systems Consortium, Inc. ("ISC")
 //
 // This Source Code Form is subject to the terms of the Mozilla Public
 // License, v. 2.0. If a copy of the MPL was not distributed with this
@@ -137,6 +137,41 @@ TEST(IPRangePermutationTest, pd) {
     EXPECT_TRUE(addrs.begin()->isV6Zero());
 }
 
+// This test verifies that a permutation of delegated prefixes is
+// generated from the prefix range specified using first and last
+// address.
+TEST(IPRangePermutationTest, pdStartEnd) {
+    PrefixRange range(IOAddress("3000::"), IOAddress("3000::ffff"), 120);
+    IPRangePermutation perm(range);
+
+    std::set<IOAddress> addrs;
+    bool done = false;
+    for (auto i = 0; i < 257; ++i) {
+        auto next = perm.next(done);
+        if (!next.isV6Zero()) {
+            // Make sure the prefix is within the range.
+            EXPECT_LE(range.start_, next);
+            EXPECT_LE(next, range.end_);
+        }
+        // If we went over all delegated prefixes in the range, the flags indicating
+        // that the permutation is exhausted should be set to true.
+        if (i >= 255) {
+            EXPECT_TRUE(done);
+            EXPECT_TRUE(perm.exhausted());
+        } else {
+            // We're not done yet, so these flag should still be false.
+            EXPECT_FALSE(done);
+            EXPECT_FALSE(perm.exhausted());
+        }
+        // Insert the prefix returned to the set.
+        addrs.insert(next);
+    }
+
+    // We should have recorded 257 unique addresses, including the zero address.
+    EXPECT_EQ(257, addrs.size());
+    EXPECT_TRUE(addrs.begin()->isV6Zero());
+}
+
 // This test verifies that it is possible to reset the permutation state.
 TEST(IPRangePermutationTest, reset) {
     // Create address range with 11 addresses.
diff --git a/src/lib/dhcpsrv/tests/random_allocator_unittest.cc b/src/lib/dhcpsrv/tests/random_allocator_unittest.cc
new file mode 100644
index 0000000000..79dbfa5d6f
--- /dev/null
+++ b/src/lib/dhcpsrv/tests/random_allocator_unittest.cc
@@ -0,0 +1,370 @@
+// Copyright (C) 2022 Internet Systems Consortium, Inc. ("ISC")
+//
+// This Source Code Form is subject to the terms of the Mozilla Public
+// License, v. 2.0. If a copy of the MPL was not distributed with this
+// file, You can obtain one at http://mozilla.org/MPL/2.0/.
+
+#include <config.h>
+#include <asiolink/io_address.h>
+#include <dhcpsrv/random_allocator.h>
+#include <dhcpsrv/tests/alloc_engine_utils.h>
+#include <boost/make_shared.hpp>
+#include <gtest/gtest.h>
+#include <set>
+#include <vector>
+#include <sstream>
+
+using namespace isc::asiolink;
+using namespace std;
+
+namespace isc {
+namespace dhcp {
+namespace test {
+
+using RandomAllocatorTest4 = AllocEngine4Test;
+
+// Test allocating IPv4 addresses when a subnet has a single pool.
+TEST_F(RandomAllocatorTest4, singlePool) {
+    RandomAllocator alloc(Lease::TYPE_V4, subnet_);
+
+    // Remember returned addresses, so we can verify that unique addresses
+    // are returned.
+    std::set<IOAddress> addresses;
+    for (auto i = 0; i < 1000; ++i) {
+        IOAddress candidate = alloc.pickAddress(cc_, clientid_, IOAddress("0.0.0.0"));
+        addresses.insert(candidate);
+        EXPECT_TRUE(subnet_->inPool(Lease::TYPE_V4, candidate));
+        EXPECT_TRUE(subnet_->inPool(Lease::TYPE_V4, candidate, cc_));
+    }
+    // The pool comprises 10 addresses. All should be returned.
+    EXPECT_EQ(10, addresses.size());
+}
+
+// Test allocating IPv4 addresses from multiple pools.
+TEST_F(RandomAllocatorTest4, manyPools) {
+    RandomAllocator alloc(Lease::TYPE_V4, subnet_);
+
+    // Add several more pools.
+    for (int i = 2; i < 10; ++i) {
+        stringstream min, max;
+        min << "192.0.2." << i * 10 + 1;
+        max << "192.0.2." << i * 10 + 9;
+        auto pool = boost::make_shared<Pool4>(IOAddress(min.str()),
+                                              IOAddress(max.str()));
+        subnet_->addPool(pool);
+    }
+
+    // First pool (.100 - .109) has 10 addresses.
+    // There are 8 extra pools with 9 addresses in each.
+    int total = 10 + 8 * 9;
+
+    // Repeat allocation of all addresses several times. Make sure that
+    // the same addresses are returned when all pools are exhausted.
+    for (auto j = 0; j < 6; ++j) {
+        std::set<IOAddress> addresses_set;
+        std::vector<IOAddress> addresses_vector;
+        std::vector<PoolPtr> pools_vector;
+
+        // Pick random addresses the number of times equal to the
+        // subnet capacity to ensure that all addresses are returned.
+        for (auto i = 0; i < total; ++i) {
+            IOAddress candidate = alloc.pickAddress(cc_, clientid_, IOAddress("0.0.0.0"));
+            addresses_set.insert(candidate);
+            addresses_vector.push_back(candidate);
+            EXPECT_TRUE(subnet_->inPool(Lease::TYPE_V4, candidate));
+            EXPECT_TRUE(subnet_->inPool(Lease::TYPE_V4, candidate, cc_));
+            pools_vector.push_back(subnet_->getPool(Lease::TYPE_V4, candidate));
+        }
+        // Make sure that unique addresses have been returned.
+        EXPECT_EQ(total, addresses_set.size());
+
+        // Verify that the addresses are returned in the random order.
+        // Count how many times we found consecutive addresses. It should
+        // be 0 or close to 0.
+        int consecutives = 0;
+        for (auto k = 0; k < addresses_vector.size()-1; ++k) {
+            if (addresses_vector[k].toUint32() == addresses_vector[k+1].toUint32()-1) {
+                ++consecutives;
+            }
+        }
+        // Ideally, the number of consecutive occurences should be 0 but we
+        // allow some to make sure the test doesn't fall over sporadically.
+        EXPECT_LT(consecutives, addresses_vector.size()/4);
+
+        // Repeat similar check for pools. The pools should be picked in the
+        // random order too.
+        int pool_matches = 0;
+        for (auto k = 0; k < pools_vector.size()-1; ++k) {
+            if (pools_vector[k] == subnet_->getPools(Lease::TYPE_V4)[k]) {
+                ++pool_matches;
+            }
+        }
+        EXPECT_LT(pool_matches, pools_vector.size()/2);
+    }
+}
+
+// Test that the allocator returns a zero address when there are no
+// pools.
+TEST_F(RandomAllocatorTest4, noPools) {
+   RandomAllocator alloc(Lease::TYPE_V4, subnet_);
+
+   subnet_->delPools(Lease::TYPE_V4);
+
+   IOAddress candidate = alloc.pickAddress(cc_, clientid_, IOAddress("0.0.0.0"));
+   EXPECT_TRUE(candidate.isV4Zero());
+}
+
+// Test that the allocator respects client classes while it picks
+// pools and addresses.
+TEST_F(RandomAllocatorTest4, clientClasses) {
+   RandomAllocator alloc(Lease::TYPE_V4, subnet_);
+
+   // First pool only allows the client class foo.
+   pool_->allowClientClass("foo");
+
+   // Second pool. It only allows client class bar.
+   auto pool1 = boost::make_shared<Pool4>(IOAddress("192.0.2.120"),
+                                         IOAddress("192.0.2.129"));
+   pool1->allowClientClass("bar");
+   subnet_->addPool(pool1);
+
+   // Third pool. It only allows client class foo.
+   auto pool2 = boost::make_shared<Pool4>(IOAddress("192.0.2.140"),
+                                          IOAddress("192.0.2.149"));
+   pool2->allowClientClass("foo");
+   subnet_->addPool(pool2);
+
+   // Forth pool. It only allows client class bar.
+   auto pool3 = boost::make_shared<Pool4>(IOAddress("192.0.2.160"),
+                                          IOAddress("192.0.2.169"));
+   pool3->allowClientClass("bar");
+   subnet_->addPool(pool3);
+
+   // Remember offered addresses.
+   std::set<IOAddress> addresses_set;
+
+   // Simulate client's request belonging to the class bar.
+   cc_.insert("bar");
+   for (auto i = 0; i < 40; ++i) {
+       // Allocate random addresses and make sure they belong to the
+       // pools associated with the class bar.
+       IOAddress candidate = alloc.pickAddress(cc_, clientid_, IOAddress("0.0.0.0"));
+       addresses_set.insert(candidate);
+       EXPECT_TRUE(pool1->inRange(candidate) || pool3->inRange(candidate));
+   }
+   EXPECT_EQ(20, addresses_set.size());
+
+   addresses_set.clear();
+
+   // Simulate the case that the client also belongs to the class foo.
+   // All pools should now be available.
+   cc_.insert("foo");
+   for (auto i = 0; i < 60; ++i) {
+       IOAddress candidate = alloc.pickAddress(cc_, clientid_, IOAddress("0.0.0.0"));
+       addresses_set.insert(candidate);
+       EXPECT_TRUE(subnet_->inRange(candidate));
+   }
+   EXPECT_EQ(40, addresses_set.size());
+
+   // When the client does not belong to any client class the allocator
+   // can't offer any address to the client.
+   cc_.clear();
+   IOAddress candidate = alloc.pickAddress(cc_, clientid_, IOAddress("0.0.0.0"));
+   EXPECT_TRUE(candidate.isV4Zero());
+}
+
+using RandomAllocatorTest6 = AllocEngine6Test;
+
+// Test allocating IPv6 addresses when a subnet has a single pool.
+TEST_F(RandomAllocatorTest6, singlePool) {
+    RandomAllocator alloc(Lease::TYPE_NA, subnet_);
+
+    // Remember returned addresses, so we can verify that unique addresses
+    // are returned.
+    std::set<IOAddress> addresses;
+    for (auto i = 0; i < 1000; ++i) {
+        IOAddress candidate = alloc.pickAddress(cc_, duid_, IOAddress("::"));
+        addresses.insert(candidate);
+        EXPECT_TRUE(subnet_->inPool(Lease::TYPE_NA, candidate));
+        EXPECT_TRUE(subnet_->inPool(Lease::TYPE_NA, candidate, cc_));
+    }
+    // The pool comprises 17 addresses. All should be returned.
+    EXPECT_EQ(17, addresses.size());
+}
+
+// Test allocating IPv6 addresses from multiple pools.
+TEST_F(RandomAllocatorTest6, manyPools) {
+    RandomAllocator alloc(Lease::TYPE_NA, subnet_);
+
+    // Add several more pools.
+    for (int i = 2; i < 10; ++i) {
+        stringstream min, max;
+        min << "2001:db8:1::" << hex << i * 16 + 1;
+        max << "2001:db8:1::" << hex << i * 16 + 9;
+        auto pool = boost::make_shared<Pool6>(Lease::TYPE_NA,
+                                              IOAddress(min.str()),
+                                              IOAddress(max.str()));
+        subnet_->addPool(pool);
+    }
+
+    // First pool (::10 - ::20) has 17 addresses.
+    // There are 8 extra pools with 9 addresses in each.
+    int total = 17 + 8 * 9;
+
+    // Repeat allocation of all addresses several times. Make sure that
+    // the same addresses are returned when all pools are exhausted.
+    for (auto j = 0; j < 6; ++j) {
+        std::set<IOAddress> addresses_set;
+        std::vector<IOAddress> addresses_vector;
+        std::vector<PoolPtr> pools_vector;
+
+        // Pick random addresses the number of times equal to the
+        // subnet capacity to ensure that all addresses are returned.
+        for (auto i = 0; i < total; ++i) {
+            IOAddress candidate = alloc.pickAddress(cc_, duid_, IOAddress("::"));
+            addresses_set.insert(candidate);
+            addresses_vector.push_back(candidate);
+            EXPECT_TRUE(subnet_->inPool(Lease::TYPE_NA, candidate));
+            EXPECT_TRUE(subnet_->inPool(Lease::TYPE_NA, candidate, cc_));
+            pools_vector.push_back(subnet_->getPool(Lease::TYPE_NA, candidate));
+        }
+        // Make sure that unique addresses have been returned.
+        EXPECT_EQ(total, addresses_set.size());
+
+        // Verify that the addresses are returned in the random order.
+        // Count how many times we found consecutive addresses. It should
+        // be 0 or close to 0.
+        int consecutives = 0;
+        for (auto k = 0; k < addresses_vector.size()-1; ++k) {
+            
+            if (IOAddress::increase(addresses_vector[k]) == addresses_vector[k+1]) {
+                ++consecutives;
+            }
+        }
+        // Ideally, the number of consecutive occurences should be 0 but we
+        // allow some to make sure the test doesn't fall over sporadically.
+        EXPECT_LT(consecutives, addresses_vector.size()/4);
+
+        // Repeat similar check for pools. The pools should be picked in the
+        // random order too.
+        int pool_matches = 0;
+        for (auto k = 0; k < pools_vector.size()-1; ++k) {
+            if (pools_vector[k] == subnet_->getPools(Lease::TYPE_NA)[k]) {
+                ++pool_matches;
+            }
+        }
+        EXPECT_LT(pool_matches, pools_vector.size()/2);
+    }
+}
+
+// Test that the allocator respects client classes while it picks
+// pools and addresses.
+TEST_F(RandomAllocatorTest6, clientClasses) {
+   RandomAllocator alloc(Lease::TYPE_NA, subnet_);
+
+   // First pool only allows the client class foo.
+   pool_->allowClientClass("foo");
+
+   // Second pool. It only allows client class bar.
+   auto pool1 = boost::make_shared<Pool6>(Lease::TYPE_NA,
+                                          IOAddress("2001:db8:1::120"),
+                                          IOAddress("2001:db8:1::129"));
+   pool1->allowClientClass("bar");
+   subnet_->addPool(pool1);
+
+   // Third pool. It only allows client class foo.
+   auto pool2 = boost::make_shared<Pool6>(Lease::TYPE_NA,
+                                          IOAddress("2001:db8:1::140"),
+                                          IOAddress("2001:db8:1::149"));
+   pool2->allowClientClass("foo");
+   subnet_->addPool(pool2);
+
+   // Forth pool. It only allows client class bar.
+   auto pool3 = boost::make_shared<Pool6>(Lease::TYPE_NA,
+                                          IOAddress("2001:db8:1::160"),
+                                          IOAddress("2001:db8:1::169"));
+   pool3->allowClientClass("bar");
+   subnet_->addPool(pool3);
+
+   // Remember offered addresses.
+   std::set<IOAddress> addresses_set;
+
+   // Simulate client's request belonging to the class bar.
+   cc_.insert("bar");
+   for (auto i = 0; i < 60; ++i) {
+       // Allocate random addresses and make sure they belong to the
+       // pools associated with the class bar.
+       IOAddress candidate = alloc.pickAddress(cc_, duid_, IOAddress("::"));
+       addresses_set.insert(candidate);
+       EXPECT_TRUE(pool1->inRange(candidate) || pool3->inRange(candidate));
+   }
+   EXPECT_EQ(20, addresses_set.size());
+
+   addresses_set.clear();
+
+   // Simulate the case that the client also belongs to the class foo.
+   // All pools should now be available.
+   cc_.insert("foo");
+   for (auto i = 0; i < 100; ++i) {
+       IOAddress candidate = alloc.pickAddress(cc_, duid_, IOAddress("::"));
+       addresses_set.insert(candidate);
+       EXPECT_TRUE(subnet_->inRange(candidate));
+   }
+   EXPECT_EQ(47, addresses_set.size());
+
+   // When the client does not belong to any client class the allocator
+   // can't offer any address to the client.
+   cc_.clear();
+   IOAddress candidate = alloc.pickAddress(cc_, duid_, IOAddress("0.0.0.0"));
+   EXPECT_TRUE(candidate.isV4Zero());
+}
+
+// Test allocating delegated prefixes when a subnet has a single pool.
+TEST_F(RandomAllocatorTest6, singlePdPool) {
+    RandomAllocator alloc(Lease::TYPE_PD, subnet_);
+
+    // Remember returned prefixes, so we can verify that unique addresses
+    // are returned.
+    std::set<IOAddress> prefixes;
+    for (auto i = 0; i < 66000; ++i) {
+        IOAddress candidate = alloc.pickAddress(cc_, duid_, IOAddress("::"));
+        prefixes.insert(candidate);
+        EXPECT_TRUE(subnet_->inPool(Lease::TYPE_PD, candidate));
+        EXPECT_TRUE(subnet_->inPool(Lease::TYPE_PD, candidate, cc_));
+    }
+    // The pool comprises 65536 prefixes. All should be returned.
+    EXPECT_EQ(65536, prefixes.size());
+}
+
+// Test allocating delegated prefixes from multiple pools.
+TEST_F(RandomAllocatorTest6, manyPdPools) {
+    RandomAllocator alloc(Lease::TYPE_PD, subnet_);
+
+    for (auto i = 0; i < 10; ++i) {
+        ostringstream s;
+        s << "300" << hex << i+1 << "::";
+        auto pool = boost::make_shared<Pool6>(Lease::TYPE_PD,
+                                              IOAddress(s.str()),
+                                              120,
+                                              128);
+        subnet_->addPool(pool);
+    }
+
+    size_t total = 65536 + 10*256;
+
+    for (auto j = 0; j < 2; ++j) {
+        std::set<IOAddress> prefixes;
+        for (auto i = 0; i < total; ++i) {
+            IOAddress candidate = alloc.pickAddress(cc_, duid_, IOAddress("::"));
+            prefixes.insert(candidate);
+            EXPECT_TRUE(subnet_->inPool(Lease::TYPE_PD, candidate));
+            EXPECT_TRUE(subnet_->inPool(Lease::TYPE_PD, candidate, cc_));
+        }
+        // Make sure that unique prefixes have been returned.
+        EXPECT_EQ(total, prefixes.size());
+    }
+}
+
+} // end of isc::dhcp::test namespace
+} // end of isc::dhcp namespace
+} // end of isc namespace