KR101465498B1 - 하이브리드 광학 네트워크 온 칩의 적응적 라우팅 장치 및 방법, 이를 이용한 하이브리드 광학 네트워크 온 칩 시스템 - Google Patents

Abstract

하이브리드 광학 네트워크 온 칩(HONoC)에서 복수의 처리 소자(PE) 별로 연결된 라우팅 장치를 통한 적응적 라우팅 시, 전기적 링크를 통해 제 1 라우팅 장치로부터 컨트롤 패킷을 수신하고, 컨트롤 패킷의 유형을 판단하고, 유형을 판단한 결과 경로 설정 패킷인 경우, 경로 설정 패킷에 기초하여 제 1 라우팅 장치와 인접한 라우팅 장치 중 기설정된 목적지를 향한 방향의 제 2 라우팅 장치를 결정하고, 제 2 라우팅 장치의 사용 상태를 확인하여, 사용 상태에 따라 경로 설정 패킷에 대한 롤백 처리 여부를 결정하고, 경로 설정 패킷에 대한 롤백 처리가 결정되면, 제 1 라우팅 장치로 경로 설정 패킷을 롤백 시키되, 롤백시킨 경로 설정 패킷은 제 1 라우팅 장치에서 재결정된 우회 경로 상의 제 3 라우팅 장치로 전송된다.

Description

하이브리드 광학 네트워크 온 칩의 적응적 라우팅 장치 및 방법, 이를 이용한 하이브리드 광학 네트워크 온 칩 시스템{APPARATUS AND METHOD FOR ADAPTIVE ROUTING OF HYBRID OPTICAL NETWORKS ON CHIP AND HYBRID OPTICAL NETWORKS ON CHIP SYSTEM USING THE SAME}

본 발명은 하이브리드 광학 네트워크-온-칩(Hybrid Optical Networks-On-Chip, HONoC) 환경에서 각 라우팅 장치의 상태에 따라 라우팅을 진행하는 적응적 라우팅 장치 및 방법과, 이를 이용한 HONoC시스템에 관한 것이다.

싱글 코어 프로세서의 전력 효율 대비 성능의 한계로 인해 다중 코어를 이용한 다중 프로세서 시스템-온-칩(Multi-Processor System-on-Chip, MPSoC)이 개발되었다. 이러한 다중 프로세서 시스템-온-칩에서는 기존의 버스(bus) 구조를 적용할 경우 병목의 문제가 발생되어 전체 시스템 성능 향상이 저하될 수 있다. 이로 인해, 수백개 이상의 코어와 IP(Intellectual Property)가 집적된 첨단 SoC 구조에 온-칩 네트워크(On-chip Network, OCN) 개념을 적용한 네트워크-온-칩(Network-on-Chip, NoC)이 등장하였다.

NoC는 토폴로지와 프로토콜 관점의 구조적 변화이므로, 기존 반도체 공정/소자 기술의 한계에 대응하기 위해서는 추가적으로 물리적 연결 매체(Interconnection medium)까지 고려한 접근 방식이 요구된다. 이에 따라, 기존 NoC에서의 전기적 상호 연결(Electrical Interconnect, EI)에 의한 전력 소모 및 지연 시간 문제를 광학적 상호 연결(Optical Interconnect, OI)을 통해 해결하는 하이브리드 광학적 네트워크-온-칩(Hybrid Optical NoC, HONoC)이 등장하였다.

예를 들어, 메시 토폴로지에서 OI를 통해 대용량 패이로드(payload) 데이터를 전송하고, EI를 통해 컨트롤 패킷 및 경로 설정 패킷을 전송하도록 하는 방법 등이 제안되었다. 이러한, HONoC에서는 광 신호를 패킷 스위칭(Packet Switching) 방식으로 라우팅하게 되면 각 라우터에서 광신호의 전기 신호로의 변환과 이를 통한 목적지 판별 과정을 거쳐야 하므로, 지연 시간(latency)이 오히려 EI기반 NoC보다 증가하기 때문에 EI를 통해 OI의 경로를 설정하게 하는 서킷 스위칭(Circuit Switching) 네트워크로 구성한다.

한편, 광학적 라우팅의 중요성으로 인하여 라우터를 최적화하려는 연구들이 많이 진행되고 있다. 그런데, 기존의 HONoC의 라우터에 관한 연구에서는 X-Y 라우팅등과 같은 단순한 라우팅 방식을 적용함으로써, 서로 다른 데이터가 동일한 경로를 사용하려 할 때 경로를 점령하지 못한 데이터는 다른 데이터가 전송이 종료될 때까지 기다려야 하는 블로킹(blocking) 문제가 발생한다. 이에 따라 HONoC 상의 라우터들에 대해 레이튼시(latency)가 공평하게 보장되지 못하는 문제가 발생하게 된다. 이에 따라, HONoC의 구조적인 특성에 적합하게 설계되어 효율적인 경로 설정을 수행할 수 있는 장치 및 방법이 필요하다.

이와 관련하여, 대한민국등록특허 제714073호(발명의 명칭: 통신 자원의 충돌이 없는 온칩 네트워크 자동 생성 방법)에서는, SoC 설계에 있어서, 온칩 네트워크를 구성하는 모듈들간의 통신량에 대한 트래픽 그래프 및 통신 스케줄을 분석하여 각 통신 요구들 간의 경합이 없는 최적의 온칩 네트워크를 자동으로 생성하는 방법을 개시하고 있다.

하지만 이러한 기존의 연구들은 광학적 상호 연결(OI)의 적용을 통해 서킷 스위칭을 사용해야 하는HONoC 구조의 환경을 제대로 반영하지 못하여, HONoC 구조에서의 경로 충돌 제어에는 한계가 있었다.

전술한 종래 기술의 문제점을 해결하기 위해, 본 발명의 일 실시예는 HONoC 환경에서 라우팅 장치의 경로 설정 상태에 기초하여 효율적으로 우회 경로 설정을 처리하는 적응적 라우팅 장치 및 방법과 그에 따른 HONoC 시스템을 제공하고자 한다.

다만, 본 실시예가 이루고자 하는 기술적 과제는 상기된 바와 같은 기술적 과제로 한정되지 않으며, 또 다른 기술적 과제들이 존재할 수 있다.

상기와 같은 기술적 과제를 달성하기 위한 본 발명의 일 측면에 따른, 하이브리드 광학 네트워크 온 칩(Hybrid Optical Network-on-Chip, HONoC)에서 복수의 처리 소자(Processing Element, PE) 별로 연결된 라우팅 장치는, 전기적 링크를 통해 경로 설정을 위한 컨트롤 패킷을 수신하고, 상기 컨트롤 패킷을 기설정된 유형에 따라 분배하여 출력하는 패킷 분배 모듈; 상기 패킷 분배 모듈로부터 출력된 상기 컨트롤 패킷 중 경로 설정 패킷을 수신하면, 기설정된 목적지를 향한 방향으로 인접한 다음 라우팅 장치를 결정하고, 상기 다음 라우팅 장치의 사용 상태에 따라 상기 경로 설정 패킷에 대한 롤백(rollback) 처리 여부를 결정하는 경로 설정 처리 모듈; 및 상기 경로 설정 처리 모듈에 의해 상기 경로 설정 패킷에 대한 롤백 처리가 결정되면, 상기 경로 설정 패킷이 입력된 이전 라우팅 장치로 상기 경로 설정 패킷을 롤백시키는 롤백 처리 모듈을 포함하되, 상기 이전 라우팅 장치로 롤백시킨 상기 경로 설정 패킷은, 상기 이전 라우팅 장치가 재결정한 우회 경로 상의 다른 라우팅 장치로 전송된다.

그리고, 본 발명의 다른 측면에 따른, 하이브리드 광학 네트워크 온 칩(Hybrid Optical Network-on-Chip, HONoC)에서 복수의 처리 소자(Processing Element, PE) 별로 연결된 라우팅 장치를 통한 적응적 라우팅 방법은, (a) 전기적 링크를 통해 제 1 라우팅 장치로부터 컨트롤 패킷을 수신하는 단계; (b) 상기 컨트롤 패킷의 유형을 판단하는 단계; (c) 상기 유형을 판단한 결과 경로 설정 패킷인 경우, 상기 경로 설정 패킷에 기초하여 상기 제 1 라우팅 장치와 인접한 라우팅 장치 중 기설정된 목적지를 향한 방향의 제 2 라우팅 장치를 결정하는 단계; (d) 상기 제 2 라우팅 장치의 사용 상태를 확인하여, 상기 사용 상태에 따라 상기 경로 설정 패킷에 대한 롤백(rollback) 처리 여부를 결정하는 단계; 및 (e) 상기 경로 설정 패킷에 대한 롤백 처리가 결정되면, 상기 제 1 라우팅 장치로 상기 경로 설정 패킷을 롤백 시키는 단계를 포함하되, 상기 롤백시킨 경로 설정 패킷은 상기 제 1 라우팅 장치에서 재결정된 우회 경로 상의 제 3 라우팅 장치로 전송된다.

또한, 본 발명의 또 다른 측면에 따른, 하이브리드 광학 네트워크 온 칩(Hybrid Optical Networks-on-Chip) 시스템은, 복수의 처리 소자(Processing Element, PE); 및 상기 PE 별로 매칭되며, 광학적 링크를 통해 상기 PE 간 데이터의 전송을 위한 서킷 스위칭을 처리하고, 전기적 링크를 통해 상기 PE 간 경로 설정을 위한 패킷 스위칭을 처리하는 복수의 라우팅 장치를 포함하되, 상기 라우팅 장치는, 상기 전기적 링크를 통해 경로 설정을 위한 컨트롤 패킷을 수신하여 기설정된 유형에 따라 분배하여 출력하고, 상기 컨트롤 패킷 중 경로 설정 패킷을 수신하면 기설정된 목적지를 향한 방향으로 인접한 다음 라우팅 장치를 결정하고, 상기 다음 라우팅 장치가 사용 불가능한 상태이면 상기 경로 설정 패킷이 입력된 이전 라우팅 장치로 상기 경로 설정 패킷을 롤백(rollback) 처리하되, 상기 이전 라우팅 장치로 롤백 처리된 상기 경로 설정 패킷은, 상기 이전 라우팅 장치가 재결정한 우회 경로 상의 다른 라우팅 장치로 전송된다.

전술한 본 발명의 과제 해결 수단 중 어느 하나에 의하면, HONoC 상에서 데이터 송수신을 위한 경로 설정 시, 경로 진행 방향이 블로킹된 경우 블로킹 이전의 라우팅 장치로 되돌아가 경로를 재탐색함으로써 신속하게 경로를 우회시킬 수 있다. 이에 따라, 동일 경로를 사용하고자하는 데이터 통신들에 대해서 각각 적합한 우회 경로를 제공함으로써, 통신 속도를 높일 수 있는 효과가 있다.

그리고, 본 발명의 과제 해결 수단 중 어느 하나에 의하면, 출발지로부터 목적지까지의 최단 거리 경로 내에서 우회 경로를 설정함으로써, 경로 우회 시에도 최적의 경로 설정을 제공할 수 있는 효과가 있다.

또한, 본 발명의 과제 해결 수단 중 어느 하나에 의하면, 둘 이상의 통신에 의해 동일 방향으로의 경로 설정 시도가 동시에 발생된 경우, 각 통신의 경로 설정 재시도에 대해 차등적인 지연 시간을 적용함으로써 동시 발생된 통신들에 대한 안정적인 병렬 통신이 가능한 효과가 있다.

또한, 본 발명의 과제 해결 수단 중 어느 하나에 의하면, 경로 설정 완료 후 광학적 네트워크를 통한 데이터 전송과 동시에(또는 빠른 시간 내에) 전기적 네트워크를 통한 경로 해제를 수행함으로써, 신속하게 설정된 경로를 해제시킬 수 있어 통신 효율을 높일 수 있다.

도 1은 본 발명의 일 실시예에 따른 하이브리드 광학 네트워크 온 칩 시스템의 구성을 나타내는 도면이다.
도 2는 본 발명의 일 실시예에 따른 라우팅 장치의 구성을 나타낸 블록도이다.
도 3은 본 발명의 일 실시예에 따른 컨트롤 패킷의 유형 별 구조를 설명하기 위한 도면이다.
도 4는 본 발명의 일 실시예에 따른 적응적 라우팅 방식에서 라우팅 진행 방향을 결정하는 절차를 설명하기 위한 순서도이다.
도 5는 본 발명의 일 실시예에 따른 적응적 라우팅 방식에서 다음 라우팅 장치에 대한 경로 설정 예측 처리 절차를 설명하기 위한 순서도이다.
도 6은 본 발명의 일 실시예에 따른 적응적 라우팅 수행 결과의 일례를 나타낸 도면이다.
도 7은 본 발명의 일 실시예에서 발생될 수 있는 중복 경로 탐색 과정의 일례를 나타낸 도면이다.
도 8은 본 발명의 일 실시예에 따른 적응적 라우팅 방식에서 중복 경로를 제외하는 절차를 설명하기 위한 순서도이다.
도 9는 본 발명의 일 실시예에 따른 경로 설정 지연 방식을 설명하기 위한 경로 설정 동시 발생 상태의 일례를 나타낸 도면이다.
도 10은 본 발명의 일 실시예에 따른 경로 설정 재시도에 적용될 지연 시간의 산출 방식을 설명하기 위한 도면이다.
도 11은 본 발명의 일 실시예에 따른 적응적 라우팅 방법을 설명하기 위한 순서도이다.

