Adaptive static routing for traffic balance

Размещено на http://www.allbest.ru/

ADAPTIVE STATIC ROUTING FOR TRAFFIC BALANCE

The non-stable, low-bandwidth and expensive connections to the WAN which are usual for low-populated regions and rural areas demand from Systems Administrators any approaches of using multiple different channels and technologies allowing to use them simultaneously and switch the data flows between them according to their state and effective bandwidth to reach maximum effective use of all their facilities with reduce of the total cost of usage. We offer an approach of routing control which does not demand any special facilities of the ISP or telecommunication channels hardware based on the 2-criteria model of the routing tables estimation and the real-time algorithm for the corresponding optimization problem.

The uninterrupted rapid growth of the telecommunication networks including qualitative increase of data channels bandwidth and development of high-bandwidth access technologies which is mostly typical for the megapolises and densely populated territories is least apparent in remote and sparsely populated regions where the networks are nevertheless vitally important. As a rule, underdeveloped infrastructure of that territories including the undeveloped traditional networks such as telephony embarrasses the advance of such a popular technology as ADSL. So, frequently, in case of long and noisy telephone lines, this technology does not support the declared maximum bandwidth and degenerates into a low-bandwidth access technology (often, transfer rate < 512 kbit/s) apart from the unstable connection which depends on the weather, the humidity and other accidental factors. Sometimes, the usage of radio channels does not support the necessary quality of service, though this technology is expensive and that is why the users with a shoestring budget use the channels which belong to the low-bandwidth technologies such as GPRS. Modem dial-up connection is still very popular the same way as modems for leased lines with synchronous and asynchronous ports with the baud rate 32-512 kbps. Figure 1 shows the typical network configuration of an organization acting as a “last mile” of the Internet. It uses VPN channels over Internet to join its LANs.

Fig.1

routing traffic internet

Often, to acquire the guaranteed access to the Internet, the network administrators use data channels to several Internet service providers or several channels which belong to the same ISP but based on several different access methods. For example, it may be a combination of leased line and radio channel or campus-area network with Ethernet interface and GPRS-channel. The channels in such combinations may significantly differ in a price of traffic. Besides, the functional dependence between the cost of the traffic and its the volume of downloaded and/or uploaded information is often nonlinear (piecewise linear). So, in case of the usage of the leased lines and radio channels, the providers determine the fixed considerable service cost which includes some volume of traffic (some “free of charge” limit) which is accounted during some period, usually each month. The user pays this fixed cost and cost of the traffic consumed in addition to this limit (see fig.2).

Therefore, the aim of the network administrator is on the one hand to reduce the total cost of the consumed traffic and on the other hand to guarantee the fastest and uninterrupted (as far as possible) connection. So, if the ISP sets any “free of charge” limit of traffic of some data channel then it is quite reasonable to use all this limit instead of using other channels which have no such limit or such limit is already overdrawn. In this paper, we offer an approach to this dual problem which is considered a 2-criteria optimization task. Then, we propose its solution.

Fig.2

The considered problem is often a subject of discussions of the network administrators in the Internet forums and some scientific publications [1,2,3]. Some of them offer the ready-to-use software able to solve either of the aspects of the considered problem.

Particularly, organizing the VPN-channels over the physical data channels of more than one ISP with as the static routing model as the dynamic one (or, sometimes, “pseudo-static” one which mean use of the static routing tables able to be corrected by some determined rules) is examined by the researchers and practical specialists in detail [4,5].

