Slide #1.

Routing Primer Internet of Things Fall 2015
More slides like this


Slide #2.

Routing Outline        Overview of Point-to-Point Routing (WAN) Routing Algorithm Classification Distance Vector Routing Link State Routing RIP OSPF BGP Internet of Things Routing Primer 2
More slides like this


Slide #3.

Metropolitan Area Network (MAN) Organization Servers Gatewa y To the Internet or wide area network s Backbon e R R Departmental Server R s R S S S R R s s s s s s s s s Leon-Garcia & Widjaja: Communication Networks Internet of Things Routing Primer 3
More slides like this


Slide #4.

Wide Area Network (WAN) Interdomain level Border routers Autonomous system or domain Border routers Internet service provider LAN level Leon-Garcia & Widjaja: Communication Networks Intradomain level Internet of Things Routing Primer 4
More slides like this


Slide #5.

Modern Internet Backbone National service provider A National service provider B NAP NAP National service provider C Network Access Point National Internet Service Providers Leon-Garcia & Widjaja: Communication Networks Internet of Things Routing Primer 5
More slides like this


Slide #6.

Network Layer      transport segment from sending to receiving host. on sending side, encapsulates segments into datagram packets. on receiving side, delivers segments to transport layer. network layer protocols in every host, router. router examines Things header fieldsInternet in allofIP applicatio n transport network data link physical network data link physical network data link physical network data link physical network data link physical network data link physical network network data link data link physical physical network data link physical network data link physical network data link physical network data link physical applicatio n transport network data link physical K&R Routing Primer 6
More slides like this


Slide #7.

Two Key Network Layer Functions   forwarding: move analogy: packets from  routing: process of router’s input to planning trip from appropriate source to router output. destination routing: determine route taken by packets from source to destination. Internet of Things  forwarding: process of getting through single interchange Routing Primer 7
More slides like this


Slide #8.

Interplay between Routing and Forwarding routing algorithm Routing creates the tables. local forwarding table header value output link 0100 0101 0111 1001 Forwarding uses the tables. 3 2 2 1 value in arriving packet’s header 1 0111 3 2 K&R Internet of Things Routing Primer 8
More slides like this


Slide #9.

Router Node Forwarding node 15 Routing table lookup 134 17 packet packet Incoming Link 17 Outgoing Link Router Link Buffer Internet of Things Server Routing Primer 9
More slides like this


Slide #10.

The Internet Network Layer Host, router network layer functions: Transport Layer: TCP, UDP Network Layer IP protocol • addressing conventions • datagram format • packet handling conventions Routing protocols • path selection • RIP, OSPF, BGP forwarding table ICMP protocol • error reporting • router “signaling” Data Link Layer Physical Layer Internet of Things Routing Primer 10
More slides like this


Slide #11.

Routing Algorithm Classification Internet of Things
More slides like this


Slide #12.

Routing Routing algorithm:: that part of the Network Layer responsible for deciding on which output line to transmit an incoming packet. Remember: For virtual circuit subnets the routing decision is made ONLY at set up. Algorithm properties:: correctness, simplicity, robustness, stability, fairness, optimality, and scalability. Internet of Things Routing Primer 12
More slides like this


Slide #13.

Routing is Graph Theory Problem edges have costs Figure 3.28 Network represented as a graph. Internet of Things Routing Primer 13
More slides like this


Slide #14.

Routing Classification Adaptive Routing based on current measurements of traffic and/or topology. 1. centralized 2. isolated 3. distributed Internet of Things Non-Adaptive Routing routing computed in advance and off-line 1. flooding 2. static routing using shortest path algorithms Routing Primer 14
More slides like this


Slide #15.

Flooding  Pure flooding :: every incoming packet to a node is sent out on every outgoing line. – Obvious adjustment – do not send out on arriving link (assuming full-duplex links). – The routing algorithm can use a hop counter (e.g., TTL) to dampen the flooding. – Selective flooding :: only send on those lines going “approximately” in the right direction. Internet of Things Routing Primer 15
More slides like this


Slide #16.

Centralized Routing A W RCC B Z Internet of Things Routing Primer 16
More slides like this


Slide #17.

