diff --git a/apps/tvue/src/main/java/org/onlab/onos/tvue/TopologyResource.java b/apps/tvue/src/main/java/org/onlab/onos/tvue/TopologyResource.java
index ea6a7cc..42eb4e7 100644
--- a/apps/tvue/src/main/java/org/onlab/onos/tvue/TopologyResource.java
+++ b/apps/tvue/src/main/java/org/onlab/onos/tvue/TopologyResource.java
@@ -141,7 +141,7 @@
     private ObjectNode json(ObjectMapper mapper, ElementId id, int group,
                             String label, boolean isOnline) {
         return mapper.createObjectNode()
-                .put("name", id.uri().toString())
+                .put("name", id.toString())
                 .put("label", label)
                 .put("group", group)
                 .put("online", isOnline);
@@ -202,7 +202,7 @@
     // Returns a formatted string for the element associated with the given
     // connection point.
     private static String id(ConnectPoint cp) {
-        return cp.elementId().uri().toString();
+        return cp.elementId().toString();
     }
 
 }
diff --git a/cli/src/main/java/org/onlab/onos/cli/Comparators.java b/cli/src/main/java/org/onlab/onos/cli/Comparators.java
index 98ac624..d44c49f 100644
--- a/cli/src/main/java/org/onlab/onos/cli/Comparators.java
+++ b/cli/src/main/java/org/onlab/onos/cli/Comparators.java
@@ -21,14 +21,14 @@
     public static final Comparator<ElementId> ELEMENT_ID_COMPARATOR = new Comparator<ElementId>() {
         @Override
         public int compare(ElementId id1, ElementId id2) {
-            return id1.uri().toString().compareTo(id2.uri().toString());
+            return id1.toString().compareTo(id2.toString());
         }
     };
 
     public static final Comparator<Element> ELEMENT_COMPARATOR = new Comparator<Element>() {
         @Override
         public int compare(Element e1, Element e2) {
-            return e1.id().uri().toString().compareTo(e2.id().uri().toString());
+            return e1.id().toString().compareTo(e2.id().toString());
         }
     };
 
diff --git a/core/api/src/main/java/org/onlab/onos/net/DeviceId.java b/core/api/src/main/java/org/onlab/onos/net/DeviceId.java
index ef8c5ab..072ba28 100644
--- a/core/api/src/main/java/org/onlab/onos/net/DeviceId.java
+++ b/core/api/src/main/java/org/onlab/onos/net/DeviceId.java
@@ -1,15 +1,32 @@
 package org.onlab.onos.net;
 
 import java.net.URI;
+import java.util.Objects;
 
 /**
  * Immutable representation of a device identity.
  */
 public final class DeviceId extends ElementId {
 
+    /**
+     * Represents either no device, or an unspecified device.
+     */
+    public static final DeviceId NONE = deviceId("none:none");
+
+    private final URI uri;
+    private final String str;
+
     // Public construction is prohibited
     private DeviceId(URI uri) {
-        super(uri);
+        this.uri = uri;
+        this.str = uri.toString();
+    }
+
+
+    // Default constructor for serialization
+    protected DeviceId() {
+        this.uri = null;
+        this.str = null;
     }
 
     /**
@@ -30,4 +47,36 @@
         return deviceId(URI.create(string));
     }
 
+    /**
+     * Returns the backing URI.
+     *
+     * @return backing URI
+     */
+    public URI uri() {
+        return uri;
+    }
+
+    @Override
+    public int hashCode() {
+        return Objects.hash(str);
+    }
+
+    @Override
+    public boolean equals(Object obj) {
+        if (this == obj) {
+            return true;
+        }
+        if (obj instanceof DeviceId) {
+            final DeviceId that = (DeviceId) obj;
+            return this.getClass() == that.getClass() &&
+                    Objects.equals(this.str, that.str);
+        }
+        return false;
+    }
+
+    @Override
+    public String toString() {
+        return str;
+    }
+
 }
diff --git a/core/api/src/main/java/org/onlab/onos/net/HostId.java b/core/api/src/main/java/org/onlab/onos/net/HostId.java
index f2c0303..ffe558f 100644
--- a/core/api/src/main/java/org/onlab/onos/net/HostId.java
+++ b/core/api/src/main/java/org/onlab/onos/net/HostId.java
@@ -3,44 +3,69 @@
 import org.onlab.packet.MacAddress;
 import org.onlab.packet.VlanId;
 
