Hàng đợi cân bằng có trọng số(WFQ-Weighted Fair Queue)

[thanhsang_truong]

Tác giả: (sưu tầm)

HÀNG ĐỢI CÂN BẰNG CÓ TRỌNG SỐ

- Bộ lập lịch WFQ có 2 mục đích chính. Thứ nhất là cung cấp tính công bằng giữa các luồng đang tồn tại. WFQ cung cấp mỗi luồng một lượng băng thông bằng nhau. Nếu 10 luồng tồn tại với một cổng giao tiếp, và tốc độ xung 128 kpbs, mỗi luồng nhận 12,8 kbps. Nếu 100 luồng, mỗi luồng nhận 1,28 kbps. Trong một vài tình huống, trường hợp này như hệ thống phân thời gian TDM, nhưng số lượng khe thời gian không định trước, mà căn cứ vào số luồng hiện tại tồn tại ở một cổng giao tiếp.
- Với mỗi luồng, cổng giao tiếp nhận băng thông chia sẻ công bằng, nếu luồng 128 kbps, với 10 luồng. Nếu luồng 1 cần 5 kbps, và WFQ cho phép 12,8 kbps trên mỗi luồng, hàng đợi kết hợp với luồng 1 có thể có nhiều hơn một số gói trong nó, vì các gói nhanh chóng rời khỏi hàng đợi. Nếu luồng 2 cần 30 kbps, sau khi các gói dự phòng trong hàng đợi của luồng 2, vì WFQ chỉ cung cấp hàng đợi này 12,8 kbps. Các gói này có thể bị hủy bỏ, trễ và biến động trễ nếu hàng đợi đầy. Dĩ nhiên, nếu luồng 1 chỉ cần 5 kbps, thì bộ lập lịch WFQ thực sự cho phép các luồng khác sử dụng băng thông mở rộng.
- Mục đích thứ 2 của bộ lập lịch là cung cấp nhiều băng thông hơn đến các luồng với giá trị ưu tiên IP cao hơn. Độ ưu tiên của luồng ưu tiên cao gọi là “trọng số” (weighted) và trọng số căn cứ cho độ ưu tiên. Với 10 luồng trên một liên kết 128 kbps, chẳng hạn, nếu 5 luồng sử dụng ưu tiên 0 và 5 sử dụng ưu tiên 1 sẽ nhận 17 kbps. Thật ra, WFQ cung cấp sự chia sẻ công bằng dựa trên tỷ lệ ưu tiên của mỗi luồng. Mặt khác, luồng ưu tiên 7 nhận gấp 8 lần luồng ưu tiên 0, vì (7+1)/(0+1) = 8. Nếu chúng ta so sánh ưu tiên 3 và ưu tiên 0, tỉ lệ là (3+1)/(0+1) =4.
- Nếu bỏ qua vấn đề ưu tiên, các luồng có dung lượng thấp nhận các dịch vụ tốt hơn các luồng có dung lượng cao. Các luồng ưu tiên cao nhận các dịch vụ tốt hơn các luồng ưu tiên thấp. Nếu luồng có dung lượng thấp nhận giá trị ưu tiên cao; tính chất mất gói, biến động trễn, độ trễ và băng thông cải thiện nhiều hơn. Trong một mạng, vị trí nhạy cảm với độ trễ nhất là vị trí có lưu lượng dung lượng thấp. WFQ là một giải pháp tốt cho tình huống này. WFQ tiến hành khi các luồng tương tác quan trọng của mạng là kiến trúc mạng hệ thống (SNA – System Network Architecture) và Telnet đóng gói trong IP. Các loại luồng này dung lượng lớn hơn các luồng khác; vì WFQ cung cấp một giá trị mặc định lớn, không cần lo lắng về cách thể hiện sự ưu tiên trong lưu lượng SNA được đóng gói.
1. Lập lịch WFQ:
- WFQ cung cấp mỗi luồng phần trăm băng thông có trọng số. Tuy nhiên, WFQ không định nghĩa các hàng đợi như các công cụ hàng đợi dựa trên lớp, vì WFQ phân lớp các hàng đợi dựa vào các chi tiết luồng. Vì mỗi luồng có độ ưu tiên khác nhau, phần trăm băng thông liên kết cho mỗi luồng sẽ thay đổi, và nó sẽ thay đổi nhanh chóng, khi mỗi luồng thêm hay loại bỏ.
Thực ra bộ lập lịch rất đơn giản, khi TXQ /TXR trống một khe, WFQ có thể di chuyển một gói đến TXR, như bất cứ các công cụ hàng đợi khác. Bộ lập lịch WFQ sẽ lấy số tuần tự thấp nhất SN (Sequence Number) trong tất cả các hàng đợi và chuyển nó vào TXR. SN được chỉ định khi nó đặt vào hàng đợi diễn ra quá trình lập lịch WFQ. Hình 3-9 minh họa việc đánh dấu SN, phục vụ hàng đợi.

