1
LỜI NÓI ĐẦU
Một mạng truyền thông cần truyền lưu lượng trên các tuyến truyền dẫn với
băng thông khác nhau. Lưu lượng này có thể được định tuyến qua các đường khác
nhau để đến đích. Bài toán đặt ra là làm thế nào để thiết kế mạng một cách hiệu quả
dựa trên việc xem xét các tính chất của mạng, hay nói cách khác là làm thế nào để
thiết kế mạng một cách tối ưu.
Rất nhiều vấn đề trong thiết kế mạng có thể được giải quyết bằng cách xây
dựng các mô hình toán học và dựa trên các giải thuật tối ưu. Trong luận văn này sẽ
trình bày về một số phương pháp và giải thuật có thể ứng dụng để thiết kế mạng,
sau đó đi sâu vào giải bài toán tối ưu mạng để hỗ trợ cho kĩ thuật định tuyến đường
đi ngắn nhất (shortest-path routing).
Nội dung của luận văn được chia thành 3 chương với các nội dung như sau.
Chương 1 giới thiệu tổng quan về mạng viễn thông và vấn đề tối ưu hóa
mạng, đặt ra bài toán cũng như là giới thiệu những khái niệm mang tính tiền đề và
cơ sở cho các nghiên cứu tiếp theo.
Chương 2 trình bày về những vấn đề kĩ thuật cơ bản trong tối ưu hóa mạng
viễn thông. Với mỗi vấn đề sẽ đưa ra ra mô tả các yêu cầu tối ưu, các bước xây
dựng bài toán và thảo luận về phương pháp giải bài toán.
Chương 3 đi sâu vào giải quyết một số vấn đề cụ thể của bài toán tối ưu mạng
xét từ góc độ kĩ thuật định tuyến đường đi ngắn nhất, xây dựng các phát biểu bài
toán phù hợp và nghiên cứu các phương pháp cũng như giải thuật để giải quyết từng
vấn đề.
Do những lí do hạn chế, bản luận văn không tránh khỏi còn nhiều thiếu sót.
Em rất mong nhận được những ý kiến đóng góp của các thầy cô và các đồng nghiệp
để bản luận văn được hoàn thiện hơn.
Cuối cùng, em xin chân thành cảm ơn thầy giáo, TS. Nguyễn Tiến Ban đã tận
tình hướng dẫn em hoàn thành bản luận văn này.
2
MỤC LỤC
LỜI NÓI ĐẦU 1

Tín hiệu số - n
DVU Demand Volume Unit
Đơn vị khối lượng nhu cầu
DXC Digital Cross-Connect
Systems
Các hệ thống kết nối chéo số
EA Evolutionary Algorithm
Thuật toán tiến hoá
ECMP Equal Cost Multi-Path
Đẳng giá - đa đường
FD Flow Deviation
Độ lệch luồng
Gbps Gigabits per Second
Gigabit trên giây
GoS Grade-of-Service
Cấp độ dịch vụ
GSPAR Generalized Shortest Path
Allocation Rule
Qui tắc cấp xác định đường đi
ngắn nhất tổng quát
IP Internet Protocol
Giao thức Internet
IP Integer Programming
Quy hoạch nguyên
IS-IS Intermediate System-to-
Intermediate System
Giao thức định tuyến IS-IS
ISP Internet Service Provider
Nhà cung cấp dịch vụ Internet
LCU Link Capacity Unit

Bảo về đường
PR Path Restoration
Khôi phục đường
QoS Qualiy-of-Service
Chất lượng dịch vụ
RTNR Real-Time Network Routing
Định tuyến mạng theo thời gian
thực
SDH Synchronous Digital
Hierarchy
Phân cấp số đồng bộ
SONET Synchronous Optical
Network
Mạng quang đồng bộ
SPR Shortest-Path Routing
Định tuyến đường ngắn nhất
TCP Transmission Control
Protocol
Giao thức điều khiển truyền dẫn
5
DANH MỤC HÌNH VẼ
6
TỔNG QUAN VỀ MẠNG VIỄN THÔNG VÀ YÊU CẦU TỐI
ƯU MẠNG
1.1 Đặt vấn đề
Trong điện thoại cũng như Internet, topology hay cấu trúc kết nối các nút
mạng có ảnh hưởng lớn đến hoạt động của mạng. Cấu trúc điển hình của mạng điện
thoại và Internet thể hiện trên Hình 1.1 và Hình 1.2.
Hình 1.1: Cấu trúc mạng điện thoại
Trong khuôn khổ luận văn này chỉ đề cập đến phần giữa là mạng lõi hay còn

