Pemilihan Route (Routing) Pada Network Layer
Network Layer
Pemilihan Route (Routing)
Salah satu fungsi dari network layer adalah mencari rute untuk jalur transmisi paket data dari komputer sumber ke komputer tujuan. Dalam sebagian besar subnet, paket-paket data akan memerlukan banyak lompatan dalam melakukan perjalanan. Algoritma yang memilih rute dan struktur data yang digunakan jaringan merupakan masalah utama rancangan network layer.
1. 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.
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 1).
Algoritma ini memiliki 3 tahapan:
- Tetapkan M={S). Untuk setiap node neN-S, tetapkan C1(n)=1(S,n).
- 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.
- 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 1 yang menjelaskan rute jaringan yang menghubungkan 6 titik (node).
Dengan menggunakan S=1 dan berdasarkan gambar di atas, diperoleh hasil dari forward search algorithm yang tertuang pada tabel 1.
Tabel 1. Hasil Forward Searc Algoritm
- 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.
- Tetapkan C2(D)=0. Untuk tiap node neN-D, tetapkan C2(n)=8.
- 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.
- Ulangi langkah ke-2 sampai tidak ad cost yang berubah. Tabel 2 berikut ini adalah hasil pengolahan Gambar 1 dengan D=1.
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.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. Tabel 3 berikut (mengacu dari Gambar 1) memperlihatkan bagaimana sebuah rute yang tetap dikonfigurasikan.
Tabel 3. Direktori Untuk Fixed Routing
Kemungkinan rute yang bisa dikonfogurasikan, dirunjukkan pada Tabel 4 sebagai berikut:
Tabel 4. Direktori Untuk Masing-Masing Node
Tabel 4 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. 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 2).
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 3.
Terdapat dua catatan penting dengan penggunaan teknik flooding ini, yaitu:
- Semua rute yang dimungkinkan akan dicoba. Karena itu teknik ini memiliki keandalan yang tinggi dan cenderung memberi rioritas untuk pengiriman-pengiriman paket tertentu.
- 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.3. Random Routing
Prinsip 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.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.
