Method and apparatus for controlling traffic flow rate

BACKGROUND OF THE INVENTION

P-0001[0001] The present invention relates generally to a technology for controlling a traffic flow rate in a network. More particularly, the present invention relates to a technology for controlling a traffic flow rate of transferred data by considering a service level of the transferred data.

P-0002[0002] In particular control of transfers of data through a network, the control is executed in dependence on an identified class of the data. A class of the transferred data is normally identified by a first router at an entrance of the network subjected to traffic management. An identifier is embedded in a ToS field (Refer to RFC 1493) of an IP header of the transmitted data. That is to say, in the network subjected to traffic management, the class of the transmitted data is identified on the basis of the embedded identifier. As a typical technique of executing band control in a network subjected to traffic management on the basis of such identifiers, there is known a model called DiffServ (Refer to RFCs 2474, 2475, 2597 and 2598). In this case, in the network subjected to traffic management, each transmitted data's attributes such as an IP address and an application are not taken into consideration at all in determining of the class of the data. In other words, the class of the transferred data is identified by using only a value embedded in the ToS field in order to execute transfer control suitable for the class.

P-0003[0003] A system utilizing such a technology is disclosed in Japanese Patent Laid-open No. 2001-244979. In this system, classes are used for identifying categories of rendered services and do not show priority levels of data transfers.

P-0004[0004] An identified class of a data transfer is defined as a priority level of the data transfer. In order to deliver data in such a way that, the higher the priority level, the sooner the data is delivered, routers in a network subjected to traffic management generally each adopt a priority-based queuing technique whereby a packet having a high priority level is transmitted, taking precedence of a packet having a low priority level. As a system for managing traffic in a network, a technology is disclosed in documents such as Japanese Patent Laid-open No. 11-136237.

P-0005[0005] In accordance with the priority-based queuing technique adopted as the prior art in a network subjected to traffic management, a priority level of data transmitted by way of the network is determined on the basis of an identifier included in the data. It is needless to say that data with a high priority level is transmitted, taking precedence of other data so that transmission of data with a low priority level is inadvertently deferred. With such a technique, in a state of heavy traffic of pieces of data with high priority levels, data with a low priority level unavoidably enters a wait state in a router, being not transmitted for any length of time. While a technique of delaying transmission of data with a low priority level is a proper method, a big effect of the priority level on the arrival time of data is inefficiency.

P-0006[0006] In order to solve the problem described above, there have been proposed control methods such as the WFQ (Weighted Fair Queuing) technique and the WRR (Weighted Round Robin) technique. In accordance with the WFQ and WRR techniques, a router defines a send-out rate in advance for each class required for controlling data transfers. Data pertaining to a class is transmitted at a send-out rate defined for the class constantly on a priority basis. In this case, if data has an amount exceeding a send-out rate defined for the class to which the data pertains, the excess portion of the data is diverted into another class with a defined send-out rate thereof greater than the amount of other data pertaining to the other class. When an excess portion of specific data is diverted into another class to which other data pertains, however, the priority level of the specific data and the priority level of the other data are not taken into consideration. That is to say, an excess portion of specific data with a high priority level may be inadvertently diverted into another class to which other data with a low priority level pertains. As a result, send-out rates assigned to each router inadvertently have a big effect on the operation.

SUMMARY OF THE INVENTION

P-0007[0007] With the prior art, however, a send-out rate defined for each class depends on the sense of a person in charge of network management and the number of users at each service level to a certain degree. That is to say, setting of an optimum send-out rate is not absolutely assured. In addition, since the amount of traffic flowing through a router varies from router to router, it is extremely difficult to identify a send-out rate for each router. In addition, the amount of network traffic changes constantly so that, even if parameters appropriate at a particular time for all routers are set, the values of the parameters may not always be proper for the routers at other times. Furthermore, it is very hard for a person in charge of network management to grasp routes in a network subjected to traffic management. Even if all routes can be grasped, it is impossible to keep up with an abnormality state in which a flow of data transmitted through a route is detoured in the event of a failure occurring in a router on the route.

P-0008[0008] It is therefore an object of the present invention to provide a technology for dynamically changing a flow rate in accordance with traffic in a network without increasing a load borne by a person in charge of network management.

P-0009[0009] The present invention provides a technology for contoling a flow rate of traffic through a communication line in a network including a plurality of routing controllers and the communication line connecting the routing controllers. The technology provided by the present invention is characterized in that the technology is applied to control comprising the steps of: sampling traffic flow rates for each transmission direction of the communication line and for each identifier included in transmitted data; aggregating the sampled traffic flow rates to find an average value of the sampled traffic flow rates; finding a send-out rate by multiplying the average value by a weight according to the identifier to be used as a flow-rate policy; and transmitting the send-out rate to one of the routing controllers to set the send-out rate as the flow-rate policy.

