JP4959601B2 - Admission control method and control system based on traffic statistics information, and program thereof - Google Patents

Description

  The present invention relates to an admission control method and control system based on traffic statistical information, and a program thereof, and more specifically, there is a network composed of a plurality of nodes and a plurality of links. There is an admission control function that calculates the admission allowance of the service that flows into the network using information related to the service used and information related to the guarantee level of communication quality as input. An admission control method and an admission method for calculating a congestion occurrence rate in a link and calculating a reception allowance of a service flowing into the network based on consistency between the congestion occurrence rate in a certain link and information on a guarantee level of communication quality The present invention relates to a control system and its program.

  Conventionally, there is a network composed of a plurality of nodes and a plurality of links, and information relating to this network, information relating to services using this network, and information relating to the guarantee level of communication quality are input to this network. There is an admission control function for calculating the allowable admission amount of the service to be performed. In such a network, in order to check whether there is sufficient network resources for a service that is about to flow into this network, information on the service flow accommodated by a link in the network is constantly grasped. It was necessary to keep.

FIG. 1 is an explanatory diagram of a conventional admission control method.
FIG. 1A shows a state in which the reception control function 1 receives information related to a service using a network and information related to the network and outputs a determination result of whether or not the service can be received. Information about the network includes network topology, certain link bandwidth, routing table information, and the like.
Further, as information on the service using the network, the IP address obtained from the Call-ID line of SIP (call control protocol used in Internet telephone applying VoIP), the C line of SDP (Session Description Protocol), etc., There is information about the required bandwidth obtained from the b line of SDP.

FIG. 1-2 shows details of the reception control function. Information about the network is held in the network topology DB 12. When a service using the network is about to flow in, the route calculation unit 11 uses the information read from the network topology DB 12 and the IP address of the service flow included in the information about the service using the network. Calculate the service flow path. The flow path is sent to the reception determination unit 14.
In order to confirm that the requested bandwidth can be secured on the service flow path, the reception determination unit 14 acquires information on the capacity of each link from the network topology DB 12 and information on the bandwidth in use in each link from the used bandwidth management DB 13. . If there is even one link that cannot accommodate the new service flow, the acceptance is rejected.
If the service flow can be accommodated in each link on the route, the reception is permitted and the used bandwidth DB 13 is updated.

  In this case, the acceptance / rejection is judged based on whether or not the network resource requested by the newly arrived service remains. Therefore, it is necessary to always manage information about network resources, and if the scale of the network to be managed becomes large, a state explosion occurs, so that scalability is lacking.

As a previously proposed technique, Katsushi Yamaoka, which can be searched with a URL (http://www.tier.ac.jp/publications/j/chronic/423/423-1.html) (see Non-Patent Document 2) Formula: “Aiming at the realization of efficient Internet video communication-Study on the coexistence accommodation method of the stream on the Internet”. According to this, in general packet switching networks, it is not necessary to establish a line as in the circuit switching network, and attention is paid to the fact that communication can be started at an arbitrary time, and the lack of resources should be confirmed after communication is started. Focusing on the fact that it can be realized by checking the presence or absence of packet loss, etc., and does not require strict resource management, so it can be realized relatively easily. A change of concept has been introduced in which a flow is temporarily accommodated in a network, and whether or not the flow causes congestion is checked before receiving the flow.
And 1) When a new flow arrives, each node sets Drop Precedence higher than Drop Precedence (discard priority) of the flow already officially accommodated in the same flow, and temporarily accommodates it as a relay flow. 2) After a lapse of a certain time, it is confirmed whether or not a packet with Drop Precedence is set. 2-a) If there is no loss in the drop precedence packet, it is determined that a new flow can be accommodated, and drop precedence is set for the flow. 2-b) If there is a loss in the Drop Precedence packet, it is determined that the new flow causes congestion in the network, and the flow is discarded.
In this way, admission control is performed based on packet loss caused by insufficient processing capacity.
Therefore, there is a problem that packet loss becomes large.

Z. -L. Zhang et al. "On scalable design of bandwidth brokers," IEICE Trans. Commun. vol. E84-B, no. 8, Aug. 2001. URL http: // www. tiech. ac. jp / publications / j / channel / 423 / 423-1. html

  As described above, in the conventional method, when the network size is increased, the amount of information to be managed becomes enormous and causes a state explosion, so the lack of scalability has been a problem.

