Network resource provisioning method for bandwidth guarantee per flow

• US 20070118636A1
• Filed: 11/02/2006
• Published: 05/24/2007
• Est. Priority Date: 11/21/2005
• Status: Active Grant

• Current Assignee: Electronics and Telecommunications Research Institute
• Original Assignee: Electronics and Telecommunications Research Institute
• Inventors: Jung, Hae, Kim, Tae II, Yang, Mi
• Granted Patent: US 7,680,036 B2
• Time in Patent Office: Days
• US Class Current: 709/223
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/12 Shortest path evaluation
• CPC Class Codes: H04L 45/30 Routing of multiclass traffic
• CPC Class Codes: H04L 45/302 Route determination based on requested QoS
• CPC Class Codes: H04L 47/2408 for supporting different services, e.g. a differentiated services [DiffServ] type of service
• CPC Class Codes: H04L 47/70 Admission control; Resource allocation
• CPC Class Codes: H04L 47/765 triggered by the end-points
• CPC Class Codes: H04L 47/781 Centralised allocation of resources
• CPC Class Codes: H04L 47/805 QOS or priority aware
• CPC Class Codes: H04L 47/826 Involving periods of time

Abstract

Provided is a network resource provisioning method for bandwidth guarantee per flow in a differentiated service Internet in which bandwidth needed for each flow is individually requested. The method comprises setting an optimum path between a source node and a destination node based on a request for traffic for a specific period of time; performing static provisioning in which bandwidth is allocated to the optimum path according to a service class thereof; determining whether all of the bandwidth allocated to the optimum path by performing static provisioning are used up, and accepting connection admission according to the determination result; and when connection admission is not accepted, performing dynamic provisioning in which additional bandwidth is allocated to the optimum path based on a request for traffic from a new incoming flow. Accordingly, it is possible to efficiently provide a quality-guaranteed service by accepting a request for bandwidth per flow.

Claims

1. A method of provisioning network resources in a differentiated service Internet in which necessary bandwidth is requested in units of flows for bandwidth guarantee per flow, comprising:

(a) setting an optimum path between a source node and a destination node based on a request for traffic for a specific period of time;

(b) performing static provisioning in which bandwidth is allocated to each service class of the optimum path;

(c) determining whether connection admission is to be performed by determining whether all of the statically provisioned bandwidth allocated to the optimum path is being used; and

(d) if it is determined in (c) that connection admission is not to be performed, performing dynamic provisioning in which additional bandwidth is allocated to the optimum path based on a request for traffic by a newly incoming flow.

2. The method of claim 1, wherein the setting the optimum path comprises computing a value which satisfies:

the amount of traffic input to and output from each of nodes, except the source node and the destination node, is the same;

the total bandwidth requested by all paths that include the same link is not greater than an overall link capacity;

a case where one of the flows is divided into sub flows and a plurality of paths are used is excluded; and

overall link utilization in the differentiated service Internet is maximized.

3. The method of claim 2, wherein the setting the optimum path comprises computing a value which satisfies:

Minimize L_max  

 

(1)

Condition (1) must satisfy the following conditions;

$\underset{j}{\sum <br><br>}<br><br>X_{\mathrm{ij}}^{\mathrm{sd}}-\underset{j}{\sum <br><br>}<br><br>X_{\mathrm{ji}}^{\mathrm{sd}}=\left(\begin{array}{ccc}1,& i=s,& \forall <br><br>i,s,d\\ 0,& i\ne <br><br>s,& \forall <br><br>i,s,d\\ -1,& i=d,& \forall <br><br>i,s,d\end{array}\right)$

wherein i denotes a node, j denotes a link, s denotes a source node, d denotes a destination node, λ

_sd denotes bandwidth requested between the source node s and the destination node d, L_max denotes the rate of maximum overall link utilization in the differentiated service Internet, C_ij denotes the capacity of a link(i,j), and X_ij^sd denotes a ratio (%) of bandwidth allocated to the link(i,j) to bandwidth requested between the source node s and the destination node d.

4. The method of claim 1, wherein (b) comprises:

(b1) computing bandwidth to be allocated to respective nodes in the optimum path according to a service class of the optimum path;

(b2) selecting a minimum bandwidth from among the bandwidths; and

(b3) allocating a predetermined percentage of the minimum bandwidth as an initial bandwidth to the service classes of the optimum path.

5. The method of claim 4, wherein the predetermined percentage is 50% of the minimum bandwidth.

6. The method of claim 1, wherein (c) comprises:

(c1) receiving a new flow which requests a bandwidth c through the source node;

(c2) selecting a path using the destination node and the service classes;

(c3) comparing extra bandwidth available to the selected path with the requested bandwidth c, and determining whether the extra bandwidth is sufficient to accept connection of the new flow; and

(c4) if it is determined in (c3) that the connection of the new flow is acceptable, updating the extra bandwidth of the selected path to be equal to the extra bandwidth-the requested bandwidth c, and accepting the connection of the new flow.

7. The method of claim 6, wherein (d) comprises:

(d1) if it is determined in (c3) that the connection of the new flow is not acceptable, estimating a new bandwidth M′

to be requested for the selected path, and requesting a bandwidth broker to allocate the estimated bandwidth M′

to the selected path;

(d2) detecting a minimum bandwidth among extra bandwidth at all links included in the selected path, and comparing the detected minimum bandwidth with the estimated bandwidth M′

to determine whether the detected minimum bandwidth is greater than the estimated bandwidth M′

;

(d3) when it is determined that the minimum bandwidth detected in (d2) is greater than the estimated bandwidth M′

, allocating the estimated bandwidth M′

to the selected path using the bandwidth broker; and

(d4) computing the sum of the existing extra bandwidth and the estimated bandwidth M′

, and updating the extra bandwidth for the selected path as the sum minus the requested bandwidth c using the source node.

8. The method of claim 7, further comprising:

(d3′

) when the minimum bandwidth detected in (d2) is less than the estimated bandwidth M′ and

greater than the requested bandwidth c, allocating the requested bandwidth c to the selected path using the bandwidth broker; and

(d4′

) computing the sum of the existing extra bandwidth and the requested bandwidth c, and updating the extra bandwidth of the selected path as the sum minus the requested bandwidth c.

9. The method of claim 7, further comprising (d3″

), when it is determined that the minimum bandwidth detected in (d2) is less than the requested bandwidth c, rejecting a request for the connection of the new flow using the bandwidth broker.

10. The method of claim 7, wherein the estimated bandwidth M′

is greater than the requested bandwidth c.

11. The method of claim 7, wherein the estimated bandwidth M′

is determined such that a connection blocking probability and communication to be established with the bandwidth broker are minimized.