Discovering Agents for Discovery: The Case for DNS
arXiv:2606.02314v1 [cs.NI] 1 Jun 2026
Ramachandra Rao Seethiraju Verisign [email protected]
Sameer Thakar Verisign [email protected]
Karthik Shyamsunder Verisign [email protected]
Eric Osterweil Verisign [email protected]
Abstract As Artificial Intelligence (AI) agents enter their next stage of being deployed ubiquitously throughout the Internet, their discoverability will become a central challenge. The information AI agents need to discover one another, how they will locate it, how to facilitate authentication, integrity, and authorization, how to connect across different platforms, and how to scale across organizational boundaries form a set of unanswered challenges that deployment success will prompt. These are challenges for which one of the Internet’s most venerable, solid, and ubiquitous infrastructures is ideally suited: The Domain Name System (DNS). Such a rich, already ubiquitous, and programmatically flexible foundation is an ideal option for discovery of AI agents. In this work, we propose an illustration and rationale for the basic semantics that discovery for AI agents will require. We argue that three key evaluation criteria will become paramount: navigational completeness (the extent to which the necessary metadata, with elements like trust, is included in a discovery solution), lookup complexity, and transaction performance (e.g., latency, speed, or recency). Using data about 119,757 real-world service endpoints and multiple agent tooling ecosystems, we empirically evaluate the first of these considerations to illustrate the appropriateness of using DNS for AI agent discovery. Our results show the size and amount of data necessary are well within the range of a single DNS UDP transaction, whose latency can be on the order of milliseconds. Our evaluations illustrate a promising path toward enabling AI agent discoverability at the Internet’s scale, and thereby accelerating secure, stable, and resilient AI agent deployments.
1
Introduction
As Artificial Intelligence (AI) agents rapidly grow onto the Internet, their future is here today. AI agents are automating actions, discovering data, and discovering each other! However, their initial settings have largely been in tame “closed world” deployments. Evolving and deploying them into the wild of the Internet necessarily introduces many basic challenges that AI agent discovery has not previously needed to face. This frames one of the most foundational challenges: how can AI agents search, hypothesize, and optimize across science, engineering, and infrastructure? We argue that secure discovery is a broad topic, whether AI agents are discovering data, agents, or agents that operate on data. Additional challenges exist, but we propose that establishing a general approach for secure AI agent discovery is a necessary first step. As AI agents begin to grow out of “closed world” deployments, they will face axiomatic challenges. In closed worlds, named AI agents can homogeneously discover each other through their native platforms. For example, Claude agents can discover other Claude agents by name, and ChatGPT Preprint.
agents can discover other ChatGPT agents in a similar manner. However, these agents do not inherently discover and interoperate homogeneously across platforms (e.g., Claude-to-ChatGPT). AI agents in homogeneous settings discover each other by name, and through closed system (i.e., platform) registries of names. This does not immediately befit the Internet setting. For any agent to discover any other agent at the Internet’s scale, agents will need names on the Internet. This is the function of the Domain Name System (DNS) [18]. However, beyond just names, AI agents need to be associated with capabilities, be able to authenticate, establish integrity protections, identify service endpoints, and locate security status mechanisms. Work to address these considerations is underway in the Interent Engineering Task Force (IETF) and other communities. Notable examples of this work are DNS for AI Discovery (DNS-AID) [19], and the Agent Name Service (ANS) [4], as well as a growing list of others [15]. However, which of these candidate proposals provide the most appealing solutions, how well do they fit AI agents’ requirements, and how can they be evaluated? In this work, we propose a baseline set of considerations for using DNS to enable AI agent discovery on the Internet. We propose an evaluation framework that identifies a set of basic metadata needed for association and three performance evaluation criteria. These criteria are navigational completeness (which centers on metadata size), lookup complexity, and transaction performance. Our early results of the metadata size criterion show that DNS, its Security Extensions (DNSSEC) [24, 26, 25], together with DANE-like certificate binding mechanisms (e.g., the DNS-Based Authentication of Named Entities (DANE) [13]), can hit a sweet spot. Our evaluation shows that the set of necessary and sufficient metadata needed for AI agent discovery can fit within a single unfragmented UDP DNS message, and can therefore be retrieved in a single round-trip time (RTT), and can be delivered over the User Datagram Protocol (UDP) with latencies on the order of milliseconds. This is the same performance achieved by the hundreds of billions of daily DNS transactions, which have supported the world wide web for decades.
2
State of Play
The DNS is a valuable infrastructure. It is a general distributed database that allows globally unique names to map to arbitrary service identifiers. In addition to IP addresses, these identifiers include cryptographic keys, policy directives for email, and service bindings (e.g., the SVCB record [27]). This set of data types, and the DNS itself, are actively being extended. Recent work to reconsider DNS’ delegation structure (the deleg working group [16]) initially considered SVCB records as a foundation but settled on a new record type with some common features. At its core, however, the DNS is designed to operate at extremely high speeds, where query/response transactions are measured in milliseconds. Coupled with this, DNSSEC adds security assurances that cryptographically bind domain names to their rightful origins and protect their integrity [22]. These reasons underscore the growing interest in using DNS for this challenge. For example, DNSAID constructs AI agents’ names as DNS domain names that include the agents’ capabilities, and requires DNSSEC. Those names are then mapped to DNS service binding records (SVCB). DNS-AID then encodes other necessary metadata and pointers to metadata into those records. This includes service endpoints. In addition, DNS-AID uses DANE TLSA records to establish origin authentication, integrity, and confidentiality protections for the AI agents’ specified endpoints. In DNS-AID, discovering agents issue multiple queries for metadata, and for TLS authentication information. Another recent approach, ANS, also makes use of DNS domain names. As with DNS-AID, ANS requires multiple lookups to acquire all of the necessary and sufficient information for AI agent discovery. Its design uses an additional (non-DNS) registry to fully resolve its metadata. In summary, across the growing innovation space of AI agent discovery, we observe varied sets of metadata being encoding, variable numbers of lookups required, different numbers of external registries, and potentially diverse range of network transaction overheads.
3
A Framework for Evaluating Cross-Platform AI Agent Discovery
The breadth and scope of the landscape of AI agent discovery proposals is large and growing. This clearly frames the need for our work here: a framework for evaluating considerations. To construct this framework, we first identify the necessary set of metadata that is sufficient to enable AI agent discovery at the Internet scale. To do this, we begin by synthesizing several prominent current 2
Figure 1: Left: endpoint length ECDF. Middle: MCP tool namespace footprint ECDF. Right: 90th percentile DNS response size vs. 1,232B limit.
approaches, such as [19, 4]. From this synthesis, we extract that, for “navigational completeness,” AI agent discovery needs names to be “associated” with a core set of metadata the enables: identifying and determining where another agent is located (locatability), being able to interpret what functionality it provides (capability awareness), understanding how to communicate with it (protocol awareness), and establishing the authenticity and integrity of both the retrieved metadata and the actual connection with the agent. Across the different discovery proposals, these necessary metadata elements are encoded and served differently, which leads to different lookup requirements. The next aspect of our evaluation framework is the “lookup complexity.” This involves the requirements for agents to discover and obtain the sufficient set of metadata needed. For example, the ANS approach requires a DNS lookup (or “resolution”) for the domain name component of an agent’s ANS name. Then it requires additional lookups for the agent’s DANE (TLSA) and several other records. It further requires a lookup to the specified ANS agent registry. Alternately, the DNS-AID approach first requires a single lookup for an agent’s name, which retrieves a corresponding SVCB record. Then, however, it requires a DANE lookup and, because some of the elements in the SVCB refer to external registries, it requires further lookups before a connection can be established to a discovered agent. Looking these elements up in separate registries increases the complexity of this step. This necessarily affects the performance and latency of these lookups, as they will be additive and vary in performance because some of the above transactions are over DNS (e.g., the DANE and SVCB queries), and some involve HTTPS lookups. In concert with the lookup complexity, the overall reliability and efficiency of the “transaction performance” of AI agent discovery forms the third component of our framework. Our synthesis reveals a tradeoff the different proposals make. Some involve combinations of UDP-centric protocols (like the DNS) and TCP-centric protocols (like HTTPS). Our framework illustrates that these decisions will have quantitative impacts on the overall performance and scalability of solutions. Taken together, the above three elements for the basis for our evaluative framework. These form the foundation for our evaluation framework.
4
Evaluation of DNS as a Case Study
As an initial illustration of our evaluation framework, we focus on the first consideration: navigational completeness, which involves the size of sufficient metadata, including all necessary metadata, from all necessary registries. Due to the scarcity of live AI agent endpoints, we approximate agent metadata using real-world service and tooling ecosystems. Endpoint sizes are derived from API endpoint URLs in the APIs.guru dataset [2, 1] , while capability identifiers are derived from the MCPZoo [30] dataset, which is a corpus of live deployed MCP servers. From MCPZoo, we empirically measure the number of capabilities exposed per server and the lengths of capability identifiers observed from actual MCP servers deployed in the wild. Protocol identifiers are drawn from a limited set of interaction protocols (e.g., MCP, A2A). From the APIs.guru dataset we extract 143,634 endpoint observations, reduced to 119,757 unique endpoints after deduplication. Figure 1 shows that endpoint values are tightly distributed, with a median of 70 bytes and a 90th percentile of 108 bytes. To evaluate capability size requirements, we analyzed 62,739 indexed MCP server entries from MCPZoo [30] and extracted MCP tool declarations 3
directly from source code using pattern-based parsing, without executing the MCP servers at runtime. In our evaluation, we treat MCP tool identifiers as operational capability identifiers exposed by deployed AI, since they represent externally discoverable and invokable agent functionality. We found that 13,607 servers (21.7% of the corpus) contained at least one detectable MCP tool declaration. Within this subset, we observed a median of 3 MCP tools per server and a 90th-percentile (P90) value of 19 MCP tools per server. Across 128,653 extracted MCP tool names, the median tool-name length was 16 characters and the P90 tool-name length was 26 characters. Using the empirically observed per-server capability namespace footprint, defined as the sum of tool-name lengths within a server, we measured a median footprint of 49 characters per MCP server and an empirical P90 footprint of 323 characters per MCP server. Additionally, to derive a conservative upper-bound for capability sizing analysis, we combine the independent P90 measurements for MCP tool count and tool-name length, yielding a worst-case P90 capability footprint estimate of approximately 494 characters per MCP server (19 MCP tools × 26 characters/tool), as shown in Figure 1). Upon aggregation, the 90th-percentile agent metadata size is 108 + (19 × 26) + 7 = 609 bytes. Applying DNSSEC ensures authenticity and integrity of the domain names. To evaluate the impact of this, we include RRSIG overhead based on the record structure defined in RFC 4034 [26] and signature sizes specified in RFC 6605 [14]. ECDSA P-256 signatures are 64 bytes and RRSIG fields contribute approximately 40 bytes, yielding a DNSSEC overhead of (64 + 40) = 104 bytes. Although DNSSEC deployments are increasingly moving toward ECDSA P-256 due to its smaller signatures and operational advantages [29, 28], we use RSA-2048 as a conservative upper-bound. An RSA-2048 signature contributes 256 bytes and RRSIG fields contribute approximately 40 bytes, or (256 + 40) = 296 bytes. Therefore, the total DNS response size becomes: 609 + 296 = 905 bytes. To support the transaction security of AI agent discovery, agents must bind service endpoints to cryptographic identities. We model this using certificate association data, as in DANE-like mechanisms [13]. In such mechanisms, a compact representation of the certificate (typically a cryptographic hash) is stored in DNS along with a small set of control fields that define how the certificate should be interpreted. In practice, SHA-256 is the most widely used matching type, as it is mandatory to implement, while SHA-512 is optional [8]. Accordingly, the certificate is represented as a 32-byte SHA-256 hash (or a 64-byte for SHA-512). Including the associated control fields, this results in an overhead of approximately 35 bytes for SHA-256 [13, 8]. Including SHA-256 certificate association data, the metadata size becomes: 905 + 35 = 940 bytes. All together, at the 90th percentile, DNS responses with agent metadata, certificate association, and DNSSEC are therefore 940 bytes. Adding the 20 byte DNS header and a 20 byte query name (980 total bytes), this is only 79.5% of the 1,232-byte UDP response-size target associated with PMTU constraints [9, 22]. Prior work shows that DNS responses exceeding this target require fragmentation or TCP fallback, both of which introduce reliability challenges [3, 10], with failure rates of approximately 0.1–0.3% in operational deployments [11]. We find initial evidence that even under conservative assumptions, agent metadata can be encoded within a single DNS message, whose size would be smaller than where fragmentation-related reliability issues would arise. When metadata spans multiple records, tradeoffs arise in query count and resolution latency. Modern DNS deployments support responses of this size through EDNS(0) [6], with TCP fallback [7] used when necessary, indicating that metadata size alone does not prevent DNS-based agent discovery. Limitations: This evaluation relies on indirect data sources rather than measurements from deployed agentic AI systems. While existing endpoint APIs capture real-world structure, tooling ecosystems reflect emerging agent behaviors, and patterns are emerging for capability characteristics, these only approximate future AI agents’ needs. Nevertheless, this work focuses on metadata size as a feasibility condition. More exhaustive evaluation is left for future work.
5
Discussion, Future Work, and a Call to Action
AI agent ecosystems are evolving toward open, cross-platform interaction, where agents must discover and interpret each other without centralized coordination. This creates the need for mechanisms that expose machine-consumable metadata for locating, understanding, and verifying agents. We argue that an evaluation framework is critical for developing infrastructure for AI agent discovery. We propose a framework that identifies three key dimensions: navigational completeness, lookup 4
complexity, and transaction performance. Using this, we conduct a data-driven evaluation showing that the required metadata, including certificate association and DNSSEC, can fit within a single DNS response over UDP. This suggests that a discovery protocol could involve a single DNS lookup, and might be able to run over DNS, regardless of the number of lookups at Internet scale. As future work, we will extend this evaluation to a broader set of open-world AI agent discovery systems, including decentralized index-based systems (e.g., Project NANDA [23]), directory and registry-based systems (e.g., AGNTCY [20]), and naming-based approaches (e.g., DNS-ID [17], .agent [12], AgentDNS [5]). Applying our framework across these approaches will enable systematic comparison of how different designs measure against navigational completeness and impact lookup complexity and transaction performance. Finally, while this work focuses on metadata size as a feasibility condition, evaluating navigational completeness across specific proposals, as well as query complexity and latency, remains an important direction for future research. As a call to action, we propose that the DNS is a great start for AI agent discovery. While the DNS is not a search system, it does provide an authoritative and widely deployed infrastructure for making agent metadata discoverable, interoperable, and navigable. It has served as the Internet’s naming system since the 1980s, which is demonstrably ready to be extended [21] into the wild and critical world of AI agents
References [1] APIs.guru. API Index. https://api.apis.guru/v2/list.json : Accessed: May 2026. [2] APIs.guru. OpenAPI Directory. https://github.com/APIs-guru/openapi-directory : Accessed: May 2026. [3] Ron Bonica, Fred Baker, Geoff Huston, Bob Hinden, Ole Trøan, and Fernando Gont. IP Fragmentation Considered Fragile. RFC 8900, September 2020. [4] Scott Courtney, Vineeth Sai Narajala, Ken Huang, Idan Habler, and Akram Sheriff. Agent Name Service v2 (ANS): A Domain-Anchored Trust Layer for Autonomous AI Agent Identity. Internet-Draft draft-narajala-courtney-ansv2-01, Internet Engineering Task Force, April 2026. https://datatracker.ietf.org/doc/draft-narajala-courtney-ansv2/01/ : Accessed: May 2026. [5] Enfang Cui, Yujun Cheng, Rui She, Dan Liu, Zhiyuan Liang, Minxin Guo, Tianzheng Li, Qian Wei, Wenjuan Xing, and Zhijie Zhong. AgentDNS: A Root Domain Naming System for LLM Agents, 2025. https://arxiv.org/abs/2505.22368 : Accessed: May 2026. [6] Joao Luis Silva Damas, Michael Graff, and Paul A. Vixie. Extension Mechanisms for DNS (EDNS(0)). RFC 6891, April 2013. [7] John Dickinson, Sara Dickinson, Ray Bellis, Allison Mankin, and Duane Wessels. DNS Transport over TCP - Implementation Requirements. RFC 7766, March 2016. [8] Viktor Dukhovni and Wes Hardaker. The DNS-Based Authentication of Named Entities (DANE) Protocol: Updates and Operational Guidance. RFC 7671, October 2015. [9] Kazunori Fujiwara and Paul A. Vixie. IP Fragmentation Avoidance in DNS over UDP. RFC 9715, January 2025. [10] Jason Goertzen and Douglas Stebila. Post-Quantum Signatures in DNSSEC via Request-Based Fragmentation, 2022. https://arxiv.org/abs/2211.14196. [11] Google Public DNS. Google public experiment results, 2020. https://github.com/dnsviolations/dnsflagday/issues/139#issuecomment-673489183 : Accessed: May 2026. [12] Headless Domains. .agent: Headless domains for agentic applications, 2025. https://headlessdomains.com/agent : Accessed: May 2026. [13] Paul E. Hoffman and Jakob Schlyter. The DNS-Based Authentication of Named Entities (DANE) Transport Layer Security (TLS) Protocol: TLSA. RFC 6698, August 2012. 5
[14] Paul E. Hoffman and Wouter Wijngaards. Elliptic Curve Digital Signature Algorithm (DSA) for DNSSEC. RFC 6605, April 2012. [15] IETF DAWN Mailing List. Discussion of Discovery of Agents, Workloads, and Named entities (DAWN). IETF Mail Archive. https://mailarchive.ietf.org/arch/browse/dawn/. [16] IETF DELEG Working Group. DNS Delegation (deleg) Working Group. IETF Datatracker. https://datatracker.ietf.org/group/deleg/about/. [17] Naveed Ihsanullah. DNS-Anchored Durable Identity for AI Agents (DNSid). Internet-Draft draft-ihsanullah-dnsid-00, Internet Engineering Task Force, April 2026. Work in Progress. [18] Paul Mockapetris and Kevin J. Dunlap. Development of the Domain Name System. In Symposium proceedings on Communications architectures and protocols (SIGCOMM), pages 123–133, 1988. [19] Jim Mozley, Nic Williams, Behcet Sarikaya, and Roland Schott. DNS for AI Discovery. Internet-Draft draft-mozleywilliams-dnsop-dnsaid-01, Internet Engineering Task Force, March 2026. https://datatracker.ietf.org/doc/draft-mozleywilliams-dnsop-dnsaid/01/. [20] Luca Muscariello, Vijoy Pandey, and Ramiz Polic. The AGNTCY Agent Directory Service: Architecture and Implementation, 2025. https://arxiv.org/abs/2509.18787 : Accessed: May 2026. [21] Eric Osterweil. A Cybersecurity Terminarch: Use It Before We Lose It. IEEE Security & Privacy, 18(4):67–70, 2020. [22] Eric Osterweil, Dan Massey, and Lixia Zhang. Deploying and Monitoring DNS Security (DNSSEC). In 2009 Annual Computer Security Applications Conference (ACSAC), pages 429–438. IEEE, 2009. [23] Ramesh Raskar, Pradyumna Chari, John Zinky, et al. Beyond DNS: Unlocking the Internet of AI Agents via the NANDA Index and Verified AgentFacts, 2025. https://arxiv.org/abs/2507.14263 : Accessed: May 2026. [24] Scott Rose, Matt Larson, Dan Massey, Rob Austein, and Roy Arends. DNS Security Introduction and Requirements. RFC 4033, March 2005. [25] Scott Rose, Matt Larson, Dan Massey, Rob Austein, and Roy Arends. Protocol Modifications for the DNS Security Extensions. RFC 4035, March 2005. [26] Scott Rose, Matt Larson, Dan Massey, Rob Austein, and Roy Arends. Resource Records for the DNS Security Extensions. RFC 4034, March 2005. [27] Benjamin M. Schwartz, Mike Bishop, and Erik Nygren. Service Binding and Parameter Specification via the DNS (SVCB and HTTPS Resource Records). RFC 9460, November 2023. [28] Verisign. Strengthening Security with DNSSEC Algorithm Update, https://blog.verisign.com/security/dnssec-algorithm-update/ : Accessed: May 2026.
2023.
[29] Paul Wouters and Ondřej Surý. Algorithm Implementation Requirements and Usage Guidance for DNSSEC. RFC 8624, June 2019. [30] Mengying Wu, Pei Chen, Geng Hong, Baichao An, Jinsong Chen, Binwang Wan, Xudong Pan, Jiarun Dai, and Min Yang. MCPZoo: A Large-Scale Dataset of Runnable Model Context Protocol Servers for AI Agent, 2025. https://arxiv.org/abs/2512.15144 : Accessed: May 2026.
6