However, the approaches of these papers offer either the increase of the total transmit rate or the creation of such a (static) routing table optimizing the load of data channels by the total cost or total capacity where the supposed traffic volume has to be previously estimated per a month (or day etc). When building the network with the usage of the VPN channels, the optimization by the cost of the traffic is not often required because such channels are usually built within the network of the one ISP which sets the price of the internal traffic very low or even zero price (fig.1 shows this case) and, in this case, the aim is only to increase the total capacity or bandwidth of this VPN channel. Often, we cannot calculate the forecast of the traffic volume as an adequate prognosis for any situations because the traffic of the small organizations with the strongly pronounced “burstness” and self-similarity which become apparent even in the long time scales [6]. The volume of the traffic of some classes increases sometimes many times. So, for the e-mail traffic, the reasons of the increase are any business events, season factors or just a “spam”. Similar reasons are typical for the web-server too. Thus, the model based on the average values of the network observation over a long period of time has to be continuously corrected, otherwise the routing system built with this model is able either to use the unjustified expensive data channels for the uncritical classes of the traffic while the cheaper channels are free or not to provide with the appropriate quality of service for the critical important classes and to economize simultaneously.

In our case, the usage of the dynamic routing except organizing VPN channels to our own network segments is problematic [7] because of impossibility to control the routing process in the IPS's network, furthermore, each of our network interfaces used to connect to the ISP has its own wide-area IP-address within the different network of the ISP (or even a local-area IP address if the provider of our campus-area network organizes the access to the Inlernet using the NAT technology) and that is why, without the appropriate multi-homing technology supplied by the ISP, we are not allowed to select dynamically the route through the different interfaces without destroying the TCP sequence. The same problem is also actual for some applications generating the UDP traffic such as openvpn [8].

Te reasons listed in Section 2 cause the choice of the static routing model. At the same time, the routing tables have to be periodical corrected. But we cannot switch the route of the open TCP connection without a risk of its destruction, however, it is the only possibility to continue the data transfer if the interface serving this connection is dropped out for any reasons. Some of the applications which do not generate the long TCP sequences like UDP and TCP requests to the name servers allow us to switch the route of the traffic between interfaces without any serious problems. The traffic of such classes is allowed to be switched rather often according to the demands of the economy or total transmit rate increase. Another ones like ssh-, https- or rdp-connections are on the contrary very critical with this respect and their breaking is unwanted even if they are standing idle for a long time.

Thus, we have to divide our traffic into a several different classes according to not only its priority level but also its ability to the “painless” change of route. Some traffic classes have the only determined interface to use at any time which may be selected according to the reasons of confidentiality etc. We have to be able to change the routing table periodically selecting the route through one or another network interface to the ISP. The facilities built in the operating systems like both of Unix/Linux or WinNT/2003 support a simple solution of this task. So, both these systems have the utility named “route”.

Moreover, the optimal traffic control requires the facilities to estimate the load of the channels. We need the ability of estimating the volume of the traffic that presents in our channels at the present time and calculating its volume spent during the period from the beginning of the month or another period. We are allowed to use the wide variety of the proposed software (such as billing systems) but the built-in facilities of the Linux like “iptables” [9] are able to give us the complete necessary information. In this case, we construct the separate “chain” for each traffic class and store in a database the information of the spent volume of the traffic received by reading and nulling the counters of the iptables chains.

The realization of the algorithm which estimates the traffic volume using iptables and builds some model to control the routing tables does not demand any requirements for the used programming language. We use Perl which is a simple but quite appropriate facility in this case [10]. The usage of C++ gives us more performance but the performance is not critical in our case and Perl does not need any preliminary compilation which may cause some problems related to the usage of the different program libraries etc. We use MySQL as a database which stores the values of the traffic volumes although the usage of simple text files (log-files) seem to be also appropriate.

In this paper, we do not examine the problems of the securing of the priority of service of the different classes of our traffic. We suppose that this problems are already solved by any methods which are offered by the built-in facilities of Linux such as iptables.

Finally, our algorithm uses the stochastic optimization methods for the pseudo-boolean functions which usage is substantiated in Section 4.

One of out aims is to reduce the total cost of the channels. We are allowed to operate only with the prognosis of the total cost of the traffic spent during a month. Let us formulate this aim.

(1)

