Một giải pháp lập lịch gói tin đảm bao yêu cầu chất lượng dịch vụ của mạng WiMAX

MỘT GIẢI PHÁP LẬP LỊCH GÓI TIN ĐAM bao yêu câu
CHẤT LƯỢNG DỊCH vụ CỦA MẠNG WIMAX
PHẠM TUẤN MINH, NGUYEN THÚC HẢl2
2Khoa Công nghệ thông tin, Đại học Bách khoa Hà Nội
Abstract. In this paper, we propose a solution to apply the scheduling algorithm DRR to uplink packet scheduling in WiMAX network using the PMP mode and time-division duplex. We have implemented the proposed solution in the NS-2 simulator. The results show that the proposed solution satisfies the Quality-of-Service (QoS) requirements of all the service classes in the fair allocation of bandwidth.
Tóm tắt. Công nghệ mạng truy cập băng thông rộng không dây WiMAX được xác định theo chuẩn IEEE 802.16. WiMAX có nhiều đặc điểm tiến bộ so với các công nghệ mạng truy cập không dây khác. Một trong các đặc điểm đó là hỗ trợ chất lượng dịch vụ tại tầng MAC. Để thực hiện điều này, IEEE 802.16 định nghĩa cơ chế báo hiệu cho việc trao đổi thông tin giữa trạm cơ sờ (BS) và trạm thuê bao (SS) nhưng IEEE 802.16 không định nghĩa thuật toán lập lịch cho các luồng dịch vụ. Để hoàn thiện cơ chế đảm bảo chất lượng dịch vụ của IEEE 802.16, các nhà sản xuất thiết bị cho mạng WiMAX phải xác định được thuật toán lập lịch cho các thiết bị. Bài báo này đề xuất một phương pháp áp dụng thuật toán lập lịch DRR (Deficit Round Robin) vào việc lập lịch gói tin đường lên ờ chế độ PMP (Point-to-Multipoint) và sử dụng ghép kênh theo thời gian. Thuật toán đề xuất được kiểm chứng và đánh giá bằng chương trình mô phỏng NS-2. Kết quả mô phỏng cho thấy phương pháp đề xuất thỏa mãn yêu cầu chất lượng dịch vụ trong việc phân phối cấp phát băng thông công bằng cho tất cả các kiểu luồng dịch vụ của IEEE 802.16.
GIỚI THIỆU
Trong [13] hỗ trợ nhiều dịch vụ truyền thông (dữ liệu, tiếng nói, truyền hình) với các yêu cầu chất lượng dịch vụ khác nhau. Lớp MAC định nghĩa các cơ chế báo hiệu chất lượng dịch vụ và các chức năng điều khiển việc truyền dữ liệu của BS và ss. Trên hướng xuống, việc truyền thông tương đối đơn giản vì BS là thành phần duy nhất truyền trong các khung con đường xuống. Các gói tin được truyền quảng bá tới mọi ss và ss chỉ nhận các gói tin có địa chỉ đích là nó. Trên hướng lên, khi sử dụng ghép kênh theo thời gian, BS xác định số khe thời gian mà mỗi ss sẽ được phép truyền trong một khung con đường lên. BS quảng bá thông tin này qua bản tin UL-MAP tại vị trí bắt đầu mỗi khung. UL-MAP chứa các phần tử thông tin. Các phần tử thông tin chứa các cơ hội truyền, nghĩa là các khe thời gian mà ss có thể truyền trong khung con đường lên. Sau khi nhận UL-MAP, mỗi ss sẽ truyền dữ liệu trong các khe thời gian đã định nghĩa trong các phần tử thông tin. Mô đun lập lịch đường lên tại BS xác định các phần tử thông tin dựa trên các BW-request mà ss gửi tới. IEEE 802.16 định nghĩa các cơ chế báo hiệu chất lượng dịch vụ nhưng nó không định nghĩa bộ lập
lịch đường lên. Hình 1 minh hoạ kiến trúc chất lượng dịch vụ đường lên của IEEE 802.16.
Chuẩn 802.16 định nghĩa hai chế độ chia sè phương tiện không dây la? PMP và Mesh. Với PMP, BS phục vụ một tập các ss trong một phạm vi bao phủ của ăng-ten, tất cả ss nhận cùng thông tin như nhau từ BS. Việc truyền từ các ss được điều khiển bởi BS. Trong chế độ Mesh, lưu lượng có thể được truyền giữa các ss với nhau, điều khiển truy cập được phân bố giữa các ss. Chế độ hoạt động PMP thích hợp với kịch bản nhiều thuê bao dịch vụ được phục vụ bởi một nhà cung cấp dịch vụ trung tâm. Mục đích để các thuê bao có thể truy cập mạng bên ngoài (ví dụ Internet) hoặc các dịch vụ như truyền hình số. PMP làmô hình hoạt động được ứng dụng phổ biến và tập trung nghiên cứu trong chế độ hoạt động này.
Hình 1. Kiến trúc chất lượng dịch vụ đường lên của IEEE 802.16
Trong Hình 1, ta có các nhận xét:
Lập lịch gói tin đường lên (UPS) nằm trong BS để điều khiển toàn bộ việc truyền gói tin đường lên. IEEE 802.16 định nghĩa lập lịch đường lên cho luồng dịch vụ UGS, không định nghĩa lập lịch đường lên cho luồng dịch vụ rtPS, nrtPS, BE.
Vì giao thức MAC của IEEE 802.16 là hướng kết nối, đầu tiên ứng dụng thiết lập kết nối với BS cũng như với các luồng dịch vụ liên quan (UGS, rtPS, nrtPS hoặc BE). BS sẽ gán mỗi kết nối với một định danh kết nối duy nhất (CID). Kết nối có thể biểu diln một ứng dụng cụ thể hoặc một nhóm ứng dụng trong cùng một ss gửi dữ liệu với cùng CID. IEEE 802.16 định nghĩa báo hiệu kết nối (yêu cầu kết nối, trả lời kết nối) giữa ss và BS nhưng nó không định nghĩa quá trình kiểm soát cho phép.
Tất cả các gói tin từ lớp ứng dụng trong ss được phân loại bởi bộ phân loại kết nối dựa trên CID và được chuyển tới hàng đợi thích hợp.
Tại ss, bộ lập lịch sẽ triệu hồi các gói tin từ các hàng đợi và truyền chúng ra mạng trong các khe thời gian thích hợp xác định bởi UL-MAP được gửi bởi BS.
UL-MAP được xác định bởi mô đun UPS dựa trên các bản tin BW-Request.
Như vậy, chúng ta có nhận xét là trong kiến trúc chất lượng dịch vụ đường lên, IEEE 802.16 định nghĩa cơ chế báo hiệu cho việc trao đổi thông tin giữa BS và ss như thiết lập kết nối, BW-Request và UL-MAP nhưng không định nghĩa lập lịch đường lên cho luồng dịch vụ rtPS, nrtPS, BE. Như vậy, khi sản xuất các thiết bị BS, các nhà sản xuất phải nghiên cứu quyết định thuật toán lập lịch đường lên cho thiết bị này. Cơ chế đảm bảo chất lượng dịch vụ mà IEEE 802.16 đưa ra đảm bảo cho các thiết bị phối hợp hoạt động với nhau trong khi thuật toán quyết định vấn đề đảm bảo yêu cầu chất lượng dịch vụ.
Claudio Cicconetti, Luciano Lenzini, Enzo Mingozzi và Carl Eklund [1] đã phân tích để lựa chọn thuật toán thích hợp áp dụng cho bộ lập lịch gói tin và đã nhận xét:
Deficit Round Robin (DRR) là thuật toán lập lịch kết hợp nhiều ưu điểm, cân bằng giữa việc đảm bảo phân phối băng thông công bằng và độ phức tạp tính toán. DRR cung cấp khả năng xử lý công bằng trong trường hợp gói tin có kích thước thay đổi, thời gian xử lý một gói tin có độ phức tạp là 0(1). DRR đòi hỏi một tốc độ tối thiểu dành cho mỗi luồng dịch vụ. Vì vậy, mặc dù chuẩn 802.16 không đòi hỏi, dịch vụ kiểu BE nên cung cấp tốc độ tối thiểu. Điều này có thể khai thác để tránh lưu lượng BE không được phục vụ trong trường hợp quá tải và lưu lượng BE có thể sử dụng băng thông không dành cho các dịch vụ lập lịch khác.
DRR giả sử rằng biết kích thước của gói tin cuối mỗi hàng đợi. Vì vậy, thuật toán này không thể sử dụng bởi BS để lập lịch truyền trong hướng lên. Với hướng lên, BS chỉ có khả năng ước lượng tổng toàn bộ lượng lưu lượng chưa xử lý của mỗi kết nối mà không biết được kích thước của mỗi gói tin chưa được xử lý. Vì vậy, các tác giả đã chọn Weighted Round Robin (WRR) làm thuật toán lập lịch đường lên cho 802.16.
Mục 2 sẽ đề xuất cách áp dụng thuật toán DRR trong việc lập lịch gói tin đường lên ờ chế độ PMP sử dụng ghép kênh theo thời gian. Các kịch bản và kết quả mô phỏng để đánh giá thuật toán đề xuất được trong Mục 3, và cuối cùng, Mục 4 là các kết luận và hướng phát triển kết quả nghiên cứu.
ÁP DỤNG THUẬT TOÁN DRR CHO LẬP LỊCH ĐƯỜNG LÊN
A. Thuật toán DRR
Lập lịch gói tin là việc xác định thứ tự phục vụ các gói tin. Kiểu phục vụ đơn giản nhất là FIFO nhưng kiểu này không cung cấp bất kỳ sự phân biệt nào giữa các luồng dịch vụ. Nếu phục vụ theo kiểu FIFO thì nếu một luồng gửi một lượng lớn dữ liệu sẽ gây trl cho tất cả các luồng còn lại. Một kiểu phục vụ khác là theo kiểu vòng tròn của các hàng đợi. Mỗi luồng dịch vụ được tổ chức thành một hàng đợi, các gói tin thuộc luồng dịch vụ nào sẽ được xếp vào hàng đợi của luồng dịch vụ đó. Tuy vậy, vấn đề là sự không công bằng bởi vì có khả năng các luồng dịch vụ khác nhau có gói tin kích thước khác nhau. Khi đó, một luồng dịch vụ có thể chiếm gấp Max/Min lần băng thông của luồng dịch vụ khác, trong đó Max là kích thước lớn nhất của gói tin, Min là kích thước nhỏ nhất của gói tin.
Thuật toán DRR [6] giải quyết được hạn chế trên và độ phức tạp tính toán xử lý một gói tin là hằng số. Thuật toán DRR phục vụ vòng tròn các hàng đợi theo một giá trị phục vụ gán cho mỗi hàng đợi (giá trị này gọi là Quantum). Sự khác nhau duy nhất so với kiểu phục vụ vòng tròn các hàng đợi truyền thống là nếu một hàng đợi không có khả năng gửi một gói tin trong vòng lặp trước bởi vì kích thước của gói tin quá lớn thì phần còn lại của Quantum trước sẽ được cộng vào giá trị Quantum cho vòng lặp tiếp. Vì vậy, sự thiếu hụt được theo dõi, các hàng đợi mà bị thiếu trong vòng lặp trước được bù trong vòng lặp tiếp theo.
Thuật toán DRR định nghĩa Quanturĩỉi là số byte dành cho hàng đợi i mỗi vòng lặp. Một vòng lặp là một quá trình xử lý duyệt qua các hàng đợi đang chờ xử lý.
Các gói tin đến trong các luồng dịch vụ khác nhau được chứa trong các hàng đợi khác nhau. Đặt số byte gửi ra khỏi hàng đợi i trong vòng lặp thứ k là bytesiỌA). Mỗi hàng đợi i được phép gửi các gói tin trong vòng lặp đầu tiên thoả mãn byteSi(l) < Quantum^ Nếu không có gói tin trong hàng đợi i sau khi hàng đợi đã được phục vụ, biến trạng thái DeficitCounteri sẽ khởi tạo lại giá trị 0. Ngược lại, phần còn lại (Quanturĩỉi — byteSi(k)) được gán cho biến trạng thái DeficitCounteri. Trong các vòng lặp sau, lượng băng thông sử dụng bởi luồng dịch vụ này là tổng của DeficitCounteri của vòng lặp trước với Quanturĩỉi.
Để tránh kiểm tra các hàng đợi rỗng, thuật toán DRR xây dựng một danh sách Activ eList là danh sách của các hàng đợi chứa ít nhất một gói tin. Bất kỳ khi nào một gói tin tới một hàng đợi rỗng i, i được bổ sung vào cuối của ActiveList. Khi nào chỉ số i nằm ờ đầu danh sách Activ eList) thuật toán phục vụ hàng đợi i với giá trị tối đa là Quanturĩỉi + DeficitCounteribyte. Nếu tại cuối quá trình phục vụ hàng đợii này, hàng đợi i vẫn có gói tin để gửi, chỉ số i được di chuyển tới cuối của Activ eList) ngược lại DeficitCounteri được gán giá trị 0 và chỉ số i sẽ bị loại bỏ khỏi Activ eList.
Mô đun Enqueueing thực hiện xử lý khi một gói tin đến. Mô đun Dequeueing xử lý lập lịch cho việc gửi gói tin. Sau đây là mã giả mô tả chi tiết thuật toán.
Các biến và thao tác:
Queuei là hàng đợi thứ i chứa các gói tin của luồng dịch vụ i.
Các hàng đợi được đánh số từ 0 tới (n — 1), n là số hàng đợi lớn nhất tại đường ra.
Activ eList là danh sách các luồng dịch vụ hoạt động.
Quanturĩỉi là giá trị lưu lượng dành cho Queueị.
DeficitCounteri chứa số byte mà Queuei không sử dụng trong vòng lặp trước.
InsertActiveList thực hiện thêm chỉ số của luồng dịch vụ vào cuối danh sách Activ eList.
RemoveActiv eList thực hiện lấy và loại bỏ chỉ số của luồng dịch vụ ờ đầu danh sách Activ eList.
EnqueueQ là thao tác đưa một gói tin vào hàng đợi.
DequeueQ là thao tác lấy một gói tin ra khỏi hàng đợi.
ExtractFlow(p) xác định gói tin p thuộc hàng đợi nào.
Bước khởi tạo:
For (i = 0 -)i < n-)i = i + 1) DeỊicitCounteTi = 0;
Mô đun Enqueueing:
i = ExtractFlow(p)
If then
Insert ActiveListự);
DeỊicitCounteTi = 0;
Enqueue{i)pỴ)
MÔ đun Dequeueing:
While (TRUE) do
If then
i = RemoveActiveListQ
DeficitCounteri = Quantum^ + DeficitCounteri;
While (DeficitCounteri > 0) and (Queuei không rỗng) do Packetsize = Size(H ead(Queuci)};
If (Packetsize < DeficitCounteri) then
Senả(Dequeue(Queuei)};
DeficitCounteri = DeficitCounteri — Packetsize;
Else break;
If (Empty(QueueiỴ) then
DeficitCounteri = 0;
Else Insert ActiveList(i);
Ví dụ minh hoạ bước xử lý của thuật toán.
Giả sử danh sách Activ eList có 4 hàng đợi. Giá trị Quantum bằng 500.
Bắt đầu, biến DeficitCounteri khởi tạo giá trị 0 với mọi hàng đợi i. Con trỏ Round Robin chỉ tới đỉnh của Activ eList. Khi hàng đợi đầu tiên được phục vụ, giá trị Quantum bằng 500 được gán cho biến DeficitCounteri (Hình 2).
Hình 2. Ví dụ minh hoạ thuật toán DRR (1)
Hình 3. Ví dụ minh hoạ thuật toán DRR (2)
Sau khi gửi một gói tin có kích thước 200, hàng đợi thứ nhất có giá trị DeficitCounterl =
500 — 200 = 300 byte. Nó không thể sử dụng trong vòng lặp hiện tại, do gói tin tiếp theo trong hàng đợi có kích thước 750 byte. Vì vậy, giá trị 300 sẽ được chuyển tới vòng lặp tiếp theo. Trong vòng lặp tiếp theo, hàng đợi này có thể gửi các gói tin kích thước nhỏ hơn hoặc bằng 800 (300 từ vòng lặp trước cộng với giá trị Quantum 500) (Hình 3).
Áp dụng thuật toán DRR cho lập lịch đường lên
Như đã nói ở trên, các tác giả trong [1] đã phân tích các ưu điểm của thuật toán DRR trong việc lập lịch gói tin IEEE 802.16, tuy nhiên không thể áp dụng thuật toán DRR cho việc lập lịch gói tin đường lên bởi nó đòi hỏi phải biết kích thước của gói tin cuối mỗi hàng đợi khi xử lý trong khi đối tượng xử lý của lập lịch gói tin đường lên là các BW-request chứa băng thông yêu cầu. Chúng ta không biết được kích thước của từng gói tin trong đường lên. Phương án giải quyết là chúng ta thay đổi đối tượng xử lý của thuật toán DRR là các gói tin bằng các BW-request. Khi đó, việc phân phối băng thông vẫn đảm bảo công bằng giữa các luồng dịch vụ, do đó lập lịch các gói tin đường lên được thực thi.
Các vấn đề tiếp theo cần tiếp tục xác định là:
Xác định các hàng đợi.
Cách tính giá trị Quantum.
Do băng thông dịch vụ UGS được dành riêng nên chúng ta không phải lập lịch cho các dịch vụ UGS. Như vậy, chúng ta có 3 hàng đợi cho các dịch vụ rtPS, nrtPS và BE.
Do các dịch vụ rtPS cần đảm bảo hơn về yếu tố thời gian thực so với dịch vụ nrtPS, dịch vụ BE không có ràng buộc về đảm bảo chất lượng dịch vụ nên chúng ta sắp thứ tự ưu tiên phục vụ các hàng đợi này như sau rtPS > nrtPS > BE.
Chúng ta sẽ sử dụng một danh sách ActiveList chứa các hàng đợi cần lập lịch. DRR chỉ lập lịch cho các hàng đợi trong danh sách Activ eList. Nếu hàng đợi không rỗng, nó sẽ trong danh sách ActiveList. Ngược lại, nó sẽ bị loại bỏ khỏi danh sách ActiveList. Các hàng đợi của các luồng dịch vụ trong danh sách ActiveList được xếp hàng theo độ ưu tiên cố định như trên. Trong mỗi vòng lặp, hàng đợi của luồng dịch vụ có độ ưu tiên cao nhất sẽ luôn được phục vụ trước. Trong thuật toán DRR, bộ lập lịch sẽ thăm mỗi hàng đợi không rỗng Z, xác định kích thước gói tin tại đỉnh của hàng đợi, biến DeficitCounteri được tăng bởi một giá trị Quantumị. Áp dụng trong bộ lập lịch đường lên, các yêu cầu băng thông sẽ được phục vụ trong hàng đợi. Khi bộ lập lịch thăm mỗi hàng đợi không rỗng i trong Activ eList) biến DeficitCounteri được cộng thêm giá trị Quantumị. Nếu kích thước dữ liệu yêu cầu của gói tin BW-REQ tại đỉnh của hàng đợi nhỏ hơn hoặc bằng giá trị DeficitCounteri thì biến DeficitCounteri giảm một lượng bằng kích thước băng thông yêu cầu và gói tin được truyền tới cổng ra. Quá trình được lặp lại tới khi DeficitCounteri nhỏ hơn hoặc bằng 0, hoặc hàng đợi rỗng. Nếu hàng đợi rỗng, giá trị DeficitCounteri cũng được gán bằng 0. Khi điều kiện này xảy ra, bộ lập lịch chuyển tới phục vụ hàng đợi ưu tiên không rỗng tiếp theo.
Vấn đề tiếp theo là cách xác định Quantum. Một cách tính Quanturĩỉi của lớp của luồng dịch vụ thứ i là
Ji
Quantum[i] = y^rmĩaí(i,jỴ
j=ữ
trong đó, Ji là tổng số kết nối cho lớp thứ i của luồng dịch vụ. Chú ý là đối với kết nối mà Tmax của nó không được chỉ định (ví dụ rmax = 0 trong bản tin DSA), rmax sẽ được gán bằng rmin. Tốc độ dịch vụ của kết nối có giá trị Quantum lớn hơn sẽ lớn hơn kết nối có giá trị Quantum nhỏ.
Các bước thuật toán DRR áp dụng trong bộ lập lịch gói tin đường lên trong IEEE 802.16 như sau.
Buớc 1. Cập nhật danh sách ActiveList.
Nếu một hàng đợi của kết nối là rỗng, chúng ta loại bỏ nó khỏi danh sách ActiveList. Nếu hàng đợi của kết nối thay đổi từ rỗng sang không rỗng, chúng ta thêm nó vào danh sách Activ eList. Các luồng dịch vụ trong danh sách ActiveList sẽ được xếp hàng theo độ ưu tiên rtPS > nrtPS > BE.
Buớc 2. Cập nhật các tham số cho mỗi hàng đợi dịch vụ.
Gọi La là dung lượng khả dụng của một TDD frame tính theo byte, Ltotai là tổng dung lượng của một TDD frame.
Giá trị khởi tạo của La. La = Ltotai.
Giá trị khởi tạo của DeficitCounter[i]) DeficitCounter[i] = Quantum[i]. Buớc 3. Phục vụ các kết nối trong luồng dịch vụ với từng hàng đợi theo độ ưu tiên tới khi một trong các điều kiện sau thoả mãn:
Điều kiện (1): DeficitCounter[í\ < 0.
Điều kiện (2): Hàng đợi là rỗng.
Điều kiện (3): Không còn băng thông khả dụng, La < 0.
Điều kiện (4): Đến thời điểm gửi bản tin UL-MAP.
Nếu điều kiện (1) hoặc (2) thoả thì chuyển sang Bước 4.
Nếu điều kiện (3) hoặc (4) thỏa thì chuyển sang Bước 5.
Buớc 4. Nếu còn hàng đợi có độ ưu tiên thấp hơn thì phục vụ các hàng đợi có độ ưu tiên thấp hơn như trong Bước 3. Nếu không có hàng đợi ưu tiên thấp hơn nào, thì quay lại Bước 3 và thực hiện vòng lặp lập lịch mới.
Buớc 5. Gửi bản tin UL-MAP và kết thúc việc lập lịch cho TDD frame hiện tại. Quay trở lại Bước 1 cho TDD frame tiếp theo.
Ví dụ: danh sách Activ eList có hai hàng đợi của luồng dịch vụ rtPS và BE. Quantum[rtPS] = 1000, Quantum[BE] = 500, Ltotai = 2500.
Vòng lặp 1
Bước 1: Cập nhật danh sách Activ eList.
Bước 2: Cập nhật các tham số cho các hàng đợi hoạt động
DeficitCounter[rtPS] = 1000
DeficitCounter[BE] = 500
La = 2500
Bước 3(1):
Vì gói tin yêu cầu băng thông BW-REQ tại đỉnh của hàng đợi rtPS nhỏ hơn giá trị của DeficitCounter[rtPS] = 1000, BW-REQ 600 byte được phục vụ. Giá trị DeficitCounter[rtPS] bị giảm đi 600, kết quả giá trị mới là 400.
Sau đó, BW-REQ 300 byte ờ đỉnh hàng đợi rtPS nhỏ hơn 400 nên gói tin 300 byte được phục vụ, kết quả giá trị mới của DeficitCounter[rtPS] = 100.
Tiếp theo, BW-REQ 400 byte trong hàng đợi rtPS sẽ được phục vụ DeficitCounter[rtPS] = 100 — 400 = — 300(< 0). Điều kiện (1) xảy ra, chuyển sang Bước 4.
Kết thúc bước này, La = 2500 — 600 — 300 — 400 = 1200.
Vòng lặp 1
Hàng đợi rtPS (Quantum[rtPS] = 1000)
I 200 II 400 II 300 II 600 I
Hàng đợi BE (Quantu'm[BE] = 500) 	
I 500 II 300 II 400 I
Hàng đợi rtPS (Quantum[rtPS] = 1000)
I	l200l
2 J Hàng đợi BE
(Quantu'm[BE] = 500) 	
[ I 500 II 300 II 400 I
DeficitCounter[rtPS] =
= Quantum[rtPS]-600~300-400 = -300
400	300	600 I ◄—	——
Hàng đợi
_	 đang phục vụ
DeficitCounteifBE] = 0
0	La = 1200
DeficitCounterlrtPS] = -300
0
DeficitCounterlBE] = =Quantum[BE1-400-300 = -200
I 300 II 40^ Hàng đợi đang phục vụ
La =500
Vòng lặp 2
Hàng đợi rtPS (Quantum[rtPS] = 1000)
I 200 I
1	, _	_	
J Hàng đợi BE (Quantum[BE] = 500) 	
I 500 I
Hàng đợi rtPS (Quantum[rtPS] = 1000)
Hàng đợi BE (Quantum[BE] = 500) 	
I 500 I
DeficitCounter[rtPS] = =-300+Quantum[rtPS]-200 = 500 200Hàng đợi đang phục vụ
DeficitCounter[BE] = -200 0	La = 300
DeficitCounter[rtPS] = 0
I 0 I
DeficitCounter[BE] =
=-200+Quantum[BE]-300 = 0
I 300 lu Hàng đợi
đang phục vụ
La = 0
Hình 4- Thuật toán DRR áp dụng trong bộ lập lịch gói tin đường lên
Bước 4(1): Chúng ta kiểm tra thấy còn hàng đợi có độ ưu tiên thấp hơn là hàng đợi BE. Do đó, chuyển tới bước 3 phục vụ hàng đợi BE.
Bước 3(2):
Hàng đợi BE sẽ được phục vụ tới khi DeficitCounter[BE] < 0.
DeficitCounter[BE] = 500 - 300 - 400 = -200
La = 1200 - 300 - 400 = 500.
Bước 4(2): Vì không còn luồng dịch vụ nào khác mà vẫn còn băng thông khả dụng, nên sẽ thực hiện vòng lặp mới.
Vòng lặp 2
Bước 3(1): Trong vòng lặp thứ 2, luồng rtPS có độ ưu tiên cao nhất. Đầu tiên, DeficitCounter[rtPS] sẽ bằng tổng của Quantum[rtPS] và DeficitCounter[rtPS] trong vòng lặp trước:
DeficitCounter[rtPS] = 1000+ (-300) = 700.
Sau đó, yêu cầu BW-REQ 200 byte sẽ được xử lý:
DeficitCounter[rtPS] = 700 - 200 = 500.
La = 500 - 200 = 300.
Hàng đợi rtPS rỗng nên điều kiện (2) xảy ra, chuyển sang Bước 4.
Bước 4(1): Chúng ta kiểm tra thấy còn hàng đợi có độ ưu tiên thấp hơn là hàng đợi BE. Do đó, chuyển tới Bước 3 phục vụ hàng đợi BE.
Bước 3(2): Ta có DeficitCounter[BE] = —200 + 500 = 300.
Yêu cầu BW-REQ 500 byte sẽ được xử lý, do băng thông khả dụng chỉ còn 300 nên chỉ có 300 byte được xử lý:
DeficitCounter[rtPS] = 300 — 300 = 0,
La = 300 - 300 = 0.
Điều kiện (3) thoả mãn nên chúng ta chuyển sang Bước 5.
Bước 5: Việc lập lịch kết thúc cho TDD frame này.
Chú ý là trong Bước 3(2) của vòng lặp 2, chỉ có 300 byte được chấp nhận trong BS cho BW-REQ 500 byte, ss thực hiện phân mảnh gói tin 500 byte. Khung con 300 byte đầu tiên sẽ được gửi đi và khung con 200 byte còn lại sẽ được truyền tiếp trong khung TDD tiếp theo.
Áp dụng thuật toán DRR trong việc lập lịch gói tin, chúng ta thấy trong mỗi vòng lập lịch, hàng đợi có độ ưu tiên cao nhất sẽ được phục vụ đầu tiên tới khi băng th” ng chia phần cho nó thiếu. Vì vậy, đây là lập lịch dựa vào hàng đợi ưu tiên. Mặt khác, nếu băng th” ng chia phần thiếu đối với hàng đợi có độ ưu tiên cao hơn, luồng dịch vụ với hàng đợi có độ ưu tiên thấp hơn sẽ có cơ hội được phục vụ, đó là một giải pháp công bằng cho hàng đợi có độ ưu tiên thấp hơn, khác với hàng đợi có độ ưu tiên cố định.
ĐÁNH GIÁ
Bộ phần mềm mô phỏng NS-2 được sử dụng để kiểm nghiệm và đánh giá giải pháp đề xuất : áp dụng thuật toán DRR cho lập lịch gói tin đường lên đã trình bày trong phần trên. Chúng tôi đã thực hiện cài đặt các kiểu dịch vụ uGS, rtPS, nrtPS, BE và cài đặt thuật toán DRR cho bộ lập lịch gói tin của IEEE 802.16 trên NS-2.
Kịch bản mô phỏng gồm hai ss và một BS. Băng thông BS có khả năng đáp ứng là 800 Kbps, ss 1 chạy dịch vụ BE bắt đầu tại thời điểm 0,5 s với tốc độ trung bình 512 Kbps, ss 2 chạy dịch vụ rtPS bắt đầu tại thời điểm 10s với tốc độ trung bình 512 Kbps. Kết quả thu được như trên Hình 5.
Hình 5. Mô phỏng thuật toán DRR áp dụng trong lập lịch gói tin đường lên
Kết quả băng thông dành cho các dịch vụ BE giảm để cấp pháp cho dịch vụ rtPS. Như vậy, băng thông của dịch vụ BE (dịch vụ không yêu cầu đảm bảo chất lượng dịch vụ) sẽ giảm để Cấp phát cho các dịch vụ có độ ưu tiên cao hơn.
KẾT LUẬN VÀ HƯỚNG PHÁT TRIEN
Bài báo đã trình bày về mô hình đảm bảo chất lượng dịch vụ của mạng WiMAX tại tầng MAC, chỉ ra các điểm mà chuẩn IEEE 802.16 không định nghĩa và tập trung nghiên cứu vấn đề lập lịch đường lên. Các tác giả đã đề xuất phương án nhằm khắc phục hạn chế mà các tác giả trong [1] đã chỉ ra, để áp dụng thuật toán DRR vào việc lập lịch gói tin đường lên. Kết quả mô phỏng thuật toán trên NS-2 đã chứng minh việc đảm bảo phân phối băng thông công bằng cho các kiểu luồng dịch vụ của IEEE 802.16. Tuy nhiên, cần tiếp tục nghiên cứu để đánh giá hiệu năng của giải pháp đề xuất, trước hết cần xác định rõ các điều kiện để đảm bảo độ trl trong việc lập lịch gói tin đường lên khi áp dụng thuật toán DRR.
Các kết quả nghiên cứu trình bày trong bài báo này nằm trong khuôn khổ các mục tiêu nghiên cứu của Đề tài nghiên cứu cơ bản về mạng viln thông thế hệ mới NGN (mã số KHCB 2.14.06).
TÀI LIỆU THAM KHẢO
Claudio Cicconetti, Luciano Lenzini, Enzo Mingozzi, Carl Eklund, Quality of service support in IEEE 802.16 networks, IEEE Network 20 (2006) (2) 50-55.
David Johnston, Jesse Watker, Overview of IEEE 802.16 Security, IEEE Security & Privacy 2 (3) (2004) 40-48.
John Soldatos, On the building blocks of quality of service in heterogeneous IP networks, IEEE Communications Surveys & Tutorials 7 (1) (2005) 70-89.
LAN MAN Standards Committee of IEEE Computer Society and the IEEE Microwave Theory and Techniques Society (2004), IEEE Standard for Local and metropolitan area networks - Part 16: Air Interface for Fixed Broadband Wireless Access Systems, IEEE STD 802.16-2004- THE LOAI GI NHI??
LAN MAN Standards Committee of IEEE Computer Society and the IEEE Microwave Theory and Techniques Society (2006), IEEE Standard for Local and metropolitan area networks Part 16: Air Interface for Fixed and Mobile Broadband Wireless Access Systems Amendment 2: Physical and Medium Access Control Layers for Combined Fixed and Mobile Operation in Licensed Bands and Corrigendum 1, IEEE STD 802.16e-2005. THE LOAI GI NHI??
M. Shreedhar, George Varghese, Efficient fair queuing using deficit round robin, IEEE/ACM Transactions on Networking 4 (3) (1996) 375-385.
Senza Fili, “Fixed, nomadic, portable and mobile applications for 802.16-2004 and 802.16e WiMAX networks”, WIMAX Forum, (2005).
WiMAX Forum, “Mobile WiMAX - Part I: A Technical Overview and Performance Evaluation”, (2006). o DAU NHI?
WiMAX Forum, “Recommendations and Requirements for Networks based on WiMAX Forum CertifiedTM Products”, Release 1.0, (2006) 21-25.
WiMAX Forum, “WiMAX End-to-End Network Systems Architecture Stage 2: Architecture Tenets, Reference Model and Reference Points, Part 1”, (2006). TIM o DAU NHI?
WiMAX Forum, “WiMAX End-to-End Network Systems Architecture Stage 2: Architecture Tenets, Reference Model and Reference Points, Part 2”, (2006).
WiMAX Forum, “WiMAX End-to-End Network Systems Architecture Stage 2: Architecture Tenets, Reference Model and Reference Points, Part 3”, (2006).
The IEEE 802.16 Working Group on Broadband Wireless Access Standards, www.ieee802.org/16/.
WiMAX Forum, www.wimaxforum.org.
Phạm Tuấn Minh, “Nghiên cứu vấn đề chất lượng dịch vụ và an toàn bảo mật trong mạng WiMAX”, Luận văn thạc sỹ , Trường Đại học Bách khoa Hà Nội, 2006.
Nhận bài ngày 21 - 4 - 2008