8e67e159d8d03eacd4fa4085eb27d8c1a9e8247c
[olsrd.git] / README-metrics.txt
1
2
3 How to write your own metric plugin
4 ===================================
5 (by Leon Aaron Kaplan <aaron@lo-res.org> and Henning Rogge <rogge@fgan.de>)
6
7 Overview
8 =========
9 The idea behind the lq_plugin_* is that you can write your own Link Quality (LQ) 
10 metric mostly independant of the main OLSR code.
11 What is a metric? A metric is a notion of "distance" between nodes in the mesh.
12 Mobile adhoc network (MANET) research identified the area of finding proper metrics
13 for a MANET as one of the most important routing decisions.
14 A metric basically determines the path that packets will take.
15 The Shortest Path First (SPF, also sometimes called Dijkstra Algorithm) will chose
16 the shortest sum of all possible paths. 
17 So what paths do we want to chose in wifi MANET networks?
18 In general we want to have a little collisions as possible since 802.11a/b/g is a 
19 broadcast medium by nature. When you compare the very old ethernet systems
20 (coax cable, http://en.wikipedia.org/wiki/10BASE2) you can observe that at a certain
21 percentage of cable utilization (as low as 40%), you would get many collisions (since the
22 coax cable is a broadcast medium just as WIFI!) and the total throughput would
23 collapse to nearly zero.
24
25 Another choice for metrics might be signal strenght.
26
27 Currently OLSR.org as of 2008/10 implements the following metric:
28  - RFC 3626 conforming hop count (each link has the metric value "1")
29  - ETX_default_ff (ETX from MIT roofnet, with FunkFeuer.at extensions)
30  - ETX_default_float (ETX with floating point arithmetic)
31  - ETX_default_fpm   (ETX with fixed point maths (integer). Much faster on small embedded devices! Courtesy of Sven-Ola Tuecke)
32   
33
34 How to get started
35 ==================
36
37 Start by reading src/lq_plugin.c and lq_plugin.h
38
39 struct lq_handler:
40
41 is a pseudo C++ structure ;-)
42 there is a pointer table to functions so that the plugin system knows which 
43 functions it should jump to.
44
45 struct lq_handler {
46  ...
47   size_t hello_lq_size;  // number of bytes we need per hello in the hello DB for this specific metric. This has nothing to do wht is being sent over the net. This is only so that you can use the structure itself to store your metric data
48   size_t tc_lq_size;
49 };
50
51 Almost all functions accept a void pointer. This now points to the beginning of the custom memory area that you allocated with the tc_lq_size or hello_lq_size  above.
52
53
54 Now... if you want to write your own metric then you must define your own struct lq_handler and pass that variable to 
55
56 void register_lq_handler(struct lq_handler *handler, const char *name);
57
58
59 for example:
60   struct lq_handler my_lq_metric;
61
62   ... // init my_lq_metric fully (every function must be assigned)
63
64   register_lq_handler(&my_lq_metric, "my_lq_metric");
65
66
67 for another example, take a look at lq_plugin_default_float.[ch]
68 There it is done like this:
69
70 /* Default lq plugin settings */
71 struct lq_handler lq_etx_float_handler = {
72   &default_lq_initialize_float,
73   
74   &default_lq_calc_cost_float,
75   &default_lq_calc_cost_float,
76   
77   &default_lq_is_relevant_costchange_float,
78   
79   &default_lq_packet_loss_worker_float,
80   &default_lq_memorize_foreign_hello_float,
81   &default_lq_copy_link2tc_float,
82   &default_lq_clear_float,
83   &default_lq_clear_float,
84
85 ....
86   sizeof(struct default_lq_float),
87   sizeof(struct default_lq_float)
88 };
89
90 This means , we use the sizeof(struct default_lq_float) as extra memory space in the hello database and a sizeof(struct default_lq_fload) as extra space in the TC database.
91 The other entries here are pointers to functions which are defined in the .h file.
92
93
94
95
96 Now lets have a look at the functions.
97
98   void (*initialize)(void);
99 -----------------------------
100   This callback will be called when the olsrd.conf selects this routing 
101   metric plugin.
102   for example: 
103   #LinkQualityAlgorithm    "etx_ff"
104   
105   The etx_ff initialize function for example starts some timers and it reserves a callback which is triggered for each packet.
106   In general you can use any initialization code in this callback.
107
108   olsr_linkcost(*calc_hello_cost) (const void *lq);
109 ---------------------------------
110   This callback will be called whenever a packet is processed.
111   Called after:
112   Called before:
113
114   You will get a pointer to your part of the hello database and your plugin 
115   is supposed to generate a hello cost in the standard format from the internal representation:
116   the core format is a 32 bit unsigned integer . This then is used for 
117   adding up the costs in the Dijkstra calculation.
118   So be sure that you do not use values greater than 2^24 . Otherwise for 
119   very long routes (256 hops) this will then add up in the internal representation so that there will be integer overflows. So stay below 2^24 (*).
120   The base of the cost is your business. For example, to represent fixed point arithmetic you might multiply your (float) hello costs by 256 and treat the least significant byte as the digits behind the point.
121   
122   (*) or actually even better: us the constant LINK_COST_BROKEN from lq_plugin.h
123
124
125   olsr_linkcost(*calc_tc_cost) (const void *lq);
126 ---------------------------------
127   This callback will be called whenever a packet is processed.
128   Called after:
129   Called before:
130
131   same as for calc_hello_cost but just for TC costs and not for hellos
132
133
134   bool(*is_relevant_costchange) (olsr_linkcost c1, olsr_linkcost c2);
135 ---------------------------------
136   This callback is called after the main loop whenever the core has 
137   to decide if a new dijkstra needs to be calculated. In principle for every 
138   packet.
139
140   If a link quality does only change slightly, there will be no recalculation 
141   of the Dijkstra algorithm which costs a lot of CPU. 
142   Since only the plugin knows the range of the link quality values, only
143   the plugin can decide if the cost change is relevant enough.
144
145   return values:
146     true  
147     false 
148
149
150   olsr_linkcost(*packet_loss_handler) (struct link_entry * entry, void *lq,
151                        bool lost);
152 ---------------------------------
153   This callback is called 
154
155
156   returns:
157
158   void (*memorize_foreign_hello) (void *local, void *foreign);
159 ---------------------------------
160   This callback is called when
161
162
163   void (*copy_link_lq_into_tc) (void *target, void *source);
164 ---------------------------------
165   This callback is called when Hello packet's LQ is copied over into a TC.
166   Since this can have a different representation, this function can be used 
167   to convert representations.
168
169   void (*clear_hello) (void *target);
170 ---------------------------------
171   This callback is called when
172
173   void (*clear_tc) (void *target);
174 ---------------------------------
175   This callback is called when
176
177   int (*serialize_hello_lq) (unsigned char *buff, void *lq);
178 ---------------------------------
179   This callback is called when
180   
181
182   int (*serialize_tc_lq) (unsigned char *buff, void *lq);
183 ---------------------------------
184   This callback is called when
185
186   void (*deserialize_hello_lq) (const uint8_t ** curr, void *lq);
187 ---------------------------------
188   This callback is called when
189
190   void (*deserialize_tc_lq) (const uint8_t ** curr, void *lq);
191 ---------------------------------
192   This callback is called whenever a packet needs to be deserialized (for every packet 
193   and there for every neighour in the TC)
194   
195   This function reads the lq information of a binary packet into a TC
196   
197   @param pointer to the current buffer pointer
198   @param pointer to 
199
200
201
202   const char *(*print_hello_lq) (void *ptr, char separator, struct lqtextbuffer * buffer);
203 ---------------------------------
204   This callback is called whenever any other part of the code wants to 
205   convert your internal metric representation of Hellos into a printable
206   version. So it can be called at any time
207
208   ptr is a void pointer to the link quality data in the Hello DB.
209   seperator is a character which is printed whenever there are multiple values (for example ',' or '/'
210   buffer is the buffer you want to sprintf into. Please do not forget to \0 terminate!
211
212   returns: the buffer
213   In case of errors: please return "error" as string. Because print_hello_lq
214   will often directly be put into a printf()
215
216
217   const char *(*print_tc_lq) (void *ptr, char separator, struct lqtextbuffer * buffer);
218 ---------------------------------
219   same as print_hello_lq
220
221   const char *(*print_cost) (olsr_linkcost cost, struct lqtextbuffer * buffer);
222 ---------------------------------
223   same as print_hello_lq. But for an arbitrary link cost.
224