diff options
Diffstat (limited to 'table/destination.go')
| -rw-r--r-- | table/destination.go | 346 |
1 files changed, 144 insertions, 202 deletions
diff --git a/table/destination.go b/table/destination.go index c2794a6a..8d020df5 100644 --- a/table/destination.go +++ b/table/destination.go @@ -25,21 +25,24 @@ import ( "github.com/osrg/gobgp/config" "github.com/osrg/gobgp/packet" "net" + "sort" ) +type BestPathReason string + const ( - BPR_UNKNOWN = "Unknown" - BPR_ONLY_PATH = "Only Path" - BPR_REACHABLE_NEXT_HOP = "Reachable Next Hop" - BPR_HIGHEST_WEIGHT = "Highest Weight" - BPR_LOCAL_PREF = "Local Pref" - BPR_LOCAL_ORIGIN = "Local Origin" - BPR_ASPATH = "AS Path" - BPR_ORIGIN = "Origin" - BPR_MED = "MED" - BPR_ASN = "ASN" - BPR_IGP_COST = "IGP Cost" - BPR_ROUTER_ID = "Router ID" + BPR_UNKNOWN BestPathReason = "Unknown" + BPR_ONLY_PATH BestPathReason = "Only Path" + BPR_REACHABLE_NEXT_HOP BestPathReason = "Reachable Next Hop" + BPR_HIGHEST_WEIGHT BestPathReason = "Highest Weight" + BPR_LOCAL_PREF BestPathReason = "Local Pref" + BPR_LOCAL_ORIGIN BestPathReason = "Local Origin" + BPR_ASPATH BestPathReason = "AS Path" + BPR_ORIGIN BestPathReason = "Origin" + BPR_MED BestPathReason = "MED" + BPR_ASN BestPathReason = "ASN" + BPR_IGP_COST BestPathReason = "IGP Cost" + BPR_ROUTER_ID BestPathReason = "Router ID" ) func IpToRadixkey(b []byte, max uint8) string { @@ -111,11 +114,11 @@ func NewPeerInfo(g *config.Global, p *config.Neighbor) *PeerInfo { type Destination struct { routeFamily bgp.RouteFamily nlri bgp.AddrPrefixInterface - knownPathList []*Path - withdrawList []*Path - newPathList []*Path + knownPathList paths + withdrawList paths + newPathList paths bestPath *Path - bestPathReason string + bestPathReason BestPathReason RadixKey string } @@ -174,11 +177,11 @@ func (dd *Destination) setNlri(nlri bgp.AddrPrefixInterface) { dd.nlri = nlri } -func (dd *Destination) getBestPathReason() string { +func (dd *Destination) getBestPathReason() BestPathReason { return dd.bestPathReason } -func (dd *Destination) setBestPathReason(reason string) { +func (dd *Destination) setBestPathReason(reason BestPathReason) { dd.bestPathReason = reason } @@ -226,68 +229,33 @@ 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() (*Path, string, error) { +func (dest *Destination) Calculate() (*Path, BestPathReason, error) { // First remove the withdrawn paths. - // Note: If we want to support multiple paths per destination we may - // have to maintain sent-routes per path. - dest.removeWithdrawals() - - // Have to select best-path from available paths and new paths. - // If we do not have any paths, then we no longer have best path. - if len(dest.knownPathList) == 0 && len(dest.newPathList) == 1 { - // If we do not have any old but one new path - // it becomes best path. - dest.knownPathList = append(dest.knownPathList, dest.newPathList[0]) - dest.newPathList, _ = deleteAt(dest.newPathList, 0) - log.WithFields(log.Fields{ - "Topic": "Table", - "Key": dest.GetNlri().String(), - "Path": dest.knownPathList[0], - "Reason": BPR_ONLY_PATH, - }).Debug("best path") - - return dest.knownPathList[0], BPR_ONLY_PATH, nil - } - - // If we have a new version of old/known path we use it and delete old - // one. - dest.removeOldPaths() - log.Debugf("removeOldPaths") + dest.explicitWithdraw() + // Do implicit withdrawal + dest.implicitWithdraw() // Collect all new paths into known paths. dest.knownPathList = append(dest.knownPathList, dest.newPathList...) - // Clear new paths as we copied them. dest.newPathList = make([]*Path, 0) - - // If we do not have any paths to this destination, then we do not have - // new best path. - if len(dest.knownPathList) == 0 { - return nil, BPR_UNKNOWN, nil - } - // Compute new best path - currentBestPath, reason, e := dest.computeKnownBestPath() - if e != nil { - log.Error(e) - } - return currentBestPath, reason, e - + return dest.computeKnownBestPath() } -//"""Removes withdrawn paths. +// Removes withdrawn paths. +// +// Note: +// We may have disproportionate number of withdraws compared to know paths +// since not all paths get installed into the table due to bgp policy and +// we can receive withdraws for such paths and withdrawals may not be +// stopped by the same policies. // -//Note: -//We may have disproportionate number of withdraws compared to know paths -//since not all paths get installed into the table due to bgp policy and -//we can receive withdraws for such paths and withdrawals may not be -//stopped by the same policies. -//""" -func (dest *Destination) removeWithdrawals() { +func (dest *Destination) explicitWithdraw() paths { // If we have no withdrawals, we have nothing to do. if len(dest.withdrawList) == 0 { - return + return nil } log.WithFields(log.Fields{ @@ -304,24 +272,25 @@ func (dest *Destination) removeWithdrawals() { "Key": dest.GetNlri().String(), "Length": len(dest.withdrawList), }).Debug("Found withdrawals for path(s) that did not get installed") - - dest.withdrawList = dest.withdrawList[len(dest.withdrawList):] + dest.withdrawList = []*Path{} + return nil } - // If we have some known paths and some withdrawals, we find matches and - // delete them first. - matches := make(map[string]*Path) - wMatches := make(map[string]*Path) + // If we have some known paths and some withdrawals, we find matches and + // delete them first. + matches := make([]*Path, 0, len(dest.withdrawList)/2) + newKnownPaths := make([]*Path, 0, len(dest.knownPathList)/2) + newWithdrawPaths := make([]*Path, 0, len(dest.withdrawList)/2) + // Match all withdrawals from destination paths. for _, withdraw := range dest.withdrawList { - var isFound bool = false + isFound := false for _, path := range dest.knownPathList { // We have a match if the source are same. - // TODO add GetSource to Path interface if path.GetSource().Equal(withdraw.GetSource()) { isFound = true - matches[path.String()] = path - wMatches[withdraw.String()] = withdraw + path.IsWithdraw = true + matches = append(matches, path) // One withdraw can remove only one path. break } @@ -334,11 +303,12 @@ func (dest *Destination) removeWithdrawals() { "Key": dest.GetNlri().String(), "Path": withdraw, }).Debug("No matching path for withdraw found, may be path was not installed into table") + newWithdrawPaths = append(newWithdrawPaths, withdraw) } } // If we have partial match. - if len(matches) != len(dest.withdrawList) { + if len(newWithdrawPaths) > 0 { log.WithFields(log.Fields{ "Topic": "Table", "Key": dest.GetNlri().String(), @@ -347,125 +317,90 @@ func (dest *Destination) removeWithdrawals() { }).Debug("Did not find match for some withdrawals.") } - // Clear matching paths and withdrawals. - for _, path := range matches { - var result bool = false - dest.knownPathList, result = removeWithPath(dest.knownPathList, path) - if !result { - log.WithFields(log.Fields{ - "Topic": "Table", - "Key": dest.GetNlri().String(), - "Path": path, - }).Debug("could not remove path from knownPathList") - } - } - for _, path := range wMatches { - var result bool = false - dest.withdrawList, result = removeWithPath(dest.withdrawList, path) - if !result { - log.WithFields(log.Fields{ - "Topic": "Table", - "Key": dest.GetNlri().String(), - "Path": path, - }).Debug("could not remove path from withdrawList") + for _, path := range dest.knownPathList { + if !path.IsWithdraw { + newKnownPaths = append(newKnownPaths, path) } } -} - -func (dest *Destination) computeKnownBestPath() (*Path, string, error) { - - // """Computes the best path among known paths. - // - // Returns current best path among `knownPaths`. - if len(dest.knownPathList) == 0 { - return nil, "", fmt.Errorf("Need at-least one known path to compute best path") - } - - log.Debugf("computeKnownBestPath known pathlist: %d", len(dest.knownPathList)) - // We pick the first path as current best path. This helps in breaking - // tie between two new paths learned in one cycle for which best-path - // calculation steps lead to tie. - currentBestPath := dest.knownPathList[0] - bestPathReason := BPR_ONLY_PATH - for _, nextPath := range dest.knownPathList[1:] { - // Compare next path with current best path. - newBestPath, reason := computeBestPath(currentBestPath, nextPath) - bestPathReason = reason - if newBestPath != nil { - currentBestPath = newBestPath - } - } - return currentBestPath, bestPathReason, nil + dest.knownPathList = newKnownPaths + dest.withdrawList = newWithdrawPaths + return matches } -func (dest *Destination) removeOldPaths() { - // """Identifies which of known paths are old and removes them. - // - // Known paths will no longer have paths whose new version is present in - // new paths. - // """ - +// Identifies which of known paths are old and removes them. +// +// Known paths will no longer have paths whose new version is present in +// new paths. +func (dest *Destination) implicitWithdraw() { newPaths := dest.newPathList knownPaths := dest.knownPathList + newKnownPaths := make([]*Path, 0, len(knownPaths)) for _, newPath := range newPaths { if newPath.NoImplicitWithdraw { continue } - oldPaths := make([]*Path, 0) for _, path := range knownPaths { // Here we just check if source is same and not check if path // version num. as newPaths are implicit withdrawal of old // paths and when doing RouteRefresh (not EnhancedRouteRefresh) // we get same paths again. if newPath.GetSource().Equal(path.GetSource()) { - oldPaths = append(oldPaths, path) - break - } - } - for _, oldPath := range oldPaths { - match := false - knownPaths, match = removeWithPath(knownPaths, oldPath) - if !match { log.WithFields(log.Fields{ "Topic": "Table", "Key": dest.GetNlri().String(), - "Path": oldPath, - }).Debug("not matched") - + "Path": path, + }).Debug("Implicit withdrawal of old path, since we have learned new path from the same peer") + // just use as a flag whether to leave in knownPathList + path.IsWithdraw = true + break } - log.WithFields(log.Fields{ - "Topic": "Table", - "Key": dest.GetNlri().String(), - "Path": oldPath, - }).Debug("Implicit withdrawal of old path, since we have learned new path from the same peer") } } - dest.knownPathList = knownPaths -} -func deleteAt(list []*Path, pos int) ([]*Path, bool) { - if list != nil { - list = append(list[:pos], list[pos+1:]...) - return list, true + for _, path := range dest.knownPathList { + if !path.IsWithdraw { + newKnownPaths = append(newKnownPaths, path) + } + // we've used the flag. flag it down. + path.IsWithdraw = false } - return nil, false + dest.knownPathList = newKnownPaths } -// remove item from slice by object itself -func removeWithPath(list []*Path, path *Path) ([]*Path, bool) { +func (dest *Destination) computeKnownBestPath() (*Path, BestPathReason, error) { - for index, p := range list { - if p == path { - pathList := append(list[:index], list[index+1:]...) - return pathList, true - } + // If we do not have any paths to this destination, then we do not have + // new best path. + if len(dest.knownPathList) == 0 { + return nil, BPR_UNKNOWN, nil } - return list, false + + log.Debugf("computeKnownBestPath known pathlist: %d", len(dest.knownPathList)) + + // We pick the first path as current best path. This helps in breaking + // tie between two new paths learned in one cycle for which best-path + // calculation steps lead to tie. + if len(dest.knownPathList) == 1 { + return dest.knownPathList[0], BPR_ONLY_PATH, nil + } + sort.Sort(dest.knownPathList) + newBest := dest.knownPathList[0] + return newBest, newBest.reason, nil +} + +type paths []*Path + +func (p paths) Len() int { + return len(p) +} + +func (p paths) Swap(i, j int) { + p[i], p[j] = p[j], p[i] } -func computeBestPath(path1, path2 *Path) (*Path, string) { +func (p paths) Less(i, j int) bool { //Compares given paths and returns best path. // @@ -497,62 +432,69 @@ func computeBestPath(path1, path2 *Path) (*Path, string) { // Assumes paths from NC has source equal to None. // - var bestPath *Path - bestPathReason := BPR_UNKNOWN + path1 := p[i] + path2 := p[j] + + var better *Path + reason := BPR_UNKNOWN // Follow best path calculation algorithm steps. // compare by reachability - if bestPath == nil { - bestPath = compareByReachableNexthop(path1, path2) - bestPathReason = BPR_REACHABLE_NEXT_HOP + if better == nil { + better = compareByReachableNexthop(path1, path2) + reason = BPR_REACHABLE_NEXT_HOP } - - if bestPath == nil { - bestPath = compareByHighestWeight(path1, path2) - bestPathReason = BPR_HIGHEST_WEIGHT + if better == nil { + better = compareByHighestWeight(path1, path2) + reason = BPR_HIGHEST_WEIGHT } - - if bestPath == nil { - bestPath = compareByLocalPref(path1, path2) - bestPathReason = BPR_LOCAL_PREF + if better == nil { + better = compareByLocalPref(path1, path2) + reason = BPR_LOCAL_PREF } - if bestPath == nil { - bestPath = compareByLocalOrigin(path1, path2) - bestPathReason = BPR_LOCAL_ORIGIN + if better == nil { + better = compareByLocalOrigin(path1, path2) + reason = BPR_LOCAL_ORIGIN } - if bestPath == nil { - bestPath = compareByASPath(path1, path2) - bestPathReason = BPR_ASPATH + if better == nil { + better = compareByASPath(path1, path2) + reason = BPR_ASPATH } - if bestPath == nil { - bestPath = compareByOrigin(path1, path2) - bestPathReason = BPR_ORIGIN + if better == nil { + better = compareByOrigin(path1, path2) + reason = BPR_ORIGIN } - if bestPath == nil { - bestPath = compareByMED(path1, path2) - bestPathReason = BPR_MED + if better == nil { + better = compareByMED(path1, path2) + reason = BPR_MED } - if bestPath == nil { - bestPath = compareByASNumber(path1, path2) - bestPathReason = BPR_ASN + if better == nil { + better = compareByASNumber(path1, path2) + reason = BPR_ASN } - if bestPath == nil { - bestPath = compareByIGPCost(path1, path2) - bestPathReason = BPR_IGP_COST + if better == nil { + better = compareByIGPCost(path1, path2) + reason = BPR_IGP_COST } - if bestPath == nil { + if better == nil { var e error = nil - bestPath, e = compareByRouterID(path1, path2) + better, e = compareByRouterID(path1, path2) if e != nil { log.Error(e) } - bestPathReason = BPR_ROUTER_ID + reason = BPR_ROUTER_ID } - if bestPath == nil { - bestPathReason = BPR_UNKNOWN + if better == nil { + reason = BPR_UNKNOWN + better = path1 } - return bestPath, bestPathReason + better.reason = reason + + if better.Equal(path1) { + return true + } + return false } func compareByReachableNexthop(path1, path2 *Path) *Path { |