Fundamentals of optimization of information transmission systems, selection and principles of signal formation.
For radio channels with limited frequency and energy resources, the most important task is to use these resources efficiently. This means to ensure the maximum rate of information transfer from the message source for given resource parameters and message transmission reliability.
In the modern theory of information transmission systems, it is customary to optimize the communication system as a whole first. Then the remaining elements of the system, in particular the receiver, are optimized, provided that the type of signals has already been selected.
System optimization searches for the best signal type for a given radio channel and the corresponding optimum reception method.
“The founder of the optimization of communication systems in general is K. Shannon, who proved the theorem:
“If a communication channel with a finite frequency response and additive white Gaussian noise (AWGN) has a capacity of “C”, and the source performance is equal to H′(A), then with H′(A) ≤ C, such coding is possible that ensures the transmission of messages over this channel with arbitrarily small errors and at a rate arbitrarily close to the value of "C" ":
[bps], (3.1)
Where ∆f k– bandwidth of the rectangular frequency response of the communication channel;
R s- average signal power;
R w \u003d N 0· ∆f k; (3.2)
N0· - one-sided spectral density of AWGN.
For a discrete channel and random source coding, this theorem can be written in another form
where is the average decoding error probability over a set of codes;
T- duration of the code block of the enlarged message source.
Since, [С−Н ′ (А) ≥ 0] according to the condition of the theorem, then with an increase T(by enlargement of the source) and at H ′ (A) → C the value T→∞ and the decoding delay of the lumped source code increases.
From (3.3) we can make conclusions:
- the longer the encoded message segment (T) and the less efficiently
the channel capacity is used (the greater the difference [C-H ′ (A)]), the higher the reliability of communication (1-);
- there is a possibility of an exchange between the efficiency of use, the values of C, and T (decoding delay).
a) Let us analyze the capacity (3.1).
"C" can be increased by increasing ∆f k And R s. It must be taken into account that the power R w(3.2) also depends on ∆f k.
Based on the known relation (for α=2, β = e) can be written
Find the limit value depending on the band ∆f k and plot the throughput graph.
At ∆f k→∞ . Then we expand the function log(1+x) into the Maclaurin series (i.e. at the point X=0) , which x→0 equals log(1+x)≈x. As a result, we get
Let us plot the function (3.4) depending on ∆f k with normalization on both axes N 0 /P c.
Fig.3.1. Graph of the normalized channel capacity.
At R s / R w=1 in (3.1) → WITH= ∆f k. Taking into account the normalization along the axes of the graph, this equality corresponds to the point (С· N 0 /P c =Pw /Pc=1) with coordinates (1,1).
The throughput increases markedly with an increase in ∆f k until P c / R w ≥1 and tends to the limit of 1.44 P c / N 0 , i.e. the maximum value of parameter С takes place at h →0.
b) Find the Shannon boundary values for the specific bandwidth and energy costs at the information transfer rateR max \u003d C .
The specific bandwidth costs in a communication channel are, by definition, equal to
where R is the information transfer rate (bit/s) in the channel. Attempts to reduce these unit costs are associated with additional energy costs, characterized by the value of specific energy costs
Where E b- the energy spent on the transmission of 1 bit of information;
T 0- time of transmission of 1 bit over the communication channel (duration of the channel symbol T ks);
Let us find the dependence of the specific energy consumption on the specific consumption of the strip. To do this, we express the quantities in (3.1) by setting WITH=Rmax :
Substituting these values into (3.1) and dividing it by WITH we get
Based on the definition of the logarithm log 2 N=a meaning N=2a can be written from where, taking the root from both parts, we get
As a result expression
determines the relationship between the specific energy and bandwidth costs in a channel with AWGN and a finite frequency response. However, since
then from (3.5) we obtain the dependence for the signal-to-noise ratio (SNR):
Thus, in a communication channel with a finite frequency response and AWGN, an infinite number of different optimal systems can be implemented. Spectrally efficient systems (baseband spectrum) require a correspondingly increased SNR. Energy efficient systems require low SNR but must be wideband.
Real systems have values that lie on the graph in Fig. 3.2 above the Shannon bounds. By comparing real systems with potential ones, it is possible to estimate the margin for improving the parameters of the communication system.
Alexey Ukolov talks about what tricks mobile operators use and how small businesses can save on phone calls
Cellular operators are constantly introducing new tariffs to the market. And it can be quite difficult to understand them. Using the Tarifer service, subscribers can compare their current tariff with other offers on the market and choose the best option for themselves. If for individuals the benefit from switching to another tariff can be several hundred rubles a month, then the savings for large companies can amount to hundreds of thousands of rubles. What tricks are there mobile operators and how to track communication costs in real time, Alexey Ukolov, the founder of the Tarifer service, told the site portal.
35 years old, entrepreneur from Samara, founder and CEO of the service "Tarifer"(selection of optimal tariff plans cellular). Education: International Market Institute (Faculty of Economics and Management). The Tarifer service was launched in 2007. In 2008, the service received the Best Soft award, in 2009 - the Microsoft Business Start award.
Looking for the best deal
The idea of the Tarifer service came from Alexey Ukolov's brother, Dmitry, in 2007. At that time, he worked as a programmer in one of the Samara companies. By this time, Aleksey himself had experience in various projects in the field of trade - far from always successful. After discussing the idea, the brothers decided to make a trial version of the service that would analyze call details and select the most suitable tariff for a particular person.
“The idea lay on the surface. Many people had problems choosing a fare. At that moment the market was quite wild. Then there was a real leapfrog with tariffs. There were both per-minute rates and per-second rates. Some tariffs included some packages. There was also a connection fee. In general, there were many nuances that had to be taken into account and which were difficult for many people to figure out,” says Alexey Ukolov.
In the new project, Dmitry took care of programming, and Alexey took care of all other issues. In 2008, another partner, Kirill Nasedkin, joined the project. He had his own web design studio and took over the development of the site.
Creating a test version of the service took several months. And we spent several months building the site. In 2008, a year and a half after the start of work on the project, the first version of Tarifer.ru was launched. And at the end of the same year, the site was redesigned, and came to a version similar to the current one.
In Russia, the company has competitors, but they are few. They manually or semi-manually help customers analyze their costs and choose a new tariff plan. “Our advantage over them is in manufacturability, in this respect we are much stronger,” says Alexey Ukolov.
We live on our own
The founding fathers launched and are developing their project exclusively at their own expense - they have never attracted borrowed money. About a million rubles were spent on the development of a prototype site. The service brought its first revenue in 2009, and in 2010 Tarifer reached a payback.
The growth of the project was facilitated by the victory in the competition for Russian startups Microsoft Business Start in 2009. For the victory, "Tarifer" received a grant of 1 million rubles. He allowed, among other things, to hire the first employees. A programmer and a technical support specialist came to the company to work with the base of tariff plans.
The appearance of new employees in the team accelerated the development of the service. At that time, the founders of the company decided to focus on the corporate market, as more promising for their type of activity. Towards the end of 2009, Tariffer got its first corporate clients.
It was not difficult to find them, since the company set a rather low price for its corporate product - several thousand rubles, regardless of the size of the client company and the number of "calculated" SIM cards. But it soon became clear to the founders of the project that with such a pricing policy it was simply unprofitable to work with large companies, and the price list was revised. Naturally, sales became more difficult, and in 2011 the company hired a sales manager. Previously, these functions were performed by Alexei Ukolov himself, and, as he himself admits, he did not always have enough time for this. With the arrival of a new manager, sales have grown significantly.
"Tariff" for individuals
Private customers can independently choose the most favorable mobile communication tariff for themselves. The client must enter his phone number and password from the personal account of the mobile operator. If a person does not know this password, the program will help him "enter the office" - you just need to follow the instructions. The service "unloads" call details for the month and analyzes it. Based on the analysis, the client is recommended the most favorable tariffs - both "own" and "foreign" operators.
The base of tariff plans is supplemented and updated daily. It includes both federal and all regional tariffs of the Big Four operators: Beeline, MTS, Megafon and Tele2.
“New tariffs from operators appear all the time. And we regularly make improvements to the calculation algorithm, we change something all the time. Now the main trend is connected with the transition to package tariffs. In addition to the actual telephone connection, they include the use of the Internet under certain conditions. And we "sharpened" all our tools to work effectively with package tariffs", - says Alexey.
Corporate program
Corporate clients of "Tarifer" can choose one of two programs for using the service. The first is cost analysis. The program determines in which areas communication costs are higher than the average for the company. A company's telephone costs are broken down by employee, department, and cost source.
The second program is directly cost optimization, that is, the selection of the most favorable rates. The program analyzes all client numbers and selects the most advantageous offer for each number.
When working with companies "Tarifer" uses two schemes. The company can purchase from "Tarifer" the necessary software and then do it all on your own. An employee of the company working with this program will have to upload call details into it, build reports and select tariff plans. For example, this option is used if corporate security rules do not allow data to be transferred to the side.
But the most convenient variant of cooperation for corporate clients is to delegate all functions for the analysis of communication costs and the selection of tariffs to the Tarifer service. In this case, the client simply sends all bills for communication, and then the company's specialists work with them.
The program can also work with individual tariff plans, which many corporate clients have. These tariffs are “non-public”, that is, they are not presented on the websites of operators. The client provides a description of his tariff plan, and the terms of this tariff are added to the program of this particular client. The customer can see this option in his program and use it in the calculations.
One of the main difficulties when working with corporations is the need to download call details from the personal account of your telecom operator. Tarifer specialists are now working to collect all data from operators' personal accounts automatically. Then the client will only need to provide his login and password from his personal account on the operator's website.
Online monitoring
Until recently, tariff selection schemes were aimed at analyzing the communication costs that have already taken place over the past month. But in the near future "Tarifer" launches another technology for corporate clients - monitoring. It allows the client to track and adjust costs in real time.
The new technology allows you to see how much employees have spent on mobile communications and the Internet in the current month by this minute, and how much they spend in this moment. If the program "notices" that communication costs have increased dramatically, it sends an SMS notification to the client.
The service is needed primarily in order to prevent unplanned communication costs, especially in roaming. For example, a person forgot to turn off the Internet. In roaming, the subscriber may even practically not use the Internet or communication. But thanks to the rounding rules and certain tricks of the operator, he will receive an unexpectedly large bill at the end of the month. And since the company has a common balance for all numbers, this may show up late. And the communication bill will be an unpleasant surprise for the company.
It is not always possible to shift these costs to the employee for legal reasons. Therefore, companies often “get” hundreds of thousands of rubles due to the fact that someone forgot to turn off the Internet while roaming or used some services incorrectly.
“The director of the company, which is currently being serviced by us under the monitoring program, has gone abroad. And there he used the Internet, after which a bill for 160,000 rubles came to this number. The company is not very large, and this amount is significant for them. Unfortunately, at that time the monitoring program was not connected to this client. And they did not understand where such a sum for communication came from. Now they can see in real time the reason for the increased costs and prevent them in time,” Alexey gives an example.
Data on sharply increased spending enters the Tarifera system 15 minutes after the client began to overspending. It takes about 10 more minutes to react to the situation and inform the client about it. The message about the costs can be sent both to the "squanderer" and his company. Thus, the client can see and stop unplanned communication costs within half an hour after they start.
The service started working in test mode two months ago. Now about 50 companies are served under this program at Tariffer, and the first reviews about the service are the most positive.
Clients
As corporate clients "Tarifer" considers companies from 30 people. If the company has no more than 15-20 numbers, then all calculations can be done manually in a few hours. With a quantity of 30 numbers or more, the amount of data is already quite serious. And the company already needs to make a decision: either it allocates a specialist to work with them, or attracts an outside contractor.
In total, Tarifer has about 400 corporate users. Each company has from 50 to 5000 people. Of the top 10 largest Russian companies, four use the services of Tarifer.
The number of private clients who have used the services of the service since its inception is about two hundred thousand people. Now the service website receives about 200-300 orders per day from individuals.
If we are talking about an average company of 100 people spending 500 rubles a month on one phone number, then its savings after the calculations of the "Tarifer" can be about 10-15 thousand rubles a month.
But the amount of savings largely depends on the structure and type of activity of the company. If this is a trading company whose representatives spend a lot of time in the regions and use roaming, then its communication costs are many times higher. And then she has savings from working with Tarifer solutions several times more than other companies.
Tarifer employees periodically call their customers to find out their opinions about the service. “I myself take a random list of clients from time to time, call and ask them what can be improved and corrected in the service. In particular, thanks to such communication, we have a “real-time monitoring” service, - says Alexey Ukolov.
Service prices
For individuals, the service has long been free. But now a fee has been introduced for the service - and anyone can calculate the optimal tariff for 140 rubles. The site has a tariff plan calculator into which you can drive in all the parameters of your communication use. The average savings for private clients after using the service and switching to a new tariff is 37%.
Payment occurs after all calculations and preparation of the report. However, if during the calculation it turns out that the current tariff of the client is the most profitable, Tarifer does not charge him and all the analytics is provided to the client as a bonus.
Users who themselves are well versed in a variety of tariff plans can choose a tariff for themselves for free. The site is posted in open access a complete database of all current offers of the "big four" operators (including regional tariffs).
The cost of servicing companies depends on the number of their employees and the required functionality. The price varies from 10 to 20 rubles per month for each SIM card of the company, depending on the services included in the service (just cost analysis or analysis + selection of new tariff plans).
"Underwater rocks"
Any business built on working with the corporate sector faces the problem of approvals within client companies. In large structures, the decision-making system is usually multi-stage. It happens that negotiations with some large companies drag on for up to several years.
In addition, not all companies are in dire need of "tariff" savings. For many companies, communication costs are a small item of expenditure compared to the overall budget. And many executives simply do not want to spend time seriously studying the issue of corporate rates.
But even in those companies where the issue of reducing communication costs is acute, not everyone is happy with the proposals of Tarifer. The employee responsible for corporate mobile communications is not always interested in saving the company money. Therefore, the task of Tarifer's managers is, if possible, to contact the first persons of companies interested in saving.
Some existing Tarifer customers almost never use the tariff selection function. It is important for them that the data on corporate communications are streamlined. And the service helps them store information about all calls made from corporate numbers. There are many branches of Western corporations among such clients.
Operator tricks
"Tarifer" strives to make its customers pay less for communication. The task of cellular operators is just the opposite - to increase fees from customers. To do this, the "big four" has many tricks and tricks, one of the main ones is "archival tariff plans".
The meaning of the trick is quite simple. The client chooses a tariff plan, connects and uses it. After some time, the cellular company sends this plan to the “archive”. Moreover, the operator may still have the current tariff with exactly the same name. For example, three years ago the client connected to the July tariff. Now the operator has a tariff with exactly the same name, but with different conditions. And the tariff, which the client has been using for 3 years, has long become archival, and now it is called "July-2013".
The benefit for the operator is that the "archive" tariff is usually made more expensive than the current tariff plan. In any subscription service agreement it is written that the operator has the right to change the terms of the tariff without informing the client about it. The subscriber can see among the offers of the operator company a tariff with the same name as his own. But in fact, this is no longer his tariff, and he is served on an archived version, which is most likely less profitable.
“We just recently dealt with such a case. The client said that we recommended him his own tariff, and at the same time promised savings. We began to understand, and it turned out that he was "sitting" on the archived version of the same tariff, which includes a much smaller package of services. Some services are missing there - and the client overpays decent money, because the tariff is actually not the same. So if a subscriber has been served at the same tariff for several years now, it makes sense for him to check if there is a more profitable option now,” recommends Aleksey.
When a new operator enters the market, it often attracts users with low prices. At the same time, other operators are forced to adapt, reduce prices, and thus the situation on the cellular market is changing. But, having gained a foothold in the market, beginners usually begin to gradually raise prices, and the general market situation returns to its original state.
Now the strategy for operators to enter new markets can be seen in the example of Tele2. Approximately at the moment when this operator began to conquer Moscow with low tariffs, prices in the regions began to rise.
“Another feature of Tele2 is that they actually have low “frontal” tariffs, that is, figures that the client pays attention to. But for all sorts of “additional services” (intercity, roaming, etc.), their prices are far from the most profitable, ”Aleksey reveals secrets.
Promotion
Since Tariffer has two different audiences - private and corporate, there are also two sites. Services for individuals are posted on it - a tariff calculator and an all-Russian tariff base. A is the main site of the project, which contains both corporate solutions and links to tarifer.net.
Over time, tarifer.ru will become a site for corporate users only, and tarifer.net for private users. Now the site tarifer.ru is under redesign. His new version scheduled to launch at the end of August.
The founders of Tarifer chose direct sales as the main way to promote their services. Managers contact potential clients through cold calling. The company has a "two-level" sales department. Managers of the "first level" work on the principle of a call center. Their task is to call and communicate with the client. If the client shows interest, then he is transferred to a more professional sales manager.
Team
In total, the company "Tarifer" employs about 30 people. The "head" office and developers are located in Samara, and the company has a sales office in Moscow. 10 people make up the sales department, the rest are developers, administrative staff and technical support staff.
Technical support takes calls and requests from customers. In addition, she has a large scope of work related to updating data. This is support and replenishment of the base of tariff plans, support of the base of telephone numbers and recognition of all formats of billing details that are only possible with operators.
Despite the impressive experience, the project has not yet acquired its own mobile application. It is planned to be made in two versions: for individuals and for corporate clients.
The most relevant plan for the coming months is the further development of the monitoring service (tracking and adjusting expenses in real time). While it can be used in a test version, its “commercial” launch will start in the fall.
“We are planning a serious development of this service so that it also tracks the balance of current service packages. Gradually, we will reduce all our services to one interface, everything will be built on the basis of monitoring,” sums up Alexey Ukolov.
1.3 OPTIMIZATION UNITS
As already noted in Chap. 2, the algorithmic complexity of the task of synthesizing communication networks is such that the exact methods for solving it using the apparatus of mathematical programming are practically inapplicable. The main difficulties in designing distributed communication networks are caused by the following reasons:
significant dimensionality of designed networks (for example, the problem of optimizing a telephone communication network according to the cost criterion can be reduced to a discrete problem of nonlinear programming, however, the dimensions of real designed networks are such that direct use of methods for solving nonlinear problems in the general case becomes impossible);
the complexity of a complete mathematical description of the network, which necessitates a number of significant limitations of the synthesis problem.
The main limitations of the synthesis problem include: the assumption of the stationarity of the technical base of the network and its parameters, the assumption of the stationarity of control procedures and the statistical equilibrium of network processes, the assumption of the Poisson nature of the flow of applications, the exponential nature of the distribution of the lengths of discrete messages and the time the channel is occupied by a telephone message, the assumption of the absence of the possibility of interrupting the transmission and the time spent searching for a way to transmit the message. For telephone networks circuit-switched networks assume the Poisson nature of the missed and excess load, the absence of internal blocking in switching nodes and the absence of repeated requests for service, for networks with message and packet switching - the absence of interdependencies in the delay times of a given message (packet) in different queues, the absence of dependence on the delay time of a message (packet) at the node and the time of subsequent transmission over the channel; it is assumed that the message (packet) does not have a fixed length and in each transit node a new length is assigned to it, etc. Naturally, the acceptance of restrictions determines the approximation of the calculation being carried out;
the need for an integer solution caused by the discreteness of a number of technical means;
non-linearity of the cost functions of the network elements, which necessitates their approximations, solving the problem at the level of approximating functions and choosing a solution to the problem by discretizing continuous functions,
In connection with the above, the currently methodologically justified rule for solving the problem of synthesis of communication networks is a combination of a set of heuristic procedures for optimizing the solution of particular synthesis problems with the involvement of elements of statistical modeling. Note that, despite the approximate nature of the heuristic algorithms for building communication networks, the use of heuristic optimization procedures can reduce the cost of the designed communication network by about 30%.
Since the solution of the general problem of synthesizing a communication network should consist of a set of procedures for solving particular problems, it seems appropriate to study the set of particular design problems in order to determine the possibility of their autonomous consideration and determine the best sequence of their application.
Consider the problem of synthesis of a switched communication network. We assume that the following information is known:
structure G(V, U) primary network, where V- a set of switching nodes of the network; U- many communication lines of the network;
matrix Y=|| || workloads, characteristics of application flows, priority structure;
matrix S=|| || rent for the use of a unit of bandwidth (channel) between nodes i, , and Sij is a step function of the distance, independent of i, j;
probabilities (q(i),q(u)) node and communication line failures. ;
probabilities (P()) accidental or intentional simultaneous damage to n1, nodes and m1 communication lines.
We will assume that the requirements that the synthesized network must satisfy are known;
matrices 
allowable losses (delays);
matrices of allowable losses (delays) in case of simultaneous failure of n1 nodes and m1 communication lines;
limitation l on the maximum number of transits (receptions) in the transmission of information between each pair of network nodes;
restrictions ω(λ) on the number of vertex (edge) independent paths between each pair of nodes of the synthesized network (restrictions l,ω,λ, can arise, of course, and in an effort to provide the required quality of service).
When synthesizing a communication network, it is necessary to determine: network structure (network graph), channel capacities of network communication lines, switching and cross-connection requirements for network nodes, required storage capacities at network nodes (for networks with packet switching and message switching);
a communication network management graph with the definition of particular control and management algorithms (and their interdependence) with the network structure (resources) and load, distribution and transmission of information over the network, including algorithms for choosing a path and discipline for servicing applications.
As a criterion for the optimality of the synthesis of a communication network, we will take the rent for the total channel capacity of the communication lines of the network in the absence of restrictions on the capacity of the lines.
We will consider the synthesis problem under the following assumptions: assuming the stationarity of the flow of service requirements; assuming no load priorities; assuming a permanent (not scheduled and not on demand) lease of primary network channels; assuming that the channel capacities of communication lines, switching and crossover capabilities of the primary network nodes are sufficient to serve the load with the required quality of service.
Analysis of the problem of synthesis of distributed communication networks allows us to identify the following main particular design tasks:
GS - generation of initial network structures for the subsequent stage of local optimization. The initial data of the HS are the number P nodes of the synthesized network and the requirements for the hierarchy of the network, the result is a certain network graph on P vertices that satisfies the requirements for hierarchy. As a rule, without taking into account the requirements for hierarchy, the minimum structure is taken as the initial structure (in terms of distances, cost, taking into account the load Y) linking tree, star graph, complete graph, empty graph, graph whose edges correspond to non-zero values of the matrix Y, etc.;
AW - network analysis for connectivity by parameter ω or λ (choice ω or λ determined by the conditions of the synthesis problem). In the general case, an analysis is needed for any required reliability indicator;
ad- network analysis for metric property (maximum number of hops);
CW- network synthesis by parameter ω or λ . The analysis and synthesis of graphs with a degree of connectivity greater than three is of no practical interest, which is explained by the capabilities of control systems to choose the ways of transmitting information;
CD- network synthesis by parameter d;
RP- flow distribution over the communication network. To reduce the implementation time of the RP stage, it is advisable to use heuristic distribution procedures. It should also be taken into account that the network throughput depends mainly on the total amount of flow in the network and, to a lesser extent, depends on the nature of the distribution of the flow over the network;
PC- calculation of network channel capacities to ensure the specified quality of service for network subscribers.
In the case of using methods for replacing (removing, adding) branches, the following steps are required:
VC- selection of a candidate branch for replacement in accordance with a certain replacement criterion;
SW- the actual replacement (deletion, addition) of the branch.
One of the most important stages in the synthesis of a switched communication network is CS - statistical modeling of the process of network functioning under various laws of communication network control. Currently, there are no methods for calculating a communication network that are adaptive to the laws of managing its resources and load. Moreover, there are no general methods for calculating the channel capacities of a network for arbitrary procedures for choosing information transmission paths. In this regard, simulation programs are of significant interest, which make it possible to determine the indicators of the quality of service for communication network subscribers under various control laws and procedures for choosing information transmission paths. These include, for example, programs for simulating the relief method, simulating a game method for choosing a connecting path, simulating isorhythmic network control, simulating a static and dynamic path selection strategy (programs simulate a packet switching network), etc. Programs for statistical assessment of the quality of service, as a rule , determine only the integral quality index, since for calculating all differentiated quality criteria with the same accuracy, the simulation time, determined by the necessary statistics for the flow of minimum intensity, is too long. In this regard, the already mentioned programs have become widespread. AC- analysis of the communication network, allowing to calculate differentiated indicators of quality of service.
In general, procedures PC, SU And AC objectively aimed at solving the same problem - establishing a correspondence between the required indicators of the quality of service for subscribers of a communication network and network parameters (structural and channel), and the first execution of the procedure PC precedes the first execution of procedures SU, AS(procedures may be repeated in the process of iterative design). Taking into account the design costs, it seems appropriate to execute the sequence PC, AC or PC, SU as the final stage of each iterative design step and sequence PC (AC And SU) as the final stage of the last design step.
The noted procedures are, apparently, the main procedures for the synthesis of communication networks (the issue of "functional completeness" of the presented set of procedures is of independent interest and is not considered here). Auxiliary synthesis procedures include procedures such as cost function approximation, network cost calculation, checking the number of iteration steps, etc.
Naturally, different sequences of design procedures are possible, but given that HS- initial procedure, SU"alternative" AC, WA immediately follows. VC. procedure CW(Cd) procedure preceded AW(Ad), procedure PC- procedures RP, Ad, Cd, procedure SU (AS) - AW, CW, PC, the number of possible sequences of procedures is significantly reduced.
Assuming that:
the process of synthesizing a communication network is a step-by-step iterative procedure, and the number of design steps is equal to the number of initial network structures, and the number of iterations in each step is either predetermined or depends on the result of comparing the costs of network options [iterations stop if the cost of the network option is i-th the iteration step is greater than the cost of the variant; networks on (i-1)-th step];
subsequence Ad, cd, related to the distribution of flows over individual and common bundles of channels of the communication network should be performed after the RP procedure;
the procedure for replacing branches is performed at the end of each iteration (taking into account that the procedures CW, CD are essentially substitution procedures - in these cases, additions);
procedure SU or AS is performed at each iteration; CS and AS procedures are jointly performed at the end of each design step;
The sequence of synthesis procedures shown in Fig. 1 seems to be the most appropriate. 3.1, where C is the structure representation procedure
communication networks, "cost" - the procedure for calculating the total cost of channel capacities of a communication network, 1 - counter of the number of iterations, 2 - counter of the number of initial network structures. Place sequence A W, CW immediately before the RP or immediately after the PC is determined by the type of structure variant presented. Limit cases: if WITH- tree, then AW, CW follows C, if C is a complete graph, then A W, CW follows PC. In accordance with the proposed synthesis methodology, the main design procedures are the procedures HS, AW, CW, RP, Ad, Cd, PC, AC, SU And ZV.
As the practice of designing distributed non-hierarchical communication networks of large dimensions shows, the choice of the local optimization stage as the initial structure - the structure of the minimum spanning tree or star graph - leads to a very non-optimal final network structure. This is explained by the fact that such a choice of the initial network structure imposes very significant restrictions on the subsequent stages of optimization, and in the general case these restrictions are not justified. On the other hand, the choice of the second limiting variant of the initial network structure - the complete graph - for networks of large dimensions is unacceptable because of the huge amount of necessary calculations. In addition, the two noted limiting options for the initial network structure almost do not take into account the nature of the load graph presented for implementation. G(Y): the full graph provides direct bundles of channels for all information transmission requirements, the minimal tree option does not allow the possibility of distributing the transmitted information flows over different transmission paths.
In connection with the above, the most appropriate variant of the initial network structure in the synthesis of a distributed communication network of large dimension is the structure of the load graph (the minimum tree, the star graph and the complete graph can be considered as the initial structures of centralized networks or as the initial structures of distributed networks of small dimension). Since the lease payment for network channel-kilometers is taken as a criterion for the optimality of network synthesis, the application of all procedures of the local optimization stage directly to the graph G(Y) or to structures derived from G(Y), is correct. In some cases the graph G(Y) it is expedient to replace the graph G(Y\ε) obtained from G(Y) removal of edges connecting vertices with a mutual load less than ε *.
When considering the graph G(Y)(G(Y\ε)) as the initial structure of the distributed network design process
*) Since the graph G(Y) for general-purpose communication networks is, as a rule, fully connected, its transformation into the graph G(Y \ ε) is necessary.
the sequence of network synthesis procedures is represented by the diagram in fig. 3.2 [here: G(Y)- initial structure].
Assuming the availability of AS programs (network analysis) and SU ( flow distribution simulation) and the selection of candidate branches for replacement based on the results of the procedures AS, SU
the definition of the local optimization process lies in the choice of procedure algorithms AW, CW, Ad, CD and PC. Let's consider some options for solving this problem.
NETWORK ZONING
In the general case, the solution of the problem of synthesis of distributed networks
connections by branch replacement methods (procedures cw, cd, RP, SR) requires 0(n 3)-O(n 6) calculations, where n is the number of network nodes, and for networks with more than a few hundred nodes, it is not possible. One of the possible ways to reduce the design complexity is to represent the synthesized large network as a set of smaller networks (zones) and reduce the solution of the problem of synthesizing a large network to solving the problems of synthesizing networks, its components (zone and interzone networks). The second reason for the expediency of splitting (zoning) a communication network is the need to allocate control zones for a communication network with localization of control and management information within each zone.
If the desire to reduce the scope of design requires the implementation of the network zoning procedure according to the structure as a preliminary procedure of the stage of its local optimization, then the network zoning procedure for control is performed, as a rule, after the synthesis of the network structure.
The network zoning stage includes the solution of two main issues - determining the number of zones (partitioning blocks) of the network and choosing the principles for grouping nodes into zones, and the solution of these issues is most difficult for networks of a non-hierarchical structure. In the case of network zoning for management, the number of partition blocks generally depends on the network structure and the volume of the transmitted message flow, the adopted management principles, the performance characteristics of hardware and software management tools, etc. At present, there is no general methodology for dividing the network into management zones. the optimal choice of the number of control zones remains open. At the same time, the option of enumeration by the number of possible zones should not be excluded (due to the one-time nature of the solution of the zoning problem and the small value of the enumeration).
Number Nc network partitioning blocks according to the structure is selected based on the minimum design volume and is defined as , where n- the total number of nodes of the synthesized network;
The number of central nodes in each zone. The network is built as a collection Nc zone networks and interzone network on , nodes (assuming the same number of central nodes in each zone). If we assume that in each zone network there is only one central node, and this is usually true for low-load networks, then Nc = .
Determining the principles of grouping network nodes into zones in the general case is associated with the issues of estimating the cost and throughput of communication lines, with the tasks of distributing the flow over the network and ensuring structural reliability. The absence of theoretical results on the grouping problem necessitates the search for heuristic principles of grouping. The natural principle of grouping is the requirement for minimal information connectivity both between control zones and between zones according to structure, since such a grouping quite correctly localizes the tasks of control and structural synthesis and allows minimizing the cost of the interzone network and interzone control.
The expediency of using the graph has already been noted above. G(Y)(G(Y\ε)) as the initial structure of the process of local optimization of the communication network. Since the weights of the edges of the graph G(Y)(G(Y\ε)) are equal to the information gravity between the corresponding network nodes, the expediency of its use (with the selected grouping principle) is quite obvious as a graph of the network structure required for zoning (cutting).
The graph cutting problem belongs to the class of extremal combinatorial problems, i.e. problems in which it is required to determine the minimum (maximum) of some function F, defined on the aggregate
