Statistics
| Branch: | Revision:

iof-bird / bird-2.0.1 / proto / babel / babel.h @ 6b3f1a54

History | View | Annotate | Download (8.62 KB)

1
/*
2
 *        BIRD -- The Babel protocol
3
 *
4
 *        Copyright (c) 2015--2016 Toke Hoiland-Jorgensen
5
 *         (c) 2016--2017 Ondrej Zajicek <santiago@crfreenet.org>
6
 *        (c) 2016--2017 CZ.NIC z.s.p.o.
7
 *
8
 *        Can be freely distributed and used under the terms of the GNU GPL.
9
 *
10
 *        This file contains the data structures used by Babel.
11
 */
12

    
13
#ifndef _BIRD_BABEL_H_
14
#define _BIRD_BABEL_H_
15

    
16
#include "nest/bird.h"
17
#include "nest/cli.h"
18
#include "nest/iface.h"
19
#include "nest/route.h"
20
#include "nest/protocol.h"
21
#include "nest/locks.h"
22
#include "lib/resource.h"
23
#include "lib/lists.h"
24
#include "lib/socket.h"
25
#include "lib/string.h"
26
#include "lib/timer.h"
27

    
28
#define EA_BABEL_METRIC                EA_CODE(EAP_BABEL, 0)
29
#define EA_BABEL_ROUTER_ID        EA_CODE(EAP_BABEL, 1)
30

    
31
#define BABEL_MAGIC                42
32
#define BABEL_VERSION                2
33
#define BABEL_PORT                6696
34
#define BABEL_INFINITY                0xFFFF
35

    
36

    
37
#define BABEL_HELLO_INTERVAL_WIRED        (4 S_)        /* Default hello intervals in seconds */
38
#define BABEL_HELLO_INTERVAL_WIRELESS        (4 S_)
39
#define BABEL_HELLO_LIMIT                12
40
#define BABEL_UPDATE_INTERVAL_FACTOR        4
41
#define BABEL_IHU_INTERVAL_FACTOR        3
42
#define BABEL_HOLD_TIME_FACTOR                4        /* How long we keep unreachable route relative to update interval */
43
#define BABEL_IHU_EXPIRY_FACTOR(X)        ((btime)(X)*7/2)        /* 3.5 */
44
#define BABEL_HELLO_EXPIRY_FACTOR(X)        ((btime)(X)*3/2)        /* 1.5 */
45
#define BABEL_ROUTE_EXPIRY_FACTOR(X)        ((btime)(X)*7/2)        /* 3.5 */
46
#define BABEL_ROUTE_REFRESH_FACTOR(X)        ((btime)(X)*5/2)        /* 2.5 */
47
#define BABEL_SEQNO_REQUEST_RETRY        4
48
#define BABEL_SEQNO_REQUEST_EXPIRY        (2 S_)
49
#define BABEL_GARBAGE_INTERVAL                (300 S_)
50
#define BABEL_RXCOST_WIRED                96
51
#define BABEL_RXCOST_WIRELESS                256
52
#define BABEL_INITIAL_HOP_COUNT                255
53
#define BABEL_MAX_SEND_INTERVAL                5        /* Unused ? */
54

    
55
/* Max interval that will not overflow when carried as 16-bit centiseconds */
56
#define BABEL_TIME_UNITS                10000        /* On-wire times are counted in centiseconds */
57
#define BABEL_MIN_INTERVAL                (0x0001 * BABEL_TIME_UNITS)
58
#define BABEL_MAX_INTERVAL                (0xFFFF * BABEL_TIME_UNITS)
59

    
60
#define BABEL_OVERHEAD                (IP6_HEADER_LENGTH+UDP_HEADER_LENGTH)
61
#define BABEL_MIN_MTU                (512 + BABEL_OVERHEAD)
62

    
63

    
64
enum babel_tlv_type {
65
  BABEL_TLV_PAD1                = 0,
66
  BABEL_TLV_PADN                = 1,
67
  BABEL_TLV_ACK_REQ                = 2,
68
  BABEL_TLV_ACK                        = 3,
69
  BABEL_TLV_HELLO                = 4,
70
  BABEL_TLV_IHU                 = 5,
71
  BABEL_TLV_ROUTER_ID                = 6,
72
  BABEL_TLV_NEXT_HOP                = 7,
73
  BABEL_TLV_UPDATE                = 8,
74
  BABEL_TLV_ROUTE_REQUEST        = 9,
75
  BABEL_TLV_SEQNO_REQUEST        = 10,
76
  /* extensions - not implemented
77
  BABEL_TLV_TS_PC                = 11,
78
  BABEL_TLV_HMAC                = 12,
79
  BABEL_TLV_SS_UPDATE                = 13,
80
  BABEL_TLV_SS_REQUEST                = 14,
81
  BABEL_TLV_SS_SEQNO_REQUEST        = 15,
82
  */
83
  BABEL_TLV_MAX
84
};
85

    
86
enum babel_subtlv_type {
87
  BABEL_SUBTLV_PAD1                = 0,
88
  BABEL_SUBTLV_PADN                = 1
89
};
90

    
91
enum babel_iface_type {
92
  /* In practice, UNDEF and WIRED give equivalent behaviour */
93
  BABEL_IFACE_TYPE_UNDEF        = 0,
94
  BABEL_IFACE_TYPE_WIRED        = 1,
95
  BABEL_IFACE_TYPE_WIRELESS        = 2,
96
  BABEL_IFACE_TYPE_MAX
97
};
98

    
99
enum babel_ae_type {
100
  BABEL_AE_WILDCARD                = 0,
101
  BABEL_AE_IP4                        = 1,
102
  BABEL_AE_IP6                        = 2,
103
  BABEL_AE_IP6_LL                = 3,
104
  BABEL_AE_MAX
105
};
106

    
107

    
108
struct babel_config {
109
  struct proto_config c;
110
  list iface_list;                        /* List of iface configs (struct babel_iface_config) */
111
  uint hold_time;                        /* Time to hold stale entries and unreachable routes */
112
};
113

    
114
struct babel_iface_config {
115
  struct iface_patt i;
116

    
117
  u16 rxcost;
118
  u8 type;
119
  u8 limit;                                /* Minimum number of Hellos to keep link up */
120
  u8 check_link;
121
  uint port;
122
  uint hello_interval;                        /* Hello interval, in us */
123
  uint ihu_interval;                        /* IHU interval, in us */
124
  uint update_interval;                        /* Update interval, in us */
125

    
126
  u16 rx_buffer;                        /* RX buffer size, 0 for MTU */
127
  u16 tx_length;                        /* TX packet length limit (including headers), 0 for MTU */
128
  int tx_tos;
129
  int tx_priority;
130

    
131
  ip_addr next_hop_ip4;
132
  ip_addr next_hop_ip6;
133
};
134

    
135
struct babel_proto {
136
  struct proto p;
137
  timer *timer;
138
  struct fib ip4_rtable;
139
  struct fib ip6_rtable;
140

    
141
  struct channel *ip4_channel;
142
  struct channel *ip6_channel;
143

    
144
  list interfaces;                        /* Interfaces we really know about (struct babel_iface) */
145
  u64 router_id;
146
  u16 update_seqno;                        /* To be increased on request */
147
  u8 update_seqno_inc;                        /* Request for update_seqno increase */
148
  u8 triggered;                                /* For triggering global updates */
149

    
150
  slab *route_slab;
151
  slab *source_slab;
152
  slab *msg_slab;
153
  slab *seqno_slab;
154

    
155
  struct tbf log_pkt_tbf;                /* TBF for packet messages */
156
};
157

    
158
struct babel_iface {
159
  node n;
160

    
161
  struct babel_proto *proto;
162
  struct iface *iface;
163

    
164
  struct babel_iface_config *cf;
165

    
166
  u8 up;
167

    
168
  pool *pool;
169
  char *ifname;
170
  sock *sk;
171
  ip_addr addr;
172
  ip_addr next_hop_ip4;
173
  ip_addr next_hop_ip6;
174
  int tx_length;
175
  list neigh_list;                        /* List of neighbors seen on this iface (struct babel_neighbor) */
176
  list msg_queue;
177

    
178
  u16 hello_seqno;                        /* To be increased on each hello */
179

    
180
  btime next_hello;
181
  btime next_regular;
182
  btime next_triggered;
183
  btime want_triggered;
184

    
185
  timer *timer;
186
  event *send_event;
187
};
188

    
189
struct babel_neighbor {
190
  node n;
191
  struct babel_iface *ifa;
192

    
193
  ip_addr addr;
194
  uint uc;                                /* Reference counter for seqno requests */
195
  u16 rxcost;                                /* Sent in last IHU */
196
  u16 txcost;                                /* Received in last IHU */
197
  u16 cost;                                /* Computed neighbor cost */
198
  s8 ihu_cnt;                                /* IHU countdown, 0 to send it */
199
  u8 hello_cnt;
200
  u16 hello_map;
201
  u16 next_hello_seqno;
202
  uint last_hello_int;
203
  /* expiry timers */
204
  btime hello_expiry;
205
  btime ihu_expiry;
206

    
207
  list routes;                                /* Routes this neighbour has sent us (struct babel_route) */
208
};
209

    
210
struct babel_source {
211
  node n;
212

    
213
  u64 router_id;
214
  u16 seqno;
215
  u16 metric;
216
  btime expires;
217
};
218

    
219
struct babel_route {
220
  node n;
221
  node neigh_route;
222
  struct babel_entry    *e;
223
  struct babel_neighbor *neigh;
224

    
225
  u8 feasible;
226
  u16 seqno;
227
  u16 metric;
228
  u16 advert_metric;
229
  u64 router_id;
230
  ip_addr next_hop;
231
  btime refresh_time;
232
  btime expires;
233
};
234

    
235
struct babel_seqno_request {
236
  node n;
237
  u64 router_id;
238
  u16 seqno;
239
  u8 hop_count;
240
  u8 count;
241
  btime expires;
242
  struct babel_neighbor *nbr;
243
};
244

    
245
struct babel_entry {
246
  struct babel_route *selected;
247

    
248
  list routes;                                /* Routes for this prefix (struct babel_route) */
249
  list sources;                                /* Source entries for this prefix (struct babel_source). */
250
  list requests;
251

    
252
  u8 valid;                                /* Entry validity state (BABEL_ENTRY_*) */
253
  u8 unreachable;                        /* Unreachable route is announced */
254
  u16 seqno;                                /* Outgoing seqno */
255
  u16 metric;                                /* Outgoing metric */
256
  u64 router_id;                        /* Outgoing router ID */
257
  btime updated;                        /* Last change of outgoing rte, for triggered updates */
258

    
259
  struct fib_node n;
260
};
261

    
262
#define BABEL_ENTRY_DUMMY        0        /* No outgoing route */
263
#define BABEL_ENTRY_VALID        1        /* Valid outgoing route */
264
#define BABEL_ENTRY_STALE        2        /* Stale outgoing route, waiting for GC */
265

    
266

    
267
/*
268
 *        Internal TLV messages
269
 */
