Wyniki wyszukiwania - BazTech

1

Deflection routing in an all-optical network in 2D grid : performance evaluation

Borrero A., Quessette F.

Theoretical and Applied Informatics

|

2006

|

Vol. 18, nr 3

213-236

EN

In this work, we study a deflection routing strategy for the emerging generation of networks, all-optical networks. This investigation is made in order to evaluate the performance of a heuristical deflection routing strategy, known as "Scale Routing", on a synchronous network in a ID grid. We have used this routing strategy to attempt to find the optimal route, even though the packet were deflected. In this case, optimal route does not mean the shortest path, (although in many cases it comes near to it), nor the path with the minimum number of deflections. But it means the route that provides in each slot, in every node, the largest number of selection possibilities. This algorithm is known as the "scale routing algorithm". Furthermore, we add some heuristics to choose the packet(s) to be deflected. The first one is based on the rcmaining distance until its destination node, and the second one is based on the number of deflections that it has already had. Then we have modified the destination given to the packets. At first, it has been a uniform distribution, then a non uniform distribution directed towards a corner and at last a non uniform distribution directed towards the center of the grid. Finally some statistics and curves are presented to be analyzed and to compare the performances of this strategy with the different heuristics and the variation on the traffic. We have got all this results by simulation. For this work, we have used QNAP II modelling tool [14] to design the simulator.

PL

W artykule omawiana jest strategia trasowania z wymuszoną zmianą drogi (Deflection routing), zwaną w artykule odbiciem dla pojawiającej się nowej technologii sieci, jaką są sieci w pełni optyczne. Wymuszona zmiana drogi wynika z braku możliwości kolejkowania pakietów w węzłach optycznych. Jeśli do węzła przychodzi więcej pakietów, niż może być wysłane w prawidłowym dla nich kierunku, niektóre muszą być wysłane (odbite) w innym kierunku, aby nie uległy zniszczeniu. W artykule, dla synchronicznych sieci typu siatka 2D, badano wydajność heurystycznej metody takiego routingu, znanej routingiem ze skalowaniem (scale routing). Strategia ta została wypróbowana dla znajdowania optymalnej ścieżki dla pakietów, które mogły zostać po drodze odbite. W przypadku odbicia pakietu ścieżka optymalna nie oznacza ścieżki najkrótszej (choć w wielu przypadkach przebiega blisko takiej ścieżki) ani ścieżki z najmniejszą liczbą odbić. Oznacza ścieżkę, która dla każdego węzła znajdującego się na drodze pakietu zapewnia największą możliwą liczbę kolejnych ścieżek do wyboru. Taki algorytm nazywa się algorytmem routingu ze skalowaniem. Ponadto dodane zostały pewne heurystyki wybierania, który pakiet (pakiety) zostaną w weźle odbite. Pierwsza z nich opiera się na pozostałym do pokonania dystansie do węzła docelowego, druga bierze pod uwagę liczbę odbić, którą pakiet doświadczyłjuż w sieci. Modyfikowany byłsposób wyboru węzłów docelowych dla pakietów. Na początku miał on rozkład równomierny, następnie zbadano rozkłady nierównomierne. Pakiety zostały skierowane do jednego z rogów siatki węzłów, następnie pakiety kierowane były do środka siatki. Zostały zaprezentowane i przeanalizowane określone statystyki i wykresy oraz porównano wyniki z zastosowanymi heurystykami i różnymi rodzajami ruchu pakietów. Wszystkie wyniki zostały uzyskane za pomocą badań symulacyjnych, z wykorzystaniem narzędzia QNAPII.

2

Performance evaluation of multistage interconnection networks with blocking--discrete and continuous time Markov models

Badrah A., Czachórski T., Domańska D., Fourneau J.-M., Quessette F.

Archiwum Informatyki Teoretycznej i Stosowanej

|

2002

|

T. 14, z. 2

145-161

EN

We analyse the performances of building blocks of multistage interconnection networks with blocking. Both continuous and discrete time Markov models are used to study the behavior of such entities in presence of various types of input streams. It is shown that the states of the queues within the entity are correlated due to the blocking phenomena.

PL

