Phương Pháp Loại Bỏ Ngẫu Nhiên Theo Trọng Số

Caculate propability pa With propability pa:

mark the ariving packet else maxth ≤ avg

mark the ariving packet

Như vậy, giải thuật tại RED gateway gồm hai giải thuật tách biệt: Giải thuật tính kích thước hàng đợi trung bình quyết định mức độ bùng nổ cho phép trong hàng đợi tại gateway và giải thuật tính xác suất đánh dấu quyết định mức độ thường xuyên của việc đánh dấu gói tin của gateway. Giải thuật tính xác suất đánh dấu phải đảm bảo sao cho các gói tin được đánh dấu tại những khoảng không gian đều nhau, để tránh hiện tượng đồng bộ toàn cầu, trong khi vẫn giữ kích thước hàng đợi trung bình ở một giới hạn nhất định.

Giải thuật chi tiết của RED tại gateway được mô tả như sơ đồ dưới đây:

Hình 3. 2 Giải thuật chi tiết của RED[5]

Theo giải thuật, mỗi khi có một gói tin đến, sẽ tính kích thước hàng đợi trung bình

– avg bằng bộ lọc thông thấp:

Có thể bạn quan tâm!

Xem toàn bộ 88 trang tài liệu này.

Trong đó: q là kích thước hàng đợi hiện thời; wq là trọng số hàng đợi, nhận giá trị trong miền 0..1, wq còn được gọi là hệ số làm trơn, wq càng nhỏ thì mức độ làm trơn càng cao, wq càng lớn thì avg càng bám sát giá trị tức thời của q. Như vậy wq quyết định độ lớn và độ kéo dài cho phép của sự bùng nổ lưu lượng.

Khi avg chạy từ minth đến maxth thì xác suất pb thay đổi tuyến tính từ 0 đến maxp:

Xác suất đánh dấu gói tin pa tăng chậm khi số gói tin từ gói cuối cùng được đánh dấu count tăng lên: pa ← pb / (1 – count.pb), điều này đảm bảo cho gateway không phải đợi quá lâu trước khi đánh dấu một gói tin. RED gateway đánh dấu tất cả các gói tin đến nếu như avg vượt quá maxth.

RED có một tuỳ chọn: để đảm bảo xác suất một gói bị loại bỏ tỉ lệ với thông lượng tính bằng bit/s chứ không phải packet/s, pb được tính như sau:

Trong trường hợp này, một gói tin lớn dễ bị loại bỏ hơn là một gói tin nhỏ.

3.2.3 Thiết lập các tham số

Theo thuật toán chi tiết chúng ta thấy có bốn tham số cố định cần được đặt trước. Vấn đề thiết lập các tham số cố định cho giải thuật RED là rất quan trọng, quyết định tới chất lượng của thuật toán. Phần này chúng tôi sẽ trình bày song song hai cách thiết lập các tham số: định tính (bằng lý luận) và định lượng (bằng mô phỏng) để có thể chọn được một bộ tham số hợp lý nhất, mang lại hiệu quả cao nhất cho thuật toán. Phần mô phỏng đã được các tác giả [4] nghiên cứu rất kỹ bằng NS-2, tôi đã thực hiện lại các mô phỏng đó và thấy rằng các kết quả mà họ đưa ra là hoàn toàn chính xác. Vì vậy ở đây chúng tôi chỉ xin trích dẫn các kết quả đó kèm theo bình luận riêng mà không trình bày lại các mô phỏng.

a. Trọng số hàng đợi wq

RED gateway sử dụng bộ lọc thông thấp để tính kích thước hàng đợi trung bình. Theo đó, sự tăng ngắn hạn của kích thước hàng đợi hiện tại do một lưu lượng bùng nổ, hoặc một sự tắc nghẽn thoáng qua sẽ không ảnh hưởng lớn đến kích thước hàng đợi trung bình: avg ← (1 – wq) * avg + wq * q, trong đó, trọng số hàng đợi wq đóng vai trò quyết định đến giá trị của avg. Sau đây chúng ta sẽ thiết lập cận trên và cận dưới cho wq.

Cận trên cho wq

