sehee

[TCP/IP Protocol #11] Part 2 | Chapter 11. 유니캐스트 라우팅 프로토콜(RIP, OSPF and BGP)

유니캐스트 통신: 하나의 송신자와 하나의 수신자 간의 통신을 의미, one-to-one 통신

유니캐스트 통신을 지원하기 위해 라우터에 생성되는 라우팅 테이블에 관해 논의할 것

자율 시스템(AS: Autonomous System)

비용 또는 메트릭

라우터가 패킷을 수신했을 때, 어느 네트워크로 패킷을 보내야 하는가? 이 결정은 최적화 과정에 기반을 둔다.
그렇다면 최적의 경로란 무엇인가? 최적이라는 용어의 정의는 무엇인가?

망을 통해 전달되는 비용(cost)를 할당하는 것, 이 비용을 메트릭(metric))이라 부른다.

망에서 성능을 최대한 혹은 지연 시간을 최소로 하고 싶다면 성능이 높은 것/낮은 지연 시간이 낮은 비용을 의미한다.

도메인 내 및 도메인 간 라우팅

근래 들어 인터넷은 한 가지 라우팅 프로토콜로 모든 라우터의 라우팅 테이블을 갱신하는 작업을 수행하기에는 부족할 정도로 너무 많이 확장되었다. 이런 이유로 인터넷은 자율 시스템(AS: Autonomous System)으로 나눠진다.

- 자율 시스템: 하나의 단일 관리 기관 하에 있는 라우터와 네트워크의 그룹

- 도메인 내(intradomain) 라우팅: 자율 시스템 내에서의 라우팅 (e.g., 거리 벡터(RIP), 링크 상태(OSPF))

- 도메인 간(interdomain) 라우팅: 자율 시스템 간의 라우팅 (e.g., 경로 벡터(BGP))

RIP(Routing Information Protocol): 거리 벡터 프로토콜

OSPF(Open Shortest Path First): 링크 상태 프로토콜

BGP(Border Gateway Protocol): 경로 벡터 프로토콜

1. 거리 벡터 라우팅

distance vector routing

모든 라우터와 망들로 구성된 AS를 노드의 집합과 이 노드들을 연결하는 선(에지)들로 구성된 그래프로 간주한다.

그래프 이론은 노드들 간의 거리가 주어진 망에서 노드들 간의 최단 거리를 찾기 위해 Bellman-Ford(또는 Ford-Fulkerson)라고 불리는 알고리즘을 사용한다.

Bellman-Ford 알고리즘

임의의 두 노드 쌍 간의 비용을 안다면 두 노드 간의 최소 비용(최단 거리)을 찾을 수 있다.

1) 각 노드와 자신 간의 최단 거리 및 비용을 0으로 초기화함

2) 각 노드와 다른 노드와의 최단 거리를 무한대로 설정함. 그 후 노드와 다른 노드 간의 비용을 주어진 값으로 설정하되 연결이 없으면 무한대로 유지함

3) 최단 거리 벡터에 변경 사항이 더 없을 때까지 알고리즘을 반복함

거리 벡터 라우팅 알고리즘

Bellman-Ford 알고리즘은 도시 간의 도로 지도에 매우 잘 적용된다. (∵ 동일한 지역에 있는 각 노드 간의 초기 정보가 모두 주어지기 때문)

비용: 홉 수 (즉, 목적지에 도달하기 위해 얼마나 많은 망을 거쳐 가야 하는 가, 두 노드 간의 비용은 1로 설정)

각 라우터 필수 보유 정보: 목적지 망, 비용, 다음 홉(next-hop) 정보

무한대로의 카운트

라우팅 프로토콜이 잘 동작하기 위해서는 링크가 고장 나서 비용이 무한대로 바뀌었을 때 모든 다른 라우터들이 이를 즉시 인식할 수 있어야 하는데, 거리 벡터 라우팅에서는 이에 시간이 소요된다.

이 문제: 무한대로의 카운트

두 노드 루프

노드 A와 B는 노드 X에 도달하는 방법을 알고 있다. 그러나 갑자기 A와 X 사이의 링크가 실패했다고 하며 노드 A는 자신의 테이블을 변경한다.

만약 노드 A가 즉각적으로 B에게 테이블을 전송하면 문제가 없다. 그러나 만약 B가 라우팅 테이블을 A로부터 받기 전에 자신의 라우팅 테이블을 보내게 되면 시스템이 불안정해진다.

무한대의 정의

첫 번째 해결책, 무한대를 16과 같은 작은 수로 재정의 (거리 벡터 라우팅의 대부부 구현에서 16을 무한대로 정의)

→ 각 방향으로의 망의 크기가 15 홉을 넘을 수 없음
→ 거리 벡터 라우팅이 큰 시스템에서 사용될 수 없음을 의미

