FIELD OF THE INVENTION
The present invention relates generally to a method and an apparatus for determining Queue Fill Level of atleast one data type stored in a storage device for generating a Dynamic Bandwidth Allocation Report in a Gigabit Passive Optical Network (GPON).

BACKGROUND
The Gigabit Passive Optical Network technology is being considered as a promising solution for the next-generation broadband access network. Since the network topology of the GPON is point-to-multipoint, a media access control called Dynamic Bandwidth Allocation (DBA) is an important factor for determining the performance of GPON.
The Dynamic Bandwidth Allocation (DBA) is a process whereby an optical network unit (ONU) or alternatively referred to as an optical network terminal (ONT) requests upstream bandwidth to an optical line terminal (OLT) and the OLT reassigns the upstream bandwidth dynamically amongst the different ONUs. In GPON there are two forms of DBA reporting namely status-reporting (SR) and non-status reporting (NSR).
In NSR DBA, the OLT uses service level agreement (SLA) configuration data and monitored idle GPON Encapsulation method (GEM) frames in each traffic container (T-CONT) as inputs. NSR DBA has the disadvantage that there is no way for the OLT to know how best to assign bandwidth across several ONUs that need more.
In SR DBA, the OLT polls ONUs for their backlogs. A given ONU may have several so-called traffic containers (T-CONTs), each with its own priority or traffic class. The ONU reports each T-CONT separately to the OLT. The report message contains a logarithmic measure of the backlog in the T-CONT queue. By knowledge of the SLA for each T-CONT across the entire passive optical network (PON), as well as the size of each T-CONT''s backlog, the OLT can optimize allocation of the spare bandwidth on the PON. In SR DBA, the OLT uses SLA configuration data, monitored idle GEM frames in each T-CONT (traffic container) and DBA reporting information from all ONUs as inputs.
The process of ONU providing its queue status information such as the dynamic queue fill level of data types is called DBA reporting.
There has been felt a need to provide to an efficient method to generate a DBA report without much of investment of system resources and which can assist in OLT in arriving at the dynamic bandwidth allocation effectively.
SUMMARY OF THE INVENTION
Accordingly, the present invention provides a method for determining a dynamic queue fill level for at least a first data type stored in a storage device, the said storage device comprising a plurality of data types stored thereupon, said method comprising:
a) obtaining either a first data type contribution factor or an approximated first data type contribution factor;
b) obtaining a storage device fill level; and
c) calculating the dynamic queue fill level for said first data type stored in the storage device based on the obtained first data type contribution factor or an approximated first data type contribution factor and the storage device fill level.

In an embodiment of the present invention, the first data type contribution factor is obtained by configuring a predetermined constant value.

In another embodiment of the present invention, the first data type contribution factor is obtained by user repeatedly setting and resetting the contribution factor at user defined intervals.

In yet another embodiment of the present invention, the first data type contribution factor is obtained by:
a) determining a volume of the first data type being sent for storage onto the storage device over a period of time;
b) determining a total volume of all other data types being sent for storage onto the storage device over the aforesaid period of time; and
c) calculating the first data type contribution factor as:
contribution factor = (volume of first data type / volume of all other data types).

In still another embodiment of the present invention, the dynamic queue fill level for said first data type stored in the storage device is calculated as :
Dynamic queue fill level = storage device fill level x contribution factor

In an embodiment of the present invention, calculating the approximated first data type contribution factor comprises the step of determining the volume of the first data type and the total volume of all other data types.

In another embodiment of the present invention, if the volume of the first data type is 0, the approximated first data type contribution factor is assigned a value of 0, the storage device fill level is completely assigned to dynamic fill level for the other data types and the dynamic fill level for the first data type is assigned a value of 0.

In still another embodiment of the present invention, if the volume of the first data type is a non-zero value and is less than the total volume of all other data types, a digital value representative of the volume of the first data type is left shifted repeatedly till its value is equal to or greater than a digital value representative of the volume of all other data types, wherein a number of times the left shifting is performed is used to calculate the approximated first data type contribution factor and the storage device fill level is right shifted for a number of times equal to that used for calculating the approximated first data type contribution factor to obtain the dynamic queue fill level for said first data type.

