1
Computer Networks
Dynamic Routing : Distance Vector and Link State Protocol ,
Routing Algorithm , RIP and OSPF
Định tuyến động, thuậttoánđịnh tuyến, giao thức RIP và OSPF
Người thực hiện : Nguyễn Huy Thành
Chu Anh Dũng
Bùi Thị Thanh Hường
Nội dung seminar
•Kháiniệmcơ bảnvềđịnh tuyến
•Thuật toán định tuyến
• Định tuyến động
 Distance vector , RIP
 Linkstate , OSPF
Tài liệu tham khảo:
1. Computer Networks - Andrew S. Tanenbaum
2. Cisco Networking Academy Program
3. Wikipedia
4. Bài giảng nhập môn MMT – GV Hồ Đắc Phương ĐHQGHN
5. Internet resources
2
Nội dung seminar
• Khái niệmcơ bảnvềđịnh tuyến
•Thuật toán định tuyến
• Định tuyến động
 Distance vector , RIP
 Linkstate , OSPF
Tài liệu tham khảo:
1. Computer Networks - Andrew S. Tanenbaum
2. Cisco Networking Academy Program
3. Wikipedia

Để truyền dữ liệu cho PC2 , PC1 phải truyền dữ liệu cho R1, R1 sẽ
gửi cho R2 , sau đó R2 sẽ gửi cho R3 , và cuối cùng là Pc2.Cách
thức gửi gói tin ở mỗi thiết bị là ko như nhau , chúng biến đổi rất
mềm dẻo
Layer 3 Protocol
Định tuyến hoạt động ở lớp 3 trong mô hình OSI, dựa trên nền địa chỉ IP
5
Các thành phần,khái niệm liên quan đến định tuyến
9 Bảng định tuyến : dùng để lưu các địa chỉ mạng mà router
biết
9 Thông sốđịnh tuyến (Routing metrics):các giao thức định
tuyếndựavàometric để lựachọn đường đi cho router , mỗi
giao thức có cách tính metric riêng , RIP dựavàosố hop ,
OSPF dựa vào cost.
9 Giao thức định tuyến (routing protocols):router sd các giao
thức định tuyến để duy trì bảng định tuyếnvàtraođổi thông
tin với các router lân cận
Vd: RIP , OSPF , IGRP , EIGRP
9 Convergence time (thờigianhộitụ ):
Khoảng thờ
i gian tính từ lúc router mất1 tuyếnvàtìmđược
tuyếnkhácđể thay thế gọilàConvergence time
Tham khảo : />Bảng định tuyến và thông sốđịnh tuyến
Bảng định tuyến và thông sốđịnh tuyến
Network
Protocol
Destination
Network
Connected
Learned

7
Định tuyếntĩnh
•Định tuyến tĩnh:đường đi được xác định trước , ko thay đổi trong quá trình
định tuyến, định tuyến tĩnh sử dụng trong các mạng có ít máy ,việc cấu hình
là đơn giản
•Người quản trị sẽ cấu hình định tuyến tĩnh bao gồm : các mạng đích sẽ đến
thông qua interface nào !Cũng như định tuyến động , mục đích của việc cấu
hình (configuring) cho router là đưa các tuyến vào bảng định tuy
ến.Router
chỉ gửi các gói tin tới các địa chỉ đích có trong bảng định tuyến
•Nhược điểm : kém linh động , không thích nghi được với sự thay đổi của
mạng
Định tuyến động
• Định tuyến động : các router sử dụng các giao thức định tuyến để gửi
thông tin định tuyến cho các router mà nó biết, các router khác sẽ cập nhật
các thông tin định tuyến,và tiếp tục gửi đi các thông tin định tuyến của nó
cho các router lân cận, quá trình diễn ra liên tiếp tạo ra các tuyến thông
suốt kết nối các mạng với nhau.
• Định tuyến động sử dụng trong các mạng có số lượng thiết bị lớn
VD : RIP , OSPF , IGRP (Cisco)
8
Phân loại định tuyến động
Để tránh các hiện tượng routing loop(lặp đường đi) người ta phải kết
hợp với các thuật toán định tuyến để đưa ra các giao thức định
tuyến.Dựa vào cơ chế hoạt động của giao thức định tuyến , người ta
chia định tuyến động ra làm 2 loại cơ bản :
+ Distance Vector vd : RIP, IGRP
+ Link-State vd : OSPF , IS-IS
Nội dung seminar
•Kháiniệmcơ bảnvềđịnh tuyến

•Trọng số = chi phí (cost): độ trễ, độ nghẽn mạng, cước phí…
• Đường đi tốt = đường đi có “chi phí” thấp nhất.
Phân loại thuật toán định tuyến
Thông tin tập trung hay phân tán?
 Tập trung:
