From 64a92508d1037bf23252bcea540490b4494d292b Mon Sep 17 00:00:00 2001 From: Marcin Siodelski Date: Mon, 26 Feb 2018 13:30:52 +0100 Subject: [PATCH] [5437] Optimized preferred subnet selection within shared network. --- src/lib/dhcpsrv/alloc_engine.cc | 24 +++++++++- src/lib/dhcpsrv/shared_network.cc | 45 ++++++++++++++++++- src/lib/dhcpsrv/shared_network.h | 22 +++++++++ src/lib/dhcpsrv/subnet.cc | 12 +++-- src/lib/dhcpsrv/subnet.h | 13 +++++- .../dhcpsrv/tests/alloc_engine4_unittest.cc | 9 +--- 6 files changed, 108 insertions(+), 17 deletions(-) diff --git a/src/lib/dhcpsrv/alloc_engine.cc b/src/lib/dhcpsrv/alloc_engine.cc index 8c9c2114fd..feca9f4850 100644 --- a/src/lib/dhcpsrv/alloc_engine.cc +++ b/src/lib/dhcpsrv/alloc_engine.cc @@ -3446,9 +3446,29 @@ AllocEngine::allocateUnreservedLease4(ClientContext4& ctx) { Lease4Ptr new_lease; AllocatorPtr allocator = getAllocator(Lease::TYPE_V4); Subnet4Ptr subnet = ctx.subnet_; - Subnet4Ptr original_subnet = subnet; + + // Need to check if the subnet belongs to a shared network. If so, + // we might be able to find a better subnet for lease allocation, + // for which it is more likely that there are some leases available. + // If we stick to the selected subnet, we may end up walking over + // the entire subnet (or more subnets) to discover that the address + // pools have been exhausted. Using a subnet from which an address + // was assigned most recently is an optimization which increases + // the likelyhood of starting from the subnet which address pools + // are not exhausted. SharedNetwork4Ptr network; - subnet->getSharedNetwork(network); + ctx.subnet_->getSharedNetwork(network); + if (network) { + // This would try to find a subnet with the same set of classes + // as the current subnet, but with the more recent "usage timestamp". + // This timestamp is only updated for the allocations made with an + // allocator (unreserved lease allocations), not the static + // allocations or requested addresses. + ctx.subnet_ = subnet = network->getPreferredSubnet(ctx.subnet_); + } + + Subnet4Ptr original_subnet = subnet; + uint64_t total_attempts = 0; while (subnet) { diff --git a/src/lib/dhcpsrv/shared_network.cc b/src/lib/dhcpsrv/shared_network.cc index 54e4e55acd..57123b9e36 100644 --- a/src/lib/dhcpsrv/shared_network.cc +++ b/src/lib/dhcpsrv/shared_network.cc @@ -194,6 +194,43 @@ public: // Got the next subnet, so return it. return (*subnet_it); } + + /// @brief Attempts to find a subnet which is more likely to include available + /// leases than selected subnet. + /// + /// When allocating unreserved leases from a shared network it is important to + /// remember from which subnet within the shared network we have been recently + /// handing out leases. The allocation engine can use that information to start + /// trying allocation of the leases from that subnet rather than from the default + /// subnet selected for this client. Starting from the default subnet causes a + /// risk of having to walk over many subnets with exhausted address pools before + /// getting to the subnet with available leases. This method attempts to find + /// such subnet by inspecting "last allocation" timestamps. The one with most + /// recent timestamp is selected. + /// + /// The preferred subnet must also fulfil the condition of equal client classes + /// with the @c selected_subnet. + /// + /// @param subnets Container holding subnets belonging to this shared + /// network. + /// @param selected_subnet Pointer to a currently selected subnet. + /// + /// @return Pointer to a preferred subnet. It may be the same as @c selected_subnet + /// if no better subnet was found. + template + static SubnetPtrType getPreferredSubnet(const SubnetCollectionType& subnets, + const SubnetPtrType& selected_subnet) { + + Subnet4Ptr preferred_subnet = selected_subnet; + for (auto s = subnets.begin(); s != subnets.end(); ++s) { + if (((*s)->getClientClasses() == selected_subnet->getClientClasses()) && + ((*s)->getLastAllocatedTime() > selected_subnet->getLastAllocatedTime())) { + preferred_subnet = (*s); + } + } + + return (preferred_subnet); + } }; } // end of anonymous namespace @@ -238,6 +275,11 @@ SharedNetwork4::getNextSubnet(const Subnet4Ptr& first_subnet, return (Impl::getNextSubnet(subnets_, first_subnet, current_subnet)); } +Subnet4Ptr +SharedNetwork4::getPreferredSubnet(const Subnet4Ptr& selected_subnet) const { + return (Impl::getPreferredSubnet(subnets_, selected_subnet)); +} + ElementPtr SharedNetwork4::toElement() const { ElementPtr map = Network4::toElement(); @@ -290,8 +332,7 @@ SharedNetwork6::getSubnet(const SubnetID& subnet_id) const { Subnet6Ptr SharedNetwork6::getNextSubnet(const Subnet6Ptr& first_subnet, const SubnetID& current_subnet) const { - return (Impl::getNextSubnet(subnets_, first_subnet, - current_subnet)); + return (Impl::getNextSubnet(subnets_, first_subnet, current_subnet)); } ElementPtr diff --git a/src/lib/dhcpsrv/shared_network.h b/src/lib/dhcpsrv/shared_network.h index 31d0d43d97..b2fbd8b223 100644 --- a/src/lib/dhcpsrv/shared_network.h +++ b/src/lib/dhcpsrv/shared_network.h @@ -120,6 +120,28 @@ public: Subnet4Ptr getNextSubnet(const Subnet4Ptr& first_subnet, const SubnetID& current_subnet) const; + /// @brief Attempts to find a subnet which is more likely to include available + /// leases than selected subnet. + /// + /// When allocating unreserved leases from a shared network it is important to + /// remember from which subnet within the shared network we have been recently + /// handing out leases. The allocation engine can use that information to start + /// trying allocation of the leases from that subnet rather than from the default + /// subnet selected for this client. Starting from the default subnet causes a + /// risk of having to walk over many subnets with exhausted address pools before + /// getting to the subnet with available leases. This method attempts to find + /// such subnet by inspecting "last allocation" timestamps. The one with most + /// recent timestamp is selected. + /// + /// The preferred subnet must also fulfil the condition of equal client classes + /// with the @c selected_subnet. + /// + /// @param selected_subnet Pointer to a currently selected subnet. + /// + /// @return Pointer to a preferred subnet. It may be the same as @c selected_subnet + /// if no better subnet was found. + Subnet4Ptr getPreferredSubnet(const Subnet4Ptr& selected_subnet) const; + /// @brief Unparses shared network object. /// /// @return A pointer to unparsed shared network configuration. diff --git a/src/lib/dhcpsrv/subnet.cc b/src/lib/dhcpsrv/subnet.cc index 86b05f1609..82365240d6 100644 --- a/src/lib/dhcpsrv/subnet.cc +++ b/src/lib/dhcpsrv/subnet.cc @@ -56,7 +56,8 @@ Subnet::Subnet(const isc::asiolink::IOAddress& prefix, uint8_t len, prefix_len_(len), last_allocated_ia_(lastAddrInPrefix(prefix, len)), last_allocated_ta_(lastAddrInPrefix(prefix, len)), - last_allocated_pd_(lastAddrInPrefix(prefix, len)) { + last_allocated_pd_(lastAddrInPrefix(prefix, len)), + last_allocated_time_(boost::posix_time::neg_infin) { if ((prefix.isV6() && len > 128) || (prefix.isV4() && len > 32)) { isc_throw(BadValue, @@ -99,16 +100,19 @@ void Subnet::setLastAllocated(Lease::Type type, case Lease::TYPE_V4: case Lease::TYPE_NA: last_allocated_ia_ = addr; - return; + break; case Lease::TYPE_TA: last_allocated_ta_ = addr; - return; + break; case Lease::TYPE_PD: last_allocated_pd_ = addr; - return; + break; default: isc_throw(BadValue, "Pool type " << type << " not supported"); } + + // Update the timestamp of last allocation. + last_allocated_time_ = boost::posix_time::microsec_clock::universal_time(); } std::string diff --git a/src/lib/dhcpsrv/subnet.h b/src/lib/dhcpsrv/subnet.h index 52b059a8e1..e2133cd976 100644 --- a/src/lib/dhcpsrv/subnet.h +++ b/src/lib/dhcpsrv/subnet.h @@ -22,6 +22,7 @@ #include #include #include +#include #include #include @@ -81,7 +82,13 @@ public: /// @return address/prefix that was last tried from this subnet isc::asiolink::IOAddress getLastAllocated(Lease::Type type) const; - /// @brief sets the last address that was tried from this subnet + /// @brief Returns the timestamp when the @c setLastAllocated function + /// was called. + boost::posix_time::ptime getLastAllocatedTime() const { + return (last_allocated_time_); + } + + /// @brief sets the last address that was tried from this pool /// /// This method sets the last address that was attempted to be allocated /// from this subnet. This is used as helper information for the next @@ -384,6 +391,10 @@ protected: /// See @ref last_allocated_ia_ for details. isc::asiolink::IOAddress last_allocated_pd_; + /// @brief Timestamp indicating when an address has been last allocated + /// from this subnet. + boost::posix_time::ptime last_allocated_time_; + /// @brief Name of the network interface (if connected directly) std::string iface_; diff --git a/src/lib/dhcpsrv/tests/alloc_engine4_unittest.cc b/src/lib/dhcpsrv/tests/alloc_engine4_unittest.cc index 3e1a370580..104f3ac8cf 100644 --- a/src/lib/dhcpsrv/tests/alloc_engine4_unittest.cc +++ b/src/lib/dhcpsrv/tests/alloc_engine4_unittest.cc @@ -2276,14 +2276,7 @@ TEST_F(AllocEngine4Test, findReservation) { EXPECT_TRUE(ctx.currentHost()); EXPECT_EQ(ctx.currentHost()->getIPv4Reservation(), host->getIPv4Reservation()); - // Regardless of the host reservation mode, the host should be - // always returned when findReservation() is called. - subnet_->setHostReservationMode(Network::HR_DISABLED); - ASSERT_NO_THROW(engine.findReservation(ctx)); - EXPECT_TRUE(ctx.currentHost()); - EXPECT_EQ(ctx.currentHost()->getIPv4Reservation(), host->getIPv4Reservation()); - - // Check the third possible reservation mode. + // Check the out of the pool reservation mode. subnet_->setHostReservationMode(Network::HR_OUT_OF_POOL); ASSERT_NO_THROW(engine.findReservation(ctx)); EXPECT_TRUE(ctx.currentHost()); -- 2.47.2