METHOD AND APPARATUS FOR FAIR FLOW CONTROL AND CONGESTION AVOIDANCE SUPPORTING MULTIPLE QOS CLASS REQUIREMENTS

• US 20070280245A1
• Filed: 12/10/2006
• Published: 12/06/2007
• Est. Priority Date: 05/31/2006
• Status: Active Grant

• Current Assignee: Zvi Rosberg
• Original Assignee: Zvi Rosberg
• Inventors: Rosberg, Zvi
• Granted Patent: US 7,729,347 B2
• Time in Patent Office: Days
• US Class Current: 370/392
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/22 Traffic shaping
• CPC Class Codes: H04L 47/2408 for supporting different services, e.g. a differentiated services [DiffServ] type of service
• CPC Class Codes: H04L 47/2416 Real-time traffic
• 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 47/27 Evaluation or update of window size, e.g. using information derived from acknowledged [ACK] packets
• CPC Class Codes: H04L 47/283 in response to processing delays, e.g. caused by jitter or round trip time [RTT]
• CPC Class Codes: H04L 47/33 using forward notification

Abstract

For communication networks comprising user devices, edge routers, core routers, access and core links, a specification is given for a novel method and apparatus computing and allocating fair transmission rates to user data flows from a plurality of quality of service levels. The fair rates satisfy the minimum transmission rates, the end-to-end delays and the data loss rates required by each flow and also avoid network congestion. The method comprises: an edge router process and a flow control shaper for each edge router and a core router process for each edge and core router. All processes are executed in a distributed and asynchronous manner, are stable and converge to the desired fair rates. Each flow shaper process shapes the transmission rates based on local measurements driving them to the desired fair rates. The processes are efficient and lend themselves into ASIC and network processor unit implementations.

Claims

1. In a non-degenerated backbone network transmitting flows from a plurality of QoS levels that are determined either at the source edge router process or specified in the data packet header, a method in an edge router process for classifying into flows every data packet arriving at the source edge router process from an end user device through its access link, updating the current list of active flows in the source edge router based on flow activities and possibly transmitting Type I-1 and Type I-2 forward RMP packets, the method comprising the steps of:

checking a local interval timer, and

if the timer has expired, terminating the classification and updating process without taking any further steps;

if the timer has not expired,

 

setting the timer again to a predefined positive value, which can also be extremely large, and continuing the classification and updating with the following steps;

setting a wildcard symbol in the identifier of the output link (denoted by out_port) through which the packet will be switched out by the edge router, and

if the actual output link identifier can be retrieved from the edge router, setting it to the out_portvariable; and

scanning a local data structure, which maintains the active flows (denoted by Active_Flow_DS), for determining if the data packet matches an active flow characterized by the packet source IP address header field, or alternatively by a unique representative IP address in the network numberof the packet source IP address, and also by the packet destination IP address header field, or alternatively by a unique representative IP address in the network number of the packet destination IP address, and also by the packet TOS header field, and if out_port is retrieved, then also by the out_port value; and

comparing between the flow characteristics of each scanned flow in Active_Flow_DS and that of the arriving data packet, and

if the data packet matches an active flow in Active_Flow_DS, the current local time is set to a designated field (denoted by Modified) associated with the matching flow;

if the data packet does not match an active flow in Active_Flow_DS, the flow is checked for staleness by subtracting its Modified value from the current local time, and

if the result is greater than a predefined time period, then removing the flow from Active_Flow_DS; and

if the flow is also of Type I, transmitting a Type I-2 forward RMP packet toward the flow destination using a reliable protocol; and

completing the scanning by

adding a new flow to Active_Flow_DS with the characteristics of the arriving data packet, if no match is found; and

transmitting a normal Type I-1 forward RMP packet toward the flow destination using a reliable protocol, if the flow is of Type I and no match is found.

2. In a non-degenerated backbone network transmitting flows from a plurality of QoS levels that are determined either at the source edge router process or specified in the data packet header, a method in an edge router process for admitting new flows and updating all or any subset of the following variables for each active flow in the source edge router, the variables being the current packet round trip time estimator (denoted by F_RTT), the current packet loss rate estimator (denoted by LOSS_R), the current fair transmission rate of a flow without minimum transmission rate requirement (denoted by F_RATE) and the current window size (denoted by WIN) utilized for window flow control, the method comprising steps of:

generating periodically Type II forward RMP packets for every active flow, each packet includes the flow identification, the QoS and priority levels, the requested minimum rate, the difference between the current and the previous transmission rates, the packet sequence number and a request to revise the link utilization upper bound; and

transmitting, and at the same time starting an interval timer, each forward RMP packet toward its destination where it is intercepted by the corresponding destination edge router process and sent back to its originating edge router process as backward RMP packet; and

