summaryrefslogtreecommitdiffhomepage
path: root/table
diff options
context:
space:
mode:
Diffstat (limited to 'table')
-rw-r--r--table/destination.go346
-rw-r--r--table/destination_test.go4
-rw-r--r--table/path.go1
-rw-r--r--table/table.go4
4 files changed, 148 insertions, 207 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 {
diff --git a/table/destination_test.go b/table/destination_test.go
index 8624bc8d..dce14250 100644
--- a/table/destination_test.go
+++ b/table/destination_test.go
@@ -65,14 +65,14 @@ func TestDestinationGetNlri(t *testing.T) {
}
func TestDestinationSetBestPathReason(t *testing.T) {
dd := &Destination{}
- reason := "reason1"
+ reason := BestPathReason("reason1")
dd.setBestPathReason(reason)
r_reason := dd.getBestPathReason()
assert.Equal(t, r_reason, reason)
}
func TestDestinationGetBestPathReason(t *testing.T) {
dd := &Destination{}
- reason := "reason2"
+ reason := BestPathReason("reason2")
dd.setBestPathReason(reason)
r_reason := dd.getBestPathReason()
assert.Equal(t, r_reason, reason)
diff --git a/table/path.go b/table/path.go
index b2c9bb55..7cfe37b0 100644
--- a/table/path.go
+++ b/table/path.go
@@ -40,6 +40,7 @@ type Path struct {
IsFromZebra bool
Filtered bool
Owner net.IP
+ reason BestPathReason
}
func NewPath(source *PeerInfo, nlri bgp.AddrPrefixInterface, isWithdraw bool, pattrs []bgp.PathAttributeInterface, medSetByTargetNeighbor bool, timestamp time.Time, noImplicitWithdraw bool) *Path {
diff --git a/table/table.go b/table/table.go
index d40ac9c4..cf14d5c1 100644
--- a/table/table.go
+++ b/table/table.go
@@ -37,10 +37,8 @@ func (t *Table) GetRoutefamily() bgp.RouteFamily {
}
func (t *Table) insert(path *Path) *Destination {
- var dest *Destination
-
t.validatePath(path)
- dest = t.getOrCreateDest(path.GetNlri())
+ dest := t.getOrCreateDest(path.GetNlri())
if path.IsWithdraw {
// withdraw insert
generated by cgit v1.2.3 (git 2.39.1) at 2024-11-15 23:43:57 +0000