GRAAL - GRAphs and ALgorithms in communication networks
Czas trwania projektu
20.11.2007 - 19.05.2009Instytucja finansująca
Ministerstwo Nauki i Szkolnictwa WyższegoStreszczenie
Projekt realizowany był w ramach Akcji COST 293 „Graphs and Algorithms in Communication Networks – GRAAL”, którego głównym celem było opracowanie projektu sieci komunikacyjnej, przy wykorzystaniu najnowszych badań, głównie z zakresu matematyki. Dodatkowym celem Akcji było stworzenie wzajemnych kontaktów specjalistów i ekspertów w zakresie komunikacji sieciowej i matematyków a przez to łatwiejsze dzielenie się doświadczeniami. Akcja prowadzona była w latach 2004 – 2008, natomiast zespół wykonawców projektu przyłączył się do prac realizowanych w ramach akcji w 2007 r. Realizacja projektu trwała od listopada 2007 r. do maja 2009 r.Głównym celem projektu było opracowanie nowej formuły algorytmu sterującego polami komutacyjnymi typu log2N, a także podanie warunków nieblokowalności w szerokim sensie (WSNB) tego typu pól przy zastosowaniu zaproponowanego algorytmu. Celem projektu było również wprowadzenie do udowodnienia warunków koniecznych i wystarczających nieblokowalności w szerokim sensie, przy zastosowaniu specjalnego algorytmu wyboru drogi połączeniowej oraz elementów teorii grafów (w szczególności zasady budowania grafów reprezentujących pola komutacyjne i połączenia w nich realizowane oraz zasady wyznaczania liczby chrominancji grafów). Projekt był realizowany przy aktywnym udziale partnerów Akcji COST 293, a w szczególności Dpto. de Matemática Aplicada IV, Universidad Politécnica de Cataluña Barcelona oraz Department of Theoretical Computer Science (DTCS) IMFM - Institute of Matchematics, Physics and Mechanics University of Ljubljana.
Podczas realizacji projektu określono zasady opisu struktury i stanu pola komutacyjnego typu log2(N, 0, p) za pomocą sekwencji deBruijna. Opracowano również nowy algorytm sterowania wyborem drogi połączeniowej w polach log2(N, 0, p). Wykazano, że dla pól o pojemnościach 16 x 16, 32 x 32 i 64 x 64 warunki nieblokowalności w wąskim i szerokim sensie są identyczne. Przy współpracy z partnerami działania COST 293 wykazano za pomocą symulacji, że dla pola o pojemności 64 x 64 nie istnieje algorytm sterujący, który pozwala na ograniczenie liczby płaszczyzn przy jednoczesnym zachowaniu nieblokowalności pola.
Ocenę możliwości implementacji sprzętowych proponowanych algorytmów sterowania przeprowadzono przy wykorzystaniu programowalnych układów FPGA. Uzyskane wynik wskazują, że algorytmy oparte na sekwencjach deBruijna są bardzo efektywne i wymagają mniejszej ilości zasobów sprzętowych, niż algorytmy oparte na macierzach stanu.
Publikacje, raporty lub patenty będące rezultatem projektu
| 04. | 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 |
| 03. | 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. |
| 02. | 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. |
| 01. | 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. |
Koordynator projektu
Arie Koster, Warwick Business School Operational Research & Management Sciences GroupKierownik projektu PP
prof. dr hab. inż. Wojciech KabacińskiUczestnicy projektu PP
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