3rd Edition: Chapter 4 - PDF Free Download

Chapter 4 Network Layer A note on the use of these ppt slides: We re making these slides freely available to all (faculty, students, readers). They re in PowerPoint form so you can add, modify, and delete slides (including this one) and slide content to suit your needs. They obviously represent a lot of work on our part. In return for use, we only ask the following: If you use these slides (e.g., in a class) in substantially unaltered form, that you mention their source (after all, we d like people to use our book!) If you post any slides in substantially unaltered form on a www site, that you note that they are adapted from (or perhaps identical to) our slides, and note our copyright of this material. Thanks and enjoy! JFK/KWR Computer Networking: A Top Down Approach 5 th edition. Jim Kurose, Keith Ross Addison-Wesley, April 2009. All material copyright 1996-2009 J.F Kurose and K.W. Ross, All Rights Reserved Network Layer 4-1

Chapter 4: Network Layer Chapter goals: understand principles behind network layer services: routing (path selection) dealing with scale how a router works advanced topics: IPv6, mobility instantiation and implementation in the Internet Network Layer 4-2

Chapter 4: Network Layer 4. 1 Introduction 4.2 Virtual circuit and datagram networks 4.3 What s inside a router 4.4 IP: Internet Protocol Datagram format IPv4 addressing ICMP IPv6 4.5 Routing algorithms Link state Distance Vector Hierarchical routing 4.6 Routing in the Internet RIP OSPF BGP 4.7 Broadcast and multicast routing Network Layer 4-3

Router 라우터에는네트웍층까지만구현됨 Network Layer 4-4

Routing & Forwarding 보통은구별없이사용되는용어 Routing Source 부터 Dest. 까지의 end-to-end path 를결정하는 network-wide process Forwarding Router 의 input link 에서적절한 output link 로패킷을전달하는 router-local action 라우터는라우팅프로토콜을가동하여 local forwarding table 을만들고, 패킷이입력되면이 forwarding table 을참조하여패킷을적절한출력링크로이동시킴 Network Layer 4-5

Forwarding Table routing algorithm value in arriving local forwarding table header value output link 0100 0101 0111 1001 3 2 2 1 packet s header 0111 1 3 2 Network Layer 4-6

Connection setup 기능 특정네트웍구조에서네트웍층의 3 번째기능 ATM, frame relay, X.25 Before datagrams flow, two hosts and intervening routers establish virtual connection Routers get involved Network and transport layer cnctn service: Network: between two hosts Transport: between two processes Network Layer 4-7

Network service model Q: What service model for channel transporting datagrams from sender to rcvr? Example services for individual datagrams: Guaranteed delivery Guaranteed delivery with bounded delay (eg. less than 100 msec) Example services for a flow of datagrams: In-order datagram delivery Guaranteed min. bandwidth to flow Guaranteed max. Jitter Network Layer 4-8

Internet 의네트웍층서비스모델 Best-effort service -> No guarantee at all 패킷이전달될지가보장되지않음 패킷이순서대로전달될지보장되지않음 패킷간의시간간격이유지될지보장되지않음 Network Layer 4-9

Network layer service models: Network Architecture Service Model Bandwidth Guarantees? Loss Order Timing Congestion feedback Internet ATM ATM ATM ATM best effort CBR VBR ABR UBR none constant rate guaranteed rate guaranteed minimum none no yes yes no no no yes yes yes yes no yes yes no no no (inferred via loss) no congestion no congestion yes no Network Layer 4-10

Network layer connection and connection-less service Datagram network provides network-layer connectionless service Virtual Circuit network provides networklayer connection service Transport 층에서의서비스와다른점 : Host-to-host service to transport layer Transport 층에서는 process-to-process service to application layer Network 층은둘중한가지서비스만제공 라우터와 end system 에구현 Transport 층에서는 end system 에서만구현 Network Layer 4-12

Virtual circuits source-to-dest path behaves much like telephone circuit Protocol: ATM, X.25 Data 를보내기전 call setup 을위한 signaling protocol ( 예 : Q.2931 for ATM) 을이용하여경로설정을하고전송이끝나면 teardown 을함 Bandwidth may be allocated Packet header 에 VC number 가적혀있음 라우터는패킷을출력링크로내보낼때 VC number 값을 forwarding table 을보고바꿔줌 이값들은 end host 간 VC 가성립될때중간라우터들의 forwarding table 에기록되어있음 Network Layer 4-13

VC implementation a VC consists of: 1. path from source to destination 2. VC numbers, one number for each link along path 3. entries in forwarding tables in routers along path packet belonging to VC carries VC number (rather than dest address) VC number can be changed on each link. New VC number comes from forwarding table Network Layer 4-14

Forwarding table VC number 12 1 2 3 22 32 Forwarding table in northwest router: interface number Incoming interface Incoming VC # Outgoing interface Outgoing VC # 1 12 3 22 2 63 1 18 3 7 2 17 1 97 3 87 Routers maintain connection state information! Network Layer 4-15

Virtual circuits: signaling protocols used to setup, maintain teardown VC used in ATM, frame-relay, X.25 not used in today s Internet Application transport network data link physical 5. Data flow begins 6. Receive data 4. Call connected 3. Accept call 1. Initiate call 2. incoming call Application Transport network data link physical Network Layer 4-16

Datagram networks no call setup at network layer routers: no state about end-to-end connections no network-level concept of connection packets forwarded using destination host address packets between same source-dest pair may take different paths Application transport network data link physical 1. Send data 2. Receive data Application transport network data link physical Network Layer 4-17

Datagram Network VC setup 과정이없이그냥데이터를보낸다 32 bit 를사용하는 IP 의경우, forwarding table 이너무커지는단점 4 billion possible entries Table 크기를줄이기위해 longest prefix matching rule 을사용 Network Layer 4-18

Forwarding table 4 billion possible entries 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-19