아래에서는 첨부한 도면을 참조하여 본 발명이 속하는 기술 분야에서 통상의 지식을 가진 자가 용이하게 실시할 수 있도록 본 발명의 실시예를 상세히 설명한다. 그러나 본 발명은 여러 가지 상이한 형태로 구현될 수 있으며 여기에서 설명하는 실시예에 한정되지 않는다. 그리고 도면에서 본 발명을 명확하게 설명하기 위해서 설명과 관계없는 부분은 생략하였으며, 명세서 전체를 통하여 유사한 부분에 대해서는 유사한 도면 부호를 붙였다.

명세서 전체에서, 어떤 부분이 다른 부분과 "연결"되어 있다고 할 때, 이는 "직접적으로 연결"되어 있는 경우뿐 아니라, 그 중간에 다른 소자를 사이에 두고 "전기적으로 연결"되어 있는 경우도 포함한다. 또한 어떤 부분이 어떤 구성요소를 "포함"한다고 할 때, 이는 특별히 반대되는 기재가 없는 한 다른 구성요소를 제외하는 것이 아니라 다른 구성요소를 더 포함할 수 있는 것을 의미한다.

도 1은 본 발명의 일 실시예에 따른 하이브리드 광학 네트워크 온 칩 시스템의 구성을 나타내는 도면이다.

도 1에 도시한 바와 같이, 본 발명의 일 실시예에 따른 하이브리 광학 네트워크 온 칩(Hybrid Optical NoC, HONoC) 시스템(10)은 복수의 처리 소자(Processing Element, PE)(100), 각 PE(100)와 매칭되어 연결된 복수의 라우터(200), 및 각 라우터(200) 간에 광학적 경로를 형성하는 광학적 링크(300), 각 라우터(200) 간에 전기적 경로를 형성하는 전기적 링크(400)를 포함하여 구성된다.

참고로, 도 1에서는 본 발명의 일 실시예에 따른 HONoC 시스템(10)이 메시 네트워크 토폴로지 형태의 HONoC로 구성된 것을 나타내었으며, 본 발명의 실시예에 따른HONoC의 형태는 다양한 종류의 네트워크 토폴로지 형태로 설정될 수 있다.

처리 소자(PE)(100)는 HONoC 상에서 데이터를 처리하는 소자이다. 예를 들어, PE(100)는 애플리케이션과 같은 프로그램에 의한 태스크(task)가 매핑되어, 해당 태스크에 따른 데이터를 처리할 수 있다.

라우터(200)는 PE(100)에서의 데이터 처리를 위해, HONoC 상의 PE(100) 간에 경로를 설정(즉, 라우팅)하여 데이터가 송수신되도록 한다. 이때, 출발지 라우터(200)는 자신과 연결된 PE(100)로부터 발생된 데이터를 전달받아 목적지 라우터(200) 측으로 전송하고, 목적지 라우터(200)는수신된 데이터(즉, 출발지 라우터가 전송한 데이터)를 자신과 연결된 PE(100)로 전달한다.

특히, 본 발명의 일 실시예에 따른 HONoC 시스템(10)에서는 각 라우터(200)가 기설정된 라우팅 절차를 수행하여 출발지로부터 목적지까지의 경로를 설정한다. 이때, 각 라우터(200)가 수행하는 기설정된 라우팅 방식은 HONoC 상에서 다른 라우터들의 현재 상태에 따라 경로를 설정할 다음 라우터를 결정하는 방식(이하, '적응적 라우팅'이라고함)이다.

구체적으로, 적응적 라우팅에 따르면, 출발지로부터 목적지까지의 경로 상에 위치한 라우터(200)들의 경로 설정 상태를 실시간으로 판단한다. 이때, 적응적 라우팅에서는, 상기 경로 상에 경로 설정이 불가능한 상태인 라우터가 존재하는 경우, 현재 라우터의 위치에 인접하며 경로 설정이 가능한 상태의 다른 라우터로 경로를 우회시킨다.

본 발명의 일 실시예에 따른 라우터(200)의 적응적 라우팅 동작에 대해서는 하기 도 2 내지 도 8을 참조하여 상세히 설명하도록 한다.

한편, 본 발명의 일 실시예에 따른 라우터(200)는 광학 라우터 및 전기 라우터의 동작을 함께 수행하는 혼합형(hybrid) 라우터로서, HONoC 상에는 라우터(200)들의 광학적/전기적 연결을 통해 광학적 네트워크와 전기적 네트워크가 형성된다. 이때, 라우터(200)는 서킷 스위칭을 통해 광학적 네트워크를 제어하고, 패킷 스위칭을 통해 전기적 네트워크를 제어한다.

구체적으로, 광학적 네트워크는 라우터(200) 내 광학적 라우터와 광학적 링크(예를 들어, 도파관(waveguide))(300)로 구성된다. 광학적 링크(300)는 광학적 상호 연결(Optical Interconnect, OI)로서, 'PE(100)와 라우터(200)' 또는 '라우터(200)와 라우터(200)' 사이를 광학적으로 연결한다. 예를 들어, 출발지 라우터(source router)와 목적지 라우터(destination router) 간에 경로가 설정되면, 설정된 경로 상에 위치한 라우터(200)들은 각각 광학적 링크(300)를 통해 데이터(즉, 페이로드(payload))를 광신호로 송수신한다. 이때, 광학적 라우터는 마이크로공진기(micro-resonator)를 포함하여 구성될 수 있으며, 마이크로공진기의 온/오프(on/off)에 따라 광학적 링크의 사용 여부를 선택할 수 있다. 그리고, 광학적 라우터는 사용되도록 선택된 광학적 링크를 통해 광신호(즉, 데이터)를 목적지(destination) 측으로 전송하고, 목적지의 광학적 라우터는 사용하도록 선택된 광학적 링크를 통해 광신호를 수신한다.

전기적 네트워크는 라우터(200) 내 전기적 라우터와 전기적 링크(400)로 구성된다. 전기적 링크(400)는 전기적 상호 연결(Electrical Interconnect, EI)로서, 라우터(200)와 라우터(200) 사이를 전기적으로 연결하여 라우터(200) 간에 전기 신호를 통신할 수 있도록 한다. 예를 들어, 전기적 라우터는 출발지 라우터와 목적지 라우터 간에 경로를 설정하기 위한 패킷(이하, '컨트롤 패킷'이라고 함)을 전기적 링크(400)를 통해 전기 신호로 통신하도록 한다. 그리고, 전기적 라우터는 라우터(200) 내 광학적 라우터를 제어하여 광신호(즉, 데이터)가 송수신되도록 한다. 이때, 전기적 라우터는 광학적 라우터와 통신하여 광학적 네트워크를 통해 광원(즉, 데이터)이 송수신되도록 마이크로공진기를 제어할 수 있다. 또한, 전기적 라우터는 라우터(200) 내 전기적/광학적 경로의 사용 여부에 대한 정보를 다른 라우터로 제공할 수 있다.

이하, 도 2 내지 도 8을 참조하여 본 발명의 일 실시예에 따른 라우터(이하, '라우팅 장치'라고 함)(200)에 대해서 상세히 설명하도록 한다.

우선, 본 발명의 일 실시예에 따른 HONoC 시스템(10) 상에서 복수의 라우팅 장치(200)를 통해 PE(100) 간에 데이터를 송수신하는 과정을 설명하도록 한다.

먼저, 출발지 PE에서 전송할 데이터가 발생되면, 출발지 라우팅 장치는 전기적 링크를 통해 목적지 라우팅 장치 측으로 경로 설정을 위한 컨트롤 패킷을 전송한다.

그러면, 출발지 라우팅 장치로부터 목적지 라우팅 장치까지의 경로 상에 위치한 라우팅 장치는 기설정된 적응적 라우팅 알고리즘에 따른 처리를 수행하여 컨트롤 패킷을 전달할 다른 라우팅 장치를 결정한다.

구체적으로, 적응적 라우팅 알고리즘에 따르면, 경로 설정 패킷을 수신한 라우팅 장치(이하, '현재 라우팅 장치'라고 지칭함)는 목적지 라우팅 장치를 향한 일방향으로 인접한 다른 라우팅 장치(이하, '다음 라우팅 장치'라고 함)의 경로 설정 상태를 확인한다. 그리고, 현재 라우팅 장치는 다음 라우팅 장치의 경로 설정 상태가 사용 가능한 상태이면 컨트롤 패킷을 전달하고, 다음 라우팅 장치의 경로 설정 상태가 사용 중인 상태이면 현재 라우팅 장치로 경로 설정 패킷을 전송하였던 라우팅 장치(이하, '이전 라우팅 장치'라고 지칭함)로 컨트롤 패킷을 복귀(즉, 롤백(rollback))시킨다. 그러면, 복귀된 컨트롤 패킷을 수신한 라우팅 장치는 목적지 라우팅 장치를 향한 진행 방향 중 상기 일방향과는 다른 방향으로 인접한 또 다른 라우팅 장치로 컨트롤 패킷을 재전송하여 경로를 우회시킨다. 이상에서와 같은 경로 설정 절차의 수행에 따라 HONoC 상의 라우팅 장치 중 복수의 라우팅 장치들은 순차적으로 컨트롤 패킷을 수신하며, 컨트롤 패킷을 성공적으로 수신한 라우팅 장치들을 통해 출발지로부터 목적지까지의 경로가 설정된다.

이처럼, 목적지 라우팅 장치까지 경로 설정용 컨트롤 패킷이 성공적으로 전송되면, 목적지 라우팅 장치는 경로 설정의 성공을 알리는 응답 컨트롤 패킷을 출발지 라우팅 장치로 전송하여 경로 설정을 완료한다.

그런 다음, 응답 컨트롤 패킷을 수신한 출발지 라우팅 장치는 목적지 라우팅 장치(결과적으로, 목적지 PE)까지 설정된 경로의 광학적 링크(300)를 통해 목적된 데이터 패킷(즉, 페이로드)을 전송한다.

마지막으로, 출발지 라우팅 장치로부터 광학적 링크(300)를 통해 데이터 패킷이 전송되면, 출발지 라우팅 장치는 경로 해제를 위한 컨트롤 패킷을 전기적 링크(400)를 통해 전송하여, 목적지 라우팅 장치까지 설정되어 있던 경로를 해제시킨다.

이하, 위에서 설명한 적응적 라우팅을 통해 데이터 송수신 처리를 수행하는 라우팅 장치(200)의 구성 및 동작에 대해 상세히 설명하도록 한다.

도 2는 본 발명의 일 실시예에 따른 라우팅 장치의 구성을 나타낸 블록도이다. 그리고, 도 3은 본 발명의 일 실시예에 따른 컨트롤 패킷의 유형 별 구조를 설명하기 위한 도면이다.

도 2에 도시한 바와 같이, 라우팅 장치(200)는 라우팅 처리부(210), 데이터 전송부(220), 데이터 수신부(230) 및 경로 해제 처리부(240)를 포함하여 구성된다.

이때, 도 2에서와 같이, 라우팅 처리부(210)는 패킷 분배 모듈(211), 경로 설정 처리 모듈(212), 롤백 처리 모듈(213), 캔슬 처리 모듈(214) 및 패킷 전송 처리 모듈(215)을 포함한다.

패킷 분배 모듈(211)은 전기적 링크(400)를 통해 다른 라우팅 장치(200)로부터 컨트롤 패킷을 수신하고, 수신된 컨트롤 패킷을 유형(type)에 따라 분류한다.

참고로, 컨트롤 패킷은 경로 설정을 위해 라우팅 장치(200) 간에 송수신되는 패킷으로서, 유형(type)에 따라 경로 설정 패킷(path setting packet), 롤백 패킷(rollback packet), 캔슬 패킷(cancel packet), 경로 응답 패킷(path ack packet) 및 경로 해제 패킷(path release packet)으로 구분할 수 있다.

