<span class="text_page_counter">Trang 2</span><div class="page_container" data-page="2">

<small>Luận văn được hoàn thành tại:</small>

HỌC VIEN CƠNGN NGHỆ BƯU CHÍNH VIÊN THONG

<small>Phản biện 1: TS. Nguyễn Quý Sỹ</small>

<small>Phản biện 2: PGS.TS. Chu Đức Trình</small>

<small>Luận văn sẽ được bảo vệ trước Hội đông châm luận văn thạc sĩ tại</small>

<small>Học viện Cơng nghệ Bưu chính Viễn thơng</small>

<small>ngày 20 thang 09 năm 2015.</small>

<small>Có thê tìm hiêu luận van tại:</small>

<small>- Thu viện của Học viện Cơng nghệ Bưu chính Viễn Thông</small>

</div><span class="text_page_counter">Trang 3</span><div class="page_container" data-page="3">

MỞ DAU

Định tuyến (Routing) là quá trình chon lựa các đường di trên

một mạng gdm nhiều nút dé gửi dữ liệu từ nguồn tới đích theo yêu

cầu. Trong mạng gói với dữ liệu là các gói, thì định tuyến chỉ ra

hướng, sự di chuyền của các gói (dữ liệu) được đánh địa chỉ từ mạng nguồn của chúng, hướng đến đích cuối thơng qua các nút

mạng (node) trung gian; ở đó thiết bị định tuyến chuyên dùng

được gọi là bộ định tuyến (Router). Trong tiễn trình định tuyến,

gói dir liệu được truyền đi dựa vào bảng định tuyến, đó là bảng chứa những lộ trình tốt nhất đến các đích khác nhau trên mạng.

Các thơng tin định tuyến trong mang là thành phan thiết yếu

của truyền thơng Internet, vì mỗi gói trên Internet phải được

truyền một cách nhanh chóng qua mỗi mạng (hoặc hệ thống độc

lập) ở đó nó phải đi qua để đi từ nguồn đến đích. Hầu hết các phương pháp triển khai hiện nay trên Internet dé định tuyến trong mạng đều được thiết kế với các gói tin truyền theo đường đi ngắn nhất. Các thuật toán cơ bản đã chỉ ra các giao thức định tuyến hiện

nay là khơng an tồn, nó có thé bị xâm nhập do các bộ định tuyến

<small>cũng không theo các giao thức tương ứng một cách chính xác.</small>

Qua nghiên cứu có thé thấy một trong những yếu tố quan trọng nhất của định tuyến là việc cập nhật các thông tin định

tuyến. Các nút mạng liên tục trao đôi các thông tin định tuyến với

<small>nhau dé lựa chọn ra đường di tôi ưu với chi phí rẻ nhât và ngăn</small>

</div><span class="text_page_counter">Trang 4</span><div class="page_container" data-page="4">

nhất. Tuy nhiên trong quá trình định tuyến các bản tin định tuyến

này có thể bị tấn cơng làm thơng tin định tuyến bị sai lệch hoặc

làm ngập các bản tin. Vì vậy, cần phải có phương pháp để bảo vệ thông tin định tuyến.

<small>Luận văn tập trung nghiên cứu phương pháp loại bỏ các bản</small>

tin trùng lặp, sử dụng hạ tầng khóa cơng khai nhằm chống giả mạo

bản tin và các phương pháp chống tràn.

</div><span class="text_page_counter">Trang 5</span><div class="page_container" data-page="5">

Chương 1: TONG QUAN VE VAN ĐÈ NGHIÊN CỨU

Định tuyến (Routing) chỉ ra hướng, sự di chuyên của các gói

(dir liệu) được đánh dia chỉ từ mang nguồn, hướng đến đích cuối

thông qua các node trung gian thông qua thiết bị phần cứng

chuyên dùng được gọi là router (bộ định tuyến). Trong chương

này sẽ tập trung thảo luận về các nội dung: Khái quát định tuyến; lý thuyết đồ thị (Graph); phân loại định tuyến.

1.1 Khái quát định tuyến

Định tuyến là q trình tìm đường đi dé truyền thơng tin liên

