aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorMatthias Wachs <wachs@net.in.tum.de>2013-02-20 13:20:08 +0000
committerMatthias Wachs <wachs@net.in.tum.de>2013-02-20 13:20:08 +0000
commitadf18305521dc87c4ca1aee82e910ff8e22199cc (patch)
treecd5a249a88b447f76e25d49e81420389c8bdcbeb
parent4d736b1054ad4d4f7d25d9946f0a999960b091ae (diff)
downloadgnunet-adf18305521dc87c4ca1aee82e910ff8e22199cc.tar.gz
gnunet-adf18305521dc87c4ca1aee82e910ff8e22199cc.zip
changes
-rw-r--r--src/ats/gnunet-service-ats_addresses_mlp.c50
1 files changed, 43 insertions, 7 deletions
diff --git a/src/ats/gnunet-service-ats_addresses_mlp.c b/src/ats/gnunet-service-ats_addresses_mlp.c
index 8bf9f127a..c8d9759a1 100644
--- a/src/ats/gnunet-service-ats_addresses_mlp.c
+++ b/src/ats/gnunet-service-ats_addresses_mlp.c
@@ -37,15 +37,48 @@
37 * gnunet.org:/vcs/fsnsg/ats-paper.git/tech-doku/ats-tech-guide.tex 37 * gnunet.org:/vcs/fsnsg/ats-paper.git/tech-doku/ats-tech-guide.tex
38 * use build_txt.sh to generate plaintext output 38 * use build_txt.sh to generate plaintext output
39 * 39 *
40 * 4 MLP solver
41 *
42 * The MLP solver (mlp) tries to finds an optimal bandwidth assignmentby 40 * The MLP solver (mlp) tries to finds an optimal bandwidth assignmentby
43 * optimizing an mixed integer programming problem. The MLP solver uses a 41 * optimizing an mixed integer programming problem. The MLP solver uses a
44 * number of constraints to find the best adddress for a peer and an optimal 42 * number of constraints to find the best adddress for a peer and an optimal
45 * bandwidth assignment. mlp uses the GNU Linear Programming Kit to solve the 43 * bandwidth assignment. mlp uses the GNU Linear Programming Kit to solve the
46 * MLP problem. 44 * MLP problem.
47 * 45 *
48 * 4.1 Input data 46 * We defined a constraint system to find an optimal bandwidth assignment.
47 * This constraint system uses as an input data addresses, bandwidth quotas,
48 * preferences and quality values. This constraint system is stored in an
49 * matrix based equotation system.
50 *
51 * 5 Using GLPK
52 *
53 * A (M)LP problem consists of a target function to optimizes, constraints
54 * and rows and columns. FIXME GLP uses three arrays to index the matrix: two
55 * integer arrays storing the row and column indices in the matrix and an
56 * float array to store the coeeficient.
57 *
58 * To solve the problem we first find an initial solution for the LP problem
59 * using the LP solver and then find an MLP solution based on this solution
60 * using the MLP solver.
61 *
62 * Solving (M)LP problems has the property that finding an initial solution
63 * for the LP problem is computationally expensive and finding the MLP
64 * solution is cheaper. This is especially interesting an existing LP
65 * solution can be reused if only coefficients in the matrix have changed
66 * (addresses updated). Only when the problem size changes (addresses added
67 * or deleted) a new LP solution has to be found.
68 *
69 * Intended usage
70 * The mlp solver solves the bandwidth assignment problem only on demand when
71 * an address suggestion is requested. When an address is requested mlp the
72 * solves the mlp problem and if the active address or the bandwidth assigned
73 * changes it calls the callback to addresses. The mlp solver gets notified
74 * about new addresses (adding sessions), removed addresses (address
75 * deletions) and address updates. To benefit from the mlp properties
76 * mentioned in section 5 the solver rembers if since the last solution
77 * addresses were added or deleted (problem size changed, problem has to be
78 * rebuild and solved from sratch) or if addresses were updated and the
79 * existing solution can be reused.
80 *
81 * 5.1 Input data
49 * 82 *
50 * The quotas for each network segment are passed by addresses. MLP can be 83 * The quotas for each network segment are passed by addresses. MLP can be
51 * adapted using configuration settings and uses the following parameters: 84 * adapted using configuration settings and uses the following parameters:
@@ -77,13 +110,13 @@
77 * * MLP_COEFFICIENT_QUALITY_DISTANCE: 110 * * MLP_COEFFICIENT_QUALITY_DISTANCE:
78 * Quality distance coefficient (default: 1.0) 111 * Quality distance coefficient (default: 1.0)
79 * 112 *
80 * 4.2 Data structures used 113 * 5.2 Data structures used
81 * 114 *
82 * mlp has for each known peer a struct ATS_Peer containing information about 115 * mlp has for each known peer a struct ATS_Peer containing information about
83 * a specific peer. The address field solver_information contains information 116 * a specific peer. The address field solver_information contains information
84 * about the mlp properties of this address. 117 * about the mlp properties of this address.
85 * 118 *
86 * 4.3 Initializing 119 * 5.3 Initializing
87 * 120 *
88 * During initialization mlp initializes the GLPK libray used to solve the 121 * During initialization mlp initializes the GLPK libray used to solve the
89 * MLP problem: it initializes the glpk environment and creates an initial LP 122 * MLP problem: it initializes the glpk environment and creates an initial LP
@@ -96,8 +129,8 @@
96 * to BIG M. If the configured quota is smaller than MLP_MIN_CONNECTIONS 129 * to BIG M. If the configured quota is smaller than MLP_MIN_CONNECTIONS
97 * *MLP_MIN_BANDWIDTH it is increased to this value. 130 * *MLP_MIN_BANDWIDTH it is increased to this value.
98 * 131 *
99 * 4.4 Shutdown 132 * 5.4 Shutdown
100 * TBD 133
101 */ 134 */
102 135
103#define LOG(kind,...) GNUNET_log_from (kind, "ats-mlp",__VA_ARGS__) 136#define LOG(kind,...) GNUNET_log_from (kind, "ats-mlp",__VA_ARGS__)
@@ -1612,6 +1645,7 @@ void
1612GAS_mlp_address_add (void *solver, struct GNUNET_CONTAINER_MultiHashMap * addresses, struct ATS_Address *address) 1645GAS_mlp_address_add (void *solver, struct GNUNET_CONTAINER_MultiHashMap * addresses, struct ATS_Address *address)
1613{ 1646{
1614 LOG (GNUNET_ERROR_TYPE_DEBUG, "Adding address for peer `%s'\n", GNUNET_i2s(&address->peer)); 1647 LOG (GNUNET_ERROR_TYPE_DEBUG, "Adding address for peer `%s'\n", GNUNET_i2s(&address->peer));
1648 return;
1615} 1649}
1616 1650
1617/** 1651/**
@@ -1647,6 +1681,7 @@ GAS_mlp_address_update (void *solver,
1647 1681
1648 LOG (GNUNET_ERROR_TYPE_DEBUG, "Updating address for peer `%s'\n", 1682 LOG (GNUNET_ERROR_TYPE_DEBUG, "Updating address for peer `%s'\n",
1649 GNUNET_i2s(&address->peer)); 1683 GNUNET_i2s(&address->peer));
1684 return;
1650 1685
1651 GNUNET_STATISTICS_update (mlp->stats, "# MLP address updates", 1, GNUNET_NO); 1686 GNUNET_STATISTICS_update (mlp->stats, "# MLP address updates", 1, GNUNET_NO);
1652 1687
@@ -1755,6 +1790,7 @@ GAS_mlp_address_delete (void *solver,
1755 1790
1756 LOG (GNUNET_ERROR_TYPE_DEBUG, "Deleting address for peer `%s'\n", 1791 LOG (GNUNET_ERROR_TYPE_DEBUG, "Deleting address for peer `%s'\n",
1757 GNUNET_i2s(&address->peer)); 1792 GNUNET_i2s(&address->peer));
1793 return;
1758 1794
1759 GNUNET_STATISTICS_update (mlp->stats,"# LP address deletions", 1, GNUNET_NO); 1795 GNUNET_STATISTICS_update (mlp->stats,"# LP address deletions", 1, GNUNET_NO);
1760 struct GAS_MLP_SolutionContext ctx; 1796 struct GAS_MLP_SolutionContext ctx;