* @author Christian Grothoff
*/
#include "platform.h"
-
+#include "gnunet_statistics_service.h"
+#include "gnunet-service-ats_addresses.h"
#if HAVE_LIBGLPK
#include "glpk.h"
#endif
#ifndef GNUNET_SERVICE_ATS_ADDRESSES_MLP_H
#define GNUNET_SERVICE_ATS_ADDRESSES_MLP_H
+#define DEBUG_MLP GNUNET_EXTRA_LOGGING
+
+#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, 3)
#define MLP_MAX_ITERATIONS INT_MAX
+struct ATS_Peer
+{
+ struct ATS_Peer *next;
+ struct ATS_Peer *prev;
+
+ struct GNUNET_PeerIdentity id;
+
+ /* Array of quality preferences */
+ double f_q[GNUNET_ATS_QualityPropertiesCount];
+ /* Legacy preference value */
+ double f;
+
+ /* constraint 2: 1 address per peer*/
+ unsigned int r_c2;
+
+ /* constraint 9: relativity */
+ unsigned int r_c9;
+
+ struct ATS_Address *head;
+ struct ATS_Address *tail;
+};
+
+struct ATS_PreferedAddress
+{
+ uint32_t bandwidth_out;
+ uint32_t bandwidth_in;
+ struct ATS_Address *address;
+};
+
+struct GAS_MLP_SolutionContext
+{
+ int lp_result;
+ int mlp_result;
+ struct GNUNET_TIME_Relative lp_duration;
+ struct GNUNET_TIME_Relative mlp_duration;
+};
+
+/**
+ * MLP Handle
+ */
struct GAS_MLP_Handle
{
+ /**
+ * Statistics handle
+ */
+ struct GNUNET_STATISTICS_Handle *stats;
+
/**
* GLPK (MLP) problem object
*/
void *prob;
#endif
+ double BIG_M;
+
/**
* GLPK LP control parameter
*/
*/
glp_iocp control_param_mlp;
+ /**
+ * Solves the task in an regular interval
+ */
+ GNUNET_SCHEDULER_TaskIdentifier mlp_task;
+
+ /**
+ * Interval between scheduled problem solving
+ */
+ struct GNUNET_TIME_Relative exec_interval;
+
/**
* Maximum execution time per problem solving
*/
*/
unsigned int max_iterations;
+ /**
+ * Solve the problem automatically when updates occur?
+ * Default: GNUNET_YES
+ * Can be disabled for test and measurements
+ */
+ int auto_solve;
+
+ int semaphore;
+
+ /* state information */
+
+ /**
+ * Do we need to use the LP presolver?
+ *
+ * If the problem addresses were added or removed and the last basis was we
+ * need to use the presolver.
+ * presolver_required == GNUNET_YES
+ *
+ * If values were modified, we can reuse a valid basis
+ * presolver_required == GNUNET_NO
+ */
+ int presolver_required;
+
+ /* statistics */
+
+ /**
+ * Time of last execution
+ */
+ struct GNUNET_TIME_Absolute last_execution;
+
+
+ /**
+ * How often was the LP problem solved
+ */
+ unsigned int lp_solved;
+
+ /**
+ * total duration of all lp solver executions
+ */
+ uint64_t lp_total_duration;
+
+ /**
+ * How often was the MLP problem solved
+ */
+ unsigned int mlp_solved;
+
+ /**
+ * total duration of all mlp solver executions
+ */
+ uint64_t mlp_total_duration;
+
+ unsigned int addr_in_problem;
+
+ /* Information about the problem */
+
+ struct ATS_Peer *peer_head;
+ struct ATS_Peer *peer_tail;
+
+ /* Number of peers */
+ unsigned int c_p;
+
+ /* current problem matrix */
+ /* row index array */
+ int *ia;
+ /* column index array */
+ int *ja;
+ /* column index array */
+ double *ar;
+ /* current size of the constraint matrix |indices| */
+ unsigned int cm_size;
+ unsigned int ci;
+
+ /* 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;
+
+ /* column index Diversity (D) column */
+ int c_d;
+ double co_D;
+
+ /* column index Utilization (U) column */
+ int c_u;
+ double co_U;
+
+ /* column index Proportionality (R) column */
+ int c_r;
+ double co_R;
+
+ /* ATS Quality metrics
+ *
+ * array with GNUNET_ATS_QualityPropertiesCount elements
+ * contains mapping to GNUNET_ATS_Property*/
+ int q[GNUNET_ATS_QualityPropertiesCount];
+
+ /* column index quality metrics */
+ int c_q[GNUNET_ATS_QualityPropertiesCount];
+
+ /* column index quality metrics */
+ int r_q[GNUNET_ATS_QualityPropertiesCount];
+
+ /* quality metric coefficients*/
+ double co_Q[GNUNET_ATS_QualityPropertiesCount];
+
+ /* number of quality metrics */
+ int m_q;
+
+ /* ATS network quotas */
+ int c_quota[GNUNET_ATS_NetworkTypeCount];
+ int r_quota[GNUNET_ATS_NetworkTypeCount];
+ int quota_index [GNUNET_ATS_NetworkTypeCount];
+ unsigned long long quota_out[GNUNET_ATS_NetworkTypeCount];
+ 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];
+
+ /* column index ressource costs */
+ int c_rc[GNUNET_ATS_QualityPropertiesCount];
+
+ /* ressource costs coefficients*/
+ double co_RC[GNUNET_ATS_QualityPropertiesCount];
+
+ /* number of quality metrics */
+ int m_rc;
+
+ /* minimum bandwidth assigned to an address */
+ unsigned int b_min;
+
+ /* minimum number of addresses with bandwidth assigned */
+ unsigned int n_min;
+};
+
+
+/**
+ * Address specific MLP information
+ */
+struct MLP_information
+{
+ double b;
+
+ 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;
+
+ /* Quality information row indices */
+ unsigned int r_q[GNUNET_ATS_QualityPropertiesCount];
+
+ /* Quality information */
+ double q[GNUNET_ATS_QualityPropertiesCount][MLP_AVERAGING_QUEUE_LENGTH];
+
+ /* Quality information averaged */
+ double q_averaged[GNUNET_ATS_QualityPropertiesCount];
+
+ /* Averaging index */
+ int q_avg_i[GNUNET_ATS_QualityPropertiesCount];
};
+
/**
* Init the MLP problem solving component
+ *
+ * @param cfg configuration handle
+ * @param stats the GNUNET_STATISTICS handle
* @param max_duration maximum numbers of iterations for the LP/MLP Solver
* @param max_iterations maximum time limit for the LP/MLP Solver
- * @return GNUNET_OK on success, GNUNET_SYSERR on fail
+ * @return struct GAS_MLP_Handle * on success, NULL on fail
+ */
+struct GAS_MLP_Handle *
+GAS_mlp_init (const struct GNUNET_CONFIGURATION_Handle *cfg,
+ const struct GNUNET_STATISTICS_Handle *stats,
+ struct GNUNET_TIME_Relative max_duration,
+ unsigned int max_iterations);
+
+/**
+ * Solves the MLP problem on demand
+ *
+ * @param mlp the MLP Handle
+ * @param ctx solution context
+ * @return GNUNET_OK if could be solved, GNUNET_SYSERR on failure
*/
int
-GAS_mlp_init (struct GNUNET_TIME_Relative max_duration, unsigned int max_iterations);
+GAS_mlp_solve_problem (struct GAS_MLP_Handle *mlp, struct GAS_MLP_SolutionContext *ctx);
+
/**
- * Update address in the MLP problem
+ * Updates a single address in the MLP problem
+ *
+ * If the address did not exist before in the problem:
+ * The MLP problem has to be recreated and the problem has to be resolved
+ *
+ * Otherwise the addresses' values can be updated and the existing base can
+ * be reused
+ *
+ * @param mlp the MLP Handle
+ * @param addresses the address hashmap
+ * the address has to be already added from the hashmap
+ * @param address the address to update
*/
void
-GAS_mlp_update (struct ATS_Address *address);
+GAS_mlp_address_update (struct GAS_MLP_Handle *mlp, struct GNUNET_CONTAINER_MultiHashMap * addresses, struct ATS_Address *address);
+
+
+/**
+ * Deletes a single address in the MLP problem
+ *
+ * The MLP problem has to be recreated and the problem has to be resolved
+ *
+ * @param mlp the MLP Handle
+ * @param addresses the address hashmap
+ * the address has to be already removed from the hashmap
+ * @param address the address to delete
+ */
+void
+GAS_mlp_address_delete (struct GAS_MLP_Handle *mlp, struct GNUNET_CONTAINER_MultiHashMap * addresses, struct ATS_Address *address);
+
+
+/**
+ * Changes the preferences for a peer in the MLP problem
+ *
+ * @param mlp the MLP Handle
+ * @param peer the peer
+ * @param kind the kind to change the preference
+ * @param score the score
+ */
+void
+GAS_mlp_address_change_preference (struct GAS_MLP_Handle *mlp,
+ const struct GNUNET_PeerIdentity *peer,
+ enum GNUNET_ATS_PreferenceKind kind,
+ float score);
+
+
+/**
+ * Get the preferred address for a specific peer
+ *
+ * @param mlp the MLP Handle
+ * @param addresses address hashmap
+ * @param peer the peer
+ * @return suggested address
+ */
+struct ATS_PreferedAddress *
+GAS_mlp_get_preferred_address (struct GAS_MLP_Handle *mlp,
+ struct GNUNET_CONTAINER_MultiHashMap * addresses,
+ const struct GNUNET_PeerIdentity *peer);
/**
* Shutdown the MLP problem solving component