ĐẠI HỌC QUỐC GIA HÀ NỘI
KHOA CÔNG NGHỆ


NGUYỄN HOÀNG MINH


Phân tích hiệu suất TCP trên mạng không dây
không cấu trúc



LUẬN VĂN THẠC SỸ



Người hướng dẫn: PGS.TS. Vũ Duy Lợi




Hà nội - 2004

1
.
MỤC LỤC

MỞ ĐẦU
4
CHƢƠNG 1
MẠNG KHÔNG DÂY KHÔNG CẤU TRÚC
(MOBILE ADHOC NETWORKS – MANET)

1 Mạng không dây không cấu trúc
1.1 Khái niệm 7
1.2 Đặc trưng của mạng không dây không cấu trúc 8
1.3 Ứng dụng của mạng không dây không cấu trúc 9
2 Phân tích đánh giá hiệu suất mạng máy tính 10
2.1 Khái niệm hiệu suất 10
2.2 Công cụ mô phỏng NS-2 (network simulator) 12

CHƢƠNG 2
ĐỊNH TUYẾN TRONG MẠNG KHÔNG DÂY KHÔNG CẤU TRÚC
1.Nguyên tắc chung 15
2.Các thuật toán định tuyến 16

2.1 Định tuyến trước 16
2.2 Định tuyến theo yêu cầu 16
3.Phân tích đánh giá hiệu suất các giao thức định tuyến 18
3.1 Các đơn vị đo hiệu suất 19
3.2 Kết quả mô phỏng và những phân tích 19
3.2.1 So sánh hiệu suất của ba giao thức định tuyến AODV, DSR và DSDV 19
3.2.1.1 Kết quả mô phỏng 20
3.2.1.2 Phân tích các kết quả thu được 22
3.2.2 So sánh hiệu suất hoạt động của hai giao thức AODV và DSR với số lượng các
node và thời gian tạm dừng khác nhau 23
3.2.2.1 Kết quả mô phỏng 23
3.2.2.2 Phân tích các kết quả thu được 31
3.3 Nhận xét đánh giá kết quả mô phỏng 32




2
CHƢƠNG 3
GIAO THỨC TCP TRÊN MẠNG KHÔNG DÂY KHÔNG CẤU TRÚC
1. Điều khiển lƣu lƣợng TCP trong mạng không dây không cấu trúc 36
2. Một số ảnh hƣởng đối với TCP trong mạng không dây không cấu trúc 37
a) ảnh hưởng đứt kết nối 37
b) ảnh hưởng đường truyền không đối xứng 38
3. Cải tiến điều khiển lƣu lƣợng TCP trong mạng không dây không cấu trúc
a) TCP-Feedback 39
b) Thông báo rõ ràng lỗi đường truyền EFLN 40
c) Giao thức ATCP 40
d) Fixed-Retranmission Timeout 41
4. Phân tích hiệu suất giao thức TCP – ELFN trên mạng MANET 42

4.1 Môi trường và phương pháp mô phỏng 42
4.2 Thông lượng cực đại 42
4.3 So sánh hiệu suất TCP giữa TCP – Reno và TCP – ELFN 45
a) Thông lượng TCP – Reno 45
b) Nguyên nhân thông lượng của một số node giảm xuống cực tiểu 51
c) Thông lượng TCP – ELFN 53

KẾT LUẬN
59
TÀI LIỆU THAM KHẢO
61











3
MỞ ĐẦU

Ngày nay, Internet đã trở thành công nghệ mạng tiêu chuẩn, kết nối
mở các hệ thống tính toán và các mạng thông tin máy tính không đồng nhất.
Việc phát triển bùng nổ của các mạng Internet/Intranet, việc cung cấp các
dịch vụ thông tin về kinh tế, khoa học công nghệ, văn hoá giáo dục, xã hội,
ngày càng phong phú trên mạng cũng như xu thế tích hợp hầu hết các hệ

thống thông tin trong các hoạt động chính trị, kinh tế, xã hội trên giao diện
Web đã làm cho vấn đề thiết kế, xây dựng cơ sở hạ tầng mạng trên nền bộ
giao thức TCP/IP, còn gọi là cơ sở hạ tầng IP (IP Infrastructure), cũng như
việc phát triển và tích hợp các ứng dụng phong phú trên mạng trở nên hết
sức cần thiết. Kiến trúc mạng thông tin máy tính và ứng dụng được mô tả
trong Hình 1.



Hình 1: Kiến trúc mạng thông tin máy tính và ứng dụng

Hệ thống ứng dụng trên Internet bao gồm: các dịch vụ thông tin Internet cơ
bản như: dịch vụ Web, thư điện tử, dịch vụ truyền tệp FTP, dịch vụ đăng
nhập từ xa Telnet; hệ thống giao dịch trong các ngành tài chính, ngân hàng,
thị trường chứng khoán, dịch vụ du lịch như mua vé máy bay, mua vé tầu
hỏa, đặt thuê phòng khách sạn, ; các hệ thống cơ sở dữ liệu và các hệ
E-mail, Web,
FTP, Telnet
HÖ thèng
TP
HÖ thèng
CSDL
HÖ thèng
tÝnh to¸n

