Routing Algorithm

• Routing algorithm의 목표는 source에서 destination까지 라우터 네트워크를 통해 "좋은" 경로을 찾는 것이다

  좋은 경로란 무엇일까?

• 경로란 packet이 source에서 시작하여 destination에 도착하는데 사용되는 라우터들의 순서이다
• 좋은 경로는 비용이 가장 적은 경로가 될 수도 있고, 가장 빠른 경로가 될 수도 있고, 가장 혼잡이 적은 경로가 될 수도 있습니다.

Path Cost

• 어떤 경로를 선택하는데 있어서 cost가 들며 link cost는 그림과 같이 link마다 값이 주어진다
• 어떤 두 라우터 u와 z 사이에 가장 최소 비용의 경로를 찾아주는 것이 routing alogrithm이다

Routing algorithm은 어떻게 구분이 될까?

Routing Algorithm Classification

• Routing alogrithm 분류 방식은 크게 두가지가 있다
• static-dynamic, global-decentralized

Static

• 각 path를 관리자가 직접 결정하는 정적 방식이다
• 중간 라우터들을 다 수동으로 설정한다
• 네트워크의 상황이 바뀌면 관리자가 라우터들에 접속을 해서 값을 수동으로 바꾼다

Dynamic

• 라우터들이 자동으로 정보를 주고 받고 path를 선정하는 동적 방식이다
• 같은 source와 destination이더 라도 네트워크 상황에 따라서 path가 변할 수 있어 빠르게 대응할 수 있다

Global

• 모든 라우터들이 전체 네트워크 topology(연결도)를 알고
• 각 네트워크에 있는 모든 link cost를 다 알고 있는 상태로 path 결정한다
• ex) link state algorithm

Decentralized

• 직접 연결 되어 있는 이웃 라우터들끼리 정보를 주고 받는다
• 다른 라우터로 가기 위한 path 비용과 그 path 비용으로 보내기 위해서 어떤 라우터를 선택해야 하는지 알고있다
• ex) distance vector algorithm

Routing algorithm은 어떤게 있을까?

Link State Algorithm

• global (centralized)
• 모든 노드가 동일한 네트워크 topology와 link cost를 알고 있다
• 라우터들이 link state broadcast를 통해 정보를 교환한다

Dijkstra algorithm

• 하나의 source에서 모두 다른 node까지의 최단 거리를 구하는 algorithm이다
• 각각의 라우터에서 Dijkstra algorithm을 수행하여 자기로부터 네트워크에 있는 모든 node로의 최소 비용 경로를 계산한다
• 계산한 최소 비용 경로를 기반으로 forwarding table을 구현한다
• Dijkstra algorithm에 사용되는 notation이다
  - C(x,y) : x와 y 사이의 link cost이다. x, y가 직접 연결 되어 있으면 어떤 값을 가지겠지만 직접 연결이 없을 때는 무한대로 둔다
  - D(v) : source로부터 node v까지 갈 때 드는 현재 알고 있는 최소 경로 비용이다.
  - P(v) : v로 가기 위해서 이전에 거치는 node이다
  - N’ : 현재 최소 비용 경로가 계산 된 node들의 집합이다

• Initialization에서는 시작노드 u의 인접노드들의 최소 경로 비용을 link cost로 초기화한다.
• 아래는 Loop 내용이다

1. 현재 선택한 정점(처음엔 시작점)에 곧장 연결되고, 아직 방문하지 않은 정점들을 모두 본다
2. 선택한 정점과 보고있는 정점 사이의 거리와 시작 정점과 선택한 정점까지의 최단거리의 합이 현재까지 구한 시작 정점과 보고 있는 정점 사이의 거리보다 짧을 경우, 이를 갱신해준다: D(b) = min (D(b), D(a)+C(a,b))
3. 1, 2번 수행이 모두 끝난 이후, 아직 방문하지 않은 정점들 중 시작점과의 거리가 가장 짧은 정점을 선택한다
4. 방문하지 않은 정점이 존재하여 정점을 선택했다면, 현재 구한 시작점으로부터의 현재 선택한 정점 사이의 거리는 최단거리이다.
5. 방문하지 않은 정점이 존재하지 않는다면, 수행을 종료한다. 그렇지 않으면 1번으로 돌아가 수행을 반복한다

• 이전에 거치는 node를 기록한 P(v)를 사용하여 outgoing link를 구할 수 있다

Algorithm Complexity

• Loop n times = O(n)
• D(a) 최소값 찾기 = O(n) (힙 사용시 O(logn))
• update D(b) by iterating adjacent
  t nodes = O(n)
• Total complexity = O(n^2) (힙 사용시 nlogn)

