System for managing flow bandwidth utilization at network, transport and application layers in store and forward network

• US 6,046,980 A
• Filed: 11/24/1997
• Issued: 04/04/2000
• Est. Priority Date: 12/09/1996
• Status: Expired due to Term

• Current Assignee: Gen Digital Inc.
• Original Assignee: Packeteer Incorporated (Gen Digital Inc.)
• Inventors: Packer, Robert L.
• Primary Examiner(s): Patel, Ajit
• Assistant Examiner(s): Pizarro, Ricardo M.
• Application Number:
  US08/977,642
• Time in Patent Office: 862 Days
• Field of Search: 370/229, 370/230, 370/231, 370/232, 370/235, 370/465, 370/466, 370/468
• US Class Current: 370/230
• CPC Class Codes: H04L 41/0213 Standardised network management protocols, e.g. simple network management protocol [SNMP]
• CPC Class Codes: H04L 41/0893 Assignment of logical groups to network elements
• CPC Class Codes: H04L 41/0894 Policy-based network configuration management
• CPC Class Codes: H04L 41/0896 Bandwidth or capacity management, i.e. automatically increasing or decreasing capacities flow or congestion control using dynamic resource allocation, e.g. in-call renegotiation, H04L47/76
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/193 at the transport layer, e.g. TCP related
• CPC Class Codes: H04L 47/225 Determination of shaping rate, e.g. using a moving window
• CPC Class Codes: H04L 47/2441 relying on flow classification, e.g. using integrated services [IntServ]
• CPC Class Codes: H04L 47/263 Rate modification at the source after receiving feedback
• CPC Class Codes: H04L 69/16 Implementation or adaptation of Internet protocol [IP], of transmission control protocol [TCP] or of user datagram protocol [UDP]
• CPC Class Codes: H04L 69/163 In-band adaptation of TCP data exchange; In-band control procedures

Abstract

In a packet communication environment, a method is provided for classifying packet network flows for use in determining a policy, or rule of assignment of a service level, and enforcing that policy by direct rate control. The method comprises applying individual instances of traffic objects, i.e., packet network flows to a classification model based on selectable information obtained from a plurality of layers of a multi-layered communication protocol, then mapping the flow to the defined traffic classes, which are arbitrarily assignable by an offline manager which creates the classification. It is useful to note that the classification need not be a complete enumeration of the possible traffic.

Claims

1. A method for allocating bandwidth in a packet telecommunication system having any number of flows, including zero using a classification paradigm comprising the steps of:

parsing a packet into a flow specification, wherein said flow specification contains one or more instances of any of the following;

a protocol family designation,

a direction of packet flow designation,

a protocol type designation,

a plurality of hosts,

a plurality of ports,

in http protocol packets, a pointer to a URL;

thereupon,

matching the flow specification of the parsing step to a plurality of hierarchically-recognized classes represented by a plurality of nodes, each node having a traffic specification and a mask, according to the mask;

thereupon,

having found a matching node in the matching step, associating said flow specification with one of said plurality of hierarchically-recognized classes represented by a plurality nodes; and

allocating bandwidth resources according to a policy associated with said class by allocating a combination of GIR resources, EIR resources and unreserved resources based upon speed scaling and unreserved resources are allocated based upon a priority, including

detecting speed of a network link upon which said flow is transported to obtain a network link speed;

allocating available bandwidth resources based upon the speed detected.

2. A method for allocating bandwidth in a packet telecommunication system having any number of flows, including zero, using a classification paradigm comprising the steps of:

parsing a packet into a flow specification, wherein said flow specification contains one or more instances of any of the following;

a protocol family designation,

a direction of packet flow designation,

a protocol type designation,

a plurality of hosts,

a plurality of ports,

in http protocol packets, a pointer to a URL;

thereupon,

matching the flow specification of the parsing step to a plurality of hierarchically-recognized classes represented by a plurality of nodes, each node having a traffic specification and a mask, according to the mask, thereupon,

