diff --git a/agent/agentbootstrap/bootstrap.go b/agent/agentbootstrap/bootstrap.go
index cbdf5c6..b6541e8 100644
--- a/agent/agentbootstrap/bootstrap.go
+++ b/agent/agentbootstrap/bootstrap.go
@@ -37,6 +37,8 @@ type InitializeStateParams struct {
 	// BootstrapMachineAddresses holds the bootstrap machine's addresses.
 	BootstrapMachineAddresses []network.Address
 
+	BootstrapMachineDNSName string
+
 	// BootstrapMachineJobs holds the jobs that the bootstrap machine
 	// agent will run.
 	BootstrapMachineJobs []multiwatcher.MachineJob
@@ -256,6 +258,7 @@ func initBootstrapMachine(c agent.ConfigSetter, st *state.State, args Initialize
 	}
 	m, err := st.AddOneMachine(state.MachineTemplate{
 		Addresses:               args.BootstrapMachineAddresses,
+		DNSName:                 args.BootstrapMachineDNSName,
 		Series:                  series.HostSeries(),
 		Nonce:                   agent.BootstrapNonce,
 		Constraints:             args.BootstrapMachineConstraints,
diff --git a/api/provisioner/machine.go b/api/provisioner/machine.go
index d38a7bc..28c480a 100644
--- a/api/provisioner/machine.go
+++ b/api/provisioner/machine.go
@@ -231,7 +231,7 @@ func (m *Machine) DistributionGroup() ([]instance.Id, error) {
 // SetInstanceInfo sets the provider specific instance id, nonce, metadata,
 // network config for this machine. Once set, the instance id cannot be changed.
 func (m *Machine) SetInstanceInfo(
-	id instance.Id, nonce string, characteristics *instance.HardwareCharacteristics,
+	id instance.Id, dnsName, nonce string, characteristics *instance.HardwareCharacteristics,
 	networkConfig []params.NetworkConfig, volumes []params.Volume,
 	volumeAttachments map[string]params.VolumeAttachmentInfo,
 ) error {
@@ -239,6 +239,7 @@ func (m *Machine) SetInstanceInfo(
 	args := params.InstancesInfo{
 		Machines: []params.InstanceInfo{{
 			Tag:               m.tag.String(),
+			DNSName:           dnsName,
 			InstanceId:        id,
 			Nonce:             nonce,
 			Characteristics:   characteristics,
diff --git a/apiserver/client/status.go b/apiserver/client/status.go
index 1dc9025..e8efaf1 100644
--- a/apiserver/client/status.go
+++ b/apiserver/client/status.go
@@ -508,14 +508,18 @@ func makeMachineStatus(machine *state.Machine) (status params.MachineStatus) {
 	instid, err := machine.InstanceId()
 	if err == nil {
 		status.InstanceId = instid
-		addr, err := machine.PublicAddress()
-		if err != nil {
-			// Usually this indicates that no addresses have been set on the
-			// machine yet.
-			addr = network.Address{}
-			logger.Debugf("error fetching public address: %q", err)
+		if dnsName := machine.DNSName(); dnsName != "" {
+			status.DNSName = dnsName
+		} else {
+			addr, err := machine.PublicAddress()
+			if err != nil {
+				// Usually this indicates that no addresses have been set on the
+				// machine yet.
+				addr = network.Address{}
+				logger.Debugf("error fetching public address: %q", err)
+			}
+			status.DNSName = addr.Value
 		}
-		status.DNSName = addr.Value
 	} else {
 		if errors.IsNotProvisioned(err) {
 			status.InstanceId = "pending"
diff --git a/apiserver/common/networkingcommon/types.go b/apiserver/common/networkingcommon/types.go
index 0eb8ee9..3a7c005 100644
--- a/apiserver/common/networkingcommon/types.go
+++ b/apiserver/common/networkingcommon/types.go
@@ -194,27 +194,34 @@ func SortNetworkConfigsByParents(input []params.NetworkConfig) []params.NetworkC
 	return sortedInputCopy
 }
 
-type byInterfaceName []params.NetworkConfig
-
-func (c byInterfaceName) Len() int {
-	return len(c)
-}
-
-func (c byInterfaceName) Swap(i, j int) {
-	orgI, orgJ := c[i], c[j]
-	c[j], c[i] = orgI, orgJ
-}
-
-func (c byInterfaceName) Less(i, j int) bool {
-	return c[i].InterfaceName < c[j].InterfaceName
-}
-
 // SortNetworkConfigsByInterfaceName returns the given input sorted by
 // InterfaceName.
 func SortNetworkConfigsByInterfaceName(input []params.NetworkConfig) []params.NetworkConfig {
-	sortedInputCopy := CopyNetworkConfigs(input)
-	sort.Stable(byInterfaceName(sortedInputCopy))
-	return sortedInputCopy
+	var interfaceNames []string
+	inputByName := make(map[string][]params.NetworkConfig)
+	for _, iface := range input {
+		name := iface.InterfaceName
+		if iface.ParentInterfaceName != "" {
+			name = iface.ParentInterfaceName + "@" + name
+		} else if strings.HasPrefix(iface.InterfaceName, instancecfg.DefaultBridgePrefix) {
+			name = "000@" + name
+		}
+
+		interfaceNames = append(interfaceNames, name)
+		infos := inputByName[name]
+		infos = append(infos, iface)
+		inputByName[name] = infos
+	}
+	sortedNames := network.NaturallySortDeviceNames(interfaceNames...)
+
+	sortedInput := make([]params.NetworkConfig, len(input))
+	for i, name := range sortedNames {
+		infos := inputByName[name]
+		sortedInput[i] = infos[0]
+		infos = infos[1:]
+		inputByName[name] = infos
+	}
+	return sortedInput
 }
 
 // NetworkConfigsToIndentedJSON returns the given input as an indented JSON
@@ -303,24 +310,34 @@ func NetworkConfigsToStateArgs(networkConfig []params.NetworkConfig) (
 			devicesArgs = append(devicesArgs, args)
 		}
 
-		if netConfig.CIDR == "" || netConfig.Address == "" {
-			logger.Tracef(
-				"skipping empty CIDR %q and/or Address %q of %q",
-				netConfig.CIDR, netConfig.Address, netConfig.InterfaceName,
-			)
+		if netConfig.CIDR == "" && netConfig.Address == "" {
+			logger.Tracef("skipping empty CIDR and Address of interface %q", netConfig.InterfaceName)
 			continue
 		}
-		_, ipNet, err := net.ParseCIDR(netConfig.CIDR)
-		if err != nil {
-			logger.Warningf("FIXME: ignoring unexpected CIDR format %q: %v", netConfig.CIDR, err)
-			continue
+
+		var (
+			ipNet  *net.IPNet
+			ipAddr net.IP
+			err    error
+		)
+
+		if netConfig.CIDR != "" {
+			_, ipNet, err = net.ParseCIDR(netConfig.CIDR)
+			if err != nil {
+				logger.Warningf("FIXME: ignoring unexpected CIDR format %q: %v", netConfig.CIDR, err)
+				continue
+			}
 		}
-		ipAddr := net.ParseIP(netConfig.Address)
-		if ipAddr == nil {
-			logger.Warningf("FIXME: ignoring unexpected Address format %q", netConfig.Address)
-			continue
+
+		if netConfig.Address != "" {
+			ipAddr = net.ParseIP(netConfig.Address)
+			if ipAddr == nil {
+				logger.Warningf("FIXME: ignoring unexpected Address format %q", netConfig.Address)
+				continue
+			}
+			ipNet.IP = ipAddr
 		}
-		ipNet.IP = ipAddr
+
 		cidrAddress := ipNet.String()
 
 		var derivedConfigMethod state.AddressConfigMethod
@@ -431,6 +448,7 @@ func GetObservedNetworkConfig() ([]params.NetworkConfig, error) {
 		for _, addr := range addrs {
 			cidrAddress := addr.String()
 			if cidrAddress == "" {
+				logger.Warningf("no address %q on interface %q", addr, nic.Name)
 				continue
 			}
 			ip, ipNet, err := net.ParseCIDR(cidrAddress)
@@ -447,6 +465,7 @@ func GetObservedNetworkConfig() ([]params.NetworkConfig, error) {
 			}
 			if ip.To4() == nil {
 				logger.Debugf("skipping observed IPv6 address %q on %q: not fully supported yet", ip, nic.Name)
+				observedConfig = append(observedConfig, nicConfig)
 				continue
 			}
 
@@ -470,7 +489,7 @@ func GetObservedNetworkConfig() ([]params.NetworkConfig, error) {
 // configs after merging providerConfig with observedConfig.
 func MergeProviderAndObservedNetworkConfigs(providerConfigs, observedConfigs []params.NetworkConfig) ([]params.NetworkConfig, error) {
 	providerConfigsByName := make(map[string][]params.NetworkConfig)
-	sortedProviderConfigs := SortNetworkConfigsByParents(providerConfigs)
+	sortedProviderConfigs := SortNetworkConfigsByInterfaceName(providerConfigs)
 	for _, config := range sortedProviderConfigs {
 		name := config.InterfaceName
 		providerConfigsByName[name] = append(providerConfigsByName[name], config)
@@ -482,7 +501,7 @@ func MergeProviderAndObservedNetworkConfigs(providerConfigs, observedConfigs []p
 	}
 	logger.Debugf("provider network config of machine:\n%s", jsonProviderConfig)
 
-	sortedObservedConfigs := SortNetworkConfigsByParents(observedConfigs)
+	sortedObservedConfigs := SortNetworkConfigsByInterfaceName(observedConfigs)
 	jsonObservedConfig, err := NetworkConfigsToIndentedJSON(sortedObservedConfigs)
 	if err != nil {
 		return nil, errors.Annotatef(err, "cannot serialize observed config %#v as JSON", sortedObservedConfigs)
@@ -508,13 +527,23 @@ func MergeProviderAndObservedNetworkConfigs(providerConfigs, observedConfigs []p
 
 				var underlyingConfig params.NetworkConfig
 				for i, underlying := range underlyingConfigs {
-					if underlying.Address == config.Address {
+					matches := false
+					if underlying.Address == "" {
+						logger.Infof("underlying %q has no address, matching by MAC %q", underlying.InterfaceName, underlying.MACAddress)
+						matches = underlying.MACAddress == config.MACAddress
+					} else {
+						logger.Infof("matching underlying %q by address %q", underlying.InterfaceName, underlying.Address)
+						matches = underlying.Address == config.Address
+					}
+
+					if matches || underlying.Address == "" {
 						logger.Tracef("replacing undelying config %+v", underlying)
 						// Remove what we found before changing it below.
 						underlyingConfig = underlying
 						underlyingConfigs = append(underlyingConfigs[:i], underlyingConfigs[i+1:]...)
 						break
 					}
+					logger.Tracef("underlying %#v does not match observed %#v neither by MACAddress nor Address", underlying, config)
 				}
 				logger.Tracef("underlying provider config after update: %+v", underlyingConfigs)
 
@@ -527,14 +556,16 @@ func MergeProviderAndObservedNetworkConfigs(providerConfigs, observedConfigs []p
 				bridgeConfig.ProviderVLANId = underlyingConfig.ProviderVLANId
 				bridgeConfig.ProviderSubnetId = underlyingConfig.ProviderSubnetId
 				bridgeConfig.ProviderAddressId = underlyingConfig.ProviderAddressId
-				if underlyingParent := underlyingConfig.ParentInterfaceName; underlyingParent != "" {
+				bridgeConfig.CIDR = underlyingConfig.CIDR
+
+				underlyingParent := underlyingConfig.ParentInterfaceName
+				if underlyingParent != "" && !strings.HasPrefix(underlyingParent, instancecfg.DefaultBridgePrefix) {
 					bridgeConfig.ParentInterfaceName = instancecfg.DefaultBridgePrefix + underlyingParent
 				}
 
 				underlyingConfig.ConfigType = string(network.ConfigManual)
 				underlyingConfig.ParentInterfaceName = name
 				underlyingConfig.ProviderAddressId = ""
-				underlyingConfig.CIDR = ""
 				underlyingConfig.Address = ""
 
 				underlyingConfigs = append(underlyingConfigs, underlyingConfig)
@@ -547,7 +578,7 @@ func MergeProviderAndObservedNetworkConfigs(providerConfigs, observedConfigs []p
 		}
 
 		knownProviderConfigs, knownByProvider := providerConfigsByName[name]
-		if !knownByProvider {
+		if !knownByProvider && config.CIDR != "" {
 			// Not known by the provider and not a Juju-created bridge, so just
 			// use the observed config for it.
 			logger.Tracef("device %q not known to provider - adding only observed config: %+v", name, config)
@@ -557,10 +588,15 @@ func MergeProviderAndObservedNetworkConfigs(providerConfigs, observedConfigs []p
 		logger.Tracef("device %q has known provider network config: %+v", name, knownProviderConfigs)
 
 		for _, providerConfig := range knownProviderConfigs {
-			if providerConfig.Address == config.Address {
+			if providerConfig.Address == "" && providerConfig.MACAddress == "" {
+				logger.Infof("skipping provider interface %q with neither Address or MACAddress set", providerConfig.InterfaceName)
+				continue
+			}
+
+			if providerConfig.Address == config.Address || providerConfig.MACAddress == config.MACAddress {
 				logger.Tracef(
-					"device %q has observed address %q, index %d, and MTU %q; overriding index %d and MTU %d from provider config",
-					name, config.Address, config.DeviceIndex, config.MTU, providerConfig.DeviceIndex, providerConfig.MTU,
+					"device %q has observed address %q, MAC, %q, index %d, and MTU %q; overriding index %d and MTU %d from provider config",
+					name, config.Address, config.MACAddress, config.DeviceIndex, config.MTU, providerConfig.DeviceIndex, providerConfig.MTU,
 				)
 				// Prefer observed device indices and MTU values as more up-to-date.
 				providerConfig.DeviceIndex = config.DeviceIndex
@@ -572,7 +608,7 @@ func MergeProviderAndObservedNetworkConfigs(providerConfigs, observedConfigs []p
 		}
 	}
 
-	sortedMergedConfigs := SortNetworkConfigsByParents(mergedConfigs)
+	sortedMergedConfigs := SortNetworkConfigsByInterfaceName(mergedConfigs)
 
 	jsonMergedConfig, err := NetworkConfigsToIndentedJSON(sortedMergedConfigs)
 	if err != nil {
diff --git a/apiserver/params/internal.go b/apiserver/params/internal.go
index 433c05e..75cad75 100644
--- a/apiserver/params/internal.go
+++ b/apiserver/params/internal.go
@@ -358,6 +358,7 @@ type InstanceInfo struct {
 	Tag             string                            `json:"tag"`
 	InstanceId      instance.Id                       `json:"instance-id"`
 	Nonce           string                            `json:"nonce"`
+	DNSName         string                            `json:"dns-name"`
 	Characteristics *instance.HardwareCharacteristics `json:"characteristics"`
 	Volumes         []Volume                          `json:"volumes"`
 	// VolumeAttachments is a mapping from volume tag to
diff --git a/apiserver/provisioner/provisioner.go b/apiserver/provisioner/provisioner.go
index 1322b2d..2ffd16d 100644
--- a/apiserver/provisioner/provisioner.go
+++ b/apiserver/provisioner/provisioner.go
@@ -495,6 +495,13 @@ func (p *ProvisionerAPI) SetInstanceInfo(args params.InstancesInfo) (params.Erro
 		if err != nil {
 			return errors.Annotatef(err, "cannot record provisioning info for %q", arg.InstanceId)
 		}
+
+		if arg.DNSName != "" {
+			if err := machine.SetDNSName(arg.DNSName); err != nil {
+				return errors.Annotatef(err, "cannot set dns-name %q for %q", arg.DNSName, arg.InstanceId)
+			}
+		}
+
 		return nil
 	}
 	for i, arg := range args.Machines {
@@ -665,37 +672,40 @@ func (p *ProvisionerAPI) prepareOrGetContainerInterfaceInfo(args params.Entities
 				preparedOK = false
 				break
 			}
-			if len(parentAddrs) == 0 {
-				err = errors.Errorf("host machine device %q has no addresses", parentDevice.Name())
-				result.Results[i].Error = common.ServerError(err)
-				preparedOK = false
-				break
-			}
-			firstAddress := parentAddrs[0]
-			parentDeviceSubnet, err := firstAddress.Subnet()
-			if err != nil {
-				err = errors.Annotatef(err,
-					"cannot get subnet %q used by address %q of host machine device %q",
-					firstAddress.SubnetCIDR(), firstAddress.Value(), parentDevice.Name(),
-				)
-				result.Results[i].Error = common.ServerError(err)
-				preparedOK = false
-				break
-			}
 
 			info := network.InterfaceInfo{
 				InterfaceName:       device.Name(),
 				MACAddress:          device.MACAddress(),
-				ConfigType:          network.ConfigStatic,
+				ConfigType:          network.ConfigManual,
 				InterfaceType:       network.InterfaceType(device.Type()),
 				NoAutoStart:         !device.IsAutoStart(),
 				Disabled:            !device.IsUp(),
 				MTU:                 int(device.MTU()),
-				CIDR:                parentDeviceSubnet.CIDR(),
-				ProviderSubnetId:    parentDeviceSubnet.ProviderId(),
-				VLANTag:             parentDeviceSubnet.VLANTag(),
 				ParentInterfaceName: parentDevice.Name(),
 			}
+
+			if len(parentAddrs) > 0 {
+				logger.Infof("host machine device %q has addresses %v", parentDevice.Name(), parentAddrs)
+
+				firstAddress := parentAddrs[0]
+				parentDeviceSubnet, err := firstAddress.Subnet()
+				if err != nil {
+					err = errors.Annotatef(err,
+						"cannot get subnet %q used by address %q of host machine device %q",
+						firstAddress.SubnetCIDR(), firstAddress.Value(), parentDevice.Name(),
+					)
+					result.Results[i].Error = common.ServerError(err)
+					preparedOK = false
+					break
+				}
+				info.ConfigType = network.ConfigStatic
+				info.CIDR = parentDeviceSubnet.CIDR()
+				info.ProviderSubnetId = parentDeviceSubnet.ProviderId()
+				info.VLANTag = parentDeviceSubnet.VLANTag()
+			} else {
+				logger.Infof("host machine device %q has no addresses %v", parentDevice.Name(), parentAddrs)
+			}
+
 			logger.Tracef("prepared info for container interface %q: %+v", info.InterfaceName, info)
 			preparedOK = true
 			preparedInfo[j] = info
diff --git a/cmd/jujud/bootstrap.go b/cmd/jujud/bootstrap.go
index f719cfe..5fc202e 100644
--- a/cmd/jujud/bootstrap.go
+++ b/cmd/jujud/bootstrap.go
@@ -182,6 +182,11 @@ func (c *BootstrapCommand) Run(_ *cmd.Context) error {
 		return err
 	}
 
+	dnsName, err := instances[0].DNSName()
+	if err != nil {
+		logger.Errorf("ignoring DNSName error: %v", err)
+	}
+
 	// When machine addresses are reported from state, they have
 	// duplicates removed.  We should do the same here so that
 	// there is not unnecessary churn in the mongo replicaset.
@@ -260,6 +265,7 @@ func (c *BootstrapCommand) Run(_ *cmd.Context) error {
 			agentbootstrap.InitializeStateParams{
 				StateInitializationParams: args,
 				BootstrapMachineAddresses: addrs,
+				BootstrapMachineDNSName:   dnsName,
 				BootstrapMachineJobs:      jobs,
 				SharedSecret:              sharedSecret,
 				Provider:                  environs.Provider,
diff --git a/container/kvm/instance.go b/container/kvm/instance.go
index 39f69a7..3d0bd24 100644
--- a/container/kvm/instance.go
+++ b/container/kvm/instance.go
@@ -46,6 +46,11 @@ func (kvm *kvmInstance) Addresses() ([]network.Address, error) {
 	return nil, nil
 }
 
+func (kvm *kvmInstance) DNSName() (string, error) {
+	logger.Errorf("kvmInstance.DNSName not implemented")
+	return "", nil
+}
+
 // OpenPorts implements instance.Instance.OpenPorts.
 func (kvm *kvmInstance) OpenPorts(machineId string, ports []network.PortRange) error {
 	return fmt.Errorf("not implemented")
diff --git a/container/lxd/instance.go b/container/lxd/instance.go
index 87c21ca..75ccead 100644
--- a/container/lxd/instance.go
+++ b/container/lxd/instance.go
@@ -36,6 +36,10 @@ func (lxd *lxdInstance) Addresses() ([]network.Address, error) {
 	return nil, errors.NotImplementedf("lxdInstance.Addresses")
 }
 
+func (lxd *lxdInstance) DNSName() (string, error) {
+	return "", errors.NotImplementedf("lxdInstance.DNSName")
+}
+
 // Status implements instance.Instance.Status.
 func (lxd *lxdInstance) Status() instance.InstanceStatus {
 	jujuStatus := status.StatusPending
diff --git a/instance/instance.go b/instance/instance.go
index abc3bf8..86010d3 100644
--- a/instance/instance.go
+++ b/instance/instance.go
@@ -36,6 +36,9 @@ type Instance interface {
 	// Status returns the provider-specific status for the instance.
 	Status() InstanceStatus
 
+	// DNSName returns the DNS name associated with the instance.
+	DNSName() (string, error)
+
 	// Addresses returns a list of hostnames or ip addresses
 	// associated with the instance.
 	Addresses() ([]network.Address, error)
diff --git a/provider/azure/instance.go b/provider/azure/instance.go
index fc5883e..4c6eda6 100644
--- a/provider/azure/instance.go
+++ b/provider/azure/instance.go
@@ -123,6 +123,16 @@ func setInstanceAddresses(
 	return nil
 }
 
+func (inst *azureInstance) DNSName() (string, error) {
+	logger.Infof("instance %q DNSName: %#v", inst.Id(), inst)
+	for _, pip := range inst.publicIPAddresses {
+		if pip.Properties.DNSSettings != nil && pip.Properties.DNSSettings.Fqdn != nil {
+			return to.String(pip.Properties.DNSSettings.Fqdn), nil
+		}
+	}
+	return "", nil
+}
+
 // Addresses is specified in the Instance interface.
 func (inst *azureInstance) Addresses() ([]jujunetwork.Address, error) {
 	addresses := make([]jujunetwork.Address, 0, len(inst.networkInterfaces)+len(inst.publicIPAddresses))
diff --git a/provider/cloudsigma/instance.go b/provider/cloudsigma/instance.go
index a7fdf11..06565ba 100644
--- a/provider/cloudsigma/instance.go
+++ b/provider/cloudsigma/instance.go
@@ -53,6 +53,10 @@ func (i sigmaInstance) Status() instance.InstanceStatus {
 
 }
 
+func (i sigmaInstance) DNSName() (string, error) {
+	return i.findIPv4(), nil
+}
+
 // Addresses returns a list of hostnames or ip addresses
 // associated with the instance. This will supercede DNSName
 // which can be implemented by selecting a preferred address.
diff --git a/provider/dummy/environs.go b/provider/dummy/environs.go
index 7d18c8a..1c3ca37 100644
--- a/provider/dummy/environs.go
+++ b/provider/dummy/environs.go
@@ -1473,6 +1473,15 @@ func (inst *dummyInstance) checkBroken(method string) error {
 	return nil
 }
 
+func (inst *dummyInstance) DNSName() (string, error) {
+	inst.mu.Lock()
+	defer inst.mu.Unlock()
+	if err := inst.checkBroken("DNSName"); err != nil {
+		return "", err
+	}
+	return fmt.Sprintf("inst-%s.dummy", inst.id), nil
+}
+
 func (inst *dummyInstance) Addresses() ([]network.Address, error) {
 	inst.mu.Lock()
 	defer inst.mu.Unlock()
diff --git a/provider/ec2/instance.go b/provider/ec2/instance.go
index 9f89c9d..398aa2a 100644
--- a/provider/ec2/instance.go
+++ b/provider/ec2/instance.go
@@ -50,6 +50,12 @@ func (inst *ec2Instance) Status() instance.InstanceStatus {
 
 }
 
+// DNSName implements instance.Instance.
+func (inst *ec2Instance) DNSName() (string, error) {
+	logger.Infof("instance %q DNSName %q; %#v", inst.Id(), inst.Instance.DNSName, inst.Instance)
+	return inst.Instance.DNSName, nil
+}
+
 // Addresses implements network.Addresses() returning generic address
 // details for the instance, and requerying the ec2 api if required.
 func (inst *ec2Instance) Addresses() ([]network.Address, error) {
diff --git a/provider/gce/instance.go b/provider/gce/instance.go
index caafbed..b6f70a4 100644
--- a/provider/gce/instance.go
+++ b/provider/gce/instance.go
@@ -56,6 +56,11 @@ func (inst *environInstance) Addresses() ([]network.Address, error) {
 	return inst.base.Addresses(), nil
 }
 
+// DNSName implements instance.Instance.
+func (inst *environInstance) DNSName() (string, error) {
+	return "", nil
+}
+
 func findInst(id instance.Id, instances []instance.Instance) instance.Instance {
 	for _, inst := range instances {
 		if id == inst.Id() {
diff --git a/provider/joyent/instance.go b/provider/joyent/instance.go
index 3b3d912..42d8d5b 100644
--- a/provider/joyent/instance.go
+++ b/provider/joyent/instance.go
@@ -57,3 +57,7 @@ func (inst *joyentInstance) Addresses() ([]network.Address, error) {
 
 	return addresses, nil
 }
+
+func (inst *joyentInstance) DNSName() (string, error) {
+	return inst.machine.PrimaryIP, nil
+}
diff --git a/provider/lxd/instance.go b/provider/lxd/instance.go
index 5f33f30..5469e4a 100644
--- a/provider/lxd/instance.go
+++ b/provider/lxd/instance.go
@@ -54,6 +54,11 @@ func (inst *environInstance) Status() instance.InstanceStatus {
 
 }
 
+// DNSName implements instance.Instance.
+func (inst *environInstance) DNSName() (string, error) {
+	return "", nil
+}
+
 // Addresses implements instance.Instance.
 func (inst *environInstance) Addresses() ([]network.Address, error) {
 	return inst.env.raw.Addresses(inst.raw.Name)
diff --git a/provider/maas/add-juju-bridge.py b/provider/maas/add-juju-bridge.py
index d84a71d..741f74f 100755
--- a/provider/maas/add-juju-bridge.py
+++ b/provider/maas/add-juju-bridge.py
@@ -69,7 +69,9 @@ class LogicalInterface(object):
             options = []
         _, self.name, self.family, self.method = definition.split()
         self.options = options
+        self.is_loopback = self.method == 'loopback'
         self.is_bonded = [x for x in self.options if "bond-" in x]
+        self.has_bond_master_option = self.has_option(['bond-master'])
         self.is_alias = ":" in self.name
         self.is_vlan = [x for x in self.options if x.startswith("vlan-raw-device")]
         self.is_active = self.method == "dhcp" or self.method == "static"
@@ -80,6 +82,14 @@ class LogicalInterface(object):
     def __str__(self):
         return self.name
 
+    def has_option(self, options):
+        for o in self.options:
+            words = o.split()
+            ident = words[0]
+            if ident in options:
+                return True
+        return False
+
     @classmethod
     def prune_options(cls, options, invalid_options):
         result = []
@@ -94,7 +104,7 @@ class LogicalInterface(object):
         if bridge_name is None:
             bridge_name = prefix + self.name
         # Note: the testing order here is significant.
-        if not self.is_active or self.is_bridged:
+        if self.is_loopback or self.is_bridged or self.has_bond_master_option:
             return self._bridge_unchanged()
         elif self.is_alias:
             if self.parent and self.parent.iface and (not self.parent.iface.is_active or self.parent.iface.is_bridged):
diff --git a/provider/maas/bridgescript.go b/provider/maas/bridgescript.go
index fede3b5..1e68d90 100644
--- a/provider/maas/bridgescript.go
+++ b/provider/maas/bridgescript.go
@@ -81,7 +81,9 @@ class LogicalInterface(object):
             options = []
         _, self.name, self.family, self.method = definition.split()
         self.options = options
+        self.is_loopback = self.method == 'loopback'
         self.is_bonded = [x for x in self.options if "bond-" in x]
+        self.has_bond_master_option = self.has_option(['bond-master'])
         self.is_alias = ":" in self.name
         self.is_vlan = [x for x in self.options if x.startswith("vlan-raw-device")]
         self.is_active = self.method == "dhcp" or self.method == "static"
@@ -92,6 +94,14 @@ class LogicalInterface(object):
     def __str__(self):
         return self.name
 
+    def has_option(self, options):
+        for o in self.options:
+            words = o.split()
+            ident = words[0]
+            if ident in options:
+                return True
+        return False
+
     @classmethod
     def prune_options(cls, options, invalid_options):
         result = []
@@ -106,7 +116,7 @@ class LogicalInterface(object):
         if bridge_name is None:
             bridge_name = prefix + self.name
         # Note: the testing order here is significant.
-        if not self.is_active or self.is_bridged:
+        if self.is_loopback or self.is_bridged or self.has_bond_master_option:
             return self._bridge_unchanged()
         elif self.is_alias:
             if self.parent and self.parent.iface and (not self.parent.iface.is_active or self.parent.iface.is_bridged):
diff --git a/provider/maas/instance.go b/provider/maas/instance.go
index a496143..3492729 100644
--- a/provider/maas/instance.go
+++ b/provider/maas/instance.go
@@ -96,6 +96,10 @@ func (mi *maas1Instance) Addresses() ([]network.Address, error) {
 	return interfaceAddresses, nil
 }
 
+func (mi *maas1Instance) DNSName() (string, error) {
+	return mi.hostname()
+}
+
 var refreshMAASObject = func(maasObject *gomaasapi.MAASObject) (gomaasapi.MAASObject, error) {
 	// Defined like this to allow patching in tests to overcome limitations of
 	// gomaasapi's test server.
diff --git a/provider/maas/interfaces.go b/provider/maas/interfaces.go
index 1940b18..7c0db4c 100644
--- a/provider/maas/interfaces.go
+++ b/provider/maas/interfaces.go
@@ -153,6 +153,12 @@ func maasObjectNetworkInterfaces(maasObject *gomaasapi.MAASObject, subnetsMap ma
 			NoAutoStart:         !iface.Enabled,
 		}
 
+		if len(iface.Links) == 0 {
+			logger.Debugf("interface %q has no links", iface.Name)
+			infos = append(infos, nicInfo)
+			continue
+		}
+
 		for _, link := range iface.Links {
 			switch link.Mode {
 			case modeUnknown:
@@ -258,6 +264,12 @@ func maas2NetworkInterfaces(instance *maas2Instance, subnetsMap map[string]netwo
 			NoAutoStart:         !iface.Enabled(),
 		}
 
+		if len(iface.Links()) == 0 {
+			logger.Debugf("interface %q has no links", iface.Name())
+			infos = append(infos, nicInfo)
+			continue
+		}
+
 		for _, link := range iface.Links() {
 			switch maasLinkMode(link.Mode()) {
 			case modeUnknown:
diff --git a/provider/maas/maas2instance.go b/provider/maas/maas2instance.go
index 40add54..c540b3f 100644
--- a/provider/maas/maas2instance.go
+++ b/provider/maas/maas2instance.go
@@ -53,6 +53,10 @@ func (mi *maas2Instance) Id() instance.Id {
 	return instance.Id(mi.machine.SystemID())
 }
 
+func (mi *maas2Instance) DNSName() (string, error) {
+	return mi.machine.FQDN(), nil
+}
+
 func (mi *maas2Instance) Addresses() ([]network.Address, error) {
 	machineAddresses := mi.machine.IPAddresses()
 	addresses := make([]network.Address, len(machineAddresses))
diff --git a/provider/manual/instance.go b/provider/manual/instance.go
index 6a8b3d9..6321a32 100644
--- a/provider/manual/instance.go
+++ b/provider/manual/instance.go
@@ -30,6 +30,10 @@ func (manualBootstrapInstance) Refresh() error {
 	return nil
 }
 
+func (inst manualBootstrapInstance) DNSName() (string, error) {
+	return inst.host, nil
+}
+
 func (inst manualBootstrapInstance) Addresses() (addresses []network.Address, err error) {
 	addr, err := manual.HostAddress(inst.host)
 	if err != nil {
diff --git a/provider/openstack/provider.go b/provider/openstack/provider.go
index 34c8aff..a4be068 100644
--- a/provider/openstack/provider.go
+++ b/provider/openstack/provider.go
@@ -275,6 +275,10 @@ func (inst *openstackInstance) getAddresses() (map[string][]nova.IPAddress, erro
 	return addrs, nil
 }
 
+func (inst *openstackInstance) DNSName() (string, error) {
+	return "", nil
+}
+
 // Addresses implements network.Addresses() returning generic address
 // details for the instances, and calling the openstack api if needed.
 func (inst *openstackInstance) Addresses() ([]network.Address, error) {
diff --git a/provider/vsphere/instance.go b/provider/vsphere/instance.go
index 1a1d5a8..30ad3e7 100644
--- a/provider/vsphere/instance.go
+++ b/provider/vsphere/instance.go
@@ -63,6 +63,13 @@ func (inst *environInstance) Addresses() ([]network.Address, error) {
 	return res, nil
 }
 
+func (inst *environInstance) DNSName() (string, error) {
+	if inst.base.Guest != nil {
+		return inst.base.Guest.HostName, nil
+	}
+	return "", nil
+}
+
 func findInst(id instance.Id, instances []instance.Instance) instance.Instance {
 	for _, inst := range instances {
 		if id == inst.Id() {
diff --git a/state/addmachine.go b/state/addmachine.go
index fa2a7c2..dd65357 100644
--- a/state/addmachine.go
+++ b/state/addmachine.go
@@ -49,6 +49,8 @@ type MachineTemplate struct {
 	// come from link-layer device addresses.
 	Addresses []network.Address
 
+	DNSName string
+
 	// InstanceId holds the instance id to associate with the machine.
 	// If this is empty, the provisioner will try to provision the machine.
 	// If this is non-empty, the HardwareCharacteristics and Nonce
@@ -434,12 +436,35 @@ func (st *State) machineDocForTemplate(template MachineTemplate, id string) *mac
 	// no address is available, in which case the empty address is returned
 	// and setting the preferred address to an empty one is the correct
 	// thing to do when none is available.
-	privateAddr, _ := network.SelectInternalAddress(template.Addresses, false)
-	publicAddr, _ := network.SelectPublicAddress(template.Addresses)
+	var privateAddr, publicAddr address
+	if template.DNSName != "" {
+		preferredHostnameAddress, err := preferredAddressesFromDNSName(template.DNSName)
+		if err != nil {
+			logger.Errorf(
+				"skipping unresolvable hostname %q - not using for preferred addresses: %v",
+				template.DNSName, err,
+			)
+		} else {
+			privateAddr = *preferredHostnameAddress
+			publicAddr = *preferredHostnameAddress
+		}
+	}
+
+	if privateAddr.Value == "" {
+		netPrivateAddr, _ := network.SelectInternalAddress(template.Addresses, false)
+		privateAddr = fromNetworkAddress(netPrivateAddr, OriginMachine)
+	}
+
+	if publicAddr.Value == "" {
+		netPublicAddr, _ := network.SelectPublicAddress(template.Addresses)
+		publicAddr = fromNetworkAddress(netPublicAddr, OriginMachine)
+	}
+
 	logger.Infof(
 		"new machine %q has preferred addresses: private %q, public %q",
-		id, privateAddr, publicAddr,
+		id, privateAddr.networkAddress(), publicAddr.networkAddress(),
 	)
+
 	return &machineDoc{
 		DocID:                   st.docID(id),
 		Id:                      id,
@@ -450,9 +475,10 @@ func (st *State) machineDocForTemplate(template MachineTemplate, id string) *mac
 		Principals:              template.principals,
 		Life:                    Alive,
 		Nonce:                   template.Nonce,
+		DNSName:                 template.DNSName,
 		Addresses:               fromNetworkAddresses(template.Addresses, OriginMachine),
-		PreferredPrivateAddress: fromNetworkAddress(privateAddr, OriginMachine),
-		PreferredPublicAddress:  fromNetworkAddress(publicAddr, OriginMachine),
+		PreferredPrivateAddress: privateAddr,
+		PreferredPublicAddress:  publicAddr,
 		NoVote:                  template.NoVote,
 		Placement:               template.Placement,
 	}
diff --git a/state/machine.go b/state/machine.go
index 457fa43..28a4e56 100644
--- a/state/machine.go
+++ b/state/machine.go
@@ -5,6 +5,7 @@ package state
 
 import (
 	"fmt"
+	"net"
 	"strings"
 	"time"
 
@@ -129,6 +130,8 @@ type machineDoc struct {
 	// MachineAddresses is the set of addresses obtained from the machine itself.
 	MachineAddresses []address
 
+	DNSName string `bson:",omitempty"`
+
 	// PreferredPublicAddress is the preferred address to be used for
 	// the machine when a public address is requested.
 	PreferredPublicAddress address `bson:",omitempty"`
@@ -329,6 +332,10 @@ func (m *Machine) StopMongoUntilVersion() (mongo.Version, error) {
 	return mongo.NewVersion(m.doc.StopMongoUntilVersion)
 }
 
+func (m *Machine) DNSName() string {
+	return m.doc.DNSName
+}
+
 // IsManager returns true if the machine has JobManageModel.
 func (m *Machine) IsManager() bool {
 	return hasJob(m.doc.Jobs, JobManageModel)
@@ -1330,6 +1337,86 @@ func (m *Machine) SetProviderAddresses(addresses ...network.Address) (err error)
 	return nil
 }
 
+func preferredAddressesFromDNSName(hostname string) (*address, error) {
+	ips, err := net.LookupHost(hostname)
+	if err != nil {
+		return nil, errors.Annotatef(err, "cannot resolve hostname %q", hostname)
+	}
+
+	var preferredAddress network.Address
+	for _, ip := range ips {
+		// Update preferred private and public address with the results,
+		// preferring IPv4 results.
+		if netIP := net.ParseIP(ip); netIP.To4() == nil {
+			logger.Infof("skipping IPv6 address %q resolved from hostname %q", netIP, hostname)
+			continue
+		}
+		if preferredAddress.Value != "" {
+			logger.Infof("preferred address so far %q, ignoring extra %q", preferredAddress, ip)
+			continue
+		}
+		preferredAddress = network.NewAddress(ip)
+	}
+
+	if preferredAddress.Value == "" {
+		return nil, errors.Errorf(
+			"cannot resolve %q to a suitable IPv4 address for private and public address, got: %v",
+			hostname, ips,
+		)
+	}
+
+	statePreferredAddress := fromNetworkAddress(preferredAddress, OriginProvider)
+	logger.Infof(
+		"hostname %q resolves to preferred private and public address %q",
+		hostname, preferredAddress,
+	)
+	return &statePreferredAddress, nil
+}
+
+func (m *Machine) SetDNSName(hostname string) (err error) {
+	defer errors.DeferredAnnotatef(&err, "cannot set dns-name %q for machine %q", hostname, m.Id())
+
+	logger.Infof(
+		"setting machine %q hostname %q and updating preferred public %q and private %q addresses",
+		m.Id(), hostname, m.doc.PreferredPublicAddress, m.doc.PreferredPrivateAddress,
+	)
+
+	statePreferredAddress, err := preferredAddressesFromDNSName(hostname)
+	if err != nil {
+		return errors.Trace(err)
+	}
+
+	ops := []txn.Op{{
+		C:      machinesC,
+		Id:     m.doc.DocID,
+		Assert: isAliveDoc,
+		Update: bson.D{{"$set", bson.D{
+			{"dnsname", hostname},
+			{"preferredpublicaddress", *statePreferredAddress},
+			{"preferredprivateaddress", *statePreferredAddress},
+		}}},
+	}}
+
+	buildTxn := func(attempt int) ([]txn.Op, error) {
+		if attempt > 0 {
+			if m, err = m.st.Machine(m.doc.Id); err != nil {
+				return nil, err
+			}
+		}
+		if m.doc.Life != Alive {
+			return nil, errNotAlive
+		}
+		return ops, nil
+	}
+	if err := m.st.run(buildTxn); err != nil {
+		return err
+	}
+	m.doc.DNSName = hostname
+	m.doc.PreferredPrivateAddress = *statePreferredAddress
+	m.doc.PreferredPublicAddress = *statePreferredAddress
+	return nil
+}
+
 // ProviderAddresses returns any hostnames and ips associated with a machine,
 // as determined by asking the provider.
 func (m *Machine) ProviderAddresses() (addresses []network.Address) {
diff --git a/worker/provisioner/provisioner_task.go b/worker/provisioner/provisioner_task.go
index cca28da..93f6033 100644
--- a/worker/provisioner/provisioner_task.go
+++ b/worker/provisioner/provisioner_task.go
@@ -725,8 +725,14 @@ func (task *provisionerTask) startMachine(
 	volumes := volumesToApiserver(result.Volumes)
 	volumeNameToAttachmentInfo := volumeAttachmentsToApiserver(result.VolumeAttachments)
 
+	dnsName, err2 := result.Instance.DNSName()
+	if err2 != nil {
+		logger.Errorf("getting instance %q dns-name: %v", result.Instance.Id(), err2)
+	}
+
 	if err := machine.SetInstanceInfo(
 		result.Instance.Id(),
+		dnsName,
 		startInstanceParams.InstanceConfig.MachineNonce,
 		result.Hardware,
 		networkConfig,