where m is the number of the traffic classes, n is the quantity of interfaces, Pj is the function of the cost of the traffic routed through the j-th interface per a month, its argument is the prognosis of the volume of the spent traffic, vj0 is the volume of the traffic that has been already spent by the j-th interface, v*i is the average value of the used traffic volume of the i-th class calculated per a day (or another time scale), q is the quantity of days (or another time intervals) that remains till the end of this month (it may be fractional, we must take into account only the working time of the organization), pij =0 if the traffic of the i-th class routed through the j-th interface is free of charge else pij=1, xij is a Boolean variable which determines the routing of the i-th class of the traffic through the j-th interface, X is just a matrix of the variables xij.

The evident constraints of our task are

 (2)

Let us consider the second aim of increasing of the total transfer rate as the task to reach the equal load of the channels. I.e. the idle time of any channel while other channels are 100% busy has to be minimized. So, if the total load of the system is high then the optimal load of each channel is reached when

, (3)

where ai is the average volume of the i-th class traffic per one second calculated in such periods when the load of all channels or even one of them is high (more than some determined percent) [11], cj is the transfer rate of the j-th channel. The equation is adequate for the situation when the load of the system is high only. If the sum of the average traffic rates of each class of the traffic routed through the j-th interface cannot exceed cj. Then, we formulate the second aim as

(4)

Here, the minimized function means the part of the total transfer rate of all channels which stays idle when the total load of the system is high.

So, the expressions (1), (4) and (2) form the 2-criteria optimization task of pseudo-Boolean functions with constraints. The approach offered in [12] lets us to consider such optimization problems as the problems with 1 criterion if we present the universal scale for both the quantitative (monetary) function (1) and the qualitative estimation (4). We have to determine the monetary estimation of the unused transfer rate (4). Let us determine the coefficient k. Its value means the cost (in percents) of increase of the total transfer rate by 1%. So, if are ready to pay 1% more for the average increase of the total efficient transfer rate by 1% (that means that the average idle time of the channels decreases by 1%) then k=1. If we are ready to pay just 0.1% more (i.e. the cost is more important for us than the transfer rate) then k=0.1.

Then, we are allowed to present our optimization problem with the expression

(5)

with the constraints (2).

Thus, our aims are formalized as an 1-criterion optimization task of the pseudo-Boolean nonlinear function with m?n variables. The up-to-time optimization theory and system analysis propose a wide variety of stochastic and determined methods to solve this task. For the tasks with the large quantity of variables which may include our task in case of the enough number of the traffic classes, we are allowed to use some variants of the variable probability method [13,14]. In simple cases (10-20 classes and 2-3 interfaces), it is possible to use the enumeration of all possibilities method. Author uses his own hybrid algorithm which realizes the variable probability method with return which has been designed for optimization problems with constraints like ours (2) [12].

To estimate the efficiency of the proposed methods and algorithm, we used the network shown in fig.1. In our system, Interface 1 leads to the leased line (115 kbps with the asynchronous serial port which is equivalent to 92 kbps synchronous port), Interface 2 is an Ethernet card within a campus-area network with the average transfer rate to the Internet 300-500 kbps, Interface 2 is an ADSL modem (declared download transfer rate is 2 mbps, real rate is less than 1 mbps). The main volume of the download traffic is consumed by Office 1 (about 5 Gbytes per a month), the users in the Office 2 do not consume the traffic from Internet immediately. The traffic of the VPN connection is free of charge. Thus, the users in th Office 1 are connected to the Internet with the Interface 1, Interface 2 immediately through the Router 1 or with the Interface 3 through the VPN channel and Router 2. In this case, the routing system uses the capacity of both Interface 1 and Interface 3 but the cost of the traffic is determined by the price of Interface 3 because the usage of VPN is free.

We divide our traffic into 42 different classes with the different priority and their ability to be “painless” switched between different interfaces.

