Game-theoretic approach on latency-bandwidth trade-off

This is a tech. article, so you can skip this if you are not interested in computer systems or systems virtualization.

Recently, I had an interesting observation on Xen-scheduler. Xen uses the credit scheduler, by default. You can refer the credit scheduler at other papers, articles, etc. (So, I will skip to explain this) Xen’s credit scheduler has been designed to preserve fairness among CPU-bound guest domains. This results in bad latency for time-sensitive applications (or domains). For mobile virtual machines that require real-time facilities, it is a critical problem. To support real-time, I/O latency has to be time-bounded, which is difficult with the current credit scheduler and split driver.



There are some reasons why split and credit is a bad combination for I/O latency.
At first, Xen’s split driver separates device drivers from a user domain, so an additional inter-VM scheduling is required. (switching back and forth to driver domain and user domain) Unfortunately, the delay due to inter-VM scheduling cannot be bounded (to a reasonably small value). Secondly, credit’s BOOST doesn’t guarantee the bounded deterministic latency although it has indeed, BOOST priority. Multiple domains can be boosted simultaneously, so BOOST can be easily negated by another boost. In addition, VCPU doesn’t be boosted often though it has a pending I/O event. So, I/O latency in Xen is limited with credit and split driver model.

To support real-time, 1) the driver domain should handle physical interrupts quickly , and 2) a real-time guest OS should be able to process requested I/O event in a timely manner. To incorporate a real-time guest OS, we can assign a static priority to each domains so that the inter-VM scheduling at hypervisor cannot be delayed by the inter-VM scheduling at the hypervisor.

However, this causes an additional issue on fairness. Since the I/O handling domain is prioritized, it can over-utilize the CPU time compared with the others, which means the fairness is broken. The result reflects that the prioritized real-time domain is easy to be boosted, and the other party takes penalty by the boost. Our further observation reveals that fairness is broken when the real-time domain has both I/O and CPU load, and fairness becomes worse as CPU load increases. The reason seems to be that the vcpu is boosted, and its user tasks consumes more CPU time by the BOOST.

The problem leads us to an idea that there seems to be a trade-off relationship between I/O latency and fairness for CPU utilization. Let us think this problem in a slight different angle. The real-time domain needs to be boosted so that it can handle I/O; otherwise latency is unsatisfactory. Another CPU bound-user guest needs to have more CPU time so that it can utilize CPU as much as the other party; otherwise fairness is unsatisfactory. If we prioritize the real-time guest OS, then fairness is easy to be broken. If we fairly distribute the CPU utilization, CPU latency is difficult to be bounded.

To support both latency and fairness, we can apply game theory in order to find a equilibrium point that make the real-time domain have satisfactory I/O latency and the non-real-time domain have fair CPU utilization with the others.

To be cont.