Routing Protocols (RIP, OSPF, BGP)

Presentation on theme: "Routing Protocols (RIP, OSPF, BGP)"— Presentation transcript:

1 Routing Protocols (RIP, OSPF, BGP)
Chapter 13 Routing Protocols (RIP, OSPF, BGP)

2 CONTENTS INTERIOR AND EXTERIOR ROUTING RIP OSPF BGP

3 라우팅 프로토콜 인터넷 : 라우터에 의해 연결된 네트워크의 조합
라우터 : 네트워크로부터 패킷 수신 다른 네트워크로 전달(최적 경로) 메트릭(metric) : 네트워크를 거쳐 지나갈 때 할당되는 비용 라우터는 가장 적은 메트릭을 갖는 경로 선택

4 라우팅 프로토콜 각 네트워크에 할당된 메트릭은 프로토콜의 종류에 따라 서로 다름
RIP(Routing Information Protocol) : 각 네트워크를 동일하게 취급(홉 갯수) OSPF(Open Shortest Path First) : 요청된 서비스에 따라 비용을 관리자가 할당 가능 BGP(Border Gateway Protocol) : 관리자가 정하는 정책에 따라 경로 결정

5 13.1 INTERIOR AND EXTERIOR ROUTING

6 13.1 내부와 외부 라우팅 자율시스템(AS:Autonomous System) 내부 라우팅 : 자율 시스템 내 라우팅
단일 관리 기관내의 라우터와 네트워크 그룹 내부 라우팅 : 자율 시스템 내 라우팅 외부 라우팅 : 자율 시스템간 라우팅

7 13.1 내부와 외부 라우팅 많이 사용되고 있는 라우팅 프로토콜

8 13.1 내부와 외부 라우팅 자율 시스템

9 13.2 RIP: Routing Information Protocol

10 13.2 RIP 자율 시스템 내에서 사용하는 내부 라우팅 프로토콜
거리 벡터 라우팅(Distance Vector Routing)에 기반 하는 프로토콜 라우팅 테이블을 만드는데 Bellman-Ford 알고리즘 사용

11 13.2 RIP 거리벡터 라우팅 전체 자율 시스템에 대한 정보의 공유 이웃하는 라우터와 공유 주기적인 공유 : 30초 간격

12 Destination Hop Count Next Hop
13.2 RIP 라우팅 테이블 Destination Hop Count Next Hop

