Komunikasi Data " Perutean Dalam Jaringan Swtching"

1. Fungsi perutean dalam jaringan switching
    a. Perutean Dalam Jaringan Packet-Swithcing
        Salah satu aspek desain yang paling rumit dan penting dari jaringan data switched adalah perutean. Bagian ini menyurvei karakteritistik-karakteristik kunci yang dapat digunakan untuk mengklasifikasikan strategi perutean. Prinsip-prinsip yang dideskripsikan dalam bagian ini juga dapat diterapkan dalam perutean internetwork.
     • Karakteristik-Karakteristik
Fungsi utama dari packet-switching adalah menerima paket dari suatu sumber stasiun dan mengarahkan mereka ke stasiun tujuan.. Untuk menyelesaikan ini, satu jalur atau rute melalui jaringan tersebut harus ditentukan; umumnya, lebih dari satu rute yang memungkinkan. Jadi, fungsi perutean harus dilakukan. Persyaratan-persyaratan untuk fungsi ini mencakup :
• Ketepatan
• Kesederhanaan
• Ketahanan
• Stabilitas
• Kewajaran
• Keoptimalan
• Efisiensi


Pemilihan sebuah rute umumnya berdasarkan beberapa kriteria kinerja. Kriteria yang paling sederhana adalah memilih rute lompatan-minimum (kriteria yang melewati jumlah node terkecil) melalui jaringan tersebut. Kriteria ini adalah kriteria yang mudah diukur dan seharusnya meminimalkan konsumsi sumber-sumber jaringan. Generalisasi dari kriteria lompatan-minimum adalah perutean dengan biaya terendah.


Keputusan perutean dibuat berdasakan beberapa kriteria kinerja. Dua karakteristik utama dari keputusan tersebut adalah waktu dan tempat di mana keputusan tersebut dibuat. Waktu dan keputusan ditentukan oleh apakah keputusan perutean tersebut dibuat berdasarkan paket atau sirkuit maya. Ketika operasi internal dari jaringan adalah datagram, keputusan perutean dibuat masing-masing untuk setiap paket. Untuk operasi sirkuit maya internal, keputusan perutean dibuat pada saat sirkuit maya dibangun.. Pada kasus yang paling sederhana, semua paket berikutnya menggunakan sirkuit maya mengikuti rute yang sama. Pada desain jaringan yang lebih rumit, jaringan tersebut dapat secara dinamis mengganti rute yang ditugaskan pada sirkuit maya khusus sebagai respons dalam kondisi yang berubah (contohnya, kelebihan muatan atau kegagalan dalam sebuah bagian dari jaringan).
Fungsi perutean berupaya untuk menemukan rute melalui jaringan dengan biaya terendah atau dengan istilah (least-cost), Dengan biaya berdasarkan jumlah lompatan, Penundaan yang diharapkan atau ukuran lainya. Skema perutean dapat dikategorikan berdasarkan sejumlah factor seperti kriteria yang digunakan untuk menentukan rute terbaikantara dua node, strategi apa yang digunakan untuk memperoleh informasi yang diperlukan untuk menentukan rute dan apakah algoritma terdistribusi atau tersentralisasai yang digunakan.

2. Flooding dalam jaringan switching
Contoh lain dari perutean sederhana adalah flooding. Teknik ini tidak tidak membutuhkan informasi jaringan apapun dan bekerja sebagai berikut. Pada setiap node, paket yang datang ditransmisikan ulang pada semua link yang keluar, kecuali untuk link ketika paket itu tiba. Label pada setiap paket dalam gambar tersebut mengindikasikan nilai terkini dalam field perhitungan lompatan dalam paket itu.
      Teknik foolding memilki tiga sifat yang luar biasa, antara lain:
     1.Semua rute yang mungkin antara sumber dan tujuan dicoba. Dengan demikian, tidak peduli penghentian link atau node telah terjadi, Paket akan dapat selalu lewat jika paling tidak terdapat satu jalurantara sumber dan tujan.
     2.Oleh karena semua rute dicoba, paling tidak satu salinan dari paket yang tiba pada tujuan akan digunakan pada rute lompatan minimum.
     3.Semua node, baik secara langsung maupun tidak langsung dihubungkan ke node sumber akan dikunjungi.