Chúng ta thấy rằng, nếu wq quá lớn, kích thước trung bình luôn bám sát kích thước hàng đợi hiện tại, dẫn đến RED gateway không lọc được tắc nghẽn tạm thời tại gateway, nghĩa là không hấp thu được các lưu lượng tăng đột biến, dẫn đến hàng đợi bị tràn và mất gói tin. Giả sử hàng đợi được khởi tạo rỗng, với kích thước trung bình bằng không, sau đó kích thước hàng đợi tăng từ 0 đến L ứng với L gói tin đến. Sau khi gói tin thứ L đến gateway, kích thước trung bình avgL là:

Cho trước ngưỡng dưới minth, giả sử chúng ta muốn cho phép hấp thu bùng nổ đến L gói tin, wq phải được chọn thoả mãn bất phương trình avgL < minth:

Cho minth = 5, L = 50 chẳng hạn, khi đó wq ≤ 0.0042 [18, p.9-10]

Cận dưới cho wq

RED gateway được thiết kế để giữ cho kích thước hàng đợi trung bình avg dưới một ngưỡng nào đó. Tuy nhiên sẽ không đạt được mục đích nếu như avg không phản ánh được một cách hợp lý kích thước hàng đợi trung bình hiện tại. Nếu wq được thiết lập quá thấp, thì avg phản ứng rất chậm với sự thay đổi kích thước hàng đợi thực. Trong trường hợp này, gateway không phát hiện thấy sự bắt đầu của tắc nghẽn. Theo các kết quả tính toán của các nghiên cứu về RED, người ta khuyến cáo wq ≥ 0.001. Giá trị tối ưu cho wq là 0.002, ngoài ra, tuỳ theo điều kiện của mạng, ta có thể chọn wq trong khoảng (0.002, 0.003).

b. Thiết lập minth và maxth

Giá trị tối ưu cho minth và maxth phụ thuộc vào một số yếu tố, trong đó có kích thước trung bình mong muốn của hàng đợi, hay cũng chính là mức tắc nghẽn được phép tại hàng đợi. Theo nguyên lý hoạt động của RED:

− Nếu lưu lượng trên mạng ít có các đột biến, minth và maxth nên được thiết lập giá trị cao để tận dụng tối đa đường truyền.

− Nếu lưu lượng trên mạng thường xảy ra đột biến, minth và maxth nên được thiết lập giá trị nhỏ để có thể hấp thu các đột biến lưu lượng. Tuy nhiên, các giá trị quá nhỏ sẽ dẫn đến lãng phí dải thông, vì số gói tin bị loại bỏ không cần thiết sẽ cao hơn.

− Khoảng ngưỡng (maxth - minth) ảnh hưởng mạnh đến thăng giáng độ trễ, thông lượng và khả năng hấp thu các đột biến tạm thời tại hàng đợi. Để tránh được hiện tượng đồng bộ toàn cầu thì không nên để giá trị khoảng này quá thấp, avg

sẽ nhanh chóng đạt tới ngưỡng trên. RED gateway sẽ làm việc hiệu quả nhất khi (maxth – minth) bằng mức gia tăng điển hình của kích thước hàng đợi trung bình trong một khoảng thời gian khứ hồi RTT. Quy tắc nên tuân theo là thiết lập maxth ít nhất gấp đôi minth.

Sau khi kiểm nghiệm các mô phỏng trong [4], chúng tôi khuyến nghị rằng minth ≥ 5 và maxth = 3 minth.

c. Thiết lập xác suất loại bỏ tối đa maxp

Giá trị maxp sẽ quyết định tần số loại bỏ gói là lớn hay nhỏ, nó quyết định avg sẽ nằm ở mức nào trong khoảng từ minth đến maxth. Vì vậy tùy từng yêu cầu mà có thể thiết lập maxp cho phù hợp. Thí dụ, để avg nằm trong khoảng giữa minth và maxth, giá trị maxp phù hợp là 0.02. Tuy nhiên nếu tắc nghẽn thường xuyên xảy ra, cần chọn maxp lớn hơn, thí dụ bằng 0.1. Về tham số này, chúng tôi cũng đồng ý với các tác giả trong [1] rằng nên chọn maxp = 0.1.

3.2.4 Một số đánh giá về RED

RED là một điển hình của các chiến lược quản lý hàng đợi động AQM, ngoài những ưu điểm chung của AQM, RED còn có một số tính chất (ưu điểm) riêng biệt khác nữa:

