babel.h 8.63 KB
Newer Older
1 2 3 4
/*
 *	BIRD -- The Babel protocol
 *
 *	Copyright (c) 2015--2016 Toke Hoiland-Jorgensen
5 6
 * 	(c) 2016--2017 Ondrej Zajicek <santiago@crfreenet.org>
 *	(c) 2016--2017 CZ.NIC z.s.p.o.
7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
 *
 *	Can be freely distributed and used under the terms of the GNU GPL.
 *
 *	This file contains the data structures used by Babel.
 */

#ifndef _BIRD_BABEL_H_
#define _BIRD_BABEL_H_

#include "nest/bird.h"
#include "nest/cli.h"
#include "nest/iface.h"
#include "nest/route.h"
#include "nest/protocol.h"
#include "nest/locks.h"
#include "lib/resource.h"
#include "lib/lists.h"
#include "lib/socket.h"
#include "lib/string.h"
26
#include "sysdep/unix/timer.h"
27 28 29 30 31 32 33 34 35 36

#define EA_BABEL_METRIC		EA_CODE(EAP_BABEL, 0)
#define EA_BABEL_ROUTER_ID	EA_CODE(EAP_BABEL, 1)

#define BABEL_MAGIC		42
#define BABEL_VERSION		2
#define BABEL_PORT		6696
#define BABEL_INFINITY		0xFFFF


37 38
#define BABEL_HELLO_INTERVAL_WIRED	(4 S_)	/* Default hello intervals in seconds */
#define BABEL_HELLO_INTERVAL_WIRELESS	(4 S_)
39
#define BABEL_HELLO_LIMIT		12
40 41
#define BABEL_UPDATE_INTERVAL_FACTOR	4
#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 45
#define BABEL_HELLO_EXPIRY_FACTOR(X)	((btime)(X)*3/2)	/* 1.5 */
#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 48
#define BABEL_SEQNO_REQUEST_RETRY	4
#define BABEL_SEQNO_REQUEST_EXPIRY	(2 S_)
49
#define BABEL_GARBAGE_INTERVAL		(300 S_)
50 51 52
#define BABEL_RXCOST_WIRED		96
#define BABEL_RXCOST_WIRELESS		256
#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 57 58
#define BABEL_TIME_UNITS		10000	/* On-wire times are counted in centiseconds */
#define BABEL_MIN_INTERVAL		(0x0001 * BABEL_TIME_UNITS)
#define BABEL_MAX_INTERVAL		(0xFFFF * BABEL_TIME_UNITS)
59

60
#define BABEL_OVERHEAD		(IP6_HEADER_LENGTH+UDP_HEADER_LENGTH)
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
#define BABEL_MIN_MTU		(512 + BABEL_OVERHEAD)


enum babel_tlv_type {
  BABEL_TLV_PAD1		= 0,
  BABEL_TLV_PADN		= 1,
  BABEL_TLV_ACK_REQ		= 2,
  BABEL_TLV_ACK			= 3,
  BABEL_TLV_HELLO		= 4,
  BABEL_TLV_IHU 		= 5,
  BABEL_TLV_ROUTER_ID		= 6,
  BABEL_TLV_NEXT_HOP		= 7,
  BABEL_TLV_UPDATE		= 8,
  BABEL_TLV_ROUTE_REQUEST	= 9,
  BABEL_TLV_SEQNO_REQUEST	= 10,
  /* extensions - not implemented
  BABEL_TLV_TS_PC		= 11,
  BABEL_TLV_HMAC		= 12,
  BABEL_TLV_SS_UPDATE		= 13,
  BABEL_TLV_SS_REQUEST		= 14,
  BABEL_TLV_SS_SEQNO_REQUEST	= 15,
  */
  BABEL_TLV_MAX
};

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

91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109
enum babel_iface_type {
  /* In practice, UNDEF and WIRED give equivalent behaviour */
  BABEL_IFACE_TYPE_UNDEF	= 0,
  BABEL_IFACE_TYPE_WIRED	= 1,
  BABEL_IFACE_TYPE_WIRELESS	= 2,
  BABEL_IFACE_TYPE_MAX
};

enum babel_ae_type {
  BABEL_AE_WILDCARD		= 0,
  BABEL_AE_IP4			= 1,
  BABEL_AE_IP6			= 2,
  BABEL_AE_IP6_LL		= 3,
  BABEL_AE_MAX
};


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

struct babel_iface_config {
  struct iface_patt i;

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

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

  ip_addr next_hop_ip4;
  ip_addr next_hop_ip6;
133 134 135 136 137
};

