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
);
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(BABEL_ERR_ROUTE
, "WARNING: installing unfeasible route "
403 "(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
) {
409 flog_err(BABEL_ERR_ROUTE
,
410 "WARNING: attempting to install duplicate route "
411 "(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(BABEL_ERR_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(BABEL_ERR_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(BABEL_ERR_ROUTE
, "WARNING: switching to unfeasible route "
469 "(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(BABEL_ERR_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(BABEL_ERR_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(BABEL_ERR_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 "
839 "(%s %d %d -> %s %d %d).",
840 format_prefix(src
->prefix
, src
->plen
),
841 format_eui64(route
->src
->id
),
842 route
->seqno
, route
->refmetric
,
843 format_eui64(src
->id
), seqno
, refmetric
);
844 if(src
!= route
->src
) {
845 uninstall_route(route
);
850 route
->src
= retain_source(src
);
851 if((feasible
|| keep_unfeasible
) && refmetric
< INFINITY
)
852 route
->time
= babel_now
.tv_sec
;
853 route
->seqno
= seqno
;
855 memset(&route
->channels
, 0, sizeof(route
->channels
));
857 memcpy(&route
->channels
, channels
,
858 MIN(channels_len
, DIVERSITY_HOPS
));
860 change_route_metric(route
,
861 refmetric
, neighbour_cost(neigh
), add_metric
);
862 route
->hold_time
= hold_time
;
864 route_changed(route
, oldsrc
, oldmetric
);
866 route_lost(oldsrc
, oldmetric
);
869 send_unfeasible_request(neigh
, route
->installed
&& route_old(route
),
871 release_source(oldsrc
);
873 struct babel_route
*new_route
;
875 if(refmetric
>= INFINITY
)
876 /* Somebody's retracting a route we never saw. */
879 send_unfeasible_request(neigh
, 0, seqno
, metric
, src
);
884 route
= malloc(sizeof(struct babel_route
));
886 perror("malloc(route)");
890 route
->src
= retain_source(src
);
891 route
->refmetric
= refmetric
;
892 route
->cost
= neighbour_cost(neigh
);
893 route
->add_metric
= add_metric
;
894 route
->seqno
= seqno
;
895 route
->neigh
= neigh
;
896 memcpy(route
->nexthop
, nexthop
, 16);
897 route
->time
= babel_now
.tv_sec
;
898 route
->hold_time
= hold_time
;
899 route
->smoothed_metric
= MAX(route_metric(route
), INFINITY
/ 2);
900 route
->smoothed_metric_time
= babel_now
.tv_sec
;
901 route
->installed
= 0;
902 memset(&route
->channels
, 0, sizeof(route
->channels
));
904 memcpy(&route
->channels
, channels
,
905 MIN(channels_len
, DIVERSITY_HOPS
));
907 new_route
= insert_route(route
);
908 if(new_route
== NULL
) {
909 flog_err(BABEL_ERR_ROUTE
, "Couldn't insert route.");
913 consider_route(route
);
918 /* We just received an unfeasible update. If it's any good, send
919 a request for a new seqno. */
921 send_unfeasible_request(struct neighbour
*neigh
, int force
,
922 unsigned short seqno
, unsigned short metric
,
925 struct babel_route
*route
= find_installed_route(src
->prefix
, src
->plen
);
927 if(seqno_minus(src
->seqno
, seqno
) > 100) {
928 /* Probably a source that lost its seqno. Let it time-out. */
932 if(force
|| !route
|| route_metric(route
) >= metric
+ 512) {
933 send_unicast_multihop_request(neigh
, src
->prefix
, src
->plen
,
934 src
->metric
>= INFINITY
?
936 seqno_plus(src
->seqno
, 1),
941 /* This takes a feasible route and decides whether to install it.
942 This uses the strong ordering, which is defined by sm <= sm' AND
943 m <= m'. This ordering is not total, which is what causes
947 consider_route(struct babel_route
*route
)
949 struct babel_route
*installed
;
950 struct xroute
*xroute
;
955 if(!route_feasible(route
))
958 xroute
= find_xroute(route
->src
->prefix
, route
->src
->plen
);
962 installed
= find_installed_route(route
->src
->prefix
, route
->src
->plen
);
964 if(installed
== NULL
)
967 if(route_metric(route
) >= INFINITY
)
970 if(route_metric(installed
) >= INFINITY
)
973 if(route_metric(installed
) >= route_metric(route
) &&
974 route_smoothed_metric(installed
) > route_smoothed_metric(route
))
980 switch_routes(installed
, route
);
981 if(installed
&& route
->installed
)
982 send_triggered_update(route
, installed
->src
, route_metric(installed
));
984 send_update(NULL
, 1, route
->src
->prefix
, route
->src
->plen
);
989 retract_neighbour_routes(struct neighbour
*neigh
)
993 for(i
= 0; i
< route_slots
; i
++) {
994 struct babel_route
*r
= routes
[i
];
996 if(r
->neigh
== neigh
) {
997 if(r
->refmetric
!= INFINITY
) {
998 unsigned short oldmetric
= route_metric(r
);
1000 if(oldmetric
!= INFINITY
)
1001 route_changed(r
, r
->src
, oldmetric
);
1010 send_triggered_update(struct babel_route
*route
, struct source
*oldsrc
,
1013 unsigned newmetric
, diff
;
1014 /* 1 means send speedily, 2 means resend */
1017 if(!route
->installed
)
1020 newmetric
= route_metric(route
);
1022 newmetric
>= oldmetric
? newmetric
- oldmetric
: oldmetric
- newmetric
;
1024 if(route
->src
!= oldsrc
|| (oldmetric
< INFINITY
&& newmetric
>= INFINITY
))
1025 /* Switching sources can cause transient routing loops.
1026 Retractions can cause blackholes. */
1028 else if(newmetric
> oldmetric
&& oldmetric
< 6 * 256 && diff
>= 512)
1029 /* Route getting significantly worse */
1031 else if(unsatisfied_request(route
->src
->prefix
, route
->src
->plen
,
1032 route
->seqno
, route
->src
->id
))
1033 /* Make sure that requests are satisfied speedily */
1035 else if(oldmetric
>= INFINITY
&& newmetric
< INFINITY
)
1038 else if(newmetric
< oldmetric
&& diff
< 1024)
1039 /* Route getting better. This may be a transient fluctuation, so
1040 don't advertise it to avoid making routes unfeasible later on. */
1043 /* Don't fret about trivialities */
1049 send_update_resend(NULL
, route
->src
->prefix
, route
->src
->plen
);
1051 send_update(NULL
, urgent
, route
->src
->prefix
, route
->src
->plen
);
1053 if(oldmetric
< INFINITY
) {
1054 if(newmetric
>= oldmetric
+ 512) {
1055 send_request_resend(NULL
, route
->src
->prefix
, route
->src
->plen
,
1056 route
->src
->metric
>= INFINITY
?
1058 seqno_plus(route
->src
->seqno
, 1),
1060 } else if(newmetric
>= oldmetric
+ 288) {
1061 send_request(NULL
, route
->src
->prefix
, route
->src
->plen
);
1066 /* A route has just changed. Decide whether to switch to a different route or
1069 route_changed(struct babel_route
*route
,
1070 struct source
*oldsrc
, unsigned short oldmetric
)
1072 if(route
->installed
) {
1073 struct babel_route
*better_route
;
1074 /* Do this unconditionally -- microoptimisation is not worth it. */
1076 find_best_route(route
->src
->prefix
, route
->src
->plen
, 1, NULL
);
1077 if(better_route
&& route_metric(better_route
) < route_metric(route
))
1078 consider_route(better_route
);
1081 if(route
->installed
) {
1082 /* We didn't change routes after all. */
1083 send_triggered_update(route
, oldsrc
, oldmetric
);
1085 /* Reconsider routes even when their metric didn't decrease,
1086 they may not have been feasible before. */
1087 consider_route(route
);
1091 /* We just lost the installed route to a given destination. */
1093 route_lost(struct source
*src
, unsigned oldmetric
)
1095 struct babel_route
*new_route
;
1096 new_route
= find_best_route(src
->prefix
, src
->plen
, 1, NULL
);
1098 consider_route(new_route
);
1099 } else if(oldmetric
< INFINITY
) {
1100 /* Avoid creating a blackhole. */
1101 send_update_resend(NULL
, src
->prefix
, src
->plen
);
1102 /* If the route was usable enough, try to get an alternate one.
1103 If it was not, we could be dealing with oscillations around
1104 the value of INFINITY. */
1105 if(oldmetric
<= INFINITY
/ 2)
1106 send_request_resend(NULL
, src
->prefix
, src
->plen
,
1107 src
->metric
>= INFINITY
?
1108 src
->seqno
: seqno_plus(src
->seqno
, 1),
1113 /* This is called periodically to flush old routes. It will also send
1114 requests for routes that are about to expire. */
1118 struct babel_route
*r
;
1121 debugf(BABEL_DEBUG_COMMON
,"Expiring old routes.");
1124 while(i
< route_slots
) {
1127 /* Protect against clock being stepped. */
1128 if(r
->time
> babel_now
.tv_sec
|| route_old(r
)) {
1133 update_route_metric(r
);
1135 if(r
->installed
&& r
->refmetric
< INFINITY
) {
1137 /* Route about to expire, send a request. */
1138 send_unicast_request(r
->neigh
,
1139 r
->src
->prefix
, r
->src
->plen
);