April 2018 - Bird-users - Mailing Lists

[PATCH] babel: Use acknowledged retractions when losing a prefix
by Toke Høiland-Jørgensen 04 Apr '18

04 Apr '18

In order to prevent routing loops, Babel installs temporary blackhole routes to prefixes that expire or are otherwise lost. These blackhole routes are maintained for a while to ensure the route has been flushed from the whole network; the default hold time is 64 seconds. In the updated IETF version of Babel (rfc6126bis), an alternative procedure was added which replaces this hold time with an explicit acknowledgement procedure. This procedure simply consists of sending a retraction along with an acknowledgement request to all neighbours, and removing the blackhole route once all neighbours have acknowledged the retraction. As this usually happens pretty quickly, the hold time during which the route is blackholed is almost completely avoided. This patch implements the above behaviour. It adds a generic facility to the Babel protocol which allows for sending sequences of acknowledgement requests to a number of neighbours, and executing a callback function once all the requests have been ACKed. This facility is then used to implement the acknowledgement scheme when a route is lost. Signed-off-by: Toke Høiland-Jørgensen <toke(a)toke.dk> --- proto/babel/babel.c | 199 +++++++++++++++++++++++++++++++++++++++++++++++--- proto/babel/babel.h | 25 +++++++ proto/babel/packets.c | 71 +++++++++++++++++- 3 files changed, 283 insertions(+), 12 deletions(-) diff --git a/proto/babel/babel.c b/proto/babel/babel.c index 3cf8aaf0..3d235382 100644 --- a/proto/babel/babel.c +++ b/proto/babel/babel.c @@ -52,8 +52,10 @@ static void babel_select_route(struct babel_proto *p, struct babel_entry *e, str static inline void babel_announce_retraction(struct babel_proto *p, struct babel_entry *e); static void babel_send_route_request(struct babel_proto *p, struct babel_entry *e, struct babel_neighbor *n); static void babel_send_seqno_request(struct babel_proto *p, struct babel_entry *e, struct babel_seqno_request *sr); +static void babel_send_ack_sequence(struct babel_ack_sequence *seq); +static void babel_flush_outgoing_ack(struct babel_outgoing_ack_req *ack); static void babel_update_cost(struct babel_neighbor *n); -static inline void babel_kick_timer(struct babel_proto *p); +static inline void babel_kick_timer(struct babel_proto *p, btime interval); static inline void babel_iface_kick_timer(struct babel_iface *ifa); static inline void babel_lock_neighbor(struct babel_neighbor *nbr) @@ -428,6 +430,7 @@ babel_get_neighbor(struct babel_iface *ifa, ip_addr addr) nbr->txcost = BABEL_INFINITY; nbr->cost = BABEL_INFINITY; init_list(&nbr->routes); + init_list(&nbr->ack_reqs); babel_lock_neighbor(nbr); add_tail(&ifa->neigh_list, NODE nbr); @@ -438,6 +441,7 @@ static void babel_flush_neighbor(struct babel_proto *p, struct babel_neighbor *nbr) { struct babel_route *r; + struct babel_outgoing_ack_req *a; node *n; TRACE(D_EVENTS, "Removing neighbor %I on %s", nbr->addr, nbr->ifa->iface->name); @@ -449,6 +453,12 @@ babel_flush_neighbor(struct babel_proto *p, struct babel_neighbor *nbr) babel_flush_route(p, r); } + WALK_LIST_FIRST(n, nbr->ack_reqs) + { + a = SKIP_BACK(struct babel_outgoing_ack_req, neigh_ack, n); + babel_flush_outgoing_ack(a); + } + nbr->ifa = NULL; rem_node(NODE nbr); babel_unlock_neighbor(nbr); @@ -508,6 +518,69 @@ babel_expire_neighbors(struct babel_proto *p) } } +static void babel_flush_ack_seq(struct babel_ack_sequence *seq) +{ + struct babel_proto *p = seq->p; + struct babel_msg_node *msgn; + + rem_node(NODE seq); + + WALK_LIST_FIRST(msgn, seq->payload) + { + rem_node(NODE msgn); + sl_free(p->msg_slab, msgn); + } + + mb_free(seq); +} + +static int +babel_check_ack_seq(struct babel_ack_sequence *seq) +{ + if (EMPTY_LIST(seq->acks)) + { + seq->callback(seq); + babel_flush_ack_seq(seq); + return 1; + } + return 0; +} + +static void +babel_flush_outgoing_ack(struct babel_outgoing_ack_req *ack) +{ + struct babel_ack_sequence *seq = ack->seq; + rem_node(&ack->neigh_ack); + rem_node(NODE ack); + mb_free(ack); + babel_check_ack_seq(seq); +} + +static void +babel_expire_ack_seqs(struct babel_proto *p) +{ + struct babel_ack_sequence *seq, *nxt; + btime now_ = current_time(); + + WALK_LIST_DELSAFE(seq, nxt, p->ack_seqs) + { + if (now_ >= seq->expires) + { + if (seq->retries > 0) + { + babel_send_ack_sequence(seq); + seq->retries--; + seq->expires = now_ + BABEL_ACK_RETRY_INTERVAL; + babel_kick_timer(p, BABEL_ACK_RETRY_INTERVAL); + } + else + { + babel_flush_ack_seq(seq); + } + } + } +} + /* * Best route selection @@ -784,6 +857,40 @@ babel_send_ack(struct babel_iface *ifa, ip_addr dest, u16 nonce) babel_send_unicast(&msg, ifa, dest); } +static void +babel_send_ack_sequence(struct babel_ack_sequence *seq) +{ + struct babel_msg_node msgn = {}; + struct babel_outgoing_ack_req *ack; + + msgn.msg.type = BABEL_TLV_ACK_REQ; + msgn.msg.ack_req.interval = BABEL_ACK_RETRY_INTERVAL; + add_tail(&seq->payload, NODE &msgn); + + WALK_LIST(ack, seq->acks) { + DBG("Sending ACK request to %I with nonce %d\n", ack->nbr->addr, ack->nonce); + msgn.msg.ack_req.nonce = ack->nonce; + babel_send_unicast_list(&seq->payload, ack->nbr->ifa, ack->nbr->addr); + } + rem_node(NODE &msgn); +} + +static void +babel_retraction_ack_complete(struct babel_ack_sequence *seq) +{ + struct babel_proto *p = seq->p; + struct babel_msg_node *msgn = HEAD(seq->payload); + struct babel_entry *e = babel_find_entry(p, &msgn->msg.update.net) + + ASSERT(msgn->msg.type == BABEL_TLV_UPDATE); + + if (e && e->unreachable && e->valid == BABEL_ENTRY_STALE) + { + DBG("ACK sequence for retraction complete, retracting route: %N\n", e->n.addr); + babel_announce_retraction(p, e); + } +} + static void babel_build_ihu(union babel_msg *msg, struct babel_iface *ifa, struct babel_neighbor *n) { @@ -1020,7 +1127,7 @@ babel_send_retraction(struct babel_iface *ifa, net_addr *n) TRACE(D_PACKETS, "Sending retraction for %N seqno %d", n, p->update_seqno); msg.type = BABEL_TLV_UPDATE; - msg.update.interval = ifa->cf->update_interval; + msg.update.interval = BABEL_INFINITY; msg.update.seqno = p->update_seqno; msg.update.metric = BABEL_INFINITY; msg.update.net = *n; @@ -1028,6 +1135,54 @@ babel_send_retraction(struct babel_iface *ifa, net_addr *n) babel_enqueue(&msg, ifa); } +static void +babel_send_retraction_acked(struct babel_proto *p, net_addr *n) +{ + struct babel_ack_sequence *seq = mb_allocz(p->p.pool, sizeof(struct babel_ack_sequence)); + struct babel_msg_node *msgn = sl_alloc(p->msg_slab); + struct babel_iface *ifa; + struct babel_neighbor *nbr; + int i = 0; + + init_list(&seq->acks); + init_list(&seq->payload); + memset(msgn, 0, sizeof(*msgn)); + seq->callback = babel_retraction_ack_complete; + seq->expires = current_time() + BABEL_ACK_RETRY_INTERVAL; + seq->retries = BABEL_ACK_RETRIES; + seq->p = p; + add_tail(&p->ack_seqs, NODE seq); + + msgn->msg.type = BABEL_TLV_UPDATE; + msgn->msg.update.interval = BABEL_INFINITY; + msgn->msg.update.seqno = p->update_seqno; + msgn->msg.update.metric = BABEL_INFINITY; + msgn->msg.update.net = *n; + + add_tail(&seq->payload, NODE msgn); + + WALK_LIST(ifa, p->interfaces) { + WALK_LIST(nbr, ifa->neigh_list) { + struct babel_outgoing_ack_req *ack = mb_allocz(p->p.pool, sizeof(struct babel_outgoing_ack_req)); + ack->nbr = nbr; + ack->seq = seq; + ack->nonce = random(); + add_tail(&seq->acks, NODE ack); + add_tail(&nbr->ack_reqs, &ack->neigh_ack); + i++; + } + } + + DBG("Created ACK sequence for %N with %d requests\n", n, i); + + /* Sequence may be empty if we have no neighbors */ + if (!babel_check_ack_seq(seq)) + { + babel_send_ack_sequence(seq); + babel_kick_timer(p, BABEL_ACK_RETRY_INTERVAL); + } +} + static void babel_send_wildcard_retraction(struct babel_iface *ifa) { @@ -1096,11 +1251,35 @@ babel_update_hello_history(struct babel_neighbor *n, u16 seqno, uint interval) n->last_hello_int = interval; } - /* * TLV handlers */ +void +babel_handle_ack(union babel_msg *m, struct babel_iface *ifa) +{ + struct babel_proto *p = ifa->proto; + struct babel_msg_ack *msg = &m->ack; + node *n; + + TRACE(D_PACKETS, "Handling ACK nonce %d from %I", + msg->nonce, msg->sender); + + struct babel_neighbor *nbr = babel_find_neighbor(ifa, msg->sender); + if (!nbr) + return; + + WALK_LIST(n, nbr->ack_reqs) + { + struct babel_outgoing_ack_req *ack = SKIP_BACK(struct babel_outgoing_ack_req, neigh_ack, n); + if (ack->nonce == msg->nonce) + { + babel_flush_outgoing_ack(ack); + return; + } + } +} + void babel_handle_ack_req(union babel_msg *m, struct babel_iface *ifa) { @@ -2044,13 +2223,14 @@ babel_timer(timer *t) babel_expire_routes(p); babel_expire_neighbors(p); + babel_expire_ack_seqs(p); } static inline void -babel_kick_timer(struct babel_proto *p) +babel_kick_timer(struct babel_proto *p, btime interval) { - if (p->timer->expires > (current_time() + 100 MS)) - tm_start(p->timer, 100 MS); + if (p->timer->expires > (current_time() + interval)) + tm_start(p->timer, interval); } @@ -2161,9 +2341,9 @@ babel_rt_notify(struct proto *P, struct channel *c UNUSED, struct network *net, e->valid = BABEL_ENTRY_STALE; e->metric = BABEL_INFINITY; - - babel_trigger_update(p); e->updated = current_time(); + + babel_send_retraction_acked(p, net->n.addr); } } @@ -2214,6 +2394,7 @@ babel_start(struct proto *P) OFFSETOF(struct babel_entry, n), 0, babel_init_entry); init_list(&p->interfaces); + init_list(&p->ack_seqs); p->timer = tm_new_init(P->pool, babel_timer, p, 1 S, 0); tm_start(p->timer, 1 S); p->update_seqno = 1; @@ -2269,7 +2450,7 @@ babel_reconfigure(struct proto *P, struct proto_config *CF) babel_reconfigure_ifaces(p, new); babel_trigger_update(p); - babel_kick_timer(p); + babel_kick_timer(p, 100 MS); return 1; } diff --git a/proto/babel/babel.h b/proto/babel/babel.h index 1128d261..684bad1b 100644 --- a/proto/babel/babel.h +++ b/proto/babel/babel.h @@ -56,6 +56,8 @@ #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) +#define BABEL_ACK_RETRY_INTERVAL (1 S_) +#define BABEL_ACK_RETRIES 2 #define BABEL_OVERHEAD (IP6_HEADER_LENGTH+UDP_HEADER_LENGTH) #define BABEL_MIN_MTU (512 + BABEL_OVERHEAD) @@ -142,6 +144,7 @@ struct babel_proto { struct channel *ip6_channel; list interfaces; /* Interfaces we really know about (struct babel_iface) */ + list ack_seqs; /* Outstanding ACK sequences */ u64 router_id; u16 update_seqno; /* To be increased on request */ u8 update_seqno_inc; /* Request for update_seqno increase */ @@ -205,6 +208,7 @@ struct babel_neighbor { btime ihu_expiry; list routes; /* Routes this neighbour has sent us (struct babel_route) */ + list ack_reqs; /* Outstanding ack requests sent to this neighbor */ }; struct babel_source { @@ -263,6 +267,25 @@ struct babel_entry { #define BABEL_ENTRY_VALID 1 /* Valid outgoing route */ #define BABEL_ENTRY_STALE 2 /* Stale outgoing route, waiting for GC */ +struct babel_ack_sequence { + node n; + list acks; /* list of pending acks in sequence (babel_outgoing_ack_req) */ + btime expires; + u8 retries; + list payload; /* list of babel_msg_nodes in outgoing messages */ + + void (*callback)(struct babel_ack_sequence *); /* called when there are no more pending ACKs */ + struct babel_proto *p; +}; + +struct babel_outgoing_ack_req { + node n; /* in struct babel_ack_sequence->acks */ + node neigh_ack; /* in struct babel_neighbor->ack_reqs */ + u16 nonce; + struct babel_neighbor *nbr; + struct babel_ack_sequence *seq; +}; + /* * Internal TLV messages @@ -278,6 +301,7 @@ struct babel_msg_ack_req { struct babel_msg_ack { u8 type; u16 nonce; + ip_addr sender; }; struct babel_msg_hello { @@ -358,6 +382,7 @@ void babel_show_routes(struct proto *P); /* 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); +void babel_send_unicast_list(list *lst, struct babel_iface *ifa, ip_addr dest); int babel_open_socket(struct babel_iface *ifa); void babel_send_queue(void *arg); diff --git a/proto/babel/packets.c b/proto/babel/packets.c index dd86222a..5b4c4555 100644 --- a/proto/babel/packets.c +++ b/proto/babel/packets.c @@ -229,6 +229,7 @@ put_ip6_ll(void *p, ip6_addr addr) * TLV read/write functions */ +static int babel_read_ack(struct babel_tlv *hdr, union babel_msg *msg, struct babel_parse_state *state); static int babel_read_ack_req(struct babel_tlv *hdr, union babel_msg *msg, struct babel_parse_state *state); static int babel_read_hello(struct babel_tlv *hdr, union babel_msg *msg, struct babel_parse_state *state); static int babel_read_ihu(struct babel_tlv *hdr, union babel_msg *msg, struct babel_parse_state *state); @@ -239,6 +240,7 @@ static int babel_read_route_request(struct babel_tlv *hdr, union babel_msg *msg, static int babel_read_seqno_request(struct babel_tlv *hdr, union babel_msg *msg, struct babel_parse_state *state); static uint babel_write_ack(struct babel_tlv *hdr, union babel_msg *msg, struct babel_write_state *state, uint max_len); +static uint babel_write_ack_req(struct babel_tlv *hdr, union babel_msg *msg, struct babel_write_state *state, uint max_len); static uint babel_write_hello(struct babel_tlv *hdr, union babel_msg *msg, struct babel_write_state *state, uint max_len); static uint babel_write_ihu(struct babel_tlv *hdr, union babel_msg *msg, struct babel_write_state *state, uint max_len); static uint babel_write_update(struct babel_tlv *hdr, union babel_msg *msg, struct babel_write_state *state, uint max_len); @@ -256,14 +258,14 @@ static const struct babel_tlv_data tlv_data[BABEL_TLV_MAX] = { [BABEL_TLV_ACK_REQ] = { sizeof(struct babel_tlv_ack_req), babel_read_ack_req, - NULL, + babel_write_ack_req, babel_handle_ack_req }, [BABEL_TLV_ACK] = { sizeof(struct babel_tlv_ack), - NULL, + babel_read_ack, babel_write_ack, - NULL + babel_handle_ack }, [BABEL_TLV_HELLO] = { sizeof(struct babel_tlv_hello), @@ -327,6 +329,36 @@ babel_read_ack_req(struct babel_tlv *hdr, union babel_msg *m, return PARSE_SUCCESS; } +static uint +babel_write_ack_req(struct babel_tlv *hdr, union babel_msg *m, + struct babel_write_state *state UNUSED, uint max_len UNUSED) +{ + struct babel_tlv_ack_req *tlv = (void *) hdr; + struct babel_msg_ack_req *msg = &m->ack_req; + + TLV_HDR0(tlv, BABEL_TLV_ACK_REQ); + put_u16(&tlv->nonce, msg->nonce); + put_time16(&tlv->interval, msg->interval); + + return sizeof(struct babel_tlv_ack_req); +} + + +static int +babel_read_ack(struct babel_tlv *hdr, union babel_msg *m, + struct babel_parse_state *state) +{ + struct babel_tlv_ack *tlv = (void *) hdr; + struct babel_msg_ack *msg = &m->ack; + + msg->type = BABEL_TLV_ACK; + msg->nonce = get_u16(&tlv->nonce); + msg->sender = state->saddr; + + return PARSE_SUCCESS; +} + + static uint babel_write_ack(struct babel_tlv *hdr, union babel_msg *m, struct babel_write_state *state UNUSED, uint max_len UNUSED) @@ -1141,6 +1173,39 @@ babel_send_unicast(union babel_msg *msg, struct babel_iface *ifa, ip_addr dest) babel_kick_queue(ifa); } +/** + * babel_send_unicast_list - send a multi-TLV packet via unicast to a destination + * @lst: list of TLVs to send + * @ifa: Interface to send via + * @dest: Destination of the TLV + * + * This function is used to send a list of TLVs via unicast to a designated + * receiver. This is used for sending messages that comprise multiple TLVs, such + * as those that include an acknowledgement request. + */ +void +babel_send_unicast_list(list *lst, struct babel_iface *ifa, ip_addr dest) +{ + struct babel_proto *p = ifa->proto; + struct babel_msg_node *msgn, *msgn_copy; + list queue; + + init_list(&queue); + WALK_LIST(msgn, *lst) + { + msgn_copy = sl_alloc(p->msg_slab); + memcpy(msgn_copy, msgn, sizeof(*msgn_copy)); + + add_tail(&queue, NODE msgn_copy); + } + babel_write_queue(ifa, &queue); + babel_send_to(ifa, dest); + + /* We could overwrite waiting packet here, we may have to kick TX queue */ + if (!EMPTY_LIST(ifa->msg_queue)) + babel_kick_queue(ifa); +} + /** * babel_enqueue - enqueue a TLV for transmission on an interface * @msg: TLV to enqueue (in internal TLV format) -- 2.16.1

