status := joinreq
sendto e.JoinReq(n)
end if end event
event n.JoinReq(d) from m
if JoinForward and m = oldpred then
sendto pred.JoinReq(d) ⊲ Join Forwarding
else if LeaveForward then
sendto succ.JoinReq(d) ⊲ Leave Forwarding
Có thể bạn quan tâm!
-
Đồ Thị Biểu Diễn Tỷ Lệ Tìm Kiếm Thành Công (Fration Of Successful Lookups) Theo Băng Thông Trung Bình Một Node Sử Dụng (Average Live Bandwidth) Trong Mạng -
Đồ Thị Biểu Diễn Tỷ Lệ Tìm Kiếm Thành Công Theo Băng Thông Trung Bình Một Node Sử Dụng Của Kelisp Và Tapestry Với Rtt=1S, 10S Và Node Join/leave Với -
Ả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 -
Đá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 -
Đá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 - 12
Xem toàn bộ 98 trang tài liệu này.
else if pred 6= nil and d (n, pred] then sendto succ.JoinReq(d)
else
if lock 6= free or pred = nil then sendto m.RetryJoin()
else
JoinForward := true lock := taken
sendto m.JoinPoint(pred) oldpred := pred
pred := m
end if end if
end event
event n.JoinPoint(p) from m status :=joining
pred := p succ := m
sendto pred.NewSucc()
end event
event n.NewSucc() from m sendto succ.NewSuccAck(m) succ := m
end event
event n.NewSuccAck(q) from m lock := free JoinForward := false sendto q.JoinDone()
end event
event n.JoinDone() from m lock := free
status := inside
end event
Thuật toán 3.1. Thuật toán join tối ưu hóa
3.3.2.3. 15BQuá trình rời mạng của một node
Cơ chế leave của một node khỏi vòng Chord được biểu diễn trong HX
ình 3.3X, giả
sử node q muốn rời khỏi mạng, node q là successor của p và predecessor của r. Quá trình leave như sau:
Khi node q muốn rời khỏi mạng, nó phải lấy lock của bản thân, nếu lock của q đang ở trạng thái taken thì q phải đợi đến khi lock chuyển sang trạng thái free. Khi lock của q ở trạng thái free, nó lấy lock và gửi thông điệp yêu cầu rời khỏi mạng đến node r. Nếu lock của r không free thì node q phải đợi, khi lock của r free, r sẽ gửi thông điệp cho phép q rời khỏi mạng. Lúc này
Hình 3.3. Biểu đồ thời gian biểu diễn quá trình một node rời khỏi mạng
event n.Leave() from app
if lock 6= free then ⊲ Application should try again later
else if succ = pred and succ = n then
else
⊲ Last node, can quit
status := leavereq lock := true
sendto succ.LeaveReq()
end if end event
event n.LeaveReq() from m
if lock = free then
lock := taken
sendto m.GrantLeave() state :=predleavereq
else if lock 6= free then
sendto m.RetryLeave()
end if end event
event n.RetryLeave() from m status := inside
lock := free ⊲ Retry leaving later
end event
event n.GrantLeave() from m LeaveForward := true status := leaving
sendto m.LeavePoint(pred)
end event
event n.LeavePoint(q) from m status :=predleaving pred := q
sendto pred.UpdateSucc()
end event
event n.UpdateSucc() from m sendto succ.UpdateSuccAck() succ := m
end event
event n.UpdateSuccAck() from m
sendto succ.LeaveDone() ⊲ Leave the system
end event
event n.LeaveDone() from m lock := free
status := inside
end event
Thuật toán 3.2. Thuật toán leave tối ưu hóa
3.3.2.4. 16BXử lý trường hợp node bị lỗi
Các hàm FixSucc, FixPred (chạy định kỳ) và cơ chế timer được sử dụng để xử lý trường hợp node bị lỗi. Periodic stabilization có hai mục đích: gộp các node mới vào vòng và xóa các node lỗi khỏi vòng.
+ Cơ chế timer
Mỗi khi lock của node i chuyển sang trạng thái busy, node khởi tạo timer. Timer sẽ tắt ngay khi lock của node chuyển sang trạng thái free. Nếu quá thời gian định trước (timeout), lock chưa chuyển sang trạng thái free, node sẽ chuyển trạng thái của lock sang free và thiết lập các biến JoinForward và LeaveForward sang false.
Nếu timeout xuất hiện tại node đang join vào mạng, có 2 trường hợp xảy ra. Nếu succ = nil, nó sẽ khởi động lại quá trình join cho đến khi nó lấy được con trỏ successor. Nếu succ ≠ nil, các lock sẽ được giải phóng và quá trình stabilization sẽ đưa node này vào vòng.
Nếu timeout xảy ra tại node đang rời khỏi mạng, node đó sẽ rời khỏi hệ thống không đưa ra thông báo.
Nếu timeout xảy ra tại successor của node đang trong quá trình gia nhập hoặc rời khỏi mạng, node sẽ thiết lập biến lock của nó sang trạng thái free và khởi tạo quá trình stabilization.
Nếu predecessor thực sự bị fail, quá trình stabilization sẽ tự động khôi phục hệ thống và các lock tương ứng được giải phóng, khi đó hệ thống sẽ trở về trạng thái đúng.
FixSucc, FixPred tương tự như các thuật toán manintenance của Chord. Hai cơ chế này đảm bảo p.succ.pred = p đối với bất kỳ node p nào.
Cơ chế FixSucc định kỳ chuyển con trỏ successor của một node tới node còn trên mạng gần nó nhất theo chiều kim đồng hồ. Nếu một node phát hiện successor của nó không còn tồn tại nữa, node sẽ thay thế successor bằng node đầu tiên f còn trên mạng trong successor list. Ngay cả khi f kông phải là successor của node này thì có chế FixSucc sẽ cập nhật con trỏ succ trỏ đến successor gần nhất.
Cơ chế FixPred định kỳ chuyển con trỏ predecessor của một node tới node gần nhất còn trên mạng theo hướng ngược chiều kim đồng hồ và thiết lập con trỏ pred thành nil nếu nó phát hiện node predecessor không còn tồn tại trên mạng nữa. Điều kiện trong thủ tục Notify được đổi lại để con trỏ pred luôn cập nhật mỗi khi nó có giá trị nil.
Successor-list tại mỗi node được duy trì định kỳ. Mỗi node định kỳ cập nhật successor-list của nó bằng cách copy successor-list của successor, đặt successor vào đầu của successor-list và chặt successor-list tới một kích thước cố định.
Thuật toán join được xửa để successor của node đang trong quá trình join vào mạng gửi successor-list cùng với thông điệp JoinPont, như vậy các node có thể khởi tạo successor list của mình.
procedure n.CheckPredecessor(p) //Locally called periodically
if IsAlive(pred) = false then
pred := nil
end if end procedure
procedure n.Stabilize() // Locally called periodically
try
p := succ.GetPredecessor()
if p=nil and p ∈ (n, succ] then
succ := p
end if
slist := succ.GetSuccList()
succlist := succ + slist //Prepend succ to slist succlist := trunc(succlist, k) //Right-truncate
//to fixed size k
succ.Notify(n)
end try catch(RemoteException)
succ := getFirstAliveNode(succlist) //Get closest alive
//node
end catch end procedure
procedure n.GetPredecessor()
return pred
end procedure
procedure n.GetSuccList()
return succlist
end procedure
procedure n.Notify(p)
if pred = nil or p ∈ (pred, n] then
pred := p
end if end procedure
Thuật toán 3.3. Quá trình stabilization định kỳ để xử lý failure
3.3.2.5. B17B ảng finger
Bảng finger được xây dựng như trong thuật toán Chord
3.3.2.6. 18BQuá trình lookup
Có thể tìm kiếm sử dụng proxy, dựa trên quá trình tìm kiếm thông thường của Chord hoặc sử dụng tìm kiếm song song (phần nhân bản)
3.4. Giải pháp caching proxy
3.4.1. Mục tiêu
Giải pháp caching proxy nhằm làm giảm độ trễ tìm kiếm và góp phần cải tiến cơ chế replication.
3.4.2. Cơ chế làm việc
3.4.2.1. 91BSơ đồ mạng overlay
Mạng peer-to-peer được chia thành hai vòng Chord, một vòng là các nút mạng thông thường, vòng kia bao gồm các proxies. Không gian ID của hai vòng giống nhau.
Các proxy được chia thành hai loại: main proxy và normal proxy:
Mỗi main proxy chịu trách nhiệm cho các normal proxy theo sau nó và main proxy đứng ngay trước nó.
Mỗi normal proxy chịu trách nhiệm cho các node có ID đứng trước ID của nó và đứng sau ID của proxy trước nó.