HÖ thèng hç trî øng dông
Bé giao thøc TCP/IP
Ethernet
10/100 Mbits
ATM

X.25/
Frame Relay
SDH
SONET

øng dông
M¹ng th«ng tin
m¸y tÝnh




4
thống thông tin điện tử trong các lĩnh vực quản lý điều hành Nhà nước
(chính quyền điện tử), sản xuất kinh doanh (kinh doanh điện tử), giáo dục,
đào tạo (thư viện điện tử, đào tạo qua mạng), y tế (khám chữa bệnh qua
mạng).
Hiện nay cùng với sự phát triển mạnh mẽ của các mạng truyền thông hữu
tuyến (wired networks), mạng truyền thông vô tuyến (wireless networks)
được phát triển và sử dụng ngày một rộng rãi vì những tính năng đơn giản,
cơ động vv. Mạng không dây(wireless network) được coi như một giải
pháp tiện lợi cho mạng LAN trong những văn phòng và những đơn vị vừa và
nhỏ. Hơn thế nữa, Internet không dây đã và đang được triển khai và ứng
dụng tại nhiều nước trên thế giới trong đó có cả Việt Nam. Mạng không dây
có thể chia thành hai loại :
- Mạng không dây có cấu trúc (Infrastructured networks) : Mạng bao
gồm một mạng hữu tuyến thông thường, có những Gateway để giao
tiếp với những trạm không dây di động trong mạng.
- Mạng không dây không cấu trúc (Infrastructureless networks) : Mạng
này còn được gọi là: Mobile wireless Ad hoc Network (MANET).

Mạng MANET bao gồm những trạm không dây di động được kết nối
“tạm” với nhau bằng kết nối không dây theo mô hình: máy tính – nối
– máy tính (computer to computer) mà không cần tới bất cứ một hạ
tầng cơ sở mạng nào cả [1,3,47].
-
Luận văn này đi sâu vào nghiên cứu hai vấn đề là:
a) Phân tích hiệu suất của các giao thức định tuyến trong mạng không
dây không cấu trúc (Mobile Ad hoc Networks - MANET).




5
b) Phân tích hiệu suất hoạt động của giao thức TCP-ELFN trong
mạng không dây không cấu trúc (Mobile Ad hoc Networks -
MANET).
Các phân tích trong luận văn này dựa trên kết quả mô phỏng máy tính
bằng công cụ NS -2 của phòng nghiên cứu quốc gia Lawrence Berkely
Laboratoy Hoa Kỳ.

Luận văn được tổ chức thành những mục sau: Mở đầu, đặt vấn đề và
trình bày khái quát công việc và ý nghĩa của luận văn. Chương một, trình
bày khái niệm cơ bản và ứng dụng của mạng không dây không cấu trúc
MANET. Tiếp đó trình bày phương pháp luận nghiên cứu, hệ mô phỏng NS
– 2. Chương hai, trình bày về định tuyến trong mạng MANET, nguyên tắc
hoạt động, và các thuật toán định tuyến. Tiếp đó trình bày kết quả mô phỏng,
những phân tích đánh giá hiệu suất hoạt động của ba giao thức định tuyến là:
AODV, DSDV và DSR. Chương ba, trình bày về giao thức TCP, những ảnh
hưởng của giao thức TCP đối với hiệu suất mạng, những cải tiến điều khiển
lưu lượng TCP trong mạng MANET. Tiếp đó trình bày những những phân

tích đánh giá hiệu suất hoạt động của giao thức TCP – ELFN (Explicit Link
Failure Notification).




6
CHƢƠNG 1
MẠNG KHÔNG DÂY KHÔNG CẤU TRÚC
(MOBILE ADHOC NETWORKS – MANET)

1.Mạng không dây không cấu trúc:
1.1/ Khái niệm
Một trong những công nghệ quan trọng của thông tin di động (Mobile
Communication) là công nghệ mạng không dây không cấu trúc (wireless
mobile ad hoc network - MANET)

Mạng không dây không cấu trúc, sau đây gọi tắt là mạng MANET, là
một tập hợp các thiết bị không dây di động độc lập, bình đẳng, được kết nối
một cách ngẫu nhiên, với một tổ chức kết nối bất kỳ, mà không cần bất cứ
một kết cấu hạ tầng kỹ thuật có sẵn nào hoặc một thực thể điều khiển truy
nhập (trung tâm) nào hỗ trợ. Số liệu được trao đổi giữa các trạm làm việc,
thiết bị nguồn và thiết bị đích, theo phương thức chuyển mạch gói. Các trạm
làm việc, bên cạnh việc thu thập và xử lý số liệu ứng dụng, điều khiển truy
nhập mạng theo một thuật toán nhất định, đồng thời còn là các thiết bị định
tuyến, và vì vậy, việc thiết kế và thực hiện các trạm này thường phức tạp
hơn các trạm làm việc thông thường khác. Mạng không dây không cấu trúc
được chia thành hai loại là: Mạng di động kiểu Ad hoc (MANET) và mạng
cảm biến (Wireless sensor). Mạng cảm biến Wireless sensor là một lớp mới
của mạng không dây không cấu trúc, được quan tâm và phát triển trong

