The Internet was designed to interconnect a few hundreds networks, but now has more than a billion hosts. The scalability issues associated with this growth have driven both academia and industry to review the current architecture in the light of the Locator/Identifier Split paradigm. However, changing the routing and addressing architecture of the Internet in an incrementally deployable manner imposes several constraints. The authors use the IETF's Locator/Identifier Separation Protocol (LISP) as a reference to describe different design choices necessary to achieve deployability, which is the ultimate goal of any future Internet architecture.