CH5. Network Layer : The Control Plane

2. Routing Protocol

• Static Routing
  • 라우팅 경로가 한번 정해지게 되면 계속 그것을 사용하는 방식이다.
  • 네트워크 접속성은 네트워크의 상태와 존재에 따라 독립적이다.
• Dynamic Routing
  • 네트워크 상태에 따라 routing이 바뀌게 된다.
  • 라우터간에 계속해서 정보교환이 일어나고 그를 통해 최적의 경로를 알아낸다.
  • routing ocilation 같은 문제점이 일어날수가 있다.

• Global vs Decentralized Information
  • Global information
    • 모든 라우터들은 각각 완벽한 topology,link cost 정보를 가지고 있다.
    • "link state" algoritm
  • Decentralized information
    • router들은 자기와 직접적으로 연결된 이웃까지의 cost를 알고있다.
    • 모든 router와의 정보교환이 아닌 자신의 이웃과의 정보 교환이 이루어진다.
    • "distance vector" algorithm
• A Link-State Routing Algorithm
  • Dijkstra's algorithm
  • Forward search algorithm : src부터 시작해서 dest까지의 best path를 알아내는 방식이다.
  • OSPF를 사용한다. : AS내의 라우터간에 정보 교환하는 라우팅 프로토콜을 의미한다.
  • No convergence problem (convergence : 어떤 라우터에서 정보의 변화가 일어났을때 다른 모든 라우터까지 해당 정보가 퍼지는데 걸리는 정도를 의미한다.)
  • 각각의 라우터들은 자신과 이웃과의 거리를 모든 다른 라우터들에게 알려준다.
  • 각각의 라우터들은 완전한 topology를 알고있고 각 목적지에 대한 최선의 경로를 계산하게 된다.
  • time complexity가 O(n^2)이다. -> 각각의 노드에서 최소 경로를 계산 하기때문이다.
  • heap을 사용하게 되면 O(nlogn)이 되게 된다.
  • 예시

3보다는 2가 더 작은 코스트 이므로 3을통한 path가 아닌 1->1 path를 취한다.
마지막 단계로 가는데 두개의 경로가 있는데 cost값이 더 작은것을 취하게 된다.

• 표로는 아래와 같이 표현을 할수가 있다.

• Distance Vector Routing Algorithm
  • call as Bellman-Ford
  • Backward search algorithm이다.(목적지에서 부터 시작하여 최적의 경로를 찾는다.)
  • 각각의 라우터들은 자신의 이웃이 어딨는지와 얼마나 걸리는지에 대한 정보를 가지고 있다.
  • 모든 라우터에게 정보를 알리지 않고 이웃들에게만 알리게 된다.
  • 거리 계산 방법
  • 각각의 노드가 주기적으로 자신의 distance vector를 측정하여 이웃에게 보낸다.
  • 각각의 노드는 주변 노드와의 상관관계를 모두 계산하여 그중 최솟값을 취하는 방식이다.
  • Dx(y)<-min{c(x,v)+Dv(y)} for each node y
  • Dx(y)는 x에서 y까지 가는데 최소의 코스트를 의미한다.

• Distace Vector Count-to-Infinity Problem
  • slow convergence problem : 네트워크에 어떤 변화가 일어난후, 전체 라우터가 그 네트워크에 대하여 동일한 정보를 공유하는데 까지 오랜 시간이 걸리게 되는 문제가 있다.

• Count-to-Infinty의 해결법
  • B가 C에서 A로 가는 경로가 자신을 통해 가는것임을 인지하지 못하기 때문에 일어나는 문제로 그것을 알려줄수 있도록 하면 해결이 될수 있다.
  • 특정 distance(cost)가 넘게 되면 못가는 것으로 판단하게 한다.
  • 변화가 생기게 되면 바로바로 알려줄수 있도록 한다.
  • 나쁜 소식(router 하나가 끊기는 일)이 발생할 경우 전체가 이것을 알때까지 기다린다.
  • 전달 방향을 알려주어 자신을 통해 전달된다는 것을 알려준다.
  • Split horizom with poisoned reverse
  • 라우터가 이웃 라우터 N에게 N이 그 목적지로 가는 다음 홉이라면 dstination 까지의 거리가 무한대라고 알려준다.
  • 자기 자신에게 다시 데이터가 돌아 오는것을 막기 위함이다.
  • 반대 방향으로 가는 것을 막기.

3. Intra-AS routing in the Internet : OSPF

• Internet approach to scalable routing
  • AS(Autonomous systems) : domain이라고 알려져 있는 것으로 router들을 여러개 묶은 하나의 지역을 의미한다.
  • 계층적 구조로 접근하기
  • : Intra-Domain => 도메인(AS) 내의 router간에 routing을 하기 위한 알고리즘
  • : Inter-Domain => 도메인(AS) 간에 routing 하기 위한 알고리즘
• Intra-domain Routing
  • 한 도메인 내에 있는 router들은 모두 같은 routing protocol을 사용하여야 한다.
  • IGP(Interior Gateway Protocol)로 잘 알려져있다.
  • gateway router : AS의 말단에서 다른 AS와 연결되어 있는 router를 의미한다.
  • Intra-AS의 주요 routing protocol

약어	풀네임
RIP	Routing information protocol
OSPF	Open Shortest Path First : Link State 차원(Dijkstra)
EIGRP	Enhanced Interior Gateway Routing Protocol

