Föreläsning4.pdf

Network layer  transport segment from application transport sending to receiving host network data link physical  on sending side network...

Network layer  transport segment from application transport sending to receiving host network data link physical  on sending side network data link network data link encapsulates segments network physical physical data link physical into datagrams network network data link data link physical physical  on receiving side, network network delivers segments to data link physical network data link physical transport layer data link physical application  network layer protocols network data link transport network in every host, router network physical data link network data link physical data link physical router examines header physical  fields in all IP datagrams Network Layer 4-1 Two Key Network-Layer Functions  forwarding: move Analogy (driving): packets from router’s input to appropriate  routing: process of router output planning trip from source to destimation  routing: determine route taken by  forwarding: process packets from source of getting through to destination single interchange  routing algorithms Network Layer 4-2 Datagram Forwarding table routing algorithm 4 billion IP addresses, so rather than list individual destination address local forwarding table dest address output link list range of addresses address-range 1 3 (aggregate table entries) address-range 2 2 address-range 3 2 address-range 4 1 IP destination address in arriving packet’s header 1 3 2 Network Layer 4-3 Datagram Forwarding table Destination Address Range Link Interface 11001000 00010111 00010000 00000000 through 0 11001000 00010111 00010111 11111111 11001000 00010111 00011000 00000000 through 1 11001000 00010111 00011000 11111111 11001000 00010111 00011001 00000000 through 2 11001000 00010111 00011111 11111111 otherwise 3 Network Layer 4-4 IPv4 datagram format IP protocol version 32 bits number total datagram header length type of length (bytes) ver head. length (bytes) len service for “type” of data fragment fragmentation/ 16-bit identifier flgs offset reassembly max number time to upper header remaining hops live layer checksum (decremented at 32 bit source IP address each router) 32 bit destination IP address upper layer protocol to deliver payload to Options (if any) data (variable length, typically a TCP or UDP segment) Network Layer 4-5 IP Addressing: introduction  IP address: 32-bit 223.1.1.1 identifier for host, 223.1.2.1 223.1.1.2 router interface 223.1.1.4 223.1.2.9  interface: connection 223.1.2.2 between host/router 223.1.1.3 223.1.3.27 and physical link  router’s typically have multiple interfaces 223.1.3.1 223.1.3.2  host typically has one interface  IP addresses associated with each 223.1.1.1 = 11011111 00000001 00000001 00000001 interface 223 1 1 1 Network Layer 4-6 Subnets  IP address: 223.1.1.1  subnet part (high 223.1.2.1 223.1.1.2 order bits) 223.1.1.4 223.1.2.9  host part (low order bits) 223.1.1.3 223.1.2.2 223.1.3.27  What’s a subnet ? subnet  device interfaces with same subnet part of IP 223.1.3.1 223.1.3.2 address  can physically reach each other without intervening router network consisting of 3 subnets Network Layer 4-7 Subnets 223.1.1.0/24 223.1.2.0/24 Recipe  to determine the subnets, detach each interface from its host or router, creating islands of isolated networks  each isolated network is called a subnet. 223.1.3.0/24 Subnet mask: /24 Network Layer 4-8 IP addressing: CIDR CIDR: Classless InterDomain Routing  subnet portion of address of arbitrary length  address format: a.b.c.d/x, where x is # bits in subnet portion of address subnet host part part 11001000 00010111 00010000 00000000 200.23.16.0/23 Network Layer 4-9 IP addresses: how to get one? Q: How does a host get an IP address?  hard-coded by system admin in a file  Windows: control-panel->network->configuration- >tcp/ip->properties  UNIX: /etc/rc.config  DHCP: Dynamic Host Configuration Protocol: dynamically get address from a server  “plug-and-play” Network Layer 4-10 IP addressing: the last word... Q: How does an ISP get block of addresses? A: ICANN: Internet Corporation for Assigned Names and Numbers  allocates addresses  manages DNS  assigns domain names, resolves disputes Network Layer 4-11  IPv6  Initial motivation: 32-bit address space soon to be completely allocated.  Additional motivation:  header format helps speed processing/forwarding  header changes to facilitate QoS IPv6 datagram format:  fixed-length 40 byte header  no fragmentation allowed Network Layer 4-12 IPv6 Header Priority: identify priority among datagrams in flow Flow Label: identify datagrams in same “flow” (concept of “flow” not well defined) Next header: identify upper layer protocol for data ver pri flow label payload len next hdr hop limit source address (128 bits) destination address (128 bits) data 32 bits Network Layer 4-13  IPv6 Addresses (IPv4 addresses, 32 bits long, written in decimal, separated by periods) IPv6 addresses, 128 bits long, written in hexadecimal, separated by colons. 3ffe:1900:4545:3:200:f8ff:fe21:67cf Leading zeros can be omitted in each field, :0003: is written :3:. A double colon (::) can be used once in an address to replace multiple fields of zeros. fe80:0000:0000:0000:0200:f8ff:fe21:67cf can be written fe80::200:f8ff:fe21:67cf Network Layer 4-14 Other Changes from IPv4  Checksum: removed entirely to reduce processing time at each hop  Options: allowed, but outside of header, indicated by “Next Header” field  ICMPv6 (Internet Control Message Protocol) : new version of ICMP  additional message types, e.g. “Packet Too Big”  multicast group management functions Network Layer 4-15 Transition From IPv4 To IPv6  Not all routers can be upgraded simultaneous  How will the network operate with mixed IPv4 and IPv6 routers?  Tunneling: IPv6 carried as payload in IPv4 datagram among IPv4 routers  Dual stack: Both IPv4 and IPv6 protocol implemented in the routers  Translation: When transiting, translate between protocols (information lost) Network Layer 4-15 Tunneling A B E F Logical view: tunnel IPv6 IPv6 IPv6 IPv6 A B E F Physical view: IPv6 IPv6 IPv4 IPv4 IPv6 IPv6 Network Layer 4-17 Tunneling A B E F Logical view: tunnel IPv6 IPv6 IPv6 IPv6 A B C D E F Physical view: IPv6 IPv6 IPv4 IPv4 IPv6 IPv6 Flow: X Src:B Src:B Flow: X Src: A Dest: E Dest: E Src: A Dest: F Dest: F Flow: X Flow: X Src: A Src: A data Dest: F Dest: F data data data A-to-B: E-to-F: B-to-C: B-to-C: IPv6 IPv6 IPv6 inside IPv6 inside IPv4 IPv4 Network Layer 4-18 Routingalgoritmer Hur skapas innehållet i routingtabellerna?? Network Layer 4-19 Graph abstraction 5 3 v w 5 2 u 2 1 z 3 1 2 x 1 y Graph: G = (N,E) N = set of routers = { u, v, w, x, y, z } E = set of links ={ (u,v), (u,x), (v,x), (v,w), (x,w), (x,y), (w,y), (w,z), (y,z) } Remark: Graph abstraction is useful in other network contexts Example: P2P, where N is set of peers and E is set of TCP connections Network Layer 4-20  Graph abstraction: costs 5 c(x,x’) = cost of link (x,x’) 3 v w 5 2 - e.g., c(w,z) = 5 u 2 1 z 3 cost could always be 1, or 1 2 inversely related to bandwidth, x 1 y or inversely related to congestion Cost of path (x1, x2, x3,…, xp) = c(x1,x2) + c(x2,x3) + … + c(xp-1,xp) Question: What’s the least-cost path between u and z ? Routing algorithm: algorithm that finds least-cost path Network Layer 4-21 Routing Algorithm classification Global or decentralized Static or dynamic? information? Static: Global:  routes change slowly  all routers have complete topology, link cost info over time  “link state” algorithms Dynamic: Decentralized:  routes change more  router knows physically- quickly connected neighbors, link costs to neighbors  periodic update  iterative process of  in response to link computation, exchange of cost changes info with neighbors  “distance vector” algorithms Network Layer 4-22 A Link-State Routing Algorithm Dijkstra’s algorithm Notation:  net topology, link costs  c(x,y): link cost from node known to all nodes x to y; = ∞ if not direct  accomplished via “link neighbors state broadcast”  D(v): current value of cost  all nodes have same info of path from source to  computes least cost paths destination v from one node (“source”) 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 definitively  iterative: after k known iterations, know least cost path to k destinations Network Layer 4-23 Dijsktra’s 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 15 until all nodes in N' Network Layer 4-24 Dijkstra’s algorithm: example D(v) D(w) D(x) D(y) D(z) Step N' p(v) p(w) p(x) p(y) p(z) 0 u 7,u 3,u 5,u ∞ ∞ 1 uw 6,w 5,u 11,w ∞ 2 uwx 6,w 11,w 14,x 3 uwxv 10,v 14,x 4 uwxvy 12,y 5 uwxvyz x 9 Notes: 5 7 4  construct shortest path 8 tree by tracing predecessor nodes 3 w z u y 2  ties can exist (can be broken arbitrarily) 3 7 4 v Network Layer 4-25  Dijkstra’s algorithm: another example Step N' D(v),p(v) D(w),p(w) D(x),p(x) D(y),p(y) D(z),p(z) 0 u 2,u 5,u 1,u ∞ ∞ 1 ux 2,u 4,x 2,x ∞ 2 uxy 2,u 3,y 4,y 3 uxyv 3,y 4,y 4 uxyvw 4,y 5 uxyvwz 5 3 v w 5 2 u 2 1 z 3 1 2 x 1 y Network Layer 4-26 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) Network Layer 4-27  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 1 A A A A 1+e 2+e 0 0 2+e 2+e 0 D 0 0 B D 1+e 1 B D B D 1+e 1 B 0 0 0 e 0 0 1 1+e 0 e 1 C C C C 1 e … recompute … recompute … recompute initially routing Network Layer 4-28 Distance Vector Algorithm Bellman-Ford Equation (dynamic programming) Define dx(y) := cost of least-cost path from x to y Then dx(y) = min v {c(x,v) + dv(y) } where min is taken over all neighbors v of x Network Layer 4-29 Bellman-Ford example 5 3 Clearly, dv(z) = 5, dx(z) = 3, dw(z) = 3 v w 5 2 u 2 1 z B-F equation says: 3 1 2 du(z) = min { c(u,v) + dv(z), x y 1 c(u,x) + dx(z), c(u,w) + dw(z) } = min {2 + 5, 1 + 3, 5 + 3} = 4 Node that achieves minimum is next hop in shortest path ➜ forwarding table Network Layer 4-30 Distance Vector Algorithm  Dx(y) = estimate of least cost from x to y  x maintains distance vector Dx = [Dx(y): y є N ]  node x:  knows cost to each neighbor v: c(x,v)  maintains its neighbors’ distance vectors. For each neighbor v, x maintains Dv = [Dv(y): y є N ] Network Layer 4-31 Distance vector algorithm Basic idea:  from time-to-time, each node sends its own distance vector estimate to neighbors  when x receives new DV estimate from neighbor, it updates its own DV using B-F equation: Dx(y) ← minv{c(x,v) + Dv(y)} for each node y ∊ N  under minor, natural conditions, the estimate Dx(y) converge to the actual least cost dx(y) Network Layer 4-32 Distance Vector Algorithm Iterative, asynchronous: Each node: each local iteration caused by:  local link cost change wait for (change in local link  DV update message from cost or msg from neighbor) neighbor Distributed: recompute estimates  each node notifies neighbors only when its DV changes if DV to any dest has  neighbors then notify changed, notify neighbors their neighbors if necessary Network Layer 4-33  Dx(z) = min{c(x,y) + Dx(y) = min{c(x,y) + Dy(y), c(x,z) + Dz(y)} = min{2+0 , 7+1} = 2 Dy(z), c(x,z) + Dz(z)} node x table = min{2+1 , 7+0} = 3 cost to cost to x y z x y z x 0 2 7 x 0 2 3 from from y ∞∞ ∞ y 2 0 1 z ∞∞ ∞ z 7 1 0 node y table cost to x y z y 2 1 x ∞ ∞ ∞ x z y 2 0 1 7 from z ∞∞ ∞ node z table cost to x y z x ∞∞ ∞ from y ∞∞ ∞ z 71 0 time Network Layer 4-34  Dx(y) = min{c(x,y) + Dy(y), c(x,z) + Dz(y)} Dx(z) = min{c(x,y) + = min{2+0 , 7+1} = 2 Dy(z), c(x,z) + Dz(z)} node x table = min{2+1 , 7+0} = 3 cost to cost to cost to x y z x y z x y z x 0 2 7 x 0 2 3 x 0 2 3 from from y ∞∞ ∞ y 2 0 1 from y 2 0 1 z ∞∞ ∞ z 7 1 0 z 3 1 0 node y table cost to cost to cost to x y z x y z x y z y 2 1 x ∞ ∞ ∞ x 0 2 7 x 0 2 3 x z from y 2 0 1 y 2 0 1 7 from from y 2 0 1 z ∞∞ ∞ z 7 1 0 z 3 1 0 node z table cost to cost to cost to x y z x y z x y z x ∞∞ ∞ x 0 2 7 x 0 2 3 from from y 2 0 1 y 2 0 1 from y ∞∞ ∞ z 71 0 z 3 1 0 z 3 1 0 time Network Layer 4-35  Distance Vector: link cost changes Link cost changes: 1  node detects local link cost change y 4 1  updates routing info, recalculates x z distance vector 50  if DV changes, notify neighbors t0 : y detects link-cost change, updates its DV, informs its neighbors. “good t1 : z receives update from y, updates its table, computes news new least cost to x , sends its neighbors its DV. travels fast” t2 : y receives z’s update, updates its distance table. y’s least costs do not change, so y does not send a message to z. Network Layer 4-36 Distance Vector: link cost changes Link cost changes: 60  good news travels fast y 4 1  bad news travels slow - x z “count to infinity” problem! 50  44 iterations before algorithm stabilizes: see text Poisoned 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)  will this completely solve count to infinity problem? Network Layer 4-37 Comparison of LS and DV algorithms Message complexity Robustness: what happens  LS: with n nodes, E links, if router malfunctions? O(nE) msgs sent LS:  DV: exchange between  node can advertise neighbors only incorrect link cost  convergence time varies  each node computes only Speed of Convergence its own table  LS: O(n2) algorithm requires DV: O(nE) msgs  DV node can advertise  may have oscillations incorrect path cost  DV: convergence time varies  each node’s table used by  may be routing loops others error propagate thru  count-to-infinity problem network Network Layer 4-38