KUNCI• Berbagai algoritma routing yang telah dikembangkan untuk beralih packet, frame relay, dan jaringan ATM, dan Internet dan internetwork. Algoritma ini berbagi banyak prinsip yang sama.• Skema Routing dapat dikategorikan berdasarkan sejumlah faktor, seperti apa kriteria yang digunakan untuk menentukan rute terbaik antara dua node, strategi apa yang digunakan untuk memperoleh informasi yang dibutuhkan untuk menentukan rute tambang, dan apakah algoritma didistribusikan atau terpusat digunakan.• Fungsi Routing mencoba untuk menemukan rute-biaya setidaknya melalui jaringan, dengan biaya berdasarkan jumlah hop, keterlambatan diharapkan, atau metrik lainnya. Algoritma routing yang adaptif biasanya bergantung pada pertukaran informasi tentang kondisi lalu lintas antara node.

Masalah desain kunci dalam jaringan diaktifkan, termasuk packet-switching, frame relay, dan jaringan ATM, dan dengan Internets, adalah bahwa routing. Secara umum, fungsi routing berusaha untuk merancang rute melalui jaringan untuk pasangan individu berkomunikasi node end seperti jaringan yang digunakan secara efisien.

Bab ini dimulai dengan gambaran singkat tentang isu yang terlibat dalam desain routing. Selanjutnya, kita melihat fungsi routing dalam packet-switching jaringan dan kemudian memeriksa algoritma biaya terendah yang merupakan bagian utama dari routing dalam jaringan diaktifkan. Topik-topik ini mencakup isu-isu yang relevan dengan routing internet serta paket-switching jaringan.

12,1 ROUTING PAKET DI-BERGANTI JARINGAN

Salah satu kompleks yang paling penting dan aspek-aspek desain jaringan switched data Pengarah perutean. Bagian ini karakteristik kunci yang dapat survei dapat digunakan untuk mengklasifikasikan routing Strategi-strategi. Prinsip-prinsip yang dijelaskan dalam bagian ini juga berlaku untuk internet- Bekerja routing, dibahas dalam bagian lima

karakteristikFungsi utama dari jaringan packet-switching adalah menerima paket dari stasiun

sumber dan mengantarkan mereka ke stasiun tujuan. Untuk mencapai hal ini, jalur atau rute melalui jaringan harus ditentukan; umumnya, lebih dari satu rute mungkin. Ini, fungsi routing yang harus dilakukan. Persyaratan untuk fungsi ini meliputi

· Kebenaran ·  Keadilan· Kemudahan ·  Optimality· Ketangguhan ·  Efisiensi· Stabilitas

Dua pertama item pada daftar, kebenaran dan kemudahan, adalah jelas.Ketangguhan telah melakukan dengan kemampuan jaringan untuk memberikan paket melalui beberapa rute Dalam menghadapi kegagalan dilokalisasi dan overloads. Idealnya, jaringan dapat bereaksi terhadap seperti contingencies tanpa kehilangan paket atau pelanggaran sirkuit virtual. Desainer Yang mencari ketangguhan harus beradaptasi dengan persyaratan yang bersaing untuk stabilitas. Techniques yang bereaksi terhadap perubahan kondisi memiliki kecenderungan yang kurang beruntung untuk bereaksi Terlalu lambat untuk peristiwa-peristiwa atau untuk tidak stabil berayun dari satu pengalaman extreme untuk lain. Contoh, jaringan dapat bereaksi terhadap kongesti pada satu wilayah oleh perladangan kebanyakan load Untuk sebuah area kedua. Sekarang area kedua adalah kelebihan beban dan yang pertama adalah dia menambahkan, causIng shift kedua. Selama giliran kerja ini, paket perjalanan mungkin dalam sosok melalui jaringan.

Sebuah tradeoff juga ada antara keadilan dan optimality. Beberapa cri performateria mungkin memberikan prioritas yang lebih tinggi untuk pertukaran paket di antara stasiun terdekat Dibandingkan dengan pertukaran antara stasiun jauh. Kebijakan ini dapat memaksimalkan averthroughput usia akan muncul tetapi tidak adil untuk stasiun yang terutama perlu communicate dengan stasiun jauh.

Akhirnya, teknik routing apa pun melibatkan beberapa overhead pemrosesan di masing-masing Node dan sering overhead pengiriman, baik dari yang mengganggu effi jaringanciency. Azab yang perlu overhead seperti kurang dari manfaat yang masih harus dibayar berdasarkan Pada beberapa masuk akal metrik, seperti meningkatkan ketangguhan atau keadilan.

Dengan syarat-syarat ini dalam pikiran, kita berada dalam posisi untuk menilai berbagaiElemen desain yang dapat menyumbangkan sebuah strategi perutean. Daftar 12.1 elemen-elemen tabel.

Hal ini, biaya yang telah dikaitkan dengan setiap link, dan, untuk memasangkan dari stasiun yang terpasang, Melalui jaringan yang rute dari kesuluruhan kurangnya biaya yang dicari. Misalnya, Gambar 12.1 menggambarkan jaringan di mana dua garis arrowed antara sepasang Mewakili sebuah link antara node-node, dan angka yang bersangkutan Mengirim link saat ini dalam setiap arah biaya. Jalan terpendek (kecilnya hops acids) dari 1biaya = 1 + 1 + 2 = 42. Biaya-biaya yang ditetapkan ke link untuk mendukung satu atau lebih design Tujuan. Misalnya, biaya dapat berbanding terbalik terkait dengan data rate (misalnya, Data rate yang lebih tinggi pada sebuah link, menurunkan biaya yang ditetapkan dari link) atau arus Penundaan antrian pada link. Dalam kasus pertama, kurangnya-rute biaya harus memberikan Throughput tertinggi. Dalam kasus kedua, kurangnya-rute biaya harus mengurangi penundaan

Dalam-hop minimum atau kurangnya-pendekatan biaya, algoritma untuk determinIng rute yang optimal untuk pasangan apa pun dari stasiun-stasiun adalah tergolong sederhana, danWaktu pengolahan akan tentang hal yang sama untuk penghitungan yang baik. Karena kurangnya Kriteria biaya lebih fleksibel, ini adalah lebih umum dari minimal-hop kriteria.Beberapa algoritma routing biaya-kurangnya berada dalam penggunaan secara umum. Semua ini digambarkan Dalam bagian 12.3.