phương thức chuyển mạch kênh, trong đó một kênh riêng biệt được thiết lập cho
mỗi cuộc gọi.
Đối với mạng Internet toàn cầu (Hình 1.2), khi có yêu cầu trao đổi thông tin
(ví dụ dịch vụ web) từ người sử dụng này đến người sử dụng khác, thì thông tin sẽ
được truyền đi bởi nhiều nhà cung cấp mạng khác nhau (thông thường thì là các nhà
cung cấp dịch vụ Internet – ISP). Về mặt kỹ thuật thì mạng của mỗi nhà cung cấp
dịch vụ là một hệ thống tự trị riêng (Autonomous System – AS). Tương tự như
trường hợp chuyển tiếp cuộc gọi điện thoại, các nhà cung cấp ở các phân đoạn
mạng khác nhau cũng thực hiện việc truyền lưu lượng dữ liệu để hoàn thành việc
chuyển yêu cầu web qua mạng. Các gói dữ liệu được tạo ra để đáp ứng yêu cầu này
sẽ đi theo một hành trình ngược lại để đến nơi đã gửi đi yêu cầu. Trong cả hai
hướng, hình thức chuyển mạch gói được sử dụng để định tuyến các gói dữ liệu qua
mạng.
Có thể thấy rằng, đối với cả hai trường hợp điện thoại và Internet, một yêu
cầu (cuộc gọi hay giao dịch web) đi qua một loạt các mạng được duy trì bởi những
nhà cung cấp khác nhau. Điều này có thể được minh họa trên Hình 1.3, trong đó
mỗi mạng được mô tả như một đám mây.
Hình 1.3: Kết nối mạng của các nhà cung cấp
9
Các nhà cung cấp cần phải có sự thỏa thuận với nhau để thực hiện việc truyền
tải lưu lượng theo yêu cầu. Sự thỏa thuận giữa các nhà cung cấp láng giềng thường
được xem như là thỏa thuận ngang hàng. Mỗi mạng có một số thiết bị định tuyến
hay chuyển mạch của riêng mình, và các thiết bị tại biên mạng hay cổng giao tiếp
(gateway) sẽ thực hiện nhiệm vụ truyền dữ liệu từ mạng này sang mạng khác. Như
vậy, mỗi mạng sẽ tự phải biết làm thế nào để truyền dữ liệu bên trong mạng cũng
như cần sử dụng bao nhiêu thiết bị định tuyến hay chuyển mạch để hoàn thành công
việc này. Từ thực tế này thấy rằng vấn đề thiết kế mạng có thể được hạn chế bởi
phạm vi bên trong mỗi mạng, hay miền quản trị (administrative domain) của nó như
chỉ ra trên Hình 1.4.
Hình 1.4: Miền quản trị mạng (đối tượng của bài toán thiết kế mạng)

11
Hình 1.5: Nhiều miền quản trị khác nhau cùng sử dụng một nhà cung cấp mạng
truyền tải
Như vậy, có thể thấy rằng nhà cung cấp mạng truyền tải có miền riêng để đón
nhận các yêu cầu lưu lượng qua thiết bị nút hay các liên kết truyền tải. Một lưu ý
quan trọng ở đây là nhiều nhà cung cấp dịch vụ Internet (ISP) khác nhau có thể
cùng sử dụng một nhà cung cấp mạng truyền tải như trên Hình 1.5, hay ngược lại,
một ISP có thể sử dụng nhiều nhà cung cấp mạng truyền tải như chỉ ra trên Hình
1.6.
Hình 1.6: Một miền quản trị sử dụng nhiều nhà cung cấp mạng truyền tải
12
Ngoài ra, nhà cung cấp mạng truyền tải có thể đáp ứng nhiều yêu cầu khác
nhau của khách hàng như mạng Internet, mạng điện thoại, hay mạng khách hàng
kênh thuê riêng như chỉ ra trên Hình 1.7.
Hình 1.7: Nhiều mạng dịch vụ trên cùng một mạng truyền tải
Bài toán thiết kế mạng là trách nhiệm của nhà cung cấp, dù đó là nhà cung
cấp dịch vụ Internet, nhà cung cấp dịch vụ điện thoại, nhà cung cấp mạng kênh thuê
riêng, hay nhà cung cấp mạng truyền tải. Để đơn giản, chúng ta sẽ sử dụng một
thuật ngữ chung là nhà cung cấp mạng thay cho tất cả các nhà cung cấp nói trên.
Sự tổ hợp của rất nhiều loại mạng khác nhau dẫn đến một môi trường mạng
đa lớp mà ở đó mỗi lớp có các định nghĩa riêng của nó về lưu lượng, dung lượng
liên kết và các chức năng thực hiện của thiết bị ở nút mạng. Trong phần tiếp theo
chúng ta sẽ đề cập chi tiết hơn về những khía cạnh này.
1.3 Khái niệm về lưu lượng và nhu cầu lưu lượng
Một nhà cung cấp mạng phải kiểm soát được việc thiết kế và quản lý mạng
trong miền quản trị của mình, và để làm được điều đó, vấn đề quan trọng đối với
mỗi nhà cung cấp là phải xác định được nhu cầu lưu lượng trong mạng. Xem xét tất
cả các nút trong mạng, chúng ta phải xác định được khối lượng lưu lượng giữa hai
nút bất kì hình thành nên ma trận lưu lượng. Ở đây sẽ sử dụng các thuật ngữ rút gọn
13

