Method of loose source routing over disparate network types in a packet communication network

• US 5,570,084 A
• Filed: 06/28/1994
• Issued: 10/29/1996
• Est. Priority Date: 06/28/1994
• Status: Expired due to Term

• Current Assignee: Google Inc. (Alphabet Inc.)
• Original Assignee: Metricom, Inc.
• Inventors: Ritter, Michael W., Bettendorff, John, Flammer, III, George H., Galloway, Brett D.
• Primary Examiner(s): Horabik, Michael
• Assistant Examiner(s): MERZ, EDWARD W
• Application Number:
  US08/268,765
• Time in Patent Office: 854 Days
• Field of Search: 340/827, 340/825.05, 340/825.04, 370/85.13, 370/94.1, 370/94.3, 395/325
• US Class Current: 370/338
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing
• CPC Class Codes: H04L 45/34 Source routing
• CPC Class Codes: H04W 40/02 Communication route or path selection, e.g. power-based or shortest path routing

Abstract

In a packet communication system, loose source routing is employed to permit communication over networks of disparate types, including geographic and path-unaware types. No information resides on a wired access point (WAP). All of the intelligence of the system resides in Name Servers, which provide opaque addresses that end nodes (radios) in a wireless cloud can use to send packets to other end nodes (radios) in other wireless clouds. (A cloud is the set of radios serviced by a particular WAP.) According to the invention, the method employs an ordered list called a path and the network address of a packet consists of such an ordered list of addresses with a "marker" that flags the current destination of the packet and a "direction bit" that tells which direction on the list the next destination is. Each address in the path is type-length-value (TLV) encoded. The address has preferably a 4 bit "type" field, followed by a 4 bit "length" field (indicating length in words) of the value, and then the actual "value" of the address. Each address describes a "place" that the packet must "visit." These "places" may be areas which a packet must traverse, and not necessarily actual node addresses.

Claims

1. A method for digital packet communication between nodes in disparate networks including path unaware network layer types and path aware network layer types, said method comprising:

a) receiving a typed encapsulating packet which encapsulates a path-addressed packet at a first network layer, said first network layer being path aware;

b) directing the encapsulating packet to a path router;

c) determining by testing for type at said path router whether said typed encapsulating packet should be passed to a second network layer or to an application and whether said second network layer is path aware or path unaware; and

d) passing said encapsulating packet to the application if said encapsulating packet is addressed to said application, or passing said encapsulating packet to said second network layer if not so addressed by routing said encapsulating packet according to a path unaware protocol if said second network layer is path unaware;

otherwise routing said encapsulating packet according to a path aware protocol if said second network layer is path aware.

2. A method for digital packet communication between nodes in disparate networks including path unaware network layer types and path aware network layer types, said method comprising:

a) receiving an encapsulating packet which encapsulates a path-addressed packet at a first network layer of a first type;

b) if said first type is path unaware, checking whether said encapsulating packet is intended for the current destination and if not, routing said encapsulating packet according to said path unaware protocol;

otherwise

c) extracting said path-addressed packet from said encapsulating packet;

thereafter

d) finding a marker element in a path address sequence in the path-addressed packet and determining whether destination indicated by the marker is out of range for the current node, and if not in range, aborting processing;

else if in range

e) testing to determine whether the current destination indicated by the marker matches the current node, and

f) if no match, passing on the path-addressed packet to another network router;

else, if the current destination indicated by the marker matches the current node, passing on the path-addressed packet to a network router for distribution to another network layer and to applications; and

if said network layer is path aware, performing steps e) through f).

3. the method according to claim 2 further including the step of;

routing the path-addressed packet received at the path router and not destined for an application to a next appropriate network router.

4. The method according to claim 2 further including the step of determining whether the current station understands the network type of the received packet and if so passing the packet to the next appropriate network router.

5. The method according to claim 2 further including the steps of:

determining whether the current station understands the network type of the received packet and if not, processing the packet according to the understanding of the current station, else

determining whether a next destination network type is of the same type as the network type from which the packet was received, and if so, processing the packet according to the network type, else

substituting a type-length-value element in the packet which is recognizable by the next destination network type.

6. The method according to claim 2 further including the steps of:

determining whether the current station understands the network type of the received packet and if so, processing the packet according to the understanding of the current station, else

attempting to locate other network routers which do understand the network type of the received packet; and

relaying the received packet to an appropriate network router.

7. A method for digital packet communication between nodes in various networks including path aware network layer types, said method comprising:

a) designating a destination path element for a packet by means of a type-length-value element specific only to one station of a group of destinations, where said one station of said group is not necessarily a target destination;

b) selecting a route for said packet to a station within said group;

thereafter

c) transmitting said packet to said station within said group;

d) receiving said packet at said station at a first network layer, said packet being a path-addressed packet;

e) directing said path-addressed packet to a path router;

f) determining at said path router whether said path-addressed packet should be passed to a second network layer or to an application; and

g) passing said path-addressed packet to the application if so addressed and to a second network layer if not so addressed.

8. The method according to claim 7 wherein said networks include a geographically-addressed network.

9. The method according to claim 8 wherein said specifying step includes specifying a set of stations by means of a single geographic address and a radial distance from said geographic address for directing said packet to any station within a radius of said geographic address.

10. The method according to claim 7 wherein said networks include a non-geographically-addressed network.