diff --git a/rw_core/core/logical_device_agent.go b/rw_core/core/logical_device_agent.go
index 732e9cf..e123be7 100644
--- a/rw_core/core/logical_device_agent.go
+++ b/rw_core/core/logical_device_agent.go
@@ -35,7 +35,7 @@
 )
 
 type LogicalDeviceAgent struct {
-	logicalDeviceId   string
+	logicalDeviceId string
 	//lastData          *voltha.LogicalDevice
 	rootDeviceId      string
 	deviceMgr         *DeviceManager
@@ -46,9 +46,9 @@
 	DefaultFlowRules  *fu.DeviceRules
 	flowProxy         *model.Proxy
 	groupProxy        *model.Proxy
-	ldProxy *model.Proxy
-	portProxies map[string]*model.Proxy
-	portProxiesLock sync.RWMutex
+	ldProxy           *model.Proxy
+	portProxies       map[string]*model.Proxy
+	portProxiesLock   sync.RWMutex
 	lockLogicalDevice sync.RWMutex
 	flowDecomposer    *fd.FlowDecomposer
 }
@@ -246,26 +246,21 @@
 	return nil, status.Errorf(codes.NotFound, "logical_device-%s", agent.logicalDeviceId)
 }
 
-
-func (agent *LogicalDeviceAgent)  addLogicalPort (device *voltha.Device, port *voltha.Port) error {
+func (agent *LogicalDeviceAgent) addLogicalPort(device *voltha.Device, port *voltha.Port) error {
 	log.Debugw("addLogicalPort", log.Fields{"deviceId": device.Id, "port": port})
-	var changed bool
 	var err error
 	if port.Type == voltha.Port_ETHERNET_NNI {
-		if changed, err = agent.addNNILogicalPort(device, port); err != nil {
+		if _, err = agent.addNNILogicalPort(device, port); err != nil {
 			return err
 		}
 	} else if port.Type == voltha.Port_ETHERNET_UNI {
-		if changed, err =  agent.addUNILogicalPort(device, port); err != nil {
+		if _, err = agent.addUNILogicalPort(device, port); err != nil {
 			return err
 		}
 	} else {
 		log.Debugw("invalid-port-type", log.Fields{"deviceId": device.Id, "port": port})
 		return nil
 	}
-	if changed {
-		go agent.setupDeviceGraph()
-	}
 	return nil
 }
 
@@ -284,24 +279,16 @@
 	}
 
 	//Get UNI port number
-	changesMade := false
 	for _, port := range device.Ports {
-		changed := false
 		if port.Type == voltha.Port_ETHERNET_NNI {
-			if changed, err = agent.addNNILogicalPort(device, port); err != nil {
+			if _, err = agent.addNNILogicalPort(device, port); err != nil {
 				log.Errorw("error-adding-UNI-port", log.Fields{"error": err})
-			} else {
-				changesMade = changed || changesMade
 			}
 		}
 	}
-	if changesMade {
-		go agent.setupDeviceGraph()
-	}
 	return err
 }
 
-
 // setupUNILogicalPorts creates a UNI port on the logical device that represents a child UNI interface
 func (agent *LogicalDeviceAgent) setupUNILogicalPorts(ctx context.Context, childDevice *voltha.Device) error {
 	//now := time.Now()
@@ -311,20 +298,13 @@
 	var err error
 
 	//Get UNI port number
-	changesMade := false
 	for _, port := range childDevice.Ports {
-		changed := false
 		if port.Type == voltha.Port_ETHERNET_UNI {
-			if changed, err = agent.addUNILogicalPort(childDevice, port); err != nil {
+			if _, err = agent.addUNILogicalPort(childDevice, port); err != nil {
 				log.Errorw("error-adding-UNI-port", log.Fields{"error": err})
-			} else {
-				changesMade = changed || changesMade
 			}
 		}
 	}
-	if changesMade {
-		go agent.setupDeviceGraph()
-	}
 	return err
 }
 
@@ -811,7 +791,7 @@
 			if len(agent.deviceGraph.Routes) == 0 {
 				// If there are no routes set (usually when the logical device has only NNI port(s), then just return an
 				// internal route
-				hop := graph.RouteHop{DeviceID:ld.RootDeviceId, Ingress:ingressPortNo, Egress:egressPortNo}
+				hop := graph.RouteHop{DeviceID: ld.RootDeviceId, Ingress: ingressPortNo, Egress: egressPortNo}
 				routes = append(routes, hop)
 				routes = append(routes, hop)
 				return routes
@@ -863,15 +843,6 @@
 	return agent.getPreCalculatedRoute(ingressPortNo, egressPortNo)
 }
 
-// updateRoutes updates the device routes whenever there is a device or port changes relevant to this
-// logical device.   TODO: Add more heuristics to this process to update the routes where a change has occurred
-// instead of rebuilding the entire set of routes
-func (agent *LogicalDeviceAgent) updateRoutes() {
-	if ld, err := agent.GetLogicalDevice(); err == nil {
-		agent.deviceGraph.ComputeRoutes(ld.Ports)
-	}
-}
-
 func (agent *LogicalDeviceAgent) rootDeviceDefaultRules() *fu.FlowsAndGroups {
 	return fu.NewFlowsAndGroups()
 }
@@ -895,7 +866,7 @@
 	}
 	//it is possible that the downstream ports are not created, but the flow_decomposition has already
 	//kicked in. In such scenarios, cut short the processing and return.
-	if len(downstreamPorts) == 0 || len(upstreamPorts) == 0{
+	if len(downstreamPorts) == 0 || len(upstreamPorts) == 0 {
 		return fg
 	}
 	// set up the default flows
@@ -965,14 +936,13 @@
 
 func (agent *LogicalDeviceAgent) GetAllDefaultRules() *fu.DeviceRules {
 	// Get latest
-	var lDevice *voltha.LogicalDevice
 	var err error
-	if lDevice, err = agent.GetLogicalDevice(); err != nil {
+	if _, err = agent.GetLogicalDevice(); err != nil {
 		return fu.NewDeviceRules()
 	}
 	if agent.DefaultFlowRules == nil { // Nothing setup yet
-		agent.deviceGraph = graph.NewDeviceGraph(agent.deviceMgr.GetDevice)
-		agent.deviceGraph.ComputeRoutes(lDevice.Ports)
+		// Setup device graph if needed
+		agent.setupDeviceGraph()
 		agent.DefaultFlowRules = agent.generateDefaultRules()
 	}
 	return agent.DefaultFlowRules
@@ -1000,12 +970,24 @@
 
 //setupDeviceGraph creates the device graph if not done already
 func (agent *LogicalDeviceAgent) setupDeviceGraph() {
+	agent.lockLogicalDevice.Lock()
+	defer agent.lockLogicalDevice.Unlock()
 	if agent.deviceGraph == nil {
-		agent.deviceGraph = graph.NewDeviceGraph(agent.deviceMgr.GetDevice)
-		agent.updateRoutes()
+		agent.deviceGraph = graph.NewDeviceGraph(agent.logicalDeviceId, agent.deviceMgr.GetDevice)
+		if ld, err := agent.getLogicalDeviceWithoutLock(); err == nil {
+			agent.deviceGraph.ComputeRoutes(ld.Ports)
+		}
 	}
 }
 
+//updateDeviceGraph updates the device graph if not done already
+func (agent *LogicalDeviceAgent) updateDeviceGraph(lp *voltha.LogicalPort) {
+	if agent.deviceGraph == nil {
+		agent.deviceGraph = graph.NewDeviceGraph(agent.logicalDeviceId, agent.deviceMgr.GetDevice)
+	}
+	agent.deviceGraph.AddPort(lp)
+}
+
 func (agent *LogicalDeviceAgent) flowTableUpdated(args ...interface{}) interface{} {
 	log.Debugw("flowTableUpdated-callback", log.Fields{"argsLen": len(args)})
 
@@ -1035,10 +1017,10 @@
 	var err error
 	for deviceId, value := range deviceRules.GetRules() {
 		if err = agent.deviceMgr.updateFlows(deviceId, value.ListFlows()); err != nil {
-			log.Error("update-flows-failed", log.Fields{"deviceID":deviceId})
+			log.Error("update-flows-failed", log.Fields{"deviceID": deviceId})
 		}
 		if err = agent.deviceMgr.updateGroups(deviceId, value.ListGroups()); err != nil {
-			log.Error("update-groups-failed", log.Fields{"deviceID":deviceId})
+			log.Error("update-groups-failed", log.Fields{"deviceID": deviceId})
 		}
 	}
 
@@ -1073,10 +1055,10 @@
 	var err error
 	for deviceId, value := range deviceRules.GetRules() {
 		if err = agent.deviceMgr.updateFlows(deviceId, value.ListFlows()); err != nil {
-			log.Error("update-flows-failed", log.Fields{"deviceID":deviceId})
+			log.Error("update-flows-failed", log.Fields{"deviceID": deviceId})
 		}
 		if err = agent.deviceMgr.updateGroups(deviceId, value.ListGroups()); err != nil {
-			log.Error("update-groups-failed", log.Fields{"deviceID":deviceId})
+			log.Error("update-groups-failed", log.Fields{"deviceID": deviceId})
 		}
 
 	}
@@ -1110,7 +1092,7 @@
 
 	// Send the port change event to the OF controller
 	agent.ldeviceMgr.grpcNbiHdlr.sendChangeEvent(agent.logicalDeviceId,
-		&ofp.OfpPortStatus{Reason:ofp.OfpPortReason_OFPPR_ADD, Desc:port.OfpPort})
+		&ofp.OfpPortStatus{Reason: ofp.OfpPortReason_OFPPR_ADD, Desc: port.OfpPort})
 
 	return nil
 }
@@ -1140,13 +1122,13 @@
 
 	// Send the port change event to the OF controller
 	agent.ldeviceMgr.grpcNbiHdlr.sendChangeEvent(agent.logicalDeviceId,
-		&ofp.OfpPortStatus{Reason:ofp.OfpPortReason_OFPPR_DELETE, Desc:port.OfpPort})
+		&ofp.OfpPortStatus{Reason: ofp.OfpPortReason_OFPPR_DELETE, Desc: port.OfpPort})
 
 	return nil
 }
 
 // diff go over two lists of logical ports and return what's new, what's changed and what's removed.
-func diff(oldList , newList []*voltha.LogicalPort) (newPorts, changedPorts, deletedPorts []*voltha.LogicalPort) {
+func diff(oldList, newList []*voltha.LogicalPort) (newPorts, changedPorts, deletedPorts []*voltha.LogicalPort) {
 	newPorts = make([]*voltha.LogicalPort, 0)
 	changedPorts = make([]*voltha.LogicalPort, 0)
 	deletedPorts = make([]*voltha.LogicalPort, 0)
@@ -1212,26 +1194,25 @@
 	// Send the port change events to the OF controller
 	for _, new := range newPorts {
 		go agent.ldeviceMgr.grpcNbiHdlr.sendChangeEvent(agent.logicalDeviceId,
-			&ofp.OfpPortStatus{Reason:ofp.OfpPortReason_OFPPR_ADD, Desc:new.OfpPort})
+			&ofp.OfpPortStatus{Reason: ofp.OfpPortReason_OFPPR_ADD, Desc: new.OfpPort})
 	}
 	for _, change := range changedPorts {
 		go agent.ldeviceMgr.grpcNbiHdlr.sendChangeEvent(agent.logicalDeviceId,
-			&ofp.OfpPortStatus{Reason:ofp.OfpPortReason_OFPPR_MODIFY, Desc:change.OfpPort})
+			&ofp.OfpPortStatus{Reason: ofp.OfpPortReason_OFPPR_MODIFY, Desc: change.OfpPort})
 	}
 	for _, del := range deletedPorts {
 		go agent.ldeviceMgr.grpcNbiHdlr.sendChangeEvent(agent.logicalDeviceId,
-			&ofp.OfpPortStatus{Reason:ofp.OfpPortReason_OFPPR_DELETE, Desc:del.OfpPort})
+			&ofp.OfpPortStatus{Reason: ofp.OfpPortReason_OFPPR_DELETE, Desc: del.OfpPort})
 	}
 
 	return nil
 }
 
