傳統的封包排程法一般僅考慮通訊資源作為排序以及公平分配的基準，然而因網路服務日漸多元，所消耗的資源已經不僅於通訊資源，還包含了計算資源，如何在多種資源間達到公平分配以及排程成為重大議題。目前在多資源下的排程已有許多研究成果，然而，前述的研究中大多是先評估各資源的狀況並決定封包順序，但是在處理過程中資源的多寡可能會發生變化(如無線鏈路受干擾)，造成排程失準進而使得排程法無法達成其效用。
PRS (per-resource scheduling)的方法雖已被提出，但其會有欺騙行為發生，亦即其不符合抗操控性(strategy-proofness, SP)公平性原則，此原則為資料流無法透過改變資源的需求量來獲得更高比例的資源。雖然在先前的研究中有指出PRS方法並不具SP，但並無其在何種情況下違反SP及其所帶來的影響，然而PRS可透過拉近排程決定時資源預估值與實際使用時資源實際值來降低失準率，故有其優點。本論文提出了每個資源排程法(Per-Resource Fair Queuing, PRFQ)，並探討在各種情況下若資料流進行欺騙之影響。由實驗結果可得知，PRFQ相較於之前的以主導資源公平性之排程法DRFQ(Dominant Resource Fairness Queue)，吞吐量可提升20.1%，而在資料流隨機欺騙的平均效益僅0.7%，且當系統中的資料流數量越多時，因需保障每個資料流所得資源，導致可自由分配資源減少，故違反SP的情況會變得越小；而在排程準確率上，若資源處理能力若以較快的頻率變動時，PRFQ仍可維持94.97%的高準確率，DRFQ僅能維持52.87%；在公平性維持率PRFQ達99.62%，而DRFQ則因準確率低導致公平性維持率僅85.98%。

In general, traditional packet scheduling only considers communication resource as a basis for ordering and fair sharing. However, due to the increasing diversity of network services, the resources consumed are not only communication resources, but also computing resources. How to achieve fair sharing and scheduling for multiple resources has become an important issue. Many researches were proposed to solve multi-resource allocation and scheduling. Most of the studies evaluated the utilization of each resource and determine the order of the packets. However, the capacity of the resources may change during the processing (e.g. wireless interference), therefore causing inaccurate scheduling.
Per-resource scheduling (PRS) method has been proposed, but it has the side effect of cheating. That is, it does not achieve the strategy-proofness(SP) fairness, i.e., the flows can get better service by artificially changing the demand of resources. Although previous studies pointed out that PRS does not have SP, there is no any investigation about the impact of violating SP in various situations. However, PRS can reduce the inaccuracy by narrowing the gap between the resource estimated value and real values, so it has some specific advantages. Therefore, this paper proposes a Per-Resource Fair Queuing (PRFQ) scheduler, and discusses the impact of flow cheating in various situations. The simulation results show that the throughput of PRFQ is 20.1% higher than that of a typical multi-resource scheduler, Dominant Resource Fairness Queue (DRFQ). The average profit by cheating randomly is only 0.7%, furthermore, when the number of flows is larger, as the resource share for each flow is guaranteed, the amount of allocatable resources is lesser. Therefore, the effect of violating the SP becomes smaller. For the scheduling accuracy, if the resource processing capability changes at a higher frequency, PRFQ can maintain a high accuracy rate of 94.97%, while DRFQ achieves only 52.87%. About the fairness, PRFQ achieves 99.62% while DRFQ achieves 85.98% when the resource processing capability changes at a higher frequency.

