Internet Draft L. Huang ZST University Category: Informational Expires July 2007 January 18, 2007 Distributed DNS Implementation in IpV6 Status of this Memo Distribution of this memo is unlimited. By submitting this Internet-Draft, each author represents that any applicable patent or other IPR claims of which he or she is aware have been or will be disclosed, and any of which he or she becomes aware will be disclosed, in accordance with Section 6 of BCP 79. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF), its areas, and its working groups. Note that other groups may also distribute working documents as Internet-Drafts. Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress." The list of current Internet-Drafts can be accessed at http://www.ietf.org/1id-abstracts.html The list of Internet-Draft Shadow Directories can be accessed at http://www.ietf.org/shadow.html. Abstract This file is a proposal for P2P based DNS query stratagy in IpV6. The DNS servers construct n-tuple overlay virtual hierarchical overlay network.With cached addresses of DNS servers, the overload of traffic in tree structure can be avoided. This strategy may use for DNS query in IpV6 for a large number of domain names. Huang, Lican Expires July 2007 FORMFEED[Page 1] Internet Draft DNS Impl in IPv6 January 18, 2007 Table of Contents 1. Introduction ................................................2 2. Virtual Hierarchical Overlay Network for DNS ................2 2.1 DNS Query Strategy ......................................3 2.2 Route Table Definitions.................................5 3. Some Notes ..................................................6 4. Appendix A: protocols of establishment and lookup ...........6 5. References ..................................................9 1. Introduction This file is a proposal for P2P based DNS query stratagy in IpV6. The DNS servers construct n-tuple overlay virtual hierarchical overlay network. With cached addresses of DNS servers, the overload of traffic in tree structure can be avoided. This strategy may use for DNS query in IpV6 for a large number of domain names. There are huge numbers of IP address in IpV6. Moreover, there may be use case for multi domain names associated with a sigle IP address. DNS implementation currently used may encounter overload traffic in root DNS servers. This document uses VIRGO[VIRGO] overlay network to solve the above problem. VIRGO is a multi-tuple virtual hierarchical overlay network with cached node address. We here change some places to suit the distributed DNS implementation. 2. Virtual Hierarchical Overlay Network for DNS Virtual Hierarchical Overlay Network for DNS is a hybrid of unstructured P2P and structured P2P technologies. The DNS servers construct multi-tuple Virtual Hierarchical Overlay Network. Some servers are only leaves of the network,others may coexist in different layers. Random connections cached in a DNS server's routing table are maintained. The servers in the same domain are fully connected. Unlike query pathes currently used in Domain Name Systems allways go to root servers, Virtual Hierarchical Overlay Network for DNS routes query message to the server with theoretical least hops from destination server. The route tables of Domain Name servers contains two kinds of route addresses, tree addresses which are prerequiste and cached addresses. The following is some terms related to the Virtual Hierarchical Overlay Network for DNS. Domain Name Server is a node which keeps local domain RRs[RFC1035]. All the Domain Name Servers are the same except some Domain Name Servers take the function of gateways in the meantime. Every Domain Name Server just controls the leaves of the domain. Every Domain Name Huang, Lican Expires July 2007 FORMFEED[Page 2] Internet Draft DNS Impl in IPv6 January 18, 2007 Server contains route table. Every Domain Name Server uses its controlled domain name by cutting off leaves and adding a number as its Identification, which is called as Domain Name Server Identification (DNSI).For example,for science.computer.network.Grid, science.computer.network.Wireless,etc., Domain Name Servers have Identifications -- science.computer.network.1, science.computer.network.2, etc. They keep RRs for science.computer.network.Grid,science.computer.network.Wireless,etc. Gateway is a node role which takes part in routing functions in several different layers of virtual groups. Gateway uppermost layer (denoted by GUL ) is the uppermost virtual group layer that the gateway is in. The layers are ordered from root layer which is labelled as level 1. Virtual group is formed virtually by the gateways nodes. The Group Name is part of the node's domain name, eg. in the above example, science, science.computer, science.computer.network are group names. N-tuple virtual group tree (denoted by NVGT) is a hierarchical tree formed by virtual groups. Among the nodes of the lower layer virtual groups, N-tuple gateway nodes in each group are chosen to form upper- layer groups, and from the nodes of these upper-layer groups to form upper-upper-layer groups in the same way, and this way is repeated until a root-layer group is formed. In the Virtual Hierarchical Overlay Network for DNS, all Domain Name Servers consist of N-tuple virtual group tree. The Virtual Hierarchical Overlay Network can be established by manual or automatedly by establishment protocol which is shown in Appendix A. 2.1 DNS Query Strategy Every DNS server is the same but some coexist in more than one layer. Every DNS Server maintains a route table and a RR record related to its Domain. Route table includes addresses of Foreign Name Servers which are prerequiste for Virtual Hierarchical Overlay Network and cached Foreign Name Servers which are refreshed by TTL rule. The query process is as the following figure shown. Huang, Lican Expires July 2007 FORMFEED[Page 3] Internet Draft DNS Impl in IPv6 January 18, 2007 Local Host | Foreign | +-------+ +--------+ | +-------+ _______ | | user queries | |queries | | | | | |User |------------->| |---------|->|Foreign|-->| Tree +| |Program| |Resolver| | | Name | | Cache | | |<-------------| |<--------|--| Server|<--|(route | | |user responses| |responses| | | | table)| +-------+ +--------+ | +-------+ |_______| | A | | A cache additions | | | | | V | | __V___|___ +----------------+ | | | ________ | Tree + | | |Foreign | | | | Cache | | | Name |-->| RR | | (route table) | | | Server|<--| | +----------------+ | | | |______| | |________| The query process is as the following: User program sends QUERY MESSAGE to Name Server (called as Resolver), If Resolve is the destination Domain Name Server, then the resolve will check its RR to resolve the request Domain name. Otherwise,Resolver routes to the Foreign Domain Name Server which is closer to the destination Domain Name Server by calculating theoretical hops. Then the Foreign Domain Name Server routes to the even closer Foreign Domain Name Server. Repeat this process, until the destination Domain Name Server has been found. Finally, the destination Domain Name Server resolves request Domain Name by check its RR record, and response to the User Program. The details of the algorithm can be found in Appendix A. Huang, Lican Expires July 2007 FORMFEED[Page 4] Internet Draft DNS Impl in IPv6 January 18, 2007 2.2 Route Table Definitions All Route Tables have the same top level format shown below, which is also called as Node Entity(NE): 1 1 1 1 1 1 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ | | / / / DNSI / | | +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ | TYPE | +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ | GUL | +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ | TTL | | | +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ | UTS | | | +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ | | +- IP ADDRESS | / / / / +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+ where: DNSI Domain Name Server Indetification of an Domain Server. TYPE two octets containing one of the route TYPE codes (TREE as 0, CHACHE as 1). GUL two octets containing the value of gateway upmost layer of the Domain Server. TTL a 32 bit signed integer that specifies the time interval that the route record may be cached before the source of the information should again be consulted. UTS Unreachable time stamp. If the route was cached, then reflesh it by TTL rule. If the route is gateway node in virtual tree structure, notice to manager to repair it. IP ADDRESS IP address of the Domain Server. Huang, Lican Expires July 2007 FORMFEED[Page 5] Internet Draft DNS Impl in IPv6 January 18, 2007 3. Some Notes High performance and stable computers are chosen as gateway nodes. Because the gateway node not only manages local RRs,but also routes messages. The virtual tree structure requires gateway node stable. Due to the prerequiste tree, every Domain Name Server can reach other ones. Due to redundant gateway nodes, the virtual tree can be allways maintaned. Due to the random cached nodes in the route table of every Domain Name Server, the route paths are randomly chosen. This may avoid the network trafic in tree-like structure. This may also enhance the security of the DNS. The time complexity, space complexity and message-cost of the proposed architecture is O(log N), where N is the total number of Domain Name Servers in the network. Therefore, domain name query is effective. 4. Appendix A: protocols of establishment and lookup 4.1 Names of Primitives and Functions and Their Descriptions sender.send (message,receiver), sender sends message to receiver sender.send(message,receiver (- Set), sender sends message to all the receivers belong to a Set RouteTableAdd(NE,type), add NE to route table lookup_location(DomainName),find the destination node's location LengthOfSamePrefix(DomainName,DomainName), length of shared prefixes between two nodes LengthOfDomainName(DomainName), the length of DomainName hopDistance2object(pi,DomainName), the theoretical hops from the node to the destination node selectRouteNodeFromRouteTable(DomainName), choose next hop node from route table checkupRRs(QUERYMESSAGE), retrieve RR record in RR database Huang, Lican Expires July 2007 FORMFEED[Page 6] Internet Draft DNS Impl in IPv6 January 18, 2007 4.2 Protocol of Network Establishment Here, a new Domain name server P_join joins the network. 1. P_join.send(JOINMESSAGE, P_groupToJoin) 2. P_groupToJoin.send(JOINMESSAGE, pi (- joinGroup); 3. (pi (- joinGroup).send(pi.APPROVEMESSAGE, P_join); (pi (- joinGroup).RouteTableAdd(P_join.NE,TREE); 4. P_join.RouteTableAdd(pi (- joinGroup.NE,TREE); 5. repeat step 2 to 4 in upper layer groups until replicated nodes no less than n-tuple or root group. 4.3 lookup protocol Step 1 UserProgram.send (QUERYMESSAGE, resolver) Step 2 DestinationDNServer = resolver.lookup_location(QUERYMESSAGE.DomainName) Step 3 RESULTMESSAGE= DestinationDNServer.checkupRRs(QUERYMESSAGE); Step 4 DestinationDNServer =send(RESULTMESSAGE, resolver); Step 5 resolver.send(RESULTMESSAGE, UserProgram); Step 6 resolver.RouteTableAdd(DestinationDNServer.NE,CHACHE); Where, function of lookup_location (locates the destination node by the minimum hops) is as following: Huang, Lican Expires July 2007 FORMFEED[Page 7] Internet Draft DNS Impl in IPv6 January 18, 2007 Function p.lookup_location(QUERYMESSAGE) { if LengthOfSamePrefix(p.DNSI,QUERYMESSAGE.DomainName)== LengthOfDomainName(QUERYMESSAGE.DomainName)-1 return p; else { routeP = p.selectRouteNodeFromRouteTable(QUERYMESSAGE.DomainName); p.send(QUERYMESSAGE,routeP); if (message sending is successful) routeP.lookup_location(QUERYMESSAGE); else { Mark routeP as unreachable in p.routetable; p.lookup_location(QUERYMESSAGE); } } } Where, function selectRouteNodeFromRouteTable(select route with theoretical least hops from destination Domain Name Server) is as following: Function p.selectRouteNodeFromRouteTable(requestDomainName) gnSet = Minimum(p.hopDistance2object(pi (- RouteTable,requestDomainName)); return routeP = random(gnSet); Where, function hopDistance2object ( calculating theoretical hops from destination Domain Name Server ) is as following: Huang, Lican Expires July 2007 FORMFEED[Page 8] Internet Draft DNS Impl in IPv6 January 18, 2007 Function p.hopDistance2object(pi,requestDomainName) if LengthOfSamePrefix(pi.DNSI, requestDomainName) ==1 return LengthOfDomainName(requestDomainName)+pi.GUL -2; elseif pi.GUL < LengthOfSamePrefix(pi.DNSI, requestDomainName) return LengthOfDomainName(requestDomainName) - LengthOfSamePrefix(pi.DNSI, requestDomainName); else return LengthOfDomainName(requestDomainName)+pi.GUL - 2*LengthOfSamePrefix(pi.DNSI,requestDomainName) 5. References 5.1. Informative References [RFC1035] P. Mockapetris, "DOMAIN NAMES - IMPLEMENTATION AND SPECIFICATION",Specification," RFC1035, USC/Information Sciences Institute,November, 1987. [VIRGO] Huang, L., "VIRGO: Virtual Hierarchical Overlay Network for Scalable Grid Computing ",Proc. European Grid Conference(EGC2005), in LNCS 3470, p911-921, 2005. Authors' Addresses Lican Huang Current Address: Institute of Network & Distributed Computing, Zhejiang Sci_Tech University, Hangzhou, P.R.China EMail: licanhuang@zist.edu.cn; huang_lican@yahoo.co.uk Huang, Lican Expires July 2007 FORMFEED[Page 9] Internet Draft DNS Impl in IPv6 January 18, 2007 Full Copyright Statement Copyright (C) The IETF Trust (2007). This document is subject to the rights, licenses and restrictions contained in BCP 78, and except as set forth therein, the authors retain all their rights. This document and the information contained herein are provided on an "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY, THE IETF TRUST, AND THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. Intellectual Property The IETF takes no position regarding the validity or scope of any Intellectual Property Rights or other rights that might be claimed to pertain to the implementation or use of the technology described in this document or the extent to which any license under such rights might or might not be available; nor does it represent that it has made any independent effort to identify any such rights. Information on the procedures with respect to rights in RFC documents can be found in BCP 78 and BCP 79. Copies of IPR disclosures made to the IETF Secretariat and any assurances of licenses to be made available, or the result of an attempt made to obtain a general license or permission for the use of such proprietary rights by implementers or users of this specification can be obtained from the IETF on-line IPR repository at http://www.ietf.org/ipr. The IETF invites any interested party to bring to its attention any copyrights, patents or patent applications, or other proprietary rights that may cover technology that may be required to implement this standard. Please address the information to the IETF at ietf-ipr@ietf.org. Huang, Lican Expires July 2007 FORMFEED[Page 10]