Network Layer Design Issues: Routing Algorithm

Slide1Topics:- Network layer design issues - Routing Algorithm Chapter 5 Network Layer Part 1

Slide21. Network Layer Design Isues  Store-and-Forward Packet Switching  Services Provided to the Transport Layer  Implementation of Connectionless Service  Implementation of Connection-Oriented Service  Comparison of Virtual-Circuit and Datagram Subnets

Slide3Store-and-Forward Packet SwitchingThe environment of the network layer protocols. fig 5-1

Slide4Service Provided to Transport Layer• The  network  layer  provides  services  to  the  transport  layer  at  the network  layer/transport  layer  interface • The  network  layer  services  have  been  designed  with  the following  goals  : 1. The  services  should  be  independent  of  the  router  technology. 2. The  transport  layer  should  be  shielded  from  the  number,  type,  and topology  of  the  routers  present. 3. The  network  addresses  made  available  to  the  transport  layer should  use  a  uniform  numbering  plan,  even  across  LANs  and WANs. • Thus,  t he  designers  of  the  network  layer  have  a  lot  of  freedom in  writing  detailed  specifications  of  the  services  to  be  offered  to the  transport  layer

Slide5Implementation of Connectionless ServiceThe algorithm that manages the tables and makes the routing decisions is called the  routing algorithm

Slide6Implementation of Connection-Oriented ServiceRouting within a virtual-circuit subnet.

Slide7Comparison of Virtual-Circuit andDatagram Subnets 5-4

Slide82. Routing Algorithms • The Optimality Principle • Static Routing  Shortest Path Routing  Flooding • Dynamic Routing  Distance Vector Routing  Link State Routing • Hierarchical Routing • Broadcast Routing • Multicast Routing • Routing for Mobile Hosts • Routing in Ad Hoc Networks

Slide9Routing AlgorithmsIt is sometimes useful to make a distinction between  : • routing , which is making the decision which routes to use, and • forwarding , which is what happens when a packet arrives.

Slide10Routing AlgorithmsRouting algorithms can be grouped into two major classes: a) N on - adaptive  (static) a) N on - adaptive  (static) b) Adaptive   (dynamic) b) Adaptive   (dynamic) In the following sections we will discuss a variety of routing algorithms, both static and   dynamic.

Slide11The Optimality Principle(a)  A subnet.   (b)  A sink tree for router B. Tujuan dari semua algoritma routing adalah untuk menemukan dan menggunakan sink tree bagi seluruh router • If  router J is on the optimal path from router I to router K, then the optimal path from J to K also falls along the same route • Since a sink tree is indeed a tree, it does not contain any loops, so each packet will be delivered within a finite and bounded number of hops

Slide12Static Routing1. Shortest Path Routing 2. Flooding

Slide131. Shortest Path Routing The first 5 steps used in computing the shortest path from A to D. The arrows indicate the working node.

Slide14Dijkstra’s AlgorithmDijkstra's algorithm to compute the shortest path through a graph. 5-8 top  

Slide15Dijkstra’s Algorithm (2) Dijkstra's algorithm to compute the shortest path through a graph. 5-8 bottom

Slide162. Flooding   Setiap paket yang masuk dikirimkan melalui saluran keluar kecuali saluran tempat paket tersebut datang. Problems vs Solution • Age    H op counter • More flood    Sequence number • Duplication    Limit the sequence number, by  augmenting with a counter Distributed database applications,  wireless networks,  a metric against which other routing algorithms can be compared

Slide17Dynamic routing1. Distance Vector Routing 2. Link State Routing

Slide181. Distance Vector Routing (a)  A subnet.  (b)  Input from A, I, H, K, and the new routing table for J. Setiap router menjaga sebuah tabel routing yang di indeks oleh masing2 router pada subnet dan berisi sebuah entry bagi setiap router di dalam subnet. Entry ini berisi : - Saluran keluar untuk mencapai tujuan - Estimasi waktu atau jarak ke tujuan itu

Slide19Distance Vector Routing (2)The count-to-infinity problem. Routing bereaksi cepat untuk berita baik Routing bereaksi sgt lambat utk berita buruk Solusi: menetapkan nilai tertinggi

Slide202. Link State Routing Pengembangan kapasitas saluran yg berbeda mengharuskan untuk memperhitungkan bandwidth sbg parameter. Solusinya :  link state routing Each router must do the following: 1. Discover its neighbors, learn their network address. 2. Measure the delay or cost to each of its neighbors. 3. Construct a packet telling all it has just learned. 4. Send this packet to all other routers. 5. Compute the shortest path to every other router.

Slide211-Learning about the Neighbors (a)  Nine routers and a LAN.  (b)  A graph model of  (a). - Ketika router di boot ! - Paket “hello” via P2P - Nama router harus unik

Slide222-Measuring Line Cost A subnet in which the East and West parts are connected by two lines. Lintasan  yg tdk berbeban sbg rute --> unjuk kerja meningkat Memperhitungkan delay? Routing berosilasi scr tdk teratur, routing mjd tdk menentu

Slide233-Building Link State Packets (a) A subnet.  (b) The link state packets for this subnet. Kapan membuatnya?

Slide244-Distributing the Link State Packets The packet buffer for router B in the previous slide (Fig.  5-13). Tumpang tindih? 32 bit ! - Router tabrakan/ duplikat - Nmr urut rusak

Slide255-Computing the New Routes Router membuat graf subnet keseluruhan  Algoritma dijkstra dpt dioperasikan scr lokal utk menentukan lintasan terpendek.  Memori yg dibutuhkan sebanding dengan kn, dg n= jumlah router, dan k= jumlah tetangga tiap router  Bila subnet sangat besar? Memori?

Slide26Hierarchical RoutingHierarchical routing. Tabel routing bertambah: - Konsumsi memori router - Waktu penulusuran 720 Router = Berapa entry? - Tanpa hirarki -  24 wilayah @ 30 router -  8 cluster@ 9 wilyh @10 rou

Slide27Broadcast RoutingReverse path forwarding.   (a)  A subnet.   (b)  a Sink tree.   (c)  The tree built by reverse path forwarding.

Slide28Multicast Routing    (a)  A network.    (b)  A spanning tree for the leftmost router. (c)  A multicast tree for group 1.   (d)  A multicast tree for group 2.

Slide29Routing for Mobile HostsA WAN to which LANs, MANs, and wireless cells are attached.

Slide30Routing for Mobile Hosts (2)Packet routing for mobile users.