http://usera.imagecave.com/98765/QOS_hinh18.jpg
- WFQ tính toán SN trước khi một gói được thêm vào hàng đợi. Thật ra, WFQ tính toán SN trước khi quyết định bỏ gói, vì SN là một phần của nguyên lý hủy gói cuối hàng đợi. Bộ lập lịch WFQ xem xét chiều dài gói và độ ưu tiên khi tính toán SN. Công thức tính toán SN cho mộ gói như sau:


SN = Pre_SN + trong số * chiều dài gói mới
- Công thức tính xem xét chiều dài của gói mới, trọng số của luồng và SN trước. Bằng cách xem xét chiều dài gói, việc tính toán SN cho kết quả số lượng các gói lớn ưu tiên cao và số lượng các gói nhỏ hơn ưu tiên thấp. Công thức xem xét SN của tất cả các gói đưa vào hàng đợi gần nhất để tính SN mới.
- Phần thứ 3 của công thức, trọng số là phần quan trọng nhất. Chúng ta biết từ thuật toán lập lịch cơ bản mà SN thấp nhất lấy tiếo theo, và WFQ muốn cung cấp nhiều băng thông hơn cho các luồng ưu tiên cao. Vì thế, giá trị trọng số là phần nghịch đảo của giá trị ưu tiên. Bảng III-3 danh sách các giá trị trọng số sử dụng bởi WFQ trước và sau release 12.0 (5)T/2.1.

http://usera.imagecave.com/98765/QOS_hinh19.jpg
- Như trong bảng, giá trị ưu tiên lớn hơn, trọng số thấp hơn, SN thấp hơn. Hình 3-10 minh họa rõ hơn một luồng đang tồn tại và một luồng mới.

http://usera.imagecave.com/98765/QOS_hinh20.jpg
- Khi thêm gói mới 1 vào hàng đợi qua luồng 1, WFQ chỉ thực hiện công thức theo chiều dài gói mới (100) và trọng số, thêm SN của gói sau cùng vào hàng đợi, vị trí mà gói mới sẽ được thêm vào. Với các luồng mới, công thức này cũng được sử dụng, vì không có gói nào trong hàng đợi, tuy nhiên, SN của gói gần nhất được gửi trong thí dụ này là 100. Trong trường hợp khác, WFQ chỉ ra các giá trị cho các gói lớn và độ ưu tiên IP thấp hơn.

[thanhsang_truong]

- Hình 3-11 thể hiện chi tiết hơn cho thuật toán gán SN WFQ và cách thực hiện các mục đích của hàng đợi. Trong hình, ta có một tập 4 hàng đợi, mỗi một gói trong 4 gói có chiều dài khác nhau. Mỗi luồng của gói đầu tiên đến cùng một thời điểm, và tất cả các gói cho tất cả các luồng đến trước khi bất cứ gói nào có thể được lấy từ hàng đợi.

http://usera.imagecave.com/98765/QOS_hinh21.jpg
- Trong ví dụ này, mỗi luồng có 4 gói đến, tất cả các gói ưu tiên 0. Các gói trong luồng 1 chiều dài 1500 byte; trong luồng 2, các gói 1000 byte; 500 byte ở luồng 3, và luồng 4, các gói 100 byte. Cùng một ưu tiên, các gói tại luồng 4 nhận dịch vụ tốt hơn vì các gói nhỏ hơn. Thực ra, tất cả các gói luồng 1 được phục vụ trước các gói ở các luồng khác. Các gói luồng 3 được gửi trước các gói luồng 1 và 2. Do đó, mục tiêu cung cấp các luồng dung lượng thấp phục vụ tốt hơn hoàn thành, giả sử cùng độ ưu tiên.
Trong bản ghi, thứ tự các gói xuất hiện sẽ rời khỏi ngõ xuất , giả sử không có vấn đề gì xuất hiện, đầu tiên 13, sau đó 14, 15, 16, 9, 5, 10,1, 11, 6, 12, 2, 7, 8 , 3 ,4.
- Chúng ta sẽ xem xét việc gán SN với độ ưu tiên thay đổi. Hình 3-12 minh họa điều này.

