1 // SPDX-License-Identifier: MIT
3 Copyright (c) 2007, 2008 by Juliusz Chroboczek
4 Copyright 2011 by Matthieu Boutier and Juliusz Chroboczek
13 #include "babel_interface.h"
15 #include "neighbour.h"
20 #include "babel_errors.h"
22 static void consider_route(struct babel_route
*route
);
24 struct babel_route
**routes
= NULL
;
25 static int route_slots
= 0, max_route_slots
= 0;
26 int kernel_metric
= 0;
27 enum babel_diversity diversity_kind
= DIVERSITY_NONE
;
28 int diversity_factor
= BABEL_DEFAULT_DIVERSITY_FACTOR
;
29 int keep_unfeasible
= 0;
31 int smoothing_half_life
= 0;
32 static int two_to_the_one_over_hl
= 0; /* 2^(1/hl) * 0x10000 */
34 /* We maintain a list of "slots", ordered by prefix. Every slot
35 contains a linked list of the routes to this prefix, with the
36 installed route, if any, at the head of the list. */
39 route_compare(const unsigned char *prefix
, unsigned char plen
,
40 struct babel_route
*route
)
42 int i
= memcmp(prefix
, route
->src
->prefix
, 16);
46 if(plen
< route
->src
->plen
)
48 else if(plen
> route
->src
->plen
)
54 /* Performs binary search, returns -1 in case of failure. In the latter
55 case, new_return is the place where to insert the new element. */
58 find_route_slot(const unsigned char *prefix
, unsigned char plen
,
69 p
= 0; g
= route_slots
- 1;
73 c
= route_compare(prefix
, plen
, routes
[m
]);
89 find_route(const unsigned char *prefix
, unsigned char plen
,
90 struct neighbour
*neigh
, const unsigned char *nexthop
)
92 struct babel_route
*route
;
93 int i
= find_route_slot(prefix
, plen
, NULL
);
101 if(route
->neigh
== neigh
&& memcmp(route
->nexthop
, nexthop
, 16) == 0)
110 find_installed_route(const unsigned char *prefix
, unsigned char plen
)
112 int i
= find_route_slot(prefix
, plen
, NULL
);
114 if(i
>= 0 && routes
[i
]->installed
)
120 /* Returns an overestimate of the number of installed routes. */
122 installed_routes_estimate(void)
128 resize_route_table(int new_slots
)
130 struct babel_route
**new_routes
;
131 assert(new_slots
>= route_slots
);
137 new_routes
= realloc(routes
, new_slots
* sizeof(struct babel_route
*));
138 if(new_routes
== NULL
)
142 max_route_slots
= new_slots
;
147 /* Insert a route into the table. If successful, retains the route.
148 On failure, caller must free the route. */
149 static struct babel_route
*
150 insert_route(struct babel_route
*route
)
154 assert(!route
->installed
);
156 i
= find_route_slot(route
->src
->prefix
, route
->src
->plen
, &n
);
159 if(route_slots
>= max_route_slots
)
160 resize_route_table(max_route_slots
< 1 ? 8 : 2 * max_route_slots
);
161 if(route_slots
>= max_route_slots
)
166 memmove(routes
+ n
+ 1, routes
+ n
,
167 (route_slots
- n
) * sizeof(struct babel_route
*));
171 struct babel_route
*r
;
183 flush_route(struct babel_route
*route
)
190 oldmetric
= route_metric(route
);
193 if(route
->installed
) {
194 uninstall_route(route
);
198 i
= find_route_slot(route
->src
->prefix
, route
->src
->plen
, NULL
);
199 assert(i
>= 0 && i
< route_slots
);
201 if(route
== routes
[i
]) {
202 routes
[i
] = route
->next
;
206 if(routes
[i
] == NULL
) {
207 if(i
< route_slots
- 1)
208 memmove(routes
+ i
, routes
+ i
+ 1,
209 (route_slots
- i
- 1) * sizeof(struct babel_route
*));
210 routes
[route_slots
- 1] = NULL
;
215 resize_route_table(0);
216 else if(max_route_slots
> 8 && route_slots
< max_route_slots
/ 4)
217 resize_route_table(max_route_slots
/ 2);
219 struct babel_route
*r
= routes
[i
];
220 while(r
->next
!= route
)
222 r
->next
= route
->next
;
228 route_lost(src
, oldmetric
);
234 flush_all_routes(void)
238 /* Start from the end, to avoid shifting the table. */
241 while(i
< route_slots
) {
242 /* Uninstall first, to avoid calling route_lost. */
243 if(routes
[i
]->installed
)
244 uninstall_route(routes
[i
]);
245 flush_route(routes
[i
]);
250 check_sources_released();
254 flush_neighbour_routes(struct neighbour
*neigh
)
259 while(i
< route_slots
) {
260 struct babel_route
*r
;
263 if(r
->neigh
== neigh
) {
276 flush_interface_routes(struct interface
*ifp
, int v4only
)
281 while(i
< route_slots
) {
282 struct babel_route
*r
;
285 if(r
->neigh
->ifp
== ifp
&&
286 (!v4only
|| v4mapped(r
->nexthop
))) {
298 struct route_stream
{
301 struct babel_route
*next
;
305 struct route_stream
*
306 route_stream(int installed
)
308 struct route_stream
*stream
;
310 stream
= malloc(sizeof(struct route_stream
));
314 stream
->installed
= installed
;
315 stream
->index
= installed
? 0 : -1;
322 route_stream_next(struct route_stream
*stream
)
324 if(stream
->installed
) {
325 while(stream
->index
< route_slots
&& !routes
[stream
->index
]->installed
)
328 if(stream
->index
< route_slots
)
329 return routes
[stream
->index
++];
333 struct babel_route
*next
;
336 if(stream
->index
>= route_slots
)
338 stream
->next
= routes
[stream
->index
];
341 stream
->next
= next
->next
;
347 route_stream_done(struct route_stream
*stream
)
353 metric_to_kernel(int metric
)
355 return metric
< INFINITY
? kernel_metric
: KERNEL_INFINITY
;
358 /* This is used to maintain the invariant that the installed route is at
359 the head of the list. */
361 move_installed_route(struct babel_route
*route
, int i
)
363 assert(i
>= 0 && i
< route_slots
);
364 assert(route
->installed
);
366 if(route
!= routes
[i
]) {
367 struct babel_route
*r
= routes
[i
];
368 while(r
->next
!= route
)
370 r
->next
= route
->next
;
371 route
->next
= routes
[i
];
377 install_route(struct babel_route
*route
)
384 if(!route_feasible(route
))
385 flog_err(EC_BABEL_ROUTE
,
386 "Installing unfeasible route (this shouldn't happen).");
388 i
= find_route_slot(route
->src
->prefix
, route
->src
->plen
, NULL
);
389 assert(i
>= 0 && i
< route_slots
);
391 if(routes
[i
] != route
&& routes
[i
]->installed
) {
394 "Attempting to install duplicate route (this shouldn't happen).");
398 rc
= kernel_route(ROUTE_ADD
, route
->src
->prefix
, route
->src
->plen
,
400 route
->neigh
->ifp
->ifindex
,
401 metric_to_kernel(route_metric(route
)), NULL
, 0, 0);
404 flog_err(EC_BABEL_ROUTE
, "kernel_route(ADD): %s",
405 safe_strerror(errno
));
409 route
->installed
= 1;
410 move_installed_route(route
, i
);
415 uninstall_route(struct babel_route
*route
)
419 if(!route
->installed
)
422 rc
= kernel_route(ROUTE_FLUSH
, route
->src
->prefix
, route
->src
->plen
,
424 route
->neigh
->ifp
->ifindex
,
425 metric_to_kernel(route_metric(route
)), NULL
, 0, 0);
427 flog_err(EC_BABEL_ROUTE
, "kernel_route(FLUSH): %s",
428 safe_strerror(errno
));
430 route
->installed
= 0;
433 /* This is equivalent to uninstall_route followed with install_route,
434 but without the race condition. The destination of both routes
438 switch_routes(struct babel_route
*old
, struct babel_route
*new)
450 if(!route_feasible(new))
451 flog_err(EC_BABEL_ROUTE
,
452 "Switching to unfeasible route (this shouldn't happen).");
454 rc
= kernel_route(ROUTE_MODIFY
, old
->src
->prefix
, old
->src
->plen
,
455 old
->nexthop
, old
->neigh
->ifp
->ifindex
,
456 metric_to_kernel(route_metric(old
)),
457 new->nexthop
, new->neigh
->ifp
->ifindex
,
458 metric_to_kernel(route_metric(new)));
460 flog_err(EC_BABEL_ROUTE
, "kernel_route(MODIFY): %s",
461 safe_strerror(errno
));
467 move_installed_route(new, find_route_slot(new->src
->prefix
, new->src
->plen
,
472 change_route_metric(struct babel_route
*route
,
473 unsigned refmetric
, unsigned cost
, unsigned add
)
476 int newmetric
= MIN(refmetric
+ cost
+ add
, INFINITY
);
478 old
= metric_to_kernel(route_metric(route
));
479 new = metric_to_kernel(newmetric
);
481 if(route
->installed
&& old
!= new) {
483 rc
= kernel_route(ROUTE_MODIFY
, route
->src
->prefix
, route
->src
->plen
,
484 route
->nexthop
, route
->neigh
->ifp
->ifindex
,
486 route
->nexthop
, route
->neigh
->ifp
->ifindex
,
489 flog_err(EC_BABEL_ROUTE
, "kernel_route(MODIFY metric): %s",
490 safe_strerror(errno
));
495 /* Update route->smoothed_metric using the old metric. */
496 route_smoothed_metric(route
);
498 route
->refmetric
= refmetric
;
500 route
->add_metric
= add
;
502 if(smoothing_half_life
== 0) {
503 route
->smoothed_metric
= route_metric(route
);
504 route
->smoothed_metric_time
= babel_now
.tv_sec
;
509 retract_route(struct babel_route
*route
)
511 /* We cannot simply remove the route from the kernel, as that might
512 cause a routing loop -- see RFC 6126 Sections 2.8 and 3.5.5. */
513 change_route_metric(route
, INFINITY
, INFINITY
, 0);
517 route_feasible(struct babel_route
*route
)
519 return update_feasible(route
->src
, route
->seqno
, route
->refmetric
);
523 route_old(struct babel_route
*route
)
525 return route
->time
< babel_now
.tv_sec
- route
->hold_time
* 7 / 8;
529 route_expired(struct babel_route
*route
)
531 return route
->time
< babel_now
.tv_sec
- route
->hold_time
;
535 channels_interfere(int ch1
, int ch2
)
537 if(ch1
== BABEL_IF_CHANNEL_NONINTERFERING
538 || ch2
== BABEL_IF_CHANNEL_NONINTERFERING
)
540 if(ch1
== BABEL_IF_CHANNEL_INTERFERING
541 || ch2
== BABEL_IF_CHANNEL_INTERFERING
)
547 route_interferes(struct babel_route
*route
, struct interface
*ifp
)
549 struct babel_interface
*babel_ifp
= NULL
;
550 switch(diversity_kind
) {
553 case DIVERSITY_INTERFACE_1
:
554 return route
->neigh
->ifp
== ifp
;
555 case DIVERSITY_CHANNEL_1
:
556 case DIVERSITY_CHANNEL
:
557 if(route
->neigh
->ifp
== ifp
)
559 babel_ifp
= babel_get_if_nfo(ifp
);
560 if(channels_interfere(babel_ifp
->channel
,
561 babel_get_if_nfo(route
->neigh
->ifp
)->channel
))
563 if(diversity_kind
== DIVERSITY_CHANNEL
) {
565 for(i
= 0; i
< DIVERSITY_HOPS
; i
++) {
566 if(route
->channels
[i
] == 0)
568 if(channels_interfere(babel_ifp
->channel
, route
->channels
[i
]))
579 update_feasible(struct source
*src
,
580 unsigned short seqno
, unsigned short refmetric
)
585 if(src
->time
< babel_now
.tv_sec
- SOURCE_GC_TIME
)
586 /* Never mind what is probably stale data */
589 if(refmetric
>= INFINITY
)
590 /* Retractions are always feasible */
593 return (seqno_compare(seqno
, src
->seqno
) > 0 ||
594 (src
->seqno
== seqno
&& refmetric
< src
->metric
));
598 change_smoothing_half_life(int half_life
)
601 smoothing_half_life
= 0;
602 two_to_the_one_over_hl
= 0;
606 smoothing_half_life
= half_life
;
607 switch(smoothing_half_life
) {
608 case 1: two_to_the_one_over_hl
= 131072; break;
609 case 2: two_to_the_one_over_hl
= 92682; break;
610 case 3: two_to_the_one_over_hl
= 82570; break;
611 case 4: two_to_the_one_over_hl
= 77935; break;
613 /* 2^(1/x) is 1 + log(2)/x + O(1/x^2) at infinity. */
614 two_to_the_one_over_hl
= 0x10000 + 45426 / half_life
;
618 /* Update the smoothed metric, return the new value. */
620 route_smoothed_metric(struct babel_route
*route
)
622 int metric
= route_metric(route
);
624 if(smoothing_half_life
<= 0 || /* no smoothing */
625 metric
>= INFINITY
|| /* route retracted */
626 route
->smoothed_metric_time
> babel_now
.tv_sec
|| /* clock stepped */
627 route
->smoothed_metric
== metric
) { /* already converged */
628 route
->smoothed_metric
= metric
;
629 route
->smoothed_metric_time
= babel_now
.tv_sec
;
632 /* We randomise the computation, to minimise global synchronisation
633 and hence oscillations. */
634 while(route
->smoothed_metric_time
<=
635 babel_now
.tv_sec
- smoothing_half_life
) {
636 diff
= metric
- route
->smoothed_metric
;
637 route
->smoothed_metric
+= roughly(diff
) / 2;
638 route
->smoothed_metric_time
+= smoothing_half_life
;
640 while(route
->smoothed_metric_time
< babel_now
.tv_sec
) {
641 diff
= metric
- route
->smoothed_metric
;
642 route
->smoothed_metric
+=
643 roughly(diff
) * (two_to_the_one_over_hl
- 0x10000) / 0x10000;
644 route
->smoothed_metric_time
++;
647 diff
= metric
- route
->smoothed_metric
;
648 if(diff
> -4 && diff
< 4)
649 route
->smoothed_metric
= metric
;
652 /* change_route_metric relies on this */
653 assert(route
->smoothed_metric_time
== babel_now
.tv_sec
);
654 return route
->smoothed_metric
;
658 route_acceptable(struct babel_route
*route
, int feasible
,
659 struct neighbour
*exclude
)
661 if(route_expired(route
))
663 if(feasible
&& !route_feasible(route
))
665 if(exclude
&& route
->neigh
== exclude
)
670 /* Find the best route according to the weak ordering. Any
671 linearisation of the strong ordering (see consider_route) will do,
672 we use sm <= sm'. We could probably use a lexical ordering, but
673 that's probably overkill. */
676 find_best_route(const unsigned char *prefix
, unsigned char plen
, int feasible
,
677 struct neighbour
*exclude
)
679 struct babel_route
*route
= NULL
, *r
= NULL
;
680 int i
= find_route_slot(prefix
, plen
, NULL
);
686 while(route
&& !route_acceptable(route
, feasible
, exclude
))
694 if(route_acceptable(r
, feasible
, exclude
) &&
695 (route_smoothed_metric(r
) < route_smoothed_metric(route
)))
704 update_route_metric(struct babel_route
*route
)
706 int oldmetric
= route_metric(route
);
707 int old_smoothed_metric
= route_smoothed_metric(route
);
709 if(route_expired(route
)) {
710 if(route
->refmetric
< INFINITY
) {
711 route
->seqno
= seqno_plus(route
->src
->seqno
, 1);
712 retract_route(route
);
713 if(oldmetric
< INFINITY
)
714 route_changed(route
, route
->src
, oldmetric
);
717 struct neighbour
*neigh
= route
->neigh
;
718 int add_metric
= input_filter(route
->src
->id
,
719 route
->src
->prefix
, route
->src
->plen
,
721 neigh
->ifp
->ifindex
);
722 change_route_metric(route
, route
->refmetric
,
723 neighbour_cost(route
->neigh
), add_metric
);
724 if(route_metric(route
) != oldmetric
||
725 route_smoothed_metric(route
) != old_smoothed_metric
)
726 route_changed(route
, route
->src
, oldmetric
);
730 /* Called whenever a neighbour's cost changes, to update the metric of
731 all routes through that neighbour. */
733 update_neighbour_metric(struct neighbour
*neigh
, int changed
)
739 for(i
= 0; i
< route_slots
; i
++) {
740 struct babel_route
*r
= routes
[i
];
742 if(r
->neigh
== neigh
)
743 update_route_metric(r
);
751 update_interface_metric(struct interface
*ifp
)
755 for(i
= 0; i
< route_slots
; i
++) {
756 struct babel_route
*r
= routes
[i
];
758 if(r
->neigh
->ifp
== ifp
)
759 update_route_metric(r
);
765 /* This is called whenever we receive an update. */
767 update_route(const unsigned char *router_id
,
768 const unsigned char *prefix
, unsigned char plen
,
769 unsigned short seqno
, unsigned short refmetric
,
770 unsigned short interval
,
771 struct neighbour
*neigh
, const unsigned char *nexthop
,
772 const unsigned char *channels
, int channels_len
)
774 struct babel_route
*route
;
776 int metric
, feasible
;
778 int hold_time
= MAX((4 * interval
) / 100 + interval
/ 50, 15);
780 if(memcmp(router_id
, myid
, 8) == 0)
783 if(martian_prefix(prefix
, plen
)) {
784 flog_err(EC_BABEL_ROUTE
, "Rejecting martian route to %s through %s.",
785 format_prefix(prefix
, plen
), format_address(nexthop
));
789 add_metric
= input_filter(router_id
, prefix
, plen
,
790 neigh
->address
, neigh
->ifp
->ifindex
);
791 if(add_metric
>= INFINITY
)
794 route
= find_route(prefix
, plen
, neigh
, nexthop
);
796 if(route
&& memcmp(route
->src
->id
, router_id
, 8) == 0)
797 /* Avoid scanning the source table. */
800 src
= find_source(router_id
, prefix
, plen
, 1, seqno
);
805 feasible
= update_feasible(src
, seqno
, refmetric
);
806 metric
= MIN((int)refmetric
+ neighbour_cost(neigh
) + add_metric
, INFINITY
);
809 struct source
*oldsrc
;
810 unsigned short oldmetric
;
814 oldmetric
= route_metric(route
);
816 /* If a successor switches sources, we must accept his update even
817 if it makes a route unfeasible in order to break any routing loops
818 in a timely manner. If the source remains the same, we ignore
820 if(!feasible
&& route
->installed
) {
821 debugf(BABEL_DEBUG_COMMON
,"Unfeasible update for installed route to %s (%s %d %d -> %s %d %d).",
822 format_prefix(src
->prefix
, src
->plen
),
823 format_eui64(route
->src
->id
),
824 route
->seqno
, route
->refmetric
,
825 format_eui64(src
->id
), seqno
, refmetric
);
826 if(src
!= route
->src
) {
827 uninstall_route(route
);
832 route
->src
= retain_source(src
);
833 if((feasible
|| keep_unfeasible
) && refmetric
< INFINITY
)
834 route
->time
= babel_now
.tv_sec
;
835 route
->seqno
= seqno
;
837 memset(&route
->channels
, 0, sizeof(route
->channels
));
839 memcpy(&route
->channels
, channels
,
840 MIN(channels_len
, DIVERSITY_HOPS
));
842 change_route_metric(route
,
843 refmetric
, neighbour_cost(neigh
), add_metric
);
844 route
->hold_time
= hold_time
;
846 route_changed(route
, oldsrc
, oldmetric
);
848 route_lost(oldsrc
, oldmetric
);
851 send_unfeasible_request(neigh
, route
->installed
&& route_old(route
),
853 release_source(oldsrc
);
855 struct babel_route
*new_route
;
857 if(refmetric
>= INFINITY
)
858 /* Somebody's retracting a route we never saw. */
861 send_unfeasible_request(neigh
, 0, seqno
, metric
, src
);
866 route
= malloc(sizeof(struct babel_route
));
868 perror("malloc(route)");
872 route
->src
= retain_source(src
);
873 route
->refmetric
= refmetric
;
874 route
->cost
= neighbour_cost(neigh
);
875 route
->add_metric
= add_metric
;
876 route
->seqno
= seqno
;
877 route
->neigh
= neigh
;
878 memcpy(route
->nexthop
, nexthop
, 16);
879 route
->time
= babel_now
.tv_sec
;
880 route
->hold_time
= hold_time
;
881 route
->smoothed_metric
= MAX(route_metric(route
), INFINITY
/ 2);
882 route
->smoothed_metric_time
= babel_now
.tv_sec
;
883 route
->installed
= 0;
884 memset(&route
->channels
, 0, sizeof(route
->channels
));
886 memcpy(&route
->channels
, channels
,
887 MIN(channels_len
, DIVERSITY_HOPS
));
889 new_route
= insert_route(route
);
890 if(new_route
== NULL
) {
891 flog_err(EC_BABEL_ROUTE
, "Couldn't insert route.");
895 consider_route(route
);
900 /* We just received an unfeasible update. If it's any good, send
901 a request for a new seqno. */
903 send_unfeasible_request(struct neighbour
*neigh
, int force
,
904 unsigned short seqno
, unsigned short metric
,
907 struct babel_route
*route
= find_installed_route(src
->prefix
, src
->plen
);
909 if(seqno_minus(src
->seqno
, seqno
) > 100) {
910 /* Probably a source that lost its seqno. Let it time-out. */
914 if(force
|| !route
|| route_metric(route
) >= metric
+ 512) {
915 send_unicast_multihop_request(neigh
, src
->prefix
, src
->plen
,
916 src
->metric
>= INFINITY
?
918 seqno_plus(src
->seqno
, 1),
923 /* This takes a feasible route and decides whether to install it.
924 This uses the strong ordering, which is defined by sm <= sm' AND
925 m <= m'. This ordering is not total, which is what causes
929 consider_route(struct babel_route
*route
)
931 struct babel_route
*installed
;
932 struct xroute
*xroute
;
937 if(!route_feasible(route
))
940 xroute
= find_xroute(route
->src
->prefix
, route
->src
->plen
);
944 installed
= find_installed_route(route
->src
->prefix
, route
->src
->plen
);
946 if(installed
== NULL
)
949 if(route_metric(route
) >= INFINITY
)
952 if(route_metric(installed
) >= INFINITY
)
955 if(route_metric(installed
) >= route_metric(route
) &&
956 route_smoothed_metric(installed
) > route_smoothed_metric(route
))
962 switch_routes(installed
, route
);
963 if(installed
&& route
->installed
)
964 send_triggered_update(route
, installed
->src
, route_metric(installed
));
966 send_update(NULL
, 1, route
->src
->prefix
, route
->src
->plen
);
971 retract_neighbour_routes(struct neighbour
*neigh
)
975 for(i
= 0; i
< route_slots
; i
++) {
976 struct babel_route
*r
= routes
[i
];
978 if(r
->neigh
== neigh
) {
979 if(r
->refmetric
!= INFINITY
) {
980 unsigned short oldmetric
= route_metric(r
);
982 if(oldmetric
!= INFINITY
)
983 route_changed(r
, r
->src
, oldmetric
);
992 send_triggered_update(struct babel_route
*route
, struct source
*oldsrc
,
995 unsigned newmetric
, diff
;
996 /* 1 means send speedily, 2 means resend */
999 if(!route
->installed
)
1002 newmetric
= route_metric(route
);
1004 newmetric
>= oldmetric
? newmetric
- oldmetric
: oldmetric
- newmetric
;
1006 if(route
->src
!= oldsrc
|| (oldmetric
< INFINITY
&& newmetric
>= INFINITY
))
1007 /* Switching sources can cause transient routing loops.
1008 Retractions can cause blackholes. */
1010 else if(newmetric
> oldmetric
&& oldmetric
< 6 * 256 && diff
>= 512)
1011 /* Route getting significantly worse */
1013 else if(unsatisfied_request(route
->src
->prefix
, route
->src
->plen
,
1014 route
->seqno
, route
->src
->id
))
1015 /* Make sure that requests are satisfied speedily */
1017 else if(oldmetric
>= INFINITY
&& newmetric
< INFINITY
)
1020 else if(newmetric
< oldmetric
&& diff
< 1024)
1021 /* Route getting better. This may be a transient fluctuation, so
1022 don't advertise it to avoid making routes unfeasible later on. */
1025 /* Don't fret about trivialities */
1031 send_update_resend(NULL
, route
->src
->prefix
, route
->src
->plen
);
1033 send_update(NULL
, urgent
, route
->src
->prefix
, route
->src
->plen
);
1035 if(oldmetric
< INFINITY
) {
1036 if(newmetric
>= oldmetric
+ 512) {
1037 send_request_resend(NULL
, route
->src
->prefix
, route
->src
->plen
,
1038 route
->src
->metric
>= INFINITY
?
1040 seqno_plus(route
->src
->seqno
, 1),
1042 } else if(newmetric
>= oldmetric
+ 288) {
1043 send_request(NULL
, route
->src
->prefix
, route
->src
->plen
);
1048 /* A route has just changed. Decide whether to switch to a different route or
1051 route_changed(struct babel_route
*route
,
1052 struct source
*oldsrc
, unsigned short oldmetric
)
1054 if(route
->installed
) {
1055 struct babel_route
*better_route
;
1056 /* Do this unconditionally -- microoptimisation is not worth it. */
1058 find_best_route(route
->src
->prefix
, route
->src
->plen
, 1, NULL
);
1059 if(better_route
&& route_metric(better_route
) < route_metric(route
))
1060 consider_route(better_route
);
1063 if(route
->installed
) {
1064 /* We didn't change routes after all. */
1065 send_triggered_update(route
, oldsrc
, oldmetric
);
1067 /* Reconsider routes even when their metric didn't decrease,
1068 they may not have been feasible before. */
1069 consider_route(route
);
1073 /* We just lost the installed route to a given destination. */
1075 route_lost(struct source
*src
, unsigned oldmetric
)
1077 struct babel_route
*new_route
;
1078 new_route
= find_best_route(src
->prefix
, src
->plen
, 1, NULL
);
1080 consider_route(new_route
);
1081 } else if(oldmetric
< INFINITY
) {
1082 /* Avoid creating a blackhole. */
1083 send_update_resend(NULL
, src
->prefix
, src
->plen
);
1084 /* If the route was usable enough, try to get an alternate one.
1085 If it was not, we could be dealing with oscillations around
1086 the value of INFINITY. */
1087 if(oldmetric
<= INFINITY
/ 2)
1088 send_request_resend(NULL
, src
->prefix
, src
->plen
,
1089 src
->metric
>= INFINITY
?
1090 src
->seqno
: seqno_plus(src
->seqno
, 1),
1095 /* This is called periodically to flush old routes. It will also send
1096 requests for routes that are about to expire. */
1100 struct babel_route
*r
;
1103 debugf(BABEL_DEBUG_COMMON
,"Expiring old routes.");
1106 while(i
< route_slots
) {
1109 /* Protect against clock being stepped. */
1110 if(r
->time
> babel_now
.tv_sec
|| route_old(r
)) {
1115 update_route_metric(r
);
1117 if(r
->installed
&& r
->refmetric
< INFINITY
) {
1119 /* Route about to expire, send a request. */
1120 send_unicast_request(r
->neigh
,
1121 r
->src
->prefix
, r
->src
->plen
);