2 6

Can't Log information about a double
by Mattia Milani 04 Apr '18

04 Apr '18

Hello all, I'm trying to log some information during the bird process execution. I'm doing it in the bgp section. I used the command: log(L_INFO "** some text **"); with success, i added to the log some information about an integer variable with success, here it is the code: int a = 5; log(L_INFO "** some text ** %d", a); Now i'm trying to make the same with a double variable but without success double a = 5.5; log(L_INFO "** some text ** %lf", a); the output was: 2018-03-30 18:09:12.270 <INFO> ** some text ** %f I had already tried with %f instead of %lf but nothing changed in the output How can i log some double value? i need to use another function instead of log()? Thanks, Mattia

3 6

Opensource Virtual Network Topology builder (knet)
by knet solutions 03 Apr '18

03 Apr '18

All, I am glad to introduce the opensource virtual network topology builder (knet). Its built with docker and openvswitch. I am using "bird" for router node. we can build the complex routing topology in few seconds, General Intro about this tool: ----------------------------------------------- https://github.com/knetsolutions/knet/ http://knet-topology-builder.readthedocs.io/en/latest/ Quick video tutorial in youtube: ------------------------------------------------- https://www.youtube.com/watch?v=SmWmbAsiimI&list= PLSO7MDepKLNCrHGrRcAyUWWUEFCOrjC4B -- *Regards, * *Suresh* *Knet solutions.* https://github.com/knetsolutions/KNet http://knet-topology-builder.readthedocs.io/ http://knetsolutions.in/