The results of the total cost of the traffic consumed during a month are shown in Table 1 which shows the real volume of the traffic and its cost which are calculated with working optimization algorithm. Also, we calculated the values of this actual traffic volume for each interface which we obtain if we use the static routing table. These results are also shown in Table 1.

Table 1. Cost of data channels

While the cost is a simple and evident estimation, it is much more difficult to estimate the ability of system to enable the maximum transfer rate because the consideration of the average load of the channels does not give us the information about the behavior of the system when the load is over its maximum value. To illustrate the behavior of the system at the peak load, we have realized an experiment. According to the actual log-file, we have simulated the network activity with sending and receiving of 4 classes of traffic. We have simulated different situations of separate and simultaneous activity of these classes of traffic. First, we have estimated the sent/received volume of data per one second with use of our algorithm, then without it. The results are shown in Table 2. However, the adequate simulation of real situations is a vexed question and it is a matter of my further investigations. But the subjective estimation of users does not fix any decrease of the traffic rate.

Table 2. Average transmit rates estimated during the experiments without use of the optimization method and with one

So, the proposed system is efficient to reach the aim of the reduction of the total cost of usage of the channels, that is illustrated numerically. The achievement of the aim of the optimization of the channels load is not so evident but the results of the repeated experiments and the subjective estimation of the users let us say that there is no deterioration, therefore the general task of 2-criteria optimization is solved.

REFERENCES

1. Johnson Y. Smart Routing Against Congestion. http://www.osp.ru/nets/2002/04/025.htm (in Russian)

2. Hubert B. Linux Advanced Routing and Traffic Control HowTo. http://ds9a.nl/lartc/lartc.pdf

3. Ash G.R., Dynamic Routing in Telecommunications Networks, AT&T, 1997.

4. Severov M. IP-traffic Optimization, http://zeus.sai.msu.ru:7000/nets/hard/accelerator (in Russian)

5. Rudin H., Mueller H., Dynamic Routing and Flow Control, IEEE Trans.on Comm., vol. Com-28, No.7, July 1980.Chu Y., Rao S.G., Zhang H. A Case For End System Multicast, in Proc. ACM SIGMETRICS, June 2000

6. Petrov V.V., Self-Similar Netork Traffic; From Chaos and Fractals to The Prognose and Quality of Service, Conference NEW2AN, Abstracts, S.-Petersbourg, 2004, pages 110-118.

7. Chan M.C., Lacar A.A., Stadler R., Customer Management and Control of Broadband VPN Services, Proc. of the 5th IFIP/IEEE International Symposium on Integrated Network Management V: Integrated Management in Virtual World, Chapman Hall, London, 1997, pages 301-314.

8. Khanvilkar S., Khokhar A., Virtual Private Networks: An Overview with Performance Evaluation. Communications Magazine, IEEE, vol.42, issue 10, pages 146-154.

9. Diehl M., Generating Firewall Rules with Perl, Linux Journal, vol. 2006, Issue 143 (March 2006), page 4.

10. Wall L. Christiansen T., Schwartz and Potters S. Programming Perl. O'Reilly&Associates, Oct. 1996.

11. Lai K. And Baker M., Nettimer: A Tool for Measuring Bottleneck Link Bandwidth, in Proc. of the 3rd USENIX Symposiom on Internet Technologies and Systems, March 2001.

12. Kazakovtsev L.A. Adaptation of the Method of Variant Probability for the Problems of Assortment Planning and Others. Vestnik NII SUVPT, issue 6, NII SUVPT, Krasnoyarsk, 2001, pages 42-50. (in Russian)

13. Antamoshkin A. Optimization of Functionals with Boolean Variables. - Tomsk University Press, Tomsk, 1987 (in Russian).

14. Antamoshkin A., Schwefel H.P., Toern A., Yin G., Zhilinskas A., System Analysis, Design and Optimization. An Introduction. - Ofset, Krasnoyarsk, 1993.

Размещено на Allbest.ru