• Inter-domain Routing
  • 다른 AS와 정보전달을 하는 router
  • EGP(Exterior Gateway Protocols)로 잘 알려져있다.
  • BGP : Border Gateway Protocol (Intra Domain에서 받은 내용을 다른 AS로 뿌려주기 위한 protocol)
• Interconneted AS's
  • AS1은 중간에서 AS2와 AS3를 통해 목적지 까지 갈수 있음을 배우게 된다.
  • AS1 내의 모든 router들은 AS2~AS3 까지 가는 정보를 forwarding table에 저장하게 된다.
  • forwarding talble은 intra-AS와 inter-AS라우팅 알고리즘을 통해 결정되어 진다.
  • Intra-AS 집합들은 내부 라우터 간의 forwarding entry들을 알고 있다.
  • Inter-AS와 Intra-AS은 외부 라우터까지 가는 방법에 대한 entry를 가지고 있다

4. Intra-Domain Protocol

• RIP(Routing Inforamtion Protocol)
  • Intra-domain 의 프로토콜중 가장 유명한 것이다.
  • Interior Gateway Protocol
  • Distance Vector Routing Algorithm(convergence problem존재)
  • hops 에 대한 정보를 가지고 있게 되는데 이는 최대 15까지 늘어날수 있다.(그 후는 무한으로 취급하여 갈수 없음)
  • 주기적은 정보교환을 통해 update가 일어난다.
  • split horizon with poisoned reverse => 이 둘은 convergence problem의 해결을 위해 도입
  • VLSM을 지원하여 준다.(각 서브넷 마다 가변길이의 서브넷 마스크를 지원하는 것 : class less)
  • Authentication 을 지원하여 준다.=> v2에서만 지원을 한다.
• OSPF(Open Shortest Path First)
  • Intra-Domain의 프토토콜중 하나이다.
  • Link State Routing Protocol(convergence problem 이 존재 하지 않는다.)
  • Flooding을 통해 동일한 AS내에 있는 router들에게 정보를 전달하게 된다.(계속해서 flooding이 되는것을 막기 위해 area라는 개념을 도입하였다.)
  • Authentication을 지원한다.(보안에 신경을 쓸수가 있다.)
  • 부하를 줄이기 위해 해당 router서 가는 경로가 a,b 두가지 있을 경우 한번은 a로 또다른 한번은 b로 보낸다.(load balancing, a,b의 홉은 동일한 경우여야 한다.)
  • 내부서 두개의 계층 구조로 나누어 지게 된다.(Area, routing을 좀더 효율적으로 관리가 가능하다.)
  • OSPF는 Multicast를 지원하여 준다.
• Hierarchical OSPF
  • 두가지 레벨의 계층 구조를 가지고 있게 된다 : local area, backbone
    • 각각의 지역 내에서만 정보를 주고 받을수가 있게된다.
    • 각각의 라우터들은 자신이 해당한 지역 토폴로지를 알고있고 다른 지역으로 가는 것의 경우 shortest path만 알 뿐이다.
  • ABR(Area Border Routers) : 해당 Area의 정보를 요약해 그 정보를 다른 Area의 router에게 알려주는 역할을 하게 된다.
  • ASBR(AS Boundary Router) : 다른 AS와 연결된 router를 의미한다.

4. Inter-AS routing : BGP

• BGP(Boder Gateway Protocol)
  • 알고리즘을 통해 최선의 경로를 찾는 것이 아닌 policy를 가장 우선으로 하는 protocol이다.
  • 각각의 AS마다 모두 다른 algorithm을 사용할수 있기 때문에 algorithm으로 통일하는것은 어렵다.
  • Path-vector(Distance vector에서 convergence problem을 해결한것)을 사용하게 된다.
  • 비교적 간단한 프로토콜이지만 구성이 복잡하다.
  • eBGP : AS사이에서 정보를 교환 하는 것을 의미한다. (자신의 AS에서 다른 AS로 도달이 가능한가)
  • iBGP : AS 내부에서 돌아가는 것으로 외부로 부터 갈수 있는 정보를 받아서 내부에 있는 router에 알려줄때 사용이 된다.
• BGP Basics : Path advertisement
  • AS 간에 정보 전달을 하기 위해서는 eBGP를 사용한다.(빨간색 점선)
  • AS내의 router에게 정보를 전달하기 위해서는 iBGP를 사용한다.(파란색 점선)

• Path attributes and BGP routes
  • attributes : AS-PATH(자신이 dest까지 가기 위해서 거쳐야 하는 AS list), NEXT-HOP(AS에서 다른 AS로 넘어갈때 거쳐야 하는 router)가 존재한다.
  • 아래와 같은 경우 AS1의 1c 라우터는 AS3에서 알려주는 X,3a,AS3의 경로와, AS2에서 알려주는 X,2a,AS2,AS3의경로를 배우게 되는데 이중 selection rule(policy)를 통해 하나의 경로를 선택하고 iBGP를 통해 내부의 router에게 해당 경로를 알려준다.

• BGP : Route Selection
  • 하나의 라우터가 하나의 목적지에 대해 두가지 이상의 path를 배우게 될때 어떤 것을 고를지에 대한 것이다.
    1. local preference value attribute : policy decision
    2. The shortest AS-PATH : AS 를 최소한으로 거치는것을 선택한다.
    3. The closest NEXT-HOP router : hot potato routing (자기의 AS에서 가장 작은 cost로 보내게 된다, 전체적인 cost가 가장 작은 것이아닌 일단 자기를 기준으로 가장 짧은 곳으로)
    4. Additional criteria
• Hot Potato Routing(가장 가까운 곳으로 보내는 방식이다.)