W pracy przedstawiono teorię pól komutacyjnych, w których można realizować połączenia rozgłoszeniowe (między jednym wejściem a wieloma wyjściami pola). Skupiono się na dwóch popularnych strukturach pól komutacyjnych – wielopłaszczyznowych polach typu banyan i trzysekcyjnych polach Closa, na strategiach realizacji połączeń rozgłoszeniowych w polach komutacyjnych. Strategie te wykorzystują zarówno właściwości fizyczne pojedynczych komutatorów użytych do budowy pola, jak również specjalizowane algorytmy wyboru drogi połączeniowej. Zaprezentowano dotychczasowe algorytmy wykorzystywane do zestawiania połączeń rozgłoszeniowych w polach typu banyan i w polach Closa. Dla pól typu banyan usystematyzowano opis i zapis dotychczas znanych strategii. Dla pól Closa pokazano opis zaproponowany przez Hwanga oraz Yang i Wanga. W tej pracy zaproponowano modyfikację algorytmu opartego na koncepcji okien blokowania dla pól typu banyan w taki sposób, aby zestawienie nowego połączenia rozgłoszeniowego powodowało zablokowanie jak najmniejszej liczby możliwych przyszłych połączeń w polu wielopłaszczyznowym. W pracy rozważane są również trzysekcyjne pola Closa. Strategia wykrzystująca algorytm oparty na koncepcji okien blokowania nie była do tej pory szeroko rozważana w polach Closa. W pracy zaprezentowano nowy algorytm i w wyniku badań symulacyjnych sprawdzono, czy rozwiązanie, które zapewnia najmniejsze wartości współczynników strat w polach typu banyan, osiąga najlepsze wyniki także w polach Closa. Opierając się na rezultatach dotyczących pól Closa, zaproponowano nowy algorytm wyboru drogi połączeniowej w polach typu banyan. Nowy algorytm wykorzystuje koncepcję podziału połączenia rozgłoszeniowego na podpołączenia w sposób nieusystematyzowany i stąd zaproponowano dla niego nazwę – algorytm ze spontanicznym podziałem na podpołączenia. Zaprezentowano wyniki działania nowego algorytmu i porównano je z wynikami osiąganymi przez algorytm macierzowy.

Streszczenie 7 Wykaz skrótów 9 Wykaz symboli 11 Przedmowa 17 1. Wprowadzenie 19 1.1. Wstęp 19 1.2. Telekomutacja 19 1.2.1. Typy telekomutacji 19 1.2.2. Funkcja pól komutacyjnych w sieciach telekomunikacyjnych 24 1.3. Właściwości kombinatoryczne pól 26 1.3.1. Teoria telekomutacji a kombinatoryka 26 1.3.2. Pola blokowalne 27 1.3.3. Rodzaje nieblokowalności pól 28 1.4. Struktury pól komutacyjnych 29 1.5. Koszt budowy pól 38 1.6. Połączenia między większą liczbą wejść i wyjść pola komutacyjnego 41 1.6.1. Wielopołączenia 41 1.6.2. Poła˛czenia rozgłoszeniowe 43 1.6.3. Strategie realizacji połączeń rozgłoszeniowych 45 1.6.4. Algorytm oparty na koncepcji okien blokowania 49 1.7. Zakres tematyczny pracy 50 2. Pola typu banyan 53 2.1. Wstęp 53 2.2. Struktura pól typu banyan 54 2.3. Blokowalność pól typu banyan 61 2.3.1. Konflikt połączeń 61 2.3.2. Graf krzyżujących się scieżek 63 2.4. Warunki nieblokowalności pól typu banyan dla połączeń typu punkt-punkt 66 2.4.1. Nieblokowalność w wąskim sensie 66 2.4.2. Przestrajalność 67 2.4.3. Nieblokowalność w szerokim sensie 68 2.5. Warunki nieblokowalności pól typu banyan dla połączeń rozgłoszeniowych 70 2.5.1. Nieblokowalność w wąskim sensie 70 2.5.2. Nieblokowalność w szerokim sensie 70 3. Połączenia rozgłoszeniowe w polach komutacyjnych typu banyan 75 3.1. Model pola 75 3.1.1. Formalny opis struktury pola typu baseline 75 3.1.2. Relacja typu punkt-punkt 77 3.1.3. Blokowanie relacji 79 3.1.4. Relacja rozgłoszeniowa 83 3.2. Reprezentacja stanu pól typu banyan 85 3.2.1. Macierz blokowanych relacji – macierz B 85 3.2.2. Stan płaszczyzn pola wielopłaszczyznowego – macierze M 86 3.2.3. Obszar blokowania w macierzach M 86 3.2.4. Podstawowe zasady zestawiania połączeń rozgłoszeniowych w wielopłaszczyznowych polach typu banyan 88 3.3. Dotychczasowe strategie zestawiania połączeń rozgłoszeniowych 92 3.3.1. Metastrategie realizacji połączeń rozgłoszeniowych 92 3.3.2. Parametry metastrategii 93 3.3.3. Opis metastrategii przy użyciu pojęcia okna blokowania 97 3.4. Nowa strategia realizacji połączeń rozgłoszeniowych w polach wielopłaszczyznowych 99 3.4.1. Wstęp 99 3.4.2. Liczba relacji rozgłoszeniowych w polu 100 3.4.3. Liczba blokowanych relacji 103 3.4.4. Całkowita liczba blokowanych relacji 105 3.4.5. Wyznaczanie całkowitej liczby blokowanych relacji 107 3.4.6. Nowy algorytm oparty na koncepcji okien blokowania z liczeniem blokowanych relacji 108 3.5. Porównanie wyników działania nowej strategii realizacji połączeń rozgłoszeniowych z dotychczasowymi strategiami 111 3.6. Podsumowanie 114 4. Połączenia rozgłoszeniowe w polach Closa 115 4.1. Wstęp 115 4.2. Struktura pola Closa 116 4.3. Definicje w polach Closa 117 4.3.1. Definicje relacji typu punkt-punkt i relacji rozgłoszeniowej 117 4.3.2. Pojęcie okna blokowania w polach Closa 118 4.3.3. Definicje poła˛czenia rozgłoszeniowego i podpołączeń w polach Closa 119 4.4. Dotychczasowe strategie realizacji połączeń rozgłoszeniowych w trzysekcyjnych polach Closa 119 4.4.1. Metastrategia realizacji połączeń rozgłoszeniowych 119 4.4.2. Algorytmy wyboru drogi poła˛czeniowej w dotychczasowych strategiach 124 4.5. Nowa strategia realizacji poła˛czen´ rozgłoszeniowych w polach Closa 129 4.5.1. Reprezentacja stanu pola Closa 129 4.5.2. Zasada działania nowego algorytmu 131 4.5.3. Algorytm uproszczony 135 4.6. Porównanie działania algorytmów wyboru drogi poła˛czeniowej w polach Closa 138 4.7. Podsumowanie 143 5. Nowy algorytm wyboru płaszczyzn w polach typu banyan 145 5.1. Wstęp 145 5.2. Spontaniczny podział poła˛czenia rozgłoszeniowego na podpołączenia 145 5.3. Wyniki działania nowego algorytmu 150 Podsumowanie 155 Dodatek 159 A. Modele symulacyjne 161 B. Porównanie złożoności czasowej strategii realizacji połączeń rozgłoszeniowych 163 B.1. Strategie w polach typu banyan 163 B.2. Strategie w polach Closa 164 Bibliografia 167 Spis rysunków 181 Spis tabel 187 Summary 189

Koszyk

Strategie realizacji połączeń rozgłoszeniowych w polach komutacyjnych