mạng từ nút nguồn tới nút đích. Nó là một chức năng được thực hiện ở tầng mạng. Chức năng này cho phép bộ định tuyến (router) đánh giá các đường đi sẵn có tới dich. Dé đánh giá đường đi, định

tuyến sử dụng các thông tin về cấu trúc liên kết (Topology) của <small>mạng.</small>

1.2 Phân loại định tuyến

Định tuyến được chia thành 3 loại chính: định tuyến tinh, định tuyến ngẫu nhiên và định tuyến động

1.2.1 Dinh tuyến tĩnh

1.2.2 Định tuyến ngẫu nhiên

1.2.2.1 Dinh tuyến tràn lũ gói tin (flooding)

1.2.2.2 Dinh tuyến ngẫu nhiên (Random walk)

1.2.2.3 Định tuyến ngẫu nhiên (Hot potato)

1.2.3 Định tuyến động (dynamic routing)

</div><span class="text_page_counter">Trang 6</span><div class="page_container" data-page="6">

1.2.3.1 Dinh tuyến động minimum spanning tree)

1.2.3.2 Định tuyến động (shortest path tree)

1.3 Lý thuyết đồ thi (graph)

Lý thuyết đồ thị được sử dụng trong nhiều ứng dụng khác

nhau trong đó ứng dụng tìm đường ngắn nhất có ý nghĩa đặc biệt

quan trọng trong định tuyến.

1.3.1 Khai niệm cơ bản về đồ thị

1.3.2 Cây và cây khung của đồ thị

1.3.3 Bài tốn cây khung ngắn nhất

1.4 Phân tích đánh giá các phương pháp định tuyến

Một trong những ưu điểm lớn nhất của định tuyến tĩnh

chính là sự thay đổi chậm, điều đó có nghĩa là tính chịu đàn hồi của mạng sẽ tốt hơn. Chính vì thế nên nó có khả năng dự đoán <small>hiệu năng mạng và sửa lỗi nhanh hơn.</small>

Tuy nhiên, định tuyến tĩnh không dựa trên sự đánh giá lưu

lượng và cấu trúc liên kết mạng hiện thời. Trong môi trường IP, các bộ định tuyến hiện thời không thể phát hiện ra các bộ định

tuyến mới, chúng chỉ có thể chuyên gói tin tới các bộ định tuyến

được xác định bởi nhà quản trị mạng. Hơn nữa, trong định tuyến

tĩnh, các tuyến đường được thiết lập thủ cơng, mỗi khi mạng có sự

cơ hoặc cau hình mạng thay đổi, thì nhà quản tri mạng phải thiết

lập tuyến mới. Điều này cũng có nghĩa là q trình cập nhật lại

tuyến kênh truyền sẽ tốn thời gian và cơng sức hơn, do người quản

trị mạng phải tính tốn và thiết lập/câu hình lại đường truyền.

</div><span class="text_page_counter">Trang 7</span><div class="page_container" data-page="7">

Đối với định tuyến động thì lại có cơ chế hoạt động ngược

lại so với định tuyến tĩnh. Sau khi người quản trị nhập/khai báo

các lệnh cau hình dé khởi tạo định tuyến động, thông tin về tuyến

<small>sẽ được cập nhật tự động mỗi khi nhận được thông tin mới từ lớp</small>

mạng. Các thay đổi về cấu trúc liên kết mạng cũng sẽ được trao

đôi giữa các bộ định tuyến.

Định tuyến động rõ ràng thé hiện được những tinh năng ưu việt hon so với định tuyến tĩnh. Bat kỳ sự thay đổi nào của mạng, thì định tuyến động cũng sẽ tự động cập nhật tuyến đường tối ưu nhất, mà không cần người quản trị mạng phải tham gia tính

tốn và cấu hình lại. Nhưng khi định tuyến động sử dụng trong một mạng phức tạp thì nó có thể phải tái tạo lại cầu hình một cách liên tục, do sự khác nhau của các thiết bị trên mạng và chính sách

của rất nhiều nhà khai thác mạng cùng tồn tại. Điều này gây nên những tốn thất trên mạng vẻ sử dung tài nguyên hay nói cách khác

