GNUnet  0.10.x
plugin_ats_mlp.c
Go to the documentation of this file.
1 /*
2  This file is part of GNUnet.
3  Copyright (C) 2011-2014 GNUnet e.V.
4 
5  GNUnet is free software: you can redistribute it and/or modify it
6  under the terms of the GNU Affero General Public License as published
7  by the Free Software Foundation, either version 3 of the License,
8  or (at your option) any later version.
9 
10  GNUnet is distributed in the hope that it will be useful, but
11  WITHOUT ANY WARRANTY; without even the implied warranty of
12  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13  Affero General Public License for more details.
14 
15  You should have received a copy of the GNU Affero General Public License
16  along with this program. If not, see <http://www.gnu.org/licenses/>.
17 
18  SPDX-License-Identifier: AGPL3.0-or-later
19  */
20 
27 #include "platform.h"
28 #include "gnunet_util_lib.h"
29 #include "gnunet_ats_service.h"
30 #include "gnunet_ats_plugin.h"
33 #include <float.h>
34 #include <glpk.h>
35 
36 
37 #define BIG_M_VALUE (UINT32_MAX) / 10
38 #define BIG_M_STRING "unlimited"
39 
40 #define MLP_AVERAGING_QUEUE_LENGTH 3
41 
42 #define MLP_MAX_EXEC_DURATION GNUNET_TIME_relative_multiply ( \
43  GNUNET_TIME_UNIT_SECONDS, 10)
44 #define MLP_MAX_ITERATIONS 4096
45 
46 #define MLP_DEFAULT_D 1.0
47 #define MLP_DEFAULT_R 1.0
48 #define MLP_DEFAULT_U 1.0
49 #define MLP_DEFAULT_QUALITY 1.0
50 #define MLP_DEFAULT_MIN_CONNECTIONS 4
51 #define MLP_DEFAULT_PEER_PREFERENCE 1.0
52 
53 #define MLP_NaN -1
54 #define MLP_UNDEFINED 0
55 #define GLP_YES 1.0
56 #define GLP_NO 0.0
57 
59 {
63 };
64 
65 
67 {
71 };
72 
73 
74 static const char *
76 {
77  switch (qm)
78  {
80  return "delay";
81 
83  return "distance";
84 
85  default:
86  GNUNET_break (0);
87  return NULL;
88  }
89 }
90 
91 
93 {
94  int lp_res;
96  int mip_res;
98 
101  double mlp_gap;
102  double lp_mlp_gap;
103 
105  int p_cols;
106  int p_rows;
107 
108  int n_peers;
110 };
111 
112 struct ATS_Peer
113 {
115 
116  /* Was this peer already added to the current problem? */
118 
119  /* constraint 2: 1 address per peer*/
120  unsigned int r_c2;
121 
122  /* constraint 9: relativity */
123  unsigned int r_c9;
124 
125  /* Legacy preference value */
126  double f;
127 };
128 
130 {
134  glp_prob *prob;
135 
136  /* Number of addresses in problem */
137  unsigned int num_addresses;
138  /* Number of peers in problem */
139  unsigned int num_peers;
140  /* Number of elements in problem matrix */
141  unsigned int num_elements;
142 
143  /* Row index constraint 2: */
144  unsigned int r_c2;
145  /* Row index constraint 4: minimum connections */
146  unsigned int r_c4;
147  /* Row index constraint 6: maximize diversity */
148  unsigned int r_c6;
149  /* Row index constraint 8: utilization*/
150  unsigned int r_c8;
151  /* Row index constraint 9: relativity*/
152  unsigned int r_c9;
153  /* Row indices quality metrics */
155  /* Row indices ATS network quotas */
156  int r_quota[GNUNET_NT_COUNT];
157 
158  /* Column index Diversity (D) column */
159  int c_d;
160  /* Column index Utilization (U) column */
161  int c_u;
162  /* Column index Proportionality (R) column */
163  int c_r;
164  /* Column index quality metrics */
166 
167  /* Problem matrix */
168  /* Current index */
169  unsigned int ci;
170  /* Row index array */
171  int *ia;
172  /* Column index array */
173  int *ja;
174  /* Column index value */
175  double *ar;
176 };
177 
179 {
180  /* Big M value for bandwidth capping */
181  double BIG_M;
182 
183  /* MIP Gap */
184  double mip_gap;
185 
186  /* LP MIP Gap */
187  double lp_mip_gap;
188 
189  /* Number of quality metrics @deprecated, use RQ_QUALITY_METRIC_COUNT */
190  int m_q;
191 
192  /* Number of quality metrics */
193  int m_rc;
194 
195  /* Quality metric coefficients*/
197 
198  /* Ressource costs coefficients*/
199  double co_RC[RQ_QUALITY_METRIC_COUNT];
200 
201  /* Diversity coefficient */
202  double co_D;
203 
204  /* Utility coefficient */
205  double co_U;
206 
207  /* Relativity coefficient */
208  double co_R;
209 
210  /* Minimum bandwidth assigned to an address */
211  unsigned int b_min;
212 
213  /* Minimum number of addresses with bandwidth assigned */
214  unsigned int n_min;
215 
216  /* Quotas */
217  /* Array mapping array index to ATS network */
218  int quota_index[GNUNET_NT_COUNT];
219  /* Outbound quotas */
220  unsigned long long quota_out[GNUNET_NT_COUNT];
221  /* Inbound quotas */
222 
223  unsigned long long quota_in[GNUNET_NT_COUNT];
224 
225  /* ATS ressource costs
226  * array with GNUNET_ATS_QualityPropertiesCount elements
227  * contains mapping to GNUNET_ATS_Property
228  * */
230 };
231 
236 {
238 
243 
247  struct MLP_Problem p;
248 
252  struct MLP_Variables pv;
253 
257  struct MLP_Solution ps;
258 
263 
268 
273 
278 
283 
288 
293 
300 
305 
310 
315 
320 
325 
330 
335 
340 
345 
350 
355 
360 
361 
365  enum MLP_Output_Format opt_log_format;
366 };
367 
372 {
376  uint32_t b_out;
377 
381  uint32_t b_in;
382 
386  int n;
387 
391  signed int c_b;
392 
396  signed int c_n;
397 
398  /* row indexes */
399 
403  unsigned int r_c1;
404 
408  unsigned int r_c3;
409 };
410 
411 
412 
515 #define LOG(kind, ...) GNUNET_log_from (kind, "ats-mlp", __VA_ARGS__)
516 
520 #define DEBUG_MLP_PROBLEM_CREATION GNUNET_NO
521 
522 
529 static int
530 mlp_term_hook (void *info, const char *s)
531 {
532  struct GAS_MLP_Handle *mlp = info;
533 
534  if (mlp->opt_dbg_glpk_verbose)
535  LOG (GNUNET_ERROR_TYPE_ERROR, "%s", s);
536  return 1;
537 }
538 
539 
548 static int
549 reset_peers (void *cls,
550  const struct GNUNET_PeerIdentity *key,
551  void *value)
552 {
553  struct ATS_Peer *peer = value;
554 
555  peer->processed = GNUNET_NO;
556  return GNUNET_OK;
557 }
558 
564 static void
566 {
567  int c;
568 
569  if (mlp == NULL)
570  return;
571  if (mlp->p.prob != NULL)
572  {
573  glp_delete_prob (mlp->p.prob);
574  mlp->p.prob = NULL;
575  }
576 
577  /* delete row index */
578  if (mlp->p.ia != NULL)
579  {
580  GNUNET_free (mlp->p.ia);
581  mlp->p.ia = NULL;
582  }
583 
584  /* delete column index */
585  if (mlp->p.ja != NULL)
586  {
587  GNUNET_free (mlp->p.ja);
588  mlp->p.ja = NULL;
589  }
590 
591  /* delete coefficients */
592  if (mlp->p.ar != NULL)
593  {
594  GNUNET_free (mlp->p.ar);
595  mlp->p.ar = NULL;
596  }
597  mlp->p.ci = 0;
598  mlp->p.prob = NULL;
599 
600  mlp->p.c_d = MLP_UNDEFINED;
601  mlp->p.c_r = MLP_UNDEFINED;
602  mlp->p.r_c2 = MLP_UNDEFINED;
603  mlp->p.r_c4 = MLP_UNDEFINED;
604  mlp->p.r_c6 = MLP_UNDEFINED;
605  mlp->p.r_c9 = MLP_UNDEFINED;
606  for (c = 0; c < RQ_QUALITY_METRIC_COUNT; c++)
607  mlp->p.r_q[c] = MLP_UNDEFINED;
608  for (c = 0; c < GNUNET_NT_COUNT; c++)
609  mlp->p.r_quota[c] = MLP_UNDEFINED;
610  mlp->p.ci = MLP_UNDEFINED;
611 
612 
614  &reset_peers, NULL);
615 }
616 
617 
623 static const char *
624 mlp_status_to_string (int retcode)
625 {
626  switch (retcode)
627  {
628  case GLP_UNDEF:
629  return "solution is undefined";
630 
631  case GLP_FEAS:
632  return "solution is feasible";
633 
634  case GLP_INFEAS:
635  return "solution is infeasible";
636 
637  case GLP_NOFEAS:
638  return "no feasible solution exists";
639 
640  case GLP_OPT:
641  return "solution is optimal";
642 
643  case GLP_UNBND:
644  return "solution is unbounded";
645 
646  default:
647  GNUNET_break (0);
648  return "unknown error";
649  }
650 }
651 
652 
658 static const char *
659 mlp_solve_to_string (int retcode)
660 {
661  switch (retcode)
662  {
663  case 0:
664  return "ok";
665 
666  case GLP_EBADB:
667  return "invalid basis";
668 
669  case GLP_ESING:
670  return "singular matrix";
671 
672  case GLP_ECOND:
673  return "ill-conditioned matrix";
674 
675  case GLP_EBOUND:
676  return "invalid bounds";
677 
678  case GLP_EFAIL:
679  return "solver failed";
680 
681  case GLP_EOBJLL:
682  return "objective lower limit reached";
683 
684  case GLP_EOBJUL:
685  return "objective upper limit reached";
686 
687  case GLP_EITLIM:
688  return "iteration limit exceeded";
689 
690  case GLP_ETMLIM:
691  return "time limit exceeded";
692 
693  case GLP_ENOPFS:
694  return "no primal feasible solution";
695 
696  case GLP_ENODFS:
697  return "no dual feasible solution";
698 
699  case GLP_EROOT:
700  return "root LP optimum not provided";
701 
702  case GLP_ESTOP:
703  return "search terminated by application";
704 
705  case GLP_EMIPGAP:
706  return "relative mip gap tolerance reached";
707 
708  case GLP_ENOFEAS:
709  return "no dual feasible solution";
710 
711  case GLP_ENOCVG:
712  return "no convergence";
713 
714  case GLP_EINSTAB:
715  return "numerical instability";
716 
717  case GLP_EDATA:
718  return "invalid data";
719 
720  case GLP_ERANGE:
721  return "result out of range";
722 
723  default:
724  GNUNET_break (0);
725  return "unknown error";
726  }
727 }
728 
729 
731 {
733  int result;
734 };
735 
736 static int
738  const struct GNUNET_PeerIdentity *key,
739  void *value)
740 {
741  struct CountContext *cctx = cls;
742 
743  /* Check if we have to add this peer due to a pending request */
745  cctx->result++;
746  return GNUNET_OK;
747 }
748 
749 
750 static int
753  requested_peers,
754  const struct
756 {
757  struct CountContext cctx;
758 
759  cctx.map = requested_peers;
760  cctx.result = 0;
763  &cctx);
764  return cctx.result;
765 }
766 
767 
768 static int
770  const struct GNUNET_PeerIdentity *key,
771  void *value)
772 {
773  struct CountContext *cctx = cls;
774 
775  /* Check if we have to addresses for the requested peer */
777  cctx->result++;
778  return GNUNET_OK;
779 }
780 
781 
782 static int
784  GNUNET_CONTAINER_MultiPeerMap *requested_peers,
785  const struct
787 {
788  struct CountContext cctx;
789 
790  cctx.map = addresses;
791  cctx.result = 0;
792  GNUNET_CONTAINER_multipeermap_iterate (requested_peers,
794  &cctx);
795  return cctx.result;
796 }
797 
798 
812 static int
814  int row, int col, double val,
815  int line)
816 {
817  int c_cols;
818  int c_elems;
819  int c1;
820  int res;
821  int found;
822  double *val_array;
823  int *ind_array;
824 
825  GNUNET_assert (NULL != p->prob);
826 
827  /* Get number of columns and prepare data structure */
828  c_cols = glp_get_num_cols (p->prob);
829  if (0 >= c_cols)
830  return GNUNET_SYSERR;
831 
832  val_array = GNUNET_malloc ((c_cols + 1) * sizeof(double));
833  GNUNET_assert (NULL != val_array);
834  ind_array = GNUNET_malloc ((c_cols + 1) * sizeof(int));
835  GNUNET_assert (NULL != ind_array);
836  /* Extract the row */
837 
838  /* Update the value */
839  c_elems = glp_get_mat_row (p->prob, row, ind_array, val_array);
840  found = GNUNET_NO;
841  for (c1 = 1; c1 < (c_elems + 1); c1++)
842  {
843  if (ind_array[c1] == col)
844  {
845  found = GNUNET_YES;
846  break;
847  }
848  }
849  if (GNUNET_NO == found)
850  {
851  ind_array[c_elems + 1] = col;
852  val_array[c_elems + 1] = val;
853  LOG (GNUNET_ERROR_TYPE_DEBUG, "[P] Setting value in [%s : %s] to `%.2f'\n",
854  glp_get_row_name (p->prob, row), glp_get_col_name (p->prob, col),
855  val);
856  glp_set_mat_row (p->prob, row, c_elems + 1, ind_array, val_array);
857  GNUNET_free (ind_array);
858  GNUNET_free (val_array);
859  return GNUNET_YES;
860  }
861  else
862  {
863  /* Update value */
865  "[P] Updating value in [%s : %s] from `%.2f' to `%.2f'\n",
866  glp_get_row_name (p->prob, row), glp_get_col_name (p->prob, col),
867  val_array[c1], val);
868  if (val != val_array[c1])
869  res = GNUNET_YES;
870  else
871  res = GNUNET_NO;
872  val_array[c1] = val;
873  /* Update the row in the matrix */
874  glp_set_mat_row (p->prob, row, c_elems, ind_array, val_array);
875  }
876 
877  GNUNET_free (ind_array);
878  GNUNET_free (val_array);
879  return res;
880 }
881 
894 static void
896  int row, int col, double val,
897  int line)
898 {
899  if ((p->ci) >= p->num_elements)
900  {
902  "[P]: line %u: Request for index %u bigger than array size of %u\n",
903  line, p->ci + 1, p->num_elements);
904  GNUNET_break (0);
905  return;
906  }
907  if ((0 == row) || (0 == col))
908  {
909  GNUNET_break (0);
911  "[P]: Invalid call from line %u: row = %u, col = %u\n",
912  line, row, col);
913  }
914  p->ia[p->ci] = row;
915  p->ja[p->ci] = col;
916  p->ar[p->ci] = val;
917 #if DEBUG_MLP_PROBLEM_CREATION
919  "[P]: line %u: Set value [%u,%u] in index %u == %.2f\n",
920  line, p->ia[p->ci], p->ja[p->ci], p->ci, p->ar[p->ci]);
921 #endif
922  p->ci++;
923 }
924 
925 static int
927  unsigned int type, unsigned int bound, double
928  lb, double ub,
929  double coef)
930 {
931  int col = glp_add_cols (p->prob, 1);
932 
933  glp_set_col_name (p->prob, col, name);
934  glp_set_col_bnds (p->prob, col, bound, lb, ub);
935  glp_set_col_kind (p->prob, col, type);
936  glp_set_obj_coef (p->prob, col, coef);
937 #if DEBUG_MLP_PROBLEM_CREATION
938  LOG (GNUNET_ERROR_TYPE_DEBUG, "[P]: Added column [%u] `%s': %.2f\n",
939  col, name, coef);
940 #endif
941  return col;
942 }
943 
944 static int
946  unsigned int bound, double lb, double ub)
947 {
948  char *op;
949  int row = glp_add_rows (p->prob, 1);
950 
951  /* set row name */
952  glp_set_row_name (p->prob, row, name);
953  /* set row bounds: <= 0 */
954  glp_set_row_bnds (p->prob, row, bound, lb, ub);
955  switch (bound)
956  {
957  case GLP_UP:
958  GNUNET_asprintf (&op, "-inf <= x <= %.2f", ub);
959  break;
960 
961  case GLP_DB:
962  GNUNET_asprintf (&op, "%.2f <= x <= %.2f", lb, ub);
963  break;
964 
965  case GLP_FX:
966  GNUNET_asprintf (&op, "%.2f == x == %.2f", lb, ub);
967  break;
968 
969  case GLP_LO:
970  GNUNET_asprintf (&op, "%.2f <= x <= inf", lb);
971  break;
972 
973  default:
974  GNUNET_asprintf (&op, "ERROR");
975  break;
976  }
977 #if DEBUG_MLP_PROBLEM_CREATION
978  LOG (GNUNET_ERROR_TYPE_DEBUG, "[P]: Added row [%u] `%s': %s\n",
979  row, name, op);
980 #endif
981  GNUNET_free (op);
982  return row;
983 }
984 
992 static int
994  const struct
996  void *value)
997 {
998  struct GAS_MLP_Handle *mlp = cls;
999  struct MLP_Problem *p = &mlp->p;
1000  struct ATS_Address *address = value;
1001  struct ATS_Peer *peer;
1002  struct MLP_information *mlpi;
1003  char *name;
1004  double cur_bigm;
1005  uint32_t addr_net;
1006  uint32_t addr_net_index;
1007  unsigned long long max_quota;
1008  int c;
1009 
1010  /* Check if we have to add this peer due to a pending request */
1012  key))
1013  return GNUNET_OK;
1014 
1015  mlpi = address->solver_information;
1016  if (NULL == mlpi)
1017  {
1018  fprintf (stderr, "%s %p\n", GNUNET_i2s (&address->peer), address);
1019  GNUNET_break (0);
1020  return GNUNET_OK;
1021  }
1022 
1023  addr_net = address->properties.scope;
1024  for (addr_net_index = 0; addr_net_index < GNUNET_NT_COUNT; addr_net_index++)
1025  {
1026  if (mlp->pv.quota_index[addr_net_index] == addr_net)
1027  break;
1028  }
1029 
1030  if (addr_net_index >= GNUNET_NT_COUNT)
1031  {
1032  GNUNET_break (0);
1033  return GNUNET_OK;
1034  }
1035 
1036  max_quota = 0;
1037  for (c = 0; c < GNUNET_NT_COUNT; c++)
1038  {
1039  if (mlp->pv.quota_out[c] > max_quota)
1040  max_quota = mlp->pv.quota_out[c];
1041  if (mlp->pv.quota_in[c] > max_quota)
1042  max_quota = mlp->pv.quota_in[c];
1043  }
1044  if (max_quota > mlp->pv.BIG_M)
1045  cur_bigm = (double) mlp->pv.BIG_M;
1046  else
1047  cur_bigm = max_quota;
1048 
1049 
1050  /* Get peer */
1052  GNUNET_assert (NULL != peer);
1053  if (peer->processed == GNUNET_NO)
1054  {
1055  /* Add peer dependent constraints */
1056  /* Add c2) One address active per peer */
1057  GNUNET_asprintf (&name, "c2_%s", GNUNET_i2s (&address->peer));
1058  peer->r_c2 = mlp_create_problem_create_constraint (p, name, GLP_FX, 1.0,
1059  1.0);
1060  GNUNET_free (name);
1061  if (GNUNET_NO == mlp->opt_dbg_feasibility_only)
1062  {
1064  {
1065  /* Add c9) Relativity */
1066  GNUNET_asprintf (&name, "c9_%s", GNUNET_i2s (&address->peer));
1067  peer->r_c9 = mlp_create_problem_create_constraint (p, name, GLP_LO, 0.0,
1068  0.0);
1069  GNUNET_free (name);
1070  /* c9) set coefficient */
1071  mlp_create_problem_set_value (p, peer->r_c9, p->c_r, -peer->f,
1072  __LINE__);
1073  }
1074  }
1075  peer->processed = GNUNET_YES;
1076  }
1077 
1078  /* Reset addresses' solver information */
1079  mlpi->c_b = 0;
1080  mlpi->c_n = 0;
1081  mlpi->n = 0;
1082  mlpi->r_c1 = 0;
1083  mlpi->r_c3 = 0;
1084 
1085  /* Add bandwidth column */
1086  GNUNET_asprintf (&name, "b_%s_%s_%p", GNUNET_i2s (&address->peer),
1087  address->plugin, address);
1088  if (GNUNET_NO == mlp->opt_dbg_feasibility_only)
1089  {
1090  mlpi->c_b = mlp_create_problem_create_column (p, name, GLP_CV, GLP_LO, 0.0,
1091  0.0, 0.0);
1092  }
1093  else
1094  {
1095  /* Maximize for bandwidth assignment in feasibility testing */
1096  mlpi->c_b = mlp_create_problem_create_column (p, name, GLP_CV, GLP_LO, 0.0,
1097  0.0, 1.0);
1098  }
1099  GNUNET_free (name);
1100 
1101  /* Add address active column */
1102  GNUNET_asprintf (&name, "n_%s_%s_%p", GNUNET_i2s (&address->peer),
1103  address->plugin, address);
1104  mlpi->c_n = mlp_create_problem_create_column (p, name, GLP_IV, GLP_DB, 0.0,
1105  1.0, 0.0);
1106  GNUNET_free (name);
1107 
1108  /* Add address dependent constraints */
1109  /* Add c1) bandwidth capping: b_t + (-M) * n_t <= 0 */
1110  GNUNET_asprintf (&name, "c1_%s_%s_%p", GNUNET_i2s (&address->peer),
1111  address->plugin, address);
1112  mlpi->r_c1 = mlp_create_problem_create_constraint (p, name, GLP_UP, 0.0, 0.0);
1113  GNUNET_free (name);
1114  /* c1) set b = 1 coefficient */
1115  mlp_create_problem_set_value (p, mlpi->r_c1, mlpi->c_b, 1, __LINE__);
1116  /* c1) set n = - min (M, quota) coefficient */
1117  cur_bigm = (double) mlp->pv.quota_out[addr_net_index];
1118  if (cur_bigm > mlp->pv.BIG_M)
1119  cur_bigm = (double) mlp->pv.BIG_M;
1120  mlp_create_problem_set_value (p, mlpi->r_c1, mlpi->c_n, -cur_bigm, __LINE__);
1121 
1122  /* Add constraint c 3) minimum bandwidth
1123  * b_t + (-n_t * b_min) >= 0
1124  * */
1125  GNUNET_asprintf (&name, "c3_%s_%s_%p", GNUNET_i2s (&address->peer),
1126  address->plugin, address);
1127  mlpi->r_c3 = mlp_create_problem_create_constraint (p, name, GLP_LO, 0.0, 0.0);
1128  GNUNET_free (name);
1129 
1130  /* c3) set b = 1 coefficient */
1131  mlp_create_problem_set_value (p, mlpi->r_c3, mlpi->c_b, 1, __LINE__);
1132  /* c3) set n = -b_min coefficient */
1133  mlp_create_problem_set_value (p, mlpi->r_c3, mlpi->c_n,
1134  -((double ) mlp->pv.b_min), __LINE__);
1135 
1136 
1137  /* Set coefficient entries in invariant rows */
1138 
1139  /* Feasbility */
1140 
1141  /* c 4) minimum connections */
1142  mlp_create_problem_set_value (p, p->r_c4, mlpi->c_n, 1, __LINE__);
1143  /* c 2) 1 address peer peer */
1144  mlp_create_problem_set_value (p, peer->r_c2, mlpi->c_n, 1, __LINE__);
1145  /* c 10) obey network specific quotas
1146  * (1)*b_1 + ... + (1)*b_m <= quota_n
1147  */
1148  mlp_create_problem_set_value (p, p->r_quota[addr_net_index], mlpi->c_b, 1,
1149  __LINE__);
1150 
1151  /* Optimality */
1152  if (GNUNET_NO == mlp->opt_dbg_feasibility_only)
1153  {
1154  /* c 6) maximize diversity */
1155  mlp_create_problem_set_value (p, p->r_c6, mlpi->c_n, 1, __LINE__);
1156  /* c 9) relativity */
1158  mlp_create_problem_set_value (p, peer->r_c9, mlpi->c_b, 1, __LINE__);
1159  /* c 8) utility */
1161  mlp_create_problem_set_value (p, p->r_c8, mlpi->c_b, 1, __LINE__);
1162  /* c 7) Optimize quality */
1163  /* For all quality metrics, set quality of this address */
1165  {
1168  mlpi->c_b,
1169  address->norm_delay.norm,
1170  __LINE__);
1173  mlpi->c_b,
1174  address->norm_distance.norm,
1175  __LINE__);
1176  }
1177  }
1178 
1179  return GNUNET_OK;
1180 }
1181 
1182 
1186 static void
1188  MLP_Problem *p)
1189 {
1190  int c;
1191 
1192  /* Feasibility */
1193 
1194  /* Row for c4) minimum connection */
1195  /* Number of minimum connections is min(|Peers|, n_min) */
1196  p->r_c4 = mlp_create_problem_create_constraint (p, "c4", GLP_LO,
1197  (mlp->pv.n_min >
1198  p->num_peers) ?
1199  p->num_peers : mlp->pv.n_min,
1200  0.0);
1201 
1202  /* Rows for c 10) Enforce network quotas */
1203  for (c = 0; c < GNUNET_NT_COUNT; c++)
1204  {
1205  char *text;
1206  GNUNET_asprintf (&text, "c10_quota_ats_%s",
1207  GNUNET_NT_to_string (mlp->pv.quota_index[c]));
1208  p->r_quota[c] = mlp_create_problem_create_constraint (p, text, GLP_DB, 0.0,
1209  mlp->pv.quota_out[c]);
1210  GNUNET_free (text);
1211  }
1212 
1213  /* Optimality */
1214  if (GNUNET_NO == mlp->opt_dbg_feasibility_only)
1215  {
1216  char *name;
1217  /* Add row for c6) Maximize for diversity */
1219  {
1220  p->r_c6 = mlp_create_problem_create_constraint (p, "c6", GLP_FX, 0.0,
1221  0.0);
1222  /* Set c6 ) Setting -D */
1223  mlp_create_problem_set_value (p, p->r_c6, p->c_d, -1, __LINE__);
1224  }
1225 
1226  /* Adding rows for c 8) Maximize utility */
1228  {
1229  p->r_c8 = mlp_create_problem_create_constraint (p, "c8", GLP_FX, 0.0,
1230  0.0);
1231  /* -u */
1232  mlp_create_problem_set_value (p, p->r_c8, p->c_u, -1, __LINE__);
1233  }
1234 
1235  /* For all quality metrics:
1236  * c 7) Maximize quality, austerity */
1238  {
1239  for (c = 0; c < mlp->pv.m_q; c++)
1240  {
1241  GNUNET_asprintf (&name,
1242  "c7_q%i_%s", c,
1243  print_quality_type (c));
1244  p->r_q[c] = mlp_create_problem_create_constraint (p, name, GLP_FX, 0.0,
1245  0.0);
1246  GNUNET_free (name);
1248  p->r_q[c],
1249  p->c_q[c], -1, __LINE__);
1250  }
1251  }
1252  }
1253 }
1254 
1255 
1259 static void
1261  MLP_Problem *p)
1262 {
1263  if (GNUNET_NO == mlp->opt_dbg_feasibility_only)
1264  {
1265  char *name;
1266  int c;
1267 
1268  /* Diversity d column */
1270  p->c_d = mlp_create_problem_create_column (p, "d", GLP_CV, GLP_LO, 0.0,
1271  0.0, mlp->pv.co_D);
1272 
1273  /* Utilization u column */
1275  p->c_u = mlp_create_problem_create_column (p, "u", GLP_CV, GLP_LO, 0.0,
1276  0.0, mlp->pv.co_U);
1277 
1278  /* Relativity r column */
1280  p->c_r = mlp_create_problem_create_column (p, "r", GLP_CV, GLP_LO, 0.0,
1281  0.0, mlp->pv.co_R);
1282 
1283  /* Quality metric columns */
1285  {
1286  for (c = 0; c < mlp->pv.m_q; c++)
1287  {
1288  GNUNET_asprintf (&name, "q_%u", c);
1289  p->c_q[c] = mlp_create_problem_create_column (p, name, GLP_CV, GLP_LO,
1290  0.0, 0.0,
1291  mlp->pv.co_Q[c]);
1292  GNUNET_free (name);
1293  }
1294  }
1295  }
1296 }
1297 
1298 
1305 static int
1307 {
1308  struct MLP_Problem *p = &mlp->p;
1309  int res = GNUNET_OK;
1310 
1311  GNUNET_assert (p->prob == NULL);
1312  GNUNET_assert (p->ia == NULL);
1313  GNUNET_assert (p->ja == NULL);
1314  GNUNET_assert (p->ar == NULL);
1315  /* Reset MLP problem struct */
1316 
1317  /* create the glpk problem */
1318  p->prob = glp_create_prob ();
1319  GNUNET_assert (NULL != p->prob);
1321  mlp->env->addresses);
1323  mlp->env->addresses);
1324 
1325  /* Create problem matrix: 10 * #addresses + #q * #addresses + #q, + #peer + 2 + 1 */
1326  p->num_elements = (10 * p->num_addresses + mlp->pv.m_q * p->num_addresses
1327  + mlp->pv.m_q + p->num_peers + 2 + 1);
1329  "Rebuilding problem for %u peer(s) and %u addresse(s) and %u quality metrics == %u elements\n",
1330  p->num_peers,
1331  p->num_addresses,
1332  mlp->pv.m_q,
1333  p->num_elements);
1334 
1335  /* Set a problem name */
1336  glp_set_prob_name (p->prob, "GNUnet ATS bandwidth distribution");
1337  /* Set optimization direction to maximize */
1338  glp_set_obj_dir (p->prob, GLP_MAX);
1339 
1340  /* Create problem matrix */
1341  /* last +1 caused by glpk index starting with one: [1..elements]*/
1342  p->ci = 1;
1343  /* row index */
1344  p->ia = GNUNET_malloc (p->num_elements * sizeof(int));
1345  /* column index */
1346  p->ja = GNUNET_malloc (p->num_elements * sizeof(int));
1347  /* coefficient */
1348  p->ar = GNUNET_malloc (p->num_elements * sizeof(double));
1349 
1350  if ((NULL == p->ia) || (NULL == p->ja) || (NULL == p->ar))
1351  {
1353  "Problem size too large, cannot allocate memory!\n"));
1354  return GNUNET_SYSERR;
1355  }
1356 
1357  /* Adding invariant columns */
1359 
1360  /* Adding address independent constraint rows */
1362 
1363  /* Adding address dependent columns constraint rows */
1365  &
1367  mlp);
1368 
1369  /* Load the matrix */
1370  LOG (GNUNET_ERROR_TYPE_DEBUG, "Loading matrix\n");
1371  glp_load_matrix (p->prob, (p->ci) - 1, p->ia, p->ja, p->ar);
1373  {
1374  glp_scale_prob (p->prob, GLP_SF_AUTO);
1375  }
1376 
1377  return res;
1378 }
1379 
1380 
1387 static int
1389 {
1390  int res = 0;
1391  int res_status = 0;
1392 
1393  res = glp_simplex (mlp->p.prob, &mlp->control_param_lp);
1394  if (0 == res)
1395  LOG (GNUNET_ERROR_TYPE_DEBUG, "Solving LP problem: %s\n",
1396  mlp_solve_to_string (res));
1397  else
1398  LOG (GNUNET_ERROR_TYPE_DEBUG, "Solving LP problem failed: %s\n",
1399  mlp_solve_to_string (res));
1400 
1401  /* Analyze problem status */
1402  res_status = glp_get_status (mlp->p.prob);
1403  switch (res_status)
1404  {
1405  case GLP_OPT: /* solution is optimal */
1407  "Solving LP problem: %s, %s\n",
1408  mlp_solve_to_string (res),
1409  mlp_status_to_string (res_status));
1410  return GNUNET_OK;
1411 
1412  default:
1414  "Solving LP problem failed: %s %s\n",
1415  mlp_solve_to_string (res),
1416  mlp_status_to_string (res_status));
1417  return GNUNET_SYSERR;
1418  }
1419 }
1420 
1421 
1430 static int
1432  const struct GNUNET_PeerIdentity *key,
1433  void *value)
1434 {
1435  struct GAS_MLP_Handle *mlp = cls;
1436  struct ATS_Address *address;
1437  struct MLP_information *mlpi;
1438  double mlp_bw_in = MLP_NaN;
1439  double mlp_bw_out = MLP_NaN;
1440  double mlp_use = MLP_NaN;
1441 
1442  /* Check if we have to add this peer due to a pending request */
1444  key))
1445  {
1446  return GNUNET_OK;
1447  }
1448  address = value;
1449  GNUNET_assert (address->solver_information != NULL);
1450  mlpi = address->solver_information;
1451 
1452  mlp_bw_in = glp_mip_col_val (mlp->p.prob, mlpi->c_b);/* FIXME */
1453  if (mlp_bw_in > (double) UINT32_MAX)
1454  {
1456  "Overflow in assigned bandwidth, reducing ...\n");
1457  mlp_bw_in = (double) UINT32_MAX;
1458  }
1459  mlp_bw_out = glp_mip_col_val (mlp->p.prob, mlpi->c_b);
1460  if (mlp_bw_out > (double) UINT32_MAX)
1461  {
1463  "Overflow in assigned bandwidth, reducing ...\n");
1464  mlp_bw_out = (double) UINT32_MAX;
1465  }
1466  mlp_use = glp_mip_col_val (mlp->p.prob, mlpi->c_n);
1467 
1468  /*
1469  * Debug: solution
1470  * LOG (GNUNET_ERROR_TYPE_INFO, "MLP result address: `%s' `%s' length %u session %u, mlp use %.3f\n",
1471  * GNUNET_i2s(&address->peer), address->plugin,
1472  * address->addr_len, address->session_id);
1473  */
1474 
1475  if (GLP_YES == mlp_use)
1476  {
1477  /* This address was selected by the solver to be used */
1478  mlpi->n = GNUNET_YES;
1479  if (GNUNET_NO == address->active)
1480  {
1481  /* Address was not used before, enabling address */
1482  LOG (GNUNET_ERROR_TYPE_DEBUG, "%s %.2f : enabling address\n",
1483  (1 == mlp_use) ? "[x]" : "[ ]", mlp_bw_out);
1484  address->active = GNUNET_YES;
1485  address->assigned_bw_in = mlp_bw_in;
1486  mlpi->b_in = mlp_bw_in;
1487  address->assigned_bw_out = mlp_bw_out;
1488  mlpi->b_out = mlp_bw_out;
1489  if ((NULL == mlp->exclude_peer) || (0 != GNUNET_memcmp (&address->peer,
1490  mlp->exclude_peer)))
1491  mlp->env->bandwidth_changed_cb (mlp->env->cls, address);
1492  return GNUNET_OK;
1493  }
1494  else if (GNUNET_YES == address->active)
1495  {
1496  /* Address was used before, check for bandwidth change */
1497  if ((mlp_bw_out != address->assigned_bw_out) ||
1498  (mlp_bw_in != address->assigned_bw_in))
1499  {
1500  LOG (GNUNET_ERROR_TYPE_DEBUG, "%s %.2f : bandwidth changed\n",
1501  (1 == mlp_use) ? "[x]" : "[ ]", mlp_bw_out);
1502  address->assigned_bw_in = mlp_bw_in;
1503  mlpi->b_in = mlp_bw_in;
1504  address->assigned_bw_out = mlp_bw_out;
1505  mlpi->b_out = mlp_bw_out;
1506  if ((NULL == mlp->exclude_peer) || (0 != GNUNET_memcmp (&address->peer,
1507  mlp->
1508  exclude_peer)))
1509  mlp->env->bandwidth_changed_cb (mlp->env->cls, address);
1510  return GNUNET_OK;
1511  }
1512  }
1513  else
1514  GNUNET_break (0);
1515  }
1516  else if (GLP_NO == mlp_use)
1517  {
1518  /* This address was selected by the solver to be not used */
1519  mlpi->n = GNUNET_NO;
1520  if (GNUNET_NO == address->active)
1521  {
1522  /* Address was not used before, nothing to do */
1523  LOG (GNUNET_ERROR_TYPE_DEBUG, "%s %.2f : no change\n",
1524  (1 == mlp_use) ? "[x]" : "[ ]", mlp_bw_out);
1525  return GNUNET_OK;
1526  }
1527  else if (GNUNET_YES == address->active)
1528  {
1529  /* Address was used before, disabling address */
1530  LOG (GNUNET_ERROR_TYPE_DEBUG, "%s %.2f : disabling address\n",
1531  (1 == mlp_use) ? "[x]" : "[ ]", mlp_bw_out);
1532  address->active = GNUNET_NO;
1533  /* Set bandwidth to 0 */
1534  address->assigned_bw_in = 0;
1535  mlpi->b_in = 0;
1536  address->assigned_bw_out = 0;
1537  mlpi->b_out = 0;
1538  return GNUNET_OK;
1539  }
1540  else
1541  GNUNET_break (0);
1542  }
1543  else
1544  GNUNET_break (0);
1545 
1546  return GNUNET_OK;
1547 }
1548 
1549 
1550 static void
1551 notify (struct GAS_MLP_Handle *mlp,
1552  enum GAS_Solver_Operation op,
1553  enum GAS_Solver_Status stat,
1555 {
1556  mlp->env->info_cb (mlp->env->cls,
1557  op,
1558  stat,
1559  add);
1560 }
1561 
1562 
1563 static void
1564 mlp_branch_and_cut_cb (glp_tree *tree, void *info)
1565 {
1566  struct GAS_MLP_Handle *mlp = info;
1567  double mlp_obj = 0;
1568 
1569  switch (glp_ios_reason (tree))
1570  {
1571  case GLP_ISELECT:
1572  /* Do nothing here */
1573  break;
1574 
1575  case GLP_IPREPRO:
1576  /* Do nothing here */
1577  break;
1578 
1579  case GLP_IROWGEN:
1580  /* Do nothing here */
1581  break;
1582 
1583  case GLP_IHEUR:
1584  /* Do nothing here */
1585  break;
1586 
1587  case GLP_ICUTGEN:
1588  /* Do nothing here */
1589  break;
1590 
1591  case GLP_IBRANCH:
1592  /* Do nothing here */
1593  break;
1594 
1595  case GLP_IBINGO:
1596  /* A better solution was found */
1597  mlp->ps.mlp_gap = glp_ios_mip_gap (tree);
1598  mlp_obj = glp_mip_obj_val (mlp->p.prob);
1599  mlp->ps.lp_mlp_gap = (abs (mlp_obj - mlp->ps.lp_objective_value)) / (abs (
1600  mlp_obj)
1601  +
1602  DBL_EPSILON);
1603 
1605  "Found better integer solution, current gaps: %.3f <= %.3f, %.3f <= %.3f\n",
1606  mlp->ps.mlp_gap, mlp->pv.mip_gap,
1607  mlp->ps.lp_mlp_gap, mlp->pv.lp_mip_gap);
1608 
1609  if (mlp->ps.mlp_gap <= mlp->pv.mip_gap)
1610  {
1612  "Current LP/MLP gap of %.3f smaller than tolerated gap of %.3f, terminating search\n",
1613  mlp->ps.lp_mlp_gap, mlp->pv.lp_mip_gap);
1614  glp_ios_terminate (tree);
1615  }
1616 
1617  if (mlp->ps.lp_mlp_gap <= mlp->pv.lp_mip_gap)
1618  {
1620  "Current LP/MLP gap of %.3f smaller than tolerated gap of %.3f, terminating search\n",
1621  mlp->ps.lp_mlp_gap, mlp->pv.lp_mip_gap);
1622  glp_ios_terminate (tree);
1623  }
1624 
1625  break;
1626 
1627  default:
1628  break;
1629  }
1630  // GNUNET_break (0);
1631 }
1632 
1633 
1640 static int
1642 {
1643  struct GAS_MLP_Handle *mlp = solver;
1644  char *filename;
1645  int res_lp = 0;
1646  int mip_res = 0;
1647  int mip_status = 0;
1648 
1649  struct GNUNET_TIME_Absolute start_total;
1650  struct GNUNET_TIME_Absolute start_cur_op;
1651  struct GNUNET_TIME_Relative dur_total;
1652  struct GNUNET_TIME_Relative dur_setup;
1653  struct GNUNET_TIME_Relative dur_lp;
1654  struct GNUNET_TIME_Relative dur_mlp;
1655 
1656  GNUNET_assert (NULL != solver);
1657  dur_lp = GNUNET_TIME_UNIT_ZERO;
1658 
1659  if (GNUNET_YES == mlp->stat_bulk_lock)
1660  {
1661  mlp->stat_bulk_requests++;
1662  return GNUNET_NO;
1663  }
1667  start_total = GNUNET_TIME_absolute_get ();
1668 
1670  {
1672  return GNUNET_OK; /* No pending requests */
1673  }
1675  {
1677  return GNUNET_OK; /* No addresses available */
1678  }
1679 
1680  if ((GNUNET_NO == mlp->stat_mlp_prob_changed)
1681  && (GNUNET_NO == mlp->stat_mlp_prob_updated))
1682  {
1683  LOG (GNUNET_ERROR_TYPE_DEBUG, "No changes to problem\n");
1685  return GNUNET_OK;
1686  }
1687  if (GNUNET_YES == mlp->stat_mlp_prob_changed)
1688  {
1689  LOG (GNUNET_ERROR_TYPE_DEBUG, "Problem size changed, rebuilding\n");
1691  mlp_delete_problem (mlp);
1692  if (GNUNET_SYSERR == mlp_create_problem (mlp))
1693  {
1695  return GNUNET_SYSERR;
1696  }
1698  if (GNUNET_NO == mlp->opt_dbg_intopt_presolver)
1699  {
1700  mlp->control_param_lp.presolve = GLP_YES; /* LP presolver, we need lp solution */
1701  mlp->control_param_mlp.presolve = GNUNET_NO; /* No presolver, we have LP solution */
1702  }
1703  else
1704  {
1705  mlp->control_param_lp.presolve = GNUNET_NO; /* LP presolver, we need lp solution */
1706  mlp->control_param_mlp.presolve = GLP_YES; /* No presolver, we have LP solution */
1707  dur_lp = GNUNET_TIME_UNIT_ZERO;
1708  }
1709  }
1710  else
1711  {
1712  LOG (GNUNET_ERROR_TYPE_DEBUG, "Problem was updated, resolving\n");
1713  }
1714 
1715  /* Reset solution info */
1716  mlp->ps.lp_objective_value = 0.0;
1717  mlp->ps.mlp_gap = 1.0;
1718  mlp->ps.mlp_objective_value = 0.0;
1719  mlp->ps.lp_mlp_gap = 0.0;
1720 
1721  dur_setup = GNUNET_TIME_absolute_get_duration (start_total);
1722 
1723  /* Run LP solver */
1724  if (GNUNET_NO == mlp->opt_dbg_intopt_presolver)
1725  {
1728  GAS_INFO_UPDATED);
1730  "Running LP solver %s\n",
1731  (GLP_YES == mlp->control_param_lp.presolve) ? "with presolver" :
1732  "without presolver");
1733  start_cur_op = GNUNET_TIME_absolute_get ();
1734 
1735  /* Solve LP */
1736  /* Only for debugging:
1737  * Always use LP presolver:
1738  * mlp->control_param_lp.presolve = GLP_YES; */
1739  res_lp = mlp_solve_lp_problem (mlp);
1740  if (GNUNET_OK == res_lp)
1741  {
1742  mlp->ps.lp_objective_value = glp_get_obj_val (mlp->p.prob);
1744  "LP solution was: %.3f\n",
1745  mlp->ps.lp_objective_value);
1746  }
1747 
1748  dur_lp = GNUNET_TIME_absolute_get_duration (start_cur_op);
1750  (GNUNET_OK == res_lp) ? GAS_STAT_SUCCESS : GAS_STAT_FAIL,
1752  GAS_INFO_UPDATED);
1753  }
1754 
1756  res_lp = GNUNET_OK;
1757 
1758  /* Run MLP solver */
1759  if ((GNUNET_OK == res_lp) || (GNUNET_YES == mlp->opt_dbg_intopt_presolver))
1760  {
1761  LOG (GNUNET_ERROR_TYPE_DEBUG, "Running MLP solver \n");
1764  GAS_INFO_UPDATED);
1765  start_cur_op = GNUNET_TIME_absolute_get ();
1766 
1767  /* Solve MIP */
1768 
1769  /* Only for debugging, always use LP presolver */
1771  mlp->control_param_mlp.presolve = GNUNET_YES;
1772 
1773  mip_res = glp_intopt (mlp->p.prob, &mlp->control_param_mlp);
1774  switch (mip_res)
1775  {
1776  case 0:
1777  /* Successful */
1779  "Solving MLP problem: %s\n",
1780  mlp_solve_to_string (mip_res));
1781  break;
1782 
1783  case GLP_ETMLIM: /* Time limit reached */
1784  case GLP_EMIPGAP: /* MIP gap tolerance limit reached */
1785  case GLP_ESTOP: /* Solver was instructed to stop*/
1786  /* Semi-successful */
1788  "Solving MLP problem solution was interupted: %s\n",
1789  mlp_solve_to_string (mip_res));
1790  break;
1791 
1792  case GLP_EBOUND:
1793  case GLP_EROOT:
1794  case GLP_ENOPFS:
1795  case GLP_ENODFS:
1796  case GLP_EFAIL:
1797  default:
1798  /* Fail */
1800  "Solving MLP problem failed: %s\n",
1801  mlp_solve_to_string (mip_res));
1802  break;
1803  }
1804 
1805  /* Analyze problem status */
1806  mip_status = glp_mip_status (mlp->p.prob);
1807  switch (mip_status)
1808  {
1809  case GLP_OPT: /* solution is optimal */
1811  "Solution of MLP problem is optimal: %s, %s\n",
1812  mlp_solve_to_string (mip_res),
1813  mlp_status_to_string (mip_status));
1814  mip_res = GNUNET_OK;
1815  break;
1816 
1817  case GLP_FEAS: /* solution is feasible but not proven optimal */
1818 
1819  if ((mlp->ps.mlp_gap <= mlp->pv.mip_gap) ||
1820  (mlp->ps.lp_mlp_gap <= mlp->pv.lp_mip_gap))
1821  {
1823  "Solution of MLP problem is feasible and solution within gap constraints: %s, %s\n",
1824  mlp_solve_to_string (mip_res),
1825  mlp_status_to_string (mip_status));
1826  mip_res = GNUNET_OK;
1827  }
1828  else
1829  {
1831  "Solution of MLP problem is feasible but solution not within gap constraints: %s, %s\n",
1832  mlp_solve_to_string (mip_res),
1833  mlp_status_to_string (mip_status));
1834  mip_res = GNUNET_SYSERR;
1835  }
1836  break;
1837 
1838  case GLP_UNDEF: /* Solution undefined */
1839  case GLP_NOFEAS: /* No feasible solution */
1840  default:
1842  "Solving MLP problem failed: %s %s\n",
1843  mlp_solve_to_string (mip_res),
1844  mlp_status_to_string (mip_status));
1845  mip_res = GNUNET_SYSERR;
1846  break;
1847  }
1848 
1849  dur_mlp = GNUNET_TIME_absolute_get_duration (start_cur_op);
1850  dur_total = GNUNET_TIME_absolute_get_duration (start_total);
1851 
1853  (GNUNET_OK == mip_res) ? GAS_STAT_SUCCESS : GAS_STAT_FAIL,
1855  GAS_INFO_UPDATED);
1856  }
1857  else
1858  {
1859  /* Do not execute mip solver since lp solution is invalid */
1860  dur_mlp = GNUNET_TIME_UNIT_ZERO;
1861  dur_total = GNUNET_TIME_absolute_get_duration (start_total);
1862 
1865  GAS_INFO_UPDATED);
1866  mip_res = GNUNET_SYSERR;
1867  }
1868 
1869  /* Notify about end */
1870  notify (mlp, GAS_OP_SOLVE_STOP,
1871  ((GNUNET_OK == mip_res) && (GNUNET_OK == mip_res)) ?
1874  GAS_INFO_UPDATED);
1875 
1877  "Execution time for %s solve: (total/setup/lp/mlp) : %llu %llu %llu %llu\n",
1878  (GNUNET_YES == mlp->stat_mlp_prob_changed) ? "full" : "updated",
1879  (unsigned long long) dur_total.rel_value_us,
1880  (unsigned long long) dur_setup.rel_value_us,
1881  (unsigned long long) dur_lp.rel_value_us,
1882  (unsigned long long) dur_mlp.rel_value_us);
1883 
1884  /* Save stats */
1885  mlp->ps.lp_res = res_lp;
1886  mlp->ps.mip_res = mip_res;
1887  mlp->ps.lp_presolv = mlp->control_param_lp.presolve;
1888  mlp->ps.mip_presolv = mlp->control_param_mlp.presolve;
1889  mlp->ps.p_cols = glp_get_num_cols (mlp->p.prob);
1890  mlp->ps.p_rows = glp_get_num_rows (mlp->p.prob);
1891  mlp->ps.p_elements = mlp->p.num_elements;
1892 
1893  /* Propagate result*/
1895  (GNUNET_OK == res_lp) && (GNUNET_OK == mip_res) ? GAS_STAT_SUCCESS :
1896  GAS_STAT_FAIL,
1897  GAS_INFO_NONE);
1898  if ((GNUNET_OK == res_lp) && (GNUNET_OK == mip_res))
1899  {
1901  &mlp_propagate_results, mlp);
1902  }
1904  (GNUNET_OK == res_lp) && (GNUNET_OK == mip_res) ? GAS_STAT_SUCCESS :
1905  GAS_STAT_FAIL,
1906  GAS_INFO_NONE);
1907 
1909  if ((GNUNET_YES == mlp->opt_dump_problem_all) ||
1910  (mlp->opt_dump_problem_on_fail && ((GNUNET_OK != res_lp) || (GNUNET_OK !=
1911  mip_res))))
1912  {
1913  /* Write problem to disk */
1914  switch (mlp->opt_log_format)
1915  {
1916  case MLP_CPLEX:
1917  GNUNET_asprintf (&filename, "problem_p_%u_a%u_%llu.cplex",
1918  mlp->p.num_peers,
1919  mlp->p.num_addresses, time.abs_value_us);
1920  glp_write_lp (mlp->p.prob, NULL, filename);
1921  break;
1922 
1923  case MLP_GLPK:
1924  GNUNET_asprintf (&filename, "problem_p_%u_a%u_%llu.glpk",
1925  mlp->p.num_peers,
1926  mlp->p.num_addresses, time.abs_value_us);
1927  glp_write_prob (mlp->p.prob, 0, filename);
1928  break;
1929 
1930  case MLP_MPS:
1931  GNUNET_asprintf (&filename, "problem_p_%u_a%u_%llu.mps", mlp->p.num_peers,
1932  mlp->p.num_addresses, time.abs_value_us);
1933  glp_write_mps (mlp->p.prob, GLP_MPS_FILE, NULL, filename);
1934  break;
1935 
1936  default:
1937  break;
1938  }
1939  LOG (GNUNET_ERROR_TYPE_ERROR, "Dumped problem to file: `%s' \n", filename);
1940  GNUNET_free (filename);
1941  }
1942  if ((mlp->opt_dump_solution_all) ||
1943  (mlp->opt_dump_solution_on_fail && ((GNUNET_OK != res_lp) || (GNUNET_OK !=
1944  mip_res))))
1945  {
1946  /* Write solution to disk */
1947  GNUNET_asprintf (&filename, "problem_p_%u_a%u_%llu.sol", mlp->p.num_peers,
1948  mlp->p.num_addresses, time.abs_value_us);
1949  glp_print_mip (mlp->p.prob, filename);
1950  LOG (GNUNET_ERROR_TYPE_ERROR, "Dumped solution to file: `%s' \n", filename);
1951  GNUNET_free (filename);
1952  }
1953 
1954  /* Reset change and update marker */
1955  mlp->control_param_lp.presolve = GLP_NO;
1958 
1959  if ((GNUNET_OK == res_lp) && (GNUNET_OK == mip_res))
1960  return GNUNET_OK;
1961  else
1962  return GNUNET_SYSERR;
1963 }
1964 
1972 static void
1973 GAS_mlp_address_add (void *solver,
1974  struct ATS_Address *address,
1975  uint32_t network)
1976 {
1977  struct GAS_MLP_Handle *mlp = solver;
1978 
1979  if (GNUNET_NT_COUNT <= network)
1980  {
1981  GNUNET_break (0);
1982  return;
1983  }
1984 
1985  if (NULL == address->solver_information)
1986  {
1987  address->solver_information = GNUNET_new (struct MLP_information);
1988  }
1989  else
1991  _ ("Adding address for peer `%s' multiple times\n"),
1992  GNUNET_i2s (&address->peer));
1993 
1994  /* Is this peer included in the problem? */
1995  if (NULL ==
1997  &address->peer))
1998  {
1999  /* FIXME: should this be an error? */
2001  "Adding address for peer `%s' without address request\n",
2002  GNUNET_i2s (&address->peer));
2003  return;
2004  }
2005 
2007  "Adding address for peer `%s' with address request \n",
2008  GNUNET_i2s (&address->peer));
2009  /* Problem size changed: new address for peer with pending request */
2011  if (GNUNET_YES == mlp->opt_mlp_auto_solve)
2012  GAS_mlp_solve_problem (solver);
2013 }
2014 
2015 
2022 static void
2024  struct ATS_Address *address)
2025 {
2026  struct MLP_information *mlpi = address->solver_information;
2027  struct GAS_MLP_Handle *mlp = solver;
2028 
2029  if (NULL == mlp->p.prob)
2030  return; /* There is no MLP problem to update yet */
2031 
2032  if (NULL == mlpi)
2033  {
2035  _ ("Updating address property for peer `%s' %p not added before\n"),
2036  GNUNET_i2s (&address->peer),
2037  address);
2038  GNUNET_break (0);
2039  return;
2040  }
2041  if (NULL ==
2043  &address->peer))
2044  {
2045  /* Peer is not requested, so no need to update problem */
2046  return;
2047  }
2049  "Updating properties for peer `%s'\n",
2050  GNUNET_i2s (&address->peer));
2051 
2053  return;
2054 
2055  /* Update c7) [r_q[index]][c_b] = f_q * q_averaged[type_index] */
2056  if ((GNUNET_YES ==
2059  mlpi->c_b,
2060  address->norm_delay.norm,
2061  __LINE__)) ||
2062  (GNUNET_YES ==
2065  mlpi->c_b,
2066  address->norm_distance.norm,
2067  __LINE__)))
2068  {
2070  if (GNUNET_YES == mlp->opt_mlp_auto_solve)
2071  GAS_mlp_solve_problem (solver);
2072  }
2073 }
2074 
2075 
2083 static int
2085  const struct GNUNET_PeerIdentity *key,
2086  void *value)
2087 {
2088  static int counter = 0;
2089  struct ATS_Address **aa = cls;
2090  struct ATS_Address *addr = value;
2091  struct MLP_information *mlpi = addr->solver_information;
2092 
2093  if (mlpi == NULL)
2094  return GNUNET_YES;
2095 
2096  /*
2097  * Debug output
2098  * GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
2099  * "MLP [%u] Peer `%s' %s length %u session %u active %s mlp active %s\n",
2100  * counter, GNUNET_i2s (&addr->peer), addr->plugin, addr->addr_len, addr->session_id,
2101  * (GNUNET_YES == addr->active) ? "active" : "inactive",
2102  * (GNUNET_YES == mlpi->n) ? "active" : "inactive");
2103  */
2104 
2105  if (GNUNET_YES == mlpi->n)
2106  {
2107  (*aa) = addr;
2108  (*aa)->assigned_bw_in = mlpi->b_in;
2109  (*aa)->assigned_bw_out = mlpi->b_out;
2110  return GNUNET_NO;
2111  }
2112  counter++;
2113  return GNUNET_YES;
2114 }
2115 
2116 
2117 static double
2119  const struct GNUNET_PeerIdentity *peer)
2120 {
2121  double res;
2122  const double *preferences;
2123  int c;
2124 
2125  preferences = mlp->env->get_preferences (mlp->env->cls, peer);
2126  res = 0.0;
2127  for (c = 0; c < GNUNET_ATS_PREFERENCE_END; c++)
2128  {
2129  /* fprintf (stderr, "VALUE[%u] %s %.3f \n",
2130  * c, GNUNET_i2s (&cur->addr->peer), t[c]); */
2131  res += preferences[c];
2132  }
2133 
2135  res += 1.0;
2136 
2138  "Peer preference for peer `%s' == %.2f\n",
2139  GNUNET_i2s (peer), res);
2140 
2141  return res;
2142 }
2143 
2144 
2151 static void
2153  const struct GNUNET_PeerIdentity *peer)
2154 {
2155  struct GAS_MLP_Handle *mlp = solver;
2156  struct ATS_Peer *p;
2157  struct ATS_Address *res;
2158 
2160  "Getting preferred address for `%s'\n",
2161  GNUNET_i2s (peer));
2162 
2163  /* Is this peer included in the problem? */
2164  if (NULL ==
2166  peer))
2167  {
2169  "Adding peer `%s' to list of requested_peers with requests\n",
2170  GNUNET_i2s (peer));
2171 
2172  p = GNUNET_new (struct ATS_Peer);
2173  p->id = (*peer);
2174  p->f = get_peer_pref_value (mlp, peer);
2176  peer, p,
2178 
2179  /* Added new peer, we have to rebuild problem before solving */
2181 
2182  if ((GNUNET_YES == mlp->opt_mlp_auto_solve) &&
2184  mlp->env->addresses,
2185  peer)))
2186  {
2187  mlp->exclude_peer = peer;
2188  GAS_mlp_solve_problem (mlp);
2189  mlp->exclude_peer = NULL;
2190  }
2191  }
2192  /* Get prefered address */
2193  res = NULL;
2196  &res);
2197  if (NULL != res)
2198  mlp->env->bandwidth_changed_cb (mlp->env->cls,
2199  res);
2200 }
2201 
2202 
2211 static void
2213  struct ATS_Address *address)
2214 {
2215  struct GAS_MLP_Handle *mlp = solver;
2216  struct MLP_information *mlpi;
2217  struct ATS_Address *res;
2218  int was_active;
2219 
2220  mlpi = address->solver_information;
2221  if (NULL != mlpi)
2222  {
2223  /* Remove full address */
2224  GNUNET_free (mlpi);
2225  address->solver_information = NULL;
2226  }
2227  was_active = address->active;
2228  address->active = GNUNET_NO;
2229  address->assigned_bw_in = 0;
2230  address->assigned_bw_out = 0;
2231 
2232  /* Is this peer included in the problem? */
2233  if (NULL ==
2235  &address->peer))
2236  {
2238  "Deleting address for peer `%s' without address request \n",
2239  GNUNET_i2s (&address->peer));
2240  return;
2241  }
2243  "Deleting address for peer `%s' with address request \n",
2244  GNUNET_i2s (&address->peer));
2245 
2246  /* Problem size changed: new address for peer with pending request */
2248  if (GNUNET_YES == mlp->opt_mlp_auto_solve)
2249  {
2250  GAS_mlp_solve_problem (solver);
2251  }
2252  if (GNUNET_YES == was_active)
2253  {
2254  GAS_mlp_get_preferred_address (solver, &address->peer);
2255  res = NULL;
2257  &address->peer,
2259  &res);
2260  if (NULL == res)
2261  {
2262  /* No alternative address, disconnecting peer */
2263  mlp->env->bandwidth_changed_cb (mlp->env->cls, address);
2264  }
2265  }
2266 }
2267 
2268 
2274 static void
2275 GAS_mlp_bulk_start (void *solver)
2276 {
2277  struct GAS_MLP_Handle *s = solver;
2278 
2280  "Locking solver for bulk operation ...\n");
2281  GNUNET_assert (NULL != solver);
2282  s->stat_bulk_lock++;
2283 }
2284 
2285 
2286 static void
2287 GAS_mlp_bulk_stop (void *solver)
2288 {
2289  struct GAS_MLP_Handle *s = solver;
2290 
2292  "Unlocking solver from bulk operation ...\n");
2293  GNUNET_assert (NULL != solver);
2294 
2295  if (s->stat_bulk_lock < 1)
2296  {
2297  GNUNET_break (0);
2298  return;
2299  }
2300  s->stat_bulk_lock--;
2301 
2302  if (0 < s->stat_bulk_requests)
2303  {
2304  GAS_mlp_solve_problem (solver);
2305  s->stat_bulk_requests = 0;
2306  }
2307 }
2308 
2309 
2310 
2317 static void
2319  const struct GNUNET_PeerIdentity *peer)
2320 {
2321  struct GAS_MLP_Handle *mlp = solver;
2322  struct ATS_Peer *p = NULL;
2323 
2324  GNUNET_assert (NULL != solver);
2325  GNUNET_assert (NULL != peer);
2326  if (NULL != (p = GNUNET_CONTAINER_multipeermap_get (mlp->requested_peers,
2327  peer)))
2328  {
2331  peer, p));
2332  GNUNET_free (p);
2333 
2335  if (GNUNET_YES == mlp->opt_mlp_auto_solve)
2336  {
2337  GAS_mlp_solve_problem (solver);
2338  }
2339  }
2340 }
2341 
2342 
2351 static void
2353  const struct GNUNET_PeerIdentity *peer,
2354  enum GNUNET_ATS_PreferenceKind kind,
2355  double pref_rel)
2356 {
2357  struct GAS_MLP_Handle *mlp = solver;
2358  struct ATS_Peer *p;
2359 
2361  "Changing preference for address for peer `%s' to %.2f\n",
2362  GNUNET_i2s (peer),
2363  pref_rel);
2364 
2366  "# LP address preference changes", 1, GNUNET_NO);
2367  /* Update the constraints with changed preferences */
2368 
2369 
2370 
2371  /* Update relativity constraint c9 */
2372  if (NULL == (p = GNUNET_CONTAINER_multipeermap_get (mlp->requested_peers,
2373  peer)))
2374  {
2376  "Updating preference for unknown peer `%s'\n",
2377  GNUNET_i2s (peer));
2378  return;
2379  }
2380 
2381  if (GNUNET_NO == mlp->opt_dbg_feasibility_only)
2382  {
2383  p->f = get_peer_pref_value (mlp, peer);
2385  p->r_c9,
2386  mlp->p.c_r,
2387  -p->f,
2388  __LINE__);
2389 
2390  /* Problem size changed: new address for peer with pending request */
2392  if (GNUNET_YES == mlp->opt_mlp_auto_solve)
2393  GAS_mlp_solve_problem (solver);
2394  }
2395 }
2396 
2397 
2408 static void
2410  struct GNUNET_SERVICE_Client *application,
2411  const struct GNUNET_PeerIdentity *peer,
2412  const struct GNUNET_TIME_Relative scope,
2413  enum GNUNET_ATS_PreferenceKind kind,
2414  double score)
2415 {
2416  struct GAS_PROPORTIONAL_Handle *s = solver;
2417 
2418  GNUNET_assert (NULL != solver);
2419  GNUNET_assert (NULL != peer);
2420  GNUNET_assert (NULL != s);
2421 }
2422 
2423 
2424 static int
2425 mlp_free_peers (void *cls,
2426  const struct GNUNET_PeerIdentity *key, void *value)
2427 {
2428  struct GNUNET_CONTAINER_MultiPeerMap *map = cls;
2429  struct ATS_Peer *p = value;
2430 
2432  GNUNET_CONTAINER_multipeermap_remove (map, key, value));
2433  GNUNET_free (p);
2434 
2435  return GNUNET_OK;
2436 }
2437 
2438 
2445 void *
2447 {
2448  struct GNUNET_ATS_SolverFunctions *sf = cls;
2449  struct GAS_MLP_Handle *mlp = sf->cls;
2450 
2452  "Shutting down mlp solver\n");
2453  mlp_delete_problem (mlp);
2455  &mlp_free_peers,
2456  mlp->requested_peers);
2458  mlp->requested_peers = NULL;
2459 
2460  /* Clean up GLPK environment */
2461  glp_free_env ();
2462  GNUNET_free (mlp);
2463 
2465  "Shutdown down of mlp solver complete\n");
2466  return NULL;
2467 }
2468 
2469 
2470 void *
2472 {
2473  static struct GNUNET_ATS_SolverFunctions sf;
2475  struct GAS_MLP_Handle *mlp = GNUNET_new (struct GAS_MLP_Handle);
2476  float f_tmp;
2477  unsigned long long tmp;
2478  unsigned int b_min;
2479  unsigned int n_min;
2480  int c;
2481  char *outputformat;
2482 
2483  struct GNUNET_TIME_Relative max_duration;
2484  long long unsigned int max_iterations;
2485 
2486  /* Init GLPK environment */
2487  int res = glp_init_env ();
2488 
2489  switch (res)
2490  {
2491  case 0:
2492  LOG (GNUNET_ERROR_TYPE_DEBUG, "GLPK: `%s'\n",
2493  "initialization successful");
2494  break;
2495 
2496  case 1:
2497  LOG (GNUNET_ERROR_TYPE_DEBUG, "GLPK: `%s'\n",
2498  "environment is already initialized");
2499  break;
2500 
2501  case 2:
2502  LOG (GNUNET_ERROR_TYPE_ERROR, "Could not init GLPK: `%s'\n",
2503  "initialization failed (insufficient memory)");
2504  GNUNET_free (mlp);
2505  return NULL;
2506  break;
2507 
2508  case 3:
2509  LOG (GNUNET_ERROR_TYPE_ERROR, "Could not init GLPK: `%s'\n",
2510  "initialization failed (unsupported programming model)");
2511  GNUNET_free (mlp);
2512  return NULL;
2513  break;
2514 
2515  default:
2516  break;
2517  }
2518 
2520  "ats",
2521  "MLP_DUMP_PROBLEM_ALL");
2522  if (GNUNET_SYSERR == mlp->opt_dump_problem_all)
2524 
2526  "ats",
2527  "MLP_DUMP_SOLUTION_ALL");
2530 
2532  env->cfg,
2533  "ats",
2534  "MLP_DUMP_PROBLEM_ON_FAIL");
2537 
2539  env->cfg,
2540  "ats",
2541  "MLP_DUMP_SOLUTION_ON_FAIL");
2544 
2546  "ats",
2547  "MLP_DBG_GLPK_VERBOSE");
2548  if (GNUNET_SYSERR == mlp->opt_dbg_glpk_verbose)
2550 
2552  env->cfg,
2553  "ats",
2554  "MLP_DBG_FEASIBILITY_ONLY");
2559  "MLP solver is configured to check feasibility only!\n");
2560 
2562  env->cfg,
2563  "ats",
2564  "MLP_DBG_AUTOSCALE_PROBLEM");
2569  "MLP solver is configured automatically scale the problem!\n");
2570 
2572  env->cfg,
2573  "ats",
2574  "MLP_DBG_INTOPT_PRESOLVE");
2579  "MLP solver is configured use the mlp presolver\n");
2580 
2582  env->cfg,
2583  "ats",
2584  "MLP_DBG_OPTIMIZE_DIVERSITY");
2589  "MLP solver is not optimizing for diversity\n");
2590 
2592  env->cfg,
2593  "ats",
2594  "MLP_DBG_OPTIMIZE_RELATIVITY");
2599  "MLP solver is not optimizing for relativity\n");
2600 
2602  env->cfg,
2603  "ats",
2604  "MLP_DBG_OPTIMIZE_QUALITY");
2607  if (GNUNET_NO == mlp->opt_dbg_optimize_quality)
2609  "MLP solver is not optimizing for quality\n");
2610 
2612  env->cfg,
2613  "ats",
2614  "MLP_DBG_OPTIMIZE_UTILITY");
2617  if (GNUNET_NO == mlp->opt_dbg_optimize_utility)
2619  "MLP solver is not optimizing for utility\n");
2620 
2621  if ((GNUNET_NO == mlp->opt_dbg_optimize_utility) &&
2622  (GNUNET_NO == mlp->opt_dbg_optimize_quality) &&
2624  (GNUNET_NO == mlp->opt_dbg_optimize_utility) &&
2626  {
2628  _ (
2629  "MLP solver is not optimizing for anything, changing to feasibility check\n"));
2631  }
2632 
2634  "ats",
2635  "MLP_LOG_FORMAT",
2636  &outputformat))
2637  mlp->opt_log_format = MLP_CPLEX;
2638  else
2639  {
2640  GNUNET_STRINGS_utf8_toupper (outputformat, outputformat);
2641  if (0 == strcmp (outputformat, "MPS"))
2642  {
2643  mlp->opt_log_format = MLP_MPS;
2644  }
2645  else if (0 == strcmp (outputformat, "CPLEX"))
2646  {
2647  mlp->opt_log_format = MLP_CPLEX;
2648  }
2649  else if (0 == strcmp (outputformat, "GLPK"))
2650  {
2651  mlp->opt_log_format = MLP_GLPK;
2652  }
2653  else
2654  {
2656  "Invalid log format `%s' in configuration, using CPLEX!\n",
2657  outputformat);
2658  mlp->opt_log_format = MLP_CPLEX;
2659  }
2660  GNUNET_free (outputformat);
2661  }
2662 
2663  mlp->pv.BIG_M = (double) BIG_M_VALUE;
2664 
2665  mlp->pv.mip_gap = (double) 0.0;
2667  "MLP_MAX_MIP_GAP",
2668  &f_tmp))
2669  {
2670  if ((f_tmp < 0.0) || (f_tmp > 1.0))
2671  {
2672  LOG (GNUNET_ERROR_TYPE_ERROR, _ ("Invalid %s configuration %f \n"),
2673  "MIP gap", f_tmp);
2674  }
2675  else
2676  {
2677  mlp->pv.mip_gap = f_tmp;
2678  LOG (GNUNET_ERROR_TYPE_INFO, "Using %s of %.3f\n",
2679  "MIP gap", f_tmp);
2680  }
2681  }
2682 
2683  mlp->pv.lp_mip_gap = (double) 0.0;
2685  "MLP_MAX_LP_MIP_GAP",
2686  &f_tmp))
2687  {
2688  if ((f_tmp < 0.0) || (f_tmp > 1.0))
2689  {
2690  LOG (GNUNET_ERROR_TYPE_ERROR, _ ("Invalid %s configuration %f \n"),
2691  "LP/MIP", f_tmp);
2692  }
2693  else
2694  {
2695  mlp->pv.lp_mip_gap = f_tmp;
2696  LOG (GNUNET_ERROR_TYPE_INFO, "Using %s gap of %.3f\n",
2697  "LP/MIP", f_tmp);
2698  }
2699  }
2700 
2701  /* Get timeout for iterations */
2703  "MLP_MAX_DURATION",
2704  &max_duration))
2705  {
2706  max_duration = MLP_MAX_EXEC_DURATION;
2707  }
2708 
2709  /* Get maximum number of iterations */
2711  "MLP_MAX_ITERATIONS",
2712  &max_iterations))
2713  {
2714  max_iterations = MLP_MAX_ITERATIONS;
2715  }
2716 
2717  /* Get diversity coefficient from configuration */
2718  mlp->pv.co_D = MLP_DEFAULT_D;
2720  "MLP_COEFFICIENT_D",
2721  &f_tmp))
2722  {
2723  if ((f_tmp < 0.0))
2724  {
2725  LOG (GNUNET_ERROR_TYPE_ERROR, _ ("Invalid %s configuration %f \n"),
2726  "MLP_COEFFICIENT_D", f_tmp);
2727  }
2728  else
2729  {
2730  mlp->pv.co_D = f_tmp;
2731  LOG (GNUNET_ERROR_TYPE_INFO, "Using %s gap of %.3f\n",
2732  "MLP_COEFFICIENT_D", f_tmp);
2733  }
2734  }
2735 
2736  /* Get relativity coefficient from configuration */
2737  mlp->pv.co_R = MLP_DEFAULT_R;
2739  "MLP_COEFFICIENT_R",
2740  &f_tmp))
2741  {
2742  if ((f_tmp < 0.0))
2743  {
2744  LOG (GNUNET_ERROR_TYPE_ERROR, _ ("Invalid %s configuration %f \n"),
2745  "MLP_COEFFICIENT_R", f_tmp);
2746  }
2747  else
2748  {
2749  mlp->pv.co_R = f_tmp;
2750  LOG (GNUNET_ERROR_TYPE_INFO, "Using %s gap of %.3f\n",
2751  "MLP_COEFFICIENT_R", f_tmp);
2752  }
2753  }
2754 
2755 
2756  /* Get utilization coefficient from configuration */
2757  mlp->pv.co_U = MLP_DEFAULT_U;
2759  "MLP_COEFFICIENT_U",
2760  &f_tmp))
2761  {
2762  if ((f_tmp < 0.0))
2763  {
2764  LOG (GNUNET_ERROR_TYPE_ERROR, _ ("Invalid %s configuration %f \n"),
2765  "MLP_COEFFICIENT_U", f_tmp);
2766  }
2767  else
2768  {
2769  mlp->pv.co_U = f_tmp;
2770  LOG (GNUNET_ERROR_TYPE_INFO, "Using %s gap of %.3f\n",
2771  "MLP_COEFFICIENT_U", f_tmp);
2772  }
2773  }
2774 
2775  /* Get quality metric coefficients from configuration */
2776  for (c = 0; c < RQ_QUALITY_METRIC_COUNT; c++)
2777  {
2778  /* initialize quality coefficients with default value 1.0 */
2779  mlp->pv.co_Q[c] = MLP_DEFAULT_QUALITY;
2780  }
2781 
2782 
2783  if (GNUNET_OK ==
2785  "MLP_COEFFICIENT_QUALITY_DELAY",
2786  &tmp))
2787  mlp->pv.co_Q[RQ_QUALITY_METRIC_DELAY] = (double) tmp / 100;
2788  else
2790 
2791  if (GNUNET_OK ==
2793  "MLP_COEFFICIENT_QUALITY_DISTANCE",
2794  &tmp))
2795  mlp->pv.co_Q[RQ_QUALITY_METRIC_DISTANCE] = (double) tmp / 100;
2796  else
2798 
2799  /* Get minimum bandwidth per used address from configuration */
2801  "MLP_MIN_BANDWIDTH",
2802  &tmp))
2803  b_min = tmp;
2804  else
2805  {
2806  b_min = ntohl (GNUNET_CONSTANTS_DEFAULT_BW_IN_OUT.value__);
2807  }
2808 
2809  /* Get minimum number of connections from configuration */
2811  "MLP_MIN_CONNECTIONS",
2812  &tmp))
2813  n_min = tmp;
2814  else
2816 
2817  /* Init network quotas */
2818  for (c = 0; c < GNUNET_NT_COUNT; c++)
2819  {
2820  mlp->pv.quota_index[c] = c;
2821  mlp->pv.quota_out[c] = env->out_quota[c];
2822  mlp->pv.quota_in[c] = env->in_quota[c];
2823 
2825  "Quota for network `%s' (in/out) %llu/%llu\n",
2826  GNUNET_NT_to_string (c),
2827  mlp->pv.quota_out[c],
2828  mlp->pv.quota_in[c]);
2829  /* Check if defined quota could make problem unsolvable */
2830  if ((n_min * b_min) > mlp->pv.quota_out[c])
2831  {
2833  _ (
2834  "Adjusting inconsistent outbound quota configuration for network `%s', is %llu must be at least %llu\n"),
2836  mlp->pv.quota_out[c],
2837  (n_min * b_min));
2838  mlp->pv.quota_out[c] = (n_min * b_min);
2839  }
2840  if ((n_min * b_min) > mlp->pv.quota_in[c])
2841  {
2843  _ (
2844  "Adjusting inconsistent inbound quota configuration for network `%s', is %llu must be at least %llu\n"),
2846  mlp->pv.quota_in[c],
2847  (n_min * b_min));
2848  mlp->pv.quota_in[c] = (n_min * b_min);
2849  }
2850  /* Check if bandwidth is too big to make problem solvable */
2851  if (mlp->pv.BIG_M < mlp->pv.quota_out[c])
2852  {
2854  _ (
2855  "Adjusting outbound quota configuration for network `%s'from %llu to %.0f\n"),
2857  mlp->pv.quota_out[c],
2858  mlp->pv.BIG_M);
2859  mlp->pv.quota_out[c] = mlp->pv.BIG_M;
2860  }
2861  if (mlp->pv.BIG_M < mlp->pv.quota_in[c])
2862  {
2864  _ (
2865  "Adjusting inbound quota configuration for network `%s' from %llu to %.0f\n"),
2867  mlp->pv.quota_in[c],
2868  mlp->pv.BIG_M);
2869  mlp->pv.quota_in[c] = mlp->pv.BIG_M;
2870  }
2871  }
2872  mlp->env = env;
2873  sf.cls = mlp;
2874  sf.s_add = &GAS_mlp_address_add;
2883 
2884  /* Setting MLP Input variables */
2885  mlp->pv.b_min = b_min;
2886  mlp->pv.n_min = n_min;
2892  mlp->stat_bulk_requests = 0;
2893  mlp->stat_bulk_lock = 0;
2894 
2895  /* Setup GLPK */
2896  /* Redirect GLPK output to GNUnet logging */
2897  glp_term_hook (&mlp_term_hook, (void *) mlp);
2898 
2899  /* Init LP solving parameters */
2900  glp_init_smcp (&mlp->control_param_lp);
2901  mlp->control_param_lp.msg_lev = GLP_MSG_OFF;
2902  if (GNUNET_YES == mlp->opt_dbg_glpk_verbose)
2903  mlp->control_param_lp.msg_lev = GLP_MSG_ALL;
2904 
2905  mlp->control_param_lp.it_lim = max_iterations;
2906  mlp->control_param_lp.tm_lim = max_duration.rel_value_us / 1000LL;
2907 
2908  /* Init MLP solving parameters */
2909  glp_init_iocp (&mlp->control_param_mlp);
2910  /* Setting callback function */
2911  mlp->control_param_mlp.cb_func = &mlp_branch_and_cut_cb;
2912  mlp->control_param_mlp.cb_info = mlp;
2913  mlp->control_param_mlp.msg_lev = GLP_MSG_OFF;
2914  mlp->control_param_mlp.mip_gap = mlp->pv.mip_gap;
2915  if (GNUNET_YES == mlp->opt_dbg_glpk_verbose)
2916  mlp->control_param_mlp.msg_lev = GLP_MSG_ALL;
2917  mlp->control_param_mlp.tm_lim = max_duration.rel_value_us / 1000LL;
2918 
2919  LOG (GNUNET_ERROR_TYPE_DEBUG, "solver ready\n");
2920 
2921  return &sf;
2922 }
2923 
2924 /* end of plugin_ats_mlp.c */
unsigned int b_min
GAS_solver_stop_get_preferred_address s_get_stop
Tell solver stop notifying ATS about changes for this peers.
uint32_t b_in
Bandwidth assigned inbound.
int opt_dump_solution_on_fail
Write MILP problem solutions to a file when solver fails.
Solving of the LP problem was started MLP solver only.
const struct GNUNET_CONTAINER_MultiPeerMap * map
After the problem was finished, start notifications about changes to addresses.
A handle for the proportional solver.
int r_q[RQ_QUALITY_METRIC_COUNT]
#define MLP_DEFAULT_MIN_CONNECTIONS
glp_prob * prob
GLPK (MLP) problem object.
int GNUNET_CONFIGURATION_get_value_time(const struct GNUNET_CONFIGURATION_Handle *cfg, const char *section, const char *option, struct GNUNET_TIME_Relative *time)
Get a configuration value that should be a relative time.
static void GAS_mlp_address_delete(void *solver, struct ATS_Address *address)
Deletes a single address in the MLP problem.
signed int c_n
address usage column
GAS_solver_address_add s_add
Add a new address for a peer to the solver.
uint64_t rel_value_us
The actual value.
const char * GNUNET_NT_to_string(enum GNUNET_NetworkType net)
Convert a enum GNUNET_NetworkType to a string.
Definition: nt.c:44
static double get_peer_pref_value(struct GAS_MLP_Handle *mlp, const struct GNUNET_PeerIdentity *peer)
enum MLP_Output_Format opt_log_format
Output format.
struct MLP_Variables pv
Encapsulation for the MLP problem variables.
int opt_dbg_feasibility_only
solve feasibility only
static const char * print_quality_type(enum QualityMetrics qm)
struct GNUNET_ATS_Properties properties
ATS performance information for this address.
The setup of the problem as a preparation to solve it was started.
struct GNUNET_STATISTICS_Handle * stats
Statistics handle to be used by the solver.
static int mlp_create_problem_count_addresses_it(void *cls, const struct GNUNET_PeerIdentity *key, void *value)
struct GNUNET_CONTAINER_MultiPeerMap * requested_peers
Peers with pending address requests.
static int reset_peers(void *cls, const struct GNUNET_PeerIdentity *key, void *value)
Reset peers for next problem creation.
static int mlp_create_problem_update_value(struct MLP_Problem *p, int row, int col, double val, int line)
Updates an existing value in the matrix.
static int mlp_create_problem(struct GAS_MLP_Handle *mlp)
Create the MLP problem.
static void GAS_mlp_address_add(void *solver, struct ATS_Address *address, uint32_t network)
Add a single address to the solve.
int active
Is this the active address for this peer?
QualityMetrics
GAS_get_preferences get_preferences
ATS addresses function to obtain preference values.
unsigned int r_c9
int opt_dbg_optimize_relativity
solve autoscale the problem
static void mlp_branch_and_cut_cb(glp_tree *tree, void *info)
struct GNUNET_PeerIdentity peer
Peer ID this address is for.
static int mlp_create_problem_create_constraint(struct MLP_Problem *p, char *name, unsigned int bound, double lb, double ub)
int quota_index[GNUNET_NT_COUNT]
GAS_Solver_Status
Status of a GAS_Solver_Operation operation.
#define GNUNET_assert(cond)
Use this for fatal errors that cannot be handled.
MLP_Output_Format
No more specific information.
const void * addr
Address (in plugin-specific binary format).
static void mlp_create_problem_add_invariant_columns(struct GAS_MLP_Handle *mlp, struct MLP_Problem *p)
Create the invariant columns d, u, r, q0 ...
static void mlp_create_problem_set_value(struct MLP_Problem *p, int row, int col, double val, int line)
Creates a new value in the matrix.
static void GAS_mlp_get_preferred_address(void *solver, const struct GNUNET_PeerIdentity *peer)
Get the preferred address for a specific peer.
unsigned int num_elements
GAS_solver_address_feedback_preference s_feedback
Give feedback about the current assignment.
static int mlp_create_problem_add_address_information(void *cls, const struct GNUNET_PeerIdentity *key, void *value)
Create the.
unsigned int r_c2
int GNUNET_CONFIGURATION_get_value_float(const struct GNUNET_CONFIGURATION_Handle *cfg, const char *section, const char *option, float *number)
Get a configuration value that should be a floating point number.
static void GAS_mlp_bulk_stop(void *solver)
int stat_bulk_requests
Number of changes while solver was locked.
GAS_solver_address_property_changed s_address_update_property
Update the properties of an address in the solver.
int opt_dbg_optimize_utility
solve autoscale the problem
int opt_mlp_auto_solve
Solve the problem automatically when updates occur? Default: GNUNET_YES Can be disabled for test and ...
#define GNUNET_CONSTANTS_DEFAULT_BW_IN_OUT
Bandwidth (in/out) to assume initially (before either peer has communicated any particular preference...
int GNUNET_CONTAINER_multipeermap_remove(struct GNUNET_CONTAINER_MultiPeerMap *map, const struct GNUNET_PeerIdentity *key, const void *value)
Remove the given key-value pair from the map.
#define GNUNET_NO
Definition: gnunet_common.h:78
static struct GNUNET_CONTAINER_MultiPeerMap * addresses
Hashmap to store addresses.
Definition: gnunet-ats.c:146
static struct GNUNET_IDENTITY_Handle * id
Handle to identity service.
#define GNUNET_OK
Named constants for return values.
Definition: gnunet_common.h:75
A full solution process is performed Quite specific to the MLP solver.
char * plugin
Plugin name.
#define GNUNET_new(type)
Allocate a struct or union of the given type.
unsigned int num_peers
Solving of the LP problem is done MLP solver only.
static int mlp_create_problem_count_peers_it(void *cls, const struct GNUNET_PeerIdentity *key, void *value)
uint32_t b_out
Bandwidth assigned outbound.
static int mlp_create_problem_count_addresses(const struct GNUNET_CONTAINER_MultiPeerMap *requested_peers, const struct GNUNET_CONTAINER_MultiPeerMap *addresses)
int opt_dbg_glpk_verbose
Print GLPK output.
void GNUNET_STATISTICS_update(struct GNUNET_STATISTICS_Handle *handle, const char *name, int64_t delta, int make_persistent)
Set statistic value for the peer.
struct GNUNET_CONTAINER_MultiPeerMap * GNUNET_CONTAINER_multipeermap_create(unsigned int len, int do_not_copy_keys)
Create a multi peer map (hash map for public keys of peers).
static const char * mlp_solve_to_string(int retcode)
Translate glpk solver error codes to text.
int opt_dbg_optimize_quality
solve autoscale the problem
struct MLP_Problem p
Encapsulation for the MLP problem.
int stat_mlp_prob_changed
Has the problem size changed since last solution.
uint64_t abs_value_us
The actual value.
#define GNUNET_break(cond)
Use this for internal assertion violations that are not fatal (can be handled) but should not occur...
struct GNUNET_PeerIdentity id
End of preference list.
void GNUNET_CONTAINER_multipeermap_destroy(struct GNUNET_CONTAINER_MultiPeerMap *map)
Destroy a hash map.
#define MLP_DEFAULT_QUALITY
static struct GNUNET_CONTAINER_MultiPeerMap * map
Handle to the map used to store old latency values for peers.
static const char * mlp_status_to_string(int retcode)
Translate glpk status error codes to text.
struct MLP_Solution ps
Encapsulation for the MLP solution.
#define _(String)
GNU gettext support macro.
Definition: platform.h:181
Address specific MLP information.
GAS_Solver_Operation
Operation codes for solver information callback.
static void GAS_mlp_address_property_changed(void *solver, struct ATS_Address *address)
Transport properties for this address have changed.
Handle to a client that is connected to a service.
Definition: service.c:250
uint32_t assigned_bw_in
Inbound bandwidth assigned by solver.
int opt_dump_problem_on_fail
Write MILP problems to a MPS file when solver fails.
Solving of the MLP problem is done MLP solver only.
int GNUNET_asprintf(char **buf, const char *format,...)
Like asprintf, just portable.
int stat_bulk_lock
Bulk lock.
static int GAS_mlp_solve_problem(void *solver)
Solves the MLP problem.
A solution iteration has been started.
void GNUNET_STRINGS_utf8_toupper(const char *input, char *output)
Convert the utf-8 input string to upper case.
Definition: strings.c:578
unsigned int r_c9
double lp_objective_value
static struct GNUNET_OS_Process * p
Helper process we started.
Definition: gnunet-qr.c:59
unsigned int n_min
, &#39; bother checking if a value already exists (faster than GNUNET_CONTAINER_MULTIHASHMAPOPTION_...
static char * line
Desired phone line (string to be converted to a hash).
static void GAS_mlp_address_preference_feedback(void *solver, struct GNUNET_SERVICE_Client *application, const struct GNUNET_PeerIdentity *peer, const struct GNUNET_TIME_Relative scope, enum GNUNET_ATS_PreferenceKind kind, double score)
Get application feedback for a peer.
static char * value
Value of the record to add/remove.
int opt_dump_problem_all
Write all MILP problems to a MPS file.
#define MLP_MAX_EXEC_DURATION
static int mlp_create_problem_count_peers(const struct GNUNET_CONTAINER_MultiPeerMap *requested_peers, const struct GNUNET_CONTAINER_MultiPeerMap *addresses)
static enum GNUNET_NetworkType scope
Which network scope do we belong to?
static int mlp_get_preferred_address_it(void *cls, const struct GNUNET_PeerIdentity *key, void *value)
Find the active address in the set of addresses of a peer.
GAS_Solver_Additional_Information
Status of the operation.
unsigned int r_c8
GAS_solver_address_delete s_del
Delete an address in the solver.
int opt_dbg_intopt_presolver
use the intopt presolver instead of simplex
Solving of the MLP problem was started MLP solver only.
unsigned int r_c3
constraint 3: minimum bandwidth
static char * filename
#define MLP_NaN
void * libgnunet_plugin_ats_mlp_done(void *cls)
Shutdown the MLP problem solving component.
struct GNUNET_ATS_PluginEnvironment * env
#define MLP_MAX_ITERATIONS
Internal representation of the hash map.
int r_quota[GNUNET_NT_COUNT]
int n
Address selected.
unsigned long long quota_out[GNUNET_NT_COUNT]
GAS_solver_address_change_preference s_pref
Change relative preference for quality in solver.
int GNUNET_CONFIGURATION_get_value_size(const struct GNUNET_CONFIGURATION_Handle *cfg, const char *section, const char *option, unsigned long long *size)
Get a configuration value that should be a size in bytes.
#define BIG_M_VALUE
static int res
struct GNUNET_TIME_Absolute GNUNET_TIME_absolute_get(void)
Get the current time.
Definition: time.c:118
int GNUNET_CONFIGURATION_get_value_string(const struct GNUNET_CONFIGURATION_Handle *cfg, const char *section, const char *option, char **value)
Get a configuration value that should be a string.
#define MLP_DEFAULT_U
#define MLP_UNDEFINED
Address with additional information.
struct GNUNET_TESTBED_Peer * peer
The peer associated with this model.
struct GNUNET_HashCode key
The key used in the DHT.
#define GNUNET_SYSERR
Definition: gnunet_common.h:76
unsigned int r_c6
int opt_dbg_optimize_diversity
solve autoscale the problem
void * solver_information
Solver-specific information for this address.
static int mlp_free_peers(void *cls, const struct GNUNET_PeerIdentity *key, void *value)
double co_Q[RQ_QUALITY_METRIC_COUNT]
const char * name
struct GNUNET_MQ_Envelope * env
Definition: 005.c:1
void * cls
Closure to pass to all solver functions in this struct.
#define MLP_DEFAULT_D
double mlp_objective_value
ats service address management
static int add
Desired action is to add a record.
static void GAS_mlp_address_change_preference(void *solver, const struct GNUNET_PeerIdentity *peer, enum GNUNET_ATS_PreferenceKind kind, double pref_rel)
Changes the preferences for a peer in the MLP problem.
#define GNUNET_TIME_UNIT_ZERO
Relative time zero.
#define GNUNET_memcmp(a, b)
Compare memory in a and b, where both must be of the same pointer type.
int opt_dbg_autoscale_problem
solve autoscale the problem
unsigned int ci
GAS_solver_get_preferred_address s_get
Tell solver to notify ATS if the address to use changes for a specific peer using the bandwidth chang...
unsigned long long in_quota[6]
Array of configured inbound quotas Order according to networks in network array.
A solution iteration has been finished.
unsigned long long quota_in[GNUNET_NT_COUNT]
enum GNUNET_NetworkType scope
Which network scope does the respective address belong to? This property does not change...
int GNUNET_CONTAINER_multipeermap_put(struct GNUNET_CONTAINER_MultiPeerMap *map, const struct GNUNET_PeerIdentity *key, void *value, enum GNUNET_CONTAINER_MultiHashMapOption opt)
Store a key-value pair in the map.
int GNUNET_CONTAINER_multipeermap_iterate(struct GNUNET_CONTAINER_MultiPeerMap *map, GNUNET_CONTAINER_PeerMapIterator it, void *it_cls)
Iterate over all entries in the map.
MLP Handle.
GAS_solver_bulk_start s_bulk_start
Start a bulk operation.
The identity of the host (wraps the signing key of the peer).
#define GLP_NO
unsigned int r_c1
constraint 1: bandwidth capping
uint32_t assigned_bw_out
Outbound bandwidth assigned by solver.
#define GLP_YES
struct GNUNET_TIME_Relative GNUNET_TIME_absolute_get_duration(struct GNUNET_TIME_Absolute whence)
Get the duration of an operation as the difference of the current time and the given start time "henc...
Definition: time.c:373
void * GNUNET_CONTAINER_multipeermap_get(const struct GNUNET_CONTAINER_MultiPeerMap *map, const struct GNUNET_PeerIdentity *key)
Given a key find a value in the map matching the key.
static void mlp_delete_problem(struct GAS_MLP_Handle *mlp)
Delete the MLP problem and free the constrain matrix.
void * libgnunet_plugin_ats_mlp_init(void *cls)
signed int c_b
bandwidth column index
Automatic transport selection and outbound bandwidth determination.
const struct GNUNET_CONFIGURATION_Handle * cfg
Configuration handle to be used by the solver.
int c_q[RQ_QUALITY_METRIC_COUNT]
GAS_solver_information_callback info_cb
Callback for solver to call with status information, can be NULL.
struct GAS_NormalizationInfo norm_delay
Normalized delay information for this address.
The setup of the problem as a preparation to solve is finished.
unsigned long long out_quota[6]
Array of configured outbound quotas Order according to networks in network array. ...
static int mlp_solve_lp_problem(struct GAS_MLP_Handle *mlp)
Solves the LP problem.
An existing solution was reused Quite specific to the MLP solver.
unsigned int r_c2
static void GAS_mlp_stop_get_preferred_address(void *solver, const struct GNUNET_PeerIdentity *peer)
Stop notifying about address and bandwidth changes for this peer.
enum GNUNET_TESTBED_UnderlayLinkModelType type
the type of this model
void * cls
Closure to pass to all callbacks in this struct.
unsigned int r_c4
Time for absolute times used by GNUnet, in microseconds.
#define GNUNET_YES
Definition: gnunet_common.h:77
#define MLP_DEFAULT_R
unsigned int GNUNET_CONTAINER_multipeermap_size(const struct GNUNET_CONTAINER_MultiPeerMap *map)
Get the number of key-value pairs in the map.
static struct GNUNET_ATS_SolverFunctions * sf
Solver handle.
GNUNET_ATS_PreferenceKind
Enum defining all known preference categories.
unsigned int num_addresses
int stat_mlp_prob_updated
Was the problem updated since last solution.
int opt_dump_solution_all
Write all MILP problem solutions to a file.
static void notify(struct GAS_MLP_Handle *mlp, enum GAS_Solver_Operation op, enum GAS_Solver_Status stat, enum GAS_Solver_Additional_Information add)
static struct GNUNET_ARM_Operation * op
Current operation.
Definition: gnunet-arm.c:144
struct GNUNET_CONTAINER_MultiPeerMap * addresses
Hashmap containing all addresses available.
The ATS plugin will pass a pointer to a struct of this type as to the initialization function of the ...
int GNUNET_CONFIGURATION_get_value_yesno(const struct GNUNET_CONFIGURATION_Handle *cfg, const char *section, const char *option)
Get a configuration value that should be in a set of "YES" or "NO".
static int mlp_propagate_results(void *cls, const struct GNUNET_PeerIdentity *key, void *value)
Propagates the results when MLP problem was solved.
glp_iocp control_param_mlp
GLPK LP control parameter.
glp_smcp control_param_lp
GLPK LP control parameter.
int GNUNET_CONTAINER_multipeermap_contains(const struct GNUNET_CONTAINER_MultiPeerMap *map, const struct GNUNET_PeerIdentity *key)
Check if the map contains any value under the given key (including values that are NULL)...
GAS_solver_bulk_stop s_bulk_stop
Bulk operation done.
static char * address
GNS address for this phone.
const struct GNUNET_PeerIdentity * exclude_peer
Exclude peer from next result propagation.
GAS_bandwidth_changed_cb bandwidth_changed_cb
ATS addresses callback to be notified about bandwidth assignment changes.
After the problem was finished, notifications about changes to addresses are done.
#define LOG(kind,...)
NOTE: Do not modify this documentation.
const char * GNUNET_i2s(const struct GNUNET_PeerIdentity *pid)
Convert a peer identity to a string (for printing debug messages).
#define GNUNET_NT_COUNT
double norm
Normalized values from queue to a range of values [1.0...2.0].
static void GAS_mlp_bulk_start(void *solver)
Start a bulk operation.
static int mlp_create_problem_create_column(struct MLP_Problem *p, char *name, unsigned int type, unsigned int bound, double lb, double ub, double coef)
int GNUNET_CONTAINER_multipeermap_get_multiple(struct GNUNET_CONTAINER_MultiPeerMap *map, const struct GNUNET_PeerIdentity *key, GNUNET_CONTAINER_PeerMapIterator it, void *it_cls)
Iterate over all entries in the map that match a particular key.
#define GNUNET_malloc(size)
Wrapper around malloc.
struct GAS_NormalizationInfo norm_distance
Normalized distance information for this address.
#define GNUNET_free(ptr)
Wrapper around free.
Time for relative time used by GNUnet, in microseconds.
static int mlp_term_hook(void *info, const char *s)
Intercept GLPK terminal output.
static void mlp_create_problem_add_invariant_rows(struct GAS_MLP_Handle *mlp, struct MLP_Problem *p)
Create the invariant columns c4, c6, c10, c8, c7.