라우팅 Routing

라우팅 기능과 주요 프로토콜 이해

• 간단한 라우팅 프로토콜
• 거리-벡터 프로토콜
• 링크 상태 프로토콜
• 외부 라우팅 프로토콜

최단 경로 라우팅

• 거리 기준은 다양하지만 중간에 거치는 홉(hop) 수로 판단
• 패킷이 목적지로 가는 동안 거치는 라우터 수가 최소가 되도록 경로를 선택
• a > d로 가려면 a-b-d 경로 선택, a > g로 가려면 a-c-g 경로 선택
• 기타 거리 기준) 패킷의 전송 지연, 전송 대역폭, 통신 비용 등

플러딩 (Flooding)

• 입력된 패킷을 라우터가 출력 가능한 모든 경로로 중개하는 방식
• 확실하게 전달할 수 있다는 장점이 있지만 네트워크에 패킷이 무한 개 만들어질 위험이 있음
• 홉 수를 일정 범위로 제한하고 제거하는 방식으로 대처 가능
• 중요한 데이터를 모든 호스트에게 동시에 전달하는 환경에서 제한적으로 사용

거리-벡터 프로토콜

• 라우터 자신과 직접 연결된 주변 라우터에게 라우팅 정보를 교환하는 방식
• 자기가 가지고 있는 전체 네트워크에 대한 지식을 이웃 라우터에게만 일정한 주기로 전달
• 전달하는 정보는 개별 네트워크까지 걸리는 거리 정보
• 따라서 개별 라우터에서는 아래 정보를 필수로 유지해야함
  • 링크 벡터: 직접 연결된 네트워크에 대한 연결 정보
  • 거리 벡터: 전체 개별 네트워크에 대한 거리 정보
  • 다음 홉 벡터: 개별 네트워크로 가기 위한 다음 홉 정보

• 링크 벡터 - 특정 네트워크로 직접 갈 수 있는 포트번호
  • L(x) = [포트(1), 포트(2), … , 포트(M)]
  • L(R1) = [1, 3, -, -, -]
  • L(R2) = [1, -, -, 8, -]
  • L(R3) = [-, 2, -, 6, -]
• 거리 벡터 - 각 네트워크를 얼마만큼 거리로 도달할 수 있는
  • D(x) = [거리(1), 거리(2), … , 거리(N)]
  • D(R1) = [1, 1, 2, 2, 2]
  • D(R2) = [1, 2, 2, 1, 2]
  • D(R3) = [2, 1, 2, 1, 2]
• 다음 홉 벡터 - 각 네트워크로 가려면 어떤 라우터를 거쳐야 하는지
  • H(x) = [홉(1), 홉(2), … , 홉(N)]
  • H(R1) = [-, -, R4, R3, R6]
  • H(R2) = [-, R1, R5, -, R8]
• RIP(Routing Information Protocol)
  • 거리-벡터 방식
  • 소규모 네트워크 환경에 적합
  • 주변 라우터가 제공하는 거리 벡터 정보가 임의의 짧은 시간 내에 모두 도착해야 하는데 이는 현실적으로 어려움 (UDP 사용 - 패킷 손실 가능성 있음)
  • 라우팅 정보를 수정하는 경우
    • 거리 벡터 정보가 새로운 네트워크 주소면 적용
    • 목적지까지 더 짧으면 기존 경로를 대체
    • 거리 벡터 정보가 입력되면 등록 정보를 수정

• 임의의 시점에 다음 정보 도착
  • • R2 = [1. 2. 2. 1. 2]
    • R3 = [2, 1, 2, 1, 2]
    • R4 = [2, 1, 1, 2, 2]
    • R5 = [2, 1, 2, 2, 1]
• 각 라우터까지 거리 + 도착한 값과 기존 값 비교
  • R2까지 거리 1 + 도착한 값 1 < Net.4까지의 기존 거리 3
  • R3까지 거리 1 + 도착한 값 1 < Net.4까지의 기존 거리 3

 

Command) 

1이면 요구, 0이면 응답

초기에 요구를 받으면 즉시 응답해야 함

 

IP Address)

네트워크 지칭 (0으로 끝남)

 

Metric)

목적지 네트워크까지 홉 수

링크 상태 프로토콜

• 거리-벡터 프로토콜의 단점 개선
  • 주변 상황에 변화가 있을 때 주변 라우터까지의 정보를 모든 라우터에 전달
• 모든 라우터에 전달해야 하기 때문에 플러딩 방식을 사용해 받은 쪽을 제외한 나머지 라우터에 모두 전달
• 링크 상태 프로토콜의 대표 예시는 OSPF(Open Shortest Path First) 프로토콜

• 5개의 OSPF 라우터(R1~R5) 존재
• 라우터간 연결 링크에 대한 IP 주소(예 - R1과 R2 사이 1.1.1.0/30)와 OSPF Cost(예 - R1과 R2 사이 (10)) 및 각 라우터의 Loopback 주소(*예 - R1의 10.1.0.1) 표시
• 파란색 줄(링크)가 OSPF가 enable임을 표시

각 라우터가 링크 정보를 전파하는 방식과 순서

