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
)
181 memmove(routes
+ n
+ 1, routes
+ n
,
182 (route_slots
- n
) * sizeof(struct babel_route
*));
186 struct babel_route
*r
;
198 flush_route(struct babel_route
*route
)
205 oldmetric
= route_metric(route
);
208 if(route
->installed
) {
209 uninstall_route(route
);
213 i
= find_route_slot(route
->src
->prefix
, route
->src
->plen
, NULL
);
214 assert(i
>= 0 && i
< route_slots
);
216 if(route
== routes
[i
]) {
217 routes
[i
] = route
->next
;
221 if(routes
[i
] == NULL
) {
222 if(i
< route_slots
- 1)
223 memmove(routes
+ i
, routes
+ i
+ 1,
224 (route_slots
- i
- 1) * sizeof(struct babel_route
*));
225 routes
[route_slots
- 1] = NULL
;
230 resize_route_table(0);
231 else if(max_route_slots
> 8 && route_slots
< max_route_slots
/ 4)
232 resize_route_table(max_route_slots
/ 2);
234 struct babel_route
*r
= routes
[i
];
235 while(r
->next
!= route
)
237 r
->next
= route
->next
;
243 route_lost(src
, oldmetric
);
253 /* Start from the end, to avoid shifting the table. */
256 while(i
< route_slots
) {
257 /* Uninstall first, to avoid calling route_lost. */
258 if(routes
[i
]->installed
)
259 uninstall_route(routes
[i
]);
260 flush_route(routes
[i
]);
265 check_sources_released();
269 flush_neighbour_routes(struct neighbour
*neigh
)
274 while(i
< route_slots
) {
275 struct babel_route
*r
;
278 if(r
->neigh
== neigh
) {
291 flush_interface_routes(struct interface
*ifp
, int v4only
)
296 while(i
< route_slots
) {
297 struct babel_route
*r
;
300 if(r
->neigh
->ifp
== ifp
&&
301 (!v4only
|| v4mapped(r
->nexthop
))) {
313 struct route_stream
{
316 struct babel_route
*next
;
320 struct route_stream
*
321 route_stream(int installed
)
323 struct route_stream
*stream
;
325 stream
= malloc(sizeof(struct route_stream
));
329 stream
->installed
= installed
;
330 stream
->index
= installed
? 0 : -1;
337 route_stream_next(struct route_stream
*stream
)
339 if(stream
->installed
) {
340 while(stream
->index
< route_slots
&& !routes
[stream
->index
]->installed
)
343 if(stream
->index
< route_slots
)
344 return routes
[stream
->index
++];
348 struct babel_route
*next
;
351 if(stream
->index
>= route_slots
)
353 stream
->next
= routes
[stream
->index
];
356 stream
->next
= next
->next
;
362 route_stream_done(struct route_stream
*stream
)
368 metric_to_kernel(int metric
)
370 return metric
< INFINITY
? kernel_metric
: KERNEL_INFINITY
;
373 /* This is used to maintain the invariant that the installed route is at
374 the head of the list. */
376 move_installed_route(struct babel_route
*route
, int i
)
378 assert(i
>= 0 && i
< route_slots
);
379 assert(route
->installed
);
381 if(route
!= routes
[i
]) {
382 struct babel_route
*r
= routes
[i
];
383 while(r
->next
!= route
)
385 r
->next
= route
->next
;
386 route
->next
= routes
[i
];
392 install_route(struct babel_route
*route
)
399 if(!route_feasible(route
))
400 zlog_err("WARNING: installing unfeasible route "
401 "(this shouldn't happen).");
403 i
= find_route_slot(route
->src
->prefix
, route
->src
->plen
, NULL
);
404 assert(i
>= 0 && i
< route_slots
);
406 if(routes
[i
] != route
&& routes
[i
]->installed
) {
407 zlog_err("WARNING: attempting to install duplicate route "
408 "(this shouldn't happen).");
412 rc
= kernel_route(ROUTE_ADD
, route
->src
->prefix
, route
->src
->plen
,
414 route
->neigh
->ifp
->ifindex
,
415 metric_to_kernel(route_metric(route
)), NULL
, 0, 0);
418 zlog_err("kernel_route(ADD): %s", safe_strerror(errno
));
422 route
->installed
= 1;
423 move_installed_route(route
, i
);
428 uninstall_route(struct babel_route
*route
)
432 if(!route
->installed
)
435 rc
= kernel_route(ROUTE_FLUSH
, route
->src
->prefix
, route
->src
->plen
,
437 route
->neigh
->ifp
->ifindex
,
438 metric_to_kernel(route_metric(route
)), NULL
, 0, 0);
440 zlog_err("kernel_route(FLUSH): %s", safe_strerror(errno
));
442 route
->installed
= 0;
445 /* This is equivalent to uninstall_route followed with install_route,
446 but without the race condition. The destination of both routes
450 switch_routes(struct babel_route
*old
, struct babel_route
*new)
462 if(!route_feasible(new))
463 zlog_err("WARNING: switching to unfeasible route "
464 "(this shouldn't happen).");
466 rc
= kernel_route(ROUTE_MODIFY
, old
->src
->prefix
, old
->src
->plen
,
467 old
->nexthop
, old
->neigh
->ifp
->ifindex
,
468 metric_to_kernel(route_metric(old
)),
469 new->nexthop
, new->neigh
->ifp
->ifindex
,
470 metric_to_kernel(route_metric(new)));
472 zlog_err("kernel_route(MODIFY): %s", safe_strerror(errno
));
478 move_installed_route(new, find_route_slot(new->src
->prefix
, new->src
->plen
,
483 change_route_metric(struct babel_route
*route
,
484 unsigned refmetric
, unsigned cost
, unsigned add
)
487 int newmetric
= MIN(refmetric
+ cost
+ add
, INFINITY
);
489 old
= metric_to_kernel(route_metric(route
));
490 new = metric_to_kernel(newmetric
);
492 if(route
->installed
&& old
!= new) {
494 rc
= kernel_route(ROUTE_MODIFY
, route
->src
->prefix
, route
->src
->plen
,
495 route
->nexthop
, route
->neigh
->ifp
->ifindex
,
497 route
->nexthop
, route
->neigh
->ifp
->ifindex
,
500 zlog_err("kernel_route(MODIFY metric): %s", safe_strerror(errno
));
505 /* Update route->smoothed_metric using the old metric. */
506 route_smoothed_metric(route
);
508 route
->refmetric
= refmetric
;
510 route
->add_metric
= add
;
512 if(smoothing_half_life
== 0) {
513 route
->smoothed_metric
= route_metric(route
);
514 route
->smoothed_metric_time
= babel_now
.tv_sec
;
519 retract_route(struct babel_route
*route
)
521 /* We cannot simply remove the route from the kernel, as that might
522 cause a routing loop -- see RFC 6126 Sections 2.8 and 3.5.5. */
523 change_route_metric(route
, INFINITY
, INFINITY
, 0);
527 route_feasible(struct babel_route
*route
)
529 return update_feasible(route
->src
, route
->seqno
, route
->refmetric
);
533 route_old(struct babel_route
*route
)
535 return route
->time
< babel_now
.tv_sec
- route
->hold_time
* 7 / 8;
539 route_expired(struct babel_route
*route
)
541 return route
->time
< babel_now
.tv_sec
- route
->hold_time
;
545 channels_interfere(int ch1
, int ch2
)
547 if(ch1
== BABEL_IF_CHANNEL_NONINTERFERING
548 || ch2
== BABEL_IF_CHANNEL_NONINTERFERING
)
550 if(ch1
== BABEL_IF_CHANNEL_INTERFERING
551 || ch2
== BABEL_IF_CHANNEL_INTERFERING
)
557 route_interferes(struct babel_route
*route
, struct interface
*ifp
)
559 struct babel_interface
*babel_ifp
= NULL
;
560 switch(diversity_kind
) {
563 case DIVERSITY_INTERFACE_1
:
564 return route
->neigh
->ifp
== ifp
;
565 case DIVERSITY_CHANNEL_1
:
566 case DIVERSITY_CHANNEL
:
567 if(route
->neigh
->ifp
== ifp
)
569 babel_ifp
= babel_get_if_nfo(ifp
);
570 if(channels_interfere(babel_ifp
->channel
,
571 babel_get_if_nfo(route
->neigh
->ifp
)->channel
))
573 if(diversity_kind
== DIVERSITY_CHANNEL
) {
575 for(i
= 0; i
< DIVERSITY_HOPS
; i
++) {
576 if(route
->channels
[i
] == 0)
578 if(channels_interfere(babel_ifp
->channel
, route
->channels
[i
]))
584 zlog_err("Unknown kind of diversity.");
590 update_feasible(struct source
*src
,
591 unsigned short seqno
, unsigned short refmetric
)
596 if(src
->time
< babel_now
.tv_sec
- SOURCE_GC_TIME
)
597 /* Never mind what is probably stale data */
600 if(refmetric
>= INFINITY
)
601 /* Retractions are always feasible */
604 return (seqno_compare(seqno
, src
->seqno
) > 0 ||
605 (src
->seqno
== seqno
&& refmetric
< src
->metric
));
609 change_smoothing_half_life(int half_life
)
612 smoothing_half_life
= 0;
613 two_to_the_one_over_hl
= 0;
617 smoothing_half_life
= half_life
;
618 switch(smoothing_half_life
) {
619 case 1: two_to_the_one_over_hl
= 131072; break;
620 case 2: two_to_the_one_over_hl
= 92682; break;
621 case 3: two_to_the_one_over_hl
= 82570; break;
622 case 4: two_to_the_one_over_hl
= 77935; break;
624 /* 2^(1/x) is 1 + log(2)/x + O(1/x^2) at infinity. */
625 two_to_the_one_over_hl
= 0x10000 + 45426 / half_life
;
629 /* Update the smoothed metric, return the new value. */
631 route_smoothed_metric(struct babel_route
*route
)
633 int metric
= route_metric(route
);
635 if(smoothing_half_life
<= 0 || /* no smoothing */
636 metric
>= INFINITY
|| /* route retracted */
637 route
->smoothed_metric_time
> babel_now
.tv_sec
|| /* clock stepped */
638 route
->smoothed_metric
== metric
) { /* already converged */
639 route
->smoothed_metric
= metric
;
640 route
->smoothed_metric_time
= babel_now
.tv_sec
;
643 /* We randomise the computation, to minimise global synchronisation
644 and hence oscillations. */
645 while(route
->smoothed_metric_time
<=
646 babel_now
.tv_sec
- smoothing_half_life
) {
647 diff
= metric
- route
->smoothed_metric
;
648 route
->smoothed_metric
+= roughly(diff
) / 2;
649 route
->smoothed_metric_time
+= smoothing_half_life
;
651 while(route
->smoothed_metric_time
< babel_now
.tv_sec
) {
652 diff
= metric
- route
->smoothed_metric
;
653 route
->smoothed_metric
+=
654 roughly(diff
) * (two_to_the_one_over_hl
- 0x10000) / 0x10000;
655 route
->smoothed_metric_time
++;
658 diff
= metric
- route
->smoothed_metric
;
659 if(diff
> -4 && diff
< 4)
660 route
->smoothed_metric
= metric
;
663 /* change_route_metric relies on this */
664 assert(route
->smoothed_metric_time
== babel_now
.tv_sec
);
665 return route
->smoothed_metric
;
669 route_acceptable(struct babel_route
*route
, int feasible
,
670 struct neighbour
*exclude
)
672 if(route_expired(route
))
674 if(feasible
&& !route_feasible(route
))
676 if(exclude
&& route
->neigh
== exclude
)
681 /* Find the best route according to the weak ordering. Any
682 linearisation of the strong ordering (see consider_route) will do,
683 we use sm <= sm'. We could probably use a lexical ordering, but
684 that's probably overkill. */
687 find_best_route(const unsigned char *prefix
, unsigned char plen
, int feasible
,
688 struct neighbour
*exclude
)
690 struct babel_route
*route
= NULL
, *r
= NULL
;
691 int i
= find_route_slot(prefix
, plen
, NULL
);
697 while(route
&& !route_acceptable(route
, feasible
, exclude
))
705 if(route_acceptable(r
, feasible
, exclude
) &&
706 (route_smoothed_metric(r
) < route_smoothed_metric(route
)))
715 update_route_metric(struct babel_route
*route
)
717 int oldmetric
= route_metric(route
);
718 int old_smoothed_metric
= route_smoothed_metric(route
);
720 if(route_expired(route
)) {
721 if(route
->refmetric
< INFINITY
) {
722 route
->seqno
= seqno_plus(route
->src
->seqno
, 1);
723 retract_route(route
);
724 if(oldmetric
< INFINITY
)
725 route_changed(route
, route
->src
, oldmetric
);
728 struct neighbour
*neigh
= route
->neigh
;
729 int add_metric
= input_filter(route
->src
->id
,
730 route
->src
->prefix
, route
->src
->plen
,
732 neigh
->ifp
->ifindex
);
733 change_route_metric(route
, route
->refmetric
,
734 neighbour_cost(route
->neigh
), add_metric
);
735 if(route_metric(route
) != oldmetric
||
736 route_smoothed_metric(route
) != old_smoothed_metric
)
737 route_changed(route
, route
->src
, oldmetric
);
741 /* Called whenever a neighbour's cost changes, to update the metric of
742 all routes through that neighbour. */
744 update_neighbour_metric(struct neighbour
*neigh
, int changed
)
750 for(i
= 0; i
< route_slots
; i
++) {
751 struct babel_route
*r
= routes
[i
];
753 if(r
->neigh
== neigh
)
754 update_route_metric(r
);
762 update_interface_metric(struct interface
*ifp
)
766 for(i
= 0; i
< route_slots
; i
++) {
767 struct babel_route
*r
= routes
[i
];
769 if(r
->neigh
->ifp
== ifp
)
770 update_route_metric(r
);
776 /* This is called whenever we receive an update. */
778 update_route(const unsigned char *router_id
,
779 const unsigned char *prefix
, unsigned char plen
,
780 unsigned short seqno
, unsigned short refmetric
,
781 unsigned short interval
,
782 struct neighbour
*neigh
, const unsigned char *nexthop
,
783 const unsigned char *channels
, int channels_len
)
785 struct babel_route
*route
;
787 int metric
, feasible
;
789 int hold_time
= MAX((4 * interval
) / 100 + interval
/ 50, 15);
791 if(memcmp(router_id
, myid
, 8) == 0)
794 if(martian_prefix(prefix
, plen
)) {
795 zlog_err("Rejecting martian route to %s through %s.",
796 format_prefix(prefix
, plen
), format_address(nexthop
));
800 add_metric
= input_filter(router_id
, prefix
, plen
,
801 neigh
->address
, neigh
->ifp
->ifindex
);
802 if(add_metric
>= INFINITY
)
805 route
= find_route(prefix
, plen
, neigh
, nexthop
);
807 if(route
&& memcmp(route
->src
->id
, router_id
, 8) == 0)
808 /* Avoid scanning the source table. */
811 src
= find_source(router_id
, prefix
, plen
, 1, seqno
);
816 feasible
= update_feasible(src
, seqno
, refmetric
);
817 metric
= MIN((int)refmetric
+ neighbour_cost(neigh
) + add_metric
, INFINITY
);
820 struct source
*oldsrc
;
821 unsigned short oldmetric
;
825 oldmetric
= route_metric(route
);
827 /* If a successor switches sources, we must accept his update even
828 if it makes a route unfeasible in order to break any routing loops
829 in a timely manner. If the source remains the same, we ignore
831 if(!feasible
&& route
->installed
) {
832 debugf(BABEL_DEBUG_COMMON
,"Unfeasible update for installed route to %s "
833 "(%s %d %d -> %s %d %d).",
834 format_prefix(src
->prefix
, src
->plen
),
835 format_eui64(route
->src
->id
),
836 route
->seqno
, route
->refmetric
,
837 format_eui64(src
->id
), seqno
, refmetric
);
838 if(src
!= route
->src
) {
839 uninstall_route(route
);
844 route
->src
= retain_source(src
);
845 if((feasible
|| keep_unfeasible
) && refmetric
< INFINITY
)
846 route
->time
= babel_now
.tv_sec
;
847 route
->seqno
= seqno
;
849 memset(&route
->channels
, 0, sizeof(route
->channels
));
851 memcpy(&route
->channels
, channels
,
852 MIN(channels_len
, DIVERSITY_HOPS
));
854 change_route_metric(route
,
855 refmetric
, neighbour_cost(neigh
), add_metric
);
856 route
->hold_time
= hold_time
;
858 route_changed(route
, oldsrc
, oldmetric
);
860 route_lost(oldsrc
, oldmetric
);
863 send_unfeasible_request(neigh
, route
->installed
&& route_old(route
),
865 release_source(oldsrc
);
867 struct babel_route
*new_route
;
869 if(refmetric
>= INFINITY
)
870 /* Somebody's retracting a route we never saw. */
873 send_unfeasible_request(neigh
, 0, seqno
, metric
, src
);
878 route
= malloc(sizeof(struct babel_route
));
880 perror("malloc(route)");
884 route
->src
= retain_source(src
);
885 route
->refmetric
= refmetric
;
886 route
->cost
= neighbour_cost(neigh
);
887 route
->add_metric
= add_metric
;
888 route
->seqno
= seqno
;
889 route
->neigh
= neigh
;
890 memcpy(route
->nexthop
, nexthop
, 16);
891 route
->time
= babel_now
.tv_sec
;
892 route
->hold_time
= hold_time
;
893 route
->smoothed_metric
= MAX(route_metric(route
), INFINITY
/ 2);
894 route
->smoothed_metric_time
= babel_now
.tv_sec
;
895 route
->installed
= 0;
896 memset(&route
->channels
, 0, sizeof(route
->channels
));
898 memcpy(&route
->channels
, channels
,
899 MIN(channels_len
, DIVERSITY_HOPS
));
901 new_route
= insert_route(route
);
902 if(new_route
== NULL
) {
903 zlog_err("Couldn't insert route.");
907 consider_route(route
);
912 /* We just received an unfeasible update. If it's any good, send
913 a request for a new seqno. */
915 send_unfeasible_request(struct neighbour
*neigh
, int force
,
916 unsigned short seqno
, unsigned short metric
,
919 struct babel_route
*route
= find_installed_route(src
->prefix
, src
->plen
);
921 if(seqno_minus(src
->seqno
, seqno
) > 100) {
922 /* Probably a source that lost its seqno. Let it time-out. */
926 if(force
|| !route
|| route_metric(route
) >= metric
+ 512) {
927 send_unicast_multihop_request(neigh
, src
->prefix
, src
->plen
,
928 src
->metric
>= INFINITY
?
930 seqno_plus(src
->seqno
, 1),
935 /* This takes a feasible route and decides whether to install it.
936 This uses the strong ordering, which is defined by sm <= sm' AND
937 m <= m'. This ordering is not total, which is what causes
941 consider_route(struct babel_route
*route
)
943 struct babel_route
*installed
;
944 struct xroute
*xroute
;
949 if(!route_feasible(route
))
952 xroute
= find_xroute(route
->src
->prefix
, route
->src
->plen
);
956 installed
= find_installed_route(route
->src
->prefix
, route
->src
->plen
);
958 if(installed
== NULL
)
961 if(route_metric(route
) >= INFINITY
)
964 if(route_metric(installed
) >= INFINITY
)
967 if(route_metric(installed
) >= route_metric(route
) &&
968 route_smoothed_metric(installed
) > route_smoothed_metric(route
))
974 switch_routes(installed
, route
);
975 if(installed
&& route
->installed
)
976 send_triggered_update(route
, installed
->src
, route_metric(installed
));
978 send_update(NULL
, 1, route
->src
->prefix
, route
->src
->plen
);
983 retract_neighbour_routes(struct neighbour
*neigh
)
987 for(i
= 0; i
< route_slots
; i
++) {
988 struct babel_route
*r
= routes
[i
];
990 if(r
->neigh
== neigh
) {
991 if(r
->refmetric
!= INFINITY
) {
992 unsigned short oldmetric
= route_metric(r
);
994 if(oldmetric
!= INFINITY
)
995 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
);