Tempat dan Waktu keputusan  -keputusan routing berdasarkan

beberapa Kriteria performa. Tombol dua ciri-ciri keputusan adalah waktu dan

tempat Keputusan yang dibuat.Waktu keputusan ditentukan oleh apakah keputusan routing dibuat pada Atau paket virtual circuit dasar. Ketika operasi jaringan internal adalah data Gram, sebuah keputusan routing dibuat secara individu untuk setiap paket. Untuk virtual internal Operasi sirkuit, sebuah keputusan routing adalah yang dibuat saat sirkuit virtual peruahaan- Lished. Pada kasus yang paling sederhana, semua paket selanjutnya menggunakan sirkuit virtual yang mengikuti Rute yang sama. Dalam desain jaringan yang lebih canggih, jaringan mungkin dynamically mengubah rute yang ditetapkan ke sirkuit virtual tertentu terhadap perubahan(misalnya, kondisi beban yang berlebihan atau kegagalan sebagian jaringan). Istilah  tempat keputusan  merujuk ke node yang atau node dalam jaringan di Bertanggung jawab atas keputusan routing. Yang paling umum adalah didistribusikan routing, di mana Tiap node mempunyai tanggungjawab untuk memilih sebuah link output untuk paket routing sebagaiMereka tiba. Untuk routing terpusat, keputusan yang dibuat oleh beberapa node yang ditentukan,Seperti jaringan control center. Bahaya pendekatan yang terakhir ini adalah bahwa kehilangan Dari pusat kontrol jaringan dapat menghalangi operasi

jaringan. Komponen terdistribusi Pendekatan ini mungkin lebih rumit tetapi juga lebih kuat. Alternatif ketiga, digunakan Dalam beberapa jaringan, adalah source routing. Dalam hal ini, keputusan routing adalah benar-benar Dibuat oleh stasiun sumber daripada oleh node jaringan dan kemudian communicated ke jaringan. Hal ini memungkinkan pengguna untuk mendikte rute melalui jaringan Yang memenuhi kriteria untuk pengguna yang lokal.Keputusan-keputusan dan waktu tempat ini adalah variabel desain independen. UntukContoh, dalam Gambar 12.1, anggaplah bahwa tempat keputusan adalah setiap node dan bahwa Nilai-nilai yang digambarkan di biaya pada diberikan dalam masa: instan biaya-biaya dapat berubah. Jika sebuah Paket dikirimkan dari node 1 ke simpul 6, mungkin mengikuti rute 1-4-5-6, Dengan tiap-tiap kaki rute ditentukan secara lokal oleh node transmisi. KiranyaPerubahan nilai-nilai yang 1-4-5-6 seperti itu tidak lagi rute yang optimal. Dalam sebuah datagram net-Bekerja, paket berikutnya dapat mengikuti rute yang berbeda, ditentukan oleh setiap node lagi Di sepanja ng jalan. Dalam sebuah jaringan sirkuit virtual, tiap node akan mengingat pengarah perutean Keputusan yang dibuat saat sirkuit virtual didirikan, dan hanya terjadi pada Paket tanpa membuat keputusan yang baru.

Sumber informasi jaringan dan memperbarui Penentuan Masa  

paling strate routinggies memerlukan bahwa keputusan berdasarkan

pengetahuan tentang topologi jaringan, Beban lalu lintas, dan biaya link. Yang

mengejutkan, beberapa strategi tidak menggunakan informasi tersebut dan

Namun mengelola untuk mendapatkan paket melalui; flooding dan beberapa

strategi acak (dibahas Nanti) di dalam kategori ini. Dengan didistribusikan,

yang routing keputusan routing dibuat oleh tiap node, Node individu mungkin

menggunakan hanya informasi lokal, seperti biaya setiap keluar Link akan. Tiap

node mungkin juga mengumpulkan informasi dari berdekatan (langsung

Terhubung) node, seperti jumlah kepadatan alami pada node tersebut.

Akhirnya, Algoritma ada dalam penggunaan secara umum, yang

memungkinkan node untuk memperoleh informasi dari semua Node pada rute

potensial mana pun menarik. Dalam kasus routing terpusat, pusat Biasanya

node ini yang menggunakan informasi yang diperoleh dari semua node. Konsep

terkait adalah bahwa pembaruan informasi, yang merupakan pewaktuan fungsi

Kedua-dua sumber informasi dan strategi perutean. Jelas, jika tidak ada

informasi Digunakan (seperti dalam flooding), tidak ada informasi untuk

memperbarui. Jika hanya informasi lokal Digunakan, pembaruan pada

dasarnya terus-menerus. Yang, sebuah node individu selalu mengetahui

Kondisi setempat. Untuk semua informasi lain kategori sumber (node

berdekatan, semua Node), memperbarui pewaktuan tergantung pada strategi

perutean. Untuk strategi yang tetap, Informasi yang tidak pernah diperbarui.

Untuk sebuah strategi adaptif, informasi yan diperbarui dari Waktu ke waktu

untuk mengaktifkan keputusan routing untuk beradaptasi terhadap perubahan

kondisi. Seperti yang anda harapkan, informasi lebih lanjut tersedia, dan lebih

sering Ia adalah diperbarui, semakin besar kemungkinan jaringan adalah untuk

membuat keputusan routing yang baik. Pada Sisi lain, transmisi informasi yang

menghabiskan sumber daya jaringan.

Strategi RoutingSejumlah besar strategi routing berevolusi untuk berurusan dengan pengarah

perutean Syarat-syarat-paket berganti jaringan. Banyak dari strategi ini juga

Diterapkan untuk internetwork routing, yang kami di bagian penutup lima.

Dalam bagian ini, kita surVey empat strategi kunci: fixed, flooding, secara

acak, dan adaptive.

Fixed Routing

untuk fixed routing, satu, rute permanen telah dikonfigurasi untuk masing-