구체적으로, 경로 설정 패킷은, 출발지 라우팅 장치부터 목적지 라우팅 장치까지의 복수의 경로 중 적어도 일경로 상에 위치한 라우팅 장치(200)에 경로 설정을 요청하는 패킷이다. 그리고, 롤백 패킷은, 경로 설정 패킷의 전송 시 목적지 라우팅 장치까지의 경로 상에서 다음 라우팅 장치로의 진행이 블로킹(blocking)된 경우, 경로 설정 패킷이 전송된 이전 라우팅 장치로 복귀(rollback)되는 패킷이다. 예를 들어, 컨트롤 패킷의 전송이 블로킹되는 경우는, 컨트롤 패킷을 전달하고자하는 라우팅 장치가 다른 경로 설정에 의해 사용되고 있거나, 컨트롤 패킷을 전달하고자 하는 라우팅 장치의 PE(100)가 사용되고 있는 경우일 수 있다. 그리고, 캔슬 패킷은, 경로 설정 시 목적지 라우팅 장치가 사용 중인 경우, 해당 경로에 대한 라우팅 동작이 취소되어(cancelling) 출발지 라우팅 장치로 복귀되는 패킷이다. 그리고, 경로 응답 패킷은, 출발지와 목적지 간에 경로 설정이 성공적으로 완료된 경우, 경로 설정이 완료되었음을 알리기 위해 목적지 라우팅 장치로부터 출발지 라우팅 장치로 전송되는 패킷이다. 또한, 경로 해제 패킷은 출발지 라우팅 장치로부터 목적지 라우팅 장치까지 데이터가 전송된 후 해당 경로를 해제시켜 다른 경로 설정이 가능하도록 하기 위한 패킷이다. 이때, 경로 해제 패킷은 경로 해제 시간 정보를 포함할 수 있으며, 출발지 라우팅 장치로부터 광학적 링크를 통한 데이터 전송 시작과 동시에 또는 데이터의 전송 직후에 순차적으로 전기적 링크를 통해 전송될 수 있다.

도 3의 (a)에는 경로 설정(path setting) 패킷 및 경로 응답(path ack) 패킷의 구조를 나타내었고, 도 3의 (b)에는 롤백(rollback) 패킷 및 캔슬(cancel) 패킷의 구조를 나타내었다. 또한, 도 3의 (c)에는 경로 해제(path release) 패킷의 구조를 나타내었다.

도 3의 (a)에서와 같이, 경로 설정(path setting) 패킷 및 경로 응답(path ack) 패킷은, 제 1 필드(P11)에 패킷 유형 정보(Packet type)가 저장되고, 제 2 필드(P12)에 출발지 정보(Source)가 저장되고, 제 3 필드(P13)에 목적지 정보(Destination)가 저장되고, 제 4 필드(P14)에는 롤백된 적이 있는 경로 설정 패킷에 대한 롤백 위치 정보(도 2에서는, 'Y-value'로 표시함)가 저장되어 있다. 이때, 롤백 위치 정보는 경로 설정 패킷이 롤백을 시작한 라우팅 장치의 위치 정보로서, 가장 최신의 정보가 저장된다.

그리고, 도 3의 (b)에서와 같이, 롤백(rollback) 패킷 및 캔슬(cancel) 패킷은 각각, 제 1 필드(P21)에 패킷 유형 정보(Packet type)가 저장된다.

또한, 도 3의 (c)에서와 같이, 경로 해제(path release) 패킷은 제 1 필드(P31)에 패킷 유형 정보(Packet type)가 저장되고, 제 2 필드(P32)에 경로 해제 시간 정보가 저장된다. 참고로, 도 3의 (c)에서는 제 2 필드(P32)가 TTL(Time To Live) 필드인 것을 나타내었다.

다시 도 2로 돌아가서, 패킷 분배 모듈(211)은 수신된 컨트롤 패킷의 제 1 필드(P11, P21, P31)를 확인하여 컨트롤 패킷의 유형을 확인하고, 확인된 유형에 매칭되어 기설정된 처리 모듈(즉, 경로 설정 처리 모듈(212), 롤백 처리 모듈(213), 캔슬 처리 모듈(214) 및 패킷 전송 처리 모듈(215) 중 어느 하나)로 해당 컨트롤 패킷을 전달한다.

구체적으로, 패킷 분배 모듈(211)은 수신된 컨트롤 패킷이 경로 설정 패킷인 경우 경로 설정 처리 모듈(212)로 전달한다. 그리고, 패킷 분배 모듈(211)은 수신된 컨트롤 패킷이 경로 응답 패킷 또는 경로 해제 패킷인 경우 패킷 전송 처리 모듈(215)로 전달하여, 기설정된 경로 상에서 현재 라우팅 장치(200)에 인접하여 위치한 이전 또는 다음 라우팅 장치로 전송되도록 한다. 또한, 패킷 분배 모듈(211)은 수신된 컨트롤 패킷이 롤백 패킷인 경우, 해당 롤백 패킷이 현재 라우팅 장치에 입력된 방향에 따라 롤백 처리 모듈(213) 또는 경로 설정 처리 모듈(212)로 전달한다. 이때, 패킷 분배 모듈(211)은 수신된 롤백 패킷이 현재 라우팅 장치에 입력된 방향이 기설정된 일방향과 일치하는 경우, 롤백 패킷을 경로 설정 패킷으로 변경하여 경로 설정 처리 모듈(212)로 전달한다. 그리고, 패킷 분배 모듈(211)은 수신된 롤백 패킷의 입력 방향이 상기 기설정된 일방향과 상이한 다른 방향인 경우, 롤백 패킷을 롤백 처리 모듈(213)로 그대로 전달한다. 또한, 패킷 분배 모듈(211)은 수신된 컨트롤 패킷이 캔슬 패킷인 경우 캔슬 처리 모듈(214)로 전달한다.

경로 설정 처리 모듈(212)은 패킷 분배 모듈(211)을 통해, 다른 라우팅 장치로부터 롤백되어 입력된 경로 설정 패킷(이하, '롤백 경로 설정 패킷'이라고 지칭함)과, 다른 라우팅 장치로부터 롤백되지 않고 출발지 라우팅 장치의 방향에서 입력된 경로 설정 패킷(이하, '노멀(nomal) 경로 설정 패킷'이라고 지칭함)을 수신한다. 참고로, 롤백 경로 설정 패킷은, 해당 경로 설정을 시도하는 과정에서 현재 라우팅 장치를 경유하였던 패킷이며, 노멀 경로 설정 패킷은 현재 라우팅 장치를 경유한적 없는 패킷이다.

이때, 경로 설정 처리 모듈(212)로 입력된 롤백 경로 설정 패킷은, 기설정된 일방향에서 현재 라우팅 장치로 입력된 경우에 패킷 분배 모듈(211)로부터 전달된 패킷이다.

그리고, 경로 설정 처리 모듈(212)은 기설정된 적응적 라우팅 절차를 수행하여 경로 설정 패킷을 전달할 다음 라우팅 장치를 결정한 후, 전기적 링크(400)를 통해 상기 결정된 다음 라우팅 장치로 경로 설정 패킷을 전송한다. 또한, 경로 설정 처리 모듈(212)은 적응적 라우팅 절차를 수행한 결과, 라우팅을 진행할 다음 라우팅 장치가 블로킹된 것으로 판단된 경우, 경로 설정 패킷을 롤백 처리 모듈(213)로 전달하여 이전 라우팅 장치로 롤백되도록 한다.

한편, 경로 설정 처리 모듈(212)은 하기 도 4 내지 도 8을 참조하여 설명할 적응적 라우팅 알고리즘을 수행하여, 경로 설정 패킷을 다음 라우팅 장치로 전송하거나 이전 라우팅 장치로 롤백 처리할 수 있다.

하기 도 4 내지 도 8에서는, HONoC가 메시 네트워크 토폴로지 형태이며, X-Y 라우팅 방식에 기반한 적응적 라우팅 알고리즘을 적용하여 컨트롤 패킷의 경로를 설정하는 것을 나타내었다. 또한, 이하에서는 HONoC 상의 각 라우팅 장치의 위치를 X축 및 Y축의 좌표 값으로 표현하도록 한다.

구체적으로, X-Y 라우팅 방식은, HONoC상에서 X축(즉, 도 1에 도시한 'X축')방향으로 우선적으로 라우팅을 진행하되, X축 방향으로 인접한 라우팅 장치로의 경로 설정이 불가능한 경우 Y축(즉, 도 1에 도시한 'Y축')방향으로 라우팅을 진행하는 방식이다. 이때, 메시 네트워크 토폴로지에서는 각 라우팅 장치가 상/하/좌/우 방향으로 다른 라우팅 장치와 인접하며, 좌/우 방향으로 인접한 라우팅 장치는 X축 방향으로 인접한 것이고, 상/하 방향으로 인접한 라우팅 장치는 Y축 방향으로 인접한 것이다.

참고로, 본 발명의 일 실시예에서는 라우팅 장치의 경로 설정 시 X축 방향을 Y축 방향보다 우선적으로 선택하는 방식을 설명하였으나, 본 발명의 다른 실시예에서는 반대로 Y축 방향을 X축 방향보다 우선적으로 라우팅 진행 방향으로 선택하는 것도 가능하다. 또한, 본 발명의 일 실시예에서는 메시 네트워크 토폴로지 형태의 HONoC를 설명하였으나, 상이한 형태의 네트워크 토폴로지에도 우선적인 라우팅 진행 방향을 설정하여 적응적 라우팅을 적용할 수 있다. 즉, HONoC에 적용될 수 있는 다양한 네트워크 토폴로지는 각각 라우팅 장치 간의 연결 형태가 상이하며, 네트워크 토폴로지의 라우팅 장치 간의 연결을 복수의 축(axis)으로 대응시킬 경우, 각 축에 대해 라우팅 우선 순위를 설정할 수 있다.

한편, 본 발명의 일 실시예에 따른 경로 설정 처리 모듈(212)은 적응적 라우팅 절차 수행 시, '경로 설정 진행 방향 결정 처리', '경로 설정 가능 예측 처리', 및 '증복 경로 제외 처리'를 수행할 수 있다.

구체적으로, '경로 설정 진행 방향 결정 처리'는 컨트롤 패킷을 수신한 현재 라우팅 장치가 경로 설정 패킷을 전송할 진행 방향을 결정하는 처리이다. 그리고, '경로 설정 가능 예측 처리'는 상기 결정된 진행 방향으로 인접한 다음 라우팅 장치의 경로 설정 상태를 확인하여, 다음 진행 방향의 사용 가능 여부에 따라 실제 경로 설정 패킷을 전송하는 처리이다. 또한, '중복 경로 제외 처리'는 경로 설정 패킷에 저장된 롤백 위치 정보를 이용하여 경로 설정 패킷이 롤백시 경유하였던 라우팅 장치를 제외하고 우회 경로를 탐색하는 처리이다.

먼저, 도 4를 참조하여 본 발명의 일 실시예에서 경로 설정 처리 모듈(212)의 '경로 설정 진행 방향 결정 처리' 절차를 상세히 설명하도록 한다.

도 4는 본 발명의 일 실시예에 따른 적응적 라우팅 방식에서 라우팅 진행 방향을 결정하는 절차를 설명하기 위한 순서도이다.

도 4에서와 같이, 경로 설정 처리 모듈(212)은 패킷 분배 모듈(211)로부터 경로 설정 패킷을 수신하면(S410), 수신된 경로 설정 패킷이 롤백된 패킷(즉, '롤백 경로 설정 패킷')인지 여부를 판단한다(S420).

참고로, 경로 설정 처리 모듈(212)로 입력될 수 있는 롤백 경로 설정 패킷은, 현재 라우팅 장치가 컨트롤 패킷을 입력받을 수 있는 복수의 방향 중 기설정된 일방향에서 롤백된 것이다. 상기 기설정된 일방향은 적응적 라우팅에서 우선적으로 경로를 설정하는 방향(즉, 본 발명의 일 실시예에서는 'X축' 방향)이다. 설명의 편의상, 이하에서는 '우선 경로 방향'이라고 지칭하도록 한다.

참고로, 다른 라우팅 장치로부터 입력된 롤백 패킷이 상기 기설정된 일방향과 상이한 다른 방향(즉, 본 발명의 일 실시예에서는 'Y축' 방향)에서 롤백되어 입력된 경우, 패킷 분배 모듈(211)은 수신된 롤백 패킷을 롤백 처리 모듈(213)로 곧바로 전달한다. 이는, X-Y 라우팅 방식에 따르면, 우선 경로 방향(즉, X축 방향)이 아닌 방향(즉, Y축 방향)으로부터 컨트롤 패킷이 롤백된 경우는, 우선 경로 방향(즉, X축 방향)으로 더 이상 진행할 경로가 없는 경우를 의미하기 때문이다. 이와 같은 경우, 패킷 분배 모듈(211)은 Y축 방향에서 롤백된 롤백 패킷을 롤백 처리 모듈(123)로 곧바로 전달한다.

