| Full Text |
FIELD OF TECHNOLOGY
This invention in general relates to the field of wireless multimedia networks. Particularly this invention relates to the field of dynamic flow control, buffer management and admission control for wireless multimedia networks. More specifically, this invention relates to a system and method for dynamic flow control and buffer management in wireless multimedia networks
DESCRIPTION OF RELATED ART
Referring to FIG. 1 where data packets for fooA/ard link flows are sent from correspondent node (ON), through base station, to mobile stations (MS) in a wireless multimedia network which consists of the base station controller (BSC), base transceiver station (BTS), point coordination function (PCF), wireless edge router (WER) and the correspondent node (CN). An IP networking architecture for this type of networks is described in www.3qpp2.org: 3GPP2P.S0001B, "Wireless IP standard".
In a 3G wireless network. BTS serves packets over the air-link for mobile stations. BTS is connected to the BSC using a wireline link and memory at the BTS is usually much smaller than at the BSC. The BSC gets IP packets, fragments those to MAC packets and sends those to BTS. In a 3G network, time is typically divided into fixed length time slots. Each mobile station (MS) informs the base station about the rate at which it can accept data in each of the slots on fonvard link. This rate can vary rapidly in a wide-area wireless network. This maximum allowed rate, is specified via two parameters: number of bytes in physical layer packet that can be sent over the air-interface starting from this slot n and the number of slots that would be taken by this packet. There is a scheduler at the BTS which schedules these packets over the air for mobile stations. In this case, if mobile k is selected to be served via the fonA/ard link scheduler and the mobile has specified that it would need more than one slot for transmission, then it would be served for the specified number of slots (or until
the physical layer packet transmission is over or whichever occurs earlier). Some data rates for a CDMA2000 system are shown in the table 1 below.
There are other types of cellular wireless networks such as wireless local area networks (WLANs). A schematic diagram of a WLAN network is shown in Figure 2, Here, MS is a mobile station wirelessly connected to the access point AP. Each AP provides connectivity to a set of mobile stations called a basic service set (BSS) in IEEE 802.11 parlance. In a BSS, mobile stations are controlled by an access point (AP) that decides when a mobile station can transmit or receive data packets. Multiple APs can be connected to each other using a wired or wireless backbone (distribution system) resulting in a WLAN with extended reach. This is called an extended service set (ESS) in the IEEE 802,11 parlance. One ESS has one 32-octet long service set identifier (SSID). Each BSS has a 6-octet long basic service set identifier (BSSID) which is same as the MAC address of radio in the access point. The manner in which air-link resources are allocated to different mobile users and their applications over the air interface in a wireless network, determines the performance of different applications and utilization of network resources. For this purpose, one needs to have efficient traffic scheduling mechanisms to control traffic flows in both directions over the air interface.
In a 3G or WLAN network, it can happen that a mobile stations MSz has large number of MAC packets accumulated for one or more of its flows at the AP (i.e.
BTS in a 3G networl
In such situations, if one stores some of these packets at an upstream node (like the BSC in 3G network or an upstream node such as an aggregator (Aggregator aggregates traffic coming from several WLAN APs) in a WLAN network as shown in Figure 3) for some more time (before sending those to the 3G-BTS or WLAN-AP), one can reduce number of packets dropped at the AP and improve application performance. For this purpose, there is a need to have an effective buffer management mechanism at the AP (3G-BTS or WLAN-AP) and a flow control mechanism between the 3G-BTS and the 3G-BSC in 3G networks (similarly between WLAN-AP and an upstream aggregator in WLAN networks). Each application also has certain quality of service requirements which could include some of the following: delay bound, delay jitter, average delay, throughput and packet loss. The buffer management, flow control and admission control mechanisms should be such that they don't violate quality of service requirements of applications.
LIMITATIONS
As explained above, there is need to have an effective buffer management mechanism in the BTS in 3G network and a dynamic flow control mechanism between the BTS and the BSC. Similarly, such effective mechanisms are needed for flow control between WLAN access point and WLAN aggregator in a WLAN network. Similarly, such methods are also needed in 3G-WLAN
integrated network and in other types of cellular wireless networks. Presently most of the methods tend to be of static nature and there are no such methods having dynamic flow control and buffer management for cellular networks as described here in this invention. As channel conditions in wireless networks can change very rapidly and some of the data applications also have busy traffic, static methods are not very effective and can result in violation of quality of service constraints of applications and poor utilization of a wireless network.
OBJECTS OF THE INVENTION
The primary object of invention is to invent a system and method for dynamic buffer management and dynamic flow control in cellular multimedia systems which is novel and unique.
It is another object of invention to invent a method for the different class of application for which dynamic flow controls are required in cellular wireless systems.
It is another object of invention to invent a method for dynamic buffer allocation and management for different classes of applications for the cellular wireless systems.
It is another object of invention to invent a method for dynamic admission control for different classes of applications for cellular wireless networks.
It is another object of invention to invent a method wherein the limitation of having static flow control and static buffer management for multimedia wireless applications in cellular wireless systems are overcome.
SUMMARY OF THE INVENTION:
In this invention a system and methods are proposed for having a dynamic flow control, dynamic buffer management and admission control for a cellular wireless network where there are heterogeneous applications (such as VoIP, multimedia conferencing, video streaming, wireless games etc.) with different quality of service requirements. Real-time applications such as multimedia conferencing and streaming have stringent requirements on delay bound and delay jitter. In addition, they also have requirements on minimum throughput and packet loss. In cellular wireless networks, channel conditions can change rapidly and that has impact on the performance of these applications. The methods invented here work to improve the network utilization and reduce the probability of quality of service violation of applications.
Accordingly this invention further relates to a method for dynamic flow control, buffer management and admission control for cellular wireless multimedia networks such as 3G, WLAN or integrated 3G-WLAN system implemented using plurality of mechanisms wherein the said method comprising the steps of -deciding whether or not to admit a new flow in the cellular network by an adaptive admission control mechanism, - assigning a fixed amount of buffer initially depending upon its traffic characteristics and QoS requirements for each admitted flow, - computing dynamically maximum allowable buffer for each flow k belonging to quality of service class J at time t, buff _max_flow{k, Jj), taking
into account network conditions such as quality of service violation for each flow, quality of service class, channel conditions of mobile devices and network load, -pre-specifying minimum number of flows for each quality of service class J,
AT™", that can be admitted in the system and minimum amount of buffer,
buff_res_min is kept reserved for these flows, - allocating a common buffer
pool, buff ^common, wherein it is allocated and set equal to the total buffer pool
{buff_ap) minus the minimum amount of reserved buffer for all quality of
service classes {buff_res_mm), - allocating buffer space equal to
buff _mn_flow{h,J) for each new flow h corresponding to class J, if admitted in
the system, allocating buffer space for new flows belonging to some class J using common buffer pool, buff ^common, for which number of admitted flows
have already exceeded their minimum reserved quota, i.e. iV7", and for each
admitted flow h corresponding to class J for which current queue depth already exceeds its minimum reserved buffer quota, buff _mm_flow{h,J), - computing
the maximum number of MAC packets, n{k,Jj), to be admitted at the access
point, in that a maximum of n(k,Jj) MAC packets are admitted to the access
point by considering the flows which have already been admitted in the system, -dynamically deciding the action to be taken by a flow control message, which is sent from the access point to the upstream node and on receipt of the flow control message for such a flow k, the upstream regulates flow of packets to the access point for such flows.
Accordingly this invention further relates to a system for dynamic flow control, buffer management and admission control for cellular wireless multimedia networks particularly 3G-WLAN internetworking system comprising, - means for assigning each flow an amount of fixed buffer initially depending upon its traffic characteristics and QoS requirements, - means for computing dynamically maximum allowable buffer for each flow, - means for allocating common buffer pool, - means for admitting and allocating buffer space for each flow, and means for sending a flow control message for each flow from the access node to the upstream node and controlling of flow of packets for each flow.
The other objects, features and advantages of the present invention will become more apparent from the ensuing detailed description of the invention taken in conjunction with the accompanying drawings.
BRIEF DESCRIPTION OF THE ACCOMPANYING DRAWINGS
Figure 1 shows a 3G wireless network comprising of mobile station (MS), Base transceiver system (BTS), Base station controller (BSC) and correspondent node (CN).
Figure 2 shows a WLAN network with access point (AP) and mobile station (MS).
Figure 3 shows a WLAN network with access point (AP) and upstream aggregator. Aggregator aggregates traffic coming from several WLAN APs.
Figure 4 shows the allocated buffer for flow k corresponding to class J. Here, buff_min_flow(k,J) is the minimum required buffer for flow k corresponding to class J, and buff_max_flow(k,J,t) is the maximum allowable buffer for flow k corresponding to class J at time t.
Figure 5 shows the buffer management for mechanism I.
Figure 6 shows the minimum amount of reserved buffer for different classes for mechanism I.
Figure 7 shows the excess buffer reserved at time (t) in mechanism I.
Figure 8 shows the unreserved buffer at any time instance (t) in mechanism I.-
Figure 9 shows the minimum reserved buffer and maximum allowable buffer for any flow of class J in mechanism II.
Figure 10 shows the buffer management used in mechanism II.
DETAILED DESCRIPTION OF THE INVENTION
In many types of wireless networks, IP packets are segmented to MAC packets before they are transmitted over the air by the access point towards mobile
devices. For the purpose of the flow control, buffer management and admission control mechanisms invented in this document, we classify flows as follows:
Class 1: For flows such as voice (VoIP) that have very stringent requirements over delay bound and jitter. These flows may also specify their required rate.
Class 2: For flows such as video conferencing that have stringent requirements over delay bound and jitter. Some of these flows may also specify their required rate as well as desired rate.
Class 3: For flows such as video streaming that have requirements over delay bound, jitter and rate but which are more relaxed when compared to flows which belong to Class 1 or 2.
Class 4: For flows which have requirements over average delay and rate (like web browsing) or only on rate (like FTP applications).
Class 5: Flows which have no QoS requirements (called best effort flows).
Mechanism I: Dynamic Buffer Management, Flow Control and Admission Control
The dynamic buffer management, flow control and admission control mechanisms invented here work as follows.
Step A:
Each flow is assigned some amount of fixed buffer initially which depends upon its traffic characteristics and QoS requirements. Let buff _min_ flow{k, J) be this
fixed amount of buffer allocated to flow k of class J. Here, buff_m\n_flow(k,J) = buff_m\n_flowip,J)==buff_min{J) for two different flows
k and p belonging to the same class J.
step B - Dynamic Computation of Maximum Allowable Buffer for Each Flow:
Let A^7" be the minimum number of flows that are allowed corresponding to class J at the access point. Let num_flows{Jj) be the number of flows
corresponding to class J that is present in the system (i.e. at the access point) at time t.
For each flow k corresponding to class J, maximum number of MAC packets that are allowed to be stored at time t at the access point, buff _max_flowik,J,t), is
computed dynamically. Note that buff_max_flow(k,J,t) is a function of flow
identifier, flow type and time. This is shown in Figure 4. It is quite possible that buff_msoi_flow(k,Jj)^buff_max_flow{p,Jj) for two different flows, k and p,
belonging to the same class J. It is also possible that
buff_meix_flow(k,Jj^)^buff_max_flow(k,Jj2) for two time instants t^ and ^2
such that ti i^t^ for same flow k. Computation of buff _m3x_flow(k,J,t) takes
into account channel conditions for mobile stations, traffic characteristics and QoS requirements for flow k.
Dynamic computation of buff_max_flow(k,Jj)\s done as follows. Let
arr_rate{k,J) be the pre-specified average arrival rate of flow k belonging to
class J. This average arrival rate is specified as part of traffic profile of this flow. In some wireless networking systems (such as 3G wireless networks), each mobile station informs the access point (base station) the rate at which the access point can send data to that mobile station at that time instant (or in that slot in a discrete time wireless system). Let A[k,n\be the rate indicated by the
mobile station corresponding to flow k in the time slot n (considering a discrete
time wireless system), and A{k,n) be its exponentially weighted moving average
1 1
where A{k,n) =—A[k,n\-\-{\—)A{k,n-\). Here, a time constant t^ is chosen such that 0
allowed to be stored for flow k belonging to class J, at time t, at the access point is calculated as follows:
Here, buff^ap, is the total buffer pool at the AP, buff_res_min is the minimum
amount of reserved buffer at the AP, and buff^common is the remaining amount
of common buffer which is used to allocate space for new flows as well as for
admitted flows after they have used up their minimum reserved buffer space.
For each flow k belonging to some class J, a positive threshold,
buff _ max_ thres{k, J) is specified such that
buff _ niax_ flow{k, J, t)
Here, ^„,ax(-'0 = maXp{^(/?,0}. considering flows (corresponding to class J=1, 2, 3 or 4) for all mobile stations which are present in the system at time t, and A{k,t) is computed for each flow k starting from the time when that flow session was established in the system.
Minimum of average arrival rate, arr_rate^^^{,,J) = m\nimump{arr_rate{p,J)},
considering each flow p corresponding to class J=1, 2, 3 or 4 which is present in the system at time t.
For each flow k belonging to some class J, p^^ys are chosen such that p,^j > 0,
Let qdepth{k,J,t) be the number of MAC packets stored at the access point for flow k corresponding to class J at time t.
Step C - Buffer Management:
A common buffer pool, buff ^common, is allocated and it is used for two
purposes. First, to store packets of a flow when it has already used its minimum fixed quota, (i.e. to store packets for each flow k for each class J when it has used its minimum allocated quota buff _min_flow(k,J)). Second, to allocate
buffer space for new flows of a class J when number of flows present in the system for that class has already exceeded A^7". Thus, if
mm_flows{J,t) = A^7" and if a new flow h corresponding to class J appears in the system, it could be allocated buffer space equal to buff _n\m_flow{h,J) if that space is available in the common buffer pool, buff ^common. Let buff _res_m\n_class{J) be the minimum amount of buffer reserved for flows belonging to class J. Refer to Figure 5. Following is always ensured:
specified maximum number of flows that are to be admitted in the system corresponding to class J.
StepD - (Flow) Admission Control:
If a new flow h corresponding to class J appears in the system, it could be admitted and allocated buffer space equal to buff _ min_ flow{h, J) if
num_flows(Jj) N^^ when flow
h corresponding to class J arrives in the system, the new flow h could be admitted and allocated buffer space if buff _m\n_flow{k,J)
at time t. Here,
buff _ unres _ free(t) = buff _ unresit) - buff _ unres _ used{i). Here, buff _unres_used{t), is the amount of buffer which is used by flows for which qdepth{k,Jj)>buff _m\n__flow{k,J), and is given by
num_flows{J,i)
buff _ unres _ used{t) = ^ ^ max{qdepth{k, J, t) - buff __ min_ flow(k, /),0}.
Once this flow h has been admitted in the system, its channel data rate A[h,.] is observed for some slots and buff_meix_flow(k,Jj) is computed using step B.
Step E - Packet Admission:
Now consider the flows which have already been admitted in the system. Suppose, N{kyJj) MAC packets of flow k of class J arrive in the system at time
t. To decide maximum number of MAC packets, n(k,J,t), to be admitted at the
access point, follow the process below.
Let qdepth(k,J,r) be the queue depth of flow k belonging to class J at time r,
where r is a time instant just before time t and no packet arrived in the system between time r and t and no packet left the system between time r and time t. If qdepth(k,J,r)>buff_mdLx_flowik,Jj ), these N(k,J,t) packets are not
admitted in the access point and are stored at the upstream node only (like BSC in a 30 network). On the other hand, if qdepth(k,J,r)
maximum of n{kjj) MAC packets are admitted to the access point which are
computed as below:
max n{k,J,tX
0
qdepth(k, J,t) = qdepth(k, J,r) + n{k, J,/)
N(k, J, t) is a positive integer.
Step F - Flow Control:
1. Consider an arbitrary time t and suppose that /^,,, is the last time before
time t when maximum allowable buffer, buff _m^x_flow{k,J,tp^^^), was
computed for flow k. If it is found that
qdepth{k,J,t)>buff _msiX_flow{k,J,tp^^^), then buff_ma\_flow(k,Jj) iS
recomputed at the time t. If it is still found that qdepth{k,Jj)>buff _md^\_flow{k,J,t ), a flow control message is sent for
this flow k from the access node (like the 3G-BTS or the WLAN-AP) to the upstream node (like the 3G-BSC in a 3G network or WLAN-aggregator in a WLAN network) and control of flow of packets for flow k to the access point is stopped until time t1 such that t\ = xmn{s:s>t,qdepth{k,J,s)
2. If at some time t_start, buff _unres_free{t _start)
flow control as described here until the earliest time t_end {>t_start)
when buff _unres_free{t _end) > a^ * buff _ap (i.e. we have
buff __unres_free{t_end)
interval {t_start,t_end)). Here, a, and a^ are pre-specified such that
0
{t_start,t_end). For flows belonging to class J=4 and 5, send flow control
message for each flow k for which qdepth{k,Jj)> buff _m\n_flow{k,J).
This message is sent from the access point (like the 3G-BTS or the
WLAN-AP) to the upstream node (like the 3G-BSC in a 3G network or
WLAN-aggregator in a WLAN network). Upon receiving the flow control
message for such a flow k, the upstream node (like 3G-BSC) regulates
flow of packets to the access point for such flows for the time interval
{t _ start, t _ end) and works to ensure that
qdepth{k,Jj)
j=4 or J=5.
3. Again, consider an arbitrary time instant t in the interval {t_start,t_end).
For flows belonging to class J=1, 2 or 3, send flow control message for
each flow k for which
qdepth{k, J, /) > max{^^ * buff _ max_ flow{k, J, t\ buff _ min_ flow(k, J)}.
Here, ^^
and 3. This message is sent from the access point (like the 3G-BTS or the WI_AN-AP) to the upstream node (like the 3G-BSC in a 3G network or WLAN-aggregator in a WLAN network). Job of this flow control message is to regulate flow of packets to the access point for such flows for the time interval {t _startj _end) and work to ensure that
qdepth(k, J, 0 ^ max{^j * buff _ max_ flowik, J, t), buff _ min_ flow{k, J)} for
each flow k belonging to class J=1 or J=2 or J=3.
Mechanism II: Dynamic Buffer Management, Flow Control and Admission Control
The dynamic buffer management, flow control and admission control mechanisms invented here work as follows.
Buffer Management:
Let buff_ap be the maximum number of MAC packets that the access point can store for forward link flows. In the system described here, each flow is allocated a fixed amount of buffer initially. This depends upon class of the flow. Let buff_m\n{J) be the minimum number of MAC packets that can be stored at the access point for any fonward link flow for class J. Each flow belonging to the same class is assigned same amount of minimum buffer initially, i.e. buff _m\n_flow{k,J)^buff _m\n_flow(p,J% for each flow k and p belonging to
the same class J. Here, buff _m\n_ flow(k, J) is the minimum amount of buffer allocated for flow k of class J, if such a flow is admitted in the system.
For each flow k corresponding to class J, a parameter, buff _max{J), is also
specified that gives the maximum number of MAC packets that are allowed to be stored for any flow k of class J. Each flow belonging to the same class is assigned same amount of maximum allowed buffer, i.e. buff _mdix__flow(k,J) = buff _msix_flowip,J), for each flow k and p belonging to
the same class J. Here, buff _meix_flow{k,J) is the maximum amount of buffer
reserved for flow k of class J, if such a flow is admitted in the system. Let qdepth{k,Jj)be the number of MAC packets stored at the access point for flow k
at time t. In the system described here, it is ensured that
buff _ min( J)
In the system here, the network operator (i.e. the wireless service provider) is allowed to specify minimum number of flows corresponding to Class 1 to 4 which need to be supported at the access point. Let Nf^ be the minimum number of
flows that are allowed corresponding to class J at the access point (for J=1, 2, 3, 4, 5). A counter is kept for each class that counts the number of flows which have been admitted for that class. Let mm_flows{Jj) be the number of flows
corresponding to class J which are present in the system at time t.
Available buffer, buff_avail{t\ at time t, is computed as follows: buff _ avail{t) = buff _ ap - ^ max{A'^'", «w/w _ fIows(J, 0} * buff _ min(y) - ^ ]^ max{qciepth(k, J, t) ~ buff _ min( J),0}
J k
Reserved amount of buffer at time t is denoted by buff _res{t). At time 0, it is given as: buff _res{G) = ^Nf'"*"buff _mm{J). At time t, it is computed as:
buff _ resit) = ^ max{A^7", mm _ flows{J, t)} * buff _ min(J)
For a flow k corresponding to class J, which has been admitted in the system, if there are sufficient packets in the system to occupy buff_m\n{J) at time t, then
packets corresponding to this flow can be admitted at the access point upto the maximum limit of 6t#_max(J) as long as unreserved buffer space is available
at the access point. Buffer space used by such flows, buffer_used_meix_m\n(i),
at time t is computed as:
buff _ used _ max_ min(0 = ^ ^ max{qdepth{k, J, t) - buff _ niin(J),0}
In this system,
^nff -^P~ ^Hff _ ^^^(0 + buff _ avail{() + buff _ used _ max_ min(/).
This is shown in Figures 9 and 10,
(Flow) Admission Control:
Let reqrate{k,J) be the average required rate for flow k corresponding to class J. Let A[k,J,ri\be the rate indicated by the mobile station corresponding to flow k belonging to class J in the time slot n (considering a discrete time wireless
system), and A(k,J,n) be its exponentially weighted moving average where
1 , 1
A(k,J,n) = —A[k,J,n] + (l—)A{k,J,n-\). Here, a time constant t^ is chosen
such that 0
here it is quite possible that A{k\J\,ri) ^ A{k2,Jl,n) ^ A{MS^,ri). This is possible because a mobile user could start applications at different time instants at a
mobile station. Here, A{MS^,n), is the average channel data rate indicated by the mobile station, MS^, by slot n, starting from the time mobile station MS, was
activated in the network while A{kl,J\,n) is the average channel data rate
indicated by the mobile station MS,, by slot n, but starting from the time when
the application corresponding to flow k1 belonging to class J1 was activated by the mobile user corresponding to the mobile station MS,.
Suppose a flow f, belonging to an arbitrary class J, arrives in the system at time t. If J=5, this flow is admitted in the system. If J=1 or 2 or 3 or 4, do as follows. Consider each flow which has been already admitted in the system and find out the total number of flows for which
reqrate{KJ) > ^(A:, J)* ^(^, J,/),V^,for J=1, 2, 3 and 4, at time t
(i.e. when flow f corresponding to class J arrives and a decision has to be made whether or not to admit this flow f). Here, r{k,J), is a pre-specified priority
constant for each flow k, for each class J (for J=1, 2, 3 and 4), which is a function of flow's traffic and QoS characteristics. It is a positive real-number, i.e.
rik,J)eRLet mm_ flows _typeA{t) be the total number of such flows in the system at time t, i.e.
mm _ flows __ typeAit) = X S ^{^^9^^^^^^ J) ^ 7(1^^ J) * Ak, J, 0) •
J=l k
Here,
U{reqrate{K J) ^ r{k, J) * A{k, J, 0) = I if reqrateik, J) ^ y{K J) * A{K J. t); Otherwise, U{reqrate{k, J) > y{k, J) * A{k,Jj)) = 0.
Let frac_ flows_typeA{t) be the fraction of such flows at time t, considering
classes J=1, 2, 3 and 4. Thus,
num _ flows _ typeA{t)
firac _ flows _ typeA(t) =
^ num _ flows (J, t)
j=i
In the system here, a threshold, fi-ac^flows_typeA_thres, is pre-specified. Here, fi-ac^ flows _typeA_thres is a positive real-constant and ft'ac _ flows _ type A _ thres
■mm
To decide whether or not to admit flow f belonging to class J (for J=1, 2, 3 or 4) at time t, do as follows. Admit this flow f if num_flows(J,t)
Otherwise, if num_flows{J,t) > Nf"", admit this flow if
buff _ min(J)
fi^ac _ flows _ typeA(t)
Othenvise, this flow f is not admitted. If this flow f corresponding to class J is admitted in the system, the state variables are updated as follows: num_flows(J,t) = num_flows{J,t) + \\ and buff_avail(t) is recomputed.
Packet Admission:
Now consider a flow k belonging to class J which has been already admitted in the system. Suppose N(k,J,t) MAC packets of flow k of class J arrive in the
system at time t. Let qdepthik.Jj") be the queue depth of flow k belonging to
class J at time /', where /" is a time instant just before time t and no packet arrived in the system between time /" and t. If qdepthik,Jj~)>buff_meoi(J), these Nik, J J) packets are not admitted in the access point and are stored at the upstream node only (like BSC in a 3G network). On the other hand, if qdepthik,J,t')
maximum n(k,J,t), Q
qdepth{k, J, t) = qdepth{k, Jj~) + n{k, J, t)
n{k, J, t)
n{k, y, t) is a non - negative integer and
N(k, J, t) is a positive integer.
Once these n(k,J,t) MAC packets are admitted, buff_res(t) and buff_avail(t) are also recomputed. Remaining packets, i.e. max//www{A^(A:,y,/)-w(A:,J,/),0}, are
stored at the upstream node (i.e. at the 3G-BSC in a 3G network, or at WLAN aggregator in a WLAN network).
Flow Control:
Dynamic flow control in the system described here works as follows. Let mm _ flows _ thres{J) be a pre-specified threshold on number of flows
corresponding to class J for J=1, 2 and 3. Here, num_ flows__thres(J) is a non-negative integer value.
If at some time t_start, buff _ovail{t _start) t_start) when buff _avail{t_end) > //^ *buff _ap (i.e. we have buff _avail(t_end)
1. Send flow control message to each flow belonging to Class J=4 and 5 at the upstream node (i.e. 3G-BSC for 3G network and WLAN-aggregator for WLAN network). Suppose, k is an arbitrary flow corresponding to class J (with J=4 or 5) to which such a flow control message has been sent. This flow control message first freezes (maximum) queue length of each flow k that has received such a message, to maximum{qdepth{k,Jj_start),buff_m\n{J)}. Packets are allowed to be
drained out of this queue via the access point scheduler (towards mobile
stations) but packets are not allowed to this queue from the upstream node (3G-BSC in a 3G network or WLAN-aggregator in a WLAN network) until queue length of this flow k reaches a value which is equal or less than its buff _m\r\_flow{k,J).
2. Once queue depth of flow k reaches a value smaller than or equal to
buff _m\n_flow{k,J), say at time
t{k\ v^\\txtt{k)\%%\xd^\h2Xt_start
packets for this queue from the upstream node (3G-BSC in a 3G network or WLAN-aggregator in a WLAN network). But its maximum queue depth is not allowed to go above buff_m\n_flow{k,J)6\}mQ the remaining
period of the interval {t{k\t_end).
3. For each flow corresponding to class J=1 or 2 or 3, flow control works to
maintain queue depth less than 6wjf_max(J). Specifically, if there is
space for some packets in its queues (corresponding to flows belonging to class J=1, 2 or 3), it informs the upstream node about its queue length status. Also, once the time, t_end, is reached, flow control for all other classes (i.e. for J=4 or 5) allows queue depth to become higher than buff _vcvm{J) but keeps it upper bounded by few#_max(J).
Mechanism III: Dynamic Buffer Management and Flow Control
This mechanism combines the methods used in mechanisms I and II.
Buffer Management:
The same method for buffer management as in Mechanism I is carried out.
Flow Admission:
The same method for flow admission as in Mechanism II is carried out.
Packet Admission:
The same method for packet admission as in Mechanism I is carried out.
Flow Control:
The same method for flow control as in Mechanism I is carried out.
Mechanism IV: Admission Control, Dynamic Buffer Management and Flow Control
Buffer Management:
The same method for flow admission as in Mechanism I is carried out. Flow Admission:
Consider flows belonging to class J=1, 2 and 3 which are present in the system at time t. Find out fraction of these flows, frac_dbomd_ jitter_viol{t), at time t,
for which either delay bound or delay jitter has been violated. If delay bound or delay jitter is violated for more than x(k,J) percent of the IP packets of a flow (corresponding to class J=1, 2 or 3), it is considered that its QoS requirements have been violated. Here, x(k,J) is a pre-specified positive real constant for each flow k considering all flows of classes J=1, 2 and 3. Let numflows_dbound_ jitter _viol{i)be the number of such flows at time t
^ ,, , .. . ,,. numflows dbouttd jitter vioUt) . .
frac _ dbound _ jitter _ viol{t) = r= =^ = ^, (when
^ num _ flows(J, t)
j=^num_Jlows(Jj) ^ 0.)
j=Let reqrate(k,J) be the average required rate for flow k corresponding to class J. Let A[k,J,n]be the rate indicated by the mobile station corresponding to flow k belonging to class J in the time slot n (considering a discrete time wireless
system), and A(k,J,n) be its exponentially weighted moving average. Consider
each flow which has been already admitted in the system and flnd out the total number of flows for which
reqrate{k,J)>Y{KJ)*A{k,Jj%\fKfox^-'\, 2 and 3, at timet
(i.e. when flow /"corresponding to class J arrives and a decision has to be made whether or not to admit this flow f). Here, y{KJ), is a pre-specified priority
constant for each flow k, for each class J (for J=1, 2, and 3 ), which is a function of flow's traffic and QoS characteristics. It is a positive real-number, i.e.
y(k,J)eR^. Let num_ flows_typeB{t) be the total number of such flows in the
system at timet, i.e.
mm _ flows _ typeB{t) = X S U{reqrate{k, J) > r(k, J) * A{k, J, /)).
j=\ k
Here,
U{reqrate{K J) > yiK J) * A{K J. 0) = I if reqrate{k, J) > y{k, J) * A{k, J, t); Otherwise, U(reqrate(k, J) > yik, J) * A{kjj)) = 0.
Let fi-ac_ flows_typeB{t) be the fraction of such flows at time t, considering classes J=1, 2, and 3. Thus,
num _ flows _ typeB{t)
fi'QC _ flows _ typeB{t) -
^ num _ flows(J, t)
j=In the system here, a threshold, fi-ac_flows_typeBjhres, is pre-specified. Here, fi'ac_ flows _typeB_thres Is a positive real-constant and
fi'ac _ flows _ typeB _ thres
Now consider a flow f corresponding to class J which arrives in the system at time t. Do the following to decide whether or not to admit this flow. Let, fi-ac_dbound_ jitter_viol_thres be a pre-specified positive real constant and
fi'ac_dbomd_jitter_viol_thres
fi^ac _ dbound _ jitter _ viol{t) > ft-ac _ dbound _ jitter _ viol _ thres, and if
jrac_ flows_typeB{t)> fi-ac_ flows_typeB_thres, the newly arrived flow f is not
admitted. Othen/vise, method similar to the one described in mechanism I is used to decide whether or not to admit this flow f. If flow f corresponds to class
J=4 or 5, then also the method as described in mechanism I is used to decide whether or not to admit this flow in the system.
Packet Admission:
The same method for packet admission as in Mechanism I is carried out.
Flow Control:
The same method for flow control as in Mechanism I is carried out.
In the description herein, numerous specific details are provided, such as examples of components and/or methods, to provide a thorough understanding of embodiments of the present invention. One skilled in the relevant art will recognize, however, that an embodiment of the invention can be practiced without one or more of the specific details, or with other apparatus, systems, assemblies, methods, components, materials, parts, and/or the like. In other instances, well-known structures, materials, or operations are not specifically shown or described in detail to avoid obscuring aspects of embodiments of the present invention.
It will also be appreciated that one or more of the elements depicted in the drawings/figures can also be implemented in a more separated or integrated manner, or even removed or rendered as inoperable in certain cases, as is useful in accordance with a particular application. It is also within the spirit and scope of the present invention to implement a program or code that can be stored in a machine-readable medium to permit a computer to perform any of the methods described above.
Additionally, any signal arrows in the drawings/Figures should be considered only as exemplary, and not limiting, unless othenA/ise specifically noted. Furthermore, the term "or" as used herein is generally intended to mean "and/or" unless otherwise indicated. Combinations of components or steps will also be
considered as being noted, where terminology is foreseen as rendering the ability to separate or combine is unclear.
As used in the description herein and throughout the claims that follow, "a", "an", and "the" includes plural references unless the context clearly dictates otherwise. Also, as used in the description herein and throughout the claims that follow, the meaning of "in" includes "in" and "on" unless the context clearly dictates othenwise.
The foregoing description of illustrated embodiments of the present invention, including what is described in the Abstract, is not intended to be exhaustive or to limit the invention to the precise forms disclosed herein. While specific embodiments of, and examples for, the invention are described herein for illustrative purposes only, various equivalent modifications are possible within the spirit and scope of the present invention, as those skilled in the relevant art will recognize and appreciate. As indicated, these modifications may be made to the present invention in light of the foregoing description of illustrated embodiments of the present invention and are to be included within the spirit and scope of the present invention.
Thus, while the present invention has been described herein with reference to particular embodiments thereof, a latitude of modification, various changes and substitutions are intended in the foregoing disclosures, and it will be appreciated that in some instances some features of embodiments of the invention will be employed without a corresponding use of other features without departing from the scope and spirit of the invention as set forth. Therefore, many modifications may be made to adapt a particular situation or material to the essential scope and spirit of the present invention. It is intended that the invention not be limited to the particular terms used in following claims and/or to the particular embodiment disclosed as the best mode contemplated for carrying out this invention, but that the invention will include any and all embodiments and equivalents falling within the scope of the appended claims.
GLOSSARY OF TERMS AND DEFINITIONS THEREOF
3G: Third Generation Wireless NetworlK
AP: Access Point
BSC: Base Station Controller
BSS: Basic Service Set
BTS: Base Transceiver System
CN: Con^espondent Node (It is a node with which the MS is communicating. For
example, it could be a multimedia server or some other mobile station)
CDMA: Code Division Multiple Access
CDMA2000 1xEV-D0: CDMA Single Carrier Evolution, Data Only
CDMA2000 IxEV-DV: CDMA, Single Carrier, Data and Voice
DS: Distributed System
ESS: Extended Service Set
Forward link flows: These are flows which send data packets from CN (or
WER) towards the MS.
FTP: File Transfer Protocol
HTTP: Hyper-Text Transfer Protocol
IP: Internet Protocol
MAC: Medium Access Control
MS: Mobile Station
MPEG: Moving Picture Experts Group
PCF: Packet Control Function block
Reverse link flows: These are flows which send data from the MS towards the
CN (or WER).
VoIP: Voice over internet Protocol
WER: Wireless Edge Router
WLAN: Wireless Local Area Network
WCDMA: Wideband Code Division Multiple Access
WE CLAIM
1) A method for dynamic flow control, buffer management and admission control
for cellular wireless multimedia networks such as 3G, WLAN or integrated 3G-
WLAN system implemented/using plurality of mechanisms therein the said
method comprising the steps df r" ,' ; -
(a) deciding whether or not to admit a new flow in the cellular network by an adaptive admission control mechanism;
(b) assigning a fixed amount of buffer initially depending upon its traffic characteristics and QoS requirements for each admitted flow;
(c) computing dynamically maximum allowable buffer for each flow k belonging to quality of service class J at time t, buff _max_flow(k,Jj), taking into account
network conditions such as quality of service violation for each flow, quality of service class, channel conditions of mobile devices and network load;
(d) pre-specifying minimum number of flows for each quality of service class J,
A^7"» that can be admitted in the system and minimum amount of buffer, buff _res_m\n is kept reserved for these flows;
(e) allocating a common buffer pool, buff ^common, wherein it is allocated and set equal to the total buffer pool {buff_ap) minus the minimum amount of reserved buffer for all quality of service classes {buff _res_m\n);
(f) allocating buffer space equal to buff _m\n_flow(h,J) for each new flow h
corresponding to class J, if admitted in the system ;
(g) allocating buffer space for new flows belonging to some class J using
common buffer pool, buff ^common, for which number of admitted flows have
already exceeded their minimum reserved quota, i.e. Nf"", and for each
admitted flow h corresponding to class J for which current queue depth already exceeds its minimum reserved buffer quota, buff _m\n_flow(h,J);
(h) computing the maximum number of MAC packets, n{k,Jj). to be admitted at
the access point, in that a maximum of n{k,J,t) MAC packets are admitted to
the access point by considering the flows which have already been admitted in the system.
(i) dynamically deciding the action to be taken by a flow control message, which is sent from the access point to the upstream node and on receipt of the flow control message for such a flow k, the upstream regulates flow of packets to the access point for such flows.
2) A method as claimed in claim 1, wherein the said plurality of mechanisms involves four different implementations.
3) A method as claimed in claim 1, wherein in first implementation, dynamic computation of maximum allowable buffer for each flow is carried out in that for the minimum number of flows that are allowed corresponding to class J at the access point and the number of flows corresponding to class J that is present in the system, maximum number of MAC packets that are allowed to be stored at time t at the access point Is computed dynamically taking into account channel conditions for mobile stations, traffic characteristics and QoS requirements for flow k wherein for the pre-specified average arrival rate of flow k belonging to
class J a time constant r is chosen such that 0
number of MAC packets, buff _mdOL_flow{k,J,t) such as herein described and
for flow k belonging to class J, at time t, at the access point is computed and the number of MAC packets such as herein described is stored at the access point for flow k corresponding to class J at time t.
4) A method as claimed in claim 1, wherein in first implementation, a common
buffer pool, buff ^common, is allocated, packets of a flow when it has already
used its minimum fixed quota is stored, buffer space is allocated for new flows of a class J when number of flows present in the system for that class has already
exceeded Nf"" such as herein described wherein buffjresjnin, is the minimum amount of buffer reserved for flows belonging to different classes.
5)A method as claimed in claim 1, wherein in first implementation , a new flow h corresponding to class J appearing in the system is admitted and allocated buffer space equal to buff_m\n_flowiKJ)\ the channel data rate A[h,.] such as
herein described is observed for some slots and buff _m^\_flowik,J,t) is
dynamically computed.
6) A method as claimed in claim 1, wherein in first implementation, for the flows
which have already been admitted in the system and where MAC packets of flow
k of class J arrive in the system at time t the maximum number of MAC packets,
n(k,J,t), to be admitted at the access point is computed in accordance with the
value of qdepth{k,Jj:), the queue depth of flow k belonging to class J at time
r, such ^fterein described.
- ■ ■■'^
7) A method"as^claimed in claim 1, wherein in first implementation, maximum
allowable buffer, buff _m^x_f}ow{k,J,tp^^j is computed for flow k and wherein
when qdepth{k,J,t)>buff__mdiX_flow{k,J,tp^^), then buff__ma\_flow{k,J,t) is
recomputed at the time t and where qdepth{k,J,t)>buff _mw._flov^{KJ,t ), a
flow control message is sent for this flow k from the access node to the upstream node and control of flow of packets for flow k to the access point is stopped until time t1 such as herein described.
8) A method as claimed in claim 1, wherein in buffer management as per second
implementation each flow Is allocated a fixed amount of buffer initially depending
upon class of the flow; each flow belonging to the same class is assigned same
amount of minimum buffer initially, if such a flow is admitted in the system;
minimum number of flows which need to be supported at the access point is
computed, a counter counts the number of flows which have been admitted for
specified class; for a flow k corresponding to class J, which has been admitted in
the system, if there are sufficient packets in the system to occupy buff _m\n{J) at
time t, then packets corresponding to this flow are admitted at the access point
upto the maximum limit of buff_max(J) until unreserved buffer space is available at the access point.
9) A method as claimed in claim 1, wherein in admission control in second
implementation, the number of flows admitted is computed wherein reqrate{k,J)
is the average required rate for flow k corresponding to class J; A{MS^,n), is the average channel data rate indicated by the mobile station, MS/, the application corresponding to flow k1 belonging to class J1 is activated by the mobile user corresponding to the mobile station MS^ where the flow is admitted in the system considering the value of yik.J), a pre-specified priority constant for each flow k and which is a function of flow's traffic and QoS characteristics and the flow is admitted when num _flows{J,t)
more than the.minimum required buffer.
10) A method as claimed in claim 1, wherein in flow control in second
implementation, the flow controlled dynamically in that flow control message is
sent to each flow belonging to each at the upstream node and the flow control
message first freezes (maximum) queue length of each flow k that has received
such a message; packets are drained out of this queue via the access point
scheduler and allowed to this queue from the upstream node on the queue
length of this flow k is less than or equal to buff _m\n_flow(k,J).
11) A method as claimed in claim 1 and 9 wherein for each flow corresponding to
class J=1 or 2 or 3, flow is controlled such as herein described to maintain queue
depth less than buff_max{J) and where there is space for some packets in its
queues the upstream node is communicated about its queue length status and the flow is controlled for all other classes (i.e. for J=4 or 5) to allow queue depth higher than buff_m\n(J) and upper limit bounded by buff_meixiJ).
12) A method as claimed in claim 1, wherein in admission control in fourth
implementation, for flows for which QoS requirements in terms of delay jitter or
delay bound is violated, where reqrate{k,J) is the average required rate for flow
k corresponding to class J; A{k,J,n\ is the rate indicated by the mobile station
corresponding to flow k belonging to class J in the time slot n (considering a
discrete time wireless system), and A{k,J,n) its exponentially weighted moving
average and where the flow's traffic and QoS characteristics are monitored in that when the delay bound and jitter are less than the threshold such as herein described the flow is admitted.
13) A system for dynamic flow control, buffer management and admission
control for cellular wireless multimedia networks particularly 3G-WLAN
internetworking system comprising:
(a) means for assigning each flow an amount of fixed buffer initially depending upoffits traffic characteristics and QoS requirements;
(b) means for computing dynamically maximum allowable buffer for each flow;
(c) means for allocating common buffer pool;
(d) means for admitting and allocating buffer space for each flow, and
(e) means for sending a flow control message for each flow from the access node to the upstream node and controlling of flow of packets for each flow.
14) A system for dynamic flow control, buffer management and admission control for cellular wireless multimedia networks particularly 3G-WLAN internetworking system substantially as herein described particularly with reference to the drawings.
15) A method for dynamic flow control, buffer management and admission control for cellular wireless multimedia networks particularly 3G-WLAN
internetworking system substantially as herein described particularly with reference to the drawings.
|