In yet another embodiment, the present invention further comprises calculating dynamic queue fill level for all other data types by subtracting the dynamic queue fill level for said first data type from the storage device fill level.

In one more embodiment of the present invention, if the volume of all other data types is a non-zero value and is less than the total volume of the first data type, a digital value representative of the volume of all other data types is left shifted repeatedly till its value is equal to or greater than a digital value representative of the volume of the first data type, wherein a number of times the left shifting is performed is used to calculate the approximated all other data types contribution factor and the storage device fill level is right shifted for a number of times equal to that used for calculating the approximated all other data types contribution factor to obtain the dynamic queue fill level for all other data types.

In a further embodiment, the present invention further comprises calculating dynamic queue fill level for the first data type by subtracting the dynamic queue fill level of all other data types from the storage device fill level.

In a further more embodiment, the present invention further comprises calculating the dynamic queue fill level for the other data types based on the values of the storage device fill level and the calculated queue fill level for the said first data type.

The present invention also provides an apparatus for determining the storage device queue fill level for at least a first data type, comprising:
a buffer manager coupled with the storage device configured to determine storage device fill level; and
a packet processor in communication with the Buffer Manager and being configured to obtain atleast a first data type contribution factor or an approximated first data type contribution factor and determine a dynamic queue fill level for at least a first data type stored in said storage device.

BRIEF DESCRIPTION OF THE DRAWINGS
The features of the present invention are set forth with particularity in the appended claims. The invention itself, together with further features and attended advantages, will become apparent from consideration of the following detailed description, taken in conjunction with the accompanying drawings. One or more embodiments of the present invention are now described, by way of example only, with reference to the accompanied drawings wherein like reference numerals represent like elements and in which:

Figure 1 illustrates a flowchart of a method for determining a dynamic queue fill level for atleast a first data type stored in a storage device.

Figure 2 illustrates a flowchart of a method for determining a dynamic queue fill level for atleast a first data type stored in a storage device without using the division operation.

Figure 3 illustrates an algorithm determining a dynamic queue fill level for atleast a first data type stored in a storage device without using the division operation.

Figure 4 is a graph illustrating error in PIR (Peak Information Rate) as a fraction of the Queue Fill level.

Figure 5 is a graph illustrating error in PIR as a fraction of PIR reported.

Figure 6 is a graph illustrating error in PIR as a fraction of PIR reported for (Committed Information Rate) CIR/PIR ratio<=1.

Figure 7 illustrates an apparatus for determining a dynamic queue fill level for at least a first data type in accordance with an embodiment of the present invention.

DETAILED DESCRIPTION
Before describing in detail embodiments that are in accordance with the present invention, it should be observed that the embodiments reside primarily in combinations of method steps related to generating DBA report applied during the process of dynamic bandwidth allocation.

Accordingly, the method steps have been represented where appropriate by conventional symbols in the drawings, showing only those specific details that are pertinent to understanding the embodiments of the present invention so as not to obscure the disclosure with details that will be readily apparent to those of ordinary skill in the art having benefit of the description herein.

The terms “comprises”, “comprising”, or any other variations thereof, are intended to cover a non-exclusive inclusion, such that a process, method that comprises a list of steps does not include only those steps but may include other steps not expressly listed or inherent to such process, method. Similarly, one or more elements in a system or apparatus proceeded by “comprises… a” does not, without more constraints, preclude the existence of other elements or additional elements in the system or apparatus.

The present disclosure relates to a method and an apparatus for determining the storage device queue fill level for at least a first data type stored in the storage device.

Figure 1 illustrates a flowchart of a method for determining a dynamic queue fill level for at least a first data type stored in a storage device (730) implemented by a system (700).

At step 110, a plurality of data types is received by the packet processor (710).

In one embodiment, the data received by the packet processor is of two types namely Peak Information Rate (PIR) data and Committed Information Rate (CIR) data. Committed Information Rate (CIR) is the average bandwidth guaranteed by an ISP (Internet Service Provider) to work under normal conditions. At any given time the bandwidth should not fall below this committed figure. Above the Committed Information Rate (CIR), an allowance of burstable bandwidth is known as Peak Information Rate (PIR).

At step 120, the packet processor (710) obtains a contribution factor of at least a first data type stored in the storage device (730). In the above mentioned embodiment, the first data type is the PIR data type.