quan tâm đến việc bộ đệm tại bộ định tuyến mà nó chuyển gói tin đến có còn chỗ
trống hay không. Điều này có thể chấp nhận được vì quy tắc của giao thức cho phép
các máy tính kết cuối phát lại bất cứ gói dữ liệu nào bị mất. Khi giao thức cho phép
tốc độ điều chỉnh được để ứng phó với tắc nghẽn, bất kỳ gói dữ liệu đang chuyển
tiếp nào cũng có thể bị loại bỏ.
Việc tắc nghẽn lưu lượng có thể xảy ra trong một mạng (hoặc trong các phần
của mạng), vấn đề trễ có thể xảy ra, và các gói dữ liệu cũng có thể bị loại bỏ. Vì
vậy, công việc của người thiết kế mạng là phải thiết kế một mạng sao cho giữ được
độ trễ ở mức độ nhỏ nhất có thể chấp nhận, và đảm bảo việc mất gói dữ liệu ở các
bộ định tuyến là tối thiểu. Trong thực tế thì việc tắc nghẽn là không tránh khỏi vì
lưu lượng có thể không dự báo trước được. Tuy nhiên, có thể thiết kế một mạng sao
cho việc tắc nghẽn xảy ra không thường xuyên. Các đường truyền trên mạng cần
phải có đủ băng thông để hạn chế tắc nghẽn và giảm thiểu thời gian trễ. Ngoài ra,
các bộ định tuyến cần có bộ đệm đủ lớn để đối phó với sự bùng nổ lưu lượng, đặc
biệt là lưu lượng thời gian thực nhằm tối thiểu hóa số lượng các gói tin bị mất.
Nhìn tổng thể thì vấn đề trở nên phức tạp hơn. Để minh họa điều này cần xem
xét các khái niệm lưu lượng và nhu cầu lưu lượng. Trước tiên, ta không biết trước
được khi nào thì một người sử dụng sẽ gửi đi một yêu cầu sử dụng trang web từ một
địa chỉ nào đó hay một bức thư điện tử (email). Tiếp theo, từ quan điểm mạng, ta
phải chấp nhận một thực tế là các yêu cầu hay nhu cầu lưu lượng đến một cách hoàn
toàn ngẫu nhiên, và khi số lượng người sử dụng càng lớn thì tính ngẫu nhiên càng
trở nên phức tạp. Vì vậy, cách tiếp cận hợp lí ở đây là sử dụng các phương pháp
thống kê và xem xét các tính chất ngẫu nhiên trên mạng thông qua các mô hình
phân bố thống kê.
15
1.3.2 Lưu lượng trong mạng điện thoại
Tương tự như Internet, mạng điện thoại cũng phải đối diện với vấn đề những
đối tượng đến ngẫu nhiên. Trong trường hợp này thì đối tượng khảo sát là cuộc gọi.
Rõ ràng ta không thể biết khi nào một người sử dụng muốn thực hiện một cuộc gọi
và gọi đi đâu. Tương tự như việc khảo sát tốc độ đến trung bình của các gói tin

