table: use received time as tie-breaker

older path get preference

can be disabled by
`global.route-selection-options.external-compare-router-id = true`

close #806

Signed-off-by: ISHIDA Wataru <ishida.wataru@lab.ntt.co.jp>

5 files changed, 69 insertions, 3 deletions

diff --git a/server/server.go b/server/server.go
index c774e47e..605d9fe4 100644
--- a/server/server.go
+++ b/server/server.go
@@ -1660,6 +1660,8 @@ func (server *BgpServer) handleModConfig(grpcReq *GrpcRequest) error {
 			return err
 		}
 		server.bgpConfig.Global = *c
+		// update route selection options
+		table.SelectionOptions = c.RouteSelectionOptions.Config
 	case api.Operation_DEL_ALL:
 		for k, _ := range server.neighborMap {
 			_, err := server.handleGrpcModNeighbor(&GrpcRequest{
diff --git a/table/destination.go b/table/destination.go
index 131cb129..0e195f83 100644
--- a/table/destination.go
+++ b/table/destination.go
@@ -27,6 +27,8 @@ import (
 	"sort"
 )
 
+var SelectionOptions config.RouteSelectionOptionsConfig
+
 type BestPathReason string
 
 const (
@@ -42,6 +44,7 @@ const (
 	BPR_ASN                BestPathReason = "ASN"
 	BPR_IGP_COST           BestPathReason = "IGP Cost"
 	BPR_ROUTER_ID          BestPathReason = "Router ID"
+	BPR_OLDER              BestPathReason = "Older"
 )
 
 func IpToRadixkey(b []byte, max uint8) string {
@@ -485,6 +488,10 @@ func (p paths) Less(i, j int) bool {
 		reason = BPR_IGP_COST
 	}
 	if better == nil {
+		better = compareByAge(path1, path2)
+		reason = BPR_OLDER
+	}
+	if better == nil {
 		var e error = nil
 		better, e = compareByRouterID(path1, path2)
 		if e != nil {
@@ -720,11 +727,11 @@ func compareByRouterID(path1, path2 *Path) (*Path, error) {
 
 	// If both paths are from eBGP peers, then according to RFC we need
 	// not tie break using router id.
-	if !path1.IsIBGP() && !path2.IsIBGP() {
+	if !SelectionOptions.ExternalCompareRouterId && !path1.IsIBGP() && !path2.IsIBGP() {
 		return nil, nil
 	}
 
-	if path1.IsIBGP() != path2.IsIBGP() {
+	if !SelectionOptions.ExternalCompareRouterId && path1.IsIBGP() != path2.IsIBGP() {
 		return nil, fmt.Errorf("This method does not support comparing ebgp with ibgp path")
 	}
 
@@ -743,6 +750,20 @@ func compareByRouterID(path1, path2 *Path) (*Path, error) {
 	}
 }
 
+func compareByAge(path1, path2 *Path) *Path {
+	if !path1.IsIBGP() && !path2.IsIBGP() && !SelectionOptions.ExternalCompareRouterId {
+		age1 := path1.info.timestamp.UnixNano()
+		age2 := path2.info.timestamp.UnixNano()
+		if age1 == age2 {
+			return nil
+		} else if age1 < age2 {
+			return path1
+		}
+		return path2
+	}
+	return nil
+}
+
 func (dest *Destination) String() string {
 	return fmt.Sprintf("Destination NLRI: %s", dest.nlri.String())
 }
diff --git a/table/destination_test.go b/table/destination_test.go
index 32316f5f..c0666e21 100644
--- a/table/destination_test.go
+++ b/table/destination_test.go
@@ -217,6 +217,42 @@ func TestImplicitWithdrawCalculate(t *testing.T) {
 	assert.Equal(t, len(d.knownPathList), 1)
 }
 
+func TestTimeTieBreaker(t *testing.T) {
+	origin := bgp.NewPathAttributeOrigin(0)
+	aspathParam := []bgp.AsPathParamInterface{bgp.NewAs4PathParam(2, []uint32{65001})}
+	aspath := bgp.NewPathAttributeAsPath(aspathParam)
+	nexthop := bgp.NewPathAttributeNextHop("10.0.0.1")
+	med := bgp.NewPathAttributeMultiExitDisc(0)
+	pathAttributes := []bgp.PathAttributeInterface{origin, aspath, nexthop, med}
+	nlri := bgp.NewIPAddrPrefix(24, "10.10.0.0")
+	updateMsg := bgp.NewBGPUpdateMessage(nil, pathAttributes, []*bgp.IPAddrPrefix{nlri})
+	peer1 := &PeerInfo{AS: 2, LocalAS: 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, LocalAS: 1, Address: net.IP{2, 2, 2, 2}, ID: net.IP{2, 2, 2, 2}} // weaker router-id
+	path2 := ProcessMessage(updateMsg, peer2, time.Now().Add(-1*time.Hour))[0]                 // older than path1
+
+	d := NewDestination(nlri)
+	d.addNewPath(path1)
+	d.addNewPath(path2)
+
+	d.Calculate(nil)
+
+	assert.Equal(t, len(d.knownPathList), 2)
+	assert.Equal(t, true, d.GetBestPath("").GetSource().ID.Equal(net.IP{2, 2, 2, 2})) // path from peer2 win
+
+	// this option disables tie breaking by age
+	SelectionOptions.ExternalCompareRouterId = true
+	d = NewDestination(nlri)
+	d.addNewPath(path1)
+	d.addNewPath(path2)
+
+	d.Calculate(nil)
+
+	assert.Equal(t, len(d.knownPathList), 2)
+	assert.Equal(t, true, d.GetBestPath("").GetSource().ID.Equal(net.IP{1, 1, 1, 1})) // path from peer1 win
+}
+
 func DestCreatePeer() []*PeerInfo {
 	peerD1 := &PeerInfo{AS: 65000}
 	peerD2 := &PeerInfo{AS: 65001}
diff --git a/table/table_manager_test.go b/table/table_manager_test.go
index 21d70d84..8b072c44 100644
--- a/table/table_manager_test.go
+++ b/table/table_manager_test.go
@@ -1115,6 +1115,7 @@ func TestProcessBGPUpdate_6_select_ebgp_path_ipv6(t *testing.T) {
 func TestProcessBGPUpdate_7_select_low_routerid_path_ipv4(t *testing.T) {
 
 	tm := NewTableManager([]bgp.RouteFamily{bgp.RF_IPv4_UC}, 0, 0)
+	SelectionOptions.ExternalCompareRouterId = true
 
 	// low origin message
 	origin1 := bgp.NewPathAttributeOrigin(0)
diff --git a/test/lib/gobgp.py b/test/lib/gobgp.py
index 0b352fa5..b123369e 100644
--- a/test/lib/gobgp.py
+++ b/test/lib/gobgp.py
@@ -201,7 +201,13 @@ class GoBGPContainer(BGPContainer):
             self._create_config_zebra()
 
     def _create_config_bgp(self):
-        config = {'global': {'config': {'as': self.asn, 'router-id': self.router_id}}}
+        config = {'global': {'config': {'as': self.asn, 'router-id': self.router_id},
+                'route-selection-options':{
+                    'config': {
+                        'external-compare-router-id': True,
+                    },
+                },
+        }}
         for peer, info in self.peers.iteritems():
             afi_safi_list = []
             version = netaddr.IPNetwork(info['neigh_addr']).version