From: Jigar Doshi [jdoshi2@uiuc.edu] Sent: Monday, September 13, 2004 10:58 PM To: indy@cs.uiuc.edu Cc: indy@ad.uiuc.edu Subject: 598ig review 09/14 The papers reviewed for this session are FreeNet, Kelips and RON. FreeNet: Brief Summary of the paper: Freenet is a distributed file replication system. The key objective in the design of freenet is anonymity both of publisher as well as viewer. It also incorporates security mechanisms to ensure that the files that are stored cannot be spoofed and are easily available. Towards that objective the authors have designed a completely distributed file system that allows storing, retrieving and managing data, searching. The protocol is also shown to be scalable. Existing work on the same topic have covered some aspects of the problems addressed by freenet. However they have not completely integrated the solution in a secure and distributed form as freenet does. Anonymizers tend to protect consumers rather than producers. Producer anonymizer mechanisms tend to expose the operator of the service itself and are vulnerable to traffic analysis. Freenet on the other hand is completely peer to peer and provides anonymity, security and fault tolerance while being reasonably efficient. One of the key shortcomings of the paper is the fact that though freenet allows efficient storage and retrieval of information. It does not completely address the problem of finding the information. Also the performance analysis is not complete and does not address the question of how much overhead freenet generates per node. The analysis has focused request path length, but not other key factors like latency and network usage. FreeNet could be improved in the following ways. The publishing and retrieval mechanisms used in freenet are nothing but GNUTella type restricted floods. The proposed system can be made more efficient if mechanisms similar to those used in Chord can be applied to FreeNet Especially since both freenet and chord organize info in the form of keys. Search is an open problem in freenet and mechanisms like those in ad hoc network routing can be applied to improve search of information. Also gossiping can be applied to replication (instead of replicating every time, replicate with a probability p) to ensure that the file is not replicated too many times. Key Design issues learnt: •Anonymous access through hashing and random change of ownership. • Lexographic distance based storage and retrieval of information thus improving routing. • Protecting veracity of files through hash collisions. • Use of indirection as an updating mechanism. Kelips: Brief Summary of the paper: Kelips is a distributed hash table that allows the nodes to join and leave silently. It differs from other distributed hash tables in that it sacrifices efficiency of storage to improve the search and retrieval time. In fact search and retrieval can be done in O(1) whereas the storage requirements increases to O(sqrt(n)) from logarithmic bounds used in other p2p systems. Information is kept consistent by a background gossiping protocol. Thus the protocol adds a constant overhead to the system. The key contribution of the paper is that it has explored a new point in the design space of peer to peer systems. Most peer to peer systems today can afford the increased memory overhead as long as it gives efficient search and retrieval times. Such an approach also reduces network congestion especially if a number of nodes are searching concurrently. Faster response rates would make this peer to peer system very user-friendly. One of the key shortcomings of the paper is the fact that replication is left to the application layer. File replication if integrated with the system would be more efficient. Also the problem of replication brings up interesting questions. In Kelips the file is stored based on the hash value. Two versions of the same file will then most probably be stored pretty close to each other. That would negate fault tolerance and also have an impact on replication as a primary goal of replication would be to store the file as far away as possible. Also in the introduction of the paper the authors have spoken about many links in a p2p system having low bandwidth. However in Kelips there is a constant overhead which can be sizeable. Thus dial up and other low bandwidth links may not work well with Kelips. Here the main application is the transfer of files and significant overhead will cause a drop in performance. The authors have addressed the problem with the gossiping probability based on latency. However the amount of information exchanged is not latency/throughput adaptive and actually remains constant. This does not favour low bandwidth links. This work can be improved if replication mechanisms are added in the system itself without relying on the application. Mechanisms to protect security and guarantee anonymity like those used in Freenet would be an ideal addition to the system. Also fault tolerance is not discussed. If one node fails how is the files that were in that neighbor going to be redistributed? Key Design Issue Learnt: •Using gossiping to maintain information veracity •Use of background processing to improve foreground performance. •Trading memory usage for lookup times RON: RON is an overlay network which can be applied over any wide area network substrate like the internet. It improves performance by providing a degree of fault tolerance as well as injecting application specific metrics into routing. RON provides a fast recovery mechanism from path outages and periods of degraded performance by a routing around such sub optimal paths The Key contribution of this paper is the development and demonstration of an overlay based approach to improve internet routing. Routing in the general internet is very generic in order to accommodate the heterogeneity of the underlying network, Also the BGP protocols used today are very slow to converge. Thus using an application layer overlay can fill the voids created by the current internet routing architecture by providing application specific metrics and faster convergence. This approach also naturally provides fault tolerance, while greatly improving performance The paper does have a few shortcomings especially in its modeling of asymmetrical links. Also RON necessitates use of a detailed database which is a considerable investment at each node. Also the system in its current form lacks security which can be added. Key Design Issue Learnt: •Routing can also be applied at the application layer by means of an overlay •Use of an Overlay can improve performance over a WAN by providing a degree of fault tolerance and faster convergence. • Use of application specific metrics in routing has potential to greatly impact performance The common link between these papers are that they all represent distinct points in the design space of peer to peer systems. Kelips improves searching, FreeNet improves security while RON targets resilience. The protocols also seem to use some form of gossiping. Jigar Doshi From: Indranil Gupta [indy@cs.uiuc.edu] Sent: Thursday, September 16, 2004 2:29 PM To: Indranil Gupta Subject: FW: 598ig review 09/14 ---- Original message ---- >Date: Tue, 14 Sep 2004 10:42:26 -0500 >From: >Subject: 598ig review 09/14 >To: indy@ad.uiuc.edu > >Freenet : > >Summary : >Freenet is a P2P system designed address privacy (anonymity for >producers and consumers of file transaction) and avoid central point of >failure(by avoiding storing files at 1 or a few places). >The detail of system design is the following. >File lookup (request) : > request msg (file key, hops-to-live) is sent to one's own node. > when a node receives a request, it checks one's own datastore, if not >found, > forward the request to nearest key in the routing table. > If the forwarded request successfully returned, cache the data, >populate the routing > table with (filekey, source). later, similar key request is sent to >the source. > If the forwarded request fails, try next nodes in the routing table >and on. > If the routing table is depleted, report the failure. >With this mechanism, Quality of routing improve over time, in >self-reinforcing manner. >Because node come to specialize in locating sets of similar keys, >storing clusters of files with similar keys. And popular data get >replicated more and closer to the requestors. > >Store file : > request (key, hops-to-live) : the same as file lookup > all clear (failure of query) : file is sent and stored in each node >along the query path. > also each node stores in its routing table (inserter, file key) > : insertion also results in file cluster with similar keys > insertion replacing existence announcement > false-file insertion calusing spread the original file further >(Aha!) Join : > new node gets a few nodes in out-of-band manner. > new node knows other nodes : by request > other nodes knows new node : new node announcement > conflicting goal : for efficient routing, want to associate the >node with one key, > but letting the new node pick its own key is >vulnerable in security. > remedy : a new node (hash of random key, ttl) : all nodes in the >path generates random seed, > XOR with the hash ===> consistent random key. > >Comments : > #. file lookup and store process is used to generate and enrich the >network in > the self-reinforcing manner. Interesting design. > [Q] : In order for the system to perform reasonably, short >path-length is critical. > They show that their pathlength converges to 6. But this is only >after a long > time period without churn. How would the system work in more >realistic case? > [Q] : Empirically, Freenet seems to be a small world (scale-free >power-law network). > Intuitive explanation of mechanism why it is a small world? For >example, such > explanation exists for WWW. > [Q] : the network load by storing data cache at all nodes along the >pathlength? > [Q] : what are the actual P2P systems that use Freenet? > [Q] : what is the usual mechanism of publishing the file description >string? > For example, in the context of mp3 file sharing p2p? > [Q] : no rigorous guarantee of permanent file storage. >How does it actually work? > [Q] : In a new node announcing its existence, the paper says that for >efficient routing, > all other nodes want to have the same key for the new node. But, >why is this necessary? > anyway this key is not actually associated with a specific file, >and a node can be known > with multiple keys as time goes on... > [Q] : If a node with a certain file is not free to choose the file >key, thus, the description string, > (for example, it is already used, it is used in a new node >announcement), how could this be used > in mp3 file sharing system search? > [Q] : any formal proof of how pathlength is associated with network >size, etc? > > > >RON : >summary : >Internet consists of independent autonomous network systems >that peer. Protocols such >as BGP-4 that connect ASs use aggregation(no detail on the >internal of each AS) and damping >for scalability. But this hurts fault-tolerance. Then, how >do we achieve fault-tolerance >for applications interspersed over wide-area internet? >They solve this problem by forming an application-specific >overlay network called RON. >The most important design idea is to separate the >scalability and fault-tolerance (the >two conflicting goals), by letting the underlying network to >take care of scalability >and taking care of fast fault-identification and recovery at >application overlay level. >The actual design of RON is not much new. RON nodes form >complete graph, use link-state >routing. With a small number of nodes (16 in the >experiment), they can perform aggressive >fault detection and recovery. It can let applications to >specify the criterion for >network optimization (latency, loss-rate, throughput...). > >comment : >#. The idea of achieving scalability and fault-tolerance >which are normally conflicting, > by separating the implementation of the two in the >separate network layer is good. >[Q] : what problem is caused if it becomes popular? >(network load : ...) >[Q] : how does it scale? > > >Kelips : > >Summary : > >Kelips is a P2P system that achieves faster file look-up >time and more stability to >failures and churn, at the cost of increased memory usage >and constant background >communication overhead. >Specifically, it achieves lookup time O(1), at the cost of >memory usage of square >root N. This can be compared to other DHT P2P systems >(Chord, Pastry) that ensures >log(n) for lookup and memory usage. >The following is how the system works. >The system hashes node to k affinity groups. >Each node maintains group view (entry for all nodes within >the group), constant # of > contacts for all other groups. filetupes for all files >stored in the group. >This requires square root n storage, when k is optimized. >This information is maintained through gossip-style >information dissemination which >has logarithmic latency. In addition, bandwidth is limited >to constant per node. >lookup is done by hashing the file to group number, sending >a lookup request to a member >of the group, and the contact returining the filetuple info >for the lookup. >insertion is done by hashing the file to group number, >sending an insert request to a >member of the group, the contact picking up a random node in >the group as the storer. >Because latency of gossip protocol and bandwidth limit >results in incomplete soft state >maintenance, the above lookup and insertion can fail, in >that case multi-hop reroute >is used to ensure that the operation is done. > >Comments : >[Q] : This system has O(1) for lookup and square root N for >storage, while other > DHT P2P has N logarithm for lookup and storage. Is there >some application scenario > where this system serves better than other P2P? >[Q] : The experiment shows the various metrics of how the >system performs. > But, as mentioned, the original specification of what >should be stored per each > node cannot be met always, due to latency of gossip >protocol and bandwidth limit, > not guaranteeing the constant lookup time. > Could the experiment be done to show this lower-level >information of system performance > (how the group view, contact, filetuples are maintained >over churn and bandwidth limit...)? From: Adeep Singh Cheema Sent: Tuesday, September 14, 2004 12:48 PM To: Indranil Gupta; adeep.cheema@gmail.com Subject: 598ig review 09/14 09.14.2005 Cheema,Adeep S Overlays and DHT's cheema@uiuc.edu Resilient Overlay Networks Overlay based routing machinery RON’s exist above an existing Internet routing layer. They provide a quick recovery after any degradation in performance is detected. They use an alternative routing protocol to reconnect nodes once an outage, i.e. an Autonomous System failure is detected provided that some physical redundancy exists. Routing around failures takes at most one hop through aggressive probing of nodes without excessive bandwidth overhead in a matter of seconds rather than minutes. Ancillary design goals of RON include routing in accordance with specific applications for set purposes such as for an ISP and providing a basic framework for implementing specialized routing policies. Virtually linked RON nodes form a completely connected overlay to cooperatively route packets for each other while monitoring the state of the Internet paths connecting it to other nodes in terms of several metrics. Packets are tagged at entry nodes and propagated at intermediate nodes based on such tags to exercise network flow. Forwarding tables are constructed at each node and contain routing information. Criticism: Packet delivery is best effort and unreliable. Each RON node has links to every other node. This is not scalable to a large number of nodes specially since several metrics must be maintained and updated with regard to each node. Not enough data on performance. It is debatable if the additional robustness achieved should be picked over the costs of deploying a RON with its memory / CPU / bandwidth requirements. It is not clear if a RON improves outage detection and routing for an AS which does not have any nodes in common with the RON. Freenet Freenet is a P2P system / DHT that strives to achieve anonymity and privacy for participating nodes and decentralization in exchange for increased network overhead from replication. It supports standard DHT operations such as queries, storage and retrieval of files although in this case files are named with location independent keys. It is designed to perform like a cooperative distributed filesystem with guarantees of privacy. Nodes in Freenet maintain limited neighbor information and comprehensive information of their own datastores. Hop bound searches are routed in a chain of proxies with propagation based on local rather than global knowledge for privacy. A series of hashing keys are used to name files, user namespaces as well as for updating/splitting purposes. Keys are used in queries to determine the most likely store for the requested file. The paper claims that the algorithm should improve the quality of routing with an increased number of queries as it specializes for a set of keys. There is no data supporting this fact and the assumption that similar queries will appear together is unrealistic. The Freenet design also imposes files on nodes (transparent replication) based entirely on their keys. Collisions on insert attempts results in an increase in the number of genuine copies of the file. Criticism: No guarantees on file lifetimes. Proxy based search is essentially DFS based on local knowledge and may not be optimal. Anonymity is not always guaranteed for the receiver, as key anonymity is not possible. Kelips Kelips is a DHT system that sacrifices memory and increased bandwidth usage for greater stability and reduced file lookup times. File lookups are O(1) time and complexity and membership protocols are streamlined. Kelips requires a O(sqrt N) space requirement per node to realize constant lookups. The entire set of nodes in the system is divided into sqrt(N) subgroups and each node keeps track of sqrt(N) nodes in its group as well as a constant number of nodes in the other sqrt(N) groups leading to the O(sqrt N) space requirement for neighbor information. The memory requirement from filetuple storage is the same assuming that O(N) files are stored within the system. Records are maintained using a heartbeating protocol with gossip style communication, which can contain a limited number of records. Lookups are performed by hashing filenames to an affinity group and querying a node in that group in O(1) time. Insertion follows the same protocol and complexity. Criticism: Maintaining O(sqrt N) information about affinity set and external neighbors seems like a very intensive process with heartbeating + gossiping. From: Boris Capitanu Sent: Tuesday, September 14, 2004 11:03 AM To: Indranil Gupta Subject: 598ig review 09/14 Resilient Overlay Networks (RONs) --------------------------------- This paper presents a new routing mechanism designed to allow distributed Internet applications to achieve improved network connectivity and efficiency even in the face of failures or attack. RON exploits the limitations of the BGP-4 protocol to create an overlay network that is dynamically adaptable and resilient to failures. Using aggressive probing and monitoring, RON is able to detect outages in the underlying infrastructure and route packets around those outages. RON nodes maintain and exchange information about the quality of network paths which help them build internal forwarding tables based on a variety of path metrics, such as latency, packet loss rate, and available throughput. RON also provides flexibility to distributed applications by allowing them to specify their own network requirements. Another important achievement of RON is that it provides a framework for the implementation of routing policies that determine the choice of paths in the network. The authors identify two types of failures: link failures and path failures which influence the maintenance of the routing table entries at each RON node. As a result of having a multitude of nodes deployed in different Internet routing domains, their test proved that RON was able to route around between 60% and 100% of all significant outages. In their implementation RON was able to achieve an 18 second time average for detecting and routing around a failure, much better than the minute-scale achieved by BGP-4. Advantages: resilience to failures, improved QoS, meeting application demands Disadvantages: control overhead, may not be economically feasible for some ISPs that have very reliable connections since the traffic patterns might drastically change and "overload" their network. Kelips: Building an Efficient and Stable P2P DHT Through Increased Memory and Background Overhead ---------------------------------------------------------------------------- --------------------- Kelips tests a new design for a P2P DHT that tries to reduce file lookup times and increase stability to failures and churn. This is achieved by using a P2P gossip mechanism to partially replicate file index information, and allows a trade-off between lookup speed and memory or communication overhead. Nodes in a Kelips system are organized in k virtual affinity groups, with each node being mapped to a particular group by using a consistent hash function that maps the node's identifier (IP and port) to one of the groups. Each node maintains a soft state that includes: the Affinity Group View (information about round-trip time estimates, heartbeat count of other nodes in the same group), Contacts (a table of a constant set of nodes in a foreign affinity group) and Filetuples (partial set of tuples detailing the homenode's information). Lookup is done by mapping the requested file name to one of the affinity groups by using the same consistent hashing technique, after which a lookup request is sent to the topologically closest contact among those present in the node's tables. The node receiving the lookup request performs a search among the filetuples it stores and returns the address of the homenode to the requestor who at that point can retrieve the file directly from its source. Insertions are performed in a similar manner, the difference being that the contact node chooses a random node from its affinity group to forward the insert request to. Lookups and insertions occur with O(1) time and message complexity. The experimental results show that indeed lookups and insertions are very fast, while the memory requirements are relatively small. The system also achieves good Load balancing and fault-tolerance. Advantages: fast lookups and insertion, good load balancing, fault-tolerance; decent memory requirements Disadvantages: the system might not scale too well to millions of nodes, security is not discussed, what happens if nodes change their IP frequently (as it happens frequently with Cable or DSL internet, wireless networks...etc) Freenet: A distributed Anonymous Information Storage and Retrieval System ------------------------------------------------------------------------- Freenet is a decentralized, censorship-resistant, peer-to-peer distributed data store that exploits the hard drive free space in much the same way as distributed.net exploits free CPU cycles. The main advantage of Freenet is that it allows users to anonymously publish or retrieve various kinds of information. The system has no central servers and is not subject to the control of any one individual or organization. Even the designers of Freenet do not have any control over the overall system. The system is designed so that information stored in the system is encrypted and replicated across a large number of continuously-changing anonymized computers around the world. It is extremely difficult for an attacker to find out which participants are hosting a given file, since the contents of each file are encrypted, and can also be broken into sections that are distributed over many different computers. Even the participants themselves don't know what they are storing. Each node in the Freenet system maintains a data store containing documents associated with keys, and a routing table associating nodes with records of their performance in retrieving different keys. To find a document in the network given a key, a user sends a message to a node (probably one running on the same machine as the client program) requesting the document, providing it with the key. If the document is not found in the local datastore, the node then finds the node in its routing table that it thinks will be able to locate the key most quickly, and forwards the request to that node, remembering that it has done so. Their test system proves to be extremely scalable and adapts continuously to changes. From: Yookyung Jo Sent: Tuesday, September 14, 2004 10:42 AM To: Indranil Gupta Subject: 598ig review 09/14 Freenet : Summary : Freenet is a P2P system designed address privacy (anonymity for producers and consumers of file transaction) and avoid central point of failure(by avoiding storing files at 1 or a few places). The detail of system design is the following. File lookup (request) : request msg (file key, hops-to-live) is sent to one's own node. when a node receives a request, it checks one's own datastore, if not found, forward the request to nearest key in the routing table. If the forwarded request successfully returned, cache the data, populate the routing table with (filekey, source). later, similar key request is sent to the source. If the forwarded request fails, try next nodes in the routing table and on. If the routing table is depleted, report the failure. With this mechanism, Quality of routing improve over time, in self-reinforcing manner. Because node come to specialize in locating sets of similar keys, storing clusters of files with similar keys. And popular data get replicated more and closer to the requestors. Store file : request (key, hops-to-live) : the same as file lookup all clear (failure of query) : file is sent and stored in each node along the query path. also each node stores in its routing table (inserter, file key) : insertion also results in file cluster with similar keys insertion replacing existence announcement false-file insertion calusing spread the original file further (Aha!) Join : new node gets a few nodes in out-of-band manner. new node knows other nodes : by request other nodes knows new node : new node announcement conflicting goal : for efficient routing, want to associate the node with one key, but letting the new node pick its own key is vulnerable in security. remedy : a new node (hash of random key, ttl) : all nodes in the path generates random seed, XOR with the hash ===> consistent random key. Comments : #. file lookup and store process is used to generate and enrich the network in the self-reinforcing manner. Interesting design. [Q] : In order for the system to perform reasonably, short path-length is critical. They show that their pathlength converges to 6. But this is only after a long time period without churn. How would the system work in more realistic case? [Q] : Empirically, Freenet seems to be a small world (scale-free power-law network). Intuitive explanation of mechanism why it is a small world? For example, such explanation exists for WWW. [Q] : the network load by storing data cache at all nodes along the pathlength? [Q] : what are the actual P2P systems that use Freenet? [Q] : what is the usual mechanism of publishing the file description string? For example, in the context of mp3 file sharing p2p? [Q] : no rigorous guarantee of permanent file storage. How does it actually work? [Q] : In a new node announcing its existence, the paper says that for efficient routing, all other nodes want to have the same key for the new node. But, why is this necessary? anyway this key is not actually associated with a specific file, and a node can be known with multiple keys as time goes on... [Q] : If a node with a certain file is not free to choose the file key, thus, the description string, (for example, it is already used, it is used in a new node announcement), how could this be used in mp3 file sharing system search? [Q] : any formal proof of how pathlength is associated with network size, etc? RON : summary : Internet consists of independent autonomous network systems that peer. Protocols such as BGP-4 that connect ASs use aggregation(no detail on the internal of each AS) and damping for scalability. But this hurts fault-tolerance. Then, how do we achieve fault-tolerance for applications interspersed over wide-area internet? They solve this problem by forming an application-specific overlay network called RON. The most important design idea is to separate the scalability and fault-tolerance (the two conflicting goals), by letting the underlying network to take care of scalability and taking care of fast fault-identification and recovery at application overlay level. The actual design of RON is not much new. RON nodes form complete graph, use link-state routing. With a small number of nodes (16 in the experiment), they can perform aggressive fault detection and recovery. It can let applications to specify the criterion for network optimization (latency, loss-rate, throughput...). comment : #. The idea of achieving scalability and fault-tolerance which are normally conflicting, by separating the implementation of the two in the separate network layer is good. [Q] : what problem is caused if it becomes popular? (network load : ...) [Q] : how does it scale? Kelips : Summary : Kelips is a P2P system that achieves faster file look-up time and more stability to failures and churn, at the cost of increased memory usage and constant background communication overhead. Specifically, it achieves lookup time O(1), at the cost of memory usage of square root N. This can be compared to other DHT P2P systems (Chord, Pastry) that ensures log(n) for lookup and memory usage. The following is how the system works. The system hashes node to k affinity groups. Each node maintains group view (entry for all nodes within the group), constant # of contacts for all other groups. filetupes for all files stored in the group. This requires square root n storage, when k is optimized. This information is maintained through gossip-style information dissemination which has logarithmic latency. In addition, bandwidth is limited to constant per node. lookup is done by hashing the file to group number, sending a lookup request to a member of the group, and the contact returining the filetuple info for the lookup. insertion is done by hashing the file to group number, sending an insert request to a member of the group, the contact picking up a random node in the group as the storer. Because latency of gossip protocol and bandwidth limit results in incomplete soft state maintenance, the above lookup and insertion can fail, in that case multi-hop reroute is used to ensure that the operation is done. Comments : [Q] : This system has O(1) for lookup and square root N for storage, while other DHT P2P has N logarithm for lookup and storage. Is there some application scenario where this system serves better than other P2P? [Q] : The experiment shows the various metrics of how the system performs. But, as mentioned, the original specification of what should be stored per each node cannot be met always, due to latency of gossip protocol and bandwidth limit, not guaranteeing the constant lookup time. Could the experiment be done to show this lower-level information of system performance (how the group view, contact, filetuples are maintained over churn and bandwidth limit...)? From: Thadpong Pongthawornkamol [tpongth2@uiuc.edu] Sent: Tuesday, September 14, 2004 10:35 AM To: indy@cs.uiuc.edu Cc: tpongth2@uiuc.edu Subject: 598ig review 09/14 Overlay Networks & DHT Overlay Networks are high-level networks that exist on the top of other underlying low-level networks. The purposes of overlay networks are mostly to provide application-specific capabilities which are hardly found in low-level network infrastructure. One of widely known application derived from Overlay Networks is Distributed Hash Table (DHT), which matches arbitrary keys onto corresponding logical nodes in a network. Here we present reviews of three works on overlay networks, which two of them are implementation of DHTs. Resilient Overlay Networks Resilient Overlay Networks (RONs) , proposed by Andersen et al., present an attempt to increase network’s reliability and fault-tolerance by providing a routing mechanism over an overlay network that can quickly detect and recover extreme failures, which can significantly degrade traditional network systems such as Internet and BGP-based network. Moreover, RON is aimed to provide capabilities of routing and path-selection in application level, which enables users to select the best routing policy to suit their applications. Another goal of RON is to optimize package-specific transmissions by categorizing packages into different types and apply appropriate policy to each type. RON invokes its own mechanism to evaluate traffic in the network in dynamic way: each RON router observes its local network’s characteristics, such as bandwidth, latency, and loss rate. Such observations can be done by active and passive probes. Then, every RON node periodically exchanges its local information to all members and constructs a routing table based on such information. Because main purpose of RON is to enable reliable application-specific routing, any routes occurred in RON will be chosen by considering user-specified criteria. For example, users can modify factors which indicate the availability of a link (good or bad), or freely define “goodness” value to each path. Thus introduces application-flexibility to routing policies. According to the paper, each node in N-node RON maintains N-1 link information in its routing table. Every period of time, each node checks all links maintained in its table in order to detect any failures occurred. Once a link failures is detected, RON will automatically switch routing to another available paths for only small convergence time, which is yielded to be much shorter than one achieved by BGP protocol. According to the simulated results comparing between RON and traditional Internet system, RON impose more traffic overhead than Internet when the system is in the normal stage, but RON exhibits its superiority over Internet in case of system failures. RON can retain system’s stability better than Internet in most link outages. This means RON produce a tradeoff between throughput and reliability. However, an important drawback found in RON is scalability problem. RON seems to exhibit some similar characteristics to intra-domain routing protocol, such as RIP because it responds quickly to topology changes and results in much less convergence time than BGP. As a trade off, the need for each node to store routing information of all neighbors in N-node RON incur O(n2) space overhead to each node. Thus limits the usage of RON to be applicable for only a small network. Moreover, Giving users the right to specify their own policies may introduce system performance problems if users do not choose appropriate and feasible policies. Freenet: A Distributed Anonymous Information Storage and Retrieval System Freenet [Clarke et al.] is an implementation of DHT overlay network that focuses on user privacy and anonymity. Generally speaking, it provides location-independent DHT which publisher’s and consumer’s identities are difficult to identify. Its capabilities of data replication and data encryption make malicious attempts to destroy or modify data content impossible to achieve. All Freenet mechanisms are done in decentralized manners, which will not introduce scalability and availability problems due to single point of failure. Each node in Freenet is viewed as a data store, which data are stored from local user or another Freenet node. Each data is associated with a public key, which is used from any consumers to find the data. Similar to IP protocol, requests and replies for messages are sent between hops of nodes. Each intermediate to independently make route decisions based on its local routing table. In order to reduce traffic overhead, and to improve system availability, If requested data is found, it will be returned upstream to the requestor with replications done at each intermediate nodes consisting the search path. Freenet supports the following functions: Keys searching, Retrieving data, Storing data, Updating data. All of these operations use a key associated with data to route messages. A Freenet node will try to route messages with similar keys to similar location to ensure that system performance will be improved over time. The concept of key is implemented in Freenet to guarantee privacy and security. There are three data key schemes in Freenet. The first one is keyword-signed key(KSK), which will generate a key from a short descriptive string of data. This scheme introduce flat namespace problem, which is addressed by the second scheme, signed-subspace key(SSK), which generates a key from short descriptive string of data and user-specified namespace. Such scheme allow users to store hierarchy structures such as directories or folders. The final key scheme is content-hash key(CHK), which generate a key for updating and splitting data. Such scheme can be used with the first or the second scheme. Another mechanism to guarantee privacy is that during the data route, each node in that routing path can change information, such as source of data or hope-to-live value, before it sends data upstream. The purpose of this mechanism is to make it hard to track the source of arbitrary data. However, Freenet cannot completely deal with all privacy and security problem. Key anonymity is a consideration which cannot be totally solved in basic Freenet. With the use of pre-routing scheme, such problem can be solved at a certain level. Another concern is a reaction of a Freenet system to denial-of-service attacks. By using computation payment and two-phase datastore, Such problem can be alleviated. Moreover, the paper doesn’t mention any mechanisms for publisher to delete the data from the system. This operation is probably achieved by using updating mechanism. According to the evaluation result, Freenet system still cannot perform well in scalability aspect, which gossiping may be introduced on some operations to gain more scalability. Kelips Kelips, proposed by Gupta et al, presents another DHT scheme which try to optimize lookup cost at O(1) times by trading off continuous background overhead. All nodes in Kelips are divided into k affinity groups using uniform hash function. Nodes in each affinity groups maintain information about all group members, some entry nodes to foreign groups, and pointer to homenodes containing files, which are hashed by the same method as membership management . Each Kelips node maintains O(n1/2) storage overhead for membership and data index. File requests and file insertions can be done within two hops, first hop for foreign resolve and second hop for local resolve. By using gossip algorithm to maintain information. Kelips scales well and tends to work under churns and system failures. In conclusion, Kelips provides DHT features at acceptable costs in time and space by trading off small fractions of bandwidth for epidemic dissemination. However, the paper doesn’t address considerations about privacy and security, which are probably discussed in future works. From: Vartika Bhandari [vbhandar@uiuc.edu] Sent: Tuesday, September 14, 2004 10:24 AM To: indy@cs.uiuc.edu Subject: 598ig review 09/14 Resilient Overlay Networks This paper describes an application-level overlay architecture that is aimed at enhanced routing through quicker response to topology changes (route outages) and the ability to easily incorporate user-defined policies and metrics. The core idea is to have RON nodes residing in various domains of interest. These RON nodes maintain connectivity information regarding the entire RON graph via periodic control traffic. When data is to be routed, the RONs can use relevant metrics to determine whether it is better to use the default Internet route, or divert the traffic over RON links. Since RON connectivity information is fairly reliable, converges fast and often includes links not otherwise publicly announced (private peering), RON routing can circumlocute failed routes and maintain good end-user experience. Bootstrapping of a RON may be done either statically or dynamically via the new-comer contacting some well-known peer. To avoid erroneous interpretation of member-withdrawals as outages and vice-versa, RON peers periodically exchange peer-lists. The system has been implemented as a set of C++ libraries. It is targetted to specific applications e.g. multi-site conferencing, as well as to enhance reliability of IP forwarding. The evaluation has been done on an actual wide-area RON deployment, and indicates substantial improvement. RON does seem to be potentially useful for applications involving a moderate number of sites that might wish to use custom-routing for greater reliability. However, there seems to be an issue with scalability (the authors say that the design scales to around 50 nodes). Perhaps the scalability issue might be addressable by imposing a hierarchy on RON. Kelips This paper presents an interesting trade-off between storage requirements and lookup costs. While a number of P2P systems have aimed at O(log n) space complexity with O(log n) lookup time, Kelips allows for O(sqrt (n)) space but reduces lookup latency to O(1). It is therefore a suitable design for systems which are more delay-sensitive and which are medium-sized (so that sqrt(n) is not very large). Kelips has a notion of "affinity groups". Each node is member of one group (determined via consistent hashing). Given population size n, and k groups, each group has cardinality n/k with high probability. Nodes keep information of peers in same group as well as a list of contacts spanning all other groups. File-tuples are also maintained for files homed in one's group. A gossip protocol is employed to propagate updates. Query re-routing enables searches to succeed despite imperfect contact-set and file-tuple information at some nodes. Kelips exposes an interesting point of trade-off wherein constant-time lookup is achievable with sub-linear (albeit super-logarithmic) storage requirements. Freenet This paper describes a P2P system that allows for anonymous distributed storage and retrieval of files. The design attempts to address concerns about anonymity of both producers and consumers of data, as well as avoiding legal liability for storage nodes. Freenet is completely decentralized and each file is replicated at several peers with no notion of "permanent" location. A notion akin to "tropism" has been used, wherein files tend to move towards zones of high interest and away from low-interest zones. When a file is requested, the search propagates in a DFS-like manner, backtracking whenever needed, till either it is located, or the search fails. If the request succeeds, each node along on successful return path, also stores a copy of the file, thereby making the file more readily available for future accesses from that zone. In fact, this seems reminiscent of path-compression in disjoint-set data structures, where nodes on the path traversed during a find-set operation, are linked directly to the root, to ensure O(1) time for future find-sets on any of these. Thus there seems to be an implicit notion of amortization in the Freenet design. File identification is achieved by using file keys which are 160-bit SHA hashes. Keys may be of KSK, SSK and CHK type. Of these SSK also serves the purpose of creating multiple namespaces. SSK and CHK are often used in conjunction to create levels of indirection. A really interesting aspect of Freenet is how the design copes with junk file insertions. Since a collision detection also results in replication of the original file, junk inserts cannot wipe out genuine copies from the network. This provides for an autonomous protection mechanism. Freenet also uses a notion of "pre-routing" to enhance anonymity. The simulation results reported seem to have good scalability characteristics. The paper also mentions a test deployment, but does not provide details. From: emchan@uiuc.edu Sent: Tuesday, September 14, 2004 10:03 AM To: indy@cs.uiuc.edu Subject: 598ig Review 09/14 Resilient Overlay Networks: Resilient Overlay Networks provides an application layer overlay to the underlying Internet topology. Through this approach, they hope to better tailor the routing algorithms for applications with different loss rate and bandwidth requirements. RON improves on tradeoffs in the Border Gateway Protocol, whose myopic view largely ignores topology in the interest of scalability. Even though BGP can recover from failures, its tendency to damp route changes in favor of stability can cause it to take several minutes to find an alternate route. This conservative behavior can cause timeouts on TCP connections. Simultaneously, in the interest of stable routes, BGP prefers faulty routes that have not failed yet. RON improves on BGP by keeping a tighter integration with applications through its binding as a library. RON allows the expression of complex routing policies and includes active link monitoring, which is not available in BGP. Through RON, network traffic takes the best route as determined by a continuously updated database maintained by RON. RON records three metrics per host: latency, packet loss, and throughput. RON seems to work well for small virtual overlays, but its constant link monitoring causes extra traffic to be generated. In the presence of multiple large RON networks, the system can cause significant overhead on the underlying hardware, causing problems of scale. RON also raises some security concerns, since traffic may be forwarded to personal machines in order to optimally route. This violates end-to-end principles, and may lead to a new class of data snooping. In addition, RON lacks firewall compatibility. Two hosts behind NAT may be unable to communicate at all. Kelips: Kelips was designed to be resilient to P2P churn. To combat this problem, Kelips uses distributed hash tables, which minimize work per node join and exit. Kelips divides the set of all connected nodes into affinity groups, which are based off consistent hashing. Kelips uses node soft state to eliminate key redistribution at the cost of extra memory. Kelips’s loose model for clients helps it resist the need to churn upon client view change. Kelips uses gossiping to propagate locality information. The design principle of Kelips is to reduce unnecessary chatting among nodes. This is done by ensuring that gossip only lasts for several rounds, which multicasts to a constant number of nodes. Kelips’s analogue to Gnutella’s supernode system is the DHT. Propagation of file tuples may be slow in Kelips, the homenode structure results in a centralized source. Heartbeat updates ensure file freshness, but come at the cost of bandwidth. The conservative gossiping approach in conjunction with unreliable UDP packet loss may lead to overlocalization. Kelips does not preserve anonymity, nor does it replicate files. Kelips requires moderately high storage overhead in comparison to other DHTs; constant propagation in rounds doesn’t churn, but also doesn’t gossip sufficiently. Simple design might help Kelips in other ways. Freenet: Freenet attempts to provide anonymity, security, and plausible deniability for storage and transmission of information. It does so by encrypting files, hashing their names, and routing them through a privacy-preserving protocol. Along with these properties, Freenet attempts to self tuning policies that both improve system performance with increased use and thwart outsiders from flooding the network through dumping useless files and replacing existing files. I really enjoyed how the authors addressed security in Freenet. It seems to be a very well thought out system. When attackers try to replace files, they actually help propagate them. File accesses tend to help replicate through “caching”, which differs from systems like Gnutella or Napster, because nodes that help propagate also store a copy. Hops to live isn’t deterministic, it’s probabilistic, which allows the system to be resistant to manipulation of this value by corrupt hosts. However, corrupting this value would still severely cripple the network, which depends on the propagated queries to discover peers and replicate information. Even with all the benefits, I can see several problems with the design. First, it is difficult to locate the hashed keys without placing them on a central authority; this breaks down into the centralization problem again. Given a key, if you are not close enough to a node that has the information, you may never find it, since the hops to live count isn’t sufficiently large. The entire proxying architecture makes it slow, and searches/inserts are localized. Inserts and searches are highly localized based on the hops to live, which can cause virtual partitioning of the network. Although unlikely, it is possible that there will be two identical hashes inserted in different virtual partitions. There is no concept of a file lifetime, which would seem odd if it were the case in Gnutella. Adversarial conditions include flooding the network with many legitimate useless files and requesting those files from nodes that are logically far, causing many useless replications. We can also modify hops to live to reduce network efficiency, lowering the overall propagation distance of messages, and nodes can lie about what file they have and return corrupted copies, although the search algorithms require n responses, which can be used to counteract this tactic. Commonalities for improvement: All three of the systems do little to prevent the freeloader problem, nodes that contribute very little to the network, but have high consumption costs. It would be interesting to see economic models applied to routing and data storage/ swapping. Simultaneously, the lack of centralization and authorities can result in man in the middle for both Freenet and RON. Kelip’s DHT somewhat avoids the problem, since the hash reveals the host down to the affinity group level. From: pchen14@uiuc.edu Sent: Tuesday, September 14, 2004 9:15 AM To: indy@cs.uiuc.edu Subject: 598ig review 09/14 -Freenet Freenet is a peer-to-peer network application that performs distributed information storage and retrieval and meanwhile protects the anonymity of users. Files shared in Freenet are identified by binary file keys obtained by applying a hash function. Each node maintains its own local datastore and a dynamic routing table. Each entry in the routing table associates a file key with the actual data source. When retrieving a file, every node along the routing path will have a copy of the same file. And a request is always routed to a node with the nearest key in the routing table to the key requested. This request mechanism causes popular files to be transparently replicated and achieves key closeness which makes the quality of the routing improve over time. For managing data, Freenet does not guarantee permanent file storage due to finite storage capacity. That allows old and rarely sued file eventually die out. Based on the basic Freenet, adding mix-style “pre-routing” of messages can achieve key anonymity and stronger sender anonymity. Other security issues are also discussed. The routing table contains two fields 1.File key 2.Actual file source. The second field in most of time seems is useless, because as long as a node’s storage capacity is still enough to hold all the files it has seen so far, it will not need to check this field for any query request. Moreover, once a source node fails or leaves, those “Actual file source” pointed to this non-existing node will have no usage any more. One more concern about this field in routing tables is that it clearly points out which node is the one that inserts a specific file into the network. That violates the desire of privacy. However, this can be solved by the occasional resetting of the actual file source field in replies. -Kelips This paper describes a peer-to-peer distributed hash table system which provides O(1) time and complexity for file lookups by increasing memory usage and constant background communication overheads. -Resilient Overlay Networks Today's Internet is vulnerable to router and link faults, configuration errors and malice. A Resilient Overlay Network (RON) is an architecture on top of the exiting Internet to speedup the failure detection and recovery from path outages and periods of degraded performance. Several RON nodes are deployed widely across the Internet. Each of them periodically monitors the quality and state of the underlying links among themselves, and uses this information to build routing tables of this RON. Secondly, RON makes routing and path selection have tighter integration with applications. This is achieved by evaluating three specific metrics for each virtual link: 1.latency 2.packet loss 3.throughtput. Thirdly, RON provides a framework for the achieving policy routing. The creative part of this work is that by observing the tradeoff in BGP-4 between scalability and speed of fault detection and recovery, it deals the two concerns in two different places to avoid the tradeoff. From: Michael Treaster [treaster@cs.uiuc.edu] Sent: Tuesday, September 14, 2004 8:38 AM To: Indranil Gupta Subject: 598ig review 09/14 Kelips Kelips is a peer-to-peer distributed hash table system. It differentiates itself from other systems matching this description by making a different decision in the resources/performance tradeoff. Kelips uses O(sqrt(2)) memory and requires increased background communication to maintain the system, but this allows it to provide O(1) file lookup time and increase the stability of the system in the event of node failures or churn. The paper does an excellent job presenting Kelips as a technically sound peer-to-peer system. Adequate detail of the system is provided for the reader to understand what interesting decisions were made when the protocol was designed and why those decisions are important. Experimental data shows that the theoretical performance matches that actual performance of the implemented system. The paper is less compelling with regard to motivation. There are many peer-to-peer implementations in existence already. Although the paper describes how Kelips differs from these systems in terms of theoretical performance, it would be valuable to the paper if the authors had mentioned applications that Kelips supports that other systems are infeasible for. Alternatively, experimental performance data comparing Kelips to other peer-to-peer systems would be enlightening to the reader, dramatically (hopefully) showing why other systems are impractical in certain aspects. It could be interesting to build a peer-to-peer application on Kelips and on a competing peer-to-peer infrastructure and compare the performance directly. A careful choice of application could dramatically highlight the advantages of O(1) file lookup. Freenet Freenet is a peer-to-peer file sharing system. It emphasizes the anonymity of publishers and consumers of content over all other design considerations. The unguided replication of files across the network serves to conceal the originator of files. A public key cryptographic system helps protect publishers further, and also conceals the identity of requesters of files. The protocol is designed to encourage the propagation of popular files to a large number of nodes, and to encourage clustering of similar files in close proximity on the network. These are emergent properties of the lazy replication scheme, which simply duplicates a requested file on all nodes forwarding the request. Although it is not highlighted as a primary contribution of the paper, it is likely that this algorithm is more widely applicable to other applications. Resilient Overlay Networks A resilient overlay network (RON) is a routing infrastructure for the Internet that functions at the application layer rather than as a low-level protocol. It aims to quickly reroute network traffic when a link or node fails or experiences unusually high latency. While the standard BGP protocol can require many minutes to converge to a new route when an existing route fails, RON attempts to reroute traffic in less than 20 seconds. Additionally, RON allows applications to specify which metrics to optimize for when choosing a route, such that applications with different performance requirements can use routes chosen with those considerations in mind. This paper is to be commended for honestly and openly presenting the shortcomings of the system. Unfortunately, some of the shortcomings are fairly severe. NATs, scalability problems, and the reliance on social trust rather than enforced trust all inhibit widespread adoption of the system. Additionally, once the system is widely adopted its value is reduced due to widespread use of the best network links. Although the experimental analysis is a valuable inclusion to the paper, the presentation of data is sometimes poor. In particular, Figures 3 and 4 in the paper have no indication of how much better the RON-managed communication is than the no-RON communication. It only shows that RON is better, but the margin of improvement could be very small. The authors provide anecdotal evidence that RON provides a large improvement over other routing methods. It is unfortunate that they were unable to more effectively demonstrate this with experimental data. From: Dennis Y Chi Sent: Tuesday, September 14, 2004 3:06 AM To: Indranil Gupta Subject: 598ig review 09/14 Dennis Chi 9/14/04 Overlays and DHTs Computer networks are continually becoming faster, more complex, more accessible and more widespread, so applications using these networks must be able to deal with these issues. Therefore, the importance of overlay networks is increasing because overlay networks allow the application users to form their own virtual networks on top of the existing physical topology. Content-distribution networks, peer-to-peer (p2p) systems, and distributed hash tables (DHTs) are all examples of applications that utilize overlay networks. The Resilient Overlay Network (RON) is basically a distributed application architecture that improves upon the performance of the Border Gateway Protocol (BGP). One of the ways RON achieves this is by allowing nodes to detect and recover from failures in the underlying network. RON routers use a probing technique to detect path failures and use a link-state routing protocol to gather measurement data and maintain routing tables and performance databases. Therefore, RONs can implement expressive policy routing by making routing decisions based on various performance metrics, including latency, loss and throughput. Expressive policy routing allows applications to have more control over the paths of their packets because they can classify packet flows based on their preferred performance metrics. Kelips, a p2p DHT, is another type of overlay network that achieves fast file lookups by increasing memory usage and background communication. Many p2p/DHT applications incur logarithmic space and lookup costs, but Kelips incurs a O(vn) storage cost, resulting in O(1) lookup costs (under normal conditions). Nodes are mapped to affinity groups using a consistent hashing function (i.e. SHA-1), and they maintain certain state information (heartbeat counts, round-trip times, etc) about nodes and files in their own group and nodes in other groups. This state information is continually updated using heartbeats and a gossip/epidemic-style communication protocol. Files are hashed the same way and inserted at a randomly chosen node in the appropriate group. Therefore, lookups usually take O(1) time because a querying node simply has to look at its state information to find a node within the appropriate group that contains the file. Obviously, lookups and insertions may take longer if the state information is insufficient. Freenet differs from the previous two overlay networks because it primarily focuses on providing anonymity, while also providing availability and scalability. Nodes share local diskspace for reading and writing of data, in which the diskspace acts as an LRU cache. Because of the finite storage at each node, least recently used files are the first ones to be replaced by newer files. Nodes also maintain routing tables, mapping nodes to binary file keys that they hold. Data insertion involves hashing the file to its binary file key and continually passing the ‘insertion proposal’ to the next node that contains the nearest key to the proposed key until the hops limit is reached. Searches are done in a similar fashion, and all the nodes along a successful request path will store a copy of the requested file. Note that in order to provide anonymity, nodes can decide to change message contents so that the true producers and consumers cannot be identified. The three proposed systems are interesting because, while their architectures are all quite different, they each try to achieve two similar goals: efficient routing of information and fault-tolerance. In order to achieve these goals, each of the systems requires their nodes to store and gather information regarding the network and other nodes in the network. But the amount of information stored and gathered at each node also affects other performance requirements, such as scalability and reliability. Kelips may have sacrificed scalability in order to provide fast lookups and handle churn because it requires “continuous background communication with a constant overhead to maintain the index structure with high quality”. Gossip messages contain contacts, views, and filetuples, but only a fraction of the node’s state can be transferred because Kelips limits each node’s bandwidth. Although the performance results presented at the end of the paper show Kelips does well with respect to fault-tolerance and load-balancing, the experiments were simulated with less than 1500 nodes (which is much less than a typical p2p application). Kelips has its advantages, though, because the increased memory usage at each node probably is not an issue for the typical p2p application user. RON definitely sacrifices scalability as it tries to detect and recover from problems in the underlying networks. As stated in section 6.2.1 of the paper, “The frequency of routing and probing updates leads to a tradeoff between overhead and responsiveness to a path failure.” RON obviously is not suited for large-scale p2p or DHT systems because the entire Internet might run slower due to the amount of probing necessary to find the fastest path between every node. RON may also have additional problems due to the use of the performance database. Couldn’t this essentially be a bottleneck for a node, or present the same problems as a centralized server if the database is shared between multiple nodes? But RON is an interesting architecture because it allows the applications to have more control over the network, and is very well-suited for smaller-scale distributed applications that require specific performance demands. Although the performance analysis in section 5 of the Freenet paper indicates that Freenet’s path lengths are proportionally short in comparison to the network size, it seems like it would still have the same problems as Gnutella. Freenet nodes maintain less information than the other two systems, so its lookups are dependent on a fairly accurate TTL value; otherwise the querying node cannot be sure if the file does not exist in the system or if the search was too limited. But the fact that nodes do not store or gather as much information as the other two systems improves its scalability, and the amount of anonymity and security that the system provides is a nice feature. Unfortunately, searches cannot be done because there is no decent mechanism for finding keys, and there is no guarantee of document retrieval because files that are infrequently requested will eventually disappear from the system. From: Jungmin So [jso1@uiuc.edu] Sent: Tuesday, September 14, 2004 2:04 AM To: indy@cs.uiuc.edu Subject: 598ig review 09/14 Paper Reviews - Sept. 14 - Jungmin So (jso1@uiuc.edu) Resilient Overlay Networks (RON) [1] is an architecture that builds an overlay on top of the internet. The RON nodes spread out in the internet forms overlay links via the underlying internet connection, and exchange messages to collect information on the paths. Using the collected information, RON can find out the quality of paths that RON is maintaining. Also, it can find out network outages. The message exchanges are performed aggressively, so that RON can quickly find out the outages and update the quality measures on the paths. When a customer decides to use RON to forward packets, RON can forward the packets more reliably and with higher performance measures through the overlay structure and the information it has been collecting. More specifically, RON can route the packet through other RON nodes to reach the destination, when the direct path has some problem. The motivation of RON comes from the fact that the current BGP-4 protocol takes a long time to recover from network outages and also BGP is unable to detect and react to the changes in the path qualities. These weaknesses are justified because BGP is designed with the highest priority in scalability, and it actually achieves high scalability. RON does the opposite of BGP. It sacrifices scalability to increase reliability and higher performance. As a result RON achieves these goals. One more good thing about RON is that since it maintains multiple potential routes, routes can be selected according to the application requirements. As a direct result of the design goals, RON does not have a good scalability because the pairs of RON nodes exchanges messages to update information on the paths it is maintaining. Because of this, RON cannot be a substitute for the BGP protocol. However, RON could be used in small scale to provide users a way to deliver traffic that requires high reliability and performance. Perhaps opening up an alternative to the scalability-focused BGP to which can provide higher reliability and performance is the main contribution of this paper. Freenet [2] is a peer-to-peer file sharing system that protects anonymity of authors and readers, and also aims to achieve efficient store and lookup. To provide anonymity, the files are stored and retrieved location-independently, using hash functions. A Freenet peer knows a few other peers, and establish overlay links with them. The peers are also identified by the hash values. When a file is inserted, the content of the file is hashed. The file is stored at the original node, but also it is propagated to the peers that have hash values close to the hash value of the file. As more files are inserted, files with similar hash values stay close together. When a user requests a file, the node propagates the request to the peers, starting from itself and next the peer with the hash value closest to the hash value of the requested file. Store and retrival operations have a hops-to-live field set, which limits the propagation of the files and request messages. This protocol achieves anonymity and location-independence using hash functions. However, depending on the hops-to-live value of request and store messages, a file request may not always succeed even if the target file exists inside the network. To protect anonymity, the nodes that store a certain file cannot be structured as in Chord. This prevents a more efficient lookup which Chord does. Since this is an earlier work on decentralized file-sharing system, it can be a major contribution of this paper. Also, using hash functions to provide anonymity along with a level of efficiency would be another contribution of this work. Kelips [3] is another peer-to-peer system, which aims to bring down the lookup cost to O(1), both in time and complexity. For the lookup, this is an improvement from systems like Chord and Pastry, since they need logarithmic cost for lookup. The idea is to store more information in each node, an amount enough to direct a requesting node to the target in O(1) time. The nodes are divided into affinity groups. A node in a group knows all other nodes in the same affinity group and "some" nodes for each of other affinity groups. The information on other nodes is gathed using gossip protocol which runs in background. Like RON did for BGP-based internet, Kelips opens up a new perspective to P2P systems, which tolerates increased storage and communication overhead to achieve efficient lookup. It is the major contribution of this paper. The argument that Kelips makes is that the storage and communication overhead is not so significant and we do not need to increase lookup cost to reduce these overheads. This is reasonable because even with a large number of files, the total size of the metadata is not that large, and gossip protocol works with a small amount of communication overhead. [1] D. Anderson et al, "Resilient Overlay Networks", SOSP 2001 [2] I. Clarke et al, "Freenet: a distributed anonymous information storage retrieval system, 2000 [3] I. Gupta et al, "Kelips: Building an Efficient and Stable P2P DHT Through Increased Memory and Background Overhead", IPTPS 2003 Jungmin So Graduate Student 459 Coordinated Science Laboratory TEL: 217-244-5791 From: Charles Yang [cmyang2@gmail.com] Sent: Tuesday, September 14, 2004 1:59 AM To: Indranil Gupta Subject: 598ig review 09/14 Charles Yang CS 598ig, Fall 2004 9/14/2004 Resilient Overlay Networks (David Andersen, Hari Balakrishnan, Frans Kasashoek, & Robert Morris) The internet is made up of many heterogeneous Autonomous Systems (AS) which use BGP to maintain the routing between them. While BGP is designed for scalability, the cost is that many metrics and qualities of the individual links is lost in the aggregate metrics that BGP uses, as well as slow detection and recovery (on the order of minutes) after a network outage. RONs have three goals in mind: 1. Fast failure detection and recovery (on the order of seconds), 2. Allow the distributed applications to decide for themselves by what metrics to route (for instance, prioritize latency over throughput), as well as 3. make is easier to distinguish and manipulate different types of traffic. RONs work as an application overlay on top of the internet routing substrate, which basically means that BGP can handle the scaling, while RON handles the routing. Each node has a good chance of being a member of a different AS, so if one AS goes down, it's unlikely to take down many nodes with it. Hence, availability as well as performance may be higher because any connection can be rerouted through a (or even a series) of intermediary nodes. In fact, if the RON route is better (according to some application specific metric) than the original internet route, it may be used. The original prototype was written as a user-level API with hooks into FreeBSD's divert socket API. An application could call the API to send or recv, and the underlying libraries would take care of routing, routing table management, path selection, etc. One consideration is security with the intermediary routing. One could imagine someone placing a modified RON node online which sniffs all the traffic passing through it. There are also other considerations such as securing access to the RON, and various other details that will probably be solved at the application level. One possible thing to investigate is to see how RONs may act with broadcasting or multicasting type applications. Freenet: A Distributed Anonymous Information Storage and Retrieval System (Ian Clarke, Oskar Sandberg, Brandon Wiley, & Theodore W. Hong) Freenet is a distributed information storage and retrieval system which emphasizes privacy and availability. Five main design goals are: 1. anonymity for producers and consumers, 2. deniability for storers, 3. resistance to attempts by third parties to deny access, efficient dynamic storage and routing, and decentralization of network functions. Files can be inserted into the system according to a simple key generation policy that ensures an easy to remember key naming convention, as well as guarantee the contents of a retrieved file. There is also functionality for updating new versions of files as well as splitting them. Freenet also caches most recently requested data in a manner so that the most popularly requested data is located closer to the requesters as well as have more copies spread over the system. Unpopular files that have not been requested may eventually fade out of the system. Freenet seems to be built with the survivability of information in first in mind. It makes it so that information can not be suppressed. While this may make sense if one is living within an oppressive country, once can easily imagine another case where a private company's intranet is hacked into, and confidential files are made public. It would be interesting to see how Freenet actually comes into use as a possible new substrate for the world wide web. Caching would be taken care of, and extremely popular files won't have to knock down the servers serving them. Of course, a lot of file space will have to be used, but file space is becoming cheaper and cheaper every day. However, it doesn't seem that latency is a big consideration for freenet, and we have yet to see how dynamic web pages could work. Kelips: Building an Efficient and Stable P2P DHT (Indranil Gupta, Ken Birman, Prakash Linga, Al Demers, Robbert van Rensesse) Kelips is a DHT designed to use more memory (O(sqrt(n)) and background communication in order to reduce file lookup times (O(1)) and increase stability to failures and churn than many of the current DHTs. Kelips splits the nodes randomly up into affinity groups. Each node in an affinity group has an affinity group view (info about connections to other co-nodes within its own group), contacts (a small set of nodes in foreign affinity groups and their respective connection info), and filetuples (a filename, host IP address of home node) for files help within their affinity group. The background overhead is due to the gossip-style heartbeating mechanism which refreshes view, contact, and filetuple information. Entries not updated via heartbeats are eventually faded out. Kelips controls the bandwidth of the heartbeating by limiting the amount of data sent per message. Lookups and inserts are O(1). If a querying node fails, it'll retry with a different mode or contact or even groups of contacts. Kelips reminds me a lot of Chord, with its hashing scheme. The affinity groups also remind me of leaf-box trees (I wonder why). One consideration is the amount of background bandwidth. If a Kelips network grows to a large size, the overall background bandwidth will increase, possibly hindering the actual useful connections if the networking bandwidth doesn't grow with the size of the network. From: Moosa Muhammad Sent: Tuesday, September 14, 2004 1:43 AM To: Indranil Gupta Subject: 598ig review 09/14 Below is a recently updated copy of my review of the above papers. Thank you. Best Regards, Moosa. ---------------------------- Reviews Written By: Moosa Muhammad For Presentation Dated: 9/14/2004 (1) Summary of "Resilient Overlay Networks" A Resilient Overlay Network (RON) is an architecture that allows distributed applications to detect and recover from path outages and periods of degraded performance within several seconds, improving over the current delay period of several minutes. It accomplishes this task by having an application-layer overlay on top of the existing Internet routing substrate. The RON nodes then monitor the performance of the Internet paths among themselves, to make an informed decision of whether to route packets directly over the Internet or by way of other RON nodes. This paper describes the design and implementation of RON, and presents several experiments that evaluate the usefulness of RON network architecture. The goal of the RON system is to overcome path outages and performance failures, without introducing excessive overheads or new failure modes. They studied the benefits of RON by evaluating two datasets collected from their 16 node wide-area deployment. They found out that RON was able to overcome 100% (in the first dataset) and 60% (in the second dataset) of the several hundred significant observed outages, and took only 18 seconds, on average, to detect and recover from a fault. An important observation and result that they derived from their experiments was that forwarding packets via at most one intermediate RON node was, for the most part, sufficient both for fault recovery and for latency improvements. One of the criticisms that can be raised is regarding the scalability of a RON system, when it is widely accepted and the number of RON nodes increases. From their paper, it is clearly visible that they have traded away scalability for reliability. Along with this, they make a “risky” assumption that users participating in the RON “trust” each other. The previous arguments lead to the conclusion that the use of RON in a large and un-trusted network (p2p being a good example of it) is not feasible. Another criticism that arises from this is the possibility of misusing or violating AUPs and BGP transit policies. This brings up another important question as to why did the authors choose to base their RON architecture on top of the Internet, which is known to be an extremely un-trusted. Future work includes preventing misuse of established RONs by implementing cryptographic authentication and access control lists. When RONs become popular, a lot of RON networks would co-exist and compete for Internet paths. Understanding the interactions between them and investigating routing stability in an Internet with many RONs is another good area for future work. (2) Summary of "Freenet: A Distributed Anonymous Information Storage and Retrieval System" This paper describes Freenet, which is a distributed information storage and retrieval system designed to protect the anonymity of both the authors and the readers. It operates as a network of identical nodes that collectively pool their storage space to store data files (which are named by location-independent keys) and cooperate to route requests to the most likely physical location of data. It is designed to respond adaptively to usage patterns, transparently moving, replicating, and deleting files as necessary, to provide efficient service without relying on broadcast searches or centralized location indexes. The general model consists of requests for keys being passed from node to node through a chain of proxy requests in which each node makes a local decision about where to send the request next. Each request is given a hops-to-live limit (to prevent infinite chains) and also a pseudo-unique random identifier (so that nodes can prevent loops by rejecting requests they have seen before). The success/failure result is passed back up the chain to the sending node. Files are identified by binary file keys (used in searching, retrieving, and storing data) which are obtained by applying 160 bit SHA-1 function. Their performance analysis relating to scalability and fault-tolerance seem pretty impressive. It was mentioned that the Freenet network can scale up to a million nodes with a median path length of 30, but they did not provide any backing behind this claim. Also, the network is quite fault-tolerant, as with 30% failure the path length still remained under 20. A very important distinction between Freenet and other p2ps is that their routing algorithms make it extremely difficult to determine who is requesting the information and what its content is. They briefly mentioned that outdated documents (which they characterized as those documents that are not accessed “often”) will be replaced by newer documents, i.e. the system doesn’t provide longtime storage of information. I would have greatly enjoyed a more detailed explanation and the heuristics that they might have derived, to accurately label a document “outdated” and replace it by a newer one. Some ideas for future work include working on implementing a simulation and visualization suite which will enable more rigorous tests of the protocol and routing algorithm. Implementing a public-key infrastructure to authenticate nodes and adding a searching mechanism are other future extensions to this project. (3) Summary of "Kelips: Building an Efficient and Stable P2P DHT Through Increased Memory and Background Overhead" There is always a tradeoff present in p2p systems, between the amount of storage overhead at each node, the communication costs incurred while running, and the costs of file retrieval. This paper takes the approach of reducing file lookup times and increasing stability to failures and churn, by increasing memory usage and constant background communication overheads. Their design consists of mapping the node identifiers ([ip address,port] pairs) to one of k virtual affinity groups. Each node requires Big-O(sqrt(n)) space to store its soft state. For example, if number of nodes, n=100,000, then inserting a total of 10 million files into the system would result in only 1.93MB of node soft state. This gives us the ability to lookup a file in constant time and complexity. The soft state at each node is kept up to date by exchanging heartbeating messages within and across groups. These heartbeating messages are propagated across affinity groups by selecting a few of the contacts as gossip targets in each gossip round. The gossip messages in Kelips carry not just a single entry, but several filetuples and membership entries. Lookup: The querying node maps the file name to the appropriate affinity group by using the same consistent hashing used to decide node affinity groups. A lookup request is sent to the topologically closet node from its affinity group. A received lookup request is resolved by searching among the filetuples maintained at the node, and returning to the querying node the address of the node storing the file, in constant time. The querying node then fetches the file directly from the node storing it. Insertion: The mapping of file name and sending an insertion request is similar to the lookup message sending mechanism. The node that receives this request picks a random node from its affinity group and forwards the insert request to it, and the file is transferred to it. The insertion and the message complexity are both constant time operations. Location awareness among different nodes inside a particular virtual affinity group is not present. The reason for this is that ip addresses do not have locality (except for the ones within a particular subnet). Therefore querying through topologically close nodes might not always result in the query to be routed through nodes that are closet to each other (in terms of number of hops). A mechanism to add this feature into Kelips is possible by updating group membership through gossiping, based on round-trip-time for message transmissions. Ideas for future work include experimenting Kelips for a larger network consisting of around a million nodes and about 50 million files. The idea behind this would be to see how scalable this system is, and whether it is a viable solution for larger networks. Some important measurements that need to be made include the increase of per-node memory requirements and background overhead generated from all the lookups/inserts, when going from 100,000 node (10 million files) system to one with 1,000,000 nodes and more than 50 million files. From: Zahid Anwar Sent: Tuesday, September 14, 2004 1:05 AM To: Indranil Gupta Subject: 598ig review 09/14 Zahid Anwar NetId: anwar CS598IG Review Freenet -------------- Summary ------- The Freenet system is one of the first among the numerous distributed file-sharing applications that provides anonymity for both information providers and consumers. It is an attempt to implement an anonymous distributed file sharing system without prohibitive overhead for storage and retrieval operations. It stores data according to lexical hashes of document keys and replicates information along path of retrieval to help ensure greater availability. This can be seen as a lot of unnecessary overhead, but in the Freenet environment it is seen as fault tolerance and also makes it difficult to find who the original owner is. The depth and time to live values have probabilistic determination of whether to change values to provide uncertainty for who the original sender or provider is. Storage is encrypted in each node by a key determined by the info of the file so that users cannot be held responsible for the data that they hold in their own storage. Strengths --------- + A distributed and reliable network that is also anonymous is a revolutionary idea + A significant improvement over current server based central file storage systems. + It lets small sites distribute large, popular documents without suffering bandwidth problems. + Rewards popular material and allows unpopular material to disappear quietly. + Data is brought closer to nodes who want it. + The popularity of each site's material causes the Freenet system to actually alter its topology + Hashing renders Freenet unusable for random searches Weaknesses ---------- - Scalability, resilience testing in a real world scenario is lacking. - Insertion flooding is one way to take out the network. - No search mechanism implemented - a standard search would allow attacks to take out specific content holders - Suffers from problems of establishing initial network connection. - The namespace is flat and producing globally unique identifiers and versioning might become a problem as the system grows Future Work ----------- - A mechanism to locate nodes may be implemented. - May want to borrow some ideas from Gnutella like using standard HTTP to transfer files Zahid Anwar NetId: anwar CS598IG Review RON ---------- Summary ------- RON is designed to enable distributed Internet applications to detect and recover from path outages and periods of degraded performance within a very short time. The design of RON seeks to meet three main design goals: (1) failure detection and recovery in approximately 20 seconds; (2) tighter integration of routing and path selection with the application; and (3) expressive policy routing. RON nodes monitor the quality of the paths between them, and use this information to decide whether to route packets directly over the Internet or by way of other RON nodes, optimizing application-specific routing metrics. An evaluation of this system is presented using a 12 and a 16 node RONs. The authors admit that these sizes are small and that the system does not scale beyond 50 nodes. Strengths --------- + Their implementation is able to route around 60% to 100% of all significant outages taking 18 seconds on average and do so even in the face of an active DoS attack. + The authors claim that RON improved loss rates, latency and throughput. However, these benefits seem to apply to a very small percentage of samples with only a small amount of improvement. + Conferencing applications may link directly against the RON library, transparently forming an overlay between all participants in the conference, and using loss rates, delay jitter, or application-observed throughput as metrics on which to choose paths. + An administrator may use a RON-based router application to form an overlay network between multiple LANs as an 'Overlay VPN'. This idea can be extended to from an 'Overlay ISP', by linking points of presence in different traditional ISPs after buying bandwidth from them. Weaknesses ---------- - RON doesn't solve the problem of bad BGP routing for any arbitrary hosts on the Internet. A RON network is only as good as its participating members. - The evaluation did not examine the performance of routing to a non-RON node through the RON network. This is important because the RON network itself is small, and must remain so in order to be effective. - One of the problems the authors faced with NAT is that two hosts behind the same NAT will appear to have the same address. Their solution is to use the IP of the host (from behind the NAT) as its identifier. However this leads to problems of uniqueness, since the addresses might be used behind other NATs in the RON. If you concatenate the IPs together this could make a unique identifier. - Dynamic instability was prevented using hysteresis. Hotspots in the network can induce rapid topology changes due to the feedback-based optimization techniques. How would hotspots effect performance. - No accounting for the deviation of latency in selected links, nor does it provide such data. Latency-sensitive interactive applications are typically sensitive to deviations in latencies. Future work ----------- - Add mechanisms for sharing bandwidth cost. RON does not consider the possible interactions between multiple RONs competing for the same bandwidth. It is conceivable that isolated RONs would detect and use some overlapping set of good paths, which would cause dynamic instability in the system if each RON decides to send significant data through those links. - Security needs to be addressed since participating in a RON implies trust that the other participants will forward your data correctly and will not abuse your forwarding. Zahid Anwar NetId: anwar CS598IG Review Kelips ------------- Summary ------- Kelips is a structured P2P overlay (like Chord, Pastry). It implements a Distributed Hash Table that has only O(1) message overhead to both locate as well as route an object. To achieve this it takes advantage of increasing memory size on computing devices, using O(sqrt(N)) memory storage for its soft state where N is the number of nodes in overlay. It maintains the structure of the overlay by relying on an epidemic protocol. Results show that it is extremely resistant to high churn. Load balancing is comparable to existing systems and the system is locality aware. Strengths --------- + This overlay protocol would be very revolutionary in resource discovery applications like for example large-scale sensor networks + Lookups succeed even under failures + Recovery from failure of half the nodes within seconds + First peer-to-peer application that has a lookup cost the same as that of Full index duplication O(1) and at the same time a memory utilization of O(sqrt(N)) << O(N) + Assumption of availability of increased memory very natural since most desktop machines can afford to give a lot more memory to overlay routing tables + Farsite uses routing tables of size O(dn^(1/d) ) to route in O(d) hops, but does not address rapid membership changes. Weaknesses ---------- - The evaluation shows that Kelips targets nodes in the order of thousands. We can only assume that it will work scale to the internet where the order of nodes is a lot more. - Imposes a constant communication overhead and may cause data quality to lag if updates occur too rapidly - A gossip based architecture may only provide weak consistency guarantees. What if we wanted stronger guarantees? From: Pradeep Kyasanur [kyasanur@crhc.uiuc.edu] Sent: Tuesday, September 14, 2004 12:07 AM To: Indranil Gupta Subject: 598ig review 09/14 Pradeep Kyasanur netid: kyasanur 1. Resilient overlay networks , D. Andersen et al, SOSP 2001 Resilient Overlay Networks (RON) is an application-layer overlay designed to react quickly to network outages in the Internet. The overlay enables users to define their own notion of reliability. Custom routing algorithms, and user-specified routing policies can also be supported by the overlay architecture. Evaluations indicate RON significantly reduces time to recover from network outages, and in certain cases provides a significant increase in TCP throughput as well. RON is an innovative design that may be useful to implement other user-desired functionality such as load balancing, multi-path routing, etc. RON is intended for small networks (2-50 nodes), and thus is free from scalability concerns, which is exploited to provide significant advantages over traditional Internet. On the other hand, the lack of scalability implies that RON cannot be used for applications that involve a large number of end-systems. For example, while RON is useful for small video-conferencing applications, it may not be useful for large-scale video multicasts. 2. Freenet: a distributed anonymous information storage and retrieval system, I. Clarke et al, 2000 Freenet is a distributed storage system. The key property of Freenet is the ability to maintain the anonymity of both the publishers and subscribers of data. Each file or file keywords in the system map to a key. Keys can be anonymously published and retrieved using Freenet. Duplication of data, and hiding the source of queries and updates, ensures the desired anonymity properties. Freenet has an interesting property of having many copies of frequently accessed files, and removing infrequently used files from the system. This property automatically ensures high reliability for popular items, while purging unused files from the system. Freenet heavily uses public-key cryptography and one-way hash functions to guarantee anonymity properties. Frequent use of expensive cryptographic operations may significantly increase the latency of file storage, and retrieval. 3. Kelips, I. Gupta et al, IPTPS 2003 Kelips is a Distributed Hash Table designed to support constant query time at the cost of O(sqrt(n)) memory requirements. Nodes in the system are divided into O(sqrt(n)) "affinity groups" each having O(sqrt(n)) nodes. Each node is aware of (most) other nodes in its affinity group, and a constant number of nodes in other affinity groups. File insertions and lookups can be supported in constant time, by first routing to a known neighbor in the correct affinity group, and then using the closest known node in the neighbor's affinity group. Gossip-based multicast is used to exchange group information using a constant background bandwidth, and a latency polylogarithmic in the number of nodes. Kelips differs from earlier peer-to-peer systems by using more memory, and continuous background updates, to support constant query time. The increased memory requirements are not significant for moderately sized hash tables. The performance of Kelips depends on correctly identifying the number of affinity groups to maintain. For example, if the number of nodes in the network double, the number of affinity groups need to be increased by 40%. If the number of nodes in the system vary, an algorithm that dynamically adapts the number of affinity groups and updates the group membership accordingly is necessary. From: al [aharris@cs.uiuc.edu] Sent: Monday, September 13, 2004 10:54 PM To: Indranil Gupta Cc: aharris@cs.uiuc.edu Subject: 598ig review 09/14 Albert F. Harris, III CS 598IG Paper Review Resilient Overlay Networks Main Idea: The Internet is made up of many autonomous systems, each of which might fail. BGP routes between AS's hiding and delaying specific routing updates to prevent large scale oscillations in the Internet routing core as well as to promote scalability to enormous numbers of AS's. This leads to the possibility that tens of minutes can pass before a routing disruption is mended. An overlay network can be used to filter critical route information between AS's that would not be used by BGP to mend routes faster (on the order of several seconds). One of the ways RONs achieve their fault tolerance is by pressing routing up towards the application layer. One reason for this is that different types of traffic have different definitions of "failure." For example, a long term bulk transfer needs to get all the data through, but perhaps has very loose time constraints, therefore failure must be a critical failure (link dissolution). However, real-time traffic will have time constraints, therefore a failed path could be one with unacceptable latency. The simple idea is that performance can be improved by breaking the traditional layered model and filtering certain information up to the application. Of course, the main limitation is that as the size of the RON grows, the reasons this information is not used at the network layer in the first place become relevant to the overlay. It is unclear to me what the expected sizes of RON would be in actual use. Freenet Main Idea: Peer-to-Peer file sharing applications would like to incorporate privacy and high availability into the system design. It is desirable for individual nodes to be unable to keep track of exactly what sort of files are stored at any one time on that node. Also, it is desirable to make it very difficult if not impossible to tell where the origin of any file, or the destination of any file is. Most of these privacy concerns seem to be to protect people who are breaking copyright laws;) Also, a p2p system should be highly available. If a file is contained in the system, it is desirable to have the file locatable by any client in the system and retrieved with reasonable delay. Therefore, any centralized database, containing either files or file locations need to be avoided. Any centralized routing mechanism would also serve as a single point of failure. Routing neighbors as well as file replication are handled transparently by the system as it is used. In other words, as files are requested, they are copied closer to the interested node. Also, along the way, routing tables are updated as new nodes respond down the line. In this way, connectivity should increase as the system is used. Since there is no permanent data store, time to live values keep data in the system. Any node can arbitrarily claim to be the source of data, or claim some other node was the source, preserving anonymity. Out of band means are still used for node insertion in the system. Of course, it seems the goals of anonymity and performance are often at odds. It is interesting that performance in this system does not suffer too badly from the requirements of the system. Kelips Main Idea: There is an intrinsic tradeoff between lookup times, storage overhead at each node and network communication. Most current p2p systems focus on schemes that yield logarithmic path lengths. However, due to the likelihood that such paths are effected by high latency / low bandwidth links, it is possible that the overall cost of lookup will still be high. Kelips trades off extra soft-state memory usage and network communication in the form of gossip in order to achieve constant lookup costs, thereby alleviating the effects of high latency / low bandwidth links. This is an interesting idea, coming from a mobile computing background however, I would not want to run a gossip client on a mobile computer. energy efficiency and bandwidth are major commodities. Of course, this is not the intended target for this system. From: William Conner [wconner@glsn33.ews.uiuc.edu] Sent: Monday, September 13, 2004 7:12 PM To: indy@cs.uiuc.edu Subject: 598ig review 09/14 The Resilient Overlay Network (RON) is an application-layer overlay that takes advantage of physical redundancy in the underlying physical network to get around some of the undesirable properties of the Border Gateway Protocol (BGP). In particular, RON can recover from path outages and performance degradation much faster than BGP (i.e., RON recovers on average in less than 20 seconds rather than several minutes like BGP). It accomplishes this task by aggressively monitoring the virtual links in the overlay network. RON, which resides in the application layer, also allows applications to have more control over the routing of their packets. Based on its aggressive monitoring of latency, loss, and throughput, applications can select the best paths that suit their needs. Adjusting routing based on metrics important to the particular application is not available in BGP. Finally, RON allows more expressive routing policies. For example, a RON node residing on a particular network that doesn't know of a path to another network from available BGP information can discover a path to another RON node on that network, even though the other non-RON nodes on each network may not be able to talk to each other. The biggest problem with RON is the issue of scalability. Many of RON's benefits are due to its aggressive monitoring of its virtual links, but this aggressive approach would become too costly if you add too many nodes. The authors acknowledge this problem and cite plenty of scenarios where their implementation (which only supports between 2 and 50 nodes) would be useful. The authors also acknowledge that RON can possibly be misused to violate policies that were supposed to be enforced by BGP in the first place. An area of future work would be adding support for applications to use more than one metric when making routing decisions (e.g., using top-k queries to find the best path with each metric as a subsystem providing rankings/scores of paths). Freenet is a peer-to-peer storage and retrieval system that provides anonymity for both the authors and readers of the content. Rather than locating a file source via some search algorithm and contacting that source directly for download (as is done in many other p2p systems), users use store-and-forward IP-like routing (based on keys rather than IP addresses) to query/insert data and receive responses. Keys can be computed based on keywords, namespaces, or file content. An interesting property of Freenet is that each node along the way stores a copy of the response. This caching helps make future queries more efficient. It also makes it difficult to determine the origin of a file which helps protect the author's anonymity. One possible problem with Freenet is that making replicas at every node along a query response path could potentially be very costly, especially if many different users are interested in a popular file. At a certain point, it seems that some of the redundancy would be unnecessary and wasteful. Also, Freenet does not have a good way to find keys with indirect files. As the authors admit, there is no way to manage the large volume of indirect files that would be needed to find keys. Finally, Freenet doesn't have a mechanism to ensure that an unused file will remain in the system permanently. For some applications, this property would be undesirable. Kelips is a peer-to-peer system that provides faster lookups than many other popular p2p systems. More specifically, file lookups in Kelips take O(1) time at the expense of increased memory and background network communication overhead. The memory usage in Kelips is O(sqrt(n)) space per node in an n-node system. The continuous background communication overhead is constant. Each Kelips node has some soft state that consists of all the other nodes in its affinity group, some contact nodes from each of the other affinity groups, and a list of tuples containing file name and location data. All of the entries in each node's soft state are updated with gossip-style multicast. If a heartbeat isn't received after a certain timeout value, then that entry is deleted from the soft state at a particular node. Assuming no node failures, a file lookup or insertion can be accomplished in O(1) time and O(1) message complexity. With query re-tries due to failures, lookups are still O(1) time and O(1) message complexity, but insertion is O(log(sqrt(n))). One possible shortcoming is that although the paper mentions a medium-sized p2p system of 100,000 nodes should be supported by Kelips, the experimental numbers only include simulations for a few thousand nodes. Since the experiment was ongoing at the time of publication, a simulation with hundreds of thousands of nodes could possibly be future work. This would provide some solid evidence that Kelips performs well for medium-sized p2p systems. From: Jintae Kim Sent: Tuesday, September 14, 2004 10:24 AM To: Indranil Gupta Subject: 598ig review 09/15 CS598IG Review (9/15) Jintae Kim (kim28@uiuc.edu) Resilient overlay networks, D. Andersen et al, SOSP 2001 This paper proposes an overlay routing system that emphasizes better QoS and policy configuration than BGP. Since the design of BGP mainly focuses on the scalability given the huge size of the Internet, it does not handle the routing information in detail. Resilient overlay Network (RON) tries to exploit much more link information to meet its design goals: enhanced fault-tolerance, tighter integration with applications, and expressive policy routing. Unlike BGP, each node of RON continuously monitors the latency, loss rate, and throughput of the links to the neighboring nodes using active probing. This information is constantly evaluated and used in path selection algorithms. The experimental result looks promising. RON overcomes path outages better than the usual Internet at a faster rate, and handles packet floods well in tens of seconds. RON also improves the loss rate, latency, and TCP throughput. The authors successfully present a novel concept: resilient overlay networks. The main idea of this paper comes from considering the trade-off between QoS and scalability very well in designing the system. The paper not only shows that RON achieves better fault-tolerance, but also improves overall performance. The clear disadvantage, as the paper indicates, is its lack of scalability, because all the nodes are involved in active probing. This paper also does not mention the possibility of multiple RONs. If multiple RONs can be considered, some links can be involved in several different RONs. Such links can possibly cause routing instability because multiple RONs will simultaneously detect that they are “good” paths and direct their traffic to such links. Also, in this case, some nodes involved in multiple RONs can have more increased monitoring overhead. Freenet: a distributed anonymous information storage and retrieval system, I. Clarke et al, 2000 Freenet is a P2P application designed to ensure true freedom of communication over the Internet. The purpose of this paper is to design a peer-to-peer network with preventing information censorship and maintaining personal privacy. The main idea to achieve the design goals is that Freenet uses the hash keys. There are mainly two types of keys: Content- hash keys (CHK) and Signed-subspace keys (SSK). CHK, generated by hashing the content, is used primarily for data storage (specifically, update and split). SSK, a hashed random public key concatenated by a hashed description, is used as a private namespace. This idea of hash key provides both security and anonymity, because it is not hard to recover the original descriptive string from the hash key. Since this design is essentially a distributed file system, there is also no central point of failure, which could have been an easy target of the attackers. The strength of this paper comes from the intuitive idea. Anonymity over the files was pretty novel and also a significant improvement over existing P2P systems at the time of publication. There are, however, some problems in Freenet as well. Firstly, it does not support keyword search. It is not very easy to retrieve the files with the exact descriptive strings that file inserters generated. Second, the test setting is somewhat too simple. It has not really been tested in a realistic environment. In the real world, some nodes can generate heavy congestion if they have frequently requested files, or there can be even flooding attacks which request or even insert files so frequently, which Freenet is vulnerable against Third, although this paper claims that it provides security, it is vulnerable to several types of attacks. The paper indicates that it is vulnerable to the insider attack. It is also vulnerable to some basic attacks, such as replay attack man-in-the-middle attack. Kelips, I. Gupta et al, IPTPS 2003 This paper proposes a novel DHT, which is more focused on reducing the lookup cost. Two main design decision that was made in Kelips was (1) the concept and the size of affinity groups and (2) the use of gossip protocol in an effort to update soft state. In Kelips, nodes are hashed into sqrt(N) groups and each node has pretty much information about other nodes inside the same group. To update the change of system over time, each peer periodically selects a few peers, both inside and across the group, and sends them partial soft state information using gossip protocol. The methods used in Kelips can also be viewed as a trade-off between lookup cost and ‘memory usage and background overhead.’ Compared to other DHTs, it has more memory usage, O(sqrt(n)), as a price of maintaining O(1) lookup cost. But I agree with the authors that memory usage can be tolerant in a mid-size peer-to-peer systems. Another advantage of this paper is that ussing background overhead has enabled Kelips to be fault-tolerant over failure and churns. Epidemic protocol turns out to be intelligent enough in a sense that it provides such fault-tolerance at a low cost, that is, with only a constant overhead. From: Romit Roy Choudhury [croy@crhc.uiuc.edu] Sent: Tuesday, September 14, 2004 10:16 AM To: Indranil Gupta Subject: 598ig review 9/14 Resilient Overlay Networks: --------------------------- This paper proposes an architecture that utilizes overlay networks to build reliability and performance into large scale internet routing. Since BGP (or its variants) do not support fine grained control over paths, converging to the best route or bypassing failures in the internet can often consume high latency. While one solution could be to announce more information about the network, there might be scalability as well as administrative issues associated to it. By using a application layer overlay, the authors intend to maintain a periodically updated report of the paths in the internet. Routing through at least one of these RON nodes will therefore lead to better performance, since paths can be chosen based on metrics of interest, and path failures and losses can be bypassed quickly. The key contribution in the idea of RON pertains to marking multiple end-points on the internet, from which abstracted network information can be gathered. Since these endpoints communicate at the application layer, they are capable of measuring metrics that are of interest to the application layer. Thereby, the choice of paths can be adaptive depending on the requirement specification. Clearly, the underlying routing protocol does not need to be application aware. The RON nodes execute a link state protocol between themselves -- messages are periodically exchanged to keep nodes aware of the connections and qualities of the links. Traffic tunnelled through the RON nodes can be routed based on the recent path history. I am unsure how RON might scale with size. Clearly, frequent link state packets can add to the internet traffic, and may not scale well when several nodes become RON nodes. An improvement to RON could be as follows. Once path (A's) outage is detected, a RON node can bypass the outage through another completely different path (say B). However, the resilience of the underlying internet can find routes around path A, that might be of comparable or better than the new path, B, chosen by RON. In such cases, RON could preemptively switch paths from B to A. Of course, oscillations could be a consequence, but such issues can be handled through smoothing. FREENET: A Distributed Anonymous Information Storage and Retrieval System ------------------------------------------------------------------------- This is a proposal on storing, replicating and retrieving data anonymously on the network. The requirement to make publications anonymous and yet public has become pronounced with increasing online publishing. FREENET is an architecture that proposes a hashing mechanism to generate keys from the contents of a file, and based on these keys, files are stored at different nodes. While retrieving these files, a request (expressed as a key) is routed from one node to the other, until a node successfully posseses that key. Hops-to-live (like TTL in the internet) limits the scope of the search. Once a node finds that it contains the file, it routes it back to the originator of the request -- other nodes along the way back to the originiator caches the file. To preserve anonymity, the node that stores the file can specify a different node identifier as the keeper of the file. FREENET has a set of desirable properties -- all files requested by a particular node accumulate closer to the requester over time, leading to reduced search latency. In addition, close values in the key-space does not indicate proximity in the contents of the file, thereby preventing attackers from launching malicious attacks on all similar content files. For storing files, FREENET avoids collisions by propagating the file to hop-to-live hops, and only upon finding no other nodes with the same key, is the file stored on the node. I am not sure if this is a scalable approach -- larger network size can lead to higher latency in storage and higher traffic. In addition, hops-to-live must be well estimated, and optimistic estimations might lead to collisions. Kelips: Building an Efficient and Stable P2P DHT ------------------------------------------------ Kelips is a P2P system that aims to provide better join/fail reliability and lower insert/lookup latency at the expense of higher local memory requirements and higher background communication. The key idea behind Kelips is to subdivide the system into multiple smaller groups, with members in each groups maintaining information about its own group and small amounts of information from other groups. Each member maintains information about a subset of its own affinity group, a small number of members of foreign affinity groups, and a subset of files and the address of the keeper of the file. All the information maintaned by any node is periodically refreshed through proactive heartbeats. Heartbeats are disseminated in a gossip-style approach (performed over UDP). To be able to limit the background communication, the gossib messages are populated with equal amount of new and old information. On a need to lookup a file, the requestor node can calculate the key of the file (using SHA-1) and accordingly contact one of the members of the corresponding foreign affinity group. The contacted member is able to provide the address of the keeper of the file -- a O(1) complexity operation. A file storage is preceeded by the computation of the file key (using SHA-1), and then forwarding that file to the topologically closest node present in the affinity group of that computed key. This selected node picks another random node from its affinity group, and assigns it the responsibility of keeping the file. This information about the file and its keeper is now floated into the gossip stream for others to be aware of -- again a O(1) time mechanism. Kelips trades memory storage and bandwidth to gain upon latency and churn. The architecture of the system seems to be scalable, which probably means that that tradeoff is made in the right direction. However, if members of the same affinity group tend to be geographically scatterred, then the bandwidth requirements can grow really high. It might be a good idea to extend Kelips to incorporate spatial correlation in forming the affinity groups in Kelips. ----------------------------------------------------------- Romit Roy Choudhury www.crhc.uiuc.edu/~croy ----------------------------------------------------------- From: Mayssam Sayyadian Sent: Monday, September 13, 2004 11:30 PM To: Indranil Gupta Cc: Mayssam Sayyadian Subject: 598ig review 9/14 Mayssam Sayyadian ------------------------------------------------------------ Resilient Overlay Networks David Anderson et al. http://nms.lcs.mit.edu/ron This paper introduces and discuss advantages of RON (Resilient Overlay Networks). The problem is interesting since it aims improving the Internet's reliability. Internet is a widely famous network which very rich in scalibility in terms of routing. But this excellent scalablity comes at the cost of reducing fault-tolerance of end to end communication between nodes. RONs seek to detect and recover from network failures. In RON, we can name three main goals that are: 1- Failure detection recovery (increase of fault-tolerance), 2- Tighter integration of routing and path selection with the application and 3- Providing a framework for expressive routing ability (choince of path for packets, etc.) In RON network nodes participate in a limited size overlay network and they cooperate with one another to forward data on behalf of any other nodes in the RON. The way RON works in finding problems is by aggressively probing the paths connecting its nodes and each node exchanges information about the quality of paths among themselves, builds forwarding tables based on a variety of metrics such as path latency, packet loss, throughput, etc. The experiments are well designed and they consist of two distinct datasets. In the evaluation, first the ability to detect outages and recover quickly is studied. Then performance failures and RON’s ability to improve the loss rate, latency, and throughput of badly performing paths is investigated. In general it's illustrated that RON can substantially improve loss rate, latency and TCP throughput for a small number of nodes (less than 50). To do so, forwarding packets via at most one intermediate node is sufficient for fault recovery and latency improvements. Finally the paper mentions a few critisism of the proposed architecture such as problems in working with NATs, trust and access control, etc. and some discussion is made and a few not very robust solutions are provided. Maybe the most outstanding critism is that a RON is not usually scaleable and they should be created specific to the appliction. ------------------------------------------------------------------------------ ----------- Freenet: A Distributed Anonymous Information Storage and Retrieval System Ian Clarke at al. This paper describes Freenet which is What is a P2P application as a distributed storage system, designed for the sake of freedom of communication over the Internet. It aims for anonymity for both publishers and consumers and holders of information. There are some silimar previous works in different aspects such as Gnutella, FastTrack, Overnet in terms of File-sharing. Also in terms of consumer anonymity services such as Anonymizer and SafeWeb could be mentioned. Rewebber, TAZ, Publius are examples of producer anonymity systems. And for shared-storage we can mention OceanStore, Cooperative File System, PAST, etc. The main decisions for the architecture of the system is that it's a P2P network, participants share bandwidth and storage space, each file in network is given a globally-unique identifier (GUID) and queries are routed through steepest-ascent hill-climbing search. The decisions are discussed and solutions is illustrated and some issues such as joining the network, route training, storage mainainance and performance are discussed. As mentioned in the paper there is always a tradeoff between network efficiency, anonymity, and robustness. This system tends to be more anonymous rather than efficient. The most drawback of the system is that it lack searchability and establishing initial network connection which are big issues. ------------------------------------------------------------------------------ ----------- Kelips: Building an Efficient and Stable P2P DHT Through Increased Memory and Background Overhead Indranil Gupta Kelips is a DHT that aims to reduce file lookup time and increase stability to failure at the cost of increasing increasing memory usage and constant background communication overhead. The system exploits p2p gossip to partially replicate file index information. Normally in Kelips lookup time is O(1) and changes in membership is detected fast. Memory utilization is O(sqrt(n)) and Also in case of failures lookup success in ensured through a mechanism of query routing. As for the protocols, maybe of the main advantages of the system could be the adaptive contact maintenance which is adaptive, based on distance and accessibility (e.g., no firewall), trust, etc. which is very practical. A Preliminary experiment is provided. Finally a discussion about why Kelips works better than other DHTs (like Chord, Pastry, etc.) when one tunes them (by varying the value for branching factor of the overlay structure) for faster lookup is made. The discussion indicates the advantage of Kelips in being loosely structured and hence not disturbing the network traffic.