Routing skema |
---|
anycast |
siaran |
multicast |
unicast |
geocast |
Skema routing yang
berbeda dalam semantik pengiriman mereka:
- unicast memberikan pesan ke node tertentu tunggal;
- siaran memberikan pesan ke semua node dalam jaringan;
- multicast memberikan pesan kepada sekelompok node yang telah menyatakan minatnya dalam menerima pesan tersebut;
- anycast memberikan pesan untuk setiap keluar salah satu dari sekelompok node, biasanya yang terdekat ke sumber.
- geocast memberikan pesan ke wilayah geografis
Unicast adalah bentuk
dominan dari pengiriman pesan di Internet, dan artikel ini berfokus pada
algoritma routing unicast.
Topologi
distribusi
Dalam praktek yang
dikenal sebagai routing statis (atau non-adaptif routing), jaringan kecil dapat
menggunakan tabel routing dikonfigurasi secara manual. Jaringan yang lebih
besar memiliki kompleks topologi yang dapat berubah dengan cepat, membuat
konstruksi tabel routing manual tidak layak. Namun demikian, sebagian besar masyarakat
beralih jaringan telepon (PSTN) menggunakan pra-dihitung tabel routing, dengan
rute mundur jika rute yang paling langsung tersumbat (lihat routing di PSTN ). Adaptive Routing , atau
routing dinamis, upaya untuk memecahkan masalah ini dengan membangun tabel
routing otomatis, berdasarkan informasi yang dibawa oleh protokol routing , dan
memungkinkan jaringan untuk bertindak secara otonom dalam menghindari hampir
kegagalan jaringan dan penyumbatan.
Contoh algoritma
adaptif-routing adalah Routing Information Protocol ( RIP ) dan Open-protokol
Shortest-Path-First ( OSPF ). Adaptif routing yang mendominasi internet. Namun,
konfigurasi routing protokol seringkali memerlukan sentuhan yang terampil,
teknologi jaringan belum dikembangkan ke titik otomatisasi lengkap routing.
algoritma
distance vector
Artikel utama: Jarak-vector routing protokol
Jarak vektor
menggunakan algoritma Bellman-Ford algoritma. Pendekatan ini memberikan nomor, biaya,
kepada masing-masing hubungan antara setiap node dalam jaringan. Node akan
mengirimkan informasi dari titik A ke titik B melalui jalan yang menghasilkan total
biaya terendah (yaitu jumlah biaya dari link antara node digunakan).
Algoritma ini
beroperasi dengan cara yang sangat sederhana. Ketika sebuah node pertama
dimulai, hanya tahu dari tetangganya, dan biaya langsung yang terlibat dalam
menjangkau mereka. (Ini informasi, daftar tujuan, biaya total untuk
masing-masing, dan hop berikutnya untuk mengirim data ke sana, membentuk
tabel routing, atau tabel jarak.) Setiap node, secara teratur,
masing-masing mengirim ke tetangga nya Ide saat ini sendiri total biaya untuk
sampai ke semua tujuan itu mengetahui. Node tetangga (s) memeriksa informasi
ini, dan bandingkan dengan apa yang telah mereka 'tahu', apa pun yang merupakan
perbaikan pada apa yang telah mereka miliki, mereka memasukkan dalam tabel
routing yang mereka sendiri (s). Seiring waktu, semua node dalam jaringan akan
menemukan hop berikutnya yang terbaik untuk semua tujuan, dan total biaya
terbaik.
Ketika salah satu
dari node yang terlibat turun, mereka node yang digunakan sebagai hop
berikutnya mereka untuk tujuan tertentu membuang entri tersebut, dan membuat
baru tabel routing informasi. Mereka kemudian meneruskan informasi ini ke semua
node yang berdekatan, yang kemudian ulangi proses. Akhirnya semua node dalam
jaringan menerima informasi terbaru, dan kemudian akan menemukan jalan baru
untuk semua tujuan yang mereka masih bisa "mencapai".
algoritma
link-state
Artikel utama:
Ketika menerapkan
algoritma link-state, setiap node menggunakan sebagai data fundamentalnya suatu
peta dari jaringan dalam bentuk grafik . Untuk menghasilkan ini, setiap banjir
simpul jaringan dengan informasi tentang apa yang lainnya node dapat terhubung
ke seluruh, dan kemudian masing-masing node independen merakit informasi ini
menjadi sebuah peta. Menggunakan peta ini, maka setiap router secara independen
menentukan jalur paling-biaya dari dirinya ke setiap node lain menggunakan
standar jalur terpendek algoritma seperti algoritma Dijkstra . Hasilnya adalah
sebuah pohon berakar di node saat ini seperti bahwa jalan melalui pohon dari
akar ke node lain adalah jalur paling-biaya untuk simpul tersebut. Pohon ini
kemudian berfungsi untuk membangun tabel routing, yang menentukan hop
berikutnya yang terbaik untuk mendapatkan dari node saat ini ke node lain.