Multiplex communications – Channel assignment techniques – Carrier sense multiple access
Reexamination Certificate
1999-08-27
2004-10-05
Ton, Dang (Department: 2666)
Multiplex communications
Channel assignment techniques
Carrier sense multiple access
C370S447000
Reexamination Certificate
active
06801538
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The invention relates generally to communication systems, and more particularly to controlling outliers in offered load estimation in a shared medium communication network.
2. Discussion of Related Art
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.
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.
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.
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.
An example of a contention-based MAC protocol is known as an ALOHA protocol. Its original version, which operates with continuous or unspotted 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.
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.
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.
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.
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.
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.
As defined in “Outliers in Statistical Data”, 3
rd
Edition, 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.
In multivariate samples, a simple ordering of the multivariate observations in an increasin
Abi-Nassif Firass
Lee Whay Chiou
Coker Caroline
Motorola Inc
Ton Dang
Tran Phuc
LandOfFree
Method and device for controlling outliers in offered load... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and device for controlling outliers in offered load..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and device for controlling outliers in offered load... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3302698