5. Network Layer: Control Plane(2)

3. intra-AS routing in the Internet: OSPF

이전 장에서는 link state 알고리즘과 distance vector 알고리즘에 대해서 배웠다. 하지만 이 알고리즘들은 너무 이상적인 상황을 가정했다. 현실에서는 무수히 많은 라우터가 맞물려서 돌아가므로 routing table이 너무 크기 때문에, 이를 업데이트하고 계산하는데 엄청난 오버헤드가 발생하기 때문이다.

​

그렇기 때문에, 라우터의 autonomy를 강조해서 구성해보자는 의견이 나오게 되었다. 그렇게 등장한 것이 바로 AS(autonomous system)이다.

​

AS란 한 지역에서 관리하는 네트워크 라우터들의 집합 또는 동일한 prefix를 가지는 라우터들의 집합을 의미한다. 즉, 일종에 "도메인"이다.

​

그래서 이 도메인들끼리의 라우팅을 "inter-AS routing", 도메인 내부의 라우팅을 "intra-AS routing"이라 한다.

​

Intra-AS routing은 동일한 도메인에서 라우터들이 통신하기 때문에, 모두 동일한 intra domain protocol이 동작한다.

서로 다른 AS에 있는 라우터들은 서로 다른 AS routing protocol을 돌릴 수 있다.

그리고 게이트웨이 라우터 즉, 자신의 AS의 가장자리(edge)에 있는 라우터를 통해 다른 AS의 라우터와 연결해서 통신을 한다.

​

이 게이트웨이 라우터는 intra-AS 라우팅 알고리즘과 inter-AS 라우팅 알고리즘이 같이 돈다. 만약 동일한 AS 내에서 패킷을 보낼 때에는 intra-AS 라우팅을 사용하고, 다른 AS에 있는 destination에게 패킷을 보낼 때에는 intra-AS와 inter-AS 라우팅을 둘 다 사용한다.

​

Inter-AS task 란, 만약에 AS1에 있는 1d 라우터가 어떤 datagram을 받았다고 하자. 그런데 이 datagram의 목적지가 자신이 속한 AS의 라우터가 아니다. 그러면 이 패킷을 다른 AS로 보내야 하는데, 어느 링크를 선택해서 어느 AS로 보내야 할지를 판단하지 못한다.

그래서 inter-AS 라우팅 프로토콜이 해당 역할을 담당해줘야 한다.

그러기 위해서는 AS1에 있는 라우터들이 AS2를 통해서 전달할 수 있는 destination 주소와 AS3를 통해서 전달할 수 있는 destination 주소들이 어떤 것들이 있는지를 알아야 한다.

여기서 AS2나 AS3를 통해서 전달할 수 있는 네트워크 정보를 reachability information이라고 한다. 그러면 이 배운 정보를 가지고 동일한 AS에 있는 라우터들에게 전파 한다.

​

Intra-AS 라우팅은 IGP(Interior Gateway Protocol)이라고도 한다.

(참고로 inter-AS 라우팅은 EGP(exterior Gateway Protocol)이라 한다.)

​

Intra-AS 라우팅은 개발이 많이 되서 여러가지 프로토콜이 있는데, 대표적으로 RIP(Routing Information Protocl), OSPF(Open Shortest Path First), IGRP(Interior Gateway Routing Protocol)이 있다.

​

가장 유명하고 가장 많이 쓰이는 Intra-AS 라우팅 프로토콜인 OSPF를 알아보자.

​

OSPF는

· 무료로 사용할 수 있다.

· link-state 알고리즘을 사용한다.

· 다익스트라 알고리즘으로 구현이 되어있다.

· 각각의 노드가 모든 토폴로지 정보를 가지고 있다.

· TCP/UDP를 사용하지 않고 직접적으로 IP 프로토콜을 사용해서 dissemination을 한다.

· IS-IS routing protocol과 거의 유사하다.

​

OSPF의 아이디어를 알아보자.

​

기존의 네트워크가 너무 커서 LS나 DV를 사용할 수 없다고 해보자. 그래서 이 네트워크를 계층적으로 구조화한다. 즉, 자신이 담당하는 AS를 계층적으로 나눈다.

그래서 계층적으로 나누면 맨 위에는 boundary 라우터가 있다. 이 바운더리 라우터는 위 그림에 있는 AS와 다른 AS를 연결해주는 역할을 한다.

그 밑에 있는 라우터는 backbone 라우터로서 backbone area를 구성한다. 즉, 그 밑의 sub-area를 서로 연결해준다.

area border router는 자신의 area에 있는 라우터들의 정보를 수집해서 자신의 area의 라우터들에게 그 정보를 뿌려준다. 그리고 다른 area에 있는 라우터들에게 정보를 보낼 때의 정보를 알려준다.

​

즉, 하나의 AS를 백본과 local area로 나누고, 각 area에 속한 라우터들만 가지고 link-state 알고리즘을 구성해서 훨씬 가볍고 효율적으로 만드는 것이다.

​

