Tóm tắt Luận án tiến sĩ Kỹ thuật: 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ẻ: Trần Văn Nan | Ngày: | Loại File: PDF | Số trang:27

Thêm vào BST

Báo xấu

16
lượt xem 3
download

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

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 tại nhằm đáp ứng những đòi hỏi ngày càng cao của thị trường viễn thông trên cơ sở khảo sát những giải pháp đã và đang được áp dụng trên mạng hiện nay.

Chủ đề:

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

Lưu

Nội dung Text: Tóm tắt Luận án tiến sĩ Kỹ thuật: 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

BỘ THÔNG TIN VÀ TRUYỀN THÔNG HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG -------------------- TÓM TẮT 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 NCS: TRẦN MINH ANH NGƯỜI HƯỚNG DẪN: TS. NGUYỄN CHIẾN TRINH TS. BÙI THỊ MINH TÚ HÀ NỘI, 2018
i. Công trình hoàn thành tại: Học viện Công nghệ Bưu chính Viễn thông Người hướng dẫn khoa học: TS. Nguyễn Chiến Trinh TS. Bùi Thị Minh Tú Phản biện 1: Phản biện 2: Phản biện 3: Luận án được bảo vệ trước Hội đồng chấm Luận án cấp Học viện tại: Học việnCông nghệ Bưu chính Viễn thông, 122 Hoàng Quốc Việt, Hà Nội. Vào lúc: Có thể tìm hiểu luận án tại: Thư viện Học viện Công nghệ Bưu chính Viễn thông
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; 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. 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. Do đó, việc đảm bảo chất lượng dịch vụ (QoS) 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 đã trở thành vấn đề cấp thiết hiện nay. 2. 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à đả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 tại nhằm đáp ứng những đòi hỏi ngày càng cao của thị trường viễn thông trên cơ sở khảo sát những giải pháp đã và đang được áp dụng trên mạng hiện nay. 3. Các đóng góp của luận án Các đóng góp chính của luận án như sau: - Đề xuất các giải thuật định tuyến mới trong đó sử dụng thông tin nội bộ làm cơ sở, và sử dụng các thông số QoS làm tiêu chuẩn chọn đường. - Đề xuất tập tuyến truyền linh động hỗ trợ cho hoạt động của giải thuật định tuyến dùng TTNB được hiệu quả hơn.
2 - Đề xuất các giải thuật định tuyến dùng TTNB trong đó dựa vào kiểu định tuyến phân tán nhằm làm tăng hiệu năng định tuyến và giảm bộ nhớ lưu trữ và tính toán tại các nút mạng. - Đề xuất các hệ số đánh giá cân bằng tải nhằm hỗ trợ cho việc đánh giá hiệu năng các giải thuật định tuyến. 4. Bố cục của luận án Luận án gồm 4 chương với bố cục như sau: Chương 1: Giới thiệu tổng quan về vấn đề đảm bảo QoS trên mạng viễn thông,vềđịnh tuyến đảm bảo QoS, nhất là định tuyến đảm bảo QoS dùng TTNB. Trên cơ sởđó,luận án xác định hướng nghiên cứu là đề xuất các giải thuật định tuyến đảm bảo QoS dùng TTNB và các giải pháp để nâng cao hiệu năng của các giải thuật này. Chương 2: Đề xuất các hệ số đánh giá cân bằng tải mạng, đồng thời, đề cập các phương pháp mô phỏng và các mô hình mạng được sử dụng trong luận án. Chương 3: Đề xuất các giải thuật định tuyến dùng TTNB, nhằm khắc phục được một số nhược điểm của các giải thuật định tuyến đã được nghiên cứu trong phần trước. Chương 4: Đề xuất tập tuyến truyền linh động ứng dụng cho giải thuật định tuyến dùng TTNB, cùng với đề xuất giải thuật định tuyến dùngTTNB ứng dụng kiểu định tuyến phân tán. Đề xuất nâng cao hiệu năng của dạng giải thuật này qua cơ chế điều khiển định tuyến linh hoạt, ứng dụng tốt trong giải thuật định tuyến dùng kiểu định tuyến phân tán. Cuối cùng là phần Kết luận và hướng phát triển tiếp theo.
3 CHƯƠNG 1 TỔNG QUAN VỀ VẤN ĐỀ ĐẢM BẢO CHẤT LƯỢNG DỊCH VỤ TRONG MẠNG VIỄN THÔNG 1.1 Tổng quan yêu cầu về QoS trên mạng viễn thông 1.1.1 Giới thiệu: Hiện nay, vấn đề đảm bảo QoS trở nên rất nan giải do có nhiều loại ứng dụng trên mạng viễn thông với các đặc tính lưu lượng khác nhau hoặc tích hợp nhiều loại dịch vụ trên cùng một nền ứng dụng chung. Điều này làm cho việc hỗ trợ các loại ứng dụng với các đặc tính lưu lượng và các yêu cầu QoS khác nhau trở nên phức tạp hơn, bên cạnh các vấn đề khác như cấp phát tài nguyên, cân bằng tải mạng, điều khiển tắc nghẽn... Các vấn đề này cần được xem xét toàn diện nhằm đảm bảo QoS cho dịch vụ trong môi trường mạng không đồng nhất, kết hợp nhiều công nghệ khác nhau và sự tương tác giữa các kiến trúc QoS khác nhau trên đường kết nối từ đầu cuối đến đầu cuối, từ nơi cung cấp dịch vụ đến nơi sử dụng dịch vụ. 1.1.2 Xây dựng ràng buộc liên quan đến đảm bảo chất lượng dịch vụ 1) Việc xây dựng hàm ràng buộc: Xây dựng hàm g(x1, x2, … xn), trong đó, n biến số x1, x2, … xn sẽ thay thế cho từng giá trị thông số QoS đơn. Gọi v1, v2, … vn là n giá trị thông số QoS yêu cầu của luồng thông tin truyền qua mạng. Gọi u1, u2, … un là n giá trị thông số QoS của tuyến truyền P trên mạng. Nếu g(u1, u2, … un) ≥ g(v1, v2, … vn) thì ta nói tuyến truyền P có khả năng đáp ứng dịch vụ cho luồng thông tin trên và ngược lại.
4 2) Việc so sánh trực tiếp tuần tự: Việc so sánh tuần tự từng thông số sẽ giúp việc đảm bảo chất lượng tốt hơn. Trong luận án có sử dụng kiểu so sánh tuần tự này để làm tiêu chuẩn chọn tuyến , cụ thể với tuyến truyền P và luồng tin f: Với kiểu so sánh tuần tự hai thông số băng thông và độ trễ thì luận án sử dụng thủ tục sau: PROCEDURE Compare(p,f) If p.Bandwidth ≥ f.Bandwidth If p.Delay ≤ f.Delay p is chosen Else p is discarded Else p is discarded ENDHình 1.3 Thủ tục so sánh tuần PROCEDURE tự hai thông số QoS Với kiểu so sánh ba thông số QoS là băng thông, độ trễ và tỷ lệ mất gói làm tiêu chuẩn chọn đường, luận án sử dụng thủ tục như sau: PROCEDURE Compare3(p,f) If p.Bandwidth ≥ f.Bandwidth If p.Delay ≤ f.Delay If p.PER
5 1.2 Kỹ thuật định tuyến đảm bảo chất lượng dịch vụ 1.2.1 Định tuyến đảm bảo QoS dùng thông tin toàn cục Trong định tuyến đảm bảo QoS dùng thông tin toàn cục (TTTC), việc tìm một tuyến truyền có khả năng đáp ứng được những yêu cầu của luồng dữ liệu cần có thông tin trạng thái của toàn mạng. Để thu thập và lưu trữ thông tin trạng thái của mạng, hệ thống cần phải thực hiện cập nhật thường xuyên, để giúp cho giao thức định tuyến tại các nút mạng thực hiện chính xác việc định tuyến trên mạng. 1.2.2 Định tuyến đảm bảo QoS dùng thông tin nội bộ 1.2.2.1 Đặc trưng Giải thuật định tuyến dùng thông tin nội bộ (TTNB) đều lấy thông tin thống kê tại nút mạng, tính toán, đưa ra quyết định định tuyến. Do đó, quyết định định tuyến chỉ phụ thuộc vào thông tin tại nút mạng mà thôi. Tại các nút mạng này, giải thuật xây dựng và duy trì một tập các tuyến truyền đến các nút đích trên mạng. Khi một luồng tin đến nút mạng, luồng tin được định tuyến theo một trong các tuyến truyền đã định sẵn đó. 1.2.2.2 So sánh giải thuật định tuyến đảm bảo QoS dùng TTNB với giải thuật định tuyến dùng TTTC Hình 1.9 So sánh định tuyến dùng TTTC và định tuyến dùng TTNB – Nguồn [38]
6 Theo đó, trong khi giải thuật định tuyến dùng thông tin toàn cục phải dựa vào bảng định tuyến được cập nhật thường xuyên để tính toán đường truyền (hình 1.9), thì giải thuật định tuyến dùng TTNB đã xây dựng và duy trì một tập hợp các tuyến truyền giữa nút nguồn đến tất cả các nút đích có trong mạng. Sau đó, giải thuật định tuyến định tuyến các luồng tin đến, theo thông tin thống kê từ việc truyền dữ liệugiữa các cặp nút này. 1.2.2.3 Một số giải thuật định tuyến đảm bảo QoS dựa vào thông tin nội bộ 1. Giải thuật PSR (Proportional Sticky Routing) [82]: PSR yêu cầu nút mạng nguồn xây dựng và duy trì một tập tuyến truyền ngắn nhất Rmin và tập tuyến truyền thay thế Ralt đến một đích cho trước. Dựa vào thống kê của việc chọn tuyến truyền tại nút mạng nguồn (như số luồng bị chặn, xác suất luồng bị chặn …) để phân bổ luồng dữ liệu đến một nút mạng đích trong tập các tuyến truyền thiết lập sẵn Rmin hay Ralt. 2. Giải thuật CBR (Localized Credit Based Routing) [75]: CBR cũng tương tự PSR yêu cầu nút nguồn xây dựng và duy trì một tập tuyến truyền ngắn nhất Rmin và tập tuyến truyền thay thế Ralt đến một đích cho trước, sau đó CBR tạo ra một tập tuyến truyền chung R, với: R = R min ∪ R alt . Bên cạnh đó, CBR sử dụng một thủ tục đơn giản để định tuyến luồng dữ liệu trên mạng bằng một hệ thống cho điểm cho mỗi tuyến truyền trong tập tuyến truyền R. Theo đó, CBR sẽ có chế độ thưởng phạt cụ thể cho mỗi tuyến truyền khi luồng dữ liệu được chấp nhận hay loại bỏ. 3. Các giải thuật định tuyến dùng TTNB khác:Các giải thuật định tuyến dùng TTNB đã góp phần làm giảm lượng tính
7 toán tại các nút mạng, đồng thời đảm bảo QoS đến từng luồng tin, theo từng yêu cầu của người dùng, nên có thể đáp ứng tốt các yêu cầu về QoS trong mạng viễn thông phát triển mạnh hiện nay. Tuy nhiên, các giải thuật này vẫn còn một số hạn chế cần khắc phục tương tự như các giải thuật đã khảo sát ở trên. 1.3 Kết luận chương Chương này đã trình bày tổng quan về vấn đề đảm bảo QoS trên mạng viễn thông, về định tuyến đảm bảo QoS, trong đó tập trung nghiên cứu giải thuật định tuyến đảm bảo QoS dùng TTNB, và các hạn chế cần khắc phục để từ đó, xác định các vấn đề cần được tiếp tục nghiên cứu, giải quyết và đề xuất các giải thuật mới, hiệu quả hơn. CHƯƠNG 2 CÁC PHƯƠNG PHÁP ĐÁNH GIÁ HIỆU NĂNG CÁC GIẢI THUẬT ĐỊNH TUYẾN TRÊN MẠNG 2.1 Mở đầu Việc đánh giá hiệu năng định tuyến nhằm để đánh giá và qua đó tối ưu hóa hoạt động của các giải thuật định tuyến, đồng thời với việc ứng dụng phần mềm mô phỏng, xác định cụ thể các tiêu chí liên quan cũng như đề xuất xây dựng một hệ số đánh giá hiệu năng định tuyến thực sự là công việc quan trọng trong quá trình xây dựng giải thuật định tuyến. 2.2 Các mô hình mạng ứng dụng để mô phỏng Các mô hình mạng (tô-pô mạng) trong các thí nghiệm mô phỏng được thiết kế phỏng theo mạng lõi (backbone) của các nhà cung cấp dịch vụ Internet (ISP) trên thế giới, được mô tả cụ thể và được ký hiệu thống nhất như trong bảng 2.1 sau:
8 Bảng 2.1 Các mô hình mạng trong các thí nghiệm mô phỏng Độ dài tuyến Được sử dụng Tên mô Số nút truyền trung bình trong các nghiên hình ISP mạng (theo bước nhảy) cứu ISP1 32 3,137 [35], [91] … ISP2 18 2,36 [19], [20], [40]… ISP3 9 1,81 [A.1],[A.3]… ISP4 60 5,812 [8], [87] … 2.3 Các tiêu chí đánh giá 2.3.1 Xác suất nghẽn Trong các nghiên cứu liên quan cũng như trong luận án sử dụng các thông số FBP và BBP với cách tính như sau: FBP = |B|/|T| (2.1) BBP = (băng thông của |B|)/(băng thông của |T|) (2.2) với FBP (Flow blocking probability) là xác suất nghẽn luồng và BBP (Bandwidth blocking probability) là xác suất nghẽn băng thông, với |T| là tổng số luồng và |B| là tổng số luồng bị nghẽn. 2.3.2 Độ trễ đầu cuối - đầu cuối: Việc tính toán giá trị trễ đầu cuối - đầu cuối là tham số quan trọng trong việc đánh giá hiệu quả định tuyến cũng như hiệu quả của mô hình mạng. 2.3.3 Cân bằng tải mạng: Các chỉ số đánh giá cân bằng tải được ứng dụng để đánh giá hiệu năng của giải thuật định tuyến như chỉ số Jain tại [72] và chỉ số DBM được mô tả chi tiết trong phần 2.4.
9 2.4 Xây dựng các hệ số đánh giá cân bằng tải mạng Để tính cân bằngtải băng thông của một mạng,luận án đề xuất một hệ số biểu diễn giá trị chênh lệch băng thông toàn mạng, là hàm số của tất cả giá trị băng thông các đường liên kết, hệ số sử dụng theo nút mạng xét trên một mạng đó, cụ thể là hệ số DBM (viết tắt của Differential Bandwidth Metric) được tính bằng công thức sau: 2 ∑N j=1∝j Qj (∑N j=1(∝j Qj −( )) ) √ N Bm 𝐃𝐁𝐌 = bm(N−1) N−1 (2.9) Giá trị DBM thu được tại (2.9) nói lên mức độ cân bằng tải băng thông, so với mức băng thông trung bình toàn mạng. 2.5 Việc ứng dụng hệ số DBMđể đánh giá hiệu năng giải thuật định tuyến Khi sự chênh lệch băng thông khác nhau sẽ dẫn đến giá trị DBM sẽ thay đổi. Với một giải thuật làm cho tải mạng phân bổ đều hơn sẽ có giá trị DBM thấp hơn. Điều này cho thấy rằng, một giải thuật định tuyến sẽ hiệu quả hơn khi chính nó làm cho việc chênh lệch băng thông thấp hơn, hay nói cách khác, một mạng sẽ cân bằng hơn khi mạng đó sử dụng giải thuật định tuyến hiệu quả hơn. 2.6 Kết luận chương Việc đánh giá đánh giá hiệu năng định tuyến và việc ứng dụng phần mềm mô phỏng OMNeT++, cùng với các tiêu chí đánh giá trực quan đã giúp cho việc nhanh chóng có thể so sánh và xây dựng các giải thuật định tuyến mới, hiệu quả hơn.
10 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Ộ 3.1 Mở đầu So với các giải thuật định tuyến dùng thông tin toàn cục (TTTC), các giải thuật định tuyến dùng thông tin tại nội bộ nút để định tuyến thông tin trên các tập tuyến truyền đã cólà một hướng đi mới được đánh giá là khá hiệu quả, giúp giảm tính toán tại các nút mạng,giảm xác suất nghẽn, và tăng hiệu năng của mạng so với các giải thuật định tuyến dùng TTTC. 3.2 Đề xuất giải thuật định tuyến dùng TTNB sử dụng băng thông và độ trễ làm tiêu chuẩn chọn đường 3.2.1. Mô tả giải thuật RBDA RBDA xác định trước và duy trì tại tất cả các nút mạng các tập các tuyến truyền đến tất cả các nút đích. Cụ thể, với mỗi cặp nút nguồn – đích, tại nút nguồn duy trì một tập R các tuyến truyền kết nối giữa hai nút đó. Mỗi tuyến truyền PiR liên kết với một biến Pi.Quality[1,2]=Pi.[Bandwidth,Delay], một chỉ số tuyến truyền Ci, và chỉ số Ni là tổng số luồng tin truyền trên tuyến truyền giữa cặp nút nguồn và đích đó. Khi luồng tin đến nút nguồn, RBDA chọn tuyến truyền Pi có giá trị {Ci,Ni}lớn nhất trong tập R đó, và kiểm tra yêu cầu về băng thông và độ trễ của luồng dữ liệu tới (gọi giá trị này là RQ).Nếu Pi.Quality ≥ RQ: Tuyến truyền Piđược lựa chọn để truyền thông tin đi (thủ tục so sánh như hình 1.3).Nếu Pi.Quality < RQ: RBDA chọn tuyến truyền tiếp theo của tập R, và vòng lặp sẽ được tiếp tục cho đến khi tìm ra được một tuyến truyền Pi có giá trị {Ci, Ni} lớn nhất và Pi.Quality≥RQ.Nếu không có tuyến truyền nào trong tập R thỏa mãn Pi.Quality ≥ RQ, thì luồng dữ liệu đến bị từ chối.
11 3.2.2. Mô phỏng đánh giá giải thuật định tuyến RBDA 3.2.2.1 Mô hình mô phỏng Luận án dùng trình mô phỏng OMNeT++, các mạng mô phỏng ISP1 và ISP2, được thiết lập như bảng 2.1. Các luồng dữ liệu trong cả hai mạng tuân theo luật Poisson với tỷ lệ λ; thời gian của mỗi luồng dữ liệu tuân theo quy luật phân bố hàm mũ với giá trị trung bình 1/μ = 60 giây, băng thông yêu cầu tuân theo quy luật phân bố uniformtrong khoảng [0.5-4MB], độ trễ yêu cầu phân bố ngẫu nhiên trong khoảng 20ms-250ms. 3.2.2.2 Kết quả mô phỏng: Hình 3.4 Xác suất nghẽn luồng trên ISP1 Hình 3.7 Xác suất nghẽn luồng trên ISP2 Hình 3.4 và 3.7 cho thấy sự khác nhau của các giải thuật chủ yếu khi tải tăng lên cao. Giải thuật RBDA do có cơ chế so sánh cũng như sử dụng chỉ số để thay đổi tuyến truyền khi nút mạng nghẽn, nên RBDA có giá trị tốt nhất. Từ hình 3.6 và 3.8, ta có thể thấy được rằng khi số lượng các luồng tin tăng lên, có thêm nhiều luồng tin trên mạng thì giá trị trễ đầu cuối- đầu cuối tăng lên, và giải thuật RBDA cho thấy đạt được hiệu năng tốt hơn.
12 Hình 3.6 Giá trị trễ đầu cuối trung bình khi thay đổi tải Hình 3.8 Giá trị trễ đầu cuối trung bình trên ISP2 3.2.3. Mô tả giải thuật BQRA BQRA cũng xây dựng các tập hợp R các tuyến truyền đến tất cả các nút đích. Mỗi tuyến truyền PiR cũng liên kết với một biến Pi.Quality=Pi.[Bandwidth,Delay] và một chỉ số tuyến truyền βi. Gọi BFi là số luồng bị nghẽn và Ti là tổng số luồng sử dụng tuyến truyền đó. Trong đó: βi = (1-BFi/Ti) (3.5) Khi luồng thông tin yêu cầu đến, BQRA chọn tuyến truyền Pi có giá trị βi lớn nhất trong tập R,kiểm tra yêu cầu về băng thông và độ trễ của luồng dữ liệu (gọi giá trị này là SLA). Nếu Pi.Quality ≥ SLA: Tuyến truyền Piđược lựa chọn để truyền thông tin đi.Nếu Pi.Quality < SLA: BQRA chọn đường truyền tiếp theo của tập R, và vòng lặp sẽ được tiếp tục cho đến khi tìm ra được một tuyến truyền Pi có giá trị βi cao nhất và Pi.Quality ≥ SLA.Nếu không có đường truyền nào trong tập R thỏa mãn Pi.Quality ≥ SLA, thì luồng dữ liệu đến bị từ chối.
13 3.2.4. Mô phỏng đánh giá giải thuật định tuyến BQRA 3.2.4.1. Môi trường mô phỏng Luận án dùng chương trình mô phỏng OMNeT++, các mạng mô phỏng ISP2 và ISP3, được thiết lập như bảng 2.1. Các luồng dữ liệu trong cả hai mạng tương tự với RBDA. 3.2.4.2. Kết quả mô phỏng: Hình 3.10 Các giá trị của DBMtrên mạng mô phỏng ISP2 Hình 3.12 Các giá trị của DBM trên mạng mô phỏng ISP3 Từ hình 3.10 và 3.12, khi tải cao, sự chênh lệch băng thông cao dẫn đến giá trị DBM sẽ cao tương ứng. Trong hai giải thuật khảo sát, BQRA có giá trị thấp hơn vì BQRA thay đổi tuyến truyền thường xuyên dựa trên tập tuyến truyền đã lập trước nên phân bổ tải tương đối đều hơn, nên có giá trị DBM thấp hơn. Từ hình 3.11 và 3.13, giải thuật BQRA đạt có kết quả tốt hơn, do BQRA thay đổi tuyến truyền thường xuyên dựa vào chỉ số βi,nên khi nghẽn xảy ra, chỉ số βicủa tuyến truyền giảm xuống, và giải thuật sẽ thay đổi tuyến truyền. Vì thế, giá trị trễ trung bình toàn mạng của BQRA sẽ tốt hơn trường hợp WSP.
14 Hình 3.11 Giá trị trễ đầu cuối trung bình trên ISP2 Hình 3.13 Giá trị trễ đầu cuối trung bình trên ISP3 3.3 Đề xuất giải thuật định tuyến dùng TTNB sử dụng nhiều thông số QoS làm tiêu chuẩn chọn đường 3.3.1 Mô tả giải thuật BDER: BDER cũng xây dựng tập R các tuyến truyền đến tất cả các nút đích. Mỗi tuyến truyền PiR liên kết với một biến Pi.Quality[1,2,3]=Pi.[Bandwidth,Delay,PER], một chỉ số tuyến truyền Ti, là tổng số luồng tin truyền trên tuyến truyền giữa cặp nút nguồn và đích đó.Gọi T là tổng số luồng tin yêu cầu từ nút nguồn đến nút đích. Khi luồng tin đến nút nguồn, BDER chọn tuyến truyền Pi có giá trị (Ti/T) lớn nhất trong tập R, kiểm tra yêu cầu về các giá trị QoS của luồng dữ liệu tới (gọi là RQ). Nếu Pi.Quality ≥ RQ thìtuyến truyền Pi được lựa chọn để truyền thông tin đi.Nếu Pi.Quality < RQ: BDER chọn đường truyền tiếp theo của tập R,
15 và vòng lặp sẽ được tiếp tục cho đến khi tìm ra được một tuyến truyền Pi có giá trị (Ti/T) cao nhất và Pi.Quality≥RQ.(thủ tục so sánh như hình 1.4).Nếu không có tuyến truyền trong tập R thỏa mãn Pi.Quality ≥ RQ, thì luồng dữ liệu đến bị từ chối. 3.3.2 Mô phỏng đánh giá giải thuật định tuyến BDER 3.3.2.1 Mô hình mô phỏng Luận án dùng chương trình mô phỏng OMNeT++, các mạng mô phỏng ISP1 và ISP4, được thiết lập như bảng 2.1. Các luồng dữ liệu trong cả hai mạng tương tự với RBDA, với tỷ lệ mất gói yêu cầu là 1,0E-3. 3.3.2.2 Kết quả mô phỏng: Hình 3.17 cho thấy khi tăng tải tăng cao số lượng luồng tin đến các nút tăng lên, do đó, xác suất nghẽn luồng bắt đầu tăng cao. Với chỉ số Ti các tuyến truyền giúp tránh nghẽn khi nhiều luồng dữ liệu đến nút nguồn, nên xác suất nghẽn luồng của BDER tương đối thấp hơn các giải thuật khác tương ứng. Hình 3.17 Xác suất nghẽn luồng Hình 3.18 và 3.20 cho thấy giải thuật BDER đạt được hiệu năng tốt hơn, vì với giải thuật BDER, do các luồng tin thay đổi tuyến truyền thường xuyên hơn dựa vào chỉ số T i, nên khi nghẽn xảy ra, chỉ số của tuyến truyền giảm xuống, và tuyến truyền khác có chỉ số Ti cao hơn sẽ thay thế, và giúp tăng hiệu năng định tuyến.
16 Hình 3.18 Giá trị trễ đầu cuối trung bình khi tải  = 0,8 (ISP1) Hình 3.20 Giá trị trễ đầu cuối trung bình khi tải  = 0,8 (ISP4) Hình 3.21 mô tả khảo sát về lưu lượng truyền loạt với dòng lưu lượng Weibull với hệ số 0,4, trên mạng mô phỏng ISP4.Khi tải tăng cao, do BDER sử dụng tập các tuyến truyền đã lập sẵn, cùng chỉ số tuyến truyền thay đổi liên tục giúp cho BDER có giá trị xác suất nghẽn tốt nhất như trên hình. Hình 3.21 Ảnh hưởng của lưu lượng truyền loạt 3.4 Độ phức tạp tính toán của các giải thuật Độ phức tạp tính toán của giải thuật định tuyến QoS toàn cụclà O(NlogN+L), với N là số nút mạng, và L là số đường liên kết. Các giải thuật như RBDA, BQRA, BDERchỉ chọn đường trong một tập R có sẵn, nên độ phức tạp là O(|R|), với |R| chính là kích thước của tập R, và thời gian cập nhật thông tin là O(1), ít hơn nhiều so với các giải thuật định tuyến toàn cục.
17 3.5 Kết luận chương Chương này đã đề xuất các giải thuật định tuyến dùng TTNB với nhiều thông số QoS làm ràng buộc,thực hiện nhiều thí nghiệm mô phỏngcho thấy kết quả tốt hơn của các giải thuật đề xuất, đồng thời vớigiảm thiểu tính toán tại các nút mạng. 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 TTNB 4.1. Mở đầu Để cải thiện hơn nữa hiệu năng cho các giải thuật định tuyến dùng TTNB, chương này đề xuất các biện pháp như sau: Xây dựng và ứng dụng tập tuyến truyền linh động (DPS)tại các nút mạng, và Ứng dụng kiểu định tuyến phân tán trong xây dựng giải thuật định tuyến dùng TTNB. 4.2. Đề xuất tập tuyến truyền linh động 4.2.1. Giới thiệu Tập tuyến truyền linh động sẽ làm cho giải thuật linh động hơn vì tập tuyến truyền linh động cho phép mở rộng tập tuyến truyền, có nghĩa là tăng số lượng tuyến truyền trong tập tuyến truyền và do đó mang lại hiệu quả tốt hơn cho giải thuật, cụ thể là làm cho tải thông tin được chuyển đến nhiều liên kết hơn. 4.2.2. 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 4.2.2.1 Môi trường mô phỏng Luận án dùng chương trình mô phỏng OMNeT++, trênmô hình ISP1 được thiết lập như bảng 2.1. Các luồng dữ liệu tuân theo luật Poisson với tỷ lệ λ; thời gian của mỗi luồng tuân theo quy luật phân bố hàm mũ với giá trị trung bình 1/μ = 60 giây,
18 băng thông yêu cầu tuân theo quy luật phân bố uniformtrong khoảng [0.5-4MB]. 4.2.2.2 Giải thuật định tuyến dùng để mô phỏng Để đánh giá hiệu năng của tập tuyến truyền linh động với giải thuật đảm bảo QoS dùng TTNB, ta sử dụng giải thuật định tuyến Localized Bandwidth-Constraint Routing hay LBCR. 4.2.2.3 Kết quả mô phỏng Hình 4.2 Xác suất nghẽn luồng Từ hình 4.2, khi khi tải  tăng cao, LBCR có giá trị tương đối tốt hơndocác tuyến truyền lấy trên duy nhất một tập hợp tuyến truyền đã chọn sẵn, nên việc tránh nghẽn xảy ra trên mạng được thực hiện tương đối tốt hơn. Giá trị bước nhảy trung bình (AHC)khi sử dụng DPS sẽ cao hơn tại mức tải cao, do hiện tượng nghẽn xảy ra thường xuyên hơn làm cho giải thuật định tuyến tái lập lạinhiều lần vàlàm thay đổi của độ dài tuyến truyền cũng như làm tăng AHC. Hình 4.5 Giá trị số bước nhảy trung bình khi  = 0,8