Source: http://www.google.com/patents/US7630317?dq=7,546,338
Timestamp: 2015-03-27 08:15:22
Document Index: 710582385

Matched Legal Cases: ['Application No. 02819527', 'Application No. 02819527', 'Application No. 02819527', 'Application No. 02807196', 'Application No. 02807196', 'Application No. 582224', 'Application No. 582224']

Patent US7630317 - Transmission bandwidth control device - Google PatentsSearch Images Maps Play YouTube News Gmail Drive More »Sign inAdvanced Patent SearchPatentsIncluded are a network information database for storing the statistical information collected from a router, a user request processing unit for accepting and processing a flow forwarding request from a user terminal connected to the network, a route control unit for searching for a route corresponding...http://www.google.com/patents/US7630317?utm_source=gb-gplus-sharePatent US7630317 - Transmission bandwidth control deviceAdvanced Patent SearchPublication numberUS7630317 B2Publication typeGrantApplication numberUS 10/769,701Publication dateDec 8, 2009Filing dateJan 30, 2004Priority dateJan 31, 2003Fee statusPaidAlso published asCN1525701A, CN100473042C, DE602004024732D1, EP1443722A2, EP1443722A3, EP1443722B1, US20040184483Publication number10769701, 769701, US 7630317 B2, US 7630317B2, US-B2-7630317, US7630317 B2, US7630317B2InventorsAkiko Okamura, Koji Nakamichi, Hitoshi Yamada, Akira Nagata, Katsuichi Nakamura, Seiji Nomiyama, Mitsunori Fukazawa, Nobuhiro Kawamura, Sugiko Itagaki, Takashi IwasakiOriginal AssigneeFujitsu LimitedExport CitationBiBTeX, EndNote, RefManPatent Citations (15), Non-Patent Citations (33), Referenced by (2), Classifications (7), Legal Events (3) External Links: USPTO, USPTO Assignment, EspacenetTransmission bandwidth control device
US 7630317 B2Abstract
wherein the quality non-guaranteed route searching step involves selecting a route for a flow that does not guarantee a forwarding quality, using a ratio of a remaining bandwidth, as a link's residual bandwidth, which is a result of subtracting the bandwidth for the flow that does not guarantee the forwarding quality from a link bandwidth as link's physical bandwidth, with respect to a bandwidth unreserved for the flow that guarantees the forwarding quality. Description
Note that, in this embodiment, the term of �load balancing� refers to distributing the load of inequality to plural paths in the flow. Namely, in this embodiment, �load balancing� and �load sharing� refer to both the meaning of distributing the load of plural paths in the flow with equality and distributing the load of plural paths in the flow with inequality.
The policy setting screen 201 in FIG. 2 has a reallocation threshold value setting area 201 a for setting a threshold value on the occasion of judging whether a route reallocation about the GS flow is conducted or not. Further, the policy setting screen 201 has a congestion judging threshold value setting area 201 b for setting a threshold on the occasion of judging whether or not the congestion occurs on the route about the BES flow. Note that there will hereinafter be explained a judgment as to whether or not the reallocation related to the GS flow and the load on the route related to the BES flow are equal to or smaller than threshold values which are set in the reallocation threshold value setting area 201 a and in the congestion judging threshold value setting area 201 b. To begin with, a route selection system and a link residual-bandwidth calculation system in the policy 1 and the policy 2 will be described in detail.
In FIG. 4, C1 is a coefficient representing an occupying ratio of the GS flow in the link. For instance, in the case of defining that 80% of the link may be given to the GS flow, it becomes such as C1=0.8. From the above, a value that C1 can take is given by 0<C1≦1. Further, the bandwidth that may be occupied by the GS flow is given such as C1�WL, however, as a matter of fact, a statistical multiplexing effect can be expected corresponding to a flow accommodation quantity. In face, the statistical multiplexing effect enables an acceptance of more GS requests than C1�WL. Accordingly, C2 is what represents a ratio of how much the requests are to be accepted. At this time, it becomes such as C2>1.
To start with, a network control system in the policy 1 will be contemplated. It is contemplated from a state in which, as illustrated in FIG. 18, a path GS1 for the GS flow (this type flow will hereinafter be called the GS flow, and the path for the GS flow will hereinafter be called a GS path) and a path BES1 for the flow that does not guarantee the forwarding quality such as the bandwidth, the delay, etc. (this type of flow will hereinafter be called the BES flow, and the path for the BES flow will hereinafter be called a BES path), are set up respectively on a route of the router 1�the router 2�the router 3. At this time, a bandwidth of 25 Mbps is reserved for the path GS1, and in fact traffic of 20 Mbps is assumed to flow therethrough. Further, at this time, traffic of 60 Mbps is assumed to flow through the path BES1. Then, observing a link between the router 2 and the router 3, 25 Mbps is reserved in a bandwidth of 100 Mbps, it can be understood that as a traffic quantity that actually flows totals to 80 Mbps including 20 Mbps of the GS flow and 60 Mbps of the BES flow.
Similarly, a sub-policy 33 is prescribed such that �when accepting requests for a service which guarantees the forwarding quality such as the bandwidth, the delay, etc. and for a service which does not guarantee the forwarding quality such as the bandwidth, the delay, etc., routes is selected according to the respectively predetermined route selection policies, the route is determined from a topology taking allowances for only the link of which the link's residual bandwidth is equal to or larger than the request bandwidth when accepting the request for-the service which guarantees the forwarding quality such as the bandwidth, the delay, etc., and the route is determined from a topology taking allowances for all the links when accepting the request for the service which does not guarantee the forwarding quality such as the bandwidth, the delay, etc.�.
On the other hand, in the policy 1, with an application of such a sub-policy that �there is included a function of setting a threshold value in a ratio (a maximum value in a ratio of the actual using bandwidth for the non-guaranteed service to the bandwidth not ensured for the quality guaranteed service in the physical bandwidth of the link configuring the path), of the actual using bandwidth for the service that does not guarantee the forwarding quality such as the bandwidth, the delay, etc., at which to occupy a bandwidth left by subtracting the bandwidth ensured for the service that guarantees the forwarding quality such as the bandwidth, the delay, etc. in the path, and, in the case of exceeding the threshold value, the flow that does not guarantee the forwarding quality such as the bandwidth, the delay, etc. is shifted to the detour route�, this ratio becomes 20% given by Wb/(WL−WG)=60/(100−50)=1.2, and it is judged that the congestion occurs due to an excess over the threshold value.
FIG. 20 shows a result in which the sub-policies 2, 4, 6, 9 are applied, a route of the router 1�the route 4�the router 3 is selected in a way that sets a new BES path as BES2, and a flow of 55 Mbps is shifted. Therefore, even if traffic of 25Mbps flows to the path GS2, it becomes as shown in FIG. 21. Accordingly, it does not happen that the traffic is discarded as in the prior art. Thus, the use of the embodiment enables a quantity of the traffic discarded to be reduced by effecting the load balancing of the BES flow while taking the bandwidth reserved for the GS flow into consideration.
Next, a network control system in other example 2 for carrying out the policy 2 in the embodiment will be contemplated. As illustrated in FIG. 22, it is assumed that the GS path GS1 be set up on a route of the router 1�the router 2�the router 3, the GS path GS2 be set up on a route of the router 1�the router 4�the router 3 and BES1 as the BES path be set up on a route of the router 1�the router 2, respectively. An assumption is that the path GS1 with a reservation on the order of 60 Mbps receives an actual flux of 20 Mbps flow, the path GS2 with a reservation on the order of 80 Mbps receives an actual flux of 80 Mbps flow, and the path BES1 receives an actual flux of 70 Mbps flow.
Applied when calculating the route for the GS flow is a sub-policy that �there is made a selection from a topology in which to connect a link of which a using bandwidth for a service that does not guarantee the forwarding quality such as the bandwidth, the delay, etc. does not exceed a threshold value and of which a residual bandwidth obtained by a calculation of a link's using bandwidth is equal to or larger than the request bandwidth�. Herein, the threshold value of the BES flow shall be 50 Mbps. At this time, the link between the router 1 and the router 2 is in excess of the threshold value of the BES flow and is therefore excluded from the topology, and the link between the router 1 and the router 4 and the link between the router 4 and the router 3 have no residual bandwidth equal to or larger then the request bandwidth and are therefore excluded from the topology. As a result, the route calculated for this GS flow becomes a route of the router 1�the router 5�the router 6�the router 3. FIG. 23 illustrates a state when a flow of 30 Mbps comes into an actual flux, wherein GS3 is a path set up on this route. Thus, the use of the embodiment yields such an effect that a quantity of discarding the traffic of the BES flow can be decreased by taking allowances for the bandwidth for the BES flow when determining the path for the GS flow.
Next, it is considered when the flow of the path BES1 discontinues to flow from the state in FIG. 23 and turns out as shown in FIG. 24. According to the prior art, a dynamic change of the route for the GS flow is not conducted, and hence this state is maintained. In this state, however, the flow in the path GS3, in spite of a sufficient residual bandwidth being formed in the route on the path GS1, passes through a detour route, resulting in a poor bandwidth utilizing efficiency. Further, because of the detour route, there increase the hop count and the forwarding delay as well. It is therefore desired that the GS flow across the detour route be shifted to a more proper route. At this time, it is considered to use in the embodiment a sub-policy that �there is included a function of setting a threshold value in a path using ratio (a maximum value in a ratio of the actual using bandwidth to the physical bandwidth of the link configuring the path), and, when there is a residual bandwidth for accommodating the quality guaranteed flow when less than the threshold value and there exists other less optimal path, the quality guaranteed flow is shifted to the path less than the threshold value from the less optimal path�. At this time, the threshold value is set at 30%. Then, the using ratio of the link on the path GS1 is 20% and is thus less than the threshold value, and hence the flow shift takes place. Herein, the path GS3 is the detour route, so that the flow in the path GS3 is shifted to the path GS1. FIG. 25 shows a result when the whole flow in the path GS3 is shifted to the path GS1. Thus, the use of the embodiment come to enable, the GS flow being shifted, the link using efficiency to be improved and also the forwarding delay of the GS flow to be decreased.
Moreover, as shown in FIG. 26, there is considered a case where the GS path GS1 is set up on the route of the router 1�the router 2�the router 3, the GS path GS2 is set up on the route of the router 1�the router 4�the router 3 and the GS path GS3 is set up on the route of the router 1�the router 5�the router 6�the router 3, respectively. It is assumed that each of the path GS1, the path GS2 and the path GS3 has a reservation of 80 Mbps, the path GS1 and the path GS3 receive an actual flux of 40 Mbps flow, and the path GS2 receives an actual flux of 60 Mbps flow. In such a state, an assumption is that the router 1 gives a request for the GS flow of 70 Mbps to the router 3. According to the prior art, since the route capable of ensuring a bandwidth for 70 Mbps is not discovered, the acceptance is rejected. The embodiment, however, uses a sub-policy that �in a state where a plurality of paths are set up for the GS flow, in the case of being unable to ensure the request bandwidth for the quality guaranteed service due to a small residual bandwidth but in the case of being able to ensure the request bandwidth by shifting the existing flows accommodated in the plurality of paths, the request is to be accepted by effecting the flow shift�. Then, if 30 Mbps in the flow of the path GS3 is shifted to the path GS1, the requested 70 Mbps flow can be accepted by use of the path GS3. This state is illustrated in FIG. 27. Thus, the use of the embodiment enables a decrease of the possibility that the user request falls into a call loss by shifting the GS flow.
Patent CitationsCited PatentFiling datePublication dateApplicantTitleUS6115372 *Feb 4, 1998Sep 5, 2000Newcom Technologies, Inc.Synchronous packet switchingUS6493317 *Dec 18, 1998Dec 10, 2002Cisco Technology, Inc.Traffic engineering technique for routing inter-class traffic in a computer networkUS6590867 *May 27, 1999Jul 8, 2003At&T Corp.Internet protocol (IP) class-of-service routing techniqueUS6721270 *Aug 9, 1999Apr 13, 2004Lucent Technologies Inc.Multicommodity flow method for designing traffic distribution on a multiple-service packetized networkUS6788646 *Apr 26, 2000Sep 7, 2004Telefonaktiebolaget Lm Ericsson (Publ)Link capacity sharing for throughput-blocking optimalityUS6956821 *Jun 11, 2001Oct 18, 2005Telefonaktiebolaget L M Ericsson (Publ)Path determination in a data networkUS7136357 *Mar 1, 2001Nov 14, 2006Fujitsu LimitedTransmission path controlling apparatus and transmission path controlling method as well as medium having transmission path controlling program recorded thereonUS7257632 *Jul 30, 2001Aug 14, 2007Fujitsu LimitedMethod and apparatus for a bandwidth broker in a packet networkUS7310341 *Nov 25, 2002Dec 18, 2007Alcatel Canada Inc.System and method for parallel connection selection in a communication networkUS20020174246 *Jan 24, 2001Nov 21, 2002Amos TanayCentralized system for routing signals over an internet protocol networkEP0926919A2Nov 30, 1998Jun 30, 1999Northern Telecom LimitedAutomatic connections managerEP1130849A2Mar 1, 2001Sep 5, 2001Fujitsu LimitedTransmission path controlling apparatus, method and programJP2001144804A Title not availableJP2001320420A Title not availableWO2002023807A2Sep 11, 2001Mar 21, 2002Yoram AvidanCentralized system for routing signals over an internet protocol network* Cited by examinerNon-Patent CitationsReference1Anwar Elwalid, et al. "MATE: MPLS Adaptive Traffic Engineering" Proceedings IEEE Infocom, vol. 1 of 3, Conf. 20, Apr. 22, 2001, pp. 1300-1309, XP010538821.2Aug. 25, 2008 International Search Report from PCT Patent Application No. PCT/US2008/068838 filed Jun. 30, 2008 (4 pp.).3Chen, Jizhuang, Dec. 21, 2007 Office Action from Chinese Patent Application No. 02819527.2 filed Oct. 4, 2002 (12 pp.).4Chen, Jizhuang, Dec. 30, 2005 Office Action from Chinese Patent Application No. 02819527.2 filed Oct. 4, 2002 (9 pp.).5Chen, Jizhuang, Sep. 26, 2008 Office Action from Chinese Patent Application No. 02819527.2 filed Oct. 4, 2002 (4 pp.).6Chinese Office Action dated Nov. 4, 2005.7Haider, Saira Bano, Jun. 12, 2008 Office Action from U.S. Appl. No. 11/104,759 filed Apr. 13, 2005 (10 pp.).8Harlan, Robert D., Jan. 2, 2008 Office Action from U.S. Appl. No. 11/117,981 filed Apr. 29, 2005 (6 pp.).9Harlan, Robert D., Jan. 26, 2007 Office Action from U.S. Appl. No. 11/117,981 filed Apr. 29, 2005 (8 pp.).10Harlan, Robert D., Jul. 12, 2007 Office Action from U.S. Appl. No. 11/117,981 filed Apr. 29, 2005 (6 pp.).11Harlan, Robert D., Jul. 20, 2006 Office Action from U.S. Appl. No. 11/117,981 filed Apr. 29, 2005 (6 pp.).12Harlan, Robert D., Jul. 25, 2008 Office Action from U.S. Appl. No. 11/117,981 filed Apr. 29, 2005 (8 pp.).13Harlan, Robert D., Nov. 7, 2005 Office Action from U.S. Appl. No. 11/117,981 filed Apr. 29, 2005 (7 pp.).14Ikenaga, et al., "Performance Evaluation of Dynamic Rerouting Algorithm for Class Based QoS Traffic" Nov. 2000, pp. 45-50.15Katoh, et al., "A Study of IP Traffic Engineering Mechanisms" Neue Kommunikations-anwendungen in modernen Netzen, Feb. 2002.16Le, Hoa T., Sep. 25, 2008 Office Action fom U.S. Appl. No. 11/612,554 filed Dec. 19, 2006 (8 pp).17Maksymonko, John M., Aug. 6, 2008 Office Action from U.S. Appl. No. 11/305,279 filed Dec. 16, 2005 (11 pp.).18Maksymonko, John M., Feb. 20, 2008 Office Action from U.S. Appl. No. 11/305,279 filed Dec. 16, 2005 (14 pp.).19Maksymonko, John M., Jul. 17, 2008 Office Action from U.S. Appl. No. 11/305,281 filed Dec. 16, 2005 (13 pp.).20Maksymonko, John M., Jun. 11, 2008 Office Action from U.S. Appl. No. 11/642,124 filed Dec. 20, 2006 (16 pp.).21Maksymonko, John M., Jun. 13, 2008 Office Action from U.S. Appl. No. 11/641,514 filed Dec. 19, 2006 (7 pp.).22Maksymonko, John M., May 28, 2008 Office Action from U.S. Appl. No. 11/642,802 filed Dec. 20, 2006 (10 pp.).23Maksymonko, John M., May 30, 2008 Office Action from U.S. Appl. No. 11/642,795 filed Dec. 20, 2006 (12 pp.).24May 27, 2008 International Search Report from PCT Patent Application No. PCT/US2007/087869 filed Dec. 18, 2007 (4 pp.).25May 30, 2008 International Search Report from PCT Patent Application No. PCT/US2007/026031 filed Dec. 19, 2007 (4 pp.).26Mullis, Jeffrey C., Oct. 31, 2008 Office Action from U.S. Appl. No. 11/641,514 filed Dec. 19, 2006 (10 pp.).27Nakamichi, et al., "Dynamic Traffic Engineering Under Different Traffic Patterns", 2002 CQR International Workshop on Communication Quality and Reliability, May 4, 2002.28Schutte, M., Aug. 8, 2006 Office Action from European Patent Application No. 02807196.7 filed Oct. 4, 2002 (5 pp.).29Schutte, Maya, Sep. 3, 2007 Office Action from European Patent Application No. 02807196.7 filed Oct. 4, 2002 (2 pp.).30Takashima, et al., "Dynamic Traffic Engineering: Creating New Services" 4th Asia-Pacific Symposium on Information and Telecommunication Technologies, Nov. 5, 2001.31Wantanbe, Y., Jul. 29, 2008 Office Action from Japanese Patent Application No. 582224-2003 filed Oct. 4, 2002 (17 pp.).32Watanabe, Y., May 7, 2008 Office Action from Japanese Patent Application No. 582224/2003 filed Oct. 4, 2002 (5 pp.).33Yamada, et al., "Dynamic Traffic Engineering for Network Optimization-Architecture and Evaluation" The 6th Asia-Pacific Network Operations and Management Symposium, Sep. 25, 2002.Referenced byCiting PatentFiling datePublication dateApplicantTitleUS20120300623 *Mar 15, 2011Nov 29, 2012Nec CorporationLoad balance control unit, load balance control method and storage mediumUS20130208599 *Jan 23, 2013Aug 15, 2013Hitachi, Ltd.Transmission system, managing computer, and logical path construction method* Cited by examinerClassifications U.S. Classification370/237, 709/235, 370/395.43International ClassificationH04L12/28, H04L12/56Cooperative ClassificationH04L47/10European ClassificationH04L47/10Legal EventsDateCodeEventDescriptionMar 8, 2013FPAYFee paymentYear of fee payment: 4Oct 7, 2009ASAssignmentOwner name: FUJITSU LIMITED, JAPANFree format text: CORRECTIVE ASSIGNMENT TO CORRECT THE EXECUTION DATES OF INVENTORS ONE THROUGH EIGHT. NAMES OF SECOND AND EIGTH INVENTOR PREVIOUSLY RECORDED ON REEL 014954 FRAME 0055;ASSIGNORS:OKAMURA, AKIKO;NAKAMICHI, KOJI;YAMADA, HITOSHI;AND OTHERS;REEL/FRAME:023344/0771;SIGNING DATES FROM 20040123 TO 20040202Jan 30, 2004ASAssignmentOwner name: FUJITSU LIMITED, JAPANFree format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNORS:OKAMURA, AKIKO;NAKAMACHI, KOJI;YAMADA, HITOSHI;AND OTHERS;REEL/FRAME:014954/0055;SIGNING DATES FROM 20031222 TO 20031225RotateOriginal ImageGoogle Home - Sitemap - USPTO Bulk Downloads - Privacy Policy - Terms of Service - About Google Patents - Send FeedbackData provided by IFI CLAIMS Patent Services