BAB 2 TINJAUAN PUSTAKA

BAB 2 TINJAUAN PUSTAKA

2.1 Algoritma Algoritma adalah setiap prosedure komputasi yang terdefenisi dengan baik yang mengambil beberapa nilai, atau seperangkat nilai-nilai, sebagai masukan dan menghasilkan beberapa nilai, atau seperangkat nilai-nilai sebagai output. Kita juga dapat melihat sebuah algoritma sebagai alat bantu untuk memecahkan masalah (Cormen, 2001). Algoritma adalah urutan langkah-langkah logis penyelesaian masalah yang disusun secara sistematis. Langkah-langkah logis berarti kebenarannya harus dapat ditentukan benar atau salah (Munir, 1999). Menurut Thomason Susabda Ngeon (2004) Algoritma bersifat programming langguage independent. Sebuah algoritma dapat diimplementasikan dengan berbagai bahasa pemrograman, tapi penulisnya tidak tergantung pada bahasa pemrograman tertentu. Algortima dapat disajikan dengan dua teknik yaitu dengan tulisan dan gambar, penyajian algoritma dalam bentuk tulisan biasanya menggunakan metode seperti Bahasa Indonesia Tersetruktur (BIT), pseudocode, spark, Structured English. Sedangkan penyajian algoritma dalam bentuk gambar biasanya menggunakan metode seperti Flowchart, hirarcy plus input-process-output (HIPO) chart, structured chart dan nassi schneiderman chart. Sedangkan menurut kamus besar bahasa indonesia terbitan balai pustaka, Departemen Pendidikan Nasional, edisi ketiga tahun 2007, algoritma adalah prosedure sistematis untuk memecahkan masalah

matematis dalam langkah-langkah terbatas.

Masalah merupakan sesuatu yang harus diselesaikan. Pernyataan masalah menentukan secara umum yang dinginkan pada hubungan input/output, dan algoritma menggambarkan procedure komputasi tertentu utuk mencapai yang hubungan intput/output.

Universita Sumatera Utara

5

Pada ilmu komputer yang sering dipertanyakan adalah bukan bagaimana menyelesaikan suatu persoalan(problem), melainkan bagaimana menyelesaikan persoalan dengan baik (efisien), sebagai contoh adalah bagaimana mengatasi permasalahan manajemen bandwidth internet sehingga tidak terjadi overload atau client saling berebut bandwidth. Ada beberapa teknik yang dilakukan untuk menangani hal tersebut diatas, namun yang menjadi permasalahan bukanlah menemukan bagaimana cara mengefisiensi bandwidth yang sudah ada melainkan menambah kapasistasnya untuk memenuhi kebutuan user. 2.1.1 Algoritma Pencarian (Searching Algorithm) Pencarian(searhing) merupakan proses yang fundamental dalam pengolahan data. Proses pencarian adalah menemukan nilai(data) tertentu didalam sekumpulan data yang bertipe sama (baik bertipe dasar maupun bertipe bentukan). Sebuah algoritma pencarian dijelaskan secara luas adalah sebuah algoritma yang menerima masukan berupa sebuah masalah dan menghasilkan sebuah solusi untuk masalah tersebut, yang biasanya didapat dari evaluasi beberapa kemungkinan solusi. Algoritma pencarian (searching algorithm) adalah algoritma yang menerima sebuah argumen kunci dan dengan langkah-langkah tertentu akan mencari rekaman dengan kunci tersebut. Setelah proses pencarian dilaksanakan, akan diperoleh salah satu dari dua kemungkinan, yaitu data yang dicari ditemukan (successful) atau tidak ditemukan (unsuccessful) 2.1.2 Algoritma Pengurutan (Sorting Algorithm) Pengurutan data (sorting) didefinisikan sebagai suatu proses untuk menyusun kembali himpunan obyek menggunakan aturan tertentu. Menurut Microsoft book-shelf, definisi algoritma pengurutan adalah algoritma untuk meletakkan kumpulan elemen data ke dalam urutan tertentu berdasarkan satu atau beberapa kunci dalam tiap-tiap elemen. Ada dua macam urutan yang biasa digunakan dalam proses pengurutan yaitu urut naik (ascending) yaitu dari data yang mempunyai nilai paling kecil sampai paling