having found a matching node in the matching step, associating said flow specification with one of said plurality of hierarchically-recognized classes represented by a plurality nodes; and

allocating bandwidth resources according to a policy associated with said class by allocating a combination of GIR resources, EIR resources and unreserved resources based upon speed scaling and unreserved resources are allocated based upon a priority,

wherein said allocating of unreserved resources to a particular flow, said flow having an input rate, said flow being one of said plurality of flows, based upon a priority, further comprises the steps of;

extrapolating from said input rate of said network link speed detecting step an extrapolated unreserved demand (EUD);

aggregating together a plurality of individual flow demands to form an aggregate rate demand (ARD);

combining said EUD and said ARD to form an instantaneous total demand;

allocating available bandwidth resources based upon instantaneous total demand determined in the combining step from highest priority demand first to lower priority demanded to yield a satisfaction percentage of demand;

determining a target rate for individual flows by multiplying said individual flow demand for each flow by said satisfaction percentage of demand determined in the allocating step.

3. The method of claim 2 wherein said unreserved resources comprise a plurality of individual inputs, each input having a priority, further comprising the step of:

determining a target rate for said inputs according to said priority by multiplying said extrapolated unreserved demand by said satisfaction percentage of demand determined in the allocating step.

4. A method for allocating bandwidth in a packet telecommunication system having any number of flows, including zero, using a classification paradigm comprising the steps of:

parsing a packet into a flow specification, wherein said flow specification contains one or more instances of any of the following;

a protocol family designation,

a direction of packet flow designation,

a protocol type designation,

a plurality of hosts,

a plurality of ports,

in http protocol packets, a pointer to a URL;

thereupon,

matching the flow specification of the parsing step to a plurality of hierarchically-recognized classes represented by a plurality of nodes, each node having a traffic specification and a mask, according to the mask;

thereupon,

having found a matching node in the matching step, associating said flow specification with one of said plurality of hierarchically-recognized classes represented by a plurality nodes;

allocating bandwidth resources according to a policy associated with said class; and

determining that if guaranteed information rate resources are insufficient to accommodate said flow, invoking an admissions policy.

13. The method of claim 4 wherein a node may have one or many traffic specifications.

14. The method of claim 4 wherein said plurality of hierarchically-recognized classes represents a plurality of orthogonal flow attributes.

15. The method of claim 4 wherein allocating bandwidth resources further comprises the steps of:

for rate based policies having a guaranteed information rate (GIR) and an excess information rate (EIR), allocating GIR until no further GIR is available;

thereupon, allocating EIR,

for priority based policies, having a priority, allocating unreserved service according to said priority.

5. A method for allocating network bandwidth, which bandwidth comprises guaranteed information rate (GIR) resources, excess information rate (EIR) resources and unreserved rate resources, on Internet Protocol (IP) flows in a packet communication environment allocated into layers, including at least a transport layer, a link layer and an application layer, said method comprising:

automatically detecting selectable information about said flow;

determining a policy for assigning a service level to said flow based upon said automatically detected selectable information about said flow, said policy directing either reserved service or unreserved service;

dynamically allocating said bandwidth representing a combination of GIR resources and EIR resources based upon speed scaling and allocating unreserved resources based upon a priority among a plurality of flows assigned to said service level by said determining step;

wherein allocating said unreserved resources based upon a priority to a plurality of flows, each having an input rate, further comprises the steps of;

detecting input rate of a flow;

extrapolating from said input rate of the detecting step an extrapolated unreserved demand (EUD);

aggregating together a plurality of individual flow demands to form an aggregate rate demand (ARD);

combining said EUD and said ARD to form an instantaneous total demand;

allocating available bandwidth resources based upon the instantaneous total demand determined in the combining step from highest priority demand first to lower priority demanded to yield a satisfaction percentage of demand;

determining a target rate for individual flows by multiplying said individual flow demand for each flow by said satisfaction percentage of demand determined in the allocating step.