http://usera.imagecave.com/98765/QOS_hinh22.jpg
- SN của luồng 1 và luồng 2 thay đổi theo giá trị ưu tiên 3 và 5. Luồng 4 vẫn nhận dịch vụ tốt, ngay cả khi độ ưu tiên là 0 vì các gói nhỏ. Hai gói trong luồng 2 (gói 5 và gói 6), và một gói từ luồng 1 (gói 1) được phục vụ trước gói thứ tư (gói 16) của luồng 4 (SN= 12,953,600), gói trong luồng ưu tiên cao được phục vụ tốt hơn. Vì thế, luồng dung lượng thấp, luồng ưu tiên thấp được phục vụ sau các luồng dung lượng cao và ưu tiên cao.
- Trong bản ghi, trật tự các gói rời khỏi ngõ xuất, giả sử không có vấn đề gì phát sinh, là 13, 5, 14, 15, 6, 1, 16, 7, 9, 8, 2, 3, 4, 11, 12.
2. Chính sách bỏ gói, chiều dài hàng đợi, số lượng hàng đợi WFQ:
- WFQ sử dụng chính sách hủy gói cuối hàng đợi có hiệu chỉnh. Quyết định hủy gói dựa trên nhiều yêu tố, một trong số đó là số tuần tự của gói.
- WFQ đặt giới hạn tuyệt đối cho số gói vào hàng đợi; giá trị này gọi là “giới hạn giữ hàng đợi” (hold-queue limit). Nếu một gói mới đến, hàng đợi đạt đến giá trị giới hạn; gói đó bị hủy. Quyết định này không dựa trên một hàng đợi mà nó căn cứ vào hệ thống lập hàng đợi WFQ.
- Quyết định kế tiếp dựa trên một hàng đợi. Nếu một gói cần đặt vào hàng đợi và tiến đến ngưỡng bỏ gói CDT (Congestive Dircard Threshold) của hàng đợi, các gói có thể bỏ. CDT là kích thước hàng đợi ứng với hàng đợi của mỗi luồng. Hình 3-13 minh hoạ việc sử dụng CDT.

http://usera.imagecave.com/98765/QOS_hinh23.jpg
- Kích thước của “hàng đợi giới hạn” giới hạn tổng số gói trong luồng. Tuy nhiên, CDT giới hạn số gói trong mỗi hàng đợi cụ thể. Các gói mới đến sẽ bị hủy khi hàng đợi đạt đến CDT. Nếu hàng đợi của 2 luồng đều đến giá trị CDT, WFQ sẽ bỏ luồng nào có SQ cao hơn. Chúng ta có thể cấu hình giá trị CDT trong khoảng từ 1 đến 4096.

http://usera.imagecave.com/98765/QOS_hinh24.jpg

[doantrang]

chào anh
em đang làm đồ án với đề tài này, đọc bài của anh thấy có nhiều hình minh họa mà sao em chẳng xem đc. anh có thể giúp em tìm hiểu kỹ về thuật toán được không ạ. Rất mong đc sự giúp đỡ của anh. có tài liệu nào về RED, WFQ, WF2Q, GPS anh có thể share cho em được không
địa chỉ mail của em piano209@yahoo.com

[changia]

Mình đọc bài này vẫn chưa hiểu rõ lắm về cách thức hoạt động giữa các queue (WFQ , CB WFQ , LLQ , WRED .. vv..)
Các bạn có thể giải thích rõ hơn sự khác nhau và mô tả cách thức hoạt động của từng queue đc ko

[changia]

- Hình 3-11 thể hiện chi tiết hơn cho thuật toán gán SN WFQ và cách thực hiện các mục đích của hàng đợi. Trong hình, ta có một tập 4 hàng đợi, mỗi một gói trong 4 gói có chiều dài khác nhau. Mỗi luồng của gói đầu tiên đến cùng một thời điểm, và tất cả các gói cho tất cả các luồng đến trước khi bất cứ gói nào có thể được lấy từ hàng đợi.

