Luận án tiến sĩ Kỹ thuật viễn thông: Nghiên cứu các giải pháp đảm bảo chất lượng mạng sử dụng kỹ thuật định tuyến

Chia sẻ: Tỉ Thành | Ngày: | Loại File: PDF | Số trang:159

Thêm vào BST

Báo xấu

24
lượt xem 3
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Mục đích của luận án nhằm đề xuất mô hình, giải thuật định tuyến đảm bảo QoS mới, có khả năng ứng dụng trong mạng viễn thông phát triển mạnh mẽ hiện nay trên cơ sở nghiên cứu các bài báo, các đề xuất và các công trình liên quan. Đề xuất các giải pháp để nâng cao hiệu năng các giải thuật định tuyến đảm bảo QoS dùng TTNB.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận án tiến sĩ Kỹ thuật viễn thông: Nghiên cứu các giải pháp đảm bảo chất lượng mạng sử dụng kỹ thuật định tuyến

i LỜI CẢM ƠN Luận án tiến sĩ này được thực hiện tại Học viện Công nghệ Bưu chính Viễn thông, dưới sự hướng dẫn khoa học của TS. Nguyễn Chiến Trinh và TS. Bùi Thị Minh Tú. Nghiên cứu sinh xin bày tỏ lòng biết ơn sâu sắc tới các thầy giáo hướng dẫn về những định hướng nghiên cứu, hướng dẫn khoa học và phương pháp luận nghiên cứu khoa học, cùng với đó là những kiến thức, kinh nghiệm trong suốt quá trình nghiên cứu và thực hiện luận án. Nghiên cứu sinh cũng xin cám ơn các thầy giáo PGS. TS. Bùi Trung Hiếu, PGS. TS. Nguyễn Tiến Ban, PSG. TS. Nguyễn Văn Tuấn và các thầy giáo trong Học viện đã giúp đỡ, động viên, đóng góp những ý kiến quý báu để nghiên cứu sinh hoàn thành luận án. Nghiên cứu sinh xin chân thành cảm ơn Lãnh đạo Học viện Công nghệ Bưu chính Viễn thông, Hội đồng Tiến sĩ của Học viện và Khoa Quốc tế và Đào tạo Sau đại học đã tận tình hướng dẫn, hỗ trợ, giúp đỡ và tạo mọi điều kiện thuận lợi cho nghiên cứu sinh trong quá trình nghiên cứu và hoàn thành luận án. Nghiên cứu sinh xin chân thành cảm ơn Lãnh đạo Viễn thông Đà Nẵng đã tạo điều kiện cho nghiên cứu sinh tham gia khóa đào tạo và quan tâm, động viên, tạo điều kiện trong công việc để nghiên cứu sinh có thể hoàn thành luận án. Nghiên cứu sinh xin chân thành cảm ơn các bạn đồng nghiệp, bạn bè thân hữu đã khích lệ, động viên trong suốt quá trình thực hiện luận án. Cuối cùng, xin bày tỏ lòng biết ơn sâu sắc nhất tới những người thân trong gia đình và những bạn bè thân thiết đã luôn luôn khích lệ, động viên, cảm thông, chia sẻ và hết lòng tạo điều kiện cho nghiên cứu sinh trong suốt quá trình nghiên cứu để hoàn thành luận án. Hà Nội, ngày tháng năm 2018 Tác giả Trần Minh Anh
ii LỜI CAM ĐOAN Tôi xin cam đoan luận án “Nghiên cứu các giải pháp đảm bảo chất lượng mạng sử dụng kỹ thuật định tuyến” là công trình nghiên cứu của tôi, ngoài những kiến thức tham khảo từ các tài liệu nghiên cứu liên quan đã được chỉ rõ trong danh mục tài liệu tham khảo ở phần sau của luận án. Những đóng góp của luận án là kết quả nghiên cứu của tác giả, một phần đã được công bố trên các tạp chí, kỷ yếu của các hội nghị khoa học chuyên ngành, phần còn lại chưa được công bố trong bất kỳ công trình nào khác. Hà Nội, ngày tháng năm 2018 Tác giả Trần Minh Anh
iii MỤC LỤC LỜI CẢM ƠN ..............................................................................................................i LỜI CAM ĐOAN ...................................................................................................... ii MỤC LỤC ................................................................................................................. iii THUẬT NGỮ VIẾT TẮT .........................................................................................vi DANH MỤC KÝ HIỆU .............................................................................................. x DANH MỤC HÌNH VẼ ...........................................................................................xiv DANH MỤC BẢNG BIỂU ................................................................................... xvii MỞ ĐẦU .....................................................................................................................1 CHƯƠNG 1TỔNG QUAN VỀ VẤN ĐỀ ĐẢM BẢO CHẤT LƯỢNG DỊCH VỤ TRONG MẠNG VIỄN THÔNG ................................................................................7 1.1 Tổng quan yêu cầu về QoS trên mạng viễn thông ....................................7 1.1.1 Giới thiệu: .....................................................................................................7 1.1.2 Các thông số QoS: ......................................................................................... 8 1.1.3 Xây dựng các ràng buộc liên quan đến đảm bảo chất lượng dịch vụ .........11 1.1.4 Vấn đề đảm bảo QoS khi mạng viễn thông phát triển mạnh mẽ trong giai đoạn hiện nay .......................................................................................................15 1.1.4.1 Tổng quan................................................................................................ 15 1.1.4.2 Định hướng cấu trúc mạng và yêu cầu đảm bảo QoS trên mạng viễn thông trong thời gian tới .................................................................................... 16 1.2 Kỹ thuật định tuyến đảm bảo chất lượng dịch vụ ...................................18 1.2.1 Tổng quan: ...................................................................................................18 1.2.2 Định tuyến đảm bảo QoS dùng thông tin toàn cục .....................................21 1.2.3 Định tuyến đảm bảo QoS dùng thông tin nội bộ .........................................29 1.3 Các vấn đề cần nghiên cứu về định tuyến QoS dùng TTNB ..................38 1.4 Kết luận chương ...................................................................................... 39 CHƯƠNG 2CÁC PHƯƠNG PHÁP ĐÁNH GIÁ HIỆU NĂNG CÁC GIẢI THUẬT ĐỊNH TUYẾN TRÊN MẠNG..................................................................................41 2.1 Mở đầu.........................................................................................................41 2.2 Phần mềm ứng dụng để mô phỏng mạng .................................................... 42 2.3 Các tiêu chí đánh giá ...................................................................................44 2.3.1 Xác suất nghẽn ........................................................................................... 41
iv 2.3.2 Độ trễ đầu cuối – đầu cuối .......................................................................425 2.3.3 Cân bằng tải ..............................................................................................445 2.4 Xây dựng các hệ số đánh giá cân bằng tải mạng ........................................46 2.4.1 Đề xuất hệ số DBM: .................................................................................... 46 2.4.2 Khả năng ứng dụng hệ số DBM trong việc đánh giá cân bằng tải và chất lượng mạng ..........................................................................................................49 2.5 Việc ứng dụng hệ số DBM để đánh giá hiệu năng giải thuật định tuyến ...49 2.5.1. Giới thiệu.................................................................................................49 2.5.2. Đánh giá hiệu năng định tuyến qua giá trị hệ số DBM ........................... 50 2.6 Kết luận chương .......................................................................................... 51 CHƯƠNG 3ĐỀ XUẤT CÁC GIẢI THUẬT ĐỊNH TUYẾN ĐA RÀNG BUỘC SỬ DỤNG THÔNG TIN NỘI BỘ ..................................................................................52 3.1 Mở đầu.........................................................................................................52 3.2 Các nghiên cứu liên quan ............................................................................53 3.3 Đề xuất giải thuật định tuyến dùng thông tin nội bộ sử dụng băng thông và độ trễ làm tiêu chuẩn chọn đường .......................................................................54 3.3.1. Giới thiệu.................................................................................................54 3.3.2. Mô tả giải thuật RBDA ...........................................................................54 3.3.3. Mô phỏng đánh giá hiệu năng giải thuật định tuyến RBDA...................57 3.3.4. Mô tả giải thuật BQRA ...........................................................................63 3.3.5. Mô phỏng đánh giá hiệu năng giải thuật định tuyến BQRA...................64 3.4 Đề xuất giải thuật định tuyến dùng thông tin nội bộ sử dụng nhiều thông số QoS làm tiêu chuẩn chọn đường .........................................................................69 3.4.1 Giới thiệu: ............................................................................................... 69 3.4.2 Mô tả giải thuật BDER: ..........................................................................69 3.4.3 Mô phỏng đánh giá hiệu năng giải thuật định tuyến BDER ...................72 3.5 Độ phức tạp tính toán của các giải thuật ..................................................... 78 3.6 Kết luận chương .......................................................................................... 79 CHƯƠNG 4ĐỀ XUẤT CÁC BIỆN PHÁP CẢI THIỆN HIỆU NĂNG CHO GIẢI THUẬT ĐỊNH TUYẾN DÙNG THÔNG TIN NỘI BỘ ..........................................80 4.1. Mở đầu.........................................................................................................80 4.2. Đề xuất tập tuyến truyền linh động cho giải thuật định tuyến dùng TTNB 81 4.2.1. Giới thiệu................................................................................................. 81
v 4.2.2. Một số khái niệm liên quan đến tập tuyến truyền. ..................................81 4.2.3. Ảnh hưởng của kiểu tập tuyến truyền đến hoạt động của giải thuật định tuyến dùng thông tin nội bộ ..............................................................................83 4.2.4. Mô phỏng đánh giá hiệu quả của tập tuyến truyền linh động đối với giải thuật định tuyến dùng TTNB ............................................................................84 4.2.5. Đánh giá hiệu năng định tuyến QoS sử dụng tập tuyến truyền linh động .. .............................................................................................................90 4.3. Đề xuất ứng dụng kiểu định tuyến phân tán trong giải thuật định tuyến dùng thông tin nội bộ ........................................................................................... 91 4.3.1. Giới thiệu ................................................................................................ 91 4.3.2. Một số định lý liên quan đến đề xuất ứng dụng kiểu định tuyến phân tán . ................................................................................................................91 4.3.3. Mô tả giải thuật đề xuất: .........................................................................95 4.3.4. Mô phỏng đánh giá hiệu năng định tuyến. .............................................98 4.4. Đề xuất cơ chế điều khiển linh hoạt trong thuật toán định tuyến dùng thông tin nội bộ ứng dụng kiểu định tuyến phân tán ...................................................101 4.4.1. Giới thiệu chung: ...................................................................................101 4.4.2. Một số định lý liên quan đến việc ứng dụng cơ chế điều khiển linh hoạt .. ...........................................................................................................101 4.4.3. Mô tả giải thuật đề xuất: .......................................................................102 4.4.4. Mô phỏng đánh giá hiệu năng định tuyến .............................................106 4.5. Độ phức tạp tính toán của các giải thuật ...................................................112 4.6. Kết luận chương ........................................................................................112 KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN TIẾP THEO .........................................114 1. Kết luận chung ..........................................................................................114 2. Hướng phát triển tiếp theo.........................................................................115 DANH MỤC CÁC CÔNG TRÌNH CÔNG BỐ CỦA TÁC GIẢ ...........................117 TÀI LIỆU THAM KHẢO ......................................................................................120 PHỤ LỤC . ..............................................................................................................130
vi THUẬT NGỮ VIẾT TẮT Viết tắt Nghĩa tiếng Anh Nghĩa tiếng Việt Third Generation mobile 3G Mạng di động thế hệ thứ 3 telecommunications Fourth Generation mobile 4G Mạng di động thế hệ thứ 4 telecommunications ATM Asynchronous Transfer Phương thức truyền dị bộ Mode Hệ số đánh giá cân bằng băng BBM Balanced Bandwidth Metric thông mạng Bandwidth Blocking BBP Xác suất nghẽn băng thông Probability Bandwidth-Delay- BDER (Tên của giải thuật đề xuất) bitErrorRate based Routing Routing Algorithm based on Giải thuật định tuyến dựa trên băng bdp Bandwidth-Delay- thông - độ trễ- tỷ lệ lỗi gói tin Packeterrorrate Bellman- Tên của thuật toán tìm đường ngắn Bellman-Ford algorithm Ford nhất mô tả tại [25] Bandwidth-Delay Constraint BQRA (Tên của giải thuật đề xuất) QoS Routing Algorithm BRB Best Reserved Bandwidth Dự trữ băng thông tốt nhất BW Bandwidth Băng thông Compound Annual Growth CAGR Tốc độ tăng hàng năm tổng hợp Rate Localized Credit Based Định tuyến dựa trên chỉ số tín dụng CBR Routing dùng thông tin nội bộ CSHT (Infrastructure) Cơ sở hạ tầng Differential Bandwidth Hệ số đánh giá độ chênh lệch băng DBM Metric thông Tên của thuật toán tìm đường ngắn Dijkstra Dijkstra Algorithm nhất mô tả tại [50] DPS Dynamic Path Set Tập tuyến truyền linh động
vii Đơn vị tính lưu lượng, bằng 1 triệu exabyte Unit of Exabyte Gigabyte. FBP Flow Blocking Probability Xác suất nghẽn luồng FMC Fixed Mobile Convergence Hệ thống hội tụ di động – cố định Full HD Full High Definition Độ phân giải cao đầy đủ HD High Definition Đô phân giải cao Giải thuật định tuyến dựa trên lịch Highest Link Average HLABH sử băng thông trung bình các liên Bandwidth History kết cao nhất Hop, minimum number of Hop, minhop Bước nhảy, số bước nhảy ít nhất hops IP Internet Protocol Giao thức Internet IPTV Internet Protocol TeleVision Truyền hình sử dụng giao thức IP ISP Internet Service Provider Nhà cung cấp dịch vụ Internet ITU Telecommunication Standardization Sector Liên minh viễn thông quốc tế - lĩnh ITU_T vực tiêu chuẩn hóa viễn thông jitter Jitter of Delay Độ trôi trễ Chỉ số Jain, để tính độ cân bằng tải Jain’s Index Jain’s Index trên mạng mô tả tại [72] Localized Bandwidth- LBCR (Tên của giải thuật đề xuất) Constraint Routing Localized Bandwidth- LBHR constraint Hop-by-hop (Tên của giải thuật đề xuất) Routing Algorithm Giải thuật định tuyến đảm bảo QoS Localized Delay- LDCR dùng thông tin nội bộ lấy độ trễ làm Constrained QoS Routing ràng buộc Localized Distributed LDR (Tên của giải thuật đề xuất) Routing Localized Distributed LDRA bandwidth-constraint (Tên của giải thuật đề xuất) Routing Algorithm MAN Metro Area Network Mạng đô thị
viii Mạng các thiết bị di động kết nối MANET Mobile Ad Hoc Network không dây liên tục tự cấu hình, và không có hạ tầng mạng Giải thuật định tuyến lấy số bước MHA Minimum Hop Algorithm nhảy bé nhất Minimum Interference Giải thuật định tuyến dùng ảnh MIRA Routing Algorithm hưởng xuyên nhiễu bé nhất Multiprotocol Label MPLS Chuyển mạch Nhãn đa giao thức Switching Network Simulator version NS-2, NS-3 Phần mềm mô phỏng mạng 2, version 3 NwGN New Generation Network Mạng thế hệ mới Objective Modular Network Chương trình mô phỏng OMNET++ Testbed in C++ OMNET++ OPNET OPNET Simulation Program Chương trình mô phỏng OPNET Giao thức định tuyến chọn đường OSPF Open Shortest Path First ngắn nhất Giải thuật định tuyến phân chia tỷ PSR Proportional Sticky Routing lệ chặt QoS Quality Of Service Chất lượng dịch vụ Định tuyến đảm bảo chất lượng QoSR Quality of Service Routing dịch vụ QoS Routing using RBDA Bandwidth-Delay based (Tên của giải thuật đề xuất) Algorithm SDP Shortest-distance path (Giải thuật) Tuyến truyền ngắn nhất SLA Service Level Agreement Thỏa thuận cung cấp dịch vụ Synchronous Optical SONET Mạng quang đồng bộ Network SPS Static path set Tập tuyến truyền tĩnh Giải thuật định tuyến chọn đường SWP Shortest Widest Path rộng nhất ngắn nhất TTNB (local information) Thông tin nội bộ TTTC (glabal information) Thông tin toàn cục
ix UHDTV (4K, Ultra High Definition Truyền hình độ nét cực cao (4K, 8K …) Television (4K, 8K…) 8K …) uniform Uniform distribution law Luật phân phối uniform Video Video streaming Dòng thông tin video streaming VoD Video on Demand Dịch vụ Video theo yêu cầu VoIP Voice over IP Thoại sử dụng giao thức Internet WAN Wide Area Network Mạng diện rộng WSN Wireless Sensor Network Mạng cảm biến không dây Giải thuật định tuyến chọn đường WSP Widest Shortest Path ngắn nhất rộng nhất Mạng toàn cầu (dùng giao thức WWW World Wide Web http) Zettabyte Đơn vị tính lưu lượng, bằng 1 tỷ Unit of Zettabyte Gigabyte
x DANH MỤC KÝ HIỆU Ký hiệu Ý nghĩa (a,b) Liên kết kết nối hai nút mạng a và b Lưu lượng yêu cầu tại nút x (hiện tại, và dự báo trong tương ax,bx lai) A,A’,B,C Ký hiệu các tuyến truyền trong các định lý BBP Xác suất nghẽn băng thông Bi Tổng số lần truyền hỏng/từ chối truyền luồng tin trên liên kết giữa nút nguồn với nút liền kề |B| Tổng số luồng bị nghẽn BFi Tổng số lần truyền hỏng/từ chối truyền luồng tin trên tuyến truyền giữa nút nguồn với nút đích (trong giải thuật BQRA) bm Giá trị trung bình băng thông khả dụng theo số kết nối Bm Trung bình băng thông toàn mạng Bt Băng thông yêu cầu của yêu cầu định tuyến bw Giá trị băng thông trung bình yêu cầu bởi một luồng dữ liệu Bw(a,b) Băng thông còn lại của liên kết (a,b) Bw(P) Băng thông còn lại của cả tuyến truyền P Bwab Băng thông giữa hai nút liền kề a và b C Dung lượng trên một hướng liên kết Ci, Last Ci Chỉ số tuyến truyền trong giải thuật RBDA Cr Tham số thiết lập lại tập tuyến truyền d Độ sâu kết nối D Giá trị trễ các các hướng trên liên kết trên mạng DBM, BBM Các hệ số đánh giá cân bằng băng thông mạng dnew, dold Độ sâu kết nối mới, cũ. f, f(u) Ký hiệu luồng tin đến nút, hàm ràng buộc trọng số của luồng f FBP Xác suất nghẽn luồng fl_idx Chỉ số luồng tin dùng trong giải thuật LDRA
xi Ký hiệu Ý nghĩa g(x) Hàm ràng buộc trọng số G(N,L) Mạng G có N nút và L liên kết. h Độ dài trung bình của một tuyến truyền trên mạng i, j, (i,j) Các nút mạng i, j; liên kết giữa hai nút mạng i và j k Số tuyến truyền ngắn nhất giữa hai nút X, Z K Tập các nút liền kề |K| Số nút liền kề của tập K Ki Nút liền kề L Tập hợp số liên kết trên mạng m Giá trị trung bình băng thông khả dụng theo số nút M Số mô tả cửa sổ dịch trong thuật toán CBR Md Ma trận kết nối M với độ sâu kết nối d Mijd Phần tử (i,j) thuộc ma trận Md MAX_CREDITS Hệ thống cấp điểm của giải thuật CBR 𝑚𝑖𝑛𝐵𝑣𝑑 Giá trị băng thông bé nhất của tuyến truyền v trong tập Vd minhopij Số bước nhảy ngắn nhất giữa hai nút mạng i và j n Số bước nhảy tối đa trong tập tuyến truyền từ nút X đến nút Z N Số nút trên mạng, tập hợp số nút trên mạng. Ndi Yêu cầu băng thông tại các nút mạng trên mạng G(N,L) Tổng số luồng tin truyền trên tuyến truyền giữa cặp nút nguồn Ni và đích trong giải thuật RBDA ni Nút trung gian (từ 1 đến s) trên tuyến truyền P P Tuyến truyền từ nút đầu đến nút đích P.Credits Biến chỉ điểm của tuyến truyền (của giải thuật CBR) Biến chứa các giá trị băng thông, độ trễ ... trong các giải thuật P.Quality đề xuất PER Tỷ lệ mất gói trong giải thuật BDER
xii Ký hiệu Ý nghĩa Tuyến truyền có giá trị điểm cao nhất của tập Rmin và tập Ralt Pmin, Palt trong giải thuật CBR pt_idx Chỉ số điều khiển truyền tin trong giải thuật LDRA Pt_idx Chỉ số tuyến truyền trong giải thuật BQRA q Số tuyến truyền ngắn nhất giữa hai nút Y và Z Qj Tổng giá trị băng thông khả dụng tại mỗi nút R Tập tuyến truyền |R| Số tuyến truyền thuộc tập R Ralt Tập các tuyến truyền thay thế Reli Tập các tuyến truyền khả dụng trong giải thuật PSR resBwij Băng thông còn lại trên liên kết ij Rmin Tập các tuyến truyền ngắn nhất Rmin+1 Tập tuyến truyền trong giải thuật HLABH RQ Yêu cầu QoS từ luồng tin yêu cầu 𝑑 𝑅𝑖𝑗 Tập tuyến truyền (có độ sâu kết nối d) giữa hai nút i và j s Số liên kết trên một tuyến truyền P S Thông số cài đặt trước cho giải thuật BQRA, RBDA SLA Yêu cầu QoS từ luồng tin yêu cầu T Tổng luồng tin yêu cầu từ nút nguồn đến nút đích |T| Tổng số luồng phát sinh Ti Tổng số luồng sử dụng tuyến truyền giữa nút nguồn với nút đích Tx Lượng chịu tải tại nút X u, u(a,b), u(P) Giá trị thông số QoS của liên kết (a,b), của cả tuyến truyền P u1,u2...un Ký hiệu các giá trị ràng buộc (thông số QoS) tại nút u v1,v2...vn Ký hiệu các giá trị ràng buộc (thông số QoS) tại nút v v Số tuyến truyền trong tập tuyến truyền giữa hai nút mạng Vd Tập các tuyến truyền có độ sâu kết nối d
xiii Ký hiệu Ý nghĩa Vkd Tuyến truyền k thuộc tập Vd X, Y, Z Ký hiệu nút mạng xi Tải băng thông trên các liên kết trên mạng α Chỉ số thay đổi độ sâu kết nối αj , γ j các hệ số ưu tiên cho nút thứ j αx, γx các hệ số ưu tiên cho nút x βi Chỉ số so sánh chọn đường trong giải thuật BQRA Ф Tham số hệ thống của giải thuật CBR λ Giá trị tốc độ luồng dữ liệu đến nút theo luật Poisson μ Thời gian duy trì của mỗi dữ liệu theo quy luật hàm mũ ρ Tải thông tin trung bình toàn mạng
xiv DANH MỤC HÌNH VẼ Tên hình Trang Hình 1.1 Dự báo lượng thông tin trên mạng đến năm 2019 -Nguồn [27] 7 Hình 1.2 Xây dựng thủ tục so sánh tuần tự 13 Hình 1.3 Thủ tục so sánh tuần tự hai thông số QoS 14 Hình 1.4 Thủ tục so sánh tuần tự ba thông số QoS 14 Hình 1.5 Hội tụ dịch vụ và hạ tầng mạng 16 Hình 1.6 Hội tụ dịch vụ trên nền mạng viễn thông 17 Hình 1.7 Sơ đồ mô tả việc định tuyến trên mạng viễn thông 18 Hình 1.8 Mô hình Best-Effort – Nguồn [1] 24 Hình 1.9 So sánh định tuyến dùng TTTC và định tuyến dùng TTNB – Nguồn 30 [38] Hình 3.1 Lưu đồ hoạt động của RBDA 56 Hình 3.2 Mã giả ngẫu nhiên của RBDA 57 Hình 3.3 Các mạng mô phỏng có 32 nút (ISP1) và 18 nút (ISP2) 59 Hình 3.4 Xác suất nghẽn luồng trên ISP1 59 Hình 3.5 Xác suất nghẽn băng thông trên ISP1 60 Hình 3.6 Giá trị trễ đầu cuối trung bình khi thay đổi tải 61 Hình 3.7 Xác suất nghẽn luồng trên ISP2 61 Hình 3.8 Giá trị trễ đầu cuối trung bình khi tải cao và thấp trên ISP2 62 Hình 3.9 Các mạng mô phỏng có 18 nút (ISP2) và 9 nút (ISP3) 65 Hình 3.10 Các giá trị của DBM khi  thay đổi từ 0,2 đến 0,5 66 Hình 3.11 Giá trị trễ đầu cuối trung bình trên ISP2 67 Hình 3.12 Các giá trị của DBM trên mạng mô phỏng ISP3 68 Hình 3.13 Giá trị trễ đầu cuối trung bình khi tải =0.2 and 0.5 69 Hình 3.14 Lưu đồ hoạt động của BDER 71 Hình 3.15 Mã giả ngẫu nhiên của BDER 72
xv Hình 3.16 Các mạng mô phỏng có 32 nút (ISP1) và 60 nút (ISP4) 73 Hình 3.17 Xác suất nghẽn luồng trên ISP1 74 Hình 3.18 Giá trị trễ đầu cuối trung bình khi tải  = 0,8 75 Hình 3.19 Xác suất nghẽn luồng 76 Hình 3.20 Giá trị trễ đầu cuối trung bình khi tải  = 0,8 77 Hình 3.21 Ảnh hưởng của lưu lượng truyền loạt 78 Hình 4.1 Mạng mô phỏng ISP1 85 Hình 4.2 Xác suất nghẽn luồng 87 Hình 4.3 Xác suất nghẽn băng thông 88 Hình 4.4 Giá trị số bước nhảy trung bình khi  = 0,4 88 Hình 4.5 Giá trị số bước nhảy trung bình khi  = 0,8 89 Hình 4.6 Giá trị của độ sâu kết nối d của các tập tuyến truyền từ nút 0 90 Hình 4.7 So sánh hai kiểu định tuyến nguồn và phân tán – Nguồn [65] 92 Hình 4.8 Chứng minh định lý 4.1 92 Hình 4.9 Chứng minh định lý 4.2 93 Hình 4.10 Chứng minh điểm 1 của định lý 4.3 94 Hình 4.11 Chứng minh điểm 2 của định lý 4.3 94 Hình 4.12 Lưu đồ hoạt động của LBHR 97 Hình 4.13 Mạng mô phỏng ISP1 có 32 nút mạng 98 Hình 4.14 Xác suất nghẽn luồng 99 Hình 4.15 Xác suất nghẽn băng thông 100 Hình 4.16 Chứng minh định lý 4.5 102 Hình 4.17 Lưu đồ hoạt động của LDRA 105 Hình 4.18 Mạng mô phỏng ISP1 với 32 nút 107 Hình 4.19 Xác suất nghẽn luồng 108 Hình 4.20 Xác suất nghẽn băng thông 109 Hình 4.21 So sánh các chỉ số Jain về cân bằng băng thông mạng 110 Hình 4.22 Ảnh hưởng của lưu lượng truyền loạt 111 Hình PL.1. Mạng giả định 1 133
xvi Hình PL.2. Mạng giả định 2 134 Hình PL.3. Mạng điều hành viễn thông khu vực 136 Hình PL.4. Mạng mô phỏng 1 139 Hình PL.5. Mạng mô phỏng 2 140 Hình PL.6. So sánh thông số trễ toàn mạng 140 Hình PL.7. So sánh lưu lượng nhận toàn mạng 141 Hình PL.8. So sánh thông số trễ nội bộ các nút 141
xvii DANH MỤC BẢNG BIỂU Tên bảng Trang Bảng 1.1 Phân loại lưu lượng các dịch vụ 9 Bảng 1.2. Lớp dịch vụ và chuẩn QoS 10 Bảng 1.3. Các mục tiêu chất lượng đối với các ứng dụng thoại/video 10 Bảng 2.1 Các mô hình mạng trong các thí nghiệm mô phỏng 43 Bảng PL.1. Ma trận kết nối 1 134 Bảng PL.2. Ma trận kết nối 2 135 Bảng PL.3. Ma trận kết nối 3 135 Bảng PL.4. Ma trận kết nối 4 136 Bảng PL.5. Ma trận kết nối 5 137 Bảng PL.6. Ma trận kết nối 6 137
1 MỞ ĐẦU 1. Đặt vấn đề - Tính cấp thiết của đề tài Ngày nay, công nghệ viễn thông đã và đang phát triển nhanh chóng và đã trở thành nền tảng phát triển của xã hội; các công nghệ, kỹ thuật mới liên tục ra đời để đáp ứng các nhu cầu lưu lượng dữ liệu tăng mạnh do bùng nổ các loại hình dịch vụ viễn thông và các dịch vụ băng rộng nhằm đáp ứng nhu cầu của mọi lĩnh vực của xã hội. Sự tăng trưởng bùng nổ của lưu lượng dữ liệuđó đã làm cho việc đảm bảo chất lượng cho các dịch vụ cung cấp trên mạng viễn thông càng trở nên quan trọng, trong bối cảnh các dịch vụ viễn thông mới, yêu cầu chất lượng dịch vụ mạng ngày càng cao. Trong đó, việc chọn tuyến truyền từ nguồn dữ liệu đến nơi sử dụng đủ đáp ứng yêu cầu chất lượng của dịch vụ, đặc biệt là với các dịch vụ cần chất lượng tuyến truyền cao, chính là bài toán cần giải quyết hiện nay, trong bối cảnh mạng viễn thông đang phát triển ngày càng mạnh mẽ. Do đó, việc giải quyết vấn đề về đảm bảo chất lượng dịch vụ (QoS) cung cấp trên mạng mang ý nghĩa thực tiễn, đồng thời mang tính học thuật cao. Để thực hiện tốt yêu cầu này, việc xây dựng các giải pháp mới, giải thuật định tuyến mới trên cơ sở cải tiến những giải pháp đã và đang được sử dụng với mục tiêu góp phần đưa công nghệ định tuyến đảm bảo QoS được phổ dụng hơn, ứng dụng nhiều hơn trong thực tế đã trở thành vấn đề cấp thiết hiện nay. Trên cơ sở đó, Luận án tập trung nghiên cứu các vấn đề về chất lượng dịch vụ (QoS), cân bằng tải, định tuyến đảm bảo QoS và đề xuất các giải thuật định tuyến mới nhằm đảm bảo QoS cho dịch vụ viễn thông trên mạng viễn thông phát triển mạnhhiện nay cũng như trong thời gian sắp đến. 2. Tình hình nghiên cứu trong và ngoài nước - Trong nước: Hiện nay, các nghiên cứu về QoS tương đối phổ biến, được nghiên cứu nhiều, đáp ứng nhu cầu đảm bảo chất lượng dịch vụ trên các loại mạng nhưmạng tùy biến di động (MANET - mobile ad hoc network), mạng hội tụ di động – cố định (FMC - Fixed Mobile Convergence ) … thể hiện tại các nghiên cứu [2],
2 [4]. Định tuyến kiểu Best-Effort được nghiên cứu và mô tả tại [1] giúp hình dung quá trình định tuyến khi không có yêu cầu về QoS. Giải pháp sử dụng trí tuệ nhân tạo trong [6] cũng được nghiên cứu và đề xuất nhằm thoả mãn vấn đề đảm bảo QoS khi chuyển tải thông tin trên mạng viễn thông. Về định tuyến, việc nghiên cứu, đề xuất giải thuật định tuyến mới đã và đang sử dụng để bổ sung, trình bày hoặc giải các bài toán mang tính tổng quát cao về việc định tuyến thông tin trên mạng, cụ thể các nghiên cứu [2], [4], [5]. Về nghiên cứu phát triển mạng viễn thông hiện nay: Việc nghiên cứu đảm bảo chất lượng mạng như [95] đã giải quyết nhiều vấn đề về định tuyến ứng dụng trên mạng thế hệ mới, đồng thời cũng là một hướng ứng dụng gợi mở cho việc phát triển của mạng viễn thông Việt nam. - Ngoài nước: Các nghiên cứu về QoS như cơ chế định tuyến đảm bảo QoS và OSPF mở rộng [14], [39], [40], [51], [107] cũng là một giải pháp được quan tâm trong việc ứng dụng trên mạng viễn thông hiện nay. Đó là giải pháp nhằm tối ưu hóa việc chọn đường, và đề xuất giải bài toán định tuyến trong mạng viễn thông hiện nay với các giải thuật rất phổ biến nhưgiải thuật định tuyến chọn đường ngắn nhất rộng nhất (WSP - Widest Shortest Path), giải thuật định tuyến chọn đường rộng nhất ngắn nhất (SWP - Shortest Widest Path), giải thuật dùng tuyến truyền ngắn nhất (SDP - Shortest-distance path) … Bên cạnh đó, việc đề xuất và giải bài toán QoS trên mạng nội vùng, liên vùng, và mạng WAN-MAN, MANET cũng được nghiên cứu và đề xuất tại [17], [86], [104]. Đối với các mạng như: Mạng các thông tin không chính xác, không xác định ... việc nghiên cứu giải thuật định tuyến đảm bảo QoS cũng được đề xuất tại [13], [28], [61], [63], [69], [102]. Các thông số như : thông tin không chính xác, thông số không xác định là các thông số đầu vào quan trọng để đề xuất các mô hình định tuyến QoS mới, ứng dụng trong các mạng đặc thù, nơi mà các thông tin đến với các nút mạng không đầy đủ, không trọn vẹn.
3 Các đề xuất khác liên quan đến giải thuật định tuyến đảm bảo QoS đề xuất tại [30], [31], [39], [42], [53], [57], [59], [66],[71], [74], [88], [89], [99], [110] ... cũng là các cách mà các nhà nghiên cứu đi sâu vào phân tích các khía cạnh còn chưa được nghiên cứu trong việc mở rộng mô hình mạng, nhằm đáp ứng với một xã hội thông tin ngày càng mở rộng cũng như các giải pháp công nghệ ứng dụng trong việc tìm và xây dựng giải thuật mới cho định tuyến đảm bảo QoS. Đặc biệt, các hướng nghiên cứu về định tuyến đảm bảo QoS dùng thông tin nội bộ (TTNB) như tại [35], [36], [91], [97], [108] … đã được nghiên cứu nhiều hiện nay và hứa hẹn đem lại hiệu quả cao trong định tuyến đảm bảo QoS trong thời gian tới. Ngoài ra, các nghiên cứu mô phỏng luồng dữ liệu cũng được nghiên cứu nhiều tại các nghiên cứu [11], [34], [43], [68], [103] để đánh giá hiệu năng định tuyến. Các giải thuật định tuyến nêu trên sẽ được khảo sát kỹ hơn ở các phần sau của Luận án, làm cơ sở cho các đề xuất mới của Luận án. Về các nghiên cứu tiến trình phát triển của mạng viễn thông hiện nay: Các cường quốc công nghệ đặc biệt là Mỹ, Nhật đã đầu tư, nghiên cứu, và hoạch định mạng viễn thông nhằm đón đầu nhu cầu chất lượng mạng viễn thông của chính họ, với các dự án như FIND [24], NICT [60], AKARI [62], GENI [73] … Với nhu cầu cao về dịch vụ, công nghệ, ứng dụng công nghệ thông tin tại các thị trường trên, các nghiên cứu cũng chỉ ra các định hướng và các yêu cầu trong việc định tuyến thông tin nhằm ứng dụng hiệu quả trong mạng viễn thông hiện nay. Tóm lại, các nghiên cứu trên đã đề xuất được cơ chế mới cũng như mô hình mạng, mô hình cung cấp dịch vụ mới cùng với việc đề xuất cácgiải pháp định tuyến mới, hiệu quả hơn, đảm bảo QoS chất lượng cao hơn cho dịch vụ viễn thông, đáp ứng được nhu cầu ngày càng cao của thị trường viễn thông trong thời gian đến. 3. Mục tiêu, đối tượng và phạm vi nghiên cứu Với việc chọn lĩnh vực nghiên cứu là giải pháp đảm bảo chất lượng dịch vụ trên mạng viễn thông hiện nay, mục tiêu hướng đến của Luận án là đề xuất các giải pháp mới nhằm hoàn thiện hơn việc định tuyến thông tin trên mạng viễn thông hiện