지난 시간 배운 내용

routing protocol을 배우기 전에 routing algorithm(path selection)을 보고 있음.

내 라우터로부터 어떤 destination subnet으로 가기 위한 next hop을 계산하는, 나로부터 같은 ISP에 속해있는 라우터까지의 경로를 계산하는 것만 보고 있음.

path selection 알고리즘 두 가지.

link state 알고리즘은 내가 가야하는 ISP로 가기 위해 내 ISP에 나 빼고 n-1개의 라우터로의 경로를 계산하기 전에, 라우터들이 어떻게 연결 되어있고 link의 cost가 어떤지를 각 router가 broadcast로 다 알려줌. 각각의 라우터가 자신에게 physically 연결되어 있는 link 정보를 broadcast ⇒ OSPF. 모든 라우터가 똑같은 global complete topology를 갖고난 후에야(시간이 걸림) 계산을 시작. dijkstra algorithm에서 한 번 loop을 돌 때마다 n-1개 중 어느 한 라우터로 가는 least-cost path가 계산 됨. n-1번의 iteration을 거치면 n-1개의 라우터로 가는 least-cost path가 계산 됨. 어느 라우터로(next hop) 보내야 least-cost path인지가 계산됨.

즉, dijkstra algorithm으로 계산하려면, 그 link state algorithm을 쓰는 routing protocol은 dijkstra를 running 하기 전에 모든 global한 topology 정보를 주고 받는 message action을 define 해야 한다. (OSPF는 그것을 함)

OSPF가 link state algorithm을 사용하는 routing protocol이라는 말은, dijkstra 알고리즘으로 나로부터 n-1개의 라우터로 가는 least-cost path를 계산하기 전에, 라우터들끼리 자기네들의 global한 topolgy를 완전히 알기 위해서 자신의 local 정보를 주고 받는 msg와 받으면 취해야 하는 action과 order을 정의해놓은 프로토콜이라는 것.

distance vector 알고리즘은 내 바로 옆에 있는 라우터들한테서만 정보를 얻음. neighbor로 붙어있는 애들이 자신으로부터 도달할 수 있는 n-1개의 path 정보와 cost, next hop등의 측정값을 나한테 알려줌. (확실한 건 나로부터 한 hop까지의 거리 뿐). 내 이웃이 알려준 정보로 계산하고, 또 정보를 받고, 계산하고 iterative하게 동작. slow converge. 그래서 작은 망에서 쓰는 경향이 있음 (RIP도 그렇다)

LS 알고리즘의 특징은 link state algorithm을 쓰는데 dijkstra algorithm을 running하면, 결과적으로 나오는 end2end path가 트리 구조를 갖는다. → loop이 없다는 것을 보장 가능.

반면, DV 알고리즘을 쓰는 경우의 단점은 나쁜 소식이 느리게 가는 것. 어떤 하나의 라우터에 연결된 link의 cost가 극도로 나쁘게 변화 했다면, 나쁘게 변화된 정보를 빨리 알려주는 대신 이웃에게 들었던 정보로 dst 값을 다시 계산하는 순간, 내 이웃이 나한테 들은 정보를 다시 활용하는 문제가 있었음. 결과적으로 내 이웃은 나를 통해 가는 정보였기 때문에, 그 destination으로 가는 pkt을 나한테 던질테고, 나는 걔가 내가 알려준 정보로 계산한 값인줄 모르고 또 그것을 활용. link cost 값이 너무 높아졌기 때문에 나는 다시 걔한테 던짐. 이렇게 loop, 블랙홀이 생김.

심각하게 cost가 늘어난 애의 cost에 도달할 때까지 계속 loop을 돌게 됨. 그 cost에 도달하고 나서야 얘가 더 나아지니까 다시 계산. 그건 count to infinity problem.

count to infinity problem을 해결하기 위한 방법으로 1. split horizon: 내가 알고 있는 어떤 distance vector 값이 A에게 들어서 계산한 값이면 그 값을 A에겐 다시 안 준다. 2. split horizon with poison reverse: 주긴 주는데 "너에게 받았다"는 것을 알려준다는 표시로 ∞ 값을 넣어줌.

