Nghiên cứu các kĩ thuật quản lý hàng đợi trong mạng IP

h toán từ gói bị đánh dấu cuối cùng: Pa ← Pb / (1 – count * Pb) Điều này giúp cho router không phải đợi lâu trước khi đánh dấu các gói. Giá trị count càng lớn thì xác suất đánh dấu càng cao. Router đánh dấu các gói tới khi kích thước hàng đợi trung bình vượt quá maxth. Một lựa chọn cho các router RED là tính toán hàng đợi theo byte hơn là theo các gói. Với lựa chọn này thì kích thước trung bình hàng đợi sẽ phản ánh chính xác độ trễ trung bình tại router. Khi lựa chọn này được sử dụng thì thuật toán phải được chỉnh sửa để chắc chắn rằng xác suất các gói bị đánh dấu tỉ lệ với kích thước gói theo byte: Pb ← maxp (avg - minth)/ (maxth - minth) Pb ← Pb * packetsize / maximum packetsize Pa ← Pb /(1- count * Pb) Nhiệm vụ đánh dấu các gói được thực hiện nhờ vào Gateway RED tại mỗi router. Gateway RED là thành phần của mạng thực hiện nhiệm vụ đánh dấu các gói. RED là thuật toán được đưa ra và được điều khiển bởi các Gateway RED trong router. Các gateway này thực hiện việc loại bỏ tắc nghẽn bằng việc sử dụng thuật toán RED để tính toán các giá trị hàng đợi trung bình. Cổng này có thể thông báo tới các kết nối bị tắc nghẽn, cũng như loại bỏ các gói đến cổng hoặc thiết lập các bit trong phần tiêu đề của các gói. Khi kích thước hàng đợi trung bình vượt quá mức ngưỡng cho phép thì Gateway sẽ loại bỏ hoặc đánh dấu các gói đến bằng một hàm xác suất của kích thước hàng đợi trung bình. Các gateway RED giữ cho kích thước hàng đợi trung bình thấp trong khi vẫn cho phép các gói đến dưới dạng bó đi vào hàng đợi. Trong suốt thời gian tắc nghẽn xác suất các gateway thông báo cho các kết nối giảm kích thước cửa sổ của nó phải cân xứng với băng thông của các kết nối được chia sẻ qua gateway. Các gateway RED được thiết kế để hỗ trợ giao thức điều khiển tắc nghẽn lớp truyền tải như TCP. 3.3.3.2 Các tham số của RED Các tham số thể hiện hiệu năng của thuật toán RED và để cấu hình các tham số. Các tham số xác suất loại bỏ gói, chiều dài hàng đợi trung bình, các giá trị ngưỡng. a. Xác suất loại bỏ gói X là biến ngẫu nhiên thể hiện số lượng các gói đến sau một gói được đánh dấu cho tới khi có một gói bị đánh dấu. Giả thiết kích thước hàng đợi trung bình là không đổi. Cách 1: Các biến ngẫu nhiên có hình thức Nếu định nghĩa xác suất mất gói Pb là Pb = maxp * [(avg – minth) / (maxth – minth)] Thì ta có: Prob [X=n] =(1-Pb)n-1 Pb Do đó X là biến ngẫu nhiên có hình thức (RV) với tham số Pb và E[X] =1/Pb Vấn đề phải đánh dấu các gói tại các khoảng đều đặn. Nếu có quá nhiều gói được đánh dấu gần nhau hay khoảng cách các gói đánh dấu quá dài thì nó có thể gây ra hiện tượng đồng bộ toàn thể các luồng TCP và các kết nối giảm kích thước của sổ tại cùng một thời điểm. Cách 2: Các biến ngẫu nhiên đồng bộ Nếu định nghĩa xác suất loại bỏ gói là Pa Pa = Pb / (1- count * Pb) Count: là số lượng các gói đến ngay sau gói cuối cùng bị đánh dấu Prob[X=n] = = Pb với 1≤ n ≤ 1/ Pb prob[X= n] = 0 với n> 1/Pb Với biến ngẫu nhiên đồng bộ trong số [1,2,3,…1/Pb] với E[X] =1/(2*Pb)+1/2 i: là biến chạy của các gói đến router ngay sau gói cuối cùng bị đánh dấu. b. Chiều dài hàng đợi trung bình và wq Cổng RED sử dụng bộ lọc thông thấp để tính toán kích thước hàng đợi trung bình. Do đó các khoảng thời gian ngắn hạn sẽ tăng tới kích thước hàng đợi đây là kết quả của lưu lượng dạng bó hoặc tắc nghẽn trong suốt chứ không phải là thay đổi trong kích thước hàng đợi trung bình. Bộ lọc thông thấp là trung bình dịch chuyển có trọng số tăng theo luỹ thừa (EWMA): avg ← (1- wq)avg + wq*q Trọng số wq quyết định thời gian của bộ lọc thông thấp. Việc lựa chọn wq quyết định hằng số thời gian cho quá trình tính toán kích thước hàng đợi trung bình. Nếu wq thì kích thước hàng đợi trung bình được đánh giá là đáp ứng quá chậm so với tắc nghẽn trong suốt. Còn nếu wq quá cao thì kích thước hàng đợi trung bình được đánh giá là quá gần với kích thước hàng đợi tức thời. Ta có thể thiết lập các biên giới trên hoặc dưới cho tham số wq. Việc tính toán kích thước hàng đợi trung bình có thể được thực hiện một cách hiệu quả ngay cả khi wq mang cả hai tính chất trên Biên giới trên của wq Nếu wq quá lớn thì các thủ tục sẽ không xác đinh được tắc nghẽn qua gateway. Giả sử ban đầu hàng đợi rỗng (kích thước trung bình =0), sau khi có các gói, số gói trong hàng đợi sẽ tăng từ 0 đến L gói (giả sử có L gói đến hàng đợi), lúc này kích thước hàng đợi trung bình được xác định như sau: avgL = = wq(1-wq)L với: = ta xác định được biên trên đối với wq như sau: avgL = L + 1 + Khi đưa ra giá trị minth tức là ta đã cho phép số lượng các bó của L gói đến gateway. Sau đó trọng số wq sẽ được lựa chọn để thảo mãn avg < minth avgL = L + 1 + < minth Biên dưới của wq Các gateway RED được thiết kế sao cho thuật toán RED luôn giữ kết quả tính toán kích thước hàng đợi trung bình nằm dưới mức ngưỡng nào đó. Tuy nhiên nếu giá trị wq được thiết lập quá chậm thì giá trị avg sẽ đáp ứng chậm với sự thay đổi kích thước hàng đợi trong thực tế. Trong trường hợp này thì các gateway RED không loại bỏ được các mức nghẽn ban đầu. c. Các giá trị ngưỡng: thiết lập giá trị minth,maxth Giá trị tối ưu của minth, maxth phụ thuộc vào kích thước hàng đợi trung bình mong muốn. Nếu lưu lượng đến hàng đợi dưới dạng bó thì giá trị minth phải lớn tương xứng để để cho phép duy trì việc sử dụng các kết nối tại mức cao có thể chấp nhận được. Giá trị minth phụ thuộc chính xác vào việc cân bằng theo mong muốn giữa trễ trung bình thấp và sự tận dụng kết nối cao tại router. Việc thiết lập tối ưu giá trị minth cũng phụ thuộc một phần vào tốc độ kết nối, trễ lan truyền, và kích thước hàng đợi lớn nhất. Giá trị maxth tối ưu phụ thuộc vào trễ trung bình lớn nhất được cho phép bởi gateway. Các gateway hoạt động hiệu quả nhất khi giá trị (maxth- minth) rộng hơn lượng tăng thêm kích thước hàng đợi trung bình được tính toán trong một thời gian Roundtrip. Thường chọn maxth = 3 minth 3.3.4 Phát hiện sớm ngẫu nhiên có trọng số WRED 3.3.4.1 Khái niệm chung Đối với mỗi hàng đợi đưa ra nhà quản lý mạng phải sử dụng nhiều cách quản lý để phòng tắc nghẽn. Thông tin thêm vào từ ngữ cảnh các gói có thể lựa chọn một trong số các chức năng loại bỏ đa gói. WRED là sự pha trộn các chức năng của thuật toán RED với tính năng của trường IP Precedence để cung cấp việc xử lý ưu tiên luồng lưu lượng của các gói có độ ưu tiên cao. WRED có thể loại bỏ các lưu lượng có độ ưu tiên thấp một cách có chọn lọc khi giao diện bắt đầu bị tắc nghẽn và cung cấp các đặc điểm thể hiện khác nhau cho các lớp dịch vụ phân biệt. Nếu cấu hình WRED mà bỏ qua trường IP precedence khi đánh dấu các gói thì thuật toán WRED trở thành thuật toán RED. Đối với các giao diện được cấu hình để sử dụng giao thức đặt trước tài nguyên (RSVP) thì WRED sẽ lựa chọn các gói từ các luồng khác để loại bỏ chứ không loại bỏ các luồng RSVP. Tương tự như vậy các trường IP precedence cũng chi phối các gói bị loại bỏ như với các gói có trường Precedence có độ ưu tiên thấp thì sẽ có tốc độ loại bỏ cao hơn các gói có độ ưu tiên cao trong trường Precedence. WRED khác xa so với các kĩ thuật tránh tắc nghẽn khác như các chiến lược hàng đợi do nó cố gắng đoán trước tắc nghẽn trước khi tắc nghẽn xảy ra và tránh tắc nghẽn chứ không điều khiển tắc nghẽn khi nó đã xảy ra rồi. Vậy ích lợi của WRED là gì? WRED cố gắng phát hiện sớm tắc nghẽn có thể nhất và cung cấp tính năng này cho các lưu lượng đa lớp. Đồng thời nó cũng được bảo vệ chống lại hiện tượng đồng bộ trên toàn thể các luồng TCP. Do đó mà WRED thường được sử dụng nhiều hơn tại các giao diện đầu ra dễ xảy ra tắc nghẽn. Tuy nhiên WRED thường được sử dụng nhiều hơn trong các router lõi của mạng nhiều hơn là trong các router biên. Các router biên chỉ ấn định trường IP Precedence cho các gói ngay khi chúng vào trong mạng. WRED sử dụng các trường này để quyết định cách đối sử như thế nào đối với các lớp lưu lượng khác nhau. WRED cung cấp các mức ngưỡng và các trọng số khác nhau cho các IP Precedence khác nhau, cho phép cung cấp các chất lượng dịch vụ khác nhau cho các lớp lưu lượng khác nhau. Các lưu lượng thông thường có thể bị loại bỏ thường xuyên hơn các lưu lượng được đánh giá cao trong các chu kì tắc nghẽn. Cũng tương tự như RSVP, WRED có thể cung cấp dịch vụ QoS điều khiển tải trong các dịch vụ tích hợp. 3.3.4.2 Hoạt động của WRED Bằng việc loại bỏ sớm các gói trước khi các chu kì có độ tắc nghẽn cao xảy ra, WRED sẽ thông báo về cho nguồn phát các gói biết để giảm tốc độ truyền dẫn. Nếu nguồn phát các gói sử dụng TCP thì nó giảm tốc độ truyền gói cho tới khi các gói đạt được đến đích, lúc này chỉ thị tắc nghẽn sẽ thông báo là tắc nghẽn đã bị loại bỏ. Nhìn chung WRED loại bỏ các gói có lựa chọn dựa trên trường IP Precedence. Các gói có trường IP Precedence cao thì ít bị loại bỏ hơn các gói có IP Precendece thấp. Do đó các gói có độ ưu tiên cao hơn thì xác suất được truyền đi cũng cao hơn. WRED giảm cơ hội loại bỏ đuôi do các gói bị loại bỏ đều được lựa chọn khi giao diện đầu ra bắt đầu có dấu hiệu tắc nghẽn. Bằng cách loại bỏ một số gói sớm hơn là chờ cho hàng đợi đầu mới loại bỏ gói nên WRED tránh loại bỏ một số lượng lớn các gói tại cùng một thời đểm và tối thiểu hoá có hội xảy ra đồng bộ trên diện rộng. Do đó WRED cho phép sử dụng hiệu quả các đường truyền tại mọi thời điểm. Thêm vào, WRED cho phép loại bỏ thống kê nhiều gói hơn tại một nhóm nhiều người sử dụng hơn là nhóm có ít người sử dụng. Do đó, các nguồn lưu lượng mà tạo ra phần lớn lưu lượng thì giảm chậm hơn các nguồn lưu lượng tạo ra ít lưu lượng hơn. Không giống như loại bỏ phần đuôi trong cơ chế tránh tắc nghẽn WRED tránh được các vấn đề xảy ra trên toàn thể các luồng. Đồng bộ toàn thể luồng được biểu thị bằng việc khi các host đa luồng TCP giảm tốc độ truyền dẫn để đáp ứng quá trình loại bỏ gói, sau khi tắc nghẽn được giảm thì chúng sẽ đồng loạt tăng lại tốc độ truyền dẫn. Discard test incoming packets Transmit quue Outgoing packets FIFO scheduling Queue bufler resources Discard test based on: Bufler queue depth IP Precedence RSVP session Hình 3.10 : Mô phỏng hoạt động của WRED WRED chỉ thực sự hiệu quả khi phần lớn lưu lượng là lưu lượng TCP/IP. Trong TCP các gói bị loại bỏ dùng để chỉ thị tắc nghẽn do đó nguồn phát gói sẽ giảm bớt tốc độ truyền dẫn của nó. Còn đối với các giao thức khác thì các nguồn phát gói có thể đáp ứng hoặc gửi lại các gói tại cùng một tốc độ, do vậy mà chúng không làm giảm sút được tắc nghẽn. WRED gán cho các lưu lượng không phải là luồng IP giá trị Precedence 0, giá trị ưu tiên thấp nhất. Do đó mà các lưu lượng không phải là IP thường bị loại bỏ hơn. Chức năng loại bỏ các gói này áp dụng khác nhau đối với các lớp lưu lượng khác nhau tuỳ thuộc vào mức độ ưu tiên. Để hiểu rõ hơn về hoạt động của WRED ta đi vào thuật toán WRED. Lấy ví dụ đơn giản: Giả sử cho hàng đợi có đầu ra đơn, cấu hình chuyển mạch bao gồm WRED có mức ngưỡng 50% cho tất cả các lưu lượng best effort có giá trị DSCP lớn hơn 20, và 80% cho tất cả các lưu lượng có giá trị DSCP trong khoảng 20-30. Trong ví dụ này chuyển mạch sẽ loại bỏ các gói có giá trị DSCP dưới 20 khi đầu ra hàng đợi đạt mức 50%. Nếu hàng đợi tiếp tục được thêm vào quá 80%, thì chuyển mạch bắt đầu loại bỏ các gói có giá trị DSCP lớn hơn 20. Kết quả cuối cùng là tầng chuyển mạch sẽ loại bỏ ít nhất các gói có độ ưu tiên cao. Select WRED Profile No Yes IP Packet WRED Calculacte Average Queue Size Queue Full? FIFO Queue Curent Queue Sieze IP Precedence or DSCP Minimum Threshold Maximum Threshold Maximum Probability Denominator Random Drop Tail Drop Hình 3.11 : Sơ đồ Thuật toán WRED Chính sách tốt nhất là đưa ra hàng đợi có độ ưu tiên chặt cho các lưu lượng có độ ưu tiên cao và sử dụng WRED để duy trì các hàng đợi này cho các lưu lượng dữ liệu. Đối với các chuyển mạch hỗ trợ chức năng loại bỏ đuôi và cấu hình WRED, thì các cấu hình thay đổi phụ thuộc vào số lượng các hàng đợi đầu ra và các modul đường truyền hỗ trợ các mức ngưỡng tối thiểu có thể cấu hình được. Mức ngưỡng tối thiểu chỉ thị độ sâu hàng đợi mà tại mức đó không có gói nào bị loại bỏ. Trong hình dưới đây thì các gói không bị đánh dấu có giá trị ngưỡng nhỏ nhất là min1th,và giá trị ngưỡng lớn nhất là max2th. Các gói bị đánh dấu có các giá trị ngưỡng min2th, max2th. Do các gói chưa bị đánh dấu có khả năng được truyền cao hơn nên được ưu tiên đưa vào hàng đợi nhiều hơn là các gói đã bị đánh dấu ,do đó giá trị min1th > min2th ,và max1th > max2th. Giá trị maxp là xác suất loại bỏ các gói đỉnh của các gói không bị đánh dấu. Khi có hiện tượng tắc nghẽn thì xác suất loại bỏ các gói đã bị đánh dấu sẽ tăng dần đến 1, còn các gói chưa bị đánh dấu thì xác suất chỉ tăng đến maxp, nếu vẫn không khắc phục được tắc nghẽn thì sẽ tiếp tục tăng đến 1. Regular packets 0 Minth2 Minth1 Maxth2 Maxth1 100% 1 Unmarked maxp Drop Probability Queue Occupancy Marked packet Hình 3.12 : Tính năng đánh dấu các gói có thể chỉnh sửa chức năng loại bỏ gói Kích thước hàng đợi trung bình trong thuật toán WRED Router tự động quyết định các tham số được sử dụng trong các toán WRED. Kích thước hàng đợi trung bình dựa trên kích thước hàng đợi trung bình trước đó và kích thước hàng đợi trung bình hiện tại. Công thức: Average = (avg cũ * (1 – 2-n)) + (kích thước hàng đợi hiện tại * 2-n) n : tác nhân trọng số theo luỹ thừa. Với các giá trị n lớn thì kích thước trung bình trước đó trở nên quan trọng. Nếu giá trị n quá lớn thì WRED không có tác dụng đối với tắc nghẽn. Lúc này các gói sẽ bị loại bỏ hoặc được gửi như thể WRED không có hiệu quả. Kích thước hàng đợi trung bình không nên thay đổi quá nhanh. Tiến trình WRED sẽ bắt đầu loại bỏ các gói chậm, nhưng nó có thể tiếp tục loại bỏ các gói tại thời điểm sau khi kích thước hàng đợi thực giảm xuống dưới mức ngưỡng nhỏ nhất. Nhưng nếu n quá nhỏ thì WRED sẽ phản ứng quá mạnh với các bó lưu lượng tạm thời, và việc loại bỏ lưu lượng là không cần thiết. Ta có thể cấu hình WRED tại cùng một giao diện như bộ xử lý chuyển mạch router (RSP) trên cơ sở CQ, hàng đợi ưu tiên (PQ), hay hàng đợi cân bằng có trọng số(WFQ). WRED phục vụ cho các dịch vụ phân biệt(DS) WRED dành riêng cho dịch vụ DS là phần mở rộng của WRED có khả năng hỗ trợ dịch vụ phân biệt và các AFPHB. Tính năng này cho phép các khách hàng thực hiện AFPHB bằng việc đánh dấu các gói theo giá trị DSCP và sau đó ấn định các xác suất loại bỏ ưu tiên cho các gói này. Tính năng này chỉ được sử dụng với các gói IP. WRED dùng cho DS cho phép WRED sử dụng các giá trị DSCP khi nó tính toán xác suất loại bỏ một gói. Loại này có thêm hai câu lệnh: random-detect dscp và dscp. Ngoài ra nó còn có hai luận điểm liên quan: luận điểm trên cơ sở dscp,và trên cơ sở prec. Luận điểm trên cơ sở dscp cho phép WRED sử dụng giá trị DSCP của gói khi nó tính toán xác suất loại bỏ gói. Sau khi sử dụng dscp thì sử dụng lệnh random-detect dscp để thay đổi các mức ngưỡng minth, maxth của các gói theo giá trị DSCP. Còn luận điểm prec cho phép WRED sử dụng giá trị các trường IP Precedence để tính toán xác suất loại bỏ gói. Nếu đã sử dụng dscp thì không thể sử dụng prec với cùng một câu lệnh. 3.3.5 Phát hiện sớm ngẫu nhiên thích nghi ARED 3.3.5.1 Thuật toán Điều khiển tắc nghẽn đầu cuối được sử dụng rộng rãi trong các mạng ngày nay để ngăn chặn tắc nghẽn xảy ra. Tuy nhiên do lưu lượng đến dưới dạng bó, các router được cung cấp các bộ đệm rộng lớn một cách công bằng để thu hút các bó lưu lượng và duy trì việc sử dụng kết nối cao. Bên trong các bộ đệm lớn này có sử dụng quản lý bộ đệm loại bỏ đằng đuôi, nếu xảy ra tắc nghẽn tại các router thì các gói sẽ bị trễ hàng đợi lớn. Do đó quản lý bộ đệm loại bỏ đằng đuôi buộc mạng phải lựa chọn giữa độ sử dụng cao (yêu cầu kích thước hàng đợi lớn) hay độ trễ nhỏ (yêu cầu kích thước hàng đợi nhỏ). Còn quản lý hàng đợi sử dụng thuật toán RED thì tích cực hơn do sử dụng quá trình loại bỏ gói ngẫu nhiên bằng việc thay đổi kích thước hàng đợi trung bình. Mục tiêu chính của RED là phối hợp giữa trung bình hoá chiều dài của hàng đợi (cung cấp lưu lượng dạng bó) và thông báo tắc nghẽn sớm (giảm kích thước hàng đợi trung bình) để đạt được trễ hàng đợi trung bình thấp và độ thông qua cao. Tuy nhiên RED lại có mặt hạn chế: kích thước hàng đợi trung bình thay đổi theo mức tắc nghẽn và các thiết lập tham số. Về cơ bản RED yêu cầu điều chỉnh các tham số để hoạt động hiệu quả thì nó phải loại bỏ đủ các gói để đạt được mục đích. Thật không thích hợp là việc thiết lập các tham số phụ thuộc vào tính tự nhiên và dạng bó của lưu lượng truyền qua hàng đợi trên cơ sở RED. Ta thấy khi kết nối xảy ra tức nghẽn nhẹ hay giá trị maxp cao thì kích thước hàng đợi trung bình sẽ gần giá trị minth, còn khi kết nối bị tắc nghẽn nặng, hay giá trị maxp thấp thì kích thước trung bình hàng đợi gần bằng hoặc lớn hơn maxth. Kết quả là trễ hàng đợi hàng đợi trung bình rất nhạy với tải lưu lượng và tham số do đó không thể dự đoán truớc được. Thêm vào đó độ thông qua trong RED cũng nhạy với tải lưu lượng và tham số. RED thường không hoạt động tốt khi kích thước hàng đợi trung bình vượt quá giá trị maxth, khi vượt quá giá trị này thì khả năng thông qua giảm còn tốc độ loại bỏ gói tin tăng. Giải pháp đưa ra cho vấn đề trên là tìm ra một thuật toán kế thừa được các ưu điểm của thuật toán RED đồng thời hạn chế được nhược điểm của nó. Thuật toán ARED (Adaptive RED-RED thích nghi) là phần mở rộng của thuật toán RED. ARED về cơ bản vẫn dựa trên thuật toán RED nhưng chỉ chỉnh sửa tham số maxp để giữ cho kích thước hàng đợi trung bình luôn nằm trong khoảng minth và maxth. Thêm vào thuật toán ARED tự động thiết lập các tham số khác của RED, nó có thể tối thiểu hoá khả năng kích thước hàng đợi trung bình vượt quá giá trị maxth do đó hạn chế khả năng mất gói và sự dao động trong trễ hàng đợi. Các trọng số dùng để đánh giá ARED Mục đích thứ cấp của RED nói riêng hay của quản lý hàng đợi nói chung là để cung cấp trễ hàng đợi trung bình thấp và độ thông qua cao. Do đó để định giá ARED thì ta sử dụng các trọng số của trễ hàng đợi trung bình và độ thông qua. Mục đích nữa của ARED là giới hạn số lượng các gói bị loại bỏ và tốc độ đánh dấu. Tất cả các trọng số được xây dựng trên cơ sở router. Trong khi các trọng số người sử dụng đầu cuối như: thời gian chuyển file, hay độ trễ trên gói là các kết quả đo quan trọng có hiệu quả với thuật toán thì các trọng số người sử dụng đầu cuối cho thuật toán ARED có thể dễ dàng nhận được từ các trọng số trên cơ sở router Hoạt động của thuật toán ARED ARED thích ứng giá trị maxp để giữ cho kích thước hàng đợi trung bình nằm trong khoảng giá trị minth và maxth. Để đạt được điều này có 4 cách: Maxp được thích ứng không chỉ giữ cho kích thước hàng đợi trung bình nằm giữa hai giá trị minth và maxth mà còn giữ cho kích thước hàng đợi trung bình nằm trong một giải cho phép trong khoảng minth và maxth. Maxp thích nghi chậm, thời gian vượt quá được chia lớn hơn thời gian roundtrip và trong những bước nhỏ. Giá trị maxp được duy trì trong khoảng [0.01 ; 0.5] 0 Minth Maxtth 100% 1 maxp maxp Curve for Aggressive traffic Curve for Light traffic Average occupancy Drop Probability Hình 3.13 : Phát hiện sớm ngẫu nhiên thay đổi thích ứng với maxp thay đổi Thay cho việc tăng theo cấp số nhân và giảm giá trị maxp ta thực hiện chế độ giảm theo cấp số nhân và tăng theo cấp số cộng (AIMD). Thuật toán ARED: Every interval seconds: If (avg > target and maxp ≤ 0.5) Tăng giá trị maxp maxp ← maxp + α; else if (avg < target and maxp ≥ 0.01) giảm maxp ; maxp ← maxp * β ; Các biến : avg : kích thước hàng đợi trung bình Các tham số cố định : interval : khoảng thời gian khoảng 0,5 s target : giá trị mong đợi cho avg nằm trong khoảng [minth + 0.4 * (maxth - minth) ; minth + 0.6 * (maxth - minth)] α : nhân tố tăng ; min (0.01 ; maxp/4) β : nhân tố giảm ; 0.9 Chính sách tương thích giá trị maxp cho phép giá trị xác suất loại bỏ gói Đáp ứng được với sự thay đổi của kích thước hàng đợi trung bình để có thể chiếm ưu thế trong các khoảng thời gian nhỏ. Việc thích ứng chậm giá trị maxp, ARED đưa ra hiệu quả sử dụng cao trong một dải rộng các môi trường. Thuật toán ARED trong hình trên sử dụng AIMD tương thích maxp. Ngoài cách này ra còn có một cách điều khiển tuyến tính khác là MIDC (tăng theo cấp số nhân, giảm theo cấp số nhân) cũng được yêu cầu để quản lý hàng đợi. 3.3.5.2 Các tham số của ARED a. Giá trị maxp Giới hạn trên của giá trị maxp=0.5 có thể được chỉnh sửa theo cách: Cố gắng tối ưu RED để tốc độ loại bỏ gói tin 2maxp. Còn khi tốc độ loại bỏ gói giảm từ 1→ maxp khi kích thước hàng đợi thay đổi từ minth→ maxth. Do đó với giá trị Maxp được thiết lập tới giá trị 0.5 thì xác suất loại bỏ các gói thay đổi từ 0→ 1 khi kích thước hàng đợi thay đổi từ Minth→ 2Maxth. Điều này giúp cho hiệu năng truyền lớn ngay cả khi tốc độ loại bỏ gói vượt quá 50%. b. Tham số α, β Có ít nhất 0.49/α khoảng giành cho giá trị maxp để tăng từ 0.01→ 0.5 (với tham số đưa ra là 24.5s). Tương tự có ít nhất log0.02/logβ khoảng cho giá trị maxp để giảm từ 0.5→ 0.01(với tham số là 20.1s). Khi xét đến giá trị α, β yêu cầu đặt ra là ngay cả khi hoạt động dưới điều kiện bình thường thì bất kì một chỉnh sửa đơn nào của giá trị maxp cũng không ảnh hưởng tới sự thay đổi của kích thước hàng đợi trung bình Khi giá trị maxp được thích ứng với xác suất loại bỏ gói trạng thái ổn định p cũng được duy trì và kích thước hàng đợi trung bình dịch chuyển đơn giản để phù hợp với giá trị maxp mới. Do đó p < maxp khi maxp tăng bởi α, và giá trị hàng đợi trung bình có thể giảm từ giá trị minth + (maxth - minth) tới minth + (maxth - minth) Nó là sự giảm của giá trị: + (maxth - minth) Giá trị maxp nhỏ hơn 0.2(maxth- minth), do đó kích thước hàng đợi trung bình không phụ thuộc vào giá trị maxp và để tránh hiện tượng kích thước hàng đợi giảm đột ngột từ giá trị biên trên xuống giá trị biên dưới. Tham số α, β phải thoả mãn: ≤ 0.2 với α < 0.25 maxp Tương tự có thể kiểm tra việc giảm maxp theo cấp số nhân để không gây ra hiện tượng kích thước hàng đợi trung bình tăng từ giá trị biên giới tới giá trị biên trên. Phân tích tương tự như α: (maxth - minth) < 0.2(maxth - minth) Chọn β: ≤ 0.2 ; β > 0.83 c. Thiết lập các tham số maxth và wq ARED loại bỏ sự phụ thuộc của RED vào tham số maxp và một số tham số khác thì ta có thể tự động thiết lập tham số maxth,wq. Giá trị Maxp sẽ được tự động thiết lập từ giá trị 3minth. Trong trường hợp này thì kích thước hàng đợi trung bình tập trung xung quanh giá trị 2minth do đó nó chỉ chịu ảnh hưởng của tham số minth của RED. Tham số wq: nếu kích thước hàng đợi trung bình thay đổi từ giá trị này sang giá trị khác thì số lượng các gói đến là -1/ln(1-wq). Giá trị này được gọi là “hằng số thời gian”. Nó được chỉ định trong các gói đến để đánh giá kích thước hàng đợi trung bình, nhưng bản thân nó lại không mang tính chất thời gian. Các kết nối có tốc độ cao hơn yêu cầu giá trị wq nhỏ hơn, do đó “hằng số thời gian” được duy trì theo trật tự của RRT. wq được thiết lập tự động là 1s (tương đương với 10 RTT) để đánh giá kích thước hàng đợi trung bình. Giả sử rằng RTT mặc định là 100ms thì wq được thiết lập: wq = 1- exp(-1/C) C : là khả năng kết nối các gói trên 1s, được tính bắng số các gói trên một kích thước mặc định đã được chỉ ra. 3.3.6 RED với các cổng vào ra (RIO-RED with In/Out) 3.3.6.1 Giới thiệu chung về RIO Trong chương 1 đã giới thiệu về các dịch vụ DS. Nhìn chung kiến trúc DS nhằm mục đích cung cấp QoS có đảm bảo tại mức các luồng được tổng hợp. Nó phân loại các gói tin IP thành các nhóm lưu lượng nhỏ hơn tuỳ theo các giá trị DSCP được đánh dấu trong tiêu đề gói IP tại các đường biên của mạng. Trong lõi mạng chúng sẽ được truyền theo các PHB tương ứng. DS không yêu cầu duy trì trạng thái luồng, hay các tiến trình báo hiệu bên trong các mạng lõi, do đó nó giảm bớt gánh nặng làm việc cho các router trong mạng lõi. Các router biên trong các mạng DS giám sát và đánh dấu các gói của luồng lưu lượng. Các gói tuân theo các profile của người sử dụng sẽ được đánh dấu là “In profile” còn các gói nằm ngoài các profile dịch vụ sẽ được đánh dấu là out profile. Một thuật toán được hỗ trợ bên trong các router lõi của mạng phân biệt là RIO (phát hiện sớm ngẫu nhiên vào ra). Trong suốt quá trình tắc nghẽn các gói có profile out sẽ bị loại bỏ trước các gói In profile. Với các chính sách loại bỏ gói, các AFPHB sẽ đưa ra quyền ưu tiên cho các gói In và cung cấp các mức dịch vụ khác nhau cho người sử dụng trên cơ sở các proifile dịch vụ của họ. Để điều khiển tắc nghẽn cho các luồng được tổng hợp trong mạng DS ta có thể sử dụng lược đồ điều khiển tắc nghẽn từ biên tới biên (edge to edge congestion control scheme-E2E-CCS). Trong lược đồ này thì gói điều khiển QoS được gửi từ các router bên trong ra các router bên ngoài tại mỗi khoảng thời gian cố định. Các router bên trong sử dụng thuật toán để điều chỉnh tốc độ gửi của luồng theo thông tin QoS được phản hồi về từ các router biên. Ta đang xét thuật toán RIO trong mạng DS. Kiến trúc một mạng DS bao gồm 2 loại router: router biên và router lõi. Các router biên được lắp đặt tại đường biên của các mạng, nó hỗ trợ cho các điều kiện lưu lượng như: phân lớp, định dạng, và đánh dấu gói tin. Còn các router lõi được lắp đặt bên trong mạng, cung cấp chức năng phân loại đơn giản và một số chức năng định hướng khác. Các router biên lại bao gồm các node đầu ra và các node đầu vào vùng DS. E2E-CCS coi các router đầu vào và đầu ra cũng như phía thu và phía phát các gói điều khiển QoS. Phía phát sẽ gửi các gói tin điều khiển trong cùng một nhóm tới phía thu để tại các khoảng thời gian T đều đặn. Gói điều khiển được sử dụng để truyền các thông tin QoS giữa các router đầu ra và router đầu vào. Khi router đầu ra nhận được gói điều khiển, nó sẽ tính toán tốc độ đầu ra của các gói In và Out được đánh dấu bởi ECN. Các router đầu ra sau đó sẽ điền các tham số QoS vào các trường tương ứng trong các gói điều khiển và gửi chúng ngược trở lại router đầu vào. Các gói điều khiển luôn có mức ưu tiên cao nhất trong các mạng DS. Khi các router đầu vào nhận được các gói điều khiển phản hồi từ các router đầu ra thì nó sẽ chỉnh sửa tốc độ gửi trong các thông tin QoS đặt trong các gói điều khiển. Thuật toán quản lý hàng đợi của router lõi là thuật toán RIO, có thể được xem như sự phối hợp của hai thuật toán RED với các xác suất loại bỏ gói tin khác nhau cho các gói In và các gói Out. Do đó nó cũng có hai bộ giá trị ngưỡng giống như trong RED: (minth(in), maxth(in) ,maxp(in)) và (minth(out) maxth(out), maxp(out)), được sử dụng cho việc tính toán xác suất loại bỏ các gói In, Out. Thông thường các tham số của các gói Out được thiết lập cao hơn các gói In để có thể loại bỏ các Out trước khi có bất kì một gói In nào bị loại bỏ. Thêm vào đó kích thước hàng đợi trung bình của các gói Out được tính toán dựa trên cơ sở tổng các gói (gói In và các gói Out) trong hàng đợi. Trong khi kích thước hàng đợi trung bình của các gói In chỉ được tính toán dựa trên các gói In. Traffic Classifier T C T C Rate Controler QoS controller Hander To network core router QoS control packet from egress router Incoming traffic from end Host Cấu trúc router đầu vào Hình 3.14 : Cấu trúc router đầu vào TC (Traffic Controller) : bộ điều khiển lưu lượng Rate Controller : bộ điều khiển tốc độ Traffic Classifier : bộ phân loại lưu lượng Tại các router đầu vào mạng lưu lượng đến đầu tiên sẽ được phân loại trong các tập hợp lưu lượng theo các giá trị DSCP được đánh dấu trong phần tiêu đề của gói tin. Mỗi tập hợp này được giám sát bởi bộ điều phối lưu lượng để đánh giá tốc độ tổ hợp lưu lượng hiện hành và phải chắc chắn rằng mỗi tổ hợp lưu lượng này sẽ không vượt quá tốc độ thông tin đỉnh của nó. Các lưu lượng mà vượt quá tốc độ có thể cho phép thì sẽ bị loại bỏ và bị đánh dấu lại để ngăn chặn việc các luồng lưu lượng này chiếm giữ tài nguyên mạng nhiều hơn tìa nguyênđã được chia sẻ. Bộ điều khiển tốc độ điều chỉnh tốc độ đầu ra của bộ điều phối lưu lượng theo các tham số đã được ấn định trong các gói điều khiển QoS khi nó được phản hồi lại từ các router đầu ra. Cấu trúc router đầu ra Về cấu trúc thì các router đầu ra tương tự như các router đầu vào. Bộ giám sát lưu lượng có thể đáp ứng cho việc đánh giá tốc độ đến của các gói In và Out với số đo profile TSW (Time Sliding Window - cửa sổ trượt thời gian) và ghi lại số lượng các gói In, Out nhận được trong suốt các khoảng thời gian đều đặn T. Traffic classifier T C T C QoS controller Hander Incoming traffic from core Router QoS control packet to ingress Router Hình 3.15 : Cấu trúc router đầu ra Thuật toán điều khiển tốc độ gói In và Out cho cả router đầu vào và đầu ra Tại mỗi khoảng thời gian T Router cổng vào sẽ nhận các gói điều khiển QoS If Ns = Nr then If ENrIn > 0 then giảm tốc độ của các gói In và Out else if ENrOut > 0 then giảm tốc độ gửi của các gói Out else tăng tốc độ gửi else giảm tốc độ gửi của cả gói In và Out Kí hiệu: Ns : số lượng các gói gửi tại router đầu vào Nr : số lượng các gói nhận được tại router đầu ra. ENrIn : số lượng các gói In nhận được router đầu ra với ECN = 1 ENrOut : số lượng các gói Out nhận được tại router đầu ra với ECN =1 Tại router đầu vào, thuật toán tăng đơn giản thực hiện chức năng tăng tốc độ gửi Rs: Rs = Rs * (1+ α) 0< α < 1 Trong E2E-CCS thuật toán giảm được sử dụng để chỉnh sửa tốc độ gửi của các gói In và Out tuỳ theo thông tin điều khiển QoS nhận được. Thuật toán giảm: If ENrOut > 0 then Rs = RrIn + RrOut * β Với 0 < β < 1 , RrIn và RrOut là tốc độ đầu ra của các gói In và Out tại các router cổng ra. Và If ENrIn > 0 or Ns Nr then Rs = RrIn * γ Với 0< γ < 1 3.3.6.2 Thuật toán RIO RED có các cổng vào ra In/Out (RIO) là cơ chế AQM cơ sở phù hợp cho bộ AF PHB. RIO là phần mở rộng của RED sử dụng hai tập các tham số để phân biệt loại bỏ các gói In(In profile) và các gói ngoài Out(out profile). Để quyết định khi nào loại bỏ các gói Out thì RIO sử dụng kích thước trung bình của tổng chiều dài hàng đợi. RIO sẽ được mở rộng để xử lý n>2 precedence cho cùng một nguyên lý. Xác suất loại bỏ các gói của Precedence 1≤ j <n phụ thuộc vào kích thước trung bình của hàng đợi ảo chứa các gói có Precedence từ 1 tới j. Với các gói có mức precedence n (ví dụ là ưu tiên thấp nhất), xác suất loại bỏ các gói là chức năng của độ chiếm giữ trung bình của hàng đợi vật lý. Cách thức ban đầu này còn gọi là RIO-C (RIO coupled) để phân biệt với các cách thức sau đó. Ví dụ WRED sử dụng kích thước hàng đợi trung bình tổng cho tất cả precedence trong khi RIO-DC (RIO decoupled) tính toán xác suất mất gói của precedence j như một chức năng của số lượng trung bình các gói có cùng một Precedence. RIO-C phân biệt các gói theo các precedence theo 3 cách. Cách thứ nhất sử dụng các mức ngưỡng khác nhau cho các precedence khác nhau, do đó các gói có precedence thấp sẽ bị loại bỏ trước các gói có độ ưu tiên cao hơn. Cách thứ hai là sử dụng xác suất loại bỏ tăng tại tốc độ khác nhau cho các độ ưu tiên khác nhau. Cách thứ 3 nằm trong tính toán kết hợp của xác suất loại bỏ gói. Trên thực tế xác suất loại bỏ gói có precedence j sử dụng số lượng trung bình các gói của tất cả các precedence thấp hơn. Hai cách đầu tiên dựa trên việc thiết lập đơn giản các tham số khác nhau do đó chúng không loại trừ lẫn nhau. Bên cạnh đó RIO được dùng để hỗ trợ cho các bộ điều khiển tốc độ để quyết định xem nên điều chỉnh tốc độ như thế nào cho hợp lý tại các router đầu vào. Trong cơ chế E2E-CCS các router lõi giám sát hàng đợi đầu ra và đánh dấu các bit ECN trong các gói đến một cách ngẫu nhiên. Do đó điều khiển tắc nghẽn sẽ được thực hiện khi độ chiếm giữ hàng đợi trong router lõi bắt đầu đạt tới mức ngưỡng hiện thời. Bên trong mạng, tại các Router sẽ không có sự chia sẻ lưu lượng từ phía người sử dụng trong các luồng khác nhau hoặc trong các hàng đợi. Các gói của tất cả các người sử dụng được tậphợp lại trong một hàng đợi. Các người sử dụng khác nhau có các Profile khác nhau do họ có số lượng các gói In trong hàng đợi khác nhau. Thuật toán RIO: For arrival packet If là gói In Tính toán kích thước hàng đợi In trung bình avgin Else tính toán kích thước hàng đợi tổng avgtotal If là gói In If minin ≤ avgin < maxin Tính toán xác suất Pin; với Pin là xác suất loại bỏ gói else if maxin ≤ avgin Loại bỏ gói này If là gói Out If minout ≤ avgtotal < maxout Tính toán xác suất Pout; với Pout là xác suất loại bỏ gói này else if maxout ≤ avgtotal loại bỏ gói này Bằng cách lựa chọn các tham số để thể hiện thuật toán, RIO có thể đối xử với các gói Out khác nhau tại thời điểm tắc nghẽn và ưu tiên loại bỏ gói khi có tắc nghẽn xảy ra. Nhìn chung mỗi khi có gói đến router sẽ kiểm tra xem gói đó là gói In hay gói Out. Nếu là gói In router sẽ tính toán avgin (kích thước hàng đợi trung bình của gói In), nếu nó là các gói Out, router sẽ tính toán các avgtotal (kích thước hàng đợi trung bình của các gói Out). Xác suất loại bỏ các gói In phụ thuộc vào avgin , xác suất loại bỏ các gói Out phụ thuộc vào avgout. Hoạt động của thuật toán RIO 3 tham số minin, maxin, Pmax(in) , định nghĩa khoảng hoạt động bình thường của RIO [0 ,minin), pha thứ 2: tránh tắc nghẽn [minin , maxin) và điều khiển tắc nghẽn [maxin , ∞) đối với các gói In. Tương tự với các gói Out ta lựa chọn được các tham số: minout ,maxout , Pmax(out). Việc phân biệt đối xử các gói Out được thực hiện bằng việc lựa chọn các tham số: Lựa chọn minoutPmax(in). Thứ 3: các gói Out sẽ tiến tới pha điều khiển tắc nghẽn sớm hơn các gói In khi thiết lập maxout<<maxin. Tóm lại RIO sẽ loại bỏ các gói out đầu tiên ngay khi có dấu hiệu của tắc nghẽn xảy ra, và nó sẽ loại bỏ toàn bộ các gói Out khi có tắc nghẽn. Trong thuật toán RIO trên thì sử dụng avgtotal để quyết định xác suất loại bỏ các gói Out, router có thể duy trì kích thước hàng đợi bé và khả năng thông qua cao mà không ảnh hưởng tới các lưu lượng trộn trong đó. Trong lược đồ điều khiển tắc nghẽn thì việc tăng hay giảm tốc độ gửi của tập hợp các luồng là một vấn đề quan trọng. Tại các router đầu vào, thuật toán điều khiển việc tăng hay giảm các luồng lưu lượng đầu vào dựa trên các thông tin điều khiển QoS. Tần số đưa ra quyết định này phụ thuộc vào việc thay đổi tốc độ có thường xuyên hay không. Trong lược đồ này khi các router đầu vào nhận được các gói điều khiển từ router đầu ra, nó sẽ thay đổi tốc độ theo các chức năng quyết định và các thuật toán tăng, giảm. Do đó tần số quyết định của E2E-CCS được quyết định bởi việc các router đầu vào có thường xuyên gửi các gói điều khiển QoS hay không. Tần số quyết định hay T được thiết lập tới giá trị RTT ngắn nhất giữa các router đầu vào và đầu ra trong trường hợp không có tắc nghẽn. 3.3.7 Thuật toán RIO thích ứng (ARIO) Một phần mở rộng của thuật toán RIO là thuật toán ARIO (Adaptive RIO) được dùng trong quản lý hàng đợi tích cực. Thuật toán ARIO là sự pha trộn của hai thuật toán ARED và RIO. Mục đích chính của thuật toán ARIO là: Đơn giản hoá cấu hình của các router hỗ trợ DS bằng việc làm giảm bớt các vấn đề trong việc thiết lập các tham số trong hầu hết các thuật toán ARED hiện thời. Tự động biên dịch các tham số của QoS thành bộ các tham số của Router. Cố gắng giữ cho độ chiếm giữ hàng đợi ổn định xung quanh giá trị cuối cùng bên dưới các tải mạng nặng. ARED là sự mở rộng trực tiếp của các thuật toán ARED và RIO-C. Cũng giống như thuật toán ARED, ARIO cần một tham số đầu vào đơn, trễ cần đạt tới, được biên dịch thành bộ các tham số router được yêu cầu. Tính năng này có thể rất hữu ích đối với việc cung cấp các dịch vụ phân biệt: cấu hình các router trong nhóm các trễ, trọng số QoS có liên quan trực tiếp tới việc định rõ dịch vụ và các yêu cầu khách hàng nên nó sẽ đơn giản nhóm các tham số như các mức ngưỡng hàng đợi, xác suất loại bỏ các gói, trọng số trung bình. ARIO cố gắng để đạt được khả năng thông qua lớn nhất trong khi vẫn kiểm soát được độ trễ trong biên giới đã định trước, các khoảng thời gian có thể đoán trước được trong khi tải hàng đợi vẫn cao. Trong ngữ cảnh của dịch vụ phân biệt, phải nhận thức đúng các gói được đánh dấu với các trường Precedence tương ứng. Do đó thuật toán ARIO dựa trên hai nguyên lý: Thứ nhất là việc sử dụng thuật toán ARED cho mỗi mức Precedence trong lớp AF (hàng đợi vật lý). Nguyên lý thứ hai là sử dụng các mức ngưỡng chồng chéo hoàn toàn cho tất cả các Precedence. Một số diểm chính trong ARED vẫn được giữ nguyên trong ARIO: Các tham số tương thích, maxp thay đổi trong khoảng 0.001đến 0.5 Mức ngưỡng thấp nhất minth được tính toán như một chức năng của độ trễ theo yêu cầu dt và khả năng kết nối C (gói/s) có mức biên thấp nhất là 5 gói. Do đó minth=max(5,dt.C/2). Mức ngưỡng cao nhất maxth được gắn cố định là giá trị 3minth. wq cũng được tính toán trong cùng nhóm băng thông kết nối như wq=1-exp(-1/C). Biến số của RED được sử dụng thông qua, khoảng cách maxth ≤avg ≤ 2maxth. Chức năng thích ứng của maxp sử dụng luật AIMD. Mục đích của luật này để tránh sự thay đổi mạnh trong giá trị maxp do đó tránh được dao động mạnh trong kích thước hàng đợi. Nếu tải thay đổi bất ngờ, kích thước hàng đợi trung bình có thể tìm ra khoảng thời gian hợp lý. Các nhân tố tăng và giảm α và β được gắn cố định do đó kích thước hàng đợi trung bình có thể khôi phục lại được trong khoảng thời gian ít hơn 25s. Quyết định thiết kế ARIO nhằm mục đích thoả mãn độ trễ theo yêu cầu, đồng thời giữ cho kích thước hàng đợi trung bình trong khoảng (qlow,qhigh), khi qlow = minth+0.4 (maxth- minth) và qhigh = minth+0.6 (maxth-minth). Để hiểu rõ hơn ta xét hàng đợi RIO-C với các mức ngưỡng không bị chồng chéo. Các precedence là 1(In) và 2(Out). Nếu tổng tốc độ In thấp được so sánh với khả năng kết nối mà ở dưới mức tải nặng thì các mức ngưỡng Out và xác suất loại bỏ gói tin sẽ được kích hoạt để giữ kích thước hàng đợi trung bình trong khoảng min2 và max2. Tuy nhiên hầu hết lưu lượng là In nên kích thước hàng đợi trung bình sẽ là giá trị trong khoảng min1 và max1. Do đó các mức ngưỡng so le có thể đem lại các kích thước hàng đợi trung bình khác nhau cho các hỗn hợp lưu lượng khác nhau. Đây cũng chính là mặt hạn chế cho việc dự đoán trước trễ của các hàng đợi khi có trễ toàn bộ hay một phần. Do đó yêu cầu phải sử dụng cùng các mức ngưỡng cho tất cả các Precedence. Theo cách này cơ chế thích ứng của ARED nên đẩy kích thước hàng đợi trung bình tới cùng một khoảng thời gian biên không quan tâm tới trộn lưu lượng. Tuy nhiên việc sử dụng các mức ngưỡng có liên quan tới sự phân biệt. RIO-C phân biệt loại bỏ theo 3 cách: phân biệt các mức ngưỡng, phân biệt các chức năng loại bỏ, và kết hợp các hàng đợi ảo. Trong ARIO có sử dụng các mức ngưỡng chồng chéo nên ARIO không theo cách thứ nhất mà chỉ sử dụng theo hai cách dưới. Thuật toán ARIO: For mỗi gói đến có giá trị precedence I ; For mỗi giá trị precedence j = i, i+1,2,….n Tính toán lại giá trị avgj ; avg(j) ← avg(j) * (1- wq) + q(j) * wq mỗi thời gian interval tính toán lại maxp(j): if avg(j) > qhigh and maxp(j) < 0.5 tính toán tác nhân tăng: α← min(0.001 ; maxp(j)/4) tăng maxp(j): maxp(j) ← maxp(j) + α if j < n then: maxp (j) ← min(maxp(j), maxp(j+1)) else if avg(j) 0.01 giảm maxp(j): maxp(j) ← maxp(j) * β if j > 0 then: maxp(j) ← max(maxp(j) , maxp(j-1)) if minth < avg(i) ≤ maxth Tính toán p(i) như trong RED loại bỏ các gói có xác suất p(i) else if maxth < avg(i) ≤ 2* maxth Tính toán pgentle(i) như trong RED loại bỏ các gói có xác suất pgentle(i) else if avg(i) > 2 * maxth loại bỏ gói này Các tham số cố định và các biến: avg(i) : kích thước hàng đợi trung bình cho precedence thứ i (bộ đếm sẽ đếm số lượng các gói với giá trị precedence từ 1 tới i) maxp(i) : xác suất loại bỏ gói có precedence i khi giá trị avg(i) = maxth p(i) : xác suất loại bỏ gói cho precedence i pgentle(i) : xác suất loại bỏ gói có precedence i trong miền gentle interval : 0.5 s β (nhân tố tăng) : 0.9 Lưu ý rằng maxp(i) ≤ maxp(i+1) , i {1,2,…n-1} 3.3.8 Phát hiện sớm ngẫu nhiên cân bằng FRED RED không chắc chắn rằng lưu lượng cùng được chia sẻ băng tần công bằng. Trên thực hiện tế, RED không đối xử công bằng với các luồng TCP tốc đọ thấp bởi RED ngẫu nhiên loại bỏ các gói khi vượt quá mức ngưỡng max, do đó mỗi gói trong số các gói đó có băng thông nhỏ hơn băng thông được chia sẻ công bằng. Khi các luồng TCP có quá nhiều gói bị mất thì chúng cũng yêu cầu nhiều hơn các chức năng cửa sổ điều khiển tắc nghẽn,do đó tốc độ sẽ càng thấp hơn. FRED là một biến thể của RED để giảm tính không công bằng trong phân bố băng thông. FRED hoạt động giống như RED nhưng có thêm một số chức năng mới: FRED đưa ra thêm hai tham số maxq và minq là số lượng các gói lớn nhất và nhỏ nhất trong mỗi luồng được phép đưa vào hàng đợi. Ngoài ra FRED còn có thêm biến toàn cục avgcq, đánh giá kết quả đếm bộ đệm trên mỗi luồng trung bình. Khi một luồng có số lượng các gói trong hàng đợi nhỏ hơn avgcq thì chúng sẽ được ưu tiên hơn. FRED sẽ duy trì số đếm qlen của các gói được đệm cho mỗi luồng mà đã có bất kì gói nào đó trong bộ đệm. FRED duy trì biến strike để đếm thời gian mà một luồng trượt đáp ứng với các thông báo tắc nghẽn. FRED cho phép mỗi kết nối được đưa vào bộ đệm số lượng các gói có giá trị minq mà không bị loại bỏ. Tất cả các gói thêm vào đều bị loại bỏ bởi RED. Các gói đến được chấp nhận nếu kết nối có ít hơn minq được đệm và kích thước hàng đợi trung bình nhỏ hơn maxth. Thông thường một kết nối TCP gửi ít hơn 3 gói ngược trở lại: hai gói cho trễ ACK, một gói để điều khiển tăng kích thước cửa sổ. Do đó minq được thiết lập từ 2 đến 4 gói tin. Khi số lượng các kết nối tích cực nhỏ(N<< minth/minq), FRED cho phép mỗi kết nối được đệm minq các gói mà không bị loại bỏ. Nó cũng tăng từ giá trị minq tới kích thước hàng đợi trung bình trên một kết nối (avgcq). Một cách đơn giản, nó tính toán giá trị này bằng cách phân chia kích thước hàng đợi trung bình bằng việc sử dụng số lượng các kết nối tích cực. Một kết nối là tích cực khi nó có các gói được đưa vào trong bộ đệm và kết nối thu động trong trường hợp ngược lại. FRED không bao giờ để các luồng tới bộ đệm có số lượng các gói lớn hơn maxq gói tron bộ đệm, và đếm thời gian mỗi luồng để cố gắng vượt quá giá trị maxq trong biến strike của mỗi luồng. Các luồng có giá trị strike cao đều không được cho phép tới hàng đợi có nhiều hơn avgcq gói. Vì vậy chúng không cho phép sử dụng nhiều gói hơn luồng trung bình. Điều này cho phép thích ứng các luồng để gửi các bó gói. RED ban đầu định giá kích thước hàng đợi trung bình tại mỗi gói đến. Trong FRED trung bình được thực hiện tại các gói đến và đi. Do đó tần số lấy mẫu là giá trị lớn nhất của tốc độ đầu vào và tốc độ đầu ra. FRED không chỉnh sửa độ trung bình nếu gói tới bị loại bỏ trừ khi kích thước hàng đợi tạm thời bằng 0. 3.4 So sánh các kĩ thuật quản lý bộ đệm 3.4.1 So sánh RED và Tail Drop Thuật toán Tail Drop hoạt động đơn giản hơn so với thuật toán RED. Tail Drop không có sự chia sẻ giữa các luồng khác nhau. Không có các chính sách gửi nhiều gói để nâng cao hiệu năng dịch vụ. So sánh xác suất loại bỏ gói lưu lượng đầu vào dạng bó : Khi lưu lượng đầu vào dưới dạng đầu vào dưới dạng bó, quá trình các gói đến dưới dạng quá trình poisson có tốc độ đến là λ và các bó đến có số lượng gói là B. Thời gian phục vụ có phân bố mũ là μ-1 . Tải được cung cấp là p = Bλ/μ. Số lượng các gói được đệm trong hàng đợi có dạng chuỗi Markov với phân bố dừng là π. Hình 3.16 : So sánh xác suất loại bỏ gói của Tail Drop và RED Ta thấy trong điều kiện tải cung cấp thấp thì xác suất loại bỏ gói của RED cao hơn so với Tail Drop, khi tải cung cấp tăng thì xác suất loại bỏ gói gần như nhau. Thực chất Tail Drop đơn giản hơn thuật toán RED. So sánh độ trễ Lưu lượng đầu vào dạng bó có tốc độ λ, quá trình đến là quá trình poisson. Phân phối dừng của hai phương pháp : Tail Drop : ΠTD(k) = Với k= 0,….K RED : ΠRED(k) = Với k= 0,….K Ta thấy thuật toán RED có ưu điểm là giảm trễ latency nhưng vẫn làm tăng jitter. Trễ biến thiên trong RED, còn đối với Tail Drop thì khi p tăng thì độ trễ cũng tăng, tuy nhiên trễ không biến thiên nhiều. Tail Drop không có sự ưu tiên lưu lượng nên ngay cả khi có luồng lưu lượng quan trọng đến hàng đợi mà kích thước hàng đợi vượt quá giá trị lớn nhất thì gói đó vẫn bị loại bỏ. Nó quản lý kích thước hàng đợi không linh hoạt như trong thuật toán RED. Khi đầu ra của hàng đợi đầy, Tail Drop sẽ hoạt động, các gói sẽ được loại bỏ cho tới khi tắc nghẽn được đánh giá lại và kích thước hàng đợi giảm xuống. Còn RED sẽ tránh ảnh hưởng xấu của Tail Drop trong các phiên TCP khi tắc nghẽn bị tạo ra bởi đa luồng TCP tích cực. Hình 3.16: Hàm phân bố dừng của Tail Drop và RED với p=2 3.4.2 So sánh thuật toán RED và thuật toán Blue Một vấn đề quan trọng trong quản lý hàng đợi bằng thuật toán Blue là điều khiển tắc nghẽn có thể được thể hiện bởi kích thước hàng đợi nhỏ nhất. Trong khi đó thuật toán RED thì lại yêu cầu kích thước hàng đợi lớn hơn cho cùng một mục đích. Do có kích thước bộ đệm nhỏ hơn nên Blue có trễ đầu cuối qua mạng nhỏ hơn so với sử dụng thuâtk toán RED, do đó nó cải thiện được nhược điểm của thuật toán điều khiển tắc nghẽn. Thêm vào đó các yêu cầu kích thước bộ đệm nhỏ hơn cho phép có nhiều bộ nhớ hưon để phân phối cho các gói có độ ưu tiên cao và giải phóng bộ nhớ trong router để cho các chức năng khác như : lưu trữ các bảng định tuyến lớn. Blue cho phép các router thế hệ sau hoạt động tốt thậm chí trong cả trường hợp tài nguyên bộ nhớ bị giới hạn. Tuy nhiên thuật toán Blue ít nhạy với các chọn lựa tham số hơn là đối với RED. 3.4.3 So sánh các thuật toán RED Chỉ so sánh RED và ARED để thấy được ưu điểm của ARED so với RED Thuật toán ARED là phiên bản tiếp theo của RED do đó ARED khắc phục được mặt hạn chế của RED : RED quản lý hàng đợi dựa trên kích trước trung bình của hàng đợi nên kích thước trung bình hàng đợi thay đổi theo các mức tắc nghẽn và quá trình thiết lập các tham số. Điều này được thể hiện bằng việc khi tắc nghẽn xảy ra nhẹ hay maxp cao thì kích thước hàng đợi gần tới giá trị minth . Khi tắc nghẽn trong mạng nặng hay kích thước hàng đợi trung bình bằng hoặc lớn hơn maxth . Kết quả trễ hàng đợi trong thuật toán RED phụ thuộc vào tải lưu lượng và các tham số, do đó mà trễ hàng đợi không thể đoán trước. Một nhược điểm nữa của RED là khả năng thông qua trong thuật toán này cũng phụ thuộc nhiều vào tải lưu lượng và các tham số. Do thuật toán ARED quản lý kích thước trung bình của hàng đợi dựa trên việc tương thích giá trị maxp sao cho kích thước trung bình hàng đợi thay đổi trong khoảng minth và maxth nên khắc phục được sự phụ thuộc của trễ hàng đợi và khả năng thông qua của hàng đợi vào các tham số và tải lưu lượng. Tổng kết chương Chương 3 giói thiệu sơ lược về các thuật toán quản lý hàng đợi. Các thuạt toán quản lý hàng đợi bao gồm thuật toán Blue, Tail Drop, thuật toán RED. Mỗi thuật có các ưu điểm và nhược điểm riêng, phù hợp với các tham số lưu lượng khác nhau nên khi sử dụng các thuật toán nên tìm hiểu kĩ về các đặc điẻm của từng loại lưu lượng để việc sử dụng đạt hiệu quả. Nhình chung các thuật toán thì thuật toán RED vẫn có ưu điểm hơn cả. Điều này được thể hiện việc thuật toán RED tính toán sự thay đổi của kích thước hàng đợi để loại bỏ gói và phát hiện tắc nghẽn. Trong thuật toán RED còn phân ra thành nhiều thuật toán khác. Ở chương này đề cập tới một số thuật toán đó : WRED, RIO, ARED….Có sự so sánh giữa các thuật toán này để tìm ra thuật toán tối ưu nhất trong việc quản lý hàng đợi trong điều khiển tắc nghẽn Kết luận Mục đích chính của việc phát triển và nâng cấp các cấu trúc mạng viễn thông chỉ nhằm mục đích là đơn giản việc truyền tin, đáp ứng các yêu cầu đa dạng của khách hàng về chất lượng dịch vụ. Nhiều phương pháp đưa ra nhằm cải thiện và nâng cao chất lượng dịch vụ trong mạng. Các phương pháp quản lý hàng đợi được đưa ra tác động vào các tham số của chất lượng dịch vụ nhằm cải thiện QoS trong mạng IP là vấn đề quan trọng cần được quan tâm và nghiên cứu lâu dài. Trong đồ án này này em đã trình bày được các vấn đề sau : Các kiểu mô hình mạng hỗ trợ QoS trong mạng đó là mô hình mạng kiểu dịch vụ tích hợp IntServ và mô hình mạng kiểu dịch vụ phân biệt DiffServ. Mỗi mô hình có hoạt động, ưu điểm và nhược điểm riêng chúng hỗ trợ với nhau trong việc cải thiện QoS qua mạng. Cấu trúc bên trong của một router. Đi sâu vào hoạt động của kiến trúc CQS trong router Tìm hiểu được các phương pháp quản lý hàng đợi trong router như thuật toán RED, Tail Drop, …và các loại hàng đợi như : WFQ, PQ, FQ…cùng các ưu điểm và nhược điểm của chúng. Đồ án này còn có nhiều điểm hạn chế : Đồ án mới chỉ dừng lại tại độ tổng quan, chỉ đi vào các khái niệm cơ bản của hàng đợi mà chưa đi sâu được vào kĩ thuật hàng đợi và thuật toán của chúng Mô phỏng còn quá sơ sài, chưa nêu bật được sự khác nhau và các ưu nhược điểm của các phương pháp Chưa có đề xuất, giải pháp cho việc nâng cao hiệu quả sử dụng các phương pháp quản lý này trong mạng viễn thông. Nếu có thời gian em sẽ nghiên cứu kĩ hơn các ảnh hưởng của chúng tới các tham số của QoS để cải thiện chất lượng dịch vụ theo yêu cầu của khách hàng và đưa ra các đề xuất sử dụng tốt nhất các phương pháp này trong mạng viễn thông. Một lần nữa em xin chân thành cảm sự giúp đỡ nhiệt tình của các thầy cố trong khoa Viễn Thông, đặc điệt là thầy giáo ThS Nguyễn Văn Đát đã giúp đỡ em hoàn thành đồ án này. Sinh viên thực hiện Đỗ Thị Thanh Huyền Tài liệu tham khảo TS Lê Hữu Lập, TS Hoàng Trọng Minh, Công nghệ chuyển mạch IP, Hà Nội 11/2002 Genville Armitage , Quality of service in IP network, 1999 Willyam Starling, High speed network: TCP/IP and ATM priciples, Prenti hall 1998 Nguyễn Quốc Cường, Internetworking with TCP/IP , Nhà xuất bản giáo dục, 2001 IP and ATM : current Evolution for IntServ, IC techreport-1992 Balaji Kumar, Broastband communication : A professional guide to ATM, Mc Growhill, 1998 Một số tin tức và tài liệu tổng hợp từ Internet. Các tiêu chuẩn RFC của IETF.