Internetwork Routing [Halsall] Adaptive Routing Centralized [RCC] Distributed [IGP] Intradomain routing Interior Gateway Protocols Isolated Interdomain routing[EGP] [BGP,IDRP] Exterior Gateway Protoco Distance Vector routing Link State routing [RIP] [OSPF,IS-IS,PNNI] Internet of Things Routing Primer 17
More slides like this


Slide #18.

Adaptive Routing Design Design Issues: 1. How much overhead is incurred due to gathering the routing information and sending routing packets? 2. What is the time frame (i.e, the frequency) for sending routing packets in support of adaptive routing? 3. What is the complexity of the routing strategy? Internet of Things Routing Primer 18
More slides like this


Slide #19.

Adaptive Routing Basic functions: 1. Measurement of pertinent network data {e.g. the cost metric}. 2. Forwarding of information to where the routing computation will be done. 3. Compute the routing tables. 4. Convert the routing table information into a routing decision and then dispatch the data packet. Internet of Things Routing Primer 19
More slides like this


Slide #20.

Shortest Path Routing 1. Bellman-Ford Algorithm [Distance Vector] 2. Dijkstra’s Algorithm [Link State] What does it mean to be the shortest (or optimal) route? We need a cost metric (edges in graph): a. Minimize the number of hops along the path. b. Minimize the mean packet delay. c. Maximize the network throughput. Internet of Things Routing Primer 20
More slides like this


Slide #21.

Distance Vector Routing {Tanenbaum & Perlman version} Internet of Things
More slides like this


Slide #22.

Distance Vector Routing Historically known as the old ARPANET routing algorithm {or known as Bellman-Ford (BF) algorithm}. BF Basic idea: each router maintains a Distance Vector table containing the distance between itself and ALL possible destination nodes. Distances,based on a chosen metric, are computed using information from the neighbors’ distance vectors. Internet of Things Routing Primer 22
More slides like this


Slide #23.

Distance Vector Routing 1. 2. Information kept by DV router each router has an ID associated with each link connected to a router, there is a link cost (static or dynamic). Distance Vector Table Initialization Distance to itself = 0 Distance to ALL other routers = infinity number Internet of Things Routing Primer 23
More slides like this


Slide #24.

Distance Vector Algorithm [Perlman] 1. A router transmits its distance vector to each of its neighbors in a routing packet. 2. Each router receives and saves the most recently received distance vector from each of its neighbors. 3. A router recalculates its distance vector when: a. It receives a distance vector from a neighbor containing different information than before. b. It discovers that a link to a neighbor has gone down (i.e., a topology change). The DV calculation is based on minimizing the cost Routing to each Internet of Things Primer 24
More slides like this


Slide #25.

Distance Vector Example Figure 5-9.(a) A subnet. (b) Input from A, I, H, K, and the new routing table for J. Tanenbaum Internet of Things Routing Primer 25
More slides like this


Slide #26.

Distance Vector Routing {Kurose & Ross version} Internet of Things
More slides like this


Slide #27.

Distance Vector Algorithm Bellman-Ford Equation (dynamic programming) Define dx(y) := cost of least-cost path from x to y Then v dx(y) = min {c(x,v) + dv (y)} where min is taken over all neighbors v of x. Internet of Things Routing Primer 27
More slides like this


Slide #28.

Bellman-Ford Example 5 u 2 v 2 3 Clearly, dv(z) = 5, dx(z) = 3, dw(z) = 3 w 5 3 1 z B-F equation says: du(z) = min { c(u,v) + dv(z), 1 c(u,x) + dx(z), c(u,w) + dw(z) } = min {2 + 5, 1 + 3, The node that achieves minimum is next5 + 3} = 4 hop in shortest path ➜ forwarding table. Namely, packets from u destined for z are forwarded out link between u and x. 1 x y 2 Internet of Things Routing Primer 28
More slides like this


Slide #29.

Distance Vector Algorithm     Dx(y) = estimate of least cost from x to y Node x knows cost to each neighbor v: c(x,v) Node x maintains distance vector Dx = [Dx(y): y є N ] Node x also maintains its neighbors’ distance vectors – For each neighbor v, x maintains Dv = [Dv(y): y є N ] Internet of Things Routing Primer 29
More slides like this


Slide #30.