Longest prefix matching Prefix Match Link Interface 11001000 00010111 00010 0 11001000 00010111 00011000 1 11001000 00010111 00011 2 otherwise 3 Examples DA: 11001000 00010111 00010110 10100001 Which interface? DA: 11001000 00010111 00011000 10101010 Which interface? Network Layer 4-20

Datagram or VC network: why? Internet(datagram) data exchange among computers elastic service, no strict timing req. smart end systems (computers) can adapt, perform control, error recovery simple inside network, complexity at edge many link types different characteristics uniform service difficult ATM(VC) evolved from telephony human conversation: strict timing, reliability requirements need for guaranteed service dumb end systems telephones complexity inside network Network Layer 4-21

Router Architecture Overview Two key router functions: run routing algorithms/protocol (RIP, OSPF, BGP) forwarding datagrams from incoming to outgoing link Network Layer 4-23

Routing Processor Routing protocol 수행 Maintaining Forwarding table Performs network management functions Network Layer 4-24

Input Port Processing ( 주기능 : Output port 결정 ) Physical layer: bit-level reception Data link layer: e.g., Ethernet see chapter 5 Decentralized switching: given datagram dest., lookup output port using forwarding table in input port memory ( 이 table 은 routing processor 가관리하는 forwarding table 의 local copy) goal: complete input port processing at line speed queuing: if datagrams arrive faster than forwarding rate into switch fabric Network Layer 4-25

Line Speed Lookup is to be performed in less than the amount of time needed to receive a packet at the input port Input processing of a received packet can be completed before the next receive operation is complete Eg. OC48 input port = 2.5Gbps A packet size = 256 bytes (= 2048 bits) 2.5*10 9 / 2048 = 1.22 Million packets /sec 즉, line speed 로동작하려면초당 1.22 백만개의 table lookup 을수행필요 Network Layer 4-26

Three types of switching fabrics Network Layer 4-27

Switching Via Memory First generation routers: traditional computers with switching under direct control of CPU packet copied to system s memory speed limited by memory bandwidth (2 bus crossings per datagram) Input Port Memory Output Port System Bus Network Layer 4-28

Switching Via a Bus datagram from input port memory to output port memory via a shared bus bus contention: switching speed limited by bus bandwidth 1 Gbps bus, Cisco 1900: sufficient speed for access and enterprise routers (not regional or backbone) Network Layer 4-29

Switching Via An Interconnection Network overcome bus bandwidth limitations Banyan networks, other interconnection nets initially developed to connect processors in multiprocessor Advanced design: fragmenting datagram into fixed length cells, switch cells through the fabric. Cisco 12000: switches 60 Gbps through the interconnection network Network Layer 4-30

Output Ports Buffering required when datagrams arrive from fabric faster than the transmission rate Packet Scheduling is to choose among buffered (queued) datagrams for transmission Eg, FCFS, WFQ Network Layer 4-31

Output port queueing Packet scheduler select one of these 3 packets to output link 이 buffer 가 overflow 되면 packet loss 발생 Network Layer 4-32

Input Port Queuing Fabric slower than input ports combined -> queueing may occur at input queues Head-of-the-Line (HOL) blocking: queued datagram at front of queue prevents others in queue from moving forward queueing delay and loss due to input buffer overflow! win Crossbar switch Network Layer 4-33

The Internet Network layer Host, router network layer functions: Transport layer: TCP, UDP Network layer Routing protocols path selection RIP, OSPF, BGP forwarding table IP protocol addressing conventions datagram format packet handling conventions ICMP protocol error reporting router signaling Link layer physical layer Network Layer 4-35

IP datagram format IP protocol version number header length (bytes) type of data max number remaining hops (decremented at each router) upper layer protocol to deliver payload to how much overhead with TCP? 20 bytes of TCP 20 bytes of IP = 40 bytes + app layer overhead ver 16-bit identifier time to upper live layer 32 bits head. type of len service flgs length fragment offset Internet checksum 32 bit source IP address 32 bit destination IP address Options (if any) data (variable length, typically a TCP or UDP segment) total datagram length (bytes) for fragmentation/ reassembly E.g. timestamp, record route taken, specify list of routers to visit. Network Layer 4-37

Field 설명 대부분의 IPv4 패킷은 option 이없음 즉, 20 bytes of header IPv6 에서는 option 부분이없음 Fragmentation 의필요성 경로상에다른링크프로토콜들이사용될수있고이경우각 link 의 MTU 는다를수있다 IPv6 는 router 에서의 fragmentation 을허용안함 TTL 값 : router 에서 1 씩감소되어 0 이되면 drop 됨 Checksum 은 IP header 에대해서만계산됨 TTL 값이 router 에서 1 씩감소되므로 checksum 값은각 router 에서다시계산되어야함 TCP/UDP checksum 은전체 TCP/UDP segment 에대해계산됨 Network Layer 4-38

IP Fragmentation and Reassembly End host 의네트웍층에서 trasport 층으로전달하기전에 reassembly 수행 ( 일부 fragment 가 missing 된패킷은폐기 ) Network Layer 4-39

IP Fragmentation and Reassembly Example 4000 byte datagram MTU = 1500 bytes length =4000 ID =x fragflag =0 offset =0 One large datagram becomes several smaller datagrams 1480 bytes in data field offset = 1480/8 length =1500 length =1500 length =1040 ID =x ID =x ID =x fragflag =1 fragflag =1 fragflag =0 offset =0 offset =185 offset =370 Network Layer 4-40

IP Addressing: introduction IP address: 32-bit identifier for host & router interface 2 32 = 4 billion 개주소가능 Dotted-decimal notation (eg) 223.1.1.1 interface: connection between host/router and physical link router s typically have multiple interfaces host may have multiple interfaces IP addresses associated with each interface 223.1.1.1 223.1.2.1 223.1.1.2 223.1.1.4 223.1.2.9 223.1.1.3 223.1.3.1 223.1.3.27 223.1.2.2 223.1.3.2 223.1.1.1 = 11011111 00000001 00000001 00000001 223 1 1 1 Network Layer 4-42

