분류 전체보기
-
[백준] 2805 - 나무 자르기Algorithm 문제 2019. 6. 26. 16:31
https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 문제 상근이는 나무 M미터가 필요하다. 근처에 나무를 구입할 곳이 모두 망해버렸기 때문에, 정부에 벌목 허가를 요청했다. 정부는 상근이네 집 근처의 나무 한 줄에 대한 벌목 허가를 내주었고, 상근이는 새로 구입한 목재절단기을 이용해서 나무를 구할것이다. 목재절단기는 다음과 같이 동작한다. 먼저, 상근이는 절단기에 높이 H를 지정해야 한다. 높이를 지정하면 톱날이 땅으로부터 H미터 위로 올라간다. 그 다음, 한 줄에 연속해있는 나무를 모두 절단해버린다. 따 www.acmicpc.net INPUT의 개수가 1,000,000 개로 모든 높이에서 잘라 볼 경우 O(NM) 의 시간 복잡도가 소요되어 시간초과가 발생할 것이다..
-
5.3 intra-AS protocolComputer Networking 2018. 12. 17. 03:15
1. Making routin scalable - 5.2 절에서 네트워크는 연결된 라우터의 집합으로 간주됨- 모든 라우터가 동일한 알고리즘을 사용한다는 가정 및 간소화 - 확장 : 수십억개의 라우터에서 경로 연산의 오버헤드 감소 필요 - 관리 자치권(administrative autonomy) : 조직이 자신이 원하는 대로 자신의 네트워크를 운영 ☞ 라우터들을 AS(autonomous system, 자치 시스템)으로 집합화하여 해결 2. Interconnected ASes - forwarding table은 inter-AS routing algorithm 과 intra-AS routing algorithm에 의해 결정된다.- intra-AS routing이 AS 내부 경로 탐색, 외부는 intra와 in..
-
5.2 Routing protocolsComputer Networking 2018. 12. 17. 00:27
1. link-state routin algorithm- Dijkstra's algorithmD(v) = min(D(v), D(w) + c(w, v))O(n^2) --> O(nlogn) 까지도 효율 향상 가능 ※oscillations possible- 상기의 알고리즘은 진동 문제를 발생시킬 수 있다.- 혼잡을 피하기 위해 특정 상황에 한 경로로 트래픽이 몰리면 다음 상황에는 다른 경로로 변경. 이 작동이 반복됨 2. Distance vector algorith- Bellman-Ford equation (dynamic programming)- d(xy) = cost of least-cost path from x to y=> d(xy) = min{c(x, v) + d(vy) (v는 x의 모든 이웃) - 각 ..
-
4.3 IP: Internet ProtocolComputer Networking 2018. 12. 15. 00:52
1. Internet network layer 1) routing protocols ( forwarding table) - path selection, RIP, OSPF, BGP2) IP protocol - addressing conventions, datagram format, packet handling conventions3) ICMP protocol - error reporting, router signaling 2. IP datagram format - ver : 4bit로 IP 프로토콜의 버전을 명시- head len : 실제 데이터 시작하는 곳- type of service- length : 헤더 + 데이터 길이- 인식자, 플래그, fragment offset : fragmentation /..
-
4.2 What's inside a routerComputer Networking 2018. 12. 14. 23:09
1. Router architecture overview 1) 입력 포트 : 라우터로 들어오는 입력 물리 링크의 종단, 검색(lookup) 함수 수행 (이는 입력 포트의 가장 우측 상자에서 발생), 도착한 패킷이 전달되기 위한 결정. 제어 패킷 전달 2) switching structure : 라우터의 입력 포트와 출력 포트를 연결. 3) 출력 포트 : 외부 링크로 패킷을 전송. 4) routing processor : 라우팅 프로토콜(4.6)을 수행, 라우팅 테이블과 연결 상태 정보 유지, 포워딩 테이블을 계산 ○ 입력 처리 - decentralized switching : queuing 지원, 최장 프리픽스 대응을 forwarding table에서 찾아 전송 최장 프리픽스 대응 ex) 11001000..
-
4.1 Network Layer 개요Computer Networking 2018. 12. 14. 19:41
1. 포워딩과 라우팅- Forwarding: 패킷이 라우터의 입력 링크에 도달했을 때 라우터는 그 패킷을 적절한 출력 링크로 이동시켜야 한다. - Routing: 송신자가 수신자에게 패킷 전송 시, 패킷의 경로를 결정해야 한다. - Per-router control plane - Logically centralized control plane 2. Network service model ○ 별개의 패킷에 대해- 보장된 전달- 제한 지연 이내의 보장된 전달 ○ 패킷 흐름에 대해- 송신 순서대로 패킷의 도착을 보장- 보장된 최소 대역폭- 보안
-
3.7 TCP congestion controlComputer Networking 2018. 12. 14. 02:42
○ TCP는 주로 종단간의 혼잡제어를 사용 - 연결에 트래픽을 보내는 전송률을 각 송신자가 제한- 송신자는 전송률(window size)를 loss 발생 시까지 증가시킨다. 1) TCP Slow Start- TCP 연결 시작 시, cwnd 값은 일반적으로 1MSS 로 초기화- 확인응답을 받을 때마다, 1MSS 만큼 증가 (1RTT 당 cwnd는 2배로 증가) 2) TCP Congestion Avoidance- 혼잡 발생 시의 절반으로 cwnd 값을 조정- 1RTT 동안, 1MSS 만큼 증가 3) Fast Recovery- 중복 ACK 받을 때마다 1MSS 씩 증가- timeout 발생 시, 임계값 절반, cwnd=1로 초기화- TCP의 권고사항이나 필수는 아님 ○ TCP throughput ○ 공평성 -..
-
3.6 혼잡제어의 원리Computer Networking 2018. 12. 14. 00:50
1. 혼잡의 원인과 비용 1) 2개의 송신자 + 무한 버퍼 라우터 - 라우터를 균등하게 나누어 사용- 라우터의 처리량과 동일한 양의 입력 전송률이 커지면, 큐잉 지연이 급격히 증가 2) 2개의 송신자 + 유한 버퍼 라우터 - 좌측 그래프는 network에서 손실이 발생할 경우, 재전송에 의한 비용- 우측 그래프는 손실되지 않았으나, 짧은 timeout에 의해 중복 세그먼트를 전송한 것에 의한 비용 3) 4개의 송신자 + 유한 버퍼 라우터 + 멀티홉 경로 - A->C의 트래픽 양이 매우 큰 경우, R2에 도달하는 트래픽 양이 A->C D 일 수 있다.- 제공 부하가 매우 크다면, 처리량이 0이 될 수 있다. 2. 혼잡제어 대한 접근법 ○ 종단간의 혼잡제어 - timeout, 3중 중복 확인 -> 윈도우 크..