table: increase the possibiliby of many NLRIs in one update message

Without hurting the performance (the latency) much, GetBestPathList()
tries to sort Paths in the order that many routes could be packed into
one update message.

I did an experiment that the full routes are pushed to gobgpd (via
mrt), then another peer connects to gobgpd.

Without this patch, gobgpd sends 550,958 update messages to another
peer.

With this patch, gobgpd sends 250,606 update messages.

Signed-off-by: FUJITA Tomonori <fujita.tomonori@lab.ntt.co.jp>

1 files changed, 33 insertions, 3 deletions

diff --git a/table/table_manager.go b/table/table_manager.go
index 75b68b03..6943101c 100644
--- a/table/table_manager.go
+++ b/table/table_manager.go
@@ -22,6 +22,7 @@ import (
 	"github.com/osrg/gobgp/packet"
 	"net"
 	"reflect"
+	"sort"
 	"time"
 )
 
@@ -356,16 +357,45 @@ func (manager *TableManager) GetPathList(rf bgp.RouteFamily) []*Path {
 	return paths
 }
 
+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 (p paths) Less(i, j int) bool {
+	l0 := len(p[i].GetPathAttrs())
+	l1 := len(p[j].GetPathAttrs())
+	if l0 < l1 {
+		return true
+	}
+	if l0 == l1 {
+		return p[i].GetAsPathLen() < p[j].GetAsPathLen()
+	}
+	return false
+}
+
 func (manager *TableManager) GetBestPathList(rf bgp.RouteFamily) []*Path {
 	if _, ok := manager.Tables[rf]; !ok {
 		return []*Path{}
 	}
 	destinations := manager.Tables[rf].GetDestinations()
-	paths := make([]*Path, 0, len(destinations))
+	plist := make([]*Path, 0, len(destinations))
+	pathsByPeer := make(map[uint32]paths)
 	for _, dest := range destinations {
-		paths = append(paths, dest.GetBestPath())
+		path := dest.GetBestPath()
+		key := path.GetSourceAs()
+		pathsByPeer[key] = append(pathsByPeer[key], path)
 	}
-	return paths
+	for _, v := range pathsByPeer {
+		sort.Sort(v)
+		plist = append(plist, v...)
+	}
+	return plist
 }
 
 // process BGPUpdate message