수평 분할

각 인터페이스를 통해 테이블을 플러딩(flooding)하는 대신에 각 인터페이스를 통해 자신 테이블의 일부만을 전송

노드 B가 X에 도달하는 최적의 경로가 A를 거치는 것이라는 것을 안다면 다시 알릴 필요 없음 (이미 A는 알고 있기 때문)

수평 분할과 poison reverse

보통 거리 벡터 프로토콜은 타이머를 사용하고, 경로 상에 새로운 소식이 없으면 테이블에서 이 경로를 제거함

혹은 수평 분할 시나리오에서 노드 B가 A로 보내는 광고에 X로의 경로를 제거해 버림

→ (수평 분할 정책의 단점) 노드 A: 수평 분할 정책 때문에 그런 것인지, B가 최근에 X에 관한 소식을 받지 못해서인지 예측할 수 없음

→ (poison reverse) 동일하게 광고하되, 거리 값을 무한대로 설정해서 "이 값을 사용하지 말라"고 경고함

세 노드 불안정성

X가 도달 가능하지 않음을 발견한 후 노드 A가 이 상황을 노드 B와 C에 패킷을 전송해 알림

노드 B는 즉각적으로 테이블을 갱신했으나 노드 C로 가는 패킷은 유실

RIP

경로 정보 프로토콜
RIP에서 사용되는 메트릭으로, 거리는 목적지에 도달하기 위해 사용되어야만 하는 링크(네트워크)의 수로 정의된다. 이런 이유로 RIP에서의 메트릭은 홉 수라고 불린다.

2. 링크 상태 라우팅

도메인 내의 각 라우터가 도메인의 전체 토폴로지 -노드들과 링크들의 리스트, 그 유형, 비용(메트릭) 및 링크가 살아 있는지 죽어 있는지와 같은 상태를 포함해서 어떻게 연결되어 있는지- 를 알고 있다면 노드는 딕스트라(Dijkstra) 알고리즘을 사용하여 라우팅 테이블을 만들 수 있다.

라우팅 테이블 만들기

1) 각 노드에 의해 링크 상태를 생성하는 것: 이는 링크 상태 패킷(LSP: link state packet)이라고 함

2) 모든 다른 라우터로 효과적이며 안전한 방법으로 LSP들을 발송하는 것: 플러딩(flooding)이라고 부름

3) 각 노드에서 최단 경로 트리의 생성

4) 최단 경로 트리에 기반을 둔 라우팅 테이블의 계산

OSPF

Open Shortest Path First 프로토콜, 라우팅을 적절하게 수행하기 위해 OSPF는 자율 시스템을 여러 지역으로 나눈다.

지역(areas)이란 자율 시스템 내에 포함되는 호스트, 라우터 및 네트워크의 모음이다.

하나의 자율 시스템은 여러 개의 다른 지역들로 나뉠 수 있다. 지역 내의 모든 네트워크들은 연결되어야만 한다.

링크의 유형

네트워크는 링크(link)라고 불린다. 4가지 유형의 링크가 정의 되는데 각각 점-대-점(point-to-point), 경유(transient), 스터브(stub), 가상(virtual) 링크이다.

점-대-점 링크

라우터 간을 그 사이에 어떤 다른 호스트나 라우터 없이 직접 연결하는 것, 링크(네트워크)의 목적은 단지 라우터 간을 연결하는 것

경유 링크

몇 개의 라우터가 연결되어 있는 네트워크, 데이터는 어떤 라우터로도 들어갈 수 있고 어떤 라우터로부터도 떠날 수 있다.

각 라우터가 하나의 단일 네트워크를 통해 다른 라우터들과 연결되어 있다는 것을 보여주기 위해 네트워크 자체는 단일 노드로 표현되어야 한다. 그러나 여기서 문제가 되는 것은 네트워크가 장치가 아니므로 라우터로 동작할 수 없다는 것이다.

따라서 네트워크에 있는 라우터 중 하나가 이런 책임을 맡아야 한다. 이 라우터에게는 두 가지 목적이 주어지는데 하나는 실제 라우터로서 이고, 다른 하나는 지정(designated) 라우터로서 이다.

스터브 링크

단지 하나의 라우터에만 연결된 네트워크이다. 데이터 패킷은 이 단일 라우터를 통해서만 네트워크에 들어가거나 나갈 수 있다.

이런 상황을 나타내기 위해서는 라우터를 노드로, 네트워크를 지정 라우터로 표시해야 한다.

가상 링크

두 라우터간의 연결이 끊어지면 관리자는 여러 라우터를 거쳐 돌아가는 더 긴 경로를 사용하더라도 그 둘 사이에 가상 링크를 연결해야 한다.

