]>
git.proxmox.com Git - mirror_frr.git/blob - babeld/neighbour.c
2 Copyright (c) 2007, 2008 by Juliusz Chroboczek
4 Permission is hereby granted, free of charge, to any person obtaining a copy
5 of this software and associated documentation files (the "Software"), to deal
6 in the Software without restriction, including without limitation the rights
7 to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
8 copies of the Software, and to permit persons to whom the Software is
9 furnished to do so, subject to the following conditions:
11 The above copyright notice and this permission notice shall be included in
12 all copies or substantial portions of the Software.
14 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
15 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
16 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
17 AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
18 LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
19 OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
36 #include "babel_main.h"
39 #include "babel_interface.h"
40 #include "neighbour.h"
45 #include "babel_errors.h"
47 struct neighbour
*neighs
= NULL
;
49 static struct neighbour
*
50 find_neighbour_nocreate(const unsigned char *address
, struct interface
*ifp
)
52 struct neighbour
*neigh
;
53 FOR_ALL_NEIGHBOURS(neigh
) {
54 if(memcmp(address
, neigh
->address
, 16) == 0 &&
62 flush_neighbour(struct neighbour
*neigh
)
64 debugf(BABEL_DEBUG_COMMON
,"Flushing neighbour %s (reach 0x%04x)",
65 format_address(neigh
->address
), neigh
->reach
);
66 flush_neighbour_routes(neigh
);
67 if(unicast_neighbour
== neigh
)
74 struct neighbour
*previous
= neighs
;
75 while(previous
->next
!= neigh
)
76 previous
= previous
->next
;
77 previous
->next
= neigh
->next
;
83 find_neighbour(const unsigned char *address
, struct interface
*ifp
)
85 struct neighbour
*neigh
;
86 const struct timeval zero
= {0, 0};
88 neigh
= find_neighbour_nocreate(address
, ifp
);
92 debugf(BABEL_DEBUG_COMMON
,"Creating neighbour %s on %s.",
93 format_address(address
), ifp
->name
);
95 neigh
= malloc(sizeof(struct neighbour
));
97 flog_err(EC_BABEL_MEMORY
, "malloc(neighbour): %s",
98 safe_strerror(errno
));
102 neigh
->hello_seqno
= -1;
103 memcpy(neigh
->address
, address
, 16);
105 neigh
->txcost
= INFINITY
;
106 neigh
->ihu_time
= babel_now
;
107 neigh
->hello_time
= zero
;
108 neigh
->hello_interval
= 0;
109 neigh
->ihu_interval
= 0;
110 neigh
->hello_send_us
= 0;
111 neigh
->hello_rtt_receive_time
= zero
;
113 neigh
->rtt_time
= zero
;
115 neigh
->next
= neighs
;
121 /* Recompute a neighbour's rxcost. Return true if anything changed. */
123 update_neighbour(struct neighbour
*neigh
, int hello
, int hello_interval
)
129 if(neigh
->hello_interval
== 0)
132 ((int)timeval_minus_msec(&babel_now
, &neigh
->hello_time
) -
133 neigh
->hello_interval
* 7) /
134 (neigh
->hello_interval
* 10);
135 if(missed_hellos
<= 0)
137 timeval_add_msec(&neigh
->hello_time
, &neigh
->hello_time
,
138 missed_hellos
* neigh
->hello_interval
* 10);
140 if(neigh
->hello_seqno
>= 0 && neigh
->reach
> 0) {
141 missed_hellos
= seqno_minus(hello
, neigh
->hello_seqno
) - 1;
142 if(missed_hellos
< -8) {
143 /* Probably a neighbour that rebooted and lost its seqno.
144 Reboot the universe. */
148 } else if(missed_hellos
< 0) {
149 if(hello_interval
> neigh
->hello_interval
) {
150 /* This neighbour has increased its hello interval,
151 and we didn't notice. */
152 neigh
->reach
<<= -missed_hellos
;
155 /* Late hello. Probably due to the link layer buffering
156 packets during a link outage. Ignore it, but reset
157 the expected seqno. */
158 neigh
->hello_seqno
= hello
;
167 neigh
->hello_time
= babel_now
;
168 neigh
->hello_interval
= hello_interval
;
171 if(missed_hellos
> 0) {
172 neigh
->reach
>>= missed_hellos
;
173 neigh
->hello_seqno
= seqno_plus(neigh
->hello_seqno
, missed_hellos
);
178 neigh
->hello_seqno
= hello
;
180 neigh
->reach
|= 0x8000;
181 if((neigh
->reach
& 0xFC00) != 0xFC00)
185 /* Make sure to give neighbours some feedback early after association */
186 if((neigh
->reach
& 0xBF00) == 0x8000) {
187 /* A new neighbour */
188 send_hello(neigh
->ifp
);
190 /* Don't send hellos, in order to avoid a positive feedback loop. */
191 int a
= (neigh
->reach
& 0xC000);
192 int b
= (neigh
->reach
& 0x3000);
193 if((a
== 0xC000 && b
== 0) || (a
== 0 && b
== 0x3000)) {
194 /* Reachability is either 1100 or 0011 */
195 send_self_update(neigh
->ifp
);
199 if((neigh
->reach
& 0xFC00) == 0xC000) {
200 /* This is a newish neighbour, let's request a full route dump.
201 We ought to avoid this when the network is dense */
202 send_unicast_request(neigh
, NULL
, 0);
203 send_ihu(neigh
, NULL
);
209 reset_txcost(struct neighbour
*neigh
)
213 delay
= timeval_minus_msec(&babel_now
, &neigh
->ihu_time
);
215 if(neigh
->ihu_interval
> 0 && delay
< neigh
->ihu_interval
* 10U * 3U)
218 /* If we're losing a lot of packets, we probably lost an IHU too */
219 if(delay
>= 180000 || (neigh
->reach
& 0xFFF0) == 0 ||
220 (neigh
->ihu_interval
> 0 &&
221 delay
>= neigh
->ihu_interval
* 10U * 10U)) {
222 neigh
->txcost
= INFINITY
;
223 neigh
->ihu_time
= babel_now
;
231 neighbour_txcost(struct neighbour
*neigh
)
233 return neigh
->txcost
;
237 check_neighbours(void)
239 struct neighbour
*neigh
;
241 unsigned msecs
= 50000;
243 debugf(BABEL_DEBUG_COMMON
,"Checking neighbours.");
247 changed
= update_neighbour(neigh
, -1, 0);
249 if(neigh
->reach
== 0 ||
250 neigh
->hello_time
.tv_sec
> babel_now
.tv_sec
|| /* clock stepped */
251 timeval_minus_msec(&babel_now
, &neigh
->hello_time
) > 300000) {
252 struct neighbour
*old
= neigh
;
254 flush_neighbour(old
);
258 rc
= reset_txcost(neigh
);
259 changed
= changed
|| rc
;
261 update_neighbour_metric(neigh
, changed
);
263 if(neigh
->hello_interval
> 0)
264 msecs
= MIN(msecs
, neigh
->hello_interval
* 10U);
265 if(neigh
->ihu_interval
> 0)
266 msecs
= MIN(msecs
, neigh
->ihu_interval
* 10U);
274 neighbour_rxcost(struct neighbour
*neigh
)
277 unsigned short reach
= neigh
->reach
;
279 delay
= timeval_minus_msec(&babel_now
, &neigh
->hello_time
);
281 if((reach
& 0xFFF0) == 0 || delay
>= 180000) {
283 } else if(babel_get_if_nfo(neigh
->ifp
)->flags
& BABEL_IF_LQ
) {
285 ((reach
& 0x8000) >> 2) +
286 ((reach
& 0x4000) >> 1) +
288 /* 0 <= sreach <= 0x7FFF */
289 int cost
= (0x8000 * babel_get_if_nfo(neigh
->ifp
)->cost
) / (sreach
+ 1);
290 /* cost >= interface->cost */
292 cost
= (cost
* (delay
- 20000) + 10000) / 20000;
293 return MIN(cost
, INFINITY
);
295 /* To lose one hello is a misfortune, to lose two is carelessness. */
296 if((reach
& 0xC000) == 0xC000)
297 return babel_get_if_nfo(neigh
->ifp
)->cost
;
298 else if((reach
& 0xC000) == 0)
300 else if((reach
& 0x2000))
301 return babel_get_if_nfo(neigh
->ifp
)->cost
;
308 neighbour_rttcost(struct neighbour
*neigh
)
310 struct interface
*ifp
= neigh
->ifp
;
311 babel_interface_nfo
*babel_ifp
= babel_get_if_nfo(ifp
);
313 if(!babel_ifp
->max_rtt_penalty
|| !valid_rtt(neigh
))
316 /* Function: linear behaviour between rtt_min and rtt_max. */
317 if(neigh
->rtt
<= babel_ifp
->rtt_min
) {
319 } else if(neigh
->rtt
<= babel_ifp
->rtt_max
) {
320 unsigned long long tmp
=
321 (unsigned long long)babel_ifp
->max_rtt_penalty
*
322 (neigh
->rtt
- babel_ifp
->rtt_min
) /
323 (babel_ifp
->rtt_max
- babel_ifp
->rtt_min
);
324 assert((tmp
& 0x7FFFFFFF) == tmp
);
327 return babel_ifp
->max_rtt_penalty
;
332 neighbour_cost(struct neighbour
*neigh
)
336 if(!if_up(neigh
->ifp
))
339 a
= neighbour_txcost(neigh
);
344 b
= neighbour_rxcost(neigh
);
348 if(!(babel_get_if_nfo(neigh
->ifp
)->flags
& BABEL_IF_LQ
)
349 || (a
< 256 && b
< 256)) {
352 /* a = 256/alpha, b = 256/beta, where alpha and beta are the expected
353 probabilities of a packet getting through in the direct and reverse
357 /* 1/(alpha * beta), which is just plain ETX. */
358 /* Since a and b are capped to 16 bits, overflow is impossible. */
359 cost
= (a
* b
+ 128) >> 8;
362 cost
+= neighbour_rttcost(neigh
);
364 return MIN(cost
, INFINITY
);
368 valid_rtt(struct neighbour
*neigh
)
370 return (timeval_minus_msec(&babel_now
, &neigh
->rtt_time
) < 180000) ? 1 : 0;