상기 단계 (S420)의 판단 결과, 수신된 경로 설정 패킷이 롤백 경로 설정 패킷이 아닌 노멀 경로 설정 패킷인 경우, 현재 라우팅 장치와 목적지 라우팅 장치의 X축 좌표 값을 비교하여 동일한지 여부를 판단한다(S430).

이때, 경로 설정 처리 모듈(212)은 노멀 경로 설정 패킷의 제 3 필드(P13)에 저장된 목적지 정보로부터 목적지 라우팅 장치의 X 축 좌표 값을 확인할 수 있다.

그런 후, 현재 라우팅 장치와 목적지 라우팅 장치의 X축 좌표 값이 동일한 경우, 하기에서 설명할 단계 (S440)로 진행하여 현재 라우팅 장치와 목적지 라우팅 장치의 Y축 좌표 값을 비교한다.

반면, 현재 라우팅 장치와 목적지 라우팅 장치의 X축 좌표 값이 상이한 경우, 경로 설정 패킷을 전달할 X축 상의 진행 방향을 결정한다(S431).

이때, 단계 (S431)에서는, 현재 라우팅 장치의 X축 좌표 값이 목적지 라우팅 장치의 X축 좌표 값보다 작은 경우, X축 방향 중 우측 방향(도 4에서는, 'east'로 표현함)을 경로 설정 패킷을 전송할 진행 방향으로 결정한다. 또한, 현재 라우팅 장치의 X축 좌표 값이 목적지 라우팅 장치의 X축 좌표 값보다 큰 경우, X축 방향 중 좌측 방향(도 4에서는, 'west'로 표현함)을 진행 방향으로 결정한다.

즉, 현재 라우팅 장치가 목적지 라우팅 장치 보다 X축 좌표의 값이 큰 경우, 현재 라우팅 장치의 X축 좌표의 값이 작아지는 방향으로 진행 방향을 결정한다. 반면, 현재 라우팅 장치가 목적지 라우팅 장치보다 X축 좌표의 값이 작은 경우, 현재 라우팅 장치의 X축 좌표의 값이 커지는 방향으로 진행 방향을 결정한다. 이와 같이 라우팅 진행 방향을 목적지 라우팅 장치를 향한 방향으로만 설정되도록 함으로써, 불필요한 경로를 탐색할 필요없이 목적지까지의 최단 거리 경로 내에서 라우팅 방향을 결정할 수 있다. 참고로, HONoC 상에서 어느 하나의 라우터 장치(200)와 인접한 라우터 장치(200) 간의 거리를 홉(hop)이라할 경우, 최단 거리 경로는 출발지 라우팅 장치로부터 목적지 라우팅 장치까지 최소의 홉을 갖는 경로를 의미한다.

그런 후, 현재 라우팅 장치의 상기 단계(S431)에서 결정된 X축 상의 진행 방향에 대한 경로 설정 상태를 확인하여 경로 설정이 가능한지 여부를 판단한다(S432).

참고로, 본 발명의 일 실시예에 따른 라우팅 장치(200)에는 상/하/좌/우 방향으로 컨트롤 패킷을 출력할 수 있는 복수의 출력 포트가 구성되어 있으며, 경로 설정 처리 모듈(212)은 상기 결정된 진행 방향에 대응된 출력 포트의 상태를 확인하여 경로 설정 가능 여부를 판단할 수 있다.

상기 단계 (S432)의 확인 결과, 현재 라우팅 장치의 상태가 상기 결정된 진행 방향으로의 경로 설정이 가능한 상태인 경우, 경로 설정 패킷을 전송할 대상인 다음 라우팅 장치(next router)에 대한 경로 설정 가능 여부를 예측하는 처리(즉, 상기 '경로 설정 가능 예측 처리')의 초기 단계로 접근한다(S480).

참고로, 상기 다음 라우팅 장치는 현재 라우팅 장치로부터 상기 결정된 진행 방향으로 인접한 라우팅 장치로서, 다음 라우팅 장치에 대한 경로 설정 가능 예측 처리는 다음 라우팅 장치의 경로 설정 상태에 따라 실제로 경로 설정 패킷을 전송할지 여부를 판단하기 위한 것이다.

반면, 상기 단계 (S432)의 확인 결과, 현재 라우팅 장치의 상태가 상기 결정된 진행 방향으로의 경로 설정이 불가능한 상태인 경우, 하기에서 설명할 단계 (S440)으로 진행하여 현재 라우팅 장치와 목적지 라우팅 장치의 Y축 좌표 값을 비교한다.

한편, 상기 단계(S420)의 판단 결과, 수신된 경로 설정 패킷이 롤백 경로 설정 패킷인 경우, 현재 라우팅 장치와 목적지 라우팅 장치의 Y축 좌표 값을 비교하여 동일한지 여부를 판단한다(S440).

즉, Y축 방향에서 입력된 롤백 패킷에 기초한 롤백 경로 설정 패킷에 대해 X축에 대한 판별(즉, 단계 S430, S431 및 S432)은 생략함으로써, 불필요한 단계의 수행을 방지할 수 있어 효율적이다.

그런 다음, 상기 단계 (S440)의 판단 결과, 현재 라우팅 장치와 목적지 라우팅 장치의 Y축 좌표 값이 상이한 경우, 라우팅을 진행할 Y축 상의 진행 방향을 결정한다(S441).

이때, 현재 라우팅 장치의 Y축 좌표 값이 목적지 라우팅 장치의 Y축 좌표 값보다 작은 경우, Y축의 상측 방향(도 4에서는 'north' 방향으로 표현함)을 진행 방향으로 결정한다. 또한, 현재 라우팅 장치의 Y축 좌표 값이 목적지 라우팅 장치의 Y축 좌표 값 보다 큰 경우 Y축의 하측 방향(도 4에서는 'south' 방향으로 표현함)을 진행 방향으로 결정한다. 이 또한, 라우팅 진행 방향을 목적지 라우팅 장치를 향한 방향으로만 설정되도록 함으로써, 목적지까지의 최단 거리 경로 내에서 라우팅 방향을 결정할 수 있다.

그런 후, 현재 라우팅 장치의 상기 단계(S441)에서 결정된 Y축 상의 진행 방향에 대한 경로 설정 상태를 확인하여 경로 설정이 가능한지 여부를 판단한다(S442).

상기 단계 (S442)의 판단 결과, 현재 라우팅 장치가 상기 결정된 진행 방향으로의 경로 설정이 가능한 상태인 경우, 상기 단계(S480)을 수행하여 다음 라우팅 장치에 대한 경로 설정 가능 여부를 예측한다.

반면, 상기 단계 (S442)의 판단 결과, 현재 라우팅 장치가 상기 결정된 진행 방향으로의 경로 설정이 불가능한 상태인 경우, 경로 설정 패킷을 롤백 처리 모듈(213)로 전달한다(S451).

한편, 상기 단계 (S440)의 판단 결과, 현재 라우팅 장치의 Y축 좌표 값과 목적지 라우팅 장치의 Y축 좌표 값이 동일한 값이면, 현재 라우팅 장치와 목적지 라우팅 장치의 주소가 동일한지 여부를 판단한다(S450).

참고로, 현재 라우팅 장치의 X축 좌표 및 Y축 좌표와 목적지 라우팅 장치의 X축 좌표 및 Y축 좌표가 각각 동일한 경우, 현재 라우팅 장치와 목적지 라우팅 장치의 주소가 같다고 판단한다.

상기 단계 (S450)의 판단 결과, 현재 라우팅 장치와 목적지 라우팅 장치의 주소가 상이한 경우, 상기 단계(S451)를 수행하여 경로 설정 패킷을 롤백 처리 모듈(213)로 전달한다.

반면, 상기 단계 (S450)의 판단 결과, 현재 라우팅 장치와 목적지 라우팅 장치의 주소가 동일한 경우, 현재 라우팅 장치가 목적지 라우팅 장치인 것으로 판단하고 현재 라우팅 장치에 매칭된 PE(100)의 사용 가능 여부를 판단한다(S460).

그런 후, 상기 단계 (S460)의 판단 결과, 현재 라우팅 장치에 매칭된 PE(100)의 상태가 사용 불가능한 상태인 경우, 경로 설정 패킷을 캔슬 처리 모듈(214)로 전달한다(S461).

반면, 상기 단계 (S460)의 판단 결과, 현재 라우팅 장치와 매칭된 PE(100)의 상태가 사용 가능한 상태인 경우, 해당 PE(100)로 경로 설정 패킷을 전달하여 광학적 경로를 설정한다(S470).

다음으로, 도 5를 참조하여 본 발명의 일 실시예에서 경로 설정 처리 모듈(212)의 '경로 설정 가능 예측 처리'의 절차를 상세히 설명하도록 한다.

도 5는 본 발명의 일 실시예에 따른 적응적 라우팅 방식에서 다음 라우팅 장치에 대한 경로 설정 예측 처리 절차를 설명하기 위한 순서도이다.

도 5에서와 같이, 경로 설정 처리 모듈(212)은, 상기 도 4의 단계 (S432) 및 (S442)의 다음 단계로서, 다음 라우팅 장치의 X축 좌표와 목적지 라우팅 장치의 X축 좌표를 비교하여 동일한지 여부를 판단한다(S510).

그런 다음, 상기 단계(S510)의 판단 결과, 다음 라우팅 장치와 목적지 라우팅 장치의 X축 좌표 값이 상이한 경우, 다음 라우팅 장치로부터 라우팅을 진행할 X축 상의 진행 방향(이하, '다음 진행 방향'이라고 지칭함)을 결정한다(S511).

이때, 단계 (S511)에서는, 다음 라우팅 장치의 X축 좌표 값이 목적지 라우팅 장치의 X축 좌표 값보다 작은 경우, X축 방향 중 우측 방향(도 5에서는, 'east'로 표현함)을 다음 진행 방향으로 결정한다. 또한, 다음 라우팅 장치의 X 축 좌표 값이 목적지 라우팅 장치의 X축 좌표 값보다 큰 경우, X축 방향 중 좌측 방향(도 5에서는, 'west'로 표현함)을 다음 진행 방향으로 결정한다.

그런 후, 상기 단계 (S511)에서 결정된 다음 진행 방향으로 다음 라우팅 장치의 경로 설정이 가능한지 여부를 확인한다(S512).

상기 단계 (S512)의 확인 결과, 다음 라우팅 장치의 X축 상의 다음 진행 방향으로의 경로 설정이 가능한 경우, 경로 설정 패킷을 다음 라우팅 장치로 전송한다(S540).

반면, 상기 단계 (S512)의 확인 결과, 다음 라우팅 장치가 다음 진행 방향으로의 경로 설정이 불가능한 상태인 경우(즉, 블로킹된 경우), 하기에서 설명할 단계 (S520)으로 진행하여, 다음 라우팅 장치와 목적지 라우팅 장치의 Y축 좌표 값을 비교한다. 이는, 다음 라우팅 장치의X축 방향으로의 라우팅 진행은 불가능한 상태이므로, Y축 방향으로의 라우팅 진행이 가능한지 여부를 판단하기 위한 것이다.

한편, 상기 단계 (S510)의 판단 결과, 다음 라우팅 장치와 목적지 라우팅 장치의 X축 좌표 값이 동일한 경우, 다음 라우팅 장치와 목적지 라우팅 장치의 Y축 좌표 값을 비교하여 동일한지 여부를 판단한다(S520)

그런 후, 상기 단계 (S520)의 판단 결과, 다음 라우팅 장치와 목적지 라우팅 장치의 Y축 좌표 값이 상이한 경우, 다음 라우팅 장치로부터 라우팅을 진행할 Y축 상의 진행 방향(즉, '다음 진행 방향')을 결정한다(S521).

이때, 단계 (S521)에서는, 다음 라우팅 장치의 Y축 좌표 값이 목적지 라우팅 장치의 Y축 좌표 값보다 작은 경우, Y축 방향 중 상측 방향(도 5에서는, 'north'로 표현함)을 다음 진행 방향으로 결정한다. 또한, 다음 라우팅 장치의 Y축 좌표 값이 목적지 라우팅 장치의 Y축 좌표 값보다 큰 경우, Y축 방향 중 하측 방향(도 5에서는, 'south'로 표현함)을 다음 진행 방향으로 결정한다.

그런 후, 상기 단계 (S521)에서 결정된 Y축 상의 다음 진행 방향으로 다음 라우팅 장치의 경로 설정이 가능한지 여부를 판단한다(S522).

