Method and device for controlling outliers in offered load estimation in a shared medium communication network

CROSS REFERENCE TO RELATED APPLICATIONS

P-0001[0001] This application is a continuation of U.S. patent application Ser. No. 09/384,816, filed Aug. 27, 1999, entitled “Method And Device For Controlling Outliers In Offered Load Estimation In a Shared Medium Communication Network.”

BACKGROUND OF THE INVENTION

P-0002[0002] 1. Field of the Invention

P-0003[0003] The invention relates generally to communication systems, and more particularly to controlling outliers in offered load estimation in a shared medium communication network.

P-0004[0004] 2. Discussion of Related Art

P-0005[0005] In today's information age, there is an increasing need for high-speed communication networks that provide Internet access and other on-line services for an ever-increasing number of communications consumers. To that end, communications networks and technologies are evolving to meet current and future demands. Specifically, new networks are being deployed which reach a larger number of end users, and protocols are being developed to utilize the added bandwidth of these networks efficiently.

P-0006[0006] One technology that has been widely employed and will remain important in the foreseeable future is the shared medium communication network. A shared medium communication network is one in which a single communications channel (the shared channel) is shared by a number of users such that uncoordinated transmissions from different users may interfere with one another. The shared medium communication network typically includes a number of secondary stations that transmit on the shared channel, and a single primary station situated at a common receiving end of the shared channel for, among other things, coordinating access by the secondary stations to the shared channel. Since communication networks typically have a limited number of communication channels, the shared medium communication network allows many users to gain access to the network over a single communication channel, thereby allowing the remaining communication channels to be used for other purposes.

P-0007[0007] Many techniques are known, which the primary station can use for coordinating access by the secondary stations to the shared channel. The ability of the primary station to meet specified performance goals depends on a number of factors, including the particular technique(s) employed and the number of secondary stations attempting to access the shared channel at any given time. (The rate at which secondary stations are attempting to access the shared channel at a specific time is often referred to as the “offered load” at this specific time). Furthermore, the ability of the primary station to meet specified performance goals often depends on the ability of the primary station to adapt to changes in the offered load over time, and more specifically on how quickly the primary station can adapt to such changes. Thus, the primary station must be able to estimate the offered load of the network and react accordingly.

P-0008[0008] Protocols that are employed to coordinate access to the shared channel are often referred to as Medium Access Control (MAC) protocols. MAC protocols fall into two basic categories: contention-free and contention-based protocols. In contention-free protocols, end users access a shared channel in a controlled manner such that transmissions are scheduled either statically or adaptively so that collisions are completely avoided. In contention-based protocols, users contend with one another to access channel resources. Collisions are not avoided by design, but are either controlled by requiring retransmissions to be randomly delayed, or resolved using a variety of other contention resolution strategies.

P-0009[0009] An example of a contention-based MAC protocol is known as an ALOHA protocol. Its original version, which operates with continuous or unslotted time, is referred to as Unslotted ALOHA. Another version, which operates with discrete or slotted time, is referred to as Slotted ALOHA. The behavior and performance of Unslotted and Slotted ALOHA have been studied widely, and their maximum throughputs are well known to be 1/(2e) and 1/e, respectively.

P-0010[0010] Most contention-based protocols, including the ALOHA protocols, resolve collisions by using feedback information on the number of users involved in the collisions. If the number of conflicting transmissions can be determined from the feedback, then channel throughput arbitrarily close to one packet per packet transmission time is known to be achievable in principle, but with intractable complexity. More often than not, for the sake of simplicity, feedback information used is ternary indicating zero, one, or more transmissions, or binary indicating exactly one transmission or otherwise.

P-0011[0011] A shared channel is typically slotted in time, wherein a slotted ALOHA protocol or any other MAC protocols operating with slotted time can be employed for coordinating channel access. Many variations and extensions have been derived from the original slotted ALOHA protocol. In this protocol, and most of its derivatives, provided the probability of a new transmission and that of a retransmission in each slot are small, the throughput in a slot can be approximated by G(n) exp{−G(n)}, where G(n) is the offered load or attempt rate, which is a function of n that denotes the number of backlogged users at the beginning of a given slot. It follows that the maximum throughput of slotted ALOHA is 1/e=0.368, which is attained when G(n)=1. It is well known that ordinary slotted ALOHA is generally not stable. Various methods for stabilizing slotted ALOHA exist, and many of them resort to adaptive control of the backoff scheme based on one or more states of the contention process. When the actual values of these states are not observable, they are estimated by a variety of means.

P-0012[0012] The stability of slotted ALOHA can be controlled by means of a dynamic frame structure, based on an a-posteriori expected value of the backlog at the beginning of each frame. Rivest in “Network Control by Bayesian Broadcast,” published in the technical report at MIT/LCS/TM-287, MIT Lab. for Computer Science, 1985, proposed a Pseudo-Bayesian algorithm to maintain the attempt rate G(n) close to 1 by estimating the number, n, of backlogged users at the beginning of each slot. A minimum mean-squared error predictor for estimating the channel backlog in slotted ALOHA was proposed by Thomopoulos, in “A Simple and Versatile Decentralized Control for Slotted ALOHA, Reservation ALOHA, and Local Area Networks,” published in the IEEE Trans. on Communications, Vol. 36, No. 6, June 1988, for regulating the retransmission probability according to a recursive function of the channel backlog estimate.

