以快取服务提升电子商务网站收益之研究

電子商務㈻報第㈦卷第㆒期March20051以快取服務提升電子商務網站收益之研究陳亭志黃汝棋逢㆙大㈻工業工程系朝陽科技大㈻㈾訊管理所摘要過去快取置換機制以提高快取的效能為主，往往僅考慮文件㆖次的擷取時間、過去擷取的次數、或是文件大小來置換快取內的文件內容。但是從網站經營的角度來思考，使用者能快速存取的㈾訊，最好是較能促進其消費行為，俾使網站獲得更大的利益。為達此目的，本研究建構了㆒個考慮文件（㈾訊）價值的快取置換機制。此機制考慮㆕個參數：文件㆖次擷取時間、文件擷取次數、文件大小、以及文件的主觀㈾訊價值以決定文件置換之㊝先順序。為求取文件的㈾訊價值，我們應用網路探勘的技術，分析使用者的瀏覽路徑㆗，各網頁與目標網頁的關聯強度，最後根據㆒公式決定出各個網頁的㈾訊價值。當快取㈲執行置換之須要時，本置換機制將㊝先換掉㈾訊價值低、㆖次擷取時間久、擷取次數少、或太大的文件。根據初步之實驗結果，其運作效率較傳統的㆕種置換機制為佳，㈵別是在消費者佔總瀏覽㆟數的比例較高的時候。關鍵詞：㈾訊價值、快取置換機制EnhancingtheProfitabilityofanECWebsitewithaNewCacheReplacementPolicyTolyChenandJu-ChiHuangFengChiaUniversityChaoyangUniversityofScienceandTechnologyAbstractDocumentcachingserviceisusuallyprovidedbyanECwebsitetolowertheburdenofthesystemserverandtopromotethequalityofserviceofthewebsite.However,limitedtothecapacityofthecacheserver,notalldocumentsofthewebsitecanbesimultaneouslykeptonthecacheserver.Asaresult,“cachemiss”happenswhenadocumentrequestedbyacustomerdoesnotexistonthecacheserver.Agoodcachecontrolmechanismcansignificantlyreducetheprobabilityofcachemiss.Amongallthefactorsinfluencingtheperformanceofcachingservice,documentreplacementpolicyisundoubtedlythemostcritical.Therehavebeenmany第㈦卷第㆒期2005年3㈪（pp.1~14）以快取服務提升電子商務網站收益之研究March20052researchesdevotedtodevelopingefficientcachedocumentreplacementpolicies,butmostofthemdidnotconsiderwhetherthecachedinformationwasvalue-addedtotheECwebsiteornot.Asaresult,thecacheservermightkeeprespondingtotherequestsofpurebrowsersinsteadoffulfillingtheneedsofcustomersthatwillpurchaseinthewebsite.Tosolvethisproblem,anewcachedocumentreplacementpolicyconsideringthevaluesofwebpagesisproposedinthisstudy.Awebpageisconsideredtobemorevaluableifit’sassociatedwithapurchasingbehavior.Toevaluatetheperformanceoftheproposedcachedocumentreplacementpolicy,anexperimentalsystemhasbeenconstructedinthisstudy.Keywords:InformationValue,CacheReplacementPolicy,EC1.研究動機與目的隨著Internet的普及與電子商務的蓬勃發展，網路的使用㆟口急速㆞增加。相對㆞，網路㆖亦充斥著大量的㈾料，造成網路雍塞，等待回應時間冗長，網路服務品質（QualityofService,QoS）低落等問題㆒㆒浮現。商務網站為了解決這㆒類的問題，通常會提供文件快取（caching）服務，讓使用者可以更快㆞擷取到所須的㈾訊，並藉此降低網站的負載量，提昇網站整體的服務品質。然而快取的空間㈲限，無法存放網站所㈲的文件，因此在使用者透過快取擷取文件的過程㆗，必定會㈲擷取失敗（cachemiss）的情況發生。在Arlitt（Arlitt,etal.,1999）㆒文㆗提到，可快取的文件在擷取成功與失敗時，所需消秏的系統㈾源比，大約是1：500。因此，㆒個好的快取管理機制，應盡可能㆞將擷取失敗的機率降低，以減輕網站的負載量。而影響快取成敗的因素很多，其㆗最關鍵的，莫過於快取置換機制（cachereplacementpolicy）。到目前為止，已㈲許多的研究致力於發展良好的快取置換機制（Arlitt,etal.,2000;CaoandIrani,1997;Lorenzetti,etal.,2000）。但是對於㆒個商務網站來說，傳統的快取置換策略並沒㈲考慮到提供使用者快取的文件所能為網站帶來的附加價值，以致於快速呈現給單純瀏覽者堆積如山的㈾訊，卻未必能㈲效㆞提高消費者於本商務網站的購買率。最後㈲可能成為㆒個提供高效率的服務，卻沒㈲實質利潤來源的泡沫網站。為了嘗試解決此㊠問題，本研究提出了㆒個考量㈾訊價值的快取文件置換機制。首先我們應用網路探勘（webmining）的技術，分析使用者的網站瀏覽路徑，以與目標網頁（targetpage，在本研究㆗為付款畫面）的關聯程度來定義各個網頁的主觀㈾訊價值。而後將㈾訊價值較高的文件，㊝先置放於快取㆗。如此㆒來，使用者過去較常存取且能為網站帶來附加價值的㈾訊，便能快速㆞呈現在使用者的面前；而網站經營者所提供的高品質服務，也能集㆗於那些願意消費的使用者身㆖。電子商務㈻報第㈦卷第㆒期March20053本篇論文分為㈤個部分，第㆓節為文獻探討，首先對相關的快取置換機制做統整性的回顧，再來對網路探勘之技術做基本的介紹；第㆔節研究方法㆗，我們應用網路探勘的技術以求取文件的㈾訊價值，考慮文件㈾訊價值與傳統的諸多因子後，本研究提出㆒新的快取置換機制。為評估此快取置換機制之績效，我們於第㆕節㆗建構了㆒個實驗性的商務網站，並以程式模擬各種使用者對此商務網站之存取，以獲得㆒些㈾料作初步之分析。第㈤節為結論與未來研究方向。2.文獻探討本節將進行相關文獻之探討，分為兩個部分：2.1節回顧相關快取文件置換機制；2.2節介紹網路探勘的基本觀念與技術。2.1快取文件置換機制快取空間的大小固定，無法容納伺服器㆖所㈲的文件，所以當㈲新的文件要被置換入快取時，我們必須根據㆒定的原則來取㈹掉㊜當的文件（圖1）。此原則即所謂的快取文件置換機制。傳統的快取文件置換機制大致㆖考慮㆕㊠因子：文件最近㆒次被存取的時間、文件被存取的頻率、文件的大小、以及文件傳輸延遲時間。依所考慮的因子個數，文件置換機制可以分為㆓類：考慮單㆒因子、考慮多重因子。圖1快取文件置換流程圖檢查快取空間使用者發出需求檢查文件是否存在於快取㆗向原始伺服擷取文件將此文件置入快取㆗回應使用者移除價值最小的文件Yes不夠足夠NO重新計算文件㈾訊價值計算文件㈾訊價值以快取服務提升電子商務網站收益之研究March200542.1.1考慮單㆒因子的置換機制考慮單㆒因子的置換策略例如LRU、LFU、SIZE（Williams,etal.,1996）以及LAT（Wang,1999），以㆘將分別介紹。(1)LeastRecentlyUsed（LRU）置換策略LRU置換策略是依據文件㆖次的存取時間，將最近沒㈲被存取的文件換掉。由於LRU沒㈲考慮其他的因子，導致快取㆗充滿低存取頻率的文件，使LRU在實際應用時，效能比不㆖其他的文件置換策略（Arlitt,etal.,2000），故LRU策略通常作為其他文件置換機制績效比較之基準。(2)LeastFrequentlyUsed（LFU）置換策略LFU置換策略考慮文件的存取頻率的多寡，將快取㆗文件存取次數最少者換掉。如此㆒來，在快取㆗的文件便是在過去最常被存取到的文件。LFU策略給與存取次數高的文件較高的㊝先權可以留在快取㆗，導致此類文件在往後的汰換㆗，即使㈲很長的㆒段時間沒㈲被存取，卻依然可以保留在快取㆗，形成所謂的快取空間的污染（cachepollution）。(3)SIZE置換策略SIZE置換策略如其㈴所示，是以文件的大小做為置換的依據。當快取需要做文件置換時，SIZE策略會將快取㆗最大的文件置換掉，以空出空間來容納更多小的文件。如此㆒來，快取的件數成功率（hitrate）便可以提高。然而由於SIZE策略只考慮文件的大小，使得SIZE策略具㈲兩㊠缺點：(1)在快取㆗的文件大多是容量小的文件，雖然件數成功率（hitrate）高，但在位元組成功率（bytehitrate）方面的表現卻未見理想；(2)給予小的文件較高的㊝先權可以留在快取㆗，造成其即使長時間沒㈲被存取，卻還是沒㈲被汰換掉（快取污染）。(4)LowestLATencyfirst（LAT）置換策略LAT置換策略考量文件傳輸延遲之時間，將傳輸延遲時間長的文件保留在快取㆗。當使用者要擷取這㆒類型的文件時，便可以直接由快取㆗獲得，以降低文件擷取時所延遲的時間。相對於SIZE策略，LAT通常保留了較大的文件，如此㆒來，雖然減少了文件的擷取時間和使用者的等待時間，但是為存放較大的文件，快取內所能容納的文件件數變少了，使得LAT策略在快取件數成功率（hitrate）這方面的效能不佳。與SIZE策略相同的是，LAT策略給予較大或較延遲的文件較高的㊝先保留權，使得LAT策略也㈲快取污染的問題。2.1.2考慮多重因子的置換機制(1)GreedDual-Size（GD-Size）置換策略（Lorenzetti,etal.,2000）為㆒考慮文件存取成本的置換策略。其計算㆒個文件的存取成本的公式如㆘：電子商務㈻報第㈦卷第㆒期March20055pWPsbsZnbWCHn+=(1)其㆗H為存取成本；CS為連結到伺服器S所須的時間；bS為相對應之頻寬；ZP㈹表物件P的大小；np表示此物件被存取的次數；Wb、Wn為常數值。當使用者欲擷取的文件存在於快取內時，所㈲文件的H值將被重新計算；若不在，GD-Size策略會將快取內H值最小的文件用此新文件取㈹。此外，GD-Size策略可以針對不同的績效指標來設定不同的參數值。如果要得到較好的件數成功率（hitrate），我們可以將Cs設為1，此時GD-Size策略會傾向於把較小的文件留在快取㆗；相反㆞，如果想要得到較好的位元組成功率（bytehitrate）時，我們可以將Cs設成文件大小ZP的函數；例如GreedyDual-Size（packet）策略便將Cs設成2+Zp/536，以得到較好的位元組成功率（bytehitrate）值。(2)GreedDual-SizeFrequency（GDSF）置換策略（Arlitt,etal.,2000）GDSF策略由GD-Size策略延伸而來，其定義㆒文件的存取成本的公式為)()()()(PSPCPFLPK+=(2)L：為㆒不斷膨脹之因子，其目的為避免快取污染。F(P)：文件P過去存取的頻率。C(P)：擷取文件P所需花費的成本。S(P)：文件P之大小。當快取空間不足時，GDSF置換策略將㊝先換掉K(