Luận văn Các cơ chế định tuyến QoS và thuật toán mở đường ngắn nhất đầu tiên (OSPF) mở rộng

k, thì kết nối được thiết lập. Nếu bất kỳ một router nào trên đường dẫn dự kiến không dự trữ băng thông đã yêu cầu, thì nó bắt đầu giai đoạn Xử lý thất bại bằng cách gửi một thông báo thất bại tới router hướng tới. Nếu một router nhận được một thông báo thất bại, thì nó giải phóng tài nguyên mà nó đã dành riêng cho kết nối và chuyển tiếp bản tin thất bại tới router hướng tới kế tiếp trên đường dẫn sử dụng mục vào )(cidnv trong bảng định tuyến. Đích đến gửi một ack chỉ cho thăm dò đầu tiên nó nhận được và loại bỏ tất cả các bản sao. Điều này bảo đảm rằng các tài nguyên được dành riêng chỉ theo một con đường. Một router không chuyển tiếp thăm dò nhiều hơn một lần. Điều này có nghĩa là con đường dự kiến được tìm thấy bằng thuật toán này sẽ được lặp tự do. Chúng ta phải giả sử rằng các bản tin điều khiển này không bao giờ giảm trong trường hợp tắc nghẽn. 2.3.4. Chuyển tiếp hai mức giới hạn Flooding (lan tràn) dựa trên phương pháp tìm ra một con đường dự kiến thông qua việc cạnh tranh giữa các thăm dò. Nếu tải trên mạng nhẹ, thì việc lan tràn các thăm dò trên tất cả các liên kết đủ điều kiện không phải là một ý tưởng hay. Thông thường, nó chỉ là đường dẫn đủ điều kiện ngắn nhất được ưa thích. Để chỉ đạo việc tìm kiếm dọc theo con đường ngắn nhất, một cách tiếp cận đã được đưa ra. Mỗi thăm dò được gán cho một tuổi. Tuổi của một thăm dò p được định nghĩa như là số chặng mà thăm dò đã đi qua. Ban đầu, age(p)=0. Bất cứ khi nào p tới một nút, trường tuổi tăng thêm 1. Để điều khiển việc tìm kiếm dọc theo con đường ngắn nhất, điều kiện chuyển tiếp thăm dò trên liên kết (i,j) tại nút i được sửa là: 50 LdpageBjibandwidthjilinkonconditionforward tj  )1)((),(),( , Với tjd , là khoảng ngắn nhất tính theo số chặng giữa nút j và đích t; L là một hằng số. Điều kiện chuyển tiếp có thể làm các nút tràn ngập các yêu cầu chỉ dọc theo các đường dẫn ngắn nhất. Kết quả này có ý nghĩa khi tải trên mạng nhẹ. Còn khi mạng trở lên nặng nề hơn, không chắc rằng phương pháp đường dẫn ngắn nhất sẽ thành công trong việc thiết lập một đường dẫn. Do đó, nếu không đường dẫn nào được thiết lập sử dụng tsdL , , nguồn sắp đặt một sự thử thứ hai cho kết nối khác với l . Flooding với l là tương đương flooding mò mẫm tới tất cả các nút thích hợp. Tương tự với phương pháp flooding giới hạn, chúng ta có thể vẫn có một phương pháp giới hạn cho chuyển tiếp sử dụng hai mức. Khái niệm của một nút thích hợp được chỉnh sửa một cách tương tự. Nếu i là nút hiện hành, thì một hàng xóm j là thích hợp nếu Bjibandwidth ),( và Lpaged tj  1)(, . Từ giờ trở đi ta quy ước, điều kiện “không bị giới hạn” sẽ nói đến chuyển tiếp thăm dò mà không giới hạn số chặng, trong khi “bị giới hạn” sẽ nói đến chuyển tiếp thăm dò với số chặng bị hạn chế. Tóm lại: Các giao thức định tuyến phổ biến hiện nay như RIP và OSPF luôn thực thi nhiều hoạt động như là: khám phá mạng và cập nhật, duy trì các bảng định tuyến. Để cân đối giữa độ chính xác trong tính toán định tuyến với lượng tăng tải khi cập nhật thông tin định tuyến, cần có chính sách cập nhật phù hợp. Cơ chế cập nhật thông tin định tuyến hiện tại đang sử dụng phổ biến là lan tràn (flooding) các thông báo kiểu như thông báo Hello. Chương 2 đã trình bày cơ chế cập nhật thông tin dùng để lập bảng định tuyến, trong đó mô tả một cơ chế cải tiến, gọi là phương pháp chuyển tiếp flooding hai mức giới hạn, nhằm cải thiện việc lan tràn thông tin định tuyến khi mở rộng các thuật toán trong giao thức OSPF cho định tuyến QoS. Các phân tích chất lượng của cơ chế này được trình bày ở cuối Chương 3, sau khi đã mô tả các mở rộng của OSPF cho định tuyến QoS. 51 CHƯƠNG 3 - OSPF MỞ RỘNG CHO ĐỊNH TUYẾN QoS 3.1. Mở rộng đảm bảo chất lượng dịch vụ cho OSPF [7]- [12] IP đã hỗ trợ cho năm kiểu dịch vụ (TOS) khác nhau cho việc phân phát datagram. Năm kiểu này là dịch vụ thông thường, chi phí thấp nhất, độ tin cậy lớn nhất, khả năng thông lưu lượng lớn nhất và trễ nhỏ nhất. Một ứng dụng quyết định TOS sẽ được đặt vào các datagram của nó bằng cách thiết lập trường TOS trong các phần đầu IP. Khi đó, các router có thể định tuyến các gói tin IP tới một đích chung thông qua các tuyến đường khác nhau theo TOS của chúng. Để đảm bảo khả năng tương thích theo chiều ngược, các router có thể thông báo các số liệu đặc trưng TOS trong các thông điệp thông báo trạng thái liên kết của chúng. Điều này tạo ra một cơ hội để kiểm tra định tuyến QoS như một phần mở rộng của các đặc tính TOS trong OSPF tiêu chuẩn. Các mở rộng định tuyến QoS cho OSPF dựa trên hai ý tưởng chính là: thứ nhất, các thông điệp thông báo trạng thái liên kết và cơ sở dữ kiệu topo (topology database) phải bao gồm thông tin tài nguyên mạng như băng thông khả dụng, và thứ hai, thuật toán tính toán tuyến đường phải lấy thông tin này vào tính toán. 3.1.1. Các khả năng tùy chọn QoS Các gói tin Hello OSPF, các gói tin dạng cơ sở dữ liệu và tất cả các thông điệp thông báo trạng thái liên kết đều bao gồm trường các tùy chọn OSPF, trường này cho phép các router OSPF hỗ trợ các khả năng tùy chọn, và thông báo mức độ khả năng của chúng tới các router khác. Với sự giúp đỡ của cơ chế này, các router của các mức độ khả năng khác nhau có thể giao tiếp trong một miền định tuyến OSPF. Tiêu chuẩn OSPF sử dụng để chỉ rõ các bit sau đây trong octet các tùy chọn OSPF: Bảng 3.1. Octet các tùy chọn OSPF * * DC EA N/P MC E T Bit có ý nghĩa ít nhất là bit T, bit được sử dụng cho việc chỉ ra khả năng định tuyến TOS mà ngày nay đã được loại bỏ. Tuy nhiên, như đã được đề cập trước đó, thông tin này có thể được chứa trong trường các tùy chọn cho sự tương thích theo chiều ngược. Bit T có thể được sử dụng như một chỉ thị về khả năng 52 QoS của router và được đổi tên là bit Q. Trong các gói tin Hello, bit này cho biết liệu router có khả năng hỗ trợ định tuyến QoS hay không. Khi bit này được thiết lập trong một router hoặc các liên kết cơ bản LSA, nó chỉ ra rằng gói tin chứa các trường QoS. Trong một mạng LSA, bit này cho biết liệu mạng mô tả trong thông báo có khả năng QoS hay không. Cách tiếp cận này cần được thực hiện một cách cẩn thận để bất cứ sự thực thi theo cách tiếp cận cũ nào cũng không bị xáo trộn. 3.1.2. Mã hóa tài nguyên khi TOS mở rộng Bởi vì các mở rộng QoS cho OSPF sẽ tương thích với các router OSPF phiên bản hai hiện có, nên các mở rộng trong các định dạng gói tin sẽ được định nghĩa với mục đích là hiểu, lờ đi, hoặc hiểu sai mức độ nhẹ bởi các router OSPF phiên bản hai. Việc mã hóa các metric QoS trong trường TOS làm cho nó có thể bắt chước tính năng mới này như khả năng TOS mở rộng. Những định nghĩa này đã bị coi nhẹ hoặc xem xét một cách không rõ ràng bởi các bộ định tuyến OSPF phiên bản hai. Thông qua việc sử dụng bit thứ năm trong trường TOS, có 32 tổ hợp khác nhau có sẵn cho các tài nguyên QoS. Kể từ khi trường TOS được định nghĩa là bốn bit dài, thì định nghĩa này không xung đột với các giá trị hiện có. Bởi vì một số việc triển khai không thể nạp tất cả các bit trong trường TOS vào tính toán, các giá trị của băng thông và độ trễ được ánh xạ lên “khả năng cho qua lưu lượng tối đa” và “độ trễ tối thiểu” nếu bit có ý nghĩa nhất được bỏ đi. Bảng 3.2 và 3.3 mô tả TOS và QoS trong OSPF. Bảng 3.2. Mã hóa các giá trị TOS RFC 1349 Mô tả thập phân Mô tả nhị phân Ghi chú 0 0000 Dịch vụ thông thường 2 0001 Giá cực tiểu 4 0010 Độ tin cậy lớn nhất 6 0011 8 0100 Thông lượng lớn nhất 10 0101 12 0110 14 0111 16 1000 Trễ nhỏ nhất 18 1001 53 20 1010 22 1011 24 1100 26 1101 28 1110 30 1111 Bảng 3.3. Mã hóa các giá trị QoS RFC 2676 Mô tả thập phân Mô tả nhị phân Ghi chú 32 10000 34 10001 36 10010 38 10011 40 10100 Băng thông 42 10101 44 10110 46 10111 48 11000 Trễ 50 11001 52 11010 54 11011 56 11100 58 11101 60 11110 62 11111 3.1.3. Mã hóa băng thông Bởi vì trường metric có trong gói tin OSPF thực sự chỉ cung cấp 16 bits để mã hóa băng thông, trong khi các liên kết có thể hỗ trợ băng thông lên tới Gbit/s đang dần trở thành hiện thực, nên sự biểu diễn tuyến tính số liệu nguồn tài nguyên khả dụng là không khả thi. Giải pháp mô tả trong RFC 2676 là thực hiện mã hóa theo luật mũ bằng cách sử dụng một cách thích hợp giá trị cơ số được lựa chọn ngầm định và một số lượng nhất định các bit cho việc mã hóa 54 phần hệ số và số mũ. Ở đây sử dụng con số 8 làm cơ số xây dựng một hệ thống số, ba bit ý nghĩa nhất dành riêng cho phần số mũ và 13 bit còn lại dành cho phần hệ số. Điều này cho phép so sánh đơn giản qua hai con số được mã hóa trong cùng một định dạng, và thường là hữu dụng trong suốt thời gian thực thi. Bảng sau chỉ ra các phạm vi băng thông khi sử dụng các số mũ khác nhau và độ chi tiết của việc lưu trữ có thể chấp nhận được. Bảng 3.4. Phạm vi của các giá trị mũ cho 13bit, dựa vào mã hóa 8 Giá trị mũ của x Phạm vi x8*)12( 13  Bước x8 0 8,191 1 1 65,528 8 2 524,224 64 3 4,193,792 512 4 33,550,336 4,096 5 268,402,688 32,768 6 2,147,221,504 262,144 7 17,177,772,032 2,097,152 Quy tắc mã hóa băng thông này có thể được hiểu là: miêu tả băng thông khả dụng trong trường 16 bit với 3 bit mũ đứng trước và 13 bit tiếp theo cho phần cơ số định trị. Vì vậy, mã hóa trên tạo thành một thông báo nhị phân có giá trị số từ 1 cho tới 1216  (việc mã hóa băng thông khả dụng theo cơ số 2). Điều này có đặc tính của việc thông báo một giá trị số cao hơn cho băng thông khả dụng thấp hơn. Khái niệm này khá hợp lý với khái niệm về chi phí. Mặc dù nó có vẻ hơi mô phạm để nhấn mạnh về đặc tính băng thông nhỏ được biểu diễn các giá trị cao hơn, nhưng bên cạnh đó nó cũng có tính nhất quán. Một router với một sự thực thi OSPF tồi có thể hiểu sai số liệu băng thông như chi phí thông thường cung cấp cho nó và tính toán các cây mở rộng với một thuật toán Dijkstra “thông thường”. Một ví dụ để có thể làm rõ những điều này: chúng ta hãy giả sử rằng một liên kết với băng thông sbytesGbits /1024/8 3 . Mã hóa của nó sẽ là 63 8*40961024  trong đó độ chi tiết (giãn cách thang) là 68 (xấp xỉ 260kByte/s). Việc miêu tả số nhị phân kết hợp sẽ là 1101 0000 0000 0000 hoặc 53248 . Chi phí băng thông của liên kết này, khi không dùng đến, là phần bù cơ số 2 của 55 biểu diễn nhị phân ở trên, nghĩa là, 0010 1111 1111 1111 tương ứng với một giá trị thập phân 16(2 1) 53248 12287   . Nếu chúng ta chỉ có 1600Mbits/s băng thông có sẵn trên liên kết, việc mã hóa băng thông này sẽ là 58*6400 , tương ứng với độ chi tiết thang là 58 (xấp xỉ 30kBytes/s), và có một biểu diễn nhị phân 1011 1001 0000 0000 hoặc giá trị thập phân 47360. Chi phí thông báo của liên kết với mức độ tải này là 0100 0110 1111 1111 hoặc 1817547360)12( 16  . Băng thông sẵn có trên liên kết càng ít thì chi phí càng nhiều. Ngoài ra cũng đạt được mục tiêu về độ chi tiết tốt hơn cho các liên kết với băng thông hẹp hơn. Tuy nhiên, cần lưu ý rằng các metric đưa ra trong các ví dụ trước đây phù hợp với giải pháp của mã hóa đã được đề xuất, thứ sẽ không phải luôn luôn có trong cuộc sống thực. Tiêu chuẩn thông thường là làm tròn giá trị băng thông khả dụng đến con số gần nhất. Bởi vì chúng ta đang quan tâm đến giá trị chi phí, chúng ta chọn để làm tròn lên các chi phí và do đó băng thông giảm xuống. 3.1.4. Mã hóa trễ Trễ được mã hóa theo µs bằng cách sử dụng cùng một phương pháp theo hàm mũ như mô tả về băng thông, ngoài trừ cơ sở đó được xác định là 4 thay vì 8. Vì vậy, trễ lớn nhất có thể được thể hiện là 713 4*)12(  (xấp xỉ 134s). 3.2. Các cơ chế thực hiện mở rộng QoS cho OSPF 3.2.1. Các thuật toán và thông tin lựa chọn đường dẫn Phần này mô tả một vài thuật toán lựa chọn đường dẫn, thứ có thể được sử dụng để tạo ra các tuyến đường có khả năng đảm bảo chất lượng dịch vụ dựa trên các sự thỏa hiệp khác nhau giữa độ chính xác, độ phức tạp tính toán, và không bị ràng buộc của việc thực thi. 3.2.1.1. Các thông số Như đã nêu ở trên, quá trình lựa chọn một đường dẫn mà có thể thỏa mãn các yêu cầu QoS của một luồng lưu lượng mới dựa vào cả hai hiểu biết về các yêu cầu và các đặc điểm của luồng lưu lượng đó, và thông tin về sự sẵn có của nguồn tài nguyên trong mạng. Ngoài ra, điều cũng rất quan trọng đối với thuật toán là tính toán tổng số lượng tài nguyên tiêu thụ để hỗ trợ một luồng lưu lượng mới. Nhìn chung, mạng ưa lựa chọn “giá thấp nhất” hơn trong số tất cả các đường dẫn thích hợp cho một luồng lưu lượng mới. Hơn nữa, mạng lưới cũng có thể quyết định từ chối một luồng lưu lượng mới khi mà chi phí cho đường đi của 56 nó được cho là quá cao. Các vấn đề như vậy trong vùng chấp nhận cuộc gọi nhiều hơn trong vùng lựa chọn đường dẫn, nhưng việc cung cấp khả năng để tính toán cho các khía cạnh này ảnh hưởng đến một vài số liệu mà các quá trình lựa chọn đường dẫn dựa vào. Kết quả là, chúng ta xem xét các metric sau đây:  Băng thông khả dụng của liên kết: Đây là một tham số quan trọng, băng thông khả dụng của một liên kết liên quan đến dung lượng không sử dụng hay là dự phòng của liên kết đó trong 1 khoảng thời gian nhất định. Băng thông khả dụng phụ thuộc vào lưu lượng đang có trên mạng tức là phụ thuộc vào độ chiếm dụng băng thông của lưu lượng đang tồn tại trên mạng. Như vậy băng thông khả dụng thay đổi theo thời gian.  Tổng số chặng: Số lượng chặng này được sử dụng như số đo chi phí đường dẫn tới mạng. Một đường dẫn với một số lượng chặng nhỏ hơn (cái mà có thể hỗ trợ một kết nối được yêu cầu) là thích hợp hơn vì nó tiêu thụ ít tài nguyên mạng hơn.  Chính sách: Các chính sách được sử dụng để lược bớt các liên kết mạng không tương thích, sự thực thi hoặc mức độ mô tả đặc tính, với các nhu cầu của một luồng lưu lượng. Việc sử dụng các chính sách để xử lý các yêu cầu cụ thể cho phép đơn giản hóa đáng kể trong việc tối ưu hóa được thực hiện bằng các thuật toán lựa chọn đường dẫn. 3.2.1.2. Các thuật toán lựa chọn đường dẫn [13] Có một vài hướng cho các thuật toán lựa chọn đường dẫn. Các hướng chính gồm các tiêu chuẩn tối ưu hóa mà việc chọn đường dựa trên đó, topo chính xác mà trên đó nó tiến hành chọn và thời điểm nó được gọi tới. Như đã đề cập, việc gọi tới thuật toán lựa chọn đường dẫn có thể là do luồng lưu lượng hoặc do những thay đổi trong các trạng thái liên kết khi thuật toán sử dụng cho phép tính toán trước các đường dẫn. Topo mà trên đó thuật toán chạy được, như với việc lựa chọn đường dẫn OSPF tiêu chuẩn, có thể là một sơ đồ có hướng trong đó đỉnh bao gồm các router và các mạng (các đỉnh chuyển tiếp) cũng như các stub-network (các đỉnh không chuyển tiếp). Khi tính toán một đường dẫn, các stub-network được thêm vào như là một bước xử lý bổ sung tương tự như của thuật toán OSPF tiêu chuẩn. Các tiêu chí tối ưu hóa được sử dụng bởi việc lựa chọn đường dẫn được phản ánh trong các chi phí liên quan đến mỗi giao diện trong topo và làm thế 57 nào các chi phí này được tính toán cho bản thân thuật toán. Như đã đề cập trước đó, chi phí của đường dẫn là một hàm của số lượng chặng và lượng băng thông khả dụng. Kết quả là, mỗi giao diện được gán một thông số tương ứng với lượng băng thông vẫn còn có sẵn trên giao diện này. Thông số này được kết hợp với thông tin số lượng chặng để cung cấp một giá trị chi phí sử dụng trong thuật toán lựa chọn đường dẫn. Việc nó được sử dụng như thế nào phụ thuộc vào dạng chính xác của thuật toán, nhưng tất cả sự lựa chọn mô tả trong mục này chia sẻ một mục đích chung. Tất cả chúng nhằm mục đích chọn một đường dẫn với số lượng chặng nhỏ nhất mà vẫn có thể hỗ trợ băng thông yêu cầu. Khi một vài đường dẫn như vậy sẵn có, sự ưu tiên dành cho đường dẫn với băng thông khả dụng (nghĩa là giá trị nhỏ nhất trên bất kỳ liên kết nào trên đường dẫn) là lớn nhất. Lý do cơ bản cho quy tắc trên là: ta tập trung vào những đường dẫn khả thi (tính toán bởi thông số băng thông khả dụng) mà tiêu thụ một lượng tối thiểu các tài nguyên mạng (tính toán bởi thông số số lượng chặng); và quy tắc cho việc lựa chọn trong các đường dẫn này nhằm mục tiêu cân bằng tải cũng như là hợp lý hóa tối đa băng thông yêu cầu sẽ thực sự có sẵn. Nó sẽ được đề cập đến trong một vài sự quan tâm cần thiết để đảm bảo một sự tương ứng với các đỉnh trong cơ sở dữ liệu topo và số lượng chặng. Đó là bởi vì, như đã đề cập trước đó, các mạng cũng tương ứng với các đỉnh trong topo. Do đó, chúng được gắn kết với các cạnh nhưng sẽ chỉ được tính như là một chặng. Vấn đề này có thể được xử lý dễ dàng thông qua việc sử dụng các cạnh zero-hop (chặng không) trong thuật toán. Cần lưu ý rằng, các thuật toán định tuyến tiêu chuẩn thường nhằm mục đích là tối ưu hóa khách quan mục tiêu quy chuẩn riêng rẽ, tức là chúng có thể tối thiểu số lượng chặng, hoặc tối đa hóa băng thông đường dẫn, nhưng không phải là cả hai. Việc tối ưu hóa đường dẫn khách quan là một nhiệm vụ phức tạp hơn, và nói chung, nó là một vấn đề khó. Tuy nhiên, như chúng ta thấy, bởi vì bản chất cụ thể của hai mục tiêu là tối ưu hóa, sự phức tạp của thuật toán đề xuất là tương tự như là các thuật toán khách quan tiêu chuẩn riêng rẽ. 3.2.1.2.1. Thuật toán cho các đường dẫn QoS được tính toán trước chính xác Trong phần này, ta mô tả một thuật toán lựa chọn đường dẫn, thuật toán đưa ra topo mạng và các thông số liên kết, cho phép chúng ta tính toán trước tất cả các đường dẫn QoS có thể, và cũng có độ phức tạp tính toán thấp hợp lý. Cụ thể, thuật toán cho phép chúng ta tính toán trước cho bất cứ đích đến nào một đường dẫn có tổng số chặng là tối thiểu với băng thông tối đa, và có một độ phức tạp tính toán có thể so sánh với độ phức tạp của một thuật toán đường dẫn 58 ngắn nhất tiêu chuẩn. Các thuật toán lựa chọn đường dẫn dựa trên thuật toán đường dẫn ngắn nhất Bellman-Ford (BF), một thuật toán thích hợp để tính toán các đường dẫn băng thông khả dụng lớn nhất cho tất cả các số chặng. Một đặc điểm của thuật toán BF chính là tại lần lặp lại thứ h của nó, nó xác định đường dẫn giữa nguồn và mỗi đích tối ưu hóa (chúng ta coi băng thông lớn nhất) trong số các đường dẫn có tối đa h chặng. Vì vậy, chúng ta cũng tận dụng lợi thế là thuật toán BF xử lý bằng cách tăng số lượng chặng, để chủ yếu nhận được số chặng của một đường dẫn như là một tiêu chí tối ưu hóa thứ hai. Cụ thể, tại lần lặp lại thứ k của thuật toán, băng thông khả dụng tối đa cho tất cả các đích đến trên đường dẫn không quá k chặng được ghi lại, cùng với các thông tin định tuyến tương ứng. Sau khi thuật toán kết thúc, thông tin này cho phép chúng ta xác định tất cả các đích và các yêu cầu băng thông, đường dẫn với số lượng chặng nhỏ nhất có thể và băng thông đủ để đáp ứng các yêu cầu mới. Hơn nữa, đường dẫn này cũng là một đường dẫn với một băng thông khả dụng lớn nhất trong tất cả các đường dẫn khả thi với số chặng tối thiểu. Bây giờ, chúng ta tiến hành với một mô tả chi tiết hơn của thuật toán và cấu trúc dữ liệu sử dụng để ghi lại thông tin định tuyến, nghĩa là: bảng định tuyến QoS được xây dựng khi thực hiện mã hóa giả cho thuật toán này. Như đã đề cập trước đó, thuật toán này hoạt động trên một sơ đồ có hướng bao gồm chỉ các đỉnh chuyến tiếp (các bộ định tuyến và các mạng), với stub-networks rồi sau đó thêm vào đường dẫn (hoặc các đường dẫn) được tạo ra bởi thuật toán. Các số liệu kết hợp với mỗi cạnh của sơ đồ là băng thông sẵn có trên giao diện tương ứng. Cho ,n mb là băng thông khả dụng trên cạnh giữa các đỉnh n và m. Các đỉnh tương ứng với router nơi mà thuật toán đang chạy, nghĩa là: các bộ định tuyến tính toán được ký hiệu là nút nguồn cho mục đích lựa chọn đường dẫn. Thuật toán tiến hành tính toán trước các đường dẫn từ nút nguồn với tất cả các mạng đích khả dụng và cho tất cả các giá trị băng thông khả dụng. Tại mỗi bước lặp, kết quả trung gian được ghi lại vào một bảng định tuyến QoS, bảng này có cấu trúc như mô tả dưới đây. Bảng định tuyến QoS:  Một ma trận K H , với K là số lượng đích (các đỉnh trong sơ đồ) và H là số chặng tối đa cho phép (hoặc có thể ) cho một đường dẫn.  Phần tử (n; h) được xây dựng trong suốt h bước lặp (giá trị tính toán chặng) của thuật toán, và bao gồm hai trường: 59 o b là băng thông khả dụng lớn nhất trên đường dẫn của tối đa h chặng giữa nút nguồn (router) và nút đích n o Hàng xóm: đây là thông tin định tuyến kết hợp với đường dẫn có h (hoặc ít hơn) chặng đến đích nút n, băng thông khả dụng của nó là b . Đặc tính cụ thể của thông tin này phụ thuộc vào phạm vi của đường dẫn được lựa chọn, nghĩa là nó đơn giản là một chặng kế tiếp hoặc là một tuyến nguồn hoàn chỉnh theo lý thuyết. Trong cả hai trường hợp, thông tin này được xây dựng và ghi nhận tại mỗi lần lặp của thuật toán, nhưng nó nhận được khác nhau và sử dụng khác nhau.  Khi phạm vi của đường dẫn được lựa chọn thì đơn giản là bước kế tiếp, tức là việc lựa chọn đường dẫn hop-by-hop, thông tin hàng xóm đơn giản là số nhận dạng của các nút liền kề với nút nguồn trên đường dẫn đó. Theo một quy định, nút hàng xóm phải là một router và không phải là một mạng, ngoại lệ duy nhất là trường hợp mạng là nút đích (và đường dẫn đã chọn là cạnh riêng rẽ nối liền nguồn này đến nó)  Khi đường dẫn được lựa chọn là một tuyến nguồn hoàn chỉnh, thì thông tin hàng xóm là router đứng trước. Tiếp theo, chúng ta cung cấp thêm các chi tiết về hoạt động của thuật toán này và làm thế nào các mục trong bảng định tuyến được cập nhật khi thuật toán tiến hành. Để đơn giản, đầu tiên chúng ta mô tả trường hợp đơn giản hơn, mà ở đó tất cả các cạnh như là các chặng, và sau đó giải thích làm thế nào cạnh zero- hop được xử lý. Khi thuật toán được gọi tới, đầu tiên bảng định tuyến được khởi tạo với tất cả các trường b thiết lập là 0 và các trường hàng xóm được xóa đi. Tiếp theo, các mục trong cột đầu tiên (tương ứng với các đường dẫn chặng) của các hàng xóm của bộ định tuyến tính toán được sửa đổi theo cách sau: trường b được thiết lập giá trị của băng thông khả dụng trên cạnh trực tiếp từ nguồn. Việc sửa đổi của trường hàng xóm tùy thuộc vào phạm vi của sự lựa chọn đường dẫn. Đối với việc định tuyến chặng kế tiếp, nó được thiết lập để nhận dạng hàng xóm của bộ định tuyến tính toán, nghĩa là router tiếp theo trên đường dẫn lựa chọn. Đối với định tuyến nguồn, nó được thiết lập để tự nhận dạng bộ định tuyến tính toán (computing router). Sau đấy, thuật toán lặp lại cho tối đa H bước lặp. H có thể hoặc là số chặng tối đa có thể của bất kỳ đường dẫn nào, nghĩa là một giá trị 60 ẩn, hoặc nó có thể được thiết lập rõ ràng để giới hạn chiều dài đường dẫn đến một số giá trị lớn nhất để điều khiển tốt hơn trong trường hợp phức tạp nhất. Tại bước lặp thứ h, đầu tiên chúng ta sao chép cột h-1 tới cột h. Thêm nữa, thuật toán này giữ một danh sách các nút có thay đổi giá trị b của chúng trong lần lặp trước đó, nghĩa là trong suốt bước lặp thứ h-1, thuật toán sau đó xem xét mỗi liên kết (n; m) và kiểm tra băng thông khả dụng lớn nhất trên một đường dẫn h chặng tới nút m, với chặng cuối cùng của nút m chính là liên kết đó. Tổng số này để lấy số nhỏ nhất giữa trường b trong mục vào (n; h-1) và giá trị metric liên kết ,n mb giữ trong cơ sở dữ liệu topo. Nếu giá trị này cao hơn giá trị hiện tại của trường b trong mục vào (m;h), thì sau đó một đường dẫn tốt hơn (có giá trị b lớn hơn) được tìm thấy cho đích m và với h bước nhảy. Trường b của mục vào (m;h) sau đó được cập nhật để mang lại giá trị mới. Trong trường hợp định tuyến chặng kế tiếp, trường hàng xóm của mục vào (m;h) được thiết lập tới giá trị như trong mục vào (n;h-1). Điều này ghi lại định danh của chặng đầu tiên (tiếp theo chặng từ nguồn) trên đường dẫn tốt nhất được nhận biết cho đích đến n và với h chặng (hoặc ít hơn h). Trong trường hợp định tuyến nguồn, trường hàng xóm của mục vào (m;n) được thiết lập để nhận dạng nút n. Điều này ghi lại định danh của bước nhảy trước đó trên đường dẫn tốt nhất được nhận biết cho đích m và với h chặng (hoặc ít hơn). Điều này cho phép xây dựng đệ quy định tuyến nguồn hoàn chỉnh đơn giản bằng cách lần tìm ngược từ mục vào tới mục vào trong bảng. Chúng ta kết thúc mục này bằng việc mô tả các cạnh zero-hop được xử lý như thế nào. Tại mỗi bước lặp h, khi nào một mục vào (m;h) được sửa đổi, thì nó được kiểm tra xem liệu có các cạnh giá bằng không zero-cost (m;k) xuất hiện từ nút m, trong trường hợp m là một mạng chuyển tiếp. Trong trường hợp đó, ta cố gắng để cải thiện mục vào của nút k, nút mà tương ứng với chặng thứ h, tức là: mục vào (k;h) khi cạnh (m;k) không tính là một chặng bổ sung, như với hoạt động thường xuyên của thuật toán. Các số này để lấy số nhỏ nhất giữa trường b trong mục vào (m; h), và giá trị metric liên kết ,m kb giữ trong cơ sở dữ liệu topo. Nếu giá trị này cao hơn giá trị hiện tại của trường b trong mục vào (k;h), sau đó trường b của mục vào (k;h) được cập nhật giá trị mới. Trong trường hợp định tuyến chặng kế tiếp, trường hàng xóm của mục vào (k;h) được thiết lập, như thường lệ, tới giá trị tương tự như trong mục (m;h) (cũng là giá trị trong mục (n;h-1)). Trong trường hợp của định tuyến nguồn, trường hàng xóm của mục vào 61 (k; h) được thiết lập để nhận dạng nút n. Điều này ghi lại định danh của router trước đó trên đường dẫn đã nhận dạng. 3.2.1.2.2. Thuật toán cho việc tính toán theo yêu cầu của các đường dẫn QoS [1] Trong phần trước, chúng ta mô tả một thuật toán cho phép tính toán trước các tuyến đường QoS, và nó là có thể khả thi trong một số trường hợp. Ví dụ, thay vì hạn chế số lượng các yêu cầu cho các tuyến đường QoS có thể thực hiện các tính toán theo yêu cầu, tức là dựa vào mỗi khi nhận một yêu cầu cho một tuyến đường QoS. Lợi ích của cách tiếp cận như vậy là tùy thuộc vào sự tính toán lại thường xuyên của các tuyến đường đã tính toán trước, sự tính toán các tuyến đường theo yêu cầu có thể mang lại các tuyến đường tốt hơn bằng cách sử dụng các metric liên kết sẵn có gần nhất. Một lợi ích khác của việc tính toán đường dẫn theo yêu cầu là tiết kiệm bộ nhớ, nghĩa là, không cần phải có một bảng định tuyến. Đây là một sự cân bằng tiêu chuẩn giữa bộ nhớ và các chu kỳ xử lý. Trong phần này, chúng ta mô tả một cách ngắn gọn xem thuật toán Dijkstra tiêu chuẩn có thể làm gì cho một đích và yêu cầu băng thông, tạo một đường dẫn có số chặng tối thiểu có thể thích nghi với băng thông yêu cầu và cũng có băng thông tối đa. Bởi vì thuật toán Dijkstra đã được sử dụng trong việc tính toán tuyến đường OSPF hiện tại, chỉ những sự khác biệt từ thuật toán tiêu chuẩn mới được mô tả ở đây. Một thuật toán về cơ bản thực hiện một tính toán đường dẫn số chặng tối thiểu, trên một sơ đồ hướng mà trong đó tất cả các cạnh có băng thông khả dụng nhỏ hơn so với băng thông yêu cầu đều bị loại bỏ. Điều này có thể được thực hiện thông qua một bước tiền xử lý hoặc trong khi chạy thuật toán bằng cách kiểm tra giá trị băng thông khả dụng cho bất kỳ cạnh nào được xem xét. Một sửa đổi khác cho thuật toán Dijkstra tiêu chuẩn dựa vào việc tính toán đường dẫn có số chặng nhỏ nhất, là danh sách các chặng kế tiếp có chi phí như nhau, những chặng được duy trì khi thuật toán tiến hành cần được sắp xếp theo băng thông khả dụng. Điều này cho phép lựa chọn đường dẫn có số chặng tối thiểu với băng thông khả dụng tối đa. Ngoài ra, thuật toán có thể cũng được thay đổi để, tại mỗi bước, chỉ giữ lại trong số các đường dẫn có số chặng như nhau với băng thông khả dụng lớn nhất. Điều này chủ yếu để xem xét chi phí là một hàm của cả số chặng và băng thông khả dụng. 3.2.1.2.3.Thuật toán cho các đường dẫn QoS tính toán trước gần đúng 62 Phần này đưa ra một thuật toán dựa trên thuật toán Dijkstra cho phép tính toán trước các tuyến đường QoS cho tất cả các đích và các giá trị băng thông. Như đã đề cập trước đó, việc sử dụng một thuật toán dựa trên Dijkstra là mạnh hơn so với triển khai OSPF hiện tại, trong khi việc cho phép tính toán trước đường đi sẽ giúp cho sự quá tải trong tính toán trở lên thấp hơn. Tuy nhiên, có sự mất mát trong "sự chính xác" của các đường dẫn được tính toán trước, nghĩa là, những con đường được tạo ra có thể là của một số chặng lớn hơn là cần thiết. Sự mất mát trong độ chính xác đến từ sự cần thiết phải dựa vào các giá trị băng thông đã được lượng tử hóa, cái được sử dụng khi tính toán một con đường có số chặng tối thiểu. Nói một cách khác, phạm vi của các giá trị băng thông có thể được yêu cầu bởi luồng lưu lượng mới bây giờ được ánh xạ vào một số cố định của các giá trị đã lượng tử hóa, và các con đường có số chặng tối thiểu được tạo ra cho mỗi giá trị lượng tử hóa. Ví dụ, người ta có thể giả định rằng các giá trị băng thông được lượng tử hóa như là thấp, trung bình và cao, và các đường dẫn có số chặng tối thiểu được tính với từng giá trị trong ba giá trị này. Một luồng lưu lượng mới sau đó được giao cho đường dẫn có số chặng tối thiểu mà có thể mang giá trị lượng tử hóa nhỏ nhất, lớn hơn hoặc bằng với những gì nó yêu cầu. Thuật toán này hoạt động trở lại trên một sơ đồ hướng mà các đỉnh tương ứng với các router và các mạng chuyển tiếp. Một lần nữa, ,n mb là băng thông khả dụng trên các cạnh nối giữa đỉnh n và m. Đỉnh tương ứng với bộ định tuyến nơi mà thuật toán đang chạy được lựa chọn như là nút nguồn, và thuật toán tiến hành tính toán các đường dẫn tới tất cả các nút khác (các đích đến). Bắt đầu với chỉ số lượng tử hóa cao nhất, Q, thuật toán xem xét các chỉ số liên tiếp theo thứ tự giảm dần. Với mỗi chỉ số q, thuật toán hủy bỏ tất cả các liên kết topo mạng ban đầu (n,m) với , [ ]n mb b q , với [ ]b q là giá trị băng thông lượng tử hóa thứ q, và sau đó chạy trên topo còn lại với một thuật toán tính số chặng nhỏ nhất dựa trên Dijkstra giữa nút nguồn và các nút khác (các đỉnh) trên sơ đồ. Chú ý rằng với thuật toán Dijkstra sử dụng cho việc tính toán đường dẫn theo yêu cầu, việc loại bỏ các liên kết như là , [ ]n mb b q có thể vẫn được thực hiện trong khi đang chạy thuật toán [5]. 3.2.1.3. Mở rộng: Xử lý các yêu cầu trễ Nhìn chung, việc lựa chọn đường dẫn không cho phép chúng ta tính toán rõ ràng cho sự lan truyền liên kết và các trễ hàng đợi. Như đã đề cập, hướng này được xử lý thông qua một cơ chế chiến lược. Tuy nhiên, nó chỉ ra rằng một sự mở rộng đơn giản đến thuật toán lựa chọn đường dẫn dự kiến cho phép chúng ta 63 tính toán trực tiếp trễ nếu chúng ta có thể giả sử rằng trễ end-to-end có thể được mở rộng dưới một hình thức cụ thể. Cụ thể, trễ end-to-end có thể được thể hiện bởi biểu thức sau:    pl ldb phpD ))(()(  (3.1) Với p là đường đi qua D(p) là trễ end-to-end cam đoan (cận trên) h(p) là số các bước nhảy b là băng thông đã đăng ký trước dl là trễ lan truyền (cố định) của một liên kết l α(h) là một tham số tăng theo h (với chh .)(  là giá trị đặc trưng) σ là kích thước truyền loạt c là kích thước gói tối đa Giả sử thêm rằng chúng ta tự hạn chế trong định tuyến nội miền, và khi các liên kết với các trễ lan truyền rất cao có thể được lọc ra bởi chính sách điều khiển, nó có thể được giả định rằng các trễ lan truyền dl của tất cả các liên kết có thể được giới hạn cận trên hợp lý bởi một giá trị d. Biểu thức (3.1) chỉ ra rằng một yêu cầu trễ end-to-end D có thể được chuyển đổi sang yêu cầu băng thông b(h) thông qua biểu thức: dhD hhb . )()(    (3.2) với h là số chặng trong đường dẫn thiết lập cho kết nối. 3.2.2. Thông báo thông tin trạng thái liên kết Giả sử rằng mỗi router duy trì một cơ sở dữ liệu cập nhật của topo mạng, bao gồm trạng thái hiện tại (băng thông khả dụng) của mỗi liên kết. Việc phân bố thông tin trạng thái (metric) liên kết được dựa trên các cơ chế OSPF mở rộng. Trong điều kiện lý tưởng nhất, mong muốn các router tổng hợp được hầu hết băng thông có sẵn hiện tại trên tất cả các liên kết trong mạng, để chúng có thể đưa ra quyết định chính xác nhất con đường được lựa chọn. Lúc đó có các 64 bản cập nhật rất thường xuyên, ví dụ gần như mỗi khi băng thông khả dụng của một liên kết thay đổi, thứ không thường xuyên kéo dài và cũng không thực tế. Ngoài ra, người ta có thể lựa chọn một cơ chế đơn giản dựa trên các thông tin cập nhật định kỳ, nơi mà chu kỳ của việc cập nhật được xác định dựa trên một tải trọng tương ứng chấp nhận được trên mạng và các router. Nhược điểm chính của cách tiếp cận như vậy là sự thay đổi lớn trong các băng thông có sẵn trên một liên kết có thể vẫn chưa được biết trong một chu kỳ đầy đủ, và do đó, dẫn đến nhiều quyết định định tuyến không chính xác. Một thay thế tốt hơn là sử dụng một cơ chế cập nhật đơn giản, một cơ chế cố gắng để điều hòa độ chính xác của thông tin trạng thái liên kết với sự cần thiết cho quá tải có thể nhỏ nhất. Như một sự phối hợp có thể được cụ thể hóa và tinh chỉnh bằng nhiều cách khác nhau, một số trong đó được thảo luận dưới đây. Giả sử rằng mỗi nút gửi một thông điệp thông báo trạng thái liên kết (LSA) chỉ khi tỉ số giữa giá trị hiện tại b của một liên kết và giá trị báo cáo cuối cùng ở bên trên (hoặc bên dưới) ngưỡng, giả sử là 2. Điều này có nghĩa là, khi một tuyến đường với vài đơn vị (unit) băng thông được tìm kiếm, các liên kết với các giá trị băng thông thông báo trên 2b là “các dự đoán an toàn”, với những giá trị thấp hơn b/2 sẽ được loại trừ, và tất cả phần còn lại có thể cung cấp băng thông yêu cầu với các mức độ khác nhau của sự chính xác. Điều đó nghĩa là, một mục tiêu thứ ba được thêm vào hai mục tiêu tiêu chuẩn của băng thông và tổng số chặng, đó là độ chính xác. Sự hợp nhất của nó trong quá trình lựa chọn đường dẫn có thể được xử lý với các mức độ khác nhau của sự phức tạp và sự tinh sảo. 3.2.2.1. Phương pháp xác suất (1) Giá trị băng thông của một liên kết l là một biến ngẫu nhiên nhận các giá trị trong khoảng ( / 2, 2 )l lb b với lb là giá trị đã thông báo cuối cùng. Bằng việc tạo ra một vài giả thuyết về sự phân bố xác suất của các giá trị này, ví dụ các phân bố đều, người ta có thể tính toán cho mỗi yêu cầu băng thông b xác suất thành công của một liên kết l, gọi là ( )lP b , và sau đó chạy thuật toán BF trên số liệu l{ }w , với log( ( ))l lw P b  . Tuy nhiên, vấn đề ở đây là một đường dẫn khác sẽ được tính toán cho mỗi giá trị băng thông b. Do đó việc phân tích cho phương pháp này rất phức tạp trong trường hợp các tuyến đường được tính toán trước. Vậy thì, ta sẽ xem xét một phương pháp đơn giản hơn. 3.2.2.2. Phương pháp đơn giản (2) 65 Ở đây, ta chạy thuật toán BF tiêu chuẩn, được mô tả trong (3.1), có được như một đầu ra một bảng định tuyến QoS với α nằm trong khoảng 15.0  , là một tham số chỉ ra “risk proneness - hiểm” của người ra quyết định (giá trị càng thấp, ‘trạng thái nguy hiểm” càng cao). Thật vậy, cho RH là một tham số chỉ ra bao nhiêu chặng người ra quyết định sẵn sàng đánh đổi lấy sự an toàn. Sau đó, khi một yêu cầu kết nối phù hợp với giá trị b của băng thông, thực hiện như sau:  Từ bảng định tuyến, có được minh là số chặng tối thiểu của một tuyến đường với băng thông nhỏ nhất là αb  Từ bảng định tuyến, có được maxh , số chặng tối đa của một tuyến đường an toàn, nghĩa là với băng thông nhỏ nhất là 2b  Nếu maxmin hHh R  : chọn tuyến đường an toàn  Nếu khác: từ bảng, chọn tuyến đường có băng thông lớn nhất trong số những tuyến đường có RHh min chặng. 3.2.2.3. Chi tiết hóa phương pháp (3) Một vấn đề chính của phương pháp đơn giản trên là tiềm ẩn khả năng các tuyến đường tốt không được để ý đến. Một ví dụ đơn giản, xem xét 2 đường dẫn giữa nguồn và đích: đường dẫn thứ nhất có hai liên kết với 10 đơn vị băng thông, đường dẫn thứ hai có ba liên kết, hai trong số đó là 20 đơn vị băng thông và liên kết còn lại với 10 đơn vị băng thông. Giả sử rằng, một yêu cầu kết nối với 10 đơn vị băng thông đang được xử lý. Theo phương pháp đơn giản, ta sẽ không tạo một chú giải cho đường dẫn thứ hai, khi nó cho băng thông tương tự như đường dẫn đầu tiên nhưng với số chặng nhiều hơn. Tuy nhiên, đường dẫn thứ hai có độ mạo hiểm ít hơn, do đó có thể sẽ là khôn ngoan hơn khi chọn nó. Cách tiếp cận sau diễn giải vấn đề này. Cho Kbbb  ...21 với MK  là các giá trị băng thông khác nhau tương ứng với thông báo cuối cùng cho mỗi liên kết (như trước, M dùng để chỉ số của các liên kết). Các bước sau đây được thực hiện cho mỗi ib , Ki 1 :  Xóa các liên kết “cấm”, nghĩa là xóa những liên kết với băng thông nhỏ hơn 0.5 ib  Chỉ định “giá” 0 cho một liên kết “an toàn”, nghĩa là, liên kết với băng thông ít nhất là 2 ib , và 1 cho tất cả các liên kết khác, nghĩa là các liên kết với băng thông thông báo trong phạm vi 0.5 ~ 2i ib b .  Chạy thuật thoán BF, sử dụng “giá” trên như là metric. 66 Kết quả là, nhận được một bảng cho từng giá trị băng thông (quan tâm) và cho từng số các chặng h, với đường dẫn có không nhiều hơn h chặng mà có số các liên kết không an toàn nhỏ nhất (và số các liên kết an toàn lớn nhất) đối với giá trị băng thông. Sau đó, khi có một kết nối phù hợp với yêu cầu băng thông là b đơn vị, nghĩa là ii bbb  )1( với Ki 1 , người ra quyết định có thể xác định các tùy chọn khác nhau cho sự trả giá giữa độ an toàn và số chặng cho giá trị băng thông là ib , và chọn đường dẫn tương ứng theo cảm nhận của nó về sự cân bằng giữa hai tiêu chuẩn đó. Phương pháp này là phức tạp về cả thời gian chạy và kích thước bảng, là M lần lớn hơn so với một thuật toán BF tiêu chuẩn. Phương pháp sau đây nhằm giải quyết các vấn đề của phương pháp đơn giản (2), nhưng không phức tạp như trong (3). 3.2.2.4. Giảm sự phức tạp của phương pháp (3) Biểu thị bởi maxb là giá trị lớn nhất mà một băng thông kết nối có thể đạt được. Khi các giá trị băng thông thông báo tăng lên theo cấp số nhân, ví dụ như với cơ số bằng 2, thuật toán đưa ra dự đoán hạn chế phạm vi được cho phép để có thể được thông báo chuỗi tăng lên theo cấp số nhân của ngưỡng, gọi là 1, 2, 4…. Ví dụ, về nguyên tắc một thông điệp thông báo trạng thái liên kết được ban hành chỉ khi một ngưỡng mới được vượt qua, và rồi thông điệp thông báo trạng thái liên kết sẽ thông báo ngưỡng gần nhất với giá trị băng thông hiện thời. Bằng cách này, tỷ lệ giữa các giá trị băng thông thực tế và các giá trị băng thông thông báo được giữ trong phạm vi 0.5…2. Tuy nhiên, số các giá trị thông báo khác nhau, K, bây giờ trở thành ))(log(0 maxb nhỏ hơn là 0(M) như trong (3). Theo đó, độ phức tạp về không gian và thời gian được giảm xuống ))log((0 maxbMH và ))log((0 maxbNH . 3.3. Khảo sát cơ chế chuyển tiếp trong định tuyến OSPF mở rộng cho QoS Khi cần thông báo thông tin trạng thái dùng để các nút cập nhật bảng định tuyến của chúng, cả trong OSPF tiêu chuẩn và trong OSPF mở rộng cho định tuyến QoS như mô tả ở trên, người ta dùng phương pháp lan tràn (flooding) để đưa thông báo tới tất cả các nút liên quan một cách nhanh chóng nhất. Chương 2 đã trình bày một số cơ chế flooding nhằm giảm quá tải mạng do truyền bản tin thăm dò dùng để cập nhật định tuyến. Kết quả của các đề xuất trước đây là một cơ chế chuyển tiếp hai mức. 67 Động cơ thúc đẩy cho sự chuyển tiếp dựa trên bảng hai mức là để giảm quá tải bản tin của flooding. Ví dụ đưa ra trên hình dưới đây giúp cho việc hiểu chuyển tiếp dựa trên bảng 2 mức có thể giảm quá tải như thế nào. Cho v là nút được quan tâm và muuu ,...., 21 là m hàng xóm của nó. Router v nhận một yêu cầu kết nối cho một đích có hơn hai chặng. Nhu cầu băng thông là 5. Một trong những hàng xóm muuu ,...., 21 là thích hợp. Trong bối cảnh như vậy, nếu chuyển tiếp thăm dò dựa trên phương pháp hai mức được sử dụng, thì thăm dò sẽ được loại bỏ. Tuy nhiên, nếu một flooding đơn giản được sử dụng, thì router v có thể gửi m bản sao thăm dò tới muuu ,...., 21 và các thăm dò sẽ bị loại bỏ cuối cùng tại mỗi muuu ,...., 21 . Như vậy, “lan tràn mù - blind flooding” sinh thêm quá tải. Ngoài ra, trong chuyển tiếp dựa trên bảng hai mức, nếu đích đến trong vòng hai chặng thì các thăm dò sẽ được hướng dẫn chỉ về phía đích. Mặt khác, nếu các thăm dò được ngập tràn một cách “mù”, ngoại trừ đích, nhiều nút khác sẽ vẫn nhận thăm dò. Để giảm quá tải, thông tin bổ sung về các hàng xóm mức hai phải được lưu giữ tại mỗi router. Việc duy trì thông tin này tạo thêm tải trong các hình thức duy trì bảng. Cách tiếp cận hai mức sẽ là hợp lý, nếu quá tải tạo ra do việc duy trì bảng là ít hơn nhiều so với việc lưu trữ trong chuyển tiếp thăm dò. Việc lưu trữ trong chuyển tiếp thăm dò phụ thuộc vào tài nguyên sẵn có và topo mạng. Trong luận văn này, đề cập đến chuyến tiếp dựa trên bảng hai mức như là chuyển tiếp hai mức. Hình 3.1. Một ví dụ mạng Người ta đã thực hiện các mô phỏng mở rộng trên các topo mạng khác nhau để đo toàn bộ quá tải bản tin trong cả hai chuyển tiếp 2 mức và lan tràn mù. Do các điều kiện ràng buộc về không gian và thời gian mô phỏng, các kết 68 quả được báo cáo chỉ với hai topo mạng. Hai phương pháp tiếp cận đã được thử nghiệm trên các topo mạng MESH-I và ISP được thể hiện trên hình sau đây. Hình 3.2. MESH-I Hình 3.3. ISP 3.3.1. Hiệu suất của các phiên bản không giới hạn Đồ thị cho trong hình dưới đây cho thấy quá tải trong các phiên bản không giới hạn của hai cách tiếp cận về MESH-I. 69 Hình 3.4. Flooding không giới hạn: Quá tải trên MESH-I T là giá trị ngưỡng sử dụng trong chính sách cập nhật, nghĩa là cứ T giây có một bản tin cập nhật hoặc nói cách khác là bảng định tuyến ở mỗi nút được duy trì (bảo lưu) ít nhất T giây. Trên đồ thị Hình 3.4, rõ ràng là hai mức chuyển tiếp có quá tải rất thấp (cho mỗi cuộc gọi – nhận) so với lan tràn mù. Khi băng thông có sẵn trong mạng nhỏ, quá tải tăng lên đáng kể khi ngưỡng T giảm. Tuy nhiên, khi băng thông sẵn có lớn, giá trị của T không ảnh hưởng đến quá tải. Cách xử lý này có thể được giải thích như sau: Khi băng thông sẵn có ít, tỷ số giữa băng thông khả dụng hiện tại/băng thông quảng cáo mới nhất sẽ dao động đáng kể cùng với mỗi cuộc gọi được chấp nhận. Kết quả là, nếu giá trị T thấp được sử dụng, các router sẽ gửi các thông tin cập nhật thường xuyên hơn so với khi các giá trị T cao. Nếu băng thông khả dụng trong mỗi liên kết cao, thì tỷ số này sẽ không biến động nhiều với mỗi cuộc gọi được chấp nhận. Do đó, các router có xu hướng gửi thông tin cập nhật với tần suất ít hơn, không phụ thuộc vào giá trị của T. Đồ thị trong Hình 3.5 cho thấy tỷ số cho phép băng thông cho hai phiên bản không bị giới hạn trong mạng topo MESH-I. Tỷ số này được định nghĩa như là tỷ số của băng thông đã nhận vào mạng trên toàn bộ băng thông yêu cầu [10]. Đồ thị cho thấy rằng, khi tải trọng nhẹ, cả hai phương pháp tiếp cận thực hiện phần lớn là tốt như nhau. Tuy nhiên, khi lưu lượng lớn, sự chuyển tiếp dựa trên bảng hai mức nhận băng thông nhận vào ít hơn so với flooding. Ngoài ra, băng 70 thông nhận vào bởi cách tiếp cận hai mức giảm khi T tăng. Lý do là, sự không chính xác trong thông tin bảng tăng theo giá trị của T. Sự không chính xác này làm cho các router bảo lưu băng thông sẵn có trong các liên kết mức hai. Do đó, router loại bỏ các thăm dò mặc dù các liên kết mức hai có khả năng trợ giúp các yêu cầu này. Tại giá trị T thấp, sự không chính xác giảm. Vì vậy, các router có xu hướng ít bảo lưu hơn và chúng nhận được băng thông nhiều hơn vào mạng. Hình 3.5. Flooding không giới hạn: băng thông nhận vào trong MESH-I Hai hình sau đây cho thấy hiệu suất của phiên bản không giới hạn của 2 phương pháp tiếp cận trên topo ISP. 71 Hình 3.6. Flooding không giới hạn: Quá tải trên ISP Hình 3.7. Flooding không giới hạn: băng thông nhận vào trên ISP Như đã nêu ở trên, việc giảm quá tải bản tin tùy thuộc vào topo. Trong MESH-I, có nhiều đường dẫn thay thế giữa các cặp nguồn và đích. Kết quả là, về mặt quá tải bản tin, cách tiếp cận hai mức tốt hơn nhiều flooding mù. Ngoài ra, về mặt băng thông nhận vào, cách tiếp cận hai mức là tương đương với 72 flooding mù. Trong topo ISP, không có nhiều đường dẫn thay thế giữa bất cứ cặp nguồn và đích nào. Do đó, mặc dù cách tiếp cận hai mức giảm quá tải, thì việc giảm này không đáng kể so với trong MESH-I. Việc thiếu các đường dẫn thay thế ảnh hưởng tới băng thông nhận vào bởi phương pháp tiếp cận hai mức là khá đáng kể. Như vậy, bằng cách so sánh đồ thị trong Hình 3.5 và Hình 3.7, hiệu quả về topo trong việc thực thi của các cách tiếp cận hai mức có thể nhìn thấy rõ ràng. 3.3.2. Hiệu suất của các phiên bản giới hạn Phiên bản giới hạn của hai thuật toán cũng được so sánh. Động cơ thúc đẩy đằng sau kỹ thuật giới hạn là giảm flooding không cần thiết trong mạng. Trong cách tiếp cận giới hạn, các thăm dò được đưa ra độ tuổi tối đa L, bằng với tsd , , trong đó tsd , là số chặng trong tuyến đường ngắn nhất giữa nguồn s và đích t. Quá tải trong MESH-I cho fooding mù và chuyển tiếp hai mức được cho trong hình dưới đây. Hình 3.8. Giới hạn (L): Quá tải trên MESH-I Quá tải của các phiên bản giới hạn rõ ràng là ít hơn quá tải của các phiên bản không giới hạn. Thậm chí ở đây, cách tiếp cận hai mức giúp giảm quá tải bản tin. Hình tiếp sau đây so sánh băng thông nhận vào trong MESH-I bởi hai phương pháp. 73 Hình 3.9. Giới hạn (L): Băng thông nhận vào trên MESH-I Theo dự kiến, tại bất kỳ tải mạng được cho nào, băng thông nhận vào bởi các phiên bản giới hạn là nhỏ hơn hoặc bằng băng thông nhận được bởi các phiên bản không giới hạn. Điều này là do sự thu hẹp phạm vi của việc tìm kiếm đường dẫn. Một lần nữa cần lưu ý topo MESH-I, xét về băng thông nhận vào, hiệu suất của phương pháp hai mức so sánh được với hiệu suất của flooding mù. Hình 3.10 cho thấy quá tải phát sinh trong topo ISP bởi hai phiên bản giới hạn. Việc thiếu các đường dẫn thay thế kết hợp với điều kiện số chặng làm cho flooding mù và chuyển tiếp hai mức có thể so sánh được về mặt quá tải bản tin. Về mặt băng thông nhận vào, flooding thực hiện tốt hơn so với chuyển tiếp hai mức. Điều này có thể nhìn thấy từ hình 3.11. 74 Hình 3.10. Giới hạn (L): Quá tải trên ISP Hình 3.11. Giới hạn (L): Băng thông nhận vào trên ISP Tóm lại: Chương 3 trình bày về các mở rộng OSPF cho định tuyến đảm bảo chất lượng và các thuật toán tính toán đường dẫn tối ưu đa ràng buộc. Đánh giá việc thực hiện cơ chế định tuyến QoS 75 KẾT LUẬN Định tuyến dựa trên QoS là một vấn đề khó và rộng, đòi hỏi các kiến thức liên quan như lý thuyết xác suất, lưu lượng, hàng đợi ... Đây là một lĩnh vực đang rất được quan tâm nhằm tìm ra giải pháp tối ưu trong việc việc sử dụng hiệu quả tài nguyên mạng, đặc biệt quan trọng khi ứng dụng trong quy hoạch, thiết kế, điều hành và quản lý mạng. Trong phạm vi luận văn, mới chỉ tập trung vào việc tìm hiểu và trình bày về định tuyến dựa trên QoS, các cơ chế định tuyến QoS nội miền và liên miền và một số phương án mở rộng thuật toán OSPF nhằm hỗ trợ QoS. Mặc dù nội dung luận văn chưa có những nghiên cứu, ứng dụng thực tế, nhưng các kiến thức được tổng hợp và phân tích trong luận văn có thể làm tiền đề cho các kết quả nghiên cứu sâu hơn về mở rộng và phát triển các dịch vụ mạng có yêu cầu QoS. Trên cơ sở những kết quả đã đạt được của luận văn, hướng phát triển là xây dựng công cụ mô phỏng để phân tích và so sánh kỹ hơn về một số cơ chế trong thực thi mở rộng OSPF cho định tuyến QoS 76 TÀI LIỆU THAM KHẢO [1] B. V. Cherkassky, A. V. Goldberg, and T. Radzik, Shortest Paths Algorithms: Theory and Experimental Evaluation, in Proceedings of the 5th Annual ACM SIAM Symposium on Discrete Algorithms, Arlington, VA, January 1994, pp. 516–525. [2] D. Ghosh, V. Sarangan and R. Acharya, Quality of Service Routing in IP Network, IEEE Trans. Multimedia, no. 2, vol. 3, pp. 200-208, June 2001. [3] E. Crawley, R. Nair, B. Rajagopalan and H. Sandick, A Framework for QoS-based Routing in the Internet, RFC 2386, 1998. [4] G. Apostopoulos, R. Guérin, S. Kamat, A. Orda, S. K. Tripathi, Intradomain QoS routing in IP networks: a feasibility and cost/benefit analysis, IEEE Trans. Networks, no. 5, pp. 42-54, Sup/Oct. 1999. [5] R. Guerin and A. Orda, QoS-Based Routing in Networks with Inaccurate Information: Theory and Algorithms, in IEEE INFOCOM’97, Kobe, Japan, April 1997, pp. 75–83. [6] J. Moy, OSPF Version 2, RFC 2328, 1998. [7] J. Lakkakorpi, QoS Routing Extensions to OSPF, Technical report Helsinki University of Technology, 2005. [8] M. Curado, O. Reis, J. Brito, and E. Monteiro, Stability and scalability issues in Hop-By-Hop class-based routing, Proceedings of the 2nd International Workshop on QoS in Multiservice IP Networks, 2003. [9] M. Hollick, I. Martinovic, and T. Rimac, A survey on dependable routing in sensor networks, Ad hoc networks, and cellular networks, Proceedings of the 30th EUROMICRO Conference (EUROMICRO’04), pp. 495-502, Sept. 2004. [10] Q. Ma, P. Steenkiste, Quality-of-service routing with performance guarantees, Proceedings of 4th International IFIP Workshop on Quality of Service, May 1997. 77 [11] R. Guerin, and A. Orda, Computing Shortest Paths for Any Number of Hops, IEEE/ACM Transactions on Networking, pp. 613-620, Oct. 2002. [12] R. A. Guerin, A. Orda, and D. Williams, QoS Routing Mechanisms and OSPF Extensions, Proceedings of IEEE Global Telecommunications Conference (GLOBECOM’97), Phoenix USA, Nov. 1997. [13] T. H. Cormen, C. E. Leiserson, and R. L. Rivest, Introduction to Algorithms, MIT Press, Cambridge, MA, 1990. [14] X. Masip-Bruina et al., Research challenges in QoS routing, Journal of Computer Communication, vol. 29, no. 5, pp. 563-581, 2006. [15] Y. Rekhter and T. Li, A border gateway protocol 4 (BGP-4), Internet Engineering Task Force, RFC 1771, 1995.