Algorithms for interactive, distributed and networked systems

Network algorithms;Interactive communication;Communication complexity;Protocol compression;Scheduling;Circuit switch;Data center networks;Submodularity;Peer-to-peer;Streaming;Topology;Bitcoin;Anonymity;Distributed algorithms;Cryptocurrency

Bojja Venkatakrishnan, Shaileshh

关键词: Network algorithms;    Interactive communication;    Communication complexity;    Protocol compression;    Scheduling;    Circuit switch;    Data center networks;    Submodularity;    Peer-to-peer;    Streaming;    Topology;    Bitcoin;    Anonymity;    Distributed algorithms;    Cryptocurrency;   

Others  :  https://www.ideals.illinois.edu/bitstream/handle/2142/98367/BOJJAVENKATAKRISHNAN-DISSERTATION-2017.pdf?sequence=1&isAllowed=y

美国|英语

来源: The Illinois Digital Environment for Access to Learning and Scholarship

【 摘 要 】

In recent years, massive growth in internet usage has spurred the emergence of complex large-scale networking systems to serve growing user bases, bandwidth and computation requirements. For example, data center facilities -- workhorses of today's internet -- have evolved to house upward of several hundreds of thousands of servers; content distribution networks with high capacity and wide coverage have emerged as a de facto content dissemination modality, and peer-to-peer applications with hundreds of thousands of users are increasingly becoming popular. At these scales, it becomes critical to operate at high efficiencies as the price of idling resources can be significant. In particular, the interaction between agents (servers, peers etc.) is a defining factor of efficiency in these systems -- applications are often communication intensive, whereas agents share links of only limited bandwidth. This necessitates the use of principled algorithms, as efficient communication to a large extent depends on the interaction protocols. We study data center networks and peer-to-peer networks as canonical examples of modern-day large-scale networking systems. Server-to-server interaction is an integral part of the data center's operation. The latency of these interactions is often a significant bottleneck toward overall job completion times. We study complementary approaches toward reducing this latency: (i) design of computation algorithms that minimize interaction and (ii) optimal scheduling algorithms to maximally utilize the network fabric. We also consider peer-to-peer networks as an emerging mode of content distribution and sharing. Unlike data centers, these networks are flexible in their network structure and also scale well, but require decentralized algorithms for control. Of central importance here is the design of a network topology that enables efficient peer interactions for optimal application performance. We propose novel topology designs for two popular applications: (i) multimedia streaming and (ii) anonymity in Bitcoin's peer-to-peer network.