− Tránh tắc nghẽn: Nếu RED gateway thực sự loại bỏ gói tin đến khi kích thước hàng đợi trung bình đạt đến ngưỡng trên, thì RED gateway đảm bảo kích thước hàng đợi trung bình tính theo lý thuyết không vượt quá ngưỡng trên. Nếu trọng số hàng đợi wq được thiết lập một cách hợp lý thì RED gateway hoàn toàn có thể điều khiển được kích thước hàng đợi trung bình thực sự. Nếu RED gateway đánh dấu một bit trong header của gói tin đến khi kích thước hàng đợi trung bình vượt quá ngưỡng trên, thay vì loại bỏ nó, thì hiệu quả hoạt động của RED gateway còn phụ thuộc vào sự hợp tác của các cặp nguồn/đích để điều khiển kích thước hàng đợi trung bình.

− Tránh đồng bộ toàn cục: Tỷ lệ đánh dấu gói tin của RED gateway phụ thuộc vào mức độ tắc nghẽn. Ở giai đoạn tắc nghẽn thấp, RED gateway đánh dấu gói tin với một xác suất thấp, và khi tắc nghẽn tăng lên thì xác suất đánh dấu cũng tăng lên. Mặt khác, RED gateway chọn ngẫu nhiên các gói tin đến để đánh dấu; với phương pháp này xác suất đánh dấu một gói tin từ một kết nối cụ thể tỉ lệ với phần băng thông được chia sẻ của kết nối đó tại gateway. Như vậy, RED gateway tránh hiện tượng đồng bộ toàn cục bằng cách đánh dấu gói tin theo một tỷ lệ thấp nhất có thể và việc đánh dấu các gói tin một cách ngẫu nhiên.

− Đơn giản: Thuật toán RED có thể được cài đặt với một chi phí vừa phải, không yêu cầu phải cài đặt đồng loạt cho tất cả các gateway trong mạng mà có thể triển khai dần.

− Cực đại hoá công suất toàn cục: Công suất nói ở đây được định nghĩa bằng tỷ lệ giữa thông lượng và độ trễ. Vì RED gateway điều khiển cho kích thước hàng đợi nhỏ, dẫn tới độ trễ nhỏ, mặt khác như các mô phỏng chúng tôi trình bày dưới đây, hệ số sử dụng đường truyền với RED và DropTail là xấp xỉ nhau, vì vậy công suất đường truyền cao hơn rất nhiều so với DropTail (điều này được khẳng định bằng các mô phỏng dưới đây).

− Tính công bằng: một trong những mục tiêu quan trọng của một thuật toán quản lý hàng đợi là sự công bằng trong việc cấp phát đường truyền cho các kết nối chia sẻ. Về điểm này thì RED gateway có phần hạn chế. RED gateway không phân biệt các kết nối hay các lớp kết nối khác nhau. Đối với RED gateway, tỷ lệ các gói tin bị đánh dấu tỷ lệ với phần băng thông chia sẻ của kết nối đó tại gateway. Tuy nhiên nó không cố gắng đảm bảo tất cả các kết nối nhận được cùng một tỷ lệ dải thông, mặt khác nó không điều khiển được hiện tượng misbehaving users - hiện tượng một kết nối nào đó nhận được tỷ lệ băng thông lớn hơn rất nhiều so với các kết nối khác đi qua gateway.

3.3 Phương pháp loại bỏ ngẫu nhiên theo trọng số - WRED

Thuật toán RED không phải lúc nào cũng đảm bảo cho các luồng chia sẻ băng thông một cách cân đối nhau. Trong thực tế, RED không ưu tiên đối với các luồng TCP tốc độ thấp vì RED loại bỏ ngẫu nhiên các gói khi ngưỡng bị vượt quá. WRED (Weighted RED) là phương pháp tránh tắc nghẽn dựa trên việc các thuộc tính của thuật toán RED và ưu tiên IP. WRED có thể lựa chọn loại bỏ lưu lượng có mức ưu tiên thấp khi trên giao diện bắt đầu xảy ra quá trình tắc nghẽn và cung cấp các đặc tính tiêu chuẩn khác nhau cho các lớp dịch vụ khác nhau.

Với các giao diện mạng được cấu hình sử dụng đặc tính giao thức dành sẵn tài nguyên (RSVP), khi quá trình nghẽn xảy ra WRED ưu tiên các luồng RSVP hơn là các luồng dữ liệu khác trong quá trình loại bỏ gói để tránh tắc nghẽn. Cũng giống như RED trong cơ chế của mình WRED loại bỏ gói một cách ngẫu nhiên, từ đó thông báo tới trạm gốc giảm tốc độ truyền gói tin vào mạng. Nếu trạm gốc sử dụng TCP, nó sẽ làm giảm tốc độ của chính các gói đó cho tới khi tất cả các gói có thể đến được đích.