split horizon은 distance vector가 주는 size가 줄음. split horizon with poison reverse는 이웃에게 주는 메시지의 크기는 커지나 메시지가 좀 더 확실해진다는 장점이 있음.

결과적으로 split horizon & split horizon with poison reverse으로도 못 막는 경우는 세 개의 라우터가 물리적으로 loop을 형성하고 있는 경우. → 세 개 이상의 라우터가 loop을 형성하지 않도록 topology를 형성 해야함.

(loop이 생긴다 = 어떤 특정 destination으로 가는 user pkt이 destination으로 못 가고 router를 도는 것)

이걸 막기 위해 IP header에서 router 하나를 거칠 때마다 그 값이 1씩 줄어드는 TimeToLive 필드를 사용함. 0이 되면 라우터가 drop 해버림. IPv6는 hopLimit.

라우팅 프로토콜이 loop 도는 잘못된 라우팅 테이블을 갖고있는 시간 동안 들어온 pkt은 빙빙 도니 TTL을 잘 조작하면 제거할 수 있음.

---

Hierarchical routing: Autonomous Systems (AS)

Autonomous System. 하나의 domain

IP addr자체가 hierarchical 하게 할당 되어 있음. 이렇게 할당 하다보니 aggregation 해서 routing 정보가 올라가기도 한다.

routing 하는 것도 한 ISP내의 traffic은 그 안에서 해결하고, 한 ISP = 하나의 AS(자치 시스템)를 넘어가는 traffic에 대한 routing은 다른 관점에서 protocol이 관장하는 것.

그 ISP 안에서는 어떤 정책을 쓸지는 자율적. 단, 하나의 AS안에 있는 router들은 같은 protocol을 사용해야 함.

32 bit integer AS number (ASN)

라우터당 하나씩 주는 number. '나는 어떤 AS에 속한 라우터구나'

어떤 라우터와 통신할 때 그 라우터가 나와 같은 AS에 속해있는지가 중요. → 행동 양식이 다름.

따라서 router를 configuration할 때 ASN number를 넣어줘야 함.

• 같은 AS에 있는 router는 같은 routing protocol을 돌린다: Intra-AS routing protocol (OSPF, RIP ..)
• Gateway router: 이쪽 port에 연결된 router는 나와 같은 ASN, 저쪽 port에 연결된 router는 나와 다른 ASN이라면 그 router는 border에 있는 gateway router인 것. (ASBR: AS Border Router)
  → ASBR은 inter-AS routing을 하기 위한 BGP를 running 하고 있어야 함.
  inter-AS routing은 policy-based routing.

AS

• transit AS: 통과해(경유) 다른 AS로 갈 수 있는 AS (departing & arriving & passing=transit)
• stub AS: 하나의 ISP와만 연결되어 있는 AS (departing & arriving only)

Internet approach to scalable routing

gateway router(ASBR)은 intra-AS, inter-AS 모두를 running 하고 있어야 함.

두 가지 정보를 조합하여 내 next hop을 결정.

결국 라우터가 FIB에 넣어야 하는 건 destination subnet으로 가는 최종 output port.

intra-AS routing (Interial Gateway Protocol = IGP)

• 같은 AS 안의 모든 router들이 같은 intra-domain protocol을 돌리고 있음.
• 다른 AS의 라우터들은 다른 intra-domain protocol을 돌릴 수 있다.

inter-AS routing (Exterial Gateway Protocol = EGP)

• routing among interconnected ASes

  

5.3 Routing Protocols in the Internet

unicast: 1 src IP → 1 dst IP

Intra-As Routing Protocol

Interial Gateway Protocols (IGP)

• RIP: Routing Information Protocol
• OSPF: Open Shortest Path First (IS-IS protocol essentially same as OSPF)
• IS-IS : Intermediate-System to Intermediate-System; standardized by the
  ISO(International Organization for Standardization) in 1992
• IGRP: Interior Gateway Routing Protocol (Cisco proprietary)

• Classful하게 design된 protocol들은 field에 subnet mask가 필요 없음.
• Classless하게 design된 protocol들은 field에 subnet mask가 필요함.

