Computer Network ( Routing Technology )

Presentation on theme: "Computer Network ( Routing Technology )"— Presentation transcript:

1 Computer Network ( Routing Technology )
오민식 이인수 황인률 서유화

2 목 차 Routing Routing Protocol 참고 자료 라우팅의 개요 라우팅의 두가지 방법
목 차 Routing 라우팅의 개요 라우팅 기능 라우팅 알고리즘 라우팅의 두가지 방법 동적 라우팅 정적 라우팅 AS (Autonomous System) 라우팅 프로토골 Routing Protocol RIP (Routing Information Protocol) OSPF (Open Shortest Path First) 참고 자료

3 1.Routing의 개요(1) Routing Router 기능 라우터는 다양한 네트워크를 연결하는 인터넷의 필수 적인 요소
패킷을 전송하기 위해 송신측에서 목적지까지의 경로를 정하고 정해진 경로를 따라 패킷을 전달하는 일련의 과정 OSI reference model의 Layer 3 Network 계층에서 수행 Router 기능 Router 는 OSI reference model의 Layer3 device로 네트워크의 logical topology에 관한 정보를 주고 받고 logical topology를 통해 배운 정보를 바탕으로 작성된 Map을 이용하여 Packet을 전송 Packet OSI reference model의 Layer3 PDU(Protocol Data Unit)으로 라우터가 해석할 수 있는 목적지 및 주소를 포함하고 있음 Network의 logical topology를 통해 Map 작성 및 경로 제시

4 1.Routing의 개요 (2) 라우팅 알고리즘 라우팅 프로토콜 라우팅 프로토콜의 목적 최적의 경로를 찾는 방법
정적 라우팅 알고리즘 관리자가 직접 라우팅 테이블 설정 프로세스 오버헤드가 작지만 설정 유지가 어렵고 변화에 적응을 하지 못한다 동적 라우팅 알고리즘 라우팅 정보 변화에 능동적으로 대처 적응성과 구성을 유지하기가 쉽지만 오버헤드 증가 및 대역폭 소비가 발생한다 라우팅 프로토콜  라우터들은 패킷을 목적지까지 전달하기 위해서 인접한 라우터 사이에서 경로정보를 주고 받는데, 이때의 경로정보를 작성하고 제어하는 프로토콜 네트워크 정보의 생성, 교환 제어하는 프로토콜 라우팅 프로토콜의 목적 최적 경로 결정 Loop-free routing 빠른 convergence 설계 관리 최소화 갱신으로 인한 트래픽 발생 최소화

5 1.Routing의 개요 (3) AS (Autonomous System) 하나의 관리 도메인에 속해 있는 라우터들의 집합
IGP (Interior Gateway Protocol) AS내에서 라우팅 정보 교환 (ex. RIP, OSPF, …) EGP (Exterior Gateway Protocol) AS간의 라우팅 정보 교환 (ex. BGP, …)

6 1.Routing의 개요 (4) 라우팅 기본원칙 라우터는 다른 네트워크의 경로를 나타내는 네트워크 IP 주소와 지역 네트워크에 대한 호스트 IP 주소를 나열하고 있는 라우팅 테이블을 가지고 있음 라우터에서 IP 패킷의 처리 되는 과정 IP 패킷이 도착하면 목적지 주소를 찾기 위해 라우팅 테이블을 검색 패킷이 다른 네트워크로 전달되어야 하는 것이면 테이블의 인터페이스에 있는 다음 네트워크로 전달 IP 패킷이 LAN에 있는 호스트와 같이 라우터의 지역네트워크에 있다면 직접 보냄 위와 같은 검색 후에도 라우팅 테이블에 경로가 검색되지 않은 경우 디폴트 라우터로 보내짐 라우터들이 다른 네트워크들과 지역 호스트에 도달할 수 있는 경로만을 유지 하면 되기 때문에 라우팅 테이블의 크기를 크게 줄일 수 있게 함

