在網站閘道器上提供整體回應時間比例差別服務之多重資源要求排程演算法

Abstract

對於一個商業網站來說，如何最佳化網站伺服器的吞吐量與提供重要的客戶較短延遲時間的服務是兩個需要考量的主要問題。本篇論文提出了一個置於網站之前，透過多重資源要求排程演算法來提供不同等級的客戶間整體回應時間比例差別服務的閘道器系統。即使這個閘道器系統完全獨立於網站之外，此閘道器系統依然可以完全的消耗伺服器上的資源以提升網站吞吐量，並且還可以提供比例的整體回應時間差別服務給不同等級的使用者。這個閘道器系統主要由許可控制機制與要求排程機制兩大部分所組成，其中的許可控制機制透過控制轉送要求的速度，除了可以避免網站伺服器過載，還可以盡量的有效運用網站伺服器上的資源；而要求排程機制則依據三種修改過的比例延遲演算法, WTP, MDP和PAD來進行要求排程，以提供不同等級間的整體回應時間比例差別服務。為了驗證效果，我們透過修改一個開放原始碼的代理伺服器軟體Squid來實做這個閘道器系統，測試結果中顯示此閘道器系統可以提升最大的吞吐量達78%，並同時減少25%的整體回應時間。除此之外，我們也發現以WTP和MDP為基礎的排程演算法可以提供良好的整體回應時間比例差別服務效果。

Optimizing the serving throughput and providing important customers short user-perceived latency are two of major concerns for commercial websites. This thesis proposes a gateway system in front of the website to provide Proportional System-time Differentiation with multiple-resources consideration (MR-PSTD) between customers. Despite being external to the website, our gateway not only exhausts the resources of all types in the website to raise its throughput, but also provides proportionally differential system time differentiation to users of different classes. The gateway mainly consists of an admission controller (AC) and a request scheduler (RS). To prevent the server from being overloaded while exhausting all resources, AC controls the forwarding rate of requests to the server. To provide proportionally differentiated system time between classes, RS schedules the requests according to three reformed latency-based scheduling algorithms including Waiting Time Priority (WTP), Mean Delay Proportional (MDP) and Proportional Average Delay (PAD). We implement our gateway by modifying Squid, an open-source proxy. Our evaluation results show that our MR-PSTD gateway raises 78% of peak throughput and reduces 25% of user-perceived latency. Besides, WTP-based and MDP-based scheduling algorithms can provide exact PSTD between classes.