LOGO

ĐỊNH TUYẾN TRONG
CHUYỂN MẠCH GÓI

GiẢNG VIÊN:
PHAN THỊ THANH NGỌC

SINH VIÊN:
ĐỖ XUÂN THẮNG
TRẦN THỊ HUỆ

1


Nội dung
1

Định nghĩa và giới thiệu chung

2

Các thuật toán tìm đường ngắn nhất

3

Các giao thức định tuyến

4

5

Định tuyến hỗ trợ chất lượng dịch vụ QoS

Các thế hệ tìm đường

2


Định tuyến và giới thiệu chung

Định tuyến là một tiến trình lựa chọn con đường cho

thông tin chuyển qua

mạng.

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 node trung gian.

Mỗi node trong mạng nhận gói dữ liệu từ một đường vào rồi chuyển tiếp nó tới
một đường ra, hướng đến đích của dữ liệu.

3


Định tuyến và giới thiệu chung

Mục tiêu

Sử dụng


Tối thiểu hóa giá

tối đa

thành mạng..

tài nguyên mạng.

4


Định tuyến và giới thiệu chung

Phân loại: Theo sự phân tán của các chức năng chọn đường trên các node của mạng
1.Kỹ thuật định tuyến tập trung

  Các tuyến được tính toán tập trung tại một bộ xử lý và sau đó phân bố chúng ra các Router trên mạng.
2.Kỹ thuật định tuyến phân tán

 Phân chia thành các vùng tự trị AS (autonomous system).
 Các thành phần trong một AS chỉ biết về nhau, mà không quan tâm tới các thành phần trong AS khác, khi
có yêu cầu giao tiếp với các AS khác sẽ thông qua thành phần ở biên AS

5


Định tuyến và giới thiệu chung

Phân loại: Theo sự thích nghi với trạng thái hiện hành của mạng

1.Định tuyến tĩnh

 Các thông tin về đường đi là do người quản trị mạng nhập cho mỗi router
 Các đường đi là được thiết lập cố định
 Cấu trúc mạng thay đổi bất kỳ thì người quản trị phải xóa, thêm các thông tin về đường
đi

 Tốn thời gian và không có tính linh hoạt
 Sử dụng trong các mạng nhỏ

6


Định tuyến và giới thiệu chung

Phân loại: Theo sự thích nghi với trạng thái hiện hành của mạng
2.Định tuyến động

 Thông tin về tuyến sẽ được cập nhật tự động khi nhận được thông tin mới về liên
mạng.

 Hoạt động linh hoạt khi mạng có sự thay đổi trạng thái
 Phương thức tạo tuyến động thuận tiện cho việc điều chỉnh luồng tải cho nhiều đường
khác nhau trong mạng để đạt hiệu suất cao hơn.

7


Các thuật toán tìm đường ngắn nhất
1.Thuật toán định tuyến theo Vecto khoảng cách DVA(Distance Vecto Algorithm )


1

2

Tính toán con đường

Dựa trên phương pháp tập

ngắn nhất giữa các cặp

trung

node trong mạng

3
Các node mạng thực hiện quá
trình trao đổi thông tin trên cơ sở
của địa chỉ đích, node kế tiếp, và
con đường ngắn nhất tới đích

8


Các thuật toán tìm đường ngắn nhất
2.Thuật toán định tuyến theo trạng thái liên kết LSA(Link State Algorithm )

1

2


3

Tính toán con đường

Các node mạng quảng bá giá

Tất cả các node đều biết rõ

ngắn nhất tới node đích

trị liên kết của nó với các

topo mạng

node xung quanh tới các
node khác

9


Các giao thức định tuyến

1.Giao thức RIP







Là giao thức định tuyến theo vecto khoảng cách
Quảng bá toàn bộ bảng định tuyến của nó cho các bộ định tuyến lân cận theo định kỳ
Chu kỳ cập nhật là 30s
Sử dụng số đếm các node để làm giá trị đánh giá chất lượng của định tuyến. Giá trị
tối đa là 15hop



Thích hợp với mạng quy mô nhỏ

10


Các giao thức định tuyến

2. Giao thức OSPF




Thuật toán link-state
Chia hệ thống thành nhiều khu vực nhỏ. Các
router ở biên khu vực tóm tắt thông tin về khu
vực của mình và gửi thông tin này tới các khu
vực khác,