-
 // addNNILogicalPort adds an NNI port to the logical device.  It returns a bool representing whether a port has been
 // added and an eror in case a valid error is encountered. If the port was successfully added it will return
 // (true, nil).   If the device is not in the correct state it will return (false, nil) as this is a valid
 // scenario. This also applies to the case where the port was already added.
-func (agent *LogicalDeviceAgent) addNNILogicalPort (device *voltha.Device, port *voltha.Port)  (bool, error) {
+func (agent *LogicalDeviceAgent) addNNILogicalPort(device *voltha.Device, port *voltha.Port) (bool, error) {
 	//now := time.Now()
 	//defer fmt.Println("setupNNILogicalPorts:", device.Id, time.Since(now))
 	log.Debugw("addNNILogicalPort", log.Fields{"NNI": port})
@@ -1286,10 +1267,15 @@
 		log.Errorw("error-updating-logical-device", log.Fields{"error": err})
 		return false, err
 	}
+
+	// Update the device graph with this new logical port
+	clonedLP := (proto.Clone(lp)).(*voltha.LogicalPort)
+	go agent.updateDeviceGraph(clonedLP)
+
 	return true, nil
 }
 
-func (agent *LogicalDeviceAgent) portExist (device *voltha.Device, port *voltha.Port) bool {
+func (agent *LogicalDeviceAgent) portExist(device *voltha.Device, port *voltha.Port) bool {
 	if ldevice, _ := agent.getLogicalDeviceWithoutLock(); ldevice != nil {
 		for _, lPort := range ldevice.Ports {
 			if lPort.DeviceId == device.Id && lPort.DevicePortNo == port.PortNo && lPort.Id == port.Label {
@@ -1300,12 +1286,11 @@
 	return false
 }
 
-
 // addUNILogicalPort adds an UNI port to the logical device.  It returns a bool representing whether a port has been
 // added and an eror in case a valid error is encountered. If the port was successfully added it will return
 // (true, nil).   If the device is not in the correct state it will return (false, nil) as this is a valid
 // scenario. This also applies to the case where the port was already added.
-func (agent *LogicalDeviceAgent) addUNILogicalPort (childDevice *voltha.Device, port *voltha.Port)  (bool, error) {
+func (agent *LogicalDeviceAgent) addUNILogicalPort(childDevice *voltha.Device, port *voltha.Port) (bool, error) {
 	//now := time.Now()
 	//defer fmt.Println("addUNILogicalPort:", childDevice.Id, time.Since(now))
 	log.Debugw("addUNILogicalPort", log.Fields{"port": port})
@@ -1350,7 +1335,14 @@
 			cloned.Ports = make([]*voltha.LogicalPort, 0)
 		}
 		cloned.Ports = append(cloned.Ports, portCap.Port)
-		return true, agent.updateLogicalDeviceWithoutLock(cloned)
+		if err := agent.updateLogicalDeviceWithoutLock(cloned); err != nil {
+			return false, err
+		}
+
+		// Update the device graph with this new logical port
+		clonedLP := (proto.Clone(portCap.Port)).(*voltha.LogicalPort)
+		go agent.updateDeviceGraph(clonedLP)
+		return true, nil
 	}
 }
 
@@ -1360,7 +1352,7 @@
 	//frame := packet.GetData()
 	//TODO: Use a channel between the logical agent and the device agent
 	if err := agent.deviceMgr.packetOut(agent.rootDeviceId, outPort, packet); err != nil {
-		log.Error("packetout-failed", log.Fields{"logicalDeviceID":agent.rootDeviceId})
+		log.Error("packetout-failed", log.Fields{"logicalDeviceID": agent.rootDeviceId})
 	}
 }
 
diff --git a/rw_core/core/logical_device_manager.go b/rw_core/core/logical_device_manager.go
index 2fc0f1e..2417b60 100644
--- a/rw_core/core/logical_device_manager.go
+++ b/rw_core/core/logical_device_manager.go
@@ -336,7 +336,7 @@
 			return err
 		}
 		// Update the device routes - let it run in its own go routine as it can take time
-		go agent.updateRoutes()
+		//go agent.updateRoutes()
 	}
 	return nil
 }