masing Tujuan sumber sepasang limfa pada jaringan. Salah satu yang paling

kecil-perutean termurah Algoritma yang dijelaskan dalam Bab 12.3 dapat

digunakan. Rute tersebut adalah fixed, atau sekurang-kurangnya Hanya

berubah bila ada perubahan dalam topologi jaringan. Justru itu, link Biaya-

biaya yang digunakan dalam merancang merutekan tidak dapat didasarkan

pada variabel dinamis seperti traffic. Mereka dapat, walau demikian,

berdasarkan lalu lintas diharapkan atau kapasitas. Gambar 12,2 menunjukkan

bagaimana mungkin dilaksanakan routing tetap. Sebuah carut tengahIng

matrix dibuat, untuk disimpan mungkin di jaringan control center. Matriks

Menunjukkan, untuk setiap sumber-pasangan tujuan node, identiti node

berikutnya pada Rute. Catatan bahwa ia tidak diperlukan untuk menyimpan

rute yang lengkap untuk setiap kemungkinan Memasangkan node. Sebaliknya,

ia sudah cukup untuk mengetahui, untuk setiap pasangan node, identitas Node

pertama pada rute. Untuk melihat ini, menganggap bahwa kurangnya-rute

biaya dari X untuk Y  bermula dengan  X-sebuah   link. Panggil sisa route R1. ini

adalah bagian Dari sebuah untuk Y. Menentukan R2 sebagai yang paling kecil-

rute biaya dari sebuah untuk Y. Sekarang, jika biaya R1 adalah Lebih besar

daripada R2, maka X- rute Y dapat ditingkatkan dengan menggunakan

R2 sebagai ganti. Jika biaya R1  adalah kurang dari R2, kemudian R2  tidak yang

paling kecil-rute biaya dari sebuah untuk Y. Oleh karena itu, R1  = R2. Justru itu,

di setiap poin sepanjang rute, hanya diperlukan untuk mengetahui Identiti

node berikutnya, bukan seluruh rute. Di contoh kita, rute dari 1 ke node node

6 bermula dengan masuk melalui node 4. Lagi konsultasi dengan matrix, Rute

dari 4 node ke node 6 melewati 5 node. Akhirnya, rute node dari 5 untuk 6

node adalah link langsung ke simpul 6. Justru itu, rute lengkap dari node 1 ke

simpul 6 adalah 1-4-5-6. Dari keseluruhan ini matrix, tabel routing dapat

dikembangkan dan disimpan di masing-masing Node.

Hanya menyimpan satu kolom dari direktori perutean. Direktori node yang

menunjukkan Node berikutnya untuk mengambil untuk tujuan masing-masing.

Dengan routing tetap, tidak ada perbedaan antara routing untuk datagrams dan

Sirkuit virtual. Semua paket dari sumber yang diberikan untuk sebuah tujuan

diberikan ikuti Jalur yang sama. Keuntungan dari routing tetap adalah

kemudahannya, dan ia harus bekerja dengan baik Dalam jaringan yang dapat

diandalkan dengan beban yang stabil. Para kekurangan adalah ketiadaan

fleksibilitas. Ia Tidak bereaksi terhadap kongesti jaringan atau kegagalan.

Sebuah refinement ke fixed routing yang akan menampung link node dan

pemadaman Akan untuk memasok node dengan node berikutnya alternatif

untuk tujuan masing-masing. Untuk Contoh, node berikutnya dalam alternatif

node 1 mungkin direktori 4, 3, 2, 3, 3.

flooding

teknik routing sederhana lain lagi . Teknik ini memerlukan Tidak ada informasi

jaringan apa pun dan bekerja sebagai berikut. Paket dikirimkan oleh sebuah

Node sumber untuk setiap satu dari tetangga-tetangganya. Pada setiap node,

sebuah paket masuk Pada semua link keluar dilarang menyalin kecuali untuk

link pada yang masuk. Ujian untuk Ple, jika node dalam Gambar 1 12.1 telah

sebuah paket untuk mengirim ke simpul 6, ia mengirim salinan yang Paket

(dengan alamat tujuan dari 6), pada node 2, 3, dan 4. Node 2 akan mengirim

menyalin

Pada node 3 dan 4. 4 node akan mengirim menyalin pada node 2, 3, dan 5. Dan sehingga akan padam. Bahkan beberapa salinan paket akan tiba di node 6. Paket harus memiliki Beberapa pengenal unik (misalnya, node sumber dan nomor urutan, atau sirkuit virtual Jumlah dan nomor urutan) sehingga 6 node mengetahui untuk membuang semua tetapi salinan yang pertama. Kecuali jika ada sesuatu yang dilakukan untuk menghentikan pekerjaan retransmission paket, Jumlah paket yang beredar hanya dari satu paket sumber tumbuh tanpa Terikat. Salah satu cara untuk mencegah ini adalah untuk tiap node untuk mengingat identitas orang-orang Paket yang telah dilarang menyalin. Ketika salinan duplikat paket tiba, Mereka diabaikan. Teknik yang lebih sederhana yang berisi field jumlah hop dengan masing-masing Paket. Perhitungan dapat awalnya disetel ke beberapa nilai maksimum. Setiap kali suatu node melewati satu paket, ia decrements perhitungan oleh satu. Bila Menghitung mencapai nol, paket diabaikan.

Contoh taktik yang kedua adalah seperti yang diperlihatkan pada Gambar 12.3. Label pada masing-masing Paket dalam gambar menunjukkan nilai saat ini dari field jumlah hop dalam paket yang. Sebuah paket akan dikirim dari node 1 ke simpul 6 dan ditetapkan ke jumlah hop dari 3. Pada Hop pertama, tiga salinan paket diciptakan, dan jumlah hop adalah pengurangan untuk 2. Untuk kedua-hop semua salinan-salinan, sembilan salinan ini dibuat. Salah

