라우터이번 글에서는 라우터의 동작에 대해 정리해보려고 한다.라우터는 일종의 컴퓨터이다.라우터에도 OS가 들어가고, 여러 보드가 들어가있다. 라우터의 아키텍처는 위와 같이 되어있다.라인카드로 된 인풋 포트와 아웃풋 포트가 앞단에서 패킷을 받거나 보내고, 라우터는 여러 네트워크와 연결이 되어있으므로 그 중간에 인터페이스가 필요한데, 인터페이스 자체가 컴퓨터이면서 그 안에 여러 컴퓨팅 보드가 존재하는 것이다.이때 지금 그림에서는 왼쪽에서 오른쪽 방향으로 표현하여 input port, output port 를 구분했지만, 이는 방향에 따라 구분되는 것이지 실제로 각 라인카드가 input port, output port 의 역할을 정적으로 수행하는 것은 아니다.방향만 반대로 바꾸면 얼마든지 서로의 역할이 바뀔 수..
Control Hazard 제어 해저드는 분기를 할 때, 분기 여부의 결정을 MEM 단계에서 결정하게 되므로 MEM 단계 이후에 fetch 하는 명령어 이전까지의 명령어들을 모두 실행할 수 없게 되는 (실행하면 안되는) 해저드를 말한다. 지금 회로를 설계할 때는 branch prediction을 항상 하고 있다고 생각하고 회로를 고쳐볼 것이다.이때 예측하는 방식은 not taken 할 것이라고 예측한다고 하자.만약 not taken을 예측하고 있는데, taken 하게 된다면 그 사이에 fetch 해서 실행중이던 명령어는 모두 flush 처리할 것이다. 위 그림에서 beq명령어가 실행되는 시점의 PC 값은 40이고, MEM 단계까지 가고나면 분기 여부와 이때의 주소값을 알 수 있게 된다.그리고 WB 단계를..
Data Hazard 우선 Forwarding 이 적용되지 않은 상황에서 그냥 pipeline MIPS 회로에 그대로 위와 같은 과정으로 명령어를 실행한다고 해보자.그럼 클럭 사이클 (CC) 이 지나갈 때 회로의 흐름이 위와 같이 나타난다.그런데 첫번째 명령어인 sub의 결과로 $2 레지스터에 값이 쓰이는데, 그 다음 명령어는 곧바로 $2 레지스터의 값을 이용해 연산을 한다.즉, 데이터 의존성이 존재하는 것이다. 먼저 명령어의 흐름을 가로축으로 보았을 때, sub 명령어에 기존에는 10이라는 값이 있었고, sub 연산 결과 -20이 저장된다고 하자.그러면 WB 단계 전까지 Reg 에는 10 이 저장되어 있다가, Write Back 이 되는 전반부 쓰기 동작 이후에는 -20이 저장될 것이다. 이번엔 명령어..
Group모든 평면 투영 변환의 집합들은 그룹을 형성한다.그리고 각각의 그룹에는 특별한 케이스들이 있다.이제 다양한 특별한 케이스 (특별한 평면 투영 변환) 을 정리한다. 우선 group은 아래와 같은 특성을 갖는다. 1. 특정 그룹에 속하는 a, b 에 대해서, a와 b를 연산현 결과도 그 그룹 안에 속한다.이를 '닫혀있다' 라고 표현한다. 2. 연산 순서에 영향을 받지 않아야 한다. (associative 하다고 한다.) 3. identity element를 가져야 한다.identity element는 이 element와 다른 element를 연산했을 때, 그 다른 element가 그대로 나오도록 하는 element를 말한다. 4. 특정 group 안에 있는 모든 element에 대해, 그들의 inv..
개요네트워크 계층에 대한 내용은 크게 data plane 과 control plane으로 구분된다.data plane은 라우터 내에서 지역적으로 일어나는 일을 다루고, control plane은 네트워크 전반적으로 일어나는 일을 다룬다. 우선 data plane을 먼저 정리하려고 한다.data plane에서는 라우터의 input port, output port 그리고 그 사이에 흘러가는 데이터 흐름, IP 프로토콜에 대해 정리한다.또 Generalized Forwarding, SDN 에 대해서, 여러 중간 장치인 Middlebox에 대해서도 정리한다. 이 그림에서 3계층에 대한 이야기를 하기 시작하면, 이제 Network Core에 대한 이야기를 같이 하게 된다.(라우터가 보통 3계층 스위치 장비로서 사..
Datapath개요이제 pipeline을 적용한 MIPS의 회로도를 그려보자. 이 회로도는 j 명령어 (무조건 분기) 를 고려하지 않은 CPU 회로도이다.먼저 단순하게 기존 single cycle 회로도에서 단계를 나눈 뒤, 단계 사이사이에 flip-flop(파이프라인 레지스터)을 넣어두었다. 하나의 스테이지 동작을 마친 뒤, 다음 스테이지에서 이어서 하기 위해 그때까지 수행한 값을 레지스터에 보관해두는 것이다.각각의 파이프라인 레지스터 이름을 구분하기 위해, 어떤 단계 사이에 끼어있는 레지스터인지로 이름을 명시하였다. 이제 이 CPU는 동시에 최대 5개의 명령어를 처리할 수 있게 되었다. 예를 들면 위와 같이 특정 시점에서 5개의 명령어를 동시에 실행하고 있을 수 있다.이 그림에서는 분홍색으로 색칠한 ..
Homographyhomography는 평면 투영 변환 행렬을 가리키는 말이다.평면 투영 변환은 2차원 평면에 어떤 변환 H를 가해 다시 2차원 평면으로 만드는 것을 말한다. 이걸 사용하는 이유는 수학적으로 어려운 개념을 인간의 관점에서 쉽게 이해하기 위함이다.예를 들어 이전 내용에서 무한대에 위치한 점은 homogeneous 좌표계로 나타냈을 때 세번째 원소가 0이었고, 이들을 모두 이으면 하나의 원이 나온다고 했었다.그런데 이런 수학적인 표현은 인간의 두뇌로는 상상도 잘 안되고 이해하기 힘들다. 그래서 그냥 평행선이 있다고 할 때 이걸 인간의 시점에서 잘 비틀어보는 것이다.그러면 우리가 도로를 바라볼 때 먼 지점의 도로가 한 점에서 만나듯 (소실점) 무한대에 있는 점들은 한 곳에서 만난다는 것을 인간..
Homogeneous CoordinatesR² 을 2차원 실수 공간이라고 하자.R² 에 속하는 하나의 직선은 ax + by + c = 0 을 만족하는, R² 에 속하는 점 (x, y) 의 집합이다.이를 통해 R² 에 속하는 하나의 직선은 (a, b, c) 를 통해 나타낼 수 있다. 이때 l 을 (a, b, c) 라는 3차원 파라미터 벡터라고 하자.그러면 (x, y) 라는 2차원 물리 점은 3D 벡터 (x, y, 1) 로 나타낼 수 있다. ax + by + c = 0 이라는 등식은 (a, b, c) · (x, y 1) 으로 나타낼 수 있다.이때 3차원 실수 공간 R³ 에 속하는 (x, y, 1) 을 2차원 실수 공간 내부의 점 (x, y) 에 대한 homogeneous coordinate 표현이라고 한다...
TCP, UDP 프로토콜은 40년이 넘은 굉장히 오래된 프로토콜이다.그래서 현대의 인터넷 사용환경과 맞지 않는 부분도 꽤 있다. 예를 들면, 과거에는 무선 인터넷이라는 것이 존재하지 않았지만, 지금은 무선 인터넷이 굉장히 흔하다.이런 새로운 환경의 변화에 의해 새로운 도전과제가 생겼을 때, 어떻게 발전을 해야하는지에 대해 정리해보려고 한다. 1. 대역폭이 매우 큰 데이터 링크매우 넓고 긴 대역폭을 가진 링크는 과거에 불가능했지만, 지금은 가능하다.예로 백본에서 사용하는 급의 링크는 10Gbps 이상의 대역폭을 제공하기도 한다. 그런 상황에서의 문제는 굉장히 많은 패킷들이 in-flight 될 수 있다는 것이다.미국 서부에서 동부 끝까지 데이터를 보내는 상황을 생각해보자.만약 stop-and-wait 프로..
Congestion (혼잡)네트워크에서의 '혼잡' 은 너무 많은 source host (sender) 가 너무 많은 데이터를 너무 빠르게 전송해서 네트워크가 이를 처리할 수 없는 상황을 의미한다.즉, 네트워크 트래픽이 몰려있는 상황, 고속도로에 차가 몰려서 차가 막히는 상황과 같다. 데이터가 몰리면 라우터 버퍼에는 패킷이 계속 쌓이니 queueing 딜레이가 증가하니 데이터 전송 시간이 증가할 수 있고, 심한 경우 라우터의 버퍼가 넘쳐서 패킷 Loss가 발생할 수 있다. 이때 혼잡 제어와 흐름 제어를 구분하면흐름 제어는 1:1 상황(TCP, UDP)에서 너무 많은 데이터를 보내는 것을 제어하여 receiver 의 버퍼가 넘치지 않게 조절하는 것을 말하고혼잡 제어는 다수의 sender가 데이터를 너무 많이..