babel.h 9.04 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 "lib/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
enum babel_subtlv_type {
  BABEL_SUBTLV_PAD1		= 0,
88 89 90 91
  BABEL_SUBTLV_PADN		= 1,

  /* Mandatory subtlvs */
  BABEL_SUBTLV_SOURCE_PREFIX    = 128,
92 93
};

94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112
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;
113 114
  list iface_list;			/* List of iface configs (struct babel_iface_config) */
  uint hold_time;			/* Time to hold stale entries and unreachable routes */
115
  u8 randomize_router_id;
116 117 118

  struct channel_config *ip4_channel;
  struct channel_config *ip6_channel;
119 120 121 122 123 124 125
};

struct babel_iface_config {
  struct iface_patt i;

  u16 rxcost;
  u8 type;
126
  u8 limit;				/* Minimum number of Hellos to keep link up */
127
  u8 check_link;
128
  uint port;
129 130 131
  uint hello_interval;			/* Hello interval, in us */
  uint ihu_interval;			/* IHU interval, in us */
  uint update_interval;			/* Update interval, in us */
132 133 134 135 136

  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;
137 138 139

  ip_addr next_hop_ip4;
  ip_addr next_hop_ip6;
140 141 142 143 144
};

struct babel_proto {
  struct proto p;
  timer *timer;
145 146 147 148 149 150
  struct fib ip4_rtable;
  struct fib ip6_rtable;

  struct channel *ip4_channel;
  struct channel *ip6_channel;

151 152 153
  list interfaces;			/* Interfaces we really know about (struct babel_iface) */
  u64 router_id;
  u16 update_seqno;			/* To be increased on request */
154
  u8 update_seqno_inc;			/* Request for update_seqno increase */
155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178
  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;
179 180
  ip_addr next_hop_ip4;
  ip_addr next_hop_ip6;
181 182 183 184 185 186
  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 */

187 188 189 190
  btime next_hello;
  btime next_regular;
  btime next_triggered;
  btime want_triggered;
191 192 193 194 195 196 197 198 199 200

  timer *timer;
  event *send_event;
};

struct babel_neighbor {
  node n;
  struct babel_iface *ifa;

  ip_addr addr;
201
  uint uc;				/* Reference counter for seqno requests */
202 203 204 205
  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 */
206 207 208
  u8 hello_cnt;
  u16 hello_map;
  u16 next_hello_seqno;
209
  uint last_hello_int;
210
  /* expiry timers */
211 212
  btime hello_expiry;
  btime ihu_expiry;
213 214 215 216 217 218 219 220 221 222

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

struct babel_source {
  node n;

  u64 router_id;
  u16 seqno;
  u16 metric;
223
  btime expires;
224 225 226 227 228 229 230 231
};

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

232
  u8 feasible;
233 234
  u16 seqno;
  u16 metric;
235
  u16 advert_metric;
236 237
  u64 router_id;
  ip_addr next_hop;
238 239
  btime refresh_time;
  btime expires;
240 241
};

242 243 244 245 246 247 248 249 250 251
struct babel_seqno_request {
  node n;
  u64 router_id;
  u16 seqno;
  u8 hop_count;
  u8 count;
  btime expires;
  struct babel_neighbor *nbr;
};

252
struct babel_entry {
253
  struct babel_route *selected;
254 255

  list routes;				/* Routes for this prefix (struct babel_route) */
256 257 258 259 260 261 262 263 264
  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 */
265 266

  struct fib_node n;
267 268
};

269 270 271
#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 */
272 273 274 275 276 277 278 279 280


/*
 *	Internal TLV messages
 */

struct babel_msg_ack_req {
  u8 type;
  u16 nonce;
281
  uint interval;
282 283 284 285 286 287 288 289 290 291 292
  ip_addr sender;
};

struct babel_msg_ack {
  u8 type;
  u16 nonce;
};

struct babel_msg_hello {
  u8 type;
  u16 seqno;
293
  uint interval;
294 295 296 297 298 299 300
  ip_addr sender;
};

struct babel_msg_ihu {
  u8 type;
  u8 ae;
  u16 rxcost;
301
  uint interval;
302 303 304 305 306 307
  ip_addr addr;
  ip_addr sender;
};

struct babel_msg_update {
  u8 type;
308
  u8 wildcard;
309
  uint interval;
310 311 312
  u16 seqno;
  u16 metric;
  u64 router_id;
313 314 315 316
  union {
    net_addr net;
    net_addr_ip6_sadr net_sadr;
  };
317 318 319 320 321 322 323
  ip_addr next_hop;
  ip_addr sender;
};

struct babel_msg_route_request {
  u8 type;
  u8 full;
324 325 326 327
  union {
    net_addr net;
    net_addr_ip6_sadr net_sadr;
  };
328 329 330 331 332
};

struct babel_msg_seqno_request {
  u8 type;
  u8 hop_count;
333
  u16 seqno;
334
  u64 router_id;
335 336 337 338
  union {
    net_addr net;
    net_addr_ip6_sadr net_sadr;
  };
339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357
  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;
};

358 359
static inline int babel_sadr_enabled(struct babel_proto *p)
{ return p->ip6_rtable.addr_type == NET_IP6_SADR; }
360 361 362 363 364 365 366 367 368 369 370 371 372 373

/* 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);
374
void babel_show_routes(struct proto *P);
375 376 377 378 379 380 381 382 383

/* 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