Routing Algorithnms

Routing protocol

• goal: 송신 호스트에서 수신 호스트까지 라우터의 네트워크를 통과하는 good path를 결정하는 것
  -> good: least-cost, fastest, least congested
  -> path: 일련의 라우터 패킷들

Abstract graph model

• graph G(N, E)
  • N: 라우터(노드)의 집합
  • E: 라우터 간의 링크(엣지)의 집합
• 노드x``y 사이 엣지는 cost를 나타내는 값을 가짐 -> c(x, y)

Routing Classification

1. global routing algorithm
   • 모든 라우터가 네트워크 전체에 대한 링크 비용 정보를 갖고있음
     -> 전체에 대한 정보로 최소 비용 경로 계산
   • 시간에 따라 천천히 변하는 경로
   • link state(LS) algorithms
2. decentralized algorithm
   • 라우터가 자신에게 직접 연결된 링크에 대한 cost만 알고있음
     -> 이웃과의 정보를 교환하며 iterative process computation
   • 경로가 더 빠르게 변경 (peridic주기적 update, in response to link cost change)
   • distance vector(DV) algorithms

1. LS Routing algorithm

Dijkstra's algorithm

• 다익스트라 알고리즘은 하나의 노드(출발지)에서 네트워크 내 다른 모든 노드로의 최소 비용 경로 찾기
  -> global information 사용
• ex) 강노 p.14~20 참고
  • 찾은 최소 경로로 시작점u 기준으로의 fowarding table 만듦 (목적지에 따라 u에서 어디로 가야할지)

Complexity: O(n^2)

• 각 iter마다 하나씩 줄어듦 (n) + (n-1) + (n-2) ... = n(n+1)/2

Flodding

• source node의 패킷이 모든 이웃 node에게 보내지고
• 각 노드에서 들어오는 패킷은 들어오는 링크를 제외한 나머지 모든 링크로 재전송
  -> 목적지에 여러 개의 복사본 도착 (같은 곳에 도착한 복사본은 삭제 됨)
• 패킷이 노드로 보내질 때마다 hop count가 감소하고, 0에 도달하면 패킷 삭제됨
• ex) 강노 p.27~31
  • 찾은 최소 경로로 시작점 C 기준으로의 Routing table 만듦 (목적지에 따라 C에서 어디로 가야할지)

2. DV Routing algorithm (⭐기말)

1. Distributed
   • 각 노드는 직접 연결된 이웃에게 정보 수신
   • 계산을 수행한 뒤 결과를 다시 이웃에게 분배
2. Iterative
   • 이웃 간에 정보 교환이 없을 때까지 반복
3. asynchrounous (비동기적)
   • 모든 노드가 동기화되지 않고 개별적으로 동작 (lockstep으로 동작할 필요 없음)

Bellman-Ford algorithm

• dx(y): x에서 y로 least-cost path의 cost
• 아래는 x에서 이웃노드 v로 이동한 후, v에서 y까지의 최소 비용 경로를 택하는 식
• ex) p.37~45, p.48~54
  • 갱신되는 것이 없어 끝나면, 각 노드들은 다른 노드로 가는 최소비용경로를 알게되고
  • 이것으로 routing table을 만듦

LV vs DV

message complexity

• LS: O(N E)개의 메세지 전송 (노드N, 링크E)
• DV: 이웃이랑만 메세지 전송 (수렴하는데 걸리는 시간에 따라 다름)

  • 링크 비용이 변할때마다 새로운 링크 비용은
    • LS는 모든 노드에게 전달해줘야하고
    • DV는 이웃의 최소 비용 경로에 변화를 준 경우에만 전달

Speed of convergence (수렴 속도)

• LS: O(n^2)
• DV: 수렴하는데 걸리는 시간은 많은 요소에 좌우됨

Robustness (견고성, 라우터가 고장나면?)

• LS: 노드는 잘못된 비용을 알릴 수 있다. 그리고 각 노드는 자신의 forwarding table만 계산하기 때문에 분산되어 계산되므로 어느정도 견고성을 가짐
• DV: 노드는 잘못된 경로를 알릴 수 있다. 각 노드는 다른 노드의 table도 사용하므로 한 노드의 잘못된 계산은 전체로 확산될 수 있음 (error propagate thru netowork)

Routing in the Internet

Routing protocol

• 라우팅 알고리즘으로 라우팅 테이블 구성

Autonomous System (자율시스템, AS)