Oleh karena sifat pertama, teknik flooding sangatlah tahan dan dapat digunakan untuk mengirimi pesan-pesan darurat. Sebuah contoh aplikasinya adalah jaringan militer yang merupakan subyek pengrusakan besar. Oleh karean sifat kedua tersebut, flooding mungkin yangdigunakan pada awalnya untuk menyetel rute untuk sirkuit maya. Sifat ketiga menyarankan bahwa flooding dapat digunakan untuk penghamburan informasi perutean.Kerugian utuama pada flooding adalah muatan lalu lintas yang tinggi dihasilkan, yang secara langsung proposional terhadap hubungan jaringan tersebut.

3. Perutean Dalam ARPANET
Strategi-Strategi Dalam Perutean
Sejumlah besar strategi perutean telah berkembang untuk berhadapan dengan persyaratan perutean dari jaringan packet-switching. Banyak dari strategi ini juga diterapkan pada perutean internetwork. Pada bagian ini kita akan membahas empat strategi penting yaitu :
   • Perutean tetap
      Bagi perutean tetap, sebuah rute tunggal dan permanen dikonfigurasi untuk masing-masing pasangan sumber-tujuan dari node dalam jaringan tersebut. Algoritma perutean biaya-terendah dapat digunakan. Rute tersebut ditetapkan, atau paling tidak hanya diubah ketika tidak ada perubahan dalam topologi jaringan. Jadi, biaya link yang digunakan dalam merancang rute tidak berdasarkan pada variabel dinamis seperti lalu lintas, Bagaimanapun juga, mereka dapat berdasarkan pada lalu lintas atau kapasitas yang diinginkan.
   • Flooding
     Seperti yang udah dijelaskan diatas tadi .Teknik ini membutuhkan informasi jaringan apa pun dan bekerja sebagai berikut. Sebuah paket dikirimkan oleh sebuah node sumber ke setiap node tetangganya. Pada setiap node, paket yang datamg ditransmisikan ulang pada semua link yang keluar, kecuali untuk link paket itu tiba.
   • Perutean acak
Perutean acak memiliki kesederhanaan dan ketahanan dari flooding dengan muatan lalu lintas yang jauh lebih sedikit. Dengan perutean acak, sebuah node memilih hanya satu jalur output untuk transmisi ulang dari paket yang datang. Link output dipiluh secara acak, di luar link di mana paket tersebut tiba. Jika semua link memiliki keuntungan yang sama untuk dipilih, maka semua node mungkin secara sederhana menggunakan link output dalam sebuah model.
   • Perutean adaptif
     Pada semua jaringan packet-switcing secara maya, beberapa jenis teknik perutean adaptif digunakan. Maksudnya, keputusan perutean yang dibuat berubah seiring dengan kondisi perubahan jaringan.
     Kondisi-kondisi utama yang mempengaruhi keputusan perutean adalah :
    1.Kegagalan :Ketika sebuah node atau link gagal, ia tidak dapat lagi digunakan sebagai bagian dari sebuah rute
    2.Kemacetan : Ketika sebuah bagian khusus dari jaringan tidak mengalami kemacetan, akan lebih baik memindahkan paket-paket dengan cara memutar daripada melewati area kemacetan.