những năm gần đây. Mạng gồm rất nhiều node cảm biến và có thể truyền
thông với nhau. Mỗi node được cấu tạo bởi module cảm biến (sensor) và
module truyền thông. Mạng có độ tin cậy cao trong những môi trường phức
tạp, khó dự đoán trước. Mạng cảm biến như một trung tâm dữ liệu. Mỗi
node trong mạng đều cập nhật và lưu trữ dữ liệu [5, 21].




7













Hình 2: Kiến trúc mạng MANET



1.2 Đặc trƣng của mạng không dây không cấu trúc
- Tổ chức kết nối động: các trạm làm việc di chuyển tự do và ngẫu
nhiên, và vì vậy, tổ chức kết nối mạng thay đổi một cách ngẫu nhiên, không

dự báo trước được.
- Băng thông bị giới hạn, dung lượng kênh truyền rất khác nhau: trong
mạng MANET, dung lượng kênh truyền thường nhỏ hơn rất nhiều dung
lượng kênh truyền trong mạng có kết cấu hạ tầng kỹ thuật. Hơn nữa, thông
lượng đạt được trong mạng MANET - do ảnh hưởng của các yếu tố như:
nhiễu, hiện tượng xuyên kênh, fading, phương thức đa truy nhập vào hệ
thống mạng, hiện tượng tắc nghẽn số liệu, , thường nhỏ hơn nhiều lần tốc
độ truyền số liệu (vô tuyến).
- Giới hạn về nguồn điện làm việc: các trạm làm việc di động đều sử
dụng acqui hoặc pin, và vì vậy, một trong các yêu cầu quan trọng thiết kế và
thực hiện các trạm làm việc di động này là tiết kiệm năng lượng điện làm
việc.
MH1
MH8
MH7
MH2
MH3
MH5
MH6
MH4
Asymmetrical link
symmetrical link
MH1
MH8
MH7
MH2
MH3
MH5
MH6
MH4

Asymmetrical link
symmetrical link




8
- Giới hạn về an toàn, bảo mật: các trạm làm việc di động dễ bị “nghe
trộm”, bị tấn công theo kiểu “từ chối dịch vụ” (denie-of-service),
1.3 Ứng dụng của mạng không dây không cấu trúc
Có rất nhiều ứng dụng của mạng MANET trong cuộc sống, hiện nay
MANET đang được phát triển như là một phần mở rộng của Internet.
MANET được nối với Internet thông qua những Gateway. Điều này thật tiện
lợi để người sử dụng có thể dùng những ứng dụng Internet phổ biến như là
e-mail, web, ftp vv.

MANET rất thích hợp cho những ứng dụng có tính hợp tác và cơ động
cao, đặc biệt là trong quân sự và trong việc ứng cứu khắc phục những thảm
hoạ, ví dụ : trên chiến trường việc triển khai một mạng thông tin hữu tuyến
là rất khó khăn, đôi khi là không thể. Nhưng với MANET thì thật tiện lợi khi
trên những thiết bị chiến đấu như là : xe tăng, máy bay vv được trang bị
những thiết bị tính toán di động và chúng được kết nối với nhau theo kiểu
Ad hoc. Khi đó hiệu quả chiến đấu sẽ rất cao và hệ thống thông tin thực sự
phát huy được tác dụng. Điều này cũng đúng trong những trường hợp triển
khai lực lượng kịp thời cứu hộ khắc phục thảm hoạ. Thông tin sẽ được trao
đổi kịp thời giữa các nhóm cứu hộ mà không cần một sự triển khai hệ thống
mạng nào cả [5].

Trong những năm tới đây, mục tiêu là mỗi xe ôtô sẽ được trang bị
máy tính. Mỗi máy tính này đều có những thiết bị truy cập Internet. Đây sẽ

là một ứng dụng rất quan trọng đối với cuộc sống của con người.







9



2. Phân tích đánh giá hiệu suất mạng máy tính
2.1. Khái niệm hiệu suất
Hiệu suất (performance) là khái niệm tổng quát xác định chất lượng hoạt
động của một hệ thống - xét từ góc độ của người sử dụng - về độ sẵn sàng
(availability), tính hiệu quả (effectivity), độ tin cậy (reliability) và độ an toàn
(security) của hệ thống đó (Hình 3-a). Hiệu suất được thể hiện, đối với thiết
bị phần cứng, bằng số lệnh trong một đơn vị thời gian MIPS; với hệ thống
chương trình ứng dụng là số lượng nhiệm vụ (task) giải quyết được trong
một đơn vị thời gian; đối với mức tổ chức là các thông số thể hiện tính thân
thiện sử dụng như thời gian đáp ứng, độ sẵn sàng phục vụ, giao diện người
dùng, ngôn ngữ lập trình,