P-0013[0013] The co-pending U.S. patent application Ser. No. 09/085,749 entitled OFFERED LOAD ESTIMATION AND APPLICATIONS FOR USING SAME IN A COMMUNICATION NETWORK by Firass Abi-Nassif and Whay Chiou Lee, filed on May 28, 1998, describes a method for estimating the offered load on the upstream of an HFC (Hybrid Fiber Coaxial) cable. The estimate is susceptible to degradation due to outliers. A need remains for enhancing the performance of the offered load estimator.

P-0014[0014] Parameter estimators, in general, make use of measured sample observations to determine the values of the parameters to be estimated. The presence of erroneous or misleading sample observations can lead to an unreliable estimation. Methods for identifying and handling sample observations are therefore essential in many estimation problems.

P-0015[0015] As defined in “Outliers in Statistical Data”, 3^rdEdition, Wiley 1994, by V. Barnett and T. Lewis, an observation in a set of data is considered an outlier if it appears to be inconsistent with the remainder of that set of data. Consider a univariate random sample of n observations originating from a distribution F. Suppose that they are ordered such that x(1)<x(2)< . . . <x(n). Observations close to, and including x(1) and x(n), are referred to as extremes. An observation that originates from another distribution H, but not from F, is referred to as a contaminant. There exist statistical methods, named discordancy tests, which can be used to examine an outlier as a potential contaminant, or to determine if an observation is statistically dubious in relation to a given distribution of observations.

P-0016[0016] In multivariate samples, a simple ordering of the multivariate observations in an increasing/decreasing order is inapplicable. One alternative, referred to as “reduced sub-ordering”, is to identify a scalar metric that characterizes the “extremeness” of observations. For example, when the underlying sample distribution is a normal distribution, one could use a quadratic distance measure.

P-0017[0017] Three ways to handle outliers after assessing that they are discordant are presented by V. Barnett, in “Outliers and Order Statistics”, published in Communications Statistics-Theory, 1988. 17 (7), 2109-2118. The first, referred to as “incorporation”, consists of altering the underlying distribution F so that no observation vector appears to be discordant. The second method, referred to as “identification”, uses a discordant outlier to discover a new important characteristic of the corresponding population. The third method, referred to as “rejection”, is to simply reject the observation vector. This rejection method should be utilized when the knowledge of the underlying distribution is very accurate and “inviolable”.

P-0018[0018] In many complex systems, it is often desirable to infer system state information based on a limited number of observations in the system. Specifically, a number of sample observations are made in order to obtain a number of sample values. The number of sample values represents a sample value combination from among a set of possible sample value combinations. Unfortunately, when only a limited number of observations are made, the inferred system state information may or may not be an accurate representation of the true state of the system. In the co-pending U.S. patent application Ser. No. 09/085,749 entitled OFFERED LOAD ESTIMATION AND APPLICATIONS FOR USING SAME IN A COMMUNICATION NETWORK, offered load estimates are susceptible to degradation due to outliers. Therefore, a need remains for a method and a device for controlling outliers in offered load estimation in a shared medium communication network.

SUMMARY OF THE INVENTION

P-0019[0019] In the preferred embodiment of the present invention, a method and device for outlier control of contention outcomes in a shared medium communication network is described which includes collecting a set of sample values being formed using contention outcomes of a plurality of contention intervals and partitioning the set of sample values according to a predetermined scheme the scheme being based on a measure of proximity to a locus of expected sample values, into a set of trusted sample values and a set of untrusted sample values. The untrusted sample values are rejected and the trusted sample values are accepted.

BRIEF DESCRIPTION OF THE DRAWINGS

P-0020[0020] The above-mentioned and other features of the invention will now become more apparent by reference to the following description taken in connection with the accompanying drawings in which:

P-0021[0021]FIG. 1 is a time line depicting a shared channel in accordance with a preferred embodiment of the present invention, with the shared channel divided into successive frames including a contention interval for providing contention access;

P-0022[0022]FIG. 2 is a three-dimensional graph depicting a planar region ABC representing the set of possible contention outcomes in accordance with a preferred embodiment of the present invention;

P-0023[0023]FIG. 3 is a three-dimensional graph showing the locus of expected outcomes within the planar region ABC in accordance with a preferred embodiment of the present invention;

P-0024[0024]FIG. 4 is a two-dimensional graph showing the planar region ABC divided into three regions based on the distance of points from the locus of expected outcomes in accordance with a preferred embodiment of the present invention;

P-0025[0025]FIG. 5 is a three-dimensional graph showing the planar region ABC intersected with three planes S₀, I₀, and C₀in accordance with the present invention;

P-0026[0026]FIG. 6 is a two-dimensional graph showing the planar region ABC intersected with three planes S₀, I₀, and C₀, subdividing ABC into rejection regions and acceptance regions, in accordance with a preferred embodiment of the present invention;

P-0027[0027]FIG. 7 depicts a flowchart of the method for controlling outliers in offered load estimation in a shared medium communication network; and

P-0028[0028]FIG. 8 is a block diagram showing a shared medium communication network in accordance with a preferred embodiment of the present invention.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT

P-0029[0029] As discussed above, a need remains for a method and a device for controlling outliers in offered load estimation in a shared medium communication network. The present invention provides a technique for outlier control that partitions the set of all possible sample value combinations into a set of trusted sample value combinations and a set of untrusted sample value combinations according to some predetermined partitioning scheme. Henceforth, “untrusted”, “unreliable” and “improbable” will be used interchangeably. It should also be noted that the terms “sample value” and “observation point” will be used interchangeably. Various exemplary partitioning schemes are described. If a particular sample value combination falls within the set of trusted sample value combinations, then it is deemed to have a relatively high confidence level. On the other hand, if the sample value combination falls within the set of untrusted sample value combinations, then it is deemed to have a relatively low confidence level.

P-0030[0030] Referring now to FIG. 1, in accordance with one aspect of the present invention, a shared channel time line is shown where a partition of the shared channel <b>100</b> is divided into discrete time slots, and is often referred to as a “slotted channel.” The slotted channel <b>100</b> is organized into successive Frames <b>110</b>, <b>115</b>, etc. (as shown) where each Frame consists of a number of contiguous slots. The number of slots (not shown) in each frame, can be fixed or variable. In the preferred embodiment, k represents the index of the k^thframe on the shared channel time line. Henceforth, “Frame k” <b>110</b> denotes the Frame whose index is k and “Frame k−1” <b>115</b> denotes the Frame whose index is k−1.

P-0031[0031] In the preferred embodiment, T_krepresents the number of slots in Frame k <b>110</b>. A portion of each frame, referred to as the “contention interval k−1” and “contention interval k” <b>120</b>, <b>125</b>, respectively, is used for transmitting requests for contention access, and particularly for placing reservations of bandwidth for subsequent contention-free data transmission <b>130</b>, <b>135</b>. Henceforth, “contention interval k” <b>125</b> denotes the contention interval residing in “Frame k” <b>110</b>. The number of slots in each contention interval <b>120</b>,<b>125</b> can be fixed or variable. In the preferred embodiment, M_krepresents the number of slots in the contention interval k, <b>125</b>. It should be noted that (T_k−M_k) slots in Frame k <b>110</b> are used for contention-free transmission of data upon successful reservation. According to the present invention, assuming that R slots are needed to transmit a request, the contention interval k, <b>125</b> therefore provides M_k/R contention opportunities in which requests can be transmitted. Although M_kis typically selected such that M_k/R is an integer, N_k, there is no requirement that M_kbe so selected, and the value M_k/R is heuristically treated as being a real number for the purpose of simplified analysis. When M_k/R is not an integer, the value of N_kis set to an integer value that is nearest to and smaller than M_k/R.

P-0032[0032] It is to be noted that while the description of the present invention is limited to a slotted shared medium network that utilizes a contention-based reservation scheme for coordinating contention-free data transmission, wherein each transmission frame is divided into a contention interval and a data interval, as discussed above in conjunction with FIG. 1, it is straightforward for a person skilled in the art to apply the invention to a slotted shared medium network that supports contention-based multiple access, wherein each transmission frame is entirely utilized for data contention.

P-0033[0033] In one preferred embodiment of the invention, each contention opportunity in a contention interval, such as contention interval k, <b>125</b>, will result in one of the following contention outcomes: (1) no request transmission; (2) a single request transmission; and (3) multiple request transmissions. When a single request is transmitted in a contention opportunity, the request is considered successful. When multiple requests are transmitted, it is presumed that the requests collide, and are therefore unsuccessful. Therefore, according to the present invention, the three contention outcomes are referred to as IDLE, SUCCESS, and COLLISION, respectively.

P-0034[0034] It should be noted that certain combinations of contention outcomes are more probable than others. For example, it is unlikely (but possible) that there would be all SUCCESS outcomes in a contention interval with no IDLE or COLLISION outcomes. It is also unlikely (but possible) that there would be an equal number of IDLE and COLLISION outcomes with no SUCCESS outcomes in a contention interval. Thus, according to the preferred embodiment of the present invention, the set of all possible combinations of contention outcomes in a contention interval can be divided into two sets: those combinations of contention outcomes that are likely and therefore “trusted”, and those that are unlikely and therefore “untrusted”. If an outcome falls within the set of “trusted” combinations of contention outcomes, then it is used to update the estimated offered load. Otherwise, it can be discounted or completely ignored for the purpose of updating the estimated offered load.

P-0035[0035] Hence, the present invention provides a method and device for defining the sets of “trusted” and “untrusted” combinations of contention outcomes.

P-0036[0036] Referring now to FIG. 2, in accordance with the present invention, I_k, S_k, and C_krespectively denote the number of IDLE, SUCCESS and COLLISION outcomes in frame k <b>110</b> of FIG. 1. A combination of contention outcomes in a Frame k <b>110</b> is referred to by a triplet (I_k, S_k, C_k). An observation point with coordinates specified by the triplet (I_k, S_k, C_k) can be obtained according to an underlying stochastic process that generates transmission attempts with a rate G_kthat is to be estimated. By assuming that the contention message arrival process is a Poisson process, the rate G_kis the only parameter needed to completely characterize that process. Note that the system is gated in the sense that all requests associated with an offered load in a frame must wait at least until the beginning of the next frame before they are allowed to be transmitted. In this respect, rate G_kis the effective offered load in the contention interval of Frame k <b>110</b> due to the offered load in Frame k−1, <b>115</b>. Henceforth, G_kwill be interchangeably referred to as rate G_kand effective offered load G_k.

