BMF: Fatpipe support

Adjust A' matrix and is_bmf functions accordingly.

diff --git a/src/kernel/lmm/bmf.cpp b/src/kernel/lmm/bmf.cpp
index 7dfa0e0..a569f6a 100644 (file)
--- a/src/kernel/lmm/bmf.cpp
+++ b/src/kernel/lmm/bmf.cpp
@@ -58,11 +58,21 @@ bool AllocationGenerator::next(std::vector<int>& next_alloc)
 
 /*****************************************************************************/
 
-BmfSolver::BmfSolver(Eigen::MatrixXd A, Eigen::MatrixXd maxA, Eigen::VectorXd C, Eigen::VectorXd phi)
-    : A_(std::move(A)), maxA_(std::move(maxA)), C_(std::move(C)), phi_(std::move(phi)), gen_(A_)
+BmfSolver::BmfSolver(Eigen::MatrixXd A, Eigen::MatrixXd maxA, Eigen::VectorXd C, std::vector<bool> shared,
+                     Eigen::VectorXd phi)
+    : A_(std::move(A))
+    , maxA_(std::move(maxA))
+    , C_(std::move(C))
+    , C_shared_(std::move(shared))
+    , phi_(std::move(phi))
+    , gen_(A_)
 {
   xbt_assert(max_iteration_ > 0,
              "Invalid number of iterations for BMF solver. Please check your \"bmf/max-iterations\" configuration.");
+  xbt_assert(A_.cols() == maxA_.cols(), "Invalid number of cols in matrix A (%ld) or maxA (%ld)", A_.cols(),
+             maxA_.cols());
+  xbt_assert(A_.cols() == static_cast<long>(phi_.size()), "Invalid size of phi vector (%ld)", phi_.size());
+  xbt_assert(static_cast<long>(C_shared_.size()) == C_.size(), "Invalid size param shared (%zu)", C_shared_.size());
 }
 
 template <typename T> std::string BmfSolver::debug_eigen(const T& obj) const
