Network Routing

그래프 기본 용어

Fowarding vs Routing Table

Forwaring: 목적지까지 가장 빨리 도달할수 있는 다음 포트 (위치)를 알려주는 표

Routing: 출발지부터 목적지까지 경로를 적어둔 표. 라우팅 알고리즘으로 경로를 파악해서, 빠른 구간을 알려주는 포워딩 표를 만들 수가 있다.

가장 큰 차이점은, decisions in local or global 이라고 볼 수 있다.

포워드는 내 위치에서 목적지를 향하는 가장 가까운 다음것만 알려주니 Local.

라우팅의 경우 여러 경로를 알고 있으니 (의도적으로 다른 경로를 알려줘서 로드를 줄일수도 있음)

Spanning Trees

loop을 없애서 안전한 경로를 만들었음. 하지만 이로 인해 바로 옆에 있는 경로도 선택을 못하는등의 낭비가 발생함. 즉 만들어진 경로에 대한 퀄리티를 측정할 방법이 없음

Routing

어느 경로로 일정 트래픽을 보냄으로써, 네트워크의 대역폭을 그 경로의 조건과 요구사항에 적응하며 형성.

라우팅은 이상적으로,

• 컨트롤러가 없으며, 모든 노드 (라우터)가 비슷하며 (같은 언어, 알고리즘 등등)
• 이웃과 소통을 하며 학습하고, 각종 링크/메세지 실패를 처리 해야한다.

라우팅에는 몇가지의 Expectiatons 들이 존재하는데

• Correctness - A 로부터 B에 패킷이 전달되어야 한다.
• Efficiency - Use available bandwidth and other resources (CPU, energy)
• Fairness - Dont ignore capable network elements (적절한 네트워크 요소에 공평해야 한다)
• Convergence - Recover fast from disturbances
• Scalability - Copes (대응) with large and complex networks

최선의 경로란 무엇인가?

• 최선을 정의하는것에 다양한 요소들이 존재하는데
  • 레이턴시 (distance delay), 대역폭, 코스트, 홉스 (forwarding delays)
• 고정된 위상을 사용할 경우, 링크 혼잡과 라우터 부담등을 전혀 고려하지 않는다

Shortest path routing

가장 비용이 낮은 라우팅을 말하며, 양 종단간의 route간에 소요된 비용중 가장 낮은것을 선택함. 물론 해당 비용은 정의에 따라 다르다 (홉수, 속도, 지연, 가격 등등)

Optimality Property: ABCDE 가 AE를 연결하는 가장 짧은 구간이라면, AB, CDE, BCD등의 sub 구간또한 가장 짧은 경로이다.

• Sink(source) Tree: 각 소스로부터 해당 node까지의 가장 가까운 경로들의 합.
  • E의 sink trees = FE, DE, BE, ABCE등
  • 물론 소스 트리의 경우 양방향을 고려하기도 해서 만약 비용이 비대칭적이라면 sink tree ≠ source tree.
• 어느 곳에서 시작을 하던, 결국 라우팅 결정은 목적지에 따라 결정된다. 어디서 시작되는지는 사실 중요하지 않음.
• 각 노드들은 해당 목적지까지의 가장 가까운 경로를 가진 다음 hop만 알고 있으면 됨 (포워딩 테이블)

Dijkstra’s algorithm

위상과 비용이 주어졌을때 각 소스에 대한 소스 트리를 만든다, 위에 명시된 Optimality property를 사용한다

https://namu.wiki/w/%EB%8B%A4%EC%9D%B5%EC%8A%A4%ED%8A%B8%EB%9D%BC%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

1. 소스로 부터 시작해서 모든 소스들에게 반복적으로 탐색을 시도한다
2. Leverages optimality property - 부분 구간을 이용하여 더 긴 가장-짧은 구간을 만든다
3. 복잡한 네크워크에서는 스케일링 문제가 있다 - 한 부분이 바뀌면 다시 다 탐색해야함.
4. Complete Topology을 필요로 한다 (각각의 노드/소스 로부터)

Distance Vector Routing

위상을 모를때, 가중치가 음일때도 사용가능하지만, 다익스트라보다 시간 복잡도가 높다

노드들은:

• 이웃까지의 비용밖에 모른다, 오직 이웃과 대화한다
• 모든 노드는 같은 알고리즘을 사용한다, 노드와 링크들은 메세지를 잃거나 실패할수 있다.

모든 노드들은 모든 종착지에 관한 거리와 다음 노트를 저장하고 있다