Chất lượng hoạt động của một hệ thống phụ thuộc vào năng lực phục vụ của
hệ thống dưới ảnh hưởng của tải đầu vào, và được thể hiện bằng kết quả hoạt
động của hệ thống ở đầu ra (Hình 3-b). Hiệu suất của một hệ thống phụ
thuộc vào năng lực hoạt động của phần cứng (tốc độ tính toán của CPU, thời
gian truy nhập và dung lượng bộ nhớ làm việc và bộ nhớ ngoài, tốc độ và
phương thức vào/ra số liệu, ), phần mềm (khả năng hỗ trợ của hệ điều hành

đối với các chương trình ứng dụng để có thông lượng lớn), độ song song tính
toán của phần cứng, phần mềm cũng như mục tiêu của phương thức vận
hành (đối với một hệ thống tính toán ở chế độ hoạt động hỗn hợp giữa tương
tác với người dùng và xử lý theo lô chẳng hạn, thì thời gian phản ứng ngắn
được ưu tiên thực hiện hơn là số lượng tối đa các bài toán của lô được xử lý)
[17, 47].




10















Hình 3 : Đánh giá chất lượng hoạt động của hệ thống

Trong khuôn khổ luận văn này, hiệu suất của một hệ thống được hiểu theo
nghĩa hẹp là các tiêu chí xác định tính hiệu quả hoạt động của hệ thống một

cách định lượng. Đối với một hệ thống mạng máy tính, đánh giá hiệu suất
(performance evaluation) là xác định về mặt định lượng chất lượng phục vụ
của hệ thống mạng đó đối với việc chuyển tiếp (bao gồm truyền và chuyển
mạch) số liệu của các ứng dụng trên hệ thống mạng. Chất lượng chuyển tiếp
số liệu của một hệ thống mạng được xác định bằng các đại lượng như thông
lượng (throughput), nghĩa là: lượng số liệu (hữu ích) tính bằng bit, byte hoặc
gói số liệu được truyền tải trong một đơn vị thời gian; thời gian trễ (delay)

HW
Speed
MIPS
Capacity
Service rate
Throughput
(task pro time unite)
User friendships:
- Response time
- Availability
- Interfaces
- Progr. languages
Performance
(Effectivity, Reliability, Security)
O
S
Appl.
Organization
User
Level
Level
software

Load
System
a) Quality of service of system component b) Load – System Relationship
HW
Speed
MIPS
Capacity
Service rate
Throughput
(task pro time unite)
User friendships:
- Response time
- Availability
- Interfaces
- Progr. languages
Performance
(Effectivity, Reliability, Security)
O
S
Appl.
Organization
User
Level
Level
software
HW
Speed
MIPS
Capacity
Service rate

Throughput
(task pro time unite)
User friendships:
- Response time
- Availability
- Interfaces
- Progr. languages
Performance
(Effectivity, Reliability, Security)
O
S
Appl.
Organization
User
Level
Level
software
Load
System
Load
System
a) Quality of service of system component b) Load – System Relationship




11
và thay đổi thời gian trễ (delay variation) khi chuyển tiếp số liệu trên một hệ
thống mạng; xác suất xảy ra lỗi và thời gian xử lý, khắc phục lỗi;




2.2 Công cụ mô phỏng NS-2 (network simulator)
NS là hệ mô phỏng máy tính được xây dựng và phát triển bởi dự án
VINT của phòng thí nghiệm quốc gia Lawrence Berkeley National
Laboratory.

NS là một hệ mô phỏng có cấu trúc hướng đối tượng. Nó được xây
dựng trên hai ngôn ngữ là C++ và Otcl và được xây dựng theo cách có thể
được mở rộng bởi người dùng hay người dùng có thể “lập trình được” trên
nền của hệ mô phỏng NS. Với cách tiếp cận này thì ta có thể coi mỗi một
mô phỏng như một chương trình hơn là các mô hình cứng nhắc, tĩnh, không
thể thay đổi. Một mô phỏng gồm các đối tượng có thể cấu hình tuỳ thích để
có thể đạt được mục đích mô phỏng đề ra.

Do vậy những người thiết kế NS đã không chọn một ngôn ngữ duy
nhất để xây dựng môi trường mô phỏng, bởi sẽ có những đòi hỏi khác nhau
về chính mục đích của việc mô phỏng. Khi cần mô phỏng những tầng thấp
của mạng máy tính, xử lý ở mức độ byte hay tiêu đề của các gói tin thì cần
đòi hỏi một hiệu quả tính toán cao, và một ngôn ngữ biên dịch như C++ đáp
ứng được nhu cầu đó. Mặt khác, việc phải thay đổi cấu hình của một mô
phỏng để tìm ra một cấu hình tốt và hiệu quả lại yêu cầu ngôn ngữ script, ví
dụ như là Tcl.




12

Những người thiết kế đã khai thác mô hình lập trình phân chia ngôn

