From: pooja.agarwal.mit@gmail.com on behalf of pooja agarwal [pagarwl@illinois.edu] Sent: Thursday, February 11, 2010 12:32 PM To: Gupta, Indranil Subject: 525 review 02/11 REVIEW 02/11 By: Pooja Agarwal Paper - Resilient Overlay Networks Authors - D Andersen, H Balakrishanan, F Kaashoek, and R Mooris Conference - SOSP 2001 Main Idea: This paper proposes Resilient Overlay Network(RON) which provides applications a faster response and adaptation to link and path failures increasing the fault tolerance and performance over internet. RON is a collection of nodes connected via application layer overlay. The key ideas of the paper are as follows: 1) Provide users an interface to choose the metrics used to choose paths between two nodes in RON. The users also assign the routing policies identifying kind of traffic allowed on a network path. 2) Based on the chosen metrics, RON uses active and passive probing to find quality paths between each of the RON nodes. 3) The results obtained after probing and processing are broadcasted to all other nodes in RON. 4) The processed results are stored in a database at each node that can be queried by any other node. 5) During a failure or degraded performance, the underlying ip layer path is substituted with a different path which is selected based on the probe results. Pros: 1) RON provides general interface to allow users to specify the path selection metrics based on the application’s needs. It also provides implementation for highly used metrics like delay, loss rate and throughput. 2) It provides faster recovery from link and path failures (in few seconds) as compared to BGP routing (which takes several minutes). 3) The modular design of RON effectively divides the problem into sub tasks like conduit, router, and forwarder which allows for easy replacement of an algorithm in any sub task by a better algorithm if need arises. Cons: 1) High amount of active probing is required which itself adds a lot of network traffic and bandwidth wastage. The paper shows that for one test case the probe traffic was about 2.6 million packets for 8.3 million data packets. 2) The one to all probing between each node requires monitoring of O(n^2) network paths which becomes infeasible with even small increases in number of nodes n. 3) The main application of this paper is targeted towards smaller networks of number of nodes less than 50. However, in current days, even small networks comprise of atleast 150 to 200 nodes, hence this scheme is not even scalable for current small networks. Discussion Questions: 1) It seems like if lot of RON based private networks are established, they would be fighting for the best paths. How would these RON based networks coordinate among themselves? 2) It is also worrisome to deploy lot of co-located RON based networks. There is a high probability that these co-located RON based networks share almost the same virtual links. During an outage, the behavior of both these RON’s would be to simultaneously jump to the other best available paths. If the best available paths coincide, it could lead to congestion or instability on the network. How can we avoid such occurrences? 3) Is RON unfair to other traffic in the network? On switching to a new path will increase the RON nodes performance, but it can also potentially decrease the performance of other traffic that was currently utilizing this newly selected path. Comment : RON is an interesting idea, making it scalable would be both interesting and useful. Paper - A Scalable Content-Addressable Network Authors - S Ratnasamy, P Francis, M Handley, R Karp, and S Shenker Conference - SIGCOMM’01 Main Idea: The paper describes a scalable and fault tolerant content addressable network named CAN. CAN provides hash based access to content stored across large scale network. The nodes in CAN join over an application overlay. Many ideas were explored in the paper which are as follows: 1) Use of virtual d-dimensional space to partition space known as zone between different nodes based on the hash of the keys. The nodes in the virtual zone store the keys and the content. 2) The routing between nodes is done on the basis of greedy forwarding to the neighbors with coordinates closest to the destination. 3) Zone partitioning on join of new nodes and merging on leaving of nodes. 4) Decreasing path length by using multi-dimensioned coordinate spaces. 5) Replication of coordinate spaces by using realities increases the fault tolerance. 6) RTT based routing to prefer the topologically near nodes to route packets. 7) More than one node in each zone to increase fault tolerance. 8) Multiple hash chains and topologically sensitive overlay networks based on landmark algorithm. Pros: 1) Many schemes are proposed to increase availability, fault tolerance and scalability. 2) The design using d-dimensional spaces can be made sufficiently scalable. 3) Max peers and RTT based routing particularly allow for greater fault tolerance and efficiency. Cons: 1) The schemes mostly depend on the availability of the neighbors which might be seriously affected when outages occur in topologically sensitive overlay networks. 2) Path length is based on the number of nodes which grows as the number of nodes increases. 3) The hash based zone assignment does not guarantee uniform allocation of space. Discussion: 1) Tradeoff between path length which is based on the number of dimensions and number of states and complexity of increasing the number of dimensions. From: Shivaram V [shivaram.smtp@gmail.com] on behalf of Shivaram Venkataraman [venkata4@illinois.edu] Sent: Thursday, February 11, 2010 12:30 PM To: Gupta, Indranil Subject: 525 review 02/11 A Scalable Content Addressable Network (CAN) This paper presents CAN, a Content Addressable Network, which provides a large scale distributed infrastructure implementing hash-table like functionality. Each node in CAN is responsible for a zone, which consists of a partition from a virtual ‘d’ dimensional co-ordinate space and maintains a list of neighboring nodes for routing. Similar in functionality to a Distributed Hash Table (DHT), CAN is designed to have an average routing path of length of (d/4)n1/d while maintaining 2d neighbors per node. This result is important as the routing length and state maintained per node in CAN is independent of the number of nodes in the system. A new node joins CAN by picking a bootstrap node, routing to a random point in the ‘d’ dimensional space and splitting the zone to take ownership of a part of the zone. Node departure is detected by probe failures from neighbors and the smallest neighboring node takes over ownership of the zone. There are other design elements in CAN which can be used to improve the performance and reliability of the system. Multiple independent co-ordinate spaces, called realities, can be maintained on CAN with each node responsible for a zone in each reality. Having ‘r’ such realities would mean that the data can be replicated on each reality resulting in better fault tolerance. Also nodes can route to the nearest destination node on any reality reducing the overall path length. Experiments show that to improve routing in the network, increasing the dimensions is more effective than adding realities to the system. As nodes are placed randomly in CAN, there could be scenarios where neighboring nodes have large RTT between them. To improve the overall latency, CAN uses a design where messages are routed to the neighbor which has the highest ratio of progress towards the destination to RTT. There are two other design techniques that can be used to improve the reliability of the system. The first is to use ‘k’ different hash functions on the given key to map it to ‘k’ different points in the space. The second is to have up to MAXPEERS number of nodes responsible for each zone, with the data replicated among these peers. The latter technique also helps in reducing the path length as more number of nodes can be accommodated in the same number of zones. Load balancing among nodes can be achieved by having the data stored in some of the neighboring nodes which might have a lower load. Pros - Routing path length is dn1/d – and can have lower bounds than log n for higher values of d - Insightful techniques to increase the fault tolerance and reduce the path length at the same time. - Simulations show that design scales effectively to 2^18 nodes. Cons - It was not clear how the parameters for the ‘knobs on full’ CAN nodes were chosen. - The evaluation did not compare CAN with Chord even though the paper is cited by CAN. - Some of the techniques like the Background zone reassignment used to ensure one-to-one node to zone assignments, make the system very complex. - Results and experiences from real world deployments would be interesting. Resilient Overlay Network (RON) A Resilient Overlay Network is an architecture proposed to overcome routing inefficiencies in the Internet due to limitations of the BGP protocol. Link congestions and failures are not detected for many minutes while routing on the Internet and experiments show that routing through a single RON node can decrease the latency and increase the throughput perceived. RON is designed as a user level library and can be integrated with applications that require specific routing strategies. RON consists of a relatively small number of nodes in the network (up to say 50) all of which send probe messages to each other to determine link failures and measure latency and throughput available on the links connecting them. This data helps nodes in constructing routing tables and paths for each routing strategies and RON uses different metrics for minimizing latency, minimizing loss or optimizing TCP throughput. One important difference between RON and traditional routing is that the source node in RON determines the path of the message and intermediate nodes can forward them directly to the destination. In addition to the public Internet, links like Internet2 are available for communication across certain centers but not directly advertised in BGP. RON allows users to specify policies which can be used to filter traffic on certain networks. Two classifiers that have been designed and evaluated in RON are the ‘exclusive cliques’ classifier and a regular expression based ‘general policy’ classifier. Pros - Simple design that results in routing through just one RON node to overcome most of the outages, even without using Internet 2. - Extensive evaluation of how RON compares with normal internet routing on two real world large data samples to prove the robustness of the system. - Highly configurable design where applications can specify the routing policy and metrics to use. Cons - RON uses UDP to forward data. The paper does not discuss in detail if RON retries any packets UDP lost in transmission. - Routing through a user level library (divert sockets) has memory bandwidth and latency overheads and limits the throughput to 90 Mbps. - If there are only going to be a few RON nodes in a network, it is not clear how end user applications like video conferencing (used by many thousands of users) can benefit. Interesting points to think about - 30% packet loss forces TCP into frequent timeout based retransmissions - Outages in the edge links are very difficult to overcome. What are other ways to overcome this challenge ? - RON can sometimes pick a less effective path at lower loss rates - Some techniques in RON like tagging the flow id is inspired partly by IPv6. How will routing be improved with the deployment of IPv6 ? From: Giang Nguyen [nguyen59@illinois.edu] Sent: Thursday, February 11, 2010 12:21 PM To: Gupta, Indranil Subject: 525 review 02/11 Giang Nguyen A scalable content addressable network Then-existing peer-to-peer systems like Napster (central server stores lookup information for all files) and Gnutella (lookup information is decentralized) were not scalable. The paper's authors observe that central to a scalable peer-to-peer system is at least a scalable indexing scheme--finding out where files are located. The basic idea is to use a virtual d-dimensional coordinate space, broken into "zones" that are assigned to participating nodes. Then, some identifier of a file (eg, its name) is considered the key (key K), which is hashed to obtain a point P in the coordinate space. The node responsible for the zone containing the point P is where the content of the file (value V) is/should be stored. When a node joins the system, it picks a random node already in the system to contact and to split that node's zone responsibility. A node also maintains its neighbors' IP addresses and their zones' coordinates. Routing a message is by looking up the destination coordinates in the message and simply greedily forwarding the message towards a neighbor that is closest to the destination coordinates. The paper then describes several optimizations to reduce the average hop-count, the average per-hop latency, the reliability, etc of the systems. A shortcoming of this paper is the lack of a real world study of the practicality of the system. For example, there's no mention/address of the churn rate. The system obviously is targeted at large numbers of participating nodes (eg, 2^18). For such large distributed systems, the churn is high. The paper does not have experiments dealing with how the system behaves with high churn rates. On a more general note, I think a problem with this system and similar approaches is that a node will have to store contents for other nodes. I think this is unattractive to most users. From: ashameem38@gmail.com on behalf of Shameem [ahmed9@illinois.edu] Sent: Thursday, February 11, 2010 12:06 PM To: Gupta, Indranil Subject: 525 review 02/11 Hi Indy, Here are my reviews: Pastry: scalable, distributed object location and routing for large-scale peer-to-peer systems Reviewer: Shameem Ahmed Since early 2K, DHT based peer to peer system has gained a lot of attention from research community. The major reason is the success (in real world) of famous file sharing systems such as Napster, Gnutella, and so on. Although Napster followed centralized approach, Gnutella and subsequent file sharing systems followed the distributed manner. However, those structures were mainly unstructured and create a huge traffic just for searching for a particular object. Considering this fact, academic researchers jumped into this domain to make efficient p2p based system especially to make the look-up process faster and efficient. Many researchers proposed different DHT based system since early 2K. Surprisingly, many such systems were proposed around the same time such as Chord (SIGCOMM 2001), CAN (SIGCOMM 2001), Resilient overlay networks (SOSP 2001), PASTRY (Middleware 2001), Tapestry (Berkeley 2001), Kademlia (IPTPS 2002), and so on. Pastry was one of such system. Pastry is a generic p2p content location and routing system. Pastry is built based on self-organizing application level overlay network of nodes connected via the Internet. Pastry is distributed, scalable, fault-tolerant, and robust. One notable feature of Pastry which significantly distinguishes it from Chord (a very popular and famous DHT-based p2p system) is that Pastry considers locality. Each Pastry node is assigned a 128-bit ID, which is typically generated through one way hash function such as SHA-1. Node ID is used to indicate node's position in a circular nodeID space. Pastry routes messages to the node whose nodeID is numerically closest to the given key. The routing complexity of Pastry is O(logn). For routing purpose, each pastry node maintains a routing table, a neighborhood set and a leaf set. To route a message, a node first looks at its leaf set. If the node doesn't find the destination in the leaf set, then it uses the routing table. By consulting the routing table, the node forwards the message to a node which shares a common prefix at least one more digit than the current node. Pros: 1. Unlike Chord, Pastry considers locality it its design. 2. Routing scheme is very simple 3. Some applications have been developed based on Pastry (e.g. PAST, SCRIBE) which reflects the usefulness of Pastry in real world. Cons: 1. Perhaps, Pastry is vulnerable to Sybil attack, where attacker can spoof IP address and can take over the control of the entire pastry system. 2. Even there is no Sybil attack, any malicious node can create unnecessary traffic for DoS attack. Moreover, how to protect if malicious node generates false routing information or doesn't forward the message. 3. For proximity, Pastry only considers the Euclidean distance, which might not be a good metric all the time to determine proximity. Some other metric such as delay or bandwidth consumption can be considered for proximity as well. ========================================================================================================== ===================================== Resilient Overlay Networks Reviewer: Shameem Ahmed In Internet architecture, typical routing protocols allow scalability with the cost of reduced fault-tolerance. This cost comes from the little traffic information provided by BGP protocol. That is why, today's Internet is vulnerable to many problems such as router and link failures, configuration errors, etc. In the paper titled "Resilient Overlay Networks", the authors proposed an architecture named RON to remedy some of these problems. RON is distributed application-layer overlay where each RON nodes cooperate each other to forward data. RON utilizes redundancy in Internet architecture RON has three major goals namely: to allow fast failure detection and recovery, to integrate routing and path selection with distributed applications more tightly, and to provide a framework for expressive routing policies. To achieve the goals, each RON node exchanges the information of path quality with other nodes periodically. Each node also maintains a routing table based on path metrics such as latency, packet loss rate, available throughput, etc. By tagging the packet, RON achieves the expressive routing policies. The experimental result shows that RON achieves the goal of fast failure detection and recovery (around 15 sec), RON is able to route around certain DoS attack, RON improves in latency, throughput and loss rate and RON route is stable. Pros: 1. First and foremost, RON achieves its three major goals: faster failure detection and recovery, tighter integration of routing and path selection with the application, and expressive policy routing. 2. The idea is very simple and hence can be applicable for many real world applications 3. Many system papers are evaluated based on simulation. However, RON is evaluated in a real network rather than in simulation testbed. This makes the results provided by this paper more reliable and authentic. Cons: 1. Scalability is the most important issue of RON. 2. What is the way to select a RON node? Is there any criterion for this? 3. Another major concern is the security. It seems to me that, perhaps, RON is vulnerable to byzantine attack. ========================================================================================================== Thanks. -- Shameem Ahmed Ph.D. Student Department of Computer Science University of Illinois at Urbana-Champaign Champaign, IL USA ahmed9@illinois.edu Website: https://netfiles.uiuc.edu/ahmed9/www/ ----- Smile is a curve that straightens a lot of things in life------- From: Fatemeh Saremi [samaneh.saremi@gmail.com] Sent: Thursday, February 11, 2010 11:22 AM To: Gupta, Indranil Subject: 525 review 02/11 Paper 1: Resilient Overlay Networks This paper presents a Resilient Overlay Network (RON) that improves packet delivery in the Internet by quickly detecting and recovering from outages and path failures. The architecture works by deploying nodes in different Internet routing domains which cooperatively route packets for each other. The main feature of RON is its fastness and its routing mechanism is able to detect, recover, and route around failures in about 18 seconds on average which is much better than taking several minutes in previously proposed wide-area routing protocols. RON detects problems by aggressively probing and monitoring the paths connecting its nodes. RON nodes monitor the quality of the underlying Internet between themselves to decide whether to send the packets using direct links or by utilizing other RON nodes. RON nodes exchange information about the quality of the paths among themselves via a routing protocol and build forwarding tables based on a variety of path metrics such as latency, packet loss rate, and throughput. In addition, it integrates routing and path selection with distributed applications and sets metrics and the notion of what network conditions constitute a fault based on the applications. It also provides a framework for the implementation of expressive routing policies which on their own govern the choice of paths in the network. Their experimental results confirm that in most scenarios their architecture is able to overcome path outages and performance failures in a few seconds and improve loss rate, latency, and throughput. Pros: - Being much faster in detecting and recovering from failures, compared to previous approaches (on average, only a few seconds in RON while minutes in BGP). - Sufficiency of forwarding packets via at most one intermediate RON node in most scenarios, both for fault recovery and for latency improvements. - Using application-specific metrics for path selection and considering a situation as a failure. - Real implementation of the framework rather than just simulating it which results in more accurate data. Cons: - Not scalable: Active probing and maintenance of tables are very restrictive to increase the number of RON nodes to span the entire Internet. - Considerable bandwidth consumption due to active probing and maintenance of tables. - Security issues: No mechanism for authentication of nodes is used and besides, hidden links in the network are revealed which provides a good opportunity for attackers. - Asymmetric: Especial capabilities have been assumed for some network nodes (RON nodes). Paper 2: Pastry Pastry is a distributed, scalable, and self-organizing object location and routing substrate for the construction of a variety of peer-to-peer applications such as global file storage, file sharing, group communication and naming systems; for example PAST, a global and persistent storage utility, and SCRIBE, a scalable publish/subscribe system have been built on top of it. Each node in the Pastry has a unique numeric identifier (nodeId) which its assignment is application specific and typically is computed as the SHA-1 hash of the IP address or public key of the node. When presented with a message and a numeric key, a Pastry node efficiently routes the message to the node with a nodeId that is numerically closest to the key, among all currently live Pastry nodes. The expected number of routing steps is O(log N) and it maintains routing tables with only O(log N) entries in which N is the number of Pastry nodes. In addition, it takes into account network locality; it seeks to minimize the distance messages travel, according to a scalar proximity metric like the number of IP routing hops. Each Pastry node keeps track of its immediate neighbors in the nodeId space, and notifies applications of new node arrivals, node failures and recoveries. Pastry has been simulated for up to 100000 nodes and the results confirm that Pastry is efficient and scales well, it is self-organizing and can adapt to node failures and it has good locality properties. Pros: - Pastry routes to any node in the network in O(log N) steps in the absence of recent node failures. - It maintains routing tables with only O(log N) entries. - It takes into account locality when routing messages. - Pastry is completely decentralized, scalable, fault resilient, reliable, and self organizing. - The message overhead for handling a join is logarithmic. - It has been evaluated with results confirming its scalability and acceptable performance. - The fact that some applications have been built on top of it confirm its usability and efficiency. Cons: - When many nodes fail simultaneously, the number of routing steps required may be linear in N. - When the triangulation inequality does not hold for the proximity metric, the locality properties of Pastry routes might suffer. - Experimental results for latency, the most important measure in these systems, have not been provided directly. - Proposing an efficient solution for situations that two or more network partitions merge could be valuable. From: Virajith Jalaparti [jalapar1@illinois.edu] Sent: Thursday, February 11, 2010 11:15 AM To: Gupta, Indranil Subject: 525 review 02/11 *Review of "Pastry: scalable, distributed object location and routing for large-scale peer-to-peer systems"* This paper presents Pastry which is a scalable peer-to-peer system for distributed detection of objects, identified by unique ids. Pastry creates an overlay of nodes organized in the form of a (nearly) hypercube and maintains routing state of each of these nodes which enables nodes each of these nodes to reach the others in the overlay. The paper claims that the routing state and the maximum number of overlay hops (with high probability) are logarithmic in the total number of nodes in the overlay ensuring that the overlay can scale to a large number of nodes. The objects stored in the overlay are identified by values called “keys” and a node which is numerically close to the key value is responsible for it. The paper goes on to discuss in detail the routing state that the various nodes maintain, the routing mechanism in Pastry, how node joins and failures are handled and how Pastry can exploit locality. Further, it provides results of various experiments conducted to verify how Pastry can scale with the number of nodes in the network and how efficiently it deals with node failures. While Pastry is similar to various other DHTs in spirit (aims to provide logarithmic routing table sizes and maximum number of hops), one of the main advantages that it provides is locality. Even a few overlay hops of around 4-5 can result in very large number of hops in the physical network and thus locality is an important factor affecting the overall efficiency of operation of the overlay. Further, the routing state of Pastry is smaller compared to that in DHTs like Chord because of the possibility of using ids in a base greater than 2 (the constant factor varies which might actually be a significant reduction). The paper also briefly mentions two systems which use Pastry in practice, SCRIBE and PAST, showing the practical use of Pastry as a generic platform for deploying various peer-to-peer applications. Although the paper provides some evaluation results to showing how Pastry scales, these results are completely unrealistic and the setup used is nowhere close to real p2p systems. None of the experiments take the dynamic nature of a p2p system into account. The paper doesn’t even provide an intuition as to how well Pastry can handle churn in the system. Although it is might be believable that Pastry would eventually converge (again no arguments made for this), the period of high churn which is the actual test for a real p2p system is never analyzed in the paper. Another claim the paper makes is that the failure of L/2 nodes which are neighbors is quite unrealistic and thus even in the face of failures, messages are routed to the correct key values. This claim relies on the fact that neighbors are chosen randomly which is no longer true when locality is considered. In fact, if all the L/2 neighbors are in a single ISP and if the ISP loses connectivity to the rest of the Internet messages cannot be routed across the overlay (Although this is also a rare event, it is more likely because of locality being considered for neighbors). *Review of "Resilient Overlay Networks"* This paper provides a new overlay architecture RON which is intended for helping various Internet applications to detect and recover from path failures along with giving them the ability to chose better paths (limited to the region covered by RON), if they exist. As inter-domain routing protocols like BGP can take a long time to converge/detect alternate paths in presence of a path failure/can remain oblivious to link failures within the ASes, they can severely affect the connectivity/performance perceived by various applications. RON helps to maintain/recover in the presence of such link/path failures. Further, different applications might have different preferences for the path over which their traffic is sent but the current Internet architecture provides only one path to a particular destination irrespective of the application which is using that path. RON helps to solve this problem by allowing applications choose the paths that are more apt for them. RON nodes continuously probe the virtual links and repeatedly re-estimate the various path metrics (e.g. throughput, loss rate) of these links and the paper presents ways of estimating the required metric using the limited tools at the disposal of the end nodes. RON also provides policy based routing taking into account the nature of the current Internet. The paper goes on provide evaluation results which show how efficiently can RON work around link/path failures and choose paths which better meet the application requirements (decrease loss rates, latency). The advantages of RON are obvious: it helps to work around paths whose performance is below a tolerance level for the application in concern. It helps applications to choose paths, thus effectively improving the performance of the application. RON is the first work of its kind: cleverly exploiting overlays to take advantage of the underlying path redundancy in an application specific manner. While RON has several advantages, it is not very clear how can RON be deployed in the Internet. Who would provide the RON nodes? ISPs may not be willing to do it as it would expose their network vulnerabilities to their competitors. The paper does not discuss any such deployment issues. RON nodes must be across various AS boundaries to provide any advantage as compared to the current Internet. (Within an AS existing link-state routing protocols perform very well). Apart from this, RON requires the services (e.g. someone like Google) to be RON clients to be able to achieve the advantages provides by RON which can lead to problems with the privacy of these services. The authors also identify security as a primary concern with RON along with scalability. Further, although the experimental results presented in the paper show that RON can provide a lot of advantage, it is not quite clear how this would vary in various practical scenarios esp. because there is 40% difference in results for overcoming packet loss in RON1 and RON2. -- Virajith Jalaparti PhD Student, Computer Science University of Illinois at Urbana-Champaign Web: http://www.cs.illinois.edu/homes/jalapar1/ From: Kurchi Subhra Hazra [hazra1@illinois.edu] Sent: Thursday, February 11, 2010 11:02 AM To: Gupta, Indranil Subject: 525 review 02/11 Resilient Overlay Networks - Andersen et al. --------------------------------------------------------------- Summary -------------- This paper describes an application layer overlay network, Resilient Overlay Network (RON), that keeps up todate information about the connectivity between the nodes involved in the overlay. It uses redundant paths in the underlying internet to route packets in case of any failure of links. This makes the system highly fault tolerant and resilient. RON considers all its nodes to be connected via virtual links in a mesh network. At every node or a local group of nodes, a performance database is maintained that keeps track of performance metrics over "virtual links" with other RON nodes. On submission of a packet to the RON network, using the RON API called conduit, each node evaluates the next hop for it and forwards the packets accordingly. The next hop is evaluated based on active probing and passive observations of ongoing data to decide whether the underlying internet path or the path involving redirection through one or more RON nodes is the best one. Users have the flexibility of specifying the metrics to be optimized in finding such a path. Besides, RON also integrates policy routing in the forwarding process. The writers prove the resilience of the overlay via extensive experiments. The writers assert that the system is for use in applications that will not scale to more than fifty nodes. Pros ------- -- The time taken to overcome a failure and find an alternate routing path is short and impressive. Hence, RON successfully acieves its goal of quick fault tolerance. -- The optimization metrics can be tuned in accordance to the needs of the application, thus making RON flexible and useful in a variety of applications. -- The writers have handled many of the cases leading to failure of packet delivery and ensure end to end transmission of packets. -- Deployment and extensive experiments on the real internet increase confidence on the results and hence one the system. Cons ------- -- Since the system is not scalable, it is not very clear as to how useful it will be in any realworld application. Even a simple video conferencing application can easily scale to more than 50 remote users. RON will simply not scale in such a scenario. -- A lot of overhead is incurred in terms of storage of network maintenance information. -- Probing is used to collect information regarding the virtual links, that heavily impedes the system's scalability and introduces a heavy amount of network traffic. -- The prototype presented is not capable of forwarding in very high speed networks, which is ubiquitous in today's world. -- The security used in this overlay is based on trust, which is not enough for deployment in the internet. Other Thoughts ---------------------- -- RON maintains uptodate information about all the n-1 virtual links in a network of n nodes. However, this leads to a lot of redundant information. Various optimizations could be introduced into the system to overcome this redundancy. For example, a node could stop maintaining information about a link with high latency since this link is very unlikely to be used for routing. Besides, the overlay could be restructred such that one node maintains information about a specified number of links with neighbouring nodes, leading to decreased probing traffic and increased scalability. A Scalable Content-Addressable Network - Ratnasamy et al. ------------------------------------------------------------------------------------------------------- Summary -------------- In this paper, the writers describe a system with a scalable indexing mechanism that uses a distributed hash-table called Content-Addressable Networks. A co-ordinate space is partitioned into zones, with each individual CAN node being responsible for one (or more) zone(s). All nodes involved in CAN store a chunk of the entire hash table depending on their zone. A (key,value) pair is deterministically mapped onto a particular point,say P, in the co-ordinate space and is thus stored at the node owning the zone to which P belongs. To retrieve the value eventually, a request is routed via this infrastructure to the correct zone or node. In order to facilitate this routing and make the network fault tolerant, CAN nodes store information about its neighbours, who co-ordinate spans overlap along d-1 dimensions. The writers further show how this infrastructure is self adaptive when a node joins or leaves the network. Besides, they also point out various advantages and tradeoffs involved in varying different parameters of the network, such as dimensions of the co-ordinate space, number of nodes assigned to each zone and so on. Such an indexing mechanism can be used for large scale peer to peer systems as well as large scale storage mangament systems. Pros-- --------- -- Every node needs to maintain information about a limited number of its neighbours, that does not grow with an increase in number of nodes. The system is totally distributed with no client-server type of architecture involved. For a d-dimension space, the number of nodes can be grown without increasing per node state while the average path length grows as O(n^(1/d)). All these features make the system highly scalable. -- The system is self adaptive and highly fault tolerant. This makes it ideal for use in peer to peer systems that typically have a high churn rate. -- The addition and deletion of a node results in updates of tables of a limited number of neighbouring nodes. Thus, most of the CAN infrastructure remains unaffected by this. Cons-- --------- -- Not much of importance has been given to load balancing techniques. When a node joins the infrastructure, an exisiting neighbouring zone is simply split to accommodate the new zone. Even when a node leaves the infrastructure, its zone is simply merged with that of a neighboruing node. The writers claim that the volume of a zone will be proportional to the load on that zone since key,value pairs are spread across the co-ordinate space using a uniform hash function. However, I am not too confident about this assumption. An alternative to this could be that a node keeps a track of the size of its database, and the algorithm for splitting or merging of zones is modified to take this into account. -- The writers show that increasing the dimensionality of the co-ordinate space leads to a greater decrese in routing path lengths, than increading the number of relaities. However, the writers fail to point out any possible or intuitive reason for this. Kurchi Subhra Hazra Graduate Student Department of Computer Science University of Illinois at Urbana-Champaign From: mukherj4@illinois.edu Sent: Thursday, February 11, 2010 11:00 AM To: Gupta, Indranil Subject: 525 Review 02/11 Overlays and DHTs Resilient overlay networks , D. Andersen et al A Resilient overlay network (RON) is capable of detecting failures in the network causing the network delay and thereby, facilitate quick recovery from path (network) outages by detecting the alternative routes. RON is capable of fault-detection and recovery using alternate paths. RON aggressively probe in order to detect problems and monitor paths connecting the nodes. RON nodes exchange the information (like path metrics, latency, packet loss rate, available throughput) between each other. RON can route around most failures by using only one intermediate hop. RON provide a framework for the implementation of expressive routing policies. Advantages of RON: The wide-area routing scalability (using BGP) comes at the cost of reduced fault tolerance taking few minutes to recover as it hides some of the topological details. RON can improve reliability as different Autonomous Systems (AS) are independently configured and administered and rarely share interior links. Their failures are independent of each other. Using redundancy in the physical path, unlike BGP, RON can often find paths between its nodes RON tries to prevent disruptions in end-to-end communication by taking advantage of the underlying Internet path redundancy. . RON is designed as an application-controlled routing overlay; because each RON is more closely tied to the application using it. Disadvantages: Fault tolerance is being taken care of by RON while relying on underlying internet substrate. The scalability is neglected to improve fault-tolerance. Comments: The experiments are done on 16 nodes and the model is scalable up to 50 machines, so the recovery time for alternative path as described as few seconds, may not be true as the number of the nodes grows. So, comparing the network recovery time for a real-time network (like internet) where enormous no. of routers and paths are present, can not be compared. Pastry: scalable, distributed object location and routing for large-scale peer-to-peer systems, A. Rowstron et al Pastry is a scalable, decentralized, self-organizing distributed system for peer-to-peer applications for wide-area network. Pastry node route messages efficiently to the nodeId numerically closer to it. The nodes keep track of its neighbors and automatically adapts to the arrival and departure and failure of nodes. Different real-time applications like PAST, SCRIBE are built on top of Pastry. Advantages: Pastry minimize the distance message travel, according to the scalar proximity metric like the number of IP routing hops, as the nodes keep tracks of its neighbors. Pastry is capable of doing Self-organization and adaptation. So, pastry efficiently takes care of the node arrival or removal . Arrival and departure of any node affects only a small no. of nodes. Disadvantages: The failure detection techniques are conventional. There is not much being said about the aggressive probing like RON. Also, Pastry minimizes the distance in local sense not in Global sense, so, in some cases the distance of a message from its source increases monotonically at each step, a message tends to make larger and larger strides without the possibility of returning Comments: The experiments being performed on 100,000 nodes, the scalability results are pretty convincing. Details about the Pastry architecture is not present, only some protocols are described without much implementation issues. This may be intentional as MSR is involved. A scalable content addressable network, S. Ratnasamy et al, This paper introduces the concept of Content-Addressable Network (CAN) as a distributed infrastructure by providing scalable indexing mechanism (Hash-table like functionality) over internet. CAN is scalable, distributed, fault-tolerant and self-organizing. The robustness of CAN is assured as the failure of the nodes is being handled by Immediate Takeover Algorithm, which ensures that the failed nodes neighbors will take over the zone. Advantages: Unlike DNS or IP routing, this system does not impose any form of hierarchical naming structures to achieve scalability. CAN is composed of many individual nodes storing a chunk of the hash table. So, the load is distributed. Intelligent algorithms being adopted on how to split zones. Also, capable of taking care of simultaneous failure of multiple adjacent nodes with a safe takeover. Caching and replication techniques being adopted for Hotspots. Disadvantages: Security of this system is a major issue. Denial-of-service attacks may affect the system stability. Comments: The authors does not mention the limitations of the model very clearly, other than in the Discussion session. No details about the distributed hashing algorithm is provided. From: Nathan Dautenhahn [dautenh1@illinois.edu] Sent: Thursday, February 11, 2010 10:34 AM To: Gupta, Indranil Subject: 525 Review 02/11 Paper Review: Pastry and RON Nathan Dautenhahn February 11, 2010 1 Pastry 1.1 Summary and Overview This paper discusses Pastry a novel routing substrate for wide area and peer to peer applications. The goal of Pastry is to provide a mechanism by which Internet applications can perform decentralized, fault- resilient, scalable, and reliable routing. The problem that Pastry is attempting to solve is how to provide efficient algorithms for object location and routing within large-scale peer to peer applications. The primary contributions of Pastry include: • provide the substrate, and subsequently programming API to develop applications using Pastry • provide special algorithms that focus on using locality metrics in the routing • allow the locality metrics to be defined by the application using Pastry • routing tables are small • requires small number of hops to successfully route The latter point is one of the primary contributions of this paper. They have not done anything too novel in terms of being the first to approach this problem, but most of the other works do not deal with taking advantage of the underlying network. This means that Pastry can provide better bounds on routing performance. 1.2 Comments and Criticisms The following are my primary criticisms with the paper: • This paper is somewhat unpolished in its approach to identifying pertinent information for the reader. It took me a long time to understand the problem that they are addressing, and in truth I still don’t know where Pastry fits in the big picture. • This issue of where Pastry fits in is an important one. In the works cited, the paper refers to another similar routing and location service, Tapestry. They do not state the differences between itself and Tapestry, or how they have improved on Tapestry. The of course have developed an exiting and novel method to perform routing and location services, but they have not argued well its true novelty with respect to existing works. • I have a few problems with the experimentation. To say the least I think they have made some assumptions that force me to question their results. I have questions such as: How are they modeling the layer 3 routing? Where is timing information? How do their results compare to say Chord or Tapestry? • It appears as though they authors have focused on proving correctness of their approach and not necessarily pushed it to the upper limits. In all I think this is novel work, but that it misses on good descriptive writing, and is weak in its basic experimental assumptions. I think that it can be improved in its experimental validation. I think the protocol they have developed is extremely interesting and complete. The fact that they have chosen to include locality is the big novelty here. That is what really makes me like this work. 2 Resilient Overlay Networks 2.1 Summary and Overview This paper discusses the design and implementation of RON an architecture that performs routing at the application layer. RON does not just perform routing, but also detects and recovers from path outages and periods of degraded performance extremely quick. The authors have developed a novel technique to perform evaluation of path quality by facilitating aggressive path maintenance via probing. This allows RON to identify poor links and create new routes to a a destination. RON includes some really cool ideas such as, Flow IDs, where the initial router in the forwarding chain identifies the best path to the destination and marks it as such. This allows subsequent routers to avoid changing the path, taking advantage of the work the initial RON client provided. The authors have also included an in depth analysis of their implementation, which show that RON is extremely successful in overcoming link outages and failures. Additionally, the authors have enable application developers to develop path selection metrics that RON take into consideration when developing paths. 2.2 Comments and Concerns My primary concerns are: • RON is explicitly limited in the number of nodes that it allows, this makes non-scalable, and might not be an issue in general, but I think is a large limitation. • I believe that the Authors should not attempt to compare RON to BGP. The primary reason I say this is that RON does not purport to do the same thing that BGP does. It also doesn’t work at the same layer in the network stack. In terms of comparison to BGP RON does well in certain instances, but the lack of scalability completely hurts RON’s case because BGP scales to the entire Internet. 3 Common Themes In this section I would like to make comments on themes that I see in both papers. The major theme shared between these two papers is the ability to allow the upper level application using the routing substrates to define the metric by which to route. It allows for a semantic difference to exist in how a given object is routed, which gives greater control to the application designer. This allows the designer to obtain higher performance by fine tuning the routing components of their applications. *** Nathan Dautenhahn *** ((( dautenh1@illinois.edu ))) From: Reeni Kaushik [kaushik1@illinois.edu] Sent: Thursday, February 11, 2010 10:11 AM To: Gupta, Indranil Subject: 525 review 02/11 Hi Indy, I am inlining my reviews herewith. Thanks, Rini Pastry is a scalable, distributed object location and routing substrate for wide-area peer-to-peer systems. It consists of a self-organizing overlay network of nodes. Pros: ----- 1)Pastry takes into account network locality for minimizing the message latency which makes it better than other peer-to-peer solutions such as Chord. 2)Pastry’s decentralized and self-organizing architecture makes it highly scalable. Each node maintains local routing tables and doesn’t require propagation of global routing information. The routing tables are also storage-efficient. 3)Pastry offers high probability that the set of nodes with adjacent nodeId are diverse in geography, and jurisdiction. This property would be very useful for disaster recovery solutions which could be built on top of Pastry. 4)Routing to a node is done in a bounded number of steps O(log N) unlike Gnutella. 5)Pastry is fault resilient which is an important property in a wide-area network with a lot of churn. Cons: ----- 1)There is no mention of admission control or trust negotiations when a node first joins Pastry. 2)Security aspects have not been considered. Security and privacy would be big concerns in such a system if a node has malicious intents. 3)There are no checks for maintaining the integrity of the message along the route hops. 4)Assumes that the proximity metric is Euclidean. I don’t think that the physical distance alone is sufficient in determining a routing policy. Delay and congestion also need to be considered. 5)The evaluation is only done on a simulation. Resilient Overlay Networks RON allows fast detection of path outages and degraded performance periods. To achieve this, RON nodes periodically probe the connecting paths. The nodes then exchange information via a routing protocol and build forwarding tables based on path metrics such as latency, loss rate and throughput. Pros: ----- 1)RON allows applications to specify path selection metrics and hence, is very versatile. An interactive multimedia application may chose latency over throughput and a non-interactive application may choose throughput over latency. 2)RON provides a framework for implementation of expressive, fine-grained routing policies. 3)Fast failure detection in order of seconds. Cons: ----- 1)Scalability is a concern here as the probing traffic will become huge as the overlay network is scaled up. It won’t scale above hundreds of nodes which is quite limiting in today’s context. 2)Even if RON selects an internet path after intense probing, there are no guarantees that the packet won’t run into network congestion or delays mid-path. RON doesn’t seem to be doing any mid-path routing changes. 3)If multiple distributed applications with varying metrics coexist on the same underlying WAN, it is not clear how QoS guarantees or fairness will be ensured across applications. 4)No consideration is given to security concerns or trust violations. From: Chia-Chi Lin [lin36@illinois.edu] Sent: Thursday, February 11, 2010 9:40 AM To: Gupta, Indranil Subject: 525 review 02/11 Being able to address content in a distributed system is an important building block, as there are many applications that could be implemented on top of it. Most notably, peer-to-peer file sharing systems such as Napster, Gnutella, and FreeNet. The following two papers provide such functionality in overlay networks with a technique we called distributed hash table (DHT). Both works virtualized the content space into structures and assign nodes to take charge of certain fractions of the space. In addition, the structures are associated with efficient routing algorithms to find a value corresponding to a key. However, as we will see, these two works holds different design goals and, hence, has different pros and cons. Pastry: Scalable, decentralized object location and routing for large-scale peer-to-peer systems Pastry maps content keys and nodes onto a circular ring. The ring is divided into address blocks with size 2^b. Each node records information of neighbors in the same address blocks as well as nodes at different address levels. The associate routing algorithm leverages this information to bound the number of routing steps taken for each query. In addition, Pastry optimizes routing performance by examining proximity metric. That is, it takes locality into account and offers routes with less hop counts. The system is evaluated with a Java implementation and shown to be scalable and efficient. Pros: - Scale up to 100,000 nodes with a prototype implementation with reasonable search and state bounds. - An efficient routing algorithm taking locality into account. Cons: - Proximity metrics might not hold the Euclidean properties. - Trying to minimize routing hops instead of the more obvious metric – latency. - Might not handle churn well. - Security and privacy issues are not considered. A Scalable Content-Addressable Network CAN hashes content keys onto d-dimension spaces and assigns nodes to certain zones of the space. Nodes record information about other nodes in the same zone as well as neighboring ones. The routing algorithm greedily forwards queries towards the destination. Under normal operations, the path lengths of the queries and the per-node states are bounded. Several optimizations are proposed to address efficiency and reliability. The system is evaluated under different scales of simulations and demonstrates its scalability, robustness and low-latency properties. Pros: - With 260,000 nodes, CAN routes with a latency that is less than twice the IP path latency. - Various knobs to tune the system. Cons: - No comprehensive analysis about interactions between different knobs. - Measuring per-hop instead of end-to-end latency. - Might not handle churn well. - Security and privacy issues are not considered. Chia-Chi Lin From: gildong2@gmail.com on behalf of Hyun Duk Kim [hkim277@illinois.edu] Sent: Thursday, February 11, 2010 2:42 AM To: Gupta, Indranil Subject: 525 review 02/11 525 review 02/11 Hyun Duk Kim (hkim277) *Pastry: scalable, distributed object location and routing for large-scale peer-to-peer systems, A. Rowstron et al, Middleware 2001. This paper presents Pastry, scalable/decentralized object location and routing for large-scale peer-to-peer systems. Pastry performs application-level routing and object location. Pastry mainly uses nodeId which is unique identifier of each node. Pastry routes messages to the node with numerically closest nodeId to the key. Pastry finds fast routes by minimizing the distance using proximity metric considering network locality. This paper explains all the details of Pastry system including routing algorithm, API, self-organization/ adaptation protocol, the meaning of locality, and failure recovery. Various experiment results show that Pastry performs well as a decent building block of peer-to-peer system even with various failure scenarios. This paper covers all the related topics completely. Authors explain basic protocols and show them how Pastry works with usage scenarios like node arrival and node departure. Various experiments also well cover all the explained aspects. Even authors rebutted possible limitations. For example, I had a question of ‘the limitation of finding local optimum’ because we may be able to improve the performance of algorithm by trying to find global optimum. This paper suggested some heuristics which support local optimum philosophy and its usefulness with experiment results. However, this paper does not mention about the future work which is usually mentioned at the end of the paper. Although the paper is pretty complete, we can think some possible future works. For instance, experiments with various setups can give more ideas how Pastry work. Authors briefly mentioned that node distribution does not affect the performance, without showing real data. It would be also good to show performance results with some extreme setup. Because this is for scalable system, conducting experiment with more nodes is still meaningful. Also, connection speed/structure can show different aspects to consider. Some of connections between peers may have high bandwidth, some may not. Furthermore, not all the nodes are very well connected. That is, there can be nodes which is not connected or connected with very slow channel. ‘Distance’ factor should consider this in routing. Other heuristics for complementing local optimum path routing also can improve performance and lower cost. At last, just for curiosity, I am still wondering why authors named the proposed protocol as 'Pastry'. There is no explanation about that. * A scalable content addressable network, S. Ratnasamy et al, SIGCOMM 2001 This paper introduces the concept of a Content-Addressable Network (CAN). CAN is distributed, scalable, and fault-tolerant peer-to-peer system using hash table. It can be implemented in application level. Main design feature of CAN is a virtual d-dimensional Cartesian coordinate space. This virtual coordinate space is to store (key,value) pairs. Node join occurs by splitting space in the coordinate, and routing is done by forwarding to the neighbor with coordinates closest to the destination coordinates. In addition to the basic construction, routing, maintenance protocols, authors suggest various possible design improvements, and check its performance through experiments. This paper shows an interesting peer-to-peer system idea using hash table, and especially the section introducing possible design improvements is very interesting. Each design points are introduced intuition with effects to the performance. Readers can think important points in designing one by one. Especially, checking RTT can be very useful especially when channel speed can vary. Even RTT can be changed depending on the usage of the channel/location/time. However, this paper does not consider the different combinations of designing improvements. Although two features increase performance each, combination of those two may decrease the performance or may show only small amount of performance improvement because of interference between them. Therefore, just selecting all features which showed positive affect may not show the best performance. In the experiment section of the paper, they just compared two settings, one using basic features and the other using all the features. If they showed various combinations, it would be more interesting. When we use overloading coordinate zones, what are relationships among nodes within one space? If there is no relationship among them, it may degrade performance. In addition to overloading coordinate zone, we can think of using hierarchical spacing. If there is more than one node in one space, it is connected to another coordinates and use it for the nodes in one cell. It can be one way to deal with overloading coordinate zones. For routing, CAN uses greedy algorithm which does not guarantee the global optimum. As authors did for other system like Pastry, we may be able to supplement local optimum by adding some heuristics to avoid bad local optimum.. -- Best Regards, Hyun Duk Kim Ph.D. Candidate Computer Science University of Illinois at Urbana-Champaign http://gildong2.com From: Sun Yu [sunyu9910@gmail.com] Sent: Wednesday, February 10, 2010 9:56 PM To: Gupta, Indranil Subject: 525 review 02/11 Sun Yu 1.A Scalable Content-Addressable Network Popular peer-to-peer file sharing systems at the time of this paper are Napster and Gnutella. They both have the problem of poor scalability: although the actual file transfer is peer-to-peer, the process of locating specific file in the network is either centralized (server model of Napster) or has unsatisfactory performance (curtailed flooding of Gnutella). Using the idea of hash table, the authors proposed an alternative approach for fast and scalable file locating in peer-to-peer systems. This infrastructure, termed as \emph{Content-Addressable Network }(CAN), is essentially a distributed internet-scale hash table. Various design issues such as routing, construction of coordinate overlay and maintenance of the overlay are discussed. In the "Design improvements" section, they also covered other possible design choices such as use of multiple realities, multiple hash functions, different routing metrics, etc, along with a discussion of load balancing issues and how to constructing topological-congruent CAN. The CAN network has big advantage over traditional systems sucha as Napster and Gnutella, because it has a real peer-to-peer structure.The authors claim that per-node state scales as $O(d)$, independent of $n$, and average routing path length scales as $O(dn^{1/d})$. I do have some questions about a few details in the paper. For example, at the very beginning of section 2, it reads "Our design centers around a virtual $d$-dimensional Cartesian coordinate space on a $d$-torus". Why it's necessary to define a coordinate space on torus? Wouldn't a regular hypercube also suffice? I didn't find the answer from reading the rest part of the paper. My guess is that this is so designed to meet the need of greedy forward routing, providing more robustness? Another question is, would it be beneficial to introduce some hierarchy? For example, can we implement this CAN structure solely on servers to provide more stable file sharing service? This results in a backbone CAN network with each node being a server, and users connect to topologically nearby servers to get file. We may overload the coordinate zones to improve robustness with respect to server failure. This goes back somehow to the centralized structure on user level, the server may become very busy because all file-request and file-transfer traffic needs to go through it. This question may be naive, basically what's in my mind is when some peers are more powerful than most others, is it a waste of resource to just serve as an ordinary peer? 2. Resilient Overlay Networks This paper introduced the concept of Resilient Overlay Network (RON), which provides application-layer routing control. The goal of RON is to enable reliable packet delivery through fast detection and recovery from path outrage, failure, performance downgrade and intelligently routing around them. By actively monitoring the path connecting them, RON nodes collect up-to-date information about quality of those Internet paths. When packets are to be sent, RON choose the optimal route by optimizing some application-specific metric. The implementation of RON is on application-layer, so it doesn't require change of existing Internet routing substrate. However, suppose we want to implement RON on some wireless network (say, sensor network? ) when the communication is expensive. In this case if we want to guarantee a timely detection of link failure, the corresponding probing overhead can be too much to afford. It would be interesting to see if a proper optimization problem can be formulated out of this. Also, for some applications maybe we can monitor some important paths more closely, leaving other link less frequently probed? From: ntkach2@illinois.edu Sent: Wednesday, February 10, 2010 9:09 PM To: Gupta, Indranil Subject: 525 review 02/11 Nadia Tkach - ntkach2 CS525 – paper review 1 Topic: Overlays and DHTs Paper 1: Resilient Overlay Networks The paper describes and analyses the new Resilient Overlay Network (RON) architecture (at the time of the paper was written). Implemented on top of Internet routing structure this application-level overlay can detect and recover from outages and performance failures on the network over a very short period of time comparing to the currently existing routing protocols. Each RON node would contain a table of neighboring nodes and links in between and maintain the information about their performance via monitoring and probing. As the experiments show RON take on average 20-30 seconds to detect and re-route the traffic of about 60% - 100% of outages. In general this architecture can improve the loss rate, latency and throughput of the network. Pros: • Short time detection and recovery mechanism for path outages Cons: • There were only collected two experimental datasets based on a few days of measurement with 12 and 16 nodes on the network. It would be useful to see the performance statistics on a larger scale with hundreds of nodes to evaluate the benefits. • Improvements in latency and throughput in 11% and 5% of samples don’t sound very significant for a project of global scale implementation • Consider the feasibility of implementing of RON architecture on the Internet, that is manual or automatic installation and update of the routing application on selected nodes. Paper 2: A Scalable Content-Addressable Network The paper describes the Content-Addressable Network infrastructure that promises scalability, fault-tolerance and self-organization for any distributed system whether it is peer-to-peer system or large storage management network. The principle behind CAN concept is to dynamically divide the network into zones and have one or more nodes that contain routing tables and indexed data, and provide the information to the requesting client. The zones are dynamic and whenever the new nodes join or older ones leave the partitioning automatically changes to represent the new state of the system (split or merge zones). Pros: • CAN handles such cases as when a node leaves without notification, a neighboring node take over and merge the two zones together • Improved performance with overloading coordinate zones (reduced path length, per-hop latency, improved fault tolerance) • Caching and replication of data with a high demand Cons: • Not resistant to DoS attacks • Tested and evaluated via simulator • Consider the case when nodes frequently join and leave the area From: Ghazale Hosseinabadi [gh.hosseinabadi@gmail.com] Sent: Wednesday, February 10, 2010 7:53 PM To: Gupta, Indranil Subject: 525 review 02/11 Paper 1: A Scalable Content-Addressable Network, S. Ratnasamy et al, SIGCOMM 2001 A hash table is a data structure that efficiently maps “keys” onto “values”. Many large-scale distributed systems could likewise benefit from hash table functionality. Content-Addressable Network (CAN) describes such a distributed, Internet-scale, hash table. In CANs, an indexing mechanism is used to map file names to their location in the system. The basic operations performed on a CAN are the insertion, lookup and deletion of (key,value) pairs. In the designed CAN, a virtual d-dimensional Cartesian coordinate space on a d-torus is constructed. This virtual coordinate space is used to store (key,value) pairs as follows: to store a pair (K1,V1), key K1 is deterministically mapped onto a point P in the coordinate space using a uniform hash function. This work addresses three key problems in the design of CANs: CAN routing, construction of the CAN coordinate overlay, and maintenance of the CAN overlay. Two example networks in which CAN can be used are scalable peer-to-peer systems and large scale storage management systems. Through simulations, they showed that in a CAN with over 260,000 nodes, routing can be done with a latency that is less than twice the IP path latency. Pros: This paper presents a lot of metrics and parameters through a clear mathematical framework. The main idea of the paper is simple but interestingly a lot of capabilities can be easily added to the basic design. Cons: Mathematical analysis for the scalability of the proposed CAN is missing. The security issues are not disscussed in this paper. Presense of attackers prevent functionality of CAN. Are we able to make the designed CAN secure or a secured CAN should be designed from scratch? Any comparison with existing work. Paper 2: Resilient Overlay Networks, D. Andersen, et al, SOSP 2001 This paper describes the design and implementation of RON ( Resilient Overlay Network ). RON is a wide-area network overlay system that can detect and recover from path outages and periods of degraded performance within several seconds. RON basically exploits redundancy in underlying internet to recover from different kinds of failure. There are three main objectives in the design of RON: 1) RON is capable of failure detection and recovery in less than 20 seconds. 2) RON allows different applications to independently define and react to failures. 3) RON implements expressive policy routing which determines the choice of path in the network. RON is defined by a set of RON clients. Path evaluation and selection is done using an active probing implemented by each RON router. Each RON router maintains three information for each virtual link: 1) latency, 2) packet loss rate, 3) throughput. This information is used to evaluate the quality of the Internet between RON routers and to decide whether to use direct Internet routing or by way of other RON nodes. Their simulations show that RON is capable of handling of high percentage of Internet outages. Pros: Their idea of building an overlay network on top of Internet for handling failure is easy to implement in small scales and as their results show the overlay network is capable of overcoming failures successfully. Maybe this idea of adding an overlay network on top of internet can be used to overcome other issues, such as providing quality of service, node location or handling different security issues for example intrusion detection. My guess is that the overlay network will decrease the delay in performing the above mentioned tasks. Cons: The main issue of RON is the scalability problem. Each RON router implements active probing and maintains a routing table. Both imposes too much load and overhead to the network when the size of the network grows. It is not clear how RON is built on top of a network. Which nodes of the current network are chosen as RON nodes? Security issues should also be considered in implementing RON on top of a real network, since traffic is routed via RON nodes. From: arod99@gmail.com on behalf of Wucherl Yoo [wyoo5@illinois.edu] Sent: Wednesday, February 10, 2010 6:44 PM To: Gupta, Indranil Subject: 525 Review 02/11 525 Review 02/11, Overlays and DHTs, Wucherl Yoo (wyoo5) Pastry: scalable, distributed object location and routing for large-scale peer-to-peer systems, A. Rowstron et al, Middleware 2001. Summary: Patry provides scalable overlay P2P network. Each node has a 128-bit globally unique identifier (GUID) that is hashed value. It maintains a leaf set, a routing table, and a neighborhood set. The leaf set consists of numerically close nodes. The routing table stores GUID prefixes and corresponding (GUID, IP) pair. The table is structured for radix-r search, object lookup and application-level routing require O(log N) with base r. In the paper, r is chosen as 2^b. Numerically close nodes can be found on upper rows by matching longest prefixes so that lookup time to be reduced. The neighborhood set stores proximately close nodes using proximity metric such as the number of IP routing hops or geographic distance. This set helps to consider locality for routing since the numerically close nodes may not be proximately close. Node join, leave, failure detection, and replication of objects are similar as Chord. Pros: Compared with other P2P overlay network such as Chord, it considers locality of nodes to reduce latency of routing with the proximity set. Cons: Although the authors propose randomization mechanism to be resilient against malicious nodes, it is still not sufficient to defend Pastry against the attackers. It does not address how to handle inconsistency of maintained three sets due to Churn. Resilient overlay networks , D. Andersen et al, SOSP 2001 Summary: The internet routing can be failed due to multiple reasons. However, re-routing takes significant time between BGP-4 routers that connect different Internet routing domains. RON is application-level overlay network consisting of small number of nodes. Each node of RON monitors the functioning and routing. Ron Nodes exchange the monitored information periodically and stores it into database. Using the information, the RON node can choose the routing path either directly over the Internet path or indirectly via RON nodes. This helps the application to select best path based on the application specific requirement. Pros: Fast recovery when routing fails Cons: Not scalable (small number of RON nodes) Difficult to deploy to current Internet – Different routing domains would stick to BGP protocol-Wucherl From: Shehla Saleem [shehla.saleem@gmail.com] Sent: Wednesday, February 10, 2010 2:22 PM To: Gupta, Indranil; indy@ad.illinois.edu Subject: 525 review 02/11 Pastry: Scalable, decentralized object location and routing for large-scale peer-to-peer systems This paper presents Pastry: A decentralized, scalable object location and routing service for large peer-to-peer systems. A decentralized peer-to-peer system is clearly the most desirable. This is to avoid the whole system coming down in case of a single failure. Also, the popularity of peer-to-peer applications dictates the need for high scalability. Furthermore, good locality properties are attractive so that packets do not travel unnecessarily in the network. Pastry seems to address all these issues reasonably. It starts by assigning unique NodeIds to all pastry nodes from a 128-bit circular namespace. A routing table is maintained using NodeIds of known pastry nodes. Given a message and a key, routing of messages is done towards nodes with NodeId closest to the key. Node joins and failures are dealt with by using a few additional message exchanges. A few issues came to mind while understanding Pastry. For systems where the churn is very high, it might not be trivial to keep a current (up-to-date) list of live nodes. Also, for nodes newly joining the system for a short time, building such a complete list seems debatable because of the overheads involved. This would especially be true if the new node happens to be closer to the keys of many large objects and would require all these objects to be transferred to it. Maybe there should be some criteria on how long a node intends to stay on the network (excluding the possibility of a crash failure which may occur at any time) before scheduling large objects to be transferred to it. Another question that remains unanswered is the issue of security. Pastry only guarantees message delivery to a node with the NodeId closest to the key. What if a malicious node chooses its nodeId such that it becomes closest to some popular file/object and then all requests for that object reach the malicious node which may simply refuse to provide it and/or corrupt it. If many such nodes join in this, they may make sure that even redundant copies of the file may all be located on them and will never be available on the network. Also, malicious nodes might generate large files and have other nodes store them thus taking up their storage resources. Finally, as with any other system depending on some keep-alive messages, Pastry would also have to deal with the trade-offs involved in how frequent should a node probe its neighbor to check for liveness. The more often this is done, the smaller the window of vulnerability where a node has stale information about its neighbors but the higher the overheads. A Scalable Content Addressable Network This paper tries to address the main scalability issue that comes with any large scale peer-to-peer system i.e. the underlying indexing mechanism. The authors present "CAN: A Scalable Content Addressable Network”. The system is completely distributed and the basic principle is still that of using hash table like functionality for mapping (Key,Value) pairs. However, each node stores a portion (termed a Zone) of the hash table and requests for a particular key are routed in a greedy manner by the intermediate nodes such that the request is forwarded to a node closest to the destination. Node joins are handled gracefully with some overhead. Prior nodes in the zone of the newly joining node split their chunk of hash table and assign half of it to the new node. Neighbor information is also obtained similarly. A graceful failure is similar in that the leaving node hands over its share of the hash table to its live neighbors. Crash failures are detected by the absence of periodic refresh messages and neighbors take-over the zone of the crashed node(s). The design is very well organized and concisely presented. Many improvements and optimizations have been suggested in the paper itself. However, a majority of them seem to involve one or another form of replication. For example, using multiple hash functions to map the same point to multiple points and keeping copies of data at all those points. This comes at the cost of additional storage requirement. Also, to reduce lookup latency, the authors propose to send out queries in parallel to all possible copies of the data. Once again, this reduction in latency will come at the cost of increased redundant traffic in the network. It would have been interesting to see some quantifiable results relating the level of replication with these costs. Also since this is a simulation study, experimental studies with real network scenarios are needed for further insights. Finally, the question of security remains open.