Research on the Next Generation Naming System

This work was funded by the National Basic Research Program of China (“973” Program) under Grant No. 2007CB307100.

    Currently, names in the Internet are domain names, and their resolution is provided by the Domain Name System (DNS). The goal of DNS is to map an IP address (which is often difficult to remember) into a meaningful character string that is easy to remember [1]. The advantages of DNS have been fully exploited, and DNS has quickly become the largest domain name system in the world. However, the simple design of early DNS means that it is challenged by today’s applications.

    First, the root DNS servers have too much authority. All domain name resolution requests that cannot be processed by the local DNS server are forwarded to the root servers. These root servers are controlled by the U.S. government. Therefore, if the U.S. government decided to modify the ROOTZONE files in the DNS root servers, some countries would disappear from the Internet [2].

    Second, the domain name is meaningful, and legal wrangling over domain ownership is common [3].

    Third, the DNS is host-oriented. After data in the host migrates or is replicated, the DNS cannot provide services for the data again [4].

    Fourth, loads are unbalanced among DNS servers. The servers responsible for resolving .com domain names have heavier loads than those responsible for resolving .org domain names. Moreover, there is no coordination mechanism for sharing network resources.

1 New Naming Systems Proposed by Academia
    To overcome DNS shortcomings, academia has proposed some new naming systems, of which the naming system introduced in [5] is representative. 

    Names are generated in the system using hashing algorithm; meta-data of a resource is first extracted, then a character string is generated by hashing the meta-data. This character string is the resource’s network name. Because the name is based on meta-data of the resource, it does not change when the resource migrates or is replicated. It is transparent to all users and can be used to locate the resource at any time. Therefore, the problem is solved whereby services become unavailable once a resource migrates or is replicated.

    For name resolution, the system adopts a Distributed Hash Table (DHT) structure. DHT enables a hashed keyword to be mapped to a unique node of the system. In [5], the node in the DHT is regarded as a resolution mapping server. During name registration, meta-data is treated as a keyword and is used to generate a name through hashing. This name is then registered with the DHT. In name resolution, the name is resolved in the DHT and its connection information is returned. Because DHT architecture is flat, if the DHT naming system experiences Denial-of-Service (DoS) attacks, only the attacked server is paralyzed. Other servers are not affected. Such a system is more robust than DNS in the case of DoS attacks. But in a DHT system, there is a maximum delay of log N (take Chord for example), where N is the number of nodes in the system, to resolve a name. For a global system, N may be a mega number, so the delay is quite long and the system is not applicable. To solve the long resolution delay problem, two new naming systems are proposed: One-hop DHT-based naming system and overlay naming system. Both have the advantages of the DHT-based naming system introduced in [5].

2 One-Hop DHT-Based Naming System
    The one-hop DHT-based naming system is an overlapped structure consisting of three layers: Relay layer, implementation layer and maintenance layer. Fig. 1 shows the structure of one-hop DHT-based naming system. The relay layer mainly controls user access and processes user requests for registration or querying of resource names. The implementation and maintenance layers work together to register or query resource names. The implementation layer maintains a Chord system, while the maintenance layer manages a vector space where a server knows all information of other servers in the layer.

2.1 Implementation Scheme
    In the one-hop DHT-based naming system, each node in the relay layer connects to between one and three nodes of the implementation layer—through which the system can be entered for registration or obtaining necessary connection information for services. The implementation layer maintains a Chord ring, and each node maintains two kinds of tables: a parent node table and a routing table. Implementation of the routing table in this system is the same as that in the Chord algorithm [6]. The parent node table contains the ID of the maintenance layer node that manages it. The maintenance layer also maintains a region table and a management table. The region table is used to maintain continuous regions in the implementation layer, and the management table is used to indicate which nodes in the region survive.

    An example is taken to briefly explain the entire workflow of the naming system. Fig. 2 illustrates a one-hop DHT-based naming system and the connections between its nodes. The maintenance layer has 4 nodes, the implementation layer has 11 Chord nodes, and there are two relay nodes. Fig. 3 shows three typical tables: Region and management tables of maintenance node M1, and the parent node table of Chord node C1.

