[TCP/IP] 라우팅

라우팅

• 최적의 경로를 선택하고 선택된 경로를 따라 패킷을 전달하는 과정

 

• AS(Autonomous System)
  • : 동일한 관리 도메인에 속하는 네트워크나 라우터의 집합
  • 관리의 용이성과 효율성을 위함
• 내부 게이트웨이 프로토콜 IGP(Interior Gateway Protocol)
  • RIP(Routing Informaion Protocol)
  • IGRP(Interior Gateway Routing Protocol)
  • EIGRP(Enhanced Interior Gateway Routing Protocol)
  • OSPF(Open Shortest Path First)
• 외부 게이트웨이 프로토콜 EGP(Exterior Gateway Protocol)
  • BGP(Border Gateway Protocol)

 

라우팅 알고리즘

• 정적 라우팅 알고리즘
• 동적 라우팅 알고리즘

---

RIP(Routing Informaion Protocol)

• 거리 벡터 알고리즘벨만-포드 알고리즘 이용
• 인접 라우터와 주기적으로 라우팅 테이블 값 교환 → 갱신 → 경로 선택
• 소규모 네트워크에 적합
• 메트릭 : 홉(hope) 수
• 라우팅 테이블 갱신 과정
  • 갱신 알고리즘

 

 

• RIP 패킷 포맷

• 명령
• : 메시지의 종류 (요청 : 1 , 응답 : 2)
• 버전
• 네트워크 패밀리
  • : 사용된 프로토콜 계열
• 네트워크 주소
• 메트릭
  • : 목적지까지의 홉 수 (범위 : 1~15) 
  • 16은 무한대를 나타낸다.
  • RIP패킷이 15 홉보다 더 긴 경우를 갖지 않도록 하여 RIP 패킷의 네트워크 잔여 상태 방지

 

RIP의 문제점

1. 홉 수가 15 이상인 네트워크에서는 사용 ❌
2. 메트릭 정보가 홉 수 뿐이라 회선 속도와 같은 다른 정보 반영 ❌
3. 홉 수 16 이상부터 장애 발생 감지 가능 (counting to infinity)
4. : 수렴 속도의 늦은 발생, 자원 낭비 초래
5. 라우팅 테이블 갱신 속도가 늦어 특정 경로에 루프 생성 우려

 

RIP 성능 개선 방법

1. 트리거드 업데이트(Triggered update)
   • 홉 수 변경시, 즉시 통보 - 복구시간 감소
2. 홀드다운(Holddown)
   • 메트릭이 무한대인 경로는 일정시간 동안 경로 갱신 ❌, 전체 네트워크 경로 갱신 시까지 대기
3. 스필리트 호라이즌(Split horizon)
   • A→B→C 에서 B→C 간 장애가 발생하면 A→B 구간에서 루프가 발생할 수 있음
   • ∴ B가 A에게 보낸 정보는 이후 다시 B에게 보내지 않음 (추후에 발생할 우려 사항들에 대해서도 미리 차단)*
4. 포이즈닝(Posioning)
   • 회선 고장 감지 시, 즉시 해당 경로의 메트릭을 16으로 지정 후 전체 네트워크에게 도달 불가능함을 신속히 알림

 

RIPv2

: 기존 RIPv1의 예약 필드 사용

• RIPv1과 RIPv2의 차이

1. 서브넷 마스크 식별
2. 경로 정보 인증
3. AS 구별
4. 브로드캐스트와 멀티캐스트 전송

• RIPv2 패킷 포맷

• 경로 태그(Route Tag)
  • : AS 번호를 전달하여 내부 경로와 외부 경로 구분
• 서브넷 마스크
• 다음 홉 주소(Next-Hop Address)
  • : 다른 라우팅 프로토콜을 사용하는 라우터에 대한 주소
  • → 동일한 네트워크 상에 있지만 라우팅 프로토콜이 달라서 최적의 경로를 찾지 못할 경우 사용
• RIPv2 인증 패킷 포맷

---

IGRP(Interior Gateway Routing Protocol)

• 다양한 네트워크 파라미터를 메트릭으로 이용 ↔ RIP는 '홉 수'만 메트릭으로 이용
• 멀티 패스 라우팅
  • 하나의 목적지에 대해 최대 4개의 경로 관리 ↔ RIP는 경로 하나
  • 트래픽에 대한 부하 분산과 링크에 대한 자동 복구 수행
• 네트워크 구성 변화에 빠르게 반응
• 라우팅 테이블 갱신을 위해 꼭 필요한 정보만을 전송 - 회선에 대한 오버헤드 감소
• 메트릭
  • 대역폭(Bandwidth) : 회선속도
  • 지연(Delay) : 전송 시간(매체 지연 시간 포함)
  • 신뢰도(Reliablility) : 라우터가 동적으로 측정
  • 부하(Load)
  • MTU : 최대 프레임 크기
