[컴퓨터 네트워크] 라우팅 알고리즘 | RIP와 OSPF | 임시노드, 영구노드 작성

시험 날짜는 다가오는데... 진도는 계속 나간다ㅎ... 갈수록 어려워짐 

오늘은 라우팅 알고리즘에 대해서 배웠고 이를 정리해두려한다.

 

* 제 3계층(네트워크 계층)

1. Routing Control

:: 경로만 설정함. (경로 관리)

2. Switching

:: 주어진 경로에 따라 정보에 처리. 정보만 처리함. (전송관리)

→ 속도, 메시지 크기, Protocol을 맞춰줌.

3. Traffic

:: 주어진 전송의 혼잡(과부화)

3-1. 전송 단위

3-2. 속도

3-3. Protocol

 

:: 여기서 스위칭과 트래픽은 서로 연관이 있지만 라우팅 제어는 이들과 조금 거리가 있다고 할 수 있다.

 

*Routing

# Metric

:: Routing 의 파라미터

1. hop 수

2. cost

3. delay

4. throughput

5. attribute

 

여기서 1번부터 4번까지는 모두 내부 요소들이지만 5번은 외부 요소이다. (5번은 조금 복잡해서 나중에 공부한다!)

내부인지 외부인지 하는 성질로 이들을 분류하는 문제가 기사 시험에 나오기도 한다. ( Q. 다음 중 그 성질이 다른 것은? 1. hop수 2. cost 이런 식으로!)

 

#종류

1. 고정 경로와 우회 경로

:: 우리 나라 우선 순위 첫번째. 고정으로 가다가 문제가 생기면 우회 경로를 이용한다.

– Static 경로(정적 경로) : RT 테이블이 고정되어 있다.

– Dynamic 경로(동적 경로) : RT 테이블이 고정되어있지 않다.

 

2. Flooding

: 빨리 빨리 보내기 위해서 빨리 응답하는 애한테 우선권을 주어서 보내는 방식. 접속된 노드에게 모두 보낸다. 무조건 Forward만 한다. (여기서 Forward는 왼쪽에서 오른쪽으로 가는 것과 같이 정해진 방향으로 가야지만 Forward이고 이에 반대해서 가는 것은 Backward라고 한다.)

 

*Routing의 분류

-같은 망, 같은 지역 : RIP, OSRF
:: 고정을 사용하다가 이를 변경하여 결국 가변이 되는 형식으로 사용한다. 여기서 가변하는 방식은 접근하기 가까운 것으로 Table을 바꾼다.

-외부 : BGP(여기서 B는 Border이다.)

 

#RT(Routing Table) 가변?

# 단계

초기화

↓

공유

↓

갱신

:: 초기화 : 고정된 테이블의 값. 이게 초기값이다.

:: 공유 : Metric

:: 갱신 : 값이 변한다. ∞ (서로 이어져 있지 않은 노드들간의 Cost 혹은 Delay를 표현한 것) 이 없어지도록 변경되어야 한다.

 

위의 세가지 단계가 아주 중요하다.

 

– reachable : 도착 가능성.

– unreachable : 도착 불가능. 이게 ∞로 표현됨.

 

# RIP

:: 출발지에서 도착지로 가는 길 중 가장 저렴한 걸 찾고 ∞가 있는 테이블을 갱신해주는 방식으로 진행된다.

예를 들어 다음 그림과 같이 연결된 노드가 있다고 해보자.

[그림 11.1] 연결 노드 예시

위 그림에서 A는 B와 C,D와는 연결되어 있지만 E와는 연결되어 있지 않다. 이런 경우 A와 E가 unreachable 하다고 한다.

A에서 출발하여 E까지 가는 경로를 찾는다고 할 때, 현재 그림에 주어진 Cost를 이용해 각 Node의 테이블을 만들 수 있는데 이를 초기값이라고 한다.

