네트워크는 규모가 크고, 관리하는 기관이 다양하기 때문에 autonomouse 시스템으로 나누어 짐
forwarding table은 목적직 subnet prefix와 경로를 가지고 있음
한개의 AS입장에서 볼때는 서브넷으로 가기위한 Intra-AS Routing Algotirhm을 통해서 경로를 결정 할 수 있었음
자신이 속해있는 AS가 아닌 다른 AS로 가기 위해서는 Intra-AS + Inter-AS Routing Algotirhm이 협력해서 목적시 subnet 주소를 발견하게 됨
Inter-AS task
AS1을 기준으로 보았을 때
•
AS2, 3와 같은 이웃 AS가 존재함
•
AS1은 AS3를 통해서 도달할 수 있는 subnet을 발견할 수 있어야하고, 마찬가지로 AS2 를 통해서 도달할 수 있는 Subnet도 발견할 수 있어야 함
◦
이후 밖에 있는 Subnet 정보를 Gatway router들이 알아와서 네트워크 전체에 알려주게 됨
•
inter-AS routing의 책임
◦
이웃한 AS로 부터 도달할 수 있는 서브넷이 뭐냐 = reachability information
◦
그리고 해당 reachability information을 AS 내에서 proagate한 역할을 해야함
포워드 테이블 셋팅 예시
1.
AS1은 Inter-AS routing protocol을 통해서 세상에 x라는 서브넷이 있고, AS3를 통해서 reach할 수 있다는 정보를 알아와야함
a.
해당 역할은 AS3에 연결된 게이트웨이 1c가 해당 역할을 수행
b.
1c는 AS전체에 정보를 propagetes 시킴
그런데 도달 방법이 multiple 하다면?
해당 사진에서는 X에 가는 방법이 AS3를 통해서 가는 방법과 AS2를 통해서 가는 방법이 유효함
•
1c는 AS3를 통해서 X에 도달할 수 있는 정보를 알아옴
•
1b도 AS2를 통해서 X에 도달할 수 있는 정보를 알아옴
•
그렇게 1c, 1b 모두 자신의 라우터 내에 해당 도달 정보를 퍼트리게 됨
•
그 경우 1d는 어떤 라우터를 골라갈 것이냐? ⇒ 이것도 Inter-AS 라우팅 프로토콜의 일임!
•
hot potato routing
◦
1c와 1b중 더 가까운 라우터는 어딘지 확인
▪
그건 우째 파악할까? intra-AS routing protocol을 통해서 얻어진 정보로 확인이 가능
◦
더 가까운 라우터를 x로 나가는 인터페이스로 결정함
inter-AS routing protocol 정리
1.
inter-AS routing protocol을 통해서 외부의 subnet에 접근할 수 있는 정보를 알아 냄
2.
도달 정보가 multiple 하다면 내부 게이트웨이의 최단경로를 알아냄 (intra-AS 라우팅 사용)
3.
그 중에서 가장 가까운 라우터에게 x로가는 게이트웨이로 결정 (hot potato routing)
4.
게이트웨이가 결정됬다면 해당 게이트웨이로 가는 인터페이스는 intra-AS routing protocol을 통해서 알아낼 수 잇음
인터넷에서 이용되는 라우팅 프로토콜
Intra-AS Routing
다른 말로는 interior gateway protocols (IGP) 이라고 불림
•
가장 일반적인 intra-AS 프로토콜의 종류
◦
RIP : Routiong Information Protocol
◦
OSFP : Open Shortest Path First
◦
IGRP : Interior Gateway Routiong Protocol (Cisco proprietary)
RIP
•
인터넷 가장 초창기에 사용되던 프로토콜
•
distance vector 알고리즘에 속함
•
1982년 BSD-UNIX 시스템 내장되어 distribution됨
•
소규모의 네트워크에서 적합함
•
RIP는 모든 링크 코스트를 1로 잡음 ⇒ 매우 단순한 방법
◦
따라서 distance matric이 홉 카운트임
◦
RIP에서 Maximum 홉 카운트는 15임
▪
16부터는 경로가 없다는걸 의미함
•
Advertisement 메세지에 distance vector를 실어서 이웃과 교환
◦
실릴 수 있는 목적지의 갯수가 25개임
◦
매 30초마다 이웃과 교환함
예제
라우터 D의 입장에서 생각해볼 때
목적지 Subnet | 다음 라우터 | 홉카운트 |
X | 없음 | 1 |
W | A | 2 |
Y | B | 2 |
Z | B | 7 |
RIP은 지속적으로 distance vector를 교환하는데 A가 Z로 가는걸 알려옴
•
Z 목적지로 가는 엔트리를 수정함
◦
다음 라우터는 A로, 홉카운트는 5로 수정
link filure, recovery
링크간 fail이 생겻을때는 Advertisement를 교환할 수 없음
•
180초 동안 Advertisement가 오지 않을 경우 해당 link가 fail 되었다고 생각
•
해당 루트로 가는 라우팅 테이블을 모두 invalidated를 함
•
자신의 디스턴스 벡터를 새롭게 계산하여 새로운 Advertisement를 자신의 이웃들에게 보내주게 됨
•
이웃들 역시 새로운 디스턴스 백터를 계산해서 변경이 있다면 새로운 Advertisement를 보내줌
•
ping-pong loops을 회피하기 위해서 poison reverse를 사용함
RIP table processing
•
RIP는 어플리케이션 레벨의 프로세스로 만들어짐
◦
프로세스의 이름은 route-d (deamon)
OSPF
RIP의 경우 최대가 15홉, 목적지는 25개 까지만 수용 가능하기 때문에 부족함이 생겼음
•
Open = publicly available
•
OSPF는 link state 알고리즘에 기반한 프로토콜임
◦
각 라우터는 LS packet을 네트워크 전체에 퍼트림
◦
모든 네트워크상의 라우터는 네트워크 토폴로지 맵을 그리게 됨
◦
토폴로지맵이 그래프로 모델링 됨
◦
해당 그래프를 모델로 다익스트라 알고리즘을 적용함으로서 라우트 테이블을 계산하게 됨
•
OSPF의 Advertisement에는 각 엔트리가 이웃별로 있음
•
OSPF 프로토콜은 IP바로 위에 구현이 되어있음
OSPF가 RIP에 비해서 향상된 점
•
규모가 크다면 hierarchical(구조적인) OSPF를 사용함
•
링크 코스트를 다양하게 사용 가능
◦
delay, bandwidth, money 등 다양한 링크코스트 사용 가능
◦
각자 LS Advertise가 필요함, 라우팅 테이블도 별도로 계산 필요
•
OSPF의 메세지들은 authenticated됨 (보안 요소)
•
멀티케스트 라우팅을 지원함 = MOSPF
•
동일 경로의 비슷한 비용의 PATH가 존재할 경우 모든 경로를 활용할 수 있도록 허용함
hierarchical OSPF
•
AS의 규모가 커지면 node와 link가 많아짐
•
규모가 커질 수록 LS packet이 많아짐 때문에 AS의 규모가 제한됨
◦
때문에 AS를 다시 Area로 나누게 됨
◦
그리고 LS broadcasting은 해당 Area내에서만 이루어지게 됨
•
다른 Area가는 길을 알수가 없음
◦
때문에 Area border routers를 두게 됨
◦
자신에 Area내엔 어떤 목적지 Subet이 있는지 그리고 각 거리를 나타내는 summarize를 서로 교환하게 됨
•
Area border router를 포함해서 backbone area가 구성이됨
◦
Area 들을 붙혀주는 역할을 함
◦
Backbone Area 내에서도 OSPF가 돌음
◦
때문에 Backbone Area내의 라우터들은 다른 라우터로 가는길을 정확히 알고있음
◦
그리고 해당 Area는 Boundary router를 통해서 다른 Area와 연결됨
•
hierarchy는 local area와 backbone으로 구성되어 있음
Internet inter-AS routing: BGP
각 AS는 자신이 원하는 라우팅 프로토콜을 선택할 수 있음
But 각 AS를 연결하는 프로토콜은 동일한 프로토콜을 사용해야함
때문에 인터넷에선 딱하나의 inter-AS 프로토콜이 사용되는데 그게 BGP임
•
BGP는 역할에 따라 2가지로 나누어짐
◦
eBGP : 서브넷 도달정보를 이웃 AS로 부터 알오는데 이용되는 프로토콜
◦
iBGP : 그렇게 알아온 정보를 라우트 내부에 퍼트리는 역할을 하는 프로토콜
◦
좋은 경로는 선택하는데 있어서 BGP가 가장 중요시하는건 Policy(정책)
BGP Basics
두개의 BGP 라우터들은 BGP 메세지를 교환함
•
semi-permanent TCP connections를 통해서 BGP advertis를 교환함
그런데 가령 AS3에서 prefix를 adversites를 한다면?
•
AS3는 해당 새로운 경로로 보내는걸 약속해준다는 의미
기본적인 BGP 동작
•
3a가 X에 대한 prefix reachability를 adversies할 경우
•
1c는 eBGP 세션을 통해서 해당 정보를 받음
•
1c는 iBGP 세션을 통해서 자신의 AS에 해당 정보를 알리게됨
•
1b는 X로 가는 경로를 2a에게 알리지 말지 결정할 수 있음
Path attributes and BGP routes
•
BGP 라우터들이 주고받는 경로 정보의 핵심적 내용은
◦
목적지 subnet의 prefix와 도달하기 위한 attributes로 구성됨
•
목적지 prefix의 구성
◦
AS-PATH : subnet prefix로 가기위해 거쳐야 하는 AS의 리스트를 보여줌
◦
NEXT-HOP : 다음 AS로 가기위한 라우터 정보
▪
왜냐하면 multiple 정보를 가지고 잇을 수 있기때문에 하나를 선택해서 보내줘야 함
•
받은 AS advertisement를 받은 후 우리의 AS 쓸것인지 말것인지를 결정하는 import policy를 적용함
BGP route selection
특정 서브넷으로 가는 경로가 여러개 있을 경우
1.
policy decision을 함
2.
shortest AS-PATH
3.
hot potato routing
4.
추가적인 criteria
BGP message
•
OPEN : 세션을 오픈하기 위한 메세지 = 이웃간 TCP 커넥션이 연결됨
•
UPDATE : 새로운 경로를 발견할 때마다 advertises를 하게됨 (혹은 중단 시킬대도 사용)
•
KEEPALIVE : OPEN 메세지를 받은 BGP 클라이언트는 해당 메세지로 ACKs을 하게 됨
◦
혹은 TCP 커넥션의 중단을 막고, 서로 연결되어 있다는걸 알리기 위해서 사용
•
NOTIFICATION : 이전 메세지에서 오류가 있다거나, BGP 세션을 종료하고 싶을때 이용
