From 5c7df672664f06a8bcdf411667e1c61000805c8c Mon Sep 17 00:00:00 2001 From: ISHIDA Wataru Date: Thu, 2 Jun 2016 05:48:06 +0000 Subject: server/table: support bgp multipath This patch adds multiPathList field to watcherEventBestPathMsg and fills it when global.use-multiple-paths.config.enable = true Following patches add support injecting multipath to zebra and monitoring it via gRPC Signed-off-by: ISHIDA Wataru --- table/destination.go | 43 +++++++++++++++++++++- table/destination_test.go | 89 +++++++++++++++++++++++++++++++++++++++++++++ table/path.go | 36 ++++++++++++++++++ table/table_manager.go | 19 +++++++--- table/table_manager_test.go | 2 +- 5 files changed, 180 insertions(+), 9 deletions(-) (limited to 'table') diff --git a/table/destination.go b/table/destination.go index 8b80f29b..f6de40d1 100644 --- a/table/destination.go +++ b/table/destination.go @@ -28,6 +28,7 @@ import ( ) var SelectionOptions config.RouteSelectionOptionsConfig +var UseMultiplePaths config.UseMultiplePathsConfig type BestPathReason string @@ -230,7 +231,7 @@ 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(ids []string) (map[string]*Path, []*Path) { +func (dest *Destination) Calculate(ids []string) (map[string]*Path, []*Path, []*Path) { best := make(map[string]*Path, len(ids)) oldKnownPathList := dest.knownPathList // First remove the withdrawn paths. @@ -274,10 +275,48 @@ func (dest *Destination) Calculate(ids []string) (map[string]*Path, []*Path) { return best } + var multi []*Path for _, id := range ids { best[id] = f(id) + if id == GLOBAL_RIB_NAME && UseMultiplePaths.Enabled { + multipath := func(paths []*Path) []*Path { + mp := make([]*Path, 0, len(paths)) + var best *Path + for _, path := range paths { + if path.Filtered(id) == POLICY_DIRECTION_NONE { + if best == nil { + best = path + mp = append(mp, path) + } else if best.Compare(path) == 0 { + mp = append(mp, path) + } + } + } + return mp + } + 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 := multipath(oldKnownPathList) + newM := multipath(dest.knownPathList) + if diff(oldM, newM) { + multi = newM + if len(newM) == 0 { + multi = []*Path{best[id]} + } + } + } } - return best, withdrawnList + + return best, withdrawnList, multi } // Removes withdrawn paths. diff --git a/table/destination_test.go b/table/destination_test.go index 23458906..532cb5b1 100644 --- a/table/destination_test.go +++ b/table/destination_test.go @@ -400,3 +400,92 @@ func TestRadixkey(t *testing.T) { assert.Equal(t, "000010100000001100100000", IpToRadixkey(net.ParseIP("10.3.32.0").To4(), 24)) assert.Equal(t, "000010100000001100100000", IpToRadixkey(net.ParseIP("10.3.32.0").To4(), 24)) } + +func TestMultipath(t *testing.T) { + UseMultiplePaths.Enabled = true + origin := bgp.NewPathAttributeOrigin(0) + aspathParam := []bgp.AsPathParamInterface{bgp.NewAs4PathParam(2, []uint32{65000})} + aspath := bgp.NewPathAttributeAsPath(aspathParam) + nexthop := bgp.NewPathAttributeNextHop("192.168.150.1") + med := bgp.NewPathAttributeMultiExitDisc(100) + + pathAttributes := []bgp.PathAttributeInterface{ + origin, + aspath, + nexthop, + med, + } + + nlri := []*bgp.IPAddrPrefix{bgp.NewIPAddrPrefix(24, "10.10.10.0")} + updateMsg := bgp.NewBGPUpdateMessage(nil, pathAttributes, nlri) + peer1 := &PeerInfo{AS: 1, Address: net.IP{1, 1, 1, 1}, ID: net.IP{1, 1, 1, 1}} + path1 := ProcessMessage(updateMsg, peer1, time.Now())[0] + peer2 := &PeerInfo{AS: 2, Address: net.IP{2, 2, 2, 2}, ID: net.IP{2, 2, 2, 2}} + + med = bgp.NewPathAttributeMultiExitDisc(100) + nexthop = bgp.NewPathAttributeNextHop("192.168.150.2") + pathAttributes = []bgp.PathAttributeInterface{ + origin, + aspath, + nexthop, + med, + } + updateMsg = bgp.NewBGPUpdateMessage(nil, pathAttributes, nlri) + path2 := ProcessMessage(updateMsg, peer2, time.Now())[0] + + d := NewDestination(nlri[0]) + d.addNewPath(path1) + d.addNewPath(path2) + + best, w, multi := d.Calculate([]string{GLOBAL_RIB_NAME}) + assert.Equal(t, len(best), 1) + assert.Equal(t, len(w), 0) + assert.Equal(t, len(multi), 2) + assert.Equal(t, len(d.GetKnownPathList(GLOBAL_RIB_NAME)), 2) + + path3 := path2.Clone(true) + d.addWithdraw(path3) + best, w, multi = d.Calculate([]string{GLOBAL_RIB_NAME}) + assert.Equal(t, len(best), 1) + assert.Equal(t, len(w), 1) + assert.Equal(t, len(multi), 1) + assert.Equal(t, len(d.GetKnownPathList(GLOBAL_RIB_NAME)), 1) + + peer3 := &PeerInfo{AS: 3, Address: net.IP{3, 3, 3, 3}, ID: net.IP{3, 3, 3, 3}} + med = bgp.NewPathAttributeMultiExitDisc(50) + nexthop = bgp.NewPathAttributeNextHop("192.168.150.3") + pathAttributes = []bgp.PathAttributeInterface{ + origin, + aspath, + nexthop, + med, + } + updateMsg = bgp.NewBGPUpdateMessage(nil, pathAttributes, nlri) + path4 := ProcessMessage(updateMsg, peer3, time.Now())[0] + d.addNewPath(path4) + + best, w, multi = d.Calculate([]string{GLOBAL_RIB_NAME}) + assert.Equal(t, len(best), 1) + assert.Equal(t, len(w), 0) + assert.Equal(t, len(multi), 1) + assert.Equal(t, len(d.GetKnownPathList(GLOBAL_RIB_NAME)), 2) + + nexthop = bgp.NewPathAttributeNextHop("192.168.150.2") + pathAttributes = []bgp.PathAttributeInterface{ + origin, + aspath, + nexthop, + med, + } + updateMsg = bgp.NewBGPUpdateMessage(nil, pathAttributes, nlri) + path5 := ProcessMessage(updateMsg, peer2, time.Now())[0] + d.addNewPath(path5) + + best, w, multi = d.Calculate([]string{GLOBAL_RIB_NAME}) + assert.Equal(t, len(best), 1) + assert.Equal(t, len(w), 0) + assert.Equal(t, len(multi), 2) + assert.Equal(t, len(d.GetKnownPathList(GLOBAL_RIB_NAME)), 3) + + UseMultiplePaths.Enabled = false +} diff --git a/table/path.go b/table/path.go index 4a0d9031..d4946e8d 100644 --- a/table/path.go +++ b/table/path.go @@ -866,3 +866,39 @@ func (lhs *Path) Equal(rhs *Path) bool { } return bytes.Equal(pattrs(lhs.GetPathAttrs()), pattrs(rhs.GetPathAttrs())) } + +func (lhs *Path) Compare(rhs *Path) int { + if lhs.IsLocal() && !rhs.IsLocal() { + return 1 + } else if !lhs.IsLocal() && rhs.IsLocal() { + return -1 + } + + if !lhs.IsIBGP() && rhs.IsIBGP() { + return 1 + } else if lhs.IsIBGP() && !rhs.IsIBGP() { + return -1 + } + + lp1, _ := lhs.GetLocalPref() + lp2, _ := rhs.GetLocalPref() + if lp1 != lp2 { + return int(lp1 - lp2) + } + + l1 := lhs.GetAsPathLen() + l2 := rhs.GetAsPathLen() + if l1 != l2 { + return int(l2 - l1) + } + + o1, _ := lhs.GetOrigin() + o2, _ := rhs.GetOrigin() + if o1 != o2 { + return int(o2 - o1) + } + + m1, _ := lhs.GetMed() + m2, _ := rhs.GetMed() + return int(m2 - m1) +} diff --git a/table/table_manager.go b/table/table_manager.go index cc9784b9..f6bebbf7 100644 --- a/table/table_manager.go +++ b/table/table_manager.go @@ -216,22 +216,29 @@ func (manager *TableManager) DeleteVrf(name string) ([]*Path, error) { return msgs, nil } -func (manager *TableManager) calculate(ids []string, destinations []*Destination) (map[string][]*Path, []*Path) { +func (manager *TableManager) calculate(ids []string, destinations []*Destination) (map[string][]*Path, []*Path, [][]*Path) { withdrawn := make([]*Path, 0, len(destinations)) best := make(map[string][]*Path, len(ids)) emptyDsts := make([]*Destination, 0, len(destinations)) + var multi [][]*Path + if UseMultiplePaths.Enabled && len(ids) == 1 && ids[0] == GLOBAL_RIB_NAME { + multi = make([][]*Path, 0, len(destinations)) + } for _, dst := range destinations { log.WithFields(log.Fields{ "Topic": "table", "Key": dst.GetNlri().String(), }).Debug("Processing destination") - paths, w := dst.Calculate(ids) + paths, w, m := dst.Calculate(ids) for id, path := range paths { best[id] = append(best[id], path) } withdrawn = append(withdrawn, w...) + if m != nil { + multi = append(multi, m) + } if len(dst.knownPathList) == 0 { emptyDsts = append(emptyDsts, dst) @@ -242,18 +249,18 @@ func (manager *TableManager) calculate(ids []string, destinations []*Destination t := manager.Tables[dst.Family()] t.deleteDest(dst) } - return best, withdrawn + return best, withdrawn, multi } -func (manager *TableManager) DeletePathsByPeer(ids []string, info *PeerInfo, rf bgp.RouteFamily) (map[string][]*Path, []*Path) { +func (manager *TableManager) DeletePathsByPeer(ids []string, info *PeerInfo, rf bgp.RouteFamily) (map[string][]*Path, []*Path, [][]*Path) { if t, ok := manager.Tables[rf]; ok { dsts := t.DeleteDestByPeer(info) return manager.calculate(ids, dsts) } - return nil, nil + return nil, nil, nil } -func (manager *TableManager) ProcessPaths(ids []string, pathList []*Path) (map[string][]*Path, []*Path) { +func (manager *TableManager) ProcessPaths(ids []string, pathList []*Path) (map[string][]*Path, []*Path, [][]*Path) { m := make(map[string]bool, len(pathList)) dsts := make([]*Destination, 0, len(pathList)) for _, path := range pathList { diff --git a/table/table_manager_test.go b/table/table_manager_test.go index 193890f3..f86bfd05 100644 --- a/table/table_manager_test.go +++ b/table/table_manager_test.go @@ -30,7 +30,7 @@ import ( // this function processes only BGPUpdate func (manager *TableManager) ProcessUpdate(fromPeer *PeerInfo, message *bgp.BGPMessage) ([]*Path, error) { paths := ProcessMessage(message, fromPeer, time.Now()) - best, _ := manager.ProcessPaths([]string{GLOBAL_RIB_NAME}, paths) + best, _, _ := manager.ProcessPaths([]string{GLOBAL_RIB_NAME}, paths) paths2 := make([]*Path, 0, len(paths)) for _, p := range best[GLOBAL_RIB_NAME] { if p != nil { -- cgit v1.2.3