| 615 | } |
| 616 | |
| 617 | func SolveStarvation(router *state.RouterState, r Router) { |
| 618 | // 3.8.2.1. Avoiding Starvation |
| 619 | |
| 620 | // When a route is retracted or expires, a Babel node usually switches |
| 621 | // to another feasible route for the same prefix. It may be the case, |
| 622 | // however, that no such routes are available. |
| 623 | // |
| 624 | // A node that has lost all feasible routes to a given destination but |
| 625 | // still has unexpired unfeasible routes to that destination MUST send a |
| 626 | // seqno request; if it doesn't have any such routes, it MAY still send |
| 627 | // a seqno request. |
| 628 | |
| 629 | isFeasible := make(map[state.Source]bool) |
| 630 | |
| 631 | for _, neigh := range router.Neighbours { |
| 632 | if neigh.BestEndpoint() == nil { |
| 633 | continue // no endpoint to this neighbour |
| 634 | } |
| 635 | for _, route := range neigh.Routes { |
| 636 | curFeasible, present := isFeasible[route.Source] |
| 637 | routeFeasible := route.Metric != state.INF && checkFeasibility(router, route.PubRoute) |
| 638 | isFeasible[route.Source] = (present && curFeasible) || routeFeasible |
| 639 | } |
| 640 | } |
| 641 | |
| 642 | // |
| 643 | // The router-id of the request is set to the router- |
| 644 | // id of the route that it has just lost, and the requested seqno is the |
| 645 | // value contained in the source table plus 1. The request carries a |
| 646 | // hop count, which is used as a last-resort mechanism to ensure that it |
| 647 | // eventually vanishes from the network; it MAY be set to any value that |
| 648 | // is larger than the diameter of the network (64 is a suitable default |
| 649 | // value). |
| 650 | // |
| 651 | // If the node has any (unfeasible) routes to the requested destination, |
| 652 | // then it MUST send the request to at least one of the next-hop |
| 653 | // neighbours that advertised these routes, and SHOULD send it to all of |
| 654 | // them; in any case, it MAY send the request to any other neighbours, |
| 655 | // whether they advertise a route to the requested destination or not. |
| 656 | // A simple implementation strategy is therefore to unconditionally |
| 657 | // multicast the request over all interfaces. |
| 658 | |
| 659 | for src, feasible := range isFeasible { |
| 660 | if !feasible && src.NodeId != router.Id { |
| 661 | r.BroadcastRequestSeqno(src, router.Sources[src].Seqno+1, router.SeqnoRequestHopCount) |
| 662 | r.RouterEvent(log.EventSeqnoRequested, "requested seqno", "src", src, "seqno", router.Sources[src].Seqno+1) |
| 663 | } |
| 664 | } |
| 665 | |
| 666 | // Similar requests will be sent by other nodes that are affected by the |
| 667 | // route's loss. If the network is still connected, and assuming no |
| 668 | // packet loss, then at least one of these requests will be forwarded to |
| 669 | // the source, resulting in a route being advertised with a new sequence |
| 670 | // number. (Due to duplicate suppression, only a small number of such |
| 671 | // requests are expected to actually reach the source.) |
| 672 | } |
| 673 | |
| 674 | func ShouldSwitch(curRoute state.SelRoute, newRoute state.SelRoute, tunable *state.RouterTunables) bool { |