cầu truyền tải nhiều loại hình lưu lượng khác nhau. Vì vậy, cần phải phân biệt một
cách rõ ràng hai khái niệm mạng lưu lượng và mạng truyền tải.
Mạng lưu lượng (traffic network) là mạng mà trong đó nhu cầu lưu lượng
mang tính chất ngẫu nhiên không phụ thuộc vào tốc độ dữ liệu của dịch vụ (truyền
gói, thoại 64 Kb/s, …) và có khả năng chuyển mạch/định tuyến để xử lý các yêu cầu
phục vụ trong thời gian ngắn.
Mạng truyền tải (transport network) cung cấp các dịch vụ tốc độ dữ liệu cao
trên cơ sở thiết lập các đường truyền cố định hay bán cố định, và thường là theo chu
kỳ có thời hạn dài.
1.3.4 Đơn vị đo dung lượng và nhu cầu lưu lượng
Sau khi xem xét những khái niệm lưu lượng và nhu cầu lưu lượng trong các
mạng khác nhau, phần này giới thiệu về những khái niệm liên quan đến đơn vị đo
dung lượng và nhu cầu lưu lượng. Hai thuật ngữ được sử dụng ở đây là: đơn vị khối
lượng nhu cầu (DVU – Demand Volume Unit) và đơn vị dung lượng liên kết
(LCU – Link Capacity Unit). Ví dụ, DVU có thể được tính theo pps, Erl, hoặc tốc
độ dữ liệu điều chế tùy thuộc vào mạng thiết kế. LCU là đơn vị dung lượng của liên
kết, có dạng khác nhau phụ thuộc vào lớp của mạng truyền tải. Ví dụ, nó có thể là
E1 hay STM-1, … phụ thuộc vào lớp mạng mà chúng ta thiết kế và giá trị dung
lượng liên kết có thể áp dụng được.
Bây giờ, nếu xem xét bản chất phân cấp nguồn tài nguyên giữa các mạng lưu
lượng và truyền tải, chúng ta có thể thấy rằng nhu cầu lưu lượng tính theo DVU
17
được chuyển thành LCU thông qua việc thiết kế mạng lưu lượng, hay ngược lại,
LCU chuyển thành DVU trong trường hợp mạng truyền tải.
Ưu điểm của việc sử dụng các thuật ngữ mang tính tổng quát nói trên là trong
nhiều trường hợp ta sẽ thấy việc biểu diễn toán học các mô hình thiết kế là hoàn
toàn tương tự như nhau từ một kiểu mạng này sang kiểu mạng khác. Điểm khác ở
đây chỉ là dùng đơn vị nào (DVU hay LCU) cho phù hợp.
1.4 Khái niệm về định tuyến và luồng
Khi có lưu lượng từ một điểm này đến một điểm khác trong mạng, chúng ta

Ở trên đã xem xét các khái niệm về lưu lượng/nhu cầu và phân biệt chúng
khác nhau như thế nào đối với các mạng lưu lượng và truyền tải. Ngoài ra, chúng ta
cũng đã rõ vấn đề định tuyến có thể ảnh hưởng tới bài toán thiết kế mạng như thế
nào. Với quan điểm rằng các mạng lưu lượng và truyền tải là khác nhau với những
tính chất khác nhau, trong phần này sẽ đề cập đến khía cạnh kiến trúc mạng và mối
quan hệ phức tạp giữa các phần tử khác nhau trong mạng dưới góc độ phân lớp.
Kiến trúc của các mạng truyền thông có thể khá phức tạp, điều này không chỉ
là do số lượng lớn các nút hình thành nên mạng, mà còn do quan điểm phân biệt
mạng lưu lượng và mạng truyền tải đã giới thiệu ở trên. Có thể nói một cách đơn
giản rằng một mạng (hay lớp) này chạy trên một mạng (hay lớp) khác. Mạng lưu
lượng cần có một mạng truyền tải để kết nối các liên kết cần thiết cho mạng lưu
lượng. Tiếp đến, trong mạng truyền tải cũng có thể có nhiều lớp ứng với các tốc độ
dữ liệu khác nhau. Trên quan điểm dịch vụ, người sử dụng mạng lưu lượng không
nhìn thấy sự phụ thuộc vào mạng truyền tải.
Kiến trúc mạng đa lớp và mối liên quan giữa các lớp có thể được minh họa
thông qua một ví dụ đơn giản như sau. Xét một môi trường mạng IP có 4 nút ở bên
19
trong một miền quản trị. Với mạng này, chúng ta có 4 bộ định tuyến được kết nối
như trên Hình 1.8 (phần trên).
Hình 1.8: Mạng lưu lượng và mạng truyền tải
Các liên kết (hay trung kế) có khả năng truyền lưu lượng với nhiều loại dung
lượng liên kết khác nhau như là E1, STM-1, … Chú ý rằng các liên kết trong mạng
lưu lượng (trong trường hợp này là mạng IP) hoàn toàn chỉ mang tính logic.
Bây giờ chúng ta cần sự trợ giúp của một mạng truyền tải để định tuyến các
liên kết logic này (Hình 1.8, phần dưới). Ví dụ, đơn vị dung lượng liên kết f của liên
kết logic giữa nút 1 và nút 3 trong mạng IP được kết nối bằng cách sử dụng tuyến 1-
20
2-3 của mạng truyền tải. Tương tự, đơn vị nhu cầu đối với liên kết logic 1-4, giữa
nút 1 và nút 4 trong mạng lưu lượng, được kết nối qua tuyến truyền tải 1-2-3-4.
Ánh xạ giữa các lớp trong kiến trúc mạng đa lớp này, có thể rút ra một số

