[Computer Network] Network Layer(3) - Unicast Routing

"Network Layer"의 주된 서비스 중 하나는 Routing이며, 

"Routing"은 Source부터 Destination까지 최소 비용인 경로를 결정하는 작업을 의미한다.

 

이러한 Routing은

1:1 통신일 경우에는 "Unicast Routing"

1:N 통신일 경우에는 "Multicast Routing"으로 구분된다. 

이번 포스팅에서는 Unicast Routing에 대해 알아보자.

 

 

Hop-By-Hop Routing 

다음과 같은 네트워크가 있다고 가정해 보자. 

 

해당 네트워크에서 A부터 B까지 최소 비용 경로는 라우터 "u-x-y-z"를 거친다.

 

만약 Router가 경로상에 있는 모든 Router정보를 안다고 가정해 보자. 

해당 예시에선 "u-x-y-z"로 짧지만, 인터넷 상에서 Router의 갯수는 무수히 많다. 

해외에 있는 친구와 카톡을 주고 받는다면, 수많은 Router를 거치게 될 것이다. 

즉, Router가 경로 상의 모든 Router정보를 안다면, 

Router가 알아야 할 정보가 많아지게 되며, 이는 인터넷 속도가 느려지게 될 것이다. 

따라서, Router는 다음과 같이 목적지에 따른 "다음 Router 정보"만 알고 있다.

이렇게 데이터가 여러개의 Router를 거쳐 전달되는 모습을 보고 Hop-By-Hop Routing이라 부른다. 

 

Routing vs. Forwarding

Routing 알고리즘을 통해 최소 비용인 경로가 결정 나며, 

이 과정에서 각 Router의 Forwarding Table이 업데이트 된다.

 

즉, 앞선 예시에서 A부터 B로 가는 경로는 여러 가지가 있다. 

그중 Routing 알고리즘을 통해 "u-x-y-z"가 최소 비용 경로라는 것을 알게 되었다.

 

이때 앞서 각 Router는 다음 목적에 따른 다음 Router 정보를 가지고 있다고 했는데, 

해당 정보는 Forwarding Table에 저장된다.

각 Router는 이 "Forwarding Table"를 통해

목적지 정보를 보고 최단 경로상에 있는 다음 Router로 가는 출력 포트로 데이터를 위치시킨다. 

 

"Forwarding"은 Forwarding Table을 보고 다음 Router로 이동하는 포트로 패킷을 위치시키는 작업을 의미한다.

 

"Routing"을 알고리즘과 같이 SW적으로 동작하지만, "Forwarding"은 HW적으로 동작한다.

 

 

Routing Algorithm

"Routing 알고리즘"은 네트워크 상에서 Source부터 Destination까지 최소 비용 경로를 찾는 알고리즘이다.

IP 프로토콜은 이러한 Routing과정에서 Forwarding Table을 업데이트한다. 

 

이러한 Routing에는 크게 2가지로 구분된다.

• Link-State Routing : 전체적인 네트워크 상황을 토대로 경로를 찾는 Routing
• Distance-Vector Routing : 연결된 이웃 Router의 정보만을 가지고 경로를 찾는 Routing 

Link-State Routing 알고리즘에는 대표적으로 Dijkstra 알고리즘이, 

Distance-Vector Routing 알고리즘에는 Bellman-Ford알고리즘이 대표적인 예시이다.

 

Link-State Routing

"Link-State Routing"은 각 Router들이 "전체 Network 상황을 이해"하고 경로를 찾는 Routing이다. 

각 Router들은 자신과 연결된 Router의 상태(Link-State)를 다른 Router와 교환해

최종적으로 전체 네트워크 상태가 저장된 LSDB를 생성한다.

 

이후 Routing과정에선 이 LSDB를 보고

다익스트라 알고리즘을 통해 최소비용의 경로를 선택한다.

 

Distance-Vector Algorithm

"Distance-Vector Routing"은 "전체 Network 상태는 알지는 못하고",

이웃 Router의 정보를 가지고 최소 비용을 찾는 Routing방식이다.

 

