From: Jin Liang [jinliang@cs.uiuc.edu] Sent: Tuesday, October 05, 2004 12:21 PM To: Indranil Gupta Subject: cs598ig review 10/05 A Comparison of Overlay Routing and Multihoming Route Control This paper compares the performance of multihoming routing control and overlay routing. Multihoming routing means the end network has one or more network service providers, so the end network can dynamically choose which ISP to use in order to reach a particular destination. If the end network has up-to-date data for the for the different ISPs, it can select the best one for the data transmission. Multihoming route control is different from overlay routing. The end network can only select one ISP from the list of ISPs to which it has a connection. Overlay routing, on the other hand, can select any node in the wide area network as the intermediate relay node (and there can be multiple relay nodes). Multihoming route control is a special case of overlay routing, where only a local node (belonging to a different ISP) can be selected as a relay node. This paper shows that when k = 1, k-overlay routing has much better performance than k-multihoming, as has been shown by previous work. When k = 3, however, the performance benefit of k-overlay over k-multihoming is marginal. The paper thus concludes that k-multihoming with k = 3 is good enough, so it's unnecessary to use k-overlay routing, which often violates the Internet policy routing. The paper also analyzes the availability of the paths selected by the two schemes and shows that k-multihoming can route around almost all observed failures, although its fault-tolerance is not as good as k-overlay routing. One issue not addressed by the paper is whether it is possible for each end network to have multiple service providers. Common users are even more unlikely to have multiple ISPs, so how can they benefit from multihoming. Preserving peer replicas by rate-limited sampled voting This paper presents a scheme to maintain the integrity of digital documents for cooperating libraries. The goal is to design a system that is low-cost, can run for a long time, and without central maintenence. The design is to have each library maintain a friend list and a reference list of peer libraries. Every certain period of time, the library contacts a random subset of the libraries in its list, and ask them for their version of the document. If the majority of the peers have the same version, then it is regarded as the authentic version. Peers can nominate other peers when contacted for a voting, and a library can replace its list by the new peers learned this way. Although sampled voting is a good approach to decentralized replicas maintenance, the paper did not address the problem whether its claimed "random sampling" is truly random. A more important issue is that the paper didn't address the possible partitioning of the network, where the system partitions in two groups, and each library only has reference to peers in its own group. On Transport Layer Support for Peer-to-peer networks. This paper argues that TCP is inappropriate for supporting peer to peer applications. Therefore, they propose to support multipoint to point connections at the transport layer. They outlined several key issues in designing such a system and presented a case study for a multipoint to point transport protocol, the Radial Reception Control Protocol. The R2CP protocol is receiver driven, and is built on top of a RCP protocol. Multiple RCP pipes in R2CP conection are coordinated by the R2CP engine at the receiver. The engine is responsible for buffer management, flow control, reliable delivery, etc. Although the paper presents an interesting protocol design, there is not much performance evaluation results. Therefore, it's not clear whether such a protocol can really achieve the benefits as the paper claimed. From: James Richard Newell Sent: Tuesday, October 05, 2004 11:52 AM To: Indranil Gupta Subject: 598ig review 10/05 P2P Apps (2) - Sampled Voting, Transport Layer for P2P, Multihoming James Newell 10/05/04 The first paper is "Preserving Peer Replicas By Rate-Limited Sampled Voting" by Maniatis, Rosenthal, Roussopoulos, Baker, Giuli, and Muliadi. The authors propose a new system called LOCKSS for persistent long-term archival storage of documents on a peer-to-peer network service; where the target audience consists of academic libraries that wish to preserve digital journals. The authors address the scalability, longevity, security, and consistency problems by focusing on certain design principles such as absence of long-term secrets and reputation mechanisms, lack of central control, and reliance on inertia. The existing LOCKSS system would cache local journals to local readers and perform opinion polls to maintain cache consistency on Archival Units. The new opinion poll protocol using polling by inviting a small subset of peers it has encountered to vote on an AU digest. Hopefully, the results are bimodal (otherwise set off a human alert). This subset is the inner circle; the outer circle can be nominated to become future members of the inner circle (by participating in the vote but not counting it). When invited to be part of a poll (from a reference list), each member will need to solve a computation puzzle to increase the cost of Sybil attacks. Votes are based off a hash of the AU and interleaved with provable computation effort. After a poll, the inner circle list is modified using a series of algorithms including a churn from an out-of-band friend list. The authors then go on to simulate their protocol for 30 years, and find that a stealth advisory fails even with 1/3 of the peers subverted. This is an interesting idea because it deviates from the traditional paradigm of time. Where the goal here is long-term stability, small-time performance can be expendable. While I don't particularly believe any advisory would spend years trying to take down an academic journal system (unless it is a bored teenager), and I would think more sensitive data would not rely on peer-to-peer networks (government data). Also, the authors try to tackle the Sybil attack by using computational puzzles, which is a very hardware dependent solution. The next paper is "On Transport Layer Support for Peer-to-peer Networks" by Hsieh and Sivakumar. This paper makes the case for a new transport layer paradigm specifically designed for peer-to-peer networks. They claim that current use of TCP's unicast is inadequate for optimal performance, and suggest instead a multipoint-to-point connection. This can be thought of as an inverted multicast where there are many sources sending data to single destination. The goal is to increase the stream of the incoming data by replicating sources. This has already been shown to be superior in tradition content-based peer-to-peer networks such as Bittorent. However, the only was to achieve this on something like video-stream is to provide support in the transport layer. Furthermore, the multipoint-to-point connections provide redundancy for error control and allows out-of-band resiliency against dropped packets. Due to the unreliable and asymmetric nature of P2P connections, this will allow smaller-bandwidth nodes to participate and relive pressure of high-performance peers. The transient behavior of peer longevity forces most of the connection control to remain on the requestor (the destination point) because it is the only static part of the connection. The authors then go on to describe a protocol that they think fits their call for peer-to-peer transport layer- R2CP. R2CP was originally designed for heterogeneous wireless interfaces and supports the crucial multipoint-to-point connections. Although very short, I found this paper to be quite interesting because this is the first paper I read that suggested adding new functionality solely based upon peer-to-peer networks that doesn't reside in the application layer. This obviously has many future directions, and for it to be accepted, it needs to be back-compliant with the common TCP connections. From what I can tell, it seems like the biggest problem is packet-scheduling and re-ordering. Since you are retrieving data from many different sources, it would difficult to achieve optimal performance by coordinating each source to send a different part of the data (particularly if it is a stream). Of course there would probably be some redundancy to fix a small amount of packet-losses (which is only best-effort). The biggest concern I have comes from my own experience using Kazaa which tries to emulate this behavior. Typically you will get 3 or 4 connections that have extremely low bandwidth (1 to 2 KB/s) and one dominate one ( > 20 KB/s). If this behavior is replicated on say a video stream, it would very difficult to use the low-bandwidth connections for anything since the dominating one would leave them in the dust. The last paper "A Comparison of Overlay Routing and Multihoming Route Control" by Akella, Maggs, Pang, Seshan, and Shaikh does a comprehensive study on the use of intelligent use of BGP routes and ISP multihoming can reduce RTT, increase throughput, and increase resiliency (along with overlay routing). BGP is well-known to be the bottle-neck of Internet routing in today's connections. Some existing protocols have already tried to circumvent this problem by abstracting a new overlay on top of the current routing architecture. This results in an elite routing group (such as RON) that is quickly able to bypass failure BGP paths and find better performing routes. This paper contends that one can achieve similar performance by making better BGP selection at the end-points. The basic assumption that the overlay networks used was that each end-point subscribes to a single ISP. If end-networks sites were able to choose from many ISPs, it would be easier to bypass bad BGP links (this is call multihoming). The authors then go on to compare how much benefit overlay routing would achieve if multihoming and intelligent route-selection was enabled. They found that multihoming route control can provide similar performance gains one experiences using overlay routing. However, overlays can provide marginally better RTT and resiliency than multihoming route control. From what I can tell, the main drawback about Multihoming route control compared to overlays is the need to change existing architecture and the requirement of multi ISPs (too expensive for the average user); whereas overlay networks don't require anything special other than the middle-ware. Also, in multihoming what would be good method to monitor different ISP connections with arbitrary destinations? This seems like it would be a difficult task. If there is really that much problems with BGP performance that require multi-ISP connection, I believe more effort should be spent on fixing the underlying BGP downfalls to prevent elitist groups from developing (which is what multihoming and routing overlays are heading towards). From: Yookyung Jo Sent: Tuesday, October 05, 2004 10:37 AM To: Indranil Gupta Subject: 598ig review 10/05 A comparison of overlay routing and multihoming route control : Summary : In the past, to overcome the limitation of BGP Internet routing, overlay routing approaches such as RON were suggested. In this paper, authors analyze in detail what makes the performance of overlay routing superior to BGP, and investigate the possibility of whether a scheme respecting the current BGP, yet performing as good as overlay network can be achieved. Their suggested solution is multihoming (end-points connected to multiple ISPs, typically 3). This solution is compared to end-points connected to overlay via 1 ISP and via multiple ISPs (typically 3), in terms of performance (RTT and throughput) and availability. Their experiment shows that multihoming performs nearly as good as overlay approach (though overlay approach is better, because it has the superset of path choice compared to that of multihoming). Understanding Performance Gap: 1. Majority of cases of overlay being better comes from overlay choosing physically shorter path, while a few cases where overlay perform far better comes from overlay avoiding congestion. 2. Most overlay path with better RTT violate common inter- domain routing policies (BGP), while a fraction of policy compliant overlay paths can be achieved with BGP, if cooperative policies can be employed between ISPs. Comments : [C] : While RON and this paper talk about very practical solutions to the problem of how to overcome the limitation of BGP, they seem to inspire deeper thoughts on network routing in general. RON has shown that faster routing convergence can be achieved with coarser level of routing nodes, suggesting that some way of hierarchically-leveled routing scheme could achieve effective performance. Multihoming might be inspired by pracitcal cause, but it has analyzed to what extent coarser level routing can perform better. On transport layer support for peer to peer networks : Summary : Communication in P2P systems can be better served by a transport layer designed for it, rather than TCP. This is because while TCP is designed for the end-to- end performance in server-client situation, in P2P communication source (which is just a peer) often has limited bandwidth but the data source is often replicated over many peers, suggesting the possibility of multipoint-to- point transport layer protocol in place of TCP. Design principles such as multiple states, decoupling of functionalities, packet scheduling, receiver- driven operation are considered. Comments : [C] : The use of this transport layer protocol seems to need a support of means identifying the replicas in P2P system. The simplest strategy could be that a user at destination chooses the sources by looking at the filenames, but this does not guarantee the bit-wise identical copies. So, the use of the protocol needs to have some system-support of indexing where are the replica of files. Preserving peer replicas by rate-limited sampled voting : Summary : This paper suggests a distributed storage that lasts for long period of time, against natural damages and strong adversaries, by peer replicas and voting. How it works : In this system, digital content (i.e. publication archive) is stored among many peer storage systems. Each storage system (aka peer) decides to check the sanity of its archive according to ramdomized period. It maintains its reference list and randomly picks peers and ask for voting (basically, hashing of the archive to check the validity of the copy and some provable computational effort). Those peers that successfully participate in the voting gets its place in inner circle list and they can recommend other peers for voting, which will be placed in the outer circle list (they also participate in the voting to prove they are loyal but the vote doesn't count for this round). Reference list is updated with random selection from outer circle list. The peer who initiated the voting decides its copy is in good shape, if it coincides with the majority voting, or it repairs its copy, if it collides with the majority voting, or raises security alarm, if there is no majority. Analysis : The goal is to raise a security alarm before any strong adversary can damage the system integrity. The following principles are devised and observed in the system architecture to ensure such behavior. Inertia : By requiring substantial computational effort, make it expensive to impact the system Reduce predictability : By introducing randomness in choosing peers that can affect the validity of a copy, make it harder for the intruder to plan its attack Rate-limited : Bimodal behavior : In normal condition without an attack, it is expected that votes are bimodal in the sense that they agree with the initiator by landslides, or disagree by landslides (the initiator's copy is damaged). So, if this bimodal behavior is not observed, it is a sign that an attack is underway. And it is very difficult for an attacker to get around this defense. Because, he first needs to be in many peers' reference list and then start doing attacks (by bad votes), and it is hard to determine when to switch to the mode of attack, which gets even worse by a few factors not in control of an attacker due to the inherent randomization nature of the system. Comments : [C] : The way that the reference list is formed for each peer is very typical of the formation mechanism for any social network. Thus, it is exptected that the network of peers with their reference list forms the typical power-law network. So, there could be a few well-connected peers and other characteristics of social network would also hold. To think of a scenario of attacker and defense in this perspective might be interesting. For example, if an attacker can make use of a few well-connected hubs, would he be able to dodge the bimodal alarm checking mentioned above? From: Thadpong Pongthawornkamol Sent: Tuesday, October 05, 2004 10:23 AM To: Indranil Gupta Cc: Thadpong Pongthawornkamol Subject: 598ig review 10/05 P2P Apps (2) A Comparison of Overlay Routing and Multihoming Route Control The paper presented by Akella et al. give a different view of comparison between currently popular overlay routing protocols and traditional BGP routing protocols. Although several previous research yields a significant performance improvement by overlay protocols over BGP routing protocols. This paper presents a slightly modification of BGP routing protocol by adding end-to-end BGP routes via multiple ISP and implementing performance- and resilience- aware route control mechanisms, which result in multihoming route control mechanism. The paper then gives a comparison between overlay network protocol and multihoming route control protocol in terms of route-trip delay, throughput, and availability. The overlay routing and route control will be compared with respect to the flexibility of the network, described by degree k which indicates the number of ISPs available for routing in the network. Round-trip delay will be measured by small-sized HTTP downloads between each node in the network. Throughput will be measured by downloading 1-megabyte files across any pairs of nodes. A weigh directed graph then can be drawn with employments of optimistic and pessimistic loss calculation to ensure accuracies on the result. According to the result from the paper, the comparison between 1-multihoming and 1-overlay network provides that 1-Overlays gain a little performance improvement in both RTT and throughput. This result is expected because of the ability to choose intermediate path by overlay protocol. However, both k-multihoming and k-overlay protocol outperform 1-multihoming protocol in term of both RTT and throughput, especially when k is 3. K-multihoming scheme performs better than 1-overlay scheme. Finally, k-overlay schemes have marginal benefits over k-multihoming scheme (only 5-15% RTT improvement and 1-10% throughput improvement). An active measurement of path availability is then conducted by using periodical ping message between each nodes and using path availability analysis. According to the availability test, k-multihoming scheme yields significant improvement over traditional 1-multihoming scheme, and there is only little improvement on availability over k-multihoming scheme when k-overlay scheme is used. In conclusion, with the extended version of BGP routing called multihoming route control, a traditional BGP protocol can achieve the same level of performance, both latency and throughput, as the overlay network scheme. Moreover, Multihoming is relatively easier to deploy and use and does not violate traditional inter-domain policies, which makes it desirable to use in traditional network. However, it will be more appropriate for the paper to provide a complete detail of multihoming protocol, which is missing in this paper. On Transport Layer Support for Peer-to-Peer Networks A paper proposed by Hsieh and Sivakumar presents a new transport protocol which is designed specifically to suit the characteristics of peer-to-peer network applications. The paper states the need to establish a multipoint-to-point communication mechanism on transport communication layer from the view of source, destination, and content in peer to peer network. The paper then indicates some design principles to achieve such efficient multipoint-to-point connections. Finally, it gives an example of multipoint-to-point protocol. The paper explains the need to build multipoint-to-point communication mechanism support in transport layer from the view of entities in peer-to-peer network. From the perspective of the destination, the peer requesting for contents, the asymmetry in upload and download speed in the Internet raises the need for concurrent multiple sources transmission and multiple-sourced packet reordering scheme in destination-centric manner. From the perspective of the source peer, a multipoint-to-point connection can perform aggregated transmission, which will balance the load among multiple sources based on each source’s performance and bandwidth. From the view of the content, a certain level of integrity of content can be ensured by separating one transmission channel dedicated to loss discovery. The paper then draws some principles to design multipoint-to-point transmission protocol based on the needs from each entity in peer-to-peer network. Such principles are maintaining multiple states for multiple sources at the receiver peer, decoupling of functionalities from per-path basis to per transmission basis, using a scheduling algorithm based on bandwidth ratio among multiple sources, putting most mechanisms to receiver as receiver-driven operations. Finally, the R2CP (Radial Reception Control Protocol) is picked up as an example of multipoint-to-point protocol. R2CP is built on top of RCP (Reception Control Protocol), a TCP-friendly protocol transmission protocol which receiver controls the congestion and reliability. R2CP channel operates with multiple per-source RCP channels. Thus, each RCP channel takes care of per-source transmission control, while R2CP mechanisms perform aggregation and packet scheduling in destination node. In conclusion, this paper provides a set of basic principles to design multipoint-to-point transport protocol which is suitable for peer-to-peer applications. The paper also gives a clearer understanding by providing R2CP as a real example of such protocol. However, the paper is lacking of theoretical and practical results to ensure and prove the efficiency of such multipoint-to-point protocol. Preserving Peer Replicas By Rate-Limited Sampled Voting The paper by Maniatis et al. presents a novel mechanism built in LOCKSS academic publishing archival system to ensure integrity and security of journal archives stored for very long period of time. The paper presents the detail of the voting-based protocol and how it prevents content archives from being corrupted by powerful maligned hosts in the network. A simulation conducted in the paper reveal that only few probabilities that naturally-caused errors affect the integrity of stored contents and any maligned nodes need a significant amount of effort to silently modify any stored contents without triggering alarm system. Thus, the LOCKSS has a high probability of detecting an attack from any malicious nodes. LOCKSS digital preservation system is designed with many principles and considerations. For examples, it does not rely on cheap storage and rather use peer protocol to maintain the integrity of contents, or it does not use any long-term identifications or third-party reputations because any malicious nodes can exploit such policies to silently step into the system by using previously trusted information. The LOCKSS system provides mechanisms to collect, distribute, and preserve any electronic journals and documents available to any subscribed entities. The integrity and security of stored archives will be guaranteed by the poll method. Any nodes will periodically check its content by sending invitations to other nodes which maintain the same content to mutually make the consensus about the integrity of the inviter’s content. If most votes yield the integrity of the inviter’s content, the poll is done. However, if most votes yield the corruption of the inviter’s content, the poll requestor will request for a correct copy of corrupted content from any voters and perform rechecking again until the integrity is yielded. In the worst case, if merely equity between agreeing votes and disagreeing votes indicates an inconsistency in the system, which may be occurred from any malicious attempt to corrupt the content, the system will raise an alarm and leave all problem to human operators. LOCKSS applies several techniques based on the assumption of extremely powerful attackers to guarantee the consistency of the system. Such techniques are limiting the rate of voting, dynamically selecting voters, making voting protocol complicated to prevent spoofing and eavesdropping, using an alarm when any serious problems which require human intervention are occurred. In conclusion, the simulation given from the paper yields two outcomes: with the absence of malicious attacks, substantial rates of random damage at peers cause very low rate of false alarm, and the system can detect any malicious attempts to corrupt any contents with up to one-third of the subverted peer nodes. Additional to theoretical simulation results, the real implementation of LOCKSS has been available to prove that it can be used in real situations. From: Boris Capitanu Sent: Tuesday, October 05, 2004 10:06 AM To: Indranil Gupta Subject: cs598ig review 10/05 A Comparison of Overlay Routing and Multihoming Route Control ------------------------------------------------------------- In this paper the authors try to answer the question of whether overlay routing is required to achieving better end-to-end performance in the Internet, as opposed to choosing better routes at the BGP endpoints by leveraging the capability of multihoming route control. The authors pay close attention to the degree of multihoming at endpoints and whether the BGP routing choices are sufficient to allow the same performance as with overlay routing. To help them address these issues, the authors deploy a testbed comprised of 68 nodes scattered across 17 U.S. cities, connected to commercial ISPs of various sizes. To emulate multihoming, they select a few nodes in an area and connect them to different ISPs, each node being singly-homed. The initial comparison is done between 1-multihoming and 1-overlay through a single provider. Their data set consists of measured RTT of HTTP requests for small objects, and throughput measurements for downloads of objects of 1MB. Using these metrics the underlying loss rates between overlay hops is computed, which are then summed with the RTTs and use a model to compute the end-to-end overlay throughput. The results show that overlay routing can improve RTT times between 20 and 70 percent compared to using direct BGP paths. In terms of throughput, 1-overlays achieve 6-20% better performance than 1-multihoming. A series of other tests are then performed, including 1-multihoming vs. k-multihoming vs k-overlays, k-multihoming vs 1-overlays, k-multihoming vs k-overlays. The data shows that both k-multihoming and k-overlays offer significantly better RTT and throughput than 1-multihoming, and k-overlay (for k>3) is much better than 1-overlay. When comparing k-multihoming and 1-overlays, the results are far less dramatic - the performance advantage of overlays is vastly reduced when BGP is coupled with multihoming route control. The benefits of coupling multihoming with overlay routing offers marginal gains over using multihoming alone, as the k-overlay vs k-multihoming experiment shows. However, for a small fraction of transfers from a given city k-overlays have significantly better performance compared with k-multihoming. The analysis performed by the authors shows that these differences arise from the overlay's ability to avoid congested links and find shorter end-to-end paths compared to direct BGP paths. Overall, multihoming route control offers similar performance number compared with overlay routing. When overlays are coupled with multihoming, the performance gains are only 5-15% in RTT and 1-10% for throughput (compared with multihoming-BGP). There might be a problem with multihoming-BGP, however, since now routing tables will have to grow to account for the choice of different outgoing paths. On the other hand, the cost of deployment and policy-violation issues of overlays might give multihoming-BGP the edge in gaining widespread acceptance. On Transport Layer Support for Peer-to-Peer Networks ---------------------------------------------------- This paper talks about the need of transport layer support for peer-to-peer networks, showing how the current transport protocol (TCP) is inappropriate, and even undesirable, for effective data transfer in such networks. The characteristics of peer-to-peer networks are very different from those of traditional client-server networks; the latter favors point-to-point and point-to-multipoint connectivity, while the former is most effective in a multipoint-to-point scheme. The paper identifies that in most P2P networks studied the bottleneck occurs at the source due to the asynchrony of upload/download speeds of cable and DSL. Having multipoint-to-point support in the transport layer allows P2P clients to faster retrieve the data needed by leveraging the existence of multiple sources. This benefits both the requesting peer (better download or streaming performance) and the supplying peer (better load balancing in sharing a resource - lower average load on the sources). From the point of view of the content being transmitted, having multipoint-to-point connectivity implies better preservation of integrity since data is coming from multiple sources. The authors present RRCP (Radial Reception Control Protocol) that addresses the above points. The protocol is designed to maintain multiple states per session, one for each source path; to minimize the control overhead the transport layer functionalities are divided between the individual paths and the whole aggregate connection. To achieve in-sequence data delivery, packet scheduling is performed at the receiver since it has the best knowledge of how many sources and what bandwidth capabilities each has. This allows for minimal impact to the system in case of source failures. Problems: - no test data offered - overload in the network - corrupted data injected on purpose (malicious user) Preserving Peer Replicas by Rate-Limited Sampled Voting ------------------------------------------------------- In this paper the authors present a design for, and simulations of, a new peer-to-peer opinion poll protocol that improves on the limitations and weaknesses of LOCKSS. The LOCKSS system maintains persistent caches of the original URLs such that library users can access the same document even after it is no longer available there from the publisher. Specifically, participating libraries maintain persistent web caches that collect (crawl journal web sites to load newly published material), distribute (act as a limited proxy cache for library's local readers), and preserve (through participation in "opinion polls" with other caches that hold the same material to detect and repair damage). Voting is performed on large archival units (AUs) and if needed (as in case of lost poll) on a sequence of increasingly specific partial polls within the AU. The new opinion poll protocol also conducts polls to determine the authenticity of its data. It creates an inner circle of peers (hosts it has already discovered and it has invited to participate in the poll) and outer circle (chosen by the poll initiator from peers nominated by the inner circle voters). The outer circle is used to perform peer discovery. The outcome of the poll is decided solely on votes from the inner circle of peers. The voting mechanism includes a challenge-handshake protocol to authenticate the participants. If the voting on a particular AU is won by overwhelming majority (landslide win) the initiator is satisfied and waits until next poll; if the opposite occurs (landslide loss), it repairs its AU by copying from a voter that disagreed and then re-invoking the poll until a landslide win occurs (or the poll is deemed inconclusive if more than D repair attempts are made). If there is an inconclusive poll, an alarm is raised to call for human help. After a poll concluded successfully the initiator goes through a 4 step reference list update process that removes the peers on which the vote was based, as well as the disagreeing inner circle voters. Rate limiting is used to prevent rapid change to the system (based on their principle of inertia); since polls are called infrequently and autonomously by the loyal peers, an adversary is limited in its ability to attack. To further reduce the chances of a successful attack, the system obfuscates the protocol state by encrypting all but the first protocol message exchanged (using new symmetric keys for each poll and voter). The simulation results show that random storage faults and malicious attacks have very little impact on the system. Random damage at peers results in low rates of false alarms, while even with 1/3 of peers subverted the probability of irrecoverable damage is very low, and then increases gradually. From: Adeep Singh Cheema Sent: Tuesday, October 05, 2004 10:04 AM To: Indranil Gupta Cc: adeep.cheema@gmail.com Subject: 598ig review 10/05 09.28.2004 Cheema, Adeep S P2P Apps cheema@uiuc.edu A Comparison of Overlay Routing and Multihoming Route Control The Border Gateway Protocol has limitations and is responsible for poor performance with respect to transfers as well as failures. Overlays have been recently put to use to bypass BGP path selection for performance improvement and fault tolerance [RON]. The paper looks at intelligent control together with ISP multihoming as a means of achieving better performance and reliability. Overlay based routing scores over BGP in terms of greater route availability and because of advanced policies for route selection which optimize on metrics such as latency. The paper compares BGP with an overlay based routing scheme with multihoming – using several ISP links for transfers, on several metrics such as RTT, latency, throughput and availability. Testing was conduced with a setup involving 68 nodes spread over 17 cities connected to various differently sized ISP’s. This testbed was used to gather data on attributes such as latency, throughput and RTT. Results from testing showed that k-Multihoming and k-Overlay perform a lot better than 1-multihoming. Also, k-Multihoming and 1-Overlays have no significant difference due to the flexibility attained from multihoming. In a comparison of k-Overlay and k-Multihoming, k-Overlay performs better for most values of k. These differences in performance can be attributed to propagation delay and congestion improvement. Essentially overlay based routing was able to provide improved latency throughput etc. + Attempts to collect actual performance gain data on two widely accepted forms. - Some parts of the testing procedure could be more convincing. - Churn in overlays is expensive and its effect is not discussed. Transport Layer Support for P2P Systems The paper argues that using TCP as the transport layer in a P2P system in suboptimal since TCP does not recognize the existence of multiple data sources and due to the fact that peers in such a network do not behave like servers. It follows up by establishing design concepts for designing a new transport layer protocol for effective multipoint-to-point connections. Arguments are provided in favor of multipoint-to-point connections in P2P systems from a requesting or sending peer’s perspective. For a requesting peer, multipoint-to-point communications has great potential as it facilitates sharing and resource aggregation. From a supplying peers perspective, multipoint-to-point is fairly applicable in this scenario as well. Multipoint-to-point communication encourages nodes to participate. Several components determined to be central for a P2P transport protocol are: Mutiple States – maintaining several states proportional to the number of paths available for use in optimization. Decoupling of Functionalities: Dividing transport layer functionalities Packet Scheduling, Receiver Driven Operation. R2CP has been presented as a case study in this topic. - An elaborate communications protocol violates the end to end argument. Preserving Peer Replicas By Rate-Limited Sampled Voting A design is presented on rate limitation and intrusion detection as a minimum. It incorporates rate limiting as well as intrusion detection. These methods insure that brute force attacks have minimal chances of success. The protocol is intended to be scalable to a large number of documents. + The comprehensive set of design principles behind the system suggest that cheap storage is unreliable, there should be no long time secrets [security keys], use inertia instead of speed, avoid third parties, reduce predictability of the system, intrusion detection should be intrinsic and the adversary is strong. Any peer could be classified as maligned, loyal, damaged or healthy and many such peers form archival units for voting. The goal is to keep most of peers healthy in spite of attacks. + The voting protocol is fairly complex in its design and is intended to withstand adversary attacks. Votes are collected within the AU and some action is taken whenever by the source node whenever its peers disagree on vote outcome. + Adversaries can only harm peers when they call for a vote. This is the rate limiting principle in action and helps in reliability. The paper follows this up with an analysis on adversary characteristics and the kind of attacks they could foresee for the system. + A simulation was set up to experimentally check results and the tests agreed with the projected numbers on the low frequency of failures etc. - The trade of for this system is speed for reliability since a complicated procedure is required to check for maintenance. There are no speed constraints on the system however so that is acceptable. Future work: If performance is not a primary concern, it is reasonable to design complex protocols such that the probability of failure becomes insignificant. This principle can be applied to several situations. From: Vartika Bhandari Sent: Tuesday, October 05, 2004 10:00 AM To: Indranil Gupta Subject: 598ig review 10/05 A Comparison of Overlay Routing and Multi-Homing Route Control This paper considers overlay routing and multi-homing route control as alternatives to default routing. Both provide more flexibility than default Internet routes. However the intent of the authors is to determine whether there is a significant improvement obtainable using overlays as compared to multi-homed route control. The authors point out that overlay routing also needs multi-homing, else given the way BGP works, only one route would be available through a given ISP. The comparison is performed between k-overlays and k-multihoming where k refers to the number of ISP connections. The authors report that k-multihoming provides throughput and latency characteristics fairly close to what k-overlays provide. Similarly while overlays provide greater path availability, the difference is not very large. Thus this seems to indicate that retaining the regular routing structure but allowing for alternatve paths via multi-homing might be an alternative to widespread overlay routing deployment. However there are a few caveats. Some of these are pointed out by the authors themselves e.g. the cost/overhead of route-selection/overlay-deployment has not been factored in, increase in routing table size due to multi-homing is not considered etc. Besides, another factor that they seem not to have considered is that BGP is often prone to delayed convergence problems and multi-homed route selection would also suffer from it (there could be cases where a link outage in the backbone affects all the available ISP connections). Overlays might be more effective as they can maintain and use additional information e.g. private peering that is not otherwise advertised (ref. RON paper). On Transport Layer Support for Peer-to-Peer Networks This paper makes a case for multipoint-to-point communication in peer-to-peer networks using a receiver-centric transport protocol. The paper essentially uses an earlier proposed protocol (by the same authors) viz. Radial RCP (Mobicom 2003) and espouses its utility in the P2P case. The earlier proposal had been made in the context of a wired-cum-wireless scenario with the last link being wireless. A receiver-centric transport protocol named RCP was proposed which transposes congestion-control and reliability functionality from sender to receiver. This allows for quick and unambiguous response to conditions observed at the wireless link. Radial RCP is a multi-state extension of RCP initially proposed for bandwidth aggregation and builds upon RCP and pTCP (another earlier proposal by the same authors). The idea is to have an encapsulating entity R2CP that handles reliability and flow control while individual RCP pipes handle congestion control. Intelligent striping of data is done to avoid head-of-line blocking. The authors contend that P2P networks exhibit similar characteristics as the end-users are often connected via bottleneck links e.g. dial-up or DSL. However there is actually a major difference in P2P systems: the sender of data is also generally connected via a bottleneck link (after all the sender is also a peer). RCP and R2CP are designed for the specific case where the link at the receiver's end is the crucial one, and therefore receiver-centricity is a good option. They may not really work as well when links at both end-points are problem-spots. RCP got around the issue by proposing a generic framework wherein the protocol would behave like TCP if the sender is a mobile host and like RCP when the receiver is a mobile host. However, when both sender and receiver are connected to the network by a bottleneck link (be it DSL, dialup, or anything else), it isn't clear where functionality should reside. Besides, RCP/R2CP have security implications too. Apart from the possibility of peers greedily opening too many connections (which the authors themselves mention), RCP allows for even a single connection overloading the sender (senders passively hand out data, so a receiver could inflate its congestion window artifically and even request each sequence number n times just to tie down the sender). Preserving Peer Replicas by Rate-limited Sampled Voting This paper describes a digital preservation system that attempts to ensure availability and immutability of digital documents in the face of persistent adversery attacks. The key objective is to avoid change, and a notion of rate-limiting is adopted to ensure that any changes are gradual enough for them to get noticed before too much damage is done. An opinion poll protocol named LOCKSS is designed. A peer holding a copy of an archival unit calls for a poll at a rate greater than the expected rate of damage. Each poll involves a subset of nodes comparing hashes, and nodes that seem to have anomalous copies obtain a replacement. The subset of nodes used is subjected to churning to avoid deterministic poisoning by an adversary. LOCKSS tends to avoid any long-term secrets in the form of cryptographic keys. While this simplifies matters by not requiring key management and security, it opens the system up to attacks like source spoofing (since identities may not be authenticated). This could actually be a potent problem. In fact, even if an adversary is unable to hijack a session by spoofing, it is able to discredit an honest peer, and that by itself is a form of attack. In my opinion it would be a good idea to use public-key cryptography for message authentication. Since private keys never get sent on the network, the adversary cannot spoof unless it manages to compromise a peer's system and get the private key, and the probability of that happening is fairly low in general, as compared to attacks where the adversary is stationed in the network. From: Michael Treaster [treaster@cs.uiuc.edu] Sent: Tuesday, October 05, 2004 9:58 AM To: Indranil Gupta Subject: 598ig review 10/05 P2P Apps (2) A Comparison of Overlay Routing and Multihoming Route Control This is a data collection paper. It proposes no solution or new technologies, but instead it studies existing systems in order to make an argument. The authors observed that overlay-based routing typically outperformed BGP-based routing by a considerable margin, but they hypothesized that BGP routing might be more competitive when enhanced with a multihoming approach, They collected real data from the real Internet to compare the performance of the overlay approach and the multihoming approach. This data is used to argue that although overlay routing offers better performance than multihoming, but that the multihoming succeeds in making BGP competitive with overlay techniques in both performance and reliability. It is important to note that the data in this paper was collected from the real Internet, rather than from the simulators that are used in many distributed systems projects. This is especially important in this paper, since this paper's primary contribution is the data itself. The node locations were well-distributed, being scattered across the continental United States. It would have been more impressive to see a global distribution of nodes, but the US-only distribution is adequate. Considering that this paper was all about the data, it is unfortunate that the presentation of the data was not clearer. The data plots were small, and it often was unclear what they were showing due to poor labeling decisions and an excessive number of trend lines. On Transport Layer Support for Peer-to-Peer Networks This paper attempts to argue that TCP is inadequate for peer-to-peer network communication due to its end-to-end, point-to-point nature. It proceeds to present four design requirements for a P2P-oriented protocol: - Maintain one state per sender/source/path, but have multiple sources for each connection. - Decouple individual path functionalities and aggregate connection functionalities. - Optimize Packet scheduling for multipoint-to-point communication. - Provide receiver-oriented control over the communication. Finally, the R2CP protocol is presented. This protocol is claimed to fulfill the four requirements described above. This paper is poorly done. Although the premise of a P2P-oriented transport level protocol might have merit, this paper fails to convince the reader of this. Section 2 presents the argument that such a protocol is required. Although it promises that a new protocol would provide improved usage of available bandwidth, it fails to explain how the protocol would overcome the social issues of users leeching from P2P networks without contributing anything of their own. This section also explains how there are a variety of existing transport layer protocols such that a spectrum of reliability services can be provided, but it goes on to imply that a single P2P protocol would be adequate for all P2P applications. It also suggests that implementing video streaming with out-of-band loss recovery is difficult using TCP, but it is somehow magically easy with a P2P transport protocol. Finally, the authors make no compelling argument why TCP or some other existing protocol cannot be used to construct a higher level multipoint-to-point protocol. Section 3 presents the proposed requirements for the P2P transport protocol. Although some justification is given for each requirement, more space is spent describing what the requirement is than why it is necessary. Furthermore, no attempt is made to explain why these requirements are more important than other requirements that could be specified. The packet scheduling requirement is especially interesting, since the description of this requirement proceeds to explain why there has been little success implementing this feature in previous work. Section 4 presents the R2CP protocol. It basically goes back through the requirements presented in section 3 and very briefly describes how it was implemented. Unfortunately, with less than a page dedicated to this explanation it is difficult to get any understanding of how the protocol works. The reader is referred to a previous paper to get more technical information on the protocol implementation. It is unclear what this paper contributes that the previous paper did not address. Preserving Peer Replicas By Rate-Limited Sampled Voting This paper presents a peer-to-peer long-term storage repository solution. The basic premise is to massively replicate data such that in the event that any copy of the data is lost or damaged, it can be repaired from a remote source. Most of the paper is dedicated to describing the voting mechanism for determining whether or not data is damaged and how it should be repaired. The highest emphasis is placed on security in the unusual environment the paper proposes. Specifically, this environment is distributed, consists of low-cost, unreliable hardware, and will exist over the course of many decades. There is a significant amount of research in progress today concerning storage security, which is what this paper is trying to address. Most storage security researchers are attempting to solve the problem using special hardware devices oriented to the task. In this situation, it is not clear why one would prefer a complicated P2P solution when several mirrored write-once devices could probably be constructed into an adequate solution. One specific weak point of the P2P solution is its reliance on a skilled system administrator to diagnose and repair attacks. One premise of the system is that it is supposed to be low maintenance, and indeed, most of the time it runs itself. Due to the infrequency of catastrophic security threats, it is unlikely that most libraries would keep on-hand a security expert qualified to handle the types of attacks the paper describes. From: William Conner [wconner@glsn33.ews.uiuc.edu] Sent: Tuesday, October 05, 2004 7:51 AM To: Indranil Gupta Subject: 598ig review 10/05 A COMPARISON OF OVERLAY ROUTING AND MULTIHOMING ROUTE CONTROL This paper proposes the use of multihoming route control as an alternative to overlay routing. As many overlay routing papers (such as RON) have pointed out, BGP imposes limits on Internet routing that often cause failures that require minutes before repair and poor performance end-to-end. One observation made by the authors of this paper is that end hosts can have as many paths to destinations as they have ISP connections. If hosts monitor these available paths, then the best one can be chosen. Based on this observation, they study whether hosts having more than one ISP can obtain enough BGP route choices to be as good as the overlay routing schemes proposed in the literature. Multihoming route control is an end-point-based meachanism that performs intelligent route control of the BGP paths provided by their ISPs. Since the overlay routing papers only considered networks with a single ISP, this paper studies the potential benefits of multihoming. The results of their experiments lead to many interesting findings. One of the more interesting results is that a node that uses k-multihoming (where increasing k beyond 3 usually provides negligible improvement in RTT or throughput) can come close to the same performance as overlay routing. This would imply that current BGP implementations can be utilized to provide good performance if a host is multihomed without resorting to overlay routing which would only provide marginal improvement. Cooperation between ISPs could improve BGP routes even further and thus improve multihoming route control. A major problem with this approach is that it would require a host to have multiple ISPs. Depending on the rates that ISPs charge organizations, this could be very cost prohibitive since an organization would have its costs increase threefold in order to use 3-multihoming. Also, even though BGP routes could improve with cooperating ISPs, some sort of incentive mechanism would need to be proposed (if none exists) in order to get ISPs to cooperate. ON TRANSPORT LAYER SUPPORT FOR PEER-TO-PEER NETWORKS This paper addresses the transport layer services required for applications running over peer-to-peer networks. The authors note that TCP is inappropriate for most peer-to-peer applications and that the transport layer should support multipoint-to-point connections. Such support should also address the fact that most peers lack server-like qualities (e.g., large capacity). Since many peer-to-peer applications allow multiple replicas of content, there is an opportunity for performance improvement in these applications since a peer can download an object from several peers in parallel. Due to the asymmetry amongst hosts in peer-to-peer networks, many peers always choose to download from the peers with the most bandwidth when only point-to-point connections are possible. This could create a bottleneck at these peers and exhaust their resources, thus discouraging them from participating fully. Multipoint-to-point connections would address fairness since peers with low bandwidth connections can contribute to the system and relieve some of the burden on peers with high bandwidth connections. Some challenges of multipoint-to-point connections are the resequencing of data from multiple sources and fault tolerance when peers leave. Some key design elements are multiple states for multiple sources, decoupling functionality of individual paths from the aggregate connection, packet scheduling from multiple sources, and receiver-driven operation. Although this paper motivates a need for transport layer services in peer-to-peer networks, it does not really offer a proposal for a novel solution. It basically identifies key design elements and a wireless protocol that could serve as an example. Future work would definitely include the design of a specific multipoint-to-point transport layer protocol that would be suitable for peer-to-peer networks (which are often wireline). PRESERVING PEER REPLICAS BY RATE-LIMITED SAMPLED VOTING This paper presents a new protocol for peer-to-peer opinion polling that is both scalable and resilient to attack. Such a protocol is useful in distributed digital preservation. Digital preservation systems, such as LOCKSS (which has a peer-to-peer design), want to preserve access to journals and other archives on the web on a time scale of many decades. Such systems must avoid long term secrets like encryption keys and resist random failures and malicious attacks for a long period of time. The opinion polls help achieve this goal by getting a sample of peers to vote on hash of a specified part of the content (e.g., a year's run of a journal called an archival unit). By avoiding a reputation-based scheme, attackers cannot get an extra advantage by corrupting highly reputable peers. The protocol works by having a peer call a poll on a small subset of peers (which come from a reference list of recently encountered peers). Each of the other peers will then compute a fresh digest of the archival unit in question and submit that digest as their vote. The outcome has three possibilities: landslide win, landslide loss, and inconclusive poll. If the result of the poll is a landslide win where the vast majority of peers' digests agree with the digest of the initiator, then the initiator is satisfied and does nothing. If the result of the poll is a landslide loss where the vast majority of peers' digests disagree with the digest of the initiator, then the intiator will get a good copy of the archival unit from a peer with a correct digest and re-evaluate votes. If the poll is inconclusive (i.e., neither landslide win nor loss), then an alarm is raised. Using rate limitation, the system is designed such that an adversary would have to spend an extraordinary amount of computational effort in order to corrupt enough peers without being detected such that those peers can influence the outcomes of polls. One problem with the system is that it requires an out-of-band relationship with an existing member in order for another peer to initialize itself once it joins the system. There should be some mechanism (similar to Gnutella and many other p2p systems) for a peer to join the system without having such an out-of-band relationship. Also, this protocol would be unsuitable for any peer-to-peer application that cares about performance since peers are rate-limited and perform extra amounts of computation simply to discourage attackers (i.e., unnecessary CPU cycles are wasted in this effort and some applications can't affort that waste). From: Jigar Harshad Doshi Sent: Tuesday, October 05, 2004 3:09 AM To: Indranil Gupta Subject: cs598ig review 10/05 A comparison of overlay routing and Multihoming route control This paper attempts to analyze why peer to peer overlay networks like RONS have higher resiliency and provide better performance than BGP and routing schemes on the internet. It speculates that the end-to-end performance of traditional internet over BGP can be improved by multihoming at the source end and then investigates this claim. A number of experiments are carried out comparing the performance of normal BGP with and without multihoming and overlay networks with and without multihoming. The measurement testbed is a network that is distributed across the united states. The authors have carefully avoided the use of the internet 2 infrastructure as it would skew the results. Only two stats are collected namely round trip time and throughput. Since it may not be always possible to calculate this directly, indirect metrics may be used. In the study 1 overlays are shown to be better than 1 multihomed networks as expected. This is the basis of RON. However the authors then repeat the experiment comparing 1 multihoming to k multihoming and overlays which show that 1 multihoming performs the poorest. Also the performance of k multihoming is shown to be better than 1 overlays thus reinforcing the authors argument. K multihoming however does not do as well as k overlays. But the performance gain of overlays is not that persuasive. The authors then try to analyze why overlay networks performs as well as they do. Their finding is that a majority of the RTT improvements are due to a reduction in propagation delay. And the advantages of overlay routing are due to shorter end to end paths. The big performance improvements are due to routing around congested links. The authors’ primary argument is that multihoming is very easy to implement and is as simple as subscribing to multiple isp’s. On the other hand RONS would require a whole network to be set up. Thus they feel that using k multihoming can give performance comparable to an overlay network and still be easy to implement. Also they would avoid some of the problems with RONs like selfish behaviour and policy violations. Preserving Peer replicas by rate limited sampled voting This paper tries to build a distributed cache for online journal libraries. Such a system is designed due to the transience of digital data. Libraries and information store houses will now have to ensure that such digital data is available in thefuture. To do so the authors propose a collaborative peer to peer web cache. The proposed system is low budget and trades speed of availability of information for security and low cost access. The ultimate success of such a system can only be known after decades of operation but a decent solution is provided. The problem is such that any solution would require to be distributed and secure. Thus the system is designed such that intrusion detection is core and not something layered on top of it. Also the adversary is assumed to be very strong. To do this an opinion poll based system is proposed to verify the authenticity of any data unit. The participants of the opinion poll are classified into two main types and their replies are used in order to verify the authenticity of the data. These lists are dynamic and allow movement from one into another. The main contribution of LOCKSS is a completely new notion of security by making the cost of the attack higher rather than relying on notion of security and shared keys. It also takes into account the churn which is so prevalent in peer to peer systems. The system is also shown to degrade gracefully and keep a high level of reliability. On Transport Layer support for Peer to peer Systems: Peer to peer systems as implemented today are overlays over the normal internet hierarchy. This paper argues the case for a special transport protocol for pere to peer systems. This is primarily based on the argument that in a peer to peer network a node should have multiple concurrent connections even if it is accessing a single resources. A part of this stems from the way peer to peer systems are structured. With most of the nodes being at the periphery of the internet with asymmetrical links and thus contribute less to the upload. The traditional methods around this problem has been either not using multiple connections at all. This can be done by choosing only higher bandwidth nodes as hosts or ignoring the problem altogether. Systems like Kazaa use application layer semantics to reorganize the file. A Transport layer solution to this problem would be more efficient. Also it would allow more resiliency and fault tolerance. Thus the authors propose design guidelines for any solution. The transmission protocol should have multiple TCB’s for each connection within each TCP connection. It advocates decoupling of functionalities and receiver driven operation. The authors then propose R2CP which uses these guidelines in order to build a competitive protocol. Questions remain although to its applicability to real p2p systems. P2p systems have succeeded because of their independence of the lower layers. Implementing such a system would mostly have to be done at the application layer and this would lead to inefficient solutions. Also it has to be seen how systems like RON perform with a transport layer like R2CP operating. From: Zahid Anwar Sent: Tuesday, October 05, 2004 2:38 AM To: Indranil Gupta Subject: 598ig review 10/05 Zahid Anwar NetId: anwar CS598IG Review On Transport layer Support for p2p ---------------------------------------- Summary ------- The paper argues in favor of a multipoint-to-point transport level protocol as apposed to simple point-to-point protocol like vanilla tcp for p2p networks. The authors build their case on the argument that from the point of view of the destination having multiple sources can help achieve better resource aggregation and fault tolerance. This also helps deal with the problems of having uplink bandwidths significantly lower than downstream ones and that of choosing the 'best' source to request data. For the source this approach results in lower average load. As far as content is concerned you get the ability to preserve better integrity and 'out-of-band' loss recovery for timely data. A transport protocol called R2CP is described that mirrors tcp congestion control and reliability techniques but does it at the receiver rather than the sender. It keeps multiple states and does congestion on a per-path basis. Strengths --------- + Out-of-order arrivals at the destination due to packets traversing multiple paths do not trigger unnecessary window cutdown using a multi-state TCP Weaknesses ---------- - Issues of potential server overload and network overload due to the greedy use of multi point-to-point connections needs to be addressed Future work ----------- - There is a need for consensus on a sound fairness model to avoid network overload Review Preserving Peer Replicas By Rate-Limited Sampled Voting -------------------------------------------------------------- Summary ------- This paper improves on the LOCKSS project which is a peer-to-peer system designed to preserve access to journals and other archival information published on the web. LOCKSS aims to achieve long term scalability, without centralized control and resist random failures and deliberate attacks. To achieve these goals it makes assumptions that storage is unreliable, 3rd path repudiation is problematic (vulnerable to slander and subversion and can cash in a history of good behavior), adversaries are strong and that there is no such thing as long-term secrets. The system works as follows. Libraries use persistent web caches by crawling journal web sites and distributing content to local readers and preserve content by cooperating with other caches. Opinion polls based on independently obtained copies are an important part of the system used to provide content authenticity and integrity. Peers vote on large archived units (AUs). If a peer finds that its AU is damaged it repairs it by participating peers who only help it if the replica has participated in the past. This technique prevents free-loading and theft. This paper builds on top of this an algorithm that says that a peer invites a small subset of the peers it has recently encountered and each computes a fresh digest of its AU. If the caller of the poll receives votes that overwhelmingly agree with its own version then it does nothing otherwise it asks for a copy to repair its own and votes again. If the result of the poll is neither a landslide win nor a landslide loss, then the caller raises an alarm to attract human attention to the situation. Membership for voting is determined by an 'inner circle' that decides on poll outcome and a outer circle that is nominated by the inner circle. Strengths --------- + Use of a java based discrete event simulator, simulating a 30 year period of use shows a Low rate of false alarms with up to 1/3 of peers subverted and that the system degrades gracefully + Attack by adversaries made difficult. Firstly he needs to wait for an initiator to call for votes then it needs to go through many rounds of voting without triggering an alarm and finally has to expend effort to maintain the foothold in the reference list Weaknesses ---------- - A large frequency of attacks may require a lot of human intervention. Review A Comparison of Overlay Routing and Multihoming Route Control -------------------------------------------------------------------- Summary ------- Recent research has shown that the use of overlay routing makes better use of the underlying Internet connectivity than the current BGP-based system allows. On the other hand BGP routing has the benefit of additional access to end-to-end BGP routes via ISP multihoming, and implementation of performance and resilience-aware route control mechanisms to dynamically select among multiple BGP routes. This paper compares the relative benefits of overlay routing and intelligent route control and draws the conclusion that Multihoming route control can offer performance similar to overlay routing. k-multihoming is defined as a end node having access to multiple ISPs and emulated by a virtual node composed of multiple physical 1-multihoming nodes in the same city. A k-overlay is the same as k-multihoming, but paths can use additional nodes. The study in the paper states that overlays employed in conjunction with multihoming to 3 ISPs offer only about 5–15% better RTTs and 1–10% better throughput than route control in conjunction with multihoming to three ISPs. In fact, when overlays are constrained to a single first-hop ISP, they provide inferior performance relative to route control. The slightly better RTT performance of overlays comes primarily from their ability to select shorter end-to-end routes. Also, the performance gap between overlays and route control can be further reduced if, for example, ISPs implement mutually cooperative peering policies such as late-exit. While route control cannot offer the near perfect resilience of overlays, it can eliminate almost all observed failures on end-to-end paths. The path diversity offered by multihoming can improve fault tolerance of end-to-end paths by two orders of magnitude relative to the direct BGP path. From: Mayssam Sayyadian Sent: Tuesday, October 05, 2004 2:38 AM To: Indranil Gupta Subject: cs598ig review 10/5 Mayssam Sayyadian NetId: sayyadia CS598ig - 10/5/2004 A comparison of overlay routing and multihoming route control A. Akella et al SIGCOMM 2004 This paper investigates the two choice of routing: BGP and Overlay routing. The background belief is that overlay routing can improve performance over BGP, between a limited number of nodes and overlay routing protocols are much more flexible. The basic assumption of previous overlay studies is that end nodes subscribe to a single ISP. The paper points out that multihoming allows end-network sites to schedule their transfers over multiple ISPs (route control). The basic question this paper deals with is how much benefit does overlay routing provide over BGP, when multihoming and route control are considered ? To answer this question, round trip time and throughput metrics are used. The paper then defines k-multihoming this way: End node has access to multiple ISPs, emulated by a virtual node composed of multiple physical 1-multihoming nodes in the same city. K-overlay is defined the same but paths can use additional nodes. The paper then lays out experiments comparing 1-overlay, k-overlay, k-multihoping, and 1-multihoping. The testbed has 68 nodes in 17 US cities and for the experiments it is assumed that we'd have instantaneous knowledge about the performance and availability of routes via each of its ISPs or overlay paths. Also it's mentioned that for throughput maximizing overlay paths, only paths comprised of at most two overlay hops are considered. Comparing 1-Multihoming vs. 1-Overlays, it's shown through experiments that 1-overlays offer better round trip time (33%) and throughput (15%). Also in a large fraction of measurements (46%) indirect paths offered better RTT performance than direct path. Comparing 1-Multihoming vs. k-Multihoming and k-Overlays, the experiments show that both k-multihoming and k-overlay routing offer significantly better performance than 1-multihoming and finally k-overlay with (k >=3 ) performs better than 1-overlay (5-20% RTT). The final comparison is between k-multihoming and k-overlays. It's shown that k-overlays offer marginal benefits over k-multihoming alone but surprisingly only a small fraction of transfers showed significantly better performance with k-overlays rather than k-multihoming. The paper has many strong points which could be enumerated as: interesting subject, good and well designed experiments and it favors a good discussion about performance difference. According to the paper large improvements performance is mainly due to avoiding congestion (small difference in propagation delay) and the diagrams show that most of the time improvement is due to finding physically shorter paths. Finally there is an experiment about resiliency to path failures. The paper has much to offer and many key questions are highlighted through this research. The most important message probably could be the pros and cons of overlays vs. multihoming and wether they should be considered as complementary or competing. A very promising future work as mentioned in the paper is studying future changes to BGP that may further improve standard Internet routing performance relative to overlays. The main drawback maybe is the question if the experiments are scaable to the Internet or not. On transport layer support for peer to peer networks, H-Y. Hsieh et al, IPTPS 2004. This paper takes a new and interesting approach in augmenting the transport layer protocols for p2p networks. Specifically in this paper In this paper, the focus is on embedding the support for multipoint-to-point connections to address the problem of sources in peer-to-peer networks lacking serverlike properties in terms of capacity and availability. The paper outlines key elements in designing a new transport protocol for supporting multipoint-to-point connections, and presents a case study for a multipointto-point transport protocol that puts together these design elements in practice. The motivation is interesting and the papers points out some characteristics of p2p networks that result in feeling the neef for disigning a new trasnport layer protocol. Among these motivations we can mention the fact that in many cases there are multiple sources with replicated content, and there are sources with non server like behaviour (as is the case in tcp). Also the new design should favor multipoint to multipoint connections as well as p2p and p2multipoint connections according to the intrinsics of p2p networks. The paper then discusses and points out the design issues for transport protocol design, issues such as: in-sequence data delivery semantics, multiple possible states and related issues, decoupling of functionalities, packet scheduling, and reciever centric operations. Finally there is a case study, R2CP (Radial reception control protocol). In general this problem is a novel and promising research direction (working on p2p and protocols in transport layer) and has not been discussed before so the paper favors a good subject. The design issues discussed are all suitable but there are much remained for future study such as: peer selection, load balancing, trustworthy peers, selfish peers, fairness of the model, and deploymenr issues. Also it should be considered that the protocol should be adaptable or designed for domains other than internet as well ( such as mobile p2p networks, etc.). Preserving peer replicas by rate-limited sampled voting, P. Maniatis et al, SOSP 2003 This paper lays out the LOCKSS system that has been developed and deployed over web and aims to preserving access to archival information published on the Web such as journals, etc and also addresses the problems such as scalability and security. The system has a p2p architecrue, consisting of a large number of independent, low-cost, persistent web caches that cooperate to detect and repair damage to their content by voting in “opinion polls.” Besides building the system another contribution of the paper is presenting a design and simulations of a protocol for voting in systems of this kind by incorporating rate limitation and intrusion detection to ensure that even some very powerful adversaries attacking over many years have only a small probability of causing irrecoverable damage before being detected. The key idea behind LOCKSS is very original and simple: acquire lots of copies of the document, distribute them around the world, lend (or copy) them when acess is requested. As a design principle the paper argues that no long-term secret could be exploited meaning that methods like encryption etc. require storage and are effectively difficult (if possible) for auditing, replication, repair, etc. The existing LOCKSS system works as follows: 1. Take and use persistent web caches: crawl to journal websites, distribute to local readers, preserve by cooperating with other caches. 2. Use "opinion polls" in a p2p network to compare the signature (hash values) of specified part of the content. The opinion polls provides content authority and integrity because of obtaiting copies are done independantly. Peers vote on a large achive units, and a replica is repaired only if it was participated in past. The key (and reasonable) assumption here is that the polling rate is much more than random damage rate (but this should have been demonstrated). The results from simulation show a low rate of false alarms. Also it's experimented that ith up to 1/3 of peers subverted, a stealth adversary fails, with more than 35% subverted nodes there is a 12% of irrecoverable damage after 3.2 years of effort. And runs with low subversion levels don't achieve foothold ratios of 40% or more in 20 years. Although the paper discussed preserving peer replicas by sampled voting but it seems to me that all the experiments and discussion is about journals and text documents. The same approach might be applicable in replication of multimedia data and in this case the adversary coudl be any scenario leading to loosing the quality and this sampled voting may be able to help. Another promising future work could be how to use the idea of sampled voting in data replication over mobile devices. It is the case that nowadays many applications for mobile devices like PDAs and mobiles have been started (e.g. to guide tourists) and different approches for replication of mobile, p2p data sources have been tested but this approach could be very interesting to investigate. From: Dennis Y Chi Sent: Tuesday, October 05, 2004 12:25 AM To: Indranil Gupta Subject: 598ig review 10/05 Dennis Chi 10/5/04 P2P Apps (2) A Comparison of Overlay Routing and Multihoming Route Control Overlay networks, such as RON, have been developed to bypass BGP’s routing, but these networks may violate routing policies and may be difficult to deploy. This paper compares overlay routing to multihoming route control (MRC) to determine whether overlay routing is necessary to improve performance and fault tolerance. MRC involves a multihomed end-network choosing the best route based on different performance metrics. The authors use the Akamai content distribution network with 68 nodes in the U.S. to compare RTT and throughput with a varying number of ISPs available to the end-network. The results show that 1-overlays provide significantly better RTT and throughput than 1-multihoming, mainly because overlays use indirect paths. As the number of ISPs increases, the RTT and throughput advantages of 1-overlays over k-multihoming are significantly reduced, and in some cases eliminated. The results also show that k-overlays provide marginal benefits over k-multihoming, and become less significant as k increases. Also, the authors show that multihoming improves path availability, and that 3-multihoming achieves availability within 0.10% of 3-overlay. The paper provides sufficient data to show that MRC can provide comparable (but not better) results to overlay routing, but MRC has similar limitations as overlay routing. The paper discusses the similar cost and deployment issues, and both methods will incur additional overhead when probing and monitoring paths. Although the authors show that overlay routing violated inter-domain policy frequently, earlier results show that 3-overlay routing only used an indirect path 8% of the time, and 1-overlay only 17-23%. In addition, the MRC method depends on assumptions that may not be practical, and the use of singly-homed nodes connected to different ISPs to simulate multihomed nodes may not provide accurate results. On Transport Layer Support for Peer-to-Peer Networks Current peer-to-peer (p2p) applications use TCP connections for data transmission, but TCP may not be sufficient because of the specific properties of p2p networks. This paper proposes the design of a new transport layer protocol that supports multipoint-to-point connections (mp2p) to improve performance for the hosts and the data content. Sources will have better load balancing, the destination peer can better aggregate resources and tolerate poor performing or unavailable sources, and the integrity of the content will most likely improve as it is replicated throughout the network. Transfer protocols (TPs) must be designed appropriately to deal with mp2p. Since multiple sources will be traversing different paths at different rates, TPs should maintain a separate state for each point-to-point connection, and the states should be coordinated be a main engine. The individual states will determine how data is transmitted (i.e. congestion control). The main engine will provide functionality for the aggregate connection, such as reliability and buffer management, controlling what data each state will request. The packet scheduler needs to deal with the differences in bandwidth and latency of each path, and allow sources to join and leave. Also, the TP should be receiver-driven, in which the receiver controls all aspects of the data transfer, and the sources simply respond. The authors present a transfer protocol, R2CP (Radial Reception Control Protocol), which implements the design elements discussed in the paper. The paper is interesting because many p2p applications, such as Kazaa or BitTorrent, rely on mp2p, so it makes sense to consider moving the functionality from the application layer to the transport layer to help development and interoperability. But the design may have some problems. It still has the same problems as existing p2p systems because certain high-quality sources can still be overloaded. Maintaining multiple states may be expensive if a user is transferring a large number of files from many sources. Also, it would be interesting to see just how TCP-friendly RCP is, because it does not seem like congestion control will work if it is only performed at the receiver side. Future work could be done in creating specific RCP components for different aspects of the aggregate connection, such as throughput or loss. Preserving Peer Replicas by Rate-Limited Sampled Voting Distributed digital preservation systems are unusual because they must use cheap and reliable storage, maintain no long-term secrets, avoid third-party reputation, reduce predictability, and use intrinsic detection of strong adversaries to resist failures and attacks for decades. They must also use rate limiting to prevent change as much as possible. This paper presents a new voting protocol for the LOCKSS program, which consists of many persistent web caches that collect archival units (AUs) from journal websites, distribute data to readers, and preserve data by detecting and repairing damage. Peers maintain a reference list for each AU it stores, and a friends list. Peers initiate opinion pools for their AUs as infrequently as possible (rate limiting), but more frequently than the rate of undetected random damage. The initiator contacts a random subset of peers from the AU’s reference list (inner circle), and those peers will reply with a hash of their AU if they want to vote. If the votes overwhelmingly disagree, then the initiator will repair its AU by contacting a voter. Once a poll is completed, the initiator updates the reference list with peers from the outer circle (subset of peers nominated by inner circle) and the friends list to reduce the effect of malign peers. Note that this protocol utilizes a memory-bound function mechanism, making it costly and time-consuming for any peer to participate. The paper focuses on dealing with adversaries that try to replace protected content with bad content without being detected. Based on simulation results of 1000 peers, the opinion poll protocol rarely produces false alarms, and sustains minimal damage even when an adversary controls one-third of the peers. This paper is very interesting because it is the first type of p2p storage system presented in this class that seems to have practical uses, even though it has unusual and specific properties. Rate limiting and avoiding long-term secrets and third-party reputation seem to be effective design principles. But one of the problems with the protocol is the possibility of malicious peer operators. Operators are in charge of bootstrapping the peer with its friend list, which could be a list of malign peers. Therefore, if the peer fetches a journal entry and initiates a poll with its friends, all the friends will disagree, and the peer will repair its copy with a bad one from one of its friends. Also, nuisance could be a difficult problem to handle, because any node can continually send messages to peers to force them to raise alarms. From: Pei-Hsi Chen Sent: Tuesday, October 05, 2004 12:24 AM To: Indranil Gupta Subject: 598ig review 10/05 --On Transport Layer Support for Peer-to-Peer Networks This paper argues that the unique characteristics of peer-to- peer networks render TCP which is designed for a unicast between a server and a client inappropriate for effective data transport. Therefore, it presents transport layer support for facilitating multipoint-to-point connections in peer-to-peer networks. It argues that a transport layer protocol supporting multipoint-to-point connections can address problems such as peer transience, redundant data transmitted, and then mask such artifacts in the peer-to-peer network from the application. However, this approach challenges the end-to- end arguments. For example, in order to download a file from multiple sources concurrently, data should not be transmitted redundantly across multiple sources. This requires application layer’s knowledge about the file content. Therefore, even though the underlying transport layer can support to deal with it, it still can’t reduce much the implementation complexities of application layer. Moreover, what are proposed for transport layer should also be built in application layer. For example, on the issue of reliable content replication, the solution proposed in this paper, opening one more source dedicated to loss recovery in the transport layer, can be implemented in application layer as well. I can’t see very strong benefits of transport layer support for multipoint-point connections. --Preserving Peer Replicas By Tate-Limited Sampled Voting The KOCKSS is a distributed digital preservation system. It has been developed for preserving access to journals and archival information published on the Web. It deploys a large number of independent, low-cost, persistent web caches that cooperate to detect and repair damage by voting in “opinion polls”. However, it has scaling and attack resistance problems. Therefore, this paper presents a novel protocol for voting in systems of this kind to address these two issues. The overall goal of the new design is that there be a high probability that loyal peers are in the healthy state despite failures and attacks, and a low probability that even a powerful adversary can damage a significant proportion of the loyal peers without detection. A peer periodically calls opinion polls on the contents of an AU (archival units) it holds. It invites a small subset of the peers into its poll, hoping they will offer votes on their version of the AU. Then if the poll initiator obtains a landslide win, it does nothing; if a landslide loss, it repairs its AU by fetching the copy of a voter who disagreed, and re-evaluates the votes; if the result is inconclusive, the caller raises an alarm to attract human attention to the situation. All the communication is encrypted via symmetric session keys. To defend the LOCKSS system from attack, the protocol prevents the adversary from populating a poll initiator’s reference list with malign peers by “reference list churning”, and prevents the adversary from using traffic analysis to infer state by “obfuscation of protocol state”. The simulation result demonstrates that substantial rates of random damage at peers result in low rates of false alarm and that the probability of a stealth adversary causing irrecoverable damage remains very low even for an initial subversion of 1/3. This paper didn’t consider the traffic generated by those complicated operations. Whether the traffic is a bottleneck for this application needs to be verified. --A Comparison of Overlay Routing and Multihoming Route Control This paper explores the possibility that intelligent control of BGP routes, coupled with ISP multihoming, can provide competitive end-to-end performance and reliability. The experiment of 3-multihoming versus 3-overlays shows that overlay routing achieve only a 5-15% RTT improvement over multihoming route control, and 1-10% improvement in throughput. The underlying causes of RTT performance differences are mainly from overlay routing’s ability to find shorter end-to-end paths. And another reason of performance gap is because most indirect overlay paths violate common inter-domain routing policies. This paper suggests that ISP can implement mutually cooperative peering policies to further improve the performance of route control. In addition, networks employing multihoming route control can react to observed failures more quickly by monitoring paths across ISP links, and switching to an alternate ISP when failures occur. The most contribution of this paper is that it demonstrates that there are still other possibilities for BGP routing to achieve good end-to- end resilience and performance. From: Ellick M Chan Sent: Tuesday, October 05, 2004 12:16 AM To: Indranil Gupta Subject: CS598ig reviews 10/5/2004 Ellick Chan CS598ig Reviews 10/5/2004 # A comparison of overlay routing and multihoming route control: Many of the benefits of overlay networks over the traditional BGP protocol stem from the innate ability of overlays to have fine-grained control over a globally optimal route. The main assumption made is that endpoints are only single- homed, and are thus unable to select a better route other than through an overlay. This paper examines the case where hosts may be multi-homed. Given multiple available BGP paths via multihoming, the BGP RTT is within 5-15% of the best overlay paths, while the throughput on the best overlay paths is only 1 -10% better than the best BGP paths. However, in situations with a single bottleneck, which are the common cases, overlays have significant performance advantages over multihoming and BGP. The authors attribute some of the overlay benefits to ISP preference of customer traffic over peer and provider traffic. Some 70% of overlay traffic violates these policies, potentially accounting for the performance increase measured. Finally, when 3-multihoming is used, it attains reliability that rivals overlay networks. The authors suggest that it is not necessary to circumvent BGP routing to achieve good resilience and performance. While this result is useful, it still requires that hosts must have multihoming interfaces. Another potential pitfall when using multihoming is that a customer can get two seemingly independent links, which are actually connected to the same line, resulting in a single point of failure. # On transport layer support for peer to peer networks: Traditionally, the Internet is divided into servers and clients. TCP provides a reliable method of transport with good congestion control for client-server transfers. The proliferation of peer to peer networks urges changes the requirements of the underlying Internet protocols. Peer to peer networks are characterized by transient reliability, low source bandwidth, and peer link heterogeneity. TCP does not work well with many connections to peers due to the transient reliability characteristics and connection heterogeneity of peer to peer networks. When these characteristics are exposed to peer clients, the anomalies in network operation can cause degraded performance. To adapt to the newer peer requirements, this paper suggests the use of multipoint-to-point connections. In this model, many “servers” send information to a single peer. In contrast to existing networks, this allows many low-bandwidth connections to contribute to peer to peer networks. By allowing parts of the data to come from many sources, this reduces average server load, resilience to transient failure, and an overall higher performance. To combat the heterogeneity, each individual connection of the multipath should keep it’s own statistics and congestion control. This reduces the problem observed using TCP where a single node can become bottlenecked. By placing the logic primarily at the receiver end, server migration is possible. There is minimal overhead in synchronizing the state between old and new supplying peers. Furthermore, in a streaming application, deadlines are more important than reliability. The R2CP protocol allows many peers to send data over to a receiver over a lossy channel; the receiver can later recover lost frames via an out of band recovery channel for later redistribution. One example to illustrate the multipoint argument is Gnutella vs. Bit torrent. In Gnutella, files are downloaded from a single host, but if the host leaves, then the file transfer is aborted. In Bit torrent, client computers receive chunks of the file from many sources, and the global integrity is verified by a checksum. # Preserving peer replicas by rate-limited sampled voting: LOCKSS is a project designed to preserve information in digital libraries using a large number of replicas on cheap hardware. Reliability, copy control, and integrity are verified through distributed consensus techniques optimized for accuracy over performance. The designers built the system to avert the strongest of adversaries by employing two principles. First, change in the system is intentionally slow and costly, making an attack difficult to mount over short durations; this allows both the system and human maintainers to detect and thwart the attack. Secondly, the system uses inertia through a distributed voting technique that replicates the most popular replica. Attackers can only affect replicas during a vote, and if the vote frequency is low, then damage can be slowed or stopped. Theft and freeloading are prevented by only allowing updates on nodes that previously contributed to a vote. This allows the system to maintain copy control as necessary. The system can survive up to 1/3 failures of maligned peers. The massive replication approach of LOCKSS is similar to peer-to-peer networks, but LOCKSS provides stronger guarantees of availability, reliability, and content control. Systems such as Oceanstore work similar to LOCKSS by maintaining many encrypted replicas. In Oceanstore, file distribution is governed by introspection, which allows data to be optimally placed based on various metrics such as usage and latency. LOCKSS differs by not relying on straight encryption to control distribution. The approach is better suited for long-term replication and integrity; there are no long-term private keys necessary. A similar approach is used by the Google file system, but chunks are used instead of archival units, and it relies on a master machine, which contains checksums of chunk contents. From: Pradeep Kyasanur [kyasanur@crhc.uiuc.edu] Sent: Monday, October 04, 2004 11:46 PM To: Indranil Gupta Subject: 598ig review 10/05 Pradeep Kyasanur P2P Apps(2) 1. A comparison of overlay routing and multihoming route control, A. Akella et al, SIGCOMM 2004. Overlay routing on top of the Internet has been proposed as a way of improving performance and overcoming the shortcomings of BGP. However, studies propounding the benefits of overlay routing have assumed that the end users are connected to the Internet through a singe ISP. This paper studies the benefits of using multiple ISPs (multihoming) as an alternative for overlay routing. The paper shows that using mulithoming offers similar path diversity and resilience to failure as offered by overlay routing. Comments: + The paper shows that poor performance of BGP can be overcome by using multihoming. Multihoming enables a significantly larger number of Internet hosts to be benefit from improved performance than is possible with specialized architectures such as RONs (Resilient Overlay Networks). + Multihoming is already used by many large end-users for fault tolerance purposes. Thus multihoming solution may be cost-effective to implement. - It requires further study to see what the impact on Internet will be when end users start to control the choice of routes. 2. On transport layer support for peer to peer networks, H-Y. Hsieh et al, IPTPS 2004. This paper identifies the need for a new transport protocol for peer-to-peer networks. Traditional transport protocols are beneficial for transfers between a single source and a destination. However, in peer-to-peer systems, for example for applications such as file sharing, data often needs to be downloaded to a client potentially from many hosts hosting replicated copies. Thus, the communication pattern used has a single receiver, and multiple, dynamically changing set of senders. The paper argues that the receiver is the only stable entity in the data communication, and hence should be responsible for reliability and congestion control. A new transport protocol called Radial Reception Control Protocol is proposed that is receiver-centric, and can interact in parallel with multiple sender nodes. Comments: + The main contribution of the paper is to identify the need for a new transport paradigm for peer-to-peer communication. - The proposed solution places all control in the client seeking data. This may lead to misbehaving nodes trying to cheat, for example, by not following the congestion control protocol, or by using many parallel connections to speed up the data transfer. It has been previously noted that many commercial applications are detrimental to Internet by using many parallel UDP flows. A similar possibility may arise with the proposed protocol. 3. Preserving peer replicas by rate-limited sampled voting, P. Maniatis et al, SOSP 2003 Digital preservation systems are designed to store data persistently for long durations of time and be resilient against failures and malicious attackers. Such digital preservation systems, based on a peer-to-peer network of participating hosts, have been proposed in literature. A key primitive required for the correct operation of the system is a voting protocol among a subset of peers in the network, which is used to maintain correctness and repair damaged data. This paper presents a voting protocol that is resilient to malicious attackers. The voting protocol ensures with high probability that malicious attackers cannot subvert the system without being detected. The main contribution of the paper is to develop an adversary model, and present voting algorithms that are secure in the proposed adversarial model. Comments: + The proposed voting protocol offers high degree of security against small number of malicious attackers. The overhead of maintaining the security is not too high, as long as the voting algorithm is not frequently invoked. - The need for digital preservation systems of the kind proposed here is not clear. The system is a means for preserving the archives, and traditional storage mechanisms such as replicated storage across geographically distributed sites may be sufficient. From: Charles Yang [cmyang2@gmail.com] Sent: Monday, October 04, 2004 11:33 PM To: Indranil Gupta Subject: 598ig review 10/05 Charles Yang 598ig, Fall 2004 10/5 P2PApps A Comparison of Overlay Routing and Multihome Route Control. A. Akella, B. Maggs, J. Pang, S. Seshan, A. Shaikh. Motivation: While Resilient Overlay Networks (RONs) offer RTT and throughput increases over today's internet BGP router networking, it may be possible to offer similar performance increases with today's current BGP routers. Enter Multi-homing. Basic idea: Instead of 1 uplink ISP, have 2+ and choose your best routes from there. Experimental Results: - compared with 1-multihoming (vanilla), 3-multihoming offered the best performance increase (20-40% RTT, 15-25% throughput over k=1) with respect to the # of ISPs. - compared with 1-overlay, 3-multihoming yielded comparable (within 5%, and sometimes marginally better) RTT, and 2-12% better throughput. -compared with 3-overlay, within 5-15% RTT, and 1-10% throughput. Main contribution: Multihoming, which requires no overlay network and is done with current BGP routers, yields comparable performance increases to that of overlay networks. Conclusion: There are a number of factors in deciding between overlays and multihoming (ISP costs, overlay costs, performance benefits). On Transport Layer support for Peer-to-Peer Networks. H.Y. Hsieh, and R. Sivakumar. Motivation: The paper posits that TCP is not optimal for P2P networks due to its point-to-point nature. Instead, they offer R^2CP which is designed to implement multipoint-to-point. The idea behind multipoint-to-point is that a destination peer will have a connection to multiple source peers, and will be able to select which packets to receive from a list of source peers (therefore, it can request more packets from a higher bandwidth peer – and still get *some* throughput from low b/w peers). Implementation: R2CP is dual layered. 1. the lower layer is RCP, basically a TCP clone except the destination peer is in charge of congestion and reliability of the incoming data. 2. R^2CP engine: maintains state of the many individual RCP connections, and basically does some smart multiplexing with its data requesting. Issues: - I am not quite convinced that one needs to create a new control protocol to sit side-by-side to TCP and UDP (and hence require new network stacks to be deployed network wide). What's the actual benefit of RCP over TCP? Why can't we just write the RCP engine as a library on top of TCP? P2P apps like Kazaa and BitTorrent already break up files into discrete chunks, and you merely request more chunks from the higher b/w connections, and less chunks from the lower b/w peers. - Perhaps an implementation at the transport level may be more efficient, but I just don't see how it's necessary or even desired. Preserving Peer Replicas By Rate-Limited Sampled Voting. P. Maniatis, D. Rosenthal, M. Roussopoulos, M. Baker, TJ Giuli, Y Muliadi. LOCKSS is a distributed protocol designed for the decentralized long term preservation of data, more specifically, library documents. The system is deployed on low cost (libraries, after all) machines, and accounts for the entropy of data due to unreliable storage, as well as possible malicious attacks. Design principles: 1. Cheap storage is unreliable, 2. No long-term secrets, 3. use inertia, 4. avoid 3rd party reputation 5. reduce predictability 6. intrusion detection is intrinsic, 7. assume strong adversary. The basic unit of data is the Archival Unit (AU), which consists about a year's run of a journal. The idea is that the AU is stored on multiple nodes, and every so often, a node can initiate a poll/vote to see if its own AU differs from the others'. There are two types of exchanges: poll initiation and participation, and bulk transfer of an AU in the case of repair. LOCKSS defends against free-loading and theft by only allowing machines which have participated in previous polls (and proven they have a valid copy of the AU), to get a new copy. The polling protocol also requires that both poll initiators and voters expend a provable computational effort (memory-bound functions), in order to increase the cost of malicious intent. Alarms can also be raised if the results of a poll do not fall within certain cutoffs. Simulation results indicate that 1. absent an attack, substantial rates of damage results in low rates of false alarm, and 2. with up to 1/3 of peers subverted, stealth adversary fails; and above that, the probability of irrecoverable damage gradually increases. From: Christopher W Banek Sent: Monday, October 04, 2004 9:03 PM To: Indranil Gupta Subject: 598ig review 10/05 Summaries of papers for October 5, 2004 Christopher Banek Akella et al. This paper presents a way to compare how overlays compare to normal Border Gateway Protocol (or BGP for short routing). By comparing BGP routing to overlays with only one end-to- end route, as well as k end-to-end routes using different overlays, this paper shows that overlay routing is preferable to normal BGP routing, but also if BGP routing is changed slightly (not inducing the overhead for an overlay network), that BGP routing might be able to come into contest if the source and/or destination networks are multi- homed. Their findings are mostly empirical, with not a lot of accompanying explanation as to why the results are as they are. I find their findings, although useful in context, to be somewhat lacking in the big picture. In Internet routing, the Internet is somewhat of a black box, and it is hard to figure out what each individual router is doing along the network. Because of this, I think it is hard to justify their results in a more general fashion. For instance, the bay area and Seattle area tend to provide different results in many of their tests. Why is this? Although they present that the networks and routing might be handled differently, I feel this is the more interesting and relevant part of their research. I believe that with how many different types of networks exist over the Internet, as well as different types of overlays, types of service in routing, as well as routing and peering preferences, that Internet routing is not merely a mathematical problem to be solved using certain metrics such as shortest path and lowest latency, but it is a large almost economic system of data. Although again, I find their data to be very useful and valid in context, I am not sure how this can be extended to provide useful data that could change routing protocols on the Internet for the better. Hsieh, et al. Although somewhat short, I believe this paper makes it's statement very eloquently and simply: almost all protocols developed for Internet usage did not have in mind the idea of distributed systems. Many of the problems in creating a distributed system, such as propagation of data and multi- cast, are usually just hacks on top of unicast communications. This presents a lot of overhead and programming headaches for the person writing a distributed system, since they have to take into account many possible failure and propagation cases, increasing programming time and more importantly network overhead. TCP specifically is a protocol that is best used for two computers, one acting as a client, and the other as a server (using bind() and accept() in sockets for example). But other than it's ability to reliably send data between two hosts, TCP is not a good choice for most distributed systems. Since this is a difficult problem to solve, I think that they did a good job in recommending a protocol and the features that a distributed system protocol would use at the transport layer. I feel that the ideas behind this protocol need to be further researched as I find the R2CP protocol somewhat lacking in that respect (I believe it should have more features involving joining and creating groups and small sub-clusters of nodes for file transfer and querying). Maniatis, et al. With my mom as a librarian and understanding a lot of the copyright issues as well as the electronic availability of journals, I think this article is no less than brilliant. The ability to store large amounts of data in an archive system that can repair itself is a wonderful idea. The prospects for illegal copying are reduced if not eliminated by the system, as well as the ability to change the data. Security built in from the protocol level up is also a brilliant way of doing things, providing accountability for both failed, malicious, and malfunctioning hosts. This is the way that security and intrusion detection should be done on more projects, at the protocol, as opposed to the application layer. By building security and reliability into the protocol itself, then most of the security issues will be programming and client specific, such as buffer overruns in the client providing a way to issue malicious instructions over a long period of time. I think these are the novel ideas, in the way that the protocol was come up with as opposed to the protocol itself. Many voting algorithms exist, but few are as complete and protected from attack as this. This is the true strength of this article. ~