2.1.1 Resource Registration
    The resource registration procedure is as follows:

    (1) A user sends a resource registration request to a relay node (relay node 1).

    (2) The relay node extracts the meta-data of the service and generates a network name (SID1=3) by hashing the meta-data.

    (3) Using Chord algorithm, the network name is registered to the Chord ring via one access point of the implementation layer (C26). That is to say, information applied to the network name during connection setup is written in another node (C4).

2.1.2 Resource Resolution
    The resource resolution procedure is as follows:

    (1) A network name (SID1=3) is generated by hashing the meta-data of a service.

    (2) The user sends a resource resolution request to a relay node (relay node 2).

    (3) The relay node sends the network name to the upper layer via one access node of the implementation layer (C32) which it connects to.

    (4) Upon receiving the service request, C32 forwards the request to its parent node M4 without any processing.

    (5) Maintenance node M4 queries its region table. When it finds the network name 3 is in the region of M1, it sends the request to M1.

    (6) M1 queries its management table. When it finds the information of the network name 3 (in C4), it sets up a connection with C4 to obtain the connection information necessary for the service and returns it to the user.    

   
    (7) The user sets up a connection with the service provider and obtains the service.
The maintenance layer is only involved in the query process because this process is one of the main bottlenecks of network applications. With the maintenance node only processing query requests, query efficiency is improved.

    Normally, nodes in the maintenance layer are configured in hot backup and are robust. If a fault occurs, the system no longer sends query messages to the nodes in the maintenance layer but uses Chord algorithm to set up a route in the implementation layer. Nodes in the maintenance layer can be fixed while the system works normally. As a result, the robustness of the entire system is improved.

    In the one-hop DHT-based naming system, the maximum number of hops for name resolution is 3, and the query delay is relatively short. But this system is only suitable for small-scale application, and processing capability of servers in the maintenance layer is limited. For large systems, an overlay naming system is necessary.

3 Overlay Naming System

3.1 Name Structure
    In an overlay naming system, the network name has a prefix and resource identifier, as shown in Fig. 4. The prefix contains 16 bits that are divided into two parts: the first 9 bits are used to identify the geographical location, and the last 7 bits are used to carry QoS information or are reserved for future expansion. Because there are only around 200 countries and areas in the world, 9 bits are enough to identify them all. The resource identifier is a 160-bit character string obtained from resource meta-data using a hashing function. It uniquely identifies the resource.

    The resource identifier is based on resource meta-data and does not change as the resource migrates or is replicated. This characteristic is similar to the naming architecture proposed in [4]; hence, users can always query the resource by name. With geographical location included in the name structure, the resolution range of the resource is shrunk. In addition, the QoS part enables users to select resources that meet their specific needs.

3.2 Name Resolution Mapping Subsystem
    The name resolution mapping subsystem consists of two layers: Top layer and bottom layer, as shown in Fig. 5. The top layer is global and adopts DHT architecture for maintaining and managing the names worldwide. The bottom layer is used for a country or area. It adopts DHT architecture for resolving local names and interacting with the top layer and other domains. In the bottom layer, there are ordinary servers and gateway servers. For ordinary servers, name registration and resolution methods are consistent with DHT algorithm; for gateway servers, two new routing tables are added. One is used for routing to top layer servers, and the other is used for routing to gateway servers of other domains.

3.2.1 Resource Registration
    Resource registration involves generating a name for a resource and registering it with the name resolution subsystem. This procedure is performed by an ordinary server in the bottom layer in six steps:

    (1) meta-data of the resource is extracted.

    (2) Extracted meta-data is hashed to generate the resource identifier of the resource name.

    (3) The country code is entered as the geographical location.

    (4) Regional information or QoS information is entered. If the QoS or reserved part is to be reserved, this step is ignored and the part left blank. A legal name is generated for the resource.

    (5) Algorithms of the local domain are used to register the name and its connection information to another ordinary server in the domain.

    (6) The name and its connection information are registered to the top layer DHT via the nearest gateway server.

    Suppose a Chinese service provider wants to register the book Principles of Digital Communication. First, meta-data such as principles of digital communication is extracted. Second, a 160-bit character string 101010101111…001 is generated by hashing the meta-data. Third, the country code of China (111000100) is extracted. Fourth, QoS information is entered. For example, QoS class is 3 to 0000111. Finally, all the information above is combined to generate a name: 1110001000000111101010…001.