1. 루트를 더하거나 삭제할때, 옆 이웃과 이야기가 안되면 업데이트 할때 서로 알려주면됨
2. 어느 특정 네트워크가 사라질때 구간의 비용이 무제한이 될 수 있음 - 이에 대해 따로 알고리즘이 필요함
   1. 만약 ABCD 에서 A가 사라지면, B는 C 에게 C는 B에게 A에 대해 서로 물어보게됨
      1. 왜냐면 A-B 로 이어져 있어도 C-A연결이 가능할수도 있으니까 (평소에는 그냥 최단거리만 알고 있음)
   2. 이를 해결하기 위해 Poison reverse or split horizon을 이용한다
      1. 내가 루트를 배운 노드에게는 내 노드를 광고하지 않음
      2. 몇몇 상황에서는 well scale 하지 않음.

Link State Routing

더 많은 계산을 필요하지만, 더 나은 모습을 보여줌. 기업네트워크에서 스케일이 좋다 (글로벌은 아님)

예로는 Open Shortest Path First (OSPF), IS-IS

다른 알고리즘과 비슷하게 다음과 같은 요소들을 가지고 있음

• 이웃과 이야기하며, 그들만의 비용만 알고 있고
• 위상을 모르며 (초반에), 노드/링크/메세지 실패를 처리할수 있다.

Simple Algorithms in 3 parts

1. Flood the network
   1. Broadcast incoming message to all outbound - 이를 link state packet (LSP)라 칭한다
      • 내가 받은 메세지를 모두에게 알려주는거.
      • 놓치면 ARQ 이용해서 다시 알려달라함
   2. 돌고돌아 자신에게 도착했을때 반복하지 않도록만 알고 있으면 됨 (보통 증가하는 넘버를 사용함)
2. Learn the topology
   1. LSP를 듣고, 위상을 파악함
3. Compute Tables with Dijkstra
   1. 아마 여태 받음 LSP들을 다 저장해서 각 노드에 개별적으로 계산하는듯
   2. 내부적으로 (스스로) 다익스트라를 실행함)
   3. 반복적이고, 많은 씨피유를 낭비하지만 효과적임
4. Repeat everytime whene there is a change.
   1. 만약 한 링크의 변화를 감지하면 업데이트된 LSP를 1번하고 3번을 모든 노드가 다시 함

