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