컴퓨터 네트워크 - 5(Network layer)

박승현·2023년 9월 9일

컴퓨터 네트워크

목록 보기
5/6

introduction

  • Routing을 수행하는 부분이 control plane

  • control plane 구현 2가지 방법(data plane과 동일)

    • per-router control(각각의 라우터에 routing 알고리즘 구현)
    • logically centralized control(하나의 논리적 컨트롤러가 모든 라우터의 정보를 관리, 알고리즘 수행) + 물리적으로는 하나가 아닐수도 있음
    • control, data plane이 분리되어 있는 방법
    • remote controller가 물리적으로 따로 존재

Routing protocols

  • 라우팅에 필요한 정보를 주고받는 프로토콜
  • routing : 여러가지 경로 중에서 좋은 경로를 찾는 과정
  • 좋은 경로 : 비용이 적은 경로, 빠른 경로, 혼잡이 적은 경로

Routing algorithm classification(알고리즘 방법 분류)

  • Global or decentralized
    • global
      • 모든 라우터와 링크, 링크의 코스트 등 모든 정보를 알고 있을때
      • "link state" 알고리즘 이라고 부름
    • decentralized
      • 이웃 노드와 그 노드로 가는 링크의 코스트 정도만 알때
      • 이웃 노드끼리 정보를 주고 받아야함
      • "distance vector" 알고리즘으로 부름
  • static or dynamic
    • static(보통 한번 작성하면 끝, 거의 사용 안함)
      • 경로가 느리게 변하는 상태
    • dynamic
      • 경로가 자주 변함
      • 주기적으로 네트워크 상태 업데이트

