diff --git a/core/net/src/main/java/org/onosproject/net/intent/impl/compiler/PathCompiler.java b/core/net/src/main/java/org/onosproject/net/intent/impl/compiler/PathCompiler.java
index 3f8bba4..3994b90 100644
--- a/core/net/src/main/java/org/onosproject/net/intent/impl/compiler/PathCompiler.java
+++ b/core/net/src/main/java/org/onosproject/net/intent/impl/compiler/PathCompiler.java
@@ -16,7 +16,9 @@
 package org.onosproject.net.intent.impl.compiler;
 
 import com.google.common.collect.ImmutableList;
+import com.google.common.collect.Iterables;
 import com.google.common.collect.Sets;
+import org.apache.commons.lang.math.RandomUtils;
 import org.onlab.packet.EthType;
 import org.onlab.packet.Ethernet;
 import org.onlab.packet.MplsLabel;
@@ -62,6 +64,8 @@
 
 public class PathCompiler<T> {
 
+    public static final boolean RANDOM_SELECTION = true;
+
     /**
      * Defines methods used to create objects representing flows.
      */
@@ -120,6 +124,44 @@
         return vlanIds;
     }
 
+    /**
+     * Implements the first fit selection behavior.
+     *
+     * @param available the set of available VLAN ids.
+     * @return the chosen VLAN id.
+     */
+    private VlanId firsFitSelection(Set<VlanId> available) {
+        if (!available.isEmpty()) {
+            return available.iterator().next();
+        }
+        return VlanId.vlanId(VlanId.NO_VID);
+    }
+
+    /**
+     * Implements the random selection behavior.
+     *
+     * @param available the set of available VLAN ids.
+     * @return the chosen VLAN id.
+     */
+    private VlanId randomSelection(Set<VlanId> available) {
+        if (!available.isEmpty()) {
+            int size = available.size();
+            int index = RandomUtils.nextInt(size);
+            return Iterables.get(available, index);
+        }
+        return VlanId.vlanId(VlanId.NO_VID);
+    }
+
+    /**
+    * Select a VLAN id from the set of available VLAN ids.
+    *
+    * @param available the set of available VLAN ids.
+    * @return the chosen VLAN id.
+    */
+    private VlanId selectVlanId(Set<VlanId> available) {
+        return RANDOM_SELECTION ? randomSelection(available) : firsFitSelection(available);
+    }
+
     private Map<LinkKey, VlanId> findVlanIds(PathCompilerCreateFlow creator, Set<LinkKey> links) {
         Map<LinkKey, VlanId> vlanIds = new HashMap<>();
         for (LinkKey link : links) {
@@ -129,7 +171,11 @@
             if (common.isEmpty()) {
                 continue;
             }
-            vlanIds.put(link, common.iterator().next());
+            VlanId selected = selectVlanId(common);
+            if (selected.toShort() == VlanId.NO_VID) {
+                continue;
+            }
+            vlanIds.put(link, selected);
         }
         return vlanIds;
     }
@@ -185,7 +231,6 @@
                 if (egressVlanId == null) {
                     throw new IntentCompilationException("No available VLAN ID for " + link);
                 }
-                prevVlanId = egressVlanId;
 
                 TrafficSelector transitSelector = DefaultTrafficSelector.builder()
                         .matchInPort(prev.port())
@@ -200,6 +245,11 @@
                 creator.createFlow(transitSelector,
                                    transitTreat.build(), prev, link.src(),
                                    intent.priority(), true, flows, devices);
+                /* For the next hop we have to remember
+                 * the previous egress VLAN id and the egress
+                 * node
+                 */
+                prevVlanId = egressVlanId;
                 prev = link.dst();
             } else {
                 // Egress traffic
diff --git a/core/net/src/test/java/org/onosproject/net/intent/impl/compiler/MockResourceService.java b/core/net/src/test/java/org/onosproject/net/intent/impl/compiler/MockResourceService.java
index 18ba79e..9da412e 100644
--- a/core/net/src/test/java/org/onosproject/net/intent/impl/compiler/MockResourceService.java
+++ b/core/net/src/test/java/org/onosproject/net/intent/impl/compiler/MockResourceService.java
@@ -106,10 +106,25 @@
                 .collect(Collectors.toList());
     }
 