6. (Amended) The method of claim 5 wherein said unreserved resources comprise a plurality of individual inputs, each input having a priority, further comprising the step of:

determining a target rate for said inputs units according to said priority by multiplying said extrapolated unreserved demand by said satisfaction percentage of demand determined in the allocating step.

7. A method for allocating network bandwidth, which bandwidth comprises guaranteed information rate (GIR) resources, excess information rate (EIR) resources and unreserved rate resources, on Internet Protocol (IP) flows in a packet communication environment allocated into layers, including at least a transport layer, a link layer and an application layer, said method comprising:

automatically detecting selectable information about said flow;

determining a policy for assigning a service level to said flow based upon said automatically detected selectable information about said flow, said policy directing either reserved service or unreserved service;

dynamically allocating said bandwidth representing a combination of GIR resources and EIR resources and unreserved among a plurality of flows assigned to said service level by said determining step;

determining that if guaranteed bandwidth available is insufficient to accommodate said flow, invoking an admissions policy.

9. The method of claim 7 wherein said traffic classes have a hierarchical relationship to one another.

8. A method for allocating network bandwidth, which bandwidth comprises guaranteed information rate (GIR) resources, excess information rate (EIR) resources and unreserved rate resources, on Internet Protocol (IP) flows in a packet communication environment allocated into layers, including at least a transport layer, a link layer and an application layer, said method comprising:

automatically detecting selectable information about said flow;

determining a policy for assigning a service level to said flow based upon said automatically detected selectable information about said flow, said policy directing either reserved service or unreserved service, applying individual instances of traffic classes, each traffic class having an associated policy, to said flow based on selectable information; and

dynamically allocating said bandwidth representing a combination of GIR resources and EIR resources and unreserved among a plurality of flows assigned to said service level by said determining step.

17. The method according to claim 8 wherein said policy determining step comprises:

parsing a packet into a flow specification, wherein said flow specification containing one or more instances of any of the following;

a protocol family designation,

a direction of packet flow designation,

a protocol type designation,

a plurality of hosts,

a plurality of ports,

in http protocol packets, a pointer to a URL;

thereupon,

matching the flow specification of the parsing step to a plurality of hierarchically-recognized classes represented by a plurality of nodes, each node having a traffic specification and a mask, according to the mask.

10. A method for allocating network bandwidth, which bandwidth comprises guaranteed information rate (GIR) resources, excess information rate (EIR) resources and unreserved rate resources, on Internet Protocol (IP) flows in a packet communication environment allocated into layers, including at least a transport layer, a link layer and an application layer, said method comprising:

automatically detecting selectable information about said flow;

determining a policy for assigning a service level to said flow based upon said automatically detected selectable information about said flow said policy directing either reserved service or unreserved service;

dynamically allocating said bandwidth representing a combination of GIR resources and EIR resources and unreserved among a plurality of flows assigned to said service level by said determining step; and

allocating said bandwidth representing said unreserved data resources among flows based upon a priority associated with said flows.

11. A method for allocating network bandwidth, which bandwidth comprises guaranteed information rate (GIR) resources, excess information rate (EIR) resources and unreserved rate resources on Internet Protocol (IP) flows in a packet communication environment allocated into layers, including at least a transport layer, a link layer and an application layer, said method comprising:

automatically detecting selectable information about said flow;

determining a policy for assigning a service level to said flow based upon said automatically detected selectable information about said flow, said policy directing either reserved service or unreserved service;

dynamically allocating said bandwidth representing a combination of GIR resources and EIR resources and unreserved among a plurality of flows assigned to said service level by said determining step; and

applying a partition to one or more classes, said partition having a limit on aggregate data rate flow.

12. The method of claim 11 wherein said limit is a soft partition limiting EIR for one or more classes.

16. The method according to claim 11, further including steps of stepwise mapping of policies according to association with nodes classified in a hierarchy.