JP4852069B2 - BAND ALLOCATION METHOD, BAND ALLOCATION DEVICE, AND BAND ALLOCATION PROGRAM - Google Patents

Description

  The present invention relates to a bandwidth allocation method, a bandwidth allocation device, and a bandwidth allocation program that reduce a reservation rejection rate when a bandwidth to be used is secured in a bandwidth of a path stretched over a network.

In recent years, with the increase in network speed and capacity, individuals and business users are expected to provide various network services. Among such services, there is a bandwidth reservation type service that secures a bandwidth used for a path by reservation.
In the bandwidth reservation type service, it is important to reduce the reservation rejection rate, and attempts have been made to make it possible to accept as many reservations as possible.

For example, Non-Patent Document 1 discloses a case classification when a reservation is rejected and a countermeasure corresponding to the case classification. Specifically, (1) If the request is to be rejected because the bandwidth is insufficient for all the request periods for which the reservation is to be made, the proposal is made to shorten the request period. (2) The reservation is to be made. If the usage start time is rejected due to lack of bandwidth, it will be proposed to change the usage start time. (3) Secured by a part of the request period to reserve the bandwidth by reservation There are three proposals: a proposal to reduce the required bandwidth when there is insufficient bandwidth to be rejected.
Jun Zheng, Baoxian Zhang, Mouftah, HT, “Toward automated provisioning of advance reservation service in next-generation optical internet”, IEEE Communications Magazine, p.68-74 (Dec, 2006)

