HIERARCHICAL TOKEN BUCKET
SEBAGAI SUATU DISIPLIN ANTRIAN
Setiap
perangkat jaringan dapat diasosiasikan dengan suatu disiplin antrian. Dengan
antrian, kita dapat menentukan bagaimana data akan dikirimkan. Harus dipahami
bahwa kita hanya dapat menshaping data yang akan kita kirimkan. Antrian
diidentifikasi dengan menggunakan bantuan sebuah handle yang memiliki format
X:Y, di mana X merepresentasikan nomor mayor, dan Y merepresentasikan nomor
minor. Handle-handle inilah yang akan mengasosiasikan kelas-kelas ke disiplin antrian
masing-masing.
Setiap
switch dan router akan melakukan proses antrian, di mana paket akan disimpan
sampai kapasitas tersedia untuk mengirimkannya ke suatu link. Waktu yang
diperlukan untuk proses antrian akan menimbulkan delay, yang akan terakumulasi di
setiap peralatan jaringan yang dilaluinya.
Gambar 3.1
Contoh Traffic Control pada Interface Output
Dalam Linux, dikenal 2 macam disiplin antrian, yaitu disiplin antrian
dengan kelas-kelas (classful queuing discipline) dan disiplin antrian non kelas
(classless queuing discipline).
3.1 Classless Queuing Discipline
Classless queuing discipline merupakan suatu disiplin
antrian yang hanya dapat menunda ataupun
mendrop paket yang diterimanya. Ini dapat digunakan untuk menshape trafik pada
semua interface tanpa adanya pembagian-pembagian kelas lagi. Pada Linux,
dikenal beberapa jenis classless queueing discipline, di antaranya adalah:
- FIFO Queueing
FIFO queueing merupakan teknik antrian interface yang
paling sederhana dan umum digunakan. Antrian ini dapat bekerja dengan baik
apabila link-link tidak mengalami kongesti. Antrian ini menjadi suatu mekanisme
default untuk setiap interface dengan bandwidth lebih dari 2MB. Paket pertama
yang ditempatkan pada antrian di interface output adalah paket yang akan
pertama kali meninggalkan interface tersebut. Masalah yang akan muncul pada
antrian ini adalah jika sebuah node melakukan transfer file, ia akan memakai semua
bandwidth pada sebuah link yang akan merugikan suatu sesi yang interaktif.
Fenomena ini mengacu pada barisan paket yang disebabkan satu sumber mengirimkan
suatu “baris” paket ke tujuannya, sehingga paket dari node lain terjebak di
belakang barisan paket tersebut. Antrian ini sangat efektif untuk link-link
yang besar yang memiliki delay yang kecil dan kongesti yang minimal.
Gambar 3.2
FIFO Queuing
- Token Bucket Filter (TBF)
Token bucket merupakan suatu definisi formal dari
suatu transfer rate. Antrian ini memiliki tiga buah komponen: ukuran burst,
mean rate, dan interval waktu (Tc).
Gambar 3.3
Token Bucket Filter
Implementasi TBF terdiri dari sebuah
buffer (bucket), yang secara konstan diisi oleh beberapa informasi virtual yang
dinamakan token, pada rate yang spesifik (token rate). Parameter paling penting
dari bucket adalah ukurannya, yaitu banyaknya token yang dapat disimpan.
Setiap token yang masuk mengumpulkan
satu paket yang datang dari antrian data dan kemudian dihapus dari bucket.
Dengan menghubungkan algoritma ini dengan dua aliran – token dan data, akan
kita dapati tiga buah kemungkinan skenario:
o
Data yang datang pada TBF memiliki rate yang
sama dengan masuknya token. Dalam hal ini, setiap paket yang masuk memiliki
tokennya masing-masing dan akan melewati antrian tanpa adanya delay.
o
Data yang datang pada TBF memiliki rate yang
lebih kecil daripada rate token. Hanya sebagian dari token yang dihapus pada
output pada tiap paket data yang dikirim ke antrian, sehingga token akan
menumpuk, memenuhi ukuran bucket. Token yang tidak digunakan kemudian akan
dapat digunakan untuk mengirimkan data pada kecepatan yang melampaui rate token
standar, ini terjadi jika ada ledakan data yang pendek.
o
Data yang datang pada TBF memiliki rate yang
lebih besar daripada rate token. Hal ini berarti bucket akan segera kosong dari
token, yang akan menyebabkan TBF akan menutup alirannya untuk sementara. Hal
inilah yang dinamakan situasi overlimit. Jika paket-paket tetap datang, maka
paket-paket akan segera didrop.
Skenario terakhir ini sangatlah penting,
karena dengan skenario ini kita dapat menshaping bandwidth yang tersedia
terhadap data yang melewati filter.
- Stochastic Fairness Queueing (SFQ)
Stochastic Fairness Queueing (SFQ) merupakan suatu
implementasi sederhana dari keluarga algoritma fair queueing. Ia kurang akurat
apabila dibandingkan dengan yang lain, tetapi ia juga membutuhkan perhitungan
yang lebih sedikit dibandingkan dengan yang lain. Kata kunci dari SFQ adalah
conversation (atau aliran), yang sangat berhubungan dengan sebuah sesi TCP atau
sebuah aliran UDP. Traffik akan dibagi ke dalam beberapa jumlah besar antrian
FIFO, satu untuk setiap conversation. Traffik kemudian dikirim secara
round-robin, dengan memberikan kesempatan kepada tiap sesi untuk mengirimkan
data pada gilirannya. SFQ disebut stochastic karena ia sebenarnya tidak
menyediakan sebuah antrian untuk setiap sesi, ia memiliki suatu algoritma yang
membagi traffik melalui sejumlah antrian yang terbatas dengan menggunakan
algoritma hashing. Karena hash inilah, sesi yang banyak dapat berakhir di
bucket yang sama, yang akan membagi dua tiap sesi kesempatan untuk mengirimkan
paket, sehingga membagi dua kecepatan efektif yang tersedia. Untuk menghindari
situasi ini menjadi terlihat, SFQ mengubah algoritma hashing yang ia miliki
secara sering sehingga dua sesi yang bertabrakan akan terjadi dalam waktu yang
singkat. SFQ hanya berguna jika interface outgoing yang kita miliki benar-benar
penuh. Jika tidak, maka tidak akan ada queue pada mesin linux kita sehingga
tidak akan ada efeknya.
3.2 Classful Queueing Discipline
Classful
Queueing Discipline merupakan suatu disiplin antrian yang akan membagi trafik
berdasarkan kelas-kelas. Classful qdisc sangat berguna apabila kita memiliki
traffik yang berbeda-beda yang harus memiliki pembedaan penanganan. Ketika
traffik memasuki suatu classful queueing discipline, maka paket tersebut akan
dikirimkan ke kelas-kelas di dalam qdisc, dengan kata lain paket tersebut perlu
diklasifikasikan terlebih dahulu. Untuk menentukan apa yang harus dilakukan
dengan sebuah paket yang datang, maka filter-filter akan digunakan. Harus
dipahami bahwa filter-filter ini dipanggil dari dalam sebuah qdisc, bukan
sebaliknya. Filter-filter yang terdapat pada qdisc tersebut akan menghasilkan
suatu keputusan, dan qdisc akan menggunakan hasil ini untuk mengantrikan paket
ke salah satu kelas yang telah tersedia. Setiap subklas mungkin saja akan
mencoba filter-filter yang lainnya untuk melihat apakah ada instruksi lain yang
berlaku. Jika tidak, maka kelas akan mengantrikan paket tersebut ke qdisc yang
ia miliki.
Di
samping memiliki suatu qdisc, kebanyakan dari classful qdisc juga menerapkan
fungsi shaping. Ini sangat berguna untuk melakukan penjadwalan paket (misal
dengan SFQ) dan pengontrolan rate sekaligus. Kita akan sangat membutuhkan
proses ini apabila kita memiliki suatu interface dengan kecepatan tinggi (misal
ethernet) ke suatu alat yang lebih lambat (misal modem). Beberapa contoh
classful queueing discipline di Linux adalah:
- CBQ (Class Based Queueing)
CBQ
dapat menerapkan pembagian kelas dan menshare link bandwidth melalui struktur
kelas-kelas secara hirarki. Setiap kelas memiliki antriannya masing-masing dan
diberikan jatah bandwidthnya. Sebuah kelas child dapat meminjam bandwidth dari
kelas parent selama terdapat kelebihan bandwidth. Gambar di bawah ini
menunjukkan komponen dasar dari CBQ. CBQ bekerja sebagai berikut: classifier
akan mengarahkan paket-paket yang datang ke kelas-kelas yang bersesuaian.
Estimator akan mengestimasi bandwidth yang sedang digunakan oleh sebuah kelas.
Jika sebuah kelas telah melampaui limit yang telah ditentukannya, maka
estimator akan menandai kelas tersebut sebagai kelas yang overlimit. Scheduler
menentukan paket selanjutnya yang akan dikirim dari kelas-kelas yang
berbeda-beda, berdasarkan pada prioritas dan keadaan dari kelas-kelas. Weighted
round robin scheduling digunakan antara kelas-kelas dengan prioritas yang sama.
Gambar 3.4
Cara Kerja CBQ
- PRIO
Priority
queueing memungkinkan manajer jaringan untuk menentukan bagaimana traffik
diprioritaskan dalam suatu jaringan. Dengan menentukan serangkaian filter
berdasarkan karakteristik dari paket, traffik ditempatkan pada suatu antrian;
antrian dengan prioritas yang lebih tinggi dilayani lebih dahulu, kemudian
antrian yang lebih rendah lagi dilayani sesuai urutannya. Jika antrian dengan
prioritas paling tinggi selalu penuh, maka antrian ini akan secara kontinyu
dilayani dan paket-paket dari antrian yang lain akan didrop. Dalam algoritma
antrian ini, maka satu jenis traffik jaringan dapat mendominasi traffik-traffik
lainnya. Priority queueing akan menentukan traffik ke dalam salah satu dari 4
antrian: tinggi, sedang, normal, dan rendah.
Priority
Queueing dapat menjamin bahwa traffik-traffik yang penting mendapatkan
penanganan yang tercepat pada setiap titik di mana ia digunakan. Queueing ini
di buat untuk memberikan prioritas yang ketat pada traffik-traffik yang
penting. Priority queueing dapat secara fleksibel membagi prioritas berdasarkan
protokol jaringan (misal IP, IPX, atau AppleTalk), interface yang masuk, ukuran
paket, alamat asal/tujuan, dan sebagainya.
Gambar 3.5
PRIO Queuing
- HTB (Hierarchical Token Bucket)
Gambar 3.6
Konsep Link Sharing
HTB menggunakan TBF sebagai estimator yang
sangat mudah diimplementasikan. TBF
sangat mudah diset karena banyak dari administrator jaringan yang memiliki ilmu
tentangnya. Estimator ini hanya menggunakan parameter rate, sebagai akibatnya
seseorang hanya perlu mengeset rate yang akan diberikan ke suatu kelas. Oleh
karena itu HTB lebih mudah dan intuitif dibandingkan CBQ.
Pada HTB terdapat parameter ceil sehingga kelas akan
selalu mendapatkan bandwidth di antara base rate dan nilai ceil ratenya.
Parameter ini dapat dianggap sebagai estimator kedua, sehingga setiap kelas
dapat meminjam bandwidth selama bandwidth total yang diperoleh memiliki nilai
di bawah nilai ceil. Hal ini mudah diimplementasikan dengan cara tidak
mengijinkan proses peminjaman bandwidth pada saat kelas telah melampaui rate
ini (keduanya leaves dan interior dapat memiliki ceil). Sebagai catatan,
apabila nilai ceil sama dengan nilai base rate, maka akan memiliki fungsi yang
sama seperti parameter bounded pada CBQ, di mana kelas-kelas tidak diijinkan
untuk meminjam bandwidth. Sedangkan jika nilai ceil diset tak terbatas atau
dengan nilai yang lebih tinggi seperti kecepatan link yang dimiliki, maka akan
didapat fungsi yang sama seperti kelas non-bounded. Sebagai contoh, seseorang
dapat menjamin bandwidth 1 Mbit untuk suatu kelas, dan mengijinkan penggunaan
bandwidth sampai dengan 2 Mbit pada kelas tersebut apabila link dalam keadaan
idle. Parameter ceil ini sangatlah berguna untuk ISP karena para ISP
kemungkinan besar akan memakainya untuk membatasi jumlah servis yang akan
diterima oleh suatu pelanggan walaupun pelanggan lain tidak melakukan
permintaan servis, dengan kata lain kebanyakan ISP menginginkan pelanggan untuk
membayar sejumlah uang lagi untuk memperoleh pelayanan yang lebih baik.
Untuk
menjadwalkan pengiriman paket dari antrian, maka HTB menggunakan suatu proses
penjadwalan yang dapat dijelaskan sebagai berikut:
Keterangan:
·
Class merupakan parameter yang
diasosiasikan dengan rate yang dijamin (assured rate) AR, ceil rate CR,
prioritas P, level dan quantum. Class dapat memiliki parent. Selain AR
dan CR, didefinisikan juga actual rate atau R, yaitu rate dari aliran paket
yang meninggalkan class dan diukur pada suatu perioda waktu tertentu.
·
Leaf merupakan class yang tidak memiliki
anak. Hanya leaf yang dapat memegang antrian paket.
·
Level dari kelas menentukan posisi dalam
suatu hirarki. Leaf-leaf memiliki level 0, root class memiliki level=jumlah
level-1 dan setiap inner class memiliki level kurang dari satu dari parentnya.
Untuk gambar di bawah (jumlah level=3).
·
Mode dari class merupakan nilai-nilai
buatan yang diperhitungkan dari R, AR, dan CR. Mode-mode yang mungkin adalah:
o Merah:
R > CR
o Kuning:
R <= CR and R > AR
o Hijau
selain yang di atas
Kita
asumsikan terdapat kelas-kelas yang tersusun seperti pohon pada HTB scheduler.
Dalam tiap level, terdapat sebuah self feed yang terdiri dari self slot.
Sehingga jika misalkan terdapat tiga buah level, maka terdapat 6 buah self slot
(kita abaikan dulu slot putih). Setiap self slot, memegang daftar kelas-kelas,
daftar tersebut digambarkan melalui garis berwarna yang terhubung dari self
slot menuju kelas. Self slot berisikan daftar dari semua kelas-kelas hijau yang
memiliki permintaan.
Setiap
kelas inner (non-leaf), memiliki inner feed slot. Inner feed memiliki sebuah inner
feed slot per prioritas (merah untuk prioritas tinggi, biru untuk prioritas
rendah) dan per inner class. Inner slot
akan menangani kelas-kelas anak yang berwarna kuning.
 |
 |
