ALGORITMA SCHEDULING WEIGHTED ROUND ROBIN DAN DEFICIT ROUND ROBIN PADA JARINGAN WIMAX
TESIS
Karya tulis sebagai salah satu syarat untuk memperoleh gelar Magister dari Institut Teknologi Bandung
Oleh
IMAN HEDI SANTOSO NIM : 23205053 Program Studi Teknik Elektro
INSTITUT TEKNOLOGI BANDUNG 2007
ALGORITMA SCHEDULING WEIGHTED ROUND ROBIN DAN DEFICIT ROUND ROBIN PADA JARINGAN WIMAX
Oleh : Iman Hedi Santoso NIM : 23205053
Program Studi Teknik Elektro Sekolah Teknik Elektro dan Informatika Institut Teknologi Bandung
Menyetujui Tim Pembimbing
Tanggal : .......................... 2007
Pembimbing I :
Dr. Ir. Hendrawan NIP : 131 660 121
Pembimbing II :
Ir. Nana Rachmana M.Eng. NIP : 131 473 905
ABSTRAK
ALGORITMA SCHEDULING WEIGHTED ROUND ROBIN DAN DEFICIT ROUND ROBIN PADA JARINGAN WIMAX
Oleh:
Iman Hedi Santoso NIM: 23205053 Diantara bermacam-macam sistem akses broadband, sistem fixed broadband wireless access (FBWA) diharapkan akan menjadi sistem yang paling fleksible dimasa depan. Meskipun link fiber optik dan link DSL merupakan teknologi broadband yang sudah eksis di jaringan akses, layanan-layanan berbasis BWA mempunyai keuntungan seperti: pengembangannya cepat, sharing sumberdaya radio yang dinamis, dan berbiaya rendah
Salah satu standar BWA adalah IEEE 802.16, standar ini disponsori oleh masyarakat IEEE/LAN/MAN, yang beroperasi pada range 2-11 GHz dan mendukung akses LOS (Line of Sight) dan NLOS. Dengan adanya standar IEEE 802.16 ini, jaringan internet wireless menjadi mungkin terwujud. Munculnya teknologi ini memunculkan harapan teknologi informasi makin berkembang maju.
Standar IEEE 802.16 telah mendasari sebuah teknologi jaringan akses yang disebut WIMAX. WIMAX menawarkan beberapa keuntungan salah satunya adalah jaminan QoS pada level MAC. Agar dapat menjamin QoS, base station (BS) harus mengalokasikan bandwidth berdasarkan algoritma tertentu. Standar IEEE 802.16 memang sudah menetapkan mekanisme QoS signaling tetapi belum menetapkan algoritma scheduling untuk alokasi bandwidth sehingga terbuka kesempatan bagi berbagai pihak untuk berinovasi.
Karena jaringan WIMAX
merupakan jaringan berkecepatan tinggi, kesederhanaan algoritma scheduling
i
harus menjadi perhatian. Oleh karena itu, dalam penelitian ini dikaji dan dibandingkan kinerja 2 jenis scheduling yang sederhana, yaitu Weighted Round Robin (WRR) dan Deficit Round Robin (DRR). Hasil simulasi menunjukkan, bahwa, algoritma scheduling WRR dapat menjamin QoS requirement untuk setiap kelas layanan pada jaringan WIMAX, sedang DRR kinerjanya sedikit dibawah WRR. Oleh karena itu pada jaringan WIMAX sebaiknya digunakan WRR daripada DRR. Kata Kunci: scheduling, WIMAX, WRR, DRR.
ii
ABSTRACT
SCHEDULING ALGORITHM WEIGHTED ROUND ROBIN AND DEFICIT ROUND ROBIN ON WIMAX NETWORK
Oleh:
Iman Hedi Santoso NIM: 23205053
Among various broadband wireless access, fixed broadband wireless access (FBWA) are expected become most flexible system in the future. In spite of optic fiber and DSL link have became existing broadband technology in access network, BWA-based services have several advantage, ie: rapid development, dynamic resource sharing, and low cost.
One of the BWA standard is IEEE 802.16, this standar is sponsored by IEEE/LAN/MAN society, operate in range 2 – 11 GHz and support LOS (Line of Sight) and NLOS (Non Line of Sight) propagation. By this standar, the implementation of wireless internet become possible. The advent of this technology has raised the expectation in increased rapid progress of information technology.
IEEE 802.16 standard
serves as a basis for an access network, it is called
WIMAX. WIMAX offer several advantage, one of them is guaranteeing QoS in MAC level. In order to guarantee the QoS, base station (BS) has to allocate bandwidth according to certain algorithm. IEEE 802.16 standard has defined QoS signalling mechanism but not yet for the scheduling algorithm. This scheduling algorithm over WIMAX is opened to the public, giving opportunity to everyone creating inovation in this field. WIMAX network is a high speed network, the simplicity of the scheduling algorithm become important to notice. Therefore, in
iii
this
research
two
simple
scheduling,
Weighted
Round
Robin (WRR) and Deficit Round Robin (DRR) will be analyzed and compared. The simulation shows WRR and DRR scheduling can guarantee QoS requirement for every service classes, even though the DRR performance slightly below WRR. Therefore, in WIMAX network, this research suggests using WRR instead of DRR.
Keywords: scheduling, WIMAX, WRR, DRR.
iv
PEDOMAN PENGGUNAAN TESIS Tesis S2 yang tidak dipublikasikan terdaftar dan tersedia di Perpustakaan Institut Teknologi Bandung, dan terbuka untuk umum dengan ketentuan bahwa hak cipta ada pada pengarang dengan mengikuti aturan HaKI yang berlaku di Institut Teknologi Bandung. Referensi kepustakaan
diperkenankan dicatat, tetapi
pengutipan atau peringkasan hanya dapat dilakukan seizin pengarang dan harus disertai dengan kebiasaan ilmiah untuk menyebutkan sumbernya.
Memperbanyak atau menerbitkan sebagian
atau seluruh tesis haruslah seizin
Direktur Program Pascasarjana, Institut Teknologi Bandung.
v
KATA PENGANTAR Pertama-tama penulis ucapkan syukur ke hadlirat Allah SWT karena Dialah yang menjadi sebab yang pertama dan utama atas segala sesuatu yang terjadi didunia ini, dan karena Dialah yang telah memberikan kesehatan, kelancaran, dan hidayah sehingga penulis dapat menyelesaikan karya tulis ini.
Penulis mengucapkan terimakasih atas partisipasi dan bantuan semua pihak, yang telah diberikan kepada penulis baik secara langsung atau pun tidak, dan secara khusus kepada: 1. Dr. Ir. Hendrawan dan Ir. Nana Rachmana M.Eng. yang telah membimbing penulis dalam penyelesaian tesis ini. 2. Dr. Ir. Suhartono Tjondronegoro, selaku wali akademik yang telah membimbing penulis dalam menyelesaikan studi Magister di ITB. 3. Ir. Sigit Haryadi, M.T., yang telah memberi rekomendasinya untuk penulis sehingga penulis dapat diterima di program pasca sarjana ITB, dan juga atas kesediaannya untuk menjadi penguji penulis dalam sidang tesis. 4. Ir. Hardi Nusantara, M.T., Dr. Ir. Ridwan Efendi, dan Ir. Tutun Juhana, M.T., yang telah bersedia menjadi penguji penulis dalam sidang tesis dan telah memberikan masukkan berharga dalam penyelesaian tesis ini. 5. Bapak dan Ibu tercinta yang telah memberikan do’a, motivasi, dan dorongan, dan begitu juga kepada Istriku, Tjutju Supriatin, dan Anakku, Nisrina Nurul Iman, atas motivasi dan penyertaannya di hari-hari yang sempit dalam menyelesaikan tesis ini. 6. Achmad Ubaidillah, Nina Hendrarini, Andri Priambodo, sebagai temanteman di komunitas WIMAX. 7. Junaid, Samy, dan Ibu Liby yang telah mendorong penulis dalam penyelesaikan tesis ini, Sukiswo, Martinus Mujur Rose, dan Sholihin sebagai teman-teman di laboratorium resisdensi S2.
vii
8. Baso Marudani, Wiwit, teman-teman angkatan 2004 dan 2005 lainnya, yang tidak dapat penulis sebutkan satu persatu, atas bantuan dan kerjasamanya. 9. Seluruh sivitas akademika Sekolah Teknik Elektro dan Informatika Institut Teknologi
Bandung,
pengelola
Laboratorium
Telematika
dan
Laboratorium Telekomunikasi Radio dan Gelombang Mikro atas segala bimbingan, pengajaran, dan bantuannya. 10. Ir Arief Permana, M.Sc., sebagai Ketua STTK, yang telah memberikan rekomendasi sehingga penulis dapat diterima pada program pasca sarjana ITB. 11. Departemen Pendidikan dan Kebudayaan atas bantuan Beasiswa Pendidikan Pascasarjana (BPPs) yang telah diterima selama pendidikan program magister ini.
Akhir kata, penulis berharap semoga hasil penelitian ini dapat bermanfaat bagi para pembaca dan buku tesis ini dapat menjadi referensi.
Bandung, Juni 2007 Penulis,
Iman Hedi Santoso
viii
DAFTAR ISI
ABSTRAK ...................................................................................................
i
ABSTRACT .................................................................................................
iii
PEDOMAN PENGGUNAAN TESIS ..........................................................
v
KATA PENGANTAR ..................................................................................
vi
DAFTAR ISI ................................................................................................
viii
DAFTAR GAMBAR ...................................................................................
xi
DAFTAR TABEL ........................................................................................
xiii
BAB I
BAB II
Pendahuluan …………………………………………………..
1
I.1
Latar Belakang ..................................................................
1
I.2
Rumusan Masalah .............................................................
3
I.3
Tujuan Penelitian ..............................................................
4
I.4
Batasan Masalah ................................................................
4
I.5
Metodologi Penelitian .......................................................
5
I.6
Sistematika Laporan ..........................................................
5
Standar WIMAX – IEEE 802.16 ……………………………...
5
II.1
Arsitektur ……………………………………………......
6
II.2
Layer Fisik ……………………………………………...
8
II.2.1
Single Carrier …………………………………
8
II.2.2
Orthogonal Frequency Division Multiple
10
Access (OFDMA) …………………………………...... II.2.3
Teknik Duplexing ……………………………..
12
II.3
Subframe Downlink …………………………………….
13
II.4
Subframe Uplink ……………………………………......
14
II.5 MAC Common Part Sublayer …………………………...
15
II.5.1
MAC Protocol Data Unit ...................................
16
II.5.2
Network Entity dan Inisialisasi Sebuah SS …
17
II.5.3
Keterjaminan QoS pad IEEE 802.16 ................
18
II.5.3.1 Layanan Uplink Scheduling ............
19
viii
II.5.3.2 Mekanisme Bandwidth Request dan
20
Grant ............................................................... BAB III
BAB IV
Algoritma Scheduling ................................................................
22
III.1 Pendahuluan .....................................................................
22
III.2 Persyaratan Sebuah Scheduling .......................................
23
III.3 Klasifikasi Algoritma Scheduling ....................................
25
III.4 Beberapa Jenis Scheduling ..............................................
25
III.4.1 Generalized Processor Sharing (GPS) ………..
26
III.4.2 First In First Out (FIFO) ……………………
28
III.4.3 Priority Queueing (PQ) .....................................
30
III.4.4 Fair Queueing (FQ) ...........................................
30
III.4.5 Weighted Fair Queueing (WFQ) ………….......
33
III.4.6 Weighted Round Robin (WRR) ………………
33
III.4.7 Deficit Round Robin (DRR) ………………….
37
III.4.7.1 Algoritma DRR ...............................
37
III.4.7.2 DRR Pseudocode ............................
38
Modul IEEE 802.16 dan Implementasi Scheduling pada
42
Simulator NS-2 ……………………………………………......
BAB V
IV.1 Pendahuluan ………………………………………….....
42
IV.2 Modul IEEE 802.16 pada NS-2 .......................................
42
IV.3 Implementasi Scheduling pada NS-2 ..............................
44
IV.3.1 Weighted Round Robin ....................................
46
IV.3.2 Deficit Round Robin .........................................
50
IV.4 Contoh Simulasi ..............................................................
53
Simulasi dan Analisis Algoritma Scheduling pada WIMAX ....
75
V.1 Karakteristik Layanan pada Jaringan WIMAX .....
61
V.2 Analisa Kinerja Scheduling ...................................
64
V.2.1 Node Tunggal .........................................
64
V.2.2 Node Banyak ...........................................
66
V.2.2.1 Weighted Round Robin ...........
67
V.2.2.2 Deficit Round Robin ...............
69
ix
BAB VI
Kesimpulan dan Saran ...............................................................
71
VI.1 Kesimpulan ......................................................................
71
VI.2 Saran ................................................................................
71
DAFTAR PUSTAKA ..................................................................................
72
x
DAFTAR TABEL
Tabel V.1
Parameter pada WIMAX
61
Tabel V.2
..................................................................................................
68
Tabel V.3
..................................................................................................
70
xiii
DAFTAR GAMBAR Halaman Gambar I.1
Standar-standar yang dipakai di dunia untuk
1
komunikasi wireless ................................................. Gambar I.2
Struktur PMP ............................................................
2
Gambar I.3
Struktur MESH .........................................................
2
Gambar II.1
Jaringan WIMAX .....................................................
7
Gambar II.2
Protokol Stack 802.16 ..............................................
8
Gambar II.3
Banyak antena pada mode LOS ...............................
9
Gambar II.4.
Modulasi dan coding adaptif ....................................
9
Gambar II.5
Struktur frame OFDMA ...........................................
11
Gambar II.6
Struktur subframe TDD ............................................
12
Gambar II.7
Tiga tipe struktur subframe ......................................
13
Gambar II.8
Struktur subframe downlink .....................................
13
Gambar II.9
Struktur subframe uplinkI .........................................
14
Gambar III.1
Model algoritma scheduling .....................................
23
Gambar III.2
GPS scheduling ........................................................
26
Gambar III.3
Contoh 1, scheduling GPS .......................................
27
Gambar III.4
Contoh 2, scheduling GPS .......................................
27
Gambar III.5
FIFO scheduling .......................................................
29
Gambar III.6
Priority Queueing (PQ) ............................................
30
Gambar III.7
Fair Queueing ...........................................................
31
Gambar III.8
Weighted Fair Queueing ..........................................
33
Gambar III.9
Weighted Round Robin ……………………………
35
Gambar III.10
Contoh untuk WRR ………………………………..
36
Gambar III.11
Deficit Round Robin (DRR) ....................................
38
Gambar III.12
Cara kerja DRR ........................................................
40
Gambar IV.1
Hubungan antara modul WIMAX dengan modul-
43
modul pada NS-2 ...................................................... Gambar IV.2
Diagram kelas pada modul WIMAX .......................
45
Gambar IV.3
Konfigurasi jaringan .................................................
54
Gambar IV.4
Tampilan NAM pada NS-2 ......................................
59
Gambar V.1
Tampilan grafis pada simulator NS-2 ......................
60
Gambar V.2
Perbandingan rata-rata throughput ...........................
62
Gambar V.3
Delay transmisi UGS, ertPS, dan rtPS .....................
62
Gambar V.4
Perbandingan delay antrian rata-rata ........................
63
Gambar V.5
Perbandingan standar deviasi delay antrian .............
63
Gambar V.6
Satu BS melayani satu SS ........................................
65
Gambar V.7
Rata-rata throughput pada WRR scheduling ………
65
Gambar V.8
Rata-rata throughput pada DRR scheduling ……….
66
Gambar V.9
Konfigurasi jaringan WIMAX dengan banyak SS ...
67
Gambar V.10
WRR dengan skema pembobotan: 30-30-30-5-5 .....
67
Gambar V.11
WRR dengan skema pembobotan: 20-20-50-5-5 .....
68
Gambar V.12
WRR dengan skema pembobotan: 30-20-40-5-5 .....
68
Gambar V.13
DRR dengan skema quantum: 250-250-980 ............
69
Gambar V.14
DRR dengan skema quantum: 500-250-980 ............
69
Gambar V.15
DRR dengan skema quantum: 980-980-980 ............
70