satu Salinan-salinan mencapai 6 node, yang mengakui bahwa ia adalah tujuan yang dimaksudkan Tidak kirim ulang. Namun, node-node yang lain membuat total 22 salinan baru untuk Ketiga dan terakhir hop mereka. Masing-masing paket kini memiliki harapan jumlah 1. Catatan bahwa jika suatu node Tidak memelihara melacak pengenal paket, ia dapat menghasilkan beberapa salinan di ketiga ini Tahap. Semua paket yang diterima dari hop ketiga diabaikan, karena jumlah hop Kelelahan. Dalam semua node, 6 telah menerima empat salinan paket tambahan. Teknik flooding memiliki tiga properti yang luar biasa:

·  Semua rute mungkin antara dicuba sumber dan tujuan. Justru itu, tidak

peduli Apa link atau gangguan terjadi node, sebuah paket akan selalu

mendapatkan melalui jika di Paling tidak satu jalur antara ada sumber dan

tujuan.

·  karena semua rute dicuba, sedikitnya satu salinan paket ke tiba di

desTination akan digunakan minimal-hop rute.

·  Semua node yang secara langsung atau tidak langsung terhubung ke node

sumber adalah Mengunjungi. Karena properti pertama, teknik flooding sangat

kuat dan Dapat digunakan untuk mengirim pesan darurat. Contoh aplikasi ini

militer Jaringan yang tunduk untuk kerusakan luas. Karena properti yang

kedua, floodingmungkin digunakan pada awalnya untuk menyetel rute untuk

sirkuit virtual. Properti yang ketiga Menyarankan bahwa flooding dapat

berguna untuk penyebaran informasi penting Untuk semua node, kita akan

melihat bahwa ia digunakan dalam beberapa skema untuk menyebarkan

routingInformasi.Kepala sekolah kekurangan flooding adalah beban lalu lintas tinggi yang ia menghasilkan,Yang secara langsung cukup proporsional untuk konektivitas jaringan.

Untuk setiap pasangan end system terpasang ke jaringan, ada jalan minimum-hop. Panjang terpanjang seperti jalan minimum-hop adalah diameter jaringan

Acak Routing Acak Routing memiliki kesederhanaan dan ketahananflooding dengan jauh lebih sedikit beban lalu lintas. Dengan random routing, sebuah node hanya memilih satu jalur outgoing untuk pengiriman ulang paket yang masuk. keluar yang link dipilih secara

acak, tidak termasuk link di mana paket tiba. Jika semua link yang sama mungkin dipilih, maka node hanya dapat memanfaatkan out-akan link secara round-robin.

Sebuah penyempurnaan dari teknik ini adalah untuk menetapkan probabilitas untuk setiap link keluar dan pilih link berdasarkan probabilitas. Probabilitas dapat didasarkan pada data rate,dalam hal ini kita memiliki jumlah ini diambil alih para calon link keluar. Skema ini harus menyediakan distribusi lalu lintas yang baik. Perhatikan bahwa probabilitas bisa juga didasarkan pada biaya link tetap.Seperti flooding, acak routing yang memerlukan penggunaan tidak ada informasi jaringan. Karena rute yang diambil adalah acak, sama dengan rute yang akan biasanya tidak menjadi-terkecil Biaya rute atau jalur minimum-hop. Dengan demikian, jaringan harus membawa lebih tinggi dari beban lalu lintas yang optimal, meskipun tidak setinggi flooding.Routing Adaptif Dalam hampir semua jaringan packet-switching, semacam adaptifTeknik routing yang tive digunakan. Artinya, keputusan routing yang dibuat perubahan sebagaikondisi pada perubahan jaringan. Kondisi utama yang mempengaruhi routing yangkeputusan yang• Kegagalan: Ketika sebuah node atau link gagal, tidak bisa lagi digunakan sebagai bagian dari rute.• Kemacetan: Ketika ada bagian tertentu dari jaringan sangat padat, itu adalahdiinginkan untuk paket rute sekitar daripada melalui daerah kemacetan.Untuk adaptif routing untuk menjadi mungkin, informasi tentang keadaan jaringan

harus dipertukarkan antara node. Ada beberapa kelemahan yang terkait denganpenggunaan adaptif routing, dibandingkan dengan rute tetap:• Keputusan routing lebih kompleks; Oleh karena itu, beban pengolahan dijaringan node meningkat.• Dalam kebanyakan kasus, strategi adaptif tergantung pada informasi status yang dikumpulkandi satu tempat tetapi digunakan di lain. Ada tradeoff sini antara kualitasinformasi dan jumlah overhead. Semakin banyak informasi yangdipertukarkan, dan lebih sering dipertukarkan, semakin baik akan menjadi rout-ing keputusan yang setiap node membuat. Di sisi lain, informasi ini sendiribeban pada jaringan konstituen, menyebabkan penurunan kinerja.• Strategi adaptif dapat bereaksi terlalu cepat, menyebabkan kemacetan yang memproduksiosilasi, atau terlalu lambat, tidak relevan.Meskipun bahaya ini nyata, strategi routing yang adaptif adalah yang palinglazim, karena dua alasan:• Strategi routing yang adaptif dapat meningkatkan kinerja, seperti yang terlihat oleh pengguna jaringanStrategi routing yang adaptif dapat membantu dalam kontrol kongesti, yang dibahasdalam Bab 13. Karena strategi routing yang adaptif cenderung untuk menyeimbangkan beban, itudapat menunda timbulnya kemacetan parah.Manfaat ini mungkin atau mungkin tidak menyadari, tergantung pada tingkat kesehatan daridesain dan sifat beban. Pada umumnya, adaptif routing tugas yang sangat kompleks untuk melakukan dengan benar. Sebagai demonstrasi ini, yang paling utama packetberalih jaringan, seperti ARPANET dan penerusnya, dan banyak komersialjaringan, telah mengalami setidaknya satu perbaikan besar-besaran dari strategi routing.Sebuah cara mudah untuk mengklasifikasikan strategi routing yang adaptif adalah berdasarkan