However, although the countermeasure proposed in Non-Patent Document 1 can reduce the rejection rate of reservation, it is premised that the used bandwidth is reserved one after another in order from the person who made the reservation earlier. Therefore, when there is a reservation using a large bandwidth, the bandwidth of the path is occupied by the reservation. And even if there is a vacant bandwidth in the occupied bandwidth, there is a problem in that the bandwidth cannot be effectively used because it is not lent out to other reservations. In addition, other reservations tend to be rejected, that is, the reservation rejection rate cannot be reduced. In addition, the above-described countermeasures have a problem that the quality of service to the user is deteriorated because the reservation conditions must be changed.
Therefore, in order to solve such a problem, the problem of the present invention is to effectively use an unused unused band of the path band and prevent the band from being occupied, The purpose is to provide a technique for reducing the rejection rate of reservations.

  In order to solve the above-mentioned problem, the invention according to claim 1 allocates a service band for each service to a band of a path extending over a network, and the service based on reservation information related to use of the service band. A bandwidth allocation method used in a bandwidth allocation device for calculating a bandwidth set in a bandwidth, wherein the bandwidth allocation device allocates service identification information for identifying the service and the service for each service. A storage unit that stores the service band, a reserved allocated band that is a band set in the service band, and a usage period of the reserved allocated band; and a processing unit, wherein the processing unit includes: When an input of reservation information including a use request band requesting to be set within a service band of a service and a use request period of the use request band is received, A bandwidth in which the total of the reserved allocated bandwidths of the first service is maximized during the usage request period is calculated as a first maximum allocated bandwidth, and the first maximum allocated bandwidth is calculated from the service bandwidth of the first service. Subtracting the bandwidth to calculate a first free bandwidth, subtracting the first free bandwidth from the usage request bandwidth to calculate the insufficient bandwidth, and if the insufficient bandwidth is positive For a second service different from the first service, a band that maximizes the total of the reserved allocated bands of the second service in the usage request period is calculated as a second maximum allocated band. And subtracting the second maximum allocated bandwidth from the service bandwidth of the second service to calculate a second vacant bandwidth, and according to a future time from the time when the reservation information is received. An operation for reducing the size of the second free band is performed, the second free band at the use end time of the use request period is calculated as a loan band, and the loan band is used as the second service band. The reserved allocation band of the first service set in the service band, the usage request period as the usage period of the reserved allocation band, the reserved allocation band, the usage period of the reserved allocation band, and the second service And storing the information in the storage unit in association with the service identification information.

  According to such a configuration, since the free bandwidth of the second service can be lent to the first service, the free bandwidth can be shared and used effectively by a plurality of services. In addition, “the second vacancy at the use end time of the use request period for the first service is calculated by performing a calculation to reduce the size of the second vacant band as the reservation information is received and the future time. The process of calculating the bandwidth and setting it as the lending bandwidth allocates the lending bandwidth in anticipation of an increase in the usage bandwidth of the second service over time. Therefore, it is possible to prevent a large band from being continuously occupied by the first service. As a result, the rejection rate of reservations for the second service can be reduced.

  According to a second aspect of the present invention, in the bandwidth allocation method according to the first aspect of the present invention, an operation for reducing the size of the second free bandwidth as the future time starts from the time when the reservation information is received. The reduction rate is a constant calculation.

  According to such a configuration, since the reduction rate is constant, there is an effect that it is easy to understand for the user who makes a reservation and the calculation of the lending bandwidth is simplified.

  According to a third aspect of the present invention, in the bandwidth allocation method according to the first aspect, the operation of reducing the size of the second vacant bandwidth as the future time comes from the time when the reservation information is received, The logarithm, the exponent, and the quadratic function, or a combination of them, with the time elapsed from the time when the reservation information was received as a variable,

  According to such a configuration, it is possible to execute an operation using an optimal function in response to a difference in statistical distribution regarding the occurrence frequency of reservations for the second service. In other words, it is possible to adjust the size of the lent bandwidth by executing an operation using an optimal function, and to adjust the ratio of the bandwidth to be secured to the reservation for the second service and the lent bandwidth. become able to. As a result, the rejection rate of reservation can be reduced.

  According to a fourth aspect of the present invention, in the bandwidth allocation method according to any one of the first to third aspects, from the time when the processing unit accepts the reservation information to a use start time of the use period. In the period before the start of use, the leased bandwidth is calculated every predetermined time, and the largest value among the leased bandwidths calculated during the period before the start of use is set as the reserved allocated bandwidth of the first service. The following step is performed.

  According to such a configuration, the lending bandwidth is recalculated every predetermined time in the period before the start of use, and the largest lending bandwidth among the recalculated lending bandwidth is set as the bandwidth allocated to the first service. In addition to the operation and effect of claim 1, it is possible to reduce unfairness with respect to the difference in reservation timing for the user. Further, if the bandwidth (maximum allocated bandwidth in the second service) in which the total of the reserved allocated bandwidth of the second service is the maximum in the period before the start of use is constant, the reservation is made immediately before the use start time. A large lending bandwidth can be allocated, which has the effect of reducing the rejection rate of reservations for the first service.

  According to a fifth aspect of the present invention, in the bandwidth allocation method according to the fourth aspect, when the processing unit determines that the lent bandwidth is larger than the insufficient bandwidth, either the insufficient bandwidth or the lent bandwidth. Performing the step of setting the reserved allocated bandwidth of the first service as

  According to such a configuration, it is possible to lend the bandwidth closest to the insufficient bandwidth, and it is possible to effectively use the bandwidth of the path.

  A sixth aspect of the present invention is the bandwidth allocation method according to any one of the first to fifth aspects, wherein there are a plurality of the second services, and the processing unit is provided for each of the services. When calculating the lending bandwidth, adding the lending bandwidth in the order of services with the largest lending bandwidth from the plurality of lending bandwidths calculated for each service, and when the sum total exceeds the insufficient bandwidth The step of setting the added individual lending bandwidth as the reserved allocation bandwidth of the first service is executed.

  According to such a configuration, it is possible to receive bandwidth lending from a plurality of services, so that it is possible to reduce the reservation rejection rate and to effectively use the bandwidth of the path. Further, since the services are lent in order from the service with the largest available bandwidth, it becomes easier to satisfy the amount of bandwidth necessary for renting, and the calculation processing for renting is reduced. Further, since the number of lent bandwidths can be reduced, the processing amount for path bandwidth management is reduced.

  A seventh aspect of the present invention is the bandwidth allocation method according to any one of the first to fifth aspects, wherein there are a plurality of the second services, and the processing unit is provided for each of the plurality of services. The bandwidth allocation rate is calculated by summing the reserved allocated bandwidths and dividing the total by the service bandwidth, and the lending bandwidth is calculated and added in the order of services with the smallest bandwidth usage rates. When the insufficient bandwidth is exceeded, the step of setting each added lending bandwidth as the reserved allocation bandwidth of the first service is executed.

  According to such a configuration, since the services are lent out in order from the service with the largest available bandwidth, it becomes easy to satisfy the amount of bandwidth necessary for the rent, and the calculation processing for rent is reduced. Further, since the number of lent bandwidths can be reduced, the processing amount for path bandwidth management is reduced. Further, by leveling the bandwidth usage rate, the load is distributed throughout the network, so that stable network operation is possible.

  In order to solve the above-mentioned problem, the invention according to claim 8 assigns a service band for each service to a band of a path stretched over a network, and the service based on reservation information related to use of the service band. A bandwidth allocation method used in a bandwidth allocation device for calculating a bandwidth set in a bandwidth, wherein the bandwidth allocation device allocates service identification information for identifying the service and the service for each service. A storage unit that stores the service band, a reserved allocated band that is a band set in the service band, and a usage period of the reserved allocated band; and a processing unit, wherein the processing unit includes: Borrowing information for identifying whether or not to allocate a use request band requesting to be set in the first service band to a second service different from the service; When receiving reservation information including a request bandwidth and a use request period of the use request bandwidth, it is determined that the use request bandwidth is allocated within the service bandwidth of the second service using the borrowing information In this case, for the second service, a bandwidth in which the total of the reserved allocated bandwidths of the second service is maximized during the usage period is calculated as a second maximum allocated bandwidth, A step of calculating a second free bandwidth by subtracting the second maximum allocated bandwidth from a service bandwidth of a service, and performing the second free space as a future time comes from a time when the reservation information is received An operation for reducing the size of the band is performed, the second free band at the use end time of the use request period is calculated as a loan band, and the loan band is used as the second service. The reserved allocation band of the first service set in the service band of the first service, the usage request period as the usage period of the reserved allocation band, the reserved allocation band, the usage period of the reserved allocation band, and the second The step of associating and storing the service identification information of the service in the storage unit is performed.

  According to such a configuration, the free bandwidth of the second service can be lent to the first service as in the first aspect, so that the free bandwidth can be shared and used effectively by a plurality of services. In addition, “the second vacancy at the use end time of the use request period of the first service is calculated by performing a calculation to reduce the size of the second vacant bandwidth as the reservation information is received and the future time. The process of calculating the bandwidth and setting it as the lending bandwidth allocates the lending bandwidth in anticipation of an increase in the usage bandwidth of the second service over time. Therefore, it is possible to prevent a large band from being occupied continuously. As a result, the rejection rate of reservation can be reduced. Further, by using the borrowed information, the processing for calculating the vacant bandwidth of the first service can be omitted because the processing for calculating the rented bandwidth can be started immediately after receiving the reservation information.

  In order to solve the above-mentioned problem, the invention according to claim 9 assigns a service band for each service to a band of a path stretched over a network, and the service based on reservation information related to use of the service band. A bandwidth allocation device for calculating a bandwidth to be set in a bandwidth, wherein each service is provided with service identification information for identifying the service, the service bandwidth allocated to the service, and the service bandwidth. A storage unit that associates and stores a reserved allocated band that is a band and a usage period of the reserved allocated band, a requested request band that is requested to be set within the service band of the first service, and the requested request band When the input of the reservation information including the use request period is accepted, the total of the reserved allocation bandwidth of the first service becomes the maximum in the use request period A first maximum allocated bandwidth is calculated by subtracting the first maximum allocated bandwidth from the service bandwidth of the first service, and a first free bandwidth is calculated. The insufficient bandwidth is calculated by subtracting the first vacant bandwidth. If the insufficient bandwidth is positive, the second service different from the first service is used in the usage request period for the second service. A bandwidth in which the total of the reserved allocated bandwidths of the service of the second service is maximized is calculated as a second maximum allocated bandwidth, and the second maximum allocated bandwidth is subtracted from the service bandwidth of the second service to obtain a second Ending the use request period by performing a calculation to reduce the size of the second free band from the time when the reservation information is received to a future time. Said at time The second vacant bandwidth is calculated to be a lent bandwidth, the lent bandwidth is set as the reserved allocated bandwidth of the first service that is set within the service bandwidth of the second service, and the use request period is the reserved allocated bandwidth. And a processing unit that stores the reserved allocation band, the usage period of the reserved allocation band, and the service identification information of the second service in association with each other and stores them in the storage unit.

  According to such a configuration, the free bandwidth of the second service can be lent to the first service as in the first aspect, so that the free bandwidth can be shared and used effectively by a plurality of services. In addition, “the second vacancy at the use end time of the use request period of the first service is calculated by performing a calculation to reduce the size of the second vacant bandwidth as the reservation information is received and the future time. The process of calculating the bandwidth and setting it as the lending bandwidth allocates the lending bandwidth in anticipation of an increase in the usage bandwidth of the second service over time. Therefore, it is possible to prevent a large band from being continuously occupied by the first service. As a result, the rejection rate of reservations for the second service can be reduced.

  According to a tenth aspect of the present invention, there is provided a bandwidth allocation program that causes the bandwidth allocation device that is a computer to execute the bandwidth allocation method according to any one of the first to eighth aspects.

  According to such a bandwidth allocation program, it is possible to cause a general computer to execute the bandwidth allocation method according to any one of claims 1 to 8.

  According to the present invention, it is possible to reduce the reservation rejection rate by lending unused bandwidth out of the bandwidth of one service path to the bandwidth of another service path. It can be used effectively. Also, in the calculation to determine the size of the lent bandwidth, the vacant bandwidth size is reduced from the time when the reservation information is received to the future time, and the vacant bandwidth at the use end time is calculated to be the lent bandwidth. Thus, it is possible to prevent the lent bandwidth from being occupied by an early reservation. As a result, the rejection rate of reservation can be reduced.

  Next, the best mode for carrying out the present invention (hereinafter referred to as “embodiment”) will be described in detail with reference to the drawings as appropriate.

