Multiplex communications – Channel assignment techniques – Carrier sense multiple access
Reexamination Certificate
1998-05-29
2001-04-24
Patel, Ajit (Department: 2661)
Multiplex communications
Channel assignment techniques
Carrier sense multiple access
C370S461000, C370S462000, C710S119000
Reexamination Certificate
active
06222851
ABSTRACT:
TECHNICAL FIELD
This invention relates to local area network technology, and more particularly to a contention resolution media access control protocol for a local area network using orthogonal frequency division multiplexing.
BACKGROUND
Local area networks (LANs) allow multiple users (or “nodes”) to utilize a shared media to transmit and receive digital information. The concept of a LAN is so useful that attempts are being made to extend LAN technology to Digital Subscriber Line (DSL) communication systems. DSL systems use existing telephone lines for high speed data communications. A DSL system essentially encodes digital data as analog signals at very high data rates using special modems. One signaling method used to transmit such analog signals is orthogonal frequency division multiplexing (OFDM), in which analog encoded data bits are transmitted as complex tones in distinct frequency bins.
A number of Digital Subscriber Line (DSL) systems have been proposed. For example, a version known as Asymmetric Digital Subscriber Line (ADSL) provides a system that applies signals over a single twisted-wire pair that supports “plain old telephone service” (POTS) and high-speed duplex (simultaneous two-way) and simplex (from a network to the customer installation) digital services. Part of the proposed standard for ADSL is set forth in the Draft Proposed Revision of ANSI T1. 413-1995—Interface Between Networks and Customer Installation—Asymmetric Digital Subscriber Line (ADSL) Metallic Interface (Sep. 26, 1997), which is hereby incorporated by reference.
In order to permit sharing of a LAN media, a media access control (MAC) protocol must resolve “contention” between the users seeking to access the media simultaneously. In a media such as DSL systems, a variety of possible MAC protocols may be used. For example, each node on the network can synchronize transmissions based on simultaneous detection of silence (i.e., no node is currently transmitting data). However, DSL systems are inherently noisy due to cross-talk in telephone wiring bundles, reflections, etc. Further, the wiring environment within a home may be particularly “hostile”, with unterminated telephone extensions of various lengths causing reflections. Accordingly, silence is not easily detectable, and positive identification of idle media may be difficult or impossible to achieve.
Another technique is described in co-pending U.S. patent application No. 09/003,844, entitled “Method and Protocol for a Medium Access Control Layer for Local Area Networks with Multiple-Priority Traffic”, filed Jan. 7, 1998 and assigned to the assignee of the present invention. In this technique, each node waits for a certain period of silence, then transmit a single randomly selected tone as an intent-to-transmit signal. All nodes receive the combined intent-to-transmit signals of all other signals. Each station makes a determination as to whether it had transmitted the highest frequency, and if so, begins to transmit data. If two or more stations had sent the same frequency as an intent-to-transmit signal, a collision will occur, indicated by the presence of garbled data on the medium. The colliding nodes stop transmitting data and repeat the process above until no collisions exist. A drawback of this technique is that each transmitting node must “listen” to what it is transmitting to detect a collision, which requires data demodulation. Data demodulation requires a substantial expenditure of processing resources and complex processing.
Accordingly, the invention has determined that it would be useful to have a contention resolution MAC protocol that is simple to implement, provides positive identification of idle media, and does not require data demodulation. The present invention provides a method and system for achieving this end.
SUMMARY
The invention uses an adaptive tree-based contention resolution media access control protocol that includes multiple contention phases. Each node transmitter performs simple tone detection while transmitting, but is not required to perform data demodulation to detect collisions.
More particularly, the preferred embodiment of the invention uses constant tones in OFDM frequency bins to resolve contention between multiple transmitting nodes. All nodes are roughly synchronized to transmit “contention tones” in a “contention frame.” Each node is assigned a unique identification (ID) number, and this ID number is mapped to frequency bins by transmitting a tone in each bin corresponding to each 1-bit in the binary representation of the node's ID number. The result of multiple nodes each transmitting its unique ID during a contention frame is a complex frequency signal.
After the contention frame has completed, each participating node decodes the complex frequency signal such node received while it was transmitting. Following the “contention frame”, all nodes participate in a “resolution frame” in which all nodes again transmit tones in frequency bins. However, the tones transmitted by a node in a resolution frame correspond only to tones in which the result of the contention frame indicated the presence of a tone where such node had 0-valued ID bits. In other words, a node transmits 1-bits in frequency bins corresponding to positions where the contention frame turned 0-bits of its ID into 1-bits.
All nodes receive the results of the resolution frame and record the results (called “resolution bits”) in a reasonably-balanced binary tree. If the resolution frame contained no tones in any frequency bin, one and only one node is contending and can transmit. Otherwise, the contending nodes utilize the resolution bits to continue with another cycle of contention and resolution frames to divide the contenders and resolve contention. In the preferred embodiment, after transmitting, a node refrains from entering into contention/resolution cycles until all currently contending nodes have been able to transmit. In the preferred embodiment, each node follows a tree-traversal algorithm to determine the order of transmission among all contending nodes. When the last node transmits, the contention process is complete and all contending nodes have transmitted their frames. In addition, all non-contending nodes monitor the contention/resolution process to determine when they may participate in a next set of contention/resolution cycles.
The details of one or more embodiments of the invention are set forth in the accompanying drawings and the description below. Other features, objects, and advantages of the invention will be apparent from the description and drawings, and from the claims.
REFERENCES:
patent: 4493074 (1985-01-01), Walter et al.
patent: 4593282 (1986-06-01), Acampora et al.
patent: 4817080 (1989-03-01), Soha
patent: 4855997 (1989-08-01), Wilson et al.
patent: 5651009 (1997-07-01), Perreault et al.
patent: 5968154 (1999-10-01), Cho
patent: 5978414 (1999-11-01), Nara
patent: 6111888 (2000-08-01), Green et al.
3Com Corporation
Fish & Richardson P.C.
Patel Ajit
Phunkulh Bob A.
LandOfFree
Adaptive tree-based contention resolution media access... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Adaptive tree-based contention resolution media access..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Adaptive tree-based contention resolution media access... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2530229