Annotation of embedaddon/quagga/babeld/neighbour.c, revision 1.1
1.1 ! misho 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