10. Routing

나는컴공생·2024년 6월 5일

Computer Network

목록 보기

2/4

Network Layer

host to host 전달
라우터는 두개의 data link 층과 물리층, 1개의 network층을 가지며, 모든 IP datagram의 header을 확인한다.

Network Layer Functions

Packetizing

근원지 호스트에서 네트워크 층은 transport 층으로부터 packet을 받아서 datagram으로 캡슐화하고, datalink층으로 packet을 전달한다.
목적지 호스트에서 datagram은 캡슐이 벗겨지고, 패킷이 추출된 다음, transport 층으로 전달된다.
라우터는 패킷 분할 필요가 없다면 수신한 패킷의 캡슐제거를 허용하지 않는다. 패킷의 경로상의 다음 네트ㅝ크로 전달하는 목적으로만 주소를 검사할 수 있다.

Forwarding

: 각 라우터의 의사결정 table을 만들기 위해 라우팅에 규칙을 적용하고, 라우팅 프로토콜을 실행할 때
포워딩은 라우터 상의 하나의 인터페이스로 패킷이 도착했을 때 라우터가 취하는 행동을 의미합니다.

Data Plane
move packets from router's input to output
한 라우터 내에서 이루어지는 지역적(local) 기능
패킷 헤더의 값들을 기반으로 어느 포트로 패킷을 전송할지 결정합니다.

Routing

: 패킷이 근원지에서 목적지싸지 갈 수 있도록 하는 경로중 가장 좋은 경로를 찾는 것입니다.
라우팅 프로토콜은 통신이 이루어지기 전에 수행되어야 합니다.

Control Plane
determine route taken by packets
네트워크 전체에 걸친 로직
라우팅 방법:
- 전통적 라우팅 알고리즘: 라우터 안에서 구현
- 소프트웨어 정의 네트워킹(SDN): 원격 서버에서 구현

Routing

packet들이 forwarded 되는 경로를 결정한다.
결국, 라우터들이 forwarding table을 만드는 방법

Intra-domain vs Inter-domain

Autonomous Systems(AS)

: 하나의 라우팅 정책을 공유하는 네트워크 집합입니다.
인터넷은 여러 AS로 구성되어 있으며, 각각은 독립적인 관리 및 라우팅 정책을 가집니다.

Intra-domain(Intra-AS) routing

같은 AS, 도메인에 있는 라우터, 호스트들간 라우팅
같은 AS안에 있는 모든 라우터는 같은 intra-domain protocol을 사용해야한다.
다른 AS 안에 있으면 다른 intra-domain protocol 사용 가능하다.
gateway router: AS에서 다른 AS에 있는 라우터로의 link을 가지는 라우터

Inter-domain(Inter-AS) routing

AS 간 라우팅
gateway router들이 inter doamin routing을 수행한다.
(intra domain routing도 한다)

Routing Algorithms & Protocols

Distance Vector routing

Inter-AS routing algorithm
모든 destination에 대해 다음 노드가 무엇인지 기록
routing table을 neighbor들과 공유한다.
distance vector: (destination, distance, next node)
routing table에 모든 destination에 대한 정보를 저장한다.

how?

자기의 이웃들이 destination인 경우를 자기 table에 적는다.
이웃들과 서로의 routing table을 공유한다.

destination, distance 정보를 공유한다.
"이웃 D야 나 (E) 거쳐서 가는 경로 알려줄게~"
이웃 거쳐서 가는 경로 vs 원래 내가 아는 경로
(이웃 routing table cost + 이웃과 node 사이 cost) vs (원래 내 길)
- 만약에 (이웃) 나 거쳐서 가는 경로를 선택할거면, 너의 routing table 해당 목적지의 next hop는 바로 이웃인 나야나!

내 라우팅테이블이 갱신되면, 이웃들에게 다시 보내기(주기적으로)
모든 교환들이 다 종료되어, 테이블이 안정적으로 유지되었을 경우까지 반복한다.

만약 d, e 링크가 끊어졌다면, 둘 다 문제가 생겼음을 감지하고, 라우팅 테이블에서 서로의 node로 가는 길 없앤 다음 다른 이웃들한테 알린다.

Count to infinity problem

a,b,c node가 있다고 가정,
a와 b연결된 link가 끊어졌다고 가정,
b가 c로부터 얻은 a로 가는 길이 'b와 a가 이미 끊어진 경로'를 포함하는 길이었다면, 계속 cost가 서로서로 테이블 주고받으면서 무한대로 커진다.
추후에는 수가 커져서 다른 길을 선택하겠지만, 그 전까지 network 자원의 낭비가 심하다.

왜 발생하는가?

b가 얻은 경로 안에 b를 통한다는 사실을 몰라서 발생하는 문제
-> 모르는 이유는 전체 경로를 아는게 아니라, next node 정보만 저장하기 때문이다.

해결책

1. split horizon

: C가 B한테 보낼 때 next stop이 B인 vector는 보내지 않는다.

2. split horizon with poison reverse

: C가 B한테 보낼 때 next stop이 B인 vector는 cost를 무한대로 바꿔서 보낸다

3-hop loop 문제는 계속 발생

3. path vector routing

: 모든 path를 포함해서 보낸다.
(Inter-domain Protocol: Border Gateway Protocol에서 쓰인다)

next node가 아닌, destination까지 다 포함해서 보낸다.

