Scalable methods and devices for computing routing paths within the internet

1. A method for computing routing paths within the Internet comprising:

identifying one or more nodes;

assigning a topologically encoded Internet address, of at most a length of k log n bits, to each of the identified nodes such that any two nodes may be determined to be adjacent within a time period that is proportional to the size of the assigned addresses, where “k” is a constant and is independent of the size of a network comprising “n” nodes.

2. A method for computing routing paths within the Internet comprising:

identifying one or more nodes;

assigning a topologically encoded Internet address to each of the identified nodes; and

determining whether any two identified nodes are adjacent within a time period that is proportional to the logarithm of the size of the network (“log n”).

3. A method for computing routing paths within the Internet using nodes that have previously been assigned Internet addresses comprising:

identifying on or more nodes that have previously been assigned Internet addresses

assigning a topologically encoded Internet address to each identified node such that the encoded address assigned to each node is represented by a number of bits which is no more than a constant factor larger than a number of bits representing a previously assigned Internet address, and such that two nodes may be determined to be adjacent within a time period that is proportional to the logarithm of the size of the network.

4. The method as in claim 1 further comprising

routing information from one node to another node using the topologically encoded Internet addresses.

5. The method as in claim 4 further comprising:

determining whether a destination node is unreachable from a source node within a certain number of hops using the topologically encoded Internet addresses;

expanding a neighborhood of hops when said destination node is unreachable; and

routing information to the destination node using the expanded neighborhood of hops.

6. The method as in claim 5 further comprising determining a routing path associated with a shortest distance between the source and destination nodes using the topologically encoded Internet addresses.

7. The method as in claim 6 further comprising determining a routing path that is a distance which is within a certain percentage of a shortest distance between the source and destination nodes using the topologically encoded Internet addresses.

8. A device for computing routing paths within the Internet operable to:

identify one or more nodes;

assign a topologically encoded Internet address, of at most a length of k log n bits, to each of the identified nodes such that any two nodes may be determined to be adjacent within a time period that is proportional to the size of the assigned addresses, where “k” is a constant and is independent of the size of a network comprising “n” nodes.

9. A device for computing routing paths within the Internet operable to:

identify one or more nodes;

assign a topologically encoded Internet address to each of the identified nodes; and

determine whether any two identified nodes are adjacent within a time period that is proportional to the logarithm of the size of the network (“log n”).

10. A device for computing routing paths within the Internet using nodes that have previously been assigned Internet addresses operable to:

identify on or more nodes that have previously been assigned Internet addresses; and

assign a topologically encoded Internet address to each identified node such that the encoded address assigned to each node is represented by a number of bits which is no more than a constant factor larger than a number of bits representing a previously assigned Internet address, and such that two nodes may be determined to be adjacent within a time period that is proportional to the logarithm of the size of the network.

11. The device as in claim 10 where the device comprises a router.

12. The device as in claim 8 further operable to

route information from one node to another node using the topologically encoded Internet addresses.

13. The device as in claim 12 further operable to:

determine whether a destination node is unreachable from a source node within a certain number of hops using the topologically encoded Internet addresses;

expand a neighborhood of hops when said destination node is unreachable; and

route information to the destination node using the expanded neighborhood of hops.

14. The device as in claim 13 further operable to determine a routing path associated with a shortest distance between the source and destination nodes using the topologically encoded Internet addresses.

15. The device as in claim 14 further operable to determine a routing path that is a distance which is within a certain percentage of a shortest distance between the source and destination nodes using the topologically encoded Internet addresses.

16. The device as in claim 8 wherein the device comprises a router.