The flooding search routing algorithm is an on-demand routing scheme, and does not require essentially any knowledge of network topology. Under low traffic conditions, it is one of the most robust routing algorithms that have high probability of finding a path if one exists, since multiple copies of search-message explore all possible paths to the destination. It has been implemented in networks where a robust routing algorithm is of prime concern; this includes some military networks with extreme Survivability requirements. But, it has a main drawback that it has heavy overload on the search-message in the signal channel.
This thesis proposes DSRA (Dynamic ＆ Survivable Routing Algorithm) that is a Preplanned routing scheme. Global network is separated into several overlapped sub-network. The central node optimally preplans the path for each o-d node pair in sub-network using the data from the network data base system. Each node is received several information about the path routing pattern from the central nodes in the overlapped sub-networks, and positively uses the path routing pattern information for the real-time call set-up. DSRA responses to the failures of network with a reactive restoration scheme, and has three restoration methods. First, call connection algorithm restores the failed o-d node pairs using alternate disjoint paths and connecting the selected alternate paths. Second, the flooding search routing algorithm is used for link restoration, both terminals of the failed link flood the failure message which has a search message function to the nodes in the network. Third, a failure-oriented rerouting algorithm is used for end-to-end restoration. This algorithm reroutes the failed o-d node pair's paths and updates the routing table. DSRA's main contributions are simplicity, low computational complexity and survivability. But it has a drawback that it requires integrated and perfect information about the network topology.
확산 탐색 알고리즘은 통화 요구에 의한 경로 선정 방법으로, 기본적으로 네트워크 구조에 관한 정보를 요구하지 않는다. 낮은 통화 빈도하에서, 이 알고리즘은 다중의 탐색 정보가 목적지에 대한 모든 경로를 탐색하기 때문에 경로가 존재하기만 한다면 경로를 구할 수 있는 확률이 높은 강력한 경로 선정알고리즘으로 알려져 있다. 이 알고리즘은 군사 통신망과 같이 높은 생존성이 요구되는 통신망 등에서 강력한 경로 선정 알고리즘으로 응용되어 왔다. 그러나 이 알고리즘은 통제 회선에서의 통제 신호의 과부하가 발생된다는 주요 단점이 있다. 본 연구에서는 사전 경로 선정 방법인 동적 및 생존성 있는 경로 선정 알고리즘 (DSRA)을 제안한다. 전체 통신망을 서로 중복되게 수개의 하위 통신망으로 나누어지며, 하위 통신망 내의 중앙 노드는 통신망 데이터 베이스 시스템으로부터 데이터를 받아 최적으로 각 발신-목적 노드 쌍에 대한 경로를 최적으로 사전에 계획한다. 통신망내의 각 노드는 중첩된 하위 통신망의 중앙 노드로부터 수개의 경로 선정 패턴 정보를 받아, 능동적으로 실시간 호 연결에 사용한다. DSRA는 통신망의 오류에 반응적 보국 방법으로 대응하며, 세가지 복구 방법을 가지고 있다. 첫째, 호 연결 알고리즘이 오류 발신-목적 노드 쌍의 경로에 대하여 독립된(disjoint) 복구 경로와 선정된 경로간의 연결을 통하여 복구한다. 둘째, 확산 탐색 알고리즘을 이용하여, 오류 링크의 양단말은 오류 메시지에 복구 경로 탐색 신호의 기능을 가지게 하여 링크 복구를 한다. 셋째, 오류 지향 재 경로 선정알고리즘을 통하여, 오류 발신-목적 노드 쌍들의 경로를 재선정하고, 경로 선정표를 갱신하여 종단 대 종단 복구를 한다. DSRA의 주요 기여는 알고리즘의 단순화, 낮은 계산 복잡성, 그리고 생존성의 보장에 있다. 그러나 이것은 통신망에 대한 통합되고 완벽한 통신망 정보가 요구된다는 단점이 있다.