diff --git a/rw_core/flow_decomposition/flow_decomposer_test.go b/rw_core/flow_decomposition/flow_decomposer_test.go
index a0a2e3b..d27fd21 100644
--- a/rw_core/flow_decomposition/flow_decomposer_test.go
+++ b/rw_core/flow_decomposition/flow_decomposer_test.go
@@ -29,7 +29,7 @@
 
 func init() {
 	log.AddPackage(log.JSON, log.WarnLevel, nil)
-	log.UpdateAllLoggers(log.Fields{"instanceId": "flow-descomposition"})
+	log.UpdateAllLoggers(log.Fields{"instanceId": "flow-decomposition"})
 	log.SetAllLogLevel(log.WarnLevel)
 }
 
@@ -361,7 +361,7 @@
 	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(tfd.getDeviceHelper)
+	tfd.deviceGraph = graph.NewDeviceGraph("ldid", tfd.getDeviceHelper)
 	tfd.deviceGraph.RootPorts = make(map[uint32]uint32)
 	tfd.deviceGraph.RootPorts[10] = 10
 
diff --git a/rw_core/graph/device_graph.go b/rw_core/graph/device_graph.go
index 0ed2748..376df16 100644
--- a/rw_core/graph/device_graph.go
+++ b/rw_core/graph/device_graph.go
@@ -28,7 +28,7 @@
 )
 
 func init() {
-	log.AddPackage(log.JSON, log.DebugLevel, nil)
+	log.AddPackage(log.JSON, log.WarnLevel, nil)
 }
 
 type RouteHop struct {
@@ -42,91 +42,202 @@
 	Egress  uint32
 }
 
