[VOL-1035] Initial submission of flow decomposition code.
Additional test cases will follow to test the core of the flow
decomposition functionality
Change-Id: Ie685714ce5ab54ac89501a67f9489613de195c15
diff --git a/rw_core/graph/device_graph.go b/rw_core/graph/device_graph.go
new file mode 100644
index 0000000..9acda6d
--- /dev/null
+++ b/rw_core/graph/device_graph.go
@@ -0,0 +1,208 @@
+/*
+ * Copyright 2018-present Open Networking Foundation
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package graph
+
+import (
+ "errors"
+ "fmt"
+ "github.com/gyuho/goraph"
+ "github.com/opencord/voltha-go/common/log"
+ "github.com/opencord/voltha-go/protos/voltha"
+ "strconv"
+ "strings"
+)
+
+func init() {
+ log.AddPackage(log.JSON, log.DebugLevel, nil)
+}
+
+type RouteHop struct {
+ DeviceID string
+ Ingress uint32
+ Egress uint32
+}
+
+type OFPortLink struct {
+ Ingress uint32
+ Egress uint32
+}
+
+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
+ boundaryPorts map[string]uint32
+}
+
+func NewDeviceGraph(getDevice GetDeviceFunc) *DeviceGraph {
+ var dg DeviceGraph
+ dg.GGraph = goraph.NewGraph()
+ dg.getDevice = getDevice
+ return &dg
+}
+
+func (dg *DeviceGraph) ComputeRoutes(lps []*voltha.LogicalPort) {
+ 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 = make(map[string]uint32)
+ for _, lp := range lps {
+ dg.boundaryPorts[fmt.Sprintf("%s:%d", lp.DeviceId, lp.DevicePortNo)] = 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.Routes = dg.buildRoutes()
+}
+
+func (dg *DeviceGraph) addDevice(device *voltha.Device, g goraph.Graph, devicesAdded *map[string]string, portsAdded *map[string]string,
+ boundaryPorts map[string]uint32) goraph.Graph {
+
+ if device == nil {
+ return g
+ }
+
+ if _, exist := (*devicesAdded)[device.Id]; exist {
+ return g
+ }
+ g.AddNode(goraph.NewNode(device.Id))
+ (*devicesAdded)[device.Id] = device.Id
+
+ var portId string
+ var peerPortId string
+ for _, port := range device.Ports {
+ portId = concatDeviceIdPortId(device.Id, port.PortNo)
+ if _, exist := (*portsAdded)[portId]; !exist {
+ (*portsAdded)[portId] = portId
+ g.AddNode(goraph.NewNode(portId))
+ g.AddEdge(goraph.StringID(device.Id), goraph.StringID(portId), 1)
+ g.AddEdge(goraph.StringID(portId), goraph.StringID(device.Id), 1)
+ }
+ for _, peer := range port.Peers {
+ if _, exist := (*devicesAdded)[peer.DeviceId]; !exist {
+ d, _ := dg.getDevice(peer.DeviceId)
+ g = dg.addDevice(d, g, devicesAdded, portsAdded, boundaryPorts)
+ } else {
+ peerPortId = concatDeviceIdPortId(peer.DeviceId, peer.PortNo)
+ g.AddEdge(goraph.StringID(portId), goraph.StringID(peerPortId), 1)
+ g.AddEdge(goraph.StringID(peerPortId), goraph.StringID(portId), 1)
+ }
+ }
+ }
+ return g
+}
+
+func (dg *DeviceGraph) IsRootPort(port uint32) bool {
+ _, exist := dg.RootPorts[port]
+ 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
+ for source, sourcePort := range dg.boundaryPorts {
+ for target, targetPort := range dg.boundaryPorts {
+ if source == target {
+ continue
+ }
+ //Ignore NNI - NNI Routes
+ if dg.IsRootPort(sourcePort) && dg.IsRootPort(targetPort) {
+ continue
+ }
+
+ //Ignore UNI - UNI Routes
+ if !dg.IsRootPort(sourcePort) && !dg.IsRootPort(targetPort) {
+ continue
+ }
+
+ 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})
+ continue
+ }
+ if len(pathIds)%3 != 0 {
+ continue
+ }
+ 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 paths
+}
+
+func (dg *DeviceGraph) GetDeviceNodeIds() map[string]string {
+ 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
+}
diff --git a/rw_core/graph/device_graph_test.go b/rw_core/graph/device_graph_test.go
new file mode 100644
index 0000000..533d03d
--- /dev/null
+++ b/rw_core/graph/device_graph_test.go
@@ -0,0 +1,171 @@
+/*
+ * Copyright 2018-present Open Networking Foundation
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package graph
+
+import (
+ "errors"
+ "fmt"
+ "github.com/opencord/voltha-go/protos/openflow_13"
+ "github.com/opencord/voltha-go/protos/voltha"
+ "github.com/stretchr/testify/assert"
+ "testing"
+ "time"
+)
+
+var ld voltha.LogicalDevice
+var olt voltha.Device
+var onusOnPort4 []voltha.Device
+var onusOnPort5 []voltha.Device
+
+const (
+ maxOnuOnPort4 int = 64
+ maxOnuOnPort5 int = 64
+)
+
+func init() {
+
+ logicalDeviceId := "ld"
+ oltDeviceId := "olt"
+
+ // Setup ONUs on OLT port 4
+ onusOnPort4 = make([]voltha.Device, 0)
+ var onu voltha.Device
+ var id string
+ oltPeerPort := uint32(4)
+ for i := 0; i < maxOnuOnPort4; i++ {
+ id := fmt.Sprintf("onu%d", i)
+ onu = voltha.Device{Id: id, ParentId: oltDeviceId}
+ ponPort := voltha.Port{PortNo: 1, DeviceId: onu.Id, Type: voltha.Port_PON_ONU}
+ ponPort.Peers = make([]*voltha.Port_PeerPort, 0)
+ peerPort := voltha.Port_PeerPort{DeviceId: oltDeviceId, PortNo: oltPeerPort}
+ ponPort.Peers = append(ponPort.Peers, &peerPort)
+ uniPort := voltha.Port{PortNo: 2, DeviceId: onu.Id, Type: voltha.Port_ETHERNET_UNI}
+ onu.Ports = make([]*voltha.Port, 0)
+ onu.Ports = append(onu.Ports, &ponPort)
+ onu.Ports = append(onu.Ports, &uniPort)
+ onusOnPort4 = append(onusOnPort4, onu)
+ }
+
+ // Setup ONUs on OLT port 5
+ onusOnPort5 = make([]voltha.Device, 0)
+ oltPeerPort = uint32(5)
+ for i := 0; i < maxOnuOnPort5; i++ {
+ id := fmt.Sprintf("onu%d", i+maxOnuOnPort4)
+ onu = voltha.Device{Id: id, ParentId: oltDeviceId}
+ ponPort := voltha.Port{PortNo: 1, DeviceId: onu.Id, Type: voltha.Port_PON_ONU}
+ ponPort.Peers = make([]*voltha.Port_PeerPort, 0)
+ peerPort := voltha.Port_PeerPort{DeviceId: oltDeviceId, PortNo: oltPeerPort}
+ ponPort.Peers = append(ponPort.Peers, &peerPort)
+ uniPort := voltha.Port{PortNo: 2, DeviceId: onu.Id, Type: voltha.Port_ETHERNET_UNI}
+ onu.Ports = make([]*voltha.Port, 0)
+ onu.Ports = append(onu.Ports, &ponPort)
+ onu.Ports = append(onu.Ports, &uniPort)
+ onusOnPort5 = append(onusOnPort5, onu)
+ }
+
+ // Setup OLT
+ // Setup the OLT device
+ olt = voltha.Device{Id: oltDeviceId, ParentId: logicalDeviceId}
+ p1 := voltha.Port{PortNo: 2, DeviceId: oltDeviceId, Type: voltha.Port_ETHERNET_NNI}
+ p2 := voltha.Port{PortNo: 3, DeviceId: oltDeviceId, Type: voltha.Port_ETHERNET_NNI}
+ p3 := voltha.Port{PortNo: 4, DeviceId: oltDeviceId, Type: voltha.Port_PON_OLT}
+ p4 := voltha.Port{PortNo: 5, DeviceId: oltDeviceId, Type: voltha.Port_PON_OLT}
+ p3.Peers = make([]*voltha.Port_PeerPort, 0)
+ for _, onu := range onusOnPort4 {
+ peerPort := voltha.Port_PeerPort{DeviceId: onu.Id, PortNo: p3.PortNo}
+ p3.Peers = append(p3.Peers, &peerPort)
+ }
+ p4.Peers = make([]*voltha.Port_PeerPort, 0)
+ for _, onu := range onusOnPort5 {
+ peerPort := voltha.Port_PeerPort{DeviceId: onu.Id, PortNo: p4.PortNo}
+ p4.Peers = append(p4.Peers, &peerPort)
+ }
+ olt.Ports = make([]*voltha.Port, 0)
+ olt.Ports = append(olt.Ports, &p1)
+ olt.Ports = append(olt.Ports, &p2)
+ olt.Ports = append(olt.Ports, &p3)
+ olt.Ports = append(olt.Ports, &p4)
+
+ // Setup the logical device
+ ld = voltha.LogicalDevice{Id: logicalDeviceId}
+ ld.Ports = make([]*voltha.LogicalPort, 0)
+ ofpPortNo := 1
+ //Add olt ports
+ for i, port := range olt.Ports {
+ if port.Type == voltha.Port_ETHERNET_NNI {
+ id = fmt.Sprintf("nni-%d", i)
+ lp := voltha.LogicalPort{Id: id, DeviceId: olt.Id, DevicePortNo: port.PortNo, OfpPort: &openflow_13.OfpPort{PortNo: uint32(ofpPortNo)}, RootPort: true}
+ ld.Ports = append(ld.Ports, &lp)
+ ofpPortNo = ofpPortNo + 1
+ }
+ }
+ //Add onu ports on port 4
+ for i, onu := range onusOnPort4 {
+ for _, port := range onu.Ports {
+ if port.Type == voltha.Port_ETHERNET_UNI {
+ id = fmt.Sprintf("uni-%d", i)
+ 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
+ }
+ }
+ }
+ //Add onu ports on port 5
+ for i, onu := range onusOnPort5 {
+ for _, port := range onu.Ports {
+ if port.Type == voltha.Port_ETHERNET_UNI {
+ id = fmt.Sprintf("uni-%d", i+10)
+ 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
+ }
+ }
+ }
+}
+
+func GetDeviceHelper(id string) (*voltha.Device, error) {
+ if id == "olt" {
+ return &olt, nil
+ }
+ for _, onu := range onusOnPort4 {
+ if onu.Id == id {
+ return &onu, nil
+ }
+ }
+ for _, onu := range onusOnPort5 {
+ if onu.Id == id {
+ return &onu, nil
+ }
+ }
+ return nil, errors.New("Not-found")
+}
+
+func TestGetRoutes(t *testing.T) {
+
+ getDevice := GetDeviceHelper
+
+ // Create a device graph and computes Routes
+ start := time.Now()
+ dg := NewDeviceGraph(getDevice)
+ dg.ComputeRoutes(ld.Ports)
+ fmt.Println("Total Time creating graph & compute Routes:", 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)
+ //}
+
+}