Penjadwalan paket secara hierarcical

Alokasi link-sharing bisa dikonfigurasi statis atau dinamis. Tujuan pertama dari penerapan linksharing adalah setiap kelas akan mendapat bandwidth yang dialokasikan, dalam beberapa interval waktu tertentu, saat waktu congestion. Untuk kelas dengan alokasi link-sharing 0 seperti FTP, bandwidth yang diterima ditentukan oleh mekanisme penjadwal pada gateway dan mekanisme link-sharing tidak “menjamin” bandwidth untuk kelas tersebut dalam kondisi trafik penuh. Tujuan kedua adalah ketika beberapa kelas tidak menggunakan alokasi bandwidth, distribusi dari kelebihan bandwidth antar kelas lain tidak boleh berubah-ubah tetapi mengikuti aturan tertentu. Floyd dan Jacobson mendefinisikan tujuan dari link-sharing:

1. Setiap interior class atau leaf class harus menerima link-sharing sesuai alokasi yang diberikan dalam interval waktu tertentu, sehingga terpenuhi kebutuhannya.

2. Jika semua leaf dan interior class yang memiliki permintaan telah menerima sedikitnya link-sharing bandwidth yang dialokasikan, distribusi dari kelebihan banwidth tidak berubah-ubah tetapi harus mengikuti aturan yang ditentukan.

Pada sistem operasi Linux yang difungsikan sebagai router, semua paket dimasukkan dalam antrian sebelum paket-paket tersebut diteruskan. Mekanisme dalam antrian tersebut diatur oleh traffic controller sesuai kebutuhan QoS. Traffic Controller hanya memanajemen paket-paket yang akan keluar dari sistem.




Penjadwalan Paket Hierarchical Token Bucket (HTB)

Hierarchical Token Bucket merupakan teknik penjadwalan paket yang dikembangkan pertama kali oleh Martin Devera dan sering digunakan bagi router yang menggunakan sistm operasi Linux. General Scheduler HTB menggunakan mekanisme Deficit Round Robin(DRR) dan pada blok umpan baliknya, Estimator HTB menggunakan Token Bucket Filter (TBF).

a. Token Bucket Filter (TBF)

Token Bucket Filter (TBF) merupakan qdisc yang sederhana dimana qdisc ini hanya meneruskan paket yang datang pada sebuah rate yang tidak melebihi ketentuan rate yang diberikan. Token bucket merupakan suatu definisi formal dari suatu transfer rate. Antrian ini memiliki tiga buah komponen: ukuran burst, mean rate, dan interval waktu (tc). 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 pentingdari 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. Denganmenghubungkan algoritma ini dengan dua aliran – token dan data, maka akan didapatkan tiga buah kemungkinan skenario:

- Data yang datang pada TBF memiliki rate yang sama dengan masuknya token. Dalam hal ini, setiap paket yang masuk memiliki token-nya masing-masing dan akan melewati antrian tanpa adanya delay.

- 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 kemudianakan dapat digunakan untuk mengirimkan data pada kecepatan yang melampaui rate token standar, ini terjadi jika ada ledakan data yang pendek.

- 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 di-drop.

Skenario terakhir ini sangatlah penting, karena dengan skenario tersebut, dapat diterapkan shaping bandwidth yang tersedia terhadap data yang melewati filter. Akumulasi dari semua token mengijinkan sebuah short burst dari data yang overlimit untuk tetap bisa lewat tanpa ada loss tetapi mengakibatkan delay. Perlu diketahui bahwa token pada kernel dalam sistem operasi Linux hanya sesuai dengan satuan bytes, bukan packet.




Mekanisme Kerja Hierarchical Token Bucket

Hierarchical Token Bucket (HTB) menggunakan Token Bucket Filter (TBF) sebagai estimator idle time sehingga hanya rate dan burstsaja yang harus ditentukan. Pada HTB terdapat parameter ceil sehingga kelas akan selalu mendapatkan bandwidth di antara base link dan nilai ceil linknya. 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 link ini (keduanya leaves dan interior dapat memiliki ceil). Apabila nilai ceil sama dengan nilai base rate, maka kelas-kelas tidak diijinkan untuk meminjam bandwidth. Sedangkan jika nilai ceil diset dengannilai tak terbatas atau dengan nilai yang lebih tinggi seperti kecepatan link yang dimiliki, makaakan didapat fungsi yang sama seperti kelas nonbounded. Sebagai contoh, seseorang dapatmenjamin bandwidth 1 Mbit untuk suatu kelas, dan mengijinkan penggunaan bandwidth sampai dengan 2 Mbit pada kelas tersebut apabila link dalam keadaan idle.


b. Penjadwalan Paket Hierarchical Fair Service Curve (HFSC)

Hierarchical Fair Service Curve (HFSC) adalah disiplin antrian atau penjadwalan paket yang bekerja berdasarkan pada konsep dari sebuah service curve yang mendefiniskan persyaratanQoS dari satu kelas trafik atau satu sesi dalam hal bandwidth dan prioritas (delay). Service curve merupakan grafik linear yang merepresentasikan hubungan antara service dengan waktu.


