22

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 guaranteed-

service.

b. Alokasi resource secara adil pada aplikasi best-effort.

23

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 antrian-

antrian 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

24

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.

25

III.3 Klasifikasi Algoritma Scheduling

Mekanisme packet scheduling terbagi kedalam 2 kategori: work-conserving dan non-

work-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 non-

work 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

26

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

27

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

28

Adapun variabel-variabel yang digunakan dalam algoritma GPS adalah:

- ,iφ merupakan bagian bandwidth yang disediakan untuk setiap flow

- senti (t1, t2) : jumlah data flow i yang dapat dilayani selama rentang waktu (t1, t2).

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 t1 dan t2

j

i

j

i

ttsentttsent

φφ

=),(),(

21

21

mengikuti rumusan sebagai

berikut:

atau =i

i ttsentφ

),( 21 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).

29

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 flow-

flow 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.

30

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.

31

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

32

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. Flow-

based 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

33

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

34

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.

35

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.

36

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.

37

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

38

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 pseudocode-

nya 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:

39

Fungsi Enqueue(i) menempatkan paket-paket yang baru sampai kedalam antrian-

antrian 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)

40

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 men-

enqueue dan O(1) untuk men-dequeue sebuah paket, maka akan ditetapkan

work untuk algoritma tersebut adalah O(log(n)).

41

• 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(t1, t2) didefinisikan sebagai nilai maksimum, dari semua

pasangan flow i, j yang di-backlog selama interval (t1, t2

j

j

i

i

fttsent

fttsent ),(),( 2121 −

), untuk rumusan

berikut: . Sebuah algoritma scheduling disebut fair

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 (t1, t2), Queue(i) menerima pelayanan dari scheduler

sebanyak m kali. Maka berlaku rumusan sebagai berikut:

m.Q(i) – Max ≤ sent(i)(t1, t2

• Rumusan 3

) ≤ m.Q(i) + Max

Pada semua interval waktu (t1, t2) berlaku:

FM(t1, t2

• Rumusan 4

) ≤ 2 Max + Q , dimana Q = Min[ Q(i) ]

DRR mempunyai beban kerja O(1) jika untuk semua i, Q(i) ≥ Max