ngữ (trên hai ngôn ngữ), ở đó nhân của hệ mô phỏng được viết bằng C++ là
phần có tốc độ thực hiện cao, còn phần định nghĩa, cấu hình và điều khiển
mô phỏng được viết ngôn ngữ script Tcl. Cách tiếp cận này mang lại một
hiệu quả rất cao vì nó đã chia mục đích của việc mô phỏng thành những
phần nhỏ và giải quyết chúng bằng những ngôn ngữ phù hợp. Nó cung cấp
cho người lập trình mô phỏng khả năng sử dụng dễ hơn, mềm dẻo và linh
hoạt hơn.

Vì C++ là ngôn ngữ hướng đối tượng mà Tcl thì không nên ta phải
xây dụng những đối tượng macro bậc cao cho phù hợp với các lớp của C++.
Sau này, để đạt được một hệ thống sáng sủa hơn, mềm dẻo và mạnh hơn,
trong phiên bản thứ hai của mình, NS đã thay Tcl bởi một ngôn ngữ Tcl
hướng đối tượng là OTcl. Và để có sự liên kết gắn bó giữa hai ngôn ngữ đó,
ta cần có một ngôn ngữ làm cầu nối là TclCl là một ngôn ngữ mở rộng của
Tcl. Với sự thay đổi đó thì các đối tượng macro đã được thay bằng các lớp
OTcl và trở nên dễ sử dụng bởi tập hợp các phương thức của một lớp Otcl
được thiết kế gần gũi với người viết các script, tức là các người dùng. Điều
đó dẫn đến một kiến trúc phân tầng hỗ trợ nhiều tầng các khái niệm mô
phỏng. Ví dụ như các đối tượng bậc cao sẽ thể hiện toàn bộ kiến trúc của
mạng, và tập hợp các công việc trong mạng, trong khi đó các đối tượng bậc
thấp lại thể hiện được các khái niệm như phân kênh, hàng đợi,

Cùng với NS, Nam ( Netwoark Animator) và Xgraph là hai công cụ
để trực quan hoá những kết quả thu được từ NS. Khi NS thực hiên mô




13
phỏng, nếu chương trình mô phỏng của người dùng có các thao tác để xuất

ra các file dữ liệu *.nam thì những file đó là đầu vào của chương trình Nam,
và Nam thể hiện những phần của việc mô phỏng như là topology của mạng,
sự truyền tin, hỗ trợ việc xem xét các kết quả mô phỏng tại những thời gian
theo ý muốn Nếu chương trình mô phỏng của người dùng có các thao tác
xuất ra các file *.tr thì chúng sẽ là dữ liệu vào đối với Xgraph. Xgraph sẽ
nhận dữ liệu và vẽ ra những biểu đồ thể hiện những kết quả của công việc
mô phỏng.
NS được nhiều cá nhân và tổ chức ở nhiều nơi trên thế giới dùng để phục vụ
cho việc học tập và nghiên cứu mạng máy tinh. NS hỗ trợ các khía cạnh
khác nhau trong mạng máy tính. Từ các lớp mô phỏng cơ sở như là các
Node, các liên kết để tạo thành Topology của mạng, các gói tin, việc chuyển
tiếp các gói tin, độ trễ truyền dẫn, rồi đến lớp dùng để phân kênh các gói tin
nhằm mục đích hướng các gói tin đến các trạm xác định, các Agent xác
định. Rồi đến việc quản lý các hàng đợi tại các trạm trung chuyển, lập lịch
trình cho các gói tin, các thuật toán tránh tắc nghẽn, nâng cao hiệu suất
truyền tin. Trong NS, ngưòi dùng có thể mô phỏng các mạng LAN, mạng
không dây, thông tin vệ tinh, rồi các ứng dụng như là Ftp, Http, Webcache,
Telnet, dựa trên các Agent của tầng giao vận, trên các mô phỏng về kỹ thuật
chọn đường, các giao thức tầng giao vận,






14
CHƢƠNG 2
ĐỊNH TUYẾN TRONG MẠNG KHÔNG DÂY
KHÔNG CẤU TRÚC
1.Nguyên tắc chung