Dijkstra 알고리즘

  • 그래프 전체, 링크 코스트가 각각의 노드(라우터)가 알고있다는 가정
    • link state broadcast를 통해서 달성(이웃 노드, 링크, 코스트에 대한 정보를 이웃에게 전달하는 방법을 반복하는 방법
    • 완료 후에는 모든 노드가 같은 정보를 가지게 됨
  • 그 후에 자신을 source로 해서 다른 모든 노드로 향하는 최단 경로를 계산
    • 계산한 정보를 바탕으로 해당 노드의 포워딩 테이블을 작성(각각의 노드가 본인의 포워딩 테이블을 작성함)
  • K번 반복하면 K개의 목적이에 대한 경로를 계산
    • 노트가 n개이면 n번 반복하면 모든 경로를 찾을 수 있음

Dijkstra 알고리즘 과정

  • notation
    • C(x, y) : x -- y에 대한 링크의 코스트(이웃이 없으면 코스트 = 무한대
    • D(V) : source to V로 가는 현재까지 발견된 경로 중 최소값
    • P(V) : 경로에서 V바로 앞에 있는 노드를 저장
    • N' : 현재까지 최단경로를 찾은 노드들의 집합
  • 과정
    • 시작 : 자기자신(u)으로 가는 경로 0으로 시작, source에서 인접한 모든 노드 v에 대해 최단경로는 바로 저장 가능 -> 최단경로 = c(u, v)
    • 이전 노드를 활용해서 트리를 만들 수 있음 -> 이 트리를 이용해 포워딩 테이블을 만듬
    • 0 : 시작, 인접 적어주기
    • 1 : 인접한 노드 중 가장 가까운거 꺼내서 꺼낸거의 인접한 노드로 가는 경로를 계산해줌
    • 2부터는 반복 -> 1의 결과 중 가장 짧은거 꺼내기
    • 꺼낼때마다 N'에 추가하고 추가된 애는 꺼내지 않음

Dijkstra 알고리즘으로 포워딩 테이블 만들기

  • 목적지에 따라서 본인 기준 어느쪽으로 보낼지만 정해주면 됨

Dijkstra 알고리즘 discussion

  • 최악은 O(n^2)인데 네트워크에서는 보통 O(nlogn + e) e = 엣지 개수
  • oscillations possible : 시간에 따라 링크의 코스트를 바꾸고 그에따라 경로가 바뀌는 방식
  • 트레픽이 많으면 코스트를 높여서 다른쪽으로 보내는 방법인데 이러면 한쪽만 쓰다가 다른쪽만 쓰다가 하기 떄문에 이 방법은 쓰면 안된다

Distance vector algorithm

Bellman-Ford equation사용

  • 기본 : 멀리 있는 Y에 도달하기 위해선 이웃해있는 V중 가장 가까운 v를 거쳐야 한다는 개념 ->
  • 주어진 정보 + 본인 이웃 정보 조합해서 모든 경우 구하고 최소값으로 적용
  • 실제 네트워크에서는 모든 노드가 이 알고리즘을 수행해야함
  • Dx(Y) : x에서 y까지 가는 최단 경로의 추정치, 노드 x는 x에서 모든 노드 n에 대한 추정치의 집합인 Dx를 벡터 형태로 가지고 있음, distance vector라고 부름
  • 노드별로 가지고 있어야 하는 것
    • 이웃으로 가는 링크의 코스트
    • 자기 자신의 distance vector(Dx)
    • 이웃들의 distance vector(Dv)
  • 주기적으로 본인의 distance vector를 이웃에게 전달해줌
  • 이웃의 Dv를 받으면 본인의 Dx를 갱신하는데 이때 벨만포드 알고리즘을 사용함 -> 대문자는 추정치고 소문자는 실제 값인데 추정치가 시간이 지나면 결국 실제값에 수렴해서 사용해도 무리가 없음

Distance vector algorithm정리

  • 반복시행, 비동기적 : 나, 이웃의 정보가 바뀌면 계산하는 작업 시행
  • distributed : 각각의 노드는 본인의 정보가 변결 될 때만 이웃에게 알려주면 됨
  • wait -> 변경되면 다시 계산 -> 변경정보 이웃에게 전파 -> wait이던 이웃은 변경된 내용 받아서 다시 계산(무한 반복)
  • 과정
    • 2번째 칸에서 3으로 바뀐과정 : x에서 바로 z로 가는 방버과 y에서 받은 Dv를 바탕으로 y를 거쳐서 z로 가는게 짧은지 비교한 것
    • 바뀐 내용만 전송
    • 새로 계산한 내용이 기존과 같으면 그 값이 실제 값으로 수렴 하게 된 것

Distance vector : link cost changes

  • 링크의 코스트가 변경 될 때

    • 코스트가 줄면 2단계 만에 수렴함

      1. 링크 코스트 변경 및 y가 정보 파악, 재계산 후 이웃에게 전파
      2. z재계산, 전파
      3. 1에서 전파된 내용으로 y가 재계산 하지만 변경 사항이 없기 떄문에 z에게 전파하기 않고 수렴함

    • 코스트가 늘어나면 굉장히 오래 걸림

      • 기존 z to x의 값이 5였으므로 y에서 재 계산하면 y to x가 1 + 5로 6이됨
      • 이 6을 바탕으로 z에서는 1 + 6으로 7이됨
      • 반복하다 51을 알려주면 그냥 z에서 바로 x로가는 50이 최소값이 되므로 그때 종료(44번 반복)

    • Poisoned reverse : z가 y에게만 x로가는 경로가 무한대라고 알려주는 방법(다른 노드에게는 그냥 5라고 알려줌), 이 방법도 완전히 해결은 못함

  • message complexity
    • LS : n node, e link -> O(ne), 모든 링크의 정보를 n개의 노드가 받아야 하기 때문
    • DV : 이웃의 정보만 사용하기 때문에 계산하기 어려움
  • Convergence(수렴)
    • LS : O(n^2) -> 다익스트라 알고리즘 한 번 수행하면 끝
    • DV : 변화가 큼 (예측 힘듬)
  • robustness
    • LS : 하나의 잘못된 정보가 큰 영향을 끼치진 않음
    • DV : 벨만포드 알고리즘으로 하나의 정보가 잘못되면 계산할때마다 잘못되기 떄문에 rovustness 측면에선 좋지 않다

intra-AS routing in internet : OSPF

Making routing scalable

  • 이전의 알고리즘들은 모든 라우터의 성능이 동일하고 네트워크가 동등한 레벨에 있다고 가정하지만 실제로는 그렇지 않음
  • 수십억개의 라우팅 테이블을 작성하는 것도 사실상 불가능
  • 네트워크 마다 사용하는 방식도 다름

autonomous systems(AS) : 라우터들의 집합

  • intra-AS routing(AS 내부)
    • AS를 관리하는 주체가 하나
    • 같은 routing protocol 사용해야함
    • 다른 AS에서는 다른 방식의 라우팅 프로토콜을 사용할 수 있음
    • gateway router : 다른 AS로 가는 링크를 가지고 있는 라우터
  • inter-AS routing(AS간의 라우팅)
    • gateway router는 두개의 라우팅을 둘다 시행할 수 있어야 함

AS간의 연결

  • forwarding table 작성 : intra, inter AS알고리즘이 협업해서 작성해야함
    • AS내부의 목적지 : intra알고리즘만 사용
    • AS외부의 목적지 : 둘다 사용

inter-AS tasks(intra는 이전의 알고리즘(다익스트라, 벨만포드)을 사용하면 됨)

  • AS1은 AS2,AS3 각각을 통해 도달할 수 있는 목적지를 수집함
  • AS1의 모든 라우터에게 수집한 정보를 공유

OSPF(Open Shortest Path First)

  • 프로토콜임
  • open : 정보 공유의 의미(누구나 사용 가능)
  • Link-State 알고리즘 사용
  • IP바로 위에 메시지가 합쳐져서 보내짐(TCP, UDP에서 사용하지 않는다)
  • 특징
    • 보안 강화
    • 한개의 목적지에 대한 코스트가 같은 여러개의 경로를 허용
    • TOS에 따른 다른 링크 코스트를 제공 -> TOS에 따라 다른 테이블을 사용할 수 있음
    • multi-cast허용 : 하나의 source에서 여러개의 목적지로 전송 가능(브로드케스트와 다르게 목적지 여러개 설정 가능)
    • 계층 구조 지원 : 하나의 라우터가 정리해서 다른 구역에 전송하는 구조

routing among the ISPs : BGP

inter-AS routing: BGP

  • BGP : Border Gateway Protocol : AS간의 라우팅에 사용하는 프로토콜
  • BGP의 사용방법
    • eBGP : 주변 AS의 정보를 수집할 때
    • iBGP : 수집한 정보를 AS내부에 전파 할 때
    • 두 개는 동일한 프로토콜인데 사용방법에 따라 다르게 부르기만 하는 것
    • 서브넷의 존재를 다른 인터넷에 알려야 정보가 생성, 전달 되는데 알릴 수 있는 기능을 BGP가 제공함

eBGP, iBGP연결

  • 내부와 외부로 분류하는데 게이트웨이 라우터는 2개다 수행함
  • TCP를 통해 프로토콜을 전달함
  • BGP는 경로를 광고함, 경로는 라우터가 아닌 어떤 AS를 거치는지 나타내는 경로임 그래서 BGP를 path vector라고도 부름
  • AS는 본인 서브넷의 존재를 광고
    • advertisement msg의 구성요소
      • 서브넷의 prefix + attributes(추가 정보) = route
    • two important attributes
      • AS-PATH : 서브넷이 지나왔던 AS들을 저장
      • NEXT-HOP : 다음 AS로 가기 위해 지나가는 라우터
  • advertisement msg는 정책에 따라 받거나 주변에 알릴때 선택적으로 시행 가능함
  • AS 지날때 AS-PATH추가 해주기, 경로가 여러개인 1C 입장에서는 좋은 경로 하나를 정책에 따라 결정한 뒤 AS내부의 라우터에게 전파

BGP messages

  • TCP연결 사용
  • MESSAGES
    • OPEN : TCP 연결, 암호등이 맞는지 인증
    • UPDATE : 새로운 경로 광고, 기존 경로 회수
    • KEEPALIVE : 일정시간 메세지를 주고 받지 않으면 tcp가 끊어지기 떄문에 이를 방지하기 위해 주고받는 msg
    • NOTIFICATION : 에러와 연결을 끊을때 사용

BGP, OSPF로 forwarding table 작성

  • BGP로 게이트웨이간의 경로 작성
  • AS 내부에서는 OSPF로 게이트웨이로 보내는 경로 작성

BGP route selection

  • 게이트웨이에 여러개의 경로가 들어올 때 어떤걸 고를지 정하는 방법
    • attrivute에 local preference라는 int값이 있음 이걸 큰걸 고른다
    • AS-PATH가 짧은거
    • NEXT-HOP이 가까운 것을 고름

Hot Potato Routing

  • 제일 빨리 내보낼 수 있는 경로로 보냄(코스트가 작은 것)

policy

  • A에서 보낸 w에 대한 정보를 B가 x에게 전달해주지만 C에게는 전해줄 필요가 없음
  • C도 마찬가지로 x,y에게는 알려주지만 B에게는 전송하지 않는다
  • A, B, C : PROVIDER NETWORK
  • X : dual-homed 링크가 하나 끊어져도 다른 링크로 연결 가능
  • policy to enforce : x는 B,C에게 정보를 전달해 주 필요가 없음 -> drop시킴

intra,inter routing

  • policy : inter-AS는 정책이 중요 intra는 내부에서 정하기 때문에 크게 신경쓰지 않는다.
  • scale : 계층적으로 routing해서 트레픽을 줄임?
  • performance : intra-AS -> 성능에 중점을 둠, inter-AS -> 성능보다는 정책에 중점을 둠

ICMP : internet control message protocol

  • 호스트와 라우터가 네트워크 레벨의 정보를 전달 할때 사용(에러를 전달할때), request/reply
  • IP위에 존재(IP 페킷의 데이터 부분에 들어감)
  • ICMP message : type, code와 에러를 일으키는 IP 데이터의 첫 8바이트로 구성 type,code로 에러의 종류를 파악함

Traceroute and ICMP

  • TTL 1부터 3번씩 보냄
  • TTL은 1씩 증가, TTL을 다 쓰게 되면 라우터에서 에러 ICMP(11, 0)을 보내는데 이걸 받으면서 각 라우터에 대한 RTT를 계산 가능
  • TTL을 증가 시키다보면 목적지에 도달하는데 초기에 사용하지 않는 포트번호를 지정했기 떄문에 에러 ICMP(3, 0)을 목적지에서 보내게 됨
  • 다른 에러를 받으면 목적지에 도착한 것이기 때문에 TTL을 증가 시키지 않고 종료

Network management and SNMP

  • 네트워크에 존재하는 여러 기기와 라우터등을 모니터링, 관리하는 것 -> 실시간으로 성능, 품질을 보장하기 위해서
  • 각각의 기기에 관리에 필요한 정보를 Management information base(MIB)에 저장하는데 이 정보를 교환 할때 사용하는 프로토콜이 SNMP임

SNMP 모드

  • 두가지 모두 필요
  • 첫번째는 요청을 통해 통신, 두번째는 정보를 알아서 managing entity로 보내줌
profile
박승현
KMU SW
이전 포스트

컴퓨터 네트워크 - 4(Network layer)

다음 포스트

컴퓨터 네트워크 - 6(Link layer)

0개의 댓글