besar

urut turun

(descending) yaitu data yang mempunyai nilai paling besar sampai paling kecil. Data yang diurutkan sangat bervariasi, dalam hal jumlah data maupun jenis data yang akan diurutkan. Tidak ada algoritma terbaik untuk setiap situasi yang kita hadapi,


6

bahkan cukup sulit untuk menentukan algoritma mana yang paling baik untuk situasi tertentu karena ada beberapa faktor yang mempengaruhi efektifitas algoritma pengurutan. Beberapa faktor yang berpengaruh pada efektifitas suatu algoritma pengurutan antara lain, banyak data yang diurutkan, kapasitas pengingat apakah mampu menyimpan semua data yang kita miliki, tempat penyimpanan data, misalnya piringan, pita atau kartu, atau media menyimpan yang lain. 2.1.3 Algoritma Per Connection Queue (PCQ) Algoritma pembagian bandwidth dengan (PCQ) prinsipnya menggunakan metode antrian untuk menyamakan bandwidth yang dipakai pada multiple user. Didalam mikrotik PCQ sudah terinstal default dan merupakan program untuk mengatur traffic jaringan Quality of Service (QoS). Untuk

memecahkan beberapa imperfectness SFQ,

Per Connection

Queuing (PCQ) diciptakan. Ini adalah satu-satunya. Antrian tanpa kelas jenis yang dapat melakukan pembatasan. Ini adalah versi perbaikan dari SFQ tanpa stohasticnya alam. PCQ juga menciptakan subqueues, mengenai parameter pcqclassifier. PCQ juga menciptakan subqueues, mengenai parameter pcqclassifier, Subqueue masing-masing memiliki data rate batas pcq-rate dan ukuran pcq-limit paket. Ukuran total antrian PCQ tidak dapat lebih besar dari pcq-total-limit paket. (Herlambang, 2008). 2.1.4 Algoritma Hierarchical Token Bucket (HTB) Algoritma antrian HTB mirip dengan CBQ, perbedaannya terletak pada jenis pilihan yang disediakan. HTB memiliki lebih sedikit pilihan saat konfigurasi dan lebih presisi. Teknik antrian HTB memberikan fasilitas pembatasan traffic pada setiap level maupun klasifikasi, bandwidth yang tidak terpakai bisa digunakan oleh klasifikasi yang lebih rendah. Susunan HTB dapat dilihat seperti suatu struktur organisasi dimana pada setiap bagian memiliki wewenang

dan mampu membantu bagian lain yang memerlukan.

Algoritma antrian HTB cocok diterapkan pada

perusahaan dengan banyak struktur

organisasi. Algoritma HTB mempunyai dua parameter yakni: (Herlambang, 2008)


7

1.

Rate, yaitu parameter untuk menentukan bandwidth maksimum yang bisa dipakai oleh setiap class, jika bandwidth melebihi nilai “rate” maka paket data akan dipotong atau ditanggalkan (drop).

2.

Ceil, yaitu parameter untuk menentukan peminjaman bandwidth antar class (kelas), peminjaman bandwidth dilakukan oleh class lebih rendah ke kelas di atasnya, teknik ini disebut link sharing.

2.1.5. Algoritma Penjadwalan FIFO Salah satu algoritma penjadwalan antrian yang sering digunakan adalah FIFO (First In First Out) dari paket yang terkirim, dalam hal ini paket akan terbuffer dan mengantri dan menghasilkan waktu tunda pada jaringan. Data yang dikirimkan membentuk paket-paket yang dikirim kesetiap node, dan memiliki latensi yang berbeda kesetiap node sehingga mempengaruhi kecepatan transfer data.

Gambar 2.1. FIFO (sumber : www.digilib.ittelkom.ac.id) Gambar diatas menunjukkan kedatangan beberapa paket dengan berbeda waktu, paket pertama dari flow delapan tiba lebih awal dikeluarkan ke port terlebih dahulu oleh antrian.


8