+type ofPortLinkToPath struct {
+	link OFPortLink
+	path []RouteHop
+}
+
 type GetDeviceFunc func(id string) (*voltha.Device, error)
 
-func concatDeviceIdPortId(deviceId string, portId uint32) string {
-	return fmt.Sprintf("%s:%d", deviceId, portId)
-}
-
-func splitIntoDeviceIdPortId(id string) (string, uint32, error) {
-	result := strings.Split(id, ":")
-	if len(result) != 2 {
-		return "", 0, errors.New(fmt.Sprintf("invalid-id-%s", id))
-	}
-	if temp, err := strconv.ParseInt(result[1], 10, 32); err != nil {
-		return "", 0, errors.New(fmt.Sprintf("invalid-id-%s-%s", id, err.Error()))
-	} else {
-		return result[0], uint32(temp), nil
-	}
-}
-
 type DeviceGraph struct {
-	GGraph        goraph.Graph
-	getDevice     GetDeviceFunc
-	logicalPorts  []*voltha.LogicalPort
-	RootPorts     map[uint32]uint32
-	Routes        map[OFPortLink][]RouteHop
-	graphBuildLock sync.RWMutex
-	boundaryPorts sync.Map
+	logicalDeviceId    string
+	GGraph             goraph.Graph
+	getDeviceFromModel GetDeviceFunc
+	logicalPorts       []*voltha.LogicalPort
+	rootPortsString    map[string]uint32
+	nonRootPortsString map[string]uint32
+	RootPorts          map[uint32]uint32
+	rootPortsLock      sync.RWMutex
+	Routes             map[OFPortLink][]RouteHop
+	graphBuildLock     sync.RWMutex
+	boundaryPorts      map[string]uint32
+	boundaryPortsLock  sync.RWMutex
+	cachedDevices      map[string]*voltha.Device
+	cachedDevicesLock  sync.RWMutex
+	devicesAdded       map[string]string
+	portsAdded         map[string]string
 }
 
