Routing Algorithm
Routing algorithms
- routing algorithm은 네트워크에서 end-end 경로를 결정한다
- forwarding table은 라우터에서 local forwarding을 결정한다.
그래프와 트리 차이
- 그래프는 cycling
- 트리는 acycling
다익스트라와 벨만포드 차이
- 다익스트라: 가중치는 항상 양수
- 벨만포드: 음의 가중치가 가능
Routing algorithm classification
- Q: global or decentralized information?
- global:
- 모든 라우터가 완벽한 topology와 link cost 정보를 가진다.
- "link state" 알고리즘
- decentralized:
- 라우터는 물리적으로 연결된 이웃과, 그 이웃까지의 link cost를 안다
- 이웃과 정보를 교환하며 반복 계산 과정을 거친다
- "distance vector" algorithm
- global:
- Q: static or dynamic?
- static:
- 시간이 지남에 따라 경로가 느리게 변화
- 라우터 포워딩 테이블을 직접 수정해야 함
- dynamic:
- 빠르게 경로가 변화
- 정기적인 업데이트
- link cost 변경에 대한 응답
- 빠르게 경로가 변화
- static:
Link-State Routing Algorithm
- 다익스트라(Dijkstra) 알고리즘
- 모든 노드에게 net topology와 link costs 정보가 알려짐
- "link state broadcasting"을 통해 알려짐
- 모든 노드들은 같은 정보를 갖는다
- 하나의 노드(출발지)에서 다른 노드(도착지)까지 최소 비용 경로를 연산한다.
- 해당 노드들에 대해 포워딩 테이블을 제공
- k번 반복 연산 후, k까지 가는 최소 비용 경로를 알게 됨
- 모든 노드에게 net topology와 link costs 정보가 알려짐
- notation:
- C(x,y): x에서 y로의 link cost
- 만약 바로 갈 수 있는 노드가 아니라면 ∞
- D(v): 출발지에서 목적지까지 경로의 cost (현재까지 계산한 cost)
- P(v): 출발지에서 경로로의 v까지의 경로에서 v의 이전 노드
- N': 최소 비용 경로로 정의된 노드들의 집합
- C(x,y): x에서 y로의 link cost
다익스트라 알고리즘의 complexity
- n개의 노드가 있을 때, 모든 노드를 확인해야한다. -> n(n+1)/2번의 비교가 필요하므로 O(n2�2)의 복잡도를 가진다.
- 더 효율적으로 구현하면 O(nlogn)이 가능하다.
Distance vector algorithm
- 벨만 포드 알고리즘 (dynamic programming)
- dx(y): x에서 y까지의 최소 비용 경로의 cost
- dx(y)) = minv����{c(x,v)+dv(y)��(�)}
![[Pasted image 20231214094958.png]]
- key idea:
- 자신의 distance vector estimate를 이웃들에게 보낸다.
- x가 이웃으로부터 새로운 DV를 받으면, B-F equation을 이용하여 자신의 DV를 업데이트한다.
- Dx(y) ← min{c(x,v) + Dv(y)} for each node y ∊ N
- 추정한 Dx(y)��(�)는 실제 최소 비용인 dx(y)��(�)에 수렴한다.
- iterative, asynchronous:
- local link cost가 바뀔때 local iteration이 발생
- 이웃으로부터 DV 업데이트 메시지 받으면 업데이트
- distributed:
- 각 노드들은 자신의 DV가 변경될 때 이웃에게 알림
![[Pasted image 20231214095005.png]]
- Distance vector: link cost changes
- link cost가 감소한 경우 업데이트가 빠름
- t0�0: y가 link cost 변화를 탐지하고 자신의 DV를 업데이트한 후, 이웃들에게 이를 알림
- t1�1: z가 y로부터 업데이트 정보를 받고, 자신의 테이블을 업데이트. x로의 최소 비용을 업데이트 한 후, 이웃들에게 자신의 DV 보냄
- t2�2: y가 z로부터 업데이트된 정보로를 받고, 자신의 테이블을 업데이트. y의 최소 비용 테이블은 변하지 않았으므로 z에게 메시지를 보내지 않음 => 업데이트 끝!
- link cost가 증가한 경우는 업데이트가 느림
- z가 x로 갈 때, y를 통한 경로보다 x로 바로 가는 것이 cheap하다는 것을 깨달을 때까지 44번의 반복이 발생 -> 'count to infinity' 문제
- poinson reverse를 이용해 문제 해결
- link cost가 감소한 경우 업데이트가 빠름
- Distance vector: poisoned reverse
- 만약 Z가 X를 얻기 위해 Y를 통해 간다면:
- z에서 y 거리를 ∞ 주고 업데이트 하도록 함
- 즉, 업데이트된 곳 반대를 ∞로 설정해주고 업데이트하면 빠름
- poisoned reverse가 infinity problem을 대부분 해결하기는 하나, 세 개 이상의 이웃 노드를 포함한 루프인 경우 감지하지 못한다.
- 만약 Z가 X를 얻기 위해 Y를 통해 간다면:
LS와 DV 알고리즘 비교
- message complexity
- LS: 노드가 n개, 링크가 E개일 때 O(nE)
- DV: 이웃끼리만 메시지 교환
- 수렴 속도
- LS: O(n2�2)
- DV: 수렴 속도 다양
- 라우팅 루프 발생 가능
- count to infinity problem 발생 가능
Hierarchical routing
- 6억개의 목적지가 있다면?
- 모든 목적지를 라우팅 테이블에 저장할 수 없음
- 라우팅 테이블의 변경은 링크를 벅차게 함
- administrative autonomy
- internet = network of networks
- 각 네트워크 admin은 자신의 네트워크 내에서 라우팅을 컨트롤하기를 원한다.
- 라우터를 영역으로 통합, "autonomous systems(AS)"
- AS: LG U+, SK, KT 같은 거
- 같은 AS 내의 라우터는 같은 라우팅 알고리즘을 사용
- "intra-AS" 라우팅 프로토콜
- 다른 AS에 있는 라우터는 다른 intra-AS 라우팅 프로토콜을 사용
- gateway router:
- 다른 AS의 라우터에 링크를 가짐 (직접 연결됨)
- 자신의 AS의 "edge"
Interconnected ASes
- 포워딩 테이블은 intra-AS와 inter-AS 라우팅 알고리즘에 의해 설정된다.
- intra-AS은 내부 목적지 엔트리를 설정하고
- inter-AS & intra-AS는 외부 목적지 엔트리를 설정한다.
Routing int the Internet
Intra-AS Routing
- interior gateway protocols (IGP)라고도 알려짐
- 대부분의 흔한 intra-AS 라우팅 프로토콜:
- RIP: Routing Information Protocol
- OSPF: Open Shortest Path First => 빠르고 정확
- IGRP: Interior Gateway Routing Protocol
RIP
- distance vector algorithm
- 이웃의 더 좋은 정보를 이용하여 업데이트
- RIP table processing
- RIP 라우팅 테이블은 route-d라 불리는 application 계층 프로세스에 의해 관리된다.
- advertisement는 주기적으로 반복해서 UDP 패킷을 보냄
OSPF
- link state 알고리즘 이용 -> 다익스트라 알고리즘으로 경로 연산
- OSPF advertisement는 이웃 당 하나의 엔트리를 전달
- advertisements는 전체 AS에게 flood
- TCP나 UDP 대신에 IP로 직접 OSPF 메시지 전달
- IS-IS routing protocol: OSPF와 거의 동일
- OSPF "advanced" features (not in RIP)
- security: 모든 OSPF 메시지는 인증됨(authenticated) -> 악의적인 침입을 막기 위해
- 여러개의 같은 cost 경로를 허용 (RIP는 하나의 경로만 허용)
- cost가 같은 경로 여러개이면 나눠서 보냄 => 속도↑
- 각 link에 대해 서로 다른 TOS에 대한 여러 cost 행렬 (예: best effort ToS에 대해 낮음으로 설정된 위성 링크 비용, 실시간 ToS에 대해 높음)
- 통합된 uni-cast 와 multicast 지원:
- Multicast OSPF (MOSPF)는 OSPF 기반의 동일한 토포로지 데이터를 사용한다
- 계층적인 OSPF in large domains.
Hierarchical OSPF
- two-level hierarchy: local area, backbone.
- link-state advertisements는 영역 안에서만 일어남
- 각 노드에는 자세한 영역 토폴로지가 있다.
- 다른 지역은 net로 가는 방향(최단 경로)만 안다
- area border routers: 자신의 영역 안의 nets까지의 거리를 요약하여 다른 영역 경계 라우터에게 알린다.
- backbone routers: 백본으로 제한된 OSPF 라우팅을 실행
- boundary routers: 다른 AS에 연결
Internet inter-AS routing: BGP
- BGP(Border Gateway Protocol):
Broadcast and multicast routing
- 출발지에서 모든 다른 노드에게 패킷 전달
- source 중복은 비효율적:
- source duplication: 어떻게 출발지는 수령자 주소를 결정하는가?
In-network duplication
- flooding: 노드가 broadcast 패킷을 받으면, 카피본을 모든 이웃에게 보낸다.
- 문제: cycles & broadcast storm
- controlled flooding: 전에 같은 패킷을 broadcast한 적이 없는 경우에만 패킷을 broadcast한다.
- 노드는 이미 broadcast한 패킷의 트랙을 저장한다.
- 또는 reverse path forwarding (RPF): 출발지와 노드 사이의 최단 경로에 도달한 경우에만 패킷 forward
- spanning tree:
- 어떤 노드로부터 중복된 패킷을 받지 않는다.
-
broadcasting: 나와 이전에 보낸 사람 제외하고 보냄 = controlled flooding
-
flooding: 나를 제외한 나머지한테 보냄
Spanning tree
- 먼저 spanning tree 구성
- 노드는 스패닝 트리를 따라서만 카피하고 forward한다.
Multicast routing: problem statement
- local multicast group members를 가지는 라우터를 연결하는 트리를 찾는다
- tree: 사용하는 라우터 사이에 모든 경로가 아니다
- shared-tree: 모든 그룹 구성원이 사용하는 같은 트리
- source-based: 송신자에서 수신자로의 다른 트리
Internet inter-AS routing: BGP
BGP
inter-AS routing으로 널리 사용되는 protocol이다. 전체 인터넷을 하나로 붙여주는 역할을 한다.
BGP는 두가지 타입이 있다.
- eBGP : 이웃 AS 간에 도달할 수 있는가 등에 대한 정보들을 이웃AS끼리 주고받는 것이다.
- iBGP : 한 AS 내부에서 어디에 갈 수 있는가 등에 대한 정보들을 내부에서 전파하는 것이다.
BGP를 통해서 인터넷 전체에 "나 여기 있어"라고 나의 존재에 대해 알릴 수 있다.
1c - 2a 와 2c - 3a 가 서로 메시지를 주고 받아서 연결을 만들었다. 이웃 AS간에 연결이 만들어졌는데, 이것을 만드는 것이 eBGP에서 하는 것이다.
1c 입장에서는 2a가 내게 연결되었다는 사실을 AS1 내부에 공유할 필요가 있다. 그래야 내부에서 외부로 나가는 어떤 데이터를 받았을 때 1c 라우터를 통해 밖으로 내보낼 수 있다는 것을 알 수 있기 때문이다. AS 내부에서 하는 것이 iBGP에서 하는 것이다.
BGP session : 두개의 BGP 라우터가 semi-permanent TCP connection을 통해서 서로 메시지를 교환하는 것. 이것을 통해 다른 destination으로 가는 경로를 advertising할 수 있다.
BGP**를 "path vector"라고도 한다. 아래 예시를 보자.**
X라는 네트워크가 3d에 붙은 상황이다. 그러면 3d는 X하고 붙었다고 iBGP를 통해서 내부에 broadcast한다. 3a가 이를 받고, 3a는 2c에게 AS3는 X하고 연결되어 있다고 알려준다. (AS3,X) 즉, 3a는 2c에게 X로 데이터를 forward할 수 있다고 약속하는 것이다.
Path attributes
내가 붙어있는 것에 대한 속성에 대해서 하나의 route를 형성하게 된다. 그래서 이 속성에는 두가지 종류가 있다.
1. AS-PATH : prefix advertisement하는 것을 통해서 AS들의 list가 붙는 것.
2. NEXT-HOP : 어떤 특정 내부의 AS 라우터가 그 다음 HOP AS로 간다는 정보.
Policy-based routing
어떤 route에 대한 advertisement를 gateway가 받았을 때, 이 path를 수용할 건지 policy를 가지고 결정할 수 있다**. (이 prefix를 붙일지 안붙일지. 붙여서 알릴지 말지.) AS policy**를 통해서 다른 이웃한 AS로 가는 path를 전달할 건지 결정하게 된다. (policy에 대해선 뒤에서 배울 것임)
BGP path advertisement
X가 AS3에 붙은 상황이다.
3a는 X와 연결되었다는 정보(AS3,X)를 2c에게 알려주고 2c는 이를 받는다. AS2는 AS2 policy를 가지고 이것을 받아서 X로 가는 경로를 AS2 내부에 퍼트릴지 말지 결정한다. 퍼트린다고 하면 AS2 routers는 AS3,X를 accept한다.
그러면 같은 policy를 가지고 2a는 이것을 다른 AS에게 보낼지 말지 결정한다. 결정되면은 바깥에 advertise를 한다. 그래서 AS2,AS3,X를 전파한다. 경로를 하나씩 붙여나가는 것이다. AS1은 X로 보내는 데이터는 우선 AS2로 보내면 되겠다고 알게 된다.
AS1에서 AS3로 가는 길이 있는 경우. 1c 입장에서는 X로 가는 경로를 AS2와 AS3로부터 받아 X로 가는 경로가 두개가 있다. AS2와 AS3로부터 정보를 받았다. 둘 중에 어느 경로로 보낼까? 1c는 어떤 경로를 선택해서 iBGP를 통해 내부에 알린다. 자세한 것은 뒤에서 배운다.
BGP message
BGP message는 TCP로 라우터들 간에 연결되어 있다**.** BGP message**에는 네가지 타입이 있다.**
- OPEN : TCP conntection을 open하는 메시지. 다른 라우터와 연결하게 되는 경우, 상호 인증을 하게 된다.
- UPDATE : 새로운 path에 대한 advertise를 업데이트라는 메시지를 통해 전달된다.
- KEEPALIVE : 업데이트가 없는 경우에 서로 주고받는게 없다면, 서로 살아있는지 죽어있는지 알 수가 없다. 그래서 서로 살아있다는 사실을 주기적으로 가끔 메시지를 보내서 알려준다.
- NOTIFICATION : 이런 메시지를 보냈는데 에러가 나거나, connection을 닫을 때 사용한다.
BGP & OSPF
BGP, OSPF**가 적용됐을 때 forwarding table entries를 살펴보자.**
1a, 1b, 1d는 전부 X로 가는 경로를 1c를 통해 알게 된다.(iBGP). 1d에서 OSPF를 통해 X로 가려면 1번 인터페이스로 가는 것이 기록되어 있다. 1a는 X로 가는 것은 2로 가면 된다는 table이 있다.
그 다음 경로 선택을 BGP에서는 어떻게 해줄까? 복수의 경로가 있는데 어느 경로를 선택할까. 이것은 여러가지 기술로 가능하다.
1. 어떤 policy를 가지고 결정한다. 내부 policy를 만들어서 이 규칙으로 결정한다.
2. 가장 가까운 AS-PATH를 통해 간다.
3, hot potato routing이라고 해서 자신의 AS를 기준으로 가장 빠른 경로로 결정되는 것.
4. 다른 추가적인 기준을 가지고 할 수 있다. 기타 등등..
Hot Potato Routing
AS1**과 AS3로부터 X의 연결 정보를 받는 상황.**
2d는 2a와 2c로부터 정보를 받아, 2d는 2a와 2c 양쪽으로 보내도 된다는 것을 알게 된다. Hot Potato Routing에서는 자신의 라우터를 기준으로 적은 cost의 길을 선택한다. 여기선 2a의 cost가 적으니 2a에게 보내게 된다. 그러면 최종 경로는 2d-2a-1c-3a-3d-X 가 된다.
뜨거운 감자를 손에 쥐면 빨리 내던지게 된다. 이것과 같은 원리로 2d도 빨리 내던져야 하는데, 일단 cost가 가장 적은 2a한테 던져버리는 것이다.
BGP : Policy
A는 w와 연결되어 있다는 것을 B,C에게 알려준다. (Aw). 그러면 B,C는 w한테 가기 위해선 A한테 가면 되겠다는 것을 알게 된다.
B**는 BAw라는 것을 C한테 알려줄 수도 있는데, 이것을 advertise하지 않도록 정할 수 있다**. B는 B의 customer만 서비스해주면 되는데, 내가 왜 남의 customer까지 라우팅 해 줄 필요가 없다는 policy를 가질 수 있다. 그래서 이 policy에 의해서 B는 전파를 하지 않는다.
그러면 C는 CBAw라는 path가 있는지 알지 못한다. 물리적으로 연결되어 있지만, 경로를 알지 못한다. B가 전파하지 않아도 라우팅에는 문제가 되지 않는다. C는 CAw를 알고 있기 때문이다.
policy**는 inter-AS 간에 유효한 것이다. 자기를 통과하는 것에 대한 control을 어떻게 해줄것인지에 대해 inter-AS간에 policy를 통해서 control할 수 있다**. intra-AS**는 같은 서비스 사업자가 하기 때문에 이런 policy에 대해 필요가 없다**.
inter-AS와 intra-AS routing이 구분되어 있기 때문에 scale문제. 즉 table size가 너무 커지는 것을 해결할 수 있게 되었다. hierarchical routing. 구분해서 라우팅 해놨기 때문에 업데이트가 되었을 때의 오버헤드를 줄일 수 있다.
performance 측면에서도 intra-AS는 내부에서 performace만 가지고 하면 된다. inter-AS는 performance는 모르겠고, policy로 결정한다. 어차피 inter-AS는 AS 간에 라우팅이기 때문에 performance를 같이 해줄 이유가 없다.