상기 단계 (S522)의 판단 결과, 다음 라우팅 장치의 다음 진행 방향으로의 경로 설정이 가능한 경우, 앞서 설명한 단계 (S540)로 진행하여 경로 설정 패킷을 다음 라우팅 장치로 전송한다.

반면, 상기 단계 (S522)의 판단 결과, 다음 라우팅 장치의 다음 진행 방향으로의 경로 설정이 불가능한 상태인 경우, 하기에서 설명할 단계 (S531)로 진행하여, 상기 도 4에서 설명한 '경로 설정 진행 방향 결정 처리'에서 결정된 진행 방향이 X축 상의 방향인지를 확인한다.

한편, 상기 단계 (S520)의 판단 결과, 다음 라우팅 장치와 목적지 라우팅 장치의 Y축 좌표 값이 동일한 경우, 다음 라우팅 장치와 목적지 라우팅 장치의 주소가 동일한지 여부를 판단한다(S530).

즉, 다음 라우팅 장치와 목적지 라우팅 장치의 X축 좌표 및 Y축 좌표 값이 각각 동일한 경우, 다음 라우팅 장치와 목적지 라우팅 장치의 주소가 동일하다고 판단한다.

그런 후, 상기 단계 (S530)의 판단 결과, 다음 라우팅 장치와 목적지 라우팅 장치의 주소가 동일한 경우, 앞서 설명한 단계 (S540)로 진행하여 경로 설정 패킷을 다음 라우팅 장치로 전송한다.

반면, 상기 단계 (S530)의 판단 결과, 다음 라우팅 장치와 목적지 라우팅 장치의 주소가 상이한 경우, 현재 라우팅 장치로부터 다음 라우팅 장치로의 진행 방향이 X축 방향인지 여부에 따라 롤백 처리 여부를 판단한다(S531).

즉, 상기 도 4에서 설명한 '경로 설정 진행 방향 결정 처리' 절차에서, 노멀 경로 설정 패킷이 수신되어 X축 상의 진행 방향이 결정된 경우, Y축에 대한 진행 방향은 탐색하지 않은 상태이다. 따라서, 상기 단계 (S531)은, 현재 라우팅 장치의 진행 방향이 X축 방향으로 결정된 상태에서, 상기 단계 (422)의 판단 결과 X축 상에 인접한 다음 라우팅 장치가 X축 및 Y축 상의 다음 진행 방향으로의 경로 설정이 불가능하다고 판단된 경우, 현재 라우팅 장치의 Y축 에 대한 경로 재탐색이 수행되도록 하기 위한 단계이다.

상기 단계 (S531)의 판단 결과, 다음 라우팅 장치가 현재 라우팅 장치로부터 X축 진행 방향으로 인접한 라우팅 장치인 경우, 상기 도 4에서의 단계 (S440)으로 복귀하여 현재 라우팅 장치의 Y축에 대한 진행 방향 탐색을 수행한다.

반면, 상기 단계 (S531)의 판단 결과, 다음 라우팅 장치가 현재 라우팅 장치로부터 Y축 방향으로 인접한 라우팅 장치인 경우, 경로 설정 패킷을 롤백 처리 모듈(213)로 전달한다(S532).

이상에서 도 4 및 도 5를 참조하여 설명한 바와 같이, 경로 설정 처리 모듈(212)이 적응적 라우팅을 수행함으로써, 출발지로부터 목적지까지의 경로 설정 시 다음 라우팅 장치의 상태에 따른 경로 설정이 가능하며 최단 거리 경로를 설정할 수 있다.

예를 들어, 도 6은 본 발명의 일 실시예에 따른 적응적 라우팅 수행 결과의 일례를 나타낸 도면이다.

도 6에서는, HONoC 상에 위치한 64개의 라우팅 장치(200) 및 각 라우팅 장치(200)에 매칭된 PE(100)를 나타내었으며, 각 PE(100) 상에 위치 좌표(X, Y)를 표현하였다.

또한, 도 6에서는 출발지의 위치 좌표가 (1, 0)이고, 목적지의 위치 좌표가 (4, 5)인 것을 나타내으며, 위치 좌표 (3, 1), (4, 1), (4, 2), (4, 3), (4, 4)를 경유하는 제 1 사용 경로(도 6에서는 'path 1'로 나타냄)와, 위치 좌표 (5, 1), (5, 2), (5, 3)을 경유하는 제 2 사용 경로(도 6에서는 'path 2'로 나타냄)를 나타내었다. 즉, 출발지와 목적지 사이에 이미 사용 중인 라우팅 장치가 존재한다.

이때, 본 발명의 일 실시예에 따른 적응적 라우팅을 수행한 결과, 출발지로부터 목적지까지 설정될 수 있는 복수의 경로 중 위치 좌표 (1, 0), (2, 0), (2, 1), (2, 2), (3, 2), (3, 3), (3, 4), (3, 5), (4, 5)를 경유하는 경로(도 6에서는 'path 3'으로 나타냄)가 설정될 수 있다.

구체적으로, 본 발명의 일 실시예에 따른 적응적 라우팅에 따르면, X-Y라우팅에 의해, 출발지 라우팅 장치(즉, 위치 좌표 (1, 0))부터 목적지 라우팅 장치의 X축 좌표와 동일한 값을 갖는 라우팅 장치(즉, 위치 좌표 (4, 0))까지 X축 상에서 경로 설정 패킷이 전송된다. 그런데, 위치 좌표 (4, 0)를 갖는 라우팅 장치가 Y축 상으로 라우팅을 진행해야할 다음 라우팅 장치(즉, 위치 좌표 (4, 1))가 이미 사용 중인 상태이므로, 위치 좌표 (4, 0)를 갖는 라우팅 장치는 경로 설정 패킷가 경유하였던 이전 라우팅 장치로 롤백 패킷을 롤백시킨다. 이에 따라, 롤백 패킷은 Y축 상으로의 진행 방향 탐색이 가능한(즉, Y축 상의 인접 라우팅 장치가 사용 가능한) 상태인 라우팅 장치(즉, 위치 좌표 (2, 0))까지 롤백된다. 그리고, 위치 좌표 (2, 0)을 갖는 라우팅 장치는 Y축 상으로 경로를 우회시켜 Y축 상에 인접한 라우팅 장치(즉, 위치 좌표 (2, 1))로 경로 설정 패킷을 전송하여 경로(즉, 'path 3')를 설정한다.

이에 비해, 롤백 처리없이 X-Y 라우팅만을 적용할 경우, 도 6에서와 같이, 출발지 라우팅 장치(즉, 위치 좌표 (1, 0))로부터 전송된 경로 설정 패킷이 X축 상의 라우팅 장치들에 순차적으로 전송된 후, 해당 경로 설정 패킷이 목적지 라우팅 장치의 X축 좌표 값을 지나친 위치의 라우팅 장치(즉, 위치 좌표 (6, 0))까지 진행된 후에야 Y축 상으로 진행되어 최종적으로 경로(도 6에서는 'path 4'로 도시함)를 설정할 수 있다. 즉, 최단 거리 경로 내에서 경로가 설정되는 본 발명의 일 실시예에 따른 적응적 라우팅 방식에 비해, 다른 라우팅 방식에서는 탐색된 경로의 거리가 매우 비효율적인 것을 알 수 있다.

한편, 경로 설정 처리 모듈(212)은 상기 도 6에서 설명한 바와 같이, 이미 경유한 경로에 대해 불필요한 반복적 재탐색을 방지하기 위하여, 롤백 경로 설정 패킷에 저장된 롤백 위치 정보(즉, 최초 롤백된 위치 정보)를 이용하여 '중복 경로 제외 처리' 절차를 수행한다. 본 발명의 일 실시예에서는, 경로 설정 패킷의 제 4 필드(P14)에 롤백을 시작한 라우팅 장치의 Y축 좌표 값(즉, 'Y-value')이 저장된 것을 나타내었다.

예를 들어, 도 7은 본 발명의 일 실시예에서 발생될 수 있는 중복 경로 탐색 과정의 일례를 나타낸 도면이다.

도 7에서는, 출발지 라우팅 장치(P710)로부터 목적지 라우팅 장치(P720)로의 경로 상에 이미 사용중인 경로(path 1)가 존재하는 것을 나타내었다. 이때, 경로 설정 패킷은 출발지 라우팅 장치(P710)로부터 목적지 라우팅 장치(P720)의 X축 좌표와 동일한 X축 좌표를 갖는 제 1 라우팅 장치(P730)까지 X축 상에서 라우팅된다. 그런 후, 제 1 라우팅 장치(P730)로부터 목적지 라우팅 장치(P720)를 향해 Y축 상에서 경로 설정 패킷이 라우팅된다. 그런데, 도 7에서와 같이 제 1 라우팅 장치(P730)로부터 라우팅되던 경로 설정 패킷은, 이미 사용중인 경로(path 1) 상에 위치하는 제 3 내지 제 5 라우팅 장치(P750 내지 P770)에 의하여, 제 2 라우팅 장치(P740)에서 블로킹된다. 이에 따라, 제 2 라우팅 장치(P740)는 출발지 라우팅 장치(P710) 방향의 이전 라우팅 장치(P780)로 롤백 패킷을 롤백시킨다.

특히, 출발지 라우팅 장치(P710)로부터 제 2 라우팅 장치(P740)까지 제 1 경로(도 7에서는 '①'로 도시함)를 통해 경로 설정 패킷이 전송된 이후, 제 2 내지 제4 경로(도 7에서는 '② 내지④'로 도시함)와 같이 Y축 상에서 이미 경유한 라우팅 장치를 다시 진행 방향으로 탐색하는 롤백 처리가 발생될 수 있다.

이와 같은 불필요한 중복 경로 탐색을 방지하기 위하여, 본 발명의 일 실시예에 따른 경로 설정 처리 모듈(212)은, 상기 도 4에서 설명한 '경로 설정 진행 방향 결정 처리'를 수행하기에 앞서, 하기 도 8에서와 같은 '중복 경로 제외 처리'를 수행하는 적응적 라우팅 절차를 수행한다.

도 8은 본 발명의 일 실시예에 따른 적응적 라우팅 방식에서 중복 경로를 제외하는 절차를 설명하기 위한 순서도이다.

참고로, 본 발명의 일 실시예에 따른 '중복 경로 제외 처리'는 도 8에서와 같이 상기 도 4의 'X축 위치 비교 처리 단계'(S430) 및 'Y축 위치 비교 처리 단계'(S440) 이전에 수행되는 것으로서, 도 8에서는 상기 도 4에서와 동일한 동작을 수행하는 단계에 대해서는 상기 도 4에서와 같은 도면 부호를 사용하였다.

먼저, 상기 도 4의 단계 (S420)에서, 현재 입력된 경로 설정 패킷이 롤백 경로 설정 패킷인 것으로 판단되면, 상기 도 4의 단계 (S440)으로 진행하여 현재 라우팅 장치에 대한 Y축 위치 비교 처리 단계(S440)을 수행한다.

반면, 상기 도 4의 단계 (S420)에서, 현재 입력된 경로 설정 패킷이 롤백 경로 설정 패킷이 아닌 것(즉, 노멀 경로 설정 패킷인 것)으로 판단되면, 현재 라우팅 장치의 Y축 좌표 값이 목적지 라우팅 장치 및 롤백이 시작된 라우팅 장치(예를 들어, 도 7의 제 2 라우팅 장치(P740))의 Y축 좌표 값보다 큰 값인지를 판단한다(S421).

이때, 경로 설정 처리 모듈(212)은 노멀 경로 설정 패킷의 제 4 필드(P14)에 저장된 롤백 위치 정보(즉, 'Y-value')를 확인하여 해당 경로 설정 패킷의 롤백이 처음 시작된 라우팅 장치의 Y축 좌표 값을 추출할 수 있다.

상기 단계 (S421)의 판단 결과, 현재 라우팅 장치의 Y축 좌표 값이 목적지 라우팅 장치 및 롤백이 시작된 라우팅 장치의 Y축 좌표 값보다 큰 값인 경우, 상기 도 4의 단계 (S440)으로 진행하여 현재 라우팅 장치에 대한 Y축 위치 비교 처리 단계(S440)을 수행한다.

반면, 단계 (S421)의 판단 결과, 현재 라우팅 장치의 Y축 좌표 값이 목적지 라우팅 장치 및 롤백이 시작된 라우팅 장치의 Y축 좌표 값 중 적어도 하나보다 작은 값인 경우, 현재 라우팅 장치의 Y축 좌표 값이 목적지 라우팅 장치 및 롤백이 시작된 라우팅 장치의 Y축 좌표 값보다 작은 값인지를 판단한다(S422).