• ‘R1은 R2, R3에 연결되어 있다’는 링크 정보를 다른 라우터에게 전달하려면,
• R1에 연결된 모든 라우터(R2, R3)에 정보 전달
• R2는 정보를 받은 R1을 제외하고 R4, R5에 전달
• R3도 R1을 제외하고 연결된 R4, R5에 전달
• R4, R5는 동일한 Router-LSA를 2개씩 수신
  • LSA 식별자에 해당하는 LS Type, Link State ID, Advertising Router가 동일한 경우 나중에 수신한 LSA를 폐기
  • 여기에서는 R2로부터 온 정보가 더 먼저 도착했기 때문에(Cost가 10으로 Cost가 20인 R3보다 빠름) R3로부터 받은 정보는 폐기함

R2

• 자신의 링크 정보를 다른 OSPF 라우터로 전파
• 이를 수신한 R1, R4, R5는 Router-LSA가 수신된 링크를 제외한 나머지 링크로 플러딩
• R3은 동일한 Router-LSA를 3개 수신
• 가장 먼저 수신한 것(R1으로부터)을 제외한 나머지 폐기

R3

 

R4

 

R5

 

모든 정보를 모아서 전체 그림을 그림

 

최단 경로(=cost가 가장 적은) 트리 구성

외부 라우팅 프로토콜

• 외부 라우팅 프로토콜에서 사용하는 경로 벡터는 경로에 관한 거리 정보값이 필요 없는 방식
• 어디를 통해서 연결되는지, 연결 여부가 더 중요
• 내부 라우팅 프로토콜과는 달리 거리(비용)에 대한 처리 과정이 없음
• 목적지 네트워크에 도착하기 위한 자율시스템에 대한 내용만 포함
• BGP(Border Gateway Protocol)
  • 인터넷에서 많이 사용
  • 서로 다른 종류의 자율시스템간 정보 교환 가능
  • TCP를 이용하여 정보 교환
  • 메시지 종류
    • Open: 관계 생성
    • Updata: 경로 관련 정보 전달
    • KeepAlive: Open에 대한 응답 기능과 주기적인 관계 확인 기능
    • Notification: 오류 상태 통보

BGP

• 평면적 라우팅은 확장이 어려움. (저장 공간, 합의에 도달하는 시간, 통신 문제 등)
• 목적지에 이르는 거리가 멀수록 더 적은 정보를 이용하는 것이 타당
• 해결 방안: 영역 계층구조(Area Hierarchy)

• 망을 영역으로 분할
• 각 영역에 서브 영역 존재 가능
• 망 노드는 계층적 주소 부여
  • 영역 내부
    • 각 노드는 다른 노드로 가는 경로 보유
  • 영역 외부
    • 각 노드는 다른 top-level 영역으로 가는 경로만 보유
    • 영역간 패킷은 적절한 border router에게 전달

• 실제로 더 짧은 경로가 있음에도 영역 외부에서는 각 영역 top level끼리만 오갈 수 있기 때문에 비효율적일 수 있지만 단순하게 구성 가능

자율시스템(AS : Autonomous System)

• 하나의 기술적 관리 하에 있는 라우터들의 집합
• AS 안에서는 IGP(Interior Gateway Protocol)와 패킷을 전달하기 위한 공통 메트릭 이용
• 다른 AS로 전달하기 위해서는 EGP(Exterior ~) 사용
• 가끔 하나의 AS 안에서 여러 IGP를 이용할 수도 있지만, 외부에는 하나의 AS로만 인식됨
• 각 AS는 유일한 ID 할당
  • 16비트로 구성
  • 64512 ~ 65535는 private ID
  • 예
    • MIT: 3
    • JANET: 786
    • AT&T: 7018, 6341, 5074
    • Sprint: 1239, 1240, 6211, 6242
• AS는 피어 역할

• 실제로는 이렇지 않는다 (엔드 호스트가 라우터에 연결되는 방식 X)
• RIP, OSPF는 계층적 구조가 아니기 때문에 확장성이 떨어지진 않는다
• ISP에도 계층이 존재함

• Tier1 ISP는 전역(global)적으로 도달 가능
• Tier2,3은 local

Transit vs Peering

• Transit은 더 큰 ISP와 묶이는 것
• Peering은 규모가 비슷한 ISP끼리 묶이는 것

렇다면

• 링크 상태 vs. 거리-벡터 프로토콜 중 무엇을 쓸 것인가?
  • 정답은 없음. 상황과 정책에 따라 판단
• 거리-벡터 문제점
  • 수렴하지 않을 가능성
• 링크 상태 문제점
  • 전체 라우터가 같은 메트릭을 쓸 수 있음
  • 전체 네트워크를 다 수용하기엔 DB가 너무 커짐
• 해결 방안
  • 거리-벡터 + 경로를 같이 쓰는 하이브리드 형태가 해답이 될 수 있음
  • 각 라우팅 업데이트가 전체 경로 정보를 담고 있음
  • loop는 중간에 감지해 제거

Interconnecting BGP Peers

• BGP는 TCP를 이용해 피어를 연결
• 장점
  • BGP보다 간단해짐
  • 계속 연결을 유지하고 있기 때문에 주기적 refresh가 필요 없음
  • 점진적 업데이트 가능
• 단점
  • 혼잡 제어가 과연 필요할까?
  • 과부하 걸릴 때 피어 인터랙션은 어떻게 할 것인가?

Hop-by-hop Model

• BGP는 직접 묶여있는 라우터에게 본인이 가진 정보를 광고하는 Hop-by-hop 모델이다.

https://naon.me/posts/til85