Streaming big data meets backpressure in distributed network computation

摘要

We study network response to a stream of queries that require computations on remotely located data, and we seek to characterize the network performance limits in terms of maximum sustainable query rate that can be satisfied. The available network setup consists of (i) a communication network graph with finite-bandwidth links over which data is routed, (ii) computation nodes with certain computation capacity, over which computation load is balanced, and (iii) network nodes that need to schedule raw and processed data transmissions. Our aim is to design a universal methodology and distributed algorithm to adaptively allocate resources in order to support maximum query rate. The proposed algorithms extend in a nontrivial way the backpressure (BP) algorithm to take into account computations carried out in the presence of query streams. They contribute to the fundamental understanding of network computation performance limits when the query rate is limited by both the communication bandwidth and the computation capacity, a classical setting that arises in streaming big data applications in network clouds and fogs.