Highly dynamic destination-sequenced destination vector routing for mobile computers

• US 5,412,654 A
• Filed: 01/10/1994
• Issued: 05/02/1995
• Est. Priority Date: 01/10/1994
• Status: Expired due to Term

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Perkins, Charles E.
• Primary Examiner(s): Olms, Douglas W.
• Assistant Examiner(s): VU, HUY DUY
• Application Number:
  US08/179,397
• Time in Patent Office: 477 Days
• Field of Search: 370/94.1, 370/60, 370/60.1, 370/61, 370/92, 455/33.1, 455/56.1, 455/54.1, 455/11.1, 455/13.1, 455/13.2, 455/7
• US Class Current: 370/312
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/20 Hop count for routing purposes, e.g. TTL
• CPC Class Codes: H04W 40/248 Connectivity information update
• CPC Class Codes: H04W 40/34 Modification of an existing route
• CPC Class Codes: H04W 48/08 Access restriction or access information delivery, e.g. discovery data delivery signalling during connection H04W76/00
• CPC Class Codes: H04W 8/26 Network addressing or numbering for mobility support
• CPC Class Codes: H04W 84/18 Self-organising networks, e.g. ad-hoc networks or sensor networks
• CPC Class Codes: H04W 88/04 adapted for relaying to or from another terminal or user
• CPC Class Codes: H04W 92/18 between terminal devices

Abstract

Packets are transmitted between stations of an ad-hoc network of mobile stations by using routing tables which are stored at each station of the network. Routing information is broadcast or multicast according to three schedules; upon demand to show new routes, periodically to show recently changed routes, and less often to provide a complete dump of all known routes. A new route will trigger immediate re-broadcast so that this information is quickly disseminated. A new route is defined to be one with a better metric or a metric of infinity. A metric of infinity indicates a broken link; i.e., a particular destination is no longer reachable and thus all other destinations depending upon the newly unreachable destination are themselves unreachable. Periodically, routes are advertised. This advertisement serves primarily in most cases to notify all neighbors that everything they have stored is still correct regarding the broadcasting Mobile Host. On rarer occasions when the routing topology changes, the demand nature of the incremental update displaces the periodic transmission until an update interval transpires. In order to damp out oscillations, data is kept about how often the routes change. Based on this data, a decision may be made to delay advertising routes which are about to change soon, thus damping oscillations of the route tables.

Claims

1. A method for routing a packet of information between two mobile hosts that are coupled to an ad-hoc network comprised of a plurality of mobile hosts, each of the mobile hosts having a unique network address but not having a fixed location, said ad-hoc network conforming to a network standard including a network-layer and a link-layer, said method comprising the steps of:

storing routing tables at each mobile host, said routing tables including a "metric" defined as a number of hops from a source mobile host to a destination mobile host;

advertising routes by periodically broadcasting by each mobile host the routing table stored by the mobile host;

originating a time stamp by a destination mobile host;

tagging each route table entry with a time stamp originated by the destination mobile host;

updating, for each destination mobile host, mobile host stored routing tables based on received broadcasts from other mobile hosts;

retransmitting by each mobile host new routing information received from a neighboring mobile host; and

routing a packet of information by choosing a route from updated routing tables for transmitting a packet of information from a source mobile host as a route having a best "metric" for a desired destination mobile host, said best "metric" being a minimum number of hops that a packet must jump before reaching its destination, the routing being performed at the link-layer of the ad-hoc network.

2. The method of routing recited in claim 1 wherein a new route is defined to be one with a better metric, a better metric being a fewer number of hops a packet must jump before reaching its destination, or a metric of infinity, a metric of infinity indicating a broken link meaning that a particular destination is no longer reachable and thus all other destinations depending upon the newly unreachable destination are themselves unreachable, said step of retransmitting new routing information received from a neighboring mobile host being performed immediately upon reception of new routing information by a mobile host.

7. The method of routing recited in claim 1 further comprising the step of tracking network layer protocol availability data on a per destination basis.

3. A method for routing a packet of information between two mobile hosts that are coupled to an ad-hoc network comprised of a plurality of mobile hosts, each of the mobile hosts having a unique network address but not having a fixed location, said method comprising the steps of:

storing routing tables at each mobile host, said routing tables including a "metric" defined as a number of hops from a source mobile host to a destination mobile host;

storing routes in said routing tables;

advertising routes by periodically broadcasting by each mobile host the routing table stored by the mobile host;

originating a time stamp by a destination mobile host;

tagging each route table entry with a time stamp originated by the destination mobile host;

updating, for each destination mobile host, mobile host stored routing tables based on received broadcasts from other mobile hosts;

keeping data about how often routes, stored in said routing tables, change;

measuring stabilities of routes by determining average settling times of the routes stored in said routing tables;

storing determined average settling times of routes in a settling time table;

accessing the settling time table prior to the step of advertising and delaying the advertising of the routes which may change soon to damp oscillations of information in said route tables;

retransmitting by each mobile host new routing information received from a neighboring mobile host; and

