다른 명령
새 문서: 상위 문서: Network Layer ==개요== ==각주== 분류:컴퓨터 네트워크 |
편집 요약 없음 |
||
| 2번째 줄: | 2번째 줄: | ||
==개요== | ==개요== | ||
라우팅 알고리즘(Routing algorithm)이란 송신 호스트에서 수신 호스트까지의 "좋은(good)" 경로(path)<ref>route라고도 한다.</ref>들을 결정하는 알고리즘을 의미한다. 경로란 패킷이 출발지 호스트에서 목적지 호스트까지 이동할 때 거치는 라우터들의 순서를 의미한다. 이때 "좋은" 경로의 기준은 가장 비용이 적거나(least "cost"), 가장 빠르거나("fastest"), 가장 혼잡하지 않은("least congested") 경로를 의미한다. | |||
==Network graph notation== | |||
[[파일:Abstract graph model of a computer network.png|대체글=Figure 1. Abstract graph model of a computer network|가운데|섬네일|'''Figure 1. Abstract graph model of a computer network''' ]] | |||
이때 라우팅 알고리즘은 figure 1과 같이 그래프를 사용하여 형식화된다. 그래프 G = (N, E)는 노드들의 집합 N과 간선(edge)들의 모음 E로 구성되며, 각 간선은 N에 속한 두 노드의 쌍이다. 이는 아래와 같이 나타내어 진다. | |||
N = set of routers = {u, v, w, x, y, z} | |||
E = set of links ={(u,v), (u,x), (v,x), (v,w), (x,w), (x,y), (w,y), (w,z), (y,z)} | |||
이때 그래프의 각 노드는 라우터를 의미하며, 간선은 해당 라우터들 간의 물리적인 링크(link)를 의미한다. 간선은 해당 링크의 비용을 나타내는 값을 가진다. 일반적으로 간선의 비용은 해당 링크의 물리적인 길이와 링크의 혼잡도 등에 의해 결정된다. 이때 각 간선과 경로의 비용은 다음과 같이 표기한다. | |||
(x, y) <math>\in</math> E, c(x,y) = cost of link (x,y) | |||
(x, y) <math>\notin</math> E, c(x,y) = <math>\infty</math> //해당 간선은 존재하지 않음 | |||
cost of path (x<sub>2</sub>, x<sub>2</sub>, x<sub>3</sub>, ⋯, x<sub>p</sub>) = c(x<sub>1</sub>,x<sub>2</sub>) + c(x<sub>2</sub>,x<sub>3</sub>) + ⋯ + c(x<sub>p-1</sub>,x<sub>p</sub>) | |||
==Routing algorithm classification== | |||
라우팅 알고리즘을 분류하는 한가지 방식은 중앙 집중형 라우팅 알고리즘(centralized routing algorithm)과 분산형 라우팅 알고리즘(decentralized routing algorithm)으로 구분하는 것이다. 라우팅 알고리즘을 분류하는 두 번째 방식은 그것이 정적(static)이냐 동적(dynamic)이냐에 따른 것이다. | |||
===Centralized vs. Decentralized=== | |||
중앙 집중형 라우팅 알고리즘은 '''네트워크에 대한 전체적이고 전역적인 정보(topology<ref>네트워크에서 장치들이 어떻게 연결되어 있는지를 나타내는 구조</ref>)를 이용하여 출발지와 목적지 간의 최소 비용 경로를 계산'''한다. 따라서 해당 알고리즘은 모든 노드 간의 연결 정보와 각각의 링크의 비용을 필요로 한다. 해당 알고리즘은 흔히 '''LS(link-state) 알고리즘'''이라고 불린다. | |||
분산형 라우팅 알고리즘은 각각의 라우터 들에 의해서 반복적이고 분산된 방식으로 수행된다. 이때 어떠한 노드도 전체 네트워크의 LS에 대한 완전한 정보를 가지고 있지 않다. 대신 각 노드는 자신에게 직접 연결된 링크들의 비용만 알고 있으므로, 각 노드는 이웃 노드들과의 정보 교환과 계산을 반복하여 최소 비용 경로를 점진적으로 계산한다. 해당 알고리즘은 흔히 DV(distance-vector) 알고리즘이라고 불린다. 왜냐하면 각 노드는 네트워크 내의 다른 모든 노드에 대한 비용의 추정치를 벡터 형태로 유지하기 때문이다. | |||
===Static vs. Dynamic=== | |||
정적 라우팅 알고리즘에서는 패킷의 경로가 시간에 따라 매우 느리게 변화하며, 보통 사람의 개입을 통해서 변경된다.<ref>예를 들면 사람이 직접 링크 비용을 편집하는 방식이다.</ref> 반면 동적 라우팅 알고리즘은 네트워크 트래픽 부하나 topology가 변할 때 라우팅 경로를 변경한다. 동적 알고리즘은 주기적으로 실행되거나 해당 변화에 직접적으로 반응하여 구현된다. 동적 알고리즘은 네트워크 변화에 더 잘 반응할 수 있지만, 라우팅 루프(routing loop)나 경로 진동(route oscillation) 같은 문제에 더 취약할 수 있다. | |||
==각주== | ==각주== | ||
[[분류:컴퓨터 네트워크]] | [[분류:컴퓨터 네트워크]] | ||
2025년 4월 30일 (수) 11:24 판
상위 문서: Network Layer
개요
라우팅 알고리즘(Routing algorithm)이란 송신 호스트에서 수신 호스트까지의 "좋은(good)" 경로(path)[1]들을 결정하는 알고리즘을 의미한다. 경로란 패킷이 출발지 호스트에서 목적지 호스트까지 이동할 때 거치는 라우터들의 순서를 의미한다. 이때 "좋은" 경로의 기준은 가장 비용이 적거나(least "cost"), 가장 빠르거나("fastest"), 가장 혼잡하지 않은("least congested") 경로를 의미한다.
Network graph notation
이때 라우팅 알고리즘은 figure 1과 같이 그래프를 사용하여 형식화된다. 그래프 G = (N, E)는 노드들의 집합 N과 간선(edge)들의 모음 E로 구성되며, 각 간선은 N에 속한 두 노드의 쌍이다. 이는 아래와 같이 나타내어 진다.
N = set of routers = {u, v, w, x, y, z}
E = set of links ={(u,v), (u,x), (v,x), (v,w), (x,w), (x,y), (w,y), (w,z), (y,z)}
이때 그래프의 각 노드는 라우터를 의미하며, 간선은 해당 라우터들 간의 물리적인 링크(link)를 의미한다. 간선은 해당 링크의 비용을 나타내는 값을 가진다. 일반적으로 간선의 비용은 해당 링크의 물리적인 길이와 링크의 혼잡도 등에 의해 결정된다. 이때 각 간선과 경로의 비용은 다음과 같이 표기한다.
(x, y) [math]\displaystyle{ \in }[/math] E, c(x,y) = cost of link (x,y) (x, y) [math]\displaystyle{ \notin }[/math] E, c(x,y) = [math]\displaystyle{ \infty }[/math] //해당 간선은 존재하지 않음 cost of path (x2, x2, x3, ⋯, xp) = c(x1,x2) + c(x2,x3) + ⋯ + c(xp-1,xp)
Routing algorithm classification
라우팅 알고리즘을 분류하는 한가지 방식은 중앙 집중형 라우팅 알고리즘(centralized routing algorithm)과 분산형 라우팅 알고리즘(decentralized routing algorithm)으로 구분하는 것이다. 라우팅 알고리즘을 분류하는 두 번째 방식은 그것이 정적(static)이냐 동적(dynamic)이냐에 따른 것이다.
Centralized vs. Decentralized
중앙 집중형 라우팅 알고리즘은 네트워크에 대한 전체적이고 전역적인 정보(topology[2])를 이용하여 출발지와 목적지 간의 최소 비용 경로를 계산한다. 따라서 해당 알고리즘은 모든 노드 간의 연결 정보와 각각의 링크의 비용을 필요로 한다. 해당 알고리즘은 흔히 LS(link-state) 알고리즘이라고 불린다.
분산형 라우팅 알고리즘은 각각의 라우터 들에 의해서 반복적이고 분산된 방식으로 수행된다. 이때 어떠한 노드도 전체 네트워크의 LS에 대한 완전한 정보를 가지고 있지 않다. 대신 각 노드는 자신에게 직접 연결된 링크들의 비용만 알고 있으므로, 각 노드는 이웃 노드들과의 정보 교환과 계산을 반복하여 최소 비용 경로를 점진적으로 계산한다. 해당 알고리즘은 흔히 DV(distance-vector) 알고리즘이라고 불린다. 왜냐하면 각 노드는 네트워크 내의 다른 모든 노드에 대한 비용의 추정치를 벡터 형태로 유지하기 때문이다.
Static vs. Dynamic
정적 라우팅 알고리즘에서는 패킷의 경로가 시간에 따라 매우 느리게 변화하며, 보통 사람의 개입을 통해서 변경된다.[3] 반면 동적 라우팅 알고리즘은 네트워크 트래픽 부하나 topology가 변할 때 라우팅 경로를 변경한다. 동적 알고리즘은 주기적으로 실행되거나 해당 변화에 직접적으로 반응하여 구현된다. 동적 알고리즘은 네트워크 변화에 더 잘 반응할 수 있지만, 라우팅 루프(routing loop)나 경로 진동(route oscillation) 같은 문제에 더 취약할 수 있다.