3
ph
ươ
ng pháp quy ho
ạ
ch tuy
ế
n tính, tuy nhiên,
ñố
i v
ớ
i các m
ạ
ng l
ớ
n
(s
ố
l
ượ
ng b
ộ
ñị
nh tuy
ế
n lên
ñế
n hàng nghìn, hàng v
ạ
n) thì ph
ươ
ng
pháp quy ho
ạ
ch tuy
ế
n tính h
ầ
u nh
ư
không kh
ả
thì. Vì v
ậ
y,
ñề
tài này
s
ẽ
nêu ra m
ộ
t ph
ươ
ng pháp m
ớ
i áp d
ụ
ng gi
ả
i thu
ậ
t di truy
ề
n (Genetic
Algorithm -GA)
ñể
tìm ra m
ộ
t b
ộ
các tr
ọ
ng s
ố
t
ố
i
ư
u s
ẽ
ñượ
c gán vào
cho các thi
ế
t b
ị
ñị
nh tuy
ế
n.
6. Cấu trúc luận văn
V
ớ
i
ñị
nh h
ướ
ng nh
ư
trên, ngoài ph
ầ
n
Mở ñầu
và ph
ầ
n
Kết
luận và hướng phát triển
, lu
ậ
n v
ă
n g
ồ
m 3 ch
ươ
ng:
Chương 1
: T
ổ
ng quan v
ề
ñị
nh tuy
ế
n m
ạ
ng
Chương 2
: Bài toán
ướ
c l
ượ
ng nhu c
ầ
u truy
ề
n thông
Chương 3
: T
ố
i
ư
u hóa quá trình
ñị
nh tuy
ế
n m
ạ
ng b
ằ
ng gi
ả
i
thu
ậ
t di truy
ề
n.
4
CHƯƠNG 1
TỔNG QUAN VỀ ĐỊNH TUYẾN MẠNG
1.1. CÁC KHÁI NIỆM CƠ BẢN
1.1.1. Hệ thống tự trị (Autonomous System - AS)
Internet toàn c
ầ
u
ñượ
c t
ổ
ch
ứ
c theo t
ừ
ng kh
ố
i riêng l
ẻ
, ho
ạ
t
ñộ
ng t
ươ
ng
ñố
i
ñộ
c l
ậ
p v
ớ
i nhau g
ọ
i là nh
ữ
ng h
ệ
th
ố
ng t
ự
tr
ị
(
Autonomous System - AS
). M
ỗ
i AS bao g
ồ
m m
ộ
t ho
ặ
c m
ộ
t s
ố
nhóm
các
ñị
a ch
ỉ
IP, m
ỗ
i nhóm t
ượ
ng tr
ư
ng cho m
ộ
t m
ạ
ng con, s
ử
d
ụ
ng
chung m
ộ
t chính sách c
ụ
th
ể
, rõ ràng cho vi
ệ
c
ñị
nh tuy
ế
n và c
ũ
ng
ho
ạ
t
ñộ
ng d
ướ
i s
ự
ki
ể
m soát c
ủ
a m
ộ
t t
ậ
p th
ể
các chuyên gia
ñ
i
ề
u
hành m
ạ
ng.
Công vi
ệ
c thi
ế
t k
ế
m
ạ
ng th
ườ
ng
ñượ
c gi
ớ
i h
ạ
n trong ph
ạ
m vi
m
ộ
t h
ệ
th
ố
ng t
ự
tr
ị
AS. Có th
ể
nh
ậ
n th
ấ
y rõ r
ằ
ng, n
ế
u các AS c
ũ
ng
ñượ
c xây d
ự
ng và v
ậ
n hành theo m
ộ
t ph
ươ
ng th
ứ
c thì toàn b
ộ
h
ệ
th
ố
ng Internet s
ẽ
ho
ạ
t
ñộ
ng t
ố
t h
ơ
n v
ớ
i chi phí th
ấ
p và hi
ệ
u su
ấ
t cao,
tuy nhiên th
ự
c t
ế
l
ạ
i hoàn toàn không ph
ả
i nh
ư
v
ậ
y, m
ỗ
i AS hay ngay
c
ả
trong t
ừ
ng m
ạ
ng con c
ủ
a m
ộ
t AS c
ũ
ng th
ườ
ng
ñượ
c xây d
ự
ng và
v
ậ
n hành m
ộ
t cách
ñộ
c l
ậ
p v
ớ
i nhau, ch
ỉ
nh
ữ
ng n
ơ
i nào c
ầ
n thi
ế
t m
ớ
i
có nh
ữ
ng h
ợ
p
ñồ
ng, th
ỏ
a thu
ậ
n nh
ằ
m
ñả
m b
ả
o chúng k
ế
t n
ố
i
ñượ
c
v
ớ
i nhau.
1.1.2. Ðường ñi tối ưu cơ bản
1.2. TỔNG QUAN VỀ ĐỊNH TUYẾN MẠNG
1.2.1. Khái niệm ñịnh tuyến mạng
Định tuyến
(routing)
là quá trình ch
ọ
n l
ự
a các
ñườ
ng
ñ
i trên
m
ộ
t m
ạ
ng máy tính
ñể
g
ử
i d
ữ
li
ệ
u qua
ñ
ó.
5
Đị
nh tuy
ế
n m
ạ
ng
ñượ
c dùng trong l
ĩ
nh v
ự
c truy
ề
n thông
Internet
ñể
ch
ỉ
quá trình g
ồ
m hai thao tác: xác
ñị
nh
ñườ
ng truy
ề
n
(
path determination
) và chuy
ể
n gói tin (
forwarding
) theo con
ñườ
ng
ñ
ã ch
ọ
n, hai thao tác này luôn luôn
ñ
i kèm v
ớ
i nhau trong thi
ế
t b
ị
ph
ầ
n c
ứ
ng chuyên dùng
ñượ
c g
ọ
i là b
ộ
ñị
nh tuy
ế
n
(
router
).
Trong các m
ạ
ng thông tin khác nhau, vi
ệ
c xác
ñị
nh
ñườ
ng
truy
ề
n c
ũ
ng di
ễ
n ra khác nhau. Tuy nhiên, cách xác
ñị
nh
ñườ
ng
truy
ề
n nào c
ũ
ng g
ồ
m hai công vi
ệ
c c
ơ
b
ả
n :
Thứ nhất,
là thu th
ậ
p và phân phát thông tin v
ề
tình tr
ạ
ng c
ủ
a
m
ạ
ng (nh
ư
tr
ạ
ng thái
ñườ
ng truy
ề
n, tình tr
ạ
ng t
ắ
c ngh
ẽ
n .) và c
ủ
a
thông tin c
ầ
n truy
ề
n (nh
ư
l
ư
u l
ượ
ng, b
ă
ng thông, t
ố
c
ñộ
, yêu c
ầ
u d
ị
ch
v
ụ
.). Các thông tin này s
ẽ
ñượ
c s
ử
d
ụ
ng làm c
ơ
s
ở
cho vi
ệ
c xác
ñị
nh
ñườ
ng truy
ề
n.
Thứ hai,
là vi
ệ
c phân tích, tính toán
ñể
ch
ọ
n ra
ñườ
ng truy
ề
n
kh
ả
d
ụ
ng (c
ũ
ng có th
ể
là
ñườ
ng truy
ề
n t
ố
i
ư
u) d
ự
a trên các thông tin
tr
ạ
ng thái trên.
Đườ
ng truy
ề
n kh
ả
d
ụ
ng là
ñườ
ng truy
ề
n tho
ả
mãn
m
ọ
i yêu c
ầ
u c
ủ
a thông tin c
ầ
n truy
ề
n (nh
ư
t
ố
c
ñộ
, b
ă
ng thông) và
ñ
i
ề
u ki
ệ
n c
ủ
a m
ạ
ng (nh
ư
kh
ả
n
ă
ng c
ủ
a
ñườ
ng truy
ề
n). Còn
ñườ
ng
truy
ề
n t
ố
i
ư
u (theo m
ộ
t tiêu chu
ẩ
n nào
ñ
ó) là
ñườ
ng truy
ề
n t
ố
t nh
ấ
t
trong nh
ữ
ng
ñườ
ng truy
ề
n kh
ả
d
ụ
ng.
1.2.2. Phân loại ñịnh tuyến mạng
1.2.2.1. Định tuyến tĩnh
Đị
nh tuy
ế
n t
ĩ
nh là d
ạ
ng
ñị
nh tuy
ế
n mà các thông tin v
ề
ñườ
ng
ñ
i ph
ả
i do ng
ườ
i qu
ả
n tr
ị
m
ạ
ng nh
ậ
p cho router. Khi c
ấ
u trúc m
ạ
ng
có b
ấ
t k
ỳ
thay
ñổ
i nào thì chính ng
ườ
i qu
ả
n tr
ị
m
ạ
ng ph
ả
i xoá ho
ặ
c
thêm các thông tin v
ề
ñườ
ng
ñ
i cho router. Các
ñườ
ng
ñ
i này là c
ố
ñị
nh nên trong h
ệ
th
ố
ng m
ạ
ng l
ớ
n vi
ệ
c b
ả
o trì b
ả
ng
ñị
nh tuy
ế
n cho
6
router t
ố
n r
ấ
t nhi
ề
u th
ờ
i gian.
Đị
nh tuy
ế
n t
ĩ
nh là cách
ñị
nh tuy
ế
n
không linh ho
ạ
t, không có kh
ả
n
ă
ng t
ự
thích nghi khi các
ñ
i
ề
u ki
ệ
n
truy
ề
n thông thay
ñổ
i nên th
ườ
ng phù h
ợ
p v
ớ
i h
ệ
th
ố
ng m
ạ
ng nh
ỏ
ho
ặ
c tuy
ế
n
ñơ
n ít có bi
ế
n
ñổ
i v
ề
thông tin
ñị
nh tuy
ế
n.
1.2.2.2. Định tuyến ñộng
Đị
nh tuy
ế
n
ñộ
ng là d
ạ
ng
ñị
nh tuy
ế
n mà các
ñườ
ng
ñ
i
ñượ
c t
ự
ñộ
ng c
ậ
p nh
ậ
t b
ở
i router, vi
ệ
c l
ự
a ch
ọ
n tuy
ế
n
ñườ
ng d
ự
a trên thông
tin tr
ạ
ng thái hi
ệ
n th
ờ
i c
ủ
a m
ạ
ng. Thông tin tr
ạ
ng thái có th
ể
ñ
o ho
ặ
c
d
ự
ñ
oán và tuy
ế
n
ñườ
ng có th
ể
thay
ñổ
i khi topo m
ạ
ng ho
ặ
c l
ư
u
l
ượ
ng m
ạ
ng thay
ñổ
i. Thông tin
ñị
nh tuy
ế
n
ñượ
c c
ậ
p nh
ậ
t t
ự
ñộ
ng
vào trong các b
ả
ng
ñị
nh tuy
ế
n c
ủ
a các node m
ạ
ng tr
ự
c tuy
ế
n, và
ñ
áp
ứ
ng tính th
ờ
i gian th
ự
c nh
ằ
m tránh t
ắ
c ngh
ẽ
n c
ũ
ng nh
ư
t
ố
i
ư
u hi
ệ
u
n
ă
ng m
ạ
ng.
Đị
nh tuy
ế
n
ñộ
ng có th
ể
thích
ứ
ng v
ớ
i vi
ệ
c thay
ñổ
i ki
ế
n
trúc m
ạ
ng và l
ư
u l
ượ
ng truy
ề
n thông, phù h
ợ
p
ñố
i v
ớ
i m
ạ
ng l
ớ
n,
th
ườ
ng bi
ế
n
ñổ
i trong quá trình ho
ạ
t
ñộ
ng.
Chính vì
ñị
nh tuy
ế
n t
ĩ
nh
ñ
òi h
ỏ
i ng
ườ
i qu
ả
n tr
ị
m
ạ
ng ph
ả
i c
ấ
u
hình m
ọ
i thông tin v
ề
ñườ
ng
ñ
i cho router nên nó không có
ñượ
c tính
linh ho
ạ
t nh
ư
ñị
nh tuy
ế
n
ñộ
ng. Trong nh
ữ
ng h
ệ
th
ố
ng m
ạ
ng l
ớ
n,
ñị
nh
tuy
ế
n t
ĩ
nh th
ườ
ng
ñượ
c s
ử
d
ụ
ng k
ế
t h
ợ
p v
ớ
i giao th
ứ
c
ñị
nh tuy
ế
n
ñộ
ng cho m
ộ
t s
ố
m
ụ
c
ñ
ích
ñặ
c bi
ệ
t.
1.2.3. Các giao thức ñịnh tuyến mạng
1.2.3.1. Định tuyến theo ñường ñi ngắn nhất
Để
ch
ọ
n m
ộ
t tuy
ế
n
ñườ
ng
ñ
i gi
ữ
a hai b
ộ
ñị
nh tuy
ế
n, thu
ậ
t toán
ch
ỉ
c
ầ
n tìm ra
ñườ
ng
ñ
i ng
ắ
n nh
ấ
t gi
ữ
a chúng trên
ñồ
th
ị
.
Khái ni
ệ
m
ñường ñi ngắn nhất
ở
ñ
ây có m
ộ
t s
ố
v
ấ
n
ñề
c
ầ
n
ph
ả
i làm rõ. M
ộ
t cách
ñể
ñ
o
ñộ
dài
ñườ
ng
ñ
i là s
ố
l
ượ
ng các nút mà
nó
ñ
i qua (còn
ñượ
c g
ọ
i là s
ố
b
ướ
c nh
ả
y). Bên c
ạ
nh các
ñộ
ñ
o s
ố
7
b
ướ
c nh
ả
y và kho
ả
ng cách
ñị
a lý, m
ộ
t s
ố
ñộ
ñ
o khác c
ũ
ng có th
ể
ñượ
c s
ử
d
ụ
ng. Ví d
ụ
, m
ỗ
i cung có th
ể
ñượ
c gán nhãn t
ươ
ng
ứ
ng v
ớ
i
ñộ
tr
ễ
trung bình c
ủ
a các gói tin do ph
ả
i x
ế
p hàng
ñợ
i tr
ướ
c khi
ñượ
c
truy
ề
n
ñ
i. V
ớ
i nhãn
ñượ
c gán ki
ể
u này thì
ñườ
ng d
ẫ
n ng
ắ
n nh
ấ
t
chính là
ñườ
ng truy
ề
n nhanh nh
ấ
t thay vì là
ñườ
ng ít b
ướ
c nh
ả
y nh
ấ
t
hay
ñư
òng ng
ắ
n nh
ấ
t xét v
ề
kho
ả
ng cách v
ậ
t lý.
Trong tr
ườ
ng h
ợ
p t
ổ
ng quát, các nhãn trên m
ỗ
i cung
ñượ
c tính
nh
ư
m
ộ
t hàm theo kho
ả
ng cách, b
ă
ng thông, l
ư
u l
ượ
ng trung bình,
chi phí truy
ề
n tin, th
ờ
i gian ch
ờ
trung bình,
ñộ
tr
ễ
,… và nh
ữ
ng y
ế
u t
ố
khác. B
ằ
ng cách thay
ñổ
i hàm tr
ọ
ng s
ố
, thu
ậ
t toán s
ẽ
tính l
ạ
i
ñượ
c
ñườ
ng
ñ
i “ng
ắ
n nh
ấ
t” tùy theo s
ố
l
ượ
ng các y
ế
u t
ố
ñượ
c ch
ọ
n.
Cho
ñế
n nay,
ñ
ã có khá nhi
ề
u gi
ả
i thu
ậ
t
ñượ
c
ñư
a ra nh
ằ
m gi
ả
i
thuy
ế
t vi
ệ
c tính toán
ñườ
ng
ñ
i ng
ắ
n nh
ấ
t trên
ñồ
th
ị
, nh
ư
ng gi
ả
i thu
ậ
t
Dijkstra (1959) v
ẫ
n
ñượ
c xem là hi
ệ
u qu
ả
nh
ấ
t và
ñượ
c s
ử
d
ụ
ng ph
ổ
bi
ế
n trong các nghi th
ứ
c
ñị
nh tuy
ế
n theo
ñườ
ng d
ẫ
n ng
ắ
n nh
ấ
t hi
ệ
n
nay.
1.2.3.2. Định tuyến ngập lụt (Flooding)
1.2.3.3. Định tuyến theo vectơ khoảng cách
Hai gi
ả
i thu
ậ
t
ñộ
ng thông d
ụ
ng nh
ấ
t hi
ệ
n nay là
ñịnh tuyến
theo vectơ khoảng cách
và
ñịnh tuyến theo tình trạng kết nối
. Gi
ả
i
thu
ậ
t
ñị
nh tuy
ế
n theo vect
ơ
kho
ả
ng cách ho
ạ
t
ñộ
ng d
ự
a vào vi
ệ
c duy
trì m
ộ
t hàng (
ñượ
c g
ọ
i là m
ộ
t
vectơ
) bên trong m
ỗ
i b
ộ
ñị
nh tuy
ế
n cho
bi
ế
t
khoảng cách ñược biết
t
ố
t nh
ấ
t t
ớ
i m
ỗ
i nút
ñ
ích và c
ổ
ng nào s
ẽ
ñượ
c s
ử
d
ụ
ng
ñể
ñ
i
ñế
n
ñ
ó, hàng này
ñượ
c c
ậ
p nh
ậ
t th
ườ
ng xuyên
nh
ờ
vi
ệ
c trao
ñổ
i thông tin v
ớ
i các b
ộ
ñị
nh tuy
ế
n k
ế
c
ậ
n.
8
1.2.3.4. Định tuyến theo tình trạng kết nối
1.2.3.5. Định tuyến phân cấp
1.2.3.6. Định tuyến quảng bá (broadcast)
1.2.3.7. Ðịnh tuyến theo nhóm (multicast)
1.2.3.8. Định tuyến cho mạng có các trạm di ñộng
1.2.3.9. Định tuyến cho mạng di ñộng hỗn tạp (Ad Hoc)
1.2.3.10. Tìm kiếm các nút trong mạng ñiểm nối ñiểm (Peer-to-
Peer)
1.3. KẾT LUẬN CUỐI CHƯƠNG
Để
m
ộ
t m
ạ
ng máy tính có th
ể
t
ồ
n t
ạ
i theo th
ờ
i gian thì
ñ
òi h
ỏ
i
ph
ả
i có các thao tác v
ậ
n hành thích h
ợ
p. Có r
ấ
t nhi
ề
u các y
ế
u t
ố
khác
nhau
ả
nh h
ưở
ng
ñế
n su
ố
t quá trình ho
ạ
t
ñộ
ng c
ủ
a m
ạ
ng,
ñ
ôi khi
trong b
ả
n thân nh
ữ
ng y
ế
u t
ố
này l
ạ
i ch
ứ
a
ñự
ng mâu thu
ẫ
n l
ẫ
n nhau.
Vì v
ậ
y s
ẽ
không th
ể
có m
ộ
t gi
ả
i pháp chung
ñ
em l
ạ
i hi
ệ
u qu
ả
t
ố
i
ư
u
cho t
ấ
t c
ả
các mô hình m
ạ
ng, mà ng
ượ
c l
ạ
i, nhà qu
ả
n tr
ị
c
ầ
n ph
ả
i
xem xét k
ỹ
l
ưỡ
ng t
ừ
ng hoàn c
ả
nh c
ụ
th
ể
ñể
xác
ñị
nh
ñượ
c nh
ữ
ng y
ế
u
t
ố
nào c
ầ
n ph
ả
i
ñượ
c
ư
u tiên tr
ướ
c, nh
ữ
ng y
ế
u t
ố
nào có th
ể
dung hòa
ñượ
c l
ẫ
n nhau,
ñể
t
ừ
ñ
ó
ñư
a ra quy
ế
t
ñị
nh sáng su
ố
t trong vi
ệ
c l
ự
a
ch
ọ
n ph
ươ
ng án thích h
ợ
p cho h
ệ
th
ố
ng m
ạ
ng c
ủ
a mình.
9
CHƯƠNG 2
BÀI TOÁN ƯỚC LƯỢNG
NHU CẦU TRUYỀN THÔNG
2.1. PHÁT BIỂU BÀI TOÁN
2.1.1. Vai trò và mục tiêu ñặt ra của bài toán
Nhu c
ầ
u truy
ề
n thông gi
ữ
a các c
ặ
p nút ngu
ồ
n -
ñ
ích trên m
ạ
ng
th
ườ
ng
ñượ
c bi
ể
u di
ễ
n d
ướ
i d
ạ
ng ma tr
ậ
n g
ọ
i là
ma trận nhu cầu
truyền thông
, cùng v
ớ
i
sơ ñồ cấu trúc mạng
và
nghi thức ñịnh tuyến
,
chúng làm nên nh
ữ
ng y
ế
u t
ố
c
ơ
b
ả
n cho vi
ệ
c giám sát, phân tích và
t
ố
i
ư
u hóa quá trình truy
ề
n d
ữ
li
ệ
u trên m
ạ
ng. H
ơ
n n
ữ
a, vi
ệ
c thu th
ậ
p
nhu c
ầ
u truy
ề
n thông trong m
ộ
t kho
ả
ng th
ờ
i gian dài s
ẽ
r
ấ
t h
ữ
u ích
cho vi
ệ
c thi
ế
t k
ế
m
ạ
ng, l
ậ
p k
ế
ho
ạ
ch phát tri
ể
n m
ở
r
ộ
ng m
ạ
ng và t
ừ
ñ
ó
ñư
a ra
ñượ
c các chi
ế
n l
ượ
c kinh doanh thích h
ợ
p. Thông th
ườ
ng
v
ớ
i nh
ữ
ng m
ạ
ng nh
ỏ
, l
ư
u l
ượ
ng truy
ề
n không cao, thì các ma tr
ậ
n
này có th
ể
ñượ
c thu th
ậ
p m
ộ
t cách tr
ự
c ti
ế
p thông qua ch
ứ
c n
ă
ng l
ư
u
v
ế
t (log) c
ủ
a các b
ộ
ñị
nh tuy
ế
n. Tuy nhiên, c
ơ
ch
ế
này s
ẽ
không còn
kh
ả
thi
ñố
i v
ớ
i các m
ạ
ng tr
ụ
c l
ớ
n,
ở
ñ
ó l
ư
u l
ượ
ng truy
ề
n r
ấ
t cao, b
ộ
x
ử
lý và b
ộ
nh
ớ
trong các thi
ế
t b
ị
ñị
nh tuy
ế
n h
ầ
u nh
ư
ph
ả
i t
ậ
p trung
h
ế
t cho vi
ệ
c luân chuy
ể
n các gói tin, n
ế
u b
ậ
t ch
ế
ñộ
l
ư
u v
ế
t
ñể
thu
th
ậ
p thông tin nh
ằ
m xây d
ự
ng ma tr
ậ
n nhu c
ầ
u truy
ề
n thông thì
chúng s
ẽ
tr
ở
nên trì tr
ệ
không th
ể
ch
ấ
p nh
ậ
n
ñượ
c. Ng
ượ
c l
ạ
i, thông
tin v
ề
l
ư
u l
ượ
ng truy
ề
n -
ở
ñ
ây chúng ta g
ọ
i là
tải trọng
- trên t
ừ
ng
c
ổ
ng (interface) c
ủ
a các thi
ế
t b
ị
ñị
nh tuy
ế
n thì h
ầ
u nh
ư
luôn có s
ẵ
n
và có th
ể
ñượ
c thu th
ậ
p m
ộ
t cách d
ễ
dàng thông qua nghi th
ứ
c qu
ả
n
tr
ị
m
ạ
ng
ñơ
n gi
ả
n (SNMP).
10
Đế
n
ñ
ây, chúng ta
ñ
ã có th
ể
th
ấ
y rõ vai trò không th
ể
thi
ế
u c
ủ
a
ma tr
ậ
n nhu c
ầ
u truy
ề
n thông, tuy nhiên vi
ệ
c xác
ñị
nh chính xác
chúng là
ñ
i
ề
u h
ầ
u nh
ư
không th
ể
th
ự
c hi
ệ
n
ñượ
c, vì v
ậ
y
ñề
tài s
ẽ
s
ử
d
ụ
ng m
ộ
t ph
ươ
ng pháp nh
ằ
m
ước lượng ma trận nhu cầu truyền
thông
d
ự
a vào
thông tin tải trọng trên từng kết nối
,
sơ ñồ cấu trúc
mạng
và
nghi thức truyền thông ñ
ang s
ử
d
ụ
ng.
2.1.2. Mô hình hóa bài toán
2.2. CÁC PHƯƠNG PHÁP ƯỚC LƯỢNG NHU CẦU
TRUYỀN THÔNG
2.2.1. Phương pháp suy diễn dựa vào xác suất
Có b
ố
n y
ế
u t
ố
làm
ñầ
u vào cho các ph
ươ
ng pháp d
ự
a vào lý
thuy
ế
t xác su
ấ
t: nh
ữ
ng gi
ả
ñị
nh v
ề
xác su
ấ
t phân b
ố
c
ủ
a nhu c
ầ
u
truy
ề
n thông s
ẽ
quy
ế
t
ñị
nh chi
ế
n l
ượ
c
ñể
ti
ế
n hành các b
ướ
c k
ế
ti
ế
p
và
ñ
ó c
ũ
ng chính là y
ế
u t
ố
ñể
phân bi
ệ
t s
ự
khác nhau gi
ữ
a các
ph
ươ
ng pháp. Y
ế
u t
ố
ñầ
u vào th
ứ
hai chính là ma tr
ậ
n nhu c
ầ
u truy
ề
n
thông tr
ướ
c
ñ
ó,
ñượ
c dùng làm kh
ở
i
ñ
i
ể
m cho thu
ậ
t toán. Tham s
ố
k
ế
ti
ế
p là tr
ọ
ng s
ố
c
ủ
a các k
ế
t n
ố
i
ñượ
c s
ử
ñụ
ng
ñể
tính
ñườ
ng
ñ
i ng
ắ
n
nh
ấ
t nh
ằ
m xây d
ự
ng nên ma tr
ậ
n
ñị
nh tuy
ế
n A. Tham s
ố
cu
ố
i cùng là
t
ả
i tr
ọ
ng c
ủ
a các k
ế
t n
ố
i
ñượ
c thu th
ậ
p tr
ự
c ti
ế
p t
ừ
các thi
ế
t b
ị
ñị
nh
tuy
ế
n thông qua nghi th
ứ
c SNMP dùng
ñể
áp
ñặ
t các ràng bu
ộ
c trên
ma tr
ậ
n nhu c
ầ
u truy
ề
n thông s
ẽ
ướ
c l
ượ
ng.
2.2.2. Phương pháp quy hoạch tuyến tính (Linear
Programming)
2.2.3. Phương pháp suy diễn Tomography
Ph
ươ
ng pháp tomography
ñ
ã
ñượ
c áp d
ụ
ng vào bài toán
ướ
c
l
ượ
ng nhu c
ầ
u truy
ề
n thông,
ở
ñ
ây ta
ñ
o
ñượ
c t
ổ
ng l
ư
u l
ượ
ng thông
11
tin truy
ề
n trên m
ỗ
i k
ế
t n
ố
i m
ạ
ng b
ằ
ng nghi th
ứ
c SNMP và bi
ế
t
ñượ
c
c
ấ
u trúc bên trong c
ủ
a m
ạ
ng thông qua chính sách
ñị
nh tuy
ế
n, v
ấ
n
ñề
c
ủ
a chúng ta là ph
ả
i tính ng
ượ
c l
ạ
i
ñượ
c nhu c
ầ
u truy
ề
n thông gi
ữ
a
t
ừ
ng c
ặ
p k
ế
t n
ố
i
ñ
ó.
2.2.4. Phương pháp suy diễn dựa vào mô hình trọng lực
(Gravity)
M
ộ
t trong nh
ữ
ng ph
ươ
ng pháp
ướ
c l
ượ
ng ma tr
ậ
n nhu c
ầ
u
truy
ề
n thông
ñơ
n gi
ả
n nh
ấ
t là d
ự
a vào mô hình l
ự
c h
ấ
p d
ẫ
n. Theo
lu
ậ
t h
ấ
p d
ẫ
n Newton thì l
ự
c hút gi
ữ
a hai v
ậ
t th
ể
t
ỉ
l
ệ
thu
ậ
n v
ớ
i tích
kh
ố
i l
ượ
ng c
ủ
a hai v
ậ
t th
ể
chia cho bình ph
ươ
ng kho
ả
ng cách gi
ữ
a
chúng.
2.3. THUẬT TOÁN TOMO-GRAVITY
2.3.1. Giới thiệu thuật toán
Nh
ư
ñ
ã
ñề
c
ậ
p
ở
trên, trong c
ả
hai ph
ươ
ng pháp
ướ
c l
ượ
ng
nhu c
ầ
u truy
ề
n thông d
ự
a vào mô hình gravity và tomography
ñề
u có
nh
ữ
ng
ư
u và khuy
ế
t
ñ
i
ể
m riêng c
ủ
a nó, nh
ư
ng nhìn chung c
ả
hai
ph
ươ
ng pháp
ñề
u không cho k
ế
t qu
ả
t
ố
t nh
ư
mong
ñợ
i. Vì v
ậ
y
ở
ñ
ây
chúng ta s
ẽ
nêu ra m
ộ
t gi
ả
i pháp k
ế
t h
ợ
p
ư
u
ñ
i
ể
m c
ủ
a c
ả
hai ph
ươ
ng
pháp trên và
ñặ
t tên là TomoGravity, gi
ả
i pháp này t
ậ
n d
ụ
ng
ñượ
c c
ả
nguyên lý h
ấ
p d
ẫ
n thông tin gi
ữ
a các nút và nh
ữ
ng ràng bu
ộ
c v
ề
t
ả
i
tr
ọ
ng c
ủ
a các k
ế
t n
ố
i trên mô hình tomography.
2.3.2. Sơ ñồ thuật toán
2.3.3. Chi tiết thuật toán
Bước 1:
Gi
ả
i bài toán
ướ
c l
ượ
ng nhu c
ầ
u truy
ề
n thông
theo mô hình tr
ọ
ng l
ự
c c
ả
i ti
ế
n
12
Bước 2:
Tìm trong s
ố
nh
ữ
ng l
ờ
i gi
ả
i thu
ộ
c không gian
vect
ơ
b
ị
ràng bu
ộ
c b
ở
i các
ñ
i
ề
u ki
ệ
n thu th
ậ
p
ñượ
c qua ph
ươ
ng pháp
tomography m
ộ
t l
ờ
i gi
ả
i g
ầ
n nh
ấ
t so v
ớ
i l
ờ
i gi
ả
i thu
ñượ
c
ở
b
ướ
c th
ứ
nh
ấ
t
2.4. CÁC GIẢI THUẬT TÌM ĐƯỜNG ĐI TỐI ƯU
Đườ
ng
ñ
i t
ố
i
ư
u t
ừ
A
ñế
n B là
ñườ
ng
ñ
i “ng
ắ
n nh
ấ
t” trong s
ố
các
ñườ
ng
ñ
i có th
ể
. Tuy nhiên khái ni
ệ
m “ng
ắ
n nh
ấ
t” có th
ể
ñượ
c
hi
ể
u theo nhi
ề
u ý ngh
ĩ
a khác nhau tùy thu
ộ
c vào
ñơ
n v
ị
dùng
ñể
ñ
o chi
ề
u dài
ñườ
ng
ñ
i.
Đố
i v
ớ
i các router, các
ñạ
i l
ượ
ng sau có
th
ể
ñượ
c s
ử
d
ụ
ng
ñể
ñ
o
ñộ
dài
ñườ
ng
ñ
i:
S
ố
l
ượ
ng các router trung gian ph
ả
i
ñ
i qua (HOP)
Độ
trì hoãn trung bình c
ủ
a các gói tín
C
ướ
c phí truy
ề
n tin
M
ỗ
i gi
ả
i thu
ậ
t ch
ọ
n
ñườ
ng tr
ướ
c tiên ph
ả
i ch
ọ
n cho
mình
ñơ
n v
ị
ñ
o chi
ề
u dài
ñườ
ng
ñ
i.
Để
xác
ñị
nh
ñượ
c
ñườ
ng
ñ
i t
ố
i
ư
u, các gi
ả
i thu
ậ
t ch
ọ
n
ñườ
ng
s
ử
d
ụ
ng ph
ươ
ng pháp
ñồ
th
ị
ñể
tính toán. Tr
ướ
c tiên, nó mô hình hóa
tình tr
ạ
ng m
ạ
ng thành m
ộ
t
ñồ
th
ị
có các
ñặ
c
ñ
i
ể
m nh
ư
sau:
Nút là các router.
C
ạ
nh n
ố
i li
ề
n 2 nút là
ñườ
ng truy
ề
n n
ố
i hai router.
Trên m
ỗ
i c
ạ
nh có giá
ñ
ó là chi
ề
u dài
ñườ
ng
ñ
i gi
ữ
a 2
router thông qua
ñườ
ng truy
ề
n n
ố
i hai router .
Chi
ề
u dài
ñườ
ng
ñ
i t
ừ
nút A
ñế
n nút B là t
ổ
ng t
ấ
t c
ả
các
giá c
ủ
a các c
ạ
nh n
ằ
m trên
ñườ
ng
ñ
i. N
ế
u không có
ñườ
ng
ñ
i gi
ữ
a
2 router thì xem nh
ư
giá là vô cùng. Trên
ñồ
th
ị
này s
ẽ
th
ự
c hi
ệ
n
vi
ệ
c tính toán tìm
ñườ
ng
ñ
i ng
ắ
n nh
ấ
t.
Không có nhận xét nào:
Đăng nhận xét