In one embodiment, the contribution factor of PIR data type is obtained by configuring a predetermined constant value. By way of example, the contribution factor of PIR data or that of CIR data type can be configured as part of device bringing up by appropriate means. For example, the value of PIR data can be set to 30% of the storage fill level.

In another embodiment, the contribution factor of PIR data type is given by the user. The user can repeatedly set and reset this value.

In yet another embodiment, the contribution factor of PIR data type is obtained by calculating the contribution factor of PIR data based on the determination the volume of PIR data type being sent for storage on the storage device (730) over a period of time and determination of a total volume of PIR and CIR data types being sent for storage onto the storage device over the aforesaid period of time.

For example, contribution factor (C.F.) of PIR data can be calculated as:

C.F. = PIR
PIR+CIR

At step 130, the packet processor (710) obtains a storage device fill level. The buffer manager (720) has the information of the storage device fill level which is conveyed to the packet processor (710) at certain intervals or on request made to the buffer manager (720).

At step 140, the packet processor (710) calculates a dynamic queue fill level of PIR data.

In a particular implementation, the dynamic queue fill level of PIR data is calculated by using the storage fill level and the contribution factor of PIR data, which can be obtained by any of the above mentioned three methods.

In yet another embodiment, the dynamic queue fill level of PIR data is calculated by using the storage device fill level and the contribution factor of PIR data which in-turn is calculated by using the volume of PIR data type being sent for storage on the storage device (730) over a period of time and a total volume of PIR and CIR data types being sent for storage onto the storage device (730) over the aforesaid period of time.

In all the above mentioned embodiments, the dynamic queue fill level of PIR data can be calculated as:
Dynamic queue fill level of PIR = storage device fill level x Contribution factor of PIR.

As it can be noticed, the above methodology uses operations that involve:
(a) divisions; and
(b) multiplications.

As implementation of methods involving multiplication and/or division operations may be:
(a) costly; and/or
(b) involve high resource utilization.
it is preferred to provide a method which does not require performing one or more of the division and/or multiplication operation while calculating the dynamic queue fill level for a particular type of data flow (for example PIR / CIR).

Thus, figure 2 illustrates a flowchart of a method for determining a dynamic queue fill level (DQL) for at least a first data type stored in a storage device without using the division operation.

At step 210, a plurality of data types is received by the packet processor (710). In one embodiment, the data received by the packet processor is Peak Information Rate (PIR) data and Committed Information Rate (CIR) data.

At step 220, the volume of each of the data type received by the packet processor (710) is determined. More particularly, the volume of each data type is separately counted.

At step 230, the packet processor (710) obtains a storage device fill level. The buffer manager (720) has the information of the storage device fill level which is conveyed to the packet processor (710) at certain intervals or on a request made to the buffer manager (720).

At step 240, it is determined as to whether the volume count of PIR is equal to the volume count of CIR. If the response is YES, then in step 250, the storage device fill level is equally assigned to dynamic fill level for PIR and the dynamic fill level of CIR. In other words, dynamic fill level for PIR is set to be equal to the dynamic fill level for CIR.

Although not explicitly shown in figure 2, it may be also possible to determine as to whether volume count of PIR is “0” and if it is determined to be “0”, the approximated PIR contribution factor is assigned a value of 0, the storage device fill level is completely assigned to dynamic fill level for the other data types (i.e. to CIR) and the dynamic fill level for PIR is assigned a value of 0. A vice versa procedure in respect of CIR can also be performed.

As can be seen from step 260, it can also be checked as to whether the volume of the first data type (PIR in the present case) is less than the total volume of all other data types (CIR), if the response is YES, the approximated dynamic queue level for PIR is calculated in step 270, which comprises repeatedly left shifting a digital value representative of the volume of the first data type till its value is equal to or greater than a digital value representative of the volume of all other data types, wherein a number of times the left shifting is performed is used to calculate the approximated first data type contribution factor and the storage device fill level is right shifted for a number of times equal to that used for calculating the approximated first data type contribution factor to obtain the dynamic queue fill level for said first data type. Step 270 may further comprise calculating dynamic queue fill level for all other data types by subtracting the dynamic queue fill level for said first data type from the storage device fill level.