struct babel_proto {
  struct proto p;
  timer *timer;
138 139 140 141 142 143
  struct fib ip4_rtable;
  struct fib ip6_rtable;

  struct channel *ip4_channel;
  struct channel *ip6_channel;

144 145 146
  list interfaces;			/* Interfaces we really know about (struct babel_iface) */
  u64 router_id;
  u16 update_seqno;			/* To be increased on request */
147
  u8 update_seqno_inc;			/* Request for update_seqno increase */
148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171
  u8 triggered;				/* For triggering global updates */

  slab *route_slab;
  slab *source_slab;
  slab *msg_slab;
  slab *seqno_slab;

  struct tbf log_pkt_tbf;		/* TBF for packet messages */
};

struct babel_iface {
  node n;

  struct babel_proto *proto;
  struct iface *iface;

  struct babel_iface_config *cf;

  u8 up;

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

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

180 181 182 183
  btime next_hello;
  btime next_regular;
  btime next_triggered;
  btime want_triggered;
184 185 186 187 188 189 190 191 192 193

  timer *timer;
  event *send_event;
};

struct babel_neighbor {
  node n;
  struct babel_iface *ifa;

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

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

struct babel_source {
  node n;

  u64 router_id;
  u16 seqno;
  u16 metric;
216
  btime expires;
217 218 219 220 221 222 223 224
};

struct babel_route {
  node n;
  node neigh_route;
  struct babel_entry    *e;
  struct babel_neighbor *neigh;

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

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

245
struct babel_entry {
246
  struct babel_route *selected;
247 248

  list routes;				/* Routes for this prefix (struct babel_route) */
249 250 251 252 253 254 255 256 257
  list sources;				/* Source entries for this prefix (struct babel_source). */
  list requests;

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

  struct fib_node n;
260 261
};

262 263 264
#define BABEL_ENTRY_DUMMY	0	/* No outgoing route */
#define BABEL_ENTRY_VALID	1	/* Valid outgoing route */
#define BABEL_ENTRY_STALE	2	/* Stale outgoing route, waiting for GC */
265 266 267 268 269 270 271 272 273


/*
 *	Internal TLV messages
 */

struct babel_msg_ack_req {
  u8 type;
  u16 nonce;
274
  uint interval;
275 276 277 278 279 280 281 282 283 284 285
  ip_addr sender;
};

struct babel_msg_ack {
  u8 type;
  u16 nonce;
};

struct babel_msg_hello {
  u8 type;
  u16 seqno;
286
  uint interval;
287 288 289 290 291 292 293
  ip_addr sender;
};

struct babel_msg_ihu {
  u8 type;
  u8 ae;
  u16 rxcost;
294
  uint interval;
295 296 297 298 299 300
  ip_addr addr;
  ip_addr sender;
};

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

struct babel_msg_route_request {
  u8 type;
  u8 full;
314
  net_addr net;
315 316 317 318 319
};

struct babel_msg_seqno_request {
  u8 type;
  u8 hop_count;
320
  u16 seqno;
321
  u64 router_id;
322
  net_addr net;
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
  ip_addr sender;
};

union babel_msg {
  u8 type;
  struct babel_msg_ack_req ack_req;
  struct babel_msg_ack ack;
  struct babel_msg_hello hello;
  struct babel_msg_ihu ihu;
  struct babel_msg_update update;
  struct babel_msg_route_request route_request;
  struct babel_msg_seqno_request seqno_request;
};

struct babel_msg_node {
  node n;
  union babel_msg msg;
};


/* babel.c */
void babel_handle_ack_req(union babel_msg *msg, struct babel_iface *ifa);
void babel_handle_ack(union babel_msg *msg, struct babel_iface *ifa);
void babel_handle_hello(union babel_msg *msg, struct babel_iface *ifa);
void babel_handle_ihu(union babel_msg *msg, struct babel_iface *ifa);
void babel_handle_router_id(union babel_msg *msg, struct babel_iface *ifa);
void babel_handle_update(union babel_msg *msg, struct babel_iface *ifa);
void babel_handle_route_request(union babel_msg *msg, struct babel_iface *ifa);
void babel_handle_seqno_request(union babel_msg *msg, struct babel_iface *ifa);

void babel_show_interfaces(struct proto *P, char *iff);
void babel_show_neighbors(struct proto *P, char *iff);
void babel_show_entries(struct proto *P);
356
void babel_show_routes(struct proto *P);
357 358 359 360 361 362 363 364 365

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


#endif