Routing Algorithms 문서 원본 보기

상위 문서: [[Network Layer]]

==개요==
라우팅 알고리즘(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) 같은 문제에 더 취약할 수 있다.

==각주==
[[분류:컴퓨터 네트워크]]