1 0

Problem with ECMP
by André Carlim 02 Apr '18

02 Apr '18

I'm trying to use ECMP, but without success, I'll leave my conf below, does anyone know where I'm going wrong? Q. I have two routers announcing the default route for this "client". conf: log syslog all; # Override router ID router id 10.192.0.2; # Turn on global debugging of all protocols debug protocols all; protocol direct { interface "-eth*", "*"; # Restrict network interfaces it works with } filter kernel_export { print "filter_name: ", "kernel_export", " protocol: ", proto, " net: ", net, " krt_metric: ", krt_metric; if net = 0.0.0.0/0 then { krt_metric = 100; } accept; } protocol kernel { learn; # Learn all alien routes from the kernel persist; # Don't remove routes on bird shutdown scan time 20; # Scan kernel routing table every 20 seconds import all; # Default is import all export filter kernel_export; # Default is export none } protocol device { scan time 10; # Scan interfaces every 10 seconds } protocol static { disabled; # Disable by default } filter ospf_import { print "router_id: ", ospf_router_id, " net: ", net, " ospf_metric1: ", ospf_metric1 ; if net = 0.0.0.0/0 then { ospf_metric1 = 1000; } accept; } protocol ospf { ecmp yes; import filter ospf_import; export all; tick 1; rfc1583compat yes; area 0.0.0.0 { networks { 10.192.0.0/29; }; interface "eth1" { type broadcast; authentication none; }; }; } output of 'show ospf state' in this host: area 0.0.0.0 router 10.192.0.1 distance 10 network 10.192.0.0/29 metric 10 external 0.0.0.0/0 metric2 10000 router 10.192.0.2 distance 0 network 10.192.0.0/29 metric 10 external 100.126.0.44/32 metric2 10000 router 10.192.0.3 distance 10 network 10.192.0.0/29 metric 10 external 0.0.0.0/0 metric2 10000 network 10.192.0.0/29 dr 10.192.0.3 distance 10 router 10.192.0.3 router 10.192.0.2 router 10.192.0.1 -- André Carlim StubNetwork

2 2

OSPF Create and Originate Default Route
by André Carlim 02 Apr '18

02 Apr '18

Hello! I use the OSPF module of the bird, however I use several different tables in both the module and the Linux kernel, and in general I need to create and distribute the default route. I saw in other discussions that the folks there are no problems in reading the route in the kernel table, and so redistribute it, I remember that this is not my case, I do not have the default route in these kernel tables. Does anyone have any idea how I will do this? -- André Carlim StubNetwork

3 6