순환이 없는 라우팅을 위한 확산 계산 사용

컴퓨터 네트워크 또는 인터넷에서 최단 경로의 동적 계산을 위한 분산 알고리즘의 가족이 제시되고, 검증되며, 분석됩니다. 이러한 알고리즘에 따르면, 각 노드는 다른 모든 노드에 대한 거리를 포함하는 벡터를 유지합니다. 노드에서 업데이트 메시지는 이웃 노드에게만 전송되며, 각 메시지는 하나 이상의 항목으로 구성된 거리 벡터를 포함하고, 각 항목은 네트워크 목적지까지의 선택된 경로의 길이와, 해당 항목이 업데이트, 쿼리 또는 이전 쿼리에 대한 응답인지를 나타내는 지시를 포함합니다. 새로운 알고리즘은 분산 최단 경로 라우팅 문제를 확산 계산 문제로 간주하며, 이는 Dijkstra와 Scholten(1980)에 의해 처음 제안되었습니다. 이들은 이전에 도입된 여러 알고리즘을 개선합니다. 새로운 알고리즘은 링크 비용 또는 토폴로지 변화의 임의의 순서 후에 유한한 시간 안에 수렴하고, 모든 순간에서 순환이 없으며, 결합된 시간, 메시지 및 저장 복잡성의 관점에서 이전에 제안된 모든 순환이 없는 라우팅 알고리즘을 초월하는 것으로 나타났습니다.