Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
1998-11-23
2002-11-12
Yao, Kwang Bin (Department: 2664)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S252000, C370S278000
Reexamination Certificate
active
06480497
ABSTRACT:
BACKGROUND OF THE INVENTION
This invention relates to packet communications in a radio-based mesh network, and in particular to techniques for improving throughput of packets via such a network.
In a mesh network, there is an collection of nodes which autonomously connect, send, receive, forward and analyze packetized traffic in the network, which is a shared resource having limitations on traffic capacity. There is a need to optimize performance throughput to the greatest number of users in the network. Heretofore, the nodes have been able to develop performance metrics about themselves and their neighboring nodes which can prove useful in developing throughput improvement schemes. Due to a large installed base of nodes, it is important that new nodes be made backwards compatible with previously installed nodes so that the older nodes are not rendered inoperable.
Mesh packet radio networks are used throughout the world to provide data communication between nodes. These networks are one of several type of data communication network architectures (the other major types being star (e.g., conventional wireline and cellular) and bus (e.g., computer backplane and cable television) and have several advantages over other architectures for providing high capacity data communication over a large area and to a large number of users.
When known radio mesh networks communicate, the radios use a single data rate among all radio that can communicate. There are at least two reasons for using a single data rate:
Hardware simplicity. If the modulation and demodulation hardware operates at but one data rate, it is often much easier and less expensive to implement.
Protocol simplicity. A broadcast on-air protocol supporting only a single data rate is much simpler to design and implement than one intending to coordinate multiple data rates (and, sometimes equivalently, occupied bandwidth) among a plurality of communicating nodes.
Use of a single data rate has permitted implementation of several successful networks, e.g. Metricom's Ricochet data communication network. These networks occupy a spectra, collect, transport and deliver packets at an acceptable level of performance. This level of performance is in many respects limited by the speed of the constituent links. Extending the performance of these types of networks is the subject of continuing development efforts; this invention teaches the results of one such effort.
Technologies from other environments are known which have been considered as useful in developing solutions to the problems hereinabove described. For example, there are modulation techniques previously considered for PCS radio systems, as in Ue et al., Symbol Rate and Modulation Level Controlled Adaptive Modulation/TDMA/TDD for Personal Communication Systems, IEEE VTE, July 1995, pp. 306-310 (0-7803-3742-X/95). Therein the concern was mainly to combat delay spread, which is the temporal distortion in the time of arrival of a particular bit or symbol of information. The function was to estimate the channel based upon conditions at the transmitter.
Seiichi Sampei, Norihiko Morinaga, and Yukiyoshi Kamio, Adaptive Modulation/TDMA with a BDDFE for 2 Mbp/s Multi-Media Wireless Communication Systems, IEEE VTC'95, July 1995, pg. 311-315. This reference describes a technique whereby a modulation scheme is chosen based upon estimates by or at the transmitter which then “sends” the link to a channel preselected to support that modulation scheme.
Patents uncovered during the course of research include the following.
U.S. Pat. No. 5,048,054 to Eyuboglu, et. al. issued Sep. 10, 1991 entitled Line Probing Modem and assigned to Codex Corporation describes an adaptive modem which probes both ends of a link.
U.S. Pat. No. 5,557,644 to Kuwabara issued Sep. 17, 1996 entitled Signal Demodulating and Decoding Apparatus and Signal Demodulating and Decoding Method and assigned to Hitachi, Ltd. describes parallel demodulators.
U.S. Pat. No. 5,490,168 to Phillips, et. al. issued Feb. 6, 1996 entitled Method and System for Automatic Optimization of Data Throughput Using Variable Packet Length and Code parameters and assigned to Motorola, Inc. describes modification of the packet length with changing channel characteristics, with the two “predetermined” coding rates, using varying packet length, as well as a method for transitioning the receiving and transmitting ends of the link from the “efficient” packet to the more “robust” (i.e., shorter) packet, and changing between the predetermined coding rates and packet lengths. An alternative includes transitioning from the shorter packets to the longer packets, using counts of the channel errors to change the length of the packets and their related coding rates.
U.S. Pat. No. 5,150,368 to Autruong, et. al. issued Sep. 22, 1992 entitled Minimization of Modem Retransmissions originally assigned to Rolm Systems (now part of Siemens) describes selective retransmission (BEC) with bitwise voting to reach a valid checksum.
U.S. Pat. No. 5,425,051 to Mahany issued Jun. 13, 1995 entitled Radio Frequency Communication Network Having Adaptive Parameters and assigned to Norand Corporation (Cedar Rapids, Iowa) describes an adaptive RF network. U.S. Pat. No. 5,548,821 to Coveley issued Aug. 20, 1996 entitled Adaptive System for Self-Tuning and Selecting a Carrier Frequency in a Radio Frequency Communication System describes an automatic frequency control technique.
Patents uncovered in a survey of keywords include: U.S. Pat. No. 5,432,818 issued Jul. 11, 1995 to Yuang Lou entitled Method and Apparatus of Joint Adaptive Channel Encoding, Adaptive System Filtering, and Maximum Likelihood Sequence Estimation Process by Means of an Unknown Data Training; and U.S. Pat. No. 5,448,593 issued Sep. 5, 1995 to Lawrence Hill, assigned to Cyplex Corporation, entitled Frequency Hopping Time-diversity Communications Systems and Transceivers for Local Area Networks. This patent describes power line carrier communication which uses modulation of frequency pairs selected from sets of pairs. Both ends communicate using the same modulation scheme.
Reference is also made to the prior work of the current inventors, such as Method and System for Routing Packets in a Packet Communication Network Using Locally Constructed Routing Tables, U.S. Pat. No. 5,488,608 issued Jan. 30, 1996; and Method for Routing Packets by Squelched Flooding, U.S. Pat. No. 5,007,052 issued Apr. 9, 1991.
SUMMARY OF THE INVENTION
According to the invention, net throughput is optimized on the link between the communicating nodes by dynamically modifying signal characteristics of the signals transmitted between nodes in response to performance metrics which have been determined from analysis at the receivers for the corresponding links. The signal characteristics can be the data rate, modulation type, on-air bandwidth, etc. The performance metrics are calculated based on data-link on-air characteristics of received signals.
In one embodiment, the performance metrics are based upon the historical information about the link that are available at the affected nodes. Each node in the radio network continually collects information regarding measurable on-air characteristics (or specific parameters) while retaining information regarding categories of interference to received packets. The node collects and retains these data both on a per-link and per transmission (specific packets sent and received from a specific node) and a locality-specific basis.
The communication between two nodes has signal characteristics that affect the performance metrics. These signal characteristics include data rate, packet length, modulation type, forward error correction, backwards error correction, bit-wise interleaving, frequency channel selection, power level, block size and/or computational complexity. Probability information can be gathered as a performance metric, such as, a probability of successful transmission between the two nodes, a probability of a bit error in the communication upon receipt at a receiving node, a probability o
Bradford Curtis
Flammer, III George Henry
Duong Frank
Ricochet Networks, Inc.
Yao Kwang Bin
LandOfFree
Method and apparatus for maximizing data throughput in a... 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 apparatus for maximizing data throughput in a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for maximizing data throughput in a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2960532