việc sử dụng định tuyến động cũng sẽ tạo ra độ phức tạp cao hơn

so với định tuyến tinh. Do đó, khi phải cập nhật tat cả cơ sở dit

liệu và cập nhật bản định tuyến thì hai phương pháp định tuyến

<small>này không thực sự hiệu quả.</small>

Định tuyến ngẫu nhiên có nhược điểm là làm tăng số

lượng gói tin gửi trong mạng quá nhiều. Vì vậy việc sử dụng định

tuyến ngẫu nhiên trong hầu hết các ứng dụng là khơng thực tế, do

<small>các gói tin được nhân lên đã làm tăng băng thơng, thâm chí gây</small>

tắc nghẽn mạng và yêu cầu năng lực xử lý của CPU cũng tăng

</div><span class="text_page_counter">Trang 8</span><div class="page_container" data-page="8">

theo. Tuy vậy, đối với các bản tin định tuyến có kích cỡ nhỏ hoặc các bản tin cập nhật cơ sở dữ liệu thì việc sử dụng định tuyến ngẫu

nhiên sẽ thực sự hiệu quả. Định tuyến ngẫu nhiên sử dụng phương pháp tràn lũ gói tin (cập nhật định tuyến) có thé được dùng dé so

sánh với các phương thức định tuyến khác. Việc tràn lũ gói tin sẽ

ln chon được đường ngắn nhất hay chi phí giảm nhất, do đó

khơng có giải thuật nào có thé tìm được độ trễ ngắn hơn. Do tran

lũ gói tin sẽ tự động gửi tất cả các bản tin định tuyến trong mạng,

nên việc cập nhật cơ sở dữ liệu định tuyến sẽ ln nhanh nhất.

Chính vì thế việc sử dụng phương pháp định tuyến ngẫu nhiên

(tràn lũ gói tin) trong việc cập nhật cơ sở dit liệu và truyền bản tin định tuyến sẽ thực sự hiệu quả hơn rất nhiều so với định tuyến tĩnh và định tuyến động. Phương pháp định tuyến ngẫu nhiên sẽ

đặc biệt hiệu quả và ứng dụng cao hơn nếu loại bỏ được các gói tin dư thừa tràn lan trên mạng. Như vậy, sẽ dẫn đến sự thay đổi

<small>của phương pháp tràn lũ gói tin đó là tràn lũ gói tin có chọn lọc,</small>

<small>nghĩa là router sẽ chỉ gửi các gói đi trên các đường đi theo hướng</small>

từ nguồn đến đích. Do đó, sau đây luận văn sẽ tập trung nghiên cứu các phương pháp tràn lũ gói tin nhằm khắc phục nhược điểm dé nâng cao tính ứng dụng, hiệu quả của định tuyến tran lũ gói tin.

15 Kết luận chương 1

Trong chương 1, đã thảo luận tổng quan về định tuyến, phân

loại các loại định tuyến, nhất là lý thuyết đồ thị, một lý thuyết cơ bản trong định tuyến. Tuy nhiên, để đảm bảo chất lượng truyền tải

</div><span class="text_page_counter">Trang 9</span><div class="page_container" data-page="9">

cũng như tránh các hiện tượng bị mất gói tin hay xác định được

đường đi nhanh nhất từ nguồn đến đích, thường đưa ra các thuật toán định tuyến để giải quyết vấn dé trên. Trong Chương 2, sẽ

thảo luận về các giao thức định tuyến động.

</div><span class="text_page_counter">Trang 10</span><div class="page_container" data-page="10">

Chương 2: CÁC GIAO THỨC ĐỊNH TUYẾN

Router thực hiện hai chức năng chính là quyết định chọn đường đi và chuyên mach. Quá trình chọn đường di được thực

hiện ở lớp mạng.Router dựa vào bảng định tuyến để chọn đường cho gói dita liệu,sau đó quyết định đường ra. Chuyên mạch là quá

<small>trình rouer thực hiện đê chun gói từ cơng nhận vào ra cơng phát</small>

