Path

OSPF (Open Shortest Path First)

개념- 1980년대 중반, RIP의 한계 발생 (대규모의 이질적인 네트워크 사이에서)- IETF (Internet Engineering Task Force)에서는 SPF 알고리즘에 기반을 하고 인터넷에 적용하기 위해 IP 네트워크용 알고리즘 개발- RFC 1247 (OSPF 표준)- RFC 2328에 정의된 OSPFv2가 나오게 됨으로써 현재는 TCP/IP 환경에서 가장 많이 사용하고 있는 라우팅 프로토콜 1) OSPF의 라우팅 계위- OSPF는 계위(hierarchy) 구조를 취함 2) OSPF의 동작처음 부팅시, HELLO 패킷의 교환을 통해 이웃한 라우터를 서로 인식 (이를 통해, 여러개의 라우터 중에서, 그 네트워크를 대표하여 경로 정보의 생성 및 분배 책임을 지는 지명(Desigated) 라우터..

가중치 그래프와 임계 경로(Critical Path)

가중치 그래프 Weighted Graph 숫자로 된 가중치를 각 간선에 부여하여 가중치 그래프(weighted graph)로 확장할 수 있다. 이는 비가중치 그래프를 일반화한 것인데, 비가중치 그래프는 모든 간선의 가중치가 동일해서 생략한 가중치 그래프이고 더 많은 정보를 표현할 수 있어서 유용하다. 그래프가 도로망을 나타낸다면 가중치는 거리 또는 두 지점 사이를 여행하는데 걸리는 시간일 수 있다. 가중치 그래프는 비가중치 그래프와 유사하게 표현할 수 있다. 인접 행렬로 나타낸다면, 가중치 그래프의 인접 행렬은 엔트리로 간선들의 가중치를 갖거나 연결되지 않은 엔트리들에 대해서는 특수한 값을 갖는다. 아래는 위 그래프를 인접행렬로 표현한 것이다. 이 인접행렬에서는 연결된 간선이 없을 때는 특수 값으로 \i..