Columbia University

Distributed Throughput Optimization

  • 6g4UxNNNwjWYVAAU_b3UbSewEW2n03X2an9biG4VubY

We consider scheduling and routing in wireless networks with stochastic packet arrivals. Recently, several distributed scheduling algorithms whose objective is to maximize the network throughput have been proposed. In networks with primary interference constraints, such algorithms (referred to as Greedy Maximal Scheduling – GMS) guarantee 50% of the maximum possible throughput. We presented the first distributed scheduling framework that guarantees maximum throughput. It is based on a combination of distributed matching algorithms and algorithms that compare and merge successive matching solutions. We showed that the complexities for achieving 100% throughput are comparable to those of the algorithms that achieve 50% throughput.

It was recently shown that if a set of conditions, known as Local Pooling, holds, GMS algorithms achieve 100% throughput. Hence, as an alternative to increasing the throughput by designing new algorithms, we proposed to use channel allocation to partition the network into subnetworks in which GMS algorithms can achieve 100% throughput. We characterized topologies in which 100% throughput can be achieved distributedly, and used these topologies to develop a number of channel assignment algorithms. We also presented new conditions under which distributed routing and scheduling algorithms achieve 100% throughout.

We later used graph theoretical tools to provide the first characterization of all the network graphs in which Local Pooling holds under primary interference constraints. Moreover, since under general interference constraints the throughput fraction achieved by GMS can be very low, we provided performance guarantees for GMS in various interference graphs. Overall, our results demonstrate the dependencies between the network topology, decentralization level, interference degree, and throughput.

Publications

[1]
B. Birand, M. Chudnovsky, B. Ries, P. Seymour, G. Zussman, and Y. Zwols, “Analyzing the performance of greedy maximal scheduling via local pooling and graph theory,” IEEE/ACM Transactions on Networking, vol. 20, no. 1, pp. 163–176, Feb. 2012.

[download]

[1]
B. Birand, M. Chudnovsky, B. Ries, P. Seymour, G. Zussman, and Y. Zwols, “Analyzing the performance of greedy maximal scheduling via local pooling and graph theory,” in Proc. IEEE INFOCOM’10, 2010.

[download] [Google Scholar]

[1]
A. Brzezinski, G. Zussman, and E. Modiano, “Distributed throughput maximization in wireless mesh networks via pre-partitioning,” IEEE/ACM Transactions on Networking, vol. 16, no. 6, pp. 1406–1419, Dec. 2008.

[download]

[1]
A. Brzezinski, G. Zussman, and E. Modiano, “Local pooling conditions for joint routing and scheduling,” in Proc. ITA’08, 2008.

[download]

[1]
G. Zussman, A. Brzezinski, and E. Modiano, “Multihop local pooling for distributed throughput maximization in wireless networks,” in Proc. IEEE INFOCOM’08, 2008.

[download] [Google Scholar]

[1]
E. Modiano, D. Shah, and G. Zussman, “Maximizing throughput in wireless networks via gossiping,” in Proc. ACM SIGMETRICS / IFIP Performance’06, 2006.

[download] [Google Scholar] Best Paper Award

[1]
A. Brzezinski, G. Zussman, and E. Modiano, “Enabling distributed throughput maximization in wireless mesh networks: A partitioning approach,” in Proc. ACM MOBICOM’06, 2006.

[download] [Google Scholar]