컴퓨터네트워크 2014.05.14 장문정 (cathmjang@gmail.com) 홍익대학교게임소프트웨어전공
네트워크계층 이장의목표 : 네트워크계층서비스에대한기본원리를이해 네트워크계층서비스모델 포워딩 (forwarding) vs. 라우팅 (routing) 네트워크계층프로토콜 : IP, DHCP, ICMP 등 라우팅알고리즘 ( 경로선택 ) 라우팅프로토콜들 : RIP, OSPF, BGP 브로드캐스트 (broadcast) & 멀티캐스트 (multicast) 라우팅 2
IP 주소 IPv4 주소 호스트 / 라우터인터페이스를위한 32비트식별자인터페이스 호스트 / 라우터와물리링크사이의경계 라우터 : 2개이상의인터페이스호스트 : 한개혹은두개의인터페이스 IP 주소는각인터페이스와연관됨! 223.1.1.2 223.1.1.1 223.1.1.3 223.1.1.4 223.1.2.9 223.1.3.27 223.1.3.1 223.1.2.1 223.1.2.2 223.1.3.2 223.1.1.1 = 11011111 00000001 00000001 00000001 223 1 1 1 3
서브넷 (Subnets) IP 주소 네트워크부분 ( 상위비트 ) 호스트부분 ( 하위비트 ) 서브넷이란? IP 주소의네트워크 ( 서브넷 ) 부분이같은디바이스인터페이스중계하는라우터없이서로물리적으로연결 223.1.1.1 223.1.1.2 223.1.2.1 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 4
서브넷 (Subnets) 서브넷구성하는방법 서브넷을결정하기위하여 호스트나라우터에서각인 터페이스를분리하여고립된 네트워크를만듦 이고립된네트워크의종단 점은인터페이스의끝이됨 이렇게고립된네트워크를 각각서브넷이라함 5
서브넷 (Subnets) 몇개의서브넷이존재하는가? 223.1.1.1 223.1.1.2 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 6
서브넷마스크 ( 주소마스크 ) IP 노드에게정확한네트워크 ID 를제공하기위해서브넷 마스크를사용! 네트워크 ID 와호스트 ID 를구분! 32 비트값 네트워크 ID 에해당하는모든비트 = 1 호스트 ID 에해당하는모든비트 = 0 기본서브넷마스크 : 클래스기반네트워크 ID 에서사용 사용자정의서브넷마스크 : 서브넷이나슈퍼넷에서사용 7
서브넷마스크 ( 주소마스크 ) 서브넷마스크의 10 진수표기법 서브넷마스크의네트워크접두어길이표현 ( 프리픽스표기법 or CIDR 표기법 ) /<# of bits>: 네트워크 ID를정의하는비트의개수를표시 네트워크접두어표기법으로본기본서브넷마스크 8
사용자정의서브넷마스크 서브넷이나슈퍼넷을구성할때사용되는서브넷마스크 예 ) 138.96.58.0: 8 비트서브넷으로구성된클래스 B 네 트워크 ID라고가정 클래스기반호스트 ID 16비트중 8비트는서브넷네트워크 ID를표현하기위해사용! 서브넷으로구성된네트워크 ID: 138.96.58.0 이에해당하는서브넷마스크 : 255.255.255.0 다른표현법 : 138.96.58.0/24 Q) 138.23.0.0/16 과 138.23.0.0/24 는동일한네트워크 내에있는가? 9
네트워크 ID 결정 IP 주소와마스크값에대해 bit-wise AND 연산을수행 예 ) IP 주소 : 203.247.166.178 (C class) MASK: 255.255.255.0 IP 주소 & MASK = 203.247.166.0 ( 네트워크 ID!) 연습 ) IP 주소 : 129.56.189.41 이고, MASK: 255.255.240.0 일때, 네트워크 ID 는무엇인가? 10
클래스풀어드레싱 vs. 클래스리스어드레싱 클래스풀어드레싱 (classful addressing) IP 주소를네트워크, 서브넷, 호스트로나누는경우 클래스리스어드레싱 (classless addressing) 라우팅관점에서보면, 네트워크부분과서브넷부분은결국해당주소가어느네트워크에속해있는지알려주기위한것네트워크클래스와서브넷을하나로합쳐서보는개념을의미 CIDR (Classless InterDomain Routing): a.b.c.d/y 11
Subnet mask 사용방법 예 ) 연습1) 192.168.63.0/24 서브넷마크스길이와서브넷마스크는무엇인가? 가능한 IP 주소범위는? 네트워크주소는? 브로드캐스트주소는? 12
특수 IP 주소 Local loopback 주소 127.0.0.1 자신의컴퓨터가송신과수신컴퓨터로동작네트워크프로그램테스트용으로활용 13
IP 주소획득방법 개별 IP 주소를호스트에할당 시스템관리자에의해파일에저장 Windows: control-panel->network->configuration->tc p/ip->properties UNIX: /etc/rc.config DHCP (Dynamic Host configuration Protocol) DHCP 서버로부터동적으로주소를획득 플러그앤플레이 (plug-and-play) 14
DHCP 호스트가네트워크에접속할때, 네트워크서버로부터 IP 주소를동적으로획득하기위한프로토콜 네트워크에연결된동안만주소를가질수있음 주소의재사용이가능함 짧은시간동안네트워크에연결되는모바일사용자지원 DHCP 동작개요 호스트는 DHCP 서버발견메시지 (DHCP discover msg) 를브로드캐스트함 (Optional) DHCP 서버는 DHCP 제공메시지 (DHCP offer msg) 를통해응답함 호스트는 DHCP 요청메시지 (DHCP request msg) 를통해 IP 주소를요청 DHCP 서버는 DHCP ACK 메시지 (DHCP ACK msg) 를통해 IP 주소를전송함 15
DHCP Client-Server 시나리오 223.1.1.0/24 223.1.1.1 DHCP server 223.1.2.1 223.1.1.2 223.1.1.4 223.1.2.9 223.1.2.2 223.1.1.3 223.1.3.27 arriving DHCP client needs address in this network 223.1.2.0/24 223.1.3.1 223.1.3.2 223.1.3.0/24 16
DHCP Client-Server 시나리오 DHCP server: 223.1.2.5 DHCP discover src : 0.0.0.0, 68 dest.: 255.255.255.255,67 server yiaddr: out 0.0.0.0 there? transaction ID: 654 Broadcast: is there a DHCP arriving client DHCP request DHCP offer src: 0.0.0.0, 68 dest:: 255.255.255.255, 67 yiaddrr: 223.1.2.4 transaction t IP address! ID: 655 lifetime: 3600 secs Broadcast: OK. I ll take tha src: 223.1.2.5, 67 dest: 255.255.255.255, 68 yiaddrr: 223.1.2.4 transaction can use ID: 654 lifetime: 3600 secs Broadcast: I m a DHCP serv er! Here s an IP address you DHCP ACK src: 223.1.2.5, 67 dest: 255.255.255.255, 68 yiaddrr: 223.1.2.4 that transaction IP address! ID: 655 lifetime: 3600 secs Broadcast: OK. You ve got 17
DHCP Client-Server DHCP DHCP DHCP DHCP DHCP UDP IP Eth Phy DHCP DHCP DHCP DHCP DHCP DHCP UDP IP Eth Phy 168.1.1.1 router with DHCP server built into router DHCP DHCP DHCP DHCP DHCP UDP IP Eth Phy DHCP DHCP DHCP DHCP DHCP DHCP UDP IP Eth Phy router with DHCP server built into router 18
네트워크주소변환 (NAT) NAT (Network Address Translation) 19
네트워크주소변환 (NAT) NAT 사용동기 : 외부세계에서는지역네트워크는하나의 IP 주소로인식됨 모든디바이스에대해하나의 IP 주소만을사용함으로써 ISP 로부터여러개주소를할당받을필요없음 지역네트워크내에서는 외부세계에알리지않고도디바이스주소를변경할수있음 디바이스주소를변경하지않고 ISP 를바꿀수있음 지역네트워크내부의디바이스들은외부세계에서명시적으 로주소지정을하거나노출되지않음 ( 보안이점 ) 20
네트워크주소변환 (NAT) NAT 라우터구현 외부로나가는데이터그램 ( 출발지 IP 주소, 포트번호 ) 를 (NAT IP 주소, 새로운포트번호 ) 로대체 외부의원격클라이언트 / 서버는목적지주소로 (NAT IP 주소, 새로운포트번호 ) 를사용하여응답 NAT 변환테이블저장 NAT 변환테이블에 ( 출발지 IP 주소, 포트번호 ) 와 (NAT IP 주소, 새로운포트번호 ) 의변환쌍을저장 들어오는데이터그램 (NAT IP 주소, 새로운포트번호 ) 를 NAT 테이블에있는 ( 출발지 IP 주소, 포트번호 ) 로대체 21
네트워크주소변환 (NAT) 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 S: 138.76.29.7, 5001 D: 128.119.40.186, 80 138.76.29.7 S: 128.119.40.186, 80 D: 138.76.29.7, 5001 3 3: reply arrives dest. address: 138.76.29.7, 5001 10.0.0.4 S: 10.0.0.1, 3345 D: 128.119.40.186, 80 S: 128.119.40.186, 80 D: 10.0.0.1, 3345 1 1: host 10.0.0.1 sends datagram to 128.119.40.186, 80 4: NAT router changes datagram dest addr from 138.76.29.7, 5001 to 10.0.0.1, 3345 4 10.0.0.1 10.0.0.2 10.0.0.3 22
네트워크주소변환 (NAT) 16- 비트포트번호 단일 LAN 측주소로 6 만개동시연결 NAT 에대한논란 포트번호는호스트주소지정이아닌프로세스주소지정에 사용되어야함 라우터는계층 3 까지만처리해야함 종단간의논의에위반 호스트가 IP 주소와포트번호수정없이직접통신해야함 주소부족은 IPv6 로해결 23
ICMP ( 인터넷제어메시지프로토콜 ) 네트워크오류에관한정보를전송하기위해사용되는프로토콜네트워크계층에서상주하지않고 IP 데이터그램에캡슐화되어인터넷을통해전송 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 24
ICMP ICMP 메시지형식 ICMP 질의메시지 ICMP는질의를하거나응답함으로써정보를획득함일반적인질의메시지유형 25
ICMP 에코요청및응답 ping 프로토콜을구현하는데사용되는메시지 에코요청메시지는어떤컴퓨터상의 ICMP 소프트웨어로도전송될수있음타임스탬프요청및응답 호스트나라우터에서현재의날짜와시간을지시하는메시지 여러가지상황에서경과시간을측정하는도구로사용 두시스템간 IP 데이터그램이오고가는데필요한왕복시간 (RTT) 을결정주소마스크요청및응답 호스트의서브넷마스크를알아보기위해사용라우터정보요청 다른네트워크의호스트에게데이터전송시자신의네트워크에연결된라우터주소를요청하기위해사용 26
ICMP ICMP 오류메시지 가장일반적인 ICMP 메시지 전송을시도할때또는 IP 데이터그램전송도중발생하는다 양한형태의오류상태를통보 일반적인오류메시지발생유형 27
ICMP 목적지도달불가능 라우터는데이터그램이최종목적지로전달될수없을때, 목적지도달불가능메시지를데이터그램을생성한호스트에게전송 Network Unreachable Host Unreachable Protocol Unreachable Port Unreachable Source Route 송신지억제 송신시스템이처리하기에너무많은데이터를전송하면, 수신지시스템은송신시스템에게 ICMP 송신지억제오류메시지를전송하여전송속도를줄일것을요구함 28
ICMP 재지정 송신측에적합하지않은경로설정이되어있다고판단되는경우노드를재지정해주는오류메시지전송시간초과 Time-to-Live Exceeded in Transit 데이터그램의 TTL = 0 일때마다라우터는데이터그램을소멸시키고시간초과메시지를보냄 Fragment Reassembly Time Exceeded 주어진데이터그램으로부터의모든단편들이도착하기전에재조립타이머가끝난다면호스트에의해시간초과메시지가보내짐 매개변수문제 라우터나호스트는데이터그램의 IP 헤더매개변수에문제가있음을발견하면데이터그램을폐기함 29
ICMP ICMP 오류메시지를생성하지않는경우 ICMP 오류메시지를전송하는데이터그램에대해서 멀티캐스트주소를가진데이터그램에대해서 127.0.0.0 이나 0.0.0.0 과같은특수주소를가진데이터그 램에대해서 30
IPv6
변화동기 제한된주소공간 현재 IP 는 32 비트주소공간을사용 향후네트워크성장률 을만족하지못함 ( 빠른속도로고갈되어가고있음 ) 새로운인터넷응용의필요성 실시간멀티미디어전송서비스 고품질의서비스요구 (QoS, Quality of Service) 그룹통신 동일한서비스를여러사용자에게제공하기위함 멀티캐스트 새로운주소지정과경로설정을요구 32
IPv6 특징 새로운주소체계와데이터그램형식 128 비트주소공간 가변길이의다중확장헤더사용 오디오와비디오전송지원 고품질의높은성능을보장하는경로설정 확장프로토콜 보안기능추가 IPSec 새로운기능추가에대한유연성제공 33
IPv6 16 바이트, 즉 128 비트로구성 주소를읽기쉽게하기위해 16 진수콜론표기를규정 128 비트는길이가 2 바이트인 8 개의영역으로나뉨 16 진수표기법에서 2 바이트는 4 개의 16 진수로표현되어전체적으로 32 개의 16 진수로표현 34
IPv6 헤더 IPv6 패킷형식 우선순위 ( 트래픽클래스 ) 흐름중인데이터그램들사이에우선순위를부여흐름라벨 같은흐름의데이터그램을구분다음헤더 데이터그램의데이터가전달될상위계층프로토콜을구분 32 bits 35
IPv6 다중확장헤더 사용목적 경제성 기능별헤더분할로인한공간절약작은데이터그램은적은전송시간을요구 IPv4 헤더에는모든기능이표현되어사용되지않는부분에대한낭비가있음 확장성 새로운기능의추가가용이프로토콜설계에대한유연성제공 IPv4 같은고정헤더는새로운기능을추가하기위해헤더전체를수정해야함 36
IPv6 주소지정 Type ID: Provider-based address 정의 Registry ID Provider ID: ISP 할당값 Subscriber ID: ISP에서가입자에게부여하는값 Subnet ID Node ID 37
IPv4 vs. IPv6 IPv6 에서는 고정된길이의 40 바이트헤더 가변길이의다중확장헤더사용 체크섬필드가없음 각홉에서의처리시간을줄이기위해서 옵션필드는더이상표준 IP 헤더필드가아님 IPv6 헤 더의 다음헤더 중하나가될수는있음 IPv6 라우터는단편화 / 재결합을수행하지않음 38
IPv4 IPv6 전환전략 인터넷에많은시스템이있으므로 IPv4에서 IPv6로전환하기에는많은시간이필요 전환은 IPv4와 IPv6 시스템이공존하고있을때발생되는문제를방지하면서점차적으로이루어져야함 IETF에의해고안된세가지전환전략 39
이중스택 인터넷의모든시스템이 IPv6를사용할때까지 IPv4와 IPv6를동시에사용함패킷을목적지로보낼때버전을결정하기위해송신측에서 DNS에질의를함 DNS가 IPv4 주소를응답한다면송신측은 IPv4 패킷을보내고, IPv6 주소를응답하면송신측은 IPv6 패킷을보내게됨 40
터널링 (Tunneling) IPv6 를사용하는컴퓨터들이통신하기위해 IPv4 를사용하 는네트워크영역을통과해야할때사용! IPv6 패킷은 IPv4 를사용하는네트워크영역을통과할때 IPv4 패킷내에캡슐화가되고, 영역을통과한다음역캡 슐화됨 IPv4 header fields IPv4 source, dest addr IPv6 header fields IPv6 source dest addr UDP/TCP payload IPv4 payload IPv6 datagram IPv4 datagram 41
터널링 logical view: A IPv6 B IPv6 IPv4 tunnel connecting IPv6 routers E IPv6 F IPv6 physical view: A B C D E F IPv6 IPv6 IPv4 IPv4 IPv6 IPv6 42
터널링 logical view: A IPv6 B IPv6 IPv4 tunnel connecting IPv6 routers E IPv6 F 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 data A-to-B: IPv6 B-to-C: IPv6 inside IPv4 B-to-C: IPv6 inside IPv4 E-to-F: IPv6 43
헤더변환 헤더변환은대부분의인터넷이 IPv6 를사용하지만일부 시스템이 IPv4 를사용하는경우에필요 송신측에서는 IPv6 를사용하기를원하지만수신측에서 IPv6 를이해하지못하는경우, 패킷이수신측에서이해할 수있는 IPv4 형식으로헤더형식이헤더변환을통하여 변환되어야만함 44
그래프추상화 (Graph Abstraction) Graph: G = (N, E) N = set of routers = {u, v, w, x, y, z} E = set of links = {(u,v), (u,x), (v,x), (x,w), (x,y), (w,y), (w,z), (y,z)} 5 2 v 3 w 5 u 1 x 2 1 3 y 1 2 z 45
그래프추상화 : 비용 (costs) c(x,x ): 링크 (x,x ) 의비용 예 ) c(w,z) = 5 비용은대역폭에반비례 & 혼잡에비례함 경로,,,, 의비용 =,,, 라우팅알고리즘 : 최소비용경로를찾는알고리즘 46
라우팅알고리즘분류 글로벌 vs. 분산정보 글로벌라우팅알고리즘 모든라우터가완벽한정보 ( 토폴로지, 링크비용정보 ) 를가짐링크상태 (Link state, LS) 알고리즘 분산라우팅알고리즘 라우터가직접연결된이웃링크의비용에대한정보만가짐반복계산과정과이웃노드들간의정보교환거리벡터 (Distance vector, DS) 알고리즘 정적 (static) vs. 동적 (dynamic) 정적라우팅알고리즘 경로가아주느리게변경 ( 라우터포워딩테이블을수작업으로수정 ) 동적라우팅알고리즘 경로가빠르게변경 주기적인변경, 링크비용변화시변경 47
링크상태라우팅알고리즘
링크상태라우팅알고리즘 Dijkstra algorithm 네트워크토폴로지와링크비용이모든노드에알려짐 링크상태패킷을브로드캐스팅하여알려줌 모든노드들이같은정보를가짐 한노드에서다른모든노드들까지의최소비용경로를계산 해당노드에대해포워딩테이블제공 K 번째반복이후에 k 개의목적지노드에대해최소비용경 로가계산 49
링크상태라우팅알고리즘 기호정의 c(x,y): 노드 x 에서 y 까지링크비용, 이웃이노드가아니 면 D(v): 출발지에목적지 v 까지경로의현재비용 p(v): 출발지에서 v 까지경로에서 v 의이전경로 ( 노드 ) N : 최소비용경로로명확히알려진노드의집합 50
Dijkstra 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' 51
Step 0 1 2 3 4 5 Dijkstra algorithm: 예 1 D(v) p(v) D(w) p(w) D(x) p(x) D(y) p(y) D(z) p(z) N' u 7,u 3,u 5,u uw 6,w 5,u 11,w uwx 6,w 11,w 14,x uwxv 10,v 14,x uwxvy 12,y uwxvyz x 9 5 4 7 8 u 3 w y 2 z 3 7 4 v 52
Dijkstra algorithm: 예 2 53 Step 0 1 2 3 4 5 N' u ux uxy uxyv uxyvw uxyvwz D(v),p(v) 2,u 2,u 2,u D(w),p(w) 5,u 4,x 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 u y x w v z 2 2 1 3 1 1 2 5 3 5
Dijkstra algorithm: 예 3 알고리즘종료후각노드는출발지에서부터시작된최소비용경로를따라이전노드를가짐노드 u의포워딩테이블은최소비용경로에서다음홉에대한정보로구성 U 에서부터의최소비용경로결과 U 에대한포워딩테이블결과 u v w z destination v x link (u,v) (u,x) x y y w (u,x) (u,x) z (u,x) 54
Dijkstra algorithm: 진동 (Oscillation) 링크비용 = 전송되는트래픽양초기에는시계반대방향경로선택 : D A, C B A 링크상태알고리즘을한번더수행하면시계방향선택 : B C D A 다시수행하면시계반대방향, 또다시수행하면시계방향경로를선택하여진동 1 D A 1 1+e 0 0 0 C e e initially B 1 A 2+e 0 D 0 1+e 1 C B given these costs, find new routing. resulting in new costs 0 D A 0 2+e 1 0 0 C 1+e B given these costs, find new routing. resulting in new costs A 2+e 0 D 0 1+e 1 C B given these costs, find new routing. resulting in new costs 0 55
거리벡터라우팅알고리즘
거리벡터라우팅알고리즘 벨만 - 포드식 (Bellman-Ford equation) 이용하여최소비용을계산, : x 에서 y 까지최소비용경로의비용, : 이웃 v 까지의비용 min: x 의모든이웃 v 에대해서적용함 57
벨만 - 포드식예 5, 3, 3 B-F 식에의해,,,,, min25, 13, 53 4 최소값을갖는노드는최단경로에서다음홉 포워딩테이블의엔트리제공 5 u 1 2 v x 2 3 1 3 w y 1 5 2 z 58
거리벡터라우팅알고리즘 노드 X 가유지해야하는정보들 예측! X 에직접연결된이웃 v 까지의비용 :, 각이웃에대한거리벡터 : : 자신의거리벡터 : : 59
기본아이디어 각노드는비정기적으로이웃에게자신의거리벡터예측 값을보냄 비동기적 노드 x 가이웃으로부터새로운 DV 예측값을받으면벨만 - 포드식을사용하여자신의 DV 를갱신 D x (y) min v {c(x,v) + D v (y)} for each node y N 노드들이 DV 를계속교환하게되면각비용예측 는 실제최소비용 에근접하게됨! 60
거리벡터라우팅알고리즘 반복적, 비동기적 지역링크비용변경 이웃으로부터의 DV 갱신 분산적 각노드는자신의 DV 가갱신될때에만이웃노드들에게광고 필요하면, 이웃노드들이자신의이웃들에게광고 각노드 : wait for (change in local link cost or msg from neighbor) recompute estimates if DV to any dest has changed, notify neighbors 61
node x table from x y z cost to x y z 0 2 7 D x (y) = min{c(x,y) + D y (y), c(x,z) + D z (y)} = min{2+0, 7+1} = 2 from x y z x y z 0 cost to 2 2 0 1 7 1 0 3 D x (z) = min{c(x,y) + D y (z), c(x,z) + D z (z)} = min{2+1, 7+0} = 3 node y table from x y z cost to x y z 2 0 1 x 2 y 7 1 z node z table cost to x y z from x y z 71 0 time 62
node x table from x y z node y table from x y z cost to x y z 0 2 7 cost to x y z D x (y) = min{c(x,y) + D y (y), c(x,z) + D z (y)} = min{2+0, 7+1} = 2 2 0 1 from from x y z x y z x y z 0 cost to 2 2 0 1 7 1 0 cost to x y z 0 2 7 3 2 0 1 7 1 0 from from x y z x y z cost to x y z 0 2 3 2 0 1 3 1 0 cost to x y z 0 2 3 2 0 1 3 1 0 D x (z) = min{c(x,y) + D y (z), c(x,z) + D z (z)} = min{2+1, 7+0} = 3 y 2 1 x 7 z node z table x y z from cost to x y z 71 0 from x y z cost to x y z 0 2 7 2 0 1 3 1 0 from x y z cost to x y z 0 2 3 2 0 1 3 1 0 time 63
링크비용변경 노드가링크비용을감지 거리벡터를재계산 거리벡터값이변경되었으면이웃노드들에게알림 1 예 ( 목적지 x) 시간 y 가링크비용변경을감지하고 (4 1), 거리벡터를갱신한후이웃노드들에게알림 x 4 y 50 1 z 시간 z는갱신메시지를받아서테이블을갱신함 z는 x까지의최소비용을계산하고 (5 2) 이웃에게알림 시간 y는 z의갱신메시지를받아서거리테이블을갱신 y의최소비용의변경이없으므로 z에게메시지를보내지않음 비용이감소하는좋은소식은네트워크전역에빨리전파! 64
링크비용변경 비용이증가하는나쁜소식은네트워크전역에느리게전파 예 ( 목적지 x) 링크비용변경전 : 4, 1, 1, 5 시간 y가링크비용변경을감지하고 (4 60), 거리벡터를계산,,, min 600,15 6? 시간 y에서 x까지새로운비용 를알림 y z, z y 로라우팅루프발생 시간 이후 z 는 6 이라고통보받고새로운최소비용계산,,, min 500, 16 7 유사한반복으로 8 다시 9로변경 반복! z 가 y 를통한경로비용이 50 보다크다는사실을알때까지 44 번반복 무한카운트 (count to infinity) 문제 60 x 4 y 50 1 z 65
Poison reverse z 가 y 를통해목적지 x 로가는경로를설정하는경우 예 z 는 y 에게 z 에서 x 까지의거리가무한대라고알림 : 시간 y가링크비용변경을감지하고 (4 60), 포이즌리버스의결과로 로변경하고거리벡터를계산,,, min 600,1 60 y 는 z 를경유하는대신 x 로직접라우팅하여 60 으로 z 에게통보 시간 : z는 x로가는경로비용을 50으로변경하고 50 ( 최소비용 ) 으로 y에게알림 시간 : y는 z를경유하여 x로가는경로를선택하고, 51 로갱신하고알림 시간 ( 실제는 51) 로알려서 z에서 x로역경로를깸 3 개이상의이웃노드를포함한루프인경우에는감지못함! 66
링크상태 vs. 거리벡터 링크상태알고리즘 다른모든노드와통신 링크비용이변할때마다새로운링크비용이모든노드에게전달되어야함 직접연결된링크비용만을제공 거리벡터알고리즘 직접연결된이웃과통신 모든노드까지의최소비용예측값을이웃에게제공 새로운링크비용이해당노드의최소비용경로에변화를준경우에만수정된링크비용을전파함 매우천천히수렴 무한카운트문제가있음 67