nhân bản trong một số lớp khác. Đối với các node được nhân bản them thì nhân bản là không đối xứng, node này không nhân bản các item của các node trong các lớp nó được nhân bản bổ xung.
Các node trong các lớp liên kết với ID i được xác định như sau: fk: rk(i, x) = i (x − 1) + N/f + (k-1).N/f
Với N/f < N/k or f > k
k = 1 là mức nhân bản cơ sở.
k > 1 nhân bản bổ xung trong đó k được tính từ proxy dựa trên tần suất tìm kiếm
Quá trình duy trì
Thuật toán join
Khi một node n join vào hệ thống, nó sẽ kích hoạt sự kiện JoinReplication, sự kiện này gửi thông điệp RetrieveItems tới successor để lấy về các item n cần lưu. Thông điệp bao gồm các thông tin về các item nằm trong giải (pred,n], trong đó pred là ID của predecessor và n là ID của nó.
Có thể bạn quan tâm!
-
Ảnh Hưởng Của Tham Số “Base” Đối Với Hiệu Năng Của Tapestry (Trái) Và Tham Số “Gossip Interval” Đối Với Hiệu Năng Của Mạng Kelips Trong Mạng -
Biểu Đồ Thời Gian Biểu Diễn Quá Trình Một Node Rời Khỏi Mạng -
Đánh giá hiệu năng của một số thuật toán bảng băm phân tán DHT và đưa ra giải pháp cải tiến hiệu năng của thuật toán CHORD - 11
Xem toàn bộ 98 trang tài liệu này.
Khi successor nhận được thông điệp RetrieveItems, nó khởi tạo một mạng hai chiều rỗng ( f , N). Sau đó, các item liên kết với một ID trong giải xác định được sao từ bảng HashTable cục bộ tới mảng vừa tạo và được gửi trở lại trong thông điệp Replicate tới node vừa join vào mạng. Khi nhận được thông điệp Replicate, node mới join vào mạng sẽ sao các item trong mảng vào bảng HashTable cục bộ. Node mới lúc này sẽ sẵn sàng nhận truy vấn tìm kiếm từ các node khác trong hệ thống.
Thuật toán leave
Thuật toán leave làm việc tương tự như thuật toán join. Khi một node muốn leave khỏi hệ thống, nó sẽ kích hoạt sự kiện LeaveReplication, sự kiện này sử dụng sự kiện RetrieveItems để sao các item mà nó chịu trách nhiệm và gửi chúng trong thông điệp Replicate tới node successor.
Thuật toán chèn
Để chèn một item, node muốn chèn thực hiện quá trình chèn song song tới các node chịu trách nhiệm cho item.
event n.JoinReplication() from m
sendto succ.RetrieveItems(pred, n, n)
end event
event n.LeaveReplication() from m
sendto n.RetrieveItems(pred, n, succ)
end event
event n.RetrieveItems(start, end, p) from m
for r := 1 to f do items[r] := Æ i := start
while i 6= end do
i := i 1
items[r][i] := localHashTable[r][i]
end while end for
sendto p.Replicate(items, start, end)
end event
event n.Replicate(items, start, end) from m
for r := 1 to f do
i := start
while i 6= end do
i := i 1
localHashTable[r][i] := items[r][i]
end while end for
end event
Thuật toán 3.7. Quá trình tìm kiếm và chèn trong giải pháp nhân bản đối xứng
event n.InsertItem(key, value) from app
for r := 1 to f do
replicaKey := key (r − 1)Nf n.Lookup(replicaKey,AddItem(replicaKey, value,
r))
end for end event
procedure n.AddItem(key, value, r) localHashTable[key][r] := value
end procedure
event n.LookupItem(key, r) from app replicaKey := key (r − 1)Nf
Lookup(replicaKey,GetItem(replicaKey, r))
end event
procedure n.GetItem(key, r)
return localHashTable[r][key]
end procedure
Thuật toán 3.8. Join và leave trong trường hợp nhân bản đối xứng
Thuật toán xử lý failure
event n.FailureReplication( f ailed, predFailed, r) from m s := predFailed (r − 1)Nf
e := f ailed (r − 1)Nf
sendto n.StartBulkOwn((s, e], RetrieveItems(s, e, succ))
end event
Thuật toán 3.9. Xử lý failure trong nhân bản đối xứng
event n.StartBulkOwn(I, msg) from m
sendto n.BulkOwn(I, I, n, msg) ⊲ Local message to itself
end event
event n.BulkOwn(I, R, next, msg) from m
MS := R ∩ (u(M), n] ⊲ u(M) is same as pred
if MS 6= Æ then
Deliver(msg, MS) ⊲ App is responsible for ids in MS
end if
limit := n lnext := next
sentsucc :=false
for i := M downto 1 do ⊲ Node has M unique pointers
J := (u(i), limit]
if I ∩ J 6= Æ then
K := (u(i − 1), u(i)]
sendto u(i).BulkOwn(I ∩ J, I ∩ K, lnext, msg) I := I − J ⊲ Same as I := I − (I ∩ J)
limit := u(i) lnext := u(i) if i = 1 then
sentsucc :=true end if
end if end for
J := (n, u(1)]
if I ∩ J 6= Æ and sentsucc = false and next 6= u(1) then sendto u(1).BulkOwn(Æ, I ∩ J, limit, msg)
end if end event
Thuật toán 3.10. Thuật toán bulk owner operation
Kết luận
Sự phát triển mạnh mẽ và đa dạng của các thiết bị truy cập mạng như điện thoại, PDA, TV,… là một thách thức đối với mạng structured overlay hiện nay. Với sự xuất hiện của các thiết bị này, mạng trở nên bất ổn và kéo theo sự sụt giảm nghiêm trọng hiệu năng của mạng. Cải tiến hiệu năng của mạng trong điều kiện làm việc mới là bài toán đặt ra cho cộng đồng nghiên cứu peer-to-peer hiện nay.
Sau khi tóm tắt lý thuyết tổng quan về peer-to-peer, luận văn đánh giá, phân tích và so sánh hiệu năng của các DHT như Chord, Kademlia, Kelips và Tapestry trong điều kiện churn rate cao sử dụng phương pháp mô phỏng. Dựa trên cơ chế hoạt động của Chord, kết hợp với kết quả mô phỏng, luận văn đã chỉ ra hạn chế của giao thức Chord trong điều kiện churn rate cao và đưa ra các giải pháp nâng cao hiệu năng của giao thức này.
Trong giai đoạn tiếp theo, tác giả sẽ cài đặt các giải pháp nâng cao hiệu năng của Chord và đánh giá kết quả đạt được, trên cơ sở đó tác giả tiếp tục cải tiến hơn nữa các giải pháp để Chord đạt được hiệu suất cao trong môi trường truyền thông không dây.
Trong quá trình nghiên cứu, một số kết quả nghiên cứu đã được công bố trên các bài báo quốc tế và trong nước [ 15, 16, 17, 18].
Tài liệu tham khảo
[1]. Jinyang Li, Jeremy Stribling, Robert Morris, M. Frans Kaashoek and Thomer M. Gil. “A performance vs. cost framework for evaluating DHT design tradeoffs under churn”
[2]. Ion Stoica, Robert Morris, David Karger, Frans Kaashoek, and Hari Balakrishnan. “Chord: A scalable Peer-To-Peer lookup service for internet applications”. In Proceedings of the 2001 ACM SIGCOMM Conference, pages 149–160, 2001.
[3]. Ali Ghodsi. “Distributed k-ary System: Algorithms for Distributed Hash Tables”, PhD dissertation, KTH-Royal Institute of Technology, October 2006.
[4]. Ali Ghodsi, Luc Onana Alima, Seif Haridi. Symmetric Replication for Structured Peer-to-Peer Systems, DBISP2P2005, The 3rd International Workshop on Databases, Information Systems and Peer-to-Peer Computing, August 28-29, 2005, Trondheim, Norway
[4]. Ruud van Kessel. “Peer-to-peer storage: a survey on the common used techniques”, 2006
[5]. S. Rhea, D. Geels, T. Roscoe, and J. Kubiatowicz, “Handling churn in a DHT,” in roceedings of the 2004 USENIX Technical Conference, June 2004.
[6] J. Li, J. Stribling, T. Gil, R. Morris, and M. F. Kaashoek, “Comparing the performance of distributed hash tables under churn,” in Proceedings of the 3rd International Workshop on Peer-to- Peer Systems, Feb. 2004.
[7]. P. Maymounkov and D. Mazieres, “Kademlia: A peer-to-peer information system based on the XOR metric,” in Proceedings of the 1st IPTPS, Mar. 2002.
[8]. I. Gupta, K. Birman, P. Linga, A. Demers, and R. van Renesse, “Kelips: Building an efficient and stable P2P DHT through increased memory and background overhead,” in Proceedings of the 2nd IPTPS, 2003.
[9]. B. Y. Zhao, L. Huang, J. Stribling, S. C. Rhea, A. D. Joseph, and J. D. Kubiatowicz, “Tapestry: A resilient global-scale overlay for service deployment,” IEEE Journal on Selected Areas in Communications, vol. 22, no. 1, pp. 41–53, Jan. 2004.
[10]. K.P.Gummadi, R.Gummadi, S.Gribble, S.Ratnasamy , S.Shenker, and I. Stoica, “The impact of DHT routing geometry on resilience and proximity,” in Proceedings of the 2003 ACM SIGCOMM, Aug. 2003.
[11]. F. Dabek, M. F. Kaashoek, J. Li, R. Morris, J. Robertson, and E. Sit, “Designing a DHT for low latency and high throughput,” in Proceedings of the 1st NSDI, March 2004.
[12]. A. Gupta, B. Liskov, and R. Rodrigues, “Efficient routing for peer-to-peer overlays,” in Proceedings of the 1st NSDI, Mar. 2004.
[13]. Eng Keong Lua, Jon Crowcroft, Marcelo Pias, Ravi Sharma and Steven Lim, “A Survey and Comparison of Peer-to-Peer Overlay Network Schemes” IEEE COMMUNICATIONS SURVEY AND TUTORIAL, MARCH 2004
[14]. P2PSIM home page, UHhttp://pdos.csail.mit.edu/p2psim/U
[15]. Giang Ngo Hoang, Hung Nguyen Chan, Thang Le Quang, “Performance study of distributed hash table mechanisms on p2p overlay network under extreme conditions”, International Symposium on Electrical-Electronics Engineering – ISEE 2007, Hochiminh, Vietnam.
[16]. Nguyen Chan Hung, Ngo Hoang Giang, Le Quang Thang, “Comparative study on Distributed Hash Table algorithms of P2P network”, Proceeding NOC2007 12th European Conference on Networks & Optical Communications.
[17]. “Performance Evaluation of Distributed Hash Table (DHT) Chord algorithm”, MCSE 2007, Proceeding of Modeling of Complex System and Environment MCSE 2007 by ISSAT (IEEE -
International Society of Science and Applied Technologies Conference), Hochiminh, Vietnam [18]. Hung Nguyen Chan, Giang Ngo Hoang, Thang Le Quang, Tan Pek Yew, “Performance study of
Chord, Kelips and Tapestry protocols on structured Peer-to-Peer Overlay networks”, in press,
Special issues of Post & Telecommunications & Information Technology Journal, 2008