Subnets IP address: subnet part (high order bits) host part (low order bits) What s a subnet? 라우터의한개 interface 와그에연결된 host 들이한개의 subnet 을구성 Subnet mask: Subnet 안에서 IP 주소의공통부분 (eg) 223.1.1.0/24 (/24 notation) Leftmost 24bits define subnet address Broadcast address: 255.255.255.255 To all hosts on the same subnet 223.1.1.1 223.1.2.1 223.1.1.2 223.1.1.4 223.1.2.9 223.1.1.3 223.1.3.1 223.1.2.2 223.1.3.27 subnet 223.1.3.2 network consisting of 3 subnets Network Layer 4-43

Subnets 223.1.1.2 How many? 223.1.1.1 223.1.1.4 223.1.1.3 223.1.9.2 223.1.7.0 223.1.9.1 223.1.8.1 223.1.8.0 223.1.7.1 223.1.2.6 223.1.3.27 223.1.2.1 223.1.2.2 223.1.3.1 223.1.3.2 Network Layer 4-44

Classful addressing Class A,B,C: 8-, 16-, 24-bits subnet address Class C (= /24) 2 8-2=254 hosts (2 개는특별용도 ) Class B (= /16) 65,643 hosts If you need 2,000 hosts, Class B is allocated IP 주소낭비초래 Network Layer 4-45

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 part 11001000 00010111 00010000 00000000 200.23.16.0/23 host part Network Layer 4-46

IP addressing: CIDR CIDRized address 예 a.b.c.d/21: 한기관에배정된 network prefix 해당기관에서는나머지 11 비트중 3 비트를기관내의 subnet 구조에사용하면 ( 즉, 8 개의 subnet 가능 ), host 는 8 비트를배정받으므로한 sbunet 내에는 2 8 개호스트가능 결국, host 의 subnet 주소는 a.b.c.d/24 가됨 Network Layer 4-47

IP addresses: how to get one? Q: How does host get IP address? hard-coded by system admin in a file Wintel: control-panel->network->configuration- >tcp/ip->properties UNIX: /etc/rc.config DHCP: Dynamic Host Configuration Protocol: dynamically get address from as server plug-and-play (more in next chapter) Network Layer 4-48

DHCP: Dynamic Host Configuration Protocol Goal: allow host to dynamically obtain its IP address from network server when it joins network Can renew its lease on address in use Allows reuse of addresses (only hold address while connected an on ) Support for mobile users who want to join network (more shortly) DHCP overview: host broadcasts DHCP discover msg DHCP server responds with DHCP offer msg host requests IP address: DHCP request msg DHCP server sends address: DHCP ack msg Network Layer 4-49

DHCP client-server scenario A 223.1.1.1 DHCP server 223.1.2.1 B 223.1.1.2 223.1.1.4 223.1.2.9 223.1.2.2 223.1.1.3 223.1.3.27 223.1.3.1 223.1.3.2 E arriving DHCP client needs address in this network Network Layer 4-50

DHCP client-server scenario DHCP server: 223.1.2.5 time DHCP request src: 0.0.0.0, 68 DHCP discover dest:: 255.255.255.255, 67 yiaddrr: 223.1.2.4 transaction ID: 655 src : 0.0.0.0, 68 dest.: 255.255.255.255,67 yiaddr: 0.0.0.0 transaction ID: 654 DHCP offer Lifetime: 3600 secs DHCP ACK src: 223.1.2.5, 67 dest: 255.255.255.255, 68 yiaddrr: 223.1.2.4 transaction ID: 654 Lifetime: 3600 secs src: 223.1.2.5, 67 dest: 255.255.255.255, 68 yiaddrr: 223.1.2.4 transaction ID: 655 Lifetime: 3600 secs arriving client Network Layer 4-51

IP addresses: how to get one? Q: How does network get subnet part of IP addr? A: gets allocated portion of its provider ISP s address space ISP's block 11001000 00010111 00010000 00000000 200.23.16.0/20 Organization 0 11001000 00010111 00010000 00000000 200.23.16.0/23 Organization 1 11001000 00010111 00010010 00000000 200.23.18.0/23 Organization 2 11001000 00010111 00010100 00000000 200.23.20.0/23....... Organization 7 11001000 00010111 00011110 00000000 200.23.30.0/23 Network Layer 4-52

Hierarchical addressing: route aggregation Hierarchical addressing allows efficient advertisement of routing information: Organization 0 200.23.16.0/23 Organization 1 200.23.18.0/23 Organization 2 200.23.20.0/23 Organization 7 200.23.30.0/23.... Fly-By-Night-ISP ISPs-R-Us Send me anything with addresses beginning 200.23.16.0/20 Internet Send me anything with addresses beginning 199.31.0.0/16 Network Layer 4-53

Hierarchical addressing: more specific routes ISPs-R-Us has a more specific route to Organization 1 Organization 0 200.23.16.0/23 Organization 2 200.23.20.0/23 Organization 7 200.23.30.0/23.... Organization 1 200.23.18.0/23 Fly-By-Night-ISP ISPs-R-Us Send me anything with addresses beginning 200.23.16.0/20 Internet Send me anything with addresses beginning 199.31.0.0/16 or 200.23.18.0/23 Network Layer 4-54

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 root servers assigns domain names, resolves disputes Network Layer 4-55

NAT: Network Address Translation rest of Internet 138.76.29.7 10.0.0.4 local network (e.g., home network) 10.0.0/24 10.0.0.1 10.0.0.2 10.0.0.3 All datagrams leaving local network have same single source NAT IP address: 138.76.29.7, different source port numbers Datagrams with source or destination in this network have 10.0.0/24 address for source, destination (as usual) Network Layer 4-56

