Trường Đại Học Bách Khoa Tp.HCM
Khoa Khoa Học và Kỹ Thuật Máy Tính

Bài giảng
Mạng máy tính
ThS. NGUYỄN CAO ĐẠT
E-mail:


Bài giảng 9: Tầng Mạng(t.t)
Tham khảo:
Chương 4: “Computer Networking – A top-down approach”
Kurose & Ross, 5th ed., Addison Wesley, 2010.

Trường Đại Học Bách Khoa Tp.HCM
Khoa Khoa Học và Kỹ Thuật Máy Tính
© 2011

MẠNG MÁY TÍNH CĂN BẢN
Bài giảng 3 - Chương 4: Tầng Mạng
2


Chương 4: Tầng Mạng





4.1 Giới thiệu
4.2 Bên trong bộ định

tuyến là gì?
4.3 IP: Internet Protocol






Định dạng gói tin
Đánh địa chỉ IPv4
ICMP
IPv6



4.4 Các giải thuật định
tuyến






4.5 Định tuyến trong
Internet




Trường Đại Học Bách Khoa Tp.HCM

Khoa Khoa Học và Kỹ Thuật Máy Tính
© 2011

Trạng thái liên kết
Véc-tơ Khoảng cách
Định tuyến phân cấp

RIP
OSPF
BGP

MẠNG MÁY TÍNH CĂN BẢN
Bài giảng 3 - Chương 4: Tầng Mạng
3


ICMP: Giao thức thơng điệp kiểm sốt Internet






sử dụng bởi máy tính và bđt để liên
lạc thơng tin tầng-mạng

báo cáo lỗi: máy, mạng, cổng,
giao thức không liên lạc được

yêu cầu/phản hồi gói echo (sử

dụng bởi ping)
nằm ở tầng “trên” IP:

th/điệp ICMP được mang trong
gói tin IP
thơng điệp ICMP: loại, mã cùng với
8 byte đầu của gói tin IP mà gây ra
lỗi

Trường Đại Học Bách Khoa Tp.HCM
Khoa Khoa Học và Kỹ Thuật Máy Tính
© 2011

Loại
0
3
3
3
3
3
3
4

Mã
0
0
1
2
3
6

7
0

8
9
10
11
12

0
0
0
0
0

Chú giải
phản hồi echo (ping)
mạng đích ko liên lạc được
máy đích ko liên lạc được
g/thức đích ko liên lạc được
cổng đích ko liên lạc được
mạng đích khơng biết
máy đích khơng biết
giảm tốc độ nguồn (kstn –
khơng dùng)
truy vấn echo (ping)
quảng bá tuyến đường
tìm tuyến đường
TTL hết hạn
mào đầu IP bị lỗi


MẠNG MÁY TÍNH CĂN BẢN
Bài giảng 3 - Chương 4: Tầng Mạng
4


Traceroute và ICMP


Nguồn gửi một loạt khúc UDP
cho đích






khúc đầu tiên có TTL =1
khúc thứ 2 có TTL=2, v.v.
số cổng khơng cố định

Khi gói tin thứ n đến bđt n:





BĐT loại bỏ gói tin
Và gửi lại nguồn một thơng điệp
ICMP (loại 11, mã 0)

Thông điệp bao gồm cả tên và
địa chỉ IP của bđt

Trường Đại Học Bách Khoa Tp.HCM
Khoa Khoa Học và Kỹ Thuật Máy Tính
© 2011

Khi thơng điệp ICMP tới, nguồn
sẽ tính RTT

Traceroute thực hiện việc này 3
lần
Điều kiện để ngừng lại

Khúc UDP đến được máy đích

Máy trả về gói ICMP “máy đích
khơng tới được” (loại 3, mã 3)

Khi nguồn nhận được những
ICMP này, nó sẽ dừng lại.


MẠNG MÁY TÍNH CĂN BẢN
Bài giảng 3 - Chương 4: Tầng Mạng
5


