Algoritma Routing

Dalam jaringan komputer, routing adalah proses untuk menentukan jalur komunikasi antara sumbe rdan tujuan dari sebuah paket. Routing adalah fungsi utama dari network layer dalam OSI Reference Model. Pada kebanyakan jaringan komputer, sebuah paket data memerlukan banyak loncatan antarhost untuk mencapai tujuan. Selama terdapat jalur fisik antara kedua mesin, sebuah algoritma routing harus dapatmemastikan bahwa data yang dikirim dari mesin sumber diterima oleh mesin tujuan.Algoritma routing dapat dibagi menjadi dua kelas: nonadaptive dan adaptive. Algoritma nonadaptive tidak mendasarkan keputusan routing pada keadaan lalu lintas data dan topologi jaringan saat ini. Pemilihan jalur komunikasi yang digunakan antarmesin pada algoritma iniditentukan dari awal dan ditanamkan ke router pada saat jaringan diaktifkan. Algoritma routing ini disebut juga static routing. Kebalikannya, algoritma adaptivemenentukan jalur komunikasi berdasar kondisi jaringan saat ini, seperti topologi yang digunakan dan juga kondisilalu lintas data. Algoritma adaptive (dynamic routing) memperoleh informasi untuk proses routing secara lokal, dari router terdekat atau dari semua router yang ada dijaringan. Algoritma routing yang akan dibahas pada makalah ini Backtracking. Dipilihnya backtracking sebagai algoritma routing juga berdasar pertimbangan di atas: efektivitas untuk memperoleh solusi (dalam hal ini routedari sumber ketujuan) dan efisiensi dalam penggunaan sumber daya komputasi. Pada dasarnya, algoritma Backtracking atau runut -balik adalah algoritma yang digunakan untuk mencari solusi yang lebih mangkus dengan berbasis pada algoritma DFS (Depth First Search ). Backtracking bisa dikatakan sebagai perbaikan dari algoritma Brute-Forcedan exhaustive search, yang secara sistematis mencari solusi persoalan di antara semua kemungkinan yang ada. Semua kemungkinan solusi dibuat dalam bentuk pohon ( tree) terlebih dahulu, kemudian dengan menggunakan metode DFS (Depth First Search ) dilakukan pencarian sampai solusi ditemukan. Karena menggunakan DFS, maka proses pencarian tidak memakan banyak waktu. Secara umum, algoritma ini digunakan antara lain untuk menyelesaikan masalah -masalah yang berkembang secara dinamik ( dynamic problem solving ) sehingga digunakan juga sebagai dasar algoritma Artificial Intelligence(inteligensia buatan). Dalam makalah ini akan dibahas mengenai algoritma Backtrackingdan penggunaannya secara umum.

PENGERTIAN ALGORITMA ROUTING

Algoritma routing adalah bagian algoritma dari perangkat lunak network layer yang bertanggung jawab untuk menentukan jalur mana yang menjadi jalur transmisi paket. Jika subnet tersebut menggunakan datagram secara internal, keputusan ini harus selalu dibuat setiap kali paket datang. Tetapi jika subnet tersebut menggunakan rangkaian virtual secara internal, keputusan routing ini hanya diambil pada waktu penetapan rangkaian virtual yang baru, sesudah itu paket data tinggal mengikuti rute yang telah ditetapkan sebelumnya. Setiap algoritma routing memiliki sifat-sifat seperti kebenaran, kesederhanaan, kekokohan, kestabilan, kewajaran dan keoptimalitas. Algoritma routing harus dapat menyesuaikan diri atau bertahan terhadap perubahan-perubahan dalam topologi dan lalu lintas data. 

Algoritma routing dapat dibagi menjadi dua kelas

o Algoritma nonadaptive tidak mendasarkan keputusan routing pada keadaan lalu lintas data dan topologi jaringan saat ini. Pemilihan jalur komunikasi yang digunakan antarmesin pada algoritma iniditentukan dari awal dan ditanamkan ke router pada saat jaringan diaktifkan. Algoritma routing ini disebut juga static routing.

o Algoritma adaptive menentukan jalur komunikasi berdasar kondisi jaringan saat ini, seperti topologi yang digunakan dan juga kondisilalu lintas data. Algoritma adaptive (dynamic routing) memperoleh informasi untuk proses routing secara lokal, dari router terdekat atau dari semua router yang ada dijaringan.Dua hal yang penting yang menguntungkan dari adaptive routing adalah :

1.Strategi routing adaptif dapat meningkatkan performance seperti apa yang keinginan user

2. Strategi adaptif dapat membantu kendali lalulintas. Akan tetapi, strategi ini dapat menimbul-kan beberapa akibat, misalnya :

o Proses pengambilan keputusan untuk menetap-kan rute menjadi sangat rumit akibatnya beban pemrosesan pada jaringan meningkat.

o Pada kebanyakan kasus, strategi adaptif tergantung pada informasi status yang dikumpulkan pada satu tempat tetapi digunakan di tempat lain. Akibatnya beban lalu lintas meningkat.

o Strategi adaptif bisa memunculkan masalah seperti kemacetan apabila reaksi yang terjadi terlampau cepat, atau menjadi tidak relevan apabila reaksi sangat lambat.

 Kategori Strategi Adaptif dapat dibagi menjadi :

- Isolated adaptive : informasi lokal, kendali ter-distribusi.

- Adaptive : informasi dari node yang berdekatan, kendali terdistribusi.

- Adaptive : informasi dari seluruh node, kendali terpusat.

Algoritma Routing terdiri dari dua metode

o Forward Search Algrithm

Forward search algorithm dinyatakan sebagai menentukan jarak terpendek dari node awal yang ditentukan ke setiap node yang ada. Algoritma diungkapkan dalam stage. Dengan k buah stage, jalur terpendek node k terhadap node sumber ditentukan. Node-node ini ada dalam himpunan N. pada stage ke ( k+1 ), node yang tidak ada dalam M yang mempunyai jarak terpendek terhadap sumber ditambahkan ke M. sebagai sebuah node yang ditambahkan dalam M, maka jalur dari sumber menjadi terdefinisi

o Backward Search Algortihm

Menentukan biaya terkecil yang diberikan node tujuan dari semua node yang ada. Algoritma ini juga diproses tiap stage. Pada setiap stage, algoritma menunjuk masing-masing node. Definisi yang digunakan : N = himpunan node yang terdapat pada jaringan. D = node tujuan I ( i,j ) = seperti keterangan di atas. C2 ( n ) = biaya dari jalur biaya terkecil dari n ke D yang dihasilkan ketika algortma dikerjakan.

Backtracking adalah algoritma yang berbasis pada algoritma DFS (Depth-First Search) yang dapat mencari solusi sebuah persoalan dengan lebih mangkus. Algoritma ini dapat menemukan solusi sebuah persoalan tanpa perlu memeriksa semua kemungkinan solusi dan hanya mempertimbangkan pencarian yang mengarah kesolusi.Algoritma Backtracking merupakan algoritma yang berbasiskan DFS (Depth First Search). Yang dilakukan oleh algoritma ini adalah mencari kemungkinan solusi dengan menelusuri hingga node terdalam. Kemudian dilakukan perjalanan kembali dengan melalui node-node calon solusi yang telah dikunjungi untuk menemukan jalur solusi lain yang lebih sesuai. Dengan kata lain, algoritma ini akan melakukan pencarian solusi secara berurutan dari jalur solusi satu ke jalur solusi lain. Namun akan berhenti bila solusi yang sesuai telah ditemukan.