만약 area가 너무 크면 동일한 방식으로 recursive하게 area를 계층적으로 나눈다.

​

4. routing among the ISPs: BGP

​

IGP의 대표주자인 OSPF를 배웠으니 이번엔 EGP의 대표적인 프로토콜인 BGP(Border Gateway Protocol)을 알아보자.

​

BGP는 inter-AS routing protocol의 사실상 표준(de facto)인 프로토콜이다.

(Intra-AS routing protocol은 여러 종류가 있었지만 inter-AS routing protocl은 BGP가 거의 표준이라고 보면 된다.)

​

BGP는 2개의 sub-protocol로 나누어진다.

· eBGP(external BGP)

- AS와 AS 간에서 사용되는 BGP

- AS와 AS 간의 라우팅 업데이트를 하는 용도

​

· iBGP(internal BGP)

- AS 내부에서 사용되는 BGP

- AS 내부에서 BGP 라우팅 정보를 교환하기 위해 사용

​

BGP는 고려해야 되는 점이 있는데, 우리가 good route를 결정하는데 reachability information 즉, 기술적인 이슈 뿐만 아니라 정책(policy) 즉, 정치적인 이슈 또한 고려해야 한다는 것이다.

​

1c와 2a, 2c, 3a가 바로 게이트웨이 역할을 한다. 이 라우터들은 eBGP와 iBGP가 같이 동작해서 포워딩 테이블이 유지가 된다.

​

X라는 라우터가 AS3에 새로 편입했다고 해보자. 그러면 AS3에서 게이트웨이 역할을 하는 3a는 2c에게 우리 AS에 X라는 라우터가 있으니, X에게 패킷을 보내고 싶으면 나에게 보내면 된다는 정보를 보내준다.

​

최종적인 루트는 prefix와 attribute로 결정이 된다.

​

attribute는 중요한 것이 2개가 있다.

· AS-PATH : 지금까지 prefix advertisement 거쳐온 AS들의 리스트들

· NEXT-HOP : 목적지 네트워크로 가기위한 경로에서, 바로 다음에 반드시 거쳐야할 특정 라우터

​

정책 기반 라우팅

지금까지는 기술적인 부분만 고려해왔지만, 정치적인 부분도 고려를 한다는 것이다. 게이트웨이는 import policy를 사용하는데, import policy란 AS-PATH를 받았을 때, 즉, 거쳐갈 수 있는 AS 리스트들을 받았을 때 거쳐갈 수 있는 도메인 영역이면 accept를 하고, 만약 절대 가서는 안되는 AS가 포함되어있다면 decline 한다.

​

AS는 정책에 따라 accept하면 해당 정보를 자신의 안에있는 라우터들에게 정보를 공유하고 이웃한 AS들에게 advertise 해준다.

 

예를 들어, X라는 라우터가 AS3에 추가가 됬다고 해보자. 그러면 AS3의 게이트웨이 역할을 하는 3a가 해당 정보를 AS2의 2c에게 보낸다. 그러면 2c는 이 정보를 받아들일지 말지를 결정하고, 받아들인다고 결정하면 자신과 같은 AS에 속하는 라우터들에게 해당 정보를 전파하고, 2a는 마찬가지로 해당 정보를 AS1의 1c에게 보낸다.

​

재밌는 점은 multiple path가 가능하다는 점이다.

AS3에서 AS2를 거쳐서 AS1으로 가는 것도 가능하지만, AS3에서 direct로 AS1에게 가는 방법 또한 가능하다. 그러면 AS1의 1c가 자신의 policy에 의해 어느 path로 할지 결정을 한다.

​

BGP route selection을 하기 위해서는 reachability information 뿐만아니라 policy decision, shortest AS-PATH, 가장 가까운 NEXT-HOP 라우터 등등을 고려해서 경로를 결정한다.

​

hot potato routing이란 AS 외부는 고려하지 않고 자신이 속한 AS내에서 코스트가 제일 작은 경로를 선택하는 것이다.

​

그렇게 내부에서 경로를 정하면 policy가 고려가 된다.

​

B에서 w로 패킷을 전송한다고 해보자. 경로는 BAw와 BCAw가 있는데, C입장에서는 나에게 속한 라우터가 아닌데 릴레이로 전달해 줄 이유가 없다(해준다고 해서 이득볼게 없으니까).

그래서 경로는 2가지가 있지만 BAw가 선택되는 것이다.

​

혹은 x가 w에게 패킷을 보낼 때를 고려해보자.

x는 B의 customer임과 동시에 C의 customer이다. 그러면 BAw 혹은 CAw의 경로로 전송한다.(BCAw 혹은 CBAw로 보내지 않는다.)

​

Intra-AS 라우팅과 Inter-AS 라우팅의 차이는 무엇일까?

​

Intra-AS 라우팅은 policy는 고려하지 않는다. 반면에 Inter-AS 라우팅은 policy를 고려한다.

​

또한 Intra-AS는 오직 퍼포먼스 즉, 성능만을 고려하지만, Inter-AS는 정치적인 policy가 좀 더 결정적인 역할을 한다.