P-0037[0037] Since a contention outcome can only be an IDLE, SUCCESS or COLLISION, the following equation is necessarily satisfied:

<i>I</i>_k<i>+S</i>_k<i>+C</i>_k<i>=N</i>_k,  Eq. 1

P-0038[0038] with, I_k≧0, S_k≧0 and C_k≧0.

P-0039[0039] Eq. 1 defines a two-dimensional (2-D) Plane P <b>220</b> as shown in shaded section in FIG. 2 in a three-dimensional (3-D) coordinate system with the three axes representing ‘I_k’, ‘S_k’ and ‘C_k’.

P-0040[0040]FIG. 2 depicts the 3-D coordinate system along with Plane P <b>220</b>. Note that Plane P <b>220</b> contains all the possible contention outcomes of a request contention interval in Frame k <b>110</b>. In other words, any observation point (I_k, S_k, C_k) falls inside Plane P <b>220</b>.

P-0041[0041] Referring to FIG. 3, Z(G_k) <b>310</b> denotes an expected observation point, which is determined by the rate G_kunder the Poisson assumption. The associated coordinates (E^I(G_k), E^S(G_k), E^C(G_k)) are given by:

<i>E</i>^I(<i>G</i>_k)=exp(<i>−G</i>_k)×<i>N</i>_k

<i>E</i>^S(<i>G</i>_k)=<i>G</i>_k×exp(−<i>G</i>_k)×<i>N</i>_k

<i>E</i>^C(<i>G</i>_k)=[1−exp(−<i>G</i>_k)−<i>G</i>_k×exp(−<i>G</i>_k)]×<i>N</i>_k

P-0042[0042] wherein E^I(G_k), E^S(G_k), E^C(G_k), respectively denote the expected numbers of IDLE, SUCCESS and COLLISION contention outcomes.

P-0043[0043] Since the expected observation point satisfies Eq. 1 or E^I(G_k)+E^S(G_k)+E^C(G_k)=N_k, it falls inside the Plane P <b>220</b> containing all possible observation points.

P-0044[0044] The credibility of an observation point can be tested based on its proximity to the expected point Z(G_k) <b>310</b>. It should be noted that Curve L <b>320</b>, as depicted in FIG. 3, describes a locus of Z(G_k) <b>310</b>, for G_kranging from zero to infinity. In accordance with the Poisson arrival process model, every observation point on L <b>320</b> corresponds to a unique value of G_k.

P-0045[0045] Since the maximum probability of SUCCESS that can be achieved given the Poisson arrival process model, is equal to 1/e≅0.368, the maximum expected number of SUCCESSes E^S(G_k), out of N_k, is approximately equal to 0.368×N_k. This maximum is achieved for G_k=1. The corresponding point <b>330</b>, Q*≡Z(1)=(0.368×N_k<b>, 0.368×N</b>_k, 0.264×N_k) is shown in FIG. 3.

P-0046[0046] In accordance with the present invention, in order to better understand how Curve L <b>320</b> can be utilized in testing the credibility of an observation point, given that the underlying arrival process is Poisson, it is first assumed that the associated rate G_kis known. It will be recognized that the rate is unknown.

P-0047[0047] If the rate (i.e., effective offered load) is indeed G_k(known), and an infinite number of samples (i.e. N_k→∞) are considered, it is expected that, by the law of large numbers, the observation point inside Plane P <b>220</b> of FIG. 2 coincides with the expected observation point Z(G_k) <b>310</b> on Curve L <b>320</b>. Thus, the observation point asymptotically matches the a-priori knowledge of the arrival process (i.e. Poisson with rate G_k). When N_kis sufficiently small, and hence the law of large numbers does not hold true, such asymptotic matching is very unlikely.

P-0048[0048] Observation points which do not coincide with the expected observation point Z(G_k) <b>310</b>, occur with a probability that is dependent on the position of the observation point in Plane P <b>220</b>. In fact, it is expected that points which do not closely match the a-priori knowledge would occur with low probability and would be considered unreliable.

P-0049[0049] What is assumed known a-priori is that the underlying arrival process is Poisson, but that the true rate G_kis not known. However, if for any value of G_k≧0, the observation point poorly matches the a-priori knowledge, the observation point is considered improbable. An observation point is considered improbable if there exists no G_ksuch that the point matches well the a-priori knowledge about the underlying Poisson arrival process.

P-0050[0050] For instance, the observation point A <b>340</b> in FIG. 3 corresponds to observing SUCCESSes in all the contention opportunities within Frame k <b>110</b>. Obtaining total SUCCESSES is not impossible, but rather unusual because, for any value of the effective offered load G_k, it does not agree with the a-priori knowledge. As another example, the observation point J <b>370</b> in FIG. 3 corresponds to obtaining many COLLISIONS and many IDLES in the contention interval of Frame k <b>110</b>. It is also rather unusual to observe many IDLEs and many COLLISIONs at the same time, with no SUCCESSes at all, for any value of the effective offered load G_k. Therefore, if for any value of the effective offered load G_k, a point has a low probability of occurrence, it can be practically be considered as unreliable.

