METHOD AND APPARATUS FOR FAIR FLOW CONTROL AND CONGESTION AVOIDANCE SUPPORTING MULTIPLE QOS CLASS REQUIREMENTS
First Claim
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, andif 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, andif 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, andif 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, andif 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 byadding 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.
0 Assignments
0 Petitions
Accused Products
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.
-
Citations
7 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
byupdating 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
byupdating 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
byupdating 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; andprocessing 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
byremoving 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. - View Dependent Claims (3, 7)
-
-
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, thena 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; andthe 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.
-
Specification