Loopin's Page

Chapter 4.

- Transport 층과는 달리 각 호스트와 네트워크의 라우터마다 네트워크 계층의 일부가 존재한다. 곧, 라우터가 지닌 계층은, Application, Transport 계층은 없다. 그 아래 계층인 Network, Data link, Physical 층 세 단계로 이뤄져 있다.

- Transport 층에선 파일에 대한 패키징 작업을 하는데, 패킷 헤더에 가야할 dest 를 기입한다. 이후 Network 층으로 넘겨 진행되고 라우터에선 이를 보고 판단하여 처리.

@ Forwarding(전달) : '단일' 라우터에서 입력 링크로부터 출력 링크로 패킷을 전달하는 것(갈림길!) 각 라우터는 포워딩 테이블을 지니는데, 이 테이블은 라우팅 알고리즘에 의해 결정된다.

@ Routing : 네트워크의 '모든' 라우터들, 출발지로부터 목적지 노드까지의 패킷이 지나가는 경로를 결정. 라우터들의 전체 연동이 포함된다. 덧붙여, 전체 경로를 계산하는 알고리즘을 라우팅 알고리즘(routing algorithm)이라 한다.

@ 네트워크 서비스 모델

송신 호스트에서 Transport 계층에서 Network 계층으로 넘어갈 때 제공될 서비스

- 보장된 전달 : 패킷이 반드시 목적지에 도착함을 보장

- 제한 지연 이내 전달 : 보장된 전달과 함께, 특정 지연 제한(100ms 이내)안에 전달.

출발지와 목적지 사이의 패킷 흐름에 제공되는 서비스

- 순서화(in-order) 패킷 전달 : 송신된 순서로 도착하는 것을 보장.

- 보장된 최소 대역폭, 보장된 최대 지터(jitter, 송신자에서의 두 개의 성공적인 패킷 전송 사이 시간 간격이 목적지 수신 시간 간격과 동일하도록 보장), 보안 서비스(기밀성) 등을 제공한다.

$ 하지만 인터넷 네트워크 계층은 최선형 서비스(Best-effort service)를 제공한다. 곧, 대역폭 보장이 없고, 무손실 보장도 없고, 어떤 순서로 송신, 수신되고 가능하고, 타이밍도 유지하지 않으며 혼잡 암시 또한 없다.

@ 네트워크 계층에서의 명칭

- 연결형 서비스만을 제공 : 가상회선 네트워크(Virtual-Circuit Network)

- 비연결형 서비스만을 제공 : 데이터그램 네트워크(Datagram Network)

@ Virtual Circuit(VC, 가상 회선) : 일반 망에서 특정한 dest까지의 path를 확보하여 통제. 경로에 해당하는 라우터들 모두 이 정보를 전달받아 확보한 뒤 해당 패킷에 표식을 해두고 보낸다. 구성은 아래와 같다.

(1) source와 dest 호스트 간의 경로(일련의 링크 + 라우터들)

(2) path 상 링크(링크다! 링크!)마다 부여되는 가상 번호

(3) path 상에 있는 각 라우터 forwarding table 안의 entry(VC마다 추가됨)

-> 어떤 VC에 속하는 패킷은 그 헤더 안에 가상회선 번호를 갖는다. 단, 이 VC는 각 링크에서 제각기이므로 check point 격인 라우터는(중간-_-) 전달 패킷의 VC 번호를 새것으로 교체. 이는 forwarding table 에서 얻는다.

VC number 부여가 매번 달라지는 이유!

(1) 헤더 필드의 길이가 짧게 유지 될 수 있다.

(2) 하나의 번호로 설정되었을 때 중복에 대해 다른 라우터들에게 모두 메시지 교환해야 하는 번거로움을 해결.

하지만, VC 가 현재 인터넷에 쓰이지 않게 된 단점이 있다.

(1) VC 는 라우터 내 테이블 생성을 위해 사전 약속(call setup)이 있어야 한다.

(2) 패킷 전송 후 이 테이블은 의미가 없어진다.

(3) VC 에 대해 부가적으로 상태 정보를 유지해야 한다. (이는 forwarding table 과는 별개)

@ Datagram Network

- VC 설정이 필요없고, 상태 정보도 필요없다. 목적지 주소를 포함하고 있는데, 이는 32bit 를 사용한다. 그럼 forward table 에 변화가 있는데, 패킷에 대한 lookup(검색) 동작을 살펴보자.

목적지 주소 범위가 40억인데 이를 모두 대응하지 않고, prefix(프리픽스) 대응을 적용한다.

앞만 잘라내서 갈라지는 기준을 잡고 링크 인터페이스과 사상(mapping)한다.

단, 미묘한 문제가 추가적으로 발생한다. 한 목적지 주소가 하나 이상의 엔트리에 대응되는 점이다.

-> Longest prefix matching rule(최장 프리픽스 대응 규칙)이 이 대안인데, 테이블에서 가장 긴 대응 엔트리를 찾고, 여기에 연관된 링크 인터페이스로 패킷을 보낸다.

@ Internet(datagram, 단말이 computer. 설계가 여러망 위의 여러망이 존재)

<-> ATM(VC, 일반 전화와 개념이 유사)

@ 라우터

- 패킷의 헤더 내부 아이피나 포트를 기준으로 분류하는 작업을 한다. 이 작업을 스위칭이라고 명명하며 여기서 다룰 요점은 다음과 같다. 예를 들자. 지하철 개찰구를 생각해보면, 실제 이 개찰구가 없으면(독일 등에선 수금하는 식으로 개찰구가 없다.)사람들이 몰려서 혼잡해지는 일이 훨씬 적을 것이다. 그렇다면, 이 지연을 가장 적게 만드는 방법을 찾자.)

@ 라우터 스위칭 구조

입력에 대해서는 다음과 같다.

- switching via memory : 마이크로프로세서가 패킷을 읽어 주소를 보고 판단하여 분류

- bus : 공통의 버스가 존재하여 하드웨어(logic)적으로 구현. 메모리에 올려 처리하는 시간이 줄어드므로 처리 시간이 단축되나, 한 번에 하나만 올려야 되는 제약이 발생.

- crossbar switch : 회로 구현으로 버스를 보완. 점에 해당하는 곳으로 패킷을 보내주는 로직을 만든다. 비용이 가장 많이 들지만 가장 효과적.

출력에 대해서는 별 다른 언급보다 특정 상황에 고려되는 부분이 생긴다.

- 출력 링크 속도보다 더 빨리 출력 포트에 패킷을 전달할 때 큐잉, 버퍼 관리 기능이 필요하다. 이는, 절대 온 순서대로 나가는 것이 최선의 방법이 아님을 보여주는 Head-of-the-Line(HOL)의 예를 참조하자. 곧, 일부의 순서 변경으로 더욱 효율적으로 처리되는 경우가 존재한다.

@ 네트워크 계층 protocol

- Transport 바로 아래 계층.

- IP protocol : 주소 체계 규약. 데이터그램 포맷.

- ICMP(Internet Control Message Protocol, 인터넷 제어 메시지 프로토콜) : 네트워크 상태를 알려주는 프로토콜. 네비게이션을 떠올리자. 도로가 변경되면 이는 업데이트를 통해 이 도로가 더 이상 못 가는 길임을 알려야 한다. 네트워크에서는 이 변화가 매우 크다. Timeout 이 발생한 링크는 못 가는 길로 치부하는데 이를 알리는 역할이라고 보면 된다.

- RIP : 경로 선택에 TM이는 라우팅 프로토콜.

@ IP Datagram format

- Transport 계층으로부터 캡슐화된 패킷이 내려오면 이 위에 더 크게 패키징을 한다. 물론 이 새로운 패키징엔 IP protocol 의 규약에 맞는 헤더 등이 포함되게 된다. 4바이트씩 5줄 가량. 20바이트인데 Transport 계층에서 20바이트 가량의 헤더를 사용하면 40바이트로 약 1400바이트로 나가는 이더넷의 최종패킷에서 이 헤더가 차지하는 비율은 약 3% 가량으로, 이 정도의 오버헤드는 존재해도 무방하다 여기자.

TTL : 패킷이 목적지를 못 찾고 뺑뺑이 돌 수도 있다. 여기에 시한폭탄을 달아 시한부 인생을 선고하는 작업.

@ IP 단편화와 재결합(Fragmentation, Reassembly)

- path 에 따라 진행 도중 어떤 프로토콜은 큰 패킷을 다룰 수 있는 반면, 다른 프로토콜은 작은 패킷만을 다룰 수 있다. MTU(Maximum Transmission Unit)는 링크 계층 패킷이 전달할 수 있는 최대 양인데, 전달되는 기점(호스트, 라우터)의 Network 계층의 IP는 이를 미리 탐지해서 패킷을 단편화하여 보낸다. 그럼, 다음 기점에서는 이를 종합하여 다시 판단 후 재전송하는데, 이 단편화에 대한 정보는 다음과 같이 구분하여 받아낸다.

 패킷 내 아이디를 단편화시킨 패킷마다 동일하게 특정값으로 부여한다. fragflag 가 1이면 추가로 더 있다는 의미로 사용한다. (곧, 0일 때는 마지막 단편이라는 의미를 갖고, 곧 이 플래그를 쭉 나열하면 111110, 1110... 식이 될 것이다.) 오프셋은 바이트 단위를 8로 나눈 값을 갖는다. 이 조각 패킷은 원본에서의 시작지점을 이 오프셋을 통하여 파악한다.

@ IP Addressing

- 인터페이스(여기서의 인터페이스는 네트워크가 가능한 단말기기를 의미한다. 컴퓨터 PC에 매겨지는 게 아닌, 랜카드에 매겨지는 개념. 곧, 넷북만 봐도 하나의 단말이지만, 무선랜과 유선랜이 존재함으로써 두 개 이상의 아이피를 가질 수 있다. 이 개념은 라우터에는 특히 여러개의 아이피를 지닐 수 있음을 상기시켜준다.)의 IP 주소는 연결된 Subnet 이 결정!

- Subnet은 호스트간 인터페이스들과 라우터 인터페이스로 연결된 네트워크는 서브넷을 구성한다고 말한다.

- /24 : Subnet Mask. 211.1.1.2, 211.1.1.4 는 동일한 서브넷이라고 할 수 있는데, 이 때 Subnet Mask는 211.1.1.0/24 로 정의하고, ‘/24’가 Subnet Mask이다. 단, 이 서브넷은 호스트에만 한정되는 개념이 아니다. 라우터 간 연결에도 서브넷이 존재한다.

@ CIDR(사이다, Classless Interdomain Routing)

- 위에 Subnet Mask 라고 언급한 부분이 바로 CIDR 이다. a.b.c.d/x 의 형식에서 x 는 서브넷의 길이이자 MSB이다. 이를 해당 주소의 prefix라 부르며 32-x 는 해당 네트워크의 인터페이스들이 각기 구분할 수 있는 값이라고 볼 수 있다. 물론, 이 값은 한 번으로 한정되는 것이 아니라, 나머지 32-x 의 값에서 다시 서브넷을 구성할 수도 있다. (물론 이 값을 다 쓸 수는 없다. 브로드캐스트, 디폴트로 쓰이는 주소들이 있어서 2^(32-x) 중 일부만 사용이 가능하다.) 이전엔 바이트 단위로 끊어 분류했던 클래스 주소체계였으나 기관의 수가 급속히 늘어나 지원해야 하는 양의 급증에 따라 생긴 대안이다.

- 주소 블록을 획득하는 조직 내의 서브 조직들은 이후 ISP 업체를 바꿔도 longest prefix matching rule로 구분되어 받아낼 수 있다.

@ DHCP(Dynamic Host Configuration Protocol) - Plug-and-Play protocol

- 랜 케이블을 꽂을 때마다 사용자가 IP와 관련된 설정을 수동으로 잡아주면 불편할 것이다. 자동으로 아이피 할당 및 네트워크 세팅을 해주는데 이 원리는 호스트가 인터넷에 연결하기 위해 요청하면 서버가 응답으로 IP를 할당하는 기술.