P-0051[0051] Using the probability of occurrence as a measure for the credibility of the observation point is fairly computationally involved. For this reason, an alternative measure of how well the observation point matches the a-priori knowledge of the expected outcomes represented by Curve L <b>320</b>, is utilized based on the Euclidian distance from the observation point to Curve L <b>320</b>. According to this measurement, it is expected that points that are far (in terms of Euclidian distance) from Curve L <b>320</b>, have a low probability of occurrence for any value of G_k≧0.

P-0052[0052] Assume that the actual effective offered load in Frame k <b>110</b> of FIG. 1 is known to be G_k. Considering the observation point, (I_k, S_k, C_k), as determined by the statistics collected during Frame k <b>110</b>, it would not necessarily coincide with point Z(G_k) <b>310</b>. By letting d_I, d_Sand d_Cbe the disturbances of the coordinates of the observation point with respect to the coordinates of the point Z(G_k) <b>310</b>, that is,

<i>d</i>_I<i>≡I</i>_k<i>−E</i>^I(<i>G</i>_k); <i>d</i>_S<i>≡S</i>_k<i>−E</i>^S(<i>G</i>_k); <i>d</i>_C<i>≡C</i>_k<i>−E</i>^C(<i>G</i>_k),

P-0053[0053] it follows that:

<i>I</i>_k<i>=E</i>^I(<i>G</i>_k)+<i>d</i>_I=exp(−<i>G</i>_k)+<i>d</i>_I

<i>S</i>_k<i>=E</i>^S(<i>G</i>_k)+<i>d</i>_S<i>=G</i>_kexp(−<i>G</i>_k)+<i>d</i>_S

<i>C</i>_k<i>=E</i>^C(<i>G</i>_k)+<i>d</i>_C=[1−exp(−<i>G</i>_k)−<i>G</i>_kexp(−<i>G</i>_k)]+<i>d</i>_C

P-0054[0054] By definition, d²=(d_I)²+(d_S)²+(d_C)², is the squared Euclidian distance from the actual observation point to the expected observation point Z(G_k) <b>310</b> that matches the a-priori knowledge about the arrival process. Clearly, the larger the Euclidian distance d, the greater the magnitude of the error introduced due to the finite number of samples, and thus, the poorer the matching between the observation point and the a-priori knowledge.

P-0055[0055] Consequently, it would be reasonable to set a threshold D and classify as unreliable, observation points whose Euclidian distance d exceeds D. Unfortunately, the Euclidian distance d is not determinable because the actual value of the effective offered load G_kis not known. However, a lower bound d_min<b>420</b> for d can be determined, d_min<b>420</b>, as shown in FIG. 4, being the minimum Euclidian distance from observation point to the Curve L <b>320</b>.

P-0056[0056] Therefore, if d_min<b>420</b> is greater than a certain threshold D, then no matter what the actual value of G_kis, the Euclidian distance d from the observation point to point Z(G_k) <b>310</b> would be greater than this threshold. Therefore, d_min<b>420</b> can also be viewed as a measure of how well the observation point fits the a-priori knowledge. Hence, as d_min<b>420</b> increases, the observation point fits less and less the a-priori knowledge, and if d_min<b>420</b> exceeds some threshold D, the observation point is considered untrusted and will therefore not be used to update the value of the estimator.

P-0057[0057] The shaded regions <b>430</b> and <b>440</b> in FIG. 4 depict the set of observation points whose d_min<b>420</b> from L <b>320</b> exceeds threshold D and thus, would be rejected.

P-0058[0058] In order to determine whether an observation point falls in the shaded (rejection) regions <b>430</b> and <b>440</b>, its minimum Euclidian distance from Curve L <b>320</b> needs to be calculated. This is a computationally involved problem. Hence, it is desirable to determine rejection regions which contain the observation points with a minimum Euclidian distance d_min<b>420</b> from L <b>320</b> exceeding a certain threshold D, and such that testing if an observation point falls in these regions is straightforward. A goal of the present invention is to subdivide Plane P <b>220</b> into an acceptance region R<b>1</b> where the Euclidian distance from the observation point to Curve L <b>320</b> is considered to be small and another rejection region R<b>2</b> where the Euclidian distance from the observation point to Curve L <b>320</b> is considered to be large, while keeping the acceptance/rejection decision making simple.

P-0059[0059] In an attempt to identify acceptance/rejection regions that make the observations classification simple, consider the intersection of Plane P <b>220</b>, with the following three planes, each of which is identified by a constant value of one of the coordinates associated with IDLE, SUCCESS, and COLLISION.

<i>I</i>_k<i>=I</i>₀<i>; S</i>_k<i>=S</i>₀<i>; C</i>_k<i>=C</i>₀

P-0060[0060] The resulting graph is shown in FIG. 5. A corresponding 2-D view of Plane P <b>520</b> is depicted in FIG. 6 for a specific choice of I₀≅0.4×N_k, S₀≅0.4×N_k, and C₀≅0.3×N_k.