NAT: Network Address Translation Motivation: local network uses just one IP address as far as outside word is concerned: no need to be allocated range of addresses from ISP: - just one IP address is used for all devices can change addresses of devices in local network without notifying outside world can change ISP without changing addresses of devices in local network devices inside local net not explicitly addressable, visible by outside world (a security plus). Network Layer 4-57

NAT: Network Address Translation Implementation: NAT router must: outgoing datagrams: replace (source IP address, port #) of every outgoing datagram to (NAT IP address, new port #)... remote clients/servers will respond using (NAT IP address, new port #) as destination addr. remember (in NAT translation table) every (source IP address, port #) to (NAT IP address, new port #) translation pair incoming datagrams: replace (NAT IP address, new port #) in dest fields of every incoming datagram with corresponding (source IP address, port #) stored in NAT table Network Layer 4-58

NAT: Network Address Translation 2: NAT router changes datagram source addr from 10.0.0.1, 3345 to 138.76.29.7, 5001, updates table 2 NAT translation table WAN side addr LAN side addr 138.76.29.7, 5001 10.0.0.1, 3345 1: host 10.0.0.1 sends datagram to 128.119.40.186, 80 S: 138.76.29.7, 5001 D: 128.119.40.186, 80 10.0.0.4 S: 10.0.0.1, 3345 D: 128.119.40.186, 80 1 10.0.0.1 10.0.0.2 S: 128.119.40.186, 80 D: 138.76.29.7, 5001 3: Reply arrives 138.76.29.7 dest. address: 138.76.29.7, 5001 3 S: 128.119.40.186, 80 D: 10.0.0.1, 3345 4 4: NAT router changes datagram dest addr from 10.0.0.3 138.76.29.7, 5001 to 10.0.0.1, 3345 Network Layer 4-59

NAT: Network Address Translation 16-bit port-number field: 60,000 simultaneous connections with a single LAN-side address! NAT is controversial: routers should only process up to layer 3 End-to-end 통신 (host간에 IP주소와 port number를변경하지않고하는통신 ) 불가능 NAT possibility must be taken into account by app designers, eg, P2P applications P2P에서는모든 peer가 client/server로동작해야하는데, NAT뒤의 peer는서버로동작불가능. NAT 외부의 peer는 NAT 내부의 peer에게자발적tcp 연결을해낼수없기때문. address shortage should instead be solved by IPv6 Network Layer 4-60

NAT traversal problem client wants to connect to server with address 10.0.0.1 server address 10.0.0.1 local to LAN (client can t use it as destination addr) only one externally visible NATted address: 138.76.29.7 solution 1: statically configure NAT to forward incoming connection requests at given port to server e.g., (123.76.29.7, port 2500) always forwarded to 10.0.0.1 port 25000 Client? 138.76.29.7 NAT router 10.0.0.1 10.0.0.4 Network Layer 4-61

NAT traversal problem solution 2: Universal Plug and Play (UPnP) Internet Gateway Device (IGD) Protocol. Allows NATted host to: learn public IP address (138.76.29.7) add/remove port mappings (with lease times) i.e., automate static NAT port map configuration 138.76.29.7 NAT router IGD 10.0.0.4 10.0.0.1 Network Layer 4-62

NAT traversal problem solution 3: relaying (used in Skype) NATed client establishes connection to relay External client connects to relay relay bridges packets between to connections Client 2. connection to relay initiated by client 3. relaying established 1. connection to relay initiated by NATted host 138.76.29.7 NAT 10.0.0.1 router Network Layer 4-63

ICMP: Internet Control Message Protocol used by hosts & routers to communicate network-level information error reporting: unreachable host, network, port, protocol echo request/reply (used by ping ) ICMP msgs carried in IP datagrams ICMP message: type, code plus first 8 bytes of IP datagram causing error Type Code description 0 0 echo reply (ping) 3 0 dest. network unreachable 3 1 dest host unreachable 3 2 dest protocol unreachable 3 3 dest port unreachable 3 6 dest network unknown 3 7 dest host unknown 4 0 source quench (congestion control - not used) 8 0 echo request (ping) 9 0 route advertisement 10 0 router discovery 11 0 TTL expired 12 0 bad IP header Network Layer 4-65

Traceroute and ICMP Source 가엉뚱한 UDP port number 를가진 UDP 패킷들을발생시킴 First has TTL =1 Second has TTL=2.. nth packet has TTL=n n 번째 datagram 이 n 번째라우터에도착했을때 : TTL 이 0 이되므로라우터는이 datagram 을폐기 Source 로 ICMP warning 메시지를전송 (type 11, code 0) 이것을수신한 source 는 round trip time, n 번째라우터의 IP 주소를알게됨 실제로 Traceroute 프로그램은동일한 TTL 값을가진 UDP 패킷을 3 번보냄 Stopping criterion UDP segment eventually arrives at destination host Destination returns ICMP host unreachable packet (type 3, code 3) When source gets this ICMP, stops. Network Layer 4-66

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 중간라우터에서의 fragmentation 은허용되지않음 (source 와 dest. 에서만가능 ) Checksum field 가없어짐 Network Layer 4-68

IPv6 Header (Cont) 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 Network Layer 4-69

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: new version of ICMP additional message types, e.g. Packet Too Big multicast group management functions Network Layer 4-70

Transition From IPv4 To IPv6 Not all routers can be upgraded simultaneous no flag days How will the network operate with mixed IPv4 and IPv6 routers? Tunneling: IPv6 carried as payload in IPv4 datagram among IPv4 routers Network Layer 4-71

Tunneling Logical view: A B E F tunnel IPv6 IPv6 IPv6 IPv6 Physical view: A B E F IPv6 IPv6 IPv6 IPv6 IPv4 IPv4 Network Layer 4-72

Tunneling Logical view: A B E F tunnel IPv6 IPv6 IPv6 IPv6 Physical view: A B C D E F IPv6 IPv6 IPv4 IPv4 IPv6 IPv6 Flow: X Src: A Dest: F data Src:B Dest: E Flow: X Src: A Dest: F Src:B Dest: E Flow: X Src: A Dest: F Flow: X Src: A Dest: F data data A-to-B: IPv6 B-to-C: IPv4 (encapsulating IPv6) data E-to-F: IPv6 B-to-C: IPv4 (encapsulating IPv6) Network Layer 4-73

Interplay between routing, forwarding routing algorithm value in arriving local forwarding table header value output link 0100 0101 0111 1001 3 2 2 1 packet s header 0111 1 3 2 Network Layer 4-75

Graph abstraction 5 u v 3 w 2 2 1 3 1 x y Graph: G = 1(N,E) 5 2 z 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-76

Graph abstraction: costs u 2 1 5 c(x,x ) = cost of link (x,x ) v x 2 3 3 1 w y 1 5 2 z - e.g., c(w,z) = 5 cost could always be 1, or inversely related to bandwidth, Cost of path (x or inversely related to 1, x 2, x 3,, x p ) = c(x 1,x 2 ) + c(x 2,x 3 ) + + c(x p-1,x p ) congestion Question: What s the least-cost path between u and z? Routing algorithm: algorithm that finds least-cost path Network Layer 4-77

Routing Algorithm classification Global or decentralized information? Global: all routers have complete topology, link cost info link state algorithms Decentralized: router knows physicallyconnected neighbors, link costs to neighbors iterative process of computation, exchange of info with neighbors distance vector algorithms Static or dynamic? Static: routes change slowly over time Dynamic: routes change more quickly periodic update in response to link cost changes Network Layer 4-78

A Link-State Routing Algorithm Dijkstra s algorithm Using global information > Centralized algorithm net topology, link costs known to all nodes accomplished via link state broadcast all nodes have same info Computing least cost paths from one node ( source ) to all other nodes gives forwarding table for that node iterative: after k iterations, know least cost path to k dest. s Problem Oscillation of list-cost path Network Layer 4-80

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 Notation: c(x,y): link cost from node x to y; = if not direct neighbors D(v): current value of cost of path from source to dest. v p(v): predecessor node along path from source to v N': set of nodes whose least cost path definitively known 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' Network Layer 4-81

Dijsktra s Algorithm 3 2 2 3 4 3 1 1 1 6 6 2 3 1 2 4 5 1 Network Layer 4-82

Network Layer 4-83 Dijsktra s Algorithm 6 1 Nodes 2 3 4 5 y p I 1 2 2 6 1 2 6 2 6 2 3 6 5 6 4 4 6 6 5 5 6 3 6 6 1 1 4 2 5 1 2 3 6 4 5 2 1 3 4 3 1 1 2 3 1 2 6 2 6 6 0 Permanent label

Dijsktra s Algorithm 6 s 2 10 1 5 3 5 4 4 12 4 6 5 5 t 7 3 7 5 7 6 8 5 Network Layer 4-84

Distance Vector Algorithm Distributed, asynchronous, iterative algorithm Bellman-ford algorithm Problem Count-to-infinity problem Network Layer 4-86

Distance Vector Algorithm Bellman-Ford Equation (dynamic programming) Define d x (y) := cost of least-cost path from x to y Then d x (y) = min {c(x,v) + d v (y) } where min. is taken over all neighbors of x Network Layer 4-87

Distance Vector Algorithm D x (y) = estimate of least cost from x to y Distance vector: D x = [D x (y): y є N ] Node x knows cost to each neighbor v: c(x,v) Node x maintains D x = [D x (y): y є N ] Node x also maintains its neighbors distance vectors For each neighbor v, x maintains D v = [D v (y): y є N ] Network Layer 4-88

Distance Vector Algorithm Basic idea: Each node periodically sends its own distance vector estimate to neighbors When a node x receives new DV estimate from neighbor, it updates its own DV using B-F equation: D x (y) min v {c(x,v) + D v (y)} for each node y N Under minor, natural conditions, the estimate D x (y) converge the actual least cost d x (y) Network Layer 4-89

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 Each node: wait for (change in local link cost of msg from neighbor) recompute estimates if DV to any dest has changed, notify neighbors Network Layer 4-90

Distance Vector Algorithm A B C D E F G H I J K L Dest. A B C D E F G H I J K L Delay at J Before Update Dist. Next 8 * * * * * * * * * * * * * 12 * 10 * 0-6 * * * Info. from A Dist. 0 12 25 40 14 23 18 17 21 9 24 29 Info. from H Dist. 20 31 19 8 30 19 6 0 14 7 22 9 Info. from I Dist. 24 36 18 27 7 20 31 20 0 11 22 33 Info. from K Dist. 21 28 36 24 22 40 31 19 22 10 0 9 New Estimated Delay at J Dist. Next 8 A 20 A 28 I 20 H 17 I 30 I 18 H 12 H 10 I 0-6 K 15 K Network Layer 4-91

Hierarchical Routing Our routing study thus far - idealization all routers identical network flat not true in practice scale: with 200 million destinations: can t store all dest s in routing tables! routing table exchange would swamp links! administrative autonomy internet = network of networks each network admin may want to control routing in its own network Network Layer 4-93

Hierarchical Routing Our routing study thus far - idealization all routers identical network flat not true in practice Hierarchical Routing 사용이유 Scalability 현재인터넷에는 200 million 개이상의호스트가있으므로라우팅테이블크기를줄일필요가있음 Administrative autonomy 회사의네트웍관리자는자신이관리하는라우터의라우팅프로토콜을선택권한을갖기를원함 AS 라는개념을도입하고이 AS 내에서의라우팅프로토콜선택등은해당관리자의권한하에두고, AS 간을연결하는 gateway 라우터간의프로토콜은별도로정함 Network Layer 4-94

Hierarchical Routing aggregate routers into regions, autonomous systems (AS) routers in same AS run same routing protocol intra-as routing protocol routers in different AS can run different intra- AS routing protocol Gateway router Direct link to router in another AS Network Layer 4-95

Hierarchical Routing Network Layer 4-96

AS 내부의라우터가 AS 외부의목적지로패킷을보내야할경우 (Case 1) AS 가한개의 gateway 라우터를가진경우 각내부라우터는 AS 가사용하는 intra-as 라우팅알고리즘을사용하여 gateway 라우터까지의최단경로를결정하고이경로로패킷을보내면됨. Network Layer 4-97

AS 내부의라우터가 AS 외부의목적지로패킷을보내야할경우 (Case 2) 한 AS 에두개의 gateway 가있으나목적지로의 gateway 라우터는한개인경우 ( 예 :AS1 의 1d 가외부로보내려할때 AS3 를경유해서만가능한경우 ) Inter-AS 라우팅프로토콜사용 1 AS1 learns from the inter-as protocol that subnet x is reachable from AS3 (gateway 1c) but not from AS2 2 Inter-AS protocol propagates reachability info to all internal routers in AS1. Intra-AS 라우팅프로토콜사용 3 Router 1d determines from intra-as routing info that its interface I is on the least cost path to 1c. 4 라우터 1d puts in forwarding table entry (x,i) Network Layer 4-98

AS 내부의라우터가 AS 외부의목적지로패킷을보내야할경우 (Case 3) 한 AS 에두개의 gateway 가있으며, 이둘중어느것을통해서도목적지로갈수있는경우 ( 예 :AS1 의 1d 가외부로보내려할때 AS3 및 AS2 를경유해서도가능한경우 ) Hot-potato routing 사용가능 뜨거운감자를가능한한빨리넘겨버리는방식 두개의라우터중가장가까운곳으로패킷을넘김 ( 예 : hot-potato routing running on 1d) Inter-AS 라우팅프로토콜로부터목적지가 AS2 및 AS3 를경유해서도가능하다고파악 Intra-AS 라우팅프로토콜을이용하여 AS2 로의 gateway 라우터 1b, AS3 로의 gateway 라우터 1c 로의경로를파악 Hot-potato routing 은이중 least-cost path 선택 Network Layer 4-99

AS 내부의라우터가 AS 외부의목적지로패킷을보내야할경우 (Case 3) Learn from inter-as protocol that subnet x is reachable via multiple gateways Use routing info from intra-as protocol to determine costs of least-cost paths to each of the gateways Hot potato routing: Choose the gateway that has the smallest least cost Determine from forwarding table the interface I that leads to least-cost gateway. Enter (x,i) in forwarding table Network Layer 4-100

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) Network Layer 4-102