Distance Vector Algorithm DV Basic idea:  From time-to-time, each node sends its own distance vector estimate to neighbors.  Asynchronous  When a node x receives a new DV estimate from any neighbor v, it saves v’s distance vector and it updates its own DV using B-F equation: Dx(y) ← min {c(x,v) + Dv(y)} for each node y ∊ N v  Under minor, natural conditions, the estimate Dx(y) converges to the actual least cost dx(y). Internet of Things Routing Primer 30
More slides like this


Slide #31.

Distance Vector Algorithm Iterative, asynchronous: each   local iteration caused by: local link cost change DV update message from neighbor Distributed:  each node notifies neighbors only when its DV changes – neighbors then notify their neighbors if necessary. Internet of Things Each node: wait for (change in local link cost or msg from neighbor) recompute estimates if DV to any destination has changed, notify neighbors Routing Primer 31
More slides like this


Slide #32.

from x 0 2 7 y ∞∞ ∞ z ∞∞ ∞ node y table cost to x y z from Dx(y) = min{c(x,y) + Dy(y), c(x,z) + Dz(y)} Dx(z) = min{c(x,y) + Dy(z), c(x,z) + Dz(z)} = min{2+0 , 7+1} = 2 node x table = min{2+1 , 7+0} = 3 cost to cost to x y z x y z x 0 2 3 y 2 0 1 z 7 1 0 2 x ∞∞ ∞ y 2 0 1 z ∞∞ ∞ node z table cost to x y z from from x x ∞∞ ∞ y ∞ ∞ ∞ z 7 1 0 Internet of Things time Routing Primer y 7 1 z 32
More slides like this


Slide #33.

Dx(y) = min{c(x,y) + Dy(y), c(x,z) + Dz(y)}Dx(z) = min{c(x,y) + Dy(z), c(x,z) + Dz(z)} = min{2+0 , 7+1} = 2 node x table = min{2+1 , 7+0} = 3 x 0 2 7 y ∞∞ ∞ z ∞∞ ∞ node y table ∞ cost to x y z x 0 2 3 y 2 0 1 z 7 1 0 x 0 2 3 y 2 0 1 z 3 1 0 x 0 2 7 y 2 0 1 z 7 1 0 x 0 2 3 y 2 0 1 z 3 1 0 from from cost to x y z x 0 2 7 y 2 0 1 z 3 1 0 Internet of Things 2 x y 7 1 z cost to x y z from x ∞∞ ∞ y ∞ ∞ ∞ z 71 0 cost to x y z cost to x y z from from from x ∞ ∞ ∞ y 2 0 1 z ∞∞ ∞ node z table cost to x y z from cost to x y z from cost to x y z from cost to x y z x 0 2 3 y 2 0 1 z 3 1 0 time Routing Primer 33
More slides like this


Slide #34.

Distance Vector: Link Cost Changes Link cost changes:  node detects local link cost change.  updates routing info, recalculates 1 y 4 1 x 50 z distance vector. At time t0, y detects the link-cost change, updates  if DV changes, it notifies its DV, and informs its neighbors. neighbors . “good At time t1, z receives the update from y and updates its news table. travels It computes a new least cost to x and sends its neighbors At time t2, y receives z’s update and updates its distance its DV. fast” table. y’s least costs do not change and hence y does not send any message to z. Internet of Things Routing Primer 34
More slides like this


Slide #35.

Distance Vector: Link Cost Changes Link cost changes:  good news travels fast  bad news travels slow - “count to infinity” problem!  44 iterations before algorithm stabilizes: see P&D page 248! 60 y 4 1 x 50 z Possible solutions: 1. Keep ‘infinity ‘ small {depends on graph diameter}. 2. Split Horizon: node does not send those routes learned from a neighbor back to that neighbor. 3. Split Horizon with Poison Reverse: • If z routes through y to get to x, z tells y its (z’s) distance to x is infinite (so y won’t route to x via z).  Does this solve count to infinity problem? Internet of Things Routing Primer 35
More slides like this


Slide #36.

Link State Algorithm 1. Each router is responsible for meeting its neighbors and learning their names. 2. Each router constructs a link state packet (LSP) which consists of a list of names and cost to reach each of its neighbors. 3. The LSP is transmitted to ALL other routers. Each router stores the most recently generated LSP from each other router. 4. Each router uses complete information on the network topology to compute the shortest path route toPrimer each Internet of Things Routing 36
More slides like this


