Telecommunications – Radiotelephone system – Zoned or cellular telephone system
Reexamination Certificate
1999-04-20
2001-02-27
Bost, Dwayne D. (Department: 2744)
Telecommunications
Radiotelephone system
Zoned or cellular telephone system
C455S428000
Reexamination Certificate
active
06195553
ABSTRACT:
FIELD OF THE INVENTION
The invention claimed herein relates to the area of communications networks. More particularly, this invention relates to chains of ground stations and satellite constellations, (hereinafter referred to simply as “chains”), as well as other configurations of communications resources, such as systems involving aircraft and fixed and mobile surface units, and the problem of evaluating available links and identifying the optimal path between a starting point and the desired end point in the communications system when the availability of the links is in a constant state of change.
BACKGROUND OF THE INVENTION
In modern satellite communications networks, often consisting of dozens of satellites and numerous surface facilities, the process of determining which links to use in communicating between one point in the network and another can be extremely complex, time-consuming and error prone. In addition to such considerations as minimizing distance or the number of links, other factors such as location and conditions that may impact the quality of a given link can make one link more or less costly than another. Given such factors, determining the optimal combination of links to use in a specific situation can require hours of complex calculations with a significant possibility of error.
What is “optimal” will depend upon priorities and factors important to a given user or situation, but includes such criteria as minimizing the number of separate links or avoiding links that are undesirable due to distance, location (e.g. outside certain latitudes), interference factors, loading, limited availability, lack of reliability and other negative characteristics.
A satellite communications system that utilizes satellites in geosynchronous orbit is generally a static system, since the spacecraft do not change position appreciably relative to relay stations on the ground beneath them. Geosynchronous satellites, however, operate in very high altitudes on the order of 22,000 statue miles. The propagation delays inherent in conveying signals over a nearly 50,000 mile round-trip are not acceptable for many communication environments. Low Earth orbit systems are seen to be essentially static where one satellite merely hands off a communication to another satellite which moves into its place, covering the same cells on the Earth's surface as its predecessor-in-orbit.
A path between any two arbitrary nodes in the network is a sequence of nodes from the originating (source) node to the terminating (destination) node. In order to select a “best” path, some figure of merit for any candidate path is derived. The figure of merit consists of the additive “costs” of each of the links between nodes derived from the connectivity matrix. The link costs may include the additive “costs” associated with the nodes. Thus the cost of a path is just the sum of the link costs between adjacent nodes in the path sequence.
Regardless of the algorithm used to transform the network nodal connectivity to the “shortest path” between two nodes, (e.g., Floyd's Algorithm or Dijkstra's Algorithm, both provided in
Introduction to Algorithms
by Thomas Cormen, Charles Leiserson and Ronald Rivest, © 1990, chapter 25 for Dijkstra's Algorithm and chapter 26 for Floyd's Algorithm, therein referred to as the Floyd-Warshall Algorithm, which is the alternative nomenclature for Floyd's Algorithm), the cost of such a path is obtainable by taking the sum of the link costs, perhaps including some additive nodal cost, either by using Floyd's Algorithm or Dijkstra's Algorithm to make the required determination. As long as there is a single link cost factor used to determine the cost for the logical or physical links between two nodes, the approach to determining the shortest path value is straightforward.
The situation is not as clear cut when there are two or more independent cost factors used to determine an aggregate cost for a path to be used in evaluating the best or shortest path. It will be understood that when multiple costs are considered for evaluating a best or shortest path, the various cost considerations lead to different “shortest path” conclusions. For example, if hop count, i.e., the number of nodes traversed by a packet from source to destination node, is an overwhelming concern, one path within a network may be the shortest path. Alternatively, if delay is the major factor, i.e., the time it takes for a packet to travel from the source to the destination node, then another path within the network may be the best path. Still different conclusions may be reached if other factors, such as monetary cost, are taken into consideration.
When single cost functions are used as a means of obtaining figures of merit for various paths within the network, the concept of adding the costs of each link in the path, as discussed above, is the natural way to obtain the result. Known routing algorithms assume that costs add as the path is traversed. Common cost functions, used in path selection (e.g., “delay”, “cost of transmission line facility”, “hop count”), are additive. Individually, they are immediately adaptable to standard path-cost-determination algorithms. However, there are other cost-factors, (e.g., “percent available bandwidth”, “ability to handle a specific protocol”, “ability to handle a certain packet type”) which are major determiners of path selection, but which are not additive. These types of cost factors cannot be treated by usual connectivity matrix based methods. The reason is that arithmetic addition is too limiting to describe the actions of many cost factors.
Therefore, a method for handling multi-cost factors in determining the relative costs of paths within a network is needed. Additionally, this method for handling multi-cost factors should also be capable of considering non-additive cost factors in the relative costs of paths determination.
The methods and apparatus disclosed in U.S. Pat. No. 5,740,164 to Liron, comprises software and hardware which manage satellite communication links between the origin and destination of telephone calls which convey voice, data, or video information. The methods of this invention select the best series of connections from a terrestrial gateway or terminal up through a satellite constellation and back down to Earth. The constellation operates in low Earth orbit, and provides continuous worldwide service. The pathway that is selected for a particular call is adaptive and able to change rapidly in response to the constantly changing geometry of the low Earth orbit constellation. Based upon inputs from the position determination algorithms that define the length of each link in the system, algorithms are provided to determine the optimal route for each transmission from each satellite and also establish the most efficient distribution pattern of traffic throughout the system.
In U.S. Pat. No. 4,905,233, issued Feb. 27, 1990, Cain et al. disclose a mechanism for establishing at least one transmission route between a source node and a destination node in a communications network. Transmission characteristics of each of the transmission paths among the nodes of the network are monitored so as to derive a plurality of path metrics representative of the ability of the network to transmit communication signals. Feasible transmission routes from source node to destination node are selected where the sum of path metrics from neighboring nodes to the destination node is less than the path metric of a transmission path, the end nodes of which correspond to the source and destination nodes. Communication signals are then transmitted from the source node to the destination node over the selected feasible transmission routes. Typical link metrics are presented, which include as terms normalized propagation plus processing delay, and expected transmission delay including queuing delay. Cain et al. do not describe a specific method of packet switching and routing in a low Earth orbit satellite communication system in which the metrics
Claffery Douglas J.
Holland David M.
Woodburn James W.
Analytical Graphics Inc.
Bost Dwayne D.
Roberts Abokhair & Mardula
Vuong Anochien B.
LandOfFree
Method and apparatus for determining optimal paths among... 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 determining optimal paths among..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for determining optimal paths among... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2611882