BAB III
Algoritma Scheduling
III.1 Pendahuluan Generasi internet ke depan mendukung 2 tipe aplikasi: best-effort dan aplikasi guaranted-service. Aplikasi berbasis best-effort, yang sekarang ini umum pada jaringan internet, adaptif terhadap kondisi jaringan seperti apa pun. Sebagai contoh, aplikasi FTP idealnya mempunyai delay end-to-end nol dan mendapatkan bandwidth link tak terbatas, tetapi tetap dapat berjalan pada sumberdaya jaringan yang terbatas. Suatu layanan disebut best-effort karena jaringan tetap berjanji untuk melakukan yang terbaik demi terkirimnya paket-paket data walaupun tanpa menjamin QoS
Disamping aplikasi best-effort, di masa depan jaringan internet diharapkan dapat membawa trafik dari aplikasi yang membutuhkan jaminan QoS. Oleh karena itu, untuk menjamin QoS, dimasa depan tidak akan lagi digunakan jaringan dengan bandwidth kurang dari 64 kbps untuk membawa trafik voice.
Jaminan QoS yang dirasakan oleh sebuah koneksi bergantung pada algoritma scheduling yang digunakan. Scheduling
dijalankan pada node-node switching
sepanjang jalur antara sumber dan tujuan. Algoritma scheduling memilih paket mana yang akan dikirimkan pada link berikutnya. Scheduler dapat memberikan delay antrian dan bandwidth yang berbeda-beda untuk setiap koneksi dengan cara menentukan urutan pelayanan dan jumlah paket yang akan ditransmisikan untuk setiap koneksi. Jadi, internet masa depan membutuhkan aturan scheduling untuk mewujudkan: a. Delay, bandwidth, dan loss per koneksi yang dapat menjamin aplikasi guaranteedservice. b. Alokasi resource secara adil pada aplikasi best-effort.
22
Dibawah ini gambar sebuah model algoritma scheduling:
Gambar III.1. Model Algoritma Scheduling
Jadi setiap ada dua komponen utama yang terlibat dalam proses scheduling: classifier dan scheduler. Fungsi classifier adalah menempatkan paket-paket kedalam antrianantrian menurut aturan tertentu. Sedangkan fungsi scheduler adalah memilih dari antrian-antrian, paket-paket mana yang akan dikirimkan.
III.2 Persyaratan sebuah scheduling Dalam perancangan sebuah algoritma scheduling, ada 5 persyaratan yang harus dipertimbangkan: kompleksitas, fairness, isolasi/proteksi, efisiensi, dan performansi . Bergantung pada situasinya, sebagian dari persyaratan tersebut menjadi lebih penting dari yang lainnya, sehingga keputusan terbaik tergantung pada situasi dan masalahnya. Berikut ini uraian dari 5 persyaratan tersebut: a. Kompleksitas: setiap skema scheduling mempunyai tingkat kompleksitas yang berlainan dipandang dari segi pengontrolan dan hardware. Kompleksitas algoritma merupakan hal yang penting untuk dipertimbangkan karena router harus mengambil paket untuk diberikan pada output link setiap kali sebuah paket akan diberangkatkan. Frekuensi keberangkatan paket-paket tergantung pada
23
kecepatan output link. Keberangkatan dapat terjadi sekali setiap beberapa mikro detik, atau sekali setiap beberapa nano detik. Jadi, demi mudah dan murahnya implementasi, sebaiknya algoritma scheduling dibuat ringkas dengan beberapa operasi yang sederhana. b. Fairness: sebuah skema scheduling bertugas membagikan sumberdaya jaringan berupa link bandwidth dan kapasitas buffer kepada antrian-antrian, maka pembagian sumber daya tersebut harus adil. Fairness merupakan properti yang dibutuhkan untuk layanan best-effort. c. Isolasi dan proteksi: algoritma scheduling yang baik melakukan perlindungan dan isolasi terhadap user. Perlindungan yang dimaksud adalah dengan membuat miss-behaving user tidak mempengaruhi well-behaving user. Miss-behaving user adalah para pengguna jaringan yang mengirimkan paket-paket data pada bit rate yang lebih tinggi dari yang seharusnya sehingga dapat mengakibatkan unfairness/hilangnya fairness. d. Efisiensi: Sebuah algoritma dikatakan lebih efisien dari pada algoritma yang lain apabila pada beban yang lebih berat dapat menjamin kinerja yang sama. Atau pada beban yang sama dapat memberikan kinerja yang lebih baik. Dan juga, agar jaminan QoS terpenuhi, koneksi yang guaranteed-service jumlahnya harus dibatasi dengan menggunakan mekanisme Admission Control. e. Performance: merupakan tujuan utama dibuatnya algoritma scheduling, yaitu menjamin throughput, delay, dan loss sesuai dengan yang diinginkan. Jaringan menjamin tersedianya koneksi sesuai dengan kebutuhan setiap layanan dan para pengguna jaringan pun tidak menggunakan jaringan melebihi batas yang telah ditetapkan. Menjamin kinerja sistem di level yang baik merupakan permasalahan yang sulit, karena semua scheduler yang dilalui paket data sepanjang koneksi harus berpartisipasi dalam memenuhinya.
24
III.3 Klasifikasi Algoritma Scheduling Mekanisme packet scheduling terbagi kedalam 2 kategori: work-conserving dan nonwork-conserving. Algoritma scheduling yang work-conserving akan melewati antrian yang tidak memiliki paket, sedang non-work-conserving selalu memberikan waktu untuk setiap antrian walaupun dalam antrian tersebut tidak dalam keadaan akan mengirimkan paket.
Salah satu sifat algoritma yang bersifat work-conserving adalah mempunyai total delay antrian rata-rata yang minimum. Total delay antrian rata-rata dihitung berdasar semua flow yang harus dilayani. Semua algoritma work-conserving mempunyai total delay antrian rata-rata yang sama. Dengan kata lain, meskipun setiap scheduler menggunakan algoritma yang berbeda, delay antrian rata-rata secara keseluruhan selalu sama. Ini menunjukkan bahwa algoritma work-conserving melayani flow-flow tertentu dengan lebih cepat tetapi mengorbankan flow yang lain.
Timbul sejumlah pertanyaan, mengapa kita tetap menggunakan algoritma non-work conserving dan membuang bandwidth dengan meninggalkan link dalam keadaan menganggur sampai ada paket yang harus dikirimkan? Jawabannya adalah, algoritma non-work conserving membuat aliran trafik lebih dapat diprediksi. Algoritma nonwork conserving biasanya pilihan terbaik untuk jaringan yang melayani trafik real time karena dapat menjamin delay dan delay jitter pada nilai tertentu.
III.4 Beberapa Jenis Scheduling Semua algoritma scheduling merupakan varian dari dua disiplin scheduling berikut: Generalized Processor Sharing (GPS) dan Earliest-Deadline-First (EDF). GPS membagi sumberdaya diantara antrian-antrian berdasarkan kebutuhannya, sedang EDF melayani paket berdasarkan urutan deadline. EDF berusaha mencapai level QoS tertentu dengan melayani paket-paket berdasar urutan deadlinenya. Paket-paket yang
25
lebih mendekati deadline lebih dahulu dilayani. Deadline sebuah paket berkaitan dengan maximum tolerable delay dan dihitung dengan menambahkan maximum tolerable delay terhadap waktu kedatangan paket. Contoh algoritma EDF adalah: delay earliest due date dan jitter earliest due date.
Subbab ini akan berkonsentrasi pada 2 jenis scheduling: Weighted Round Robin (WRR) dan Deficit Round Robin (DRR), karena 2 algoritma inilah yang akan dianalisa performansinya dalam jaringan WIMAX. Namun demikian algoritma scheduling yang lain pun akan dibahas secara sekilas.
III.4.1 Generalized Processor Sharing (GPS) GPS merupakan algoritma scheduling yang ideal. Dalam algoritma ini, paket-paket dari setiap flow dimasukkan kedalam antrian-antrian. Setiap antrian yang tidak kosong akan dilayani sedang antrian yang kosong akan dilewati. Dari antrian-antrian tersebut secara round robin GPS scheduling mengirimkan data dalam jumlah yang sangat kecil sekali (infinitesimal). Setiap antrian dapat diberikan bobot, dan layanan akan diterima sesuai dengan bobot tersebut.
Gambar III.2. GPS scheduling
26
Berikut ini contoh-contoh yang menunjukkan bagaimana cara kerja algoritma GPS: Contoh 1 •
Ukuran paket A, B, dan C masing-masing: 10, 20, dan 30
•
Paket A, B, dan C tiba di waktu 0
•
Semua antrian mempunyai bobot yang sama
Gambar III.3. Contoh 1, Scheduling GPS
Contoh 1 •
Ukuran paket A, B, dan C masing-masing: 15, 20, dan 10
•
Paket A, B, dan C masing-maing tiba di waktu: 0, 5, 15
•
Semua antrian mempunyai bobot yang sama
Gambar III.4. Contoh 2, Scheduling GPS
27
Adapun variabel-variabel yang digunakan dalam algoritma GPS adalah: - φi , merupakan bagian bandwidth yang disediakan untuk setiap flow - sent i (t 1 , t 2 ) : jumlah data flow i yang dapat dilayani selama rentang waktu (t 1 , t 2 ). Sebuah flow didefinisikan sebagai backlogged jika flow tersebut mempunyai paket yang sedang menerima layanan atau sedang menunggu pelayanan. Pada GPS, untuk pasangan flow i dan j selama interval waktu t 1 dan t 2 mengikuti rumusan sebagai berikut:
senti (t1 , t2 ) φ i = sent j (t1 , t2 ) φ j
sent i (t1 , t 2 )
atau
φi
= konstanta
Meskipun GPS scheduling menyediakan fairness yang ideal dan isolasi flow yang sempurna, tetapi algoritma ini tidak dapat dibuat. Sampai saat ini, mengirimkan data dari antrian-antrian dalam besaran yang sangat kecil adalah suatu hal yang mustahil. Oleh karena itu, secara praktis tidak ada satu pun algoritma scheduling yang dapat menyamai keidealan GSP dalam hal fairness dan isolasi. Pada saat scheduler melayani sebuah paket, maka pada saat itu sedang terjadi ketidakadilan terhadap paket yang lain. Sampai saat ini telah banyak diusulkan berbagai macam algoritma scheduling yang berusaha mendekati keidealan karakteristik GPS.
III.4.2 First In First Out (FIFO) FIFO merupakan skema scheduling yang paling sederhana. Dalam FIFO semua paket diperlakukan sama. Paket-paket ditempatkan dalam antrian hanya berdasarkan urutan kedatangan, tidak memandang seberapa penting paket tersebut. Algoritma FIFO juga sering disebut First Come First Served (FCFS).
28
Gambar III.5. FIFOScheduling
FIFO merupakan algoritma yang bersifat work-conserving dan mempunyai kompleksitas yang sangat rendah, sebab itu FIFO menjadi algoritma yang paling umum dipakai dalam jaringan. Ada beberapa keterbatasan FIFO, misalnya: •
Tidak dapat memberikan fairness dalam alokasi sumberdaya kepada flowflow yang sedang dilayani. Namun demikian, hal ini tidak terlalu menjadi masalah untuk aplikasi berbasis best-effort.
•
Tidak dapat menjamin kinerja sistem dalam hal: delay, delay jitter, atau throughput paket-paket pada aplikasi-aplikasi yang real time. Oleh karena itu, aplikasi multimedia tidak dapat bekerja dengan baik apabila digunakan scheduler FIFO. Satu cara untuk menjamin batasan delay adalah dengan membatasi ukuran buffer. Setiap paket dijamin akan dikirimkan dalam waktu kurang dari waktu yang diperlukan untuk melayani antrian yang penuh. Kerugian cara ini adalah, akan meningkatkan packet loss probability, sebagai sebuah konsekuensi dari high buffer overflow probability.
29
III.4.3 Priority Queueing (PQ) Algoritma scheduling ini merupakan versi sederhana dari queue scheduling yang bertujuan untuk mendukung differentiated service class. Dalam PQ, pertama-tama sistem mengklasifikasi
paket-paket berdasar tipe layanannya dan setelah itu
ditempatkan pada antrian-antrian yang memiliki prioritas berlainan. Paket-paket dalam sebuah antrian akan dilayani apabila semua paket yang berprioritas tinggi sudah dilayani. Dalam masing-masing antrian paket-paket dilayani secara FIFO.
Gambar III.6. Priority Queueing (PQ)
III.4.4 Fair Queueing (FQ) Skema ini diusulkan oleh John Nagle pada tahun 1987. FQ merupakan dasar dari kelas scheduling yang menjamin setiap aliran paket dapat mengakses sumberdaya jaringan secara adil dan mencegah bursty flow mengakses jaringan secara berlebihan. Dalam FQ, paket-paket pertama-tama diklasifikasi dan setelah itu dimasukkan ke dalam antrian. Setelah itu setiap antrian dilayani dengan mengirimkan 1 paket per antrian, antrian yang kosong akan dilewati.
30
Gambar III.7. Fair Queueing (FQ)
Keuntungan utama FQ adalah bahwa bursty yang melewati batas maksimum tidak akan mengganggu QoS flow yang lain, karena setiap flow mempunyai antrian yang berbeda. Jika flow berusaha mengonsumsi melebihi bandwidth yang telah dibagi secara adil, maka hanya antrian tersebut yang kena dampaknya, sehingga tidak berpengaruh kepada performansi antrian yang lain.
Meskipun demikian, FQ juga memiliki beberapa keterbatasan, diantaranya: •
FQ diimplementasikan di tingkat software bukan hardware. Hal ini menjadikan FQ menjadi interface kecepatan rendah yang hanya dapat digunakan pada edge jaringan.
•
Tujuan FQ adalah untuk mengalokasikan bandwidth dalam jumlah yang sama kepada setiap flow. FQ tidak dirancang untuk mendukung sejumlah flow yang mempunyai kebutuhan bandwidth yang berbeda.
•
FQ memberikan jumlah bandwidth yang sama kepada setiap flow hanya jika semua paket di dalam antrian-antrian berukuran sama. Flow-flow dengan paket
31
yang besar-besar akan mendapatkan bagian bandwidth yang lebih besar daripada flow dengan ukuran paket yang kecil. •
FQ sangat sensitif terhadap permintaan kedatangan paket. Jika paket datang di dalam antrian kosong segera setelah antrian tersebut didatangi oleh scheduler round-robin, maka paket tersebut harus menunggu di dalam antrian sampai semua antrian terlayani sebelum dapat ditransmisikan.
•
FQ tidak memberikan mekanisme yang mendukung layanan real-time seperti VoIP
•
FQ mengasumsikan bahwa klasifikasi trafik jaringan dapat dilakukan dengan mudah. Pada jaringan IP, hal ini tidak semudah seperti yang diperkirakan. Flowbased dapat diklasifikasikan pada alamat sumber paket, akan tetapi kemudian setiap workstation diberi resource jaringan dalam jumlah yang sama atau mainframe. Jika akan mengklasifikasikan flow-based pada koneksi TCP, maka harus dilihat lebih dalam header paketnya, dan itupun masih harus berurusan dengan masalah lain seperti enkripsi, fragmentasi dan flow-flow UDP.
•
FQ pada umumnya tidak dapat dikonfigurasi pada router inti karena router inti sangat dibutuhkan untuk mendukung ribuan atau bahkan puluhan ribu antrian diskrit pada setiap port-nya. Hal ini dapat menambah kompleksitas dan overhead manajemen yang akan berdampak pada skalabilitas FQ itu sendiri dalam jaringan IP yang luas.
FQ biasanya diaplikasikan di edge jaringan di mana banyak subscriber terkoneksi ke penyedia
layanannya.
Vendor
biasanya
mengimplementasikan
FQ
untuk
mengklasifikasikan paket ke 256, 512, atau 1024 antrian menggunakan fungsi hash yang dihitung melalui pasangan alamat sumber/tujuan. FQ memberikan isolasi yang sempurna bagi flow trafik individu karena pada edge jaringan, subscriber memiliki jumlah flow terbatas, sehingga setiap flow dapat diberikan pada suatu antrian. Di
32
dalam FQ class-based, port output dibagi ke dalam klas layanan yang berbeda. Setiap kelas layanan dialokasikan prosentase bandwidth tertentu.
III.4.5 Weighted Fair Queueing (WFQ) WFQ dikembangkan secara independen pada tahun 1989 oleh Lixia Zhang dan Alan Demers, Srinivasan Keshav dan Scott Shenke. WFQ mendasari algoritma scheduling untuk mengatasi kelemahan FQ. Algoritma ini memberikan bobot antrian yang berbeda berdasarkan kebutuhan bandwidth setiap aliran paket. WFQ dapat memberikan distribusi bandwidth yang fair untuk variable-length packet dengan cara meniru cara kerja GPS.
Gambar III.8. Weighted Fair Queueing (WFQ)
III.4.6 Weighted Round Robin (WRR) WRR merupakan emulasi sederhana dari GPS. Perbedaan antara GPS dengan WRR adalah WRR melayani sejumlah tertentu data. Tidak seperti GPS yang mengirimkan data dalam besaran yang amat sangat kecil. Besaran data yang dilayani oleh WRR dapat berupa paket atau byte. WRR scheduling akan lebih mendekati GPS jika semua flow mempunyai bobot yang sama dan setiap paket mempunyai ukuran yang sama.
Algoritma scheduling ini merupakan dasar dari kelas scheduling yang dibuat untuk mengatasi kelemahan FQ dan PQ. WRR mengatasi kelemahan FQ dengan cara
33
memberikan bobot yang berbeda untuk setiap antrian. Bobot ini menentukan besarnya bagian setiap antrian terhadap bandwidth sistem. WRR mengatasi kelemahan PQ dengan cara, antrian berprioritas rendah tetap diberi kesempatan mengirimkan paket sesuai dengan bobotnya, jadi tidak diabaikan sama sekali.
Dalam antrian WRR, pertama-tama paket diklasifikasi kedalam kelas-kelas (misalnya, real-time, interaktif, transfer file, dsb), kemudian paket-paket tersebut dimasukkan ke dalam antrian-antrian yang khusus melayani kelas-kelas tersebut. Tiap-tiap antrian dilayani secara round-robin. Sama seperti PQ dan FQ, antrian yang kosong akan dilewati. WRR juga disebut sebagai Class-Based Queueing (CBQ) atau Custom Queueing.
Algoritma WRR mendukung alokasi bandwidth yang berbeda untuk setiap kelas dengan cara: •
Mengijinkan antrian ber-bandwidth tinggi untuk mengirimkan lebih dari satu paket pada setiap putaran.
•
Pada setiap putaran masing-masing antrian hanya boleh mengirimkan satu paket setiap diberi kesempatan, tetapi antrian berbandwidth tinggi akan diberi kesempatan transmit beberapa kali.
Pada gambar dibawah ini antrian trafik real-time diberi 25% BW, antrian trafik interaktif diberi 25% BW, dan antrian trafik file transfer diberi 50% BW. Dengan demikian pada setiap putarannya antrian file transfer akan diberi kesempatan 2 kali transmit, masing-masing satu paket, atau setiap kali diberi kesempatan akan mengirimkan langsung 2 paket.
34
Gambar III.9. Weighted Round Robin (WRR)
Algoritma scheduling WRR mempunyai keuntungan dan kerugian/keterbatasan. Adapun keuntungannya adalah: •
Karena sederhana, WRR dapat dibuat secara hardware, sehingga dapat dipakai pada interface berkecepatan tinggi.
•
Dengan WRR secara kasar dapat dikontrol berapa besar presentase bandwidth yang dialokasikan untuk masing-masing kelas
•
WRR menjamin setiap kelas layanan mempunyai akses terhadap bandwidth sistem sehingga terhindar dari kelaparan bandwidth.
•
Daripada menggunakan prioritas (seperti pada PQ), klasifikasi berdasar kelas menghasilkan manajemen yang lebih adil dan lebih stabil bagi aplikasi-aplikasi. Sebagai contoh, jika kita memberikan prioritas lebih kepada trafik real-time daripada trafik file transfer, maka jumlah trafik real-time yang berlebihan akan menghambat semua trafik file transfer dari jaringan. WRR didasarkan pada sebuah kepercayaan, bahwa, untuk mengontrol kongesti mekanisme resource reduction lebih baik daripada resource denial.
35
Kekurangan yang utama dari WRR adalah, algoritma ini hanya akan memberikan persentase bandwidth yang tepat kepada setiap kelas layanan jika semua paket dalam semua antrian mempunyai ukuran yang sama atau ketika ukuran paket rata-rata dapat diketahui dari awal.
Berikut ini diberikan sebuah gambar dan contoh kasus untuk menjelaskan cara kerja WRR:
Gambar III.10. Contoh untuk WRR
Diasumsikan untuk antrian 1 sampai 4 masing-masing diberi bagian bandwidth sebesar: 40%, 30%, 20%, dan 10%. Anggap ukuran semua paket sebesar 100 byte. Pada setiap putaran antrian 1 mengirimkan 4 paket (400 byte), antrian 2 mengirimkan 3 paket (300 byte), antrian 3 mengirimkan 2 paket (200 byte),dan antrian 4 mengirimkan 1 paket (100 byte). Jadi total paket yang dikirim untuk satu putaran sebesar 1000 byte, dan setiap antrian mendapat bagian yang sesuai dengan bobotnya. Dalam contoh ini WRR secara sempurna mendistribusikan bandwidth sistem kepada semua antrian.
36
III.4.7 Deficit Round Robin (DRR) DRR scheduling diusulkan oleh M. Shreedhar dan G. Varghesee pada tahun 1995. DRR dibuat untuk mengatasi kelemahan yang ada pada WRR dan WFQ. DRR mengatasi kelemahan pada WRR dengan memberikan akses bandwidth sistem secara fair kepada antrian-antrian yang memiliki panjang paket yang berbeda. DRR mengatasi kelemahan WFQ karena algoritma ini mempunyai kerumitan komputasi yang lebih rendah. Oleh karena itu, algoritma ini dapat secara langsung diterapkan pada hardware.
Dalam DRR, setiap antrian dikonfigurasi dengan sejumlah parameter: •
Bobot, menentukan persentasi dari bandwidth sistem untuk masing-masing antrian
•
Deficit Counter (DC), menentukan jumlah byte yang dapat ditransmisikan oleh sebuah antrian pada saat diberikan kesempatan. Dengan adanya deficit counter, sebuah antrian yang tidak dapat transmit (karena ukuran paketnya lebih besar dari nilai deficit counter) dapat memiliki simpanan transmisi. Simpanan transmisi ini akan digunakan pada putaran selanjutnya sehingga antrian tersebut dapat mengirimkan paket lebih besar/banyak dari jatah yang telah ditentukan.
•
Quantum of Service (Q), nilai yang proporsional dengan bobot sebuah antrian dan quantum ini dinyatakan dalam byte. Deficit Counter sebuah antrian nilainya meningkat sebesar Quantum antrian tersebut setiap kali dikunjungi oleh scheduler. Jika quantum [i] = 2 * quantum [k], maka antrian i akan menerima jatah bandwidth sebanyak dua kali yang diterima antrian k.
III.4.7.1 Algoritma DRR Scheduler mengunjungi setiap antrian yang tidak kosong dan mendeteksi ukuran paket yang akan dikirimkan pada antrian tersebut, kemudian DC ditingkatkan sebesar nilai quantum. Jika ukuran paket dalam sebuah antrian lebih besar dari DC, maka
37
scheduler akan berpindah ke antrian berikutnya. Dan sebaliknya, jika ukuran paket lebih kecil atau sama dengan DC maka paket tersebut akan dilayani dan nilai DC akan dikurangi sejumlah byte ukuran paket tersebut. Pada putaran-putaran selanjutnya scheduler akan terus menerus mengunjungi setiap antrian yang tidak kosong, melakukan dequeue terhadap paket-paketnya, dan menurunkan nilai DC sebesar paket yang dilayani sampai ukuran paket lebih besar dari DC atau antrian tersebut kosong. Jika antrian kosong nilai DC diset ke nol.
Gambar III.11. Deficit Round Robin (DRR)
III.4.7.2 DRR pseudocode Pada bagian ini akan dipaparkan pseudocode DRR, dengan mengamati pseudocodenya scheduling ini lebih mudah dipahami. Larik DC diinisialisasi dengan nol. Dalam contoh berikut, antrian diberi nomor 1 sampai n, dimana n adalah jumlah antrian maksimum pada port output:
38
Fungsi Enqueue(i) menempatkan paket-paket yang baru sampai kedalam antrianantrian yang sesuai dan memasukkan antrian tersebut kedalam ActiveList. ActiveList merupakan daftar antrian-antrian yang tidak kosong, paling sedikit berisi satu paket. Isi ActiveList selalu diperbaharui agar scheduler tidak membuang waktunya dengan mendatangi antrian yang kosong. Ketika sebuah paket mendatangi suatu antrian yang sebelumnya diketahui kosong, maka index antrian tersebut ditambahkan pada bagian akhir ActiveList oleh fungsi InsertActiveList(i). Begitu juga, kapan saja sebuah antrian menjadi kosong, index antrian tersebut dikeluarkan dari ActiveList oleh fungsi RemoveActiveList(i);
Kapan saja sebuah index antrian berada pada bagian awal ActiveList, fungsi Dequeue(i) akan mengeluarkan dari Queue(i) paket sebesar : DeficitCounter(i)+Quantum(i)
39
Gambar dibawah ini menjelaskan satu contoh kasus bagaimana scheduling DRR melayani paket-paket dalam sebuah antrian:
Gambar III.12. Cara Kerja DRR
Dari gambar diatas terlihat keunggulan scheduling DRR dalam melayani antrian dengan ukuran paket yang berbeda-beda. Berikut adalah beberapa definisi yang berkaitan dengan algoritma scheduling DRR: •
Definisi 1: work didefinisikan sebagai maksimum kompleksitas waktu yang dibutuhkan untuk melakukan enqueue atau dequeu terhadap sebuah paket. Jika sebuah sebuah algoritma membutuhkan waktu selama O(log(n)) untuk menenqueue dan O(1) untuk men-dequeue sebuah paket, maka akan ditetapkan work untuk algoritma tersebut adalah O(log(n)).
40
•
Definisi 2: sebuah flow disebut backlogged selama interval I pada sebuah eksekusi jika antrian untuk flow i tidak pernah kosong selama interval I tersebut.
•
Definisi 3: FM(t 1 , t 2 ) didefinisikan sebagai nilai maksimum, dari semua pasangan flow i, j yang di-backlog selama interval (t 1 , t 2 ), untuk rumusan berikut:
sent i (t1 , t 2 ) sent j (t1 , t 2 ) . Sebuah algoritma scheduling disebut fair − fi fj
jika FM bernilai kecil dan konstan .
Selanjutnya, berikut ini beberapa rumusan untuk DRR: •
Rumusan 1 Pada semua Queue(i) berlaku rumusan: 0 < DC(i) < Max. Max adalah ukuran paket maksimum pada setiap antrian
•
Rumusan 2 Pada interval waktu (t 1 , t 2 ), Queue(i) menerima pelayanan dari scheduler sebanyak m kali. Maka berlaku rumusan sebagai berikut: m.Q(i) – Max ≤ sent(i)(t 1 , t 2 ) ≤ m.Q(i) + Max
•
Rumusan 3 Pada semua interval waktu (t 1 , t 2 ) berlaku: FM(t 1 , t 2 ) ≤ 2 Max + Q , dimana Q = Min[ Q(i) ]
•
Rumusan 4 DRR mempunyai beban kerja O(1) jika untuk semua i, Q(i) ≥ Max
41
