Sub-optimal routing at computer communication networks with unreliable transmission channels

• Autorzy: Grzech, A. , Kollek, R.
• Języki publikacji: EN

Abstrakty

EN

This paper is devoted to present an algorithm leading to sub-optimal solution of flow assignment task in packet-switched store-and forward communication network with unreliable communication channels. It is assumed that the sub-optimal flow may be determined based on optimal solution of flow assignment task at reliable network. It is further assumes that the knowledge of optimal flows in reliable network allows to obtain the sub-optimal flow in unreliable network in much shorter time, that time required to obtain optimal solution of flow assignment task in unreliable network. The shorter time and accuracy of the sub-optimal flow are trade-off factors of the assignment task. The quality of the sub-optimal solution depends of monitoring system supported the considered network; exactly it depends on monitoring system range, i.e., number of nodes among which the information about channel failures is distributed. Introduction of monitoring system is equivalent to possibility of dividing entire network into two sub-networks. Some simulation results illustrate the features of the proposed approach.

PL

Artykuł jest poświęcony prezentacji algorytmu prowadzącego do suboptymalnego rozwiązania przydziału strumienia zadaniom w sieciach komputerowych z przełączaniem pakietów typu zapamiętaj i prześlij z niewiarygodnymi kanałami transmisji. Założono, że prawie optymalny strumień może być określony w oparciu o optymalne rozwiązanie przydziału strumienia zadaniom w niezawodnych sieciach. Następnie założono, że wiedza o optymalnym przepływie w niezawodnych sieciach pozwala uzyskać suboptymalny strumień w sieciach niewiarygodnych w czasie krótszym niż czas wymagany do uzyskania optymalnego rozwiązania przydziału strumienia zadaniom w sieciach niewiarygodnych. Trzeba znaleźć kompromis pomiędzy dokładnością a czasem przydziału suboptymalnego strumienia. Jakość rozwiązania zależy od systemu monitorującego rozważaną sieć, a ściślej od zasięgu tego systemu, tzn. liczby węzłów, pomiędzy którymi jest rozpowszechniana informacja o błędach w kanale. Wprowadzenie systemu monitorującego jest jednoznaczne z możliwością podzielenia całej sieci na dwie podsieci. Cechy zilustrowanej aproksymacji zilustrowano wynikami kilku symulacji.

Słowa kluczowe

EN

flow control; routing; monitoring; routing related traffic

• Czasopismo: Archiwum Informatyki Teoretycznej i Stosowanej
• Rocznik: 2001
• Tom: T. 13, z. 4
• Strony: 375-387
• Opis fizyczny: Bibliogr. 14 poz., rys.

Twórcy

autor

Grzech, A.

• Institute of Control and Systems Engineering Wrocław University of Technology

autor

Kollek, R.

• Institute of Control and Systems Engineering Wrocław University of Technology

Bibliografia

• [1] Bertsekas D., Gallager R.. Data Networks, Prentice-Hall International, Inc., New Jersey 1987.
• [2] Cantor D., Gerla M., Optimal Routing in a Packet-Switched Computer, IEEE Transaction of Communication, Vol. COM-23, s. 1062 - 1069, 1974.
• [3] Cherkassky B., Goldberg V., Radzik T., Shortest Path Algorithms: Theory and Experimental Evaluation, http://citeseer.nj.nec.com/cs, Stantford University, 1993.
• [4] Grzech A., Performance of networks and routing related traffic, Proceedings of the 13th International Conference on System Science, Wroclaw 1998.
• [5] Kasprzak A., Rozległe sieci komputerowe z komiltacją pakietów, Wydawnictwo Politechniki Wrocławskiej, Wrocław 1997 (in Polish).
• [6] Kleinrock L., Communications Nets: Stochastic message flow and delay, McGraw-Hill, New York, 1976.
• [7] Kleinrock L., Queueing systems, Volume H: Computer applications, John Wiley & Sons, New York, 1976.
• [8] Kleinrock L., Fratta L., Gerla M., The Flow Deviation Method: An Approach to Store-and-Forward Communication Network Design. Networks, an International Journal, Vol. 3, p. 97-133, 1973.
• [9] Kollek R., Influence of Selected Systems Monitoring and Routing Algorithms on Network Perform¬ance, Information Systems Archit. and Technology, Wroclaw, 2000
• [10] Lorenz H., QoS Routing in Networks with Uncertain Parameters, http://citeseer.nj.nec.com/cs, Haifa, 1998.
• [11] Perrow G., Monitoring Techniques in Distributed Systems Management, http://citeseer.nj.nec.com/cs, Tech. Report 421, University of Western Ontario, 1994.
• [12] Schwartz M., Cheung C., The Gradient Projection Algorithm for MultipleRouting in Message Switched Networks, IEEE Transaction of Communication, Vol. COM-24, p. 449-456, 1976.
• [13] Stallings W., SNMP, SNMPv2, and CMIP, Addison-Wesley, New York, 1994.
• [14] Syslo M., Deo N., Kowalik J., Algorytmy optymalizacji dyskretnej, Warszawa 1993 (in Polish).