P-0010[0010] In addition, the present invention also provides a traffic flow-rate control technology to be adopted by a system, which has a management means for managing traffic flow rates in a network, for the purpose of controlling a traffic flow rate of transmitted data flowing through a communication line in the network comprising a plurality of transmission means, the communication line connecting the transmission means to each other and a measurement means for measuring the traffic flow rate. The traffic flow-rate control technology provided by the present invention is characterized in that the technology is applied to control comprising the steps of: driving the measurement means to measure a traffic flow rate of data transmitted through the communication line for each transmission direction of the communication line and for each identifier included in the transmitted data and transmit the measured traffic flow rates to the management means in accordance with a request received from the management means; and driving each of the transmission means to receive a send-out rate as a flow-rate policy set for each transmission direction of the communication line and for each identifier included in the transmitted data from the management means and control the flow rate of the transmitted data for each identifier included in the transmitted data in accordance with the send-out rate received from the management means.

BRIEF DESCRIPTION OF THE DRAWINGS

P-0011[0011]FIG. 1 is a diagram showing a system configuration of an embodiment;

P-0012[0012]FIG. 2 is a diagram showing an exemplified data format of resource information <b>201</b>;

P-0013[0013]FIG. 3 is a diagram showing exemplified resources identified by resource IDs;

P-0014[0014]FIG. 4 is a diagram showing an exemplified data format of a service level definition <b>401</b>;

P-0015[0015]FIG. 5 is a diagram showing exemplified identifiers set in transmitted data;

P-0016[0016]FIG. 6 is a diagram showing an exemplified data format of an initial flow rate policy <b>601</b>;

P-0017[0017]FIG. 7 is a diagram showing an exemplified structure of flow rate policy data;

P-0018[0018]FIG. 8 is an explanatory diagram showing flows of data <b>501</b> transmitted in a router <b>102</b>;

P-0019[0019]FIG. 9 shows a flowchart representing a procedure of a process carried out by a flow-rate acquisition unit <b>111</b> employed in the embodiment;

P-0020[0020]FIG. 10 is a diagram showing exemplified flow rates;

P-0021[0021]FIG. 11 shows a flowchart representing a procedure of a process carried out by a flow-rate aggregation unit <b>110</b> employed in the embodiment;

P-0022[0022]FIG. 12 is a diagram showing an example of aggregated flow rate data;

P-0023[0023]FIG. 13 is a diagram showing an example of a graph representing changes in flow rate with the lapse of time;

P-0024[0024]FIG. 14 shows a flowchart representing a procedure of a process carried out by a flow-rate-policy control unit <b>107</b> employed in the embodiment; and

P-0025[0025]FIG. 15 is a diagram showing exemplified flow-rate policy data.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS

P-0026[0026] Preferred embodiments of the present invention will be described taking an example of Diffserv model into account with reference to the accompanying drawings below.

P-0027[0027]FIG. 1 is a diagram showing a system configuration of an embodiment. An area enclosed by a dashed line in the figure is a network subjected to traffic management. As shown in the figure, the network includes routers <b>102</b> and meters <b>104</b>. A router <b>102</b>-<b>1</b> is an edge router, which is a router connected to a terminal <b>105</b> utilized by an end user. On the other hand, a router <b>102</b>-<b>2</b> is a core router, which is a router not connected to the terminal <b>105</b>. As shown in the figure, the routers <b>102</b> and the meters <b>104</b> are connected to each other by communication lines. In addition, one of the routers <b>102</b> is connected to a management server <b>101</b> by communication lines. The management server <b>101</b> is a computer connected to the network subjected to traffic management. The management server <b>101</b> collects traffic information from the meters <b>104</b> in the range of traffic management in order to set a flow-rate policy of traffic in each of the routers <b>102</b> in the range of traffic management. The management server <b>101</b> has an initialization data <b>112</b>, an acquired-flow-rate data <b>113</b> and an all-flow-rate data <b>114</b> stored in storage devices of the management server <b>101</b>. In addition, the management server <b>101</b> includes a initialization unit <b>106</b>, a flow-rate-policy control unit <b>107</b>, a flow-rate-policy-setting unit <b>108</b>, a flow-rate-data display unit <b>109</b>, a flow-rate aggregation unit <b>110</b> and a flow-rate acquisition unit <b>111</b> as configuration components implemented by software and/or hardware. Processing procedures of these configuration components are implemented by execution of programs by the management server <b>101</b> as will be described later in detail.