RIP Version 1 (RFC 1058), Version 2 (RFC 2453) RIP advertisement sent over UDP Port number 520 Network Layer 4-104

RIP advertisements Cost metric: hop count ( 거쳐야되는 subnet 갯수 ) Max. cost: 15 (16= ) Routing table is exchanged among neighbors every 30 sec via Response Message (also called advertisement) Each advertisement: list of up to 25 destination subnets within AS If no advertisement heard after 180 sec --> neighbor/link declared dead routes via neighbor invalidated Network Layer 4-105

RIP: Example z w x y A D B C Destination Network Next Router Num. of hops to dest. w A 2 y B 2 z B 7 x -- 1 Routing/Forwarding table in D..... Network Layer 4-106

RIP: Example Dest Next hops w - - x - - z C 4.... Advertisement from A to D w x y A D B z C Destination Network Next Router Num. of hops to dest. w A 2 y B 2 z B A 7 5 x -- 1..... Routing table in D Network Layer 4-107

RIP: Link Failure and Recovery If no advertisement heard after 180 sec --> neighbor/link declared dead routes via neighbor invalidated new advertisements sent to neighbors neighbors in turn send out new advertisements (if tables changed) link failure info quickly (?) propagates to entire net poison reverse used to prevent ping-pong loops (infinite distance = 16 hops) Network Layer 4-108