≪Overview of this embodiment≫
First, an outline of the present embodiment will be described with reference to FIG. FIG. 14 is a diagram showing an outline of the present embodiment.
First, FIG. 14 shows the bandwidth of a certain path, the bandwidth allocated by the reservation (rectangle with dots), and the newly reserved bandwidth (rectangle with hatching). The vertical axis represents the bandwidth width allocated to services and reservations, and the horizontal axis represents time.
In FIG. 14, the bandwidth of service A and the bandwidth of service B are set for one path. The bandwidth of service A is assumed to be service bandwidth BWa, and the bandwidth of service B is assumed to be service bandwidth BWb. Here, the service band BWa and the service band BWb are values determined in advance by the network operator, and are set to prevent a large band from being occupied by early reservation. The service bands BWa and BWb are determined in advance by service attributes (for example, video conference, live relay, data transfer, Internet access, etc.).
In this way, by assigning a predetermined maximum allocatable bandwidth (service bandwidths BWa and BWb in FIG. 14) to each service, a large bandwidth is not set as required by the reservation. It is possible to prevent the path from being occupied by the bandwidth.

On the other hand, even if the service band BWa is assigned to the service A, the service band BWa is not always used. That is, the service band BWa may have a free band Wv that is not used. Assume that a reservation requesting a bandwidth larger than the service bandwidth BWb is accepted as a bandwidth reservation by the service B. In that case, lending this free bandwidth Wv to the service B prevents the bandwidth reservation by the service B from being rejected.
On the other hand, after the service A lends the free bandwidth Wv to the service B, it is necessary to prevent the reservation of the service A from being rejected.
Therefore, in order to prevent the reservation of the service A from being rejected, it is necessary to appropriately determine how much of the free bandwidth Wv can be lent to the service B.

  Specifically, as shown in FIG. 14, it is assumed that the first reserved reservation and the second reserved reservation of the service A have already been received at the time t0. Bands assigned to the first reserved and second reserved of service A are a reserved assigned band Wa1 and a reserved assigned band Wa2, respectively. Then, it is assumed that a new bandwidth reservation (a hatched rectangle) by service B is newly received at t0. In the new bandwidth reservation by the service B, it is assumed that the use period is the use start time t1 to the use end time t2, and the use request bandwidth, which is a bandwidth requesting use, exceeds the service bandwidth BWb.

At the current time t0, the service bandwidth BWa of the service A has a free bandwidth Wv from the use start time t1 to the use end time t2. However, free bandwidth Wv = service bandwidth BWa−maximum allocated bandwidth Wat. Here, the maximum allocated bandwidth Wat is a value where the sum of the reserved allocated bandwidth Wa1 and the reserved allocated bandwidth Wa2 is the maximum in the range of the usage period (between times t1 and t2).
Then, a part of the vacant bandwidth Wv of the service A is allocated to the bandwidth reservation by the service B. At this time, how to determine the size of the loan bandwidth Wxb to be lent from the service A to the service B is important. Then, the reservation rejection rate can be reduced by appropriately determining the size of the lending bandwidth Wxb.

<< First Embodiment >>
First, the configuration of a bandwidth allocation system including a bandwidth allocation device according to the first embodiment of the present invention will be described with reference to FIG. FIG. 1 is a diagram showing an example of a configuration of a bandwidth allocation system according to the first embodiment of the present invention.
As shown in FIG. 1, the bandwidth allocation system 1 includes communication devices 11 to 14 and a bandwidth allocation device 10 arranged in a network 15.
For example, when a path setting request is received so as to set a path from the communication apparatus 11 to the communication apparatus 14, the bandwidth allocation apparatus 10 has a function of performing path calculation and determining a path.

Now, it is assumed that the bandwidth allocation device 10 determines a path of a path that passes through the communication devices 12 and 13 with the communication device 11 as a start node and the communication device 14 as an end node. The bandwidth allocation device 10 outputs the determination result as path setting instruction information to the communication device 11 serving as the start node.
Then, the communication device 11 that has received the path setting instruction information first transmits path setting signaling to the communication device 12. Thereafter, the communication apparatuses 11 to 14 exchange information related to the path to establish a path by connecting the links between the communication apparatuses 11 to 14. The communication apparatuses 11 to 14 are connected by a logical path provided by establishing a path directly to each other or by setting a path of a lower layer relatively lower than the network layer. Note that the communication devices 11 to 14 are nodes in a path, and are, for example, an MPLS router of an MPLS (Multi-Protocol Label Switching) network, a router of a packet network, or an optical cross-connect of an optical network.

