Bisecting IR:一個行動計算環境中高效率的暫存資料驗證法




翁國彬、呂永和、李之中

國立臺灣科技大學資管系
台北市基隆路四段四十三號
TEL:(02) 27376770
EMAIL:{yhl,leecc}@cs.ntust.edu.tw






摘要

在行動計算環境中,有一具代表性的暫存資料驗證法稱為時間戳記法。在 這個方法中,伺服端於固定時間廣播驗證報告給行動客戶端,行動客戶端再利用此驗證報告,驗證其暫存資料的正確性。時間戳記法為了防止行動客戶端將原本有效的資料誤判為無效,在 驗證報告中為每一個失效資料,記錄該資料被異動時的時間戳記。然而,時間戳記本身卻造成網路的資料流量的大量增加。本篇論文中我們提出一個簡化驗證報告的方法,稱為Bisecting IR法,以有效地降低網路資料流量。Bisecting IR法的基本精神是將行動客戶端所收到的驗證報告區分為兩部份:已經做過驗證的部份,以及未曾做過驗證的部份;客戶端只處理未曾做 過驗證的部份。經由模擬發現,我們所提的方法明顯地降低了網路的資料流量。

一、研究動機

1.1 行動計算環境基本架構

隨著電腦科技與無線網路(Wireless Network)技術的進步,人們可以利用手提式電腦在任何地方、任何時間,透過無線通訊技術擷取存在公司中伺服器(Server)內的相關資料,處理公司的日常業務。這種結合電腦與無線通訊技術而成的系統,稱之為行動計算環境(Mobile Computing Environment)

行動計算環境如圖1所示,其主要是由固定式主機(Fixed Host)與行動主機(Mobile Unit)所組成[1],各個固定式主機間是以有線網路來完成資料通訊或資料傳輸。而固定式主機如果擁有無線通訊傳輸功能者,我們又稱它為行動支援工作站(Mobile Support Station)。行動主機與固定主機間的資料傳遞,則是先透過無線網路連接到行動支援工作站,再由行動支援工作站透過固定網路傳送到固定主機上。

Image18.gif (5809 bytes)

圖1、行動計算環境

每一個行動主機在同一時間,只能隸屬於一個區域(Cell),以方便行動支援工作站管理行動主機與記錄行動主機所在位址。行動主機可以一面接收資訊,一面從一個區域移動到另一個區域,這個動做叫做區域轉移(Handoff)。為了使行動主機在各個區域都能夠繼續接收資料且能維持資料之一致性,我們假設每一個行動主機所需的資料完全複製(Fully Replicated) 在每一個行動支援工作站上[2]。為方便起見,在後面文章中,我們稱行動主機為客戶端,而行動支援工作站則稱為伺服端。

 在無線通訊計算環境下,行動客戶端和伺服端之間的通訊頻寬相當有限,為了有效利用網路頻寬, 於是行動客戶端上會保存一些從伺服端下載的資料以供後續的應用使用。但這些客戶端的暫存資料,會因為其對應的伺服端資料遭到修改而失效;這些失效的資料必須由客戶端移除,以保證客戶端資料的正確性。維持客戶端暫存資料正確性的方法中較具代表性的是時間戳記法(Broadcasting Timestamps Strategy)[2],簡稱TS法。

1.2   時間戳記法

在時間戳記法中,伺服端每隔一段時間(在此假設為L秒),就會送一個失效驗證報告(Invalidation Report,簡稱IR)給客戶端,供客戶端去刪除已失效的暫存資料。而IR會包含異動資料的資料代號與其異動時間的時間戳記(Timestamp)。為了允許客戶端離線後再連線時仍可有效驗證其暫存資料;每一個IR會往前包含過去數個(在此假設為w個)時段內的所有異動資料的記錄。