+
+    /**
+     * It adds a number of VLAN ids in order to test the random behavior.
+     *
+     * @param parent the parent resource
+     * @return a set of VLAN ids
+     */
+    private Collection<Resource> addVlanIds(DiscreteResourceId parent) {
+        Collection<Resource> resources = new HashSet<>();
+        for (int i = VlanId.NO_VID + 1; i < VlanId.MAX_VLAN; i++) {
+            resources.add(Resources.discrete(parent).resource().child(VlanId.vlanId((short) i)));
+        }
+        return resources;
+    }
+
     @Override
     public Set<Resource> getAvailableResources(DiscreteResourceId parent) {
         Collection<Resource> resources = new HashSet<>();
-        resources.add(Resources.discrete(parent).resource().child(VlanId.vlanId((short) 10)));
+        resources.addAll(addVlanIds(parent));
         resources.add(Resources.discrete(parent).resource().child(MplsLabel.mplsLabel(10)));
         resources.add(Resources.discrete(parent).resource().child(TributarySlot.of(1)));
         resources.add(Resources.discrete(parent).resource().child(TributarySlot.of(2)));
diff --git a/core/net/src/test/java/org/onosproject/net/intent/impl/compiler/PathIntentCompilerTest.java b/core/net/src/test/java/org/onosproject/net/intent/impl/compiler/PathIntentCompilerTest.java
index ae7859c..67852a5 100644
--- a/core/net/src/test/java/org/onosproject/net/intent/impl/compiler/PathIntentCompilerTest.java
+++ b/core/net/src/test/java/org/onosproject/net/intent/impl/compiler/PathIntentCompilerTest.java
@@ -61,7 +61,10 @@
 import static org.hamcrest.MatcherAssert.assertThat;
 import static org.hamcrest.Matchers.hasSize;
 import static org.hamcrest.Matchers.is;
+import static org.hamcrest.Matchers.lessThan;
 import static org.hamcrest.number.OrderingComparison.greaterThan;
+import static org.junit.Assert.assertNotEquals;
+import static org.junit.Assert.assertTrue;
 import static org.onosproject.net.DefaultEdgeLink.createEdgeLink;
 import static org.onosproject.net.Link.Type.DIRECT;
 import static org.onosproject.net.NetTestTools.APP_ID;
@@ -257,7 +260,7 @@
                 .get();
         verifyIdAndPriority(rule2, d2p0.deviceId());
         verifyVlanEncapSelector(rule2.selector(), d2p0, vlanToEncap);
-        verifyVlanEncapTreatment(rule2.treatment(), d2p1, false, false);
+        vlanToEncap = verifyVlanEncapTreatment(rule2.treatment(), d2p1, false, false);
 
         FlowRule rule3 = rules.stream()
                 .filter(x -> x.deviceId().equals(d3p0.deviceId()))
@@ -300,7 +303,7 @@
                 .get();
         verifyIdAndPriority(rule2, d2p0.deviceId());
         verifyVlanEncapSelector(rule2.selector(), d2p0, vlanToEncap);
-        verifyVlanEncapTreatment(rule2.treatment(), d2p1, false, false);
+        vlanToEncap = verifyVlanEncapTreatment(rule2.treatment(), d2p1, false, false);
 
         FlowRule rule3 = rules.stream()
                 .filter(x -> x.deviceId().equals(d3p0.deviceId()))
@@ -323,6 +326,66 @@
         sut.deactivate();
     }
 
