diff options
author | Matthias Wachs <wachs@net.in.tum.de> | 2013-02-20 13:20:08 +0000 |
---|---|---|
committer | Matthias Wachs <wachs@net.in.tum.de> | 2013-02-20 13:20:08 +0000 |
commit | adf18305521dc87c4ca1aee82e910ff8e22199cc (patch) | |
tree | cd5a249a88b447f76e25d49e81420389c8bdcbeb | |
parent | 4d736b1054ad4d4f7d25d9946f0a999960b091ae (diff) | |
download | gnunet-adf18305521dc87c4ca1aee82e910ff8e22199cc.tar.gz gnunet-adf18305521dc87c4ca1aee82e910ff8e22199cc.zip |
changes
-rw-r--r-- | src/ats/gnunet-service-ats_addresses_mlp.c | 50 |
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 | |||
1612 | GAS_mlp_address_add (void *solver, struct GNUNET_CONTAINER_MultiHashMap * addresses, struct ATS_Address *address) | 1645 | GAS_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; |