如圖2所示,假設Tlb為一客戶端上次收到IR的時間;Ti為此客戶端再連線後收到第一個IR的時間(注意:在此例中客戶端遺失了一個IR)。當客戶端再連線後,如果Ti-Tlb大於w*L,則代表客戶端遺失過多的IR,以致於可能遺失一些伺服端的資料異動資訊;此時客戶端必須將其所擁有的暫存資料全部移除。反之,若Ti-Tlb小於或等於w*L,則客戶端便可利用IR做暫存資料驗証,刪除過時的資料,保存正確的暫存資料供使用者使用。在TS法中,客戶端會將IR中的資料代號與客戶端的暫存資料的資料代號比對,如果IR中的資料代號和暫存資料的資料代號相同,則比較兩資料的異動時間戳記是否相同;如果相同,則代表客戶端暫存的資料與伺服端的資料是一致的;否則,代表伺服端已對此筆資料做過異動,而客戶端所保留的是舊資料,則此筆資料必須由客戶端的暫存資料中移除。

Image20.gif (2786 bytes)

圖2、時間戳記法

在TS 法中客戶端的查詢交易必須在客戶端收到IR,且做完所有的驗証工作之後才能處理。此時, 如果查詢所須的資料完全存在於客戶端的暫存資料之中,則查詢交易馬上執行;否則,客戶端會透過上載通道向伺服端要求資料。伺服端接到客戶端的請求後便將資料透過下載通道送到客戶端,並存放於客戶端暫存資料之中,然後執行查詢交易。

TS法的精神是以資料最後被異動的時間,來比對客戶端的暫存資料是否仍然有效,它的缺點是所付出的IR成本也相當高,因為用來表示資料異動時間的時間戳記本身需要很大的位元數,而且對每一個資料異動都要傳送一個時間戳記,所以當伺服端對資料的異動頻率很高時,時間戳記本身會構成網路傳輸成本的主要部份。

二、 Bisecting IR 資料驗證法

  以下我們首先介紹Bisecting IR資料驗證法的基本精神,然後介紹Bisecting IR 的演算法。

2 .1 Bisecting IR的基本精神

考慮TS法中使用時間戳記的目的,也許我們可以用別種方式取代時間戮記的功用。以圖3為例,假設w=3一客戶端在10:00最後一次收到IR,然後離線;在12:00時又重新連線(Ti=12:00),今此客戶端以Ti時的IR(3個週期的異動資訊)做客戶端的資料驗証,此時資料項Y,W,C,O,D,A,N都被伺服端異動過,且此客戶端並未暫存這些資料項的新內容(因為此客戶端屬於離線狀態)。然而資料項G,Z,X的新內容在10:00IR驗証後,可能已由伺服端載入至此客戶端之中(在9:00之前此客戶端查詢G﹐ Z﹐ X,G﹐ Z﹐ X沒有暫存;且新的資料在10:00之前到達此客戶端)。因此,此客戶端在做資料驗証時,若沒有時間戳記,則可能會把已更新的G,Z,X暫存資料捨棄,造成錯誤驗證。TS法是以資料項上所附之時間戮記來驗証客戶端的暫存資料是否和伺服端的對應資料一樣新。

Image26.gif (4248 bytes)

3、伺服端端異動佇列內的情形

然而,換個角度來看,如果我們能將Ti客戶端所收到的IR驗証資料,區分為兩個部份:一部份含從未被執行過的驗証資料如{Y,W,C,O,D,A,N},另一部份含(以前)已被執行過的驗証資料,如{G,Z,X}。則在Ti時我們只要執行未被執行過的資料驗証,即{Y,W,C,O,D,A,N},則我們並不需時間戳記來幫忙避免錯誤驗證。在Bisecting IR法中,我們提出一個有效分割IR的方法;因此, 完全避免使用時間戳記。

 

2.2   Bisecting IR演算法

在Bisecting IR 法中,每當有資料發生異動時,伺服端就將被異動的資料的資料代號與異動時的時間戳記放到一個專門存放異動資訊的異動佇列中。當要廣播IR時,伺服端會將此異動佇列拿出處理,作成IR,然後廣播出去。客戶端在接到IR時,先對IR做必要之處理:將IR分為已執行過的部份及未執行過的部份;然後,只執行未驗證過的IR部份。Bisecting IR方法的運作方式如每隔L秒廣播一次IR,每個IR 包含w個廣播區間等,基本上和TS法相同。和TS法不同的地方是IR的內容及其使用方式,以一個IR包含w個廣播週期為例,Bisecting IR中一個IR內含最近w*L時間內被異動資料的資料代號,以及w個數字,每個數字代表對應廣播週期內異動的資料個數。

