Chapter 3 part 3
Internetworking (Routing) Muhammad Al Makky
Pembahasan Chapter 3 • Memahami fungsi dari switch dan bridge • Mendiskusikan Internet Protocol (IP) untuk interkoneksi jaringan • Memahami konsep dari routing
Outline • Routing – Network as a Graph – Distance Vector – Link State
Routing • Forwarding vs Routing Routing
Forwarding
• Proses pembuatan routing table
• Memilih port keluar berbasis alamat tujuan dan routing table
• Forwarding Table vs Routing Table Routing Table
• Dibuat melalui algoritma routing sebagai dasar membuat forwarding table • Tabel berisi pemetaan dari jaringan ke “NextHop”
Forwarding table
• Digunakan saat paket diteruskan ke tujuan sehingga harus mengandung informasi yang lengkap • Tabel berisi pemetaan jaringan ke outgoing interface dan informasi MAC (Ethernet Address dari “NextHop”)
Routing
Contoh (a) routing table (b) forwarding tables
Routing • Network as a Graph
• Masalah dalam routing adalah untuk menemukan cost jalur terendah (terpendek) antara 2 (dua) node – Cost adalah jumlah seluruh cost dari edge yang membentuk jalur
Routing • Pada jaringan sederhana dapat dilakukan perhitungan jalur terpendek dan menyimpannya di setiap node. Masalah yang terjadi – Tidak dapat mengetahui kesalahan pada node atau link – Tidak mempertimbangkan apabila terdapat tambahan node atau link baru – Cost edge tidak dapat diubah
• Maka – Dibutuhkan distributed and dynamic protocol – 2 (dua) kelas utama protokol • Distance Vector • Link State
Distance Vector • Setiap node membentuk array 1 (satu) dimensi (Vektor) berisi “distances” (cost) ke semua node dan mendistribusikan vektor ke node terdekat dengan segera • Asumsi: setiap node mengetahui cost dari link ke setiap node terdekat
Distance Vector
“Initial distance” disimpan di setiap node
“Initial routing table” pada node A
Distance Vector • Algoritma routing “distance vector” disebut juga sebagai “Bellman-Ford algorithm” • The next step… – every node sends a message to its directly connected neighbors containing its personal list of distances
• UPDATE: – Periodic: each node automatically sends an update message every so often, even if nothing has changed – Triggered: happens whenever a node notices a link failure or receives an update from one of its neighbors that causes it to change one of the routes in its routing table
Distance Vector
“Final routing table” pada node A
“Final distances” disimpan di setiap node
Distance Vector • Saat node mendeteksi terdapat gangguan link 1. F mendeteksi bahwa link ke G gagal 2. F menetapkan “distance” ke G menjadi tak hingga dan mengirim update ke A 3. A menetapkan “distance” ke G menjadi tak hingga 4. A menerima update secara periodik dari C dengan 2 hop ke G 5. A menetapkan “distance” ke G menjadi 3 dan mengirim update ke F 6. F memutuskan bahwa dapat menggapai G dalam 4 hop melalui A
Count-to-infinity Problem • Menggunakan “relatively small number” sebagai perkiraan tak hingga • Teknik untuk meningkatkan waktu penstabilan routing disebut “split horizon” – Node tidak mengirim balik apa yang route itu pelajari dari node tersebut – Contoh: B memiliki route (E, 2, A) dalam tabel, diketahui bahwa route tersebut dipelajari dari A, sehingga saat B mengirim update routing ke A maka tidak akan mengikutsertakan route (E, 2) dalam update tersebut
• Versi atas dari “split horizon”, disebut split “horizon with poison reverse” – B sebenarnya mengirim balik route ke A tetapi memberikan informasi negatif di dalam route untuk memastikan bahwa A tidak akan menggunakan B untuk mencapai E – Contoh: B mengirim route (E, ∞) ke A
Routing Information Protocol (RIP)
Example Network running RIP
RIPv2 Packet Format
Link State Routing • Strategi: Mengirim informasi ke semua node mengenai link yang langsung terhubung (bukan seluruh routing table) • Link State Packet (LSP) – – – –
ID dari node yang membuat LSP Cost dari link yang langsung terhubung dengan node terdekat sequence number (SEQNO) time-to-live (TTL) untuk paket
• 2 (dua) mekanisme: – Reliable Flooding – Route Calculation
Link State • Reliable Flooding – – – – –
store most recent LSP from each node forward LSP to all nodes but one that sent it generate new LSP periodically; increment SEQNO start SEQNO at 0 when reboot decrement TTL of each stored LSP; discard when TTL=0
Link State • Route Calculation – Based on Dijkstra’s shortest-path algorithm
• Forward Search algorithm – Specifically each switch maintains two lists, known as Tentative and Confirmed – Each of these lists contains a set of entries of the form (Destination, Cost, NextHop)
Shortest Path Routing • Forward Search Algorithm – Initialize the Confirmed list with an entry for myself; this entry has a cost of 0 – For the node just added to the Confirmed list in the previous step, call it node Next, select its LSP – For each neighbor (Neighbor) of Next, calculate the cost (Cost) to reach this Neighbor as the sum of the cost from myself to Next and from Next to Neighbor • If Neighbor is currently on neither the Confirmed nor the Tentative list, then add (Neighbor, Cost, Nexthop) to the Tentative list, where Nexthop is the direction I go to reach Next • If Neighbor is currently on the Tentative list, and the Cost is less than the currently listed cost for the Neighbor, then replace the current entry with (Neighbor, Cost, Nexthop) where Nexthop is the direction I go to reach Next
– If the Tentative list is empty, stop. Otherwise, pick the entry from the Tentative list with the lowest cost, move it to the Confirmed list, and return to Step 2.
Shortest Path Routing
Open Shortest Path First (OSPF)
– OSPF Header Format
OSPF Link State Advertisement
Summary Switching and Bridging • Datagrams (Connectionless), Virtual Circuit (Connection-oriented), Source Routing, Spanning Tree
Internet Protocol • IP Service Model, Global Addresses, Datagram Forwarding, Subnetting dan Classless Addressing, Address Translation (ARP), Host Configuration (DHCP), Error Reporting (ICMP), Virtual Networks dan Tunnel
Routing • Network as a Graph, Distance Vector (Split Horizon), Link State (Reliable Flooding, Route Calculation)