processing every return of a Type II backward RMP packet by

updating the estimator F_RTT of the respective flow with

 

C×

P_F_RTT+(1−

C)×

RTT, where P_F_RTT is the previous estimator value, C is a predefined constant between zero and one and RTT is the value of the corresponding interval timer; and

by

updating the estimator LOSS_R of the respective flow with

 

CL×

P_LOSS_R+(1−

CL)×

Losses/(1+Losses), where P_LOSS_R is the previous estimator, 1+Losses is the difference between the sequence numbers (denoted by SEQ#) of the currently returned and the previously returned backward RMP packets from the same flow and CL is a predefined constant between zero and one; and

by

updating the fair transmission rate F_RATE, if the respective flow has no minimum transmission rate requirement, with (W/FB)^1/FL, where W is the weight associated with the respective flow, FB is the feedback information in the currently returned backward RMP packet and FL is a constant equals to or larger than one specifying the fairness level parameter utilized by the backbone network; and

by

updating the window size, WIN, utilized for window flow control of the respective flow, with max {min {CW×

P_WIN+(1−

CW)×

F_RTT×

F_RATE;

WIN_UB};

WIN_LB}, where F_RTT is the current estimated packet round trip time of the respective flow, F_RATE is the current required transmission rate of the respective flow, P_WIN is the previous window size, CW is a predefined constant between zero and one, and both, WIN_UB and WIN_LB, are predefined upper and lower bounds on the window size, respectively; and

processing every return of a Type I-1 backward RMP packet by

admitting the respective flow to the network and transmitting a commit Type I-1 forward RMP packet, if the designated feedback information field of the RMP packet indicates flow admission; and

by

removing the respective flow from the local active flow list, if the designated feedback information field of the RMP packet indicates flow rejection; and

processing every return of a Type I-2 backward RMP packet by disposing it.

3. The method as set forth in claim 2, before transmitting each forward RMP packet for an active flow, further verifying whether or not the end-to-end packet delay and the end-to-end packet loss rate conform to the flow QoS requirements and requesting an appropriate update from the core router processes so as to address the flow QoS requirements, the method further comprising the steps of:

checking the locations of the estimated packet round trip time, F_RTT, and the estimated packet loss rate, LOSS_R, of the respective flow, relative to two corresponding confidence intervals, one of which is around the pre-specified packet delay requirement and the other of which is around the packet loss rate requirement of the respective flow; and

if both, F_RTT and LOSS_R, are within their corresponding confidence intervals, a designated field in the RMP packet (denoted by UTIL_REV) is set to indicate the core router processes that no update of the respective link utilization is required;

if F_RTT or LOSS_R is greater than the right edge of the corresponding confidence interval, then UTIL_REV is set to indicate the core router processes that they should reduce the respective link utilization while computing their feedback information;

if both, F_RTT and LOSS_R, are smaller than the left edge of each corresponding confidence interval, then UTIL_REV is set to indicate the core router processes that they could increase the respective link utilization while computing the feedback information.

7. In a non-degenerated backbone network transmitting flows from a plurality of QoS levels that are determined either at the source edge router process or specified in the data packet header, a method for shaping the transmission rate of each active flow in every source edge router process and in every transport layer application in the end user device so as to meet the flow target rate, the method utilizing a window flow control wherein the window size, WIN, is established by the steps of claim 2.

4. In a non-degenerated backbone network transmitting flows from a plurality of QoS levels that are determined either at the source edge router process or specified in the data packet header, a method in a core router process for updating upon every forward RMP packet arrival all or any subset of the following variables associated with each output core link (denoted by n) and scheduling priority level (denote by p), the variables being the feedback information contributed by the core router process for link n and priority p (denoted by FB(p,n)), the reserved bandwidth in link n for Type I flows with priority p (denoted by RES(p,n)) and the bandwidth in link n utilized by Type II flows with priority p or with higher priority (denoted by RATE(p,n)), the method comprising steps of:

retrieving, explicitly from the core router, or implicitly from the incoming port, the output link identifier through which the RMP packet will be switched out downward its destination and setting it to variable n; and

extracting the priority level from a designated field of the RMP packet and setting it to variable p; and

extracting from the local data structure (denoted by Flow_LINK_DS), the capacity of link n, the total reserved rate in link n for flows of Type I, and the upper bound on the utilization of link n set for packets with the same scheduling priority as p or with higher priority, and setting them to variables c, r and u, respectively; and

checking the type of the forward RMP packet; and

if the RMP packet is a normal Type I-1 and the requested minimum transmission rate is less than c×

u−

r, then

a logical AND between one and the designated feedback information field in the RMP packet is set into the latter indicating that link n can accommodate the new flow; and

the reserved rate in link n for flows of Type I having priority level p in Flow_LINK_DS, RES(p,n), is conditionally incremented by the requested rate of the respective new flow taken from a designated field of the RMP packet;

if the RMP packet is a normal Type I-1 and the requested minimum transmission rate is not less than c×

u−

r, then a logical AND between zero and the designated feedback information field of the RMP packet is set into the latter indicating that link n cannot accommodate the new flow;

if the RMP packet is a commit Type I-1, then the respective reservation is committed;

if the RMP packet is of Type I-2, then the reserved rate in link n for flows of Type I having priority level p in Flow_LINK_DS, RES(p,n), is decremented by the rate reserved for the respective non-active flow taken from a designated field of the RMP packet;

if the RMP packet is of Type II and also associated with a flow of Type II, then the variable RATE(p,n) in the local Flow_LINK_DS data structure is updated with the rate difference taken from a designated field of the RMP packet; and

the contribution to the feedback information for link n and priority p is computed by pos {P_FB(p,n)+C×

(Rate(p,n)−

f((c−

r)×

u))}, where P_FB(p,n) is the feedback information computed in the previous update of the variables associated with output link n and priority p, C is a predefined positive tuning constant, Rate(p,n) is the sum of all current packet transmission rates associated with flows having priority level p or higher priority and are traversing through output link n as retrieved from the local Flow_LINK_DS data structure, f(rc) could be any quantized implementation of a continuous and strictly increasing non-negative function of rc satisfying f(0)=0, pos{x} is the non-negative part of the variable x and rc is given by (c−

r)×

u; and

the computed feedback information contribution is added to the designated feedback information field of the RMP packet and also updates the local Flow_LINK_DS data structure.

5. The method as set forth in, before extracting from Flow_LINK_DS the data required for the setting of the variables c, r and u, in the case of forward RMP packets of Type II, further updating the utilization upper bound on each link n and priority p (denoted by bw_util(p,n)), the method further comprising the steps of:

checking a local interval timer, and

if the timer has been expired, the updating aborts and no further steps are taken;

if the timer has not been expired,

the timer is set again to a predefined positive value which can also be extremely large, and the updating proceeds with the following steps;

checking the value of a designated field in the forward RMP packet (denoted by UTIL_REV) carrying the update request, and

if UTIL_REV equals one, then bw_util(p,n) is decremented by a predefined positive constant while preserving consistency between all variables bw_util(1,n), bw_util(2,n), . . . , bw_util(P,n), where P is the number of supported priority levels;

if UTIL_REV is negative, then bw_util(p,n) is incremented by a predefined positive constant while preserving consistency between all variables bw_util(1,n), bw_util(2,n), . . . , bw_util(P,n), where P is the number of supported priority levels;

if UTIL_REV equals zero, then no variables are updated.

6. In a non-degenerated backbone network transmitting flows from a plurality of QoS levels that are determined either at the source edge router process or specified in the data packet header, a method for admitting new flows of Type I and computing the transmission rate of every flow of Type II so as to meet the QoS requirements of all active flows and at the same time achieving fair allocation of rate, comprising the steps of:

classifying the data packets arriving to each source edge router process from the end user devices through their access links into flows; and

determining the active flows in each source edge router process based on each flow activity; and

generating a normal Type I-1 forward RMP packet for each new flow of Type I; and

generating a commit Type I-1 forward RMP packet for each new flow of Type I that has been admitted to the network; and

generating a Type I-2 forward RMP packet for each flow of Type I that ceases to be active; and

generating periodically Type II forward RMP packets for each active flow in every source edge router process, each packet includes the flow identification, the QoS and priority levels, the requested minimum rate, the difference between the current and the previous transmission rates, the packet sequence number, the feedback information, and a request to revise the link utilization upper bound; and

estimating the RTT and the packet loss rate of each active flow in every source edge router process based on RMP packets and checking if both satisfy the QoS requirements of the corresponding flow; and

setting the request to revise the link utilization upper bound in a designated field of the forward RMP packet in accordance to the QoS requirement check; and

transmitting each Type II forward RMP packet to its corresponding destination edge router process and starting an interval timer for RTT timing; and

intercepting forward RMP packets in each destination edge router process and sending them back as backward RMP packets to their corresponding source edge router processes; and

intercepting backward RMP packets in each source edge router process, and based on the information fields carried by each backward RMP packet,

computing the updated transmission rate of the corresponding flow, if the backward RMP packet is of Type II; and

deciding whether or not to admit the corresponding flow into the network, if the backward RMP packet is of Type I-1; and

reading and processing in every core router process each forward RMP packet traversed through it, and based on the information fields it carries,

updating the feedback information in its fields; and

updating in the local data structure the reserved rates of Type I flows, the transmission rates of Type II flows, and the upper bounds on the link utilizations; and

forwarding the forward RMP packet toward its destination.