Many distributed applications build overlays on top of the Internet. Several unsolved issues at the network layer can explain this trend to implement network services such as multicast, mobility and security at the application layer. On one hand, overlays creating basic topologies are usually limited in flexibility and scalability. On the other hand, overlays creating complex topologies require some form of application level addressing, routing and naming mechanisms. Our aim is to design an efficient and robust addressing, routing and naming architecture for these complex overlays. Our only assumption is that they are constrained by the Internet topology. Applications that use our middleware will be relieved from managing their own overlay topologies. Our architecture is based on the separation of the naming and the addressing plans. To implement this property, we have designed a scalable distributed kresilient name to address binding system. This paper describes its design and presents some performance results concerning its scalability, its efficiency and its resilience.