Layer3 Routing

Routig Control Plane(plane - 특정프로세스가 발생하는 위치에 대한 추상적 개념)

• Router 내의 Data forwartding / routing 에 따라 기능이 나뉘어 진다
  • data forwarding - 수신프레임/패킷주소를 보고,
    • 입력포트로부터 어떤 출력포트로프레임/패킷을 전달
    • 또는, 이 장소에서 다음 장소로 전달
  • routing - 네트워크 안에서 통신 데이터를 보낼 때 최적의 경로를 선택하는 과정
• DATA plane - 네트워크에서 실제로 데이터를 전송하는 부분
  • ip header 분석
  • datagram forwarding(data gram)은 layer 3의 pdu 이름
  • fragmentation
  • 교통에서 굳이 비유를 하자면 data plane은 도로에 다니는 자동차이고
  • control plane은 신호등이나 도로 같은 역할이다.
• Control Plane - 데이터 패킷이 전달되는 방식을 제어하는 네트워크의 일부 제어 평면은 데이터 패킷 이 전달되는 방식을 제어하는 네트워크의 일부입니다. 즉, 데이터가 한 위치에서 다른 위치로 전송되는 방식을 의미합니다.

  • routing algorithm

  • ICMP - 인터넷 제어 메서지 프로토콜 네트워크 컴푸터 위에서 돌아가는 운영체제의 오류메세지를 주고 받는데 사용된다.

    Routing Algorithm

• Router 의 forwarding table
  • 입력 datagram에 대한 출력 port 를 정하기 위해 각 router가 보유한 표
• routing algorithm
  • routing table을 만들기 위한 각 router의 동작
  • decentralized - 중앙집권적이지 않게 동작해야한다, 너무 거대해서 중앙 집권적일 수 없음
• control plane의 routing algorithm에 의해 forwarding table 생성
• data plane 에서는 forwarding table 을 이용해서 동작 control plane에서 만들어진 forwarding table 을 사용해서 data plane에서 동작한다.
  • 이 ip address 목적지는 어느 port로 내보내야 궁극적으로 도달하는가를 결정
• routing algorithm의 최종 목적
  • Soure router(패킷 송신이 시작되는 라우터) - destination router (보낸 데이터 패킷을 수신하는 라우터) 간 최적의 경로를 찾는 것
  • https://doorbw.tistory.com/52 누군지 모르겠는데 너무 정리를 잘해줌
• Background
  • Routing algrithm 은 graph theory 를 기본적으로 활용한다
    • Graph G = (N,E) 노드와 엣지들을 합쳐놓은 것이다
      • 그래프 간략한 추가 설명 - 그래프는 vertex와 edge로 구성된 한정된 자료구조를 의미한다. vertex는 정점, edge는 정점과 정점을 연결하는 간선이다.
      • 발생 리스트(Incidence list) - 변들은 변으로 연결된 두 꼭짓점(방향이 있다면 순서가 존재함)와 가중치(weight), 다른 특정 데이터들을 포함하는 배열로 표현된다. 변으로 연결된 두 꼭짓점은 서로 인접(adjacent)한 관계라고 일컫는다.
      • 인접 리스트(Adjacency list) - 발생 리스트와 비슷하게도, 각 꼭짓점이 인접한 꼭짓점들의 리스트를 가진다. 따라서 방향성을 가지지 않은 그래프에서는 불필요한 정보가 생기게 한다. 예를 들어 만약 A와 B가 인접하다면 A의 인접 리스트는 B를 포함하게 되며 동시에 B의 리스트에도 A가 포함된다. 추가적인 저장 공간에 대한 비용이 있다면 인접 정보를 얻는 것은 빨라진다.
    • N: node들의 집합(router)
    • E: edge 들의 집합(router 간 연결)
    • Weight: cost = c(x,y) EX) u node에서 z까지 패킷을 전달하는데 드는 cost = c(u,z)
      • u,z는 Neighbor
    • path : (x,x1,x2,...,xp)

Routing path

• Least-cost path

  • cost 의 합이 최소인 경로
    

         위의 그림에서 u - w로의 경로를 찾는 경우에는 u - x - y -w이다.
         
         - 트래픽이라는 것이 가변적이 때문에 적용이 힘들다
         - 실
         