Slide #37.

Reliable Flooding X A C B D X A C B (a) X A C B D (b) D (c) X A C B D (d) Figure 4.18 Reliable LSP Flooding P&D slide Internet of Things Routing Primer 37
More slides like this


Slide #38.

Reliable Flooding The process of making sure all the nodes participating in the routing protocol get a copy of the link-state information from all the other nodes. • LSP contains: – Sending router’s node ID – List of connected neighbors with the associated link cost to each neighbor – Sequence number – Time-to-live (TTL) {an aging mechanism} • Internet of Things Routing Primer 38
More slides like this


Slide #39.

Reliable Flooding • • First two items enable route calculation. Last two items make process reliable – ACKs and checking for duplicates is needed. • • Periodic Hello packets used to determine the demise of a neighbor. The sequence numbers are not expected to wrap around. Internet of Things Routing Primer 39
More slides like this


Slide #40.

A Link-State Routing Algorithm Notation: algorithm Dijkstra’s  net topology, link costs known nodes c(x,y): link cost from node x to to y; all =∞ if not direct      – accomplished via “link state broadcast”. neighbors. – allcurrent nodes have same D(v): value ofinfo. cost of path from source to computes least cost paths from one node (‘source”) destination v to all other nodes p(v): predecessor node along path from source to v – gives forwarding table for that node. N': set of nodes whose least cost path is definitively iterative: after k iterations, know least cost path to k known. destinations. K&R Internet of Things Routing Primer 40
More slides like this


Slide #41.