- 시나리오를 그려보면, 클라이언트가 도착했다. 이 클라이언트는 현재 아이피를 모르므로 본 클라이언트 ip 를 0.0.0.0 으로 하고 목적지는 255.255.255.255 로 DHCPDISCOVER (DHCP 발견 메시지), ID 를 임의로 결정하여 보낸다. 그럼 이 메시지는 DHCP 서버에게도 가는데 서버는 yiaddrr 에 할당할 주소를 기입하고 dest 는 역시 브로드캐스트 255.255.255.255 로 발송. offer 메시지이며 받은 클라이언트는 역시 브로드캐스트로 request하게 되며 서버는 ack.

@ ICANN(Internet Corporation for Assigned Names and Numbers)

- DNS 관리, 도메인 이름 등록, 주소 할당 등을 담당하는 국제 기구

@ NAT(Network Address Translation)

- 공유기의 원리를 이해하는 것과 연관되는 부분으로, 공유기 밖에 하나의 아이피만 존재한다. 매달린 단말기가 여러 개고, 공유기 내부에서 스스로 작은 소규모 네트워크를 정의한다.(ex : 인트라넷) 이 때문에 들어오는 주소와 관련하여 NAT table 이 별도로 정의되어야 하며, 이에 대한 시나리오를 하나 보도록 하자.

- 공유기 내부의(이해를 위해 공유기라 했지만 실제 라우터에도 해당하는 일이다.) 단말이 외부로 보내려는 패킷에 대해 헤더를 기입하고 패킷을 발송했다. 이 dest 는 수정될 이유가 없지만, source 는 자체적으로 정의한 내부 체계의 주소이므로 맞을리 없다. 곧, 공유기에선 이 source를 공유기가 물고 있는 실제 외부에서도 공용되는 IP로 바꾸어 보낸다. 이 때 NAT table 에 이 데이터가 기록되고, 수신 때는 NAT table 을 참조하여 공유기 내부의 단말로 보낼 수 있게 된다.

- 단, 공유기 내부의 단말로 외부 단말이 접속을 하려는 때가 있다.(대표적으로 p2p) 이 때는, 해결책이 세 가지 존재.

(1) 미리 내부의 단말에 대해 포트를 각기 부여해서 구분하는 방법이 있다.

(2) 이 값을 미리 부여하지 않고 프로그램 실행과 함께 할당하는 방식인 동적으로 운영하는 방식이 있다.

(3) 스카이프 방식. 공유기 밖에 있는 중간보스 피어(Leader)를 지정하고 이용하는 방법.

@ ICMP(Internet Control Message Protocol)

- 네트워크의 상태가 어떤지 그 정보에 대해 주고받는 프로토콜.

- Network 층에 있으며 곧, IP보다 상위 계층이다. IP 패킷을 이용하여 이를 수행한다.

- 예를 들어 학교에서 아이피가 겹칠 때, 이게 단말의 문제인지, 실제 다른 사람과 겹친건지 판단하는 방법은 ping 메시지를 보내보는 것으로 알 수 있다. (응답이 온다면 누군가 실제 쓰고 있다는 결론) Traceroute 또한 이 ICMP를 이용하여 알 수 있다.

@ Traceroute

- UDP를 이용하여 처음에 TTL을 1로 설정하여 전송하게 된다. 첫 라우터를 만나게 되었을 때 이 TTL은 0이 되는데, 해당 라우터는 패킷이 더 이상 앞으로 나갈 수 없다는 메시지를 송신하는데 이 메시지에는 해당 라우터의 주소 등 정보가 포함되어 있으므로 파악할 수 있다. 그리고 뒤이어 TTL을 2로 설정하여 보내는 반복작업이며 패킷의 실종상황을 고려하여 하나의 TTL에 대해 3개씩 송신해본다. 발송은 쓰이지 않는 포트를 설정해서 보내는데, 최종 목적지에 도착했을 때는 쓰이지 않는 포트이므로 응답 메시지는 여지껏 왔던 메시지와는 다를 것이다. 그로 인해 판단하여 결정.

@ IPv6

- 아무리 공유기를 써도 IP 자원이 고갈될 상황에 놓이게 되자 등장한 대안.

- 중요한 변화는 다음과 같다.

(1) 확장된 주소 : 32bit 주소가 128bit.

(2) 헤더 길이 40byte로 고정.

(3) 단편화/재결합을 제거 : 송신했을 때 해당 라우터에서 소화 못할 사이즈일 때 ICMP 메시지가 송신되고 송신측은 IP Datagram 크기를 줄여서 다시 송신한다.(이전 것은 폐기) 단편화와 재결합 작업이 시간을 지연시킨다는 점에 착안하여 개선하였다. (보안문제도 포함)

(4) 헤더 체크섬 제거 : Transport 계층과 Data link 계층에서 체크섬을 시행하므로 제거해도 무방하다 판단되어 제거됨. IP 패킷의 빠른 처리가 가장 주요하게 작용하였다.

IPv6 Datagram format 은 버전(6), 트래픽 클래스(가중치), 흐름 라벨, 페이로드 길이, 다음 헤더, 홉 제한(TTL), source, dest, data 로 구성되어 있다.

이로 인해 ICMPv6 로 개편되었다.

- 그렇다면 이를 변화해야 하는데, 플래그 데이를 정해서 하루 동안 모두 장비를 끄고 한꺼번에 바꾸자는 제안이 있었으나, 현실적으로 불가능하므로 조금씩 바꾸는 방안으로 현재도 진행중에 있다.

- 현재 병행되는데에 문제가 하나 발생한다. 바로 이전에 IPv4 로 구축된 시스템이 IPv6 를 인식하지 못하는데에 있다. IPv6 는 IPv4 를 고려하여 설계되었으므로 변환이 가능하지만 반대가 안 된다는데 그 문제요지가 있다. 해결방법은 터널링.

@ 터널링(Tunneling)

- IPv6 가 적용된 라우터에는 이 방식을 이용하여 전송된다. 그리고 IPv4 라우터로 가야하는 상황이 되면 이 터널링이 적용되어 IPv4 직후에 나오게 될 IPv6 라우터를 목적지로 설정하고(출발주소 또한 현재 변환작업을 적용하는 라우터의 주소로 바뀐다.) IPv4 의 데이터 필드에 이를 캡슐화하여 저장한다. 그러면 터널로 명명된 IPv4 라우터들을 지날 때는 내부에 IPv6 데이터가 있는지도 모르고 전송시키고 수신측이 된 IPv6 가 가능한 라우터에서 데이터를 참조하여 이를 다시 IPv6 로 복원시켜 최종 목적지로 송신한다.

@ Routing Algorithm

- 송신측의 디폴트 라우터(첫 번째 홉 라우터)와 수신측의 디폴트 라우터까지의 패킷 path 를 최소비용으로 찾아내는 작업.

- 라우팅 알고리즘은 크게 두 가지로 분류된다.

(1) Global : 네트워크에 대한 완벽한 전체 정보를 아는 경우.

-> LS(Link-State) Algorithm(링크 상태 알고리즘)

(2) Decentralized(분산) : 노드가 모든 네트워크 링크의 비용에 대한 완벽한 정보를 알지 못할 때.

-> DV(Distance-Vector, 거리 벡터) Algorithm

또 다른 분류로 정적, 동적 라우팅 알고리즘(네트워크 트래픽 부하, 토폴로지 변화를 고려대상으로 하는 유무로)으로 혹은 부하에 민감한, 둔감한으로 나눌 수 있다.

@ LS Algorithm

- 링크 상태 브로드캐스트 알고리즘으로 정보를 수집. 자기 라우터로 돌아오는 경우와 음수 가중치는 없다고 가정한다.

- Dijkstra's Algorithm : 이 알고리즘은 자료구조에서 배웠으므로 생략하자. 직접 해보는 것은 필수!

- 복잡도는 이다.

- 단, 이 알고리즘은 혼잡이나 지연을 기반으로 한 링크 방식의 진동 문제에 딜레마를 겪는다. 물론, 링크 비용이 트래픽에 의존하지 않게 만드는 방법이 있지만, 이 경우 본질적인 문제로부터 벗어나는 결과를 갖게 된다.

@ DV Algorithm

- 비동기적, 반복적, 자기 종료, 분산 알고리즘.

- Bellman-Ford Algorithm( 단, 1<k<n, ())을 이용.

- 재귀적인 구조로 목적지로부터 값이 되돌아오는 연산 형태를 지닌다.

- 문제가 있다. 링크 비용 변경과 링크 고장이 그 문제점인데, 시나리오를 보자. (대신 링크 비용이 감소하는 소식은 빨리 퍼진다.)

  라우팅 루프가 발생되는 경우인데, 해당 노드간 가중치의 증가 때는, 연결된 두 노드간 라우팅 루프가 일어나 왔다갔다를 반복한다. 이는 Bellman-Ford 알고리즘이 적은 값에 대해서만 업데이트를 적용하고 큰 값은 무시하기 때문에 벌어지는 일인데, 가중치 증가량이 크면 클수록 루핑 타임은 무한해진다. 무한 카운트라고 부른다.

  -> 이 문제는 포이즌 리버스로 해결한다.(poison reverse) 이 방안은 경로 설정이 된 이외의 경로를 무한대라고 다른 라우터들에게 해당 라우터(무한대로 설정할 큰 값의 가중치 간선과 연결된 라우터들)는 이를 전부 알려둔다. 그러면, 다른 곳에서의 경로상 값의 큰 변화가 일어났을 때 그 큰 값에 대해 다른 라우터들에게 알리고 무한대로 설정했던 라우터는 값을 받아 비교했을 때 적은 값이면 즉시 거리 테이블을 수정한다. 이로써 해결할 수 있으나, 일반적인 무한카운트 문제는 많은 노드를 포함한 루프에 대해 포이즌 리버스로는 감지하기가 힘들다.

@ 두 알고리즘의 비교

- 복잡도 : 링크 상태 알고리즘은 , 거리 벡터 알고리즘은 매우 천천히 수렴하고 라우팅 루프에 의한 무한카운트 문제 가능성이 있다.

- LS 는 변경에 대해 전체를 다시 업데이트해야 하고, DV는 변경된 부분에 한해 메시지 교환으로 매번 파악하는 형태. 단, DV는 메시지에 오류가 발생되었을 때 일파만파로 퍼지지만, LS는 잘못된 부분 이외에는 멀쩡.

@ 계층적 라우팅

- 실제로 두 알고리즘은 전 세계 라우터들을 대상으로는 막대한 메모리와 오버헤드를 불러온다. 또한 관리에 대한 자치적인 문제가 침해되는 일이 있다. 이 해결책으로 자치 시스템(AS : autonomous system)이 도입된다.

@ 자치 시스템(AS)

- Intra-AS Routing Protocol : AS 내부에서 동작하는 라우팅 알고리즘

- Gateway Routers : 외부 목적지 AS에 패킷을 전달하는 라우터.

- 이 자치 시스템은 문제를 단순화해서 보자는데 측면이 강하다. 예를 들어 서울에서 부산을 간다고 하자. 그러면 일단 우리는 부산까지의 상세한 루트를 고려하기보단, 밖으로 나가게 될 중요 기점을 먼저 생각하게 된다. 경부고속도로, 국도, 버스 등. 네트워크에선 각각의 이 영역이 별개의 라우팅 알고리즘을 사용해도, 이 영역은 분리되어 있고, 중간 기점은 별개로 이어주는 계층적 형태를 추구하게 된다.

- 다른 측면에서 다시 설명해보자. 전세계의 지도 형태를 아는 네비게이션이 있다고 하자. 이 네비게이션이 다뤄야 하는 데이터량은 매우 방대하다. 여기에 추가로, 네비게이션이므로 각 도로의 교통상황까지 구현해야 한다면, PC로도 힘든 수준에 이를 것이다. 하지만 이 네비게이션은 사용하는 구간이 한정적이다. (최소한 전 세계를 대상으로 해야만 할 경우는 확률적으로도 매우 희박할 것이다.) 곧, 영역별로(AS) 쪼개어 각 구획은 알아서 LS 든, DV 든 처리하도록 맡기고, 영역의 바깥을 결정해야 한다.

- 알아야 하는 기본 정보는 아래와 같다.

1. 가야할 목적지의 존재 여부를 알아야 한다.

2. 목적지의 위치를 알아야 한다. (1과 2는 일맥상통하는 부분이 있다.)

3. 이를 가려면, 해당 AS 에서 어느 게이트웨이 라우터로 가야 할지를 결정해야 한다.