2.1.6. Algoritma Penjadwalan Round-Robin Konsep dasar algoritma ini adalah dengan menggunakan time sharing. Pada dasarnya algoritma ini sama dengan Algoritma FCFS, hanya saja bersifat preemptive, setiap proses mendapatkan waktu CPU yang disebut dengan waktu quantum (quantum time) untuk membatasi waktu proses. Setelah waktu habis, proses ditunda dan ditambahkan pada ready queue. Jika suatu proses memiliki CPU burst lebih kecil dibandingkan dengan waktu quantum, maka proses tersebut akan melepaskan CPU jika telah selesai bekerja, sehingga CPU dapat segera digunakan oleh proses selanjutnya. Sebaliknya, jika suatu proses memiliki CPU burst yang lebih besar dibandingkan dengan waktu quantum, maka proses tersebut akan dihentikan sementara jika sudah mencapai waktu quantum, dan selanjutnya mengantri kembali pada posisi ekor dari ready queue, CPU kemudian menjalankan proses berikutnya. (Abas & Doni, 2008). 2.1.7. Algoritma SJF (Shortest Job First) Pada algoritma ini setiap proses yang ada di ready queue akan dieksekusi berdasarkan burst time terkecil. Hal ini mengakibatkan waiting time yang pendek untuk setiap proses dan karena hal tersebut maka waiting time rata-ratanya juga menjadi pendek. (Abas, Dony, 2008) Algoritma SJF terdiri dari dua skema yakni : 1.

Non preemtive, bila CPU diberikan pada proses, maka tidak bisa ditunda sampai CPU burst selesai.

2.

Preemtive, jika proses baru datang dengan panjang CPU burst lebih pendek dari sisa waktu proses yang saat itu sedang dieksekusi, proses ini ditunda dan diganti dengan proses baru. Skema ini disebut dengan Shortest-Remaining-Time-First (SRTF).

2.1.8. Algoritma HRN (Higest Ratio Next) Higest Ratio Next (HRN) Merupakan penjadwalan untuk mengoreksi kelemahan SJF yang berprioritas dinamis. HRN Adalah strategi penjadwalan dengan prioritas proses tidak


9

hanya merupakan fungsi waktu layanan,tetapi juga jumlah waktu tunggu proses. Begitu proses mendapat jatah pemroses, maka proses berjalan sampai selesai. Prioritas dinamis HRN dihitung berdasarkan rumus berikut : Prioritas = (waktu tunggu + waktu layanan ) / waktu layanan. Karena waktu layanan muncul sebagai pembagi, maka job lebih pendek berprioritas lebih baik, karena waktu tunggu sebagai pembilang, maka proses yang telah menunggu lebih lama juga mempunyai kesempatan lebih bagus. Mengapa algoritma ini disebut HRN karena waktu tunggu ditambah waktu layanan adalah waktu tanggap, yang berarti waktu tanggap tertinggi yang harus dilayani 2.1.9. Algoritma Multilevel Queue Scheduller Pada perakteknya algoritma ini memungkinkan adanya penerapan algoritma internal dalam masing-masing sub-antriannya yang bisa memiliki algoritma internal yang berbeda untuk meningkatkan kinerjanya. Algoritma ini pun memiliki kelemahan yang sama dengan priority scheduling, yaitu sangat mungkin bahwa suatu proses pada queue dengan prioritas rendah bisa saja tidak mendapat jatah. Untuk mengatasi hal tersebut, salah satu caranya adalah dengan memodifikasi algoritma ini dengan adanya jatah waktu maksimal untuk tiap antrian, sehingga jika suatu antrian memakan terlalu banyak waktu, maka prosesnya akan dihentikan dan digantikan oleh antrian dibawahnya, dan tentu saja batas waktu untuk tiap antrian bisa saja sangat berbeda tergantung pada prioritas masing-masing antrian. (Ibas, Dony. 2008) 2.1.10. Algoritma Penjadwalan Weighted Round Robin (WRR) Algoritma penjadwalan WRR merupakan pengembangan dari algoritma Round Robin (RR) yang sebenarnya diusulkan untuk jaringan ATM yang mempunyai ukuran paket tetap. WRR adalah sebuah algoritma penjadwalan yang dapat diterapkan pada berbagai bidang, untuk pemakaian sumber daya secara bersama-sama pada sebuah komputer atau jaringan. Algoritma ini dieksekusi atau dijalankan pada permulaan dari setiap frame pada Base Station (BS). Pada permulaan frame, algoritma WRR menentukan alokasi bandwidth


