We analyze the effect of sponsored data when Internet service providers (ISPs) compete for subscribers and content providers (CPs) compete for a share of the bandwidth usage by customers. Our model is of a full information, leader-follower game. ISPs lead and set sponsorship prices. CPs then make the binary decision of sponsoring or not sponsoring their content on the ISPs. Lastly, based on both of these, users make a two-part decision-choose the ISP to subscribe to, and amount of data to consume from each CPs through the chosen ISP. User consumption is determined by a utility maximization framework, sponsorship decision is determined by a non-cooperative game between CPs, and ISPs set their prices to maximize their profit in response to prices set by competing ISP. We analyze the dynamics of the prices set by ISPs, the sponsorship decisions of CPs, the market structure therein, and surpluses of the ISPs, CPs, users. This is the first analysis of the effect sponsored data in the presence of ISP competition. We show that inter-ISP competition does not inhibit ISPs from extracting a significant fraction of CP surplus, leaving CPs no better off (and sometimes worse off) as compared to the scenario where data sponsoring is disallowed. Moreover, ISPs often have an incentive to significantly skew the CP marketplace in favor of the most profitable CP.

We consider optimal distributed computation of a given function of distributed data. The input (data) nodes and the sink node that receives the function form a connected network that is described by an undirected weighted network graph. The algorithm to compute the given function is described by a weighted directed acyclic graph and is called the computation graph. An embedding defines the computation communication sequence that obtains the function at the sink. Two kinds of optimal embeddings are sought, the embedding that: 1) minimizes delay in obtaining function at sink, and 2) minimizes cost of one instance of computation of function. This abstraction is motivated by three applications - in-network computation over sensor networks, operator placement in distributed databases, and module placement in distributed computing. We first show that obtaining minimum-delay and minimum-cost embeddings are both NP-complete problems and that cost minimization is actually MAX SNP-hard. Next, we consider specific forms of the computation graph for which polynomial-time solutions are possible. When the computation graph is a tree, a polynomial-time algorithm to obtain the minimum-delay embedding is described. Next, for the case when the function is described by a layered graph, we describe an algorithm that obtains the minimum-cost embedding in polynomial time. This algorithm can also be used to obtain an approximation for delay minimization. We then consider bounded treewidth computation graphs and give an algorithm to obtain the minimum-cost embedding in polynomial time.

In-network function computation (INFC) is becoming an essential aspect of large database systems where the data is distributed over the network. Such situations arise often in resource constrained wireless sensor network making them a natural candidate for INFC. We study the problem of maximizing the rate of INFC in wireless networks. In this paper, we develop a functional flow model for INFC when the function computation sequence is represented by a directed acyclic graph. We propose a linear program formulation to maximize the rate of INFC over all possible embeddings. We also formulate a mixed integer linear program (MILP) for maximizing the rate of computation for a single embedding on a capacity constrained wireless network. The MILP for finding the single embedding that yields maximum rate turns out to be NP hard; we develop a heuristic to solve this problem by formulating a linear program. We provide numerical results to illustrate the performance of these formulations.