di.Dé router thực hiện tốt hai chức năng trên thì trong chương này sẽ tập trung nghiên cứu về các giao thức định tuyến.

Giao thức định tuyến RIP

Giao thức định tuyến cong nội bộ (IGRP) Giao thức định tuyến EIGRP

Giao thức định tuyến OSPF

Định tuyến vector- khoảng cách

Định tuyến trạng thái đường liên kết

Phân tích, đánh giá các giao thức định tuyến

<small>Qua nghiên cứu về các giao thức định tuyên có thê nhận</small>

thấy các giao thức RIP và OSPF là các giao thức chuẩn chung, có

<small>thê chạy trên các router của nhiêu hãng khác nhau, ngồi ra cịn có</small>

một số đặc điểm có thé áp dụng định tuyến ngẫu nhiên trong quá trình truyền bản tin định tuyến.

</div><span class="text_page_counter">Trang 11</span><div class="page_container" data-page="11">

Nhược điểm của giao thức định tuyến ngẫu nhiên là dé <small>dẫn tới gói tin trong mang bi lặp vịng (loop), do thời gian các nút</small>

mạng gửi thông tin định tuyến cho nhau là định kỳ và trong

<small>khoảng thời gian khá lâu, trong khi mơi trường mạng ln có sự</small>

thay đổi ngẫu nhiên. Mặt khác, giao thức này không phân biệt loại

gói tin được truyền đi trong mạng, cho nên với những gói tin là thời gian thực vẫn bị xử lí giống những gói tin dữ liệu thơng

thường, tức là giao thức không hỗ trợ chất lượng phục vụ (QoS).

Ngồi ra, vì chi phí được tính theo số “hoop count”, cho nên có

thé xảy ra trường hop chi phí của liên kết thì nhỏ hơn, băng thơng

cũng nhỏ sẽ gây nên tình trạng nghẽn mạng, trong khi liên kết

<small>khác có chi phí lớn hơn nhưng băng thơng cũng lớn thì lại khơng</small>

có dữ liệu được truyền trên đó. Vì vậy, giao thức này chỉ được sử

dụng ở các mạng nhỏ và dung lượng truyền trên mạng không quá lớn (như dữ liệu bản tin định tuyến hoặc bản tin cập nhật định tuyến) dé tránh tình trạng nghẽn mạng gây mat dữ liệu do bị lặp vòng quá nhiều.

Đối với giao thức EIGRP, là một giao thức định tuyến do

Cisco phát triển, chỉ chạy trên các sản phẩm của Cisco. Đây là một giao thức véc tơ - khoảng cách được cải tiến, EIGRP khơng sử dụng thuật tốn truyền thống cho véc tơ - khoảng cách là thuật

toán Bellman-Ford mà sử dụng thuật toán riêng được phát triển

<small>bởi J.J.Garcia Luna Aceves — thuật toán DUALL. Cách thức hoạt</small>

động của EIGRP cũng khác biệt so với RIP và vay mượn một SỐ

</div><span class="text_page_counter">Trang 12</span><div class="page_container" data-page="12">

cấu trúc và khái niệm của OSPF như: xây dựng quan hệ hàng xóm, sử dụng bộ 3 bang dit liệu (bảng hàng xóm, bảng cấu trúc

hình học và bảng định tuyến).

Như vậy, qua nghiên cứu các giao thức định tuyến, ta có thé xây dựng các bảng định tuyến thơng qua q trình thiết lập

đơn giản, mà có thể an tồn sử dụng thuật tốn định tuyến tràn lũ

gói tin trong hai giao thức chuẩn OSPF và RIP. Giao thức EIGRP

tuy có nhiều ưu điểm nhưng do nó chỉ thiết kế dành riêng cho các

thiết bị của Cisco, nên luận văn đã tập trung nghiên cứu về hai

<small>giao thức OSPF và RIP.</small>

2.6. Kết luận chương 2

Trong chương 2 đã nghiên cứu phân tích về các giao thức định tuyến nhăm đánh giá và lựa chọn giao thức thích hop dé thiết lập

định tuyến ứng dụng vào mạng cụ thể.

