Bài giảng Mạng máy tính - Chương 4: Tầng mạng (Phần 1)

Chương 4:ꢀTꢁng Mꢂng

Hꢄc cái gì:

Mꢃc tiêu

ꢀ Các dꢄch vꢅ cꢆa tꢇng Mꢈng

ꢀ Nguyên tꢂc triꢃn khai dꢄch vꢅ

cꢆa tꢇng Mꢈng:

ꢁ ðꢄnh tuyꢉn (Lꢊa chꢋn

ñưꢌng ñi)

ꢁ Mꢍ rꢎng Phꢈm vi

ꢁ Cách thꢏc routerꢀhoꢈt ñꢎng

ꢁ Nâng cao:ꢀIPv6,ꢀmulticast

ꢀ Nguyên tꢂc ñꢄnh tuyꢉn:ꢀlꢊa chꢋn

ñưꢌng ñi

ꢀ ðꢄnh tuyꢉn phân cꢒp

ꢀ Giao thꢏc IP

ꢀ Giao thꢏc ñꢄnh tuyꢉn trên Internet

ꢁ Nꢎi miꢓn

ꢁ Liên miꢓn

ꢀ Cài ñꢐt nhꢑng dꢄch vꢅ này

ꢀ Kiꢉn trúc Router

ꢀ IPv6

trên Internetꢀnhư thꢉ nào

ꢀ NAT,ꢀPAT

ꢀ multicastꢀrouting

4:ꢀNetworkꢀLayer 4aꢁ1

Chꢅc năng cꢆa tꢁng Mꢂng

ꢀ Chuyꢃn gói tinꢀtꢔ máy tính gꢕi

application

transport

network

dataꢀlink

physical

ñꢉn máy tính nhꢖn

ꢀ Giao thꢏc tꢇng Mꢈng có mꢐt trên

tꢀt cꢁ máy tính,ꢀrouter

network

dataꢀlink

physical

network

dataꢀlink

physical

network

dataꢀlink

physical

network

dataꢀlink

physical

Ba chꢅc năng cơ bꢇn:

network

ꢀ Lꢂa chꢃn tuyꢄn ñưꢅng: Tuyꢉn

ñưꢌng gói tinꢀñi tꢔ nguꢗn ñꢉn

ñích.ꢀThuꢀt toán ñꢁnh tuyꢂn

ꢀ Chuyꢆn mꢇch: Routerꢀchuyꢃn gói

tinꢀtꢔ mꢎt ñꢇu vào này ra ñꢇu ra

thích hꢘp

ꢀ Thiꢄt lꢈp tuyꢄn ñưꢅng: mꢎt sꢙ

kiꢉn trúc mꢈng ñòi hꢚi tuyꢉn

ñưꢌng gói tinꢀñi quaꢀphꢛi ñưꢘc

thiꢉt lꢖp trưꢜc

dataꢀlink

physical

network

dataꢀlink

physical

network

dataꢀlink

physical

network

dataꢀlink

physical

application

transport

network

dataꢀlink

physical

4:ꢀNetworkꢀLayer 4aꢁ2

Mô hình Dꢈch vꢃ tꢁng Mꢂng

?: Chꢋn Mô hình dꢁch vꢃ nào

cꢆa “kênh truyꢓn” ñꢃ

chuyꢃn gói dꢑ liꢝu tꢔ nơi

gꢕi ñꢉn nơi nhꢖn ?

Vꢀn ñꢁ quan trꢂng nhꢀt

mà tꢃng Mꢄng phꢅi trꢅ lꢆi

:

ꢀ ðꢛm bꢛo băng thông không?

ꢀ ðꢛm bꢛo tꢙc ñꢎ nhꢖn ñꢓu không

Mꢀch ꢁo

(không có hiꢝn tưꢘng jitter)?

hayꢂ

Mꢀch gói?

?

ꢀ Không mꢒt mát ?

ꢀ ðꢛm bꢛo thꢏ tꢊ?

?

ꢀ Có thông báo vꢓ tình trꢈng tꢂc

nghꢞn cho bên gꢕi không ?

4:ꢀNetworkꢀLayer 4aꢁ3

Chuyꢉn mꢂch ꢇo

Tuyꢉn ñưꢌng tꢔ ñích ñꢉn nguꢗn giꢙng như mꢈch trong mꢈng

ñiꢝn thoꢈi

ꢁ Quan trꢋng :ꢀHiꢝu suꢒt

ꢁ Thiꢉt lꢖp kꢉt nꢙi dꢋc theo tuyꢉn ñưꢌng