• 같은 관리체계(administraion) 아래에 있는 라우터와 네트워크 집합
• AS number: 네트워킹 당국(authorities)에 의해 할당된 16비트 번호
  • Intra-AS routing: IGP (interior gateway protocol): AS 내부 라우터 간의 라우팅 담당 프로토콜 -> RIP, OSPF
  • Inter-AS routing: EGP (exterior gateway protocol): AS간의 라우팅 담당 프로토콜 -> BGP

1. RIP (Routing Information Protocol)

• 가장 널리 사용되는 IGP 중 하나
• DV 알고리즘 기반
  • Distance: number of hops (최대 15hop, 16은 끊어짐을 의미)
  • vector: next hop router
  • RIP advertisement: 각 라우터는 이웃과 매 30초마다 RIP 응답 메세지 교환 (UDP)
    • 메세지는 최대 25개의 목적지 subnet 목록 정보 포함

RIP routing table

• route-daemon이라는 application-layer process에 의해 관리
• periodically(주기적)으로 반복되는 UPD 패킷으로 advertise됨

ex)

• 라우터D의 라우팅 테이블이 A의 라우팅 테이블을 받고(AtoD advertisement) 갱신되는 모습

RIP advertisement

• 새로운 네트워크 연결되면
  1. R1이 net1이 연결된걸 알고 RT 업데이트
  2. R1이 자신의 RT를 R2에게 advertise하고, R2도 RT업데이트
  3. R2도 자신의 RT를 R3에게 advertise ...
• 네트워크 연결 끊키면
  1. R1이 net1과 연결 실패하면 RT를 D=16(infinity, 연결 끊어짐)으로해서 업데이트
  2. R1이 자신의 RT를 R2에게 advertise하고, R2도 RT업데이트
  3. R2도 자신의 RT를 R3에게 advertise ...

2. OSPF (Open Shortest Path First)

• Open: 공개적으로 사용 가능하다 (publicly available)
• LS 알고리즘 기반
  • 각 라우터는 AS내의 모든 라우터에 LS패킷을 broadcast(flooding)
  • 각 노드는 topology map을 얻고 Dijkstra 알고리즘으로 routing table을 계산
• OSPF 메세지는 IP를 통해 직접 전송 (TCP, UDP 사용 안함)

feature (not in RIP)

• security
  • 모든 OSPF 메세지는 authenticated(인증됨) (malicious intrusion악의적 침입 막음)
• multiple same-cost path allow
  • RIP에서는 동일한 비용이면 하나의 경로만 허용하는데 OSPF는 다중 경로 허용
  • 각 링크에 대해 서로 다른 TOS(type of service)에 대한 여러 비용 metrics 지원
    (ex- best effort Tos에는 low satellite link cost set, real time ToS에는 high satellite link cost set)
• unicast, multicast routing에 대한 통합 지원
  • OSPF를 확장해 멀티캐스트 라우팅 기능을 제공하는 MOSPF
• 단일 AS내에서의 계층 지원 (아래 area 설명)
  • OSPF의 AS는 계층적인 영역으로 구성될 수 있다

Operation

1. 이웃 관계 설정
   • 라우터는 hello 패킷을 교환하여 이웃 테이블(neighbor table, adjacency database) 구축
2. OSFP 데이터베이스 동기화(synchronize)
   • flooding을 사용하여 모든 다른 노드에게 Adjacency DB를 보냄
   • Link-State Database(LSDB) 구축
3. SPF tree (forwarding table) 생성
   • Link-state(shortest path first) 라우팅 알고리즘 실행
   • forwarding table (routing table) 생성

OSPF area

• OSPF 네트워크는 Area라고 불리는 하위 도메인(sub-domain)으로 나눠질 수 있다
  • 라우팅 DB사이즈를 줄일 수 있고(flooding 부담 줄임)
  • 네트워크 계층 구조를 구성할 수 있다(어떤 라우터가 백본에 더 가까운지 중요도가 정해짐)
• 한 area 내 라우터는 같은 area 라우터들과만 flooding
• 각 area 내의 area border router가 area 외부로의 패킷 라우팅 책임짐
• backbone router는 AS 영역 내 영역 간의 트래픽 라우팅
• 위 이미지에서 Broder router끼리 통용되는 프로토콜이 BGP

3. BGP (Border Gateway Protocol)

= Path vector Routing

Distance vs Path

• Distance vector advertisement: hop-count로 routing table
• Path vector advertisemnet: 목적지로의 path 정보로 routing table

BGP가 Path vector를 쓰는 이유 (distance vector도 충분하지 않나?에 대한 답)

• loop-free path selection 제공 (루프 방지)
• network 관리자(administrators)의 정책(service policies) 배포를 쉽게 해줌