3.2.2 Resource Resolution
    Resource resolution involves obtaining the connection information of a resource from its network name. The resource requester may know the storage location of the resource or not. If the storage location is known, the location may be in the requester’s own country or in a foreign country. Fig. 6 illustrates the resolution procedures for these three cases.

    Before resolving a resource, a legal name for the requested resource needs to be generated.  meta-data of the resource is hashed to generate the resource identifier; the country code is entered if the requester knows the storage location (or 000000000 if the location is not known); and QoS information is entered as the QoS or reserved part.

• If the requested resource is in a domestic server, the resource identifier is used to search the local DHT and find connection information of the requested resource. This occurs at the access point of an ordinary server.
• If the requested resource is in a foreign server, the resource name is sent to the nearest gateway server. The gateway server resolves the geographical location in the name and forwards the request to a gateway server of the country where the resource is located. Upon receiving the request, the gateway server in the foreign country finds the connection information of the resource using DHT routing in its domain.
• If the requester does not know the storage location, the resource name is sent to the nearest gateway server, which directly forwards the request to the top layer DHT. The top layer DHT uses its own routing algorithm to resolve the resource identifier and finds the connection information.

3.3 Delay Analysis
    According to [7], network delay is mostly related to the number of hops. Therefore, resolution delay of the overlay naming system can be measured by hops. There are three cases of resource resolution, and the resolution delays for these cases are analyzed in this section.

• For intra-domain resolution, the resolution request is processed in the local domain, and the required maximum number of hops is logN1 (supposing the servers in the domain are organized as a Chord ring) and N1 is the number of servers in the domain.
• For inter-domain resolution, the resolution request is first sent to the gateway node of the local domain, which in turn forwards the request to the gateway node of the domain where the resource is stored. The gateway node of the remote domain resolves the name. In this case, the required maximum number of hops is 2 + logN2, where N2 is the number of servers in the remote domain.
• For routing to top domain for resolution, the resolution request is first sent to the gateway node of the local domain. The gateway node then uses the top domain’s routing table to resolve the name. In this case, the required maximum number of hops is logN3, where N3 is the number of servers in the top domain.

    Assuming the percentages of the three cases above are p1, p2 and p3 respectively, the required maximum number of hops for resolution of the system is

THop=p1logN1+p2(2+logN2) +p3logN3   (1)

    Suppose each country has the same number of names to be processed, each country has 50 gateway servers, and each country contributes 50 top domain servers. The top DHT system comprises 10,000 servers. If the percentages of intra-domain resolution, inter-domain resolution, and routing to top domain for resolution are 98%, 1%, and 1% respectively, the required maximum number of hops is

THop= 0.98log1000 + 0.01(2+log10000) 
      + 0.01log 10000
    = 0.98 × 13.287 + 0.01 × 13.287
    = 13.307                                 (2)

    In [5], Chord ring is used to replace the DNS for name resolution mapping. When there is the same number of servers as overlay naming system; that is, 10,000 in the above example, the required maximum number of hops is

T 'Hop= log(200×10000)= 20.9316        (3)

    Comparing equations (1) and (2), the overlay naming system performs better than the system proposed in [5].

4 Advantages of Two New Naming Systems
    Compared with other naming systems, the two naming systems above have the following advantages:

    First, they prevent the resolution systems being absolutely controlled by one country, and enable all countries to share network resources. At least one node of the resolution system is deployed in each country, and the entire system serves users around the world. Also, the network name registered with the naming system is a character string that has no real meaning. So one country cannot completely control the system, and the political factor is stripped from network applications.

    Second, the new naming systems use the values generated from meta-data as network names for registration and query. Any new service can extract its own meta-data to generate a network name for registration and query. In other words, the new naming systems provide a proper interface for accessing new services. Moreover, the new network name is a nonsemantic hash value without any real meaning. So there will be no wrangling over ownership.

    Third, in existing network applications, data replication and migration is inevitable. With existing network technologies, data has to be re-registered with the system and a new domain name assigned after it migrates. It takes a long time for a user to get the new name. As a result, a “http 404 error” message is often seen during Internet surfing. Researchers have developed the http redirection function, which can redirect the data if it migrates within one domain. But for inter-domain migration, there is still no good solution. In the proposed naming systems, a network name is generated from meta-data. When data migrates, the same network name is used to re-register with the system. For users, this process is completely transparent, and migration or replication of data is unnoticeable. Connection information of data can be obtained by resolving the old name.

