-
Notifications
You must be signed in to change notification settings - Fork 78
/
gridroutetable.hh
386 lines (313 loc) · 13.4 KB
/
gridroutetable.hh
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
#ifndef GRIDROUTETABLE_HH
#define GRIDROUTETABLE_HH
/*
* =c
* GridRouteTable(TIMEOUT, PERIOD, JITTER, ETH, IP, GridGatewayInfo, LinkTracker, LinkStat [, I<KEYWORDS>])
*
* =s Grid
* Run DSDV-like local routing protocol
*
* =d
* Implements a DSDV-like loop-free routing protocol by originating
* routing messages based on its routing tables, and processing
* routing update messages from other nodes. Maintains an immediate
* neighbor table, and a multi-hop route table. Route entries are
* removed TIMEOUT milliseconds after being installed. PERIOD is the
* milliseconds between route broadcasts, randomly offset by up to
* JITTER milliseconds. ETH and IP describe this node's Grid
* addresses, and GW is the GridGatewayInfo element. LinkTracker
* and LinkStat are LinkTracker and LinkStat elements for the interface
* to which this GridRouteTable element is connected.
*
* Routing message entries are marked with both a sequence number
* (originated by the destination of the entry) and a real-time ttl.
* Entries with higher sequence numbers always supersede entries with
* lower sequence numbers. For entries with the same sequence number,
* the lower hop-count entry prevails. Entry ttls decrease while the
* entry resides in a node's routing table, as well as being decreased
* by a minimum amount when the route is propagated to another node.
* Thus an individual route entry will only propagate through the
* network for a finite amount of time. A route entry is not
* propagated if its ttl is less than the minimum decrement amount. A
* route is not accepted if its ttl is <= 0.
*
* New routes are advertised with even sequence numbers originated by
* the route destination (obtained from LR_HELLO messages); broken
* routes are advertised with odd sequence numbers formed by adding 1
* to the sequence number of the last known good route. Broken route
* advertisements are originally initiated when an immediate neighbor
* entry times out, and will always supersede the route they are
* concerned with; any new route will always supersede the previous
* broken route. When a node receives a broken route advertisement
* for a destination to which it knows a newer route, it kills the
* broken route advertisement and sends an advertisement for the the
* new route.
*
* Keyword arguments are:
*
* =over 8
*
* =item MAX_HOPS
*
* Integer. The maximum number of hops for which a route should
* propagate. The default number of hops is 3.
*
* =item LOGCHANNEL
*
* String. The name of the chatter channel to which route action log
* messages should be logged. Default channel is ``routelog''.
*
* =item METRIC
*
* String. The type of metric that should be used to compare two
* routes. Allowable values are: ``hopcount'',
* ``cumulative_delivery_rate'', ``min_delivery_rate'',
* ``min_sig_strength'', and ``min_sig_quality''. The default is to
* use hopcount.
*
* =item LOG
*
* GridLogger element. Object to log events to.
*
* =a
* SendGridHello, FixSrcLoc, SetGridChecksum, LookupLocalGridRoute, UpdateGridRoutes,
* LinkStat, LinkTracker, GridGatewayInfo, GridLogger */
#include <click/bighashmap.hh>
#include <click/etheraddress.hh>
#include <click/ipaddress.hh>
#include <elements/grid/gridgatewayinfo.hh>
#include <elements/grid/linktracker.hh>
#include <elements/grid/linkstat.hh>
#include "grid.hh"
#include "gridgenericrt.hh"
#include <click/timer.hh>
CLICK_DECLS
class GridLogger;
class GridRouteTable : public GridGenericRouteTable {
public:
// generic rt methods
bool current_gateway(RouteEntry &entry);
bool get_one_entry(const IPAddress &dest_ip, RouteEntry &entry);
void get_all_entries(Vector<RouteEntry> &vec);
public:
GridRouteTable() CLICK_COLD;
~GridRouteTable() CLICK_COLD;
const char *class_name() const override { return "GridRouteTable"; }
void *cast(const char *);
const char *port_count() const override { return PORTS_1_1; }
const char *processing() const override { return "h/h"; }
const char *flow_code() const override { return "x/y"; }
int configure(Vector<String> &, ErrorHandler *) CLICK_COLD;
int initialize(ErrorHandler *) CLICK_COLD;
virtual bool can_live_reconfigure() const { return false; }
Packet *simple_action(Packet *);
void add_handlers() CLICK_COLD;
private:
/*
* route table entry
*/
class RTEntry {
bool _init;
public:
IPAddress dest_ip; // IP address of this destination
EtherAddress dest_eth; // Eth of this destination; may be all 0s if we don't hear any ads...
IPAddress next_hop_ip; // IP address of next hop for this destination
EtherAddress next_hop_eth; // hardware address of next hop
private:
unsigned char _num_hops; // number of hops to dest
public:
unsigned char num_hops() const { check(); return _num_hops; }
void invalidate() {
check();
assert(_num_hops > 0 && !(_seq_no & 1));
_num_hops = 0; _seq_no++;
check();
}
struct grid_location loc; // location of dest, as contained in its route ads
unsigned short loc_err;
bool loc_good;
bool is_gateway;
private:
unsigned int _seq_no;
public:
unsigned int seq_no() const { check(); return _seq_no; }
unsigned int ttl; // msecs
int last_updated_jiffies; // last time this entry was updated
unsigned int metric; // generic metric -- routing code must interpret this as neccessary
bool metric_valid; /* metrics are invalid until updated to
incorporate the last hop's link, i.e. by
calling initialize_metric or
update_metric. */
RTEntry() :
_init(false), _num_hops(0), loc_good(false), is_gateway(false),
_seq_no(0), ttl(0), last_updated_jiffies(-1), metric_valid(false)
{ }
public:
RTEntry(IPAddress _dest_ip, IPAddress _next_hop_ip, EtherAddress _next_hop_eth,
unsigned char num_hops, grid_location _loc, unsigned short _loc_err,
bool _loc_good, bool _is_gateway, unsigned int seq_no, unsigned int _ttl,
unsigned int _last_updated_jiffies) :
_init(true), dest_ip(_dest_ip), next_hop_ip(_next_hop_ip),
next_hop_eth(_next_hop_eth), _num_hops(num_hops), loc(_loc),
loc_err(_loc_err), loc_good(_loc_good), is_gateway(_is_gateway),
_seq_no(seq_no), ttl(_ttl),
last_updated_jiffies(_last_updated_jiffies), metric_valid(false)
{ check(); }
/* constructor for 1-hop route entry, converting from net byte order */
RTEntry(IPAddress ip, EtherAddress eth, grid_hdr *gh, grid_hello *hlo,
unsigned int jiff) :
_init(true), dest_ip(ip), dest_eth(eth), next_hop_ip(ip), next_hop_eth(eth), _num_hops(1),
loc(gh->loc), loc_good(gh->loc_good), is_gateway(hlo->is_gateway),
last_updated_jiffies(jiff), metric_valid(false)
{
loc_err = ntohs(gh->loc_err);
_seq_no = ntohl(hlo->seq_no);
ttl = ntohl(hlo->ttl);
check();
}
/* constructor from grid_nbr_entry, converting from net byte order */
RTEntry(IPAddress ip, EtherAddress eth, grid_nbr_entry *nbr,
unsigned int jiff) :
_init(true), dest_ip(nbr->ip), next_hop_ip(ip), next_hop_eth(eth),
_num_hops(nbr->num_hops ? nbr->num_hops + 1 : 0), loc(nbr->loc), loc_good(nbr->loc_good),
is_gateway(nbr->is_gateway), last_updated_jiffies(jiff),
metric_valid(nbr->metric_valid)
{
loc_err = ntohs(nbr->loc_err);
_seq_no = ntohl(nbr->seq_no);
ttl = ntohl(nbr->ttl);
metric = ntohl(nbr->metric);
check();
}
/* copy data from this into nb, converting to net byte order */
void fill_in(grid_nbr_entry *nb, LinkStat *ls = 0);
void check() const { assert(_init); assert((_num_hops > 0) != (_seq_no & 1)); }
};
typedef HashMap<IPAddress, RTEntry> RTable;
typedef RTable::iterator RTIter;
/* the route table */
RTable _rtes;
void get_rtes(Vector<RTEntry> *retval);
private:
/* max time to keep an entry in RT */
int _timeout; // msecs, -1 if we are not timing out entries
unsigned int _timeout_jiffies;
/* route broadcast timing parameters */
int _period;
int _jitter;
GridGatewayInfo *_gw_info;
LinkTracker *_link_tracker;
LinkStat *_link_stat;
/* interval at which to check RT entries for expiry */
static const unsigned int EXPIRE_TIMER_PERIOD = 100; // msecs
/* extended logging */
ErrorHandler *_extended_logging_errh;
void log_route_table(); // print route table on 'routelog' chatter channel
/* binary logging */
GridLogger *_log;
unsigned int _dump_tick;
/* this node's addresses */
IPAddress _ip;
EtherAddress _eth;
/* latest sequence number for this node's route entry */
unsigned int _seq_no;
unsigned int _fake_seq_no;
unsigned int _bcast_count;
unsigned int _seq_delay;
/* local DSDV radius */
int _max_hops;
Timer _expire_timer;
Timer _hello_timer;
/* runs to expire route entries */
static void expire_hook(Timer *, void *);
/* expires routes; returns the expired routes */
Vector<RTEntry> expire_routes();
/* runs to broadcast route advertisements and triggered updates */
static void hello_hook(Timer *, void *);
/* send a route advertisement containing the entries in rte_info */
void send_routing_update(Vector<RTEntry> &rtes_to_send, bool update_seq = true, bool check_ttls = true);
static unsigned int decr_ttl(unsigned int ttl, unsigned int decr)
{ return (ttl > decr ? ttl - decr : 0); }
static int jiff_to_msec(int j)
{ return (j * 1000) / CLICK_HZ; }
static int msec_to_jiff(int m)
{ return (CLICK_HZ * m) / 1000; }
/* update route metric with the last hop from the advertising node */
void update_metric(RTEntry &);
/* initialize the metric for a 1-hop neighbor */
void init_metric(RTEntry &);
/* true iff first route's metric is preferable to second route's
metric -- note that this is a strict comparison, if the metrics
are equivalent, then the function returns false. this is
necessary to get stability, e.g. when using the hopcount metric */
bool metric_is_preferable(const RTEntry &, const RTEntry &);
/* true iff we should replace the first route with the second route */
bool should_replace_old_route(const RTEntry &, const RTEntry &);
static String print_rtes(Element *e, void *);
static String print_rtes_v(Element *e, void *);
static String print_nbrs(Element *e, void *);
static String print_nbrs_v(Element *e, void *);
static String print_ip(Element *e, void *);
static String print_eth(Element *e, void *);
static String print_links(Element *e, void *);
static String print_metric_type(Element *e, void *);
static int write_metric_type(const String &, Element *, void *, ErrorHandler *);
static String print_metric_range(Element *e, void *);
static int write_metric_range(const String &, Element *, void *, ErrorHandler *);
static String print_est_type(Element *e, void *);
static int write_est_type(const String &, Element *, void *, ErrorHandler *);
static String print_seq_delay(Element *e, void *);
static int write_seq_delay(const String &, Element *, void *, ErrorHandler *);
static String print_frozen(Element *e, void *);
static int write_frozen(const String &, Element *, void *, ErrorHandler *);
unsigned int qual_to_pct(int q);
unsigned int sig_to_pct(int s);
bool est_forward_delivery_rate(const IPAddress, double &);
bool est_reverse_delivery_rate(const IPAddress, double &);
enum MetricType {
MetricUnknown = -1,
MetricHopCount = 0, // unsigned int hop count
MetricCumulativeDeliveryRate, // unsigned int percentage (0-100)
MetricMinDeliveryRate, // unsigned int percentage (0-100)
MetricMinSigStrength, // unsigned int negative dBm. e.g. -40 dBm is 40
MetricMinSigQuality, // unsigned int ``quality''
MetricCumulativeQualPct, // unsigned int percentage (0-100) of range
MetricCumulativeSigPct, // unsigned int percentage (0-100) of range
MetricEstTxCount // unsigned int expected number of transmission * 100
};
static String metric_type_to_string(MetricType t);
static MetricType check_metric_type(const String &);
MetricType _metric_type;
/* top and bottom of ranges for qual/sig pct */
int _max_metric;
int _min_metric;
static const unsigned int _bad_metric = 7777777;
/* default ranges taken from experiments -- from approx 144 million received packets! */
/*
* +-------------+-------------+-------------+-------------+--------------+--------------+--------------+--------------+
* | min(signal) | max(signal) | std(signal) | avg(signal) | min(quality) | max(quality) | std(quality) | avg(quality) |
* +-------------+-------------+-------------+-------------+--------------+--------------+--------------+--------------+
* | -100 | -13 | 13.0719 | -69.8756 | 0 | 130 | 3.6859 | 6.7074 |
* +-------------+-------------+-------------+-------------+--------------+--------------+--------------+--------------+
*/
static const int _max_qual = 130;
static const int _min_qual = 0;
static const int _max_sig = -13;
static const int _min_sig = -100;
enum {
EstByQual = 0,
EstBySig,
EstBySigQual,
EstByMeas
};
unsigned int _est_type;
bool _frozen;
RouteEntry make_generic_rte(const RTEntry &rte) {
return RouteEntry(rte.dest_ip, rte.loc_good, rte.loc_err, rte.loc,
rte.next_hop_eth, rte.next_hop_ip,
0, // ignore interface number information
rte.seq_no(), rte.num_hops());
}
};
CLICK_ENDDECLS
#endif