확산 업데이트 알고리즘

Diffusing Update Algorithm(DUAL; 확산 업데이트알고리즘)은 라우팅 루프가 발생할 가능성이 있을 때마다 특정 루트가 글로벌하게 재계산되도록 시스코의 EIGRP^[1] 라우팅 프로토콜에서 사용되는 알고리즘입니다.그것은 SRI International의 J.J. Garcia-Luna-Aceves에 의해 개발되었다.알고리즘의 풀네임은 DUAL Finite-State Machine(DUAL FSM; 듀얼 유한 상태 머신)입니다.EIGRP는 자율 시스템 내의 루팅을 담당하며 DUAL은 라우팅 토폴로지의 변경에 응답하여 라우터의 라우팅 테이블을 자동으로 조정합니다.

EIGRP는 실행 가능성 조건을 사용하여 루프프리 루트만 선택되도록 합니다.실현 가능성 조건은 보수적입니다.조건이 true일 경우 루프가 발생하지 않지만 상황에 따라서는 수신처에 대한 모든 루트가 거부될 수 있습니다.단, 루프가 없는 루트가 있습니다.

수신처에 대한 실현 가능한 루트를 사용할 수 없는 경우 DUAL 알고리즘은 확산 계산을 호출하여 문제가 있는 루트의 모든 트레이스가 네트워크에서 삭제되도록 합니다.이 시점에서 일반 Bellman-Ford 알고리즘은 새로운 루트를 회복하기 위해 사용됩니다.

작동

DUAL은 루트 계산에 3개의 테이블을 사용합니다.이들 테이블은 EIGRP 라우터 간에 교환되는 정보를 사용하여 작성됩니다.이 정보는 링크 스테이트 라우팅 프로토콜에 의해 교환되는 정보와 다릅니다.EIGRP에서는 교환되는 정보에는 루트, 각 루트의 '메트릭' 또는 비용 및 네이버 관계 형성에 필요한 정보(AS 번호, 타이머, K 값 등)가 포함됩니다.3개의 테이블과 그 기능에 대한 자세한 내용은 다음과 같습니다.

• 네이버 테이블에는 직접 연결된 다른 모든 라우터에 대한 정보가 포함되어 있습니다.지원되는 각 프로토콜(IP, IPX 등)에 대해 별도의 테이블이 있습니다.각 엔트리는 네트워크인터페이스와 주소의 설명을 가진 네이버에 대응합니다.또, 타이머를 초기화해, 접속의 유효 여부를 정기적으로 검출한다.이것은, 「Hello」패킷에 의해서 실현됩니다.지정된 기간 동안 네이버로부터 "Hello" 패킷이 수신되지 않으면 라우터는 다운된 것으로 간주되어 네이버테이블에서 삭제됩니다.
• 토폴로지 테이블에는 자율 시스템 내의 임의의 수신처에 대한 모든 루트의 메트릭(비용 정보)이 포함됩니다.이 정보는 Neighbor 테이블에 포함된 네이버라우터로부터 수신됩니다.행선지에의 프라이머리(사쿠세컨더리) 루트와 세컨더리(실행 가능한 후계자) 루트는, 토폴로지 테이블의 정보에 근거해 결정됩니다.특히 토폴로지 테이블의 각 엔트리에는 다음이 포함됩니다.

"FD(가능 거리)":자율 시스템내의 행선지에의 루트의 계산된 메트릭.

"RD(보고된 거리)":네이버 라우터에 의해 애드버타이즈된 수신처에 대한 메트릭.RD는 FD를 계산하고 루트가 "실현 가능성 조건"을 충족하는지 여부를 판단하기 위해 사용됩니다.

루트 상태:루트는 "active" 또는 "passive" 중 하나로 표시됩니다."패시브" 경로는 안정적이며 데이터 전송에 사용할 수 있습니다."Active" 루트가 다시 계산되고 있거나 사용할 수 없습니다.

• 라우팅 테이블에는, 행선지에의 최적인 루트(최저 「메트릭」의 관점에서)가 포함되어 있습니다).이러한 루트는 토폴로지 테이블의 후계 루트입니다.

DUAL은 토폴로지 테이블 내의 다른 라우터로부터 수신한 데이터를 평가하여 프라이머리(사쿠세컨더리) 루트와 세컨더리(사쿠세컨더리) 루트를 계산합니다.프라이머리 패스는 통상, 행선지에 도달하기 위한 메트릭이 가장 작은 패스입니다.용장 패스는 두 번째로 비용이 낮은 패스입니다(실현가능성 조건을 만족하는 경우).복수의 후계자와 복수의 피지블 후계자가 있는 경우가 있습니다.후계자와 피지블사쿠세사 모두 토폴로지 테이블에 유지되지만 후속자만 라우팅 테이블에 추가되어 패킷 라우팅에 사용됩니다.

루트가 피지블사쿠세서가 되려면 루트의 RD가 후계기의 FD보다 작아야 합니다.이 실현가능성 조건이 충족되면 이 루트를 라우팅 테이블에 추가하는 것으로 루프가 발생할 가능성은 없습니다.

행선지에의 모든 후계 루트에 장해가 발생했을 경우는, 피지블 후계 라우터가 후계 라우터가 되어, 곧바로 라우팅 테이블에 추가됩니다.토폴로지 테이블에 피지블세서가 없는 경우 쿼리 프로세스가 시작되고 새로운 루트가 검색됩니다.

예

범례:

+ = 라우터

- 또는 = 링크

(X) = 링크 메트릭

A (2) B (1) C + - - - + - - - - - + (2) + - - - - + D (1) E

라우터 E의 클라이언트가 라우터 A의 클라이언트와 통신하려고 합니다.즉, 라우터 A와 라우터E 사이의 루트를 사용할 수 있어야 합니다.이 루트는 다음과 같이 계산됩니다.

라우터 E의 근접 라우터는 라우터 C와 라우터 D입니다.라우터 E의 DUAL은 라우터 C와 D에서 라우터 A로의 보고 거리(RD)를 요구합니다.결과는 다음과 같습니다.

수신처:라우터 A

D 경유: RD(4)

C 경유: RD(3)

따라서 C를 경유하는 루트는 비용이 가장 적게 듭니다.다음 단계에서는 라우터E에서 네이버까지의 거리를 리포트된 거리에 가산하여 실현 가능한 거리(FD)를 취득합니다.

수신처:라우터 A

D 경유: RD(4), FD(5)

C 경유: RD(3), FD(6)

따라서 DUAL은 D를 경유하는 루트의 총비용이 가장 낮다고 판단합니다.그 후 D 경유 루트는 패시브상태를 갖추고 라우팅 테이블에 등록되는 "successor"로 마킹됩니다.C 경유 루트는 RD가 후계 라우터의 FD보다 작기 때문에 "실현 가능한 후계 라우터"로 유지됩니다.

수신처:라우터 A

D 경유: RD(4), FD(5) 후계기

C 경유: RD(3), FD(6) 피지블사쿠세사

레퍼런스