• Shortest Path

  • cost를 고려하지 않고 가장 짧은 path - 이게 내 생각에는 노드 간의 cost를 고려하지 않고 거쳐가는 노드들의 수를 최소화로 계산하는거 같은데 검색해도 안나와서 모르겠다
  • 모든 cost가 같은 경우의 least - cost path
  • 위의 그래프에서 least - cost - path를 구하고자 하면
    • 17가지 모든 경우의 수에 대해 해보면 답을 구할 수 있음
      • Centralized algorithm: It is also known as global routing algorithm as it computes the least-cost path between source and destination by using complete and global knowledge about the network. This algorithm takes the connectivity between the nodes and link cost as input, and this information is obtained before actually performing any calculation. Link state algorithm is referred to as a centralized algorithm since it is aware of the cost of each link in the network.
        • 이미 알고 있는 노드들간의 코스트 정보를 바탕으로 least cost path를 source와 distination사이에서 계산한다. 이미 노드들 사이의 코스트를 알고 있는 가정하에 진행되므로 중앙집권적인 알고리즘이다. 위의 그림에서 17가지 경로를 계산하면 알 수 있지만 실제로는 너무 방대해서 사용이 불가능하다
      • 실제 router들이하는 방식은 decentralized한 방식으로 각각의 라우터들이 자신의 주변 라우터들과 비교한다.

routing 종류 globla vs decentralized

• global routing algorithm

  • complete/global knowledge about network - 네트워크의 모든 정보를 알고 있다다는 가정하에 수행됨
    • connectivity, link에 대한 정보
  • Link - state(LS) algorithm - centralized 방식임 이미 각 링크의 코스트를 알고 있기 때문

• Decentralized routing algorithm

  • iterative, distributed manner 반복적, 분배방식 이건 교수님한테 다시 물어볼것 뭔 의미인지 모르겠음
  • node 가 주로 자신과 연결된 link에 대한 정보만을 가지고 단계적으로 동작하는 방법이다
  • distane - Vector algorithm

routing algorithm static vs dynamin

• Static routing algorithm
  • routing table 이 시간에 따라서 변하지 않음
    • 주로 사람의 조작에 의해서 변화해서 정적임
• Dynamin routing algorithms
  • Traffic load (인터넷에서의 데이터의 흐름) 및 topology(node 와 node 간의 물리적 또는 논리적배열)변화에 의해 자동으로 routing table이 변한다
  • 잘못하면 Routing loop, oscillation 문제가 발생한다.
  • 잦은 routing table의 변경이 일어나기 때문에 발생한다.
    • routing loop - A routing loop 은 흔하게 발생하는 네트워크의 문제 인데 A node에서 Cnode로 데이터를 전송하는 Bnode를 거쳐서 전송한다고 가정할 때 Bnode의 데이터 전송에 문제가 발생해서 Cnode로의 데이터 전송이 불가능한 것을 node A가 인지하지 못해서 Anode가 지속적으로 데이터를 전송해서 무한 루프가 발생한다...
    • oscillation 두개의 node 사이에서 반복적으로 node A 가 최단거리라고 판단해서 nodeB로 보냈는데 nodeB도 nodeA로 가는게 졸라 합리적이라고 판단하면 둘만 데이터를 졸라 주고 받는거야 맞나...?

Fixed Routing

• Permanent route: 고정으로 routing 규칙을 지정
  • IP address특정 대역 등에 대해 out port지정
• 활용시점
  • 전체관리가 사람에 의해서 이루어질때
  • 부분적으로 고정된 규칙을 적용하고 싶을때
• 간단하지만 flexbilliy가 적고 수고가 많이 든다
  • network failure, congestion등의 dynamin한 상황에 취약하다

Flooding

• 모든 neighbor들에게 packet을 무조건 뿌린다 (연결된 node로 무조건 갈겨)
• 최종적을 destitnation은 multiple copy 형태로 수신한다
  • sequence number를 통해서 duplicatioin을 방지 가능하다.
• 단순함
  • routing protocol, table등이 필요없어서 control plane(네트워크에서 데이터 전송을 제어하는 부분) 관점에서 simple
  • traffic load가 불필요하게 너무 크며 재전송에 대한 제어가 필요하다.

Link state routing

• Topology 및 모든 link cost를 파악하고 routing table생성
  • Link- state broadcast algorithm을 통해 활용한다
    • 각자의 indentity와 link 별 cost정보를 neighbor에게 전달한다
  • 모든 node가 동일한 routing 정보를 공유할 수 있음

Dijkstra algorithm

• least - cost path를 iterative하게 파악한다.
• D(v) 목적지 v까지의 현재까지 계산한 cost
• p(v) 목적지 v까지의 경로에서 바로전 node
• N이미 파악해서 알고 있는 목적지까지의 cost들의 집합

1. 다익스트라 알고리즘에서 아직 확인되지 않은 거리느 전부 초기값을 무한으로 잡는다

위의 그림에서 S는 거리를 알고 있는 node의 집함

Q는 거리를 모르고 있는 집합

제일 먼저 출발지를 A로 가정하면 A까지의 거리는 0이다 따라서 d[A]는 0의 값을 가진다.

나머지 node는 아직 방문하지 않아서 무한대로 가정

1. 루프를 돌려서 이웃 노드를 방문하고 거리를 계산한다.

