KR100659719B1 - Ring-based communication network design method for building the least cost communication network in computing devices - Google Patents

Abstract

1. TECHNICAL FIELD OF THE INVENTION

The present invention relates to a ring-based communication network design method for establishing a minimum cost communication network in a computing device.

2. The technical problem to be solved by the invention

The present invention provides a ring-based communication network in a computing device for constructing a ring cover at a minimum cost by configuring rings centered around a hub node in order to service inter-node communication demands at a minimum cost in a network topology consisting of a node and a link set. To provide a computer-readable recording medium recording a design method and a program for realizing the method.

3. Summary of Solution to Invention

The present invention includes a first step of finding a ring cover in a given network topology; A second step of obtaining capacity and construction cost of equipment to be installed for each ring of the ring cover found in the first step; A third step of obtaining a dual value vector by generating a linear planning problem for minimizing the construction cost; A fourth step of determining whether there is a ring in the given network topology where the sum of the pairwise vectors is greater than a total cost; As a result of the fourth step, if present, the ring is included in the original ring cover, the least expensive equipment to be installed in the ring is calculated, the ring construction cost is calculated, and the information about the ring is included in the linear planning problem. Adding as a new row, proceeding to said third step; And a sixth step of making the optimal ring the solutions obtained if the determination result of the fourth step does not exist.

4. Important uses of the invention

The present invention is used in a wireless communication system and the like.

Network, ring-based, topology, ring cover, hub node, minimum cost

Description

Method for Communication Network Design based Ring for the Minimun Expense}             

1 is an exemplary configuration diagram of a hardware system to which the present invention is applied.

2 is an embodiment configuration of a ring-based communication network according to the present invention.

3 is a flowchart illustrating an embodiment of a ring-based communication network design method according to the present invention;

* Explanation of symbols for the main parts of the drawings

201: hub 202: digital line splitter (DCS)

The present invention relates to a ring-based communication network design method for accommodating communication requirements given in one network topology at a minimum cost and a computer-readable recording medium having recorded thereon a program for realizing the method.                         

 A network topology represents a possible connection state within a network. The topology shows the hardware configuration and shows which nodes can communicate. The basic computer network topologies are star, ring, and bus. Any of these three topologies is hard to find in pure form, and most computer networks are mixed. .

In particular, the ring-shaped computer system is generally ring-shaped with computer systems of the same size without a computer system that is the center of the communication network. When one system sends a message to another, the message goes round the ring until it reaches its destination.

However, the communication requirements given to one network topology vary from system to system, which makes it difficult to determine the optimal cost for constructing a network.

The present invention has been proposed to solve the above problems, and in order to service the inter-node communication demands at a minimum cost in one network topology consisting of a node and a link set, the rings are configured around the hub node at a minimum cost. It is an object of the present invention to provide a ring-based communication network design method in a computing device for constructing a ring cover and a computer-readable recording medium recording a program for realizing the method.

According to an aspect of the present invention, there is provided a method of designing a ring-based network for establishing a least cost communication network in a computing device, comprising: a first step of finding a ring cover in a given network topology; A second step of obtaining capacity and construction cost of equipment to be installed for each ring of the ring cover found in the first step; A third step of obtaining a dual value vector by generating a linear planning problem for minimizing the construction cost; A fourth step of determining whether there is a ring in the given network topology where the sum of the pairwise vectors is greater than a total cost; As a result of the fourth step, if present, the ring is included in the original ring cover, the least expensive equipment to be installed in the ring is calculated, the ring construction cost is calculated, and the information about the ring is included in the linear planning problem. Adding as a new row, proceeding to said third step; And a sixth step of making the optimal ring the solutions obtained if it does not exist as a result of the determination in the fourth step.

On the other hand, the present invention provides a computing device with a processor, comprising: a first function of locating a ring cover in a given network topology; A second function of obtaining capacity and construction cost of equipment to be installed for each ring of the ring cover found in the first function; A third function of obtaining a dual value vector by generating a linear planning problem for minimizing the construction cost; A fourth function of determining if there is a ring in the given network topology where the sum of the pairwise vectors is greater than the total cost; As a result of the determination of the fourth function, if present, the ring is included in the original ring cover, the least expensive equipment to be installed in the ring is selected, the ring construction cost is calculated, and the information about the ring is included in the linear planning problem. A fifth function proceeding to said third function in addition as a new row; And a computer-readable recording medium having recorded thereon a program for realizing a sixth function for making the optimum ring the solutions obtained if it does not exist as a result of the determination of the fourth function.