@@ -92,6 +102,9 @@ std::string BmfSolver::debug_alloc(const allocation_map_t& alloc) const
 double BmfSolver::get_resource_capacity(int resource, const std::vector<int>& bounded_players) const
 {
   double capacity = C_[resource];
+  if (not C_shared_[resource])
+    return capacity;
+
   for (int p : bounded_players) {
     capacity -= A_(resource, p) * phi_[p];
   }
@@ -115,10 +128,7 @@ Eigen::VectorXd BmfSolver::equilibrium(const allocation_map_t& alloc) const
   Eigen::MatrixXd A_p = Eigen::MatrixXd::Zero(n_players, n_players); // square matrix with number of players
   Eigen::VectorXd C_p = Eigen::VectorXd::Zero(n_players);
 
-  // iterate over alloc to verify if 2 players have chosen the same resource
-  // if so, they must have a fair sharing of this resource, adjust A_p and C_p accordingly
-  int last_row  = n_players - 1;
-  int first_row = 0;
+  int row = 0;
   std::vector<int> bounded_players;
   for (const auto& e : alloc) {
     // add one row for the resource with A[r,]
@@ -127,20 +137,32 @@ Eigen::VectorXd BmfSolver::equilibrium(const allocation_map_t& alloc) const
       bounded_players.insert(bounded_players.end(), e.second.begin(), e.second.end());
       continue;
     }
-    A_p.row(first_row) = A_.row(cur_resource);
-    C_p[first_row]     = get_resource_capacity(cur_resource, bounded_players);
-    first_row++;
-    if (e.second.size() > 1) {
-      auto it = e.second.begin();
-      int i   = *it; // first player
-      /* for each other player sharing this resource */
-      for (++it; it != e.second.end(); ++it) {
-        /* player i and k on this resource j: so maxA_ji*rho_i - maxA_jk*rho_k = 0 */
-        int k            = *it;
-        C_p[last_row]    = 0;
-        A_p(last_row, i) = maxA_(cur_resource, i);
-        A_p(last_row, k) = -maxA_(cur_resource, k);
-        last_row--;
+    if (C_shared_[cur_resource]) {
+      /* shared resource: fairly share it between players */
+      A_p.row(row) = A_.row(cur_resource);
+      C_p[row]     = get_resource_capacity(cur_resource, bounded_players);
+      row++;
+      if (e.second.size() > 1) {
+        // if 2 players have chosen the same resource
+        // they must have a fair sharing of this resource, adjust A_p and C_p accordingly
+        auto it = e.second.begin();
+        int i   = *it; // first player
+        /* for each other player sharing this resource */
+        for (++it; it != e.second.end(); ++it) {
+          /* player i and k on this resource j: so maxA_ji*rho_i - maxA_jk*rho_k = 0 */
+          int k       = *it;
+          C_p[row]    = 0;
+          A_p(row, i) = maxA_(cur_resource, i);
+          A_p(row, k) = -maxA_(cur_resource, k);
+          row++;
+        }
+      }
+    } else {
+      /* not shared resource, each player can receive the full capacity of the resource */
+      for (int i : e.second) {
+        C_p[row]    = get_resource_capacity(cur_resource, bounded_players);
+        A_p(row, i) = A_(cur_resource, i);
+        row++;
       }
     }
   }
@@ -259,7 +281,12 @@ bool BmfSolver::is_bmf(const Eigen::VectorXd& rho) const
   bool bmf = true;
 
   // 1) the capacity of all resources is respected
+  Eigen::VectorXd shared(C_shared_.size());
+  for (int j = 0; j < shared.size(); j++)
+    shared[j] = C_shared_[j] ? 1.0 : 0.0;
+
   Eigen::VectorXd remaining = (A_ * rho) - C_;
+  remaining                 = remaining.array() * shared.array(); // ignore non shared resources
   bmf                       = bmf && (not std::any_of(remaining.data(), remaining.data() + remaining.size(),
                                 [](double v) { return double_positive(v, sg_maxmin_precision); }));
 
@@ -399,14 +426,18 @@ void BmfSystem::get_flows_data(int number_cnsts, Eigen::MatrixXd& A, Eigen::Matr
   phi.conservativeResize(var_idx);
 }
 
-template <class CnstList> void BmfSystem::get_constraint_data(const CnstList& cnst_list, Eigen::VectorXd& C)
+template <class CnstList>
+void BmfSystem::get_constraint_data(const CnstList& cnst_list, Eigen::VectorXd& C, std::vector<bool>& shared)
 {
   C.resize(cnst_list.size());
+  shared.resize(cnst_list.size());
   cnst2idx_.clear();
   int cnst_idx = 0;
   for (const Constraint& cnst : cnst_list) {
     C(cnst_idx)      = cnst.bound_;
     cnst2idx_[&cnst] = cnst_idx;
+    // FATPIPE links aren't really shared
+    shared[cnst_idx] = (cnst.sharing_policy_ != Constraint::SharingPolicy::FATPIPE);
     cnst_idx++;
   }
 }
@@ -428,10 +459,11 @@ template <class CnstList> void BmfSystem::bmf_solve(const CnstList& cnst_list)
   cnst2idx_.clear();
   Eigen::MatrixXd A, maxA;
   Eigen::VectorXd C, bounds;
-  get_constraint_data(cnst_list, C);
+  std::vector<bool> shared;
+  get_constraint_data(cnst_list, C, shared);
   get_flows_data(C.size(), A, maxA, bounds);
 
-  auto solver = BmfSolver(A, maxA, C, bounds);
+  auto solver = BmfSolver(std::move(A), std::move(maxA), std::move(C), std::move(shared), std::move(bounds));
   auto rho    = solver.solve();
 
   if (rho.size() == 0)

diff --git a/src/kernel/lmm/bmf.hpp b/src/kernel/lmm/bmf.hpp
index 3b5b0af..601151b 100644 (file)
--- a/src/kernel/lmm/bmf.hpp
+++ b/src/kernel/lmm/bmf.hpp
@@ -29,7 +29,16 @@ private:
 
 class XBT_PUBLIC BmfSolver {
 public:
-  BmfSolver(Eigen::MatrixXd A, Eigen::MatrixXd maxA, Eigen::VectorXd C, Eigen::VectorXd phi);
+  /**
+   * @brief Instantiate the BMF solver
+   *
+   * @param A A_ji: consumption of player i on resource j
+   * @param maxA maxA_ji: consumption of larger player i on resource j
+   * @param C Resource capacity
+   * @param shared Is resource shared between player or each player receives the full capacity (FATPIPE links)
+   * @param phi Bound for each player
+   */
+  BmfSolver(Eigen::MatrixXd A, Eigen::MatrixXd maxA, Eigen::VectorXd C, std::vector<bool> shared, Eigen::VectorXd phi);
   /** @brief Solve equation system to find a fair-sharing of resources */
   Eigen::VectorXd solve();
 
@@ -120,12 +129,13 @@ private:
   Eigen::MatrixXd maxA_; //!< maxA_ji,  similar as A_, but containing the maximum consumption of player i (if player a
                          //!< single flow it's equal to A_)
   Eigen::VectorXd C_;    //!< C_j Capacity of each resource
-  Eigen::VectorXd phi_;  //!< phi_i bound for each player
+  std::vector<bool> C_shared_; //!< shared_j Resource j is shared or not
+  Eigen::VectorXd phi_;        //!< phi_i bound for each player
 
   std::unordered_set<std::vector<int>, boost::hash<std::vector<int>>> allocations_;
   AllocationGenerator gen_;
   std::vector<int> allocations_age_;
-  static constexpr int NO_RESOURCE = -1;     //!< flag to indicate player has selected no resource
+  static constexpr int NO_RESOURCE = -1;                    //!< flag to indicate player has selected no resource
   int max_iteration_               = sg_bmf_max_iterations; //!< number maximum of iterations of BMF algorithm
 };
 
@@ -164,8 +174,10 @@ private:
    *
    * @param cnst_list Constraint list (modified for selective update or active)
    * @param C Resource capacity vector
+   * @param shared Resource is shared or not (fatpipe links)
    */
-  template <class CnstList> void get_constraint_data(const CnstList& cnst_list, Eigen::VectorXd& C);
+  template <class CnstList>
+  void get_constraint_data(const CnstList& cnst_list, Eigen::VectorXd& C, std::vector<bool>& shared);
 
   std::unordered_map<int, Variable*> idx2Var_; //!< Map player index (and position in matrices) to system's variable
   std::unordered_map<const Constraint*, int> cnst2idx_; //!< Conversely map constraint to index

diff --git a/src/kernel/lmm/bmf_test.cpp b/src/kernel/lmm/bmf_test.cpp
index 0ad0f61..e4be895 100644 (file)
--- a/src/kernel/lmm/bmf_test.cpp
+++ b/src/kernel/lmm/bmf_test.cpp
@@ -141,6 +141,34 @@ TEST_CASE("kernel::bmf Basic tests", "[kernel-bmf-basic]")
     REQUIRE(double_equals(rho_2->get_value(), .8, sg_maxmin_precision));
   }
 
+  SECTION("Fatpipe")
+  {
+    /*
+     * Two flows using a fatpipe resource
+     *
+     * In details:
+     *   o System:  a1 * p1 * \rho1 < C and  a2 * p2 * \rho2 < C
+     *   o consumption_weight: a1=1 ; a2=1
+     *   o sharing_penalty:    p1=1 ; p2=1
+     *
+     * Expectations
+     *   o a1*rho1 = C
+     *   o a2*rho2 = C
+     */
+
+    lmm::Constraint* sys_cnst = Sys.constraint_new(nullptr, 3);
+    sys_cnst->set_sharing_policy(lmm::Constraint::SharingPolicy::FATPIPE, {});
+    lmm::Variable* rho_1 = Sys.variable_new(nullptr, 1);
+    lmm::Variable* rho_2 = Sys.variable_new(nullptr, 1);
+
+    Sys.expand(sys_cnst, rho_1, 1);
+    Sys.expand(sys_cnst, rho_2, 1);
+    Sys.solve();
+
+    REQUIRE(double_equals(rho_1->get_value(), 3.0, sg_maxmin_precision));
+    REQUIRE(double_equals(rho_2->get_value(), 3.0, sg_maxmin_precision));
+  }
+
   Sys.variable_free_all();
 }