• 메트릭 계산 연산

$$
메트릭 = K1 * 대역폭 + (K2 * 대역폭) / (256-부하)+K3 *지연
$$

• 상수의 기본값 : K1 = K3 = 1, K2 = K4 = K5 = 0
• K5가 0이 아닐 경우 아래 연산 추가

 

$$
메트릭 = 메트릭 * K5 / (신뢰도 +K4)
$$

 

• 동작
  • 다중 경로에 대해 라우팅 수행
  • 메트릭 값이 가장 적은 경로 선택

---

EIGRP(Enhanced Interior Gateway Routing Protocol)

• RIP의 단점 해소
• 네트워크 상태 효과적 반영

1. 수렴 속도가 빠르며 부분적인 갱신 지원
2. VLSM(Variable Length Subnet Mask) 지원
3. DUAL 알고리즘이용
4. 다양한 네트워크 프로토콜 지원
5. IGRP와 호환

• 메트릭 계산 연산
  • 더 정확한 수치 비교를 위해 메트릭 값을 크게 조정

$$
지연=지연*256
$$

$$
메트릭 = K1 * 대역폭 + (K2 * 대역폭) / (256-부하)+K3 *지연
$$

$$
대역폭=(10^7/대역폭)*256
$$

 

• 동작
  1. 헬로 패킷 교환을 통해 인접 라우터 발견
     • 5초 간격으로 전송(홀드 타임 정보(default - 15") 함께 삽입)
  2. 초기 라우팅 정보 교환 후에는 토폴로지나 메트릭 변화가 있을 때만 변경된 부분을 인접 라우터로 전송
  • 갱신 메시지를 수신한 라우터는 응답 메시지를 보냄으로써 메시지 전달의 신뢰성 보장
  1. 수신한 라우팅 정보를 토대로 DUAL 알고리즘 수행 → 최적 경로 계산
     1. 루프가 없는 최적의 경로
     2. 피저블 석세서(Feasible Successors)를 찾아 라우팅 테이블에 기록
        : 특정 목적지까지의 경로 비용이 자신보다 작은 인접 라우터
     3. 경로를 동적으로 할당하고 끊긴 경로에 대한 자동복구 수행
• EIGRP 패킷 포맷

---

OSPF(Open Shortest Path First)

• 모든 라우터가 동일한 네트워크 토폴로지 데이터베이스를 기반으로 경로 계산
• → 라우팅 루프 발생 ❌
• 네트워크 변화 시에만 라우팅 정보 전송
• → 라우팅 트래픽 양 감소
• 플러딩을 통한 갱신 속도 향상
  • 플러딩 : 갱신 정보를 인접 라우터로 전송, 인접 라우터는 다시 자신의 인접 라우터로 갱신 정보 전달 - 신속 전달
• 동작
  1. 인접 라우터간 인식
  2. 라우팅 정보 전달
     • 데이터 베이스 교환 과정
  3. 링크 상태 알고리즘 수행
  • 인접 라우터 간 동기화 이후 변화 발생 시, LSA(Link State Advertisements) 수행
    • 링크 상태 광고(LSA) : 링크 상태에 변화가 있을 때만 정보 교환
      • 라우터 링크 LSA
      • 네트워크 링크 LSA
      • 요약 링크 LSA
      • AS 외부 링크 LSA
  • 링크 상태 알고리즘(다익스트라)
    • 네트워크 토폴로지와 모든 노드에 대한 링크 비용을 알고 있다고 가정
    1. 모든 노드의 집합을 M이라고 한다.
    2. 집합N에 출발 노드를 넣는다.
    3. M에 있는 노드에 대해 출발 노드와 인접하다면 그 비용값을 c(노드)에 기록한다.
    4. 인접하지 않다면 c(노드) 값은 무한대로 설정된다.
    5. M에 있는 노드에 대해 c(노드) 값이 최소인 노드 x를 찾는다.
    6. 최소인 노드 x를 집합 N에 넣는다.
    7. 최소인 노드 x에 인접하고 집합 N에 없는 노드에 대해서 x를 통하는 경우와 그렇지 않은 경우에 대해 비용을 계산하여 최소값으로 갱신한다.
    8. 모든 노드가 집합N에 포함될 때까지 4~6 과정을 되풀이한다.
• OSPF의 계층 구조
  • AS를 다수의 영역으로 나누고 각 영역은 독립적으로 OSPF를 수행
    • 라우터 브로드캐스팅은 영역 내로 제한
    • 영역간 정보 전달은 영역 경계 라우터를 통해 수행
  • OSPF의 상위 계층 영역 : 백본 영역