•mỗi router phảinắmgiữ thông
tin toàn bộ mạng (topology, link
cost…)
•“link state” algorithms
 Phân tán:
• router nắm được chi phí truyền
tin tới các router đượcnốitrực
tiếpvới mình (hàng xóm)
• quá trình tính toán mang tính
chấtlặp đilặplại, trao đổi thông
tin giữa các routers.
•“distance vector” algorithms
Tĩnh hay động?
 Tĩnh:
• đường đi ít thay đổi
 Động:
• đường đi thay đổi
thường xuyên
• các thông tin dẫn
đường đượ
c cập nhật
định kỳ.
• link cost thay đổi.
10
A Link-State Routing Algorithm

5,A
4,D
3,E
3,E
D(D),p(D)
1,A
D(E),p(E)
∞
2,D
D(F),p(F)
∞
∞
4,E
4,E
4,E
A
E
D
CB
F
2
2
1
3
1
1
2
5
3
5

9
11
D
5
5
4
2
E
cost to destination via
d
e
s
t
i
n
a
t
i
o
n
A
B
C
D
A,1
D,5
D,4
D,4
Outgoing link
to use, cost

A
1
7
6
4
B
14
8
9
11
D
5
5
4
2
E
cost to destination via
d
e
s
t
i
n
a
t
i
o
n
D (C,D)
E

•O(n
2
), nE msgs
•Mỗi nút chỉ tính toán bảng dẫn
đường cho riêng mình.
Distance Vector
•Chỉ nắmgiữ thông tin liên quan tới
các nút “hàng xóm”
• msgs chỉ đượcgửi cho các nút
“hàng xóm”.
•tốc độ hộitụ có thể khác nhau tuỳ
từng tình huống, đôi khi rơivào
trạng thái lặpvôhạn.
• Thông tin dẫn đường của nút này
đượcsử dụng bởi nút khác.
–Mộtnútgặpsự cố có thể gây ảnh
hưởng tới các nút khác.
13
Other routing algorithms
• Routing in Ad-hoc networks
• Routing in Mobile Systems
Nội dung seminar
•Kháiniệmcơ bảnvềđịnh tuyến
•Thuật toán định tuyến
• Định tuyến động
 Distance vector , RIP
 Linkstate , OSPF
14
Distance Vector Routing Protocols
Distance Vector Routing Protocols

Routing
Table
Routing
Table
Distance—How Far
Vector—In Which Direction
Distance—How Far
Vector—In Which Direction
Duy trì thông tin bảng định tuyến
Duy trì thông tin bảng định tuyến
Updates proceed step-by-step
from router to router.
A
A
B
B
Process to
Update This
Routing
Table
Process to
Update This
Routing
Table
Process to
Update This
Routing
Table
Process to
Update This

trên metric
9 Router gửicácbản tin update định kỳ
và cũng đợi để nhậncácbản tin update
định kỳ từ các router khác
9 Nếu sau 1 khoảng thờigiannhất định mà router không nhận đươợ bảntin
update từ hàng xóm thì nó sẽ loạibỏ tuyếnmànóđãhọc đượctừ router đó
.
Maintaining Routing Information
Problem:Routing Loops
Maintaining Routing Information
Problem:Routing Loops
• Each node maintains the distance from itself to each possible destination
network.
A
A
B
B
C
C
10.1.0.0 10.2.0.0 10.3.0.0 10.4.0.0
E0 S0
S0 S1 S0 E0
Routing Table
Routing Table
10.3.0.0
S0
E0
S0
S0
1

S0
1
1
1
1
10.1.0.0
10.4.0.0
10.3.0.0
0
0
16
Maintaining Routing Information Problem—
Routing Loops
Maintaining Routing Information Problem—
Routing Loops
• Each node maintains the distance from itself to each possible destination
network.
A
A
B
B
C
C
10.1.0.0 10.2.0.0 10.3.0.0 10.4.0.0
E0 S0
S0 S1 S0 E0
Routing Table
Routing Table
10.3.0.0
S0

10.2.0.0
S0
S1
S1
S0
1
1
1
1
10.1.0.0
10.4.0.0
10.3.0.0
0
0
Maintaining Routing Information Problem—
Routing Loops (cont.)
Maintaining Routing Information Problem—
Routing Loops (cont.)
• Slow convergence produces inconsistent routing.
A
A
B
B
C
C
10.1.0.0 10.2.0.0 10.3.0.0 10.4.0.0
E0 S0
S0 S1 S0 E0
X
X

0
0
Routing Table
Routing Table
10.2.0.0
S0
S1
S1
S0
1
1
1
1
10.1.0.0
10.4.0.0
10.3.0.0
0
0
17
• Router C concludes that the best path to network
10.4.0.0 is through router B.
Maintaining Routing Information Problem—
Routing Loops (cont.)
Maintaining Routing Information Problem—
Routing Loops (cont.)
A
A
B
B
C