http://usera.imagecave.com/98765/QOS_hinh21.jpg
- Trong ví dụ này, mỗi luồng có 4 gói đến, tất cả các gói ưu tiên 0. Các gói trong luồng 1 chiều dài 1500 byte; trong luồng 2, các gói 1000 byte; 500 byte ở luồng 3, và luồng 4, các gói 100 byte. Cùng một ưu tiên, các gói tại luồng 4 nhận dịch vụ tốt hơn vì các gói nhỏ hơn. Thực ra, tất cả các gói luồng 1 được phục vụ trước các gói ở các luồng khác. Các gói luồng 3 được gửi trước các gói luồng 1 và 2. Do đó, mục tiêu cung cấp các luồng dung lượng thấp phục vụ tốt hơn hoàn thành, giả sử cùng độ ưu tiên.
Trong bản ghi, thứ tự các gói xuất hiện sẽ rời khỏi ngõ xuất , giả sử không có vấn đề gì xuất hiện, đầu tiên 13, sau đó 14, 15, 16, 9, 5, 10,1, 11, 6, 12, 2, 7, 8 , 3 ,4.
- Chúng ta sẽ xem xét việc gán SN với độ ưu tiên thay đổi. Hình 3-12 minh họa điều này.

http://usera.imagecave.com/98765/QOS_hinh22.jpg
- SN của luồng 1 và luồng 2 thay đổi theo giá trị ưu tiên 3 và 5. Luồng 4 vẫn nhận dịch vụ tốt, ngay cả khi độ ưu tiên là 0 vì các gói nhỏ. Hai gói trong luồng 2 (gói 5 và gói 6), và một gói từ luồng 1 (gói 1) được phục vụ trước gói thứ tư (gói 16) của luồng 4 (SN= 12,953,600), gói trong luồng ưu tiên cao được phục vụ tốt hơn. Vì thế, luồng dung lượng thấp, luồng ưu tiên thấp được phục vụ sau các luồng dung lượng cao và ưu tiên cao.
- Trong bản ghi, trật tự các gói rời khỏi ngõ xuất, giả sử không có vấn đề gì phát sinh, là 13, 5, 14, 15, 6, 1, 16, 7, 9, 8, 2, 3, 4, 11, 12.
2. Chính sách bỏ gói, chiều dài hàng đợi, số lượng hàng đợi WFQ:
- WFQ sử dụng chính sách hủy gói cuối hàng đợi có hiệu chỉnh. Quyết định hủy gói dựa trên nhiều yêu tố, một trong số đó là số tuần tự của gói.
- WFQ đặt giới hạn tuyệt đối cho số gói vào hàng đợi; giá trị này gọi là “giới hạn giữ hàng đợi” (hold-queue limit). Nếu một gói mới đến, hàng đợi đạt đến giá trị giới hạn; gói đó bị hủy. Quyết định này không dựa trên một hàng đợi mà nó căn cứ vào hệ thống lập hàng đợi WFQ.
- Quyết định kế tiếp dựa trên một hàng đợi. Nếu một gói cần đặt vào hàng đợi và tiến đến ngưỡng bỏ gói CDT (Congestive Dircard Threshold) của hàng đợi, các gói có thể bỏ. CDT là kích thước hàng đợi ứng với hàng đợi của mỗi luồng. Hình 3-13 minh hoạ việc sử dụng CDT.

http://usera.imagecave.com/98765/QOS_hinh23.jpg
- Kích thước của “hàng đợi giới hạn” giới hạn tổng số gói trong luồng. Tuy nhiên, CDT giới hạn số gói trong mỗi hàng đợi cụ thể. Các gói mới đến sẽ bị hủy khi hàng đợi đạt đến CDT. Nếu hàng đợi của 2 luồng đều đến giá trị CDT, WFQ sẽ bỏ luồng nào có SQ cao hơn. Chúng ta có thể cấu hình giá trị CDT trong khoảng từ 1 đến 4096.

http://usera.imagecave.com/98765/QOS_hinh24.jpg


Sao ko thấy hình minh họa nên đọc khó hiểu quá

[deep_blue]

bạn co the share tài liệu này cho mình hay hiệu chỉnh lại dùm mấy cái hình minh họa ko, minh ko xem được mấy cái hình này. Mình đang làm đồ án về cái này nên rất cần. Cám ơn nhiều.
email honey28785@yahoo.com