Sumber informasi: lokal, node yang berdekatan, semua node. Contoh dari strategi routing yang adaptif yang hanya bergantung pada informasi lokal adalah salah satu di mana rute simpul setiappaket ke link keluar dengan panjang antrian terpendek, Q. ini akan memilikiefek menyeimbangkan beban pada link keluar. Namun, beberapa link keluar mungkintidak menuju ke arah yang benar umum. Kita bisa memperbaiki masalah dengan juga tak-ing mempertimbangkan pilihan arah, sebanyak dengan random routing. Dalam hal ini, masing-masingLink yang berasal dari node akan memiliki bias Bi, untuk setiap tujuan saya, sehingganilai yang lebih rendah dari Bi menunjukkan arah yang lebih disukai. Untuk setiap paket yang masukmenuju simpul i, node akan memilih link keluar yang meminimalkan Q + Bi.Dengan demikian node akan cenderung untuk mengirim paket ke arah yang benar, dengan konsesi dibuat untuk penundaan lalu lintas saat ini.Sebagai contoh, Gambar 12.4 menunjukkan status simpul 4 dari gambar 12.1 pada titik tertentu dalam waktu. Node 4 memiliki link ke empat node lain. Paket telah tiba dan backlog telah dibangun, dengan antrian paket menunggu setiap link keluar.Sebuah paket datang dari simpul 1 ditakdirkan untuk simpul 6.To yang link keluar harus paket diteruskan? Berdasarkan panjang antrian saat ini dan nilai-nilai bias 1B6 untuk setiap link keluar, nilai minimum adalah 4, pada link ke node 3. Dengan demikian, simpul 4 rute paket melalui simpul 3.Skema adaptif hanya berdasarkan informasi lokal jarang digunakan karena mereka tidak memanfaatkan informasi dengan mudah tersedia. Strategi berdasarkan informasi dari node yang berdekatan atau semua node biasanya ditemukan. Keduanya mengambil keuntungan dari informasi bahwa setiap node memiliki tentang penundaan dan padam sehingga mengalami. Strategi adaptif tersebut dapat baik didistribusikan atau terpusat. Dalam kasus didistribusikan, setiap pertukaran simpul menunda informasi dengan node lainnya. Berdasarkan informasi yang masuk, node mencoba untuk memperkirakan situasi delay seluruh jaringan, dan menerapkan algoritma routing yang paling murah. Dalam kasus terpusat, setiap node melaporkan nya status link delay ke node pusat, yang merancang rute berdasarkan informasi yang masuk dan

mengirimkan informasi routing kembali ke node.

Pada bagian ini, kita melihat beberapa contoh dari strategi routing. Semua ini adalah awalnya dikembangkan untuk ARPANET, yang merupakan jaringan packet-switching yang merupakan dasar dari masa kini internet. Ini adalah pelajaran untuk menguji strategi ini karena beberapa alasan. Pertama, strategi ini dan yang serupa juga digunakan dalam jaringan packet-switching lainnya, termasuk sejumlah jaringan di Internet. Kedua, skema routing yang didasarkan pada karya ARPANET juga telah digunakan untuk routing internetwork di Internet dan internetwork pribadi. Dan akhirnya, skema routing yang ARPANET berkembang dengan cara yang menerangi beberapa isu utama yang berkaitan dengan algoritma routing.

Generasi PertamaAlgoritma routing yang asli, yang dirancang pada tahun 1969, adalah algoritma adaptif terdistribusimenggunakan estimasi delay sebagai kriteria kinerja dan versi Bellman-Algoritma ford (Bagian 12.3). Untuk algoritma ini, setiap node mempertahankan dua

vektor:

Berkala (setiap 128 ms), setiap node pertukaran keterlambatan vektor dengan semua tetangganya. Atas dasar semua vektor keterlambatan masuk, node k update kedua vektor sebagai berikut:

Gambar 12.5 memberikan contoh algoritma ARPANET asli, dengan menggunakan jaringan Gambar 12.6.This adalah jaringan yang sama

seperti yang dilakukan oleh Gambar 12.1, dengan beberapa biaya link memiliki nilai yang berbeda (dan dengan asumsi biaya yang sama di kedua arah). Gambar 12.5a menunjukkan tabel routing untuk node 1 pada suatu saat dalam waktu yang mencerminkan biaya link Gambar 12.6. Untuk setiap tujuan, penundaan yang ditentukan, dan node berikutnya pada rute yang menghasilkan penundaan itu. Pada titik tertentu, biaya link berubah dengan yang Gambar 12.1. Asumsikan bahwa simpul 1 tetangga (node 2, 3, dan 4) belajar dari perubahan sebelum simpul 1. Setiap node ini update delay vektor dan mengirimkan salinan ke semua tetangga, termasuk simpul 1 (Gambar 12.5b). Node 1 membuang tabel routing saat ini dan membangun yang baru, hanya berdasarkan masuk delay vektor dan estimasi sendiri link keterlambatan untuk masing-masing hasil neighbors.The yang ditunjukkan pada Gambar 12.5c. Diperkirakan penundaan link hanya panjang antrian untuk link.Thus itu, dalam membangun tabel routing baru, simpul akan cenderung mendukung link keluar dengan antrian yang lebih pendek. Hal ini cenderung untuk menyeimbangkan beban pada link keluar. Namun, karena panjang antrian bervariasi pesat dengan waktu, persepsi didistribusikan rute terpendek bisa berubah saat sebuah paket perjalanan. Hal ini bisa mengakibatkan situasi meronta-ronta di mana paket terus mencari daerah kemacetan rendah daripada bertujuan tujuan.

Generasi KeduaSetelah beberapa tahun pengalaman dan beberapa modifikasi kecil, algoritma routing asli diganti dengan yang sangat berbeda pada tahun 1979 [MC80]. Kekurangan utama dari algoritma tua adalah sebagai berikut:

• Algoritma tidak mempertimbangkan kecepatan baris, hanya antrian length.The, link kapasitas yang lebih tinggi tidak diberi status disukai mereka pantas.• Panjang Antrian, dalam setiap kasus, ukuran buatan keterlambatan, karena beberapa jumlah variabel waktu pengolahan berlalu antara kedatangan paket pada node dan penempatannya dalam antrian outbound.• Algoritma ini tidak terlalu akurat. Secara khusus, ia menjawab perlahan kemacetan dan keterlambatan meningkat.

Algoritma baru ini juga merupakan salah satu adaptif terdistribusi, menggunakan delay sebagai kriteria kinerja, tetapi perbedaan yang