[1] T. Y. Tsai, Y. L. Chung, and Z. Tsai, “Introduction to Packet Scheduling Algorithms for Communication Networks,” in Communications and Networking, J. Peng, Ed. Rijeka: InTech, Sept. 2010.
[2] M. Katevenis, S. Sidiropoulos, and C. Courcoubetis, “Weighted Round-robin Cell Multiplexing in a General-purpose ATM Switch Chip,” IEEE Journal on Selected Areas in Communications, vol. 9, no. 8, pp. 1265-1279, Oct. 1991.
[3] M. Shreedhar and G. Varghese, “Efficient Fair Queuing Using Deficit Round-robin,” IEEE/ACM Transactions on Networking, vol. 4, no. 3, pp. 375-385, June 1996.
[4] S. S. Kanhere, H. Sethu, and A. B. Parekh, “Fair and Efficient Packet Scheduling using Elastic Round Robin,” IEEE Transactions on Parallel and Distributed Systems, vol. 13, no. 3, pp. 324-336, Mar. 2002.
[5] A. K. Parekh and R. G. Gallager, “A Generalized Processor Sharing Approach to Flow Control in Integrated Services Networks: the Single-node Case,” IEEE/ACM Transactions on Networking, vol. 1, no. 3, pp. 344-357, June 1993.
[6] J. C. R. Bennett and Hui Zhang, “WF2Q: Worst-case Fair Weighted Fair Queueing,” Proc. INFOCOM '96. vol. 1, pp. 120-128, 1996.
[7] J. C. R. Bennett and Hui Zhang, “Hierarchical Packet Fair Queueing Algorithms,” IEEE/ACM Transactions on Networking, vol. 5, no. 5, pp. 675-689, Oct. 1997.
[8] S. J. Golestani, “A Self-clocked Fair Queueing Scheme for Broadband Applications,” Proc. INFOCOM '94, vol. 2, pp. 636-646, 1994.
[9] P. Goyal, H. M. Vin and Haichen Cheng, “Start-time Fair Queueing: a Scheduling Algorithm for Integrated Services Packet Switching Networks,” IEEE/ACM Transactions on Networking, vol. 5, no. 5, pp. 690-704, Oct. 1997.
[10] L. Zhang, “Virtual Clock: A New Traffic Control Algorithm for Packet Switching Networks,” SIGCOMM Computer Communication Review, pp. 19–29, Aug. 1990.
[11] M. Honda, Y. Nishida, C. Raiciu, A. Greenhalgh, M. Handley, and H. Tokuda, “Is it still possible to extend TCP? ,” Proc. IMC, 2011.
[12] Z. Wang, Z. Qian, Q. Xu, Z. M. Mao, and M. Zhang, “An Untold Story of Middleboxes in Cellular Networks,” Proc. SIGCOMM, 2011.
[13] A. Ghodsi, M. Zaharia, B. Hindman, A. Konwinski, S. Shenker, and I. Stoica, “Dominant Resource Fairness: Fair Allocation of Multiple Resource Types,” Proc. USENIX Conf. Networked Systems Design and Implementation (NSDI), 2011.
[14] Y. Zeldes and D. G. Feitelson, “On-line Fair Allocations Based on Bottlenecks and Global Priorities,” Proc. 4th ACM/SPEC International Conference on Performance Engineering, pp. 229-240, 2013.
[15] S. M. Zahedi and B. C. Lee, “REF: Resource Elasticity Fairness with Sharing Incentives for Multiprocessors,” Proc. Intl. Conf. on Architectural Support for Programming Languages and Operating Systems (ASPLOS), 2014.
[16] A. A. Bhattacharya, D. Culler, E. Friedman, A. Ghodsi, S. Shenker, and I. Stoica, “Hierarchical Scheduling for Diverse Datacenter Workloads,” Proc. 4th Annu. Symp. Cloud Compute, 2013.
[17] A. Gutman and N. Nisan. “Fair Allocation without Trade,” Proc. 11th International Conference on Autonomous Agents and Multiagent Systems, vol. 2, 2012.
[18] D. Parkes, A. Procaccia, and N. Shah, “Beyond Dominant Resource Fairness: Extensions, Limitations, and Indivisibilities,” Proc. ACM EC, 2012.
[19] T. Bonald, and J. Roberts. “Enhanced Cluster Computing Performance Through Proportional Fairness,” Performance Evaluation, vol. 79, pp. 134-145, 2014.
[20] W. Wang, B. Li, B. Liang, and J. Li, “Multi-resource Fair Sharing for Datacenter Jobs with Placement Constraints,” Proc. High Performance Computing, Networking, Storage and Analysis, 2016.
[21] T. Bonald, and J. Roberts, “Multi-resource Fairness: Objectives, Algorithms and Performance,” ACM SIGMETRICS Performance Evaluation Review, vol. 43, no. 1, 2015.
[22] D. Klusáček H. Rudová, and M. Jaroš, “Multi Resource Fairness: Problems and Challenges,” Proc. Workshop on Job Scheduling Strategies for Parallel Processing, 2013.
[23] D. Klusáček and H. Rudová, “Multi-resource Aware Fairsharing for Heterogeneous Systems,” Proc. Workshop on Job Scheduling Strategies for Parallel Processing, 2014.
[24] H. Liu and B. He, “Reciprocal Resource Fairness: Towards Cooperative Multiple-resource Fair Sharing in Iaas Clouds,” Proc. International Conference for High Performance Computing, Networking, Storage and Analysis, 2014.
[25] A. Ghodsi, V. Sekar, M. Zaharia, and I. Stoica, “Multi-resource Fair Queueing for Packet Processing,” ACM SIGCOMM Computer Communication Review, pp. 1-12, 2012.
[26] W. Wang, B. Li, and B. Liang, “Multi-Resource Round Robin: A Low Complexity Packet Scheduler with Dominant Resource Fairness,” Proc. 21st IEEE International Conference on Network Protocols (ICNP), pp. 1-10, 2013.
[27] W. Wang, B. Li, and B. Liang, “Low Complexity Multi-resource Fair Queueing with Bounded Delay,” Proc. INFOCOM, 2014.
[28] J. Zhang, H. Qi, D. Guo, K. Li, W. Li and Y. Jin, "ATFQ: A Fair and Efficient Packet Scheduling Method in Multi-Resource Environments," in IEEE Transactions on Network and Service Management, vol. 12, no. 4, pp. 605-617, 2015.
[29] J. Zhang, K. Li, D. Guo, H. Qi, W. Li and Y. Jin, "MDFS: Deadline-Driven Flow Scheduling Scheme in Multi-Resource Environments," in IEEE Transactions on Multi-Scale Computing Systems, vol. 1, no. 4, pp. 207-219, 1 2015.
[30] X. Li and Q. Chen, “Low-complexity Multi-resource Packet Scheduling for Network Function Virtualization,” Proc. INFOCOM, 2015.
[31] J. Zhang, K. Li, D. Guo, H. Qi, Xiaoyi Tao and Y. Jin, "Data Rate Guarantee for Coflow scheduling in network function virtualization," 2016 IEEE/ACM 24th International Symposium on Quality of Service (IWQoS), Beijing, pp. 1-6, 2016.
[32] C. A. Waldspurger and W. E. Weihl. Lottery scheduling: flexible proportional-share resource management. in OSDI ’94, 1994.