Routing protocol creates a rounting table and packets are sent based on the routing table. Dijkstra’s shortest path algorithm finds shortest paths from the start node in OSPF, which is a famous routing protocol. When the network scale is large, calculation time of Dijkstra’s shortest path algorithm increases rapidly, so high-end CPU and memory are required. Recently, there has been an increase of research of computing based on informations such as network bandwidth or wavelength. However, it takes a long time to compute shortest paths by conventional serial processor.

Research Introduction

In our research, we propose various new parallel path search algorithms and implement them on DAPDNA-2 dynamically reconfigurable processor of IPFlex Inc. DAPDNA-2 is a dual-core processor, comprised of high-performance RISC core (DAP), paired with the DNA, a dynamically reconfigurable two-dimensional processing element matrix. The PE Matrix is an array of 376 Processing Elements which are comprised of computation units, memory, synchronizers, and counters. The PE Matrix circuitry can be reconfigured freely into the structure that is most optimal for meeting the needs of the application in demand.

Multi Path Search Algorithm (MPSA)
It’s very difficult to compute in parallel by Dijkstra’s algorithm because of need for previous calculation results. Proposed algorithm searches shortest paths in parallel using PE Matrix. Moreover, we partition the nodes in the network into different groups and merge calculation results after computing shortest paths respectively by pipeline operation. As a result of simulations, we show that calculation time of the proposed algorithm decreases compared to Dijkstra’s algorithm on DAPDNA-2.

Diorama Path Search Algorithm
In this research, we propose the route computation algorithm in a chip by converting into the virtual network in a chip that contract an actual network topology to emulate an actual router and a link. The node and the link in the network are concretely made by two or more PE(Processor Element) in DNA, and the network topology is constructed in the chip. Various topologies such as NSFNet (Nation Science Foundation) and EON (European OFF network) can be constructed by converting the configuration. The figure below shows the example of the network construction. The operation of an actual link and a node are emulated by DAPDNA-2. Emulate a packet transmission in a actual network that can be read a virtual packet from the memory in the source node, then transmitted by the virtual network in the chip, finally packet write into the memory in destination node.

Parallel Link Disjoint Path Algorithm
In next generation optical network, it is expected that the transmission request of mass data such as High Definition contents increases rapidly. The interruption which happened by link-down due to disaster causes fatal data loss. Therefore, it becomes an important issue to prepare a backup path for survivability. A backup path should have the constraint that it can’t use the same link as the primary path uses. These path pair which doesn’t uses the same link is called the link-disjoint paths. K-shortest path algorithm was widely used to calculate link-disjoint paths. However, k-shortest path algorithm is not suitable for a large-scale network because it is based on Dijkstra’s algorithm. In this research, we propose a high-speed parallel link-disjoint path search algorithm using DAPDNA-2. In our proposed algorithm, all path information which include cost and link information are collected at high speed by simultaneous multiple path search, and then the optimum link-disjoint paths are calculated from all path information.

Publication

• Hiroyuki ISHIKAWA,Sho SHIMIZU,Yutaka ARAKAWA,Naoaki YAMANAKA,Kosuke SHIBA,”Shortest Path Algorithm on Parallel Reconfigurable Processor DAPDNA-2,”Technical Report IEICE,NS2005-162,pp.17-20,March 2006
• Hiroyuki ISHIKAWA, Sho SHIMIZU, Yutaka ARAKAWA, Naoaki YAMANAKA, Kosuke SHIBA, “Parallel Shortest Path Searching Algorithm on Dynamically Reconfigurable Processor,” CPT2007 -Photonic Technologies towards the Next Decade-, pp. 119-120, January 2007.
• Hiroyuki ISHIKAWA, Sho SHIMIZU, Yutaka ARAKAWA, Naoaki YAMANAKA, Kosuke SHIBA, “New Parallel Shortest Path Searching Algorithm based on Dynamically Reconfigurable Processor DAPDNA-2,” 2007 IEEE International Conference on Communications (ICC2007), June 2007
• Hiroyuki ISHIKAWA, Sho SHIMIZU, Yutaka ARAKAWA, Naoaki YAMANAKA, and Kosuke SHIBA, “Fast calculation method of Set Cover Problem on parallel reconfigurable processor DAPDNA-2”, TECHNICAL REPORT OF IEICE, Vol. RECONF2007-62, pp. p67-72, January 2008
• Taku KIHARA, Sho SHIMIZU, Yutaka ARAKAWA, Naoaki YAMANAKA, Kosuke SHIBA, “Fast Link-Disjoint Path Algorithm on Parallel Reconfigurable Processor DAPDNA-2,” International Conference on The 14th Asia-Paciffic Conference on Communications (APCC2008), Vol. 15-PM1-C-4, October 2008
• Shan GAO, Taku KIHARA, Sho SHIMIZU, Yutaka ARAKAWA, Naoaki YAMANAKA, Kosuke SHIBA, “Traffic Engineering based on Experimentation in On-chip Virtual Network on Dyamically Reconfigurable Processor,” International Student Paper Contest , Vol. Seoul Section 2008, pp. 90-95, November 2008
• Shan GAO, Taku KIHARA, Sho SHIMIZU, Yutaka ARAKAWA, Naoaki YAMANAKA, and Kosuke SHIBA, “A Novel Network Optimization Method using On-Chip Virtual Network
  on Dynamically Reconfigurable Processor DAPDNA-2”, TECHNICAL REPORT OF IEICE, Vol. RECONF2008-38~54, pp. 69-74, November 2008
• Taku KIHARA, Sho SHIMIZU, Gao SHAN, Yutaka ARAKAWA, Naoaki YAMANAKA, and Akifumi WATANABE, “Fast Solution of Link Disjoint Path Algorithm on Parallel Reconfigurable
  Processor DAPDNA-2”, TECHNICAL REPORT OF IEICE, Vol. RECONF108, No. 414, pp. 201-206, January 2009
• Gao SHAN, Taku KIHARA, Sho SHIMIZU, Yutaka ARAKAWA, Naoaki YAMANAKA, and Akifumi WATANABE, “A Novel Traffic Engineering Method using On-Chip Diorama Network on Dynamically Reconfigurable Processor DAPDNA-2,” HPSR(High Performance Switching and Routing)2009, June 2009