基于二部圖最大匹配的動態負載均衡算法①

周 磊 孟利民 周立鵬 蔣 維

(*浙江工業大學信息工程學院 杭州 310023) (**浙江樹人大學信息科技學院 杭州 310015)

0 引 言

隨著網絡技術的高速發展，互聯網服務已經成為日常生活中不可或缺的部分。由于互聯網用戶的爆發式增長，服務器常常在短時間內收到大量并發的用戶請求，若不能及時處理這些請求將影響用戶體驗，降低服務質量。因此，單個服務器遠遠無法滿足大量的服務請求，聯合多個服務器的服務器集群應運而生。如何合理地分配集群服務器的任務并滿足最大的服務需求是服務器集群需要解決的關鍵技術問題，而負載均衡是解決服務器集群難點的核心技術之一，能夠平衡集群中各個服務節點的負載，充分發揮服務器集群的性能。目前國內外已經提出了各種負載均衡算法[1]。其中有靜態負載均衡算法，如輪詢調度算法、加權輪詢調度算法[2]、目標地址散列調度算法等，這類算法易于實現，但不考慮各個服務器節點的負載狀態，容易導致負載不均衡；有動態負載均衡算法[3,4]，如最小連接數算法、一致性哈希算法[5]、動態反饋算法[6]等，這類算法沒有考慮服務器間的性能差異和任務請求的大小，不能準確地判斷服務器真實的負載狀態。動態負載均衡算法注重于服務器負載狀態的計算和反饋，文獻[7]提出一種基于排隊論綜合指標評估的動態負載均衡算法，采用服務器M/M/1排隊模型，以任務的平均排隊時長和平均等待時長來計算負載，但其計算需花費較多時間，具有一定的延后性。……