1: /*
2: * This file is free software: you may copy, redistribute and/or modify it
3: * under the terms of the GNU General Public License as published by the
4: * Free Software Foundation, either version 2 of the License, or (at your
5: * option) any later version.
6: *
7: * This file is distributed in the hope that it will be useful, but
8: * WITHOUT ANY WARRANTY; without even the implied warranty of
9: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
10: * General Public License for more details.
11: *
12: * You should have received a copy of the GNU General Public License
13: * along with this program. If not, see <http://www.gnu.org/licenses/>.
14: *
15: * This file incorporates work covered by the following copyright and
16: * permission notice:
17: *
18: Copyright (c) 2007, 2008 by Juliusz Chroboczek
19:
20: Permission is hereby granted, free of charge, to any person obtaining a copy
21: of this software and associated documentation files (the "Software"), to deal
22: in the Software without restriction, including without limitation the rights
23: to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
24: copies of the Software, and to permit persons to whom the Software is
25: furnished to do so, subject to the following conditions:
26:
27: The above copyright notice and this permission notice shall be included in
28: all copies or substantial portions of the Software.
29:
30: THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
31: IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
32: FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
33: AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
34: LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
35: OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
36: THE SOFTWARE.
37: */
38:
39: #include <stdlib.h>
40: #include <string.h>
41: #include <stdio.h>
42: #include <sys/time.h>
43: #include <time.h>
44:
45: #include <zebra.h>
46: #include "if.h"
47:
48: #include "babel_main.h"
49: #include "babeld.h"
50: #include "util.h"
51: #include "babel_interface.h"
52: #include "neighbour.h"
53: #include "source.h"
54: #include "route.h"
55: #include "message.h"
56: #include "resend.h"
57:
58: struct neighbour *neighs = NULL;
59:
60: static struct neighbour *
61: find_neighbour_nocreate(const unsigned char *address, struct interface *ifp)
62: {
63: struct neighbour *neigh;
64: FOR_ALL_NEIGHBOURS(neigh) {
65: if(memcmp(address, neigh->address, 16) == 0 &&
66: neigh->ifp == ifp)
67: return neigh;
68: }
69: return NULL;
70: }
71:
72: void
73: flush_neighbour(struct neighbour *neigh)
74: {
75: flush_neighbour_routes(neigh);
76: if(unicast_neighbour == neigh)
77: flush_unicast(1);
78: flush_resends(neigh);
79:
80: if(neighs == neigh) {
81: neighs = neigh->next;
82: } else {
83: struct neighbour *previous = neighs;
84: while(previous->next != neigh)
85: previous = previous->next;
86: previous->next = neigh->next;
87: }
88: free(neigh);
89: }
90:
91: struct neighbour *
92: find_neighbour(const unsigned char *address, struct interface *ifp)
93: {
94: struct neighbour *neigh;
95: const struct timeval zero = {0, 0};
96:
97: neigh = find_neighbour_nocreate(address, ifp);
98: if(neigh)
99: return neigh;
100:
101: debugf(BABEL_DEBUG_COMMON,"Creating neighbour %s on %s.",
102: format_address(address), ifp->name);
103:
104: neigh = malloc(sizeof(struct neighbour));
105: if(neigh == NULL) {
106: zlog_err("malloc(neighbour): %s", safe_strerror(errno));
107: return NULL;
108: }
109:
110: neigh->hello_seqno = -1;
111: memcpy(neigh->address, address, 16);
112: neigh->reach = 0;
113: neigh->txcost = INFINITY;
114: neigh->ihu_time = babel_now;
115: neigh->hello_time = zero;
116: neigh->hello_interval = 0;
117: neigh->ihu_interval = 0;
118: neigh->ifp = ifp;
119: neigh->next = neighs;
120: neighs = neigh;
121: send_hello(ifp);
122: return neigh;
123: }
124:
125: /* Recompute a neighbour's rxcost. Return true if anything changed.
126: This does not call local_notify_neighbour, see update_neighbour_metric. */
127: int
128: update_neighbour(struct neighbour *neigh, int hello, int hello_interval)
129: {
130: int missed_hellos;
131: int rc = 0;
132:
133: if(hello < 0) {
134: if(neigh->hello_interval <= 0)
135: return rc;
136: missed_hellos =
137: ((int)timeval_minus_msec(&babel_now, &neigh->hello_time) -
138: neigh->hello_interval * 7) /
139: (neigh->hello_interval * 10);
140: if(missed_hellos <= 0)
141: return rc;
142: timeval_add_msec(&neigh->hello_time, &neigh->hello_time,
143: missed_hellos * neigh->hello_interval * 10);
144: } else {
145: if(neigh->hello_seqno >= 0 && neigh->reach > 0) {
146: missed_hellos = seqno_minus(hello, neigh->hello_seqno) - 1;
147: if(missed_hellos < -8) {
148: /* Probably a neighbour that rebooted and lost its seqno.
149: Reboot the universe. */
150: neigh->reach = 0;
151: missed_hellos = 0;
152: rc = 1;
153: } else if(missed_hellos < 0) {
154: if(hello_interval > neigh->hello_interval) {
155: /* This neighbour has increased its hello interval,
156: and we didn't notice. */
157: neigh->reach <<= -missed_hellos;
158: missed_hellos = 0;
159: } else {
160: /* Late hello. Probably due to the link layer buffering
161: packets during a link outage. Ignore it, but reset
162: the expected seqno. */
163: neigh->hello_seqno = hello;
164: hello = -1;
165: missed_hellos = 0;
166: }
167: rc = 1;
168: }
169: } else {
170: missed_hellos = 0;
171: }
172: neigh->hello_time = babel_now;
173: neigh->hello_interval = hello_interval;
174: }
175:
176: if(missed_hellos > 0) {
177: neigh->reach >>= missed_hellos;
178: neigh->hello_seqno = seqno_plus(neigh->hello_seqno, missed_hellos);
179: missed_hellos = 0;
180: rc = 1;
181: }
182:
183: if(hello >= 0) {
184: neigh->hello_seqno = hello;
185: neigh->reach >>= 1;
186: neigh->reach |= 0x8000;
187: if((neigh->reach & 0xFC00) != 0xFC00)
188: rc = 1;
189: }
190:
191: /* Make sure to give neighbours some feedback early after association */
192: if((neigh->reach & 0xBF00) == 0x8000) {
193: /* A new neighbour */
194: send_hello(neigh->ifp);
195: } else {
196: /* Don't send hellos, in order to avoid a positive feedback loop. */
197: int a = (neigh->reach & 0xC000);
198: int b = (neigh->reach & 0x3000);
199: if((a == 0xC000 && b == 0) || (a == 0 && b == 0x3000)) {
200: /* Reachability is either 1100 or 0011 */
201: send_self_update(neigh->ifp);
202: }
203: }
204:
205: if((neigh->reach & 0xFC00) == 0xC000) {
206: /* This is a newish neighbour, let's request a full route dump.
207: We ought to avoid this when the network is dense */
208: send_unicast_request(neigh, NULL, 0);
209: send_ihu(neigh, NULL);
210: }
211: return rc;
212: }
213:
214: static int
215: reset_txcost(struct neighbour *neigh)
216: {
217: unsigned delay;
218:
219: delay = timeval_minus_msec(&babel_now, &neigh->ihu_time);
220:
221: if(neigh->ihu_interval > 0 && delay < neigh->ihu_interval * 10U * 3U)
222: return 0;
223:
224: /* If we're losing a lot of packets, we probably lost an IHU too */
225: if(delay >= 180000 || (neigh->reach & 0xFFF0) == 0 ||
226: (neigh->ihu_interval > 0 &&
227: delay >= neigh->ihu_interval * 10U * 10U)) {
228: neigh->txcost = INFINITY;
229: neigh->ihu_time = babel_now;
230: return 1;
231: }
232:
233: return 0;
234: }
235:
236: unsigned
237: neighbour_txcost(struct neighbour *neigh)
238: {
239: return neigh->txcost;
240: }
241:
242: unsigned
243: check_neighbours()
244: {
245: struct neighbour *neigh;
246: int changed, rc;
247: unsigned msecs = 50000;
248:
249: debugf(BABEL_DEBUG_COMMON,"Checking neighbours.");
250:
251: neigh = neighs;
252: while(neigh) {
253: changed = update_neighbour(neigh, -1, 0);
254:
255: if(neigh->reach == 0 ||
256: neigh->hello_time.tv_sec > babel_now.tv_sec || /* clock stepped */
257: timeval_minus_msec(&babel_now, &neigh->hello_time) > 300000) {
258: struct neighbour *old = neigh;
259: neigh = neigh->next;
260: flush_neighbour(old);
261: continue;
262: }
263:
264: rc = reset_txcost(neigh);
265: changed = changed || rc;
266:
267: update_neighbour_metric(neigh, changed);
268:
269: if(neigh->hello_interval > 0)
270: msecs = MIN(msecs, neigh->hello_interval * 10U);
271: if(neigh->ihu_interval > 0)
272: msecs = MIN(msecs, neigh->ihu_interval * 10U);
273: neigh = neigh->next;
274: }
275:
276: return msecs;
277: }
278:
279: unsigned
280: neighbour_rxcost(struct neighbour *neigh)
281: {
282: unsigned delay;
283: unsigned short reach = neigh->reach;
284:
285: delay = timeval_minus_msec(&babel_now, &neigh->hello_time);
286:
287: if((reach & 0xFFF0) == 0 || delay >= 180000) {
288: return INFINITY;
289: } else if(babel_get_if_nfo(neigh->ifp)->flags & BABEL_IF_LQ) {
290: int sreach =
291: ((reach & 0x8000) >> 2) +
292: ((reach & 0x4000) >> 1) +
293: (reach & 0x3FFF);
294: /* 0 <= sreach <= 0x7FFF */
295: int cost = (0x8000 * babel_get_if_nfo(neigh->ifp)->cost) / (sreach + 1);
296: /* cost >= interface->cost */
297: if(delay >= 40000)
298: cost = (cost * (delay - 20000) + 10000) / 20000;
299: return MIN(cost, INFINITY);
300: } else {
301: /* To lose one hello is a misfortune, to lose two is carelessness. */
302: if((reach & 0xC000) == 0xC000)
303: return babel_get_if_nfo(neigh->ifp)->cost;
304: else if((reach & 0xC000) == 0)
305: return INFINITY;
306: else if((reach & 0x2000))
307: return babel_get_if_nfo(neigh->ifp)->cost;
308: else
309: return INFINITY;
310: }
311: }
312:
313: unsigned
314: neighbour_cost(struct neighbour *neigh)
315: {
316: unsigned a, b;
317:
318: if(!if_up(neigh->ifp))
319: return INFINITY;
320:
321: a = neighbour_txcost(neigh);
322:
323: if(a >= INFINITY)
324: return INFINITY;
325:
326: b = neighbour_rxcost(neigh);
327: if(b >= INFINITY)
328: return INFINITY;
329:
330: if(!(babel_get_if_nfo(neigh->ifp)->flags & BABEL_IF_LQ)
331: || (a < 256 && b < 256)) {
332: return a;
333: } else {
334: /* a = 256/alpha, b = 256/beta, where alpha and beta are the expected
335: probabilities of a packet getting through in the direct and reverse
336: directions. */
337: a = MAX(a, 256);
338: b = MAX(b, 256);
339: /* 1/(alpha * beta), which is just plain ETX. */
340: /* Since a and b are capped to 16 bits, overflow is impossible. */
341: return (a * b + 128) >> 8;
342: }
343: }
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to neighbour.c CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / quagga / babeld