P-0028[0028] The router <b>102</b> has the flow-rate-policy data <b>120</b> stored in the storage device employed in the router <b>102</b>. The router <b>102</b> also has a data reception unit <b>115</b>, an identification unit <b>116</b>, a controller <b>117</b>, a data transmission unit <b>118</b> and a control-policy-setting unit <b>119</b> as configuration components implemented by software and/or hardware. The control-policy-setting unit <b>119</b> receives flow-rate policy data from the management server <b>101</b> and stores the data in the flow-rate-policy data <b>120</b>. The data reception unit <b>115</b> receives data flowing into the router <b>102</b>. The identification unit <b>116</b> distributes pieces of received data to a plurality of queues in accordance with identifiers set in the data. The controller <b>117</b> determines a queue from which data is to be output and an output destination of the data in accordance with the contents of the flow-rate-policy data <b>120</b>. The data transmission unit <b>118</b> sends out the data of the determined queue from the router <b>102</b>. It is to be noted that a transmission apparatus including a routing controller as one of its components can be utilized as a substitute for the router <b>102</b> specially used for routing.

P-0029[0029] In this embodiment, a meter <b>104</b> is an apparatus intercepting a communication line connecting two routers <b>102</b> to each other. The meter <b>104</b> comprises a request reception unit <b>121</b>, a request-response unit <b>122</b>, a data reception unit <b>123</b>, a data measurement unit <b>124</b> and a data transmission unit <b>125</b> as configuration components implemented by software and/or hardware. The data reception unit <b>123</b> receives data flowing into the meter <b>104</b> from the intercepted communication line. The data transmission unit <b>125</b> outputs data from the meter <b>104</b> to the intercepted communication line. The request reception unit <b>121</b> receives a request for a measurement of traffic from the management server <b>101</b>. The data measurement unit <b>124</b> is placed between the data reception unit <b>123</b> and the data transmission unit <b>125</b> and used for measuring a flow rate of data for each requested identifier. The request-response unit <b>122</b> transmits traffic information measured by the data measurement unit <b>124</b> to the management server <b>101</b>.

P-0030[0030] The initialization unit <b>106</b> employed in the management server <b>101</b> catalogs information required at an operation stage in the initialization data <b>112</b>. The initialization data <b>112</b> is used for storing tables such as resource information <b>201</b>, a service-level definition <b>401</b> and an initial flow-rate policy <b>601</b> as well as an interval of setting the flow-rate policy, an interval of acquiring flow-rate information and an interval of aggregating flow rates.

P-0031[0031]FIG. 2 is a diagram showing an exemplified data format of the resource information <b>201</b>. A resource shown in the figure refers to a specific interface of a particular router <b>102</b>. The resource is identified by a pair of a router ID <b>205</b> and an interface ID <b>206</b>. An interface of a router <b>102</b> is a port of a line emanating from the router <b>102</b>. A resource ID <b>202</b> is another identifier for uniquely identifying a specific resource among all resources of all the routers <b>102</b>. A meter ID <b>203</b> associated with a resource ID is an identifier for identifying a meter <b>104</b> for measuring the flow rate of data flowing to a resource identified by the resource ID. A direction <b>204</b> associated with a meter ID <b>203</b> is represented by a pair of an input interface and an output interface, which are associated with a meter <b>104</b> identified by the meter ID <b>203</b>. An interface of a meter <b>104</b> is a port of a line emanating from the meter <b>104</b>. Thus, a direction of transmitted data flowing through a resource is identified by a meter ID <b>203</b> and a direction <b>204</b>. A flow-rate limit <b>207</b> associated with a resource ID <b>202</b> is a limit of a flow rate of a flow in the direction of transmitted data flowing through the resource identified by the resource ID <b>202</b>. An attribute <b>208</b> associated with a resource ID <b>202</b> indicates whether the router <b>102</b> owning a resource identified by the resource ID <b>202</b> is a core router or an edge router. As is obvious from the table, a meter <b>104</b> measures a flow rate for each of two resources, which have different directions of transmitted data.

P-0032[0032]FIG. 3 is a diagram showing as an example a resource identified by a resource ID of 001 and a resource identified by a resource ID of 002. A router <b>102</b> identified by R001 has interfaces identified by IF001, IF002 and IF003. A router <b>102</b> identified by R002 has interfaces identified by IF001, IF002 and IF003. These two routers <b>102</b> are connected through a meter <b>104</b> identified by M001. The meter <b>104</b> has interfaces identified by IF001 and IF002. The meter <b>104</b> identified by M001 measures the flow rate of data output by the resource identified by the resource ID of 001 in the direction from IF001 to IF002 of the meter <b>104</b>. On the other hand, the meter <b>104</b> identified by M001 measures the flow rate of data output by the resource identified by the resource ID of 002 in the direction from IF002 to IF001 of the meter <b>104</b>. Thus, in accordance with the technique described above, data's flow rates measured by the meter <b>104</b> are each associated with a resource outputting the data.

