Multiplex communications – Diagnostic testing – Determination of communication parameters
Reexamination Certificate
1999-10-28
2004-01-13
Pham, Chi (Department: 2661)
Multiplex communications
Diagnostic testing
Determination of communication parameters
C370S351000, C370S400000, C370S431000, C370S468000
Reexamination Certificate
active
06678252
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to a data protocol in a computer network, and in particular to a Quality of Service (QoS) metric for a data protocol for transmitting Internet Protocol (IP) data subject to QoS constraints in a wireless mobile ad-hoc network.
2. Description of the Related Art
A collection of wireless mobile “nodes” that form the network without any fixed infrastructure or centralized administration is typically referred to as a wireless mobile “ad hoc” network (MANET). Such networks are useful for when it is economically or physically impractical to provide a fixed infrastructure, or when urgency does not allow installation of a fixed infrastructure. For example, a class of students may need to interact with their computers during a lecture; business associates may wish to share files impromptu at an airport terminal; rescue workers may need emergency communications after an earthquake; or, soldiers may need mobile communications on a battle field. In these situations, the computer communications network cannot be “terrestrial,” i.e., it cannot have a fixed infrastructure or centralized administration; it must be a MANET.
Due to the limited range of the wireless transmission of each node in a MANET, a source node may need to enlist the aid of other intermediary transit nodes to forward data, usually grouped in “packets,” to a destination node. A routing protocol finds a “path,” “route,” or “channel” for the data packets to travel from the source node to the destination node.
FIG. 1
is a diagram of a conventional MANET. For example, a node C is not within a wireless transmission range
102
of a node A, and node A is not within a wireless transmission range
104
of node C. If node A and C want to exchange data packets, they may use node B as a transit node to forward data packets from node A to node C, and vice versa. It is practical to use transit node B because it is within both the wireless transmission ranges
102
,
104
of node A and node C. Of course, the routing problem in a MANET may be more complicated than that in
FIG. 1
, due to mobile nodes and nonuniform propagation characteristics of wireless transmission.
Recently, MANETs have been supporting real-time Internet Protocol (IP) applications, such as telephony, and video streaming. Real-time IP applications (and any application that requires the transmission of time-sensitive data) need predictable network resources, to support predictable Quality of Service (QoS). QoS support entails providing an application with enough network resources so that it can function within acceptable performance limits. This support includes providing a minimum guaranteed bandwidth or special processing some packets. In IP telephony, for instance, the network must provide two “flows” of data—one flow in both directions between telephone users. The two flows must have a large enough bandwidth to carry digitized voice without introducing an annoying delay.
In both MANETs and terrestrial networks, however, data traffic congestion often frustrates providing sufficient network resources for QoS support for real-time applications. In a MANET, for instance, “physical layer” impairments that are caused by noisy, poor-quality radio channels result in insufficient network resources. In addition to the Gaussian background noise of terrestrial networks, MANETs also have impulsive noise, multipathing, signal fading, unintentional interference from other users of the channel, and intentional enemy jamming. These all increase noise and reduce the quality of radio channels in MANETs.
Solutions to physical layer impairments include providing stronger data coding, finding an alternate route, or increasing the transmission power level. These solutions, however, usually increase congestion in the network. For example, stronger codes add resiliency to a channel, but effectively reduce available bandwidth. Further, when the bit error rate caused by channel impairments reaches a certain threshold, coding methods alone are insufficient to overcome the impairment and an alternate path is needed. For example, such a threshold may be a bit error rate (BER) of 10
−2
errors per second. Of course, finding an alternate route increases data congestion at other parts of the MANET. Lastly, increasing transmission power increases collisions and interference between nodes, which may reduce available bandwidth.
Another solution to the congestion problem is to over-engineer the network to provide more bandwidth. In a terrestrial network, over-engineering may include laying more coaxial or fiber optic cables. In a MANET, over-engineering may include increasing the frequency bands allocated to the MANET. It is expensive and inefficient to over-engineer a network, however, and this approach is not easily applied in MANETs.
Yet another solution to the congestion problem is to identify packets carrying real-time applications and provide them with special “priority” treatment. A widely known priority treatment is Differentiated Services (DS). Roughly speaking, DS marks special packets of data in a DS field in the packet. Nodes treat the specially marked packets according to an appropriate priority. DS does not identify individual flows, but provides a special treatment to an aggregate “class” of flows, as specified in the Per Hop Behavior (PHB) that corresponds to a particular value in the DS field.
PHBs use well-known packet scheduling algorithms such as weighted fair queuing, or start time queuing. These algorithms ensure that a minimum bandwidth is allocated to a certain class of traffic. Because DS does not differentiate between individual flows, the guaranteed bandwidth is allocated to an aggregate of flows, differentiated from other aggregated flows by a different DS field value. In the DS approach, a class of traffic obtains a given portion of the network resources. In one extreme case, however, the portion allocated to a specific class is 100%, and effectively nothing is gained from the DS approach. Further, there may be too many data packets for the allocated bandwidth in a given class. In this case, packets from the class would be subject to congestion within its allocated resources, similar to a single class best-effort system.
Many other solutions to solve the congestion problem assume that a particular node in the MANET is likely to serve as a transit node to a very large number of flows, similar to a “backbone” node in a high-speed terrestrial network. This assumption, however, is flawed because there usually is no identifiable backbone node in a MANET. MANET nodes, unlike terrestrial nodes, randomly assume transit responsibilities so that no one node is significantly more likely than another to serve as a transit node. Second, MANET nodes generally have a relatively low channel bit-rate that may saturate if acting as a backbone. Hence, no node in a MANET is likely to be a backbone node.
Most solutions to the congestion problem may also use “metrics” to measure conditions of the network in order to manage congestion. There are several known QoS metrics that relate to the performance requirements of real-time applications, including delay, jitter, and throughput. Routing algorithms use QoS metrics to find a path that satisfies the QoS requirements. Calculating a metric to find a route that satisfies multiple constraints, however, is a computationally difficult problem.
Thus, there is a need to overcome congestion within a class, provide QoS service, allocate network resources for identified flows, without generating significant overhead data. More specifically, there is a need for improved routing of IP packets with QoS constraints over MANETs with an improved QoS metric.
SUMMARY OF THE INVENTION
This summary and the following detailed description should not restrict the scope of the claimed invention. Both provide examples and explanations to enable others to practice the invention. The accompanying drawings, which form part of the detailed description, show several embodiments of the invention
Emdadi Kamran
Suchyta Leonard Charles
Verizon Laboratories Inc.
Weixel James K.
LandOfFree
Method and apparatus for dynamic source routing in ad hoc... 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 dynamic source routing in ad hoc..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for dynamic source routing in ad hoc... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3235958