choosing a route from Updated routing tables for transmitting a packet of information from a source mobile host as a route having a best "metric" for a desired destination mobile host, said best "metric" being a minimum number of hops that a packet must jump before reaching its destination.

4. The method of routing recited in claim 3 further comprising the step of weighting the determined average settling times of routes by counting a most recent measurement of the settling time of a particular route with a higher weighting factor than less recent measurements.

5. A method for routing a packet of information between two mobile hosts that are Coupled to an ad-hoc network comprised of a plurality of mobile hosts, each of the mobile hosts having a unique network address but not having a fixed location, wherein the ad-hoc network conforms to a network standard including a network-layer and a link-layer, said method comprising the steps of:

storing routing tables at each mobile host, said routing tables including a "metric" defined as a number of hops from a source mobile host to a destination mobile host;

storing routing information in said routing tables based on network-layer addresses of the mobile hosts;

advertising routes by periodically broadcasting by each mobile host the routing table stored by the mobile host;

originating a time stamp by a destination mobile host;

tagging each route table entry with a time stamp originated by the destination mobile host;

updating, for each destination mobile host, mobile host stored routing tables based on received broadcasts from other mobile hosts;

keeping data about how often routes, stored in said routing tables, change;

measuring stabilities of routes by determining average settling times of the routes stored in said routing tables;

storing determined average settling times of routes in a settling time table;

accessing the settling time table prior to the step of advertising and delaying the advertising of the routes which may change soon to damp oscillations of information in said routing tables;

retransmitting by each mobile host new routing information received from a neighboring mobile host; and

choosing a route from updated routing tables for transmitting a packet of information from a source mobile host as a route having a best "metric" for a desired destination mobile host, said best "metric" being a minimum number of hops that a packet must jump before reaching its destination.

6. A method for routing a packet of information between two mobile hosts that are coupled to an ad-hoc network comprised of a plurality of mobile hosts, each of the mobile hosts having a unique network address but not having a fixed location, said ad-hoc network conforming to a network standard including a network-layer and a link-layer, said method comprising the steps of:

storing routing tables at each mobile host., said routing tables including a "metric" defined as a number of hops from a source mobile host to a destination mobile host;

storing routing information in said routing tables based on link-layer addresses of the mobile hosts;

advertising routes by periodically broadcasting by each mobile host the routing table stored by the mobile host;

originating a time stamp by a destination mobile host;

tagging each route table entry with a time stamp originated by the destination mobile host;

updating, for each destination mobile host, mobile host stored routing tables based on received broadcasts from other mobile hosts;

keeping data about how often routes, stored in said routing tables, change;

measuring stabilities of routes by determining average settling times of the routes stored in said routing tables;

storing determined average settling times of routes in the settling time table;

accessing the settling time table prior to the step of advertising and delaying the advertising the routes which may change soon to damp oscillations of information in said routing tables;

retransmitting by each mobile host new routing information received from a neighboring mobile host; and

choosing a route from updated routing tables for transmitting a packet of information from a source mobile host as a route having a best "metric" for a desired destination mobile host, said best "metric" being a minimum number Of hops that a packet must jump before reaching its destination.

8. A method for routing a packet of information between two mobile hosts that are coupled to an ad-hoc network comprised of a plurality of mobile hosts, each of the mobile hosts having a unique network address but not having a fixed network location, wherein the ad-hoc network conforms to a network standard including a network-layer and a link-layer, said method comprising the steps of:

storing link-layer routing tables at each mobile host, said routing tables including a "metric" defined as a number of hops from a source mobile host to a destination mobile host;

advertising routes by periodically broadcasting by each mobile host the routing table stored by the mobile host;

originating a time stamp by a destination mobile host;

tagging each route table entry with a time stamp originated by the destination mobile host;

updating, for each destination mobile host, mobile host stored routing tables based on received broadcasts from other mobile hosts, said updating being limited to new routes defined to be those with a better metric, a better metric being a fewer number of hops a packet must jump before reaching its destination, or a metric of infinity, a metric of infinity indicating a broken link meaning that a particular destination is no longer reachable and thus all other destinations depending upon the newly unreachable destination are themselves unreachable;

retransmitting by each mobile host new routing information received from a neighboring mobile host, said step of retransmitting new routing information received from a neighboring mobile host being performed immediately upon reception of new routing information by a mobile host; and

choosing a route from updated routing tables for transmitting a packet of information from a source mobile host as a route having a best "metric" for a desired destination mobile host, said best "metric" being a minimum number Of hops that a packet must jump before reaching its destination.

9. The method of routing recited in claim 8 further comprising the steps of:

keeping data about how often routes stored in said route tables change;

measuring stabilities of routes by determining average settling times of the routes stored in said route tables;

storing measured settling times of routes in a settling time table; and

accessing the settling time table prior to the step of advertising and delaying the advertising the routes which may change soon to damp oscillations of information in said route tables.

10. The method of routing recited in claim 9 further comprising the step of weighting the measured settling times of routes by counting a most recent measurement of the settling time of a particular route with a higher weighting factor than less recent measurements.