여기에 발생되는 문제가 하나 있다. 목적지로 향하는 게이트웨이 라우터가 여럿이라면, 어느 쪽으로 가야 하는 게 더 빠를 것인가를 결정해야 한다. -> Hot-Potato Routing!

@ Hot-Potato Routing

- 가장 적은 비용의 게이트웨이로 해당 패킷을 빨리 내보내는 방향으로 설계된 라우팅 기법.

@ RIP(Routing Information Protocol, 라우팅 정보 프로토콜)

- DV 이용.

- Hop(홉) : 출발지 라우터에서 목적지 서브넷까지의 최단 경로를 지나는데 지나는 서브넷의 숫자.

- 최대 경로 비용은 15로 제한. RIP를 AS에서 사용하는 경우 15홉보다 작게 설정, AS 내부는 최대 25개 목적지로 제한.

- RIP 광고(Advertisement) 이용, 대략 30초마다 이웃끼리 교환

- RIP table(라우팅 테이블)을 RIP 광고 수신과 수정작업을 함께 병행한다.

- 6번의 반복 송신에 의해 판단하는데(UDP) 180초(30 x 6)동안 이웃에 내게 아무런 RIP 응답 메시지가 없다면 해당 이웃이 없다고 재정의한다. 보낼 예정이었던 패킷들의 경로를 모두 수정하고(물론 이웃한 다른 라우터들에게도 알린다.) 재정의하는 가중치는 16으로 설정. (poison reverse)

@ OSPF(Open Shortest Path First)

- LS 이용.

- 링크 상태가 변경되거나, 정기적으로(30분) Link-State 를 브로드캐스팅 한다.

- 2수준 계층화 : 지역 영역, 백본.

- AS에서 하나의 OSPF 영역만이 백본 영역으로 설정된다.

- OSPF 의 네 가지 유형은 아래와 같다.

1) 내부 라우터 : 백본이 아닌 영역에 있고 intra-AS 라우팅만 수행.

2) 영역 경계 라우터 : 외부 영역으로 패킷 라우팅을 담당. 백본에 속함.

3) 백본 라우터 : 백본 내에서 라우팅하지만 영역 경계 라우터는 아니다. 내부 라우터는 백본 라우터가 주는 영역 정보 브로드캐스팅에 의해서 다른 영역으로의 경로가 있음을 알 수 있다.

4) 경계 라우터 : 다른 AS에 속한 라우터들과 라우팅 정보를 교환. inter-AS를 위해 BGP 사용한다.

@ BGP(Border Gateway Protocol)

- 백본에 해당하는 AS의 경계 라우터가 갖는 알고리즘. 다른 AS의 라우터들과 연결하는데 이 사이의 연결은 영구적인 TCP로 설정.

- 각 AS는 스스로 인터넷에 광고를 하여 자신을 알려 BGP는 인터넷의 모든 AS가 이 서브넷에 대해 어떻게 도달하는지를 알게 해준다.

- BGP의 목적지는 호스트가 아닌 CIDR된 Prefix이다.

- Internal 과 External 로 나뉜다.

- Internal BGP : AS 내 라우터간의 BGP 세션

- External BGP : 두 AS에 걸치는 BGP 세션

- eBGP는 어떤 AS에서 게이트웨이 라우터가 프리픽스를 배우는 eBGP를 수신하면, 게이트웨이 라우터는 자신의 iBGP 세션을 사용하여 그 프리픽스를 자신의 AS 내부의 다른 모든 라우터에게 분배한다. eBGP 에서 보내야 될 대상 정보 데이터는 전파 받은 또 다른 AS 에 대한 데이터를 포함한다. 곧, 인접하지 않은 AS를 파악이 가능.

- ASN : AS 식별번호

- AS-Path : AS가 굉장히 많이 때문에 여러 AS를 지나게 되는데 사이클이 생기는 등의 비효율적인 경로를 만들 가능성이 있다. 이를 별도로 구분하여 효율성 있게 처리하는 알고리즘.

- Next-Hop : 최단 거리라는 보장은 그 어디에도 없으나, 다른 AS의 서브넷으로 데이터를 보내려면 보내는 라우터가 포함된 AS에서 어느 라우터쪽으로 우선적으로 향해야 하는지 결정하는 것.

@ BGP 의 경로 설정

- 결정된 경로에 대해 쓸 것인가, 말 것인가를 판단하는 시스템

- 먼저 BGP 라우팅 정책을 예를 들어보자. 단순한 BGP 시나리오에서 계산된 가중치 값이 더 적더라도, 수신(소비자) 네트워크를 경유해서 가는 경우는 무조건 폐기한다. 또한 수신 네트워크에 다이렉트로 연결되지 않은 공급자 네트워크를 거치는 경우, 해당 공급자가 도울 이유가 전혀 없으므로 이 경우도 폐기 사항에 포함된다.

- 경로의 선택 기준은 4가지로 말할 수 있다.

1. 정책에 따른 선호하던 루트가 선택된다. 라우터에겐 학습 능력이 있으므로 지역선호는 이를 따른다.

2. 같은 지역 선호 값을 지닌 나머지 루트로부터 최단 AS-Path 가 선택된다.

3. Intra AS Algorithm 에 의해 결정된 Path에서 가장 가까운 Next-Hop Router 를 갖는 루트를 찾는다.(비용이 낮은) 이게 Hot-Potato routing.

4. 식별자를 이용하여 루트를 선택한다.

@ Broadcast Routing

- 브로드캐스트는 불특정 다수에게 모두 보내는 것이고 멀티캐스트는 특정 다수에게 보낼 때 해당되는 것이다.(소속집단에게 보낼 때가 그 예)

- 브로드캐스트 폭풍 : 너무나 많은 브로드캐스트 패킷의 증가 때문에 네트워크에 과도한 트래픽이 오는 경우를 의미한다.

- 브로드캐스트 전송에 대해 몇 가지 살펴보자.

1. 근원지 노드에서 복사하여 전송 : 출발지에서 패킷을 복사하여 각기 발송할 때 한 경유지에서 동일 패킷 여럿이 지나가 불필요한 트래픽(자원의 낭비)을 일으키게 된다.

2. 비제어 플러딩 : 노드가 브로드캐스트 패킷을 수신하면 모든 이웃들로 복사하여 발송한다. 하지만 사이클이 존재한다면 이야기가 복잡하게 구성된다.

3. 제어 플러딩 : 받아서 브로드캐스트 적용한 패킷에 대해서는 다시 받았을 때 브로드캐스트 하지 않는다.

   이 제어 플러딩에 대해서도 두 가지 세부적으로 나눌 수 있다.

   1) 순서번호 제어 플러딩 : 패킷에 대해 일련번호를 매겨 보내는 방법이다. 수신 라우터는 이를 검사하여 목록에 없다면 브로드캐스트하고 있다면 폐기하는 방식. 하지만 이 일련번호조차도 양이 많아지면 중복될 가능성이 있다.

   2) 역경로 전달(Reverse Path Forwarding, RPF) : 단순한 아이디어로 최소비용 경로의 간선은 제외하고 나머지에 대해서 다이렉트로 온 라우터의 테이블을 역참조하여 보내지 않는 방법이다.

- 제어 플러딩의 두 가지 방법 모두 브로드캐스트 폭풍을 피할 수는 있지만, 중복 전송은 피할 수 없다.

- Spanning tree 를 생성한다. 이는, 모든 브로드캐스트 노드는 단 한 개의 복사본만을 수신한다는 특징을 갖는다. 하지만 Prim, 크루스컬 알고리즘과 같이 적용하지 못하고 병렬로 적용, Center 노드를 기점으로 퍼져나가는 형태.

@ Multicast Routing

- 유료방송을 생각해보자. 곧, 브로드캐스트이지만 특정 다수에게만 보내야 하는 경우가 이 경우이다. 이 경우 이 멀티캐스트를 위해 대상 라우터만 고른다고 하면, 맵이 끊어질 수 있다. 곧 참여대상에서 제외된 서브넷들만 지닌 라우터 또한 경로상에 있다면 참여해야 한다.

- 이런 멀티캐스트 그룹은 인터넷 그룹 관리 프로토콜(IGMP)에 의해 관리된다.

- 경로 생성을 다익스트라 알고리즘을 이용하여 해당 유니캐스트(센터)에 대해 모두를 구하는데, 이 때 해당하지 않는 라우터 또한 함께 계산하도록 한다. 단, 이 트리 생성은 보내려는 대상 라우터에서 올라온 정보인데, 유향 그래프이기 때문에 그 역 또한 같은 가중치를 갖는다는 보장이 전혀 없으며, 또한 계산할 때는 포함시켰지만 이 중 빠져도 무방한 노드들이 존재한다. -> 이 문제는 리프노드부터 다시 질문해 올라가는 방식이다. 해당 리프노드 아래에 멀티캐스트에 참여하는 노드가 있는지 질의하고 없다면 삭제, 있다면 pass. 작업은 상위 노드를 향해 질의를 반복하는 작업이고, 이 방법을 Reverse Path Forward 라고 한다.

- Steiner Tree : 이 트리는 문제가 있다. 만약, 세 정점 간을 잇는 세 개의 간선이 모두 2의 가중치를 갖는다고 할 때, 이에 새로운 정점을 추가하여 더 최단경로를 생성할 수 있냐는 질문에 대해서 무게 중심을 잡아 설정해주면 된다. . 굉장히 복잡한 문제이므로 실제로 잘 안 쓰인다. 멀티캐스트 특성상 삽입삭제가 잦은데 이 부분이 어렵다.

- Center-based tree : 대상되는 라우터만 포함시켜 지정된 센터(기준점)로 가는 최단 경로를 구하고, 이를 추가하여 만들어주는 방법.

<< CHAPTER 5 >>

MAC address 는 네트워크 단말장치에 부여된 고정된 값으로, 이 값은 IP와는 전혀 별개의 값이며 또한 MAC에서 IP를 참조하진 못한다. (상위 계층)

@ Link-Layer Service

- 흐름제어(들어오는 signal 에 동일 클럭을 적용시켜 많이 들어올 때를 파악), 오류 검출 및 교정, 반이중 전송, 전이중 전송.

@ NIC(Network Interface Card) : 랜카드

@ Parity Checking

- Single bit Parity : 한 비트를 이용하여 홀짝 구분

- Two Dimensional Bit Parity : 행렬 형태를 이용하여 둘 이상을 구분. 하지만 역시 4개는 구분하지 못한다.

@ Checksum : 다 합산한 뒤 그 합을 통해 파악

@ CRC(Cyclic Redundancy Check, 순환중복검사)

- 메인 아이디어는 우리가 어떤 정수 데이터를 보낸다고 가정하자. 송신측과 수신측은 미리 특정한 수를 정하고 입력 받은 수에 대해 나눈 나머지를 둘이 서로 비교한다.

- d 비트로 이루어진 데이터 D를 송신 노드가 수신 노드로 전송할 때, 송신자와 수신자는 G로 표기되는 생성자(Generator)로 알려진 r+1 비트 패턴에 대해서 합의한다. 이 때, 반드시 G의 MSB는 1이어야 하며, 주어진 데이터 D에 대해 송신자는 r개의 추가 비트 R을 선택해서 D의 뒤에 덧붙이며 d+r 패턴은 나누기를 적용하였을 때 정확히 나머지가 R 로 나와야 한다. 여기서의 R은 CRC 비트라고 하며, 다음은 그 예시이다.

D=101110, d=6, G=1001, r=3 일 때.

곧, CRC bit 는 011, 실제 전송되는 9비트는 101110011이다. 이 사이의 연산은 모두 XOR로 진행되는 점과 마지막 CRC bit 는 일반 나머지와 같이 수를 끌어오는 형태가 아님을 유의하자.

@ Multiple Access Protocol

- 공유된 매질을 여러 참여자가 동시에 쓰는 방법이다. 한 순간에는 한 명만 통신이 가능하며 간섭 또한 존재하므로 이를 해결하는 세 가지 방안이 있을 수 있다.

@ TDM, FDM 으로 채널을 분할

- 사용하지 않는 비가용 상황에서도 시간이 할당되는 문제와 주파수 대역 또한 보내는

패킷이 단 하나여도 대역폭이 한정된다.

@ Random Access

- TDM, FDM 모두 감독하는 단말이 존재해야 하는 문제가 있다. 호스트가 늘어나면 재설정 해야 한다는 불편 또한 존재한다.

