US5488608A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and system for routing packets in a packet communication network using locally constructed routing tables
Assignee: Google LLC
•
Filing: 1994-04-14
•
Granted: 1996-01-30
•
Expires: 2014-04-14
Abstract
Abstract In a packet communication system, wherein nodes are assigned an absolute coordinate-based address and routing decisions are made at each node without the use of directory-based routing, routing decisions made for a particular packet with an ultimate destination are stored at each node so that the next packet sent by that node to that same ultimate destination can be forwarded in accordance with the previous routing decision made for that destination. Routing decisions are stored locally at each node in a routing table. In one embodiment, nodes also store routing information about the source node for a packet so that when a return packet is received for the original source, the relay node will not have to make a routing decision.
Inventors
- 👤 George H. Flammer, III
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-30 11:40
CPC Classifications
H; H04; H04L; H04L45/00; H04L49/00; H04L49/30; H04L49/3081; H04Q; H04Q11/00; H04Q11/04; H04Q11/0428; H04Q11/0478; H04L12/00; H04L12/54; H04L12/56; H04L12/5601; H04L2012/5619
Claims Analysis
Total Claims: 15
Claim 1
Independent Claim
221 words
A method for routing packets of dam without a network directory comprising the steps of: assigning to each node in a network an identifier indicative of coordinate location, said identifier including an absolute coordinate value; addressing a packet to an ultimate destination node by designating in a packet header said ultimate destination node only by said coordinate value of said ultimate destination node and without designating a complete intermediate path to said ultimate destination node such that the network is free to route the packet via any intermediate path to said ultimate destination node; at a relay local node, selecting upon first receipt of a packet for a destination node one neighboring node by using said absolute coordinate value of said destination node and other information specific to said relay local node according to preselected criteria; storing at said relay local node an identifier of said selected neighboring node along with a label for said ultimate destination node in a routing table; forwarding said packet to said selected neighboring node for eventual delivery to said ultimate destination node; and retrieving said identifier of said selected neighboring node from said routing table when a subsequent packet for said ultimate destination node is received at said relay local node and forwarding said subsequent packet to said selected neighboring node indicated by said identifier.
Claim 2
Independent Claim
221 words
A method for routing packets of dam without a network directory comprising the steps of: assigning to each node in a network an identifier indicative of coordinate location, said identifier including an absolute coordinate value; addressing a packet to an ultimate destination node by designating in a packet header said ultimate destination node only by said coordinate value of said ultimate destination node and without designating a complete intermediate path to said ultimate destination node such that the network is free to route the packet via any intermediate path to said ultimate destination node; at a relay local node, selecting upon first receipt of a packet for a destination node one neighboring node by using said absolute coordinate value of said destination node and other information specific to said relay local node according to preselected criteria; storing at said relay local node an identifier of said selected neighboring node along with a label for said ultimate destination node in a routing table; forwarding said packet to said selected neighboring node for eventual delivery to said ultimate destination node; and retrieving said identifier of said selected neighboring node from said routing table when a subsequent packet for said ultimate destination node is received at said relay local node and forwarding said subsequent packet to said selected neighboring node indicated by said identifier.
Claim 3
Dependent Claim
28 words
The method according to claim 1 wherein said selecting step includes using said packet header to determine distance of said neighboring nodes relative to said ultimate destination node.
Claim 4
Dependent Claim
27 words
The method according to claim 1 wherein said selecting step includes developing a local table for maintaining communication history between said local nodes and said neighboring nodes.
Claim 5
Independent Claim
99 words
The method according to claims 1, 2, or 3 further comprising the step of: storing at said relay local node an identifier for a neighboring node from which the packet was received along with a label for a source node of said packet in a routing table; and retrieving said identifier for said neighboring node from which the packet was received from said routing table when a return packet directed to said source node is received at said relay local node; and forwarding said return packet to said transmitted from neighboring node for eventual delivery to said source node.
Claim 6
Dependent Claim
18 words
The method according to claim 3 wherein a link quality factor is employed to define preferred communication paths.
Claim 7
Independent Claim
191 words
A system for routing packets of data in a packet data communication network without a network directory comprising: a plurality of nodes in a network, each node including an identifier indicative of coordinate location, said identifier including a coordinate value referenced to a terrestrial grid; means for addressing a packet to an ultimate destination node by designating in a packet header said ultimate destination node only by said coordinate value of said ultimate destination node and without designating a complete intermediate path to said ultimate destination node such that the network is free to route the packet via any intermediate path to said ultimate destination node; means at each of said plurality of nodes for selecting upon first receipt of a packet for a destination node a neighboring node by using said identifier indicative of coordinate location of said destination node; and means at each of said plurality of nodes for storing a routing table entry for an ultimate destination of a packet, said routing table entry selected by an identifier for said ultimate destination node and including information identifying a neighboring node as a forwarding node for said ultimate destination.
Claim 8
Independent Claim
191 words
A system for routing packets of data in a packet data communication network without a network directory comprising: a plurality of nodes in a network, each node including an identifier indicative of coordinate location, said identifier including a coordinate value referenced to a terrestrial grid; means for addressing a packet to an ultimate destination node by designating in a packet header said ultimate destination node only by said coordinate value of said ultimate destination node and without designating a complete intermediate path to said ultimate destination node such that the network is free to route the packet via any intermediate path to said ultimate destination node; means at each of said plurality of nodes for selecting upon first receipt of a packet for a destination node a neighboring node by using said identifier indicative of coordinate location of said destination node; and means at each of said plurality of nodes for storing a routing table entry for an ultimate destination of a packet, said routing table entry selected by an identifier for said ultimate destination node and including information identifying a neighboring node as a forwarding node for said ultimate destination.
Claim 9
Independent Claim
210 words
A system for routing packets of data without a network directory comprising: a plurality of nodes in a network, each node including an identifier indicative of geographic location, said identifier including a coordinate value referenced to a terrestrial grid; means for addressing a packet to an ultimate destination node by designating in a packet header said ultimate destination node only by said coordinate value of said ultimate destination node and without designating a complete intermediate path to said ultimate destination node such that the network is free to route the packet via any intermediate path to said ultimate destination node; and at a local node, means for selecting at least one of said neighboring nodes upon first receipt of a packet for said destination node by using said packet header and other information specific to said local node according to preselected criteria; means for forwarding said packet to said selected neighboring nodes for eventual delivery to said ultimate destination node; and means at each of said plurality of nodes for storing a routing table entry for an ultimate destination of a packet, said routing table entry selected by an identifier for said ultimate destination node and including information identifying a neighboring node as a forwarding node for said ultimate destination.
Claim 10
Independent Claim
210 words
A system for routing packets of data without a network directory comprising: a plurality of nodes in a network, each node including an identifier indicative of geographic location, said identifier including a coordinate value referenced to a terrestrial grid; means for addressing a packet to an ultimate destination node by designating in a packet header said ultimate destination node only by said coordinate value of said ultimate destination node and without designating a complete intermediate path to said ultimate destination node such that the network is free to route the packet via any intermediate path to said ultimate destination node; and at a local node, means for selecting at least one of said neighboring nodes upon first receipt of a packet for said destination node by using said packet header and other information specific to said local node according to preselected criteria; means for forwarding said packet to said selected neighboring nodes for eventual delivery to said ultimate destination node; and means at each of said plurality of nodes for storing a routing table entry for an ultimate destination of a packet, said routing table entry selected by an identifier for said ultimate destination node and including information identifying a neighboring node as a forwarding node for said ultimate destination.
Claim 11
Dependent Claim
27 words
The system according to claim 7 wherein said selecting means comprises means for selecting one neighboring node requiring the least amount of power for forwarding said packet.
Claim 12
Dependent Claim
29 words
The system according to claim 7 wherein said selecting means includes means for using said packet header to determine distance of neighboring nodes relative to said ultimate destination node.
Claim 13
Dependent Claim
29 words
The system according to claim 7 wherein said selecting means includes means for developing a link list for maintaining communication history between said local nodes and said neighboring nodes.
Claim 14
Dependent Claim
63 words
The system according to claim 10 wherein said link list maintains information about said neighboring nodes on at least one of the following criteria: distance, output power required to establish communication, retry history (reliability), throughput history, speed of transfer (net data rate), network delay, data priority, link utilization percentage, closeness to desired destination, closeness to desired bearing, randomness, and closeness to local bearing.
Claim 15
Dependent Claim
18 words
The system according to claim 10 wherein a link quality factor is employed to define preferred communication paths.
References Cited (Backward Citations)
US5031093A
Cited
US4905233A
Cited
US5088032A
Cited
US5007052A
Cited
US5142531A
Cited
US5115433A
Cited
US4974224A
Cited
US5253161A
Cited
US5079768A
Cited
US5253248A
Cited
US5265092A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1999-01-29 | 1999-07-31 | 2000-01-30 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2003-01-29 | 2003-07-31 | 2004-01-30 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2007-01-29 | 2007-07-31 | 2008-01-30 | $7700.00 | Window Closed / Lapsed |