P-0033[0033]FIG. 4 is a diagram showing an exemplified data format of the service level definition <b>401</b>. A number is assigned to each service level <b>402</b>, which is associated with an identifier <b>403</b>. An identifier <b>403</b> is a value set in a ToS field <b>506</b> in an IP header <b>502</b> of transmitted data <b>501</b>, which has a data structure shown in FIG. 5. The value set in a ToS field <b>506</b> is used for identifying a service level of the transmitted data <b>501</b>. The identifier <b>403</b> corresponds to a DSCP (DiffServ Code Point) in the case of DiffServ. A relative priority <b>404</b> assigned to a service level <b>402</b> is a priority level relative to other service levels. In other words, a relative priority <b>404</b> is a value corresponding to a weight for the service level or the identifier <b>403</b> associated with the relative priority <b>404</b>.

P-0034[0034] In the data format shown in FIG. 4, the data with a service level of 5 is data treated at the lowest priority level. Pieces of data having service levels of 4, 3 and 2 respectively are treated at gradually increasing priority levels. In addition, in order to assure the quality of communication, a desired minimum band that can be absolutely assured is considered as is the case with an EF (Expedited Forwarding) feature of DiffServ. In this case, a service level treated absolutely at the highest priority level by ignoring relative priorities of other service levels is defined. By using this service level treated absolutely at the highest priority level, it is possible to assure data of a minimum amount even in the event of a traffic jam. A contracted flow rate <b>405</b> is a flow rate contracted for each service level in an initial state of an operation.

P-0035[0035]FIG. 6 is a diagram showing an exemplified data format of the initial flow rate policy <b>601</b>. The initial flow rate policy <b>601</b> is a table for storing a send-out rate <b>603</b> in an initial state of an operation for each resource and each service level <b>602</b>. The initialization unit <b>106</b> creates the initial flow-rate policy <b>601</b>.

P-0036[0036] In the initial flow-rate policy <b>601</b>, the service level of 1 treated at the absolute priority level has the contracted flow rate <b>405</b> thereof as the send-out rate <b>603</b>. The send-out rate <b>603</b> of a service level other than the service level of 1 is found by using the following equation: <maths id="MATH-US-00001" num="1"><math overflow="scroll"><mtable><mtr><mtd><mrow><msub><mi>r</mi><mi>n</mi></msub><mo>=</mo><mfrac><mrow><mrow><mo>(</mo><mrow><mi>V</mi><mo>-</mo><msub><mi>r</mi><mn>1</mn></msub></mrow><mo>)</mo></mrow><mo></mo><msub><mi>γ</mi><mi>n</mi></msub><mo></mo><msub><mi>W</mi><mi>n</mi></msub></mrow><mrow><mo>∑</mo><mrow><msub><mi>γ</mi><mi>k</mi></msub><mo></mo><msub><mi>W</mi><mi>k</mi></msub></mrow></mrow></mfrac></mrow></mtd><mtd><mrow><mo>(</mo><mrow><mi>Equation</mi><mo></mo><mstyle><mtext> </mtext></mstyle><mo></mo><mn>1</mn></mrow><mo>)</mo></mrow></mtd></mtr></mtable></math><img file="US20030191853A1-20031009-M00001.TIF" id="EMI-M00001" he="18.96615" wi="216.027" img-format="tif" img-content="mf" /><attachments><attachment idref="MATHEMATICA-00001" attachment-type="nb" file="US20030191853A1-20031009-M00001.NB" /></attachments></maths>

P-0037[0037] where symbol rn denotes the send-out rate <b>603</b> of service level n, symbol V denotes the flow-rate limit <b>207</b> of the line, symbol γn or γk denotes the relative priority <b>404</b> of level n or k respectively whereas symbol Wn or Wk denotes contracted flow rate <b>405</b> of level n or k respectively.

P-0038[0038]FIG. 7 is a diagram showing an exemplified structure of flow rate policy data transmitted by the management server <b>101</b> to a router <b>102</b> and set by the router <b>102</b>. A target interface <b>701</b> refers to a resource identified by a resource ID <b>202</b>. In this case, the target interface <b>701</b> is expressed by an IP address for identifying a specific interface of a particular router. A flow-rate policy <b>702</b> comprises a plurality of flow-rate rules <b>703</b>, which each include a conditional part <b>704</b> and an operational part <b>705</b>. A flow-rate rule <b>703</b> indicates that, if the condition of the conditional part <b>704</b> is satisfied, control shall be executed at the send-out rate of the operational part <b>705</b> in the same flow-rate rule <b>703</b> as the conditional part <b>704</b>. The flow-rate-policy-setting unit <b>108</b> converts the initial flow-rate policy <b>601</b> for each resource into a flow-rate policy described in a data format shown in FIG. 7 and transmits the flow-rate policy obtained as a result of conversion to a router having the resource. The control-policy-setting unit <b>119</b> receives the flow-rate policy, converts the policy-into data with a table format and stores the data in the flow-rate-policy data <b>120</b>. After the setting operation, the flow-rate-policy-setting unit <b>108</b> stores the initial flow-rate policy <b>601</b> in the all-flow-rate-policy data <b>114</b>.

