#include "glpk.h"
#define WRITE_MLP GNUNET_NO
-#define DEBUG_ATS GNUNET_EXTRA_LOGGING
+#define DEBUG_ATS GNUNET_NO
+#define VERBOSE_GLPK GNUNET_NO
/**
* Translate glpk solver error codes to text
return "unknown error";
}
+/**
+ * Translate ATS properties to text
+ * Just intended for debugging
+ *
+ * @param retcode return code
+ * @return string with result
+ */
+const char *
+mlp_ats_to_string (int ats_index)
+{
+ switch (ats_index) {
+ case GNUNET_ATS_ARRAY_TERMINATOR:
+ return "GNUNET_ATS_ARRAY_TERMINATOR";
+ break;
+ case GNUNET_ATS_UTILIZATION_UP:
+ return "GNUNET_ATS_UTILIZATION_UP";
+ break;
+ case GNUNET_ATS_UTILIZATION_DOWN:
+ return "GNUNET_ATS_UTILIZATION_DOWN";
+ break;
+ case GNUNET_ATS_COST_LAN:
+ return "GNUNET_ATS_COST_LAN";
+ break;
+ case GNUNET_ATS_COST_WAN:
+ return "GNUNET_ATS_COST_LAN";
+ break;
+ case GNUNET_ATS_COST_WLAN:
+ return "GNUNET_ATS_COST_WLAN";
+ break;
+ case GNUNET_ATS_NETWORK_TYPE:
+ return "GNUNET_ATS_NETWORK_TYPE";
+ break;
+ case GNUNET_ATS_QUALITY_NET_DELAY:
+ return "GNUNET_ATS_QUALITY_NET_DELAY";
+ break;
+ case GNUNET_ATS_QUALITY_NET_DISTANCE:
+ return "GNUNET_ATS_QUALITY_NET_DISTANCE";
+ break;
+ default:
+ return "unknown";
+ break;
+ }
+ GNUNET_break (0);
+ return "unknown error";
+}
+
/**
* Find a peer in the DLL
* @param the peer to find
return GNUNET_OK;
}
+/**
+ * Find the required ATS information for an address
+ *
+ * @param addr the address
+ * @param ats_index the desired ATS index
+ *
+ * @return the index on success, otherwise GNUNET_SYSERR
+ */
+
+static int
+mlp_lookup_ats (struct ATS_Address *addr, int ats_index)
+{
+ struct GNUNET_ATS_Information * ats = addr->ats;
+ int c;
+ int found = GNUNET_NO;
+ for (c = 0; c < addr->ats_count; c++)
+ {
+ if (ats[c].type == ats_index)
+ {
+ found = GNUNET_YES;
+ break;
+ }
+ }
+ if (found == GNUNET_YES)
+ return c;
+ else
+ return GNUNET_SYSERR;
+}
/**
* Adds the problem constraints for all addresses
mlp_add_constraints_all_addresses (struct GAS_MLP_Handle *mlp, struct GNUNET_CONTAINER_MultiHashMap * addresses)
{
unsigned int n_addresses;
- int row_index;
- //int c;
+ int c;
char *name;
/* Problem matrix*/
*
* c 7) quality
* #rows: |quality properties|
- * #indices:|quality properties| + |n_addresses|
+ * #indices: |n_addresses| + |quality properties|
+ *
+ * c 8) utilization
+ * #rows: 1
+ * #indices: |n_addresses| + 1
+ *
+ * c 9) relativity
+ * #rows: |peers|
+ * #indices: |n_addresses| + |peers|
* */
- int pi = ((7 * n_addresses) + (2 * n_addresses + mlp->m_q + 1));
+ /* last +1 caused by glpk index starting with one */
+ int pi = ((7 * n_addresses) + (4 * n_addresses + mlp->m_q + mlp->c_p + 2) + 1);
mlp->cm_size = pi;
mlp->ci = 1;
*
* c 2) 1 address per peer
* sum (n_p1_1 + ... + n_p1_n) = 1
- */
+ *
+ * c 8) utilization
+ * sum (f_p * b_p1_1 + ... + f_p * b_p1_n) - u = 0
+ *
+ * c 9) relativity
+ * V p : sum (bt_1 + ... +bt_n) - f_p * r = 0
+ * */
- /* Adding rows for c 2) */
- row_index = glp_add_rows (mlp->prob, mlp->c_p);
+ /* Adding rows for c 8) */
+ mlp->r_c8 = glp_add_rows (mlp->prob, mlp->c_p);
+ glp_set_row_name (mlp->prob, mlp->r_c8, "c8");
+ /* Set row bound == 0 */
+ glp_set_row_bnds (mlp->prob, mlp->r_c8, GLP_FX, 0.0, 0.0);
+ /* -u */
+ ia[mlp->ci] = mlp->r_c8;
+ ja[mlp->ci] = mlp->c_u;
+ ar[mlp->ci] = -1;
+ mlp->ci++;
struct ATS_Peer * peer = mlp->peer_head;
while (peer != NULL)
{
struct ATS_Address *addr = peer->head;
struct MLP_information *mlpi = NULL;
- /* Adding row for c 2) */
+
+ /* Adding rows for c 2) */
+ peer->r_c2 = glp_add_rows (mlp->prob, 1);
GNUNET_asprintf(&name, "c2_%s", GNUNET_i2s(&peer->id));
- glp_set_row_name (mlp->prob, row_index, name);
+ glp_set_row_name (mlp->prob, peer->r_c2, name);
GNUNET_free (name);
/* Set row bound == 1 */
- glp_set_row_bnds (mlp->prob, row_index, GLP_FX, 1.0, 1.0);
+ glp_set_row_bnds (mlp->prob, peer->r_c2, GLP_FX, 1.0, 1.0);
+
+ /* Adding rows for c 9) */
+ peer->r_c9 = glp_add_rows (mlp->prob, 1);
+ GNUNET_asprintf(&name, "c9_%s", GNUNET_i2s(&peer->id));
+ glp_set_row_name (mlp->prob, peer->r_c9, name);
+ GNUNET_free (name);
+ /* Set row bound == 0 */
+ glp_set_row_bnds (mlp->prob, peer->r_c9, GLP_LO, 0.0, 0.0);
+
+ /* Set -r */
+ ia[mlp->ci] = peer->r_c9;
+ ja[mlp->ci] = mlp->c_r;
+ ar[mlp->ci] = -1;
+ mlp->ci++;
while (addr != NULL)
{
mlpi = (struct MLP_information *) addr->mlp_information;
- ia[mlp->ci] = row_index;
+
+ ia[mlp->ci] = peer->r_c2;
ja[mlp->ci] = mlpi->c_n;
ar[mlp->ci] = 1;
mlp->ci++;
+
+ ia[mlp->ci] = mlp->r_c8;
+ ja[mlp->ci] = mlpi->c_b;
+ ar[mlp->ci] = peer->f;
+ mlp->ci++;
+
+ ia[mlp->ci] = peer->r_c9;
+ ja[mlp->ci] = mlpi->c_b;
+ ar[mlp->ci] = 1;
+ mlp->ci++;
+
addr = addr->next;
}
peer = peer->next;
}
+ /* c 7) For all quality metrics */
- /* For all quality metrics */
-/*
for (c = 0; c < mlp->m_q; c++)
{
struct ATS_Peer *p = mlp->peer_head;
+ struct ATS_Address *addr = p->head;
+ struct MLP_information * mlpi;
+ double value = 1.0;
+
while (p != NULL)
{
- ia[mlp->ci] = row_index;
+ /* Adding rows for c 7) */
+ mlp->r_q[c] = glp_add_rows (mlp->prob, 1);
+ GNUNET_asprintf(&name, "c7_q%i_atsi_%i", c, mlp->q[c]);
+ glp_set_row_name (mlp->prob, mlp->r_q[c], name);
+ GNUNET_free (name);
+ /* Set row bound == 0 */
+ glp_set_row_bnds (mlp->prob, mlp->r_q[c], GLP_LO, 0.0, 0.0);
+
+ /* Set -q_m */
+ ia[mlp->ci] = mlp->r_q[c];
ja[mlp->ci] = mlp->c_q[c];
- ar[mlp->ci] = mlp->;
+ ar[mlp->ci] = -1;
mlp->ci++;
+ while (addr != NULL)
+ {
+ mlpi = addr->mlp_information;
+ /* lookup ATS information */
+ int index = mlp_lookup_ats(addr, mlp->q[c]);
+
+ if (index != GNUNET_SYSERR)
+ {
+ value = (double) addr->ats[index].value;
+#if DEBUG_ATS
+ GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Quality %i with ATS property `%s' has index %i in addresses ats information has value %f\n", c, mlp_ats_to_string(mlp->q[c]), index, (double) addr->ats[index].value);
+#endif
+ }
+#if DEBUG_ATS
+ else
+ GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Quality %i with ATS property `%s' not existing\n", c, mlp_ats_to_string(mlp->q[c]), index);
+#endif
+ mlpi = addr->mlp_information;
+
+ mlpi->r_q[c] = mlp->r_q[c];
+ mlpi->c_q[c] = mlpi->c_b;
+ mlpi->q[c] = value;
+
+ ia[mlp->ci] = mlp->r_q[c];
+ ja[mlp->ci] = mlpi->c_b;
+ ar[mlp->ci] = p->f * value;
+ mlp->ci++;
+
+ addr = addr->next;
+ }
p = p->next;
}
}
-*/
}
mlp_create_problem (struct GAS_MLP_Handle *mlp, struct GNUNET_CONTAINER_MultiHashMap * addresses)
{
int res = GNUNET_OK;
-
int col;
-/*
int c;
char *name;
-*/
+
GNUNET_assert (mlp->prob == NULL);
/* create the glpk problem */
glp_set_obj_coef (mlp->prob, col, mlp->co_D);
/* Column lower bound = 0.0 */
glp_set_col_bnds (mlp->prob, col, GLP_LO, 0.0, 0.0);
-#if 0
+
/* Utilization u column */
col = glp_add_cols (mlp->prob, 1);
/* Coefficient == Qm */
glp_set_obj_coef (mlp->prob, col + c, mlp->co_Q[c]);
}
-#endif
+
/* Add columns for addresses */
GNUNET_CONTAINER_multihashmap_iterate (addresses, create_columns_it, mlp);
return GNUNET_OK;
}
-int mlp_solve_problem (struct GAS_MLP_Handle *mlp);
+int GAS_mlp_solve_problem (struct GAS_MLP_Handle *mlp);
static void
mlp_scheduler (void *cls, const struct GNUNET_SCHEDULER_TaskContext *tc)
GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Scheduled problem solving\n");
#endif
if (mlp->addr_in_problem != 0)
- mlp_solve_problem(mlp);
+ GAS_mlp_solve_problem(mlp);
}
* @return GNUNET_OK if could be solved, GNUNET_SYSERR on failure
*/
int
-mlp_solve_problem (struct GAS_MLP_Handle *mlp)
+GAS_mlp_solve_problem (struct GAS_MLP_Handle *mlp)
{
int res;
mlp->last_execution = GNUNET_TIME_absolute_get ();
}
#if DEBUG_ATS
- GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Problem solved: %i %s\n", res, mlp_status_to_string(res));
+ GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Problem solved\n");
#endif
/* Process result */
mlp->stats = (struct GNUNET_STATISTICS_Handle *) stats;
mlp->max_iterations = max_iterations;
mlp->max_exec_duration = max_duration;
+ mlp->auto_solve = GNUNET_YES;
/* Redirect GLPK output to GNUnet logging */
glp_error_hook((void *) mlp, &mlp_term_hook);
/* Init LP solving parameters */
glp_init_smcp(&mlp->control_param_lp);
-#if DEBUG_ATS
+#if VERBOSE_GLPK
mlp->control_param_lp.msg_lev = GLP_MSG_ALL;
#else
mlp->control_param_lp.msg_lev = GLP_MSG_OFF;
/* Init MLP solving parameters */
glp_init_iocp(&mlp->control_param_mlp);
-#if DEBUG_ATS
+#if VERBOSE_GLPK
mlp->control_param_mlp.msg_lev = GLP_MSG_ALL;
#else
mlp->control_param_mlp.msg_lev = GLP_MSG_OFF;
return mlp;
}
+
/**
* Updates a single address in the MLP problem
*
{
int new;
struct MLP_information *mlpi;
- int c;
GNUNET_STATISTICS_update (mlp->stats,"# LP address updates", 1, GNUNET_NO);
if (new == GNUNET_YES)
{
mlpi = GNUNET_malloc (sizeof (struct MLP_information));
+
+ int c;
+ for (c = 0; c < GNUNET_ATS_QualityPropertiesCount; c++)
+ {
+ mlpi->c_q[c] = 0;
+ mlpi->r_q[c] = 0;
+ mlpi->q[c] = 0.0;
+ }
+
address->mlp_information = mlpi;
mlp->addr_in_problem ++;
if (peer == NULL)
{
#if DEBUG_ATS
- GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Adding new peer `%s'\n", GNUNET_i2s (&address->peer));
+ GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Adding new peer `%s'\n",
+ GNUNET_i2s (&address->peer));
#endif
peer = GNUNET_malloc (sizeof (struct ATS_Peer));
peer->head = NULL;
peer->tail = NULL;
+ int c;
for (c = 0; c < GNUNET_ATS_QualityPropertiesCount; c++)
{
peer->f_q[c] = 1.0;
}
+ peer->f = 1.0;
memcpy (&peer->id, &address->peer, sizeof (struct GNUNET_PeerIdentity));
GNUNET_assert(address->prev == NULL);
else
{
#if DEBUG_ATS
- GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Adding address to peer `%s'\n", GNUNET_i2s (&address->peer));
+ GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Adding address to peer `%s'\n",
+ GNUNET_i2s (&address->peer));
#endif
GNUNET_CONTAINER_DLL_insert (peer->head, peer->tail, address);
}
else
{
#if DEBUG_ATS
- GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Updating existing address to peer `%s'\n", GNUNET_i2s (&address->peer));
+ GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Updating existing address to peer `%s'\n",
+ GNUNET_i2s (&address->peer));
#endif
+ mlpi = address->mlp_information;
+ int c;
+ for (c = 0; c < GNUNET_ATS_QualityPropertiesCount; c++)
+ {
+ int index = mlp_lookup_ats(address, mlp->q[c]);
+ if ((index != GNUNET_SYSERR) && (mlpi->c_q[c] != 0) && (mlpi->r_q[c] != 0))
+ {
+ if (mlpi->q[c] == (double) address->ats[index].value)
+ break;
+#if DEBUG_ATS
+ GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Updating address for peer `%s' value `%s'from %f to %f\n",
+ GNUNET_i2s (&address->peer),
+ mlp_ats_to_string(mlp->q[c]),
+ mlpi->q[c],
+ (double) address->ats[index].value);
+#endif
+ switch (mlp->q[c])
+ {
+ case GNUNET_ATS_QUALITY_NET_DELAY:
+ mlpi->q[c] = (double) address->ats[index].value;
+ break;
+ case GNUNET_ATS_QUALITY_NET_DISTANCE:
+ mlpi->q[c] = (double) address->ats[index].value;
+ break;
+ default:
+ break;
+ }
+
+ /* Get current number of columns */
+ int cols = glp_get_num_cols(mlp->prob);
+ int *ind = GNUNET_malloc (cols * sizeof (int));
+ double *val = GNUNET_malloc (cols * sizeof (double));
+
+ /* Get the matrix row of quality */
+ cols = glp_get_mat_row(mlp->prob, mlp->r_q[c], ind, val);
+
+ int c2;
+ /* Get the index if matrix row of quality */
+ for (c2 = 1; c2 <= cols; c2++ )
+ {
+#if DEBUG_ATS
+ GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Existing element column %i : %f\n",
+ ind[c2], val[c2]);
+#endif
+ if ((mlpi->c_b == ind[c2]) && (val[c2] != mlpi->q[c]))
+ {
+ /* Update the value */
+ val[c2] = mlpi->q[c];
+#if DEBUG_ATS
+ GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "New element column %i : %f\n",
+ ind[c2], val[c2]);
+#endif
+ }
+ }
+
+ /* Get the index if matrix row of quality */
+ glp_set_mat_row (mlp->prob, mlpi->r_q[c], cols, ind, val);
+
+ GNUNET_free (ind);
+ GNUNET_free (val);
+ }
+ }
}
/* Recalculate */
mlp_create_problem (mlp, addresses);
mlp->presolver_required = GNUNET_YES;
}
- mlp_solve_problem (mlp);
+ if (mlp->auto_solve == GNUNET_YES)
+ GAS_mlp_solve_problem (mlp);
}
/**
/* Recalculate */
mlp->presolver_required = GNUNET_YES;
- mlp_solve_problem (mlp);
+ if (mlp->auto_solve == GNUNET_YES)
+ GAS_mlp_solve_problem (mlp);
}
}
struct ATS_Peer * peer;
struct ATS_Peer * tmp;
+ GNUNET_assert (mlp != NULL);
+
if (mlp->mlp_task != GNUNET_SCHEDULER_NO_TASK)
{
GNUNET_SCHEDULER_cancel(mlp->mlp_task);
}
/* clean up peer list */
- if (mlp != NULL)
+ peer = mlp->peer_head;
+ while (peer != NULL)
{
- peer = mlp->peer_head;
- while (peer != NULL)
- {
- GNUNET_CONTAINER_DLL_remove(mlp->peer_head, mlp->peer_tail, peer);
- tmp = peer->next;
- GNUNET_free (peer);
- peer = tmp;
- }
+ GNUNET_CONTAINER_DLL_remove(mlp->peer_head, mlp->peer_tail, peer);
+ tmp = peer->next;
+ GNUNET_free (peer);
+ peer = tmp;
}
mlp_delete_problem (mlp);
projects / oweals / gnunet.git / blobdiff