Một trong những thách thức lớn nhất đối với việc định tuyến trong
mạng di động kiểu ad hoc là tổ chức kết nối mạng thay đổi một cách ngẫu
nhiên, phụ thuộc vào sự di chuyển của các trạm làm việc kết nối trong mạng;
số lượng các trạm làm việc, đồng thời là các trạm định tuyến, có thể rất lớn,
thông tin định tuyến, vì vậy, luôn thay đổi, đòi hỏi các thuật toán định tuyến
phải được thiết lập một cách tin cậy, hạn chế đến mức tối đa việc trao đổi,
cập nhật thông tin định tuyến đối với các trạm làm việc, để có thể dành tối
đa băng thông có được cho việc trao đổi số liệu của các ứng dụng.
Có hai loại thuật toán định tuyến trong mạng di động kiểu ad hoc: a) Định
tuyến trước (proactive), và b) Định tuyến theo yêu cầu (reactive or on-
demand). Định tuyến trước cho phép các trạm làm việc cập nhật thường
xuyên bảng định tuyến của mình, nghĩa là: luôn có được thông tin định
tuyến đến mỗi trạm đích khác trong mạng, và vì vậy, sẵn sàng chuyển tiếp
các gói số liệu đến trạm đích khi có yêu cầu định tuyến. Để có được thông
tin định tuyến tức thời, đồng nghĩa với thời gian định tuyến nhỏ, các trạm
làm việc phải thường xuyên trao đổi, cập nhật thông tin định tuyến, khiến tải
số liệu trong mạng nói chung tăng, làm giảm thông lượng số liệu hữu ích
trong mạng. Ngược lại, định tuyến theo yêu cầu chỉ xác định thông tin định
tuyến đến trạm đích khi có yêu cầu định tuyến. Rõ ràng, trong trường hợp
này, để giảm thiểu thông tin định tuyến trao đổi, người ta phải trả giá bằng
thời gian định tuyến lớn, và vì vậy, các thuật toán định tuyến theo yêu cầu




15
không phù hợp với các ứng dụng thời gian thực ngày càng phổ biến trong
mạng.
Phần tiếp theo trình bày một số thuật toán định tuyến tới một đích (unicast
routing algorithms). Về các thuật toán định tuyến quảng bá (multicast

routing algorithms).

2.Các thuật toán định tuyến
2.1 Định tuyến trƣớc
Một trong các thuật toán định tuyến trước là thuật toán định tuyến
vector khoảng cách DSDV (Destination-Sequenced Distance-Vector), dựa
trên thuật toán định tuyến Ballman-Ford. Mỗi trạm làm việc thường xuyên
cập nhật bảng định tuyến của mình với thông tin đường đi và số chặng tới tất
cả các trạm đích trong mạng. Thông tin định tuyến tới mỗi trạm đích
(routing entry) được gán một số tuần tự của trạm đích đó. Số tuần tự này
giúp các trạm làm việc phân biệt thông tin định tuyến cũ (stale route) với
thông tin định tuyến mới, từ đó giúp ngăn chặn việc hình thành đường đi
vòng lặp (routing loop) đối với mỗi trạm đích. Thông tin định tuyến được
phát quảng bá định kỳ trong mạng để giúp các trạm cập nhật bảng định
tuyến của mình.
Để hạn chế thông tin định tuyến trao đổi trong mạng, người ta thực hiện
phương thức quảng bá thông tin định tuyến như sau: a) Quảng bá toàn bộ nội
dung bảng định tuyến (full dump) mỗi khi trạm làm việc di chuyển (không
định kỳ); b) Chỉ quảng bá định kỳ những thông tin định tuyến mới thay đổi
so với lần quảng bá toàn bộ nội dung bảng định tuyến (full dump) trước
(incremental dump) [5, 6].

2.2 Định tuyến theo yêu cầu




16
Thuật toán định tuyến theo nguồn động (Dynamic Source Routing)
thuộc loại thuật toán định tuyến theo yêu cầu. Định tuyến theo nguồn nghĩa

là: thông tin định tuyến do trạm nguồn xác định, và được chuyển cùng với
gói số liệu. Dọc đường đi, các trạm làm việc chuyển tiếp gói số liệu đến trạm
đích căn cứ vào thông tin định tuyến được lưu giữ trong trường thông tin
định tuyến của bản thân gói số liệu đó.
Thông thường, mỗi khi có yêu cầu định tuyến một gói số liệu đến một trạm
đích, trạm làm việc điền thông tin định tuyến có trong bảng định tuyến vào
trường định tuyến của gói số liệu và chuyển đi trong mạng. Trong trường
hợp không tìm thấy thông tin định tuyến trong bảng định tuyến, trạm làm
việc khởi động quá trình tìm đường (path discovery), bằng cách phát quảng
bá gói số liệu "yêu cầu tìm đường", trong đó chứa địa chỉ trạm đích, địa chỉ
trạm nguồn và một từ định danh. Các trạm làm việc nhận được yêu cầu tìm
đường xử lý như sau: a) nếu biết thông tin định tuyến đến trạm đích thì điền
các thông tin này vào trường định tuyến của gói số liệu trả lời và gửi trở lại
trạm có yêu cầu định tuyến; b) trong trường hợp ngược lại, trạm làm việc
điền địa chỉ của mình vào trường định tuyến và chỉ gửi trên tất cả các đường
ra, nếu gói số liệu này chưa được "nhìn" bởi trạm này và địa chỉ của trạm
này chưa có trong trường định tuyến của gói số liệu. Trạm đích nhận được
gói số liệu "yêu cầu tìm đường" với các thông tin định tuyến từ trạm nguồn
đến trạm đích, điền các thông tin này vào trường định tuyến của gói số liệu
trả lời và gửi trở lại trạm có yêu cầu định tuyến.
Trạm làm việc hoặc trạm đích gửi gói số liệu trả lời cho trạm có yêu cầu
định tuyến bằng nhiều cách: a) gửi thông thường cho một trạm đích khi có
đầy đủ thông tin định tuyến; b) nếu đường truyền "yêu cầu tìm đường" là
đường truyền đối xứng, nghĩa là, đường truyền có khả năng trao đổi số liệu
hai chiều, thì sử dụng chính đường truyền này để gửi lại trạm nguồn; c) nếú




