Hierarchical scheduling for multiple resources is partially responsible for the performance achievements in large scale datacenters. However, the latest scheduling technique, Hierarchy Dominant Resource Fairness (H-DRF)[1], has some shortcomings in heterogeneous environments, such as starving certain jobs or unfair resource allocation. This is because a heterogeneous environment brings new challenges. In this paper, we propose a novel scheduling algorithm called Dominant Fairness Fairness (DFF). DFF tries to keep resource allocation fair, avoid job starvation, and improve system resource utilization. We implement DFF in the YARN system, a most commonly used scheduler for large scale clusters. The experimental results show that our proposed algorithm leads to higher resource utilization and better throughput than H-DRF.

A large-scale packet-switch architecture for a tera bit/s system--which uses a combined-packet-distribution (CPD) method for a crossbar packet switch--was developed. This method eliminates the restriction on scheduling processing time by extending a switching data unit. The data unit is called a combined packet that consists of plural variable-length packets or their fragments. The combined packets are sequentially distributed among multiple crossbar switch planes and their sequence integrity is preserved. Distributive targets among the switch planes are selectable. As a result, when one or more switch planes are damaged, redundancy of the switch fabric is easily attained in a so-called "graceful degradation" manner. Moreover, this switch uses a novel algorithm called hierarchical priority scheduling. This algorithm enables fairness of scheduling by taking account of queuing state. The repetition required for priority scheduling is reduced by a novel hierarchical approach. The simulated performance of this algorithm shows that it performs better than the simple maximal matching method under both uniform and non-uniform traffic.

In this paper, we study efficient scheduling algorithms that are suitable for ATM networks. In ATM networks, all packets have a fixed small length of 53 bytes and they are transmitted at very high rate. Thus time complexity of a scheduling algorithm is quite important. Most scheduling algorithms proposed so far have a complexity of O(log N) per packet, where N denotes the number of connections sharing the link. In contrast, weighted round robin (WRR) has the advantage of having O(1) complexity; however, it is known that its delay property gets worse as N increases. To solve this problem, in this paper we propose two new variants of WRR, uniform round robin (URR) and idling uniform round robin (I-URR). Both disciplines provide end-to-end delay and fairness bounds which are independent of N. Complexity of URR, however, slightly increases as N increases, while I-URR has complexity of O(1) per packet. I-URR also works as a traffic shaper, so that it can significantly alleviate congestion on the network. We also introduce a hierarchical WRR discipline (H-WRR) which consists of different WRR servers using I-URR as the root server. H-WRR efficiently accommodates both guaranteed and best-effort connections, while maintaining O(1) complexity per packet. If several connections are reserving the same bandwidth, H-WRR provides them with delay bounds that are close to those of weighted fair queueing.

Medium access control (MAC) protocol is one of the key components for providing quality of service (QoS) in wireless ATM (W-ATM) networks. In this paper, we propose a hierarchical scheduling scheme coupled with fair queueing algorithms with adaptive weights. This scheme is intended to be applicable to a TDMA/TDD based MAC protocol. Specifically, the performance of the fair-queueing algorithm using fixed weights and adaptive weights is evaluated and compared. Simulation results show that the proposed hierarchical fair-queueing scheduling with adaptive weights (HAW) can yield a lower cell transfer delay and a higher channel utilization while maintaining fairness among multiple users.

This paper proposes a hierarchical Digital Signal Processor (DSP) Code Generator VIRGO for large scale general signal processing algorithms. Hierarchical structured Vectorized Signal Flow Graph (V-SFG) description is used as input specifications. Ths DSP independent optimization procedure for both the program size and the execution time is performed each module by each hierarchically with regard to operation order, memory assignment and register allocation. The efficient code generation is demonstrated by comparing both instruction steps and dynamic steps of a practical ADPCM encoder/decoder with a conventional method.