Giao thức tầng mạng chapter04
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (887.89 KB, 24 trang )
Chương 4. Giao thức tầng mạng
1-6/2006
Chương 4.
Giao thức tầng mạng (network layer)
Đặng Xuân Hà
Computer Networking 2006
Dept. of CS, HAU1.
Ch4. The Network Layer
4.1 - Giới thiệu và chức năng của tầng mạng.
4.2 - Network service model (VC and Datagram).
4.3 - Thiết bị tầng mạng - Bộ định tuyến (router).
4.4 - Giao thức IP (Internet Protocol).
4.5 - Giải thuật chọn đường (Routing Algorithms).
4.6 - Chọn đường trong mạng Internet.
1-6/2006
2
Chương 4. Giao thức tầng mạng
Chức năng của tầng mạng
Truyền các gói tin (packets) từ sending
application
host tới receiving host.
transport
segment Æ packets (datagrams).
network
data link
physical
Network layer được cài đặt tại router
và cả end system.
Chức năng:
1-6/2006
chọn đường (path selection): có nhiều
đường đi, gói tin sẽ đi theo đường nào?
chuyển mạch (switching, forwarding):
chuyển gói tin từ cổng vào tới cổng ra của
router một cách thích hợp.
thiết lập liên kết (call setup): một số kiến
trúc mạng cần thiết lập kênh truyền trước
khi truyền.
Chương 4. Giao thức tầng mạng
<dxha at hau1.edu.vn>
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
application
transport
network
data link
physical
3
1
Chương 4. Giao thức tầng mạng
1-6/2006
Routing & switching in routers
routing algorithm
local forwarding table
header value output link
0100
0101
0111
1001
3
2
2
1
value in arriving
packet’s header
1
0111
3 2
1-6/2006
Chương 4. Giao thức tầng mạng
4
Ch4. The Network Layer
4.1 - Giới thiệu và chức năng của tầng mạng.
4.2 - Network service model (VC and Datagram).
4.3 - Thiết bị tầng mạng - Bộ định tuyến (router).
4.4 - Giao thức IP (Internet Protocol).
4.5 - Giải thuật chọn đường (Routing Algorithms).
4.6 - Chọn đường trong mạng Internet.
1-6/2006
Chương 4. Giao thức tầng mạng
5
Network service model
Tầng mạng cung cấp dịch vụ cho tầng Transport:
tin
cậy vào tầng network?
gói tin có đến đích đúng thứ tự đã gửi?
thời gian truyền có được đảm bảo?
có phản hồi về tình trạng nghẽn mạng?
các
Hai model cơ bản của tầng mạng:
kênh
lược
1-6/2006
ảo (virtual circuit)
đồ (gam) dữ liệu (datagram)
Chương 4. Giao thức tầng mạng
<dxha at hau1.edu.vn>
6
2
Chương 4. Giao thức tầng mạng
1-6/2006
Virtual Circuit
Thiết lập liên kết trước khi truyền dữ liệu và huỷ bỏ liên
kết sau khi truyền xong.
VC
setup: trước khi truyền, tầng mạng phải thiết lập một kênh
truyền ảo (VC) từ sender tới receiver (đã biết địa chỉ).
Data transfer: dữ liệu được truyền qua VC.
VC teardown: một khi sender hoặc receiver muốn ngắt VC, nó
thông báo cho network layer biết, network layer sẽ huỷ bỏ VC.
Æ Còn được gọi là connection-oriented
Mỗi gói tin chứa thêm thông tin về kênh mà nó sẽ đi qua
(VC identifier number).
Các routers/packet switches trên kênh ảo (VC) luôn nắm
giữ trạng thái của kênh đi qua nó.
1-6/2006
7
Chương 4. Giao thức tầng mạng
Virtual Circuit: Signaling protocol
Giao thức truyền các thông điệp giữa end system và
network layer để yêu cầu thiết lập, huỷ bỏ VC; giữa các
thiết bị chuyển mạch (switches) để thiết lập VC.
Được sử dụng trong mạng ATM, Frame Relay, X.25.
application
transport 5. Data flow begins
network 4. Call connected
data link 1. Initiate call
physical
1-6/2006
application
transport
network
data link
physical
host A
6. Receive data application
3. Accept call transport
2. incoming call network
data link
physical
8
Chương 4. Giao thức tầng mạng
application
transport
network
data link
physical
server B
Sự khác biệt giữa liên kết tại tầng Transport và Network?
application
transport
network
data link
physical
1-6/2006
application
transport
network
data link
physical
Chương 4. Giao thức tầng mạng
<dxha at hau1.edu.vn>
9
3
Chương 4. Giao thức tầng mạng
1-6/2006
Datagram network
Không thiết lập kênh truyền.
Các thiết bị chuyển mạch không cần nắm giữ trạng thái các
kênh.
Gói tin được truyền dựa trên địa chỉ của receiving host.
Đường đi của các gói tin giữa hai host có thể khác nhau.
application
transport
network
data link 1. Send data
physical
application
transport
2. Receive data network
data link
physical
10
Chương 4. Giao thức tầng mạng
1-6/2006
Network taxonomy (review)
communication
networks
switched
networks
circuit-switched
networks
(vd. telephone)
FDM
1-6/2006
TDM
broadcast
networks
(vd. Radio,
Broadcast TV)
packet-switched
networks
virtual circuitswitched
networks
(vd. ATM)
datagram
networks
(vd. Internet)
Chương 4. Giao thức tầng mạng
11
Datagram or VC network: why?
Internet
ATM
Mạng máy tính:
dịch vụ nhạy cảm.
không giới hạn thời gian.
Các hệ thống cuối “thông minh”
(computer):
có khả năng thích nghi, kiểm
soát, khôi phục lỗi.
kiến trúc bên trong mạng đơn
giản nhưng kết nối các mạng
phức tạp.
Nhiều dạng liên kết mạng dẫn đến
một dịch vụ thuần nhất (kênh) là
không thích hợp.
1-6/2006
Mạng điện thoại (chuyển mạch kênh).
Tương tác người-người đòi hỏi:
thời gian truyền.
độ tin cậy.
dịch vụ phải được đảm bảo.
Các thiết bị cuối đơn giản, dường như
cố định:
điện thoại.
mức độ phức tạp nằm bên trong
mạng.
Chương 4. Giao thức tầng mạng
<dxha at hau1.edu.vn>
12
4
Chương 4. Giao thức tầng mạng
1-6/2006
Ch4. The Network Layer
4.1 - Giới thiệu và chức năng của tầng mạng.
4.2 - Network service model (VC and Datagram).
4.3 - Thiết bị tầng mạng - Bộ định tuyến (router).
4.4 - Giao thức IP (Internet Protocol).
4.5 - Giải thuật chọn đường (Routing Algorithms).
4.6 - Chọn đường trong mạng Internet.
Chương 4. Giao thức tầng mạng
1-6/2006
13
Bộ định tuyến – router
Thực thi các giải thuật chọn đường (routing algorithms).
Chuyển tiếp (forwarding) các gói tin từ cổng vào tới cổng
ra thích hợp.
Chương 4. Giao thức tầng mạng
1-6/2006
14
Input ports
Physical layer:
bit-level reception
Data link layer:
e.g., Ethernet
Decentralized switching:
1-6/2006
sử dụng forwarding table có trong input
port memory để tra cứu output port
queuing: nếu các gam dữ liệu
(datagram) đến nhanh quá, cần phải xếp
hàng chờ xử lý.
Chương 4. Giao thức tầng mạng
<dxha at hau1.edu.vn>
15
5
Chương 4. Giao thức tầng mạng
1-6/2006
Các cơ cấu chuyển mạch (switching fabrics)
1-6/2006
Chương 4. Giao thức tầng mạng
16
Output ports
Buffering: khi datagram được gửi ra nhanh hơn tốc độ xử
lý, cần đưa vào bộ đệm.
Scheduling discipline: cơ chế lựa chọn datagram từ bộ đệm
để tiếp tục gửi đi.
1-6/2006
Chương 4. Giao thức tầng mạng
17
Ch4. The Network Layer
4.1 - Giới thiệu và chức năng của tầng mạng.
4.2 - Network service model (VC and Datagram).
4.3 - Thiết bị tầng mạng - Bộ định tuyến (router).
4.4 - Giao thức IP (Internet Protocol).
4.5 - Giải thuật chọn đường (Routing Algorithms).
4.6 - Chọn đường trong mạng Internet.
1-6/2006
Chương 4. Giao thức tầng mạng
<dxha at hau1.edu.vn>
18
6
Chương 4. Giao thức tầng mạng
1-6/2006
The Internet (TCP/IP) network layer
Network layer được thực thi tại end system cũng như tại router!
Transport layer: TCP, UDP
Network
layer
IP protocol
•addressing conventions
•datagram format
•packet handling conventions
Routing protocols
•path selection
•RIP, OSPF, BGP
routing
table
ICMP protocol
•error reporting
•router “signaling”
Link layer
physical layer
19
Chương 4. Giao thức tầng mạng
1-6/2006
IP datagram format
IP protocol version
number
header length
(bytes)
“type” of data
max number
remaining hops
(decremented at
each router)
upper layer protocol
to deliver payload to
6 = TCP; 17 = UDP
32 bits
ver head. type of
len service
length
fragment
16-bit identifier flgs
offset
time to upper
Internet
layer
live
checksum
total datagram
length (bytes)
for
fragmentation/
reassembly
32 bit source IP address
32 bit destination IP address
Options (if any)
data
(variable length,
typically a TCP
or UDP segment)
Chương 4. Giao thức tầng mạng
1-6/2006
E.g. timestamp,
record route
taken, specify
list of routers
to visit.
20
IP Fragmentation & Reassembly
Fragmentation: gam dữ liệu
(datagram) lớn được chia
thành nhiều gam dữ liệu
nhỏ.
Do mỗi đường truyền giữa
các nút (link) có tốc độ giới
hạn, chỉ cho phép truyền đơn
vị dữ liệu có kích thước tối đa
là MTU (Max Transfer Unit)
fragmentation:
in: one large datagram
out: 3 smaller datagrams
reassembly
Reassembly: Các gam dữ
liệu nhỏ được hợp nhất
thành gam dữ liệu lớn
(ngược lại) tại điểm đến
cuối cùng
1-6/2006
Chương 4. Giao thức tầng mạng
<dxha at hau1.edu.vn>
21
7
Chương 4. Giao thức tầng mạng
1-6/2006
length ID fragflag offset
=4000 =x
=0
=0
Example
4000 byte datagram
MTU = 1500 bytes
gam dữ liệu lớn được chia thành
nhiều gam dữ liệu nhỏ hơn
length ID fragflag offset
=1500 =x
=1
=0
1480 bytes in
data field
length ID fragflag offset
=1500 =x
=1
=185
offset =
1480/8
length ID fragflag offset
=1040 =x
=0
=370
22
Chương 4. Giao thức tầng mạng
1-6/2006
IPv4 Addressing: introduction
IP address: Số 32-bit định danh giao diện mạng (interface).
Interface (NIC - Network Interface Card): giao diện kết nối mạng
từ nút mạng tới mạng.
host interface: mỗi máy tính thường có một NIC, cho phép nối vào một đường
liên kết.
router interface: router thường có nhiều giao diện mạng.
223.1.1.1
223.1.1.2
223.1.1.4
32-bit = 4 số 8-bit Æ dạng thập phân dễ nhớ:
223.1.1.3
223.1.1.1 = 11011111 00000001 00000001 00000001
223
1
1
223.1.2.1
223.1.2.9
223.1.2.2
223.1.3.27
223.1.3.2
223.1.3.1
1
23
Chương 4. Giao thức tầng mạng
1-6/2006
Mạng & mạng con (subnet)
Internet = network of networks.
Địa chỉ IP bao gồm 2 phần:
Các bit cao dành cho network.
Các bit thấp dành cho host.
223.1.1.1
223.1.1.2
223.1.1.4
223.1.1.3
223.1.3.27
223.1.2.2
LAN
Network:
Mạng
tạo bởi các interface có
phần network trong IP addr
giống nhau.
Các host cùng network có thể
trao đổi dữ liệu không cần
thông qua router.
1-6/2006
223.1.2.1
223.1.2.9
223.1.3.1
network = 3 IP networks
Chương 4. Giao thức tầng mạng
<dxha at hau1.edu.vn>
223.1.3.2
24
8
Chương 4. Giao thức tầng mạng
1-6/2006
IP addressing: Class-full
Chương 4. Giao thức tầng mạng
1-6/2006
25
Subnet
Đôi khi cần chia nhỏ một mạng thành các mạng
nhỏ hơn (subnet)
Ví dụ:
Chương 4. Giao thức tầng mạng
1-6/2006
26
Subnet mask
Một interface trong mạng cần có:
IP
address
nạ mạng con (subnet mask):
Mặt
Là một số 32 bit bao gồm các bit cao = 1 và các bit thấp = 0. Các bit 1
quy định subnet, các bit 0 quy định địa chỉ host.
từ subnet mask có thể xác định ranh giới giữa địa chỉ mạng và địa chỉ của
interface (host).
Ví dụ: Subnet gồm các host 192.168.10.x, một host có thể
có thông số như sau:
IP
= 192.168.10.1
= 255.255.255.0
(111111111.11111111.11111111.00000000)
SM
Kiểm tra xem hai IP có cùng một subnet không?
(IP1
1-6/2006
XOR IP2) AND SM = 0?
Chương 4. Giao thức tầng mạng
<dxha at hau1.edu.vn>
27
9
Chương 4. Giao thức tầng mạng
1-6/2006
Network addr, Broadcast và loopback
Để ám chỉ một mạng, thay địa chỉ host bằng các bit
0, ví dụ: 192.168.10.0
Broadcast:
Địa
chỉ host thay bằng các bit 1, vd: 192.168.10.255
gói tin có ip đích dạng broadcast sẽ được gửi cho
mọi host trong mạng.
Các
Loopback ip: 127.x.x.x
các
gói tin được coi như được gửi tới từ nút khác.
dùng 127.0.0.1
thường
28
Chương 4. Giao thức tầng mạng
1-6/2006
IP addressing: CIDR
Class-full addressing: sự phân lớp cứng nhắc,
không còn thích hợp nữa.
CIDR (Classless InterDomain Routing):
Vị
trí ngăn cách giữa net addr và host addr tuỳ ý.
format: a.b.c.d/x, với x là số lượng bit dành cho net
addr.
addr
network
part
host
part
11001000 00010111 00010000 00000000
200.23.16.0/23
Chương 4. Giao thức tầng mạng
1-6/2006
29
IP addresses: how to get one?
Làm thế nào để có địa chỉ IP cho host?
Người
quản trị hệ thống thiết lập (TCP/IP properties trong
Windows 2000/XP).
RARP (Reverse Address Resolution Protocol):
RARP server cung cấp IP cho client dựa trên bảng cấu hình sẵn có (từ địa
chỉ vật lý (MAC) Æ IP).
BOOTP
DHCP
1-6/2006
(BOOTstrap Protocol):
BOOTP server cung cấp IP cho client dựa trên bảng cấu hình sẵn có.
(Dynamic Host Configuration Protocol):
Giao thức cấp phát địa chỉ IP động.
DHCP server phụ trách việc cấp phát/thu hồi IP cho/từ các DHCP client.
Client có thể nhận IP khác nhau tuỳ thời điểm kết nối.
Chương 4. Giao thức tầng mạng
<dxha at hau1.edu.vn>
30
10
Chương 4. Giao thức tầng mạng
1-6/2006
Phân cấp địa chỉ Internet - ISP
ICANN: Internet
Corporation for
Assigned Names
and Numbers
ISP's block
11001000 00010111 00010000 00000000
200.23.16.0/20
Organization 0
Organization 1
Organization 2
...
Organization 7
11001000 00010111 00010000 00000000
11001000 00010111 00010010 00000000
11001000 00010111 00010100 00000000
…..
….
11001000 00010111 00011110 00000000
200.23.16.0/23
200.23.18.0/23
200.23.20.0/23
….
200.23.30.0/23
Organization 0
200.23.16.0/23
Organization 1
200.23.18.0/23
Organization 2
200.23.20.0/23
Organization 7
.
.
.
.
.
.
Fly-By-Night-ISP
“Send me anything
with addresses
beginning
200.23.16.0/20”
Internet
200.23.30.0/23
“Send me anything
with addresses
beginning
199.31.0.0/16”
ISPs-R-Us
31
Chương 4. Giao thức tầng mạng
1-6/2006
NAT: Network Address Translation
rest of
Internet
local network
(e.g., home network)
10.0.0/24
10.0.0.4
10.0.0.1
10.0.0.2
138.76.29.7
10.0.0.3
All datagrams leaving local
network have same single source
NAT IP address: 138.76.29.7,
different source port numbers
1-6/2006
Datagrams with source or
destination in this network
have 10.0.0/24 address for
source, destination (as usual)
Chương 4. Giao thức tầng mạng
32
NAT: Network Address Translation (cont)
Giả sử một LAN chỉ sử dụng một IP duy nhất khi
giao tiếp với mạng ngoài.
Lợi điểm:
Không
cần tìm dải IP từ ISP để cấp phát cho các thiết bị
mạng trong (máy trạm) vì chỉ dùng 1 IP.
Thay đổi IP của máy trạm nội bộ mà không ảnh hưởng
tới mạng ngoài.
Thay đổi ISP mà không cần thay đổi địa chỉ các thiết bị
mạng trong.
Các thiết bị mạng trong không “nhìn thấy” được từ
mạng ngoài.
1-6/2006
Chương 4. Giao thức tầng mạng
<dxha at hau1.edu.vn>
33
11
Chương 4. Giao thức tầng mạng
1-6/2006
NAT: Implementation
NAT router:
outgoing datagrams: replace (source IP address, port #) of every
outgoing datagram to (NAT IP address, new port #)
. . . remote clients/servers will respond using (NAT IP address, new
port #) as destination addr.
remember (in NAT translation table) every (source IP address, port
#) to (NAT IP address, new port #) translation pair
incoming datagrams: replace (NAT IP address, new port #) in dest
fields of every incoming datagram with corresponding (source IP
address, port #) stored in NAT table
34
Chương 4. Giao thức tầng mạng
1-6/2006
NAT example
2: NAT router
changes datagram
source addr from
10.0.0.1, 3345 to
138.76.29.7, 5001,
updates table
2
NAT translation table
WAN side addr
LAN side addr
1: host 10.0.0.1
sends datagram to
128.119.40, 80
138.76.29.7, 5001 10.0.0.1, 3345
……
……
S: 10.0.0.1, 3345
D: 128.119.40.186, 80
S: 138.76.29.7, 5001
D: 128.119.40.186, 80
138.76.29.7
S: 128.119.40.186, 80
D: 138.76.29.7, 5001
3
1
10.0.0.4
10.0.0.2
S: 128.119.40.186, 80
D: 10.0.0.1, 3345
4
10.0.0.3
4: NAT router
changes datagram
dest addr from
138.76.29.7, 5001 to 10.0.0.1, 3345
3: Reply arrives
dest. address:
138.76.29.7, 5001
35
Chương 4. Giao thức tầng mạng
1-6/2006
10.0.0.1
ICMP (Internet Control Message Protocol)
Giao tiếp ở mức mạng giữa các
hosts, routers
ICMP có thể coi là một thành
phần của IP
thông báo lỗi (vd: không tìm được
đường đi, không gửi tin được tới
host, port…).
echo request/reply.
về mặt kiến trúc, ICMP thuộc về
tầng ứng dụng.
sử dụng UDP.
ICMP msg
1-6/2006
được đóng gói trong IP
datagrams/packet.
type + code + 8 bytes of IP
datagram.
Type
0
3
3
3
3
3
3
4
Code
0
0
1
2
3
6
7
0
8
9
10
11
12
0
0
0
0
0
Chương 4. Giao thức tầng mạng
<dxha at hau1.edu.vn>
description
echo reply (ping)
dest. network unreachable
dest host unreachable
dest protocol unreachable
dest port unreachable
dest network unknown
dest host unknown
source quench (congestion
control - not used)
echo request (ping)
route advertisement
router discovery
TTL expired
bad IP header
36
12
Chương 4. Giao thức tầng mạng
1-6/2006
IPv6
IPv4: sử dụng 32-bit địa chỉ IP sẽ là không đủ???
IPv6:
sử
dụng 128-bit địa chỉ.
tiêu đề (header) cung cấp khả năng xử lý nhanh
hơn, chất lượng hơn (QoS).
40 bytes header.
không cho phép phân mảnh (fragmentation).
ICMP v6.
phần
1-6/2006
Chương 4. Giao thức tầng mạng
37
IPv6: datagram format
ver: phiên bản (6=v6, 4#v4!!).
priority: thứ tự các gói tin
trong cùng flow.
flow: nhãn của luồng mà gói
tin thuộc về
các
ứng dụng đòi hỏi chất lượng
cao Æ flow.
ứng dụng không đòi hỏi chất
lượng Æ không được coi là flow.
next header: giao thức tầng
trên.
1-6/2006
Chương 4. Giao thức tầng mạng
38
IPv6: chuyển đổi IPv4 Æ IPv6
Chuyển đổi tất cả các hosts, routers sang sử dụng
IPv6: không thể!!!
Chuyển đổi dần dần:
tồn
tại các nút mạng IPv4 và IPv6.
có khả năng xử lý gói tin IPv4.
Tunneling: gói tin IPv6 được coi như phần data
(payload) của IPv4 khi đi qua các nút mạng IPv4.
IPv6
1-6/2006
Chương 4. Giao thức tầng mạng
<dxha at hau1.edu.vn>
39
13
Chương 4. Giao thức tầng mạng
1-6/2006
Tunneling
Logical view:
Physical view:
A
B
IPv6
IPv6
A
B
IPv6
IPv6
Flow: X
Src: A
Dest: F
F
C
D
IPv6
IPv6
E
F
IPv4
IPv4
IPv6
Src:B
Dest: E
Src:B
Dest: E
Flow: X
Src: A
Dest: F
Flow: X
Src: A
Dest: F
data
data
data
A-to-B:
IPv6
E
tunnel
B-to-C:
IPv6 inside
IPv4
B-to-C:
IPv6 inside
IPv4
IPv6
Flow: X
Src: A
Dest: F
data
E-to-F:
IPv6
Chương 4. Giao thức tầng mạng
1-6/2006
40
Ch4. The Network Layer
4.1 - Giới thiệu và chức năng của tầng mạng.
4.2 - Network service model (VC and Datagram).
4.3 - Thiết bị tầng mạng - Bộ định tuyến (router).
4.4 - Giao thức IP (Internet Protocol).
4.5 - Giải thuật chọn đường (Routing Algorithms).
4.6 - Chọn đường trong mạng Internet.
Chương 4. Giao thức tầng mạng
1-6/2006
41
Forwarding & routing
routing algorithm
local forwarding table
header value output link
0100
0101
0111
1001
3
2
2
1
value in arriving
packet’s header
1
0111
3 2
1-6/2006
Chương 4. Giao thức tầng mạng
<dxha at hau1.edu.vn>
42
14
Chương 4. Giao thức tầng mạng
1-6/2006
Network: graph abstraction
5
v
2
u
2
1
3
x
w
3
5
z
1
y
2
1
Network = Graph = G(N,E).
N = tập hợp các routers = { u, v, w, x, y, z }.
E = tập các đường nối giữa các routers.
= { (u,v), (u,x), (v,x), (v,w), (x,w), (x,y), (w,y), (w,z), (y,z) }
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.
Chương 4. Giao thức tầng mạng
1-6/2006
43
Routing Algorithm classification
Thông tin tập trung hay phân tán?
Tĩnh hay động?
Tập trung:
Tĩnh:
mỗi router phải nắm giữ thông tin toàn
đường đi ít thay đổi
bộ mạng (topology, link cost…)
Động:
“link state” algorithms
đường đi thay đổi
Phân tán:
thường xuyên
router nắm được chi phí truyền tin tới các
các thông tin dẫn
router được nối trực tiếp với mình (hàng
đường được cập
xóm)
nhật định kỳ.
quá trình tính toán mang tính chất lặp đi
lặp lại, trao đổi thông tin giữa các
link cost thay đổi.
routers.
“distance vector” algorithms
Chương 4. Giao thức tầng mạng
1-6/2006
44
A Link-State Routing Algorithm
Giải thuật Dijkstra:
tất
cả các nút mạng có thông tin như nhau về các liên kết của toàn
bộ mạng.
cho phép tìm đường đi từ một nút tới tất cả các nút còn lại.
Ký hiệu:
c(i,j): chi phí phải trả để đi từ i tới j (trực tiếp)
D(v): giá trị hiện tại của chi phí phải trả để đi từ đỉnh xuất phát
tới đỉnh v.
p(v): đỉnh trước đỉnh v trên đường đi ngắn nhất
N: tập hợp đỉnh mà đường đi ngắn nhất đã được xác định.
1-6/2006
Chương 4. Giao thức tầng mạng
<dxha at hau1.edu.vn>
45
15
Chương 4. Giao thức tầng mạng
1-6/2006
Dijsktra’s Algorithm
1 Initialization:
2 N = {A}
3 for all nodes v
4
if v kề với A
5
then D(v) = c(A,v)
6
else D(v) = ∞
7
8 Loop
9 Tìm w không thuộc N sao cho D(w) nhỏ nhất
10 N = N + w
11 for all v kề với w và không thuộc N:
12
D(v) = min( D(v), D(w) + c(w,v) )
13 until tất cả nút thuộc N
Chương 4. Giao thức tầng mạng
1-6/2006
46
Dijkstra’s algorithm: example
Step
0
1
2
3
4
5
N
A
AD
ADE
ADEB
ADEBC
ADEBCF
D(B),p(B) D(C),p(C) D(D),p(D) D(E),p(E) D(F),p(F)
1,A
2,A
∞
5,A
∞
2,A
2,D
4,D
∞
2,A
3,E
4,E
3,E
4,E
4,E
5
2
A
3
B
2
1
C
3
D
1
5
F
1
E
2
Chương 4. Giao thức tầng mạng
1-6/2006
47
Distance Vector Routing Algorithm
Distance Table data structure
mỗi nút mạng có một bảng khoảng cách.
hàng: các nút có thể đến được.
cột: các nút có thể đến trực tiếp (hàng xóm)
Ví dụ: tại nút X, với đích Y đến qua nút Z:
X
D (Y,Z)
chi phí cho đường đi (XÆZÆ…ÆY)
= Z là nút kế tiếp cần đi tới
Z
= c(X,Z) + minw{D (Y,w)}
1-6/2006
Chương 4. Giao thức tầng mạng
<dxha at hau1.edu.vn>
48
16
Chương 4. Giao thức tầng mạng
1-6/2006
Distance Table: example
C
E
E
D
= 2+2 = 4
D
D (A,D)
B
D
A
1
14
5
B
7
8
5
C
6
9
4
D
4
11
2
D
2
D (C,D) = c(E,D) + minw {D (C,w)}
E
A
2
8
1
= c(E,D) + minw {D (A,w)}
= 2+3 = 5 loop!
E
cost to destination via
E
D ()
destination
A
1
B
7
B
D (A,B) = c(E,B) + minw{D (A,w)}
= 8+6 = 14
loop!
49
Chương 4. Giao thức tầng mạng
1-6/2006
Distance table Æ routing table
E
cost to destination via
Outgoing link
to use, cost
B
D
A
1
14
5
A
A,1
B
7
8
5
B
D,5
C
6
9
4
C
D,4
D
4
11
2
D
D,4
Distance table
destination
A
destination
D ()
Routing table
Chương 4. Giao thức tầng mạng
1-6/2006
50
DV Algorithm: Initialization
At all nodes, X:
1 Initialization:
2 for all adjacent nodes v:
3
D X(*,v) = infinity
/* the * operator means "for all rows" */
X
4
D (v,v) = c(X,v)
5 for all destinations, y
X
6
send min D (y,w) to each neighbor /* w over all X's neighbors */
w
1-6/2006
Chương 4. Giao thức tầng mạng
<dxha at hau1.edu.vn>
51
17
Chương 4. Giao thức tầng mạng
1-6/2006
DV Algorithm: Loop
8 loop
9 wait (until I see a link cost change to neighbor V
10
or until I receive update from neighbor V)
11
12 if (c(X,V) changes by d)
13 /* change cost to all dest's via neighbor v by d */
14 /* note: d could be positive or negative */
15 for all destinations y: D X(y,V) = DX(y,V) + d
16
17 else if (update received from V wrt destination Y)
18 /* shortest path from V to some Y has changed */
19 /* V has sent a new value for its min w DV(Y,w) */
20 /* call this received new value is "newval" */
21 for the single destination y: D X(Y,V) = c(X,V) + newval
22
23 if we have a new minw DX(Y,w)for any destination Y
24
send new value of min D X(Y,w) to all neighbors
w
26 forever
52
Chương 4. Giao thức tầng mạng
1-6/2006
DV Algorithm: example
X
2
Y
1
Z
7
Y
X
D (Z,Y) = c(X,Y) + minw {D (Z,w)}
= 2+1 = 3
Z
X
D (Y,Z) = c(X,Z) + minw{D (Y,w)}
= 7+1 = 8
Chương 4. Giao thức tầng mạng
1-6/2006
53
DV Algorithm: example
X
1-6/2006
2
Y
7
1
Z
Chương 4. Giao thức tầng mạng
<dxha at hau1.edu.vn>
54
18
Chương 4. Giao thức tầng mạng
1-6/2006
Một vài so sánh (LS và DV)
Link-State
Distance Vector
Cần nắm được thông tin toàn
bộ mạng
n nút, E links, nE msgs được
gửi mỗi lần
O(n2), nE msgs
Mỗi nút chỉ tính toán bảng dẫn
đường cho riêng mình.
Chỉ nắm giữ thông tin liên
quan tới các nút “hàng xóm”
msgs chỉ được gửi cho các nút
“hàng xóm”.
tốc độ hội tụ có thể khác nhau
tuỳ từng tình huống, đôi khi rơi
vào trạng thái lặp vô hạn.
Thông tin dẫn đường của nút
này được sử dụng bởi nút khác.
Một nút gặp sự cố có thể gây ảnh
hưởng tới các nút khác.
Chương 4. Giao thức tầng mạng
1-6/2006
55
Hierarchical Routing
Dẫn đường theo từng mức mạng, do:
Quy mô mạng Internet là rất lớn:
một
việc
Nhu
nút không thể chứa tất cả các bản ghi cho mọi đích!
cập nhật bảng dẫn đường tốn kém!
cầu mạng tự trị
Internet
= network of networks
quản trị mạng muốn điều khiển việc dẫn đường
(routing) trong mạng họ quản lý.
người
Chương 4. Giao thức tầng mạng
1-6/2006
56
Hierarchical Routing (cont)
Phân vùng routers, tạo thành các “autonomous systems”
(AS)
routers trong cùng AS sử dụng chung giao thức tìm đường,
gọi là “intra-AS” routing protocol.
routers
tại các AS khác nhau có thể sử dụng intra-AS routing
protocol khác nhau.
Gateway router:
router
sử
đặc biệt trong AS
dụng intra-AS routing protocol với các routers khác trong AS
sử
dụng inter-AS routing protocol với các gateway
routers khác.
1-6/2006
Chương 4. Giao thức tầng mạng
<dxha at hau1.edu.vn>
57
19
Chương 4. Giao thức tầng mạng
1-6/2006
Hierarchical Routing (cont)
C.b
a
C
Gateways:
B.a
A.a
b
A.c
d
A
a
a
c
B
•perform inter-AS
routing amongst
themselves
•perform intra-AS
routers with other
routers in their
AS
b
c
b
network layer
inter-AS, intra-AS
routing in
gateway A.c
link layer
physical layer
58
Chương 4. Giao thức tầng mạng
1-6/2006
Hierarchical Routing (cont)
Inter-AS
routing
between
A and B
C.b
a
Host
h1
1-6/2006
C
b
A.a
A.c
a
d
c
b
A
Intra-AS routing
within AS A
B.a
a
c
B
Host
h2
b
Intra-AS routing
within AS B
Chương 4. Giao thức tầng mạng
59
Ch4. The Network Layer
4.1 - Giới thiệu và chức năng của tầng mạng.
4.2 - Network service model (VC and Datagram).
4.3 - Thiết bị tầng mạng - Bộ định tuyến (router).
4.4 - Giao thức IP (Internet Protocol).
4.5 - Giải thuật chọn đường (Routing Algorithms).
4.6 - Chọn đường trong mạng Internet.
1-6/2006
Chương 4. Giao thức tầng mạng
<dxha at hau1.edu.vn>
60
20
Chương 4. Giao thức tầng mạng
1-6/2006
Routing in the Internet
Internet = nhiều Autonomous Systems (AS) :
Stub
AS: các công ty nhỏ: có một liên kết với AS khác.
AS: công ty lớn: nhiều liên kết tới AS
Multihomed
khác.
Transit AS: nhà cung cấp (móc nối các AS với nhau).
Two-level routing:
Intra-AS:
người quản trị có quyền chọn giải thuật cho
riêng mạng của mình
Inter-AS: giải thuật duy nhất (inter-AS routing: BGP)
Chương 4. Giao thức tầng mạng
1-6/2006
61
Internet AS Hierarchy
Intra-AS border (exterior gateway) routers
Inter-AS interior (gateway) routers
Chương 4. Giao thức tầng mạng
1-6/2006
62
Intra-AS Routing
Tên gọi khác: Interior Gateway Protocols (IGP)
Một số giao thức:
RIP:
Routing Information Protocol
OSPF:
Open Shortest Path First
IGRP:
Interior Gateway Routing Protocol (Cisco
proprietary)
1-6/2006
Chương 4. Giao thức tầng mạng
<dxha at hau1.edu.vn>
63
21
Chương 4. Giao thức tầng mạng
1-6/2006
RIP ( Routing Information Protocol)
Sử dụng Distance vector algorithm
Included in BSD-UNIX Distribution in 1982
Đơn vị đo khoảng cách: số lượng chặng (hop, tối đa = 15 hops)
Routing table được trao đổi 30 giây một lần thông qua RIP response
msg (RIP advertisement), mỗi msg chứa tối đa 25 bản ghi.
v1: RFC 1058; v2: RFC 1723
u
z
destination hops
u
1
v
2
w
2
x
3
y
3
z
2
v
A
B
C
D
w
x
y
64
Chương 4. Giao thức tầng mạng
1-6/2006
RIP: Example
z
w
A
x
D
y
B
C
Destination Network
w
y
z
x
Next Router
Num. of hops to dest.
….
....
A
B
B
--
….
2
2
7
1
Routing table in D
1-6/2006
Chương 4. Giao thức tầng mạng
65
RIP Table processing
RIP routing tables managed by application-level
process called route-d (daemon)
advertisements được gửi định kỳ, qua UDP
packets.
1-6/2006
Chương 4. Giao thức tầng mạng
<dxha at hau1.edu.vn>
66
22
Chương 4. Giao thức tầng mạng
1-6/2006
RIP Table example
Destination
-------------------127.0.0.1
192.168.2.
193.55.114.
192.168.3.
224.0.0.0
default
Gateway
Flags Ref
Use
Interface
-------------------- ----- ----- ------ --------127.0.0.1
UH
0 26492 lo0
192.168.2.5
U
2
13 fa0
193.55.114.6
U
3 58503 le0
192.168.3.5
U
2
25 qaa0
193.55.114.6
U
3
0 le0
193.55.114.129
UG
0 143454
Three attached class C networks (LANs)
Router only knows routes to attached LANs
Default router used to “go up”
Route multicast address: 224.0.0.0
Loopback interface (for debugging)
Chương 4. Giao thức tầng mạng
1-6/2006
67
OSPF (Open Shortest Path First)
“open”: publicly available; RFC 2178
Uses Link State algorithm
LS
packet dissemination
map at each node
Route computation using Dijkstra’s algorithm
Topology
OSPF advertisement carries one entry per neighbor router
Advertisements disseminated to entire AS (via flooding)
Carried
in OSPF messages directly over IP (rather than TCP or
UDP
1-6/2006
Chương 4. Giao thức tầng mạng
68
OSPF “advanced” features (not in RIP)
Security: các OSPF msgs đều chứa thông tin chứng thực
(authenticated).
Multiple same-cost paths: Cho phép truyền tin theo nhiều
đường có cùng chi phí với cùng một phiên truyền tin.
Diff. cost metrics for diff. TOS: Cho phép nhiều đơn vị đo
khác nhau cho từng loại dịch vụ (e.g., satellite link cost set
“low” for best effort; high for real time)
Integrated unicast and multicast support:
Multicast OSPF (MOSPF) uses same topology data
base as OSPF
Hierarchical OSPF in large domains.
1-6/2006
Chương 4. Giao thức tầng mạng
<dxha at hau1.edu.vn>
69
23
Chương 4. Giao thức tầng mạng
1-6/2006
Hierarchical OSPF
Two-level hierarchy: local area, backbone.
Link-state advertisements only in area
each nodes has detailed area topology; only know direction
(shortest path) to nets in other areas.
Area border routers: “summarize” distances to nets in own area,
advertise to other Area Border routers.
Backbone routers: run OSPF routing limited to backbone.
Boundary routers: connect to other AS’s.
70
Chương 4. Giao thức tầng mạng
1-6/2006
Internet inter-AS routing: BGP
BGP (Border Gateway Protocol): RFC 1771; RFC
1772; RFC 1773
R4
R5
R3
AS1
AS2
(RIP intra-AS
routing)
BGP
R2
R1
1-6/2006
BGP
(OSPF
intra-AS
routing)
Chương 4. Giao thức tầng mạng
<dxha at hau1.edu.vn>
AS3
(OSPF intra-AS
routing)
71
24
