EIGRP // DUAL 알고리즘과 Query & Reply packet

Diffusing Update Algorithm 의 약자로 EIGRP에서 최적경로를 찾기 위해 사용하는 알고리즘이다.

기본적으로 EIGRP에서 최적경로를 계산하기 위해서는 대역폭(Bandwidth)과 지연시간(Delay)를 사용하는데 이 때 대역폭은 목적지까지 가는 동안의 최저 대역폭을, 지연시간은 목적지까지 가는 지연시간의 합을 사용한다.

DUAL을 이해하기 위해서 먼저 알아야 하는 용어들을 살펴보자.

   

1. FD (Feasible distance)

출발지부터 목적지까지 Metric의 합

2. AD (Advertised distance)

출발지 다음 Router부터 목적지까지 Metric의 합

3. Successor

EIGRP환경에서 목적지로 가기 위한 최적경로

FD값이 가장 작은 길

4. Feasible successor

목적지로 가기 위한 대체경로

Feasible successor가 되기 위한 조건

해당 경로의 AD가 Successor의 FD보다 작아야 한다

그렇지 않으면 목적지 네트워크로 가는 경로가 여러 개이더라도 Feasible successor가 될 수 없다

   

예시1

Successor 와 Feasible successor 결정 방법

R1에서 Network A로 가기 위한 길은 2가지가 보인다. FD를 비교하여 작은 길이 Successor로 결정되어 Routing table에 올라간다. R2를 지나서 가는 길은 FD가 20이고 R5를 지나서 가는 길은 10이다. 그러면 Routing table에 생성되는 경로는 R5를 지나서 가는 길이다. R2를 통해서 가는 길의 AD는 10이다. Successor의 FD값보다 작지 않기 때문에 Feasible successor로 뽑히지 않는다.

   

예시2

경로에 문제가 발생했을 때 Query 와 Reply 의 동작과정

   

   

각각의 Router에서 Network A로 가기 위한 최적경로를 다음과 같이 Dual 알고리즘으로 결정하였다. 만약에 R2와 R3 사이의 Link가 끊겼다면 어떤 일이 발생하는지 알아본다

   

   

Network A로 가기 위한 최적 경로를 잃은 R3는 Feasible successor가 있는지를 찾는다. 하지만 Feasible successor가 생성되지 않았기 때문에 인접장비인 R4와 R5에게 Network A로 가는 길을 알려달라는 Query를 보낸다. Query를 받은 R4와 R5는 R3를 거쳐서 가는 길에 문제가 생겼음을 확인하고 해당 경로를 삭제한다.

   

   

R4, R5는 자신이 가진 정보를 찾아보고 전달해주게 되는데 R4는 최적경로(R2를 거쳐가는 길)를 Reply를 통해 알려준다. R5는 Network A로 가는 최적경로가 없기 때문에 R4에게 Query를 보낸다.

   

   

R3는 R4에게서 받은 정보를 자신의 Topology table에 저장해 놓는다. 아직 R5에게서 Reply가 오지 않았기 때문에 Dual 알고리즘으로 경로 계산을 하지 않는다. R5에게서 Query를 받은 R4는 R5로 가는 길을 지운 후 자신이 가진 최적경로 정보를 Reply를 통해서 전달한다. 그러면 R5는 Dual 알고리즘으로 계산 후 R4에게서 받은 경로를 Successor로 선출한다.

   

   

그리고 이정보를 R3에게 보낸다. 그러면 R3는 이제 Dual 알고리즘으로 최적경로를 결정하는 계산을 한다.

R4를 거쳐 가는 길과 R5를 거쳐 가는 길 FD가 같기 때문에 2가지 경로가 모두 Successor가 되어 Routing table에 생성된다. 즉, 부하분산이 일어난다. ( AD는 Feasible successor를 구할 때 사용하는 것이기 때문에 달라도 Successor를 선택하는 것에는 영향을 주지 않는다. 헷갈리지 말자)

   

   

즉, 결과는 다음과 같다