Multiplex communications – Channel assignment techniques – Combining or distributing information via time channels...
Reexamination Certificate
2000-09-01
2003-03-04
Olms, Douglas (Department: 2661)
Multiplex communications
Channel assignment techniques
Combining or distributing information via time channels...
C270S052160, C270S052160
Reexamination Certificate
active
06529520
ABSTRACT:
FIELD OF THE INVENTION
The invention relates generally to communication systems, and more particularly to scheduling for bandwidth allocation in a shared medium communication network that employs a contention-based reservation mechanism for coordinating channel access.
BACKGROUND OF THE INVENTION
Communication networks and technologies have been evolving rapidly to meet current and future demands for efficient remote information exchange and high-speed Internet access. In some communication networks, referred to as shared medium networks, transmission resources are shared among a population of users. In a shared medium network, users independently access the network via stations, and uncoordinated transmissions from different stations may interfere with one another. Such a 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.
Protocols that are employed to coordinate access to a shared channel are often referred to as Medium Access Control (MAC) protocols. MAC protocols fall into two basic categories: contention-based and contention-free protocols. In contention-based protocols, end 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. 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.
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. The behavior and performance of Unslotted Aloha have been studied widely, and its maximum throughput is well known to be 1/(2e). A later version of the Aloha protocol, which operates with discrete or slotted time, is referred to as Slotted Aloha. 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 i.e., the number of packet arrivals per packet transmission opportunity, which is a function of n that denotes the number of backlogged users at the beginning of a given time slot. It follows that the maximum throughput of Slotted Aloha is 1/e=0.368, which is attained when G(n)=1, i.e. one packet arrival per packet transmission opportunity. The constant e is the base for natural logarithm. It is to be noted that the value 1/e reflects the efficiency of Slotted Aloha, as it indicates on the average one successful packet transmission every e packet transmission opportunities.
Most contention-based protocols, including the Aloha protocols, resolve collisions by using feedback information on the number of users involved in the collisions. Based on this feedback information, each backlogged user executes a predetermined back off strategy to ensure stable operation of the protocol. In practice, feedback information used is typically ternary indicating zero, one, or more transmissions, or binary indicating exactly one transmission or otherwise.
It is well known that ordinary Slotted Aloha is unstable. Various methods for stabilizing Slotted Aloha exist, and many of them resort to adaptive control of the back off 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 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 (Rivest, “Network Control by Bayesian Broadcast,” technical report MIT/LCS/TM-287, MIT Lab. for Computer Science, 1985). A minimum mean-squared error predictor for estimating the channel backlog in Slotted Aloha was proposed by Thomopoulos for regulating the retransmission probability according to a recursive function of the channel backlog estimate (Thomopoulos, “A Simple and Versatile Decentralized Control for Slotted Aloha, Reservation Aloha, and Local Area Networks,” IEEE Trans. on Communications, Vol. 36, No. 6, June 1988).
In a contention-free multiple access protocol with static scheduling, such as that of a Time Division Multiple Access (TDMA) scheme, a predetermined transmission pattern is repeated periodically. The users may access channel resources only during the time intervals assigned to them individually. Contention-free protocols with static scheduling for resource allocation are inefficient for supporting a large population of users where, typically, only a fraction of the users are active at any time. In a contention-free multiple access protocol with adaptive scheduling, the transmission pattern may be modified in each cycle, via reservation, to accommodate dynamic traffic demand. A reservation scheme typically requires a centralized controller to manage reservations. A fraction of the channel, or a separate channel, is often used to support the overhead due to reservation.
It has been known that reservation protocols with contention-based transmission of request messages are particularly suitable for a shared medium communication system in which there is a large population of bursty users with long messages. This is the case in a Hybrid Fiber Coaxial Cable Network with a Cable TV headend coupled through an optical fiber mode to a two way coaxial amplifier to which are attached a number of cable modems.
In the prior art, the channel is modeled as a stream of transmission slots of a fixed size. The channel is divided into frames, wherein the number of transmission slots in each frame is fixed. Each frame consists of a contention interval, and a data interval. Each contention interval contains a number of contention slots that are allocated for contention-based transmission of reservation packets in accordance with the Slotted Aloha protocol. Each reservation packet carries appropriate control information including the number of data slots requested. Each data interval contains a number of data slots that are allocated for transmission of reserved data packets. Depending on the granularity of the transmission slots, a contention slot may be an integral fraction of a transmission slot or an integral multiple of a transmission slot. Typically, the granularity of the transmission slots is selected such that a data slot is either a single transmission slot or an integral multiple of a transmission slot. In any case, a contention slot is typically much smaller than a data slot.
Szpankowski teaches a frame-based contention-based reservation system, wherein Slotted Aloha is used to coordinate transmission of reservation requests and each successful request transmission in a frame reserves a data slot in a data interval of a future frame. In accordance with the teaching of Szpankowski, provided the sizes of each frame and the two intervals in it are respectively fixed, system throughput in the steady state is maximized when the ratio of the number of data slots in each frame to the number of contention slots in the same frame is equal to 1/e, which is the throughput of Slotted Aloha (Wojciech Szpankowski, “Analysis and Stability Considerations in a Reservation Multiaccess System,” IEEE Trans. Communications, Vol. COM-31, No. 5, May 1983). In other words, the number of contention slots allocated in a frame must be such that the ratio of the
Abi-Nassif Firass
Lee Whay Chiou
Bawel Paul F.
Olms Douglas
Phunkulh Bob A.
LandOfFree
Method and device for bandwidth allocation in multiple... 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 bandwidth allocation in multiple..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and device for bandwidth allocation in multiple... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3024521