4장. 인터네트워킹 간단한 인터네트워킹 라우팅 전역 인터넷 멀티캐스팅 IP DHCP Virtual Networks Mobile hosts 전역 인터넷 IPv6 멀티캐스팅

라우팅(Routing) 포워딩과 라우팅의 차이 네트워크의 그래프 표현 문제: 임의의 두개 노드사이의 최저 경로를 찾는 것 포워딩: 목적지 주소와 라우팅 테이블에 기초해서 출력 포트를 선택 라우팅: 라우팅 테이블을 만드는 작업 네트워크의 그래프 표현 문제: 임의의 두개 노드사이의 최저 경로를 찾는 것 단, 중앙 관리 없이, 각 라우터가 독자적으로 고려 요소: 정적 요소: 토폴로지 동적 요소: 부하

거리 벡터 (Distance Vector) 라우팅 거리 벡터 (Distance Vector) 각 노드는 다음의 3개의 인자로 구성된 트리플의 집합을 유지 (Destination, Cost, NextHop) 각 노드는 자신과 직접 연결된 노드들에게 이 집합의 갱신 정보를 주고 받음 주기적으로 : 몇 초단위로 표가 바뀔 때마다 : 트리그(triggered) 갱신이라 부름 갱신 정보는 다음과 같은 형태의 리스트이다 (Destination, Cost) 더 좋은 경로를 받으면, 자신의 테이블을 갱신 적은 비용의 경로 : NextHop은 갱신 정보를 보낸 쪽으로 최신 정보 : 테이블의 NextHop에서 온 갱신 정보 테이블에 이미 존재하는 경로는 refresh; 타임 아웃을 설정하여 갱신 정보가 오지 않으면 삭제