2.2.1 Bisecting IR伺服端演算法

 

伺服端演算法包括異動發生時的演算法及廣播IR的演算法。

伺服端資料異動時的演算法:

1.當有資料異動情形發生時,伺服端就產生一個新的異動資料節點。

2.被異動資料的資料代號、異動間的時間戳記放入此一異動資料節點(Node)之中,此節點的資料結構如下。

           struct node

                     {

                       INT pageid;(資料代號)

                      DOUBLE timestamp;(時間戳記)

                    }

3.搜尋現有的異動佇列,看是否有與本次被異動資料代號相同的節點,有則跳到4,沒有則跳5

4.將搜尋出來資料代號相同的異動節點從異動佇列中刪除。

5.將本次所產生的異動資料節點放入異動佇列之中。

6.完成

伺服端每隔固定時段(L)就將IR廣播出去,以下就是廣播IR時的演算法:

1.產生一個長度為w的一維陣列,稱之為numbers[w],wIR所涵蓋區段個數;此陣列用來記錄此次廣播的IR中每個廣播區段各有多個資料被異動。

2.將異動佇列中所有異動資料節點循序取出。

3.比對所有異動資料節點的時間戳記,將發生在Ti-w*L(Ti為這次廣播的時間)之後的異動節點取出。

4.找出每個時段的異動數目,填入各別的numbers陣列元素之中。

5.numbers中所記錄的值、和所有被循序取出的異動節點的資料代號組成一個IR,廣播出去。

6.完成

一、以圖三的異動為例,當資料發生異動時,伺服端便將異動資料的資料代號、異動時間戳記匯整到一個異動資料節點,然後將此異動資料節點放入異動佇列之中,異動佇列內容如表一所示。

12:00時伺服端準備要廣播IR時,伺服端會去異動佇列(如表一所示)中,找出在9:00以後(12:003小時)所發生的異動的節點之資料代號,如表二所示。並用一個numbers的一維陣列記錄從現在開始往前w個時段,異動佇列中每個時段各發生幾次資料異動,如表三所示。然後將numbers的內容,與表二所記錄在過去w過區段內的異動資料代號循序取出組成IR,並將此IR廣播出去。此時IR內容如表四所示。

表一、使用Bisecting IR法,伺服端12:00時異動佇列內容如下

資料代號

...

E

G

Z

X

Y

W

C

O

D

A

N

時間戳記

...

8:35 9:13 9:31 9:48 10:03 10:13 10:32 11:15 11:25 11:35 11:50

表二、使用Bisecting IR法,伺服端在12:00時經過比較,去除在w*L時間(三小時)前所異動的訊息後,其異動佇列內容如下

資料代號

G

Z

X

Y

W

C

O

D

A

N

表三、使用Bisecting IR法,伺服端在12:00時numbers中記錄的情形如下

現在起往前第幾個時段

1

2

3

異動資料個數

4

    3     3

表四、使用Bisecting IR法,伺服端12:00時所廣播的IR內容如下

異動資料個數

4

   3    3

資料代號

G

Z

X

Y

W

C

O

D

A

N

 

2.2.2 Bisecting IR客戶端演算法

 

我們在伺服端的演算法中可以看到,伺服端有一個異動佇列專門用來存放異動資訊;相對地在客戶端也有一個暫存佇列,用來記錄客戶端現在擁有那些資料。當使用者在客戶端查詢資料時,客戶端會先將此查詢需的資料代號放到一個查詢佇列之中,待收到IR時,才去處理此查詢佇列的東西;假設客戶端這次收到IR的時間為Ti,且上一次收到IR的時間為Tlb。

以下為客戶端收到IR時的演算法:

1.當客戶端收到IR時,先比較Ti-Tlb是否大於w*L(斷線是否太久);若是,則將所有暫存資料刪除並結束;否則,執行2