Artykuł opisuje użycie łańcucha Markowa do analizy wydajności bloków, z których zbudowana jest wielostanowiskowa sieć połączeń z blokowaniem. Tego rodzaju sieć połączeń spełnia ważną rolę w procesie projektowania efektywnych architektur wieloprocesorowych. Jednakże duży rozmiar takich sieci, jak również charakterystyczne dla ich pracy zjawisko blokowania powodują, że są one bardzo trudne do analizy. Modele takich wielopoziomowych sieci są z reguły oparte na dekompozycji - poszczególne przełączniki rozważane są osobno, a prawdopodobieństwa blokowania uzyskuje się na drodze iteracyjnego dochodzenia do punktu zbieżności. W artykule zaproponowano metodę analizy opartą na dekompozycji na podsieci większe od pojedynczego przełącznika. Opisano ciągły i dyskretny model Markowa rozważanej podsieci oraz przedstawiono uzyskane wyniki numeryczne.

3

Groups of various ON/OFF sources in models of network switch solved with the method of Stochastic Automata Network

Quessette F., Tomasik J.

Archiwum Informatyki Teoretycznej i Stosowanej

|

1999

|

T. 11, z. 1

87-104

EN

In the paper the groups of various ON/OFF sources are presented with the Stochastic Automata Network formalism. The group of sources are the models of a data stream entering a wide area network. After introducing the method, the models of ON/OFF sources with phase duration distributed according to exponential distribution and according to Erlang distribution are described. The Erlang distribution has been chosen because it may approximate deterministic distribution in continuous time Markov chain. All numerical results are depicted in graphs and commented.

PL

W artykule przedstawione są za pomocą formalizmu Sieci Automatów Stochastycznych grupy różnych źródeł ON/OFF. Klienci generowani przez grupę zródeł tego typu modelują strumień pakietów na wejściu do sieci rozległej. Po zaprezentowaniu metody, w artykule przedstawione są modele źródeł ON/OFF, których długość trwania faz jest opisana zgodnie z rozkładem wykładniczym bądź rozkładem Erlanga, który służy do modelowania stałych odcinków czasu dla modeli z czasem ciągłym. Wyniki obliczeń przedstawione są w postaci graficznej i skomentowane.

4

Functional transitions in stochastic automata networks

Quessette F., Tomasik J.

Archiwum Informatyki Teoretycznej i Stosowanej

|

1999

|

T. 11, z. 1

69-85

EN

Stochastic automata networks are frequently used in defining Markovian models of computer networks. A queueing model may be represented by more then one stochastic automata network, however, functional transitions depending on a current global state are generally easier to determine. Introducing a new formula for defining a global generator allows one to calculate more easily non-zero elements during an iterative process. All stochastic automata networks representing the same queueing model lead to the same global generator and conversion may be done automatically.

PL

Automaty stochastyczne są często stosowane przy tworzeniu markowowskich modeli systemów komputerowych. Model kolejkowy może być reprezentowany przez więcej niż jedną sieć automatów stochastycznych, przy czym przeważnie sieci z tranzycjami, których wartości określone są funkcjami stanu łańcucha globalnego, z punktu widzenia użytkownika, są prostsze w konstrukcji. Wprowadzony nowy wzór dla generatora globalnego ułatwia iteracyjny proces obliczeniowy dla tranzycji funkcyjnych. Różne reprezentacje sieci automatów stochastycznych prowadzą do powstania identycznego generatora, a ich konwersja jest automatyczna.

5

Markowowskie modele wielowarstwowych przełączników sieciowych z blokowaniem.

Badrah A., Czachórski T., Domańska J., Quessette F.

Zeszyty Naukowe. Informatyka / Politechnika Śląska

|

1998

|

z. 34

325-340

PL

Artykuł opisuje użycie łańcuchów Markova do analizy wydajności bloków , z których zbudowana jest wielostanowiskowa sieć połączeń z blokowaniem. Opisano krótko wykorzystaną metodę dyskutując analityczne i numeryczne problemy związane z jej implementacją. Artykuł pokazuje, jak oszacować wydajność rozważanych bloków sieci połączeń.

EN

The article presents the use Markov chains to analyse the performancies of blocks building a multistage interconnection network with blocking. Brief description of markovian analysis with its analitical and numerical problems is given. The article shows how to evaluate performancies of the considered elements to interconnection networks.