1
BỘ GIÁO DỤC VÀ
ĐÀO TẠO
TẬP ĐOÀN BƢU CHÍNH
VIỄN THÔNG VIỆT NAM
HỌC VIỆN CÔNG NGHỆ BƢU CHÍNH VIỄN THÔNG
HẠ THỊ ÁNH NGHIÊN CỨU CÁC PHƢƠNG PHÁP ĐỊNH TUYẾN TỐI ƢU
TRONG MẠNG VIỄN THÔNG CHUYÊN NGÀNH : KỸ THUẬT ĐIỆN TỬ
MÃ SỐ: 60.52.70 TÓM TẮT LUẬN VĂN THẠC SĨ KỸ THUẬT

HÀ NỘI - 2010

2 MỞ ĐẦU

1.1. KHÁI NIỆM VỀ ĐỊNH TUYẾN
Định tuyến là quá trình xác lập đƣờng thông trên mạng để kết nối
thuê bao gọi đi với thuê bao bị gọi. Khi một cuộc gọi xuất phát từ thuê
bao, trƣớc hết cần xác định xem hiện có đƣờng thông nào trên mạng có thể
dùng để nối cuộc gọi tới đích đƣợc không, nếu có (thông thƣờng là sẽ có
một tập hợp các đƣờng thông) ta phải quyết định chọn đƣờng thông nào,
hoặc nếu không còn đƣờng thông nào rỗi cả thì ta cần xử lý nhƣ thế nào:
hủy hay chờ,…
Có nhiều yếu tố ảnh hƣởng tới sự quyết định này nhƣ: số đƣờng
thông lý thuyết trên mạng có thể dùng để kết nối hai thuê bao, trạng thái
(bận/rỗi) của các đƣờng trung kế, các nút chuyển mạch… Để kết nối cuộc
gọi, cần có các quy định về việc xác định đƣờng thông, gọi là quy tắc định
tuyến (chọn đƣờng), thƣờng đƣợc biểu diễn dƣới dạng các bảng định
tuyến. Bảng định tuyến thông thƣờng là danh mục các đƣờng thông theo
một thứ tự nhất định để theo đó tổng đài sẽ chọn đƣờng để xác lập cuộc
gọi.
1.2. CÁC PHƢƠNG PHÁP ĐỊNH TUYẾN TRONG MẠNG VIỄN
THÔNG
1.2.1. Định tuyến chia tải (Load sharing)
Định tuyến chia tải có nguyên lý cơ bản nhƣ sau: giả sử ta có một
tập hợp các đƣờng thông k, với các đƣờng k
1
, k
2
, k
3
… lƣu lƣợng tới t
n
sẽ
đƣợc phân chia thành các lƣu lƣợng nhỏ t

tới việc cần phải chọn đƣờng thông một cách linh hoạt hơn, cụ thể là
đƣờng thông sẽ đƣợc chọn từ một tập hợp các đƣờng thông có thể dùng để
kết nối, theo những điều kiện và quy tắc cụ thể.
1.2.2. Định tuyến thay thế (Alternate Routing)
Định tuyến thay thế đƣợc sử dụng ngay từ khi mạng viễn thông
đầu tiên đƣợc thiết lập. Trong định tuyến thay thế, các đƣờng thông dùng
để kết nối đƣợc sắp xếp theo một thứ tự nhất định từ trƣớc và cuộc gọi sẽ
đƣợc kết nối trên đƣờng thông còn kênh trung kế rỗi đầu tiên trong thứ tự
này. Việc tìm kiếm đƣờng thông đƣợc bắt đầu từ đƣờng đầu tiên trong thứ
tự (còn gọi là đƣờng ƣu tiên 1 – first choice), nếu đƣờng thông này bận thì
sẽ xét đƣờng tiếp theo (second choice)… cho tới khi tìm đƣợc đƣờng
thông rỗi. Đƣờng thông đứng cuối trong thứ tự này (last choice) đƣợc gọi
là đường cuối cùng (final router) và nếu đƣờng thông cuối cùng này cũng
bận thì cuộc gọi sẽ bị loại bỏ. Có thể nêu ra một số phƣơng pháp tiêu biểu
5 nhƣ: định tuyến thay thế phân bậc cố định, định tuyến thay thế động và
định tuyến thay thế động không phân bậc.
1.2.3. Định tuyến thích nghi (Adaptive routing)
Cùng với sự tiến bộ về công nghệ, việc ra đời các thế hệ tổng đài
điện tử số điều khiển bởi chƣơng trình lƣu trữ, các hệ thống truyền dẫn số,
các hệ thống báo hiệu kênh chung… đã loại bỏ đƣợc tất cả những hạn chế
đó và cho ta khả năng có đƣợc lƣợng thông tin lớn gấp bội để quản lý và
điều khiển mạng lƣới. Những ƣu thế này đã cho phép các nhà khai thác
mạng nghiên cứu ứng dụng những phƣơng pháp định tuyến phức tạp hơn,
hiện đại hơn, gần với thực trạng mạng lƣới hơn, đó là các phƣơng pháp
định tuyến theo trạng thái thực của mạng, đƣợc gọi chung là định tuyến
thích nghi.Các phƣơng pháp định tuyến tự thích nghi đƣợc sử dụng phổ
biến hiện nay là định tuyến tự thích nghi theo dung lƣợng còn lại: Residual