5 Conclusions
    This paper analyzes the shortcomings of DNS, which include meaningful names, incapability of supporting data migration or replication, and unbalanced load. It discusses one DHT-based naming system that has been proposed by academia to overcome the DNS shortcomings. However, new naming systems have long resolution delays and are not suitable for application. Two new naming systems are therefore proposed: One-hop DHT-based naming system and overlay naming system.

    The one-hop DHT-based naming system adopts a three-layer ring structure to control user access, to register the resource names, and to resolve the names. But because few upper-layer nodes are responsible for the query, this system is only suitable for small-scale application. In the overlay naming system, name registration and resolution are performed in different domains, and so the system can be used globally. At the bottom layer, each country maintains a DHT-based naming system; while at the top layer, there is a global DHT system. Together, these two systems overcome the shortcomings of the DNS and reduce the resolution delay that affects other DHT-based naming systems. Theoretical analyses demonstrate these two systems are feasible for practical use.

References
[1] P. Mockapetris and K.J. Dunlap, “Development of the domain name system,” in Proc. Conf. Applications, Technologies, Architectures, and Protocols for Comput. Commun. (SIGCOMM’08), Seattle, WA, 2008, pp.123-133.
 [2] Jiguang Cao, “New management mechanism of Internet DNS,” Telecom Network Technology, vol. 10, pp.8-12, Oct. 2005. 
 [3] M. Walfish, H. Balakrishnan, and S. Shenker, “Untangling the web from DNS,” in Proc. 1st Conf. Symp. Networked Syst. Design and Implementation (NSDI’04), San Fransisco, CA, 2004, pp.225-238.
[4] H. Balakrishnan, K. Lakshminarayanan, and S. Ratnasamy et al., “A layered naming architecture for the Internet,” in Proc. Conf. Applications, Technologies, Architectures, and Protocols for Comput. Commun. (SIGCOMM’04), Portland, OR, 2004, pp.343-352.
 [5] V. Ramasubramanian and G. Emin, “The design and implementation of a next generation name service for the Internet,” in Proc. Conf. Applications, Technologies, Architectures, and Protocols for Comput. Commun. (SIGCOMM’04), Portland, OR, 2004, pp.331-342.
[6] I. Stoica, R. Morris, and D. Liben-Nowell et al, “Chord: a scalable peer-to-peer lookup protocol for Internet applications,” IEEE/ACM Trans. Netw., vol. 11, no. 1, pp.17-32, 2003.
[7] Fuhong Lin, Changjia Chen, Hengkui Wu et al., “Analysis Time Delay of a Next Generation Name Resolution System,” in Proc. Conf. 2009 WASE International Inf. Engineering, Tai Yuan,China,2009.

Biographies
Fuhong Lin (dr.lin.bjtu@139.com) is a doctoral student at the School of Electronic and Information Engineering, Beijing Jiaotong University. His research interests include network architecture and P2P networks. He has participated in several projects funded by the “973” Program, National High Technology Development Program of China (“863” Program), and National Natural Science Foundation of China (NSFC). He has also published more than 10 papers.

Changjia Chen (changjiachen@sina.com), received his doctoral degree from the Department of Electrical Engineering, University of Hawaii. He is a professor and doctoral advisor at the School of Electronic and Information Engineering, Beijing Jiaotong University; director of the Teaching and Research Office of Communications Engineering, Beijing Jiaotong University; a fellow of the Chinese Institute of Electronics; and a senior member of IEEE. His research interests include communications theory, information and encoding theories, and network theory. He has participated in projects funded by “973” Program, “863” Program, NSFC, and the Chinese Ministry of Railways. He has published more than 100 papers.

[Abstract] Academia has recently proposed new naming systems based on flat Distributed Hash Table (DHT). These naming systems are designed to overcome defects—such as lack of support for data migration and replication—in the Domain Name System (DNS). DHT naming systems have long resolution delay and are not suitable for practical application. This paper introduces two new naming systems that have the advantages of both DNS and DHT systems. The first is a three-layer system based on one-hop DHT and is suitable for small-scale application. The second adopts a hybrid DHT structure, can be implemented in different domains, and can be applied globally. Theoretical analyses demonstrate that these two systems are feasible for practical use.

[Keywords] naming system; DNS; DHT; naming; name resolution mapping