라우팅 알고리즘의 작동 방식

1. 물리적으로 연결된 라우터를 식별하고 IP 주소를 얻습니다. 라우터가 작동을 시작하면 먼저 네트워크를 통해 "HELLO" 패킷을 보냅니다. 이 패킷을 수신하는 각 라우터는 IP 주소 가 포함된 메시지로 응답 합니다 .
2. 인접 라우터에 대한 지연 시간(또는 평균 트래픽과 같은 네트워크의 다른 중요한 매개변수)을 측정합니다. 이를 위해 라우터 는 네트워크를 통해 에코 패킷 을 보냅니다 . 이러한 패킷을 수신하는 모든 라우터는 에코 응답 패킷으로 응답합니다. 왕복 시간을 2로 나누어 라우터는 지연 시간을 계산할 수 있습니다. (왕복 시간은 일부 원격 호스트에서 반송된 패킷의 타이밍에 의해 발견되는 네트워크의 현재 지연 측정값입니다.) 이 시간에는 전송 및 처리 시간이 모두 포함됩니다. 패킷이 대상에 도달하는 데 걸리는 시간과 수신자가 처리하고 응답하는 데 걸리는 시간입니다.
3. 네트워크를 통해 다른 라우터에 대한 정보를 브로드캐스트하고 다른 라우터의 정보를 수신합니다. 이 단계에서 모든 라우터는 지식을 공유하고 정보를 서로 브로드캐스트합니다. 이러한 방식으로 모든 라우터는 네트워크의 구조와 상태를 알 수 있습니다.
4. 적절한 알고리즘을 사용하여 네트워크의 두 노드 사이의 최상의 경로를 식별합니다. 이 단계에서 라우터는 모든 노드에 대한 최상의 경로를 선택합니다. 그들은 Dijkstra 최단 경로 알고리즘 과 같은 알고리즘을 사용하여 이를 수행 합니다 . 이 알고리즘에서 라우터는 다른 라우터에서 수집한 정보를 기반으로 네트워크의 그래프를 작성합니다. 이 그래프는 네트워크에서 라우터의 위치와 서로에 대한 링크를 보여줍니다. 모든 링크에는 가중치 또는 비용 이라는 숫자로 레이블이 지정됩니다 . 이 숫자는 지연 시간, 평균 트래픽, 때로는 단순히 노드 간 홉 수의 함수입니다. 예를 들어, 노드와 목적지 사이에 두 개의 링크가 있는 경우 라우터는 가중치가 가장 낮은 링크를 선택합니다.

1. 라우터는 네트워크의 그래프를 작성하고 예를 들어 V1 및 V2와 같이 소스 및 대상 노드를 식별합니다. 그런 다음 "인접 행렬"이라는 행렬을 만듭니다. 이 행렬에서 좌표는 무게를 나타냅니다. 예를 들어, [i, j]는 Vi와 Vj 사이의 링크의 가중치입니다. Vi와 Vj 사이에 직접적인 연결이 없는 경우 이 가중치는 "무한대"로 식별됩니다.
2. 라우터는 네트워크의 모든 노드에 대한 상태 레코드 세트를 구축합니다. 레코드에는 세 개의 필드가 있습니다. 선행 필드 - 첫 번째 필드는 이전 노드를 표시합니다. 길이 필드 - 두 번째 필드는 소스에서 해당 노드까지의 가중치 합계를 표시합니다. 레이블 필드 - 마지막 필드는 노드의 상태를 보여줍니다. 각 노드는 "영구" 또는 "임시"와 같은 하나의 상태 모드를 가질 수 있습니다.
3. 라우터는 상태 레코드 세트의 매개변수(모든 노드에 대해)를 초기화하고 길이를 "무한대"로, 레이블을 "임시"로 설정합니다.
4. 라우터는 T-노드를 설정합니다. 예를 들어, V1이 소스 T-노드인 경우 라우터는 V1의 레이블을 "영구"로 변경합니다. 레이블이 "영구적"으로 변경되면 다시 변경되지 않습니다. T 노드는 에이전트일 뿐 그 이상은 아닙니다.
5. 라우터는 소스 T-노드에 직접 연결된 모든 임시 노드에 대한 상태 레코드 세트를 업데이트합니다.
6. 라우터는 모든 임시 노드를 살펴보고 V1에 대한 가중치가 가장 낮은 노드를 선택합니다. 해당 노드는 대상 T-노드입니다.
7. 이 노드가 V2(목적지)가 아니면 라우터는 5단계로 돌아간다.
8. 이 노드가 V2이면 라우터는 상태 레코드 집합에서 이전 노드를 추출하고 V1에 도달할 때까지 이를 수행합니다. 이 노드 목록은 V1에서 V2까지의 최적 경로를 보여줍니다.