Chỉ gửi update khi có sự thay đổi trên mạng


11


Định tuyến hỗ trợ chất lượng dịch vụ QoS

Mục tiêu: Đáp ứng các yêu cầu về QoS của luồng dữ liệu và nâng cao hiệu quả sử
dụng tài nguyên mạng.

1. Đáp ứng đòi hỏi về QoS của các luồng dữ liệu




Tìm đường đi thỏa mãn yêu cầu của luồng dữ liệu về băng thông, trễ…
Cơ chế tìm đường thường là động theo yêu cầu, có thể dựa vào các ràng buộc như:
đường đi có số node nhỏ nhất hoặc chi phí thấp nhất

12


Định tuyến hỗ trợ chất lượng dịch vụ QoS

2. Tối ưu hệ số sử dụng tài nguyên mạng

 Chuyển hướng lưu lượng theo cách hiệu quả nhất để tối đa nhất thông lượng qua
mạng.

 Vì đường dài tốn nhiều tài nguyên mạng nên đường ngắn nhất trong các đường có thể
đáp ứng sẽ được chọn.


13


Định tuyến hỗ trợ chất lượng dịch vụ QoS
3. Hiệu suất mạng không bị giảm đáng kể khi có sự cố xuất hiện như tắc nghẽn.
Để thực hiện định tuyến đảm bảo chất lượng dịch vụ QoS, một số kiểu định tuyến đã được định nghĩa
và phát triển:

 Định tuyến hỗ trợ QoS là cơ chế định tuyến xác định đường đi cho các luồng dựa vào sự hiểu biết về
tài nguyên hiện có trên mạng, cũng như yêu cầu về QoS của các luồng dữ liệu

 Định tuyến dựa vào chính sách quản trị.
 Định tuyến theo điều kiện ràng buộc để tính toán các tuyến

14


Khó

Trạng
Các

Định tuyến hỗ trợ chất lượng dịch vụ QoS

Hỗ trợ cả lưu lượng tối đa và chất
lượng dịch vụ, nên vấn đề tối ưu
hóa hiệu suất trở nên rất phức tạp

15



Các thế hệ tìm đường

Thế hệ đầu tiên

 1969
 Dùng thời gian trễ ước tính làm tiêu chuẩn đánh giá hiệu quả
 Dùng thuật toán vecto khoảng cách
 Các node trao đổi thông tin với các node kề
 Cập nhật bảng tìm đường dựa trên thông tin đến
 Không quan tâm đến tốc độ đường truyền, chỉ quan tâm chiều dài hàng đợi tại các node
 Đáp ứng chậm với nghẽn mạch

16


Các thế hệ tìm đường

Thế hệ thứ 2

 1979
 Dùng thời gian trễ làm tiêu chuẩn đánh giá hiệu quả
 Thời gian trễ được đo trực tiếp
 Sử dụng thuật toán định tuyến theo trạng thái liên kết
 Thích hợp cho mạng có tải trung bình hoặc nhẹ
Thế hệ thứ 3

 1987
 Việc tính toán chi phí của liên kết đã được thay đổi
17



Câu hỏi

1. Đặc tính nào không phải của giải thuật Dijkstra(LSA):

a.
b.
c.
d.

Mỗi node cần biết topology toàn bộ mạng
Phải biết chi phí liên kết của tất cả các liên kết trong mạng
Phải trao đổi thông tin với tất cả các node khác trong mạng
Có thể trao đổi thông tin với các node kề trực tiếp

18


Câu hỏi

2. Đặc điểm không phải của giao thức RIP

a.
b.
c.
d.

Là giao thức định tuyến vecto khoảng cách
Chu kỳ cập nhật là 30s

Chỉ gửi update khi có sự thay đổi trên mạng
Giá trị tối đa là 15hop

19


Câu hỏi

3. ARPANET – Tìm đường thế hệ đầu tiên là năm:

a.
b.
c.
d.

1969
1979
1987
Không có đáp án

20


Câu hỏi

4. ARPANET (Tìm đường) đã trải qua mấy thế hệ:

a.
b.
c.

d.

2
3
4
5

21


Câu hỏi

5.Tiêu chuẩn để đo tính hiệu quả trong các chiến thuật tìm đường:

a.
b.
c.

Số chặng đường (hop) là tối thiểu
Chi phí (cost) tối thiểu
Cả 2 đáp án trên

22


LOGO

Thank You !

23