목표

목적지까지 가는 가장 좋은 path 를 찾아내는 것

좋은 path 란 ? 비용이 적게 들거나, 가장 빠르거나, least congested 하거나 !

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 를 빨리 벗어날 수 있는 쪽으로 선택하는 전략
뜨거운 감자가 내 손에 있다 → 빨리 다른 사람 줘야 돼 ..! 너무 뜨거워..

728x90

저작자표시

Network :: Routing protocol

목표

분류