In the foreseeable future, three types of address spaces will coexist
in the Internet, they are IP, IPv6, and
reusable-IP. Table 1 describes the connectivity
between all combinations of the three address space types. In a
connection, the initiator is the ``caller'' host that sends the first
packet to start the connection; the responder is the ``callee'' host
that answers the in-coming connection. For example, to connect a
reusable-IP (R-IP) initiator to an IP responder, it is well known that
NAT  can be used and it works well in practice. Similarly,
NAT-PT  can be used to connect an IPv6 initiator
to an IP responder. On the other hand, to connect an IP initiator to
an IPv6 responder (case (a), Table 1), or to
connect an IP initiator to a reusable-IP responder (case (b),
Table 1) is hard because the responder does not
have any IP address and the initiator cannot address the responder
directly. Solving these problems is the key challenge in maintaining
the bi-directional connectivity abstraction of the Internet.
We emphasize that the problems underlying case (a) and case (b) are essentially identical, except that case (a) requires additional packet header format conversion which has been well documented in [18,27]. Thus for simplicity, for the remainder of this paper, we only consider case (b), where an IP initiator is connecting to a reusable-IP responder. The results can be mapped to case (a).
Note that because there are multiple coexisting instances of the reusable-IP address space, connecting a reusable-IP initiator to a reusable-IP responder in a different instance of the address space is non-trivial. However, under NAT, this is equivalent to the initiator's NAT gateway (which is an IP host) connecting to the reusable-IP responder. Therefore, this case can be reduced to case (b) as indicated in Table 1. Similarly, connecting a reusable-IP initiator to an IPv6 responder reduces to case (a), and connecting an IPv6 initiator to a reusable-IP responder reduces to case (b).
In summary, the key difficulty in achieving bi-directional connectivity across heterogeneous address spaces is to provide connectivity from IP hosts to non-IP hosts.