From mp98@cornell.edu Tue Nov 19 00:57:48 2002 Received: from postoffice2.mail.cornell.edu (postoffice2.mail.cornell.edu [132.236.56.10]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id gAJ5vl904594 for ; Tue, 19 Nov 2002 00:57:47 -0500 (EST) Received: from cornell.edu (r109493.resnet.cornell.edu [128.253.240.252]) by postoffice2.mail.cornell.edu (8.9.3/8.9.3) with ESMTP id AAA23498 for ; Tue, 19 Nov 2002 00:57:06 -0500 (EST) Date: Tue, 19 Nov 2002 00:57:05 -0500 Mime-Version: 1.0 (Apple Message framework v546) Content-Type: text/plain; charset=US-ASCII; format=flowed Subject: 615 Paper 66 From: Milo Polte To: egs@CS.Cornell.EDU Content-Transfer-Encoding: 7bit Message-Id: X-Mailer: Apple Mail (2.546) The first paper provides background information on the history of the DNS system, a hierarchical distributed naming system. DNS seperates the name database into hierarchical zones of control. A name server is assigned to, say, the google.com zone and is responsible both for the resolution of google.com, and to point to name servers for www.google.com. Caching is implemented along the request path to speed up future requests. The second paper describes a new approach to DNS designed to make up for the various shortcomings of the original system such as its centralization and poor security. To achieve this, they design a simply configurable peer-to-peer name resolution system on top of Chord. To prevent spoofing, responses are signed with public key cryptography. Key distribution is handled in a recursive manner and assumes one knows the key for the root server and caching is implemented in a similar way to the original DNS (along the request path). The problem with their approach is that whereas the latency of traditional DNS scales according to the length of the request (i.e. foo.boogle.google.com is expected to take about twice as long as google.com) albeit at the cost of really hammering the root servers, the latency of this DNS system is proportional to the log of the total number of hosts in the network. The third paper examines the general problem of using an overlay network to build a naming service. Their system is not peer-to-peer as the low lifetime of p2p nodes makes the unsuitable for something like DNS. Rather, they build their network out of a few high performance servers whom client machines contact. Their system is designed to be both scalable and speedy and resilient to unbalanced queries. The main servers are organized into a pastry network. The improvement over the previous paper's approach is that the number of hosts participating in the pastry network (and hence the logarithmic routing time) is bounded. Caching is implemented through replication of popular queries. We've seen DHTs used for a lot of apps so far: File sharing being a primary one. Now they have been used for DNS queries. We can easily imagine some other uses for them. For example, a new naming service for resource location could be built upon them using something similar to the intentional naming scheme we encountered earlier, but more simplified. We could also build a dictionary system on top of them. Basically, DHTs are useful for any service where one needs to lookup information on a subject given a well known key. There are plenty of good uses that come to mind: A new kind of wiki web for publication. Distributed chat. Instant messaging and so forth. A more interesting question is what kind of tools would not work well with a distributed hash table. Obviously, any system in which the keys are not well known will not work well. DHTs can't do Gnutella style searching. They are also unsuitable for boolean operations on large data sets. For example, the canonical example of looking up the keyword MADONNA and the keyword PRAYER (for Madonna's like a prayer) is unreasonable because we expect the size of both of these keyword files to be quite large, incurring a very large cost of bandwidth when all we are truly interested in is their intersection. For this kind of application, a new sort of system would have to be written, allowing SQL style queries. From shafat@CS.Cornell.EDU Tue Nov 19 04:30:57 2002 Received: from exchange.cs.cornell.edu (exchange.cs.cornell.edu [128.84.97.8]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id gAJ9Uv919348 for ; Tue, 19 Nov 2002 04:30:57 -0500 (EST) content-class: urn:content-classes:message MIME-Version: 1.0 Content-Type: text/plain; charset="utf-8" X-MimeOLE: Produced By Microsoft Exchange V6.0.6249.0 Subject: 615 PAPER 66 Date: Tue, 19 Nov 2002 04:30:57 -0500 Message-ID: <47BCBC2A65D1D5478176F5615EA7976D134FEC@opus.cs.cornell.edu> X-MS-Has-Attach: X-MS-TNEF-Correlator: Thread-Topic: 615 PAPER 66 Thread-Index: AcKPgY1KJwMQwGRkSWOzvzXvKyZBww== From: "S. Shafat Zaman" To: "Gun Sirer" Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from base64 to 8bit by sundial.cs.cornell.edu id gAJ9Uv919348 The first paper, "Development of the Domain Name System", presents a historical background on the development of the DNS in the early 80's. It elaborates on the much needed transition from the centrally-administered HOSTS.TXT model to a more distributed, reliable and flexible naming system to connect the emerging Internet. The paper also describes the hierarchical name space and two major database distribution mechanisms (zones and caching) used in the DNS. The operation of the DNS led to a number aforeseen issues such as those related to performance, negative caching and refinement of semantics. The paper finally discusses in length the various advantages and shortcomings of the then implementation of the DNS. The paper titled "Serving DNS using a Peer-to-Peer Lookup Service" explores an alternative usage of DHash, a P2P DHT based on Chord. It leverages Chord's fault-tolerance and load balancing properties to implement an alternative storage system for DNS. In DDNS, a resource record set (RRSet) has a key hashed by the domain name and the RRSet query type. It then relies on the underlying Chord network to manage and serve these DNS records. Although DDNS eliminates most the problems associated with managing name servers, and displays good fault-tolerance and load balancing properties, it however has a worse performance than regular DNS in latency due to a higher number of RPCs involved per lookup in DDNS. The last paper presents Overlook, a name service implemented on top of Pastry. Its design is not however specifically based on Pastry, and it can be used on top of any other overlay routing scheme. Overlook makes use of a DHT where each table entry is a directory in a hierarchical name space. The 128-bit key to each entry is obtained by hashing the full path name of a directory. The DHT is distributed across a set of serves connected together by a Pastry network. This enables clients to look up values stored in the DHT by submitting a directory name. With these mechanisms in place, directories can easily be created or deleted. Clients can also enumerate a directory's entries. Experimental results show that Overlook is highly scalable, efficient and fault tolerant (due to replication). From smw17@cornell.edu Tue Nov 19 09:43:12 2002 Received: from cornell.edu (cornell.edu [132.236.56.6]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id gAJEhC905074 for ; Tue, 19 Nov 2002 09:43:12 -0500 (EST) Received: from cornell.edu (syr-24-161-107-202.twcny.rr.com [24.161.107.202]) by cornell.edu (8.9.3/8.9.3) with ESMTP id JAA02287 for ; Tue, 19 Nov 2002 09:43:11 -0500 (EST) Message-ID: <3DDA4CB4.6060503@cornell.edu> Date: Tue, 19 Nov 2002 09:37:40 -0500 From: Sean Welch User-Agent: Mozilla/5.0 (Windows; U; Windows NT 5.0; en-US; rv:1.0.1) Gecko/20020823 Netscape/7.0 X-Accept-Language: en-us, en MIME-Version: 1.0 To: Emin Gun Sirer Subject: 615 PAPER 66 Content-Type: text/plain; charset=us-ascii; format=flowed Content-Transfer-Encoding: 7bit DNS DNS is the (now) standard for name resolution on the internet. DNS is a distributed, heirarchical system that replaced the centralized distribution of a hosts.txt file. DNS provides a cut-down distributed database that creates a heirarchy of name servers to span the entire namespace. The root servers control the entire space, and when desireable will delegate responsibility for a given namespace to another server, forming a sub-tree for the namespace in question. Naming data are cached based on an administrator specified TTL field. To resolve a name, a machine attempts to contact a name server containing the relevant information on the machine specified by the hostname (name->address mappings, mailserver information, etc). In addition to the function of providing a replacement for the hosts.txt file, DNS also (perhaps unintentionally) introduced new possibilities into the resolution process. Whereas the hosts.txt file is inherently static, the new DNS system provides the ability to create dynamic responses to requests, such as mapping unknown hostnames to existing hostnames. DDNS/Overlook Both DDNS and Overlook consider the problem of implementing a name lookup system over a P2P network based on a distributed hash table. DDNS operates over Dhash/Chord, and Overlook operates over Pastry. Overlook also limits the participants to a collection of high-power server nodes rather than operating over a general public P2P system. Both systems have a 'root' node for a particular key, generally the node with the node ID closest to the name key. The data is replicated across multiple nodes, and may also be cached based on popularity. In DDNS, authenticity is guaranteed through a public key based system, with each heirarchical entity (i.e. - cs, cornell, and edu) signing the result to provide authentication up to the DNS root. Overall, P2P systems provide a mechanism for a distributed DNS to function, and provide roughly the same functionality as the hosts.txt mechanism. When compared to DNS, however, there are a number of problems. Most significant is performance. The average DNS latency is quoted as 43ms, whereas the latency for DDNS is mean 350, and for the 'good' Overlook results, the mean is roughly 650ms. This is a significant increase over conventional DNS. In addition, both of these systems are strictly less useful than the current DNS implementation. Neither system provides for dynamic responses to requests, and require either additional network traffic or more complex responses to deal effectively with additional name spaces. For instance, if I access cornell.edu under the current DNS, I may not know the name to cit.cornell.edu. But under standard DNS, my link to the cornell.edu nameserver provides a shortcut to find the cit.cornell.edu nameserver. Under either DDNS or Overlook, however, the name cornell.edu and the name cit.cornell.edu will hash to significantly different values, obscuring the inherent connection between them. Similarly, if Cornell is removed from the global internet for some reason, the current DNS scheme still allows for internal access to the local internet. Such a feature is not available in DDNS/Overlook. From vrg3@cornell.edu Tue Nov 19 10:30:28 2002 Received: from travelers.mail.cornell.edu (travelers.mail.cornell.edu [132.236.56.13]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id gAJFUR918687 for ; Tue, 19 Nov 2002 10:30:27 -0500 (EST) Received: from travelers.mail.cornell.edu (travelers.mail.cornell.edu [132.236.56.13]) by travelers.mail.cornell.edu (8.9.3/8.9.3) with SMTP id KAA10367 for ; Tue, 19 Nov 2002 10:30:25 -0500 (EST) Date: Tue, 19 Nov 2002 10:30:25 -0500 (EST) From: vrg3@cornell.edu X-Sender: vrg3@travelers.mail.cornell.edu To: egs@CS.Cornell.EDU Subject: 615 PAPER 66 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII The DNS paper describes the origin of the presently standard Domain Name System. DNS partially distributes the task which used to be handled by a centralized hosts database, by partitioning namespace into a hierarchy. Root servers are responsible for the entire namespace, but they delegate responsibility for particular domains to servers (ordinarily) belonging to the owners of the domains. A DNS query starts at a node at the bottom of a tree and propagates up as far as necessary and then back down as far as necessary, with its result being cached along the way, for an amount of time specified by the server which actually answers the request. The DDNS paper presents a fully distributed replacement for DNS. DDNS relies on a distributed hash table, DHash, based on Chord. Keys are hashed from the domain names, and distributed around the ring. The standard Chord query mechanisms apply. This results in fairly good robustness and load balancing. There are a few limitations, however; DDNS scales logarithmically with the size of the network, whereas the performance of DNS is constant with respect to the number of nodes. This performance is generally worse than DNS even in fairly good cases. Additionally, DDNS does not allow a network to take advantage of locality the way hierarchical DNS does; a query for a hostname on your local network (a1.b1.c1 querying for a2.b1.c1) or in the same higher-level domain (a1.b1.c1 querying for a2.b2.c1) is no quicker than any other query. The Overlook paper also presents a distributed DNS replacement, but it is distributed a different way. In Overlook, a distinction is made between clients and servers. The servers form an overlay network and use the Pastry peer-to-peer protocol to maintain a hash table among them. These servers are reliable and long-lived, unlike the typical servent in a fully peer-to-peer network. Overlook attempts to outperform DDNS by having a fixed number of nodes in the server overlay network, all of which are high-performance. It has, however, the same weakness with regard to locality. In addition, the latency is still far greater than that typical of DNS. We have discussed distributed hash tables being used for file sharing and domain naming. DHTs are best suited to any kind of application where you have clients querying for data where a relatively small number of possible query values map to each result. Domain naming fits this description very well; filesharing only kind of does, since you would like to be able to find Emerson, Lake, and Palmer's "I Believe in Father Christmas" by searching for any of "Emerson," "Christmas," "Emerson Lake and Palmer," and so forth. Other database applications where items can be queried by unique or nearly unique keys include things like customer information databases. This in particular is interesting because if you kept this kind of network on a DHT, it would be relatively easy to look up a particular person's record, knowing their key (some unique ID like a social security number or whatnot), but it could be relatively difficult to collect information on all people in general, especially if each data item is encrypted with its key and the data is distributed across many nodes. This might make it difficult for an intruder to easily collect every customer's sensitive information. From kwalsh@CS.Cornell.EDU Tue Nov 19 10:54:49 2002 Received: from kwalsh4158.cs.cornell.edu (dhcp99-7.cs.cornell.edu [128.84.99.7]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id gAJFsm924293 for ; Tue, 19 Nov 2002 10:54:49 -0500 (EST) Message-Id: <5.1.1.6.0.20021119105315.00a96030@popsrv.cs.cornell.edu> X-Sender: kwalsh@popsrv.cs.cornell.edu X-Mailer: QUALCOMM Windows Eudora Version 5.1.1 Date: Tue, 19 Nov 2002 10:54:31 -0500 To: egs@CS.Cornell.EDU From: Kevin Walsh Subject: 615 PAPER 66 Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed Development of the Domain Name System Serving DNS using a Peer-to-Peer Lookup Service Overlook: Scalable Name Service on an Overlay Network It is interesting to contrast DNS with the then-existing grapevine, showing how an intelligent, powerful but complex system loses out to a simple, limited but robust one. The designers consciously omitted advanced features (replication, atomic updates, voting, backup) because these might make the system too complex. Extensibility from the start, but even then, a realization that this was not used much. No particular encoding or pretty-printing of names was specified, in the hopes that various uses would arise for DNS. This enables host names, email addresses, or other data to be first-class data. Also taken into account were political and social considerations. The imagined uses for DNS were several: host information (address, type, ...); address information (host name, administrative domain, ...); mailbox information (user name, gateway, protocol,...). Other uses have not been so fast in coming, due not to the limitations of DNS, but to the need for recoding applications. From a peer-to-peer perspective, the problem is that individual users have little to no control over the DNS system. Further, administrators fear tampering with such a critical infrastructure. The DDNS paper looks at the opportunity for new administrative organization given the decoupling of authentication and serving of records (provided by DNSSEC). The authors propose using DHash, based on Chord, as an alternative to DNS, with authentication of data provided by record signing. While citing the Mockapetris and Dunlap paper, they failed to address several of the concerns raised (even the ones they quoted!). As for new applications, DDNS seems to eliminate practically the only new successful use for DNS dynamic on-demand generation of responses (as in a CDN), since users have no control over where their records are stored. Overlook is similar to DDNS, in that it uses Pastry as the underlying DHT to provide name the service. Custom server-side functionality is not (usually) possible in these systems, as mentioned in DDNS. To overcome this, the authors try to implement very fast updates so that clients can implement dynamic services (updating the service frequently and rapidly). This is less powerful than custom services, since all data must be generated centrally and without access to the queries. Also, a key reason for dynamic services is to specifically not pre-generate records, but to generate it only in response to a query. What I feel is missing in these papers is a clear understanding of potential applications of DHTs, other than for replacing traditional DNS functionality (but possibly not newer DNS functions). From mvp9@cornell.edu Tue Nov 19 11:08:02 2002 Received: from cornell.edu (cornell.edu [132.236.56.6]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id gAJG81927765 for ; Tue, 19 Nov 2002 11:08:01 -0500 (EST) Received: from zoopark.cornell.edu (syr-24-58-46-186.twcny.rr.com [24.58.46.186]) by cornell.edu (8.9.3/8.9.3) with ESMTP id LAA03812 for ; Tue, 19 Nov 2002 11:08:00 -0500 (EST) Message-Id: <5.1.0.14.2.20021119110654.00adb110@postoffice.mail.cornell.edu> X-Sender: mvp9@postoffice.mail.cornell.edu (Unverified) X-Mailer: QUALCOMM Windows Eudora Version 5.1 Date: Tue, 19 Nov 2002 11:07:56 -0500 To: egs@CS.Cornell.EDU From: mike polyakov Subject: 615 PAPER 66 Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed Dynamic hash tables provide a service on top of which many applications can be built, such as naming services of DNS. The first paper discusses the introduction of the DNS system to replace the host name file that was used previously. It goes through the successes and failures of the implementation as well as the lessons that have been learned. These range over technical issues, like the benefit of UDP and the lack of negative caching to the difficulties of dynamically switching widely used systems. The second paper describes DDNS a distributed domain naming system which eschews hierarchy for a distributed hash table topology, specifically Pastry. Their system addresses several weaknesses in DNS improve security through cryptographic signatures, improve load balancing and robustness by eliminating root servers, simplifying administration. The less touted but important aspect of their system is the simplicity of switching to it, should that ever happen just consider your own computer as a DNS server and send requests to it as usual. Unfortunately, it turns out that DDNS is far slower than DNS, because through its huge branching factor, DNS lookups are almost constant, while Pastry takes log N good for file sharing, but slow for a naming service. Still, since its introduction and the time of the first paper, DNS has come along way, so the weaknesses of new solutions should not necessarily be discouraging. Finally, the third paper introduces Overlook, a general naming service layered on top of a overlay network, for routing, in this case, also Pastry. One of the main ideas of the paper is that peer-to-peer performance suffers from variability of bandwidth and computation of resources of nodes. Their solution is to restrict the network to servers to which clients connect with queries. Because their main requirements include speed of update diffusion and adaptation to flash crowds, much effort is devoted to dealing with replicas and caches, when to make them and how to distribute them. That is the principle contribution of this paper. Their results are somewhat poor hundreds of milliseconds at best for a 10K node network though there may be applications that tolerate such delays, like event notification. Also, these 10K servers may potentially support millions of clients, depending on frequency of requests. Clearly, dynamic hash tables have their limitations; in some cases, like DNS, speeds of log N that they generally offer are considered slow. Their niche are applications where the location or some property of an object with a known key is desired; where large size must be combined with fairly fast access, robustness and distributed nature. As we have seen, file sharing fits this model; so does most communication. Messaging services as well as things like phones (if they were done in software will digital telephony ever take off?) can benefit from the lack of centralization. Potentially, another use is for knowledge bases, where the enormity of size and need for robustness make dynamic hash tables advantageous. From bd39@cornell.edu Tue Nov 19 11:12:25 2002 Received: from postoffice2.mail.cornell.edu (postoffice2.mail.cornell.edu [132.236.56.10]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id gAJGCO929021 for ; Tue, 19 Nov 2002 11:12:24 -0500 (EST) Received: from boweilaptop.cornell.edu (dhcp-128-84-93-87-wifi.ece.cornell.edu [128.84.93.87]) by postoffice2.mail.cornell.edu (8.9.3/8.9.3) with ESMTP id LAA14426; Tue, 19 Nov 2002 11:11:11 -0500 (EST) Message-Id: <5.1.0.14.2.20021119110750.00b75910@postoffice2.mail.cornell.edu> X-Sender: bd39@postoffice2.mail.cornell.edu (Unverified) X-Mailer: QUALCOMM Windows Eudora Version 5.1 Date: Tue, 19 Nov 2002 11:08:24 -0500 To: egs@CS.Cornell.EDU From: Bowei Du Subject: 615 PAPER 66 Cc: bd39@cornell.edu Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed Development of the DNS: This paper gives an historical overview of the development of the DNS system. The initial design goals of DNS were to provide host name to IP database queries, be distributed, interoperable and have relatively few limits on the size of the names. The design would strive to be frugal and provide a workable minimum of functionality. DNS divides the name space into a hierarchy of zones, which correspond to various levels of delegation of the authority to resolve certain names. - Requires central root servers to resolve top level names, which becomes a bottleneck. But this also means that top level resolutions are authoritative. - Caching works very well, but maybe cause mapping information to become inconsistant or unauthoritative. Authenticity of the cache information is also an issue. - Flexible namespace that can encode other schemes easily - Authority over a domain entails responsibility for management of naming in that domain DNS using a Peer-to-Peer lookup Service The main idea of this paper is to demonstrate a way to implement DNS in a p2p overlay network and to argue for the usefulness of such a scheme. The authors cite the load balancing behavior and ease of administration as main motivations. DNS is implemented on top of DHash by storing the DNS RR in a DHash scheme on top of Chord. Authenticty of the replies is guaranteed with signatures (DNSSEC). - Performance with the Chord servers is bad - greater than 7 times the latency of DNS. It would be difficult to motivate replacement of a working (if somewhat faulty) system with a much slower one. - DNS takes advantage of network locality of queries. (i.e. queries to machines on campus, for example, have an immediate response from the name server. Chord's distributed hash algorithm will distribute keys willy-nily throughout the entire chord network, which will increase latency. - Not all nodes are created equal, what if a very popular key, (.com) got mapped to a very inefficient host? Or if this node was extremely flaky in reliability? - Someone will still need to manage the hosts, except the problem has been extended from operators being inept system administrators to anyone who desires to join the peer-to-peer network. The idea of a peer-to-peer implementation of DNS is interesting if it could more evenly distribute the load induced upon the root servers. Overlook: Scalable Name Service on Overlay Network Overlook is a distributed naming directory service that can be built on top of any of the distributed hash schemes that we have examined before. Overlook addresses the issue of unequal peers by stipulating that only server nodes can participate in the p2p network. Directory information is stored in the usual scheme. Overlook also caches popular directories along the request route if requests exceeed a certain rate. Clients can also be migrated between servers if client request latency exceeds some threshold. Servers migrate clients to the server it forwarded its request to. When a flash of requests occur in the system (slashdot effect), copies are replicated from the home node in a tree like fashion. Updates to the data are performed from the root of the tree. Heartbeat messages are used to determined whether parent nodes are alive. (What happens when a parent dies? After a timeout, does the child contact the original? Also, wouldn't the migration of clients closer to the request home be diametric to the scheme of load balancing?) From bd39@cornell.edu Tue Nov 19 11:13:33 2002 Received: from postoffice2.mail.cornell.edu (postoffice2.mail.cornell.edu [132.236.56.10]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id gAJGDW929148 for ; Tue, 19 Nov 2002 11:13:32 -0500 (EST) Received: from boweilaptop.cornell.edu (dhcp-128-84-93-87-wifi.ece.cornell.edu [128.84.93.87]) by postoffice2.mail.cornell.edu (8.9.3/8.9.3) with ESMTP id LAA18070; Tue, 19 Nov 2002 11:12:12 -0500 (EST) Message-Id: <5.1.0.14.2.20021119110750.00b75910@postoffice2.mail.cornell.edu> X-Sender: bd39@postoffice2.mail.cornell.edu (Unverified) X-Mailer: QUALCOMM Windows Eudora Version 5.1 Date: Tue, 19 Nov 2002 11:08:24 -0500 To: egs@CS.Cornell.EDU From: Bowei Du Subject: 615 PAPER 66 Cc: bd39@cornell.edu Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed Development of the DNS: This paper gives an historical overview of the development of the DNS system. The initial design goals of DNS were to provide host name to IP database queries, be distributed, interoperable and have relatively few limits on the size of the names. The design would strive to be frugal and provide a workable minimum of functionality. DNS divides the name space into a hierarchy of zones, which correspond to various levels of delegation of the authority to resolve certain names. - Requires central root servers to resolve top level names, which becomes a bottleneck. But this also means that top level resolutions are authoritative. - Caching works very well, but maybe cause mapping information to become inconsistant or unauthoritative. Authenticity of the cache information is also an issue. - Flexible namespace that can encode other schemes easily - Authority over a domain entails responsibility for management of naming in that domain DNS using a Peer-to-Peer lookup Service The main idea of this paper is to demonstrate a way to implement DNS in a p2p overlay network and to argue for the usefulness of such a scheme. The authors cite the load balancing behavior and ease of administration as main motivations. DNS is implemented on top of DHash by storing the DNS RR in a DHash scheme on top of Chord. Authenticty of the replies is guaranteed with signatures (DNSSEC). - Performance with the Chord servers is bad - greater than 7 times the latency of DNS. It would be difficult to motivate replacement of a working (if somewhat faulty) system with a much slower one. - DNS takes advantage of network locality of queries. (i.e. queries to machines on campus, for example, have an immediate response from the name server. Chord's distributed hash algorithm will distribute keys willy-nily throughout the entire chord network, which will increase latency. - Not all nodes are created equal, what if a very popular key, (.com) got mapped to a very inefficient host? Or if this node was extremely flaky in reliability? - Someone will still need to manage the hosts, except the problem has been extended from operators being inept system administrators to anyone who desires to join the peer-to-peer network. The idea of a peer-to-peer implementation of DNS is interesting if it could more evenly distribute the load induced upon the root servers. Overlook: Scalable Name Service on Overlay Network Overlook is a distributed naming directory service that can be built on top of any of the distributed hash schemes that we have examined before. Overlook addresses the issue of unequal peers by stipulating that only server nodes can participate in the p2p network. Directory information is stored in the usual scheme. Overlook also caches popular directories along the request route if requests exceeed a certain rate. Clients can also be migrated between servers if client request latency exceeds some threshold. Servers migrate clients to the server it forwarded its request to. When a flash of requests occur in the system (slashdot effect), copies are replicated from the home node in a tree like fashion. Updates to the data are performed from the root of the tree. Heartbeat messages are used to determined whether parent nodes are alive. (What happens when a parent dies? After a timeout, does the child contact the original? Also, wouldn't the migration of clients closer to the request home be diametric to the scheme of load balancing?) From bd39@cornell.edu Tue Nov 19 11:14:59 2002 Received: from postoffice2.mail.cornell.edu (postoffice2.mail.cornell.edu [132.236.56.10]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id gAJGEw929299 for ; Tue, 19 Nov 2002 11:14:59 -0500 (EST) Received: from boweilaptop.cornell.edu (dhcp-128-84-93-87-wifi.ece.cornell.edu [128.84.93.87]) by postoffice2.mail.cornell.edu (8.9.3/8.9.3) with ESMTP id LAA19804; Tue, 19 Nov 2002 11:12:40 -0500 (EST) Message-Id: <5.1.0.14.2.20021119110750.00b75910@postoffice2.mail.cornell.edu> X-Sender: bd39@postoffice2.mail.cornell.edu (Unverified) X-Mailer: QUALCOMM Windows Eudora Version 5.1 Date: Tue, 19 Nov 2002 11:08:24 -0500 To: egs@CS.Cornell.EDU From: Bowei Du Subject: 615 PAPER 66 Cc: bd39@cornell.edu Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed Development of the DNS: This paper gives an historical overview of the development of the DNS system. The initial design goals of DNS were to provide host name to IP database queries, be distributed, interoperable and have relatively few limits on the size of the names. The design would strive to be frugal and provide a workable minimum of functionality. DNS divides the name space into a hierarchy of zones, which correspond to various levels of delegation of the authority to resolve certain names. - Requires central root servers to resolve top level names, which becomes a bottleneck. But this also means that top level resolutions are authoritative. - Caching works very well, but maybe cause mapping information to become inconsistant or unauthoritative. Authenticity of the cache information is also an issue. - Flexible namespace that can encode other schemes easily - Authority over a domain entails responsibility for management of naming in that domain DNS using a Peer-to-Peer lookup Service The main idea of this paper is to demonstrate a way to implement DNS in a p2p overlay network and to argue for the usefulness of such a scheme. The authors cite the load balancing behavior and ease of administration as main motivations. DNS is implemented on top of DHash by storing the DNS RR in a DHash scheme on top of Chord. Authenticty of the replies is guaranteed with signatures (DNSSEC). - Performance with the Chord servers is bad - greater than 7 times the latency of DNS. It would be difficult to motivate replacement of a working (if somewhat faulty) system with a much slower one. - DNS takes advantage of network locality of queries. (i.e. queries to machines on campus, for example, have an immediate response from the name server. Chord's distributed hash algorithm will distribute keys willy-nily throughout the entire chord network, which will increase latency. - Not all nodes are created equal, what if a very popular key, (.com) got mapped to a very inefficient host? Or if this node was extremely flaky in reliability? - Someone will still need to manage the hosts, except the problem has been extended from operators being inept system administrators to anyone who desires to join the peer-to-peer network. The idea of a peer-to-peer implementation of DNS is interesting if it could more evenly distribute the load induced upon the root servers. Overlook: Scalable Name Service on Overlay Network Overlook is a distributed naming directory service that can be built on top of any of the distributed hash schemes that we have examined before. Overlook addresses the issue of unequal peers by stipulating that only server nodes can participate in the p2p network. Directory information is stored in the usual scheme. Overlook also caches popular directories along the request route if requests exceeed a certain rate. Clients can also be migrated between servers if client request latency exceeds some threshold. Servers migrate clients to the server it forwarded its request to. When a flash of requests occur in the system (slashdot effect), copies are replicated from the home node in a tree like fashion. Updates to the data are performed from the root of the tree. Heartbeat messages are used to determined whether parent nodes are alive. (What happens when a parent dies? After a timeout, does the child contact the original? Also, wouldn't the migration of clients closer to the request home be diametric to the scheme of load balancing?) From bd39@cornell.edu Tue Nov 19 11:15:10 2002 Received: from travelers.mail.cornell.edu (travelers.mail.cornell.edu [132.236.56.13]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id gAJGFA900004 for ; Tue, 19 Nov 2002 11:15:10 -0500 (EST) Received: from travelers.mail.cornell.edu (travelers.mail.cornell.edu [132.236.56.13]) by travelers.mail.cornell.edu (8.9.3/8.9.3) with SMTP id LAA07897; Tue, 19 Nov 2002 11:15:08 -0500 (EST) Date: Tue, 19 Nov 2002 11:15:08 -0500 (EST) From: bd39@cornell.edu X-Sender: bd39@travelers.mail.cornell.edu To: egs@CS.Cornell.EDU cc: bd39@cornell.edu Subject: 615 PAPER 66 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Development of the DNS: This paper gives an historical overview of the development of the DNS system. The initial design goals of DNS were to provide host name to IP database queries, be distributed, interoperable and have relatively few limits on the size of the names. The design would strive to be frugal and provide a workable minimum of functionality. DNS divides the name space into a hierarchy of zones, which correspond to various levels of delegation of the authority to resolve certain names. - Requires central root servers to resolve top level names, which becomes a bottleneck. But this also means that top level resolutions are authoritative. - Caching works very well, but maybe cause mapping information to become inconsistant or unauthoritative. Authenticity of the cache information is also an issue. - Flexible namespace that can encode other schemes easily - Authority over a domain entails responsibility for management of naming in that domain DNS using a Peer-to-Peer lookup Service The main idea of this paper is to demonstrate a way to implement DNS in a p2p overlay network and to argue for the usefulness of such a scheme. The authors cite the load balancing behavior and ease of administration as main motivations. DNS is implemented on top of DHash by storing the DNS RR in a DHash scheme on top of Chord. Authenticty of the replies is guaranteed with signatures (DNSSEC). - Performance with the Chord servers is bad - greater than 7 times the latency of DNS. It would be difficult to motivate replacement of a working (if somewhat faulty) system with a much slower one. - DNS takes advantage of network locality of queries. (i.e. queries to machines on campus, for example, have an immediate response from the name server. Chord's distributed hash algorithm will distribute keys willy-nily throughout the entire chord network, which will increase latency. - Not all nodes are created equal, what if a very popular key, (.com) got mapped to a very inefficient host? Or if this node was extremely flaky in reliability? - Someone will still need to manage the hosts, except the problem has been extended from operators being inept system administrators to anyone who desires to join the peer-to-peer network. The idea of a peer-to-peer implementation of DNS is interesting if it could more evenly distribute the load induced upon the root servers. Overlook: Scalable Name Service on Overlay Network Overlook is a distributed naming directory service that can be built on top of any of the distributed hash schemes that we have examined before. Overlook addresses the issue of unequal peers by stipulating that only server nodes can participate in the p2p network. Directory information is stored in the usual scheme. Overlook also caches popular directories along the request route if requests exceeed a certain rate. Clients can also be migrated between servers if client request latency exceeds some threshold. Servers migrate clients to the server it forwarded its request to. When a flash of requests occur in the system (slashdot effect), copies are replicated from the home node in a tree like fashion. Updates to the data are performed from the root of the tree. Heartbeat messages are used to determined whether parent nodes are alive. (What happens when a parent dies? After a timeout, does the child contact the original? Also, wouldn't the migration of clients closer to the request home be diametric to the scheme of load balancing?) From adam@graphics.cornell.edu Tue Nov 19 11:32:02 2002 Received: from bach.graphics.cornell.edu (bach.graphics.cornell.edu [128.84.247.50]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id gAJGW2904021 for ; Tue, 19 Nov 2002 11:32:02 -0500 (EST) Received: from envy.graphics.cornell.edu (envy.graphics.cornell.edu [128.84.247.206]) by bach.graphics.cornell.edu (8.12.1/8.12.1) with ESMTP id gAJGVu0k043980 for ; Tue, 19 Nov 2002 11:31:56 -0500 (EST) Date: Tue, 19 Nov 2002 11:31:20 -0500 (EST) From: Adam Kravetz To: egs@CS.Cornell.EDU Subject: 615 paper 66 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII DNS: This is the paper that brings us the de facto DNS standards. It's one of the first big pushes to change from HOSTS.TXT to full DNS in the internet. It explains the RFC and IEN's that call for DNS and explains the importance of a Domain Name System which is somewhat distributed vs. relying on a file to contain the host on every server or system connected to the internet. Obviously the HOSTS.txt file doesn't scale (size of file, % of bandwidth used to update, etc) well so this was one of the main concerns and reasons to change to DNS. This paper also identifies the shortcomings of DNS (like setting TTL on A records too low, resulting in much uneeded traffic or having a misconfigured server) which are left as open problems in the system. DDNS: Idea, use CHORD to build a distributed dns system in which no administration of DNS servers is needed, replication of data is high (avoiding the /. effect on at least lookup) for popularity and there is at least some defense against DOS. DDNS has a root node for every key in which a record request is sent to for a record, and there is an augmented public key signing system to ensure security. Overlook: A similar Distributed DNS system to DDNS. In Overlook however there is the notion of Client and Server in the system. The Servers use a PASTRY network to keep a hash table. The idea is that the servers would be like a normal DNS server (it would service requests from a client, it would always be available) and the clients would simply insert requests into the network. Both Overlook and DDNS suffer the problem that locality and hierarchy are lost (although they both could be added to these sytems). Network partitioning is mentioned in the DDNS paper and both systems are susceptible to a network partition. Further the typical P2P user is frequently on and off giving very little stability (which is needed) in the network. DDNS is susceptible to stability issues, but Overlook is less likely to be since it relies on "servers" (basically machined which are designated to generally be available) to be part of the DHT. As is known DHTs suffer when there are many choices that lead to the same query result (how many different ways are there to search for an mp3? by artist, genre, title, track name, file size, even creation date) This results in a problem so genericized query terms are hard to deal w/. I think that a DHT could be used to do help aid against DOS attacks. Imagine the following situation. A group of collaborating web servers enter into a CHORD system. Each server inserts there name, their critical data (could be stored on many servers) and information about their machines (what needs to happen when they are under attack, replicate data, take over the this machines DNS entry, notify certain people, etc). Each server then inserts a request (hashed and passed to various other servers) for "partnership". This partnership is basically a promise to periodically check that server's status, and if under attack find the information about the machine and take the critical steps. The DHT could also be used as a Distributed Force Field in which the servers themselves could commit a DOS against the offender given that they are identifiable. From tmroeder@CS.Cornell.EDU Tue Nov 19 11:37:17 2002 Received: from dhcp99-96.cs.cornell.edu (dhcp99-96.cs.cornell.edu [128.84.99.96]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id gAJGbH905348 for ; Tue, 19 Nov 2002 11:37:17 -0500 (EST) Received: (from tmroeder@localhost) by dhcp99-96.cs.cornell.edu (8.11.6/8.11.6) id gAJGbGX19895; Tue, 19 Nov 2002 11:37:16 -0500 From: Thomas Roeder MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Message-ID: <15834.26812.695910.278845@dhcp99-96.cs.cornell.edu> Date: Tue, 19 Nov 2002 11:37:16 -0500 To: Emin Gun Sirer Subject: 615 PAPER #66 X-Mailer: VM 7.07 under Emacs 21.2.1 For today's papers, we were asked to discuss for what other applications DHT's could be used. We have seen the uses as a file sharing mechanism, as a name resolution service, as a file system, and as an anonymous publication mechanism so far in our readings. All of the papers we have seen have been considering the use of DHT's over the Internet, and so require Internet scalability (though many do not necessarily achieve it). An interesting application of DHT's might be for local use; for instance, the services like NIS, which allow login to local machines based on information which is general to the LAN. Generalizing this case, we might consider a local DHT for information which needs to be made available consistently within a LAN, but should not put an undue load on any one machine. An example might be a finger-like-directory of users' information, where only a given user can publish under their own name. Many applications might take advantage of similar services. At Silicon Chalk, where I worked, we had a similar DHT service for providing user and local-application data (for instance, which courses were live, and how to join one if so) in our product. In summary of the papers: The DNS paper describes the experiences of the first 5 years of using DNS for name resolution, and its gradual takeover of the resolution role from hosts.txt (although the latter idea still exists even today to provide local resolution). It incorporates many systems-level suggestions not necessarily specific to DNS (like: remember to write the examples as if they are the only thing that gets read, since they are.). They suggest many potential future changes to DNS, few of which were ever actually done, due to the inertia of an established system. They have designed a general (name, value) mapping service, which effectively only gets used for name->address resolution. Both the Overlook and DDNS papers describe a DHT run over the favorite P2P overlay routing network of the authors, but they are essentially describing the same system. Overlook is from Microsoft, and so uses Pastry, and DDNS is from MIT and so uses Chord and DHash. Both try to balance the load using the DHT to spread the resolution effort across the network. DDNS deals with the inherent security issues by requiring nested signatures on the hierarchical names, whereas Overlook (like its possible inspiration in naming: Outlook) assumes that there are no malicious nodes in the collection of servers. Both suffer from the same DoS flaws that we have discussed in class, and, worse, both have significant latency problems in lookup. The DDNS paper admits this flaw and suggests possible improvements. Overlook ignores it, and just redefines "good" and "bad" for the purposes of evaluation. In reality, none of these lookup times are acceptable. From hs247@cornell.edu Tue Nov 19 11:41:50 2002 Received: from travelers.mail.cornell.edu (travelers.mail.cornell.edu [132.236.56.13]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id gAJGfn906509 for ; Tue, 19 Nov 2002 11:41:50 -0500 (EST) Received: by travelers.mail.cornell.edu (8.9.3/8.9.3) id LAA29001; Tue, 19 Nov 2002 11:41:47 -0500 (EST) Date: Tue, 19 Nov 2002 11:41:47 -0500 (EST) From: hs247@cornell.edu Message-Id: <200211191641.LAA29001@travelers.mail.cornell.edu> To: egs@CS.Cornell.EDU Errors-To: hs247@cornell.edu Reply-To: hs247@cornell.edu MIME-Version: 1.0 Content-Type: text/plain Content-Transfer-Encoding: 7bit X-Mailer: IMP/PHP3 Imap webMail Program 2.0.9 Sender: hs247@cornell.edu X-Originating-IP: 128.84.97.226 Subject: 615 Paper 66 The first paper describes the motivation behind, the design, and the development of the Domain Name System. The Domain Name System is a system used on the Internet today to keep track of name, address bindings. It also provides the resolving of names to address(s). The current design is to have a hierarchical name space. (Ie. the name cs.cornell.edu is resolved by going to servers responsible for edu, then cornell, then cs). The problem with this structure is that there is a lot of administrative needed at each level. Also this relies on name servers at each level to be available. Any slight error could result in irresolvable names or incorrect mappings. The second paper ¡§Server DNS using Peer-to-Peer Lookup Service¡¨ looks at implementing a Domain name service on top of Chord and D-hash (CFS). The idea behind this is to load balance and not have to rely on a set number of servers to service lookups. Entries in D-hash are resource record sets that consist of name to address mapping as well as keys so the requestor can verify the validity of the message. Caching is done similarly to what was described in CFS where data is stored cached on the lookup path. The advantage of this system is that administration is now distributed and a central administrator is not required. Through simulation, they find that the latency of DDNS (log n) is a lot higher then convention DNS (avg 2 hops). And find that peer-to- peer hash tables can not offer the same services as conventional DNS, mainly because distributed hashtable rely on clients to be cooperative and as seen in class, this is not always the case. It is also harder to update the software when the system runs on so many clients. Overlook describes a Domain Name Service application designed for a general overlay distributed hash- table. In particular, an example was given where Pastry was used. Because Pastry and Chord are very similar, the implementation is really similar to the above paper. They provide extra description on how popular directories can be replicated and therefore be load balanced. Also, a client can specify how strongly it wants a directory to be able to respond to updates. The stronger in consistency desired, the less it can be replicated. In general, their performance evaluation was more positive then the above paper. However they do mention that the system was designed for peer-to-peer networks that all have ¡§server-like¡¨ qualities, therefore ignoring the fact that peer-to-peer systems can have many ¡§client- like¡¨ qualities which would degrade the performance of such as system. Some other applications Distributed hash tables can be used for besides DNS that we have looked at include file storage and file sharing. Perhaps file storage can also lead to distributed databases. One could also imagine implementing a web-crawler or search engine. From ag75@cornell.edu Tue Nov 19 11:45:15 2002 Received: from travelers.mail.cornell.edu (travelers.mail.cornell.edu [132.236.56.13]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id gAJGjF907534 for ; Tue, 19 Nov 2002 11:45:15 -0500 (EST) Received: from travelers.mail.cornell.edu (travelers.mail.cornell.edu [132.236.56.13]) by travelers.mail.cornell.edu (8.9.3/8.9.3) with SMTP id LAA01763 for ; Tue, 19 Nov 2002 11:45:12 -0500 (EST) Date: Tue, 19 Nov 2002 11:45:12 -0500 (EST) From: ag75@cornell.edu X-Sender: ag75@travelers.mail.cornell.edu To: egs@CS.Cornell.EDU Subject: 615 PAPER 66 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII The first paper we read for this week was about DNS. DNS was created because the then present centralized HOSTS.TXT naming system was becoming inadequate in the face of increasing size of the Internet and thus difficulty in disseminating large HOSTS.TXT file in a cost-effective manner. There was a need to distribute functionality and add new features, while not making the system overly complicated to gain acceptance by the community. DNS uses name servers to answer queries and resolvers to find a name server that has the information sought by the client. It uses zones and caching to transfer data from its ultimate source to ultimate destination. Its performance is not bad, but can be significantly improved with addition of new features, such as negative caching. DNS's use of variable depth hierarchy is very useful since different organizations have very different sizes. Some of the shortcomings of DNS are that it's difficult to administer DNS servers and that DNS servers can be impersonated using forged IP addresses. The authors list several other successes, surprises and shortcomings of DNS and discuss possible future improvements. In the second paper, the authors try to use DDNS to solve problems related to the complexity of running a DNS server and problems related to security. DDNS is based on DHash, which is in turn based on Chord. The idea behind DDNS is to use DHash and Chord to provide security against DoS attacks, while eliminating much of the need for expertise in running a DNS server by automatically providing a routing infrastructure for finding name information and automatically avoiding single points of failure. Unforunately, DDNS has very high latencies: on average almost 10 times as large as those of DNS. Additionally, it can't implement many of the features of DNS, such as dynamic generation of records. Finally, since DDNS relies on a P2P system, there must be incentives for members to run servers and not freeload, which there don't seem to exist. The third paper talks about Overlook. Overlook is a large scale naming service in which updates to the name space become visible quickly, and which can handle high variations in the popularity and lookup request rates of various parts of the namespace. Overlook is based on top of Pastry, and uses Pastry to provide fault-taulerant routing. It uses dynamic replication to deal with popular directories and to handle network congestion. The experimental results for Overlook were obtained using a simulator. While many factors are modelled, they make an assumption that packets are never dropped. The experimental results show that the average latency for Overlook is about 20 times as large as that for DNS. Moreover, LAN-speed links are required for Overlook to be able to scale. DHTs found another use in the naming service area. However, the performance of the systems that use them still leaves a lot to be desired. While DHTs would provide many new and desirable features, research must be done to improve the performance of such systems. From nbs24@cornell.edu Tue Nov 19 11:53:07 2002 Received: from travelers.mail.cornell.edu (travelers.mail.cornell.edu [132.236.56.13]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id gAJGr6909113 for ; Tue, 19 Nov 2002 11:53:06 -0500 (EST) Received: by travelers.mail.cornell.edu (8.9.3/8.9.3) id LAA07961; Tue, 19 Nov 2002 11:53:04 -0500 (EST) Date: Tue, 19 Nov 2002 11:53:04 -0500 (EST) From: nbs24@cornell.edu Message-Id: <200211191653.LAA07961@travelers.mail.cornell.edu> To: egs@CS.Cornell.EDU Errors-To: nbs24@cornell.edu Reply-To: nbs24@cornell.edu MIME-Version: 1.0 Content-Type: text/plain Content-Transfer-Encoding: 7bit X-Mailer: IMP/PHP3 Imap webMail Program 2.0.9 Sender: nbs24@cornell.edu X-Originating-IP: 132.236.71.82 Subject: 615 PAPER 66 Development of the Domain Name System This paper provides the history behind the development of DNS and discusses what the authors believed to be surprises, successes and shortcomings of the system. DNS is basically a hierarchical naming system with two major active components: name servers and resolvers. The former answer queries using their repositories of information and the resolvers provide an interface to the client programs. Data is transferred from source to destination by means of zoning and caching. The developers were surprised at the difficulty in making reasonable measurements of DNS performance and the non- decrease in negative responses when hosts converted their names to the domain-name format. Serving DNS using a Peer-to-Peer Lookup Service To counter some of the shortcomings in the current DNS (which includes significant administration expertise), the authors serve DNS data over Chord. This way, they can eliminate the root server and provide better load balancing. They also take advantage of Chord’s fault- tolerance to design a more robust system. The design, DDNS, uses Dhash to store and retrieve resource record sets (RRSets) that are lists matching domain names with resource types. Unfortunately, lookups in DDNS take longer than in the conventional DNS because Chord requires O(log2n) RPCs per lookup while the conventional DNS requires 2 RPCs. Overlook: Scalable Name Service on an Overlay Network Like the previous paper, the authors try to leverage the advantages of a peer-to-peer overlay routing network, this time Pastry, to build a scalable naming system. Overlook employs dynamic hash tables, distributed across connected servers. However, instead of operating on a globally pure peer-to-peer system, this is only limited to server-to-server systems. Their design employs a dynamic replication scheme that provides the ability to handle flash crowds. They find that Overlook is fault-tolerant, bandwidth efficient and scalable. However, latency is still a problem. Dynamic hash tables are well suited for naming services because the keys are well known. Thus, applications for communication will work really well on DHT. From mr228@cornell.edu Tue Nov 19 12:04:23 2002 Received: from travelers.mail.cornell.edu (travelers.mail.cornell.edu [132.236.56.13]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id gAJH4N911842 for ; Tue, 19 Nov 2002 12:04:23 -0500 (EST) Received: by travelers.mail.cornell.edu (8.9.3/8.9.3) id MAA16489; Tue, 19 Nov 2002 12:04:15 -0500 (EST) Date: Tue, 19 Nov 2002 12:04:15 -0500 (EST) From: mr228@cornell.edu Message-Id: <200211191704.MAA16489@travelers.mail.cornell.edu> To: egs@CS.Cornell.EDU Errors-To: mr228@cornell.edu Reply-To: mr228@cornell.edu Cc: mr228@cornell.edu MIME-Version: 1.0 Content-Type: text/plain Content-Transfer-Encoding: 7bit X-Mailer: IMP/PHP3 Imap webMail Program 2.0.9 Sender: mr228@cornell.edu X-Originating-IP: 128.84.223.176 Subject: 615 PAPER 66 Development of the Domain Name System: The DNS provides name to IP mappings for the Internet. This paper describes the development of the DNS system, the assumptions the designers made about the Internet, and current implementations. The designers took a minimalistic approach; this was necessary due to the heterogeneity of hosts on the Internet. The ultimate design was a hierarchical one with "privledged" root servers to allow for authoritative answers to queries. As you work your way down the tree, servers have a smaller domain of control. Another key component of the design is the caching. Caching happens at all levels of the tree and is a huge performance win for this system. Serving DNS using a Peer-to-Peer Lookup Service The central idea here is to propose a way to implement DNS in a distributed fashion using Chord as the overlay network. More specifically, they use DHash, a distributed hash table scheme that is built on top of Chord. The authors also highlight the need for verification of query replies and they use DNSSEC for this purpose. DNSSEc is a security extension to DNS that provides data integrity and authentication. One potential problem with this system might arise from the inequitable load that is placed on certain portions of the namespace. That is, microsoft.com is probably far more popular than other domains and with this system you need a user that (a) has the compute power and network connectivity to resovle this address and (b) a willingness to do so. The problem is that with Chord (and the fact that assignment in no way takes into account the underlying network's properties) is that it may be likely that neither is of these is the case. Overlook Overlook is a similar approach. The key difference is in the assumptions: Here we assume that all nodes are capable of serving as the lookup for popular domains. The other key contribution here is the replication. Hotspots are eliminated through this replication. They use pastry as their underlying hash table. The argue that with the replication they are able to achieve a scalable and efficient system. From ashieh@CS.Cornell.EDU Tue Nov 19 12:09:59 2002 Received: from zinger.cs.cornell.edu (zinger.cs.cornell.edu [128.84.96.55]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id gAJH9w913194 for ; Tue, 19 Nov 2002 12:09:59 -0500 (EST) Received: from localhost (ashieh@localhost) by zinger.cs.cornell.edu (8.11.3/8.11.3/C-3.2) with ESMTP id gAJH9wq07386 for ; Tue, 19 Nov 2002 12:09:58 -0500 (EST) Date: Tue, 19 Nov 2002 12:09:58 -0500 (EST) From: Alan Shieh To: Subject: 615 PAPER 66 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII What other applications can DHTs be used for? - Distributed global network testing system. Nodes within the DHT are likely to be in vastly different parts of the Internet. DHT routing allows for the dissemination of probe or test code, and the collection of accumulated data. In general, DHT is capable of maintaining and addressing a list of geographically diverse hosts; however, DHT lack the functionality to define mask parameters to address a specific subset of nodes, or to maintain metrics about node - Decentralized instant messaging, including database of users. Would require distributed CA functionality. - In general, a single popular DHT on the Internet can be used to support many robust distributed out-of-band tracking servers at once, for instance game matchmaking services. However, a bottleneck for such applications is the lack of efficient searching, and so some sort of ad hoc out-of-band mechanism needs to be fashioned for each application using this infrastructure. ** Development of the Domain Name System This paper describes the motivations and development process of the DNS system. DNS was designed to replace the centrally-managed HOSTS.TXT name file with a database that supported both distributed query processing and distributed administration. DNS supports a hierarchical namespace, with subzones of a particular domain delegated to different name servers. Queries proceed downward from the domains known to be accessible, and the results (both positive and negative) are cached at local resolvers and name serveres. For reasons of simplicity, DNS is designed as a read-only distributed database. Only out-of-band mechanisms may modify the Resource Records stored on a name server. Moreover, the performance of the caching mechanism depends on the TTL field set by the administrator for a particular RR. * Shortcomings The evolution of DNS illustrates several social pitfalls that may beset an emerging system. To promote faster, more widespread adoption, the designers of DNS chose a simple design that relied heavily on out-of-band configuration and tuning. The result was that performance of certain lookups was limited by the ability of local administrators to perform such tasks as setting proper TTL values. ** Serving DNS using a Peer-to-Peer Lookup Service This paper presents DDNS, a DNS-like naming system layered on top of Chord. Record publication is protected and signed using a certificate chain, starting from the root administrative domain and proceeding top-down through all enclosing domains. Records are distributed throughout the Chord ring using a hash on the name and type of query, and are distributed to a fixed number of replicas across the Chord ring for fault-tolerance. The standard caching mechanism in Chord to cache popular tuples in the network. As expected, DDNS incurs much higher latency than DNS for the typical query, since most queries require multiple RPCs in the overlay network for completion, whereas in DNS only a small number of Internet RPCs are necessary. The authors claim that DDNS is simpler to maintain than DNS because administrative domains need only publish RRs to the network, and do not have to configure delegation. * Shortcomings The performance of this system is quite bad. Moreover, the arguments for simpler administration are somewhat flawed. DDNS as described in this paper does not allow any tuning of TTL parameters, although due to lack of support of dynamically-generated names, TTL is much less useful. It is true that much less configuration is required for DDNS; however, this is at the cost of making client queries globally slow (by a factor of 20). Most of the common DNS configuration mistakes mentioned in the paper can be checked with some added functionality to name server configuration software. ** Overlook: Scalable Name Service on an Overlay Network Overlook is a naming service built on top of Pastry. It has a more ambitious design than either DNS or DDNS, allowing the user to specify a desired level of consistency. The system supports continuous publication and updates of names, and so proactively maintains replicas of data. Replication is performed in response to network congestion (latency-based) and CPU load. The system assumes that the P2P overlay network consists solely of nodes with high-speed connections to the Internet, e.g. no end-users on cable/dsl/dial-up, and hence the underlying Pastry network would be global infrastructure located at ISPs or corporations. As expected, hop-by-hop bandwidth limitations was found to limit the scalability of the system; with low bandwidth links at each node, the improvement in throughput saturates early on as the number of nodes is increased. Without replication, a workload biased to a subset of names is not scalable, whereas a workload that is evenly distributed is still scalable. The proactive update mechanism causes performance to degrade when the number of nodes in the system is increased above a certain point, since at that point update traffic would begin to consume a large fraction of the available bandwidth. * Shortcomings The scalability of this system depends heavily on the global availability of high-bandwidth links just for performing name resolution. System performance without replication is rather horrible. Performance with replication is good (although the workload consists of a single directory, so replication is expected to work great) over inexpensive T1 links, although they do not provide numbers regarding the amount of bandwidth expended. * Future work for naming systems - An obvious solution to some of the loss of query processing capability over peer-to-peer systems is to use mobile code as in Active Naming. - Would increasing routing base improve scalability of Overlook on lower bandwidth links? - Cost-sharing scheme for allowing companies to share bandwidth costs in a P2P system. From liuhz@CS.Cornell.EDU Tue Nov 19 14:35:41 2002 Received: from exchange.cs.cornell.edu (exchange.cs.cornell.edu [128.84.97.8]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id gAJJZf916626 for ; Tue, 19 Nov 2002 14:35:41 -0500 (EST) content-class: urn:content-classes:message MIME-Version: 1.0 Content-Type: text/plain; charset="utf-8" X-MimeOLE: Produced By Microsoft Exchange V6.0.6249.0 Subject: 615 PAPER 66 Date: Tue, 19 Nov 2002 14:35:41 -0500 Message-ID: <706871B20764CD449DB0E8E3D81C4D4302CEE71A@opus.cs.cornell.edu> X-MS-Has-Attach: X-MS-TNEF-Correlator: Thread-Topic: 615 PAPER 66 Thread-Index: AcKQAtgY792/6oQYRWuq9C9M1hT24g== From: "Hongzhou Liu" To: "Gun Sirer" Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from base64 to 8bit by sundial.cs.cornell.edu id gAJJZf916626 Develpment of the Domain Name System This is a quite old paper, published in 1988. It introduced the basic design and implement of DNS. The main contribution of this paper is that it summarized some "suprisese", "successes" and "shortcomings" of DNS. Six successes of DNS are listed in the paper. Briefly, they are variable depth hierarchy which makes DNS more flexible, oranizational structuring of names (names are independent of network, topology, etc), datagram access instead of TCP because of unexpectedly bad performance of DARPA Internet, additional section processing that can reduce the overhead of name lookup a great deal, caching scheme that's crucial to the success of this system, and lastly mail address cooperation. The main shortcomings of DNS are the difficulty to upgrade applications that use HOSTS.TXT to use DNS and the difficulty to administer DNS server. To overcome second shortcoming is one of the motivations of another paper we read today: "serving DNS using a P2P lookup service". This paper introduces a DNS system called DDNS built on top of DHash, a peer-to-peer distributed hash table based on Chord. The main goals of DDNS are to tolerate faults, balance load and ease administration of the system. However it has higher latencies and less functions compared to conventional DNS systems. One reason that lookup in DDNS is slower then that in conventional DNS is that lookup in p2p overlay networks requires typically O(log N) RPCs. In DDNS, when we retrieve an RRset from a server, we need to verify the signature of retrieved RRSet. To abain the public key, which in turns is signed by its parent's public key, that signed the RRset, we need to acheive all the public keys from all the ancesters of the node that holds the RRSet, which will introduce several lookups and thus contributes to the slow speed of DDNS in another way. At last DDNS suffers from free riders problem like many other p2p systems. Overlook: Scalable Name Service on an Overlay Network The paper introduces a name service system called overlook that provides name lookup, directories enumeration and updates services. Overlook is built on top of Pastry. To reduce the negative effect that low-bandwidth hosts have on the overall performance of peer-to-peer systems, Overlook exclude those hosts and only includes name server nodes which typically have high bandwidth and lower latencies. Name service clients will connect to server nodes and use them as proxies for their requests. The main goals of overlook are: scalability, availability, rapid propagation of updates, and fault tolerance that's offerred by Pastry for free. Now we can summarize applications that DHTs can be used for. Besides name services we see today, DHTs can also be used in archive storage systems for file backups, we have seen many such examples as CFS, PAST and etc. DHTs can also be used in peer-to-peer database systems to improve their scalabilites. From ks238@cornell.edu Tue Nov 19 14:36:14 2002 Received: from travelers.mail.cornell.edu (travelers.mail.cornell.edu [132.236.56.13]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id gAJJaE916689 for ; Tue, 19 Nov 2002 14:36:14 -0500 (EST) Received: by travelers.mail.cornell.edu (8.9.3/8.9.3) id OAA12443; Tue, 19 Nov 2002 14:36:10 -0500 (EST) Date: Tue, 19 Nov 2002 14:36:10 -0500 (EST) From: ks238@cornell.edu Message-Id: <200211191936.OAA12443@travelers.mail.cornell.edu> To: egs@CS.Cornell.EDU Errors-To: ks238@cornell.edu Reply-To: ks238@cornell.edu MIME-Version: 1.0 Content-Type: text/plain Content-Transfer-Encoding: 7bit X-Mailer: IMP/PHP3 Imap webMail Program 2.0.9 Sender: ks238@cornell.edu X-Originating-IP: 128.84.99.82 Subject: 615 Paper 66 The first paper in this section discusses the development of the DNS (Domain Name System) which is a naming system which is used to connect and help identify resources on the Internet. The first naming convention used was HOSTS.TXT which stored names to address mappings in order to provide a central point at which resources can be allocated. Unfortunately, this system scales terribly. The resulting solution was a distributed, hierarchial organized naming convention which would scale much more as the Internet’s growth continued. Two key facets of a DNS are the servers and the resolvers which together help map names to their respective addresses in an efficient manner. In addition, the name space is designed as a variable depth tree which helps enforce the hierarchy in the naming convention. Finally, two additional features are discussed to help facilitate the distribution of databases and to help facilitate efficient data lookup: zones and caching. The paper also goes into detail in some of the major shortcomings of the implementation currently being used. The next paper describes the implementation of a distributed P2P lookup service based on Chord. The primary problem with a current DNS system which was identified by the system was the issue of security and enforcing an authentication scheme to help verify the validity of DNS servers. The solution was the implementation of DDNS which uses RRSets which are lists that match a given domain with a resource type. Nodes are allocated keys using Dhash, which is a DHT employed by Chord. The primary advantaged of using Dhash is that now the system becomes evenly distributed which allows for better load balancing and increases the robustness of the system. Recall, that the DDNS implementation inherits the node failure mechanisms employed by Chord which are able to resolve failures in logarithmic time, which is quite efficient. The final paper is quite similar to the second paper in that it is a detailed discussion of a distributed hashing mechanism being applied to a naming convention such as DNS using the PASTRY protocol this time, instead of Chord as in the pervious paper. This system, known as Overlook, is a more scalable naming service than the current implementation of DNS. Due to the even distribution of nodes throughout the network, the system facilitates and is able to adapt to large number of nodes inserting in the system, robustness of the system in response to failures and is able to support high loads in the system. In this system, in order to allocate keys to certain nodes Overlook uses a DHT and hashes the entire path name used to identify a particular resource. Since each path is unique this ensure a very evenly random distribution along the circle. The primary advantages of the system are scalability, performance and availability. It is interesting that the two overlay routing schemes studied are Chord and Pastry. It would be interesting to learn of other systems which are able to implement more efficient responses to node failures. This would be an interesting area of further study for resource allocation in more varied information networks. From linga@CS.Cornell.EDU Tue Nov 19 14:52:44 2002 Received: from snoball.cs.cornell.edu (snoball.cs.cornell.edu [128.84.96.54]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id gAJJqi920271 for ; Tue, 19 Nov 2002 14:52:44 -0500 (EST) Received: from localhost (linga@localhost) by snoball.cs.cornell.edu (8.11.3/8.11.3/C-3.2) with ESMTP id gAJJqiE29952 for ; Tue, 19 Nov 2002 14:52:44 -0500 (EST) Date: Tue, 19 Nov 2002 14:52:44 -0500 (EST) From: Prakash Linga To: Emin Gun Sirer Subject: 615 PAPER 66 Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII Development of the Domain Name System ------------------------------------- This paper presents the design of DNS (as of 1988) and describes its successes and shortcomings. Initial approach was to centrally maintain a hosts.txt file (containing the mapping between host names and addresses) which is distributed to all the hosts in the Internet. This obviously does not scale well. DNS is the proposed alternative. DNS consists of two parts: name space and resolvers. Resolvers (associated with every client) help find a name server and name servers have the necessary information to answer queries. DNS name space is heirarchical (like a variable depth tree where each node is associated with a label). The concatenation of all labels on the path from a node to root is the domain name of that node. Each label is a variable length string. Zero length label is reserved for root. Labels at the same level in a subtree should be different (comparisions are case-insensitive). Data for each name in the DNS is organized as a set of resource records (RRs). Each resource record (RR) has a well-known type and class field followed by application data. Multiple RRs are used to represent multiple values of the type. Data transfer from source to intended destination is carried out using two important mechanisms: zones and caching. A contiguous section of the total tree name space is a zone. A zone also includes some pointers to other zones. `Parent' zones can delegate subzones to `child' zones. RR are cached to decrease latency. Cached items have an associated TTL field for controlled caching. Performance of the system was much worse than the original design expected. Growth in the number of networks led to lost paths and unidirectional links. Growth in load plus addition of low speed links increased latency considerably. Measurement of DNS performance was rather difficult because of unexpected effects. Caching negative results improves performance (reduces number of negative responses and delays.) Main successes are: Varible-depth heirarchy; organizational structuring of names; datagram access; additional section processing; caching; mail address cooperation. Important short-comings are: Type and class growth specifiers are too small (just 8-bit); Converting network applications to use DNS is not an easy task etc. Pros,Cons: This paper did a good job at summaring DNS and presenting its successes and shortcomings. A more extensive performance study would have helped. Serving DNS using a P2P Lookup Service -------------------------------------- DNSSEC (DNS with security extensions) allows for verification of records obtained by alternate means. This enables exploring alternative storage mechanisms for DNS records. Once such mechanism using DHash (a distributed hash-table built on top of Chord) is explored in this paper. One important shortcoming of DNS is the fact that it requires significant expertise to administer. Serving DNS over Chord using DDNS solves this by separating service from authority. This also provides better load balancing and robustness against DOS attacks. RRset is a list of all RRs matching a given domain name and resource type. DNSSEC using public-key cryptography to sign and verify RR sets. Verifying a DNSSEC RRset for a name with n path elements requires n key lookups. To alleviate this problem in DDNS, KEY RRsets for popular names are omitted (on the assumption that they are widely cached). Experiments show that DDNS does achieve the objectives of load-balancing and lookups in DDNS take much longer than in traditional DNS. Authors argue that DDNS address six of the 13 common problems associated with DNS (as outlined in Albitz and Liu). Pros,Cons: Fully distributed DNS (called DDNS) built over Chord has been proposed in this paper. This achieves better load balancin, is safe against DOS attacks and addresses some problems with traditional DNS but this has some shortcomings important of which is the increased latency. Overlook -------- This paper presents a scalable fault-tolerant name service which utilizes a P2P overlay network (like Pastry). Here we have a set of Overlook servers connected by Pastry overlay network. The Overlook servers register themselves with the DNS. Clients find an Overlook server using DNS and then send the requests to the selected server. Servers act as proxies for client requests, forwarding the requests on the Pastry network and relaying the replies back to the client. Experimental results show that Overlook scales well. Pros,Cons: Main advantages of this scheme are: It allows concurrent lookups on the same name/set of names, scales to a large number of clients, lookup latencies are very small. Simulation results look ok. Real experiments still need to be performed. New applications ---------------- One important application they could be used for is: Publish-Subscribe systems. We could have some channels with associated names. Publishers publish data on to these channels and subscribers get data from these channels. Name servers tell the subscribers where the data corresponding to a channel is actually stored. We could also use name servers in autonomous computing where devices communicate automatically with each other without manual intervention. From vivi@CS.Cornell.EDU Tue Nov 19 21:36:44 2002 Received: from exchange.cs.cornell.edu (exchange.cs.cornell.edu [128.84.97.8]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id gAK2ai920943 for ; Tue, 19 Nov 2002 21:36:44 -0500 (EST) content-class: urn:content-classes:message MIME-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" X-MimeOLE: Produced By Microsoft Exchange V6.0.6249.0 Subject: 615paper66 Date: Tue, 19 Nov 2002 21:36:43 -0500 Message-ID: <47BCBC2A65D1D5478176F5615EA7976D11AFB0@opus.cs.cornell.edu> X-MS-Has-Attach: X-MS-TNEF-Correlator: Thread-Topic: 615paper66 Thread-Index: AcKQPakyATyr34PiQDSf8+mEo45B+w== From: "Vivek Vishnumurthy" To: "Gun Sirer" Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from quoted-printable to 8bit by sundial.cs.cornell.edu id gAK2ai920943 The first paper discussed today looks at issues behind the design of DNS, and how it evolved. The growing size of the internet meant that the system of maintaining the mapping between names and addresses of all the hosts in a single "HOSTS.TXT" file was no longer viable, and there was a need for a distributed naming scheme, and this led to the birth of DNS. In DNS, the name space is organized in a hierarchical fashion, with zones controlled by single organizations. The subspace corresponding to a zone is entirely under the control of the organization that owns the zone. DNS uses aggressive caching to make future queries terminate faster. The paper identifies several areas for possible improvement: (i) A simpler way to include new types and classes has to be identified (ii) Better documentation to be provided (iii) More involved delegation of zones. The next paper describes DDNS, an implementation of storage of DNS records over Chord. This paper uses the fact that DNS records are verifiable owing to the development of DNS Secure Extension (DNSSEC), thus splitting the jobs of authentication of data and storing of the data. The owner of an RRSet signs it and inserts it into Dhash. The signature is verified before Dhash accepts the data, and when a client retrieves the data. The simulation results show that while DDNS does a good job in balancing the load across different servers, the average latency of a lookup is much worse in DDNS than in conventional DNS. The reason for the large latency is the O(log N) expected number of RPC's per query in DDNS, while in DNS only 2 RPC's are needed per lookup. Also, DDNS is unable to provide any functionality other than the bare minimum, as it requires the features to be employed by the client. The paper suggests that nodes should be incentivized to run as servers and provide required information, rather than just take free rides on other servers. The conclusion arrived at is that DDNS, (and any distributed hash-table implemented DNS) performs worse than conventional DNS. The third paper describes Overlook, a name service layered on top of Pastry. The paper identifies bandwidth as a major bottleneck in achieving scalability, and recommends placing the naming system on an overlay network of "edge of the network" servers connected with high-bandwidth links, with clients connecting to the servers to resolve their queries. The system has scalability, ability to respond to flash crowds and enabling of directory updates as the major goals. Overlook employs replication of popular directory entries to achieve load balancing. When a server sees that some directory has been requested for a large number of times, it "pushes" a replica to the node that initiated the most number of queries for the directory. Similarly when the server finds that the request rate for a particular replica has dipped, it deletes the replica. Also, when a server observes that a request is taking too long to complete, it requests a replica from the holder of the directory entry. When a directory update is to be updated, the request is routed to the root node of the directory, from where it is forwarded to all nodes holding replicas. To ensure fault-tolerance, a minimum number of replicas of every directory entry are maintained at all points of time. If strong consistency is required of the update semantics corresponding to a directory, then replication of this entry is disabled altogether. (Simulation results show that without replication, only 1000 requests/sec can be handled, far short of the design goal) Simulations show that performance degrades when there are more than 1000 nodes, because of update overheads, indicating the need for a tight replicating policy. (The assumption of the existence of the high bandwidth backbone network is questionable.) Other applications of DHT's --------------------------- This use of DHTs for storing DNS information indicates the applicability of DHTs to store any kind of information (files OR blocks OR any unformatted data), where there are a large number of users and a huge store of data, and the probability that some user wants to access some data is roughly uniformly distributed across all users and data. From bd39@cornell.edu Wed Nov 20 11:09:11 2002 Received: from postoffice2.mail.cornell.edu (postoffice2.mail.cornell.edu [132.236.56.10]) by sundial.cs.cornell.edu (8.11.3/8.11.3/M-3.10) with ESMTP id gAKG9B913638 for ; Wed, 20 Nov 2002 11:09:11 -0500 (EST) Received: from boweilaptop.cornell.edu (r102439.resnet.cornell.edu [128.253.163.42]) by postoffice2.mail.cornell.edu (8.9.3/8.9.3) with ESMTP id LAA16880; Wed, 20 Nov 2002 11:09:09 -0500 (EST) Message-Id: <5.1.0.14.2.20021119110750.00b75910@postoffice2.mail.cornell.edu> X-Sender: bd39@postoffice2.mail.cornell.edu (Unverified) X-Mailer: QUALCOMM Windows Eudora Version 5.1 Date: Tue, 19 Nov 2002 11:08:24 -0500 To: egs@CS.Cornell.EDU From: Bowei Du Subject: 615 PAPER 66 Cc: bd39@cornell.edu Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed Development of the DNS: This paper gives an historical overview of the development of the DNS system. The initial design goals of DNS were to provide host name to IP database queries, be distributed, interoperable and have relatively few limits on the size of the names. The design would strive to be frugal and provide a workable minimum of functionality. DNS divides the name space into a hierarchy of zones, which correspond to various levels of delegation of the authority to resolve certain names. - Requires central root servers to resolve top level names, which becomes a bottleneck. But this also means that top level resolutions are authoritative. - Caching works very well, but maybe cause mapping information to become inconsistant or unauthoritative. Authenticity of the cache information is also an issue. - Flexible namespace that can encode other schemes easily - Authority over a domain entails responsibility for management of naming in that domain DNS using a Peer-to-Peer lookup Service The main idea of this paper is to demonstrate a way to implement DNS in a p2p overlay network and to argue for the usefulness of such a scheme. The authors cite the load balancing behavior and ease of administration as main motivations. DNS is implemented on top of DHash by storing the DNS RR in a DHash scheme on top of Chord. Authenticty of the replies is guaranteed with signatures (DNSSEC). - Performance with the Chord servers is bad - greater than 7 times the latency of DNS. It would be difficult to motivate replacement of a working (if somewhat faulty) system with a much slower one. - DNS takes advantage of network locality of queries. (i.e. queries to machines on campus, for example, have an immediate response from the name server. Chord's distributed hash algorithm will distribute keys willy-nily throughout the entire chord network, which will increase latency. - Not all nodes are created equal, what if a very popular key, (.com) got mapped to a very inefficient host? Or if this node was extremely flaky in reliability? - Someone will still need to manage the hosts, except the problem has been extended from operators being inept system administrators to anyone who desires to join the peer-to-peer network. The idea of a peer-to-peer implementation of DNS is interesting if it could more evenly distribute the load induced upon the root servers. Overlook: Scalable Name Service on Overlay Network Overlook is a distributed naming directory service that can be built on top of any of the distributed hash schemes that we have examined before. Overlook addresses the issue of unequal peers by stipulating that only server nodes can participate in the p2p network. Directory information is stored in the usual scheme. Overlook also caches popular directories along the request route if requests exceeed a certain rate. Clients can also be migrated between servers if client request latency exceeds some threshold. Servers migrate clients to the server it forwarded its request to. When a flash of requests occur in the system (slashdot effect), copies are replicated from the home node in a tree like fashion. Updates to the data are performed from the root of the tree. Heartbeat messages are used to determined whether parent nodes are alive. (What happens when a parent dies? After a timeout, does the child contact the original? Also, wouldn't the migration of clients closer to the request home be diametric to the scheme of load balancing?)