On the other hand, if the volume of all other data types is less than the total volume of the first data type, the approximated dynamic queue level for CIR is calculated in step 280, which comprises repeatedly left shifting a digital value representative of the volume of all other data types till its value is equal to or greater than a digital value representative of the volume of the first data type wherein a number of times the left shifting is performed is used to calculate the approximated all other data types contribution factor and the storage device fill level is right shifted for a number of times equal to that used for calculating the approximated all other data types contribution factor to obtain the dynamic queue fill level for all other data types. Step 280 in this case may further comprise calculating dynamic queue fill level for the first data type by subtracting the dynamic queue fill level of all other data types from the storage device fill level.

Thus, in general, in addition to calculating dynamic queue fill level for the first data type (PIR), it is also possible to additionally or alternatively calculate the dynamic queue fill level for the other data types based on the values of the storage device fill level and the calculated queue fill level for the said first data type. One of the methods of for performing the flow chart of figure 2 is illustrated in figure 3.

Figure 4 is a graph illustrating error in PIR as a fraction of the Queue Fill level. The graph is plotted as a function of queue fill level for different ratios of CIR/PIR. (“cp_x indicates CIR/PIR ratio of x).

Figure 5 is a graph illustrating error in PIR as a fraction of PIR reported. In this graph, when the total amount of data available in the storage device is large, the error in PIR stays bounded within ~10% of the data available.

Figure 6 is a graph illustrating error in PIR as a fraction of PIR reported for CIR/PIR ratio<=1.In this graph, when the CIR to PIR ratio is large, there is more uncertainity on the PIR value sent in the DBA report.

Figure 7 illustrates an apparatus for determining a dynamic queue fill level for at least a first data type in accordance with an embodiment of the present invention.

The apparatus (700) may be connected to a storage device (730) configured to store a plurality of data types. The apparatus comprises a buffer manager (720) coupled with the storage device to determine the storage device fill level. The apparatus further comprises a packet processor (710) in communication with the buffer manager which is configured to determine a dynamic queue fill level for at least a first data type stored in the storage device (730). The packet processor (710) receives a plurality of data types and obtains or calculates a volume of each of the data type received. The Buffer Manager (720) conveys the storage device fill level to the packet processor at certain intervals. The packet processor (710), using the volume of all data types and the storage device fill level, determines a dynamic queue fill level for at least a first data type stored in the storage device (730). The apparatus shown in figure 7 is by way of illustration only and the packet processor shown processes headers and generates the DBA report. All the packets are processed in the packet processor (710) and handed over to the buffer manager (720) for storage on to the storage device (730). Also, the buffer manager maintains the status of the Qfill levels of all the queues and communicates that to the packet processor. The packet processor counts the number of PIR and CIR bytes passing through it (called PIRfw and CIRfw) that it uses, as described above to derive the PIR and CIR bytes contrinutions to the Qfill (which is obtained from the buffer manager).

It will be appreciated that embodiments of the invention described herein (especially each of the packet processor and the buffer manager) may be comprises of one or more conventional processors and unique stored program instructions that control the one or more processors to implement, in conjunction with certain non-processor circuits, some, most, or all of the arbitration functions described herein. Alternatively, some or all of the arbitration functions could be implemented by a state machine that has no stored program instructions or in one or more application specific integrated circuits (ASICs), in which each function or some combinations of certain of the functions are implemented as custom logic.

Of course, a combination of the two approaches could be used. Thus, method and means for these functions have been described herein. Further, it is expected that one of ordinary skill, notwithstanding possibly significant effort and many design choices motivated by, for example, available time, current technology, and economic considerations, when guided by the concepts and principles disclosed herein will be readily capable of generating such software instructions and programs and ICs with minimal experimentation.

While the particular preferred embodiments of the present invention have been shown and described, it will be obvious to those skilled in the art that changes and modifications may be made without departing from the teachings of the invention. It is therefore contemplated that the present invention cover any and all modifications, variations or equivalents that fall within the scope of the basic underlying principles disclosed above and claimed herein.

We Claim :