signifikan. Alih-alih menggunakan antrian panjang sebagai pengganti untuk keterlambatan, penundaan diukur secara langsung. Pada node, setiap paket yang masuk adalah waktu dicap dengan waktu kedatangan. Waktu keberangkatan dicatat pada saat paket yang ditransmisikan. Jika pengakuan positif dikembalikan, penundaan untuk paket yang tercatat sebagai waktu keberangkatan dikurangi waktu kedatangan ditambah waktu transmisi dan delay propagasi. Oleh karena itu node harus tahu keterkaitan nilai data dan waktu propagasi. Jika hal yang tidak kembali, waktu keberangkatan diperbarui dan node mencoba lagi, sampai ukuran sukses delay transmisi diperoleh. Setiap 10 detik, node menghitung delay rata-rata pada setiap link keluar. Jika ada perubahan signifikan dalam penundaan, informasi tersebut dikirim ke semua node lain menggunakan flooding. Setiap node mempertahankan perkiraan delay pada setiap jaringan link.When informasi baru tiba, ia menghitung tabel routing dengan menggunakan algoritma Dijkstra (Bagian 12.3).

Generasi KetigaPengalaman dengan strategi baru ini menunjukkan bahwa itu lebih responsif dan stabildari yang lama. Overhead yang disebabkan oleh flooding adalah moderat karena setiap node melakukan hal ini paling banyak sekali setiap 10 detik. Namun, sebagai beban pada jaringan tumbuh, kelemahan dalam strategi baru mulai muncul, dan strategi direvisi pada tahun 1987 [KHAN 89].Masalah dengan strategi kedua adalah asumsi bahwa delay diukur pada link merupakan prediksi yang baik dari penundaan link yang ditemui setelah semua node mengubah rute lalu lintas mereka berdasarkan ini dilaporkan delay.Thus, itu adalah mekanisme routing yang efektif hanya jika ada beberapa korelasi antara nilai yang dilaporkan dan mereka benar-benar mengalami setelah rerouting. Korelasi ini cenderung lebih tinggi di bawah cahaya dan beban lalu lintas moderat. Namun, di bawah beban berat, ada sedikit korelasi. Oleh karena itu, segera setelah semua node telah membuat update routing, tabel routing yang usang!

Sebagai contoh, mempertimbangkan jaringan yang terdiri dari dua wilayah dengan hanya dua link, A dan B, yang menghubungkan dua daerah (Gambar 12.7). Setiap rute antara dua node di berbagai daerah harus melewati salah satu link tersebut. Asumsikan bahwa situasi berkembang di mana sebagian besar lalu lintas pada A.This link yang akan menyebabkan penundaan link di A menjadi signifikan, dan pada

kesempatan berikutnya, ini nilai delay akan dilaporkan ke semua pembaruan nodes.These lainnya akan tiba di semua node pada waktu yang sama, dan semua akan memperbarui tabel routing mereka segera. Sangat mungkin bahwa penundaan ini nilai baru untuk link A akan cukup tinggi untuk membuat hubungan B pilihan yang lebih disukai untuk sebagian besar, jika tidak semua, rute antar wilayah. Karena semua node menyesuaikan rute mereka pada saat yang sama, sebagian besar atau semua pergeseran antar lintas daerah pada saat yang sama untuk menghubungkan B. Sekarang nilai link yang delay pada B akan menjadi tinggi, dan akan ada pergeseran berikutnya untuk menghubungkan osilasi A. This akan berlanjut sampai volume lalu lintas mereda.

Ada sejumlah alasan mengapa osilasi ini tidak diinginkan:• Sebagian besar kapasitas yang tersedia tidak digunakan pada waktu ketikayang paling dibutuhkan: di bawah beban lalu lintas berat

• The overutilization beberapa link dapat menyebabkan penyebaran kemacetan dalam jaringan (ini akan terlihat dalam pembahasan kemacetan di Bab 13).• Ayunan besar diukur nilai delay mengakibatkan kebutuhan untuk lebih sering messages.This routing update meningkatkan beban pada jaringan di hanya saat jaringan sudah stres. Para desainer ARPANET menyimpulkan bahwa esensi masalahnya adalah bahwa setiap simpul mencoba untuk mendapatkan rute terbaik untuk semua tujuan, dan bahwa upaya-upaya tersebut bertentangan. Disimpulkan bahwa di bawah beban berat, tujuan routing harus memberikan rute rata-rata jalan yang baik daripada mencoba untuk memberikan semua rute jalan terbaik.Para desainer memutuskan bahwa itu tidak perlu untuk mengubah algoritma routing secara keseluruhan. Sebaliknya, itu cukup untuk mengubah fungsi yang menghitung biaya link. Hal ini dilakukan sedemikian rupa untuk meredam osilasi Routing dan mengurangi routing yang overhead. Perhitungan dimulai dengan mengukur delay rata-rata selama terakhir nilai 10 seconds.This kemudian diubah dengan langkah-langkah berikut:1. Menggunakan satu server model antrian sederhana, penundaan diukur

berubah menjadi perkiraan utilisasi link. Dari teori antrian, utilisasi

dapat dinyatakan sebagai fungsi delay sebagai berikut:

Waktu layanan ditetapkan pada jaringan-lebar rata-rata ukuran paket (600 bit) dibagi dengan tingkat data link.

2. Hasilnya kemudian dihaluskan oleh rata-rata dengan perkiraan sebelumnya pemanfaatan:

Averaging meningkatkan periode osilasi routing, sehingga mengurangi routing yangoverhead.

3. Biaya link kemudian ditetapkan sebagai fungsi dari rata-rata penggunaan yang dirancang untuk memberikan perkiraan yang wajar dari biaya sambil menghindari osilasi. Gambar 12.8 menunjukkan cara di mana perkiraan pemanfaatan diubah menjadi nilai biaya akhir biaya value.The adalah, pada dasarnya, nilai berubah keterlambatan.