Pada bagian ini, kita akan melihat beberapa contoh strategi perutean. Semua ini awalnya dikembangkan untuk ARPANET, yang merupakan jaringan packet-switching yang merupakan fondasi dari internet saat ini. Penting untuk mengamati strategi-strategi ini karena berbagai alasan. Pertama, strategi-strategi ini dan yang serupa juga digunakan dalam jaringan packet-switching yang lain, termasuk sejumlah jaringan dalam internet, Kedua, skema perutean berdasarkan kerja ARPANET juga digunakan untuk perutean internetwork dalam internet dan internetwork pribadi. Terakhir, skema perutean ARPANET berevolusi dengan cara memberikan pencerahan terhadap beberapa isu desain penting yang berhubungan dengan algoritma perutean.
• Generasi Pertama
Algoritma perutean awal, dirancang pada tahun 1969, merupakan algoritma adaptif terdistribusi menggunakan penundaan yang diperkirakan sebagai kriteria kinerja dan versi algoritma Bellman-Ford.
• Generasi Kedua
Setalah beberapa tahun pengalaman dan beberapa modifikasi minor, algoritma perutean asli digantikan dengan sesuatu yang sangat berbeda pada tahun 1979.
• Generasi Ketiga
Pengalaman dengan strategi baru ini mengindikasikan bahwa strategi tersebut lebih responsif dan stabil dibandingkan yang lama. Overhead yang dipengaruhi oleh flooding sedang-sedang saja karena masing-masing node melakukan hal ini paling banyak satu kali setiap 10 detik. Bagaimanapun juga, ketika muatan pada jaringan bertambah. Kekurangan dalam strategi baru mulai muncul, dan strategi tersebut direvisi pada tahun 1987.
Sebagai contoh misalkan sebuah jaringan yang terdiri dari dua wilayah yang dengan hanya dua link (A dan B ). Terdapat sejumlah alasan mengapa osilasi ini tidak tidak diinginkan :
1.Porsi yang signifikan dari kapsitas yang tersedia tidak digunakan pada saat mana hal itu sangat dibutuhkan : ketika muatan lalu lintas berat
2.Pemamfaatan yang berlebihan dari beberapa link dapat mengarahkan pada penyebaran kemacetan dalam jaringan ( hal ini dapat dilihat pada pembahasan kemacetan )
3.Ayunan besar dalam nilai penundaan yang diukur menghasilkan kebutuhan akan pesan update perutean yang lebih sering. Hal ini meningkatkan muatan pada jaringan ketika jaringan telah padat.
Para perancang ARPANET menyimpulkan bahwa inti dari permasalahan tersebut adalah setiap node berupaya untuk mendapatkan rute terbaik untuk semua jurusan dan bahwa semua upaya ini saling bertentangan. Disimpilkan bahwa dibawah muatan yang berat, tujuan dari perutean seharusnya memberikan jalur yang baik untuk sebagian rute, bukan utntuk memberikan jalur terbaik untuk semua rute.
4. Perbedaan dari algoritma Dijakstra dengan algoritma Bell-ford.
    1. Algoritma Dijakstra
        Algoritma Dijkstra dapat dinyatakan sebagai; carilah jalur terpendek dari sebuah sumber node tertentu ke semua node lainnya dengan mengembangkan jalur-jalur tersebut dalam urutan meningkatnya panjang jalur. Algoritma tersebut akan melanjutkan ke beberapa tahapan.Algoritma Dijkstra, (dinamai menurut penemunya, seorang ilmuwan komputer, Edsger Dijkstra), adalah sebuah algoritma rakus (greedy algorithm) yang dipakai dalam memecahkan permasalahan jarak terpendek (shortest path problem) untuk sebuah graf berarah (directed graph) dengan bobot-bobot sisi (edge weights) yang bernilai tak-negatif. Misalnya, bila vertices dari sebuah graf melambangkan kota-kota dan bobot sisi (edge weights) melambangkan jarak antara kota-kota tersebut, maka algoritma Dijkstra dapat digunakan untuk menemukan jarak terpendek antara dua kota. Input algoritma ini adalah sebuah graf berarah yang berbobot (weighted directed graph) G dan sebuah sumber vertex s dalam G dan V adalah himpunan semua vertices dalam graph G. Setiap sisi dari graf ini adalah pasangan vertices (u,v) yang melambangkan hubungan dari vertex u ke vertex v. Himpunan semua tepi disebut E. Bobot (weights) dari semua sisi dihitung dengan fungsi.

      Algorima dijkstra adalah sebuah algoritma rakus (greedy algorithm) dalam memecahkan permasalahan jarak terpendek (shortest path problem) untuk sebuah graf berarah (directed graph) atau graf tak berarah (undirected graph) dengan bobot-bobot sisi (edge weights) yang bernilai tak negatif sehingga diasumsikan bahwa k(vij) >= 0 untuk semua edges (vij) ∈ E. Algoritma dijkstra ditemukan oleh E.W Dijkstra salah seorang kontributor utama dalam pengembangan ALGOL, sebuah bahasa pemrogaman tingkat tinggi. Dan juga merupakan salah seorang pengembang dari ilmu dan dari bahasa pemrograman secara umum. E.W Dijkstra adalah lulusan dari The Gymnasium Erasmianum di Rotterdam, dan mendapatkan gelar dalam bidang matematika dan fisika teori dari universitas Leyden, dan gelar Ph.D. dalam ilmu komputer dari universitas Amsterdam. E.W Dijkstra bekerja sebagai programmer di pusat matematika, Amsterdam pada tahun 1952 sampai denga tahun 1962. Pada tahun 1962 hingga tahun 1984, E.W Dijkstra menjadi professor matematika di Universitas Teknik Eindhoven. E.W Dijkstra mengadakan Schlumberger Centennial Chair in Computing Sciences di Universitas Texas pada tahun 1984 sampai dengan tahun 1999, dan mundur dengan menyandang gelar sebagai professor kehormatan pada tahun 1999. Dengan algoritma dijkstra dapat menyelesaikan lintasan/rute terpendek dari sebuah verteks asal dan verteks tujuan dalam suatu graf berbobot G=(V,E). Jarak terpendek diperoleh dari dua buah verteks jika total bobot dari semua edges dalam jaringan graf adalah yang paling minimal. 