거리 벡터 구현: 테이블 갱신 void mergeRoute (Route *new) { int i; 라우팅 거리 벡터 구현: 테이블 갱신 void mergeRoute (Route *new) { int i; for (i = 0; i < numRoutes; ++i) if (new->Dest == rt[i].Dest) if (new->Cost + 1 < rt[i].Cost) break; else if (new->NextHop == rt[i].NextHop) else return; } rt[i] = *new; rt[i].TTL = MAX_TTL; ++rt[i].Cost; if (i == numRoutes) /* 새로운 Dest */ ++numRoutes;

라우팅 거리 벡터: 예 노드 A의 라우팅 표

라우팅 루프 (Routing Loops) : 예1 F는 G로 가는 링크가 끊어졌음을 발견함 F는 집합에서 G로 가는 거리를 무한대로 바꾸고 A에게 갱신된 정보를 보냄 A역시 F를 이용해서 G에 갔기 때문에 집합에서 G로 가는 거리를 무한대로 바꿈 A는 C에서 G로 2홉 경로가 있다는 정보를 주기적으로 받음 A는 집합에서 G에 가는 거리를 3으로 바꾸고 이를 F에게 보냄 F는 A를 경유하여 G에 4홉 만에 갈 수 있다고 결정함 G 1 F 2 노드 F 노드 A 노드 C D F, G 사이 링크 고장 G   D G A F E B C G   G C 3 G A 4

라우팅 루프 (Routing Loops) : 예2 A로부터 E로 가는 링크가 끊어짐 A는 E로 가는 길이 무한대라고 알림 한편, 이 정보가 전달되기 전까지는 B와 C는 E로 가는 길이 2라고 알림 B는 E에 3홉 만에 갈 수 있다고 결정; A에게 이 정보를 알림 A는 E에 4홉 만에 갈 수 있다고 결정; C에게 이 정보를 알림 C는 E에 5홉 만에 갈 수 있다고 결정...... E 1 A 2 노드 A 노드 B 노드 C A, E 사이 링크 고장 E   E   E   E C 3 E B 4 E A 5 E C 6

라우팅 루프 문제의 해결 라우팅의 루프를 없애는 방법 무한대의 값을 16으로 설정 수평 분할 (split horizon) 정보의 소스에게는 갱신 정보를 보내지 않음 극단적 수평분할 (split horizon with poison reverse) 갱신된 정보를 전파시키기 전에 시간 간격을 둔다. 라우팅 정보의 수렴 시간이 길어짐. 단순 Next_Hop 대신에 경로(Path) 정보 교환

링크 상태 (Link State)  LSP를 만든 노드의 식별자(id)  직접 연결된 링크 각각에 대한 비용(cost) 라우팅 링크 상태 (Link State) 정책: 직접 연결된 링크의 정보를 (완전한 라우팅 테이블이 아님) 모든 노드에게 (단지 이웃한 노드가 아닌) 보낸다.  각 노드는 네트워크의 토폴로지를 알 수 있다.  각 노드는 스스로 알고리즘 수행 / 테이블 작성  링크 상태 패킷(Link State Packet) (LSP)  LSP를 만든 노드의 식별자(id)  직접 연결된 링크 각각에 대한 비용(cost)  순서 번호 (SEQNO)  이 패킷의 수명(time-to-live) (TTL)

신뢰성 있는 플러딩 (Reliable Flooding) 라우팅 신뢰성 있는 플러딩 (Reliable Flooding) 링크 상태 정보를 모든 노드에게 보내는 방법 각 노드로부터 받은 가장 최근의 LSP를 저장 LSP를 보낸 노드를 제외하고 모든 노드에게 받은 LSP를 포워드함 주기적으로 새로운 LSP를 생성; 이때 순서 번호(SEQNO)는 증가시킴 재시동할 경우 SEQNO를 0에서 시작 각각의 저장된 LSP에 대한 TTL을 감소; TTL=0일 때 삭제 X A C B D (a) (b) (c) (d)

경로 계산(Route Calculation) (이론적으로) 라우팅 경로 계산(Route Calculation) (이론적으로) Dijkstra의 최단 경로(shortest path) 알고리즘 N 은 그래프에서의 노드 집합 l(i,j)은 에지(i,j)에 대한 음수가 아닌 비용(가중치) s (s  N)는 경로 계산 노드 M은 현재까지 결정된 노드들의 집합을 나타냄 C(n)은 s 에서 n까지 경로의 비용 D A B C 5 3 2 11 10 M = {s} for each n  (N - {s}) C(n) = l(s,n) while(N  M) M = M  {w} such that C(w) is the minimum for all w  (N - M) for each n  (N - M) C(n) = MIN(C(n),C(w)+l(w,n))

메트릭 (Metrics) (1) 초기의 ARPANET 메트릭 새로운 ARPANET 메트릭 라우팅 메트릭 (Metrics) (1) 초기의 ARPANET 메트릭 각 링크에서 큐(queue)에 대기하고 있는 패킷의 수로 측정 대기 시간(latency) 또는 대역폭(bandwidth)과는 무관 새로운 ARPANET 메트릭 각 패킷에 들어온 도착시간(AT )을 찍어 줌 출발 시간(DT )을 기록 링크-레벨에서 ACK가 도착했을 때, 다음을 계산 Delay = (DT - AT) + Transmit + Latency 타임아웃이 발생하면, DT 는 재전송 시간으로 reset link cost(링크 비용) = 일정 시간 동안의 평균 지연시간

메트릭 (Metrics) (2) “New”메트릭이 가지는 문제 개선된 ARPANET 메트릭 라우팅 메트릭 (Metrics) (2) “New”메트릭이 가지는 문제 부하가 적은 경우, 정적인 요소가 비용에 미치는 영향이 큼; OK 부하가 큰 경우, 혼잡이 발생한 링크는 매우 높은 많은 비용이 됨; 패킷이 집중된 링크와 유휴 링크사이를 진동하는(oscillate) 현상을 보임. 비용의 범위가 넓음; 9.6Kbps의 링크 1-hop의 경로보다 부하가 작은 56Kbps 링크 126개로 가는 경로가 선호될 수 있음. 개선된 ARPANET 메트릭 지연 시간의 측정 대신에 링크의 이용율을 사용 동적 범위를 압축 높은 부하일 때도 유휴 상태 때의 3배 이상의 비용을 가질 수 없음 최대 비용도 최소 비용의 약 7배로 저속의 지상 링크보다 고속의 위성 링크를 선호하도록 비용은 부하가 적당히 높을 때만 링크 이용율의 함수가 되도록

메트릭 (Metrics) (3) 225 New metric (routing units) 140 90 75 60 30 25% 라우팅 메트릭 (Metrics) (3) 225 New metric (routing units) 140 90 75 60 30 25% 50% 75% 100% 9.6-Kbps satellite link 9.6-Kbps terrestrial link 56-Kbps satellite link 56-Kbps terrestrial link Utilization

이동 호스트에 대한 라우팅 문제 IP 주소는 계층적; 주소에 네트워크 주소 부분 포함 라우팅 : Mobile IP 이동 호스트에 대한 라우팅 문제 IP 주소는 계층적; 주소에 네트워크 주소 부분 포함 호스트가 이동하여 다른 네트워크에 접속되면, 패킷 전달 불가능 접근방법 새 IP 주소 할당  통신 중단; 서비스 중단 Mobile IP 호스트의 이동이 투명하도록 기존 통신 소프트웨어 및 라우터에 변경 없이 이동 호스트 지원

Mobile IP 구성 요소 home address : 이동 호스트의 영구적 IP 주소 Home Agent (HA) : 이동 호스트의 홈 네트워크에 있는 라우터 반드시 라우터일 필요는 없음. Foreign Agent (FA) : 이동 호스트가 접속되어 있는 외부 네트워크의 라우터 care-of-address(COA) : 이동 호스트에 대한 패킷을 보낼 주소; 대개 FA 주소 구성 설정 HA와 FA는 주기적으로 자신의 존재를 홍보 이동 호스트는 HA의 주소 인식 이동 호스트가 어떤 외부 네트워크에 접속하면  FA 인식 ; HA의 주소를 알림 FA는 HA에게 care-of-address 통보

Mobile IP의 패킷 전달 이동 호스트로부터의 패킷 전달: 기존과 동일 (보안, 멀티캐스팅 제외) 이동 호스트로의 패킷 전달: Internetwork Foreign agent (12.0.0.6) Mobile host (10.0.0.9) Home agent (10.0.0.3) Home network (network 10) Sending host

세부 문제/기술 HA가 이동호스트로 향하는 패킷을 가로채는 방법 Proxy ARP 라우팅 : Mobile IP 세부 문제/기술 HA가 이동호스트로 향하는 패킷을 가로채는 방법 Proxy ARP HA가 이동호스트로의 패킷을 FA에게 보내는 방법 터널링 FA가 수신된 패킷을 이동호스트로 전달하는 방법 IP 포워딩을 사용하지 않고, Hardware 주소로 직접 FA와 이동호스트가 동일한 경우 (Collocated COA) FA가 없는 네트워크로 이동 등 처리 간단; 단, 동적으로 IP 주소를 배정 받을 수 있어야 함. 보안 문제 제3자가 FA를 자처하며, 이동호스트로의 패킷을 interception

경로 최적화 ‘triangle routing problem’ HA가 송신자에게 ‘binding update’ 메시지를 보내서 라우팅 : Mobile IP 경로 최적화 ‘triangle routing problem’ HA가 송신자에게 ‘binding update’ 메시지를 보내서 이동호스트의 care-of-address를 알려줌 송신자는 Binding cache를 유지하면서 FA로 직접 터널링

Interdomain 라우팅 아이디어 라우터들을 계층화하여 분류 전역 인터넷 : 인터도메인 라우팅 Interdomain 라우팅 아이디어 라우터들을 계층화하여 분류 즉, 어떤 라우터가 통신할 수 있는 상대 라우터를 제한하는 또 다른 계층 구조를 도입 (패킷을 포워드하는 방법을 관장하는 주소 구조가 첫번째 계층 구조임)

Interdomain 라우팅 (2) 자율 시스템 (Autonomous System (AS)) 두 단계의 경로 전파 계층 구조 전역 인터넷 : 인터도메인 라우팅 Interdomain 라우팅 (2) 자율 시스템 (Autonomous System (AS)) 네트워크 관리 범위 예: 대학, 회사, 기간 통신망 네트워크 각 AS에는 16-bit 숫자를 할당 두 단계의 경로 전파 계층 구조 내부 게이트웨이 프로토콜 (interior gateway protocol) 각 AS는 자신의 프로토콜 선택 외부 게이트웨이 프로토콜 (exterior gateway protocol) 인터넷 전체의 표준

대표적 내부 게이트웨이 프로토콜 RIP: Route Information Protocol XNS에 의해서 개발됨 전역 인터넷 : 인터도메인 라우팅 대표적 내부 게이트웨이 프로토콜 RIP: Route Information Protocol XNS에 의해서 개발됨 Unix와 함께 배포됨 거리 벡터 알고리즘 (distance-vector algorithm) 홉 카운트(hop-count) 기반 OSPF: Open Shortest Path First 최근의 인터넷 표준 링크상태(link-state) 알고리즘 사용 부하 균형 (load balancing) 지원 인증(authentication) 지원

EGP: 외부 게이트웨이 프로토콜 (Exterior Gateway Protocol) 전역 인터넷 : 인터도메인 라우팅 EGP: 외부 게이트웨이 프로토콜 (Exterior Gateway Protocol) 개요 트리 구조의 인터넷을 위해 설계 최단 경로보다는 도달 가능성(reachability에 관심 N1 N3 N2 N6 N5 N4 Exterior Neighbor (Other system) G5 G4 G3 G2 G1 AS

BGP-4: (Border Gateway Protocol) 전역 인터넷 : 인터도메인 라우팅 BGP-4: (Border Gateway Protocol) 인터넷은 임의로 연결된 AS들의 집합이라 가정. 트래픽 유형 지역 트래픽 (local traffic): AS 내부 노드에서 시작하거나 내부 노드에서 종료하는 트래픽, 전이 트래픽 (transit traffic): AS를 통과하여 지나가는 트래픽 이와 같은 정의에 따라, AS는 다음과 같은 3가지 유형으로 분류할 수 있다. 스터브(Stub) AS: 다른 AS와 오직 하나만의 연결을 갖고 있는 AS;그러한 AS는 지역 트래픽만을 처리. 다중 연결(Multihomed) AS: 두개 이상의 다른 AS와 연결되어 있으나, 전이 트래픽은 처리하지 않음. 전이(Transit) AS: 두개 이상의 다른 AS와 연결되어 있고, 전이 트래픽 및 지역 트래픽 모두를 처리하록 설계. 각각의 AS는: 하나 또는 그 이상의 변방 라우터를 가짐 다음과 같은 사항을 알리는 하나의 BGP 대변인( speaker )를 가짐: 지역 네트워크들 도달할 수 있는 다른 네트워크 (전이 AS 경우에만) path 정보

BGP의 예 AS 2의 대변인(speaker)은 P와 Q에 도착할 수 있다고 알려줌 전역 인터넷 : 인터도메인 라우팅 BGP의 예 Backbone network (AS 1) Regional provider A (AS 2) Regional provider B (AS 3) Customer P (AS 4) Customer Q (AS 5) Customer R (AS 6) Customer S (AS 7) 128.96 192.4.153 192.4.32 192.4.3 192.12.69 192.4.54 192.4.23 AS 2의 대변인(speaker)은 P와 Q에 도착할 수 있다고 알려줌 네트워크 128.96, 192.4.153, 192.4.32, 및 192.4.3은 AS 2로부터 직접 도착할 수 있음. 백본 네트워크의 대변인은 이에 따라 다음을 알림 네트워크 128.96, 192.4.153, 192.4.32, 및 192.4.3은 경로 (AS 1, AS 2)를 따라 도착할 수 있음. 대변인은 이전에 알렸던 경로를 취소할 수도 있음