테이블을 만들고 보면 A에서 A로 가는 것은 0, A에서 연결된 다른 지점으로 가는 것은 선위에 적힌 숫자, A에서 E로 가는 것은 ∞로 표현할 수 있다. 이 ∞를 제거하기 위하여, 두 번째 단계인 공유를 한다.

공유를 하는 방법은 시작점에서 ∞가 아닌 이동할 수 있는 지점들의 Cost를 비교해 가장 저렴한 비용이 드는 지점을 선택해 이 지점과 출발 지점을 하나로 묶는 식으로 수행한다. 즉, A에서는 B와 C,D 중 가격이 2인 C가 가장 저렴하므로 A와 C를 공유한다.

공유한다는 의미는 A와 C를 하나로 묶어 이를 하나의 지역으로 보겠다는 의미이다. A와 C를 공유했으므로 A는 C이고 C는 A이다. 이를 편의상 A’이라고 하자.
(A에서 C로 간 것은 이미 결정된 경로이고,  A와 C를 하나로 보기 때문에 C에서 A로 돌아가 A와 연결된 지점에 가는 것은 Backward가 아닌 것이 된다. 따라서 C에서 한 번에 D에 가는 것도 우리가 보기에는 A-C-A-D이지만 C에서 A로 돌아간 것은 A와 C가 하나의 지역이라고 생각하기 때문에 되돌아간 것이라고 보지 않고 그냥 A’에서 한 번  갔다고 생각하는 것이다.)

따라서 예를 들어 A에서 B로 간다고 할 때, 한 번에 갈 수 있었던 것도 C를 거쳐 가야한다는 것을 의미한다. 그렇기 때문에 기존의 A 테이블의 값들은 모두 2가 증가된 값으로 변경되어야 한다.

그럼 이제 A’이라는 새로운 지점이 생성되었으므로 A’의 테이블을 만들어주어야 한다. A’의 테이블은 A’의 요소라고 볼 수 있는 A와 C의 테이블의 값들을 비교하여 더 저렴한 것들을 뽑아 넣으면 된다.

그 방법은 다음 그림과 같다.

[그림 11.2] 공유와 갱신

이렇게 하여 A 테이블의 ∞은 모두 사라진 상태가 되었다.
(C까지는 이미 왔기 때문에 0!)
A’을 만드는 과정에서 우리는 초기화, 공유, 갱신 과정을 모두 알아보았다. (나중에 혼란이 없게 하기 위해서 A와 C를 공유했다는 의미로 A와 C를 동그란 원으로 묶어두는 것도 하나의 방법이다.) 이제 새로 갱신된 A’ 테이블을 이용해 E로 다시 이동해보자!

A’ 테이블을 보면 A로 다시 되돌아가는 방법을 제외하고는 최소 비용이 B와 E가 모두 4로 일치한다. 여기서 우리의 목적지가 E이므로 E를 선택한다.
(B를 선택할 수도 있지만 B를 선택하는 순간 hop수가 증가하므로 B는 선택하지 않는다.)

A’과 E의 테이블을 보면 모두 ∞가 존재하므로 이를 없애주기 위해서 공유 과정을 다시 수행한다. A’을 만들 때와 마찬가지로 C에서 E로 이미 갔다는 의미로 A’ 테이블의 모든 Cost에 4를 더해주고, 연산을 마친 C 테이블과 E 테이블을 비교해서 가장 저렴한 것들을 모아 E’ 테이블을 만들어준다.

[그림 11.3] 공유와 갱신2

이렇게 해서 이동한 경로들의 테이블에서 ∞을 모두 제거하고 출발지에서 도착지까지 최소 hop수와 최소 비용으로 이동하는 경로를 모두 정했다. 이렇게 테이블을 갱신하는 방법이 RIP이다.

 

# OSPF

– OSPF의 단점 : unreachable 을 판별할 수 없다.

다음과 같이 노드가 연결이 되어있다고 하자.

[그림 11.4] 링크 노드 예시

위의 RIP 예제와 연결 상태는 동일하지만 표현 형태가 위와 같이 다르다. 위와 같이 서로 뭉쳐져있다고 해서 상태가 링크되어있다고 한다.

