[VOL-2576] Improve route calculation

This commit changes the way device routes are calculated. It
replaces the device graph method. The graph method relies on the
shortest path calculation which is quite resource intensive. For
instance, generating the routes for a PON network with 1 OLT having
8 PON ports, 64 ONUs per Port and 4 UNIs per ONUs took 96 secs to
generate the 4096 routes.  The new method creates the routes from
the devices data with no middle step.  Generating routes for the
above topology now takes 4ms.

Change-Id: I32bffe06d12ad0fea94002a39f217547dc55cdbf
diff --git a/rw_core/flowdecomposition/flow_decomposer.go b/rw_core/flowdecomposition/flow_decomposer.go
index 5819705..9e996dc 100644
--- a/rw_core/flowdecomposition/flow_decomposer.go
+++ b/rw_core/flowdecomposition/flow_decomposer.go
@@ -20,11 +20,13 @@
 	"context"
 	"github.com/gogo/protobuf/proto"
 	"github.com/opencord/voltha-go/rw_core/coreif"
-	"github.com/opencord/voltha-go/rw_core/graph"
+	"github.com/opencord/voltha-go/rw_core/route"
 	fu "github.com/opencord/voltha-lib-go/v3/pkg/flows"
 	"github.com/opencord/voltha-lib-go/v3/pkg/log"
 	ofp "github.com/opencord/voltha-protos/v3/go/openflow_13"
 	"github.com/opencord/voltha-protos/v3/go/voltha"
+	"google.golang.org/grpc/codes"
+	"google.golang.org/grpc/status"
 )
 
 func init() {
@@ -47,7 +49,7 @@
 }
 
 //DecomposeRules decomposes per-device flows and flow-groups from the flows and groups defined on a logical device
-func (fd *FlowDecomposer) DecomposeRules(ctx context.Context, agent coreif.LogicalDeviceAgent, flows ofp.Flows, groups ofp.FlowGroups) *fu.DeviceRules {
+func (fd *FlowDecomposer) DecomposeRules(ctx context.Context, agent coreif.LogicalDeviceAgent, flows ofp.Flows, groups ofp.FlowGroups) (*fu.DeviceRules, error) {
 	deviceRules := *fu.NewDeviceRules()
 	devicesToUpdate := make(map[string]string)
 
@@ -56,16 +58,18 @@
 		groupMap[groupEntry.Desc.GroupId] = groupEntry
 	}
 
-	var decomposedRules *fu.DeviceRules
 	for _, flow := range flows.Items {
-		decomposedRules = fd.decomposeFlow(ctx, agent, flow, groupMap)
+		decomposedRules, err := fd.decomposeFlow(ctx, agent, flow, groupMap)
+		if err != nil {
+			return nil, err
+		}
 		for deviceID, flowAndGroups := range decomposedRules.Rules {
 			deviceRules.CreateEntryIfNotExist(deviceID)
 			deviceRules.Rules[deviceID].AddFrom(flowAndGroups)
 			devicesToUpdate[deviceID] = deviceID
 		}
 	}
-	return deviceRules.FilterRules(devicesToUpdate)
+	return deviceRules.FilterRules(devicesToUpdate), nil
 }
 
 // Handles special case of any controller-bound flow for a parent device
@@ -106,7 +110,7 @@
 }
 
 //processControllerBoundFlow decomposes trap flows
