BAB II LANDASAN TEORI Pada bab BAB II yang berisi berbagai landasan teori ini, akan dibahas mengenai IEEE Standard 802.16/Wimax secara umum, MAC Layer pada Wimax, berbagai algoritma penjadwalan pada MAC layer Wimax, dan beberapa metrik QoS untuk menilai performansi algoritma penjadwalan. Landasan teori ini dimaksudkan untuk memberikan pemahaman yang lebih mendalam mengenai cara kerja algoritma penjadwalan yang selanjutnya akan dianalisis dan dirancang implementasinya pada bab III.
2.1 IEEE 802.16 Broadband Wireless Access / WIMAX Jaringan komputer telah menjadi bagian penting dari komunikasi manusia di seluruh dunia. Sejak dekade akhir dari abad 20, wire internet network telah dipasang di penjuru dunia yang memungkinkan komunikasi luas lintas negara. Kini pada dekade awal abad 21, wireless network mulai dikembangkan dan dipakai di berbagai negara. Pengembangan wireless communication network dimulai sejak ditemukannya persamaan Maxwell yang menunjukkan bahwa transmisi data dapat terjadi tanpa memerlukan kabel. Sinyal yang dipancarakan di udara dapat menjadi media untuk mengantarkan informasi, bahkan menjadi media yang lebih murah daripada media kabel [NYL07].
Wireless communication network awalnya hanya dipakai untuk komunikasi suara. Selanjutnya wireless communication network dikembangkan untuk komunikasi data, tidak hanya berupa suara. Berdasarkan besarnya daerah jangkauan, wireless network dapat dibedakan menjadi 4 jenis [NYL07]. Gambar II-1 menunjukkan ilustrasi dari klasifikasi wireless network berdasarkan besarnya daerah jangkauan. Keempat jenis wireless network tersebut adalah : 1. Wireless Personal Area Network Wireless network ini memiliki jangkauan kurang dari 10 meter. Biasanya dipakai untuk koneksi peralatan bagi satu orang. Contoh : Bluetooth, UWB, Zigbee
II-1
II-2 2. Wireless Local Area Network Wireless network ini memiliki jangkauan sekitar 100 meter. Biasanya digunakan dalam area yang tidak terlalu luas, seperti rumah, satu lantai dalam gedung, dan restoran. Contoh : WiFi (Wireless Fidelity). 3. Wireless Metropilitan Area Network Wireless network ini memiliki jangkauan beberapa kilometer. Biasanya digunakan untuk koneksi sebuah kampus dan sebuah kota kecil. Contoh : Fixed Wimax. 4. Wide Are Network Wireless network ini memiliki jangkauan sangat luas, yaitu satu planet ini. Contoh : 3G dan Mobile Wimax.
Gambar II-1 Klasifikasi wireless network berdasarkan luas dearah jangkauan
IEEE Std. 802.16 Broadband Wireless Access (BWA) adalah contoh standar wireless network yang termasuk pada kategori Wireless Metropolitan Network dan Wide Area Network. BWA lahir disebabkan oleh kebutuhan komunikasi data tanpa kabel dengan kecepatan tinggi dan mencakup area yang luas. Worldwide Interoperability for Microwave Access (Wimax) merupakan penerapan dari IEEE Std 802.16 tersebut. Wimax merupakan teknologi jaringan berbasis cell yang bertujuan untuk memberikan akses last mile wireless broadband dengan biaya yang murah [WIX07]. Akses last mile adalah akses yang memberikan konektivitas antara service provider kepada pengguna.
II-3 2.1.1 Layer-layer Wimax Dibandingkan dengan Open System Interconnection (OSI) network reference sevenlayer model, IEEE Std. 802.16 hanya mencakup dua layer tebawah OSI. Pada standar 802, Data Link layer dibagi atas 2 sublayer, yaitu LLC (Logical Link Control) dan MAC (Medium Access Control) Gambar II-2 menunjukkan tujuh OSI layer dan dua sublayer dari data link layer.
Gambar II-2 OSI Network Reference Seven-layer Model
Dua network layer yang didefinisikan pada IEEE Std 802.16 adalah physical layer dan MAC layer. MAC layer dibagi atas 3 sublayer, yaitu Convergen Sublayer, Common part Sublayer, dan Security Sublayer [IES04]. Suatu paket data yang dikirim dari suatu layer pada Wimax disebut Protocol Data Unit (PDU), sedangkan suatu paket data yang diterima dari suatu layer Wimax disebut Service Data Unit (SDU). Contohnya, paket data dikirim oleh MAC layer sebagai MAC PDU (MPDU) dan diterima oleh physical layer sebagai Physical SDU (PSDU).
Physical layer merupakan layer yang bertanggung jawab untuk menciptakan koneksi antara dua buah perangkat pada jaringan (the peer entities). MAC layer merupakan layer yang bertanggung jawab untuk menstabilkan dan mengatur koneksi, termasuk di dalamnya permasalahan multiple access dan penjadwalan. Perbatasan antar layer dihubungkan oleh interface SAP. SAP adalah point pada protocol stack dimana servis dari lower layer telah dapat disediakan untuk layer di atasnya. Gambar II-3 menunjukkan dua layer dan 3 sublayer dari Wimax.
II-4
Gambar II-3 Protocol Layer of IEEE Std 802.16
Pada physical layer didefinisikan tipe sinyal yang digunakan, jenis modulasi dan demodulasi, serta berbagai karakteristik fisik lainnya. Wimax physical layer berada pada range frequency 2-11 GHz. Frekuensi ini memungkinkan transmisi yang bersifat Non Line of Sight (NLOS). Terdapat dua jenis duplexing yang didukung oleh physical layer, yaitu Time Division Duplexing (TDD) dan Frequency Division Duplexing (FDD).
MAC layer, merupakan interface antara physical layer dengan upper data link layer. Protokol pada Wimax MAC layer bersifat connection oriented. Awalnya, IEEE Std 802.16 MAC layer didesain hanya untuk arsitektur Point to Multipoint (PMP). Melalui amandement 802.16a dan 802.16d, Wimax MAC layer juga mendukung arsitektur mesh network. Mengenai MAC layer dan ketiga sublayernya akan dibahas pada subbab II.2. 2.1.2 Arsitektur Wimax Sesuai dengan IEEE Std. 802.16, arsitektur dasar wimax terdiri atas sebuah Base station (BS) dan satu atau lebih Subcriber station (SS). BS merupakan perangkat jaringan yang bertanggung jawab menyediakan konekstivitas, manajemen, dan kontrol antar SS. SS merupakan perangkat jaringan yang bertanggung jawab menyediakan konektivitas antara BS dengan subscriber equipment. Baik BS maupun SS merupakan perangkat yang tidak berpindah-pindah (fixed) sedangkan subscriber equipment dapat berupa perangkat yang bergerak (mobile station).
II-5 Terdapat dua topologi jaringan yang dapat dibangun pada Wimax, yaitu Point to Multipoint (PMP) dan Mesh network. Perbedaan kedua topologi ini terdapat pada cara koneksi antara SS dengan SS lainnya. Pada topologi mesh network, SS dapat terhubung langsung dengan SS lainnya. Pada PMP, tiap-tiap SS hanya dapat berhubungan dengan SS lain melalui BS. Pembahasan tugas akhir ini dibatasi pada topologi PMP.
Pada topologi PMP, BS menjadi pusat komunikasi data antar SS. Transmisi data antara BS dan SS terjadi pada dua kanal yang independen, yaitu uplink dan downlink. Uplink adalah kanal transportasi data dari SS ke BS. Downlink adalah kanal transportasi data dari BS ke SS. Downlink merupakan kanal broadcast. Semua SS dapat mendengarkan data yang dikirim oleh BS, namun hanya data yang ditujukan untuk dirinya saja yang akan ditangkap dan diproses oleh sebuah SS. 2.1.3 QoS Classes Salah satu keunggulan dari Wimax adalah kemampuan untuk memberikan garansi Quality of service (QoS). IEEE Std. 802.16 mendefinisikan bahwa MAC layer dapat memberikan garansi QoS yang berbeda-beda untuk beberapa jenis aplikasi. Perbedaan jenis garansi QoS ini disebut dengan kelas QoS. Tiap kelas QoS ini dilengkapi dengan QoS service flow parameter yang mengatur behavior dari kelas tersebut. Terdapat 5 jenis kelas QoS menurut IEEE Std. 802.16e [IES05], yaitu : 1. Unsolicited Grant Service (UGS) Kelas UGS didesain untuk melayani real time data service dengan ukuran paket yang sama tiap periode interval tertentu. QoS service flow parameter yang digunakan pada kelas UGS adalah Maximum Sustained Traffic Rate, Maximum latency, Tolerated Jitter, dan Request/Trasmission Policy. Contoh aplikasi yang menggunakan kelas ini adalah Voice Over Internet Protocol (VOIP) tanpa silence suppression. Gambar II-4 menunjukkan ilustrasi pengiriman paket UGS.
II-6
Gambar II-4 Paket data kelas UGS
2. Real-time Polling Service (rtPS) Kelas rtPS didesain untuk melayani real time data service dengan ukuran paket bebas namun tetap dalam periode interval tertentu. QoS service flow parameter yang digunakan pada kelas rtPS adalah Maximum Sustained Traffic Rate, Maximum latency, Request/Trasmission Policy, dan Minimum Reserved Traffic Rate. Contoh aplikasi yang menggunakan kelas ini adalah transmisi video dalam format Moving Pictures Experts Group (MPEG). Gambar II-5 menunjukkan ilustrasi pengiriman paket rtPS.
Gambar II-5 Paket data kelas rtPS
3. Non Real-time Polling Service (nrtPS) Kelas nrtPS didesain untuk melayani non real time data service dan delay tolerant service yang membutuhkan minimum data rate tertentu. Pada kelas ini tidak terdapat periode interval tertentu. QoS service flow parameter yang digunakan pada kelas nrtPS adalah Maximum Sustained Traffic Rate, Request/Trasmission Policy, Minimum Reserved Traffic Rate, dan Traffic Priority. Contoh aplikasi yang menggunakan kelas ini adalah File Transfer Protocol (FTP) transmission. Gambar II-6 menunjukkan ilustrasi pengiriman paket nrtPS.
II-7
Gambar II-6 Paket data kelas nrtPS
4. Extended Real-time Polling Service (ertPS) Kelas ertPS merupakan kelas yang dibuat berdasarkan efisiensi dari kelas UGS dan rtPS. Unicast grant diberikan ole Base station tanpa diminta seperti halnya kelas UGS. Besar paket yang dikirim dapat beragam (tidak fixed size) seperti pada kelas rtPS. QoS service flow parameter yang digunakan pada kelas ertPS adalah Maximum Sustained Traffic Rate, Maximum latency, Request/Trasmission Policy, dan Minimum Reserved Traffic Rate. Contoh aplikasi yang menggunakan kelas ini adalah Voice Over IP dengan silence suppression.
5. Best Effort (BE) Kelas BE didesain untuk melayani data streaming service yang tidak memerlukan minimum data service granted. Kelas ini dilayani dengan data rate terbaik yang dapat diberikan. QoS service flow parameter yang digunakan pada kelas BE adalah Maximum Sustained Traffic Rate, Request/Trasmission Policy, dan Traffic Priority. Contoh aplikasi yang menggunakan kelas ini adalah telnet dan http transmission. Gambar II-7 menunjukkan ilustrasi pengiriman paket BE.
Gambar II-7 Paket data kelas BE
II-8
2.2 Wimax MAC Layer Sesuai dengan standar 802, MAC layer merupakan sublayer kedua dari data link layer. MAC layer pada Wimax bersifat connection oriented. Saat telah terkoneksi dengan sebuah BS, SS akan membuat satu atau lebih koneksi ke BS sesuai dengan jenis data yang ingin ditransmisikan. Setiap koneksi memiliki penanda unik 16-bit yang disebu Connection Indentifier (CID). Pemetaan data ke jenis kelas QoS yang sesuai dan pembuatan koneksi dilakukan pada MAC layer. MAC layer pada wimax dibagi atas tiga sublayer, yaitu Convergen Sublayer (CS), Common part Sublayer (CPS), dan Security Sublayer. 2.2.1 Convergen Sublayer Convergen Sublayer (CS) merupakan sublayer paling atas dari MAC layer. CS bersifat connection oriented. Pada IEEE Std 802.16 tahun 2004, didefinisikan dua spesifikasi CS, yaitu Asynchronous Transfer Mode (ATM) CS dan Packet CS. ATM CS didesain untuk dapat menerima paket ATM cells dari ATM layer di atasnya. Packet CS disesain untuk dapat menerima paket data dari layer atas yang menggunakan protokol berbasis paket. Contoh protokol yang berbasis paket adalah Internet Protocol (IP) baik versi 4 maupun versi 6, Point to Point Protocol (PPP), dan IEEE Std. 802.3 (Ethernet).
Fungsi – fungsi yang dijalankan oleh CS adalah sebagai berikut [NYL07] : 1. Menerima PDU dari layer di atasnya (baik ATM network maupun IP based network) 2. Mengklasifikasikan dan memetakan MAC Service Data Unit (MSDU) ke Connection Identifiiter (CID). Fungsi ini merupakan fungsi dasar dari manajemen QoS pada Wimax. 3. Memroses (jika dibutuhkan) higher-layer PDU yang diterima oleh CS. 4. Mengirimkan CS PDU ke MAC SAP 5. Fungsi tambahan dari CS adalah Payload Header Suppression (PHS), yaitu proses untuk menghilangkan bagian-bagian payload header yang berulang.
Terdapat duah buah konsep dasar dalam mengklasifikasikan dan memetakan paket di CS, yaitu :
II-9 1. Connection Connection yang dimaksud disini adalah connection pada MAC level, antar BS ke SS atau sebaliknya. Connection bersifat satu arah dan bertujuan untuk mengirimkan trafik service flow. Sebuah connection hanya untuk sebuah tipe servis. Connection diidentifikasikan dengan CID berupa 16 bit data. 2. Service flow Service flow adalah MAC transport service yang menyediakan transportasi satu arah untuk paket-paket uplink maupun downlink. Service flow diidentifikasikan dengan Service flow Identifier (SFID) berupa 32 bit data
Sebuah SFID pada suatu waktu dapat berelasi dengan nol atau satu buah CID. Sebuah CID dapat berelasi dengan satu buah SFID. Gambar II-8 memperlihatkan ilustrasi hubungan antara connection dan service flow.
Gambar II-8 Keterhubungan antara service flow dan connection
Klasifikasi dan pemetaan dilakukan pada uplink dan downlink. Pada transmisi downlink, klasifikasi dilakukan di BS, sedangkan pada transmisi uplink, klasifikasi dilakukan di SS. Setelah dilakukan klasifikasi dan pemetaan oleh CS, selanjutnya adalah tugas CPS untuk melakukan establishment dan maintenance connection. Gambar II-9 menunjukkan ilustrasi alur klasifikasi pada BS ke SS atau sebaliknya.
II-10
Gambar II-9 Klasifikasi dan pemetaan connection pada CS
2.2.2 Common Part Sublayer Common Part Sublayer (CPS) merupakan sublayer kedua pada MAC layer Wimax. Sublayer ini bertanggung jawab atas 3 hal berikut [NYL07]: 1. Pengalokasian bandwidth 2. Connection establishment 3. Pengaturan koneksi antara dua stasion
CPS menerima data dari CS melalu MAC SAP untuk diproses lebih lanjut. CPS menjalankan berbagai fungsi, diantaranya adalah frame construction, multiple access, scheduling, radio resource management, dan QoS management. Algoritma penjadwalan diterapkan pada fungsi scheduling di sublayer ini.
Penjadwalan merupakan bagian dari tugas mengatur pengalokasian bandwidth yang merupakan tanggung jawab CPS. Penjadwalan merupakan mekanisme menangani paket data agar terjadi distribusi resource yang adil bagi semua pengguna Wimax. Penjadwalan erat kaitannya dengan 5 kelas QoS yang didefinisikan sebelumnya. Tujuan dilakukannya penjadwalan adalah agar setiap pengguna sebisa mungkin dapat memperoleh layanan servis yang sesuai dengan aplikasi yang dijalankan.
Pada topologi PMP, BS bertugas mengatur penjadwalan baik uplink maupun downlink. BS scheduller mengalokasikan sejumlah bandwidth yang dibutuhkan oleh tiap-tiap aplikasi yang meminta alokasi bandwidth. Pemberian alokasi bandwidth ini
II-11 dilakukan perCID. Seperti dijelaskan
sebelumnya bahwa setiap koneksi berelasi
dengan sebuah service flow dan setiap service flow memiliki QoS parameter yang berisi jenis kelas QoS yang dipakai. Gambar II-10 menunjukkan ilustrasi mekanisme penjadwalan pada sebuah station.
Gambar II-10 Mekanisme penjadwalan pada sebuah station
Modul scheduler pada BS bertugas untuk menentukan burst profile dan periode transmisi dari tiap-tiap connection. Pilihan parameter coding dan modulation ditentukan oleh BS dengan memperhatikan kualitas link dan network load yang ada. Untuk itu, BS scheduler harus memonitor nilai CINR dari berbagai link untuk kemudian menentukan kebutuhan bandwidth untuk tiap station sesuai dengan kelas servis untuk jenis connection tersebut. Gambar II-11 menunjukkan faktor-faktor yang mempengaruhi pengambilan keputusan oleh BS.
Gambar II-11 Faktor-faktor yang mempengaruhi penjadwalan pada BS
II-12 Pada
SS
juga
terdapat
modul
scheduler.
SS
scheduler
bertugas
untuk
mengklasifikasikan semua paket yang masuk ke dalam SS connection yang berbedabeda. IEEE Std. 802.16 tidak mendefinisikan algoritma penjadwalan yang harus digunakan. Hal ini menjadikan desain penjadwalan yang efisien merupakan tantangan bagi peneliti dan pengembang Wimax. Beberapa algoritma penjadwalan akan dibahas pada bab 2.3. 2.2.3 Security Sublayer Seluruh wireless system menggunakan radio channel sebagai media transmisi data. Radio channel merupakan open channel dimana paket-paket data yang lewat dapat ditangkap dan dibaca oleh siapa saja. Untuk itu, aspek security pada tiap wireless system sangat penting. Pada Wimax, security menjadi satu sublayer bagian dari MAC layer. Security sublayer pada Wimax bertugas untuk menyediakan berbagai fungsi, yaitu authentification, security key exchange, dan integrity control [IES04].
Terdapat dua topik penting dalam data network security, yaitu enkripsi data dan autentifikasi. IEEE Std. 802.16, mendefinikasikan bahwa enkripsi dilakukan pada komunikasi antara BS dan SS, begitu juga sebaliknya.
Protokol enkapsulasi
digunakan untuk mengenkripsi paket data yang melintas pada jaringan Wimax. Protokol ini menyediakan seperangkat supported cryptographic suites seperti pairings of data encryption dan algoritma autentifikasi. Aturan-aturan untuk mengaplikasikan algoritma pada payload MAC PDU juga telah didefinisikan pada standar. Untuk protokol autentifikasi, digunakan Privacy Key Management (PKM) protocol. Protokol ini menyediakan prosedur yang aman untuk pertukaran key antara BS dan SS.
2.3 Algoritma Penjadwalan pada MAC Layer Algoritma penjadwalan pada BS scheduler tidak ditetapkan pada IEEE Std. 802.16. Hal ini memungkinkan para peneliti untuk mengembangkan algoritma penjadwalan yang optimal untuk diterapkan pada MAC layer Wimax. Beberapa algoritma penjadwalan yang banyak dibahas pada berbagai paper adalah Weighted Round robin, Deficit Round robin, Weighted Fair queueing, dan Early Deadline First [DHP07]. Algoritma-algoritma tersebut dipilih untuk dibahas pada tugas akhir ini karena keempat algoritma tersebut merupakan algoritma dasar (basic algorithm). Sebagian algoritma yang diusulkan untuk dipakai pada penjadwalan Wimax merupakan
II-13 algoritma campuran (hybrid algorithm), misalnya campuran antara Weighted Round Robin dengan Early Deadline First. Dengan memahami algoritma dasar, maka relatif mudah untuk memahami algortma campuran. 2.3.1 Weighted Round Robin Algoritma Round robin merupakan algoritma yang banyak diterapkan pada berbagai sistem antrian. Pada algoritma round robin, tiap-tiap task yang ada pada antrian dilayani dengan quantum waktu tertentu. Jika task tidak berhasil diselesaikan pada satu quantum waktu, maka task akan ditempatkan kembali pada ujung antrian. Algoritma ini menjamin tidak adanya task yang harus menunggu selamanya (wait forever) untuk dapat dilayani [TAS02]. Gambar II-12 menunjukkan ilustrasi penerapan algoritma round robin pada suatu antrian.
Gambar II-12 Algoritma Round robin
Pada round robin, tidak ada prioritas paket dan semua paket diperlakukan sama. Seringkali pada suatu penjadwalan, ada paket yang memiliki prioritas lebih tinggi daripada paket lainnya. Untuk itu dibuat pengembangan dari algoritma round robin, yaitu algoritma Weighted Round Robin (WRR). Algoritma ini memungkinkan penerapan prioritas yang berbeda-beda pada tiap-tiap paket. WRR bersifat workconserving, artinya algoritma ini tidak membiarkan line berada pada kondisi idle. Prinsip work conserving adalah bahwa line harus selalu dalam keadaan sibuk apabila masih ada paket dalam antrian.
Jika pada Round Robin semua paket dikunjungi satu kali untuk tiap cycle, pada WRR paket yang memiliki weight lebih besar akan dikunjungi lebih dari satu kali. Gambar II-13 menunjukkan ilustrasi cycle Round Robin. Terdapat dua pendekatan dalam
II-14 memberikan alokasi lebih untuk paket yang memiliki weight lebih besar. Pendekatan pertama adalah dengan memberikan quantum lebih untuk paket dengan weight besar pada satu cycle. Pendekatan kedua adalah dengan membagi jenis cycle menjadi dua cycle. Pada cycle pertama, semua paket akan diberi quantum waktu yang sama. Pada cycle kedua, hanya paket yang membutuhkan lebih dari satu quantum waktu yang akan dikunjungi [KTM01]. Gambar II-14 dan II-15 menunjukkan ilustrasi cycle WRR pendekatan 1 dan WRR pendekatan 2.
Gambar II-13 Round robin Cycle
Gambar II-14 Weighted Round robin Cycle
Gambar II-15 Weighted Round robin Cycle
(Pendekatan 1)
(Pendekatan 2)
Pada algoritma WRR, tiap paket yang datang diberi parameter bobot (weight). Scheduler memilih paket mana yang akan dikirim selanjutnya dengan memperhatikan parameter weight tersebut. Pada Wimax, nilai weight didapat dari salah satu QoS service flow parameter, yaitu Minimum Reserved Traffic Rate (MRTR) dengan mengikuti rumus berikut [DHP07]:
Keterangan : Wi = weight dari paket yg ke i n = jumlah paket yang masuk
II-15 2.3.2 Deficit Round Robin Algoritma Deficit Round Robin atau juga disebut Deficit Weighted Round Robin merupakan pengembangan dari algoritma WRR. Algoritma ini diusulkan oleh Shreedhar dan George Varghese pada tahun 1995. Pada DRR, tiap antrian diberi sebuah parameter counter yang disebut deficit counter. Deficit counter menyimpan sisa quantum waktu yang tidak dipakai oleh suatu paket [SMV96].
Saat inisialisasi, defisit counter diisi dengan quantum waktu. Saat paket dari antrian tersebut dikirim, defisit counter diisi dengan nilai deficit counter sebelumnya ditambah dengan sisa quantum yang tidak terpakai. Suatu paket dari suatu antrian akan dikirim apabila besarnya paket lebih kecil daripada deficit counter dari antrian tersebut. Apabila ukuran paket lebih besar daripada deficit counter, maka paket tidak dikirim dan nilai deficit counter ditambah dengan satu quantum waktu.
Gambar II-16 Ilustrasi algoritma Deficit Round robin (1)
II-16
Gambar II-17 Ilustrasi algoritma Deficit Round robin (2)
Gambar II-16 menunjukkan saat paket dari antrian #1 akan dilayani, nilai deficit counter antrian #1 diisi dengan quantum waktu. Karena ukuran paket pertama dari antrian #1 kurang dari deficit counter, maka paket tersebut dikirim. Gambar II-17 menunjukkan kondisi ketika paket pertama dari antrian #1 telah dikirim. Pointer dari antrian akan dipindahkan ke antrian #2 dan deficit counter antrian #1 akan dikurangi dengan besarnya paket yang telah dikirim. Algoritma DRR efektif untuk diterapkan pada datagram network dengan jumlah paket yang sangat beragam.
2.3.3 Weighted Fair Queueing Algoritma Weighted Fair Queueing (WFQ) merupakan pendekatan berbasis paket dari algoritma Generalized Packet Scheduling (GPS). GPS termasuk pada jenis algoritma ideal yang tidak dapat diimplementasikan. GPS mengasumsikan bahwa tiap paket dapat dipecah ke dalam bi-bit data dan tiap bit dapat dijadwalkan untuk dikirim secara terpisah. Hal ini tidak mungkin diimplementasikan karena sebuah paket harus dikirimkan bersamaan sebagai sebuah entitas. Packet GPS atau disebut juga WFQ merupakan implementasi praktikal dari GPS [PKG93].
Sama seperti pada WRR, tiap paket juga diberi parameter penanda yang dijadikan acuan dalam memilih paket untuk ditransmisikan. Pada WFQ, parameter tersebut adalah finish time. Finish time terdiri atas weight, ukuran paket, dan kapasitas kanal
II-17 yang tersedia. WFQ lebih lengkap daripada WRR karena mempertimbangkan aspek kapasitas kanal dan ukuran paket [DHP07]. Penghitungan weight pada WFQ sama dengan penghitungan weight pada algoritma WRR. Tiap paket yg masuk akan diberi nilai finish time dengan rumus berikut ini
Keterangan = Finish time untuk paket ke k dari SS i = Start time untuk paket ke k dari SS i = Panjang paket ke k dari SS ke i = Reserved rate dari SS i dimana Wi = Weight dari SS i C = Kapasitas kanal
Finish number bersifat incremental, artinya finish time suatu paket tidak akan lebih kecil daripada finish time paket yang datang sebelumnya. Start time adalah waktu dimana paket mulai akan dikirim. Start time dipilih dari nilai maksimal antara finish time dan virtual time.
Keterangan : = Start time untuk paket ke k dari SS i = Finish time untuk paket ke k-1 dari SS i = Virtual time untuk paket ke k dari SS i = Waktu kedatangan paket k dari SS i
Kompleksitas algoritma WFQ terletak pada penghitungan virtual time dan pemilihan paket pada antrian mana yang akan dikirim selanjutnya. Untuk menghitung virtual time digunakan rumus berikut :
II-18
dimana
dan j = 2,3,...
Keterangan = Jumlah SS yang berada pada antrian V(tj) = Virtual time untuk waktu tj
2.3.4 Early Deadline First Algoritma Early Deadline First (EDF) merupakan algoritma yang bersifat workconserving [DHP07]. Pada algoritma ini, tiap paket data ditambah dengan parameter deadline. Deadline didapat dari waktu kedatangan paket ditambah dengan maximum latency. Nilai deadline hanya dapat diisikan pada paket yang memiliki QoS service flow parameter maximum latency, yaitu UGS, rtPS, dan ertPS. Untuk paket dari kelas QoS yang tidak memiliki parameter maximum latency, seperti nrtPS dan BE, deadline diisi dengan nilai tak hingga.
Paket yang pertama dipilih adalah paket dengan deadline terkecil. EDF cocok diterapkan untuk transmisi paket-paket real-time yang memiliki deadline sangat singkat. Namun paket-paket yang memiliki deadline tak hingga mungkin tidak pernah dilayani (starving).
2.4 Metrik QoS Dalam menilai kualitas suatu algoritma, perlu ditetapkan parameter pengukuran. Parameter pengukuran ini digunakan agar analisis efektivitas suatu algoritma dapat dilakukan dari sudut pandang yang sama. Dalam berbagai penelitian, telah dipakai beberapa parameter pengujian yang disebut metrik QoS. Berikut beberapa metrik QoS yang dikumpulkan dari beberapa paper referensi [DHP07] [CYV00] [CCA07] : 1. Average Throughput Average throughput adalah jumlah rata-rata data yang dipilih untuk dikirimkan pada suatu jangka waktu tertentu.
II-19 2. Average Queueing Delay Average Queueing Delay adalah jumlah rata-rata waktu antara sampainya paket ke antrian sampai paket meninggalkan antrian. 3. Packet Loss Packet Loss adalah perbandingan paket yang didrop dari antrian dibandingkan dengan seluruh paket yang ada pada antrian. 4. Frame Utilization / Gross Subframe Utilization Frame utilization adalah banyaknya simbol yang terpakai dibandingkan dengan jumlah seluru simbol yang ada pada satu frame 5. Fairness Index Fairness Index adalah perbandingan traffic dalam suatu kelas (intraclass fairness) dengan traffic keseluruhan kelas (interclass fairness). 6. Jumlah SS yang dilayani pada satu frame 7. Mechanism for wireless link variability Metrik ini merupakan penilaian apakah suatu algoritma penjadwalan memperhatikan keadaan link dalam menjadwalkan pengiriman paket. 8. Pre-allocated resource for compensation Metrik ini hanya dapat diukur apabila metrik ke-7 (mechanism for wireless link variability) dipenuhi. Pre-allocated resource for compensation menilai apakah suatu algoritma penjadwalan memberi kompensasi bandwidth kepada node yang gagal mendapat bandwidth akibat error link.
Dari ketiga paper yang dijadikan referensi, terdapat beberapa kesamaan metrik yang digunakan. Paper pertama [DHP07] menggunakan lima metrik QoS, yaitu average throughput, average queueing delay, packet loss, frame utilization, dan fairness index. Paper kedua [CYV00] menggunakan lima metrik, yaitu delay, throughput, mechanism for wireless link variability, fairness, dan pre-allocated resource for compensation. Paper ketiga [CCA07] menggunakan empat metrik, yaitu frame utilization, throughput, delay, dan jumlah SS yang dilayani dalam satu frame. Metrik-metrik yang diimplementasikan dan dipakai dalam membangun kerangka uji algoritma penjadwalan akan dibahas pada subbab III.1
II-20
2.5 Network Simulator 2 Network simulator 2 (NS2) adalah sebuah program yang mensimulasikan proses dan kejadian pada sebuah jaringan. NS2 menyediakan simulasi untuk berbagai network protocol seperti TCP dan UDP, traffic source behaviour seperti FTP dan web, mekanisme manajemen router queue seperti Drop Tail dan RED, algoritma routing seperti algoritma Djikstra, dan lain sebagainya [WIN08]. Proyek NS dimulai pada tahun 1989 sebagai varian dari REAL network simulator. Saat ini NS2 dikembangkan melalui kolaborasi antara beberapa kelompok peneliti dan institusi, diantaranya adalah SAMAN, CONSER, dan ICIR. Versi terakhir nari NS2 adalah versi 2.32.
NS2 bersifat object-oriented dan discrete driven. NS2 dibangun menggunakan bahasa C++ dengan antarmuka simulasi dibangun melalui OTcl. OTcl merupakan object oriented extension dari Tool Command Language (TCL). Pengguna NS2 mendeskripsikan topologi jaringan yang ingin disimulasikan dengan menggunakan OTcl script . Gambar II-18 menunjukan keterhubungan antara bahasa C++ dengan OTcl script dalam NS2 [TNS08].
Gambar II-18 Keterhubungan antara C++ dan OTcl pada NS2
Script OTcl yang dituliskan akan diterjemahkan oleh Tcl interpreter dan kemudian disimulasikan oleh main program NS2. Hasil simulasi dapat berupa kumpulan data atau berupa masukan bagi perangkat simulasi grafik yang disebut Network Animator (NAM). NAM memiliki antarmuka grafik yang mirip dengan CD player, yaitu memiliki tombol play, pause, rewind, fast forward, dan sebagainya. Gambar II-19 menunjukkan ilustrasi proses kerja NS2 dilihat dari sudut pandang pengguna.
II-21
Gambar II-19 Proses Kerja NS2
2.6 Modul 802.16 pada NS2 NS2 merupakan simulator jaringan yang dapat mensimulasikan berbagai standar jaringan.Untuk dapat mensimulasikan Wimax, telah dikembangkan modul 802.16 oleh Network and Distribution Laboratory, Chang Gung University, Taiwan. Modul ini dipilih karena telah mengimplementasikan algoritma penjadwalan. Rilis terbaru modul 802.16 ini adalah versi 2.03. Topologi Wimax yang diimplementasikan pada modul ini adalah topologi Point to Multipoint (PMP) dan skema physical layer yang dipakai adalah Orthogonal Frequency Division Mulitple Access (OFDMA) [WMN08]. Pengembangan modul ini dilakukan dengan model Unified Modeling Language (UML).
Modul 802.16 pada NS2 ini telah dapat mengimplementaskan ketiga sublayer dari MAC layer Wimax. Modul ini mengimplementasikan berbagai fungsi dari MAC layer, seperti ranging, MAC management scheduler, IP-SFID mapping, dan SFIDTCID mapping. Gambar III-1 menunjukkan arsitektur MAC layer dari modul 802.16 pada NS2 [JCT06].
II-22
Gambar II-20 Arsitektur MAC layer pada modul 802.16 NS2
Pada modul 802.16 dikembangkan sebuah kelas berdasarkan IEEE Std. 802.16 yang dinamakan Mac802_16. Keseluruhan modul didesain dengan object oriented programming menggunakan bahasa C++. Keterkaitan antara modul 802.16 dengan modul lain pada NS2 adalah berdasarkan original network component stack dari NS2. Gambar III-2 menunjukkan bagan keterkaitan modul 802.16 dengan modul-modul NS2 lainnya.
II-23
Gambar II-21 Keterkaitan modul 802.16 dengan NS2
Traffic Generating Agent (TGA) merupakan generator pada level aplikasi yang membangkitkan traffic VOIP, MPEG, HTTP, FTP, dan sebagainya. Traffic ini kemudian diklasifikasikan ke lima kelas QoS, yaitu UGS, rtPS, nrtPS, ertPS, dan BE. Selanjutnya paket-paket tersebut dimasukkan pada priority queue yang tepat menggunakan mekanisme SFID-CID pada CS Sublayer. Setelah Wimax MAC modul pada SS menerima paket-paket tersebut dari antrian, MAC management akan mulai melakukan ranging untuk memasuki Wimax network atau untuk mentransfer paket sesuai dengan penjadwalan pengiriman paket [JCT06].
Masalah penjadwalan ditangani oleh fungsi Scheduler(). Fungsi ini bertugas untuk memilih MSDU yang akan dikirimkan dari antrian disesuaikan dengan bandwidth yang tersedia. Algoritma penjadwalan yang diterapkan pada fungsi ini adalah algoritma Weighted Round robin (WRR).
2.7 Algoritma Penjadwalan pada Modul 802.16 di NS2 Pada tugas akhir ini, digunakan adalah modul 802.16 yang dibuat oleh Network and Distribution Laboratory, Chang Gung University, Taiwan. Pada modul ini telah diimplementasikan fungsi BS_Scheduler() yang didesain dengan menggunakan
II-24 algoritma Weighted Round robin (WRR) [JCT06]. Fungsi ini bertugas untuk memilih MSDU yang ada pada antrian untuk dikirim sesuai dengan bandwidth yang tersedia.
Pada proses penjdawalan, pertama-tama akan dibuat suatu parameters klasifikasi q1, q2, q3, q4, q5 yang melambangkan 5 kelas QoS yaitu UGS, rtPS, ertPS, nrtPS, dan BE. Algoritma WRR yang dipakai adalah WRR dengan jenis pendekatan kedua, dimana cycle quantum waktu dibagi menjadi 2 jenis. Pada putaran pertama bandwidth yang diberikan akan sesuai dengan kuantitas servis yang diharapkan. Kuantitas servis yang diharapkan dari tiap klasifikasi data dihitung dengan rumus berikut :
dengan i ∈ {1, 2,.., 5} dan
Keterangan : = Jumlah bandwidth yang diminta oleh tipe servis = Jumlah total bandwidth yang tersedia
Pada putaran kedua, fungsi BS_Scheduler() akan melayani tiap paket pada antrian sesuai dengan prioritasnya. Jika semua antrian pada priority i telah dilayani, maka fungsi BS_Scheduler() akan melayani antrian dengan prioritas i+1, dan seterusnya. Putaran ini akan terus diulangi hingga bandwidth yang tersedia terpakai atau semua paket pada antrian telah dilayani. Dengan metode ini dapat dijamin bahwa paket dengan prioritas rendah tetap dapat memiliki minimum bandwidth yang tersedia walaupun trafik sedang sangat ramai [JCT06].
