Fast and Optimal Scheduling over Multiple Network Interfaces

Most of today’s mobile devices have at least two wireless network interface cards (NICs). Future devices are expected to have as many as twelve wireless NICs, with different data transmission capacities and a wide range of energy and dollar costs. When multi-NIC devices are running multiple applications, each unit of application data ought to be scheduled on to the network interface that maximizes user satisfaction. The scheduling algorithm must take into account not only user and application preferences, such as user cost-tolerance and application delay-tolerance, but also future availability of NICs due to device mobility. Furthermore, to run on small, resource-limited devices, it must be highly efficient. We addressed the problem of efficiently computing an optimal transmission schedule if future connectivity is known. We showed that simple greedy algorithms are incorrect and that classical optimization techniques are too inefficient for CPU- and memory-constrained mobile devices. We developed a hill-climbing algorithm that finds optimal schedules 10-100 times faster than classical techniques by exploiting problem structure, and is therefore efficient enough to employ on a mobile device. Our algorithm also supports efficient incremental rescheduling. Finally, we also implemented our algorithm on a real system that runs on Java-enabled laptops, PDAs and cell phones.