//create the new decision tree object DecisionTree* NewTree = new DecisionTree(); //add root node the very first 'Question' or decision to be made //is monster health greater than player health? NewTree->CreateRootNode(1); //add nodes depending on decisions //2nd decision to be made //is monster strength greater than player strength? NewTree->AddNode1(1, 2); //3rd decision //is the monster closer than home base? NewTree->AddNode2(1, 3); //depending on the weights of all three decisions, will return certain node result //results! //Run, Attack, NewTree->AddNode1(2, 4); NewTree->AddNode2(2, 5); NewTree->AddNode1(3, 6); NewTree->AddNode2(3, 7); //Others: Run to Base ++ Strength, Surrender Monster/Player, //needs to be made recursive, that way when strength++ it affects decisions second time around DT //display information after creating all the nodes //display the entire tree, i want to make it look like the actual diagram! NewTree->Output(); //ask/answer question decision making process NewTree->Query();
IP 라우팅-> 네트워크 계층의 목적지 주소를 확인해 목적지까지의 경로를 설정해주는 방법.(1) Static Routing(정적 라우팅)-> 모든 네트워크에 대한 경로를 관리자가 수동으로 설정한다.-> 관리자가 다시 변경하기 전까지 절대 변하지 않기 때문에 새로운 네트워크가 추가되거나 삭제가 되더라도 매번 수동 설정이 필요하며, 이로써 관리자의 부담이 크다.-> 임의의 라우터에 문제 발생 시, 해당 정보에 대하여 자동으로 알지 못하기 때문에 토폴로지 변화에 적응할 수 없다.-> 관리지의 부담을 덜어주는 방법으로 Default Gateway(Default Static Route)를 이용한다.※ Default Gateway(Default Static Route)-> 패킷의 출입 경로가 하나 밖에 없는 Stub Network에 대하여 설정한다.-> 라우팅 설정을 단순하게 해 줄 뿐만 아니라 라우팅 테이블을 간소화 할 수 있다. (자세한 경로 요약 설명은 교재 참고)(2) Dynamic Routing(동적 라우팅)-> 일반적으로 중 * 대규모 네트워크에서 사용되며, 현재 EIGRP, OSPF가 주로 사용된다.-> 주기적 또는 비주기적으로 라우터간의 라우팅 정보를 업데이트한다.-> 네트워킹 장치 및 링크의 장애로 패킷을 주고받아왔던 경로를 사용하지 못할 경우, 자동으로 우회 경로를 찾아 통신 세션의 연속성을 지원한다.-> Static Routing에 비해 라우터의 자원을 많이 사용한다.가) Distance Vector Algorithm(Bellman-Ford Algorithm)-> 직접 연결된 라우터간의 경로 정보를 주기적(RIP : 30초, IGRP : 90초)으로 주고받음으로써 경로에 대한 정보를 알게 된다.(EIGRP 제외)-> 라우팅 정보 업데이트는 네트워크 상태 변화 여부에 관계없이 무조건적으로 이루어지며, 네트워크의 규모가 커질수록 업데이트 정보의 양이 증가한다.-> 최적의 경로를 선택하는 척도가 Hop Count에 의해서만 선택된다. 그렇기 때문에 목적지까지의 경로에 정확성을 보장하지는 못한다.(RIP)-> 서로 연결된 라우터에게만 주기적으로 정보를 전달하는데 이러한 과정을 Step-By-Step이라고 한다.-> 라우팅 프로토콜의 수렴시간이 상당히 소요된다.-> 대표적인 프로토콜 : RIPv1 & RIPv2, IGRP, EIGRP 등※ 정상적인 라우팅 기능의 수행을 위해서는 네트워크상에 존재하는 모든 라우터의 라우팅 테이블이 같아야 한다. 이와 같이 모두 같은 라우팅 정보를 가지게 되는 상태를 Convergence라고 한다.나) Link State Algorithm-> Shortest Path First Algorithm 또는 Dijkstra 알고리즘을 사용하여 목적지까지의 최단 경로를 계산 후, 이를 기초로 패킷을 전송한다.-> 경로 정보의 Update를 위해 LSP(Link State Packet)을 생성하며, 전달은 플러딩(Flooding) 방식으로 수행되고 이 정보를 전달받은 라우터들은 LSP를 참조하여 최단 경로를 결정한다.-> 라우팅 정보가 변경될 경우 바뀐 라우팅 정보만을 전파하기 때문에 트래픽 발생량을 현저히 줄일 수 있고, 라우팅 루프 같은 오류가 발생하지 않는다.-> Topology DB에 정보를 수정 후, ACK 신호를 Designed Router에게 전송한다.-> 대표적인 프로토콜 : OSPF, IS-IS 등Distance Vector AlgorithmLink State Algorithm이웃한 라우터의 시각에서 네트워크를 인식네트워크 전체를 인식라우터간의 거리를 더하여 계산다른 라우터까지의 최단경로 계산주기적으로 갱신 데이터를 교환이벤트 기반의 갱신 신호 교환이웃한 라우터와 라우팅 테이블 교환링크상태 정보만을 교환※ 플러딩(Flooding) : 어느 노드에서 들어온 패킷을 라우터에 접속되어 있는 다른 모든 노드로 전달하는 방식.-이하 공백 --> 라우터는 패킷을 전송할 때 메트릭(Metric)이라는 것을 기반으로 우선순위를 결정한다.* Hop Count : 목적지까지의 경로의 수를 가리키는 것으로 보통 Router의 수로 생각한다.* Network Delay : 하나의 패킷이 네트워크를 통하여 전송 측에서 목적지까지 가는데 걸리는 시간을 말하며, 대역폭, 실제거리, 포트의 큐, 과부하 등 여러 요인에 의해 결정된다.* Bandwidth : 연결된 네트워크 구간에서 사용 가능한 트래픽의 양을 말한다.* Reliability : 각 네트워크 연결 상태에 있어서 얼마만큼의 신뢰(일반적으로 비트 에러율)를 유지하느냐가 수치로 표현된 것을 말한다.* Load : 네트워크 트래픽의 분주한 정도를 말한다. 초당 패킷 처리율 등 다양한 방법에 의해서 계산 가능하다.① RIPv1(Routing Information Protocol version 1) - DVA-> 라우팅 정보 업데이트 시 UDP 520번 포트를 사용하며, 경로 결정을 위해 Hop Count를 사용한다.-> 최대 도달 가능 Hop은 15로 제한을 둔다.-> 라우팅 테이블을 기본 30초 간격으로 연결되어 있는 모든 인터페이스를 통해 Broad-casting(255.255.255.255)한다.-> 라우팅 테이블의 갱신은 180초 단위로 한다. 특정 네트워크에 대한 정보가 도달 불가능 경로로 들어오면 해당 정보를 바로 파기하지 않고 180초까지 대기한 후 더 좋은 정보가 들어오지 않으면 파기한다.-> 네트워크 트래픽이 많이 발생하고, 토폴로지 변화에 대한 적응이 느리다.-> 이웃하는 라우터로부터 경로 정보를 받으면 자신의 정보와 비교해 더 좋은 정보가 있으면 받아들이고 좋지 않은 정보는 폐기한다.-> 경로 정보에는 Subnet Mask값이 포함 되지 않는다.(Classful)-> Natural Mask를 기준으로 작성, 전송한다.(Automatic Summarization)※ Classful : Subnet Mask를 제외한, 즉 IP에서 첫 옥텟의 비트로 알 수 있는 클래스 정보에 따른 Default Subnet을 갖는 것을 말한다.② RIPv2(Routing Information Protocol version 2) - DVA-> RIPv1과 동일한 기본 알고리즘을 사용하면서 단점을 보완한 프로토콜.-> 인증 Mechanism을 제공하고, VLSM을 사용할 수 있도록 보완하였으며, 자동 요약은 설정할 수도 해제할 수도 있다.(Classless)-> Multi-casting(224.0.0.9)을 사용하여 라우팅 정보를 전달한다.-> 네트워크의 최대 크기에 대한 홉 제한이 여전히 남아있다.※ Classless : Route Advertisement 시 Subnet Mask 정보를 포함한다.※ RIP의 문제점 및 해결법 - > 별도 Hand_Out 참고③ IGRP(Interior Gateway Routing Protocol) - DVA-> 표준 프로토콜이 아닌 시스코에서 만들어낸 프로토콜이며, 시스코 라우터에서만 사용이 가능하다.-> Hop Count만이 아닌, Bandwidth, Delay, Reliability, Load, MTU 등을 갖고 최적의 경로를 참고한다.-> VLSM을 지원하지 못한다.-> IOS 12.2 이후로는 지원을 하지 않는다.④ EIGRP(Enhanced Interior Gateway Routing Protocol) - DVA-> IGRP의 기능을 향상 시킨 라우팅 프로토콜이며, Classless의 속성을 가진다.
논리회로(정 연 모 교수님) / 제출일 : 2012. 09. 25.Homework #1 /=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-① 문제 정의 : 다음의 식을 1의 보수, 2의 보수, 9의 보수, 10의 보수로 해결하시오. / (4) p.26 연습문제 풀이 / (5) CRC Code.(1) 5 - 13(2) 13 - 5(3) - 13 - 5--------------------------------------------------------------------------------------------------------------------------------------------------------② 문제 해결.(1) 5 - 13① 1의 보수☞ 감수의 1의 보수를 구하여 그 수를 피감수에 더한다. ≫ 0101(5)0101≫≫-1101(13) +0010-1000(-8)0111 ∴ -1000(-8)☞ 가중치가 제일 큰 자리에서 자리올림 수가 생기지 않으면 결과를 1의 보수로 취한 후에 (-)부호를 붙인다.~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~② 2의 보수☞ 감수의 2의 보수를 구하여 그 수를 피감수에 더한다. ≫ 0101(5)0101 0111≫-1101(13) +0011 +0001-1000(-8)1000 ∴ -1000(-8)☞ 자리올림 수가 생기지 않으면 결과를 2의 보수로 취한 후에 (-)부호를 붙인다.~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~③ 9의 보수☞ 감수의 9의 보수를 구하여 그 수를 피감수에 더한다. ≫ 5 5≫≫- 13 + 86-8 91 ∴ -8☞ 가중치가 제일 큰 자리에서 자리올림 수가 생기지 않으면 결과를 9의 보수로 취한 후에 (-)부호를 붙인다.~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~④ 10의 보수☞ 감수의 10의 보수를 구하여 그 수를 피감수에 더한다. ≫ 5 5 7≫- 13 + 87 + 1-8 92 ∴ -8☞ 자리올림 수가 생기지 않으면 결과를 10의 보수로 취한 후에 (-)부호를 붙인다.~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~(2) 13 - 5① 1의 보수☞ 감수의 1의 보수를 구하여 그 수를 피감수에 더한다. ≫ 1101(13)1101 0111≫≫-0101(5) +1010 + 00011000(8) 10111 ∴ 1000(8)☞ 가중치가 제일 큰 자리에서 자리올림 수가 생기면 결과에 가중치가 제일 낮은 자리에 1을 더한다.~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~② 2의 보수☞ 감수의 2의 보수를 구하여 그 수를 피감수에 더한다. ≫ 1101(13)1101≫≫≫≫-0101(5) +10111000(8) 11000 ∴ 1000(8)☞ 가중치가 제일 큰 자리에서 자리올림 수가 생기면 그 자리올림 수를 무시한다.~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~③ 9의 보수☞ 감수의 9의 보수를 구하여 그 수를 피감수에 더한다. ≫ 13 13 7≫≫- 5 + 94 + 18 107 ∴ 8☞ 가중치가 제일 큰 자리에서 자리올림 수가 생기면 그 수를 결과의 가중치가 제일 낮은 자리에 더한다.④ 10의 보수☞ 감수의 10의 보수를 구하여 그 수를 피감수에 더한다. ≫ 13 13≫≫- 5 + 95 8 108 ∴ 8☞ 가중치가 제일 큰 자리에서 자리올림 수가 생기면 그 자리올림 수를 무시한다.~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~(3) - 13 ? 5 (부호화 수 이용)① 1의 보수☞ 피감수를 6bit의 부호화 수로 변환한다. ≫-13 110011≫☞ 감수를 6bit의 1의 부호화 수로 변환하여 더한다.- 5+ 111010☞ 자리올림 수가 생기면 그 수를 결과의 가중치가 -18 1101101제일 낮은 자리에 더한다. +1101110(-18)~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~② 2의 보수☞ 피감수를 6bit의 부호화 수로 변환한다. ≫-13 110011≫☞ 감수를 6bit의 2의 부호화 수로 변환하여 더한다.- 5+ 111011☞ 자리올림 수가 생기면 그 수를 무시한다. -18 1101110 ∴ 101110(-18)~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~③ 9의 보수☞ 피감수는 10의 보수를 구하고 ≫ -13 87 181≫≫≫감수는 9의 보수를 구하여 그 수를 피감수에 더한다.- 5 + 94 + 1-18 181 82 ∴ -18`☞ 자리올림 수가 생기면 그 수를 결과의 가중치가 제일 낮은 자리에 더하고 변환 결과에 (-)부호를 붙인다.~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~④ 10의 보수☞ 피감수는 10의 보수를 구하고 ≫ -13 87≫≫감수는 10의 보수를 구하여 그 수를 피감수에 더한다.- 5 + 95-18 182 82 ∴ -18`☞ 자리올림 수가 생기면 그 수를 무시한다.~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~(4) p.26 연습문제 풀이17**************************0①1) 347을 2진수로 변환하면 2347∴ 101011011{} _{(2)}2) 347을 16진수로 변환하면5111211616 347∴ 15B{} _{(16)}②1) 01011112) *************14 *************25 1000100 68 -> 결과 값이 4처럼 보이지만, Overflow.③10010101 / 011100111) 무부호화 2진수 : 149 / 1152) 부호화 2진수 : -107 / +1153) BCD(8421 코드) : 95 / 73④ 100 110 1111) 1100 -42) 1010 -63) 0101 +51101 -3 0111 +7 0011 +3(())1001 -7 (1)0001 +1 (0)1000 부호화 수는 +8 불가(Overflow.)⑤1) 1101 - 11002) 1010 - 0110a) 13 - 12 = 1a) 10 - 6 = 4b) - 3 - ( - 4) = + 1b) - 6 - ( + 6) = Overflow.~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~(5) CRC Code. : CRC(cyclic redundancy check)는 네트워크 등을 통하여 데이터를 전송할 때 전송된 데이터에 오류가 있는지를 확인하기 위한 체크 값을 결정하는 방식을 말한다. 데이터를 전송하기 전에 주어진 데이터의 값에 따라 CRC 값을 계산하여 데이터에 붙여 전송하고, 데이터 전송이 끝난 후 받은 데이터의 값으로 다시 CRC 값을 계산하게 된다. 이어서 두 값을 비교하고, 이 두 값이 다르면 데이터 전송 과정에서 잡음 등에 의해 오류가 덧붙여 전송된 것임을 알 수 있다. CRC는 이진법 기반의 하드웨어에서 구현하기 쉽고, 데이터 전송 과정에서 발생하는 흔한 오류들을 검출하는 데 탁월하다. 하지만 CRC의 구조 때문에 의도적으로 주어진 CRC 값을 갖는 다른 데이터를 만들기가 쉽고, 따라서 데이터의 무결성을 검사하는 데는 사용될 수 없다. 이런 용도로는 MD5 등의 함수들이 사용된다.CRC는 가환환(commutative ring)의 나눗셈에 기반 한다. 여기서 쓰이는 환은 법 2 (modulo 2) 정수에서 정의된 다항식의 환이다. 쉽게 말하면, 이는 한 비트의 계수를 갖는 다항식의 집합이고, 이 다항식들 간의 사칙연산은 다시 계수들을 가장 아래 비트만 따도록 정의하여 1비트 계수의 다항식으로 표현하도록 정의된다.예를 들면:위 식에서 2는 이진수로 10이고, 따라서 정의에 의해서 가장 아랫자리 수(또는, 가장 아래 비트)인 0을 취하고 그 이상의 자릿수는 버린다. 다음은 곱셈의 예이다:더하기와 곱하기 말고 나누기도 정의할 수 있다. 예를 들어, x3 + x2 + x 를 x + 1 로 나눈다고 해 보자.나눗셈의 몫은 x2 + 1 이고 나머지는 -1 이고, -1은 홀수이기 때문에 1이 된다. 모든 데이터 비트 스트림은 이러한 다항식의 계수로 상상할 수 있다. 즉, 101 은 0번 자리가 1, 1번 자리가 0, 2번 자리가 1이므로, 다항식 에 해당한다고 볼 수 있다. CRC 값은, 정해진 특정 다항식으로 데이터 스트링으로 주어진 다항식을 나누어 그 나머지를 나타내는 특정 길이의 비트 스트링이 된다. 이 나머지를 구하는 간단하고 빠른 알고리즘은 잘 알려져 있다. CRC는 종종 체크 섬(checksum)으로 불리는데, 엄밀히 말하면 나눗셈을 통해 얻어지는 CRC 값에는 옳지 않은 이름이다.