RIP Table processing RIP routing tables managed by application-level process called route-d (daemon) advertisements sent in UDP packets, periodically repeated routed routed Transprt (UDP) Transprt (UDP) network (IP) forwarding table forwarding table network (IP) link link physical physical Network Layer 4-109

OSPF (Open Shortest Path First) open : publicly available uses Link State algorithm LS packet dissemination topology map at each node route computation using 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 Network Layer 4-111

OSPF advanced features (not in RIP) Security: all OSPF messages authenticated (to prevent malicious intrusion) MD5 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 in large domains. Network Layer 4-112

Hierarchical OSPF BGP 별도 OSPF 동작 별도 OSPF 동작 별도 OSPF 동작 별도 OSPF 동작 Network Layer 4-113

Hierarchical OSPF Two-level hierarchy: local area, backbone. Link-state advertisements only in area each nodes has detailed area topology; only know 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. Network Layer 4-114

Internet inter-as routing: BGP BGP (Border Gateway Protocol): the de facto standard Semi-permanent TCP connection (port 179) 각 AS 는이웃 AS 를통하면어느목적지에도달할수있을지를알게됨 직접연결된두개의 AS 간의 gateway 라우터들은자신의 AS 로부터도달가능한 prefix list 를서로교환함 (ebgp 세션 ) Gateway 라우터는 AS 내의모든라우터들에게이 reachability 정보를알려줌 (ibgp 세션 ) allows subnet to advertise its existence to rest of Internet: I am here Network Layer 4-116

