T3: Ping to same host behind two routers

Change-Id: Idb07b620587345c4ffefccc980e365606bbbffc0
diff --git a/apps/route-service/api/src/main/java/org/onosproject/routeservice/RouteService.java b/apps/route-service/api/src/main/java/org/onosproject/routeservice/RouteService.java
index c626e47..cacee10 100644
--- a/apps/route-service/api/src/main/java/org/onosproject/routeservice/RouteService.java
+++ b/apps/route-service/api/src/main/java/org/onosproject/routeservice/RouteService.java
@@ -17,6 +17,7 @@
 package org.onosproject.routeservice;
 
 import org.onlab.packet.IpAddress;
+import org.onlab.packet.IpPrefix;
 import org.onosproject.event.ListenerService;
 
 import java.util.Collection;
@@ -51,6 +52,15 @@
     Optional<ResolvedRoute> longestPrefixLookup(IpAddress ip);
 
     /**
+     * Returns all resolved routes stored for the given prefix, including the
+     * best selected route.
+     *
+     * @param prefix IP prefix to look up routes for
+     * @return all stored resolved routes for this prefix
+     */
+    Collection<ResolvedRoute> getAllResolvedRoutes(IpPrefix prefix);
+
+    /**
      * Performs a longest prefix match on the given IP address. The call will
      * return the route with the most specific prefix that contains the given
      * IP address.
diff --git a/apps/route-service/api/src/test/java/org/onosproject/routeservice/RouteServiceAdapter.java b/apps/route-service/api/src/test/java/org/onosproject/routeservice/RouteServiceAdapter.java
index 1d6ec19..5d41450 100644
--- a/apps/route-service/api/src/test/java/org/onosproject/routeservice/RouteServiceAdapter.java
+++ b/apps/route-service/api/src/test/java/org/onosproject/routeservice/RouteServiceAdapter.java
@@ -16,7 +16,9 @@
 
 package org.onosproject.routeservice;
 
+import com.google.common.collect.ImmutableList;
 import org.onlab.packet.IpAddress;
+import org.onlab.packet.IpPrefix;
 
 import java.util.Collection;
 import java.util.Optional;
@@ -56,6 +58,11 @@
     }
 
     @Override
+    public Collection<ResolvedRoute> getAllResolvedRoutes(IpPrefix prefix) {
+        return ImmutableList.of();
+    }
+
+    @Override
     public void addListener(RouteListener listener) {
 
     }
diff --git a/apps/route-service/app/src/main/java/org/onosproject/routeservice/impl/RouteManager.java b/apps/route-service/app/src/main/java/org/onosproject/routeservice/impl/RouteManager.java
index 8914a1e..eb73f69 100644
--- a/apps/route-service/app/src/main/java/org/onosproject/routeservice/impl/RouteManager.java
+++ b/apps/route-service/app/src/main/java/org/onosproject/routeservice/impl/RouteManager.java
@@ -16,6 +16,7 @@
 
 package org.onosproject.routeservice.impl;
 
+import com.google.common.collect.ImmutableList;
 import org.apache.felix.scr.annotations.Activate;
 import org.apache.felix.scr.annotations.Component;
 import org.apache.felix.scr.annotations.Deactivate;
@@ -208,6 +209,11 @@
     }
 
     @Override
+    public Collection<ResolvedRoute> getAllResolvedRoutes(IpPrefix prefix) {
+        return ImmutableList.copyOf(resolvedRouteStore.getAllRoutes(prefix));
+    }
+
+    @Override
     public void update(Collection<Route> routes) {
         synchronized (this) {
             routes.forEach(route -> {
diff --git a/apps/t3/BUCK b/apps/t3/BUCK
index 50905b2..f28792c 100644
--- a/apps/t3/BUCK
+++ b/apps/t3/BUCK
@@ -8,11 +8,13 @@
     '//cli:onos-cli',
     '//drivers/default:onos-drivers-default',
     '//apps/segmentrouting/app:onos-apps-segmentrouting-app',
+    '//apps/route-service/api:onos-apps-route-service-api',
 ]
 
 TEST_DEPS = [
     '//lib:TEST_ADAPTERS',
     '//utils/misc:onlab-misc',
+    '//apps/route-service/api:onos-apps-route-service-api-tests',
 ]
 
 osgi_jar_with_tests (
@@ -26,5 +28,5 @@
     url = 'https://wiki.opencord.org/pages/viewpage.action?pageId=4456974',
     description = 'Provides static analysis of flows and groups ' +
     'to determine the possible paths a packet may take.',
-    required_apps = [ 'org.onosproject.segmentrouting' ],
+    required_apps = [ 'org.onosproject.segmentrouting', 'org.onosproject.route-service' ],
 )
diff --git a/apps/t3/src/main/java/org/onosproject/t3/impl/TroubleshootManager.java b/apps/t3/src/main/java/org/onosproject/t3/impl/TroubleshootManager.java
index b891c1b..f9d1b2a 100644
--- a/apps/t3/src/main/java/org/onosproject/t3/impl/TroubleshootManager.java
+++ b/apps/t3/src/main/java/org/onosproject/t3/impl/TroubleshootManager.java
@@ -67,6 +67,8 @@
 import org.onosproject.net.host.InterfaceIpAddress;
 import org.onosproject.net.intf.Interface;
 import org.onosproject.net.link.LinkService;
+import org.onosproject.routeservice.ResolvedRoute;
+import org.onosproject.routeservice.RouteService;
 import org.onosproject.segmentrouting.config.SegmentRoutingDeviceConfig;
 import org.onosproject.t3.api.GroupsInDevice;
 import org.onosproject.t3.api.StaticPacketTrace;
@@ -80,6 +82,7 @@
 import java.util.Comparator;
 import java.util.HashSet;
 import java.util.List;
+import java.util.Optional;
 import java.util.Set;
 import java.util.stream.Collectors;
 
@@ -133,6 +136,9 @@
     @Reference(cardinality = ReferenceCardinality.MANDATORY_UNARY)
     protected EdgePortService edgePortService;
 
+    @Reference(cardinality = ReferenceCardinality.MANDATORY_UNARY)
+    protected RouteService routeService;
+
     @Override
     public List<StaticPacketTrace> pingAll(EtherType type) {
         ImmutableList.Builder<StaticPacketTrace> tracesBuilder = ImmutableList.builder();
@@ -404,6 +410,7 @@
             ConnectPoint cp = outputPath.getOutput();
             log.debug("Connect point in {}", in);
             log.debug("Output path {}", cp);
+            log.debug("{}", outputPath.getFinalPacket());
 
             //Hosts for the the given output
             Set<Host> hostsList = hostService.getConnectedHosts(cp);
@@ -497,38 +504,40 @@
                 //We treat as correct output only if it's not LLDP or BDDP
                 if (!(ethTypeCriterion.ethType().equals(EtherType.LLDP.ethType())
                         && !ethTypeCriterion.ethType().equals(EtherType.BDDP.ethType()))) {
-                    if (hostsList.isEmpty()) {
-                        trace.addResultMessage("Packet is " + ((EthTypeCriterion) outputPath.getFinalPacket()
-                                .getCriterion(Criterion.Type.ETH_TYPE)).ethType() + " and reached " +
-                                cp + " with no hosts connected ");
-                    } else {
-                        IpAddress ipAddress = null;
-                        if (trace.getInitialPacket().getCriterion(Criterion.Type.IPV4_DST) != null) {
-                            ipAddress = ((IPCriterion) trace.getInitialPacket()
-                                    .getCriterion(Criterion.Type.IPV4_DST)).ip().address();
-                        } else if (trace.getInitialPacket().getCriterion(Criterion.Type.IPV6_DST) != null) {
-                            ipAddress = ((IPCriterion) trace.getInitialPacket()
-                                    .getCriterion(Criterion.Type.IPV6_DST)).ip().address();
-                        }
-                        if (ipAddress != null) {
-                            IpAddress finalIpAddress = ipAddress;
-                            if (hostsList.stream().anyMatch(host -> host.ipAddresses().contains(finalIpAddress)) ||
-                            hostService.getHostsByIp(finalIpAddress).isEmpty()) {
+                    if (computePath(completePath, trace, outputPath.getOutput())) {
+                        if (hostsList.isEmpty()) {
+                            trace.addResultMessage("Packet is " + ((EthTypeCriterion) outputPath.getFinalPacket()
+                                    .getCriterion(Criterion.Type.ETH_TYPE)).ethType() + " and reached " +
+                                    cp + " with no hosts connected ");
+                        } else {
+                            IpAddress ipAddress = null;
+                            if (trace.getInitialPacket().getCriterion(Criterion.Type.IPV4_DST) != null) {
+                                ipAddress = ((IPCriterion) trace.getInitialPacket()
+                                        .getCriterion(Criterion.Type.IPV4_DST)).ip().address();
+                            } else if (trace.getInitialPacket().getCriterion(Criterion.Type.IPV6_DST) != null) {
+                                ipAddress = ((IPCriterion) trace.getInitialPacket()
+                                        .getCriterion(Criterion.Type.IPV6_DST)).ip().address();
+                            }
+                            if (ipAddress != null) {
+                                IpAddress finalIpAddress = ipAddress;
+                                if (hostsList.stream().anyMatch(host -> host.ipAddresses().contains(finalIpAddress)) ||
+                                        hostService.getHostsByIp(finalIpAddress).isEmpty()) {
+                                    trace.addResultMessage("Packet is " +
+                                            ((EthTypeCriterion) outputPath.getFinalPacket()
+                                            .getCriterion(Criterion.Type.ETH_TYPE)).ethType() + " and reached " +
+                                            cp + " with hosts " + hostsList);
+                                } else {
+                                    trace.addResultMessage("Wrong output " + cp + " for required destination ip " +
+                                            ipAddress);
+                                }
+                            } else {
                                 trace.addResultMessage("Packet is " + ((EthTypeCriterion) outputPath.getFinalPacket()
                                         .getCriterion(Criterion.Type.ETH_TYPE)).ethType() + " and reached " +
                                         cp + " with hosts " + hostsList);
-                            } else {
-                                trace.addResultMessage("Wrong output " + cp + " for required destination ip " +
-                                        ipAddress);
                             }
-                        } else {
-                            trace.addResultMessage("Packet is " + ((EthTypeCriterion) outputPath.getFinalPacket()
-                                    .getCriterion(Criterion.Type.ETH_TYPE)).ethType() + " and reached " +
-                                    cp + " with hosts " + hostsList);
                         }
+                        trace.setSuccess(true);
                     }
-                    trace.setSuccess(true);
-                    computePath(completePath, trace, outputPath.getOutput());
                 }
 
             } else {
@@ -661,10 +670,15 @@
     private StaticPacketTrace traceInDevice(StaticPacketTrace trace, TrafficSelector packet, ConnectPoint in,
                                             boolean isDualHomed) {
 
-        if (trace.getGroupOuputs(in.deviceId()) != null && !isDualHomed) {
+        boolean multipleRoutes = false;
+        if (trace.getGroupOuputs(in.deviceId()) != null) {
+            multipleRoutes = multipleRoutes(trace);
+        }
+        if (trace.getGroupOuputs(in.deviceId()) != null && !isDualHomed && !multipleRoutes) {
             log.debug("Trace already contains device and given outputs");
             return trace;
         }
+
         log.debug("Packet {} coming in from {}", packet, in);
 
         //if device is not available exit here.
@@ -686,7 +700,6 @@
 
         List<FlowEntry> flows = new ArrayList<>();
         List<FlowEntry> outputFlows = new ArrayList<>();
-
         List<Instruction> deferredInstructions = new ArrayList<>();
 
         FlowEntry nextTableIdEntry = findNextTableIdEntry(in.deviceId(), -1);
@@ -810,7 +823,35 @@
         trace.addFlowsForDevice(in.deviceId(), ImmutableList.copyOf(flows));
 
         List<PortNumber> outputPorts = new ArrayList<>();
+        List<FlowEntry> outputFlowEntries = handleFlows(trace, packet, in, outputFlows, builder, outputPorts);
 
+
+        log.debug("Handling Groups");
+        //Analyze Groups
+        List<Group> groups = new ArrayList<>();
+
+        Collection<FlowEntry> nonOutputFlows = flows;
+        nonOutputFlows.removeAll(outputFlowEntries);
+
+        //Handling groups pointed at by immediate instructions
+        for (FlowEntry entry : flows) {
+            getGroupsFromInstructions(trace, groups, entry.treatment().immediate(),
+                    entry.deviceId(), builder, outputPorts, in);
+        }
+
+        //If we have deferred instructions at this point we handle them.
+        if (deferredInstructions.size() > 0) {
+            builder = handleDeferredActions(trace, packet, in, deferredInstructions, outputPorts, groups);
+
+        }
+        packet = builder.build();
+
+        log.debug("Output Packet {}", packet);
+        return trace;
+    }
+
+    private List<FlowEntry> handleFlows(StaticPacketTrace trace, TrafficSelector packet, ConnectPoint in,
+                                        List<FlowEntry> outputFlows, Builder builder, List<PortNumber> outputPorts) {
         //TODO optimization
         //outputFlows contains also last rule of device, so we need filtering for OUTPUT instructions.
         List<FlowEntry> outputFlowEntries = outputFlows.stream().filter(flow -> flow.treatment()
@@ -834,28 +875,26 @@
             buildOutputFromDevice(trace, in, builder, outputPorts, outputInstruction, ImmutableList.of());
 
         }
-        log.debug("Handling Groups");
-        //Analyze Groups
-        List<Group> groups = new ArrayList<>();
+        return outputFlowEntries;
+    }
 
-        Collection<FlowEntry> nonOutputFlows = flows;
-        nonOutputFlows.removeAll(outputFlowEntries);
-
-        //Handling groups pointed at by immediate instructions
-        for (FlowEntry entry : flows) {
-            getGroupsFromInstructions(trace, groups, entry.treatment().immediate(),
-                    entry.deviceId(), builder, outputPorts, in);
+    private boolean multipleRoutes(StaticPacketTrace trace) {
+        boolean multipleRoutes = false;
+        IPCriterion ipCriterion = ((IPCriterion) trace.getInitialPacket().getCriterion(Criterion.Type.IPV4_DST));
+        IpAddress ip = null;
+        if (ipCriterion != null) {
+            ip = ipCriterion.ip().address();
+        } else if (trace.getInitialPacket().getCriterion(Criterion.Type.IPV6_DST) != null) {
+            ip = ((IPCriterion) trace.getInitialPacket().getCriterion(Criterion.Type.IPV6_DST)).ip().address();
         }
 
-        //If we have deferred instructions at this point we handle them.
-        if (deferredInstructions.size() > 0) {
-            builder = handleDeferredActions(trace, packet, in, deferredInstructions, outputPorts, groups);
-
+        Optional<ResolvedRoute> optionalRoute = routeService.longestPrefixLookup(ip);
+        if (ip != null && optionalRoute.isPresent()) {
+            ResolvedRoute route = optionalRoute.get();
+            route.prefix();
+            multipleRoutes = routeService.getAllResolvedRoutes(route.prefix()).size() > 1;
         }
-        packet = builder.build();
-
-        log.debug("Output Packet {}", packet);
-        return trace;
+        return multipleRoutes;
     }
 
     /**
diff --git a/apps/t3/src/test/java/org/onosproject/t3/impl/TroubleshootManagerTest.java b/apps/t3/src/test/java/org/onosproject/t3/impl/TroubleshootManagerTest.java
index bbf9fd5..12c2321 100644
--- a/apps/t3/src/test/java/org/onosproject/t3/impl/TroubleshootManagerTest.java
+++ b/apps/t3/src/test/java/org/onosproject/t3/impl/TroubleshootManagerTest.java
@@ -53,10 +53,13 @@
 import org.onosproject.net.host.HostServiceAdapter;
 import org.onosproject.net.link.LinkServiceAdapter;
 import org.onosproject.net.provider.ProviderId;
+import org.onosproject.routeservice.ResolvedRoute;
+import org.onosproject.routeservice.RouteServiceAdapter;
 import org.onosproject.t3.api.StaticPacketTrace;
 import org.slf4j.Logger;
 
 import java.util.HashMap;
+import java.util.Optional;
 import java.util.Set;
 
 import static org.junit.Assert.assertEquals;
@@ -88,6 +91,7 @@
         mngr.deviceService = new TestDeviceService();
         mngr.mastershipService = new TestMastershipService();
         mngr.edgePortService = new TestEdgePortService();
+        mngr.routeService = new TestRouteService();
 
         assertNotNull("Manager should not be null", mngr);
 
@@ -649,6 +653,13 @@
         }
     }
 
+    private class TestRouteService extends RouteServiceAdapter {
+        @Override
+        public Optional<ResolvedRoute> longestPrefixLookup(IpAddress ip) {
+            return Optional.empty();
+        }
+    }
+
     private class TestMastershipService extends MastershipServiceAdapter {
         @Override
         public NodeId getMasterFor(DeviceId deviceId) {