Luận văn Tìm hiểu ngôn ngữ mô hình hóa mạng và xây dựng bộ công cụ phát sinh Topology cho mạng

t đầu khởi động lại cơ chế Slow-Start. 3.4.3.1.2 TCP Reno TCP Reno (Agent/TCP/Reno) là một cải tiến của TCP Tahoe bằng cách đưa ra cơ chế Fast Recovery (phục hồi nhanh) kết hợp với cơ chế Fast Retransmit trong TCP Tahoe. Ý tưởng của Fast Recovery là một yêu cầu truyền lại (D-ACK) sẽ phải chỉ ra băng thông có thể dùng trong khung truyền từ khi một đoạn dữ liệu được phát đi thành công. Điều này có nghĩa rằng cwnd_ cần thực sự tăng lên mỗi khi phát đi một D-ACK. Sau khi gởi 94 đoạn được xem như là bị mất, Fast Recovery sẽ bắt đầu. Lúc đó, cwnd_ sẽ được tăng lên: cwnd_ = ssthresh_ + 3 MSS Sau đó, mỗi khi nhận D-ACK, cwnd_ sẽ tăng lên 1MSS. Cơ chế Fast Recovery được kích hoạt khi nhận được một số ngưỡng các D-ACK: bên gởi sẽ truyền lại một đoạn và gán các ngưỡng này giá trị bằng ½ giá trị của cwnd_ hiện tại. Kế đến, thay vì chuyển sang cơ chế Slow-Start như TCP Tahoe, bên gởi sẽ cộng thêm vào cwnd_ một số bằng với số ngưỡng. Sau đó, chừng nào bên nhận còn trong trạng thái Fast Recovery thì cwnd_ sẽ được cộng thêm 1 cho mỗi D-ACK được nhận. Fast Recovery chỉ được hoàn tất khi một ACK cho dữ liệu mới được nhận. Bên gởi sau đó sẽ gán cwnd_ bằng với giá trị của ngưỡng hiện tại và chỉnh lại số đếm D-ACK về giá trị ban đầu. 3.4.3.1.3 TCP Newreno TCP Newreno (Agent/TCP/Newreno) giải quyết được sự bất khả thi của TCP Reno đó là việc khắc phục lỗi khi có nhiều packet bị mất đồng thời. Nó sửa lại quá trình hoạt động của cơ chế Fast Recovery: trong quá trình Fast Recovery, nếu một “partial ACK” (thông báo không công nhận số byte liên tiếp cao nhất đã được nhận) được nhận, bên gởi sẽ xem nó như là dấu hiệu chỉ ra rằng đoạn kế tiếp tương ứng với thông báo đó đã bị mất. TCP Newreno sẽ truyền lại đoạn đó và đợi thông báo phản hồi tương ứng. Trạng thái Fast Recovery sẽ không kết thúc chừng nào mà byte được đánh số cao nhất được gởi đi trước khi phát hiện ra sự mất packet đầu tiên được thừa nhận. Khi điều này xảy ra, kích thước khung sẽ co lại bằng ssthresh_ và cơ chế tránh tắt nghẽn được lặp lại. 3.4.3.2 Một số TCP agent bên nhận TCPSink 95 TCPSink có nhiệm vụ trả về giá trị ACK mỗi khi nhận gói dữ liệu từ TCP bên gởi. Nó chỉ phát sinh một ACK cho mỗi packet nhận được. Kích thước của ACK có thể thay đổi đựoc. Các tham số cấu hình: Agent/TCPSink set packetSize_ 40 : thay đổi kích thước của packet. TCPSink/DelAck Đối tượng Delayed-ACK TCP Sink (Agent/TCPSink/DelAck) có thể gởi phản hồi một gói ACK sau khi đã nhận được vài packet. Đối tượng này chứa tham số interval_ để qui định thời gian chờ giữa hai lần truyền gói tin ACK. Các tham số cấu hình: Agent/TCPSink/DelAck set interval_ 100ms1 3.4.3.3 TCP agent hai chiều Để có thể tạo kết nối, TCP phải thực hiện việc bắt tay ba lần (3 way_ handshake): + Bên gởi gởi một gói SYN sang bên nhận. + Bên nhận gởi phản hồi một gói với SYN + ACK tương ứng. + Bên gởi sẽ gởi lại một gói ACK để chấp nhận kết nối. Sau đó dữ liệu sẽ được trao đổi với nhau. Các tham số cấu hình mặc định cho FullTcp: + Agent/TCP/FullTcp set segsperack_ 1. + Agent/TCP/FullTcp set segsize_ 536. + Agent/TCP/FullTcp set tcprexmtthresh_ 3. + Agent/TCP/FullTcp set iss_ 0. + Agent/TCP/FullTcp set nodelay_ false. + Agent/TCP/FullTcp set data_on_syn_ false. + Agent/TCP/FullTcp set dupseg_fix_ true. + Agent/TCP/FullTcp set dupack_reset_ false. + Agent/TCP/FullTcp set interval_ 0.1. 96 Ví dụ: Tạo một agent FullTcp: set src [new Agent/TCP/FullTcp] ;# create agent set sink [new Agent/TCP/FullTcp] ;# create agent $ns_ attach-agent $node_(s1) $src ;# bind src to node $ns_ attach-agent $node_(k1) $sink ;# bind sink to node $src set fid_ 0 ;# set flow ID field $sink set fid_ 0 ;# set flow ID field $ns_ connect $src $sink ;# active connection src to sink # set up TCP-level connections $sink listen ;# will figure out who its peer is $src set window_ 100; 3.4.4 Ví dụ minh họa Tạo một kết nối TCP giữa hai node n0 và n1 với n0 sử dụng TCP Tahoe và n1 sử dụng TCPSink. lớp TCP đại diện cho giao thức TCP ở bên node gởi dữ liệu. Nó sẽ gởi dữ liệu đến cho agent TCPSink và TCPSink sẽ xử lý tham số ACK để kiểm tra tính đúng đắn của gói dữ liệu: set ns [new Simulator] … set tcp [new Agent/TCP] ;# Khởi tạo agent TCP bên node gởi dữ liệu $tcp set fid_ 2 ;# set IP-layer flow ID set sink [new Agent/TCPSink] ;# Khởi tạo agent TCPSink bên node nhận $ns attach-agent $n0 $tcp ;# Thiết lập agent TCP cho node n0 $ns attach-agent $n1 $sink ;# Thiết lập agent TCPSink cho node n1 $ns connect $tcp $sink ;# Xác lập một kết nối TCP cho hai agent set ftp [new Application/FTP] ;# Tạo môt ứng dụng FTP $ftp attach-agent $tcp ;# Cài đặt ứng dụng FTP cho node n0 $ns at 2 "$ftp start" ;# Thực thi ứng dụng FTP tại thời điểm giây thứ 2 97 3.5 Ứng dụng trong NS-2: 3.5.1 Lớp Application Ứng dụng trong NS-2 được xây dựng bỡi lớp Application được cài đặt trong phần nhân của NS-2: class Application: public TclOject { public: Application(); virtual void send(int nbytes); virtual void recv(int nbytes); virtual void resume(); protected: int command(int argc, const char* const* argv); virtual void start(); virtual void stop(); Agent *agent_; int enableRecv_; // call Otcl recv or not int enableResume_; // call Otcl resume or not }; Bảng 3.3 Các phương thức của lớp Application Lớp Application cung cấp một số phương thức cơ bản cho quá trình hoạt động của một ứng dụng: send(), recv(), resume(), start(), stop(), một con trỏ trỏ đến giao thức ở tầng vận tải bên dưới mà nó kết nối. 3.5.2 Phân loại ứng dụng Trong NS-2 có hai loại ứng dụng cơ bản: + Ứng dụng phát sinh lưu lượng mạng (Traffic Generator). + Ứng dụng giả lập mạng (Simulated Applications). 98 Hình 3.5 Hai loại ứng dụng trong NS-2 3.5.2.1 Ứng dụng phát sinh lưu lượng mạng Loại ứng dụng này được xây dựng bỡi lớp TrafficGenerator: class TrafficGenerator : public: TrafficGenerator(); virtual double next_ virtual void init() virtual double interval() virtual int on() virtual void timeout(); virtual void recv() virtual void resume() protected: virtual void start(); virtual void stop(); double nextPkttime_; int size_; int running_; TrafficTimer timer_; 99 }; Bảng 3.4 Các phương thức của lớp TrafficGenerator Ứng dụng phát sinh lưu lượng mạng có thể chia làm ba loại: exponential, pareto và CBR. Đối tượng Exponential (Application/Traffic/Exponential) phát sinh lưu lượng mạng theo hai trạng thái ON/OFF. Ở trạng thái “ON”, các gói dữ liệu được phát sinh theo một tốc độ truyền không đổi. Ngược lại, trong trạng thái “OFF”, không phát sinh lưu lượng mạng. Các tham số cấu hình cho đối tượng: PacketSize_ : kích thước của gói dữ liệu. burst_time_ : thời gian trung bình trong ở trạng thái ON. idle_time_ : thời gian trung bình trong ở trạng thái OFF. rate_ : tốc độ gởi các gói dữ liệu. Đối tượng Pareto (Application/Traffic/Pareto) cũng phát sinh lưu lượng mạng theo hai trạng thái ON, OFF. Các tham số cấu hình: PacketSize_ : kích thước của gói dữ liệu. burst_time_ : thời gian trung bình trong ở trạng thái ON. idle_time_ : thời gian trung bình trong ở trạng thái OFF. rate_ : tốc độ gởi các gói dữ liệu. Đối tượng CBR (Application/Traffic/CBR) dùng để phát sinh các gói dữ liệu theo một tốc độ bit không đổi. Các tham số cấu hình: PacketSize_ : kích thước của gói dữ liệu. rate_ : tốc độ truyền dữ liệu. interval_ : khoảng thời gian giữa hai lần truyền dữ liệu. random_ : phát sinh tín hiệu nhiễu một cách ngẫu nhiên. Giá trị mặc định là off. maxpkts_ : số packet lớn nhất được truyền đi. 3.5.2.2 Ứng dụng giả lập mạng FTP ( Application/FTP ) là ứng dụng dùng để truyền tải các file qua mạng. 100 Các phương thức đã được cài đặt trong NS-2: attach-agent : gắn ứng dụng FTP lên agent vận tải. start : khởi động ứng dụng FTP. stop : ngừng ứng dụng. Tham số cấu hình: maxpkts : số gói dữ liệu lớn nhất được phát sinh ở bên gởi. Telnet : ( Application/Telnet ) dùng để phát sinh các gói dữ liệu theo một trong hai cách dựa vào biến interval_ . Mặc định , giá trị này bằng 0. 3.5.3 Các ví dụ minh họa Ví dụ 1 : Tạo ứng dụng phát sinh lưu lượng mạng: set src [new Agent/UDP] set sink [new Agent/UDP] $ns_ attach-agent $node_0 $src $ns_ attach-agent $node_1 $sink $ns_ connect $src $sink set e [new Application/Traffic/Exponential] $e attach-agent $src $e set packetSize_ 210 $e set burst_time_ 500ms $e set idle_time_ 500ms $e set rate_ 100k $ns_ at 0.0 "$e start" $ns_ at 100.0 "$e stop" Ví dụ 2 : Tạo ứng dụng giả lập mạng: set Tcp [new Agent/TCP] set Sink [new Agent/TCPSink] $ns_ attach-agent $node_0 $Tcp 101 $ns_ attach-agent $node_1 $Sink $ns_ connect $Tcp $Sink set App [new Application/FTP] $App attach-agent $Tcp $ns_ at 10 "$App start" $ns_ at 100 "$App stop" 3.6 Mạng không dây trong NS-2: Thành phần quan trọng nhất trong mô hình mạng không dây là MobileNode. Trong C++, lớp MobileNode được kế thừa từ lớp cha là lớp Node. Do đó, MobileNode có đầy đủ các đặc điểm của đối tượng Node, thêm vào đó là các đặc tính của Wireless như khả năng di chuyển tự do trong phạm vi của topology, có khả năng truyền và nhận tín hiệu vô tuyến. Điểm khác nhau quan trọng giữa Node và MobileNode là MobileNode không dùng khái niệm Link (liên kết có dây) để liên kết với các Node hay các MobileNode khác. Thay vào đó, MobileNode sử dụng sóng vô tuyến để liên kết với các MobileNode khác. Lớp Mobile được cài đặt trong cả C++ và OTcl: Các cài đặt phức tạp như việc di chuyển của MobileNode, việc cập nhật lại vị trí, duy trì cầu trúc mạng, … được viết bằng C++. Trong khi đó, việc cấu hình các thành phần trong MobileNode như địa chỉ Mac, Channel, Antenna, … được cài đặt trong OTcl. 3.6.1 Các thành phần cấu hình của một MobileNode Xem phần 3.3.2 ( Cấu hình Node ). 3.6.2 Tạo mô hình mạng không dây trong NS-2 Một MobileNode bao gồm các thành phần: Link Layer, Interface Queue, ARP, địa chỉ MAC, mô hình truyền của sóng vô tuyến, Card mạng, kênh truyền. Ngoài ra, còn có các thành phần khác: kiểu Antenna, loại giao thức định tuyến. Do đó, để tạo một mô hình mạng không dây, ta cần cấu hình cho MobileNode: set val(chan) Channel/WirelessChannel ;#channel type 102 set val(prop) Propagation/TwoRayGround ;#radio-propagation model set val(ant) Antenna/OmniAntenna ;#Antenna type set val(add) hierarchical ;#Addressing type set val(ll) LL ;#Link layer type set val(ifq) Queue/DropTail/PriQueue ;#Interface queue type set val(ifqlen) 50 ;#max packet in ifq set val(netif) Phy/WirelessPhy ;#network interface type set val(mac) Mac/802_11 ;#MAC type set val(adhocRouting) DSDV ;#ad-hoc routing protocol set val(x) 500 ;#X-cordinate set val(y) 500 ;#Y-cordinate set topo [new Topography] … set ns_ [new Simulator] … $ns_ node-config -adhocRouting $val(adhocRouting) \ -llType $val(ll) \ -macType $val(mac) \ -ifqType $val(ifq) \ -ifqLen $opt(ifqlen) \ -antType $opt(ant) \ -propInstance [new $opt(prop)] \ -phyType $opt(netif) \ -channel [new $opt(chan)] \ -topoInstance $topo \ -wiredRouting OFF \ -agentTrace ON \ -routerTrace OFF \ -macTrace OFF 103 Tiếp theo, tạo một mô hình mạng không dây với năm MobileNode theo cú pháp: set val(nn) 5 for { set j 0 } { $j < $val(nn)} {incr j} { set node_($j) [ $ns_ node ] $node_($i) random-motion 0 ;# disable random motion } 3.6.3 Tạo kịch bản chuyển động cho các Node Các MobileNode được thiết kế để chuyển động ba chiều ( X,Y,Z ). Tuy nhiên, trong công cụ giả lập này, thì chiều Z không được sử dụng ( Z=0 ), nên các MobileNode chỉ chuyển động theo hai chiều X, Y. Trong NS-2, có hai phương pháp để tạo sự chuyển động cho các MobileNode: + Khởi tạo vị trí ban đầu cho các MobileNode và khai báo địa chỉ đích mà các MobileNode di chuyển tới một cách tường minh. + Thiết lập cho các MobileNode di chuyển ngẫu nhiên. Phương pháp thứ nhất $node set X_ $node set Y_ $node set Z_ $ns at $time $node setdest Chú thích: Ban đầu, ta khởi tạo vị trí bắt đầu cho node với tọa độ (x1,y1,0). Sau đó, tại thời điểm “$time” giây, node sẽ bắt đầu di chuyển từ vị trí khởi tạo (x1,y1,0) đến vị trí đích (tọa độ ( x2 , y2 ,0 ) ) với vận tốc speed. Phương pháp thứ hai $node start Chú thích: MobileNode khởi tạo ngẫu nhiên cho vị trí ban đầu, vị trí đích và tốc độ di chuyển. 104 3.6.4 Giao thức định tuyến cho mạng không dây Giao thức định tuyến là một trong những thành phần quan trong trong cấu hình mạng Trong phạm vi của đề tài này, chúng tôi tập trung tìm hiểu các giao thức định tuyến đã được cài đặt trong công cụ giả lập mạng NS-2 sử dụng trong mạng MANET, bao gồm: TORA, DSDV, AODV, DSR. 3.6.4.1 Giới thiệu tổng quan Trong mạng Ad-hoc, giao thức định tuyến được chia thành ba loại: + Giao thức định tuyến kiểu Table-driven (Proactive). + Giao thức định tuyến kiểu On-Demand (Reactive). + Giao thức định tuyến kết hợp. Giao thức định tuyến kiểu Table-driven (Proactive) Trong kiểu giao thức định tuyến này, một node luôn luôn duy trì trong bảng định tuyến của nó thông tin định tuyến đến tất cả các node khác trong mạng. Thông tin định tuyến được phát broadcast trên mạng theo một khoảng thời gian qui định để giúp cho bảng định tuyến luôn cập nhật những thông tin mới nhất. Tuy nhiên, với những mạng mà các node di chuyển nhiều, hoặc các liên kết giữa các node bị đứt thì giao thức định tuyến proactive sẽ phải tìm kiếm hoặc sửa chữa các liên kết bị đứt, nhưng nếu các liên kết đó không sử dụng thì sẽ trở nên lãng phí tài nguyên, ảnh hưởng đến băng thông của mạng. Nên giao thức định tuyến này chỉ áp dụng trong các mô hình mạng MANET mà các node ít di chuyển. Các giao thức định tuyến theo kiểu Proactive: + Destination-Sequenced Distance Vector (DSDV). + Wireless Routing Protocol (WRP). + Global State Routing (GSR). + Clusterhead Gateway Switch Routing (CGSR). Giao thức định tuyến kiểu On-Demand (Reactive) Trong loại giao thức định tuyến này, các con đường đi sẽ chỉ được tạo ra nếu có nhu cầu. Khi một node muốn gởi dữ liệu đến một node đích, nó sẽ 105 khởi động tiến trình route discovery để tìm kiếm con đường đi đến đích. Sau khi một đường đi đã được xác lập, nó sẽ duy trì thông tin đó bằng tiến trình route maintenance cho đến khi hoặc node đích không thể truy cập hoặc con đường đi đó không còn hiệu lực. Với các cơ chế đó, giao thức định tuyến theo kiểu Reactive không phát broadcast các thay đổi của bảng định tuyến theo thời gian, nên tiết kiệm được tài nguyên mạng. Vì vậy loại giao thức này có thể sử dụng trong các mạng lớn, các node di chuyển nhiều. Các giao thức định tuyến dạng Reactive tiêu biểu: + Cluster Based Routing Protocol (CBRP). + Ad hoc On-Demand Distance Vector (AODV). + Dynamic Source Routing (DSR). + Temporally Ordered Routing Algorithm (TORA). + Associativity-Based Routing (ABR). + Signal Stability Routing (SSR). + Location Aided Routing (LAR). Giao thức định tuyến kết hợp(Hybrid) Trong kiểu định tuyến này, mạng được chia thành các zone. Mỗi node duy trì cả thông tin về kiến trúc mạng trong zone của nó và thông tin về các zone láng giềng. Điều đó có nghĩa là: giao thức Hybrid sử dụng giao thức định tuyến proactive trong zone của nó và giao thức định tuyến reactive giữa các zone. Do đó, đường đi đến mỗi node trong cùng một zone được xác lập mà không cần phải định tuyến ra ngoài zone, trong khi đó các tiến trình route discovery và route maintenance thì được sử dụng để tìm kiếm, duy trì đường đi giữa các node của các zone với nhau. Các giao thức định tuyến tiêu biểu sử dụng kiểu Hybrid: + Zone Routing protocol (ZRP). + Zone-based hierarchical link state (ZHLS) routing protocol. + Distributed dynamic routing algorithm (DDR). 106 Hình 3.6 Các giao thức định tuyến trong mạng MANET 3.6.4.2 Giao thức định tuyến TORA TORA (Temporally Ordered Routing Algorithm) là một giao thức định tuyến giải quyết được nhược điểm của các giao thức định tuyến truyền thống là phá bỏ được vòng lặp (loop-free) và có khả năng thích ứng cao với môi trường mạng có nhiều thay đổi dựa trên khái niệm “link reversal”, nó tìm kiếm thông tin về đường đi theo yêu cầu, cung cấp nhiều đường đi đến đích, xác lập đường đi một cách nhanh chóng. TORA ít sử dụng con đường đi tối ưu (tức là con đương đi ngắn nhất) mà nó thường sử dụng các con đường đi dài hơn nhằm để hạn chế việc phải tìm kiếm các con đường đi mới làm ảnh hưởng đến lưu lượng truyền trên mạng. Cách thức hoạt động của thuật toán TORA có thể diễn tả như thuật ngữ mô hình nước chảy từ node nguồn đến node đích của mạng các ống nước như trong mô hình mạng thực tế. Các ống nước đại diện cho liên kết giữa các node, giao điểm của các ống nước đại diện cho các node và nước trong ống đại diện cho các gói dữ liệu truyền đến đích. Mỗi node có một trọng số tới mỗi node đích được tính toán bỡi giao thức định tuyến. Nếu một ống nước giữa node A và node B bị chặn làm cho nước không thể chảy qua được, thì trọng số của node A được đặt trọng số lớn hơn các node láng giềng của nó và do đó nước sẽ chảy ngược trở ra node A (và chảy vào các node khác mà có thông tin định tuyến đến đích qua node A). 107 Hình 3.7 Mô hình nước chảy trong mạng với giao thức TORA Giao thức định tuyến TORA được sử dụng trong môi trường mạng di động có tính chất động cao, cung cấp nhiều đường đi khác nhau giữa hai node. Để làm được điều này, các node cần duy trì thông tin định tuyến đến các node láng giềng của nó. Giao thức định tuyến này thực hiện ba chức năng chính : + Tạo thông tin định tuyến. + Duy trì thông tin định tuyến. + Xóa bỏ thông tin định tuyến. Mỗi node trong mạng luôn duy trì một đồ thị không vòng có hướng (directed acyclic graph (DAG)) riêng cho mỗi node còn lại trong mạng. Khi một node muốn định tuyến đến một node đích cụ thể nào đó, nó phát broadcast một gói QUERY chứa thông tin về địa chỉ đích. Gói QUERY này được truyền trong mạng cho đến khi nó tìm được node đích hoặc một node trung gian mà có thông tin định tuyến đến node đích. Sau đó, node đích hoặc node trung gian đó sẽ phát broadcast một gói UPDATE chứa trọng số của nó đến node nguồn. Khi gói UPDATE truyền qua mạng, các node trong mạng mà nhận được gói UPDATE này sẽ cập nhật lại thông tin về trọng số của nó bằng cách đặt giá trị trọng số lớn hơn giá trị trọng số của node láng giềng mà đã nhận gói UPDATE trước đó. Điều này tạo ra một chuỗi các liên kết có hướng từ node gởi gói QUERY đến node gởi gói UPDATE trả lời. Khi một node khám phá rằng một 108 thông tin định tuyến đến một node đích không còn giá trị, nó sẽ điều chỉnh giá trị trọng số của nó bằng giá trị lớn nhất so với các node láng giềng của nó và phát gói UPDATE lên mạng. Nếu node mà có tất cả các láng giềng có trọng số bằng vô cùng đến node đích này, thì node sẽ bắt đầu khám phá thông tin định tuyến mới. Khi một node khám phá ra con đường đi mới, nó sẽ phát sinh một gói CLEAR để thiết lập lại trạng thái bảng định tuyến và xóa các con đường đi không còn hiệu lực. Hình 3.8 Các giá trị hop-count trong TORA Như đã đề cập ở trên, trong quá trình tạo và duy trì thông tin định tuyến, các node sử dụng giá trị hop-count để xác lập một DAG đến node đích. Sau đó, hướng của các liên kết được chỉ định dựa trên mối quan hệ giữa các node láng giềng. Khi các liên kết giữa các node trong một DAG bị đứt, thì cơ chế duy trì thông tin định tuyến (route maintenance) sẽ xác lập một DAG mới đến node đích. Sau đó, TORA sẽ phảt broadcast gói tin CLEAR qua mạng để loại bỏ thông tin định tuyến không còn giá trị đó. 3.6.4.3 Giao thức định tuyến DSDV DSDV (Destination-Sequenced Distance-Vector) là một biến thể của giao thức định tuyến distance vector theo kiểu proactive, dựa trên ý tưởng của thuật toán định tuyến kinh điển Bell-man-Ford với một chút cải tiến. Cải tiến mới của DSDV là sử dụng kỹ thuật đánh số sequence number. kỹ thuật này dùng để nhận ra các con đường đi không còn giá trị trong quá trình cập nhật bảng định tuyến, do đó sẽ tránh được vòng lặp trong quá trình định 109 tuyến. Mỗi node sẽ tăng số sequence number khi gởi thông tin về bảng định tuyến của nó cho các node khác trong mạng.Các cơ chế trong DSDV: Quản lý bản định tuyến Mỗi node luôn duy trì một bảng định tuyến đến tất cả các node khác trong mạng. Thông tin của một entry trong bảng định tuyến bao gồm: + Địa chỉ của node đích. + Số hop đến đích (hop-count ). + Next hop. + Số sequence number của node đích. Để đảm bảo cho bảng định tuyến luôn phù hợp với những thay đổi trong mạng thì các node phải thường xuyên cập nhật bảng định tuyến theo một khoảng thời gian nhất định hoặc khi mạng có sự thay đổi. Do đó, các node phải quảng bá thông tin định tuyến của nó cho các node khác trong mạng bằng cách phát broadcast những thay đổi trong bảng định tuyến của nó. Khi một node nhận gói tin cập nhật bảng định tuyến, nó sẽ kiểm tra số sequence number của gói tin cập nhật, nếu số sequence number trong gói tin cập nhật lớn hơn hoặc bằng với số sequence number trong bảng định tuyến và có số hop-count nhỏ hơn thì node đó sẽ cập nhật thông tin đó vào bảng định tuyến. Cách thức cập nhật bảng định tuyến: Bảng định tuyến cập nhật theo hai cách: + Cập nhật toàn bộ bảng định tuyến cho các node láng giềng và có thể truyền trong nhiều packet, gọi là full- dump. + Cập nhật các phần thay đổi trong bảng định tuyến của nó cho các node láng giềng và các thông tin thay đổi đó chỉ được gởi đi trong một packet. Cách cập nhật này gọi là incremental- update. Đối với một mạng Ad-hoc tương đối ổn định, thì kiểu cập nhật incremental-update sẽ thường được sử dụng để hạn chế lưu lượng truyền trên mạng. Trong khi đó, full-dump sẽ được sử dụng trong mạng ít có sự ổn định. 110 Quản lý sự thay đổi của Topology Khi một node di chuyển từ nơi này đến nơi khác thì các liên kết của nó với các node láng giềng có thể không còn hiệu lực. Khi node phát hiện rằng liên kết đến next hop của nó không còn tồn tại, thì đường đi thông qua next hop đó lập tức sẽ có hop-count là ∞ và số sequence number được tăng lên 1. Sau đó node sẽ phát broadcast thông tin đó cho tất cả các node trong mạng và các node sẽ cập nhật lại bảng định tuyến của mình. 3.6.4.4 Giao thức định tuyến DSR DSR (Dynamic Source Routing) là giao thức định tuyến đơn giản và hiệu quả được thiết kế riêng cho mạng MANET. DSR cho phép mạng tự động tổ chức và cấu hình mà không cần đến sự quản trị hoặc cơ sở hạ tầng sẵn có của mạng. Giao thức định tuyến DSR bao gồm hai cơ chế cơ bản: Route Discovery và Route Maintenance, nhờ hai cơ chế này mà các node có thể tìm và duy trì được các đường đi đến các node trong mạng. Một đặc tính nổi bật khác của DSR là nó sử dụng kỹ thuật định tuyến source routing, khi đó bên gởi sẽ biết toàn bộ thông tin đường đi đến đích, điều này giúp cho việc định tuyến trên mạng không bị hiện tượng vòng lặp (loop) làm tăng hiệu năng của mạng. Để định tuyến được thì trong header của packet lưu giữ thêm thông tin về source route. Thông tin về bảng định tuyến được lưu trong route cache. Khi một node trong mạng Ad hoc muốn gởi dữ liệu đến một node đích nó sẽ tìm kiếm thông tin trong route cache nếu chưa có thông tin về đường đi thì node nguồn sẽ khởi động tiến trình route discovery để tìm kiếm con đường đi đến đích. Cơ chế route discovery: Route Discovery cho phép các host trong mạng Ad hoc tìm kiếm đường đi đến đích một cách tự động thông qua các node trung gian. Tiến trình route discovery sẽ phát broadcast gói route request (RREQ) lên mạng. Ngoài các trường bình thường, Thông tin trong packet RREQ còn chứa một 111 số request ID_ là một số được tạo ra bỡi node nguồn và là số không trùng nhau. Khi một node nhận gói RREQ thì nó sẽ tiến hành kiểm tra thông tin trong RREQ như sau: 1. Nó kiểm tra xem đây có phải là lần đầu tiên nó nhận gói RREQ có địa chỉ đích và số request ID_ hay không? nếu không phải thì nó sẽ loại bỏ gói tin này và không xử lý. Ngược lại thì qua bước 2. 2. Nó kiểm tra trong trường source route của gói RREQ đã có địa chỉ của nó hay chưa? nếu đã tồn tại thì nó cũng sẽ loại bỏ gói tin đó và không xử lý gì thêm. Ngược lại thì qua bước 3. 3. Nó kiểm tra trong route cache của nó có đường đi đến node đích mà còn hiệu lực hay không? nếu có đường đi đến đích thì nó sẽ phản hồi lại cho node nguồn bằng gói route reply (RREP) chứa thông tin về đường đi đến đích và kết thúc tiến trình. Ngược lại qua bước 4. 4. Nó kiểm tra địa chỉ đích cần tìm có trùng với địa chỉ của nó hay không? nếu trùng thì nó cũng sẽ gởi lại cho node nguồn gói route reply (RREP) chứa