Ý tưởng mới cho mạng không dây kết nối tự do

WMN là mạng không dây ad-hoc kết nối với nhau bằng sóng vô tuyến mà không sử dụng điều khiển tập trung. WMN có khả năng thiết lập nhanh, phủ sóng trong những khu vực khó thực hiện việc đi dây, có khả năng mở rộng và tự cấu hình để đảm bảo hiệu suất. Ngoài ra WMN còn có khả năng tăng tầm phủ sóng nhờ dùng nhiều nút để chuyển tiếp dữ liệu, giảm năng lượng sử dụng nhờ truyền với năng lượng thấp và tăng tải nhờ dùng đường đi ngắn. Mỗi một nút trong mạng WMN sẽ thực hiện chuyển tiếp dữ liệu cho các nút khác. Việc xác định nút nào sẽ chuyển tiếp dữ liệu được xác định động dựa vào cấu trúc mạng lúc đó. Mỗi nút trong mạng WMN cũng đóng vai trò của một router và việc định tuyến cho nó đóng một vai trò rất quan trọng.

Hiện vẫn chưa có một chuẩn thống nhất về giao tiếp cho WMN. Dự án thiết kế một chuẩn giao tiếp cho WMN của nhóm phát triển thuộc IEEE vẫn chưa được thông qua và hiện còn ở mức draft. Draft giao tiếp này có tên là 802.11s và đã được sử dụng trong một số dự án như OPLC và open802.11s mặc dù vẫn chưa chính thức được IEEE công nhận là chuẩn.

Việc định tuyến cho mạng WMN hầu hết được thực hiện ở lớp network của mô hình OSI. Thực hiện định tuyến ở lớp network có một số điểm hạn chế. Tuy nhiên khi thực hiện định tuyến ở lớp data link thì tránh được các vấn đề này. Hiện thực định tuyến ở lớp data link giúp cho nó trong suốt với các lớp bên trên nên có thể sử dụng lại các lớp bên trên mà không cần thay đổi gì (ping, tcp, udp, kết nối với các mạng khác,…). Hơn nữa khi thực hiện định tuyến ở lớp data link, ta dễ dàng can thiệp vào các thông số của WMN như beacon, channel, bit error rate,… Các thông số này rất quan trọng trong việc điều khiển WMN. Thực hiện định tuyến ở lớp data link không cần phải thông qua mô hình thác nước, giúp giảm tổng thời gian và chi phí gửi thông điệp định tuyến. Đây còn gọi là kỹ thuật thiết kế cross-design và là một hướng nghiên cứu thời gian gần đây.

Tuy có nhiều ưu điểm nhưng hiện có rất ít giao thức định tuyến được thực hiện ở lớp data link vì định tuyến ở lớp data link phải thực hiện trên nền địa chỉ MAC. Địa chỉ MAC không phân cấp như địa chỉ IP nên định tuyến cho nó phức tạp hơn. Không phải giao thức định tuyến ở lớp network nào cũng có thể áp dụng ở lớp data link. Chỉ có những giải thuật định tuyến có khả năng đáp ứng khi mạng mở rộng mà không cần thực hiện phân cấp mới có thể áp dụng hữu hiệu ở lớp data link. Một vấn đề khó khăn nữa là bảo mật ở lớp data link phức tạp và khó hiện thực hơn ở lớp network.

Bài báo này trình bày một giao thức định tuyến proactive mới ở lớp hai dành cho WMN dựa trên ý tưởng của giải thuật định tuyến XL , cũng như kết quả mô phỏng thu được. Giao thức định tuyến này, gọi là DLL-XL, giúp định tuyến hiệu quả nhờ áp dụng các kỹ thuật truyền cập nhật có lựa chọn đến các nút khác.

Ý TƯỞNG CỦA GIẢI THẬT ĐỊNH TUYẾN XL