+    /**
+     * Tests the random selection of VlanIds in the PathCompiler.
+     * It can fail randomly (it is unlikely)
+     */
+    @Test
+    public void testRandomVlanSelection() {
+
+        if (PathCompiler.RANDOM_SELECTION) {
+
+            sut.activate();
+
+            List<Intent> compiled = sut.compile(constraintVlanIntent, Collections.emptyList());
+            assertThat(compiled, hasSize(1));
+
+            Collection<FlowRule> rules = ((FlowRuleIntent) compiled.get(0)).flowRules();
+            assertThat(rules, hasSize(3));
+
+            FlowRule rule1 = rules.stream()
+                    .filter(x -> x.deviceId().equals(d1p0.deviceId()))
+                    .findFirst()
+                    .get();
+            verifyIdAndPriority(rule1, d1p0.deviceId());
+            assertThat(rule1.selector(), is(DefaultTrafficSelector.builder(selector)
+                    .matchInPort(d1p0.port()).build()));
+
+            VlanId vlanToEncap = verifyVlanEncapTreatment(rule1.treatment(), d1p1, true, false);
+
+            assertTrue(VlanId.NO_VID < vlanToEncap.toShort() && vlanToEncap.toShort() < VlanId.MAX_VLAN);
+
+            /**
+             * This second part is meant to test if the random selection is working properly.
+             * We are compiling the same intent in order to verify if the VLAN ID is different
+             * from the previous one.
+             */
+
+            List<Intent> compiled2 = sut.compile(constraintVlanIntent, Collections.emptyList());
+            assertThat(compiled2, hasSize(1));
+
+            Collection<FlowRule> rules2 = ((FlowRuleIntent) compiled2.get(0)).flowRules();
+            assertThat(rules2, hasSize(3));
+
+            FlowRule rule2 = rules2.stream()
+                    .filter(x -> x.deviceId().equals(d1p0.deviceId()))
+                    .findFirst()
+                    .get();
+            verifyIdAndPriority(rule2, d1p0.deviceId());
+            assertThat(rule2.selector(), is(DefaultTrafficSelector.builder(selector)
+                    .matchInPort(d1p0.port()).build()));
+
+            VlanId vlanToEncap2 = verifyVlanEncapTreatment(rule2.treatment(), d1p1, true, false);
+
+            assertTrue(VlanId.NO_VID < vlanToEncap2.toShort() && vlanToEncap2.toShort() < VlanId.MAX_VLAN);
+            assertNotEquals(vlanToEncap, vlanToEncap2);
+
+            sut.deactivate();
+
+        }
+
+    }
+
     private VlanId verifyVlanEncapTreatment(TrafficTreatment trafficTreatment,
                                         ConnectPoint egress, boolean isIngress, boolean isEgress) {
         Set<Instructions.OutputInstruction> ruleOutput = trafficTreatment.allInstructions().stream()
@@ -339,12 +402,21 @@
                     .collect(Collectors.toSet());
             assertThat(vlanRules, hasSize(1));
             L2ModificationInstruction.ModVlanIdInstruction vlanRule = vlanRules.iterator().next();
-            assertThat(vlanRule.vlanId().toShort(), greaterThan((short) 0));
+            assertThat(vlanRule.vlanId().toShort(), greaterThan((short) VlanId.NO_VID));
+            assertThat(vlanRule.vlanId().toShort(), lessThan((short) VlanId.MAX_VLAN));
             vlanToEncap = vlanRule.vlanId();
         } else if (!isIngress && !isEgress) {
-            assertThat(trafficTreatment.allInstructions().stream()
-                               .filter(treat -> treat instanceof L2ModificationInstruction.ModVlanIdInstruction)
-                               .collect(Collectors.toSet()), hasSize(0));
+
+            Set<L2ModificationInstruction.ModVlanIdInstruction> vlanRules = trafficTreatment.allInstructions().stream()
+                    .filter(treat -> treat instanceof L2ModificationInstruction.ModVlanIdInstruction)
+                    .map(x -> (L2ModificationInstruction.ModVlanIdInstruction) x)
+                    .collect(Collectors.toSet());
+            assertThat(vlanRules, hasSize(1));
+            L2ModificationInstruction.ModVlanIdInstruction vlanRule = vlanRules.iterator().next();
+            assertThat(vlanRule.vlanId().toShort(), greaterThan((short) VlanId.NO_VID));
+            assertThat(vlanRule.vlanId().toShort(), lessThan((short) VlanId.MAX_VLAN));
+            vlanToEncap = vlanRule.vlanId();
+
         } else {
             assertThat(trafficTreatment.allInstructions().stream()
                                .filter(treat -> treat instanceof L2ModificationInstruction.ModVlanIdInstruction)
@@ -385,7 +457,7 @@
                 .get();
         verifyIdAndPriority(rule1, d1p0.deviceId());
         assertThat(rule1.selector(), is(DefaultTrafficSelector.builder(selector)
-                                        .matchInPort(d1p0.port()).build()));
+                .matchInPort(d1p0.port()).build()));
         MplsLabel mplsLabelToEncap = verifyMplsEncapTreatment(rule1.treatment(), d1p1, true, false);
 
         FlowRule rule2 = rules.stream()