Giao thức định tuyến mạng
MANET


Mạng MANET
l Mobile Adhoc Network.
l Gồm các thiết bị di động, kết nối không dây
l Multi-hop routing


Thách thức trong định tuyến cho
mạng MANET
l Cần định tuyến động

¡ Topo thay đổi rất thường xuyên

l Cần giữ lượng thông tin điều khiển định tuyến
tối thiểu
¡ Wireless à băng thông thấp
¡ Mobile à năng lượng thấp
¡ Cần giảm thiểu số lượng các gói tin điều khiển định
tuyến
¡ Cần giảm thiểu lượng thông tin trạng thái lưu tại mỗi
nút.


Các giao thức định tuyến trong
mạng MANET
l Topology based routing

¡  Proactive approach, e.g., DSDV.

¡  Reactive approach, e.g., DSR, AODV, TORA.
¡  Hybrid approach, e.g., Cluster, ZRP.

l  Position based routing
¡  Location Services:
l DREAM, Quorum-based, GLS, Home zone etc.

¡  Forwarding Strategy:
l Greedy, GPSR, RDF, Hierarchical, etc.


Routing Protocols
l  Reactive (On-demand) protocols
¡ Khám phá đường đi khi cần
¡ Quá trình tìm kiếm được khởi tạo từ nguồn

l  Proactive protocols
¡ Tìm kiếm đường đi ngắn nhất theo các giao thức định tuyến
phân tán truyền thống
¡ Cần các quá trình cập nhật thông tin định tuyến thường
xuyên. Lượng thông tin điều khiển định tuyến lớn

l  Vấn đề cân đối giữa 2 phương pháp
¡ Thông lượng để cập nhật trạng thái vs. thông lượng để khám
phá đường đi
¡ Định tuyến dữ liệu theo các tuyến đường cũ vs. trễ khi khám
phá đường đi.


Reactive (on-demand) Routing

l Mục tiêu: Giảm routing overhead
l Không tạo trước một cấu trúc định tuyến
nào
l 2 phương pháp phát hiện đường đi
¡ Định tuyến nguồn
¡ Học ngược

l Nhược điểm: gây trễ do quá trình khám
phá đường.


Reactive (on-demand) routing:
l Định tuyến khi cần
Ưu điểm:

0

¡ Không cần các cập nhật định kỳ

query(0)
reply(0)

¡ Thích nghi với sự thay đổi
động của mạng

query(0)

1
query(0)


Nhược điểm:

3

reply(0)

2

query(0)

query(0)

4

query(0)
reply(0)

query(0)

5

l  Overhead do phát tán thông tin
khám phá lớn

¡ Độ trễ đến thời điểm tìm được
đường đi lớn.


Reactive Routing – Định tuyến
nguồn

l  Nguồn sẽ phát tán (kiểu ngập lụt) trong mạng bản
tin route request khi có yêu cầu về đường đi đến
một đích.
¡ Phát tán xuất phát từ nguồn
¡ Ngập lụt = mọi nút trong mạng đều nhận được yêu cầu
1 lần

l  Đích trả lời bằng cách gửi bản tin route reply
¡ Trả lời bằng cách sử dụng đường đi xác định bởi route
request
¡ Thiết lập đường chuyển dữ liệu

l  2 giao thức đặc trưng: DSR and AODV


Dynamic Source Routing (DSR)
l Cooperative nodes
l Relatively small network diameter (5-10 hops)
l Detectable packet error
l Unidirectional or bidirectional link
l Promiscuous mode (optional)


Route Discovery
B

RREQ FORMAT

A-B-D-G


A-B-D-G
A-B

A

Initiator ID

A-B-D-G

Target ID

A-B-D

D

A

Initiator seq#

G

Partial route

A-C-E
A

E

C


A-C

H
A-C-E
A-C-E
F

A-B-C
Route Request (RREQ)

A-B-C
Route Reply (RREP)

Route Discovery is issued with exponential back-off intervals.


Route Discovery: ở nguồn A
A need to send to G
Lookup Cache for route A to G
Start Route
Discovery
Protocol

wait
Route
Discovery
finished

no


Buffer
packet
Continue
normal
processing

Route
found
?

yes
yes

Packet
in
buffer
?

Write route in
packet header

no
don
e

Send
packet to
next-hop



Route Discovery: Ở nút trung gian
<src,id> in
recently
seen
requests
list?