우선, 초기에 Router는 이웃 Router 간의 비용을 기반으로 테이블을 생성하는데, 이를 "Distance-Vector"라 부른다. 

이러한 Distance-Vector를 Bellman-Ford 알고리즘을 통해 끊임없이 교환한다.

 

Bellman-Ford알고리즘은 다음과 같이 수행된다. 

 

초기에는 다음과 같이 Distance-Vector는 이웃 Router간의 비용만을 가지고 있다. 

 

이후, 이러한 Distance-Vector를 이웃 Router와 교환을 해,

이웃 Router를 거치는 경로가 더 작다면 Distance-Vector를 업데이트한다.

만약, Distace-Vector의 업데이트가 일어났다면, 이웃 Router에 전달하고, 

업데이트가 일어나지 않았다면 전달하지 않는다.

 

이후에 특정 Router사이의 비용이 변경되었다면, 변경된 Router를 기준으로 다시 D-V를 교환한다. 

 

Count to Infinity

Distance-Vector Routing에는 Count to Infinity 문제가 있는데, 예시로 해당 문제를 살펴보자.

초기에 다음과 같이 y가 z로 D-V를 전달해 z가 D-V를 업데이트 진행한다.

 

이때, x-y사이 연결이 고장 났다고 가정해 보자.

y Router를 x로 가는 비용을 INF로 업데이트할 것이다. 

 

하지만, 앞서 z Router의 D-V가 변경되었기 때문에, 전달하게 되고, 

x Router의 D-V가 업데이트된다.

 

이때, x Router의 D-V가 업데이트되었으므로 이를 z Router에게 전달한다. 

z Router는 자신의 다음 Router(Next Router)에서 온 정보이기 때문에 D-V를 수정한다. 

 

이 중 3번과 4번 과정을 무한히 반복하게 되는데, 해당 현상을 "Count to Infinity"문제라 부른다.

 

Posion Reverse

"Posion Reverse"는 무한루프를 방지하기 위한 방법으로 

상대방 이웃 Router를 경유하는 최소 경로 비용을 INF로 변경하여 통보하는 방법이다.

 

이전 예시를 다시 한번 살펴보자!

문제가 발생했던 원인은 z Router가 자신의 "Next Router"로 D-V를 전달했기 때문이다. 

 

따라서, 자신의 "Next Router"에게 D-V을 전달할 때는 다음과 같이 INF를 전달하는데

이러한 방법이 Posion Reverse방법이다.

 

하지만 이러한 Posion Reverse방법은 2개의 노드에선 잘 동작하지만, 

3개 이상의 노드에서 Count to Infinity문제가 발생할 경우 해결이 불가능하다.

 

 

Unicast Routing Protocol

Unicast Routing Protocol은 "어떠한 Routing Algorithm"을 사용했냐에 따라 구분된다. 

• RIP: Distance-Vector Routing Algorithm 기반
• OSPF: Link-State Routing Algorithm 사용
• BGF: Path-Vector Routing Algorithm 사용

 

AS (Autonomous System)

"AS"란 Internet상의 개별적인 Routing관리 Domain이다.

 

Internet은 KT, SKT, LG와 같은 기관들이 운영하는 네트워크들이 연결된 형태인데, 

이러한 독립적인 네트워크를 AS라 부른다. 

각 AS는 독립적인 Routing Protocol을 적용할 수 있다.

 

따라서, Routing Protocol은 AS 내부에서 사용하는 프로토콜과, 

AS 간에 사용하는 프로토콜로 구분된다. 

 

"Intra-AS Routing Protocol"는 AS내부에서 사용하는 Routing Protocol로,

대표적으로 RIP, OSPF 등등이 있다. 

 

"Inter-AS Routing Protocol"는 AS간에 사용하는 Routing Protocol로,

Internet에선 BGP만 사용된다.

 

 

RIP (Routing Information Protocol)

"RIP"는 초기 IP와 함께 개발된 최초의 Intra-AS-Routing Protocol로, 

