Multiplex communications – Channel assignment techniques – Using time slots
Reexamination Certificate
1998-08-28
2004-04-27
Ton, Dang (Department: 2666)
Multiplex communications
Channel assignment techniques
Using time slots
C370S228000, C370S347000
Reexamination Certificate
active
06728257
ABSTRACT:
FIELD OF THE INVENTION
The present invention generally concerns base and host wireless shared channel packet communication networks. The method of the invention more specifically concerns channel scheduling among contending hosts in such base and host wireless shared channel packet communication networks.
BACKGROUND OF THE INVENTION
A basic problem in shared resource communication is the need to allocate the resource between competing hosts which utilize the resource. In wired communication networks, such as local area networks (LANs), metropolitan area networks (MANS), and wide area networks (WANs), physical layer and medium access layer portions of the network protocol resolve contentions between competing nodes, or hosts, which seek communication access over the physical wire which is the backbone of the network. Token passing, in which a token is passed around a ring and the host possessing the token is permitted to communicate, is an example of contention resolution.
As wired networks have evolved, however, token passing and other straightforward arrangements have been recognized as having inherent inefficiencies in the allocation of network communication bandwidth. Typical Ethernet and similar commercially available switches use a first-in-first out packet queueing arrangement. Inefficiencies in such techniques have lead to development of wired network fair queuing models that seek to fairly allocate the shared resource taking into account the amount, or weight, of traffic associated with each host seeking access. The basis for such networks is a fluid flow model, which seeks to model each packet flow as a fluid pipe. Heavily weighted packet flows see larger access availability without denying or foreclosing some access to the shared wire resource to less weighted packet flows.
Future indoor and outdoor packet cellular environments will seek to support communication-intensive applications currently supported primarily by wired networks, such as multimedia teleconferencing and world wide web browsing. Supporting such applications requires the wireless network to provide sustained quality of service to packet flows over scarce and shared wireless networking resources. In wired networks, quality of service requirements are typically satisfied by a combination of resource reservation (at the flow level) and fair resource allocation/packet scheduling (at the packet level).
Various fair queuing models have been previously proposed for wired networks. These are based upon an assumption of an error free and constant capacity communication medium. A popular model for packet scheduling over a wired link is the fluid fair queueing model. In this model, packet flows are modeled as fluid flows through a channel of capacity C, and every flow f is assigned a weight r
f
; over any infinitesimally small window of time [t, t+&Dgr;t], a backlogged flow f is allocated a channel capacity of C(t).&Dgr;t.(r
f
/&Sgr;
i&egr;B(t)
r
i
), where B(t) is the set of flows that are backlogged at time t and C(t) is the channel capacity at time t. There are several known packet-level algorithmic implementations of this model, such as WFQ, WF
2
Q, SCFQ, STFQ, etc. Essentially, the goal of each of these algorithms is to serve packets in an order that approximates fluid fair queueing as closely as possible. All of these algorithms assume that the channel is error-free, or at least that either all flows can be scheduled or none of them can be scheduled.
Such assumptions are invalid in wireless media. Wireless media are prone to various types of errors that violate the error free and constant capacity assumptions. Bursty errors are typically caused by external interference and prevent effective communication for a limited period of time. Location dependent errors arise from interference or fading path associated with hosts in a particular geographic area, frequently at the edge of a base's communication range. Hidden/exposed host errors arise from stations which are within receiver range but outside of transmitter range or vice versa. Since wireless transmissions are locally broadcast, contention and effective channel capacity are location-dependent, which impedes application of the model to wireless communications. Interference, fades, multipath effects, and channel errors are also location-dependent in wireless communications. This implies that at any time, only a subset of flows can be scheduled on the channel. Thus, in packet cellular environments, user mobility and wireless channel error are significant impediments to both resource reservation and fair packet scheduling.
Another unique concern in packet cellular networks is that within a cell, every host is only guaranteed to be within the range of the base station, and all transmissions are either uplink or downlink. Thus, the base station is the only logical choice for the scheduling entity in a cell. However, the base station has only limited knowledge about the arrival of packets in uplink flows. In particular, the base station may know if an uplink flow has any outstanding packets, but it does not know when packets arrive, or how many packets there are in the queue at any instant. Thus it cannot be assumed that convenient tagging mechanisms accompany packet arrivals, as assumed in most wired medium fair queueing algorithms.
Accordingly, there is a need for an improved base and host wireless shared channel network packet communication method which accounts for the aforementioned difficulties. There is a further need for an improved communication method which extends benefits of fluid modeled wired communication shared resource contention into wireless communication networks and accounts for errors inherent to wireless communication media.
SUMMARY OF THE INVENTION
These and other needs are met or exceeded by the present base and host wireless shared channel network packet communication method. Lagging communication flows, typically caused by burst errors in wireless communication systems, make up for their lag by causing leading flows to give up their lead. In a preferred embodiment, lag compensation is accounted for by a service tag which identifies a precedence for contention based upon the previous denial of access for channel error. This precedence allows compensation when channels become error free. A modified preferred embodiment first attempts intraframe compensation by swapping slots when a host predicts an error for its assigned slot and another host assigned a later slot is able to transmit in the slot for which the error was predicted. Interframe compensation, when needed, is accomplished preferably by a round robin contention among backlogged flows. Errors are predicted by hosts for a subsequent slot when activity is sensed in a current slot but no good packet is received. Preferred packet structures include data and control slots, with data slots partitioned to provide necessary error status and backlog information piggybacked with data so a base has sufficient information to implement compensation in contention resolution.
REFERENCES:
patent: 5001703 (1991-03-01), Johnson et al.
patent: 5184347 (1993-02-01), Farwell et al.
patent: 5195090 (1993-03-01), Bolliger et al.
patent: 5195091 (1993-03-01), Farwell et al.
patent: 5206881 (1993-04-01), Messenger et al.
patent: 5260944 (1993-11-01), Tomabechi
patent: 5299199 (1994-03-01), Wilson et al.
patent: 5303234 (1994-04-01), Kou
patent: 5438565 (1995-08-01), Hemmady et al.
patent: 5473602 (1995-12-01), McKenna et al.
patent: 5475681 (1995-12-01), White et al.
patent: 5483671 (1996-01-01), Helm et al.
patent: 5515379 (1996-05-01), Crisler et al.
patent: 5583869 (1996-12-01), Grube et al.
patent: 5666348 (1997-09-01), Thornberg et al.
patent: 5708655 (1998-01-01), Toth et al.
patent: 5726984 (1998-03-01), Kubler et al.
patent: 5742588 (1998-04-01), Thornberg et al.
patent: 5752166 (1998-05-01), Dorenbosch et al.
patent: 5901226 (1999-05-01), Brenner et al.
patent: 5923648 (1999-07-01), Dutta
patent: 5926458 (1999-07-01), Yin
patent: 5987021 (1999-11-01), Erickson et al.
p
Bharghavan Vaduvur
Lu Songwu
Srikant Rayadurgam
Greer Burns & Crain Ltd.
The Board of Trustees of the University of Illinois
Ton Dang
Tran Phuc
LandOfFree
Fluid flow fair scheduling emulation in wireless shared... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Fluid flow fair scheduling emulation in wireless shared..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fluid flow fair scheduling emulation in wireless shared... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3229686