Chương 4: Tầng Mạng






4.1 Giới thiệu
4.2 Bên trong bộ định
tuyến là gì?
4.3 IP: Internet Protocol






Định dạng gói tin
Đánh địa chỉ IPv4
ICMP
IPv6



4.4 Các giải thuật định
tuyến






4.5 Định tuyến trong

Internet




Trường Đại Học Bách Khoa Tp.HCM
Khoa Khoa Học và Kỹ Thuật Máy Tính
© 2011

Trạng thái liên kết
Véc-tơ Khoảng cách
Định tuyến phân cấp

RIP
OSPF
BGP

MẠNG MÁY TÍNH CĂN BẢN
Bài giảng 3 - Chương 4: Tầng Mạng
6


IPv6




Động lực ban đầu: không gian địa chỉ 32-bit sẽ được cấp
phát hết trong t/g ngắn.
Động lực khác:

định dạng mào đầu sẽ giúp tăng tốc xử lý/chuyển tiếp gói tin
 thay đổi mào đầu để hỗ trợ QoS
Định dạng gói tin IPv6:
 mào đầu có độ dài cố định 40 byte
 không cho phép phân khúc


Trường Đại Học Bách Khoa Tp.HCM
Khoa Khoa Học và Kỹ Thuật Máy Tính
© 2011

MẠNG MÁY TÍNH CĂN BẢN
Bài giảng 3 - Chương 4: Tầng Mạng
7


Mào đầu IPv6 (tt)
Mức ưu tiên: xác định mức ưu tiên giữa các gói tin
Nhãn luồng: xác định các gói tin trong cùng “luồng”.

(khái niệm “luồng” chưa thực sự chuẩn).
Mào đầu tiếp theo: xác định dữ liệu của giao thức tầng trên

Trường Đại Học Bách Khoa Tp.HCM
Khoa Khoa Học và Kỹ Thuật Máy Tính
© 2011

MẠNG MÁY TÍNH CĂN BẢN
Bài giảng 3 - Chương 4: Tầng Mạng
8



Những thay đổi khác từ IPv4






Tổng kiểm tra: được loại bỏ hoàn toàn để giảm thời gian xử
lý tại mỗi thiết bị
Tùy chọn: cho phép, nhưng nằm ngoài phần mào đầu, chỉ
định bởi trường “Next Header”
ICMPv6: phiên bản mới của ICMP



những thơng điệp bổ sung, vd: “Gói tin q lớn”
những chức năng quản lý nhóm gửi-nhiều-đích (multicast)

Trường Đại Học Bách Khoa Tp.HCM
Khoa Khoa Học và Kỹ Thuật Máy Tính
© 2011

MẠNG MÁY TÍNH CĂN BẢN
Bài giảng 3 - Chương 4: Tầng Mạng
9


Chuyển tiếp Từ IPv4 Tới IPv6



Không thể nâng cấp tất cả bđt ngay một lúc được




Làm sao để mạng có thể làm việc với cả các bộ định tuyến IPv4
và IPv6?

Tạo đường hầm: IPv6 được mang như là dữ liệu của gói
tin IPv4 giữa các bđt IPv4

Trường Đại Học Bách Khoa Tp.HCM
Khoa Khoa Học và Kỹ Thuật Máy Tính
© 2011

MẠNG MÁY TÍNH CĂN BẢN
Bài giảng 3 - Chương 4: Tầng Mạng
10


Tạo đường hầm
Góc nhìn luận lí:

Góc nhìn vật lí:

E

F


IPv6

IPv6

IPv6

A

B

E

F

IPv6

IPv6

IPv6

IPv6

A

B

IPv6

Trường Đại Học Bách Khoa Tp.HCM

Khoa Khoa Học và Kỹ Thuật Máy Tính
© 2011

đường hầm

IPv4

IPv4

MẠNG MÁY TÍNH CĂN BẢN
Bài giảng 3 - Chương 4: Tầng Mạng
11