Distance Vector Routing Algoritm을 "단순화" 시킨 Routing방식이다.

 

동작 방식 

앞서 말했지만, Distance-Vector Routing을 단순화시킨 Routing 방식이다.

 

RIP에선 모든 링크의 비용을 전부 1로 설정한다.

즉, Hope Count가 Routing의 비용이 된다. 

 

Distance-Vector Routing방식에선 무한루프로 인한 Count to Infinity문제가 발생하는데,

RIP에선 이를 해결하기 위해 최고 경로 비용을 15로 설정한다.

경로 비용이 16인 경우 무한대로 간주해 해당 경로를 유효하지 않는 경로로 처리한다.

 

RIP Message

RIP는 2종류의 메시지를 주고 받으며 Distance-Vector를 형성한다. 

• Response Message
• Request Message

"Response Message"는 "Request Message"의 응답으로 송신이 될 수도 있지만, 

이웃 Router에게 자신의 Routing정보를 알리기 위해 약 30초마다 계속 송신한다.

이러한 성격에 Advertisement Message(광고 메시지)라고도 부른다.

 

만약 이웃 Router로부터 Response Message가 없으면, 

해당 경로는 유효하지 않는 경로로 간주해 16(무한대)로 비용을 설정한다.

 

"Request Message"는 Router가 초기화되었거나, 

특정 Router의 비용이 16으로 설정되어, 해당 경로로 갈 수 있는지 주변 Router에게 물어볼 때 사용한다.

 

 

문제점

RIP는 다음과 같은 이유에서 현대는 거의 사용하지 않는다.

 

우선 가장 큰 문제점은 약 30초마다 Response Message를 보내는 과정에서 Routing Traffic이 많아질 수 있다. 

 

또한, Forwarding Table의 수렴속도가 매우 느리다. 

만약 한 Router에서 Forwarding Table에서 변경이 일어났다고 가정해 보자.

Routing 정보가 매번 약 30초마다 전송되는 것을 고려한다면 

멀리 떨어진 Router가 해당 정보를 받아 보는데까진 오랜시간이 걸린다. 

 

마지막으로 모든 링크의 비용이 1이기 때문에, 차등화된 경로 선택이 불가능하다.

이는 RIP를 현대 사용하지 않는 가장 큰 이유이다. 

초기에는 링크의 종류가 56 kbps의 전화선이 하나였지만, 
현대는 1 Gbps, 10 Gbps, 100 Gbps 등 여러 종류의 링크가 존재하기에 RIP는 사용하기 힘들다.

 

 

OSPF (Open Shortest Path First)

"OSPF"는 Link-State Routing Algorithm을 기반으로 한 Intra-AS-Routing Protocol이다.

 

앞서, Link-State Routing Algorithm을 다시 한번 살펴보면, 

Router가 Link-State(링크의 상태)를 공유해 LSDB를 형성한다. 

이후, 각 Router는 다익스트라 알고리즘을 통해 최소 비용 경로를 알아낸다.

 

"OSPF"는 정확히는 어떻게 Link-State를 서로 공유해 LSDB를 생성하는지를 규약 하는 프로토콜이다.

Routing과정은 LSDB를 보고 다익스트라 알고리즘만 적용하면 Forwarding Table을 완성할 수 있다.

 

동작 방식

우선, 이웃 Router간의 Link-State를 주고받기 위해 "이웃 Router"를 찾는다. 

이때 주기적으로 hello 패킷을 주고받으며 이웃관계를 형성한다. 

 

이웃을 찾으면, 각 Router는 Link-State정보가 포함된 패킷을 생성한다. 

이 패킷을 "LSA"(Link-State Advertisement) 혹은 "LSP"(Link-State Packet)라 부른다.

 

이후 LSA를 Flooding 함으로써 모든 Router가 LSDB를 갱신하도록 한다.

 

각 Router는 다익스트라 알고리즘을 통해 최소 비용 경로를 계산한다.

 

Designated Router

큰 Network에선 연결된 Router가 여러 개인 경우가 많다.

 

