거리 벡터 알고리즘은 반복적이고 비동기적이며 분산됩니다.
분산:이는 각 노드가 직접 연결된 하나 이상의 이웃으로부터 정보를 수신하고 계산을 수행한 다음 결과를 이웃에 다시 배포한다는 점에서 분산됩니다.반복적 인:이는 이웃 간에 교환할 수 있는 정보가 더 이상 없을 때까지 프로세스가 계속된다는 점에서 반복적입니다.비동기식:모든 노드가 서로 잠금 단계에서 작동할 필요는 없습니다.
• 거리 벡터 알고리즘은 동적 알고리즘입니다.
• 주로 ARPANET, RIP에서 사용됩니다.
• 각 라우터는 다음과 같은 거리 테이블을 유지합니다. 벡터 .

거리 벡터 라우팅 알고리즘의 작동을 이해하기 위한 세 가지 열쇠:

전체 네트워크에 대한 지식:각 라우터는 전체 네트워크를 통해 지식을 공유합니다. 라우터는 네트워크에 대해 수집된 정보를 이웃에게 보냅니다.이웃에게만 라우팅:라우터는 직접 링크가 있는 라우터에만 네트워크에 대한 정보를 보냅니다. 라우터는 포트를 통해 네트워크에 관한 모든 정보를 보냅니다. 정보는 라우터에 의해 수신되고 이 정보를 사용하여 자체 라우팅 테이블을 업데이트합니다.정기적인 정보 공유:30초 이내에 라우터는 주변 라우터로 정보를 보냅니다.

거리 벡터 라우팅 알고리즘

하자_엑스(y) 노드 x에서 노드 y까지의 최소 비용 경로의 비용입니다. 최소 비용은 Bellman-Ford 방정식과 관련이 있습니다.

 d<sub>x</sub>(y) = min<sub>v</sub>{c(x,v) + d<sub>v</sub>(y)} 

어디 minv는 모든 x 이웃에 대해 취해진 방정식입니다. x에서 v로 이동한 후 v에서 y로의 최소 비용 경로를 고려하면 경로 비용은 c(x,v)+d가 됩니다._~에(와이). x에서 y까지의 최소 비용은 c(x,v)+d의 최소값입니다._~에(y) 모든 이웃을 점령했습니다.

거리 벡터 라우팅 알고리즘을 사용하면 노드 x에는 다음 라우팅 정보가 포함됩니다.

• 각 이웃 v에 대해 비용 c(x,v)는 x에서 직접 연결된 이웃 v까지의 경로 비용입니다.
• 거리 벡터 x, 즉 D_엑스= [ 디_엑스(y) : y in N ], N의 모든 목적지 y에 대한 비용을 포함합니다.
• 각 이웃의 거리 벡터, 즉 D_~에= [ 디_~에(y) : x의 각 이웃 v에 대한 y in N ]입니다.

거리 벡터 라우팅은 노드 x가 거리 벡터의 복사본을 모든 이웃에게 보내는 비동기 알고리즘입니다. 노드 x가 이웃 벡터 v 중 하나로부터 새 거리 벡터를 수신하면 v의 거리 벡터를 저장하고 Bellman-Ford 방정식을 사용하여 자체 거리 벡터를 업데이트합니다. 방정식은 다음과 같습니다.

오토캐드 늘이기 명령

 d<sub>x</sub>(y) = min<sub>v</sub>{ c(x,v) + d<sub>v</sub>(y)} for each node y in N 

노드 x는 위의 방정식을 사용하여 자신의 거리 벡터 테이블을 업데이트하고 업데이트된 테이블을 모든 이웃에게 전송하여 자신의 거리 벡터를 업데이트할 수 있도록 합니다.

연산

 At each node x, <p> <strong>Initialization</strong> </p> for all destinations y in N: D<sub>x</sub>(y) = c(x,y) // If y is not a neighbor then c(x,y) = &#x221E; for each neighbor w D<sub>w</sub>(y) = ? for all destination y in N. for each neighbor w send distance vector D<sub>x</sub> = [ D<sub>x</sub>(y) : y in N ] to w <strong>loop</strong> <strong>wait</strong> (until I receive any distance vector from some neighbor w) for each y in N: D<sub>x</sub>(y) = minv{c(x,v)+D<sub>v</sub>(y)} If D<sub>x</sub>(y) is changed for any destination y Send distance vector D<sub>x</sub> = [ D<sub>x</sub>(y) : y in N ] to all neighbors <strong>forever</strong> 

