]>
git.proxmox.com Git - mirror_frr.git/blob - babeld/neighbour.c
48a32c4a9c39c658d86ee6564958475685ed20cf
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
32 #include "babel_main.h"
35 #include "babel_interface.h"
36 #include "neighbour.h"
42 struct neighbour
*neighs
= NULL
;
44 static struct neighbour
*
45 find_neighbour_nocreate(const unsigned char *address
, struct interface
*ifp
)
47 struct neighbour
*neigh
;
48 FOR_ALL_NEIGHBOURS(neigh
) {
49 if(memcmp(address
, neigh
->address
, 16) == 0 &&
57 flush_neighbour(struct neighbour
*neigh
)
59 debugf(BABEL_DEBUG_COMMON
,"Flushing neighbour %s (reach 0x%04x)",
60 format_address(neigh
->address
), neigh
->reach
);
61 flush_neighbour_routes(neigh
);
62 if(unicast_neighbour
== neigh
)
69 struct neighbour
*previous
= neighs
;
70 while(previous
->next
!= neigh
)
71 previous
= previous
->next
;
72 previous
->next
= neigh
->next
;
78 find_neighbour(const unsigned char *address
, struct interface
*ifp
)
80 struct neighbour
*neigh
;
81 const struct timeval zero
= {0, 0};
83 neigh
= find_neighbour_nocreate(address
, ifp
);
87 debugf(BABEL_DEBUG_COMMON
,"Creating neighbour %s on %s.",
88 format_address(address
), ifp
->name
);
90 neigh
= malloc(sizeof(struct neighbour
));
92 zlog_err("malloc(neighbour): %s", safe_strerror(errno
));
96 neigh
->hello_seqno
= -1;
97 memcpy(neigh
->address
, address
, 16);
99 neigh
->txcost
= INFINITY
;
100 neigh
->ihu_time
= babel_now
;
101 neigh
->hello_time
= zero
;
102 neigh
->hello_interval
= 0;
103 neigh
->ihu_interval
= 0;
104 neigh
->hello_send_us
= 0;
105 neigh
->hello_rtt_receive_time
= zero
;
107 neigh
->rtt_time
= zero
;
109 neigh
->next
= neighs
;
115 /* Recompute a neighbour's rxcost. Return true if anything changed. */
117 update_neighbour(struct neighbour
*neigh
, int hello
, int hello_interval
)
123 if(neigh
->hello_interval
<= 0)
126 ((int)timeval_minus_msec(&babel_now
, &neigh
->hello_time
) -
127 neigh
->hello_interval
* 7) /
128 (neigh
->hello_interval
* 10);
129 if(missed_hellos
<= 0)
131 timeval_add_msec(&neigh
->hello_time
, &neigh
->hello_time
,
132 missed_hellos
* neigh
->hello_interval
* 10);
134 if(neigh
->hello_seqno
>= 0 && neigh
->reach
> 0) {
135 missed_hellos
= seqno_minus(hello
, neigh
->hello_seqno
) - 1;
136 if(missed_hellos
< -8) {
137 /* Probably a neighbour that rebooted and lost its seqno.
138 Reboot the universe. */
142 } else if(missed_hellos
< 0) {
143 if(hello_interval
> neigh
->hello_interval
) {
144 /* This neighbour has increased its hello interval,
145 and we didn't notice. */
146 neigh
->reach
<<= -missed_hellos
;
149 /* Late hello. Probably due to the link layer buffering
150 packets during a link outage. Ignore it, but reset
151 the expected seqno. */
152 neigh
->hello_seqno
= hello
;
161 neigh
->hello_time
= babel_now
;
162 neigh
->hello_interval
= hello_interval
;
165 if(missed_hellos
> 0) {
166 neigh
->reach
>>= missed_hellos
;
167 neigh
->hello_seqno
= seqno_plus(neigh
->hello_seqno
, missed_hellos
);
172 neigh
->hello_seqno
= hello
;
174 neigh
->reach
|= 0x8000;
175 if((neigh
->reach
& 0xFC00) != 0xFC00)
179 /* Make sure to give neighbours some feedback early after association */
180 if((neigh
->reach
& 0xBF00) == 0x8000) {
181 /* A new neighbour */
182 send_hello(neigh
->ifp
);
184 /* Don't send hellos, in order to avoid a positive feedback loop. */
185 int a
= (neigh
->reach
& 0xC000);
186 int b
= (neigh
->reach
& 0x3000);
187 if((a
== 0xC000 && b
== 0) || (a
== 0 && b
== 0x3000)) {
188 /* Reachability is either 1100 or 0011 */
189 send_self_update(neigh
->ifp
);
193 if((neigh
->reach
& 0xFC00) == 0xC000) {
194 /* This is a newish neighbour, let's request a full route dump.
195 We ought to avoid this when the network is dense */
196 send_unicast_request(neigh
, NULL
, 0);
197 send_ihu(neigh
, NULL
);
203 reset_txcost(struct neighbour
*neigh
)
207 delay
= timeval_minus_msec(&babel_now
, &neigh
->ihu_time
);
209 if(neigh
->ihu_interval
> 0 && delay
< neigh
->ihu_interval
* 10U * 3U)
212 /* If we're losing a lot of packets, we probably lost an IHU too */
213 if(delay
>= 180000 || (neigh
->reach
& 0xFFF0) == 0 ||
214 (neigh
->ihu_interval
> 0 &&
215 delay
>= neigh
->ihu_interval
* 10U * 10U)) {
216 neigh
->txcost
= INFINITY
;
217 neigh
->ihu_time
= babel_now
;
225 neighbour_txcost(struct neighbour
*neigh
)
227 return neigh
->txcost
;
233 struct neighbour
*neigh
;
235 unsigned msecs
= 50000;
237 debugf(BABEL_DEBUG_COMMON
,"Checking neighbours.");
241 changed
= update_neighbour(neigh
, -1, 0);
243 if(neigh
->reach
== 0 ||
244 neigh
->hello_time
.tv_sec
> babel_now
.tv_sec
|| /* clock stepped */
245 timeval_minus_msec(&babel_now
, &neigh
->hello_time
) > 300000) {
246 struct neighbour
*old
= neigh
;
248 flush_neighbour(old
);
252 rc
= reset_txcost(neigh
);
253 changed
= changed
|| rc
;
255 update_neighbour_metric(neigh
, changed
);
257 if(neigh
->hello_interval
> 0)
258 msecs
= MIN(msecs
, neigh
->hello_interval
* 10U);
259 if(neigh
->ihu_interval
> 0)
260 msecs
= MIN(msecs
, neigh
->ihu_interval
* 10U);
268 neighbour_rxcost(struct neighbour
*neigh
)
271 unsigned short reach
= neigh
->reach
;
273 delay
= timeval_minus_msec(&babel_now
, &neigh
->hello_time
);
275 if((reach
& 0xFFF0) == 0 || delay
>= 180000) {
277 } else if(babel_get_if_nfo(neigh
->ifp
)->flags
& BABEL_IF_LQ
) {
279 ((reach
& 0x8000) >> 2) +
280 ((reach
& 0x4000) >> 1) +
282 /* 0 <= sreach <= 0x7FFF */
283 int cost
= (0x8000 * babel_get_if_nfo(neigh
->ifp
)->cost
) / (sreach
+ 1);
284 /* cost >= interface->cost */
286 cost
= (cost
* (delay
- 20000) + 10000) / 20000;
287 return MIN(cost
, INFINITY
);
289 /* To lose one hello is a misfortune, to lose two is carelessness. */
290 if((reach
& 0xC000) == 0xC000)
291 return babel_get_if_nfo(neigh
->ifp
)->cost
;
292 else if((reach
& 0xC000) == 0)
294 else if((reach
& 0x2000))
295 return babel_get_if_nfo(neigh
->ifp
)->cost
;
302 neighbour_rttcost(struct neighbour
*neigh
)
304 struct interface
*ifp
= neigh
->ifp
;
305 babel_interface_nfo
*babel_ifp
= babel_get_if_nfo(ifp
);
307 if(!babel_ifp
->max_rtt_penalty
|| !valid_rtt(neigh
))
310 /* Function: linear behaviour between rtt_min and rtt_max. */
311 if(neigh
->rtt
<= babel_ifp
->rtt_min
) {
313 } else if(neigh
->rtt
<= babel_ifp
->rtt_max
) {
314 unsigned long long tmp
=
315 (unsigned long long)babel_ifp
->max_rtt_penalty
*
316 (neigh
->rtt
- babel_ifp
->rtt_min
) /
317 (babel_ifp
->rtt_max
- babel_ifp
->rtt_min
);
318 assert((tmp
& 0x7FFFFFFF) == tmp
);
321 return babel_ifp
->max_rtt_penalty
;
326 neighbour_cost(struct neighbour
*neigh
)
330 if(!if_up(neigh
->ifp
))
333 a
= neighbour_txcost(neigh
);
338 b
= neighbour_rxcost(neigh
);
342 if(!(babel_get_if_nfo(neigh
->ifp
)->flags
& BABEL_IF_LQ
)
343 || (a
< 256 && b
< 256)) {
346 /* a = 256/alpha, b = 256/beta, where alpha and beta are the expected
347 probabilities of a packet getting through in the direct and reverse
351 /* 1/(alpha * beta), which is just plain ETX. */
352 /* Since a and b are capped to 16 bits, overflow is impossible. */
353 cost
= (a
* b
+ 128) >> 8;
356 cost
+= neighbour_rttcost(neigh
);
358 return MIN(cost
, INFINITY
);
362 valid_rtt(struct neighbour
*neigh
)
364 return (timeval_minus_msec(&babel_now
, &neigh
->rtt_time
) < 180000) ? 1 : 0;