Gambar diatas adalah grafik service curve linear dimana gambar dibawah ini merepresentasikan jaminan bandwidth sebesar 64 Kbps pada waktu yang ditentukan yaitu 20 milidetik dengan garansi paket yang dikirimkan sebesar1280 bits.




Sedangkan gambar 2.8 adalah representasi dari aturan yang menjamin bandwidth sebesar 256 Kbps pada waktu ke 5 milidetik dengan ukuran paket yang dikirimkan sebesar 1280 bits, namunsaat setelah waktu ke 5 milidetik maka bandwidth akan diset pada 64 Kbps.




Service Curve berdasarkan model QoS

Dalam teori algoritma Hierarchical Fair Service Curve (HFSC), service curve bisa memiliki beberapa bentuk, karena HFSC didesain untuk bekerja dengan dua buah linear service curve. Dua buah linear service curve terbentuk dari dua segmen garis lurus. Jika dua buah slope dari dua segmen garis memiliki tingkatkecenderungan derajat yang berbeda, maka akan didapatkan dua buah grafik service curve berbeda yang disebut concave (cembung) dan convex (cekung). Secara umum, sebuah service curve cekung (convex) menghasilkan rata-rata yang rendah dan worst case delay daripada sebuah service curve cembung (concave) dengan rate asimtotik yang sama.




Mekanisme Kerja Hierarchical Fair Service Curve

HFSC bekerja berdasarkan pada konsep “service curve” yang mendefinisikan persyaratan QoS dari sebuah kelas trafik atau single sesi dalam bentuk bandwidth dan prioritas (delay). Setiap kelas diberikan sebuah service curve yang menentukan jumlah mimimal layanan yang harus diterima. Service curve terjamin apabila untuk jumlah service curve semua node subordinat harus kurang dari atau sama dengan root/parent node, aturan ini diaplikasikan secara rekursif dari node root. HFSC menggunakan service curve non-linear agar bandwidth dan komponen delay terpisahkan. Namun dengan service curve non-linear tidak memungkinkan untuk menjamin service curvesecara simultan maka HFSC menggunakan dua kriteria curve dalam pemilihan paket yaitu:

- Kriteria real-time untuk menjaminan service curve untuk semua kelas cabang.

- Kriteria link-sharing untuk menjamin service curve untuk kelas interior danmendisitribusikan kelebihan bandwidth secara adil.

Dalam suatu hierarchy hanya kelas leaf saja yang menjamin layanan terhadap suatu aplikasi,oleh karena itu tiap cabang kelas mempunyai 3 komponen ( ei , di , vi ) yang mewakili eligible time, deadline, dan virtual time. Sedangkan kelasinterior hanya terdiri dari komponen virtual time vi . Konsep utama dalam mekanisme ini adalah pada paket deadline time yang diturunkan dari service curve. Eligible dan deadline mengacu pada kepala suatu paket dalam kelas antrian I sedangkan virtual time meangacu pada suatu kelas i.





Deadline digunakan untuk mencapai tujuan real-time. Deadline time digunakan sebagai perwakilan waktu dari sebuah paket harus memulai pengiriman karena suatu kelas service curve tidak terancam. Suatu deadline time dihitung dari sebuah curve yang menandakan bahwa suatu kelas terjamin secara service curve. Kemudian diset dengan nilai mimimum dari deadline curve sebelumnya dan kelas service curve (dengan nilai jumlah service yang telah diterima dan waktu sebelumnya). Virtual time digunakan untuk mencapai tujuan link sharing. Nilainya mewakili jumlah service suatu node yang telah diterima ketika terjadi penjadwalan dengan kriteria link-sharing. Service yang diberikan kriteria real-time tidak termasuk dalam perhitungan. Virtual time dihitung juga dari kurva yang berkaitan. Kemudian ditentukan ke nilai minimum dari virtual curve sebelumnya dan suatu service curve (dengan nilai dari virtual time dikurangi virtual time parent dantotal service yang diterima oleh link-sharing dan kriteria real-time). Virtual time diperbarui secara rekursif dalam hierarchy sampai mencapai sebuahkelas yang aktif. Virtual curve diperbarui ketika sebuah kelas menjadi aktif. Eligible time digunakan sebagai penengahantara kedua tujuan tersebut yaitu untuk memilih satu dari dua kriteria penjadwal tersebut untuk digunakan dalam paket berikutnya. Ketika ada paket eligible maka kriteria real-time digunakan untuk memastikan bahwa tidak ada service curve yang terancam untuk pengiriman berikutnya. Jika ada kelas-kelas yang eligible maka penjadwal memilih suatu kelas yang mempunyai deadline minimum diatara kelas-kelas eligible. Jika tidak ada kelas eligible maka diterapkan algoritma dengan kriteria link-sharing. Algoritmamenerapakan kriteria link-sharing secara rekursif, dimulai dari bagian root dan berhenti pada cabang kelas, memilih pada tiap level kelas dengan virtual time terkecil. Eligible time dihitung berdasarkan eligible curve. Eligible curve dalamkasus HFSC cukup sederhana, akan bernilai sama dengan deadline curve pada kasus concave curve atau segaris dengan segmen kedua untuk kasus convex curve.