2. Algoritma Bellman-Ford

            Algoritma Bellman-Ford dapat dinyatakan sebagai berikut. Carilah jalur terpendek dari suatu node sumber tertentu dengan syarat hambatan yang terkandung dalam jalur maksimum satu link, kemudian carilah jalur terpendek dengan hambatan jalur maksimum dua link, dan seterusnya. Algoritma ini juga akan berlanjut ke beberapa tahapan. Algoritma Bellman ford adalah salah satu algoritma untuk mencari shostest path dimana jika dalam dalam suatu graf terdapat edge yang bernilai negatif. Meski demikian algoritma bellman ford juga bisa digunakan untuk mencari shortest path dalam graf yang hanya memiliki posotife edges, akan tetapi tidak akan seefisien algortima djikstra. Agar lebih jelas, perhatikan contoh dibawah ini :

     Maka jika kita menggunakan algortima bellman untuk menghitung jarak terdekat vertex A ke vertex C adalah 5, akan tetapi jarak terpendek sesungguhnya adalah 1, yaitu dengan jalur A – B – C. Hal ini dapat diantisipasi dengan menggunakan algoritma bellman. Dalam algoritma bellman class vertex harus memiliki 2 field yaitu distance(yang menunjukan jarak terdekat vertex tersebut terhadap vertex source) dan predecessor (yaitu c=vertex yang mendahului vertex tersebut pada path yang terbentuk) Akan tetapi algoritma bellman memiliki suatu kelemahan terdapat graf yang memiliki negative cycle, sehingga untuk graf yang memilki negative cycle memang tidak dapat dihitung shortest pathnya. Untuk langkah langkah dalam algoritma bellman ford adalah sebagai berikut ini :  Tentukan vertex source dan daftar seluruh vertices maupun edges.  Assign nilai untuk distance dari vertex source = 0, dan yang lain infinite Mulailah iterasi terhadap semua vertices yang dimulai dari vertex source,  Untuk menentukan distance dari semua vertices yang berhubungan dengan vertex source dengan formula seperti berikut ini :

U = vertex asal
V = vertex tujuan
UV = Edges yang menghubungkan U dan V  (Jika distance V, lebih kecil dari distance U + weight UV maka distance V, diisi dengan distance U + weight UV)

    Lakukan hingga semua vertices terjelajahi Untuk mengecek apakah ada negative cycle dalam graf tersebut lakukan iterasi untuk semua edges yang ada, kemudia lakukan penge-cek-an seperti dibawah ini :  Untuk semua edges UV, jika ada distance vertex U + weight edges UV kurang dari distance vertex V maka sudah jelas bahwa graf tersebut memiliki negative cycle.