Kỹ thuật flooding: Flooding là quá trình chuyển tiếp một gói tin cho tất cả các nút kề của nó trừ nút gửi gói tin đến. Kỹ thuật flooding được sử dụng để truyền các thông tin về chi phí kết nối (link cost) từ một nút đến các nút khác trong mạng để nút tính toán định tuyến. Flooding cơ bản có rất nhiều hạn chế. Gói tin sẽ được flooding đến tất cả các nút khác trong mạng nhưng không phải nút nào cũng cần nhận gói tin này. Các gói tin được flooding trong mạng gây ra dư thừa và quá tải mạng. Do vậy các giao thức định tuyến đều phải giới hạn việc flooding. Giao thức định tuyến có hiệu quả và chính xác hay không là do các phương pháp giới hạn flooding tốt và đầy đủ hay không. Một số phương pháp giới hạn flooding trong định tuyến hiện nay gồm có:

−Đánh số thứ tự gói tin để không flooding lại những gói tin cũ. Kỹ thuật này được dùng trong hầu hết các giao thức định tuyến như AODV (RFC 3561 [10]) và OLSR (RFC 3626.

−Giới hạn vùng flooding nhân tạo. Mạng lớn được chia thành những vùng nhỏ; flooding chỉ thực hiện bên trong từng vùng, không flooding ra ngoài vùng. Định tuyến giữa các vùng thực hiện nhờ các nút biên. Do đó đường đi chỉ tối ưu trong từng vùng và cũng khó mở rộng khi phải phân cấp nhân tạo một mạng lớn. Kỹ thuật này được áp dụng trong giao thức định tuyến OSPF (RFC 2328).

−Giới hạn bán kính flooding. Flooding chỉ truyền qua một số nút tối đa được quy định trước. Việc xác định bán kính tối đa này rất khó thực hiện. Bán kính lớn thì sẽ flooding dư thừa mà bán kính nhỏ thì định tuyến không chính xác. Kỹ thuật này được áp dụng trong giao thức định tuyến Fish-eye và OLSR.

−Bầu chọn nút flooding. Chỉ những nút đại diện này mới flooding, các nút còn lại chỉ nhận gói tin mà không flooding. Kỹ thuật này được sử dụng trong giao thức định tuyến OLSR.

Mỗi phương pháp hạn chế flooding đều có những điểm yếu nhất định. Giải thuật định tuyến XL , được trình bày bởi Levchenko et al. tại hội nghị SIGCOMM’08, đề xuất một phương pháp routing mới giới hạn flooding thông tin về chi phí kết nối bằng cách truyền cập nhật theo các luật nhưng vẫn đảm bảo định tuyến đúng và đầy đủ.

Giải thuật định tuyến XL: Giải thuật định tuyến XL của Levchenko et al. phân biệt với các giải thuật định tuyến khác ở chỗ chỉ flooding các cập nhật về chi phí kết nối:

−Khi cập nhật có chi phí kết nối tăng lên (S1).

− Khi kết nối đó nằm trên cây đường đi ngắn nhất thì phải truyền chi phí kết nối đó cho nút kề trong cây đường đi ngắn nhất (S2).

− Khi cập nhật làm cho chi phí đến một đích bất kỳ ít hơn (1+ ε) lần chi phí đường đi tốt nhất hiện tại, ε ≥ 0 là thông số thiết kế của giải thuật (C1).

Ba luật trên là đủ để đảm bảo định tuyến không bị lặp vòng, các đích đều có thể đến được, và đường đi tìm được đảm bảo tính bao đóng về chi phí, nghĩa là chi phí đường đi tìm được không vượt quá (1 + ε) lần chi phí đường đi tốt nhất.

Giao thức định tuyến DLL-XL do nhóm nghiên cứu đề xuất và thiết kế là giao thức định tuyến proactive được thiết kế ở lớp data link của mô hình OSI dành cho WMN. Giao thức giúp hạn chế flooding bằng cách truyền cập nhật có lựa chọn theo các luật truyền. Giao thức thích hợp nhất cho WMN có mật độ nút dày và có nhiều biến động. Họ cho rằng các luật truyền của giao thức có thể được giới hạn thêm nữa để tăng tính hiệu quả của việc định tuyến. Tuy vậy đây là một vấn đề khó khăn và cần phải nghiên cứu sâu hơn nữa.

Thiên Thành