5/22/2011
LOGO
C4
TẦNG MẠNG
(cid:61558) Giới thiệu
(cid:61558)Giao thức IP
(cid:61558)Định tuyến
Biên soạn : Lê Minh
LOGO
I
Giới thiệu
application transport network data link physical
(cid:61558)Chuyển các segment từ máy tính gởi tới máy tính nhận
network data link physical
network data link physical
network data link physical
network data link physical
network data link physical
network data link physical
network data link physical
network data link physical
(cid:61558)Các giao thức tầng mạng hoạt động trên tính máy cả gởi/nhận và các thiết bị mạng trung gian ( router)
application transport network data link physical
Biên soạn : Lê Minh
1
5/22/2011
LOGO
I
Giới thiệu
application transport network data link physical
network data link physical
network data link physical
network data link physical
(cid:61558)Máy tính gởi: nhận các segment từ tầng giao vận, đóng gói thành datagram
network data link physical
(cid:61558)Máy
network data link physical
network data link physical
network data link physical
network data link physical
nhận: tính chuyển các segment lên tầng giao vận (cid:61558)Router: kiểm tra và các
tiếp
application transport network data link physical
chuyển datagram
Biên soạn : Lê Minh
LOGO
I
Giới thiệu
(cid:61558)Chức năng cơ bản của tầng mạng:
(cid:61607) Định tuyến (routing): xác định đường đi cho các gói tin để có thể đi từ nơi gởi tới nơi nhận • Chạy các thuật toán định tuyến ở các router để
xác định “đường đi”
(cid:61607) Chuyển tiếp (forwarding): chuyển các gói tin từ ngõ vào của router đến ngõ ra tương ứng của nó
Biên soạn : Lê Minh
2
5/22/2011
LOGO
I
Giới thiệu
(cid:61558)Các giao thức của tầng mạng:
Giao thức định tuyến •Lựa chọn đường đi •RIP, OSPF, BGP
Giao thức IP •Định địa chỉ IP •Định dạng gói tin datagram •Nguyên tắc xử lý datagram
Network layer
Transport layer: TCP, UDP
Giao thức ICMP •Thông báo lỗi •Trao đổi thông tin
forwarding table
Link layer
Biên soạn : Lê Minh
physical layer
LOGO
II
Giao thức IP
(cid:61558)Đặc điểm:
(cid:61607) Là giao thức không hướng kết nối (cid:61607) Là giao thức không tin cậy
(cid:61558)Quy định:
(cid:61607) Định dạng gói
tin của tầng mạng (IP
datagram)
(cid:61607) Cách thức đánh địa chỉ IP cho hệ thống (cid:61607) Cơ chế phân mảnh và hợp nhất các datagram
Biên soạn : Lê Minh
3
5/22/2011
LOGO
1
Định dạng IP datagram
32 bits Chiều dài cả datagram (bytes) type of head. length ver len Phiên bản Giao thức IP Chiều dài header (bytes) Kiểu dữ liệu flgs Dùng đề Phân mảnh/ hợp nhất gói tin Thời gian sống service 16-bit identifier upper time to layer live fragment offset Internet checksum
32 bit source IP address
Dữ liệu (độ lớn không cố định, Thường là một TCP hay UDP segment)
Biên soạn : Lê Minh
32 bit destination IP address Kiểu giao thức của tầng trên Tùy chọn Options (if any)
LOGO
1
Định dạng IP datagram
32 bits
type of head. length ver len flgs
service 16-bit identifier upper time to layer live fragment offset Internet checksum
32 bit source IP address
32 bit destination IP address
Dữ liệu (độ lớn không cố định, Thường là một TCP hay UDP segment)
Biên soạn : Lê Minh
Options (if any)
4
5/22/2011
LOGO
2
Phân mảnh và hợp nhất các datagram
(cid:61558)Mỗi đường truyền có MTU khác nhau: độ dài của lớn nhất frame dữ liệu
(cid:61558)Các IP datagram lớn được chia nhỏ bên trong mạng: (cid:61607) Mỗi datagram trở nhiều
thành datagram nhỏ hơn
(cid:61607) Hợp
Biên soạn : Lê Minh
các nhất datagram ở đích cuối cùng
LOGO
2
Phân mảnh và hợp nhất các datagram
(cid:61558)Ví dụ: IP datagram có chiều dài 4000 byte
trên đường truyền có MTU 1500 byte
length =4000 ID =x fragflag =0 offset =0
chia ra thành các
(cid:61607) Datagram này được datagram nhỏ hơn:
length =1500 ID =x fragflag =1 offset =0
length =1500 ID =x fragflag =1 offset =1480
Biên soạn : Lê Minh
length =1040 ID =x fragflag =0 offset =2960
5
5/22/2011
LOGO
3
Địa chỉ IP V.4
223.1.1.1
223.1.2.1
223.1.1.2
223.1.1.4 223.1.2.9
223.1.2.2
223.1.3.27
223.1.1.3
(cid:61558)Địa chỉ IP: 1 con số 32 bit dùng để định danh cho cổng (interface) của các thiết bị trên mạng (cid:61558)Cổng: kết nối các thiết bị với đường truyền vật lý
223.1.3.2
223.1.3.1
Biên soạn : Lê Minh
LOGO
3
Địa chỉ IP v.4
(cid:61558)Thành phần của địa chỉ IP v.4:
(cid:61607) Cách viết: 32 bit được chia thành 4 octet, mỗi octet cách nhau một dấu chấm. Thường được viết dạng thập phân xxx.xxx.xxx.xxx
(cid:61607) Gồm 3 thành phần chính:
• Class bit: bit nhận dạng lớp • Net ID: phần nhận dạng mạng • Host ID: phần nhận dạng máy
Biên soạn : Lê Minh
6
5/22/2011
LOGO
3
Địa chỉ IP v.4
(cid:61558)Phân lớp địa chỉ IPv4: chia thành 5 lớp
Host (24 bits)
0
A,B,C,D và E (cid:61607) Lớp A:
Network (7 bits)
0 1
(cid:61607) Lớp B:
Host (16bits)
Network( 14 bits)
110
(cid:61607) Lớp C:
Host (8bits)
Network( 21 bits)
Multicast address
1110
(cid:61607) Lớp D:
Future use addresses
(cid:61607) Lớp E:
Biên soạn : Lê Minh
1111
LOGO
3
Địa chỉ IP v.4
(cid:61558) Nguyên tắc: không dùng các IP có tất cả các bit của phần host id bằng 1 và bằng 0 để đánh địa chỉ (cid:61558)Lớp A:
(cid:61607) Net id: phạm vi 1 - 126 (cid:61607) Host id: phạm vi 0.0.1 – 255.255.254 (cid:61607) Ví dụ: 110.10.3.5
• Địa chỉ mạng? Địa chỉ máy?
(cid:61607) Số lượng mạng lớp A? Số lượng máy trên mỗi
Biên soạn : Lê Minh
mạng?
7
5/22/2011
LOGO
3
Địa chỉ IP v.4
(cid:61558)Lớp B:
(cid:61607) Net id: phạm vi 128.0 – 191.255 (cid:61607) Host id: phạm vi 0.1 – 255.254 (cid:61607) Ví dụ: 151.2.255.4
• Địa chỉ mạng? Địa chỉ máy? • 1 IP khác cùng địa chỉ mạng với IP trên?
(cid:61607) Số lượng mạng lớp B? Số lượng máy trên mỗi
mạng?
Biên soạn : Lê Minh
LOGO
3
Địa chỉ IP v.4
(cid:61558)Lớp C:
(cid:61607) Net id: phạm vi 192.0.0 – 223.255.255 (cid:61607) Host id: phạm vi 1 – 254 (cid:61607) Ví dụ: 203.0.1.254
• Địa chỉ mạng? Địa chỉ máy? • 1 IP khác cùng địa chỉ mạng với IP trên?
(cid:61607) Số lượng mạng lớp C? Số lượng máy trên mỗi
mạng?
Biên soạn : Lê Minh
8
5/22/2011
LOGO
3
Địa chỉ IP v.4
(cid:61558)Các thiết bị (máy tính, router…) xác định địa
chỉ mạng và địa chỉ máy như thế nào? (cid:61607) Mặt nạ mạng (net mask): (cid:61607) Vd:
• IP: 154.210.2.65 • net mask: 255.255.0.0
(cid:61558)Quy định viết địa chỉ: IP/số bit 1 của mask
(cid:61607) Vd: 154.210.2.65/16
Biên soạn : Lê Minh
LOGO
3
Địa chỉ IP V.4
(cid:61558)Mạng con (subnet):
(cid:61607) Lấy thêm một số bit của phần host id làm net
id (subnet id)
(cid:61607) Xác định bằng mặt nạ mạng con (subnet mask)
• Vd: 223.2.5.129/ 26 • Địa chỉ mạng? Địa chỉ máy (host)? Mặt nạ
Biên soạn : Lê Minh
mạng con (subnet mask)?
9
5/22/2011
LOGO
3
Địa chỉ IP V.4
(cid:61558)Mạng con (subnet):
(cid:61607) Số lượng mạng con tạo ra được từ 1 địa chỉ
mạng gốc: (2n) mạng • n : số bit lấy từ phần host id ban đầu • Vd:
– địa chỉ mạng lớp C gốc 223.2.5.0/24, lấy 2 bit của
phần host id để chia subnet.
– Số lượng mạng con có thể thành lập từ địa chỉ mạng
này là 22 = 4 mạng
Biên soạn : Lê Minh
LOGO
3
Địa chỉ IP v.4
(cid:61558)Một số địa chỉ IP đặc biệt:
(cid:61607) Địa chỉ loopback: 127.0.0.1 (cid:61607) Địa chỉ mạng : địa chỉ có tất cả các bit của
phần host id bằng 0
(cid:61607) Địa chỉ quảng bá (broadcast) địa chỉ có tất cả
các bit của phần host id bằng 1
(cid:61607) 255.255.255.255 : địa chỉ quảng bá cục bộ (local
broadcast)
Biên soạn : Lê Minh
10
5/22/2011
LOGO
3
Địa chỉ IP v.4
(cid:61558)IP riêng (private) và IP chung (puplic):
(cid:61607) IP riêng: dành riêng cho các mạng nội bộ
• Mạng riêng lớp A: 10.0.0.0 /8 • Mạng riêng lớp B: 172.16.0.0 /12 • Mạng riêng lớp C: 192.168.0.0 /16
(cid:61607) IP chung: được quản lý bởi tổ chức InterNic
Biên soạn : Lê Minh
LOGO
III
Định tuyến
(cid:61558)Mục tiêu: xác định đường đi “tốt nhất” trên
mạng từ nút gởi đến nút nhận
v
w
u
z
y
5 3 5 2 1 3 1 2 2 x 1
(cid:61558)Việc định tuyến được thực hiện bởi các router (cid:61607) Chạy các thuật toán định tuyến để xác định
đường đi
(cid:61607) Mỗi router sẽ có 1 bảng định tuyến (routing
table)
Biên soạn : Lê Minh
11
5/22/2011
LOGO
III
Định tuyến
(cid:61558)Dùng đồ thị để xây dựng các thuật toán định
tuyến
v
w
u
z
y
5 3 5 2 1 3 1 2 2 x 1
(cid:61607) Nút : các router (cid:61607) Đường liên kết (link): kết nối trực tiếp các nút
với nhau
Biên soạn : Lê Minh
LOGO
III
Định tuyến
v
w
u
z
y
5 3 5 2 1 3 1 2 2 x 1
(cid:61607) Chi phí đường liên kết (cost of link, ký hiệu c(a, b) ): phụ thuộc vào băng thông, mức độ tắt nghẽn, thời gian trễ … • Ví dụ: c(u,w) = 5
(cid:61607) Chi phí đường đi (cost of path) : tổng chi phí
của các đường liên kết từ nguồn tới đích (cid:61558)Định tuyến : xác định đường đi có tổng chi phí
Biên soạn : Lê Minh
đường đi nhỏ nhất từ nguồn tới đích
12
5/22/2011
LOGO
1
Phân loại thuật toán định tuyến
(cid:61558)Theo quy mô: định tuyến toàn cục (global routing) hay phân tán (decentralized routing) (cid:61607) Toàn cục:
• Các router phải có đầy đủ thông tin về topology
của mạng cũng như link cost
• Thuật toán Link State
(cid:61607) Phân tán:
• Router chỉ biết các thông tin về router láng
giềng (kết nối trực tiếp) tới nó
• Thuật toán Distance vector
Biên soạn : Lê Minh
LOGO
1
Phân loại thuật toán định tuyến
(cid:61558)Theo tính chất: định tuyến tĩnh (static routing) hay định tuyến động (dynamic routing) (cid:61607) Tĩnh:
• Thông số định tuyến thường ít thay đổi theo
thời gian
(cid:61607) Động:
• Thông số định tuyến thay đổi nhanh chóng theo chu kỳ hoặc theo sự thay đổi cấu trúc đường truyền
Biên soạn : Lê Minh
13
5/22/2011
LOGO
2
Định tuyến tĩnh
(cid:61558)Bảng định tuyến (routing table) của mỗi router trên hệ thống được thiết lập bởi người quản trị
(cid:61558)Không tự động cập nhật bảng định tuyến khi
có sự thay đổi về cấu trúc mạng
(cid:61558)Thiết lập bảng định tuyến cho router: dùng
câu lệnh (cid:61607) ip route địa chỉ mạng đích netmask exit interface (cid:61607) ip route địa chỉ mạng đích netmask next-hoop interface address
Biên soạn : Lê Minh
LOGO
2
Định tuyến tĩnh
(cid:61558)Ví dụ: cho hệ thống mạng
(cid:61607) Định tuyến tĩnh cho các router?? (cid:61607) Kết quả: mophong\static_routing.pkt
Biên soạn : Lê Minh
14
5/22/2011
LOGO
3
Thuật toán định tuyến Link state
(cid:61558)Thuật toán Dijkstra
(cid:61607) Tất cả các nút mạng đều biết được topo mạng
và chi chí các đường liên kết của cả mạng
(cid:61607) Tính toán chi phí đường đi thấp nhất từ một
nút (nguồn) đến tất cả các nút còn lại
(cid:61607) Sau một vài bước tính toán sẽ xác định được
chi phí đường đi thấp nhất tới nút đích
(cid:61607) Ký hiệu:
• c(x,y) : chi phí đường liên kết từ nút x tới nút y, = ∞ nếu
nút y không kết nối trực tiếp tới x
• D(v): chi phí đường đi hiện tại từ nguồn tới v • p(v): nút kế cận trước v trên đường đi tới v • N: tập hợp các nút đã xác định được đường đi
Biên soạn : Lê Minh
LOGO
3
Thuật toán định tuyến Link state
(cid:61558)Hoạt động: khởi tạo: N' = {u} for( tất cả các nút v)
if (v kết nối trực tiếp với u ) then ( D(v) = c(u,v) )
else D(v) = ∞
Lặp :
Tìm nút w không ở trong N' có D(w) nhỏ nhất thêm w vào N' Cập nhật D(v) cho tất cả các nút v
kết nối trực tiếp tới w và không ở trong N' :
D(v) = min( D(v), D(w) + c(w,v) )
dừng lại khi tất cả các nút đều có trong N'
Biên soạn : Lê Minh
15
5/22/2011
LOGO
3
Thuật toán định tuyến Link state
(cid:61558)Ví dụ:
5
v
w
u
z
y
x
D(x),p(x) 1,u
D(y),p(y) ∞ 2,x
D(v),p(v) 2,u 2,u 2,u
D(w),p(w) 5,u 4,x 3,y 3,y
D(z),p(z) ∞ ∞ 4,y 4,y 4,y
Bước 0 1 2 3 4 5
N' u ux uxy uxyv uxyvw uxyvwz
Biên soạn : Lê Minh
3 5 2 2 1 3 1 2 1
LOGO
4
Thuật toán định tuyến Distance Vector
(cid:61558)Ý tưởng:
5
v
w
u
z
y
x
3 5 2 2 1 3 1 2
(cid:61607) Gọi dv(z): chi phí đường đi thấp nhất từ v tới z (cid:61607) c(u,v) : chi phí đường liên kết từ u tới nút v kế cận với nó
(cid:61607) Khi đó: (cid:61607) du(z) = min{c(u,v)+ dv(z)
1
,c(u,x) + dx(z), c(v,w) + dw(z)} = min{ 2 + 5, 1 + 3, 5 + 3 } = 4
Biên soạn : Lê Minh
16
5/22/2011
LOGO
4
Thuật toán định tuyến Distance Vector
(cid:61558)Thuật toán D-V:
(cid:61607) Mỗi nút:
5
v
w
u
z
y
x
3 5 2 2 1 3 1 2
• Biết chi phí đường link (c ) từ nó tới các nút kế cận • Biết chi phí đường đi (d ) nhỏ nhất từ các nút kế cận tới nút đích
1 (cid:61607) Việc gởi ( quảng bá) thông số được tiến hành theo chu kỳ
• Tính toán đươc chi phí đường đi nhỏ nhất từ nó tới đích
(cid:61607) Mỗi nút sẽ gởi thông số chi phí đường đi nhỏ nhất từ nó tới đích cho các nút kế cận
Biên soạn : Lê Minh
LOGO
4
Thuật toán định tuyến Distance Vector
(cid:61558)Ví dụ:
y
x
z
2 1
Biên soạn : Lê Minh
7
17
5/22/2011
LOGO
5
Định tuyến phân cấp
(cid:61558)Chia các router thành các vùng nhỏ, gọi là các
miền tự quản (AS: Autonomous System)
3c
3a
2c
3b
2a
AS3
2b
1c
1a
1b
AS1
AS2
1d (cid:61558)Các router trong cùng một miền AS chạy cùng một thuật toán định tuyến nội miền ( intra-AS routing protocol)
(cid:61558)Các router trong các miền AS khác nhau có thể chạy các thuật toán định tuyến khác nhau
Biên soạn : Lê Minh
LOGO
5
Định tuyến phân cấp
(cid:61558)Gateway Router : nối các miền AS lại với
Gateway Router
nhau
3c
3a
2c
3b
2a
AS3
2b
1c
1a
1b
AS1
1d
Intra-AS Routing algorithm
Inter-AS Routing algorithm
Routing table
AS2
(cid:61607) Chạy các thuật toán: • Định tuyến nội miền (Intra-AS routing) • Định tuyến liên miền (Inter-AS routing)
Biên soạn : Lê Minh
18
5/22/2011
LOGO
6
Giao thức định tuyến động
(cid:61558)Các giao thức định tuyến nội miền : RIP,
OSPF, EIGRP
(cid:61558)Giao thức định tuyến liên miền : BGP (cid:61558)RIP (Routing Information Protocol) (cid:61607) Dùng thuật toán Distance Vector (cid:61607) Chi phí đường đi : số lượng router sẽ phải qua
để tới đích (hoop-count)
(cid:61607) Trao đổi bảng định tuyến theo chu kỳ 30s
(cid:61558)OSPF (Open Shortest Path First)
(cid:61607) Dùng thuật toán định tuyến Link State
Biên soạn : Lê Minh