Reference

Behrouz A. Forouzan (2009), TCP/IP 프로토콜(Protoccol Suite), 4th Edition

Opcode: 스택

x64 아키텍쳐에서는 다음의 명령어로 스택을 조작할 수 있음

push val: val을 스택 최상단에 쌓음 (연산: rsp -= 8, [rsp] = val)

[Register]
rsp = 0x7fffffffc400

[Stack]
0x7fffffffc400 | 0x0 ≦ rsp
0x7fffffffc408 | 0x0

[Code]
push 0x31337

해석

rsp(Stack Pointer): 현재 스택의 최상위 주소
rsp 주소에 현재 스택의 최상위 값이 존재 - '0x0'

rsp 주소에서 8바이트(64비트 아키텍처에서는 8바이트가 한 워드) 위로 올라가면 또 다른 8바이트 값이 있음 - '0x0'

스택에 0x31337 푸시 - c400 - c3f8 -> 8만큼 차이

결과

[Register]
rsp = 0x7fffffffc3f8

[Stack]
0x7fffffffc3f8 | 0x31337 ≦ rsp
0x7fffffffc400 | 0x0
0x7fffffffc408 | 0x0

pop reg: 스택 최상단의 값을 꺼내서 reg에 대입 (연산: reg = [rsp], rsp += 8)

[Register]
rax = 0
rsp = 0x7fffffffc3f8

[Stack]
0x7fffffffc3f8 | 0x31337 <= rsp 
0x7fffffffc400 | 0x0
0x7fffffffc408 | 0x0

[Code]
pop rax

결과

[Register]
rax = 0x31337
rsp = 0x7fffffffc400

[Stack]
0x7fffffffc400 | 0x0 <= rsp 
0x7fffffffc408 | 0x0

Opcode: 프로시저

특정 기능을 수행하는 코드 조각

호출(Call): 프로시저를 부르는 행위

반환(Return): 프로시저에서 돌아오는 것

call 다음의 명령어 주소(return address, 반환 주소)를 스택에 저장하고 프로시저로 rip 이동

x64 어셈블리언어에는 프로시저의 호출과 반환을 위한 call, leave, ret 명령어 존재

call addr: addr에 위치한 프로시져 호출

연산: push return_address / jmp addr

예제

[Register]
rip = 0x400000
rsp = 0x7fffffffc400

[Stack]
0x7fffffffc3f8 | 0x0
0x7fffffffc400 | 0x0 <= rsp

[Code]
0x400000 | call 0x401000  <= rip
0x400005 | mov esi, eax
...
0x401000 | push rbp

해석

Register(레지스터): rip(명령 포인터 레지스터), rsp(스택 포인터)

after call 0x401000 - 현재 위치의 다음 명령어의 주소(0x400005)가 스택에 푸시됨

rsp는 8만큼 감소하여 스택의 새로운 맨 위를 가리킴

결과

[Register]
rip = 0x401000
rsp = 0x7fffffffc3f8

[Stack]
0x7fffffffc3f8 | 0x400005  <= rsp
0x7fffffffc400 | 0x0

[Code]
0x400000 | call 0x401000
0x400005 | mov esi, eax
...
0x401000 | push rbp  <= rip

leave: 스택프레임 정리

연산: mov rsp rbp / pop rbp

예제

[Register]
rsp = 0x7fffffffc400
rbp = 0x7fffffffc480

[Stack]
0x7fffffffc400 | 0x0 <= rsp
...
0x7fffffffc480 | 0x7fffffffc500 <= rbp
0x7fffffffc488 | 0x31337 

[Code]
leave

해석

Register(레지스터): rsp(스택 포인터), rbp(베이스 포인터)

mov rsp, rbp / pop rbp

leave 명령: 현재 함수의 프롤로그에서 설정된 스택 프레임이 제거됨

rsp가 rbp로 복원되고 rbp의 원래 값인 0x7fffffffc500이 rbp로 복원됨

결과

[Register]
rsp = 0x7fffffffc488
rbp = 0x7fffffffc500

[Stack]
0x7fffffffc400 | 0x0
...
0x7fffffffc480 | 0x7fffffffc500
0x7fffffffc488 | 0x31337 <= rsp
...
0x7fffffffc500 | 0x7fffffffc550 <= rbp

스택 프레임이란?

함수별로 자신의 지역변수 또는 연산과정에서 부차적으로 생겨나는 임시 값들을 저장하는 영역
스택 영역을 구분 없이 사용한다면, 서로 다른 두 함수가 같은 메모리 영역을 사용할 수 있음

A라는 함수가 B라는 함수를 호출하는데, 같은 스택 영역을 사용한다면 B에서 A의 지역변수를 모두 오염시킬 수 있음, B에서 반환한 뒤 A는 정상적인 연산을 수행할 수 없음