- 또한 충돌이라는 사건이 발생할 수 있다. 간섭과 상쇄라는 개념과 연관되는데, 이를 보내는 신호와 해당 라인에서 흐르고 있는 신호를 비교함으로써 충돌여부를 판정할 수 있을 때,  ALOHA, CSMA, CSMA/CD 가 있다.

@ Slotted ALOHA

- 모든 패킷은 동일한 크기를 갖는다.

- 모두 동일한 시간대역을 공유한다. (시간 분할이 모두 동일하다.)

- 충돌 발생 시 이를 즉시 감지할 수 있다.

- 충돌이 발생했음을 감지했을 때는 두 발신 호스트가 동시에 패킷을 송신했을 때인데, 두 호스트가 바로 다음 시간대역에 발신하게 되면 다시 충돌이 발생한다. 곧, 두 호스트는 각각 임의의 난수 알고리즘을 통해 재발신 순간을 결정하게 된다. 이로써 충돌의 확률을 낮추는 방법이다.

- 하지만, 이 경우 노는 망이 생길 수 있고, 망이 서로 계속 겹쳐 금방 보낼 수 있는 작업이 많이 지연될 수 있다. 또한 모든 단말의 동기화가 이뤄져야 한다.

1. 문제 개요

- pi 의 값을 유도하여 증명한다.

- 이 문제의 식을 유도하는 과정을 Python 언어로 구현한다.

- Python 은 2.6.2 버전으로 적용되었다.

2. 문제 분석(알고리즘 및 해결방안)

①  확률적 개념으로 접근하는 방법도 있으나, pi의 값에 대해 증명하는 것이므로 확률개념을 제외하고 구하도록 한다.

②  삼각함수 sin 을 이용하여 원에 내접하는 다각형을 n-각형으로 정의한다.

③  원의 반지름을 r 로 정의, r 값은 n각형의 중점과도 일치하며, 중점으로부터 n 각형의 꼭지점까지의 거리와도 일치한다.

④  반지름 r 인 원에 내접하는 사각형(n=4)의 경우, 중점으로부터 대각선으로 네 경우의 r 거리가 나오며, 이는 이등변 삼각형이 4개 생긴 것으로도 볼 수 있다.

⑤  이 이등변 삼각형이 중점부에 이르는 각도를 정확히 2분할 한 수직하는 선을 긋게 되면 네 개의 이등변 삼각형들은 여덟 개의 직각 삼각형으로 볼 수 있다.

⑥  빗변이 r, 중심각을 알면, sin 으로 접근이 가능하다. 이는 사각형뿐만이 아닌, 모든 n-각형에 적용이 가능하며, 이를 식으로 유도하면 다음과 같다.

2n * r * sin(360 / 2n) = 2(pi)r .  이 식은 아래와 같이 정리 가능하다.

n * sin(360 / 2n) = pi

⑦  프로그래밍화 할 부분은 아래 수식의 n 을 증가시켜 pi값이 얼마에 수렴하는 것인가하는 부분이다. 이 코드 부분은 충분히 설계할 가벼운 내용이니 생략한다.

1. 문제 개요

- (생일 문제) n 명의 사람들로 구성되어 있는 모임에서 적어도 두 사람의 생일이 같을 확률은 얼마인지 구한다. (윤년은 고려하지 않으며 모임 구성원들의 생일에 대한 모든 가능한 조합들은 가능성이 동일한 것으로 생각한다.)

- 이 문제의 식을 유도하는 과정을 Python 언어로 구현한다.

- Python 은 2.6.2 버전으로 적용되었다.

2. 문제 분석(알고리즘 및 해결방안)

①  여사건의 개념으로 접근한다.

②  전체 n 명의 사람들로 구성되어 있는 모임에서의 모든 생일의 수가 전체가 되고, 문제에서 주어진 조건의 여집합에 해당하는 것은 n 명의 사람들 모두가 생일이 일치하지 않을 경우이다. 곧, 전자가 분모에, 후자가 분자에 해당한다.

③  단, 주의해야 할 점은 서로 다른 생일들을 선택할 때 순서의 의미가 있다는 점이다. 전체의 경우가 총 선택 수에 대해 중복을 허용하는 순열이므로 여사건에 해당하는 부분에 순서를 배치해야 함을 누락해선 안 된다.

④  유도한 식을 프로그래밍 화하여 답을 구한다.

3. 결과(소스 및 스크린샷)

풀이는 다음과 같다.

①  전체 사건은 중복을 허용한 365일 중 n만큼을 골라야 한다. => 365^n

②  여사건은 총 1년 365일에서 중복되지 않는 한도로 n만큼을 골라야 하므로(곧, n 은 반드시 365 이하여야한다.) 365Cn 지만, 전체 사건에서 n만큼 선택에 있어 순서가 의미가 있으므로 여사건 또한 순서 의미를 지니게 된다. 곧, 일자로 나열하는 경우의 수가 포함되어야 한다. => 365Cn*n!

③  최종 구하고자 하는 사건으로 정리하면, => 1 - (365Cn*n!)/365^n 가 구하고자 하는 사건의 확률이다.

④  코딩

def cbn(x,y):

 result = 1

 underresult = fact(y)

 while y > 0 :

  result = result * x

  y = y - 1

  x = x - 1

 return (result/underresult)

def fact(n):

 if n <= 1:

  return 1

 else:

  return n * fact(n-1)

def calcp(n):

 undernumber = 365 ** n

 undernumber = float(undernumber) / fact(n)

 return (1-(cbn(365,n)/undernumber))

## confirm the problem

a = 0

i = 1

while i < 100:

 a = calcp(i)

 print a, i

 i = i + 1

4. 고찰

①  실행화면 결과는 한 행마다 앞쪽은 해당 확률, 뒤쪽은 n 의 값이다. n 의 값이 증가할수록 확률은 급격히 증가하는 모습을 보인다. 365에 못 미치는 60 정도만 와도 이미 99/100 의 확률을 보임을 알 수 있다. 확률이 반이 되는 위치는 n = 23 일 때이며, 의미하는 바는 23명 이상이 있다면, 적어도 두 명 이상은 생일이 같은 경우가 50% 이상임을 말한다.

②  교수님께서 지적하신 부분의 실수를 저지르고 말았다. 결과가 계속 0 으로 나오기에 정수/정수의 결과를 떠올리기 전에 함수간 값 전달에 문제가 있었던 게 아닐까 한참 고민한 점이 많은 시간을 앗아갔다. 그 외에 제곱 연산에 ‘^’ 을 사용, 덧셈 값이 나와 오류를 겪기도 했다. 팩토리얼 연산은 수업 시간 때 배웠었던 재귀적 호출법을 이용하여 구현하였고, 나머진 미리 언급된 알고리즘에 따라 구현되었다.

1. 문제 개요

- Python과 Tkinter를 이용한 프로그래밍으로, 비트맵 그래픽의 효과를 구현한다.

- http://www.python.org 에서 Python 프로그램을 다운로드 할 수 있다.

- http://www.activestate.com/activetcl/ 의 다운로드 프로그램 중 ActivePython을

  다운로드 한다.

- Python 은 3.0 버전이 있으나 일부 기능의 변화와(print "Hello" 의 문법은 오류가

  발생하고 print("Hello") 로 구현해주어야 한다.) ActivePython과의 원활한 동작을 위

  해 2.6.2 버전으로 통일하였다.

2. 문제 분석(알고리즘 및 해결방안)

①  채점하지 않는 과제 1은 캔버스의 크기를 지정하여 생성한 뒤 반복문을 통해

그린 캔버스 내부를 검은 사각형과 하얀 사각형들로 번갈아 표현하는 것이 관건이다.

물론, 이는 전체 크기인 800 x 600 size 와 10 x 10 인 사각형들의 구성 관계를 연상해보면 일련의 계산을 통해 이중 반복문으로 해결할 수 있다.

②  2 x 2 사각형들의 모임으로 베지어 곡선을 표현하는데, 알고리즘은 다음과 같다.

     1) 사다리꼴 형태로 보았을 때 좌측부터 p1,2,3,4 로 정의한다.

     2) p1과 p2의 중점, p2와 p3의 중점, p3와 p4의 중점을 구한다. 이를 p12, p23,

     p34 라 정의하자.

     3) p12와 p23의 중점, p23과 p34의 중점을 각각 p1223, p2334로 정의하자.

     4) p1223과 p2334의 중점을 구한다. 이 때 중점을 중심으로 내부에도 또 다른

     사다리꼴 형상의 구조가 만들어지는데 이에 대해서도 각각 재귀적으로 중점을 구할

     수 있다.

     5) 최종적으로 구한 점들을 모두 찍어보면 그 점들을 이었을 때 베지어 곡선이라

     할 수 있으며, 이 장에선 직선관련 함수의 내용보다 사각형을 직관적으로 볼 수 있

     게 2 x 2 size 로 정의된 것으로 보아 선이 아닌 점들로 표현하도록 하자.

③  과제 2는 256 x 256 크기의 캔버스에 2 x 2 size 의 사각형들로 RGB 그러데이션을 보이는 것이다. 채점하지 않는 과제 1 과 마찬가지로 계산을 통하여 이중 반복문 구조로 해결할 수 있으나, 배열을 사용하는 조건이 있다. 하지만 C 언어와는 달리 python은 기존의 생성한 배열에 추가적으로 원소들을 더해줄 수 있음을 이용하여, 배열을 추가하여 사용하도록 한다.

④  과제 3은 비트맵 이미지의 블러링 필터를 적용하는 문제로, 각 픽셀별로 접근하여 해당 값을 계산, 적용을 반복하여야 한다. 문제 조건에서 가장자리의 경우는 무시하여도 된다는 조건이 있으므로 가장 외곽에 위치한 픽셀들은 이 대상에서 제외하여도 무방하며(단, 외곽 바로 안쪽에 위치한 픽셀들은 이를 참조하여야 한단 것은 누락해선 안 된다.)내부 픽셀들에 차례로 접근하여 계산하는 과정을 거치도록 한다.

⑤  과제 4는 45도의 회전을 적용하는 것으로, PIL 라이브러리에서의 rotate 를 직접 구현하는 문제다. 수업시간 때의 python 과 과제를 위한 예제 pdf 파일의 내용만으로는 삼각함수를 표현하는데 무리가 있다고 판단, math 함수를 사용하였으며, 이를 이용한 구현은 bitmap 수업 시간 때의 이론을 적용하여 표현하도록 한다.

3. 결과(소스 및 스크린샷)

<<채점하지 않는 과제 1>> ($ 표시 부분은 한 줄이라는 의미로 정의하자.)

from Tkinter import *       #Tkinter 라이브러리를 import

root = Tk()                  #root 로 지정

c = Canvas(root, height=600, width=800)     #c에 높이 600, 너비 800 Canvas 지정

c.pack()                                     #지정한 Canvas를 화면에 출력

for i in range(1,61):     #이중 반복문. 바깥쪽을 세로로 할 예정이므로 1~60까지

     for j in range(1,81): #안쪽은 너비에 맞춰 1~80까지

         if(i/2 != (i+1)/2):       #홀수줄이고

             if(j/2 != (j+1)/2):   #홀수칸이라면

                 c.create_rectangle(j*10-9,i*10-9,j*10,i*10, width=0, fill=$

"#%02x%02x%02x"%(255,255,255))  #하얀색의 네모를 그림

             else:               #홀수줄이지만 짝수칸이라면

                 c.create_rectangle(j*10-9,i*10-9,j*10,i*10, width=0, fill=$

"#%02x%02x%02x"%(0,0,0))     #검은색의 네모를 그림

         else:                   #짝수줄이고,

             if(j/2 != (j+1)/2):   #홀수칸이라면

                 c.create_rectangle(j*10-9,i*10-9,j*10,i*10, width=0, fill=$

"#%02x%02x%02x"%(0,0,0))     #검은색의 네모를 그림

             else:               #짝수줄, 동시에 짝수칸이라면

                 c.create_rectangle(j*10-9,i*10-9,j*10,i*10, width=0, fill=$

"#%02x%02x%02x"%(255,255,255))  #하얀색의 네모 그림

 - 구조는 위와 같다. 2중 반복문 내부에 2중의 조건문이 삽입된 형태로, 반복문은