• 다양한 실패들이 존재함 (flood, node flaps, seq# error 등등)
  • LSP ageing and timeouts 를 이용해서 처리한다.

Equal Cost Multiple Path

라우팅 프로토콜/알고리즘은 아니고 그냥 extension임

소스와 목적기까지의 경로를 여러가지를 가지고 있음으로써, 로드 밸런스, capacity increase와 같은 성능 향상과 Greater redundancy (불필요한 반복) 를 가져온다.

이를 위해 Detect 와 foward traffic along with paths 가 요구된다

Detection:

• 같은 비용의 여러가지 경로가 존재 한다면 모두를 저장해둔다.
  • ABE, ABCE, ABCDE 모두 비용 8
  • Not a tree, but a directed acyclic grapd

Forward: Detection을 통해 이제 forward table 는 각 목적지에 여러 인터페이스를 가진다

• 각 패킷에게 다른 경로를 (무작위로) 제공한다.
  • 이로 인해 로드밸런싱은 좋으나, jitter (패킷 딜레이 variation)은 안좋다
    • 왜냐면 다른 경로를 통하니 서로 PDV 가 다르지
• 관계에 따라 경로를 제공한다
  • 소스와 목적지의 아이피 주소를 이용한다. 같은 비용, 지속적인 성능을 제공한다
    • 아이피 주소를 이용해서 이 아이피 주소는 이 경로만 이용하는거
• 흐름에 따라 제공
  • Use of flow identifiers (IPv6)

이러한 방법들은 불균형적이지만 좀더 예상 가능해 진다.

Hierarchical Routing

• 스케일링 문제가 존재한다
  • 라우팅 테이블, 계산, 포워딩 테이블의 크기가 점점 증가하기 때문이다
• 네트워크 aggregation -
  • LAN prefix 가 이미 존재하기에 그것을 이용한다
    • 한 서브넷안의 모든 호스트를 광고할 필요없다, 나 (라우터) 에게 결국 와야 하니까
  • 한 서브넷의 집합을 큰 서브넷처럼 다룬다 - 모든 서브넷들이 붙어 있는건 아니다

Routing to a region

• 장점: 노드와 서브넷을 합쳐서 지역으로 간주한다.
  • 이로 인해 그 안의 복잡함을 감추고, 테이블의 길이를 짧게 한다
  • 또한 통신과 계산등을 줄일수 있다.
  • 지역간을 담당하는 라우터를 지정하고, 각 지역마다 어떤 방식을 사용할지 결정도 가능하다.
    • 즉 A는 B 쪽 라우터를 가려면 꼭 이 라우터를 통과해야 하는 담당 라우터를 말하는것
• 단점:
  • 덜 효율적인 경로가 만들어질수 있다.

Policy Routing

• 다양한 정치적인 기준점이 존재한다; 돈 정치, 보안, 종교

14. Routing in Internet - 인터넷에서의 라우팅

• 가장 짧은 경로는 결국 지역적 우선순위, ISP는 단지 부담을 최대한 줄이고 싶을뿐
• Hot Potato Routing 이라고 한다
  • 최단 경로가 아닌, 어느정도 짧은 경로 이용
  • 비대칭적인 경로, 오고가는길이 다를수 있음
  • 계층은 좋은 비지니스 이유로 수립되지 않음

Common Policy

1. Transiting: ISP A 가 너의 인터넷 연결을 관리함
2. Peering: ISP A가 너에게 인터넷 트래픽을 주고 받고 제공하지만, A가 인터넷에 연결된게 아닌 ISP B로 부터 인터넷을 받아오는 형식

Border Gateway Protocol (BGP)

다른 ISP간의 트래픽 전송을 방지하고 자신의 네트워크를 통해서는 트래픽 라우팅을 원하는 정책

오늘날 가장 흔한 정책이다

키 컨셉트:

1. Autonomous System (AS) 즉 자치 시스템안에서의 노드들을 통합
   1. 이로 인해 확장성 문제를 해결화 한다.
2. Border Router (Gateway) which run BGP 를 확정한다
   1. 외부 (네트워크) 와 지역 (자치 시스템) 사이를 담당한다.
   2. 이 게이트 웨이가 다른 라우터에게 자신이 담당하는 경로를 알릴지 말지 결정 가능하다
      1. 이 라우터에게 정보를 받지 못하면 이 네트워크 이용 불가능 하다 (뭐있는지 모르니까)
      2. 혹은 몇몇 경로만 필터링해서 알려줄수도 있다.
   3. 또한 이 게이트웨이는 다른 라우터로 부터 도착한 메세지의 목적지를 보고, 내가 제공하는 경로중 하나이면 다음 홉으로 패스해준다. (이 조건은 가격, 친구요청인지, 안전한지 등등 많다)
3. 외부와 내부의 라우팅 프로토콜의 단절화
   1. Intradomain
      1. 하나의 관리자가 제어하므로 정책 결정 무필요
      2. 성능에 초점
   2. interdomain
      1. 각 네트워크 관리자 끼리 정책을 교환한다
      2. 정책에 초점 - 최소 비용이 더 중요하기 때문

BGP는 LS 보다는 DV에 해당한다 (DV 보단 Path vector에 더 가깝다). 루프의 존재를 감지와 함께 삭제할 수 있다.

위의 경고 광고는 다음을 포함한다

• IP Prefix, next hop
• Path: list of AS’s to transit
  • 이로 인해 루프의 존재 감지및 삭제를 가능하게 한다
  • 거리 indication 은 없다.

정책 Implementation

• BGP 로 누구한테 “광고”를 할지 설정할 수 있다
• Border Routers 들은 가능한 경로들을 광고 하는데 (얘네가 담당하니까 다른 Inter domain 연결을)
  • 얘네가 사용 가능한 (허락해준) AS 에게만
  • 혹은 얘네가 허락해주는 AS 에게만
  • 혹은 알려주되 다른 경로들 (빠르거나 느리거나) 을 AS에 차별해서 나눠준다 (AS간 금전거래 이유등등)

와 같은 다양한 이유와 목적을 가지고 경로들을 알려줄 수 있다.

• 또한 Border Router 들은 다양한 announcements 들을 주위로부터 받는데 자신이 사용하고 싶은 광고만 골라서 네트워크 안으로 전파할 수 있다 (예를 들어 같은 목적지에 갈 수 있는데 싼 비용의 SA 광고만 전파한다던가 등등)

보통 peer 관계의 경우

[B, (AS3), borderRouter 3a] → B는 AS3 의 3a 라우터를 통해 도착할수 있습니다 알려주는것

transit의 경우

[B, (AS1, AS3), router 1b] → B는 AS1 을 통해 AS3 로 가서 도착할 수 있는데, 먼저 AS1의 1b 라우터를 통해 오십시오 같은것

결국 위의 A 손님은 B 로 갈수 있는 방법이 두가지인것. 보통 peering 이 무료다.