Dijsktra’s Shortest Path Algorithm 1 Initialization: 2 N' = {u} 3 for all nodes v 4 if v adjacent to u 5 then D(v) = c(u,v) 6 else D(v) = ∞ 7 8 Loop 9 find w not in N' such that D(w) is a minimum 10 add w to N' 11 update D(v) for all v adjacent to w and not in N' : 12 D(v) = min( D(v), D(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 */ 15 until all nodes in N' Internet of Things Routing Primer [K&R] 41
More slides like this


Slide #42.

Dijkstra’s Algorithm: Example Step 0 1 2 3 4 5 N' u ux uxy uxyv uxyvw uxyvwz D(v),p(v) D(w),p(w) 2,u 5,u 2,u 4,x 2,u 3,y 3,y D(x),p(x) 1,u D(y),p(y) ∞ 2,x D(z),p(z) ∞ ∞ 4,y 4,y 4,y 5 u 2 1 v 2 x 3 w 3 1 1 y Internet of Things 5 z 2 Routing Primer 42
More slides like this


Slide #43.

Dijkstra’s Algorithm: Example (2) Resulting shortest-path tree from u: v w u z x y Resulting forwarding table in u: destination link v (u,v) x (u,x) y (u,x) w (u,x) z (u,x) Internet of Things Routing Primer 43
More slides like this


Slide #44.

Dijkstra’s Algorithm, Discussion Algorithm complexity: n nodes  each iteration: need to check all nodes, w, not in N  n(n+1)/2 comparisons: O(n2)  more efficient implementations possible: O(nlogn) Oscillations possible:  e.g., link cost = amount of carried traffic A A A A 1 1+e 2+e 0 0 2+e 2+e 0 D B D D D B 0 0 1+e1 B 0 B 0 1 1+e 0 C e 0 C 0 1 C 1+e 0 C e 1 1 e … recompute … recompute … recompute initially routing Internet of Things Routing Primer 44
More slides like this


Slide #45.

Intra-AS Routing   also known as Interior Gateway Protocols (IGP) most common Intra-AS routing protocols: – RIP: Routing Information Protocol – OSPF: Open Shortest Path First – IGRP: Interior Gateway Routing Protocol (Cisco proprietary) Internet of Things Routing Primer 45
More slides like this


Slide #46.

Routing Information Protocol (RIP)       RIP had widespread use because it was distributed with BSD Unix in “routed”, a router management daemon in 1982. RIP - most used Distance Vector protocol. RFC1058 in June 1988 Runs over UDP. Metric = hop count BIG problem is max. hop count =16  RIP limited to running on small networks (or AS’s that have a small Internet of Things Routing Primer diameter)!! 46
More slides like this


Slide #47.

Routing Information Protocol (RIP) u v A z    C B D w x y From router A to subnets: destination hops u 1 v 2 w 2 x 3 y 3 z 2 Sends DV packets every 30 seconds (or faster) as Response Messages (also called advertisements). each advertisement: list of up to 25 destination subnets within AS. Upgraded to RIPv2 Internet of Things Routing Primer 47
More slides like this


Slide #48.

RIP Packets 0 8 Command 16 Version Family of net 1 31 Must be zero Address of net 1 Address of net 1 (network_address, distance) pairs Distance to net 1 Family of net 2 Address of net 2 Address of net 2 Distance to net 2 Figure 4.17 RIP Packet Format P&D slide Internet of Things Routing Primer 48
More slides like this


Slide #49.

RIPv2      Allows routing on a subnet (subnet masks) Has an authentication mechanism Tries to deal with multicast Uses route tags Has the ability for router to announce routes on behalf of another router. Internet of Things Routing Primer 49
More slides like this


Slide #50.

RIPv2 Packets subnet masks Figure 3.31 RIPv2 Packet Format Internet of Things Routing Primer 50
More slides like this


Slide #51.

OSPF (Open Shortest Path First)   “open” :: publicly available (due to IETF) uses Link State algorithm – LS packet dissemination – topology map at each node – route computation uses Dijkstra’s algorithm.   OSPF advertisement carries one entry per neighbor router. advertisements disseminated to entire AS (via flooding*). – carried in OSPF messages directly over IP (rather than TCP or UDP). * However hierarchy (partitioning domains into areas) reduces flooding impact. Internet of Things Routing Primer 51
More slides like this


Slide #52.

OSPF “Advanced” Features (not in RIP)     security: all OSPF messages authenticated (to prevent malicious intrusion). multiple same-cost paths allowed (only one path in RIP). For each link, multiple cost metrics for different TOS (e.g., satellite link cost set “low” for best effort; high for real time). integrated uni- and multicast support: – Multicast OSPF (MOSPF) uses same topology data base as OSPF.  hierarchical OSPF used in large domains. Internet of Things Routing Primer 52
More slides like this


Slide #53.

Partitioning Domains Figure 4.2 A domain divided into areas Internet of Things Routing Primer 53
More slides like this


Slide #54.

Hierarchical OSPF Internet of Things Routing Primer 54
More slides like this


Slide #55.

Hierarchical OSPF  Two-Level Hierarchy: local area, backbone. – Link-State Advertisements (LSAs) only in area – each node has detailed area topology; only knows direction (shortest path) to nets in other areas.    area border routers: “summarize” distances to nets in own area, advertise to other Area Border routers. backbone routers: run OSPF routing limited to backbone. boundary routers: connect to other AS’s. Internet of Things Routing Primer 55
More slides like this


Slide #56.

OSPF LSA Types 1. Router link advertisement [Hello message] 2. Network link advertisement 3. Network summary link advertisement 4. AS border router’s summary link advertisement 5. AS external link advertisement Internet of Things Routing Primer 56
More slides like this


Slide #57.

OSPF Figure 5-65.The relation between AS’s, backbones, and areas in OSPFTanenbaum Internet of Things Routing Primer 57
More slides like this


Slide #58.

Internet Inter-AS routing: BGP   BGP (Border Gateway Protocol): the de facto standard BGP provides each AS a means to: 1. Obtain subnet reachability information from neighboring ASs. 2. Propagate reachability information to all ASinternal routers. 3. Determine “good” routes to subnets based on reachability information and policy.  allows subnet to advertise its existence to rest of Internet: “I am here!” Internet of Things Routing Primer 58
More slides like this


Slide #59.

Routing Primer Summary  Routers forward and route over WANs – Produce look up tables in routers  Routing Classification: – Adaptive or non-adaptive – Interdomain and Intradomain  Distance Vector Routing (DV) – Perlman version – Tanenbaum example – K&R version Internet of Things Routing Primer 59
More slides like this


Slide #60.

Routing Primer Summary  Link State Routing (LS) – Uses reliable flooding; Dijkstra’s SP algorithm  RIP – Old ARPA routing; unicast DV routing  OSPF – Two-Level Hierarchical LS routing – Five LSA types for router communication  BGP – Interdomain usingPrimer reachability Internetrouting of Things Routing 60
More slides like this