Next, details of the functions of the bandwidth allocation device 10 will be described with reference to FIG. FIG. 2 is a diagram illustrating functions of the bandwidth allocation device. However, since the gist of the present invention is related to bandwidth allocation, explanation of path route calculation is limited to the necessary level.
As shown in FIG. 2, the bandwidth allocation device 10 includes a processing unit 20, a storage unit 30, an input / output unit 40, and a communication unit 50.

The processing unit 20 includes a bandwidth allocation unit 21, a route calculation unit 22, and a path setting unit 23.
The bandwidth allocation unit 21 calculates a service bandwidth (service bandwidths BWa and Bwb shown in FIG. 14) for each service. The service band is determined with reference to the band allocation information 31 (see FIG. 3) based on the service attribute. The service attribute is a classification of time fluctuations in the amount of traffic flow. The service band may be determined based on statistical information regarding the past used band.
Further, the bandwidth allocation unit 21 cooperates with the route calculation unit 22 to execute a change process of the bandwidth used for the service if necessary in the route calculation. This bandwidth changing process is to lend a free bandwidth of one service to another service. The determination of how much free bandwidth to lend will be described later.

The route calculation unit 22 performs route calculation for the route of the path from the start point node to the end point node of the path. The path of the path is formed by using a link that satisfies a band necessary for transmitting a signal. At that time, there may be a plurality of route candidates having different links used for the path of the path. In that case, the route calculation unit 22 selects one route candidate from the plurality of route candidates and determines it as a path route.
The path setting unit 23 outputs path setting instruction information for setting a path to the node that is the starting point of the path determined by the route calculating unit 22, and sets the path of the path on the network 15. Further, the path setting unit 23 may instruct the node to add or delete a path or change the bandwidth by VCAT (Virtual Concatenation) and LCAS (Link Capacity Adjustment Scheme).

  The processing unit 20 includes a CPU (Central Processing Unit) (not shown) that executes arithmetic processing and the like, and a main memory (not shown) that is used by the CPU for arithmetic processing and the like. Then, the processing unit 20 realizes the functions of the respective units (21 to 23) when the application program is expanded in the main memory and the CPU executes it. The main memory is realized by a RAM (Random Access Memory) or the like.

Next, the storage unit 30 will be described.
The storage unit 30 stores information including band allocation information 31, resource information 32, path information 33, route candidate information 34, path reservation information 35, and reservation condition information 36. The storage unit 30 also stores an application program for realizing the functions of the processing unit 20.

First, the band allocation information 31 will be described with reference to FIG. FIG. 3 is a diagram illustrating an example of band allocation information.
As shown in FIG. 3, the band allocation information 31 stores a service ID and a service band.
The service ID is information for identifying a service. Different service attributes have different time variation patterns of traffic flow. For example, a large band is regularly used for live broadcasting, a small band is regularly used for video conferencing, a large band is intermittently used for data transfer, and the time variation of the band used for the Internet increases. .
Therefore, when receiving a path setting request for a service, the network operator determines a service band for each service attribute in advance with reference to statistical information on past band use.

Next, the resource information 32 (see FIG. 2) will be described with reference to FIG. FIG. 4A is a diagram illustrating an example of link information in the resource information, and FIG. 4B is a diagram illustrating an example of resource reservation information in the resource information.
As shown in FIG. 4, the resource information 32 includes link information 321 and resource reservation information 322.
As shown in FIG. 4A, the link information 321 includes information on links that connect the nodes constituting the network 15. The link information 321 includes at least a link ID, a bandwidth of the link, a node ID of a link end point, a node IF (Interface) _ID, and a link cost. The link cost is a cost (burden) when the node sends a signal to the link. Typical link costs include IGP (Interior Gateway Protocol) costs and TE (Traffic Engineering) metrics. The node ID and node IF_ID are, for example, IP addresses.

As shown in FIG. 4B, the resource reservation information 322 includes, for each link ID, at least information indicating the path ID of the path using the link and the remaining bandwidth of the link in time series.
The resource reservation information 322 further includes, for each link ID, the slot number of the slot of the link. (Slot number), the path ID of the path assigned to this slot, and the remaining bandwidth are stored in association with each other. As shown in FIG. 4B, in the case of the link ID “1”, the remaining bandwidth at the time ta of this link is “XX”. It can be seen that no path is assigned to “1”. In addition, the slot No. A path with a path ID “ee” is assigned to “2-4”, and a slot No. It can be seen that the path with the path ID “bb” is assigned to the slot “5”.
For example, when the bandwidth of one slot is 155 Mbps, it is understood that the bandwidth of 155 Mbps × 3 = 465 Mbps is allocated to the path with the path ID “ee” in the link with the link ID “1”. .

  Further, in FIG. 4B, the information on the time “ta” indicates the current resource reservation information, and indicates the resource reservation information at a future time as the times “tb” and “tc” are reached. Note that the time intervals of the times “ta”, “tb”, and “tc” may be predetermined time intervals. The times “tb” and “tc” may be milestones such as the use start time and use end time related to the use period included in the reservation information when the bandwidth allocation device 10 receives the reservation information. . In this way, by managing the remaining bandwidth in time series, the free bandwidth Wv shown in FIG. 14 can be easily calculated.

Next, the path information 35 (see FIG. 2) will be described with reference to FIG. FIG. 5 is a diagram illustrating an example of path information.
As shown in FIG. 5, the path information 33 stores, for each path, the node ID, the node IF_ID, the via link ID list indicating the path of the path, and the allocated bandwidth for the current path that has been set. ing.

Next, the route candidate information 34 (see FIG. 2) will be described with reference to FIG. FIG. 6 is a diagram illustrating an example of route candidate information.
As shown in FIG. 6, the route candidate information 34 is information obtained by collecting candidates for a path route, and stores a route candidate ID, a via link ID list, and a link cost in association with each other. The transit link ID list is a link forming a path, and is created by the route calculation unit 22 with reference to topology information (not shown) indicating how the node ID and the nodes are connected to each other. Is done. The link cost is calculated by using the link cost for each link ID stored in the link information 321 with respect to the path when the link stored in the via link ID list is connected by the path calculation unit 22. Calculated.
FIG. 6 shows three route candidates. Then, the route calculation unit 22 determines the route with the lowest link cost, that is, the route candidate ID “1”, from the three route candidates as the route of the path to be set.
The route candidate information 34 is not necessarily stored in the storage unit 30 and may be calculated by the route calculation unit 22 every time a route calculation is required.