-import java.net.URI;
+import java.util.Objects;
+
+import static com.google.common.base.Preconditions.checkArgument;
 
 /**
  * Immutable representation of a host identity.
  */
 public final class HostId extends ElementId {
 
-    private static final String NIC = "nic";
-
     /**
      * Represents either no host, or an unspecified host; used for creating
      * open ingress/egress edge links.
      */
-    public static final HostId NONE = hostId(NIC + ":none-0");
+    public static final HostId NONE = new HostId(MacAddress.ZERO, VlanId.NONE);
+
+    private static final int MAC_LENGTH = 17;
+    private static final int MIN_ID_LENGTH = 19;
+
+    private final MacAddress mac;
+    private final VlanId vlanId;
 
     // Public construction is prohibited
-    private HostId(URI uri) {
-        super(uri);
+    private HostId(MacAddress mac, VlanId vlanId) {
+        this.mac = mac;
+        this.vlanId = vlanId;
+    }
+
+    // Default constructor for serialization
+    private HostId() {
+        this.mac = null;
+        this.vlanId = null;
     }
 
     /**
-     * Creates a device id using the supplied URI.
+     * Returns the host MAC address.
      *
-     * @param uri device URI
-     * @return host identifier
+     * @return MAC address
      */
-    public static HostId hostId(URI uri) {
-        return new HostId(uri);
+    public MacAddress mac() {
+        return mac;
     }
 
     /**
-     * Creates a device id using the supplied URI string.
+     * Returns the host MAC address.
+     *
+     * @return MAC address
+     */
+    public VlanId vlanId() {
+        return vlanId;
+    }
+
+    /**
+     * Creates a device id using the supplied ID string.
      *
      * @param string device URI string
      * @return host identifier
      */
     public static HostId hostId(String string) {
-        return hostId(URI.create(string));
+        checkArgument(string.length() >= MIN_ID_LENGTH,
+                      "Host ID must be at least %s characters", MIN_ID_LENGTH);
+        MacAddress mac = MacAddress.valueOf(string.substring(0, MAC_LENGTH));
+        VlanId vlanId = VlanId.vlanId(Short.parseShort(string.substring(MAC_LENGTH + 1)));
+        return new HostId(mac, vlanId);
     }
 
     /**
@@ -51,7 +76,7 @@
      * @return host identifier
      */
     public static HostId hostId(MacAddress mac, VlanId vlanId) {
-        return hostId(NIC + ":" + mac + "-" + vlanId);
+        return new HostId(mac, vlanId);
     }
 
     /**
@@ -64,4 +89,26 @@
         return hostId(mac, VlanId.vlanId(VlanId.UNTAGGED));
     }
 
+    public String toString() {
+        return mac + "/" + vlanId;
+    }
+
+    @Override
+    public int hashCode() {
+        return Objects.hash(mac, vlanId);
+    }
+
+    @Override
+    public boolean equals(Object obj) {
+        if (this == obj) {
+            return true;
+        }
+        if (obj instanceof HostId) {
+            final HostId other = (HostId) obj;
+            return Objects.equals(this.mac, other.mac) &&
+                    Objects.equals(this.vlanId, other.vlanId);
+        }
+        return false;
+    }
+
 }
diff --git a/core/api/src/main/java/org/onlab/onos/net/HostLocation.java b/core/api/src/main/java/org/onlab/onos/net/HostLocation.java
index 60c5945..3fc3127 100644
--- a/core/api/src/main/java/org/onlab/onos/net/HostLocation.java
+++ b/core/api/src/main/java/org/onlab/onos/net/HostLocation.java
@@ -1,11 +1,18 @@
 package org.onlab.onos.net;
 
+import static org.onlab.onos.net.PortNumber.P0;
+
 /**
  * Representation of a network edge location where an end-station host is
  * connected.
  */
 public class HostLocation extends ConnectPoint {
 
+    /**
+     * Represents a no location or an unknown location.
+     */
+    public static final HostLocation NONE = new HostLocation(DeviceId.NONE, P0, 0L);
+
     // Note that time is explicitly excluded from the notion of equality.
     private final long time;
 
diff --git a/core/api/src/test/java/org/onlab/onos/net/DefaultEdgeLinkTest.java b/core/api/src/test/java/org/onlab/onos/net/DefaultEdgeLinkTest.java
index fd63797..9fb9570 100644
--- a/core/api/src/test/java/org/onlab/onos/net/DefaultEdgeLinkTest.java
+++ b/core/api/src/test/java/org/onlab/onos/net/DefaultEdgeLinkTest.java
@@ -18,8 +18,8 @@
 
     private static final ProviderId PID = new ProviderId("of", "foo");
     private static final DeviceId DID1 = deviceId("of:foo");
-    private static final HostId HID1 = hostId("nic:foobar");
-    private static final HostId HID2 = hostId("nic:barfoo");
+    private static final HostId HID1 = hostId("00:00:00:00:00:01/-1");
+    private static final HostId HID2 = hostId("00:00:00:00:00:01/-1");
     private static final PortNumber P0 = portNumber(0);
     private static final PortNumber P1 = portNumber(1);
 
@@ -35,12 +35,8 @@
         EdgeLink l4 = new DefaultEdgeLink(PID, cp(HID2, P0),
                                           new HostLocation(DID1, P1, 123L), false);
 
-        EdgeLink l5 = new DefaultEdgeLink(PID, cp(HID1, P0),
-                                          new HostLocation(DID1, P1, 123L), false);
-
         new EqualsTester().addEqualityGroup(l1, l2)
                 .addEqualityGroup(l3, l4)
-                .addEqualityGroup(l5)
                 .testEquals();
     }
 
diff --git a/core/api/src/test/java/org/onlab/onos/net/DeviceIdTest.java b/core/api/src/test/java/org/onlab/onos/net/DeviceIdTest.java
index eaee54c..295955e 100644
--- a/core/api/src/test/java/org/onlab/onos/net/DeviceIdTest.java
+++ b/core/api/src/test/java/org/onlab/onos/net/DeviceIdTest.java
@@ -8,7 +8,7 @@
 /**
  * Test of the device identifier.
  */
-public class DeviceIdTest extends ElementIdTest {
+public class DeviceIdTest {
 
     @Test
     public void basics() {
diff --git a/core/api/src/test/java/org/onlab/onos/net/ElementIdTest.java b/core/api/src/test/java/org/onlab/onos/net/ElementIdTest.java
deleted file mode 100644
index cf209b3..0000000
--- a/core/api/src/test/java/org/onlab/onos/net/ElementIdTest.java
+++ /dev/null
@@ -1,36 +0,0 @@
-package org.onlab.onos.net;
-
-import com.google.common.testing.EqualsTester;
-import org.junit.Test;
-
-import java.net.URI;
-
-import static org.junit.Assert.assertEquals;
-
-/**
- * Test of the network element identifier.
- */
-public class ElementIdTest {
-
-    private static class FooId extends ElementId {
-        public FooId(URI uri) {
-            super(uri);
-        }
-    }
-
-    public static URI uri(String str) {
-        return URI.create(str);
-    }
-
-    @Test
-    public void basics() {
-        new EqualsTester()
-                .addEqualityGroup(new FooId(uri("of:foo")),
-                                  new FooId(uri("of:foo")))
-                .addEqualityGroup(new FooId(uri("of:bar")))
-                .testEquals();
-        assertEquals("wrong uri", uri("ofcfg:foo"),
-                     new FooId(uri("ofcfg:foo")).uri());
-    }
-
-}
diff --git a/core/api/src/test/java/org/onlab/onos/net/HostIdTest.java b/core/api/src/test/java/org/onlab/onos/net/HostIdTest.java
index 712f6b2..40efeb1 100644
--- a/core/api/src/test/java/org/onlab/onos/net/HostIdTest.java
+++ b/core/api/src/test/java/org/onlab/onos/net/HostIdTest.java
@@ -11,20 +11,18 @@
 /**
  * Test for the host identifier.
  */
-public class HostIdTest extends ElementIdTest {
+public class HostIdTest {
 
     private static final MacAddress MAC1 = MacAddress.valueOf("00:11:00:00:00:01");
     private static final MacAddress MAC2 = MacAddress.valueOf("00:22:00:00:00:02");
     private static final VlanId VLAN1 = VlanId.vlanId((short) 11);
     private static final VlanId VLAN2 = VlanId.vlanId((short) 22);
 
-    @Override
     @Test
     public void basics() {
         new EqualsTester()
-                .addEqualityGroup(hostId("nic:00:11:00:00:00:01-11"),
-                                  hostId(MAC1, VLAN1))
-                .addEqualityGroup(hostId(MAC2, VLAN2))
+                .addEqualityGroup(hostId(MAC1, VLAN1), hostId(MAC1, VLAN1))
+                .addEqualityGroup(hostId(MAC2, VLAN2), hostId(MAC2, VLAN2))
                 .testEquals();
     }
 
diff --git a/core/api/src/test/java/org/onlab/onos/net/NetTestTools.java b/core/api/src/test/java/org/onlab/onos/net/NetTestTools.java
index ce64e46..379ec7a 100644
--- a/core/api/src/test/java/org/onlab/onos/net/NetTestTools.java
+++ b/core/api/src/test/java/org/onlab/onos/net/NetTestTools.java
@@ -31,7 +31,7 @@
 
     // Short-hand for producing a host id from a string
     public static HostId hid(String id) {
-        return hostId("nic:" + id);
+        return hostId(id);
     }
 
     // Crates a new device with the specified id
diff --git a/core/api/src/test/java/org/onlab/onos/net/PortNumberTest.java b/core/api/src/test/java/org/onlab/onos/net/PortNumberTest.java
index 528ad09..d942a98 100644
--- a/core/api/src/test/java/org/onlab/onos/net/PortNumberTest.java
+++ b/core/api/src/test/java/org/onlab/onos/net/PortNumberTest.java
@@ -10,9 +10,8 @@
 /**
  * Test of the port number.
  */
-public class PortNumberTest extends ElementIdTest {
+public class PortNumberTest {
 
-    @Override
     @Test
     public void basics() {
         new EqualsTester()
diff --git a/core/net/src/main/java/org/onlab/onos/net/topology/impl/PathManager.java b/core/net/src/main/java/org/onlab/onos/net/topology/impl/PathManager.java
index 86be9a5..849ac6d 100644
--- a/core/net/src/main/java/org/onlab/onos/net/topology/impl/PathManager.java
+++ b/core/net/src/main/java/org/onlab/onos/net/topology/impl/PathManager.java
@@ -22,9 +22,9 @@
 import org.onlab.onos.net.Path;
 import org.onlab.onos.net.PortNumber;
 import org.onlab.onos.net.host.HostService;
-import org.onlab.onos.net.topology.PathService;
 import org.onlab.onos.net.provider.ProviderId;
 import org.onlab.onos.net.topology.LinkWeight;
+import org.onlab.onos.net.topology.PathService;
 import org.onlab.onos.net.topology.Topology;
 import org.onlab.onos.net.topology.TopologyService;
 import org.slf4j.Logger;
@@ -33,7 +33,6 @@
 import java.util.Set;
 
 import static com.google.common.base.Preconditions.checkNotNull;
-import static org.onlab.onos.net.DeviceId.deviceId;
 import static org.slf4j.LoggerFactory.getLogger;
 
 /**
@@ -162,8 +161,8 @@
     // edge link since the src or dst are really an infrastructure device.
     private static class NotHost extends DefaultEdgeLink implements EdgeLink {
         NotHost() {
-            super(PID, new ConnectPoint(HostId.hostId("nic:none"), P0),
-                  new HostLocation(deviceId("none:none"), P0, 0L), false);
+            super(PID, new ConnectPoint(HostId.NONE, P0),
+                  new HostLocation(DeviceId.NONE, P0, 0L), false);
         }
     }
 }
diff --git a/core/net/src/test/java/org/onlab/onos/net/topology/impl/PathManagerTest.java b/core/net/src/test/java/org/onlab/onos/net/topology/impl/PathManagerTest.java
index 2ecf7f5..c22f985 100644
--- a/core/net/src/test/java/org/onlab/onos/net/topology/impl/PathManagerTest.java
+++ b/core/net/src/test/java/org/onlab/onos/net/topology/impl/PathManagerTest.java
@@ -65,47 +65,48 @@
     @Test
     public void infraToEdge() {
         DeviceId src = did("src");
-        HostId dst = hid("dst");
+        HostId dst = hid("12:34:56:78:90:ab/1");
         fakeTopoMgr.paths.add(createPath("src", "middle", "edge"));
-        fakeHostMgr.hosts.put(dst, host("dst", "edge"));
+        fakeHostMgr.hosts.put(dst, host("12:34:56:78:90:ab/1", "edge"));
         Set<Path> paths = service.getPaths(src, dst);
         validatePaths(paths, 1, 3, src, dst);
     }
 
     @Test
     public void edgeToInfra() {
-        HostId src = hid("src");
+        HostId src = hid("12:34:56:78:90:ab/1");
         DeviceId dst = did("dst");
         fakeTopoMgr.paths.add(createPath("edge", "middle", "dst"));
-        fakeHostMgr.hosts.put(src, host("src", "edge"));
+        fakeHostMgr.hosts.put(src, host("12:34:56:78:90:ab/1", "edge"));
         Set<Path> paths = service.getPaths(src, dst);
         validatePaths(paths, 1, 3, src, dst);
     }
 
     @Test
     public void edgeToEdge() {
-        HostId src = hid("src");
-        HostId dst = hid("dst");
+        HostId src = hid("12:34:56:78:90:ab/1");
+        HostId dst = hid("12:34:56:78:90:ef/1");
         fakeTopoMgr.paths.add(createPath("srcEdge", "middle", "dstEdge"));
-        fakeHostMgr.hosts.put(src, host("src", "srcEdge"));
-        fakeHostMgr.hosts.put(dst, host("dst", "dstEdge"));
+        fakeHostMgr.hosts.put(src, host("12:34:56:78:90:ab/1", "srcEdge"));
+        fakeHostMgr.hosts.put(dst, host("12:34:56:78:90:ef/1", "dstEdge"));
         Set<Path> paths = service.getPaths(src, dst);
         validatePaths(paths, 1, 4, src, dst);
     }
 
     @Test
     public void edgeToEdgeDirect() {
-        HostId src = hid("src");
-        HostId dst = hid("dst");
-        fakeHostMgr.hosts.put(src, host("src", "edge"));
-        fakeHostMgr.hosts.put(dst, host("dst", "edge"));
+        HostId src = hid("12:34:56:78:90:ab/1");
+        HostId dst = hid("12:34:56:78:90:ef/1");
+        fakeHostMgr.hosts.put(src, host("12:34:56:78:90:ab/1", "edge"));
+        fakeHostMgr.hosts.put(dst, host("12:34:56:78:90:ef/1", "edge"));
         Set<Path> paths = service.getPaths(src, dst);
         validatePaths(paths, 1, 2, src, dst);
     }
 
     @Test
     public void noEdge() {
-        Set<Path> paths = service.getPaths(hid("src"), hid("dst"));
+        Set<Path> paths = service.getPaths(hid("12:34:56:78:90:ab/1"),
+                                           hid("12:34:56:78:90:ef/1"));
         assertTrue("there should be no paths", paths.isEmpty());
     }
 
diff --git a/utils/misc/src/main/java/org/onlab/packet/MacAddress.java b/utils/misc/src/main/java/org/onlab/packet/MacAddress.java
index 814660b..08aa6e3 100644
--- a/utils/misc/src/main/java/org/onlab/packet/MacAddress.java
+++ b/utils/misc/src/main/java/org/onlab/packet/MacAddress.java
@@ -22,11 +22,12 @@
  *
  */
 public class MacAddress {
-    public static final byte[] ZERO_MAC_ADDRESS =
-            MacAddress.valueOf("00:00:00:00:00:00").getAddress();
 
-    public static final byte[] BROADCAST_MAC =
-            MacAddress.valueOf("ff:ff:ff:ff:ff:ff").getAddress();
+    public static final MacAddress ZERO = valueOf("00:00:00:00:00:00");
+    public static final MacAddress BROADCAST = valueOf("ff:ff:ff:ff:ff:ff");
+
+    public static final byte[] ZERO_MAC_ADDRESS = ZERO.getAddress();
+    public static final byte[] BROADCAST_MAC = BROADCAST.getAddress();
 
     public static final int MAC_ADDRESS_LENGTH = 6;
     private byte[] address = new byte[MacAddress.MAC_ADDRESS_LENGTH];
diff --git a/utils/misc/src/main/java/org/onlab/packet/VlanId.java b/utils/misc/src/main/java/org/onlab/packet/VlanId.java
index 60daec7..266a67c 100644
--- a/utils/misc/src/main/java/org/onlab/packet/VlanId.java
+++ b/utils/misc/src/main/java/org/onlab/packet/VlanId.java
@@ -3,12 +3,15 @@
 /**
  * Representation of a VLAN ID.
  */
-// FIXME: This will end-up looking like a constant; we should name it 'VlanId', 'IpAddress', 'MacAddress'.
 public class VlanId {
 
     private final short value;
+
     // Based on convention used elsewhere? Check and change if needed
     public static final short UNTAGGED = (short) 0xffff;
+
+    public static final VlanId NONE = VlanId.vlanId(UNTAGGED);
+
     // A VLAN ID is actually 12 bits of a VLAN tag.
     public static final short MAX_VLAN = 4095;