Bài giảng môn Mạng máy tính - Chương 5: Cơ sở giao thức định tuyến
Cho hệ thống mạng gồm 228 host và địa chỉ IP
đƣợc thiết lập ở lớp 192.168.1.0/24. Hãy chia hệ
thống này thành 4 mạng con (Net 1: 120 host,
Net 2: 60 host, Net 3: 30 host, Net 4: 18 host)
dựa theo kỹ thuật VLSM gồm các thông tin:
- Địa chỉ mạng con (Network ID)
- Subnet Mask của mạng con
- Dải địa chỉ host của mỗi mạng con
- Địa chỉ Broadcast
- Diệp hoàng bảo bảo
49 trang |
Chia sẻ: nguyenlam99 | Lượt xem: 1314 | Lượt tải: 1
Bạn đang xem trước 20 trang tài liệu Bài giảng môn Mạng máy tính - Chương 5: Cơ sở giao thức định tuyến, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
BÀI GIẢNG
MÔN: MẠNG MÁY TÍNH
Giảng viên: Hoàng Thanh Hòa
CHƢƠNG 5. CƠ SỞ
GIAO THỨC ĐỊNH TUYẾN
2
Các khái niệm cơ bản trong
định tuyến
5.1.
5.2. Các thuật toán định tuyến
5.3.
Một số giao thức định tuyến
thông dụng
thanhhoa48dhv@gmal.com
5.1. Các khái niệm cơ bản
trong định tuyến
Định tuyến
Bảng định tuyến
Metric
Giao thức định tuyến
Giao thức đƣợc định tuyến
Khoảng cách địa lý
3 thanhhoa48dhv@gmal.com
Khái niệm định tuyến
Là phƣơng pháp xác định đƣờng đi cho việc
vận chuyển các gói tin từ nguồn đến đích hiệu
quả nhất.
Do các thiết bị thuộc lớp 3 của mô hình OSI,
thƣờng là Router.
Router phải xây dựng cho mình một bảng
chứa các thông tin cần thiết => đƣờng đi tối
ƣu nhất đến đích
4 thanhhoa48dhv@gmal.com
Bảng định tuyến
Là một bảng chứa thông tin về các tuyến
đƣờng trên mạng, đƣợc lƣu trữ trong RAM
của Router.
Bảng có thể đƣợc lập bởi ngƣời quản trị hoặc
bằng các giao thức định tuyến.
5 thanhhoa48dhv@gmal.com
Bảng định tuyến
Gồm có các thông tin:
- Địa chỉ đích của mạng, mạng con của hệ
thống.
- Địa chỉ IP của Router chặng kế tiếp phải đến.
- Cổng đi đến Router kế tiếp.
- Mặt nạ mạng của địa chỉ đích.
- Khoảng cách để đến đích.
- Thời gian từ khi Router cập nhật lần cuối.
6 thanhhoa48dhv@gmal.com
Khái niệm Metric
Là một số đo mà giao thức định tuyến sử
dụng để từ đó chọn ra con đƣờng tối ƣu nhất.
Một giao thức định tuyến có thể sử dụng nhiều
metric khác nhau
7 thanhhoa48dhv@gmal.com
Khái niệm Metric
Các metric thường được sử dụng là:
- Path Length (chiều dài tuyến đƣờng): là metric
cơ bản, đƣợc xác định bằng số Hop giữa nguồn
và đích.
- Reliability (độ tin cậy): là khái niệm chỉ độ tin
cậy của một liên kết.
- Delay (độ trễ): Chỉ thời gian cần để chuyển một
packet từ nguồn tới đích.
- Bandwith (băng thông): Chỉ lƣu lƣợng dữ liệu
tối đa có thể truyền trên liên kết.
8 thanhhoa48dhv@gmal.com
Giao thức định tuyến
Là các giao thức để các Router sử dụng để
trao đổi thông tin định tuyến với các Router
khác.
Đƣợc cài đặt tại các Router, đƣợc sử dụng để
tạo bảng định tuyến.
Có 2 loại giao thức định tuyến:
- Giao thức định tuyến nội vùng: Rip, OSPF,
IGRP, EIGRP.
- Giao thức định tuyến ngoại vùng: BGP.
9 thanhhoa48dhv@gmal.com
Giao thức định tuyến
Chức năng của giao thức định tuyến:
- Học thông tin định tuyến về các mạng từ
Router kế cận.
- Quảng bá thông tin định tuyến về các mạng
đến các Router kế cận.
- Nếu có nhiều hơn một tuyến đƣờng đến một
mạng, chọn tuyến đƣờng tốt nhất dựa vào
metric.
- Chức năng hội tụ định tuyến.
10 thanhhoa48dhv@gmal.com
Giao thức đƣợc định tuyến
Là giao thức đƣợc sử dụng để định hƣớng
cho gói dữ liệu của ngƣời dùng.
Cung cấp đầy đủ thông tin về địa chỉ lớp mạng
để gói dữ liệu có thể truyền từ host này tới
host khác dựa trên cấu trúc địa chỉ đó.
Các giao thức đƣợc định tuyến gồm có:
- Internet Protocol (IP).
- Internetwork Packet Exchange (EPX).
11 thanhhoa48dhv@gmal.com
Khoảng cách địa lý
Administrative Distance (AD): là thông số để
đánh giá độ tin cậy của thông tin định tuyến mà
Router nhận đƣợc từ Router hàng xóm.
AD là một số nguyên có giá trị từ 0 đến 255.
Mỗi giao thức định tuyến có một giá trị AD tƣơng
ứng:
- Kết nối trực tiếp: 0
- Tuyến đường tĩnh: 1
- Rip: 120
- OSPF: 110
- IGRP: 100
12 thanhhoa48dhv@gmal.com
5.2. Các thuật toán định tuyến
5.2.1. Thuật toán tìm đƣờng đi ngắn nhất
5.2.2. Thuật toán định tuyến vector khoảng cách.
5.2.3. Thuật toán trạng thái đƣờng liên kết
5.2.4. So sánh các thuật toán
13 thanhhoa48dhv@gmal.com
Thuật toán tìm đƣờng đi
ngắn nhất
Thuật toán Bellman- Ford:
Bài toán: cho đồ thị G với các đỉnh A,B,C,D có độ dài và
đƣờng đi nhƣ hình dƣới, tìm đƣờng đi ngắn nhất từ B
đến D.
14 thanhhoa48dhv@gmal.com
Thuật toán tìm đƣờng đi
ngắn nhất
Thuật toán Bellman- Ford:
Bƣớc 0: Ta đánh dấu đỉnh xuất phát B là 0, các đỉnh còn
lại là vô cực.
15 thanhhoa48dhv@gmal.com
Thuật toán tìm đƣờng đi
ngắn nhất
Thuật toán Bellman- Ford:
Bƣớc 1: Cập nhật lại chi phí các đỉnh A,C
16 thanhhoa48dhv@gmal.com
Thuật toán tìm đƣờng đi
ngắn nhất
Thuật toán Bellman- Ford:
Bƣớc 2: Cập nhật lại chi phí các đỉnh C, D
17 thanhhoa48dhv@gmal.com
Thuật toán tìm đƣờng đi
ngắn nhất
Thuật toán Bellman- Ford:
Bƣớc 3: Cập nhật lại chi phí đỉnh D
18 thanhhoa48dhv@gmal.com
Thuật toán tìm đƣờng đi
ngắn nhất
Thuật toán Bellman- Ford:
Bài toán: Tìm đƣờng đi từ nút u đến các nút còn lại
Gọi: D(v) là độ dài đƣờng đi ngắn nhất từ một đỉnh nào
đó tới v
T(v) là đỉnh nằm phía trƣớc v trên đƣờng đi ngắn
nhất
19 thanhhoa48dhv@gmal.com
Thuật toán tìm đƣờng đi
ngắn nhất
Thuật toán Bellman- Ford:
Dùng thuật toán Bellman- Ford ta có bảng:
20
Lặp D(v), T(v) D(x), T(x) D(w), T(w) D(y), T(y) D(z), T(z)
Khởi tạo 2,u 1,u 5,u ∞,u ∞,u
K=1 2,u 1,u 4,x 2,x 10,w
K=2 2,u 1,u 3,y 2,x 8,w
K=3 2,u 1,u 3,y 2,x 4,y
K=4 2,u 1,u 3,y 2,x 4,y
thanhhoa48dhv@gmal.com
Thuật toán tìm đƣờng đi
ngắn nhất
Thuật toán Bellman- Ford:
Nhƣ vậy ta có bảng định tuyến cho nút u:
21
Network Next hop Cost
v v 2
x x 1
w x 4
y x 2
z x 4
thanhhoa48dhv@gmal.com
Thuật toán tìm đƣờng đi
ngắn nhất
Thuật toán Dijkstra:
Xét bài toán tƣơng tự nhƣ trên, xác định bảng định tuyến
của nút u:
22 thanhhoa48dhv@gmal.com
Thuật toán tìm đƣờng đi
ngắn nhất
Thuật toán Dijkstra:
Áp dụng Dijsktra ta có bảng phân tích nhƣ sau:
23
Lặp T D(v), T(v) D(x), T(x) D(w),T(w) D(y), T(y) D(z), T(z)
Khởi tạo vxwyz 2,u 1,u 5,u ∞,u ∞,u
K=1 vwyz 2,u 4,x 2,x 10,w
K=2 wyz 3,y 2,x 8,w
K=3 wz 3,y 4,y
K=4 z 4,y
K=5 Rỗng
thanhhoa48dhv@gmal.com
Thuật toán tìm đƣờng đi
ngắn nhất
Thuật toán Dijkstra:
Từ bảng phân tích ta có bảng định tuyến của nut u là:
24
Network Next hop Cost
v v 2
x x 1
w x 3
y x 2
z x 4
thanhhoa48dhv@gmal.com
Thuật toán Vector khoảng cách
Distance Vector gồm 2 phần: Distance và
Vector. Trong đó:
- Distance là khoảng cách (metric) để đến đích
- Vector là hƣớng để đi đến đích, nó đƣợc xác
định bởi next-hop của tuyến đƣờng.
Mỗi Router chỉ cần biết 2 yếu tố khi chọn
đƣờng: chọn theo hƣớng nào, khoảng cách tới
đích là bao nhiêu.
25 thanhhoa48dhv@gmal.com
Thuật toán Vector khoảng cách
26
Là thuật toán nhằm chọn ra đƣờng đi tốt nhất
đến đích dựa trên Bellman- Ford
thanhhoa48dhv@gmal.com
Thuật toán Vector khoảng cách
Các giao thức sử dụng Distance Vector gửi
các cập nhật định tuyến theo chu kỳ hoặc khi
cấu trúc mạng có sự thay đổi.
Mỗi Router sẽ gửi toàn bộ bảng định tuyến của
mình cho các Router kết nối trực tiếp với nó.
Khi tất cả các Router cập nhật đầy đủ thông tin
về các tuyến đƣờng tới các mạng đích =>
mạng đã hội tụ.
27 thanhhoa48dhv@gmal.com
Thuật toán Vector khoảng cách
Ưu điểm:
- Giao thức đơn giản, cấu hình dễ dàng, dễ
duy trì và sử dụng.
- Thích hợp với các mạng quy mô nhỏ.
Nhược điểm:
- Khi xảy ra sự cố hoặc có thay đổi trong mạng
thì cần thời gian để hội tụ.
- Có thể xảy ra lặp do những mâu thuẫn giữa
các lần định tuyến.
=> Chậm hội tụ, không thích hợp với mạng
lớn
28 thanhhoa48dhv@gmal.com
Thuật toán trạng thái đƣờng
liên kết
Các Router tự thu tập thông tin về đƣờng đi
của mạng từ tất cả các Router khác.
Mỗi Router sẽ tự tính toán để chọn đƣờng đi
tốt nhất cho nó đến các mạng đích.
Sử dụng các gói tin Hello để mang thông tin về
các mạng kết nối trực tiếp vào Router.
Sử dụng các gói tin LSA mang thông tin cập
nhật về trạng thái đƣờng liên kết của các
Router khác trong mạng.
29 thanhhoa48dhv@gmal.com
Thuật toán trạng thái đƣờng
liên kết
Cơ chế hoạt động:
- Sử dụng thông tin từ gói tin Hello và LSA
nhận đƣợc từ Router hàng xóm để xây dựng
cơ sở dữ liệu về cấu trúc hệ thống mạng.
- Sử dụng thuật toán SPF (Dijkstra) để tìm ra
đƣờng ngắn nhất đến từng mạng.
- Lƣu kết quả chọn đƣờng trong bảng định
tuyến
30 thanhhoa48dhv@gmal.com
Thuật toán trạng thái đƣờng
liên kết
Ưu điểm:
- Thời gian hội tụ mạng nhanh hơn.
- Mỗi router có một sơ đồ đầy đủ và đồng bộ
về toàn bộ cấu trúc hệ thống mạng. Do đó
chúng rất khó bị vòng lặp.
- Router sử dụng thông tin mới nhất để quyết
định chọn đƣờng đi.
- Các giao thức định tuyến trạng thái đƣờng
liên kết có hỗ trợ chia mạng con và phân
vùng.
31 thanhhoa48dhv@gmal.com
Thuật toán trạng thái đƣờng
liên kết
Nhược điểm:
- Đòi hỏi Router phải có nhiều dung lƣợng bộ
nhớ và năng lực xử lý cao hơn.
- Đòi hỏi hệ thống mạng thiết kế theo mô hình
phân cấp.
- Tiến trình phát các gói tin LSA có thể chiếm
dụng nhiều dung lƣợng đƣờng truyền
32 thanhhoa48dhv@gmal.com
5.3. Một số giao thức định tuyến
Giao thức RIP (Routing Information Protocol)
Giao thức IGRP (Interior Gateway Routing
Protocol)
Giao thức OSPF (Open Short Path First)
33 thanhhoa48dhv@gmal.com
Giao thức định tuyến RIP
RIP là giao thức định tuyến véc tơ khoảng
cách.
RIP gửi toàn bộ bảng định tuyến ra tất cả các
cổng đang hoạt động đều đặn theo chu kỳ là
30 giây.
RIP sử dụng Metric là hop count để tính ra
tuyến đƣờng tốt nhất đến đích.
Thuật toán mà RIP sử dụng để xây dựng nên
bảng định tuyến là Bellman-Ford.
34 thanhhoa48dhv@gmal.com
Giao thức định tuyến RIP
Các giá trị thời gian:
- Update time: 30 giây
- Invalid time: 180 giây
- Holddown time: 180 giây
- Flush time: 240 giây.
35 thanhhoa48dhv@gmal.com
Giao thức định tuyến RIP
Cơ chế hoạt động:
- Tất cả các gói tin của RIP đều đƣợc đóng gói
vào UDP segment với cả hai trƣờng source
và destination Port là 520.
- Request message: đƣợc sử dụng để gửi một
yêu cầu tới router hàng xóm để gửi update.
- Reponse message: mang thông tin update
36 thanhhoa48dhv@gmal.com
Giao thức định tuyến RIP
Cơ chế hoạt động:
- Router gửi broadcast bản tin Request ra tất
cả các cổng đang hoạt động => đợi
- Các router hàng xóm nhận đƣợc các Request
message rồi gửi Response message chứa
toàn bộ bảng định tuyến
- Khi nhận đƣợc thông tin định tuyến:
→ tuyến đƣờng đang tồn tại sẽ bị thay thế bởi
tuyến đƣờng mới có hop count nhỏ hơn.
→ bỏ qua nếu hop count lớn hơn
37 thanhhoa48dhv@gmal.com
Giao thức định tuyến RIP
Cấu trúc gói tin RIP:
38 thanhhoa48dhv@gmal.com
Giao thức định tuyến IGRP
IGRP là giao thức định tuyến véc tơ khoảng
cách, có chu kỳ update là 90 giây.
IGRP không sử dụng hopcount trong metric
của mình, tuy nhiên nó vẫn theo dõi đƣợc
hopcount.
Kích thƣớc của mạng cài đặt IRGP có thể lên
tới 255 hop.
39 thanhhoa48dhv@gmal.com
Giao thức định tuyến IGRP
Các giá trị về thời gian:
- Update time: 90 giây
- Invalid time: 270 giây
- Holddown time: 280 giây
- Flush timer: 630 giây
40 thanhhoa48dhv@gmal.com
Giao thức định tuyến IGRP
Cơ chế hoạt động:
- IGRP gửi broadcast Request packet tới tất cả
các Router kết nối trực tiếp với nó.
- IGRP sử dụng 3 loại tuyến đƣờng sau trong
thông tin cập nhật:
Đƣờng nội bộ (Interior route): đƣờng nối trực
tiếp với Router
Đƣờng hệ thống (System route): là những
đƣờng đi giữa các mạng trong cùng một AS.
Đƣờng ngoại vi (Exterior route): là những
đƣờng đi ra ngoài AS.
41 thanhhoa48dhv@gmal.com
Giao thức định tuyến IGRP
Cấu trúc gói tin IGRP:
42 thanhhoa48dhv@gmal.com
Giao thức định tuyến OSPF
OSPF là giao thức định tuyến theo trạng thái
đƣờng liên kết, sử dụng thuật toán Dijkstra.
OSPF có ƣu điểm là hội tụ nhanh, hỗ trợ mạng
có kích thƣớc lớn và không xảy ra vòng lặp
định tuyến.
OSPF có thể chia một AS thành nhiều vùng
(Area) khác nhau để giảm lƣu lƣợng định
tuyến, dễ quản trị.
Là giao thức hỗ trợ chia mạng con
43 thanhhoa48dhv@gmal.com
Giao thức định tuyến OSPF
Cơ chế hoạt động: gồm có 3 hoạt động
- Tìm kiếm và xác lập mối quan hệ với Router
hàng xóm.
- Trao đổi cơ sở dữ liệu (LSDB exchange).
- Sử dụng thuật toán Dijkstra để tính toán con
đƣờng tốt nhất đặt vào bảng định tuyến.
44 thanhhoa48dhv@gmal.com
Bài tập định tuyến
Sử dụng thuật toán Bellman –Ford, Dijkstra lập
bảng định tuyến cho Node A
45 thanhhoa48dhv@gmal.com
A
B
D
C
G
E
F
H
3
5
2
7
1
4
3
6
4
6
2
3
5
1
Đề kiểm tra lại
Cho địa chỉ IP: 192.168.10.210/27
1. Cho biết địa chỉ IP trên thuộc mạng có chia
mạng con không? Tại sao?
2. Tìm địa chỉ mạng, địa chỉ broadcast và dải
đia chỉ host của mạng con chứa IP trên.
3. Hãy chia mạng con vừa tìm đƣợc thành 4
mạng con mới, liệt kê các địa chỉ mạng, địa
chỉ Broadcast, dải địa chỉ host của 4 mạng
con này.
46 thanhhoa48dhv@gmal.com
Kiểm tra
47
Cho địa chỉ IP của một số Host nhƣ sau:
IP1: 134.135.30.10/20
IP2: 134.135.40.100/20
IP3: 134.135.50.20/20
IP4: 134.135.60.70/20
Hãy cho biết trong các host trên, host nào nằm
cùng mạng con.
Hãy cho biết địa chỉ mạng con đó, địa chỉ
Broadcast của mạng và liệt kê các host hợp lệ,
tính số lƣợng host trong mạng?
Bài tập
Giả sử ta có một địa chỉ Host là:
172.16.40.32/255.255.240.0
1. Host trên thuộc mạng có chia mạng con
không? tại sao? Nếu có thì có bao nhiêu
mạng con và mỗi mạng con có bao nhiêu
host.
2. Tìm địa chỉ mạng, địa chỉ Broadcast của
mạng chứa host trên
3. Liệt kê dãy địa chỉ host của mạng con vừa
tìm đƣợc
48 thanhhoa48dhv@gmal.com
Bài tập
Cho hệ thống mạng gồm 228 host và địa chỉ IP
đƣợc thiết lập ở lớp 192.168.1.0/24. Hãy chia hệ
thống này thành 4 mạng con (Net 1: 120 host,
Net 2: 60 host, Net 3: 30 host, Net 4: 18 host)
dựa theo kỹ thuật VLSM gồm các thông tin:
- Địa chỉ mạng con (Network ID)
- Subnet Mask của mạng con
- Dải địa chỉ host của mỗi mạng con
- Địa chỉ Broadcast
- Diệp hoàng bảo bảo
49 thanhhoa48dhv@gmal.com
Các file đính kèm theo tài liệu này:
- bai_gi_ng_c5_1503.pdf