• 목적지가 AS외부에 있는 경우 사용
  • 다른 AS로부터 subnet reachability 정보를 얻고, 그 정보를 AS 내의 모든 라우터로 전파하며, AS policy를 기반으로 subnet에 대한 '좋은'경로 결정
• Path-vecotr 알고리즘 기반
• semi-permanet(반영구적) TCP 연결 사용을 통해 BGP 메세지 교환

Terminology (용어)

• BGP speakers: AS내에서 BGP로 구성된 라우터들
• Border gateways: 둘 이상의 AS를 연결하는 BGP speaker
• External BGP (eBGP): 다른 AS간의 BGP
  • neighboring AS들로부터 subnet reachability를 얻음
• Interior BGP (iBGP): AS내에서 사용되는 BGP (동일한 AS 내의 eBGP speaker 간에 사용됨)
  • AS내의 모든 라우터로 subnet reachability 정보 전파
    

BGP session (advertising)

• AS간의 paths advertising (path vector..)
  • ex) AS3의 gateway router 3a가 AS2의 gateway router 2c에게 AS3, X로의 경로를 advertise
    -> AS3는 AS2에게 X로의 패킷을 전달할 것을 약속 (X: 주소 프리픽스가 X인 서브넷)
• gateway router는 같은 목적지에 대한 multiple paths를 배운다
  • AS1의 gateway router 1c는 2a로부터 AS2, AS3, Xpath를, 3a로부터 AS3, X path를 배움
  • policy에 따라, 1c는 AS3, X path를 선택하고, iBGP로 AS1의 모든 라우터에게 advertise

BGP Policy via advertisement

• 6개의 AS가 연결되어있고, customer network(ISP)인 w, x, y는 모든 트래픽의 목적지 또는 출발지여야만 한다는 조건을 만족하기 위한 policy는?
• w, y는 무조건 목적지 또는 출발지만 됨
• 하지만 x는 dual-homed (두 네트워크에 연결)
  • B에서 C로 갈 때 x를 들리지 않도록 policy가 적용되어야 한다
    -> 그래서 x는 C로 가는 길을 B에게 advertise하지 않는다 (이웃 B, C에게 다른 목적지로의 경로는 없다라고 알림, 알고있더라도 없다고함)

• A는 Awpath를 B와 C에게 advertise
• B는 BAw path를 C에게 advertise하지 않는다
  • C, A, w가 B의 고객이 아니라서 B가 CBAw를 라우팅한다해서 이득이 없기 때문
  • C는 CBAwpath를 배우지 못함
• C는 w로 가기 위해 CAw를 라우팅할 것 (B사용X)

Intra and Inter

Policy

• intra-AS: single admin만 존재하여 정책 결정 필요 X
• inter-AS: admin은 트래픽이 어떻게 경로를 통해 전달되는지, 누가 자신의 네트워크를 통해 경로를 설정하는지에 대한 통제를 원함 (정책 필요)

Scale

• hierarchical routing은 table 사이즈를 줄이고 트래픽을 감소시켜 Inter-AS에서 큰 이점을 제공
  (Intra-AS는 상대적으로 테이블이 작고 트래픽이 적음)

Performance

• intra-AS: 성능에 중점
• inter-AS: 정책이 성능 지배

SDN Control Plane

SDN(Software defined networking)

• control plane에 접근하기 위해 (원격)서버에 구현되어 있는 소프트웨어 정의 네트워킹 사용
• centralized control plane
  • 독립된(원격) 중앙 컨트롤러가 local control agent(CAs)와 상호작용
  • 중앙 컨트롤러가 전체 네트워크 상태 관리 및 라우팅 결정

why centralized control plane?

• easier network management
  • avoid router misconfigurations(구성 오류)
  • greater flexibility of traffic flows
• table-based forwarding은 라우터를 프로그래밍할 수 있게함 (OpenFlow API)
  • centralized 프로그래밍: 중앙에서 계산하고 분산시키므로 쉬움
  • distributed 프로그래밍: 각 라우터에 구현된 분산 알고리즘의 결과로 테이블을 계산해야되므로 어려움
• 제어 평면의 Open(non-proprietary비특허) 구현

특징

1. flow-based forwarding (openflow)
   • 이전의 IP데이터그램 포워딩이 온전히 목적지 주소를 기반으로 이루어지던 전통적인 방법과 대조적)
2. control, data plane separation
3. control plane function external to data-plane switches (네트워크 제어 기능이 데이터 평면 스위치 외부에 존재)
4. programmable control (프로그래밍이 가능한 네트워크)