7 2.RIP (Routing Information Protocol) (1)
개요 버클리 대학에서 개발한 RIP은 오늘날 네트워크에서 가장 널리 사용되고 있는 라우팅 프로토콜 거리 벡터 알고리즘을 사용 가장 단순한 라우팅 프로토콜 라우터는 주기적으로 이웃 라우터와 라우팅 정보 교환 거리벡터값으로 홉카운트 사용 RIP 패킷의 대부분은 네트워크 주소와 비용의 쌍인 정보 거리 벡터 알고리즘 (Distance Vector algorithm) 자신의 라우팅 테이블을 주기적으로 이웃 라우터에게 전송 이웃 라우터로 부터 라우팅 정보 수신하여 자신의 라우팅 테이블을 갱신하고 이를 통하여 경로 선택 RIP 네트워크 모델

8 2.RIP (Routing Information Protocol) (2)
라우팅 테이블 생성 목적지 주소와 비용, 이웃 라우터의 주소 저장

9 2.RIP (Routing Information Protocol) (3)
라우터의 초기 라우팅 테이블은 자신의 이웃 정보로 구성

10 2.RIP (Routing Information Protocol) (4)
각 라우터는 자신의 라우팅 테이블을 모든 이웃 라우터와 교환 라우팅 테이블 교환 과정을 반복하여 각 라우터는 전체 네트워크의 정보를 얻음 라우터B의 최종 라우팅 테이블

11 2.RIP (Routing Information Protocol) (5)
라우팅 테이블 갱신 이웃 라우터로 부터 라우팅 테이블을 수신하면 라우터는 자신의 것과 비교하여 라우팅 테이블을 갱신

12 2.RIP (Routing Information Protocol) (6)
라우팅 테이블 동작 예 (B가 A로부터 라우팅 테이블 수신) 라우터 B 에서 라우팅 테이블 갱신

13 2.RIP (Routing Information Protocol) (7)
네트워크에서 쓰이는 간단한 라우팅 프로토콜 거리 벡터 값은 홉 카운트 라우터 방송 -> 데이타그램 패킷 최대 홉 : 16 제한 180 초 이상 초과시 이상징후로 판단 RIP 규칙 라우팅 정보는 단지 180초 동안만 유효 현재의 Hop수 보다 낮은 Hop수의 라우팅 정보 수신시 효율적인 경로를 선택

14 2.RIP (Routing Information Protocol) (8)
메시지 요청과 응답의 2가지 종류의 패킷 메시지 요청 패킷 라우터가 처음 부팅되었을 때 전송 특정 목적지 정보가 타임 아웃 되었을 때 전송 응답 패킷 매 30초마다 주기적으로 이웃 라우터에게 전송 트리거 갱신시 자신의 라우팅 테이블에 변화가 생겼을 때 전송 타임아웃 시간동안 라우팅 정보의 수신이 이루어지지 않을 때 의미없는 목적지로 간주 일정시간후 라우팅 테이블에서 삭제

15 2.RIP (Routing Information Protocol) (9)
메트릭은 1에서 15의 거리값을 나타내고 16은 무한태를 나타냄 RIP 패킷이 15홉보다 긴 경로를 가지 지 않게 함 무한 루프 방지

16 2.RIP (Routing Information Protocol) (10)
문제점 홉수가 15이상인 네트워크에 사용할 수 없으므로 네트워크 규모의 제한 메트릭을 홉수로 제한함에 따라 항상 가장 빠른 경로를 선택할 수 없음 라우팅 정보가 30초 마다 교환되므로 장애시 전체 네트워크의 복구시 많은 시간이 소요 특정 경로에 루프 가능성 해결방안 트리거 갱신 : 변경시 즉시 통보함으로써 복구 시간을 줄임 Hold down : 무한대인 경로에 대해서 전체 네트워크의 경로가 새로 갱신될 때까지 일정 시간 동안 기다림 Split horizon : 라우팅 정보를 전달해준 인터페이스로 재 전송하지 않음으로 루프 방지 Route posion : 회선이 고장난 경우 즉시 홉을 16으로 지정하여 전체 네트워크에 전송