ret: return address로 반환

연산: pop rip

예제

[Register]
rip = 0x401021
rsp = 0x7fffffffc3f8

[Stack]
0x7fffffffc3f8 | 0x400005    <= rsp
0x7fffffffc400 | 0x123456789abcdef

[Code]
0x400000 | call 0x401000
0x400005 | mov esi, eax
...
0x401000 | push rbp
0x401001 | mov rbp, rsp
0x401004 | sub rsp, 0x30
0x401008 | mov BYTE PTR [RSP], 0x3
...
0x401020 | leave
0x401021 | ret <= rip

해석

Register: rip(명령 포인터 레지스터), rsp(스택 포인터)

Stack: rsp 주소에 현재 스택의 맨 위 값이 있음, 0x400005
rsp 주소에서 8바이트 아래로 내려가면 다음 슬롯이 있고 값은 0x123456789abcdef

call 0x401000: rip은 0x401000으로 변경됨

call 0x401000: 스택과 레지스터 상태

결과

[Register]
rip = 0x400005
rsp = 0x7fffffffc400

[Stack]
0x7fffffffc3f8 | 0x400005
0x7fffffffc400 | 0x123456789abcdef    <= rsp

[Code]
0x400000 | call 0x401000
0x400005 | mov esi, eax   <= rip
...
0x401000 | push rbp
0x401001 | mov rbp, rsp
0x401004 | sub rsp, 0x30
0x401008 | mov BYTE PTR [RSP], 0x3
...
0x401020 | leave
0x401021 | ret

스택 프레임의 할당과 해제

func 함수를 호출, 다음 명령어의 주소인 0x4000005는 스택에 push

main: rip

stack: rsp(0x7fffffffc400), rbp(0x7fffffffc480)

스택

push val: rsp를 8만큼 빼고, 스택의 최상단에 val을 쌓음

pop reg: 스택 최상단의 값을 reg에 넣고, rsp를 8만큼 더함

프로시저

call addr: addr의 프로시저 호출

leave: 스택 프레임 정리

ret: 호출자의 실행 흐름으로 돌아감

Q1. 레지스터, 메모리 및 코드가 다음과 같다. Code를 1까지 실행했을 때, rax에 저장된 값은?

[Register]
rbx = 0x401A40

=================================

[Memory]
0x401a40 | 0x0000000012345678
0x401a48 | 0x0000000000C0FFEE
0x401a50 | 0x00000000DEADBEEF
0x401a58 | 0x00000000CAFEBABE
0x401a60 | 0x0000000087654321

=================================

[Code]
1: mov rax, [rbx+8]
2: lea rax, [rbx+8]

0xC0FFEE

Q2. Code를 2까지 실행했을 때, rax에 들어있는 값은?

0x401A48

Q3. 레지스터, 메모리 및 코드가 다음과 같다. Code를 1까지 실행했을 때, rax에 저장된 값은?

[Register]
rax = 0x31337
rbx = 0x555555554000
rcx = 0x2

=================================

[Memory]
0x555555554000| 0x0000000000000000
0x555555554008| 0x0000000000000001
0x555555554010| 0x0000000000000003
0x555555554018| 0x0000000000000005
0x555555554020| 0x000000000003133A

==================================

[Code]
1: add rax, [rbx+rcx*8]
2: add rcx, 2
3: sub rax, [rbx+rcx*8]
4: inc rax

0x3133A

Q4. Code를 3까지 실행했을 때, rax에 저장된 값은?

0

Q5. Code를 4까지 실행했을 때, rax에 저장된 값은?

1

Q6. 레지스터, 메모리 및 코드가 다음과 같다. Code를 1까지 실행했을 때, rax에 저장된 값은?

[Register]
rax = 0xffffffff00000000
rbx = 0x00000000ffffffff
rcx = 0x123456789abcdef0

==================================

[Code]
1: and rax, rcx
2: and rbx, rcx
3: or rax, rbx

0x1234567800000000

Q7. Code를 2까지 실행했을 때, rbx에 저장된 값은?

0x000000009ABCDEF0

Q8. Code를 3까지 실행했을 때, rax에 저장된 값은?

0x123456789ABCDEF0

Q9. 레지스터, 메모리 및 코드가 다음과 같다. Code를 1까지 실행했을 때, rax에 저장된 값은?

[Register]
rax = 0x35014541
rbx = 0xdeadbeef

==================================

[Code]
1: xor rax, rbx
2: xor rax, rbx
3: not eax

0xEBACFBAE

35014541

deadbeef

3d 5e (0a) (1d) 4b 5e (4e) (1f)

EB AC FB AE