2.將所有IR中的資料代號取出,此時IR的內容會包含在過去w個時段內異動的資料代號與一數字串列用來記錄這w個時段內的每一時段中伺服端各有多少個資料被異動。

3.計算(Ti-Tlb)/L,即可知道客戶端遺失了幾個廣播區段內的異動資訊,假設少了m個。

4.客戶端再依IR中所記錄的每個時段的資料異動數目,循序取出 m個數字。

5.將所得的m個數字的值相加,即可獲知客戶端從上一次接到IR,到此次接到IR之間,伺服端的異動佇列中有多少個新的資料被異動,假設為K個。

6.客戶端會連續從IR中循序取出K個資料代號對客戶端的暫存資料做驗証。並將無效的暫存資料移除。

7.執行查詢佇列的查詢交易,當查詢交易所需的資料全部暫存在佇列中,則執行查詢交易;否則執行8

8.客戶端先向伺服端取得資料後,然後匯整到暫存資料之中,之後才執行查詢交易。

二、承例一,假設客戶端有12筆暫存資料,其如表五所示,且假設客戶端最後一次收到IR的時間在10:00、在11:30重新連線,且在11:3012:00之間使用者的查詢交易要求查詢三項資料,如表六所示。而在12:00收到IR,則收到IR時客戶端會有以下的動作:

客戶端在12:00時收到的IR原始內容如表七所示,之後客戶端計算(Ti-Tlb)/L,也就是(12:00-10:00)/1,得知客戶端從上次收到IR,到本次收到IR為止共經歷了2個時段。將IR中記錄伺服端每個廣播區段資料異動數列,循序取出2個相加,也就是4+3=7。得知在過去這2個時段內伺服端的異動佇列中增加7個異動訊息。從IR中循序取出7個異動資料代號如表八所示,並拿這7個資料代號對暫存資料做資料驗證。

經過驗証後,客戶端的暫存資料各有AND三筆要被刪除,刪除後暫存資料內容如表九所示。接下來處理查詢佇列中的內容,其中X這筆資料可從客戶端暫存資料中取得。而NR都已不存在於客戶端的暫存資料之中,所以客戶端會向伺服端提出NR這兩筆資料的請求。接著伺服端將NR這兩筆資料送到客戶端,此時客戶端的暫存資料內容如表十所示。此時查詢交易所需的資料全部暫存在客戶端,客戶端即可完成查詢交易的執行。

表五、使用Bisecting IR法,客戶端收到12:00IR以前,暫存佇列的資訊如下

資料代號

Q

Z

B

D

N

M

H

I

J

P

A

X

表六、使用Bisecting IR法,客戶端12:00時查詢佇列之內容如下

資料代號

N

R

X

表七、使用Bisecting IR法,客戶端在12:00時收到的IR內容如下

異動資料個數

4

3 3

資料代號

G

Z

X

Y

W

C

O

D

A

N

表八、使用Bisecting IR法,經過(Ti-Tlb)/L得知客戶端缺少2個時段內共7個異動資料的訊

息如下

資料代號

Y

W

C

O

D

A

N

表九、使用Bisecting IR法,客戶端將無效的資料刪除,暫存佇列內容如下

資料代號

Q

Z

B

M

H

I

J

P

X

表十、使用Bisecting IR法,客戶端處理完查詢交易後,其暫存佇列的內容如下

資料代號

Q

Z

B

M

H

I

J

P

X

N

R

 

三、效益分析

 

網路傳輸成本包含下列兩種,一種是資料驗証傳輸成本,另一種則是資料下載傳輸成本。資料驗証傳輸成本包含IR傳輸量。而資料傳輸成本,則是當使用者向客戶端查詢資料時,此資料不在暫存資料之中,而需向伺服端下載資料,所需傳輸的資料量。

3.1 系統模擬環境設定

為了比較每個方法的優劣,所以我們做了一個系統模擬,系統模型定義如下:

參考[9]中的系統模型,我們假設所有的寫(write)的動作都是在伺服端完成的,而客戶端資料只能進行資料讀取動作,客戶端只有在連線狀態時,才可以接受使用者的查詢交易,而當客戶端收到查詢交易時,並不會馬上給使用者資料,而是會將此查詢交易先放到一個查詢佇列中。然後等待下一次收到IR時,會先去驗証暫存資料是否有效,然後再比較查詢交易所需的資料是否有存在於暫存資料中;若有,則將資料送給使用者;若沒有,則向伺服端取得資料後,再執行查詢交易。

我們假設在收到IR之後,下個時段客戶端成離線狀態機率為disp,每次離線的時間長度為平均數是的指數分配(Exponential distribution)

假設資料庫內共有N個資料、客戶端最多可擁有B個暫存資料。且為了更進一步比較暫存資料驗証法對網路流量的影響,我們假設所有客戶端中的暫存資料,只有經由驗証訊息來使之無效或者當驗証訊息不足時才能使之無效。我們假設客戶端所擁有的這B個暫存資料都是隨機從伺服端資料庫中取出的,日後該使用者在查詢資料時都不會超出這B個暫存資料,作如此假設將能更清楚的看出錯誤驗證對網路傳輸量的影響。

任兩個異動交易(update transaction)動作的間隔時間,是一個平均數為u的指數分配(Exponential distribution)。每個異動交易會異動到的資料項個數,是平均數為uu,上下界分別為uu/2uu*3/2的均勻分配(Uniform distribution)。假設資料庫的資料被異動呈傾斜式異動,當中有a%比例的資料,通常被c%的異動動作更改到。

而任兩個查詢交易(query transaction)動作的間隔時間,是一個平均數為q的指數分配。而每個查詢交易會查詢到的資料項個數,會呈現平均數為qq,上下界分別為qq/2qq*3/2的均勻分配(Uniform distribution)

假設每個資料內容有256個位元組、資料代號需64位元來表示、T表示一個時間戳記所需的位元數,在此為256位元。

表十一、系統模擬環境參數如下

變數名稱 定義 給值
N 伺服端資料庫的資料總數 100,000 個資料
B 客戶端最多可擁有多少筆暫存資料 5,000 個資料
u 任兩個異動交易動作的平均間隔時間,呈指數分配 100/異動交易
uu 每個異動交易會異動的資料個數之平均數

,呈現上下界分別為uu/2uu*3/2的均勻分配

10個資料
q 任兩個查詢交易動作的平均間隔時間,呈指數分配 10/查詢交易
qq 每個查詢交易會異動的資料個數之平均數

,呈現上下界分別為qq/2qq*3/2的均勻分配

20個資料
a-c 異動資料的傾斜程度 10% - 80%
disp 一個條件機率,當客戶端是連線狀態之下,下一個時段會開始離線的機率 0.1
每一次離線平均會離線多久,呈指數分配 400
L 廣播IR的間隔時間 20
w*L 一個IR涵蓋的時間長度 200(100L時段)
page 一個資料的內容有多少位元組 256 位元組
pageid 為資料代號的位元數 64 位元
T 表示一個時間戳記所需的位元數 256 位元

3.2 模擬結果分析

 

在圖4中我們模擬伺服端異動資料的頻率對網路傳輸成本影響。我們是取平均客戶端完成1000次的查詢動作,其相對應的網路傳輸成本來比較。

 

Image23.gif (7454 bytes)  (w=50,=200,M=100,000)

4、伺服端異動交易的到達平均時間間隔(sec為單位)對網路傳輸成本的影響

 

由此模擬結果我們可以看到,當伺服端異動資料的頻率越高時(異動動作的間隔時間越短時),TS法效能越差(因IR成本大),而Bisecting IR 資料驗証法則有相對較佳的網路傳輸成本。

在圖5中我們模擬disp值(客戶端斷線機率)對網路傳輸成本的影響,我們取平均客戶端完成1000次的查詢動作時,其相對應的網路傳輸成本為多少k位元組為比較的標準。而網路傳輸成本包含IR的傳輸成本及當查詢時在客戶端的暫存資料中找不到所需資料,而向伺服端要求資料所需的資料傳輸成本。

Image25.gif (7300 bytes)

 

(w=50,=200,M=100,000)

5、客戶端斷線機率大小對網路傳輸成本的影響