10

diantara SS berdasarkan pada bobotnya (weight). Bagian yang kritis dari skema WRR adalah menentukan bobot untuk setiap SS. Bobot tersebut ditentukan untuk menggambarkan prioritas relatif dan kebutuhan QoS dari SS. Selama minimum reserved traffick rate (MRTR) (Sukiswo, 2008). 2.1.11. Algoritma Timer Multilevel Queue Scheduller (TMQS) Algoritma ini diusulkan untuk mengembangkan algoritma Multilevel Queue Schedulling, TMQS merupakan algoritma penjadwalan yang dapat diterapkan di berbagai bidang, untuk pemakaian sumber daya secara bersama-sama pada sebuah komputer server atau jaringan. Algoritma TMQS ini nantinya bekerja dengan menentukan batas waktu proses maksimal pada antrian berdasarkan jadwal yang sudah ditentukan. Algoritma ini akan dijalankan atau dieksekusi pada permulaan setiap pengguna internet melakukan akses internet, Algoritma TMQS akan menentukan pengguna bandwidth internet sesuai dengan jadwal dan prioritasnya masing-masing. Untuk penjelasan dari algoritma dan alur programnya penulis akan menjelaskan pada bagian bab berikutnya. 2.2. Router Dalam suatu jaringan internet router salah satu alat/software yang sangat dibutuhkan, karena dari fungsinya untuk mengarahkan paket data atau informasi dari suatu jaringan ke jaringan yang lain. Ketika sebuah data paket yang dikirimkan dari jaringan, router dalam hal ini berguna untuk mengarahkan ke lokasi yang diperkulan melalui rute terbaik untuk mentransfer data tertentu. Ada dua buah jenis router secara umum, yaitu sebagai berikut. 1. Static router (router statis), yaitu sebuah router yang mempunyai tabel routing statis dan disetting secara manual oleh para administrator jaringan. 2. Dynamic router (router dinamis), yaitu sebuah router yang memiliki dan membuat tabel routing dinamis dengan mendengarkan lalu lintas jaringan dan juga saling berhubungan dengan router lain.


11

2.3. Bandwidth Bandwidth adalah kapasitas atau daya tampung kabel ethernet untuk dapat dilewati traffic paket data dalam jumlah tertentu. Bandwidth juga bisa berarti jumlah konsumsi paket data per satuan waktu dinyatakan dengan satuan bytes per second [bps]. Bandwidth Internet disediakan oleh Internet Service Provider (ISP) dengan jumlah tertentu tergantung permintaan pelanggan. Istilah bandwidth muncul dari bidang teknik elektro, dimana bandwidth mempresentasikan jarak keseluruhan atau jangkauan diantara sinyal tertinggi dan terendah pada kanal (band) komunikasi. Pada dasarnya bandwidth mempresentasikan kapasitas dari koneksi, semakin tinggi kapasitas, maka umumnya akan diikuti oleh kinerja yang lebih baik, meskipun kinerja keseluruhan juga tergantung pada faktor-faktor lain, misalnya latency yaitu waktu tunda antara masa sebuah perangkat meminta akses ke jaringan dan masa perangkat itu memberi izin untuk melakukan transmisi. (Tanenbaum, 2003) Menurut Cisco System, 2003 Bandwidth merupakan salah satu faktor penting dalam jaringan. Beberapa hal yang menyebabkan bandwidth menjadi bagian penting yang harus diperhatikan adalah: a.

Bandwidth berdampak pada kinerja sebuah jaringan. Besarnya saluran atau bandwidth akan berdampak pada kecepatan transmisi. Data dalam jumlah besar akan menempuh saluran yang memiliki bandwidth kecil lebih lama dibandingkan melewati saluran yang memiliki bandwidth yang besar. Kecepatan transmisi tersebut sangat dibutuhkan untuk aplikasi komputer yang memerlukan jaringan terutama aplikasi real-time, seperti videoconferencing.

