Luận văn Xây dựng và thử nghiệm một giao thức định tuyến trong môi trường mạng ad-Hoc

-25- Chương 3. Thuật toán định tuyến Bridge - Virtual Ring Routing Chúng tôi đã khảo sát một số thuật toán định tuyến trong môi trường mạng không dây di động ad-hoc và phân tích những ưu khuyết điểm. Trên cơ sở đó, luận văn đề xuất một giao thức định tuyến mới, Brigde - Virtual Ring Routing (BVRR), mà hạt nhân là giao thức định tuyến VRR [3]. Giao thức BVRR giải quyết vấn đề phân vùng mạng còn tồn tại trong giao thức VRR [3] bằng cách xây dựng các cầu nối giữa các phân vùng giao nhau. Bằng cách này, giao thức BVRR giúp giảm chi phí để xây dựng lại vòng ảo khi đồ hình mạng thay đổi. Đồng thời, BVRR vẫn đảm bảo không xảy ra tràn thông điệp cũng như hạn chế không gian lưu trữ tại mỗi nút mạng. Giao thức BVRR thích hợp cho môi trường mạng có kích thước lớn và các nút mạng phân bố ngẫu nhiên. 1.1. Một số thuật ngữ sử dụng trong giao thức BVRR TN 3.1.1. Phân hoạch chủ (home partition) Home partition của một nút x là phân hoạch đầu tiên mà nút x liên lạc trực tiếp khi mới gia nhập mạng. Một nút mạng x được xem là liên lạc trực tiếp được với một phân hoạch p, nếu x có liên kết với Np nút láng giềng vật lý trong phân hoạch p. TN 3.1.2. Phân hoạch hiện hành Phân hoạch hiện hành của một nút là một phân hoạch mà nút đang liên lạc trực tiếp. Trường hợp nút có thể liên lạc trực tiếp với nhiều phân hoạch, phân hoạch hiện hành của nút là phân hoạch chủ (nếu nút còn liên lạc trực tiếp với phân hoạch chủ) hoặc phân hoạch có định danh nhỏ nhất. Trường hợp, nút không liên lạc được với bất kỳ phân hoạch nào, phân hoạch hiện hành của nút là NULL. -26- TN 3.1.3. Láng giềng ảo (virtual neighbor) Nút y là một láng giềng ảo của nút x nếu khoảng cách vị trí giữa nút x và nút y trên vòng ảo nhỏ hơn hoặc bằng R/2 (với R là một hằng số nguyên dương). Tập các nút láng giềng ảo của một nút được ký hiệu là vset (virtual neighbor set) TN 3.1.4. Láng giềng vật lý (physical neighbor) Nút x và nút y được gọi là láng giềng vật lý của nhau nếu chúng nằm trong phạm vi vùng phủ sóng của nhau. Tập các nút láng giềng vật lý của một nút được ký hiệu là pset (physical neighbor set). Tập các nút láng giềng (vật lý và ảo) của một nút có tính chất đối xứng. Nghĩa là nếu nút x được đánh dấu là láng giềng của nút y thì nút y cũng là một láng giềng của nút x. 1.2. Mô tả giao thức BVRR Trong không gian mạng có kích thước lớn và các nút phân bố ngẫu nhiên, các nút mạng có thể phân tách thành nhiều phân hoạch (partition), như hình 3.1. Mỗi phân hoạch gồm các nút mạng có thể liên lạc với nhau trực tiếp hoặc thông qua các nút mạng trung gian. Mỗi phân hoạch có một định danh, partition identifier - PID, duy nhất. Định danh của phân hoạch được ấn định tự động tại thời điểm ban đầu khi mạng đạt trạng thái ổn định. -27- Hình 1.1. BVRR: mạng gồm 2 phân hoạch. (a) đồ hình mạng vật lý, (b) vòng ảo tương ứng với mỗi phân hoạch Mỗi nút mạng có một định danh, node identifier - NID, duy nhất cố định và độc lập vị trí1. Định danh của một nút bao gồm hai thành phần (xem hình 3.2): định danh của phân hoạch home partition, partition identifier - PID, và định danh của host, host identifier - HID. Đây chính là điểm khác biệt của BVRR so với VRR [3] gốc. Định danh của host là duy nhất, cố định và có thể được ấn định bằng bất kỳ thuật toán nào. Định danh phân hoạch của một nút mạng được xác định khi nút xác định phân hoạch home partition và được gán bằng định danh của phân hoạch home partition. Định danh của nút mạng không thay đổi từ khi nút xác định được phần định danh phân hoạch PID. PID (m bits) HID (n bits) Hình 1.2. BVRR: cấu trúc định danh của một nút mạng Các nút mạng trong cùng một phân hoạch được tổ chức thành một vòng ảo theo thứ tự định danh của host HID. Nghĩa là không giống như giao thức VRR [3], 1định danh của nút mạng không phụ thuộc vào vị trí hiện hành của nút mạng. -28- giao thức BVRR xem mạng có thể tồn tại nhiều vòng ảo. Hình 3.1 minh họa cách tổ chức các nút mạng trên vòng ảo tương ứng với đồ hình vật lý. Mỗi nút mạng quản lý các nút láng giềng vật lý của mình, được gọi là tập láng giềng vật lý pset. Trong hình 3.1, nút mạng 016F có các láng giềng vật lý là 018B và 016C. Ngoài tập láng giềng vật lý pset, mỗi nút mạng còn quản lý R/2 nút mạng lân cận theo chiều kim đồng hồ và R/2 nút mạng lân cận theo chiều ngược chiều kim đồng hồ trên vòng ảo, được gọi là tập láng giềng ảo vset. Để đảm bảo các nút mạng định tuyến gói tin chính xác và hiệu quả, tập các nút láng giềng ảo của một nút mạng phải có tính đối xứng và nhất quán: x là láng giềng ảo của y thì y cũng là một láng giềng ảo của x. Ví dụ theo mô hình mạng hình 3.1, với R=4, nút mạng 016F có các láng giềng ảo là 01FB, 016C, 017F và 0180. Trong trường hợp một nút x liên lạc trực tiếp được với hai phân hoạch trở lên, nút x trở thành một cầu nối (bridge) liên kết các phân hoạch và được gọi là gateway. Ngoài ra, giao thức BVRR cũng chọn nút mạng có định danh của host nhỏ nhất trong mỗi phân hoạch làm nút đại diện (representative). Nhằm tăng hiệu quả thực hiện của giao thức, cũng như lưu thông tin dự phòng, giao thức BVRR chọn các nút láng giềng vật lý với nút đại diện làm nút đại diện dự trữ (bakup representative node). Nút gateway và nút đại diện gọi chung là nút chuyển tiếp (forwarding node). Hình 3.3 minh họa vai trò của các nút mạng trong mỗi phân hoạch. Với môi trường mạng minh họa trong hình 3.1, các nút mạng bắt đầu di chuyển tự do. Tại thời điểm t, đồ hình mạng đạt trạng thái như hình 3.3a. Và nút mạng 016F tạo thêm liên kết mới với một số nút mạng trong phân hoạch 1A, 1A11 và 1A16. Khi đó, nút mạng 016F liên lạc trực tiếp với hai phân hoạch 01 và 1A nên 016F trở thành cầu nối giữa hai phân hoạch và đóng vai trò như một gateway trong mỗi phân hoạch (hình 3.3b). Nút mạng 016C và 1A05 được chọn làm nút đại diện của phân hoạch 01 và 1A theo thứ tự. Tương ứng các nút láng giềng vật lý của nút -29- 016C và 1A05 cũng trở thành nút đại diện dự trữ. Đặc biệt, nút 016F vừa đóng vai trò là nút dại diện dự trữ vừa là một gateway. 016C 016F 0180 0185 018B 01A1 01B0 01F2 01FB 1A05 1A11 1A16 1A61 1A70 1AB9 1AF1017F 1A14 017F01 1A 016C 016F 0180 0185 018B 01A1 01B0 01F2 01FB 1A05 1A11 1A14 1A16 1A61 1A70 1AB9 1AF1 gateway nút mạng 016F Nút đại diện Nút đại diện dự trữ Hình 1.3. BVRR: minh họa vai trò của các nút mạng trong phân hoạch Như vậy, nếu một gói tin có nút nguồn và nút đích thuộc cùng một phân hoạch thì ta chỉ cần định tuyến gói tin dọc theo vòng ảo trong phân hoạch đó tương tự như giao thức VRR [3]; ngược lại gói tin bắt buộc phải đi qua các nút gateway giữa hai phân hoạch chứa nút nguồn và nút đích. Giao thức BVRR thực hiện định tuyến một gói tin dựa trên ý tưởng này. BVRR thực hiện định tuyến gói tin đến nút mạng có phần định danh của host HID gần với định danh của nút đích nhất trong -30- nội bộ phân hoạch nếu nút mạng gởi và nút mạng đích đến thuộc về cùng một phân hoạch. Ngược lại, gói tin được định tuyến đến đích thông qua các nút gateway. 1.3. Thông tin định tuyến Tương tự giao thức VRR [3], mỗi nút mạng thiết lập và duy trì một bảng định tuyến (routing table). Bảng định tuyến lưu thông tin định tuyến của các vset- path giữa nó với các nút mạng trong tập láng giềng vật lý pset và tập láng giềng ảo vset trong mỗi phân hoạch mà nút mạng đang liên lạc trực tiếp cùng các vset-path có đi ngang qua nút đó. Ngoài ra, các nút gateway thiết lập một vset-path giữa nó với nút đại diện trong mỗi phân hoạch mà nút gateway liên lạc trực tiếp. Thông tin này đảm bảo một gói tin có thể chuyển tiếp được đến nút gateway hay nút đại diện khi cần chuyển tiếp liên phân hoạch. Thông tin về vset-path giữa hai nút mạng lưu trong bảng định tuyến tại một nút gồm các trường dữ liệu sau: • Định danh phân hoạch - PID: định danh của phân hoạch chứa vset- path. • Định danh của hai điểm mút (endpoint) của vset-path - Ea, Eb, với Ea là định danh của nút mạng đã khởi tạo vset-path này. • Định danh của nút kế tiếp (next hop) - Na, Nb là định danh của nút láng giềng vật lý mà chúng ta cần chuyển gói tin đến khi muốn chuyển gói tin đến điểm mút tương ứng. • Định danh của vset-path - PathID. Bộ ba dùng để phân định các vset-path khác nhau. Bảng 3.1 minh họa bảng định tuyến của nút mạng 016F với hiện trạng mạng như hình 3.3. Dòng 1 đến 7 là các vset-path thuộc về phân hoạch 1A, dòng 8 đến 16 là các vset-path thuộc về phân hoạch 01. Trong phân hoạch 01, dòng 8 đến dòng 11 là các vset-path giữa nút 016F và các láng giềng vật lý; dòng 12 và dòng 15 là vset- -31- path giữa nút 016F với các láng giềng ảo; và dòng 16 là vset-path giữa nút mạng 016F và nút đại diện của phân hoạch 01, nút 016C, do 016F là nút gateway. Bảng 1.1. BVRR: bảng định tuyến của nút 016F PID Ea Eb Na Nb pathID 1A 1A16 016F 1A16 FFFF FFFF 1 1A 1A11 016F 1A11 FFFF FFFF 2 1A 1A70 016F 1A16 FFFF 7 3 1A 1AB9 016F 1A16 FFFF 9 4 1A 1A16 016F 1A16 FFFF 4 5 1A 1A61 016F 1A11 FFFF 5 6 1A 1A05 016F 1A11 FFFF F02A 7 01 016C 016F 016C FFFF FFFF 8 01 01B0 016F 01B0 FFFF FFFF 9 01 0185 016F 0185 FFFF FFFF 10 01 018B 016F 018B FFFF FFFF 11 01 016F 01FB FFFF 01B0 6 12 01 016F 017F FFFF 018B 7 13 01 016F 0180 FFFF 018B 9 14 01 016F 016C FFFF 016C 17 15 01 016C 016F 016C FFFF F014 16 Để đảm bảo có thể định tuyến được gói tin giữa hai nút mạng thuộc các phân hoạch khác nhau, thì các nút chuyển tiếp (nút đại diện và nút gateway) ngoài việc duy trì bảng định tuyến còn thiết lập và duy trì một bảng chuyển tiếp (forwarding table). Bảng chuyển tiếp tại mỗi nút chuyển tiếp lưu thông tin cần chuyển tiếp gói tin đến nút chuyển tiếp nào tiếp theo khi muốn chuyển gói tin đến một phân hoạch p -32- và số lần cần chuyển tiếp tương ứng. Mỗi dòng dữ liệu trong bảng chuyển tiếp gồm các trường dữ liệu sau: • Định danh của phân hoạch đích đến PID • Danh sách các bộ là danh sách các định danh nút chuyển tiếp NID cần chuyển tiếp gói tin đến khi muốn đến được phân hoạch đích PID với số lần cần phải chuyển tiếp hopcount. Bảng 3.2 minh họa bảng chuyển tiếp tại nút mạng 1A05 trong hiện trạng mạng như hình 3.3. Dòng 1 cho biết nếu muốn định tuyến gói tin sang phân hoạch 01 thì nút 1A05 chuyển tiếp gói tin đến nút chuyển tiếp 016F với một lần chuyển tiếp. Bảng 1.2. BVRR: Bảng chuyển tiếp của nút mạng 1A05 Phân hoạch Thông tin chuyển tiếp 01 1 1.4. Quá trình một nút mạng mới tham gia vào mạng Khi một nút x lần đầu tham gia vào mạng, nút x khởi tạo tập láng giềng vật lý pset, tập láng giềng ảo vset và bảng định tuyến. Đầu tiên nút x bắt đầu tìm các nút láng giềng vật lý pset và dùng các nút mạng này như là một proxy để định tuyến các thông điệp đến các nút mạng khác. Nút x tìm một proxy bằng cách gởi và lắng nghe thông điệp hello. Thông điệp hello được gởi quảng bá (broadcast) đến các nút láng giềng vật lý theo định kỳ. Khi nút x liên lạc trực tiếp được với một phân hoạch mới, nút x thực hiện quá trình tìm các nút láng giềng ảo vset bằng cách gởi một thông điệp vset_setup_req đến chính nó thông qua một proxy trong phân hoạch đó. Thông điệp vset_setup_req -33- được định tuyến cục bộ trong phân hoạch theo thuật toán chuyển tiếp (xem chi tiết trong mục 3.7) đến nút y có định danh của host gần với x nhất. Khi nút y nhận một thông điệp vset_setup_req từ nút x và là nút có định danh host gần với x nhất, nút y phản hồi cho nút x một thông điệp vset_setup nếu nút x là nút láng giềng ảo của nút y vào tập láng giềng ảo vset của nút y. Ngược lại, nút y trả lời nút x bằng một thông điệp vset_setup_fail. Cả hai thông điệp vset_setup và vset_setup_fail đều chứa tập láng giềng ảo vset của nút y và được định tuyến theo hướng proxy trong thông điệp vset_setup_req. Đặc biệt, thông điệp vset_setup thiết lập một vset-path giữa nút x và nút y. Thông tin về vset-path này được thêm vào bảng định tuyến của các nút mà thông điệp đi ngang qua. Khi nút x nhận được thông điệp phản hồi từ nút y, nút x tiếp tục tìm các nút láng giềng ảo khác bằng cách gởi thông điệp vset_setup_req đến các nút trong tập vset của nút y được đính kèm trong thông điệp phản hồi. Đồng thời, nút x thêm nút y vào tập láng giềng ảo vset nếu thông điệp phản hồi là thông điệp vset_setup và nút y là nút láng giềng ảo của nút x. Để xử lý trường hợp các nút tham gia vào mạng đồng thời, ta hủy các vset- path giữa các cặp láng giềng ảo bị lỗi. Ta sẽ hủy thông tin về vset-path bị lỗi ở tất cả các nút mạng có liên quan bằng cách gởi thông điệp teardown cho vset-path đó. Khi một nút x nhận được thông điệp teardown, nút x xóa thông tin định tuyến liên quan đến vset-path trong thông điệp teardown và tiếp tục chuyển thông điệp teardown đến nút kế tiếp còn lại. Trong trường hợp, nút x là một trong hai điểm mút của vset- path (x bằng Ea hay Eb), nút x xóa điểm đầu cuối còn lại ra khỏi tập láng giềng ảo vset nếu đây là một vset-path giữa hai nút láng giềng ảo; ngược lại, nếu đây là vset- path giữa nút đại diện và nút gateway, nút x cập nhật thông tin trong bảng chuyển tiếp. Đồng thời, nút x gởi thông điệp tương ứng để tìm lại nút láng giềng ảo hoặc nút đại diện nếu cần. -34- Khi nút x liên lạc trực tiếp được với hai hay nhiều phân hoạch, nút x trở thành gateway. Khi đó, mỗi khi nút x liên lạc được với một phân hoạch mới, ngoài việc thiết lập tập láng giềng ảo vset và thông tin vset-path liên quan, nút x còn thiết lập vset-path đến các nút mạng đại diện trong mỗi phân hoạch. Để thiết lập vset-path giữa nút gateway và nút đại diện trong một phân hoạch, nút gateway gởi một thông điệp rep_setup_req đến ZERO NODE2 của phân hoạch đó thông qua một proxy. Nút x gởi kèm danh sách các phân hoạch mà nút x có thể liên lạc trong thông điệp rep_setup_req. Thông điệp rep_setup_req được định tuyến cục bộ trong phân hoạch đến nút mạng đại diện r. Khi nút đại diện r nhận được thông điệp rep_setup_req, nút đại diện r cập nhật thông tin bảng chuyển tiếp đồng thời gởi về cho nút x một thông điệp rep_setup theo hướng proxy trong thông điệp rep_setup_req. Cũng như thông điệp rep_setup_req, thông tin các phân hoạch mà nút mạng đại diện có thể liên lạc cũng được gởi kèm trong thông điệp rep_setup. Nút x cập nhật thông tin bảng chuyển tiếp khi nhận được thông điệp rep_setup từ nút mạng đại diện r. Một vset-path cũng được thiết lập dọc theo con đường mà thông điệp rep_setup đi ngang qua. Để đảm bảo tính nhất quán, khi xảy ra thay đổi trong bảng chuyển tiếp tại một nút chuyển tiếp (gateway hay nút đại diện), nút chuyển tiếp gởi thông điệp cập nhật cho các nút chuyển tiếp khác. Khi một nút chuyển tiếp f nhận được thông điệp cập nhật, nút chuyển tiếp f cập nhật thông tin bảng chuyển tiếp của mình. Để tránh trường hợp lặp thông điệp, nút chuyển tiếp f không gởi thông tin cập nhật ngược lại nút nguồn cũng như không xử lý lại thông điệp cập nhật cũ (dựa vào trường sequence number trong thông điệp cập nhật). Trong trường hợp nút mạng không thể tham gia vào bất kỳ một phân hoạch nào, thì nút mạng hoạt động tự do không thuộc vào bất kỳ vòng ảo nào. Thuật toán xử lý các thông điệp đề cập trong mục này được minh họa cụ thể bằng mã giả trong mục PL1.2, phụ lục 1. 2 ZERO NODE trong một phân hoạch là nút mạng có định danh của host bằng 0. -35- 1.5. Quản lý liên kết (link) giữa các nút mạng Nhằm đảm bảo thông tin định tuyến tại mỗi nút mạng một cách chính xác và nhất quán, giao thức BVRR quản lý trạng thái các nút mạng cũng như các liên kết giữa chúng. Đồng thời, giao thức BVRR thực hiện quá trình sửa lỗi khi một nút phát hiện liên kết giữa nó và một nút khác bị lỗi. 1.5.1. Quản lý liên kết Giao thức BVRR sử dụng một cơ chế phát hiện lỗi đồng bộ (symmetric failure detection) tương tự như giao thức VRR [3] để quản lý chất lượng liên kết giữa các nút mạng. Để đảm bảo tính nhất quán, một khi nút x đánh dấu mất liên lạc với nút láng giềng vật lý y trong phân hoạch p thì nút y cũng đánh dấu trạng thái của nút x trong phân hoạch p tương tự và không dùng nút x để chuyển tiếp các gói tin trong phân hoạch p. Mỗi nút mạng quản lý khả năng liên lạc với các nút láng giềng vật lý của mình bằng cách gởi quảng bá thông điệp hello theo định kỳ Th giây. Nút x đánh dấu trạng thái của nút láng giềng vật lý y trong phân hoạch p bằng một trong ba trạng thái: Linked nếu nút x nhận được thông điệp hello từ nút y và ngược lại; Pending nếu nút x nhận được thông điệp hello từ nút y nhưng không biết nút y có nhận được thông điệp hello từ nút x hay không; ngược lại thì nút mạng nhận trạng thái Unknown. Thông điệp hello chứa trạng thái của những nút láng giềng vật lý tại nút y trong mỗi phân hoạch. Khi nút x nhận được thông điệp hello từ nút y, nút x so sánh trạng thái của nó tại nút y và cập nhật trạng thái của nút y trong các phân hoạch theo sơ đồ như mô tả trong hình 3.4. Nếu nút y không tồn tại trong bất kỳ tập láng giềng vật lý của phân hoạch nào, nút x thêm nút y vào tập láng giềng vật lý của phân hoạch mà cả hai cùng active. Nếu không tìm thấy một phân hoạch nào như thế, nút -36- x tạo liên kết mới với nút y trong tất cả các phân hoạch mà nút x và nút y cùng có thể liên lạc3. Trong trường hợp không tìm được phân hoạch mà cả hai cùng active hoặc có thể liên lạc, nút x tạo liên kết với nút y trong phân hoạch hiện hành của mình và phân hoạch hiện hành của nút y4. Khi nút x mới thêm nút y vào tập láng giềng vật lý pset của phân hoạch p thì trạng thái của nút y được khởi tạo là Pending. Pending/Linked Hình 1.4. BVRR: Sơ đồ chuyển trạng thái của một nút mạng Hình 3.4 minh họa quá trình nút x cập nhật trạng thái của nút y tại nút x trong phân hoạch p. Trong đó, cạnh của sơ đồ biểu diễn trạng thái của nút x trong phân hoạch p tại nút y từ thông điệp hello của nút y. Trạng thái hiện hành của nút y trong phân hoạch p tại nút x thể hiện bằng hình oval. Trong trường hợp nút y không biết thông tin về trạng thái của nút x trong phân hoạch p thì trạng thái của nút x trong phân hoạch p tại nút y là Unknown. Nút x xóa nút y ra khỏi tập láng giềng vật lý pset trong tất cả các phân hoạch nếu nút x không nhận được thông điệp hello từ nút y trong kTh giây. Đồng thời, nút x cũng hủy các vset-path có nút y là nút kế tiếp bằng cách gởi thông điệp teardown cho các vset-path tương ứng. Đồng thời, thông điệp hello còn cho biết nút y đã active trong phân hoạch p hay chưa. Nút x xem nút y như một nút láng giềng vật lý tốt (good physical neighbor) trong phân hoạch p nếu nút y có trạng thái là linked và đã active trong phân hoạch p. Khi đó, nút x chèn thêm một vset-path đến nút y vào bảng định Pending Linked Unknown Unknown Unknown Thêm mới y vào tập pset P 3 PNút x có thể liên lạc với phân hoạch p nếu nút x đã active trong phân hoạch p hoặc nút x có ít nhất 1 một liên kết vật lý trong phân hoạch đó. P 4 P Chỉ thêm tạo liên kết khi phân hoạch p khác phân hoạch NULL -37- tuyến của nút x. Và nút x dùng nút y để chuyển tiếp gói tin trong phân hoạch p. Để tối ưu độ dài đường đi chuyển tiếp gói tin, ta thêm các vset-path qua 2 hop vset- path-2-hop thông qua các nút láng giềng vật lý dựa trên thông tin các nút láng giềng của một nút trong thông điệp hello. 1.5.2. Sửa lỗi Khi nút x đánh dấu liên kết với nút y bị hư trong phân hoạch p, nút x xóa tất cả các vset-path thuộc phân hoạch p trong bảng định tuyến có nút y như nút mạng trung gian. Và nút x xóa nút y ra khỏi tập các nút láng giềng vật lý của nó trong phân hoạch p. Để đảm bảo thông tin định tuyến nhất quán trong toàn mạng, nút x khởi tạo thông điệp teardown để xóa thông tin định tuyến về vset-path bị hư dọc theo đường đi của vset-path, chi tiết xem hàm Teardown trong mục PL1.2 trong phụ lục 1. Để hạn chế thông điệp điều khiển cho quá trình sửa lỗi khi phát hiện liên kết hư, mỗi nút mạng dùng cơ chế sửa lỗi