Gambar 3.7
Cara Kerja
Scheduler di HTB
Slot putih
yang terdapat pada gambar di atas berfungsi sebagai antrian tunggu per level.
Ia akan memegang daftar kelas-kelas yang berada pada levelnya yang berwarna
merah atau kuning.
Dari sini
kita mungkin telah dapat melihat apabila kita dapat menjaga semua kelas pada
daftar yang bersesuaian, maka proses pemilihan paket selanjutnya yang akan
melakukan pengiriman paket dari antrian akan sangatlah mudah. HTB cukup melihat
pada daftar self feed dan memilih slot yang tidak kosong (yaitu slot yang
terhubung dengan garis ke sebuah kelas) dengan level yang paling rendah dan
prioritas yang paling tinggi. Pada gambar 1 di atas tidak terdapat slot yang
tidak kosong, sehingga tidak ada paket yang akan dikirim. Pada gambar 2,
terdapat slot merah dengan level 0 pada kelas D, sehingga kelas D dapat mengirim
paketnya.
Untuk lebih
jelasnya dapat dijelaskan sebagai berikut. Pada gambar 1, tidak terdapat
backlogged leaf (semua non-backlogged leaf digambarkan dengan lingkaran tipis)
sehingga tidak ada yang dapat dilakukan. Pada gambar 2, paket-paket datang untuk
C dan D. Sehingga HTB akan mengaktifkan kelas-kelas ini, dan karena keduanya
berwarna hijau, HTB akan menambahkannya ke self slot yang bersesuaian. Proses
dequeue akan memilih D karena D berada pada level yang rendah dan memiliki
prioritas yang lebih tinggi daripada C.
 |
 |