WRED loại gói dựa trên giá trị ưu tiên IP được gán cho mỗi gói. Các gói có giá trị ưu tiên thấp hơn có khả năng bị làm rớt cao. WRED khắc phục các điểm yếu của cơ chế DropTail khi đầu ra giao diện có nguy cơ bị tắc nghẽn nó sẽ thực hiện lựa chọn làm mất một số gói thay vì chờ cho tới khi các hàng đợi bị đầy rồi mới thực hiện việc loại bỏ gói.

WRED tránh việc làm mất một lượng lớn các gói trong một khoảng thời gian ngắn, từ đó nó cho phép các đường truyền được sử dụng hữu ích tại mọi thời điểm. WRED tránh được các vấn đề đồng bộ toàn cục xảy ra khi sử dụng DropTail để tránh tắc

nghẽn. WRED chỉ hữu ích khi phần lớn lưu lượng là dữ liệu của giao thức TCP, khi đó các gói bị loại sẽ phát sinh thông báo (gián tiếp) về sự nghẽn mạch để từ đó trạm phát giảm tốc độ truyền dẫn của mình. Đối với các gói tin được đóng gói theo một giao thức khác có thể trạm gửi không phát hiện quá trình mất gói xảy ra, như vậy có thể không ngăn chặn được quá trình nghẽn mạch. Với các dữ liệu mà không thuộc dạng gói TCP, WRED coi đó như là dữ liệu có mức ưu tiên thấp nhất (Precedence = 0), bởi vậy khả năng bị loại của nó là cao hơn các dữ liệu TCP.

Hình 3. 3 Cơ chế làm việc của WRED được minh hoạ trong hình vẽ trên

Router sẽ tự động tính toán các thông số của WRED để xác định cỡ hàng đợi trung bình. Cỡ hàng đợi trung bình được tính trên cơ sở cỡ hàng đợi trung bình trước và cỡ hàng đợi hiện tại. Giá trị của nó được tính theo công thức sau:

average = (old_average * (1 – 1/2n )) + (current_queue_size * 1/2n )

Trong đó:

n: là hệ số trọng số và có thể cấu hình được. average: Cỡ hàng đợi trung bình old_average: Cỡ hàng đợi trung bình trước đó

current_queue_size: Kích thước hàng đợi hiện tại

Chúng ta nên chọn hệ số trọng số cho phù hợp nếu n quá lớn WRED sẽ không tác động để chống tắc nghẽn, các gói tin sẽ được gửi hoặc bị loại vì vậy việc áp dụng WRED là vô ích, tuy nhiên việc lựa chọn n quá nhỏ WRED sẽ phản ứng mãnh liệt với sự bùng nổ lưu lượng tạm thời dẫn đến làm mất gói trong khi không thực sự cần thiết. Chúng tôi sẽ sử dụng NS2 để mô phỏng thuật toán này và đưa ra các nhận xét trong chương 4.

Như đã trình bày trong chương 2, DiffServ đi theo hướng đảm bảo chất lượng dựa trên nguyên lý hành vi theo từng chặng căn cứ vào mức ưu tiên của các gói tin đã được đánh dấu. Việc đưa ra chính sách với các loại lưu lượng khác nhau là do người quản trị quyết định và có thể thay đổi theo thực tế nên nó rất mềm dẻo. DiffServ tận dụng tốt tài nguyên mạng hơn, tránh được tình trạng nhàn rỗi băng thông và năng lực xử lý trên

router, ngoài ra mô hình DifServ có thể triển khai trên nhiều miền độc lập do vậy khả năng mở rộng mạng trở nên dễ dàng. Dưới đây, là các đặc tính của WRED được sử dụng trong kiến trúc DiffServ.

a. Cấu trúc của DiffServ

DiffServ cung cấp dịch vụ QoS bằng việc chia traffic ra làm nhiều nhóm (lớp) khác nhau, mỗi một packet sẽ được đánh dấu bằng 1 mã (Code Point) để xác định nhóm. Module DiffServ trong NS2 có thể hỗ trợ 4 lớp traffic, mỗi lớp lại có 3 loại quyền ưu tiên loại bỏ (dropping precedences) cho phép ta xử lý các lớp traffic theo nhiều cách khác nhau. Các packet trong một lớp đơn sẽ được đưa vào trong 1 hàng đợi RED vật lý (physical queue), trong đó chứa tối đa 3 hàng đợi ảo (virtual queue). Tại các hàng đợi ảo này ta có thể cấu hình để ưu tiên với các loại gói tin theo ý muốn.