13 13.2 RIP RIP갱신 알고리즘 Return. Receive : a response RIP Message
Add one hop to the hop count for each advertised destination. Repeat the following steps for each advertised destination: If(destination not in the routing information to the table. Add the advertised information to the table. Else If(next-hop field is the same) Replace entry in the table with the advertised one. If(advertised hop count smaller than one in the table) Replace entry in the routing table Return.

14 13.2 RIP 라우팅 테이블 갱신 예

15 13.2 RIP 라우팅 테이블 초기화

16 13.2 RIP 이전 그림의 마지막 라우팅 테이블

17 13.2 RIP RIP메시지 형식

18 13.2 RIP RIP 메시지 형식 명령(command) : 메시지 종류(요청 –1, 응답 –2)
버전(version) : 버전 1 계열(family) : 사용된 프로토콜 계열(TCP/IP : 2) 주소(address) : 목적지 네트워크 주소(14바이트) 거리(distance) : 목적지 네트워크까지 홉 계수

19 13.2 RIP(계속) 요청 메시지 새로운 요청이 생기거나 시간이 만료된 라우터에 의해 전송

20 13.2 RIP Example 1 What is the periodic response sent by router R1 in Figure 13.8 (next slide)? Assume R1 knows about the whole autonomous system.

21 13.2 RIP 예제 1

22 13.2 RIP Solution R1 can advertise three networks , , and The periodic response (update packet) is shown in Figure 13.9 (next slide).

23 13.2 RIP 예제 1에 대한 해결책

24 13.2 RIP RIP 타이머

25 13.2 RIP RIP 메시지 타이머 주기적 타이머(periodic timer) : 정규 갱신 메시지 통보를 제어(30초 간격) 만료 타이머(expiration timer) : 경로의 유효성 관리(180초) 폐 경로 수집 타이머(garbage collection) : 무효화된 경로 관리(120초)

26 13.2 RIP Example 2 A routing table has 20 entries. It does not receive information about five routes for 200 seconds. How many timers are running at this time?

27 13.2 RIP Solution The timers are listed below: Periodic timer: 1
Expiration timer: = 15 Garbage collection timer: 5

28 13.2 RIP 저속 수렴(Slow convergence) 인터넷 일부에서 발생하는 변화가 매우 느리게 다른 부분에 알려짐

29 13.2 RIP 홉 카운트(Hop count) 홉 수를 15로 제한

30 13.2 RIP 불안정(Instability)

31 13.2 RIP 불안정을 해결하기위한 대책 수평분할(Split horizon)
트리거 갱신(triggered update) : 네트워크에 변화가 있으면 절차에 따라 새로운 테이블 전송 수평 분할(split horizons):갱신 메시지 전송을 선택적으로 이용 수평분할(Split horizon)

32 13.2 RIP poison reverse : 수평 분할의 변형

33 13.2 RIP RIP 버전 2 형식

34 13.2 RIP RIP 버전 2의 새로운 필드 경로 태그(route tag) : 자율 시스템 번호 정보 전달
서브넷 마스크(subnet mask) : 서브넷 마스크 전달 다음 홉 주소(next hop address) : 다음 홉의 주소

35 RIP version 2 supports CIDR.

36 13.2 RIP 인증 메시지 보호를 위해 사용

37 13.2 RIP 멀티캐스팅 RIP 버전 2 : 네트워크에 있는 라우터만 RIP 메시지를 수신하는 멀티캐스트 주소 사용 캡슐화 UDP 사용자 데이터그램에 캡슐화 잘 알려진 포트 520번 이용 UDP서비스 사용

38 RIP uses the services of UDP on well-known port 520.

39 13.3 OSPF: Open Shortest Path First

40 13.3 OSPF Open Shortest Path First 가장 많이 사용되는 내부 라우팅 프로토콜
자율 시스템 경계 라우터(autonomous system boundary router)라는 특별한 라우터가 다른 자율 시스템에 정보 배포 라우팅을 효율적으로 수행하기 위해 자율시스템을 여러 지역으로 나눔

41 13.3 OSPF 지역(area) 자율시스템에 포함되는 호스트, 라우터, 네트워크의 모음
지역 경계 라우터(area boarder router) : 지역에 대한 경로 정보를 정리하여 다른 지역에 전송 백본 라우터 (backbone router) : 가장 중심이 되는 backbone지역에 있는 라우터 지역 식별자 : backbone – 0, 지역–1, 2, .., n

42 13.3 OSPF 메트릭(metric) 관리자가 각 경로에 대한 비용 할당 서비스 종류에 따라 결정 : 최소지연, 최대 성능

43 13.3 OSPF 자율 시스템 내 지역

44 13.3 OSPF 링크 상태 라우팅(link state routing) 이웃에 대한 정보 공유
다른 모든 라우터와 정보 공유 : 플러딩(flooding) 변화가 있는 경우에 공유

45 13.3 OSPF(계속) 링크의 유형 OSPF 용어에서 네트워크 지칭 링크 유형

46 13.3 OSPF(계속) 점-대-점(Point-to-Point) 링크 라우터간에 다른 호스트나 라우터 없이 직접 연결

47 13.3 OSPF(계속) 경유(transient) 링크 몇 개의 라우터가 연결되어 있는 네트워크

48 13.3 OSPF 스터브( stub)링크 가상(virtual) 링크 하나의 라우터에만 연결된 네트워크
라우터간 연결이 끊어지면 돌아서가는 긴 경로를 사용

49 13.3 OSPF 인터넷의 예

50 13.3 OSPF 인터넷의 그림 표현

51 13.3 OSPF 링크 상태 광고(LSA : link state advertisement) 이웃에 대한 정보 교환 LSA 유형

52 13.3 OSPF 라우터 링크 실제 라우터의 링크들을 정의

53 13.3 OSPF 네트워크 링크 네트워크의 링크들을 정의

54 13.3 OSPF 네트워크 요약 링크 지역내의 라우터 링크와 네트워크 링크에 대한 정보를 지역내에 보급

55 13.3 OSPF 자율시스템 경계 라우터의 요약 링크 지역 경계 라우터가 자율시스템 내에 있는 정보를 지역에 전달

56 13.3 OSPF 외부 링크 자율시스템 외부 네트워크에 대한 정보는 외부링크 광고를 통하여 열수 있다.

57 13.3 OSPF Example 3 In Figure (next slide), which router(s) sends out router link LSAs?

58 13.3 OSPF 예제 3과 예제 4

59 13.3 OSPF Solution All routers advertise router link LSAs.
R1 has two links, Net1 and Net2. R2 has one link, Net1 in this AS. R3 has two links, Net2 and Net3.

60 In Figure 13.31, which router(s) sends out the network link LSAs?
13.3 OSPF Example 4 In Figure 13.31, which router(s) sends out the network link LSAs?

61 13.3 OSPF Solution All three network must advertise network links:
Advertisement for Net1 is done by R1 because it is the only router and therefore the designated router. Advertisement for Net2 can be done by either R1, R2, or R3, depending on which one is chosen as the designated router. Advertisement for Net3 is done by R3 because it is the only router and therefore the designated router.

62 In OSPF, all routers have the same link state database.

63 13.3 OSPF 링크상태 데이터 베이스 다른 라우터로부터 라우터 링크와 네트워크 링크 LAS를 수신하여 링크상태 데이터베이스 작성 인터넷 접속 형태를 표를 이용하여 표현한 방식 각 라우터와 이웃간의 관계, 메트릭 정보

64 13.3 OSPF 딕스트라 알고리즘(Dijkstra Algorithm) 라우팅 테이블 계산 알고리즘
Start with the local node(router) : the root of the tree. Assign a cost of 0 to this node and make it the first permanent node. Examine each neighbor node of the node that was the last permanent node. Assign a cumulative cost to each node and make it tentative. Among the list of tentative nodes Find the node with the smallest cumulative cost and make it permanent. If a node can be reached from more than one direction Select the direction with the shortest cumulative cost. Repeat steps 3 to 5 until every node becomes permanent.

65 13.3 OSPF(계속) 최단 경로 계산

66 13.3 OSPF 최단 경로 계산

67 13.3 OSPF 최단 경로 계산

68 13.3 OSPF 라우팅 테이블 지역내의 각 네트워크에 도달하는 비율 라우터 A에 대한 링크 상태 라우팅 테이블
Network Cost Next Router N N2 7 C N D N B N D

69 13.3 OSPF 패킷의 종류

70 13.3 OSPF OSPF 패킷 헤더

71 13.3 OSPF 패킷 형식 버전(version) : 8비트, OSPF 프로토콜 버전, 현재 값 : 2
유형(type) : 패킷 유형(1~5) 메시지 길이(message length) : 전체 메시지 길이 발신지 라우터 IP 주소(source router IP address) : 32bit 지역 식별자(area identification) : 라우팅이 일어나는 지역 검사합(checksum) : 오류 정정 인증 종류(authentication type) : 지역에서 사용되는 인증 방법 인증(authentication) : 인증 데이터의 실제 값

72 13.3 OSPF Hello 패킷 이웃 관계를 생성하고 이웃의 도달 가능성 검사 링크 상태 라우팅의 첫 번째 과정

73 13.3 OSPF Hello 패킷 네트워크 마스크(network mask) : 32비트 – hello 메시지가 전송 되어지는 네트워크 마스크 Hello 간격(interval) : 메시지의 간격(초 단위) E 플래그(flag) : 설정된 경우 지역이 스터브 지역 T 플래그(flag) : 설정된 경우 라우터는 다중 메트릭 지원 우선순위(priority) : 라우터의 우선 순위 Dead 간격(interval) : 이웃 라우터가 다운되었다고 가정하기 전까지 시간(초 단위) 지정 라우터 IP 주소(designated router IP address): 메시지가 전송되는 네트워크의 지정 라우터의 IP 주소 백업 지정 라우터 IP 주소(backup designated router IP address) 이웃 IP 주소(neighbor IP address) : hello 메시지를 수신한 모든 이웃들의 현재 목록

74 13.3 OSPF 데이터베이스 기술 패킷 라우터가 처음으로 또는 장애후에 시스템에 연결되면 전체 링크 상태 데이터베이스 필요
자신의 이웃에게 hello 메시지 전송 첫 번째 인사이면 데이터베이스 기술 패킷 전송 그런 다음 링크 상태 요청 패킷 전송

75 13.3 OSPF 데이터베이스 기술 패킷

76 13.3 OSPF 데이터베이스 기술 패킷 E 플래그 : 광고 라우터가 자율 시스템 경계 라우터이면 1
B 플래그 : 광고 라우터가 지역 경계 라우터이면 1 I 플래그 : 첫 번째 메시지 일 때 1 M 플래그 : 마지막 메시지가 아닐 경우에 1 M/S (Mster/Slave) 플래그 : 패킷의 시작점 메시지 순서 번호(message sequence number) 링크 상태 헤더(link state header)

77 13.3 OSPF 링크 상태 요청 패킷 특정 경로나 경로들에 대한 정보를 필요로 하는 라우터가 보내는 패킷
링크 상태 갱신 패킷으로 응답

78 13.3 OSPF 링크 상태 갱신 패킷 각 라우터가 자신의 링크 상태를 광고할 때 사용 서로 다른 LSA 포함 가능

79 13.3 OSPF LSA 헤더

80 13.3 OSPF LSA 헤더 링크 상태 기간(Link State Age) : 메시지가 만들어지고 난 경과 시간(초단위)
E 플래그(flag) : 스터브 지역일 경우 1 T 플래그(flag) : 라우터가 복수개의 서비스 종류를 처리할 수 있다면 1 링크상태 식별자(link state ID) : 링크의 종류에 따라 다름 광고 라우터(advertise router) : 광고한 라우터의 IP 주소 링크 상태 순서번호(Linkstate Sequence Number) : 갱신 메시지에 할당된 순서 번호 링크 상태 검사합(Link State Checksum) : 오류검사 길이(Length) : 전체 패킷의 바이트 단위 길이

81 13.3 OSPF 라우터 링크 LSA

82 13.3 OSPF 라우터 광고 패킷 형식 링크 식별자(link ID) : 링크의 종류(표 13.3 참조)
링크 데이터(link data) : 추가 정보(표 13.3) 링크 종류(link type) : 네트워크 종류에 따른 링크 유형(표 13.3 참조) 서비스 종류(type of service: TOS)의 갯수 : 각 링크에 알려진 서비스 종류 TOS 0에 대한 메트릭(metric for TOS 0) TOS(type of Service) : 서비스 유형 메트릭(metric) : 해당 TOS에 대한 메트릭

83 13.3 OSPF 링크 종류, 링크 식별자와 링크 데이터 Link Type Link Identification
Link Data Type 1: Point-to-Point connection to another router Address of neighbor-router Interface number Type 2: Connection to any-to-any network Address of designated router Router address Type 3: Connection to stubnetwork Network address Network mask Type 4: Virtual link

84 Give the router link LSA sent by router 10.24.7.9 in Figure 13.41.
13.3 OSPF Example 5 Give the router link LSA sent by router in Figure

85 13.3 OSPF 예제 5

86 13.3 OSPF Solution This router has three links: two of type 1 (point-to-point) and one of type 3 (stub network). Figure shows the router link LSA.

87 13.3 OSPF 예제 5의 해결책

88 13.3 OSPF 네트워크 링크 LSA 네트워크에 연결된 링크를 알리는데 사용 네트워크 마스크
접속(attached) 라우터 : 반복 필드로 접속된 모든 라우터의 IP 주소

89 Give the network link LSA in Figure 13.44.
13.3 OSPF Example 6 Give the network link LSA in Figure

90 13.3 OSPF 예제 6

91 13.3 OSPF Solution The network, for which the network link advertises, has three routers attached. The LSA shows the mask and the router addresses. See Figure Note that only one of the routers, the designated router, advertises the network link.

92 13.3 OSPF 예제 6의 해결책

93 13.3 OSPF 네트워크에 대한 요약 링크 LSA 지역 경계 라우터가 지역 밖에 있는 다른 네트워크의 존재를 알리는데 사용
네트워크 마스크, 서비스 종류, 메트릭으로 구성 각 광고는 단일 네트워크면 알림 네트워크 주소는 링크 상태 광고의 헤더에 들어있는 라우터의 IP 주소와 마스크 정보를 통하여 얻게됨

94 13.3 OSPF 네트워크 LSA의 요약 링크

95 13.3 OSPF 자율 시스템 경계 LSA의 요약 링크 자율 시스템 경계 라우터로 가는 경로를 알리는데 사용

96 13.3 OSPF 외부 링크 LSA 자율 시스템 외부에 있는 모든 네트워크로 알리는데 사용

97 13.3 OSPF 링크 상태 확인응답 패킷 링크 상태 갱신 패킷에 대한 확인응답

98 OSPF packets are encapsulated in IP datagrams.

99 13.4 BGP: Border Gateway Protocol

100 13.4 BGP Border Gateway Protocol 자율 시스템간 라우팅 프로토콜
경로 벡터 라우팅(path vector routing) 방법 적용 경로 벡터 라우팅 테이블(표 13.4로 대체 374) Network Next Router Path N01 R01 AS14, AS23, AS67 N02 R05 AS22, AS67, AS05, AS89 N03 R06 AS67, AS89, AS09, AS34 N04 R12 AS62, AS02, AS09

101 13.4 BGP 경로 벡터 메시지 자신의 자율시스템 네트워크에서 이웃하는 자율 경계 라우터까지 연결이 가능한지 광고
경로 벡터 패킷

102 13.4 BGP 루프 방지 라우터가 메시지 수신시 목적지까지의 경로 목록에 해당 자율시스템이 있는지 확인 정책 라우팅 메시지 수신시에 경로상에 자율시스템 중 하나가 정책에 위반되면 해당 경로와 목적지를 무시 경로 속성 각 속성은 경로에 대한 정보 제공

103 13.4 BGP 패킷 종류

104 BGP supports classless addressing and CIDR.

105 13.4 BGP 패킷 형식 모든 패킷은 동일한 공통 헤더를 가짐 표시기(maker) : 인증을 위해 예약
길이(length) : 전체 메시지 길이 유형(type) : 패킷 유형

106 13.4 BGP Open 메시지 동작중인 라우터가 이웃 관계를 생성하기 위해 이웃들과 TCP 연결을 하고 open 메시지 전송

107 13.4 BGP Open 메시지 형식 버전(version) : BGP 버전(현재는 4)
자신의 자율 시스템(My autonomous system) : 자율시스템 번호 유지 시간(hold time) : 상대방으로부터 메시지 수신 후 경과될 수 있는 시간 BGP 식별자(identifier) : 메시지를 전송한 라우터의 IP 주소 선택 매개 변수 길이(option length) : 전체 옵션의 길이 선택 매개 변수(option) : 옵션 유무

108 13.4 BGP Update 메시지 이전에 광고된 목적지를 취소하거나 새로운 목적지 경로를 알리는데 사용

109 13.4 BGP Update 메시지 필드 불가능(unfeasible) 경로 길이 : 다음 필드의 길이
취소된(withdrawn) 경로 : 전에 광고된 목록중에서 삭제되어야 하는 모든 경로 경로 속성 길이 – 다음 필드의 길이 경로 속성 – 메시지를 통해 광고되는 도달 가능한 네트워크까지의 경로에 대한 속성 네트워크 계층 도달 가능 정보 – 실제 광고되는 네트워크

110 13.4 BGP Keepalive 메시지 상대방에게 자신이 동작하고 있음을 알리는 메시지

111 13.4 BGP Notification 메시지 오류 상황 감지 또는 연결을 닫기 원할 때

112 13.4 BGP 오류 코드 Error Code Error Code Description
Error Subcode Description 1 Message message error Three different subcodes are define for this type of error: synchroniation problem(1), bad message length(2), and bad message type(3) 2 Open message error Six different subcodes are defined for this type of error: unsupported version number(1), bad peer AS(2), bad BGP identifier(3), unsupported optional parameter(4), authentication famiure(5), and unacceptable hold time(6) 3 Update message error Eleven different subcodes are defined for this type of error: malformed attribute list(1), unrecognized well-known attribute(2), missing well-known attribute(3), attribute flag error(4), attribute length error(5), invalid oriin attribute(8), optional attribute error(9), invalid network field(10), malformed ASPATH(11) 4 Hold timer expired No subcode defined. 5 Finite state machine This defines the procedural error. No subcode defined. 6 Cease No subcode defined

113 BGP uses the services of TCP on port 179.