From: w SpamElide on behalf of Will Dietz [wdietz2 SpamElide] Sent: Thursday, April 07, 2011 12:23 PM To: Gupta, Indranil Subject: CS525 Review 04/07 Will Dietz cs525 4-7-2011 "Corona: A High Performance Publish-Subscribe System for the World Wide Web" This paper presents Corona, a novel publish-subscribe system for the web. Presently we have lots of content that is constantly changing (paper gives examples of micronews, but there are many others). Instead of pushing updates to users interested in content, we have all users constantly polling. This is terribly unscalable, has poor performance, and absurdly high server loads. As a good system designer, the authors of this paper notice "polling is bad, event-driven is good" in terms of efficiency and built Corona which is uses a peer-to-peer distributed system to push content updates to interested parties (subscribers) via instant messaging services. One of their novel contributions is their optimization algorithm that achieves "optimal resource allocation" on their distributed system. The divide their system into 'wedges' that poll resources, the idea being that if n servers poll the content and /share/ any updates they find, Corona can detect updates n times faster. They determine wedge size dynamically based on observed overhead, and propose various optimization formalizations (leveraging Honeycomb) to achieve this. "AnySee: Peer-To-Peer Live Streaming" This paper presents Anysee, a peer-to-peer live streaming system. It improves upon existing work by focusing on inter-overlay (as opposed to intra-overlay) system optimization to achieve improved resource utilization. They allow nodes to belong to multiple overlays to achieve this, which they claim provides a robust and scalabe improvement to resource utilization, service quality, and load distribution. They evaluated this fairly extensively by deploying it on CERNET in China, with over 60k users to test their system. Their results show that their system is significantly better than intra-overlay optimizing systems that hope to achieve the same. ~Will From: Simon Krueger [skruege2 SpamElide] Sent: Thursday, April 07, 2011 12:18 PM To: Gupta, Indranil Subject: 525 review 04/07 Splitstream, M. Castro et al, SOSP 2003 Core idea of the paper: To allow high multicast bandwidth in a p2p environment by splitting the multicast content and multicasting each split into a separate tree. THe difficult aspect is to form the forest topology which has interior odes of one tree be leaves in the all the others which will distributes the forwarding loading. In order to construct and maintain the topology they use a peer to peer overlay. Pros: Cons: Thoughts on how the paper can be furthered developed: Any questions, criticisms, thoughts, doubts, or wanderings: Anysee: p2p live streaming, X. Liao et al, Infocom 2006 Core idea of the paper: In order to improve performance in p2p networks they purpose an inter-overlay scheme which allows nodes to join multiple overlays simultaneously. This allows for distributed resource utilization and better locality of resources, Pros: Cons: Thoughts on how the paper can be furthered developed: Any questions, criticisms, thoughts, doubts, or wanderings: What are applications that can benefit from this system? I feel like they do not provide enough motivation for their system for me to appreciate the work. Some of their points seem the same. For example they say (1) improve global resource utilization of a P2P live streaming network and distribute traffic to all physical links evenly and then state (4) balance the load among the group members but I believe these are the same things. Additionally in the same paragraph they mention (2) assign resources based on their locality and delay but I feel this is the same as their next point (3) guarantee streaming service quality by using the nearest peers Corona: a high-performance publish-subscribe for the World Wide Web, V. Ramasubramaniam et al, Usenix NSDI 2006 Core idea of the paper: Corona s a publish subscribe system for the web that does not use polling. Instead Corona uses a distributed, p2p, system to disseminate and in order to do it effectively they use a mathematical model to determine the optimal way to allocate bandwidth for objects depending on the objects popularity, update rate, size, and metadata/accounting information. They then figure out what is the minimal update latency that can be achieved with out occurring an overhead worst then normal, and what is the minimal update latency that can be achieved while trying to minimize bandwidth. Pros: Cons: Thoughts on how the paper can be furthered developed: Any questions, criticisms, thoughts, doubts, or wanderings: I think the instant messaging interface is something that I would not want to use. I would much rather use a web based interface. Simon From: Anupam Das [anupam009 SpamElide] Sent: Thursday, April 07, 2011 12:16 PM To: Gupta, Indranil Subject: 525 review 04/07 i. Anysee: Peer-to-Peer Live Streaming This paper talks about developing an efficient and scalable P2P overlay for live streaming. This paper argues that traditional P2P live streaming systems focus on intra-overlay optimization which suffers from drawbacks like high start-up and source-end delay, and inefficient global resource utilization. With the view to addressing these problems, this paper introduces a new P2P live streaming system called AnySee where resources can join multiple overlays. AnySee basically consists of 5 components: Mesh-based overlay manager, single overlay manager, inter-overlay manager, key node manager and finally a buffer manager. Mesh-based overlay manager uses a location detector based algorithm to construct an overlay that matches with the underlying overlay. Single overlay manager manages the join/leave operation of peers using a traditional intra-overlay based optimization technique. Inter-overlay manager’s job is to explore existing paths to establish backup paths in the event of the primary path failing to meet the required QoS. A fixed threshold number of backup paths are maintained by each node. These backup paths are setup through a reverse tracing mechanism. The key node manager takes care of the admission control policy and allocates the limited resource using queuing models. Finally the buffer manager schedules the transmission of the media data. The paper presents several trace driven simulations for comparing AnySee with CoolStreaming. The authors also deployed AnySee in CERNET of China in 2004. Pros: 1. AnySee uses inter-overlay optimization which allows peers to utilize low-latency path. 2. The system has been deployed in the Internet and used by more than 60000 users. Cons: 1. The paper does not discuss the reason behind using mesh-based overlay. Why not other topologies? May be a combination of topologies could be used. 2. In using inter-overlay optimization the system uses source nodes as relays. This could put extra burden on them and could eventually degrade QoS. 3. The paper assumes that the individual overlays will co-operate with each other. But if the purpose of each overlay is different then it would not incentivize them to co-operate. 4. The paper uses delay as one of the metric of link quality and it assumes that the nodes are synchronized using NTP (accuracy reported to be 7.5 ms which in the current network context is not that small). If however, this synchrony breaks then their approach would suffer greatly. ------------------------------------------------------------------------------------------------------------------------------------------------------- ii. SplitStream: High- Bandwidth Multicast in Co-operative Environments In a conventional tree-based multicast system, the load of forwarding multicast messages is carried out by a relatively small number of interior nodes. This poses a problem in P2P networks where dedicated high bandwidth nodes are not guaranteed. To address this problem this paper introduces SplitStream which partitions the content into multiple strips and then sends strips across a forest of interior-node-disjoint multicast trees. This significantly distributes the forwarding load across all the participating nodes. The main challenge is to construct a forest of multicast trees such that an interior node in one tree becomes the leaf of all the remaining trees. Doing so SplitStream also becomes resilient to node failures. The authors use Pastry routing to construct interior-node-disjoint trees by grouping the interior nodes by most significant bits. These interior-node-disjoint trees can guarantee the constraints of inbound bandwidth. To achieve outbound bandwidth constraint parent nodes try to have children within the outdegree limit. Experimental results show that SplitStream can distributes the forwarding load among peers with different bandwidth capacities while imposing low overhead for forest construction and maintenance. Pros: 1. Distributes forwarding load to all the participants i.e., no single peer is burdened with bulk of the forwarding load. 2. Fault tolerant to node failures as the failure results in a single strip loss. 3. The paper provides both theoretical and experimental analysis. Cons: 1. Though SplitStream distributes the forwarding load among the participants, it could result in increased latency as the message now might have to traverse a longer path. 2. The adoption and rejection of child by parent nodes has a kind of ping pong effect when the outdegree limit is reached. Because accepting a child only to reject another seems too much perturbation. 3. Here nodes become the interior node of a single tree while becoming the leaf of all the other trees. But would it be possible for a node to become the interior node of multiple trees (given that bandwidth permits)? If so then maybe some form of locality could be utilized in forwarding messages. ---Anupam From: Long Kai [longkai1 SpamElide] Sent: Thursday, April 07, 2011 12:15 PM To: Gupta, Indranil Subject: 525 review 04/07 CS 525 Reviews 04/07 Long Kai (longkai1) SplitStream: High-Bandwidth Multicast in Cooperative Environments Summary: This paper presents and evaluates SplitStream, an application level multicast protocol in cooperative environments. The motivation for this approach is that conventional tree based multicast suffers from uneven distribution of output burden. The few interior nodes in the tree take on the entire burden to spread the data.  In SplitStream however, the data is divided into several stripes and there is a separate multicast tree for each stripe that need to be sent out. Most of the nodes are interior node only in one such tree of the forest. This ensures the forwarding load can be spread across all participating peers. The protocol also accommodates to the bandwidth of each node. The node can change the number of stripes to receive and the number of child nodes to send to according to the bandwidth capabilities of itself. In this way, this approach is also more resilient to node failure, because now only one stripe of the data would be affected if a node is failed, and this can be detected if the encoding is good. Pros: It solves the problem of uneven distribution of forward load in application level multicast in an elegant way. Cons: When there is only one tree, good nodes with high bandwidth can be chosen to be interior nodes. In this approach, however, one bad node can slow down the speed of multicast. Each node can set the number of child nodes to forward to, but the tree structure cannot be changed. If a slow node is chosen to be the root, it is the root forever. Another problem is that the multicast does not send data in order. This is a problem for applications like stream video. Corona: A High Performance Publish-Subscribe System for the World Wide Web Summary: This paper presents Corona, an update notification system that is motivated by conventional high over head pulling model. In the conventional methods, clients keep polling to the server to check for updates, which create huge overhead on the server and meanwhile the clients cannot get update in a timely manner either. Corona system creates a notification system that allows clients to register for interest on a particular URL.  Corona polls to the server to check for updates, and this update will be published to clients who have subscribed. Another important feature about Corona is that it determines the number of computers in the system to keep polling for update based on the optimal balance of latency and bandwidth. If an update is found by one machine in Corona system, this update will be shared by all machines in system that poll for updates in that server. This update then is spread out by those machines. Pros: Reduce the bandwidth of polling for updates and get the update faster. Cons: This system creates another layer between the server and the clients. In some cases, this may not be an efficient way in a long run. If the update messages are frequent and the size of the messages are huge. This creates unnecessary cost of bandwidth on the network, because the data is not directly transferred to the clients. It would be better if clients can automatically share the updates. -- Larry From: Jason Croft [croft1 SpamElide] Sent: Thursday, April 07, 2011 12:14 PM To: Gupta, Indranil Subject: 525 review 04/07 Corona: A High Performance Publish-Subscribe System for the World Wide Web Users independently and repeatedly polling for the same content can incur high bandwidth to content providers. Corona aims to resolve the fundamental tradeoff between bandwidth and update latency by modeling it as a mathematical optimization problem. To achieve low latency updates, Corona uses cooperative polling by assigning multiple nodes to poll the same channels and share updates. It builds off Pastry and uses "polling levels" to determine the number of nodes to poll a channel, where a channel with level L is polled by all nodes with at least L matching prefix digits for Pastry's identifier. The authors propose several different optimizations for Corona, named Corona-Lite, Corona-Fast, and Corona-Fair. Corona-Lite ensures a server's load is no more than if clients simply pulled the data, while improving update performance by clients. This scheme benefits the most from cooperation, so more popular channels gain greater benefits than less popular ones. Corona-Fast minimizes network load on content servers while still meeting a specific average update detection time. Corona-Fair takes into account the update rate of the objects and uses a ratio of update detection time and update interval to minimize load. To solve the optimization problems for these schemes, Corona uses Honeycomb to find an approximate solution to the NP- Hard problem in O(MlogMlogN) time, where M is the number of channels and N is the number of nodes. It uses consistent hashing to spread load uniformly among nodes, while a primary owner of a channel (the node with the numerically closest ID to the channel's ID) is responsible for managing subscriptions, polling, and updates. Updates use timestamps when available or version numbers. Unlike many other publication-subscribe projects, Corona requires no changes to-- and fully interoperates with--the current pull-based architecture of the Web. The design also allows any Web object that has a URL to be monitored. Additionally, it can further reduce bandwidth by only sending deltas rather than the entire content for updates (since the average update consists of less than 7% of the content size). However, the use of an IM system to subscribe/unsubscribe exposes some information about the subscriber, as they now must use their IM account to subscribe. Perhaps a method of anonymizing subscriptions could be employed. Also, for offline users, the authors state the IM system buffers the update. Not all IM systems may do this; rather, some simply return an error to the sender stating the user is offline and the message cannot be delivered. Finally, the authors chose to build Corona on top of IM systems rather than a centralized infrastructure so as not to introduce a single point of failure. However, this simply shifts that problem to the IM systems, which may have centralized infrastructures that can fail (e.g., Skype outage in August 2007). AnySee: Peer-to-Peer Live Streaming Unlike traditional distributed systems, live streaming focuses on startup delay, source-to-end-delay, and playback continuity. AnySee uses inter-overlay optimization where nodes can join multiple overlays at the same time to improve the global resource utilization of the live streaming network, assign resources based on locality and delay, guarantee service quality by using the nearest peers, and balance load. AnySee consists of five main parts: a mesh-based overlay manager, a single overlay manager, an inter-overlay optimization manager, a key-node manager, and a buffer manager. The mesh-based overlay manager uses Location-aware Topology Matching (LTM) to find the latest neighbors and eliminate slow connections. The single overlay manager handles nodes leave and joining. The inter-overlay optimization manager finds appropriate streaming paths in the P2P network when the number of backup paths drops below a threshold. The key-node manager and admission control policy optimizes resource utilization, and the buffer manager handles receiving valid media data. AnySee has several strong points. First, it has been deployed and used by a large number of users, proving its scalability and effectiveness in minimizing latency. It is also optimized to choose low latency neighbors. However, it assumes clocks are synchronized, and uses timestamps between nodes to calculate delay (the LastDelay field in the probing message). Thus, if the clocks between peers are not synchronized, delay may be miscalculated. From: harshitha.menon SpamElide on behalf of Harshitha Menon [gplkrsh2 SpamElide] Sent: Thursday, April 07, 2011 12:08 PM To: Gupta, Indranil Subject: 525 review 04/07 Anysee : Peer-Peer Live Streaming Anysee is a peer-to-peer live streaming system which adopts an inter-overlay optimization scheme, in which resources can join multiple overlays to improve global resource utilization, balance load and give high streaming quality. The performance metrics considered are startup delay, source-to-end delay and playback continuity. To achieve good performance, the following challenges have to be solved. -How to find paths with low-delays -How to maintain service continuity and stability -How to determine frequency of optimization operations -How to reduce control overhead Pros: -It improves global resource utilization -Locality aware resource allocation to reduce delay -Guarantee streaming quality -Load balanced -This system was released to the user and hence has more credibility. Cons and Suggestions: -Why is it a mesh overlay? How about using torus which has a max distance of n/2 between nodes. -Requires the clocks of all the peers to be synchronized. -The paper doesn't show results of message overhead due to high churn rate. -In streaming bandwidth is one of the important parameters to be considered for performance evaluation which hasn't been considered here. Corona This paper describes publish-subscribe system for the web, which provides high performance and scalability through optimal resource allocation. Users register interest in Web pages through existing instant message services. Corona monitors the subscribed pages, detects updates and updates efficiently by allocating polling load among cooperating peers, and is disseminating updates quickly to users. Allocation of resources for polling is driven by a distributed optimization engine. The tradeoff between bandwidth and latency is considered as an optimization problem. Corona uses cooperative polling to improve the update latency and reduce overhead. Pros: -Provides high performance update notification service for the Web without requiring any changes to the existing infrastructure -It delivers updates asynchronously -Cooperative polling is used to improve the update latency. -Variation of pusher-subscriber which aims for different types of performance can be easily done by the constrains specified. This system is flexible. -Apart from bandwidth and latency they consider popularity, update interval, content size etc while constructing the constrains and this models the real life scenario. Cons: -Solving the optimization constrains is time consuming and might affect the overall performance. From: anjalis2006 SpamElide on behalf of Anjali Sridhar [sridhar3 SpamElide] Sent: Thursday, April 07, 2011 12:05 PM To: Gupta, Indranil Subject: 525 review 4/7 Corona: a high-performance publish-subscribe for the World Wide Web, V. Ramasubramaniam et al, Usenix NSDI 2006. Corona aims to provide a system of updates for rapidly changing information that does involve active polling. It is a scalable Pub-Sub system that delivers updates to its users. It is a distributed peer to peer system that allocates resources efficiently. It examines the tradeoff between the latency of updates received and the bandwidth load on the server to disseminate these updates. Corona uses cooperative polling to assign multiple nodes to periodically poll the same channel. Any updates seen by the nodes are then distributed among them themselves. Corona uses Pastry as the underlying routing algorithm for constructing the overlay network. Each channel is assigned a wedge number of nodes. These nodes that form the wedge share a common number of prefix digits. The polling level l determines the number of prefix digits to match. Lower the number l the smaller the digits to match and hence the greater number of nodes. There are five types of optimization problems that are stated Corona-Lite, Corona-Fast, Corona-Fair, Corona-Fair-Sqrt, Corona-Fair-Log. Each channel is assigned a primary owner which is the node whose identifier matches most closely with that of the channel. The primary owner assigns version number of the updates it receives and only shares the difference of the content. Cooperative polling is carried out in three phases – optimization phase, maintenance phase and aggregation phase. The primary node sends the update to the subscribers though an IM system. The central server that is present for the IM system poses a bottleneck. It seems that people subscribing to micro news updates do it via a plugin on their browser, an RSS aggregator like Google reader etc. The number of messages that are buffered can increase to a great extent depending on the number of days that the user has not seen the message and the number of subscriptions that the user currently has. Splitstream, M. Castro et al, SOSP 2003 The idea of Splitstream is to split the content into stripes and disseminate it to all using multicast trees. The multicast tree is constructed in such a way that the interior node in one tree is a leaf node in all remaining trees. The multicast trees constructed have disjoint interior nodes. This ensures that the required bandwidth of the node is limited and balanced across all nodes. Each multicast tree is used to distribute one stripe. Nodes in a tree can receive only the number of stripes that is within their incoming bandwidth. The outgoing bandwidth is controlled by the number of children it chooses to associate itself with as the parent. The number of stripes that are received can be less than the total in order to reconstruct the original data using some techniques like erasure coding, FEC etc. Splitstream uses Pastry as the underlying routing algorithm and Scribe as the group communication system. Using Pastry, the node forwards the message to the node whose prefix is most closely matched with that of the key. Splitstream limits the number of children by a process called push down. If the node has reached its out-degree limit, the child node looks at its siblings with the capacity else it is temporarily adopted by a sibling node and the process continues. If an orphan node is unable to connect to any of the nodes in a tree, it contacts one of the nodes in the spare capacity group that is maintained. It would be interesting to note the delay if different coding techniques were used. For streaming video, you do not require all frames and hence the delay would be significantly different. Viewing some results based on this would give us an idea about using split stream for peer to peer streaming or content distribution networks. From: kevin larson [kevinlarson1 SpamElide] Sent: Thursday, April 07, 2011 12:01 PM To: Gupta, Indranil Subject: 525 Review 04/07 SplitStream is an interesting alternative to traditional IP multicast. In multicast systems, a single tree is used to forward traffic. The non-leaf nodes in the tree are forced to carry the majority of the traffic burden. SplitStream introduces the idea of a multicast forest, made up of many trees. The data is split into stripes, each of which is propagated through a different tree. The data is by design, able to withstand loss of stripes, with a loss of quality proportional to the number of lost stripes. The system is built on top of Pastry and Scribe, leveraging the locality and neighbor sets from Pastry and the group communication system in Scribe. SplitStream also maintains a spare capacity group to adapt more quickly and efficiently to nodes joining and leaving the system. The conditions used in developing SplitStream were simple and intuitive, and the motivations were obvious. Also, the evaluation of SplitStream was thorough, covering setup costs, throughput, delay, and failure cases. This included mostly simulations, but some live experiments as well. While the evaluation was thorough, there were a few oddities about it. In one test (Churn), they used a 16x20 setup, which had never before been mentioned or motivated. Additionally, the “sequence number” was not well explained, and the disproportionately lower number of stripes in the live experiment failures were not reflected upon. AnySee was created to help alleviate several of the problems present in peer to peer streaming systems. Previous systems were local to a single overlays and regularly had difficulty taking locality into account. AnySee spans multiple overlays, and attempts to pair nodes with high locality, despite the possibility that the nodes may be on different overlays. AnySee is built atop a mech-based overlay, where it then leverages existing single overlay optimizations pertaining to join/leave operations of peers. These components also work with an inter-overlay optimization manager, which is responsible for inter-overlay links and breaking low QoS links. Atop these components are a key node manager, buffer manager, and decoder/player, which are responsible for managing and displaying resources and data. Simulation of AnySee demonstrates is viability in utilizing several overlays, outperforming Coolstreaming in both continuity and utilization, even with fewer neighbors and with smaller overlay sizes. The analysis of user behaviors related to acceptable delay and the consequences of them leaving was very interesting. While it is usually useful to include some of the math behind an algorithm, the math presented by the authors of AnySee was minimally explained, to the extent of being difficult to understand at times. Also, they mentioned crawling Gnutella for peer information, but then instead use random lifetimes in their simulation as opposed to leveraging this information. From: Shen LI [geminialex007 SpamElide] Sent: Thursday, April 07, 2011 11:38 AM To: Gupta, Indranil Subject: 525 review 04/07 Name: Shen Li SplitStream: High-Bandwidth Multicast in Cooperative Environments This paper proposes an idea to balance loads in Internet multicast tree. For previous multicast trees, a small portion of interior nodes forwards all traffic to all other leaves node. In a tree with fanout 16, 10% interior nodes will have to forward 90% traffic in this tree. It is obviously that those interior nodes will easily become bottleneck nodes. Their key idea is that transport an entire file, they split the target file into many splits. For each splits, SplitStream will try to build a non-overlapping forest to to forward the very splits to all nodes in the tree, where non-overlapping means that no nodes act as interior nodes in more than one tree.They leverage on Patry to fulfill this task. In Pastry, packets are forwarded to the destination based on maximum prefix match algorithm. So that SplitStream can simply build a non-overlapping tree by choosing groupIDs for the trees that all differ in the most significant digit. Pros: 1. Since the load is balanced among all nodes in the tree, the through put can be maximized, and if all nodes has the same capability, there will be no bottleneck nodes in the whole system. 2. Since the original data are striped into multiple splits, applications can encode some redundant information in each split. So that it will be more robust to failures. For example, even if one portion is lost due to network congestion, the end users can still reconstruct that packet from what they have. Cons: 1. SplitStream require nodes have almost the same upload and download bandwidth. But the reality is that most users have much larger downloading throughput than uploading capacity. When choosing the interior nodes, they did not take this into consideration. Corona: A High Performanc Publish-Subscribe System for the World Wide Web This paper provide a decentralized system for detecting and disseminating Web page updates. Naive polling for detecting updates cannot provide quickly notifications of updates, and there is too heavy load on server side. Corona uses a cloud of nodes which form a ring like architecture based on there nodeID. Each channel is assigned an identifier from the same space. A portion of nodes who share a common prefix will be responsible to monitor that very channel. The server can specify the polling level which indicating how many bits should be taken into account for the prefix matching algorithm. Higher level means less nodes. In this way, the load is distributed. And when all nodes for the same channel has different starting time for monitoring period, the update detection will be more prompt. Pro: Their same wins in both aspect: providing more prompt update detection and less load on each nodes. Con: The polling level is too coarse-granularity. Server cannot specify exact number for their polling group. From: Chi-Yao Hong [cyhong1128 SpamElide] Sent: Thursday, April 07, 2011 9:42 AM To: Gupta, Indranil Subject: 525 review 4/7 ---- Splitstream, SOSP 2003---- Forming an application-level topology for multicast service becomes an important problem with the prosperity of online streaming. However, conventional tree-based topology has following potential issues: i) tree structure is inherently not reliable as all the internal nodes are a point of failure, and ii) the forwarding (and duplicating) traffic has carried by just a small subset of the entire tree. To share the forwarding load over peers in the network, this paper proposed SplitStream to construct a collection of trees (i.e., a forest) for fair forwarding low sharing. In particular, the content is split into multiple stripes and is multicasted by different trees. The key idea is to build interior-node-disjoint trees to balance the load on different nodes. Pros: 1. I like this simple idea of using multiple trees, which is easy to implement and evaluate. Evaluation results show that the proposed scheme could provide very balanced load over both nodes and links. Cons: 1. The tree construction is tightly binding to the Pastry routing, which might results in suboptimal routing. In other words, given a Pastry network, the parameters of SplitStream are fixed so it is hard to increase the, say, path diversity or the size of forest according to the application needs. 2. I don’t understand how to extend this to any other overlay networks. The authors mentioned Tapestry and CAN, but there is no clear evidence that SplitStream could work on these overlays. 3. It might be interesting to address the issue of heterogeneous nodes/links. ---- Corona: a high-performance publish-subscribe for the World Wide Web, NSDI’06 ---- Conventional web update mechanism like publish-subscribe introduces scalability issues because of the frequently polling. To solve this problem, the authors propose Corona, a distributed algorithm on top of an overlay network. Corona collects the information like object popularity, update rate, content size and compute the optimal polling schedule subject to resource constraints. The authors deployed Corona on PlanetLab and validated that given the same workload Corona can provides faster update rate with a factor of 20 as compared with conventional scheme. Pros: 1. A clear presentation with a decent front-end implementation. In particular, I like the way that author explains the system model. Cons: 1. Why not showing the optimality and convergence time of Corona in the evaluation? 2. I am convinced that Corona has great performance on data plane. However, the author did not address whether the additional control plane would introduce further issues. Especially, under a high churn, it is interesting to study the stability of the control plane. -- Chi-Yao Hong PhD Student, Computer Science University of Illinois at Urbana-Champaign http://hong78.projects.cs.illinois.edu/ From: wzhou10 SpamElide Sent: Thursday, April 07, 2011 9:23 AM To: Gupta, Indranil Subject: CS525 Review 04/07 Review of “Corona: A High Performance Publish-Subscribe System for the World Wide Web” This paper proposes a novel publish-subscribe architecture, Corona, for the Web. The issue Corona tries to address is the tradeoff between bandwidth and update latency, and is formalized as a mathematical optimization problem. Corona is a distributed solution to this problem. The objective function it optimize is the global performance achieved by a polling schedule, subject to resource constraints. Constructing an overlay infrastructure, Corona makes use of cooperative polling to speed up updates and reduce overhead on servers. Pros: 1. Corona is a scalable decentralized publish-subscribe architecture, making good usage of Pastry ring. It doesn’t require any change to existing Internet infrastructure/protocols. 2. Corona reduces both update detection time and servers’ polling load. 3. The paper presents extensive simulation and real world deployment. 4. Several different optimization problems, each aiming at a distinct aspect of the system, are presented. This gives the operator the flexibility to choose a application-specific mechanism. Cons: 1. Primary owner suffers from more overhead than other nodes. 2. Corona may have some security vulnerabilities. For instance, users need to expose some private information, such as IM id, to get the update from the web server. 3. The experiment results show that the convergence time of Corona’s distributed optimization mechanism is long. Review of “SplitStream: High-Bandwidth Multicast in Cooperative Environments” Core idea: The conventional tree-based multicast system has the problem that interior nodes of a tree are overloaded. SplitStream, as a new multicast protocol on top of Pastry and Scribe, aims to address this problem. It builds a forest of interior-node-disjoint trees, satisfying the bandwidth constraints. That is the majority of nodes are interior nodes in only one tree, but could be leaf nodes in other trees. Pastry routing helps to construct interior-node-disjoint trees by grouping the interior nodes by disjoint most significant bits, which guarantees the bound of inbound bandwidth. To constrain the outbound bandwidth, a out-degree limit is posed on parents when choosing children. Moreover, DFS search is used in order to ensure parent is physically near the orphan. Pros: 1. SplitStream generalized the typical tree-based multicast to achieve balanced load by ensuring most nodes are interior nodes in only one tree. 2. Split Stream is highly robust to failures because a node failure causes the loss of a single stripe on average. 3. The authors provide convincing recults on large-scale simulation. Cons: 1. SplitStream replaces Pastry rings to construct interior-node-disjoint trees without considering proximity. Moreover, it finds orphan in a recursive manner. But both of these may increase latency. 2. Only bandwidth is considered, but not delay, which might be more important in multimedia streaming. 3. Encodings, such as erasure encoding, is recommended in the paper. But encoding and decoding might add delay. From: Andrew Harris [harris78 SpamElide] Sent: Thursday, April 07, 2011 6:06 AM To: Gupta, Indranil Subject: 525 review 04/07 Review of Corona and AnySee Corona is a content update monitoring and delta delivery service, akin to RSS readers but distributing the update burden across many machines. The result is a fast (by comparison, but also concretely in terms of tens of seconds), decentralized update monitor that incurs no extra bandwidth or server load overhead beyond RSS readers themselves. In fact, the update cost for a given web server in terms of bandwidth consumed is dramatically less than each client polling the web server for RSS files. Corona accomplishes this by using a Pastry ring of nodes to organize web update monitoring by levels, which share updates amongst themselves and eventually pass them to higher levels. Several different algorithms are described for Corona, including: achieving the fastest updates given a load bound on servers; achieving a maximum update latency while minimizing server load, and; using update rates of servers to fine tune load distribution. Corona is seen to outpace legacy RSS by multiple orders of magnitude in update detection, in the group’s micro-testing. Clients for Corona are delivered updates over traditional IM, which was a design consideration made to minimize the disruption in clients while still being useful. It seems as though it would be feasible to subvert the Corona network in two ways not discussed in this paper, which is odd considering their relative severity and effect on end users and servers alike. First, consider a malicious web host that has tuned itself to generate large delta updates at a frequency roughly equivalent to Corona’s individual nodes’ sampling rates. An example of such a large delta would be in something like an edit war on Wikipedia, wherein two users are struggling between blanking the page in question and restoring it. This malicious host could rapidly begin to flood the polling levels of the internal ring in Corona, as deltas are shared between all peers in a level. This may be an annoyance from just one malicious server, but a large enough group of such servers could affect Corona’s usability and response time for end users. Consider now a malicious group of end users that flood Corona’s internal URL monitor stores. Corona nodes would now take longer to fetch updates from legitimate nodes, as malicious nodes out-compete legitimate nodes in the update selection process. The notion of needing to trust the nodes in Corona to deliver accurate deltas is also a big point, but they address it in the paper body. AnySee is a peer-to-peer streaming content delivery system. Its core functionality is in the use of local optimizations in multiple network overlays (including geographical overlays), followed by the synthesis of these local optimizations to yield a low-latency, high bandwidth content path. They show that their micro-benchmarks outperform a widely used predecessor to AnySee, Coolstreaming, which suggests that the use of both a physical and a logical topology may be worth considering for realms such as P2P content distribution. AnySee suffers from many of the same problems of other decentralized P2P systems, such as the need to bootstrap new nodes, but this is only done once. A tool like this could be subverted as well, but for good purposes. Suppose a national (or corporate) filtering mechanism Is in place - all plaintext content is coming through the filter without users noticing. Oppressive, censoring gateway machines can block ordinary channels for content, but users can use AnySee to connect to the best servers for video just outside their grasp. This could be equally subverted, though, in that a malicious server could be added to the mix, whereby a subset of users will begin receiving a malicious video stream because they were closest to the AnySee node. The two would be interesting to see in tandem, actually. Consider using Corona to push updates to known good AnySee bootstraps. The list would be pushed fully, bootstraps would be updated, and so forth. With new seeding IPs, the content network could disappear, and the new network would take its place. Furthermore, with all seed IPs pushed through deltas, their bandwidth overhead is small but the message is still received; older parts of already-sent lists can be merged out successfully, using the delta. From: Agarwal, Rachit [rachit.ee SpamElide] Sent: Thursday, April 07, 2011 4:17 AM To: Gupta, Indranil Subject: 525 review 04/07 Rachit Agarwal ---- Corona: A high performance publish-subscribe system for the world wide web There is an apparently fundamental trade-off between update latency and bandwidth in publish-subscribe systems -- a higher frequency for checking content updates results in higher bandwidth consumption but lower update latency; on the other hand, a lower frequency for checking content updates results in higher update latency but significantly reduced bandwidth consumption. Given a pub-sub system, can we find a sweet spot? Is there an optimal operation point? Corona takes a semi-analytic systems approach to solve this problem. The problem is formulated as a distributed optimization problem and a system is designed that utilizes a solution on top of cooperative polling. Interesting, especially the design space explored by the authors! My ideas/thoughts on the paper: 1. My understanding is that the convergence time for the distributed optimization problems may be a little on the higher side, especially when the set of nodes in the network is not stable. In general, distributed optimization has a very poor performance if the set of nodes involved in the optimization problem are not fixed. 2. It would have been very interesting to see more discussion on failures. In general, more discussion on the overhead of constructing and maintaining the overlay would have been very interesting. 3. When do the performance benefits of Corona start overcoming the performance problems of RSS? It seems to me that Corona would require a large scale deployment to really overcome the shortcomings of RSS. My comment may be partly motivated by the first two comments. 4. How frequently do I check RSS feeds? Oh wait, I am not in banking, but do they check RSS feeds that frequently? How many people really do? ---- Splitstream: high-bandwidth multicast in cooperative environments This paper presents a multicast protocol that builds upon Pastry and scribe. There are two interesting observations made in the paper. First, in traditional multicast transmission, the load is not evenly distributed across the multicast nodes -- intermediate nodes are overloaded while the leaf nodes have low utilization. Second, the traditional multicast trees have low fault-tolerance -- even a single multicast tree node failure may render the transmission useless for a large fraction of receivers. Splitstream overcomes these two problems using a single solution -- rather than constructing a single multicast tree, they construct an interior node-disjoint multicast forest with specific properties to handle the first problem. Each tree in the forest transmits a "split" or chunk of the data which may further be erasure coded to take failures into account. I like the fact that the paper builds upon a solid theoretical foundation, though I do have some comments: 1. I am wondering about the trade-offs. Yes, nodes have a more homogeneous resource utilization in Splitstream, but doesn't the scheme increases the overall resource utilization in the network even in the absence of any coding scheme? 2. The multicast forest formation is intensely focused on bandwidth. My understanding is that for many applications that use multicast, delay also seems an important factor. 3. A related comment is that in many applications that use multicast, packet fragmentation leads to poorer performance. For example, if data is split into multiple chunks, the performance is not determined by how much delay each chunk has, but the *delay difference* between different chunks for the same data packet. It is not clear that Splitstream does not worsen the performance for such applications. ---- -- Siebel Center for Computer Science, University of Illinois at Urbana-Champaign, Web: http://agarwa16.wikidot.com ---- Sing as if No one is Listening, Dance as if No one is Watching, Dream as if You'll Live Forever, Live as if You'll Die Today !! From: Nipun Sehrawat [sehrawa2 SpamElide] Sent: Thursday, April 07, 2011 3:05 AM To: Gupta, Indranil Subject: 525 review 04/07 Corona: A High Performance Publish-Subscribe System for the World Wide Web Users subscribed to web-pages (through RSS feeds etc) need to poll the registered pages periodically, to detect and fetch any updates. As all users (many registered to same set of pages) poll individually, it causes high traffic to servers, which then often limit the polling intervals, increasing the update latencies seen by clients. to The central idea of Corona is to establish a framework for collaborative polling, where a set of nodes collaborate to poll for pages subscribed by client and then disperse any seen updates to all the clients. Thus, a fewer nodes do the polling, polling rate dynamically varies according to factors like popularity of webpage, mean update time etc, instead of all clients polling independently. Corona tries to minimize update latency (decreases with high polling frequency) while maintaining a low average polling load (increases with polling frequency). Corona maintains a set of nodes which cooperatively poll the registered webpages (channels). These nodes are part of an overlay network, such as Pastry. The channels (URLs) are also represented as nodes in the overlay. Number of nodes involved in polling a particular channel is determined by its polling level, a polling level l means that all nodes that share first l digits with the channel id shall poll that channel. Thus, a lower polling level indicates a higher number of associated polling nodes. Corona employs HoneyComb to solve the update-time vs network optimization problem in a distributed fashion. Each channel is assigned a primary owner, which is the the node closest to the channel id on the ring. The owner node is responsible for keeping track of subscribers of the channel, dispatching updates and maintaining optimal polling interval. Three phases are involved to ensure a selection and adoption of an optimal polling level - - Optimization phase: Nodes run the optimization algorithm locally (using HoneyComb). - Maintainable phase: Any changes to polling levels, as computed in optimization phase, are communicated to peers. - Aggregation phase: Nodes receive aggregates of trade-off factors (update interval vs network load). Corona uses a smart diff engine, which ignores minor changes, such as advertisements, visitor counters etc, to webpages. It also features a IM based frontend, using which subscribers can enter a URL they want feeds from and also receive updates over it. Pros: - Corona makes the load experienced by servers to be independent of number of clients subscribed for a channel, as polling is done only by Corona servers and not by each and every client independently. - Corona integrates well with legacy web-servers, which primarily work with updates detected using periodic polling - The network load vs update latency problem is solved in various flavors, giving many useful implementations of Corona. Cons: - Updates are dispatched centrally by the owner of a channel, possibly adding to the update latency seen by the subscribers. Suggestions: - Updates are currently dispatched centrally by the owner node. The owner can distribute the subscribers among the set of nodes polling for the concerned channel, which can then parallely dispatch updates to the subscribers. ---- SplitStream: High-Bandwidth Multicase in Cooperative Environment SplitStream provides a novel multicast streaming solution for a set of cooperating nodes, by splitting the original stream into multiple low-bandwidth stream, that can be combined to recover the original stream. The motivation of this paper comes from the fact that in a peer-to-peer multicast, most of the nodes end up being the leaves of the multicast tree and thus don't share the burden of multicasting, whereas the nodes that are at intermediate nodes, have to route high bandwidth through them. To ensure fairness, SplitStream suggests splitting the broadcast into stripes and then creating one multicast tree for each stripe to ensure that nodes that are leaves in one tree, serve as internal nodes in other trees. SplitStream uses Pastry to form an overlay network of participating nodes and Scribe for application level mutlicast. It also takes into consideration the incoming and outgoing bandwidth bound specified by peers. It then forms a forest of "interior-node-disjoint" trees, with one tree per stripe. The trees in this forest satisfy the property that a peer is an intermediate node in atmost one multicast tree and is a leaf in remaining trees. This evenly distributes the multicast load among peers. Each stripe is assigned a stripe-ID, which is equal to the node ID of group's root, and a multicast tree is formed by ascertaining routes from each peer to the root. Now, as routing in Pastry is achieved by hopping to a node that has a longer matching prefix, this scheme ensures that all intermediate peers will share a command prefix. This property can be used to ensure that different multicast trees have different internal nodes - by choosing different MSBs for stripe-ID of different groups. As nodes specify bounds on their outbound and inbound bandwidths, a case might arise during tree construction, where an intermediate node can't accommodate any new child. This can be tackled by either the (full) parent directing the child to another children of its or to a "spare capacity group", which a group of internal nodes who aren't at their maximum capacities. Pros: - Distributes multicast load equally among peers, which is not the case in IP based multi-cast. - Decomposing streaming into stripes help nodes specify the quality of stream they wish to receive, as a function of the amount of incoming and outgoing bandwidth they wish to contribute. Cons: - A delay in one of the stripes might result in either delaying the entire stream or reducing the quality of streaming (if delayed stripe if dropped). From: Curtis Wang [cwang89 SpamElide] Sent: Thursday, April 07, 2011 2:58 AM To: Gupta, Indranil Subject: 525 review 04/07 Curtis Wang (wang505) 4/7/11 Publish-Subscribe/CDNs Corona Corona is a distributed peer-to-peer system for delivering updates to subscribers through the existing pull-based architecture of the world wide web. Corona improves on naïve polling by utilizing cooperative polling: peers are divided into groups and assigned to specific websites to poll. Updates found by a peer are disseminated through the network. In this manner, traffic to web servers are greatly reduced, as well as the latency between an update and its receipt. The interface on the client side is a simple IM interface. Also, Corona expresses the tradeoff between bandwidth and update latency as an optimization problem, and provides different analyses for different performance goals. Pros - Works with existing web servers - Simple IM interface for subscribers - Uses cooperative polling to reduce network traffic and follow publisher-imposed polling limits Even though Corona provides several advantages over current methods, it is still in its essence just a patch for the time being. Also, it seems like Corona can only handle topic-based pub-sub systems and not content-based systems. AnySee AnySee is a peer-to-peer system for live video streaming seeking to improve startup delay, source-to-end delay, and playback continuity, which are important metrics from a user standpoint. Instead of focusing on intra-overlay optimization, AnySee focuses on inter-overlay optimization. This means that a node can participate in more than one overlay. This allows peers to utilize nodes in other overlays allowing for better global resource utilization, load balancing, and locality. The design of AnySee consists of five components. The mesh-based overlay manager organizes the underlying mesh topology. The single overlay manager is used for traditional intra-overlay management and deals with peers joining and leaving the overlay. The inter-overlay optimization manager explores the network and creates backup links for the overlays. The key node manager controls the resources of a node by managing requests. Finally, the buffer manager organizes the data received from peers to ensure continuous playback. Pros - Allows for better global resource utilization and load balancing - Already deployed with over 60,000 users From: lewis.tseng.taiwan.uiuc SpamElide on behalf of Lewis Tseng [ltseng3 SpamElide] Sent: Thursday, April 07, 2011 1:06 AM To: indy SpamElide Subject: 525 Review 04/07 CS 525 - Review: 04/07 Publish-Subscribe/CDNs Anysee: p2p live streaming, X. Liao et al, Infocom 2006. This paper first identified the insufficiency in traditional peer-to-peer (P2P) live streaming based on traditional streaming overlays and it proposed a new streaming service, AnySee, which is based on inter-overlay optimization in contrast to old technique of intra-overlay optimization. Such technique has been applied in DONet, and ESM, but they suffer from “long delay and unplanned interruptions.” There are two disadvantages identified in the paper, non-globally optimal route is used and resource utilization is low due to embedded multicast tree structure. The inter-overlay optimization not only outperforms old techniques in these two categories, but also guarantees service quality by considering node locality and load balance among the members in the same group. The paper has several contributions. First, AnySee introduces an extra abstract layer of overlay and uses technique like Location-aware Topology Matching to construct a mesh-based overlay, which reflects the underlying physical topology. As a result, peers should have logical links to nearest neighbors. Then AnySee separates two techniques of inter- and intra-overlays optimizations, of which would be executed on top of mesh overlay independently based on some threshold value. In particular, single overlay manager adopts traditional inter-overlay technique and performs membership management. When the number of backup streaming paths managed by the manager is too low, the inter-overlay optimization manager is called to find appropriate paths using reverse tracing algorithm that is based on information via probing messages. Second, AnySee uses M/M/m/K queuing system to solve admission control policy to achieve load balance in O(N). Third, the paper compared two metrics, resource utilization and continuity index (# segments that arrives in time over total # segments) with CoolStreaming. Moreover, the paper implemented the system and presented analysis based data collection in a half-month duration. Questions/comments/critiques: The analysis of implementation part seems a bit weak, since the number of users was relatively low (7200 users compared with 60000 potential users in 2004) and the duration of observation was too short (only half month). One observation that users do not care delays from 20 to 30 sec., if the program is popular is interesting. Hence, AnySee then uses both average delay and the percentage of leaving peers (ADL index) as triggers of overlay optimization. Is this a reasonable design choice? Especially, using average delay as denominator is weird. Doesn’t it mean that when delay is high, no optimization is performed, since ADL is becomes lower and lower (than a pre-determined threshold)? Moreover, does it make sense to use leaving percentage? This hide the real number of users. Consider a bad program, lots of user come and go, so it has large leaving percentage and high ADL. As a result, AnySee tries to perform optimization on this bad programe. All in all, the usage of ADL and their assumption about leaving percentage indicating heavy burden of overlay seem to off the track. The paper mentioned that as more users join, average delay increases. While this intuitively makes sense due to growing tree size, but isn’t one advantage of P2P system that as number of users increases, quality also increases, since more people are contributing? Is there a design exploiting this fact? Or perhaps, delay increases, but the bandwidth can also benefit from more users? Corona: a high-performance publish-subscribe for the World Wide Web, V. Ramasubramaniam et al, Usenix NSDI 2006. This paper pointed out that the publish-subscribe mechanism through uncoordinated polling suffered poor performance and scalability. The paper studied the bandwidth and update-latency tradeoff and proposed a system called Corona that tries to utilize all aggregate bandwidth available. Two relevant goals were mentioned: how to minimize update latency while keeping the load on publishers the same; and how to achieve such latency with low bandwidth consumption. First contribution of the paper is to propose a design that is backward compatible, i.e., the content publisher does not need any modification. Corona is an overlay-based system that has several features: Cooperative polling allows it to detect updates faster. Flexibility comes from the different embedded optimization problems. Such a optimization can be solve efficiently and in a decentralized fashion using the Honeycomb, a optimization toolkit. Overlay-based design provides resilience against failure and churn. A difference engine allows nodes disseminate only deltas, the differences between old and new content, when they observe updates. Second contribution is the extensive simulations that were based on extrapolation of collected user data. In the deployment on PlanetLab, Corona outperforms Legacy RSS in both update latency and polling load. Questions/comments/critiques: In conclusion part, the paper mentioned the core design can be applicable to any domain where nodes monitor some exogenous events. I am wondering what are possible scenarios that can benefit from this kind of design. Sensor network is not an appropriate context, since this pull-based data source might potentially lead to too much waste of resource. What are other problems needs backward compatibility and in such a large scale? Maybe I miss something, but did the paper mention how well does their (approximated) optimization perform through theoretical analysis? From: Qingxi Li [cs.qingxi.li SpamElide] Sent: Wednesday, April 06, 2011 11:18 PM To: Gupta, Indranil Subject: 525 review 03/31 Qingxi Li AnySee: Peer-to-Peer Live Streaming This paper introduces an inter-overlay optimization scheme. The main idea is using the node in the other overlay networks to reduce the latency. When a peer joins the network, it should know at least one peer in this network and then uses current neighbors to iteratively find the latest neighbors. For example, when node A joins the network with neighbor B, B has a neighbor C. A will send two messages which are A->C and A->B->C. If C finds that A->C is shorter than A->B->C, then C will cut the connection of BC and directly connect to A. After that, A will find the other neighbors by C. This mechanism can optimize the latency between peers, however, when one peer joins, it needs send a large amount of messages and as this optimizing mechanism is done iteratively, which also causes a large starting-up delay. Besides this, when the peers frequently join and leave, the topology of the networks will also frequently changes. In fact, this situation can always happen in the peer-to-peer median applications, like PPLive. Additionally, each peer will have one active streaming path and a lot of backup streaming path. When the active streaming path is disconnected or the speed is too slow then the peer will choose another streaming path from the backup streaming path. When the number of the backup streaming path is below a threshold, AnySee will use a probing procedure which will randomly choose neighbors to flood to find out a new path with latency small than the LastDelay which is the minimum source-to-end delay which only includes the peers in current overlay networks. There is a tradeoff between the possibility to find the source and the number of messages be used in the randomly flooding. SplitStream: High-Bandwidth Multicast in Cooperative Environments SplitStream split the content into k stripes and to multicast these k or more than k stripe using a separate tree to solve the problem that in one multicast tree the resource of the leaf nodes will not be used and the median nodes will be much less than the leaf nodes. SplitStream let the peer to determine how many child it wants and how many different strips it wants. The number of strips will determine the quality of the file. However, there are many problems of the SplitStream. Firstly, the malicious nodes can request multiple strips and don’t give any contributions which many that the peer chooses no child. Second problem is when the peer requests the highest quality and some strips lost, if the peer still wants the highest quality, it needs to request other strips which will increase the delay and otherwise, it can only get the low quality file. Thirdly, this protocol increases the workload of source as it should send more strips than necessary to make sure that even some strips cannot be received by the peers, there are enough strips for peers to recover this problems. Besides this, it also needs to compute multiple multicast trees. The last problem is that the peers can get the file until it gets all the strips it wants. I think maybe this delay will be longer than the original one but I am not sure about that. From: Tengfei Mu [tengfeimu SpamElide] Sent: Wednesday, April 06, 2011 9:52 PM To: Gupta, Indranil Subject: cs525 review 04/07 1. Anysee: p2p live streaming The paper presents Anysee, an efficient P2P media live streaming system. Anysee combines the strength of both tree-based overlay and mesh-based overlay, and composed of 5 managing blocks: mesh-based overlay, single overlay, inter-overlay optimization, buffer and key code manager. One special Anysee feature is the cross-overlay optimization, i.e. when multiple overlays share common nodes, traffic intended for one overlay is sometimes routed through another if the alternate overlay is not fully loaded. Finally, the authors present results from an experimental evaluation, as well as a simulation based comparison with the Coolstreaming system. Pro: 1. Anysee utilize the strength of both inter-overlay optimization and the intra-overlay optimization. 2. Anysee has been released and deployed in CERNET of china. Con: 1. The paper didn’t discuss about the trade-off between the performance of Anysee and its message complexity. 2. Corona: a high-performance publish-subscribe for the World Wide Web This paper presents Corona, a novel publish-subscribe architecture that is compatible with the existing pull-based web architecture. As for the existing WWW, the client polls each server to request the updated information independently. But Corona monitors subscribed web pages using channel abstractions from cooperative polling and disseminates the updates in a decentralized manner. Corona assigns a primary owner of channel and the primary owner receives cooperative polling from the assigned nodes and disseminates the updates if exist. There is tradeoff between update latency and bandwidth usage depending on polling level. Finally the authors describe and evaluate an experimental deployment which uses Pastry to maintain the polling cluster substrate. Pro: 1. Corona could achieve lower update latency for clients while not increasing load on the content publishers. 2. Corona is scalable decentralized publish-subscribe architecture Con: 1. Corona relies on IM service for control and disseminates the updates. From: mark overholt [overholt.mark SpamElide] Sent: Wednesday, April 06, 2011 5:30 PM To: Gupta, Indranil Subject: 525 review Mark Overholt CS525 Review 04/07/2011 AnySee: Peer-to-Peer Live Streaming Internet live streaming (eg, video) is popular. To do that efficiently, the consumers of the stream are constructed into a multicast tree overlay, to reduce load on the producer as well as reduce network traffic. This paper presents a case for inter-overlay optimization because separately optimizing individual streaming overlay misses opportunities to optimize whole system. The approach here is that a node can join multiple overlays, and the system will use an inter-overlay optimization scheme to improve global resource utilization and distribute traffic evenly to all physical links, assign nodes based on their locality and delay, guarantee streaming service quality by using the nearest peers, and balance the load among group members. The nodes first form a mesh-based overlay and a locality algorithm runs to match the overlay with the underlying physical topology. Within individual overlays, there is a "single overlay manager" as in traditional intra-overlay optimization that deals with node churn. Then, the "inter-overlay optimization manager" explores appropriate paths, builds backup links, and cuts off paths with low QoS for each end peer. Finally, the "key node manager" allocates the limited resources, and the "buffer manager" manages and schedules the transmission of media data. The locality algorithm uses ping-like message latencies to infer locality among logical neighbors, then the node will select among logical neighbors with the same hop counts the one with the lowest ping latency as its new neighbor. Because each node is part of multiple overlays, it can receive media contents from multiple providers, allowing the inter-overlay optimization to select the best path to receive content and use the remaining ones as backup paths. When there are multiple providers, Because of the inter-overlap optimization, nodes can use smaller buffers, thus reducing startup delay. Discussion: Pros: The overlay construction takes into account important metrics such as delay and user patience The system has been used over the real internet and has been tried and tested. The success of these transmissions speaks in favor of the ideas used here. Cons: Requires the nodes in the overlay to have synchronized clocks. How to deal with the nodes with selfish behavior? Corona: A High Performance Publish-Subscribe System for the World Wide Web Summary: RSS feed is an important application now a days to get the regular updates of different web related services such as blogs, weather report, news, etc. However, current RSS approaches suffer from a major drawback of higher number of polling for detecting updates which consume unnecessary bandwidth and creates scalability issue. In the paper titled "Corona: A High Performance Publish-Subscribe System for the World Wide Web", the authors proposed a publish-subscribe system which serves the same purpose of RSS feed but in an efficient and scalable way. Prior researches proposed various publish-subscribe systems, which unfortunately, were not directly applicable to existing WWW architecture. Corona addresses that issue. Corona, a cloud of several nodes forming overlay network through Pastry, works as the middle layer between publishers (web servers) and subscriber (clients) to assist communication between publishers and subscribers. Corona exploits IM service where each client at first needs to register their interests via IM. This paper mainly make three major contributions such as it sketches the design of Corona, a publish-subscribe system that does not require any changes to content sources, it formalizes the tradeoffs between bandwidth allocation and frequency of polling as an optimization problem and provides a distributed numerical solution, and it presents results from large-scale simulations and measurements form PlanetLab deployment Discussion: Pros: Cooperative polling is used to increase the efficiency and decrease the unnecessary overhead. An optimization framework for performance-overhead tradeoff is formulated. Different objectives can be achieved using the same optimization method and tools. Cons: No analysis on the amount of overhead introduced by constructing Corona cloud or performing different system management operations is presented. In some scenarios all these might add high overhead to the task of delivering updates. Time needed for the distributed solution of the optimization problem to converge to the optimal point might be long in some cases. And this time adds delay to informing users about the updates. The distributed methods for solving optimization problems do not always converge to the global optimal. It is not clear if this case might happen in Corona or not. From: Ankit Singla [iitb.ankit SpamElide] Sent: Wednesday, April 06, 2011 5:12 PM To: Gupta, Indranil Subject: 525 Review 04/07 1. Corona ---------------- Summary: The paper tries to resolve the issue polling-based systems face for delivering timely updates: clients need frequent probing, so servers face overload. Corona's solution to the problem is simple, but sensible - multiple nodes co-operatively poll a set of webpages/servers they subscribe to for content and then share the updates amongst themselves in a p2p overlay. They present the co-operative querying rates and distribution as an optimization problem trading update latency and publisher load. They discuss both facets of the problem - budgeted on latency as well as budgeted on publisher load - as well as a few different variants of these. They formulate the optimization problem and then solve it in a distributed fashion using Honeycomb. The fairly extensive evaluation shows a 10x improvement in update latency for the same publisher load, which is commendable. The system is built on top of the Pastry overlay. They make use of a fairly convenient prefix-based classification of nodes allowed by Pastry to decide how many and which nodes poll a resource. Their use of Pastry is quite convenient for quick and reliable dissemination and storage of updates. Comments: I think that one security problem Corona could easily avoid is that of ensuring content integrity - since the problem is polling bandwidth and not actual download of an update, Corona could have focused only on that issue, requiring the interested client to fetch the actual update from the server itself instead of Corona peers. Their attempt to strip out advertisements (by doing a 'diff') might also be seen as adversarial by the publisher. This is probably why it makes more sense for a content-publisher to actually deploy this system on some infrastructure like Akamai (which they briefly discuss). But in that case, why not push the updates to these effective replicas instead of a polling-based approach? I guess that's how content-distribution evolved in this fashion and not the Corona way. On the whole, I think the push-based multicast model is more successful for disseminating latency-sensitive updates while maintaining low overheads at the source node. 2. AnySee ---------------- Summary: AnySee attempts to allow overlay participants to take part in multiple overlays simultaneously and benefit from whichever connectivity is most useful at the moment. Several overlays run simultaneously and nodes can take part in multiple ones. There are management components that decide which overlay peers to use etc. A set of active paths and another set of backup paths are maintained and when the QoS on one of the active paths dips below acceptable, AnySee switches that for a path from the backup paths. The 'goodness' of paths is determined by the streaming recipients flooding probes over these and receiving replies. Comments: The streaming recipients probe for good paths, which is better than the source having to do the probing. However, the source does have to respond for every probe that reaches it along all paths, so that the recipient can make a decision about the path's quality. There seems to be a scaling issue here. Why don't peers exchange information about path quality only with their neighbors (like distance vector)? Overall, I find this system fairly flaky; the experiments and deployment (60,000 is a lot of users!) are probably the main reasons for why this is worthwhile. Cheers, Ankit -------------------------------------------------------------------- Ankit Singla Graduate Student, Computer Science University of Illinois at Urbana-Champaign (UIUC) http://www.cs.illinois.edu/homes/singla2/ From: david.m.lundgren SpamElide on behalf of David Lundgren [lundgre4 SpamElide] Sent: Wednesday, April 06, 2011 3:45 PM To: Gupta, Indranil Subject: 525 review 04/07 Corona: A High Performance Publish-Subscribe System for the WWW Ramasubramanian et al. present the Cornell Online News Aggregator (Corona). Corona follows the publish-subscribe messaging pattern to disseminate web site updates (a la RSS feeds) to users who subscribe to particular topics. In Corona, topics (or channels) are defined as URLs of Web content that users register their interest in. Corona monitors these channels via cooperative polling from multiple distributed nodes arranged in a Pastry ring. Corona determines the proper assignment of polling peers to web sites with certain constraints by framing the matching as an optimization problem whose solution is found using the Honeycomb toolkit. Changes based on the optimization solution are propagated to nodes via maintenance messages which also help to distribute aggregates of trade off factors. Corona is evaluated experimentally on PlanetLab and is compared to legacy RSS. By varying the optimization problem, Corona's designers are able to trade off network load with update detection time. It is also shown that Corona provides faster update detection latency for frequently updated channels. Pros, Cons, Comments, and Questions: - Corona's backwards compatibility with the existing web framework is extremely important for deploying Corona as anything more than a academic exercise. - It is unclear how well Corona's cooperative polling functions with varying rates of failure and/or churn in it's underlying distributed system. Also unclear to me is the rate of update dissemination among cooperative polling nodes. - Phrasing the problem as an optimization one makes solutions well defined and allows Corona to determine optimal resource allocation, rather than following ``best-practice'' or heuristic assumptions. - Delta-encoding is a nice mechanism for encoding updates and directly follows the authors' characterization of web content updates. ------------------------------------------------------------------------- AnySee: Peer-to-Peer Live Streaming Liao et al. introduce AnySee, a scalable P2P architecture for live-streaming overlay construction. AnySee initially builds a mesh-based overlay using flooding with a limited TTL, delegating peer membership operations to a single overlay manager which uses the attribute LastDelay, the minimal current node-to-streaming source delay across (all?) paths, to determine overlay membership. Inter-overlay optimizations are handled implicitly by the inter-overlay optimization manager, which analyzes network paths and is in charge of backup path construction and poor path pruning. Network resources are then assigned using a key node manager that frames resource utilization as an optimization problem with a solution complexity of O(n). Finally data is transmitted to the user via the buffer manager. Simulations are performed an AnySee is shown to have a better continuity index and resource utilization than Coolstreaming, an intra-overlay system. The system is then implemented and various system logs are examined. It is observed that large delays are not always the major reason for a peer leaving the system and that delays between twenty-thirty seconds may be tolerated by users for popular content. Pros, Cons, Comments, and Questions: - One of AnySee's could be its complexity. It has many different parameters (TTL, backup set threshold, etc). A plethora of parameters such as this increases the complexity of a system dramatically. - The smaller buffer improvement of AnySee is a substantial one. It allows the continuity index of AnySee to remain relatively constant across varying stream rates. - Future work could examine alternatives to the initial mesh-based overlay used. - Load balancing is mentioned as an important design motivator, yet it is not evaluated empirically. - The trade off of optimization efficacy vs. the overhead of j forwarding neighbors in the inter-overlay manager is not discussed in detail, and no formal analysis is provided.