(the purpose)
Accordingly, an object of the present invention is to provide an admission control method and control system based on traffic statistical information that does not require constant grasping of service flow information accommodated by a certain link in the network and is capable of admission control with excellent scalability. , As well as providing the program.

  In the admission control method based on the traffic statistics information of the present invention, there is a network composed of a plurality of nodes and a plurality of links, information on the network, information on a service using the network, and a guarantee level of communication quality. An admission control unit that calculates the allowable admission amount of the service that flows into this network is provided as input, and the admission control unit calculates the probability (congestion occurrence rate) that congestion will occur at a certain link in the network. In addition, it is characterized in that the allowable amount of service flowing into this network is calculated based on the consistency between the congestion occurrence rate in a certain link and information on the guarantee level of communication quality.

The admission control program according to the present invention relates to a network composed of a plurality of nodes and a plurality of links in a computer, information relating to the network, information relating to a service using the network, and a guarantee level of communication quality. Procedures for inputting information, procedures for maintaining the usage rate of each link in the requested bandwidth database for each link, and procedures for creating probability density distribution data for each usage time zone for each link from the requested bandwidth database for each link , A procedure for generating a probability distribution function based on the probability density distribution data, a procedure for calculating a congestion occurrence rate, a procedure for comparing the congestion occurrence rate with a threshold value for the congestion occurrence rate, and the congestion occurrence rate exceeds the threshold value. If so, calculate the procedure for generating the probability distribution function and the maximum acceptable capacity condition that causes the congestion occurrence rate to be less than the threshold. That procedure, based on the reception capacity of the condition in accordance with the arrival time period on the service request, the procedure for controlling the service request, a program for executing, respectively.
In the present invention, service flow information is provided by calculating a congestion occurrence rate in a link in a network based on information such as a bandwidth amount requested by a service and accepting and judging within a range in which the congestion is suppressed to a constant value. This eliminates the need to keep track of

  According to the present invention, by collecting information related to services that use a network and using statistical information, it is possible to perform admission control that is difficult to increase management information in the network and that is highly scalable.

Hereinafter, embodiments of the present invention will be described in detail with reference to the drawings.
FIG. 2 is a configuration diagram of an admission control system according to an embodiment of the present invention.
FIG. 2A illustrates a state in which the reception control function 2 under the control of the computer receives information on a service using the network, information on the network, and a guarantee level of communication quality, and outputs a determination result of whether or not the service can be received. Is shown.
Among these inputs, the information regarding the service using the network and the specific contents of the information regarding the network are the same as those in the conventional admission control method shown in FIG. In addition, the newly added communication quality guarantee level is given here as a threshold value of the congestion occurrence rate, and is assumed to be input by the network operator.

