Đề tài Ad-Hoc network

ĐẠI HỌC QUỐC GIA TP.HCM TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN ***** KHOA ĐIỆN TỬ VIỄN THÔNG BỘ MÔN VIỄN THÔNG VÀ MẠNG ***************** Bài báo cáo môn Truyền thông di động Đề tài : AD-HOC NETWORK Giảng viên hướng dẫn: ThS.Trương Tấn Quang Sinh viên thực hiện: Nguyễn Quang Hùng 0520030 Trương Thế Toàn 0520082 Đặng Vũ Thiên 0520071 Nội dung báo cáo I.Các thuật ngữ viết tắt II.Tổng quan về Mobile – Adhoc – Network (MANET): 2.1.MANET là gì 2.2.Các giao thức định tuyến trong MANET 2.3.Giới thiệu chung về mạng mắt lưới không dây WMN (Wireless Mesh Network ) 2.4.Định tuyến trong mạng WMN 2.5.Tiêu chuẩn IEEE 802.11s 2.6.Định tuyến trong mạng hình lưới 802.11s III.Giao thức định tuyến vectơ cự ly theo yêu cầu tùy biến AODV: 3.1.Tổng quan về AODV 3.2.Định dạng các gói tin 3.3.Hoạt động của AODV IV.Giao thức định tuyến nguồn động DSR: 4.1.Tổng quan về DSR 4.2.Vấn đề cơ bản của cơ chế xác định tuyến và duy trì tuyến 4.3.Định dạng mào đầu các lựa chọn DSR 4.4.Hoạt động của DSR 4.5.Vị trí của chức năng định tuyến DSR trong mô hình tham khảo ISO V.Tài liệu tham khảo I.Các thuật ngữ viết tắt ACK Acknowledgment Báo nhận AODV Ad-hoc on-demand distance vector routing Định tuyến cự ly véc tơ theo yêu cầu tùy biến DSR Dynamic Source Routing Định tuyến nguồn động ETT Expected Transmission Time Thời gian truyền dẫn mong đợi ETX Expected Transmission Count Dự báo số truyền dẫn mong đợi FIFO First In First Out Vào trước ra trước ML Minimum Loss tổn thất tối thiểu ICMP Internet Control Message Protocol Giao thức điều khiển truyền tin trên mạng LLACKS link-layer acknowledgments Báo nhận lớp liên kết MAC Medium Access Control Điều khiển truy nhập môi trường MANET Mobile Ad-hoc Network Mạng tùy biến di động MIC Metric of Interference and Channel-switching Tham số nhiễu và chuyển mạch kênh RD Route Discovery Khám phá tuyến RERR Route Error Lỗi tuyến RM Route Maintenance Duy trì tuyến RREP Route Reply Hồi đáp tuyến RREP- ACK Route Reply Acknowledgment Báo nhận hồi đáp tuyến RREQ Route Request Yêu cầu tuyến RREQ ID Route Request Identification Nhận dạng yêu cầu tuyến TTL Time to live Thời gian sống WCETT Weighted Cumulative ETT Thời gian truyền dẫn mong đợi tích lũy tải WLAN Wireless Local Area Network Mạng cục bộ không dây WMAN Wireless Metropolitan Area Network Mạng không dây đô thị WMN Wireless Mesh Network Mạng mắt lưới không dây WPAN Wireless Personnal Area Network Mạng không dây cá nhân WWAN Wireless Wide Area Network Mạng không dây diện rộng II.Tổng quan về Mobile – Adhoc – Network (MANET) 2.1.MANET là gì ? - MANET là viết tắt của mạng tùy biến di động (Mobile – Adhoc – Network ) , hay còn gọi là mô hình mạng độc lập IBSSs (Independent Basic Service sets) - Các thiết bị di động như các máy tính xách tay, với đặc trưng là công suất CPU, bộ nhớ lớn, dung lượng đĩa hàng trăm gigabyte, khả năng âm thanh đa phương tiện và màn hình màu đã trở nên phổ biến trong đời sống hàng ngày và trong công việc. Đồng thời, các yêu cầu kết nối mạng để sử dụng các thiết bị di động gia tăng đáng kể, bao gồm việc hỗ trợ các sản phẩm mạng vô tuyến dựa trên vô tuyến hoặc hồng ngoại ngày càng nhiều. Với kiểu thiết bị điện toán di động này, thì giữa những người sử dụng di động luôn mong muốn có sự chia sẻ thông tin. - Một mạng tùy biến là một tập hợp các thiết bị di động hình thành nên một mạng tạm thời mà không cần sự trợ giúp của bất kỳ sự quản lý tập trung hoặc các dịch vụ hỗ trợ chuẩn nào thường có trên mạng diện rộng mà ở đó các thiết bị di động có thể kết nối được. Các node được tự do di chuyển và thiết lập nó tùy ý, do đó, topo mạng không dây có thể thay đổi một cách nhanh chóng và không thể dự báo. Nó có thể hoạt động một mình hoặc có thể được kết nối tới Internet. MANET là một mạng có cơ sở hạ tầng nhỏ do nó không yêu cầu bất cứ một cơ sở hạ tầng cố định nào (như một trạm cơ sở) cho hoạt động của nó vì và vậy nó có thể được triển khai nhanh chóng và có khả năng tự cấu hình. Các node truyền thông không dây và chia sẻ cùng phương tiện. - Do MANET là một mạng mềm dẻo mà có thể được thiết lập tại bất cứ đâu vào bất cứ thời điểm nào mà không cần đến cơ sở hạ tầng hiện tại, bao gồm cả sự cấu hình trước đó và người quản trị, mọi người có thể nhận ra tiềm năng thương mại và lợi thế của mạng ad hoc có thể mang lại. MANET có thể được dùng trong quân sự, trong các mạng cảm biến, các hoạt động cứu hộ, sử dụng để truyền thông giữa các sinh viên trong khu trường sở, trao đổi thông tin và dữ liệu trong các khu thương mại, tự do chia sẻ kết nối Internet, dùng trong các buổi hội thảo… MANET có hai chế độ hoạt động chính là chế độ cở sở hạ tầng (Infrastructure-based Network) và chế độ IEEE Ad- hoc Hình 1.1: Chế độ cơ sở hạ tầng trong MANET Chế độ cơ sở hạ tầng: Chế độ này thì mạng bao gồm các điểm truy cập AP cố định và các node di động tham gia vào mạng, thực hiện truyền thông qua các điểm truy cập. Trong chế độ này thì các liên kết có thể thực hiện qua nhiều chặng. Hình 1.2: Chế độ IEEE Ad- hoc trong MANET Chế độ IEEE Ad- hoc: Chế độ này thì các node di động truyền thông trực tiếp với nhau mà không cần tới một cơ sở hạ tầng nào cả. Trong chế độ này thì các liên kết không thể thực hiện qua nhiều chặng 2.2.Các giao thức định tuyến trong MANET 2.2.1 Các giải pháp định tuyến thông thường - Một phương pháp đơn giản để thực hiện việc định tuyến trong mạng tùy biến là xem mỗi thiết bị di động như một bộ định tuyến và vận hành một giao thức định tuyến thông thường giữa chúng. Các giao thức định tuyến thông thường dựa trên các thuật toán vectơ khoảng cách (distance vector) hoặc thuật toán trạng thái liên kết (link state). - Trong định tuyến vectơ khoảng cách, mỗi bộ định tuyến duy trì một bảng các khoảng cách từ nó đến tất cả các đích có thể. Mỗi bộ định tuyến định kỳ quảng bá những thông tin này tới từng bộ định tuyến lân cận của nó và sử dụng các giá trị nhận được từ các bộ định tuyến lân cận của nó để tính toán các giá trị được cập nhật cho bảng của nó. Bằng cách so sánh khoảng cách nhận được cho từng đích từ mỗi bộ định tuyến lân cận của nó, bộ định tuyến có thể xác định bước nhẩy tiếp theo chính xác trên đường ngắn nhất tới từng đích. Khi đưa ra một gói để chuyển tiếp tới đích nào đó, mỗi bộ định tuyến đơn giản là chuyển tiếp gói tới đúng bộ định tuyến bước nhẩy tiếp theo. Bằng cách truyền các thông số bảng định tuyến cập nhật thường xuyên như vậy thậm chí bất kỳ thông tin nào về những thay đổi bảng, thuật toán hướng nhanh chóng tới đúng đường kết nối (ví dụ khi một kết nối lên hoặc xuống) nhưng phần phụ trội trong thời gian CPU và băng thông mạng để truyền các cập nhật bảng định tuyến đang tăng lên. - Trong định tuyến trạng thái liên kết, mỗi bộ định tuyến duy trì trọn vẹn một kiểu tôpô về toàn bộ mạng. Mỗi bộ định tuyến giám sát chi phí của tuyến liên kết tới từng bộ định tuyến lân cận của nó và định kỳ các thông báo các cập nhật thông tin này tới toàn bộ các bộ định tuyến trong mạng. Với những thông tin chi phí mỗi liên kết trong mạng, mỗi bộ định tuyến sẽ tính toán đường ngắn nhất tới từng đích có thể. Khi đưa ra một gói để chuyển tiếp tới đích nào đó, mỗi bộ định tuyến chuyển tiếp gói tới bộ định tuyến bước nhẩy tiếp theo dựa trên đường tối ưu nhất hiện nay tới đích. Các giao thức định tuyến trạng thái liên kết hướng tới đích nhanh hơn khi các điều kiện trong mạng thay đổi, nhưng nói chung đòi hỏi thời gian CPU nhiều hơn (để tính toán đường ngắn nhất tới đích) và nhiều băng thông mạng hơn các thuật toán vectơ khoảng cách. - Khi sử dụng các giao thức định tuyến thông thường trong một mạng tùy biến, mỗi thiết bị di động được coi là một bộ định tuyến, có một số vấn đề với phương pháp này: + Truyền dẫn giữa 2 thiết bị di động qua một mạng vô tuyến không nhất thiết phải tốt như nhau trên cả 2 hướng. Do đó một số tuyến được các giao thức định tuyến truyền thống xác định có thể không hoạt động trong các môi trường như vậy. + Nhiều liên kết giữa các bộ định tuyến có được bởi thuật toán đinh tuyến có thể dư thừa. Các mạng có dây thì ngược lại, thường được cấu hình chỉ có 1 hoặc một số ít các bộ định tuyến để kết nối 2 mạng bất kỳ. Các đường dư thừa không cần thiết trong môi trường vô tuyến làm tăng kích cỡ các cập nhật định tuyến mà phải gửi qua mạng, và tăng phần phụ trội CPU để xử lý cập nhật và tính toán tuyến mới. + Việc định kỳ gửi các cập nhật định tuyến tiêu tốn băng thông mạng. Đôi khi, không có thay đổi trong cập nhật định tuyến, nhưng mỗi bộ định tuyến (thiết bị di động) vẫn phải tiếp tục gửi các cập nhật định kỳ để các bộ định tuyến khác sẽ tiếp tục coi các tuyến qua bộ định tuyến đó là có hiệu lực. Các cập nhật định tuyến từ các thiết bị ở ngoài phạm vi truyền dẫn của nhau sẽ không gây nhiễu cho nhau, nhưng khi nhiều thiết bị di động là trong phạm vi truyền dẫn của nhau, các cập nhật định tuyến của chúng sẽ tiêu tốn băng thông mạng của nhau. + Các cập nhật định tuyến được gửi định kỳ tiêu tốn nguồn năng lượng. Hầu hết các thiết bị di động trong mạng tùy biến sẽ hoạt động trên nguồn năng lượng riêng ví dụ như pin, và việc truyền gói sẽ làm cạn kiện đáng kể nguồn năng lượng đó. Mặc dù việc nhận gói nói chung yêu cầu ít công suất nguồn hơn việc gửi chúng, nhưng cần phải nhận các cập nhật định tuyến định kỳ ngăn cản thiết bị tiết kiệm nguồn bằng cách thiết lập thiết bị trong chế độ chờ. + Cuối cùng, các giao thức định tuyến thông thường không được thiết kế cho kiểu thay đổi tôpô động mà điều này xảy ra trong mạng tùy biến. Ở các mạng thông thường, các kết nối giữa các bộ định tuyến thường đi xuống và đi lên và đoi khi chi phí cho một tuyến kết nối có thể thay đổi do nghẽn nhưng các bộ định tuyến nhìn chung không chuyển động theo nhiều hướng mà chỉ dịch chuyển các phần chính của tôpô mạng tiến hoặc lùi. Các thiết bị di động mặc dù có thể được phân biệt bởi sự thay đổi động vì nói cho cùng thì chúng là các thiết bị di động. Việc hội tụ tiến tới các tuyến mới và ổn định sau các thay đổi động trong tôpô có thể khá chậm, đặc biệt với các thuật toán vectơ khoảng cách. Tốc độ hội tụ có thể được nâng cao bằng cách gửi cập nhật định tuyến thường xuyên hơn, nhưng cách như vậy tiêu tốn nhiều băng thông và công suất ắcquy khi những thay đổi tôpô là không đáng kể. 2.2.2 Phân loại giao thức định tuyến trong MANET Có nhiều tiêu chí khác nhau để phân loại các giao thứ định tuyến nhưng nhìn chung, có thể phân loại các giao thức định tuyến như sau: Hình 1.3: Phân loại giao thức định tuyến 2.2.2.1 Định tuyến dựa vào topo mạng Các giao thức định tuyến dựa vào topo mạng lựa chọn đường đi cho gói tin theo các thông tin về cấu hình của mạng, ví dụ như liên kết giữa các nút mạng. Trong bất kỳ mạng nào, nhiệm vụ của định tuyến là phát hiện đường đi (route discovery) và duy trì đường đi (route maintenance). Tùy thuộc vào việc phát hiện đường và duy trì đường có thể được chia giao thức định tuyến thành các loại sau: reactive, proactive và hybrid. Các giao thức định tuyến reactive là các giao thức được xây dựng dựa vào việc tách riêng phát hiện đường (route discovery), duy trì đường (route maintenance) và không cần cập nhật các đường theo chu kỳ. Các giao thức loại này sẽ yêu cầu thủ tục quyết định đường khi cần thiết. Khi một nút nguồn cần một đường đến đích, nó sẽ thực hiện quá trình tìm đường trong mạng. Nút nguồn phát quảng bá gói tin yêu cầu tìm đường đi đến các nút lân cận, các nút lân cận này lại gửi gói tin đến các nút hàng xóm của nó, và gửi như vậy cho đến khi tới đích. Đích sẽ gửi gói tin phúc đáp cho nút nguồn thông qua các nút trung gian. Khi đường đi được thiết lập, nó được duy trì nhờ một thủ tục giữ đường cho đến khi đích không chấp nhận gói do nguồn gửi đến hoặc không cần sử dụng đường đó nữa. Với phương pháp reactive, việc tính toán tìm đường chỉ thực hiện khi cần thiết nên độ phức tạp tính toán giảm so với phương pháp proactive nhưng lại bị trễ nhiều hơn do thủ tục thiết lập đường. Các giao thức định tuyến proactive là các giao thức kết hợp việc phát hiện đường đi và duy trì đường đi bằng cách gửi các gói cập nhật định tuyến. Nếu trạng thái của một liên kết hoặc một router có sự thay đổi thì các gói tin cập nhật này sẽ thông báo cho tất cả các router còn lại biết để tính toán lại đường đi. Do đó, mỗi nút đều biết đường đi đến các nút còn lại. Như vậy sẽ không có trễ nhưng duy trì thường xuyên các đường đi không sử dụng làm cho việc quản lý các đường phức tạp hơn. Các giao thức định tuyến hybrid được tạo ra để cố gắng kết hợp các ưu điểm của 2 loại giao thức trên: sử dụng phương pháp định tuyến proactive với các nút gần hoặc cần dùng thường xuyên; sử dụng giao thức reactive với các nút ở xa hoặc ít khi cần truyền thông tin đến. 2.2.2.2 Định tuyến dựa vào vị trí: Đối với thuật toán định tuyến này, các gói được chuyển đi dựa vào vị trí địa lý của các nút chuyển tiếp, các nút hàng xóm của chúng và đích đến. Phương pháp này yêu cầu mỗi nút phải biết vị trí địa lý của mình. Vị trí nút đích do dịch vụ định vị (location service) cung cấp. Một số giao thức thuộc loại này là: Greedy forwarding (gửi gói tin đến nút gần đích nhất), face routing, GPSR,… 2.3.Giới thiệu chung về mạng mắt lưới không dây WMN (Wireless Mesh Network) Khái niệm mạng hình lưới (Mesh Network) nói chung được sử dụng trong một số lĩnh vực của ngành công nghệ thông tin. Kỹ thuật mạng hình lưới là cách thức truyền tải dữ liệu, âm thanh và câu lệnh giữa các nút xử lý, cho phép truyền thông liên tục và tự xác định lại cấu hình xung quanh đường đi bị che chắn bằng cách “nhảy” từ nút này sang nút khác cho đến khi thiết lập được kết nối. Mạng lưới có khả năng tự hàn gắn và tạo ra mạng có độ tin cậy cao; có thể hoạt động khi có một nút bị lỗi hoặc chất lượng kết nối mạng kém. Trong lĩnh vực mạng không dây, mạng lưới được áp dụng để nới rộng phạm vi phủ sóng của mạng không dây truyền thống. Các nút trong mạng truyền thông trực tiếp với các nút khác và tham gia trong mạng lưới. Nếu một nút có thể kết nối với một nút lận cận khác thì sẽ có kết nối với toàn mạng. Mạng WMN chuyển tiếp dữ liệu gói thông qua các chặng vô tuyến. Mỗi một nút lưới hoạt động giống như một điểm chuyển tiếp hay một router với các nút lưới khác trong mạng. Mạng WMN được dùng trong những mô hình như mạng truy nhập công cộng và những mạng không dây trong thành phố nơi mà các điểm truy cập là các nút lưới của mạng. Hình1.4: Các thành phần cơ bản của mạng WMN Sự tin cậy và hiệu năng của mạng là 2 tiêu chí chính của mạng WMN, đặc biệt trong môi trường kênh vô tuyến. Tính di động của nút mạng thường không được xem xét đến. Những nút cố định có thể nằm trên những đế đèn, hay gắn liền đối với nhà cửa, v.v… , nơi được cung cấp năng lượng đầy đủ. Như vậy, các giao thức định tuyến có thể được tối ưu theo sự tin cậy và hiệu năng của mạng. Các giao thức định tuyến có thể được mở rộng để sử dụng những tham số định tuyến đặc biệt. Và thậm chí chúng có thể nằm trên lớp 2 để có thể truy cập tốt hơn thông tin lớp MAC và lớp vật lý. Các nút mắt lưới có thể có nhiều giao diện vô tuyến để gia tăng khả năng của mạng mắt lưới không dây. Các giao diện vô tuyến giảm thiểu sự suy giảm thông lượng bởi các gói nhận và chuyển tiếp tuần tự trong các nút mắt lưới với chỉ một giao diện vô tuyến. Điều này cũng có thể sử dụng nhiều kênh. Dung lượng tuỳ biến của mạng WMN là giới hạn nhưng sự cài đặt đơn giản và tính mềm dẻo vẫn là những ưu điểm của mạng. Gần đây các thiết bị khách hàng ngày càng đóng vai trò như là một nút mắt lưới. Điều này mở rộng mạng WMN về vùng mạng tuỳ biến không dây cổ điển. Điều này không thành vấn đề, vì MANET và WMN có chung một khái niệm. Chúng chỉ sử dụng các giá trị khác nhau trong các tham số mạng: các nút với tính di động từ “tĩnh” sang “chuyển động với tốc độ v” sử dụng truyền thông vô tuyến qua một hay nhiều giao diện trên các chặng vô tuyến, nơi mà các tuyến được xác định rõ với các giao thức định tuyến tự tổ chức làm việc với các tham số định tuyến khác nhau. Có 3 kiểu mạng WMN, đó là : WMN hạ tầng, WMN khách hàng, và WMN lai ghép. WMN hạ tầng bao gồm các thiết bị chuyên dụng của hạ tầng mạng, như là các điểm truy nhập hay chuyển tiếp. Các thiết bị khách hàng không tham gia vào việc định tuyến ở nút lưới. Thay vào đó , chúng kết nối vào các điểm truy nhập bằng công nghệ truy nhập vô tuyến truyền thống. WMN khách hàng bao gồm các thiết bị khách hàng như máy tính xách tay. Các thiết bị khách hàng tham gia vào việc định tuyến ở nút lưới. Hơn nữa chúng có thể thực hiện chức năng như một thiết bị hạ tầng. WMN lai ghép bao gồm cả hai loại thiết bị trên. 2.4.Định tuyến trong mạng WMN Vì WMN có chung đặc điểm với những mạng tuỳ biến không dây, những giao thức định tuyến được phát triển cho MANET có thể được ứng dụng vào WMN. Chẳng hạn, những mạng mắt lưới được Microsoft xây dựng dựa vào định tuyến nguồn động (DSR), và nhiều công ty khác, sử dụng định tuyến vector cự ly theo yêu cầu tuỳ biến (AODV). Những khái niệm lõi của những giao thức định tuyến hiện hữu được mở rộng để đạt được những yêu cầu đặc biệt của mạng mắt lưới không dây. Dù đã có nhiều giao thức định tuyến cho mạng tuỳ biến không dây, những giao thức định tuyến cho WMN vẫn được tích cực nghiên cứu vì vài lý do sau: Trong đa số WMN, nhiều nút ở một chỗ hay ít di chuyển và không phụ thuộc vào nguồn pin. Do đó, những thuật toán định tuyến không cần chú ý vào việc đối phó với sự di động hay tối thiểu dùng nguồn nuôi. Khoảng cách giữa những nút có lẽ đã được ngắn lại ở một WMN, do vậy gia tăng chất lượng liên kết và tốc độ truyền. Tuy nhiên, những khoảng cách ngắn cũng tăng ảnh hưởng giữa các chặng, giảm bớt dải thông sẵn có trên mỗi mối liên kết. Bởi vậy, những tham số định tuyến mới cần được tìm hiểu và dùng để cải thiện hiệu năng của những giao thức định tuyến ở một mạng WMN với nhiều chặng và nhiều đường truyền vô tuyến. Đối với mạng WMN có nhiều kênh và nhiều đường truyền vô tuyến, giao thức định tuyến không những cần thiết để lựa chọn đường đi trong những nút khác nhau, mà còn cần thiết để lựa chọn kênh thích hợp nhất hay đường truyền vô tuyến cho mỗi nút lưới. Bởi vậy, những tham số định tuyến cần được tìm hiểu và được dùng để tận dụng nhiều kênh, nhiều đường vô tuyến trong một mạng mắt lưới không dây. Trong một mạng WMN, sự thiết kế xuyên lớp là cần thiết vì sự thay đổi của một đường định tuyến sẽ liên quan đến chuyển mạch kênh vô tuyến trong nút lưới nhiều kênh và nhiều đường truyền vô tuyến. Dựa trên hiệu năng của các giao thức định tuyến đang dùng cho mạng tuỳ biến và những yêu cầu đặc biệt của mạng WMN, giao thức định tuyến tối ưu cho WMN cần đạt được những yêu cầu sau: + Dung sai lỗi: Một vấn đề quan trọng của các mạng là khả năng sống của mạng. Khả năng sống của mạng là khả năng hoạt động của mạng thậm chí khi có nút hoặc liên kết bị lỗi. WMN có thể bảo đảm chắc chắn chống lại lỗi liên kết bởi tự nhiên gây ra. Tương ứng là giao thức định tuyến cũng nên hỗ trợ chọn đường lại tuỳ vào các liên kết lỗi. + Cân bằng tải: Các bộ định tuyến vô tuyến cho mạng mắt lưới tốt cho cân bằng tải bởi vì chúng có thể lựa chọn đường đi hiệu quả nhất cho dữ liệu. + Giảm thiểu tiêu đề định tuyến: Sự bảo vệ băng thông là bắt buộc cho sự thành công của bất kì mạng vô tuyến nào. Giảm thiểu tiêu đề định tuyến là điều quan trọng, đặc biệt bởi một nguyên nhân tái quảng bá. + Khả năng mở rộng: Mạng mắt lưới có khả năng mở rộng và có thể kiểm soát hàng trăm hàng nghìn nút. Bởi vì nhà điều hành mạng không phụ thuộc vào một điểm điều khiển trung tâm, cộng thêm các điểm thu thập dữ liệu hoặc gateway là rất tiện lợi. Điều quan trọng cho mạng WMN với hàng nghìn nút là hỗ trợ khả năng mở rộng trong các giao thức định tuyến. + Hỗ trợ QoS: Để giới hạn dung lượng kênh, ảnh hưởng của xuyên nhiễu, số lượng lớn các người dùng và sự nổi trội của các ứng dụng đa phương tiện thời gian thực, việc hỗ trợ chất lượng dịch vụ (QoS) trở nên một yêu cầu quyết định trong các mạng như vậy. 2.5.Tiêu chuẩn IEEE 802.11s 2.5.1 Giới thiệu chung    Các dịch vụ mạng không dây đang bùng nổ và trở thành một phần không thể thiếu trong hệ thống dịch vụ mạng thế hệ kế tiếp NGN (Next generation Network). Chính vì vậy, sự hình thành và phát triển mạnh mẽ của các công nghệ không dây mới trong thời gian gần đây đã và đang thu hút nhiều sự quan tâm nghiên cứu của rất nhiều các tổ chức nghiên cứu cũng như các trung tâm triển khai thử nghiệm. Trong nỗ lực chuẩn hóa các hệ thống và tìm kiếm các giải pháp kết nối và nâng cao hiệu năng mạng, tổ chức IEEE đã hình thành một số nhóm dành riêng để phát triển lĩnh vực WMN (Wireless Mesh Network) như: IEEE 802.11s [Mạng không dây cục bộ WLAN], 802.15.5 [Mạng không dây cá nhân WPAN – Wireless Personal Area Network], IEEE 802.16j [Mạng không dây đô thị WMAN – Wireless Metropolital Network]. WMN có thể được ứng dụng cho nhiều kiểu hạ tầng mạng không dây khác nhau và một trong số đó là mạng không dây cục bộ WLAN (Wireless Local Area Network ).  2.5.2 Tổng quan về IEEE 802.11s Với các đặc tính thế mạnh của các mạng hình lưới không dây WMN như tính tự cấu hình, tự tổ chức nhằm tạo ra các hình thái tùy biến để duy trì kết nối. Các ứng dụng của mạng WMN có thể tạo ra miền ứng dụng rộng rãi như: mạng truy nhập băng rộng, mạng cộng đồng, mạng doanh nghiệp, hỗ trợ các hệ thống an ninh, y tế, v.v. Với các đặc điểm riêng của công nghệ WiFi, mạng hình lưới không dây WLAN gặp nhiều thách thức cần phải vượt qua, một trong các vấn đề đó là vấn đề kết nối, mở rộng mạng để tạo ra miền ứng dụng rộng.  2.5.2.1 Các thành phần mạng kết nối hình lưới WLAN Một mạng kết nối hình lưới WLAN gồm các node có chức năng quản lý, điều khiển các dịch vụ và điều hành mạng hình lưới gọi là các điểm hình lưới MP (Mesh Point). Nếu một node (MP) thêm chức năng truy nhập tới thiết bị đầu cuối STA (Station) hoặc các node không nằm trong mạng hình lưới thì được gọi là điểm truy nhập hình lưới MAP (Mesh Access Point). Hình 1.5: Các thành phần cơ bản của mạng kết nối hình lưới WLAN Thiết bị Cổng mạng hình lưới  MPP (Mesh Point Portal) là MP có thêm chức năng kết nối tới Internet và hoạt động như một gateway. Các chức năng MAP và MPP có thể được cung cấp đồng thời trên cùng một thiết bị. Khung hệ thống phân bổ không dây WDS (Wireless Distribution Systems) sử dụng để truyền dữ liệu giữa các MP, MAP và MPP. 2.5.2.2 Kiến trúc khối chức năng của 802.11s Kiến trúc khối chức năng của 802.11s được chia thành 4 khối chức năng như hình 1.6. Hình 1.6: Kiến trúc các khối chức năng của 802.11s Khối chức năng định tuyến, chuyển tiếp và học cấu hình: Chứa các chức năng phát hiện node lân cận, thu thập các tham số đo trạng thái đường liên kết vô tuyến sử dụng cho định tuyến. Các giao thức định tuyến sử dụng địa chỉ MAC làm địa chỉ nhận dạng cũng như cho chức năng chuyển tiếp gói. Để sử dụng hiệu quả nguồn tài nguyên vô tuyến, giao thức định tuyến sử dụng các tham số vô tuyến và các kênh đa tần phù hợp với các điều kiện vô tuyến để chọn đường.  Khối đo lường và tính toán: Chứa các chức năng tính toán các tham số vô tuyến được sử dụng trong giao thức định tuyến; đo lường các điều kiện vô tuyến để lựa chọn kênh tần số. Khối điều phối truy nhập phương tiện: Bao gồm các chức năng chống suy giảm hiệu năng do các hiện tượng che dấu thông tin node (Hidden, Exposed Node); các chức năng thực hiện điều khiển ưu tiên, điều khiển tắc nghẽn, điều khiển quản lý và chức năng kích hoạt sử dụng lại tần số.  Khối an ninh: Chứa các chức năng an ninh để bảo vệ các khung dữ liệu mang trên WLAN và các khung quản lý được sử dụng bởi các chức năng quản lý như giao thức định tuyến. Các phương pháp an ninh cho WLAN được định nghĩa trong 802.11i.  Khối liên mạng: IEEE 802.11 là một phần trong cấu trúc IEEE 802 vì thế WLAN thực hiện kết nối với các mạng khác (ví dụ: 802.3) thông qua chức năng cầu nối nằm tại MPP.  Khối chức năng quản lý và cấu hình: Khối này gồm một giao diện WLAN sử dụng để tự động thiết lập các tham số tần số vô tuyến MP với mục đích quản lý chính sách chất lượng dịch vụ. 2.6.Định tuyến trong mạng hình lưới IEEE 802.11s Giao thức định tuyến và các tham số đo lượng (Metrics) là các phần tử quan trọng nhất đối với hiệu năng mạng hình lưới WMN. Một số giao thức định tuyến được đề xuất kế thừa từ các giao thức định tuyến trong mạng cảm biến không dây MANET (Mobile Ad-hoc Network) vì một số đặc tính tương đồng.  2.6.1 Phân loại các giao thức định tuyến MANET Mạng MANET chia các giao thức định tuyến thành: định tuyến theo bảng (proactive), định tuyến theo yêu cầu (reactive) và định tuyến lai ghép giữa hai loại trên. Các giao thức định tuyến proactive sử dụng phương pháp tràn lụt (Flooding) để quảng bá thông tin tới các thiết bị. Phương pháp này cho phép thời gian thiết lập đường nhanh dựa trên các tham số gửi tới thiết bị sẵn sàng cho kết nối. Tuy nhiên, việc lưu lượng thông tin tiêu đề tăng lên chính là nhược điểm của phương pháp này. Giao thức định tuyến trạng thái liên kết tối ưu OLSR (Optimized Link State Routing) [RFC 3626] và giao thức định tuyến vector khoảng cách tuần tự đích DSDV (Dynamic Destination-Sequenced Distance-Vector Routing) [IBM,1996] là hai ví dụ của giao thức định tuyến proactive.   Các giao thức định tuyến theo yêu cầu thiết lập tuyến dựa theo từng yêu cầu kết nối. Phương pháp này hạn chế được thông tin tiêu đề chọn đường, nhưng nhược điểm cơ bản là gây trễ lớn cho các khung truyền dẫn đầu tiên cũng như thời gian chọn đường dẫn chậm. Hai giao thức reactive điển hình là giao thức định tuyến vector khoảng cách theo yêu cầu AODV (On-demand Distance Vector Routing) [RFC 3561] và giao thức định tuyến định tuyến nguồn động DSR (Dynamic Source Routing) [RFC 4728].   Một khi xảy ra lỗi tại node, các giao thức định tuyến thường khôi phục đường dẫn bằng phương pháp thiết lập tuyến mới. Hầu hết các tiếp cận hiện nay đều sử dụng thông tin phản hồi tới thiết bị nguồn nhằm khởi tạo tuyến mới, vì vậy lưu lượng bản tin trao đổi là rất lớn và tăng lên rất nhanh khi kích thước mạng lớn, nhất là đối với các giao thức định tuyến proactive. Khi kích thước mạng tăng cũng đồng nghĩa với sự suy giảm hiệu năng mạng do hiện tượng trễ của thủ tục định tuyến và truyền khung đầu tiên tăng lên rất lớn nếu sử dụng giao thức định tuyến reactive.   Để khắc phục một số nhược điểm của hai loại giao thức trên, 802.11s đưa ra giải pháp định tuyến lai và sử dụng giao thức định tuyến không dây lai HWRP (Hybrid wireless routing protocol) là giao thức định tuyến ngầm định trong WLAN.  2.6.2 Tham số đo lượng liên kết vô tuyến Chất lượng dịch vụ của WLAN phụ thuộc lớn vào chất lượng các liên kết không dây, độ xuyên nhiễu và tỉ lệ chiếm dụng tài nguyên vô tuyến. Để phản ánh các điều kiện trên, 802.11s định nghĩa tham số đo lượng liên kết Airtime được sử dụng để tính toán năng lực truyền dẫn giữa các cặp liên kết trong mạng hình lưới. Tham số này mô tả số lượng nguồn tài nguyên kênh tiêu thụ bởi các khung truyền dẫn qua liên kết cụ thể . Để sử dụng trong tính toán định tuyến, tham số đo lượng liên kết Airtime được thể hiện qua tham số tính giá (cost). Tham số tính giá Ca được định nghĩa theo tốc độ điều chế r và tỉ lệ bít lỗi ept cho một khung kiểm tra có kích thước Bt.  Tiêu đề truy nhập kênh Oca, tiêu đề giao thức Op và kích thước khung kiểm tra Bt là hằng số theo bảng 1. Bảng 1: Các hằng số đo lượng liên kết Airtime Tham số 802.11a 802.11b Mô tả Oca 75 µs 335 µs Tiêu đề truy nhập kênh Op 110 µs 364 µs Tiêu đề giao thức Bt 8224 8224 Số lượng bit trong khung 2.6.3 Giao thức định tuyến không dây lai HWRP 802.11s định nghĩa giao thức định tuyến không dây lai HWMP là giao thức định tuyến ngầm định và giao thức RA-OLSR là giao thức định tuyến tùy chọn. HWMP tổ hợp hai giao thức định tuyến (proactive, reactive) tương ứng với giao thức định tuyến  dựa trên hình cây TBR (Tree Based Routing) và giao thức định tuyến Radio Metric-AODV. Radio Aware-OLSR là giao thức định tuyến proactive sử dụng tham số đo lượng liên kết Airtime để lựa chọn node trễ đa điểm MPR (Multi-Point Relay), MPR có nhiệm vụ chuyển tiếp các bản tin điều khiển, giảm tối thiểu lưu lượng tiêu đề. Cả hai giao thức đề xuất RA-OLSA và RM-AODV đều hoạt động trên lớp 2 theo các địa chỉ MAC và sử dụng thông số đo lượng liên quan trực tiếp tới đặc tính liên kết vô tuyến.  Định tuyến reactive: Với giao thức định tuyến theo yêu cầu, các tuyến yêu cầu kết nối trong mạng không bắt buộc phải đi qua node gốc. Trong IEEE 802.11s sử dụng hai cơ chế yêu cầu tuyến RReq (Route Request) và đáp ứng tuyến RRep (Route Reply) để thu thập các thông tin định tuyến. Để thực hiện duy trì tuyến, các node gửi định kỳ bản tin RReq có gắn số thứ tự nhằm tránh hiện tượng lặp vòng. Cơ chế trễ thường được thêm vào để tránh việc cập nhật tuyến quá nhanh, thường xảy ra  trong trường hợp lỗi tuyến và các bản tin cập nhật RReq từ tuyến nguyên thủy bị mất hoặc RReq từ các tuyến khác đến nhanh hơn. Cơ chế trễ thực hiện việc lưu lại tuyến tốt nhất trong một khoảng thời gian nhất định.   Định tuyến proactive: Mạng WMN có đặc tính động của các node hình lưới thấp hơn rất nhiều so với mạng MANET. Vì vậy, phương pháp định tuyến proactive được đề xuất trong IEEE 802.11s là giao thức định tuyến hình cây TBR. TBR coi WMN như một cây phân cấp có cấu trúc với một nút gốc là MPP và các nút lá là các MP hoặc MAP. Giao thức TBR sử dụng MPP để tìm và duy trì các tuyến. Thông tin tuyến giữa các node lá và node gốc được thu thập qua bản tin thăm dò node nguồn gửi đi từ node gốc xuống các node lá theo phương thức quảng bá và phát lại quảng bá bản tin. Thông tin tuyến từ node gốc tới bất kỳ node lá bất kỳ được thu thập qua bản tin đáp ứng tuyến RRep hướng từ node lá tới node gốc. Các thông tin này được lưu trong bảng chuyển tiếp để sử dụng như địa chỉ bước kế tiếp cho các gói tin đến node. Các bước hoạt động cơ bản của giao thức định tuyến TBR được trình bày trên lược đồ tại hình 1.7. Hình 1.7: Các bước thủ tục chính của giao thức TBR Bước 1: Lựa chọn MP trong mạng hình lưới làm gốc, thông thường là MPP. Bước 2: Bản tin thông báo được phát chuyển quảng bá từ node gốc tới các node lá, các node nhận thông tin thực hiện thiết lập đường dẫn tới node gốc và lựa chọn nút cha qua bản tin RRep hướng ngược.  Bước 3: MP duy trì đường dẫn bằng cách gửi bản tin RReq tới nút cha và nhận lại bản tin RRep.    Bước 4: Khi nhận được node cha, MP đăng ký chính nó với node gốc bằng bản tin RRep. Mỗi một node trung gian trên đường dẫn đều nhận được bản tin tương tự để cập nhật vào bảng định tuyến.  Bước 5: Việc chuyển tiếp dữ liệu, duy trì cấu hình và tối ưu hóa được thực hiện tại bước này. Dữ liệu được chuyển tiếp dọc theo đường dẫn tới node gốc qua các node trung gian và chức năng duy trì cấu hình được thực hiện qua các bản tin RReq được gửi định kỳ.  Bước 6: Nếu một node MP thay đổi node cha bởi một node cha khả tuyển nằm trong danh sách định tuyến, nó sẽ gửi bản tin đăng ký lại tới node gốc sau đó node gốc sẽ gửi bản tin thông báo lỗi tới đường dẫn cũ. Nếu không có node cha khả tuyển trong danh sách, thủ tục khởi tạo lại tuyến bắt đầu lại từ bước 1.   Giao thức TBR luôn chỉ thiết lập duy nhất một đường dẫn hoạt động cho một kết nối. Vì vậy, khi xuất hiện các yêu cầu thay đổi đường dẫn, TBR phải thực hiện lại một số thủ tục cùng với hàng loạt bản tin, điều này sẽ là trở ngại lớn khi mạng mở rộng và có số lượng node lớn. Trong đề xuất giao thức định tuyến dựa trên hình cây với các node chuyển tiếp hình lưới TBR-MRN (Mesh Relaying Node), cung cấp thuật toán thiết lập đa đường để giảm trễ kết nối và cung cấp tuyến thay thế dự phòng.   RA-OLSR cho phép tìm kiếm và duy trì đường dẫn tối ưu dựa trên các metric xác định trước, điều này cho phép mỗi MP có một cơ cấu riêng để xác định giá của liên kết tới node cận kề. Để truyền các thông tin giá liên kết giữa các MP, một trường chức năng riêng được sử dụng trong các phần tử thông tin RA-OLSR. Việc sử dụng cấu trúc MPR của giao thức OLSR nhằm để tối ưu các bản tin điều khiển tràn lụt và giảm tiêu đề giao thức. Tuy nhiên, giao thức này cần phải tiếp tục cải thiện vì cấu trúc MPR có thể gây ra các hiện tượng như: Quảng bá liên kết kém chất lượng, có xu hướng tập trung lưu lượng vào một số liên kết và chịu tác động lớn khi có lỗi xảy ra.  Tiêu chuẩn mạng hình lưới WLAN 802.11s cho tập dịch vụ mở rộng ESS đóng vai trò tiêu chuẩn then chốt cho khung làm việc của bài toán kết nối và định tuyến WLAN. Vì thế đó là một tiêu chuẩn rất hữu ích cho những nhà thiết kế và khai thác mạng WiFi hiện nay. Dù vậy, tiêu chuẩn này còn chứa đựng nhiều khía cạnh cần tiếp tục cải thiện để phù hợp tốt nhất với môi trường ứng dụng lớn, nhất là vấn đề định tuyến đảm bảo chất lượng dịch vụ và hiệu năng mạng. Các giao thức định tuyến ở trên trên đều hướng vào lớp MAC để khai thác hiệu quả nhất tài nguyên vô tuyến. Vì vậy, các phương pháp định tuyến đa đường đảm bảo chất lượng dịch vụ hay định tuyến heuristic sẽ là những hướng mở cho môi trường mạng phức hợp nhằm phát huy thế mạnh của mạng hình lưới không dây. III. Giao thức định tuyến vectơ cự ly theo yêu cầu tùy biến AODV 3.1.Tổng quan về AODV Yêu cầu cơ bản của thuật toán có thể được gọi là các hệ thống tiếp nhận đường đi theo yêu cầu thuần túy; các nút không nằm trên tuyến hoạt động thì không duy trì bất kì thông tin định tuyến cũng như không tham gia vào bất kì bảng định tuyến nào. Hơn nữa, một nút không có gì để khám phá và duy trì tuyến tới nút khác cho đến khi hai nút phải kết nối, trừ khi các nút trước cung cấp các dịch vụ của mình như là trạm trung chuyển để duy trì kết nối giữa hai nút khác. Khi khu vực kết nối của nút di động được quan tâm, mỗi nút di động có thể nhận biết được các nút hàng xóm nhờ việc sử dụng một số kĩ thuật, bao gồm quảng bá nội vùng ( không phải toàn hệ thống) được biết đến như các bản tin Hello. Bảng định tuyến của các nút lân cận được tổ chức tối ưu hóa thời gian để đáp ứng nội vùng và cung cấp cho các yêu cầu thành lập tuyến mới. Mục tiêu chính của thuật toán là: Chỉ phát gói quảng bá khi cần thiết Để phân biệt giữa quản lý kết nối nội vùng và duy trì topo mạng nói chung. Để phổ biến thông tin về các thay đổi trong kết nối nội cùng với các nút di động hàng xóm có khả năng cần thông tin. AODV sử dụng một cơ chế khám phá tuyến, cũng như được sử dụng ( với sửa đổi, bổ sung) trong thuật toán định tuyến nguồn động DSR. Thay vì dùng tuyến nguồn, AODV lại dựa vào bảng định tuyến thiết lập động tại các nút trung gian. Sự khác biệt này phải trả giá trong mạng mà có nhiều nút, nơi mà chi phí lớn hơn là các tuyến nguồn được mang trong mỗi gói dữ liệu.Mỗi nút ad hoc duy trì một bộ đếm số của chỉ số thứ tự tăng đơn điệu cái mà được dùng để thay thế cho bộ nhớ tuyến. Sự kết hợp của các kĩ thuật này tạo ra một thuật toán sử dụng băng thông một cách hiệu quả (bằng cách giảm tối thiểu tải trọng mạng để điều khiển và phân phát dữ liệu) là đáp ứng sự thay đổi trong topo và đảm bảo vòng lặp tuyến tự do. Các vấn đề cơ bản của thuật toán định tuyến AODV là: Các bản tin ROUTER REQUEST và ROUTER REPLY (Khám phá đường) Các bản tin ROUTER ERORR, HELLO và danh sách lưu giữ tuyến trước ( Duy trì đường) Các chỉ số thứ tự Hopcount Mở rộng vòng định tuyến 3.1.1. Khám phá đường Quá trình khám phá đường được phát động mỗi khi một nút nguồn cần truyền thông với một nút khác khi mà nó không có thông tin định tuyến về nút này trong bảng của nó. Nút nguồn phát động khám phá đường bằng việc quảng bá gói Route Request (RREQ) tới các hàng xóm của nó. . Hình 2.1: Quá trình gửi yêu cầu khám phá đường Khi một nút cần xác định tuyến tới một nút đích, nó tạo ra sự tràn lụt các bản tin RREQ trong mạng. Nút khởi đầu này quảng bá một bản tin RREQ tới tất cả các nút lân cận, các nút này lại tiếp tục quảng bá bản tin tới các hàng xóm của nó, và cứ như vậy. Để ngăn chặn sự quay vòng chu kì, mỗi nút nhớ việc chuyển tiếp tuyến yêu cầu mới nhất trong một bộ nhớ đệm tuyến yêu cầu (route request buffer). Khi các yêu cầu này trải rộng trong mạng, các nút trung gian lưu giữ các tuyến ngược quay lại nút nguồn. Khi một nút trung gian có nhiều tuyến ngược, nó luôn luôn chọn các tuyến với giá trị hop count nhỏ nhất. Khi một nút nhận được yêu cầu của một nút khác hoặc nó biết một tuyến đủ mới tới đích, hoặc bản thân nó chính là đích, nút này sẽ phát động một bản tin RREP, và gửi bản tin này dọc theo tuyến ngược quay trở lại nút nguồn. Khi bản tin RREP vượt qua các nút trung gian, các nút này sẽ cập nhật bản định tuyến của nó, để mà trong tương lai, các bản tin có thể được gửi theo tuyến này tới đích. Nút khởi đầu RREQ có thể nhận được bản tin RREP từ nhiều hơn một nút. Mỗi nút hàng xóm khi nhận được RREQ hoặc gửi bản tin Route Reply (RREP) quay trở lại nút nguồn hoặc quảng bá tiếp gói tin RREQ tới các hàng xóm khác của nó sau khi đã tăng chỉ số hop count lên 1. 3.1.2 Duy trì đường Mỗi nút lưu giữ một danh sách chặng trước và danh sách cổng ra. Một danh sách chặng trước là một thiết lập các nút mà tuyến xuyên suốt qua nút giữ danh sách. Danh sách cổng ra là thiết lập các chặng tiếp theo mà nút gửi qua. Trong các mạng nơi mà tất cả các tuyến là song hướng, các danh sách này về cơ bản là như nhau. Mỗi nút gửi định kì các bản tin Hello tới các chặng trước của nó. Một nút quyết định gửi một bản tin Hello tới một chặng trước xác định chỉ khi nếu không có bản tin nào được gửi gần đây tới chặng trước đó. Do đó, mỗi nút mong đợi nhận định kì các bản tin (không giới hạn các bản tin Hello) từ mỗi nút trong danh sách cổng ra của nút. Nếu một nút không nhận được bản tin nào từ một vài nút cổng ra trong một khoảng thời gian dài, khi đó nút được cho là không còn có thể tới được. Mỗi khi một nút xác định được một trong số các chặng tiếp theo của nó không còn tới được, nó hủy bỏ tất cả các mục tuyến ảnh hưởng và phát động một bản tin RERR. Bản tin RERR này bao gồm một danh sách tất cả các đích mà không thể tới được như một kết quả của liên kết gãy. Các nút gửi RERR tới mỗi chặng trước của nó. Các chặng trước này cập nhận bản định tuyến và lần lượt chuyển tiếp RERR đến các chặng trước của nó, và cứ như vậy. Để ngăn chặp lặp các bản tin RERR, một nút chỉ chuyển tiếp bản tin RERR nếu ít nhất một tuyến đã bị hủy bỏ. Hình 2.2: Tóm tắt xử lý nhận tại một nút Hoạt động của các nút không nằm dọc theo một tuyến hoạt động nào không ảnh hưởng tới tuyến đường tới đích. Nếu các nút nguồn di chuyển trong suốt một phiên hoạt động, nó có thể phát động lại khám phá tuyến để thành lập một tuyến mới tới đích. Khi hoặc đích hoặc một vài nút trung gian di chuyển, một RREP đặc biệt được gửi tới các nút nguồn bị ảnh hưởng. Bản tin Hello định kì có thể được sử dụng để đảm bảo liên kết đối xứng cũng như phát hiện liên kết lỗi. Như một sự lựa chọn, sự tiềm tàng như các lỗi có thể được phát hiện nhờ việc sử dụng link-layer acknowledgments (LLACKS). Một liên kết lỗi cũng được chỉ ra nếu việc cố gắng chuyển tiếp một gói tin tới nút hàng xóm thất bại. Chỉ một lần chặng tiếp theo trở nên không nhận được, nút luồng lên bị gẫy sẽ quảng bá một RREP được gửi đi với một chỉ số thứ tự mới nhất (ví dụ, một chỉ số thứ tự mà lớn hơn chỉ số trước đấy được biết) và hop count tại vô cùng tới tất cả các hoạt động luồng lên của các hàng xóm khác. Những nút này sau đó chuyển tiếp bản tin tới các hàng xóm hoạt động của nó. Quá trình này được tiếp tục cho đến khi tất cả các hoạt động của nút nguồn được thông báo là kết thúc bởi vò AODV chỉ duy trì vòng lặp tuyến tự do và chỉ có một số lượng có hạn các nút trong mạng ad hoc. Nhờ vào việc nhận khai báo của các liên kết gãy, nút nguồn có thể khởi động lại quá trình khám phá tuyến nếu nó vẫn yêu cầu một tuyến tới đích. Để xác định một tuyến vẫn cần thiết hay không, một nút có thể kiểm tra các tuyến được sử dụng mới đây, cũng như các khối điều khiểu các giao thức lớp trên xác định các kết nối mở còn lại được chỉ đến đích. Nếu các nút nguồn (hay bất cứ nút nào dọc theo tuyến trước đó) quyết định nó muốn thiết lập lại tuyến đường tới đích, nó sẽ gửi một RREQ với chỉ số thứ tự đích của một số lớn hơn chỉ số được biết đến trước đấy, để đảm bảo rằng nó xây dựng một tuyến mới, tuyến có thể tồn tại, và không có nút hồi đáp nếu nó vẫn quan tâm đến tuyến trước đó. 3.2.Định dạng các gói tin 3.2.1 Định dạng gói tin ROUTE REQUEST Hình 2.3: Định dạng bản tin Route Request. Các trường trong gói tin RREQ: Type: Xác định kiểu gói tin. Khi một nút không hiểu kiểu của một gói tin thì phải hủy bỏ gói tin. J: Join flag. Được dự trữ cho Multicast R: Repair flag. Được dùng dự trữ cho Multicast. G: Gratuitous RREP flag. Chỉ định một Gratuitous RREP có nên được truyền tải unicast hay không tới nút đã được chỉ định trong trường địa chỉ IP đích. D: Destination only flag. Xác định rõ là chỉ có một đích hồi đáp RREQ này. U: Unknow sequence number. Xác định rõ là chỉ số thứ tự đích không được biết. Hop count: Chỉ số chặng. Khi một nút trung gian quảng bá tiếp bản tin RREQ đến các nút hàng xóm, nó sẽ tăng chỉ số hop count lên 1 khi gửi RREQ id: Chỉ số RREQ id được quyết định bởi nút khởi tạo RREQ. Mỗi khi nó khởi tạo một RREQ mới thì chỉ số broadcast id được tăng thêm 1. Destination IP Address: Địa chỉ của nút đích mà cần tìm đường để thực hiện truyền tin từ nút nguồn tới nút đích. Destination Sequence Number: Chỉ số thứ tự đích. Là chỉ số cuối cùng được nhận bởi nguồn từ bất kì tuyến nào theo hướng tới đích. Originator IP Address: Địa chỉ của nút nguồn phát động bản tin RREQ. Originator Sequence Number: Chỉ số thứ tự hiện tại được sử dụng trong mục tuyến trỏ theo hướng nguồn của RREQ. 3.2.2 Định dạng gói ROUTE REPLY Hình 2.4: Định dạng gói tin Route Reply. Trong đó: Type: 2 R: Repair flag; được sử dụng cho Multicast A: Acknowledgment required Prefix Size: Kích thước tiền tố. Nếu khác không, 5 bit kích thước tiền tố xác định rằng các chỉ báo chặng tiếp theo có thể được sử dụng cho bất kì tuyến nào với cùng một tiền tố định tuyến như đích được yêu cầu. Hop count: Chỉ số chặng. Khi một nút trung gian quảng bá tiếp bản tin RREQ đến các nút hàng xóm, nó sẽ tăng chỉ số hop count lên 1 khi gửi Destination IP Address: Địa chỉ của nút đích mà cần tìm đường để thực hiện truyền tin từ nút nguồn tới nút đích. Destination Sequence Number: Chỉ số thứ tự đích. Là chỉ số cuối cùng được biết đến của đích được yêu cầu. Orginator IP Address: Địa chỉ IP của nút khởi đầu RREQ. Lifetime: Thời gian tồn tại của gói tin sau khi được gửi. Chú ý rằng Prefix Size cho phép Router của mạng con cung cấp một tuyến cho mọi trặm trong mạng con được định nghĩa bởi tiền tố định tuyến, cái mà được xác định rõ bởi địa chỉ IP của Router mạng con và kích thước tiền tố. Để mà sử dụng tính năng này, Router mạng con đảm bảo có thể đến được tất cả các trạm chia sẻ chỉ định tiền tố mạng con. Bit A được sử dụng khi liên kết qua cái mà bản tin RREP được gửi có thể không đáng tin cậy hoặc là đơn hướng. Khi bản tin RREP chứa bit A được thiết lập, nút nhận RREP sẽ được mong chờ hồi đáp lại bản tin RREP-ACK. 3.2.3. Định dạng gói ROUTE ERROR Hình 2.5: Định dạng gói tin Route Error. Các trường trong gói RERR: Type: 3 N: No delete flag. Cờ này được thiết lập khi một nút thực hiện sửa chữa một liên kết nội vùng và các nút đường lên không nên xóa tuyến. Destination Count: Số lượng các đích không thể đến được trong bản tin. Phải ít nhất là 1. Unreachable Destination IP Address: Địa chỉ IP của đích mà không thể đến được do liên kết gãy. Unreachable Destination Sequence Number: Chỉ số thứ tự trong mục bảng định tuyến cho đích được liệt kê trong trường Unreachable Destination IP Address trước. Bản tin RERR được gửi mỗi khi một liên kết bị gãy làm cho một hay nhiều đích không thể đến được từ một vài nút hàng xóm. 3.2.4. Định dạng gói Route Reply Acknowledgment Hình 2.6: Định dạng gói tin Route Rply Acknowledgment. Trong đó: Type: 4 Reserved: Được dùng để dự phòng. Bản tin Route Reply Acknowledgment (RREP-ACK) phải được gửi trong sự hồi đáp bản tin RREP với bit A được thiết lập. Điều này thường được thực hiện khi có nguy cơ các liên kết đơn hướng ngăn chặn sự hoàn thành một lộ trình khám phá đường. 3.3.Hoạt động của AODV Mô tả các tính huống mà trong đó các nút khởi tạo các bản tin RREQ, RREP, RERR cho truyền thông unicast về phía đích, và các bản tin được điều khiển như thế nào. Để xử lý các bản tin chính xác, thông tin trạng thái chắc chắn được duy trì trong các mục của bảng định tuyến đối với các nút đích được quan tâm. 3.3.1.Sự duy trì các chỉ số thứ tự Mọi mục của của bảng định tuyến tại mọi nút phải chứa những thông tin mới nhất có hiệu lực về chỉ số thứ tự đối với địa chỉ IP của nút đích mà ở đó mục của bảng định tuyến được duy trì. Chỉ số thứ tự này được gọi là “chỉ số thứ tự đích”. Nó được cập nhận mỗi khi một nút nhận được thông tin mới về chỉ số thứ tự từ các bản tin RREQ, RREP, RERR mà có thể nhận được sự liên quan tới đích đó. Một nút đích tăng chỉ số thứ tự của nó trong hai tình huống sau: Ngay trước khi một nút phát động một khám phá tuyến, nó phảu tăng chỉ số thứ tự của nó. Điều này ngăn chặn sự xung đột với các tuyến ngược được thiết lập trước đó theo hướng nút khởi đầu của một RREQ. Ngay trước khi một nút đích khởi tạo một RREP để hồi đáp tới một RREQ, nó phải cập nhật chỉ số thứ tự của nó với giá trị chỉ số thứ tự lớn nhất hiện tại và chỉ số thứ tự đích trong gói RREQ. Khi đích tăng chỉ số thứ tự của nó, nó phải làm vậy bằng cách xử lý các giá trị chỉ số thứ tự như thể nó là một số chưa được đánh dấu. Để hoàn thành cuộn số thứ tự, nếu số thứ tự đã được gán là số lớn nhất có thể biểu diễn như một số nguyên chưa đánh dấu 32 bit (ví dụ 4294967295), thì khi nó được tăng nó sẽ có giá trị 0. Mặt khác, nếu dãy số hiện tại có giá trị hiện tại là 2147483647, là số nguyên dương lớn nhất có thể nếu số bù thứ hai được sử dụng với hệ số nguyên 32-bit, giá trị tiếp theo sẽ là 2147483648, là số nguyên âm lớn nhất trong cùng hệ số. Sự đại diện của các số âm là không thích hợp cho sự gia tăng của các dãy số AODV. Việc này đối lập với kiểu mà sự so sánh hai dãy số AODV được xử lý. Để có thể biết chắc rằng thông tin về đích đến là không cũ, node sẽ so sánh giá trị hiện tại của dãy số của nó với giá trị mà nó thu được từ thông điệp AODV đi tới. Sự so sánh này bắt buộc phải được thực hiện bằng các số 32-bit đã đánh dấu, đây là điều cần thiết để hoàn thành việc đảo ngược dãy số. Nếu kết quả của việc trừ đi dãy số đang lưu trữ từ giá trị của dãy số đang tới là nhỏ hơn 0 thì thông tin liên quan đến đích đến đó trong thông điệp AODV bắt buộc phải bị bỏ đi, do thông tin đó đã cũ so với các thông tin hiện có của node. Trường hợp khác duy nhất mà một node có thể thay đổi dãy số đích đến trong một trong số các mục bảng định tuyển của nó, là trong sự phản hồi tới một liên kết đã cũ hay quá hạn tới chặng tiếp theo hướng đến đích. Node sẽ xác định đích nào sử dụng một chặng đặc biệt tiếp theo bằng cách hỏi ý kiến bảng định tuyển. Trong trường hợp này, đối với mỗi đích sử dụng chặng tiếp theo, node gia tăng dãy số và đánh dấu tuyến như là không có hiệu lực. Mỗi khi có một thông tin định tuyến nào đủ mới (chứa một dãy số ít nhất là cân bằng với dãy số đã ghi nhận) cho đích đến bị ảnh hưởng được tiếp nhận bởi một node mà đã đánh dấu mục bảng định tuyển đó là không có hiệu lực, node sẽ phải cập nhật thông tin bảng định tuyển dựa theo thông tin chứa trong phần cập nhật. Một node có thể thay đổi dãy số trong mục bảng định tuyển của một đích đến chỉ khi: Bản thân nó là node đích đến, và nó cung cấp một tuyến mới cho chính nó, hoặc Nó tiếp nhận một thông điệp AODV với các thông tin mới về dãy số cho node đích đến, hoặc Đường dẫn tới node đích đến đã quá hạn hoặc hư hỏng 3.3.2 Các mục của bảng định tuyến và danh sách chặng trước Khi một nút nhận được một gói điều khiển AODV từ một hàng xóm, hoặc khởi tạo hay cập nhật một tuyến cho một đích hoặc mạng con cụ thể, nó kiểm tra bảng định tuyến của nó với một mục cho đích. Trong sự kiện mà không có mục tương ứng cho đích đó, một mục được tạo ra. Chỉ số thứ tự hoặc được xác định từ thông tin chứa trong gói điều khiển hoặc ngược lại trường chỉ số thứ tự hợp lệ được thiết lập là false. Tuyến chỉ được cập nhật nếu chỉ số thứ tự mới hoặc hoặc là cao hơn chỉ số thứ tự đích của bảng định tuyến, hoặc chỉ số thứ tự bằng, nhưng chỉ số hop count cộng 1 nhỏ hơn chỉ số hop count hiện nay trong bảng định tuyến hoặc chỉ số thứ tự không biết. Trường Lifetime của mục bảng định tuyến hoặc được xác định từ gói điều khiển hoặc được thiết lập bằng ACTIVE_ROUTE_TIMEOUT. Tuyến này có thể được sử dụng hiện tại để gửi bất kì gói dữ liệu được xếp hàng nào và thực hiện bất kì yêu cầu tuyến nào chưa được giải quyết. Mỗi lần một tuyến được dùng để chuyển tiếp gói dữ liệu, trường Active Route Lifetime của nguồn, đích và chặng tiếp theo trong đường tới đích được cập nhận không nhỏ hơn thời gian hiện tại cộng với ACTIVE_ROUTE_TIMEOUT. Vì cặp tuyến giữa mỗi đích và nguồn được mong đợi là đối xứng, thời gian Active Route Lifetime cho chặng trước, dọc theo tuyến ngược trở lại nút nguồn cũng được cập nhật với giá trị không nhỏ hơn thời gian hiện tại cộng với ACTIVE_ROUTE_TIMEOUT. Thời gian sống Lifetime cho một tuyến hoạt động được cập nhật mỗi khi tuyến được sử dụng mà không quan tâm đến đích là nút đơn hay là một mạng con. Đối với mỗi tuyến hợp lệ được duy trì bởi một nút như một mục bảng định tuyến, nút cũng duy trì một danh sách chặng trước mà có thể chuyển tiếp các gói tin trên tuyến này. Những chặng trước này sẽ nhận được thông báo từ node trong trường hợp phát hiện các tổn thất của liên kết chặng kế tiếp. Danh sách của các chặng trước này trong một mục bảng định tuyến bao gồm các hàng xóm của nút này trong đó một RREP đã được khởi tạo hoặc chuyển tiếp. 3.3.3 Khởi tạo các Route Request Một nút phổ biến một RREQ khi nó xác định rằng nó cần một tuyến tới một đích và chưa có tuyến nào sẵn sàng. Điều này có thể xảy ra nếu đích là một nút không biết trước, hoặc nếu một tuyến hợn lệ trước đó tới đích hết hạn hoặc bị đánh dấu là không hợp lệ. Trường chỉ số thứ tự đích trong bản tin RREQ là chỉ số thứ tự cuối cùng được biết tới đối với đích này và được sao chép từ trường chỉ số thứ tự đích trong bảng định tuyến. Nếu chỉ số thứ tự không được biết, cờ chỉ số thứ tự không biết phải được thiết lập. Chỉ số thứ tự nguồn trong bản tin RREQ là chỉ số thứ tự của chính nút đó, cái mà được tăng trước khi được gài vào một RREQ. Trường RREQ ID được tăng từ một giá trị RREQ ID cuối cùng được sử dụng bởi nút hiện tại. Mỗi nút chỉ duy trì một RREQ ID. Trường Hop Count được thiết lập là 0. Trước khi quảng bá RREQ, nút khởi đầu nhớ đệm RREQ ID và địa chỉ IP nguồn (địa chỉ của chính nó) của RREQ trong thời gian khám phá tuyến PATH_DISCOVERY_TIME. Bằng cách này, khi nút nhận lại gói từ các hàng xóm của nó, nó sẽ không xử lý và chuyển tiếp lại gói. Một nút khở đầu thường mong đợi có các đường truyền song hướng với nút đích. Trong những trường hợp như vậy, nó không phải là đủ cho nút khởi đầu để có một tuyến tới đích; đích cũng phải có một tuyến quay lại nút nguồn. Để cho việc này diễn ra hiệu quả có thể, bất cứ sự khởi đầu RREP bởi một nút trung gian để hồi đáp tới nút nguồn nên được thêm vào bằng một vài hoạt động mà báo tin cho đích về một tuyến quay lại nút khởi đầu. Nút khởi đầu chọn chế độ hoạt động này trong các nút trung gian băng việc thiết lập cờ G. Một nút không nên khởi đầu nhiều hơn RREQ_RATELIMIT các bản tin RREQ trên một giây. Sauk hi quảng bá một RREQ, một nút đợi một RREP (hoặc bản tin điều khiển khác với thông tin hiện tại về một tuyến tới đích thích hợp). Nếu một tuyến không được nhận trong vòng NET_TRAVERSAL_TIME milliseconds, nút có thể cố gắng thử lại để tìm một tuyến bằng các quảng bá một RREQ khác, tăng giá trị TTL lên giá trị lớn nhất của số lần RREO_RETRIES. Mỗi một sự thử mới phải tăng và cập nhật RREQ ID. Đối với mỗi sự thử, trường TTL của mào đầu IP được thiết lập để mà kích hoạt tính năng điều khiển các RREQ ở xa được phổ biến cho mỗi lần thử. Các gói dữ liệu chờ một tuyến nên được nhớ đệm. Việc đệm nên theo cơ chế FIFO. Nếu một khám phá tuyến được thử RREQ_RETRIES lần tại giá trị TTL lớn nhất mà không nhận được một RREP nào, tất cả các gói tin từ trước cho đích tương ứng nên được hủy bỏ từ bộ nhớ đệm và một bản tin Destination Unreachable nên được hồi đáp. Để giảm sự tắc nghẽn trong mạng, các sự thử được lặp lại bởi nút nguồn với khám phá tuyến cho một nút đơn phải sử dụng một hàm mũ cơ số 2. Lần đầu tiên một nút quảng bá một RREQ, nó đợi trong NET_TRAVERSAL_TIME millisecond để nhận một RREP. Nếu một RREP không được nhận trong vòng thời gian này, nút nguồn gửi một RREQ mới. Khi tính toán thời gian để chờ một RREP sau khi gửi RREQ thứ hai, nút nguồn phải dùng một hàm mũ cơ số 2. Do đó, thời gian chờ để nhận RREP cho RREQ thứ hai là 2 x NET_TRAVERSAL_TIME millisecond. Nếu một RREP không được nhận trong khoảng thời gian này, một RREQ khác được gửi, lên đến RREQ_RETRIES số lần gửi thêm sau RREQ đầu tiên. 3.3.4 Điều khiển sự phân phát các bản tin Route Request Khi một nút cần xác định tuyến tới một nút đích, nó tạo ra sự tràn lụt các bản tin RREQ trong mạng. Nút khởi đầu này quảng bá một bản tin RREQ tới tất cả các nút lân cận, các nút này lại tiếp tục quảng bá bản tin tới các hàng xóm của nó, và cứ như vậy. Khi kích thước của một mạng nhỏ, thì đây không phải là một mối quan tâm lớn. Tuy nhiên, khi một mạng lớn, thì nó có thể cực kì hoang phí, đặc biệt nếu nút đích tương đối gần với nút nguồn. Do đó khi thiết lập giá trị tham số TTL trong bản tin RREQ để vừa đủ lớn cho bản tin này có thể tìm được đích, nhưng không quá lớn. Tuy nhiên, rất khó để một nút có thể xác định được tham số tối ưu TTL mà không có kiến thức trước về toàn bộ mạng. Để giải quyết vấn đề này, người ta thực hiện một thuật toán mở rộng vòng tìm kiếm được hoạt động như mô tả sau đây. Khi một nút phát động một RREQ, đầu tiên nó quảng bá bản tin RREQ với một giá trị TTL nhỏ ( chẳng hạn 1). Nếu nút khởi đầu bản tin không nhận được bản tin hồi đáp RREP trong một khoảng thời gian ngắn, nó sẽ quảng bá lại bản tin với một giá trị TTL lớn hơn ( và cùng với một chỉ số nhận dạng khác để phân biệt là yêu cầu mới với cùng một nút cũ). Các nút quảng bá tiếp tục bản tin và tăng giá trị TTL và RREQ id cho đến khi nó nhận được một RREP. Nếu giá trị TTL trong yêu cầu tuyến đạt tới một ngưỡng nhất định, và vẫn không có bản tin RREP nào được trả lời, sau đó có vẻ như không đến được nút đích, và các bản tin này được xếp hàng đợi cho đích này cho đến khi bị ném ra. 3.3.5 Xử lý và chuyển tiếp các Route Request Khi một nút nhận một RREQ, đầu tiên nó tạo hoặc cập nhật một tuyến tới các chặng trước không có một chỉ số thứ tự hợp lệ sau đó kiểm tra để xác định nó có phả đã nhận một RREQ với cùng địa chỉ IP nguồn và RREQ ID trong vòng ít nhất thời gian PATH_DISCOVERY_TIME cuối cùng hay không. Nếu như một RREQ đã được nhận, nút lẳng lặng hủy bỏ RREQ được nhận mới nhất này. Phần tiếp theo sẽ mô tả các hành động đối với các RREQ mà được cho rằng không phải hủy bỏ. Đầu tiên, nó tăng giá trị hop count trong RREQ thêm 1, để tính toán cho chặng mới qua nút trung gian. Sau đó nó tìm một tuyến ngược tới nút nguồn, nếu cần thiết, một tuyến được tạo, hoặc được cập nhật sử dụng chỉ số thứ tự nguồn từ RREQ trong bảng định tuyến của nó. Tuyến ngược này sẽ được cần đến nếu nút nhận một RREP quay lại nút mà đã khởi đầu RREQ. Khi tuyến ngược được tạo hoặc cập nhật, các hành động sau cũng được thực hiện: Chỉ số thứ tự nguồn từ RREQ được so sánh với chỉ số thứ tự đích tương ứng trong mục bảng định tuyến và được sao chép nếu lớn hơn giá trị trước đó. Trường chỉ số thứ tự hợp lệ được thiết lập là true. Chặng tiếp theo trong bảng định tuyến trở thành nút mà từ đó RREQ được nhận (nó được thu được từ địa chỉ IP nguồn trong mào đầu IP và thường xuyên không bằng trường địa chỉ IP nguồn tring bản tin RREQ). Chỉ số hop count được sao chép từ trường Hop count trong bản tin RREQ. Mỗi khi một bản tin RREQ được nhận, thời gian tồn tại của mục tuyến ngược đối với địa chỉ IP đích được thiết lập là giá trị lớn nhất cảu ExitingLifetime và MinimalLifetime, với MinilLifetime = ( thời gian hiện tại + 2 x NET_TRAVERSAL_TIME – 2 x hop count x NODE_TRAVERSAL_TIME). Nút hiện tại có thể sử dụng tuyến ngược để chuyển tiếp các gói dữ liệu trong cùng một tuyến như đối với bất kì tuyến nào trong bảng định tuyến. Nếu một nút không khởi tạo một RREP và nếu mào đầu IP đến có TTL lớn hơn 1, nút cập nhật và quảng bá RREQ với địa chỉ broadcast 255.255.255.255 trên mỗi giao diện mạng được cấu hình của nó. Để cập nhật RREQ, TTL hoặc trường hop limit trong mào đầu IP ra được tăng, để tính toán cho chặng mới qua nút trung gian. Cuối cùng, chỉ số thứ tự đích cho đích được yêu cầu được thiết lập giá trụ lớn nhất của giá trị được nhận tương ứng trong bản tin RREQ, và giá trị chỉ số thứ tự đích hiện tại được duy trì bởi nút cho đích được yêu cầu. Tuy nhiên, nút chuyển tiếp không được sửa đổi giá trị được duy trì của nó cho chỉ số thứ tự đích, mặc dù nếu giá trị được nhận trong RREQ đến lớn hơn giá trị hiện tại được duy trì bởi nút chuyển tiếp. Mặt khác, nếu một nút khởi tạo một RREP, thì nút hủy bỏ RREQ. Chú ý rằng, nếu các nút trung gian hồi đáp mọi sự truyền của các RREQ cho một đích cụ thể, nó phải chỉ ra rằng đích không nhận bất kì bản tin khám phá nào. Trong hoàn cảnh này, đích không học được tuyến tới nút khởi đầu từ các bản tin RREQ. Điều này có thể là nguyên nhân dẫn đến đích khởi tạo một khám phá tuyến. Để mà đích học được các tuyến tới nút khởi đầu, nút khởi đầu nên thiết lập bit cờ G trong RREQ nếu với bất kì lý do nào đích cần một tuyến tới nút khởi đầu. Nếu, trong hồi đáp RREQ với bit G được thiết lập, một nút trung gian hồi đáp một RREP, nó cũng phải truyền unicast tới nút đích. 3.3.6 Khởi tạo các Route Reply Một nút khởi tạo một RREP nếu hoặc: Nó chính là đích. Nó có một tuyến hoạt đông tới đích, chỉ số thứ tự đích trong bảng định tuyến hiện tại của nút cho đích này là hợp lệ và lớn hơn hoặc bằng chỉ số thứ tự đích trong RREQ, và cờ D không được thiết lập. Khi khởi tạo một bản tin RREP, một nút sao chép địa chỉ IP đích và chỉ số thứ tự nguồn từ bản tin RREQ vào các trường tương ứng trong bản tin RREP. Việc xử lý khác nhau là không đáng kể tùy thuộc vào nút chính là đích hay là một nút trung gian với một tuyển đủ mới tới đích. Chỉ một lần được tạo, RREP là unicast tới chặng tiếp theo theo hướng tới nút nguồn của RREQ như được chỉ ra bởi mục bảng định tuyến cho nút nguồn đó. Khi RREP được chuyển tiếp quay lại theo hướng nút khởi đầu bản tin RREQ, trường Hop Count sẽ được tăng qua mỗi chặng. 3.3.6.1 Sự khởi tạo RREP bởi đích Nếu nút khở tạo là đích, nó phải tăng chỉ số thứ tự của chính nó thêm 1 nếu chỉ số thứ tự trong gói RREQ bằng với giá trị được tăng đó. Nếu không, đích không thay đổi chỉ số thứ tự của nó trước khi khởi tạo bản tin RREP. Nút đích đặt chỉ số thứ tự của nó vào trường Destination Sequence Number của RREP, và điền giá trị 0 vào trường Hop count của RREP. Nút đích sao chép giá trị MY_ROUTE_TIMEOUT vào trường Lifetime của RREP. Mỗi nút có thể cấu hình lại giá trị của nó cho MY_ROUTE_TIMEOUT. 3.3.6.2 Sự khởi tạo RREP bởi một nút trung gian Nếu như nút khởi tạo RREP không là nút đích, nhưng để thay thế thì một nút trung gian dọc theo tuyến từ nguồn tới đích sao chép chỉ số thứ tự nó biết cho đích này vào trường chỉ số thứ tự đích trong bản tin RREP. Nút trung gian cập nhật mục tuyến chuyển tiếp bằng cách thay thế nút chặng cuối vào danh sách chặng trước cho mục chuyển tiếp. Nút trung gian cũng cập nhận mục bảng định tuyến của nó cho nút khởi đầu RREQ bằng cáh thay thế chặng tiếp theo theo hướng đích trong danh sách chặng trước cho mục tuyến ngược. Nút trung gian đặt khoảng cách của nó trong các chặng từ nó tới đích vào trường Hop Count của RREP. Trường Lifetime của RREP được tính toán bằng phép trừ thời gian hiện tại từ thời hạn kết thúc trong mục bảng định tuyến của nó. 3.3.7. Nhận và chuyển tiếp các Route Reply Khi một nút nhận bản tin RREP, nó sẽ tìm kiếm tìm kiếm một tuyến tới chặng trước. Nếu cần, một tuyến được tạo cho chặng trước, nhưng không có chỉ số thứ tự hợp lệ. Tiếp theo, nút tăng giá trị hop count trong RREP thêm 1, để tính toán cho chặng mới qua nút trung gian. Sau đó, tuyến chuyển tiếp cho đích này được tạo nếu nó không có trước đó. Nếu không, nút so sánh chỉ số thứ tự đích trong bản tin với chỉ số thứ tự được lưu bởi nó cho địa chỉ IP đích trong bản tin RREP. Nhờ vào sự so sánh, mục hiện tại được cập nhật chỉ trong các hoàn cảnh sau: Chỉ số thứ tự trong bảng định tuyến được đánh dấu như là không hợp lệ. Chỉ số thứ tự đích trong RREP lớn hơn bản sao chỉ số thứ tự đích của nút và giá trị được biết là hợp lệ. Chỉ số thứ tự là như nhau, nhưng tuyến được đánh dấu không hoạt động. CHỉ số thứ tự là như nhau, nhưng giá trị hop count mới nhỏ hơn chỉ số hop count trong mục bảng định tuyến. Nếu mục bảng định tuyến tới đích được tạo hoặc cập nhật, thì các hoạt động sau xảy ra: Tuyến được đánh dấu là hoạt động. Chỉ số thứ tự đích được đánh dấu là hợp lệ. Chặng tiếp theo trong mục tuyến được chỉ định từ nút mà từ đó RREP được nhận, được xác định bởi trừong địa chỉ IP nguồn trong mào đầu IP. Giá trị hop count được thiết lâpk là giá trị hop count mới. Thời gian hết hạn được thiết lập bằng thời gian hiện tại cộng với giá trị của Lifetime trong bản tin RREP. Và chỉ số thứ tự đích là chỉ số thứ tự đích trong bản tin RREP. Sau đó, nút hiện nay có thể sử dụng tuyến này để chuyển tiếp các gói dữ liệu tới đích. Nếu nút hiện tại không phải nút được xác định bởi địa chỉ IP nguồn trong bản tin RREP và một tuyến chuyển tiếp đã được tạo hoặc cập nhật như mô tả ở trên, nút tra cứu mục bảng định tuyến của nó cho nút khở đầu để xác định chặng tiếp theo cho gói RREP, và chuyển tiếp RREP theo hướng nguồn sử dụng thông tin trong mục bảng định tuyến. Nếu một nút chuyển tiếp một RREP qua một liên kết như là có lỗi hay là đơn hướng, nút nên thiết lập cờ A để yêu cầu nhận một báo nhận RREP của RREP bằng cách gửi một bản tin RREP- ACK quay lại. Khi bất kì nút nào truyền RREP, danh sách chặng trước cho đích tương ứng được cập nhật bằng cách thêm vào nó nút chặng tiếp theo mà ở đó RREP được chuyển tiếp. Cuối cùng, danh sách chặng trước cho chặng tiếp theo theo hướng đích được cập nhật để chứa chặng tiếp theo theo hướng nguồn. 3.3.8. Hoạt động qua các liên kết đơn hướng Việc truyền RREP có thể thất bại, đặc biệt nếu việc truyền này gây ra sự xuất hiện cảu RREP qua liên kết đơn hướng. Nếu không một RREP nào khác được tạo từ cùng khám phá tuyến, nút khởi đầu sẽ cố gắng thực hiện khám phá tuyến lại sau một thời hạn. Tuy nhiên, kịch bản tương tự có thể xảy ra và không có tuyến nào được tìm thấy mặc dù sau rất nhiều lần thử được lặp lại. Trừ khi hoạt động sử lỗi được chọn, điều này có thể xảy ra ngay cả khi các tuyến song hướng giữa nguồn và đích không tồn tại. Các lớp liên kết sử dụng truyền dẫn quảng bá cho RREQ sẽ không có khả năng phát hiện sự có mặt của những liên kết đơn hướng như vậy. Trong AODV, nút chỉ hoạt động trên RREQ đầu tiên và bỏ qua bất kì RREQ nào tiếp theo với cùng RREQ ID. Ví dụ, giả sử rằng RREQ đầu tiên đến dọc một tuyến mà có một hoặc nhiều hơn các liên kết đơn hướng. Một RREQ đến sau có thể đến qua một đường song hướng, nhưng nó sẽ bị bỏ qua. Để ngăn chặn vấn đề này, khi một nút phát hiện ra rằng sự truyền bản tin RREP của nó thất bại, nó sẽ nhớ chặng tiếp theo của RREP bị lỗi trong một danh sách đen được thiết lập. Như vậy, các sự thất bại có thể được phát hiện qua sự có mặt của một sự báo nhận lớp liên kết hay lớp mạng. Một nút bỏ qua tất cả các RREQ được nhật từ bất kì nút nào trong danh sách đen của nó. Các nút bị hủy bỏ từ danh sách đen sau một khoảng thời hạn BLACKLIST_TIMEOUT. Chú ý rằng gói RREP- ACK không chứa bất kì thông tin nào về RREP mà nó báo nhận. Thời điểm mà tại đó RREP- ACK được nhận sẽ có khả năng được đến ngay sau khi RREP được gửi với bit A được thiết lập. Thông tin này được mong đợi có khả năng cung cấp sự đảm bảo cho nút gửi RREP mà liên kết hiện tại là song hướng, bất kỳ sự phụ thuộc thực sự nào vào bản tin RREP đặc biệt được công nhận. Tuy nhiên, sự đảm bảo đó thường không thể được dự kiến vẫn có hiệu lực vĩnh viễn. 3.3.9 Bản tin Hello Một nút có thể cung cấp thông tin liên kết bằng việc quảng bá nội vùng các bản tin Hello. Một nút chỉ nên sử dụng các bản tin Hello nếu nó là một phần của tuyến hoạt động. Mỗi khoảng thời gian HELLO_INTERVAL (ms), nút kiểm tra xem nó đã gửi được một quảng bá hay không. Nếu nó không, nó có thể quảng bá một RREP với TTL = 1, được gọi là bản tin Hello, với các trường trong bản tin RREP được thiết lập như sau: Trường địa chỉ IP đích là địa chỉ IP của nút. Chỉ số thứ tự đích là chỉ số thứ tự cuối cùng của nút. Hop Count được thiết lập là 0. Lifetime = ALLOWED_HELLO_LOSS x HELLO_INTERVAL. Một nút có thể xác định liên kết bằng việc nghe đối với các gói từ các hàng xóm của nó. Nếu trong khoảng DELETE_PERIOD, nó đã nhận một bản tin Hello từ một nút hàng xóm, và sau đó nút hàng xóm đó không nhận được bất kì gói tin nào với khoảng thời gian lớn hơn ALLOWED_HELLO_LOSS x HELLO_INTERVAL, nút nên thừa nhận rằng liên kết tới hàng xóm này hiện tại bị mất. Mỗi khi một nút nhận bản tin Hello từ một hàng xóm, nút nên đảm bảo rằng nó có một tuyến hoạt động tới hàng xóm và có thể tạo tuyến nếu cần thiết. Nếu một tuyến thực sự tồn tại, thì thời gian Lifetime cho tuyến nên được tăng nếu cần thiết có thể ít nhất là ALLOWED_HELLO_LOSS x HELLO_INTERVAL. Tuyến tới hàng xóm, nếu nó tồn tại, sau đó phải chứa chỉ số thứ tự đích mới nhất từ bản tin Hello. Nút hiện nay có thể bắt đầu sử dụng tuyến này để chuyển tiếp các gói dữ liệu. Các tuyến mà được tạo bởi bản tin Hello và không được dùng bởi bất kì một tuyến hoạt động nào sẽ có một danh sách chặng trước trống rỗng và không thể gây ra một bản tin RERR nếu hàng xóm di chuyển ra xa. 3.3.10. Duy trì liên kết nội vùng Mỗi nút chuyển tiếp nên giữ vết của liên kết liên tục của nó tới các chặng tiếp theo hoạt động, cũng như các hàng xóm đã truyền các bản tin Hello trong suốt khoảng thời gian ALLOWED_HELLO_LOSS x HELLO_INTERVAL cuối cùng. Một nút có thể duy trì thông tin đảm bảo về liên kết liên tục của nó tới các chặng tiếp theo hoạt động này, sử dụng một hay nhiều liên kết sẵn sàng hoặc các kĩ thuật lớp mạng như được mô tả dưới đây. Bất kì sự khao báo lớp liên kết phù hợp nào như được cung cấp bởi IEEE 802.11 có thể được sử dụng để xác định liên kết, mỗi khi một gói được truyền tới một chặng tiếp theo hoạt động. Nếu khai báo lớp 2 không sẵn sàng, báo nhận bị động nên được sử dụng khi chặng tiếp theo được mong muốn để chuyển tiếp gói, bằng việc nghe từ kênh cho một sự cố gắng truyền được tạo ra bởi chặng tiếp theo. Nếu việc truyền không được phát hiện trong vòng NEXT_HOP_WAIT (ms) hoặc chặng tiếp là đích, một trong các phương pháp sau nên được sử dụng để xác định liên kết: Nhận một gói bất kì từ chặng tiếp theo. Gửi unicast một RREQ tới chặng tiếp theo, yêu cầu một tuyến tới chặng tiếp theo. Gửi unicast một bản tin ICMP Echo Request tới chặng tiếp theo. Nếu một liên kết tới chặng tiếp theo không thể được tìm thấy bằng các phương pháp này, nút chuyển tiếp nên thừa nhận rằng liên kết bị mất. 3.3.11 Các bản tin Route Error, sự hết hạn tuyến và sự xóa bỏ tuyến Thông thường, việc xử lý RERR và liên kết gãy cần đến các bước sau đây: Làm mất hiệu lực các tuyến hiện tại. Liệt kê các đích bị ảnh hưởng. Xác định rõ nếu có bất kì hàng xóm nào có thể bị ảnh hưởng. Thực hiện một RERR tới các hàng xóm như vậy Một bản tin RERR có thể là broadcast, unicast hay multicast. Ngay cả khi bản tin RERR là một unicast lặp lại tới một số chặng trước, nó được xem là một bản tin điều khiển đơn. Với cách hiểu đó, một nút không nên khởi tạo nhiều hơn một lượng RERR_RATELIMIT bản tin RERR trên một giây. Một nút bắt đầu xử lý cho một RERR trong ba hoàn cảnh sau: Nếu nó phát hiện một liên kết gãy cho chặng tới của một tuyến hoạt động trong bảng định tuyến của nó trong khi truyền dữ liệu. Nếu có được một gói dữ liệu đi đến một nút mà nó không có một tuyến hoạt động và không được sửa chữa. Nếu nó nhận một RERR từ một hàng xóm cho một hoặc nhiều tuyến hoạt động. Đối với trường hợp (i), đầu tiên nút tạo một danh sách các nút không tới được chứa các hàng xóm không tới được và bổ sung bất kỉ đích nào trong bảng định tuyến nội vùng cái mà sử dụng các hàng xóm không thể tới được như các chặng tiếp theo. Trong trường hợp này, nếu một tuyến mạng con được tìm thấy là khổng thể tới được, một đỉa chỉ IP đích cho mạng con này được thiết lập bằng việc chèn các số 0 vào tiền tố mạng con như được chỉ ra trong mục bảng định tuyến. Đối với trường hợp (ii), chỉ có một đích không thể tới được, cái mà là đích của gói dữ liệu mà không thể được phân phát. Trong trường hợp (iii), danh sách nên bao gồm các đích này trong RERR. Một vài đích không tới được trong danh sách có thể được sử dụng bởi các nút hàng xóm, và vì thế nó có thể cần thiết cho việc gửi một RERR. RERR nên chứa các đích đó là một phần danh sách được tạo ra của các đích khồng đến được và có một danh sách cách chặng trước không trống rỗng. Các nút láng giềng mà có thể nhận RERR là tất cả các nút thuộc về một danh sách chặng trước của ít nhất một đích không thể tới được trong RERR mới được tạo. Trong trường hợp có duy nhất một hàng xóm mà cần nhận RERR, RERR nên được truyền unicast theo hướng hàng xóm đó. Nếu không RERR được gửi quảng bá các địa chỉ nội vùng ( IP đích là 255.255.255.255 và TTL =1) với các đích không thể đến được, và chỉ số thứ tự đích tương ứng của các đích đó, được chứa trong gói tin. Trường DestCount của gói RER xác định số lượng các đích không tới được đã bao gồm tron gói tin. Ngay trước khi truyền RERR, những cập nhật đã chắc chắn được tạo trên bảng định tuyến mà có thể ảnh hưởng tới chỉ số thứ tự cho các đích không thể đến được. Đối với mỗi một đích này, các mục bảng định tuyến tương ứng được cập nhật như sau: Chỉ số thứ tự đích của mục định tuyến này, nếu hiện tại nó là hợp lệ, được tăng trong các trường hợp (i) và (ii) ở trên, và được sao chép từ RERR đến trong trường hợp (iii) ở trên. Mục được cho là không hợp lệ bởi sự đánh dấu của mục tuyến khi không hợp lệ. Trường Lifetime được cập nhật bằng thời gian hiện tại cộng với thời gian DELETE_PERIOD. Trước thời gian này, mục không nên được xóa. Chú ý rằng trường Lifetime trong bảng định tuyến đóng hai vai trò: đối với một tuyến hoạt động nó là thời gian hết hạn, và đối với một tuyến không hợp lệ nó là thời gian xóa. Nếu một gói dữ liệu được nhận cho một tuyến không hợp lệ, trường Lifetime được cập nhật bằng thời gian hiện tại cộng với thời gian DELETE_PERIOD. 3.3.12 Sửa chữa nội vùng. Khi một liên kết gãy trong một tuyến hoạt động tìm thấy, nút luồng lên của liên kết gãy này có thể chọn sửa chữa liên kết nội vùng nếu đích không xa hơn MAX_REPAIR_TTL chặng. Để sửa chữa liên kết gãy, nút tăng chỉ số thứ tự cho đích và sau đó quảng bá một RREQ cho đích đó. Trường TTL của RREQ nên được thiết lập ban đầu bằng giá trị như sau: TTL = max (MIN_REPAIR_TTL, 0.5 x #hops) + LOCAL_ADD_TTL. Với #hops là số lượng các chặng tới nút khởi đầu của gói tin không phân phát được hiện tại. Như vậy, sửa chữa nội vùng cố gắng sẽ thường xuyên ẩn tới nút khởi đầu và sẽ luôn có TTL >= MIN_REPAIR_TTL + LOCAL_ADD_TTL. Nút khởi đầu sửa chữa sau đó đợi trong khoảng thời gian khám phá để nhận các RREP hồi đáp tới RREQ. Trong suốt thời gian sửa chữa nội vùng, các gói dữ liêuk nên được nhớ đệm. Nếu, tại thời điểm cuối cùng của một thời gian khám phá, nút sửa chữa không nhận được một RREP cho đích đó, nó sẽ gửi một bản tin RERR đối với đích đó. Mặt khác, nếu nút nhận một hay nhiều RREP trong suốt thời gian khám phá, đầu tiên nó sẽ so sánh giá trị hop count của tuyến mới với giá trị trong trường hop count của mục bảng định tuyến không hợ lệ cho đích đó. Nếu giá trị hop count của tuyến được xác định mới nhất tới đích lơn hơn hop count của tuyến được biết trước đó, nút nên phát ra một bản tin RERR cho đích với bit N được thiết lập. Sau nó đõ cập nhận mục bảng định tuyến cho đích đó. Một nút mà nhận bản tin RERR với cờ N được thiết lập không được xóa bỏ tuyến tới đích đó. Chỉ nên thực hiện hành động truyền lại gói tin, nếu RERR được nhận từ chặng tiếp theo dọc tuyến đó, và nếu có một hoặc nhiều các nút chặng trước cho tuyến đó tới đích. Khi nút khởi đầu nhận một RERR với cờ N được thiết lập, nếu bản tin này đến từ chặng tiếp theo của nó dọc them tuyến của nó tới đích thì nút khởi đầu nên chọn khởi đầu lại khám phá tuyến. Sửa chữa nội cùng của các liên kết gãy trong các tuyến đôi khi cho kết quả là tăng độ dài tuyến tới các đích đó. Sự sửa chữa liên kết nội vùng có khả năng tăng số lượng các gói dữ liệu mà có thể được phân phát tới các đích, vì các gói sẽ không bị hủy bỏ khi RERR di chuyển tới nút khởi đầu. Việc gửi một RERR tới nút khởi đầu sau khi sửa chữa nội vùng liên kết gãy có thể cho phép nút khởi đầu tìm được một tuyến mới tới đích mà tốt hơn dựa trên vị trí nút hiện tại. Tuy nhiên, nó không yêu cầu nút khởi đầu xây dựng lại tuyến. Khi một liên kết gãy dọc một tuyến hoạt động, thường xuyên có nhiều đích mà trở nên không tới được. Nút mà là luồng lên của liên kết bị mất lập tức thử một sửa chữa nội vùng cho chỉ một đích theo hường mà gói dữ liệu được di chuyển. Các tuyến khác sử dụng cùng liên kết phải được đánh dấu là không hợp lệ, nhưng nút điều khiển sửa chữa nội vùng phải báo hiệu mỗi tuyến mất mới nhất khi sửa chữa nội vùng; cờ sửa chữa nội vùng này trong bảng định tuyến phải được đặt lại khi tuyến hết hạn. Trước khi thời gian hết hạn xảy ra, các tuyến khác này sẽ được sửa chữa khi cần thiết khi các gói đến các đích khác. Do đó, các tuyến này được sửa chữa khi cần; nếu một gói dữ liệu không đến tuyến nào, thì tuyến đó sẽ không được sửa chữa. Ngoài ra, tùy thuộc vào sự tắc nghẽn nội vùng, nút có thể bắt đầu xử lý thiết lập các sửa chữa nội vùng cho các tuyến khác, mà không đợi gói tin mới đến. Bằng việc sửa chữa tiên phong các tuyến mà đã gãy do mất liên kết, các gói dữ liệu đến cho các tuyến đó sẽ phải chịu sự trì hoãn sửa chữa tuyến và có thể ngay lập tức được chuyển tiếp. Tuy nhiên việc sửa chữa tuyến đường trước khi một gói dữ liệu được nhận có thể gặp phải rủi ro về việc các tuýên đường sửa chữa không còn tồn tại nữa. Vì vậy tùy thuộc vào lưu lượng nội vùng trong mạng và sự tắc nghẽn đang được trải qua, nút có thể quyết định sửa chữa tiên phong các tuyến hay không trước khi một gói dữ liệu được nhận; nếu không, nó có thể đợi cho đến khi một gói dữ liệu được nhận, và sau đó bắt đầu sửa chữa tuyến. 3.3.13 Các hoạt động sau khi khởi động lại Một nút tham gia trong mạng ad hoc chắc chắn phải thực hiện các hoạt động sau khi khởi động lại như nó có thể mất tất cả các bản ghi chỉ số thứ tự cho tất cả các đích, bao gồm chỉ số thứ tự của chính nó. Tuy nhiên, có thể có các nút hàng xóm mà đang sử dụng nút này như một chặng tiếp theo hoạt động. Điều này có thể có khả năng tạo các vòng lặp định tuyến. Để ngăn chặn khả năng này, mỗi nút trong quá trình khởi động lại chờ trong khoảng thời gian DELETE_PERIOD trước khi truyền bất kì một bản tin khám phá tuyến nào. Nếu nút nhận một gói điều khiển RREQ, RREP hoặc RERR, nó nên tạo các mục tuyến khi giữ thông tin chỉ số thứ tự thích hợp trong các gói điều khiển, nhưng không được chuyển tiếp bất kì gói điều khiển này. Nếu nút nhận một gói dữ liệu cho một vài đích khác, nó nên quảng bá một RERR và phải đặt thời gian chờ đến hết hạn sau khi cộng thêm thời gian DE:ETE_PERIOD hiện tại. Nó có thể được chỉ ra bởi thời gian mà nút được khởi động lại tới giai đoạn chờ và trở thành một nút hoạt động lại, không một hàng xóm nào của nó sẽ sử dụng nó như một chặng tiếp theo hoạt động nữa. Chỉ số thứ tự của nó được cập nhật một lần khi nó nhận một RREQ từ bất kì nút nào khác, khi một RREQ luôn mang chỉ số thứ tự đích lớn nhất được thấy trong tuyến. Nếu như không có RREQ được nhận, nút phải khởi tạo chỉ số thứ tự của nó là 0. 3.3.14 Các giao diện mạng Bởi vì AODV có thể hoạt động một cách linh hoạt qua các mạng có dây cũng như không dây, và bởi vì nó có khả năng được sử dụng bởi nhiều thiết bị không dây, giao diện cụ thể qua đó các gói đến phải được biết từ AODV mỗi khi một gói được nhận. Điều này bao gồm sự tiếp nhận các bản tin RREQ, RREP và RERR. Mỗi khi một gói được nhận từ một hàng xóm mới, giao diện trên đó mà gói đã được nhận được ghi vào mục bảng định tuyến cho hàng xóm đó, cùng với tất cả thông tin định tuyến tương ứng. Tương tự, mỗi khi một tuyến tới một đích mới được học, giao diện qua đó mà đích có thể tới được cũng được ghi vào trong mục bảng định tuyến cho đích này. Khi nhiều giao diện sẵn sàng, một nút truyền lại một bản tin RREQ quảng bá bản tin đó trên tất cả các giao diện mà đã được cấu hình cho hoạt động trong mạng ad hoc, trừ ra những cái mà trong đó nó được biết rằng tất cả các nút hàng xóm đã nhận RREQ. Ví dụ, đối với một vài phương tiện quảng bá (chẳng hạn Ethernet) nó có thể được cho rằng tất cả các nút trên cùng một liên kết nhận một bản tin quảng bá tại cùng một thời điểm. Khi một nút cần truyền một RERR, nó chỉ nên truyền trên các giao diện của nó mà có các nút hàng xóm nhận trước đó cho tuyến đó. IV.Giao thức định tuyến nguồn động DSR 4.1.Tổng quan về DSR Giao thức định tuyến nguồn động DSR (Dynamic Source Routing protocol) là một giao thức định tuyến đơn giản và hiệu quả được thiết kế sử dụng riêng cho các nút di động trong mạng không dây ad hoc multi- hop. Sử dụng DSR, mạng sẽ hoàn toàn tự động tổ chức và tự động cấu hình, tự yêu cầu mà không cần đến một cơ sở hạ tầng và quản trị mạng hiện đại. Các nút mạng chuyển tiếp các gói tới các nút khác bằng các kết nối cho phép qua multi-hop. Khi các nút di chuyển về, vào hoặc rời xa mạng, thì các trạng thái của đường truyền không dây như nguồn nhiễu sẽ thay đổi, tất cả các tuyến được tự động quyết định và duy trì bởi giao thức định tuyến DSR. Từ một số hay một chuỗi các chặng trung gian cần để đi đến một đích nào đó có thể thay đổi tại bất cứ thời gian nào, kết quả là topo mạng sẽ khá phong phú và thay thổi khá nhanh. Giao thức DSR cho phép các nút khám phá linh động từ một nút nguồn qua nhiều hop mạng để tới bất kì đích nào trong mạng ad hoc. Mỗi gói dữ liệu gửi đi sẽ mang trong nó một header đầy đủ, chứa danh sách các nút xuyên suốt mà gói dữ liệu phải vượt qua, tránh việc thiếu thông tin định tuyến tại các nút trung gian trong quá trình gói được gửi đi. Do trong mỗi header của gói dữ liệu đều bao gồm thông tin về nút nguồn, nêu khi các nút khác chuyển tiếp đi hoặc nhận được thông tin từ bất kì gói nào trong số các gói gửi nó cũng dễ dàng lưu giữ được thông tin định tuyến để sử dụng cho sau này. Giao thức định tuyến nguồn động DSR bao gồm hai cơ chế cùng thực hiện cho phép khám phá và duy trì của các phương pháp định tuyến nguồn động trong mạng ad hoc: Khám phá đường RD (Route Discovery) là cơ chế tìm đường khi nút S muốn chuyển một gói tin tớ nút đích D. Khám phá đường chỉ sử dụng khi mà nút S muốn gửi gói tin tới nút D mà chưa biết đường đi tới D. Duy trì đường RM ( Route Mantenance) là cơ chế mà khi nút S có một cách nào đó tự tìm thấy đường trong khi đường truyền đang sử dụng bị gián đoạn do cấu hình mạng bị thay đổi hoặc kết nối giữa các nút trong đường truyền đó không hoạt động. Khi RM chỉ ra rằng tuyến đến D bị đứt, S có thể cố gắng thử một đường nào khác để đến D hoặc có thể thực hiện lại cơ chế RD để tìm ra một đường mới. Duy trì đường RM chỉ được sử dụng khi S thực sự gửi gói tin tới D. Phát hiện đường và duy trì đường hoạt động hoàn toàn riêng rẽ theo các yêu cầu của nút. Thông thường, không giống như các giao thức khác, định tuyến nguồn động DSR không yêu cầu truyền định kì các gói của bất kì nhóm nào, mức độ nào trong phạm vi mạng. Ví dụ, DSR không sử dụng truyền định kì quảng bá đường, trạng thái hướng kết nối, hoặc sự nhận ra các gói hàng xóm, và không dựa vào các chức năng của các giao thức lớp dưới trong mạng. Các yêu cầu của nút này có cách hoạt động và thiếu các hoạt động định kỳ cho phép số lượng gói mào đầu sinh ra bởi DSR được sắp xếp trên tất cả các đường giảm xuống mức 0, khi tất cả các nút ở trạng thái ổn định với các nút cụ thể khác và tất cả các tuyến cần cho luồng kết nối vừa khám phá ra. Khi một số nút di chuyển nhiều hơn hoặc như sự thay đổi kiểu truyền thông, mào đầu gói định tuyến DSR tự động được sắp xếp để nắm bắt các tuyến đang được sử dụng. Trong sự đáp trả của một khám phá tuyến RD đơn ( như là qua thông tin định tuyến từ các gói mào đầu khác), một nút sẽ học và lưu trữ nhiều đường tới bất kì đích nào. Điều này cho phép đáp ứng được sự thay đổi tuyến nhiều và nhanh chóng, từ một nút với nhiều đường tới một đích có thể cố gắng truy cập bộ nhớ để tìm đường tới đích nếu như một tuyến nào đó bị lỗi. Bộ nhớ đệm các tuyến này cũng tránh cho các mào đầu cần thực hiện cơ chế khám phá tuyến mới mỗi khi tuyến sử dụng bị lỗi. Sự hoạt động của cơ chế RD và RM trong DSR được thiết kế cho phép kết nối đơn hướng và hỗ trợ dễ dàng các tuyến bất đối xứng. Cụ thể, trong các mạng không dây, nó có thể thực hiện được một kết nối giữa hai nút mà không thể thực hiện truyền cân bằng cả hai hướng hai hướng, vì những lí do như sự khác nhau giữa các anten, kiểu truyền hoặc các nguồn nhiễu. DSR cho phép sử dụng kết nối đơn hướng khi cần thiết, cải thiện hiệu suất nói chung và liên kết các mạng trong hệ thống. DSR cũng hỗ trợ ghép nối liên mạng giữa các loại mạng không dây khác nhau, cho phép một tuyến nguồn bao gồm nhiều chặng qua sự kết hợp của các kiểu mạng sẵn có. Ví dụ, một vài nút trong mạng ad hoc chỉ có duy nhất sóng vô tuyến phạm vi hẹp, trong khi những nút khác thì có cả sóng vô tuyến phạm vi hẹp và rộng; sự kết hợp giữa những nút này với nhau có thể được tính toán bởi DSR như một mạng ad hoc đơn. Thêm nữa, định tuyến nguồn động DSR có thể được tích hợp vào chuẩn định tuyến Internet, nơi mà các nút gateway kết nối tới Internet cũng tham gia trong các giao thức định tuyến của mạng ad hoc; và được tích hợp vào định tuyến Mobile IP, nơi mà các nút gateway cũng phục vụ vai trò của một nhà quản lý Mobile IP nước ngoài. 4.2.Vấn đề cơ bản của cơ chế xác định tuyến và duy trì tuyến 4.2.1 Vấn đề cơ bản của xác định tuyến Khi một vài nút S khởi đầu một gói tin mới định trước tới một vài nút D khác, trong phần mào đầu của gói tin chứa một tuyến nguồn lưu giữ chuỗi các chặng mà gói tin phải đi qua theo hướng đường đến đích D. Thông thường, S sẽ tìm được một tuyến nguồn phù hợp bằng cách tìm kiếm trong bộ nhớ đệm Route Cache của các tuyến trước đây nó học được, nhưng nếu không tìm thấy một tuyến nào trong bộ nhớ Cache nó sẽ phải thực hiện cơ chế khám phá đường RD để tìm ra đường mới tới D. Trong trường hợp này, ta gọi S là điểm khởi đầu và D là điểm kết thúc của cơ chế RD. Hình 3.1: Nút nguồn A thực hiện xác định tuyến tới đích E Ví dụ, hình 3.1 minh họa một ví dụ về cơ chế RD, trong đó nút A cố gắng xác định một tuyến tới nút E. Để bắt đầu xác định tuyến, A gửi một bản tin ROUTER REQUEST như một gói đơn quảng bá khu vực, cái mà được nhận bởi tất cả các nút trong phạm vi truyền không dây của nút A hiện tại. Mỗi bản tin RREQ cũng mang thông tin về điểm khởi đầu và điểm kết thúc của quá trình RD, và cũng bao gồm một request id duy nhất, được xác định rõ bởi điểm khởi đầu của bản tin. Mỗi bản tin RREQ cũng bao gồm một danh sách ghi chép địa chỉ của mỗi nút trung gian xuyên suốt quá trình bản tin RREQ được gửi đi. Bản định tuyến này ban đầu là một danh sách trống được tạo bởi điểm khởi đầu của cơ chế RD. Khi một nút khác nhận được bản tin RREQ, nếu nó là điểm kết thúc của RD, nó sẽ hổi đáp bằng bản tin ROUTER REPLY tới điểm bắt đầu của cơ chế RD, lưu giữ lại các tuyến tích lũy được từ bản tin RREQ; khi điểm khởi đầu nhậc được bản tin RREP này, nó lưu giữ tuyến này vào bộ nhớ đệm của nó để sử dụng cho việc gửi các gói tin sau đó tới đích. Trong trường hợp, nếu nút này nhận bản tin RREQ đã gặp mới đây được gửi từ điểm khởi đầu này và có cùng request id, hoặc nó tìm thấy địa chỉ của chính nó đã có trong danh sách chứa trong bản tin RREQ, nó sẽ loại bỏ yêu cầu này. Nếu không, nút này gắn thêm vào danh sách tuyến của bản tin RREQ địa chỉ của chính mình và quảng bá các gói bản tin RREQ tới các nút kế tiếp ( với cùng một chỉ số request id). Trong việc gửi ngược lại bản tin RREP đến nút khởi đầu xác định tuyến, chẳng hạn từ nút E hồi đáp về nút A trong hình 1, nút E sẽ nghiên cứu bộ nhớ đệm của chính nó để tìm ra một tuyến trở về A, và nếu tìm được, nó sẽ sử dụng tuyến đó làm tuyến nguồn để phân tán gói tin chứa bản tin RREP. Nếu không, E sẽ tự nó thực hiện một cơ chế xác định tuyến mới để tìm đường tới nút A, nhưng để tránh sự đệ quy vô thời hạn của xác định tuyến, nó phải mang thêm bản tin RREP này trong chính bản tin RREQ của nó gửi tới A. Nó cũng phải mang thêm những gói dữ liệu nhỏ khác như gói TCP SYN trên bản tin RREQ sử dụng cùng kĩ thuật này. Nút E cũng đảo ngược hoàn toàn chuỗi các chặng trong bản ghi tuyến trong bản tin RREQ mà nó đã nhận được để cố gắng gửi gói tin RREP và sử dụng nó như tuyến gốc trong gói tin mang chính bản tin RREP của nó. Đối với các giao thức MAC như IEEE 802.11 thì nó yêu cầu trao đổi một khung theo hai hướng trực tiếp như một phần của giao thức lớp MAC, tuyến đảo ngược này được ưu tiên hơn do nó tránh được mào đầu có thể có của xác định tuyến thứ hai, và nó kiểm tra được tuyến đã xác định ra để đảm bảo nó là hai hướng trực tiếp trước khi xác định tuyến của điểm khởi đầu bắt đầu sử dụng tuyến. Tuy nhiên, kĩ thuật này sẽ ngăn cản sự phám phá tuyến kết nối đơn hướng. Trong các môi trường vô tuyến nơi mà việc sử dụng kết nối đơn hướng được cho phép, như các tuyến mà trong một vài trường hợp thì việc sử dụng kết nối đơn hướng trực tiếp hiệu quả hơn so với việc kết nối hai hướng trực tiếp, hoặc nó chỉ có một đường duy nhất để kết nối tới nút đích. Khi bắt đầu khám phá tuyến, nút gửi sẽ lưu giữ một bản ghi của gói gốc trong vùng nhớ gọi là bộ nhớ đệm gửi Send Buffer. Bộ nhớ đệm gửi này chứa một bản ghi của mỗi gói cái mà nó không thể được truyền bởi nút này vì không có tuyến gốc tới đích của gói tin. Mỗi gói trong bộ nhớ đệm gửi được ghi vào thời gian mà nó được nhớ vào bộ nhớ đệm và bị hủy bỏ sau khi hết hạn tồn tại trong bộ nhớ đệm gửi trong một vài khe thời gian; nếu cần thiết ngăn cản bộ nhớ đệm gửi bị tràn, một FIFO hoặc một kế hoạch thay thế nào khác cũng có thể được sử dụng để truyền các gói đi trước khi nó hết hiệu lực. Trong khi một gói còn ở trong bộ nhớ đệm gửi, thì nút cần thỉnh thoảng phát động một cơ chế khám phá tuyến mới tới địa chỉ đích của gói tin. Tuy nhiên, nút phải giới hạn tốc độ phát động khám phá tuyến mới cho cùng một địa chỉ, vì nó có khả năng không thể đến đích. Cụ thể, do phạm vi truyền không dây bị giới hạn và các nút di chuyển trong mạng, mạng có thể bị chia cắt tại nhiều thời điểm, có nghĩa là hiện tại không có một chuỗi các nút xuyên suốt để có thể truyền một gói tới được đích. Tin tưởng vào hoạt động theo mẫu và sự đông đúc của các nút trong mạng, theo đó sự chia cắt trong mạng có thể là hiếm có và có thể là bình thường. Nếu một khá phá tuyến mới được phát động cho mỗi gói gửi bởi một nút như trong trạng thái, một số lượng lớn các gói RREQ không hữu ích có thể truyền bá rộng khắp các tập hợp con của mạng ad hoc từ nút này. Trong sự sắp xếp theo chiều hướng giảm xuống của mào đầu xuất phát từ các khám phá tuyến, chúng ta có thể sử dụng sự giảm dần theo hàm số mũ tới tốc độ giới hạn mà tại đó các khám phá tuyến mới có thẻ được phát động bởi bất kì nút nào đến cùng đích. Nếu nút cố gắng gửi thêm các gói dữ liệu đến cùng nút đích này thường xuyên hơn giới hạn, các gói đến sau sẽ được lưu giữ tại bộ nhớ đệm gửi cho đến khi một bản tin RREP được nhận, nhưng mà nút không được phát động một khám phá tuyến mới cho đến khi hết thời gian tối thiểu cho phép giữa các khám phá tuyến mới tới đích này. Sự giới hạn trong tốc độ lớn nhất của các khám phá tuyến cho cùng một đích tương tự như kĩ thuật quy định bởi các nút Internet tới tốc độ giới hạn mà tại đó các ARP REQUEST được gửi tới bất kì một địa chỉ IP đích nào. 4.2.2 Vấn đề cơ bản của duy trì tuyến Khi bắt đầu hay gửi một gói tin sử dụng một tuyến gốc, mỗi nút truyền gói tin có thể xác thực rằng gói tin đã được nhận bởi chặng kế tiếp dọc theo tuyến gốc hay chưa; các gói được truyền lại ( tới một số lượng lớn nhất có thể) cho đến khi được xác thực là đã được nhận. Ví dụ, trong minh họa ở hình 2, nút A phát động một gói tin tới nút E sử dụng một tuyến gốc xuyên suốt các nút trung gian là B, C và D. Trong trường hợp này, nút A có nghĩa vụ xác thực tại B, nút B có nghĩa vụ xác thực tại C, nút C có nghĩa vụ xác thực tại D và nút D cuối cùng có nghĩa vụ xác thực tại đích E. Sự ghi nhận xác thực này trong nhiều trường hợp có thể cung cấp không giá cho DSR, cái này như một phần tiêu chuẩn hiện tại của giao thức lớp MAC đang được sử dụng. Nếu các kĩ thuật xác thực không sẵn sàng, nút truyền gói tin có thể bố trí một phần nhỏ trong mào đầu gói tin đẻ yêu cầu một phần mềm đặc biệt của DSR công nhận sự phản hồi của chặng kế tiếp; phần mềm này công nhận đường truyền trực tiếp thông thường tới nút gửi, nhưng nếu kết nối giữa hai nút là đơn hướng trực tiếp, phần mềm có thể sẽ công nhận di chuyển qua một chặng khác, như đường nhiều chặng. Hình 3.2: Nút C không thể chuyển tiếp gói tin từ A đến E do liên kết giữa nó và D bị gãy Nếu gói tin được gửi lại bởi một vài chặng sau một lượng thời gian lớn nhất và không được xác thực là đã nhận, nút này sẽ gửi trả lại một bản tin ROUTE ERROR tới nút gốc của gói tin, chỉ ra rằng không thể chuyển tiếp gói tin. Ví dụ, trong hình 2, nếu C không thể gửi gói tin tới chặng kế tiếp D, thì C sẽ gửi một bản tin ROUTE ERROR tới A, chỉ ra rằng kết nối giữa C và D bị đứt. Nút A sau đó sẽ xóa bỏ liên kết bị gãy này khỏi bộ nhớ của nó; bất kỳ sự truyền lại nào của gói tin gốc đều là chức năng của các giao thức lớp cao hơn như TCP. Để gửi một sự truyền lại hay các gói tin khác đến cùng đích E, nếu A có trong bộ nhớ của nó một tuyến nào khác đến E ( ví dụ, từ các RREP của nó có được từ khám phá tuyến mới nhất, hoặc từ thông tin về tuyến đầy đủ trong mào đầu từ các gói khác), nó có thể ngay lập tức gửi gói tin sử dụng tuyến mới. Nếu không, nó có thể phát động một khám phá tuyến mới để tìm đường đến đích. 4.3.Định dạng mào đầu các lựa chọn DSR Giao thức định tuyến nguồn động DSR sử dụng một mào đầu đặc biệt mang thông tin điều khiển mà có thể chứa trong nó bất kì gói IP hiện tại nào. Mào đầu các lựa chọn DSR này trong một gói bao gồm một kích thước nhỏ cố định, theo sau là một chuỗi các số 0 hoặc nhiều lựa chọn DSR mang thông tin tùy ý. Kết thúc của chuỗi các lựa chọn DSR trong mào đầu các lựa chọn DSR được mặc định bởi tổng độ dài của mào đầu các lựa chọn DSR. Đối với IPv4, mào đầu các lựa chọn DSR phải theo ngay sau mào đầu IP trong gói. Để thêm một mào đầu các lựa chọn DSR vào một gói, mào đầu các lựa chọn được gài vào sau mào đầu gói tin IP, trước khi bất kì mào đầu nào theo như một mào đầu lớp vận chuyển truyền thống ( ví dụ TCP hoặc UDP). Trường giao thức trong mào đầu IP được sử dụng để chỉ ra rằng một mào đầu các lựa chọn DSR theo sau mào đầu IP, và trường mào đầu tiếp theo trong mào đầu các lựa chọn DSR được sử dụng để chỉ ra kiểu mào đầu giao thức theo sau mào đầu các lựa chọn DSR này ( như mào đầu lớp vận chuyển). Nếu bất kì mào đầu nào theo sau mào đầu các lựa chọn DSR trong một gói, tổng độ dài của mào đầu các lựa chọn DSR phải là một bội số của 4 octet. Luật lệ này bảo vệ sự liên kết của các mào đầu theo sau trong gói. 4.3.1 Sự phân chia cố định của mào đầu các lựa chọn DSR Sự phân chia cố định của mào đầu các lựa chọn DSR được sử dụng để mang thông tin mà phải có mặt trong bất kì mào đầu các lựa chọn DSR nào. Sự phân chia cố định của mào đầu các lựa chọn DSR được định dạng như dưới đây: Hình 3.3: Sự phân chia cố định mào đầu các lựa chọn DSR Next Header: 8 bit. Nhận biết kiểu mào đầu tiếp ngay sau mào đầu các lựa chọn DSR. Sử dụng cùng một giá trị như trường giao thức của IPv4. Nếu không có mào đầu nào theo sau thì Next Header phải có giá trị là 59, “No Next Header” F: Flow State Header- Mào đầu trạng thái luồng, là một flag bit. Bit này phải được thiết lập là 0. Nó được thiết lập trong một mào đầu trạng thái luồng và rõ ràng trong một mào đầu các lựa chọn DSR. Payload Length: Độ dài tải trọng. Độ dài của mào đầu các lựa chọn DSR, ngoại trừ phần 4 octet cố định. Giá trụ của trường độ dài tải trọng xác định tổng độ dài của tất cả các lựa chọn được mang trong mào đầu các lựa chọn DSR. Options: Trường các lựa chọn là trường có độ dài thay đổi. Độ dài của trường các lựa chọn được xác định bởi trường độ dài tải trọng trong mào đầu các lựa chọn DSR này. Bao gồm một hoặc nhiều mảnh của thông tin tùy ý (các lựa chọn DSR), được mã hóa trong định dạng type- length- value (TLV). Sự sắp xếp các lựa chọn DSR theo sau phần cố định của mào đầu các lựa chọn phải được lót đệm cho sự sắp hàng. Tuy nhiên, nhờ có đặc trưng băng thông không giây giới hạn cho phép trong các mạng ad hoc, việc đệm này không bắt buộc, và các nút nhận không phải mong đợi các lựa chọn trong vào một mào đầu các lựa chọn DSR được sắp hàng. Mỗi lựa chọn DSR được chỉ định một mã kiểu lựa chọn duy nhất. 3 bit quan trọng nhất (đó là kiểu tùy chọn & 0xE0) cho phép một node không triển khai thực hiện giá trị kiểu tùy chọn này để xử lý một cách gần đúng nhất kiểu đó: Các bit quan trọng nhất trong giá trị kiểu lựa chọn ( đó là kiểu tùy chọn & 0x80) có đại diện cho một nút nhận kiểu lựa chọn này hay không (khi một nút không thực hiện xử lý đối với kiểu lựa chọn này) nên hồi đáp tới một lựa chọn DSR với RERR của kiểu OPTION_NOT_SUPPORTED, không kể một RERR không bao giờ được gửi trong hồi đáp tới một gói bao gồm một lựa chọn RREQ. Hai bit theo sau trong giá trị kiểu lựa chọn ( đó là kiểu lựa chọn & 0x60) là một trường 2 bit chỉ ra một nút nào đó mà không hỗ trợ kiểu lựa chọn này phải xử lý gói: 00 = bỏ qua lựa chọn 01 = hủy bỏ lựa chọn 10 = đánh dấu lựa chọn 11 = hủy bỏ gói Khi hai bit này là 00 ( đó là kiểu lựa chọn & 0x60 = = 0), một nút không thực hiện xử lý đối với kiểu lựa chọn đó mà phải sử dụng trường độ dài dữ liệu lựa chọn để bỏ qua lựa chọn và tiếp tục xử lý. Khi hai bit này là 01 ( đó là kiểu lựa chọn & = = 0x20), một nút không thực hiện xử lý đối với kiểu lựa chọn đó và phải sử dụng trường độ dài dữ liệu lựa chọn để hủy bỏ lựa chọn từ gói tin và tiếp tục xử lý nếu như lựa chọn không được bao gồm trong gói tin nhận. Khi hai bit là 10 ( đó là kiểu lựa chọn & 0x60 = = 0x40), một nút không thực hiện xử lý đối với kiểu lựa chọn phải thiết lập bit quan trọng nhất theo sau trường độ dài dữ liệu lựa chọn, phải bỏ qua nội dung của lựa chọn sử dụng trường độ dài dữ liệu lựa chọn và phải tiếp tục xử lý gói tin. Cuối cùng, khi hai bit là 11 ( đó là, kiểu lựa chọn & 0x60 = = 0x60), một nút không thực hiện xử lý đối với kiểu lựa chọn đó phải hủy bỏ gói tin. Các kiểu lựa chọn sau đây của DSR được định nghĩa để sử dụng trong mào đầu các lựa chọn DSR: Lựa chọn ROUTE REQUEST Lựa chọn ROUTE REPLY Lựa chọn RUOTE ERROR Lựa chọn ACKNOWLEDGMENT REQUEST Lựa chọn ACKNOWLEDGMENT Lựa chọn tuyến nguồn DSR Lựa chọn Pad1 Lựa chọn PadN 4.3.2 Lựa chọn ROUTE REQUEST Lựa chọn ROUTE REQUEST trong một mào đầu các lựa chọn DSR được mã hóa như sau: Hình 3.4: Định dạng lựa chọn Route Request DSR Các trường của RREQ: Option Type: 1. Các nút không hiểu lựa chọn này sẽ bỏ qua lựa chọn này. Opt Data Len: Độ dài dữ liệu lựa chọn. Là độ dài của lựa chọn, trong các octet, ngoại trừ các trường Kiểu lựa chọn và Độ dài dữ liệu lựa chọn. Phải bằng (4 x n) + 6, với n là số lượng địa chỉ trong lựa chọn RREQ. Identification: Một giá trị duy nhất được thiết lập bởi nút khởi đầu bản tin RREQ. Các nút khởi đầu một RREQ thiết lập một giá trị Identification mới cho mỗi RREQ. Giá trị này cho phép một nút nhận có thể xác định xem là nó đã nhận một bản sao của RREQ này hay chưa. Nếu giá trị Identification này được tìm thấy bởi nút nhận trong bảng RREQ của nó, nó sẽ hủy bỏ RREQ này. Khi một RREQ được nhân giống, trường này phải được sao lại từ nút nhận RREQ trước khi được quảng bá tiếp. Target Address: Địa chỉ của nút mà là đích của RREQ. Address [1…n]: Address [i] là địa chỉ IPv4 của nút thứ i trong lựa chọn RREQ. Địa chỉ được giữ trong trường địch chỉ nguồn trong mào đầu IP là địa địa chỉ của nút khởi đầu khám phá tuyến và không được kê khai trong trường Address[i]; địa chỉ được giữ trong Address[1] là địa chỉ Ipv4 của nút đầu tiên trên đường sau nút khởi đầu. Số lượng các địa chỉ có mặt trong trường này được xác định bởi trường Độ dài dữ liệu lựa chọn trong lựa chọn ( n = (Opt Data Len- 6) / 4). Mỗi nút nhân giống RREQ thêm vào địa chỉ của nó trong danh sách, tăng giá trị Độ dài dữ liệu lựa chọn lên 4 octet. Lựa chọn RREQ không phải xuất hiện nhiều hơn một lần trong vòng mào đầu các lựa chọn DSR. 4.3.3 Lựa chọn ROUTE REPLY Hình 3.5: Định dạng lựa chọn Route Reply DSR Các trường trong lựa chọn này: Option Type: 2. Các nút không hiểu lựa chọn này sẽ bỏ qua lựa chọn này. Opt Data Len: Độ dài dữ liệu lựa chọn. Là độ dài của lựa chọn, trong các octet, ngoại trừ các trường Kiểu lựa chọn và Độ dài dữ liệu lựa chọn. Phải bằng (4 x n) + 1, với n là số lượng địa chỉ trong lựa chọn RREP. L: Last Hop External. Được thiết lập để xác định chặng cuối cùng được lưu giữ bởi RREP thực sự là một đường riêng trong một mạng lưới bên ngoài tới mạng DSR; tuyến chính xác bên ngoài mạng DSR không được trình bày trong RREP. Các nút nhớ lại chặng này trong bộ nhớ tuyến của nó phải đánh cờ chặng được nhớ này với cờ External. Như các chặng không được hồi đáp trong một RREP được lưu giữ phát ra từ mục bộ nhớ tuyến này, và sựa lựa chọn từ bộ nhớ tuyến một tuyến để gửi gói tin sẽ thích các tuyến mà không bao gồm các chặng được đánh cờ External. Reserved: Dự phòng. Address [1…n]: Tuyến nguồn được hồi đáp bởi RREP. Tuyến này xác định chuỗi các chặng, được khởi đầu tại nút nguồn trong trường địa chỉ đích của mào đầu IP của gói mang RREP, xuyên suốt mỗi nút có địa chỉ Address[i] trong danh sách được liệt kê trong RREP, kết thúc tại nút xác định bởi Address [n]. Số lượng các địa chỉ có mặt tronng trường Address[1…n] được xác định bởi trường độ dài dữ liệu lựa chọn trong lựa chọn (n= (Opt Data Len- 1) /4). Một lựa chọn RREP có thể xuất hiện một hoặc nhiều lần trong một mào đầu các lựa chọn DSR. 4.3.4 Lựa chọn ROUTE ERROR Lựa chọn RERR trong mào đầu các lựa chọn DSR được mã hóa như sau: Hình 3.6: Định dạng lựa chọn Route Error DSR Option Type: 3. Các nút không hiểu lựa chọn này sẽ bỏ qua lựa chọn này. Opt Data Len: Độ dài dữ liệu lựa chọn. Độ dài của lựa chọn, trong các octet ngoại trừ các trường Option Type và Opt Data Len. Đối với định nghĩa hiện tại của lựa chọn RERR, trường này phải được thiếp lập là 10, cộng với kích thước của bất kì thông tin chỉ định kiểu nào trong RERR. Hơn nữa, sự mở rộng định dạng lựa chọn RERR cũng có thể bao gồm phần thông tin chỉ định kiểu sau đó của lựa chọn RERR được chỉ định ở trên. Hiện diện của sự mở rộng đó được xác định bởi trường Opt Data Len. Khi một Opt Data Len lớn hơn phần cố định đòi hỏi của RERR cộng thêm thông tin chỉ định kiểu cần thiết như được xác đinh bởi giá trị của kiểu lựa chọn trong lựa chọn, các octet còn lại được hiểu như sự mở rộng. Hiện nay, chưa có sự mở rộng hơn được định nghĩa. Error Type: Hiện nay, giá trị các kiểu sau được định nghĩa là: 1 = NODE_UNREACHABLE 2 = FLOW_STATE_NOT_SUPPORTED 3 = OPTION_NOT_SUPPORTED Các giá trị khác của trường kiểu lỗi được dự phòng sử dụng trong tương lai. Reservd: Dự phòng Salvage: Được sao chép từ trường Salvage trong lựa chọn tuyến nguồn DSR của gói khởi hành RERR. “Total salvage count” của lựa chọn RERR được nhận từ giá trị trong trường Salvage của lựa chọn RERR và tất cả các lựa chọn RERR có trước trong gói như sau: total salvage count là tổng của mỗi lựa chọn RERR cộng với một giá trị trong trường Salvage của lựa chọn RERR đó. Error Source Address: Địa chỉ của nút khởi đầu RERR (ví dụ, nút mà đã cố gắng chuyển tiếp gói tin và phát hiện ra liên kết lỗi). Error Destination Address: Địa chỉ của nút mà từ đó RERR được thực hiện. Ví dụ, khi trường Error Tyoe được thiết lập là NODE_UNREACHABLE, trường này sẽ được thiết lập địa chỉ của nút mà đã phát thông tin tuyến yêu cầu mà chặng từ địa chỉ nguồn lỗi tới địa chỉ nút nguồn không thể tới được là một chặng hợp lệ. Type-Specific Information: Thông tin chỉ định của Error Type của bản tin RERR này. Một lựa chọn RERR có thể xuất hiện một hoặc nhiều lần trong