목표
목적지까지 가는 가장 좋은 path 를 찾아내는 것
좋은 path 란 ? 비용이 적게 들거나, 가장 빠르거나, least congested 하거나 !
분류
Q. global or decentralized information ?
- global →
link statealgorithm - decentralized →
distance vectoralgorithm
Q. static or dynamic ?
- static
- dynamic
Link state algorithm
Dijkstra’s algorithm
특정 출발지에서부터 모든 노드로 최단 경로 찾기 알고리즘 !
특정 출발지에서 목적지까지 가는 경로 중 최소 비용으로 갈 수 있는 경로를 찾는 것
표기 방법
- C(x, y) : x 에서 y 까지 가는데 드는 비용
- D(w) : w 까지 가는데 드는 비용
- P(v) : 바로 앞 전 노드
- N’ : 최소 비용을 가지도록 하는 경로에 있는 노드의 집합
아래는 출발지를 u 로 잡고 다익스트라 알고리즘을 돌렸을 때의 결과값이다.
예시를 하나 더 해보자.
이거 이해되면 다익스트라 마스터 ?
이렇게 다익스트라 알고리즘을 통해 u 노드에서 출발하는 최단거리를 계산하고 나면
아래와 같은 최단 거리 결과값들이 나온다.
이게 바로 Link state 알고리즘
전체 노드와 경로 정보를 다 알고 시작한다 !
문제점
노드 개수 N 에 따라 O(N^2) 의 시간복잡도를 가진다.
다익스트라 알고리즘은 특정 경로를 많이 사용하게 되어 비용이 변화하면 또 다시 계산해야 하고,
다시 계산된 값으로 경로를 새로 세팅해 또 그 경로를 많이 사용하게 되면 비용이 변화하는..
순환적인 문제가 생길 수 있다 → oscillation 문제 발생 가능
Distance vector algorithm
Bellman-Ford equation (dynamic programming)
x 에서 y 까지 가는 비용 중 가장 비용이 적은 경로 선택 !
전체 노드 사이의 경로 비용은 모르지만,
인접한 노드 하나하나씩 비용의 최솟값을 계산해나가는 것 !
주기적으로 본인과 붙어있는 노드들에게 정보를 알려주고,
정보를 받은 노드는 다시 계산해서 라우팅 테이블을 반복적으로 만들어내는 것이 키 아이디어이다.
OSPF
intra-AS routing in the Internet
하나의 네트워크 안에서 동작 !
autonomous system → AS (a.k.a. domain)
AS 내부에서 돌아가는 시스템 → IGP (Interior gateway protocol)
- RIP
- OSPF
- IGRP
그 중 대표적인 게 OSPF !
OSPF : Open Shortest Path First
- link-state 알고리즘을 사용
- 3계층 IP 바로 위에 존재한다.
- 특정 노드까지 가는 여러 개의 길을 제공
- 계층적 구조
BGP
routing among the ISPs
AS 사이에서 동작하는 프로토콜
BGP : Border Gateway Protocol
- 인터넷에서 표준처럼 사용되고 있음
- eBGP : 외부와 통신
- iBGP : 내부 AS 에서 통신
- “I am here” 정보를 계속 서로 주고받음
BGP message
- OPEN
- UPDATE
- KEEPALIVE
- NOTIFICATION
BGP 는 TCP 커넥션 위에서 동작 !
따라서 연결 OPEN, KEEPALIVE 와 같은 메시지가 필요하다.
BGP 에서 Route 를 선택하는 전략 (아래 순차적으로)
- policy 우선
- path 가 작은 걸 선택
- 가장 가까운 NEXT-HOP 라우터를 선택 :
hot potato routing - 그 외 전략
hot potato routing : AS 를 빨리 벗어날 수 있는 쪽으로 선택하는 전략
뜨거운 감자가 내 손에 있다 → 빨리 다른 사람 줘야 돼 ..! 너무 뜨거워..