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
, "WARNING: installing unfeasible route (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 flog_err(EC_BABEL_ROUTE
,
409 "WARNING: attempting to install duplicate route (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 flog_err(EC_BABEL_ROUTE
, "kernel_route(ADD): %s",
420 safe_strerror(errno
));
424 route
->installed
= 1;
425 move_installed_route(route
, i
);
430 uninstall_route(struct babel_route
*route
)
434 if(!route
->installed
)
437 rc
= kernel_route(ROUTE_FLUSH
, route
->src
->prefix
, route
->src
->plen
,
439 route
->neigh
->ifp
->ifindex
,
440 metric_to_kernel(route_metric(route
)), NULL
, 0, 0);
442 flog_err(EC_BABEL_ROUTE
, "kernel_route(FLUSH): %s",
443 safe_strerror(errno
));
445 route
->installed
= 0;
448 /* This is equivalent to uninstall_route followed with install_route,
449 but without the race condition. The destination of both routes
453 switch_routes(struct babel_route
*old
, struct babel_route
*new)
465 if(!route_feasible(new))
466 flog_err(EC_BABEL_ROUTE
, "WARNING: switching to unfeasible route (this shouldn't happen).");
468 rc
= kernel_route(ROUTE_MODIFY
, old
->src
->prefix
, old
->src
->plen
,
469 old
->nexthop
, old
->neigh
->ifp
->ifindex
,
470 metric_to_kernel(route_metric(old
)),
471 new->nexthop
, new->neigh
->ifp
->ifindex
,
472 metric_to_kernel(route_metric(new)));
474 flog_err(EC_BABEL_ROUTE
, "kernel_route(MODIFY): %s",
475 safe_strerror(errno
));
481 move_installed_route(new, find_route_slot(new->src
->prefix
, new->src
->plen
,
486 change_route_metric(struct babel_route
*route
,
487 unsigned refmetric
, unsigned cost
, unsigned add
)
490 int newmetric
= MIN(refmetric
+ cost
+ add
, INFINITY
);
492 old
= metric_to_kernel(route_metric(route
));
493 new = metric_to_kernel(newmetric
);
495 if(route
->installed
&& old
!= new) {
497 rc
= kernel_route(ROUTE_MODIFY
, route
->src
->prefix
, route
->src
->plen
,
498 route
->nexthop
, route
->neigh
->ifp
->ifindex
,
500 route
->nexthop
, route
->neigh
->ifp
->ifindex
,
503 flog_err(EC_BABEL_ROUTE
, "kernel_route(MODIFY metric): %s",
504 safe_strerror(errno
));
509 /* Update route->smoothed_metric using the old metric. */
510 route_smoothed_metric(route
);
512 route
->refmetric
= refmetric
;
514 route
->add_metric
= add
;
516 if(smoothing_half_life
== 0) {
517 route
->smoothed_metric
= route_metric(route
);
518 route
->smoothed_metric_time
= babel_now
.tv_sec
;
523 retract_route(struct babel_route
*route
)
525 /* We cannot simply remove the route from the kernel, as that might
526 cause a routing loop -- see RFC 6126 Sections 2.8 and 3.5.5. */
527 change_route_metric(route
, INFINITY
, INFINITY
, 0);
531 route_feasible(struct babel_route
*route
)
533 return update_feasible(route
->src
, route
->seqno
, route
->refmetric
);
537 route_old(struct babel_route
*route
)
539 return route
->time
< babel_now
.tv_sec
- route
->hold_time
* 7 / 8;
543 route_expired(struct babel_route
*route
)
545 return route
->time
< babel_now
.tv_sec
- route
->hold_time
;
549 channels_interfere(int ch1
, int ch2
)
551 if(ch1
== BABEL_IF_CHANNEL_NONINTERFERING
552 || ch2
== BABEL_IF_CHANNEL_NONINTERFERING
)
554 if(ch1
== BABEL_IF_CHANNEL_INTERFERING
555 || ch2
== BABEL_IF_CHANNEL_INTERFERING
)
561 route_interferes(struct babel_route
*route
, struct interface
*ifp
)
563 struct babel_interface
*babel_ifp
= NULL
;
564 switch(diversity_kind
) {
567 case DIVERSITY_INTERFACE_1
:
568 return route
->neigh
->ifp
== ifp
;
569 case DIVERSITY_CHANNEL_1
:
570 case DIVERSITY_CHANNEL
:
571 if(route
->neigh
->ifp
== ifp
)
573 babel_ifp
= babel_get_if_nfo(ifp
);
574 if(channels_interfere(babel_ifp
->channel
,
575 babel_get_if_nfo(route
->neigh
->ifp
)->channel
))
577 if(diversity_kind
== DIVERSITY_CHANNEL
) {
579 for(i
= 0; i
< DIVERSITY_HOPS
; i
++) {
580 if(route
->channels
[i
] == 0)
582 if(channels_interfere(babel_ifp
->channel
, route
->channels
[i
]))
593 update_feasible(struct source
*src
,
594 unsigned short seqno
, unsigned short refmetric
)
599 if(src
->time
< babel_now
.tv_sec
- SOURCE_GC_TIME
)
600 /* Never mind what is probably stale data */
603 if(refmetric
>= INFINITY
)
604 /* Retractions are always feasible */
607 return (seqno_compare(seqno
, src
->seqno
) > 0 ||
608 (src
->seqno
== seqno
&& refmetric
< src
->metric
));
612 change_smoothing_half_life(int half_life
)
615 smoothing_half_life
= 0;
616 two_to_the_one_over_hl
= 0;
620 smoothing_half_life
= half_life
;
621 switch(smoothing_half_life
) {
622 case 1: two_to_the_one_over_hl
= 131072; break;
623 case 2: two_to_the_one_over_hl
= 92682; break;
624 case 3: two_to_the_one_over_hl
= 82570; break;
625 case 4: two_to_the_one_over_hl
= 77935; break;
627 /* 2^(1/x) is 1 + log(2)/x + O(1/x^2) at infinity. */
628 two_to_the_one_over_hl
= 0x10000 + 45426 / half_life
;
632 /* Update the smoothed metric, return the new value. */
634 route_smoothed_metric(struct babel_route
*route
)
636 int metric
= route_metric(route
);
638 if(smoothing_half_life
<= 0 || /* no smoothing */
639 metric
>= INFINITY
|| /* route retracted */
640 route
->smoothed_metric_time
> babel_now
.tv_sec
|| /* clock stepped */
641 route
->smoothed_metric
== metric
) { /* already converged */
642 route
->smoothed_metric
= metric
;
643 route
->smoothed_metric_time
= babel_now
.tv_sec
;
646 /* We randomise the computation, to minimise global synchronisation
647 and hence oscillations. */
648 while(route
->smoothed_metric_time
<=
649 babel_now
.tv_sec
- smoothing_half_life
) {
650 diff
= metric
- route
->smoothed_metric
;
651 route
->smoothed_metric
+= roughly(diff
) / 2;
652 route
->smoothed_metric_time
+= smoothing_half_life
;
654 while(route
->smoothed_metric_time
< babel_now
.tv_sec
) {
655 diff
= metric
- route
->smoothed_metric
;
656 route
->smoothed_metric
+=
657 roughly(diff
) * (two_to_the_one_over_hl
- 0x10000) / 0x10000;
658 route
->smoothed_metric_time
++;
661 diff
= metric
- route
->smoothed_metric
;
662 if(diff
> -4 && diff
< 4)
663 route
->smoothed_metric
= metric
;
666 /* change_route_metric relies on this */
667 assert(route
->smoothed_metric_time
== babel_now
.tv_sec
);
668 return route
->smoothed_metric
;
672 route_acceptable(struct babel_route
*route
, int feasible
,
673 struct neighbour
*exclude
)
675 if(route_expired(route
))
677 if(feasible
&& !route_feasible(route
))
679 if(exclude
&& route
->neigh
== exclude
)
684 /* Find the best route according to the weak ordering. Any
685 linearisation of the strong ordering (see consider_route) will do,
686 we use sm <= sm'. We could probably use a lexical ordering, but
687 that's probably overkill. */
690 find_best_route(const unsigned char *prefix
, unsigned char plen
, int feasible
,
691 struct neighbour
*exclude
)
693 struct babel_route
*route
= NULL
, *r
= NULL
;
694 int i
= find_route_slot(prefix
, plen
, NULL
);
700 while(route
&& !route_acceptable(route
, feasible
, exclude
))
708 if(route_acceptable(r
, feasible
, exclude
) &&
709 (route_smoothed_metric(r
) < route_smoothed_metric(route
)))
718 update_route_metric(struct babel_route
*route
)
720 int oldmetric
= route_metric(route
);
721 int old_smoothed_metric
= route_smoothed_metric(route
);
723 if(route_expired(route
)) {
724 if(route
->refmetric
< INFINITY
) {
725 route
->seqno
= seqno_plus(route
->src
->seqno
, 1);
726 retract_route(route
);
727 if(oldmetric
< INFINITY
)
728 route_changed(route
, route
->src
, oldmetric
);
731 struct neighbour
*neigh
= route
->neigh
;
732 int add_metric
= input_filter(route
->src
->id
,
733 route
->src
->prefix
, route
->src
->plen
,
735 neigh
->ifp
->ifindex
);
736 change_route_metric(route
, route
->refmetric
,
737 neighbour_cost(route
->neigh
), add_metric
);
738 if(route_metric(route
) != oldmetric
||
739 route_smoothed_metric(route
) != old_smoothed_metric
)
740 route_changed(route
, route
->src
, oldmetric
);
744 /* Called whenever a neighbour's cost changes, to update the metric of
745 all routes through that neighbour. */
747 update_neighbour_metric(struct neighbour
*neigh
, int changed
)
753 for(i
= 0; i
< route_slots
; i
++) {
754 struct babel_route
*r
= routes
[i
];
756 if(r
->neigh
== neigh
)
757 update_route_metric(r
);
765 update_interface_metric(struct interface
*ifp
)
769 for(i
= 0; i
< route_slots
; i
++) {
770 struct babel_route
*r
= routes
[i
];
772 if(r
->neigh
->ifp
== ifp
)
773 update_route_metric(r
);
779 /* This is called whenever we receive an update. */
781 update_route(const unsigned char *router_id
,
782 const unsigned char *prefix
, unsigned char plen
,
783 unsigned short seqno
, unsigned short refmetric
,
784 unsigned short interval
,
785 struct neighbour
*neigh
, const unsigned char *nexthop
,
786 const unsigned char *channels
, int channels_len
)
788 struct babel_route
*route
;
790 int metric
, feasible
;
792 int hold_time
= MAX((4 * interval
) / 100 + interval
/ 50, 15);
794 if(memcmp(router_id
, myid
, 8) == 0)
797 if(martian_prefix(prefix
, plen
)) {
798 flog_err(EC_BABEL_ROUTE
, "Rejecting martian route to %s through %s.",
799 format_prefix(prefix
, plen
), format_address(nexthop
));
803 add_metric
= input_filter(router_id
, prefix
, plen
,
804 neigh
->address
, neigh
->ifp
->ifindex
);
805 if(add_metric
>= INFINITY
)
808 route
= find_route(prefix
, plen
, neigh
, nexthop
);
810 if(route
&& memcmp(route
->src
->id
, router_id
, 8) == 0)
811 /* Avoid scanning the source table. */
814 src
= find_source(router_id
, prefix
, plen
, 1, seqno
);
819 feasible
= update_feasible(src
, seqno
, refmetric
);
820 metric
= MIN((int)refmetric
+ neighbour_cost(neigh
) + add_metric
, INFINITY
);
823 struct source
*oldsrc
;
824 unsigned short oldmetric
;
828 oldmetric
= route_metric(route
);
830 /* If a successor switches sources, we must accept his update even
831 if it makes a route unfeasible in order to break any routing loops
832 in a timely manner. If the source remains the same, we ignore
834 if(!feasible
&& route
->installed
) {
835 debugf(BABEL_DEBUG_COMMON
,"Unfeasible update for installed route to %s (%s %d %d -> %s %d %d).",
836 format_prefix(src
->prefix
, src
->plen
),
837 format_eui64(route
->src
->id
),
838 route
->seqno
, route
->refmetric
,
839 format_eui64(src
->id
), seqno
, refmetric
);
840 if(src
!= route
->src
) {
841 uninstall_route(route
);
846 route
->src
= retain_source(src
);
847 if((feasible
|| keep_unfeasible
) && refmetric
< INFINITY
)
848 route
->time
= babel_now
.tv_sec
;
849 route
->seqno
= seqno
;
851 memset(&route
->channels
, 0, sizeof(route
->channels
));
853 memcpy(&route
->channels
, channels
,
854 MIN(channels_len
, DIVERSITY_HOPS
));
856 change_route_metric(route
,
857 refmetric
, neighbour_cost(neigh
), add_metric
);
858 route
->hold_time
= hold_time
;
860 route_changed(route
, oldsrc
, oldmetric
);
862 route_lost(oldsrc
, oldmetric
);
865 send_unfeasible_request(neigh
, route
->installed
&& route_old(route
),
867 release_source(oldsrc
);
869 struct babel_route
*new_route
;
871 if(refmetric
>= INFINITY
)
872 /* Somebody's retracting a route we never saw. */
875 send_unfeasible_request(neigh
, 0, seqno
, metric
, src
);
880 route
= malloc(sizeof(struct babel_route
));
882 perror("malloc(route)");
886 route
->src
= retain_source(src
);
887 route
->refmetric
= refmetric
;
888 route
->cost
= neighbour_cost(neigh
);
889 route
->add_metric
= add_metric
;
890 route
->seqno
= seqno
;
891 route
->neigh
= neigh
;
892 memcpy(route
->nexthop
, nexthop
, 16);
893 route
->time
= babel_now
.tv_sec
;
894 route
->hold_time
= hold_time
;
895 route
->smoothed_metric
= MAX(route_metric(route
), INFINITY
/ 2);
896 route
->smoothed_metric_time
= babel_now
.tv_sec
;
897 route
->installed
= 0;
898 memset(&route
->channels
, 0, sizeof(route
->channels
));
900 memcpy(&route
->channels
, channels
,
901 MIN(channels_len
, DIVERSITY_HOPS
));
903 new_route
= insert_route(route
);
904 if(new_route
== NULL
) {
905 flog_err(EC_BABEL_ROUTE
, "Couldn't insert route.");
909 consider_route(route
);
914 /* We just received an unfeasible update. If it's any good, send
915 a request for a new seqno. */
917 send_unfeasible_request(struct neighbour
*neigh
, int force
,
918 unsigned short seqno
, unsigned short metric
,
921 struct babel_route
*route
= find_installed_route(src
->prefix
, src
->plen
);
923 if(seqno_minus(src
->seqno
, seqno
) > 100) {
924 /* Probably a source that lost its seqno. Let it time-out. */
928 if(force
|| !route
|| route_metric(route
) >= metric
+ 512) {
929 send_unicast_multihop_request(neigh
, src
->prefix
, src
->plen
,
930 src
->metric
>= INFINITY
?
932 seqno_plus(src
->seqno
, 1),
937 /* This takes a feasible route and decides whether to install it.
938 This uses the strong ordering, which is defined by sm <= sm' AND
939 m <= m'. This ordering is not total, which is what causes
943 consider_route(struct babel_route
*route
)
945 struct babel_route
*installed
;
946 struct xroute
*xroute
;
951 if(!route_feasible(route
))
954 xroute
= find_xroute(route
->src
->prefix
, route
->src
->plen
);
958 installed
= find_installed_route(route
->src
->prefix
, route
->src
->plen
);
960 if(installed
== NULL
)
963 if(route_metric(route
) >= INFINITY
)
966 if(route_metric(installed
) >= INFINITY
)
969 if(route_metric(installed
) >= route_metric(route
) &&
970 route_smoothed_metric(installed
) > route_smoothed_metric(route
))
976 switch_routes(installed
, route
);
977 if(installed
&& route
->installed
)
978 send_triggered_update(route
, installed
->src
, route_metric(installed
));
980 send_update(NULL
, 1, route
->src
->prefix
, route
->src
->plen
);
985 retract_neighbour_routes(struct neighbour
*neigh
)
989 for(i
= 0; i
< route_slots
; i
++) {
990 struct babel_route
*r
= routes
[i
];
992 if(r
->neigh
== neigh
) {
993 if(r
->refmetric
!= INFINITY
) {
994 unsigned short oldmetric
= route_metric(r
);
996 if(oldmetric
!= INFINITY
)
997 route_changed(r
, r
->src
, oldmetric
);
1006 send_triggered_update(struct babel_route
*route
, struct source
*oldsrc
,
1009 unsigned newmetric
, diff
;
1010 /* 1 means send speedily, 2 means resend */
1013 if(!route
->installed
)
1016 newmetric
= route_metric(route
);
1018 newmetric
>= oldmetric
? newmetric
- oldmetric
: oldmetric
- newmetric
;
1020 if(route
->src
!= oldsrc
|| (oldmetric
< INFINITY
&& newmetric
>= INFINITY
))
1021 /* Switching sources can cause transient routing loops.
1022 Retractions can cause blackholes. */
1024 else if(newmetric
> oldmetric
&& oldmetric
< 6 * 256 && diff
>= 512)
1025 /* Route getting significantly worse */
1027 else if(unsatisfied_request(route
->src
->prefix
, route
->src
->plen
,
1028 route
->seqno
, route
->src
->id
))
1029 /* Make sure that requests are satisfied speedily */
1031 else if(oldmetric
>= INFINITY
&& newmetric
< INFINITY
)
1034 else if(newmetric
< oldmetric
&& diff
< 1024)
1035 /* Route getting better. This may be a transient fluctuation, so
1036 don't advertise it to avoid making routes unfeasible later on. */
1039 /* Don't fret about trivialities */
1045 send_update_resend(NULL
, route
->src
->prefix
, route
->src
->plen
);
1047 send_update(NULL
, urgent
, route
->src
->prefix
, route
->src
->plen
);
1049 if(oldmetric
< INFINITY
) {
1050 if(newmetric
>= oldmetric
+ 512) {
1051 send_request_resend(NULL
, route
->src
->prefix
, route
->src
->plen
,
1052 route
->src
->metric
>= INFINITY
?
1054 seqno_plus(route
->src
->seqno
, 1),
1056 } else if(newmetric
>= oldmetric
+ 288) {
1057 send_request(NULL
, route
->src
->prefix
, route
->src
->plen
);
1062 /* A route has just changed. Decide whether to switch to a different route or
1065 route_changed(struct babel_route
*route
,
1066 struct source
*oldsrc
, unsigned short oldmetric
)
1068 if(route
->installed
) {
1069 struct babel_route
*better_route
;
1070 /* Do this unconditionally -- microoptimisation is not worth it. */
1072 find_best_route(route
->src
->prefix
, route
->src
->plen
, 1, NULL
);
1073 if(better_route
&& route_metric(better_route
) < route_metric(route
))
1074 consider_route(better_route
);
1077 if(route
->installed
) {
1078 /* We didn't change routes after all. */
1079 send_triggered_update(route
, oldsrc
, oldmetric
);
1081 /* Reconsider routes even when their metric didn't decrease,
1082 they may not have been feasible before. */
1083 consider_route(route
);
1087 /* We just lost the installed route to a given destination. */
1089 route_lost(struct source
*src
, unsigned oldmetric
)
1091 struct babel_route
*new_route
;
1092 new_route
= find_best_route(src
->prefix
, src
->plen
, 1, NULL
);
1094 consider_route(new_route
);
1095 } else if(oldmetric
< INFINITY
) {
1096 /* Avoid creating a blackhole. */
1097 send_update_resend(NULL
, src
->prefix
, src
->plen
);
1098 /* If the route was usable enough, try to get an alternate one.
1099 If it was not, we could be dealing with oscillations around
1100 the value of INFINITY. */
1101 if(oldmetric
<= INFINITY
/ 2)
1102 send_request_resend(NULL
, src
->prefix
, src
->plen
,
1103 src
->metric
>= INFINITY
?
1104 src
->seqno
: seqno_plus(src
->seqno
, 1),
1109 /* This is called periodically to flush old routes. It will also send
1110 requests for routes that are about to expire. */
1114 struct babel_route
*r
;
1117 debugf(BABEL_DEBUG_COMMON
,"Expiring old routes.");
1120 while(i
< route_slots
) {
1123 /* Protect against clock being stepped. */
1124 if(r
->time
> babel_now
.tv_sec
|| route_old(r
)) {
1129 update_route_metric(r
);
1131 if(r
->installed
&& r
->refmetric
< INFINITY
) {
1133 /* Route about to expire, send a request. */
1134 send_unicast_request(r
->neigh
,
1135 r
->src
->prefix
, r
->src
->plen
);