phòng các tuyền truyền dẫn, chuyển hƣớng tuyến, khôi phục tuyến một
cách nhanh chóng để nâng cao độ sử dụng các tuyến truyền dẫn và chất
lƣợng của mạng trong những điều kiện nguy cấp.
1.2.6. Định tuyến động hỗn hợp (Mixed Dynamic Routing)
Với xu thế hội tụ giữa truyền thông và tin học, giữa các mạng
PSTN, DCN, IP…, trong tƣơng lai gần chúng ta sẽ chứng kiến sự tiến hóa
lên một thế hệ mạng thông tin mới – Next Generation Networks. Mạng thế
hệ mới này sẽ bao gồm một mạng cốt lõi băng rộng (core network) xây
dựng trên cơ sở công nghệ gói (packet based network), còn các mạng hiện
tại sẽ bao quanh (edge network), kết nối và tƣơng tác với nhau qua phần
cốt lõi này. Để đáp ứng đƣợc các yêu cầu rất cao về băng thông, độ tổn
thất cũng nhƣ tính thời gian thực của các dịch vụ tƣơng lai, các phƣơng
pháp định tuyến rất mới theo công nghệ IP và mạng neural đang đƣợc các
chuyên gia tích cực nghiên cứu phát triển. Các phƣơng pháp định tuyến
này sẽ đƣợc sử dụng trong mạng cốt lõi băng rộng trên cơ sở công nghệ
7 gói, còn các phƣơng pháp định tuyến lƣu lƣợng động truyền thống vẫn tiếp
tục đƣợc phát triển trong các mạng chuyển mạch kênh thông thƣờng.
1.3. Kết luận chƣơng
Định tuyến trong mạng viễn thông đã trải quan một quá trình tiến
hóa lâu dài và đa dạng. Với sự phát triển nhanh chóng của công nghệ viễn
thông và máy tính, các phƣơng pháp định tuyến ngày càng trở nên linh
hoạt và gắn liền với hiệu quả của hoạt động mạng lƣới hơn, kế hoạch định
tuyến trở thành một thành phần không thể thiếu đƣợc trong công tác thiết
kế, xây dựng và vận hành,quản lý mạng.
Trong sự phát triển nhƣ vũ bão của khoa học và công nghệ, xu thế
cạnh tranh, hội nhập và toàn cầu hóa, mạng viễn thông, hơn lúc nào hết,
cần đƣợc cải tiến lại về cấu trúc và nghiên cứu trong bị những công nghệ