17 2.RIP (Routing Information Protocol) (12)
홉(Hop) : 거리값 (ex) 홉2=> 목적지까지의 네트워크2개를 경유 패킷 형태 : 요청과 응답 요청패킷 : 전체 목적지 정보 혹은 특정 부분의 목적지 정보들을 요청 응답패킷 : 실제 목적지에 대한 정보 패킷( 3가지 중 하나) 주기적 전송 . 상대의 요청 패킷에 의한 응답 목적지 정보의 변화 　 응답 패킷을 수신한 경우, 라우터는 수신된 정보를 통해 최적 경로의 결정하게 되는데 수신된 목적지의 거리값 (+ 수신 네트워크의 거리값(1)) 과 현재 유지하고 있는 거리값을 비교하여 작은 것을 목적지에 대한 경로로 유지하게 된다.

18 2.RIP (Routing Information Protocol) (13)
향후 전망 RIP 버전2가 개발 실제로 잘 쓰이지는 않는 상황 OSPF같은 링크 상태 알고리즘이 일반적인 추세이다

19 3. OSPF (Open Shortest Path First) (1)
등장 배경 1980 중반 RIP의 한계 SPF(Shortest Path First) 알고리즘에 기반 IP 네트워크용 라우팅 알고리즘 개발 => OSPF가 탄생 OSPF : 모든 사양이 개방(Open) 대규모의 네트워크에서 사용할 수 있도록 한 프로토콜

20 3. OSPF (Open Shortest Path First) (2)
개요 링크 상태 알고리즘 사용 네트워크에 변화시 플러딩과정을 통해 갱신 링크에 대한 비용 지정 1980년대 중반 IETF(Internet Engineering Task Force)가 개발 모든 라우터는 동일한 토폴로지 데이터베이스 유지, 자신을 중심으로 최적의 경로를 계산 수렴시간을 감소 라우팅 트래픽 양 감소

21 3. OSPF (Open Shortest Path First) (3)
메시지 동일한 헤더 < OSPF 헤더 포맷 >

22 3. OSPF (Open Shortest Path First) (4)
Area 필드 OSPF는 한 도메인에서 계층적으로 구성이 가능하므로 필요 < 계층 구조의 AS >

23 3. OSPF (Open Shortest Path First) (5)
동작 플러딩을 위해 D class IP 주소를 사용 멀티캐스팅 수행 “hello”메시지 이웃라우터에게 자신이 살아있다는 것을 알리기 위해 사용 일정기간동안 “hello”메시지가 없을 때에는 이상상태가 발생했음을 감지하고 그 사실을 플러딩 수렴 속도 (Convergence) 네트워크 토폴로지가 변경되었을 때 신속하게 적응 장애를 즉시 감지 변경된 정보를 LSP에 담아 모든 OSPF 라우터에 플러딩 LSP 수신시 즉시 데이터베이스 갱신 최단 경로 알고리즘을 이용하여 경로를 재 계산 영향을 주는 요인 장애 감지 인터페이스 상태변화 Dead Timer시간내에 이웃라우터로부터 hello 패킷이 수신되지 않을 때 경로 계산 네트워크의 크기, 데이터베이스 내의 경로 개수에 따라 달라짐

24 3. OSPF (Open Shortest Path First) (6)
링크 상태 알고리즘 (Link State algorithm) 개요 라우터는 이웃에 대한 연결정보를 다른 모든 라우터에 전달 네트워크 전체 토폴로지에 대한 정보를 얻고 이를 바탕으로 최적의 경로 선택 플러딩 (flooding) 링크 상태 프로토콜을 사용하고 있는 모든 라우터에 링크 상태 정보를 전송 과정 링크 상태 패킷(LSP: Link State Packet)을 사용하여 정보 전송 < LSP 구성 >

25 3. OSPF (Open Shortest Path First) (7)
LSP 플러딩 과정 링크 상태 데이터베이스 (Link State Database) 모든 라우터는 동일한 네트워크 맵정보 보유하며 최적의 경로를 계산 공통의 데이터 베이스 유지

26 3. OSPF (Open Shortest Path First) (8)
링크 상태 데이터베이스 예 각 노드는 플러딩 과정을 통하여 네트워크 토폴로지 정보를 링크 상태  데이터베이스에 넣어 공통의 데이터 베이스를 유지