이러한 경우 특정 Router에서 Flooding을 하게 되면 연결된 모든 Router에 전달해야 한다. 

전달된 Link-State는 또다시 Link-State로 전달될 것이다. 

즉, 이웃 Router가 많아질수록 Flooding으로 인한 Routing Traffic은 많아지게 될 것이다. 

 

따라서, 동일한 Network라면 "Designated Router"를 설정하고,

Network내의 Router는 이 Designated Router와만 이웃관계를 맺는다.

 

즉, AS내의 Router는 LSA패킷을 Desinated Router에게만 전송되고,

Designated Router가 Network내의 모든 Router로 Flooding 하게 된다. 

 

OSPF는 위와 같은 방식으로 Routing Traffic을 줄인다.

 

계층 구조

OSPF는 "Intra-AS Routing Protocol"이지만, AS 내 역시 대규모 네트워크를 형성한다.

따라서, Designated Router를 설정해도 Router의 숫자가 많아져 결국엔 Traffic이 증가하게 된다. 

 

이를 위해 OSPF는 AS를 여러 구역으로 나누어, 각 영역은 독립적으로 OSPF라우팅을 수행한다.

이때, AS 간의 연결한 Router를 BackBone Router라 부르고, 

이들 간의 연결관계가 BackBone Area가 된다.

 

vs. RIP

Link-State가 변경되었을 때만 Flooding한다는 점에서 Traffic은 RIP에 비해 적다. 

 

또한, 비용이 변경되면 RIP의 경우 정해진 시간(약 30초마다)에 Routing 정보를 보낼 수 있지만, 

OSPF는 변경될 때마다 보낼 수 있다는 점에서 Forwarding Table의 수렴속도가 빠르다. 

 

마지막으로 각 Link마다 비용을 다르게 설정할 수 있다.

 

 

BGP (Border Gateway Protocol)

"BGP"는 Path Vector Routing Algorithm을 기반으로 한 Inter-AS Routing Protocol이다.

 

앞서 살펴본 RIP, OSPF는 Inter-AS Routing Protocol인 반면, 

BGP는 AS간에 Routing을 해주는 Intra-AS Routing Protocol이다. 

Intra-AS Routing Protocol은 BGP가 유일하다. 

 

Path Vector Routing Algorithm

Distance Vector Routing에선 다음 Router로 Distance Vector를 전달하며,

Distance Vector에는 "목적지 정보"와 "비용"만을 포함했다.

따라서, 각 Router는 전체 경로를 알 수 없기 때문에 Count to Infinity문제가 발생했다. 

 

반면 "Path Vector Routing"에선 Path-Vector를 전달하는데,

Path Vector에는 Distance Vector와 달리 여러 종류의 "Path Attributes"(경로 속성)를 조합해 경로 정보를 제공한다.

 

"Path Attributes"에는 다음과 같은 속성들이 있다. 

• AS-PATH 
• NEXT-HOP
• LOCAL-PREF
• MULTI-EXIT-DISC

이 중 "AS-PATH" 속성은 전체경로 정보를 제공하는데, 

이를 통해 BGP는 순환 경로를 탐지할 수 있다.

 

BGP는 이러한 Path Vector의 여러 Path Attributes를 조합해 Routing을 진행한다.

 

AS-PATH 

앞서 살펴보았듯이, 목적지까지 도착하기 위해 거치는 "AS"의 목록이다. 

이를 통해 순환 경로를 탐지할 수 있다. 

 

AS 내부에선 각자의 Routing 정책으로 전달하기 때문에, 

모든 Router 정보가 아닌, 거치는 AS의 정보만 전달한다.

해당 그림의 동작은 다음과 같다.

  1. AS 200은 초기에 180.10.0.0/16의 네트워크가 있다고 주변 AS에 알린다.

  2. AS 100은 자신의 네트워크와 AS 200에게 받은 경로에 자신을 추가해 다음 AS에게 전달한다. 

  3, 4. 경로에 자신의 AS를 추가하여 전달한다. 

  5. AS 200에서 순환 경로를 탐지해 첫 번째 Entry를 폐기한다. 

 