270

    
271
struct babel_msg_ack_req {
272
  u8 type;
273
  u16 nonce;
274
  uint interval;
275
  ip_addr sender;
276
};
277

    
278
struct babel_msg_ack {
279
  u8 type;
280
  u16 nonce;
281
};
282

    
283
struct babel_msg_hello {
284
  u8 type;
285
  u16 seqno;
286
  uint interval;
287
  ip_addr sender;
288
};
289

    
290
struct babel_msg_ihu {
291
  u8 type;
292
  u8 ae;
293
  u16 rxcost;
294
  uint interval;
295
  ip_addr addr;
296
  ip_addr sender;
297
};
298

    
299
struct babel_msg_update {
300
  u8 type;
301
  u8 wildcard;
302
  uint interval;
303
  u16 seqno;
304
  u16 metric;
305
  u64 router_id;
306
  net_addr net;
307
  ip_addr next_hop;
308
  ip_addr sender;
309
};
310

    
311
struct babel_msg_route_request {
312
  u8 type;
313
  u8 full;
314
  net_addr net;
315
};
316

    
317
struct babel_msg_seqno_request {
318
  u8 type;
319
  u8 hop_count;
320
  u16 seqno;
321
  u64 router_id;
322
  net_addr net;
323
  ip_addr sender;
324
};
325

    
326
union babel_msg {
327
  u8 type;
328
  struct babel_msg_ack_req ack_req;
329
  struct babel_msg_ack ack;
330
  struct babel_msg_hello hello;
331
  struct babel_msg_ihu ihu;
332
  struct babel_msg_update update;
333
  struct babel_msg_route_request route_request;
334
  struct babel_msg_seqno_request seqno_request;
335
};
336

    
337
struct babel_msg_node {
338
  node n;
339
  union babel_msg msg;
340
};
341

    
342

    
343
/* babel.c */
344
void babel_handle_ack_req(union babel_msg *msg, struct babel_iface *ifa);
345
void babel_handle_ack(union babel_msg *msg, struct babel_iface *ifa);
346
void babel_handle_hello(union babel_msg *msg, struct babel_iface *ifa);
347
void babel_handle_ihu(union babel_msg *msg, struct babel_iface *ifa);
348
void babel_handle_router_id(union babel_msg *msg, struct babel_iface *ifa);
349
void babel_handle_update(union babel_msg *msg, struct babel_iface *ifa);
350
void babel_handle_route_request(union babel_msg *msg, struct babel_iface *ifa);
351
void babel_handle_seqno_request(union babel_msg *msg, struct babel_iface *ifa);
352

    
353
void babel_show_interfaces(struct proto *P, char *iff);
354
void babel_show_neighbors(struct proto *P, char *iff);
355
void babel_show_entries(struct proto *P);
356
void babel_show_routes(struct proto *P);
357

    
358
/* packets.c */
359
void babel_enqueue(union babel_msg *msg, struct babel_iface *ifa);
360
void babel_send_unicast(union babel_msg *msg, struct babel_iface *ifa, ip_addr dest);
361
int babel_open_socket(struct babel_iface *ifa);
362
void babel_send_queue(void *arg);
363

    
364

    
365
#endif