Accept route
request
packet

yes

Discard
route
request

no
Host’s
address
already in
patrial
route
Append
myAddr to
partial route

Store <src,id>
in list
Broadcast packet


no

no
myAdd
r=targ
et

yes

Send route
reply packet

done

yes

Discard
route
request


DSR - Route Discovery
l  Route Reply chứa thông tin đường đi tìm được được
gửi bởi đích hoặc nút trung gian có đường đi bộ phận
đến đích
l  Mỗi nút chứa một Route Cache chứa các bản ghi
đường đi mà nuts này học được (nhận được) trong quá
trình hoạt động



Duy trì đường đi
l  Đường đi được duy trì chỉ khi nó vẫn đang được sử
dụng
l  Phát hiện lỗi:
¡ Kiếm soát tính hợp lệ của các đường đi đang có bằng cách
nghe thụ động các quá trình truyền dữ liệu của các nút
hàng xóm
¡ Nhờ cơ chế ACK của tầng thấp hơn.

l  Khi phát hiện có vấn đề, gửi bản tin Route Error về
nguồn để thực hiện một quá trình khám phá đường đi
mới.


Duy trì đường đi
B
RERR

RERR

G
D

G

A
Route Cache (A)
G: A, B, D, G
G: A, C, E, H, G

F: B, C, F

H

E

C
F


Tóm tắt về DSR
" Hoàn toàn on-demand, nói chung không gây overhead
" Loop-free
" source routing
" Hỗ trợ cả liên kết unidirectional và bidirectional.
" Có độ trễ truyền/jitters gây ra do on-demand routing
" Đòi hỏi không gian lưu trữ đường đi trong caches


AODV Routing Protocol
S

E
F

A

C
G
B


D

l  AODV = Ad Hoc On-demand Distance Vector
l  Nguồn gửi ngập lụt route request đi toàn mạng.
l  Đích D
l  Tuyến đường ngược về nguồn được xác định khi
một nút nhận được route request.
l  Mỗi nút chỉ forward gói tin request 1 lần (pure
flooding).


AODV Route Discovery
S

E
F

A

C
G
B

D

l  Nguồn gửi ngập lụt gói tin route request
l  Mỗi nút chỉ forward gói tin route request 1 lần (pure
flooding).



AODV Route Discovery
S

E
F

A

C
G
B

D

l  Reverse paths được tạo khi một nút nhận được một
gói route request.


AODV Route Discovery
S

E
F

A

C
G
B


D

l Route reply forwarded via the reverse path.


AODV Route Discovery
S

E
F

A

C
G
B

D

l Route reply được chuyển ngược về nguồn sử
dụng reverse path … do đó tạo lập forward
path
l Forward path được dùng để vận chuyển dữ
liệu từ nguồn đến đích sau này.


Vấn đề hết hạn của tuyến đường
S


E
F

A

C
G
B

D

l Đường đi không sử dụng sẽ hết hạn
theo timers.
¡ Đường đi được lưu trong bảng định tuyến
khi chưa hết hạn


AODV
l Một nút trung gian biết đường đi tới Đích sẽ
trả lời lại nguồn bằng cách gửi gói tin route
reply
¡ Giúp quá trình tìm đường đi diễn ra nhanh hơn.

l Tuy nhiên hình thức trả lời này có thể gây ra
lặp khi có các kết nối bị lỗi.
¡ Kết nối bị lỗi từ nút trung gian đến đích trong khi nút
này không biết.


AODV: Lặp do lỗi

A

B

C

D

E

l  Giả sử, C-D bị lỗi nút A không biết (do gói tin Route
error từ C bị mất).
l  C thực hiện route discovery tìm đường đến D.
l  Nút A nhận được RREQ (qua đường C-E-A)
l  Nút A trả lời vì A biết đường đi tới D qua B
l  Kết quả tạo ra đường đi có lặp từ C-D: C-E-A-B-C


AODV: Sử dụng Sequence Numbers
l Mỗi nút X có một số sequence number
¡ Hoạt động như một nhãn thời gian
¡ Seq# tăng mỗi khi X gửi một gói tin (có thể là RREQ
hoặc RREP)

l Mỗi tuyến đường đến X (tại nút Y) cũng có
Seq# là số Seq# mới nhất của X mà Y biết.
l Seq# thể hiện tính “tươi” của một tuyến
đường
¡ Càng lớn thì càng “tươi”