NEXT-HOP

말 그대로 다음 AS의 정보를 전달한다. 

하지만 여기서의 HOP은 다음 Router정보가 아닌,  Path Vector를 전송한 직전 AS의 Router 주소를 의미한다. 

 

AS내부의 Router들은 NEXT-HOP을 알기에 NEXT-HOP으로 가는 경로를 계산할 수 있다.

다음과 같이 AS 100의 R1와 AS 200의 R2사이에는 다른 네트워크가 껴있지만, 

R1입장에선 Path Vector를 전송한 직전의 AS의 Router는 R2가 되기 때문에 NEXT-HOP은 R2가 된다.

 

또한 AS 200 내부의 모든 Router는 이제 NEXT-HOP을 알 수 있기 때문에, AS 100으로 가는 경로를 계산할 수 있다.

 

LOCAL-PREF

"OutBound Traffic"에 대한 최적 경로 결정을 위한 선호도를 지정한다.

즉, 나가는 경로가 2개 이상이라면 어디를 우선적으로 택할 것인지 결정한다. 

 

해당 속성은 AS내부에서만 사용되는 속성이기에 외부 AS로 전달할 필요는 없다. 

즉, BGP Update 메시지에 포함시키지 않아도 된다.

 

MULTI-EXIT-DISC

"InBound Traffic"에 대한 최적 경로 결정을 위한 선호도를 지정한다.

 

AS-PATH, NEXT-HOPE, LOCAL-PREF는 필수적으로 구현해야 하는 Path Attribute이지만, 

MULTI-EXIT-DISC는 필수 구현은 아니다. 

 

하지만, LOCAL-PREF와 달리 InBound Traffic이기에 구현했다면 외부 AS가 알아야 하는 정보이다.

따라서 구현했다면, BGP Update 메시지에 포함시켜야 한다.

 

경로 선택

Path Vector에선 다음과 같은 여러 Attributes를 전달해, 

해당 정보를 토대로 Routing 작업을 진행한다. 

 

이때 경로 우선순위는 다음과 같이 결정된다. 

1. LOCAL-PREF 속성이 가장 큰 경로를 선택한다. 
2. MULTI-EXIT-DISC 속성이 가장 작은 경로를 선택한다. 
3. AS-PATH 속성이 가장 짧은 경로를 선택한다. 
4. NEXT-HOP의 경로 비용이 가장 작은 경로를 선택한다. (Hot Photato Routing)

만약 NEXT-HOP의 경로 비용마저 같다면, 추가적인 기준을 사용한다.

 

eBGP & iBGP

BGP에선, AS 간에 Routing 정보를 주고받으면 해당 Routing 정보를 AS 내에서 공유한다. 

예를 들어, NEXT-HOP의 경우 AS내에 전달하여, AS내의 모든 Router가 NEXT-HOP에 대한 최소 비용을 계산한다.

 

따라서, BGP는"AS 경계 Router간에 동작하는 Protocol"과 "AS 내의 Router간에 동작하는 Protocol"로 구분된다.

• eBGP: AS경계 Router 간에 동작
• iBGP : AS 내의 Router간에 동작

eBGP는 AS내의 Routing Protocol로 생성한 Path-Vector를 다른 AS로 전달하고, 수신하는 역할을 한다.

반면, iBGP는 수신한 Path-Vector를 AS 내에 전달하는 역할을 한다. 

 

AS 경계 Router의 경우에는 OSPF, RIP와 같은 Intra-AS-Protocol의 구현과 eBGP구현이 필요하다. 

또한, 다른 AS에서 전달받은 Path-Vector를 AS내로 전달해야 하기에 iBGP까지 구현이 필요하다. 

 

반면, AS내의 Router는 Intra-AS Protocol과 iBGP만 구현하면 된다.

 

References

https://www.youtube.com/watch?v=0v1zNpqHtGg&list=PLOml5j0-AMQkHM6SFAP3YIRXHKu2glLVc