Message Complexity

• 각 라우터는 모든 라우터들에게 link state 정보를 broadcast해야 한다
• broadcast algorithm: O(n)
• Total complexity = nO(n) = O(n^2)

Oscillations

• 초기에 c는 e(<1), d는 1, b는 1 만큼의 traffic을 보유한다
• d에서 a 시계방향으로 갈때는 1, c에서 a 반시계 방향으로 갈때는 e+1 만큼의 traffic이 발생한다
• 1) c는 시계 방향으로 (0+1=1<e+1) 가는 것이 traffic이 덜 발생한다고 감지하여 시계 방향으로 방향을 바꾼다
• 2) 이후 b가 시계 방향으로 가면 e+2, 반시계 방향으로 가면 0 만큼의 traffic이 발생한다고 감지하여 반시계 방향으로 다시 바꾼다
• 1)->2)->1)->2).. 반복된다!

라우터 B,C가 네트워크 변화에 빠르게 반응하여 oscillation이 생기는 것 같다. 동시에 link state 알고리즘을 수행하지 못하도록 하면 문제를 해결할 수 있지 않을까?

Distance-Vector Algorithm

• 각 노드가 자신과 이웃 사이 link cost가 변경된 것을 알게되면, 자신의 distance vector를 갱신하고, 최소 비용 경로의 비용에 변화가 있는 경우 이웃에게 새로운 distance vector를 보낸다

Bellman-Ford Algorithm

• node x부터 y까지의 최소 비용 경로의 비용을 Dx(y)라고 한다
• Dx(y) = min {Dx(y), c(x,v) + Dv(y)}

• 각 라우터가 Initialization을 통해 초기 distance vector를 계산한다

• 라우터 b가 인접한 a,e,c (1 hop away routers)로 부터 distance vector를 받는다

• 이제 b는 a,c,e를 거쳐서 갈 수 있는 라우터들에 대한 최소 비용 경로를 계산 할 수 있다

• bellman-ford 공식 Dx(y) = min {c(x,v) + Dv(y)}를 사용한다

• Db(d)은 아래와 같이 갱신된다
  - Db(d) = min {Db(d), c(b,a) + Da(d)=9} = 9
  - Db(d) = min {Db(d), c(b,c) + Dc(d)=2} = 2
  - Db(d) = min {Db(d), c(b,e) + De(d)=inf} = 2

• b가 계산하는 동안 c도 동시에 distance vector를 갱신하고 있다

• 당연히 c는 b의 초기 distance vector를 받았다 (같은 t=1이기 때문!)

• b,c 뿐만 아니라 모든 라우터들이 동시에 같은 작업을 수행중이다

• t=1에 1 hop away 라우터의 distance vector를 받고 자신의 distance vector를 갱신했다
• t=2에는 바뀐 자신의 distance vector를 인접 라우터들에게 전달한다
• 즉 t=2에는 자신의 distance vector는 2 hop away 라우터들의 distance vector로 부터 영향을 받기 시작한다

Routing Loop

• count to infinity
• link cost가 변화하면 문제가 생길 수 있다

• c(x,y)가 1로 줄어들었다
• Dy(x) = min(c(x,y),c(y,z)+Dz(x)) = min(1,51) = 1 (문제없음)
  
• c(x,y)가 증가한 경우다
• Dy(x) = min(c(x,y),c(y,z)+Dz(x)) = min(60,6) = 6?

  문제는 Dz(x) 값이다. t=0에서 y가 link cost 변화를 감지하고 x까지의 최소 비용 경로를 새로 계산한다. 하지만 계산 과정에서 c(x,y)가 4였을때 계산됐던 Dz(x)값 5가 사용된다. 이어서 z는 y가 갱신한 distance vector를 받고 Dz(x) = 7로 갱신한다. 그럼 또 y는 z가 갱신한 distance vector를 받고 Dy(x) = 1+7 = 8로 갱신한다. y->z->y->z->y.... Loop!

Algorithm Complexity

• 수렴 시간이 다양함

Message Complexity

• 연결된 이웃만 메시지 교환
• 수렴 시간이 다양함

LS DV Malfunction

LS

• 잘못된 link cost가 광고된다
• 각 라우터가 자신의 forwarding table만 계산한다

DV:

• 잘못된 path cost가 광고된다 = black-holing
• 각 라우터의 table이 다른 라우터에서 사용되어 에러가 네트워크 전반에 전파된다

지금까지 라우터의 성능이 똑같고 network가 flat하다는 가정했다. 실제로는 어떤 모습일까?

Scaling Problem