ꢀ Thiꢉt lꢖp và ðóng kꢉt nꢙi trưꢄc khi truyꢓn dꢑ liꢝu

ꢀ Mꢟi packetꢀmang ñꢄnh danh mꢈch ꢛo là VCꢀidentifierꢀ(Không phꢛi

ñꢄa chꢠ máy ñích)

ꢀ Tꢅt cꢆ routerꢀtrên tuyꢉn ñưꢌng duy trì trꢈng thái cꢆa kꢉt nꢙi ñi qua

ꢁ Kênh truyꢓn ꢍ tꢇng giao vꢖn chꢠ liên quan ñꢉn hai thꢊc thꢃ ñꢇu cuꢙi

ꢀ Tài nguyên cꢆa ñưꢌng truyꢓn (Băng thông,ꢀBꢎ ñꢝm)ꢀphꢛi ñưꢘc cꢒp

phát cho mꢟi mꢈch ꢛo

ꢁ ðꢃ ñꢈt ñưꢘc hiꢝu suꢒt như mꢈng ñiꢝn thoꢈi.

4:ꢀNetworkꢀLayer 4aꢁ4

Mꢂch ꢇo:ꢀGiao thꢅc báo hiꢊu (Signal)

ꢀ ðꢃ Thiꢉt lꢖp và ðóng mꢈch ꢛo (VC)

ꢀ Có trong ATM,ꢀFrameꢁrelay,ꢀX.25

ꢀ Không ñưꢘc sꢕ dꢅng trên Internetꢀngày nay

application

6.ꢂNhꢈn dꢋ liꢌu application

5.ꢂChuyꢊn dꢋ liꢌu

4.ꢂThiꢆt lꢈp kꢆt nꢉi

1.ꢂKhꢃi tꢀo

transport

network

dataꢀlink

physical

transport

network

dataꢀlink

physical

3.ꢂChꢇp nhꢈn

2.ꢂCuꢄc gꢅi ñꢆn

4:ꢀNetworkꢀLayer 4aꢁ5

Mꢂng chuyꢉn mꢂch gói:ꢀMô hình Internet

ꢀ Không cꢇn thiꢉt lꢖp ñưꢌng truyꢓn ꢍ tꢇng Mꢈng

ꢀ routers:ꢀKhông duy trì trꢈng thái các kꢉt nꢙi ñi qua

ꢁ noꢀnetworkꢁlevelꢀconceptꢀofꢀ“connection”

ꢀ Gói tinꢀñưꢘc ñꢄnh tuyꢉn dꢊa trên ñꢄa chꢠ gói nhꢖn

ꢁ Các gói tinꢀcó thꢃ ñi theo nhꢑng tuyꢉn ñưꢌng khác nhau

application

transport

network

dataꢀlink

physical

transport

network

dataꢀlink

physical

1.ꢂGꢍi dꢋ liꢌu

2.ꢂNhꢈn dꢋ liꢌu

4:ꢀNetworkꢀLayer 4aꢁ6

Mô hình Dꢈch vꢃ ꢋ tꢁng Mꢂng

Có ñꢅm bꢅo ?

Kiꢇn trúc Mô hình

Phꢅn hꢍi

Băng thông Mꢀt

Mꢄng Dꢈch vꢉ

Internet bestꢊeffort

ATM CBR

Thꢋ tꢌ Thꢆi gian

Tꢎc nghꢏn

none

no

noꢊ(inferred

viaꢊloss)

no

congestion

no

constant yes

rate

guaranteed yes

rate

guaranteedꢊ no

minimum

yes

no

ATM VBR

congestion

yes

ATM ABR

none

no

ATM UBR

no

ꢀ Mô hình dꢄch vꢅ trên Internetꢀ:ꢀIntserv,ꢀDiffserv

ꢁ Chương 6

4:ꢀNetworkꢀLayer 4aꢁ7

Chuyꢉn Mꢂch hayꢀChuyꢉn Gói?

ATM

Internet

ꢀ Phát triꢃn tꢔ Mꢈng ñiꢝn thoꢈi

ꢀ Dꢑ liꢝu trao ñꢡi giꢑa máy tính

ꢀ Hꢎi thoꢈi cꢆa conꢀngưꢌi:ꢀ

ꢁ Dꢄch vꢅ mang tính “coꢀgiãn”,ꢀ

không ñòi hꢚi chꢐt chꢞ thꢌi

gian.ꢀ

