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(GNUNET_TIME_UNIT_SECONDS, 10)
43 #define MLP_MAX_ITERATIONS 4096
44 
45 #define MLP_DEFAULT_D 1.0
46 #define MLP_DEFAULT_R 1.0
47 #define MLP_DEFAULT_U 1.0
48 #define MLP_DEFAULT_QUALITY 1.0
49 #define MLP_DEFAULT_MIN_CONNECTIONS 4
50 #define MLP_DEFAULT_PEER_PREFERENCE 1.0
51 
52 #define MLP_NaN -1
53 #define MLP_UNDEFINED 0
54 #define GLP_YES 1.0
55 #define GLP_NO 0.0
56 
61 };
62 
63 
68 };
69 
70 
71 static const char *
73 {
74  switch (qm)
75  {
77  return "delay";
78 
80  return "distance";
81 
82  default:
83  GNUNET_break(0);
84  return NULL;
85  }
86 }
87 
88 
89 struct MLP_Solution {
90  int lp_res;
92  int mip_res;
94 
97  double mlp_gap;
98  double lp_mlp_gap;
99 
101  int p_cols;
102  int p_rows;
103 
104  int n_peers;
106 };
107 
108 struct ATS_Peer {
110 
111  /* Was this peer already added to the current problem? */
113 
114  /* constraint 2: 1 address per peer*/
115  unsigned int r_c2;
116 
117  /* constraint 9: relativity */
118  unsigned int r_c9;
119 
120  /* Legacy preference value */
121  double f;
122 };
123 
124 struct MLP_Problem {
128  glp_prob *prob;
129 
130  /* Number of addresses in problem */
131  unsigned int num_addresses;
132  /* Number of peers in problem */
133  unsigned int num_peers;
134  /* Number of elements in problem matrix */
135  unsigned int num_elements;
136 
137  /* Row index constraint 2: */
138  unsigned int r_c2;
139  /* Row index constraint 4: minimum connections */
140  unsigned int r_c4;
141  /* Row index constraint 6: maximize diversity */
142  unsigned int r_c6;
143  /* Row index constraint 8: utilization*/
144  unsigned int r_c8;
145  /* Row index constraint 9: relativity*/
146  unsigned int r_c9;
147  /* Row indices quality metrics */
149  /* Row indices ATS network quotas */
150  int r_quota[GNUNET_NT_COUNT];
151 
152  /* Column index Diversity (D) column */
153  int c_d;
154  /* Column index Utilization (U) column */
155  int c_u;
156  /* Column index Proportionality (R) column */
157  int c_r;
158  /* Column index quality metrics */
160 
161  /* Problem matrix */
162  /* Current index */
163  unsigned int ci;
164  /* Row index array */
165  int *ia;
166  /* Column index array */
167  int *ja;
168  /* Column index value */
169  double *ar;
170 };
171 
173  /* Big M value for bandwidth capping */
174  double BIG_M;
175 
176  /* MIP Gap */
177  double mip_gap;
178 
179  /* LP MIP Gap */
180  double lp_mip_gap;
181 
182  /* Number of quality metrics @deprecated, use RQ_QUALITY_METRIC_COUNT */
183  int m_q;
184 
185  /* Number of quality metrics */
186  int m_rc;
187 
188  /* Quality metric coefficients*/
190 
191  /* Ressource costs coefficients*/
192  double co_RC[RQ_QUALITY_METRIC_COUNT];
193 
194  /* Diversity coefficient */
195  double co_D;
196 
197  /* Utility coefficient */
198  double co_U;
199 
200  /* Relativity coefficient */
201  double co_R;
202 
203  /* Minimum bandwidth assigned to an address */
204  unsigned int b_min;
205 
206  /* Minimum number of addresses with bandwidth assigned */
207  unsigned int n_min;
208 
209  /* Quotas */
210  /* Array mapping array index to ATS network */
211  int quota_index[GNUNET_NT_COUNT];
212  /* Outbound quotas */
213  unsigned long long quota_out[GNUNET_NT_COUNT];
214  /* Inbound quotas */
215 
216  unsigned long long quota_in[GNUNET_NT_COUNT];
217 
218  /* ATS ressource costs
219  * array with GNUNET_ATS_QualityPropertiesCount elements
220  * contains mapping to GNUNET_ATS_Property
221  * */
223 };
224 
230 
235 
239  struct MLP_Problem p;
240 
244  struct MLP_Variables pv;
245 
249  struct MLP_Solution ps;
250 
255 
260 
265 
270 
275 
280 
285 
292 
297 
302 
307 
312 
317 
322 
327 
332 
337 
342 
347 
352 
353 
357  enum MLP_Output_Format opt_log_format;
358 };
359 
367  uint32_t b_out;
368 
372  uint32_t b_in;
373 
377  int n;
378 
382  signed int c_b;
383 
387  signed int c_n;
388 
389  /* row indexes */
390 
394  unsigned int r_c1;
395 
399  unsigned int r_c3;
400 };
401 
402 
403 
506 #define LOG(kind, ...) GNUNET_log_from(kind, "ats-mlp", __VA_ARGS__)
507 
511 #define DEBUG_MLP_PROBLEM_CREATION GNUNET_NO
512 
513 
520 static int
521 mlp_term_hook(void *info, const char *s)
522 {
523  struct GAS_MLP_Handle *mlp = info;
524 
525  if (mlp->opt_dbg_glpk_verbose)
526  LOG(GNUNET_ERROR_TYPE_ERROR, "%s", s);
527  return 1;
528 }
529 
530 
539 static int
540 reset_peers(void *cls,
541  const struct GNUNET_PeerIdentity *key,
542  void *value)
543 {
544  struct ATS_Peer *peer = value;
545 
546  peer->processed = GNUNET_NO;
547  return GNUNET_OK;
548 }
549 
555 static void
557 {
558  int c;
559 
560  if (mlp == NULL)
561  return;
562  if (mlp->p.prob != NULL)
563  {
564  glp_delete_prob(mlp->p.prob);
565  mlp->p.prob = NULL;
566  }
567 
568  /* delete row index */
569  if (mlp->p.ia != NULL)
570  {
571  GNUNET_free(mlp->p.ia);
572  mlp->p.ia = NULL;
573  }
574 
575  /* delete column index */
576  if (mlp->p.ja != NULL)
577  {
578  GNUNET_free(mlp->p.ja);
579  mlp->p.ja = NULL;
580  }
581 
582  /* delete coefficients */
583  if (mlp->p.ar != NULL)
584  {
585  GNUNET_free(mlp->p.ar);
586  mlp->p.ar = NULL;
587  }
588  mlp->p.ci = 0;
589  mlp->p.prob = NULL;
590 
591  mlp->p.c_d = MLP_UNDEFINED;
592  mlp->p.c_r = MLP_UNDEFINED;
593  mlp->p.r_c2 = MLP_UNDEFINED;
594  mlp->p.r_c4 = MLP_UNDEFINED;
595  mlp->p.r_c6 = MLP_UNDEFINED;
596  mlp->p.r_c9 = MLP_UNDEFINED;
597  for (c = 0; c < RQ_QUALITY_METRIC_COUNT; c++)
598  mlp->p.r_q[c] = MLP_UNDEFINED;
599  for (c = 0; c < GNUNET_NT_COUNT; c++)
600  mlp->p.r_quota[c] = MLP_UNDEFINED;
601  mlp->p.ci = MLP_UNDEFINED;
602 
603 
605  &reset_peers, NULL);
606 }
607 
608 
614 static const char *
616 {
617  switch (retcode)
618  {
619  case GLP_UNDEF:
620  return "solution is undefined";
621 
622  case GLP_FEAS:
623  return "solution is feasible";
624 
625  case GLP_INFEAS:
626  return "solution is infeasible";
627 
628  case GLP_NOFEAS:
629  return "no feasible solution exists";
630 
631  case GLP_OPT:
632  return "solution is optimal";
633 
634  case GLP_UNBND:
635  return "solution is unbounded";
636 
637  default:
638  GNUNET_break(0);
639  return "unknown error";
640  }
641 }
642 
643 
649 static const char *
651 {
652  switch (retcode)
653  {
654  case 0:
655  return "ok";
656 
657  case GLP_EBADB:
658  return "invalid basis";
659 
660  case GLP_ESING:
661  return "singular matrix";
662 
663  case GLP_ECOND:
664  return "ill-conditioned matrix";
665 
666  case GLP_EBOUND:
667  return "invalid bounds";
668 
669  case GLP_EFAIL:
670  return "solver failed";
671 
672  case GLP_EOBJLL:
673  return "objective lower limit reached";
674 
675  case GLP_EOBJUL:
676  return "objective upper limit reached";
677 
678  case GLP_EITLIM:
679  return "iteration limit exceeded";
680 
681  case GLP_ETMLIM:
682  return "time limit exceeded";
683 
684  case GLP_ENOPFS:
685  return "no primal feasible solution";
686 
687  case GLP_ENODFS:
688  return "no dual feasible solution";
689 
690  case GLP_EROOT:
691  return "root LP optimum not provided";
692 
693  case GLP_ESTOP:
694  return "search terminated by application";
695 
696  case GLP_EMIPGAP:
697  return "relative mip gap tolerance reached";
698 
699  case GLP_ENOFEAS:
700  return "no dual feasible solution";
701 
702  case GLP_ENOCVG:
703  return "no convergence";
704 
705  case GLP_EINSTAB:
706  return "numerical instability";
707 
708  case GLP_EDATA:
709  return "invalid data";
710 
711  case GLP_ERANGE:
712  return "result out of range";
713 
714  default:
715  GNUNET_break(0);
716  return "unknown error";
717  }
718 }
719 
720 
721 struct CountContext {
723  int result;
724 };
725 
726 static int
728  const struct GNUNET_PeerIdentity *key,
729  void *value)
730 {
731  struct CountContext *cctx = cls;
732 
733  /* Check if we have to add this peer due to a pending request */
735  cctx->result++;
736  return GNUNET_OK;
737 }
738 
739 
740 static int
743 {
744  struct CountContext cctx;
745 
746  cctx.map = requested_peers;
747  cctx.result = 0;
750  return cctx.result;
751 }
752 
753 
754 static int
756  const struct GNUNET_PeerIdentity *key,
757  void *value)
758 {
759  struct CountContext *cctx = cls;
760 
761  /* Check if we have to addresses for the requested peer */
763  cctx->result++;
764  return GNUNET_OK;
765 }
766 
767 
768 static int
771 {
772  struct CountContext cctx;
773 
774  cctx.map = addresses;
775  cctx.result = 0;
778  return cctx.result;
779 }
780 
781 
795 static int
797  int row, int col, double val,
798  int line)
799 {
800  int c_cols;
801  int c_elems;
802  int c1;
803  int res;
804  int found;
805  double *val_array;
806  int *ind_array;
807 
808  GNUNET_assert(NULL != p->prob);
809 
810  /* Get number of columns and prepare data structure */
811  c_cols = glp_get_num_cols(p->prob);
812  if (0 >= c_cols)
813  return GNUNET_SYSERR;
814 
815  val_array = GNUNET_malloc((c_cols + 1) * sizeof(double));
816  GNUNET_assert(NULL != val_array);
817  ind_array = GNUNET_malloc((c_cols + 1) * sizeof(int));
818  GNUNET_assert(NULL != ind_array);
819  /* Extract the row */
820 
821  /* Update the value */
822  c_elems = glp_get_mat_row(p->prob, row, ind_array, val_array);
823  found = GNUNET_NO;
824  for (c1 = 1; c1 < (c_elems + 1); c1++)
825  {
826  if (ind_array[c1] == col)
827  {
828  found = GNUNET_YES;
829  break;
830  }
831  }
832  if (GNUNET_NO == found)
833  {
834  ind_array[c_elems + 1] = col;
835  val_array[c_elems + 1] = val;
836  LOG(GNUNET_ERROR_TYPE_DEBUG, "[P] Setting value in [%s : %s] to `%.2f'\n",
837  glp_get_row_name(p->prob, row), glp_get_col_name(p->prob, col),
838  val);
839  glp_set_mat_row(p->prob, row, c_elems + 1, ind_array, val_array);
840  GNUNET_free(ind_array);
841  GNUNET_free(val_array);
842  return GNUNET_YES;
843  }
844  else
845  {
846  /* Update value */
847  LOG(GNUNET_ERROR_TYPE_DEBUG, "[P] Updating value in [%s : %s] from `%.2f' to `%.2f'\n",
848  glp_get_row_name(p->prob, row), glp_get_col_name(p->prob, col),
849  val_array[c1], val);
850  if (val != val_array[c1])
851  res = GNUNET_YES;
852  else
853  res = GNUNET_NO;
854  val_array[c1] = val;
855  /* Update the row in the matrix */
856  glp_set_mat_row(p->prob, row, c_elems, ind_array, val_array);
857  }
858 
859  GNUNET_free(ind_array);
860  GNUNET_free(val_array);
861  return res;
862 }
863 
876 static void
878  int row, int col, double val,
879  int line)
880 {
881  if ((p->ci) >= p->num_elements)
882  {
883  LOG(GNUNET_ERROR_TYPE_DEBUG, "[P]: line %u: Request for index %u bigger than array size of %u\n",
884  line, p->ci + 1, p->num_elements);
885  GNUNET_break(0);
886  return;
887  }
888  if ((0 == row) || (0 == col))
889  {
890  GNUNET_break(0);
891  LOG(GNUNET_ERROR_TYPE_ERROR, "[P]: Invalid call from line %u: row = %u, col = %u\n",
892  line, row, col);
893  }
894  p->ia[p->ci] = row;
895  p->ja[p->ci] = col;
896  p->ar[p->ci] = val;
897 #if DEBUG_MLP_PROBLEM_CREATION
898  LOG(GNUNET_ERROR_TYPE_DEBUG, "[P]: line %u: Set value [%u,%u] in index %u == %.2f\n",
899  line, p->ia[p->ci], p->ja[p->ci], p->ci, p->ar[p->ci]);
900 #endif
901  p->ci++;
902 }
903 
904 static int
906  unsigned int type, unsigned int bound, double lb, double ub,
907  double coef)
908 {
909  int col = glp_add_cols(p->prob, 1);
910 
911  glp_set_col_name(p->prob, col, name);
912  glp_set_col_bnds(p->prob, col, bound, lb, ub);
913  glp_set_col_kind(p->prob, col, type);
914  glp_set_obj_coef(p->prob, col, coef);
915 #if DEBUG_MLP_PROBLEM_CREATION
916  LOG(GNUNET_ERROR_TYPE_DEBUG, "[P]: Added column [%u] `%s': %.2f\n",
917  col, name, coef);
918 #endif
919  return col;
920 }
921 
922 static int
924  unsigned int bound, double lb, double ub)
925 {
926  char * op;
927  int row = glp_add_rows(p->prob, 1);
928 
929  /* set row name */
930  glp_set_row_name(p->prob, row, name);
931  /* set row bounds: <= 0 */
932  glp_set_row_bnds(p->prob, row, bound, lb, ub);
933  switch (bound)
934  {
935  case GLP_UP:
936  GNUNET_asprintf(&op, "-inf <= x <= %.2f", ub);
937  break;
938 
939  case GLP_DB:
940  GNUNET_asprintf(&op, "%.2f <= x <= %.2f", lb, ub);
941  break;
942 
943  case GLP_FX:
944  GNUNET_asprintf(&op, "%.2f == x == %.2f", lb, ub);
945  break;
946 
947  case GLP_LO:
948  GNUNET_asprintf(&op, "%.2f <= x <= inf", lb);
949  break;
950 
951  default:
952  GNUNET_asprintf(&op, "ERROR");
953  break;
954  }
955 #if DEBUG_MLP_PROBLEM_CREATION
956  LOG(GNUNET_ERROR_TYPE_DEBUG, "[P]: Added row [%u] `%s': %s\n",
957  row, name, op);
958 #endif
959  GNUNET_free(op);
960  return row;
961 }
962 
970 static int
972  const struct GNUNET_PeerIdentity *key,
973  void *value)
974 {
975  struct GAS_MLP_Handle *mlp = cls;
976  struct MLP_Problem *p = &mlp->p;
977  struct ATS_Address *address = value;
978  struct ATS_Peer *peer;
979  struct MLP_information *mlpi;
980  char *name;
981  double cur_bigm;
982  uint32_t addr_net;
983  uint32_t addr_net_index;
984  unsigned long long max_quota;
985  int c;
986 
987  /* Check if we have to add this peer due to a pending request */
989  return GNUNET_OK;
990 
991  mlpi = address->solver_information;
992  if (NULL == mlpi)
993  {
994  fprintf(stderr, "%s %p\n", GNUNET_i2s(&address->peer), address);
995  GNUNET_break(0);
996  return GNUNET_OK;
997  }
998 
999  addr_net = address->properties.scope;
1000  for (addr_net_index = 0; addr_net_index < GNUNET_NT_COUNT; addr_net_index++)
1001  {
1002  if (mlp->pv.quota_index[addr_net_index] == addr_net)
1003  break;
1004  }
1005 
1006  if (addr_net_index >= GNUNET_NT_COUNT)
1007  {
1008  GNUNET_break(0);
1009  return GNUNET_OK;
1010  }
1011 
1012  max_quota = 0;
1013  for (c = 0; c < GNUNET_NT_COUNT; c++)
1014  {
1015  if (mlp->pv.quota_out[c] > max_quota)
1016  max_quota = mlp->pv.quota_out[c];
1017  if (mlp->pv.quota_in[c] > max_quota)
1018  max_quota = mlp->pv.quota_in[c];
1019  }
1020  if (max_quota > mlp->pv.BIG_M)
1021  cur_bigm = (double)mlp->pv.BIG_M;
1022  else
1023  cur_bigm = max_quota;
1024 
1025 
1026  /* Get peer */
1028  GNUNET_assert(NULL != peer);
1029  if (peer->processed == GNUNET_NO)
1030  {
1031  /* Add peer dependent constraints */
1032  /* Add c2) One address active per peer */
1033  GNUNET_asprintf(&name, "c2_%s", GNUNET_i2s(&address->peer));
1034  peer->r_c2 = mlp_create_problem_create_constraint(p, name, GLP_FX, 1.0, 1.0);
1035  GNUNET_free(name);
1036  if (GNUNET_NO == mlp->opt_dbg_feasibility_only)
1037  {
1039  {
1040  /* Add c9) Relativity */
1041  GNUNET_asprintf(&name, "c9_%s", GNUNET_i2s(&address->peer));
1042  peer->r_c9 = mlp_create_problem_create_constraint(p, name, GLP_LO, 0.0, 0.0);
1043  GNUNET_free(name);
1044  /* c9) set coefficient */
1045  mlp_create_problem_set_value(p, peer->r_c9, p->c_r, -peer->f, __LINE__);
1046  }
1047  }
1048  peer->processed = GNUNET_YES;
1049  }
1050 
1051  /* Reset addresses' solver information */
1052  mlpi->c_b = 0;
1053  mlpi->c_n = 0;
1054  mlpi->n = 0;
1055  mlpi->r_c1 = 0;
1056  mlpi->r_c3 = 0;
1057 
1058  /* Add bandwidth column */
1059  GNUNET_asprintf(&name, "b_%s_%s_%p", GNUNET_i2s(&address->peer), address->plugin, address);
1060  if (GNUNET_NO == mlp->opt_dbg_feasibility_only)
1061  {
1062  mlpi->c_b = mlp_create_problem_create_column(p, name, GLP_CV, GLP_LO, 0.0, 0.0, 0.0);
1063  }
1064  else
1065  {
1066  /* Maximize for bandwidth assignment in feasibility testing */
1067  mlpi->c_b = mlp_create_problem_create_column(p, name, GLP_CV, GLP_LO, 0.0, 0.0, 1.0);
1068  }
1069  GNUNET_free(name);
1070 
1071  /* Add address active column */
1072  GNUNET_asprintf(&name, "n_%s_%s_%p", GNUNET_i2s(&address->peer), address->plugin, address);
1073  mlpi->c_n = mlp_create_problem_create_column(p, name, GLP_IV, GLP_DB, 0.0, 1.0, 0.0);
1074  GNUNET_free(name);
1075 
1076  /* Add address dependent constraints */
1077  /* Add c1) bandwidth capping: b_t + (-M) * n_t <= 0 */
1078  GNUNET_asprintf(&name, "c1_%s_%s_%p", GNUNET_i2s(&address->peer), address->plugin, address);
1079  mlpi->r_c1 = mlp_create_problem_create_constraint(p, name, GLP_UP, 0.0, 0.0);
1080  GNUNET_free(name);
1081  /* c1) set b = 1 coefficient */
1082  mlp_create_problem_set_value(p, mlpi->r_c1, mlpi->c_b, 1, __LINE__);
1083  /* c1) set n = - min (M, quota) coefficient */
1084  cur_bigm = (double)mlp->pv.quota_out[addr_net_index];
1085  if (cur_bigm > mlp->pv.BIG_M)
1086  cur_bigm = (double)mlp->pv.BIG_M;
1087  mlp_create_problem_set_value(p, mlpi->r_c1, mlpi->c_n, -cur_bigm, __LINE__);
1088 
1089  /* Add constraint c 3) minimum bandwidth
1090  * b_t + (-n_t * b_min) >= 0
1091  * */
1092  GNUNET_asprintf(&name, "c3_%s_%s_%p", GNUNET_i2s(&address->peer), address->plugin, address);
1093  mlpi->r_c3 = mlp_create_problem_create_constraint(p, name, GLP_LO, 0.0, 0.0);
1094  GNUNET_free(name);
1095 
1096  /* c3) set b = 1 coefficient */
1097  mlp_create_problem_set_value(p, mlpi->r_c3, mlpi->c_b, 1, __LINE__);
1098  /* c3) set n = -b_min coefficient */
1099  mlp_create_problem_set_value(p, mlpi->r_c3, mlpi->c_n, -((double )mlp->pv.b_min), __LINE__);
1100 
1101 
1102  /* Set coefficient entries in invariant rows */
1103 
1104  /* Feasbility */
1105 
1106  /* c 4) minimum connections */
1107  mlp_create_problem_set_value(p, p->r_c4, mlpi->c_n, 1, __LINE__);
1108  /* c 2) 1 address peer peer */
1109  mlp_create_problem_set_value(p, peer->r_c2, mlpi->c_n, 1, __LINE__);
1110  /* c 10) obey network specific quotas
1111  * (1)*b_1 + ... + (1)*b_m <= quota_n
1112  */
1113  mlp_create_problem_set_value(p, p->r_quota[addr_net_index], mlpi->c_b, 1, __LINE__);
1114 
1115  /* Optimality */
1116  if (GNUNET_NO == mlp->opt_dbg_feasibility_only)
1117  {
1118  /* c 6) maximize diversity */
1119  mlp_create_problem_set_value(p, p->r_c6, mlpi->c_n, 1, __LINE__);
1120  /* c 9) relativity */
1122  mlp_create_problem_set_value(p, peer->r_c9, mlpi->c_b, 1, __LINE__);
1123  /* c 8) utility */
1125  mlp_create_problem_set_value(p, p->r_c8, mlpi->c_b, 1, __LINE__);
1126  /* c 7) Optimize quality */
1127  /* For all quality metrics, set quality of this address */
1129  {
1132  mlpi->c_b,
1133  address->norm_delay.norm,
1134  __LINE__);
1137  mlpi->c_b,
1138  address->norm_distance.norm,
1139  __LINE__);
1140  }
1141  }
1142 
1143  return GNUNET_OK;
1144 }
1145 
1146 
1150 static void
1152 {
1153  int c;
1154 
1155  /* Feasibility */
1156 
1157  /* Row for c4) minimum connection */
1158  /* Number of minimum connections is min(|Peers|, n_min) */
1159  p->r_c4 = mlp_create_problem_create_constraint(p, "c4", GLP_LO, (mlp->pv.n_min > p->num_peers) ? p->num_peers : mlp->pv.n_min, 0.0);
1160 
1161  /* Rows for c 10) Enforce network quotas */
1162  for (c = 0; c < GNUNET_NT_COUNT; c++)
1163  {
1164  char * text;
1165  GNUNET_asprintf(&text, "c10_quota_ats_%s",
1167  p->r_quota[c] = mlp_create_problem_create_constraint(p, text, GLP_DB, 0.0, mlp->pv.quota_out[c]);
1168  GNUNET_free(text);
1169  }
1170 
1171  /* Optimality */
1172  if (GNUNET_NO == mlp->opt_dbg_feasibility_only)
1173  {
1174  char *name;
1175  /* Add row for c6) Maximize for diversity */
1177  {
1178  p->r_c6 = mlp_create_problem_create_constraint(p, "c6", GLP_FX, 0.0, 0.0);
1179  /* Set c6 ) Setting -D */
1180  mlp_create_problem_set_value(p, p->r_c6, p->c_d, -1, __LINE__);
1181  }
1182 
1183  /* Adding rows for c 8) Maximize utility */
1185  {
1186  p->r_c8 = mlp_create_problem_create_constraint(p, "c8", GLP_FX, 0.0, 0.0);
1187  /* -u */
1188  mlp_create_problem_set_value(p, p->r_c8, p->c_u, -1, __LINE__);
1189  }
1190 
1191  /* For all quality metrics:
1192  * c 7) Maximize quality, austerity */
1194  {
1195  for (c = 0; c < mlp->pv.m_q; c++)
1196  {
1197  GNUNET_asprintf(&name,
1198  "c7_q%i_%s", c,
1199  print_quality_type(c));
1200  p->r_q[c] = mlp_create_problem_create_constraint(p, name, GLP_FX, 0.0, 0.0);
1201  GNUNET_free(name);
1203  p->r_q[c],
1204  p->c_q[c], -1, __LINE__);
1205  }
1206  }
1207  }
1208 }
1209 
1210 
1214 static void
1216 {
1217  if (GNUNET_NO == mlp->opt_dbg_feasibility_only)
1218  {
1219  char *name;
1220  int c;
1221 
1222  /* Diversity d column */
1224  p->c_d = mlp_create_problem_create_column(p, "d", GLP_CV, GLP_LO, 0.0, 0.0, mlp->pv.co_D);
1225 
1226  /* Utilization u column */
1228  p->c_u = mlp_create_problem_create_column(p, "u", GLP_CV, GLP_LO, 0.0, 0.0, mlp->pv.co_U);
1229 
1230  /* Relativity r column */
1232  p->c_r = mlp_create_problem_create_column(p, "r", GLP_CV, GLP_LO, 0.0, 0.0, mlp->pv.co_R);
1233 
1234  /* Quality metric columns */
1236  {
1237  for (c = 0; c < mlp->pv.m_q; c++)
1238  {
1239  GNUNET_asprintf(&name, "q_%u", c);
1240  p->c_q[c] = mlp_create_problem_create_column(p, name, GLP_CV, GLP_LO, 0.0, 0.0, mlp->pv.co_Q[c]);
1241  GNUNET_free(name);
1242  }
1243  }
1244  }
1245 }
1246 
1247 
1254 static int
1256 {
1257  struct MLP_Problem *p = &mlp->p;
1258  int res = GNUNET_OK;
1259 
1260  GNUNET_assert(p->prob == NULL);
1261  GNUNET_assert(p->ia == NULL);
1262  GNUNET_assert(p->ja == NULL);
1263  GNUNET_assert(p->ar == NULL);
1264  /* Reset MLP problem struct */
1265 
1266  /* create the glpk problem */
1267  p->prob = glp_create_prob();
1268  GNUNET_assert(NULL != p->prob);
1271  mlp->env->addresses);
1272 
1273  /* Create problem matrix: 10 * #addresses + #q * #addresses + #q, + #peer + 2 + 1 */
1274  p->num_elements = (10 * p->num_addresses + mlp->pv.m_q * p->num_addresses +
1275  mlp->pv.m_q + p->num_peers + 2 + 1);
1277  "Rebuilding problem for %u peer(s) and %u addresse(s) and %u quality metrics == %u elements\n",
1278  p->num_peers,
1279  p->num_addresses,
1280  mlp->pv.m_q,
1281  p->num_elements);
1282 
1283  /* Set a problem name */
1284  glp_set_prob_name(p->prob, "GNUnet ATS bandwidth distribution");
1285  /* Set optimization direction to maximize */
1286  glp_set_obj_dir(p->prob, GLP_MAX);
1287 
1288  /* Create problem matrix */
1289  /* last +1 caused by glpk index starting with one: [1..elements]*/
1290  p->ci = 1;
1291  /* row index */
1292  p->ia = GNUNET_malloc(p->num_elements * sizeof(int));
1293  /* column index */
1294  p->ja = GNUNET_malloc(p->num_elements * sizeof(int));
1295  /* coefficient */
1296  p->ar = GNUNET_malloc(p->num_elements * sizeof(double));
1297 
1298  if ((NULL == p->ia) || (NULL == p->ja) || (NULL == p->ar))
1299  {
1300  LOG(GNUNET_ERROR_TYPE_ERROR, _("Problem size too large, cannot allocate memory!\n"));
1301  return GNUNET_SYSERR;
1302  }
1303 
1304  /* Adding invariant columns */
1306 
1307  /* Adding address independent constraint rows */
1309 
1310  /* Adding address dependent columns constraint rows */
1313  mlp);
1314 
1315  /* Load the matrix */
1316  LOG(GNUNET_ERROR_TYPE_DEBUG, "Loading matrix\n");
1317  glp_load_matrix(p->prob, (p->ci) - 1, p->ia, p->ja, p->ar);
1319  {
1320  glp_scale_prob(p->prob, GLP_SF_AUTO);
1321  }
1322 
1323  return res;
1324 }
1325 
1326 
1333 static int
1335 {
1336  int res = 0;
1337  int res_status = 0;
1338 
1339  res = glp_simplex(mlp->p.prob, &mlp->control_param_lp);
1340  if (0 == res)
1341  LOG(GNUNET_ERROR_TYPE_DEBUG, "Solving LP problem: %s\n",
1342  mlp_solve_to_string(res));
1343  else
1344  LOG(GNUNET_ERROR_TYPE_DEBUG, "Solving LP problem failed: %s\n",
1345  mlp_solve_to_string(res));
1346 
1347  /* Analyze problem status */
1348  res_status = glp_get_status(mlp->p.prob);
1349  switch (res_status)
1350  {
1351  case GLP_OPT: /* solution is optimal */
1353  "Solving LP problem: %s, %s\n",
1354  mlp_solve_to_string(res),
1355  mlp_status_to_string(res_status));
1356  return GNUNET_OK;
1357 
1358  default:
1360  "Solving LP problem failed: %s %s\n",
1361  mlp_solve_to_string(res),
1362  mlp_status_to_string(res_status));
1363  return GNUNET_SYSERR;
1364  }
1365 }
1366 
1367 
1376 static int
1378  const struct GNUNET_PeerIdentity *key,
1379  void *value)
1380 {
1381  struct GAS_MLP_Handle *mlp = cls;
1382  struct ATS_Address *address;
1383  struct MLP_information *mlpi;
1384  double mlp_bw_in = MLP_NaN;
1385  double mlp_bw_out = MLP_NaN;
1386  double mlp_use = MLP_NaN;
1387 
1388  /* Check if we have to add this peer due to a pending request */
1390  key))
1391  {
1392  return GNUNET_OK;
1393  }
1394  address = value;
1395  GNUNET_assert(address->solver_information != NULL);
1396  mlpi = address->solver_information;
1397 
1398  mlp_bw_in = glp_mip_col_val(mlp->p.prob, mlpi->c_b);/* FIXME */
1399  if (mlp_bw_in > (double)UINT32_MAX)
1400  {
1401  LOG(GNUNET_ERROR_TYPE_DEBUG, "Overflow in assigned bandwidth, reducing ...\n");
1402  mlp_bw_in = (double)UINT32_MAX;
1403  }
1404  mlp_bw_out = glp_mip_col_val(mlp->p.prob, mlpi->c_b);
1405  if (mlp_bw_out > (double)UINT32_MAX)
1406  {
1407  LOG(GNUNET_ERROR_TYPE_DEBUG, "Overflow in assigned bandwidth, reducing ...\n");
1408  mlp_bw_out = (double)UINT32_MAX;
1409  }
1410  mlp_use = glp_mip_col_val(mlp->p.prob, mlpi->c_n);
1411 
1412  /*
1413  * Debug: solution
1414  * LOG (GNUNET_ERROR_TYPE_INFO, "MLP result address: `%s' `%s' length %u session %u, mlp use %.3f\n",
1415  * GNUNET_i2s(&address->peer), address->plugin,
1416  * address->addr_len, address->session_id);
1417  */
1418 
1419  if (GLP_YES == mlp_use)
1420  {
1421  /* This address was selected by the solver to be used */
1422  mlpi->n = GNUNET_YES;
1423  if (GNUNET_NO == address->active)
1424  {
1425  /* Address was not used before, enabling address */
1426  LOG(GNUNET_ERROR_TYPE_DEBUG, "%s %.2f : enabling address\n",
1427  (1 == mlp_use) ? "[x]" : "[ ]", mlp_bw_out);
1428  address->active = GNUNET_YES;
1429  address->assigned_bw_in = mlp_bw_in;
1430  mlpi->b_in = mlp_bw_in;
1431  address->assigned_bw_out = mlp_bw_out;
1432  mlpi->b_out = mlp_bw_out;
1433  if ((NULL == mlp->exclude_peer) || (0 != GNUNET_memcmp(&address->peer, mlp->exclude_peer)))
1434  mlp->env->bandwidth_changed_cb(mlp->env->cls, address);
1435  return GNUNET_OK;
1436  }
1437  else if (GNUNET_YES == address->active)
1438  {
1439  /* Address was used before, check for bandwidth change */
1440  if ((mlp_bw_out != address->assigned_bw_out) ||
1441  (mlp_bw_in != address->assigned_bw_in))
1442  {
1443  LOG(GNUNET_ERROR_TYPE_DEBUG, "%s %.2f : bandwidth changed\n",
1444  (1 == mlp_use) ? "[x]" : "[ ]", mlp_bw_out);
1445  address->assigned_bw_in = mlp_bw_in;
1446  mlpi->b_in = mlp_bw_in;
1447  address->assigned_bw_out = mlp_bw_out;
1448  mlpi->b_out = mlp_bw_out;
1449  if ((NULL == mlp->exclude_peer) || (0 != GNUNET_memcmp(&address->peer, mlp->exclude_peer)))
1450  mlp->env->bandwidth_changed_cb(mlp->env->cls, address);
1451  return GNUNET_OK;
1452  }
1453  }
1454  else
1455  GNUNET_break(0);
1456  }
1457  else if (GLP_NO == mlp_use)
1458  {
1459  /* This address was selected by the solver to be not used */
1460  mlpi->n = GNUNET_NO;
1461  if (GNUNET_NO == address->active)
1462  {
1463  /* Address was not used before, nothing to do */
1464  LOG(GNUNET_ERROR_TYPE_DEBUG, "%s %.2f : no change\n",
1465  (1 == mlp_use) ? "[x]" : "[ ]", mlp_bw_out);
1466  return GNUNET_OK;
1467  }
1468  else if (GNUNET_YES == address->active)
1469  {
1470  /* Address was used before, disabling address */
1471  LOG(GNUNET_ERROR_TYPE_DEBUG, "%s %.2f : disabling address\n",
1472  (1 == mlp_use) ? "[x]" : "[ ]", mlp_bw_out);
1473  address->active = GNUNET_NO;
1474  /* Set bandwidth to 0 */
1475  address->assigned_bw_in = 0;
1476  mlpi->b_in = 0;
1477  address->assigned_bw_out = 0;
1478  mlpi->b_out = 0;
1479  return GNUNET_OK;
1480  }
1481  else
1482  GNUNET_break(0);
1483  }
1484  else
1485  GNUNET_break(0);
1486 
1487  return GNUNET_OK;
1488 }
1489 
1490 
1491 static void
1493  enum GAS_Solver_Operation op,
1494  enum GAS_Solver_Status stat,
1496 {
1497  mlp->env->info_cb(mlp->env->cls,
1498  op,
1499  stat,
1500  add);
1501 }
1502 
1503 
1504 static void
1505 mlp_branch_and_cut_cb(glp_tree *tree, void *info)
1506 {
1507  struct GAS_MLP_Handle *mlp = info;
1508  double mlp_obj = 0;
1509 
1510  switch (glp_ios_reason(tree))
1511  {
1512  case GLP_ISELECT:
1513  /* Do nothing here */
1514  break;
1515 
1516  case GLP_IPREPRO:
1517  /* Do nothing here */
1518  break;
1519 
1520  case GLP_IROWGEN:
1521  /* Do nothing here */
1522  break;
1523 
1524  case GLP_IHEUR:
1525  /* Do nothing here */
1526  break;
1527 
1528  case GLP_ICUTGEN:
1529  /* Do nothing here */
1530  break;
1531 
1532  case GLP_IBRANCH:
1533  /* Do nothing here */
1534  break;
1535 
1536  case GLP_IBINGO:
1537  /* A better solution was found */
1538  mlp->ps.mlp_gap = glp_ios_mip_gap(tree);
1539  mlp_obj = glp_mip_obj_val(mlp->p.prob);
1540  mlp->ps.lp_mlp_gap = (abs(mlp_obj - mlp->ps.lp_objective_value)) / (abs(mlp_obj) + DBL_EPSILON);
1541 
1543  "Found better integer solution, current gaps: %.3f <= %.3f, %.3f <= %.3f\n",
1544  mlp->ps.mlp_gap, mlp->pv.mip_gap,
1545  mlp->ps.lp_mlp_gap, mlp->pv.lp_mip_gap);
1546 
1547  if (mlp->ps.mlp_gap <= mlp->pv.mip_gap)
1548  {
1550  "Current LP/MLP gap of %.3f smaller than tolerated gap of %.3f, terminating search\n",
1551  mlp->ps.lp_mlp_gap, mlp->pv.lp_mip_gap);
1552  glp_ios_terminate(tree);
1553  }
1554 
1555  if (mlp->ps.lp_mlp_gap <= mlp->pv.lp_mip_gap)
1556  {
1558  "Current LP/MLP gap of %.3f smaller than tolerated gap of %.3f, terminating search\n",
1559  mlp->ps.lp_mlp_gap, mlp->pv.lp_mip_gap);
1560  glp_ios_terminate(tree);
1561  }
1562 
1563  break;
1564 
1565  default:
1566  break;
1567  }
1568  //GNUNET_break (0);
1569 }
1570 
1571 
1578 static int
1580 {
1581  struct GAS_MLP_Handle *mlp = solver;
1582  char *filename;
1583  int res_lp = 0;
1584  int mip_res = 0;
1585  int mip_status = 0;
1586 
1587  struct GNUNET_TIME_Absolute start_total;
1588  struct GNUNET_TIME_Absolute start_cur_op;
1589  struct GNUNET_TIME_Relative dur_total;
1590  struct GNUNET_TIME_Relative dur_setup;
1591  struct GNUNET_TIME_Relative dur_lp;
1592  struct GNUNET_TIME_Relative dur_mlp;
1593 
1594  GNUNET_assert(NULL != solver);
1595  dur_lp = GNUNET_TIME_UNIT_ZERO;
1596 
1597  if (GNUNET_YES == mlp->stat_bulk_lock)
1598  {
1599  mlp->stat_bulk_requests++;
1600  return GNUNET_NO;
1601  }
1604  start_total = GNUNET_TIME_absolute_get();
1605 
1607  {
1609  return GNUNET_OK; /* No pending requests */
1610  }
1612  {
1614  return GNUNET_OK; /* No addresses available */
1615  }
1616 
1617  if ((GNUNET_NO == mlp->stat_mlp_prob_changed)
1618  && (GNUNET_NO == mlp->stat_mlp_prob_updated))
1619  {
1620  LOG(GNUNET_ERROR_TYPE_DEBUG, "No changes to problem\n");
1622  return GNUNET_OK;
1623  }
1624  if (GNUNET_YES == mlp->stat_mlp_prob_changed)
1625  {
1626  LOG(GNUNET_ERROR_TYPE_DEBUG, "Problem size changed, rebuilding\n");
1628  mlp_delete_problem(mlp);
1629  if (GNUNET_SYSERR == mlp_create_problem(mlp))
1630  {
1632  return GNUNET_SYSERR;
1633  }
1635  if (GNUNET_NO == mlp->opt_dbg_intopt_presolver)
1636  {
1637  mlp->control_param_lp.presolve = GLP_YES; /* LP presolver, we need lp solution */
1638  mlp->control_param_mlp.presolve = GNUNET_NO; /* No presolver, we have LP solution */
1639  }
1640  else
1641  {
1642  mlp->control_param_lp.presolve = GNUNET_NO; /* LP presolver, we need lp solution */
1643  mlp->control_param_mlp.presolve = GLP_YES; /* No presolver, we have LP solution */
1644  dur_lp = GNUNET_TIME_UNIT_ZERO;
1645  }
1646  }
1647  else
1648  {
1649  LOG(GNUNET_ERROR_TYPE_DEBUG, "Problem was updated, resolving\n");
1650  }
1651 
1652  /* Reset solution info */
1653  mlp->ps.lp_objective_value = 0.0;
1654  mlp->ps.mlp_gap = 1.0;
1655  mlp->ps.mlp_objective_value = 0.0;
1656  mlp->ps.lp_mlp_gap = 0.0;
1657 
1658  dur_setup = GNUNET_TIME_absolute_get_duration(start_total);
1659 
1660  /* Run LP solver */
1661  if (GNUNET_NO == mlp->opt_dbg_intopt_presolver)
1662  {
1664  (GNUNET_YES == mlp->stat_mlp_prob_changed) ? GAS_INFO_FULL : GAS_INFO_UPDATED);
1666  "Running LP solver %s\n",
1667  (GLP_YES == mlp->control_param_lp.presolve) ? "with presolver" : "without presolver");
1668  start_cur_op = GNUNET_TIME_absolute_get();
1669 
1670  /* Solve LP */
1671  /* Only for debugging:
1672  * Always use LP presolver:
1673  * mlp->control_param_lp.presolve = GLP_YES; */
1674  res_lp = mlp_solve_lp_problem(mlp);
1675  if (GNUNET_OK == res_lp)
1676  {
1677  mlp->ps.lp_objective_value = glp_get_obj_val(mlp->p.prob);
1679  "LP solution was: %.3f\n",
1680  mlp->ps.lp_objective_value);
1681  }
1682 
1683  dur_lp = GNUNET_TIME_absolute_get_duration(start_cur_op);
1685  (GNUNET_OK == res_lp) ? GAS_STAT_SUCCESS : GAS_STAT_FAIL,
1686  (GNUNET_YES == mlp->stat_mlp_prob_changed) ? GAS_INFO_FULL : GAS_INFO_UPDATED);
1687  }
1688 
1690  res_lp = GNUNET_OK;
1691 
1692  /* Run MLP solver */
1693  if ((GNUNET_OK == res_lp) || (GNUNET_YES == mlp->opt_dbg_intopt_presolver))
1694  {
1695  LOG(GNUNET_ERROR_TYPE_DEBUG, "Running MLP solver \n");
1697  (GNUNET_YES == mlp->stat_mlp_prob_changed) ? GAS_INFO_FULL : GAS_INFO_UPDATED);
1698  start_cur_op = GNUNET_TIME_absolute_get();
1699 
1700  /* Solve MIP */
1701 
1702  /* Only for debugging, always use LP presolver */
1704  mlp->control_param_mlp.presolve = GNUNET_YES;
1705 
1706  mip_res = glp_intopt(mlp->p.prob, &mlp->control_param_mlp);
1707  switch (mip_res)
1708  {
1709  case 0:
1710  /* Successful */
1712  "Solving MLP problem: %s\n",
1713  mlp_solve_to_string(mip_res));
1714  break;
1715 
1716  case GLP_ETMLIM: /* Time limit reached */
1717  case GLP_EMIPGAP: /* MIP gap tolerance limit reached */
1718  case GLP_ESTOP: /* Solver was instructed to stop*/
1719  /* Semi-successful */
1721  "Solving MLP problem solution was interupted: %s\n",
1722  mlp_solve_to_string(mip_res));
1723  break;
1724 
1725  case GLP_EBOUND:
1726  case GLP_EROOT:
1727  case GLP_ENOPFS:
1728  case GLP_ENODFS:
1729  case GLP_EFAIL:
1730  default:
1731  /* Fail */
1733  "Solving MLP problem failed: %s\n",
1734  mlp_solve_to_string(mip_res));
1735  break;
1736  }
1737 
1738  /* Analyze problem status */
1739  mip_status = glp_mip_status(mlp->p.prob);
1740  switch (mip_status)
1741  {
1742  case GLP_OPT: /* solution is optimal */
1744  "Solution of MLP problem is optimal: %s, %s\n",
1745  mlp_solve_to_string(mip_res),
1746  mlp_status_to_string(mip_status));
1747  mip_res = GNUNET_OK;
1748  break;
1749 
1750  case GLP_FEAS: /* solution is feasible but not proven optimal */
1751 
1752  if ((mlp->ps.mlp_gap <= mlp->pv.mip_gap) ||
1753  (mlp->ps.lp_mlp_gap <= mlp->pv.lp_mip_gap))
1754  {
1756  "Solution of MLP problem is feasible and solution within gap constraints: %s, %s\n",
1757  mlp_solve_to_string(mip_res),
1758  mlp_status_to_string(mip_status));
1759  mip_res = GNUNET_OK;
1760  }
1761  else
1762  {
1764  "Solution of MLP problem is feasible but solution not within gap constraints: %s, %s\n",
1765  mlp_solve_to_string(mip_res),
1766  mlp_status_to_string(mip_status));
1767  mip_res = GNUNET_SYSERR;
1768  }
1769  break;
1770 
1771  case GLP_UNDEF: /* Solution undefined */
1772  case GLP_NOFEAS: /* No feasible solution */
1773  default:
1775  "Solving MLP problem failed: %s %s\n",
1776  mlp_solve_to_string(mip_res),
1777  mlp_status_to_string(mip_status));
1778  mip_res = GNUNET_SYSERR;
1779  break;
1780  }
1781 
1782  dur_mlp = GNUNET_TIME_absolute_get_duration(start_cur_op);
1783  dur_total = GNUNET_TIME_absolute_get_duration(start_total);
1784 
1786  (GNUNET_OK == mip_res) ? GAS_STAT_SUCCESS : GAS_STAT_FAIL,
1787  (GNUNET_YES == mlp->stat_mlp_prob_changed) ? GAS_INFO_FULL : GAS_INFO_UPDATED);
1788  }
1789  else
1790  {
1791  /* Do not execute mip solver since lp solution is invalid */
1792  dur_mlp = GNUNET_TIME_UNIT_ZERO;
1793  dur_total = GNUNET_TIME_absolute_get_duration(start_total);
1794 
1796  (GNUNET_YES == mlp->stat_mlp_prob_changed) ? GAS_INFO_FULL : GAS_INFO_UPDATED);
1797  mip_res = GNUNET_SYSERR;
1798  }
1799 
1800  /* Notify about end */
1802  ((GNUNET_OK == mip_res) && (GNUNET_OK == mip_res)) ? GAS_STAT_SUCCESS : GAS_STAT_FAIL,
1803  (GNUNET_YES == mlp->stat_mlp_prob_changed) ? GAS_INFO_FULL : GAS_INFO_UPDATED);
1804 
1806  "Execution time for %s solve: (total/setup/lp/mlp) : %llu %llu %llu %llu\n",
1807  (GNUNET_YES == mlp->stat_mlp_prob_changed) ? "full" : "updated",
1808  (unsigned long long)dur_total.rel_value_us,
1809  (unsigned long long)dur_setup.rel_value_us,
1810  (unsigned long long)dur_lp.rel_value_us,
1811  (unsigned long long)dur_mlp.rel_value_us);
1812 
1813  /* Save stats */
1814  mlp->ps.lp_res = res_lp;
1815  mlp->ps.mip_res = mip_res;
1816  mlp->ps.lp_presolv = mlp->control_param_lp.presolve;
1817  mlp->ps.mip_presolv = mlp->control_param_mlp.presolve;
1818  mlp->ps.p_cols = glp_get_num_cols(mlp->p.prob);
1819  mlp->ps.p_rows = glp_get_num_rows(mlp->p.prob);
1820  mlp->ps.p_elements = mlp->p.num_elements;
1821 
1822  /* Propagate result*/
1824  (GNUNET_OK == res_lp) && (GNUNET_OK == mip_res) ? GAS_STAT_SUCCESS : GAS_STAT_FAIL,
1825  GAS_INFO_NONE);
1826  if ((GNUNET_OK == res_lp) && (GNUNET_OK == mip_res))
1827  {
1829  &mlp_propagate_results, mlp);
1830  }
1832  (GNUNET_OK == res_lp) && (GNUNET_OK == mip_res) ? GAS_STAT_SUCCESS : GAS_STAT_FAIL,
1833  GAS_INFO_NONE);
1834 
1836  if ((GNUNET_YES == mlp->opt_dump_problem_all) ||
1837  (mlp->opt_dump_problem_on_fail && ((GNUNET_OK != res_lp) || (GNUNET_OK != mip_res))))
1838  {
1839  /* Write problem to disk */
1840  switch (mlp->opt_log_format)
1841  {
1842  case MLP_CPLEX:
1843  GNUNET_asprintf(&filename, "problem_p_%u_a%u_%llu.cplex", mlp->p.num_peers,
1844  mlp->p.num_addresses, time.abs_value_us);
1845  glp_write_lp(mlp->p.prob, NULL, filename);
1846  break;
1847 
1848  case MLP_GLPK:
1849  GNUNET_asprintf(&filename, "problem_p_%u_a%u_%llu.glpk", mlp->p.num_peers,
1850  mlp->p.num_addresses, time.abs_value_us);
1851  glp_write_prob(mlp->p.prob, 0, filename);
1852  break;
1853 
1854  case MLP_MPS:
1855  GNUNET_asprintf(&filename, "problem_p_%u_a%u_%llu.mps", mlp->p.num_peers,
1856  mlp->p.num_addresses, time.abs_value_us);
1857  glp_write_mps(mlp->p.prob, GLP_MPS_FILE, NULL, filename);
1858  break;
1859 
1860  default:
1861  break;
1862  }
1863  LOG(GNUNET_ERROR_TYPE_ERROR, "Dumped problem to file: `%s' \n", filename);
1864  GNUNET_free(filename);
1865  }
1866  if ((mlp->opt_dump_solution_all) ||
1867  (mlp->opt_dump_solution_on_fail && ((GNUNET_OK != res_lp) || (GNUNET_OK != mip_res))))
1868  {
1869  /* Write solution to disk */
1870  GNUNET_asprintf(&filename, "problem_p_%u_a%u_%llu.sol", mlp->p.num_peers,
1871  mlp->p.num_addresses, time.abs_value_us);
1872  glp_print_mip(mlp->p.prob, filename);
1873  LOG(GNUNET_ERROR_TYPE_ERROR, "Dumped solution to file: `%s' \n", filename);
1874  GNUNET_free(filename);
1875  }
1876 
1877  /* Reset change and update marker */
1878  mlp->control_param_lp.presolve = GLP_NO;
1881 
1882  if ((GNUNET_OK == res_lp) && (GNUNET_OK == mip_res))
1883  return GNUNET_OK;
1884  else
1885  return GNUNET_SYSERR;
1886 }
1887 
1895 static void
1896 GAS_mlp_address_add(void *solver,
1897  struct ATS_Address *address,
1898  uint32_t network)
1899 {
1900  struct GAS_MLP_Handle *mlp = solver;
1901 
1902  if (GNUNET_NT_COUNT <= network)
1903  {
1904  GNUNET_break(0);
1905  return;
1906  }
1907 
1908  if (NULL == address->solver_information)
1909  {
1910  address->solver_information = GNUNET_new(struct MLP_information);
1911  }
1912  else
1914  _("Adding address for peer `%s' multiple times\n"),
1915  GNUNET_i2s(&address->peer));
1916 
1917  /* Is this peer included in the problem? */
1918  if (NULL ==
1920  &address->peer))
1921  {
1922  /* FIXME: should this be an error? */
1924  "Adding address for peer `%s' without address request\n",
1925  GNUNET_i2s(&address->peer));
1926  return;
1927  }
1928 
1930  "Adding address for peer `%s' with address request \n",
1931  GNUNET_i2s(&address->peer));
1932  /* Problem size changed: new address for peer with pending request */
1934  if (GNUNET_YES == mlp->opt_mlp_auto_solve)
1935  GAS_mlp_solve_problem(solver);
1936 }
1937 
1938 
1945 static void
1947  struct ATS_Address *address)
1948 {
1949  struct MLP_information *mlpi = address->solver_information;
1950  struct GAS_MLP_Handle *mlp = solver;
1951 
1952  if (NULL == mlp->p.prob)
1953  return; /* There is no MLP problem to update yet */
1954 
1955  if (NULL == mlpi)
1956  {
1958  _("Updating address property for peer `%s' %p not added before\n"),
1959  GNUNET_i2s(&address->peer),
1960  address);
1961  GNUNET_break(0);
1962  return;
1963  }
1964  if (NULL ==
1966  &address->peer))
1967  {
1968  /* Peer is not requested, so no need to update problem */
1969  return;
1970  }
1972  "Updating properties for peer `%s'\n",
1973  GNUNET_i2s(&address->peer));
1974 
1976  return;
1977 
1978  /* Update c7) [r_q[index]][c_b] = f_q * q_averaged[type_index] */
1979  if ((GNUNET_YES ==
1982  mlpi->c_b,
1983  address->norm_delay.norm,
1984  __LINE__)) ||
1985  (GNUNET_YES ==
1988  mlpi->c_b,
1989  address->norm_distance.norm,
1990  __LINE__)))
1991  {
1993  if (GNUNET_YES == mlp->opt_mlp_auto_solve)
1994  GAS_mlp_solve_problem(solver);
1995  }
1996 }
1997 
1998 
2006 static int
2008  const struct GNUNET_PeerIdentity *key,
2009  void *value)
2010 {
2011  static int counter = 0;
2012  struct ATS_Address **aa = cls;
2013  struct ATS_Address *addr = value;
2014  struct MLP_information *mlpi = addr->solver_information;
2015 
2016  if (mlpi == NULL)
2017  return GNUNET_YES;
2018 
2019  /*
2020  * Debug output
2021  * GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
2022  * "MLP [%u] Peer `%s' %s length %u session %u active %s mlp active %s\n",
2023  * counter, GNUNET_i2s (&addr->peer), addr->plugin, addr->addr_len, addr->session_id,
2024  * (GNUNET_YES == addr->active) ? "active" : "inactive",
2025  * (GNUNET_YES == mlpi->n) ? "active" : "inactive");
2026  */
2027 
2028  if (GNUNET_YES == mlpi->n)
2029  {
2030  (*aa) = addr;
2031  (*aa)->assigned_bw_in = mlpi->b_in;
2032  (*aa)->assigned_bw_out = mlpi->b_out;
2033  return GNUNET_NO;
2034  }
2035  counter++;
2036  return GNUNET_YES;
2037 }
2038 
2039 
2040 static double
2042  const struct GNUNET_PeerIdentity *peer)
2043 {
2044  double res;
2045  const double *preferences;
2046  int c;
2047 
2048  preferences = mlp->env->get_preferences(mlp->env->cls, peer);
2049  res = 0.0;
2050  for (c = 0; c < GNUNET_ATS_PREFERENCE_END; c++)
2051  {
2052  /* fprintf (stderr, "VALUE[%u] %s %.3f \n",
2053  * c, GNUNET_i2s (&cur->addr->peer), t[c]); */
2054  res += preferences[c];
2055  }
2056 
2058  res += 1.0;
2059 
2061  "Peer preference for peer `%s' == %.2f\n",
2062  GNUNET_i2s(peer), res);
2063 
2064  return res;
2065 }
2066 
2067 
2074 static void
2076  const struct GNUNET_PeerIdentity *peer)
2077 {
2078  struct GAS_MLP_Handle *mlp = solver;
2079  struct ATS_Peer *p;
2080  struct ATS_Address *res;
2081 
2083  "Getting preferred address for `%s'\n",
2084  GNUNET_i2s(peer));
2085 
2086  /* Is this peer included in the problem? */
2087  if (NULL ==
2089  peer))
2090  {
2091  LOG(GNUNET_ERROR_TYPE_INFO, "Adding peer `%s' to list of requested_peers with requests\n",
2092  GNUNET_i2s(peer));
2093 
2094  p = GNUNET_new(struct ATS_Peer);
2095  p->id = (*peer);
2096  p->f = get_peer_pref_value(mlp, peer);
2098  peer, p,
2100 
2101  /* Added new peer, we have to rebuild problem before solving */
2103 
2104  if ((GNUNET_YES == mlp->opt_mlp_auto_solve) &&
2106  peer)))
2107  {
2108  mlp->exclude_peer = peer;
2109  GAS_mlp_solve_problem(mlp);
2110  mlp->exclude_peer = NULL;
2111  }
2112  }
2113  /* Get prefered address */
2114  res = NULL;
2117  if (NULL != res)
2118  mlp->env->bandwidth_changed_cb(mlp->env->cls,
2119  res);
2120 }
2121 
2122 
2131 static void
2133  struct ATS_Address *address)
2134 {
2135  struct GAS_MLP_Handle *mlp = solver;
2136  struct MLP_information *mlpi;
2137  struct ATS_Address *res;
2138  int was_active;
2139 
2140  mlpi = address->solver_information;
2141  if (NULL != mlpi)
2142  {
2143  /* Remove full address */
2144  GNUNET_free(mlpi);
2145  address->solver_information = NULL;
2146  }
2147  was_active = address->active;
2148  address->active = GNUNET_NO;
2149  address->assigned_bw_in = 0;
2150  address->assigned_bw_out = 0;
2151 
2152  /* Is this peer included in the problem? */
2153  if (NULL ==
2155  &address->peer))
2156  {
2158  "Deleting address for peer `%s' without address request \n",
2159  GNUNET_i2s(&address->peer));
2160  return;
2161  }
2163  "Deleting address for peer `%s' with address request \n",
2164  GNUNET_i2s(&address->peer));
2165 
2166  /* Problem size changed: new address for peer with pending request */
2168  if (GNUNET_YES == mlp->opt_mlp_auto_solve)
2169  {
2170  GAS_mlp_solve_problem(solver);
2171  }
2172  if (GNUNET_YES == was_active)
2173  {
2174  GAS_mlp_get_preferred_address(solver, &address->peer);
2175  res = NULL;
2177  &address->peer,
2179  &res);
2180  if (NULL == res)
2181  {
2182  /* No alternative address, disconnecting peer */
2183  mlp->env->bandwidth_changed_cb(mlp->env->cls, address);
2184  }
2185  }
2186 }
2187 
2188 
2194 static void
2195 GAS_mlp_bulk_start(void *solver)
2196 {
2197  struct GAS_MLP_Handle *s = solver;
2198 
2200  "Locking solver for bulk operation ...\n");
2201  GNUNET_assert(NULL != solver);
2202  s->stat_bulk_lock++;
2203 }
2204 
2205 
2206 static void
2207 GAS_mlp_bulk_stop(void *solver)
2208 {
2209  struct GAS_MLP_Handle *s = solver;
2210 
2212  "Unlocking solver from bulk operation ...\n");
2213  GNUNET_assert(NULL != solver);
2214 
2215  if (s->stat_bulk_lock < 1)
2216  {
2217  GNUNET_break(0);
2218  return;
2219  }
2220  s->stat_bulk_lock--;
2221 
2222  if (0 < s->stat_bulk_requests)
2223  {
2224  GAS_mlp_solve_problem(solver);
2225  s->stat_bulk_requests = 0;
2226  }
2227 }
2228 
2229 
2230 
2237 static void
2239  const struct GNUNET_PeerIdentity *peer)
2240 {
2241  struct GAS_MLP_Handle *mlp = solver;
2242  struct ATS_Peer *p = NULL;
2243 
2244  GNUNET_assert(NULL != solver);
2245  GNUNET_assert(NULL != peer);
2246  if (NULL != (p = GNUNET_CONTAINER_multipeermap_get(mlp->requested_peers, peer)))
2247  {
2250  GNUNET_free(p);
2251 
2253  if (GNUNET_YES == mlp->opt_mlp_auto_solve)
2254  {
2255  GAS_mlp_solve_problem(solver);
2256  }
2257  }
2258 }
2259 
2260 
2269 static void
2271  const struct GNUNET_PeerIdentity *peer,
2272  enum GNUNET_ATS_PreferenceKind kind,
2273  double pref_rel)
2274 {
2275  struct GAS_MLP_Handle *mlp = solver;
2276  struct ATS_Peer *p;
2277 
2279  "Changing preference for address for peer `%s' to %.2f\n",
2280  GNUNET_i2s(peer),
2281  pref_rel);
2282 
2284  "# LP address preference changes", 1, GNUNET_NO);
2285  /* Update the constraints with changed preferences */
2286 
2287 
2288 
2289  /* Update relativity constraint c9 */
2290  if (NULL == (p = GNUNET_CONTAINER_multipeermap_get(mlp->requested_peers, peer)))
2291  {
2293  "Updating preference for unknown peer `%s'\n",
2294  GNUNET_i2s(peer));
2295  return;
2296  }
2297 
2298  if (GNUNET_NO == mlp->opt_dbg_feasibility_only)
2299  {
2300  p->f = get_peer_pref_value(mlp, peer);
2302  p->r_c9,
2303  mlp->p.c_r,
2304  -p->f,
2305  __LINE__);
2306 
2307  /* Problem size changed: new address for peer with pending request */
2309  if (GNUNET_YES == mlp->opt_mlp_auto_solve)
2310  GAS_mlp_solve_problem(solver);
2311  }
2312 }
2313 
2314 
2325 static void
2327  struct GNUNET_SERVICE_Client *application,
2328  const struct GNUNET_PeerIdentity *peer,
2329  const struct GNUNET_TIME_Relative scope,
2330  enum GNUNET_ATS_PreferenceKind kind,
2331  double score)
2332 {
2333  struct GAS_PROPORTIONAL_Handle *s = solver;
2334 
2335  GNUNET_assert(NULL != solver);
2336  GNUNET_assert(NULL != peer);
2337  GNUNET_assert(NULL != s);
2338 }
2339 
2340 
2341 static int
2342 mlp_free_peers(void *cls,
2343  const struct GNUNET_PeerIdentity *key, void *value)
2344 {
2345  struct GNUNET_CONTAINER_MultiPeerMap *map = cls;
2346  struct ATS_Peer *p = value;
2347 
2349  GNUNET_CONTAINER_multipeermap_remove(map, key, value));
2350  GNUNET_free(p);
2351 
2352  return GNUNET_OK;
2353 }
2354 
2355 
2362 void *
2364 {
2365  struct GNUNET_ATS_SolverFunctions *sf = cls;
2366  struct GAS_MLP_Handle *mlp = sf->cls;
2367 
2369  "Shutting down mlp solver\n");
2370  mlp_delete_problem(mlp);
2372  &mlp_free_peers,
2373  mlp->requested_peers);
2375  mlp->requested_peers = NULL;
2376 
2377  /* Clean up GLPK environment */
2378  glp_free_env();
2379  GNUNET_free(mlp);
2380 
2382  "Shutdown down of mlp solver complete\n");
2383  return NULL;
2384 }
2385 
2386 
2387 void *
2389 {
2390  static struct GNUNET_ATS_SolverFunctions sf;
2392  struct GAS_MLP_Handle * mlp = GNUNET_new(struct GAS_MLP_Handle);
2393  float f_tmp;
2394  unsigned long long tmp;
2395  unsigned int b_min;
2396  unsigned int n_min;
2397  int c;
2398  char *outputformat;
2399 
2400  struct GNUNET_TIME_Relative max_duration;
2401  long long unsigned int max_iterations;
2402 
2403  /* Init GLPK environment */
2404  int res = glp_init_env();
2405 
2406  switch (res)
2407  {
2408  case 0:
2409  LOG(GNUNET_ERROR_TYPE_DEBUG, "GLPK: `%s'\n",
2410  "initialization successful");
2411  break;
2412 
2413  case 1:
2414  LOG(GNUNET_ERROR_TYPE_DEBUG, "GLPK: `%s'\n",
2415  "environment is already initialized");
2416  break;
2417 
2418  case 2:
2419  LOG(GNUNET_ERROR_TYPE_ERROR, "Could not init GLPK: `%s'\n",
2420  "initialization failed (insufficient memory)");
2421  GNUNET_free(mlp);
2422  return NULL;
2423  break;
2424 
2425  case 3:
2426  LOG(GNUNET_ERROR_TYPE_ERROR, "Could not init GLPK: `%s'\n",
2427  "initialization failed (unsupported programming model)");
2428  GNUNET_free(mlp);
2429  return NULL;
2430  break;
2431 
2432  default:
2433  break;
2434  }
2435 
2437  "ats", "MLP_DUMP_PROBLEM_ALL");
2438  if (GNUNET_SYSERR == mlp->opt_dump_problem_all)
2440 
2442  "ats", "MLP_DUMP_SOLUTION_ALL");
2445 
2447  "ats", "MLP_DUMP_PROBLEM_ON_FAIL");
2450 
2452  "ats", "MLP_DUMP_SOLUTION_ON_FAIL");
2455 
2457  "ats", "MLP_DBG_GLPK_VERBOSE");
2458  if (GNUNET_SYSERR == mlp->opt_dbg_glpk_verbose)
2460 
2462  "ats", "MLP_DBG_FEASIBILITY_ONLY");
2467  "MLP solver is configured to check feasibility only!\n");
2468 
2470  "ats", "MLP_DBG_AUTOSCALE_PROBLEM");
2475  "MLP solver is configured automatically scale the problem!\n");
2476 
2478  "ats", "MLP_DBG_INTOPT_PRESOLVE");
2483  "MLP solver is configured use the mlp presolver\n");
2484 
2486  "ats", "MLP_DBG_OPTIMIZE_DIVERSITY");
2491  "MLP solver is not optimizing for diversity\n");
2492 
2494  "ats", "MLP_DBG_OPTIMIZE_RELATIVITY");
2499  "MLP solver is not optimizing for relativity\n");
2500 
2502  "ats", "MLP_DBG_OPTIMIZE_QUALITY");
2505  if (GNUNET_NO == mlp->opt_dbg_optimize_quality)
2507  "MLP solver is not optimizing for quality\n");
2508 
2510  "ats", "MLP_DBG_OPTIMIZE_UTILITY");
2513  if (GNUNET_NO == mlp->opt_dbg_optimize_utility)
2515  "MLP solver is not optimizing for utility\n");
2516 
2517  if ((GNUNET_NO == mlp->opt_dbg_optimize_utility) &&
2518  (GNUNET_NO == mlp->opt_dbg_optimize_quality) &&
2520  (GNUNET_NO == mlp->opt_dbg_optimize_utility) &&
2522  {
2524  _("MLP solver is not optimizing for anything, changing to feasibility check\n"));
2526  }
2527 
2529  "ats", "MLP_LOG_FORMAT", &outputformat))
2530  mlp->opt_log_format = MLP_CPLEX;
2531  else
2532  {
2533  GNUNET_STRINGS_utf8_toupper(outputformat, outputformat);
2534  if (0 == strcmp(outputformat, "MPS"))
2535  {
2536  mlp->opt_log_format = MLP_MPS;
2537  }
2538  else if (0 == strcmp(outputformat, "CPLEX"))
2539  {
2540  mlp->opt_log_format = MLP_CPLEX;
2541  }
2542  else if (0 == strcmp(outputformat, "GLPK"))
2543  {
2544  mlp->opt_log_format = MLP_GLPK;
2545  }
2546  else
2547  {
2549  "Invalid log format `%s' in configuration, using CPLEX!\n",
2550  outputformat);
2551  mlp->opt_log_format = MLP_CPLEX;
2552  }
2553  GNUNET_free(outputformat);
2554  }
2555 
2556  mlp->pv.BIG_M = (double)BIG_M_VALUE;
2557 
2558  mlp->pv.mip_gap = (double)0.0;
2560  "MLP_MAX_MIP_GAP", &f_tmp))
2561  {
2562  if ((f_tmp < 0.0) || (f_tmp > 1.0))
2563  {
2564  LOG(GNUNET_ERROR_TYPE_ERROR, _("Invalid %s configuration %f \n"),
2565  "MIP gap", f_tmp);
2566  }
2567  else
2568  {
2569  mlp->pv.mip_gap = f_tmp;
2570  LOG(GNUNET_ERROR_TYPE_INFO, "Using %s of %.3f\n",
2571  "MIP gap", f_tmp);
2572  }
2573  }
2574 
2575  mlp->pv.lp_mip_gap = (double)0.0;
2577  "MLP_MAX_LP_MIP_GAP", &f_tmp))
2578  {
2579  if ((f_tmp < 0.0) || (f_tmp > 1.0))
2580  {
2581  LOG(GNUNET_ERROR_TYPE_ERROR, _("Invalid %s configuration %f \n"),
2582  "LP/MIP", f_tmp);
2583  }
2584  else
2585  {
2586  mlp->pv.lp_mip_gap = f_tmp;
2587  LOG(GNUNET_ERROR_TYPE_INFO, "Using %s gap of %.3f\n",
2588  "LP/MIP", f_tmp);
2589  }
2590  }
2591 
2592  /* Get timeout for iterations */
2594  "MLP_MAX_DURATION", &max_duration))
2595  {
2596  max_duration = MLP_MAX_EXEC_DURATION;
2597  }
2598 
2599  /* Get maximum number of iterations */
2601  "MLP_MAX_ITERATIONS", &max_iterations))
2602  {
2603  max_iterations = MLP_MAX_ITERATIONS;
2604  }
2605 
2606  /* Get diversity coefficient from configuration */
2607  mlp->pv.co_D = MLP_DEFAULT_D;
2609  "MLP_COEFFICIENT_D", &f_tmp))
2610  {
2611  if ((f_tmp < 0.0))
2612  {
2613  LOG(GNUNET_ERROR_TYPE_ERROR, _("Invalid %s configuration %f \n"),
2614  "MLP_COEFFICIENT_D", f_tmp);
2615  }
2616  else
2617  {
2618  mlp->pv.co_D = f_tmp;
2619  LOG(GNUNET_ERROR_TYPE_INFO, "Using %s gap of %.3f\n",
2620  "MLP_COEFFICIENT_D", f_tmp);
2621  }
2622  }
2623 
2624  /* Get relativity coefficient from configuration */
2625  mlp->pv.co_R = MLP_DEFAULT_R;
2627  "MLP_COEFFICIENT_R", &f_tmp))
2628  {
2629  if ((f_tmp < 0.0))
2630  {
2631  LOG(GNUNET_ERROR_TYPE_ERROR, _("Invalid %s configuration %f \n"),
2632  "MLP_COEFFICIENT_R", f_tmp);
2633  }
2634  else
2635  {
2636  mlp->pv.co_R = f_tmp;
2637  LOG(GNUNET_ERROR_TYPE_INFO, "Using %s gap of %.3f\n",
2638  "MLP_COEFFICIENT_R", f_tmp);
2639  }
2640  }
2641 
2642 
2643  /* Get utilization coefficient from configuration */
2644  mlp->pv.co_U = MLP_DEFAULT_U;
2646  "MLP_COEFFICIENT_U", &f_tmp))
2647  {
2648  if ((f_tmp < 0.0))
2649  {
2650  LOG(GNUNET_ERROR_TYPE_ERROR, _("Invalid %s configuration %f \n"),
2651  "MLP_COEFFICIENT_U", f_tmp);
2652  }
2653  else
2654  {
2655  mlp->pv.co_U = f_tmp;
2656  LOG(GNUNET_ERROR_TYPE_INFO, "Using %s gap of %.3f\n",
2657  "MLP_COEFFICIENT_U", f_tmp);
2658  }
2659  }
2660 
2661  /* Get quality metric coefficients from configuration */
2662  for (c = 0; c < RQ_QUALITY_METRIC_COUNT; c++)
2663  {
2664  /* initialize quality coefficients with default value 1.0 */
2665  mlp->pv.co_Q[c] = MLP_DEFAULT_QUALITY;
2666  }
2667 
2668 
2669  if (GNUNET_OK ==
2671  "MLP_COEFFICIENT_QUALITY_DELAY",
2672  &tmp))
2673  mlp->pv.co_Q[RQ_QUALITY_METRIC_DELAY] = (double)tmp / 100;
2674  else
2676 
2677  if (GNUNET_OK ==
2679  "MLP_COEFFICIENT_QUALITY_DISTANCE",
2680  &tmp))
2681  mlp->pv.co_Q[RQ_QUALITY_METRIC_DISTANCE] = (double)tmp / 100;
2682  else
2684 
2685  /* Get minimum bandwidth per used address from configuration */
2687  "MLP_MIN_BANDWIDTH",
2688  &tmp))
2689  b_min = tmp;
2690  else
2691  {
2692  b_min = ntohl(GNUNET_CONSTANTS_DEFAULT_BW_IN_OUT.value__);
2693  }
2694 
2695  /* Get minimum number of connections from configuration */
2697  "MLP_MIN_CONNECTIONS",
2698  &tmp))
2699  n_min = tmp;
2700  else
2702 
2703  /* Init network quotas */
2704  for (c = 0; c < GNUNET_NT_COUNT; c++)
2705  {
2706  mlp->pv.quota_index[c] = c;
2707  mlp->pv.quota_out[c] = env->out_quota[c];
2708  mlp->pv.quota_in[c] = env->in_quota[c];
2709 
2711  "Quota for network `%s' (in/out) %llu/%llu\n",
2713  mlp->pv.quota_out[c],
2714  mlp->pv.quota_in[c]);
2715  /* Check if defined quota could make problem unsolvable */
2716  if ((n_min * b_min) > mlp->pv.quota_out[c])
2717  {
2719  _("Adjusting inconsistent outbound quota configuration for network `%s', is %llu must be at least %llu\n"),
2721  mlp->pv.quota_out[c],
2722  (n_min * b_min));
2723  mlp->pv.quota_out[c] = (n_min * b_min);
2724  }
2725  if ((n_min * b_min) > mlp->pv.quota_in[c])
2726  {
2728  _("Adjusting inconsistent inbound quota configuration for network `%s', is %llu must be at least %llu\n"),
2730  mlp->pv.quota_in[c],
2731  (n_min * b_min));
2732  mlp->pv.quota_in[c] = (n_min * b_min);
2733  }
2734  /* Check if bandwidth is too big to make problem solvable */
2735  if (mlp->pv.BIG_M < mlp->pv.quota_out[c])
2736  {
2738  _("Adjusting outbound quota configuration for network `%s'from %llu to %.0f\n"),
2740  mlp->pv.quota_out[c],
2741  mlp->pv.BIG_M);
2742  mlp->pv.quota_out[c] = mlp->pv.BIG_M;
2743  }
2744  if (mlp->pv.BIG_M < mlp->pv.quota_in[c])
2745  {
2747  _("Adjusting inbound quota configuration for network `%s' from %llu to %.0f\n"),
2749  mlp->pv.quota_in[c],
2750  mlp->pv.BIG_M);
2751  mlp->pv.quota_in[c] = mlp->pv.BIG_M;
2752  }
2753  }
2754  mlp->env = env;
2755  sf.cls = mlp;
2756  sf.s_add = &GAS_mlp_address_add;
2765 
2766  /* Setting MLP Input variables */
2767  mlp->pv.b_min = b_min;
2768  mlp->pv.n_min = n_min;
2774  mlp->stat_bulk_requests = 0;
2775  mlp->stat_bulk_lock = 0;
2776 
2777  /* Setup GLPK */
2778  /* Redirect GLPK output to GNUnet logging */
2779  glp_term_hook(&mlp_term_hook, (void *)mlp);
2780 
2781  /* Init LP solving parameters */
2782  glp_init_smcp(&mlp->control_param_lp);
2783  mlp->control_param_lp.msg_lev = GLP_MSG_OFF;
2784  if (GNUNET_YES == mlp->opt_dbg_glpk_verbose)
2785  mlp->control_param_lp.msg_lev = GLP_MSG_ALL;
2786 
2787  mlp->control_param_lp.it_lim = max_iterations;
2788  mlp->control_param_lp.tm_lim = max_duration.rel_value_us / 1000LL;
2789 
2790  /* Init MLP solving parameters */
2791  glp_init_iocp(&mlp->control_param_mlp);
2792  /* Setting callback function */
2793  mlp->control_param_mlp.cb_func = &mlp_branch_and_cut_cb;
2794  mlp->control_param_mlp.cb_info = mlp;
2795  mlp->control_param_mlp.msg_lev = GLP_MSG_OFF;
2796  mlp->control_param_mlp.mip_gap = mlp->pv.mip_gap;
2797  if (GNUNET_YES == mlp->opt_dbg_glpk_verbose)
2798  mlp->control_param_mlp.msg_lev = GLP_MSG_ALL;
2799  mlp->control_param_mlp.tm_lim = max_duration.rel_value_us / 1000LL;
2800 
2801  LOG(GNUNET_ERROR_TYPE_DEBUG, "solver ready\n");
2802 
2803  return &sf;
2804 }
2805 
2806 /* 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:43
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.
double lp_mlp_gap
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:246
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:577
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:139
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.