OSPF는 A에서 E로 이동하는 과정이 다음 그림과 같다.

[그림 11.5] OSPF 길찾기 과정

자세하게 그림을 분석해보자.

그림에서 영구 리스트는 이미 결정된 경로들이고 임시 리스트는 찾아가는 방향들을 나타낸다.

1. 시작

먼저 출발지인 A에서 시작한다. A가 출발지이므로 이미 결정된 경로인 영구 리스트는 비어있고, 임시 리스트는 A에서 시작해야하므로 A 하나만 있다. 괄호 속에 들어있는 것은 Cost이면서 Delay이다. (OSPF는 Cost와 Delay를 모두 고려한다. 이를 모두 고려한 숫자가 그림 11.4의 숫자들이다.)

 

2. 이동(1)

A에서 출발하는 것이 결정되었으므로 영구 리스트에는 A가 들어가고 A에서 이동할 수 있는 경로들인 B와 C,D가 임시 리스트에 들어간다. A는 Flooding 방식으로 연결된 모든 노드들에 데이터를 보내고 가장 빨리 응답이 오는 곳에 우선권을 부여한다. 선에 적힌 숫자로 보아 Delay 시간이 C가 가장 적으므로 가장 빨리 응답이 오는 곳은 C이다. 따라서 C를 선택한다.

:: 이 과정에서 B와 D는 30초 정도 기다리고 A에서 네가 계속 보내라는 신호가 오지 않으면 그냥 스스로 사라진다.

 

3. 이동 (2)

A와 C가 선택되었으므로 영구 리스트에는 A와 C가 들어간다. A에서 C로 이동하는 비용이 2이므로 괄호 속에는 2가 들어간다. 이제 A와 C를 하나로 보고, 이 상태에서 이동할 수 있는 곳인 B,D,E가 임시 리스트에 담기게 된다. 임시 리스트에 들어있는 E 지점이 괄호에 들어있는 비용은 A에서 C로 간 뒤 E로 갔을 때의 비용이 축적된 것이 들어가는데 이를 축적 비용이라고 한다. 이 축적 비용들을 비교하여가 가장 적은 비용이 드는 지점을 고르는데 이 중 가장 적은 것은 3을 가지는 D이다. 따라서 D가 선택된다.

4. 이동 (3)

위 단계에서 D를 선택했지만 D로 갔다가 E로 가려면 A로 되돌아가서 C를 거쳐 E를 가야하므로 Forward가 아닌 경로가 추가되게 된다. 따라서 D는 선택하지 않는다. (선택되었다가 탈락한 것들은 빨간 원으로 표시하였다.)

이제 남은 비용 중 가장 적은 비용인 B를 선택한다.

 

5. 이동 (4)& 도착

하지만 B또한 hop수가 늘어나게 되므로 선택하지 않고, 결국 E가 선택되게 된다.

 

위 분석에서 알 수 있듯이, OSPF는 도착지에 도달하는 과정에서 unreachable도 선택한다. 따라서 OSPF는 unreachable 이 없다고 본다.

 

[그림 11.6] RIP와 OSPF의 비교

:: 네번째 항목은 이렇게 비교하기도 하지만 별로 맞다고 판단되지 않아서 취소선을 넣음.

:: 분산라우팅 : CISCO에서 사용

:: OSPF의 설정이 어려운 이유는 위의 예시에서 D와 같이 선택해선 안 되는 것들을 걸러내는 부분이 필요하기 때문이다.

:: 속도는 중요하게 생각할 필요가 없다. OSPF는 하드웨어적 처리 속도(CPU에서 처리하는 속도) 는 빠르다. -> 이미 축적된 것을 가져오기 때문에.

:: OSPF의 유지보수가 약한 이유는 모든 데이터를 하나로 묶어서 가지고 있기 때문이다.

 

<중요한 사항>

1. 고정경로 + 우회

2. Flooding (Copy Rule 방식)

3. RIP 라우터를 많이 사용.