ꢁ Yêu cꢇu nghiêm ngꢐt vꢓ

Thꢌi gian và ðꢎ tinꢀcꢖy

ꢀ Thiꢉt bꢄ ñꢇu cuꢙi “thông minh”

ꢁ ðꢛm bꢛo chꢒt lưꢘng dꢄch

vꢅ

ꢁ Có thꢃ thích nghi,ꢀKiꢃm soát,ꢀ

Khꢂc phꢅc lꢟi

ꢁ “Lõi” mꢈng ñơn giꢛn,ꢀPhꢏc

tꢈp ñꢐt ꢍ “Rìa”

ꢀ Nhiꢓu kiꢃu môi trưꢌng truyꢓn dꢢn

ꢁ Các ñꢐc ñiꢃm khác nhau

ꢀ Thiꢉt bꢄ ñꢇu cuꢙi ñơn giꢛn

ꢁ Máy ñiꢝn thoꢈi

ꢁ Phꢏc tꢈp ñꢐt ꢍ bên trong

Mꢈng

ꢁ Không thꢃ có chung chꢒt

lưꢘng dꢄch vꢅ

4:ꢀNetworkꢀLayer 4aꢁ8

Sꢍ dꢎng Mꢀch ꢁo ñꢊ cài ñꢏt Dꢐch vꢎ

ꢃ tꢑng Mꢀng

ꢀ ðꢐ cung cꢀp thêm mꢑt sꢒ chꢋc năng,ꢀcó thꢐ lꢌa chꢂn

công nghꢓ mꢄch ꢅo – ví dꢉ VirtualꢀPrivateꢀNetworkꢀ

(VPN)

4:ꢀNetworkꢀLayer 4aꢁ9

Chuyꢊn mꢀch gói :ꢀCài ñꢏt các chꢒc

năng Mꢀng cơ bꢁn nhꢇt

ꢀ Thưꢆng chꢔ cung cꢀp dꢈch vꢉ cơ bꢅn nhꢀt:ꢀchuyꢐn gói tinꢀ

ñi tꢕ nơi Gꢖi ñꢇn nơi Nhꢗn.

ꢀ Tꢗp trung vào mô hình Internetꢀtheo kiꢐu “cꢒ gꢎng tꢒi ña”

này

4:ꢀNetworkꢀLayer 4aꢁ10

ðꢈnh tuyꢌn

ðꢄnh tuyꢉn

Mꢎc tiêu: xác ñꢐnh tuyꢆn ñưꢓng

“tꢉt” (dãy các router)ꢂtrên mꢀng

tꢔ nút gꢍi ñꢆn nút nhꢈn.

ðꢗ thꢄ ñꢃ xây dꢊng thuꢖt

toán ñꢄnh tuyꢉn:

5

ꢀ ðꢠnh là Router

3

B

C

ꢀ Cꢈnh là các ñưꢌng kꢉt nꢙi

5

2

trꢊc tiꢉp

ꢁ Giá cꢆa cꢈnh:ꢀðꢎ trꢣ,ꢀChiꢀ

A

2

F

1

3

1

2

D

E

phí,ꢀhayꢀMꢏc ñꢎ Tꢂc nghꢞn

1

4:ꢀNetworkꢀLayer 4aꢁ11

ðꢈnh tuyꢌn :ꢀCác Yêu cꢁu khác

ꢀ Mꢎt vài Yêu cꢇu khác

ꢁ Mꢈnh và Tinꢀcꢖy

ꢁ Tꢙi ưu và có Hiꢝu quꢛ

ꢁ Phân tán,ꢀTꢌ quꢅn,ꢀKhông

có ñiꢐm hꢘng duy nhꢀt

ꢁ ðơn giꢛn

ꢁ Công bꢙng

ðꢄnh tuyꢉn

Mꢎc tiêu: xác ñꢐnh tuyꢆn ñưꢓng

“tꢉt” (dãy các router)ꢂtrên mꢀng

tꢔ nút gꢍi ñꢆn nút nhꢈn.

4:ꢀNetworkꢀLayer 4aꢁ12

Minh hꢅa Chꢒc năng Tꢑng Mꢀng

routingꢊandꢊcallꢊ

setup

4:ꢀNetworkꢀLayer 4aꢁ13

Không gian ðꢈnh tuyꢌn

ꢀ ðꢄnh tuyꢉn

ꢁ Aiꢀquyꢉt ñꢄnh tuyꢉn ñưꢌng?

• Nút gꢕi quyꢉt ñꢄnh