참고: 거리 벡터 알고리즘에서 노드 x는 직접 연결된 하나의 노드에서 비용 변화를 확인하거나 일부 이웃으로부터 벡터 업데이트를 받을 때 테이블을 업데이트합니다.

예를 통해 이해해 봅시다:

정보 공유

• 위 그림에서 각 구름은 네트워크를 나타내고, 구름 안의 숫자는 네트워크 ID를 나타냅니다.
• 모든 LAN은 라우터로 연결되며 A, B, C, D, E, F로 표시된 상자에 표시됩니다.
• 거리 벡터 라우팅 알고리즘은 모든 링크의 비용을 1단위로 가정하여 라우팅 프로세스를 단순화합니다. 따라서 전송 효율은 목적지에 도달하기까지의 링크 수로 측정할 수 있습니다.
• 거리 벡터 라우팅에서 비용은 홉 수를 기준으로 합니다.

위 그림에서 우리는 라우터가 바로 이웃에게 지식을 보내는 것을 관찰합니다. 이웃은 이 지식을 자신의 지식에 추가하고 업데이트된 테이블을 자신의 이웃에게 보냅니다. 이러한 방식으로 라우터는 자체 정보와 이웃에 대한 새로운 정보를 얻습니다.

라우팅 테이블

두 가지 프로세스가 발생합니다.

• 테이블 만들기
• 테이블 업데이트

테이블 만들기

처음에는 네트워크 ID, 비용, 다음 홉 등 최소한 세 가지 유형의 정보를 포함하는 각 라우터에 대해 라우팅 테이블이 생성됩니다.

넷 ID:네트워크 ID는 패킷의 최종 목적지를 정의합니다.비용:비용은 패킷이 해당 위치에 도달하기 위해 거쳐야 하는 홉 수입니다.다음 홉:패킷이 전달되어야 하는 라우터입니다.

• 위 그림에서는 모든 라우터의 원래 라우팅 테이블이 표시됩니다. 라우팅 테이블에서 첫 번째 열은 네트워크 ID를 나타내고, 두 번째 열은 링크 비용을 나타내며, 세 번째 열은 비어 있습니다.
• 이 라우팅 테이블은 모든 이웃에게 전송됩니다.

예를 들어:

 A sends its routing table to B, F & E. B sends its routing table to A & C. C sends its routing table to B & D. D sends its routing table to E & C. E sends its routing table to A & D. F sends its routing table to A. 

테이블 업데이트

• A는 B로부터 라우팅 테이블을 받으면 해당 정보를 사용하여 테이블을 업데이트합니다.
• B의 라우팅 테이블은 패킷이 네트워크 1과 네트워크 4로 어떻게 이동할 수 있는지 보여줍니다.
• B는 A 라우터의 이웃이며 A에서 B로의 패킷은 한 홉에 도달할 수 있습니다. 따라서 B의 표에 제공된 모든 비용에 1이 추가되고 그 합계는 특정 네트워크에 도달하는 데 드는 비용이 됩니다.

• 조정 후 A는 이 테이블을 자신의 테이블과 결합하여 결합된 테이블을 만듭니다.

• 결합된 테이블에는 중복된 데이터가 일부 포함되어 있을 수 있습니다. 위 그림에서 라우터 A의 결합 테이블에는 중복된 데이터가 포함되어 있으므로 비용이 가장 낮은 데이터만 유지합니다. 예를 들어 A는 두 가지 방법으로 네트워크 1에 데이터를 보낼 수 있습니다. 첫 번째는 다음 라우터를 사용하지 않으므로 1홉 비용이 듭니다. 두 번째에는 두 개의 홉(A에서 B로, B에서 네트워크 1로)이 필요합니다. 첫 번째 옵션의 비용이 가장 낮으므로 유지되고 두 번째 옵션은 삭제됩니다.

• 라우팅 테이블 생성 프로세스는 모든 라우터에 대해 계속됩니다. 모든 라우터는 이웃으로부터 정보를 수신하고 라우팅 테이블을 업데이트합니다.

모든 라우터의 최종 라우팅 테이블은 다음과 같습니다.