Next, the reservation condition information 36 (see FIG. 2) will be described with reference to FIG. FIG. 7 is a diagram illustrating an example of reservation condition information.
As shown in FIG. 7, the reservation condition information 36 stores reservation information received when the service is used.
The reservation condition information 36 includes, for example, a reservation ID, a service ID, a usage request bandwidth, and a usage request period. The reservation ID is for identifying the reservation, and is given by the processing unit 20 when the reservation is accepted. The service ID is the same as that shown in the band allocation information 31 (see FIG. 3). For example, in the case of a video conference, the usage request band is easily determined from the specifications of the video conference system. The usage request period may be the usage start time and the usage end time, or may be “one week from the month Δ day” or “24 hours on the first day of every month”.

Next, the path reservation information 35 (see FIG. 2) will be described with reference to FIG. FIG. 8 is a diagram illustrating an example of path reservation information.
As shown in FIG. 8, the path reservation information 35 stores information related to a reserved path.
Specifically, the path reservation information 35 stores a reservation ID, a service ID, a route candidate ID, a use start date / time and a use end date / time, a path ID, and a reservation allocated bandwidth as a use period. The reservation ID is the same as that shown in the reservation condition information 36 (see FIG. 7). The service ID and usage period are acquired by the processing unit 20 from the input reservation information. The route candidate ID and the path ID are calculated by the route calculation unit 22. The reserved allocation bandwidth is calculated by the bandwidth allocation unit 21 and confirmed to be secured by the route calculation unit 22.
Further, the path reservation information 35 is referred to by the path setting unit 23 (see FIG. 2) when the use start date / time is reached, and is used for path setting. In the path reservation information 35, the information related to the corresponding reservation ID is deleted by the path setting unit 23 when the use end date / time is reached.

  In addition to the above, the storage unit 30 stores identification information of nodes installed in the network 15 (see FIG. 1) and topology information indicating how the nodes are connected to each other. . The storage unit 30 is realized by a storage device such as an HDD (Hard Disk Drive).

  The input / output unit 40 (see FIG. 2) is an interface with an input device (not shown) such as a keyboard and a mouse connected to the band allocation device 10 and an output device (not shown) such as a liquid crystal monitor. The input / output unit 40 transmits information input from the input device to the processing unit 20 and outputs the information processed by the processing unit 20 to the output device.

  The communication part 50 (refer FIG. 2) is provided with the communication interface when communicating with the communication apparatuses 11-14. Then, the bandwidth allocation device 10 acquires link and path update information via the communication unit 50 and outputs path setting instruction information to the communication devices 11 to 14.

<< Flow of bandwidth allocation process >>
Next, the flow of the bandwidth allocation process of the bandwidth allocation device 10 (see FIG. 2) will be described with reference to FIG. 9 (see FIGS. 2 to 8 as appropriate). FIG. 9 is a diagram showing the flow of the bandwidth allocation process.
First, the bandwidth allocation unit 21 calculates a service bandwidth for each service (step S91). The service bandwidth is determined based on service attributes, statistical information, past history, and the like. The service band may be a fixed value or may change with time. The calculated service band is stored in the band allocation information 31 (see FIG. 3) for each service ID.

  Next, the bandwidth allocation unit 21 receives the reservation information, and acquires the service ID, the usage request period, and the usage request bandwidth from the received reservation information (step S92).

Next, the route calculation unit 22 calculates the route of the path that matches the reservation information (step S93). Specifically, the route calculation unit 22 is configured by referring to the resource information 32 (see FIG. 4) and topology information (not shown), and a combination of links having a remaining bandwidth equal to or higher than the usage request bandwidth in the usage request period. Calculate the path. For the route calculation, dijkstra algorithm, k-shortest algorithm or the like is used.
The route calculation unit 22 refers to the resource information 32 for the link combination, calculates the link cost corresponding to the route, and stores the link cost in the route candidate information 34 (see FIG. 6).

  Next, the route calculation unit 22 determines whether or not the route calculated by the route calculation in Step S93 is a route satisfying the reservation information (Step S94). If the route satisfies the reservation information (Yes in step S94), the process proceeds to step S95. In step S <b> 95, the route calculation unit 22 determines a path candidate having the lowest link cost among the path candidates stored in the route candidate information 34 as a path to be set in the network 15. Then, the path setting unit 23 performs path setting based on the path information determined by the route calculation unit 22.

  If the route does not satisfy the reservation information (No in step S94), the process proceeds to step S96. In step S96, it is determined whether or not there is a free band that satisfies the reservation information in another service. Specifically, the bandwidth allocating unit 21 calculates, for each service, a lent bandwidth that can be lent out of the free bandwidth allocated to other services on the link of the route that is determined not to satisfy the reservation information in step S94. To do. Then, the bandwidth allocation unit 21 determines whether or not the total loan bandwidth satisfies the reservation information.

  Next, when there is no free bandwidth that satisfies the reservation information in another service (No in step S96), the processing unit 20 ends the process. That is, this reservation is rejected. However, if the requested bandwidth is not satisfied, but a certain amount of bandwidth can be secured, the fact is notified to the user, and if the user's consent is obtained, the reservation information is relaxed and the path is set. Also good.

  In step S96, if there is a free band that satisfies the reservation information in another service (Yes in step S96), the band allocation unit 21 lends a loan band that satisfies the reservation information (step S97). Then, the process returns to step S93, and the route calculation unit 22 performs path route calculation using the lending bandwidth.

≪Lending bandwidth calculation process≫
Here, an outline of the lending bandwidth calculation process in step S97 will be described with reference to FIG. FIG. 10 is a diagram showing an outline of the lending bandwidth calculation process.
FIG. 10 shows the bandwidth allocation status at present t0. At present t0, service band BWa is allocated to service A, and service band BWb is allocated to service B. The service A has already received the first reserved reservation and the second reserved reservation, and reserved allocation bands Wa1 and Wa2 are allocated to the respective reservations. Then, it is assumed that reservation information using the service B is newly accepted at the current t0. The bandwidth reservation status by the service B is “new reservation for service B” indicated by hatching. That is, FIG. 10 shows a case where there is no reserved reservation in service B, that is, there is no reserved allocated bandwidth during the usage period t1 to t2, for the sake of simplicity.