P-0039[0039]FIG. 8 is an explanatory diagram showing a model representing flows of data <b>501</b> transmitted in a router <b>102</b>. The data reception unit <b>115</b> receives transmitted data <b>501</b>. The identification unit <b>116</b> stores the data <b>501</b> in a queue selected in accordance with the value set in the ToS field of the data <b>501</b>. The controller <b>117</b> executes control to output data from each queue on the basis of the contents of the flow-rate-policy data <b>120</b> so as to achieve a rate determined in advance for the queue. If the data stored in a queue is of too small quantity to satisfy the rate determined for the queue, the remaining time can be spent instead to send out data from any other queue. The data transmission unit <b>118</b> passes on data received from the queues to a communication line. In general, the router <b>102</b> is a special-purpose router or, as a substitute for the special-purpose router, a transmission apparatus or a transmission means can be employed as far as the transmission apparatus or the transmission means includes the data reception unit <b>115</b>, the identification unit <b>116</b>, the controller <b>117</b> and the data transmission unit <b>118</b>.

P-0040[0040] As the setting process is finished, an operation is started. When the operation is started, the flow-rate acquisition unit <b>111</b>, the flow-rate aggregation unit <b>110</b> and the flow-rate-policy control unit <b>107</b> begin to work.

P-0041[0041]FIG. 9 shows a flowchart representing a procedure of a process carried out by the flow-rate acquisition unit <b>111</b>. The flow-rate acquisition unit <b>111</b> acquires a flow rate information from a meter <b>10</b> periodically. The intervals at which a flow rate is acquired are determined at the initialization time. A flow rate is acquired from a meter <b>104</b> only for data subjected to traffic management for each resource.

P-0042[0042] The flowchart begins with a step <b>901</b> at which, by referring to the resource information <b>201</b>, a resource for which a flow rate is acquired is selected. Then, at the next step <b>902</b>, a request for acquisition of a flow rate for a resource is transmitted to a meter <b>104</b> for measuring the flow rate. The meter <b>104</b>, to which the request is transmitted, is specified by using an IP address. A service level is expressed by an identifier associated with the service level. According to the service-level definition shown in FIG. 4, flow rates of data with ToS values (identifiers) of 184, 152, 112, 72 and 0 are acquired. Subsequently, at the next step <b>903</b>, the flow rates are received from the meter <b>104</b>. Then, at the next step <b>904</b>, the flow-rate acquisition unit <b>111</b> creates a table like one shown in FIG. 10. Flow rates shown in the table of FIG. 10 are send-out rates sampled at particular times shown in the table.

P-0043[0043] The table shown in FIG. 10 shows, for each resource ID, a time at which a flow rate has been measured, a condition (or an identifier) of the flow rate and the flow rate itself.

P-0044[0044] When the operation to acquire the flow rate is completed, the flow of the processing goes on to a step <b>905</b> to form a judgment as to whether or not it is necessary to acquire flow rates for a next resource. If the operation to acquire flow rates for all resources has not been completed, the flow of the processing goes back to the step <b>901</b> to acquire flow rates for the next resource. If the operation to acquire flow rates for all resources has been completed, on the other hand, the flow of the processing goes on to a step <b>906</b> to compare a time elapsing since the immediately preceding aggregation of flow rates with an aggregation interval set at the initialization time. If the time elapsing since the immediately preceding aggregation of flow rates has exceeded the aggregation interval, the flow of the processing goes on to a step <b>907</b> at which a request for an aggregation of flow rates is issued to the flow-rate aggregation unit <b>110</b>. Then, the flow of the processing goes on to a step <b>908</b> to enter a state of waiting for an acquisition time set at the initialization time to lapse before going back to the step <b>901</b> to again acquire flow rates for the first resource.