Pada Gambar 12.8, delay dinormalkan dengan nilai yang dicapai pada garis menganggur, yang hanya propagasi delay ditambah transmisi waktu. Satu kurva pada gambar menunjukkan cara di mana penundaan sebenarnya meningkat sebagai fungsi pemanfaatan; peningkatan keterlambatan ini disebabkan delay antrian di node. Untuk algoritma direvisi, nilai biaya disimpan pada nilai minimum sampai tingkat tertentu pemanfaatan tercapai. Fitur ini memiliki efek mengurangi overhead routing pada tingkat lalu lintas rendah. Di atas tingkat tertentu

pemanfaatan, tingkat biaya diperbolehkan untuk naik ke nilai maksimum yaitu sebesar tiga kali nilai minimum. Efek dari nilai maksimum ini adalah untuk menentukan bahwa lalu lintas tidak harus diarahkan di sekitar garis berat digunakan oleh lebih dari dua hop tambahan.

Perhatikan bahwa batas minimum ditetapkan lebih tinggi untuk link satelit. Hal ini mendorong penggunaan terrestrial link di bawah kondisi lalu lintas ringan, karena link terestrial memiliki delay propagasi jauh lebih rendah. Perhatikan juga bahwa kurva delay yang sebenarnya jauh lebih curam daripada kurva transformasi pada tingkat pemanfaatan yang tinggi. Ini adalah kenaikan tajam ini biaya link yang menyebabkan semua lalu lintas pada link untuk ditumpahkan, yang pada gilirannya menyebabkan osilasi routing.Singkatnya, fungsi biaya direvisi bersemangat untuk pemanfaatan daripada delay. Fungsi bertindak mirip dengan berbasis delay metrik bawah beban ringan dan kapasitas berbasis metrik di bawah beban berat.

Hampir semua packet-switching jaringan dan semua Internets

mendasarkan keputusan routingpada beberapa bentuk kriteria yang paling murah. Jika kriteria ini adalah untuk meminimalkan jumlahhop, setiap link memiliki nilai 1. Lebih biasanya, nilai hubungan berbanding terbalikdengan kapasitas link, sebanding dengan arus beban pada link, atau beberapa kombinasi.Dalam kasus apapun, biaya link atau hop ini digunakan sebagai input untuk algoritma routing-biaya terendah, yang dapat hanya dinyatakan sebagai berikut:

Mengingat jaringan node dihubungkan dengan link dua arah, di mana setiap link memiliki biaya yang terkait dengan itu di setiap arah, menentukan biaya jalan antara dua node sebagai jumlah dari biaya link dilalui. Untuk setiap pasangan node, menemukan jalan dengan biaya sedikit.

Perhatikan bahwa biaya link mungkin berbeda dalam dua directions.This yang akan menjadi kenyataan, misalnya, jika biaya link menyamai panjang antrian paket menunggu transmisi dari masing-masing dua node pada link.

Kebanyakan algoritma routing yang paling murah digunakan dalam paket-switching jaringan dan Internets adalah variasi dari salah satu dari dua algoritma yang umum, yang dikenal sebagai algoritma Dijkstra dan algoritma Bellman-Ford. Bagian ini menyediakan ringkasan dari dua algoritma tersebut.

Algoritma DijkstraAlgoritma Dijkstra [DIJK59] dapat dinyatakan sebagai: Cari jalur terpendek dari sumber node yang diberikan ke semua node lain dengan mengembangkan jalur dalam rangka peningkatan panjang jalan. Algoritma hasil secara bertahap. Pada tahap k, jalur terpendek ke node k paling dekat dengan (biaya minimal dari) node sumber telah ditentukan; node ini dalam satu set T. Pada tahap node tidak dalam T yang memiliki jalur terpendek dari node sumber ditambahkan ke T. Karena setiap node ditambahkan ke T, jalurnya dari sumber didefinisikan. Algoritma dapat secara resmi digambarkan sebagai berikut. Tentukan:

Algoritma ini memiliki tiga langkah; langkah 2 dan 3 diulangi sampai Artinya, langkah 2 dan 3 diulangi sampai jalan akhir telah ditetapkan ke semua node dalam jaringan:

node berbayang ketika ditambahkan ke T. Perhatikan bahwa pada setiap langkah jalan ke setiap node ditambah total biaya jalur yang dihasilkan. Setelah iterasi akhir, biaya terendah path ke setiap node dan biaya jalan yang telah dikembangkan. Prosedur yang sama dapat digunakan dengan simpul 2 sebagai sumber node, dan sebagainya.Bellman-Ford AlgoritmaAlgoritma Bellman-Ford [FOR 62] dapat dinyatakan sebagai berikut: Cari jalur terpendek dari node subjek sumber diberikan kepada kendala bahwa jalan berisi paling banyak satu link, kemudian menemukan jalan terpendek dengan kendala jalan yang paling dua link, dan sebagainya. Algoritma ini juga hasil secara bertahap. Algoritma dapat secara resmi digambarkan sebagai berikut.

ComparissonSatu perbandingan yang menarik dapat dibuat antara dua algoritma ini, yang berkaitan dengan apa yang perlu informasi yang akan

dikumpulkan. Pertimbangkan pertama algoritma Bellman-Ford. Pada langkah 2, perhitungan untuk simpul n melibatkan pengetahuan tentang biaya link semua node tetangga node n [yaitu, w (j, n)] ditambah biaya jalan total masing-masing node tetangga dari sumber node tertentu s [ yaitu,]. Setiap node dapat mempertahankan satu set biaya dan jalur terkait untuk setiap node lainnya dalam jaringan dan bertukar informasi dengan tetangga langsung dari waktu ke waktu. Setiap node sehingga dapat menggunakan ekspresi pada langkah 2 dari algoritma Bellman-Ford, hanya berdasarkan informasi dari tetangga dan pengetahuan biaya kaitannya, untuk memperbarui biaya dan jalan. Di sisi lain, pertimbangkan algoritma Dijkstra. Langkah 3 tampaknya mengharuskan setiap node harus memiliki informasi lengkap tentang topologi jaringan. Artinya, setiap node harus mengetahui biaya link semua link dalam jaringan. Dengan demikian, untuk algoritma ini, informasi harus ditukar dengan semua node lainnya. Secara umum, evaluasi manfaat relatif dari kedua algoritma harus mempertimbangkan waktu proses algoritma dan jumlah informasi yang harus dikumpulkan dari node lain dalam jaringan atau internet. Evaluasi akan tergantung pada pendekatan implementasi dan implementasi yang spesifik. Titik akhir: Kedua algoritma dikenal untuk berkumpul dalam kondisi statis topologi, dan biaya link dan akan bertemu dengan solusi yang sama. Jika biaya link berubah dari waktu ke waktu, algoritma akan mencoba untuk mengejar ketinggalan dengan perubahan ini. Namun, jika biaya link yang tergantung pada lalu lintas, yang pada gilirannya tergantung pada pilihan rute, maka kondisi umpan balik ada, dan dapat menyebabkan ketidakstabilan.