상기 단계 (S422)의 판단 결과, 현재 라우팅 장치의 Y축 좌표 값이 목적지 라우팅 장치 및 롤백이 시작된 라우팅 장치의 Y축 좌표 값보다 작은 값인 경우, 상기 도 4의 단계 (S440)으로 진행하여 현재 라우팅 장치에 대한 Y축 위치 비교 처리 단계(S440)을 수행한다.

반면, 단계 (S422)의 판단 결과, 현재 라우팅 장치의 Y축 좌표 값이 목적지 라우팅 장치 및 롤백이 시작된 라우팅 장치의 Y축 좌표 값 중 적어도 하나보다 큰 값인 경우, 상기 도 4의 단계 (S430)으로 진행하여 현재 라우팅 장치에 대한 X축 위치 비교 처리 단계(S430)를 수행한다.

즉, 경로 설정 패킷에 대한 우회 경로 탐색 시, 해당 경로 설정 패킷에 대한 롤백이 시작된 라우팅 장치가 현재 라우팅 장치보다 Y축 상에서 목적지 라우팅 장치에 근접한 경우 상기 도 4의 단계 (S440)을 수행하여 Y축 상에서의 진행 경로를 탐색한다. 그 외의 경우, 상기 도 4의 단계 (S430)을 수행하여 경로 설정 패킷에 대한 X축 상에서의 진행 경로를 탐색한다.

다시 도 2로 돌아가서, 롤백 처리 모듈(213)은 패킷 분배 모듈(211)로부터 롤백 패킷을 수신하거나, 경로 설정 처리 모듈(212)로부터 롤백시킬 경로 설정 패킷을 수신한다.

그리고, 롤백 처리 모듈(213)은 패킷 분배 모듈(211)로부터 수신된 롤백 패킷은 그대로 이전 라우팅 장치로 전달한다. 참고로, 롤백 패킷이 그대도 전달되는 이전 라우팅 장치는, 출발지 라우팅 장치로부터 전송된 경로 설정 패킷이 경유한 라우팅 장치 중 현재 라우팅 장치보다 출발지 라우팅 장치에 근접한 인접 라우팅 장치를 의미한다.

또한, 롤백 처리 모듈(213)은 경로 설정 처리 모듈(212)로부터 수신된 롤백시킬 경로 설정 패킷을 롤백 패킷으로 변경하여, 해당 경로 설정 패킷이 입력되었던 이전 라우팅 장치로 롤백시킨다.

캔슬 처리 모듈(214)은 경로 설정 처리 모듈(212)로부터 취소시킬 경로 설정 패킷을 수신한다.

이때, 캔슬 처리 모듈(214)은 경로 설정 처리 모듈(212)이 결정한 다음 라우팅 장치가 목적지 라우팅 장치이되, 목적지 라우팅 장치와 매칭된 PE(100)의 상태가 사용 불가능한 상태인 경우, 해당 경로 설정 패킷에 대해 직전까지 설정된 경로 상의 라우팅 장치들을 경유하여 출발지 라우팅 장치까지 도착하는 캔슬 패킷을 전송한다.

참고로, 캔슬 패킷 또는 롤백 패킷을 수신한 출발지 라우팅 장치는 안정적인 경로 재설정을 위하여, 기설정된 지연 시간이 경과한 후 경로 설정 패킷을 재전송한다. 이는, 하기 데이터 전송부(220)의 동작 설명 시 상세히 설명하도록 한다.

패킷 전송 처리 모듈(215)은 하기 데이터 수신부(230)를 통해 다른 라우팅 장치로부터 경로 응답 패킷 또는 경로 해제 패킷을 수신한다.

구체적으로, 패킷 전송 처리 모듈(215)은 경로 응답 패킷을 수신하면, 경로 응답 패킷의 제 2 필드(P12)를 확인하여 출발지 라우팅 장치의 주소를 추출하고, 현재 라우팅 장치가 출발지 라우팅 장치인 경우 및 응답이 경유하는 라우팅 장치인 경우를 구분한다.

그리고, 패킷 전송 처리 모듈(215)은 현재 라우팅 장치가 출발지 라우팅 장치인 경우 해당 경로 응답 패킷을 데이터 전송부(220)로 전달하고, 현재 라우팅 장치가 응답이 경유하는 라우팅 장치인 경우 해당 경로 응답 패킷을 출발지 라우팅 장치 방향으로 인접한 이전 라우팅 장치로 전달한다.

또한, 패킷 전송 처리 모듈(215)은 경로 해제 패킷을 수신하면, 경로 해제 패킷의 제 2 필드(P32)에 저장된 경로 해제 시간 정보를 추출하여 경로 해제 처리부(240)로 전달한다. 그리고, 패킷 전송 처리 모듈(215)은 경로 해제 처리부(240)에 의해 기설정된 값만큼 감소시킨 경로 해제 시간 정보를 포함하는 경로 해제을 다음 라우팅 장치로 전달한다.

이때, 패킷 전송 처리 모듈(215)은 수신된 경로 해제 패킷에 저장되었던 원래 경로 해제 시간 정보를 상기 지연 시간에 기초하여 감소시킨 값을 경로 해제 패킷의 제 2 필드(P32)에 갱신 저장한 후, 해당 경로 해제 패킷을 전달한다.

한편, 도 2에서와 같이, 데이터 전송부(220)는 경로 설정 지연 모듈(221), 데이터 전송 모듈(222) 및 경로 해제 설정 모듈(223)을 포함한다.

경로 설정 지연 모듈(221)은 현재 라우팅 장치가 출발지 라우팅 장치로서 캔슬 패킷 또는 롤백 패킷을 수신하면, 기설정된 지연 시간만큼 대기한 이후에 경로 설정을 재시도한다.

예를 들어, 도 9는 본 발명의 일 실시예에 따른 경로 설정 지연 방식을 설명하기 위한 경로 설정 동시 발생 상태의 일례를 나타낸 도면이다.

도 9에서와 같이, HONoC 상에 위치 좌표 (5, 3)에서 위치 좌표(6, 5)로 데이터가 전송 중인 상태에서, 위치 좌표 (3, 3)에서 위치 좌표 (7, 3)으로의 경로 설정 시도(이하, '제 1 경로 설정 시도'라고 지칭함)와, 위치 좌표 (1, 3)에서 위치 좌표 (5, 3)로의 경로 설정 시도(이하, '제 2 경로 설정 시도'라고 지칭함)가 동시에 발생할 수 있다.

이와 같은 경우, 제 2경로 설정 시도에 따른 경로에서는 목적지의 위치 좌표 (5, 3)가 이미 사용 중인 상태이므로 실제적으로 데이터 통신이 발생할 수 없다. 그럼에도 불구하고, 두 경로 설정 시도가 동시에 발생될 경우, 제 1 경로 설정 시도에 의한 경로 설정 또한 불가능하여 병렬 전송 시 문제가 발생될 수 있다.

이에 따라, 본 발명의 일 실시예에 따른 각 라우팅 장치(200)들은 HONoC 상에서의 해당 라우팅 장치(200)의 위치에 기초하여 다른 라우팅 장치(200)와는 차등적인 지연 시간을 설정하고, 설정된 지연 시간이 경과한 이후 경로 설정을 시도할 수 있다.

구체적으로, 경로 설정 지연 모듈(221)은, 캔슬 처리 모듈(214)로부터 캔슬 패킷을 수신하거나, 현재 라우팅 장치가 출발지 라우팅 장치인 경우에 롤백 처리 모듈(214)로부터 롤백 패킷을 수신하면, 경로 설정 재시도에 대한 지연 시간을 산출한다.

이때, 하기 수학식 1을 이용하여 경로 설정 재시도에 대한 지연 시간을 산출할 수 있다.

<수학식 1>

상기 수학식 1에서, S_aps는 라우팅 장치(200)의 전기적 라우터가 컨트롤 패킷을 출력하는 복수의 포트를 스위칭하는데 필요한 평균 사이클이며, X_max 및 Y_max는 네트워크 토폴로지의 각 축(즉, X/Y 축)의 사이즈(즉, 배열된 라우팅 장치의 축 별 전체 개수)를 의미한다. 그리고, X_bound 및 Y_bound는, 현재 라우팅 장치로부터 패킷이 전송될 방향으로 가장 먼 라우팅 장치의 위치와 현재 라우팅 장치의 위치 간의 차를 의미한다.

구체적으로, 도 10은 본 발명의 일 실시예에 따른 경로 설정 재시도에 적용될 지연 시간의 산출 방식을 설명하기 위한 도면이다.

하기 도 10의 (a)에서는 경로 설정을 시도할 방향 별 X_bound 및 Y_bound의 값을 나타내었으며, 도 10의 (b)에서는 각 진행 방향(direction)이 HONoC 상에서 의미하는 방향을 표시하였다.

결과적으로, 현재 라우팅 장치와 동일한 방향(예를 들어, 도 10의 'E' 방향)으로 경로 설정을 시도하는 다른 라우팅 장치가 현재 라우팅 장치보다 X축 상에서 좌측(즉, 도 10의 'W' 방향)에 위치한 경우 보다, 상기 다른 라우팅 장치가 현재 라우팅 장치보다 X 축 상의 우측(즉, 도 10의 'E' 방향)에 위치한 경우에, 상기 수학식 1에 의한 지연 시간(C_delay)의 값이 크게 설정된다.

이와 같이 함으로써, 동일 방향 상에서 뒤쪽에서 경로 설정을 시도하는 라우팅 장치가 앞쪽의 라우팅 장치보다 먼저 경로 설정을 재시도하도록 하여, HONoC 상에서 효율적인 병렬 전송이 가능하다.

다시 도 2로 돌아와서, 데이터 전송 모듈(222)은 패킷 전송 처리 모듈(215)을 통해 경로 응답 패킷이 수신되는 경우, 목적지 라우팅 장치와의 경로 설정이 성공적으로 완료된 것으로 판단하고, 매칭 연결된 PE(100)가 광학적 링크(300)를 통해 목적한 데이터를 전송하도록 제어한다.

참고로, 데이터 전송 모듈(222)이 경로 응답 패킷을 수신한 후 PE(100)가 데이터를 전송하도록 제어하는 경우는, 현재 라우팅 장치가 출발지 라우팅 장치인 경우이다.

한편, 광학적 경로를 통해 PE(100)의 데이터 전송이 완료되면, 목적지까지 설정된 경로 상의 라우팅 장치(200)들로 경로 해제 패킷을 전송하여 설정되었던 경로를 해제시켜야 한다. 만약, PE(100)가 데이터 전송을 완료한 이후 경로 해제 패킷을 전송할 경우, 해당 경로에 대한 광학적 경로가 실제적으로 사용되지 않음에도 경로가 해제되는 동안 경로가 점유되어 있게 된다.

이에 따라, 본 발명의 일 실시예에 따른 경로 해제 설정 모듈(223)은 매칭 연결된 PE(100)가 광학적 링크(300)를 통해 기설정된 경로로 목적한 데이터의 전송을 시작하면, 전기적 링크(400)를 통해 동일 경로로 경로 해제 패킷을 전송한다. 이때, 경로 해제 설정 모듈(223)은 목적 데이터의 전송 시작과 동시에 또는 이후에 경로 해제 패킷을 전송할 수 있다.

이때, 경로 해제 설정 모듈(223)은 하기 수학식 2를 이용하여 경로 해제 시간을 산출하고, 산출된 경로 해제 시간의 정보를 포함하는 경로 해제 패킷을 전기적 링크(400)를 통해 다른 라우팅 장치로 전송한다.

<수학식 2>

상기 수학식 2에서, 경로 해제 시간인 C_tx는 광학적 경로를 통해 데이터를 전송하는데 걸리는 클록 사이클(clock cycle)이다. 그리고, P_size는 전송한 패킷의 크기(packet size)이고, f_elec는 전기적 링크(400)에 대해 기설정된 주파수(frequency)이며, B_optical는 광학적 링크(300)에 대해 기설정된 대역폭(bandwidth)이다.

이때, 경로 해제 설정 모듈(223)은 경로 해제 패킷의 제 2 필드(P32)(즉, TTL field)에 경로 해제 시간의 값을 저장하여 전송한다. 이러한, 경로 해제 패킷은 경유하는 각 라우팅 장치마다 패킷 전송 처리 모듈(215)로 전송된다.

한편, 전송하는 데이터의 양이 많아지면 경로 해제 시간(C_tx)이 커지며, 이에 따라 경로 해제 패킷 내의 TTL filed에 경로 해제 시간을 표시하는데 사용되는 비트(bit)가 늘어날 수 있다. 이는, 전기적 링크(400)에 대한 사용량(예를 들어, 'bus size')을 증가시킬 수 있으므로, TTL field의 비트 수를 한정시킬 필요가 있다.