22
CÁC VẤN ĐỀ KĨ THUẬT TRONG TỐI ƯU HÓA MẠNG
1.7 Bài toán luồng trên mạng
1.7.1 Mô tả vấn đề
Chúng ta có thể minh họa bài toán luồng với một ví dụ mạng đơn giản gồm 3
nút, mỗi nút được kết nối tới 2 nút khác, cấu hình mạng như trên Hình 2.1.
Hình 2.1: Ví dụ mạng 3 nút
Các nút có thể là các bộ định tuyến trong mạng Internet, các chuyển mạch
trong mạng điện thoại, hoặc các kết nối chéo trong mạng SONET/SDH. Nút (node)
là một thuật ngữ chung để chỉ định các loại thiết bị định tuyến hay chuyển mạch
khác nhau trong mạng. Thuật ngữ khối lượng nhu cầu (demand volume) được dùng
một cách tổng quát để thay cho khối lượng lưu lượng (trong Internet hay mạng điện
thoại) hoặc băng thông yêu cầu (trong mạng SONET/SDH) giữa hai nút, phụ thuộc
vào mạng xem xét. Một cặp hai nút được gọi là cặp nhu cầu (demand pair) hay đơn
giản là nhu cầu (demand).
Giả sử khối lượng nhu cầu giữa nút 1 và nút 2 là 5 đơn vị, giữa nút 1 và nút 3
là 7 đơn vị, giữa nút 2 và nút 3 là 8 đơn vị. Lưu ý rằng nhu cầu được giả thiết ở đây
là theo cả hai hướng (bi-directional) hay vô hướng (undirected), hàm ý là “giữa hai
nút” chứ không phải “từ nút này đến nút kia”. Với ví dụ đơn giản này chúng ta cũng
giả thiết rằng các liên kết là vô hướng. Nhìn chung nhu cầu và liên kết có thể là có
hướng (directed) hay còn gọi là đơn hướng (undirected).
23
Chúng ta sẽ sử dụng kí hiệu
h
ˆ
để chỉ định khối lượng nhu cầu. Khi đó có thể
viết
5
ˆ
12

2,1
ta có thể viết
)(5
ˆˆ
1213212
hxx ==+
.
24
Với các cặp nhu cầu khác ta có thể nhận được các phương trình tương tự.
Những phương trình dạng này được gọi là ràng buộc về nhu cầu (demand
constraints). Một lưu ý ở đây là các giá trị luồng luôn không âm, nghĩa là
0
ˆ
≥
x
với
mọi đường.
Vấn đề tiếp theo cần xem xét là dung lượng liên kết, đôi khi còn gọi là băng
thông của liên kết. Để phân biệt giữa nhu cầu và liên kết, chúng ta sẽ chỉ thị các liên
kết là 1-2, 1-3 và 2-3, còn dung lượng của chúng tương ứng là
12
ˆ
c
,
13
ˆ
c
và
23
ˆ

) và
213
ˆ
x
(cặp nhu cầu
〉〈
3,2
) cùng sử dụng liên kết 1-2 với
dung lượng
12
ˆ
c
, tính theo pps. Một yêu cầu chung trong mạng truyền thông cũng
như mạng máy tính là tải trên liên kết không thể lớn hơn dung lượng liên kết. Vì
vậy, ta có bất đẳng thức sau đối với liên kết 1-2:
12
ˆ
x
+
123
ˆ
x
+
213
ˆ
x
≤
12
ˆ
c

nhu cầu 2
cặp nhu cầu
〉〈
3,2

↔
nhu cầu 3
Ta sẽ sử dụng ký hiệu
D
để chỉ tổng số cặp nhu cầu trong mạng có khối
lượng nhu cầu là giá trị dương, và chỉ số
d
để đánh số cho các nhu cầu đó (trong ví
dụ trên
D
= 3 và
d
= 1, 2, 3). Tương tự, các liên kết có trong mạng cũng được đánh
số từ 1 đến giá trị tổng số liên kết. Cũng giống như với các cặp nhu cầu, nếu liên
kết trực tiếp giữa hai nút nào đó không có thì sẽ không được liệt kê. Đối với ví dụ
trên, ta có:
liên kết 1-2
↔
liên kết 1
liên kết 1-3
↔
liên kết 2
liên kết 2-3
↔
liên kết 3