b. Bandwidth memiliki keterbatasan Bandwidth dibatasi oleh hukum fisika dan teknologi yang diterapkan pada medium yang digunakan. Setiap medium yang digunakan untuk mentransmisikan data memiliki batas maksimal bandwidth yang dapat dicapai.


12

c.

Kebutuhan akan bandwidth akan selalu naik Setiap sebuah teknologi jaringan baru dikembangkan dan infrastruktur jaringan yang ada diperbaharui, aplikasi yang akan digunakan umumnya juga akan mengalami peningkatan dalam hal konsumsi bandwidth. Video streaming dan Voice over IP (VoIP) adalah beberapa contoh penggunaan teknologi baru yang turut mengkonsumsi bandwidth dalam jumlah besar.

2.4 Pengaturan Bandwidth Penggunaan internet secara bersamaan pastinya mempengaruhi bandwidth dan kecepatan transfer data antar komputer dalam suatu jaringan Local Area Network (LAN), oleh karena itu diperlukan yang namanya pengaturan bandwidth (management bandwidth), server akan melakukan pembagian bandwidth kepada client agar tidak terjadi penguasaan bandwidth. Tanpa pengaturan bandwidth setiap client akan secara otomatis memperluas bandwidthnya sesuai dengan kebutuhannya, sehingga memperlambat akses ke komputer client yang lain. Layanan

jaringan

internet

yang

kompleks

akan

menimbulkan tantangan yang besar untuk menata dan mengontrol keakuratan sejumlah aplikasi

yang

baru,

seperti

video

streaming

Aplikasi ini mengkonsumsi bandwidth yang cukup besar

dan

game

online.

dan mempengaruhi kinerja

jaringan terutama di jaringan bandwidth yang terbatas seperti kampus atau universitas, hal ini menyebabkan penurunan kinerja aplikasi yang lain. Perlunya pengklasifikasian yang akurat untuk penggunaan bandwidth seperti video streaming dan game online, hal ini dapat digunakan kemudian dapat dikontrol trafficnya, kapasitas yang direncanakan maupun perhitungan penggunaan yang secara tidak langsung dapat

memberikan

kontribusi

yang

signifikan

pada

peningkatan

kinerja jaringan. (Abuagla Babiker Mohd & Dr. Sulaiman bin Mohd Nor, 2010)


13

2.5. Cara Pengaturan Bandwidth Banyak cara yang dilakukan untuk menangani pengaturan bandwidth internet, namun tidak semua cocok penerapannya pada suatu tempat, mungkin karena alasan terntu, berikut beberapa cara untuk pengaturan bandwidth internet :

2.5.1. Pembatasan Transfer Data Pengaturan bandwidth dilakukan dengan memberikan batasan pada kecepatan transfer data. Setiap pengguna diberikan batasan tertentu tergantung daripada kebutuhan dan kemampuan user itu sendiri.

2.5.2. Pembagian Secara Merata Pembagian secara merata ini dapat diartikan dengan cara menghitung jumlah client kemudian membagi bandwith denga merata, sehingga dengan cara ini tidak ada user yang terprioritaskan, dengan rumus dapat digambarkan sebagai berikut : = Dimana B adalah Bandwith untuk tiap pengguna, TB dalah total bandwidth yang diterima dari ISP, dan U adalah jumlah user yang menggunakan akses internet. 2.5.3. Pembagian dengan Memberikan Paket (Limiter) Pembagian dengan cara ini umumnya dilakukan oleh ISP, dengan cara ini pengguna lebih leluasa memilih kecepatan akses seuai dengan keuangan mereka, selain dari pada itu kecepatan internet dapat tetap terjaga. Namun kelemahan dari cara ini terdapat bandwidth yang tidak digunakan.

2.6. Pembatasan User Untuk menghindari overload bandwith akibat kebanayakan user yang mengakses internet, mengingat kuota bandwidth internet yang tersedia sudah tertentu, dalam hal ini perlu


14