P-0061[0061] The rejection region R<b>2</b> is shown in FIG. 6 as the two shaded areas AB″C″ <b>610</b> which corresponds to: S_k>S₀, and the shaded area A′E″D″ <b>612</b> which corresponds to: I_k>I₀and C_k>C₀. It should be noted that the rejection region R<b>2</b>, <b>610</b> and <b>612</b> need not be contiguous. By default, the acceptance region R<b>1</b><b>630</b> is the remaining un-shaded portion within the Plane P <b>520</b>.

P-0062[0062] Note that FIG. 6 suggests that these areas approximate fairly well the rejection regions <b>430</b> and <b>440</b> based on the Euclidian distance criterion shown in FIG. 4. Therefore, the un-shaded acceptance region R<b>1</b><b>630</b> in FIG. 6 and the shaded rejection region R<b>2</b><b>610</b> and <b>620</b> in FIG. 6 are determined as follows:

R<b>2</b>≡(A′E″D″∪AB″C″) and R<b>1</b>≡(ABC∩(R<b>2</b>)^C).

P-0063[0063] The following examples illustrate how observation points that fall in the shaded (rejection) regions, <b>610</b> and <b>612</b> in FIG. 6, have a low probability of occurrence for any value of G_k, and at the same time, have a relatively large Euclidian distance d_min<b>420</b> from Curve L <b>320</b>.

P-0064[0064] For instance, area A′E″D″, [I_k>I₀and C_k>C₀], <b>612</b> shown in FIG. 6, corresponds to obtaining many COLLISIONs and many IDLEs in the request contention interval within Frame k <b>110</b>. This combination of contention outcomes is improbable whatever the value of the effective offered load is. Therefore, observation points that fall in this region match poorly the a-priori knowledge of the arrival process (for any value of the rate G_k). It should be noted that the Euclidian distance between Curve L <b>320</b> and observation points that fall in this area is relatively large.

P-0065[0065] Area AB″C″, [S_k>S₀], <b>610</b> corresponds to the case of many SUCCESSes, few COLLISIONs and few IDLEs, with a probability of SUCCESS higher than 0.368. Although this is usually a very desirable operating point, it is improbable. Therefore, observation points that fall in this region match poorly the a-priori knowledge (for any value of the rate G_k). It should be noted that the Euclidian distance between Curve L <b>320</b> and observation points that fall in this area is relatively large.

P-0066[0066] It should also be noted that although the description of the above embodiment of the present invention is limited to a contention-based system utilizing ternary feedback, it is straightforward for a person skilled in the art to extend the invention to apply to a contention-based system utilizing an n-array feedback, where n≧2.

P-0067[0067] In general, one can consider the following feedback state of the system in a Frame k <b>110</b> using the following feedback vector:

F_k=(F_k(0), F_k(1), F_k(2), . . . , F_k(n−1))

P-0068[0068] where F_k(j), for j=0, 1, 2, . . . , n−2, represents the number of contention slots in each of which exactly j users transmit, and F_k(n−1) represents the number of contention slots in which at least n−1 users transmit. Given N_kcontention opportunities within Frame k <b>110</b>, it is necessary that: <maths id="MATH-US-00001" num="1"><math overflow="scroll"><mrow><mrow><munderover><mo>∑</mo><mrow><mi>j</mi><mo>=</mo><mn>0</mn></mrow><mrow><mi>n</mi><mo>-</mo><mn>1</mn></mrow></munderover><mo></mo><mrow><msub><mi>F</mi><mi>k</mi></msub><mo></mo><mrow><mo>(</mo><mi>j</mi><mo>)</mo></mrow></mrow></mrow><mo>=</mo><msub><mi>N</mi><mi>k</mi></msub></mrow></math><img file="US20030193903A1-20031016-M00001.TIF" id="EMI-M00001" he="25.9119" wi="216.027" img-format="tif" img-content="mf" /><attachments><attachment idref="MATHEMATICA-00001" attachment-type="nb" file="US20030193903A1-20031016-M00001.NB" /></attachments></maths>

P-0069[0069] With the following mapping, this general framework degenerates to the system utilizing ternary feedback, whereby:

F_k(0)→I_k

F_k(1)→S_k

F_k(2)→C_k

Outlier Control

P-0070[0070] The method for controlling outliers in offered load estimation is described by the flowchart in FIG. 7. Prior to the first contention interval, the system is at Step <b>710</b>. As contention intervals pass on the shared channel time line <b>100</b> of FIG. 1, the system collects the contention outcomes of the contention opportunities (Step <b>720</b>). At the end of each contention interval, the sample value, corresponding to the contention outcomes of the contention interval, is generated and located on Plane P <b>520</b> of FIG. 5 (Step <b>730</b>). Then at Step <b>740</b>, the system determines if the sample value falls in the un-shaded acceptance region R<b>1</b><b>630</b> of FIG. 6. This determination is made based upon the number of IDLES exceeding the IDLE I₀threshold and the number of COLLISIONS exceeding the COLLISION C₀threshold or the number of SUCCESSES exceeding the SUCCESS S₀threshold.

P-0071[0071] The following boolean expression defines the above determination:

(S_k>S₀)∥(I_k>I₀&&C_k>C₀)

P-0072[0072] as depicted in Step <b>740</b>.

