Unicast Routing Protocol
유니캐스트 라우팅 프로토콜
- Unicast Communication(유니캐스트 통신)*상에서 최적의 Metric(비용)**을 갖는 통신 경로를 찾아내는 프로토콜을 의미한다.
- 라우터들은 라우팅 프로토콜을 이용하여 인터넷의 수정 사항을 서로에게 알려 최적의 통신 경로를 갱신해나간다.
* Unicast Communication(유니캐스트 통신)
- 하나의 Sender와 하나의 Receiver 간의 통신을 의미하며, One-to-One 통신이라 하기도 한다.
** Metric(비용)
- Graph의 Weight, Cost와 같은 의미이다.
- Edge(경로)에 부여되는 특정한 값이다. (도로의 길이, 정체 상황, 이동 비용 등)
Autonomous System (AS; 자율 시스템)
- 인터넷은 Autonomous System(AS; 자율 시스템)의 관리 단위로 나뉘며, 자율 시스템은 단일 관리 기관 하에 있는 라우터와 네트워크 그룹을 의미한다.
- 대규모의 인터넷을 AS로 나누어 Divide & Conquer 방식으로 다루기 위한 개념이다.
- 각각의 AS끼리는 서로의 네트워크 구조를 공유하여, 외부의 네트워크 상황을 알게 된다.
Static Routing Table - Dynamic Routing Table (정적 라우팅 테이블 - 동적 라우팅 테이블)
Static Routing Table (정적 라우팅 테이블)
- 주로 Host가 갖고 있는 라우팅 테이블을 의미한다.
- ICMP Redirection 메시지를 받지 않는 한, 거의 변하지 않는다.
- 네트워크 변경 사항이 즉각적으로 갱신되지 않고, 테이블의 크기가 크지 않다.
Dynamic Routing Table (동적 라우팅 테이블)
- 주로 라우터가 갖고 있는 라우팅 테이블을 의미한다.
- 네트워크의 변경 사항이 즉각적으로 갱신되며, 테이블의 크기가 큰 편에 속한다.
Intradomain - Interdomain (도메인 내 라우팅 - 도메인 간 라우팅)
Intradomain (도메인 내 라우팅)
- 자율 시스템 내에서의 라우팅을 의미한다.
- 각 자율 시스템은 하나 이상의 Intradomain 라우팅 프로토콜을 사용하게 된다.
- Distance Vector Routing 알고리즘 기반의 RIP 라우팅 프로토콜
- Link State Routing 알고리즘 기반의 OSPF 라우팅 프로토콜
Interdomain (도메인 간 라우팅)
- 자율 시스템 간의 라우팅을 의미한다.
- 자율 시스템 간 라우팅을 처리하기 위해 하나의 Interdomain 라우팅 프로토콜을 사용하게 된다.
- Path Vector Routing 알고리즘 기반의 BGP 라우팅 프로토콜
Bellman-Ford Algorithm (벨만-포드 알고리즘)
- 그래프상에서, 임의의 두 노드간의 최단 거리(최소 비용) 경로를 찾아내는 알고리즘이다.
- 거리 벡터 라우팅 알고리즘의 기초가 되는 알고리즘이다.
- 노드 \(i\)는 노드 \(1, 2, \cdots , N\)과 하나의 Edge로 연결되어 있다.
- 노드 \(1, 2, \cdots , N\)에서 노드 \(j\)까지의 최단 경로는 이미 알고있다 가정한다.
- 이 때, \(i\)에서 \(j\)로 가는 최단 경로 \(D_{ij}\)는 \(minimum{(c_{i1} + D_{1j}), (c_{i2} + D_{2j}), \cdots, (c_{iN} + D_{Nj})}\) 이다.
Distance Vector Routing Algorithm (거리 벡터 라우팅 알고리즘)
- 벨만-포드 알고리즘을 기반으로 한 알고리즘이다.
- 각 라우터들은 거리 벡터 알고리즘을 수행하며 네트워크의 수정 사항을 갱신해나간다.
Distance_Vector_Algorithm() {
// At startup
// 라우터가 Power-on 되었을 경우 행해지는 작업이다.
// 전원이 켜지는 그 시점에서 라우터는 인접한 노드들만 인지하고 있다.
for (i = 1 to N) { // N is number of ports
Table[i].dest = address of the attached network
Table[i].cost = 1 // 직접 연결된 네트워크이므로 거쳐가는 라우터의 개수는 1이다.
Table[i].next = Direct // 인접한 노드임을 의미한다.
// Interface 칼럼은 생략하였다.
Send a record R about each row to each neighbor // dest와 cost만 전송한다. (NHA는 따로 알리지 않는다.)
} // end for loop
// Updating
Repeat (forever) {
Wait for event
if (event is arrival of R from a neighbor) // Neighbor로부터 R 이라는 정보를 수신했을 때
Update(R, T) // 내 라우팅 테이블 T에 정보 R을 반영한다.
else // event is time-out (보통 30초 간격으로 Re-Protocol 한다.)
Send R from its T to each neighbor // 주기적으로 Neighbor에게 라우팅 정보를 전송한다.
} // end repeat
} // end Distance_Vector
// Update Module
Update(R, T) {
Search T for a destination matching the one in R // R : Destination 정보 + Cost 정보
if (destination is found in row i) { // R속의 Destination이 내 라우팅 테이블에 있는 경우 = 새로 갱신되는 경우
if (R.cost + 1 < T[i].cost or Address of sending router == T[i].next) {
// 현재 경로보다 최소 비용 경로이거나 NHA로부터 송신된 최신정보이면 Update 한다. (무조건 최신 정보로 업데이트하게 된다.)
T[i].cost = R.cost + 1
T[i].next = Address of sending router
}
else
discard the record // No change is needed
}
else { // a new network is found (R속의 Destination이 내 라우팅 테이블에 없는 경우 = 새로 추가되는 경우)
// Insert new network
T[N+1].dest = R.dest
T[N+1].cost = R.cost + 1 // 인접한 Neighbor가 알려준 정보이므로, cost는 1만 더하면 된다.
T[N+1].next = Address of sending router // 라우팅 정보를 알려준 라우터의 주소가 NHA가 된다.
}
} // end of Update Module
※ Cost는 아래와 같이 해석될 수 있다.
1. 패킷이 이동하면서 거쳐가는 라우터의 개수이다.
(Direct Delivery의 경우 Cost는 1이다. 즉, 라우터 자기 자신도 반영해야 함을 의미한다.)
2. 패킷이 이동하면서 거쳐가는 네트워크의 개수이다.
※ Routing 정보를 Neighbor에게 알릴 때에는 Destination과 Cost 정보만 넘겨주게 된다.
- 일반적인 거리 벡터 라우팅 알고리즘에서 라우팅 정보는 Destination과 Cost정보를 한꺼번에 전송한다.
- 위 Pseudo Code에서는 Destination과 Cost 정보를 하나의 Entry씩 전송하는 형태로 설명하고 있다.
- 수신한 라우팅 정보의 NHA는 당연히 건네받은 라우터의 주소가 된다.
※ Update*는 아래 3가지 경우에 해당되면 수행된다.
1. 보다 최소 비용 경로에 대한 정보가 수신되었을 경우
2. 이전에 NHA로부터 수신했던 내용에 대한 최신 정보가 수신되었을 경우 (최소 비용 여부에 관계없음)
3. 새로운 노드에 대한 정보가 수신되었을 경우
* Update : 수신한 라우팅 정보를 자신의 라우팅 테이블에 반영하는 작업이다.
※ Two-Node Instability (두 노드 간의 불안정성)
- 그림과 같이, Distance Vector Routing Algorithm을 사용하는 네트워크에서 라우터 A에 인접한 네트워크 X와의 연결이 끊어졌을 때 발생할 수 있는 문제점이다.
- 네트워크 X와의 Failure에 관한 라우팅 정보를 노드 A와 B가 주고받으며 생기는 무한 Loop에 관한 문제이다.
- 노트 A는 X와의 Failure를 감지하고, X로의 Cost를 무한대로 설정하여 라우팅 테이블에 Failure를 반영한다.
- Failure를 먼저 감지하는 것은 노드 A이고 A가 먼저 B에게 라우팅 정보를 전송한다면 문제가 발생하지 않겠지만, 노드 A가 먼저 갱신된 라우팅 정보를 B에게 전송한다는 보장이 없다.
- 즉, Two-Node Instability는 Failure 발생 이후에 B가 먼저 라우팅 정보를 보냈을 때 발생하는 문제이다.
(B가 보내는 라우팅 정보는 근본적으로 A에게 기존에 받았던 라우팅 정보이다. 즉, A에게 받은 라우팅 정보를 다시 A에게 보낼 때 문제가 발생하게 된다.)
- 그림과 같이, Failure 이후에 B가 먼저 라우팅 정보를 A에게 보내고, A가 갱신한 라우팅 정보를 B에게 보내는 식의 Loop(인접한 라우터에서 수신한 정보이므로, Cost에 1을 더하여 저장하게 된다.)가 발생하면, 무의미하게 오랜 시간동안 라우팅 정보를 주고받게 되고, 결국엔 노드 A와 노드 B의 라우팅 테이블에는 X로 향하는 NHA를 서로를 가리키게 되어 패킷이 무한루프에 갇히게 된다.
Solution: Two-Node Instability
- Two-Node Instability에 대한 해결책이다.
- Cost값의 MAX를 무한대가 아닌, 16으로 설정한다.
- A에게 기존에 받았던 라우팅 정보를 다시 A에게 못 보내게 하는 방법으로, Split Horizon(수평 분할), Poison Reverse가 있다.
- 인접한 라우터로부터 라우팅 정보를 수신할 때, 자연히 Cost는 1을 더하여 반영한다. (인접한(바로 옆) 라우터에서 받았으므로, Cost에 1이 더해지는 것이다.)
1. Split Horizon
- R로부터 온 라우팅 정보를 R에게는 다시 알리지 않게하는 방법이다.
2. Poison Reverse
- R로부터 온 라우팅 정보를 다시 R에게 알릴 경우, Cost를 16(최대값)으로 설정하여 전송하는 방법이다.
Ex. Split Horizon - Poison Reverse
- Split Horizon 방식에서는 R1에게서 받은 Entry는 제외하고 전송한다.
(여기선, (N1, 1) Entry가 R1에게서 받은 라우팅 정보에 해당된다.)
- Poison Reverse 방식에서는 R1에게서 받은 Entry의 Cost를 16으로 설정하여 전송한다.
RIP (Routing Information Protocol)
※ "립"이라 발음한다.
- Distance Vector Routing Algorithm 기반의 라우팅 프로토콜이다.
- Intra Domain(Interior) 라우팅 프로토콜 중 하나이다.
- 고안된지 오래된 라우팅 프로토콜로, 오늘날 널리 쓰이는 Intra Domain 라우팅 프로토콜로는 OSPF가 있다.
- RIP은 UDP의 Well-Known Port 520에서 제공하는 서비스이다.
(즉, RIP 요청/업데이트 메시지는 User-Datagram 이다.)
Ex. Domain using RIP
- R1 ~ R4 라우터들과 각각의 물리 네트워크로 구성된 하나의 AS이다.
- 각각의 라우터들은 서로 라우팅 정보를 주고받으며 그림의 AS에 대한 모든 네트워크 정보를 알고있는 상태가 된다.
Example 11.4 (TCP/IP Protocol Suite p.295)
위 그림과 같은 하나의 AS에서, R2가 R1에게 Request for all 형태의 RIP Request Message(요청 메시지)를 전송한다고 할 때, R2가 R1으로부터 수신하게 될 RIP Update Message(응답 메시지)는 어떠한 형태일 것인가.
Sol)
- 195.2.4.0, 195.2.5.0, 195.2.6.0 네트워크는 R1이 R2로부터 알게된 정보이므로, Cost를 16으로 설정한다.
- 위 3개의 네트워크에 대한 Cost를 16으로 전송한 모습을 보아, Poison Reverse 방식으로 응답 메시지를 작성했음을 알 수 있다.
- 위 3개의 네트워크에 대한 정보를 아예 보내지 않으면 Split Horizon 방식인 것이다.
RIP Message Format (RIP 메시지 형태)
- RIP 프로토콜 하에서, 라우터들끼리 라우팅 정보를 주고받을 때 사용하는 메시지의 형식이다.
- Command : Request(요청)일 경우 1, Update(응답)일 경우 2로 설정된다. 응답메시지가 라우팅 정보를 담고있는 것이 일반적이다.
- Version : 본 포스트에서 설명하는 RIP의 버전은 1이다.
- Repeated 되는 필드(회색부분)에 Destination과 Cost에 해당되는 정보들이 입력된다.
- Family : TCP/IP의 경우, Family 값은 2로 고정된다.
- Network Address : Destination 정보에 해당된다.
- Distance : Cost 정보에 해당된다.
RIP Request Message (RIP 요청 메시지)
- RIP 요청 메시지의 경우, Command 값이 1로 설정된다.
- RIP 요청 메시지의 경우, 아래와 같이 두 가지 형태로 존재하게 된다.
a. Request for some
- 지정한 네트워크에 대한 Cost를 요청하는 형태이다.
- Network Address에 알고자하는 네트워크의 주소를 입력하여 전송한다.
- 다수의 네트워크에 대한 Cost를 알고자 하는 경우, 요청 메시지를 Repeat(반복; 연장)하여 전송한다.
b. Request for all
- 요청 메시지를 받게될 라우터가 알고있는 모든 라우팅 정보를 보내줄 것을 요청하는 형태이다.
- Network Address에 0.0.0.0(All 0s)을 입력하여 전송한다.
- 요청 메시지를 반복(연장)할 필요가 없다.
※ RIP은 UDP에서 제공되는 서비스이므로, RIP 요청/업데이트 메시지는 User-Datagram이다.
RIP Timer (RIP 타이머)
- RIP이 정상적으로 동작하기 위해 존재하는 3가지의 타이머이다.
1. Periodic Timer (주기적 타이머) 25s ~ 35s
- 모든 라우터들이 자신의 라우터 정보를 Neighboring Router(인접한 라우터)에게 전송하는 시간 간격이다.
- 라우터(라우팅 테이블)마다 하나만 존재하는 타이머이다.
- 라우터들은 평균 30초 간격*으로 라우팅 정보를 인접한 라우터들에게 전송하게 된다.
* 주기를 25초에서 35초 사이의 "범위"로 설정한 이유
- 하나의 네트워크를 두고 여러 라우터들이 라우팅 정보 메시지를 동시에 같은 시각에 전송하게 되면 메시지가 서로 충돌할 가능성이 존재한다.
- 충돌을 방지하기 위해, 각각의 라우터에서는 주기적 타이머의 시간값을 아래와 같이 난수화한 값으로 설정한다.
\(25 + 10 * {rand(seed) \over MAX}\) : 이와 같은 수식의 결과(25~35사이의 값)를 자신의 주기적 타이머 값으로 설정하게 된다.
각각의 라우터들끼리 seed값을 달리하기 위해, 자신의 IP주소를 seed로 활용한다. (IP주소는 서로 다르기 때문이다.)
2. Expiration Timer (만료 타이머) 180s
- Update 메시지를 받은 직후 180초간 동작되는 타이머이다.
- 라우팅 테이블의 유효한 엔트리는 저마다 하나씩의 만료 타이머를 갖는다.
- 주기적 타이머에 의해 평균 30초 간격으로 만료타이머가 계속해서 리셋되는 것이 가장 이상적인 경우에 해당된다.
- 만료 타이머가 만료되었다 함은, 평균적으로 6개의 Update 메시지가 수신되지 못한 경우를 의미하고, 해당 경로로의 Connection이 끊겼다고 판단해도 무방하다.
- RIP의 경우, Disconnection을 감지하면, Cost를 16으로 설정하여 엔트리를 무효화한다.
3. Garbage Collection Timer (폐 경로 수집 타이머) 120s
- 만료 타이머에 의해 무효화 된 엔트리가 생기면 동작하는 타이머이다.
- 라우팅 테이블의 무효한 엔트리는 저마다 하나씩의 폐 경로 수집 타이머를 갖는다.
- 주기적 타이머에 의해, 엔트리를 무효화한 사실이 평균적으로 4번 전송될 수 있다.
- Garbage Collection Timer가 Time-Out(120초 초과)되면, 무효화된 엔트리는 폐기된다.
※ 타이머의 개수
1. 주기적 타이머 : 라우팅 테이블(라우터) 당 1개
2. 만료 타이머 : 라우팅 테이블의 유효한 엔트리 당 1개
3. 폐 경로 수집 타이머 : 라우팅 테이블의 무효한 엔트리 당 1개
Example 11.5 (TCP/IP Protocol Suite p.297)
A routing table has 20 entries. It does not receive information about five routes for 200 s. How
many timers are running at this time?
Sol) 총 21개의 타이머가 작동할 것이다.
5개의 라우터로 부터 180초가 넘는 시간동안 정보를 수신하지 못했으므로, 5개의 유효한 엔트리가 무효화될 것이다.
즉, 1개의 라우팅 테이블에 대한 주기적 타이머 1개,
15개의 유효한 엔트리들에 대한 만료 타이머 15개,
5개의 무효한 엔트리들에 대한 폐 경로 수집 타이머 5개,
총 21개의 타이머가 작동중인 상태이다.
Drawbacks of RIP (RIP의 문제점)
1. 대규모 네트워크에 적용이 어렵다.
- RIP에서 Cost의 최댓값은 16이다.
2. 하나의 Metric만 존재할 수 있다.
- Cost로써 Number of Hops(거치는 라우터 혹은 네트워크의 개수)만 존재하며, 여러 요인을 적용할 수 없다.
ex) 네비게이션 프로그램과 같이, 도로의 길이와 이동 비용, 정체 상황과 같은 여러 요인을 적용할 수 없다.
3. Source에서 Destination까지의 하나의 Path만 생성할 수 있다.
- 네트워크의 Congestion에 대응하여 패킷을 여러 경로로 전송할 수 없다.
Link State Routing Algorithm (링크 상태 라우팅 알고리즘)
- 근래에 많이 사용되는 라우팅 알고리즘이다.
- OSPF 프로토콜은 링크 상태 라우팅 알고리즘을 기반으로 한 대표적인 알고리즘이다.
- Link State란, 라우터 자신에게 연결된 Edge 정보(특정 노드와의 연결 여부와 Cost 등)를 의미한다.
- 링크 상태 라우팅 알고리즘은, 각 라우터들이 자신의 LSP(Link State Packet)*를 Flooding(플러딩)**하는 방식으로 동작한다.
- 결과적으로, 모든 라우터들이 Link State(Edge 정보)를 다 알게 되며, 모두가 Complete Network Topology를 파악한 상태가 된다.
- 각각의 라우터들은 LSP를 인접한 노드에게 주기적으로 전송하며, Link의 변화가 감지되면 그 즉시 LSP를 인접한 노드에게 전송하는 식으로 Update한다.
- 각각의 라우터 혹은 물리 네트워크 노드에서는 Shortest Path Algorithm을 이용하여 특정 노드로의 최단 경로를 계산한다. (대표적으로 Dijkstra Algorithm을 이용한다.)
* LSP (Link State Packet; 링크 상태 패킷)
- 라우터 자신의 Link State를 저장한 패킷이다.
** Flooding(플러딩)
- 다른 라우터들에게 효과적이며 안전한 방법으로 LSP(Link State Packet)를 전송하는 방법이다.
- 인접한 라우터에 LSP를 전달하고, 이를 수신한 라우터가 다른 라우터에게도 전송하는 방식이다.
※ 그림에서와 달리, 실제 링크 상태 라우팅 알고리즘에서 노드는 라우터와 네트워크로 구성된다. (라우터만이 노드가 아니다.) 위 그림은 각 Link(Edge)마다 존재하는 하나 이상의 Network 노드가 생략된 형태이다.
※ 단, Point to Point Network는 노드로 모델링하지 않는다.
Link State Routing Algorithm의 수행과정 (4-Phase)
1. 모든 라우터들의 LSP의 생성
2. Flooding Dissemination of LSP to every other nodes
- 플러딩을 통한 모든 노드로의 LSP 보급
3. Dijkstra's Algorithm Formation of shortest path tree
4. Calculation of routing table
OSPF (Open Shortest Path First)
- Link State Routing Algorithm에 기반한 프로토콜이다.
- 각 라우터들이 링크 정보를 주고받음으로써, 네트워크 전체에 대한 Topology를 알게 되고, 전체 네트워크에 대한 최단경로를 주로 다익스트라 알고리즘을 통해 계산한다.
- Intra Domain(Interior) 라우팅 프로토콜 중 하나이다.
- RIP 프로토콜의 단점*을 개선했다.
* RIP은 대규모 네트워크에 적용할 수 없고, 하나의 Metric, 하나의 패킷 전송 경로만 생성할 수 있다는 단점이 있다. (자세한 내용은 본 블로그의 포스트 참조)
Area
- AS내에 포함되는 호스트, 라우터, 네트워크의 집합이다.
Backbone Area
- 모든 Area들의 기본이 되는 Area를 의미한다.
Area Border Router
- 각 Area를 상호 연결하는 라우터이다.
- 양쪽 Area에 서로의 네트워크 정보에 대한 Summary를 공유하게 한다.
AS Boundary Router
- 각 AS를 상호 연결하는 라우터로, Backbone Area에 위치한다.
- 각 라우터들은 자신이 속한 Area의 Complete Network Topology를 바탕으로 라우팅 테이블을 생성한다.
- 즉, Area내에 위치하는 라우터들은 자신이 속한 Area의 Complete Topology를 알게 되고, 외부 Area의 Topology Summary를 알게 된다.
Types of Link (Link = Physical Network 의 유형)
- 각각의 링크들은 그래프로 모델링되어 표현된다.
※ Virtual은 생략한다.
1. Point to Point Link (점-대-점 링크)
- Point to Point Link는 노드 A와 B, 두 노드만 연결하므로, Edge로 모델링 한다.
- 위 그림은 Bidirectional Edge로 모델링한 Point to Point Network의 예시이다.
2. Transient Link (경유 링크)
- 패킷의 Source, Destination이 위치하지 않은 네트워크로, 패킷이 경유하기 위한 네트워크를 모델링하는 방법이다.
- 하나의 라우터에 네트워크가 두 개 이상 연결된 형태의 네트워크이다. (경유지이므로)
- 그림 b. Unrealistic과 같은 형태로 모델링 할 경우, Edge의 개수가 너무 많아 설계가 어렵고 비용이 높다는 한계가 있다.
- 실제로는 그림 c. Realistic과 같이, Designated router 노드로 모델링한다.
Realistic Transient Network Modeling
- 실제로, Transient Network는 하나의 Network Node로 모델링한다.
- 모든 라우터와 네트워크 노드 사이는 Bidirectional Edge로 구성된다.
- 라우터에서 Network로 향하는 Path의 Cost는 치르고, Network에서 라우터로 향하는 Path의 Cost는 치르지 않는다.
ex) A에서 C로 전송되는 Cost는 2C가 아닌, 1C이다. (네트워크 노드에서 라우터 C로 가는데에는 Cost를 치르지 않는다.)
- 각 라우터들에서 네트워크 노드로 가는 Link State들은 각각의 라우터들이 알린다.
- 네트워크 노드에서 각 라우터들로 가는 Link State들은 네트워크 노드에 연결된 라우터 중 하나인 Designated Router(A ~ E 중 하나)가 알린다.
3. Stub Link (스터브 링크)
- Source와 Destination의 역할만을 수행하는 네트워크를 의미한다.
- 네트워크가 하나의 라우터에 연결된 형태이다.
- 즉, 네트워크는 Sender 혹은 Receiver의 역할만을 수행하며, Transient할 수 없다. (경유지가 될 수 없다.)
- 라우터 A에서 네트워크 노드로 향하는 Path에만 Cost를 치르는 구조이다.
Ex 간단한 AS내에서의 OSPF 동작 원리 예시 1
- N1, N3는 Transient Network이다.
- N2, N4, N5는 Stub Network이다.
- N1 ~ N5는 네트워크 노드로 모델링된다.
- T-1(1.544Mbps), T-3(45Mbps) Line은 Point to Point 연결 방식의 라인이며, Bidirectional Edge로 모델링 된다.
- Transient Network과 Stub Network에서 라우터로 향하는 Path에 Cost가 없음에 유의해야 한다.
Ex 간단한 AS내에서의 OSPF 동작 원리 예시 2
- 위 그림과 같은 AS의 Network는 Bus, Ring, P2P 방식으로 구현되며, Cost는 위와 같다고 가정한다.
- Area 1입장에서의 모델링은 아래와 같이 표현할 수 있다.
- 네트워크 노드는 원으로, 라우터 노드는 사각형으로 표현한다.
- 자신의 Area에서는 Complete Network Topology를 알고 있고, 다른 Area는 Summary Topology를 알고 있으므로 위와 같은 그림으로 모델링하게 된다.
OSPF Packet (OSPF 패킷)
- OSPF 패킷은 IP-Datagram(L3) 패킷 위에서 Encapsulation된다.
- OSPF 패킷은 크게 다섯 가지 종류로 구분된다.
1. Hello Packet
- 라우터가 Power-On되었을 때, 주변 라우터에게 보내는 메시지이다.
2. Database Description Packet (DB Description Packet)
- Hello 패킷을 수신한 라우터가 보내는 메시지이다.
- 라우팅 테이블에 대한 윤곽(개요)을 전송한다. (라우팅 테이블 전체를 전송하는 것이 아니다.)
3. Link State Request Packet
- DB Description 패킷을 수신한 후에도 추가적인 정보를 원할 때 보내는 요청 메시지이다.
4. Link State Update Packet
- Link State 요청 메시지를 수신한 라우터가 보내는 메시지이다.
- 5가지 종류의 링크*로 구성된다.
5. Link State Acknowledgment (Link State ACK)
- Link State Update 패킷에 대한 ACK 메시지이다.
※ 라우터끼리 1번 패킷부터 5번 패킷까지 차례대로 주고받으며 라우터를 초기화한다.
※ 네트워크에 문제(변경사항)가 발생할 경우, 이를 알고있는 라우터가 Link State Update 메시지를 통해 알리게 되고, 새로 알게된 라우터는 Link State ACK를 전송하게 된다.
*Type of Link for Link State Update Packet(Link State Update 패킷을 구성하는 링크의 종류)
1. Router Link
- 라우터에 연결된 Link State(Edge 정보)를 의미한다.
- 라우터에 인접한 Stub Network, P2P Connection, Transient Network로의 링크 정보를 통칭하여 "라우터 링크"라 한다.
2. Network Link
- Transient Network에 대한 Link State이다.
- Network Link는 Cost를 갖지 않는다.
3. Summary Link to Network
- 한 Area에 속한 라우터는 자신이 속한 Area의 Complete Network Topology를 알고 있으며, 다른 Area는 Summary Topology 형태로 알고있다.
- Summary Link는 연결 여부, Cost와 같은 핵심적인 정보를 요약해놓은 형태이며, 자세한 경로를 의미하지는 않는다.
4. Summary Link to AS Boundary Router
- AS Boundary 라우터에 대한 Summary Link를 의미한다.
- AS Boundary 라우터는 한 AS와 다른 AS를 상호 연결하는 라우터이다.
- AS Boundary 라우터는 각 Area Boundary 라우터와 P2P로 연결되어 각각의 Area의 Link Summary 정보를 전달받는다.
5. External Link
- AS Boundary 라우터와 AS의 외부에 존재하는 네트워크가 서로 연결되어 있음을 알리는 링크 정보이다.
- 단, AS에 하나의 AS Boundary 라우터만 존재할 경우 External Link 정보를 전송할 필요가 없어진다.
(외부 네트워크로 송신되는 패킷은 무조건 단일 AS Boundary 라우터로 나가기 때문이다. 즉, AS Boundary 라우터가 Default 라우터가 된다.)
Example 11.9 - 11.10 (TCP/IP Protocol Suite p.314)
Which router(s) sends out router link LSAs? and Which router(s) sends out network link LSAs?
Sol) N1과 N3는 Stub Network, N2는 Transient Network에 해당된다.
R1, R2, R3 라우터 모두 저마다의 라우터 링크 정보를 전송한다.
라우터 링크 : (R1 - N1), (R1 - N2), (R2 - N2), (R3 - N2), (R3 - N3)
네트워크 링크 Transient Network인 N2에 인접한 라우터 R1, R2, R3 중 하나가 Designated Router가 되어 네트워크 링크 정보를 전송한다.
네트워크 링크 : (N2 - R1), (N2 - R2), (N2 - R3)
Path Vector Routing Algorithm (경로 벡터 라우팅 알고리즘)
- AS1~AS3의 각각의 Exterior 라우터(대표 라우터; R1~R3)들 간에 사용되는 라우팅 프로토콜이 Interdomain 라우팅 프로토콜이다.
- 각 Exterior 라우터는 자신의 Reachability(도달 가능성)를 다른 Exterior 라우터에게 알린다.
- Intradomain에서는 송신 경로를 NHA로써 표현하고, Interdomain에서는 송신 경로를 Path*로써 표현한다.
* Path : AS들의 Collection이다.
- 위 그림은 각 Exterior 라우터들의 라우팅 테이블을 표현한 것이다.
- 위 그림은 Address Aggregation을 통해 간소화 한 라우팅 테이블을 표현한 것이다..
- 3가지의 경로들을 하나의 엔트리로 나타내기 위해 수퍼네팅을 수행한다.
- 경로가 3가지이므로, 2bit를 필요로 한다. 따라서 Net-Id가 2bit 줄어들게 된다.
※ Path Vector 라우팅 알고리즘을 통한 Anycast 구현 방식
- Anycast : 1 to Any Communication 형태로, 중복된 목적지 중 가장 최적의 경로로 연결하는 통신 형태이다.
- 다수의 목적지로부터 Source에게 Path가 전송되고, Source는 수신한 Path 중 거치는 Exterior 라우터의 수가 가장 적은 Path를 택하게 된다.
BGP (Border Gateway Protocol)
- 1989년에 처음 도입되어 4번의 버전이 갱신되었다.
- 가장 많이 쓰이는 Interdomain 라우팅 프로토콜이다.
- BGP는 TCP의 Well-Known Port 179에서 제공하는 서비스이다.
(즉, BGP 메시지는 Segment 이다.)
External BGP Session (E-BGP Session)
- 각 AS의 Exterior 라우터들이 서로 연결되는 절차이다.
- 각 Exterior 라우터들은 서로의 Reachability를 공유하게 된다.
Internal BGP Session (I-BGP Session)
- 각 AS의 Exterior 라우터(A1, B1)들은 자신의 AS의 Reachability를 파악하기 위한 절차이다.
BGP Message
- BGP 메시지의 Common Header(공통 헤더)의 형태이다.
- Type 필드를 통해 아래 BGP 메시지 형태를 구분할 수 있다.
- BGP 메시지는 4가지 형태로 구성된다.
1. Open Message
- Exterior 라우터가 Power-on되고, 이웃의 Exterior와 E-BGP Session을 생성하기 위해 송신하는 메시지이다.
2. Update Message
- Path Vector에 대한 정보를 담은 메시지이다.
- Withdrawn Routes : 무효화 된 경로를 의미한다. (다수의 네트워크가 저장될 수 있다.)
- Path Attributes : Path Vector를 의미한다.
- Network Layer Reachability Information : 액세스 가능한 네트워크 주소를 의미한다.
※ 즉, Path Attributes와 Network Layer Reachability Information가 Key 역할이다.
3. Keep-alive Message
- Open 메시지에 대한 ACK 메시지이다. (헤더만 존재한다.)
- 각 AS의 Exterior 라우터들은 서로 주기적으로 Keep-alive 메시지를 주고 받으며, 연결 여부를 지속적으로 파악한다.
4. Notification Message
- 오류가 발생했을 때, 오류에 관한 내용을 송신하는 메시지이다.
Reference: TCP/IP Protocol Suite 4th Edition
(Behrouz A. Forouzan 저, McGraw-Hill, 2010)
Reference: Data Communications and Networking 5th Edition
(Behrouz A. Forouzan 저, McGraw-Hill, 2012)