네트워크 계층–제어 평면(Control plane)
⤷단대단(end-to-end)연결을 할 때 출발지에서 목적지까지 내가 원하는 패킷(PDU)를 길을 찾아 연결을 해주는 것이 네트워크 계층의 가장 큰 역할이다. 그럴 때 네트워크 계층이 하는 일이 가장 최선의 길을 찾아줘야하는데 그때 길을 찾는 게 라우팅. 중간중간 라우터들은 라우팅을 통한 결과를 보고 누구한테 전달을 해줘야 하느냐, 포워딩. 이 두 개가 가장 중요한 역할이다.
-포워딩: 라우터의 입력에서 적절한 라우터 출력으로 패킷 이동 (데이터 평면에서 일어남)
-라우팅: 소스에서 목적지까지 패킷이 사용하는 경로 결정, 최단 경로 (제어 평면에서 일어남)
[네트워크 제어 평면을 구조화하는 두 가지 접근 방법]
라우터별 제어 (전통적) - 라우팅이 결정되는게 라우터마다 결정됨. 라우팅 테이블과 포워딩 테이블이 라우터마다 있는 것.
논리적으로 중앙 집중된 제어 (소프트웨어적으로 정의) - 논리적으로 집중된 컨트롤러가 포워딩 테이블을 작성하고 이를 각 라우터가 사용할 수 있도록 배포한 경우.
[라우터별 제어]
⤷각 라우터의 개별 라우팅 알고리즘 구성 요소는 제어 평면에서 상호작용하여 포워딩 테이블을 계산한다.
⤷각 라우터마다 라우팅 알고리즘을 따로 가지고 있다.
⤷라우팅 알고리즘이 라우팅 테이블을 만들어줌. 그래서 라우터가 비쌈.
<다익스트라 알고리즘 예시1>
⤷동그라미 표시 된 게 최단거리로 업데이트가 된다.
⤷12, y 이면 cost가 12고 z바로 앞에 있는게 y이다라는 뜻.
⤷N’에 모든 노드들 들어가고 반복이 끝나고 종료.
<다익스트라 알고리즘 예시2>
⤷예시 2의 u로부터 시작하는 최단 경로
⤷u가 가지는 포워딩 테이블. 다음에 누구한테 줘야하는지. u에서 w갈때는 먼저 x한테 가야하니까 (u,x)
[다익스트라 알고리즘 토론]
-> 찾아야 하는 노드의 총 수는
n(n+1)/2 이다.
-> 복잡도 :
->Oscillation 문제 (진동 문제)
⤷왔다 갔다 반복하는 것.
⤷우회도로가 막히니까 원래 막혔던 길로 다시 또 몰리는 것.
⤷진동 문제 해결 방법: 모든 라우터가 동시에 링크 상태 알고리즘을 실행하지 못하도록 하면 된다.
[거리 벡터 라우팅 알고리즘]
⤷링크 상태 알고리즘이 네트워크 전체 정보를 이용하는 알고리즘인 반면
⤷거리 벡터 알고리즘은 반복적이고 비동기적이며 분산적이다. (독립적으로 동작)
⤷피보나치 개념! 메모리 사용량도 줄고 처리 속도도 빨라진다. (동적, dynamic)
<벨만-포드 식> - dynamic programming
⤷x : 출발지
⤷y : 목적지
⤷노드 x부터 y까지 최소 비용 경로의 비용
⤷출발지가 새로 생기면 이전에 찾은 최단 경로에 새로 생긴 출발지의 최단 경로를 더하면 된다.
⤷내 주변에 나하고 연결된 애의 정보만 알고 있으면 된다. 데이터양이 적다는 말. 대신 그걸 받아서 전파하는 데 오래 걸린다.
⤷만약 이 업데이트로 인해 노드 x의 거리 벡터가 변경된다면 노드 x는 이 수정된 거리 벡터를 자신의 이웃들에게 보내고 그에 따라 이웃들도 자신의 거리 벡터를 수정한다.
⤷모든 노드가 자신의 거리 벡터를 비동기적으로 교환하는 동작을 계속하다 보면 비용 추정값 Dx(Y)는 노드x에서 y까지의 실제 최소 비용 경로의 비용으로 수렴한다.
⤷거리 벡터 알고리즘에서는 어떤 노드 x가 자신에게 직접 연결된 링크 중 하나의 비용이 변경된 사실을 알게 되거나 어떤 이웃으로부터 변경된 거리 벡터를 수신했을 때 자신의 거리 벡터 추정값을 업데이트한다.
⤷DV에서 노드 x는 나하고 연결된 이웃들과의 비용을 알고 있다. C(x, y)
⤷나하고 연결된 v가 목적지가 y일 때 v에서 y로 연결되는 최단 경로 값을 알아야 한다.
⤷거리 벡터 알고리즘의 아이디어는 때때로 각 노드는 이웃들에게 자신의 거리 벡터 값을 보낸다.
⤷그리고 x가 이웃으로부터 새로운 DV 추정치를 받으면 벨만-포드 식을 사용하여 자체 DV를 업데이트 한다.
⤷최소가 되는 v를 찾는다.
-> DV 알고리즘은 분산적이고 전체 정보를 사용하지 않는다.
⤷하나의 노드가 가지는 정보는 단지 자신에게 직접 연결된 이웃으로의 링크 비용과 그 이웃들로부터 수신하는 정보뿐이다.
⤷알고리즘 동작은 동기적 방식이다.
⤷즉, 모든 노드가 동시에 이웃에게서 거리 벡터를 받고 새로운 거리 벡터를 계산해서 변화가 있다면 그들의 이웃에게 알린다.
⤷recompute, 최단 경로를 다시 계산.
⤷x에서 z까지 가는데 아까는 7이었는데 3이면 충분해서 업데이트됨.
⤷바뀐 파트만 업데이트.
⤷t0 : y는 링크 비용 변경을 감지하고 DV를 업데이트하며 이웃에게 알린다.
⤷t1 : z는 y로부터 업데이트를 받고, 테이블을 업데이트하고, x에 대한 새로운 최소 비용을 계산하고, 이웃에게 DV를 보낸다.
⤷t2 : y는 z의 업데이트를 수신하고 거리 테이블을 업데이트한다. y의 최소 비용은 변경되지 않으므로 y는 z에게 메시지를 보내지 않는다. 알고리즘은 정지상태가 된다.
⤷책 356p
⤷아직 z는 4가 60으로 바뀌었다는 걸 모름.
y가 z로 가면 z가 다시 y로 경로 설정을 함.
=> 라우팅 루프 발생.
⤷경로 비용 값이 50 될 때까지
즉, 이 루프를 알고리즘이 안정화될 때까지 44번 반복을 한다.
⤷만약 60이 아닌 4에서 10,000으로 바뀜
=> 무한 계수 문제
이런 문제를 막기 위해
포이즌 리버스 (poisoned reverse)를 추가한다.
⤷만약 z가 y를 통해서 목적지 x로 가는 경로 설정을 했다면 z는 y에게 x까지의 거리가 무한대라고 알린다.
⤷z는 y를 통과해서 x로 가는 동안은 이런 선의의 거짓말을 계속한다.
⤷y는 z에서 x로 가는 경로가 없다고 믿으므로 z가 계속해서 거짓말을 하면서 y를 통해 x로 가는 경로를 사용하는 동안은 y는 z를 통해 x로 가는 경로를 시도하지 않을 것이다.
-> 하지만 포이즌 리버스는 세 개 이상의 노드를 포함한 루프는 포이즌 리버스 스스로는 감지할 수 없다. (모든 무한 계수 문제를 해결할 수는 없음.)
[링크 상태(LS)와 거리 벡터(DV) 알고리즘의 비교]
[LS]
⤷전체 정보를 필요로 한다.
[DV]
⤷각 노드는 오직 직접 연결된 이웃과만 메시지를 교환한다.
⤷자신으로부터 네트워크 내 모든 노드들로의 최소 비용 추정값을 이웃들에게 제공한다.
⤷좋은 소식은 빨리 전파되는데
나쁜 소식은 루프가 생긴다든지 느리다.
메시지 복잡성
(LS)
⤷ 각 노드는 네트워크 내 각 링크 비용을 알아야 한다. O(nE)개의 메시지가 전송되어야 함.
⤷링크 비용이 변할 때마다 새로운 링크 비용이 모든 노드에게 전달되어야 한다.
(DV)
⤷매번 반복마다 직접 연결된 이웃끼리 메시지를 교환한다.
⤷링크 비용이 변하고 이 새로운 링크 비용이 이 링크에 연결된 어떤 노드의 최소 비용 경로에 변화를 준 경우에만 DV알고리즘은 수정된 링크 비용을 전파한다.
수렴 속도
(LS)
⤷O(n2)의 복잡도를 가진다.
(DV)
⤷천천히 수렴하고 알고리즘이 수렴하는 동안 라우팅 루프가 발생할 수 있다. 또한 무한 계수 문제가 일어날 수 있다.
견고성 : 망가졌을 때
(LS)
⤷라우터는 연결된 링크에 대해서 잘못된 비용 정보를 브로드캐스트 할 수 있다.
⤷노드는 전송된 링크 상태 브로드캐스트 부분을 변질시키거나 폐기할 수 있다.
⤷하지만 각 링크 상태 노드는 자신의 포워딩 테이블만 계산하고 다른 노드들도 유사한 계산을 수행한다. 이는 경로 계산이 어느 정도 분산되어 수행됨을 의미하고 어느 정도의 견고성을 제공한다.
(DV)
⤷노드는 잘못된 최소 비용 경로를 어떤 혹은 모든 목적지에 알릴 수 있다.
⤷각 반복마다 한 노드의 거리 벡터 계산이 이웃에게 전달되고 다음 반복에서 이웃의 이웃에게 간접적으로 전달된다.
⤷잘못된 계산이 전체로 확산될 수 있다.
[논리적으로 중앙 집중된 제어]
⤷고유한 (일반적으로 원격) 컨트롤러가 라우터의 로컬 CA(제어 에이전트)와 상호 작용하여 전달 테이블을 계산한다.
⤷컨트롤러는 포워딩 테이블만 처리함.
⤷더이상 개별로 라우팅 알고리즘이 필요없음.
⤷각 라우터에 컨트롤 에이전트가 존재.
⤷자원이 줄어들어도 되는 장점이 있다.
⤷컨트롤러는 각 CA와 상호작용하여 라우터의 플로우 테이블을 구성 및 관리한다.
⤷CA는 컨트롤러와 통신하고 컨트롤러의 명령을 수행하는 최소한의 기능만 가진다.
- 저 컨트롤러를 ‘SDN컨트롤러’라고 한다.
- 통신하는걸 ‘open flow’라고 한다.
⤷라우터들이 훨씬 simple 해짐.
⤷라우터 장비가 훨씬 저렴해지고 기능이 줄어들었다.
[라우팅 프로토콜]
link state
distance vector
⤷라우팅 프로토콜의 목적: 송신자부터 수신자까지 라우터의 네트워크를 통과하는 좋은 경로를 결정하는 것이다. 일반적으로 좋은 경로란 최소 비용 경로를 말한다. 혼잡하지 않고 가장 빠른 길.
[네트워크의 그래프 표현]
그래프는 노드와 에지로 이루어진다.
⤷에지는 그 비용을 나타내는 값을 가진다.
이 비용은 일반적으로 해당 링크의 물리적인 거리, 링크 속도, 링크와 관련된 금전 비용 등을 반영한다.
⤷W와 Z의 cost는
C(W,Z) = 5 이렇게 표현한다.
⤷출발지에서 목적지까지 가는 cost를 나타낸 것. = 전체 cost
=> 출발지 U에서 목적지 Z까지 가는 가장 비용이 적은 경로는 무엇인가?
⤷최단 비용을 찾는게 라우팅 알고리즘.
[라우팅 알고리즘]
⤷1. 라우팅에 필요한 정보들을 라우터간에 공유해야 하는데 그 정보가 똑같이 전역적으로 받느냐(global) 나와 이웃한 노드의 정보만 가지고 있을 거냐(decentralized)
<중앙 집중형 라우팅 알고리즘> (global)
- 링크 상태 알고리즘
⤷연결과 링크 비용에 대한 완전한 정보를 가진다.
⤷전체 상태 정보를 가지는 알고리즘
⤷이 알고리즘은 네트워크 내 각 링크의 비용을 알고 있어야 한다.
<분산 라우팅 알고리즘> (decentralized)
- 거리 벡터 알고리즘
⤷최소 비용 경로의 계산이 라우터들에 의해 반복적이고 분산된 방식으로 수행된다.
⤷어떤 노드도 모든 링크의 비용에 대한 완전한 정보를 갖고 있지 않다. 대신 각 노드는 자신에 직접 연결된 링크에 대한 비용 정보만을 가지고 시작한다.
⤷이후 반복된 계산과 이웃 노드와의 정보 교환을 통해 노드는 점차적으로 목적지까지의 최소 비용 경로를 계산한다.
⤷각 노드가 네트워크 내 모든 다른 노드까지 비용(거리)의 추정값을 벡터 형태로 유지한다.
2. 정보를 가지고 있는 게 정적이냐 동적이냐
<정적 라우팅 알고리즘> (static)
⤷경로가 아주 느리게 변한다.
<동적 라우팅 알고리즘> (dynamic)
⤷네트워크 트래픽 부하나 토폴로지 변화에 따라 라우팅 경로를 바꾼다.
⤷주기적으로 혹은 토폴로지나 링크 비용의 변경에 직접적으로 응답하는 방식으로 수행된다.
⤷동적 라우팅 알고리즘은 네트워크 변화에 빠르게 대응할 수 있지만 경로의 루프나 경로 진동과 같은 문제에 더 취약하다.
[링크 상태 알고리즘, link state]
= 다익스트라 알고리즘
⤷모든 노드들은 네트워크 토폴리지(노드와 에지, cost 정보)들을 다 알고 있다는 것.
⤷각 노드들의 링크 cost를 다 알고 있다.
⤷링크 상태를 나말고 다른 애들한테 다 뿌리는거임.
⤷모든 노드는 같은 정보를 갖게 된다.
⤷그래서 중앙 집중형이다. (global)
⤷하나의 노드에서 네트워크 내 모든 다른 노드로의 최소 비용 경로를 계산한다.
⤷계산한 다음 각 노드별로 포워딩 테이블을 만들어준다. 다음에 누구한테 전달해 줄지.
⤷이 다익스트라 알고리즘은 반복적이고 알고리즘의 k번째 반복 이후에는 k개의 목적지 노드에 대해 최소 비용 경로가 알려지며 이 k개의 경로는 모든 목적지 노드로의 최소 비용 경로 중에서 가장 적은 비용을 갖는 k개의 경로이다.
- N : 노드
- E : 에지
C : 비용(cost)
C(x, y): 노드 x에서 y로 가는 비용
D(v) : 알고리즘의 현재 반복 시점에서 출발지 노드부터 목적지 v까지의 최소 비용 경로의 비용
p(v) : 출발지에서 v까지의 현재 최소 비용 경로에서 v의 직전 노드 (v의 이웃)
N’ : 노드의 집합. 출발지에서 v까지의 최소 비용 경로가 명확히 알려져 있다면 v는 N’에 포함된다.
⤷11번째 줄
: u에서 v까지 가는 길이 w가 새롭게 추가 됐는데 u에서 w로, w에서 v까지 가는 길을 비교해서 두 개 중에 최단 값이 v가 되라는 말이다.
⤷N’에 모든 노드가 들어갈 때까지 반복.