1. 첫 번째 이미지에서 볼 수 있듯이 소스 노드(A)는 T-노드로 선택되어 레이블이 영구적입니다(채워진 원이 있는 영구 노드와 --> 기호가 있는 T-노드를 표시함).
2. 다음 단계에서는 T-노드(B, C)에 직접 연결된 임시 노드의 상태 레코드 집합이 변경되었음을 알 수 있습니다. 또한 B는 가중치가 적기 때문에 T-노드로 선택되었으며 레이블이 영구적으로 변경되었습니다(아래 참조).
3. 3단계에서는 2단계와 마찬가지로 T 노드(D, E)에 직접 연결되어 있는 임시 노드의 상태 레코드 집합이 변경되었습니다. 또한 D는 가중치가 적기 때문에 T-node로 선택되어 레이블이 영구적으로 변경되었습니다.
4. 4단계에서는 임시 노드가 없으므로 다음 T-노드만 식별합니다. E의 가중치가 가장 작기 때문에 T 노드로 선택되었습니다.

#define MAX_NODES 1024 /* 최대 노드 수 */
#define INFINITY 1000000000 /* 모든 최대 경로보다 큰 숫자 */
int n,dist[MAX_NODES][MAX_NODES]; /*dist[I][j]는 i에서 j까지의 거리 */
무효 shortest_path(int s,int t,int 경로[ ])
{struct state { /* 작업 중인 경로 */
int 전임자 ; /*이전 노드 */
int length /*소스에서 이 노드까지의 길이*/
enum {영구, 잠정} 레이블 /*레이블 상태*/
}상태[MAX_NODES];
int I, k, min;
구조체 상태 *
                     NS;
for (p=&state[0];p < &state[n];p++){ /*상태 초기화*/
p->전임자=-1
p->길이=INFINITY
p->라벨=임시;
}
상태[t].길이=0; 상태[t].label=영구적 ;
k=t ;                                                          
/*k는 초기 작업 노드입니다. */
하다{                                                            
/* k에서 더 나은 경로입니까? */
I=0인 경우; 나는 < n; 나++)                                       
/*이 그래프에는 n개의 노드가 있습니다 */
if (dist[k][I] !=0 && state[I].label==미정){
            if (상태[k].길이+거리[k][I] < 상태[I].길이){
		       state[I].predecessor=k;
		       상태[I].길이=상태[k].길이 + 거리[k][I]
		    }
}
/* 가장 작은 레이블을 가진 임시 레이블이 지정된 노드를 찾습니다. */
k=0;min=무한대;
(I=0;I < n;I++)
     if(상태[I].label==잠정 && 상태[I].length <
최소)=상태[I].길이;
     k=나;
	}
state[k].label=영구적
}동안(k!=s);
/*경로를 출력 배열로 복사*/
나는=0;k=0
Do{경로[I++]=k;k=state[k].predecessor;} 동안 (k > =0);
}

1. 직접 연결된 링크의 가중치를 계산하고 해당 테이블에 정보를 저장합니다.
2. 특정 시간 동안 자신의 테이블을 이웃 라우터(모든 라우터가 아님)로 보내고 각 이웃의 라우팅 테이블을 수신합니다.
3. 이웃의 라우팅 테이블에 있는 정보를 기반으로 자신의 라우팅 테이블을 업데이트합니다.

• 라우터 작동 방식
• 라우터 퀴즈
• 방화벽 작동 방식
• 인터넷 인프라 작동 방식
• LAN 스위치 작동 방식
• 홈 네트워킹 작동 방식
• 네트워크 주소 변환 작동 방식
• 패킷이란 무엇입니까?
• 사람들이 "컴퓨터 알고리즘"을 언급할 때 정확히 무엇을 말하는 것입니까?

• 인터넷 백과사전: 라우팅
• 라우팅 테이블
• 네트워크 라우팅
• 네트워크 계층
• 계층적 라우팅