Study On Routing Algorithms With Multiple QoS Constrains Based On Small Word & Random Graph Theory

Routing is the key theory and technical problem in Network communications, especiallyInternet is rapidly developed and the number of nodes is increasing at exponent level, towardthe giant capacity, high speed and multimedia, traditional routing algorithms can't meet therequirements of multi-QoS constrains, thus, new routing algorithms are needed to be studied.Routing algorithms with multi-QoS constrains are studied. Small world network model isset up based on its theory. The new concepts of the static and dynamic network models areproposed. The upper bound and low bound of message transportation expectation steps from asource s to a target t in the distributed routing algorithm. Through research on random graph,a k-ary network model is founded and the function of unicast and multicast average hops isdeduced. It comes to conclusion that the distributed routing algorithm is efficient to giant andcomplex networks. The models and methods of random graph simulation are described.Distributed multi-QoS constrained routing algorithm (DQRGA) based on GA are designedand implemented, and its space and time complexity is analyzed. The results show it isadvantage over traditional routing algorithms in time and space complexity with N/[log₂ N]and (log₂ N)² respectively, in which N is a node number of network. A new distributedrouting algorithm (DRBSR) based on small world and random graph theories is designed andimplemented. Its time and space complexity is analyzed and the result shows that it is superiorto the centralized algorithms. According to the different transactions, considering Multi-QoSconstrains and network resource utilization rate, Fallback⁺⁺ is designed and realized. Its timeand space complexity is analyzed and the result shows that it is superior to Fallback⁺.The multicast routing with multi-QoS constrains is one of the most difficult problems inrouting algorithms because not only it is NP-complete but also the QoS parameters arenondeterministic even fuzzy. Most traditional multicast routing algorithms belong to accuratealgorithms that can't represent real network status. Multicast routing algorithms (IQMRFI)with multi-QoS constrains based on fuzzy information is put forward which is first to applythe fuzzy set theory to routing algorithm. Membership functions and ideal points of QoSparameters are defined and the model of computing the distance of QoS parameters to idealpoints is established. IQMRFI is designed and implemented by simplifying multiobjectsplanning into the single object planning. Its time and space complexity is analyzedas O(mn²) and O(5|E|) respectively, the simulation result shows that the algorithm is superiorto them in selection success rate and run time.