Gambar 3.8
Cara Kerja
Scheduler di HTB
Kita
asumsikan paket telah dikirim dari kelas D dan HTB mengukur berapa besar paket
yang dikirim melalui bantuan TBF. Karena paket yang dikirim melampaui besar
rate yang telah ditetapkan untuk kelas D, maka HTB akan memaksa D untuk berubah
warna menjadi kuning. Sebagai bagian dari perubahan ini, HTB akan menghapus D
dari daftar self feed dan menambahkan D ke inner feed B. HTB juga secara
rekursif akan menambahkan B ke self feed pada levelnya. Karena D akan kembali
ke keadaan hijau lagi pada suatu waktu, maka HTB akan menambahkan D ke slot
putih pada level 0.
Proses
dequeue sekarang akan memilih kelas C meskipun kelas C memiliki prioritas yang
lebih rendah dibandingkan D. Ini dikarenakan C berada pada daftar slot dengan
level yang lebih rendah. Secara intuitifpun hal ini baik dilakukan, untuk apa
meminjam bandwidth jika ada yang dapat mengirim paket tanpa meminjam bandwidth.
a.
TBF lebih akurat dalam menentukan rate.
b.
TBF tidak memerlukan waktu akhir pengiriman yang tepat
seperti pada ewma-idle. Akibatnya, HTB akan bekerja secara kuat pada semua
perangkat jaringan di mana CBQ menunjukkan rate yang aneh dan salah.
c.
HTB memungkinkan cross-device bandwidth sharing.
Sehingga ethernet pertama dapat memakai bandwidth dari ethernet kedua.
0 komentar:
Posting Komentar