Luận án Đề 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ộ - Trần Minh Anh

số DBM có thể dùng để hoạch định mạng thông qua việc đánh giá hiệu năng của giải thuật định tuyến sử dụng trên mạng đó. 2.6 Kết luận chương Việc đánh giá và xây dựng phương pháp đánh giá hiệu năng định tuyến sẽ hỗ trợ cho việc xây dựng các giải thuật định tuyến hiệu quả, đáp ứng tốt nhu cầu của thực tế. 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. Đồng thời, việc đề xuất hệ số DBM về mặt học thuật cũng là công cụ để đánh giá hiệu năng của các công cụ định tuyến, hiệu năng của việc thiết kế mô hình mạng của mạng viễn thông. Trên cơ sở đó, có thể điều chỉnh để tối ưu hóa mạng viễn thông nhằm đạt hiệu quả cao nhất. Các đóng góp đề xuất của luận án trong chương này là các công trình như [A.1], [A.3], [A.9] và [B.7] đã được đăng tại các Hội nghị khoa học và tạp chí chuyên ngành. 52 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Ộ Ngày nay, yêu cầu về chất lượng dịch vụ (QoS) ngày càng trở nên quan trọngvà phổ biến trong việc cung cấp dịch vụ viễn thông cho người dùng.Bên cạnh các giải thuật định tuyến đảm bảo chất lượng QoS dùng thông tin toàn cục, việc sử dụng các kiểu giải thuật định tuyến chỉ dùng thông tin tại nội bộ nút để định tuyến thông tin đã và đang được nghiên cứu nhiều hiện nay, như là một giải pháp bổ trợ quan trọng trong bối cảnh mạng viễn thông phát triển bùng nổ hiện nay. Chương này đề xuất các giải thuật định tuyến dùng thông tin nội bộ (TTNB) với các thông số QoS là tiêu chuẩn chọn đường, cùng các thí nghiệm mô phỏng, so sánh với các giải thuật định tuyến đã có theo các tiêu chí như chương 2 đã đề cập như xác suất nghẽn, độ trễ đầu cuối – đầu cuối Cấu trúc của chương như sau: Phần 3.1 trình bày những vấn đề chung trong việc xây dựng giải thuật định tuyến dùng TTNB. Phần 3.2 trình bày về các nghiên cứu liên quan. Phần 3.3 và 3.4 đề xuất các giải thuật định tuyến, và các thí nghiệm mô phỏng, cũng như phân tích kết quả mô phỏng với các nghiên cứu đã có. Phần 3.5 nêu thời gian tính toántại các nút mạng. Phần 3.6 trình bày các kết luận của chương. 3.1 Mở đầu Như chương 1 đã đề cập, cùng với sự phát triển mạnh mẽ của ngành viễn thông hiện nay, các nhu cầu lưu lượng 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. Các dịch vụ càng cao cấp, lại càng yêu cầu khắt khe hơn về chất lượng tuyến truyền, chất lượng của dịch vụ.Kỹ thuật định tuyến đảm bảo QoS là một phương cách để thỏa mãn yêu cầu này, đồng thời đảm bảo tối ưu hóa việc sử dụng tài nguyên mạng. Trong các kỹ thuật định tuyến, các giải thuật định tuyến dùng thông tin toàn cục (TTTC) phải thu thập và cập nhật liên tục thông tin trạng thái toàn mạng để từ đó quyết định định tuyến. Cách thức này khi áp dụng với các mạng có số lượng nút mạng tăng đột biến, yêu cầu cao về QoS 53 thì rất không hiệu quả, hay gây nghẽn mạng do phải chịu tải tính toán tuyến truyền cao tại các nút mạng, việc cập nhật thông tin toàn mạng không kịp thời, không chính xác Để giải quyết các nhược điểm trên, giải thuật định tuyến trong đó nút mạng xây dựng trước các tập tuyến truyền, thu thập các thông tin tại nội bộ nút như xác suất nghẽn, thống kê thông tin gói tin, luồng tin để đưa ra quyết định định tuyến thông tin trên các tập tuyến truyền đã có,đến các nút trong mạng là một hướng đi mới được đánh giá là khá hiệu quả. Mô hình này giúp giảm xác suất nghẽn toàn mạng, giảm lượng tính toán tại các nút mạng đồng thời tăng hiệu năng của mạng so với các mô hình định tuyến dùng TTTC. Chương này đề xuất các giải thuật định tuyến mới, trong đó sử dụng các thông số QoS như băng thông, độ trễ hay tỷ lệ mất gói là tiêu chuẩn chọn tuyến truyền. Trong các thí nghiệm mô phỏng, luận án so sánh kết quả mô phỏng với các giải thuật định tuyến dùng TTNB khác như đã khảo sát ở chương 1 và qua đó đánh giá được hiệu năng tốt hơn của các giải thuật đề xuất khi thực hiện trên cùng một môi trường mô phỏng. 3.2 Các nghiên cứu liên quan Trong chương này, luận án có sử dụng các giải thuật định tuyến liên quan như đã khảo sát trong chương 1 như các giải thuật WSP, CBR, PSR để so sánh và đánh giá hiệu năng của các giải thuật đề xuất. Cụ thể, luận án so sánh các giải thuật đề xuất với các giải thuậtdùng TTTC và các giải thuật định tuyến dùng TTNB ở các tiêu chí như xác suất nghẽn luồng, nghẽn băng thông,giá trị trễ đầu cuối - đầu cuối, Qua đó, luận án có những kết luận đánh giá đối với từng giải thuật cụ thể. Trong các giải thuật định tuyến QoS dùng TTTC, luận án so sánh với giải thuật phổ biến hiện nay là WSP (tìm đường ngắn nhất rộng nhất), như mô tả trong chương 1 và trong các nghiên cứu [39], [57], [67]. Trong các giải thuật định tuyến dùng TTNB, luận án khảo sát và so sánh với các giải thuật như LDCR [36], CBR [75], PSR [83], HMB [91], Tất cả các giải thuật khi so sánh với giải thuật đề xuất đều được thực hiện trên cùng một môi trường mô phỏng, cùng với các mô tả về thông số mô phỏng như nhau. 54 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 3.3.1. Giới thiệu Các giải thuật định tuyến đảm bảo QoS chọn tuyến truyền với các tài nguyên mạng đủ đáp ứng các yêu cầu QoS của luồng tin, đồng thời các giải thuật định tuyến đảm bảo QoS cũng dung hòa giữa sử dụng tài nguyên mạng và cân bằng tải mạng để đạt được hiệu quả định tuyến cao nhất. Các yêu cầu về QoS của một luồng tin bao gồm một tập các ràng buộc mà các giải thuật định tuyến phải đáp ứng để tìm ra một tuyến truyền khả dĩ để truyền thông tin đi đến nút đích. Các giải thuật định tuyến thường sử dụng một hay nhiều thông số QoS để làm tiêu chuẩn chọn tuyến truyền. Trong các thông số QoS, băng thông và độ trễ là hai thông số phổ biến nhất trong các dịch vụ viễn thông hiện nay như trong chương 1 đã phân tích. Do đó, trong phần 3.3 này, luận án đề xuấthaigiải thuật định tuyến đảm bảo QoS lấy băng thông và độ trễ làm tiêu chuẩn chọn đường, cụ thể: 1. Giải thuật sử dụng tỷ lệ luồng truyền thành công làm chỉ số tuyến truyền là: “QoS Routing using Bandwidth-Delay based Algorithm” hay RBDA. 2. Giải thuật sử dụng tỷ lệ luồng nghẽn làm chỉ số tuyến truyềnlà: “Bandwidth-Delay Constraint QoS Routing Algorithm” hay BQRA. 3.3.2. Mô tả giải thuật RBDA Tương tự các giải thuật định tuyến dùng TTNB khác, RBDA cũng 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 đó. Không giống như các giải thuật định tuyến dùng TTNB khảo sát ở phần trên như CBR hay PSR,giữa mỗi cặp nút, giải thuật RBDA chỉ sử dụng duy nhất một tập tuyến truyền R (kết quả của việc tìm đường ngắn nhất) mà thôi. 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 đó. Cách tính toán giá trị Ci và Ni được đề cập ở phần sau. Và để chọn đường, tập tuyến truyền R được sắp xếp theo giá trị của Ci, và Ni theo thứ tự giá trị lớn nhất của Ci gọi là max(Ci), và giá trị nhỏ nhất của Ni gọi là min(Ni). Ta gọi thủ tục sắp xếp tập R như trên là max{Ci,Ni}. 55 3.3.2.1 Quá trình định tuyến: Với mỗi luồng thông tin yêu cầu đến nút nguồn, RBDA sắp xếp tập R theo giá trị của max{Ci,Ni}. Sau đó, chọn tuyến truyền Pi có giá trị {Ci,Ni}lớn nhất trong tập R đó. Tiếp theo, RBDA kiểm tra yêu cầu về băng thông và độ trễ của luồng dữ liệu tới từ thông số SLA (thỏa thuận mức chất lượng giữa mạng và người sử dụng [32]) của luồng dữ liệu. Ta gọi giá trị này là RQ.[Bandwidth,Delay] hay đơn giản là RQ, và lấy giá trị này để so sánh chọn đường. Nếu như luồng tin không có yêu cầu về thông số QoS, luồng tin đầu tiên của tập R sẽ được truyền. Nếu có yêu cầu về thông số QoS, thì RBDA sẽ tiến hành so sánh Pi.Quality[1,2] với RQ, cụ thể: Theo đó, nếu Pi.Quality ≥ RQ: Tuyến truyền được lựa chọn để truyền thông tin đi (thủ tục so sánh như đề cập ở chương 1, 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 cao nhất (với giá trị Ni thấp nhất nếu có giá trị Ci bằng nhau) 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 (do không có đường nào thỏa mãn yêu cầu chất lượng của luồng dữ liệu). Ta thấy, RBDA chỉ thay đổi chỉ số tuyến truyền tương ứng với khả năng truyền tải dữ liệu của tuyến truyền đã chọn, cụ thể: RBDA tăng Ci, Ninếu luồng tin qua Pi đến được nút đích, giảm Ci, giữ Ni nếu không truyền được. Cụ thể cách tính Ci, Ni như sau: Ci được đặt là S, và giá trị Ni được đặt là 0. Khi tuyến truyền được chọn và giá trị Pi.Quality[Bandwidth, Delay] của tuyến truyền lớn hơn giá trị RQ, điều này chỉ dấu rằng tuyến truyền được chọn có đủ chất lượng và các giá trị Ci, Ni đều tăng lên 1, theo công thức sau: Ci = (Last Ci + 1) (3.1) (Ci≤ S, nếu sau công thức (2.1), Ci>S thì Ci bị đặt lại là S) Ni = (Ni + 1) (3.2) Khi tuyến truyền không được chọn (khi Pi.Quality < RQ) hay bị từ chối, thì: Ci = (Last Ci – 1) (3.3) (Ci≥ 1, nếu Ci nhỏ hơn 1, Ci lại được đặt là 1) 56 Trong đó, S là một thông số hệ thống được cài đặt trước, tùy thuộc vào khả năng của mạng. Còn giá trị Last Ci là giá trị của Ci trước khi luồng tin đến với nút nguồn, Ni là số luồng tin được chấp nhận truyền trên tuyến truyền đó. Sau đó, luồng tin tiếp theo sẽ sử dụng các giá trị của {Ci, Ni} làm tiêu chuẩn chọn tuyến truyền và vòng lặp lại tiếp tục như vậy. Vì thế giá trị của {Ci, Ni} sẽ phản ảnh xác suất được lựa chọn của tuyến truyền cho luồng tin tiếp theo. Giá trị S phụ thuộc vào khả năng của mạng, thường ta đặt S = 1015 cho mạng có từ 18-60 nút (như trong mô phỏng ở phần sau). Giá trị S này nhằm để giới hạn sử dụng một tuyến truyền nào đó trong tập tuyến truyền. Vì nếu để một tuyến truyền nào đó trong tập tuyến truyền có giá trị Ci quá lớn, đến khi tuyến truyền đó bị nghẽn, thì do giá trị Ci trên vẫn còn cao, RBDA sẽ dùng giá trị này so sánh và tuyến truyền trên sẽ lại được chọn. Do đó, với giá trị chặn trên S (ta luôn có: Ci≤ S), đảm bảo việc sử dụng đồng đều hơn các tuyến truyền trong tập tuyến truyền tại nút nguồn. 3.3.2.2 Lưu đồ của giải thuật: Từ các bước mô tả ở trên, ta có lưu đồ giải thuật như sau: Hình 3.1 Lưu đồ hoạt động của RBDA 57 Theo các bước như trên, RBDA chỉ thay đổi các chỉ số Ci, Nicủa tuyến truyền, và các giá trị của Ci, Niđược dùng để so sánh giữa các tuyến truyền. Nếu tuyến truyền có tỷ số cao hơn, có nghĩa là nó có tiềm năng hơn, và nó sẽ được chọn cho luồng thông tin tiếp theo. Cho nên, sau khi truyền một luồng thông tin, RBDA cập nhật giá trị Ci, Ni, và sử dụng nó để chọn đường cho luồng kế tiếp. 3.3.2.3 Mã giả ngẫu nhiên của giải thuật RBDA: Hình 3.2Mã giả ngẫu nhiên của RBDA 3.3.3. Mô phỏng đánh giá hiệu năng giải thuật định tuyến RBDA Trong phần này, luận án sẽ mô phỏng giải thuật RBDA và so sánh kết quả với các giải thuật đã mô tả ở chương 1 như WSP, CBR và PSR. Các kết quả đánh giá sẽ được nêu ở phần sau. 3.3.3.1 Mô hình mô phỏng Luận án dùng chương trình mô phỏng OMNeT++ [22], thu thập kết quả như giới thiệu trong phần 2.2.4. Các mô hình mô phỏng (tô-pô mạng) được phỏng theo Initialize Building R Set S=15 Set Ci=SPiR Set Ni=0, RBDA 1. Range max{Ci,Ni} for flow-in 2. Set P.success = false; 3. Get RQ from flow-in 4. P=first(Pi.(Ci,Ni): PiR) 5. While !(P.success or R(end)) 6. if(P.Quality≥RQ) 7. Route flow along path P 8. if P is accepted 9. {Compute Pi.(Ci,Ni) (increase Ci(≤S), Ni) 10. P.success=true} 11. elseif { 12. P= next(Pi.(Ci,Ni): PiR) 13. Compute Pi.Ci (decrease Ci(≥1)) 14. endif} 15. ElseIf 16. P= next(Pi.(Ci,Ni): PiR) 17. Compute Pi.Ci (decrease Ci(≥1)) 18. Endif 19. Endwhile 20. END. 58 các mạng lõi của các ISP trên thế giới, và đã được sử dụng trong các nghiên cứu liên quan. Với mô phỏng trong phần này, Luận án sử dụng hai mô hình mạng là các mạng lõi của các ISP được dùng trong các nghiên cứu [39], [40], [82], [83], [92] như giới thiệu ở mục 2.2,cụ thể: Mạng mô phỏng 32 nút (hình 3.3), gọi là mạng ISP1, được thiết lập như sau: các liên kết là song hướng với cùng một dung lượng C (C=150Mbps) và một độ trễ là D (D=10ms) trên mỗi hướng; số liên kết là 108 liên kết, độ dài trung bình của một tuyến truyền trên mạng (tính theo số bước nhảy) là 3,137. Mạng mô phỏng 18 nút (hình 3.3), gọi là mạng ISP2, được thiết lập như sau: các liên kết là song hướng với cùng một dung lượng C (C=20Mbps) và một độ trễ là D (D=20ms) trên mỗi hướng; số liên kết là 60 liên kết, độ dài trung bình của một tuyến truyền trên mạng (tính theo số bước nhảy) là 2,36. Các luồng dữ liệu đến các nút nguồn trong cả hai mạng tuân theo luật Poisson với tốc độλ và các nút đích được chọn lựa ngẫu nhiên (mỗi nút đều có thể là nút nguồn, cũng như nút đích); thời gian giữ 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 của mỗi luồng tuân theo quy luật phân bố uniform với giá trị trong khoảng [0.5-4MB], độ trễ yêu cầu của mỗi luồng tuân theo quy luật phân bố uniform với giá trịtrong khoảng 20ms-250ms. Theo tính toán tại [19], [20], tải trung bình toàn mạng được tính theo công thức: bwh/LC (3.4) với N là số nút, bw là giá trị băng thông trung bình yêu cầu bởi một luồng dữ liệu, h là độ dài trung bình của một tuyến truyền trên mạng (tính theo số bước nhảy) và L là số liên kết trên mạng. Vì việc hoạt động của các giải thuật định tuyến thay đổi tùy theo các điều kiện tải khác nhau, nên trong các thí nghiệm, giải thuật đã được thực hiện với nhiều loại tải từ thấp đến cao qua giá trị thông số λ từ thấp đến cao tương ứng. 59 Hình 3.3Các mạng mô phỏng có 32 nút (ISP1) và 18 nút (ISP2) 3.3.3.2 Các tiêu chí đánh giá: Để so sánh kết quả giữa các giải thuật, ta chọn các giá trị xác suất nghẽn luồng và xác suất nghẽn băng thông là các tiêu chí so sánh tương tự như các thí nghiệm mô phỏng tại [75], [83], được mô tả ở phần 2.3, theo các công thức (2.1) và (2.2). Các giá trị xác suất trên được tính dựa trên giá trị thu thập của 100.000 luồng liên tục sau hơn 2,5 triệu luồng dữ liệu đã phát sinh. Ngoài ra, luận án cũng tính giá trị trễ đầu cuối – đầu cuối trên toàn mạng củagiải thuật RBDA để so sánh với WSP khi mô phỏng ở tải thấp đến tải cao. 3.3.3.3 Kết quả mô phỏng: a. Trên mạng mô phỏng ISP1: Với các kết quả từ các thí nghiệm mô phỏng, ta thu thậpdữ liệu về xác suất nghẽn luồng của RBDA và so sánh với giá trị xác suất nghẽn luồng của các giải thuật khác, như trên hình 3.4. Hình 3.4 Xác suất nghẽn luồng trên ISP1 60 Hình 3.4 mô tả kết quả xác suất nghẽn luồng của giải thuật RBDA so sánh với các giải thuật khác như CBR, PSR và WSP với giá trị thu thậpxác suất nghẽn luồng khi tải  thay đổi giữa 0,2 và 0,5. Qua hình trên ta thấy được sự khác nhau của các giải thuật chủ yếu khi tải tăng lên cao. Điều này dễ hiểu là vì khi tải tăng cao, thì các nút mạng mới trở nên nghẽn, và các luồng tin mới sắp hàng chờ nhiều tại các nút. Do có so sánh thời gian trễ, nên nhiều gói tin đã bị loại bỏ khi không thỏa mãn phép so sánh tuần tự như đã đề cập ở phần trên. Giải thuật định tuyến đã đề xuấ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 dễ dàng thấy là RBDA có giá trị tốt nhất. Giải thuậtWSP có giá trị cao nhất với lý do là giải thuật cứ căn cứ vào giá trị thông tin toàn mạng tìm được, sử dụng thuật toán tìm đường, và tìm đường ngắn nhất, và thực hiện điều này đến khi gây nghẽn. Do đó, WSP có giá trị xác suất nghẽn luồng cao nhất. Khi tải  tăng cao, nhiều luồng dữ liệu bị nghẽn dẫn đến xác suất nghẽn luồng bắt đầu tăng cao, kéo theo xác suất nghẽn băng thông theo lên theo như mô tả ở hình 3.5. Do RBDA đã xây dựng và sử dụng tập tuyến truyền để định tuyến thông tin, nên khi có nghẽn xảy ra, chỉ số tuyến truyền thay đổi, và giải thuật thay đổi tuyến truyền, dẫn đến xác suất nghẽn luồng thấp hơn, và chỉ số tuyến truyền này lại tiếp tục được sử dụng để định tuyến tiếp từ đó, giải thuật có xác suất nghẽn thấp nhất như các hình 3.4 và 3.5. Hình 3.5 Xác suất nghẽn băng thông trên ISP1 61 Trong thí nghiệm mô phỏng tiếp theo, ta lấy thông tin về thông số trễ đầu cuối-đầu cuối với các dạng tải thông tin thay đổi (với tải  = 0,2 đến 0,8). Tính toán và so sánh kết quả giữa giải thuật RBDA và WSP, kết quả như biểu diễn ở hình 3.6. Từ hình 3.6, 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. Hình 3.6 Giá trị trễ đầu cuối trung bình khi thay đổi tải Sự chênh lệch giữa hai giải thuật là tương đối bé khi  = 0,2, nhưng khi tải lớn hơn > 0,4, mức chênh lệch giữa hai giải thuật sẽ cao hơn như hình biểu diễn.Nghĩa là khi với tải cao hơn thì nghẽn xảy ra thường xuyên hơn, vì thế giá trị này cao hơn. Trong trường hợp của giải thuật RBDA, do các luồng tin thay đổi tuyến truyền thường xuyên hơn dựa vào chỉ số Ci, Ni, 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ố (Ci, Ni) cao hơn sẽ thay thế. Vì thế, giá trị trễ trung bình toàn mạng của RBDA sẽ tốt hơn trường hợp WSP. b. Trên mạng mô phỏng ISP2: Hình 3.7 Xác suất nghẽn luồng trên ISP2 62 Hình 3.7 mô tả xác suất nghẽn luồng của giải thuật RBDA so sánh với các giải thuật khác như CBR, PSR và WSP trên mô hình ISP2. Tương tự như ở mô hình ISP1, sự khác nhau của các giải thuật chủ yếu khi tải tăng lên cao. Bởi vì khi tải tăng cao (> 0,3), các nút mạng trở nên nghẽn làm cho xác suất nghẽn tăng lên như hình mô tả. RBDA sử dụng chỉ số để thay đổi tuyến truyền khi nút mạng nghẽn, nên khi nghẽn xảy ra, RBDA thay đổi tuyến truyền và hạn chế sử dụng tuyến truyền đã gây nghẽn nên có giá trị tốt nhất. Giải thuật WSPcó giá trị cao nhất với lý do là giải thuật cứ căn cứ vào giá trị thông tin toàn mạng tìm được, sử dụng thuật toán tìm đường, và tìm đường ngắn nhất, và thực hiện điều này đến khi gây nghẽn. Do đó, WSP có giá trị nghẽn luồng cao nhất. Trong các thí nghiệm tiếp theo, luận án thu thập dữ liệu về thông số trễ đầu cuối - đầu cuối với các dạng tải thông tin thay đổi (với tải  = 0,2 và 0,5). Tính toán và so sánh kết quả giữa giải thuật RBDA và WSP, kết quả như biểu diễn ở hình 3.8. Hình 3.8 Giá trị trễ đầu cuối trung bình khi tải cao và thấp trên ISP2 Từ hình 3.8, ta có thể thấy được rằng khi số lượng các luồng tin tăng lên, 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. Sự chênh lệch giữa hai giải thuật là tương đối bé khi  = 0,2, nhưng khi tải  = 0,5, mức chênh lệch giữa hai giải thuật sẽ cao hơn như hình biểu diễn. Điều này là do khi tải cao thì nghẽn xảy ra thường xuyên hơn, vì thế giá trị này cao hơn. Trong trường hợp của giải thuật RBDA, tương tự với mô hình ISP1, do các 63 luồng tin thay đổi tuyến truyền thường xuyên hơn dựa vào chỉ số Ci, Ni. 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ố (Ci, Ni) cao hơn sẽ thay thế. Vì thế, giá trị trễ trung bình toàn mạng của RBDA sẽ tốt hơn trường hợp WSP. Tóm lại, với các kết quả mô phỏng như các phần trên, có thể thấy được giải thuật đề xuất RBDA có hiệu năng tốt hơn các trường hợp được khảo sát như trong các thí nghiệm mô phỏng. 3.3.4. Mô tả giải thuật BQRA Giống như giải thuật RBDA, BQRA cũng xác định trước và duy trì tại tất cả các nút mạ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. Khác với giải thuật RBDA, các giá trị βi liên quan đến tỷ lệ luồng bị nghẽn trong quá trình định tuyến.Gọi BFi là số luồng bị nghẽn trên tuyến truyền đó, và Ti là tổng số luồng sử dụng tuyến truyền đó. Trong đó: βi = (1-BFi/Ti) (3.5) Để chọn đường, tương tự giải thuật RBDA, tập R sẽ được sắp xếp theo giá trị của βi.Với mỗi luồng thông tin yêu cầu đến nút nguồn, BQRA chọn tuyến truyền Pi có giá trị βi lớn nhất trong tập R đó hay gọi tắt là max(βi). Tiếp theo, BQRA cũng kiểm tra yêu cầu về băng thông và độ trễ của luồng dữ liệu tới từ thông số SLA (thỏa thuận mức chất lượng giữa mạng và người sử dụng [32]) của luồng dữ liệu. Ta gọi giá trị này là SLA, và lấy giá trị này để so sánh chọn đường. Nếu không có yêu cầu về QoS cho luồng này, tuyến truyền Pi sẽ được chọn để truyền thông tin. Nếu có yêu cầu về QoS, BQRA so sánh Pi. Qualityvà SLA (cách so sánh tuần tự như mô tả ở thủ tục ở hình 1.3. Nếu Pi.Quality ≥ SLA: Tuyến truyền được lựa chọn để truyền thông tin đi. Nếu Pi.Quality < SLA: BQRA 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ị βi cao nhất và Pi.Quality ≥ SLA. 64 Nếu không có tuyến 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 (do không có đường nào thỏa mãn yêu cầu chất lượng của luồng dữ liệu), các chỉ số Ti, BFi sẽ tăng. Nếu truyền thành công một luồng đến đích, thì chỉ có giá trị Ti tăng thôi. Ta thấy, BQRA chỉ thay đổi chỉ số βi của tuyến truyền tương ứng với khả năng truyền tải dữ liệu của tuyến truyền đã chọn. Khi tuyến truyền truyền thành công, hay không thành công, giải thuật sẽ tăng hay giảm các giá trị Ti, BFi tương ứng, hay là tăng hay giám giá trị βi. Từ đó, giá trị βi quyết định khả năng chọn đường tiếp theo, trên các tuyến truyền qua nút nguồn đến nút đích trên mạng. Các mô tả khác về giải thuật BQRA tương tự giải thuật RBDA ở trên. 3.3.5. Mô phỏng đánh giá hiệu năng giải thuật định tuyến BQRA Trong phần này, giải thuật BQRA được mô phỏng, tính toán các giá trị cân bằng tải qua hệ số DBM và các giá trị độ trễ đầu cuối – đầu cuối khi thay đổi tải mạng, đồng thời so sánh với giải thuật định tuyến dùng thông tin toàn cục như WSP để xem xét tính cân bằng tải, trễ mạng khi ứng dụng các loại giải thuật định tuyến trên mạng mô phỏng. 3.3.5.1. Môi trường mô phỏng Phần mô phỏng này, luận án cũng sử dụng chương trình mô phỏng OMNeT++ [22] để đánh giá, so sánh kết quả như đối với giải thuật RBDA ở trên. Các mô hình mô phỏng trong phần này cũng là mạng lõi của các ISP, và đã được sử dụng trong các nghiên cứu liên quan như giới thiệu ở phần 2.2, cụ thể: Mạng mô phỏng ISP2 có 18 nút (hình 3.9), được thiết lập như sau: các liên kết là song hướng với cùng một dung lượng C (C=20Mbps) và một độ trễ là D (D=20ms) trên mỗi hướng; số liên kết là 60 liên kết, độ dài trung bình của một tuyến truyền trên mạng (tính theo số bước nhảy) là 2,36. Mạng mô phỏng ISP3 có 9 nút (hình 3.9), là hình mô phỏng một mạng lõi điều hành khu vực của VNPT, cũng là mạng được mô phỏng tính toán cân bằng tải trong phần phụ lục đính kèm, được thiết lập như sau: các liên kết là song hướng với cùng một dung lượng C (C=20Mbps) và một độ trễ là D (D=10ms) trên mỗi hướng; số 65 liên kết là 28 liên kết, độ dài trung bình của một tuyến truyền trên mạng (tính theo số bước nhảy) là 1,81. Các luồng dữ liệu đến các nút nguồn trong cả hai mạng tuân theo luật Poisson với tốc độλ và các nút đích được chọn lựa ngẫu nhiên (mỗi nút đều có thể là nút nguồn, cũng như nút đích); thời gian giữ 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 của mỗi luồng tuân theo quy luật phân bố uniform với giá trị trong khoảng [1-5MB], độ trễ yêu cầu của mỗi luồng tuân theo quy luật phân bố uniform với giá trị trong khoảng 20ms- 250ms. Theo công thức (3.4), tải trung bình toàn mạng được tính theo công thức với bwh/LC, với N là số nút, bw là giá trị băng thông trung bình yêu cầu bởi một luồng dữ liệu, h là độ dài trung bình của một tuyến truyền trên mạng (tính theo số bước nhảy) và L là số liên kết trên mạng. Tương tự với giải thuật RBDA, trong các thí nghiệm đã được thực hiện với nhiều loại tải từ thấp đến cao qua giá trị thông số λ từ thấp đến cao tương ứng. Hình 3.9 Các mạng mô phỏng có 18 nút (ISP2) và 9 nút (ISP3) 3.3.5.2. Các giá trị thu thập để đánh giá: Như giới thiệu của phần 2.4 và 2.5, để tính được giá trị cân bằng băng thông, phần này luận án sẽ thu thập các giá trị của băng thông còn lại trên các liên kết trên toàn mạng. Từ các dữ liệu này, luận án xây dựng ma trận kết nối liên quan đến giá trị băng thông