총 800 x 600 의 캔버스에 채우기 위해, 조건문은 각 라인별로 검정색(모두 0)과

하얀색의(모두 255) 출력이 서로 어긋나게 하기 위함이다. 조건문은 홀수인지 짝수인지를 묻는 구문으로 mod 연산 없이 수행했다. (덧붙여서, 10inch 세로 길이 600 으로 제한된 넷북 사양에서 편집한 화면으로 아랫부분이 일정량 편집되었다.)

<<채점하는 과제 1>> ($ 표시 부분은 한 줄이라는 의미로 정의하자.)

from Tkinter import *

root = Tk()

c = Canvas(root, height=600, width=800)

c.pack()

def midp((x1, y1), (x2, y2)):     #두 개의 좌표로부터 중점을 구하는 정의 함수

 return ((x1+x2)/2, (y1+y2)/2)     #중점 좌표를 되돌린다

def beziercurves(p1, p2, p3, p4):   #베지어 곡선을 그리는 함수

 if ((p4[0]-p1[0]) > 3) :             #끝점과 시작점 사이의 x 축 거리가 4 이상일 때

     leftp1 = p1                     #왼쪽 첫 번째 점에 첫 점을 저장

     rightp4 = p4                   #오른쪽 끝 점에 마지막 점을 저장

     leftp2 = midp(p1, p2)  #왼쪽 두 번째 점은 첫 점과 두 번째 점 사이의 중점을

     rightp3 = midp(p3, p4) #오른쪽 세 번째 점은 세 번째 점과 네 번째 사이의 중점을

     temp = midp(p2, p3)   #임시로 두 번째 점과 세 번째 점 사이의 중점을 저장

     leftp3 = midp(leftp2, temp)     #왼쪽 세 번째에 임시점과 두 번째 점간의 중점을

     rightp2 = midp(rightp3, temp) #오른쪽 두 번째에 임시점과 오른쪽 세 번째점간의 중점을

     leftp4 = midp(leftp3, rightp2) #왼쪽 네 번째에 왼쪽 세 번째와 오른쪽 두 번째 중점을

     rightp1 = leftp4         #최종적으로 오른쪽 첫 번째 점을 왼쪽 끝 점과 같게함

     beziercurves(leftp1, leftp2, leftp3, leftp4) #왼쪽 점들을 인수로 베지어 함수 호출

     c.create_rectangle(rightp1[0], rightp1[1], rightp1[0]+2, rightp1[1]+2, $

width=0, fill="black")     #2 x 2 사이즈의 사각형을 위 점들을 기준으로 그림

     beziercurves(rightp1, rightp2, rightp3, rightp4)#오른쪽 점들을 인수로 베지어 호출

beziercurves((20,500),(360,100),(580,100),(690,500)) #베지어 함수 초기 호출값

(단위를 더 좁히면 자연스러운 베지어 곡선이 나타난다.)

- 2번에 명시한 알고리즘을 설계한 것이다. 정의한 midp 함수는 중점을 구하는 사용자정의 함수이며 베지어 곡선의 점을 찍는 함수는 재귀적 용법으로 호출된다. 이 재귀적 호출은 첫 점과 사다리꼴형의 반대쪽 끝점간의 x 축 거리가 4 이상일 때까지 시행하며 제한 조건에 도달했을 때 오른쪽 기준의 점들부터 찍는다. 차이에 관련해서 사실상 오른쪽 기준의 점이든 왼쪽 기준의 점이든 찍히는 모양은 같은데 이는 바로 아랫줄의 right point 들을 인수로 다시 재귀적 호출을 하기 때문이다. 이 구조로 인해 베지어 곡선이 완성되며 순서를 바꾸어도 같은 결과를 출력해낸다. 단, 두 번의 재귀호출을 한 번으로 줄이면 엉성하게 지극히 셀 수 있는 개수로 왼쪽에 점이 찍힘을 볼 수 있다.(첫 재귀 호출을 오른쪽으로 바꾸면 오른쪽에만 찍힌다.)

<<채점하는 과제 2>> ($ 표시 부분은 한 줄이라는 의미로 정의하자.)

from Tkinter import *

root = Tk()

c = Canvas(root, height=256, width=256)

c.pack()

rgbarray = [[0,0]]  #list 를 선언하고 [0,0]을 초기 값으로 지정

for i in range(128):

     for j in range(128):     #이중 반복문

         if j!=0 or i!=0:      #위의 초기 지정 값을 제외하고 반복

             rgbarray.append([2*i,2*j])   #list 에 배열을 변화하여 추가

         c.create_rectangle(i*2, j*2, i*2+2, j*2+2, width=0, fill= $

"#%02x%02x%02x"%(rgbarray[(128*i)+j][0],rgbarray[(128*i)+j][1],128))

#그리고 배열의 값에 맞춰 RGB 조절 후 사각형을 그림

- 채점하지 않는 과제 1 과 마찬가지로 이중 반복문 구조를 통해 canvas 전체에 표현한 결과다. 세로로 한 줄씩 표현되어 다음으로 이동하는 구조로 처음이 R,G,B 순으로

0,0,128 임을 참조하면, 파란색으로 표현되고 그 라인 가장 아래쪽은 0, 254, 128 임을 생각한다면 올바르게 표현되었다. 2차원 배열과 같은 형태이나 128 * 128 개의 좌표쌍 배열들의 집합으로 구성되어 접근방법이 외부 반복문의 변수에 128 을 곱하여 접근한다.

<<채점하는 과제 3>> ($ 표시 부분은 한 줄이라는 의미로 정의하자.)

from Tkinter import *

root = Tk()

c = Canvas(root, height=256, width=256)

c.pack()

rgbarray = [[0,0]]

for i in range(128):

     for j in range(128):

         if j!=0 or i!=0:

             rgbarray.append([2*i,2*j])           #위 내용과 동일

     

def filtering(n):     #블러링을 적용할 필터링이란 이름의 사용자 정의 함수

 temp1 = 0         #임시로 누적 합산 및 배정 용도로 쓰일 변수 선언 및 초기화

 temp2 = 0

 for x in range(-1,2):         #9칸이므로 -1 ~ 1 까지

     for y in range(-1,2):     #역시 -1 ~ 1 까지의 범위

         temp1 = temp1 + rgbarray[n+(128*x)+y][0] #R값들을 누적

         temp2 = temp2 + rgbarray[n+(128*x)+y][1] #G값들을 누적

 temp1 = temp1/9   #9로 나눔(평균을 구함)

 temp2 = temp2/9

 for x in range(-1,2):         #위에서 계산했었던 해당 9 칸에

     for y in range(-1,2):

         rgbarray[n+(128*x)+y][0] = temp1  #R 평균값으로 적용

         rgbarray[n+(128*x)+y][1] = temp2  #G 평균값으로 적용

     

for i in range(1,127):

     for j in range(1,127):   #모서리는 제외하므로 1~126까지의 이중 반복문

         filtering(128*i+j)     #필터링 함수를 호출

for i in range(128):

     for j in range(128):

         c.create_rectangle(i*2, j*2, i*2+2, j*2+2, width=0, fill= $

"#%02x%02x%02x"%(rgbarray[(128*i)+j][0],rgbarray[(128*i)+j][1],128))

#필터링 적용 후 해당 값들을 사각형으로 출력

- 각 RGB 성분 중 RG 의 값을 성분으로 갖는 배열들을 추가하여 만든 뒤 순차적으로 접근하여 해당 성분으로 사각형을 만드는 과정을 거치는 것은 위의 문제와 동일하고 모서리는 제외하므로 1~126 의 범위로 접근하여 사각형에 대한 색을 블러링 한다. 순차적으로 접근하는데 원본 그림이 이미 순차적인 RG 성분의 변화에 따른 그림인 탓에 결과화면상으로는 확연한 차이를 알기 힘들다. 이는 느낀점 항목에서 다른 소스에 적용하여 효과를 확인하도록 한다.

<<채점하는 과제 4>> ($ 표시 부분은 한 줄이라는 의미로 정의하자.)

from Tkinter import *

root = Tk()

c = Canvas(root, height=256, width=256)

c.pack()

import math

rgbarray = [[0,0]]

for i in range(128):

     for j in range(128):

         if j!=0 or i!=0:

             rgbarray.append([2*i,2*j])   #위 내용과 동일

         

def calcdistance(x,y):           #Rotate 를 실현할 함수

     rex = int(x*math.cos(math.radians(45)) - y*math.sin(math.radians(45)))

     rey = int(x*math.sin(math.radians(45)) + y*math.cos(math.radians(45)))

     #45도 변환이므로 삼각함수를 이용하여 새로운 좌표 rex, rey 를 도출

     if rex>-1 and rex<128 and rey>-1 and rey<128: #새로운 좌표가 유효하면

         c.create_rectangle(rex*2, rey*2, rex*2+4, rey*2+4, width=0, fill= $

"#%02x%02x%02x"%(rgbarray[(128*x)+y][0],rgbarray[(128*x)+y][1],128))

 #새로운 좌표의 위치에 현재 위치의 RG 값을 적용하여 사각형을 그림

for i in range(128):

     for j in range(128):

         calcdistance(i, j)     #함수 호출

- Bitmap 시간 때 배웠던 Rotate 하는 과정에 필요한 수식을 이용하여 구현했다. 이를 위해 math 를 import 하였으며, 정수여야 하기 때문에 int 를 적용하였다.(혹은 round를 이용하여 두 번째 인수에 0 으로 설정해도 무방하다.) 길이를 2로 설정하지 않은 것은 45도 회전에 따른 일부 공간의 표현이 막히기 때문이다. 정수로만 존재하는 좌표탓에 실수로서는 분명히 다른 좌표가 동일화되는 문제가 발생한다. 그 결과는 아래의 그림과 같으며, +4의 효과는 보간법을 적용한 결과와 유사한 효과를 지니게 된다.

 4. 배운점(느낀점)

①  블러링 효과가 유효한 내용이었는지 다른 예제에 적용한 결과를 통하여 파악하자.

이는 기존의 문제에서 사각형의 크기를 넓혀서 표현한 그림이다. 커진 변화 탓에 앨리어싱 현상이 보임을 알 수 있다. 그림에서 보이듯 왼쪽의 그림보다 오른쪽의 그림이 색상간의 변화가 무뎌졌음을 통해 이 알고리즘은 색상에 대한 블러링 효과가 유효하단 결론을 얻을 수 있다.

②  채점하는 과제 3은 블러링이 적용되는지 알아보기가 힘든 탓에 몇 번이고 알고리즘을 재적용하는 일이 있었던 반면에, 채점하는 과제 4는 표현 결과 때문에 많은 고생을 했다. 처음의 45도 결과 화면은 현재의 결과 화면과 반대방향으로 표현되는 것과 함께 실제 그림이 돌아간 것이 아닌 돌아간 형태만 유지, 색상은 원본상의 위치와 동일하게 표현되는 문제가 있었다. 다시 알고리즘을 파악하다보니 구조에서, 새로운 좌표를 얻어 그 좌표의 값에 해당하는 x, y 를 그대로 출력했기 때문에 생긴 실수였으며 이를 파악했더니 구멍이 숭숭 뚫린 그림 6과 같은 결과를 얻고 역시 한참을 고민했다. 배웠던 interpolation 은 Nearest neighbor, Bilinear, Bicubic 이었는데 Nearest 를 직접 구현하지 않고 이와 유사한 효과를 얻을 수 있는 방법을 고민하다가 차례로 색을 적용해나가는 알고리즘 상에 미리 그려놔도 이후에 겹쳐지는 영역은 이후의 그림이 덮어쓴다는 점을 이용하여 구현하였다.

③  배열을 이용하여 그림을 표현할 때 처음엔 튜플을 추가하는 방법으로 표현하였다.(리스트내의 튜플로)다음 문제에서 직접 내부 배열의 값을 변경하는 과정에서 에러가 발생하였고 다시 튜플이 아닌 리스트로 수정하는 시행착오도 있었다.

④  과제 수행과는 직접적인 연관이 없는 건으로, 프로그램의 코딩을 따로 파일로 생성하여 실행하는데에서도 꽤 많은 어려움이 있었다. 더블클릭하여 실행하면 프로그램이 바로 종료되는 탓에 프롬프트로 직접 접근하여 실행해보기도 하는 등의 시도 끝에 폴더 옵션에서 E:\PYTHON22\python.exe -i "%1" %* 로 -i 가 추가되면 바로 종료되지 않음을 인터넷을 통해 알 수 있었다.