The above objects, features and advantages will become more apparent from the following detailed description taken in conjunction with the accompanying drawings. Hereinafter, exemplary embodiments of the present invention will be described in detail with reference to the accompanying drawings.

1 is an exemplary configuration diagram of a hardware system to which the present invention is applied.

As shown in FIG. 1, a general hardware system includes a central processing unit 11, a main memory device 12 connected to the central processing device 11, and an auxiliary memory device 13 connected to the main memory device 12. And an input device 14 and a display device 15 connected to the central processing unit 11.

Here, the hardware system, the central processing unit 11 for controlling and managing the overall operation of the computer, the program stored in the central processing unit 11 and stores a variety of data used during or during operation And a main memory device 12, an auxiliary memory device 13, and input / output devices 14 and 15 for inputting and outputting data to and from a user.

The auxiliary memory device 13 stores a large amount of data, and the input / output devices 14 and 15 include a general keyboard, a display device, and a printer.

In the main memory device 12 of the hardware system as described above, a program for constructing a ring cover at a minimum cost is stored, and is executed under the control of the CPU 11.

2 is a block diagram of an embodiment of a ring-based communication network according to the present invention.

As shown in FIG. 2, the ring-based communication network has constructed a total of two rings to cover seven nodes including the hub node 201, and equipment of appropriate capacity to satisfy communication demands of nodes belonging to each ring. And the equipment is connected by optical cable. Here, the hub node 201 is one node in an important position among the network nodes, and all the rings must pass through the hub node 201. The ring represents a connected set of one or more nodes / links via the hub node 201. For reference, the set of rings is called a ring cover.

On the other hand, each node in the network must belong to one of the rings.

The equipment capacity for each ring should be the same equipment, and equipment with a capacity larger than the sum of the communication demands in and between rings should be installed. For reference, the ring-to-ring connection is mediated by the Digital Circuit Splitter (DCS) 202 equipment at the hub node, but the present invention assumes that the capacity of the Digital Circuit Splitter (DCS) 202 equipment is sufficient and excludes it from the algorithm design. .

3 is a flowchart illustrating a ring-based communication network design method according to the present invention.                     

First, the data given for the ring-based communication network design method is as follows.

Network topology "G" is represented by "(N, L; h, l _ij )", where "N" is a node set, "L" is a link set, "h" is a hub node, "l _ij Is the link distance between the nodes "i" and "j".

Inter-node communication demand data is "(d _ij )", where all nodes "i" and "j" belong to node set "N".

The cost of establishing a link (i, j) is "C _ij ", where all nodes "i" and "j" belong to node set "N".

The type of communication equipment "T" is represented as "{t; (P _t , Q _t )}", where "t" is the equipment, "P _t " is the price of the equipment "t", and "Q _t " is the equipment The dose of "t" is shown.

The cost of the optical cable is "F _ijt " where all nodes "i" and "j" belong to node set "N" and equipment "t" belongs to communication equipment type "T".

Also, the decision variables given for the ring-based communication network design method are as follows.

A ring-based communication network design method using the given data and decision variables is as follows.

For reference, for convenience of explanation, "N _r " includes a set of nodes via ring "r", "Lr" includes a set of links via ring "r", and "R _i " includes node "i". It is called a set of rings.

As shown in FIG. 3, first find the correct ring cover in a given network topology (301). Here, a representative method for finding the correct ring cover in a given network topology is to use one ring cover as a set of rings including each node via a hub node.

For each ring of the obtained ring cover, the capacity of equipment to be installed and the construction cost of each ring are calculated (302).

Here, the sum of the communication demands of the ring is represented by the sum of the sum of the communication demands between the nodes in the ring and the sum of the communication demands between the nodes belonging to the ring and the nodes belonging to the other ring, which is represented by Equation 1 below. It was.

Therefore, the equipment capacity to be installed is the least expensive among the devices having a capacity larger than the combined communication demand of the ring.                     

Then, the construction cost of each ring is calculated as shown in [Equation 2].

Here, the first item is the sum of the link opening costs of the ring, the second item is the sum of the optical cable costs of the ring, and the third item is the sum of the equipment costs. In the third item, the device is represented by the product of the price of the selected device and the number of nodes in the ring, since the device of the same capacity must be included in each node of the ring. Equation 2 is the total cost of opening each ring.

Next, a linear programming problem such as a flowchart is generated using the ring cover and the construction cost of each ring obtained above to obtain a pairwise vector (303). Here, the objective equation as shown in [Equation 3] is to minimize the sum of ring construction costs, and the meaning of the constraint as shown in [Equation 4] is that each node must belong to one of the rings passing through the node. And the decision variable for ring selection must be greater than or equal to zero.

)는 선형계획 문제를 해결하여 나오는 결과값의 일종이다.The solution of the linear planning problem is to use a commercial package (CPLEX, etc.), where the dual value vector (

) Is a result of solving the linear planning problem.

