전체 글109 4.2 라우터 내부 -라우터의 구조 4.2.1 입력 포트 처리 및 목적지 기반 전송 입력 포트의 맨 왼쪽 박스와 출력 포트의 맨 오른쪽 박스는 라우터로 들어오는 입력 링크로, 물리계층 기능을 수행한다, 들어오는 링크의 반대편에 있는 링크 계층과 상호 운용하기 위해 필요한 링크 계층 기능을 수행한다. 이것은 입력 및 출력 포트에서 미들박스로 표시된다. -입력 포트에서 수행되는 검색은 라우터 동작의 핵심이다 -라우터는 포워딩 테이블을 사용하여 도착 패킷이 스위치 구조를 통해 전달되는 출력 포트를 검색한다 -포워딩 테이블은 라우팅 프로세서에서 계산되거나 갱신되거나 원격 SDN컨트롤러에서 수신된다 -포워딩 테이블은 라우틍 프로세서에서 그림과 같이 입력 라인 카드로 복사된다 -각 라인 카드에서 섀도 복사본을 사용하면 패킷 단위로 중.. 2023. 3. 26. 4.1 네트워크 계층 개요 -네트워크 계층 : 보내는 host에서부터 받는 host로 segment를 전달한다. sender(보내는 host) : 세그먼트를 얻어서 데이터그램으로 캡슐화하고 링크 레이어에게 보낸다. receiver(받는 host) : 세그먼트를 추출해서 트랜스포트 계층까지 전달한다. c.f) segment : 전송계층에서 다루는 데이터 단위 -네트워크 계층은 모든 인터넷 장치(라우터, host)에 설치되어 있다. -라우터가 하는 일 : 라우터에 들어온 데이터그램의 header를 살펴보고, 데이터그램을 input port에서 output port로 전달해줌, 어떤 output port를 선택할것인가를 결정함 4.1.1 포워딩과 라우팅: 데이터 평면과 제어 평면 -네트워크 계층 기능 1. forwarding(전달) :.. 2023. 3. 26. 1.4 패킷 교환 네트워크에서의 지연, 손실, 처리율 -패킷 delay , loss 어떻게 일어날까? 먼저 패킷은 첫번째 라우터 버퍼에 도달하게 된다. 그리고 다음 라우터로 전송하기 위해서는 첫번째 라우터에 저장이 되어야 한다. 이 때 패킷이 첫번째 라우터에 도달하는 속도 > 다음 라우터에 전송되는 속도 일 경우 들어오는 것이 많아지니 점점 쌓이게 된다. => queue(= 다음 라우터로 나가기를 기다리는 줄)가 생기게 된다. 계속 패킷이 쌓이다 보면 첫 라우터에 저장 공간이 줄어들게 된다. -> 더 이상 저장할 공간이 없어지면 (=가득 차게 되면) 데이터를 잃어버리게 된다. = loss 발생 -패킷 delay가 발생하는 4가지 지연 유형 1) 처리 지연(processing delay) : 비트 에러 조사 패킷을 어떤 output link로 보낼지 결정 :.. 2023. 3. 14. 힙(Heap), 힙화(Heapify), 최댓값, 최솟값 구하기, 구현 ●힙(Heap) - 최댓값, 최솟값을 빠르게 검색할 수 있는 자료구조 - 완전이진트리(Complete Binary Tree) 형태로 구성 - Max Heap, Min Heap으로 구성 - Max Heap(최대 힙) 부모노드 >= 자식노드 => 루트에 최댓값이 들어있다. - Min Heap(최소 힙) 부모노드 루트에 최솟값이 들어있다. -힙 트리에서는 이진탐색트리와는 다르게 중복된 값을 허용한다. -힙화(Heapify) 무작위로 데이터가 들어간 배열 구조를 힙 구조에 맞게 변경하는 것 이런 트리구조가 있다고 해보자. 3 2 4 1 5 6 먼저 자식노드가 있는 노드들을 중심으로 생각한다. 1, 5, 6은 자식 노드가 없기 때문에 일단 제쳐놓는다. 자식중에 더 큰 노드의 값을 찾는다. 부모와 자식을 비교한 다.. 2023. 2. 25. 이진탐색트리 노드 삭제 개념, 구현 ●노드 삭제 경우 3가지 - 자식 노드가 없는 경우 - 자식 노드가 한 개인 경우 - 자식 노드가 두 개인 경우 - 자식 노드가 없는 경우 위의 트리에서 3번 노드를 없애려고 한다. 3번노드 삭제 -> 3번노드의 부모인 2번노드에 NULL을 넘겨준다. - 자식 노드가 한 개인 경우 2번노드를 없애려고 한다. 2번노드를 바로 없애버리면 1번노드의 정보가 사라진다. 그래서 temp 임시변수를 하나 만들어서 1번노드의 주소를 저장한다. 과정: temp에 1번노드 저장 -> 2번노드 삭제 -> 1번노드의 주소값을 4번노드에 넘겨준다. - 자식 노드가 두 개인 경우 루트인 8번노드를 없애려고 한다. 왼쪽 자식중 최댓값을 구해서 삭제하려는 위치로 덮어쓰기 한다. 위의 트리에서는 왼쪽 최댓값이 7이므로 원래 8자리에.. 2023. 2. 24. 이진탐색트리 최댓값, 최솟값 노드 찾기, 구현 ●이진검색트리의 특징 부모를 기준으로 부모보다 큰 데이터 오른쪽에, 작은 데이터는 왼쪽에. 따라서 루트를 중심으로 오른쪽 끝까지 찾아가면 최댓값을 찾을 수 있다. 왼쪽 끝까지 찾아가면 최솟값을 찾을 수 있다. ●최댓값, 최솟값 찾는 과정 구현 typedef struct TREE { int value; struct TREE* left; struct TREE* right; } TREE; TREE* findMax(TREE* t) { if(t) { while(t->right) t = t->right; return t; } } TREE* findMin(TREE* t) { if(t->left) t = findMin(t->left) return t; } 반복문으로 구현할 수 있으면 반복문으로 구현하는 것이 좋다. 최.. 2023. 2. 23. 이전 1 ··· 14 15 16 17 18 19 다음