dilakukan penjadwalan penggunaan akses internet, apakah dilakukan secara per user atau group user tergantung dari pada kapasitas bandwidth yang tersedia. Selain dari pada hal diatas pembatasan user pada jam kerja karyawan pada perkantoran perlu dilakukan untuk meningkatkan efisiensi kerja para karyawan, mungkin hal ini perlu diterapkan ditempat-tempat yang lain juga. 2.7. Pembagian Berprioritas Pembagian dengan cara ini bertujuan untuk memberikan bandwidth yang lebar/besar kepada user yang dianggap paling membutuhkan pada jadwal (waktu) yang sudah ditentukan, dalam penelitian ini akan dikategorikan dengan 3 tingkatan yakni low (rendah), midle(menengah), hight (tinggi).

2.8. Riset-riset Terkait 2.8.1 Riset Terdahulu Dalam penelitian ini penulis mendapat banyak masukan-masukan dari riset-riset yang terdahulu, sehingga dalam hal ini penulis sangat tertarik untuk mengembangkan lebih dari yang sudah di buat oleh peneliti terdahulu, dari yang penulis baca hampir semua peneliti terdahulu memfokuskan penelitiannya ke arah optimasi kuota bandwidth yang ada dan menmbatasi bandwidth secara konstanta kepada pengguna bandwidth itu sendiri, sehingga tidak ada elastisitas dalam penggunaan bandwidth itu sendiri. Alokasi bandwidth dan routing merupakan dua mekanisme yang penting dalam penyediaan jaminan QoS di jaringan nirkabel. QoS penyediaan algoritma yang dikembangkan dalam jaringan mobile ad hoc tidak bisa diterapkan langsung dalam jaringan wireles mesh, karena WIMAX berbasis jaringan yang memiliki karakteristik yang berbeda. Untuk memecahkan masalah routing dan alokasi sumber daya, kami mengusulkan untukdesain routing dan protocol bersamaan dalam alokasi bandwidth untuk jaringan WIMAX. (R Murali Prasad and P.Satish Kumar. 2010) Berikut ini penulis akan tampilkan dalam bentuk tabel, tentang riset-riset terdahulu yang penulis kutib dari beberapa sumber :


15

Tabel 2.1. Daftar riset-riset terdahulu Nama Imam Riadi

Sandy Arjuni

Benjamin Anthon Balukh

Sukiswo Abuagla Babiker Mohd & Dr. Sulaiman bin Mohd Nor R Murali Prasad and P.Satish Kumar

Judul

Keterangan

Optimasi bandwidth menggunakan traffic shaping Perancangan Implementasi Proxy Server dan Manajemen Bandwidth menggunakan Linux Ubuntu. Analisa Log dan Metode Cache Replacement untuk Optimalisasi Proxy Server Evaluasi Kinerja Algoritma Penjadwalan Weighted Round Robin Pada Wimax Towards a Flow-based internet Traffic Classification for Bandwidth Optimization A Joint Routing and Bandwidth Allocation Protocol for IEEE 802.16 WiMax Mesh Networks

Jurnal Informatika Vol. 4, 2010 Jurnal Informatika, 2011

Jurnal Informatika, 2010

Jurnal Teknik Elektro Vol. 10, 2008 , International Journal of Computer Science and Security (IJCSS IACSIT International Journal of Engineering and Technology, Vol.2

2.8.2 Perbedaan Penelitian Perbedaan penelitian terdahulu dengan yang penulis lakukan saat ini terletak pada proses penjadwalan pengguna bandwidth, dari beberapa riset yang penulis pelajari bahwa penulis terfokus kepada optimalisasi quota bandwidth internet saja seperti pemisahan traffic international dan nasional, caching (penyimpanan cache) Sementara dalam penelitian ini penulis memodifikasi algoritma untuk pengaturan pengguna bandwidth internet dengan memberikan jadwal dan perioritasnya, dimana penulis akan memberikan prioritas pemakaian bandwidth internet ke user atau group user sekaligus mengatur jadwalnya 2.8.3 Kontribusi yang diberikan Dengan adanya pengembangan algoritma ini kontribusi yang dapat diberikan khususnya kepada STMIK Kristen Neumann Indonesia, dapat mengatasi apa yang menjadi kendala terhadap koneksi in internet yang ada saat ini, mengingat banyak jumlah user yang mengakses

internet

tidak

sebanding

dengan

quota

bandwidth

yang

tersedia.


BAB 2 TINJAUAN PUSTAKA

Recommend Documents