diff options
| -rw-r--r-- | server/server.go | 4 | ||||
| -rw-r--r-- | server/server_test.go | 2 | ||||
| -rw-r--r-- | table/destination.go | 420 | ||||
| -rw-r--r-- | table/table_manager.go | 18 | ||||
| -rw-r--r-- | table/table_manager_test.go | 2 |
5 files changed, 210 insertions, 236 deletions
diff --git a/server/server.go b/server/server.go index e766d84e..30fb9c22 100644 --- a/server/server.go +++ b/server/server.go @@ -701,7 +701,7 @@ func (server *BgpServer) dropPeerAllRoutes(peer *Peer, families []bgp.RouteFamil } } -func dstsToPaths(id string, as uint32, dsts []*table.Destination) ([]*table.Path, []*table.Path, [][]*table.Path) { +func dstsToPaths(id string, as uint32, dsts []*table.Update) ([]*table.Path, []*table.Path, [][]*table.Path) { bestList := make([]*table.Path, 0, len(dsts)) oldList := make([]*table.Path, 0, len(dsts)) mpathList := make([][]*table.Path, 0, len(dsts)) @@ -717,7 +717,7 @@ func dstsToPaths(id string, as uint32, dsts []*table.Destination) ([]*table.Path return bestList, oldList, mpathList } -func (server *BgpServer) propagateUpdateToNeighbors(source *Peer, newPath *table.Path, dsts []*table.Destination, needOld bool) { +func (server *BgpServer) propagateUpdateToNeighbors(source *Peer, newPath *table.Path, dsts []*table.Update, needOld bool) { if table.SelectionOptions.DisableBestPathSelection { return } diff --git a/server/server_test.go b/server/server_test.go index 720202d0..0bbd4070 100644 --- a/server/server_test.go +++ b/server/server_test.go @@ -269,7 +269,7 @@ func newPeerandInfo(myAs, as uint32, address string, rib *table.TableManager) (* } func process(rib *table.TableManager, l []*table.Path) (*table.Path, *table.Path) { - dsts := make([]*table.Destination, 0) + dsts := make([]*table.Update, 0) for _, path := range l { dsts = append(dsts, rib.Update(path)...) } diff --git a/table/destination.go b/table/destination.go index 6dac57db..44f65e7f 100644 --- a/table/destination.go +++ b/table/destination.go @@ -166,14 +166,11 @@ func NewPeerInfo(g *config.Global, p *config.Neighbor) *PeerInfo { } type Destination struct { - routeFamily bgp.RouteFamily - nlri bgp.AddrPrefixInterface - knownPathList paths - withdrawList paths - newPathList paths - oldKnownPathList paths - RadixKey string - localIdMap *Bitmap + routeFamily bgp.RouteFamily + nlri bgp.AddrPrefixInterface + knownPathList []*Path + RadixKey string + localIdMap *Bitmap } func NewDestination(nlri bgp.AddrPrefixInterface, mapSize int, known ...*Path) *Destination { @@ -181,8 +178,6 @@ func NewDestination(nlri bgp.AddrPrefixInterface, mapSize int, known ...*Path) * routeFamily: bgp.AfiSafiToRouteFamily(nlri.AFI(), nlri.SAFI()), nlri: nlri, knownPathList: known, - withdrawList: make([]*Path, 0), - newPathList: make([]*Path, 0), localIdMap: NewBitmap(mapSize), } // the id zero means id is not allocated yet. @@ -243,8 +238,8 @@ func (dd *Destination) GetKnownPathList(id string, as uint32) []*Path { return list } -func getBestPath(id string, as uint32, pathList *paths) *Path { - for _, p := range *pathList { +func getBestPath(id string, as uint32, pathList []*Path) *Path { + for _, p := range pathList { if rsFilter(id, as, p) { continue } @@ -257,100 +252,11 @@ func getBestPath(id string, as uint32, pathList *paths) *Path { } func (dd *Destination) GetBestPath(id string, as uint32) *Path { - return getBestPath(id, as, &dd.knownPathList) -} - -func getMultiBestPath(id string, pathList *paths) []*Path { - list := make([]*Path, 0, len(*pathList)) - var best *Path - for _, p := range *pathList { - if !p.IsNexthopInvalid { - if best == nil { - best = p - list = append(list, p) - } else if best.Compare(p) == 0 { - list = append(list, p) - } - } - } - return list + return getBestPath(id, as, dd.knownPathList) } func (dd *Destination) GetMultiBestPath(id string) []*Path { - return getMultiBestPath(id, &dd.knownPathList) -} - -func (dd *Destination) GetAddPathChanges(id string) []*Path { - l := make([]*Path, 0, len(dd.newPathList)+len(dd.withdrawList)) - for _, p := range dd.newPathList { - l = append(l, p) - } - for _, p := range dd.withdrawList { - l = append(l, p.Clone(true)) - } - return l -} - -func (dd *Destination) GetChanges(id string, as uint32, peerDown bool) (*Path, *Path, []*Path) { - best, old := func(id string) (*Path, *Path) { - old := getBestPath(id, as, &dd.oldKnownPathList) - best := dd.GetBestPath(id, as) - if best != nil && best.Equal(old) { - // RFC4684 3.2. Intra-AS VPN Route Distribution - // When processing RT membership NLRIs received from internal iBGP - // peers, it is necessary to consider all available iBGP paths for a - // given RT prefix, for building the outbound route filter, and not just - // the best path. - if best.GetRouteFamily() == bgp.RF_RTC_UC { - return best, old - } - // For BGP Nexthop Tracking, checks if the nexthop reachability - // was changed or not. - if best.IsNexthopInvalid != old.IsNexthopInvalid { - return best, old - } - return nil, old - } - if best == nil { - if old == nil { - return nil, nil - } - if peerDown { - // withdraws were generated by peer - // down so paths are not in knowpath - // or adjin. - old.IsWithdraw = true - return old, old - } - return old.Clone(true), old - } - return best, old - }(id) - - var multi []*Path - - if id == GLOBAL_RIB_NAME && UseMultiplePaths.Enabled { - diff := func(lhs, rhs []*Path) bool { - if len(lhs) != len(rhs) { - return true - } - for idx, l := range lhs { - if !l.Equal(rhs[idx]) { - return true - } - } - return false - } - oldM := getMultiBestPath(id, &dd.oldKnownPathList) - newM := dd.GetMultiBestPath(id) - if diff(oldM, newM) { - multi = newM - if len(newM) == 0 { - multi = []*Path{best} - } - } - } - return best, old, multi + return getMultiBestPath(id, dd.knownPathList) } func (dd *Destination) validatePath(path *Path) { @@ -369,11 +275,9 @@ func (dd *Destination) validatePath(path *Path) { // // Modifies destination's state related to stored paths. Removes withdrawn // paths from known paths. Also, adds new paths to known paths. -func (dest *Destination) Calculate(newPath *Path) *Destination { +func (dest *Destination) Calculate(newPath *Path) *Update { oldKnownPathList := make([]*Path, len(dest.knownPathList)) copy(oldKnownPathList, dest.knownPathList) - newPathList := make([]*Path, 0) - withdrawList := make([]*Path, 0) if newPath.IsWithdraw { p := dest.explicitWithdraw(newPath) @@ -382,11 +286,9 @@ func (dest *Destination) Calculate(newPath *Path) *Destination { dest.localIdMap.Unflag(uint(id)) } } - withdrawList = append(withdrawList, newPath) } else { dest.implicitWithdraw(newPath) dest.knownPathList = append(dest.knownPathList, newPath) - newPathList = append(newPathList, newPath) } for _, path := range dest.knownPathList { @@ -402,13 +304,11 @@ func (dest *Destination) Calculate(newPath *Path) *Destination { // Compute new best path dest.computeKnownBestPath() - return &Destination{ - routeFamily: dest.routeFamily, - nlri: dest.nlri, - knownPathList: dest.knownPathList, - oldKnownPathList: oldKnownPathList, - newPathList: newPathList, - withdrawList: withdrawList, + l := make([]*Path, len(dest.knownPathList)) + copy(l, dest.knownPathList) + return &Update{ + KnownPathList: l, + OldKnownPathList: oldKnownPathList, } } @@ -521,7 +421,7 @@ func (dest *Destination) computeKnownBestPath() (*Path, BestPathReason, error) { } return dest.knownPathList[0], BPR_ONLY_PATH, nil } - sort.Sort(dest.knownPathList) + dest.sort() newBest := dest.knownPathList[0] // If the first path has the invalidated next-hop, which evaluated by IGP, // returns no path with the reason of the next-hop reachability. @@ -531,123 +431,197 @@ func (dest *Destination) computeKnownBestPath() (*Path, BestPathReason, error) { return newBest, newBest.reason, nil } -type paths []*Path +func (dst *Destination) sort() { + sort.SliceStable(dst.knownPathList, func(i, j int) bool { + //Compares given paths and returns best path. + // + //Parameters: + // -`path1`: first path to compare + // -`path2`: second path to compare + // + // Best path processing will involve following steps: + // 1. Select a path with a reachable next hop. + // 2. Select the path with the highest weight. + // 3. If path weights are the same, select the path with the highest + // local preference value. + // 4. Prefer locally originated routes (network routes, redistributed + // routes, or aggregated routes) over received routes. + // 5. Select the route with the shortest AS-path length. + // 6. If all paths have the same AS-path length, select the path based + // on origin: IGP is preferred over EGP; EGP is preferred over + // Incomplete. + // 7. If the origins are the same, select the path with lowest MED + // value. + // 8. If the paths have the same MED values, select the path learned + // via EBGP over one learned via IBGP. + // 9. Select the route with the lowest IGP cost to the next hop. + // 10. Select the route received from the peer with the lowest BGP + // router ID. + // + // Returns None if best-path among given paths cannot be computed else best + // path. + // Assumes paths from NC has source equal to None. + // + + path1 := dst.knownPathList[i] + path2 := dst.knownPathList[j] + + var better *Path + reason := BPR_UNKNOWN + + // draft-uttaro-idr-bgp-persistence-02 + if better == nil { + better = compareByLLGRStaleCommunity(path1, path2) + reason = BPR_NON_LLGR_STALE + } + // Follow best path calculation algorithm steps. + // compare by reachability + if better == nil { + better = compareByReachableNexthop(path1, path2) + reason = BPR_REACHABLE_NEXT_HOP + } + if better == nil { + better = compareByHighestWeight(path1, path2) + reason = BPR_HIGHEST_WEIGHT + } + if better == nil { + better = compareByLocalPref(path1, path2) + reason = BPR_LOCAL_PREF + } + if better == nil { + better = compareByLocalOrigin(path1, path2) + reason = BPR_LOCAL_ORIGIN + } + if better == nil { + better = compareByASPath(path1, path2) + reason = BPR_ASPATH + } + if better == nil { + better = compareByOrigin(path1, path2) + reason = BPR_ORIGIN + } + if better == nil { + better = compareByMED(path1, path2) + reason = BPR_MED + } + if better == nil { + better = compareByASNumber(path1, path2) + reason = BPR_ASN + } + if better == nil { + better = compareByIGPCost(path1, path2) + reason = BPR_IGP_COST + } + if better == nil { + better = compareByAge(path1, path2) + reason = BPR_OLDER + } + if better == nil { + var e error = nil + better, e = compareByRouterID(path1, path2) + if e != nil { + log.WithFields(log.Fields{ + "Topic": "Table", + "Error": e, + }).Error("Could not get best path by comparing router ID") + } + reason = BPR_ROUTER_ID + } + if better == nil { + reason = BPR_UNKNOWN + better = path1 + } -func (p paths) Len() int { - return len(p) -} + better.reason = reason -func (p paths) Swap(i, j int) { - p[i], p[j] = p[j], p[i] + if better == path1 { + return true + } + return false + }) } -func (p paths) Less(i, j int) bool { - - //Compares given paths and returns best path. - // - //Parameters: - // -`path1`: first path to compare - // -`path2`: second path to compare - // - // Best path processing will involve following steps: - // 1. Select a path with a reachable next hop. - // 2. Select the path with the highest weight. - // 3. If path weights are the same, select the path with the highest - // local preference value. - // 4. Prefer locally originated routes (network routes, redistributed - // routes, or aggregated routes) over received routes. - // 5. Select the route with the shortest AS-path length. - // 6. If all paths have the same AS-path length, select the path based - // on origin: IGP is preferred over EGP; EGP is preferred over - // Incomplete. - // 7. If the origins are the same, select the path with lowest MED - // value. - // 8. If the paths have the same MED values, select the path learned - // via EBGP over one learned via IBGP. - // 9. Select the route with the lowest IGP cost to the next hop. - // 10. Select the route received from the peer with the lowest BGP - // router ID. - // - // Returns None if best-path among given paths cannot be computed else best - // path. - // Assumes paths from NC has source equal to None. - // - - path1 := p[i] - path2 := p[j] - - var better *Path - reason := BPR_UNKNOWN +type Update struct { + KnownPathList []*Path + OldKnownPathList []*Path +} - // draft-uttaro-idr-bgp-persistence-02 - if better == nil { - better = compareByLLGRStaleCommunity(path1, path2) - reason = BPR_NON_LLGR_STALE - } - // Follow best path calculation algorithm steps. - // compare by reachability - if better == nil { - better = compareByReachableNexthop(path1, path2) - reason = BPR_REACHABLE_NEXT_HOP - } - if better == nil { - better = compareByHighestWeight(path1, path2) - reason = BPR_HIGHEST_WEIGHT - } - if better == nil { - better = compareByLocalPref(path1, path2) - reason = BPR_LOCAL_PREF - } - if better == nil { - better = compareByLocalOrigin(path1, path2) - reason = BPR_LOCAL_ORIGIN - } - if better == nil { - better = compareByASPath(path1, path2) - reason = BPR_ASPATH - } - if better == nil { - better = compareByOrigin(path1, path2) - reason = BPR_ORIGIN - } - if better == nil { - better = compareByMED(path1, path2) - reason = BPR_MED - } - if better == nil { - better = compareByASNumber(path1, path2) - reason = BPR_ASN - } - if better == nil { - better = compareByIGPCost(path1, path2) - reason = BPR_IGP_COST - } - if better == nil { - better = compareByAge(path1, path2) - reason = BPR_OLDER - } - if better == nil { - var e error = nil - better, e = compareByRouterID(path1, path2) - if e != nil { - log.WithFields(log.Fields{ - "Topic": "Table", - "Error": e, - }).Error("Could not get best path by comparing router ID") +func getMultiBestPath(id string, pathList []*Path) []*Path { + list := make([]*Path, 0, len(pathList)) + var best *Path + for _, p := range pathList { + if !p.IsNexthopInvalid { + if best == nil { + best = p + list = append(list, p) + } else if best.Compare(p) == 0 { + list = append(list, p) + } } - reason = BPR_ROUTER_ID - } - if better == nil { - reason = BPR_UNKNOWN - better = path1 } + return list +} - better.reason = reason +func (u *Update) GetChanges(id string, as uint32, peerDown bool) (*Path, *Path, []*Path) { + best, old := func(id string) (*Path, *Path) { + old := getBestPath(id, as, u.OldKnownPathList) + best := getBestPath(id, as, u.KnownPathList) + if best != nil && best.Equal(old) { + // RFC4684 3.2. Intra-AS VPN Route Distribution + // When processing RT membership NLRIs received from internal iBGP + // peers, it is necessary to consider all available iBGP paths for a + // given RT prefix, for building the outbound route filter, and not just + // the best path. + if best.GetRouteFamily() == bgp.RF_RTC_UC { + return best, old + } + // For BGP Nexthop Tracking, checks if the nexthop reachability + // was changed or not. + if best.IsNexthopInvalid != old.IsNexthopInvalid { + return best, old + } + return nil, old + } + if best == nil { + if old == nil { + return nil, nil + } + if peerDown { + // withdraws were generated by peer + // down so paths are not in knowpath + // or adjin. + old.IsWithdraw = true + return old, old + } + return old.Clone(true), old + } + return best, old + }(id) - if better == path1 { - return true + var multi []*Path + + if id == GLOBAL_RIB_NAME && UseMultiplePaths.Enabled { + diff := func(lhs, rhs []*Path) bool { + if len(lhs) != len(rhs) { + return true + } + for idx, l := range lhs { + if !l.Equal(rhs[idx]) { + return true + } + } + return false + } + oldM := getMultiBestPath(id, u.OldKnownPathList) + newM := getMultiBestPath(id, u.KnownPathList) + if diff(oldM, newM) { + multi = newM + if len(newM) == 0 { + multi = []*Path{best} + } + } } - return false + return best, old, multi } func compareByLLGRStaleCommunity(path1, path2 *Path) *Path { diff --git a/table/table_manager.go b/table/table_manager.go index e1accda7..29f36a23 100644 --- a/table/table_manager.go +++ b/table/table_manager.go @@ -180,15 +180,15 @@ func (manager *TableManager) DeleteVrf(name string) ([]*Path, error) { return msgs, nil } -func (tm *TableManager) update(newPath *Path) *Destination { +func (tm *TableManager) update(newPath *Path) *Update { t := tm.Tables[newPath.GetRouteFamily()] t.validatePath(newPath) dst := t.getOrCreateDest(newPath.GetNlri()) - d := dst.Calculate(newPath) + u := dst.Calculate(newPath) if len(dst.knownPathList) == 0 { t.deleteDest(dst) } - return d + return u } func (manager *TableManager) GetPathListByPeer(info *PeerInfo, rf bgp.RouteFamily) []*Path { @@ -206,24 +206,24 @@ func (manager *TableManager) GetPathListByPeer(info *PeerInfo, rf bgp.RouteFamil return nil } -func (manager *TableManager) Update(newPath *Path) []*Destination { +func (manager *TableManager) Update(newPath *Path) []*Update { if newPath == nil || newPath.IsEOR() { return nil } - // normally, we'll have one destination. - dsts := make([]*Destination, 0, 1) + // Except for a special case with EVPN, we'll have one destination. + updates := make([]*Update, 0, 1) family := newPath.GetRouteFamily() if _, ok := manager.Tables[family]; ok { - dsts = append(dsts, manager.update(newPath)) + updates = append(updates, manager.update(newPath)) if family == bgp.RF_EVPN { for _, p := range manager.handleMacMobility(newPath) { - dsts = append(dsts, manager.update(p)) + updates = append(updates, manager.update(p)) } } } - return dsts + return updates } // EVPN MAC MOBILITY HANDLING diff --git a/table/table_manager_test.go b/table/table_manager_test.go index 3c07dd53..53e226f8 100644 --- a/table/table_manager_test.go +++ b/table/table_manager_test.go @@ -31,7 +31,7 @@ import ( // this function processes only BGPUpdate func (manager *TableManager) ProcessUpdate(fromPeer *PeerInfo, message *bgp.BGPMessage) ([]*Path, error) { pathList := make([]*Path, 0) - dsts := make([]*Destination, 0) + dsts := make([]*Update, 0) for _, path := range ProcessMessage(message, fromPeer, time.Now()) { dsts = append(dsts, manager.Update(path)...) } |