Introduction

The Internet was originally conceived as a homogeneous global network in which all hosts would implement the network protocol Internet Protocol version 4 (IP or IPv4) [20], have globally unique unicast IP addresses for identification and routing purposes, and could freely communicate with each other. But as the Internet evolves, it is becoming a heterogeneous network (as depicted in Figure 1(a)). In the process, bi-directional connectivity between hosts is lost. That is, given a pair of hosts, sometimes a connection can be established only if it is initiated by a particular side, and sometimes a connection cannot be established at all.

Figure 1: (a) Heterogeneous address spaces (b) IPv6 dual-stack strategy

The root of the problem is that with the rapid growth of the Internet and the inefficient utilization of the IP address space, it has become clear that the relatively small 32-bit address space defined by IP is insufficient. The danger of exhausting the IP address space has prompted the Internet Assigned Numbers Authority (IANA) to conserve the remaining IP address space. This has resulted in two important development trends.

First, to get around the IP address shortage problem, it is increasingly common for networks ranging from large corporate networks to small home networks to be deployed using reusable-IP addresses. By connecting a reusable-IP network to the IP Internet through a Network Address Translation (NAT) [25] gateway, uni-directional connectivity to the IP Internet is provided. That is, in general, reusable-IP hosts can initiate connections to IP hosts but not vice versa. Moreover, between two reusable-IP hosts belonging to different networks, there is generally no connectivity. Thus, hosts inside reusable-IP networks are not first-class Internet entities.

Second, as a long term solution, the IETF has designed the Internet Protocol version 6 (IPv6) [4] which defines an enormous 128-bit address space. Ideally, all new networks should now be deployed using IPv6, and all existing IP and reusable-IP networks should be upgraded to IPv6. However, since upgrading to IPv6 is a gradual process, IP and reusable-IP networks will remain in the foreseeable future. In addition, although new IPv6 networks can be fully compatible with IP when the dual-stack transition mechanism [8] is used, to achieve full transparency, every IPv6 host must be assigned an IP address and essentially behave as both an IPv6 and an IP host simultaneously as shown in Figure 1(b). Obviously, for many IPv6 network operators, this is simply not a viable option. Thus, a significant portion of IPv6 networks will likely be deployed as IPv6-only networks, and they will only have uni-directional connectivity to the IP Internet via Network Address Translation - Protocol Translation (NAT-PT) [27] gateways similar to the reusable-IP network scenario.

These development trends clearly indicate that the Internet today and in the foreseeable future will be a heterogeneous network composed of IP, IPv6 and reusable-IP address spaces as shown in Figure 1(a), and the fundamental bi-directional connectivity property of the Internet has been destroyed. In this environment, many common applications are no longer usable. Recent interest in peer-to-peer applications has raised awareness of this problem because under these applications there is no longer a distinction between client versus server and bi-directional connectivity is crucial. An important challenge is: How can the lost connectivity in this heterogeneous environment be restored to as high a degree as possible? The obvious difficulty is that, without IP addresses, non-IP hosts (i.e. reusable-IP or IPv6 hosts) cannot be directly addressed by IP hosts, therefore IP hosts cannot initiate connections to non-IP hosts directly. Any general solution to this problem must therefore allow a non-IP host to be identified by an identifier other than an IP address, and the identifier must be mapped to the actual non-IP host during communication.

To date, no known solution to this problem can provide general bi-directional connectivity and at the same time be deployed easily. Of the known solutions, which are discussed in Section 7, some are specific to one application (e.g. HTTP virtual hosting), some are application independent but require per application manual configurations and cannot provide general bi-directional connectivity (e.g. port forwarding), and some can provide general bi-directional connectivity but require upgrades to existing IP hosts or IP network edge routers (e.g. SOCKS-based proposal). In practice, these upgrades to existing IP hosts or IP network edge routers are either too daunting to carry out, or there is no incentive to carry them out in the first place because they are aimed to benefit non-IP hosts and do not directly benefit existing IP hosts and networks.

In this paper, our aim is to design a solution that not only provides general bi-directional connectivity but also requires as little upgrades to existing software and hardware as possible. To achieve this goal, we propose a network layer waypoint service called AVES. Waypoints are 3rd-party network agents. The key idea is to virtualize non-IP hosts by a set of IP addresses assigned to waypoints. In this approach, we use DNS [15] names as identifiers for non-IP hosts and dynamically bind non-IP hosts to waypoint IP addresses during DNS name resolution in a connection-initiator-specific fashion. The waypoints then act as relays to connect IP hosts to non-IP hosts through AVES-aware NAT gateways.This scheme allows every IP host to simultaneously connect to as many non-IP hosts as the number of waypoint IP addresses. As a result, high connectivity is achieved even when a small number of IP addresses are used. The internetworking heterogeneity is handled by the waypoints, no upgrade to existing IP hosts or IP network routers is required, making non-intrusive deployment of AVES possible. This approach is unique because it addresses an internetworking problem without changing the network layer of existing systems besides the NAT gateways.

It is important to note that AVES is optimized for deployment and is not perfect in every regard. In particular, AVES trades performance for deployability. It turns out that, since the binding of non-IP hosts to waypoint IP addresses during DNS name resolution is the critical step, the more control we have over the local DNS servers used by IP initiators, the better AVES can perform. However, in the extreme case where we have no control over the local DNS servers, AVES still provides the same connectivity but at the cost of lowered performance.

In Section 2, we further motivate the heterogeneous address space connectivity problem with a case study and precisely formulate the problem. We present the design of AVES in Section 3, and discuss its connectivity and deployability properties in Section 4. We have implemented a complete prototype of AVES on Linux and the details are presented in Section 5. In Section 6, we discuss key concerns about AVES such as application compatibility, scalability, and security. Finally, we discuss related work in Section 7 and summarize the paper in Section 8.