P-0073[0073] At Step <b>750</b>, if the above expression is true, the sample value falls within the acceptance region R<b>1</b><b>630</b> of FIG. 6 and the sample value is used to estimate the offered load (Step <b>760</b>). Subsequently, the system returns to Step <b>720</b> to re-start the process of collecting contention outcomes. If the sample value falls in the rejection region R<b>2</b>, shaded regions <b>610</b> and <b>612</b> in FIG. 6, the sample value is therefore not used to estimate the offered load and the system returns to Step <b>720</b> to re-start the process of collecting contention outcomes.

Some Applications Utilizing Estimated Offered Load with Outlier Control

P-0074[0074] The method of estimating offered load as shown in Step <b>760</b> of FIG. 7 in a communication network has many applications. One important application utilizes the estimated offered load to improve access performance in a shared medium communication network. Specifically, the estimated offered load is used for determining certain operating parameters such as the number of contention opportunities per frame and certain access mode parameters that affect how the network is accessed.

P-0075[0075]FIG. 8 shows a generic shared medium communication network <b>800</b> in accordance with a preferred embodiment of the present invention. The shared medium communication network <b>800</b> allows a number of end users <b>810</b>₁through <b>810</b>_Nto access a remote external network <b>808</b> such as the Internet. The shared medium communication network <b>800</b> acts as a conduit for transporting information between the end users <b>810</b> and the external network <b>808</b>.

P-0076[0076] The shared medium communication network <b>800</b> includes a primary station <b>802</b> that is coupled to the external network <b>808</b>. The preferred embodiment of the present invention described in the algorithm of FIG. 7 applies to an offered load estimator residing in the primary station <b>802</b>. The primary station <b>802</b> is in communication with a plurality of secondary stations <b>804</b>₁through <b>804</b>_N(collectively referred to as “secondary stations 804” and individually as a “secondary station 804”) by means of channels <b>806</b> and <b>807</b>. Channel <b>806</b> carries information in a “downstream” direction from the primary station <b>802</b> to the secondary stations <b>804</b>, and is hereinafter referred to as “downstream channel 806.” Channel <b>807</b> carries information in an “upstream” direction from the secondary stations <b>804</b> to the primary station <b>802</b>, and is hereinafter referred to as “upstream channel 807. ” Each end user <b>810</b> interfaces to the shared medium communication network <b>800</b> by means of a secondary station <b>804</b>.

P-0077[0077] In an exemplary embodiment, the shared medium communication network <b>800</b> is a data-over-cable (DOC) communication system wherein the downstream channel <b>806</b> and the upstream channel <b>807</b> are separate channels carried over a shared physical medium. In the preferred embodiment, the shared physical medium is a hybrid fiber-optic and coaxial cable (HFC) network. The downstream channel <b>806</b> is one of a plurality of downstream channels carried over the HFC network. The upstream channel <b>807</b> is one of a plurality of upstream channels carried over the HFC network. In other embodiments, the shared physical medium may be coaxial cable, fiber-optic cable, twisted pair wires, and so on, and may also include air, atmosphere, or space for wireless and satellite communication. Also, the various upstream and downstream channels may be the same physical channel, for example, through time-division multiplexing/duplexing, or separate physical channels, for example, through frequency-division multiplexing/duplexing.

P-0078[0078] In the shared medium communication network <b>800</b> of the preferred embodiment, the downstream channels, including the downstream channel <b>806</b>, are typically situated in a frequency band above approximately 50 MHz, although the particular frequency band may vary from system to system, and is often country-dependent. The downstream channels are classified as broadcast channels, since any information transmitted by the primary station <b>802</b> over a particular downstream channel, such as the downstream channel <b>806</b>, reaches all of the secondary stations <b>804</b>. Any of the secondary stations <b>804</b> that are tuned to receive on the particular downstream channel can receive the information.

P-0079[0079] In the shared medium communication network <b>800</b> of a preferred embodiment, the upstream channels, including the upstream channel <b>807</b>, are typically situated in a frequency band between approximately 5 through 42 MHz, although the particular frequency band may vary from system to system, and is often country-dependent. The upstream channels are classified as shared channels, since only one secondary station <b>804</b> can successfully transmit on a particular upstream channel at any given time, and therefore the upstream channels must be shared among the plurality of secondary stations <b>804</b>. If more than one of the secondary stations <b>804</b> simultaneously transmit on a particular upstream channel, such as the upstream channel <b>807</b>, there is a COLLISION that corrupts the information from all of the simultaneously transmitting secondary stations <b>804</b>.

P-0080[0080] In order to allow multiple secondary stations <b>804</b> to share a particular upstream channel, such as the upstream channel <b>807</b>, the primary station <b>802</b> and the secondary stations <b>804</b> participate in a medium access control (MAC) protocol. The MAC protocol provides a set of rules and procedures for coordinating access by the secondary stations <b>804</b> to the shared upstream channel <b>807</b>. Each secondary station <b>804</b> participates in the MAC protocol on behalf of its end users. For convenience, each participant in the MAC protocol is referred to as a “MAC User.”

