# US 11,451,475 B2 · Packet forwarding based on geometric location > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 11,451,475 B2 - Document ID: US11451475B2 - Status: Granted - Kind: B2 - Application number: 16/721,171 - Filed: 2019-12-19 - Published: 2021-06-24 - Granted: 2022-09-20 - Earliest claimed: 2019-12-19 - Assignees: Huawei Technologies Co., Ltd. - Applicants: William Carson McCormick; Peter Ashwood-Smith - Inventors: William Carson McCormick; Peter Ashwood-Smith - Web page: https://patentgrep.com/patent/US11451475B2 ## CPC - H04L 45/123: {Evaluation of link metrics (techniques for monitoring network metrics H04L43/08)} - H04L 45/122: by minimising distances, e.g. by selecting a route with minimum of number of hops - H04L 45/126: {minimising geographical or physical path length} - H04L 45/48: Routing tree calculation - H04L 47/10: Flow control; Congestion control - H04L 47/822: {Collecting or measuring resource availability data} - H04W 40/22: using selective relaying for reaching a BTS [Base Transceiver Station] or an access point - H04W 84/18: Self-organising networks, e.g. ad-hoc networks or sensor networks - H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M) - H04W: WIRELESS COMMUNICATION NETWORKS (broadcast communication H04H; communication systems using wireless links for non-selective communication, e.g. wireless extensions H04M1/72) ## Abstract The present invention is provides a method and apparatus for routing a data packet in a network. For each nearby device capable of routing the packet toward a further destination, an associated cost or utility is determined. The device with lowest cost or highest utility is selected and the packet is forwarded toward same. The selecting may use a comparator tree. The cost or utility may be associated with forwarding the data packet from the candidate device toward the further destination. The cost or utility may be based on a distance from candidate device to the further destination, and may be determined using a Haversine function or approximation thereof, or by computing an inner product of a first vector and a second vector originating at a center of Earth, the first vector directed toward the candidate device, the second vector directed toward the further destination. ## Claims ### Claim 1 A method for routing a data packet in a network, the method comprising: for each one of a plurality of destination devices capable of further handling of the data packet for routing toward a further destination, determining a respective cost or utility associated with forwarding the data packet to said one of the plurality of destination devices, wherein the cost or utility is determined by computing an inner product of a first vector and a second vector, the first vector originating at a first location and directed toward said one of the plurality of destination devices, the second vector originating at the first location and directed toward said further destination; selecting, using a comparator tree, one of the plurality of destination devices based at least in part on the determined costs or utilities; and forwarding the data packet to said selected one of the plurality of destination devices. ### Claim 2 (depends on 1) The method of claim 1, wherein said selecting one of the plurality of destination devices comprises selecting a particular one of the plurality of destination devices having a lowest cost or highest utility. ### Claim 3 (depends on 1) The method of claim 1, wherein the comparator tree includes multiple stages, each stage having one or more comparators configured to compare pairs of said costs or utilities and output an indication of a lower of compared costs or a higher of compared utilities. ### Claim 4 (depends on 1) The method of claim 1, wherein the inner product of the first vector and a second vector represents an orthodromic distance. ### Claim 5 (depends on 1) The method of claim 1, wherein at least one of the plurality of destination devices is a satellite-based network node, and the first location is a location at a center of the Earth. ### Claim 6 (depends on 1) The method of claim 1, wherein each one of the plurality of destination devices is a satellite-based network node, the further destination is a ground-based network node, and the first location is a location at a center of the Earth. ### Claim 7 An apparatus for routing a data packet in a network, the apparatus comprising: a cost determiner configured, for each one of a plurality of destination devices capable of further handling of the data packet for routing toward a further destination, to determine a respective cost or utility associated with forwarding the data packet to said one of the plurality of destination devices, wherein the cost or utility is determined by computing an inner product of a first vector and a second vector, the first vector originating at a first location and directed toward said one of the plurality of destination devices, the second vector originating at the first location and directed toward said further destination; a destination selector configured to receive the determined costs or utilities from the cost determiner and select one of the plurality of destination devices based at least in part on the determined costs or utilities, the destination selector comprising a comparator tree; and a packet forwarder configured to receive said selected one of the plurality of destination devices from said destination selector and forward the data packet to said selected one of the plurality of destination devices. ### Claim 8 (depends on 7) The apparatus of claim 7, wherein one or both of the cost determiner and the destination selector is implemented using a processor operatively coupled to memory, the memory storing program instructions that, when executed by the processor, cause the processor to implement said one or both of the cost determiner and the destination selector. ### Claim 9 (depends on 7) The apparatus of claim 7, wherein one or both of the cost determiner and the destination selector is implemented using dedicated data processing hardware. ### Claim 10 (depends on 7) The apparatus of claim 7, wherein said selecting one of the plurality of destination devices comprises selecting a particular one of the plurality of destination devices having a lowest cost or highest utility. ### Claim 11 (depends on 7) The apparatus of claim 7, wherein the comparator tree includes multiple stages, each stage having one or more comparators configured to compare pairs of said costs or utilities and output an indication of a lower of compared costs or a higher of compared utilities. ### Claim 12 (depends on 7) The apparatus of claim 7, wherein the inner product of the first vector and the second vector represents an orthodromic distance. ### Claim 13 (depends on 7) The apparatus of claim 7, wherein at least one of the plurality of destination devices is a satellite-based network node, and the first location is a location at a center of the Earth. ### Claim 14 (depends on 7) The apparatus of claim 7, wherein each one of the plurality of destination devices is a satellite-based network node and the further destination is a ground-based network node, and the first location is a location at a center of the Earth. ### Claim 15 A method for selecting a routable target in a packet data network, the method comprising: determining, in accordance with a geographic location of the routable target, a distance metric for each of a plurality of network nodes, each distance metric representative of the distance between the respective network node and the geographic location of the routable target, the distance metric being computed as an inner product of location information associated with the nodes and the routable target; providing each of the determined distance metrics to inputs of a comparator tree, wherein the comparator tree comprises a plurality of levels, each level prior to a last level performing a corresponding plurality of pairwise comparisons in parallel and forwarding results of said pairwise comparisons to a subsequent level, the pairwise comparisons being between pairs of the determined distance metrics; and receiving from an output of the comparator tree an indicator associated with a network node form the plurality of network nodes associated with the smallest distance metric. ### Claim 16 A target selection engine for selecting a node from a plurality of node, the selection engine comprising: an input for receiving a geographic location identifier associated with a destination node; a distance metric computation engine for computing a plurality of distance metrics, each of the distance metrics associated with a node from the plurality of nodes indicative of a distance from the associated node to the received geographic indicator, each distance metric representative of the distance between the respective network node and the geographic location of the routable target, the distance metric being computed as an inner product of location information associated with the nodes and the routable target; a comparator tree for receiving the plurality of distance metrics and for selecting the smallest distance metric, wherein the comparator tree comprises a plurality of levels, each level prior to a last level performing a corresponding plurality of pairwise comparisons in parallel and forwarding results of said pairwise comparisons to a subsequent level, the pairwise comparisons being between pairs of the plurality of distance metrics. ### Claim 17 (depends on 16) The target selection engine of claim 16, wherein the inner product represents an orthodromic distance.