Improved model of adaptive routing
in telecommunication systems.
Savisko M.S.
Cherkassy State Technological University
The rapid
growth of computer networks and fast routing of data are
accompanied by a change in network technology, which aimed at
improving performance and reliability of the network, possibilities
of voice, data and other information.
An
analysis of the algorithms of adaptive routing in
telecommunication networks shows that the construction of
routing tables used by the two algorithms – the Bellman-Ford, with
complexity O(N3) and Dykstra, with O(N2), where N
is a number of routers in the network. Also, the
algorithm pairs of transitions, which reduces complexity to
a value of O (K * N), where K - number of pairs
of transitions.
Graph after the pair of transitions.
For improving efficiency of telecommunications
networks can be used algorithm of pairs for
transitions to a value O (N).
The scheme of the algorithm is as follows.
Point 1. To the top, a leaf of the
tree, search is all paired hits. The list is
bound to consider the edges incident to the
top and below in the hierarchy.
Point 2. Procedure is executed to generate a
list of transitions. This is necessary in case of increase or
decrease the weight of the ribs.
Point 3. For each node create a list
of possible routes passing through the edges, consisting of
a pair of transition occurring in the shortest path tree.
Point 4. With the help of a routing
protocol to determine the change of the metric for an
edge. If yes, proceed to point 5, if not - to point 7.
Point 5. With a list of pairs of transitions need
to define a pair of transition. If yes, proceed to point 6 - if not, go to
point 8.
Point 6. For each node to determine the
path of minimum length.
Item 7. Send packages at affordable equivalent
routes.
Item 8. Reshape a list of routes for each
substitution changed the top.
Item 9. Go to item 4.
The main advantage is that
the new shortest path will pass through the edges
of the pair consisting of a transition to the
ribs included in the original graph. Thus, by
decreasing the weight edge not included in
the shortest-path tree for the vertices,
routing degree greater than two.
Algorithm pair of permutations improves efficiency
of the telecommunications network by the using additional network
information.
Used literature:
1. Waldvogel M. et al. “Scalable High Speed IP Routing Lookup”. Proceedings
of ACM SIGCOMM ‘2008 (Cannes, France, Sept. 2008).
http://www.acm.org/sigs/-sigcornom.html
2. Williamson C. Generating Synthetic Traffic Streams for Network. http://www.cs.ca/faculty/carev.html
3. Thomson K., Miller G., Wilder R. “Wide Area Traffic Patterns and
Characteristics”. IEEE Network magazine. Vol. 10. No. 7. pp 11-24.