경로정보전달과정 3a 는 AS3 에서도달가능한 prefix 들을 1c 에알려줌 (ebgp 세션 ). 이때 prefix 와같이가는 AS-PATH attribute 는 AS3 로적힘 1c 는 AS1 내부의라우터들에게이정보를알려줌 (ibgp 세션 ) 이중 1b 는 AS2 와연결되어있으므로, 이정보를 2a 에게도알려줌 (ebgp 세션 ). 이때 AS-PATH attribute 는 AS3AS1 으로적힘. Network Layer 4-117

Path attributes & BGP routes When advertising a prefix, advertisement includes BGP attributes. a route = a prefix + attributes Two important attributes: AS-PATH: contains the ASs through which the advert for the prefix passed: AS 67 AS 17 NEXT-HOP: gateway router 간 multiple link 가있을때특정링크를선택가능하도록, gateway router 의특정 link 에부여된 IP 주소를줌 When gateway router receives route advert, uses import policy to accept/decline. Network Layer 4-118

BGP route selection 동일한 prefix 로 2 개이상의경로가있을떄선택하는 rule Elimination rules: 1. Local preference 값 () 이높은경로선택 Local preference 값 = router 가설정하는 attribute 2. AS-PATH 가짧은경로선택 3. NEXT-HOP 이가장가까운 (least cost) 경로선택 : hot potato routing Network Layer 4-119

BGP messages BGP messages exchanged using TCP. BGP messages: OPEN: opens TCP connection to peer and authenticates sender UPDATE: advertises new path (or withdraws old) KEEPALIVE keeps connection alive in absence of UPDATES; also ACKs OPEN request NOTIFICATION: reports errors in previous msg; also used to close connection Network Layer 4-120

BGP routing policy B legend: provider network W A C X customer network: Y A,B,C are provider networks Figure 4.5-BGPnew: a simple BGP scenario X,W,Y are customer (of provider networks); stub net. X is dual-homed: attached to two networks X 는 ISP 간의 transit traffic 을경유시키기를원치않음 따라서, X 는 C 로가는경로가있다고 B 로광고하지않으며, B 로가는경로가있다고 C 로광고하지않음 Network Layer 4-121

BGP routing policy (2) B legend: provider network W A C X customer network: Y Figure 4.5-BGPnew: a simple BGP scenario A advertises to B the path AW B advertises to X the path BAW Should B advertise to C the path BAW? No way! B gets no revenue for routing CBAW since neither W nor C are B s customers B wants to force C to route to W via A B wants to route only to/from its customers! Network Layer 4-122

Why different Intra- and Inter-AS routing? Policy: AS 간의연결 (Inter-AS) 에서는 policy issue 가 dominate 할수있음 즉, 성능보다는 policy 에따라라우팅을결정한다. Scale: hierarchical routing saves table size, reduced update traffic Performance: AS 내부 (Intra-AS) 에서는 performance 가중요 Network Layer 4-123

Broadcast Routing deliver packets from source to all other nodes source duplication is inefficient: duplicate R1 duplicate creation/transmission R1 R2 R2 duplicate R3 R4 R3 R4 source duplication in-network duplication source duplication: how does source determine recipient addresses? Network Layer 4-125

Broadcasting 방법 Flooding: when node receives brdcst pckt, sends copy to all neighbors Problems: cycles & broadcast storm Controlled flooding: node only brdcsts pkt if it hasn t brdcst same packet before (sequence number controlled flooding) Node keeps track of pckt ids already brdcsted Or reverse path forwarding (RPF): only forward pckt if it arrived on shortest path between node and source Spanning tree broadcasting No redundant packets received by any node Network Layer 4-126

Uncontrolled flooding 노드가패킷을수신시, 방금보낸노드를제외한모든이웃노드들에게복사해서보냄 문제점 Each broadcast packet will cycle indefinitely Broadcast storm 발생 각패킷의수많은복사본발생 Network Layer 4-127

Sequence number controlled flooding 노드가 broadcast 패킷을전송시 sequence number 를적어서보냄 노드는수신된 broadcast packet 의 source node 주소와 sequence number 를기록한 list 유지 어느 broadcast 패킷을수신시 list 에있는값과일치하면폐기, 아니면 list 에기록하고이웃노드들로 flooding 시킴 ( 예 ) Gnutella; overlay network 에서수행 Network Layer 4-128

Reverse Path Forwarding(RPF) B 는 A 로부터 source S 가보낸패킷수신시, B 로부터 S 까지의 shortest path 에 BA link 가속해있으면이웃노드 C, D 로 flooding 시킴, 아니면 discard 함 S (Source) A c A B B F E D C D G Network Layer 4-129

Reverse Path Forwarding(RPF) ( 예 ) Source=A A c B F E D G Network Layer 4-130

Spanning Tree First construct a spanning tree Nodes forward copies only along spanning tree A A c B c B F E D F E D (a) Broadcast initiated at A G (b) Broadcast initiated at D G Network Layer 4-131

Spanning Tree: Creation Center node (rendezvous point, core) 선정 Each node sends unicast join message to center node Message forwarded until it arrives at a node already belonging to spanning tree 이메시지가이동한경로가 spanning tree의 edge가됨 A A c 3 B c B 4 2 D D F 1 E 5 F E G G (a) Stepwise construction of spanning tree (Center 노드 = E) (b) Constructed spanning tree Network Layer 4-132

Sequence-number-controlled flooding 사용예 Gnutella Application-level broadcast 16-bit identifier, 16-bit payload descriptor TTL 사용 limited-scope flooding으로도불림 LSA (link-state advertisement) in OSPF 32-bit sequence number 16-bit age field; TTL과유사한역할 Network Layer 4-133

Multicast Mcast packet is delivered to only a subset of network nodes Internet: Class D The group of receivers associated with a class D address is referred to as a multicast group 호스트의 IP 주소 (unicast를위한주소 ) 는이 mcast IP 주소와는별개 ( 즉, 이두주소간에는연관성이없다 ) 네트웍층의 Multicast routing protocol IGMP, DVMRP, PIM, etc Network Layer 4-134

