Pengertian dan Pembahasan ALGORITMA ROUTING

Advertisement

Rekomendasi

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 data datang. Tetapi, jika subnet tersebut menggunakan rangkaian virtual secara internal , keputusan routing ini hanya akan dibuat pada waktu penetapan rangkaian virtual yang terbaru. Sesudah itu, paket data tinggal mengikuti rute yang telah ditetapkan sebelumnya.

Setiap algoritma routing memiliki sifat-sifat seperti kebenaran, kesederhanaan, kekokohan, kestabilan,kewajaran, dan optimalitas. Algoritma routing harus dapat menyesuaikan diri atau bertahan terhadap perubahan-perubahan dalam topologi dan lalu lintas data.

Untuk mencari rute dengan biaya minimum, dapat digunakan dua metode yaitu metode forward search agorithm dan backword search algorithm.

2.1.1.Forward Search Algorithm

Forward Search Algorithm digunakan untuk menentukan jarak terpendek dari node awal yang ditentukan ke setiap node yang ada. Algoritma diungkapkan dalam stage. Dengan k buah 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 yng mempunyai jarak terpendek terhadap sumber ditambahkan ke M. Sebagai sebuah node yang di tembarvkan dalam M, maka jalur dari sumber menjadi terdefinisi (Gambar 5.4). Algoritma ini memiliki 3 tahapan:

1. Tetapkan M={S). Untuk setiap node neN-S, tetapkan C1(n)=1(S,n).
2. Cari WeN-M sehingga C1(W0 minimum dan tambahkan ke M. Kemudian C1 (n) = MIN[C1(n), C1(W) + 1(W,n) untuk tiap node neN-M. Apabila pernyataan terakhir bernilai minimunv, jalur dari S ke n sebagai jalur S ke W menotong Jink dari W ke n.
3. Ulang langkah 2 sampai M=N. Keterangan:

• N = himpunan node dalam jaringan
• S = node sumber
• M = himpunan node yang dihasilkan oleh algoritma
• 1 (I,J) = link cost dari node I sampai node ke }, biaya bernilai > jika node tidak secara langsung terhubung.
• C1(n) = biaya daru jalur biaya terkecil dari S ke n yang dihasilkan pada saat algoritma dikerjakan.

Untuk memperjelas dari penggunaan forward search algorithm, perhatikan Gambar.4 yang menjelaskan rute jaringan yang menghubungkan 6 titik (node).

Gambar .4 Rute Jaringan Pada 6 Titik

Dengan menggunakan S=1 dan berdasarkan gambar diatas, diperoleh hasil dari forward search algorithm yang tertuang pada Gambar 5.5.

Gambar .5 Hasil Forward Searc Algoritm

2.1.1.Backward Search Algorithm

Digunakan untuk menentukan jalur biaya terkecil yang diberikan node tujuan dari semua node yang ada (Gambar 5.6). Algoritma ini juga diproses tiap St&ge. Pada tiap stage, algoritma menunjuk masing-masing node.

Devinisi yang digunakan:

• N = Himpunan node yang terdapat pada jaringan
• D = node tujuan
• 1(i,j) = seperti keterangan diatas
• C2(n) = biaya dari jalur biaya terkecil dari n ke D yang dihasilkan saat algoritma dikerjakan.

Algoritma ini juga terdiri dari 3 tahapan:

1. Tetapkan C2(D)=0. Untuk tiap node neN-D, tetapkan C2(n)=8.
2. Untuk tiap node neN-D, tetapkan C2(n)=MIN WN[C2(N), C2(W) + 1(n,W)]. Apabila pada pernyataan terakhir bernilai minimum, maka jalur dari n ke D saat ini merupakan link dari n ke W dan menggantikan jalur dari W ke D.
3. Ulangi langkah ke-2 sampai tidak ad cost yang berubah.

Gambar 5.6 berikut ini adalah hasil pengolahan Gambar 5.4 dengan D=1.

Gambar .6 Hasil Backward Search Algoritm

2.2 Strategi Routing

Dalam mencari rute bagi paket yang dikirim dari komputer sumber ke komputer tujuan ada beberapa strategi yang dipakai. Strategi itu meliputi fixed routing, flooding, random routing, dan adaptive routing.

2.2.1 Fixed Routing

Merupakan cara routing yang paling sederhana. Dalam hal ini rute bersifat tetap atau paling tidak, rute hanya diubah apabila topologi jaringan berubah. Gambar 5.7 berikut (mengacu dari Gambar 5.4) memperlihatkan bagaimana sebuah rute yang tetap dikonfigurasikan.

Gambar .7 Direktori Untuk Fixed Routing

Kemungkinan rute yang bisa dikonfogurasikan, dirunjukkan pada Gambar .8 sebagai berikut:

Gambar .8 Direktori Untuk Masing-Masing Node

Tabel pada Gambar 5.8 disusun berdasarkan rute terpendek dengan menggunakan least-cost algorithm. Sebagai misal direktori node 1. Dari node 1 untuk mencapai node 6, maka rute terpendek yang bisa dilewati adalah rute dari node 1,4,5,6. Maka pada tabel direktori node 1 dituliskan destination = 6, dan next node = 4.

Keuntungan konfigurasi dengan rute tetap semacam ini adalah bahwa konfigurasi menjadi sederhana. Penggunaan sirkuit aya atau datagram tidak dibedakan. Artinya semua paket dari sumber menuju titik tujuan akan melewati rute yang sama . kinerja yang bagus terdapat apabila beban bersifat tetap. Tetapi pada beban yang bersifat dinamis, kinerja menjadi turun. Sistem ini tidak memberi tanggapan apabila terjai error maupun kemacetan jalur.

2.2.2 Flooding

Teknik routing yang lain yang dirasa sederhana adalah flooding. Cara kerja teknisi ini adalah mengirimkan paket dari suatu sumber ke seluruh node tetangganya. Pada tiap ode, setiap paket yang datang akan ditransmisikan kembali ke seluruh link yang dipunyai kecuali link yang dipakai untuk menerima paket tersebut. Mengambil dari contoh yang sama, sebutlah bahwa node 1 akan mengirimkan paketnya ke node 6. Pertama kali node 1 akan mengirimkan paket ke seluruh tetangganya, yakni ke node 2, node 4 dan node 5 (Gambar 5.9).

Selanjutnya operasi terjadi pada node 2, node 3 dan node 4. Node 2 mengirimkan paket ke tetangganya yaitu node 3 dan node 4. Sedangkan node 3 meneruskan paket ke node 2, node 4, node 5 dan node 6. Node 4 meneruskan paker ke node 2, node 3, node 5. Semua node ini tidak mengirimkan paket ke node 1. Ilustrasi tersebut digambarkan pada Gambar 5.10.

Gambar 5.9 Hop Pertama

Gambar 5.10 Hop Kedua

Pada saat ini jumlah salinan yang diciptakan berjumlah 9 buah. Paket-paket yang sampai ketitik tujuan, yakni node 6, tidak lagi diteruskan. Posisi terakhir node-node yang menerima paket dan harus meneruskan adalah node 2, node 3, node 4, node 5. Dengan cara yang sama masing-masing node tersebut membuat saiman yang memberikan dan ke node tetangganya. Pada saat ini ainasilkan salinan sebanyak 22 (lihat Gambar 5.11).

Gambar 5.11 Hop Ketiga

Terdapat dua catatan penting dengan penggunaan teknik flooding ini, yaitu:

1. Semua rute yang dimungkinkan akan dicoba. Karena itu teknik ini memiliki keandalan yang tinggi dan cenderung memberi rioritas untuk pengiriman-pengiriman paket tertentu.
2. Karena keseluruhan rute dicoba, maka akan muncul paling tidak satu buah salinan paket dititik tujuan dengan waktu paling minimum. Tetapi hal ini akan menyebabkan naiknya beban lalu lintas yang pada akhirnya menambah delay bagi rute-rute secara keseluruhan.

2.2.3 Random Routing

Prinip utama dari teknik ini adalah sebuah node memiliki hanya satu jalur keluaran untuk menyalurkan paket yang datang kepadanya. Pemilihan terhadap sebuah jalur keluaran bersifat acak. Apabila link yang akan dipilih memiliki bobot yang sama, maka bisa dilakukan dengan pendekatan seperti teknik round robin.

Routing ini adalah untuk mencari probabilitas untuk tiap-tiap outgoing link dan memilih link berdasarkan nilai probabilitasnya. Probabilitas bisa dicari berasarkan data rate, dalam kasus ini didefinisikan sebagai berikut:

Dimana:
Pi = probabilitas pemilihan i
Rj = data rate pada link j

Penjumlahan dilakukan untuk keseluruhan link outgoing. Skema seperti ini memungkinkan distribusi lalu lintas yang baik. Seperti teknik flooding, random routing tidak memerlukan informasi jaringan, karena route akan dipilih dengan cara random.

2.2.4 Adaptive Routing

Strategi routing yang dibahas di depan, tidak mempunyai reaksi terhadapperubahan kondisi yang terjadi didalam suatu jaringan. Untuk itu pendekatan dengan atrategi adaptif mempunyai kemampuan yang lebih dibandingkan dengan beberapa hal di atas.

Dua hal yang penting yang menguntungkan adalah:

• Strategi routing adaptif dapat meningkatkan kinerja seperti apa yang diinginkan user.
• Strategiadaptif dapat membantu kendali lalu lintas.

Akan tetapi, strategi ini dapat menimbulkan beberapa akibat, misalnya:

• Proses pengambilan keputusan untuk menetapkan rute menjadi sangat rumit akibatnya beban pemrosesan pada jaringan meningkat.
• Pada kebnyakan kasus, strategi adaptif tergntung pada informasi status yang dikumpulkan pada satu tempat tetapi digunakan ditempat lain. Akibatnya beban lalu lintas meningkat.
• Strategi adaptif bisa memunculkan masalah seperti kemacetan apabila reaksi yang terjadi terlampau cepat, atau menjadi tida relevan apabila reaksi sangat lambat.

3. kemacetan

Bila terlalu banyak paket yang berada di dalam subnet, maka unjuk kerja jaringan akan mengalami penurunan (Gambar 5.12). situasi seperti ini disebut keacetan (congestion). Bila jumlah paket yag mengalir ke dalam subnet daru host masih berasa dalam daya tampungnya, paket-paket tersebut seluruhnya akan dihantarkan. Jumlah paket yang dihantarkan proporsional dengan jumlah paket yang dikirimkan. Akan tetapi dengan semakin meningkatnya lalu lintas, router tidak mampu lagi menangani paket yang datang dan router akan memulai kahilangan paket.

Gambar .12 Kemacetan

Kemacetan bisa disebabkan oleh beberapa faktor. Bila semuanya terjadi dengan tiba-tiba , aliran paket yang datang pada tiga atau empat saluran input dan semuanya memerlukan saluran output yang sama, maka antrian mulai membesar. Bila tidak terdapat memori yang cukup untuk menampung seluruh antrian, maka paket akan hilang.

Proses yang lambat juga dapat menimbulkan kemacetan. Bila CPU router lambat dalam melakukan tugas yang diperlukan, antrian akan menjadi semakin panjang. Permasalahan yang serius yang diakibatkan efek congestion adalah deadlock, yaitu suatu kondisi dimana sekelompok node tidak bisa meneruskan pengiriman paket karena tidak ada buffer yang tersedia. Trknik deadlock avoidance digunakan untuk merancang jaringan sehingga deadlock tidak terjadi.

Bentuk deadlock yang paling sederhana adalah direct store-and-forward deadlock. Pada Gambar 5.13 memperlihatkan situasi bagaimana antara node A dan node B berinteraksi di mana kedua buffer penuh dan deadlock terjadi.

Gambar .13 Direct store and forward deadlock

Bentuk deadlock kedua adalah indirect store-and-forward eadlock (Gambar 5.14). hal ini terjadi tidak pada sebuah link tunggal seperti bentuk deadlock di atas. ^pada tiap node, antrian yang ditujukan untuk node terdekatnya bersifat searah dan J menjadi penuh.

Gambar .14 Inderect stote and forward deadlock

Bentuk deadlock yang ketiga adalah reassembly deadlock. Situasi ini digambarkan pada Gambar 5.15 dimana node C memiliki 4 paket terdiri dari paket 1 tiga buah dan sebuah paket 3. Seluruh buffer penuh dan tidak lagi menerima paket baru.

Gambar .15 Reassembly deadlock

[ baca berikutnya > INTER NETWORKING >