các bài toán đó.
2.1. TỐI ƢU THEO MÔ HÌNH LƢU LƢỢNG NHIỀU THÀNH
PHẦN (Multicommodity Flow – MF)
Mô hình lƣu lƣợng nhiều thành phần đƣợc sử dụng tƣơng đối rộng
rãi và hiệu quả trong nghiên cứu lý thuyết giao thông vận tải và trong lĩnh
vực chuyển mạch gói viễn thông. Mô hình này cũng thƣờng đƣợc nghiên
cứu áp dụng vào mạng chuyển mạch kênh để xây dựng và giải các bài toán
tối ƣu về định tuyến.
2.1.1. Mô hình lƣu lƣợng nhiều thành phần MF
Theo phân tích của A.Girard, mô hình lƣu lƣợng nhiều thành phần
MF là kết quả thu đƣợc từ việc áp dụng mô hình quá trình liên tục theo
thời gian của Markov vào mạng chuyển mạch kênh, với giả thiết rằng tất
9 cả các đƣờng thông nối giữa các nút mạng là đƣợc cho trƣớc và theo một
thứ tự quy định.
Mô hình lƣu lƣợng nhiều thành phần cho phép chúng ta mô tả một
cách tƣơng đối đầy đủ trạng thái hoạt động của một mạng chuyển mạch
kênh. Việc áp dụng mô hình MF để xây dựng và giải các bài toán định
tuyến tối ƣu cho ta hai tính chất quan trọng: (1) lƣu lƣợng phải đƣợc chọn
một cách tối ƣu sao cho đối với mỗi thành phần thì “giá trị danh giới” của
lƣu lƣợng trên tất cả các đƣờng thông i có mang lƣu lƣợng đó phải bằng
nhau và (2) bài toán có thể đƣợc giải nhờ các thuật toán đặc biệt cho phép
biến đổi về các phép tính toán tìm đƣờng thông ngắn nhất (hoặc chi phí
nhỏ nhất) để áp dụng đƣợc cho các mạng tƣơng đối lớn.
2.1.2. Bài toán tối ƣu phi tuyến theo mô hình lƣu lƣợng MF
Ta nghiên cứu bài toán phi tuyến về các “giá trị” hoặc “chi phí” áp
dụng cho lƣu lƣợng nhiều thành phần đã đƣợc đơn giản hoá ở trên (bỏ chỉ
số trạng thái

x

)(
k
l
u

trong đó:
-
k
x
là nhu cầu đối với thành phần (loại cuộc gọi)
k

-
k
l
x
là véctơ lƣu lƣợng - đƣờng thông,
x
biểu diễn phần lƣu
lƣợng loại k đƣợc chuyển tải trên đƣờng thông
l
.
-
)(xgz 
là hàm giá trị phi tuyến, phụ thuộc vào lƣu lƣợng
x
và
cần phải tối thiểu hoá (hàm mục tiêu)

k
A
là phần lƣu lƣợng xuất phát từ nút
i
tới nút
j
và đi
qua tổng đài Toll
k
. Trong trƣờng hợp thông thƣờng nhất, mục tiêu bài
11 toán tối ƣu là tối thiểu hoá tổng lƣu lƣợng bị rơi trên mạng, với hàm mục
tiêu là:


ij
ijij
ALzmin
(2.4)
ij
L
là xác suất bị mất (tổn hao) của lƣu lƣợng
ij
A

Hay



2.2. ĐỊNH TUYẾN TỐI ƢU THEO LỢI ÍCH
2.2.1. Khái niệm “giá trị kéo theo” (Implied cost)
Theo ý tƣởng do F.P.Kelly đề xuất vào năm 1988, lợi ích thu đƣợc
từ hoạt động của mạng lƣới có thể đƣợc biểu diễn bằng một phép tổng từ
tất cả các lƣu lƣợng đã đƣợc chuyển tải tới đích nhân với “giá trị” của lƣu
lƣợng đó. Giá trị của lƣu lƣợng có thể gán bằng nhiều đại lƣợng khác
nhau, trƣờng hợp đặc biệt khi tất cả các giá trị đó đều bằng 1 thì tổng thu
đƣợc chính là tổng lƣu lƣợng đƣợc chuyển tải trên mạng.
12 Ta ký hiệu
r
là chỉ số đƣờng thông,
k
là chỉ số của các đoạn
tuyến trên đƣờng thông đó,
k
N
là dung lƣợng của đoạn tuyến
k
, các cuộc
gọi tƣơng ứng với doanh thu
r
w
và có phân bố Poisson với tỷ lên
kr
L,



Pconst


là dự báo độ chiếm dụng kện cuối cùng
của đoạn tuyến
k
và có thể tìm đƣợc từ giá trị lƣu lƣợng đƣợc chuyển tải.
2.2.2. Tối ƣu lợi ích trong mô hình định tuyến chia tải
Bài toán chia tải tối ƣu là tìm các phần lƣu lƣợng
k
A
mà ta phải
chia vào mỗi đƣờng thông
k
sao cho tổng doanh thu mang lại từ mạng
lƣới là lớn nhất. Bên cạnh đó, bài toán tính toán các phần lƣu lƣợng
k
A
đã
đƣơc nghiên cứu và giải quyết qua phƣơng trình điểm bất động Erlang. Do
vậy khi đặt ra việc tối ƣu thì bài toán có thể sẽ trở nên tƣơng đối phức tạp.
Để đơn giản hoá, ngƣời ta xây dựng bài toán, trong đó ẩn số không chỉ là
các
k
A
mà còn thêm cả
k
B
, và coi các phƣơng trình điểm bất động
Erlang là các ràng buộc thêm. Điều này tƣơng đƣơng với việc giải quyết

k
u
và
k
v
là các nhân tử Kuhn-Tucker tƣơng ứng với các ràng
buộc chúng sẽ xuất hiện trong đó,
0
k
u
; giả thiết
0
s
N
tức là không
có nhóm trung kế nào có số đƣờng thông bằng 0 cả.
2.2.3. Tối ƣu lợi ích trong mô hình định tuyến thay thế
Phƣơng pháp định tuyến tối ƣu theo mô hình chia tải đƣợc mô tả
tại phần 2 ở trên có ƣu điểm là dễ phân tích và tính toán, tuy nhiên lại
không thích hợp cho việc áp dụng vào thực tế. Thông thƣờng, ngƣời ta sẽ
đạt đƣợc hiệu quả cao hơn nếu cho phép ít nhất một đƣờng thông thứ hai
nữa để chọn lựa khi cuộc gọi bị chặn trên đƣờng thông đầu tiên. Định
tuyến thay thế đã khắc phục đƣợc nhƣợc điểm cơ bản này của định tuyến
theo mô hình chia tải.
2.3. Kết luận chƣơng
Nội dung cốt lõi của bài toán định tuyến tối ƣu theo lợi ích là xây
dựng và giải hàm mục tiêu. Tuy nhiên, nhƣ đã đƣợc chỉ ra, do tính phức
tạp của hàm mục tiêu với các ràng buộc nên về lý thuyết khó có thể di tới
lời giải tối ƣu cuối cùng.
Khi xây dựng bài toán, ngƣời ta vẫn coi các tham số đầu vào của
Chƣơng 3
MỘT SỐ PHƢƠNG PHÁP GIẢI BÀI TOÁN ĐỊNH TUYẾN TỐI ƢU
TRONG MẠNG VIỄN THÔNG
Trong chƣơng 2, chúng ta đã xem xét các mô hình lƣu lƣợng
mạng, cách xây dựng hàm mục tiêu để tối ƣu hoá, cũng nhƣ một số nghiên
cứu lý thuyết về khả năng hội tụ tới điểm tối ƣu của các hàm mục tiêu. Với
cấu trúc nhiều cấp của mạng hiện tại, cộng với việc điều hành mạng chƣa
đƣợc tự động và tập trung hoá thì việc áp dụng các phƣơng pháp định
tuyến thích nghi và tối ƣu trên toàn mạng là chƣa thực hiện ngay đƣợc.
Tuy nhiên với xu thế phát triển của công nghệ và dịch vụ, mạng viễn
thông tất yếu sẽ phải giảm cấp và áp dụng các công nghệ định tuyến hiện
đại. Với mục tiêu trên, chúng ta đi sâu nghiên cứu phƣơng pháp định tuyến
tối ƣu, với việc xây dựng một hàm mục tiêu gắn liền với các tham số lợi
ích cho mô hình mạng phân 2 cấp. Để giải bài toán tối ƣu hoá hàm mục
tiêu phi tuyến này chúng ta lựa chọn sử dụng phƣơng pháp hàm phạt kết
hợp với gradient.
3.1. XÂY DỰNG HÀM MỤC TIÊU THEO MÔ HÌNH MẠNG VÀ
LƢU LƢỢNG TRONG MẠNG VIỄN THÔNG
Hiện nay, trong các công trình nghiên cứu và thực tế các mạng
viễn thông hiện đại trên thế giới, mô hình mạng không phân cấp thƣờng
đƣợc chú trọng do có nhiều ƣu điểm so với mạng phân cấp. Mặt khác
mạng không phân cấp cũng là mô hình mạng trong tƣơng lai. Xuất phát từ
khả năng ứng dụng cũng nhƣ ý nghĩa thực tế của bài toán tối ƣu trong cấu
trúc mạng, chúng ta lựa chọn mô hình mạng phân hai cấp: cấp 1, cấp 2
(Hình 3.1)
16

(3.4)
Đây chính là hàm mục tiêu mà ta cần tối ƣu hoá (tìm hiểu max)
theo các biến
ij
k
a
. Ta xác định các ràng buộc của hàm mục tiêu này.
Quay trở lại nút xuất phát
i
, sau khi đã phân chia lƣu lƣợng tràn
ij
a
để đƣa lên các tổng đài Liên tỉnh
k
. Ta biết rằng đối với mỗi một nút
đi
i
thì có tất cả
1n
nút đến
j
, do vậy lƣu lƣợng đƣa vào đƣờng trung
kế
ki 
để đi lên tổng đài liên tỉnh
k
sẽ là tổng theo
j
của tất cả các







s
s
l
t
lx
ll
ls
s
N
B
BA
EB ,
)1(
)1(
.
,
1

(3.6)
17 Ma trận đƣờng thông
ls,





















j
kjikij
k
ijkj
j
ikkjij
k
ijik
NdBuaaEBd
NuBdaaEBu
































ij
k
ij
k
kj
j
kjij
k
ijkj
ik
j
kjij
k
ijik
i j k
ij
k
kjikij
k
ij
1;,1,1
!
!
),(
0;1
,)1(
,)1(
)1)(1(min
0
1

mục tiêu này khả vi và các đạo hàm
j
X
XF

 )(
với
)1(, ,1  nmnj
hoàn
toàn xác định đƣợc bằng hệ công thức:
)1)(1(
)(
kjikij
k
ij
ij
k
BdBuwa
a
XF




ij
k
kjij
k
n
j

1
)1(
)(

Nhƣ vậy, bài toán (3.8) có dạng tổng quát của bài toán quy hoạch:
0)(
0)(
min)(



XG
XH
XF





(3.10)
)(XH
bao gồm
)1( nn
phƣơng trình dạng
19 



k
r
jj
r
j
ij
k
XGXXX
x
G
0)()).((
)()()(

thực chất vẫn giữ nguyên dạng
0
ij
k
a

Còn trong quá trình xây dựng hàm phạt trong phƣơng pháp hàm
phạt và gradient kết hợp thì đóng góp của ràng buộc
0)( XG
trong
thành phần của Hàm phạt ngoài chỉ đơn giản là:

2
)(
ij
k
a

đƣợc quan tâm nhiều nhất vì những tính ƣu việt nổi trội của nó.
20 Xét bài toán:
min
),(zF
n
Rz






ljzr
mizf
j
i
,10)(
,1,0)(
(3.11)
Trong đó các hàm
ji
rf ,
khả vi, liên tục.
Thuật toán kết hợp hàm phạt và Gradient đƣợc phát biểu nhƣ
sau:
+Bước 0: Chọn
)8.0,5.0();5.0,0(,,;

l
j Ii
ij
zfzrzP
1 '
22
))(())(()('
(3.12)
Hàm phạt trong:



''
)(
1
)(''
Ii
i
zf
zP
(3.13)
+ Bước 4: Nếu
0v
chuyển đến bƣớc 5, nếu khác chuyển tới bƣớc 8
+ Bước 5: Tính gradient
)(''),('),( zPzPzF 

+ Bước 6: Tính
||)(||
||)('||





 )('''')('
'
1
)()( zPzPzFzh


(3.14)
+ Bước 9: Nếu
v
zh

||)(||
chuyển tới bƣớc 10, nếu khác: kiểm tra điều
kiện
*


v
, nếu thoả mãn thì STOP, kết thúc thuật toán,
nếu khác, đặt:














)("")('
1
)()(
||)(||
2
1
)())((
2
zPzPzFzP
zhzPzhzP



(3.15)
+ Bước 12: Nếu
0
đặt
)(zhzz


và chuyển tới bƣớc 8, nếu khác
đặt


3.4. Kết luận chƣơng
Trong chƣơng 3, tiếp nối và dựa trên các kết quả nghiên cứu lý
thuyết về định tuyến tối ƣu. Để phù hợp với quy mô nghiên cứu của đề tài,
mô hình mạng phân hai cấp và các lƣu lƣợng Poisson đã đƣợc chọn lựa.
Từ đó, việc xây dựng hàm mục tiêu và các ràng buộc đƣợc thực hiện dƣới
góc độ tối ƣu theo lợi ích mạng lại, đây là mô hình tối ƣu thích hợp với xu
thế phát triển nhanh chóng, đa dạng của dịch vụ và lƣu lƣợng hiện nay.
Phân tích và giải toán tối ƣu hàm mục tiêu (3.8) là phần phức tạp
và quan trong nhất trong quá trình nghiên cứu. Với dạng hàm mục tiêu phi
tuyến và các ràng buộc tổng quát, phƣơng pháp sử dụng kết hợp hàm phạt
và gradient đƣợc chọn lựa nhƣ là phƣơng pháp tƣơng đối hiệu quả để đạt
đƣợc tốc độ hội tụ nhanh. Các hàm phạt trong
'P
và ngoài
"P
, gradient

…

Thầy giáo - Tiến sĩ Nguyễn Tiến Ban đã giúp đỡ em hoàn thành luận văn
tốt nghiệp cao học này.