1 files changed, 559 insertions, 0 deletions

diff --git a/src/ats/plugin_ats_mlp.h b/src/ats/plugin_ats_mlp.h
new file mode 100644
index 000000000..57698c708
--- /dev/null
+++ b/src/ats/plugin_ats_mlp.h
@@ -0,0 +1,559 @@
+/*
+ (C) 2011 Christian Grothoff (and other contributing authors)
+
+ GNUnet is free software; you can redistribute it and/or modify
+ it under the terms of the GNU General Public License as published
+ by the Free Software Foundation; either version 3, or (at your
+ option) any later version.
+
+ GNUnet is distributed in the hope that it will be useful, but
+ WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ General Public License for more details.
+
+ You should have received a copy of the GNU General Public License
+ along with GNUnet; see the file COPYING.  If not, write to the
+ Free Software Foundation, Inc., 59 Temple Place - Suite 330,
+ Boston, MA 02111-1307, USA.
+ */
+
+/**
+ * @file ats/plugin_ats_mlp.h
+ * @brief ats MLP problem solver
+ * @author Matthias Wachs
+ * @author Christian Grothoff
+ */
+#include "platform.h"
+#include "gnunet_util_lib.h"
+#include "gnunet_ats_service.h"
+#include "gnunet_ats_plugin.h"
+#include "gnunet-service-ats_addresses.h"
+#include "gnunet_statistics_service.h"
+#if HAVE_LIBGLPK
+#include "glpk.h"
+#endif
+
+#ifndef GNUNET_SERVICE_ATS_ADDRESSES_MLP_H
+#define GNUNET_SERVICE_ATS_ADDRESSES_MLP_H
+
+#define BIG_M_VALUE (UINT32_MAX) /10
+#define BIG_M_STRING "unlimited"
+
+#define MLP_AVERAGING_QUEUE_LENGTH 3
+
+#define MLP_MAX_EXEC_DURATION   GNUNET_TIME_relative_multiply(GNUNET_TIME_UNIT_SECONDS, 10)
+#define MLP_MAX_ITERATIONS      4096
+
+#define DEFAULT_D 1.0
+#define DEFAULT_R 1.0
+#define DEFAULT_U 1.0
+#define DEFAULT_QUALITY 1.0
+#define DEFAULT_MIN_CONNECTIONS 4
+#define DEFAULT_PEER_PREFERENCE 1.0
+
+#define MLP_NaN -1
+#define MLP_UNDEFINED 0
+#define GLP_YES 1.0
+#define GLP_NO  0.0
+
+struct MLP_Solution
+{
+  int lp_res;
+  int lp_presolv;
+  int mip_res;
+  int mip_presolv;
+
+  int p_elements;
+  int p_cols;
+  int p_rows;
+
+  int n_peers;
+  int n_addresses;
+
+};
+
+struct ATS_Peer
+{
+  struct GNUNET_PeerIdentity id;
+
+  /* Was this peer already added to the current problem? */
+  int processed;
+
+  /* constraint 2: 1 address per peer*/
+  unsigned int r_c2;
+
+  /* constraint 9: relativity */
+  unsigned int r_c9;
+
+  /* Legacy preference value */
+  double f;
+};
+
+struct MLP_Problem
+{
+  /**
+   * GLPK (MLP) problem object
+   */
+#if HAVE_LIBGLPK
+  glp_prob *prob;
+#else
+  void *prob;
+#endif
+
+  /* Number of addresses in problem */
+  unsigned int num_addresses;
+  /* Number of peers in problem */
+  unsigned int num_peers;
+  /* Number of elements in problem matrix */
+  unsigned int num_elements;
+
+  /* Row index constraint 2: */
+  unsigned int r_c2;
+  /* Row index constraint 4: minimum connections */
+  unsigned int r_c4;
+  /* Row index constraint 6: maximize diversity */
+  unsigned int r_c6;
+  /* Row index constraint 8: utilization*/
+  unsigned int r_c8;
+  /* Row index constraint 9: relativity*/
+  unsigned int r_c9;
+  /* Row indices quality metrics  */
+  int r_q[GNUNET_ATS_QualityPropertiesCount];
+  /* Row indices ATS network quotas */
+  int r_quota[GNUNET_ATS_NetworkTypeCount];
+
+  /* Column index Diversity (D) column */
+  int c_d;
+  /* Column index Utilization (U) column */
+  int c_u;
+  /* Column index Proportionality (R) column */
+  int c_r;
+  /* Column index quality metrics  */
+  int c_q[GNUNET_ATS_QualityPropertiesCount];
+
+  /* Problem matrix */
+  /* Current index */
+  unsigned int ci;
+  /* Row index array */
+  int *ia;
+  /* Column index array */
+  int *ja;
+  /* Column index value */
+  double *ar;
+
+};
+
+struct MLP_Variables
+{
+  /* Big M value for bandwidth capping */
+  double BIG_M;
+
+  /* ATS Quality metrics
+   *
+   * Array with GNUNET_ATS_QualityPropertiesCount elements
+   * contains mapping to GNUNET_ATS_Property*/
+  int q[GNUNET_ATS_QualityPropertiesCount];
+
+  /* Number of quality metrics */
+  int m_q;
+
+  /* Number of quality metrics */
+  int m_rc;
+
+  /* Quality metric coefficients*/
+  double co_Q[GNUNET_ATS_QualityPropertiesCount];
+
+  /* Ressource costs coefficients*/
+  double co_RC[GNUNET_ATS_QualityPropertiesCount];
+
+  /* Diversity coefficient */
+  double co_D;
+
+  /* Utility coefficient */
+  double co_U;
+
+  /* Relativity coefficient */
+  double co_R;
+
+  /* Minimum bandwidth assigned to an address */
+  unsigned int b_min;
+
+  /* Minimum number of addresses with bandwidth assigned */
+  unsigned int n_min;
+
+  /* Quotas */
+  /* Array mapping array index to ATS network */
+  int quota_index[GNUNET_ATS_NetworkTypeCount];
+  /* Outbound quotas */
+  unsigned long long quota_out[GNUNET_ATS_NetworkTypeCount];
+  /* Inbound quotas */
+
+  unsigned long long quota_in[GNUNET_ATS_NetworkTypeCount];
+
+  /* ATS ressource costs
+   * array with GNUNET_ATS_QualityPropertiesCount elements
+   * contains mapping to GNUNET_ATS_Property
+   * */
+  int rc[GNUNET_ATS_QualityPropertiesCount];
+
+};
+
+/**
+ * MLP Handle
+ */
+struct GAS_MLP_Handle
+{
+  struct GNUNET_ATS_PluginEnvironment *env;
+
+  /**
+   * Statistics handle
+   */
+  struct GNUNET_STATISTICS_Handle *stats;
+
+  /**
+   * Address hashmap for lookups
+   */
+  const struct GNUNET_CONTAINER_MultiPeerMap *addresses;
+
+  /**
+   * Addresses' bandwidth changed callback
+   */
+  GAS_bandwidth_changed_cb bw_changed_cb;
+
+  /**
+   * Addresses' bandwidth changed callback closure
+   */
+  void *bw_changed_cb_cls;
+
+  /**
+   * ATS function to get preferences
+   */
+  GAS_get_preferences get_preferences;
+
+  /**
+   * Closure for ATS function to get preferences
+   */
+  void *get_preferences_cls;
+
+  /**
+   * ATS function to get properties
+   */
+  GAS_get_properties get_properties;
+
+  /**
+   * Closure for ATS function to get properties
+   */
+  void *get_properties_cls;
+
+  /**
+   * Exclude peer from next result propagation
+   */
+  const struct GNUNET_PeerIdentity *exclude_peer;
+
+  /**
+   * Encapsulation for the MLP problem
+   */
+  struct MLP_Problem p;
+
+  /**
+   * Encapsulation for the MLP problem variables
+   */
+  struct MLP_Variables pv;
+
+  /**
+   * Encapsulation for the MLP solution
+   */
+  struct MLP_Solution ps;
+
+  /**
+   * Bulk lock
+   */
+
+  int bulk_lock;
+
+  /**
+   * Number of changes while solver was locked
+   */
+  int bulk_request;
+
+  /**
+   * GLPK LP control parameter
+   */
+#if HAVE_LIBGLPK
+  glp_smcp control_param_lp;
+#else
+  void *control_param_lp;
+#endif
+
+  /**
+   * GLPK LP control parameter
+   */
+#if HAVE_LIBGLPK
+  glp_iocp control_param_mlp;
+#else
+  void *control_param_mlp;
+#endif
+
+  /**
+   * Peers with pending address requests
+   */
+  struct GNUNET_CONTAINER_MultiPeerMap *requested_peers;
+
+  /**
+   * Was the problem updated since last solution
+   */
+  int mlp_prob_updated;
+
+  /**
+   * Has the problem size changed since last solution
+   */
+  int mlp_prob_changed;
+
+  /**
+   * Solve the problem automatically when updates occur?
+   * Default: GNUNET_YES
+   * Can be disabled for test and measurements
+   */
+  int mlp_auto_solve;
+
+  /**
+   * Write MILP problem to a MPS file
+   */
+  int write_mip_mps;
+
+  /**
+   * Write MILP problem to a MPS file
+   */
+  int write_mip_sol;
+
+};
+
+/**
+ * Address specific MLP information
+ */
+struct MLP_information
+{
+
+  /* Bandwidth assigned */
+  struct GNUNET_BANDWIDTH_Value32NBO b_out;
+  struct GNUNET_BANDWIDTH_Value32NBO b_in;
+
+  /* Address selected */
+  int n;
+
+  /* bandwidth column index */
+  signed int c_b;
+
+  /* address usage column */
+  signed int c_n;
+
+  /* row indexes */
+
+  /* constraint 1: bandwidth capping */
+  unsigned int r_c1;
+
+  /* constraint 3: minimum bandwidth */
+  unsigned int r_c3;
+};
+
+
+/**
+ * Solves the MLP problem
+ *
+ * @param solver the MLP Handle
+ * @return #GNUNET_OK if could be solved, GNUNET_SYSERR on failure
+ */
+int
+GAS_mlp_solve_problem (void *solver);
+
+
+/**
+ * Init the MLP problem solving component
+ *
+ * @param cfg the GNUNET_CONFIGURATION_Handle handle
+ * @param stats the GNUNET_STATISTICS handle
+ * @param addresses Hashmap containing addresses
+ * @param network array of GNUNET_ATS_NetworkType with length dest_length
+ * @param out_dest array of outbound quotas
+ * @param in_dest array of outbound quota
+ * @param dest_length array length for quota arrays
+ * @param bw_changed_cb callback for changed bandwidth amounts
+ * @param bw_changed_cb_cls cls for callback
+ * @param get_preference callback to get relative preferences for a peer
+ * @param get_preference_cls cls for callback to get relative preferences for a peer
+ * @param get_properties callback to get relative properties
+ * @param get_properties_cls cls for callback to get relative properties
+ * @return struct GAS_MLP_Handle on success, NULL on fail
+ */
+void *
+GAS_mlp_init (const struct GNUNET_CONFIGURATION_Handle *cfg,
+              const struct GNUNET_STATISTICS_Handle *stats,
+              const struct GNUNET_CONTAINER_MultiPeerMap *addresses,
+              int *network,
+              unsigned long long *out_dest,
+              unsigned long long *in_dest,
+              int dest_length,
+              GAS_bandwidth_changed_cb bw_changed_cb,
+              void *bw_changed_cb_cls,
+              GAS_get_preferences get_preference,
+              void *get_preference_cls,
+              GAS_get_properties get_properties,
+              void *get_properties_cls);
+
+
+/**
+ * Add a single address within a network to the solver
+ *
+ * @param solver the solver Handle
+ * @param address the address to add
+ * @param network network type of this address
+ */
+void
+GAS_mlp_address_add (void *solver, struct ATS_Address *address,
+    uint32_t network);
+
+
+/**
+ * Transport properties for this address have changed
+ *
+ * @param solver solver handle
+ * @param address the address
+ * @param type the ATSI type in HBO
+ * @param abs_value the absolute value of the property
+ * @param rel_value the normalized value
+ */
+void
+GAS_mlp_address_property_changed (void *solver, struct ATS_Address *address,
+    uint32_t type, uint32_t abs_value, double rel_value);
+
+
+/**
+ * Transport session for this address has changed
+ *
+ * NOTE: values in addresses are already updated
+ *
+ * @param solver solver handle
+ * @param address the address
+ * @param cur_session the current session
+ * @param new_session the new session
+ */
+void
+GAS_mlp_address_session_changed (void *solver, struct ATS_Address *address,
+                                 uint32_t cur_session, uint32_t new_session);
+
+
+/**
+ * Usage for this address has changed
+ *
+ * NOTE: values in addresses are already updated
+ *
+ * @param solver solver handle
+ * @param address the address
+ * @param in_use usage state
+ */
+void
+GAS_mlp_address_inuse_changed (void *solver, struct ATS_Address *address,
+    int in_use);
+
+/**
+ * Network scope for this address has changed
+ *
+ * NOTE: values in addresses are already updated
+ *
+ * @param solver solver handle
+ * @param address the address
+ * @param current_network the current network
+ * @param new_network the new network
+ */
+void
+GAS_mlp_address_change_network (void *solver, struct ATS_Address *address,
+    uint32_t current_network, uint32_t new_network);
+
+/**
+ * Deletes a single address in the MLP problem
+ *
+ * The MLP problem has to be recreated and the problem has to be resolved
+ *
+ * @param solver the MLP Handle
+ * @param address the address to delete
+ * @param session_only delete only session not whole address
+ */
+void
+GAS_mlp_address_delete (void *solver, struct ATS_Address *address,
+    int session_only);
+
+/**
+ * Changes the preferences for a peer in the MLP problem
+ *
+ * @param solver the MLP Handle
+ * @param peer the peer
+ * @param kind the kind to change the preference
+ * @param pref_rel the relative score
+ */
+void
+GAS_mlp_address_change_preference (void *solver,
+    const struct GNUNET_PeerIdentity *peer, enum GNUNET_ATS_PreferenceKind kind,
+    double pref_rel);
+
+/**
+ * Get application feedback for a peer
+ *
+ * @param solver the solver handle
+ * @param application the application
+ * @param peer the peer to change the preference for
+ * @param scope the time interval for this feedback: [now - scope .. now]
+ * @param kind the kind to change the preference
+ * @param score the score
+ */
+void
+GAS_mlp_address_preference_feedback (void *solver, void *application,
+    const struct GNUNET_PeerIdentity *peer,
+    const struct GNUNET_TIME_Relative scope,
+    enum GNUNET_ATS_PreferenceKind kind, double score);
+
+/**
+ * Start a bulk operation
+ *
+ * @param solver the solver
+ */
+void
+GAS_mlp_bulk_start (void *solver);
+
+/**
+ * Bulk operation done
+ */
+void
+GAS_mlp_bulk_stop (void *solver);
+
+/**
+ * Get the preferred address for a specific peer until
+ * GAS_mlp_stop_get_preferred_address is called
+ *
+ * @param solver the MLP Handle
+ * @param peer the peer
+ * @return suggested address
+ */
+const struct ATS_Address *
+GAS_mlp_get_preferred_address (void *solver,
+    const struct GNUNET_PeerIdentity *peer);
+
+/**
+ * Stop notifying about address and bandwidth changes for this peer
+ *
+ * @param solver the MLP handle
+ * @param peer the peer
+ */
+void
+GAS_mlp_stop_get_preferred_address (void *solver,
+    const struct GNUNET_PeerIdentity *peer);
+
+/**
+ * Shutdown the MLP problem solving component
+ *
+ * @param solver the solver handle
+ */
+void
+GAS_mlp_done (void *solver);
+
+#endif
+/* end of plugin_ats_mlp.h */