Review Questions12.1. Apa persyaratan utama untuk fungsi routing untuk jaringan packet-switching?12.2. Apa yang tetap Routing?12.3. Apa banjir?12.4. Apa keuntungan dan kerugian dari adaptif routing yang?12.5. Apa yang dimaksud dengan algoritma paling murah?12.6. Apa perbedaan penting antara algoritma Dijkstra dan Bellman-Ford algoritma?

PROBLEM :12.1 Pertimbangkan jaringan packet-switching N node, terhubung dengan topologi berikut:a. Star: satu simpul pusat tanpa stasiun terpasang; semua node lain melekat pada simpul pusat.b. Loop: setiap node terhubung ke dua node lain untuk membentuk loop tertutup.c. Penuh terhubung: setiap node terhubung langsung ke semua node lainnya. Untuk setiap kasus, memberikan rata-rata jumlah hop antara stasiun. 12.2 Pertimbangkan topologi pohon biner untuk jaringan packet-switching. Simpul akar menghubungkan dua node lain. Semua node intermediate terhubung ke satu simpul dalam arah menuju akar, dan dua arah yang jauh dari root.At bagian bawah adalah node dengan hanya satu link kembali ke akar. Jika ada node, berasal ekspresi untuk jumlah rata-rata hop per paket untuk besar N, dengan asumsi bahwa perjalanan antara semua pasangan simpul sama-sama mungkin. Petunjuk: Anda akan menemukan kesamaan-kesamaan berikut berguna:

12.4 Dalam pembahasan algoritma Dijkstra dalam Bagian 12.3, itu menegaskan bahwa pada setiap iterasi, node baru ditambahkan ke T dan bahwa jalan-biaya setidaknya untuk node baru melewati hanya melalui node sudah T. Menunjukkan bahwa ini benar . Petunjuk: Mulailah dari awal. Tunjukkan bahwa node pertama ditambahkan ke T harus memiliki link langsung ke node sumber. Kemudian menunjukkan bahwa node kedua T baik harus memiliki link langsung ke node sumber atau link langsung ke node pertama ditambahkan ke T, dan sebagainya. Ingat bahwa semua biaya link diasumsikan negatif.12,5 Dalam pembahasan algoritma Bellman-Ford, itu menegaskan bahwa pada iterasi yang jika ada jalan panjang didefinisikan, hop K pertama jalur yang membentuk jalur yang ditetapkan pada iterasi sebelumnya. Menunjukkan bahwa hal ini benar.12.6 Pada langkah 3 dari algoritma Dijkstra, nilai least-cost path hanya diperbarui untuk node belum T. Apakah mungkin bahwa jalan-biaya yang lebih rendah dapat ditemukan node yang sudah di T? Jika demikian, menunjukkan dengan contoh. Jika tidak, berikan alasan

mengapa tidak.12.7 Menggunakan algoritma Dijkstra, menghasilkan rute-biaya terendah ke semua node lain untuk node 2 sampai 6 dari Gambar 12.1. Menampilkan hasil seperti pada Tabel 12.2a.12,8 Ulangi Soal 12.7 dengan menggunakan algoritma Bellman-Ford.12,9 Terapkan algoritma routing Dijkstra ke jaringan pada Gambar 12.11. Menyediakan tabel seperti Tabel 12.2a dan tokoh yang mirip dengan Gambar 12.9.12.10 Ulangi Soal 12.9 dengan menggunakan algoritma Bellman-Ford.Algoritma 12.11 Will Dijkstra dan algoritma Bellman-Ford selalu menghasilkan solusi yang sama? Mengapa atau mengapa tidak?12.13 Dalam Gambar 12.3, simpul 1 mengirimkan sebuah paket ke node 6 menggunakan banjir. Menghitung transmisi satu paket di satu link sebagai beban satu, apa beban total yang dihasilkan jikaa. Setiap membuang simpul duplikat paket yang datang?b. Bidang hop digunakan dan pada awalnya diatur ke 5, dan tidak ada duplikat dibuang?12.14 Hal ini menunjukkan bahwa banjir dapat digunakan untuk menentukan rute minimum-hop. Apakah bisa digunakan untuk menentukan delay rute minimum?12.15 Dengan random routing, hanya satu salinan paket yang ada pada suatu waktu. Namun demikian, akan lebih bijaksana untuk memanfaatkan field.Why hop count?12.16 skema routing yang adaptif lain dikenal sebagai pembelajaran mundur. Sebagai sebuah paket disalurkan melalui jaringan, ia membawa tidak hanya alamat tujuan, namun alamat sumber ditambah jumlah hop berjalan yang bertambah untuk setiap hop. Setiap node membangun tabel routing yang memberikan node berikutnya dan hop count untuk setiap tujuan. Bagaimana informasi paket yang digunakan untuk membangun meja? Apa keuntungan dan kerugian dari teknik ini?12.17 Membangun direktori routing yang terpusat untuk jaringan Gambar 12.11.12.18 Pertimbangkan sistem menggunakan banjir dengan hop counter. Misalkan bahwa hop counter awalnya diatur ke "diameter" dari network.When hop count mencapai nol, paket tersebut akan dibuang kecuali di tempat tujuan. Apakah ini selalu memastikan bahwa paket akan mencapai tujuannya jika ada setidaknya satu jalur beroperasi? Mengapa atau mengapa tidak?