• IP 주소는 엄청나게 많다
• Network가 flat하다면 forwarding table에 이 많은 IP 주소를 다 포함 시켜야 한다 = table size가 매우 커짐

Administrative Autonomy

• Admin에게 administrative autonomy를 부여하여 자신의 영역에 대한 지배권을 가져한다

Scalable Router

• Scalable하게 만들기 위해서 라우터들을 autonomous systems (AS aka domain) 영역으로 나눠줘야 한다
• 전체 네트워크를 여러개의 AS로 나눴을 때 AS 내부를 담당하는 라우팅과 AS 간의 라우팅을 담당하는 라우팅이 있다

Intra-AS Routing

• AS 내의 모든 router는 모두 같은 intra-domain protocol을 사용한다
• 다른 AS에서는 다른 intra-domain protocol을 사용할 수 있다
• Admin이 protocol을 결정한다

Inter-AS Routing

• AS의 경계에 있는 라우터들이 수행한다
• gateway router: AS에서 다른 AS 라우터로 가기위해 거쳐하는 링크다
• gateway router는 자신의 AS에 속함으로 intra-AS routing도 수행한다

Forwarding Table

• forwarding table은 intra-AS routing과 inter-AS routing 알고리즘들로 설정된다
• intra-AS routing는 AS내의 도착 지점들에 대한 entries를 결정한다
• inter-AS + intra-AS가 AS 바깥의 도착 지점들에 대한 entries를 결정한다

  예를 들어 AS1은 도착 지점이 AS3에 있는지 AS2에 있는지 알아야한다. Gateway 라우터를 통해 알아내고 이 reachable info를 AS1내 라우터들에게 알린다. 전달 받은 라우터들은 이를 기반으로 forwarding table을 설정하여 routing 할 수 있다

Intra-AS Routing Protocols

Routing Information Protocol(RIP)

• 30초마다 distance vector 교환
• 더이상 안쓰임

Open Shortest Path First (OSPF)

• link state 라우팅 방식이다
• open = publicly avabilbe
• 각 라우터는 OSPF link state AS내 모든 라우터들에게 광고한다
• 각 라우터는 full topology를 가지고 dijkstra 알고리즘으로 forwarding table을 계산한다

Hierarchical OSPF

• 하나의 AS를 area, backbone으로 나눈다
• backbone은 여러 area를 묶어준다
• 각 area가 하나의 OSPF domain이 된다
• area border router:
  -backbone에서 area를 이어주는 라우터
  -area 내부에서 도착지로 가는 거리 정보를 정리하여 backbone에 광고한다
• local router
  -area내 라우터
  -link state를 area내로만 광고한다
  -routing도 area내로만 한다
  -area border router를 통해 area 밖으로 packet을 보낸다
• boundary router
  -backbone의 경계에 있고 다른 AS로 연결한다
  

Inter-AS Routing Protocols

Border Gateway Protocol (BGP)

• subnet의 존재를 Internet 전반에 광고한다
• 이웃하는 AS들로부터 destination reachability info를 받는다 (eBGP)
• reachability info와 policy를 기반하여 다른 네트워크로의 routes들을 결정한다
  -policy란 예를 들어 특정 ISP나 특정 국가 네트워크를 통하지 않고 route를 구하는 것이다
• reachability info를 모든 AS내 라우터들에 propagate한다 (iBGP)
• AS가 원하는 정보만 광고 할 수 있다
• 다른 AS에서 AS에 속한 라우터 x로 packet을 보내고 싶지만 AS가 원하지 않는 경우가 있을 수 있다

BGP session

• 두 BGP 라우터는 TCP 연결을 통해 BGP 메시지 (path 광고)를 주고 받는다

• AS3에 X가 추가되었다
• AS3는 X에 도달 할 수 있다는 사실을 알고 이웃 AS2로 알리려고 한다

• AS2로 알리기 위해서는 AS3 gateway 3a가 AS3,X의 path를 AS2 gateway 2c로 광고한다
• 즉 AS3는 AS2에게 datagram을 X로 보낼 수 있다고 약속한다

BGP messages

• OPEN: BGP peer간의 TCP 연결을 열고 peer를 검증한다
• UPDATE: 새로운 path를 광고한다 (혹은 기존의 path를 지운다)
• KEEPALIVE: UPDATE 메시지 없이 연결을 계속 열어놓거나 OPEN 요청에 ACK 보낸다
• NOTIFICATION: 기존 메시지에 대한 에러를 알리거나 연결을 끊는다

Path attributes

• BGP 라우터가 path를 광고할때 제공하는 정보는 두가지다: prefix + attibutes
• path prefix: CIDR destination IP 주소
• attributes
  -AS-PATH: prefix 광고가 지난간 AS 리스트
  -NEXT-HOP: 다음 AS로 넘어가기 위한 AS 라우터

