라우팅 프로토콜은 라우터끼리 길 정보를 주고받아, 목적지마다 패킷을 어느 이웃에게 넘길지 적은 라우팅 표를 스스로 채우는 규칙입니다. RIP는 이웃이 알려 준 거리로, OSPF는 네트워크 지도 전체로 길을 정합니다.
인터넷의 구성과 교환 방식에서 패킷은 라우터를 여러 개 건너 목적지에 닿았습니다. 라우터마다 갈 길을 사람이 손으로 적어 두면, 링크 하나가 끊길 때마다 표를 모두 고쳐야 합니다. 아래 그림은 같은 지도에서 RIP와 OSPF가 서로 다른 길을 고르는 모습을 보여 줍니다.
1라우팅 표와 라우팅 프로토콜
라우터는 라우팅 표(routing table)에 목적지마다 '다음에 넘길 라우터'와 '거리'를 적어 둡니다. 관리자가 표를 손으로 적는 것을 정적 라우팅(static routing), 프로토콜로 스스로 채우고 고치는 것을 동적 라우팅(dynamic routing)이라고 합니다.
한 기관이 한 정책으로 관리하는 네트워크 묶음을 자율 시스템(AS, Autonomous System)이라고 합니다. AS 안에서 쓰는 내부 라우팅 프로토콜(IGP, Interior Gateway Protocol)에는 RIP와 OSPF가 있고, AS 사이를 잇는 외부 라우팅 프로토콜(EGP, Exterior Gateway Protocol)로는 BGP를 씁니다.
| 가르는 기준 | RIP | OSPF | BGP |
|---|---|---|---|
| 쓰는 곳 | AS 안 | AS 안 | AS 사이 |
| 방식 | 거리 벡터 | 링크 상태 | 경로 벡터 |
| 길을 고르는 값 | 홉 수 | 링크 비용의 합 | 거쳐 가는 AS 목록 |
| 맞는 크기 | 작은 망 | 큰 망 | 인터넷 전체 |
2RIP — 이웃이 알려 준 거리로
RIP(Routing Information Protocol)는 거리 벡터(distance vector) 방식입니다. 라우터마다 목적지까지의 거리를 적은 표를 30초마다 이웃에게 보내고, 받은 거리에 이웃까지의 1을 더해 가장 짧은 쪽을 고릅니다. 이 계산을 벨만-포드(Bellman-Ford) 알고리즘이라고 합니다.
거리는 거쳐 가는 라우터 수, 곧 홉 수(hop count)로 셉니다. 링크가 빠른지 느린지는 보지 않습니다. 최대 15홉까지 쓰고 16은 '갈 수 없음'이라 큰 망에는 맞지 않습니다. 표를 이웃에게서만 받으므로 바뀐 소식이 끝까지 퍼지는 데도 오래 걸립니다.
3OSPF — 지도 전체로 최단 경로
OSPF(Open Shortest Path First)는 링크 상태(link state) 방식입니다. 라우터마다 자기 링크의 상태와 비용을 모든 라우터에게 알려 모두가 같은 지도를 갖고, 각자 그 지도로 다익스트라 알고리즘(Dijkstra algorithm)을 돌려 비용 합이 가장 작은 길을 구합니다. 링크가 바뀌면 바뀐 것만 곧바로 알려 빨리 맞춰지고, 망을 영역(area)으로 나눠 큰 망에도 씁니다.
다익스트라는 출발점의 비용을 0, 나머지를 ∞(아직 모름)로 두고 세 일을 되풀이합니다.
- 아직 확정하지 않은 라우터 가운데 비용이 가장 작은 것을 확정합니다.
- 확정한 라우터를 거쳐 가는 비용이 지금 적힌 값보다 작으면 고쳐 적습니다.
- 모두 확정할 때까지 1로 돌아갑니다.
라우터를 정점, 링크를 간선으로 보면 지도는 그래프입니다. 그래프의 다른 탐색은 그래프와 탐색에서 봅니다.
예제
라우터 다섯(P~T)이 아래 링크로 이어져 있습니다. P에서 T로 갈 때 OSPF와 RIP가 고르는 길을, 종이에 지도를 그려 놓고 구해 보세요.
| 링크 | 비용 |
|---|---|
| P–Q | 2 |
| P–R | 6 |
| Q–R | 3 |
| Q–S | 7 |
| R–S | 1 |
| R–T | 8 |
| S–T | 2 |
OSPF는 다익스트라로 구합니다. 한 줄이 확정 한 번이고, 칸은 그때 적혀 있는 P로부터의 비용입니다.
| 확정 | Q | R | S | T |
|---|---|---|---|---|
| P(0) | 2 | 6 | ∞ | ∞ |
| Q(2) | — | 5 | 9 | ∞ |
| R(5) | — | — | 6 | 13 |
| S(6) | — | — | — | 8 |
| T(8) | — | — | — | — |
OSPF의 길은 P–Q–R–S–T(비용 8, 4홉)입니다. RIP는 홉만 세므로 P–R–T(2홉, 비용 14)를 고릅니다.
시험 포인트
- 필기: RIP는 거리 벡터 방식이고 홉 수로 고르며 최대 15홉, 30초마다 표를 보냅니다. OSPF는 링크 상태 방식이고 다익스트라로 최단 경로를 구하며 큰 망에 맞습니다. BGP는 AS 사이를 잇습니다. 방식과 프로토콜을 엇갈려 짝지은 보기(RIP — 링크 상태)를 고르게 합니다.
- 실기: 이름을 씁니다 — RIP(Routing Information Protocol), OSPF(Open Shortest Path First), BGP(Border Gateway Protocol), 거리 벡터(Distance Vector), 링크 상태(Link State), 다익스트라 알고리즘(Dijkstra Algorithm), 홉 수(Hop Count). 지도를 주고 길을 묻는 문제는 링크 비용이 적혀 있어도 RIP라면 홉 수가 가장 적은 길, OSPF라면 비용 합이 가장 작은 길을 씁니다.
확인 문제
1. 다음 가운데 OSPF에 대한 설명으로 알맞은 것을 고르세요.
- ① 이웃에게서 받은 거리표에 1을 더해 길을 고른다
- ② 홉 수가 16이 되는 목적지는 갈 수 없는 곳으로 친다
- ③ 모든 라우터가 같은 지도를 갖고, 각자 비용 합이 가장 작은 길을 계산한다
- ④ 서로 다른 기관의 네트워크 묶음 사이에서 길을 주고받는다
정답
③입니다. 링크 상태를 모두에게 알려 같은 지도를 만들고, 그 지도로 다익스트라를 돌려 비용 합이 가장 작은 길을 구합니다.
- ① RIP의 거리 벡터 방식입니다.
- ② RIP의 홉 수 한계입니다. 15홉까지 쓰고 16은 갈 수 없음을 뜻합니다.
- ④ AS 사이를 잇는 BGP입니다.
2. 다음 (가)~(다)에 맞는 라우팅 프로토콜의 이름을 약어와 영문 원어로 쓰세요. 답을 끝까지 쓴 뒤 정답을 펼치세요.
- (가) 작은 사무실 네트워크에서 라우터들이 30초마다 이웃에게 '어디까지 몇 단계'인지 적은 표를 보냅니다.
- (나) 큰 회사망을 영역으로 나누고, 링크가 끊기면 그 소식만 곧바로 모든 라우터에 알려 각자 길을 다시 계산합니다.
- (다) 통신사와 통신사처럼 정책이 다른 두 기관의 망 사이에서, 거쳐 가는 기관 목록을 붙여 길을 알립니다.
정답
받는 답: (가) RIP(Routing Information Protocol) · (나) OSPF(Open Shortest Path First) · (다) BGP(Border Gateway Protocol)
(가)의 실마리는 '30초마다 이웃에게 · 몇 단계', (나)는 '영역 · 바뀐 것만 모두에게', (다)는 '정책이 다른 기관 사이 · 거쳐 가는 기관 목록'입니다.
- 틀리는 꼴 OSPF — (가)에: 표를 이웃에게만 주기적으로 보내는 것은 RIP입니다. OSPF는 바뀐 링크 상태를 모두에게 알립니다.
- 틀리는 꼴 OSPF — (다)에: OSPF는 한 AS 안에서 씁니다. AS 사이는 BGP입니다.
3. 다음 (가)~(라)에 맞는 이름을 한글 이름과 영문으로 함께 쓰세요. 답을 끝까지 쓴 뒤 정답을 펼치세요.
- (가) 이웃이 보내 준 표의 '목적지까지 얼마'에 이웃까지의 몫을 더해 길을 고르는 방식
- (나) 라우터마다 자기에게 붙은 선들의 사정과 비용을 모두에게 알려, 모두가 같은 지도를 갖게 하는 방식
- (다) (나)의 지도에서 가장 가까운 라우터부터 하나씩 확정하며 최소 비용을 구하는 계산법
- (라) (가) 방식의 RIP가 길을 고를 때 세는 값으로, 패킷이 목적지까지 라우터를 몇 개 거치는지
정답
받는 답: (가) 거리 벡터(Distance Vector) · (나) 링크 상태(Link State) · (다) 다익스트라 알고리즘(Dijkstra Algorithm) · (라) 홉 수(Hop Count)
(가)의 실마리는 '이웃이 보내 준 표에 더한다', (나)는 '모두에게 알려 같은 지도', (다)는 '가까운 것부터 하나씩 확정', (라)는 '거쳐 가는 라우터를 센다'입니다.
- 틀리는 꼴 링크 상태 — (가)에: 모두에게 알려 지도를 만드는 쪽입니다. (가)는 이웃의 표만 봅니다.
- 틀리는 꼴 벨만-포드 알고리즘 — (다)에: 이웃의 거리표로 고치는 거리 벡터 쪽 계산입니다. 가장 가까운 것부터 확정하는 것은 다익스트라입니다.
4. 그림의 지도에서 C–E 링크의 비용만 2에서 9로 바뀌었습니다. A에서 E로 갈 때 (가) OSPF의 길과 비용, (나) RIP의 길을 쓰세요. 답을 끝까지 쓴 뒤 정답을 펼치세요.
정답
받는 답: (가) A–B–D–E, 비용 8 · (나) A–D–E
다익스트라로 A(0) → B(1) → C(2)를 확정하면 E가 2 + 9 = 11로 적힙니다. 다음 D(3)를 확정하면 D를 거친 3 + 5 = 8이 더 작아 E를 8로 고쳐 적습니다. RIP는 비용을 보지 않아, 비용이 바뀌어도 2홉인 A–D–E 그대로입니다.
- 틀리는 꼴 (가) A–B–C–E: 바뀌기 전의 길입니다. 이제 비용이 1 + 1 + 9 = 11입니다.
- 틀리는 꼴 (나) A–B–D–E: 비용 합으로 골랐습니다. RIP는 홉 수만 셉니다.