FIG. 2-2 is a diagram illustrating a detailed configuration of the reception control function.
As shown in FIG. 2B, the admission control function 2 of the present invention includes a route calculation unit 21, a network topology DB 22, a request bandwidth DB 23 for each link, a statistical processing unit 28, and a congestion occurrence rate calculation unit 27. The congestion occurrence rate comparison unit 26, the reception ratio calculation unit 25, and the reception determination unit 24. Each of these processing units executes processing under the control of a computer.

  In the admission control function 2 of the present invention, the congestion occurrence rate in a certain link in the network is calculated based on statistical information such as a bandwidth required when the service flows into the network, and the congestion occurrence rate is set to a certain value or less. An allowable reception amount for suppressing the amount is calculated, and reception control is performed based on the allowable reception amount. As a result, it is not necessary to constantly grasp the information of the service flow accommodated by a certain link in the network, and the amount of information to be managed can be suppressed, so that the admission control function 2 with excellent scalability can be obtained.

  This admission control function 2 includes network topology, information on a network such as a bandwidth of a link, routing table information, a network topology DB 22 for registering a route calculated by the route calculation unit 21, and information on a service including an incoming / outgoing IP address. , And a route calculation unit 21 that calculates a route based on information read from the network topology DB 22, a service that uses a network such as a flow route and requested bandwidth information from the route calculation unit 21, and a requested bandwidth A request bandwidth DB 23 for each link for registering information on the link, and a statistical processing unit 28 that inputs information from the request bandwidth DB 23 for each link and creates probability density distribution data for each time zone of the usage rate in each link; Input probability density distribution from statistical processing unit 28 and calculate congestion occurrence rate When the congestion occurrence rate calculating unit 27 to be input, the congestion occurrence rate which is the calculation result of the congestion occurrence rate calculating unit 27 and the threshold value of the congestion occurrence rate input from the outside are input, and the calculation result exceeds the threshold value Includes a congestion occurrence rate comparison unit 26 that instructs the reception ratio calculation unit 25 to calculate, and information from the statistical processing unit 28, a threshold value of the congestion occurrence rate, and a maximum value based on a command from the congestion occurrence rate comparison unit 26. The acceptance ratio calculation unit 25 for calculating the condition of the acceptance acceptance amount, and the condition that is the calculation result from the acceptance ratio calculation unit 25 are input, and the service request is randomly selected based on the acceptance ratio according to the time zone when the service request arrives. It is comprised from the reception determination part 24 which refuses.

  In addition, in the admission control function 2 shown in FIG. 2A, the information regarding the network input to the admission control function 2 includes information on the network topology, bandwidth information of a link in the network, and flow path information using the network. It is also characterized by being either or a combination. That is, in FIG. 2-1, the network-related information input to the admission control function 2 is not limited to the combination of the network topology, the link bandwidth, and the routing table information as shown in the figure. Any one, two, three, or one, two, three, or four combinations of the flow path information added thereto may be used.

  In addition, the admission control function 2 shown in FIG. 2A is characterized in that the guarantee level of communication quality input to the admission control function 2 is a congestion occurrence rate threshold. Specifically, the threshold value of the congestion occurrence rate is input to the admission control function 2 in FIG. 2-2 and added to the congestion occurrence rate comparison unit 26. By considering the threshold of the link usage rate (link capacity, etc.) with respect to the congestion occurrence rate (see FIG. 3-1) calculated by the congestion occurrence rate calculation unit 27, an area where no congestion occurs is an acceptance ratio calculation unit. It is determined whether or not the request input by the reception determination unit 24 is accepted.

  In addition, the admission control function 2 shown in FIG. 2A is characterized in that the information regarding the service using the network input to the admission control function 2 is information obtained from SIP signaling, description by SDP, and the like. . SIP is one of the call control protocols used in Internet telephones using VoIP, and has functions close to the public telephone network compared to similar protocols such as a transfer function and a caller ID notification function. This time is also short. SDP is a platform for developing and executing a new communication service by combining existing telephone services and data services such as e-mail. SIP Call. It may be the information about the requested bandwidth obtained from the ID line, the SDP C line, etc., the SDP b line, etc.

  In addition, in the admission control function 2 shown in FIG. 2A, information regarding the service using the network input to the admission control function 2 is statistically processed from information obtained from SIP signaling, description by SDP, and the like. It is also characterized by information.

  In FIG. 2B, information on the network is held in the network topology DB 22 as in the conventional method. Further, the route calculation unit 21 calculates the route of the new service flow using the information obtained from the network topology DB 22 and the arrival / departure IP address included in the new service request message (SIP, SDP, etc.). The flow path information and the requested bandwidth are input to the requested bandwidth DB 23 for each link.

The requested bandwidth DB 23 for each link holds the usage rate for each link on the flow path. The data in the requested bandwidth DB 23 for each link is stored separately for each day and each time zone as shown in the lower left table of FIG.
In the statistical processing unit 28, information on the recent several days is acquired from the request bandwidth DB 23 for each link, and the probability density of the usage rate for each link as shown in the lower right table of FIG. 2-2. Create distribution data.

The congestion occurrence rate calculation unit 27 generates a probability distribution function based on the probability density distribution input from the statistical processing unit 28, and calculates the congestion occurrence rate.
In the congestion occurrence rate comparison unit 26, the calculation result of the congestion occurrence rate calculation unit 27 is compared with a threshold value, and when the calculation result exceeds the threshold value, the maximum occurrence rate such that the congestion occurrence rate is less than the threshold value. The condition of the allowable amount is calculated.
The acceptance ratio calculation unit 25 can calculate the acceptance ratio using the probability density distribution before the acceptance control is applied.
There are two methods for calculating the acceptance ratio, both of which are performed before the acceptance control is applied.
The first is a method of using a probability density function before application of admission control as it is, and the second method is to generate a probability density function after application of admission control and then calculate the congestion occurrence rate, and the value is a threshold value. This is a method of calculating the maximum acceptance ratio while confirming whether or not the number exceeds.
That is, in the second method, a probability density function (and probability distribution function) is generated as a method for calculating the congestion occurrence rate after admission control in order to determine whether or not to accept a service request. The reception ratio is calculated.
By the way, when the acceptance control is uniformly performed for all services, if the acceptance ratio is r and the probability density function before application of acceptance control is p (x), the probability density function q (· ) Is expressed by the following equation.
q (rx) = p (x) / r