5.3 intra-AS routing in the Internet

RIP (Routing Information Protocol)

router를 지나가는 user의 가입자 패킷은 layer 3까지만 지나가나, RIP msg는 layer 5까지 올라갔다 내려옴.

• RIP routing tables managed by application-level process called “routed” (daemon) ; included in BSD-UNIX distribution in 1982
• advertisements sent in UDP packets(multicast로 주고 받음), periodically repeated

RIP algorithm & msg format

• distance vector algorithm을 주고 받을 때 쓰는 메시지 format을 정의
  • Metric=hopcount(max=15hops), each link has cost 1
    가장 멀리 떨어진 라우터가 15 hop 정도 떨어진 크기의 NW에서 사용
  • Routes with a hop count > 15 are unreachable.
  • DVs (aka advertisement) are exchanged with neighbors every 30 sec.
  • Each advertisement contains up to 25 destination subnets (IP address)

RIP: Slow convergence problem & Solutions

DV algorithm의 문제점인 Count to infinity problem을 가짐.

만약 A가 B를 통해 목적지 x로 가는 경로 설정을 했다면, A는 B에게 x까지의 거리가 ∞라고 알린다.

즉, A는 B에게 Da(x) = ∞ 라고 알림으로써 B는 A에게 x로 가는 경로가 없다고 믿으므로, B는 A를 통해 x로 가는 경로를 시도하지 않을 것이다.

OSPF

OSPF는 링크상태를 area 내에서 flooding하고 다익스트라 알고리즘을 사용하는 Link State 알고리즘.

OSPF를 사용하는 라우터는 인접한 라우터만이 아니라 AS내 다른 모든 라우터에게 라우팅 정보를 broadcast.

라우터는 링크 상태가 변경될 때마다 링크 상태 정보를 broadcast. 변경되지 않았더라도 정기적인 broadcast.

• Link state algorithm
  • Metric based on type of service : Bandwidth, Minimum delay(RTT), max throughput, reliability.
  • OSPF를 이용해 각 라우터는 전체 AS에 대한 완벽한 토폴로지 그래프를 얻는다.
  • 각 라우터는 자신을 루트로 두고 모든 서브넷에 이르는 최단 경로 트리를 결정하기 위해 각각 다익스트라를 수행한다.
  • 관리자는 모든 링크 비용을 1로 설정함으로써 최소 홉라우팅이 이루어지게 하거나, 적은 대역폭을 가진 링크 사용을 억제하기 위해 링크 용량에 반비례하게 링크 가중치를 설정할 수 있다.
• Two-level hierarchy
  • broadcast limit을 정하기 위해 AS를 또 두 area로 나눔. : local areas, one backbone area
    → area 안에서만 topology를 share, broadcast, area 끼리는 backbone area를 통해 통신.
  • Link-state advertisement(LSA) flooded to only in area.
    carried directly over IP (RIP는 UDP, BGP는 TCP, OSPF는 IP위에서 실행)
    - area border routers(ABR): area 외부로의 패킷 라우팅
    - backbone routers: ABR들을 연결하기 위한 라우터, area간의 트래픽을 라우팅.
    - boundary routers(ASBR): 다른 AS와의 경계에 있는 라우터. OSPF와 BGP 동시에 수행

OSPF: Two-level hierarchy

같은 영역(area) 내의 라우터들에게만 링크 상태를 flooding(broadcast) 후 다익스트라 실행. (속도 up)

backbone에서는 OSPF 프로토콜을 돌리지 않고 DV algorithm을 사용 (loop-free topology 보장)
⇒ 3개 이상의 라우터가 loop를 가지면 안 된다.

RIP vs OSPF

• OSPF는 dijkstra(link state algorithm)을 사용하고 use DV algorithm for backbone area

---

Keywords

• Hierarchical routing

-- Autonomous system(AS)

-- intra-AS routing(OSPF, RIP) v.s. inter-AS routing(BGP)

• RIPv2 v.s. OSPFv2,
• (Q) Why do we need to construct a loop-free inter-area topology in a backbone area (area0) of OSPF?

(A) In order to avoid a loop that may be caused by a distance vector algorithm used in the backbone area