항상 루프의 시작은 현재 방문하지 않은 노드들의 집합 Q에서 거리 값이 최소인 노드를 탐색하는 것이다.

A노드를 제외한 나머지 노드들의거리값은 무한대이므로 노드 A를 기준으로 탐색을 시작합니다. A노드에서 B,C,D에 대한 거리 값을 계산하여 기록한다.

1. 루푸 이후의 그래프의 상태가 업데이트 되는 방식

위의 사진은 두번째 루프를 마치고 난 뒤의 모습입니다.

2번에서 언급한 바와 같이 두번째 루프의 시작 또한 방문하지 않은 노드들의 집합 Q에서 거리 값이 최소인 노드로 시작합니다. 따라서 거리 값이 10으로 최소인 B노드를 기준으로 탐색을 시작합니다. B노드를 방문하였으므로 집합 S에 기록하고 E의 거리값을 계산합니다. 거리 값을 계산할때는 출발지로 부터 탐색노드(기준노드)사이의 거리값과 탐색노드와 이웃노드의 거리값을 더한 값 입니다. 따라서 노드 E의 거리값은 10+20=30으로 기록됩니다.

1. 더 빠른 경로를 발견한 경우

동일한 방식으로 세번째 루프에서는 D노드로 시작합니다. 이때 D노드를 기준을 탐색을 하면 C노드에 대한 거리값이 20으로 계산됩니다. 이전에 기록되어 있는 d[C]값인 30보다 더 짧은 최단 경로이므로 새롭게 계산된 값으로 업데이트를 합니다

1. 방문하지 않은 노드들의 집합이 공집합이 될 때 까지 반복합니다.

위의 사진은 네번째 루프를 실행한 결과입니다. 위의 2~4번 과정에서 총 3번의 루프를 설명하였듯이 지속적으로 네번째, 다섯번째, 여섯번째 루프를 반복합니다. 마지막 루프까지 계산을 하면 최종적으로 다음과 같은 값을 가질 것 입니다.

d[A] = 0 / d[B] = 10 / d[C] = 20 / d[D] = 15 / d[E] = 30 / d[F] = 25

최종 목적지가 F 였으므로, 최단 경로의 거리 값은 25이며 그 경로는 A,D,C,F 입니다.

Link State Routing

• 예시
  • node가 늘어날 수록 D()값이 줄어든다
  • p를 추적하면 path를 찾을 수 있다
• Forwarding table 결과
  • Routing path 를 고려해서 destination을 고려하여 destination별로 out-port지정
    
• congestion - sensitive routing 과정에서의 oscillation
  • Link cost를 traffic load로 가정하면
  • Traffic 상태에 따라 Routing경로가 안정적이지 못하고 왔다갔다 할 수 있음

Distance - vector Routing

• LS routing 과는 다르게 asynchronous/ distribute함
  • neighbor node 끼리만 정보를 주고 받으면서 routing계산
  • 더이상 neighbor node끼리 정보를 주고 받을 일이 없을 때까지 iterative하게 정보를 교환/계산을 반복한다
  • 각 node가 알아서 정보 교환을 하고 계산을 수행한다
• bellman - ford equation활용 - 거리를 분해하는 방법인데 dx(y) = minv{ c(x,v) + dv(y)}
• x node에서 y node까지의 거리를 c(x,v)x와 v까지의 가중치 + dv(y)(v에서 y까지의 거리)}
• 기본적인 routing algorithm 방향
  • 각 node x 는 Dx(y)값을 특정 초기값으로 적절히 설정하고
  • distance vector Dx에 대해서 아라 정보를 통해 지속적으로 updata한다
  • 각 neighor v, 에대해서 c(x,v)바로 붙어있는 neighbors와의 cost를 계산
• 이웃의 DV정보만 이용하며 DV정보 교환을 각node가 알서 asyncronous하게 함.
• 각 노드가 DV를 받아서 table을 생성하고 DV를 받으면 변동이 없을때 까지 교환을 계속한다 최종적으로 각각의 table 이 동일해 진것을 볼 수 있다.
  

• Link - cost change 1: cost reduced
  • t0: y detects cost change(4 →1) y의 코스트가 감소한걸 라우터가 broad cast하면
  • t1: z receives update(Dz(x): 5 →2) 라우터 z에서 코스드가 감소한걸 인지하고 Z→x까지의 cost를 수정함
  • t2: y 도 변화를 업데이트 받는데 바뀌는게 없다
    
