[컴퓨터 네트워크] Distributed asynchronous Bellman-Ford algorithm(DABFA)

✔ 거리 벡터 라우팅 알고리즘이라고도 한다. 라우팅 결정방식에 사용되는 알고리즘 중의 하나로 모든 라우터가 경로 결정을 주로 거리(distance)에 의존하는 방식이다.

📌 분산형 비동기식 벨만포드 알고리즘 특징(DABFA)

✔ 분산적

• 각 노드는 직접 연결된 이웃들이 보내는 정보로부터 계산하고, 그 계산결과(자신의 거리벡터 계산 복사본)를 이웃에게 알린다.

✔ 비동기적

• 모든 노드가 비동기적으로 제각각 동작하며 계산한다.
• 이웃에서 보내준 경로 예측 값들과 자신이 가지고 있는 경로 예측 값을 비교하여 적은 값을 최적 경로로 삼게된다.

📌 Asynchronous Bellman-Ford algorithm(비동기식)

• 노드 사이의 동기를 유지할 필요가 없다.
• 특정 초기조건이 필요없다.
• 알고리즘 시작 또는 알고리즘 재시작 프로토콜의 필요성 제거하기 위함이다.

✔ 동기식 알고리즘의 두 가지 어려움

• 노드가 알고리즘 시작에 동의하는 데 필요한 메커니즘
• 알고리즘이 실행될 때, 링크 상태 또는 길이가 변경되는 경우 알고리즘을 중단하고 새 버전을 시작하는 데 필요한 메커니즘

💡 벨만 포드 알고리즘 수도코드

Step 1: initialize graph
   for each vertex v in vertices:
       if v is source then distance[v] := 0
       else distance[v] := infinity
       predecessor[v] := null

// Step 2: relax edges repeatedly
   for i from 1 to size(vertices)-1:
       for each edge (u, v) with weight w in edges:
           if distance[u] + w < distance[v]:
               distance[v] := distance[u] + w
               predecessor[v] := u

  // Step 3: check for negative-weight cycles
   for each edge (u, v) with weight w in edges:
       if distance[u] + w < distance[v]:
           error "Graph contains a negative-weight cycle"코드를 입력하세요

💡 벨만포드 알고리즘 예시

📌 Count-to-Infinity Problem in Distance Vector

거리 벡터에는 라우팅 루프(loop)를 돌 수 있는 큰 문제가 있다. 이 문제는 네트워크가 죽을 때에 발생하게 된다. 1. A와 B가 끊어지게 된다.
2. 동시에 B가 테이블에서 갈 수 없는 A를 무한대 길이로 수정한다.
3. 그리고 약간의 시간이 지나고 C가 라우팅 테이블을 B에 준다.
4. 여기서 C는 A, B 사이에 무슨 일이 벌어지는지 모르기 때문에, B는 일전에 말한 ‘너는 A까지 2번에 갈 수 있어’였다는 정보를 C에게 그냥 그대로 준다.
5. 그러고 B는 C가 A에 2번 만에 갈 수 있는 라우팅 테이블을 받게 되고, B는 A를 가려면 C를 거쳐서 나는 3번 만에 갈 수 있다고 수정한다.
6. 또 시간이 지나 B는 C에게 자신의 테이블을 주고, C는 B가 3번 만에 간다는 것만 믿고 A를 가려면 B를 거치고 자신은 4번 만에 간다고 수정한다.

이렇게 5, 6이 반복되면 결국에 B, C는 서로에게 무한대로 가게 되고, 완벽한 루프가 만들어지게 된다. 따라서, 거리 벡터를 사용할 때는 이런 것을 유의하고 제작을 해야 한다.