• Mꢈng quyꢉt ñꢄnh

ꢁ Có bao nhiêu tuyꢉn ñưꢌng tꢔ nút Gꢕi sꢀñꢉn nút Nhꢖn d?

• ðꢄnh tuyꢉn nhiꢓu chꢐng

ꢁ Tuyꢉn ñưꢌng có thay ñꢡi theo tꢛi cꢆa mꢈng không?

• ðꢄnh tuyꢉn thích nghi

• ðꢄnh tuyꢉn tĩnh

ꢁ …

4:ꢀNetworkꢀLayer 4aꢁ14

Phân loꢂi Thuꢍt toán ðꢈnh tuyꢌn

Thông tinꢀToàn cꢉc hayꢀ

Phân tán ?

ðꢎng hayꢀTĩnh?

Tĩnh (Static):

Toàn cꢎc (Global):

ꢀ Routerꢀrꢒt ít thay ñꢡi

ꢀ Mꢋi routerꢀñꢓu biꢉt vꢓ toàn bꢎ

topo cꢆa ñꢗ thꢄ

ꢀ Thuꢖt toán “linkꢀstate”

Phân tán (Decentralized):

ꢀ Mꢟi routerꢀchꢠ biꢉt vꢓ routerꢀvà

giá ñꢉn các routerꢀhàng xóm

ꢀ Thꢊc hiꢝn quá trình trao ñꢡi

ðꢄng (Dynamic):

ꢀ Routerꢀthay ñꢡi thưꢌng xuyên

ꢁ Cꢖp nhꢖt ñꢄnh kỳ

ꢁ Chꢈy lꢈi thuꢖt toán khi có 1ꢀ

giá ñưꢌng ñi thay ñꢡi

thông tinꢀvꢜi các “hàng xóm”

ꢀ Thuꢖt toán “distanceꢀvector”

4:ꢀNetworkꢀLayer 4aꢁ15

Thuꢍt toán ðꢈnh tuyꢌn LinkꢏState

Thuꢍt toán Dijkstra

Ký hiꢊu:

ꢀ Tꢒt cꢛ các nút ñꢓu biꢉt ñưꢘc vꢓ

ꢀ c(i,j): Giá ñưꢌng ñi tꢔ iꢀtꢜi j.ꢀ

Có giá trꢄ vô cùng nꢉu iꢀvà jꢀ

không có ñưꢌng trꢊc tiꢉp

topo cꢆa toàn mꢈng

ꢁ Biꢉt ñưꢘc doꢀcác thông ñiꢝp

quꢛng cáo ñưꢘc gꢕi quꢛng

bá

ꢀ D(v): Giá hiꢝn tꢈi cꢆa ñưꢌng

ñi tꢜi ñích V

ꢁ Tꢒt cꢛ các nút có thông tinꢀ

ꢀ p(v): Nút kꢓ trưꢜc Vꢀtrong

giꢙng nhau

ꢀ Tính toán ñưꢌng ñi tꢙt nhꢒt ñꢉn

tuyꢉn ñưꢌng ñꢉn V

ꢀ N: Tꢖp hꢘp các ñꢠnh ñã xác

tꢒt cꢛ các nút khác

ꢁ Tꢈo ra Bꢇng ðꢈnh tuyꢌn

ñꢄnh ñưꢘc ñưꢌng ñi ngꢂn nhꢒt

ꢀ Sau kꢀbưꢜc tính toán,ꢀxác ñꢄnh

ñưꢘc ñưꢌng ngꢂn nhꢒt tói kꢀ

ñích

4:ꢀNetworkꢀLayer 4aꢁ16

Thuꢍt toán Dijsktra

1ꢊꢊKhꢀi tꢁo:

2ꢊꢊꢊꢊNꢊ=ꢊ{A}ꢊ

3ꢊꢊꢊꢊVꢚi tꢀt cꢅ các nút vꢊ

4ꢊꢊꢊꢊꢊꢊNꢇu vꢊkꢁ vꢚi Aꢊ

5ꢊꢊꢊꢊꢊꢊꢊꢊthì D(v)ꢊ=ꢊc(A,v)ꢊ

6ꢊꢊꢊꢊꢊꢊꢊꢊnꢇu không D(v)ꢊ=ꢊinfty

7ꢊ

8ꢊꢊꢊLꢂp

9ꢊꢊꢊꢊꢊꢊTìm wꢊkhông trong Nꢊsao cho D(w)ꢊnhꢘ nhꢀt