⑤  sin, cos 부분은 모두 45도이므로 math.sqrt(2)/2 로 대체하여 같은 결과를 얻을 수 있다. math 없이 루트 2 의 값을 (약)1.4142136 를 곱하여 표현한다면 math 없이 표현하는 것도 가능하다.

⑥  가장 흥미 있었던 과제였다. 알고 있는 범위 속에서 문제를 풀어내는 과정이 마치 퍼즐을 풀어내는 것 같았으며 여러 번의 시도 끝에 결과를 얻어냈을 때의 기분은 무척 좋았다.

1. 문제 개요

어셈블러 알고리즘과 자료구조를 바탕으로 앞선 레포트에서 했던 어셈블러 컴파일 과정을 알고리즘 Pass1, Pass2를 참조하여 프로그래밍 언어를 이용하여 프로그래밍과정으로 만들고 더 추가적인 기능이 있을 때 추가 하여라.

2. 문제 분석

 <알고리즘>

 Pass 1

1) 한 줄을 읽는 것으로 시작한다. 그리고 분기하는데, 읽은 첫 줄의 OPCODE 가 'start'가 아니라면, LOCCTR 을 0 으로 초기화하는 것으로 끝낸다. 반면, 'start'라면 시작 주소값으로서 OPERAND(immediate value)를 저장하고, LOCCTR 을 위의 시작 주소값으로 초기화한다. 그리고 파일 내 다음 줄을 읽어들인다. 그리고 이후부턴 OPCODE 가 'END' 가 아니라는 조건만 만족하면 이후의 내용을 계속 반복하는 구조이다.

2) 현재 line 모두가 주석문으로 이뤄진 문장라면 바로 파일 내 다음 줄을 읽어들이게 된다. 주의할 점은 이 동작은 line 모두가 주석문이 아니라는 조건에 해당되어도 마지막에 실행되는 동작으로,내부에 별도의 추가 동작의 실행 여부를 결정하는 조건들의 나열로 구성된다.

3) Label 영역내에 symbol 이 있다면, SYMTAB 에서 이 label 을 찾는다. 찾은 결과가 있다면, 해당 symbol 이 복사되었다는 의미로 error flag 를 설정한다. 찾은 결과가 없을 경우는 SYMTAB 에 Label 과 LOCCTR 을 추가한다.

4) 3번 항목의 결과와는 별개의 명령 구문으로, OPTAB 로부터 OPCODE 를 찾는다. 찾았다면 LOCCTR 에 3(이는 명령어의 길이를 의미하는 것으로, 확장형(+ 형태)을 만났을 때는 4로 배정이 된다.)을 더한다. 혹 다른 조건으로, OPCODE 가 'WORD' 일 때는 LOCCTR 에 3을 더하는 작업으로 끝내고, OPCODE 가 'RESW'나 'RESB' 일 때는 정의되는 데이터 영역의 길이를 합산하는 것으로, RESW 는 3 * OPERAND(immediate value)를, RESB 는 OPERAND(immediate value)를 LOCCTR 에 합산한다. OPCODE 가 'BYTE' 일 때는 연속되는 길이(Byte 기준)를 측정한 후 그 길이만큼을 LOCCTR 에 합산하는 결과를 보인다. 위의 조건들을 하나라도 만족하지 못하는 경우엔 유효하지 못한 operation code 란 의미로

error flag 를 설정한다.

5) 위 반복문의 조건에 어긋나는 'END' 문장을 만났을 경우 반복을 해제하고 마지막 줄을 읽어들여 현재의 LOCCTR 과 첫 시작 주소값의 차를 프로그램의 길이로서 저장한다.

Pass 2

1) 중간 파일로부터 첫 번째 줄을 읽는다. 만약 OPCODE 가 'START' 라면, 리스팅 파일에 쓰고  목적 파일에 헤더 레코드를 기입한다. 텍스트 레코드를 초기화 시킨다.

2) OPCODE가 ‘END'가 아닌 한 반복을 계속 한다. 반복 문 안에서 만약 읽은 줄이 주석 라인이 아니라면 이 후 나열할 명령을 수행한다.

3) OPCODE에서 OPTAB을 찾는다. 만약 OPREAND 필드에 심볼이 있다면 OPERAND의 SYMTAB을 찾고 OPERAND주소로써 심볼 값을 저장한다. 찾지 못했을 시에는 OPREAND주소에 0을 저장하고 에러 플래그(undefined symbol)를     나타낸다. 하지만 심볼이 없다면 OPERAND 주소에 0을 저장한다. 그리고 나서 위의 내용을 바탕으로 목적코드를 생성한다. 이 때, OPCODE에서 찾은 OPTAB이 ‘BYTE' 혹은 'WORD'일때는 바로 목적코드로 변환 한다.

4) 만약 목적코드를 현재의 텍스트 레코드에 저장하지 않을 경우에는 목적 프로그램에 텍스트 레코드를 생성한다. 목적코드를 텍스트 레코드에 작성한다.

5) 중간파일에서 읽은 줄을 위의 조건을 바탕으로 리스팅 파일을 작성하고 중간파일의 다음 줄을 읽는다. 그리고 이를 OPCODE가 'END'가 아닌 한 계속 반복한다.

6) 목적프로그램에 마지막 텍스트 레코드와 엔드 레코드를 작성한다. 그리고 리스팅 파일의 마지막 라인을 작성하고 프로그램을 마친다.

1. 문제 개요

- 교재 연습문제 5.19 3개의 플립플롭 A, B, C, 한 개의 입력 x와 한 개의 출력 y를 가진 순차회로를 설계한다. 이 회로의 상태도는 교재에 있으며 무정의 조건, 즉 사용되지 않는 상태를 이용해 설계한다. 사용되지 않는 상태가 미치는 영향을 알아보기 위한 설계를 통해 얻어진 이 회로를 분석한다. 단, 사용하는 플립플롭은 JK FF를 사용한다.

- Verilog 를 이용하여 교재 HDL 예제 6.4 Ripple Counter를 직접 코딩해보고 그 결과를 살펴본다.

2. 문제 분석(알고리즘 및 해결방안)

①  연습문제의 내용은 JK Flip-Flop을 이용하여 조건에 맞는 회로를 설계하는 내용이

     다. 회로의 설계는 (1) 주어진 조건(기술된 내용 등)으로부터 상태도를 유도하고,

     (2) 상태 축소, (3) 상태 할당, (4) 상태표를 작성하고, (5) Flip-Flop을 선택 후,

     (6) Flip-Flop 의 입출력식을 유도, (7) 논리도를 작성하는 단계로 진행된다. 이

     문제의 경우 JK Flip-Flop으로 정해졌으며 D Flip-Flop 에 비해 입출력식 유도 과

     정이 하나 추가된다는 점 이외엔 큰 문제는 없다.

②  예제의 내용 그대로 코딩 하되, 본문의 코딩 내용에 컴파일 오류가 발생한다. 이를

     수정하고 내용을 확인한다.

3. 결과(소스 및 스크린샷)

<<1번 과제, 연습문제 5.19>>

①  상태도가 교재에 있고, 상태 축소와 상태 할당은 대상이 없으므로 생략한다.

②  상태표

현재 상태			입력	차기 상태			출력	JK Flip-Flop
A	B	C	X	A+	B+	C+	Y	Ja	Ka	Jb	Kb	Jc	Kc
0	0	0	0	0	1	1	0	0	x	1	x	1	x
0	0	0	1	1	0	0	1	1	x	0	x	0	x
0	0	1	0	0	0	1	0	0	x	0	x	x	0
0	0	1	1	1	0	0	1	1	x	0	x	x	1
0	1	0	0	0	1	0	0	0	x	x	0	0	x
0	1	0	1	0	0	0	1	0	x	x	1	0	x
0	1	1	0	0	0	1	0	0	x	x	1	x	0
0	1	1	1	0	1	0	1	0	x	x	0	x	1
1	0	0	0	0	1	0	0	x	1	1	x	0	x
1	0	0	1	0	1	1	0	x	1	1	x	1	x
1	0	1	0
1	0	1	1
1	1	0	0
1	1	0	1
1	1	1	0
1	1	1	1

③ FF 식, 출력식 유도

AB/CX

Ja = B'X

0	1	1	0
0	0	0	0
x	x	x	x
x	x	x	x

           

Ka = 1

x	x	x	x
x	x	x	x
x	x	x	x
1	1	x	x

Jb = A + C'X'

1	0	0	0
x	x	x	x
x	x	x	x
1	1	x	x

           

Kb = C'X + CX'

x	x	x	x
0	1	0	1
x	x	x	x
x	x	x	x

Jc = AX + A'B'X'

1	0	x	x
0	0	x	x
x	x	x	x
0	1	x	x

           

Kc = X

x	x	1	0
x	x	1	0
x	x	x	x
x	x	x	x

A+ = A'B'X

0	1	1	0
0	0	0	0
x	x	x	x
0	0	x	x

           

B+ = A + C'X' + BCX

1	0	0	0
1	0	1	0
x	x	x	x
1	1	x	x

C+ = AX + CX' + A'B'X'

1	0	0	1
0	0	0	1
x	x	x	x
0	1	x	x

           

Y = A'X

0	1	1	0
0	1	1	0
x	x	x	x
0	0	x	x

⑤  이 회로는 Ka = 1 로, A+ = 0 의 결과를 항상 갖게 되는 보정의 효과를 갖는다.

<<2번 과제, Verilog Ripple Counter>>

①  책의 내용대로 코딩 후(테스트 벤치부는 삭제) 컴파일을 실행하면 에러가 발생한다.

②  이는 코딩 부의 쉼표가 아닌 or 로 바꾸어 주면 해결된다.
 always @ (negedge CLK, posedge Reset) ->  always @ (negedge CLK or posedge Reset)

③  또한 설정 하나를 바꾸어주어야 하는데 클럭폭의 영향으로 Grid 설정을 10.0ns로 변경해야 한다.

④  웨이브폼 생성 후 시뮬레이터를 실행시킨다. (클럭값을 count 에 별도로 지정해주어야 한다.)

⑤  좀 더 상세히 분석해보자.

     count 는 20ns 의 주기로 반복되는 클럭으로, 주기의 반복에 따라 A0 가 그 펄스

     에 반응함을 볼 수 있다. 이 구조는 리플 카운터의 각 플립플롭의 출력이 다음 상

     위 FF의 Clk에 연결되어 보수화 FF 로 인해 반응하는 구조와 동일하다. 순서는

     0000 -> 0001 -> 0010 -> 0011 -> ..... -> 1110 -> 1111 -> 0000 -> ....

     순이다. (부-에지)

     이하 내용은 코딩이다.