1
2
2
10.4.0.0
10.3.0.0
10.2.0.0
0
0
Routing Table
Routing Table
10.2.0.0
S0
S1
S1
S1
1
1
1
1
10.1.0.0
10.4.0.0
10.3.0.0
0
0
• Router A updates its table to reflect the new but
erroneous hop count.
Maintaining Routing Information Problem—
Routing Loops (cont.)
Maintaining Routing Information Problem—
Routing Loops (cont.)

S0
S0
S0
1
1
4
4
10.1.0.0
10.4.0.0
10.3.0.0
10.2.0.0
0
0
Routing Table
Routing Table
S0
S1
S1
S0
3
3
1
1
10.2.0.0
10.1.0.0
10.4.0.0
10.3.0.0
0
0
18

4
Routing Table
Routing Table
E0
S0
S0
S0
1
1
6
6
10.1.0.0
10.4.0.0
10.3.0.0
10.2.0.0
0
0
Routing Table
Routing Table
S0
S1
S1
S0
5
5
1
1
10.2.0.0
10.1.0.0
10.4.0.0

10.4.0.0
0
16
Routing Table
Routing Table
E0
S0
S0
S0
1
1
16
16
10.1.0.0
10.4.0.0
10.3.0.0
10.2.0.0
0
0
Routing Table
Routing Table
S0
S1
S1
S0
16
16
1
1
10.2.0.0

S0
S0
S0
1
1
2
2
10.1.0.0
10.2.0.0
10.4.0.0
0
0
Routing Table
Routing Table
E0
S0
S0
S0
1
1
2
2
10.1.0.0
10.4.0.0
10.3.0.0
10.2.0.0
0
0
Routing Table
Routing Table

10.3.0.0
S0
S0
S0
S0
1
1
2
2
10.1.0.0
10.2.0.0
10.4.0.0
0
Infinity
Routing Table
Routing Table
10.1.0.0
E0
S0
S0
S0
1
1
2
2
10.4.0.0
10.3.0.0
10.2.0.0
0
0

X
Routing Table
Routing Table
10.3.0.0
S0
S0
S0
S0
1
1
2
2
10.1.0.0
10.2.0.0
10.4.0.0
0
Infinity
Routing Table
Routing Table
10.1.0.0
E0
S0
S0
S0
1
1
2
2
10.4.0.0
10.3.0.0

Update After
Holddown Time
Update After
Holddown Time
Network 10.4.0.0
Is Unreachable
Network 10.4.0.0
Is Unreachable
A
A
B
B
C
C
10.1.0.0 10.2.0.0 10.3.0.0 10.4.0.0
E0 S0
S0 S1 S0 E0
X
X
Update After
Holddown Time
Update After
Holddown Time
21
Solution: Triggered Updates
Solution: Triggered Updates
• The router sends updates when a change in its routing table occurs.
A
A
B

• Nếu số Hop count bằng 15 thì gói tin gửi đi sẽ bị hủy bỏ
• Bản tin routing update sẽ được gửi đi tuần tự sau mỗi 30 giây
22
19.2 kbps
T1
T1 T1
– Maximum is 6 paths (default = 4).
– Hop-count metric selects the path.
– Routes update every 30 seconds.
RIP Overview
RIP Overview
RIPv1 vs RIPv2
• RIP Version 1 (RIPv1) requires that all devices in the
network use the same subnet mask, because it does not
include subnet mask information in routing updates. This
is also known as classful routing.
• RIP Version 2 (RIPv2) provides prefix routing, and does
send subnet mask information in routing updates. This is
also known as classless routing.
• With classless routing protocols, different subnets within
the same network can have different subnet masks. The
use of different subnet masks within the same network is
referred to as variable-length subnet masking (VLSM).
23
RIP: Example
Destination Network Next Router Num. of hops to dest.
w A2
y B2
z B7
x 1

S2E0 S3
192.168.1.1
10.1.1.1
10.2.2.2
10.1.1.2
S2 S3
10.2.2.3
172.16.1.0
A
BC
192.168.1.0
E0
Tóm tắt về Distance Vector
•Bản tin routing update gửi đi định kỳ, mỗi khi gửi router
gửi đi toàn bộ thông tin bảng định tuyến mà nó có
• RIP là 1 giao thức định tuyến Distance Vector
•Các phương pháp chống routing loop:
9 Split Horizon
9 Route Poisoning
9 Triggered Updates
9 Holddown Timers
Routing by rumor
Routing by rumor
25
Nội dung seminar
•Kháiniệmcơ bảnvềđịnh tuyến
•Thuật toán định tuyến
• Định tuyến động
 Distance vector , RIP
 Linkstate , OSPF