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"
37 #include "babel_errors.h"
39 static void consider_route(struct babel_route
*route
);
41 struct babel_route
**routes
= NULL
;
42 static int route_slots
= 0, max_route_slots
= 0;
43 int kernel_metric
= 0;
44 enum babel_diversity diversity_kind
= DIVERSITY_NONE
;
45 int diversity_factor
= BABEL_DEFAULT_DIVERSITY_FACTOR
;
46 int keep_unfeasible
= 0;
48 int smoothing_half_life
= 0;
49 static int two_to_the_one_over_hl
= 0; /* 2^(1/hl) * 0x10000 */
51 /* We maintain a list of "slots", ordered by prefix. Every slot
52 contains a linked list of the routes to this prefix, with the
53 installed route, if any, at the head of the list. */
56 route_compare(const unsigned char *prefix
, unsigned char plen
,
57 struct babel_route
*route
)
59 int i
= memcmp(prefix
, route
->src
->prefix
, 16);
63 if(plen
< route
->src
->plen
)
65 else if(plen
> route
->src
->plen
)
71 /* Performs binary search, returns -1 in case of failure. In the latter
72 case, new_return is the place where to insert the new element. */
75 find_route_slot(const unsigned char *prefix
, unsigned char plen
,
86 p
= 0; g
= route_slots
- 1;
90 c
= route_compare(prefix
, plen
, routes
[m
]);
106 find_route(const unsigned char *prefix
, unsigned char plen
,
107 struct neighbour
*neigh
, const unsigned char *nexthop
)
109 struct babel_route
*route
;
110 int i
= find_route_slot(prefix
, plen
, NULL
);
118 if(route
->neigh
== neigh
&& memcmp(route
->nexthop
, nexthop
, 16) == 0)
127 find_installed_route(const unsigned char *prefix
, unsigned char plen
)
129 int i
= find_route_slot(prefix
, plen
, NULL
);
131 if(i
>= 0 && routes
[i
]->installed
)
137 /* Returns an overestimate of the number of installed routes. */
139 installed_routes_estimate(void)
145 resize_route_table(int new_slots
)
147 struct babel_route
**new_routes
;
148 assert(new_slots
>= route_slots
);
154 new_routes
= realloc(routes
, new_slots
* sizeof(struct babel_route
*));
155 if(new_routes
== NULL
)
159 max_route_slots
= new_slots
;
164 /* Insert a route into the table. If successful, retains the route.
165 On failure, caller must free the route. */
166 static struct babel_route
*
167 insert_route(struct babel_route
*route
)
171 assert(!route
->installed
);
173 i
= find_route_slot(route
->src
->prefix
, route
->src
->plen
, &n
);
176 if(route_slots
>= max_route_slots
)
177 resize_route_table(max_route_slots
< 1 ? 8 : 2 * max_route_slots
);
178 if(route_slots
>= max_route_slots
)
183 memmove(routes
+ n
+ 1, routes
+ n
,
184 (route_slots
- n
) * sizeof(struct babel_route
*));
188 struct babel_route
*r
;
200 flush_route(struct babel_route
*route
)
207 oldmetric
= route_metric(route
);
210 if(route
->installed
) {
211 uninstall_route(route
);
215 i
= find_route_slot(route
->src
->prefix
, route
->src
->plen
, NULL
);
216 assert(i
>= 0 && i
< route_slots
);
218 if(route
== routes
[i
]) {
219 routes
[i
] = route
->next
;
223 if(routes
[i
] == NULL
) {
224 if(i
< route_slots
- 1)
225 memmove(routes
+ i
, routes
+ i
+ 1,
226 (route_slots
- i
- 1) * sizeof(struct babel_route
*));
227 routes
[route_slots
- 1] = NULL
;
232 resize_route_table(0);
233 else if(max_route_slots
> 8 && route_slots
< max_route_slots
/ 4)
234 resize_route_table(max_route_slots
/ 2);
236 struct babel_route
*r
= routes
[i
];
237 while(r
->next
!= route
)
239 r
->next
= route
->next
;
245 route_lost(src
, oldmetric
);
251 flush_all_routes(void)
255 /* Start from the end, to avoid shifting the table. */
258 while(i
< route_slots
) {
259 /* Uninstall first, to avoid calling route_lost. */
260 if(routes
[i
]->installed
)
261 uninstall_route(routes
[i
]);
262 flush_route(routes
[i
]);
267 check_sources_released();
271 flush_neighbour_routes(struct neighbour
*neigh
)
276 while(i
< route_slots
) {
277 struct babel_route
*r
;
280 if(r
->neigh
== neigh
) {
293 flush_interface_routes(struct interface
*ifp
, int v4only
)
298 while(i
< route_slots
) {
299 struct babel_route
*r
;
302 if(r
->neigh
->ifp
== ifp
&&
303 (!v4only
|| v4mapped(r
->nexthop
))) {
315 struct route_stream
{
318 struct babel_route
*next
;
322 struct route_stream
*
323 route_stream(int installed
)
325 struct route_stream
*stream
;
327 stream
= malloc(sizeof(struct route_stream
));
331 stream
->installed
= installed
;
332 stream
->index
= installed
? 0 : -1;
339 route_stream_next(struct route_stream
*stream
)
341 if(stream
->installed
) {
342 while(stream
->index
< route_slots
&& !routes
[stream
->index
]->installed
)
345 if(stream
->index
< route_slots
)
346 return routes
[stream
->index
++];
350 struct babel_route
*next
;
353 if(stream
->index
>= route_slots
)
355 stream
->next
= routes
[stream
->index
];
358 stream
->next
= next
->next
;
364 route_stream_done(struct route_stream
*stream
)
370 metric_to_kernel(int metric
)
372 return metric
< INFINITY
? kernel_metric
: KERNEL_INFINITY
;
375 /* This is used to maintain the invariant that the installed route is at
376 the head of the list. */
378 move_installed_route(struct babel_route
*route
, int i
)
380 assert(i
>= 0 && i
< route_slots
);
381 assert(route
->installed
);
383 if(route
!= routes
[i
]) {
384 struct babel_route
*r
= routes
[i
];
385 while(r
->next
!= route
)
387 r
->next
= route
->next
;
388 route
->next
= routes
[i
];
394 install_route(struct babel_route
*route
)
401 if(!route_feasible(route
))
402 flog_err(EC_BABEL_ROUTE
,
403 "Installing unfeasible route (this shouldn't happen).");
405 i
= find_route_slot(route
->src
->prefix
, route
->src
->plen
, NULL
);
406 assert(i
>= 0 && i
< route_slots
);
408 if(routes
[i
] != route
&& routes
[i
]->installed
) {
411 "Attempting to install duplicate route (this shouldn't happen).");
415 rc
= kernel_route(ROUTE_ADD
, route
->src
->prefix
, route
->src
->plen
,
417 route
->neigh
->ifp
->ifindex
,
418 metric_to_kernel(route_metric(route
)), NULL
, 0, 0);
421 flog_err(EC_BABEL_ROUTE
, "kernel_route(ADD): %s",
422 safe_strerror(errno
));
426 route
->installed
= 1;
427 move_installed_route(route
, i
);
432 uninstall_route(struct babel_route
*route
)
436 if(!route
->installed
)
439 rc
= kernel_route(ROUTE_FLUSH
, route
->src
->prefix
, route
->src
->plen
,
441 route
->neigh
->ifp
->ifindex
,
442 metric_to_kernel(route_metric(route
)), NULL
, 0, 0);
444 flog_err(EC_BABEL_ROUTE
, "kernel_route(FLUSH): %s",
445 safe_strerror(errno
));
447 route
->installed
= 0;
450 /* This is equivalent to uninstall_route followed with install_route,
451 but without the race condition. The destination of both routes
455 switch_routes(struct babel_route
*old
, struct babel_route
*new)
467 if(!route_feasible(new))
468 flog_err(EC_BABEL_ROUTE
,
469 "Switching to unfeasible route (this shouldn't happen).");
471 rc
= kernel_route(ROUTE_MODIFY
, old
->src
->prefix
, old
->src
->plen
,
472 old
->nexthop
, old
->neigh
->ifp
->ifindex
,
473 metric_to_kernel(route_metric(old
)),
474 new->nexthop
, new->neigh
->ifp
->ifindex
,
475 metric_to_kernel(route_metric(new)));
477 flog_err(EC_BABEL_ROUTE
, "kernel_route(MODIFY): %s",
478 safe_strerror(errno
));
484 move_installed_route(new, find_route_slot(new->src
->prefix
, new->src
->plen
,
489 change_route_metric(struct babel_route
*route
,
490 unsigned refmetric
, unsigned cost
, unsigned add
)
493 int newmetric
= MIN(refmetric
+ cost
+ add
, INFINITY
);
495 old
= metric_to_kernel(route_metric(route
));
496 new = metric_to_kernel(newmetric
);
498 if(route
->installed
&& old
!= new) {
500 rc
= kernel_route(ROUTE_MODIFY
, route
->src
->prefix
, route
->src
->plen
,
501 route
->nexthop
, route
->neigh
->ifp
->ifindex
,
503 route
->nexthop
, route
->neigh
->ifp
->ifindex
,
506 flog_err(EC_BABEL_ROUTE
, "kernel_route(MODIFY metric): %s",
507 safe_strerror(errno
));
512 /* Update route->smoothed_metric using the old metric. */
513 route_smoothed_metric(route
);
515 route
->refmetric
= refmetric
;
517 route
->add_metric
= add
;
519 if(smoothing_half_life
== 0) {
520 route
->smoothed_metric
= route_metric(route
);
521 route
->smoothed_metric_time
= babel_now
.tv_sec
;
526 retract_route(struct babel_route
*route
)
528 /* We cannot simply remove the route from the kernel, as that might
529 cause a routing loop -- see RFC 6126 Sections 2.8 and 3.5.5. */
530 change_route_metric(route
, INFINITY
, INFINITY
, 0);
534 route_feasible(struct babel_route
*route
)
536 return update_feasible(route
->src
, route
->seqno
, route
->refmetric
);
540 route_old(struct babel_route
*route
)
542 return route
->time
< babel_now
.tv_sec
- route
->hold_time
* 7 / 8;
546 route_expired(struct babel_route
*route
)
548 return route
->time
< babel_now
.tv_sec
- route
->hold_time
;
552 channels_interfere(int ch1
, int ch2
)
554 if(ch1
== BABEL_IF_CHANNEL_NONINTERFERING
555 || ch2
== BABEL_IF_CHANNEL_NONINTERFERING
)
557 if(ch1
== BABEL_IF_CHANNEL_INTERFERING
558 || ch2
== BABEL_IF_CHANNEL_INTERFERING
)
564 route_interferes(struct babel_route
*route
, struct interface
*ifp
)
566 struct babel_interface
*babel_ifp
= NULL
;
567 switch(diversity_kind
) {
570 case DIVERSITY_INTERFACE_1
:
571 return route
->neigh
->ifp
== ifp
;
572 case DIVERSITY_CHANNEL_1
:
573 case DIVERSITY_CHANNEL
:
574 if(route
->neigh
->ifp
== ifp
)
576 babel_ifp
= babel_get_if_nfo(ifp
);
577 if(channels_interfere(babel_ifp
->channel
,
578 babel_get_if_nfo(route
->neigh
->ifp
)->channel
))
580 if(diversity_kind
== DIVERSITY_CHANNEL
) {
582 for(i
= 0; i
< DIVERSITY_HOPS
; i
++) {
583 if(route
->channels
[i
] == 0)
585 if(channels_interfere(babel_ifp
->channel
, route
->channels
[i
]))
596 update_feasible(struct source
*src
,
597 unsigned short seqno
, unsigned short refmetric
)
602 if(src
->time
< babel_now
.tv_sec
- SOURCE_GC_TIME
)
603 /* Never mind what is probably stale data */
606 if(refmetric
>= INFINITY
)
607 /* Retractions are always feasible */
610 return (seqno_compare(seqno
, src
->seqno
) > 0 ||
611 (src
->seqno
== seqno
&& refmetric
< src
->metric
));
615 change_smoothing_half_life(int half_life
)
618 smoothing_half_life
= 0;
619 two_to_the_one_over_hl
= 0;
623 smoothing_half_life
= half_life
;
624 switch(smoothing_half_life
) {
625 case 1: two_to_the_one_over_hl
= 131072; break;
626 case 2: two_to_the_one_over_hl
= 92682; break;
627 case 3: two_to_the_one_over_hl
= 82570; break;
628 case 4: two_to_the_one_over_hl
= 77935; break;
630 /* 2^(1/x) is 1 + log(2)/x + O(1/x^2) at infinity. */
631 two_to_the_one_over_hl
= 0x10000 + 45426 / half_life
;
635 /* Update the smoothed metric, return the new value. */
637 route_smoothed_metric(struct babel_route
*route
)
639 int metric
= route_metric(route
);
641 if(smoothing_half_life
<= 0 || /* no smoothing */
642 metric
>= INFINITY
|| /* route retracted */
643 route
->smoothed_metric_time
> babel_now
.tv_sec
|| /* clock stepped */
644 route
->smoothed_metric
== metric
) { /* already converged */
645 route
->smoothed_metric
= metric
;
646 route
->smoothed_metric_time
= babel_now
.tv_sec
;
649 /* We randomise the computation, to minimise global synchronisation
650 and hence oscillations. */
651 while(route
->smoothed_metric_time
<=
652 babel_now
.tv_sec
- smoothing_half_life
) {
653 diff
= metric
- route
->smoothed_metric
;
654 route
->smoothed_metric
+= roughly(diff
) / 2;
655 route
->smoothed_metric_time
+= smoothing_half_life
;
657 while(route
->smoothed_metric_time
< babel_now
.tv_sec
) {
658 diff
= metric
- route
->smoothed_metric
;
659 route
->smoothed_metric
+=
660 roughly(diff
) * (two_to_the_one_over_hl
- 0x10000) / 0x10000;
661 route
->smoothed_metric_time
++;
664 diff
= metric
- route
->smoothed_metric
;
665 if(diff
> -4 && diff
< 4)
666 route
->smoothed_metric
= metric
;
669 /* change_route_metric relies on this */
670 assert(route
->smoothed_metric_time
== babel_now
.tv_sec
);
671 return route
->smoothed_metric
;
675 route_acceptable(struct babel_route
*route
, int feasible
,
676 struct neighbour
*exclude
)
678 if(route_expired(route
))
680 if(feasible
&& !route_feasible(route
))
682 if(exclude
&& route
->neigh
== exclude
)
687 /* Find the best route according to the weak ordering. Any
688 linearisation of the strong ordering (see consider_route) will do,
689 we use sm <= sm'. We could probably use a lexical ordering, but
690 that's probably overkill. */
693 find_best_route(const unsigned char *prefix
, unsigned char plen
, int feasible
,
694 struct neighbour
*exclude
)
696 struct babel_route
*route
= NULL
, *r
= NULL
;
697 int i
= find_route_slot(prefix
, plen
, NULL
);
703 while(route
&& !route_acceptable(route
, feasible
, exclude
))
711 if(route_acceptable(r
, feasible
, exclude
) &&
712 (route_smoothed_metric(r
) < route_smoothed_metric(route
)))
721 update_route_metric(struct babel_route
*route
)
723 int oldmetric
= route_metric(route
);
724 int old_smoothed_metric
= route_smoothed_metric(route
);
726 if(route_expired(route
)) {
727 if(route
->refmetric
< INFINITY
) {
728 route
->seqno
= seqno_plus(route
->src
->seqno
, 1);
729 retract_route(route
);
730 if(oldmetric
< INFINITY
)
731 route_changed(route
, route
->src
, oldmetric
);
734 struct neighbour
*neigh
= route
->neigh
;
735 int add_metric
= input_filter(route
->src
->id
,
736 route
->src
->prefix
, route
->src
->plen
,
738 neigh
->ifp
->ifindex
);
739 change_route_metric(route
, route
->refmetric
,
740 neighbour_cost(route
->neigh
), add_metric
);
741 if(route_metric(route
) != oldmetric
||
742 route_smoothed_metric(route
) != old_smoothed_metric
)
743 route_changed(route
, route
->src
, oldmetric
);
747 /* Called whenever a neighbour's cost changes, to update the metric of
748 all routes through that neighbour. */
750 update_neighbour_metric(struct neighbour
*neigh
, int changed
)
756 for(i
= 0; i
< route_slots
; i
++) {
757 struct babel_route
*r
= routes
[i
];
759 if(r
->neigh
== neigh
)
760 update_route_metric(r
);
768 update_interface_metric(struct interface
*ifp
)
772 for(i
= 0; i
< route_slots
; i
++) {
773 struct babel_route
*r
= routes
[i
];
775 if(r
->neigh
->ifp
== ifp
)
776 update_route_metric(r
);
782 /* This is called whenever we receive an update. */
784 update_route(const unsigned char *router_id
,
785 const unsigned char *prefix
, unsigned char plen
,
786 unsigned short seqno
, unsigned short refmetric
,
787 unsigned short interval
,
788 struct neighbour
*neigh
, const unsigned char *nexthop
,
789 const unsigned char *channels
, int channels_len
)
791 struct babel_route
*route
;
793 int metric
, feasible
;
795 int hold_time
= MAX((4 * interval
) / 100 + interval
/ 50, 15);
797 if(memcmp(router_id
, myid
, 8) == 0)
800 if(martian_prefix(prefix
, plen
)) {
801 flog_err(EC_BABEL_ROUTE
, "Rejecting martian route to %s through %s.",
802 format_prefix(prefix
, plen
), format_address(nexthop
));
806 add_metric
= input_filter(router_id
, prefix
, plen
,
807 neigh
->address
, neigh
->ifp
->ifindex
);
808 if(add_metric
>= INFINITY
)
811 route
= find_route(prefix
, plen
, neigh
, nexthop
);
813 if(route
&& memcmp(route
->src
->id
, router_id
, 8) == 0)
814 /* Avoid scanning the source table. */
817 src
= find_source(router_id
, prefix
, plen
, 1, seqno
);
822 feasible
= update_feasible(src
, seqno
, refmetric
);
823 metric
= MIN((int)refmetric
+ neighbour_cost(neigh
) + add_metric
, INFINITY
);
826 struct source
*oldsrc
;
827 unsigned short oldmetric
;
831 oldmetric
= route_metric(route
);
833 /* If a successor switches sources, we must accept his update even
834 if it makes a route unfeasible in order to break any routing loops
835 in a timely manner. If the source remains the same, we ignore
837 if(!feasible
&& route
->installed
) {
838 debugf(BABEL_DEBUG_COMMON
,"Unfeasible update for installed route to %s (%s %d %d -> %s %d %d).",
839 format_prefix(src
->prefix
, src
->plen
),
840 format_eui64(route
->src
->id
),
841 route
->seqno
, route
->refmetric
,
842 format_eui64(src
->id
), seqno
, refmetric
);
843 if(src
!= route
->src
) {
844 uninstall_route(route
);
849 route
->src
= retain_source(src
);
850 if((feasible
|| keep_unfeasible
) && refmetric
< INFINITY
)
851 route
->time
= babel_now
.tv_sec
;
852 route
->seqno
= seqno
;
854 memset(&route
->channels
, 0, sizeof(route
->channels
));
856 memcpy(&route
->channels
, channels
,
857 MIN(channels_len
, DIVERSITY_HOPS
));
859 change_route_metric(route
,
860 refmetric
, neighbour_cost(neigh
), add_metric
);
861 route
->hold_time
= hold_time
;
863 route_changed(route
, oldsrc
, oldmetric
);
865 route_lost(oldsrc
, oldmetric
);
868 send_unfeasible_request(neigh
, route
->installed
&& route_old(route
),
870 release_source(oldsrc
);
872 struct babel_route
*new_route
;
874 if(refmetric
>= INFINITY
)
875 /* Somebody's retracting a route we never saw. */
878 send_unfeasible_request(neigh
, 0, seqno
, metric
, src
);
883 route
= malloc(sizeof(struct babel_route
));
885 perror("malloc(route)");
889 route
->src
= retain_source(src
);
890 route
->refmetric
= refmetric
;
891 route
->cost
= neighbour_cost(neigh
);
892 route
->add_metric
= add_metric
;
893 route
->seqno
= seqno
;
894 route
->neigh
= neigh
;
895 memcpy(route
->nexthop
, nexthop
, 16);
896 route
->time
= babel_now
.tv_sec
;
897 route
->hold_time
= hold_time
;
898 route
->smoothed_metric
= MAX(route_metric(route
), INFINITY
/ 2);
899 route
->smoothed_metric_time
= babel_now
.tv_sec
;
900 route
->installed
= 0;
901 memset(&route
->channels
, 0, sizeof(route
->channels
));
903 memcpy(&route
->channels
, channels
,
904 MIN(channels_len
, DIVERSITY_HOPS
));
906 new_route
= insert_route(route
);
907 if(new_route
== NULL
) {
908 flog_err(EC_BABEL_ROUTE
, "Couldn't insert route.");
912 consider_route(route
);
917 /* We just received an unfeasible update. If it's any good, send
918 a request for a new seqno. */
920 send_unfeasible_request(struct neighbour
*neigh
, int force
,
921 unsigned short seqno
, unsigned short metric
,
924 struct babel_route
*route
= find_installed_route(src
->prefix
, src
->plen
);
926 if(seqno_minus(src
->seqno
, seqno
) > 100) {
927 /* Probably a source that lost its seqno. Let it time-out. */
931 if(force
|| !route
|| route_metric(route
) >= metric
+ 512) {
932 send_unicast_multihop_request(neigh
, src
->prefix
, src
->plen
,
933 src
->metric
>= INFINITY
?
935 seqno_plus(src
->seqno
, 1),
940 /* This takes a feasible route and decides whether to install it.
941 This uses the strong ordering, which is defined by sm <= sm' AND
942 m <= m'. This ordering is not total, which is what causes
946 consider_route(struct babel_route
*route
)
948 struct babel_route
*installed
;
949 struct xroute
*xroute
;
954 if(!route_feasible(route
))
957 xroute
= find_xroute(route
->src
->prefix
, route
->src
->plen
);
961 installed
= find_installed_route(route
->src
->prefix
, route
->src
->plen
);
963 if(installed
== NULL
)
966 if(route_metric(route
) >= INFINITY
)
969 if(route_metric(installed
) >= INFINITY
)
972 if(route_metric(installed
) >= route_metric(route
) &&
973 route_smoothed_metric(installed
) > route_smoothed_metric(route
))
979 switch_routes(installed
, route
);
980 if(installed
&& route
->installed
)
981 send_triggered_update(route
, installed
->src
, route_metric(installed
));
983 send_update(NULL
, 1, route
->src
->prefix
, route
->src
->plen
);
988 retract_neighbour_routes(struct neighbour
*neigh
)
992 for(i
= 0; i
< route_slots
; i
++) {
993 struct babel_route
*r
= routes
[i
];
995 if(r
->neigh
== neigh
) {
996 if(r
->refmetric
!= INFINITY
) {
997 unsigned short oldmetric
= route_metric(r
);
999 if(oldmetric
!= INFINITY
)
1000 route_changed(r
, r
->src
, oldmetric
);
1009 send_triggered_update(struct babel_route
*route
, struct source
*oldsrc
,
1012 unsigned newmetric
, diff
;
1013 /* 1 means send speedily, 2 means resend */
1016 if(!route
->installed
)
1019 newmetric
= route_metric(route
);
1021 newmetric
>= oldmetric
? newmetric
- oldmetric
: oldmetric
- newmetric
;
1023 if(route
->src
!= oldsrc
|| (oldmetric
< INFINITY
&& newmetric
>= INFINITY
))
1024 /* Switching sources can cause transient routing loops.
1025 Retractions can cause blackholes. */
1027 else if(newmetric
> oldmetric
&& oldmetric
< 6 * 256 && diff
>= 512)
1028 /* Route getting significantly worse */
1030 else if(unsatisfied_request(route
->src
->prefix
, route
->src
->plen
,
1031 route
->seqno
, route
->src
->id
))
1032 /* Make sure that requests are satisfied speedily */
1034 else if(oldmetric
>= INFINITY
&& newmetric
< INFINITY
)
1037 else if(newmetric
< oldmetric
&& diff
< 1024)
1038 /* Route getting better. This may be a transient fluctuation, so
1039 don't advertise it to avoid making routes unfeasible later on. */
1042 /* Don't fret about trivialities */
1048 send_update_resend(NULL
, route
->src
->prefix
, route
->src
->plen
);
1050 send_update(NULL
, urgent
, route
->src
->prefix
, route
->src
->plen
);
1052 if(oldmetric
< INFINITY
) {
1053 if(newmetric
>= oldmetric
+ 512) {
1054 send_request_resend(NULL
, route
->src
->prefix
, route
->src
->plen
,
1055 route
->src
->metric
>= INFINITY
?
1057 seqno_plus(route
->src
->seqno
, 1),
1059 } else if(newmetric
>= oldmetric
+ 288) {
1060 send_request(NULL
, route
->src
->prefix
, route
->src
->plen
);
1065 /* A route has just changed. Decide whether to switch to a different route or
1068 route_changed(struct babel_route
*route
,
1069 struct source
*oldsrc
, unsigned short oldmetric
)
1071 if(route
->installed
) {
1072 struct babel_route
*better_route
;
1073 /* Do this unconditionally -- microoptimisation is not worth it. */
1075 find_best_route(route
->src
->prefix
, route
->src
->plen
, 1, NULL
);
1076 if(better_route
&& route_metric(better_route
) < route_metric(route
))
1077 consider_route(better_route
);
1080 if(route
->installed
) {
1081 /* We didn't change routes after all. */
1082 send_triggered_update(route
, oldsrc
, oldmetric
);
1084 /* Reconsider routes even when their metric didn't decrease,
1085 they may not have been feasible before. */
1086 consider_route(route
);
1090 /* We just lost the installed route to a given destination. */
1092 route_lost(struct source
*src
, unsigned oldmetric
)
1094 struct babel_route
*new_route
;
1095 new_route
= find_best_route(src
->prefix
, src
->plen
, 1, NULL
);
1097 consider_route(new_route
);
1098 } else if(oldmetric
< INFINITY
) {
1099 /* Avoid creating a blackhole. */
1100 send_update_resend(NULL
, src
->prefix
, src
->plen
);
1101 /* If the route was usable enough, try to get an alternate one.
1102 If it was not, we could be dealing with oscillations around
1103 the value of INFINITY. */
1104 if(oldmetric
<= INFINITY
/ 2)
1105 send_request_resend(NULL
, src
->prefix
, src
->plen
,
1106 src
->metric
>= INFINITY
?
1107 src
->seqno
: seqno_plus(src
->seqno
, 1),
1112 /* This is called periodically to flush old routes. It will also send
1113 requests for routes that are about to expire. */
1117 struct babel_route
*r
;
1120 debugf(BABEL_DEBUG_COMMON
,"Expiring old routes.");
1123 while(i
< route_slots
) {
1126 /* Protect against clock being stepped. */
1127 if(r
->time
> babel_now
.tv_sec
|| route_old(r
)) {
1132 update_route_metric(r
);
1134 if(r
->installed
&& r
->refmetric
< INFINITY
) {
1136 /* Route about to expire, send a request. */
1137 send_unicast_request(r
->neigh
,
1138 r
->src
->prefix
, r
->src
->plen
);