Tạo đường hầm
Góc nhìn luận lí:

Góc nhìn vật lí:

A

B

IPv6

IPv6

A

B


C

IPv6

IPv6

IPv4

Flow: X
Src: A
Dest: F
data

A-tới-B:
IPv6
Trường Đại Học Bách Khoa Tp.HCM
Khoa Khoa Học và Kỹ Thuật Máy Tính
© 2011

E

F

IPv6

IPv6

D


E

F

IPv4

IPv6

IPv6

đường hầm

Src:B
Dest: E

Src:B
Dest: E

Flow: X
Src: A
Dest: F

Flow: X
Src: A
Dest: F

data

data


B-tới-C:
IPv6 bên trong
IPv4

Flow: X
Src: A
Dest: F
data

E-tới-F:
B-tới-C:
IPv6
IPv6 bên trong
MẠNG MÁY TÍNH CĂN BẢN
IPv4 Bài giảng 3 - Chương 4: Tầng Mạng
12


Chương 4: Tầng Mạng





4.1 Giới thiệu
4.2 Bên trong bộ định
tuyến là gì?
4.3 IP: Internet Protocol







Định dạng gói tin
Đánh địa chỉ IPv4
ICMP
IPv6



4.4 Các giải thuật định
tuyến






4.5 Định tuyến trong
Internet




Trường Đại Học Bách Khoa Tp.HCM
Khoa Khoa Học và Kỹ Thuật Máy Tính
© 2011

Trạng thái liên kết

Véc-tơ Khoảng cách
Định tuyến phân cấp

RIP
OSPF
BGP

MẠNG MÁY TÍNH CĂN BẢN
Bài giảng 3 - Chương 4: Tầng Mạng
13


Tương tác giữa định tuyến, chuyển tiếp
giải thuật định tuyến

bảng chuyển tiếp cục bộ
gtrị mào đầu đầu ra
0100
0101
0111
1001

3
2
2
1

giá trị trong mào đầu
của gói tới
0111


1
3 2

Trường Đại Học Bách Khoa Tp.HCM
Khoa Khoa Học và Kỹ Thuật Máy Tính
© 2011

MẠNG MÁY TÍNH CĂN BẢN
Bài giảng 3 - Chương 4: Tầng Mạng
14


Trừu tượng hóa bằng đồ thị
5
2

u
Đồ thị: G = (N,E)

1

v

2
x

3
3


1

w

1
y

5

z

2

