Local Feature Extraction서로 다른 이미지에서 물체를 매칭하기 위해서, 각 물체의 '특징'을 추출해야 한다.현대에는 특징점 추출 연산으로 SIFT, SURF 와 같은 연산자를 사용하며, 이들은 스케일 (크기 변봐) , 방향, 밝기 변화에도 불구하고 같은 특징을 갖는 (불변한 값을 갖는) 특징점을 찾는 것을 목표로 한다. 사실 이미지의 특징으로 사용할 수 있는 것 중에 지난 글에서 정리한 방법대로 검출했던 '엣지' 가 있다.하지만 엣지가 제공하는 정보는 강도와 방향, 2가지에 한정된다.보다 다양한 정보를 특징으로 사용하기 위해 엣지대신 gray scale 이미지로부터 추출되는 local feature 를 사용하는 방법이 등장했다.  이 이미지는 같은 물체를 서로 다른 방향에서 찍은 이미지..

Distance VectorBellman-FordDistance Vector 는 벨만포드 알고리즘 기반의 라우팅 알고리즘이다. 벨만포드 알고리즘은 DP 기반의 알고리즘인데, 위와 같은 점화식을 사용한다.나(x)로부터 목적지(y)까지 가는데, 필요한 최단 경로는 나의 이웃 노드 v가 알려준 Dv(y) 값들과 내가 알고있는 v까지의 거리 Cx,v 로부터 최소값을 계산해서 얻는다는 아이디어다.(이때 기존의 Dx(y) 값은 사용하지 않는다. 링크의 비용이 증가하는 쪽으로 갱신되어 최소값도 증가했다면, 증가한 것으로 계산해야 되기 때문이다.) Link State 에서 사용했던 예제 그림에 벨만포드를 그대로 적용해보자.u에서 z로 가는 최단 경로를 찾고자 한다.  u와 인접한 v, x, w 로 부터 각각 그 노드(..

Link State링크 스테이트 방식은 말 그대로 각 라우터가 자신이 알고있는 '링크 정보' = '링크 스태이트' 를 모두 공유해서 같은 네트워크 맵을 보는 상태를 만들고, 이 맵을 input으로 다익스트라 알고리즘을 돌려서 최단 경로를 얻는 방법이다. 다익스트라 알고리즘은, 시작점이 고정되어있을 때, 그 시작점으로부터 다른 모든 목적지까지의 최단경로를 구하는 알고리즘이다.따라서 각각의 라우터는 자신을 시작점으로 해서 다익스트라를 돌리면 다른 모든 라우터까지의 최단 경로를 알 수 있다.이를 통해 포워딩 테이블을 만든다.  LS 알고리즘을 설명할 때 위와 같은 노테이션을 사용한다.Cxy는 x에서 y로 가는 비용을 말하며, 직접 연결된 링크가 없으면 무한대 값을 갖는다.D(v)는 현재 측정한 v까지 가는 최..

Network Control Plane컨트롤 플레인에는 전통적인 라우팅 알고리즘 (하지만 여전히 자주 쓰인다. 포워딩 테이블을 만드는데 사용한다.) 과 SDN 컨트롤러에 대한 내용을 다룬다.또 network 관리와 설정하는 것도 control plane 영역에서 다룬다. 실제 인터넷에서 널리 사용하는 라우팅 프로토콜로 OSPF 와 BGP가 있다.두 프로토콜이 적용되는 영역이 달라서 두 프로토콜 모두 중요하게 사용된다.상술한 전통적인 라우팅 알고리즘 내용과 관련있다. SDN 컨트롤러 개념을 구현한 프로토콜로는 OpenFlow, ODL, ONOS 컨트롤러 등이 있다.각각은 모두 특정 브랜드 이름이고, OpenFlow는 지난 글에서 정리했듯 공개된 표준이고, ODL과 ONOS은 일종의 OS이다. 네트워크를 관..

lw $1, 8($0)8번 virtual address 에서 레지스터로 데이터를 가져올 때 일어나는 과정1. virtual address 를 physical address로 변환하기1. TLB 에 접근8번 주소를 분해한다.만약 주소의 길이가 32bit 라면 4KB 페이지 크기를 고려하여 12bit 를 떼고,TLB 인덱스의 개수가 8개라면 3bit 를 index bit 로서 추가로 떼어내, 남은 17 bit 를 tag 로서 TLB 에서 PA를 찾는다. 1-1. TLB HitTLB Hit 라면 바로 Physical Address 를 가져온다.이때 TLB에 기록된 dirty bit, ref bit는 신경쓸 필요가 없는걸까? 1-2. TLB Miss메인 메모리에 있는 Page Table에 직접 접근한다. (Pa..

TLB가상 메모리를 사용할 때 참고하는 page table 이 메모리에 있기 때문에, page를 읽으려고 할 때마다 접근하는 시간이 오래 걸린다. (메모리에 대한 접근을 매우 느리게 만든다.)메모리의 특정 부분에서 데이터를 읽기 위해서 2번의 메모리 접근이 필요한 것이다. 첫번째는 VA를 PA로 변환하기 위해 page table에 접근하면서 1번 메모리에 접근하고,두번째는 이렇게 얻어온 PA를 가지고 데이터/명령어를 읽어오기 위해 메모리에 한번 더 접근한다. 그래서 이 문제를 해결하기 위해 하드웨어 지원을 추가하는 방법을 고민했다.page table에 대한 접근은 그래도 spatial locality가 꽤 좋다.명령어의 크기가 4byte인 것에 비해 4KB라는 페이지 크기는 매우 넉넉해서 한번 페이지를 ..

Middlebox미들박스는 source host로부터 목적지 호스트로 가는 데이터 경로상의 IP 라우터를 제외한 모든 다른 네트워킹 장치를 일컫는다.IP 라우터는 normal (인터넷 설계 초기부터 매우 중요한 설계 요소) 인데, 인터넷 설계 초기에는 고려하지 않았던, 새롭게 등장한 장치들을 모두 미들박스라고 한다. 대표적으로 NAT 가 있다.만약 IP주소가 넉넉해서 모든 IP주소를 항상 원하는 단체, 기관, 개인에게 공급할 수 있었다면 NAT는 등장하지 않았겠지만, IP주소가 부족한 문제가 발생해서 NAT가 source - destination 경로 사이에서 IP라우터가 하는 일 이외의 다른 일을 하기위해 등장했다. 이런 장치를 미들박스라고 한다. Middlebox 종류1. NAT 2. Firewall..

Edge Detection의 기본 원리어떤 물체의 내부, 또는 그 물체의 배경에 대해 변화가 작다면, 배경과 물체 사이의 경계 주위에서는 큰 변화가 있을 것이다.이 관찰에 기반해서, Edge detection 알고리즘은 밝기, 색상, 텍스쳐 등의 변화량을 측정하고, 큰 변화가 발생한 위치를 edge로 인식한다. 이 작업을 수행하기 위한 가장 간단한 방법은, 각 픽셀에서 gray level의 gradient vector를 계산하는 것이다.이미지를 흑백으로 바꾼 뒤, 밝기의 차이만 보는 것이다. 그 값은 위와 같이 계산할 수 있다.또한 절대적인 변화량은 이렇게 절댓값을 씌워서 얻을 수 있다.그리고 이 변화량은 마치 수학에서 두 점 사이의 변화량을 보는 것과 같이 그 변화의 뱡향을 따질 수 있다.이때 변화의 ..

Generalized Forwarding지금까지 정리한 포워딩 방식은 IP 패킷을 받으면, 이 패킷의 목적지 IP주소를 보고, 가장 길게 매치되는 것을 포워딩 테이블에서 찾아서, 그 다음 목적지로 가기 위한 output link(port) 를 결정했었다. 이번엔 이 방법보다 조금 더 일반화된 포워딩 방법을 정리해보려고 한다.왜 output port 를 찾을 때 목적지 주소만 봐야 하는가, Source IP주소를 봤을 때도 도움이 될 만한 부분이 실제로 많다. 예를 들어 인터넷 해킹에서 공격 시발점의 source ip주소를 보고, black list에 있는 IP주소와 매칭되면 원천적으로 방화벽에서 차단시켜버리는 경우가 있다.홍대도 매일 100건 이상의 공격시도가 들어오는데, 물론 공격자들이 IP주소를 바꿔..

IPv6(IPv5는 실험적 목적이므로 건너감!)IPv6는 나온지 20년이 넘은 꽤 오래된 개념이다.약 27년전 시점부터 IPv4의 주소가 고갈될게 분명해져서 그 전에 새로운 주소 체계를 도입하고자 등장한 것이 IPv6이였다.그런데 주소 체계를 바꾼다는 것은 꽤 큰 일이다.32bit 에서 128bit 주소 체계로 바꾼다는 것은, 일단 양립성을 포기하는 것과 같다.32bit 주소체계를 쓰면서 동시에 128bit 주소 체계를 사용하는 것이 불가능하기 때문이다. 그래서 IPv6를 설계할 때는 어차피 처음부터 만들 거 IPv4에서 마음에 안들었던 부분을 다같이 바꾸자고 생각했고, 많은 부분들이 개선되었다. (option, checksum 과 같은 필드가 삭제되었다.)따라서 헤더의 크기가 고정되었기 때문에, 프로세..