DNS provides a global-scale distributed lookup service to retrieve data of all types for a given name, be it IP addresses, service records, or cryptographic keys. This service has proven essential in today's operational Internet. Our experience with the design and development of Named Data Networking (NDN) suggests the need for a similar always-on lookup service. To fulfill this need we have designed the NDNS (NDN DNS) protocol, and learned several interesting lessons through the process. Although DNS's request-response operations seem closely resembling NDN's Interest-Data packet exchanges, they operate at different layers in the protocol stack. Comparing DNS's implementations over IP protocol stack with NDNS's implementation over NDN reveals several fundamental differences between applications designs for host-centric IP architecture and data-centric NDN architecture.