1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161171181191201211221231241251261271281291301311321331341351361371381391401411421431441451461471481491501511521531541551561571581591601611621631641651661671681691701711721731741751761771781791801811821831841851861871881891901911921931941951961971981992002012022032042052062072082092102112122132142152162172182192202212222232242252262272282292302312322332342352362372382392402412422432442452462472482492502512522532542552562572582592602612622632642652662672682692702712722732742752762772782792802812822832842852862872882892902912922932942952962972982993003013023033043053063073083093103113123133143153163173183193203213223233243253263273283293303313323333343353363373383393403413423433443453463473483493503513523533543553563573583593603613623633643653663673683693703713723733743753763773783793803813823833843853863873883893903913923933943953963973983994004014024034044054064074084094104114124134144154164174184194204214224234244254264274284294304314324334344354364374384394404414424434444454464474484494504514524534544554564574584594604614624634644654664674684694704714724734744754764774784794804814824834844854864874884894904914924934944954964974984995005015025035045055065075085095105115125135145155165175185195205215225235245255265275285295305315325335345355365375385395405415425435445455465475485495505515525535545555565575585595605615625635645655665675685695705715725735745755765775785795805815825835845855865875885895905915925935945955965975985996006016026036046056066076086096106116126136146156166176186196206216226236246256266276286296306316326336346356366376386396406416426436446456466476486496506516526536546556566576586596606616626636646656666676686696706716726736746756766776786796806816826836846856866876886896906916926936946956966976986997007017027037047057067077087097107117127137147157167177187197207217227237247257267277287297307317327337347357367377387397407417427437447457467477487497507517527537547557567577587597607617627637647657667677687697707717727737747757767777787797807817827837847857867877887897907917927937947957967977987998008018028038048058068078088098108118128138148158168178188198208218228238248258268278288298308318328338348358368378388398408418428438448458468478488498508518528538548558568578588598608618628638648658668678688698708718728738748758768778788798808818828838848858868878888898908918928938948958968978988999009019029039049059069079089099109119129139149159169179189199209219229239249259269279289299309319329339349359369379389399409419429439449459469479489499509519529539549559569579589599609619629639649659669679689699709719729739749759769779789799809819829839849859869879889899909919929939949959969979989991000100110021003100410051006100710081009101010111012101310141015101610171018101910201021102210231024102510261027102810291030103110321033103410351036103710381039104010411042104310441045104610471048104910501051105210531054105510561057105810591060106110621063106410651066106710681069107010711072107310741075107610771078107910801081108210831084108510861087108810891090109110921093109410951096109710981099110011011102110311041105110611071108110911101111111211131114111511161117111811191120112111221123112411251126112711281129113011311132113311341135113611371138113911401141114211431144114511461147114811491150115111521153115411551156115711581159116011611162116311641165116611671168116911701171117211731174117511761177117811791180118111821183118411851186118711881189119011911192119311941195119611971198119912001201120212031204120512061207120812091210121112121213121412151216121712181219122012211222122312241225122612271228122912301231123212331234123512361237123812391240124112421243124412451246124712481249125012511252125312541255125612571258125912601261126212631264126512661267126812691270127112721273127412751276127712781279128012811282128312841285128612871288128912901291129212931294129512961297129812991300130113021303130413051306130713081309131013111312131313141315131613171318131913201321132213231324132513261327132813291330133113321333133413351336133713381339134013411342134313441345134613471348134913501351135213531354135513561357135813591360136113621363136413651366136713681369137013711372137313741375137613771378137913801381138213831384138513861387138813891390139113921393139413951396139713981399140014011402140314041405140614071408140914101411141214131414141514161417141814191420142114221423142414251426142714281429143014311432143314341435143614371438143914401441144214431444144514461447144814491450145114521453145414551456145714581459146014611462146314641465146614671468146914701471147214731474147514761477147814791480148114821483148414851486148714881489149014911492149314941495149614971498149915001501150215031504150515061507150815091510151115121513151415151516151715181519152015211522152315241525152615271528152915301531153215331534153515361537153815391540154115421543154415451546154715481549155015511552155315541555155615571558155915601561156215631564156515661567156815691570157115721573157415751576157715781579158015811582158315841585158615871588158915901591159215931594159515961597159815991600160116021603160416051606160716081609161016111612161316141615161616171618161916201621162216231624162516261627162816291630163116321633163416351636163716381639164016411642164316441645164616471648164916501651165216531654165516561657165816591660166116621663166416651666166716681669167016711672167316741675167616771678167916801681168216831684168516861687168816891690169116921693169416951696169716981699170017011702170317041705170617071708170917101711171217131714171517161717171817191720172117221723172417251726172717281729173017311732173317341735173617371738173917401741174217431744174517461747174817491750175117521753175417551756175717581759176017611762176317641765176617671768176917701771177217731774177517761777177817791780178117821783178417851786178717881789179017911792179317941795179617971798179918001801180218031804180518061807180818091810181118121813181418151816181718181819182018211822182318241825182618271828182918301831183218331834183518361837183818391840184118421843184418451846184718481849185018511852185318541855185618571858185918601861186218631864186518661867186818691870187118721873187418751876187718781879188018811882188318841885188618871888188918901891189218931894189518961897189818991900190119021903190419051906190719081909191019111912191319141915191619171918191919201921192219231924192519261927192819291930193119321933193419351936193719381939194019411942194319441945194619471948194919501951195219531954195519561957195819591960196119621963196419651966196719681969197019711972197319741975197619771978197919801981198219831984198519861987198819891990199119921993199419951996199719981999200020012002200320042005200620072008200920102011201220132014201520162017201820192020202120222023202420252026202720282029203020312032203320342035203620372038203920402041204220432044204520462047204820492050205120522053205420552056205720582059206020612062206320642065206620672068206920702071207220732074207520762077207820792080208120822083208420852086208720882089209020912092209320942095209620972098209921002101210221032104210521062107210821092110211121122113211421152116211721182119212021212122212321242125212621272128212921302131213221332134213521362137213821392140214121422143214421452146214721482149215021512152215321542155215621572158215921602161216221632164216521662167216821692170217121722173217421752176217721782179218021812182218321842185218621872188218921902191219221932194219521962197219821992200220122022203220422052206220722082209221022112212221322142215221622172218221922202221222222232224222522262227222822292230223122322233223422352236223722382239224022412242224322442245224622472248224922502251225222532254225522562257225822592260226122622263226422652266226722682269227022712272227322742275227622772278227922802281228222832284228522862287228822892290229122922293229422952296229722982299230023012302230323042305230623072308230923102311231223132314231523162317231823192320232123222323232423252326232723282329233023312332233323342335233623372338233923402341234223432344234523462347234823492350235123522353235423552356235723582359236023612362236323642365236623672368236923702371237223732374237523762377237823792380238123822383238423852386238723882389239023912392239323942395239623972398239924002401240224032404240524062407240824092410241124122413241424152416241724182419242024212422242324242425242624272428242924302431243224332434243524362437243824392440244124422443244424452446244724482449245024512452245324542455245624572458245924602461246224632464246524662467246824692470247124722473247424752476247724782479248024812482248324842485248624872488248924902491249224932494249524962497249824992500250125022503250425052506250725082509251025112512251325142515251625172518251925202521252225232524252525262527252825292530253125322533253425352536253725382539254025412542254325442545254625472548254925502551255225532554255525562557255825592560256125622563256425652566256725682569257025712572257325742575257625772578257925802581258225832584258525862587258825892590259125922593259425952596259725982599260026012602260326042605260626072608260926102611261226132614261526162617261826192620262126222623262426252626262726282629263026312632263326342635263626372638263926402641264226432644264526462647264826492650265126522653265426552656265726582659266026612662266326642665266626672668266926702671267226732674267526762677267826792680268126822683268426852686268726882689269026912692269326942695269626972698269927002701270227032704270527062707270827092710271127122713271427152716271727182719272027212722272327242725272627272728272927302731273227332734273527362737273827392740274127422743274427452746274727482749275027512752275327542755 |
- /*
- This file is part of GNUnet.
- Copyright (C) 2011-2014 Christian Grothoff (and other contributing authors)
- GNUnet is free software; you can redistribute it and/or modify
- it under the terms of the GNU General Public License as published
- by the Free Software Foundation; either version 3, or (at your
- option) any later version.
- GNUnet is distributed in the hope that it will be useful, but
- WITHOUT ANY WARRANTY; without even the implied warranty of
- MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
- General Public License for more details.
- You should have received a copy of the GNU General Public License
- along with GNUnet; see the file COPYING. If not, write to the
- Free Software Foundation, Inc., 59 Temple Place - Suite 330,
- Boston, MA 02111-1307, USA.
- */
- /**
- * @file ats/plugin_ats_mlp.c
- * @brief ats mlp problem solver
- * @author Matthias Wachs
- * @author Christian Grothoff
- */
- #include "platform.h"
- #include "gnunet_util_lib.h"
- #include "gnunet_ats_service.h"
- #include "gnunet_ats_plugin.h"
- #include "gnunet-service-ats_addresses.h"
- #include "gnunet_statistics_service.h"
- #include <float.h>
- #include <glpk.h>
- #define BIG_M_VALUE (UINT32_MAX) /10
- #define BIG_M_STRING "unlimited"
- #define MLP_AVERAGING_QUEUE_LENGTH 3
- #define MLP_MAX_EXEC_DURATION GNUNET_TIME_relative_multiply(GNUNET_TIME_UNIT_SECONDS, 10)
- #define MLP_MAX_ITERATIONS 4096
- #define MLP_DEFAULT_D 1.0
- #define MLP_DEFAULT_R 1.0
- #define MLP_DEFAULT_U 1.0
- #define MLP_DEFAULT_QUALITY 1.0
- #define MLP_DEFAULT_MIN_CONNECTIONS 4
- #define MLP_DEFAULT_PEER_PREFERENCE 1.0
- #define MLP_NaN -1
- #define MLP_UNDEFINED 0
- #define GLP_YES 1.0
- #define GLP_NO 0.0
- enum MLP_Output_Format
- {
- MLP_MPS,
- MLP_CPLEX,
- MLP_GLPK
- };
- enum QualityMetrics
- {
- RQ_QUALITY_METRIC_DELAY = 0,
- RQ_QUALITY_METRIC_DISTANCE = 1,
- RQ_QUALITY_METRIC_COUNT = 2
- };
- static const char *
- print_quality_type (enum QualityMetrics qm)
- {
- switch (qm){
- case RQ_QUALITY_METRIC_DELAY:
- return "delay";
- case RQ_QUALITY_METRIC_DISTANCE:
- return "distance";
- default:
- GNUNET_break (0);
- return NULL;
- }
- }
- struct MLP_Solution
- {
- int lp_res;
- int lp_presolv;
- int mip_res;
- int mip_presolv;
- double lp_objective_value;
- double mlp_objective_value;
- double mlp_gap;
- double lp_mlp_gap;
- int p_elements;
- int p_cols;
- int p_rows;
- int n_peers;
- int n_addresses;
- };
- struct ATS_Peer
- {
- struct GNUNET_PeerIdentity id;
- /* Was this peer already added to the current problem? */
- int processed;
- /* constraint 2: 1 address per peer*/
- unsigned int r_c2;
- /* constraint 9: relativity */
- unsigned int r_c9;
- /* Legacy preference value */
- double f;
- };
- struct MLP_Problem
- {
- /**
- * GLPK (MLP) problem object
- */
- glp_prob *prob;
- /* Number of addresses in problem */
- unsigned int num_addresses;
- /* Number of peers in problem */
- unsigned int num_peers;
- /* Number of elements in problem matrix */
- unsigned int num_elements;
- /* Row index constraint 2: */
- unsigned int r_c2;
- /* Row index constraint 4: minimum connections */
- unsigned int r_c4;
- /* Row index constraint 6: maximize diversity */
- unsigned int r_c6;
- /* Row index constraint 8: utilization*/
- unsigned int r_c8;
- /* Row index constraint 9: relativity*/
- unsigned int r_c9;
- /* Row indices quality metrics */
- int r_q[RQ_QUALITY_METRIC_COUNT];
- /* Row indices ATS network quotas */
- int r_quota[GNUNET_ATS_NetworkTypeCount];
- /* Column index Diversity (D) column */
- int c_d;
- /* Column index Utilization (U) column */
- int c_u;
- /* Column index Proportionality (R) column */
- int c_r;
- /* Column index quality metrics */
- int c_q[RQ_QUALITY_METRIC_COUNT];
- /* Problem matrix */
- /* Current index */
- unsigned int ci;
- /* Row index array */
- int *ia;
- /* Column index array */
- int *ja;
- /* Column index value */
- double *ar;
- };
- struct MLP_Variables
- {
- /* Big M value for bandwidth capping */
- double BIG_M;
- /* MIP Gap */
- double mip_gap;
- /* LP MIP Gap */
- double lp_mip_gap;
- /* Number of quality metrics @deprecated, use RQ_QUALITY_METRIC_COUNT */
- int m_q;
- /* Number of quality metrics */
- int m_rc;
- /* Quality metric coefficients*/
- double co_Q[RQ_QUALITY_METRIC_COUNT];
- /* Ressource costs coefficients*/
- double co_RC[RQ_QUALITY_METRIC_COUNT];
- /* Diversity coefficient */
- double co_D;
- /* Utility coefficient */
- double co_U;
- /* Relativity coefficient */
- double co_R;
- /* Minimum bandwidth assigned to an address */
- unsigned int b_min;
- /* Minimum number of addresses with bandwidth assigned */
- unsigned int n_min;
- /* Quotas */
- /* Array mapping array index to ATS network */
- int quota_index[GNUNET_ATS_NetworkTypeCount];
- /* Outbound quotas */
- unsigned long long quota_out[GNUNET_ATS_NetworkTypeCount];
- /* Inbound quotas */
- unsigned long long quota_in[GNUNET_ATS_NetworkTypeCount];
- /* ATS ressource costs
- * array with GNUNET_ATS_QualityPropertiesCount elements
- * contains mapping to GNUNET_ATS_Property
- * */
- int rc[RQ_QUALITY_METRIC_COUNT];
- };
- /**
- * MLP Handle
- */
- struct GAS_MLP_Handle
- {
- struct GNUNET_ATS_PluginEnvironment *env;
- /**
- * Exclude peer from next result propagation
- */
- const struct GNUNET_PeerIdentity *exclude_peer;
- /**
- * Encapsulation for the MLP problem
- */
- struct MLP_Problem p;
- /**
- * Encapsulation for the MLP problem variables
- */
- struct MLP_Variables pv;
- /**
- * Encapsulation for the MLP solution
- */
- struct MLP_Solution ps;
- /**
- * Bulk lock
- */
- int stat_bulk_lock;
- /**
- * Number of changes while solver was locked
- */
- int stat_bulk_requests;
- /**
- * GLPK LP control parameter
- */
- glp_smcp control_param_lp;
- /**
- * GLPK LP control parameter
- */
- glp_iocp control_param_mlp;
- /**
- * Peers with pending address requests
- */
- struct GNUNET_CONTAINER_MultiPeerMap *requested_peers;
- /**
- * Was the problem updated since last solution
- */
- int stat_mlp_prob_updated;
- /**
- * Has the problem size changed since last solution
- */
- int stat_mlp_prob_changed;
- /**
- * Solve the problem automatically when updates occur?
- * Default: GNUNET_YES
- * Can be disabled for test and measurements
- */
- int opt_mlp_auto_solve;
- /**
- * Write all MILP problems to a MPS file
- */
- int opt_dump_problem_all;
- /**
- * Write all MILP problem solutions to a file
- */
- int opt_dump_solution_all;
- /**
- * Write MILP problems to a MPS file when solver fails
- */
- int opt_dump_problem_on_fail;
- /**
- * Write MILP problem solutions to a file when solver fails
- */
- int opt_dump_solution_on_fail;
- /**
- * solve feasibility only
- */
- int opt_dbg_feasibility_only;
- /**
- * solve autoscale the problem
- */
- int opt_dbg_autoscale_problem;
- /**
- * use the intopt presolver instead of simplex
- */
- int opt_dbg_intopt_presolver;
- /**
- * Print GLPK output
- */
- int opt_dbg_glpk_verbose;
- /**
- * solve autoscale the problem
- */
- int opt_dbg_optimize_relativity;
- /**
- * solve autoscale the problem
- */
- int opt_dbg_optimize_diversity;
- /**
- * solve autoscale the problem
- */
- int opt_dbg_optimize_quality;
- /**
- * solve autoscale the problem
- */
- int opt_dbg_optimize_utility;
- /**
- * Output format
- */
- enum MLP_Output_Format opt_log_format;
- };
- /**
- * Address specific MLP information
- */
- struct MLP_information
- {
- /**
- * Bandwidth assigned outbound
- */
- uint32_t b_out;
- /**
- * Bandwidth assigned inbound
- */
- uint32_t b_in;
- /**
- * Address selected
- */
- int n;
- /**
- * bandwidth column index
- */
- signed int c_b;
- /**
- * address usage column
- */
- signed int c_n;
- /* row indexes */
- /**
- * constraint 1: bandwidth capping
- */
- unsigned int r_c1;
- /**
- * constraint 3: minimum bandwidth
- */
- unsigned int r_c3;
- };
- /**
- *
- * NOTE: Do not modify this documentation. This documentation is based on
- * gnunet.org:/vcs/fsnsg/ats-paper.git/tech-doku/ats-tech-guide.tex
- * use build_txt.sh to generate plaintext output
- *
- * The MLP solver (mlp) tries to finds an optimal bandwidth assignmentby
- * optimizing an mixed integer programming problem. The MLP solver uses a
- * number of constraints to find the best adddress for a peer and an optimal
- * bandwidth assignment. mlp uses the GNU Linear Programming Kit to solve the
- * MLP problem.
- *
- * We defined a constraint system to find an optimal bandwidth assignment.
- * This constraint system uses as an input data addresses, bandwidth quotas,
- * preferences and quality values. This constraint system is stored in an
- * matrix based equotation system.
- *
- * 5 Using GLPK
- *
- * A (M)LP problem consists of a target function to optimizes, constraints
- * and rows and columns. FIXME GLP uses three arrays to index the matrix: two
- * integer arrays storing the row and column indices in the matrix and an
- * float array to store the coeeficient.
- *
- * To solve the problem we first find an initial solution for the LP problem
- * using the LP solver and then find an MLP solution based on this solution
- * using the MLP solver.
- *
- * Solving (M)LP problems has the property that finding an initial solution
- * for the LP problem is computationally expensive and finding the MLP
- * solution is cheaper. This is especially interesting an existing LP
- * solution can be reused if only coefficients in the matrix have changed
- * (addresses updated). Only when the problem size changes (addresses added
- * or deleted) a new LP solution has to be found.
- *
- * Intended usage
- * The mlp solver solves the bandwidth assignment problem only on demand when
- * an address suggestion is requested. When an address is requested mlp the
- * solves the mlp problem and if the active address or the bandwidth assigned
- * changes it calls the callback to addresses. The mlp solver gets notified
- * about new addresses (adding sessions), removed addresses (address
- * deletions) and address updates. To benefit from the mlp properties
- * mentioned in section 5 the solver rembers if since the last solution
- * addresses were added or deleted (problem size changed, problem has to be
- * rebuild and solved from sratch) or if addresses were updated and the
- * existing solution can be reused.
- *
- * 5.1 Input data
- *
- * The quotas for each network segment are passed by addresses. MLP can be
- * adapted using configuration settings and uses the following parameters:
- * * MLP_MAX_DURATION:
- * Maximum duration for a MLP solution procees (default: 3 sec.)
- * * MLP_MAX_ITERATIONS:
- * Maximum number of iterations for a MLP solution process (default:
- * 1024)
- * * MLP_MIN_CONNECTIONS:
- * Minimum number of desired connections (default: 4)
- * * MLP_MIN_BANDWIDTH:
- * Minimum amount of bandwidth assigned to an address (default: 1024)
- * * MLP_COEFFICIENT_D:
- * Diversity coefficient (default: 1.0)
- * * MLP_COEFFICIENT_R:
- * Relativity coefficient (default: 1.0)
- * * MLP_COEFFICIENT_U:
- * Utilization coefficient (default: 1.0)
- * * MLP_COEFFICIENT_D:
- * Diversity coefficient (default: 1.0)
- * * MLP_COEFFICIENT_QUALITY_DELAY:
- * Quality delay coefficient (default: 1.0)
- * * MLP_COEFFICIENT_QUALITY_DISTANCE:
- * Quality distance coefficient (default: 1.0)
- * * MLP_COEFFICIENT_QUALITY_DISTANCE:
- * Quality distance coefficient (default: 1.0)
- * * MLP_COEFFICIENT_QUALITY_DISTANCE:
- * Quality distance coefficient (default: 1.0)
- * * MLP_COEFFICIENT_QUALITY_DISTANCE:
- * Quality distance coefficient (default: 1.0)
- *
- * 5.2 Data structures used
- *
- * mlp has for each known peer a struct ATS_Peer containing information about
- * a specific peer. The address field solver_information contains information
- * about the mlp properties of this address.
- *
- * 5.3 Initializing
- *
- * During initialization mlp initializes the GLPK libray used to solve the
- * MLP problem: it initializes the glpk environment and creates an initial LP
- * problem. Next it loads the configuration values from the configuration or
- * uses the default values configured in -addresses_mlp.h. The quotas used
- * are given by addresses but may have to be adjusted. mlp uses a upper limit
- * for the bandwidth assigned called BIG M and a minimum amount of bandwidth
- * an address gets assigned as well as a minium desired number of
- * connections. If the configured quota is bigger than BIG M, it is reduced
- * to BIG M. If the configured quota is smaller than MLP_MIN_CONNECTIONS
- * *MLP_MIN_BANDWIDTH it is increased to this value.
- *
- * 5.4 Shutdown
- */
- #define LOG(kind,...) GNUNET_log_from (kind, "ats-mlp",__VA_ARGS__)
- /**
- * Print debug output for mlp problem creation
- */
- #define DEBUG_MLP_PROBLEM_CREATION GNUNET_NO
- /**
- * Intercept GLPK terminal output
- * @param info the mlp handle
- * @param s the string to print
- * @return 0: glpk prints output on terminal, 0 != surpress output
- */
- static int
- mlp_term_hook (void *info, const char *s)
- {
- struct GAS_MLP_Handle *mlp = info;
- if (mlp->opt_dbg_glpk_verbose)
- LOG (GNUNET_ERROR_TYPE_ERROR, "%s", s);
- return 1;
- }
- /**
- * Reset peers for next problem creation
- *
- * @param cls not used
- * @param key the key
- * @param value ATS_Peer
- * @return #GNUNET_OK
- */
- static int
- reset_peers (void *cls,
- const struct GNUNET_PeerIdentity *key,
- void *value)
- {
- struct ATS_Peer *peer = value;
- peer->processed = GNUNET_NO;
- return GNUNET_OK;
- }
- /**
- * Delete the MLP problem and free the constrain matrix
- *
- * @param mlp the MLP handle
- */
- static void
- mlp_delete_problem (struct GAS_MLP_Handle *mlp)
- {
- int c;
- if (mlp == NULL)
- return;
- if (mlp->p.prob != NULL)
- {
- glp_delete_prob(mlp->p.prob);
- mlp->p.prob = NULL;
- }
- /* delete row index */
- if (mlp->p.ia != NULL)
- {
- GNUNET_free (mlp->p.ia);
- mlp->p.ia = NULL;
- }
- /* delete column index */
- if (mlp->p.ja != NULL)
- {
- GNUNET_free (mlp->p.ja);
- mlp->p.ja = NULL;
- }
- /* delete coefficients */
- if (mlp->p.ar != NULL)
- {
- GNUNET_free (mlp->p.ar);
- mlp->p.ar = NULL;
- }
- mlp->p.ci = 0;
- mlp->p.prob = NULL;
- mlp->p.c_d = MLP_UNDEFINED;
- mlp->p.c_r = MLP_UNDEFINED;
- mlp->p.r_c2 = MLP_UNDEFINED;
- mlp->p.r_c4 = MLP_UNDEFINED;
- mlp->p.r_c6 = MLP_UNDEFINED;
- mlp->p.r_c9 = MLP_UNDEFINED;
- for (c = 0; c < RQ_QUALITY_METRIC_COUNT ; c ++)
- mlp->p.r_q[c] = MLP_UNDEFINED;
- for (c = 0; c < GNUNET_ATS_NetworkTypeCount; c ++)
- mlp->p.r_quota[c] = MLP_UNDEFINED;
- mlp->p.ci = MLP_UNDEFINED;
- GNUNET_CONTAINER_multipeermap_iterate (mlp->requested_peers,
- &reset_peers, NULL);
- }
- /**
- * Translate glpk status error codes to text
- * @param retcode return code
- * @return string with result
- */
- static const char *
- mlp_status_to_string (int retcode)
- {
- switch (retcode) {
- case GLP_UNDEF:
- return "solution is undefined";
- case GLP_FEAS:
- return "solution is feasible";
- case GLP_INFEAS:
- return "solution is infeasible";
- case GLP_NOFEAS:
- return "no feasible solution exists";
- case GLP_OPT:
- return "solution is optimal";
- case GLP_UNBND:
- return "solution is unbounded";
- default:
- GNUNET_break (0);
- return "unknown error";
- }
- }
- /**
- * Translate glpk solver error codes to text
- * @param retcode return code
- * @return string with result
- */
- static const char *
- mlp_solve_to_string (int retcode)
- {
- switch (retcode) {
- case 0:
- return "ok";
- case GLP_EBADB:
- return "invalid basis";
- case GLP_ESING:
- return "singular matrix";
- case GLP_ECOND:
- return "ill-conditioned matrix";
- case GLP_EBOUND:
- return "invalid bounds";
- case GLP_EFAIL:
- return "solver failed";
- case GLP_EOBJLL:
- return "objective lower limit reached";
- case GLP_EOBJUL:
- return "objective upper limit reached";
- case GLP_EITLIM:
- return "iteration limit exceeded";
- case GLP_ETMLIM:
- return "time limit exceeded";
- case GLP_ENOPFS:
- return "no primal feasible solution";
- case GLP_ENODFS:
- return "no dual feasible solution";
- case GLP_EROOT:
- return "root LP optimum not provided";
- case GLP_ESTOP:
- return "search terminated by application";
- case GLP_EMIPGAP:
- return "relative mip gap tolerance reached";
- case GLP_ENOFEAS:
- return "no dual feasible solution";
- case GLP_ENOCVG:
- return "no convergence";
- case GLP_EINSTAB:
- return "numerical instability";
- case GLP_EDATA:
- return "invalid data";
- case GLP_ERANGE:
- return "result out of range";
- default:
- GNUNET_break (0);
- return "unknown error";
- }
- }
- struct CountContext
- {
- const struct GNUNET_CONTAINER_MultiPeerMap *map;
- int result;
- };
- static int
- mlp_create_problem_count_addresses_it (void *cls,
- const struct GNUNET_PeerIdentity *key,
- void *value)
- {
- struct CountContext *cctx = cls;
- /* Check if we have to add this peer due to a pending request */
- if (GNUNET_YES == GNUNET_CONTAINER_multipeermap_contains (cctx->map, key))
- cctx->result++;
- return GNUNET_OK;
- }
- static int
- mlp_create_problem_count_addresses (const struct GNUNET_CONTAINER_MultiPeerMap *requested_peers,
- const struct GNUNET_CONTAINER_MultiPeerMap *addresses)
- {
- struct CountContext cctx;
- cctx.map = requested_peers;
- cctx.result = 0;
- GNUNET_CONTAINER_multipeermap_iterate (addresses,
- &mlp_create_problem_count_addresses_it, &cctx);
- return cctx.result;
- }
- static int
- mlp_create_problem_count_peers_it (void *cls,
- const struct GNUNET_PeerIdentity *key,
- void *value)
- {
- struct CountContext *cctx = cls;
- /* Check if we have to addresses for the requested peer */
- if (GNUNET_YES == GNUNET_CONTAINER_multipeermap_contains (cctx->map, key))
- cctx->result++;
- return GNUNET_OK;
- }
- static int
- mlp_create_problem_count_peers (const struct GNUNET_CONTAINER_MultiPeerMap *requested_peers,
- const struct GNUNET_CONTAINER_MultiPeerMap *addresses)
- {
- struct CountContext cctx;
- cctx.map = addresses;
- cctx.result = 0;
- GNUNET_CONTAINER_multipeermap_iterate (requested_peers,
- &mlp_create_problem_count_peers_it, &cctx);
- return cctx.result;
- }
- /**
- * Updates an existing value in the matrix
- *
- * Extract the row, updates the value and updates the row in the problem
- *
- * @param p the mlp problem
- * @param row the row to create the value in
- * @param col the column to create the value in
- * @param val the value to set
- * @param line calling line for debbuging
- * @return GNUNET_YES value changed, GNUNET_NO value did not change, GNUNET_SYSERR
- * on error
- */
- static int
- mlp_create_problem_update_value (struct MLP_Problem *p,
- int row, int col, double val,
- int line)
- {
- int c_cols;
- int c_elems;
- int c1;
- int res;
- int found;
- double *val_array;
- int *ind_array;
- GNUNET_assert (NULL != p);
- GNUNET_assert (NULL != p->prob);
- /* Get number of columns and prepare data structure */
- c_cols = glp_get_num_cols(p->prob);
- if (0 >= c_cols)
- return GNUNET_SYSERR;
- val_array = GNUNET_malloc ((c_cols +1)* sizeof (double));
- GNUNET_assert (NULL != val_array);
- ind_array = GNUNET_malloc ((c_cols+1) * sizeof (int));
- GNUNET_assert (NULL != ind_array);
- /* Extract the row */
- /* Update the value */
- c_elems = glp_get_mat_row (p->prob, row, ind_array, val_array);
- found = GNUNET_NO;
- for (c1 = 1; c1 < (c_elems+1); c1++)
- {
- if (ind_array[c1] == col)
- {
- found = GNUNET_YES;
- break;
- }
- }
- if (GNUNET_NO == found)
- {
- ind_array[c_elems+1] = col;
- val_array[c_elems+1] = val;
- LOG (GNUNET_ERROR_TYPE_DEBUG, "[P] Setting value in [%s : %s] to `%.2f'\n",
- glp_get_row_name (p->prob, row), glp_get_col_name (p->prob, col),
- val);
- glp_set_mat_row (p->prob, row, c_elems+1, ind_array, val_array);
- GNUNET_free (ind_array);
- GNUNET_free (val_array);
- return GNUNET_YES;
- }
- else
- {
- /* Update value */
- LOG (GNUNET_ERROR_TYPE_DEBUG, "[P] Updating value in [%s : %s] from `%.2f' to `%.2f'\n",
- glp_get_row_name (p->prob, row), glp_get_col_name (p->prob, col),
- val_array[c1], val);
- if (val != val_array[c1])
- res = GNUNET_YES;
- else
- res = GNUNET_NO;
- val_array[c1] = val;
- /* Update the row in the matrix */
- glp_set_mat_row (p->prob, row, c_elems, ind_array, val_array);
- }
- GNUNET_free (ind_array);
- GNUNET_free (val_array);
- return res;
- }
- /**
- * Creates a new value in the matrix
- *
- * Sets the row and column index in the problem array and increments the
- * position field
- *
- * @param p the mlp problem
- * @param row the row to create the value in
- * @param col the column to create the value in
- * @param val the value to set
- * @param line calling line for debbuging
- */
- static void
- mlp_create_problem_set_value (struct MLP_Problem *p,
- int row, int col, double val,
- int line)
- {
- if ((p->ci) >= p->num_elements)
- {
- LOG (GNUNET_ERROR_TYPE_DEBUG, "[P]: line %u: Request for index %u bigger than array size of %u\n",
- line, p->ci + 1, p->num_elements);
- GNUNET_break (0);
- return;
- }
- if ((0 == row) || (0 == col))
- {
- GNUNET_break (0);
- LOG (GNUNET_ERROR_TYPE_ERROR, "[P]: Invalid call from line %u: row = %u, col = %u\n",
- line, row, col);
- }
- p->ia[p->ci] = row ;
- p->ja[p->ci] = col;
- p->ar[p->ci] = val;
- #if DEBUG_MLP_PROBLEM_CREATION
- LOG (GNUNET_ERROR_TYPE_DEBUG, "[P]: line %u: Set value [%u,%u] in index %u == %.2f\n",
- line, p->ia[p->ci], p->ja[p->ci], p->ci, p->ar[p->ci]);
- #endif
- p->ci++;
- }
- 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 col = glp_add_cols (p->prob, 1);
- glp_set_col_name (p->prob, col, name);
- glp_set_col_bnds (p->prob, col, bound, lb, ub);
- glp_set_col_kind (p->prob, col, type);
- glp_set_obj_coef (p->prob, col, coef);
- #if DEBUG_MLP_PROBLEM_CREATION
- LOG (GNUNET_ERROR_TYPE_DEBUG, "[P]: Added column [%u] `%s': %.2f\n",
- col, name, coef);
- #endif
- return col;
- }
- static int
- mlp_create_problem_create_constraint (struct MLP_Problem *p, char *name,
- unsigned int bound, double lb, double ub)
- {
- char * op;
- int row = glp_add_rows (p->prob, 1);
- /* set row name */
- glp_set_row_name (p->prob, row, name);
- /* set row bounds: <= 0 */
- glp_set_row_bnds (p->prob, row, bound, lb, ub);
- switch (bound)
- {
- case GLP_UP:
- GNUNET_asprintf(&op, "-inf <= x <= %.2f", ub);
- break;
- case GLP_DB:
- GNUNET_asprintf(&op, "%.2f <= x <= %.2f", lb, ub);
- break;
- case GLP_FX:
- GNUNET_asprintf(&op, "%.2f == x == %.2f", lb, ub);
- break;
- case GLP_LO:
- GNUNET_asprintf(&op, "%.2f <= x <= inf", lb);
- break;
- default:
- GNUNET_asprintf(&op, "ERROR");
- break;
- }
- #if DEBUG_MLP_PROBLEM_CREATION
- LOG (GNUNET_ERROR_TYPE_DEBUG, "[P]: Added row [%u] `%s': %s\n",
- row, name, op);
- #endif
- GNUNET_free (op);
- return row;
- }
- /**
- * Create the
- * - address columns b and n
- * - address dependent constraint rows c1, c3
- * - peer dependent rows c2 and c9
- * - Set address dependent entries in problem matrix as well
- */
- static int
- mlp_create_problem_add_address_information (void *cls,
- const struct GNUNET_PeerIdentity *key,
- void *value)
- {
- struct GAS_MLP_Handle *mlp = cls;
- struct MLP_Problem *p = &mlp->p;
- struct ATS_Address *address = value;
- struct ATS_Peer *peer;
- struct MLP_information *mlpi;
- char *name;
- double cur_bigm;
- uint32_t addr_net;
- uint32_t addr_net_index;
- unsigned long long max_quota;
- int c;
- /* Check if we have to add this peer due to a pending request */
- if (GNUNET_NO == GNUNET_CONTAINER_multipeermap_contains(mlp->requested_peers, key))
- return GNUNET_OK;
- mlpi = address->solver_information;
- if (NULL == mlpi)
- {
- fprintf (stderr, "%s %p\n",GNUNET_i2s (&address->peer), address);
- GNUNET_break (0);
- return GNUNET_OK;
- }
- addr_net = address->properties.scope;
- for (addr_net_index = 0; addr_net_index < GNUNET_ATS_NetworkTypeCount; addr_net_index++)
- {
- if (mlp->pv.quota_index[addr_net_index] == addr_net)
- break;
- }
- if (addr_net_index >= GNUNET_ATS_NetworkTypeCount)
- {
- GNUNET_break (0);
- return GNUNET_OK;
- }
- max_quota = 0;
- for (c = 0; c < GNUNET_ATS_NetworkTypeCount; c++)
- {
- if (mlp->pv.quota_out[c] > max_quota)
- max_quota = mlp->pv.quota_out[c];
- if (mlp->pv.quota_in[c] > max_quota)
- max_quota = mlp->pv.quota_in[c];
- }
- if (max_quota > mlp->pv.BIG_M)
- cur_bigm = (double) mlp->pv.BIG_M;
- else
- cur_bigm = max_quota;
- /* Get peer */
- peer = GNUNET_CONTAINER_multipeermap_get (mlp->requested_peers, key);
- GNUNET_assert (NULL != peer);
- if (peer->processed == GNUNET_NO)
- {
- /* Add peer dependent constraints */
- /* Add c2) One address active per peer */
- GNUNET_asprintf(&name, "c2_%s", GNUNET_i2s(&address->peer));
- peer->r_c2 = mlp_create_problem_create_constraint (p, name, GLP_FX, 1.0, 1.0);
- GNUNET_free (name);
- if (GNUNET_NO == mlp->opt_dbg_feasibility_only)
- {
- if (GNUNET_YES == mlp->opt_dbg_optimize_relativity)
- {
- /* Add c9) Relativity */
- GNUNET_asprintf(&name, "c9_%s", GNUNET_i2s(&address->peer));
- peer->r_c9 = mlp_create_problem_create_constraint (p, name, GLP_LO, 0.0, 0.0);
- GNUNET_free (name);
- /* c9) set coefficient */
- mlp_create_problem_set_value (p, peer->r_c9, p->c_r, -peer->f , __LINE__);
- }
- }
- peer->processed = GNUNET_YES;
- }
- /* Reset addresses' solver information */
- mlpi->c_b = 0;
- mlpi->c_n = 0;
- mlpi->n = 0;
- mlpi->r_c1 = 0;
- mlpi->r_c3 = 0;
- /* Add bandwidth column */
- GNUNET_asprintf (&name, "b_%s_%s_%p", GNUNET_i2s (&address->peer), address->plugin, address);
- if (GNUNET_NO == mlp->opt_dbg_feasibility_only)
- {
- mlpi->c_b = mlp_create_problem_create_column (p, name, GLP_CV, GLP_LO, 0.0, 0.0, 0.0);
- }
- else
- {
- /* Maximize for bandwidth assignment in feasibility testing */
- mlpi->c_b = mlp_create_problem_create_column (p, name, GLP_CV, GLP_LO, 0.0, 0.0, 1.0);
- }
- GNUNET_free (name);
- /* Add address active column */
- GNUNET_asprintf (&name, "n_%s_%s_%p", GNUNET_i2s (&address->peer), address->plugin, address);
- mlpi->c_n = mlp_create_problem_create_column (p, name, GLP_IV, GLP_DB, 0.0, 1.0, 0.0);
- GNUNET_free (name);
- /* Add address dependent constraints */
- /* Add c1) bandwidth capping: b_t + (-M) * n_t <= 0 */
- GNUNET_asprintf(&name, "c1_%s_%s_%p", GNUNET_i2s(&address->peer), address->plugin, address);
- mlpi->r_c1 = mlp_create_problem_create_constraint (p, name, GLP_UP, 0.0, 0.0);
- GNUNET_free (name);
- /* c1) set b = 1 coefficient */
- mlp_create_problem_set_value (p, mlpi->r_c1, mlpi->c_b, 1, __LINE__);
- /* c1) set n = - min (M, quota) coefficient */
- cur_bigm = (double) mlp->pv.quota_out[addr_net_index];
- if (cur_bigm > mlp->pv.BIG_M)
- cur_bigm = (double) mlp->pv.BIG_M;
- mlp_create_problem_set_value (p, mlpi->r_c1, mlpi->c_n, -cur_bigm, __LINE__);
- /* Add constraint c 3) minimum bandwidth
- * b_t + (-n_t * b_min) >= 0
- * */
- GNUNET_asprintf(&name, "c3_%s_%s_%p", GNUNET_i2s(&address->peer), address->plugin, address);
- mlpi->r_c3 = mlp_create_problem_create_constraint (p, name, GLP_LO, 0.0, 0.0);
- GNUNET_free (name);
- /* c3) set b = 1 coefficient */
- mlp_create_problem_set_value (p, mlpi->r_c3, mlpi->c_b, 1, __LINE__);
- /* c3) set n = -b_min coefficient */
- mlp_create_problem_set_value (p, mlpi->r_c3, mlpi->c_n, - ((double )mlp->pv.b_min), __LINE__);
- /* Set coefficient entries in invariant rows */
- /* Feasbility */
- /* c 4) minimum connections */
- mlp_create_problem_set_value (p, p->r_c4, mlpi->c_n, 1, __LINE__);
- /* c 2) 1 address peer peer */
- mlp_create_problem_set_value (p, peer->r_c2, mlpi->c_n, 1, __LINE__);
- /* c 10) obey network specific quotas
- * (1)*b_1 + ... + (1)*b_m <= quota_n
- */
- mlp_create_problem_set_value (p, p->r_quota[addr_net_index], mlpi->c_b, 1, __LINE__);
- /* Optimality */
- if (GNUNET_NO == mlp->opt_dbg_feasibility_only)
- {
- /* c 6) maximize diversity */
- mlp_create_problem_set_value (p, p->r_c6, mlpi->c_n, 1, __LINE__);
- /* c 9) relativity */
- if (GNUNET_YES == mlp->opt_dbg_optimize_relativity)
- mlp_create_problem_set_value (p, peer->r_c9, mlpi->c_b, 1, __LINE__);
- /* c 8) utility */
- if (GNUNET_YES == mlp->opt_dbg_optimize_utility)
- mlp_create_problem_set_value (p, p->r_c8, mlpi->c_b, 1, __LINE__);
- /* c 7) Optimize quality */
- /* For all quality metrics, set quality of this address */
- if (GNUNET_YES == mlp->opt_dbg_optimize_quality)
- {
- mlp_create_problem_set_value (p,
- p->r_q[RQ_QUALITY_METRIC_DELAY],
- mlpi->c_b,
- address->norm_delay.norm,
- __LINE__);
- mlp_create_problem_set_value (p,
- p->r_q[RQ_QUALITY_METRIC_DISTANCE],
- mlpi->c_b,
- address->norm_distance.norm,
- __LINE__);
- }
- }
- return GNUNET_OK;
- }
- /**
- * Create the invariant columns c4, c6, c10, c8, c7
- */
- static void
- mlp_create_problem_add_invariant_rows (struct GAS_MLP_Handle *mlp, struct MLP_Problem *p)
- {
- int c;
- /* Feasibility */
- /* Row for c4) minimum connection */
- /* Number of minimum connections is min(|Peers|, n_min) */
- 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);
- /* Rows for c 10) Enforce network quotas */
- for (c = 0; c < GNUNET_ATS_NetworkTypeCount; c++)
- {
- char * text;
- GNUNET_asprintf(&text, "c10_quota_ats_%s",
- GNUNET_ATS_print_network_type(mlp->pv.quota_index[c]));
- p->r_quota[c] = mlp_create_problem_create_constraint (p, text, GLP_DB, 0.0, mlp->pv.quota_out[c]);
- GNUNET_free (text);
- }
- /* Optimality */
- if (GNUNET_NO == mlp->opt_dbg_feasibility_only)
- {
- char *name;
- /* Add row for c6) Maximize for diversity */
- if (GNUNET_YES == mlp->opt_dbg_optimize_diversity)
- {
- p->r_c6 = mlp_create_problem_create_constraint (p, "c6", GLP_FX, 0.0, 0.0);
- /* Set c6 ) Setting -D */
- mlp_create_problem_set_value (p, p->r_c6, p->c_d, -1, __LINE__);
- }
- /* Adding rows for c 8) Maximize utility */
- if (GNUNET_YES == mlp->opt_dbg_optimize_utility)
- {
- p->r_c8 = mlp_create_problem_create_constraint (p, "c8", GLP_FX, 0.0, 0.0);
- /* -u */
- mlp_create_problem_set_value (p, p->r_c8, p->c_u, -1, __LINE__);
- }
- /* For all quality metrics:
- * c 7) Maximize quality, austerity */
- if (GNUNET_YES == mlp->opt_dbg_optimize_quality)
- {
- for (c = 0; c < mlp->pv.m_q; c++)
- {
- GNUNET_asprintf (&name,
- "c7_q%i_%s", c,
- print_quality_type (c));
- p->r_q[c] = mlp_create_problem_create_constraint (p, name, GLP_FX, 0.0, 0.0);
- GNUNET_free (name);
- mlp_create_problem_set_value (p,
- p->r_q[c],
- p->c_q[c], -1, __LINE__);
- }
- }
- }
- }
- /**
- * Create the invariant columns d, u, r, q0 ... qm
- */
- static void
- mlp_create_problem_add_invariant_columns (struct GAS_MLP_Handle *mlp, struct MLP_Problem *p)
- {
- if (GNUNET_NO == mlp->opt_dbg_feasibility_only)
- {
- char *name;
- int c;
- /* Diversity d column */
- if (GNUNET_YES == mlp->opt_dbg_optimize_diversity)
- p->c_d = mlp_create_problem_create_column (p, "d", GLP_CV, GLP_LO, 0.0, 0.0, mlp->pv.co_D);
- /* Utilization u column */
- if (GNUNET_YES == mlp->opt_dbg_optimize_utility)
- p->c_u = mlp_create_problem_create_column (p, "u", GLP_CV, GLP_LO, 0.0, 0.0, mlp->pv.co_U);
- /* Relativity r column */
- if (GNUNET_YES == mlp->opt_dbg_optimize_relativity)
- p->c_r = mlp_create_problem_create_column (p, "r", GLP_CV, GLP_LO, 0.0, 0.0, mlp->pv.co_R);
- /* Quality metric columns */
- if (GNUNET_YES == mlp->opt_dbg_optimize_quality)
- {
- for (c = 0; c < mlp->pv.m_q; c++)
- {
- GNUNET_asprintf (&name, "q_%u", c);
- p->c_q[c] = mlp_create_problem_create_column (p, name, GLP_CV, GLP_LO, 0.0, 0.0, mlp->pv.co_Q[c]);
- GNUNET_free (name);
- }
- }
- }
- }
- /**
- * Create the MLP problem
- *
- * @param mlp the MLP handle
- * @return #GNUNET_OK or #GNUNET_SYSERR
- */
- static int
- mlp_create_problem (struct GAS_MLP_Handle *mlp)
- {
- struct MLP_Problem *p = &mlp->p;
- int res = GNUNET_OK;
- GNUNET_assert (p->prob == NULL);
- GNUNET_assert (p->ia == NULL);
- GNUNET_assert (p->ja == NULL);
- GNUNET_assert (p->ar == NULL);
- /* Reset MLP problem struct */
- /* create the glpk problem */
- p->prob = glp_create_prob ();
- GNUNET_assert (NULL != p->prob);
- p->num_peers = mlp_create_problem_count_peers (mlp->requested_peers, mlp->env->addresses);
- p->num_addresses = mlp_create_problem_count_addresses (mlp->requested_peers,
- mlp->env->addresses);
- /* Create problem matrix: 10 * #addresses + #q * #addresses + #q, + #peer + 2 + 1 */
- p->num_elements = (10 * p->num_addresses + mlp->pv.m_q * p->num_addresses +
- mlp->pv.m_q + p->num_peers + 2 + 1);
- LOG (GNUNET_ERROR_TYPE_DEBUG,
- "Rebuilding problem for %u peer(s) and %u addresse(s) and %u quality metrics == %u elements\n",
- p->num_peers,
- p->num_addresses,
- mlp->pv.m_q,
- p->num_elements);
- /* Set a problem name */
- glp_set_prob_name (p->prob, "GNUnet ATS bandwidth distribution");
- /* Set optimization direction to maximize */
- glp_set_obj_dir (p->prob, GLP_MAX);
- /* Create problem matrix */
- /* last +1 caused by glpk index starting with one: [1..elements]*/
- p->ci = 1;
- /* row index */
- p->ia = GNUNET_malloc (p->num_elements * sizeof (int));
- /* column index */
- p->ja = GNUNET_malloc (p->num_elements * sizeof (int));
- /* coefficient */
- p->ar = GNUNET_malloc (p->num_elements * sizeof (double));
- if ((NULL == p->ia) || (NULL == p->ja) || (NULL == p->ar))
- {
- LOG (GNUNET_ERROR_TYPE_ERROR, _("Problem size too large, cannot allocate memory!\n"));
- return GNUNET_SYSERR;
- }
- /* Adding invariant columns */
- mlp_create_problem_add_invariant_columns (mlp, p);
- /* Adding address independent constraint rows */
- mlp_create_problem_add_invariant_rows (mlp, p);
- /* Adding address dependent columns constraint rows */
- GNUNET_CONTAINER_multipeermap_iterate (mlp->env->addresses,
- &mlp_create_problem_add_address_information,
- mlp);
- /* Load the matrix */
- LOG (GNUNET_ERROR_TYPE_DEBUG, "Loading matrix\n");
- glp_load_matrix(p->prob, (p->ci)-1, p->ia, p->ja, p->ar);
- if (GNUNET_YES == mlp->opt_dbg_autoscale_problem)
- {
- glp_scale_prob (p->prob, GLP_SF_AUTO);
- }
- return res;
- }
- /**
- * Solves the LP problem
- *
- * @param mlp the MLP Handle
- * @return #GNUNET_OK if could be solved, #GNUNET_SYSERR on failure
- */
- static int
- mlp_solve_lp_problem (struct GAS_MLP_Handle *mlp)
- {
- int res = 0;
- int res_status = 0;
- res = glp_simplex(mlp->p.prob, &mlp->control_param_lp);
- if (0 == res)
- LOG(GNUNET_ERROR_TYPE_DEBUG, "Solving LP problem: %s\n",
- mlp_solve_to_string (res));
- else
- LOG(GNUNET_ERROR_TYPE_DEBUG, "Solving LP problem failed: %s\n",
- mlp_solve_to_string (res));
- /* Analyze problem status */
- res_status = glp_get_status (mlp->p.prob);
- switch (res_status) {
- case GLP_OPT: /* solution is optimal */
- LOG (GNUNET_ERROR_TYPE_INFO,
- "Solving LP problem: %s, %s\n",
- mlp_solve_to_string(res),
- mlp_status_to_string(res_status));
- return GNUNET_OK;
- default:
- LOG (GNUNET_ERROR_TYPE_ERROR,
- "Solving LP problem failed: %s %s\n",
- mlp_solve_to_string(res),
- mlp_status_to_string(res_status));
- return GNUNET_SYSERR;
- }
- }
- /**
- * Propagates the results when MLP problem was solved
- *
- * @param cls the MLP handle
- * @param key the peer identity
- * @param value the address
- * @return #GNUNET_OK to continue
- */
- static int
- mlp_propagate_results (void *cls,
- const struct GNUNET_PeerIdentity *key,
- void *value)
- {
- struct GAS_MLP_Handle *mlp = cls;
- struct ATS_Address *address;
- struct MLP_information *mlpi;
- double mlp_bw_in = MLP_NaN;
- double mlp_bw_out = MLP_NaN;
- double mlp_use = MLP_NaN;
- /* Check if we have to add this peer due to a pending request */
- if (GNUNET_NO == GNUNET_CONTAINER_multipeermap_contains (mlp->requested_peers,
- key))
- {
- return GNUNET_OK;
- }
- address = value;
- GNUNET_assert (address->solver_information != NULL);
- mlpi = address->solver_information;
- mlp_bw_in = glp_mip_col_val(mlp->p.prob, mlpi->c_b);/* FIXME */
- if (mlp_bw_in > (double) UINT32_MAX)
- {
- LOG (GNUNET_ERROR_TYPE_DEBUG, "Overflow in assigned bandwidth, reducing ...\n" );
- mlp_bw_in = (double) UINT32_MAX;
- }
- mlp_bw_out = glp_mip_col_val(mlp->p.prob, mlpi->c_b);
- if (mlp_bw_out > (double) UINT32_MAX)
- {
- LOG (GNUNET_ERROR_TYPE_DEBUG, "Overflow in assigned bandwidth, reducing ...\n" );
- mlp_bw_out = (double) UINT32_MAX;
- }
- mlp_use = glp_mip_col_val(mlp->p.prob, mlpi->c_n);
- /*
- * Debug: solution
- * LOG (GNUNET_ERROR_TYPE_INFO, "MLP result address: `%s' `%s' length %u session %u, mlp use %.3f\n",
- * GNUNET_i2s(&address->peer), address->plugin,
- * address->addr_len, address->session_id);
- */
- if (GLP_YES == mlp_use)
- {
- /* This address was selected by the solver to be used */
- mlpi->n = GNUNET_YES;
- if (GNUNET_NO == address->active)
- {
- /* Address was not used before, enabling address */
- LOG (GNUNET_ERROR_TYPE_DEBUG, "%s %.2f : enabling address\n",
- (1 == mlp_use) ? "[x]": "[ ]", mlp_bw_out);
- address->active = GNUNET_YES;
- address->assigned_bw_in = mlp_bw_in;
- mlpi->b_in = mlp_bw_in;
- address->assigned_bw_out = mlp_bw_out;
- mlpi->b_out = mlp_bw_out;
- if ((NULL == mlp->exclude_peer) || (0 != memcmp (&address->peer, mlp->exclude_peer, sizeof (address->peer))))
- mlp->env->bandwidth_changed_cb (mlp->env->cls, address);
- return GNUNET_OK;
- }
- else if (GNUNET_YES == address->active)
- {
- /* Address was used before, check for bandwidth change */
- if ((mlp_bw_out != address->assigned_bw_out) ||
- (mlp_bw_in != address->assigned_bw_in))
- {
- LOG (GNUNET_ERROR_TYPE_DEBUG, "%s %.2f : bandwidth changed\n",
- (1 == mlp_use) ? "[x]": "[ ]", mlp_bw_out);
- address->assigned_bw_in = mlp_bw_in;
- mlpi->b_in = mlp_bw_in;
- address->assigned_bw_out = mlp_bw_out;
- mlpi->b_out = mlp_bw_out;
- if ((NULL == mlp->exclude_peer) || (0 != memcmp (&address->peer, mlp->exclude_peer, sizeof (address->peer))))
- mlp->env->bandwidth_changed_cb (mlp->env->cls, address);
- return GNUNET_OK;
- }
- }
- else
- GNUNET_break (0);
- }
- else if (GLP_NO == mlp_use)
- {
- /* This address was selected by the solver to be not used */
- mlpi->n = GNUNET_NO;
- if (GNUNET_NO == address->active)
- {
- /* Address was not used before, nothing to do */
- LOG (GNUNET_ERROR_TYPE_DEBUG, "%s %.2f : no change\n",
- (1 == mlp_use) ? "[x]": "[ ]", mlp_bw_out);
- return GNUNET_OK;
- }
- else if (GNUNET_YES == address->active)
- {
- /* Address was used before, disabling address */
- LOG (GNUNET_ERROR_TYPE_DEBUG, "%s %.2f : disabling address\n",
- (1 == mlp_use) ? "[x]": "[ ]", mlp_bw_out);
- address->active = GNUNET_NO;
- /* Set bandwidth to 0 */
- address->assigned_bw_in = 0;
- mlpi->b_in = 0;
- address->assigned_bw_out = 0;
- mlpi->b_out = 0;
- return GNUNET_OK;
- }
- else
- GNUNET_break (0);
- }
- else
- GNUNET_break (0);
- return GNUNET_OK;
- }
- static void
- notify (struct GAS_MLP_Handle *mlp,
- enum GAS_Solver_Operation op,
- enum GAS_Solver_Status stat,
- enum GAS_Solver_Additional_Information add)
- {
- mlp->env->info_cb (mlp->env->cls,
- op,
- stat,
- add);
- }
- static void
- mlp_branch_and_cut_cb (glp_tree *tree, void *info)
- {
- struct GAS_MLP_Handle *mlp = info;
- double mlp_obj = 0;
- switch (glp_ios_reason (tree))
- {
- case GLP_ISELECT:
- /* Do nothing here */
- break;
- case GLP_IPREPRO:
- /* Do nothing here */
- break;
- case GLP_IROWGEN:
- /* Do nothing here */
- break;
- case GLP_IHEUR:
- /* Do nothing here */
- break;
- case GLP_ICUTGEN:
- /* Do nothing here */
- break;
- case GLP_IBRANCH:
- /* Do nothing here */
- break;
- case GLP_IBINGO:
- /* A better solution was found */
- mlp->ps.mlp_gap = glp_ios_mip_gap (tree);
- mlp_obj = glp_mip_obj_val (mlp->p.prob);
- mlp->ps.lp_mlp_gap = (abs(mlp_obj - mlp->ps.lp_objective_value)) / (abs(mlp_obj) + DBL_EPSILON);
- LOG (GNUNET_ERROR_TYPE_INFO,
- "Found better integer solution, current gaps: %.3f <= %.3f, %.3f <= %.3f\n",
- mlp->ps.mlp_gap, mlp->pv.mip_gap,
- mlp->ps.lp_mlp_gap, mlp->pv.lp_mip_gap);
- if (mlp->ps.mlp_gap <= mlp->pv.mip_gap)
- {
- LOG (GNUNET_ERROR_TYPE_INFO,
- "Current LP/MLP gap of %.3f smaller than tolerated gap of %.3f, terminating search\n",
- mlp->ps.lp_mlp_gap, mlp->pv.lp_mip_gap);
- glp_ios_terminate (tree);
- }
- if (mlp->ps.lp_mlp_gap <= mlp->pv.lp_mip_gap)
- {
- LOG (GNUNET_ERROR_TYPE_INFO,
- "Current LP/MLP gap of %.3f smaller than tolerated gap of %.3f, terminating search\n",
- mlp->ps.lp_mlp_gap, mlp->pv.lp_mip_gap);
- glp_ios_terminate (tree);
- }
- break;
- default:
- break;
- }
- //GNUNET_break (0);
- }
- /**
- * Solves the MLP problem
- *
- * @param solver the MLP Handle
- * @return #GNUNET_OK if could be solved, #GNUNET_SYSERR on failure
- */
- static int
- GAS_mlp_solve_problem (void *solver)
- {
- struct GAS_MLP_Handle *mlp = solver;
- char *filename;
- int res_lp = 0;
- int mip_res = 0;
- int mip_status = 0;
- struct GNUNET_TIME_Absolute start_total;
- struct GNUNET_TIME_Absolute start_cur_op;
- struct GNUNET_TIME_Relative dur_total;
- struct GNUNET_TIME_Relative dur_setup;
- struct GNUNET_TIME_Relative dur_lp;
- struct GNUNET_TIME_Relative dur_mlp;
- GNUNET_assert(NULL != solver);
- if (GNUNET_YES == mlp->stat_bulk_lock)
- {
- mlp->stat_bulk_requests++;
- return GNUNET_NO;
- }
- notify(mlp, GAS_OP_SOLVE_START, GAS_STAT_SUCCESS,
- (GNUNET_YES == mlp->stat_mlp_prob_changed) ? GAS_INFO_FULL : GAS_INFO_UPDATED);
- start_total = GNUNET_TIME_absolute_get();
- if (0 == GNUNET_CONTAINER_multipeermap_size(mlp->requested_peers))
- {
- notify(mlp, GAS_OP_SOLVE_STOP, GAS_STAT_SUCCESS, GAS_INFO_NONE);
- return GNUNET_OK; /* No pending requests */
- }
- if (0 == GNUNET_CONTAINER_multipeermap_size(mlp->env->addresses))
- {
- notify(mlp, GAS_OP_SOLVE_STOP, GAS_STAT_SUCCESS, GAS_INFO_NONE);
- return GNUNET_OK; /* No addresses available */
- }
- if ((GNUNET_NO == mlp->stat_mlp_prob_changed)
- && (GNUNET_NO == mlp->stat_mlp_prob_updated))
- {
- LOG(GNUNET_ERROR_TYPE_DEBUG, "No changes to problem\n");
- notify(mlp, GAS_OP_SOLVE_STOP, GAS_STAT_SUCCESS, GAS_INFO_NONE);
- return GNUNET_OK;
- }
- if (GNUNET_YES == mlp->stat_mlp_prob_changed)
- {
- LOG(GNUNET_ERROR_TYPE_DEBUG, "Problem size changed, rebuilding\n");
- notify(mlp, GAS_OP_SOLVE_SETUP_START, GAS_STAT_SUCCESS, GAS_INFO_FULL);
- mlp_delete_problem(mlp);
- if (GNUNET_SYSERR == mlp_create_problem(mlp))
- {
- notify(mlp, GAS_OP_SOLVE_SETUP_STOP, GAS_STAT_FAIL, GAS_INFO_FULL);
- return GNUNET_SYSERR;
- }
- notify(mlp, GAS_OP_SOLVE_SETUP_STOP, GAS_STAT_SUCCESS, GAS_INFO_FULL);
- if (GNUNET_NO == mlp->opt_dbg_intopt_presolver)
- {
- mlp->control_param_lp.presolve = GLP_YES; /* LP presolver, we need lp solution */
- mlp->control_param_mlp.presolve = GNUNET_NO; /* No presolver, we have LP solution */
- }
- else
- {
- mlp->control_param_lp.presolve = GNUNET_NO; /* LP presolver, we need lp solution */
- mlp->control_param_mlp.presolve = GLP_YES; /* No presolver, we have LP solution */
- dur_lp = GNUNET_TIME_UNIT_ZERO;
- }
- }
- else
- {
- LOG(GNUNET_ERROR_TYPE_DEBUG, "Problem was updated, resolving\n");
- }
- /* Reset solution info */
- mlp->ps.lp_objective_value = 0.0;
- mlp->ps.mlp_gap = 1.0;
- mlp->ps.mlp_objective_value = 0.0;
- mlp->ps.lp_mlp_gap = 0.0;
- dur_setup = GNUNET_TIME_absolute_get_duration (start_total);
- /* Run LP solver */
- if (GNUNET_NO == mlp->opt_dbg_intopt_presolver)
- {
- notify(mlp, GAS_OP_SOLVE_MLP_LP_START, GAS_STAT_SUCCESS,
- (GNUNET_YES == mlp->stat_mlp_prob_changed) ? GAS_INFO_FULL : GAS_INFO_UPDATED);
- LOG(GNUNET_ERROR_TYPE_DEBUG,
- "Running LP solver %s\n",
- (GLP_YES == mlp->control_param_lp.presolve)? "with presolver": "without presolver");
- start_cur_op = GNUNET_TIME_absolute_get();
- /* Solve LP */
- /* Only for debugging:
- * Always use LP presolver:
- * mlp->control_param_lp.presolve = GLP_YES; */
- res_lp = mlp_solve_lp_problem(mlp);
- if (GNUNET_OK == res_lp)
- {
- mlp->ps.lp_objective_value = glp_get_obj_val (mlp->p.prob);
- LOG (GNUNET_ERROR_TYPE_DEBUG,
- "LP solution was: %.3f\n",
- mlp->ps.lp_objective_value);
- }
- dur_lp = GNUNET_TIME_absolute_get_duration (start_cur_op);
- notify(mlp, GAS_OP_SOLVE_MLP_LP_STOP,
- (GNUNET_OK == res_lp) ? GAS_STAT_SUCCESS : GAS_STAT_FAIL,
- (GNUNET_YES == mlp->stat_mlp_prob_changed) ? GAS_INFO_FULL : GAS_INFO_UPDATED);
- }
- if (GNUNET_YES == mlp->opt_dbg_intopt_presolver)
- res_lp = GNUNET_OK;
- /* Run MLP solver */
- if ((GNUNET_OK == res_lp) || (GNUNET_YES == mlp->opt_dbg_intopt_presolver))
- {
- LOG(GNUNET_ERROR_TYPE_DEBUG, "Running MLP solver \n");
- notify(mlp, GAS_OP_SOLVE_MLP_MLP_START, GAS_STAT_SUCCESS,
- (GNUNET_YES == mlp->stat_mlp_prob_changed) ? GAS_INFO_FULL : GAS_INFO_UPDATED);
- start_cur_op = GNUNET_TIME_absolute_get();
- /* Solve MIP */
- /* Only for debugging, always use LP presolver */
- if (GNUNET_YES == mlp->opt_dbg_intopt_presolver)
- mlp->control_param_mlp.presolve = GNUNET_YES;
- mip_res = glp_intopt (mlp->p.prob, &mlp->control_param_mlp);
- switch (mip_res)
- {
- case 0:
- /* Successful */
- LOG (GNUNET_ERROR_TYPE_INFO,
- "Solving MLP problem: %s\n",
- mlp_solve_to_string (mip_res));
- break;
- case GLP_ETMLIM: /* Time limit reached */
- case GLP_EMIPGAP: /* MIP gap tolerance limit reached */
- case GLP_ESTOP: /* Solver was instructed to stop*/
- /* Semi-successful */
- LOG (GNUNET_ERROR_TYPE_INFO,
- "Solving MLP problem solution was interupted: %s\n",
- mlp_solve_to_string (mip_res));
- break;
- case GLP_EBOUND:
- case GLP_EROOT:
- case GLP_ENOPFS:
- case GLP_ENODFS:
- case GLP_EFAIL:
- default:
- /* Fail */
- LOG (GNUNET_ERROR_TYPE_INFO,
- "Solving MLP problem failed: %s\n",
- mlp_solve_to_string (mip_res));
- break;
- }
- /* Analyze problem status */
- mip_status = glp_mip_status(mlp->p.prob);
- switch (mip_status)
- {
- case GLP_OPT: /* solution is optimal */
- LOG (GNUNET_ERROR_TYPE_WARNING,
- "Solution of MLP problem is optimal: %s, %s\n",
- mlp_solve_to_string (mip_res),
- mlp_status_to_string (mip_status));
- mip_res = GNUNET_OK;
- break;
- case GLP_FEAS: /* solution is feasible but not proven optimal */
- if ( (mlp->ps.mlp_gap <= mlp->pv.mip_gap) ||
- (mlp->ps.lp_mlp_gap <= mlp->pv.lp_mip_gap) )
- {
- LOG (GNUNET_ERROR_TYPE_INFO,
- "Solution of MLP problem is feasible and solution within gap constraints: %s, %s\n",
- mlp_solve_to_string (mip_res),
- mlp_status_to_string (mip_status));
- mip_res = GNUNET_OK;
- }
- else
- {
- LOG (GNUNET_ERROR_TYPE_WARNING,
- "Solution of MLP problem is feasible but solution not within gap constraints: %s, %s\n",
- mlp_solve_to_string (mip_res),
- mlp_status_to_string (mip_status));
- mip_res = GNUNET_SYSERR;
- }
- break;
- case GLP_UNDEF: /* Solution undefined */
- case GLP_NOFEAS: /* No feasible solution */
- default:
- LOG (GNUNET_ERROR_TYPE_ERROR,
- "Solving MLP problem failed: %s %s\n",
- mlp_solve_to_string (mip_res),
- mlp_status_to_string (mip_status));
- mip_res = GNUNET_SYSERR;
- break;
- }
- dur_mlp = GNUNET_TIME_absolute_get_duration (start_cur_op);
- dur_total = GNUNET_TIME_absolute_get_duration (start_total);
- notify(mlp, GAS_OP_SOLVE_MLP_MLP_STOP,
- (GNUNET_OK == mip_res) ? GAS_STAT_SUCCESS : GAS_STAT_FAIL,
- (GNUNET_YES == mlp->stat_mlp_prob_changed) ? GAS_INFO_FULL : GAS_INFO_UPDATED);
- }
- else
- {
- /* Do not execute mip solver since lp solution is invalid */
- dur_mlp = GNUNET_TIME_UNIT_ZERO;
- dur_total = GNUNET_TIME_absolute_get_duration (start_total);
- notify(mlp, GAS_OP_SOLVE_MLP_MLP_STOP, GAS_STAT_FAIL,
- (GNUNET_YES == mlp->stat_mlp_prob_changed) ? GAS_INFO_FULL : GAS_INFO_UPDATED);
- mip_res = GNUNET_SYSERR;
- }
- /* Notify about end */
- notify(mlp, GAS_OP_SOLVE_STOP,
- ((GNUNET_OK == mip_res) && (GNUNET_OK == mip_res)) ? GAS_STAT_SUCCESS : GAS_STAT_FAIL,
- (GNUNET_YES == mlp->stat_mlp_prob_changed) ? GAS_INFO_FULL : GAS_INFO_UPDATED);
- LOG (GNUNET_ERROR_TYPE_DEBUG,
- "Execution time for %s solve: (total/setup/lp/mlp) : %llu %llu %llu %llu\n",
- (GNUNET_YES == mlp->stat_mlp_prob_changed) ? "full" : "updated",
- (unsigned long long) dur_total.rel_value_us,
- (unsigned long long) dur_setup.rel_value_us,
- (unsigned long long) dur_lp.rel_value_us,
- (unsigned long long) dur_mlp.rel_value_us);
- /* Save stats */
- mlp->ps.lp_res = res_lp;
- mlp->ps.mip_res = mip_res;
- mlp->ps.lp_presolv = mlp->control_param_lp.presolve;
- mlp->ps.mip_presolv = mlp->control_param_mlp.presolve;
- mlp->ps.p_cols = glp_get_num_cols(mlp->p.prob);
- mlp->ps.p_rows = glp_get_num_rows(mlp->p.prob);
- mlp->ps.p_elements = mlp->p.num_elements;
- /* Propagate result*/
- notify (mlp, GAS_OP_SOLVE_UPDATE_NOTIFICATION_START,
- (GNUNET_OK == res_lp) && (GNUNET_OK == mip_res) ? GAS_STAT_SUCCESS : GAS_STAT_FAIL,
- GAS_INFO_NONE);
- if ((GNUNET_OK == res_lp) && (GNUNET_OK == mip_res))
- {
- GNUNET_CONTAINER_multipeermap_iterate(mlp->env->addresses,
- &mlp_propagate_results, mlp);
- }
- notify (mlp, GAS_OP_SOLVE_UPDATE_NOTIFICATION_STOP,
- (GNUNET_OK == res_lp) && (GNUNET_OK == mip_res) ? GAS_STAT_SUCCESS : GAS_STAT_FAIL,
- GAS_INFO_NONE);
- struct GNUNET_TIME_Absolute time = GNUNET_TIME_absolute_get();
- if ( (GNUNET_YES == mlp->opt_dump_problem_all) ||
- (mlp->opt_dump_problem_on_fail && ((GNUNET_OK != res_lp) || (GNUNET_OK != mip_res))) )
- {
- /* Write problem to disk */
- switch (mlp->opt_log_format) {
- case MLP_CPLEX:
- GNUNET_asprintf(&filename, "problem_p_%u_a%u_%llu.cplex", mlp->p.num_peers,
- mlp->p.num_addresses, time.abs_value_us);
- glp_write_lp (mlp->p.prob, NULL, filename);
- break;
- case MLP_GLPK:
- GNUNET_asprintf(&filename, "problem_p_%u_a%u_%llu.glpk", mlp->p.num_peers,
- mlp->p.num_addresses, time.abs_value_us);
- glp_write_prob (mlp->p.prob, 0, filename);
- break;
- case MLP_MPS:
- GNUNET_asprintf(&filename, "problem_p_%u_a%u_%llu.mps", mlp->p.num_peers,
- mlp->p.num_addresses, time.abs_value_us);
- glp_write_mps (mlp->p.prob, GLP_MPS_FILE, NULL, filename);
- break;
- default:
- break;
- }
- LOG(GNUNET_ERROR_TYPE_ERROR, "Dumped problem to file: `%s' \n", filename);
- GNUNET_free(filename);
- }
- if ( (mlp->opt_dump_solution_all) ||
- (mlp->opt_dump_solution_on_fail && ((GNUNET_OK != res_lp) || (GNUNET_OK != mip_res))) )
- {
- /* Write solution to disk */
- GNUNET_asprintf(&filename, "problem_p_%u_a%u_%llu.sol", mlp->p.num_peers,
- mlp->p.num_addresses, time.abs_value_us);
- glp_print_mip(mlp->p.prob, filename);
- LOG(GNUNET_ERROR_TYPE_ERROR, "Dumped solution to file: `%s' \n", filename);
- GNUNET_free(filename);
- }
- /* Reset change and update marker */
- mlp->control_param_lp.presolve = GLP_NO;
- mlp->stat_mlp_prob_updated = GNUNET_NO;
- mlp->stat_mlp_prob_changed = GNUNET_NO;
- if ((GNUNET_OK == res_lp) && (GNUNET_OK == mip_res))
- return GNUNET_OK;
- else
- return GNUNET_SYSERR;
- }
- /**
- * Add a single address to the solve
- *
- * @param solver the solver Handle
- * @param address the address to add
- * @param network network type of this address
- */
- static void
- GAS_mlp_address_add (void *solver,
- struct ATS_Address *address,
- uint32_t network)
- {
- struct GAS_MLP_Handle *mlp = solver;
- if (GNUNET_ATS_NetworkTypeCount <= network)
- {
- GNUNET_break (0);
- return;
- }
- if (NULL == address->solver_information)
- {
- address->solver_information = GNUNET_new (struct MLP_information);
- }
- else
- LOG (GNUNET_ERROR_TYPE_ERROR,
- _("Adding address for peer `%s' multiple times\n"),
- GNUNET_i2s(&address->peer));
- /* Is this peer included in the problem? */
- if (NULL ==
- GNUNET_CONTAINER_multipeermap_get (mlp->requested_peers,
- &address->peer))
- {
- /* FIXME: should this be an error? */
- LOG (GNUNET_ERROR_TYPE_DEBUG,
- "Adding address for peer `%s' without address request\n",
- GNUNET_i2s(&address->peer));
- return;
- }
- LOG (GNUNET_ERROR_TYPE_DEBUG,
- "Adding address for peer `%s' with address request \n",
- GNUNET_i2s(&address->peer));
- /* Problem size changed: new address for peer with pending request */
- mlp->stat_mlp_prob_changed = GNUNET_YES;
- if (GNUNET_YES == mlp->opt_mlp_auto_solve)
- GAS_mlp_solve_problem (solver);
- }
- /**
- * Transport properties for this address have changed
- *
- * @param solver solver handle
- * @param address the address
- */
- static void
- GAS_mlp_address_property_changed (void *solver,
- struct ATS_Address *address)
- {
- struct MLP_information *mlpi = address->solver_information;
- struct GAS_MLP_Handle *mlp = solver;
- if (NULL == mlpi)
- {
- LOG (GNUNET_ERROR_TYPE_INFO,
- _("Updating address property for peer `%s' %p not added before\n"),
- GNUNET_i2s (&address->peer),
- address);
- GNUNET_break (0);
- return;
- }
- if (NULL ==
- GNUNET_CONTAINER_multipeermap_get (mlp->requested_peers,
- &address->peer))
- {
- /* Peer is not requested, so no need to update problem */
- return;
- }
- LOG (GNUNET_ERROR_TYPE_DEBUG,
- "Updating properties for peer `%s'\n",
- GNUNET_i2s(&address->peer));
- if (GNUNET_YES == mlp->opt_dbg_feasibility_only)
- return;
- /* Update c7) [r_q[index]][c_b] = f_q * q_averaged[type_index] */
- if ( (GNUNET_YES ==
- mlp_create_problem_update_value (&mlp->p,
- mlp->p.r_q[RQ_QUALITY_METRIC_DELAY],
- mlpi->c_b,
- address->norm_delay.norm,
- __LINE__)) ||
- (GNUNET_YES ==
- mlp_create_problem_update_value (&mlp->p,
- mlp->p.r_q[RQ_QUALITY_METRIC_DISTANCE],
- mlpi->c_b,
- address->norm_distance.norm,
- __LINE__)) )
- {
- mlp->stat_mlp_prob_updated = GNUNET_YES;
- if (GNUNET_YES == mlp->opt_mlp_auto_solve)
- GAS_mlp_solve_problem (solver);
- }
- }
- /**
- * Find the active address in the set of addresses of a peer
- * @param cls destination
- * @param key peer id
- * @param value address
- * @return #GNUNET_OK
- */
- static int
- mlp_get_preferred_address_it (void *cls,
- const struct GNUNET_PeerIdentity *key,
- void *value)
- {
- static int counter = 0;
- struct ATS_Address **aa = cls;
- struct ATS_Address *addr = value;
- struct MLP_information *mlpi = addr->solver_information;
- if (mlpi == NULL)
- return GNUNET_YES;
- /*
- * Debug output
- * GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
- * "MLP [%u] Peer `%s' %s length %u session %u active %s mlp active %s\n",
- * counter, GNUNET_i2s (&addr->peer), addr->plugin, addr->addr_len, addr->session_id,
- * (GNUNET_YES == addr->active) ? "active" : "inactive",
- * (GNUNET_YES == mlpi->n) ? "active" : "inactive");
- */
- if (GNUNET_YES == mlpi->n)
- {
- (*aa) = addr;
- (*aa)->assigned_bw_in = mlpi->b_in;
- (*aa)->assigned_bw_out = mlpi->b_out;
- return GNUNET_NO;
- }
- counter++;
- return GNUNET_YES;
- }
- static double
- get_peer_pref_value (struct GAS_MLP_Handle *mlp,
- const struct GNUNET_PeerIdentity *peer)
- {
- double res;
- const double *preferences;
- int c;
- preferences = mlp->env->get_preferences (mlp->env->cls, peer);
- res = 0.0;
- for (c = 0; c < GNUNET_ATS_PREFERENCE_END; c++)
- {
- /* fprintf (stderr, "VALUE[%u] %s %.3f \n",
- * c, GNUNET_i2s (&cur->addr->peer), t[c]); */
- res += preferences[c];
- }
- res /= GNUNET_ATS_PREFERENCE_END;
- res += 1.0;
- LOG (GNUNET_ERROR_TYPE_DEBUG,
- "Peer preference for peer `%s' == %.2f\n",
- GNUNET_i2s(peer), res);
- return res;
- }
- /**
- * Get the preferred address for a specific peer
- *
- * @param solver the MLP Handle
- * @param peer the peer
- */
- static void
- GAS_mlp_get_preferred_address (void *solver,
- const struct GNUNET_PeerIdentity *peer)
- {
- struct GAS_MLP_Handle *mlp = solver;
- struct ATS_Peer *p;
- struct ATS_Address *res;
- LOG (GNUNET_ERROR_TYPE_DEBUG,
- "Getting preferred address for `%s'\n",
- GNUNET_i2s (peer));
- /* Is this peer included in the problem? */
- if (NULL ==
- GNUNET_CONTAINER_multipeermap_get (mlp->requested_peers,
- peer))
- {
- LOG (GNUNET_ERROR_TYPE_INFO, "Adding peer `%s' to list of requested_peers with requests\n",
- GNUNET_i2s (peer));
- p = GNUNET_new (struct ATS_Peer);
- p->id = (*peer);
- p->f = get_peer_pref_value (mlp, peer);
- GNUNET_CONTAINER_multipeermap_put (mlp->requested_peers,
- peer, p,
- GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_FAST);
- /* Added new peer, we have to rebuild problem before solving */
- mlp->stat_mlp_prob_changed = GNUNET_YES;
- if ((GNUNET_YES == mlp->opt_mlp_auto_solve)&&
- (GNUNET_YES == GNUNET_CONTAINER_multipeermap_contains(mlp->env->addresses,
- peer)))
- {
- mlp->exclude_peer = peer;
- GAS_mlp_solve_problem (mlp);
- mlp->exclude_peer = NULL;
- }
- }
- /* Get prefered address */
- res = NULL;
- GNUNET_CONTAINER_multipeermap_get_multiple (mlp->env->addresses, peer,
- &mlp_get_preferred_address_it, &res);
- if (NULL != res)
- mlp->env->bandwidth_changed_cb (mlp->env->cls,
- res);
- }
- /**
- * Deletes a single address in the MLP problem
- *
- * The MLP problem has to be recreated and the problem has to be resolved
- *
- * @param solver the MLP Handle
- * @param address the address to delete
- */
- static void
- GAS_mlp_address_delete (void *solver,
- struct ATS_Address *address)
- {
- struct GAS_MLP_Handle *mlp = solver;
- struct MLP_information *mlpi;
- struct ATS_Address *res;
- int was_active;
- mlpi = address->solver_information;
- if (NULL != mlpi)
- {
- /* Remove full address */
- GNUNET_free (mlpi);
- address->solver_information = NULL;
- }
- was_active = address->active;
- address->active = GNUNET_NO;
- address->assigned_bw_in = 0;
- address->assigned_bw_out = 0;
- /* Is this peer included in the problem? */
- if (NULL ==
- GNUNET_CONTAINER_multipeermap_get (mlp->requested_peers,
- &address->peer))
- {
- LOG (GNUNET_ERROR_TYPE_INFO,
- "Deleting address for peer `%s' without address request \n",
- GNUNET_i2s(&address->peer));
- return;
- }
- LOG (GNUNET_ERROR_TYPE_INFO,
- "Deleting address for peer `%s' with address request \n",
- GNUNET_i2s (&address->peer));
- /* Problem size changed: new address for peer with pending request */
- mlp->stat_mlp_prob_changed = GNUNET_YES;
- if (GNUNET_YES == mlp->opt_mlp_auto_solve)
- {
- GAS_mlp_solve_problem (solver);
- }
- if (GNUNET_YES == was_active)
- {
- GAS_mlp_get_preferred_address (solver, &address->peer);
- res = NULL;
- GNUNET_CONTAINER_multipeermap_get_multiple (mlp->env->addresses,
- &address->peer,
- &mlp_get_preferred_address_it,
- &res);
- if (NULL == res)
- {
- /* No alternative address, disconnecting peer */
- mlp->env->bandwidth_changed_cb (mlp->env->cls, address);
- }
- }
- }
- /**
- * Start a bulk operation
- *
- * @param solver the solver
- */
- static void
- GAS_mlp_bulk_start (void *solver)
- {
- struct GAS_MLP_Handle *s = solver;
- LOG (GNUNET_ERROR_TYPE_DEBUG,
- "Locking solver for bulk operation ...\n");
- GNUNET_assert (NULL != solver);
- s->stat_bulk_lock ++;
- }
- static void
- GAS_mlp_bulk_stop (void *solver)
- {
- struct GAS_MLP_Handle *s = solver;
- LOG (GNUNET_ERROR_TYPE_DEBUG,
- "Unlocking solver from bulk operation ...\n");
- GNUNET_assert (NULL != solver);
- if (s->stat_bulk_lock < 1)
- {
- GNUNET_break (0);
- return;
- }
- s->stat_bulk_lock --;
- if (0 < s->stat_bulk_requests)
- {
- GAS_mlp_solve_problem (solver);
- s->stat_bulk_requests= 0;
- }
- }
- /**
- * Stop notifying about address and bandwidth changes for this peer
- *
- * @param solver the MLP handle
- * @param peer the peer
- */
- static void
- GAS_mlp_stop_get_preferred_address (void *solver,
- const struct GNUNET_PeerIdentity *peer)
- {
- struct GAS_MLP_Handle *mlp = solver;
- struct ATS_Peer *p = NULL;
- GNUNET_assert (NULL != solver);
- GNUNET_assert (NULL != peer);
- if (NULL != (p = GNUNET_CONTAINER_multipeermap_get (mlp->requested_peers, peer)))
- {
- GNUNET_assert (GNUNET_YES ==
- GNUNET_CONTAINER_multipeermap_remove (mlp->requested_peers, peer, p));
- GNUNET_free (p);
- mlp->stat_mlp_prob_changed = GNUNET_YES;
- if (GNUNET_YES == mlp->opt_mlp_auto_solve)
- {
- GAS_mlp_solve_problem (solver);
- }
- }
- }
- /**
- * Changes the preferences for a peer in the MLP problem
- *
- * @param solver the MLP Handle
- * @param peer the peer
- * @param kind the kind to change the preference
- * @param pref_rel the relative score
- */
- static void
- GAS_mlp_address_change_preference (void *solver,
- const struct GNUNET_PeerIdentity *peer,
- enum GNUNET_ATS_PreferenceKind kind,
- double pref_rel)
- {
- struct GAS_MLP_Handle *mlp = solver;
- struct ATS_Peer *p;
- LOG (GNUNET_ERROR_TYPE_DEBUG,
- "Changing preference for address for peer `%s' to %.2f\n",
- GNUNET_i2s(peer),
- pref_rel);
- GNUNET_STATISTICS_update (mlp->env->stats,
- "# LP address preference changes", 1, GNUNET_NO);
- /* Update the constraints with changed preferences */
- /* Update relativity constraint c9 */
- if (NULL == (p = GNUNET_CONTAINER_multipeermap_get (mlp->requested_peers, peer)))
- {
- LOG (GNUNET_ERROR_TYPE_INFO,
- "Updating preference for unknown peer `%s'\n",
- GNUNET_i2s(peer));
- return;
- }
- if (GNUNET_NO == mlp->opt_dbg_feasibility_only)
- {
- p->f = get_peer_pref_value (mlp, peer);
- mlp_create_problem_update_value (&mlp->p,
- p->r_c9,
- mlp->p.c_r,
- - p->f,
- __LINE__);
- /* Problem size changed: new address for peer with pending request */
- mlp->stat_mlp_prob_updated = GNUNET_YES;
- if (GNUNET_YES == mlp->opt_mlp_auto_solve)
- GAS_mlp_solve_problem (solver);
- }
- }
- /**
- * Get application feedback for a peer
- *
- * @param solver the solver handle
- * @param application the application
- * @param peer the peer to change the preference for
- * @param scope the time interval for this feedback: [now - scope .. now]
- * @param kind the kind to change the preference
- * @param score the score
- */
- static void
- GAS_mlp_address_preference_feedback (void *solver,
- struct GNUNET_SERVER_Client *application,
- const struct GNUNET_PeerIdentity *peer,
- const struct GNUNET_TIME_Relative scope,
- enum GNUNET_ATS_PreferenceKind kind,
- double score)
- {
- struct GAS_PROPORTIONAL_Handle *s = solver;
- GNUNET_assert (NULL != solver);
- GNUNET_assert (NULL != peer);
- GNUNET_assert (NULL != s);
- }
- static int
- mlp_free_peers (void *cls,
- const struct GNUNET_PeerIdentity *key, void *value)
- {
- struct GNUNET_CONTAINER_MultiPeerMap *map = cls;
- struct ATS_Peer *p = value;
- GNUNET_assert (GNUNET_YES ==
- GNUNET_CONTAINER_multipeermap_remove (map, key, value));
- GNUNET_free (p);
- return GNUNET_OK;
- }
- /**
- * Shutdown the MLP problem solving component
- *
- * @param cls the solver handle
- * @return NULL
- */
- void *
- libgnunet_plugin_ats_mlp_done (void *cls)
- {
- struct GNUNET_ATS_SolverFunctions *sf = cls;
- struct GAS_MLP_Handle *mlp = sf->cls;
- LOG (GNUNET_ERROR_TYPE_DEBUG,
- "Shutting down mlp solver\n");
- mlp_delete_problem (mlp);
- GNUNET_CONTAINER_multipeermap_iterate (mlp->requested_peers,
- &mlp_free_peers,
- mlp->requested_peers);
- GNUNET_CONTAINER_multipeermap_destroy (mlp->requested_peers);
- mlp->requested_peers = NULL;
- /* Clean up GLPK environment */
- glp_free_env();
- GNUNET_free (mlp);
- LOG (GNUNET_ERROR_TYPE_DEBUG,
- "Shutdown down of mlp solver complete\n");
- return NULL;
- }
- void *
- libgnunet_plugin_ats_mlp_init (void *cls)
- {
- static struct GNUNET_ATS_SolverFunctions sf;
- struct GNUNET_ATS_PluginEnvironment *env = cls;
- struct GAS_MLP_Handle * mlp = GNUNET_new (struct GAS_MLP_Handle);
- float f_tmp;
- unsigned long long tmp;
- unsigned int b_min;
- unsigned int n_min;
- int c;
- char *outputformat;
- struct GNUNET_TIME_Relative max_duration;
- long long unsigned int max_iterations;
- /* Init GLPK environment */
- int res = glp_init_env();
- switch (res) {
- case 0:
- LOG (GNUNET_ERROR_TYPE_DEBUG, "GLPK: `%s'\n",
- "initialization successful");
- break;
- case 1:
- LOG (GNUNET_ERROR_TYPE_DEBUG, "GLPK: `%s'\n",
- "environment is already initialized");
- break;
- case 2:
- LOG (GNUNET_ERROR_TYPE_ERROR, "Could not init GLPK: `%s'\n",
- "initialization failed (insufficient memory)");
- GNUNET_free(mlp);
- return NULL;
- break;
- case 3:
- LOG (GNUNET_ERROR_TYPE_ERROR, "Could not init GLPK: `%s'\n",
- "initialization failed (unsupported programming model)");
- GNUNET_free(mlp);
- return NULL;
- break;
- default:
- break;
- }
- mlp->opt_dump_problem_all = GNUNET_CONFIGURATION_get_value_yesno (env->cfg,
- "ats", "MLP_DUMP_PROBLEM_ALL");
- if (GNUNET_SYSERR == mlp->opt_dump_problem_all)
- mlp->opt_dump_problem_all = GNUNET_NO;
- mlp->opt_dump_solution_all = GNUNET_CONFIGURATION_get_value_yesno (env->cfg,
- "ats", "MLP_DUMP_SOLUTION_ALL");
- if (GNUNET_SYSERR == mlp->opt_dump_solution_all)
- mlp->opt_dump_solution_all = GNUNET_NO;
- mlp->opt_dump_problem_on_fail = GNUNET_CONFIGURATION_get_value_yesno (env->cfg,
- "ats", "MLP_DUMP_PROBLEM_ON_FAIL");
- if (GNUNET_SYSERR == mlp->opt_dump_problem_on_fail)
- mlp->opt_dump_problem_on_fail = GNUNET_NO;
- mlp->opt_dump_solution_on_fail = GNUNET_CONFIGURATION_get_value_yesno (env->cfg,
- "ats", "MLP_DUMP_SOLUTION_ON_FAIL");
- if (GNUNET_SYSERR == mlp->opt_dump_solution_on_fail)
- mlp->opt_dump_solution_on_fail = GNUNET_NO;
- mlp->opt_dbg_glpk_verbose = GNUNET_CONFIGURATION_get_value_yesno (env->cfg,
- "ats", "MLP_DBG_GLPK_VERBOSE");
- if (GNUNET_SYSERR == mlp->opt_dbg_glpk_verbose)
- mlp->opt_dbg_glpk_verbose = GNUNET_NO;
- mlp->opt_dbg_feasibility_only = GNUNET_CONFIGURATION_get_value_yesno (env->cfg,
- "ats", "MLP_DBG_FEASIBILITY_ONLY");
- if (GNUNET_SYSERR == mlp->opt_dbg_feasibility_only)
- mlp->opt_dbg_feasibility_only = GNUNET_NO;
- if (GNUNET_YES == mlp->opt_dbg_feasibility_only)
- LOG (GNUNET_ERROR_TYPE_WARNING,
- "MLP solver is configured to check feasibility only!\n");
- mlp->opt_dbg_autoscale_problem = GNUNET_CONFIGURATION_get_value_yesno (env->cfg,
- "ats", "MLP_DBG_AUTOSCALE_PROBLEM");
- if (GNUNET_SYSERR == mlp->opt_dbg_autoscale_problem)
- mlp->opt_dbg_autoscale_problem = GNUNET_NO;
- if (GNUNET_YES == mlp->opt_dbg_autoscale_problem)
- LOG (GNUNET_ERROR_TYPE_WARNING,
- "MLP solver is configured automatically scale the problem!\n");
- mlp->opt_dbg_intopt_presolver = GNUNET_CONFIGURATION_get_value_yesno (env->cfg,
- "ats", "MLP_DBG_INTOPT_PRESOLVE");
- if (GNUNET_SYSERR == mlp->opt_dbg_intopt_presolver)
- mlp->opt_dbg_intopt_presolver = GNUNET_NO;
- if (GNUNET_YES == mlp->opt_dbg_intopt_presolver)
- LOG (GNUNET_ERROR_TYPE_WARNING,
- "MLP solver is configured use the mlp presolver\n");
- mlp->opt_dbg_optimize_diversity = GNUNET_CONFIGURATION_get_value_yesno (env->cfg,
- "ats", "MLP_DBG_OPTIMIZE_DIVERSITY");
- if (GNUNET_SYSERR == mlp->opt_dbg_optimize_diversity)
- mlp->opt_dbg_optimize_diversity = GNUNET_YES;
- if (GNUNET_NO == mlp->opt_dbg_optimize_diversity)
- LOG (GNUNET_ERROR_TYPE_WARNING,
- "MLP solver is not optimizing for diversity\n");
- mlp->opt_dbg_optimize_relativity= GNUNET_CONFIGURATION_get_value_yesno (env->cfg,
- "ats", "MLP_DBG_OPTIMIZE_RELATIVITY");
- if (GNUNET_SYSERR == mlp->opt_dbg_optimize_relativity)
- mlp->opt_dbg_optimize_relativity = GNUNET_YES;
- if (GNUNET_NO == mlp->opt_dbg_optimize_relativity)
- LOG (GNUNET_ERROR_TYPE_WARNING,
- "MLP solver is not optimizing for relativity\n");
- mlp->opt_dbg_optimize_quality = GNUNET_CONFIGURATION_get_value_yesno (env->cfg,
- "ats", "MLP_DBG_OPTIMIZE_QUALITY");
- if (GNUNET_SYSERR == mlp->opt_dbg_optimize_quality)
- mlp->opt_dbg_optimize_quality = GNUNET_YES;
- if (GNUNET_NO == mlp->opt_dbg_optimize_quality)
- LOG (GNUNET_ERROR_TYPE_WARNING,
- "MLP solver is not optimizing for quality\n");
- mlp->opt_dbg_optimize_utility = GNUNET_CONFIGURATION_get_value_yesno (env->cfg,
- "ats", "MLP_DBG_OPTIMIZE_UTILITY");
- if (GNUNET_SYSERR == mlp->opt_dbg_optimize_utility)
- mlp->opt_dbg_optimize_utility = GNUNET_YES;
- if (GNUNET_NO == mlp->opt_dbg_optimize_utility)
- LOG (GNUNET_ERROR_TYPE_WARNING,
- "MLP solver is not optimizing for utility\n");
- if ( (GNUNET_NO == mlp->opt_dbg_optimize_utility) &&
- (GNUNET_NO == mlp->opt_dbg_optimize_quality) &&
- (GNUNET_NO == mlp->opt_dbg_optimize_relativity) &&
- (GNUNET_NO == mlp->opt_dbg_optimize_utility) &&
- (GNUNET_NO == mlp->opt_dbg_feasibility_only))
- {
- LOG (GNUNET_ERROR_TYPE_ERROR,
- _("MLP solver is not optimizing for anything, changing to feasibility check\n"));
- mlp->opt_dbg_feasibility_only = GNUNET_YES;
- }
- if (GNUNET_SYSERR == GNUNET_CONFIGURATION_get_value_string (env->cfg,
- "ats", "MLP_LOG_FORMAT", &outputformat))
- mlp->opt_log_format = MLP_CPLEX;
- else
- {
- GNUNET_STRINGS_utf8_toupper(outputformat, outputformat);
- if (0 == strcmp (outputformat, "MPS"))
- {
- mlp->opt_log_format = MLP_MPS;
- }
- else if (0 == strcmp (outputformat, "CPLEX"))
- {
- mlp->opt_log_format = MLP_CPLEX;
- }
- else if (0 == strcmp (outputformat, "GLPK"))
- {
- mlp->opt_log_format = MLP_GLPK;
- }
- else
- {
- LOG (GNUNET_ERROR_TYPE_WARNING,
- "Invalid log format `%s' in configuration, using CPLEX!\n",
- outputformat);
- mlp->opt_log_format = MLP_CPLEX;
- }
- GNUNET_free (outputformat);
- }
- mlp->pv.BIG_M = (double) BIG_M_VALUE;
- mlp->pv.mip_gap = (double) 0.0;
- if (GNUNET_SYSERR != GNUNET_CONFIGURATION_get_value_float (env->cfg, "ats",
- "MLP_MAX_MIP_GAP", &f_tmp))
- {
- if ((f_tmp < 0.0) || (f_tmp > 1.0))
- {
- LOG (GNUNET_ERROR_TYPE_ERROR, _("Invalid %s configuration %f \n"),
- "MIP gap", f_tmp);
- }
- else
- {
- mlp->pv.mip_gap = f_tmp;
- LOG (GNUNET_ERROR_TYPE_INFO, "Using %s of %.3f\n",
- "MIP gap", f_tmp);
- }
- }
- mlp->pv.lp_mip_gap = (double) 0.0;
- if (GNUNET_SYSERR != GNUNET_CONFIGURATION_get_value_float (env->cfg, "ats",
- "MLP_MAX_LP_MIP_GAP", &f_tmp))
- {
- if ((f_tmp < 0.0) || (f_tmp > 1.0))
- {
- LOG (GNUNET_ERROR_TYPE_ERROR, _("Invalid %s configuration %f \n"),
- "LP/MIP", f_tmp);
- }
- else
- {
- mlp->pv.lp_mip_gap = f_tmp;
- LOG (GNUNET_ERROR_TYPE_INFO, "Using %s gap of %.3f\n",
- "LP/MIP", f_tmp);
- }
- }
- /* Get timeout for iterations */
- if (GNUNET_OK != GNUNET_CONFIGURATION_get_value_time(env->cfg, "ats",
- "MLP_MAX_DURATION", &max_duration))
- {
- max_duration = MLP_MAX_EXEC_DURATION;
- }
- /* Get maximum number of iterations */
- if (GNUNET_OK != GNUNET_CONFIGURATION_get_value_size(env->cfg, "ats",
- "MLP_MAX_ITERATIONS", &max_iterations))
- {
- max_iterations = MLP_MAX_ITERATIONS;
- }
- /* Get diversity coefficient from configuration */
- mlp->pv.co_D = MLP_DEFAULT_D;
- if (GNUNET_SYSERR != GNUNET_CONFIGURATION_get_value_float (env->cfg, "ats",
- "MLP_COEFFICIENT_D", &f_tmp))
- {
- if ((f_tmp < 0.0))
- {
- LOG (GNUNET_ERROR_TYPE_ERROR, _("Invalid %s configuration %f \n"),
- "MLP_COEFFICIENT_D", f_tmp);
- }
- else
- {
- mlp->pv.co_D = f_tmp;
- LOG (GNUNET_ERROR_TYPE_INFO, "Using %s gap of %.3f\n",
- "MLP_COEFFICIENT_D", f_tmp);
- }
- }
- /* Get relativity coefficient from configuration */
- mlp->pv.co_R = MLP_DEFAULT_R;
- if (GNUNET_SYSERR != GNUNET_CONFIGURATION_get_value_float (env->cfg, "ats",
- "MLP_COEFFICIENT_R", &f_tmp))
- {
- if ((f_tmp < 0.0))
- {
- LOG (GNUNET_ERROR_TYPE_ERROR, _("Invalid %s configuration %f \n"),
- "MLP_COEFFICIENT_R", f_tmp);
- }
- else
- {
- mlp->pv.co_R = f_tmp;
- LOG (GNUNET_ERROR_TYPE_INFO, "Using %s gap of %.3f\n",
- "MLP_COEFFICIENT_R", f_tmp);
- }
- }
- /* Get utilization coefficient from configuration */
- mlp->pv.co_U = MLP_DEFAULT_U;
- if (GNUNET_SYSERR != GNUNET_CONFIGURATION_get_value_float (env->cfg, "ats",
- "MLP_COEFFICIENT_U", &f_tmp))
- {
- if ((f_tmp < 0.0))
- {
- LOG (GNUNET_ERROR_TYPE_ERROR, _("Invalid %s configuration %f \n"),
- "MLP_COEFFICIENT_U", f_tmp);
- }
- else
- {
- mlp->pv.co_U = f_tmp;
- LOG (GNUNET_ERROR_TYPE_INFO, "Using %s gap of %.3f\n",
- "MLP_COEFFICIENT_U", f_tmp);
- }
- }
- /* Get quality metric coefficients from configuration */
- for (c = 0; c < RQ_QUALITY_METRIC_COUNT; c++)
- {
- /* initialize quality coefficients with default value 1.0 */
- mlp->pv.co_Q[c] = MLP_DEFAULT_QUALITY;
- }
- if (GNUNET_OK ==
- GNUNET_CONFIGURATION_get_value_size (env->cfg, "ats",
- "MLP_COEFFICIENT_QUALITY_DELAY",
- &tmp))
- mlp->pv.co_Q[RQ_QUALITY_METRIC_DELAY] = (double) tmp / 100;
- else
- mlp->pv.co_Q[RQ_QUALITY_METRIC_DELAY] = MLP_DEFAULT_QUALITY;
- if (GNUNET_OK ==
- GNUNET_CONFIGURATION_get_value_size (env->cfg, "ats",
- "MLP_COEFFICIENT_QUALITY_DISTANCE",
- &tmp))
- mlp->pv.co_Q[RQ_QUALITY_METRIC_DISTANCE] = (double) tmp / 100;
- else
- mlp->pv.co_Q[RQ_QUALITY_METRIC_DISTANCE] = MLP_DEFAULT_QUALITY;
- /* Get minimum bandwidth per used address from configuration */
- if (GNUNET_OK == GNUNET_CONFIGURATION_get_value_size (env->cfg, "ats",
- "MLP_MIN_BANDWIDTH",
- &tmp))
- b_min = tmp;
- else
- {
- b_min = ntohl (GNUNET_CONSTANTS_DEFAULT_BW_IN_OUT.value__);
- }
- /* Get minimum number of connections from configuration */
- if (GNUNET_OK == GNUNET_CONFIGURATION_get_value_size (env->cfg, "ats",
- "MLP_MIN_CONNECTIONS",
- &tmp))
- n_min = tmp;
- else
- n_min = MLP_DEFAULT_MIN_CONNECTIONS;
- /* Init network quotas */
- for (c = 0; c < GNUNET_ATS_NetworkTypeCount; c++)
- {
- mlp->pv.quota_index[c] = c;
- mlp->pv.quota_out[c] = env->out_quota[c];
- mlp->pv.quota_in[c] = env->in_quota[c];
- LOG (GNUNET_ERROR_TYPE_INFO,
- "Quota for network `%s' (in/out) %llu/%llu\n",
- GNUNET_ATS_print_network_type (c),
- mlp->pv.quota_out[c],
- mlp->pv.quota_in[c]);
- /* Check if defined quota could make problem unsolvable */
- if ((n_min * b_min) > mlp->pv.quota_out[c])
- {
- LOG (GNUNET_ERROR_TYPE_INFO,
- _("Adjusting inconsistent outbound quota configuration for network `%s', is %llu must be at least %llu\n"),
- GNUNET_ATS_print_network_type(mlp->pv.quota_index[c]),
- mlp->pv.quota_out[c],
- (n_min * b_min));
- mlp->pv.quota_out[c] = (n_min * b_min);
- }
- if ((n_min * b_min) > mlp->pv.quota_in[c])
- {
- LOG (GNUNET_ERROR_TYPE_INFO,
- _("Adjusting inconsistent inbound quota configuration for network `%s', is %llu must be at least %llu\n"),
- GNUNET_ATS_print_network_type(mlp->pv.quota_index[c]),
- mlp->pv.quota_in[c],
- (n_min * b_min));
- mlp->pv.quota_in[c] = (n_min * b_min);
- }
- /* Check if bandwidth is too big to make problem solvable */
- if (mlp->pv.BIG_M < mlp->pv.quota_out[c])
- {
- LOG (GNUNET_ERROR_TYPE_INFO,
- _("Adjusting outbound quota configuration for network `%s'from %llu to %.0f\n"),
- GNUNET_ATS_print_network_type(mlp->pv.quota_index[c]),
- mlp->pv.quota_out[c],
- mlp->pv.BIG_M);
- mlp->pv.quota_out[c] = mlp->pv.BIG_M ;
- }
- if (mlp->pv.BIG_M < mlp->pv.quota_in[c])
- {
- LOG (GNUNET_ERROR_TYPE_INFO,
- _("Adjusting inbound quota configuration for network `%s' from %llu to %.0f\n"),
- GNUNET_ATS_print_network_type(mlp->pv.quota_index[c]),
- mlp->pv.quota_in[c],
- mlp->pv.BIG_M);
- mlp->pv.quota_in[c] = mlp->pv.BIG_M ;
- }
- }
- mlp->env = env;
- sf.cls = mlp;
- sf.s_add = &GAS_mlp_address_add;
- sf.s_address_update_property = &GAS_mlp_address_property_changed;
- sf.s_get = &GAS_mlp_get_preferred_address;
- sf.s_get_stop = &GAS_mlp_stop_get_preferred_address;
- sf.s_pref = &GAS_mlp_address_change_preference;
- sf.s_feedback = &GAS_mlp_address_preference_feedback;
- sf.s_del = &GAS_mlp_address_delete;
- sf.s_bulk_start = &GAS_mlp_bulk_start;
- sf.s_bulk_stop = &GAS_mlp_bulk_stop;
- /* Setting MLP Input variables */
- mlp->pv.b_min = b_min;
- mlp->pv.n_min = n_min;
- mlp->pv.m_q = RQ_QUALITY_METRIC_COUNT;
- mlp->stat_mlp_prob_changed = GNUNET_NO;
- mlp->stat_mlp_prob_updated = GNUNET_NO;
- mlp->opt_mlp_auto_solve = GNUNET_YES;
- mlp->requested_peers = GNUNET_CONTAINER_multipeermap_create (10, GNUNET_NO);
- mlp->stat_bulk_requests = 0;
- mlp->stat_bulk_lock = 0;
- /* Setup GLPK */
- /* Redirect GLPK output to GNUnet logging */
- glp_term_hook (&mlp_term_hook, (void *) mlp);
- /* Init LP solving parameters */
- glp_init_smcp(&mlp->control_param_lp);
- mlp->control_param_lp.msg_lev = GLP_MSG_OFF;
- if (GNUNET_YES == mlp->opt_dbg_glpk_verbose)
- mlp->control_param_lp.msg_lev = GLP_MSG_ALL;
- mlp->control_param_lp.it_lim = max_iterations;
- mlp->control_param_lp.tm_lim = max_duration.rel_value_us / 1000LL;
- /* Init MLP solving parameters */
- glp_init_iocp(&mlp->control_param_mlp);
- /* Setting callback function */
- mlp->control_param_mlp.cb_func = &mlp_branch_and_cut_cb;
- mlp->control_param_mlp.cb_info = mlp;
- mlp->control_param_mlp.msg_lev = GLP_MSG_OFF;
- mlp->control_param_mlp.mip_gap = mlp->pv.mip_gap;
- if (GNUNET_YES == mlp->opt_dbg_glpk_verbose)
- mlp->control_param_mlp.msg_lev = GLP_MSG_ALL;
- mlp->control_param_mlp.tm_lim = max_duration.rel_value_us / 1000LL;
- LOG (GNUNET_ERROR_TYPE_DEBUG, "solver ready\n");
- return &sf;
- }
- /* end of plugin_ats_mlp.c */
|