[CH.4] Routing algorithms / Routing in the Internet

 

 

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
• Q: static or dynamic?
  • static:
    • 시간이 지남에 따라 경로가 느리게 변화
    • 라우터 포워딩 테이블을 직접 수정해야 함
  • dynamic:
    • 빠르게 경로가 변화
      • 정기적인 업데이트
      • link cost 변경에 대한 응답

 

 

 

Link-State Routing Algorithm

• 다익스트라(Dijkstra) 알고리즘
  • 모든 노드에게 net topology와 link costs 정보가 알려짐
    • "link state broadcasting"을 통해 알려짐
    • 모든 노드들은 같은 정보를 갖는다
  • 하나의 노드(출발지)에서 다른 노드(도착지)까지 최소 비용 경로를 연산한다.
    • 해당 노드들에 대해 포워딩 테이블을 제공
  • k번 반복 연산 후, k까지 가는 최소 비용 경로를 알게 됨
• notation:
  • C(x,y): x에서 y로의 link cost
    • 만약 바로 갈 수 있는 노드가 아니라면 ∞
  • D(v): 출발지에서 목적지까지 경로의 cost (현재까지 계산한 cost)
  • P(v): 출발지에서 경로로의 v까지의 경로에서 v의 이전 노드
  • N': 최소 비용 경로로 정의된 노드들의 집합

 

 

다익스트라 알고리즘의 complexity

• n개의 노드가 있을 때, 모든 노드를 확인해야한다. -> n(n+1)/2번의 비교가 필요하므로 O($n^2$)의 복잡도를 가진다.
• 더 효율적으로 구현하면 O(nlogn)이 가능하다.

 

 

 

Distance vector algorithm

• 벨만 포드 알고리즘 (dynamic programming)
• $d_{x}(y)$: x에서 y까지의 최소 비용 경로의 cost
• $d_{x}(y)$ = $min_{v}${c(x,v)+$d_{v}(y)$}

• key idea:
  • 자신의 distance vector estimate를 이웃들에게 보낸다.
  • x가 이웃으로부터 새로운 DV를 받으면, B-F equation을 이용하여 자신의 DV를 업데이트한다.
  • Dx(y) ← min{c(x,v) + Dv(y)}  for each node y ∊ N
  • 추정한 $D_{x}(y)$는 실제 최소 비용인 $d_{x}(y)$에 수렴한다.

 

• iterative, asynchronous:
  • local link cost가 바뀔때 local iteration이 발생
  • 이웃으로부터 DV 업데이트 메시지 받으면 업데이트
• distributed:
  • 각 노드들은 자신의 DV가 변경될 때 이웃에게 알림

 

 

 

 

• Distance vector: link cost changes
  • link cost가 감소한 경우 업데이트가 빠름
    1. $t_{0}$: y가 link cost 변화를 탐지하고 자신의 DV를 업데이트한 후, 이웃들에게 이를 알림
    2. $t_{1}$: z가 y로부터 업데이트 정보를 받고, 자신의 테이블을 업데이트. x로의 최소 비용을 업데이트 한 후, 이웃들에게 자신의 DV 보냄
    3. $t_{2}$: y가 z로부터 업데이트된 정보로를 받고, 자신의 테이블을 업데이트. y의 최소 비용 테이블은 변하지 않았으므로 z에게 메시지를 보내지 않음 => 업데이트 끝!
  • link cost가 증가한 경우는 업데이트가 느림
    • z가 x로 갈 때, y를 통한 경로보다 x로 바로 가는 것이 cheap하다는 것을 깨달을 때까지 44번의 반복이 발생 -> 'count to infinity' 문제
    • poinson reverse를 이용해 문제 해결
• Distance vector: poisoned reverse
  • 만약 Z가 X를 얻기 위해 Y를 통해 간다면:
    • z에서 y 거리를 ∞ 주고 업데이트 하도록 함
  • 즉, 업데이트된 곳 반대를 ∞로 설정해주고 업데이트하면 빠름
  • poisoned reverse가 infinity problem을 대부분 해결하기는 하나, 세 개 이상의 이웃 노드를 포함한 루프인 경우 감지하지 못한다.

 

 

 

LS와 DV 알고리즘 비교

• message complexity
  • LS: 노드가 n개, 링크가 E개일 때 O(nE)
  • DV: 이웃끼리만 메시지 교환
• 수렴 속도
  • LS: O($n^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: 송신자에서 수신자로의 다른 트리 

 

 

 

 

 

출처: [Computer networking: A top-down approach, 6th]