P-0045[0045]FIG. 11 shows a flowchart representing a procedure of a process carried out by the flow-rate aggregation unit <b>110</b>. The flowchart begins with a step <b>1101</b> at which the flow-rate aggregation unit <b>110</b> forms a judgment as to whether or not a received request is a request for aggregation of flow rates that has been received from the flow-rate acquisition unit <b>111</b>. If the received request is not a request for aggregation of flow rates that has been received from the flow-rate acquisition unit <b>111</b>, the flow of the processing goes on to a step <b>1112</b> at which the flow-rate aggregation unit <b>110</b> forms a judgment as to whether or not the received request is a display request received from the flow-rate-data display unit <b>109</b>. If the received request is a request for aggregation of flow rates that has been received from the flow-rate acquisition unit <b>111</b>, on the other hand, the flow of the processing goes on to a step <b>1102</b> at which the flow-rate aggregation unit <b>110</b> receives a table like the one shown in FIG. 10, and selects a resource. Then, at the next step <b>1103</b>, a table is created for the resource and for each service level in a format shown in FIG. 12. As shown in the figure, the table includes flow rates sampled at different times for a resource identified by a resource ID of 001 and for a service level of 1. Subsequently, at the next step <b>1104</b>, the flow-rate aggregation unit <b>110</b> forms a judgment as to whether or not flow rates for different service levels have been aggregated for all resources. The operations of the steps <b>1102</b> to <b>1104</b> are carried out till flow rates for different service levels have been aggregated for all resources.

P-0046[0046] As flow rates for different service levels have been aggregated for all resources, the flow of the processing goes on to a step <b>1105</b> at which the aggregated data is stored in the acquired-flow-rate data <b>113</b> in the format shown in FIG. 12. Then, at the next step <b>1106</b>, a resource associated with tables of aggregated data, which are each created for a service level, is again selected. Subsequently, at the next step <b>1107</b>, in order to form a judgment as to whether or not an interval of setting a flow-rate policy is proper, a variance of aggregated flow rates is found for each service level by using the following equation: <maths id="MATH-US-00002" num="2"><math overflow="scroll"><mtable><mtr><mtd><mrow><mi>S</mi><mo>=</mo><msqrt><mfrac><mrow><mo>∑</mo><mrow><mo>(</mo><mrow><msub><mi>v</mi><mi>t</mi></msub><mo>-</mo><mover><mi>v</mi><mi>_</mi></mover></mrow><mo>)</mo></mrow></mrow><mi>T</mi></mfrac></msqrt></mrow></mtd><mtd><mrow><mo>(</mo><mrow><mi>Equation</mi><mo></mo><mstyle><mtext> </mtext></mstyle><mo></mo><mn>2</mn></mrow><mo>)</mo></mrow></mtd></mtr></mtable></math><img file="US20030191853A1-20031009-M00002.TIF" id="EMI-M00002" he="24.01245" wi="216.027" img-format="tif" img-content="mf" /><attachments><attachment idref="MATHEMATICA-00002" attachment-type="nb" file="US20030191853A1-20031009-M00002.NB" /></attachments></maths>

P-0047[0047] where symbol S denotes a computed value of the variance, ν t denotes a flow rate sampled at an acquisition time, over-lined symbol ν denotes the average value of flow rates sampled at different acquisition times and symbol T denotes the number of acquisitions.

P-0048[0048] Then, the flow of the processing goes on to a step <b>1108</b> at which the computed value S of the variance is examined to form a judgment as to whether or not the computed value S is within a predetermined threshold range used for changing the flow-rate policy. If the computed value S of the variance is outside the predetermined threshold range, the flow of the processing goes on to a step <b>1109</b> at which the flow-rate aggregation unit <b>110</b> changes the interval of setting the flow-rate policy. To be more specific, if the computed value S of the variance is greater than the upper limit of the predetermined threshold range, the flow-rate aggregation unit <b>110</b> reduces the interval of setting the flow-rate policy in order to set the flow-rate policy more frequently. If the computed value S of the variance is smaller than the lower limit of the predetermined threshold range, on the other hand, the flow-rate aggregation unit <b>110</b> increases the interval of setting the flow-rate policy in order to set the flow-rate policy less frequently. Then, at the next step <b>1110</b>, the flow-rate aggregation unit <b>110</b> informs the flow-rate-policy control unit <b>107</b> of the new interval of setting the flow-rate policy. Subsequently, the flow of the processing goes on to a step <b>1111</b>. If the judgment formed at the step <b>1108</b> indicates that the computed value S of the variance is within the predetermined threshold range, on the other hand, the flow of the processing goes on directly to the step <b>1111</b>. At the step <b>1111</b>, the flow-rate aggregation unit <b>110</b> forms a judgment as to whether or not the operations of the steps <b>1107</b> to <b>1110</b> have been carried out for all resources. The operations of the steps <b>1106</b> to <b>1111</b> are carried out till the operations of the steps <b>1107</b> to <b>1110</b> have been performed for all resources.

