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 <ishida.wataru@lab.ntt.co.jp>

7 files changed, 189 insertions, 15 deletions

diff --git a/server/server.go b/server/server.go
index 4d5ebf43..539c4086 100644
--- a/server/server.go
+++ b/server/server.go
@@ -401,10 +401,10 @@ func (server *BgpServer) dropPeerAllRoutes(peer *Peer, families []bgp.RouteFamil
 		ids = append(ids, table.GLOBAL_RIB_NAME)
 	}
 	for _, rf := range families {
-		best, _ := server.globalRib.DeletePathsByPeer(ids, peer.fsm.peerInfo, rf)
+		best, _, multipath := server.globalRib.DeletePathsByPeer(ids, peer.fsm.peerInfo, rf)
 
 		if !peer.isRouteServerClient() {
-			server.watchers.notify(WATCHER_EVENT_BESTPATH_CHANGE, &watcherEventBestPathMsg{pathList: best[table.GLOBAL_RIB_NAME]})
+			server.watchers.notify(WATCHER_EVENT_BESTPATH_CHANGE, &watcherEventBestPathMsg{pathList: best[table.GLOBAL_RIB_NAME], multiPathList: multipath})
 		}
 
 		for _, targetPeer := range server.neighborMap {
@@ -498,7 +498,7 @@ func (server *BgpServer) propagateUpdate(peer *Peer, pathList []*table.Path) ([]
 				ids = append(ids, targetPeer.TableID())
 			}
 		}
-		best, withdrawn = rib.ProcessPaths(ids, append(pathList, moded...))
+		best, withdrawn, _ = rib.ProcessPaths(ids, append(pathList, moded...))
 	} else {
 		for idx, path := range pathList {
 			path = server.policy.ApplyPolicy(table.GLOBAL_RIB_NAME, table.POLICY_DIRECTION_IMPORT, path, nil)
@@ -549,11 +549,12 @@ func (server *BgpServer) propagateUpdate(peer *Peer, pathList []*table.Path) ([]
 			}
 		}
 		alteredPathList = pathList
-		best, withdrawn = rib.ProcessPaths([]string{table.GLOBAL_RIB_NAME}, pathList)
+		var multi [][]*table.Path
+		best, withdrawn, multi = rib.ProcessPaths([]string{table.GLOBAL_RIB_NAME}, pathList)
 		if len(best[table.GLOBAL_RIB_NAME]) == 0 {
 			return nil, alteredPathList
 		}
-		server.watchers.notify(WATCHER_EVENT_BESTPATH_CHANGE, &watcherEventBestPathMsg{pathList: best[table.GLOBAL_RIB_NAME]})
+		server.watchers.notify(WATCHER_EVENT_BESTPATH_CHANGE, &watcherEventBestPathMsg{pathList: best[table.GLOBAL_RIB_NAME], multiPathList: multi})
 	}
 
 	for _, targetPeer := range server.neighborMap {
@@ -1538,6 +1539,7 @@ func (server *BgpServer) handleModConfig(grpcReq *GrpcRequest) error {
 	server.bgpConfig.Global = *c
 	// update route selection options
 	table.SelectionOptions = c.RouteSelectionOptions.Config
+	table.UseMultiplePaths = c.UseMultiplePaths.Config
 	return nil
 }
 
diff --git a/server/watcher.go b/server/watcher.go
index 4b4b700c..87039479 100644
--- a/server/watcher.go
+++ b/server/watcher.go
@@ -87,7 +87,8 @@ type watcherEventAdjInMsg struct {
 }
 
 type watcherEventBestPathMsg struct {
-	pathList []*table.Path
+	pathList      []*table.Path
+	multiPathList [][]*table.Path
 }
 
 type watcher interface {
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 {