Next, it is determined whether a ring that satisfies the inequality of Equation 5 below using the obtained dual value vector exists in the topology of a given network (304).

Here, the inequality of Equation 5 below is a general method in the linear planning solution for checking whether the solution of the linear planning problem can be further improved. As a method for checking whether a ring that satisfies the inequality of Equation 5 below, a well-known network search method (such as depth-first search) may be used.

는 쌍대값 벡터,

은 링구축을 위한 총비용을 나타낸다.here,

Is a dual value vector,

Represents the total cost for ring construction.

As a result of the determination, if there is a ring that satisfies the condition of Equation 5, the ring is included in the original ring cover, the minimum cost equipment to be installed in the ring is selected, and the ring construction cost is calculated. The information about this ring is added to the linear planning problem as a new column, and the process proceeds to step 303, where a linear planning problem is created to minimize the sum of the ring construction costs and a dual value vector is obtained.

인 링들을 최종 링들로 택하고, 모든 알고리듬을 마친다(306). 이 때, 선형계획 문제의 목적식([수학식 3])의 값이 최소 링 설계 비용이 된다.In the determination result 304, if none of the rings satisfy the condition of Equation 5,

The in rings are taken as the final rings and all algorithms are completed (306). At this time, the value of the objective equation ([Equation 3]) of the linear planning problem becomes the minimum ring design cost.

The method of the present invention as described above may be implemented as a program and stored in a computer-readable recording medium (CD-ROM, RAM, ROM, floppy disk, hard disk, magneto-optical disk, etc.).

The present invention described above is not limited to the above-described embodiments and the accompanying drawings, and various substitutions, modifications, and changes are possible in the art without departing from the technical spirit of the present invention. It will be clear to those of ordinary knowledge.

According to the present invention as described above, in order to service the inter-node communication demands in a single network topology consisting of a node and a link set at a minimum cost, the rings are configured around the hub node to build a ring cover at a minimum cost. This can reduce costs.

Claims (6)

A ring-based communication network design method for constructing a least expensive communication network in a computing device, Finding a ring cover in a given network topology; A second step of obtaining capacity and construction cost of equipment to be installed for each ring of the ring cover found in the first step; A third step of obtaining a dual value vector by generating a linear planning problem for minimizing the construction cost; A fourth step of determining whether there is a ring in the given network topology where the sum of the pairwise vectors is greater than a total cost; As a result of the fourth step, if present, the ring is included in the original ring cover, the least expensive equipment to be installed in the ring is calculated, the ring construction cost is calculated, and the information about the ring is included in the linear planning problem. Adding as a new row, proceeding to said third step; And A sixth step of making the optimal ring the solutions obtained if it does not exist as a result of the determination in the fourth step Ring-based communication network design method for constructing a minimum cost communication network comprising a. The method of claim 1, The capacity of the equipment of the second stage, The sum of the communication demands between the nodes in the ring and the communication demands between the nodes in the ring and the nodes in the other ring, which is the sum of the least expensive equipments with more capacity than the combined demands of the rings. Ring-based communication network design method for building a minimum cost communication network, characterized in that. The method of claim 1, The construction cost of the second stage, A method for designing a ring-based network for building a network of minimum cost, comprising the sum of link establishment costs, the sum of the costs of optical cables in a ring, and the sum of equipment costs. The method of claim 1, The linear planning problem of the third stage, A method for designing a ring-based communication network for establishing a least-cost communication network, wherein the sum of a product of total cost and a degree of ring selection is minimized. The method of claim 4, wherein The degree of selection of the ring, The total ring selectivity is 1 in all networks, and the ring selectivity is "0" or more. In a computing device having a processor, A first function of locating a ring cover in a given network topology; A second function of obtaining capacity and construction cost of equipment to be installed for each ring of the ring cover found in the first function; A third function of obtaining a dual value vector by generating a linear planning problem for minimizing the construction cost; A fourth function of determining if there is a ring in the given network topology where the sum of the pairwise vectors is greater than the total cost; As a result of the determination of the fourth function, if present, the ring is included in the original ring cover, the least expensive equipment to be installed in the ring is selected, the ring construction cost is calculated, and the information about the ring is included in the linear planning problem. A fifth function proceeding to said third function in addition as a new row; And A sixth function that makes the optimum ring the solutions obtained if it does not exist as a result of the determination of the fourth function A computer-readable recording medium having recorded thereon a program for realizing this.

Images