N = tập các bđt = { u, v, w, x, y, z }
E = tập các đg liên kết ={ (u,v), (u,x), (v,x), (v,w), (x,w), (x,y), (w,y), (w,z), (y,z)
Lưu ý: Trừu tượng hóa bằng đồ thị cũng hữu dụng trong những phạm trù
mạng khác
Ví dụ: P2P, với N là tập các thành viên và E là tập các kết nối TCP
Trường Đại Học Bách Khoa Tp.HCM
Khoa Khoa Học và Kỹ Thuật Máy Tính
© 2011

MẠNG MÁY TÍNH CĂN BẢN
Bài giảng 3 - Chương 4: Tầng Mạng
15


Trừu tượng hóa bằng đồ thị: chi phí
5
u


2

1

v

2
x

3

3
1

• c(x,x’) = chi phí của đường (x,x’)

w

1
y

5
2

- vd: c(w,z) = 5

z

• chi phí có thể ln bằng 1, hoặc

nghịch đảo với băng thơng,
hoặc nghịch đảo với tắc nghẽn

chi phí của đường đi c(x1, x2, x3,…, xp) = c(x1,x2) + c(x2,x3) + … + c(xp-1,xp)
Câu hỏi: Đường đi nào ít chi phí nhất giữa u và z ?

Giải thuật định tuyến: tìm ra đường đi ít tốn kém nhất
Trường Đại Học Bách Khoa Tp.HCM
Khoa Khoa Học và Kỹ Thuật Máy Tính
© 2011

MẠNG MÁY TÍNH CĂN BẢN
Bài giảng 3 - Chương 4: Tầng Mạng
16


Phân loại giải thuật định tuyến
Thông tin tổng quát hay phân
tán?
Tổng qt:

tất cả bđt đều có thơng tin đầy
đủ về đồ hình mạng và chi phí
liên kết

g/thuật “trang thái kết nối”
Phân tán:

bđt biết hàng xóm kết nối vật lý
tới nó, chi phí tới họ


q trình tính tốn, trao đổi
thơng tin với hàng xóm được lặp
đi lặp lại

g/thuật “véc tơ khoảng cách”
Trường Đại Học Bách Khoa Tp.HCM
Khoa Khoa Học và Kỹ Thuật Máy Tính
© 2011

Tĩnh hay động?
Tĩnh:
 tuyến đường chậm thay
đổi theo t/gian
Động:
 tuyến đường thay đổi
nhanh hơn



cập nhật theo chu kì
để phản ánh lại sự thay đổi
trong chi phí đường liên kết

MẠNG MÁY TÍNH CĂN BẢN
Bài giảng 3 - Chương 4: Tầng Mạng
17


Chương 4: Tầng Mạng






4.1 Giới thiệu
4.2 Bên trong bộ định
tuyến là gì?
4.3 IP: Internet Protocol






Định dạng gói tin
Đánh địa chỉ IPv4
ICMP
IPv6



4.4 Các giải thuật định
tuyến







4.5 Định tuyến trong
Internet




Trường Đại Học Bách Khoa Tp.HCM
Khoa Khoa Học và Kỹ Thuật Máy Tính
© 2011

Trạng thái liên kết
Véc-tơ Khoảng cách
Định tuyến phân cấp

RIP
OSPF
BGP

MẠNG MÁY TÍNH CĂN BẢN
Bài giảng 3 - Chương 4: Tầng Mạng
18


Một g/thuật trạng thái-liên kết
giải thuật Dijkstra







tất cả nốt đều biết đồ hình
mạng, chi phí liên kết
 thực hiện bởi “phát tán trạng
thái liên kết”
 mọi nốt có cùng th/tin
tính tuyến đường rẻ nhất từ 1
nốt tới tất cả nốt khác
 tạo bảng chuyển tiếp cho nốt
đó
lặp: sau k lần lặp, biết được
tuyến đường rẻ nhất tới k đích

Trường Đại Học Bách Khoa Tp.HCM
Khoa Khoa Học và Kỹ Thuật Máy Tính
© 2011

Kí hiệu:
 c(x,y): chi phí từ nốt x tới y;
= ∞ nếu khơng phải hàng xóm
trực tiếp


D(v): giá trị hiện tại của chi phí
của tuyến đường từ nguồn tới
đích v



p(v): nốt liền trước trên đường

đi từ nguồn tới v



N': tập các nốt mà đã biết
được đường đi xác định rẻ nhất
tới chúng

MẠNG MÁY TÍNH CĂN BẢN
Bài giảng 3 - Chương 4: Tầng Mạng
19


Giải thuật Dijsktra
1 Khởi tạo:
2 N' = {u}
3 với mọi nốt v
4
nếu v kề với u
5
thì D(v) = c(u,v)
6
ngồi ra D(v) = ∞
7
8 Lặp
9 tìm w khơng thuộc N' sao cho D(w) là min
10 thêm w vào N'
11 cập nhật D(v) cho tất cả v kề với w và ko thuộc N' :
12
D(v) = min( D(v), D(w) + c(w,v) )

13 /* chi phí mới tới v hoặc là chi phí cũ tới v hoặc là chi phí
14 tuyến ngắn nhất tới w cộng với chi phí từ w tới v */
15 tới khi tất cả các nốt đều thuộc N'
Trường Đại Học Bách Khoa Tp.HCM
Khoa Khoa Học và Kỹ Thuật Máy Tính
© 2011

MẠNG MÁY TÍNH CĂN BẢN
Bài giảng 3 - Chương 4: Tầng Mạng
20


Giải thuật Dijkstra: Ví dụ
Bước
0
1
2
3
4
5

N'
u
ux
uxy
uxyv
uxyvw
uxyvwz

D(v),p(v) D(w),p(w)

2,u
5,u
2,u
4,x
2,u
3,y
3,y

D(x),p(x)
1,u

D(y),p(y)
∞
2,x

D(z),p(z)

∞
∞

4,y
4,y
4,y

5
u

2
1


Trường Đại Học Bách Khoa Tp.HCM
Khoa Khoa Học và Kỹ Thuật Máy Tính
© 2011

v

2
x

3

w

3 1
1

y

5

z

2
MẠNG MÁY TÍNH CĂN BẢN
Bài giảng 3 - Chương 4: Tầng Mạng
21


Giải thuật Dijkstra: ví dụ (2)
Kết quả cây đường đi ngắn nhất từ u:


v

w

u
Kết quả bảng chuyển tiếp tại u:
đích

z
x

y

liên kết

v
x

(u,v)
(u,x)

y

(u,x)

w

(u,x)


z

(u,x)

Trường Đại Học Bách Khoa Tp.HCM
Khoa Khoa Học và Kỹ Thuật Máy Tính
© 2011

MẠNG MÁY TÍNH CĂN BẢN
Bài giảng 3 - Chương 4: Tầng Mạng
22


Giải thuật Dijkstra, thảo luận
Độ phức tạp giải thuật: n nốt
 mỗi lần lặp: phải kiểm tra tất cả n nốt, w, ko thuộc N
 thực hiện n(n+1)/2 lần so sánh: O(n2)
 có khả năng hiện thực tốt hơn: O(nlogn)
Dạng khác:
 vd, chi phí liên kết = lượng lưu lượng sử dụng
1
D

1

0

A

0 0

C

1+e
B

e

2+e
D

0
1

e
khởi đầu
Trường Đại Học Bách Khoa Tp.HCM
Khoa Khoa Học và Kỹ Thuật Máy Tính
© 2011

A

1+e 1
C

0

B

0


… tính lại
định tuyến

0

D

A

2+e

B
0 0
1 C 1+e

… tính lại

2+e
D

0

A

1+e 1
C

0

B


e

… tính lại
MẠNG MÁY TÍNH CĂN BẢN
Bài giảng 3 - Chương 4: Tầng Mạng
23


Chương 4: Tầng Mạng





4.1 Giới thiệu
4.2 Bên trong bộ định
tuyến là gì?
4.3 IP: Internet Protocol






Định dạng gói tin
Đánh địa chỉ IPv4
ICMP
IPv6




4.4 Các giải thuật định
tuyến






4.5 Định tuyến trong
Internet




Trường Đại Học Bách Khoa Tp.HCM
Khoa Khoa Học và Kỹ Thuật Máy Tính
© 2011

Trạng thái liên kết
Véc-tơ Khoảng cách
Định tuyến phân cấp

RIP
OSPF
BGP

MẠNG MÁY TÍNH CĂN BẢN
Bài giảng 3 - Chương 4: Tầng Mạng

24


Giải thuật Véc tơ-Khoảng cách
Phương trình Bellman-Ford (lập trình động)
Xác định
dx(y) := chí phí của tuyến đường rẻ nhất từ x tới y
Khi đó
dx(y) = min {c(x,v) + dv(y) }
v
với min được lấy trên tất cả hàng xóm v của x

Trường Đại Học Bách Khoa Tp.HCM
Khoa Khoa Học và Kỹ Thuật Máy Tính
© 2011

MẠNG MÁY TÍNH CĂN BẢN
Bài giảng 3 - Chương 4: Tầng Mạng
25