Faculty: Computers and Information Science
Speciality: Computer systems and networks
Plenty of algorithms of routing is used in computer networks. Exactly the network layer of model of OSI is engaged in development of routes of delivery of packages from a sender to the recipient. To get to the point of setting, it can a package be required to overcome a few transit areas between routers. A network layer is the lowest level which deals with communication of data on all way from one end to other.
Usually in difficult catenets practically there always are a few alternative routes on which communication of data is possible between two knots. In addition, large catenets can plug in itself the networks of different scales – from local to the up-diffused global networks.
Route of transfer of a package from one knot of a compound network on another is the passage order this package of the transit networks connecting networks in which are located a source and the addressee of the given package.
Catenets in which routing of package is required network-level must be incorporated between itself by means of routers. Therefore on a network it is possible the route of sending of package to name the sequence of routers through which this package will be redirected in the process of the following to the addressee.
Routeing of packages includes two primary goals: definition of an optimum route of transfer of a package on a compound network; actually package transfer on a network [1].
For realisation of a problem of data transmission network level should possess the information on topology подсети communications (that is about set of all routers) and to choose the necessary way on this подсети. It is important enough to watch that loading on routers and communication lines was, whenever possible, more uniform.
The algorithm of routing will be realized that part of network layer software, which is responsible for the choice of output line for the dispatch of coming package. At the modern level of development of network technologies the special requirements are produced to that the algorithm of choice of route possessed certain properties – correctness, simplicity, reliability, stability, justice and optimality. During work of large network constantly there are some refuses of apparatus and changes a topology [2].
Master's degree work is executed in a flow 2008-2009 in accordance with scientific direction of department the «Electronic calculable machines» of the Donetsk national technical university.
Purpose of work. Research and analysis of work of algorithm of routing is in a network topology.
Idea of work. Consideration of partial use of a method of application of the centralised routeing in a computer network at which a certain main router is the centre, and all next, directly attached to it – minor knots. In that case for the analysis of work of a network it is convenient to arrange routers as consecutive alternation.
Basic tasks of development and research. For achievement of the put purpose it is necessary in the process of research:
Article of development and research. Computer network.
Object of working out and research. Devices of network level – routers (routers).
Methodology and research methods. In the process of research the formal vehicle of theory of the graphs and algorithms of routing is used.
Novelty got results consists the use as a model of research of the concrete developed topology of network and mechanism of work of algorithm of routing for the grant of services of exchange by information between knots.
Consists in application of a choice of algorithm of work of a router in concrete topology.
The basic results were reported and proved at the fourth international scientific and technical conference of students, post-graduate students and young scientists on «to Computer science and computer technologies».
By working out of algorithms of routeing often pursue one or several of listed more low the purposes: an optimality, simplicity and low unproductive expenses, survivability and stability, fast convergence, flexibility, an optimality [3].
Alternative routing. The task of choice of optimum routes behaves to the class of multifood tasks with a protuberant objective function and protuberant in a number of limitations. Consequently, there is unique local a minimum of this task, being a global minimum, for finding of which the large enough number of calculable methods is developed [4].
It is necessary to remember that absolutely reliable reports of routeing do not exist. At excessive loading any report can refuse. Any standard standards of adjustment of reports of a condition of the channel are not present [5].
IP-routeing — simple process which is identical in networks of any size. For example, on fig. 1 process of step-by-step interaction of a host And with a host In in other network is shown. [6]
Figure. 1. An example of IP-routeing for two hosts and one router.
Adaptive routing. It is a basic type of algorithms of routing, used routers in modern networks with a difficult topology. The adaptive routing is based on that routers are periodically exchanged the special topological information about present in the internet networks, and also about connections between routers. Not only the topology of connections but also their carrying capacity and state is usually taken into account [7].
The router device: - entrance ports; - the switching block; - target ports; - the routeing processor [8].
Leading leaders in working out of routers-technologies [9]: Cisco; Juniper; Huawei; Fujitsu; Foundry; NEC.
Modelling represents a powerful method of scientific knowledge at which use the investigated object is replaced with more simple object named model. It is possible to consider as the basic versions of process of modelling two its kinds - mathematical and physical modelling. At physical (natural) modelling the investigated system is replaced with other material system corresponding to it which reproduces properties of studied system with preservation of their physical nature.
Possibilities of physical modelling are limited enough. It allows to solve separate problems at the task of a small amount of combinations of investigated parametres of system. Really, at natural modelling of the computer network it is almost impossible to check up its work for variants with use of various types of communication devices - routers, switchboards, etc. Check in practice about ten different types router is connected not only with the big efforts and time expenses, but also with considerable material inputs [10].
The method of research of algorithm of routeing is considered. Differentiation of algorithms of routing is produced, based on a few key descriptions. At first, concrete tasks influence to work of resulting protocol of routing. Secondly, influence of different types of algorithms of routing on a network and resources. And finally, the algorithms of routing are used by various indexes which influence on the calculation of optimum routes.
Generally it is possible to present a principle of work of a router the following sequence of actions (fig. 2):
Figure 2 - Algorithm of a router work (animation: 6 shots, 6 cycles, 31 Kb).
At some initial moment of an operating time of a network it is accepted that minor routers (on fig. 3 are designated by numbers, since №14) have the information only about directly connected to them to routers. The central routers with numbers from 1 to 13 contain in the tables the information not only on direct next routers, but also the routers located through one (that is on distance with the metrics of passage of a way equal to two). Further at functioning of a network and by search of new demanded ways the main things, more difficult in realisations, routers work on algorithms of routeing only. They can specify the information on the found ways to minor routers for possibility of work of a network and correct sending of packages. Routers with simple realisation by search of routeing ways are not engaged, and - only sending of packages by data about network topology in own tables of routeing.
Figure. 3 – Topology of an experimental network.
The algorithm starts to be engaged in search of routes only when they really are required. Let it is necessary to find a way between routers №1 and №8. The knot №1 generates special inquiry of route Route Request and extends it on a network in the broadcasting way. In the big networks the algorithm generates many broadcasting packages, therefore for avoidance of excessive loading and for detection of the addressee the sender dispatches a package of inquiry of a route with the step equal 1. That is the inquiry is formed for routers №14 and №16 (in an example). If the answer does not come also a way still неопределен one more inquiry is sent, but with the step equal 2, etc. Thus, the search which has begun in any local area, expands the coverage more and more.
When after the concrete number of steps of query of route, there is necessary information, an answer is formed about the presence of way of Route Reply. The last leaves in a reverse way in to the source of query. Thus knots, standings on the indicated way, quite «for nothing» get information about a route to routeru №8.
Problems of an overload of lines of data transmission are considered. The material variable can be connected with each line u which value in limits from 0.0 to 1.0 reflected there would be line use lately. Such average estimation of congestion of a line can be received by means of simple calculations, periodically measuring instant congestion of a line f (0 or 1) and counting new value of a variable u under the formula:
uнов=auст+(1-a)f,
where the constant and defines, is how much frequent in time a router analyzes congestion of a line.
When a variable of u value begins to exceed a certain threshold level, it means that a line passes to the dangerous state. Every coming package passes verification: if coming him to follow on a line, to being in the near to the overload state, it is necessary to choose an alternative way.
When the number of the packages sent by hosts in a network, does not exceed its throughput, all of them are delivered to addressees. Thus quantity of the delivered packages to proportionally quantity of the sent. However in process of growth of the traffic routers cease to have time to process all packages and start them to lose. When packages reaches a maximum level, productivity of a network falls to low level.
In master's work for achievement of an object in view in the course of research following problems are carried out:
At a writing of the given author's abstract магистерская work is not finished yet. Definitive end: December, 2009 the Full text of work and materials on a theme can be received at the author or its head after the named date.