GRAAL - GRAphs and ALgorithms in communication networks
Duration
20.11.2007 - 19.05.2009Financing entity
Ministry of Science and Higher EducationSummary
The project was implemented as part of Action COST 293 “Graphs and Algorithms in Communication Networks – GRAAL”, the main goal of which was to develop a communication network design employing the latest research, mainly in the field of mathematics. In addition, the Action aimed at creating mutual contacts between specialists and experts in network communications and mathematicians, facilitating the exchange of experience. The action was carried out in the years 2004-2008, and our team of project participants joined the action works in 2007. The project was implemented from November 2007 until May 2009.The chief goal of the project was to develop a new formula of a control algorithm for log2N switching fabrics, as well as defining the wide-sense non-blocking (WSNB) conditions of such fabrics when the proposed algorithm is applied. Another goal of the project was to present and prove the necessary and sufficient WSNB conditions using a special algorithm for selecting the connection route and elements of graph theory (particularly the principle of building graphs representing switching fabrics and connections implemented within them, and the principles of determining the graph chromaticity number). The project was carried out in active cooperation with Action COST 293 partners, particularly including Dpto. de Matemática Aplicada IV, Universidad Politécnica de Cataluña Barcelona and Department of Theoretical Computer Science (DTCS) IMFM – Institute of Mathematics, Physics and Mechanics, University of Ljubljana.
In the course of the project, principles were defined for describing the structure and state of a log2(N, 0, p) switching fabric using the de Bruijn sequence. A new control algorithm for selecting the connection route in log2(N, 0, p) switching fabrics has also been developed. It has been shown that for 16 x 16, 32 x 32 and 64 x 64 fabrics, the narrow- and wide-sense non-blocking conditions were identical. In cooperation with the partners of Action COST 293, it has been proved through simulation that for a 64 x 64 fabric, there is no control algorithm that would enable the reduction of the number of planes while preserving the non-blocking feature.
The possibility of implementing the proposed control algorithms in devices was assessed using programmable FPGA circuits. The results thus obtained show that algorithms based on deBruijn sequences are very efficient and require less equipment resources than algorithms based on state matrices.
Publications, reports or patents resulting from the project
| 01. | ] W. Kabaciński and M. Żal, “Performance Evaluation of log2N Switching Networks,” in Performance Modelling and Analysis of Heterogeneous Networks. Series: River Publishers Series in Information Sciences and Technology, vol. 2. River Publishers., pp. 73-90, 2009. ISBN: 978-87-92329-16-5 |
| 02. | G. Danilewicz, W. Kabaciński and M. Żal, “Reduced Banyan-Type Multiplane Rearrangeable Switching Networks,” IEEE Communications Letters vol. 12, no. 1, pp. 900-902, Dec. 2008. |
| 03. | Praca zbiorowa pod kierunkiem prof. dr. hab. inż. Wojciecha Kabacińskigo, “Algorytmy sterowania polami log2(N;0;p) oparte na sekwencjach deBruijna,” raport wewnętrzny nr. TR-KK-10/2/2009/P , Poznań 2009. |
| 04. | Praca zbiorowa pod kierunkiem prof. dr. hab. inż. Wojciecha Kabacińskiego, “Implementacja algorytmów sterowania wyborem drogi połączeniowej w polach log2(N,0,p) w językuVHDL,” raport wewnętrzny nr. TR-KK-3/1/2008/P , Poznań 2009. |
Supervisor/coordinator
Arie Koster, Warwick Business School Operational Research & Management Sciences GroupProject Manager (PUT)
prof. dr hab. inż. Wojciech KabacińskiProject participants (PUT)
prof. dr hab. inż. Wojciech Kabacińskidr hab. inż. Grzegorz Danilewicz, prof. nadzw.
dr hab. inż. Mariusz Żal
dr inż. Marek Michalski
dr inż. Remigiusz Rajewski