For example, it is assumed that the probability density distribution of a certain link usage rate follows a normal distribution, the average usage rate is 88%, and the standard deviation of the usage rate is 10%.
At this time, the maximum average link usage rate such that the congestion occurrence rate is less than 10% is 80%. In this case, in order to suppress the average link use necessity to 80%, it can be understood that one eleventh of all service requests should be rejected. The reception ratio calculation unit 25 calculates such a value and inputs it to the reception determination unit 24.

By performing the above processing for every service request, the congestion occurrence rate for each time zone is clarified for all links in the network. In the reception determination unit 24, the reception ratio according to the time zone when the service request arrives Randomly reject service requests based on
In the method of the present invention, it is not necessary to have the use band management DB 13 as compared with the conventional method, and the scalability is excellent.

FIG. 3 is a diagram illustrating calculation contents inside the functions of the reception ratio calculation unit 25, the congestion occurrence rate calculation unit 27, the congestion occurrence rate comparison unit 26, and the like of FIG.
The graph in FIG. 3A shows an example in which a certain link usage rate in the network follows a normal distribution. In this case, for example, when a certain link band in the network is given, the congestion occurrence rate in the link can be calculated by calculating the distribution function.

  FIG. 3-2 is a diagram illustrating a relationship among the congestion occurrence rate, the average value of the link usage rate, and the standard deviation in a certain link in the network. As shown in the figure, the congestion occurrence rate increases as the average value of the link usage rate increases and as the standard deviation of the link usage rate increases. The acceptance refusal rate is determined by the distance away from the area where the congestion occurrence rate satisfies the communication quality guarantee level.

FIG. 4 is a process flowchart of the reception control function of the present invention.
Figure 4 (a) is a flow you calculate the reception capacity of the service request flowing into the network under the control of the computer. First, information relating to the network, information relating to a service using the network, and information relating to a guarantee level of communication quality are input to a network composed of a plurality of nodes and a plurality of links (step 101). Next, the usage rate of each link is held in the requested bandwidth database 23 for each link (step 102). Next, the statistical processing unit 28 creates probability density distribution data for each time zone of the usage rate in each link from the requested bandwidth database 23 for each link (step 103). Next, the congestion occurrence rate calculation unit 27 generates a probability distribution function based on the probability density distribution data (step 104). Similarly, the congestion occurrence rate calculation unit 27 calculates the congestion occurrence rate based on the congestion occurrence rate (step 105). Next, the congestion occurrence rate comparison unit 26 compares the congestion occurrence rate with a threshold value of the congestion occurrence rate (step 106). As a result of the comparison, if the congestion occurrence rate exceeds the threshold value (step 107), a condition for the maximum acceptable amount that allows the congestion occurrence rate to be less than the threshold value is calculated (step 108).
FIG. 4B is a flow of admission control. The acceptance determination unit 24 determines whether or not to accept the service request based on the acceptable amount condition according to the time zone when the service request arrives (step 109). Only requests that meet the conditions are accepted (step 110).

  If the flow of FIG. 4 is converted into a reception control program and stored in a recording medium such as a CD-ROM, it is installed in a computer having a reception control function, and the program is installed in the computer. If this program is executed, the present invention is easily realized. Further, the program can be generalized by downloading this program from this computer to another computer via the Internet.

It is explanatory drawing of the reception control method by the system which manages the conventional network resource. It is a detailed block diagram of the conventional reception control function. It is explanatory drawing of the reception control method which concerns on one Embodiment of this invention. It is a detailed block diagram of the reception control function which concerns on one Embodiment of this invention. It is an image figure for calculating the congestion incidence rate inside the reception control function in this invention. It is an image figure for determining the acceptance refusal rate inside the acceptance control function in this invention. It is a process flowchart of the reception control function in this invention.

Explanation of symbols

2 Admission Control Function 21 Route Calculation Unit 22 Network Topology DB
23 Required bandwidth DB for each link
24 reception determination unit 25 reception ratio calculation unit 26 congestion occurrence rate comparison unit 27 congestion occurrence rate calculation unit 28 statistical processing unit

Claims (9)

