Institute of Electrical & Electronic Engineers
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.