Multicast 4 node(green) has unicast IP, mcast IP 주소 Unicast address Network Layer 4-135

IGMP Internet Group Management Protocol IGMP 는 edge router 와연결된 host 간에만동작하는국지적프로토콜 이러한 edge router 들을포함한라우터들간에는별도의 multicast routing 프로토콜이필요함 PIM, DVMRP, MOSPF 등을사용 어느호스트가특정멀티캐스트그룹에속해있다고할때, 자신이속한 local net. 외부에 ( 즉, networkwide) 그특정멀티캐스트그룹에속한다른호스트를알아낼수없다. Network Layer 4-136

IGMP PIM, DVMRP, MOSPF Network Layer 4-137

IGMP 메시지 format Membership_query 메시지 Membership_report 메시지 Leave_group 메시지 Network Layer 4-138

IGMP 동작 1. 라우터는연결된호스트들중어느특정멀티캐스트그룹에속한호스트가어느것인지알기위해 membership_query 메시지발생 ( 그안에그특정멀티캐스트그룹주소를적어놓는다 ) 2. 라우터는연결된호스트들이속해있는멀티캐스트그룹들을다알기위해 membership_query 메시지발생 ( 이경우에는특정멀티캐스트그룹주소는적지않음 ) 3. 라우터는특정멀티캐스트그룹에속한호스트가하나도안남아있는지아닌지를확인하기위해 membership_query 메시지발생 ( 이경우에는특정멀티캐스트그룹주소를적어놓음 ) 1,2,3의경우에호스트는 membership_report 메시지로답함 (3의경우에아무도답하지않으면라우터는해당멀티캐스트그룹에속한호스트가더이상존재하지않는다고판단 Soft state) Network Layer 4-139

IGMP 동작 4. 호스트가특정멀티캐스트그룹에 join 하고싶으면연결된라우터에게 membership_report 메시지전송 ( 이안에그특정멀티캐스트그룹주소를적어놓는다 ) 즉, 멀티캐스트패킷의 sender 는해당그룹에 join 하는호스트들을통제할수없다. 또한 sender 는특정호스트를해당그룹에 add 할수도없다. 5. 호스트는특정그룹에서탈퇴하고싶을때는 leave_group 메시지를라우터로보내면됨. 6. 호스트는특정 sender 로부터멀티캐스트를받는것을거부할수있다 Network Layer 4-140

멀티캐스트라우팅 tree 생성방법 Group-shared tree 전체네트웍에서트리한개만생성 모든 sender 들이이동일한트리사용 생성방법 Minimal spanning tree (Steiner tree)» 전체네트웍에대한정보가필요하고, 연산이복잡하고라우터가 join/leave 한다음다시트리생성이필요하여실제로는사용이안됨 Center-based approach Source-based tree 각 sender (source) 를위해별도의 tree 생성 RPF 알고리즘사용하여 tree 생성 단, 어느라우터가멀티캐스트패킷수신시자신에속한호스트들중그멀티캐스트그룹에속한호스트가하나도없는경우에는 source 로의 upstream 라우터로자신을 tree 에서제외해달라는 prune 메시지를보냄. Network Layer 4-141

Internet 에서의멀티캐스트라우팅 프로토콜 DVMRP (Distance-Vector Multicast Routing Protocol) RFC 1075 De facto inter-as mcast 라우팅프로토콜 Mbone 에서사용 PIM (Protocol-Independent Multicast Routing Protocol) 어느 Unicast routing protocol 과도사용가능 Dense mode & Sparse mode Network Layer 4-142

Internet 에서의멀티캐스트라우팅 프로토콜 한 AS 내에서는한개의멀티캐스트라우팅프로토콜을사용하지만다른 AS 에서는다른멀티캐스트라우팅프로토콜사용가능 AS 간의멀티캐스트라우팅프로토콜필요 (DVMRP 가 de facto 로사용됨 ) 멀티캐스팅은 IP 층에서제공하는라우팅프로토콜 ( 즉, IGMP+ DVMRP, PIM) 보다응용층의 overlay 네트웍에서구현되고있는것이현실 Network Layer 4-143

DVMRP 동작 RPF with pruning 각라우터는모든가능한 source 까지의 shortest path 를 distance vector 방법을이용하여계산해놓고있음. 또한, 각라우터는 dependent downstream 라우터들을알아놓고있음 모든 downstream 라우터들로부터해당멀티캐스트그룹에대한 prune 메시지를받을때 upstream 으로이 prune 메시지를전달한다. Network Layer 4-144

PIM 두개의 mode 에따라다른동작 Dense mode 어느 area 에있는많은 ( 대부분의 ) 라우터들이멀티캐스트에참여할때 group members densely packed, in close proximity bandwidth more plentiful Sparse mode 어느 area 에있는라우터들중작은수가멀티캐스트에참여할때 group members widely dispersed bandwidth not plentiful Network Layer 4-145

PIM Dense mode 동작 DVMRP 와유사 (RPF with pruning) Sparse mode 동작 Group-shared tree (center-based approach) source 로부터 datagram 을받은라우터는랑데뷰포인트 (RP) 로 unicast 로보냄 RP 는 group-shared tree 를이용해멀티캐스트함. 특징 : RP 를기점으로 group-shared tree 에서 source-specific tree 로전환할수있음. Network Layer 4-146

PIM- Dense Mode flood-and-prune RPF, similar to DVMRP but underlying unicast protocol provides RPF info for incoming datagram less complicated (less efficient) downstream flood than DVMRP reduces reliance on underlying routing algorithm has protocol mechanism for router to detect it is a leaf-node router

Network Layer: summary What we ve covered: network layer services routing principles: link state and distance vector hierarchical routing IP Internet routing protocols RIP, OSPF, BGP what s inside a router? IPv6 Next stop: the Data link layer! Network Layer 4-148