It is assumed that reservation information for using the service B is newly received at the present t0. The reservation information includes a service ID, a use request bandwidth, and a use request period of the use request bandwidth.
First, the free bandwidth of service B itself is calculated. In FIG. 10, since the maximum allocated bandwidth of service B is 0, the free bandwidth of service B itself is service bandwidth BWb. However, if there is a reserved allocation band for service B during the usage period t1 to t2, the service band BWb to the maximum allocated band for service B (that is, a band in which the total of the reserved allocation bands is maximum) Is subtracted to calculate the free bandwidth.
Next, the insufficient bandwidth is calculated by subtracting the free bandwidth of service B from the usage request bandwidth. As a result, if the insufficient bandwidth is positive, the free bandwidth of service A is lent to service B. Then, the free bandwidth Wv is calculated for the service A this time.
Next, as shown in FIG. 10, when the time direction is the X axis and the band direction is the Y axis, the point (X, Y) = (t0, Wv) and the point (X, Y) = (t3, 0 ), That is, a free bandwidth allocation function X (t) 100 is applied, and X (t2) is defined as a lending bandwidth Wxb.
In other words, an operation for decreasing the size of the free bandwidth Wv from the time t0 when the reservation information is received to the future time t3 is performed, and the size of the free bandwidth Wv at the use end time t2 is calculated as the lending bandwidth Wxb. To do.

Note that if the lent bandwidth Wxb is larger than the insufficient bandwidth of the usage request bandwidth (calculated by subtracting the vacant bandwidth of the service B from the usage requested bandwidth), the entire lent bandwidth Wxb may be lent to the service B or insufficient. You may lend only the bandwidth. In addition, an intermediate band between them may be lent.
Further, FIG. 10 shows a case where the free bandwidth allocation function X (t) 100 is a straight line (decrease rate is constant), but is not limited to this, and as the future time comes from the time t0 when the reservation is accepted. As long as the function reduces the size of the free bandwidth Wv, it may be a logarithm, exponent, and quadratic function with time as a variable, or a combination thereof.
Further, when the service A is provided with a threshold value of a bandwidth that is not lent to other services, the available bandwidth may be calculated in advance by the amount corresponding to the threshold value.

≪Process when renting free bandwidth from multiple services≫
Next, in step S96 to step S97 (see FIG. 9), the details of the processing flow when renting a free band from a plurality of services will be described with reference to FIG. 11 (see FIGS. 2 and 10 as appropriate). FIG. 11 is a diagram showing the flow of processing when renting a free band from a plurality of services.
First, the bandwidth allocation unit 21 (see FIG. 2) calculates the free bandwidth Wv for each service (step S111). The calculation of the free bandwidth Wv is as described with reference to FIG.
Next, the lending bandwidth Wxb is calculated for each service using the free bandwidth allocation function X (t) 100 (step S112).
Then, for the lending bandwidth Wxb calculated for each service, the order of lending bandwidth selection for each service is determined based on the selection criteria described later (step S113).

  Next, it is determined whether there is an unselected loan band (step S114). If there is an unselected loan band in step S114 (Yes in step S114), the process proceeds to step S115. If there is no unselected loan band (No in step S114), the process proceeds to step S117.

In step S115, the initial value of the total when adding the lending bandwidth is set to 0, one lending bandwidth Wxb is selected according to the selection order, and the lending bandwidth Wxb is added to the total up to the previous time. Then, it is determined whether or not the total of the lending bandwidth Wxb exceeds the shortage of the usage request bandwidth (step S116). If the total of the lent bandwidth Wxb exceeds the shortage of the usage request bandwidth (Yes in step S116), the process proceeds to step S117. If the total of the lent bandwidth Wxb does not exceed the shortage of the usage request bandwidth (No in step S116), the process returns to step S114.
In step S117, the lending bandwidth Wxb is lent out.

  In addition, when the total of the loan bandwidth Wxb calculated as a loan amount is larger than the use request bandwidth, all of the summed individual loan bandwidths Wxb may be loaned to other services or changed to the use request bandwidth only. Then you can lend it. In addition, an intermediate band between them may be lent.

≪About selection criteria≫
Next, the selection criteria described in step S113 and the flow of the processing will be described below.
(1) Lending from a service having a large free bandwidth If the free bandwidth allocation function X (t) 100 shown in the present embodiment is used, the size of the leased bandwidth is proportional to the size of the free bandwidth. Accordingly, in step S113 shown in FIG. 11, when the lending bandwidth selection criterion is the order of increasing available bandwidth, the lending bandwidth is calculated in the order of increasing available bandwidth, as shown in steps S115 to S117. The calculated lending bandwidth is added, and when the total sum exceeds the usage request bandwidth, the added individual lending bandwidth is lent.
Note that the comparison of the size of the lent bandwidth is executed by the bandwidth allocation unit 21 (see FIG. 2).

(2) Lending from a service with a small bandwidth usage rate The bandwidth usage rate is calculated by dividing the reserved allocated bandwidth in a predetermined period before the current t0 by the service bandwidth. In step S113 shown in FIG. 11, when the free band selection criterion is the order of decreasing band usage rate, as shown in steps S115 to S117, the lending bandwidth is calculated in ascending order of band usage rate, The calculated lending bandwidth is added, and when the total sum exceeds the usage request bandwidth, the added individual bandwidth is lent.
Note that the bandwidth usage rate is calculated by the bandwidth allocation unit 21 (see FIG. 2).

(3) Lending from a service with a small average of the reserved allocated bandwidth The average of the reserved allocated bandwidth is calculated as the time average of the reserved allocated bandwidth in a predetermined period before the current t0. In step S113 shown in FIG. 11, when the free band selection criterion is the order in which the average of the reserved allocation bands is small, as shown in steps S115 to S117, the lending bands are set in the order of the average of the reserved allocation bands. The calculated lending bandwidth is added, and when the total sum exceeds the use request bandwidth, the added individual bandwidth is lent.
Note that the average comparison of the reserved allocation bands is executed by the band allocation unit 21 (see FIG. 2).
In addition, lending free bandwidths in ascending order of reserved allocation bandwidth is highly likely to have large free bandwidths and can suppress rejection of reservations.

