Tối ưu mạng internet sử dụng thuật toán p proximal convexification

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 (1.41 MB, 125 trang )

ĐẠI HỌC QUỐC GIA TP HỒ CHÍ MINH
TRƯỜNG ĐẠI HỌC BÁCH KHOA TP. HCM

KHOA ĐIỆN – ĐIỆN TỬ

LUẬN VĂN TỐT NGHIỆP THẠC SỸ
ĐỀÂ TÀI :

TỐI ƯU MẠNG INTERNET SỬ DỤNG
THUẬT TỐN r PROXIMAL
CONVEXIFICATION
HVTH

: NGUYỄN ĐỨC QUANG

MSHV

: 01406325

CBHD

: TS. LƯU THANH TRÀ

BỘ MÔN : VIỄN THÔNG

TP. HCM , 7/2008

ĐẠI HỌC QUỐC GIA TP.HCM
TRƯỜNG ĐẠI HỌC BÁCH KHOA

CỘNG HOÀ XÃ HỘI CHỦ NGHĨA VIỆT NAM
Độc lập – Tự do – Hạnh phúc

NHẬN XÉT LUẬN VĂN THẠC SĨ
(Nhận xét của CB hướng dẫn

Nhận xét của CB phản biện

)

Họ và tên học viên: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Đề tài luận văn: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
.......................................................................
Chuyên ngành: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Người nhận xét (họ tên, học hàm , học vị : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Cơ quan cơng tác (nếu có): . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Ý KIẾN NHẬN XÉT
1- Về nội dung & đánh giá thực hiện nhiệm vụ nghiên cứu của đề tài:
.........................................................................
.........................................................................
.........................................................................
.........................................................................
.........................................................................
.........................................................................
.........................................................................
.........................................................................
.........................................................................
.........................................................................
.........................................................................

.........................................................................
...........................................................................
.......................................................................
2- Về phương pháp nghiên cứu, độ tin cậy của các số liệu:
...........................................................................
...........................................................................
...........................................................................
...................................................................
3- Về kết quả khoa học của luận văn:
...........................................................................
...........................................................................
...........................................................................
...................................................................

4- Về kết quả thực tiễn của luận văn:
.........................................................................
...........................................................................
...........................................................................
.....................................................................
5- Những thiếu sót & vấn đề cần làm rõ (nếu có):
...........................................................................
.......................................................................
...........................................................................
...........................................................................
...........................................................................
...................................................................
6. Ý kiến kết luận (mức độ đáp ứng yêu cầu đối với LVThS; cho điểm đánh giá LV):
...........................................................................
...........................................................................

Nơi sinh : . . . . . . . . . . . . . . . . . . . .

Chuyên ngành : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Khoá (Năm trúng tuyển) : . . . . . . . . . . .
1- TÊN ĐỀ TÀI: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2- NHIỆM VỤ LUẬN VĂN: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
..........................................................................
..........................................................................
..........................................................................
..........................................................................
..........................................................................
..........................................................................
..........................................................................
..........................................................................
..........................................................................
..........................................................................
..........................................................................
.....................................................................
3- NGÀY GIAO NHIỆM VỤ : . . . . . . . . . . . . . . . . . . . . .
4- NGÀY HOÀN THÀNH NHIỆM VỤ : . . . . . . . . . . . . . . . . . . . . .
5- HỌ VÀ TÊN CÁN BỘ HƯỚNG DẪN (Ghi đầy đủ học hàm, học vị ): . . . . . . . . . . . . . . . . .
.......................................................................
Nội dung và đề cương Luận văn thạc sĩ đã được Hội Đồng Chuyên Ngành thông qua.
CÁN BỘ HƯỚNG DẪN
(Họ tên và chữ ký)

CHỦ NHIỆM BỘ MÔN

QUẢN LÝ CHUYÊN NGÀNH
(Họ tên và chữ ký)

LỜI CẢM ƠN
Trước tiên, em xin chân thành cảm ơn Thầy Lưu
Thanh Trà, Thầy đã tận tình hướng dẫn em hoàn
thành Luận văn cao học này. Thầy đã dành sự giúp đỡ
nhiệt tình cũng như động viên, khích lệ cho em trong
suốt thời gian và hoàn thành đề tài.
Em xin bày tỏ lịng biết ơn chân thành đến q
Thầy/Cơ trong bộ mơn Viễn thơng đã dành thời gian
q báu để nhận xét và chấm Luận văn của em. Em
cũng xin chân thành cảm ơn tất cả q Thầy/Cơ trong
Khoa Điện – Điện Tử, Trường Đại Học Bách Khoa
Thành Phố Hồ Chí Minh đã trang bị cho em những
kiến thức cơ sở nền tảng cũng như đã giúp đỡ em
vượt qua những khó khăn trong suốt thời gian học tập
tại trường .
Em sẽ mãi mãi ghi nhớ sự đóng góp tích cực về
vật chất, sự ủng hộ động viên tinh thần từ phía gia
đình. Điều đó đã hình thành một chỗ dựa vững chắc
cho em trong những lúc khó khăn nhất.
Sau cùng là lời cảm ơn chân thành đến tất cả các
bạn cùng với sự giúp đỡ, những lời động viên đúng
lúc của các bạn trong khi học và trong thời gian thực
hiện đề tài .
HVTH: Nguyễn Đức Quang

MỤC LỤC

CHƯƠNG 1: GIỚI THIỆU ĐỀ TÀI.................................................................. 1
1.1 GIỚI THIỆU ................................................................................................ 1
1.2 HƯỚNG ĐỀ CẬP CỦA LUẬN VĂN......................................................... 3
CHƯƠNG 2: LÝ THUYẾT TỐI ƯU HOÁ CHO BÀI TOÁN ĐIỀU KHIỂN
LƯU LƯỢNG MẠNG INTERNET................................................................... 6
2.1 KHÁI NIỆM VỀ TOÁN TỐI ƯU ............................................................... 6
2.2 CÁC PHƯƠNG PHÁP GIẢI BÀI TOÁN TỐI ƯU...................................... 8
2.3 QUY HOẠCH LỒI –BÀI TOÁN VÀ CÁC KHÁI NIỆM CƠ BẢN: ........... 9
2.3.1 Định nghĩa quy hoạch toán học:.............................................................. 9
2.3.2 Định nghĩa quy hoạch lồi: ...................................................................... 10
2.4 TỐI ƯU KHÔNG RÀNG BUỘC – BÀI TOẤN VÀ KHÁI NIỆM............... 11
2.4.1 Định nghĩa ............................................................................................. 11
2.4.2 Phân loại các thuật toán tối ưu ................................................................ 12
2.4.3 Định nghĩa (hướng làm giảm hàm mục tiêu)........................................... 13
2.4.4 Định nghĩa tập ứng cử viên..................................................................... 14
2.4.5 Tối ưu không ràng buộc - Xuống đồi theo hướng đạo hàm (gradient descent)
........................................................................................................................ 15
2.5 PHƯƠNG PHÁP NHÂN TỬ LAGRANGE................................................ 18
2.6 BÀI TOÁN TỐI ƯU LỒI DÙNG PHƯƠNG PHÁP ĐỐI NGẪU ................ 19
CHƯƠNG 3: TỔNG QUAN VỀ MẠNG .......................................................... 21
3.1 GIỚI THIỆU MƠ HÌNH THAM CHIẾU OSI ............................................. 21
3.2 CÁC LỚP CỦA MƠ HÌNH OSI: ................................................................. 21
3.3 GIỚI THIỆU HỌ GIAO THỨC TCP/IP: ..................................................... 22
3.4 GIỚI THIỆU VỀ TCP:................................................................................. 24
3.4.1 Giới thiêu giao thức TCP:....................................................................... 24
3.4.2 Cơ chế điều khiển tắc nghẽn của TCP:.................................................... 25
3.5 PHIÊN BẢN TCP TAHOE VÀ RENO:....................................................... 27

i

3.5.1 Trạng thái bắt đầu chậm : ....................................................................... 27
3.5.2 Trạng thái tránh nghẽn: .......................................................................... 27
3.5.3 Trạng thái truyền lại nhanh:.................................................................... 28
3.6 PHIÊN BẢN TCP VEGAS: ......................................................................... 30
3.7 MƠ HÌNH TỐC ĐỘ CỦA TCP: .................................................................. 32
3.7.1 Mơ hình cấp độ gói tin đơn giản cho trạng thái ổn định của thông lượng TCP
........................................................................................................................ 33
3.7.2 Mơ hình mức độ gói tin phức tạp cho thông lượng TCP trạng thái ổn định
........................................................................................................................ 35
3.8 CÁC YẾU TỐ ẢNH HƯỞNG ĐẾN THUẬT TOÁN ĐIỀU KHIỂN NGHẼN
CỦA TCP .......................................................................................................... 35
3.9 ĐIỀU KHIỂN NGHẼN DÙNG PHƯƠNG PHÁP PHẢN HỒI 1 BIT: ......... 36
3.10 KHÁI NIỆM HÀM ỨNG DỤNG MẠNG:................................................. 37

3.10.1 Định nghĩa hàm ứng dụng: ........................................................... 37
3.10.2 Phân loại các loại traffic và hàm ứng dụng:.................................. 38
3.11 CÁC CƠ CHẾ PHÂN CHIA BĂNG THÔNG: .......................................... 41
3.12 BÀI TOÁN TỐI ƯU LƯU LƯỢNG MẠNG INTERNET:........................ 43
3.12.1Giới thiệu bài toán tối ưu lưu lượng mạng internet: ............................... 43
3.12.2 Ứng dụng lý thuyết toán tối ưu trong bài toán lưu lượng internet:......... 43
CHƯƠNG 4: XÂY DỰNG GIẢI THUẬT CHO BÀI TOÁN TỐI ƯU MẠNG
............................................................................................................................. 49
4.1 CẤU TRÚC MẠNG: ................................................................................... 49
4.2 CÁC THUẬT TỐN TỐI ƯU MẠNG:....................................................... 49
4.2.1 Thuật tốn của Stenve H Low và Lapsley (thuật toán 1): ....................... 49
4.2.2 Giải thuật proximal convexification (thuật toán 2):................................. 57
4.2.3 Giải thuật

r

proximal convexification (thuật toán 3): ......................... 61

4.2.4 Cải tiến giải thuật

r

proximal convexification: .................................. 66

4.3 KHÁI QUÁT HƯỚNG NGHIÊN CỨU VỀ CƠ CHẾ ĐIỀU KHIỂN NGHẼN
DÙNG CHI PHÍ ĐƯỢC ĐỀ NGHỊ TRÊN THẾ GIỚI:...................................... 70
4.3.1 Các cơ chế điều khiển lưu lượng dựa vào chi phí tĩnh (static prices):...... 70
4.3.2 Định chi phí động dựa vào q trình dị tìm: ........................................... 71

ii

CHƯƠNG 5: KẾT QUẢ MÔ PHỎNG VÀ HƯỚNG NGHIÊN CỨU ............. 74
5.1 CẤU TRÚC MẠNG DÙNG TRONG MÔ PHỎNG: ................................... 74
5.2 MƠ PHỎNG Q TRÌNH TRUYỀN FILE (FTP) DÙNG THUẬT TỐN
TCP: .................................................................................................................. 74
5.2.1 Mơ phỏng dùng thuật tốn TCP Tahoe: .................................................. 75
5.2.2 Mơ phỏng dùng thuật tốn TCP Reno:.................................................... 78
5.2.3 Mơ phỏng dùng thuật tốn TCP Vegas: .................................................. 81
5.3 MƠ PHỎNG CÁC GIẢI THUẬT TỐI ƯU:................................................. 84
5.3.1 Các thông số cài đặt cho các thuật toán:.................................................. 84
5.3.2 Thuật toán của Low và Lapsley (thuật tốn 1): ....................................... 96
5.3.3 Mơ phỏng thuật tốn convexified projection (thuật tốn 2) :................... 93

5.3.4 Mơ phỏng thuật toán r priximal convexification (thuật toán 3): .......... 98
5.3.5 So sánh giữa các thuật toán:.................................................................... 105
5.4 CẢI TIẾN THUẬT TOÁN

r

PROXIMAL CONVEXIFICATION:.......... 154

5.4.1 Giới thiệu: .............................................................................................. 106
5.4.2 Một số kết quả mô phỏng: ...................................................................... 107
5.4.3 Khảo sát thống kê kết quả mô phỏng: ..................................................... 109
5.5 NHẬN XÉT CÁC THUẬT TOÁN: ............................................................. 111
5.6 KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN: ................................................... 112

iii

TÓM TẮT LUẬN VĂN
Luận văn được chia làm 5 chương :
Chương 1 : Giới thiệu đề tài :
Giới thiệu các phương pháp điều khiển nghẽn của thuật toán TCP và hướng đề cập
đến thuật toán tối ưu điều khiển nghẽn dựa vào chi phí được sử dụng trong luận văn.
Chương 2 : Lý thuyết toán tối ưu cho bài toán điều khiển lưu lượng mạng
internet
Ø Giới thiệu về toán tối ưu và các lý thuyết cơ bản.
Ø Các phương pháp giải bài tốn tối ưu.
Ø Mơ phỏng bài tốn điều khiển mạng như một bài toán tối ưu và ứng dụng
.phương pháp đối ngẫu để giải bài toán lưu lượng mạng internet.
Chương 3: Tổng quan về mạng
Ø Tìm hiểu và khái quát về mạng TCP/IP

Ø Tìm hiểu các phương pháp điều khiển nghẽn của TCP và các phiên bản của TCP
Ø Nghiên cứu các mơ hình tốn của TCP và thuật toán điều khiển nghẽn của TCP
và các phương pháp khác.
Ø Tìm hiểu về hàm ứng dụng mạng và các cơ chế phân loại lưu lượng dựa vào hàm
ứng dụng mạng.
Ø .Mơ phỏng bài tốn tối ưu mạng và sử dụng toán tối ưu để điều khiển
Chương 4: Xây dựng giải thuật cho bài tốn tối ưu mạng
Ø Tìm hiểu các thuật toán và cơ sở lý thuyết cho các giải thuật đề nghị đồng thời
đưa ra hướng cải tiến thuật toán đã được đề nghị
Ø Khái quát hướng nghiên cứu điều khiển nghẽn dựa vào chi phí trên trên giới
Chương 5 : Kết quả mô phỏng và hướng nghiên cứu
Ø Mô phỏng và nhận xét các phiên bản của thuật tốn TCP
Ø Mơ phỏng và nhận xét các thuật toán đề nghị và so sánh giữa các thuật toán
Ø Mơ phỏng và nhận xét thuật tốn cải tiến của thuật toán r
convexification
iv

priximal

Ø Nhận xét chung và đưa ra hướng nghiên cứu và phát triển của đề tài
Với kiến thức còn hạn hẹp, đề tài chắc chắn cịn nhiều thiếu xót vì thế rất mong
nhận đựơc sự thơng cảm và sự góp ý từ phía q Thầy Cơ và bạn bè để có thể phát triển
và hồn thiện đề tài
Học viên thực hiện
Nguyễn Đức Quang

v

Chương 1: Giới thiệu đề tài

CHƯƠNG 1: GIỚI THIỆU ĐỀ TÀI
1.1 GIỚI THIỆU:
Ngày nay, cùng với sự bùng nổ của internet thì nhu cầu truyền dữ liệu tin cậy
cũng rất được quan tâm. Q trình chia sẻ dữ liệu địi hỏi phải nhanh, đầy đủ và
chính xác nên hầu hết các ứng dụng truyền dữ liệu trên internet đều sử dụng nghi
thức TCP như là phương tiện để đảm bảo thực hiện được các yêu cầu trên. TCP là
nghi thức truyền dữ liệu tin cậy nghĩa là khi có mất mát dữ liệu trong quá trình
truyền, dữ liệu sẽ được truyền lại. TCP với cơ chể quản lý nghẽn dựa vào cửa sổ
tuy rất phổ biến nhưng lại không hướng đến việc phân bổ băng thông một cách hiệu
quả giữa các kết nối. Cơ chế quản lý nghẽn bằng cửa sổ nghẽn và cơ chế cập nhật
cửa sổ TCP sẽ dẫn tới việc sử dụng không hiệu quả băng thông đối với các kết nối
tốc độ cao.

Hình 1.1 Mơ phỏng thuật toán TCP
Mặt khác, TCP điều chỉnh tốc độ của các nguồn dựa vào thơng tin các gói tin
bị mất bằng cách điều chỉnh cửa sổ nghẽn mà không cần biết nhu cầu sử dụng băng
thông khác nhau của từng user (hay các nguồn phát). Ta giả sử có 2 nguồn và sử
dụng 2 ứng dụng khác nhau. Nguồn 1 sử dụng ứng dụng truyền file FTP và nguồn
1

Chương 1: Giới thiệu đề tài

thứ hai đang sử dụng ứng dụng thoại. Rõ ràng hai ứng dụng này có nhu cầu sử
dụng băng thông khác nhau. Với FTP, tốc độ càng cao thì hiệu quả càng cao, cịn
với thoại, nếu băng thơng lớn hơn 64kbs thì dù có tăng băng thông đi nữa cũng
không thấy sự hiệu quả. Nếu TCP vẫn chỉ dựa vào cơ chế cửa sổ để điều khiển các
nguồn này sẽ dẫn đến phân bổ băng thơng khơng hợp lí và hiệu quả như ví dụ trên.

Do đó, để cải thiện độ tin cậy của TCP, nhiều phiên bản ra đời sau của TCP đã
cải thiện cơ chế cập nhật cửa sổ một cách hợp lí hơn, tuy nhiên các giao thức này
vẫn không quan tâm đến user đầu cuối đang sử dụng các ứng dụng có nhu cầu
băng thơng khác nhau.
Vì vậy ý tưởng trong việc điều khiển luồng trên internet thay vì dựa vào cơ
chế cửa sổ của TCP mà dựa vào các dịch vụ hay các ứng dụng mà các user đầu cuối
đang sử dụng đã ra đời để cho việc sử dụng băng thông một cách hiệu quả hơn.
Kelly và Stenven H. Low là những người tiên phong cho ý tưởng này. Đó là một cơ
chế quản lý luồng khơng dựa vào các cửa sổ nghẽn mà dựa vào các dịch vụ (ứng
dụng) tại các user đầu cuối. Sự hoạt động của các tài nguyên mạng tại các liên kết
(là các router) sẽ được cung cấp cho các user đầu cuối và bản thân các user đầu
cuối phải quyết định yêu cầu về băng thông như thế nào là tốt nhất cho mình dựa
theo các giới hạn về các tài nguyên mạng. Họ cho rằng các user đầu cuối có thể
quyết định băng thơng cho mình một cách hiệu quả bằng những thông tin về nghẽn
từ mạng gửi cho các user hơn là các user phải gửi thông tin cho mạng và để cho
mạng quyết định băng thông cho các user.
Một biến điều khiển quan trọng trong cơ chế này là chi phí. Trong kinh tế, chi
phí là cơng cụ để điều khiển cung cầu trên thị trường cho một lượng hàng hóa nhất
định. Cơ chế điều khiển luồng dựa vào chi phí có thể được mơ tả như q trình xử
lý thị trường với mục tiêu là một sự phân bố cân bằng mà tại đó nhu cầu hàng hóa
bằng với số lượng cung cố định (dạng của giới hạn đường truyền).
2

Chương 1: Giới thiệu đề tài

Lấy ví dụ, ta có thể mơ tả cơ chế TCP theo một mơ hình mới. Trong TCP,
nguồn nhận những thông tin phản hồi về trạng thái nghẽn của mạng chủ yếu thơng
qua các gói tin bị mất. Khi định nghĩa xác suất gói tin bị mất trung bình trên đường
đi của nguồn như một chi phí kết nối, thì đặc tính của nguồn có thể được mô tả như

một hàm thể hiện mức nhu cầu như trong mơ hình kinh tế. Chi phí càng cao thì nhu
cầu (hay băng thơng ) của nguồn càng thấp xuống. Khi một nguồn mới muốn sử
dụng mạng, việc tăng nhu cầu băng thơng của tồn bơ mạng sẽ dẫn đến xácb suất
mất gói tin cao dẫn đến chi phí cao. Những nguồn khác sẽ phải truyền với một tốc
độ nhỏ hơn và một trạng thái cân bằng mới được thiết lập.
Trong luận văn này, mơ hình quản lý luồng dựa vào chi phí (PFC: price-based
flow control) được dùng để so sánh những phiên bản của TCP và những thuật tốn
mới dựa vào mơ hình này.
Tại mỗi nguồn sẽ có một khả năng sử dụng là Ui(xi) với xi là tốc độ của nguồn,
khả năng sử dụng của mạng là là tổng các khả năng sử dụng của các nguồn. Mục
tiêu của chúng ta là tìm giá trị tối ưu xr * sao cho cực đại khả năng sử dụng của
mạng (đặc trưng bởi hàm khả dụng mạng là tổng các hàm khả dụng của các user

å U i ( xi ) ). Các phương pháp và giải thuật đã được đề ra trong [2], tuy nhiên bài
toán chỉ được giải quyết với giả sử hàm khả dụng lõm để cho kết quả là cực đại
tồn cục.
Một thuật tốn mới được đề nghị [1] cho những kết quả tốt hơn, r proximal
convexification, được luận văn này miêu tả và mô phỏng cho những kết quả hội tụ
tốt hơn cải thiện những nhược điểm của TCP
1.2 HƯỚNG ĐỀ CẬP CỦA LUẬN VĂN :
Việc quản lý lưu lượng (Traffic control ) liên quan đến việc tối ưu hóa hoạt
động của mạng trên cơ sở điều hành lưu lượng (traffic) hay nói cách khác là điều
3

Chương 1: Giới thiệu đề tài

hành lưu lượng cho phù hợp với topo mạng. Khái niệm này được dùng để phân biệt
với khái niệm thiết kế mạng (network design)- thiết kế mạng liên quan đến việc xây
dựng topo mạng sao cho phù hợp với lưu lượng.

Mục tiêu thực hiện theo định hướng lưu lượng bao gồm: Quản lý lưu lượng
chủ yếu tập trung vào khả năng ánh xạ hiệu quả lưu lượng đến các topo mạng đang
tồn tại để tối ưu hóa việc sử dụng tài nguyên mạng. Chức năng điều khiển lưu
lượng thực hiện việc tối ưu hiệu quả mạng hiện hành, làm cho việc vận hành hiệu
quả và tin cậy hơn trong đó tạo cho người dùng hiệu quả QoS.
Nghẽn trong mạng có thể xuất hiện nếu những người sử dụng gửi dữ liệu vào
mạng lớn hơn tốc độ cho phép bởi tài nguyên mạng. Ví dụ nghẽn có thể xuất hiện
bởi vì các bộ chuyển mạch trọng có kích thước đệm hạn chế để chứa các gói đến
trước khi xử lý.

Hình 1.2 Mơ phỏng q trình nghẽn và bị rớt gói của TCP
Trong [2], tác giả đề nghị một phương pháp tối ưu để điều khiển lưu lượng
mục đích là cực đại hố hàm khả dụng của nguồn hay tối ưu tốc độ truyền dẫn của
4

Chương 1: Giới thiệu đề tài

nguồn dùng thuật toán gradient projection, tác giả chứng minh sự hội tụ của giải
thuật và minh hoạ sự hội tụ của giải thuật. Tuy nhiên, giải thuật chỉ được thực hiện
với giả sử là hàm khả dụng lõm (concave).
Trong [1], tác giả đề nghị hiệu chỉnh và cải tiến phương pháp của Steven
H.Low [2] bằng thuật tốn r proximal convexification . Tác giả mơ tả lại thuật
toán synchronous gradient projection của tác giả Steven H. Low và hiệu chỉnh lại
bằng thuật toán convexified prọjection. Sau cùng, tác giả hiệu chỉnh bằng thuật
toán r proximal convexification cho những kết quả hội tụ tốt hơn.
Luận văn này sẽ đề cập đến cả 3 giải thuật được đề xuất bởi Kozakiewicz [1],
chứng minh và mô phỏng các giải thuật và chứng tỏ sự cải thiện so với giải thuật
TCP đồng thời đưa ra hướng cải tiến để phù hợp hơn với mơ hình mạng internet
thực tế. Đồng thời luận văn cũng khái quát về hướng nghiên cứu và đề cập giải

thuật tối ưu mạng dùng chi phí trên thế giới.

5

Chương 2: Lý thuyết tối ưu hóa cho bài tốn điều khiển lưu lượng mạng internet

CHƯƠNG 2: LÝ THUYẾT TỐI ƯU HOÁ CHO BÀI TOÁN
ĐIỀU KHIỂN LƯU LƯỢNG MẠNG INTERNET
2.1 KHÁI NIỆM VỀ TỐN TỐI ƯU:
Trong tốn học, thuật ngữ tối ưu hóa chỉ tới việc nghiên cứu các bài
tốn có dạng
Cho trước: một hàm f : A

R từ tập hợp A tới tập số thực

Tìm: một phần tử x0 thuộc A sao cho f(x0) ≤ f(x) với mọi x thuộc A
("cực tiểu hóa") hoặc sao cho f(x0) ≥ f(x) với mọi x thuộc A ("cực đại
hóa").
Một phát biểu bài tốn như vậy đơi khi được gọi là một quy hoạch
toán học (mathematical program). Nhiều bài toán thực tế và lý thuyết có thể
được mơ hình theo cách tổng qt trên.
Miền xác định A của hàm f được gọi là khơng gian tìm kiếm. Thơng
thường, A là một tập con của không gian Euclid Rn, thường được xác định
bởi một tập các ràng buộc, các đẳng thức hay bất đẳng thức mà các thành
viên của A phải thỏa mãn. Các phần tử của A được gọi là các lời giải khả thi.
Hàm f được gọi là hàm mục tiêu, hoặc hàm chi phí. Lời giải khả thi nào cực
tiểu hóa (hoặc cực đại hóa, nếu đó là mục đích) hàm mục tiêu được gọi là lời
giải tối ưu.
Thông thường, sẽ có một vài cực tiểu địa phương và cực đại địa

phương, trong đó một cực tiểu địa phương x* được định nghĩa là một điểm
thỏa mãn điều kiện:
Với giá trị δ > 0 nào đó và với mọi giá trị x sao cho
;
6

Chương 2: Lý thuyết tối ưu hóa cho bài tốn điều khiển lưu lượng mạng internet

công thức sau luôn đúng

Nghĩa là, tại vùng xung quanh x*, mọi giá trị của hàm đều lớn hơn
hoặc bằng giá trị tại điểm đó. Cực đại địa phương được định nghĩa tương tự.
Thông thường, việc tìm cực tiểu địa phương là dễ dàng – cần thêm các thơng
tin về bài tốn (chẳng hạn, hàm mục tiêu là hàm lồi) để đảm bảo rằng lời
giản tìm được là cực tiểu tồn cục.

Hinh 2.1: Hàm lồi (convex) và hàm lõm (concave)

Hình 2.2 Hàm lồi và hàm lồi nghiêm ngặt

7

Chương 2: Lý thuyết tối ưu hóa cho bài tốn điều khiển lưu lượng mạng internet

Hình 2.3 Hàm lõm và hàm lõm nghiêm ngặt
2.2 CÁC PHƯƠNG PHÁP GIẢI BÀI TOÁN TỐI ƯU:
Đối với các hàm khả vi hai lần (twice-differentiable), có thể giải các
bài tốn khơng ràng buộc bằng cách tìm các điểm mà tại đó đạo hàm của

hàm mục tiêu bằng 0 (điểm dừng) và sử dụng ma trận Hesse để xác định
xem đó là cực tiểu, cực đại, hay điểm n ngựa.
Ta có thể tìm các điểm dừng bằng cách bắt đầu từ một điểm dự đoán
là điểm dừng rồi tiến về điểm dừng bằng cách lặp đi lặp lại các phương pháp
như:
Ø Phương pháp Gradient (gradient descent)
Ø phương pháp Newton
Ø phương pháp Gradient liên hợp (conjugate gradient)
Ø line search
Nếu hàm mục tiêu là hàm lồi trong vùng quan tâm thì cực tiểu địa
phương sẽ là cực tiểu tồn cục. Có các phương pháp số nhanh chóng và hiệu
quả cho việc tối ưu hóa các hàm lồi khả vi hai lần.

8

Chương 2: Lý thuyết tối ưu hóa cho bài tốn điều khiển lưu lượng mạng internet

Các bài toán ràng buộc thường có thể được biến đổi thành một bài
tốn khơng có ràng buộc bằng phương pháp nhân tử Lagrange (Lagrange
multiplier).
2.3 QUY HOẠCH LỒI –BÀI TOÁN VÀ CÁC KHÁI NIỆM CƠ BẢN:
2.3.1 Định nghĩa quy hoạch toán học: Bài toán quy hoạch tốn học
(mathematical programming) là bài tốn tìm cực trị,

trong đó
1.

gọi là hàm mục tiêu.

2.

là các ràng buộc bất đẳng thức.
là các ràng buộc đẳng thức.

3.
4.
5.

là miền xác định.
thỏa mãn tất cả các ràng buộc gọi là nghiệm chấp nhận được

(hoặc gọi tắt là nghiệm).
Tập tất cả các nghiệm chấp nhận được,
Khi tập nghiệm
6. Nếu

, ta nói

, được gọi tắt là tập nghiệm.

thỏa được.

bị chặn dưới trên tập nghiệm, ta nói

bị chặn.

7. Giá trị tối ưu của hàm mục tiêu
nếu
nếu

nếu

thỏa được.
thỏa được nhưng không bị chặn.

không thỏa được.
9

Chương 2: Lý thuyết tối ưu hóa cho bài tốn điều khiển lưu lượng mạng internet

8. Nghiệm tối ưu của

là nghiệm chấp nhận được

. Bài tốn quy hoạch

sao cho

có nghiệm tối ưu gọi là bài

tốn giải được.
Ø Nhận xét:
có thể biến thành

1. Các ràng buộc dạng
.

2. Ta cũng có thể phát biểu bài tốn tìm cực đại với các khái niệm bị
chặn, giá trị tối ưu thay đổi tương ứng.

2.3.2 Định nghĩa quy hoạch lồi: Bài toán quy hoạch toán học

gọi là bài toán quy hoạch lồi (convex programming) nếu
1.

là tập lồi.

2.

là các hàm lồi.

3. Khơng có ràng buộc đẳng thức.
Ø Nhận xét:
1. Ta có thể đưa vào các ràng buộc đẳng thức, nhưng do tính lồi của hàm
, hàm này phải là hàm tuyến tính trên

, do đó các điều kiện này

tương ứng với việc giới hạn tập nghiệm trên khơng gian affine con
của

, tức là khơng mất tính tổng qt, về mặt lý thuyết có thể giả sử

khơng có ràng buộc đẳng thức.
2. Trong thực hành, khi thiết kế thuật tốn quy hoạch, khơng thể khơng
tính đến các ràng buộc đẳng thức, khi đó thường người ta biến đổi

10

Chương 2: Lý thuyết tối ưu hóa cho bài tốn điều khiển lưu lượng mạng internet

thuật tốn để nó hoạt động trên không gian affine tương ứng (sử dụng
hệ cơ sở affine và các tọa độ trên hệ này).
3. Vì

lồi nên tập

lồi .Như vậy tập nghiệm

là tập lồi

vì nó là giao của các tập lồi.

Hình 2.2 Tập lồi và tập khơng lồi

Hình 2.3 Giao của các tập lồi

2.4 TỐI ƯU KHÔNG RÀNG BUỘC – BÀI TOẤN VÀ KHÁI NIỆM:
2.4.1 Định nghĩa:
Bài tốn tối ưu khơng ràng buộc (unconstrained optimization) là bài
tốn tìm cực tiểu sau

11

Chương 2: Lý thuyết tối ưu hóa cho bài tốn điều khiển lưu lượng mạng internet

trong đó

gọi làm hàm mục tiêu.

Ø Nhận xét:
1. Tập nghiệm tối ưu (optimal solution)

là tập

nào chỉ nhận giá trị

2. Bất cứ một hàm

trên

có thể coi là

hàm đánh giá sai số (error measurement) của nghiệm

so với

nghiệm tối ưu.
Ví dụ:
1.
2.
3. Nếu một thuật tốn tối ưu (optimization algorithm/method) trong quá
trình tìm kiếm nghiệm tối ưu sinh ra nghiệm
đánh giá sai số của nghiệm

Ta còn gọi dãy

tại bước lặp thứ thì

là

là quỹ đạo (trajectory) của thuật tốn.

4. Một thuật toán tối ưu phải bảo đảm sai số tiến tới

khi số bước lặp

ngày càng lớn

2.4.2 Phân loại các thuật toán tối ưu:
1. Các phương pháp bậc 0: các phương pháp chỉ sử dụng giá trị của hàm
.

12

Chương 2: Lý thuyết tối ưu hóa cho bài tốn điều khiển lưu lượng mạng internet

2. Các phương pháp bậc 1: các phương pháp sử dụng giá trị của hàm
và đạo hàm (gradient)

.

3. Các phương pháp bậc 2: các phương pháp sử dụng giá trị của hàm
, đạo hàm

và ma trận Hessian

.

2.4.3 Định nghĩa (hướng làm giảm hàm mục tiêu):
Hướng
nếu tồn tại

là hướng làm giảm hàm mục tiêu (descent direction)

tại

sao cho

Ø Định lý: Nếu

thì

là hướng làm giảm hàm mục tiêu tại

.
Ø Chứng minh: Đặt

Với

, ta có

đủ nhỏ thì

. Vì vậy khi đủ nhỏ, ta có
do
Tức là

.

Ø Nhận xét: Mệnh đề ngược lại chưa chắc đã đúng tức là nếu tồn tại
để

thì vẫn có thể
thì ta có

Ø Hệ quả: Nếu
1.

thì

là hướng làm giảm hàm mục tiêu tại .

13

. Tuy nhiên, nếu

Chương 2: Lý thuyết tối ưu hóa cho bài tốn điều khiển lưu lượng mạng internet

2.

là hướng làm giảm hàm mục tiêu tại với

là ma trận đối

xứng, xác định dương bất kì.

Ø Lưu ý:
làm hướng giảm hàm

1. Các phương pháp tối ưu sử dụng hướng

mục tiêu gọi là các phương pháp xuống đồi theo hướng đạo hàm
(gradient descent) (do hướng

là hướng làm giảm hàm mục

tiêu nhanh nhất trong tất cả các hướng tại ).
2. Để so sánh các hướng làm giảm hàm mục tiêu, người ta thường chuẩn
.

hóa các hướng này sao cho
2.4.4 Định nghĩa tập ứng cử viên:

Nếu trong các bước lặp, thuật tốn tối ưu ln duy trì một tập

sao

cho
nếu
thì

gọi là tập ứng cử viên (localizer) tại bước .
Ø Nhận xét:
1. Rõ ràng, mục tiêu của các thuật toán tối ưu là sau một số bước lặp, lý
tưởng nhất là ta có
ln khác rỗng nếu

(lưu ý: theo định nghĩa thì tập ứng cử viên
khác rỗng).

2. Nếu khơng được như vậy, thì thuật tốn tối ưu phải đảm bảo

Khi đó

với

có thể coi là cận trên của

và với mọi

.
14

vì

Chương 2: Lý thuyết tối ưu hóa cho bài tốn điều khiển lưu lượng mạng internet

3. Tốc độ hội tụ của

về ít nhất là bằng tốc độ hội tụ của

về 0.

Ø Ví dụ: Thuật tốn chia đơi (bisection) nổi tiếng dùng để tìm nghiệm
trên đoạn

mà

(giá trị hàm liên tục trái dấu ở

hai đầu đoạn thẳng):
Bước : Gán
Bước : Ta có tập ứng cử viên

với

thì thơng báo nghiệm

Nếu

. Đặt

.

gán

Nếu

,

. Chuyển sang bước

ngược

lại,

gán

.

Ø Nhận xét:
, phải tồn tại

1. Tại mỗi bước lặp, vì
. Nghĩa là

sao cho

(nếu ta đặt

2. Ta có

).

, suy ra, tốc độ hội tụ của thuật

tốn chia đơi là tuyến tính.
3. Thuật tốn trên có thể áp dụng để tìm cực tiểu của hàm khả vi liên tục
nếu ta biết

và

chỉ tại duy nhất một điểm

. Ta áp dụng thuật toán trên với hàm

.

2.4.5 Tối ưu không ràng buộc - Xuống đồi theo hướng đạo hàm
(gradient descent)
Ta xem xét một phương pháp tối ưu hóa hay được sử dụng nhất, đó là
phương pháp xuống đồi theo hướng véctơ đạo hàm (gradient descent). Đúng

15

Tối ưu mạng internet sử dụng thuật toán p proximal convexification

Tài liệu liên quan

Tài liệu bạn tìm kiếm đã sẵn sàng tải về