P-0049[0049] The flow-rate-data display unit <b>109</b> is a program for displaying measured flow rates as a graph. When the operator wants to verify-information on flow rates, the operator issues a display request to the flow-rate-data display unit <b>109</b>. Receiving the display request, the flow-rate-data display unit <b>109</b> issues another request specifying a resource ID to the flow-rate aggregation unit <b>110</b>. At a step <b>1112</b>, the flow-rate aggregation unit <b>110</b> forms a judgment as to whether or not the other request is a display request. If the result of the judgment is Yes indicating that the other request is a display request, the flow of the processing goes on to a step <b>1113</b> at which a resource in the aggregated data is selected. Then, at the next step <b>1114</b>, the flow-rate aggregation unit <b>110</b> forms a judgment as to whether or not the selected resource is the requested resource specified in the other request. If the selected resource is the requested resource, the flow of the processing goes on to a step <b>1115</b> at which a resource table is created. Then, at the next step <b>1116</b>, the resource table is transferred to the flow-rate-data display unit <b>109</b> in response to the other request. Subsequently, at the next step <b>1117</b>, the flow-rate aggregation unit <b>110</b> forms a judgment as to whether or not the operations of the steps <b>1114</b> to <b>1116</b> have been carried out for all resources. If the operations of the steps <b>1114</b> to <b>1116</b> have not been carried out for all resources, the flow of the processing goes on to a step <b>1113</b> to repeat the operations of the steps <b>1113</b> to <b>1117</b> till the operations of the steps <b>1114</b> to <b>1116</b> are carried out for all resources. Receiving the responses from the flow-rate aggregation unit <b>110</b>, the flow-rate-data display unit <b>109</b> displays a graph based on the table shown in FIG. 12 on the display unit like one shown in FIG. 13. FIG. 13 is a diagram showing a graph representing changes in flow rate with the lapse of time for a specific resource and for a particular service level. A straight line <b>1301</b> shown in FIG. 13 represents a send-out rate set at an acquisition time. The operator is capable of issuing a request for a change in flow-rate policy to the flow-rate-policy-setting unit <b>108</b> by moving the straight line <b>1301</b> in the upward or downward direction through an operation carried out on the display screen.

P-0050[0050]FIG. 14 shows a flowchart representing a procedure of a process carried out by the flow-rate-policy control unit <b>107</b>. The flow-rate-policy control unit <b>107</b> sets a flow-rate policy periodically at intervals computed by the flow-rate aggregation unit <b>110</b> or intervals set by the operator. The flowchart shown in FIG. 14 begins with a step <b>1401</b> at which the flow-rate-policy control unit <b>107</b> acquires an interval of setting a flow-rate policy from the initialization data <b>112</b>. Then, at the next step <b>1402</b>, the flow-rate-policy control unit <b>107</b> compares a time elapsing since a last operation to set a flow-rate policy with the acquired interval in order to form a judgment as to whether or not the elapsed time is greater than the setting interval. If the elapsed time is not greater than the setting interval, the flow of the processing goes on to a step <b>1403</b> to enter a wait state for one second. Then, after the wait state has elapsed for one second, the flow of the processing goes back to the step <b>1401</b> at which the flow-rate-policy control unit <b>107</b> again acquires an interval of setting a flow-rate policy from the initialization data <b>112</b>. If the elapsed time is greater than the setting interval, on the other hand, the flow of the processing goes on to a step <b>1404</b> at which the flow-rate-policy control unit <b>107</b> acquires current information on a flow-rate policy from the all-flow-rate-policy data <b>114</b>. Then, at the next step <b>1405</b>, the flow-rate-policy control unit <b>107</b> acquires flow-rate information from the acquired-flow-rate data <b>113</b>.

P-0051[0051] Subsequently, at the next step <b>1406</b>, a resource is selected. Then, at the next step <b>1407</b>, a service level is selected. Subsequently, the flow of the processing goes on to a step <b>1408</b> to form a judgment as to whether or not the selected service level is the service level of 1. If the result of the judgment formed at the step <b>1408</b> is Yes, indicating that the selected service level is the service level of 1, the flow of the processing goes on to a step <b>1409</b> at which a maximum value of the flow rates is extracted since the service level is a level whose data is to be treated absolutely with the highest priority level. If the result of the judgment formed at the step <b>1408</b> is No, indicating that the selected service level is not the service level of 1, on the other hand, the flow of the processing goes on to a step <b>1410</b> at which a traffic average value of the flow rates is found for the service level. Then, the flow of the processing goes on from either the step <b>1409</b> or <b>1410</b> to a step <b>1411</b> to form a judgment as to whether or not the operations of the steps <b>1408</b> and <b>1409</b> or <b>1410</b> have been carried out for all service levels. If the results of the judgment formed at the step <b>1411</b> is Yes, indicating that the operations of the steps <b>1408</b> and <b>1409</b> or <b>1410</b> have been carried out for all service levels, the flow of the processing goes on to a step <b>1412</b> at which a send-out rate is computed for each service level.