SND 관점에서의 설명

• data plane switches
  • 빠르고, 간단한, 대중적인 스위치
  • 하드웨어에서 일반화된 data-plane forwarding 구현
  • 컨트롤러에 의해 게산되고 설치되는 switch flow table
  • 테이블 기반 스위치 제어 API 존재 (openflow)
  • 컨트롤러와 통신을 위한 프로토콜 존재 (openflow
• SDN controller (network OS)
  • 네트워크 상태 정보 유지
  • 상위 네트워크 control application과 northbound API로 상호작용
  • 하위 네트워크 스위치와 southbound API로 상호작용
  • implemented as distributed system (성능, 확장성, 오류 허용, 견고성을 위해)
• Network control apps
  • brains of control: SND controller에서 제공하는 낮은 수준의 API를 사용해 control function 구현
  • unbundled(분리 가능): 라우팅 공급업체나 SDN 컨트롤러와 별개로 제 3자에 의해 제공될 수 있음

Components of SDN

1. Interface layer to network control apps northbound
   • 네트워크 제어 애플리케이션들이 state management layer의 정보와 flow table을 읽고 쓸 수 있도록 인터페이스의 추상화
2. Network-wide state management layer (네트워크 전역 상태 관리 계층)
   • 네트워크 전역에 분산되고 견고한 상태 관리
   • SDN의 제어 결정을 위해 알아야하는 정보들이 최신이도록 관리 (네트워크 링크, 스위치, 제어되는 장치들에 대한 정보)
3. Communication layer southbound
   • 컨트롤러와 제어받는 장치들과의 통신 (컨트롤러가 장치를 제어하기 위해 정보를 전달하기 위한 프로토콜)
   • ex) OpenFlow

OpenFlow

• SDN컨트롤러와 제어되는 스위치/장치 사이에서 동작
• 메세지 교환을 위해 TCP 사용 (상황에 따라 암호화encryption)
• tree classes of openflow messages
  • controller to switch
  • asynchromous (switch to controller)
  • symmetric (misc) -> 양방향 통신

controller to switch message

• feature: 컨트롤러가 스위치 기능에 대한 정보를 쿼리하고, 스위치는 이에 대해 응답
• contigure: 컨트롤러가 스위치의 구성 매개변수를 쿼리하거나 설정 (스위치 동작 조정)
• modify-state: 컨트롤러가 openflow table에 있는 flow entries를 추가, 삭제, 수정 (스위치 전달 동작 동적 조절)
• packet-out: 컨트롤러가 특정 스위치 포트로 패킷 전송

switch to controller message

• packet-in: 스위치가 패킷 수신하면 해당 패킷과 제어 정보를 컨트롤러에게 전달
• flow-removed: 스위치가 flow table entry 제거 (컨트롤러에게 네트워크에서 어떤 흐름이 끊킴을 알림)
• port status: 스위치의 포트에서 변경이 있을 때 컨트롤러에게 알림

네트워크 operator는 직접 openflow 메세지를 만들거나 전송하면서 스위치를 프로그래밍하지 않는다. 대신 컨트롤러에서 제공하는 고수준 abstraction을 사용해서 프로그래밍한다

ex)

• 스위치 s1과 s2가 단절되어 s1, s3, s4로 들어오고 나가는 플로우 포워딩 규칙이 변경된 경우

1. s2와 링크 단절을 감지한 s1은 openflow의 port status 메세지를 사용해 링크 상태 변화를 SDN 컨트롤러에게 알림
2. openflow 메세지를 받은 SDN 컨트롤러는 링크 상태 관리자에게 알리고 링크상태 관리자는 링크 상태를 갱신
3. 다익스트라의 링크 상태 라우팅 담당 네트워크 제어 애플리케이션은 이전에 이미 링크 상태 변화가 있을 경우 알려달라고 등록해두었으므로, 알림을 받게 됨
4. 다익스트라 링크 상태 라우팅 애플리케이션은 네트워크 그래프 정보와 컨트롤러의 링크상태 정보에 접근하여 새로운 루트를 계산
5. 링크 상태 라우팅 애플리케이션은 갱신되어야 할 flow table을 결정하는 flow table 관리자(in SDNcontroller)와 접촉
6. 컨트롤러는 openflow를 사용해 링크 상태 변화에 영향을 받는 스위치들의 flow table을 갱신

SDN challenges

• control plane 강화
  • dependable(reliable), performance-scalable, secure distributed system
• 네트워크와 프로토콜이 실시간, ultra-신뢰성, ultra-보안과 같은 요구사항을 충족
• 대규모 인터넷 규모