1
HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG
---------------------------------------
TIÊU VĂN GIANG
NGHIÊN CỨU ĐỊNH TUYẾN VÀ GÁN BƯỚC SÓNG
TRONG MẠNG WDM SỬ DỤNG PHƯƠNG PHÁP
TÍNH TOÁN TIẾN HÓA LAI
NGÀNH : KHOA HỌC MÁY TÍNH
MÃ SỐ : 60.48.01
TÓM TẮT LUẬN VĂN THẠC SĨ
HÀ NỘI - 2012
LỜI NÓI ĐẦU
Sự bùng nổ của mạng Internet, sự phát triển số lượng người
sử dùng, sự phát triển của các ứng dụng và dịch vụ mới trên nền IP,
đó là những gì mà chúng ta đã chứng kiến trong vòng gần một thập
kỉ qua [7]. Mạng truyền dẫn quang đã đáp ứng được rất nhiều yêu
cầu về dung lượng, chi phí xây dựng và tính bảo mật thông tin. Hai
công nghệ quan trọng gần đây giúp tăng dung lượng mạng quang
đó là ghép kênh theo bước sóng WDM và khuếch đại sợi quang
EDFA [25].
Định tuyến và gán bước sóng (RWA) có thể được coi là một
bài toán cổ điển trong mạng quang WDM [17]. Trong đó nó có thể
được phân thành hai bài toán con: (i) định tuyến và (ii) gán bước
sóng. Bài toán con định tuyến là tìm đường từ nguồn tới đích, còn
bài toán con gán bước sóng thực hiện gán một bước sóng cho tuyến
được thiết lập bởi bài toán con định tuyến. Bài toán RWA có tính
kết hợp bởi bản chất của nó và thuộc lớp bài toán tối ưu hóa, do
vậy phù hợp với cách tiếp cận heuristic [13].
Đối với vấn đề RWA ta có thể xem xét nhiều mục tiêu thiết
kế mạng đồng thời như tối đa hóa số lượng yêu cầu liên lạc để
được phục vụ và giảm thiểu số lượng kênh bước sóng được chỉ
định[3][6].
Để giải bài toán thiết kế đa mục tiêu, các kỹ thuật tối ưu hóa
đa mục tiêu thường được sử dụng. Một số phương pháp sử dụng
các gần đúng đơn mục tiêu để giải các bài toán đa mục tiêu như
ràng buộc và tổng trọng số [1]. Tuy nhiên các gần đúng đơn mục
tiêu có một nhược điểm là rất khó tìm được các nghiệm tối ưu[16].
Do vậy mà các thuật toán tiến hóa đa mục tiêu được áp dụng để
giải các bài toán thiết kế đa mục tiêu này [18] sẽ thu được những
kết quả quan trọng cho việc thiết kế mạng toàn quang trên cơ sở
công nghệ WDM.
2
Qua đây tôi xin trân trọng cảm ơn TS.Nguyễn Đức Nhân và
các thầy cô trong hội đồng khoa học nhà trường, Khoa Quốc tế và
sau đại học đã giúp đỡ rất nhiều cho tôi để hoàn thiện luận văn này.
Tuy nhiên, do thời gian và trình độ còn giới hạn, tôi kính mong
được các thầy cô tiếp tục đóng góp, giúp đỡ để luận văn được hoàn
thiện tốt hơn và được ứng dụng vào thực tế.
Tôi xin trân trọng cảm ơn!
TÁC GIẢ
TIÊU VĂN GIANG
CHƯƠNG 1: TỔNG QUAN
Hệ thống thông tin của con người có lịch sử phát triển từ rất
lâu. Cho tới nay, đã có rất nhiều các hệ thống thông tin dưới các
hình thức đa dạng. Các hệt hống thông tin này được gán cho các
tên gọi nhất định theo môi trường truyền dẫn và đôi khi theo cả tính
chất dịch vụ của hệ thống. So với hệ thống thông tin hiện đại đầu
tiên là thông tin điện báo (đưa vào khai thác năm 1844) thì hệ
thống thông tin quang (mới được khai thác từ những năm 1980) là
hệ thống có tuổi đời còn khá trẻ. Tuy vậy cùng với sự phát triển của
các dịch vụ mạng và đòi hỏi ngày càng cao về dung lượng và băng
thông, hệ thống thông tin quang cũng đã phát triển rất mạnh mẽ về
công nghệ trong gần 3 thập niên qua. Do có ưu điểm như vậy nên
các hệ thống thông tin quang nhanh chóng được áp dụng rộng rãi
trên mạng lưới. Chúng còn tiềm tàng những khả năng rất lớn trong
việc hiện đại hoá các mạng lưới viễn thông trên thế giới.
1.1. Mạng WDM.
1.1.1. Định nghĩa:
WDM (Wavelength Division Multiplexing – Ghép kênh theo
bước sóng) là công nghệ “trong một sợi quang truyền dẫn đồng
thời nhiều tín hiệu quang với nhiều bước sóng khác nhau”. ở đầu
phát, nhiều tín hiệu quang có bước sóng khác nhau được tổ hợp lại
(ghép kênh) để truyền đi trên một sợi quang. ở đầu thu, tín hiệu tổ
hợp đó được phân giải ra (tách kênh), khôi phục lại tín hiệu gốc rồi
đưa vào các đầu cuối khác nhau.
1.1.2. Các công nghệ dùng trong mạng thông tin quang.
Phần này sẽ trình bày về các công nghệ đã, đang và sẽ được
dùng trong hệ thống thông tin quang.
1.1.2.1. TDM (Time Division Multiplexing):
TDM là phương pháp ghép kênh phân chia theo thời gian.
Đây là phương pháp giúp tăng số lượng tín hiệu được gửi trên
đường truyền vật lý.
Hình 1.1 : Ghép kênh theo thời gian
3
1.1.2.2. SONET/SDH:
SONET (Sychronous Optical Network : Mạng quang đồng
bộ) là một chuẩn của American National Standards Institute để
truyền dữ liệu đồng bộ trên môi trường truyền là cáp sợi quang.
Tương đương với SONET về mặt quốc tế là SDH.
SONET/SDH lấy các luồng n bit, ghép chúng lại, điều chế quang
tín hiệu và sử dụng thiết bị phát quang để gửi nó ra ngoài với một
tốc độ bit tương đương với : (tốc độ bit đi vào)
n . Vì vậy lưu
lượng đi đến bộ ghép kênh SONET tù bốn đầu vào với tốc độ 2,5
Gbps sẽ đi ra như một luồng đơn ở tốc độ 4
2,5 Gbps = 10 Gbps.
Nguyên tắc này được minh họa trong hình 1.2.
Hình 1.2 : Nguyên tắc ghép kênh trong mạng SONET
SONET cung cấp các chuẩn cho một số lượng lớn các tốc độ
truyền (tốc độ truyền thực tế vào khoảng 20 Gbps).
1.1.2.3. Gigabit Ethernet:
Công nghệ Ethernet 10 Gigabit được xây dựng trên nghi thức
Ethernet, nhưng có tốc độ nhanh gấp 10 lần Ethernet (1000 Mbps).
Ethernet Gigabit được triển khai như một công nghệ xương sống
cho các mạng đô thị. Đối với mạng diện rộng WAN, Ethernet 10
Gigabit cho phép các ISP (Internet Service Provider) và NSP
(Network Service Provider) tạo ra các liên kết tốc độ rất cao với giá
thành thấp từ các bộ chuyển mạch và các bộ định tuyến trong phạm
vi công ty cho đến thiết bị quang gán trực tiếp vào SONET/SDH.
Công nghệ Ethernet Gigabit hỗ trợ cả cáp sợi quang đơn mode và
đa mode. Tuy vậy, các khoảng cách được hỗ trợ tùy vào các kiểu
cáp sợi quang và bước sóng được thực thi trong ứng dụng.
1.1.3. Hệ thống thông tin quang nhiều kênh
Trên thực tế, sự ra đời của các hệ thống quang đa kênh đã giải
quyết được những hạn chế của hệ thống đơn kênh, đồng thời cũng
tận dụng được những công nghệ hiện có để phát triển mạnh mẽ. Cụ
thể là :
Thứ nhất, đối với hệ thống đơn kênh, khi tốc độ đạt tới mức
khoảng vài chục Gbit/s thì khoảng cách tuyến truyền dẫn sẽ bị rút
ngắn lại, các thiết bị điện tử sẽ đạt đến giới hạn của nó và không
đáp ứng được các xung tín hiệu cực kì hẹp; thêm vào đó chi phí
dành cho các giải pháp trên tuyến truyền dẫn trở nên tốn kém vì
cấu trúc, thuật toán phức tạp và đòi hỏi các thiết bị có công nghệ
cao.
Thứ hai, kỹ thuật ghép kênh quang được sử dụng sẽ tận
dụng được phổ hẹp của Laser, tận dụng được băng tần rất lớn của
sợi quang.
1.1.4. Nguyên lý cơ bản của ghép kênh theo bước sóng quang.
Nguyên lý cơ bản của ghép kênh theo bước sóng mang có
thể minh họa như hình 1.3.
Hình 1.3 : Quá trình ghép và giải ghép WDM
4
1.1.5. Mục đích công nghệ WDM.
Do băng thông quang rất lớn nên nếu chỉ sử dụng cho mục
đích đơn lẻ sẽ rất hao phí. Vì vậy sử dụng công nghệ WDM nhằm
mục đích tận dụng băng tần truyền dẫn của sợi quang bằng cách
truyền đồng thời nhiều kênh bước sóng trên cùng một sợi quang.
1.1.6. Phân loại hệ thống truyền dẫn WDM.
1.1.6.1. Hệ thống ghép bước sóng đơn hướng:
Chỉ thực hiện truyền theo một chiều trên sợi quang. Do vậy
để truyền thông tin giữa hai điểm cần hai sợi quang.
Hình 1.4: Hệ thống WDM đơn hướng
1.1.6.2. Hệ thống ghép bước sóng song hướng:
Có thể truyền theo hai chiều trên một sợi quang nên chỉ cần
một sợi quang để có thể trao đổi thông tin giữa hai điểm.
Hình 1.5: Hệ thống WDM song hướng
1.2. Định tuyến và gán bước sóng trong mạng WDM.
1.2.1. Định tuyến (Routing)
1.2.1.1. Giới thiệu
Định tuyến được coi là thành phần cốt yếu của kiến trúc
mạng, thiết kế mạng và điều hành mạng của mọi mạng thông tin, là
thành phần không thể thiếu trong mạng viễn thông.
1.2.1.2. Phân loại định tuyến
Có nhiều cách phân loại định tuyến, có thể đưa ra một số
loại định tuyến như sau:
Dựa vào chức năng thích nghi với trạng thái hiện thời của
mạng để phân loại thành: định tuyến tĩnh và định tuyến động
+ Định tuyến tĩnh: với định tuyến tĩnh, đường dẫn được
chọn trước cho mỗi cặp nguồn – đích của các node trong mạng.
+ Định tuyến động: định tuyến động lựa chọn tuyến dựa trên
thông tin trạng thái hiện thời của mạng.
Dựa vào phạm vi định tuyến, ta phân loại thành: định tuyến
trong và định tuyến ngoài.
Định tuyến trong: định tuyến xảy ra bên trong một hệ thống
độc lập (AS – Autonomous System), các giao thức thường dùng là
RIP (Router Information Protocol), IGRP (Interior Gateway
Routing Protocol), OSPF (Open Shortest Path First), EIGRP
(Enhanced IGRP),…
Định tuyến ngoài: định tuyến xảy ra giữa các hệ thống độc
lập (AS), liên quan tới dịch vụ của nhà cung cấp mạng sử dụng
giao thức định tuyến ngoài rộng và phức tạp. Giao thức thường
dùng là BGP (Border Gateway Protocol).
5
Hình 1.6: Định tuyến trong và định tuyến ngoài
1.2.2. Định tuyến và gán bước sóng (Routing and
Wavelength Assignment - RWA).
Tìm đường được hiểu theo hai khía cạnh, đó là tìm đường
vật lí mang được mẫu lưu lượng yêu cầu (Routing) và đưa ra bước
sóng phù hợp để mang lưu lượng trên mỗi link dọc path
(Wavelength Assignment) trong số các bước sóng cho phép (bởi
mỗi path gồm một số fiber, mà trên mỗi fiber này, bạn có thể có W
sub-chanels, cũng là W bưóc sóng và W lựa chọn cho yêu cầu kết
nối hiện tại). Vấn đề này được viết tắt là RWA. Rắc rối đặt ra đối
với bài toán RWA là nó đưa ra hai điều kiện sau:
Điều kiện tính liên tục bước sóng: một lightpath phải sử
dụng chung một bước sóng trên tất cả các link dọc theo đường đi
của nó từ nguồn đến đích.
Hình 1.7: Điều kiện tính liên tục bước sóng
Điều kiện tính riêng biệt về bước sóng: tất cả các lightpath
sử dụng cùng một link (fiber) phải được gán các bước sóng riêng
biệt.
Hình 1.8: Mạng WDM định tuyến bước sóng
1.3. Động cơ và mục tiêu nghiên cứu.
1.3.1. Động Cơ
Để giải bài toán thiết kế đa mục tiêu, các kỹ thuật tối ưu hóa
đa mục tiêu thường được sử dụng. Một số phương pháp sử dụng
các gần đúng đơn mục tiêu để giải các bài toán đa mục tiêu như
ràng buộc và tổng trọng số. Tuy nhiên các gần đúng đơn mục tiêu
có một nhược điểm là rất khó tìm được các nghiệm tối ưu. Do vậy
mà các thuật toán tiến hóa đa mục tiêu được áp dụng để giải các bài
toán thiết kế đa mục tiêu này.
1.3.2. Mục tiêu nghiên cứu
Nghiên cứu giải quyết bài toán định tuyến và gán bước sóng
đa mục tiêu trong mạng WDM bao gồm:
+ Xây dựng bài toán RWA như là một bài toán tối ưu đa
mục tiêu.