2 Copyright (c) 2007, 2008 by Juliusz Chroboczek
3 Copyright 2011 by Matthieu Boutier and Juliusz Chroboczek
5 Permission is hereby granted, free of charge, to any person obtaining a copy
6 of this software and associated documentation files (the "Software"), to deal
7 in the Software without restriction, including without limitation the rights
8 to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
9 copies of the Software, and to permit persons to whom the Software is
10 furnished to do so, subject to the following conditions:
12 The above copyright notice and this permission notice shall be included in
13 all copies or substantial portions of the Software.
15 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
16 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
17 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
18 AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
19 LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
20 OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
30 #include "babel_interface.h"
32 #include "neighbour.h"
38 static void consider_route(struct babel_route
*route
);
40 struct babel_route
**routes
= NULL
;
41 static int route_slots
= 0, max_route_slots
= 0;
42 int kernel_metric
= 0;
43 int diversity_kind
= DIVERSITY_NONE
;
44 int diversity_factor
= BABEL_DEFAULT_DIVERSITY_FACTOR
;
45 int keep_unfeasible
= 0;
47 int smoothing_half_life
= 0;
48 static int two_to_the_one_over_hl
= 0; /* 2^(1/hl) * 0x10000 */
50 /* We maintain a list of "slots", ordered by prefix. Every slot
51 contains a linked list of the routes to this prefix, with the
52 installed route, if any, at the head of the list. */
55 route_compare(const unsigned char *prefix
, unsigned char plen
,
56 struct babel_route
*route
)
58 int i
= memcmp(prefix
, route
->src
->prefix
, 16);
62 if(plen
< route
->src
->plen
)
64 else if(plen
> route
->src
->plen
)
70 /* Performs binary search, returns -1 in case of failure. In the latter
71 case, new_return is the place where to insert the new element. */
74 find_route_slot(const unsigned char *prefix
, unsigned char plen
,
85 p
= 0; g
= route_slots
- 1;
89 c
= route_compare(prefix
, plen
, routes
[m
]);
105 find_route(const unsigned char *prefix
, unsigned char plen
,
106 struct neighbour
*neigh
, const unsigned char *nexthop
)
108 struct babel_route
*route
;
109 int i
= find_route_slot(prefix
, plen
, NULL
);
117 if(route
->neigh
== neigh
&& memcmp(route
->nexthop
, nexthop
, 16) == 0)
126 find_installed_route(const unsigned char *prefix
, unsigned char plen
)
128 int i
= find_route_slot(prefix
, plen
, NULL
);
130 if(i
>= 0 && routes
[i
]->installed
)
136 /* Returns an overestimate of the number of installed routes. */
138 installed_routes_estimate(void)
144 resize_route_table(int new_slots
)
146 struct babel_route
**new_routes
;
147 assert(new_slots
>= route_slots
);
153 new_routes
= realloc(routes
, new_slots
* sizeof(struct babel_route
*));
154 if(new_routes
== NULL
)
158 max_route_slots
= new_slots
;
163 /* Insert a route into the table. If successful, retains the route.
164 On failure, caller must free the route. */
165 static struct babel_route
*
166 insert_route(struct babel_route
*route
)
170 assert(!route
->installed
);
172 i
= find_route_slot(route
->src
->prefix
, route
->src
->plen
, &n
);
175 if(route_slots
>= max_route_slots
)
176 resize_route_table(max_route_slots
< 1 ? 8 : 2 * max_route_slots
);
177 if(route_slots
>= max_route_slots
)
182 memmove(routes
+ n
+ 1, routes
+ n
,
183 (route_slots
- n
) * sizeof(struct babel_route
*));
187 struct babel_route
*r
;
199 flush_route(struct babel_route
*route
)
206 oldmetric
= route_metric(route
);
209 if(route
->installed
) {
210 uninstall_route(route
);
214 i
= find_route_slot(route
->src
->prefix
, route
->src
->plen
, NULL
);
215 assert(i
>= 0 && i
< route_slots
);
217 if(route
== routes
[i
]) {
218 routes
[i
] = route
->next
;
222 if(routes
[i
] == NULL
) {
223 if(i
< route_slots
- 1)
224 memmove(routes
+ i
, routes
+ i
+ 1,
225 (route_slots
- i
- 1) * sizeof(struct babel_route
*));
226 routes
[route_slots
- 1] = NULL
;
231 resize_route_table(0);
232 else if(max_route_slots
> 8 && route_slots
< max_route_slots
/ 4)
233 resize_route_table(max_route_slots
/ 2);
235 struct babel_route
*r
= routes
[i
];
236 while(r
->next
!= route
)
238 r
->next
= route
->next
;
244 route_lost(src
, oldmetric
);
254 /* Start from the end, to avoid shifting the table. */
257 while(i
< route_slots
) {
258 /* Uninstall first, to avoid calling route_lost. */
259 if(routes
[i
]->installed
)
260 uninstall_route(routes
[i
]);
261 flush_route(routes
[i
]);
266 check_sources_released();
270 flush_neighbour_routes(struct neighbour
*neigh
)
275 while(i
< route_slots
) {
276 struct babel_route
*r
;
279 if(r
->neigh
== neigh
) {
292 flush_interface_routes(struct interface
*ifp
, int v4only
)
297 while(i
< route_slots
) {
298 struct babel_route
*r
;
301 if(r
->neigh
->ifp
== ifp
&&
302 (!v4only
|| v4mapped(r
->nexthop
))) {
314 struct route_stream
{
317 struct babel_route
*next
;
321 struct route_stream
*
322 route_stream(int installed
)
324 struct route_stream
*stream
;
326 stream
= malloc(sizeof(struct route_stream
));
330 stream
->installed
= installed
;
331 stream
->index
= installed
? 0 : -1;
338 route_stream_next(struct route_stream
*stream
)
340 if(stream
->installed
) {
341 while(stream
->index
< route_slots
&& !routes
[stream
->index
]->installed
)
344 if(stream
->index
< route_slots
)
345 return routes
[stream
->index
++];
349 struct babel_route
*next
;
352 if(stream
->index
>= route_slots
)
354 stream
->next
= routes
[stream
->index
];
357 stream
->next
= next
->next
;
363 route_stream_done(struct route_stream
*stream
)
369 metric_to_kernel(int metric
)
371 return metric
< INFINITY
? kernel_metric
: KERNEL_INFINITY
;
374 /* This is used to maintain the invariant that the installed route is at
375 the head of the list. */
377 move_installed_route(struct babel_route
*route
, int i
)
379 assert(i
>= 0 && i
< route_slots
);
380 assert(route
->installed
);
382 if(route
!= routes
[i
]) {
383 struct babel_route
*r
= routes
[i
];
384 while(r
->next
!= route
)
386 r
->next
= route
->next
;
387 route
->next
= routes
[i
];
393 install_route(struct babel_route
*route
)
400 if(!route_feasible(route
))
401 zlog_err("WARNING: installing unfeasible route "
402 "(this shouldn't happen).");
404 i
= find_route_slot(route
->src
->prefix
, route
->src
->plen
, NULL
);
405 assert(i
>= 0 && i
< route_slots
);
407 if(routes
[i
] != route
&& routes
[i
]->installed
) {
408 zlog_err("WARNING: attempting to install duplicate route "
409 "(this shouldn't happen).");
413 rc
= kernel_route(ROUTE_ADD
, route
->src
->prefix
, route
->src
->plen
,
415 route
->neigh
->ifp
->ifindex
,
416 metric_to_kernel(route_metric(route
)), NULL
, 0, 0);
419 zlog_err("kernel_route(ADD): %s", safe_strerror(errno
));
423 route
->installed
= 1;
424 move_installed_route(route
, i
);
429 uninstall_route(struct babel_route
*route
)
433 if(!route
->installed
)
436 rc
= kernel_route(ROUTE_FLUSH
, route
->src
->prefix
, route
->src
->plen
,
438 route
->neigh
->ifp
->ifindex
,
439 metric_to_kernel(route_metric(route
)), NULL
, 0, 0);
441 zlog_err("kernel_route(FLUSH): %s", safe_strerror(errno
));
443 route
->installed
= 0;
446 /* This is equivalent to uninstall_route followed with install_route,
447 but without the race condition. The destination of both routes
451 switch_routes(struct babel_route
*old
, struct babel_route
*new)
463 if(!route_feasible(new))
464 zlog_err("WARNING: switching to unfeasible route "
465 "(this shouldn't happen).");
467 rc
= kernel_route(ROUTE_MODIFY
, old
->src
->prefix
, old
->src
->plen
,
468 old
->nexthop
, old
->neigh
->ifp
->ifindex
,
469 metric_to_kernel(route_metric(old
)),
470 new->nexthop
, new->neigh
->ifp
->ifindex
,
471 metric_to_kernel(route_metric(new)));
473 zlog_err("kernel_route(MODIFY): %s", safe_strerror(errno
));
479 move_installed_route(new, find_route_slot(new->src
->prefix
, new->src
->plen
,
484 change_route_metric(struct babel_route
*route
,
485 unsigned refmetric
, unsigned cost
, unsigned add
)
488 int newmetric
= MIN(refmetric
+ cost
+ add
, INFINITY
);
490 old
= metric_to_kernel(route_metric(route
));
491 new = metric_to_kernel(newmetric
);
493 if(route
->installed
&& old
!= new) {
495 rc
= kernel_route(ROUTE_MODIFY
, route
->src
->prefix
, route
->src
->plen
,
496 route
->nexthop
, route
->neigh
->ifp
->ifindex
,
498 route
->nexthop
, route
->neigh
->ifp
->ifindex
,
501 zlog_err("kernel_route(MODIFY metric): %s", safe_strerror(errno
));
506 /* Update route->smoothed_metric using the old metric. */
507 route_smoothed_metric(route
);
509 route
->refmetric
= refmetric
;
511 route
->add_metric
= add
;
513 if(smoothing_half_life
== 0) {
514 route
->smoothed_metric
= route_metric(route
);
515 route
->smoothed_metric_time
= babel_now
.tv_sec
;
520 retract_route(struct babel_route
*route
)
522 /* We cannot simply remove the route from the kernel, as that might
523 cause a routing loop -- see RFC 6126 Sections 2.8 and 3.5.5. */
524 change_route_metric(route
, INFINITY
, INFINITY
, 0);
528 route_feasible(struct babel_route
*route
)
530 return update_feasible(route
->src
, route
->seqno
, route
->refmetric
);
534 route_old(struct babel_route
*route
)
536 return route
->time
< babel_now
.tv_sec
- route
->hold_time
* 7 / 8;
540 route_expired(struct babel_route
*route
)
542 return route
->time
< babel_now
.tv_sec
- route
->hold_time
;
546 channels_interfere(int ch1
, int ch2
)
548 if(ch1
== BABEL_IF_CHANNEL_NONINTERFERING
549 || ch2
== BABEL_IF_CHANNEL_NONINTERFERING
)
551 if(ch1
== BABEL_IF_CHANNEL_INTERFERING
552 || ch2
== BABEL_IF_CHANNEL_INTERFERING
)
558 route_interferes(struct babel_route
*route
, struct interface
*ifp
)
560 struct babel_interface
*babel_ifp
= NULL
;
561 switch(diversity_kind
) {
564 case DIVERSITY_INTERFACE_1
:
565 return route
->neigh
->ifp
== ifp
;
566 case DIVERSITY_CHANNEL_1
:
567 case DIVERSITY_CHANNEL
:
568 if(route
->neigh
->ifp
== ifp
)
570 babel_ifp
= babel_get_if_nfo(ifp
);
571 if(channels_interfere(babel_ifp
->channel
,
572 babel_get_if_nfo(route
->neigh
->ifp
)->channel
))
574 if(diversity_kind
== DIVERSITY_CHANNEL
) {
576 for(i
= 0; i
< DIVERSITY_HOPS
; i
++) {
577 if(route
->channels
[i
] == 0)
579 if(channels_interfere(babel_ifp
->channel
, route
->channels
[i
]))
585 zlog_err("Unknown kind of diversity.");
591 update_feasible(struct source
*src
,
592 unsigned short seqno
, unsigned short refmetric
)
597 if(src
->time
< babel_now
.tv_sec
- SOURCE_GC_TIME
)
598 /* Never mind what is probably stale data */
601 if(refmetric
>= INFINITY
)
602 /* Retractions are always feasible */
605 return (seqno_compare(seqno
, src
->seqno
) > 0 ||
606 (src
->seqno
== seqno
&& refmetric
< src
->metric
));
610 change_smoothing_half_life(int half_life
)
613 smoothing_half_life
= 0;
614 two_to_the_one_over_hl
= 0;
618 smoothing_half_life
= half_life
;
619 switch(smoothing_half_life
) {
620 case 1: two_to_the_one_over_hl
= 131072; break;
621 case 2: two_to_the_one_over_hl
= 92682; break;
622 case 3: two_to_the_one_over_hl
= 82570; break;
623 case 4: two_to_the_one_over_hl
= 77935; break;
625 /* 2^(1/x) is 1 + log(2)/x + O(1/x^2) at infinity. */
626 two_to_the_one_over_hl
= 0x10000 + 45426 / half_life
;
630 /* Update the smoothed metric, return the new value. */
632 route_smoothed_metric(struct babel_route
*route
)
634 int metric
= route_metric(route
);
636 if(smoothing_half_life
<= 0 || /* no smoothing */
637 metric
>= INFINITY
|| /* route retracted */
638 route
->smoothed_metric_time
> babel_now
.tv_sec
|| /* clock stepped */
639 route
->smoothed_metric
== metric
) { /* already converged */
640 route
->smoothed_metric
= metric
;
641 route
->smoothed_metric_time
= babel_now
.tv_sec
;
644 /* We randomise the computation, to minimise global synchronisation
645 and hence oscillations. */
646 while(route
->smoothed_metric_time
<=
647 babel_now
.tv_sec
- smoothing_half_life
) {
648 diff
= metric
- route
->smoothed_metric
;
649 route
->smoothed_metric
+= roughly(diff
) / 2;
650 route
->smoothed_metric_time
+= smoothing_half_life
;
652 while(route
->smoothed_metric_time
< babel_now
.tv_sec
) {
653 diff
= metric
- route
->smoothed_metric
;
654 route
->smoothed_metric
+=
655 roughly(diff
) * (two_to_the_one_over_hl
- 0x10000) / 0x10000;
656 route
->smoothed_metric_time
++;
659 diff
= metric
- route
->smoothed_metric
;
660 if(diff
> -4 && diff
< 4)
661 route
->smoothed_metric
= metric
;
664 /* change_route_metric relies on this */
665 assert(route
->smoothed_metric_time
== babel_now
.tv_sec
);
666 return route
->smoothed_metric
;
670 route_acceptable(struct babel_route
*route
, int feasible
,
671 struct neighbour
*exclude
)
673 if(route_expired(route
))
675 if(feasible
&& !route_feasible(route
))
677 if(exclude
&& route
->neigh
== exclude
)
682 /* Find the best route according to the weak ordering. Any
683 linearisation of the strong ordering (see consider_route) will do,
684 we use sm <= sm'. We could probably use a lexical ordering, but
685 that's probably overkill. */
688 find_best_route(const unsigned char *prefix
, unsigned char plen
, int feasible
,
689 struct neighbour
*exclude
)
691 struct babel_route
*route
= NULL
, *r
= NULL
;
692 int i
= find_route_slot(prefix
, plen
, NULL
);
698 while(route
&& !route_acceptable(route
, feasible
, exclude
))
706 if(route_acceptable(r
, feasible
, exclude
) &&
707 (route_smoothed_metric(r
) < route_smoothed_metric(route
)))
716 update_route_metric(struct babel_route
*route
)
718 int oldmetric
= route_metric(route
);
719 int old_smoothed_metric
= route_smoothed_metric(route
);
721 if(route_expired(route
)) {
722 if(route
->refmetric
< INFINITY
) {
723 route
->seqno
= seqno_plus(route
->src
->seqno
, 1);
724 retract_route(route
);
725 if(oldmetric
< INFINITY
)
726 route_changed(route
, route
->src
, oldmetric
);
729 struct neighbour
*neigh
= route
->neigh
;
730 int add_metric
= input_filter(route
->src
->id
,
731 route
->src
->prefix
, route
->src
->plen
,
733 neigh
->ifp
->ifindex
);
734 change_route_metric(route
, route
->refmetric
,
735 neighbour_cost(route
->neigh
), add_metric
);
736 if(route_metric(route
) != oldmetric
||
737 route_smoothed_metric(route
) != old_smoothed_metric
)
738 route_changed(route
, route
->src
, oldmetric
);
742 /* Called whenever a neighbour's cost changes, to update the metric of
743 all routes through that neighbour. */
745 update_neighbour_metric(struct neighbour
*neigh
, int changed
)
751 for(i
= 0; i
< route_slots
; i
++) {
752 struct babel_route
*r
= routes
[i
];
754 if(r
->neigh
== neigh
)
755 update_route_metric(r
);
763 update_interface_metric(struct interface
*ifp
)
767 for(i
= 0; i
< route_slots
; i
++) {
768 struct babel_route
*r
= routes
[i
];
770 if(r
->neigh
->ifp
== ifp
)
771 update_route_metric(r
);
777 /* This is called whenever we receive an update. */
779 update_route(const unsigned char *router_id
,
780 const unsigned char *prefix
, unsigned char plen
,
781 unsigned short seqno
, unsigned short refmetric
,
782 unsigned short interval
,
783 struct neighbour
*neigh
, const unsigned char *nexthop
,
784 const unsigned char *channels
, int channels_len
)
786 struct babel_route
*route
;
788 int metric
, feasible
;
790 int hold_time
= MAX((4 * interval
) / 100 + interval
/ 50, 15);
792 if(memcmp(router_id
, myid
, 8) == 0)
795 if(martian_prefix(prefix
, plen
)) {
796 zlog_err("Rejecting martian route to %s through %s.",
797 format_prefix(prefix
, plen
), format_address(nexthop
));
801 add_metric
= input_filter(router_id
, prefix
, plen
,
802 neigh
->address
, neigh
->ifp
->ifindex
);
803 if(add_metric
>= INFINITY
)
806 route
= find_route(prefix
, plen
, neigh
, nexthop
);
808 if(route
&& memcmp(route
->src
->id
, router_id
, 8) == 0)
809 /* Avoid scanning the source table. */
812 src
= find_source(router_id
, prefix
, plen
, 1, seqno
);
817 feasible
= update_feasible(src
, seqno
, refmetric
);
818 metric
= MIN((int)refmetric
+ neighbour_cost(neigh
) + add_metric
, INFINITY
);
821 struct source
*oldsrc
;
822 unsigned short oldmetric
;
826 oldmetric
= route_metric(route
);
828 /* If a successor switches sources, we must accept his update even
829 if it makes a route unfeasible in order to break any routing loops
830 in a timely manner. If the source remains the same, we ignore
832 if(!feasible
&& route
->installed
) {
833 debugf(BABEL_DEBUG_COMMON
,"Unfeasible update for installed route to %s "
834 "(%s %d %d -> %s %d %d).",
835 format_prefix(src
->prefix
, src
->plen
),
836 format_eui64(route
->src
->id
),
837 route
->seqno
, route
->refmetric
,
838 format_eui64(src
->id
), seqno
, refmetric
);
839 if(src
!= route
->src
) {
840 uninstall_route(route
);
845 route
->src
= retain_source(src
);
846 if((feasible
|| keep_unfeasible
) && refmetric
< INFINITY
)
847 route
->time
= babel_now
.tv_sec
;
848 route
->seqno
= seqno
;
850 memset(&route
->channels
, 0, sizeof(route
->channels
));
852 memcpy(&route
->channels
, channels
,
853 MIN(channels_len
, DIVERSITY_HOPS
));
855 change_route_metric(route
,
856 refmetric
, neighbour_cost(neigh
), add_metric
);
857 route
->hold_time
= hold_time
;
859 route_changed(route
, oldsrc
, oldmetric
);
861 route_lost(oldsrc
, oldmetric
);
864 send_unfeasible_request(neigh
, route
->installed
&& route_old(route
),
866 release_source(oldsrc
);
868 struct babel_route
*new_route
;
870 if(refmetric
>= INFINITY
)
871 /* Somebody's retracting a route we never saw. */
874 send_unfeasible_request(neigh
, 0, seqno
, metric
, src
);
879 route
= malloc(sizeof(struct babel_route
));
881 perror("malloc(route)");
885 route
->src
= retain_source(src
);
886 route
->refmetric
= refmetric
;
887 route
->cost
= neighbour_cost(neigh
);
888 route
->add_metric
= add_metric
;
889 route
->seqno
= seqno
;
890 route
->neigh
= neigh
;
891 memcpy(route
->nexthop
, nexthop
, 16);
892 route
->time
= babel_now
.tv_sec
;
893 route
->hold_time
= hold_time
;
894 route
->smoothed_metric
= MAX(route_metric(route
), INFINITY
/ 2);
895 route
->smoothed_metric_time
= babel_now
.tv_sec
;
896 route
->installed
= 0;
897 memset(&route
->channels
, 0, sizeof(route
->channels
));
899 memcpy(&route
->channels
, channels
,
900 MIN(channels_len
, DIVERSITY_HOPS
));
902 new_route
= insert_route(route
);
903 if(new_route
== NULL
) {
904 zlog_err("Couldn't insert route.");
908 consider_route(route
);
913 /* We just received an unfeasible update. If it's any good, send
914 a request for a new seqno. */
916 send_unfeasible_request(struct neighbour
*neigh
, int force
,
917 unsigned short seqno
, unsigned short metric
,
920 struct babel_route
*route
= find_installed_route(src
->prefix
, src
->plen
);
922 if(seqno_minus(src
->seqno
, seqno
) > 100) {
923 /* Probably a source that lost its seqno. Let it time-out. */
927 if(force
|| !route
|| route_metric(route
) >= metric
+ 512) {
928 send_unicast_multihop_request(neigh
, src
->prefix
, src
->plen
,
929 src
->metric
>= INFINITY
?
931 seqno_plus(src
->seqno
, 1),
936 /* This takes a feasible route and decides whether to install it.
937 This uses the strong ordering, which is defined by sm <= sm' AND
938 m <= m'. This ordering is not total, which is what causes
942 consider_route(struct babel_route
*route
)
944 struct babel_route
*installed
;
945 struct xroute
*xroute
;
950 if(!route_feasible(route
))
953 xroute
= find_xroute(route
->src
->prefix
, route
->src
->plen
);
957 installed
= find_installed_route(route
->src
->prefix
, route
->src
->plen
);
959 if(installed
== NULL
)
962 if(route_metric(route
) >= INFINITY
)
965 if(route_metric(installed
) >= INFINITY
)
968 if(route_metric(installed
) >= route_metric(route
) &&
969 route_smoothed_metric(installed
) > route_smoothed_metric(route
))
975 switch_routes(installed
, route
);
976 if(installed
&& route
->installed
)
977 send_triggered_update(route
, installed
->src
, route_metric(installed
));
979 send_update(NULL
, 1, route
->src
->prefix
, route
->src
->plen
);
984 retract_neighbour_routes(struct neighbour
*neigh
)
988 for(i
= 0; i
< route_slots
; i
++) {
989 struct babel_route
*r
= routes
[i
];
991 if(r
->neigh
== neigh
) {
992 if(r
->refmetric
!= INFINITY
) {
993 unsigned short oldmetric
= route_metric(r
);
995 if(oldmetric
!= INFINITY
)
996 route_changed(r
, r
->src
, oldmetric
);
1005 send_triggered_update(struct babel_route
*route
, struct source
*oldsrc
,
1008 unsigned newmetric
, diff
;
1009 /* 1 means send speedily, 2 means resend */
1012 if(!route
->installed
)
1015 newmetric
= route_metric(route
);
1017 newmetric
>= oldmetric
? newmetric
- oldmetric
: oldmetric
- newmetric
;
1019 if(route
->src
!= oldsrc
|| (oldmetric
< INFINITY
&& newmetric
>= INFINITY
))
1020 /* Switching sources can cause transient routing loops.
1021 Retractions can cause blackholes. */
1023 else if(newmetric
> oldmetric
&& oldmetric
< 6 * 256 && diff
>= 512)
1024 /* Route getting significantly worse */
1026 else if(unsatisfied_request(route
->src
->prefix
, route
->src
->plen
,
1027 route
->seqno
, route
->src
->id
))
1028 /* Make sure that requests are satisfied speedily */
1030 else if(oldmetric
>= INFINITY
&& newmetric
< INFINITY
)
1033 else if(newmetric
< oldmetric
&& diff
< 1024)
1034 /* Route getting better. This may be a transient fluctuation, so
1035 don't advertise it to avoid making routes unfeasible later on. */
1038 /* Don't fret about trivialities */
1044 send_update_resend(NULL
, route
->src
->prefix
, route
->src
->plen
);
1046 send_update(NULL
, urgent
, route
->src
->prefix
, route
->src
->plen
);
1048 if(oldmetric
< INFINITY
) {
1049 if(newmetric
>= oldmetric
+ 512) {
1050 send_request_resend(NULL
, route
->src
->prefix
, route
->src
->plen
,
1051 route
->src
->metric
>= INFINITY
?
1053 seqno_plus(route
->src
->seqno
, 1),
1055 } else if(newmetric
>= oldmetric
+ 288) {
1056 send_request(NULL
, route
->src
->prefix
, route
->src
->plen
);
1061 /* A route has just changed. Decide whether to switch to a different route or
1064 route_changed(struct babel_route
*route
,
1065 struct source
*oldsrc
, unsigned short oldmetric
)
1067 if(route
->installed
) {
1068 struct babel_route
*better_route
;
1069 /* Do this unconditionally -- microoptimisation is not worth it. */
1071 find_best_route(route
->src
->prefix
, route
->src
->plen
, 1, NULL
);
1072 if(better_route
&& route_metric(better_route
) < route_metric(route
))
1073 consider_route(better_route
);
1076 if(route
->installed
) {
1077 /* We didn't change routes after all. */
1078 send_triggered_update(route
, oldsrc
, oldmetric
);
1080 /* Reconsider routes even when their metric didn't decrease,
1081 they may not have been feasible before. */
1082 consider_route(route
);
1086 /* We just lost the installed route to a given destination. */
1088 route_lost(struct source
*src
, unsigned oldmetric
)
1090 struct babel_route
*new_route
;
1091 new_route
= find_best_route(src
->prefix
, src
->plen
, 1, NULL
);
1093 consider_route(new_route
);
1094 } else if(oldmetric
< INFINITY
) {
1095 /* Avoid creating a blackhole. */
1096 send_update_resend(NULL
, src
->prefix
, src
->plen
);
1097 /* If the route was usable enough, try to get an alternate one.
1098 If it was not, we could be dealing with oscillations around
1099 the value of INFINITY. */
1100 if(oldmetric
<= INFINITY
/ 2)
1101 send_request_resend(NULL
, src
->prefix
, src
->plen
,
1102 src
->metric
>= INFINITY
?
1103 src
->seqno
: seqno_plus(src
->seqno
, 1),
1108 /* This is called periodically to flush old routes. It will also send
1109 requests for routes that are about to expire. */
1113 struct babel_route
*r
;
1116 debugf(BABEL_DEBUG_COMMON
,"Expiring old routes.");
1119 while(i
< route_slots
) {
1122 /* Protect against clock being stepped. */
1123 if(r
->time
> babel_now
.tv_sec
|| route_old(r
)) {
1128 update_route_metric(r
);
1130 if(r
->installed
&& r
->refmetric
< INFINITY
) {
1132 /* Route about to expire, send a request. */
1133 send_unicast_request(r
->neigh
,
1134 r
->src
->prefix
, r
->src
->plen
);