(4) Lending a lent bandwidth that is equal to or greater than the requested bandwidth and a bandwidth that is closest to the requested bandwidth in step S113 shown in FIG. When setting the loan bandwidth closest to the bandwidth, calculate the loan bandwidth for all available bandwidths, compare the calculated loan bandwidth with the requested bandwidth, and select the bandwidth that is equal to or greater than the requested bandwidth and closest to the requested bandwidth To do.
The comparison between the size of the lent bandwidth and the size of the usage request bandwidth is executed by the bandwidth allocation unit 21 (see FIG. 2).

(5) Lending from a service with a small free band distribution when the service is used In step S113 shown in FIG. 11, when the free band selection criterion is the order of small free band distribution when using the service As shown in steps S115 to S117, the loan bandwidths are calculated in ascending order of variance within the predetermined period of the free bandwidth when the service is used, and the calculated loan bandwidths are added. When the value exceeds the value, the added individual loan bandwidth is lent.
Note that the calculation for the distribution of the free bandwidth is executed by the bandwidth allocation unit 21 (see FIG. 2).
In addition, lending free bandwidths in ascending order of dispersion of free bandwidths is highly likely that the free bandwidths are stable (constant), and rejection of reservations can be suppressed.

≪Modification: Adjustment of lending bandwidth size≫
Next, the lending bandwidth size adjustment process calculated in step S117 shown in FIG. 11 will be described with reference to FIG. FIG. 12 is a diagram illustrating a process for adjusting the size of a lending bandwidth.
FIG. 12 shows a case where the maximum allocated bandwidth Wat for the reservation of the service A does not change between times t0 and t1 as a simple case.
It is assumed that the lending bandwidths Wxb0, Wxb01, and Wxb1 are values calculated at times t0, t01, and t1, respectively.
In FIG. 12, the lending bandwidth Wxb is calculated as Wxb1>Wxb01> Wxb0. In other words, a reservation whose use end time t2 is closer to the current t0 is assigned a larger lending bandwidth Wxb.
The bandwidth allocation unit 21 (see FIG. 2) determines the largest loan bandwidth Wxb among the loan bandwidths Wxb calculated as described above as the loan bandwidth Wxb to be lent to the service B.

  According to the bandwidth allocating device 10 in the first embodiment, a vacant bandwidth of a service can be lent to another service, so that the vacant bandwidth can be shared and used effectively by a plurality of services. In addition, the free bandwidth allocation function X (t) 100 allocates a rental bandwidth in anticipation of an increase in the usage bandwidth of the second service over time. Therefore, it is possible to prevent a large band from being occupied continuously. As a result, the rejection rate of reservation can be reduced.

<< Second Embodiment >>
The second embodiment differs from the first embodiment in the contents of the reservation information that is accepted, and accordingly, the calculation processing of the lending bandwidth (step S96 shown in FIG. 9) is different. However, other processes are the same in the second embodiment and the first embodiment. Therefore, the configuration diagram of the bandwidth allocation device 10 of the second embodiment is the same as that of FIG. In addition, the reservation condition information 36 in the first embodiment is expressed as “reservation condition information 36a” in the second embodiment.

FIG. 13 is a diagram showing reservation condition information in the second embodiment.
FIG. 13 differs from FIG. 7 in that a borrowing information column is newly provided. The service ID of the reservation ID “Bu1” is “A”. This borrowing information indicates that the reservation ID “Bu1”, which is supposed to use the band of the service B, is assigned the lending band from the service with the service ID “A” from the beginning. Therefore, for example, if the flag in the borrowing information column is “1”, it indicates that the lent bandwidth is allocated from a different service bandwidth. This makes it possible to omit the process of calculating the free bandwidth of service B.
Since the other processes are the same as those described in the first embodiment, description thereof is omitted.

  According to the bandwidth allocation device 10 in the second embodiment, there are the same effects as in the first embodiment.

  As mentioned above, although each embodiment was described, this invention is not limited to these, It can implement in the range which does not change the meaning.

  Further, in each embodiment of the present invention, the processing of each part of the bandwidth allocation device 10 (see FIG. 2) has been described, but these processing are realized by a program installed when the bandwidth allocation device 10 is realized by a computer. May be. This program can be provided via a communication line, or can be written on a recording medium such as a CD-ROM and distributed.

It is a figure which shows an example of a structure of the band allocation system which concerns on 1st Embodiment of this invention. It is a figure which shows the function of a bandwidth allocation apparatus. It is a figure which shows an example of band allocation information. (A) is a figure which shows an example of link information among resource information, (b) is a figure which shows an example of resource reservation information among resource information. It is a figure which shows an example of path information. It is a figure which shows an example of route candidate information. It is a figure which shows an example of reservation condition information. It is a figure which shows an example of path reservation information. It is a figure which shows the flow of a band allocation process. It is a figure which shows the outline | summary of a calculation process of a lending band. It is a figure which shows the flow of a process in the case of lending an empty band from several services. It is a figure which shows the adjustment process of the magnitude | size of a lending band. It is a figure which shows an example of the reservation condition information in 2nd Embodiment. It is a figure which shows the outline | summary of this embodiment.

Explanation of symbols

DESCRIPTION OF SYMBOLS 1 Bandwidth allocation system 10 Bandwidth allocation apparatus 11-14 Communication apparatus 20 Processing part 21 Bandwidth allocation part 22 Path | route calculation part 23 Path setting part 30 Memory | storage part 31 Bandwidth allocation information 32 Resource information 33 Path information 34 Path candidate information 35 Path reservation information 36 36a Reservation condition information 100 Free bandwidth allocation function BWa, Bwb Service bandwidth Wa1, Wa2, Wb Reserved allocation bandwidth Wat Maximum allocated bandwidth Wv Free bandwidth Wxb Lending bandwidth

Claims (10)