• Link - cost change 2: cost increase
• 초기에는 z에서 x로 가는것이 x에서 y이를 경유해서 가는게 더 저렴했음

  • t0: y detects (4→ 60), Dy(x) = Dy(z) + Dz(x) = 6

    • node y가 값이 60으로 증가한것을 감지하고 z →x경로를 1만큼 증가시킨다.

  • t2: y가 업데이트를 받아서 Dz(x) = 5 →7로 증가시킨다.)

  • 이후 link cost가 50이 될때까지 1씩 증가한다. 너무 많은 반복이 일어난다.

    

    자 진은아 잘봐 맨처음에 각 테이블에 y의 테이블에는 y→x:4, y→z:1, z→x:5라고 되어있을거야 근데 이때 이 z→x는 y를 경유한 cost라는걸 y는 몰라 그래서 y→x가 60으로 증가했으니까 이제 시발 y→z로 들렀다가 z →x로 가면 되겠다 싶어서 다시 자기 테이블에 z→x를 y→z의 cost인 1을 증가시켜 그러면 6이 될꺼야

    이 6이 저장이 되는데 y → x cost 가 6인겨 그리고 이걸 broad cast하면 z 어디를 경유한다는 정보가 없으니까 발생하는 문제야 z에서는 x→y가 6으로 증가했으니까 아 여기서 x까지 보내는데 비용이 7 = 6+1이 되겠네 하고 증가시켜 시발 그러면 다시 이제 forwarding table에 z→x는 7로 싱크되면 다시 이제 y에서는 졸라 멍청하게 다시 증가시키는거여 이게 몇번된다? 50보다 커질때 까지니까 45번 정도

    

    Link state vs Distance vector

• DV : 인접 node끼리만 정보 교환, 정보 내용은 모든 node 에 대한 cost
• LS: 모든 node 정보교환, 정보 내용은 인접 node에 대한 cost
• massage complexity
  • LS는 많은 메세지 전송이 필요, DV는 link cost변화 빈도에 따라 메세지 전송 횟수 증가
• speed of convergence: DV가 convergence 속도가 느리다 syncornize하는데 오레걸림
• robustness(견고성): LS는 가자 routing 을 계산하는 방식이라 더 안정적임

Hierarchical Routing

• 실제 internet 은 sub-network와 gateway router 형태로 계층적으로 네트워크를 형성
  • subnet 간 packet routing 은 gateway router 를 통해서만 이루어짐
• AS(autonomus System): 한 기관이 관리하는 router 및 network모음
  • 동일한 routing protocol에 의해 밀접하게 동작
• intra vs inter-AS routing
• intra as: AS내에서 일어나는 routing
• inter as: AS 간에서 일어나는 routing

Routing information Protocol (RIP) - Intra AS routing

intra-AS routing 에 주로 활용되는 routing algorithm

• distance vector protocol에 속하며 link cost가 모두 1이다(hop count용)
• hop count 가 cost metric이다(max 15, 즉 최대 hop 15개 까지만 전달)
• 30초 마다 RIP응답 메세지(RIP)패킷를 브로드케스팅하는데, 이 브로드케스팅을 위한 ip address로 하여 브로드케스팅 주소로 사용한다.
  • advertisement/Adverising
  • 라우터 , 무선노드 등 장비에서, 장비들 간에 일정주기 또는 필요시에, 자신 및 주변 정보(라우팅 갱신정보 등)을 알리는 과정을 말한다.

RIP Routing Table

• Distance vector 및 Forwarding table을 갖고있다
• Routing advertisement message를 수신 후 Routing 정보를 갱신한다.
• 180초 이상 routing advertisement message 수신이 없으면 no longer reachable이라 판단한다
• Routing table 을 수정하고 advertisement message를 보낸다

RIP Requset Message

• (수신을 안주면) 특정 destinatio에 대한 neighbor’s cost를 달라고 요청한다.(UDP,port 520)

Open Shortest Path First (OSPF)

• RIP의 다음 버전이며, 여러가지 개선된 기능을 가진다
• Dijkstra least - cost path algorithm 기반이며 ,link state에 대한 flooting 활용
  • complete topological map을 기반으로 모든 subnet 에 대한 shorteset - path계산
  • link cost 는 network administrator가 지정하기 나름이며, 모든 link cost를 1로 설정하면 minimum-hop routing이 됨
• 모든 router에게 link state information을 broadcasting함
  • robustness를 위해서 link change가 없어도 최소한 30분에 한번수행

Border Gateway protocol

internet 에서의 Exterior router protocol(AS간의 라우팅을 위해서 활용)

• AS간 routing을 위한 protocol
• 아래 세가지 역할 수행
  • 인접 AS간 subnet reacjability information교환
  • reachability 정보에 대해 AS내 router에게 전달
  • subnet 에 대한 routing 결정

key design issue

• Routing performace — 라우팅 수행
  • Correctness Optimality
• Low control over head
  • 너무 잦은 메세지 교환으로 오버헤드가 높아지면 안됌
  • simplicity Efficiency(간결성 , 효휼성)
• Robustness Stability Fairness(공정성, 서비스를 잘 고루 받아야한다.)