From: Igor Svecs [isvecs SpamElide] Sent: Tuesday, March 15, 2011 12:14 PM To: Gupta, Indranil Subject: 525 review 03/15 Storage management and caching in PAST, a large-scale, persistent peer-to-peer storage utility SUMMARY PAST is a distributed storage system that is built on top of a DHT - Pastry. FileID (DHT ID) is computed by hashing file name, owner's public key, and salt. Each file is associated with a certificate, which is checked by storage nodes to ensure integrity. Files are immutable, but can be deleted from PAST by the owner who issues a reclaim command. Files are replicated to k numerically closest neighbors, but finite storage at nodes and imbalance issues lead to two mechanisms being presented - replica diversion (local load balancing), and file diversion (global load balancing). Each node uses unused portion of their advertised storage space for caching to reduce latency. PROS - Good idea of using certificates to ensure file integrity. - Modular enough to be used on top of a better DHT that takes geographic locality into consideration. - Storage management and caching are highly effective as confirmed by experimental results. CONS - This follows from Pastry - lookups minimize overlay hops instead of real hops. Geographic distribution is not being considered. - Reliable storage / compliance to routing scheme - an insert operation and replicated is not guaranteed when the first node turns out to be malicous node. The owner of the file waits for an ack from each replica manager but they can be forged. - Malicious nodes may not participate in routing correctly, causing routing loops. The authors claim that randomization solves this, but it will significantly increase lookup latency. Experimental evaluation would be very helpful. CoDNS : Masking DNS Delays via Cooperative Lookups SUMMARY The paper shows average DNS response time measurements and argues that a small percentage of lookup failure cases dominates the total time; hence, it is important to reduce time spent on these longer cases. By correlating DNS lookup failures across multiple servers, they observe that in general at least 90% of nameservers are healthy. They implemented a CoDNS daemon that uses CoDeeN CDN, and show that latency spikes under Local DNS are flatted out, and in general the latency of all requests is reduced. PROS - Interesting DNS measurement results and analysis (failures, latency, periodicity, correlation, etc). - This system is great because of its incremental approach - CoDNS can be involved only when the traditional lookup takes too long (configurable delay). CONS - They used all-to-all heartbeats to initially measure latency between any pair of hosts. Not only this would not scale, this latency information may become obsolete with time. - It is possible that CoDNS will lead to the same problem as RON (resilient overlay network): a small group of hosts running a clever protocol initially has an advantage, the overall network perfomance goes down as more and more hosts are using this system. Side node: whenever I see a protocol that collects link state information between any pair of nodes, this thought comes to my mind. - CoDNS was clearly designed for CoDeeN and the authors do not discuss how it can be adapted for other p2p networks. - Complexity. Requires an entire p2p network infrastructure to work. This complexity may lead to more bugs / vulnerabilities / management. - Many latency graphs are presented but there is no single bandwidth graph (i.e., CoDNS overhead compared to regular DNS). - Title of the paper is misleading. It is mostly a measurement paper rather than a design paper. From: Curtis Wang [cwang89 SpamElide] Sent: Tuesday, March 15, 2011 12:12 PM To: Gupta, Indranil Subject: 525 review 03/15 Curtis Wang (wang505) 3/15/11 P2P Apps CoDNS The authors have shown that in DNS, the name service is responsible for a small percentage of failures that account for a large fraction of the total time for lookups—total lookup time is dominated by failure. CoDNS attempts to minimize the lookup time required for the failures. It does so by utilizing a peer network, since most nameservers are “healthy”. When there is enough of a delay, the name service will forward the lookup to some of its peers. This delay can be adjusted to reduce the amount of network traffic and additional DNS lookups. Results have shown that asking one peer can potentially reduce the average DNS lookup by a factor of two. The system uses heartbeat measurements for roudtrip latency times between pairs of nodes. CoDNS nodes form, manage, and utilize a set of neighbor nodes that reside within a latency boundary. Pros - Reduces the average latency of lookups when compared to DNS Cons - Extra DNS lookups are performed—about 20% in practice - Extra network traffic when utilizing peers for lookups. Additional traffic from heartbeat messages to keep track of peers. UsenetDHT To reduce the storage requirements of individual servers in Usenet, the authors propose using a DHT for file storage. In the original Usenet, servers store a local copy of all of the articles, which means the data is replicated several times. By using a DHT and distributing the load throughout all of the servers, the storage savings on a single server are significant. To ensure that replicas are properly maintained, the system uses Passing Tone, which uses Merkle trees for object comparison, to determine if neighboring servers are missing data and require updates. Pros - Reduces storage requirements on each Usenet server by a factor of O(n). Cons - Participants in the DHT must be trusted - Retrieval is now done through a DHT instead of locally. Sites do not have control over what articles they have stored locally As long as the maintenance aspects are covered, using a DHT seems to naturally provide much better performance in terms of storage capacity. The result of the paper itself is not surprising, but the application of DHTs to such a system suggests that DHTs can be used in “smaller” settings, such as Usenet and do not necessarily need to be used on the scale of Amazon or Facebook. From: trowerm SpamElide on behalf of Matt Trower [mtrower2 SpamElide] Sent: Tuesday, March 15, 2011 11:46 AM To: indy SpamElide Subject: 525 review 03/15 CoDNS CoDNS is a replacement to the existing DNS system. During their deployment of a content-distribution network (CDN), the authors noticed less than optimal performance in the Internet-2 network. After tracking down the cause of the performance degradation, long delays resolving DNS queries were identified as the culprit. The paper presents an extensive study of DNS latencies in the Internet-2. Three types of failures were found in the system traces: periodic failures, long continuous failures, and sporadic short failures. Reasons are given for each type of failure with the common property that the failures are based on local issues. The authors solve these three types of failures by utilizing secondary or peer nameservers for redundancy. Significant improvements in latency were shown using these changes. The paper's study of DNS request latency was insightful and thorough. It would have been interesting to see a similar study of the Internet to show similarities. The solution seems to assume low latency between networks which is true in the Internet-2 but not the public domain. Finally, using another network's DNS servers would degrade their performance. In real networks, convincing admins to make this sacrifice would be a hard sell. UsenetDHT: Usenet is a popular forum and file sharing service which allows for arbitrary users to post data to servers which is then replicated to all interested servers. Usenet currently hosts large amounts of data with more being produced constantly (~1 TB/day). This massive storage load is the focus of the paper which looks at applying DHT principles to Usenet. UsenetDHT distributes the data amongst friendly servers instead of replicating at every server. It maintains metadata at every node in order to track the locations of actual files. Their implementation was shown to have cost reduction on the order of O(n/k) where n is the number of collaborating nodes and k is the amount of replication. The replication is still desired to a smaller degree to ensure the availability of files. Like other works Merkle trees are used as an optimization for coalescing different node's metadata. This paper shows an impressive reduction of storage and bandwidth costs for Usenet without requiring changes to the user clients. Many new issues come in to play such as k+1 servers leaving simultaneously and longer latencies retrieving data. These tradeoffs seem justified as the storage costs become quickly overwhelming for servers that maintain any amount of old data. From: wzhou10 SpamElide Sent: Tuesday, March 15, 2011 11:45 AM To: Gupta, Indranil Subject: CS525 Review 03/15 CS525 Review 03/15 Wenxuan Zhou Review on “UsenetDHT: A low-overhead design for Usenet” Core idea: This paper presents the design and implementation of UsenetDHT, a modified version of Usenet. The motivation is the high storage need of Usenet. Traditionally, every server of Usenet should keep a full replica of every article, forcing the expire time be short due to the storage limits. Usenet DHT, however, lets servers cooperate in storing articles: replicas of article bodies are stored on a subset of the servers, while the metadata is distributed and replicated as before. UsenetDHT consists of Usenet NNTP front-ends and a DHT system where articles stored. UsenetDHT uses Passing tone Algorithm to efficiently perform DHT updates: each server synchronizes its locally stored objects with its successor and predecessor to make maintenance decisions. Pros: 1. UsenetDHT leverage DHT to reduce the storage load by a factor of O(n), making efficient use of both the storage and bandwidth. 2. Caching at front-ends is enabled, improving performance after the first request. 3. Usenet DHT is incrementally deployable and scalable. Especially, no changes on clients are needed. 4. Passing Tone makes synchronization operation more efficient. Cons 1. Usenet DHT initially stores only two copies of an article, which might not be enough to tolerate fault and guarantee availability. 2. The clock difference among different sites could cause update error. 3. Users who request for an article not on its direct server may experience longer delay. Review on “CoDNS: Masking DNS Delays via Cooperative Lookups” Core idea: This paper presents a method against temporary DNS failure, CoDNS, as an alternative to the traditional domain name system. First, the authors did a solid measurement on DNS failures, and provided an analysis on the reasons of these failures. The reasons include packet loss, overload, cron jobs, and maintenance problems. Then CoDNS is proposed to mitigate the negative effects. The core idea is to forward name lookup queries to peer nodes using CDN when local server doesn’t response after a given time threshold. Pros: 1. The authors did a thorough measurement work, and more importantly provided an interesting analysis of DNS failures. 2. CoDNS is an resilient approach against temporary DNS failures. The idea is simple, if the original way doesn’t work, a detour might be faster. It doesn’t cause conflicts with existing DNS infrastructure. Cons: 1. It seems peers trust each other unconditionally. It might be the case in this paper’s experiments, but in real world, this will cause serious problems, most obvious one among which is DNS poisoning. 2. All the tests were done on planetlab nodes, so I doubt about the generality of the results. From personal experiments, planetlab doesn’t represent the real world network quite well. 3. The initial delay threshold is set as a constant, based on their observation of the RTT among planetlab nodes. The number is doubtable to me, since when I tested the RTT between an UIUC planetlab node and a Berkeley node, the result varied so much and sometimes up to 1000ms. Besides, I wonder if this value could be set dynamically. From: harshitha.menon SpamElide on behalf of Harshitha Menon [gplkrsh2 SpamElide] Sent: Tuesday, March 15, 2011 11:36 AM To: Gupta, Indranil Subject: 525 review 03/15 UsenetDHT In Usetnet each server has to pay the cost of receiving and storing 1TB/day. UsenetDHT aims to reduce this cost as well as provide other features. UsenetDHT is a usenet system that allows a set of cooperating sites to keep a shared distributed copy of Usetnet article. UsenetDHT instead of replicating the data at all servers, uses DHT to provide a single logical storage system for all sites. Usenet consists of client-facing Usenet NNTP front-ends and a distributed hash table. This uses a new replica maintenance algorithm called Passing Tone. A Usenet post reaches the front-end, its metadata is flooded through the network, but the article is stored in the DHT. In Usenet, each site contributes servers with dedicated storage to form DHT. DHT algorithm deals with load balancing, data placement and maintenance during failure. DHT stores object replicas in the k successors called replica set. Passing Tone ensures that all members of the replica set have a replica of the object even when this set membership changes. Passing Tone uses Merkle trees for synchronization. Pros: -The data is not replicated at all the servers instead it is stored in a DHT. This reduces the cost. -The caching scheme at front-end ensures that the article is retrieved only once for local clients. -The experiments show that it is linearly scalable. -Passing Tone algorithm provides good durability and availability. Cons: -The DHT is complex to construct. Storage management and caching in PAST PAST is based on self-organizing, internet-based overlay network of storage nodes that cooperatively route file queries, store multiple replicas of file and cache additional copies of popular files. It is based on Pastry routing and location scheme. PASTs storage management aims at allowing high global storage utilization and graceful degradation as the system approaches maximal utilization. Storage nodes and files in PAST are each assigned uniformly distributed ids, and replicas of a file is stored at k nodes where the nodeids are numerically closest to the files fileId. This takes care of load balancing. PAST supports caching to reduce client access latencies. Pros: -The cache management system creates additional copies of popular files and store a copy near each cluster. This reduces client latency -Uses Pastry for underlying replica location scheme. This is very tolerant to network failures. -Uses unused disk space to cache files and caching improves performance. Cons: -Since the unused disk space is used to cache files, it degrades performance when the system utilization is high. -In case of high churn, this might lead to high overhead and might degrade performance -The files are immutable. So whenever an update has to happen, the whole file is created again and distributed. Instead we could consider segmentation of files and updating only the changed portion. Thanks -Harshitha From: Shen LI [geminialex007 SpamElide] Sent: Tuesday, March 15, 2011 11:22 AM To: Gupta, Indranil Subject: 525 review 03/15 Name: Shen Li UsenetDHT: A low-overhead design for Usenet This paper propose an idea which uses a DHT system to amortize the data in Usernet network so that the burden on each node is alleviated. Traditionally, the Usenet distributes articles on an overlay netowkr of servers which connect to each other in a P2P pattern. Each node in this network has to store all data. According to their statistics, it is roughly 3TB of traffic per day. None-profit entities like universities can hardly hold such large volume of data. So Their design divide the Usenet into two parts: UsenetDHT front-end and DHash nodes. UsenetDHT front-end maintains the meta not bulk data and provides a transparent service that remains unchanged from the client view. And the bulk data is actually stored in DHash nodes. Whenever a front-end node receives a query that asks for a piece of data that it does not have, the node will retrieve the data from DHash network. Pros: 1. The first advantage is of paper is oblivious, previous Usenet node has to handle too much data which is hardly possible for many non-profit organizations. 2. I like the Passing Tone idea they mentioned in paper that transfer the maintenance of objects into the maintenance of adjacent nodes which is a much smaller set. So the traffic in the network for the maintenance is reduced. Cons: 1. The front-end node can become the bottleneck of the whole service. Previously, Usenet node only need to read data from its local disk and feed them to users. But now, their is another level that front-end node has to retrieve the data from DHash network. 2. To my point of view, the Usenet itself is not design for multimedia applications. They use flood-fill algorithms to propagate articles. We have plenty other kind of networks that is able to server multimedia data like P2P network, or dedicated data centers. Their idea mixed several different kind of design to solve the problem emerge in Usenet. Why not use a new one. 3. The meta data is distributed among all front-end node, and they should maintain the consistency of meta data. Given the fact that front-end node can be extremely busy, maintaining consistency deteriorate the problem. CoDNS: Masking DNS Delay via Cooperative Lookups This paper try to apply the Contend Distributed Networks idea into DNS system to overcome DNS failure and consequent delays. They argue that the Cornell node consistently shows DNS problems, with more than 20% of lookups showing high lookup time of five seconds or more. They think it is because the resolvers use to retry a request to another name sever. So, if they can design a better name solving architecture that takes the DNS failures into consideration this kind of delay can be shortened. Their basic contribution is designing a policy that helps to determine when to begin using remote servers and how many of them should be involved. They apply dynamically adjusted initial delay based on the recent performance of local name servers and peer responses. And each CoDNS node maintains a set of neighbour nodes within a reasonable latency boundary. Pros: According to their experiment, the CoDNS can achieve lower latency, especially when traditional DNS fails. Cons: 1. They use ICMP ping to detect the cause of DNS failure. But it may no be accurate. They also mentioned that some site enable the filtering of ICMP pings. 2. They record one day's HTTP traffic and replay the traffic on their CoDNS design. They claim that the experiment is done one month after the original day to avoid the interference of caching. But, as to me, it is hard to tell whether the influence of caching is remove. For example, some organizations or individuals may visit some site like cnn, bbc, amazon like a life routine. They visit these website every day. So, the caching data may still exist when they conducting their experiments. From: Anupam Das [anupam009 SpamElide] Sent: Tuesday, March 15, 2011 4:05 AM To: Gupta, Indranil Subject: 525 review 03/15 I. UsenetDHT: A Low-Overhead Design for Usenet Usenet is a popular distributed messaging and file sharing service used by millions of users. Traditional Usenet servers flood articles over the overlay network to achieve full replication, but this comes at the cost of large data transfer (about 1 Tbyte/per day). This paper proposes a new system called UsenetDHT which aims to alleviate the storage and scalability issue of the current Usenet architecture. The basic idea of UsenetDHT is to use distributed storage system instead of a single storage system (each server containing the full network content). UsenetDHT achieves this by splitting the data into two parts namely: actual article/data and metadata. UsenetDHT floods metadata (e.g., newsgroup, author) to all the other servers in the system but stores the actual article in only few of the servers using DHT. By doing so UsenetDHT reduces the load of receiving and storing articles per server by a factor of O(n). UsenetDHT uses a maintenance algorithm called Passing Tone to synchronize a server’s locally stored objects with its successor and predecessor. Merkle tree is used to determine the difference in the stored objects. Passing tone algorithm also supports object expiration to handle capacity overflow. Pros: 1. Reduces storage and bandwidth limitation of the Usenet network. 2. Makes Usenet scalable. 3. Uses caching in the front end which ensures that an object is retrieved at most once for local clients. 4. The system can be easily deployed as the client side remains unchanged. 5. The system was tested and analyzed in real life environment. Cons: 1. Since the system relies on DHT, some the drawbacks (like slow stabilization in presence of churn) of DHT will be inherited. 2. The designed is dependent on co-operating servers i.e., a trusted environment is assumed. This might not always be the case in real life scenarios. 3. The expiration scheme assumes that all the server clocks are synchronized. This assumption is not feasible. 4. The paper does not clearly specify the number of replications (k) needed to build a reliable system. UsenetDHT uses k=2, but does not discuss why exactly this value is used. 5. Since DHT are used, the lookup time for an article might be much larger than the traditional Usenet. 6. Predecessor maintenance algorithm does not guarantee the correct predecessor list. So unnecessary replications can occur, causing bandwidth wastage. 7. Passing Tone algorithm does not provide strong consistency but rather eventual consistency. -------------------------------------------------------------------------------------------------------------------------- II. CoDNS: Masking DNS Delays via Cooperative Lookups Domain Name System (DNS) is the service that converts machine names (URLs) to IP addresses. It has been an integral part of the Internet. However, the authors of this paper have observed through careful measurements that traditional DNS encounters various failures which induce large delays. With the motivation of reducing this latency they propose a locality and proximity aware design in the presence of local DNS server failure/delay which they call CoDNS (Cooperative DNS service lookup). CoDNS tries to adopt a distributed DNS architecture rather than the hierarchical DNS structure to improve latency. In CoDNS each nameserver node maintains a list of other nameserver nodes (neighbor list) that are located close by and uses this list whenever it fails to respond to any lookup request. So basically in the CoDNS design each node runs one master process and several slave processes and whenever a lookup request is sent to a node its master assigns the request to one of its idle slave processes. The slave process tries to respond to the request but if it fails (within a certain period) then it forwards the request to one (or more) of its neighboring peers which repeat the whole procedure again. The delay between the initial query and a redirected query to a peer node is dynamically adjusted based on the recent performance of the local name-server, so as to reduce the overhead incurred due to unnecessary remote requests. In the CoDNS design each node maintains 30 peers within a reasonable latency boundary and continuously (every 30 seconds) monitor this list by sending heartbeats to each of these nodes. Experimental results show that 18.9% of the traffic use remote queries and 34.6% of these queries return a valid DNS response faster than the local DNS lookup with relatively low overhead (0.3%). Pros: 1. Examined DNS delay under different scenarios. 2. It reduces the average response time, and increases availability of the service. 3. The dynamic adaptation of delay period enables CoDNS to work well with different servers in various locations and thus enabling it to reduce the number remote requests sent out. 4. CoDNS can be incrementally deployed. Cons: 1. The model assumes that all the nodes are trusted. However, since nodes can send out remote requests to other peers, this gives an opportunity to the malicious node to overload any remote peer by flooding it with requests and thus causing more latency. 2. The paper does not talk about how the nodes set up the initial neighbor list. In the Planetlab environment this is quite simple but in the larger Internet context this might be a problem. 3. Although 39.6% of the remote requests return respond faster than the local DNS lookup the remaining 60.4% do not. So, the gain may not be that significant. -----Anupam From: Agarwal, Rachit [rachit.ee SpamElide] on behalf of Rachit Agarwal [agarwa16 SpamElide] Sent: Tuesday, March 15, 2011 3:46 AM To: Gupta, Indranil Subject: 525 review 03/15 Rachit Agarwal ---- Storage Management and caching in PAST, a large-scale, persistent peer-to-peer storage utility The paper presents a large-scale peer-to-peer storage scheme built on top of Pastry. The ideas related to heterogeneity were really interesting. Some thoughts on the other parts of the paper: 1. PAST tightly couples the replication and the architecture. In particular, a particular set of nodes in the network are responsible for storing the file replicas. However, if a replica is stored at a node not specified by PAST scheme, it is not clear how this replica will be accessed. In this context, I believe the architecture should be more flexible: giving the publisher of the file more control over where replicas are stored. 2. PAST uses Pastry; this results in PAST importing the same inefficiencies as Pastry. In particular, the latency of file access is really not reflected by the number of hops used to access a given file. While this may not be a major concern in Pastry (due to more focus on routing), file access would require a more tight control on latencies. 3. I am not sure if PAST provides a good "load balancing" in terms of file access. There may be a few replicas of a file that are over loaded and some that are rarely accessed. 4. PAST assumes that the files are immutable. This leads to a very inefficient system when the files are continually updated/modified. I believe an incremental mechanism to achieve this could have made the paper significantly more interesting. ---- CoDNS: Improving DNS Performance and reliability via cooperative lookups This paper studies the performance of DNS in presence of failures, demonstrating that failures are widespread, uncorrelated and induce significant amount of delay in name resolution. The paper also presents an alternative architecture for improving the performance of the DNS system using cooperative lookups. In general, I find the observations made in the paper very interesting. Some comments and thoughts on the paper: 1. The number of CoDeen nodes is very small compared to the real DNS system. This leaves me wondering if in practice, the performance of DNS architecture is better or worse compared to the results presented in the paper. 2. The choice of parameters in the paper is not clear. How are these parameters chosen? Do observed results depend on the chosen parameters? 3. The design of CoDNS does not exploit/consider node proximity and/or locality. IMHO, it is a hard problem, in general, to exploit proximity and/or locality in the Internet but still, the paper leaves me thinking about the performance of CoDNS if the nodes were not connected via Internet2. 4. It is not clear how CoDNS would perform if the failures were spatially correlated? In PlanetLab, this seems to be less of a concern but in real Internet, this may be an important factor. ---- Best regards, Rachit -- Siebel Center for Computer Science, University of Illinois at Urbana-Champaign, Web: http://agarwa16.wikidot.com ---- Sing as if No one is Listening, Dance as if No one is Watching, Dream as if You'll Live Forever, Live as if You'll Die Today !! From: Nipun Sehrawat [sehrawa2 SpamElide] Sent: Tuesday, March 15, 2011 1:59 AM To: Gupta, Indranil Subject: 525 review 03/15 Storage management and caching in PAST, a large-scale, persistent peer-to-peer storage utility This paper discusses PAST, which is distributed storage utility built on top of Pastry DHT scheme. Replication for high availability and caching for load-balancing are two interesting aspects of PAST. PAST presents a simple interface of insert(), lookup() and reclaim() (reclaim is a weaker semantic than delete - file might still be available) and depends on the proximity routing feature of Pastry to retrieve the “nearest” located copy of a file being looked-up. As discussed in Pasrty paper, in the simplest form, PAST replicates a file at k closest nodeIDs to ensure high availability and load-balancing, but provides a better scheme for storing replicas in the case when these k nodes don’t have enough storage capacity. Firstly, if a k-closest-node doesn’t has enough space, then it delegates the storage to a node in its leaf-set and stores a pointer to the node that eventually stores the file. Thus, each node in k-closest-nodes subset will either store the file or will store a pointer to the file, thus expanding the set of nodes that can potentially hold the files to k-closest-nodes (UNION) leaf-set of k-closest-nodes. Secondly, in case a replica can’t be stored in this big set of nodes, the insert request is rejected and a new fileID is generated, so that the file can be stored in some other part of the DHT. Thus, a file being mapped into a region less available storage is redirected randomly to some other part of the ring. PAST employs caching to reduce latencies seen by clients and to balance query-load in the system. Intermediate nodes, in a route by which a file is sent back to requester, cache a copy of the file if some unused space is available. Cached copies can be discarded if they become too old, or if the storage space remaining at a node goes below a threshold. Pros: - A decentralized storage system with most decision making done locally. - Novel replication techniques presented to balance storage space both in the leaf-set of a node and among the entire ring. Cons: - If a file insertion fails for four times, insertion fails. - Doesn’t take into consideration the heterogenity of nodes in term of both the max storage capacity and current storage space left. Suggestion: - Although it would be again the design theme of PAST, maintaining a rough estimate of storage left at various nodes (or cluster of nodes) can be helpful. Files can then be lazily migrated to nodes with higher capacity nodes, with original nodes maintaining a pointer to new storing node. UsenetDHT: A low-overhead design for Usenet This paper presents a novel scheme for storing the enormous amount of data generated by Usenet messaging & file-sharing service, allowing a set of cooperating servers to maintain a shared copy all Usetnet articles. Typically, Usenet consists of an overlay network between geographically distributed servers and all the posted articles are replicated at all of these servers, using NNTP protocol. If a group of servers decide to collaborate, they can collectively store the articles, obviating the need of each server maintaining its own copy. UsenetDHT is built on this observation - servers collaborate to collectively store the articles in a DHT, which satisfies the requests originating from the clients registered under these servers. Instead of flooding the articles, only some meta-data information about the articles is flooded - this helps all servers to independently figure out the location of an article in the backend DHT. When a client asks for a particular article, the NNTP front-end (i.e. the server) looks up the meta-data of this article and retrieves it from DHT. The front-end also locally caches this article to serve future requests from its clients. This ensures that clients of one server don’t overload another server by reading a (popular) article stored at it. Thus, each server can see atmost n-1 remote reads, where n is the total number of servers in DHT. This setup requires mutual trust among the participating servers, as a server can reject a request for an article it stores, thus resulting in non-availability of an article to some clients (which can then abandon their server). In this setup, each site receives data proportional to the storage size they contribute to the DHT. UsenetDHT employs a replication protocol, called Passing Tone, which aims at maintaining replicas in accordance to a user-specified expiration time, while reducing disk accesses and memory required to make maintenance decisions (by using Merkel trees). Pros: - Amount of storage needed and amount of network traffic seen at a Usenet front-end NNTP server is reduced significantly. Thoughts: - How useful will a DHT based arrangement be for internal storage implementation within a ‘server’’ (set of back-end servers collectively presenting one server to clients) itself? From: Tengfei Mu [tengfeimu SpamElide] Sent: Monday, March 14, 2011 11:16 PM To: Gupta, Indranil Subject: 525 review 03/15 1. Storage management and caching in PAST, a large-scale, persistent peer-to-peer storage utility This paper proposes and evaluated PAST, an internet based large peer-to-peer storage utility. PAST is a self-organizing overlay network of storage nodes and it supports file querying and routing, file replication for high availability and caching of the most popular files so that minimize the retrieval delay. PAST also aims to provide strong persistence, scalability, high availability and security. It is based on Pastry p2p locating and routing scheme, which achieves logarithmic traversal time under normal operation. PAST assigns fileID and nodeID to each file and node in the system. Then it stores files in those nodes that most closely match their fileID. Because the ID numbers are assigned uniformly, PAST could provide somewhat load balancing and high availability in term of failures. Pros: 1. caching by utilizing unused disk space 2. load balancing ability for p2p storage system. Cons: 1. PAST need to reject few file insert request. However, when these files are very large file then there maybe some limitations. 2. PAST does not maintain the conventional file system sematics. 2. Usenet DHT: A low-overhead design for Usenet This paper presents a novel system design, Usenet DHT, which aims to manage and store distributed Usenet data across multiple servers with less bandwidth and operational cost. Usenet DHT has two components: the Distributed Hash Tables (DHTs), and Usenet NNTP front-ends. First UsenetDHT gathers space availability information from multiple servers and creates a DHT acting as a virtual shared disk. The NNTP front-end is responsible for accepting all the user requests about news articles. It could gather all the data and metadata, then create a mapping from newsgroup to the actual data location. The paper also introduces a new replica maintenance algorithm, Passing Tone algorithm, which is used to minimize the impact of monitoring replication levels on memory and disk resources by operating with only pairwise communication. Pro: 1. Linear scalability based on their experiments. 2. Usenet DHT stores only two copies initially, instead of n copies. Con: 1. The paper does not consider the case when both two copies data are lost. 2. All the Usenet DHT servers are assumed to have the same expiration time. From: david.m.lundgren SpamElide on behalf of David Lundgren [lundgre4 SpamElide] Sent: Monday, March 14, 2011 10:36 PM To: Gupta, Indranil Subject: 525 review 03/15 UsenetDHT: A low-overhead design for Usenet In UsenetDHT, Sit et al. propose an incrementally deployable, distributed hash table (DHT) redesign of the Usenet peer-to-peer system architecture to decrease server storage load linearly in relation to the number of participating DHT nodes. UsenetDHT is a two-tiered system, comprised of front-end nodes and DHash nodes. Front-end nodes maintain a list of all files stored in the network via a flood-fill algorithm among themselves. The DHash nodes form a DHT where Usenet's content is stored and replicated twice. The authors introduce the maintenance algorithm, Passing Time (PT), built off of Chord and DHash, to ensure a sufficient number of data replicas are maintained in the network. PT enforces k replicas of an object via local and global maintenance algorithms. Local maintenance allows nodes to obtain objects that they are responsible for but do not have; global maintenance distributes objects that a node has but is not responsible for. The system is implemented and evaluated using one of MIT's local feeds. The authors show that UsenetDHT performs well for their feed and they posit that the system is scalable. Pros, Cons, Comments, and Questions: - The ability to incrementally update the Usenet infrastructure to support UsenetDHT is important to counter the technological momentum of a mature system such as Usenet. - UsenetDHT's local caching enables the ~1% of content frequently accessed to reside on front-end servers. Given such a high signal-to-noise ratio, future work could focus on better identification and distribution (i.e., prioritized caching) of this small amount of relevant data. - When discussing expiration support, the authors assume servers have synchronized clocks, but it is not made clear how this clock synchronization is implemented in Passing Tone. ---------------------------------------------------------------------- CoDNS: Masking DNS Delays via Cooperative Lookups Park et al. introduce CoDNS, a cooperative domain name system (DNS) lookup service that reduces the cost of DNS failures by querying neighboring nodes in a peer-to-peer (P2P) network. The authors characterize DNS failures into three types: periodic failures, prolonged persistent failures, and infrequent burst failures. It is noted that while the many failures are resolved rapidly, the overwhelming majority of failure time is generated by long duration failures in the tail of the distribution. The authors also observe that upwards of ninety percent of nameservers are typically healthy, motivating CoDNS's design of querying neighbors to hide local DNS failures. CoDNS typically routes DNS requests to a local DNS server, it chooses to route to a remote peer if a response is not received after a certain threshold. Each CoDNS node maintains a list of active neighboring nodes based on that node's DNS round trip time and average local DNS response time. CoDNS is evaluated on PlanetLab and is shown to drastically improve the average response time of DNS and to have a very low amortized overhead cost. Pros, Cons, Comments, and Questions: - Park et al. restrict their measurements to the single testbed, PlanetLab. While they argue convincingly that their testbed is a good general representation, I believe a more rigorous study across other testbeds would have been appropriate. - CoDNS's design is guided by the discovery that the majority of request delay time is spent servicing less than twenty percent of requests. By focusing on such a small fraction of all requests, the system's overhead is amortized extremely efficiently. - The authors assume a stable network and relatively static set of node peers. Are these valid assumptions? Additional work could be done to examine the efficacy of such a system given a higher rate of churn. - CoDNS performs poorly when a requested name does not exist. Future work could examine extensions of CoDNS that help to mitigate these slow responses (perhaps a probabilistic DNS system)? From: mark overholt [overholt.mark SpamElide] Sent: Monday, March 14, 2011 9:36 PM To: Gupta, Indranil Subject: 525 review 03/15 Mark Overholt 525 Review 03/15/2011 UsenetDHT: A Low-Overhead Design for Usenet Summary: Usenet is a popular file-sharing and communication medium used by millions of users and serves terabytes of data every day. Traditional Usenet servers replicate the file contents through flood filling and this results in a large amount of data being transferred across them. This paper proposes UsenetDHT in which a set of co-operative servers are organized as a Distributed Hash Table (DHT) and share the storage providing a O(n) reduction in load. It consists of two components: the Distributed Hash Tables (DHTs) with NNTP front-end, and Passing Tone algorithm for efficient management of DHTs. UsenetDHT collect information about space availability from multiple servers and creates a DHT which acts as a virtual shared disk. NNTP front-end handles all news article user requests, collects data and metadata and creates a mapping from newsgroup to the actual articles data. Passing Tone algorithm is used for maintenance of DHTs and essentially is built on Chord and DHash. When a new article is uploaded, the system initially creates and stores only 2 replicas. Passing Tone works in a way that it ensures that there are k replicas existing at all times by partitioning servers into sets and regularly checking the availability of all replicas. Discussion: Pros: Provides scalability, load balancing, durability, and availability Costs of storing and receiving reduced to O(1/n) Each site will receive article in proportion to the storage that they contribute, rather than the complete copy of the feed. Cons: Passing Tone does not guarantee consistency as the Passing Tone do not consider a consistent set of objects across several servers. Assumes a trusted environment which restricts Usenet’s applicability. Storage management and caching in PAST, a large-scale, persistent peer-to-peer storage utility Summary: The authors in this paper present PAST, an internet based peer to peer global storage utility composed of a self-organizing overlay network of PAST nodes. These nodes may either act as access points for a user, or optionally contribute storage to past and participate in routing file operation requests. PAST uses Pastry for its overlay construction and request routing. An insert request results in routing of the request with a fileID following Pastry paradigms to the appropriate node with the same nodeID as the fileID. To increase availability of the file, the file is then inserted in k leaf nodes of this node with node IDs numerically closest to the fielD, where k represents the replication factor. In addition, for high global storage utilization, PAST introduces concepts of replica diversion and file diversion. When a node among the k leaf nodes that are to store replica of the present file, cannot accommodate a local copy, it chooses another node from the same leaf set but not among the k leaf nodes to store the file. In addition, it stores a pointer to this node in its own table to cater to lookup requests. However, if the node to which the request had originally routed is not able to accommodate replica copies of a file in its leaf set, PAST uses a different salt value to generate a new fileID and retry storage at a different node. This is known as file diversion. In addition, PAST also utilizes unused space in nodes to cache copies of files in intermediate nodes that participate in routing. Discussion: Pros: PAST considers the heterogeneity of the system, for example, nodes may not have the same capacity, file sizes may differ and so on. They try to use replica diversion as a weapon against this. The routing is built on Pastry, which is efficient and usually has a minimal number of nodes to traverse, when considered in terms of number of hops. Cons: No consideration is given at all to the time taken to insert or fetch a file. Since internet is the communication infrastructure being used, with its varying delays, the fetch or insertion time should be a prime concern when using a system like PAST. According to the paper, the free space is used as cached space. So, cache performance will surely degrade when storage usage goes up. From: yanenli SpamElide on behalf of Yanen Li [yanenli2 SpamElide] Sent: Monday, March 14, 2011 9:58 PM To: Gupta, Indranil Subject: cs 525 review 03/14 cs 525 paper review 03/14 Paper 1: Storage Management and caching in PAST, a large scale persistent peer-to-peer storage utility. PAST is based on self-organizing Internet based overlay network of storage nodes that cooperatively route file queries, store multiple replicas of files, and cache additional copies of popular files. PAST supports three major operations: insert, lookup, and reclaim. 1. insert: given a filename, owner's credentials, number of replicas desired (k), PAST generates a suitable fileId and stores the file at 'k' nodes that are nearest in the Id-space. 2. lookup: given a file name, retrieves a copy of the file from the nearest available replica. 3. reclaim: reclaims the storage of k copies of the file. It does not guarantee that the file is no longer available. There are two schemes proposed to handle storage imbalances in the PAST nodes: 1. replica diversion: if one of the k closest nodes to the given fileId does not have enough space to store the file, it looks for another node in its leafset, which has enough space and no other copy of the file. 2. File diversion: If no suitable node is found for replica diversion, the entire request is reverted and the client is forced to choose a different fileId by using a different salt. pros: - high utilization using proposed storage management schemes. - addresses storage load balance problem thoroughly cons - in reclaim, PAST does not guarantee that the file is no longer available. - there is no trust negotiations and security control involved and any node can join the network. - the diversion schemes are optimized for small files and may not work as well for larger files. Paper 2: CoDNS: Improving DNS Performance and Reliability via Cooperative Lookups summary: DNS (Domain Name System) lookup service is a basic service for looking address of the target machine in the internet. This paper presents CoDNS, a co-operative DNS service that uses a locality and proximity aware design to achieve lower latency lookup service when local DNS servers fail. The authors show that part of the internet latency is attributed to the failures in DNS lookup service. The major idea of CoDNS is that when one local name server fails, it forwards name lookup service to peer healthy DNS server nodes. The delay between the initial query and a redirected query to a peer node is dynamically adjusted based on the recent performance of the local name-server. Experiment results show that sources of delay are reduced significantly by using the CoDNS design. pros: - using sound probability theory to motivate and establish the design of CoDNS. - relative simple design which resolves the problem after a local DNS failure cons: - is the delay due to DNS lookup failures is frequent? If not, the importance of the problem is doubted. - introduce extra security issues. For example, the hackers now have many more DNS targets to hack than the original design. -- Yanen Li Ph.D Candidate Department of Computer Science University of Illinois at Urbana-Champaign Tel: (217)-766-0686 Email: yanenli2 SpamElide From: lewis.tseng.taiwan.uiuc SpamElide on behalf of Lewis Tseng [ltseng3 SpamElide] Sent: Monday, March 14, 2011 7:37 PM To: indy SpamElide Subject: 525 review 03/15 CS 525 - Review: 03/14 P2P Apps UsenetDHT: A Low-Overhead Design for Usenet Emil Sit et al, NSDI 2008 The paper first identified the main problem of Usenet, a popular distributed messaging service that shares huge amount of newsgroup messages, music files, and movies over Internet. The replication scheme used by original Usenet induces too much overhead, so the paper proposed UsenetDHT that maintains DHT in the front-end servers to reduce the overhead and provide higher storage performance. The first contribution is to build Usenet on top of DHT, because DHT can efficiently handle data placement, load balance and fault tolerance. Due to the need to support NNTP and the original economic model, such an implementation is non-trivial. The second contribution is the introduction of Passing Tone. The algorithm uses local and global maintenance to perform garbage collecting while to keep enough replicas to tolerate fault at the same time. Local maintenance algorithm ensures that enough replicas are distributed in the current replica set (neighbors within some pre-defined range). Global maintenance algorithm is used by the sever to hand out those replicas that are no longer should be stored locally to a remote servers. With deliberate design, global and local algorithms complement each other and provide enough replicas for fault-tolerance and availability efficiently. Comments/questions/critiques: Due to the usage of DHT, now every server has to cooperate with each other for lookup queries every time in UsenetDHT. It is unclear to me whether this scheme works well under the assumption of selfish behaviors, because under this assumption, some servers that have less number of users and thus have less revenue might not want to handle so many queries which consumes more bandwidth and thus boosts up cost. I argue about this point, because economic model has been brought up several times and seems to be one focus in the paper. But I am not sure if the base design considers the core concept of economics at all, selfish behavior. Usenet assumes a homogeneous deployment to provide a full feed and approaches the bound of O(1/n). However, is this assumption realistic in real world, especially in such a widely deployed P2P application? I would be surprised if this is true. If there is huge difference between nodes in UsenetDHT, how would the performance be affected? More importantly, how the “economic model” be affected? Would faster and larger (in storage capacity) nodes still want to participate in UsenetDHT? If they are selfish, then these better nodes might leave UsenetDHT, and only slower and smaller ones are left. One design I do not quite understand is that local and global maintenance algorithms do not consider expiration. Passing Tone seems to be an appropriate place to handle expiration. All it needs to do is to perform extra check. Only reason I can think of is to make the common case quicker so that UsenetDHT can perform maintenance efficiently. However, the paper does not explicitly discuss about it. Moreover, the separation of object storage and synchronization trees seems to be less efficient and synchronized clock assumption is not very realistic. CoDNS: Improving DNS Performance and Reliability via Cooperative Lookups, KyoungSoo Park et al, OSDI 2004 This paper tried to decrease the DNS delay by targeting the client-side of DNS problems. Internal redundancy to hide lookup failures adds additional delay even for the common case. Moreover, the delay between “good” and “bad” lookups has very large difference, which might annoy user-experience. Therefore, the paper proposed a scheme called CoDNS to reduce the average day and provide more predictable performance by enforcing DNS nodes to cooperate with each other. The first and probably the most important contribution of the paper is to conduct bunch of experiments and measurements on PlanetLab and to characterize and categorize failures. There are four main reasons: packet loss (it turned out to be not so important due to low drop rate); periodic failures caused by cron jobs; long lasting continuous failures caused by malfunction or overloading; and sporadic short failures caused by temporary overloading. The paper then concluded that longer failures dominate the total time, so it should be address and handled more effectively. Borrowing the core idea from CDN, the paper proposed CoDNS to handle the abovementioned problems. The idea is very simple: whenever a local DNS server has problem, just go to peer server for lookup query. The choice of such server can be based on proximity, availability and locality. One important design choice is when to send query to peer servers and how many; however, the paper did not have a robust theoretical analysis on this issue. Comments/questions/critiques: The simple design of cooperation seems to work in simulation and experiment; however, the paper just briefly compared the scheme with two alternative designs. It would be interesting to see more analysis about why CoDNS is better under different situations and user behaviors. Only is very loose relation between peers maintained, so no any workload balance is possible. Worse, peer just “silently” drops remote queries if they are overloaded or fails to find the corresponding IP. In this way, the requesting local name server cannot distinguish from many situations: overloading peer, packet loss due to unstable link, peer failures and name-resolving failures. Wouldn’t some simple membership protocol helpful if the overhead is very small? With such information, then some smarter scheme of sending queries might be possible. From: Tony Huang [tonyh1986 SpamElide] Sent: Monday, March 14, 2011 7:31 PM To: Gupta, Indranil Subject: 525 review 03/17 * Trickle: a self-regulating algorithm for code propagation and maintenance in wireless sensor networks Core Idea: In this paper, the author introduces a gossip style protocol for propogating and maintaining codes in wireless sensor networks. It works by having each node periodically broadcast some metadata about its current version of the source code. If every nodes has the same version of code, no update is needed. Otherwise, if some nodes with an older version of code receive the update, they will broadcast their meta-data so that the nodes with the newer version would broadcast te newer version of the code so that everyone can stay up to date. It is assumed that as long as netork is connected and there is a minimum connection rate, everyone would eventually get updated. To avoid collission, Trickle divides time into periods of t. The first half of a period is defined as "read-only" period, and a random time is chosen during the second half of the interval to do the transmission. A more keeps a counter c and a threshold k. Each time the mote receives a meta-data identical to its current version, it increases the counter c. IF c is smaller than k when the timer kicks in, it breadcasts its meta-data. This ensures that there are only k*m transmission in each time interval, where m is non-interferring single hop network. Pros: - Gossip style protocol seems to be the most robust protocol in sensor networks. The polite gossip, in which each nodes broadcast its new version selectively conserves bandwidth and avoid conjestion in a wider area network. - The dynamically scaling of t convers bandwidth when there is no update necessary in the network. Cons: - If there is multiple version of the code running, and two originally partitioned network merges, the transient behavior may become very chaotic. - The protocol seems to use a lot of background bandwidth whin it's just conducting this simple task of distributing source code. How will it interfere with other concurrent service? Will it consumes too much bandwidth and time such that other protocol would not be able to run efficiently? * TAG: a Tiny Aggregation Service for Ad-Hoc Sensor Networks Core Idea: TAG is a system designed to aggregate information inside a distributed sensor network. It provides a SQL-like interface that performs MIN, MAX, AVG and TOTAL. The paper also classifies aggregates based on the attribute of the action, including tolerance of loss, sensitivity of duplicity, state requirement etc. The author provides further optimizaton for some actions based on their characteristics. In this system, the nodes are organized into a tree-like structure, the operations start from the leaf nodes and propogate upward to the root. Operations are conducted within a time deadline called epoch, which can be specified by the user. The operations can be pipelined to reduced overall operation time. Pros: - Support rich operations on sensor network. - Greately enhance the functionality of a sensor network. Cons and thoughts: - Is supporting an SQL-like semantic over a sensor network over-kill and require too much handling? How about implementing a mapreduce framework like protocol on the network? - It seems the root node has to be always on during the operation. What if the root-node dies during the operation? There should be built-in redundancy in the system since failure is a norm in the sensor network. However, it is missing from this work. -- Regards -- Tony From: Tony Huang [tonyh1986 SpamElide] Sent: Monday, March 14, 2011 5:49 PM To: Gupta, Indranil Subject: 525 review 03/15 * UsenetDHT: A low-overhead design for Usenet Core Idea: In this paper, the user improves the usenet by introducing an underlying distributed hash table to distribute storage of files across the network and alleviate the storage requirement on each node. In the original, contents are replicated across all nodes. Each local usenet node replicates all the data, and retrieval is done locally. Data propogation is done through a flooding protocol. The server holding the new piece of data flood the network with update. If a client interested in the update, the server feeds the client with the actual data. This design has drawbacks that it has high requirment for bandwidth and storage requirement. In UsenetDHT, each node dedicate machines to form a chord-like DHT ring. Data is no longer routed to all the nodes, but instead routed to nodes responsible for that pieec of data. The data is indexed by a hash of its contents. To ensure data consistency, replication is used. Objects are maintained in a Merkle tree for efficient comparison to decide if a piece of data is missing from the neighbor and require replication. Pros: - Efficient techniques that alleviates an obvious bottleneck for usenet. Cons: - Retrieval time maybe slower since now the data are not replicated locally. However, for the application usenet is used for, it may not be a big problem. Comments: The system design is very similar to the previous DHT paper we read, such as Dynamo and Voldemolt. UsenetDHT seems to be a special case of application for DHT on usenet. We have seem DHT to be used in almost every distributed storage system. An interesting question would be: is DHT applicable for every distributed system application? Under what situation would a DHT be not appliable? Also, besides storage, what other distributed applications would a DHT be most useful in. A third question is, will other classic data structure, such as tree and heap, become as useful as a distributed hashtable after they become distributed? Are there applications that are more suitable for other distributed data structure than DHT? * CoDNS: Masking DNS Delays via Cooperative Lookups Core Idea: In this paper, the author try to address the problem with local DNS server failure by forwarding name lookup queries to peer nodes. In this paper, the problem of reliability of traditional DNS system and shows that DNS services constantly undergo short outages. The pattern may be a result of server overload, heavy cron-jobs running concurrently in the same server. In order to mitigate the effect, CoDNS would query another peer server when the local lookup fails. The author compares this idea to another design, which would have the client the root name-servers when a failure happens. The author argues that the CoDNS is simple in design and reduces resource consumption in local nodes. Pros: - Again, a simple indea in design that improves the performance of the system. - Compared to the alternatives proposed by the author, this approach distributed the workload more uniformely across the network than overloading a central root-server. - Can be incremental deployed. Cons: - Is it possible to solve the problem by sharding the local DNS server. i.e, run multiple instances of a local DNS server. The back-up server would take over the duty of the main server when the main server is undergoing outages. Comments: This seems to be a very simple idea about DNS. I am actually surprised that the existing DNS server is relatively unreliable. However, I notice that most of the DNS server the author uses are shared servers hosted in universities. I wonder if servers hosted in for-profit organizations would perform better. Also, is it possible that we can built a DNS service using DHT as underlying storage system? -- Regards -- Tony From: Ankit Singla [iitb.ankit SpamElide] Sent: Sunday, March 13, 2011 6:36 PM To: Gupta, Indranil Subject: 525 review 03/15 1. PAST ---------------- Summary: PAST is a distributed persistent data store built on top of the Pastry DHT. It offers simple primitives through its API to support putting in, fetching and reclaiming (no delete guarantees) files but focuses on the background responsibility of load balancing and availability through replication. In spite of the different looking data structures on Pastry and Chord, these are fundamentally very similar and PAST uses the guarantees on routing path lengths (logarithmic in number of nodes) and restoration of topology on failures given by Pastry. Replication, together with targeting a metric-property-based 'closest' node to the destination, results in fairly low stretch in practice. PAST uses 'replica diversion' to handle much of the load balancing - this simply means storing data not at the nodes closest in hash space to the data key, but on their leaf-nodes instead. Replica diversion can also be employed by a newly joined node to avoid copying over data from other nodes, instead storing pointers to them. The primary mechanism for availability is keep-alive messages exchanged with neighboring nodes (in the hash space), with nodes picking the next closest nodes as the new neighbor when a failure is detected. Comments: It seems the put operation could be fairly expensive in terms of latency for the client - it has to wait for the slowest replica before it receives the acknowledgement. If reads are the major component of the workload, then this may not matter as much. Immutability of objects is a slightly limiting factor for some applications (say something like log-kind of data which is frequently appended). Given our prior reading on the RAID papers, my immediate thought on reading the introduction was about splitting and encoding data over multiple nodes. They do discuss this option briefly, but discard it citing increased network overhead (to connect to large number of nodes). I think this could be useful (it's similar to the chunking in other p2p file-sharing systems.) 2. CoDNS ----------------- Summary: This paper is about how redundancy in the DNS architecture manages to mask most name-resolution failures, but at the cost of significant latency. They measure the name resolution time for the CoDeeN content distribution network deployed on PlanetLab nodes and find that several lookups take on the order of seconds. The total time spent in performing these 'failed' lookups is more than 50% of total time spent on all lookups. They attempt to address the problem using other name-servers when a local name-server is facing problems. A query is forwarded to another name-server when the first one fails to resolve it within 200ms. It's unclear how this policy performs outside on the Internet2 environment. Comments: The most immediate question that arises is: How have failure rates and latencies in the DNS system changed since 2004? I was fairly happy to find that they tackled one other curiosity about their measurements - whether there is some inherent bias in their measurements (which are all from PlanetLab nodes; maybe they are all using some particular/free implementation of a local name-server etc.) They found that the software stacks on the local name-servers were fairly diverse and somewhat representative of the global name-server population. Ankit -------------------------------------------------------------------- Ankit Singla Graduate Student, Computer Science University of Illinois at Urbana-Champaign (UIUC) http://www.cs.illinois.edu/homes/singla2/ From: Qingxi Li [cs.qingxi.li SpamElide] Sent: Saturday, March 12, 2011 7:59 PM To: Gupta, Indranil Subject: 525 review 03/15 CoDNS: Masking DNS Delays via Cooperative Lookups This paper introduces CoDNS lookup service to achieve the low-latency name resolution in the presence of local DNS nameserver failure or delay. This paper also introduces their finding for the periodically failure of the nameservers. They observed that the failures of nameserver were widespread and frequent. And the delays induced through the failures dominate the time spent waiting on the DNS. All these findings are in the PlanetLab nodes and when we do some experiments on the PlanetLab nodes, we also found out the failures of the nameserver happened frequently and the time of these failures are so painful for our testing. For normal DNS query with cache record in local nameserver, if the delay is around 100ms, this failure can increase it sometimes to 10s around. So if CoDNS can solve this problem, it will be very helpful for most experiments which include DNS query in PlaneLab. However, when the authors found that the clients in the same site have the similar time for DNS lookup, it said that these failures are caused by the local DNS. However, it also may happen if the clients are not stable which also always happened when we use PlanetLab nodes for testing. It’s very difficult to test these failures just because the client or local nameserver. The main idea of CoDNS is just forward name lookup queries to peer nodes if the local nameserver has some problems. The author argues that this can also improve the size and performance of the “global cache”. However, this can also decrease the performance of “local cache”. This means that for some area specific cache records which are only be interested in one area, when there are many global cache records, this kind of records may be replaced more quickly. And for the local cache records created by the other sites’ nodes, it may waste the memory of the local nameserver. Besides this, the authors also use constant for the time to determine the local nameserver suffers a failure and so does the number of remote nodes be involved. The disadvantage of using constant is when the environment changed, the constant will not be suitable anymore. So maybe the author can find out a mechanism to determine the variables by the current networks situations. Additionally, for other approaches mentioned by the authors that the client can do the iteratively name resolutions, I think the disadvantages they mentioned are not problems. For caching in client, now most computer also do this as different persons have different interesting websites caching in client can have a long TTL and may be hit more frequently than the records in local nameservers. The management problem can also be done by users, in fact, when I do the experiments on DNS, I find that some people really run their own local nameserver in localhost for speeding up the DNS resolutions. The other problem mentioned by author is localhost nameserver will waste the resource in the nodes. However, for coDNS, it will also waste the resource of the remote nodes. Storage management and caching in PAST, a large0scale, persistent peer-to-peer storage utility This paper introduces the PAST’s replication management and caching mechanism. Besides this, it also mentions some details about PAST. The files and nodes in PAST will be randomly assigned a fileID or nodesID. Files will be put into k nodes with the closet nodeID to the fileID. And each nodes in PAST has a routing table with neighbors node, leaf nodes whose nodesID is in [IP-l/s, IP+l/2] where IP is the node’s IP and routing table. Routing table of node h has k=2b levels and level n stores the node with nodeID which the first n digit with base k is the same as node n’s nodeID and the n+1 digit is emulate all the other possible b-1 digitals. Routine from s1s2…sn to d1d2…dn will be s1s2….sn->d1c2…cn->d1d2e3….en->…->d1d2….dn. For the nth node in this routine, it will randomly choose the node in n+1 level of routing table with the same n+1 digital of the destination. If don’t have this node’s IP, it will choose one node which is numerically closer to the destination with the same first n digitals of destination. The routing is randomized to avoid the request of one client will also has the same path to the same destination as the malicious node on this path can block all the requests from the client to this destination. As mentioned before, the file will have k copies in k nodes and if these k nodes ran out of their utilization it will ask one of its leaf nodes to store a diversion copies of this file and keep a pointer to that file. The leaf node will accept this request only if it doesn’t have a diverted replica before and file size/remain size doesn’t exceed the threshold. Besides this, the leaf node will prefer to have a diverted replica of large file than multiple small file as decreasing the pointer and insertion operation’s load. For caching, PAST uses Greedy-Dual Size replacement mechanism which will replace the file with minimal c(d)/s(d) value. C(d) is the cost to store file d and s(d) is the size of file(d). This paper impress me a lot when it want to balance the load of each nodes, it considers about that different nodes will have different capacity and different files will have different size. When the other papers consider about the load balance, they only consider about the number of files in each nodes and the popularity of each file. However, I don’t think this is the optimal balance goal. The optimal balance is not that all the nodes use the same bandwidth and use same memory to store files but the fraction of the bandwidth or memory it used compared with what they can use is the same. In this optimal balance, the node with small capacity can use less memory to store files. Even PAST consider about different nodes will have different capacity, however, the diverted replication only be evolved if the original nodes run out of their capacity. Besides this, the author also didn’t mention some details of the mechanism, like how to decide the c(d) in cache mechanism and how about the original nodes’ have non leaf node to put the diverted replication.