5.1 Routing Algroithms
goal: good path 찾기(비용 적고, 빠르고, 혼잡 적은)
일반적으로 good이라 함은 최소비용경로 or 가장 짧은 경로
cost 정의 방식
- fixed: link의 bw나 error rate 보고 정함
- variable: 혼잡도 보고 정함(라우팅 꼬일까봐 잘 안씀)
cost of path(X1,X2,...Xn)=C(X1,X2)+...C(Xp-1+,Xp)
※C(X1,X2)는 X1,X2잇는 링크의 cost. 링크가 없거나 망가졌으면 ∞
Routing algorithm classification
global or decentralized information?
global: 모든 라우터가 전체정보를 알고 있다. Link State(LS)알고리즘 사용.
ex) OSPF
decentralized: 직접 연결된 길만 알고, 나머지는 이웃에게 소문을 들어 알아냄. 반복계산+정보교환으로 정보 알아냄. Distance Vector(DV 알고리즘 사용)
ex) RIP, BGP
static or dynamic?
static: 수동. 늦게 반영
dynamic: 라우터가 네트워크 변화를 빨리 감지. 이 장에서 배우는 라우팅 프로토콜은 dynamic임
load-sensitive or load-insensitive?
load-sensitive: 실시간 감지. 혼잡 링크에 높은 비용
load-insensitive: 항상 고정된 값. 이 장에서 배우는 라우팅 프로토콜은 load-insensitive임
5.2 Routing algorithm classification
A Link State Routing Algorithm: Dijkstra's Algorithm
다익스트라 알고리즘
D(q)=min(D(q),D(A)+C(A,q))
※D(q): 목적지 q까지의 최소경로비용
모든 노드가 complete nw 토플로지 정보 알고 있음.
global dynamic routing: global하게 정보를 주고 문제가 생기면 알려주어 rerouting.
used in OSPF
다익스트라 알고리즘의 문제점: oscillation(진동) 문제
Distance Vector Algorithm: Bellman-Ford Algorithm
벨만포드 알고리즘
dx(y)=min{C(x,v)+dv(y)}
dx(y): x~y까지의 최소경로비용
C(x,v): x~v 링크 코스트(내가 아는값)
dv(y): 이웃이 알려준, d~y까지의 최소비용경로
small nw에서 많이 사용
used in RIP
DV algorithm
iterative, a synchronous, distribute
더이상 정보교환 안할때까지 지속 → 반복적
모든 노드가 서로 정확히 맞물릴 필요 없음 → 비동기적
(wait →이웃에게 정보 받음 → recompute →이웃에게 notify → wait) 하는 과정 → 분산적
RIP은 30초마다 노드 갱신, BGP는 ISP 단위로 작동하기때문에 바뀌었을때만 갱신
DV: link cost changes
좋은 뉴스는 빨리 착. 나쁜 뉴스는 늦게 도착(count to infinity)
DV 알고리즘의 단점: count to infinity
count to infinity 해결법1- split horizon
A는 B가 알려준 'C까지 가는 경로'를 다시 B에게 알려주지 않는다. B가 착각해서 블랙홀 빠지지 않도록...상대방한테 얻은 정보는 다시 그 상대한테 알려주지 않기!
count to infinity 해결법2- split horizon with poisoned reverse
알려주되, ∞를 이용하여 너한테 얻은 정보라는 것도 알려주자!
Z-Y-X 로 연결되어있을때...
Z: Y야. Dz(X)=∞란다.
Y: Z야 너는 X로 가는 정보를 나한테 얻었구나? 알았어~ x로 갈때 너를 통해서 가는 루트는 시도 안할게~
😰하지만 이 방법들로도 모든 블랙홀을 방지할 순 없다. 3개 이상의 node가 연관된 루프면 해결할 수 없기 때문...
→ 그래서 RIP은 3개 이상의 라우터를 직접 연결하지 않고, BGP는 루프 알수 있도록 거쳐오는 라우터 정보들을 다 적는다.
DV vs LV
Hierarchical routing
ip 주소들이 많아서 주소들이 hierarchical하게 할당됨 → aggregation해서 라우팅 정보 올라가기도!
region들을 적당히 묶어서 하나의 AS로 운영한다. 어떤 정책 쓸지는 자율이지만, 하나의 AS안에 있는 라우터들은 같은 프로토콜 사용한다: intra-AS routing protocol
intra-AS routing protocol: OSPF, RIP
ASN: 32 bit integer AS Number
라우터당 하나씩 주는 number. 어떤 AS에 속하는 라우터인지 파악 가능
gateway 라우터
AS의 경계에 있고 다른 AS의 라우터로 가는 링크가 있는 라우터. inter as routing protocol 돌린다.
inter as routing protocol: BGP. policy based routing
AS의 종류
- transit AS: 어떤 AS를 통과해서 다른 AS로 갈 수 있음
- stub AS: 하나의 ISP하고만 연결된 경우. 출발/도착만 가능. (통로역할x)
※ BGP와 같은 inter domain protocol을 통하여 여러 RIB(경로 계산의 입력물)이 생기고, 이 RIB들을 토대로 FIB(경로계산의 산출물) 만든다.
