Internetworking: Routing
Teknologi Komunikasi Data
Fakultas Ilmu Komputer Universitas Indonesia Semester 2003/2004 Versi: 1.01
Agenda Problem: There is more than one network! Simple Internetworking (Bab 4.1) Routing (Bab 4.2) • Network as a Graph (Bab 4.2.1) • Link State (Bab 4.2.3) • Distance Vector (Bab 4.2.2)
2
Versi: 1.01
1
Internet Structure (1/2) Internet tidak terstruktur dalam satu jaringan tunggal Koleksi dari berbagai jaringan: dengan administrasi/pengelolaan yang berbeda.
Logikal: terbagai atas autonomous system (AS): Dikelola oleh suatu administrasi tunggal. Memiliki IP prefix (network number) yang resmi. AS melakukan interkoneksi dengan AS yang lain dan membentuk suatu internetworking global. 3
Versi: 1.01
Internet Structure (2/2) Internet Today := a collection of Autonomous Systems Large corporation Large corporation
Peering Peering Point Point
AS2 AS7 Consumer ISP Consumer ISP
Small corporation Small corporation
AS1 AS6 4
Consumer ISP Consumer ISP
Backbone Service Backbone Service Provider AS3 Provider AS3 Large corporation Large corporation
Peering Point Peering Point
Campus Campus Consumer ISP Consumer ISP
AS4 AS5 Versi: 1.01
2
Routing vs Forwarding Forwarding vs. Routing forwarding: memilih output post berdasarkan alamat tujuan dan tabel routing routing: proses dimana tabel routing tersebut dibuat (perlu struktur data, algoritma dan pertukaran informasi dgn router yang lain). Contoh entry dari tabel routing: Network Number 10
Next Hop 171.69.245.10
Contoh entry dari tabel forwarding: Network Number 10
Interface if0
MAC Address 8:0:2b:e4:b:1:2
5
Versi: 1.01
Routing & Forwarding in a router routing information base
Routing protocol: packet exchange
routing process
forwarding table
routing control traffic
forwarding process
6
Versi: 1.01
3
Routing Domains Autonomous System (AS) Intra-AS routing Inter-AS routing Border Routers
Interdomain level
Internet Service Provider
Border Routers
Autonomous System or Domain LAN level
Figure 7.7
Intradomain Level
7
Versi: 1.01
Intra-AS and Inter-AS routing C.b
a
C
b
A.a
Inter-AS routing between A and B A.c
a
B.a a
c B
Host h2 b
d Intra-AS routing c b A within AS B Intra-AS routing within AS A • Intra-AS routing: • contoh: OSPF (Open Shortest Path First) • Inter-AS routing: • contoh: BGP (Border Gateway Protocol) Host h1
8
Versi: 1.01
4
Routing questions..?? Bagaimana menentukan “path terbaik”? Istilah “terbaik” (best routes) dapat mempunyai macam-macam sudut pandang Misal: minimum host, least congested, lowest delay, most reliable?
Bagaimana issue skalabilitas (jutaaan hosts/router)? Minimize control messages and routing table size
Bagaimana routing beradaptasi terhadap kegagalan atau perubahan? Node and link failures, plus message loss 9
Versi: 1.01
Networks as a Graph Network G as a Graph: G = (V, E ) ; V = {A, B, C, D, E, F} ; E = {(A,B), ... }; c(i, j) := “cost” on link (i, j);
Routing Problem: Cari cost path yang paling rendah antara dua simpul (s, t) ∈ E Intra domain routing: E merupakan satu bagian dari Autonomous Systems;
A
Factors static: topology (slowly changing) dynamic: load (may fluctuate drastically).
4 C
10
6
1
3
2
1
B 9
E
F
1 D
Versi: 1.01
5
Routing challenges Ideal approach: menyimpan informasi dari setiap link jaringan menentukan “fastest path” antara setiap pasangan (setiap arah: bandwidth, latency dan queueing delay).
Global knowledge Sulit untuk mengumpulkan data lengkap Dinamika informasi: up-to-date informasi
Local knowledge-- inconsistencies cause: Loops: sirkulasi traffic 11
Versi: 1.01
Static vs Dynamic Static: Perhitungan “shortest path” dilakukan sekali dan di load pada storages nodes => centralized Masalah: terputusnya link? penambahan link baru? perubahan cost (congested)?
Dynamic & Distributed Pertukaran informasi antara nodes (up-dated) dapat disebarkan (dynamic) Routing protocol: mengatur tata-cara penyebaran informasi tsb. Protocol bersifat distributed => masing-masing router melakukan perhitungan (update) routing table. 12
Versi: 1.01
6
Link State Routing Class: intra-domain routing protocol Setiap node mempunyai informasi state (cost, up & down dsb) dari link ke tetangga. Pertukaran informasi ini membantu membuat tabel routing pada suatu node.
Link State Routing: Informasi tidak terbatas pertukaran antar tetangga tapi informasi suatu link dikirimkan ke semua node dalam jaringan Suatu node akan mempunyai informasi lengkap hubungan antar node-node dan cost pada jaringan. 13
Versi: 1.01
Link State Routing Distributed & Dynamic: Penyebaran bentuk jaringan dan state (cost) link ke semua node (flooding) Beritahukan semua router lainnya apa yang diketahuinya tentang topologi lokal-nya
Hitung shortest-path dari node tsb ke semua node dalam jaringan. Jika telah mempunyai informasi lengkap (bentuk jaringan) => algoritma untuk menghitung cost terendah mencapai node yang lain. 14
Versi: 1.01
7
Link-state protocol Data struktur: Link state packet (LSP) ID dari node yang membuat paket LSP Daftar dari “direct neighbors” dan cost ke tetangga tsb (vektor: distance, neighbor). Nomor Urut update (SEQ), informasi terbaru Time-to-live (TTL): mencegah sirkulasi paket
Setiap node: menyimpan semua LSP yang diterima & terbaru dari setiap node dalam jaringan: • decrement TTL of stored LSP; discard when TTL = 0
membuat LSP baru dengan nomor urut bertambah (SEQ), secara periodik atau jika topologi berubah. 15
Versi: 1.01
Flooding Setiap LSP harus disampaikan ke semua node Teknik Flooding: Forward each received LSP to all neighbor nodes but the one that sent it use the source-ID and SEQ in a LSP to detect duplicates
16
Versi: 1.01
8
Routing Computation Setiap node menghitung “shortest path” ke semua node yang lain Dijkstra’s algorithm Informasi “NextHop” => digunakan untuk forwarding table.
Dijkstra Algorithm: Direct graph dengan cost pada setiap edges/links Link cost diketahui pada semua nodes: • Flooding link state info.
Hitung “least cost” dari node tsb ke semua node yg lain. 17
Versi: 1.01
Basic Basic: Mulai dari suatu set M, dengan node awal {s}, Init tabel cost path C(s,n) ke node lain yang dapat dihitung cost-nya (reachable). Hitung/pilih node dengan lowest cost => c(w) dan tambahkan ke set M. Update tabel cost path C, dengan memasukkan cost melalui node w. 18
B
3
5 A
10 11
C
2 D
Versi: 1.01
9
Dijkstra’s Shortest – Path Algorithm Let N denotes set of nodes in the graph c (i, j) denotes non-negative cost (weight) for edge (i, j) s denotes this node M denotes the set of nodes incorporated so far C(n) denotes cost of the path from s to node n
M = {s} ; for each n ∈ N – {s} do C(n) = c(s, n) ;
while (N ≠ M) do
M = M ∪ {w} such that C(w) := min{C(x)} for all x ∈(N – M) ;
for each n ∈(N – M) do C(n) = min{C(n), C(w) + c(w, n )}; 19
Versi: 1.01
Dijsktra’s Algorithm 1 Initialization: 2 M = {s} ; 3 for all nodes v do 4 if v adjacent to s then 5 C(v) = c(s, v ) ; 6 else C(v) = ∞ ; end
7 8 Loop 9 find w ∉ M such that C(w) is a minimum ; 10 add w to M ; 11 for all v adjacent to w and not in M do 12 update C(v): C(v) = min{ C(v), C(w) + c(w, v) } 13 /* new cost to v is either old cost to v or known 14 shortest path cost to w plus cost from w to v */ end 15 Until ( all nodes in set M ) 20
Versi: 1.01
10
Djikstra Algorithm: Example B 3
5
C
10 11
A
2
D Node D: start “confirmed list” : D (lihat informasi LSP dari D) Key-- yellow = tentative blue = confirmed Versi: 1.01
Djikstra Algorithm: Example B 11
5
3
C
10 A
11
2 2
0
D
Confirmed list : D LSP’s D: mencapai B melalui B cost 11, C cost 2 Tentative list: B dan C Pilih cost dari tentative list yang terendah C => confirmed list Versi: 1.01
11
Djikstra Algorithm: Example B 11
5
3
C
10
2
11
A
2 0
D
“Confirmed list” : D, C, LSP’s C: mencapai B melalui C cost 3, A cost 10 Bandingkan cost yang ada (tentative list): B (11), update cost pada tentative list sesuai dengan cost terendah Versi: 1.01
Djikstra Algorithm: Example B 5
5
3 10
12 A
C
11
2 2
0
D
“Confirmed list” : D, C, LSP’s C: mencapai B melalui C cost 5 (2+3), A cost 12 Update cost pada Tentative list: B (cost 5), A (cost 12) Bandingkan dan pilih cost yang terendah Tentative list => B Versi: 1.01
12
Djikstra Algorithm: Example B 5
5
3
C
10
12
2
11
A
2 0
D
“Confirmed list” : D, C, B LSP’s B: mencapai A melalui B cost 5 Bandingkan cost yang ada (tentative list): A (12), update cost pada tentative list sesuai dengan cost terendah Versi: 1.01
Djikstra Algorithm: Example B 5
5
3 10
10 A
C
11
2 2
0
D
“Confirmed list” : D, C, B LSP’s B: cost A melalui C, B: cost 10 Updat cost Tentative list: A = 10, Pilih cost yang terendah dari node pada Tentative List => A Versi: 1.01
13
Djikstra Algorithm: Example B 5
5
3 10
10 A
C
11
2 2
0
D
“Confirmed list” : D, C, B, A Tentative list = tidak ada node lagi => selesai Versi: 1.01
Distance Vector Link State (LS) Dijkstra: dengan informasi lengkap cost semua link. Each network periodically floods immediate reachability information to all other routers Fast convergence, but high communication and computation overhead
Distance Vector (DV) Bellman-Ford’s single source shortest path Each neighbor periodically exchange reachability information to its neighbors Minimal communication overhead, but it takes long to converge, i.e., in proportion to the maximum path length 28
Versi: 1.01
14
Distance vector Setiap node menyimpan: array (vektor): cost dari node tsb ke setiap node yang lain
Pengumpulan informasi: Awal: cost pada link (edges) mulai dari informasi node tsb. Kirim “distance vector” ke semua tetangga nodes => “advertising routes” Pertukaran “updates” dengan tetangga • periodically (orde detik sampai menit) • whenever table changes (called triggered update) 29
Versi: 1.01
Distance vector: Basic (1) Assume all links bi-directional, with cost of “1” A’s initial routing table
B
Dest
C A D E
F
G
B C D E F G
Cost
Next Hop 1 B 1 C infinite 1 E 1 F infinite -
1. Node A mengirimkan array tabel ke: B, C, E, F 30
Versi: 1.01
15
Distance vector: Basic (2) 2. Node A menerima dari F => cost ke G adalah 1, Node A menyimpulkan cost ke G sekarang melalui F adalah 2 (jumlah cost: AF + FG). Karena 2 < ∞ ; update cost AG = 2. 3. Node A juga mendapat informasi untuk D, dapat melalui C (cost = 2) => update. Untuk B melalui C, lebih besar dari A langsung ke B tidak dilakukan update. Proses protokol routing untuk mencapai keadaan stabil/konsisten (tidak ada perubahan lagi) => convergence. Setiap node hanya mempunyai informasinya sendiri (distributed). 31
Versi: 1.01
Routing – I: Distance Vector Algorithms Each node maintains a set of triplets: (Destination, Cost, NextHop)
Exchange updates with directly connected neighbors periodically (on the order of several seconds, 30sec ) whenever its table changes (called triggered update)
Each update is a list of pairs: (Destination, Cost)
Update local table if receive a “better” route smaller cost came from next-hop
Refresh existing routes; delete if they time out 32
Versi: 1.01
16
Distance Vector Routing: overview Iterative and
Asynchronous: each local iteration caused by:
Each node i
local link cost change message from neighbor: its least cost path change from neighbor
wait for (change in local link cost or msg from neighbor)
Distributed: each node
notifies neighbors only when its least cost path to any destination changes
neighbors then notify their neighbors if necessary
recompute distance table if (least cost path to any dest has changed) then notify neighbors
33
Versi: 1.01
Distance Vector Algorithm Each node X do 1 Initialization: 2 for all adjacent nodes v do /* ‘*’ means “for all rows” */ 3 DX (*, v) = ∞ ; 4 DX (v, v) = c(X, v) ; end 5 for all destinations y do 6 send minw {DX (y, w)} to each neighbor /* w over all X's neighbors */
34
Versi: 1.01
17
