[Docs] [txt|pdf] [Tracker] [Email] [Nits]

Versions: 00 01 02 03 04 05 06 07 08 09 10 11 12 13

Internet Draft                                     L. Huang
<draft-licanhuang-dnsop-distributeddns-00.txt>     ZST University
Category: Informational
Expires  July 2007                                   January 18, 2007

                 Distributed DNS Implementation in IpV6
             <draft-licanhuang-dnsop-distributeddns-00.txt>

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]


Html markup produced by rfcmarkup 1.123, available from https://tools.ietf.org/tools/rfcmarkup/