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 
58 {
62 };
63 
64 
66 {
70 };
71 
72 
73 static const char *
75 {
76  switch (qm){
78  return "delay";
80  return "distance";
81  default:
82  GNUNET_break (0);
83  return NULL;
84  }
85 }
86 
87 
89 {
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 
109 struct ATS_Peer
110 {
112 
113  /* Was this peer already added to the current problem? */
115 
116  /* constraint 2: 1 address per peer*/
117  unsigned int r_c2;
118 
119  /* constraint 9: relativity */
120  unsigned int r_c9;
121 
122  /* Legacy preference value */
123  double f;
124 };
125 
127 {
131  glp_prob *prob;
132 
133  /* Number of addresses in problem */
134  unsigned int num_addresses;
135  /* Number of peers in problem */
136  unsigned int num_peers;
137  /* Number of elements in problem matrix */
138  unsigned int num_elements;
139 
140  /* Row index constraint 2: */
141  unsigned int r_c2;
142  /* Row index constraint 4: minimum connections */
143  unsigned int r_c4;
144  /* Row index constraint 6: maximize diversity */
145  unsigned int r_c6;
146  /* Row index constraint 8: utilization*/
147  unsigned int r_c8;
148  /* Row index constraint 9: relativity*/
149  unsigned int r_c9;
150  /* Row indices quality metrics */
152  /* Row indices ATS network quotas */
153  int r_quota[GNUNET_NT_COUNT];
154 
155  /* Column index Diversity (D) column */
156  int c_d;
157  /* Column index Utilization (U) column */
158  int c_u;
159  /* Column index Proportionality (R) column */
160  int c_r;
161  /* Column index quality metrics */
163 
164  /* Problem matrix */
165  /* Current index */
166  unsigned int ci;
167  /* Row index array */
168  int *ia;
169  /* Column index array */
170  int *ja;
171  /* Column index value */
172  double *ar;
173 
174 };
175 
177 {
178  /* Big M value for bandwidth capping */
179  double BIG_M;
180 
181  /* MIP Gap */
182  double mip_gap;
183 
184  /* LP MIP Gap */
185  double lp_mip_gap;
186 
187  /* Number of quality metrics @deprecated, use RQ_QUALITY_METRIC_COUNT */
188  int m_q;
189 
190  /* Number of quality metrics */
191  int m_rc;
192 
193  /* Quality metric coefficients*/
195 
196  /* Ressource costs coefficients*/
197  double co_RC[RQ_QUALITY_METRIC_COUNT];
198 
199  /* Diversity coefficient */
200  double co_D;
201 
202  /* Utility coefficient */
203  double co_U;
204 
205  /* Relativity coefficient */
206  double co_R;
207 
208  /* Minimum bandwidth assigned to an address */
209  unsigned int b_min;
210 
211  /* Minimum number of addresses with bandwidth assigned */
212  unsigned int n_min;
213 
214  /* Quotas */
215  /* Array mapping array index to ATS network */
216  int quota_index[GNUNET_NT_COUNT];
217  /* Outbound quotas */
218  unsigned long long quota_out[GNUNET_NT_COUNT];
219  /* Inbound quotas */
220 
221  unsigned long long quota_in[GNUNET_NT_COUNT];
222 
223  /* ATS ressource costs
224  * array with GNUNET_ATS_QualityPropertiesCount elements
225  * contains mapping to GNUNET_ATS_Property
226  * */
228 
229 };
230 
235 {
237 
242 
246  struct MLP_Problem p;
247 
251  struct MLP_Variables pv;
252 
256  struct MLP_Solution ps;
257 
262 
267 
272 
277 
282 
287 
292 
299 
304 
309 
314 
319 
324 
329 
334 
339 
344 
349 
354 
359 
360 
364  enum MLP_Output_Format opt_log_format;
365 };
366 
371 {
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  peer->processed = GNUNET_NO;
555  return GNUNET_OK;
556  }
557 
563 static void
565 {
566  int c;
567  if (mlp == NULL)
568  return;
569  if (mlp->p.prob != NULL)
570  {
571  glp_delete_prob(mlp->p.prob);
572  mlp->p.prob = NULL;
573  }
574 
575  /* delete row index */
576  if (mlp->p.ia != NULL)
577  {
578  GNUNET_free (mlp->p.ia);
579  mlp->p.ia = NULL;
580  }
581 
582  /* delete column index */
583  if (mlp->p.ja != NULL)
584  {
585  GNUNET_free (mlp->p.ja);
586  mlp->p.ja = NULL;
587  }
588 
589  /* delete coefficients */
590  if (mlp->p.ar != NULL)
591  {
592  GNUNET_free (mlp->p.ar);
593  mlp->p.ar = NULL;
594  }
595  mlp->p.ci = 0;
596  mlp->p.prob = NULL;
597 
598  mlp->p.c_d = MLP_UNDEFINED;
599  mlp->p.c_r = MLP_UNDEFINED;
600  mlp->p.r_c2 = MLP_UNDEFINED;
601  mlp->p.r_c4 = MLP_UNDEFINED;
602  mlp->p.r_c6 = MLP_UNDEFINED;
603  mlp->p.r_c9 = MLP_UNDEFINED;
604  for (c = 0; c < RQ_QUALITY_METRIC_COUNT ; c ++)
605  mlp->p.r_q[c] = MLP_UNDEFINED;
606  for (c = 0; c < GNUNET_NT_COUNT; c ++)
607  mlp->p.r_quota[c] = MLP_UNDEFINED;
608  mlp->p.ci = MLP_UNDEFINED;
609 
610 
612  &reset_peers, NULL);
613 }
614 
615 
621 static const char *
622 mlp_status_to_string (int retcode)
623 {
624  switch (retcode) {
625  case GLP_UNDEF:
626  return "solution is undefined";
627  case GLP_FEAS:
628  return "solution is feasible";
629  case GLP_INFEAS:
630  return "solution is infeasible";
631  case GLP_NOFEAS:
632  return "no feasible solution exists";
633  case GLP_OPT:
634  return "solution is optimal";
635  case GLP_UNBND:
636  return "solution is unbounded";
637  default:
638  GNUNET_break (0);
639  return "unknown error";
640  }
641 }
642 
643 
649 static const char *
650 mlp_solve_to_string (int retcode)
651 {
652  switch (retcode) {
653  case 0:
654  return "ok";
655  case GLP_EBADB:
656  return "invalid basis";
657  case GLP_ESING:
658  return "singular matrix";
659  case GLP_ECOND:
660  return "ill-conditioned matrix";
661  case GLP_EBOUND:
662  return "invalid bounds";
663  case GLP_EFAIL:
664  return "solver failed";
665  case GLP_EOBJLL:
666  return "objective lower limit reached";
667  case GLP_EOBJUL:
668  return "objective upper limit reached";
669  case GLP_EITLIM:
670  return "iteration limit exceeded";
671  case GLP_ETMLIM:
672  return "time limit exceeded";
673  case GLP_ENOPFS:
674  return "no primal feasible solution";
675  case GLP_ENODFS:
676  return "no dual feasible solution";
677  case GLP_EROOT:
678  return "root LP optimum not provided";
679  case GLP_ESTOP:
680  return "search terminated by application";
681  case GLP_EMIPGAP:
682  return "relative mip gap tolerance reached";
683  case GLP_ENOFEAS:
684  return "no dual feasible solution";
685  case GLP_ENOCVG:
686  return "no convergence";
687  case GLP_EINSTAB:
688  return "numerical instability";
689  case GLP_EDATA:
690  return "invalid data";
691  case GLP_ERANGE:
692  return "result out of range";
693  default:
694  GNUNET_break (0);
695  return "unknown error";
696  }
697 }
698 
699 
701 {
703  int result;
704 };
705 
706 static int
708  const struct GNUNET_PeerIdentity *key,
709  void *value)
710 {
711  struct CountContext *cctx = cls;
712 
713  /* Check if we have to add this peer due to a pending request */
715  cctx->result++;
716  return GNUNET_OK;
717 }
718 
719 
720 static int
723 {
724  struct CountContext cctx;
725 
726  cctx.map = requested_peers;
727  cctx.result = 0;
730  return cctx.result;
731 }
732 
733 
734 static int
736  const struct GNUNET_PeerIdentity *key,
737  void *value)
738 {
739  struct CountContext *cctx = cls;
740 
741  /* Check if we have to addresses for the requested peer */
743  cctx->result++;
744  return GNUNET_OK;
745 }
746 
747 
748 static int
751 {
752  struct CountContext cctx;
753 
754  cctx.map = addresses;
755  cctx.result = 0;
756  GNUNET_CONTAINER_multipeermap_iterate (requested_peers,
758  return cctx.result;
759 }
760 
761 
775 static int
777  int row, int col, double val,
778  int line)
779 {
780  int c_cols;
781  int c_elems;
782  int c1;
783  int res;
784  int found;
785  double *val_array;
786  int *ind_array;
787 
788  GNUNET_assert (NULL != p->prob);
789 
790  /* Get number of columns and prepare data structure */
791  c_cols = glp_get_num_cols(p->prob);
792  if (0 >= c_cols)
793  return GNUNET_SYSERR;
794 
795  val_array = GNUNET_malloc ((c_cols +1)* sizeof (double));
796  GNUNET_assert (NULL != val_array);
797  ind_array = GNUNET_malloc ((c_cols+1) * sizeof (int));
798  GNUNET_assert (NULL != ind_array);
799  /* Extract the row */
800 
801  /* Update the value */
802  c_elems = glp_get_mat_row (p->prob, row, ind_array, val_array);
803  found = GNUNET_NO;
804  for (c1 = 1; c1 < (c_elems+1); c1++)
805  {
806  if (ind_array[c1] == col)
807  {
808  found = GNUNET_YES;
809  break;
810  }
811  }
812  if (GNUNET_NO == found)
813  {
814  ind_array[c_elems+1] = col;
815  val_array[c_elems+1] = val;
816  LOG (GNUNET_ERROR_TYPE_DEBUG, "[P] Setting value in [%s : %s] to `%.2f'\n",
817  glp_get_row_name (p->prob, row), glp_get_col_name (p->prob, col),
818  val);
819  glp_set_mat_row (p->prob, row, c_elems+1, ind_array, val_array);
820  GNUNET_free (ind_array);
821  GNUNET_free (val_array);
822  return GNUNET_YES;
823  }
824  else
825  {
826  /* Update value */
827  LOG (GNUNET_ERROR_TYPE_DEBUG, "[P] Updating value in [%s : %s] from `%.2f' to `%.2f'\n",
828  glp_get_row_name (p->prob, row), glp_get_col_name (p->prob, col),
829  val_array[c1], val);
830  if (val != val_array[c1])
831  res = GNUNET_YES;
832  else
833  res = GNUNET_NO;
834  val_array[c1] = val;
835  /* Update the row in the matrix */
836  glp_set_mat_row (p->prob, row, c_elems, ind_array, val_array);
837  }
838 
839  GNUNET_free (ind_array);
840  GNUNET_free (val_array);
841  return res;
842 }
843 
856 static void
858  int row, int col, double val,
859  int line)
860 {
861  if ((p->ci) >= p->num_elements)
862  {
863  LOG (GNUNET_ERROR_TYPE_DEBUG, "[P]: line %u: Request for index %u bigger than array size of %u\n",
864  line, p->ci + 1, p->num_elements);
865  GNUNET_break (0);
866  return;
867  }
868  if ((0 == row) || (0 == col))
869  {
870  GNUNET_break (0);
871  LOG (GNUNET_ERROR_TYPE_ERROR, "[P]: Invalid call from line %u: row = %u, col = %u\n",
872  line, row, col);
873  }
874  p->ia[p->ci] = row ;
875  p->ja[p->ci] = col;
876  p->ar[p->ci] = val;
877 #if DEBUG_MLP_PROBLEM_CREATION
878  LOG (GNUNET_ERROR_TYPE_DEBUG, "[P]: line %u: Set value [%u,%u] in index %u == %.2f\n",
879  line, p->ia[p->ci], p->ja[p->ci], p->ci, p->ar[p->ci]);
880 #endif
881  p->ci++;
882 }
883 
884 static int
886  unsigned int type, unsigned int bound, double lb, double ub,
887  double coef)
888 {
889  int col = glp_add_cols (p->prob, 1);
890  glp_set_col_name (p->prob, col, name);
891  glp_set_col_bnds (p->prob, col, bound, lb, ub);
892  glp_set_col_kind (p->prob, col, type);
893  glp_set_obj_coef (p->prob, col, coef);
894 #if DEBUG_MLP_PROBLEM_CREATION
895  LOG (GNUNET_ERROR_TYPE_DEBUG, "[P]: Added column [%u] `%s': %.2f\n",
896  col, name, coef);
897 #endif
898  return col;
899 }
900 
901 static int
903  unsigned int bound, double lb, double ub)
904 {
905  char * op;
906  int row = glp_add_rows (p->prob, 1);
907  /* set row name */
908  glp_set_row_name (p->prob, row, name);
909  /* set row bounds: <= 0 */
910  glp_set_row_bnds (p->prob, row, bound, lb, ub);
911  switch (bound)
912  {
913  case GLP_UP:
914  GNUNET_asprintf(&op, "-inf <= x <= %.2f", ub);
915  break;
916  case GLP_DB:
917  GNUNET_asprintf(&op, "%.2f <= x <= %.2f", lb, ub);
918  break;
919  case GLP_FX:
920  GNUNET_asprintf(&op, "%.2f == x == %.2f", lb, ub);
921  break;
922  case GLP_LO:
923  GNUNET_asprintf(&op, "%.2f <= x <= inf", lb);
924  break;
925  default:
926  GNUNET_asprintf(&op, "ERROR");
927  break;
928  }
929 #if DEBUG_MLP_PROBLEM_CREATION
930  LOG (GNUNET_ERROR_TYPE_DEBUG, "[P]: Added row [%u] `%s': %s\n",
931  row, name, op);
932 #endif
933  GNUNET_free (op);
934  return row;
935 }
936 
944 static int
946  const struct GNUNET_PeerIdentity *key,
947  void *value)
948 {
949  struct GAS_MLP_Handle *mlp = cls;
950  struct MLP_Problem *p = &mlp->p;
951  struct ATS_Address *address = value;
952  struct ATS_Peer *peer;
953  struct MLP_information *mlpi;
954  char *name;
955  double cur_bigm;
956  uint32_t addr_net;
957  uint32_t addr_net_index;
958  unsigned long long max_quota;
959  int c;
960 
961  /* Check if we have to add this peer due to a pending request */
963  return GNUNET_OK;
964 
965  mlpi = address->solver_information;
966  if (NULL == mlpi)
967  {
968  fprintf (stderr, "%s %p\n",GNUNET_i2s (&address->peer), address);
969  GNUNET_break (0);
970  return GNUNET_OK;
971  }
972 
973  addr_net = address->properties.scope;
974  for (addr_net_index = 0; addr_net_index < GNUNET_NT_COUNT; addr_net_index++)
975  {
976  if (mlp->pv.quota_index[addr_net_index] == addr_net)
977  break;
978  }
979 
980  if (addr_net_index >= GNUNET_NT_COUNT)
981  {
982  GNUNET_break (0);
983  return GNUNET_OK;
984  }
985 
986  max_quota = 0;
987  for (c = 0; c < GNUNET_NT_COUNT; c++)
988  {
989  if (mlp->pv.quota_out[c] > max_quota)
990  max_quota = mlp->pv.quota_out[c];
991  if (mlp->pv.quota_in[c] > max_quota)
992  max_quota = mlp->pv.quota_in[c];
993  }
994  if (max_quota > mlp->pv.BIG_M)
995  cur_bigm = (double) mlp->pv.BIG_M;
996  else
997  cur_bigm = max_quota;
998 
999 
1000  /* Get peer */
1002  GNUNET_assert (NULL != peer);
1003  if (peer->processed == GNUNET_NO)
1004  {
1005  /* Add peer dependent constraints */
1006  /* Add c2) One address active per peer */
1007  GNUNET_asprintf(&name, "c2_%s", GNUNET_i2s(&address->peer));
1008  peer->r_c2 = mlp_create_problem_create_constraint (p, name, GLP_FX, 1.0, 1.0);
1009  GNUNET_free (name);
1010  if (GNUNET_NO == mlp->opt_dbg_feasibility_only)
1011  {
1013  {
1014  /* Add c9) Relativity */
1015  GNUNET_asprintf(&name, "c9_%s", GNUNET_i2s(&address->peer));
1016  peer->r_c9 = mlp_create_problem_create_constraint (p, name, GLP_LO, 0.0, 0.0);
1017  GNUNET_free (name);
1018  /* c9) set coefficient */
1019  mlp_create_problem_set_value (p, peer->r_c9, p->c_r, -peer->f , __LINE__);
1020  }
1021  }
1022  peer->processed = GNUNET_YES;
1023  }
1024 
1025  /* Reset addresses' solver information */
1026  mlpi->c_b = 0;
1027  mlpi->c_n = 0;
1028  mlpi->n = 0;
1029  mlpi->r_c1 = 0;
1030  mlpi->r_c3 = 0;
1031 
1032  /* Add bandwidth column */
1033  GNUNET_asprintf (&name, "b_%s_%s_%p", GNUNET_i2s (&address->peer), address->plugin, address);
1034  if (GNUNET_NO == mlp->opt_dbg_feasibility_only)
1035  {
1036  mlpi->c_b = mlp_create_problem_create_column (p, name, GLP_CV, GLP_LO, 0.0, 0.0, 0.0);
1037  }
1038  else
1039  {
1040  /* Maximize for bandwidth assignment in feasibility testing */
1041  mlpi->c_b = mlp_create_problem_create_column (p, name, GLP_CV, GLP_LO, 0.0, 0.0, 1.0);
1042  }
1043  GNUNET_free (name);
1044 
1045  /* Add address active column */
1046  GNUNET_asprintf (&name, "n_%s_%s_%p", GNUNET_i2s (&address->peer), address->plugin, address);
1047  mlpi->c_n = mlp_create_problem_create_column (p, name, GLP_IV, GLP_DB, 0.0, 1.0, 0.0);
1048  GNUNET_free (name);
1049 
1050  /* Add address dependent constraints */
1051  /* Add c1) bandwidth capping: b_t + (-M) * n_t <= 0 */
1052  GNUNET_asprintf(&name, "c1_%s_%s_%p", GNUNET_i2s(&address->peer), address->plugin, address);
1053  mlpi->r_c1 = mlp_create_problem_create_constraint (p, name, GLP_UP, 0.0, 0.0);
1054  GNUNET_free (name);
1055  /* c1) set b = 1 coefficient */
1056  mlp_create_problem_set_value (p, mlpi->r_c1, mlpi->c_b, 1, __LINE__);
1057  /* c1) set n = - min (M, quota) coefficient */
1058  cur_bigm = (double) mlp->pv.quota_out[addr_net_index];
1059  if (cur_bigm > mlp->pv.BIG_M)
1060  cur_bigm = (double) mlp->pv.BIG_M;
1061  mlp_create_problem_set_value (p, mlpi->r_c1, mlpi->c_n, -cur_bigm, __LINE__);
1062 
1063  /* Add constraint c 3) minimum bandwidth
1064  * b_t + (-n_t * b_min) >= 0
1065  * */
1066  GNUNET_asprintf(&name, "c3_%s_%s_%p", GNUNET_i2s(&address->peer), address->plugin, address);
1067  mlpi->r_c3 = mlp_create_problem_create_constraint (p, name, GLP_LO, 0.0, 0.0);
1068  GNUNET_free (name);
1069 
1070  /* c3) set b = 1 coefficient */
1071  mlp_create_problem_set_value (p, mlpi->r_c3, mlpi->c_b, 1, __LINE__);
1072  /* c3) set n = -b_min coefficient */
1073  mlp_create_problem_set_value (p, mlpi->r_c3, mlpi->c_n, - ((double )mlp->pv.b_min), __LINE__);
1074 
1075 
1076  /* Set coefficient entries in invariant rows */
1077 
1078  /* Feasbility */
1079 
1080  /* c 4) minimum connections */
1081  mlp_create_problem_set_value (p, p->r_c4, mlpi->c_n, 1, __LINE__);
1082  /* c 2) 1 address peer peer */
1083  mlp_create_problem_set_value (p, peer->r_c2, mlpi->c_n, 1, __LINE__);
1084  /* c 10) obey network specific quotas
1085  * (1)*b_1 + ... + (1)*b_m <= quota_n
1086  */
1087  mlp_create_problem_set_value (p, p->r_quota[addr_net_index], mlpi->c_b, 1, __LINE__);
1088 
1089  /* Optimality */
1090  if (GNUNET_NO == mlp->opt_dbg_feasibility_only)
1091  {
1092  /* c 6) maximize diversity */
1093  mlp_create_problem_set_value (p, p->r_c6, mlpi->c_n, 1, __LINE__);
1094  /* c 9) relativity */
1096  mlp_create_problem_set_value (p, peer->r_c9, mlpi->c_b, 1, __LINE__);
1097  /* c 8) utility */
1099  mlp_create_problem_set_value (p, p->r_c8, mlpi->c_b, 1, __LINE__);
1100  /* c 7) Optimize quality */
1101  /* For all quality metrics, set quality of this address */
1103  {
1106  mlpi->c_b,
1107  address->norm_delay.norm,
1108  __LINE__);
1111  mlpi->c_b,
1112  address->norm_distance.norm,
1113  __LINE__);
1114  }
1115  }
1116 
1117  return GNUNET_OK;
1118 }
1119 
1120 
1124 static void
1126 {
1127  int c;
1128 
1129  /* Feasibility */
1130 
1131  /* Row for c4) minimum connection */
1132  /* Number of minimum connections is min(|Peers|, n_min) */
1133  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);
1134 
1135  /* Rows for c 10) Enforce network quotas */
1136  for (c = 0; c < GNUNET_NT_COUNT; c++)
1137  {
1138  char * text;
1139  GNUNET_asprintf(&text, "c10_quota_ats_%s",
1141  p->r_quota[c] = mlp_create_problem_create_constraint (p, text, GLP_DB, 0.0, mlp->pv.quota_out[c]);
1142  GNUNET_free (text);
1143  }
1144 
1145  /* Optimality */
1146  if (GNUNET_NO == mlp->opt_dbg_feasibility_only)
1147  {
1148  char *name;
1149  /* Add row for c6) Maximize for diversity */
1151  {
1152  p->r_c6 = mlp_create_problem_create_constraint (p, "c6", GLP_FX, 0.0, 0.0);
1153  /* Set c6 ) Setting -D */
1154  mlp_create_problem_set_value (p, p->r_c6, p->c_d, -1, __LINE__);
1155  }
1156 
1157  /* Adding rows for c 8) Maximize utility */
1159  {
1160  p->r_c8 = mlp_create_problem_create_constraint (p, "c8", GLP_FX, 0.0, 0.0);
1161  /* -u */
1162  mlp_create_problem_set_value (p, p->r_c8, p->c_u, -1, __LINE__);
1163  }
1164 
1165  /* For all quality metrics:
1166  * c 7) Maximize quality, austerity */
1168  {
1169  for (c = 0; c < mlp->pv.m_q; c++)
1170  {
1171  GNUNET_asprintf (&name,
1172  "c7_q%i_%s", c,
1173  print_quality_type (c));
1174  p->r_q[c] = mlp_create_problem_create_constraint (p, name, GLP_FX, 0.0, 0.0);
1175  GNUNET_free (name);
1177  p->r_q[c],
1178  p->c_q[c], -1, __LINE__);
1179  }
1180  }
1181  }
1182 }
1183 
1184 
1188 static void
1190 {
1191  if (GNUNET_NO == mlp->opt_dbg_feasibility_only)
1192  {
1193  char *name;
1194  int c;
1195 
1196  /* Diversity d column */
1198  p->c_d = mlp_create_problem_create_column (p, "d", GLP_CV, GLP_LO, 0.0, 0.0, mlp->pv.co_D);
1199 
1200  /* Utilization u column */
1202  p->c_u = mlp_create_problem_create_column (p, "u", GLP_CV, GLP_LO, 0.0, 0.0, mlp->pv.co_U);
1203 
1204  /* Relativity r column */
1206  p->c_r = mlp_create_problem_create_column (p, "r", GLP_CV, GLP_LO, 0.0, 0.0, mlp->pv.co_R);
1207 
1208  /* Quality metric columns */
1210  {
1211  for (c = 0; c < mlp->pv.m_q; c++)
1212  {
1213  GNUNET_asprintf (&name, "q_%u", c);
1214  p->c_q[c] = mlp_create_problem_create_column (p, name, GLP_CV, GLP_LO, 0.0, 0.0, mlp->pv.co_Q[c]);
1215  GNUNET_free (name);
1216  }
1217  }
1218  }
1219 }
1220 
1221 
1228 static int
1230 {
1231  struct MLP_Problem *p = &mlp->p;
1232  int res = GNUNET_OK;
1233 
1234  GNUNET_assert (p->prob == NULL);
1235  GNUNET_assert (p->ia == NULL);
1236  GNUNET_assert (p->ja == NULL);
1237  GNUNET_assert (p->ar == NULL);
1238  /* Reset MLP problem struct */
1239 
1240  /* create the glpk problem */
1241  p->prob = glp_create_prob ();
1242  GNUNET_assert (NULL != p->prob);
1245  mlp->env->addresses);
1246 
1247  /* Create problem matrix: 10 * #addresses + #q * #addresses + #q, + #peer + 2 + 1 */
1248  p->num_elements = (10 * p->num_addresses + mlp->pv.m_q * p->num_addresses +
1249  mlp->pv.m_q + p->num_peers + 2 + 1);
1251  "Rebuilding problem for %u peer(s) and %u addresse(s) and %u quality metrics == %u elements\n",
1252  p->num_peers,
1253  p->num_addresses,
1254  mlp->pv.m_q,
1255  p->num_elements);
1256 
1257  /* Set a problem name */
1258  glp_set_prob_name (p->prob, "GNUnet ATS bandwidth distribution");
1259  /* Set optimization direction to maximize */
1260  glp_set_obj_dir (p->prob, GLP_MAX);
1261 
1262  /* Create problem matrix */
1263  /* last +1 caused by glpk index starting with one: [1..elements]*/
1264  p->ci = 1;
1265  /* row index */
1266  p->ia = GNUNET_malloc (p->num_elements * sizeof (int));
1267  /* column index */
1268  p->ja = GNUNET_malloc (p->num_elements * sizeof (int));
1269  /* coefficient */
1270  p->ar = GNUNET_malloc (p->num_elements * sizeof (double));
1271 
1272  if ((NULL == p->ia) || (NULL == p->ja) || (NULL == p->ar))
1273  {
1274  LOG (GNUNET_ERROR_TYPE_ERROR, _("Problem size too large, cannot allocate memory!\n"));
1275  return GNUNET_SYSERR;
1276  }
1277 
1278  /* Adding invariant columns */
1280 
1281  /* Adding address independent constraint rows */
1283 
1284  /* Adding address dependent columns constraint rows */
1287  mlp);
1288 
1289  /* Load the matrix */
1290  LOG (GNUNET_ERROR_TYPE_DEBUG, "Loading matrix\n");
1291  glp_load_matrix(p->prob, (p->ci)-1, p->ia, p->ja, p->ar);
1293  {
1294  glp_scale_prob (p->prob, GLP_SF_AUTO);
1295  }
1296 
1297  return res;
1298 }
1299 
1300 
1307 static int
1309 {
1310  int res = 0;
1311  int res_status = 0;
1312  res = glp_simplex(mlp->p.prob, &mlp->control_param_lp);
1313  if (0 == res)
1314  LOG(GNUNET_ERROR_TYPE_DEBUG, "Solving LP problem: %s\n",
1315  mlp_solve_to_string (res));
1316  else
1317  LOG(GNUNET_ERROR_TYPE_DEBUG, "Solving LP problem failed: %s\n",
1318  mlp_solve_to_string (res));
1319 
1320  /* Analyze problem status */
1321  res_status = glp_get_status (mlp->p.prob);
1322  switch (res_status) {
1323  case GLP_OPT: /* solution is optimal */
1325  "Solving LP problem: %s, %s\n",
1326  mlp_solve_to_string(res),
1327  mlp_status_to_string(res_status));
1328  return GNUNET_OK;
1329  default:
1331  "Solving LP problem failed: %s %s\n",
1332  mlp_solve_to_string(res),
1333  mlp_status_to_string(res_status));
1334  return GNUNET_SYSERR;
1335  }
1336 }
1337 
1338 
1347 static int
1349  const struct GNUNET_PeerIdentity *key,
1350  void *value)
1351 {
1352  struct GAS_MLP_Handle *mlp = cls;
1353  struct ATS_Address *address;
1354  struct MLP_information *mlpi;
1355  double mlp_bw_in = MLP_NaN;
1356  double mlp_bw_out = MLP_NaN;
1357  double mlp_use = MLP_NaN;
1358 
1359  /* Check if we have to add this peer due to a pending request */
1361  key))
1362  {
1363  return GNUNET_OK;
1364  }
1365  address = value;
1366  GNUNET_assert (address->solver_information != NULL);
1367  mlpi = address->solver_information;
1368 
1369  mlp_bw_in = glp_mip_col_val(mlp->p.prob, mlpi->c_b);/* FIXME */
1370  if (mlp_bw_in > (double) UINT32_MAX)
1371  {
1372  LOG (GNUNET_ERROR_TYPE_DEBUG, "Overflow in assigned bandwidth, reducing ...\n" );
1373  mlp_bw_in = (double) UINT32_MAX;
1374  }
1375  mlp_bw_out = glp_mip_col_val(mlp->p.prob, mlpi->c_b);
1376  if (mlp_bw_out > (double) UINT32_MAX)
1377  {
1378  LOG (GNUNET_ERROR_TYPE_DEBUG, "Overflow in assigned bandwidth, reducing ...\n" );
1379  mlp_bw_out = (double) UINT32_MAX;
1380  }
1381  mlp_use = glp_mip_col_val(mlp->p.prob, mlpi->c_n);
1382 
1383  /*
1384  * Debug: solution
1385  * LOG (GNUNET_ERROR_TYPE_INFO, "MLP result address: `%s' `%s' length %u session %u, mlp use %.3f\n",
1386  * GNUNET_i2s(&address->peer), address->plugin,
1387  * address->addr_len, address->session_id);
1388  */
1389 
1390  if (GLP_YES == mlp_use)
1391  {
1392  /* This address was selected by the solver to be used */
1393  mlpi->n = GNUNET_YES;
1394  if (GNUNET_NO == address->active)
1395  {
1396  /* Address was not used before, enabling address */
1397  LOG (GNUNET_ERROR_TYPE_DEBUG, "%s %.2f : enabling address\n",
1398  (1 == mlp_use) ? "[x]": "[ ]", mlp_bw_out);
1399  address->active = GNUNET_YES;
1400  address->assigned_bw_in = mlp_bw_in;
1401  mlpi->b_in = mlp_bw_in;
1402  address->assigned_bw_out = mlp_bw_out;
1403  mlpi->b_out = mlp_bw_out;
1404  if ((NULL == mlp->exclude_peer) || (0 != GNUNET_memcmp (&address->peer, mlp->exclude_peer)))
1405  mlp->env->bandwidth_changed_cb (mlp->env->cls, address);
1406  return GNUNET_OK;
1407  }
1408  else if (GNUNET_YES == address->active)
1409  {
1410  /* Address was used before, check for bandwidth change */
1411  if ((mlp_bw_out != address->assigned_bw_out) ||
1412  (mlp_bw_in != address->assigned_bw_in))
1413  {
1414  LOG (GNUNET_ERROR_TYPE_DEBUG, "%s %.2f : bandwidth changed\n",
1415  (1 == mlp_use) ? "[x]": "[ ]", mlp_bw_out);
1416  address->assigned_bw_in = mlp_bw_in;
1417  mlpi->b_in = mlp_bw_in;
1418  address->assigned_bw_out = mlp_bw_out;
1419  mlpi->b_out = mlp_bw_out;
1420  if ((NULL == mlp->exclude_peer) || (0 != GNUNET_memcmp (&address->peer, mlp->exclude_peer)))
1421  mlp->env->bandwidth_changed_cb (mlp->env->cls, address);
1422  return GNUNET_OK;
1423  }
1424  }
1425  else
1426  GNUNET_break (0);
1427  }
1428  else if (GLP_NO == mlp_use)
1429  {
1430  /* This address was selected by the solver to be not used */
1431  mlpi->n = GNUNET_NO;
1432  if (GNUNET_NO == address->active)
1433  {
1434  /* Address was not used before, nothing to do */
1435  LOG (GNUNET_ERROR_TYPE_DEBUG, "%s %.2f : no change\n",
1436  (1 == mlp_use) ? "[x]": "[ ]", mlp_bw_out);
1437  return GNUNET_OK;
1438  }
1439  else if (GNUNET_YES == address->active)
1440  {
1441  /* Address was used before, disabling address */
1442  LOG (GNUNET_ERROR_TYPE_DEBUG, "%s %.2f : disabling address\n",
1443  (1 == mlp_use) ? "[x]": "[ ]", mlp_bw_out);
1444  address->active = GNUNET_NO;
1445  /* Set bandwidth to 0 */
1446  address->assigned_bw_in = 0;
1447  mlpi->b_in = 0;
1448  address->assigned_bw_out = 0;
1449  mlpi->b_out = 0;
1450  return GNUNET_OK;
1451  }
1452  else
1453  GNUNET_break (0);
1454  }
1455  else
1456  GNUNET_break (0);
1457 
1458  return GNUNET_OK;
1459 }
1460 
1461 
1462 static void
1463 notify (struct GAS_MLP_Handle *mlp,
1464  enum GAS_Solver_Operation op,
1465  enum GAS_Solver_Status stat,
1467 {
1468  mlp->env->info_cb (mlp->env->cls,
1469  op,
1470  stat,
1471  add);
1472 }
1473 
1474 
1475 static void
1476 mlp_branch_and_cut_cb (glp_tree *tree, void *info)
1477 {
1478  struct GAS_MLP_Handle *mlp = info;
1479  double mlp_obj = 0;
1480 
1481  switch (glp_ios_reason (tree))
1482  {
1483  case GLP_ISELECT:
1484  /* Do nothing here */
1485  break;
1486  case GLP_IPREPRO:
1487  /* Do nothing here */
1488  break;
1489  case GLP_IROWGEN:
1490  /* Do nothing here */
1491  break;
1492  case GLP_IHEUR:
1493  /* Do nothing here */
1494  break;
1495  case GLP_ICUTGEN:
1496  /* Do nothing here */
1497  break;
1498  case GLP_IBRANCH:
1499  /* Do nothing here */
1500  break;
1501  case GLP_IBINGO:
1502  /* A better solution was found */
1503  mlp->ps.mlp_gap = glp_ios_mip_gap (tree);
1504  mlp_obj = glp_mip_obj_val (mlp->p.prob);
1505  mlp->ps.lp_mlp_gap = (abs(mlp_obj - mlp->ps.lp_objective_value)) / (abs(mlp_obj) + DBL_EPSILON);
1506 
1508  "Found better integer solution, current gaps: %.3f <= %.3f, %.3f <= %.3f\n",
1509  mlp->ps.mlp_gap, mlp->pv.mip_gap,
1510  mlp->ps.lp_mlp_gap, mlp->pv.lp_mip_gap);
1511 
1512  if (mlp->ps.mlp_gap <= mlp->pv.mip_gap)
1513  {
1515  "Current LP/MLP gap of %.3f smaller than tolerated gap of %.3f, terminating search\n",
1516  mlp->ps.lp_mlp_gap, mlp->pv.lp_mip_gap);
1517  glp_ios_terminate (tree);
1518  }
1519 
1520  if (mlp->ps.lp_mlp_gap <= mlp->pv.lp_mip_gap)
1521  {
1523  "Current LP/MLP gap of %.3f smaller than tolerated gap of %.3f, terminating search\n",
1524  mlp->ps.lp_mlp_gap, mlp->pv.lp_mip_gap);
1525  glp_ios_terminate (tree);
1526  }
1527 
1528  break;
1529  default:
1530  break;
1531  }
1532  //GNUNET_break (0);
1533 }
1534 
1535 
1542 static int
1544 {
1545  struct GAS_MLP_Handle *mlp = solver;
1546  char *filename;
1547  int res_lp = 0;
1548  int mip_res = 0;
1549  int mip_status = 0;
1550 
1551  struct GNUNET_TIME_Absolute start_total;
1552  struct GNUNET_TIME_Absolute start_cur_op;
1553  struct GNUNET_TIME_Relative dur_total;
1554  struct GNUNET_TIME_Relative dur_setup;
1555  struct GNUNET_TIME_Relative dur_lp;
1556  struct GNUNET_TIME_Relative dur_mlp;
1557 
1558  GNUNET_assert(NULL != solver);
1559  dur_lp = GNUNET_TIME_UNIT_ZERO;
1560 
1561  if (GNUNET_YES == mlp->stat_bulk_lock)
1562  {
1563  mlp->stat_bulk_requests++;
1564  return GNUNET_NO;
1565  }
1568  start_total = GNUNET_TIME_absolute_get();
1569 
1571  {
1573  return GNUNET_OK; /* No pending requests */
1574  }
1576  {
1578  return GNUNET_OK; /* No addresses available */
1579  }
1580 
1581  if ((GNUNET_NO == mlp->stat_mlp_prob_changed)
1582  && (GNUNET_NO == mlp->stat_mlp_prob_updated))
1583  {
1584  LOG(GNUNET_ERROR_TYPE_DEBUG, "No changes to problem\n");
1586  return GNUNET_OK;
1587  }
1588  if (GNUNET_YES == mlp->stat_mlp_prob_changed)
1589  {
1590  LOG(GNUNET_ERROR_TYPE_DEBUG, "Problem size changed, rebuilding\n");
1592  mlp_delete_problem (mlp);
1593  if (GNUNET_SYSERR == mlp_create_problem (mlp))
1594  {
1596  return GNUNET_SYSERR;
1597  }
1599  if (GNUNET_NO == mlp->opt_dbg_intopt_presolver)
1600  {
1601  mlp->control_param_lp.presolve = GLP_YES; /* LP presolver, we need lp solution */
1602  mlp->control_param_mlp.presolve = GNUNET_NO; /* No presolver, we have LP solution */
1603  }
1604  else
1605  {
1606  mlp->control_param_lp.presolve = GNUNET_NO; /* LP presolver, we need lp solution */
1607  mlp->control_param_mlp.presolve = GLP_YES; /* No presolver, we have LP solution */
1608  dur_lp = GNUNET_TIME_UNIT_ZERO;
1609  }
1610  }
1611  else
1612  {
1613  LOG(GNUNET_ERROR_TYPE_DEBUG, "Problem was updated, resolving\n");
1614  }
1615 
1616  /* Reset solution info */
1617  mlp->ps.lp_objective_value = 0.0;
1618  mlp->ps.mlp_gap = 1.0;
1619  mlp->ps.mlp_objective_value = 0.0;
1620  mlp->ps.lp_mlp_gap = 0.0;
1621 
1622  dur_setup = GNUNET_TIME_absolute_get_duration (start_total);
1623 
1624  /* Run LP solver */
1625  if (GNUNET_NO == mlp->opt_dbg_intopt_presolver)
1626  {
1628  (GNUNET_YES == mlp->stat_mlp_prob_changed) ? GAS_INFO_FULL : GAS_INFO_UPDATED);
1630  "Running LP solver %s\n",
1631  (GLP_YES == mlp->control_param_lp.presolve)? "with presolver": "without presolver");
1632  start_cur_op = GNUNET_TIME_absolute_get();
1633 
1634  /* Solve LP */
1635  /* Only for debugging:
1636  * Always use LP presolver:
1637  * mlp->control_param_lp.presolve = GLP_YES; */
1638  res_lp = mlp_solve_lp_problem(mlp);
1639  if (GNUNET_OK == res_lp)
1640  {
1641  mlp->ps.lp_objective_value = glp_get_obj_val (mlp->p.prob);
1643  "LP solution was: %.3f\n",
1644  mlp->ps.lp_objective_value);
1645  }
1646 
1647  dur_lp = GNUNET_TIME_absolute_get_duration (start_cur_op);
1649  (GNUNET_OK == res_lp) ? GAS_STAT_SUCCESS : GAS_STAT_FAIL,
1650  (GNUNET_YES == mlp->stat_mlp_prob_changed) ? GAS_INFO_FULL : GAS_INFO_UPDATED);
1651  }
1652 
1654  res_lp = GNUNET_OK;
1655 
1656  /* Run MLP solver */
1657  if ((GNUNET_OK == res_lp) || (GNUNET_YES == mlp->opt_dbg_intopt_presolver))
1658  {
1659  LOG(GNUNET_ERROR_TYPE_DEBUG, "Running MLP solver \n");
1661  (GNUNET_YES == mlp->stat_mlp_prob_changed) ? GAS_INFO_FULL : GAS_INFO_UPDATED);
1662  start_cur_op = GNUNET_TIME_absolute_get();
1663 
1664  /* Solve MIP */
1665 
1666  /* Only for debugging, always use LP presolver */
1668  mlp->control_param_mlp.presolve = GNUNET_YES;
1669 
1670  mip_res = glp_intopt (mlp->p.prob, &mlp->control_param_mlp);
1671  switch (mip_res)
1672  {
1673  case 0:
1674  /* Successful */
1676  "Solving MLP problem: %s\n",
1677  mlp_solve_to_string (mip_res));
1678  break;
1679  case GLP_ETMLIM: /* Time limit reached */
1680  case GLP_EMIPGAP: /* MIP gap tolerance limit reached */
1681  case GLP_ESTOP: /* Solver was instructed to stop*/
1682  /* Semi-successful */
1684  "Solving MLP problem solution was interupted: %s\n",
1685  mlp_solve_to_string (mip_res));
1686  break;
1687  case GLP_EBOUND:
1688  case GLP_EROOT:
1689  case GLP_ENOPFS:
1690  case GLP_ENODFS:
1691  case GLP_EFAIL:
1692  default:
1693  /* Fail */
1695  "Solving MLP problem failed: %s\n",
1696  mlp_solve_to_string (mip_res));
1697  break;
1698  }
1699 
1700  /* Analyze problem status */
1701  mip_status = glp_mip_status(mlp->p.prob);
1702  switch (mip_status)
1703  {
1704  case GLP_OPT: /* solution is optimal */
1706  "Solution of MLP problem is optimal: %s, %s\n",
1707  mlp_solve_to_string (mip_res),
1708  mlp_status_to_string (mip_status));
1709  mip_res = GNUNET_OK;
1710  break;
1711  case GLP_FEAS: /* solution is feasible but not proven optimal */
1712 
1713  if ( (mlp->ps.mlp_gap <= mlp->pv.mip_gap) ||
1714  (mlp->ps.lp_mlp_gap <= mlp->pv.lp_mip_gap) )
1715  {
1717  "Solution of MLP problem is feasible and solution within gap constraints: %s, %s\n",
1718  mlp_solve_to_string (mip_res),
1719  mlp_status_to_string (mip_status));
1720  mip_res = GNUNET_OK;
1721  }
1722  else
1723  {
1725  "Solution of MLP problem is feasible but solution not within gap constraints: %s, %s\n",
1726  mlp_solve_to_string (mip_res),
1727  mlp_status_to_string (mip_status));
1728  mip_res = GNUNET_SYSERR;
1729  }
1730  break;
1731  case GLP_UNDEF: /* Solution undefined */
1732  case GLP_NOFEAS: /* No feasible solution */
1733  default:
1735  "Solving MLP problem failed: %s %s\n",
1736  mlp_solve_to_string (mip_res),
1737  mlp_status_to_string (mip_status));
1738  mip_res = GNUNET_SYSERR;
1739  break;
1740  }
1741 
1742  dur_mlp = GNUNET_TIME_absolute_get_duration (start_cur_op);
1743  dur_total = GNUNET_TIME_absolute_get_duration (start_total);
1744 
1746  (GNUNET_OK == mip_res) ? GAS_STAT_SUCCESS : GAS_STAT_FAIL,
1747  (GNUNET_YES == mlp->stat_mlp_prob_changed) ? GAS_INFO_FULL : GAS_INFO_UPDATED);
1748  }
1749  else
1750  {
1751  /* Do not execute mip solver since lp solution is invalid */
1752  dur_mlp = GNUNET_TIME_UNIT_ZERO;
1753  dur_total = GNUNET_TIME_absolute_get_duration (start_total);
1754 
1756  (GNUNET_YES == mlp->stat_mlp_prob_changed) ? GAS_INFO_FULL : GAS_INFO_UPDATED);
1757  mip_res = GNUNET_SYSERR;
1758  }
1759 
1760  /* Notify about end */
1762  ((GNUNET_OK == mip_res) && (GNUNET_OK == mip_res)) ? GAS_STAT_SUCCESS : GAS_STAT_FAIL,
1763  (GNUNET_YES == mlp->stat_mlp_prob_changed) ? GAS_INFO_FULL : GAS_INFO_UPDATED);
1764 
1766  "Execution time for %s solve: (total/setup/lp/mlp) : %llu %llu %llu %llu\n",
1767  (GNUNET_YES == mlp->stat_mlp_prob_changed) ? "full" : "updated",
1768  (unsigned long long) dur_total.rel_value_us,
1769  (unsigned long long) dur_setup.rel_value_us,
1770  (unsigned long long) dur_lp.rel_value_us,
1771  (unsigned long long) dur_mlp.rel_value_us);
1772 
1773  /* Save stats */
1774  mlp->ps.lp_res = res_lp;
1775  mlp->ps.mip_res = mip_res;
1776  mlp->ps.lp_presolv = mlp->control_param_lp.presolve;
1777  mlp->ps.mip_presolv = mlp->control_param_mlp.presolve;
1778  mlp->ps.p_cols = glp_get_num_cols(mlp->p.prob);
1779  mlp->ps.p_rows = glp_get_num_rows(mlp->p.prob);
1780  mlp->ps.p_elements = mlp->p.num_elements;
1781 
1782  /* Propagate result*/
1784  (GNUNET_OK == res_lp) && (GNUNET_OK == mip_res) ? GAS_STAT_SUCCESS : GAS_STAT_FAIL,
1785  GAS_INFO_NONE);
1786  if ((GNUNET_OK == res_lp) && (GNUNET_OK == mip_res))
1787  {
1789  &mlp_propagate_results, mlp);
1790  }
1792  (GNUNET_OK == res_lp) && (GNUNET_OK == mip_res) ? GAS_STAT_SUCCESS : GAS_STAT_FAIL,
1793  GAS_INFO_NONE);
1794 
1796  if ( (GNUNET_YES == mlp->opt_dump_problem_all) ||
1797  (mlp->opt_dump_problem_on_fail && ((GNUNET_OK != res_lp) || (GNUNET_OK != mip_res))) )
1798  {
1799  /* Write problem to disk */
1800  switch (mlp->opt_log_format) {
1801  case MLP_CPLEX:
1802  GNUNET_asprintf(&filename, "problem_p_%u_a%u_%llu.cplex", mlp->p.num_peers,
1803  mlp->p.num_addresses, time.abs_value_us);
1804  glp_write_lp (mlp->p.prob, NULL, filename);
1805  break;
1806  case MLP_GLPK:
1807  GNUNET_asprintf(&filename, "problem_p_%u_a%u_%llu.glpk", mlp->p.num_peers,
1808  mlp->p.num_addresses, time.abs_value_us);
1809  glp_write_prob (mlp->p.prob, 0, filename);
1810  break;
1811  case MLP_MPS:
1812  GNUNET_asprintf(&filename, "problem_p_%u_a%u_%llu.mps", mlp->p.num_peers,
1813  mlp->p.num_addresses, time.abs_value_us);
1814  glp_write_mps (mlp->p.prob, GLP_MPS_FILE, NULL, filename);
1815  break;
1816  default:
1817  break;
1818  }
1819  LOG(GNUNET_ERROR_TYPE_ERROR, "Dumped problem to file: `%s' \n", filename);
1820  GNUNET_free(filename);
1821  }
1822  if ( (mlp->opt_dump_solution_all) ||
1823  (mlp->opt_dump_solution_on_fail && ((GNUNET_OK != res_lp) || (GNUNET_OK != mip_res))) )
1824  {
1825  /* Write solution to disk */
1826  GNUNET_asprintf(&filename, "problem_p_%u_a%u_%llu.sol", mlp->p.num_peers,
1827  mlp->p.num_addresses, time.abs_value_us);
1828  glp_print_mip(mlp->p.prob, filename);
1829  LOG(GNUNET_ERROR_TYPE_ERROR, "Dumped solution to file: `%s' \n", filename);
1830  GNUNET_free(filename);
1831  }
1832 
1833  /* Reset change and update marker */
1834  mlp->control_param_lp.presolve = GLP_NO;
1837 
1838  if ((GNUNET_OK == res_lp) && (GNUNET_OK == mip_res))
1839  return GNUNET_OK;
1840  else
1841  return GNUNET_SYSERR;
1842 }
1843 
1851 static void
1852 GAS_mlp_address_add (void *solver,
1853  struct ATS_Address *address,
1854  uint32_t network)
1855 {
1856  struct GAS_MLP_Handle *mlp = solver;
1857 
1858  if (GNUNET_NT_COUNT <= network)
1859  {
1860  GNUNET_break (0);
1861  return;
1862  }
1863 
1864  if (NULL == address->solver_information)
1865  {
1866  address->solver_information = GNUNET_new (struct MLP_information);
1867  }
1868  else
1870  _("Adding address for peer `%s' multiple times\n"),
1871  GNUNET_i2s(&address->peer));
1872 
1873  /* Is this peer included in the problem? */
1874  if (NULL ==
1876  &address->peer))
1877  {
1878  /* FIXME: should this be an error? */
1880  "Adding address for peer `%s' without address request\n",
1881  GNUNET_i2s(&address->peer));
1882  return;
1883  }
1884 
1886  "Adding address for peer `%s' with address request \n",
1887  GNUNET_i2s(&address->peer));
1888  /* Problem size changed: new address for peer with pending request */
1890  if (GNUNET_YES == mlp->opt_mlp_auto_solve)
1891  GAS_mlp_solve_problem (solver);
1892 }
1893 
1894 
1901 static void
1903  struct ATS_Address *address)
1904 {
1905  struct MLP_information *mlpi = address->solver_information;
1906  struct GAS_MLP_Handle *mlp = solver;
1907 
1908  if (NULL == mlp->p.prob)
1909  return; /* There is no MLP problem to update yet */
1910 
1911  if (NULL == mlpi)
1912  {
1914  _("Updating address property for peer `%s' %p not added before\n"),
1915  GNUNET_i2s (&address->peer),
1916  address);
1917  GNUNET_break (0);
1918  return;
1919  }
1920  if (NULL ==
1922  &address->peer))
1923  {
1924  /* Peer is not requested, so no need to update problem */
1925  return;
1926  }
1928  "Updating properties for peer `%s'\n",
1929  GNUNET_i2s(&address->peer));
1930 
1932  return;
1933 
1934  /* Update c7) [r_q[index]][c_b] = f_q * q_averaged[type_index] */
1935  if ( (GNUNET_YES ==
1938  mlpi->c_b,
1939  address->norm_delay.norm,
1940  __LINE__)) ||
1941  (GNUNET_YES ==
1944  mlpi->c_b,
1945  address->norm_distance.norm,
1946  __LINE__)) )
1947  {
1949  if (GNUNET_YES == mlp->opt_mlp_auto_solve)
1950  GAS_mlp_solve_problem (solver);
1951  }
1952 
1953 }
1954 
1955 
1963 static int
1965  const struct GNUNET_PeerIdentity *key,
1966  void *value)
1967 {
1968  static int counter = 0;
1969  struct ATS_Address **aa = cls;
1970  struct ATS_Address *addr = value;
1971  struct MLP_information *mlpi = addr->solver_information;
1972 
1973  if (mlpi == NULL)
1974  return GNUNET_YES;
1975 
1976  /*
1977  * Debug output
1978  * GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1979  * "MLP [%u] Peer `%s' %s length %u session %u active %s mlp active %s\n",
1980  * counter, GNUNET_i2s (&addr->peer), addr->plugin, addr->addr_len, addr->session_id,
1981  * (GNUNET_YES == addr->active) ? "active" : "inactive",
1982  * (GNUNET_YES == mlpi->n) ? "active" : "inactive");
1983  */
1984 
1985  if (GNUNET_YES == mlpi->n)
1986  {
1987 
1988  (*aa) = addr;
1989  (*aa)->assigned_bw_in = mlpi->b_in;
1990  (*aa)->assigned_bw_out = mlpi->b_out;
1991  return GNUNET_NO;
1992  }
1993  counter++;
1994  return GNUNET_YES;
1995 }
1996 
1997 
1998 static double
2000  const struct GNUNET_PeerIdentity *peer)
2001 {
2002  double res;
2003  const double *preferences;
2004  int c;
2005 
2006  preferences = mlp->env->get_preferences (mlp->env->cls, peer);
2007  res = 0.0;
2008  for (c = 0; c < GNUNET_ATS_PREFERENCE_END; c++)
2009  {
2010  /* fprintf (stderr, "VALUE[%u] %s %.3f \n",
2011  * c, GNUNET_i2s (&cur->addr->peer), t[c]); */
2012  res += preferences[c];
2013  }
2014 
2016  res += 1.0;
2017 
2019  "Peer preference for peer `%s' == %.2f\n",
2020  GNUNET_i2s(peer), res);
2021 
2022  return res;
2023 }
2024 
2025 
2032 static void
2034  const struct GNUNET_PeerIdentity *peer)
2035 {
2036  struct GAS_MLP_Handle *mlp = solver;
2037  struct ATS_Peer *p;
2038  struct ATS_Address *res;
2039 
2041  "Getting preferred address for `%s'\n",
2042  GNUNET_i2s (peer));
2043 
2044  /* Is this peer included in the problem? */
2045  if (NULL ==
2047  peer))
2048  {
2049  LOG (GNUNET_ERROR_TYPE_INFO, "Adding peer `%s' to list of requested_peers with requests\n",
2050  GNUNET_i2s (peer));
2051 
2052  p = GNUNET_new (struct ATS_Peer);
2053  p->id = (*peer);
2054  p->f = get_peer_pref_value (mlp, peer);
2056  peer, p,
2058 
2059  /* Added new peer, we have to rebuild problem before solving */
2061 
2062  if ((GNUNET_YES == mlp->opt_mlp_auto_solve)&&
2064  peer)))
2065  {
2066  mlp->exclude_peer = peer;
2067  GAS_mlp_solve_problem (mlp);
2068  mlp->exclude_peer = NULL;
2069  }
2070  }
2071  /* Get prefered address */
2072  res = NULL;
2075  if (NULL != res)
2076  mlp->env->bandwidth_changed_cb (mlp->env->cls,
2077  res);
2078 }
2079 
2080 
2089 static void
2091  struct ATS_Address *address)
2092 {
2093  struct GAS_MLP_Handle *mlp = solver;
2094  struct MLP_information *mlpi;
2095  struct ATS_Address *res;
2096  int was_active;
2097 
2098  mlpi = address->solver_information;
2099  if (NULL != mlpi)
2100  {
2101  /* Remove full address */
2102  GNUNET_free (mlpi);
2103  address->solver_information = NULL;
2104  }
2105  was_active = address->active;
2106  address->active = GNUNET_NO;
2107  address->assigned_bw_in = 0;
2108  address->assigned_bw_out = 0;
2109 
2110  /* Is this peer included in the problem? */
2111  if (NULL ==
2113  &address->peer))
2114  {
2116  "Deleting address for peer `%s' without address request \n",
2117  GNUNET_i2s(&address->peer));
2118  return;
2119  }
2121  "Deleting address for peer `%s' with address request \n",
2122  GNUNET_i2s (&address->peer));
2123 
2124  /* Problem size changed: new address for peer with pending request */
2126  if (GNUNET_YES == mlp->opt_mlp_auto_solve)
2127  {
2128  GAS_mlp_solve_problem (solver);
2129  }
2130  if (GNUNET_YES == was_active)
2131  {
2132  GAS_mlp_get_preferred_address (solver, &address->peer);
2133  res = NULL;
2135  &address->peer,
2137  &res);
2138  if (NULL == res)
2139  {
2140  /* No alternative address, disconnecting peer */
2141  mlp->env->bandwidth_changed_cb (mlp->env->cls, address);
2142  }
2143  }
2144 }
2145 
2146 
2152 static void
2153 GAS_mlp_bulk_start (void *solver)
2154 {
2155  struct GAS_MLP_Handle *s = solver;
2156 
2158  "Locking solver for bulk operation ...\n");
2159  GNUNET_assert (NULL != solver);
2160  s->stat_bulk_lock ++;
2161 }
2162 
2163 
2164 static void
2165 GAS_mlp_bulk_stop (void *solver)
2166 {
2167  struct GAS_MLP_Handle *s = solver;
2168 
2170  "Unlocking solver from bulk operation ...\n");
2171  GNUNET_assert (NULL != solver);
2172 
2173  if (s->stat_bulk_lock < 1)
2174  {
2175  GNUNET_break (0);
2176  return;
2177  }
2178  s->stat_bulk_lock --;
2179 
2180  if (0 < s->stat_bulk_requests)
2181  {
2182  GAS_mlp_solve_problem (solver);
2183  s->stat_bulk_requests= 0;
2184  }
2185 }
2186 
2187 
2188 
2195 static void
2197  const struct GNUNET_PeerIdentity *peer)
2198 {
2199  struct GAS_MLP_Handle *mlp = solver;
2200  struct ATS_Peer *p = NULL;
2201 
2202  GNUNET_assert (NULL != solver);
2203  GNUNET_assert (NULL != peer);
2204  if (NULL != (p = GNUNET_CONTAINER_multipeermap_get (mlp->requested_peers, peer)))
2205  {
2208  GNUNET_free (p);
2209 
2211  if (GNUNET_YES == mlp->opt_mlp_auto_solve)
2212  {
2213  GAS_mlp_solve_problem (solver);
2214  }
2215  }
2216 }
2217 
2218 
2227 static void
2229  const struct GNUNET_PeerIdentity *peer,
2230  enum GNUNET_ATS_PreferenceKind kind,
2231  double pref_rel)
2232 {
2233  struct GAS_MLP_Handle *mlp = solver;
2234  struct ATS_Peer *p;
2235 
2237  "Changing preference for address for peer `%s' to %.2f\n",
2238  GNUNET_i2s(peer),
2239  pref_rel);
2240 
2242  "# LP address preference changes", 1, GNUNET_NO);
2243  /* Update the constraints with changed preferences */
2244 
2245 
2246 
2247  /* Update relativity constraint c9 */
2248  if (NULL == (p = GNUNET_CONTAINER_multipeermap_get (mlp->requested_peers, peer)))
2249  {
2251  "Updating preference for unknown peer `%s'\n",
2252  GNUNET_i2s(peer));
2253  return;
2254  }
2255 
2256  if (GNUNET_NO == mlp->opt_dbg_feasibility_only)
2257  {
2258  p->f = get_peer_pref_value (mlp, peer);
2260  p->r_c9,
2261  mlp->p.c_r,
2262  - p->f,
2263  __LINE__);
2264 
2265  /* Problem size changed: new address for peer with pending request */
2267  if (GNUNET_YES == mlp->opt_mlp_auto_solve)
2268  GAS_mlp_solve_problem (solver);
2269  }
2270 }
2271 
2272 
2283 static void
2285  struct GNUNET_SERVICE_Client *application,
2286  const struct GNUNET_PeerIdentity *peer,
2287  const struct GNUNET_TIME_Relative scope,
2288  enum GNUNET_ATS_PreferenceKind kind,
2289  double score)
2290 {
2291  struct GAS_PROPORTIONAL_Handle *s = solver;
2292 
2293  GNUNET_assert (NULL != solver);
2294  GNUNET_assert (NULL != peer);
2295  GNUNET_assert (NULL != s);
2296 }
2297 
2298 
2299 static int
2300 mlp_free_peers (void *cls,
2301  const struct GNUNET_PeerIdentity *key, void *value)
2302 {
2303  struct GNUNET_CONTAINER_MultiPeerMap *map = cls;
2304  struct ATS_Peer *p = value;
2305 
2307  GNUNET_CONTAINER_multipeermap_remove (map, key, value));
2308  GNUNET_free (p);
2309 
2310  return GNUNET_OK;
2311 }
2312 
2313 
2320 void *
2322 {
2323  struct GNUNET_ATS_SolverFunctions *sf = cls;
2324  struct GAS_MLP_Handle *mlp = sf->cls;
2325 
2327  "Shutting down mlp solver\n");
2328  mlp_delete_problem (mlp);
2330  &mlp_free_peers,
2331  mlp->requested_peers);
2333  mlp->requested_peers = NULL;
2334 
2335  /* Clean up GLPK environment */
2336  glp_free_env();
2337  GNUNET_free (mlp);
2338 
2340  "Shutdown down of mlp solver complete\n");
2341  return NULL;
2342 }
2343 
2344 
2345 void *
2347 {
2348  static struct GNUNET_ATS_SolverFunctions sf;
2350  struct GAS_MLP_Handle * mlp = GNUNET_new (struct GAS_MLP_Handle);
2351  float f_tmp;
2352  unsigned long long tmp;
2353  unsigned int b_min;
2354  unsigned int n_min;
2355  int c;
2356  char *outputformat;
2357 
2358  struct GNUNET_TIME_Relative max_duration;
2359  long long unsigned int max_iterations;
2360 
2361  /* Init GLPK environment */
2362  int res = glp_init_env();
2363  switch (res) {
2364  case 0:
2365  LOG (GNUNET_ERROR_TYPE_DEBUG, "GLPK: `%s'\n",
2366  "initialization successful");
2367  break;
2368  case 1:
2369  LOG (GNUNET_ERROR_TYPE_DEBUG, "GLPK: `%s'\n",
2370  "environment is already initialized");
2371  break;
2372  case 2:
2373  LOG (GNUNET_ERROR_TYPE_ERROR, "Could not init GLPK: `%s'\n",
2374  "initialization failed (insufficient memory)");
2375  GNUNET_free(mlp);
2376  return NULL;
2377  break;
2378  case 3:
2379  LOG (GNUNET_ERROR_TYPE_ERROR, "Could not init GLPK: `%s'\n",
2380  "initialization failed (unsupported programming model)");
2381  GNUNET_free(mlp);
2382  return NULL;
2383  break;
2384  default:
2385  break;
2386  }
2387 
2389  "ats", "MLP_DUMP_PROBLEM_ALL");
2390  if (GNUNET_SYSERR == mlp->opt_dump_problem_all)
2392 
2394  "ats", "MLP_DUMP_SOLUTION_ALL");
2397 
2399  "ats", "MLP_DUMP_PROBLEM_ON_FAIL");
2402 
2404  "ats", "MLP_DUMP_SOLUTION_ON_FAIL");
2407 
2409  "ats", "MLP_DBG_GLPK_VERBOSE");
2410  if (GNUNET_SYSERR == mlp->opt_dbg_glpk_verbose)
2412 
2414  "ats", "MLP_DBG_FEASIBILITY_ONLY");
2419  "MLP solver is configured to check feasibility only!\n");
2420 
2422  "ats", "MLP_DBG_AUTOSCALE_PROBLEM");
2427  "MLP solver is configured automatically scale the problem!\n");
2428 
2430  "ats", "MLP_DBG_INTOPT_PRESOLVE");
2435  "MLP solver is configured use the mlp presolver\n");
2436 
2438  "ats", "MLP_DBG_OPTIMIZE_DIVERSITY");
2443  "MLP solver is not optimizing for diversity\n");
2444 
2446  "ats", "MLP_DBG_OPTIMIZE_RELATIVITY");
2451  "MLP solver is not optimizing for relativity\n");
2452 
2454  "ats", "MLP_DBG_OPTIMIZE_QUALITY");
2457  if (GNUNET_NO == mlp->opt_dbg_optimize_quality)
2459  "MLP solver is not optimizing for quality\n");
2460 
2462  "ats", "MLP_DBG_OPTIMIZE_UTILITY");
2465  if (GNUNET_NO == mlp->opt_dbg_optimize_utility)
2467  "MLP solver is not optimizing for utility\n");
2468 
2469  if ( (GNUNET_NO == mlp->opt_dbg_optimize_utility) &&
2470  (GNUNET_NO == mlp->opt_dbg_optimize_quality) &&
2472  (GNUNET_NO == mlp->opt_dbg_optimize_utility) &&
2474  {
2476  _("MLP solver is not optimizing for anything, changing to feasibility check\n"));
2478  }
2479 
2481  "ats", "MLP_LOG_FORMAT", &outputformat))
2482  mlp->opt_log_format = MLP_CPLEX;
2483  else
2484  {
2485  GNUNET_STRINGS_utf8_toupper(outputformat, outputformat);
2486  if (0 == strcmp (outputformat, "MPS"))
2487  {
2488  mlp->opt_log_format = MLP_MPS;
2489  }
2490  else if (0 == strcmp (outputformat, "CPLEX"))
2491  {
2492  mlp->opt_log_format = MLP_CPLEX;
2493  }
2494  else if (0 == strcmp (outputformat, "GLPK"))
2495  {
2496  mlp->opt_log_format = MLP_GLPK;
2497  }
2498  else
2499  {
2501  "Invalid log format `%s' in configuration, using CPLEX!\n",
2502  outputformat);
2503  mlp->opt_log_format = MLP_CPLEX;
2504  }
2505  GNUNET_free (outputformat);
2506  }
2507 
2508  mlp->pv.BIG_M = (double) BIG_M_VALUE;
2509 
2510  mlp->pv.mip_gap = (double) 0.0;
2512  "MLP_MAX_MIP_GAP", &f_tmp))
2513  {
2514  if ((f_tmp < 0.0) || (f_tmp > 1.0))
2515  {
2516  LOG (GNUNET_ERROR_TYPE_ERROR, _("Invalid %s configuration %f \n"),
2517  "MIP gap", f_tmp);
2518  }
2519  else
2520  {
2521  mlp->pv.mip_gap = f_tmp;
2522  LOG (GNUNET_ERROR_TYPE_INFO, "Using %s of %.3f\n",
2523  "MIP gap", f_tmp);
2524  }
2525  }
2526 
2527  mlp->pv.lp_mip_gap = (double) 0.0;
2529  "MLP_MAX_LP_MIP_GAP", &f_tmp))
2530  {
2531  if ((f_tmp < 0.0) || (f_tmp > 1.0))
2532  {
2533  LOG (GNUNET_ERROR_TYPE_ERROR, _("Invalid %s configuration %f \n"),
2534  "LP/MIP", f_tmp);
2535  }
2536  else
2537  {
2538  mlp->pv.lp_mip_gap = f_tmp;
2539  LOG (GNUNET_ERROR_TYPE_INFO, "Using %s gap of %.3f\n",
2540  "LP/MIP", f_tmp);
2541  }
2542  }
2543 
2544  /* Get timeout for iterations */
2546  "MLP_MAX_DURATION", &max_duration))
2547  {
2548  max_duration = MLP_MAX_EXEC_DURATION;
2549  }
2550 
2551  /* Get maximum number of iterations */
2553  "MLP_MAX_ITERATIONS", &max_iterations))
2554  {
2555  max_iterations = MLP_MAX_ITERATIONS;
2556  }
2557 
2558  /* Get diversity coefficient from configuration */
2559  mlp->pv.co_D = MLP_DEFAULT_D;
2561  "MLP_COEFFICIENT_D", &f_tmp))
2562  {
2563  if ((f_tmp < 0.0))
2564  {
2565  LOG (GNUNET_ERROR_TYPE_ERROR, _("Invalid %s configuration %f \n"),
2566  "MLP_COEFFICIENT_D", f_tmp);
2567  }
2568  else
2569  {
2570  mlp->pv.co_D = f_tmp;
2571  LOG (GNUNET_ERROR_TYPE_INFO, "Using %s gap of %.3f\n",
2572  "MLP_COEFFICIENT_D", f_tmp);
2573  }
2574  }
2575 
2576  /* Get relativity coefficient from configuration */
2577  mlp->pv.co_R = MLP_DEFAULT_R;
2579  "MLP_COEFFICIENT_R", &f_tmp))
2580  {
2581  if ((f_tmp < 0.0))
2582  {
2583  LOG (GNUNET_ERROR_TYPE_ERROR, _("Invalid %s configuration %f \n"),
2584  "MLP_COEFFICIENT_R", f_tmp);
2585  }
2586  else
2587  {
2588  mlp->pv.co_R = f_tmp;
2589  LOG (GNUNET_ERROR_TYPE_INFO, "Using %s gap of %.3f\n",
2590  "MLP_COEFFICIENT_R", f_tmp);
2591  }
2592  }
2593 
2594 
2595  /* Get utilization coefficient from configuration */
2596  mlp->pv.co_U = MLP_DEFAULT_U;
2598  "MLP_COEFFICIENT_U", &f_tmp))
2599  {
2600  if ((f_tmp < 0.0))
2601  {
2602  LOG (GNUNET_ERROR_TYPE_ERROR, _("Invalid %s configuration %f \n"),
2603  "MLP_COEFFICIENT_U", f_tmp);
2604  }
2605  else
2606  {
2607  mlp->pv.co_U = f_tmp;
2608  LOG (GNUNET_ERROR_TYPE_INFO, "Using %s gap of %.3f\n",
2609  "MLP_COEFFICIENT_U", f_tmp);
2610  }
2611  }
2612 
2613  /* Get quality metric coefficients from configuration */
2614  for (c = 0; c < RQ_QUALITY_METRIC_COUNT; c++)
2615  {
2616  /* initialize quality coefficients with default value 1.0 */
2617  mlp->pv.co_Q[c] = MLP_DEFAULT_QUALITY;
2618  }
2619 
2620 
2621  if (GNUNET_OK ==
2623  "MLP_COEFFICIENT_QUALITY_DELAY",
2624  &tmp))
2625  mlp->pv.co_Q[RQ_QUALITY_METRIC_DELAY] = (double) tmp / 100;
2626  else
2628 
2629  if (GNUNET_OK ==
2631  "MLP_COEFFICIENT_QUALITY_DISTANCE",
2632  &tmp))
2633  mlp->pv.co_Q[RQ_QUALITY_METRIC_DISTANCE] = (double) tmp / 100;
2634  else
2636 
2637  /* Get minimum bandwidth per used address from configuration */
2639  "MLP_MIN_BANDWIDTH",
2640  &tmp))
2641  b_min = tmp;
2642  else
2643  {
2644  b_min = ntohl (GNUNET_CONSTANTS_DEFAULT_BW_IN_OUT.value__);
2645  }
2646 
2647  /* Get minimum number of connections from configuration */
2649  "MLP_MIN_CONNECTIONS",
2650  &tmp))
2651  n_min = tmp;
2652  else
2654 
2655  /* Init network quotas */
2656  for (c = 0; c < GNUNET_NT_COUNT; c++)
2657  {
2658  mlp->pv.quota_index[c] = c;
2659  mlp->pv.quota_out[c] = env->out_quota[c];
2660  mlp->pv.quota_in[c] = env->in_quota[c];
2661 
2663  "Quota for network `%s' (in/out) %llu/%llu\n",
2664  GNUNET_NT_to_string (c),
2665  mlp->pv.quota_out[c],
2666  mlp->pv.quota_in[c]);
2667  /* Check if defined quota could make problem unsolvable */
2668  if ((n_min * b_min) > mlp->pv.quota_out[c])
2669  {
2671  _("Adjusting inconsistent outbound quota configuration for network `%s', is %llu must be at least %llu\n"),
2673  mlp->pv.quota_out[c],
2674  (n_min * b_min));
2675  mlp->pv.quota_out[c] = (n_min * b_min);
2676  }
2677  if ((n_min * b_min) > mlp->pv.quota_in[c])
2678  {
2680  _("Adjusting inconsistent inbound quota configuration for network `%s', is %llu must be at least %llu\n"),
2682  mlp->pv.quota_in[c],
2683  (n_min * b_min));
2684  mlp->pv.quota_in[c] = (n_min * b_min);
2685  }
2686  /* Check if bandwidth is too big to make problem solvable */
2687  if (mlp->pv.BIG_M < mlp->pv.quota_out[c])
2688  {
2690  _("Adjusting outbound quota configuration for network `%s'from %llu to %.0f\n"),
2692  mlp->pv.quota_out[c],
2693  mlp->pv.BIG_M);
2694  mlp->pv.quota_out[c] = mlp->pv.BIG_M ;
2695  }
2696  if (mlp->pv.BIG_M < mlp->pv.quota_in[c])
2697  {
2699  _("Adjusting inbound quota configuration for network `%s' from %llu to %.0f\n"),
2701  mlp->pv.quota_in[c],
2702  mlp->pv.BIG_M);
2703  mlp->pv.quota_in[c] = mlp->pv.BIG_M ;
2704  }
2705  }
2706  mlp->env = env;
2707  sf.cls = mlp;
2708  sf.s_add = &GAS_mlp_address_add;
2717 
2718  /* Setting MLP Input variables */
2719  mlp->pv.b_min = b_min;
2720  mlp->pv.n_min = n_min;
2726  mlp->stat_bulk_requests = 0;
2727  mlp->stat_bulk_lock = 0;
2728 
2729  /* Setup GLPK */
2730  /* Redirect GLPK output to GNUnet logging */
2731  glp_term_hook (&mlp_term_hook, (void *) mlp);
2732 
2733  /* Init LP solving parameters */
2734  glp_init_smcp(&mlp->control_param_lp);
2735  mlp->control_param_lp.msg_lev = GLP_MSG_OFF;
2736  if (GNUNET_YES == mlp->opt_dbg_glpk_verbose)
2737  mlp->control_param_lp.msg_lev = GLP_MSG_ALL;
2738 
2739  mlp->control_param_lp.it_lim = max_iterations;
2740  mlp->control_param_lp.tm_lim = max_duration.rel_value_us / 1000LL;
2741 
2742  /* Init MLP solving parameters */
2743  glp_init_iocp(&mlp->control_param_mlp);
2744  /* Setting callback function */
2745  mlp->control_param_mlp.cb_func = &mlp_branch_and_cut_cb;
2746  mlp->control_param_mlp.cb_info = mlp;
2747  mlp->control_param_mlp.msg_lev = GLP_MSG_OFF;
2748  mlp->control_param_mlp.mip_gap = mlp->pv.mip_gap;
2749  if (GNUNET_YES == mlp->opt_dbg_glpk_verbose)
2750  mlp->control_param_mlp.msg_lev = GLP_MSG_ALL;
2751  mlp->control_param_mlp.tm_lim = max_duration.rel_value_us / 1000LL;
2752 
2753  LOG (GNUNET_ERROR_TYPE_DEBUG, "solver ready\n");
2754 
2755  return &sf;
2756 }
2757 
2758 /* 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:81
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:78
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:208
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:249
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:580
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:79
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:80
#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.