이를 위해, 경로 해제 설정 모듈(223)은 하기 수학식 3과 같이, TTL field가 가질 수 있는 최대 값을 C_max로 정의하고, C_tx가 C_max보다 클 경우 출발지 라우팅 장치(즉, 경로 해제 설정 모듈(223)) 내에서 C_tx를 감소시키다가 C_tx가 C_max가 될 때 경로 해제 패킷을 전송한다.

<수학식 3>

상기 수학식 3에서, C_max는 경로 해제 패킷이 전기적 경로 상으로 이동하는데 걸리는 총 클록 사이클(clock cycle)이고, S _aps 는 각 라우팅 장치(200)의 전기적 라우터에서 복수의 방향 별 패킷 출력 포트를 스위칭하는데 필요한 사이클(cycle) 이다.

이에 따라, 경로 해제 설정 모듈(223)은 C_tx가 C_max보다 작은 경우, 데이터 전송 모듈(221)의 데이터 전송 시작 시에 TTL field에 C_tx값이 포함된 경로 해제 패킷을 전송한다. 반면에, 경로 해제 설정 모듈(223)은 C_tx가 C_max보다 큰 경우, 데이터 전송 모듈(221)의 데이터 전송 시작 이후에 C_tx를 점차 감소시키고, 감소된 C_tx가 C_max와 같아진 시점에 TTL field에 C_max 값이 포함된 경로 해제 패킷을 전송한다.

데이터 수신부(230)는 설정된 광학적 경로를 통해 출발지 PE(100)로부터 전송된 데이터를 수신하고, 수신된 데이터를 자신과 매칭 연결된 PE(100)로 전달한다. 이때, 데이터 수신부(240)는 현재 라우팅 장치가 목적지 라우팅 장치인 경우, 상기 수신된 데이터를 매칭된 PE(100)로 전달한다.

경로 해제 처리부(240)는 패킷 전송 처리 모듈(215)로부터 경로 해제 시간 정보를 수신하고, 경로 해제 시간 정보에 따른 대기 시간이 경과하면 자동으로 현재 라우팅 장치의 경로 설정 상태를 해제한다.

이때, 경로 해제 처리부(240)는 해당 경로 해제 패킷이 도착한 시각의 TTL field 값을 저장하고, 저장된 TTL field 값을 매 클록(clock)마다 감소시킨다.

또한, 경로 해제 처리부(240)는 다음 라우팅 장치로 전달할 경로 해제 패킷에 포함시킬 경로 해제 시간을 기설정된 값만큼 감소시켜, 패킷 전송 처리 모듈(215)로 전달한다. 이에 따라, 목적지 라우팅 장치에 가까워질수록 라우팅 장치에 저장되는 TTL field 값이 점점 작아진다. 이처럼, 각 라우팅 장치에 저장되는 TTL field 값은 서로 상이한 값으로서, 결과적으로, 경로 상의 라우팅 장치들은 같은 시각에 경로 해제 시간이 '0'이 되고, 그와 동시에 해당 광학적 경로는 해제된다.

만약, 경로 해제 패킷에 저장된 경로 해제 시간이 목적지 라우팅 장치까지 전송되지 않은 상태에서 '0'이 된 경우, 해당 경로 해제 패킷을 수신한 라우팅 장치는 경로 해제 패킷을 수신한 즉시 전송 경로를 해제시킨다.

이하, 도 11을 참조하여 본 발명의 일 실시예에 따른 라우팅 장치(200)를 통한 적응적 라우팅 방법을 설명하도록 한다.

도 11은 본 발명의 일 실시예에 따른 적응적 라우팅 방법을 설명하기 위한 순서도이다.

도 11에서와 같이, 전기적 링크(400)를 통해서 다른 라우팅 장치로부터 컨트롤 패킷을 수신한다(S110).

그런 후, 수신된 컨트롤 패킷의 유형을 판단한다(S120).

상기 유형을 판단한 결과 경로 설정 패킷인 경우, 상기 경로 설정 패킷에 기초하여 목적지를 향한 방향으로 인접한 다음 라우팅 장치를 결정한다(S130).

이때, 상기 다음 라우팅 장치가 사용 불가능한 상태인 경우 상기 경로 설정 패킷에 대한 롤백 처리를 결정하되, 반면에 상기 다음 라우팅 장치가 사용 가능한 상태인 경우 상기 경로 설정 패킷을 상기 다음 라우팅 장치로 전송한다.

그런 다음, 상기 다음 라우팅 장치의 사용 상태를 확인하여, 경로 설정 패킷에 대한 롤백(rollback) 처리 여부를 결정한다(S140).

이때, 상기 다음 라우팅 장치는 기설정된 출발지로부터 목적지까지의 복수의 최단 거리 경로 중 어느 하나의 최단 거리 경로 상에서 결정된다.

그리고, 상기 이전 라우팅 장치로부터 상기 컨트롤 패킷이 수신된 방향이 기설정된 우선 경로 설정 진행 방향(즉, 본 발명의 일 실시예에서는 'X축' 방향)이되 상기 컨트롤 패킷이 롤백된 상기 경로 설정 패킷인 경우, 우선 경로 진행 방향을 제외한 다른 방향(즉, Y축 방향)으로 인접한 라우팅 장치를 상기 다음 라우팅 장치로 결정한다.

또한, 롤백된 경로 설정 패킷이 경유하지 않은 우회 경로 상에서 상기 다음 라우팅 장치를 결정하는 경우, 상기 경로 설정 패킷에 저장된 롤백 위치 정보 및 목적지 위치 정보에 기초하여, 현재 라우팅 장치보다 롤백 처리가 시작된 라우팅 장치가 목적지에 근접한지 여부를 판단한다. 그런 후, 롤백 처리가 시작된 라우팅 장치가 현재 라우팅 장치보다 목적지에 근접한 경우, 우선 경로 설정 진행 방향을 제외한 다른 축 방향으로 인접한 라우팅 장치를 다음 라우팅 장치로 결정한다.

그런 다음, 상기 경로 설정 패킷에 대한 롤백 처리가 결정되면, 경로 설정 패킷이 입력된 이전 라우팅 장치로 해당 경로 설정 패킷을 롤백시킨다(S150).

참고로, 상기 단계 (S150)에서 롤백된 경로 설정 패킷은 상기 이전 라우팅 장치에서 재결정된 우회 경로 상의 다른 라우팅 장치로 전송된다.

한편, 다른 라우팅 장치로부터 경로 설정 패킷을 수신한 경우, 경로 설정 패킷에 기초하여 기설정된 목적지와 현재 라우팅 장치의 위치를 비교하고, 현재 라우팅 장치가 목적지인 것으로 판단되면, 연결된 PE(100)의 사용 상태를 확인한다. 그런 후, PE(100)가 사용 불가능한 상태인 경우, 기설정된 출발지로 상기 경로 설정 패킷에 대한 경로 설정을 취소하는 캔슬 패킷을 전기적 링크를 통해 전송할 수 있다.

또한, 다른 라우팅 장치로부터 캔슬 패킷을 수신한 경우, 기설정된 지연 시간 산출 조건에 따라 지연 시간을 산출하고, 산출된 지연 시간이 경과한 후 상기 전기적 링크를 통해 사전에 경로 설정이 취소된 경로 설정 패킷을 재전송할 수 있다.

또한, 상기 단계를 통해 기설정된 출발지와 상기 목적지 간에 경로 설정이 완료되면, 출발지의 PE가 광학적 링크를 통한 데이터의 전송을 시작하고, 출발지의 라우팅 장치가 설정이 완료된 경로 상의 전기적 링크를 통해 경로 해제 시간 정보를 포함하는 경로 해제 패킷을 목적지까지 전송한다. 이때, 경로 해제 시간 정보에 따른 경로 해제 시간은 목적지에 가까워질수록 감소된다.

그리고, 경로 해제 패킷을 목적지까지 전송할 시에, 상기 데이터의 크기, 상기 광학적 링크의 대역폭 및 상기 전기적 링크의 주파수에 기초하여 상기 경로 해제 시간을 산출하고, 산출된 경로 해제 시간이 기설정된 경로 해제 시간의 최대 값보다 큰 경우, 데이터의 전송이 시작된 후 상기 산출된 경로 해제 시간을 점차 감소시키고, 감소시킨 경로 해제 시간이 경로 해제 시간의 최대 값과 같아지면, 경로 해제 시간의 최대 값을 포함하는 상기 경로 해제 패킷을 상기 목적지까지 전송할 수 있다.

본 발명의 일 실시예는 컴퓨터에 의해 실행되는 프로그램 모듈과 같은 컴퓨터에 의해 실행 가능한 명령어를 포함하는 기록 매체의 형태로도 구현될 수 있다. 컴퓨터 판독 가능 매체는 컴퓨터에 의해 액세스될 수 있는 임의의 가용 매체일 수 있고, 휘발성 및 비휘발성 매체, 분리형 및 비분리형 매체를 모두 포함한다. 또한, 컴퓨터 판독가능 매체는 컴퓨터 저장 매체 및 통신 매체를 모두 포함할 수 있다. 컴퓨터 저장 매체는 컴퓨터 판독가능 명령어, 데이터 구조, 프로그램 모듈 또는 기타 데이터와 같은 정보의 저장을 위한 임의의 방법 또는 기술로 구현된 휘발성 및 비휘발성, 분리형 및 비분리형 매체를 모두 포함한다. 통신 매체는 전형적으로 컴퓨터 판독가능 명령어, 데이터 구조, 프로그램 모듈, 또는 반송파와 같은 변조된 데이터 신호의 기타 데이터, 또는 기타 전송 메커니즘을 포함하며, 임의의 정보 전달 매체를 포함한다.

전술한 본 발명의 설명은 예시를 위한 것이며, 본 발명이 속하는 기술분야의 통상의 지식을 가진 자는 본 발명의 기술적 사상이나 필수적인 특징을 변경하지 않고서 다른 구체적인 형태로 쉽게 변형이 가능하다는 것을 이해할 수 있을 것이다. 그러므로 이상에서 기술한 실시예들은 모든 면에서 예시적인 것이며 한정적이 아닌 것으로 이해해야만 한다. 예를 들어, 단일형으로 설명되어 있는 각 구성 요소는 분산되어 실시될 수도 있으며, 마찬가지로 분산된 것으로 설명되어 있는 구성 요소들도 결합된 형태로 실시될 수 있다.

본 발명의 범위는 상기 상세한 설명보다는 후술하는 특허청구범위에 의하여 나타내어지며, 특허청구범위의 의미 및 범위 그리고 그 균등 개념으로부터 도출되는 모든 변경 또는 변형된 형태가 본 발명의 범위에 포함되는 것으로 해석되어야 한다.

10: 하이브리드 광학 네트워크 온 칩 시스템
100: 처리 소자
200: 라우팅 장치
300: 광학적 경로
400: 전기적 경로

Claims (20)

1. 하이브리드 광학 네트워크 온 칩(Hybrid Optical Network-on-Chip, HONoC)에서 복수의 처리 소자(Processing Element, PE) 별로 연결된 라우팅 장치에 있어서,
   전기적 링크를 통해 경로 설정을 위한 컨트롤 패킷을 수신하고, 상기 컨트롤 패킷을 기설정된 유형에 따라 분배하여 출력하는 패킷 분배 모듈;
   상기 패킷 분배 모듈로부터 출력된 상기 컨트롤 패킷 중 경로 설정 패킷을 수신하면, 기설정된 목적지를 향한 방향으로 인접한 다음 라우팅 장치를 결정하고, 상기 다음 라우팅 장치의 사용 상태에 따라 상기 경로 설정 패킷에 대한 롤백(rollback) 처리 여부를 결정하는 경로 설정 처리 모듈;
   상기 경로 설정 처리 모듈에 의해 상기 경로 설정 패킷에 대한 롤백 처리가 결정되면, 상기 경로 설정 패킷이 입력된 이전 라우팅 장치로 상기 경로 설정 패킷을 롤백시키는 롤백 처리 모듈; 및
   상기 목적지와 현재 라우팅 장치의 위치 비교를 통해 현재 라우팅 장치가 상기 목적지인 것으로 판단되면, 연결된 상기 PE의 사용 상태를 확인하고 상기 PE가 사용 불가능한 상태인 경우 기설정된 출발지로 상기 경로 설정 패킷에 의한 경로 설정을 취소하는 캔슬 패킷을 상기 전기적 링크를 통해 전송하는 캔슬 처리 모듈을 포함하고,
   상기 이전 라우팅 장치로 롤백시킨 상기 경로 설정 패킷은, 상기 이전 라우팅 장치가 재결정한 우회 경로 상의 다른 라우팅 장치로 전송되는 적응적 라우팅 장치.