`timescale 1ns / 100 ps

module Ripple_Counter_4bit (A3,A2,A1,A0, Count, Reset);

output A3,A2,A1,A0;

input Count,Reset;

//Instantiate complementing flip-flop

Comp_D_flip_flop F0 (A0, Count, Reset);

Comp_D_flip_flop F1 (A1, A0, Reset);

Comp_D_flip_flop F2 (A2, A1, Reset);

Comp_D_flip_flop F3 (A3, A2, Reset);

endmodule

//Complementing flip-flop with delay

//Input to D flip-flop = Q'

module Comp_D_flip_flop (Q, CLK, Reset);

output Q;

input CLK, Reset;

reg Q;

always @(negedge CLK or posedge Reset)

if (Reset) Q <= 1'b0; else Q <= #2 ~Q;

endmodule

다음 학기도 남아 있는 상황이라 자료 공개는 할 의도도, 할 수도 없을 것 같습니다;
현재 C로 작성된 프로그램에 대해 Garbage Collection을 삽입하여 메모리 누수를 방지하고, 감시, 운영하는
프로그램을 만들고 있습니다. 리눅스 기반이 아닌 Windows에서의 PEFormat에 대하여 수행하고,
이를 평가 및 관리하는 이론적 기준 확립에 가장 큰 중점을 두고 있습니다.

컴퓨터공학과에서 들어갈 수 있는 최저의 깊이까지 내려온 과제라 넉넉잡고 깊이 확인해봐야 할 것 같습니다.
완성은 가능할 것 같지만 이후에 많은 난항을 겪을 것으로 예측되므로 긴장하고 있는데요;
분석과 설계 중반까지는 끝낸 상태입니다. (아... 설계 초반으로 정정하죠. ㅇㅅㅇ;) 

이번 학기 수강했던 데이터마이닝의 프로젝트 내역입니다. 컴퓨터 판매에 대한 1달간의 판매내역을 중심으로,
이를 요구사항을 정해 분석하여 전략을 제시하는 것이 주요 내역이었습니다. 즉, 과목에서 배웠던 모든 내용들을
총동원하여 엮어나가는 점이 관건입니다.

과목 자체가 무척 흥미롭습니다. 일군의 데이터 묶음으로부터 숨은 관계, 의미를 추출해내는 작업입니다.
마치 규칙없이 사방으로 흩어진 퍼즐 조각을 이리저리 맞추다보니 안에 어떤 숨은 글자가 있는 것과 같은 느낌이랄까요,
그런 점이 이 데이터마이닝의 매력인 것 같습니다. 하지만 실제 적용되기 어려운 점은,

해당하는 변수들에 대해서는 하나의 기준으로 단일화되기 어렵다는 것입니다. 이들은 복합적이기 때문에,
충분히 이들을 정의했으니 이 내부에서 단서들을 찾아내겠지- 하고 단정짓기 어렵다는 것입니다.
두 번째로는 해당 데이터 셋의 수집이 어렵다는 점입니다. 비지니스에 이를 접목하려면 목적하는 데이터 그룹이
확보되어야 하는데 가볍게 통계 정보들로만 보기에는 가치가 높은 정보들이 주류라 공개되어 있는 것이 거의 없고,
수집에 시간도, 노력도, 실질적인 경제적 비용까지도 많이 들여야 할 것입니다.

어쨌건, 그런 제약사항이 있지만 이 조건만 해결된다면 내부에서 생각지 못한 관계, 추측이 가능해집니다.
분류 나무는 직관적으로 나타나는 예시여서 그렇지만 회귀분석이나, 군집 분석 등은 이 데이터마이닝 작업에 있어서
꽃과 같은 내용입니다. 덤으로 붙여보자면 분류 모형, 연관성 분석 등을 꼽아볼 수 있겠습니다.

작업 내용도 재밌었습니다.  한 팀원분과는 잊지 못할 에피소드가 생기긴 했습니다만(-_-;) 잘 해결되어 다행입니다.
고마워요, 발표자분. ^^

Objective-C 로 코딩된 내역입니다. 실제 실행은 시뮬레이터로 돌려봤습니다.
직접 설계한 DB Schema에 따라 작성된 내용은 기본 제약에 거쳐 얻은 결과입니다. 그리고 일부 쿼리는 다음과 같습니다.

select bookname, cname, bcname, authname, pubname, pubdate, popularity, stock, bookno from AUTHOR, BIGCATEGORY, WRITING, PUBLISHER, CATEGORY, BOOK where AUTHOR.authno = WRITING.fauthno and WRITING.fbookno = BOOK.bookno and BOOK.fpubno = PUBLISHER.pubno and BOOK.fccode = CATEGORY.ccode and CATEGORY.fbccode = BIGCATEGORY.bccode order by BOOK.bookno asc;

 

select userid, bookname, predictretdate from USERINFO, LENDING, BOOK where userno = fuserno and bookno = fbookno and actualretdate = '0' order by predictretdate, userid asc;

시간이 부족해서 하고 싶었던 부분들을 많이 하지 못해서 조금 아쉬움은 남습니다. 하지만 이런 욕심을 빼고 나면
초기 계획했던 내용은 모두 삽입된 것이니 나름 괜찮아요. ^^~ 

증강현실 기술과 GPS, Gyro Sensor를 이용한 SNS 서비스가 프로젝트 주제였습니다.
"Project Doodle"로 불린 내용으로 이름 그대로 피켓을 달아두는 서비스 내용입니다.
구현전 작업인 설계 단계까지만 진행하여 이 결과를 확인하는 프로젝트였음에도,
기술적 구현 가능성을 이미 검증한 내용이었습니다. 지금 구현해보라고 한다면 적당한 시간 내로
할 수 있을 것 같네요. (이번 4학년 때 스마트폰 프로젝트 경험이 도움이 되었습니다.)

위 클래스 다이어그램은 원본 파일을 잃어버려서 (방심하고 백신을 멈춰놨다가 벌어진 사태입니다...ㅠ.ㅠ)
보고서에 기재되어 있는 것을 가져왔더니 이렇게 찌그러져서 나오네요. ㅇㅅㅇ;;;

소프트웨어경진대회 장려 수상작입니다. 실제 구현까지 해보라고 했다면 장려 이상도 가능했을 것 같아요.
(물론 충분한 시간과 지금 4학년인 제 입장에서의 Objective-C 혹은 Java 경험이 뒷받침되었을 때 이야기지만요;)

마이크로프로세서 프로젝트는 두 대의 라인트레이서를 규정된 맵 위에 올려두고 랜덤하게 배치될 장애물을 제외한 나머지 영역을
순회하는 내용입니다. 두 대가 함께 순회한다는 예외사항들과, 최대한 빠른 시간 내로 탐색하는 것에 따라 성적이 결정됩니다.
디지털 논리 실습을 거치면서 임베디드 기기에 포팅하고 다뤄보았지만 실제 포팅된 기기에 모터가 달려서 직접 운행되는 것을
보는 것- 무척 색다른 경험이었습니다. 그런만큼 애먹은 부분도 많았고요.
 

직접 부품에 대해 조립 및 포팅하고 알고리즘을 적용한 코드를 이용하여 최고 효율을 찾아내기 위한 작업들은,
여지껏 경험해본 컴퓨터정보공학 커리큘럼과는 조금 거리가 있는 내용이었기 때문에 더 느낀 바 많았던 것 같습니다.

사실 맵은 고정, 장애물 위치만 임의로 주어질 뿐 그 크기와 개수는 고정이었기 때문에 이를 예측하여 하는 방법이
있습니다. 대표적인 방법으로 맵을 분할하는 것입니다. 하지만 여기서 조심해야 하는 부분이 있습니다.
라인트레이서가 서로를 향해 바라보는 시점 혹은 다른 측면 센서가 다른 라인트레이서의 센서에 직선상에 위치할 경우
이를 반사한 적외선 센서로 인식해버려 장애물이 있다고 착각하는 점입니다.
치명적이게도 이 센서 자체에 대한 제어권 없이 Read만 되는 형태이기 때문에 더더욱 난감한 것이죠.

그러면 맵 분할은 불가능한가? 아닙니다. 두 대의 라인트레이서를 서로 엇갈려 순회할 알고리즘으로 4분할 하는 방법이
있습니다. 그래서 서로 맵 탐색 시간동안 두 라인트레이서를 대각 방향에 엇갈려두면 서로 마주칠 일이 없고, 두 대 모두
해당 Area의 탐색이 끝났을 때 맵의 끝 부분으로 돌아가 지나가도록 하는 방법이 있습니다. (뭐 조금 가까워진다면
다른 쪽 라인트레이서의 센서를 완벽히 감추는, 그러니까 거꾸로 돌린 형태로 두는 방법이 있습니다.)

하지만 이 방법은 일부이지만 Time lose가 발생합니다. 동시에 범용성 있는 알고리즘이라 하기 힘듭니다. 때문에,
우리 팀은 이 제약사항을 무시하고 어떤 환경에서도 인식할 수 있는 범용적 성격의 패턴을 구상하게 됩니다.
'개미'가 탐색하는 방법으로부터 고안한 인공지능적 접근으로 해결하였습니다. 때문에, 오히려 위 4분할 방법보다
 더 시간 손실이 큽니다. 하지만, 어디에나 적용될 수 있으니 이것으로 가자 - 라는 것이 팀의 판단이었습니다.

대부분의 팀들이 2분할 방법으로 이 문제를 해결하였습니다. 분명히 예외사항으로 장애물의 사이즈가 2분할의 한
영역을 모두 덮을 수 있습니다. 얼마든지 교수님께서 그렇게 지시하신다면 순회가 불가능해질텐데 - 하지만 교수님께서
그렇게까지는 안 하시더군요;;;

결과는 좋았습니다. 기록상에서 1등은 아니었지만 범용성에 대해 인정받았다 생각합니다.

제목은,
"블링크 ~ 샤프 찾기 대모험 ~" 입니다. 본격적인 게임을 만들었습니다. 시나리오 작업까지 이뤄졌고,
현실 세계를 풍자했습니다. (.....)

상태, 데이터과 같은 기본 골격 구조에 대한 Design을 함께 설계했습니다. 직접 해보면서 느꼈지만 이 골격을 구성한다는 건,
전체 프로그램 구조를 이해하고 있어야 가능한 일입니다. 하지만 이번 프로젝트는 처음 배우는 OpenGL 라이브러리에 대한
것으로, 가벼운 그림 그리기조차 버거웠던 제가 3D 게임을 원활하게 설계한다는 것이 조금 무리였다고 생각됩니다...만.
다행히 팀원들 도움과 어우러져 이룰 수 있었네요.

퀄리티 덕에 팀 성적에서 1위였습니다. (ㅎㅎ)
 

프로젝트는 아닙니다. 오히려 그 다음 학기인 4학년 1학기 때의 "데이터베이스 실습" 과목이 본격적입니다.
이 때는 기초적인 내용을 학습한 후 이를 C 코드에 삽입하는 형태로 작성된 프로그램입니다.
프롬프트창에서 커맨드를 입력하는 방식으로 된 녀석이라 투박해보이지만 어플리케이션의 운용보다
내부 DB Schema와 이용했던 SQLite를 어떻게 이용하느냐에 달려 있었던 내용입니다.
 

나름의 예외처리도 삽입된 내용입니다;;;
이후 디비 실습 때는 UI도 간략히 삽입됩니다. 

프로젝트 스케일에 있어서 가장 컸고, 많은 시간을 공들였던 내용으로 기억합니다.
시기가 어쩌다보니 맞아떨어져서 기말고사 이후에 집중할 기회가 있었을 거예요.

 
담당했던 부분은 서버 설계, 동기화 조정, 암호화 컴포넌트 설계였던 것으로 기억합니다. 아, 짧게나마 오프닝 동영상을
만들기도 했습니다! ....하지만 제가 담당했으니 미적감각에 무리가 좀 있었지 모르겠네요.
방대한 리소스 확보와 인터페이스, 애니메이션 작업은 팀 동료들이 맡아주었습니다. 코드량이나 노력으로 따져봐도
잘 배합되었던 팀 구성이었습니다.

암호화 부분은 당시 배웠던 정보보호론의 내용을 적용시켜 구현한 내용이었고요, 서버 부분은 돌렸던 단말기가 넷북 환경이었기때문에 더 많은 양의 접속이 발생하면 버벅거리더군요. 서버 설계 후 이 테스팅 및 디버그를 제가 해야 하는 부분이라 이런
작은 부분까지도 많은 신경을 써야 했습니다.

기획부터 시작해서 디자인, 구성, 설계, 아이디어, 리소스 확보 등 전방면으로 노력한 완성형 프로젝트라 말씀드릴 수 있습니다.
많은 테스팅으로 프로그램 완성도도 매우 높았고요.

프로젝트는 아니었고, 가산점이 부여된 일반 개인 과제였습니다.
DES 알고리즘의 동작형태를 이해하고 직접 코딩하면 되는 내용으로 위 캡쳐 화면이 결과화면입니다.
초기설계부터 완성까지 약 4시간 걸렸는데 컴포넌트별 분리하고 통합하는 과정을 끝내고 실행했을 때
단번에 돌아가는 프로그램을 보면 그 짜릿함은 이루 말로 다 할 수 없습니다.

조금 더 스케일이 커졌다면 이야기는 달라졌겠지만요. (-_-;) 

GeekOS는 OS 수업에 있어서 학생들이 직접 이를 구현해보고 이해할 수 있도록 제공되는 프로젝트 타입 학습물입니다.
각 Step별로 구현해나가는 단계가 점진되는 방식입니다.

사실 이를 정확히 학습자세로 구현한다는 것은 커널에 대해 깊은 이해가 있는 것과 동시에 이런 이론적인 내용이 이 코드상에선
어떻게 유도되었는지를 파악하여 해당 위치에 대해 구현하여야 합니다. 어셈블리 단계까지 함께 봐야 하는 케이스도 더러 있기에
만만하지 않은 내용이었죠.

개인적으로는 ELF Format을 다뤘던 Project 1 때 제일 고생했던 것 같습니다. 실제 구현되는 양이 가장 적었음에도 해법을
찾지 못해 가장 우왕좌왕 했거든요.

다른 전공과목이 진행되는 것과 함께 이 많은 내용이 한 학기에 진행되다보니 밤도 많이 샜습니다. 

2009년 말 수강했던 윈도우즈프로그래밍의 프로젝트 과제가 그림판을 만드는 것이었습니다. 바로 전 학기 때는 QT에서 만들었던 객체 방식의 그림판과는 달리, MFC를 이용하여 실제 비트맵 방식의 그림판을 설계한 것으로 보다 그림판에 가깝고, 그 이상의 임팩트를 줘야 했던 내용이었습니다.
위 그림이 그 결과인데요, 다소 투박해보이는 디자인은 공돌이들의 기본 소양이었으니 넘어가고요,(ㅇㅅㅇ;;;)
왼쪽에는 그림 작성에 쓰이는 도구와 필터 효과 색상 정보 표현 및 선택 등이 있고요,
오른쪽에는 작성한 내역에 대한 히스토리가 설정되어 있습니다.

팀은 세 명으로 구성되었고, 전 아이디어 도출 및 선택, 색상, 대화상자 등의 기본 및 부수 요소들을 구현했습니다.

히스토리 구현의 차이는 이전 객체 방식에서는 그린 객체의 작업 하나하나를 단위별로 구분하여 해당 작업 내역에 대해 지정된 구조체에 저장시켜 이를 Undo 혹은 Redo 하는 방식이었는데요, 비트맵 환경에서는 작성된 내역을 구조체로 보유하기에 한정된 정보로는 무리한 부분이 있어 다른 방식을 택했습니다.

여러 독특한 기능들과 함께 전 학기 때 배웠던 멀티미디어 이론을 바탕으로 필터 기능을 구현했다는 점이 크게 가산점으로 작용한 것 같습니다. 발표도 무난하게 잘 되서 최고점을 받았었습니다.

디지털 논리 실습 프로젝트는 2가지였습니다.
처음 것은 FPGA에 디지털 시계를 구현하는 것이었습니다. 구현 자체의 어려움을 떠나서
정확한 분주 구성과 많은 테스트를 통해 시간 흐름과 동일한 클럭 주기를 잡아주어야 한다는 점이 어려웠습니다.
왜 코딩하다보면 그런 것 느끼잖아요, "분명히 문제가 없는 소스인데 왜 포팅해서 돌리니까 안 되는거지?"
임베디드 분야의 흥미로운 부분이자 단점으로도 말할 수 있지요.

이 시계를 마치고 학기말 프로젝트로 부여받은 것이 MU0 Design입니다.
컴포넌트의 구성은 맨 윗 그림과 같고요, 컨트롤 유닛의 상태도표가 두 번째 그림입니다.
만약 프로젝트가 바쁜 기말 기간에 2주간이라는 제약된 기간이 아니었다면 두 번째 그림의 도표가 주어지지 않고
직접 구현하는 방향으로 나왔을지도 모르겠어요. 저 부분의 상태값들이 왜 그런 것인지, 어떠한 흐름을 갖는지를
이해하는 것이 이 프로젝트의 첫 번째 핵심이거든요.

마지막 그림은 수행한 결과입니다. 예제로 주어진 인스트럭쳐에 대해 수행하면 그림과 같은 결과를 갖게
되는데요, 두 번째 핵심이 이 같은 결과가 나오게 되는 메모리 참조 흐름입니다. 물론 첫 번째 핵심이나 두 번째나
마찬가지의 공통집합을 갖습니다.

정확한 이해를 기반으로 컴포넌트를 구분하여 설계한 뒤 통합하면 되는데요, 이 설계에 모호함이 포함되거나
인터페이스 정의에 문제가 있었다면 Integration 작업에서 꽤나 애먹어요.

제가 속한 팀은 이 문제로 골머리를 앓다가 한 명이 담당하는 편이 빠르겠단 결론을 내리고 홀로 뛰어들었습니다. (ㅋㅋㅋ)
팀원의 요구내용을 파악하고 Bottom-up Approach 로 연결하였는데, 이전의 실패를 교훈 삼아 사전 정의를 명확히
해두었더니 이 부분의 에러는 없었습니다.
비록 날을 새야 했지만 완성하고 나니 좋더군요.

어셈블러로부터 목적코드가 만들어지는 과정을 이해하고 이를 C 코드로 작성하는 프로젝트였습니다.
모든 어셈블러 명령어를 소화하는 것은 아니었고 일련의 범위 제한은 있었지만, 이건 구현하는데 있어서
일부 반복적인 작업들이 줄었다는 의미이지, 전체적인 구조와 흐름을 이해하고 처리 방향을 만들어내는 것과는
거리가 있는 이야기입니다.

당시 C++을 배웠습니다. 그래서 구현 언어가 특별히 C로 한정된 것이 아니어서 C++ 문법을 이용한 코드를
만들었는데 객체지향 언어인 C++을 이용한 절차지향적 프로그램이 만들어졌지요. (-_-;;)

이 정도 학부생이라면 객체지향의 개념에 대해 학습하지만 막상 이를 자기 것으로 소화하고 활용해야 한다는 점에선
많은 어려움이 따릅니다. 이는 설계 관점에는 더욱 거시적으로 바라보고, 직관적으로 이해할 수 있기엔 무리가 따르기
때문이기도 합니다.

약 2주간 진행 되었습니다. 대부분의 프로젝트 마감 및 최종검사(혹은 발표)가 기말고사 기간과 오버랩되기 때문에
2주 중의 한 주 가량은 사실상 작업에 매진했다고 보기 어렵고요, 1주일 가량은 학교 휴게실에서 넷북을 조원들이 서로
꺼내들고 노숙하다시피 작업했던 것으로 기억합니다. (수면은 집에서... 하지만 주말은 모조리 반납하였지요.)

초반 Pass1의 설계 때 이후의 작업을 고려하여 설계하는 부분을 담당하고 Pass2 또한 지원할 예정이었습니다.
하지만 이 당시 느꼈던 분량 많은 코드에서 느껴지는 울렁증 덕에 Pass1 설계를 마치고 Pass2 에서 큰 도움이 되진
못한 것 같습니다.  다행인건 Pass2에서 그대로 활용할 수 있도록 함수 입출력을 유용하게 설계한 점을 위안 삼았지요.

"울렁증"은 다행히 여기까지로 그쳤습니다. (이후 설계 과목들을 더 접하면서 점점 익숙해지더니 무리 없어지더군요.)
당시 팀워크도 상당히 좋았고, 조원 구성도 알맞게 이뤄졌습니다. 서로 잘 도와 무사히 마친 프로젝트로 좋은 성과를
거두었습니다. 

당시 복학한 후 처음으로 수행한 프로젝트였습니다.
해당하는 과목은 객체지향 프로그래밍(Object-Oriented Programming)으로,
C++ 언어와 함께 객체지향 개념을 배우는 커리큘럼에 입소문으로만 들어오던(-_-;) 리눅스를 설치 및 활용해보고
QT를 이용한 그림판 작성 프로젝트가 요구되었지요.

본론으로 들어가기 전에 여담 하나만 늘어놔 볼께요.
리눅스 개념을 전혀 모르던 내게 상세한 지침 없이 (물론 스스로 학습할 수 있도록 개략적인 안내는 있었습니다.)
설치 & 활용의 과제는 그렇다고 쳐요... 문제는, 당시 삼성 NC10 넷북을 구매했던 제게 파티션을 건드리지 않고
무선랜 드라이버와 한글 입출력 문제는 생각지도 못한 난제였습니다. 무려 주구장창 5일간 허비.
학교 실습실 컴퓨터 뒤의 유선랜을 이용할 수 없었다면 치사하게 MAC 어드레스에 케이블 망 사용 허가를 했던
집의 인터넷 상황 덕에 더 큰 고비를 맞이했을지도요.

어찌어찌해서 리눅스 환경을 갖춰놨더니 이번엔 QT... 문법은 C++과 거의 동일했지만 기본 구조를 전혀 모르는
탓에 애먹었습니다. (생각해보면 이 프로젝트 덕에 스스로 학습하며 성과물을 체크해보는데 익숙해졌던 것 같네요.)

비트맵 방식이 아닌 객체 방식(Microsoft Office 군의 PowerPoint의 그림들과 같은 속성)으로 완성되었습니다.
기본 구현 사항인 도형 작성, 파일 저장 및 불러오기, 색상 부여 등에
추가 기능으로 도형 선택, 이동, 크기 조절, 정렬, Redo & Undo 등이 구현되었고요.

투박한 디자인 덕에 성능 또한 같이 평가절하 받을 것 같지 않나요? 물론 성능과는 별개였으니 다행이지요.
그리고 안타깝게도 디자인을 제가 제의했던 것 같네요. (당시 미적감각을 발휘할 여유가 없었다고 작게 변명해봅니다. ㅠ.ㅠ)

아쉬운 점은 코드 상의 초반 기본 틀(설계 수준까지는 아닌)과 일부 구현에 그치고,
코드 분량이 커짐에 따라 내가 제 역할을 못한 것 같아요.
후반 작업은 통합쪽으로 임무를 달리했으나 그마저도 버벅거렸던 탓에
1000줄 이상의 코드에 내가 울렁증이 있는 게 아닌가 걱정했던 때이기도 합니다.

다행스럽게도 같은 팀원들이 이런 부분을 커버해준 덕에 최종발표에서 좋은 성과를 얻을 수 있었습니다.
결론짓자면, 이 프로젝트를 통해서 뚜렷한 목적을 지닌 실무적 첫 팀활동으로 경험과, 팀워크의 장점,
제가 엔지니어로서 부족한 부분이 어떤 것인지 파악할 수 있었던 유익한 과정이었어요.

문제입니다.

정말 유난히 고생했던 문제였습니다.
겉보기엔 쉬워 보입니다만, 간단히 오름차순 혹은 내림차순으로 정렬 후
차이가 적은 쌍을 찾아 묶어가는 방식으로 진행하게 되면 위의 Sample Input 에 대해서는
결과가 올바로 나옵니다만, 치명적인 함정이 있습니다.
간단한 예를 들어 5명일 경우 1:4 의 팀 구성에 대해 밸런스가 맞을 경우가 있습니다.
꽤나 극단적인 경우입니다만, 인원 수가 늘어날 수록 팀간의 인원 사이의 차이값 또한 커질 가능성이
있음을 말합니다. 곧, 이 알고리즘으로는 1:4 의 경우에 대해 해결할 수 없습니다.
(5명의 인원이 각기 40, 41, 42, 43, 158kg 일 경우 x >= 2 에 대해 1:4 조합이 모두 성립됩니다.)

이 각기의 조합에 대해 대체 무슨 수로 찾아내느냐를 한참동안 고민했습니다.
재귀 호출 방법을 통해 각각의 조합을 유도할 것인가... 대책 없죠. -_-;

그리고 오늘 불현듯 떠오른 방법으로 구현했습니다. 아이디어 짜내는데 시간이 오래 걸렸지,
컴파일은 한방에 했네요. 위의 어떤 경우라도 답을 구해냅니다만, 브루트포스 방법으로 답을
구해내기 때문에 효율성에 있어서는 합리적이라 보기 힘듭니다. 물론, 어떤 경우가 해당할 것인지
직관적으로 구분해내기 힘들지만, 이 경우만큼은 해당하지 않을 것이다... 는 구분할 수 있으니까요.

코드입니다.


실제 전공과 관련된 내용은 안 올리려 했는데 이 문제의 해결방안을 도저히 모를 때,
검색한 자료 전부 위의 찾아내지 못하는 결점을 그대로 반영했더군요;

혹시라도 고민하시는 분이 계실까 싶어 잊기 쉬운 점에 대해 지적하고, 코드를 포스팅합니다.
문제의 해결 방안에 대해서는 포스트에 언급하지 않고 코드를 보면 이해할 수 있는데,
되도록 그 점은 각자 구현해보시는 게 좋겠네요. 문제 인식만 된다면 얼마든;;