Những tham số khác nhau của RED có thể được cấu hình cho các virtual queue, từ đó có thể dẫn đến 1 virtual queue có thể drop gói tin thường xuyên hơn những virtual queue khác. Mỗi packet sẽ được gắn với 1 giá trị Code Point và các tham số của RED, trong đó có trị số drop (dropping precedences), nếu trị số này thấp thì sẽ packet được ưu tiên hơn, sẽ ít bị drop khi xảy ra tắc nghẽn.

Module DiffServ trong NS2 có 3 thành phần chính như sau:

- Policy: là bộ luật, nó được thiết lập bởi người quản trị mạng, nói về các cấp độ của dịch vụ mà của 1 lớp traffic nhận được trên mạng

- Edge router: các router biên có nhiệm vụ đánh dấu mã Code Point vào packet.

Giá trị Code Point tương ứng với policy đã được thiết lập ở trên.

- Core router: các router lõi có nhiệm vụ thực thi policy dựa theo code point của gói tin.

Tất cả những thủ tục và chức năng của DiffServ có thể tìm thấy trong bộ code/thư viện của NS2: ~ns/diffserv/dsred, dsredq, dsEdge, dsCore, dsPolicy.{cc, h}

b. Hàng đợi RED trong module DiffServ

Hàng đợi RED trong DiffServ khác với hàng đợi RED sẵn có của NS2 trong REDQueue, nó được định nghĩa trong lớp dsREDQueue, thừa kế từ lớp Queue, nó có những chức năng như sau:

- Triển khai nhiều hàng đợi vật lý RED qua cùng 1 liên kết đơn

- Triển khai nhiều hàng đợi ảo trong 1 hàng đợi vật lý, với những tham số riêng biệt cho mỗi hàng đợi ảo

- Xác định 1 packet thuộc hàng đợi vật lý và hàng đợi ảo nào dựa vào giá trị Code Point của nó

- Xác định hàng đợi vật lý và hàng đợi ảo nào mà packet đi ra.

Lớp dsREDQueue bao gồm tối đa 4 hàng đợi RED vật lý, mỗi cái lại chứa tối đa 4 hàng đợi ảo. Số hàng đợi vật lý và ảo được sử dụng có thể được thiết lập thông qua biến numPrec và numQueues_.

Hàng đợi vật lý được định nghĩa trong lớp redQueue, nó khả năng phân biệt các traffic thông qua việc định nghĩa các hàng đợi ảo với các cấu hình độc lập, chi tiết về việc này có tại file dsredq.h và dsredq.cc trong bộ cài NS2.

Lớp dsREDQueue còn chứa một kiến trúc dữ liệu là bảng Per Hop Behavior (PHB), các router biên đánh dấu packet bằng Code Point và core router xử lý packet dựa trên giá trị Code Point đó, và cả 2 loại router đều sử dụng bảng PHB để ánh xạ Code Point tới hàng đợi vật lý và ảo.

Bảng PHB được định nghĩa như là 1 mảng với 3 trường như sau:

struct phbParam {

int codePt_; // giá trị Code Point

int queue_; // số hiệu hàng đợi vật lý int prec_; // số hiệu hàng đợi ảo

c. Router lõi và router biên

Định nghĩa router lõi và router biên trong DiffServ có trong class edgeQueue và coreQueue, chúng thừa kế từ class dsREDQueue. Chi tiết có tại file dsEdge, dsCore.{h.cc}.

Vị trí của router lõi và router biên trong miền DiffServ được minh hoạ trên Hình 3.4 sau đây.

Hình 3. 4 Vị trí router lõi và biên trong miền DiffServ

Nhiệm vụ của router biên:

- Phân tích và phân loại các gói tin đến mạng dựa theo các policy đã thiết lập

- Đánh dấu gói tin với 1 mã (code point) phản ánh mức độ phục vụ

- Bảo đảm tất cả các luồng dữ liệu phải được đánh dấu và tuân theo policy Nhiệm vụ của router lõi:

- Phân tích các gói tin

- Xử lý gói tin dựa theo code point được đánh dấu