Policy-Based Routing

• route 광고를 받은 라우터는 path를 수락하거나 거절 할 수 있다
• 라우터가 이웃 AS로 path를 광고할지 말지 정할 수 있다
• 이전 예시의 자세한 과정을 보자

• AS2 gateway 2c가 AS3,X 광고를 AS3 3a로 부터 받았다 (eBGP)

• AS2 gateway 2c는 policy를 기반해 광고를 accept하고 AS2 라우터들에게 AS3,X path를 전달한다 (iBGP)

• AS2 gateway 2a가 전달받으면 AS2 policy를 기반해 AS2,AS3,X path를 AS1 gateway 1c로 광고한다 (eBGP)

Multiple Paths

• AS1 gateway 1c가 2a로 부터 AS2,AS3,X 그리고 3a에서 AS3,X를 받아 X로의 path를 두개 받을 수 있다
• 이 경우 AS1 policy를 기반하여 둘 중에 고르고 AS1 라우터들에게 광고한다 (iBGP)

Routing Policy

• ISP/provider network는 자기 customer의 traffic을 처리하기 때문에 다른 ISP의 customer의 traffic은 담당하고 싶어하지 않는다

• A의 customer w에 대해 A는 B,C에게 A,w path를 광고한다
• A가 광고하지 않으면 A를 통한 w로의 traffic은 발생하지 않는다

  B는 C에서 B,A w path를 광고할까?

• 위에서 말했듯이 다른 ISP의 customer의 traffic은 담당하고 싶어하지 않는다
• 따라서 B는 C에서 광고하지 않는다 = C는 B를 거쳐 w로 가는 path를 배우지 않는다
  

  B가 자기자신 X을 거쳐 C로 못가게 하는 경우는?

• x가 dual homed인 상태고 x는 B에게 C x path를 광고하지 않는다

Populating Forwarding Table

광고된 path는 forwarding table에 어떻게 저장될까?

• AS1의 gateway 1c가 x로의 path를 1d에게 iBGP로 광고했다
• 1d의 forwarding table에서 dest x의 interface에는 거쳐가는 gateway 1c로 가기 위한 interface가 들어간다
• 즉 최종 도착점으로의 interface에는 거쳐가는 gateway로 가기 위한 interface가 들어간다

Hot Potato Routing

• 더 가까운 gateway를 선택하는 routing 기법

• 2d에서 x로 datagram을 보낸다
• 2d 입장에서 x로 가는 path는 gateway 2a 또는 2c를 거쳐가는 두가지가 있다
• hot potato routing에 따라 2d는 더 가까운 2a (201<263) 쪽을 고르고 보낸다

Why Different Intra/Inter AS Routing

Policy

• inter AS: admin이 어떻게 traffic이 routing되고 누가 routing하는지 policy로 control
• intra AS: admin이 한명이라 같은 policy

Performance

• inter AS: policy에 따라 performance가 달라짐
• intra AS: performance에 집중

Scale

• intra, inter AS로 나눠 hierarchial routing를 하면 forwarding table size를 줄일 수 있다

Software-Defined Networking(SDN)

• 중앙에 있는 controller가 일괄적으로 flow table을 계산하고 각 라우터에게 설치해준다
• distributed 방식보다 network 관리가 더 수월하다
• OpenFlow로 라우터를 programming 할 수 있다

Difficulty with Traditional Routing

• 기존에는 u to z traffic flow를 바꾸기 위해서는 admin이 weight를 직접 조절하여 path를 유도해야 했다

• 기존에는 u->z로 가는 traffic을 위 아래로 나눠 부하분산하는 것은 불가능했다

• 기존에는 두개의 route에 대한 priority를 처리하는 것은 불가능했다

SDN Structure

Data Plane Switches

• SDN-controlled switches는 data plane에서 forwarding을 담당한다
• controller으로부터 설치한 flow table를 기반으로 forwarding한다
• 사용하는 API OpenFlow

SDN Controller

• network 정보를 수집 관리
• northbound API를 통해 network-control applications에 접속
• southbound API를 통해 network switches과 연결
• distributed system으로 구현됨 (아래 설명)

Network-Control Applications

• "brains" of control
• controller의 function을 API를 통해 노출하면 control applications의 function을 수행한다

SDN Controller Detail

• 3부분으로 나뉘어져 distributed system이다
• 맨위 layer가 network-control applications와 연결되는 northbound API다
• 중간 layer에서 network state를 저장한다
• 맨밑 layer가 SDN controlled switches와 연결되는 southbound API다

OpenFlow Protocol