10ꢊꢊꢊꢊBꢛ sungꢊwꢊvào Nꢊ

11ꢊꢊꢊꢊCꢗp nhꢗt D(v)ꢊcho tꢀt cꢅ vꢊkꢁ vꢚi wꢊvà không trong N:ꢊ

12ꢊꢊꢊꢊꢊꢊꢊD(v)ꢊ=ꢊmin(ꢊD(v),ꢊD(w)ꢊ+ꢊc(w,v)ꢊ)ꢊ

13ꢊꢊꢊꢊ/*ꢊGiá mꢚi tꢚi vꢊhoꢜc là giá cũ ñꢇn vꢊhoꢜc ñưꢆng ñi ngꢎn nhꢀt

14ꢊꢊꢊꢊñꢇn wꢊcꢑng thêm khoꢅng cách tꢕ wꢊtꢚi vꢊ*/ꢊ

15ꢊꢊCho ñꢃn khi tꢄt cꢅ các nút ñꢆu nꢇm trong N

4:ꢀNetworkꢀLayer 4aꢁ17

Ví dꢃ vꢐ Thuꢍt toán Dijsktra

D(B),p(B)

2,A

D(D),p(D)

1,A

D(C),p(C)

5,A

D(E),p(E)

vô cùng

2,D

Bưꢚc

Tꢗp N

A

D(F),p(F)

vô cùng

4,E

0

1

2

3

4

5

2,A

4,D

3,E

AD

ADE

ADEB

ADEBC

ADEBCF

4,E

5

3

B

C

5

F

2

A

2

1

3

1

D

E

1

4:ꢀNetworkꢀLayer 4aꢁ18

Thꢇo luꢍn vꢐ Thuꢍt toán Dijsktra

ðꢎ phꢅc tꢂp Thuꢍt toán:ꢀnꢀnút

ꢀ Mꢟi vòng lꢐp:ꢀCꢇn kiꢃm tra tꢒt cꢛ các nút wꢀkhông ꢍ trong N

ꢀ n*(n+1)/2ꢀ:ꢀO(n**2)

ꢀ Bꢤng thuꢖt toán “mꢄn” hơn:ꢀO(nlogn)

Tình huꢑng Daoꢀñꢎng:

ꢀ Ví dꢅ khi Chiꢀphí kênh truyꢓn =ꢀkhꢙi lưꢘng dꢑ liꢝu truyꢓn qua

A

C

A

1

1+e

2+e

D

0

2+e

D

0

2+e

0

D

B

D

B

0

B

0

1

1+e

0

C

1

1+e

e

0

e

1

1+e

0

C

1

e

… Tính lꢄi

… Tính lꢄi ðꢈnh tuyꢇn

… Tính lꢄi

Banꢊñꢃu

4:ꢀNetworkꢀLayer 4aꢁ19

Thuꢍt toán ðꢈnh tuyꢌn DistanceꢀVector

Lꢒp:

Cꢔu trúc Dꢕ liꢊu Bꢇng Distance

ꢀ Mꢟi nút có mꢎt Bꢛng riêng

ꢀ Liên tꢅc diꢣn ra cho ñꢉn

khi không còn thông ñiꢝp

ꢀ Mꢟi hàng ꢏng vꢜi mꢎt ñích cꢅ thꢃ

trao ñꢡi.

ꢀ Mꢟi cꢎt ꢏng vꢜi mꢎt hàng xóm có

ꢀ Tꢇ kꢂt thúc:ꢀKhông có “tín

ñưꢌng kꢉt nꢙi trꢊc tiêp

hiꢝu” ñꢃ dꢔng lꢈi

ꢀ Ví dꢅ:ꢀtrong nút X,ꢀvꢜi ñích Yꢀquaꢀ

Không ñꢓng bꢎ:

hàng xóm Z:

ꢀ Các nút sau khi gꢕi/ꢀnhꢖn

thông ñiꢝp không bꢄ phong

tꢚa!

Khoꢅng cách tꢀ Xꢊtꢁi

Y,ꢊqua Zꢊlà chꢜng tiꢇp

=

X

Phân tán:

ꢀ Mꢟi nút chꢠ truyꢓn thông

Dꢊ(Y,Z)

Z

c(X,Z)ꢊ+ꢊminꢊꢊ{Dꢊꢊ(Y,w)}

w

vꢜi hàng xóm

4:ꢀNetworkꢀLayer 4aꢁ20

Bài giảng Mạng máy tính - Chương 4: Tầng mạng (Phần 1) - Hồ Phương Đắc