17

cả hai khả năng trên đều không thực hiện được thì khởi động quá trình tìm
đường đến trạm nguồn như mô tả ở trên.
Bảng định tuyến được cập nhật mỗi khi có một đường mới được xác định, và
thông tin định tuyến mới được bổ sung vào bảng định tuyến, hoặc một hay
nhiều chặng bị lỗi, và tất cả thông tin định tuyến đến trạm đích có chứa
chặng bị lỗi đều bị loại bỏ khỏi bảng định tuyến. Mỗi khi phát hiện một hoặc
nhiều chặng (link) bị lỗi (mức liên kết số liệu), trạm làm việc quảng bá
thông tin lỗi nói trên trong gói số liệu thông báo lỗi (route error packet) để
các trạm làm việc cập nhật bảng định tuyến của mình [5, 6].

3.Phân tích đánh giá hiệu suất các giao thức định tuyến
Trong môi trường truyền thông không dây, di động. Có rất nhều yếu
tố ảnh hưởng tới hiệu suất hoạt động của mạng. Các nhân tố này tiềm ẩn chủ
yếu tại bốn tầng cuối trong mô hình hệ thống mở bảy mức OSI. Đó là các
tầng: tầng vật lý (physic layer), tầng liên kết dữ liệu (MAC), tầng mạng
(network), và tầng giao vận (transport). Với môi trường truyền thông bằng
sóng vô tuyến hiệu suất mạng sẽ bị giảm bởi những yếu tố là: ảnh hưởng của
nhiễu (noise), sự giảm năng lượng sóng mang (fading), băng thông hẹp
(IEEE 802.11b là 11Mbps). Tại tầng mạng (network layer), với đặc trưng
của mạng MANET là các trạm trong mạng hoạt động như chức năng của bộ
định tuyến (router) mạng MANET trở thành mạng Multi – Hop. Vậy nên vai
trò của các giao thức định tuyến là rất quan trọng. Trong mạng không dây
không cấu trúc, hiện tượng mất kết nối thường xuyên xảy ra, các thuật toán
tìm đường luôn được kích hoạt để tìm ra những con đường mới. Vậy nên
hiệu suất hoạt động các giao thức định tuyến có ảnh hưởng rất lớn tới hiệu
suất của mạng [2, 3, 21, 28].





18
Phần dưới đây trình bày những kết quả mô phỏng hoạt động của ba
giao thức định tuyến là AODV, DSDV và DSR. Tiếp đó trình bày những
phân tích đánh giá hiệu suất hoạt động của ba giao thức trên.



3.1 Các đơn vị đo hiệu suất.
- Tỷ lệ gói tin tới đích (Packet delivery fraction - PDF)
Tỷ lệ của số lượng các gói tin tới đích trên tổng số gói tin được phát đi.
- Độ trễ truyền tin (Average end – to – end delay of data packet)
Tổng thời gian trễ do quá trình tìm đường, thời gian chờ trong hàng đợi của
tầng MAC, thời gian trễ do truyền lại các gói tin bị mất, thời gian phát và
truyền tin.
- Chi phí định tuyến (Normalized routing load)
Tỷ lệ số lượng các gói tin định tuyến đối với số lượng các gói tin dữ liệu
nhận được tại trạm đích (receiver).

Trong các đơn vị đánh giá hiệu suất nêu trên, hai đơn vị đầu tiên là: Tỷ lệ
gói tin tới đích (Packet delivery fraction - PDF) và Độ trễ truyền tin
(Average end – to – end delay of data packet) là quan trọng hơn. Đơn vị đo
thứ ba: Chi phí định tuyến (Normalized routing load) chỉ nhằm đánh giá
thêm về tác động của giao thức định tuyến đối với hiệu suất TCP.

3.2 Kết quả mô phỏng và những phân tích.
3.2.1 So sánh hiệu suất hoạt động của ba giao thức định tuyến AODV,
DSR và DSDV.





19
Mô phỏng thực hiện đối với ba giao thức định tuyến là AODV, DSR,
và DSDV. Kết quả dưới đây được rút ra từ 50 lần chạy mô phỏng với những
tham số là: 20 nguồn node, di chuyển trong phạm vi 500x500 met. Thời gian
tạm dừng(pause time) của các node là 0, 10, 20,30, 100 giây(thời gian tạm
dừng của các node >= 100 giây thì các node được coi là đứng yên) thời
gian tạm dừng của các node thể hiện tính ổn định tạm thời Topology của
mạng . Mô phỏng này nhằm mục đích so sánh hiệu suất hoạt động của TCP
trên ba giao thức định tuyến. Để từ đó có thể lựa chọn những giao thức định
tuyến có hiệu suất hoạt động cao hơn.

