Router

1. Router

• 컴퓨터 네트워크에서 데이터 패킷이 경로를 선택하고 목적지까지 전송될 수 있도록 하는 네트워크 장비
  

• 역할

  1. 패킷 처리: IP 패킷은 출발지와 목적지 주소를 가지고 있으며, 라우터는 이러한 주소 정보를 사용하여 데이터를 목적지로 전달
  2. 라우팅 프로세서: 목적지 IP 주소를 사용하여 패킷을 어떤 출력 포트로 보낼지 결정
     → 라우팅 테이블을 참조
  3. 스위칭 패브릭: 라우팅 프로세서가 패킷의 목적지를 결정한 후, 패킷은 스위칭 패브릭을 통과하여 목적지 출력 포트로 전달

---

2. Longest prefix matching

• 목적지 IP 주소의 네트워크 부분에 대해 가장 긴 프리픽스 (주소 일치 부분)를 찾아서 해당 라우팅 경로를 결정하는 원칙
  

  • 11001000 00010111 00010110 10100001: 0번 link로 전달
  • 11001000 00010111 00011000 10101010: 1번 link로 전달

• 과정

  1. 목적지 IP 주소 추출
  2. 라우팅 테이블 검색: 목적지 IP 주소와 가장 길게 일치하는 쪽의 prefix(네트워크 ID)를 찾기 위해 라우팅 테이블을 검색
  3. 라우팅 결정: 선택한 가장 긴 프리픽스 네트워크 ID에 해당하는 라우팅 경로를 사용하여 패킷을 전달

---

3. Switching fabrics

• 네트워크 장비(예: 스위치, 라우터 등)에서 패킷 전송이 이루어지는 내부 구조

• 네트워크 장비의 내부 구조 중 하나로, 입력 포트에서 데이터 패킷을 받아 출력 포트로 전달하는 과정을 관리

• 스위칭 레이트(Switching Rate): 스위칭 패브릭은 패킷이 입력 링크로 들어와서 출력 링크로 전달되는 속도

• 스위칭 패브릭 구조
  

  1. Memory: 각 입력 포트에서 들어오는 패킷들을 메모리로 복사한 다음, 선택된 출력 포트로 전달하는 방식
     
     • 메모리 액세스가 2번씩 일어나므로 속도가 제한된다.
       → 입력 포트에서 메모리로 패킷 복사
       → 메모리에서 선택된 출력 포트로 패킷 전달
  2. Bus: 입력 포트에서 출력 포트로 패킷을 전달하는 데 하나의 공유 버스 회선을 사용하는 방식
     
     • bus contention: 공유 버스 회선의 대역폭이 한정되어 있으므로, 동시에 처리할 수 있는 패킷의 수가 제한된다.
     • 패킷 충돌: 모든 패킷이 하나의 버스를 공유하기 때문에, 여러 패킷이 동시에 버스에 접근하면 패킷 충돌이 발생할 수 있다.
       → 한 사이클 당 하나의 패킷만 처리 가능
  3. Interconnection network: 크로스바 형태로 여러 개의 노선 입력 포트 및 출력 포트들이 서로 교차하는 형태로 구성
     
     • 교차로의 교차점에서는 신호의 조합을 통해 패킷의 경로를 설정
     • 하나의 출력 포트로 향하는 다중 경로를 제공함으로써, 여러 패킷이 빠르게 이동할 수 있으며 처리량이 높아진다.
     • 교차점이 많아질수록 관리와 설계가 복잡해지고 비효율적일 수 있으므로, multi-stage switch 구조를 도입

• Multi-stage switch

  

  1. Cross Point 수 감소: 다중 스테이지 스위치 구조를 도입하면 크로스 포인트의 수를 줄일 수 있다.
     → 라우터의 전체 크기를 줄일 수 있으며, 설계와 관리가 더 효율적으로 이루어질 수 있다.
  2. 병렬 처리: 다중 스테이지 스위치는 다중 경로를 통해 병렬 처리를 지원한다.
     → 여러 패킷이 동시에 다른 경로를 통해 전달될 수 있으므로 처리량이 증가하고 지연 시간이 감소할 수 있다.

---

4. Input port queuing

• 스위치 패브릭이 패킷을 처리하는 속도보다 입력 포트로부터 패킷이 빠르게 들어오는 상황

  • HOL 발생: 큐에 있는 패킷 중에서 가장 앞에 있는 패킷이 뒤에 대기하고 있는 다른 패킷들이 큐 앞으로 이동하는 것을 방해하는 상황
  • Queueing delay 발생
  • Buffer management policy 필요: Drop policy 등을 결정
    → 만약 버퍼에 더 이상 공간이 없다면 Buffer overflow로 인해 패킷이 드롭 될 수 있으므로, 어떤 패킷을 드롭 할 것인지를 결정하는 정책이 있어야 한다.
    

---

5. Output port queueing

• 출력 포트 큐의 크기가 제한되어 있고 도착 패킷의 속도가 출력 라인 속도를 초과할 때, 데이터가 계속 들어오면 큐가 가득 차서 출력 포트로 패킷을 전송하는 데 지연이 발생할 수 있다.
  

---

6. Buffer management

• Drop policy: 버퍼가 가득 차 있는 상황에서 어떤 패킷을 드롭할 것인지 결정하는 정책

  • Tail Drop: 새로 도착한 패킷을 바로 드롭하는 정책
  • Priority Drop: 패킷에 우선순위를 할당하고, 우선순위가 낮은 패킷을 드롭하는 정책
  • Marking: 패킷의 헤더에 추가 정보를 표시하거나 설정함으로써 네트워크의 혼잡 상태를 관리
    • ECN 필드를 설정하여 혼잡을 표시
    • RED 알고리즘은 혼잡 발생에 의해서 일부 패킷이 랜덤하게 drop되기 전에 패킷을 마킹하여 혼잡을 알림
    • 마킹된 패킷은 우선적으로 처리되어 혼잡을 완화

---

7. Packet scheduling

• 버퍼에 도착한 패킷 중 어떤 패킷을 언제 처리할 것인지를 결정하는 과정

1. FCFS (First-Come, First-Served): 먼저 도착한 패킷을 먼저 처리하는 간단한 스케줄링 방법으로 패킷의 우선순위나 특성을 고려하지 않는다.

2. Priority Queuing: 여러 개의 큐들에 대해서 우선순위를 할당하고, 높은 우선순위의 큐에 담긴 패킷이 먼저 처리되는 방식
   

   • 낮은 우선순위를 가진 큐에 담긴 패킷은 처리되지 못하고 무기한으로 기다리는 starvation 발생할 수 있다.

3. Round Robin: 큐를 기준에 따라 일정한 시간만큼 번갈아 가면서 처리
   

   • 패킷 단위로 처리: 큐의 사용 시간 단위로 할당을 하면, 어떤 패킷은 모두 처리 되지 않고 패킷 전송이 중간에 끊길 수 있다.
   • 패킷 크기는 모두 다르므로, 공평하게 패킷 단위로 RR을 구현하기는 까다롭다.
   • 큐 간에 우선순위가 있다면, 모든 큐가 공평하게 처리에 대한 할당을 받는 것은 불공평해진다.

4. Weighted fair queueing: 큐에 우선순위 가중치를 할당하고, 해당 가중치만큼 큐 사용시간을 분배하는 방식