2. 제 1 항에 있어서,
   상기 경로 설정 처리 모듈은,
   상기 다음 라우팅 장치가 사용 불가능한 상태인 경우 상기 경로 설정 패킷에 대한 롤백 처리를 결정하고,
   상기 다음 라우팅 장치가 사용 가능한 상태인 경우 상기 경로 설정 패킷을 상기 다음 라우팅 장치로 전송하는 적응적 라우팅 장치.
3. 제 1 항에 있어서,
   상기 경로 설정 처리 모듈은,
   기설정된 출발지로부터 상기 목적지까지의 복수의 최단 거리 경로 중 어느 하나의 최단 거리 경로 상에서 상기 다음 라우팅 장치를 결정하는 적응적 라우팅 장치.
4. 제 1 항에 있어서,
   상기 경로 설정 처리 모듈은,
   상기 컨트롤 패킷을 입력받는 복수의 축(axis) 방향 중 일축 방향을 다른 축 방향들에 비해 우선적인 경로 설정 진행 방향으로 결정하되,
   상기 우선적인 경로 설정 진행 방향으로부터 롤백된 상기 경로 설정 패킷을 수신하면, 상기 우선적인 경로 설정 진행 방향을 제외한 다른 축 방향으로 인접한 라우팅 장치를 상기 다음 라우팅 장치로 결정하는 적응적 라우팅 장치.
5. 제 4 항에 있어서,
   상기 경로 설정 처리 모듈은,
   다른 라우팅 장치로부터 롤백된 상기 경로 설정 패킷이 경유하지 않은 우회 경로를 탐색하는 경우,
   상기 경로 설정 패킷에 저장된 상기 경로 설정 패킷에 대한 롤백 처리가 시작된 라우팅 장치의 위치 정보 및 목적지 위치 정보에 기초하여, 현재 라우팅 장치보다 상기 롤백 처리가 시작된 라우팅 장치가 상기 목적지에 근접한지 여부를 판단하고,
   상기 롤백 처리가 시작된 라우팅 장치가 상기 현재 라우팅 장치보다 상기 목적지에 근접한 경우, 상기 우선적인 경로 설정 진행 방향을 제외한 다른 축 방향으로 인접한 라우팅 장치를 상기 다음 라우팅 장치로 결정하는 적응적 라우팅 장치.
6. 삭제
7. 제 1 항에 있어서,
   상기 패킷 분배 모듈로부터 출력된 상기 컨트롤 패킷 중 상기 캔슬 패킷을 수신하면 기설정된 지연 시간 산출 조건에 따라 지연 시간을 산출하고,
   상기 지연 시간이 경과한 후 상기 전기적 링크를 통해 상기 경로 설정 패킷을 재전송하는 경로 설정 지연 모듈을 더 포함하는 적응적 라우팅 장치.
8. 제 1 항에 있어서,
   상기 목적지와의 경로 설정이 완료된 후 현재 라우팅 장치와 연결된 상기 PE로부터 광학적 링크를 통한 데이터의 전송이 시작되면, 상기 전기적 링크를 통해 경로 해제 시간 정보를 포함하는 경로 해제 패킷을 상기 목적지까지의 경로 상에 위치한 다른 라우팅 장치로 전송하는 경로 해제 설정 모듈을 더 포함하되,
   상기 경로 해제 시간 정보에 따른 경로 해제 시간은, 상기 목적지에 가까워질수록 감소되는 적응적 라우팅 장치.
9. 제 8 항에 있어서,
   상기 경로 해제 설정 모듈은,
   상기 데이터의 크기, 상기 광학적 링크의 대역폭 및 상기 전기적 링크의 주파수에 기초하여 상기 경로 해제 시간을 산출하되,
   상기 산출된 경로 해제 시간이 기설정된 경로 해제 시간의 최대 값보다 큰 경우, 상기 데이터의 전송이 시작된 후 상기 산출된 경로 해제 시간을 점차 감소시켜 상기 경로 해제 시간의 최대 값과 같아지면, 상기 경로 해제 시간의 최대 값을 포함하는 상기 경로 해제 패킷을 전송하는 적응적 라우팅 장치.
10. 제 1 항에 있어서,
    상기 패킷 분배 모듈로부터 출력된 상기 컨트롤 패킷 중 경로 해제 패킷을 수신하면,
    상기 경로 해제 패킷이 수신된 시각에 상기 경로 해제 패킷에 포함된 경로 해제 시간 정보를 저장한 후 시간 경과에 따라 감소시켜, 경로 해제 시간 정보에 따른 시간이 경과하면 현재 설정된 경로를 해제시키는 경로 해제 처리부를 더 포함하는 적응적 라우팅 장치.
11. 하이브리드 광학 네트워크 온 칩(Hybrid Optical Network-on-Chip, HONoC)에서 복수의 처리 소자(Processing Element, PE) 별로 연결된 라우팅 장치를 통한 적응적 라우팅 방법에 있어서,
    (a) 전기적 링크를 통해 제 1 라우팅 장치로부터 컨트롤 패킷을 수신하는 단계;
    (b) 상기 컨트롤 패킷의 유형을 판단하는 단계;
    (c) 상기 유형을 판단한 결과 경로 설정 패킷인 경우, 상기 경로 설정 패킷에 기초하여 상기 제 1 라우팅 장치와 인접한 라우팅 장치 중 기설정된 목적지를 향한 방향의 제 2 라우팅 장치를 결정하는 단계;
    (d) 상기 제 2 라우팅 장치의 사용 상태를 확인하여, 상기 사용 상태에 따라 상기 경로 설정 패킷에 대한 롤백(rollback) 처리 여부를 결정하는 단계; 및
    (e) 상기 경로 설정 패킷에 대한 롤백 처리가 결정되면, 상기 제 1 라우팅 장치로 상기 경로 설정 패킷을 롤백 시키는 단계를 포함하고,
    상기 롤백시킨 경로 설정 패킷은 상기 제 1 라우팅 장치에서 재결정된 우회 경로 상의 제 3 라우팅 장치로 전송되며,
    상기 (b) 단계 이후에,
    상기 유형을 판단한 결과 경로 설정 패킷인 경우, 상기 경로 설정 패킷에 기초하여 기설정된 목적지와 현재 라우팅 장치의 위치를 비교하는 단계;
    상기 비교의 결과, 상기 현재 라우팅 장치가 상기 목적지인 것으로 판단되면, 연결된 PE의 사용 상태를 확인하는 단계; 및
    상기 PE가 사용 불가능한 상태인 경우, 상기 경로 설정 패킷에 대한 경로 설정을 취소하는 캔슬 패킷을 상기 전기적 링크를 통해 기설정된 출발지로 전송하는 단계를 더 포함하는 적응적 라우팅 방법.
12. 제 11 항에 있어서,
    상기 (d) 단계는,
    상기 제 2 라우팅 장치가 사용 불가능한 상태인 경우 상기 경로 설정 패킷에 대한 롤백 처리를 결정하고,
    상기 제 2 라우팅 장치가 사용 가능한 상태인 경우 상기 경로 설정 패킷을 상기 제 2 라우팅 장치로 전송하는 적응적 라우팅 방법.
13. 제 11 항에 있어서,
    상기 (c) 단계는,
    기설정된 출발지로부터 상기 목적지까지의 복수의 최단 거리 경로 중 어느 하나의 최단 거리 경로 상에서 상기 제 2 라우팅 장치를 결정하는 적응적 라우팅 방법.
14. 제 11 항에 있어서,
    상기 (c) 단계는,
    상기 컨트롤 패킷이 롤백된 상기 경로 설정 패킷인 경우,
    상기 롤백된 경로 설정 패킷이 수신된 방향이 기설정된 우선 경로 설정 진행 방향이면, 상기 우선 경로 진행 방향을 제외한 다른 방향으로 인접한 라우팅 장치를 상기 제 2 라우팅 장치로 결정하며,
    상기 우선 경로 설정 진행 방향은, 상기 컨트롤 패킷을 입력받는 복수의 축(axis) 방향 중 다른 축 방향들에 비해 우선적으로 경로 설정 진행 방향으로 설정되는 일축 방향인 적응적 라우팅 방법.
15. 제 14 항에 있어서,
    상기 (c) 단계는,
    다른 라우팅 장치로부터 롤백된 상기 경로 설정 패킷이 경유하지 않은 우회 경로 상에서 상기 제 2 라우팅 장치를 결정하는 경우,
    상기 경로 설정 패킷에 저장된 상기 경로 설정 패킷에 대한 롤백 처리가 시작된 라우팅 장치의 위치 정보 및 목적지 위치 정보에 기초하여, 현재 라우팅 장치보다 상기 롤백 처리가 시작된 라우팅 장치가 상기 목적지에 근접한지 여부를 판단하고,
    상기 롤백 처리가 시작된 라우팅 장치가 상기 현재 라우팅 장치보다 상기 목적지에 근접한 경우, 상기 우선 경로 설정 진행 방향을 제외한 다른 축 방향으로 인접한 라우팅 장치를 상기 제 2 라우팅 장치로 결정하는 적응적 라우팅 방법.
16. 삭제
17. 제 11 항에 있어서,
    상기 (b) 단계 이후에,
    상기 유형을 판단한 결과 캔슬 패킷인 경우, 기설정된 지연 시간 산출 조건에 따라 지연 시간을 산출하는 단계; 및
    상기 산출된 지연 시간이 경과한 후 상기 전기적 링크를 통해 사전에 경로 설정이 취소된 경로 설정 패킷을 재전송하는 단계를 더 포함하는 적응적 라우팅 방법.
18. 제 11 항에 있어서,
    상기 (e) 단계 이후에,
    기설정된 출발지와 상기 목적지 간에 경로 설정이 완료되면, 출발지의 상기 PE가 광학적 링크를 통한 데이터의 전송을 시작하는 단계; 및
    상기 출발지의 라우팅 장치가 설정이 완료된 경로 상의 상기 전기적 링크를 통해 경로 해제 시간 정보를 포함하는 경로 해제 패킷을 상기 목적지까지 전송하는 단계를 포함하되,
    상기 경로 해제 시간 정보에 따른 경로 해제 시간은, 상기 목적지에 가까워 질수록 감소되는 적응적 라우팅 방법.
19. 제 18 항에 있어서,
    상기 경로 해제 패킷을 상기 목적지까지 전송하는 단계는,
    상기 데이터의 크기, 상기 광학적 링크의 대역폭 및 상기 전기적 링크의 주파수에 기초하여 상기 경로 해제 시간을 산출하는 단계;
    상기 산출된 경로 해제 시간이 기설정된 경로 해제 시간의 최대 값보다 큰 경우, 상기 데이터의 전송이 시작된 후 상기 산출된 경로 해제 시간을 점차 감소시키는 단계; 및
    상기 감소시킨 경로 해제 시간이 상기 경로 해제 시간의 최대 값과 같아지면, 상기 경로 해제 시간의 최대 값을 포함하는 상기 경로 해제 패킷을 상기 목적지까지 전송하는 단계를 포함하는 적응적 라우팅 방법.
20. 하이브리드 광학 네트워크 온 칩(Hybrid Optical Networks-on-Chip) 시스템에 있어서,
    복수의 처리 소자(Processing Element, PE); 및
    상기 PE 별로 매칭되며, 광학적 링크를 통해 상기 PE 간 데이터의 전송을 위한 서킷 스위칭을 처리하고, 전기적 링크를 통해 상기 PE 간 경로 설정을 위한 패킷 스위칭을 처리하는 복수의 라우팅 장치를 포함하되,
    상기 라우팅 장치는,
    상기 전기적 링크를 통해 경로 설정을 위한 컨트롤 패킷을 수신하여 기설정된 유형에 따라 분배하여 출력하고, 상기 컨트롤 패킷 중 경로 설정 패킷을 수신하면 기설정된 목적지를 향한 방향으로 인접한 다음 라우팅 장치를 결정하고, 상기 다음 라우팅 장치가 사용 불가능한 상태이면 상기 경로 설정 패킷이 입력된 이전 라우팅 장치로 상기 경로 설정 패킷을 롤백(rollback) 처리하고,
    상기 목적지와 현재 라우팅 장치의 위치 비교를 통해 상기 현재 라우팅 장치가 상기 목적지인 것으로 판단되면, 연결된 PE의 사용 상태를 확인하여 상기 PE가 사용 불가능한 상태인 경우 기설정된 출발지로 상기 경로 설정 패킷에 의한 경로 설정을 취소하는 캔슬 패킷을 상기 전기적 링크를 통해 전송하되,
    상기 이전 라우팅 장치로 롤백 처리된 상기 경로 설정 패킷은, 상기 이전 라우팅 장치가 재결정한 우회 경로 상의 다른 라우팅 장치로 전송되는 하이브리드 광학 네트워크 온 칩 시스템.
    

Images