Bandwidth allocation used in a bandwidth allocation apparatus that allocates a service bandwidth for each service to a bandwidth of a path stretched over a network and calculates a bandwidth to be set in the service bandwidth based on reservation information related to use of the service bandwidth A method,
The bandwidth allocation device is
For each service, service identification information for identifying the service, the service band allocated to the service, a reserved allocated band that is a band set for the service band, and a usage period of the reserved allocated band, A storage unit and a processing unit for storing
The processing unit is
When receiving an input of reservation information including a use request band requesting to be set within the service band of the first service and a use request period of the use request band,
A bandwidth in which the total of the reserved allocated bandwidths of the first service is maximized during the usage request period is calculated as a first maximum allocated bandwidth, and the first maximum allocated bandwidth is calculated from the service bandwidth of the first service. Subtracting the completed bandwidth to calculate a first free bandwidth, subtracting the first free bandwidth from the usage request bandwidth to calculate a shortage bandwidth,
If the insufficient bandwidth is positive,
For a second service different from the first service, a bandwidth that maximizes the total of the reserved allocated bandwidth of the second service in the usage request period is calculated as a second maximum allocated bandwidth, Performing a step of calculating a second free bandwidth by subtracting the second maximum allocated bandwidth from a service bandwidth of the second service;
The second free band at the use end time of the use request period is calculated by performing an operation for reducing the size of the second free band as the time from the time when the reservation information is received to the future time. The reserved allocation bandwidth of the first service that sets the leased bandwidth within the service bandwidth of the second service, the usage request period as the usage period of the reserved allocation bandwidth, Executing a step of associating a bandwidth, a use period of the reserved allocation bandwidth, and service identification information of the second service in the storage unit;
A bandwidth allocation method characterized by the above. The calculation for reducing the size of the second vacant band as the time from the time when the reservation information is received to the future time is an operation whose reduction rate is constant,
The band allocation method according to claim 1, wherein: The operation of reducing the size of the second free bandwidth as the future time from the time when the reservation information is received is a logarithm, exponent, And any one of the quadratic functions or a combination thereof,
The band allocation method according to claim 1, wherein: The processing unit is
In the pre-use period from the time when the reservation information is received to the use start time of the use period, the lending bandwidth is calculated every predetermined time,
Executing the step of setting the largest value among the lending bandwidths calculated during the period before the start of use as the reserved allocation bandwidth of the first service;
The band allocation method according to any one of claims 1 to 3, wherein: When the processing unit determines that the lending bandwidth is larger than the insufficient bandwidth,
Executing either the insufficient bandwidth or the lending bandwidth as the reserved allocated bandwidth of the first service;
The band allocation method according to claim 4, wherein: The second service is plural,
The processing unit is
For each service, calculate the lending bandwidth,
Among the plurality of loan bands calculated for each service, the loan bands are added in the order of services with the largest loan bands, and when the sum exceeds the shortage band, the added individual bands Performing the step of setting the lending bandwidth as the reserved allocated bandwidth of the first service;
The bandwidth allocation method according to any one of claims 1 to 5, wherein: The second service is plural,
The processing unit is
For each of the plurality of services, calculate the bandwidth usage rate by summing the reserved allocation bandwidth and dividing the sum by the service bandwidth;
The lending bandwidth is calculated and added in the order of services with the smallest bandwidth usage rate, and when the sum exceeds the insufficient bandwidth, the added lending bandwidth is used as the reserved allocated bandwidth of the first service. Performing the steps
The bandwidth allocation method according to any one of claims 1 to 5, wherein: Bandwidth allocation used in a bandwidth allocation apparatus that allocates a service bandwidth for each service to a bandwidth of a path stretched over a network and calculates a bandwidth to be set in the service bandwidth based on reservation information related to use of the service bandwidth A method,
The bandwidth allocation device is
For each service, service identification information for identifying the service, the service band allocated to the service, a reserved allocated band that is a band set for the service band, and a usage period of the reserved allocated band, A storage unit and a processing unit for storing
The processing unit is
Borrowing information for identifying whether or not to allocate a use request band requesting to be set in the first service band to a second service different from the first service, the use request band, and When the reservation information including the usage request period of the usage request bandwidth is received, when it is determined that the usage request bandwidth is allocated within the service bandwidth of the second service using the borrowing information,
For the second service, a bandwidth in which the total of the reserved allocated bandwidths of the second service is maximized during the usage period is calculated as a second maximum allocated bandwidth, and the service bandwidth of the second service is calculated. Performing a step of calculating a second free bandwidth by subtracting the second maximum allocated bandwidth;
The second free band at the use end time of the use request period is calculated by performing an operation for reducing the size of the second free band as the time from the time when the reservation information is received to the future time. The reserved allocation bandwidth of the first service that sets the leased bandwidth within the service bandwidth of the second service, the usage request period as the usage period of the reserved allocation bandwidth, Executing a step of associating a bandwidth, a use period of the reserved allocation bandwidth, and service identification information of the second service in the storage unit;
A bandwidth allocation method characterized by the above. A bandwidth allocation device that allocates a service bandwidth for each service to a bandwidth of a path stretched over a network, and calculates a bandwidth to be set in the service bandwidth based on reservation information related to use of the service bandwidth,
For each service, service identification information for identifying the service, the service band allocated to the service, a reserved allocated band that is a band set for the service band, and a usage period of the reserved allocated band, A storage unit for storing
When receiving an input of reservation information including a use request band requesting to be set within the service band of the first service and a use request period of the use request band,
A bandwidth in which the total of the reserved allocated bandwidths of the first service is maximized during the usage request period is calculated as a first maximum allocated bandwidth, and the first maximum allocated bandwidth is calculated from the service bandwidth of the first service. Subtracting the completed bandwidth to calculate a first free bandwidth, subtracting the first free bandwidth from the usage request bandwidth to calculate a shortage bandwidth,
If the insufficient bandwidth is positive,
For a second service different from the first service, a bandwidth that maximizes the total of the reserved allocated bandwidth of the second service in the usage request period is calculated as a second maximum allocated bandwidth, Performing a step of calculating a second free bandwidth by subtracting the second maximum allocated bandwidth from a service bandwidth of the second service;
The second free band at the use end time of the use request period is calculated by performing an operation for reducing the size of the second free band as the time from the time when the reservation information is received to the future time. The reserved allocation bandwidth of the first service that sets the leased bandwidth within the service bandwidth of the second service, the usage request period as the usage period of the reserved allocation bandwidth, A processing unit that associates a bandwidth, a usage period of the reserved allocated bandwidth, and service identification information of the second service, and stores the associated information in the storage unit;
A bandwidth allocating device comprising:   9. A bandwidth allocation program that causes the bandwidth allocation device that is a computer to execute the bandwidth allocation method according to claim 1.

Images