1. A method for determining a dynamic queue fill level for at least a first data type stored in a storage device, the said storage device comprising a plurality of data types stored thereupon, said method comprising :-
a) obtaining either a first data type contribution factor or an approximated first data type contribution factor;
b) obtaining a storage device fill level; and
c) calculating the dynamic queue fill level for said first data type stored in the storage device based on the obtained first data type contribution factor or an approximated first data type contribution factor and the storage device fill level.

2. The method as claimed in claim 1, wherein the first data type contribution factor is obtained by configuring a predetermined constant value.

3. The method as claimed in claim 1, wherein the first data type contribution factor is obtained by user repeatedly setting and resetting the contribution factor at user defined intervals.

4. The method as claimed in claim 1, wherein the first data type contribution factor is obtained by:
a) determining a volume of the first data type being sent for storage onto the storage device over a period of time;
b) determining a total volume of all other data types being sent for storage onto the storage device over the aforesaid period of time; and
c) calculating the first data type contribution factor as:
contribution factor = (volume of first data type / volume of all other data types).

5. The method as claimed in any of the preceding claims, wherein the dynamic queue fill level for said first data type stored in the storage device is calculated as :
Dynamic queue fill level = storage device fill level x contribution factor

6. The method as claimed in claim 1, wherein calculating the approximated first data type contribution factor comprises the step of determining the volume of the first data type and the total volume of all other data types.

7. The method as claimed in claim 6, wherein if the volume of the first data type is 0, the approximated first data type contribution factor is assigned a value of 0, the storage device fill level is completely assigned to dynamic fill level for the other data types and the dynamic fill level for the first data type is assigned a value of 0.

8. The method as claimed in claim 6, wherein if the volume of the first data type is a non-zero value and is less than the total volume of all other data types, a digital value representative of the volume of the first data type is left shifted repeatedly till its value is equal to or greater than a digital value representative of the volume of all other data types, wherein a number of times the left shifting is performed is used to calculate the approximated first data type contribution factor and the storage device fill level is right shifted for a number of times equal to that used for calculating the approximated first data type contribution factor to obtain the dynamic queue fill level for said first data type.

9. The method as claimed in claim 8, further comprising calculating dynamic queue fill level for all other data types by subtracting the dynamic queue fill level for said first data type from the storage device fill level.

10. The method as claimed in claim 6, wherein if the volume of all other data types is a non-zero value and is less than the total volume of the first data type, a digital value representative of the volume of all other data types is left shifted repeatedly till its value is equal to or greater than a digital value representative of the volume of the first data type, wherein a number of times the left shifting is performed is used to calculate the approximated all other data types contribution factor and the storage device fill level is right shifted for a number of times equal to that used for calculating the approximated all other data types contribution factor to obtain the dynamic queue fill level for all other data types.

11. The method as claimed in claim 10, further comprising calculating dynamic queue fill level for the first data type by subtracting the dynamic queue fill level of all other data types from the storage device fill level.

12. The method as claimed in claim 1, further comprising calculating the dynamic queue fill level for the other data types based on the values of the storage device fill level and the calculated queue fill level for the said first data type.

12. An apparatus for determining the storage device queue fill level for at least a first data type as claimed in claim 1, comprising:
a buffer manager coupled with the storage device configured to determine storage device fill level; and
a packet processor in communication with the Buffer Manager and being configured to obtain atleast a first data type contribution factor or an approximated first data type contribution factor and determine a dynamic queue fill level for at least a first data type stored in said storage device.

13. A method for determining a dynamic queue fill level for at least a first data type stored in a storage device substantially as herein described with reference to the foregoing description and the accompanying drawings.

14. An apparatus for determining the storage device queue fill level for at least a first data type substantially as herein described with reference to the foregoing description and the accompanying drawings.

Dated this 31st day of December, 2008

G. Deepak Sriniwas
Of K & S Partners
Attorney for the Applicants

ABSTRACT

METHOD AND APPARATUS FOR DETERMINING DYNAMIC QUEUE FILL LEVEL

A method and an apparatus for determining Queue Fill Level of atleast a first data type stored in a storage device for Dynamic Bandwidth Allocation Reporting in a Gigabit Passive Optical Network (GPON). The packet processor (110) uses the volume of each of the data types stored in the storage device (130) and the storage device fill level provided by the buffer manager (120) to calculate the dynamic queue fill level of atleast a first data type.

FIG. 1