[ch4] 2. what's inside a router

Router architecture overivew

• control plane (SW)
  • routing processor
    • 모든 routes(forwarding table)를 계산한 다음, line card들에 복사함
    • 각 line card에 shadow copy로 복사해, forwarding 결정들이 라우팅 프로세서를 다시 거치지 않고 각 input port에서 locally하게 일어날 수 있음
  • time unit: millisecond
• data plane (HW)
  
  • router input ports
    • line termination: physical layer
    • link layer protocol: data link layer
    • lookup, forwarding, queueing
      • decentralized switching: 헤더 필드를 사용해서, input port memory에 저장되어 있는 forwarding table의  output port를 찾음 ("match plus action")
        • destination-based forwarding (tradition): destination IP address에 의해 forward
        • generalized forwarding (SDN): header field value에 의해 forward
      • 목표: "line speed"로 input port processing 끝내기
      • queueing: 데이터그램이 switch fabric으로 forwarding rate보다 더 빠르게 도착하면 저장됨
  • router output ports
  • high-speed switching fabric: routing processor를 거치지 않고 switch
  • time unit: nanosecond

 

Longest prefix matching

• forwarding table entry를 볼 때, destination address와 match되는 longest address prefix를 사용해라
• nanoseconds 안에 실행되어야 함
• 종종 cache보다 빠른 ternary content addressable memory(TCAM)을 사용해서 수행됨
  • content addressable: 현재 주소를 TCAM에 옮김. 테이블 사이즈와 관계없이 한 클락 사이클에 주소를 찾음
• packet의 output port가 lookup을 통해 결정되면, packet은 switching fabric으로 옮겨짐
  • switching fabric은 port가 여러 개라서 바쁠 수 있음
  • 바쁜 경우, packet이 block되고 queue에 저장되어 나중에 전송될 수 있음

 

Other functions in input port

• physical-layer and link-layer processing
• packet의 version number, checksum, TTL이 check되어야 함
  • TTL과 checksum은 다시 작성되어야 함
• network 운영에 사용되는 couters가 업데이트 되어야함. packet이 얼마나 들어가고 나갔는지를 업데이트
  • ex) ipconfig

 

Switching fabrics

• packet을 input port buffer로부터 적절한 output port buffer로 옮김
• switching rate: packet이 input으로부터 output으로 전송될 수 있는 속도
  • 여러 input/output line rate에서 측정되기도 함
  • N * line_rate
    • N: inputs
    • 항상 그런 것은 아님
• type
  • memory
  • bus
  • crossbar: 동시에 움직이는 것 가능

 

Input port queueing

• N input ports보다 fabric이 느리면 input queue에 queueing 발생
• 이상적으로, output port들이 다 다르면 여러 패킷들이 병렬로 전송될 수 있다.
• Head-of-the-Line (HOL) blocking
  • queue의 젤 첨에 쌓인 데이터그램이 다른 큐가 forward하는 것을 막는 현상

 

Output ports

• output port의 메모리 안에 저장되어 있는 packet을 가져와서 output link로 전송시킴
• buffering: 데이터그램이 전송속도보다 빠르게 fabric로부터 도착했을 때
• scheduling: queue에 쌓여 있는 packet을 선택해서 전송을 위해 dequeue함
  • priority scheduling: 가장 좋은 성능과 망 중립성을 가짐

 

Output port queueing/buffering

• switch를 통한 도착률이 output line의 speed를 넘어설 때 버퍼링
  
  • packet을 drop 해야하는 상황이면, drop-tail, RED (random Early Detection ) 등 어느 것을 drop해야할지 선택하는 알고리즘이 존재함
• 얼마나 많이 buffering?
  • RFC 3439 rule of thumb: RTT * C 
    • C: link capacity
  • 최근에는 저기다가 sqrt(N)을 나눔 
    • N: output port #

 

Scheduling mechanisms

• Scheduling: link로 보낼 다음 packet을 선택하는 것
• FIFO: 젤 앞에거 가랏~~
  • discard policy: queue가 가득차있는데 packet이 도착하면 뭘 버림?
    • tail drop: 도착한 애 버리기
    • priority: 우선순위에 따라서 버리기
    • random: 랜덤으로 버리기
    • other: e.g. RED
• Priority Scheduling
  • 높은 우선순위 순서대로 보내기
  • 다양한 타입(class), 다양한 우선순위
    • class는 header info에 따라 결정될 수도..
      • control pkt. vs. data pkt., VoIP, etc.
• Round Robin (RR) Scheduling
  • 다양한 타입(class)
  • class들의 큐를 순환하며 스캔해, 그 큐에서 packet하나를 내보냄
• Weighted Fair Queuing (WFQ)
  • 일반화된 Round Robin
  • 도착된 packet은 적절한 class로 분류되어 queue에 쌓임.
  • WFQ 스케줄러는 RR 스케줄러와 같이 각 큐들을 순환하며 동작함
  • 특정 기준에 따라 가중치를 정하여 같은 큐 내에서도 차별을 두는 방식