Analyzing the Performance of Greedy Maximal Scheduling via Local Pooling and Graph Theory
The effective operation of wireless and wireline networks relies on the proper solution of the packet scheduling problem. Efficient operation of wireless networks and switches requires using simple (and in some cases distributed) scheduling algorithms. In general, simple greedy algorithms (known as Greedy Maximal Scheduling - GMS) are guaranteed to achieve only a fraction of the maximum possible throughput (e.g. 50% throughput in switches). However, it was recently shown that in networks in which the local pooling conditions are satisfied, GMS achieves 100% throughput.