</div><span class="text_page_counter">Trang 13</span><div class="page_container" data-page="13">

Chương 3: CÁC THUẬT TỐN ĐỊNH TUYẾN VÀ

PHƯƠNG PHÁP CHĨNG TRÀN

Trong chương này sẽ thảo luận về thuật toán tràn lũ gói tin

và phương pháp chống tràn cũng như phương pháp bảo đảm tính

<small>an tồn của thuật tốn.</small>

<small>3.1. Thuật tốn tràn lũ (Flooding) gói tin3.1.1. Hiện tượng lan tràn gói tin</small>

Thuật toán định tuyến lan tràn (flooding algorithm) là một <small>thuật tốn đơn giản khi mà mỗi gói tin được gửi đi từ một nút</small>

mạng thì gói tin đó sẽ được gửi tới tất cả các nút mạng còn lại trừ

<small>nút mà nó vừa gửi.</small>

Phương pháp này thật sự hiệu quả nếu ta cố gắng loại bỏ các dữ liệu dư thừa trong quá trình truyền tin nhưng vẫn đảm bảo rằng

tất cả các nút trong mạng vẫn nhận được gói tin.

<small>3.1.2. Thuật tốn tràn lũ (Flooding) gói tin</small>

Cho một mạng lưới G = (V,E) với đỉnh V là các thiết bị định tuyến (router) và E là các cạnh kết nối trực tiếp giữa các router đó, các router được đánh theo số thứ tự từ 1 đến n. Giả định rằng G là biconect nghĩa là phải mat ít nhất hai thiết bị định tuyến dé không

thé kết nối với mạng.

<small>Thuật toán flooding được khởi tạo bởi các router s tạo ra</small>

một bản tin M thơng báo rằng nó muốn gửi đến tất cả các router khác trong G. Thuật toán được thực hiện bằng cách gán số thứ tự

vào các bản tin mà nó gửi. Nhận thấy trong q trình áp dụng thuật tốn một router bị lỗi có thé sửa đổi gói tin hoặc thay đơi số

<small>thứ tự của gói tin đó rơi gửi tràn lan trên mạng, nó sẽ làm ảnh</small>

</div><span class="text_page_counter">Trang 14</span><div class="page_container" data-page="14">

hưởng nghiêm trọng đến mạng, có thé gây tắc nghẽn hoặc làm tê

liệt hệ thống. Chính vì thế cần phải có các chính sách bảo mật trên

các gói tin và trên router dé tránh hiện tượng trên.

<small>3.2. Phương pháp đảm bảo tính an tồn của thuật tốn</small>

3.2.1. Hạ tầng khóa cơng khai

Trong q trình truyền ta có thé tránh những thỏa hiệp thất bại do router bị lỗi gây ngập lụt dựa trên hạ tầng khóa cơng khai được

xác định cho các bộ định tuyến. Trong trường hợp này, chúng ta sẽ có s ký số cho mọi bản tin lũ truyền, và mỗi router sẽ xác nhận

tin nhắn trước khi nó gửi đi.

<small>3.2.2. Kích thước gói tin với tính tốn hàm băm</small>

Trong một số trường hợp, một router có thể phải tính tốn q

nhiều các giá trị băm, điều này sẽ làm quá tải đối với các router. Như vậy chúng ta có thể tự hỏi liệu có cách nào làm giảm số

lượng băm mà một router trung gian cần phải thực hiện không?

Trong phan này, tôi sẽ mô tả cách dé có được kết quả như vậy.

3.3. Ung dung của kỹ thuật Flooding

<small>Wireless mesh network, hay WMN, là mạng không dây</small>

kết nối tự do bởi các nút sử dụng tín hiệu vơ tuyến như máy tính

xách tay, điện thoại... khơng sử dụng điều khiến tập trung. Các giao thức định tuyến cho WMN hiện tại đều thực hiện ở lớp mạng

<small>sử dụng địa chi IP.</small>

Trong phan này luận văn sẽ trình bày một giao thức định tuyến proactive mới ở lớp hai dành cho WMN dựa trên ý tưởng