由此模擬結果我們可以看到當客戶端一直在維持在連線狀態時,Bisecting IR 資料驗証法的網路傳輸成本表現不錯。且可以看到不管用那一種暫存資料的方法,其網路傳輸成本都會比沒有使用暫存資料(圖中以No-cache代表沒有使用暫存資料的結果曲線)的情形好。但當斷線機率逐漸增加時,錯誤驗證的機會將會增加,而網路傳輸成本的IR部份也將逐漸成為網路傳輸的主要部份,最後使得網路傳輸成本爆增,甚至比不使用暫存資料的情形還糟。我們可以從圖5中看到TS法當斷線機率高時,其網路傳輸成本會增加的很快,是因為其網路傳輸成本的IR部份佔了網路傳輸成本的大部份。而我們所提的Bisecting IR 資料驗証法則在斷線機率超過50%時,其發生斷線過久而使得暫存資料全部無效的情形也增加,最後導致暫存資料功能不佳的狀況,使其網路傳輸成本逐漸大過不使用暫存資料的情形。

綜合以上,我們可以發現Bisecting IR 資料驗証法,在許多的狀況上都會得到相對較佳的網路傳輸成本。而TS法則在大部份的網路傳輸成本上的表現都不理想。

 

四、結論與未來發展方向

  

在行動計算環境中,我們必須有效地利用網路有限的頻寬,儘量減少網路的傳輸流量;而客戶端的資料暫存技術則是有效利用網路頻寬的方法。為使暫存資料有效,客戶端的暫存資料必須維持與伺服端一致。在本篇論文中,我們提出一個有效的暫存資料驗證法,稱為Bisecting IR 暫存資料驗証法。在 這個方法中,我們將客戶端所收到的驗證報告區分為兩部份:已經做過驗證的部份,以及未曾做過驗證的部份;而客戶端則只須處理未曾做 過驗證的部份。經由模擬發現,我們所提的方法明顯地降低了網路的資料流量。 在未來我們將研究行動計算環境下的資料先取(Prefetching)技術。使得客戶端的暫存資料不但能滿足目前應用的需要,也能滿足後續而來的應用的需要。

參考文獻

[1] T. Imielinski. and B. R. Badrinath. "Mobile Wireless    Computing: Challenges in Data Management." In Communications of the ACM,October 1994.

[2] D. Barbara and T. Imielinski. "Sleepers and Workaholics: Caching Strategies in Mobile Environments." In Proceedings of the ACM SIGMOD Conference on Management of Data, pages 1-12, 1994.

[3] Nuno Neves and W. Kent Fuchs. "Adaptive Recovery for Mobile Environments" Communications of The ACM, 40(1), pp. 68-74, 1997.

[4] Andrew S. Tanenbaum, Computers Networks, Prentice-Hall, 1996.

[5] George H. Forman and John Zahorjan. "The Challenges of Mobile Computing" IEEE Computers, 27(4), pp. 38-47, 1994.

[6] T. Imielinski, S. Viswanathan and B. R. Badrinath. "Data on Air: Organization and Access."IEEE Transactions on Knowledge and Data Engineering, VOL.9, NO. 3, 1997.

[7] J. Jing, O. Bukhres, A. Elmagarmid, and R. Alonso. "Bit-Sequences: A New Cache Invalidation Method in Mobile Environments."Technical Report CSD- TR-94-074, Department of Computer Sciences, Purdue University,May 1995.

[8] Yungho Leu, Kuopin Weng and Chi-Chung Lee. "A Sequence Number Based Cache Invalidation Scheme for Mobile Computing Environments" Proceeding of National Computer Symposium, Taichung, R.O.C., 1997.

[9] K. L. Wu, P. S. Yu and M. S. Chen. "Energy- Efficient Caching for Wireless Mobile Computing." In Data Engineering 1996.

[10] Yungho Leu, Kuopin Weng and Chi-Chung Lee. "Efficient Cache Invalidation Schemes for prolonged disconnected mobile clients in mobile computing environments" 1998 Workshop Distributed System Technologies & Applications, R.O.C., 1998.