P-0081[0081] In one embodiment, the MAC protocol includes a protocol commonly referred to as Multimedia Cable Network System (MCNS), which is defined in the document entitled MCNS Data-Over-Cable Service Interface Specifications Radio Frequency Interface Specification SP-RFI-I02-971008 Interim Specification (hereinafter referred to as the “MCNS Protocol Specification”), incorporated herein by reference in its entirety. In the MCNS Protocol Specification, the primary station <b>802</b> is referred to as a Cable Modem Termination System (CMTS), and the secondary stations <b>804</b> are referred to as Cable Modems (CMs). The CMTS is responsible for packet processing, resource sharing, and management of the MCNS MAC and Physical layer functions. Each CM operates as a slave to the CMTS. MAC Protocol Data Units (PDUs) transmitted on the downstream channel <b>806</b> by the CMTS may be addressed to an individual CM via unicast, or to a selected group of CMs via multicast or broadcast. In the upstream channel, a MAC PDU may be sent by any CM to the CMTS. MCNS supports variable length MAC PDUs.

P-0082[0082] The MCNS Protocol Specification utilizes a slotted upstream channel, such that the upstream channel <b>807</b> is divided into successive time slots. The MAC protocol supports a plurality of slot types for carrying different types of information. Each time slot is capable of transporting a unit of information (for example, a data packet or a control packet). The MCNS Protocol Specification further divides the upstream channel <b>807</b> into successive frames, where each frame includes a number of slots. The CMTS allocates bandwidth to a group of CMs by transmitting on the downstream channel <b>806</b> a control message containing a bandwidth allocation information element known as a MAP. The MAP specifies the allocation of transmission opportunities within a given transmission frame. Bandwidth is allocated, frame by frame, in terms of transmission opportunities for contention-based reservation requests (or simply requests) as well as for user data. A successful transmission in a contention opportunity results in the reservation of a future data transmission opportunity.

P-0083[0083] More specifically, the upstream channel <b>807</b> is modeled as a stream of mini-slots, providing for TDMA at regulated time ticks. The use of mini-slots implies strict timing synchronization between the CMTS and all the CMs. Hence, the CMTS is responsible for generating the time reference to identify these mini-slots and periodically allow for ranging opportunities so that all CMs maintain their synchronization. The access to the mini-slots by the CMs is controlled by the CMTS. To accomplish that, the CMTS transmits on the downstream channel a MAP describing the use of each upstream mini-slot in a specified future time interval. This message, in a way, “maps” in a future time interval each mini-slot to its use. Of course, the MAP has to be sent by the CMTS earlier than the effective time interval that it describes in order to allow enough time for the CMs to transmit in the mapped mini-slots.

P-0084[0084] In the MCNS Protocol Specification, each frame is organized into discrete intervals. At least three different interval types are defined. A contention interval includes a number of mini-slots that are allocated for transmitting requests (or small data packets) in contention mode. A maintenance interval includes a number of mini-slots allocated for registration of CMs. A data grant interval includes a number of mini-slots allocated for transmitting data packets. The MAP includes a number of information elements (lEs) that define the different intervals in the frame.

P-0085[0085] An important consideration that affects performance in the MCNS MAC protocol is the number of mini-slots allocated to the contention interval in each frame. The number of mini-slots allocated to the contention interval affects the number of mini-slots allocated to the other intervals, particularly the data interval. A large number of mini-slots allocated to the contention interval decreases the likelihood of COLLISIONs, but also decreases the number of mini-slots allocated for transmitting data and therefore decreases the data throughput of the system. Furthermore, a small number of mini-slots allocated to the contention interval can increase the likelihood of COLLISIONs and therefore decrease the data throughput of the system by preventing successful requests from reaching the CMTS. In an exemplary embodiment, the number of slots in the contention interval is selected to maximize the likelihood of SUCCESS outcomes. This typically involves increasing the number of slots in the contention interval if the offered load is high, and decreasing the number of slots in the contention interval if the offered load is low. Thus, the offered load is a key consideration in selecting the number of slots per contention interval.

P-0086[0086] Another important consideration that affects performance in the MCNS MAC protocol is the type of contention access used. In accordance with the MCNS Protocol Specification, at least two types of contention access is supported. In a first type of contention access, the secondary stations <b>804</b> are only permitted to transmit request messages during the contention interval. In a second type of contention access, the secondary stations <b>804</b> are permitted to transmit either request messages or small data messages during the contention interval. The second type of contention access can improve performance when there are few COLLISIONs, but can decrease performance when there are many COLLISIONs. Therefore, the second type of contention access would only be utilized when the actual offered load is low, where the first type of contention access would be used when the actual offered load is high. Thus, the offered load is a key consideration in selecting the type of contention access in the MCNS MAC protocol.

P-0087[0087] It should be noted that this invention might be embodied in software, firmware and/or hardware. The software and/or firmware might be stored on a computer usable medium, such as a computer disk or memory chip.

P-0088[0088] While the invention has been described in conjunction with a specific embodiment thereof, additional advantages and modifications will readily occur to those skilled in the art. The invention, in its broader aspects, is therefore not limited to the specific details, representative apparatus, and illustrative examples shown and described. Various alterations, modifications and variations will be apparent to those skilled in the art in light of the foregoing description. Thus, it should be understood that the invention is not limited by the foregoing description, but embraces all such alterations, modifications and variations in accordance with the spirit and scope of the appended claims.