của giải thuật định tuyến XL. Giao thức định tuyến này, gọi là DLL-XL, giúp định tuyến hiệu quả nhờ áp dụng các kỹ thuật

<small>truyền cập nhật có lựa chọn đên các nút khác.</small>

</div><span class="text_page_counter">Trang 15</span><div class="page_container" data-page="15">

3.3.1. Một số phương pháp giới han flooding

Một số phương pháp giới hạn flooding ứng dụng trong định tuyến hiện nay gồm:

- Phương pháp đánh số thứ tự gói tin để khơng flooding lại

<small>những gói tin cũ.</small>

<small>- Phương pháp giới hạn vùng flooding nhân tạo: Mạng lớnđược chia thành những vùng nhỏ; flooding chỉ thực hiện bên trong</small>

từng vùng, khơng flooding ra ngồi vùng. Định tuyến giữa các vùng thực hiện nhờ các nút biên. Do đó đường đi chỉ tối ưu trong

từng vùng và cũng khó mở rộng khi phải phân cấp nhân tạo một

<small>mạng lớn.</small>

<small>- Phương pháp giới hạn bán kính flooding: Flooding chỉ</small>

truyền qua một số nút tối đa được quy định trước. Việc xác định

bán kính tối đa này rất khó thực hiện. Bán kính lớn thì sẽ flooding

dư thừa mà bán kính nhỏ thì định tuyến khơng chính xác

- Phương pháp bầu chọn nút flooding: Chỉ những nút đại

<small>diện này mới flooding, các nút cịn lại chỉ nhận gói tin mà khôngflooding.</small>

<small>3.3.2. Giải thuật XL</small>

3.4. Đề xuất phương pháp chống tràn gói tin định tuyến 3.4.1. Phân tích, đánh giá các phương pháp chống tràn gói tin

<small>3.4.1.1. Phương pháp đánh thứ tự gói tin</small>

<small>3.4.1.2. Phương pháp giới hạn vùng flooding nhân tạo3.4.1.3. Phương pháp giới hạn bán kính flooding</small>

</div><span class="text_page_counter">Trang 16</span><div class="page_container" data-page="16">

3.4.1.4. _ Phương pháp bau chon nút

<small>3.4.2. Phân tích đánh giá tính hiệu quả của thuật tốn định</small>

tuyến tràn

Thuật toán định tuyến tràn là thuật toán đơn giản nhưng hiệu quả trong việc tìm đường và cập nhật bảng định tuyến.

Qua nghiên cứu về các giao thức định tuyến có thé nhận thấy các giao thức RIP và OSPF là các giao thức chuẩn chung, có thé chạy trên các router của nhiều hãng khác nhau, ngoài ra cịn có một số đặc điểm có thể áp dụng thuật tốn định tuyến trong q

trình truyền bản tin định tuyến. Tuy nhiên để thuật tốn, thật sự

hiệu quả thì cần phải loại bỏ các bản tin dư thừa, tránh các bản tin

cũ phát ngược lại gây tắc nghẽn. Sau đây, luận văn xin đề xuât ý tưởng thay đổi lại cấu hình của giao thức OSPF và giao thức RIP

dé thuật tốn Flooding có thé áp dụng hiệu quả nhất.

Đề cấu hình mạng một cách chính xác khi áp dụng thuật tốn Flooding thì cần phải kết hợp với các phương pháp chống tràn đã

nêu ở trên. Tuy nhiên, để thực hiện kết hợp các phương pháp này cần phải có những nghiên cứu sâu hơn và quan trọng là phải chứng minh được tính hiệu quả của giải pháp kết hợp cũng như

khả năng ứng dụng vào thực tế. Đây cũng là hướng nghiên cứu

phát triển tiếp theo của luận văn 3.5. Kết luận chương 3

Trong chương này luận văn đã thảo luận về thuật toán tràn

lũ và các phương pháp bảo đảm tính an tồn của thuật tốn. Đồng thời, cũng nghiên cứu, phân tích, đánh giá các phương pháp chống

tràn gói tin và qua đó đề xuất giải pháp kết hợp các phương pháp

<small>chông tràn đê nâng cao hiệu quả của thuật toán.</small>

</div>