컴퓨터네트워크

컴퓨터 네트워크 4-2 네트워크 계층

begong 2023. 1. 17. 02:19
반응형
참고서적 : 컴퓨터 네트워킹 하향식 접근 제 6판 Kurose, Ross

5.라우팅 알고리즘

  • 주어진 라우터와 라우터를 연결하는 링크들의 집합에서 출발지 라우터에서 목적지 라우터 까지 좋은 경로를 찾는 것.

라우팅 알고리즘 분류

  • 글로벌화,분산화 알고리즘
    • 글로벌 라우팅 알고리즘
      • 네트워크에 대한 완벽한 글로벌 정보를 가지고 출발지와 목적지 사이의 최소비용 경로를 계산
      • 링크 상태(link state) 알고리즘이라고 부르기도 함
    • 분산 라우팅 알고리즘
      • 노드가 모든 네트워크 링크의 비용에 대한 완벽한 정보를 가지고 있지 않음.
      • 각 노드는 링크에 직접 연결된 링크의 비용에 대한 정보만 가지고 있음.
      • 반복 계산 과정과 이웃 노드와의 정보교환을 통해 목적지 또는 목적지 집합까지 최소비용 경로를 계산
      • 거리 벡터(distance-vector)알고리즘
  • 정적, 동적 라우팅 알고리즘
    • 정적 라우팅 알고리즘(static routing algorithms)
      • 사람이 개입하여 경로 변화
      • 라우터의 포워딩 테이블을 수작업으로 수정
    • 동적 라우팅 알고리즘(ddynamic routing algorithms)
      • 네트워크 트래픽 부하나 포톨로지 변화에 따라 라우팅  경로를 바꿈
  • 부하에 민감/둔감
    • 부하에 민감한 알고리즘(load-sensitive algorithms)
      • 링크비용에 하부 링크의 혼잡 수준이 바로 반영
    • 부하에 둔감한 알고리즘
      • RIP,OSPF,BGP 등

5.1 링크상태 라우팅 알고리즘

  • 다익스트라 알고리즘(Dijkstra's algorithm)
    • 한 노드에서 네트워크의 다른 모든 노드에 이르는 최소비용경로를 계산
    • (추후 추가)

5.2 거리 벡터 라우팅 알고리즘

  • 반복적이고 비동기적이며 분산적
  • 벨만-포드식(Bellman-Ford equation)
    • (추후 추가)

5.3 계층적인 라우팅

  • 라우터의 개수가 증가함에 따라 라우팅 정보계산, 저장 및 통신에 관련된 오버헤드가 현저하게 증가
  • 라우터를 원하는 방법대로 작동시키거나 외부로부터 네트워크 내부 조직을 숨기려고함
  • 위의 두 문제를 자치 시스템(autonomous system, AS)로 집합화하여 해결
  • intra- AS
    • 인트라-AS 라우팅 프로토콜(intra-autonomous system routing protocol) : AS 내부에서 동작하는 라우팅 알고리즘
    • 같은 AS안에 있는 라우터는 같은 라우팅 알고리즘을 사용, 상대방에 대한 정보를 가지고 있음
    • 게이트웨이 라우터(gateway routers) : AS에서 외부 목적지 AS에 패킷을 전달하는 라우터
  • inter - AS
    • 인터-AS라우팅 프로토콜 (inter-autonomous system routing protocol): AS간 통신에 관여
    • 모든 AS는 BGP-4라는 라우팅 프로토콜을 사용
  • 각 라우터는 인트라-AS라우팅 프로토콜과 인터-AS라우팅 프로토콜로 부터 정보를 수신하고 두 프로토콜로부터의 정보를 자신의 포워딩 테이블을 구성하는데 사용
  • 핫포테이토 라우팅(hot-potato routing)
    • AS는 가능한 빨리(최소비용으로) 패킷을 없엠.
    • 라우터가 패킷을 목적지로 가는 경로의 모든 게이트웨이 중에서 최소의 라우터-게이트웨이 비용을 갖는 게이트웨이 라우터로 보냄

6. 인터넷에서의 라우팅

6.1 인터넷에서의 인트라 -AS 라우팅 :RIP

  • 라우팅 정보 프로토콜 - RIP(Routing Information Protocol)
  • DV 알고리즘에 매우 근접하게 동작하는 거리 백터 프로토콜
  • (추후 작성)

6.2 인터넷에서의 인트라 -AS 라우팅 :OSPF

  • 개방형 최단경로 우선 - OSPF(Open Shortest Path First) 
  • 다익스트라 최소비용경로 알고리즘을 사용
    • 라우터는 자신을 루트 노드라 간주하고 모든 서브넷에 이르는 최단경로 트리를 결정
    • 개별 링크 비용은 네트워크 관리자가 구성
  • 다른 모든 라우터에게 라우팅 저보를 브로드캐스트
  • 링크 상태가 변경되지 않았더라도 정기적으로 링크 상태를 브롣즈캐스트 함

6.3 인터-AS 라우팅 :BGP

  • 경계 게이트웨이 프로토콜 (Border Gateway Protocol)
  • BGP 세션 : BGP메시지가 보내지는 TCP 연결
  • 외부 BGP (external BGP, eBGP) : 두 AS에 걸치는 BGP 세션
  • 내부 BGP (internal BGP, iBGP) : 같은 AS 내의 라우터 간의 BGP세션
  • BGP는 각 AS가 이웃 AS를 통해 어느 목적지가 도달할 수 있는지 알게 함
  • BGP에서는 유일한 AS번호(autonomous system number, ASN)로 각각의 AS를 식별
    • 모든 AS가 ASN을 가지는 것은 아님
    • 출발지와 목적지에 대한 트래픽만을 전송하는 스텁 (stub AS)는 대체로 ASN을 갖지 않음

7. 브로드캐스트와 멀티캐스트 라우팅

7.1 브로드캐스트 라우팅 알고리즘

  • 송신노드가 패킷의 개별 복사본을 각 목적지로 송신
  • N 목적지 노드에 대하여 출발지 노드는 패킷의 N개 복사본을 만들고, 서로 다른 목적지로 주소를 넣고, N개의 목적지로 유니캐스트 라우팅을 이용하여 패킷의 N개 복사본을 보냄
  • 단점
    • 비효율성
    • 송신자에게 수신자와 주소를 알려줘야 하여 프로토콜에 복잡성과 부담을 증가시킴
    • 브로드캐스트를 하기 위해서 유니캐스트 라우팅 기반 구조에 의존

7.2 멀티캐스크

  • 멀티캐스크 패킷이 네트워크 노드 중에서 한 서브셋으로만 전달
  • 멀티캐스크 데이터그램은 간접 주소를 사용
    • 단일 식별자가 그룹 수신자를 위해 사용되고 이 단일 식별자를 사용해서 그룹으로 주소 지정된 데이터그램 복사본이 그룹에 속한 모든 멀티캐스크 수신자에게 전달
반응형