-func (fd *FlowDecomposer) processControllerBoundFlow(agent coreif.LogicalDeviceAgent, route []graph.RouteHop,
+func (fd *FlowDecomposer) processControllerBoundFlow(ctx context.Context, agent coreif.LogicalDeviceAgent, path []route.Hop,
 	inPortNo uint32, outPortNo uint32, flow *ofp.OfpFlowStats) *fu.DeviceRules {
 
 	log.Debugw("trap-flow", log.Fields{"inPortNo": inPortNo, "outPortNo": outPortNo, "flow": flow})
@@ -114,11 +118,11 @@
 	meterID := fu.GetMeterIdFromFlow(flow)
 	metadataFromwriteMetadata := fu.GetMetadataFromWriteMetadataAction(flow)
 
-	ingressHop := route[0]
-	egressHop := route[1]
+	ingressHop := path[0]
+	egressHop := path[1]
 
 	//case of packet_in from NNI port rule
-	if agent.GetDeviceGraph().IsRootPort(inPortNo) {
+	if agent.GetDeviceRoutes().IsRootPort(inPortNo) {
 		// Trap flow for NNI port
 		log.Debug("trap-nni")
 
@@ -212,8 +216,8 @@
 // upstream needs to get Q-in-Q treatment and that this is expressed via two flow rules, the first using the
 // goto-statement. We also assume that the inner tag is applied at the ONU, while the outer tag is
 // applied at the OLT
-func (fd *FlowDecomposer) processUpstreamNonControllerBoundFlow(agent coreif.LogicalDeviceAgent,
-	route []graph.RouteHop, inPortNo uint32, outPortNo uint32, flow *ofp.OfpFlowStats) *fu.DeviceRules {
+func (fd *FlowDecomposer) processUpstreamNonControllerBoundFlow(ctx context.Context,
+	path []route.Hop, inPortNo uint32, outPortNo uint32, flow *ofp.OfpFlowStats) *fu.DeviceRules {
 
 	log.Debugw("upstream-non-controller-bound-flow", log.Fields{"inPortNo": inPortNo, "outPortNo": outPortNo})
 	deviceRules := fu.NewDeviceRules()
@@ -221,8 +225,8 @@
 	meterID := fu.GetMeterIdFromFlow(flow)
 	metadataFromwriteMetadata := fu.GetMetadataFromWriteMetadataAction(flow)
 
-	ingressHop := route[0]
-	egressHop := route[1]
+	ingressHop := path[0]
+	egressHop := path[1]
 
 	if flow.TableId == 0 && fu.HasNextTable(flow) {
 		log.Debugw("decomposing-onu-flow-in-upstream-has-next-table", log.Fields{"table_id": flow.TableId})
@@ -272,7 +276,7 @@
 }
 
 // processDownstreamFlowWithNextTable decomposes downstream flows containing next table ID instructions
-func (fd *FlowDecomposer) processDownstreamFlowWithNextTable(agent coreif.LogicalDeviceAgent, route []graph.RouteHop,
+func (fd *FlowDecomposer) processDownstreamFlowWithNextTable(ctx context.Context, agent coreif.LogicalDeviceAgent, path []route.Hop,
 	inPortNo uint32, outPortNo uint32, flow *ofp.OfpFlowStats) *fu.DeviceRules {
 	log.Debugw("decomposing-olt-flow-in-downstream-flow-with-next-table", log.Fields{"inPortNo": inPortNo, "outPortNo": outPortNo})
 	deviceRules := fu.NewDeviceRules()
@@ -289,13 +293,17 @@
 		return deviceRules
 	}
 
-	ingressHop := route[0]
-	egressHop := route[1]
+	ingressHop := path[0]
+	egressHop := path[1]
 	if metadataFromwriteMetadata != 0 {
 		log.Debugw("creating-metadata-flow", log.Fields{"flow": flow})
 		portNumber := fu.GetEgressPortNumberFromWriteMetadata(flow)
 		if portNumber != 0 {
-			recalculatedRoute := agent.GetRoute(inPortNo, portNumber)
+			recalculatedRoute, err := agent.GetRoute(ctx, inPortNo, portNumber)
+			if err != nil {
+				log.Errorw("no-route-double-tag", log.Fields{"inPortNo": inPortNo, "outPortNo": outPortNo, "metadata": metadataFromwriteMetadata, "error": err})
+				return deviceRules
+			}
 			switch len(recalculatedRoute) {
 			case 0:
 				log.Errorw("no-route-double-tag", log.Fields{"inPortNo": inPortNo, "outPortNo": portNumber, "comment": "deleting-flow", "metadata": metadataFromwriteMetadata})
@@ -304,7 +312,7 @@
 			case 2:
 				log.Debugw("route-found", log.Fields{"ingressHop": ingressHop, "egressHop": egressHop})
 			default:
-				log.Errorw("invalid-route-length", log.Fields{"routeLen": len(route)})
+				log.Errorw("invalid-route-length", log.Fields{"routeLen": len(path)})
 				return deviceRules
 			}
 			ingressHop = recalculatedRoute[0]
@@ -358,13 +366,13 @@
 }
 
 // processUnicastFlow decomposes unicast flows
-func (fd *FlowDecomposer) processUnicastFlow(agent coreif.LogicalDeviceAgent, route []graph.RouteHop,
+func (fd *FlowDecomposer) processUnicastFlow(ctx context.Context, path []route.Hop,
 	inPortNo uint32, outPortNo uint32, flow *ofp.OfpFlowStats) *fu.DeviceRules {
 
 	log.Debugw("decomposing-onu-flow-in-downstream-unicast-flow", log.Fields{"inPortNo": inPortNo, "outPortNo": outPortNo})
 	deviceRules := fu.NewDeviceRules()
 
-	egressHop := route[1]
+	egressHop := path[1]
 
 	meterID := fu.GetMeterIdFromFlow(flow)
 	metadataFromwriteMetadata := fu.GetMetadataFromWriteMetadataAction(flow)
@@ -389,7 +397,7 @@
 }
 
 // processMulticastFlow decompose multicast flows
-func (fd *FlowDecomposer) processMulticastFlow(agent coreif.LogicalDeviceAgent, route []graph.RouteHop,
+func (fd *FlowDecomposer) processMulticastFlow(ctx context.Context, path []route.Hop,
 	inPortNo uint32, outPortNo uint32, flow *ofp.OfpFlowStats, grpID uint32,
 	groupMap map[uint32]*ofp.OfpGroupEntry) *fu.DeviceRules {
 
@@ -408,71 +416,71 @@
 		return deviceRules
 	}
 
-	deviceRules.CreateEntryIfNotExist(route[0].DeviceID)
+	deviceRules.CreateEntryIfNotExist(path[0].DeviceID)
 	fg := fu.NewFlowsAndGroups()
 	fg.AddFlow(flow)
 	//return the multicast flow without decomposing it
-	deviceRules.AddFlowsAndGroup(route[0].DeviceID, fg)
+	deviceRules.AddFlowsAndGroup(path[0].DeviceID, fg)
 	return deviceRules
 }
 
 // decomposeFlow decomposes a flow for a logical device into flows for each physical device
 func (fd *FlowDecomposer) decomposeFlow(ctx context.Context, agent coreif.LogicalDeviceAgent, flow *ofp.OfpFlowStats,
-	groupMap map[uint32]*ofp.OfpGroupEntry) *fu.DeviceRules {
+	groupMap map[uint32]*ofp.OfpGroupEntry) (*fu.DeviceRules, error) {
 
 	inPortNo := fu.GetInPort(flow)
 	if fu.HasGroup(flow) && inPortNo == 0 {
 		//if no in-port specified for a multicast flow, put NNI port as in-port
-		//so that a valid route can be found for the flow
+		//so that a valid path can be found for the flow
 		nniPorts := agent.GetNNIPorts()
 		if len(nniPorts) > 0 {
 			inPortNo = nniPorts[0]
-			log.Debugw("Assigning NNI port as in-port for the multicast flow", log.Fields{"nni": nniPorts[0], "flow:": flow})
+			log.Debugw("assigning-nni-port-as-in-port-for-multicast-flow", log.Fields{"nni": nniPorts[0], "flow:": flow})
 		}
 	}
 	outPortNo := fu.GetOutPort(flow)
 	deviceRules := fu.NewDeviceRules()
-	route := agent.GetRoute(inPortNo, outPortNo)
+	path, err := agent.GetRoute(ctx, inPortNo, outPortNo)
+	if err != nil {
+		log.Errorw("no-route", log.Fields{"inPortNo": inPortNo, "outPortNo": outPortNo, "error": err})
+		return deviceRules, err
+	}
 
-	switch len(route) {
+	switch len(path) {
 	case 0:
-		log.Errorw("no-route", log.Fields{"inPortNo": inPortNo, "outPortNo": outPortNo, "comment": "deleting-flow"})
-		//	TODO: Delete flow
-		return deviceRules
+		return deviceRules, status.Errorf(codes.FailedPrecondition, "no route from:%d to:%d", inPortNo, outPortNo)
 	case 2:
-		log.Debugw("route-found", log.Fields{"ingressHop": route[0], "egressHop": route[1]})
+		log.Debugw("route-found", log.Fields{"ingressHop": path[0], "egressHop": path[1]})
 	default:
-		log.Errorw("invalid-route-length", log.Fields{"routeLen": len(route)})
-		return deviceRules
+		return deviceRules, status.Errorf(codes.Aborted, "invalid route length %d", len(path))
 	}
 
 	// Process controller bound flow
 	if outPortNo != 0 && (outPortNo&0x7fffffff) == uint32(ofp.OfpPortNo_OFPP_CONTROLLER) {
-		deviceRules = fd.processControllerBoundFlow(agent, route, inPortNo, outPortNo, flow)
+		deviceRules = fd.processControllerBoundFlow(ctx, agent, path, inPortNo, outPortNo, flow)
 	} else {
 		var ingressDevice *voltha.Device
 		var err error
-		if ingressDevice, err = fd.deviceMgr.GetDevice(ctx, route[0].DeviceID); err != nil {
-			log.Errorw("ingress-device-not-found", log.Fields{"deviceId": route[0].DeviceID, "flow": flow})
-			return deviceRules
+		if ingressDevice, err = fd.deviceMgr.GetDevice(ctx, path[0].DeviceID); err != nil {
+			return deviceRules, err
 		}
 		isUpstream := !ingressDevice.Root
 		if isUpstream { // Unicast OLT and ONU UL
-			log.Info("processOltAndOnuUpstreamNonControllerBoundUnicastFlows", log.Fields{"flows": flow})
-			deviceRules = fd.processUpstreamNonControllerBoundFlow(agent, route, inPortNo, outPortNo, flow)
+			log.Debug("process-olt-nd-onu-upstream-noncontrollerbound-unicast-flows", log.Fields{"flows": flow})
+			deviceRules = fd.processUpstreamNonControllerBoundFlow(ctx, path, inPortNo, outPortNo, flow)
 		} else if fu.HasNextTable(flow) && flow.TableId == 0 { // Unicast OLT flow DL
-			log.Debugw("processOltDownstreamNonControllerBoundFlowWithNextTable", log.Fields{"flows": flow})
-			deviceRules = fd.processDownstreamFlowWithNextTable(agent, route, inPortNo, outPortNo, flow)
+			log.Debugw("process-olt-downstream-noncontrollerbound-flow-with-nexttable", log.Fields{"flows": flow})
+			deviceRules = fd.processDownstreamFlowWithNextTable(ctx, agent, path, inPortNo, outPortNo, flow)
 		} else if flow.TableId == 1 && outPortNo != 0 { // Unicast ONU flow DL
-			log.Debugw("processOnuDownstreamUnicastFlow", log.Fields{"flows": flow})
-			deviceRules = fd.processUnicastFlow(agent, route, inPortNo, outPortNo, flow)
+			log.Debugw("process-onu-downstream-unicast-flow", log.Fields{"flows": flow})
+			deviceRules = fd.processUnicastFlow(ctx, path, inPortNo, outPortNo, flow)
 		} else if grpID := fu.GetGroup(flow); grpID != 0 && flow.TableId == 0 { //Multicast
-			log.Debugw("processMulticastFlow", log.Fields{"flows": flow})
-			deviceRules = fd.processMulticastFlow(agent, route, inPortNo, outPortNo, flow, grpID, groupMap)
+			log.Debugw("process-multicast-flow", log.Fields{"flows": flow})
+			deviceRules = fd.processMulticastFlow(ctx, path, inPortNo, outPortNo, flow, grpID, groupMap)
 		} else {
-			log.Errorw("unknown-downstream-flow", log.Fields{"flow": *flow})
+			return deviceRules, status.Errorf(codes.Aborted, "unknown downstream flow %v", *flow)
 		}
 	}
 	deviceRules = fd.updateOutputPortForControllerBoundFlowForParentDevide(flow, deviceRules)
-	return deviceRules
+	return deviceRules, nil
 }
diff --git a/rw_core/flowdecomposition/flow_decomposer_test.go b/rw_core/flowdecomposition/flow_decomposer_test.go
index 8e2d9f3..29c1a6a 100644
--- a/rw_core/flowdecomposition/flow_decomposer_test.go
+++ b/rw_core/flowdecomposition/flow_decomposer_test.go
@@ -18,13 +18,15 @@
 import (
 	"context"
 	"errors"
-	"github.com/opencord/voltha-go/rw_core/graph"
 	"github.com/opencord/voltha-go/rw_core/mocks"
+	"github.com/opencord/voltha-go/rw_core/route"
 	fu "github.com/opencord/voltha-lib-go/v3/pkg/flows"
 	"github.com/opencord/voltha-lib-go/v3/pkg/log"
 	ofp "github.com/opencord/voltha-protos/v3/go/openflow_13"
 	"github.com/opencord/voltha-protos/v3/go/voltha"
 	"github.com/stretchr/testify/assert"
+	"google.golang.org/grpc/codes"
+	"google.golang.org/grpc/status"
 
 	"testing"
 )
@@ -116,9 +118,9 @@
 type testFlowDecomposer struct {
 	dMgr           *testDeviceManager
 	logicalPorts   map[uint32]*voltha.LogicalPort
-	routes         map[graph.OFPortLink][]graph.RouteHop
+	routes         map[route.OFPortLink][]route.Hop
 	defaultRules   *fu.DeviceRules
-	deviceGraph    *graph.DeviceGraph
+	deviceRoutes   *route.DeviceRoutes
 	fd             *FlowDecomposer
 	logicalPortsNo map[uint32]bool
 }
@@ -141,11 +143,11 @@
 	tfd.logicalPortsNo[10] = false
 	tfd.logicalPortsNo[65536] = true // nni
 
-	tfd.routes = make(map[graph.OFPortLink][]graph.RouteHop)
+	tfd.routes = make(map[route.OFPortLink][]route.Hop)
 
 	//DOWNSTREAM ROUTES
 
-	tfd.routes[graph.OFPortLink{Ingress: 10, Egress: 1}] = []graph.RouteHop{
+	tfd.routes[route.OFPortLink{Ingress: 10, Egress: 1}] = []route.Hop{
 		{
 			DeviceID: "olt",
 			Ingress:  tfd.dMgr.devices["olt"].Ports[1].PortNo,
@@ -158,7 +160,7 @@
 		},
 	}
 
-	tfd.routes[graph.OFPortLink{Ingress: 10, Egress: 2}] = []graph.RouteHop{
+	tfd.routes[route.OFPortLink{Ingress: 10, Egress: 2}] = []route.Hop{
 		{
 			DeviceID: "olt",
 			Ingress:  tfd.dMgr.devices["olt"].Ports[1].PortNo,
@@ -170,7 +172,7 @@
 			Egress:   tfd.dMgr.devices["onu2"].Ports[1].PortNo,
 		},
 	}
-	tfd.routes[graph.OFPortLink{Ingress: 10, Egress: 3}] = []graph.RouteHop{
+	tfd.routes[route.OFPortLink{Ingress: 10, Egress: 3}] = []route.Hop{
 		{
 			DeviceID: "olt",
 			Ingress:  tfd.dMgr.devices["olt"].Ports[1].PortNo,
@@ -182,7 +184,7 @@
 			Egress:   tfd.dMgr.devices["onu3"].Ports[1].PortNo,
 		},
 	}
-	tfd.routes[graph.OFPortLink{Ingress: 10, Egress: 4}] = []graph.RouteHop{
+	tfd.routes[route.OFPortLink{Ingress: 10, Egress: 4}] = []route.Hop{
 		{
 			DeviceID: "olt",
 			Ingress:  tfd.dMgr.devices["olt"].Ports[1].PortNo,
@@ -194,7 +196,7 @@
 			Egress:   tfd.dMgr.devices["onu4"].Ports[1].PortNo,
 		},
 	}
-	tfd.routes[graph.OFPortLink{Ingress: 10, Egress: 10}] = []graph.RouteHop{
+	tfd.routes[route.OFPortLink{Ingress: 10, Egress: 10}] = []route.Hop{
 		{
 			DeviceID: "olt",
 			Ingress:  tfd.dMgr.devices["olt"].Ports[1].PortNo,
@@ -209,7 +211,7 @@
 
 	//UPSTREAM DATA PLANE
 
-	tfd.routes[graph.OFPortLink{Ingress: 1, Egress: 10}] = []graph.RouteHop{
+	tfd.routes[route.OFPortLink{Ingress: 1, Egress: 10}] = []route.Hop{
 		{
 			DeviceID: "onu1",
 			Ingress:  tfd.dMgr.devices["onu1"].Ports[1].PortNo,
@@ -221,7 +223,7 @@
 			Egress:   tfd.dMgr.devices["olt"].Ports[1].PortNo,
 		},
 	}
-	tfd.routes[graph.OFPortLink{Ingress: 2, Egress: 10}] = []graph.RouteHop{
+	tfd.routes[route.OFPortLink{Ingress: 2, Egress: 10}] = []route.Hop{
 		{
 			DeviceID: "onu2",
 			Ingress:  tfd.dMgr.devices["onu2"].Ports[1].PortNo,
@@ -233,7 +235,7 @@
 			Egress:   tfd.dMgr.devices["olt"].Ports[1].PortNo,
 		},
 	}
-	tfd.routes[graph.OFPortLink{Ingress: 3, Egress: 10}] = []graph.RouteHop{
+	tfd.routes[route.OFPortLink{Ingress: 3, Egress: 10}] = []route.Hop{
 		{
 			DeviceID: "onu3",
 			Ingress:  tfd.dMgr.devices["onu3"].Ports[1].PortNo,
@@ -245,7 +247,7 @@
 			Egress:   tfd.dMgr.devices["olt"].Ports[1].PortNo,
 		},
 	}
-	tfd.routes[graph.OFPortLink{Ingress: 4, Egress: 10}] = []graph.RouteHop{
+	tfd.routes[route.OFPortLink{Ingress: 4, Egress: 10}] = []route.Hop{
 		{
 			DeviceID: "onu4",
 			Ingress:  tfd.dMgr.devices["onu4"].Ports[1].PortNo,
@@ -261,7 +263,7 @@
 	//UPSTREAM NEXT TABLE BASED
 
 	// openflow port 0 means absence of a port - go/protobuf interpretation
-	tfd.routes[graph.OFPortLink{Ingress: 1, Egress: 0}] = []graph.RouteHop{
+	tfd.routes[route.OFPortLink{Ingress: 1, Egress: 0}] = []route.Hop{
 		{
 			DeviceID: "onu1",
 			Ingress:  tfd.dMgr.devices["onu1"].Ports[1].PortNo,
@@ -273,7 +275,7 @@
 			Egress:   tfd.dMgr.devices["olt"].Ports[1].PortNo,
 		},
 	}
-	tfd.routes[graph.OFPortLink{Ingress: 2, Egress: 0}] = []graph.RouteHop{
+	tfd.routes[route.OFPortLink{Ingress: 2, Egress: 0}] = []route.Hop{
 		{
 			DeviceID: "onu2",
 			Ingress:  tfd.dMgr.devices["onu2"].Ports[1].PortNo,
@@ -285,7 +287,7 @@
 			Egress:   tfd.dMgr.devices["olt"].Ports[1].PortNo,
 		},
 	}
-	tfd.routes[graph.OFPortLink{Ingress: 3, Egress: 0}] = []graph.RouteHop{
+	tfd.routes[route.OFPortLink{Ingress: 3, Egress: 0}] = []route.Hop{
 		{
 			DeviceID: "onu3",
 			Ingress:  tfd.dMgr.devices["onu3"].Ports[1].PortNo,
@@ -297,7 +299,7 @@
 			Egress:   tfd.dMgr.devices["olt"].Ports[1].PortNo,
 		},
 	}
-	tfd.routes[graph.OFPortLink{Ingress: 4, Egress: 0}] = []graph.RouteHop{
+	tfd.routes[route.OFPortLink{Ingress: 4, Egress: 0}] = []route.Hop{
 		{
 			DeviceID: "onu4",
 			Ingress:  tfd.dMgr.devices["onu4"].Ports[1].PortNo,
@@ -312,7 +314,7 @@
 
 	// DOWNSTREAM NEXT TABLE BASED
 
-	tfd.routes[graph.OFPortLink{Ingress: 10, Egress: 0}] = []graph.RouteHop{
+	tfd.routes[route.OFPortLink{Ingress: 10, Egress: 0}] = []route.Hop{
 		{
 			DeviceID: "olt",
 			Ingress:  tfd.dMgr.devices["olt"].Ports[1].PortNo,
@@ -321,7 +323,7 @@
 		{}, // 2nd hop is not known yet
 	}
 
-	tfd.routes[graph.OFPortLink{Ingress: 0, Egress: 10}] = []graph.RouteHop{
+	tfd.routes[route.OFPortLink{Ingress: 0, Egress: 10}] = []route.Hop{
 		{}, // 1st hop is wildcard
 		{
 			DeviceID: "olt",
@@ -390,9 +392,9 @@
 	tfd.defaultRules.AddFlowsAndGroup("onu4", fg)
 
 	//Set up the device graph - flow decomposer uses it only to verify whether a port is a root port.
-	tfd.deviceGraph = graph.NewDeviceGraph("ldid", tfd.getDeviceHelper)
-	tfd.deviceGraph.RootPorts = make(map[uint32]uint32)
-	tfd.deviceGraph.RootPorts[10] = 10
+	tfd.deviceRoutes = route.NewDeviceRoutes("ldid", tfd.getDeviceHelper)
+	tfd.deviceRoutes.RootPorts = make(map[uint32]uint32)
+	tfd.deviceRoutes.RootPorts[10] = 10
 
 	tfd.fd = NewFlowDecomposer(tfd.dMgr)
 
@@ -411,8 +413,8 @@
 	return nil
 }
 
-func (tfd *testFlowDecomposer) GetDeviceGraph() *graph.DeviceGraph {
-	return tfd.deviceGraph
+func (tfd *testFlowDecomposer) GetDeviceRoutes() *route.DeviceRoutes {
+	return tfd.deviceRoutes
 }
 
 func (tfd *testFlowDecomposer) GetAllDefaultRules() *fu.DeviceRules {
@@ -433,8 +435,8 @@
 	return lPorts
 }
 
-func (tfd *testFlowDecomposer) GetRoute(ingressPortNo uint32, egressPortNo uint32) []graph.RouteHop {
-	var portLink graph.OFPortLink
+func (tfd *testFlowDecomposer) GetRoute(ctx context.Context, ingressPortNo uint32, egressPortNo uint32) ([]route.Hop, error) {
+	var portLink route.OFPortLink
 	if egressPortNo == 0 {
 		portLink.Egress = 0
 	} else if egressPortNo&0x7fffffff == uint32(ofp.OfpPortNo_OFPP_CONTROLLER) {
@@ -449,10 +451,10 @@
 	}
 	for key, val := range tfd.routes {
 		if key.Ingress == portLink.Ingress && key.Egress == portLink.Egress {
-			return val
+			return val, nil
 		}
 	}
-	return nil
+	return nil, status.Errorf(codes.FailedPrecondition, "no route from:%d to:%d", ingressPortNo, egressPortNo)
 }
 
 func (tfd *testFlowDecomposer) GetNNIPorts() []uint32 {
@@ -484,7 +486,8 @@
 	groups := ofp.FlowGroups{}
 	tfd := newTestFlowDecomposer(newTestDeviceManager())
 
-	deviceRules := tfd.fd.DecomposeRules(context.Background(), tfd, flows, groups)
+	deviceRules, err := tfd.fd.DecomposeRules(context.Background(), tfd, flows, groups)
+	assert.Nil(t, err)
 	onu1FlowAndGroup := deviceRules.Rules["onu1"]
 	oltFlowAndGroup := deviceRules.Rules["olt"]
 	assert.Equal(t, 1, onu1FlowAndGroup.Flows.Len())
@@ -546,7 +549,8 @@
 	groups := ofp.FlowGroups{}
 	tfd := newTestFlowDecomposer(newTestDeviceManager())
 
-	deviceRules := tfd.fd.DecomposeRules(context.Background(), tfd, flows, groups)
+	deviceRules, err := tfd.fd.DecomposeRules(context.Background(), tfd, flows, groups)
+	assert.Nil(t, err)
 	onu1FlowAndGroup := deviceRules.Rules["onu1"]
 	oltFlowAndGroup := deviceRules.Rules["olt"]
 	assert.Equal(t, 1, onu1FlowAndGroup.Flows.Len())
@@ -607,7 +611,8 @@
 	groups := ofp.FlowGroups{}
 	tfd := newTestFlowDecomposer(newTestDeviceManager())
 
-	deviceRules := tfd.fd.DecomposeRules(context.Background(), tfd, flows, groups)
+	deviceRules, err := tfd.fd.DecomposeRules(context.Background(), tfd, flows, groups)
+	assert.Nil(t, err)
 	onu1FlowAndGroup := deviceRules.Rules["onu1"]
 	oltFlowAndGroup := deviceRules.Rules["olt"]
 	assert.Equal(t, 1, onu1FlowAndGroup.Flows.Len())
@@ -668,7 +673,8 @@
 	groups := ofp.FlowGroups{}
 	tfd := newTestFlowDecomposer(newTestDeviceManager())
 
-	deviceRules := tfd.fd.DecomposeRules(context.Background(), tfd, flows, groups)
+	deviceRules, err := tfd.fd.DecomposeRules(context.Background(), tfd, flows, groups)
+	assert.Nil(t, err)
 	onu1FlowAndGroup := deviceRules.Rules["onu1"]
 	oltFlowAndGroup := deviceRules.Rules["olt"]
 	assert.Equal(t, 1, onu1FlowAndGroup.Flows.Len())
@@ -732,7 +738,8 @@
 	flows := ofp.Flows{Items: []*ofp.OfpFlowStats{fu.MkFlowStat(fa)}}
 	groups := ofp.FlowGroups{}
 	tfd := newTestFlowDecomposer(newTestDeviceManager())
-	deviceRules := tfd.fd.DecomposeRules(context.Background(), tfd, flows, groups)
+	deviceRules, err := tfd.fd.DecomposeRules(context.Background(), tfd, flows, groups)
+	assert.Nil(t, err)
 	onu1FlowAndGroup := deviceRules.Rules["onu1"]
 	oltFlowAndGroup := deviceRules.Rules["olt"]
 	assert.Nil(t, onu1FlowAndGroup)
@@ -794,7 +801,8 @@
 	groups := ofp.FlowGroups{}
 	tfd := newTestFlowDecomposer(newTestDeviceManager())
 
-	deviceRules := tfd.fd.DecomposeRules(context.Background(), tfd, flows, groups)
+	deviceRules, err := tfd.fd.DecomposeRules(context.Background(), tfd, flows, groups)
+	assert.Nil(t, err)
 	onu1FlowAndGroup := deviceRules.Rules["onu1"]
 	oltFlowAndGroup := deviceRules.Rules["olt"]
 	assert.NotNil(t, onu1FlowAndGroup)
@@ -896,8 +904,8 @@
 	groups := ofp.FlowGroups{}
 	tfd := newTestFlowDecomposer(newTestDeviceManager())
 
-	deviceRules := tfd.fd.DecomposeRules(context.Background(), tfd, flows, groups)
-
+	deviceRules, err := tfd.fd.DecomposeRules(context.Background(), tfd, flows, groups)
+	assert.Nil(t, err)
 	onu1FlowAndGroup := deviceRules.Rules["onu1"]
 	oltFlowAndGroup := deviceRules.Rules["olt"]
 	assert.Equal(t, 1, onu1FlowAndGroup.Flows.Len())
@@ -983,7 +991,8 @@
 	groups := ofp.FlowGroups{Items: []*ofp.OfpGroupEntry{fu.MkGroupStat(ga)}}
 	tfd := newTestFlowDecomposer(newTestDeviceManager())
 
-	deviceRules := tfd.fd.DecomposeRules(context.Background(), tfd, flows, groups)
+	deviceRules, err := tfd.fd.DecomposeRules(context.Background(), tfd, flows, groups)
+	assert.Nil(t, err)
 	oltFlowAndGroup := deviceRules.Rules["olt"]
 	assert.Equal(t, 1, oltFlowAndGroup.Flows.Len())
 	assert.Equal(t, 0, oltFlowAndGroup.Groups.Len())