In the admission control method for calculating the allowable amount of acceptance of service requests flowing into the network by computer control and controlling the inflow,
The computer inputs information relating to the network, information relating to a service using the network, and information relating to a guarantee level of communication quality to a network including a plurality of nodes and a plurality of links. The usage rate of each link is kept in each requested bandwidth database,
The computer creates probability density distribution data for each usage time zone from the requested bandwidth database for each link, generates a probability distribution function based on the probability density distribution data, and calculates the congestion occurrence rate. Calculate
When the congestion occurrence rate is compared with the threshold value of the congestion occurrence rate, and the congestion occurrence rate exceeds the threshold value, the condition of the maximum allowable reception amount is set such that the congestion occurrence rate is less than the threshold value. Calculate
An admission control method based on traffic statistics information, wherein whether or not to accept the service request is determined based on the admission allowance condition according to a time zone when the service request arrives. In the admission control method based on the traffic statistical information according to claim 1,
Acceptance based on traffic statistical information characterized by generating a probability density function and a probability distribution function as a method for calculating the congestion occurrence rate after admission control in order to determine whether or not to accept the service request Control method. In the admission control method based on the traffic statistical information according to claim 1,
Admission control based on traffic statistical information, wherein the information on the network is any of network topology information, bandwidth information of a link in the network, route information of a flow using the network, or a combination thereof. Method. In the admission control method based on the traffic statistical information according to claim 1,
The admission control method based on traffic statistical information, wherein the information related to the guarantee level of communication quality is a threshold value of a congestion occurrence rate in a certain link. In the admission control method based on the traffic statistical information according to claim 1,
The admission control method based on traffic statistics information, wherein the information on the service using the network is information obtained from a description by SIP signaling and SDP. In the admission control method based on the traffic statistical information according to claim 1,
The admission control method based on traffic statistical information, wherein the information on the service using the network is information obtained by statistically processing information obtained from SIP signaling and SDP description. In the admission control system that calculates the admission allowance of services flowing into the network under computer control and controls the inflow,
A network topology database that registers network topology, information about the network including bandwidth of a link, routing table information, and calculated route information;
A route calculation unit that inputs information about a service including an incoming / outgoing IP address and calculates a route of the flow based on the information read from the network topology database;
A request bandwidth database for each link for registering information on a service using the network such as a flow route and a request bandwidth from the route calculation unit;
A statistical processing unit that inputs information from the requested bandwidth database for each link and creates data of probability density distribution for each time zone of the usage rate in each link;
Congestion rate calculation unit that calculates probability of congestion by inputting probability density distribution from the statistical processing unit;
When the congestion occurrence rate which is the calculation result of the congestion occurrence rate calculation unit and the threshold value of the congestion occurrence rate input from the outside are respectively input and compared, and the congestion occurrence rate exceeds the threshold Is a congestion occurrence rate comparison unit that calculates a condition for the maximum allowable amount of acceptance so that the congestion occurrence rate is less than a threshold;
An acceptance ratio calculation unit that calculates an acceptance ratio based on an instruction from the congestion occurrence rate comparison unit;
A reception determination unit that inputs a condition that is a calculation result from the congestion occurrence rate comparison unit, and that determines whether to accept the service request based on a reception ratio according to a time zone when the service request arrived. Admission control system based on characteristic traffic statistics. In the admission control system based on the traffic statistical information according to claim 7 ,
In the requested bandwidth database for each link, the link usage rate is stored for each link on the flow path for each day and every time zone, and the admission control system based on traffic statistical information is characterized. A reception control program for calculating an allowable reception amount of a service request flowing into a network under computer control,
A procedure and link for inputting information relating to the network, information relating to a service using the network, and information relating to a guarantee level of communication quality to a network including a plurality of nodes and a plurality of links. A procedure for maintaining the usage rate of each link in each requested bandwidth database, a procedure for creating probability density distribution data for each usage time zone from each requested bandwidth database for each link, based on the probability density distribution data A procedure for generating a probability distribution function, a procedure for calculating a congestion occurrence rate, a procedure for comparing the congestion occurrence rate with a threshold value of the congestion occurrence rate, and the congestion occurrence rate when the congestion occurrence rate exceeds the threshold value The procedure for calculating the condition of the maximum allowable amount that allows the value to be less than the threshold, and the allowable value depending on the time zone when the service request arrives Based on the condition, the service request reception control program for a procedure for determining whether or not to accept the service request, to execute respectively.

Images