P-0052[0052] A send-out rate for the service level of 1 is computed in accordance with the following equation:

<i>r</i>_1t=(<i>ν</i>_1max<i>νVr</i>_1(t−1)  (Equation 3)

P-0053[0053] where symbol Ξ<b>1</b>max denotes the maximum value of the flow rates for the service level of 1, symbol r<b>1</b>t denotes a send-out rate set at the present time for the service level of 1 and symbol r<b>1</b>(t−1) denotes a send-out rate set at the immediately preceding time for the service level of 1. That is to say, since data with the service level of 1 takes precedence of any other data, the maximum value of the traffic is used as a send-out rate as it is. If the maximum value of the traffic is smaller than the send-out rate used so far, however, the send-out rate is not changed.

P-0054[0054] On the other hand, a send-out rate for a service level other than the service level of 1 is computed in accordance with the following equation: <maths id="MATH-US-00003" num="3"><math overflow="scroll"><mtable><mtr><mtd><mrow><msub><mi>r</mi><mrow><mi>n</mi><mo></mo><mstyle><mtext> </mtext></mstyle><mo></mo><mi>t</mi></mrow></msub><mo>=</mo><mfrac><mrow><mrow><mo>(</mo><mrow><mi>V</mi><mo>-</mo><msub><mi>r</mi><mrow><mn>1</mn><mo></mo><mi>t</mi></mrow></msub></mrow><mo>)</mo></mrow><mo></mo><msub><mi>γ</mi><mi>n</mi></msub><mo></mo><msub><mover><mi>v</mi><mi>_</mi></mover><mi>n</mi></msub></mrow><mrow><mo>∑</mo><mrow><msub><mi>γ</mi><mi>k</mi></msub><mo></mo><msub><mover><mi>v</mi><mi>_</mi></mover><mi>k</mi></msub></mrow></mrow></mfrac></mrow></mtd><mtd><mrow><mo>(</mo><mrow><mi>Equation</mi><mo></mo><mstyle><mtext> </mtext></mstyle><mo></mo><mn>4</mn></mrow><mo>)</mo></mrow></mtd></mtr></mtable></math><img file="US20030191853A1-20031009-M00003.TIF" id="EMI-M00003" he="19.93005" wi="216.027" img-format="tif" img-content="mf" /><attachments><attachment idref="MATHEMATICA-00003" attachment-type="nb" file="US20030191853A1-20031009-M00003.NB" /></attachments></maths>

P-0055[0055] where over-lined symbol νn denotes the average flow rate for a service level of n other than the service level of 1 and symbol rnt denotes a send-out rate set this time for a service level of n other than the service level of 1. Thus, Eq. (4) indicates that a send-out rate for a specific service level other than the service level of 1 is the specific service level's average flow rate weighted by a quantity according to the specific service level.

P-0056[0056] Then, at the next step <b>1413</b>, the computed send-out rate is compared with the present send-out rate to form a judgment as to whether or not the flow-rate policy needs to be changed. If a difference between the computed send-out rate and the present send-out rate is greater than a predetermined threshold value, the flow of the processing goes on to a step <b>1414</b> at which a table shown in FIG. 15 is created to include computed send-out rates for all service levels, and a request for setting of a flow-rate policy is submitted to the flow-rate-policy-setting unit <b>108</b>. Subsequently, the flow of the processing goes on to a step <b>1415</b> at which the flow-rate-policy control unit <b>107</b> forms a judgment as to whether or not the operations of the steps <b>1407</b> to <b>1414</b> have been carried out for all service levels. If the operations of the steps <b>1407</b> to <b>1414</b> have not been carried out for all service levels, the flow of the processing goes back to the step <b>1406</b> to repeat the operations of the steps <b>1406</b> to <b>1415</b>. The operations of the steps <b>1406</b> to <b>1415</b> are carried out repeatedly till the operations of the steps <b>1407</b> to <b>1414</b> are performed for all service levels. Receiving the request for setting of a flow-rate policy, the flow-rate-policy-setting unit <b>108</b> sets a flow-rate policy in an interface of a router <b>102</b> subjected to traffic management on the basis of the table shown in FIG. 15.

P-0057[0057] By carrying out the series of operations described above, the send-out rate of each router in the network subjected to traffic management is constantly updated in accordance with the traffic of the network.

P-0058[0058] In accordance with the present invention, flow rates in the network can be controlled dynamically in dependence on the traffic in the network.