Saad Mneimneh

Scheduling and Load Balancing

We work on several problems of high performance networks, including switching, routing, and load balancing. One typical aspect of the research is to establish theoretical bounds on performance. For instance, we have a fundamental result regarding the speedup (the speed of the chip relative to line speed) of an input-queued switch, an architecture consisting of buffers at the input ports. For this architecture, a naturally predominant class of algorithms schedule packets by first prioritizing them while they sit in the buffers. These algorithm always fell short, until finally our work highlighted their intrinsic limitation: By modeling the schedule as successive computations of weighted matchings in a bi-partite graph, it was possible to prove that these algorithms require a speedup of at least 1.5, regardless of the priority scheme. This result was obtained by showing that a large bi-partite graph (e.g. representing a large switch) must contain a weighted cycle with a special property that limits the weight of the matching and, thus, the throughput of the schedule.

One approach to overcome the speedup is to balance packets across multiple switches each running at a lower speed. Here, simple load balancing algorithms can achieve throughput probabilistically,by providing a bound on the expected length of buffers, at the cost of reordering packets. Our current work explores the limitation of such an approach highlighting the relationship among three properties of load balancing: Throughput, Liveliness (will some flow starve?), and Ordering. Only two of these can be achieved simultaneously (work in progress).

Packet reordering problem is strongly undesired in practice. It can be avoided by routing packets of the same flow through exactly one switch. However, using combinatorial techniques, we proved that this family of (online) flow based algorithms will only achieve a throughput of at most 1/3 the maximum throughput. Moreover, we proved that this bound is tight by designing an optimal online with a competitive ratio of 1/3.

Such theoretical bounds on performance are very important. For instance, a flow based routing algorithm that achieves a 1/3 throughput is indeed optimal (since this represents the theoretical bound). On the other hand, knowing that every priority based algorithm must operate at a speedup of at least 1.5, entices us to look for alternative architecture. We contributed a method to run copies of the same existing priority based algorithm on multiple switches while avoiding any speedup per switch. In addition, we show that it is possible to design algorithms for multiple switches that guarantee a bounded amount of packet reordering, while keeping full throughput, and requiring neither speedup nor the use of traditional input (or even output) buffers.

We also work on other resource allocation problems such as balancing colored balls in bins, the carpool problem, and game theoretic approaches for channel allocation in radio networks. Finally, we are investigating a new direction to study social networks, and other similar structures such as wikiedia pages and open source code, using simplicial complexes, a generalization of graphs where relations are not necessarily pairwise (but still form a subclass of hypergraphs).

Copyright © 2017 Saad Mneimneh