Babel: Route selection can pick no-longer-feasible routes, creating routing loops
Hello all, First of all, this is my first time reaching/contributing to a large project so if anything is wrong or missing please let me know. For my Bachelor's thesis I am emulating some nodes (25/50) on CORE emulator (https://github.com/coreemu/core) and a part of the thesis became to compare the Babel (RFC 8966) implementations in babeld and BIRD. While doing that, I found that BIRD is able to create routing loops in some edge-case scenarios. Using the same settings with babeld doesn't cause them. I looked up a bit and found that it could possibly be a regression that got created while switching from BIRD 1.x to 2.x (commit 3b3b0910, https://gitlab.nic.cz/labs/bird/-/commit/3b3b0910ffb1b212b1c9ea420db6c575a3e..., first released in 2.0.0). The commit mentions "Route update, selection and retraction simplified and fixed" and "Route feasibility is evalualated per update and stored with route". The problem arises when a route gets marked as safe, then the links change and the distances get updated, and a link change again finally to force the nodes/routers to their previously learned routes again. BIRD currently checks the feasibility distance metric only when an update is received from a neighbor, but this causes stale cached feasible-marked routes if the updates for that link is slower or more rare for some reason (in my cases, Wi-Fi collisions dropping some of the frames or during mobility when nodes are able to connect and disconnect briefly). If a node's own advertised metric improves later, the cached evaluation can become outdated and BIRD can still switch to the route, which can create a routing loop. In other words, with these link costs: 100 100 A -------- B -------- D | | C --------------------- 100 500 B learns a backup route to D via A (metric 600 + 100 = 700) at a time when A still reached D via C and later A switched to B. When B --- D breaks before A's next update reaches B, B immediately switches to that old backup route via A, but A's route to D now goes via B so A and B forward D's packets to each other. Depending on timing, the loop forms between A and B or between A and C. I also created an isolated minimal script using Linux namespaces to retrigger the issue, and tried a possible patch that restores the checks in addition to the cached feasibility status, and it seems to solve the problem. My knowledge on BIRD codebase or how to utilize namespaecs on bash scripts is not so good, so I got some help from LLM but I then -largely- simplified the script manually and checked the patch code, reproducer and the result it gives by myself (as per the CONTRIBUTING.md) and it seems to show the issue I am getting well. I wanted to reach out to ask whether this is something that is a bug/regression or am I understanding or configuring something very wrong. Have a good day! Kind Regards, Yağızhan Extra Info (from the script: BIRD 3.3.3, 4 network namespaces, wired links with the costs above, hello 1 s, update interval 10 s, C to A 120s to emulate lost updates):
sudo ./m_reproducer_babel_loop.sh 4s step 1, B-D down: A=a-c/600 C=c-d/500 11s step 2, B-D up: A=a-b/200 C=c-a/300 12s step 3, B-D down again 13s A=a-b/200 B=b-a/700 C=c-a/300 <- LOOP A-B 13s ping A->D: From 2001:db8:a::1 icmp_seq=1 Time exceeded: Hop limit 42s A=a-b/200 B=unreach/ C=c-a/300 42s A=unreach/ B=unreach/ C=c-d/500 45s A=a-c/600 B=unreach/ C=c-d/500 RESULT loop_s=28.5 (logs: /tmp/tmp.l6X9tMI2CV)
I normally use CORE emulator and EMANE for Wi-Fi physics so it is not about the intervals (in my thesis setup the intervals are the same in all nodes), but to be able to create that lost/delayed packet effect without requiring to install and configure both I created something like this to demonstrate. Possible Patch Tests: Without the change the loop appears in 10 of 10 runs (26–33 s), with the patch the loops disappear. I also tested the patch on 2.20, the current version loops, patch fixes the loops there as well. Attached: the patch (from git format-patch) and the reproducer script. -- Kind Regards, Yağızhan (This mail has been digitally signed. Please check email.yagz.eu for the PGP keys.)
participants (1)
-
Yagizhan Isik