3.2.1.1 Kết quả mô phỏng






%%
%%

Packet Delivery Fraction (PDF)
0
10
20
30
40
50
60

70
80
90
100
0 10 20 30 40 50 60 70 80 90 100
Pause time (secs)
Packet delivery fraction (%)
AODV, 20 sources
DSR, 20 sources
DSDV, 20 sources




20
Hình 4 - Biểu đồ so sánh tỷ lệ gói tin tới đích (PDF) của các giao thức
định tuyến AODV, DSDV và DSR




















Hình 5 - Biểu đồ so sánh độ trễ truyền tin (Average end – to – end
delay of data packet) của các giao thức định tuyến AODV, DSDV và
DSR




Average End-End delay
0
0.05
0.1
0.15
0.2
0.25
0.3
0.35
0.4
0 10 20 30 40 50 60 70 80 90 100
Pause time (secs)
Average delay (secs)
AODV, 20 sources
DSR, 20 sources
DSDV, 20 sources





21










3.2.1.2 Phân tích các kết quả thu đƣợc
A/ So sánh tỷ lệ gói tin tới đích (PDF) : Theo số liệu mô phỏng và ta
có thể quan sát trong hình 4 thì trong các trường hợp mạng có thời gian tạm
dừng của các node(pause time) lớn có nghĩa là các node ít di chuyển,
Topology mạng ít thay đổi thì tỷ lệ các gói tin tới đích của cả ba giao thức
định AODV, DSR, DSDV đều đạt xấp xỉ 100%. Đối với trường hợp mạng
có thời gian tạm dừng của các node là nhỏ, các node di chuyển liên tục, thì
tỷ lệ các gói tin tới đích (PDF) của ba giao thức định tuyến trên có sự khác
biệt rõ ràng. Tỷ lệ gói tin tới đích của giao thức AODV, trung bình là 95%.
PDF của giao thức DSR là xấp xỉ 90%, còn của DSDV là khoảng 75%.
Điều đó chứng tỏ rằng tỷ lệ các gói tin tới đích (PDF) phụ thuộc nhiều vào
điều kiện di chuyển của các node trong mạng. Đối với những mạng mà có
các node di chuyển liên tục thì các giao thức định tuyến loại On-Demand có
tỷ lệ các gói tin tới đích vượt trội hơn hẳn so với các giao thức định tuyến
loại proactive.
B/ So sánh độ trễ truyền tin(Average End-End Packet Delivery): Độ

trễ truyền tin(Average End-End Packet Delivery) của ba giao thức định




22
tuyến AODV, DSR, và DSDV có sự trênh lệch đáng kể khi các node trong
mạng di chuyển liên tục(thời gian tạm dừng nhỏ). Giao thức AODV có độ
trễ trung bình nhỏ nhất, sau đó là DSR và DSDV. Ví dụ như trong trường
hợp mạng có thời gian tạm dừng của các node(pause time) là 20 giây. Độ trễ
truyền tin của: AODV là 0.9 giây, DSR là 1.5 giây, còn DSDV là 2.0 giây.
Qua so sánh hai thông số đánh giá hiệu suất ở trên thì cả hai giao thức
định tuyến thuộc loại On-demand đều cho kết quả hiệu suất hoạt động cao
hơn giao thức DSDV (proactive). Vậy nên đối với những mô phỏng tiếp
theo chỉ thực hiện trên hai giao thức On-Demand là AODV và DSR.

3.2.2 So sánh hiệu suất hoạt động của hai giao thức AODV và DSR với
số lƣợng các node và thời gian tạm dừng khác nhau.
Trong mô phỏng ở trên, đối với những mạng có sự di chuyển của các
node cao với 20 node trong mạng. Hiệu xuất TCP trên giao thức AODV cao
hơn giao thức DSR. Để có kết quả toàn diện hơn, chúng tôi tiến hành mô
phỏng với số lượng các node là 10, 20, 30, 40 với thời gian tạm dừng của
các node(pause time) là 0, 10, 20, 40, 100 giây. Tần số gửi tin là 4 gói
tin/giây.

3.2.2.1 Kết quả mô phỏng






23


Hình 6 - Biểu đồ so sánh tỷ lệ gói tin tới đích (PDF) của các giao thức
định tuyến AODV và DSR


PDF
0
10
20
30
40
50
60
70
80
90
100
0 10 20 30 40 50 60 70 80 90 100
Pause time (sec)
Packet delivery fraction(%)
AODV, 10 sources
DSR, 10 sources




24



Hình 7 - Biểu đồ so sánh chi phí định tuyến của các giao thức định
tuyến AODV và DSR. Mạng 10 node.




Normalized Routing Load
0
0.2
0.4
0.6
0.8
1
0 10 20 30 40 50 60 70 80 90 100
Pause time(secs)
Normalized routing load
AODV, 10 sources
DSR, 10 sources