PERANCANGAN SOFTWARE SCHEDULER UNTUK MAC LAYER WIMAX MENURUT STANDAR IEEE 802.16-2004 Winnu Ayi Satria Mahasiswa Program Studi Teknik Elektro NIM 132 03 050 Sekolah Teknik Elektro dan Informatika Email :
[email protected] Abstraksi Worldwide Interoperability for Microwave Access (WiMAX) menyediakan layanan Broadband Wireless Access teryang menyediakan layanan data pita lebar. Sesuai standard IEEE 802.16-2004, WiMAX mengatur 2 layer terbawah Model 7 OSI Layer, yaitu MAC Layer dan PHY Layer. MAC Layer WiMAX menggunakan metode akses berbasis algoritma penjadwalan (scheduling algorithm). Blok kerja yang bertanggung jawab melakukan proses penjadwalan adalah Scheduler. Makalah ini membahas tentang perancangan Scheduler pada MAC Layer WiMAX. Algoritma yang digunakan adalah Priority Queue, algoritma penjadwalan beberapa queue berdasarkan prioritas queue tersebut. Berdasarkan Quality of Service (QoS), ada 4 macam Scheduler, yaitu UGS, rtPS, nrtPS, dan Best Effort. UGS menggunakan algoritma Fixed Bandwidth, rtPS menggunakan algoritma Earliest Deadline First (EDF), nrtPS menggunakan algoritma Weighted Round Robin (WRR), dan Best Effort menggunakan algoritma Round Robin. Dengan menggunakan algoritma penjadwalan, Scheduler dapat menjamin sebuah layanan dengan kebutuhan bandwidth tinggi dapat terpenuhi dengan menggunakan Quality of Service (QoS). Keyword: WiMAX, Scheduler, Algorithm, Quality of Service
Scheduling
1. PENDAHULUAN Worldwide Interoperability for Microwave Access (WiMAX) dikembangkan oleh Institute Electrical and Electronic Engineering (IEEE) dan dirumuskan dalam standar 802.16-2004 [1]. Teknologi ini memberikan layanan Broadband Wireless Access dengan jarak yang lebih jauh dan performa yang lebih baik daripada teknologi WiFi. WiMAX dirancang untuk menangani Physical Layer (PHY) dan Media Access Control Layer (MAC). PHY Layer bertugas mengirimkan informasi dari transmitter menuju receiver melalui sebuah saluran udara (kanal), sedangkan MAC Layer bertugas melakukan pengalamatan dan mengatur paket – paket data yang harus segera dikirim segera. Pada MAC Layer, blok yang bertugas mengatur paket – paket data tersebut adalah Scheduler [2].
Ada beberapa macam paket – paket data yang dijadwal Scheduler, seperti: 1. Paket Ethernet, IPv4, dan IPv6 2. Bandwidth Request 3. MAC Management Messages 4. Paket Automatic Repeat Request (ARQ) Berdasarkan standar 802.16-2004, Scheduler memiliki fitur Quality of Service (QoS). Ada 4 macam QoS yang digunakan, yaitu: 1. Unsolicitied Grant Service (UGS) 2. Real-time Polling Service (rtPS) 3. Non-real-time Polling Service (nrtPS) 4. Best Effort Kebutuhan – kebutuhan berinternet seperti Voice over IP (VoIP), Video dan Audio Streaming, File Transfer Protocol, Web Browsing, dan masih banyak lainnya akan dipetakan ke dalam empat QoS sesuai prioritasnya masing – masing. Untuk menjamin kepuasan pengguna saat melakukan layanan internet, Scheduler bertanggung jawab mengatur paket – paket data mana saja yang harus segera dijadwal dan dikirim. 2. SCHEDULER MAC WIMAX Scheduler melakukan penjadwalan paket – paket data berdasarkan QoS dan resources yang telah disiapkan. Quality of Service diatur oleh blok Connection Management, sedangkan resources diatur oleh PHY Layer. Dengan adanya permintaan resources dan banyaknya subscriber station yang mengharapkan resources tersebut, maka dibutuhkan algoritma scheduler yang efektif dan efisien untuk melakukan penjadwalan yang optimal. 2.1 Quality Of Service Berikut ini adalah karakteristik QoS yang didukung WiMAX [1], [5], [6]. Unsolicited Grant Service (UGS) Bersifat real-time Constant Bit Rate (CBR) Throughput dijamin. Contoh : VoIP Real-Time Polling Service (rTPS) Bersifat real-time Variable Bit Rate (VBR) Delay Intolerant
Prioritas lebih tinggi terhadap Best Effort dan nRTPS. Contoh : Video & Audio Streaming Non Real-Time Polling Service (nrTPS) Tidak real-time. Variable Bit Rate Delay-tolerant. Prioritas lebih tinggi terhadap Best Effort Contoh : File Transfer Protocol (FTP) Best Effort Service Tidak real-time Variable Bit Rate Tidak ada garansi delay ataupun troughput. Memiliki prioritas paling rendah Contoh : Email, Web Browsing 2.2 Format Data MAC
3. PERANCANGAN 3.1 Penentuan Spesifikasi Untuk penelitian ini, spesifikasi Scheduler dibatasi pada penjadwalan paket – paket data secara downlink saja, sedangkan penjadwalan paket – paket data secara uplink, Management Messages, dan ARQ tidak masuk dalam penelitian ini. Queue Generator
Management
MAC Queue
Fragment Flag Pointer (delete)
Service Flow 0 Global Table Queue
Scheduler
Pointer SDU
MAC Header PDU Queue
Ada 3 macam format data yang harus diperhatikan, yaitu: 1.
Service Data Unit (SDU)
Frame Builder
Komponen utama dari Scheduler adalah 1. Input : MAC Queue & Global Table 2. Output : PDU Queue 3. Process : Scheduler
Data yang dihasilkan oleh Convergence Sublayer (CS). Contoh: Ethernet, IPv4, dan IPv6 2.
Protocol Data Unit (PDU)
Data yang dihasilkan oleh PDU Encoder. Field Generic MAC Header sepanjang 6 byte dan CRC 4 byte. 3.
Frame
Data yang dihasilkan oleh PHY Layer. Bekerja dalam satuan waktu.
Entitas di luar sistem yang berhubungan secara tidak langsung adalah 1. Queue Generator 2. Management 3. Frame Builder Proses yang dapat dilakukan Scheduler adalah sebagai berikut: 1. Proses penjadwalan paket – paket data sesuai QoS (UGS, rtPS, nrtPS, Best Effort) 2. Membentuk PDU Payload berdasarkan policy. Ada 5 macam cara membentuk PDU: a) Tidak packing & Tidak fragmentation b) Hanya fragmentation c) Hanya packing fixed-length d) Hanya packing variable-length e) Packing & fragmentation sekaligus 3. Menampung SDU – SDU terjadwal pada Scheduled Queue 4. Memanggil PDU Encoder untuk melakukan proses enkapsulasi SDU – SDU yang ada di dalam Scheduled Queue menjadi sebuah PDU Algoritma Scheduler yang digunakan secara keseluruhan untuk 4 QoS menggunakan algoritma Priority Queue. Priority Queue merupakan algoritma yang menggunakan beberapa queue dengan prioritas yang berbeda – beda tergantung kebutuhan. Paket akan dijadwal dari sebuah queue
3.3 Perancangan Scheduler UGS UGS Queue: Complex linked list. Dibagi berdasarkan koneksi.
Scheduler
priority
jika queue dengan prioritas lebih tinggi sudah selesai dijadwal.
Urutan algoritma Scheduler: 1. Siapkan resources 2. Scheduler UGS 3. Scheduler rtPS 4. Scheduler nrtPS 5. Scheduler Best Effort 3.2 Integrasi Scheduler dengan PDU Encoder Penelitian selama setahun ini, Scheduler dirancang sebagai blok tersendiri. Namun kemudian muncul masalah sebagai berikut: 1. Perhitungan alokasi bandwidth yang kompleks pada blok Scheduler 2. Proses enkapsulasi PDU yang kompleks pada blok PDU Encoder 3. Terjadinya pemborosan memori yang tidak perlu pada Scheduled Queue
Algoritma: Fixed Bandwidth. Dengan prioritas tertinggi dari QoS lain, UGS dapat mengambil resources sesuai dengan jatah yang diberikan. PDU Encoder: Packing fixed-length 3.4 Perancangan Scheduler rtPS rtPS Queue: Simple linked list. Diurutkan berdasarkan deadline.
Gambar berikut adalah Scheduler versi 1.
Gambar berikut adalah Scheduler versi 2 yang terintegrasi dengan PDU Encoder. Algoritma: Earliest Deadline First (EDF). Paket data dengan deadline terdekat akan dijadwal lebih dahulu. PDU Encoder: Hanya Fragmentation.
Dengan model Scheduler versi 2, masalah – masalah yang sebelumnya muncul dapat teratasi semua. Model seperti ini pun memberikan kemudahan dalam merancang algoritma scheduler yang lebih optimal
3.3 Perancangan Scheduler nrtPS nrtPS Queue: Complex linked list. Dibagi berdasarkan koneksi.
rtPS rtPS nrtPS nrtPS nrtPS Best Effort Best Effort Best Effort
0xfe14 0xfe24 0xfe13 0xfe23 0xfe33 0xfe12 0xfe22 0xfe32
10 ms 20 ms
1 2 1 2 3 1 2 3
Terdapat 3 koneksi UGS, 2 koneksi rtPS, 3 koneksi nrtPS, dan 3 koneksi Best Effort. Input yang digunakan untuk semua koneksi adalah text file. Output yang dihasilkan harus sama dengan input yang dimasukkan. Dari pengujian didapatkan gambar sebagai berikut untuk seluruh koneksi: Algoritma: Weighted Round Robin. Setiap koneksi memiliki bobotnya masing – masing sehingga untuk nrtPS jatah bandwidth akan dibagi sesuai bobot.
160
140
120
UGS 1 UGS 2 UGS 3
100
BE 1 BE 2
80
BE 3 NRTPS 1 NRTPS 2
PDU Encoder: Hanya fragmentation.
60
NRTPS 3 RTPS 1 RTPS 2
40
20
3.3 Perancangan Scheduler Best Effort Best Effort Queue: Complex linked list. Dibagi berdasarkan koneksi.
0 4
1
7
10 13 16 19 22 25 28 31 34 37 40 43 46 49 52 55 58 61 64 67 70 73 76 79 82 85 88 91 94 97
Untuk mempermudah analisis, QoS dipisahkan dalam setiap gambar. Sumbu Y tidak mengalami perubahan untuk keempat gambar berikut. UGS 160 140 120 100
UGS 1
80
UGS 2
60
UGS 3
40 20 0 1
7 13 19 25 31 37 43 49 55 61 67 73 79 85 91 97
Algoritma: Round Robin. Paket data yang datang lebih awal untuk setiap koneksi akan dijadwal terlebih dahulu.
120 100
4. PENGUJIAN DAN ANALISIS Dilakukan pengujian Scheduler dengan 4 QoS sekaligus. Skenario yang disiapkan sebagai berikut: CID 0xfe11 0xfe21 0xfe31
Deadline
160 140
PDU Encoder: Packing & Fragmentation sekaligus.
QoS UGS UGS UGS
rtPS
DIUC 1 2 3
RTPS 1
80
RTPS 2
60 40 20 0 1 7 13 19 25 31 37 43 49 55 61 67 73 79 85 91 97
nrtPS
beberapa waktu kemudian. Penjadwalan NRTPS 2 dan NRTPS 3 dilakukan ketika paket data RTPS 1 telah selesai dijadwalkan sehingga resources yang tersisa masih cukup banyak.
160 140 120 100
NRTPS 1
80
NRTPS 2
60
NRTPS 3
40 20 0 1 7 13 19 25 31 37 43 49 55 61 67 73 79 85 91 97
Best Effort 160 140 120 100
BE 1
80
BE 2
60
BE 3
40 20 0 1
7 13 19 25 31 37 43 49 55 61 67 73 79 85 91 97
UGS menggunakan algoritma Fixed Bandwidth. Dengan melihat gambar UGS, terlihat bahwa grafik UGS untuk ketiga CID berbentuk lurus selama beberapa waktu dan kemudian menurun tajam ketika paket data setiap koneksi habis terjadwalkan. Hal ini terjadi karena Scheduler UGS dijalankan terlebih dahulu daripada 3 Scheduler yang lainnya sehingga resources yang disediakan masih banyak untuk digunakan. Untuk rtPS, algoritma yang digunakan adalah Earliest Deadline First di mana paket – paket data yang memiliki deadline paling dekat dengan waktu eksekusinya akan segera dijadwalkan. Jika diperhatikan pada gambar rtPS, terlihat bahwa CID 0xfe14 (RTPS 1) memiliki grafik yang menaik tajam, sedangkan pada saat yang bersamaan grafik CID 0xfe24 (RTPS 2) menurun tajam. Ini terjadi karena RTPS 1 memiliki deadline lebih kecil, yaitu 10 ms ketimbang RTPS 2 dengan deadline 20 ms. Jadi, meskipun ada paket RTPS 2 yang datang lebih dahulu dan kemudian selang beberapa waktu datang paket RTPS 1 dengan deadline yang lebih kecil, maka paket RTPS 2 pun akan tergeser urutan penjadwalannya. Scheduler rtPS akan mendahulukan paket – paket data yang memiliki deadline paling kecil. Pada gambar rtPS, terlihat ada beberapa paket data CID 0xfe13 (NRTPS 1) yang telah dijadwalkan lebih dahulu meskipun prioritas nrtPS lebih rendah daripada UGS dan rtPS. Ini terjadi karena masih ada resources tersisa dari sisa penjadwalan UGS dan rtPS. Dengan demikian, ada beberapa paket NRTPS 1 yang berhasil dijadwalkan. Kemudian, untuk 2 CID lainnya baru dijadwalkan selang
Untuk Best Effort, sama kasusnya seperti nrtPS yang kehabisan resources untuk melakukan penjadwalan. Ketika masih banyak koneksi menggunakan QoS yang lebih tinggi prioritasnya maka Best Effort tidak bisa melakukan penjadwalan. Barulah ketika beberapa koneksi telah selesai dijadwalkan, Best Effort bisa menggunakan resources yang masih banyak tersisa untuk digunakan. Namun demikian, karena adanya parameter Maximum Sustained Traffic Rate, jumlah yang dapat dijadwalkan untuk 1 frame tidak terlalu banyak. 5. KESIMPULAN DAN SARAN Dari penelitian yang telah dilakukan selama ini dapat ditarik kesimpulan sebagai berikut : • Dilakukan penelitian dengan Scheduler sebagai blok kerja berdiri sendiri dengan integrasi Scheduler dan PDU Encoder menjadi satu blok kerja. Terbukti integrasi Scheduler dan PDU Encoder lebih efisien. Dalam sekali loop yang dilakukan, Scheduler dan PDU Encoder telah dijalankan sekaligus dan menghasilkan sebuah output PDU. Proses Fragmentation dan Packing dilakukan pada blok Scheduler untuk perhitungan bandwidth yang lebih efisien. Kedua proses ini meningkatkan efisiensi resources frame. (Bab III, hlm 33) • Frame dengan durasi 2,5 ms, cenderung untuk setiap koneksinya hanya akan memiliki satu PDU. Perhitungan ini dapat dilakukan dengan memasukkan beberapa parameter seperti frame duration, symbol duration, OFDM symbol yang dibutuhkan non-data rate, dan DIUC. (Bab IV) • Telah berhasil dilakukan perancangan Scheduler berdasarkan algoritma Priority Queue. Dengan urutan prioritas dari tinggi ke rendah, UGS, rtPS, nrtPS, dan Best Effort. UGS dengan prioritas tinggi akan dijamin mendapat jatah resources lebih dahulu, sedangkan Best Effort akan sering kehabisan resources karena resources telah digunakan QoS lainnya. • Telah berhasil dilakukan perancangan Scheduler untuk 4 Quality of Service, yaitu: o Scheduler UGS dengan algoritma Fixed Bandwidth menjamin paket – paket data UGS mendapat resources untuk setiap framenya. o Scheduler rtPS dengan algoritma Earliest Deadline First (EDF) menunjukkan bahwa
o
o
paket data dengan deadline paling kecil akan dieksekusi terlebih dahulu. Scheduler nrtPS dengan algoritma Weighted Round Robin menunjukkan bahwa kapasitas bandwidth nrtPS dapat dibagi dengan adil berdasarkan bobotnya masing – masing. Scheduler Best Effort dengan algoritma Round Robin. Pada saat trafik tinggi, paket – paket data Best Effort akan sering kehabisan resources karena telah digunakan QoS lainnya yang memiliki prioritas lebih tinggi.
6. REFERENSI [1] “IEEE Standards for Local and Metropolitant Area Networks Part 16: Air Interface for Fixed Broadband Wireless Access”, 2004. [2] C. Eklund, R. B. Marks, K. L. Stanwood, S. Wang, “IEEE Standards 802.16: A Technical Overview of the WirelessMAN Air Interface for Broadband Wireless Access”, IEEE Communications Magazine, 2002. [3] D. Ghosh, A. Gupta, P. Mohapatra, “Admission Control and Interference-Aware Scheduling in Multi-hop WiMAX Networks” [4] J. Chen, W. Jiao, H. Wang, “A Service Flow Management Strategy for IEEE 802.16 Broadband Wireless Access Systems in TDD Mode” [5] J. G. Andrews, A. Ghosh, R. Muhamed, “Fundamental of WiMAX”, Prentice Hall, 2007. [6] L. Nuaymi, “WiMAX: Technology of Broadband Access”, John Wiley & Sons, 2007.
MAKALAH TUGAS AKHIR PERANCANGAN SOFTWARE SCHEDULER UNTUK MAC LAYER WIMAX MENURUT STANDAR IEEE 802.16-2004
Oleh: Winnu Ayi Satria 132 03 050 Pembimbing : Dr. Arif Sasongko
PROGRAM STUDI TEKNIK ELEKTRO SEKOLAH TEKNIK ELEKTRO DAN INFORMATIKA INSTITUT TEKNOLOGI BANDUNG 2008
