Christos Gkantsidis
Publications
  • Charalampos E. Tsourakakis, Christos Gkantsidis, Bozidar Radunovic, and Milan Vojnovic, Fennel: Streaming Graph Partitioning for Massive Scale Graphs, in WSDM 2014, February 2014
    Balanced graph partitioning in the streaming setting is a key problem to enable scalable and efficient computations on massive graph data such as web graphs, knowledge graphs, and graphs arising in the context of online social networks. Two families of heuristics for graph partitioning in the streaming setting are in wide use: place the newly arrived vertex in the cluster with the largest number of neighbors or in the cluster with the least number of non-neighbors. In this work, we introduce a framework which unifies the two seemingly orthogonal heuristics and allows us to quantify the interpolation between them. More generally, the framework enables a well principled design of scalable, streaming graph partitioning algorithms that are amenable to distributed implementations. We derive a novel one-pass, streaming graph partitioning algorithm and show that it yields significant performance improvements over previous approaches using an extensive set of real-world and synthetic graphs. Surprisingly, despite the fact that our algorithm is a one-pass streaming algorithm, we found its performance to be in many cases comparable to the {\it de-facto} standard offline software METIS and in some cases even superiror. For instance, for the Twitter graph with more than 1.4 billion of edges, our method partitions the graph in about 40 minutes achieving a balanced partition that cuts as few as 6.8\% of edges, whereas it took more than 8$\tfrac{1}{2}$ hours by METIS to produce a balanced partition that cuts 11.98\% of edges. We also demonstrate the performance gains by using our graph partitioner while solving standard PageRank computation in a graph processing platform with respect to the communication cost and runtime.
  • Raja Appuswamy, Christos Gkantsidis, Dushyanth Narayanan, Orion Hodson, and Antony Rowstron, Scale-up vs Scale-out for Hadoop: Time to rethink?, ACM Symposium on Cloud Computing, 2 October 2013
    n the last decade we have seen a huge deployment of cheap clusters to run data analytics workloads. The conventional wisdom in industry and academia is that scaling out using a cluster of commodity machines is better for these workloads than scaling up by adding more resources to a single server. Popular analytics infrastructures such as Hadoop are aimed at such a cluster scale-out environment. Is this the right approach? Our measurements as well as other recent work shows that the majority of real-world analytic jobs process less than 100 GB of input, but popular infrastructures such as Hadoop/MapReduce were originally designed for petascale processing. We claim that a single “scale-up” server can process each of these jobs and do as well or better than a cluster in terms of performance, cost, power, and server density. We present an evaluation across 11 representative Hadoop jobs that shows scale-up to be competitive in all cases and significantly better in some cases, than scale-out. To achieve that performance, we describe several modifications to the Hadoop runtime that target scale-up configuration. These changes are transparent, do not require any changes to application code, and do not compromise scale-out performance; at the same time our evaluation shows that they do significantly improve Hadoop’s scale-up performance.
  • Konstantinos Pelechrinis, Prashant Krishanmurthy, and Christos Gkantsidis, Trustworthy Operations in Cellular Networks: The case of PF Scheduler , in IEEE Transactions on Parallel and Distributed Systems, vol. PP, no. 99, IEEE, May 2013
    Cellular data networks are proliferating to address the need for ubiquitous connectivity. To cope with the increasing number of subscribers and with the spatio-temporal variations of the wireless signals, current cellular networks use opportunistic schedulers, such as the Proportional Fairness scheduler (PF), to maximize network throughput while maintaining fairness among users. Such scheduling decisions are based on channel quality metrics and Automatic Repeat reQuest (ARQ) feedback reports provided by the User’s Equipment (UE). Implicit in current networks is the a priori trust on every UE's feedback. Malicious UEs can thus exploit this trust to disrupt service by intelligently faking their reports. This work proposes a trustworthy version of the PF scheduler (called TPF) to mitigate the effects of such Denial-of-Service (DoS) attacks. In brief, based on the channel quality reported by the UE, we assign a probability to possible ARQ feedbacks. We then use the probability associated with the actual ARQ report to assess the UE's reporting trustworthiness. We adapt the scheduling mechanism to give higher priority to more trusted users. Our evaluations show that TPF (i) does not induce any performance degradation under benign settings, and (ii) it completely mitigates the effects of the activity of malicious UEs.
  • Christos Gkantsidis, Dimitrios Vytiniotis, Orion Hodson, Dushyanth Narayanan, Florin Dinu, and Antony Rowstron, Rhea: automatic filtering for unstructured cloud storage, in 10th USENIX Symposium on Networked Systems Design and Implementation (NSDI ’13) , USENIX, 4 April 2013
    Unstructured storage and data processing using platforms such as MapReduce are increasingly popular for their simplicity, scalability, and flexibility. Using elastic cloud storage and computation makes them even more attractive. However cloud providers such as Amazon and Windows Azure separate their storage and compute resources even within the same data center. Transferring data from storage to compute thus uses core data center network bandwidth, which is scarce and oversubscribed. As the data is unstructured, the infrastructure cannot automatically apply selection, projection, or other filtering predicates at the storage layer. The problem is even worse if customers want to use compute resources on one provider but use data stored with other provider(s). The bottleneck is now the WAN link which impacts performance but also incurs egress bandwidth charges. This paper presents Rhea, a system to automatically generate and run storage-side data filters for unstructured and semi-structured data. It uses static analysis of application code to generate filters that are safe, stateless, side effect free, best effort, and transparent to both storage and compute layers. Filters never remove data that is used by the computation. Our evaluation shows that Rhea filters achieve a reduction in data transfer of 2x–20,000x, which reduces job run times by up to 5x and dollar costs for cross-cloud computations by up to 13x.
  • Raja Appuswamy, Christos Gkantsidis, Dushyanth Narayanan, Orion Hodson, and Antony Rowstron, Nobody ever got fired for buying a cluster, no. MSR-TR-2013-2, 2 January 2013
    In the last decade we have seen a huge deployment of cheap clusters to run data analytics workloads. The conventional wisdom in industry and academia is that scaling out using a cluster is better for these workloads than scaling up by adding more resources to a single server. Popular analytics infrastructures such as Hadoop are aimed at such a cluster scale-out environment, and in today's world nobody gets fired for adopting a cluster solution. Is this the right approach? Our measurements as well as other recent work shows that the majority of real-world analytic jobs process less than 100GB of input, but popular infrastructures such as Hadoop/MapReduce were originally designed for petascale processing. We claim that a single "scale-up" server can process each of these jobs and do as well or better than a cluster in terms of performance, cost, power, and server density. Is it time to consider the "common case" for "big data" analytics to be the single-server rather than the cluster case? If so, this has implications for data center hardware as well as software architectures. Unfortunately widely used platforms such as Hadoop perform poorly in a scale-up configuration. We describe several modifications to the Hadoop runtime to address this problem. These changes are transparent, do not require any changes to application code, and do not compromise scale-out performance. However they do significantly improve Hadoop's scale-up performance. We present a broad evaluation across 11 representative Hadoop jobs that shows scale-up to be competitive in all cases and significantly better in some cases, than scale-out. Our evaluation considers raw performance, as well as performance per dollar and per watt.
  • Charalampos E. Tsourakakis, Christos Gkantsidis, Bozidar Radunovic, and Milan Vojnovic, Fennel: Streaming Graph Partitioning for Massive Scale Graphs, no. MSR-TR-2012-113, November 2012
    Graph partitioning is a key problem to enable efficient solving of a wide range of computational tasks and querying over large-scale graph data, such as computing node centralities using iterative computations, and personalized recommendations. In this work, we introduce a unifying framework for graph partitioning which enables a well principled design of scalable, streaming graph partitioning algorithms that are amenable to distributed implementation. We show that many previously proposed methods are special instances of this framework, we derive a novel one-pass, streaming graph partitioning algorithm and show that it yields significant benefits over previous approaches, using a large set of real-world and synthetic graphs. Surprisingly, despite the fact that our algorithm is a one-pass streaming algorithm, we found its performance to be overall comparable to the de-facto standard offline software METIS, and it even outperforms it on numerous real-world graphs. For instance, for the Twitter graph with more than 1.4 billion of edges, our method partitions the graph in about 40 minutes achieving a balanced partition that cuts as few as 6.8% of edges, whereas it took more than 8.5 hours by METIS to produce a balanced partition that cuts 11.98% of edges. Furthermore, modularity--a popular measure for community detection [Girvan and Newman, 2002; Newman and Girvan, 2004; Newman, 2006]--is also a special instance of our framework. We establish the first rigorous approximation algorithm, achieving a guarantee of O(log(k)/k) for partitioning into k clusters. Finally, we evaluate the performance gains by using our graph partitioner while solving standard PageRank computation in a graph processing platform, and observe significant gains in terms of the communication cost and runtime.
  • Konstantinos Pelechrinis, Ioannis Broustis, Srikanth V. Krishnamurthy, and Christos Gkantsidis, A Measurement-Driven Anti-Jamming System for 802.11 Networks, in IEEE/ACM Transactions on Networking, ACM/IEEE, August 2011
    Dense, unmanaged IEEE 802.11 deployments tempt saboteurs into launching jamming attacks by injecting malicious interference. Nowadays, jammers can be portable devices that transmit intermittently at low power in order to conserve energy. In this paper, we first conduct extensive experiments on an indoor 802.11 network to assess the ability of two physical-layer functions, rate adaptation and power control, in mitigating jamming. In the presence of a jammer, we find that: 1) the use of popular rate adaptation algorithms can significantly degrade network performance; and 2) appropriate tuning of the carrier sensing threshold allows a transmitter to send packets even when being jammed and enables a receiver to capture the desired signal. Based on our findings, we build ARES, an Anti-jamming REinforcement System, which tunes the parameters of rate adaptation and power control to improve the performance in the presence of jammers. ARES ensures that operations under benign conditions are unaffected. To demonstrate the effectiveness and generality of ARES, we evaluate it in three wireless test-beds: 1) an 802.11n WLAN with MIMO nodes; 2) an 802.11a/g mesh network with mobile jammers; and 3) an 802.11a WLAN with TCP traffic. We observe that ARES improves the network throughput across all test-beds by up to 150%.
  • Christos Gkantsidis and Hitesh Ballani, Network Management as a Service, no. MSR-TR-2010-83, 24 June 2010
    This paper explores the feasibility of offering network management as a service. We describe availability and responsiveness as the two key factors that govern how functionality is moved off-site (to the cloud). Using common management tasks as examples, we describe the process and the challenges of designing their cloud-based equivalents. We also examine the costs of such off-site implementations.
  • Thomas Karagiannis, Christos Gkantsidis, Dushyanth Narayanan, and Antony Rowstron, Hermes: Clustering Users in Large-Scale E-mail Services, in ACM Symposium on Cloud Computing 2010 (ACM SOCC 2010), Association for Computing Machinery, Inc., 10 June 2010
    Hermes is an optimization engine for large-scale enterprise e-mail services. Such services could be hosted by a virtualized e-mail service provider, or by dedicated enterprise data centers. In both cases we observe that the pattern of e-mails between employees of an enterprise forms an implicit social graph. Hermes tracks this implicit social graph, periodically identifies clusters of strongly connected users within the graph, and co-locates such users on the same server. Co-locating the users reduces storage requirements: senders and recipients who reside on the same server can share a single copy of an e-mail. Co-location also reduces inter-server bandwidth usage. We evaluate Hermes using a trace of all e-mails within a major corporation over a five month period. The e-mail service supports over 120,000 users on 68 servers. Our evaluation shows that using Hermes results in storage savings of 37% and bandwidth savings of 50% compared to current approaches. The overheads are low: a single commodity server can run the optimization for the entire system.
  • Marshini Chetty, Richard Banks, Richard Harper, Tim Regan, Abigail Sellen, Christos Gkantsidis, Thomas Karagiannis, and Peter Key, Who's Hogging the Bandwidth?: The Consequences Of Revealing The Invisible In the Home, in CHI 2010, Association for Computing Machinery, Inc., 10 April 2010
    As more technologies enter the home, householders are burdened with the task of digital housekeeping—managing and sharing digital resources like bandwidth. In response to this, we created a domestic tool for bandwidth management called Home Watcher. Our field trial of Home Watcher showed that when resource contention amongst different household members is made visible, people's understanding of bandwidth changes and household politics are revealed. In this paper, we describe the consequences of showing real time resource usage in a home, and how this varies depending on the social make up of the household.
  • Christos Gkantsidis, Thomas Karagiannis, Peter Key, Bozidar Radunovic, Elias Raftopoulos, and D. Manjunath, Traffic management and resource allocation in small wired/wireless networks, in Fifth ACM International Conference on emerging Networking EXperiments and Technologies (CoNEXT 2009) , Association for Computing Machinery, Inc., December 2009
    We consider the problem of traffic management in small networks with both wireless and wired devices, connected to the Internet through a single gateway. Examples of such networks are small office networks or residential networks, where typically traffic management is limited to flow prioritization through port-based filtering. We propose a practical resource allocation framework that provides simple mechanisms to applications and users to enable traffic management functionality currently not present due to the distributed nature of the system and various technology or protocol limitations. To allow for control irrespective of whether traffic flows cross wireless, wired or even broadband links, the proposed framework jointly optimizes rate allocations across wireless and wired devices in a weighted fair manner. Additionally, we propose a model for estimating the achievable capacity regions in wireless networks to overcome the absence of the queue information. This model is used by the controller to achieve a specific rate allocation. We evaluate a decentralized, host-based implementation of the proposed framework. The controller is incrementally deployable by not requiring modifications to existing network protocols and equipment or the wireless MAC. Using analytical methods and experimental results with realistic traffic, we show that our controller is stable with fast convergence for both UDP and TCP traffic, achieves weighted fairness, and mitigates scheduling inefficiencies of the existing hardware.
  • Milan Vojnovic, Varun Gupta, Thomas Karagiannis, and Christos Gkantsidis, Sampling Strategies for Epidemic-Style Information Dissemination, in to appear ACM/IEEE Trans. on Networking, Association for Computing Machinery, Inc., August 2009
    We consider epidemic-style information dissemination strategies that leverage the nonuniformity of host distribution over subnets (e.g., IP subnets) to optimize the information spread. Such epidemic-style strategies are based on random sampling of target hosts according to a sampling rule. In this paper, the objective is to optimize the information spread with respect to minimizing the total number of samplings to reach a target fraction of the host population. This is of general interest for the design of efficient information dissemination systems and more specifically, to identify requirements for the containment of worms that use subnet preference scanning strategies. We first identify the optimum number of samplings to reach a target fraction of hosts, given perfect prior information about the host distribution over subnets. We show that the optimum can be achieved by either a dynamic strategy for which the per host sampling rate over subnets is allowed to vary over time or by a static strategy for which the sampling over subnets is fixed. These results appear to be novel and are informative about (a) what best possible performance is achievable and (b) what factors determine the performance gain over oblivious strategies such as uniform random scanning. We then propose and analyze simple, online strategies that require no prior knowledge, where each host biases sampling based on its observed sampling attempts by keeping only order O(1) state at any point in time. Using real datasets from several large-scale Internet measurements, we show that these simple, online schemes provide near-optimal performance.
  • Bozidar Radunovic, Christos Gkantsidis, Peter Key, and Pablo Rodriguez, Toward Practical Opportunistic Routing with Intra-session Network Coding for Mesh Networks, in ACM/IEEE Transactions on Networking, IEEE/ACM Transactions on Networking, 2009
    We consider opportunistic routing in wireless mesh networks. We exploit the inherent diversity of the broadcast nature of wireless by making use of multi-path routing. We present a novel optimization framework for opportunistic routing based on network utility maximization (NUM) that enables us to derive optimal flow control, routing, scheduling, and rate adaptation schemes, where we use network coding to ease the routing problem. All previous work on NUM assumed unicast transmissions; however, the wireless medium is by its nature broadcast and a transmission will be received by multiple nodes. The structure of our design is fundamentally different; this is due to the fact that our link rate constraints are defined per broadcast region instead of links in isolation. We prove optimality and derive a primal-dual algorithm that lays the basis for a practical protocol. Optimal MAC scheduling is difficult to implement, and we use 802.11-like random scheduling rather than optimal in our comparisons. Under random scheduling, our protocol becomes fully decentralized (we assume ideal signaling). The use of network coding introduces additional constraints on scheduling, and we propose a novel scheme to avoid starvation. We simulate realistic topologies and show that we can achieve 20-200% throughput improvement compared to single path routing, and several times compared to a recent related opportunistic protocol (MORE).
  • Thomas Karagiannis, Christos Gkantsidis, Peter Key, Elias Athanasopoulos, and Elias Raftopoulos, HomeMaestro: Distributed monitoring and diagnosis of performance anomalies in home networks, no. MSR-TR-2008-161, 29 October 2008
    Home networks are comprised of applications running over multiple wired and wireless devices competing for shared network resources. Despite all the devices operating in a single administrative domain in such networks, applications operate independently, and users cannot express or enforce policies. By studying multiple households’ network performance at the packet-level correlated with diaries capturing user experiences, we show that the lack of cooperation across applications leads to observable performance problems and associated user frustration. We describe HomeMaestro, a cooperative host-based system that monitors local and global application performance, and automatically detects contention for network resources. HomeMaestro is designed to manage home and small networks and requires no modification to routers, access points, applications, or protocols. At each host, it transparently monitors per-flow and per-process network usage statistics, such as throughput, RTT, and loss rates. We propose novel
  • Bozidar Radunovic, Christos Gkantsidis, Dinan Gunawardena, and Peter Key, Horizon: Balancing TCP over Multiple Paths in Wireless Mesh Network, in MobiCom'08, Association for Computing Machinery, Inc., 14 September 2008
    There has been extensive work on network architectures that support multi-path routing to improve performance in wireless mesh networks. However, previous work uses ad-hoc design principles that cannot guarantee any network-wide performance objectives such as conjointly maximizing resource utilization and improving fairness. In parallel, numerous theoretical results have addressed the issue of optimizing a combined metric of network utilization and fairness using techniques based on back-pressure scheduling, routing and flow control. However, the proposed theoretical algorithms are extremely difficult to implement in practice, especially in the presence of the 802.11 MAC and TCP. We propose Horizon, a novel system design for multi-path forwarding in wireless meshes, based on the theoretical results on back-pressure. Our design works with an unmodified TCP stack and on top of the existing 802.11 MAC. We modified the backpressure approach to obtain a simple 802.11-compatible packetforwarding heuristic and a
  • Thomas Karagiannis, Elias Athanasopoulos, Christos Gkantsidis, and Peter Key, HomeMaestro: Order from Chaos in Home Networks, no. MSR-TR-2008-84, May 2008
    We present HomeMaestro, a distributed system for monitoring and instrumentation of home networks. HomeMaestro performs extensive measurements at the host level to infer application network requirements, and identifies network-related problems through time-series analysis. By sharing and correlating information across hosts in the home network, our system automatically detects and resolves contention over network resources among applications based on predefined policies. Finally, HomeMaestro implements a distributed virtual queue to enforce those policies by prioritizing applications without additional assistance from network equipment such as routers or access points. We outline the challenges in managing home networks, describe the design choices and architecture of our system, and highlight the performance of HomeMaestro components in typical home scenarios.
  • Milan Vojnović, Varun Gupta, Thomas Karagiannis, and Christos Gkantsidis, Sampling Strategies for Epidemic-Style Information Dissemination, in IEEE INFOCOM, IEEE Communications Society, April 2008
    We consider epidemic-style information dissemination strategies that leverage the nonuniformity of host distribution over subnets (e.g., IP subnets) to optimize the information spread. Such epidemic-style strategies are based on random sampling of target hosts according to a sampling rule. In this paper, the objective is to optimize the information spread with respect to minimizing the total number of samplings to reach a target fraction of the host population. This is of general interest for the design of efficient information dissemination systems and more specifically, to identify requirements for the containment of worms that use subnet preference scanning strategies. We first identify the optimum number of samplings to reach a target fraction of hosts, given perfect prior information about the host distribution over subnets. We show that the optimum can be achieved by either a dynamic strategy for which the per host sampling rate over subnets is allowed to vary over time or by a static strategy for which the sampling over subnets is fixed. These results appear to be novel and are informative about (a) what best possible performance is achievable and (b) what factors determine the performance gain over oblivious strategies such as uniform random scanning. We then propose and analyze simple, online strategies that require no prior knowledge, where each host biases sampling based on its observed sampling attempts by keeping only order O(1) state at any point in time. Using real datasets from several large-scale Internet measurements, we show that these simple, online schemes provide near-optimal performance.
  • Milan Vojnovic, Varun Gupta, Thomas Karagiannis, and Christos Gkantsidis, Sampling Strategies for Epidemic-Style Information Dissemination, no. MSR-TR-2007-82, February 2008
    We consider epidemic-style information dissemination strategies that leverage the nonuniformity of host distribution over subnets (e.g., IP subnets) to optimize the information spread. Such epidemic-style strategies are based on random sampling of target hosts according to a sampling rule. In this paper, the objective is to optimize the information spread with respect to minimizing the total number of samplings to reach a target fraction of the host population. This is of general interest for the design of efficient information dissemination systems and more specifically, to identify requirements for the containment of worms that use subnet preference scanning strategies.fl We first identify the optimum number of samplings to reach a target fraction of hosts, given global information about the host distribution over subnets. We show that the optimum can be achieved by either a dynamic strategy for which the per host sampling rate over subnets is allowed to vary over time or by a static strategy for which the sampling over subnets is fixed. These results appear to be novel and are informative about (a) what best possible performance is achievable and (b) what factors determine the performance gain over oblivious strategies such as uniform random scanning. We then consider several simple, online sampling strategies that require only local knowledge,fl where each host biases sampling based on its observed sampling outcomes and keeps only O(1) state at any point in time. Using real datasets from several large-scale Internet measurements, we evaluate the significance of the factors revealed by our analyticalfl results on the sampling efficiency.
  • Bozidar Radunovic, Christos Gkantsidis, Peter Key, and Pablo Rodriguez, An Optimization Framework for Opportunistic Multipath Routing in Wireless Mesh Networks, in INFOCOM Minisymposium, 2008
  • Christos Gkantsidis, Bozidar Radunovic, Peter Key, Steluta Gheorgiu, Wenjun Hu, and Pablo Rodriguez, Multipath Code Casting for Wireless Mesh Networks, no. MSR-TR-2007-67, June 2007
    Designing high throughput wireless mesh networks is a challenge, and involves solving interrelated scheduling, routing, and interference problems. In this paper, we exploit the fundamental properties of broadcast medium and path diversity in wireless meshes to implement multipath routing between a source and destination pair. We use network coding for a given unicast source-destination flow to ease the scheduling problem, exploit diversity, and deal with unreliable transmissions. We describe multipath-forwarding algorithms, and show their performance benefits over existing proposals, using simulation, analysis, and a prototype implementation on a small testbed. We propose a rate-scheduling protocol that relies on network coding, which gives over 30% performance improvement for a realistic topology and can double the throughput in certain cases.
  • Bozidar Radunovic, Christos Gkantsidis, Peter Key, Pablo Rodriguez, and Wenjun Hu, An optimization framework for practical multipath routing in wireless mesh networks, no. MSR-TR-2007-81, June 2007
    We consider wireless mesh networks, and exploit the inherent broadcast nature of wireless by making use of multipath routing. We present an optimization framework that enables us to derive optimal flow control, routing, scheduling, and rate adaptation schemes, where we use network coding to ease the routing problem. We prove optimality and derive a primal-dual algorithm that lays the basis for a practical protocol. Optimal MAC scheduling is difficult to implement, and we use random scheduling rather than optimal for comparisons. Under random scheduling, our protocol becomes fully decentralised. We use simulation to show on realistic topologies that we can achieve 20-200% throughput improvement compared to single path routing, and several times compared to a recent related opportunistic protocol (MORE).
  • Christos Gkantsidis, Gagan Goel, Milena Mihail, and Amin Saberi, Towards Topology Aware Networks, IEEE Communications Society, May 2007
    We focus on efficient protocols that enhance a network with topology awareness. We discuss centralized algorithms with provable performance, and introduce decentralized asynchronous heuristics that use only local information and local computations. These algorithms are based on distributed solutions of convex programs expressing optimization of various spectral properties of the matrix associated with the graph of the network topology. For example, these algorithms assign special weights to links crossing or directed towards small cuts by minimizing the second eigenvalue. Our main technical ingredient is to perform the decentralized asynchronous computations in a manner that preserves critical invariants of the exact second eigenvalue of the adjacency matrix associated with the network topology.
  • Laurent Massoulié, Andy Twigg, Christos Gkantsidis, and Pablo Rodriguez, Decentralized Broadcasting Algorithms, IEEE Communications Society, May 2007
    We consider the problem of broadcasting a live stream of data in an unstructured network. The broadcasting problem has been studied extensively for edge-capacitated networks. We give the first proof that whenever demand ? + e is feasible for e > 0, a simple local-control algorithm is stable under demand ?, and as a corollary a famous theorem of Edmonds. We then study the node-capacitated case and show a similar optimality result for the complete graph. We study through simulation the delay that users must wait in order to playback a video stream with a small number of skipped packets, and discuss the suitability of our algorithms for live video streaming.
  • Siddhartha Annapureddy, Saikat Guha, Christos Gkantsidis, Dinan Gunawardena, and Pablo Rodriguez, Exploring VoD in P2P Swarming Systems, IEEE Communications Society, May 2007
    Digital media companies have recently started embracing P2P networks as an alternative distribution mechanism. However, with current P2P swarming systems users need to download the full video, and hence have to wait a long time before they can start watching it. While a lot of effort has gone into optimizing the distribution of large files, little research has been done on enabling Video-on-Demand (VoD) functionality with P2P swarming systems. The main challenges reside in ensuring that users can start watching a movie at any point in time, with small start-up times and sustainable playback rates. In this work, we address the issues of providing VoD using P2P mesh-based networks. We investigate scheduling techniques, and network coding in particular. Using both simulations and a prototype implementation, we show that high-quality VoD is feasible, and give guidelines to build play-as-you-download P2P swarming systems with high playback rates and low start-up delays.
  • Christos Gkantsidis, John Miller, and Pablo Rodriguez, Comprehensive view of a live network coding P2P system, in IMC, Association for Computing Machinery, Inc., October 2006
    In this paper we present the first implementation of a P2P content distribution system that uses Network Coding. Using results from live trials with several hundred nodes, we provide a detailed performance analysis of such P2P system. In contrast to prior work, which mainly relies on monitoring P2P systems at particular locations, we are able to provide performance results from a variety of novel angles by monitoring all components in the P2P distribution.In particular, we show that Network Coding is practical in a P2P setting since it incurs little overhead, both in terms of CPU processing and IO activity, and it results in smooth, fast downloads, and efficient server utilization. We also study the importance of topology construction algorithms in real scenarios and study the effect of peers behind NATs and firewalls, showing that the system is surprisingly robust to large number of unreachable peers. Finally, we present performance results related to verifying network encoded blocks on-the-fly using special security primitives called Secure-Random-Checksums.
  • C. Gkantsidis, T. Karagiannis, P. Rodriguez, and M. Vojnovic, Planet Scale Software Updates, in ACM SIGCOMM, Association for Computing Machinery, Inc., September 2006
    Fast and effective distribution of software updates (a.k.a. patches) to millions of Internet users has evolved into a critical task over the last years. In this paper, we characterize “Windows Update”, one of the largest update services in the world, with the aim to draw general guidelines on how to best design and architect a fast and effective planet-scale patch dissemination system. To this end, we analyze an extensive set of data traces collected over the period of a year, consisting of billions of queries from over 300 million computers. Based on empirical observations and analytical results, we identify interesting properties of today’s update traffic and user behavior. Building on this analysis, we consider alternative patch delivery strategies such as caching and peer-to-peer and evaluate their performance. We identify key factors that determine the effectiveness of these schemes in reducing the server workload and the network traffic, and in speeding-up the patch delivery. Most of our findings are invariant properties induced by either user behavior or architectural characteristics of today’s Internet, and thus apply to the general problem of Internet-wide dissemination of software updates.
  • Christos Gkantsidis, Thomas Karagiannis, Pablo Rodriguez, and Milan Vojnovic, Planet Scale Software Updates, no. MSR-TR-2006-85, August 2006
    Fast and effective distribution of software updates (a.k.a. patches) to millions of Internet users has evolved into a critical task over the last years. In this paper, we characterize “Windows Update”, one of the largest update services in the world, with the aim to draw general guidelines on how to best design and architect a fast and effective planet-scale patch dissemination system. To this end, we analyze an extensive set of data traces collected over the period of a year, consisting of billions of queries from over 300 million computers. Based on empirical observations and analytical results, we identify interesting properties of today’s update traffic and user behavior.fl Building on this analysis, we consider alternative patch delivery strategies such as caching and peer-to-peer and evaluate their performance. We identify key factors that determine the effectiveness of these schemes in reducing the server workload and the network traffic, and in speeding-up the patch delivery. Most of our findings are invariant properties induced by either user behavior or architectural characteristics of today’s Internet, and thus apply to the general problem of Internet-wide dissemination of software updates.
  • Christos Gkantsidis, Laurent Massoulié, Pablo Rodriguez, and Andy Twigg, Provably optimal decentralised broadcast algorithms, no. MSR-TR-2006-105, July 2006
    In this paper we consider the problem of broadcasting information from a source node to a set of receiver nodes. In the context of edge-capacitated networks, we consider the "random useful" packet forwarding algorithm. We prove that it yields a stable system, provided the data injection rate at the source node is less than the (min(min-cut)) of the graph. As a corollary we retrieve a famous theorem of Edmonds. We next consider node-capacitated networks. In this context we introduce the "random useful to most deprived neighbour" packet forwarding scheme. We show that it yields a stable system in the particular case where the network graph is the complete graph, whenever the node capacities are large enough for centralised schemes to achieve successful broadcast of the data injection rate.
  • C. Gkantsidis and P. Rodriguez, Cooperative Security for Network Coding File Distribution, in IEEE/Infocom Barcelona, IEEE Communications Society, April 2006
    Peer-to-peer content distribution networks can suffer from malicious participants that intentionally corrupt content. Some systems such as BitTorrent verify blocks with traditional cryptographic signatures and hashes. However, these techniques do not apply well to more elegant systems that use network coding techniques for efficient content distribution. Architectures that use network coding are prone to jamming attacks where the introduction of a few corrupted blocks can quickly result in a large number of bad blocks propagating through the system. Identifying such bogus blocks is difficult and requires the use of homomorphic hashing functions, which are computationally expensive. This paper presents a practical security scheme for network coding that reduces the cost of verifying blocks on-the-fly while efficiently preventing the propagation of malicious blocks. In our scheme, users not only cooperate to distribute the content, but (well-behaved) users also cooperate to protect themselves against malicious users by informing affected nodes when a malicious block is found. We analyze and study such cooperative security scheme and introduce elegant techniques to prevent DoS attacks. We show that the loss in the efficiency caused by the attackers is limited to the effort the attackers put to corrupt the communication, which is a natural lower bound in the damage of the system.
  • C. Gkantsidis, John Miller, and P. Rodriguez, Anatomy of a P2P Content Distribution System with Network Coding, in IPTPS'06, February 2006
  • Siddhartha Annapureddy, Christos Gkantsidis, and Pablo Rodriguez, Providing Video-on-Demand using Peer-to-Peer Networks, in IPTV Services over World Wide Web, January 2006
    Digitalmedia companies have recently started embracing peer-assisted distribution networks as an alternative to traditional client-server architectures [5]. Such Peer-to-Peer (P2P) architectures ensure a fast and scalable delivery of media content. However, their drawback is that users need to often wait for the full video to be downloaded before they can start watching it. While a lot of effort has gone into optimizing the distribution of large video files using P2P swarming techniques, little research has been done on how to ensure a small start-up time and a sustainable playback rate to enable a play-asyou- download experience. In this work, we address the challenges underlying the problemof near Video-on-Demand (nVoD) using P2P swarming systems, and provide evidence that high-quality nVoD is feasible. In particular, we investigate the scheduling problem of efficiently disseminating the blocks of a video file in a P2P mesh-based system, and show that pre-fetching and network coding techniques can provide significant benefits. Our results show that, for videos which are 120 minutes in duration, 10 minutes (8% of the video’s length) of buffering at start-up can enable playback rates that are close (up to 80 - 90%) to the access link capacity, even under dynamic changes of the user population.
  • P Rodriguez, See-Mong Tan, and C. Gkantsidis, On the feasibility of commercial, legal P2P Content Distribution, in ACM/SIGCOMM CCR Journal, January 2006
    A spirited panel was recently held at the 10th International Web Caching and Content Distribution workshop on the future of P2P in content distribution [1]. After more than ten years of content distribution research and technology efforts, P2P is emerging as an alternative solution to solve the mass distribution of large digital content. However, using P2P for commercial content distribution faces a number of serious challenges. Issues such as content protection, impact on ISPs, security, end-to-end connectivity, and business models need careful consideration before P2P an be used as an efficient tool by content providers. In this paper, we summarize the issues brought up in discussion, and delve deeper into the feasibility of commercial, legal P2P content distribution solutions.
  • Christos Gkantsidis and Pablo Rodriguez, Network Coding for Large Scale Content Distribution, in IEEE INFOCOM, March 2005
    We propose a new scheme for content distribution of large files that is based on network coding. With network coding, each node of the distribution network is able to generate and transmit encoded blocks of information. The randomization introduced by the coding process eases the scheduling of block propagation, and, thus, makes the distribution more efficient. This is particularly important in large unstructured overlay networks, where the nodes need to make decisions based on local information only. We compare network coding to other schemes that transmit unencoded information (i.e. blocks of the original file) and, also, to schemes in which only the source is allowed to generate and transmit encoded packets. We study the performance of network coding in heterogeneous networks with dynamic node arrival and departure patterns, clustered topologies, and when incentive mechanisms to discourage free-riding are in place. We demonstrate through simulations of scenarios of practical interest that the expected file download time improves by more than 20-30% with network coding compared to coding at the server only and, by more than 2-3 times compared to sending unencoded information. Moreover, we show that network coding improves the robustness of the system and is able to smoothly handle extreme situations where the server and nodes departure the system.
  • Christos Gkantsidis, Milena Mihail, and Amin Saberi, Hybrid Search Schemes for Unstructured Peer-to-Peer Networks, in IEEE Infocom, January 2005
  • Christos Gkantsidis, Milena Mihail, and Amin Saberi, Random Walks in Peer-to-Peer Networks, in IEEE Infocom, January 2004
  • Christos Gkantsidis, Ammar Mostafa, and Ellen Zegura, On the Effect of Large-Scale Deployment of Parallel Downloading, in IEEE Workshop on Internet Applications (WIAPP'03), January 2003
  • Christos Gkantsidis, Milena Mihail, and Ellen Zegura, Spectral Analysis of Internet Topologies, in IEEE Infocom, January 2003
  • Christos Gkantsidis, Milena Mihail, and Amin Saberi, Conductance and Congestion in Power Law Graphs, in ACM SIGMETRICS, ACM Press, January 2003
    It has been observed that the degrees of the topologies of several communication networks follow heavy tailed statistics. What is the impact of such heavy tailed statistics on the performance of basic communication tasks that a network is presumed to support? How does performance scale with the size of the network? We study routing in families of sparse random graphs whose degrees follow heavy tailed distributions. Instantiations of such random graphs have been proposed as models for the topology of the Internet at the level of Autonomous Systems as well as at the level of routers. Let n be the number of nodes. Suppose that for each pair of nodes with degrees du and dv we have O(du dv) units of demand. Thus the total demand is O(n2). We argue analytically and experimentally that in the considered random graph model such demand patterns can be routed so that the flow through each link is at most O(n log2 n). This is to be compared with a bound O(n2) that holds for arbitrary graphs. Similar results were previously known for sparse random regular graphs, a.k.a. "expander graphs." The significance is that Internet-like topologies, which grow in a dynamic, decentralized fashion and appear highly inhomogeneous, can support routing with performance characteristics comparable to those of their regular counterparts, at least under the assumption of uniform demand and capacities. Our proof uses approximation algorithms for multicommodity flow and establishes strong bounds of a generalization of "expansion," namely "conductance." Besides routing, our bounds on conductance have further implications, most notably on the gap between first and second eigenvalues of the stochastic normalization of the adjacency matrix of the graph.
  • Christos Gkantsidis, Milena Mihail, and Ellen Zegura, The Markov Chain Simulation Method for Generating Connected Power Law Random Graphs, in SIAM Alenex, January 2003