-func NewDeviceGraph(getDevice GetDeviceFunc) *DeviceGraph {
+func NewDeviceGraph(logicalDeviceId string, getDevice GetDeviceFunc) *DeviceGraph {
 	var dg DeviceGraph
+	dg.logicalDeviceId = logicalDeviceId
 	dg.GGraph = goraph.NewGraph()
-	dg.getDevice = getDevice
+	dg.getDeviceFromModel = getDevice
 	dg.graphBuildLock = sync.RWMutex{}
+	dg.cachedDevicesLock = sync.RWMutex{}
+	dg.rootPortsLock = sync.RWMutex{}
+	dg.devicesAdded = make(map[string]string)
+	dg.portsAdded = make(map[string]string)
+	dg.rootPortsString = make(map[string]uint32)
+	dg.nonRootPortsString = make(map[string]uint32)
+	dg.RootPorts = make(map[uint32]uint32)
+	dg.boundaryPorts = make(map[string]uint32)
+	dg.Routes = make(map[OFPortLink][]RouteHop)
+	dg.cachedDevices = make(map[string]*voltha.Device)
+	log.Debug("new device graph created ...")
 	return &dg
 }
 
+//IsRootPort returns true if the port is a root port on a logical device
+func (dg *DeviceGraph) IsRootPort(port uint32) bool {
+	dg.rootPortsLock.RLock()
+	defer dg.rootPortsLock.RUnlock()
+	_, exist := dg.RootPorts[port]
+	return exist
+}
+
+//GetDeviceNodeIds retrieves all the nodes in the device graph
+func (dg *DeviceGraph) GetDeviceNodeIds() map[string]string {
+	dg.graphBuildLock.RLock()
+	defer dg.graphBuildLock.RUnlock()
+	nodeIds := make(map[string]string)
+	nodesMap := dg.GGraph.GetNodes()
+	for id, node := range nodesMap {
+		if len(strings.Split(node.String(), ":")) != 2 { // not port node
+			nodeIds[id.String()] = id.String()
+		}
+	}
+	return nodeIds
+}
+
+//ComputeRoutes creates a device graph from the logical ports and then calculates all the routes
+//between the logical ports.  This will clear up the graph and routes if there were any.
 func (dg *DeviceGraph) ComputeRoutes(lps []*voltha.LogicalPort) {
 	if dg == nil {
 		return
 	}
 	dg.graphBuildLock.Lock()
 	defer dg.graphBuildLock.Unlock()
-	dg.logicalPorts = lps
-	// Set the root ports
-	dg.RootPorts = make(map[uint32]uint32)
-	for _, lp := range lps {
-		if lp.RootPort {
-			dg.RootPorts[lp.OfpPort.PortNo] = lp.OfpPort.PortNo
-		}
-	}
-	// set the boundary ports
-	dg.boundaryPorts.Range(func(key interface{}, value interface{}) bool {
-		dg.boundaryPorts.Delete(key)
-		return true
-	})
-	//dg.boundaryPorts = sync.Map{}
 
+	// Clear the graph
+	dg.reset()
+
+	dg.logicalPorts = lps
+
+	// Set the root, non-root ports and boundary ports
 	for _, lp := range lps {
-		dg.boundaryPorts.Store(fmt.Sprintf("%s:%d", lp.DeviceId, lp.DevicePortNo), lp.OfpPort.PortNo)
+		portId := concatDeviceIdPortId(lp.DeviceId, lp.DevicePortNo)
+		if lp.RootPort {
+			dg.rootPortsString[portId] = lp.OfpPort.PortNo
+			dg.RootPorts[lp.OfpPort.PortNo] = lp.OfpPort.PortNo
+		} else {
+			dg.nonRootPortsString[portId] = lp.OfpPort.PortNo
+		}
+		dg.boundaryPorts[portId] = lp.OfpPort.PortNo
 	}
-	dg.Routes = make(map[OFPortLink][]RouteHop)
 
 	// Build the graph
 	var device *voltha.Device
-	devicesAdded := make(map[string]string)
-	portsAdded := make(map[string]string)
 	for _, logicalPort := range dg.logicalPorts {
 		device, _ = dg.getDevice(logicalPort.DeviceId)
-		dg.GGraph = dg.addDevice(device, dg.GGraph, &devicesAdded, &portsAdded, dg.boundaryPorts)
+		dg.GGraph = dg.addDevice(device, dg.GGraph, &dg.devicesAdded, &dg.portsAdded, dg.boundaryPorts)
 	}
+
 	dg.Routes = dg.buildRoutes()
 }
 
+// AddPort adds a port to the graph.  If the graph is empty it will just invoke ComputeRoutes function
+func (dg *DeviceGraph) AddPort(lp *voltha.LogicalPort) {
+	//  If the graph does not exist invoke ComputeRoutes.
+	if len(dg.boundaryPorts) == 0 {
+		dg.ComputeRoutes([]*voltha.LogicalPort{lp})
+		return
+	}
+
+	dg.graphBuildLock.Lock()
+	defer dg.graphBuildLock.Unlock()
+
+	portId := concatDeviceIdPortId(lp.DeviceId, lp.DevicePortNo)
+
+	//	If the port is already part of the boundary ports, do nothing
+	if dg.portExist(portId) {
+		fmt.Println("port exists")
+		return
+	}
+	// Add the device where this port is located to the device graph. If the device is already added then
+	// only the missing port will be added
+	device, _ := dg.getDevice(lp.DeviceId)
+	dg.GGraph = dg.addDevice(device, dg.GGraph, &dg.devicesAdded, &dg.portsAdded, dg.boundaryPorts)
+
+	if lp.RootPort {
+		// Compute the route from this root port to all non-root ports
+		dg.rootPortsString[portId] = lp.OfpPort.PortNo
+		dg.RootPorts[lp.OfpPort.PortNo] = lp.OfpPort.PortNo
+		dg.Routes = dg.buildPathsToAllNonRootPorts(lp)
+	} else {
+		// Compute the route from this port to all root ports
+		dg.nonRootPortsString[portId] = lp.OfpPort.PortNo
+		dg.Routes = dg.buildPathsToAllRootPorts(lp)
+	}
+
+	dg.Print()
+}
+
+func (dg *DeviceGraph) Print() error {
+	if level, err := log.GetPackageLogLevel(); err == nil && level == log.DebugLevel {
+		output := ""
+		routeNumber := 1
+		for k, v := range dg.Routes {
+			key := fmt.Sprintf("LP:%d->LP:%d", k.Ingress, k.Egress)
+			val := ""
+			for _, i := range v {
+				val += fmt.Sprintf("{%d->%s->%d},", i.Ingress, i.DeviceID, i.Egress)
+			}
+			val = val[:len(val)-1]
+			output += fmt.Sprintf("%d:{%s=>%s}   ", routeNumber, key, fmt.Sprintf("[%s]", val))
+			routeNumber += 1
+		}
+		log.Debugw("graph_routes", log.Fields{"lDeviceId": dg.logicalDeviceId, "Routes": output})
+	}
+	return nil
+}
+
+//getDevice returns the device either from the local cache (default) or from the model.
+//TODO: Set a cache timeout such that we do not use invalid data.  The full device lifecycle should also
+//be taken in consideration
+func (dg *DeviceGraph) getDevice(id string) (*voltha.Device, error) {
+	dg.cachedDevicesLock.RLock()
+	if d, exist := dg.cachedDevices[id]; exist {
+		dg.cachedDevicesLock.RUnlock()
+		//log.Debugw("getDevice - returned from cache", log.Fields{"deviceId": id})
+		return d, nil
+	}
+	dg.cachedDevicesLock.RUnlock()
+	//	Not cached
+	if d, err := dg.getDeviceFromModel(id); err != nil {
+		log.Errorw("device-not-found", log.Fields{"deviceId": id, "error": err})
+		return nil, err
+	} else { // cache it
+		dg.cachedDevicesLock.Lock()
+		dg.cachedDevices[id] = d
+		dg.cachedDevicesLock.Unlock()
+		//log.Debugw("getDevice - returned from model", log.Fields{"deviceId": id})
+		return d, nil
+	}
+}
+
+// addDevice adds a device to a device graph and setup edges that represent the device connections to its peers
 func (dg *DeviceGraph) addDevice(device *voltha.Device, g goraph.Graph, devicesAdded *map[string]string, portsAdded *map[string]string,
-	boundaryPorts sync.Map) goraph.Graph {
+	boundaryPorts map[string]uint32) goraph.Graph {
 
 	if device == nil {
 		return g
 	}
 
-	if _, exist := (*devicesAdded)[device.Id]; exist {
-		return g
+	if _, exist := (*devicesAdded)[device.Id]; !exist {
+		g.AddNode(goraph.NewNode(device.Id))
+		(*devicesAdded)[device.Id] = device.Id
 	}
-	g.AddNode(goraph.NewNode(device.Id))
-	(*devicesAdded)[device.Id] = device.Id
 
 	var portId string
 	var peerPortId string
@@ -152,81 +263,201 @@
 	return g
 }
 
-func (dg *DeviceGraph) IsRootPort(port uint32) bool {
-	_, exist := dg.RootPorts[port]
+//portExist returns true if the port ID is already part of the boundary ports map.
+func (dg *DeviceGraph) portExist(id string) bool {
+	dg.boundaryPortsLock.RLock()
+	defer dg.boundaryPortsLock.RUnlock()
+	_, exist := dg.boundaryPorts[id]
 	return exist
 }
 
-func (dg *DeviceGraph) buildRoutes() map[OFPortLink][]RouteHop {
-	var pathIds []goraph.ID
-	path := make([]RouteHop, 0)
-	paths := make(map[OFPortLink][]RouteHop)
-	var err error
-	var hop RouteHop
-
-	dg.boundaryPorts.Range(func(src, srcPort interface{}) bool {
-		source := src.(string)
-		sourcePort := srcPort.(uint32)
-
-		dg.boundaryPorts.Range(func(dst, dstPort interface{}) bool {
-			target := dst.(string)
-			targetPort := dstPort.(uint32)
-
-			if source == target {
-				return true
+// buildPathsToAllRootPorts builds all the paths from the non-root logical port to all root ports
+// on the logical device
+func (dg *DeviceGraph) buildPathsToAllRootPorts(lp *voltha.LogicalPort) map[OFPortLink][]RouteHop {
+	paths := dg.Routes
+	source := concatDeviceIdPortId(lp.DeviceId, lp.DevicePortNo)
+	sourcePort := lp.OfpPort.PortNo
+	ch := make(chan *ofPortLinkToPath)
+	numBuildRequest := 0
+	for target, targetPort := range dg.rootPortsString {
+		go dg.buildRoute(source, target, sourcePort, targetPort, ch)
+		numBuildRequest += 1
+	}
+	responseReceived := 0
+forloop:
+	for {
+		if responseReceived == numBuildRequest {
+			break
+		}
+		select {
+		case res, ok := <-ch:
+			if !ok {
+				log.Debug("channel closed")
+				break forloop
 			}
-			//Ignore NNI - NNI Routes
-			if dg.IsRootPort(sourcePort) && dg.IsRootPort(targetPort) {
-				return true
+			if res != nil && len(res.path) > 0 {
+				paths[res.link] = res.path
+				paths[OFPortLink{Ingress: res.link.Egress, Egress: res.link.Ingress}] = getReverseRoute(res.path)
 			}
-
-			//Ignore UNI - UNI Routes
-			if !dg.IsRootPort(sourcePort) && !dg.IsRootPort(targetPort) {
-				return true
-			}
-
-			if pathIds, _, err = goraph.Dijkstra(dg.GGraph, goraph.StringID(source), goraph.StringID(target)); err != nil {
-				log.Errorw("no-path", log.Fields{"source": source, "target": target, "error": err})
-				return true
-			}
-			if len(pathIds)%3 != 0 {
-				return true
-			}
-			var deviceId string
-			var ingressPort uint32
-			var egressPort uint32
-			for i := 0; i < len(pathIds); i = i + 3 {
-				if deviceId, ingressPort, err = splitIntoDeviceIdPortId(pathIds[i].String()); err != nil {
-					log.Errorw("id-error", log.Fields{"source": source, "target": target, "error": err})
-					break
-				}
-				if _, egressPort, err = splitIntoDeviceIdPortId(pathIds[i+2].String()); err != nil {
-					log.Errorw("id-error", log.Fields{"source": source, "target": target, "error": err})
-					break
-				}
-				hop = RouteHop{Ingress: ingressPort, DeviceID: deviceId, Egress: egressPort}
-				path = append(path, hop)
-			}
-			tmp := make([]RouteHop, len(path))
-			copy(tmp, path)
-			path = nil
-			paths[OFPortLink{Ingress: sourcePort, Egress: targetPort}] = tmp
-			return true
-		})
-		return true
-	})
+		}
+		responseReceived += 1
+	}
 	return paths
 }
 
-func (dg *DeviceGraph) GetDeviceNodeIds() map[string]string {
-	dg.graphBuildLock.RLock()
-	defer dg.graphBuildLock.RUnlock()
-	nodeIds := make(map[string]string)
-	nodesMap := dg.GGraph.GetNodes()
-	for id, node := range nodesMap {
-		if len(strings.Split(node.String(), ":")) != 2 { // not port node
-			nodeIds[id.String()] = id.String()
+// buildPathsToAllNonRootPorts builds all the paths from the root logical port to all non-root ports
+// on the logical device
+func (dg *DeviceGraph) buildPathsToAllNonRootPorts(lp *voltha.LogicalPort) map[OFPortLink][]RouteHop {
+	paths := dg.Routes
+	source := concatDeviceIdPortId(lp.DeviceId, lp.DevicePortNo)
+	sourcePort := lp.OfpPort.PortNo
+	ch := make(chan *ofPortLinkToPath)
+	numBuildRequest := 0
+	for target, targetPort := range dg.nonRootPortsString {
+		go dg.buildRoute(source, target, sourcePort, targetPort, ch)
+		numBuildRequest += 1
+	}
+	responseReceived := 0
+forloop:
+	for {
+		if responseReceived == numBuildRequest {
+			break
+		}
+		select {
+		case res, ok := <-ch:
+			if !ok {
+				log.Debug("channel closed")
+				break forloop
+			}
+			if res != nil && len(res.path) > 0 {
+				paths[res.link] = res.path
+				paths[OFPortLink{Ingress: res.link.Egress, Egress: res.link.Ingress}] = getReverseRoute(res.path)
+			}
+		}
+		responseReceived += 1
+	}
+	return paths
+}
+
+//buildRoute builds a route between a source and a target logical port
+func (dg *DeviceGraph) buildRoute(sourceId, targetId string, sourcePort, targetPort uint32, ch chan *ofPortLinkToPath) {
+	var pathIds []goraph.ID
+	path := make([]RouteHop, 0)
+	var err error
+	var hop RouteHop
+	var result *ofPortLinkToPath
+
+	if sourceId == targetId {
+		ch <- result
+		return
+	}
+	//Ignore Root - Root Routes
+	if dg.IsRootPort(sourcePort) && dg.IsRootPort(targetPort) {
+		ch <- result
+		return
+	}
+
+	//Ignore non-Root - non-Root Routes
+	if !dg.IsRootPort(sourcePort) && !dg.IsRootPort(targetPort) {
+		ch <- result
+		return
+	}
+
+	if pathIds, _, err = goraph.Dijkstra(dg.GGraph, goraph.StringID(sourceId), goraph.StringID(targetId)); err != nil {
+		log.Errorw("no-path", log.Fields{"sourceId": sourceId, "targetId": targetId, "error": err})
+		ch <- result
+		return
+	}
+	if len(pathIds)%3 != 0 {
+		ch <- result
+		return
+	}
+	var deviceId string
+	var ingressPort uint32
+	var egressPort uint32
+	for i := 0; i < len(pathIds); i = i + 3 {
+		if deviceId, ingressPort, err = splitIntoDeviceIdPortId(pathIds[i].String()); err != nil {
+			log.Errorw("id-error", log.Fields{"sourceId": sourceId, "targetId": targetId, "error": err})
+			break
+		}
+		if _, egressPort, err = splitIntoDeviceIdPortId(pathIds[i+2].String()); err != nil {
+			log.Errorw("id-error", log.Fields{"sourceId": sourceId, "targetId": targetId, "error": err})
+			break
+		}
+		hop = RouteHop{Ingress: ingressPort, DeviceID: deviceId, Egress: egressPort}
+		path = append(path, hop)
+	}
+	result = &ofPortLinkToPath{link: OFPortLink{Ingress: sourcePort, Egress: targetPort}, path: path}
+	ch <- result
+}
+
+//buildRoutes build all routes between all the ports on the logical device
+func (dg *DeviceGraph) buildRoutes() map[OFPortLink][]RouteHop {
+	paths := make(map[OFPortLink][]RouteHop)
+	ch := make(chan *ofPortLinkToPath)
+	numBuildRequest := 0
+	for source, sourcePort := range dg.boundaryPorts {
+		for target, targetPort := range dg.boundaryPorts {
+			go dg.buildRoute(source, target, sourcePort, targetPort, ch)
+			numBuildRequest += 1
 		}
 	}
-	return nodeIds
+	responseReceived := 0
+forloop:
+	for {
+		if responseReceived == numBuildRequest {
+			break
+		}
+		select {
+		case res, ok := <-ch:
+			if !ok {
+				log.Debug("channel closed")
+				break forloop
+			}
+			if res != nil && len(res.path) > 0 {
+				paths[res.link] = res.path
+			}
+		}
+		responseReceived += 1
+	}
+	return paths
+}
+
+// reset cleans up the device graph
+func (dg *DeviceGraph) reset() {
+	dg.devicesAdded = make(map[string]string)
+	dg.portsAdded = make(map[string]string)
+	dg.rootPortsString = make(map[string]uint32)
+	dg.nonRootPortsString = make(map[string]uint32)
+	dg.RootPorts = make(map[uint32]uint32)
+	dg.boundaryPorts = make(map[string]uint32)
+	dg.Routes = make(map[OFPortLink][]RouteHop)
+	dg.cachedDevices = make(map[string]*voltha.Device)
+}
+
+//concatDeviceIdPortId formats a portid using the device id and the port number
+func concatDeviceIdPortId(deviceId string, portNo uint32) string {
+	return fmt.Sprintf("%s:%d", deviceId, portNo)
+}
+
+// splitIntoDeviceIdPortId extracts the device id and port number from the portId
+func splitIntoDeviceIdPortId(id string) (string, uint32, error) {
+	result := strings.Split(id, ":")
+	if len(result) != 2 {
+		return "", 0, errors.New(fmt.Sprintf("invalid-id-%s", id))
+	}
+	if temp, err := strconv.ParseInt(result[1], 10, 32); err != nil {
+		return "", 0, errors.New(fmt.Sprintf("invalid-id-%s-%s", id, err.Error()))
+	} else {
+		return result[0], uint32(temp), nil
+	}
+}
+
+//getReverseRoute returns the reverse of the route in param
+func getReverseRoute(route []RouteHop) []RouteHop {
+	reverse := make([]RouteHop, len(route))
+	for i, j := 0, len(route)-1; i < j; i, j = i+1, j-1 {
+		reverse[i], reverse[j] = route[j], route[i]
+	}
+	return reverse
 }
diff --git a/rw_core/graph/device_graph_test.go b/rw_core/graph/device_graph_test.go
index 09b39e0..9520819 100644
--- a/rw_core/graph/device_graph_test.go
+++ b/rw_core/graph/device_graph_test.go
@@ -21,6 +21,7 @@
 	"github.com/opencord/voltha-protos/go/openflow_13"
 	"github.com/opencord/voltha-protos/go/voltha"
 	"github.com/stretchr/testify/assert"
+	"sync"
 	"testing"
 	"time"
 )
@@ -29,16 +30,21 @@
 var olt voltha.Device
 var onusOnPort4 []voltha.Device
 var onusOnPort5 []voltha.Device
+var logicalDeviceId string
+var oltDeviceId string
+var numCalled int
+var lock sync.RWMutex
 
 const (
-	maxOnuOnPort4 int = 64
-	maxOnuOnPort5 int = 64
+	maxOnuOnPort4 int = 256
+	maxOnuOnPort5 int = 256
 )
 
 func init() {
 
-	logicalDeviceId := "ld"
-	oltDeviceId := "olt"
+	logicalDeviceId = "ld"
+	oltDeviceId = "olt"
+	lock = sync.RWMutex{}
 
 	// Setup ONUs on OLT port 4
 	onusOnPort4 = make([]voltha.Device, 0)
@@ -127,7 +133,7 @@
 	for i, onu := range onusOnPort5 {
 		for _, port := range onu.Ports {
 			if port.Type == voltha.Port_ETHERNET_UNI {
-				id = fmt.Sprintf("uni-%d", i+10)
+				id = fmt.Sprintf("uni-%d", i+len(onusOnPort4))
 				lp := voltha.LogicalPort{Id: id, DeviceId: onu.Id, DevicePortNo: port.PortNo, OfpPort: &openflow_13.OfpPort{PortNo: uint32(ofpPortNo)}, RootPort: false}
 				ld.Ports = append(ld.Ports, &lp)
 				ofpPortNo = ofpPortNo + 1
@@ -137,6 +143,9 @@
 }
 
 func GetDeviceHelper(id string) (*voltha.Device, error) {
+	lock.Lock()
+	numCalled += 1
+	lock.Unlock()
 	if id == "olt" {
 		return &olt, nil
 	}
@@ -153,19 +162,36 @@
 	return nil, errors.New("Not-found")
 }
 
-func TestGetRoutes(t *testing.T) {
+func TestGetRoutesOneShot(t *testing.T) {
 
 	getDevice := GetDeviceHelper
 
 	// Create a device graph and computes Routes
 	start := time.Now()
-	dg := NewDeviceGraph(getDevice)
+	dg := NewDeviceGraph(logicalDeviceId, getDevice)
+
 	dg.ComputeRoutes(ld.Ports)
-	fmt.Println("Total Time creating graph & compute Routes:", time.Since(start))
+	fmt.Println("Total num called:", numCalled)
+	fmt.Println("Total Time creating graph & compute Routes in one shot:", time.Since(start))
 	assert.NotNil(t, dg.GGraph)
 	assert.EqualValues(t, (maxOnuOnPort4*4 + maxOnuOnPort5*4), len(dg.Routes))
-	//for k, v := range dg.Routes {
-	//	fmt.Println("key", k, " value:", v)
-	//}
+	dg.Print()
+}
 
+func TestGetRoutesAddPort(t *testing.T) {
+
+	getDevice := GetDeviceHelper
+
+	// Create a device graph and computes Routes
+	start := time.Now()
+	dg := NewDeviceGraph(logicalDeviceId, getDevice)
+	for _, lp := range ld.Ports {
+		dg.AddPort(lp)
+	}
+
+	fmt.Println("Total num called:", numCalled)
+	fmt.Println("Total Time creating graph & compute Routes per port:", time.Since(start))
+	assert.NotNil(t, dg.GGraph)
+	assert.EqualValues(t, (maxOnuOnPort4*4 + maxOnuOnPort5*4), len(dg.Routes))
+	dg.Print()
 }