Routing Information Protocol(RIP)

: distance vector routing에 기반한 routing protocol

매 30초마다 / routing table이 update 될 때마다
router는 이웃에게 자신의 table을 보낸다.
RIPv2 packet format

Link-state Routing

모든 노드들에게 내 이웃에 대한 정보가 적힌 table을 보낸다.(각 라우터가 그래프 그릴 수 있다)
network wide flooding(broadcast 주소 써서 보낸다)
자신의 link state을 보낸다.
link state packet(LSP)
- 보낸이의 ID
- 보낸이의 이웃의 (ID, distance) 정보
- 시퀀스 번호(몇번째 보내는건지)(동시에 두개 도착하면 최신 패킷만 보낸다)
모든 다른 노드들로부터 LSP을 받으면, Dijkstra algorithm을 사용하여 최소경로를 찾는다.
(각 라우터가 모든 길 알아서 그래프 그릴 수 있으므로)
(각각의 라우팅테이블 만든다)
만약 라우팅테이블이 갱신되면, 자신의 LSP를 LSP를 보낸이 빼고 모두에게 다시 전달한다.

Dijkstra algorithm

Input: weighted edge graph
Output: 한 노드에서부터 다른 모든 노드로의 shortest path

how?

SPT: shortest path tree, 초기값: source
D(node): des가 node까지의 총 거리
P(node): node 바로 전 거치는 노드

나의 이웃들의 정보만 저장한다.
distance가 가장 적은 (destination)node를 SPT에 추가한다.
새로 들어온 node를 거쳐서 갔을 때 더 짧은 경우를 check한다.
->강의자료 예시 꼭 직접 해보기

OSPF(Open Shortest Path First)

: link state routing을 기반으로하는 routing protocol

주기적/업데이트 될 때마다 Link State Adevertisement를 보낸다.
LSA packet format

요약

Link state
– Information exchanged: (neighbor ID, distance to neighbor)
– Information sent to: all nodes in the network
– Protocol: OSPF
Distance vector
– Information exchange: (destination, distance to destination)
– Information sent to: direct neighbors
– Protocol: RIP

Border Gateway Protocols

Internet은 hierachical하다.
- Scalable
- divided into "areas"
- Customer / Provider
- Peers
Autonomous System은 같은 routing 정책을 공유한다.
- single administrative control
- single protocol
각 ISP를 하나의 자율 시스템으로 취급한다. 각 AS는 필요로 하는 라우팅 프로토콜을 수행할 수 있다. 그러나, 모든 AS를 연결하기 위한 글로벌 라우팅 프로토콜(BGP)을 필요로한다.

Business Model
Customer는 provider에게 돈을 주고 provider의 망을 쓴다.
Peer: 협력하는 관계
Multi homing: AS가 여러 provider들을 가질 수 있다.

기존 Routing
RIP나 OSPF는 규모가 큰 경우 사용하기 어렵다.
- RIP: distance vector의 count to infinity problem이 발생하여 network resource 낭비가 발생한다.
- OSPF: LSP 패킷을 flooding 해야하는데 어렵다.
  -> BGP(Border Gateway Protocol) - Path vector routing
BGP 종류
border router(다른 AS로의 링크를 가진)끼리 라우팅하기

eBGP
- 다른 도메인을 가진 border router끼리 라우팅하기
  iBGP
- 같은 도메인을 가진 border router끼리 라우팅하기
Routing

eBGP routing
- distance vector에 next hop이 아닌 path 삽입
- 목적지 prefix , Origin AS(보낸 AS), Path
- 다른 이웃 BGP 라우터에게 route adverstisement을 보낸다.
- 보낼 때 해당 AS 지나는 path는 보내지 않는다.
  -> loop을 감지할 수 있다.
  iBGP routing
- eBGP와 같다
- eBGP로 알게 된 루트는 iBGP의 이웃들로 전달할 수 있다.
  (외부 경로를 내부 라우터들에게 알려줄 수 있고, 내부 경로를 외부 라우터에게도 가능)
- iBGP로 알게 된 루트는 iBGP의 이웃들로 전달할 수 없다.
  (내부 경로를 내부 라우터에게 보내지 않는다.)
  (loop 방지)
- 모든 같은 AS 내 iBGP들은 fully connected, 즉 누구 통해서가 아니라 직접 연결되어 있다.
Policies
가장 짧은 길이 좋은 길이 아닐 수도 있다. 왜냐하면 돈과 연관됨
customer > peer > provider
transit traffic:
- 최종 목적지(customer)로 가는 트래픽이 아니라, 그 네트워크를 통과해서 다른 네트워크로 가는 트래픽 즉, 내 고객이 아닌 다른 사람들한테 가는 트래픽
- provider일 때 accept 가능!
- customer이거나 peer면 불가능
routing:
- 나의 customer에게는 나의 모든 route 알려준다.
ex) provider/peer -> 나 -> customer
- 나의 provider, peer에게는 나의 customer들 route만 알려준다.
ex) customer -> 나 -> provider/peer

Local Preference - multi-homing
AS의 provider가 여러명인 경우, 어떤 route로 갈까?
우선순위를 설정하여 높은 곳으로 traffic 보내기

Multi-Exit Discriminator(MED)
같은 AS 내 gateway(boarder) router가 여러개인 경우,
어느 gateway router 통해서 traffic 나갈까?
MED 낮은순 이용