Methods and systems for a routing protocol

• US 7,996,558 B2
• Filed: 07/31/2007
• Issued: 08/09/2011
• Est. Priority Date: 03/01/2005
• Status: Expired due to Fees

• Current Assignee: Industrial Technology Research Institute
• Original Assignee: Industrial Technology Research Institute
• Inventors: Yang, Jen-Shun, Hsu, Yuan-Ying, Tseng, Chien-Chao
• Primary Examiner(s): Eng; George
• Assistant Examiner(s): Torres; Marcos L
• Application Number:
  US11/882,224
• Publication Number:
  US 20080040507A1
• Time in Patent Office: 1,470 Days
• Field of Search: 370/310, 370/349, 370/351, 370/386, 370/389, 455/445, 709220-222, 709238-245
• US Class Current: 709/241
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/34 Source routing
• CPC Class Codes: H04L 45/48 Routing tree calculation
• CPC Class Codes: H04W 40/246 Connectivity information discovery

Abstract

A method for routing data, using a stateless routing protocol includes communicating data between a source host and a destination host in a network with a plurality of hosts. Each host in the network has a unique numerical address. The method comprises determining a least common ancestor host of the source host and the destination host using the unique numerical address of each of the source and destination hosts. The data is sent from the source host to the least common ancestor host, and then sent from the least common ancestor host to the destination host. Alternatively, the data can be routed using a stateful routing protocol in which each host records the address of its neighbors and forwards the data to the neighbor host that is closest to the destination host.

Claims

1. A method for routing data, using a stateless routing protocol, between a source host and a destination host in a network including a plurality of hosts, wherein each of the hosts has a unique numerical address, the method comprising:

determining a least common ancestor host of the source host and the destination host using the unique numerical address of each of the source and destination hosts, the determining further comprising;

calculating a first prime factorization sequence for the source host numerical address;

calculating a second prime factorization sequence for the destination host numerical address; and

using the first and second prime factorization sequences to calculate a least common ancestor host unique numerical address by a greatest common divisor (GCD) calculation;

sending the data from the source host to the least common ancestor host;

sending the data from the least common ancestor host to the destination host; and

processing the data at the destination host.

2. The method of claim 1, wherein using the first and second prime factorization sequences further comprises:

comparing the first and second prime factorization sequences to determine a longest common prefix; and

calculating the least common ancestor host unique numerical address by multiplying together all numbers in the longest common prefix.

3. The method of claim 1, wherein the stateless routing protocol is implemented using source routing.

4. The method of claim 3, further comprising:

building a first route segment from the source host to the least common ancestor host by recursively adding parent hosts to a route list;

building a second route segment from the least common ancestor host to the destination host by calculating a prime factorization sequence of a result of dividing the unique numerical address of the destination host by the unique numerical address of the least common ancestor host, to add any further host to the route list.

5. The method of claim 1, wherein the stateless routing protocol is implemented using hop-by-hop routing.

6. The method of claim 5, wherein a current host in the network receives data to send to the destination host, the current host:

determining whether or not it is in a first or a second route segment;

sending the data to a parent host if it determines that it is in the first route segment;

sending the data to a child host if it determines that it is in the second route segment; and

wherein the child host is selected using a prime factorization sequence of a result of dividing the unique numerical address of the destination host address by the current host address.

7. A system for routing data between a plurality of networked hosts with unique numerical addresses using a stateless routing protocol, the system comprising:

a sending host adapted to;

determine a least common ancestor host using the unique numerical address of each of the source and destination hosts, by;

calculating a first prime factorization sequence for the source host numerical address,

calculating a second prime factorization sequence for the destination host numerical address, and

using the first and second prime factorization sequences to calculate a least common ancestor host unique numerical address by a greatest common divisor (GCD) calculation, and

send data to the least common ancestor host; and

a destination host to receive the data from the least common ancestor host and processes the data.

8. The system of claim 7, wherein the using the first and second prime factorization sequences is further adapted to:

compare the first and second prime factorization sequences to determine a longest common prefix; and

calculate a least common ancestor host unique numerical address by multiplying together all numbers in the longest common prefix.

9. The system of claim 7, wherein the stateless routing protocol is implemented using source routing.

10. The system of claim 9, wherein the sending host is adapted to:

build a first route segment from the source host to the least common ancestor host by recursively adding parent hosts to a route list; and

build a second route segment from the least common ancestor host to the destination host by calculating a prime factorization sequence of a result of dividing the numerical address of the destination host by the numerical address of the least common ancestor host to add any further host to the route list.

11. The system of claim 7, wherein the stateless routing protocol is implemented using hop-by-hop routing.

12. The system of claim 11, wherein a current host in the network receives data to send to the destination host, the current host adapted to:

determine whether or not it is in a first or a second route segment;

send the data to a parent host if it determines that it is in the first route segment; and

send the data to a child host if it determines that it is in the second route segment;

wherein the child host is selected using a prime factorization sequence of a result of dividing the numerical address of the destination host address by the current host address.