27 3. OSPF (Open Shortest Path First) (9)
최단 거리 트리 – Dijkstra 알고리즘 라우터는 자신을 루트로 하여 목적지 까지의 최단 거리 트리 구성 Dijstra 알고리즘 적용 모델

28 3. OSPF (Open Shortest Path First) (10)
Dijstra알고리즘 라우터와 네트워크를 노드로, 그 연결을 아크로 한 그래프를 이용하여 네트워크에 있는 노드간의 최단경로를 계산 하나의 노드를 루트로 하여 아크에 연결된 노드를 임시노드에 두고 최소 비용을 가지는 노드를 찾는 검사를 수행하여 최단거리 트리의 영구노드를 결정 알고리즘 절차 트리의 루트가 될 하나의 노드를 정한다. 1의 노드를 영구노드로 결정한다. 가장 최근에 영구노드가 된 노드의 이웃노드를 검사한다. 각 노드에 누적합의 비용을 계산하고 임시 노드로 만든다 임시 노드들에 대해서 가장 비용이 적은 노드를 찾아 영구 노드로 만든다. 하나이상의 경로가 존재 할 때는 누적합이 가장 작은 경로를 선택한다. 3에서 5의 과정을 모든 노드가 영구노드가 될 때까지 반복한다.

29 3. OSPF (Open Shortest Path First) (11)

30 3. OSPF (Open Shortest Path First) (12)

31 3. OSPF (Open Shortest Path First) (13)

32 3. OSPF (Open Shortest Path First) (14)
목적지 네트워크 비 용 다음 홉 N1 2 - N6 5 N5 3 N2 9 B N3 6 c N4 e

33 3. OSPF (Open Shortest Path First) (14)
라우팅 알고리즘을 적용하기 위한 계위 소유 백 본 Area 1 Area 2 Area 3 라우터 1 라우터 4 라우터 5 라우터 8 라우터 7 라우터 6 라우터 2 라우터 3 백본 라우터(Backbone Router) : 라우터 1, 라우터 2, 라우터 3, 라우터 4 Area 경계라우터(Area Border Router) : 라우터 1, 라우터 2, 라우터 3 내부 라우터(Internal Router) : 라우터 4, 라우터 5, 라우터 6, 라우터 7, 라우터 8 AS 경계라우터 (AS Border Router) : 라우터 3 다른 라우팅 도메인 < 계위에 따른 전형적인 망 구조 >

34 3. OSPF (Open Shortest Path First) (15)
네트워크 1 지명 라우터 라우터 A     네트워크 2 라우터 B 라우터 C 라우터 D 라우터 E  라우터 A가 지명 라우터 B에 Link-state 송출 (Designated Router용 멀티캐스트)  라우터 B는 네트워크 2상의 인접 관계를 가지는 라우터C에 멀티캐스트 송출  를 수신한 라우터 C는 네트워크 1상의 지명 라우터D를 향해서 Link-state 송출  라우터 D는 네트워크 1상의 인접관계를 가지는 라우터E에 멀티캐스트로 송출 에서 의 흐름으로 A가 송출한 Link-state가 Area내에 전파된다. 또한 수신한 라우터는 반드시 수신 확인(ACK)을 보낸다.

35 3. OSPF (Open Shortest Path First) (17)
기존의 RIP망을 OSPF로 바꾸는 작업 활발이 진행 다른 어떤 라우팅 프로토콜보다도 주도적 역할을 수행할 것으로 예상 => 라우터의 중요성 및 역할이 많이 줄어들고 있는 상황 but 외부와 연결하기 위해서는 라우터가 필요

36 < OSPF와 RIP 라우팅 테이블 구성 과정의 차이점 >
Link-State 라우터 라우팅 테이블 데이터 베이스 Link state 1) OSPF 2) RIP

37 참고 자료 참고 문헌 참고 사이트 고속내트워크, 인터비젼, WILLIAM STALLINGS < 박영근 역>
컴퓨터 네트워크, 생능 출판사< 정진욱 ,김현철 , 조강홍 공저 > Network Bible 3rd Ed. , 영진.com < 임강진 , 신재호 , 권병희 공저 > 참고 사이트 RIP