METHOD FOR DYNAMIC ROUTING USING TUNNELING

• US 20100074161A1
• Filed: 09/22/2008
• Published: 03/25/2010
• Est. Priority Date: 09/22/2008
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Schott, Wolfgang, Munari, Andrea
• Granted Patent: US 8,457,134 B2
• Time in Patent Office: Days
• US Class Current: 370/315
• CPC Class Codes: H04L 45/16 Multipoint routing
• CPC Class Codes: H04W 40/24 Connectivity information management, e.g. connectivity discovery or connectivity update

Abstract

Techniques for routing data from a source to a destination in a wireless network are provided. The techniques include broadcasting one or more messages in a network to identify a set of one or more nodes that can be used to forward data towards a destination, routing data from a source to the destination by way of a sequence of one or more data transmissions involving the one or more identified nodes, wherein each data transmission comprises a node that has data addressed to the destination to trigger a distributed procedure among the one or more identified nodes to select a relaying node, and sending the data to the selected relaying node until the destination is reached.

Claims

1. A method for routing data from a source to a destination in a wireless network, comprising the steps of:

broadcasting one or more messages in a network to identify a set of one or more nodes that can be used to forward data towards a destination;

routing data from a source to the destination by way of a sequence of one or more data transmissions involving the one or more identified nodes, wherein each data transmission comprises a node that has data addressed to the destination to trigger a distributed procedure among the one or more identified nodes to select a relaying node; and

sending the data to the selected relaying node until the destination is reached.

2. The method of claim 1, further comprising generating one or more forward route construction procedures.

3. The method of claim 2, wherein generating one or more forward route construction procedures comprises:

a source node broadcasting a route request (RREQ) packet;

one or more nodes that decode the packet comparing information contained in the RREQ with information contained in a routing table of each of the one or more nodes;

determining if the one or more nodes are suitable to be part of the one or more nodes that can be used to forward data towards the destination according to a given criterion; and

if the one or more nodes are suitable to be part of the one or more nodes that can be used to forward data towards the destination, switching on a forward route flag, updating the routing table of each of the one or more nodes and re-broadcasting an updated version of the RREQ packet.

4. The method of claim 1, further comprising generating one or more backward route construction procedures.

5. The method of claim 4, wherein generating one or more backward route constructions comprises:

a destination node broadcasting a route reply (RREP) packet;

one or more nodes decoding the RREP packet comparing information contained in the RREP packet with information contained in a routing table of each of the one or more nodes;

determining if the one or more nodes are suitable to be part of the one or more nodes that can be used to forward data towards the destination according to a given criterion; and

if the one or more nodes are suitable to be part of the one or more nodes that can be used to forward data towards the destination, switching on a backward route flag, updating the routing table of each of the one or more nodes and re-broadcasting an updated version of the RREP packet.

6. The method of claim 1, further comprising using information gathered during forward route construction and backward route construction to guarantee converge-casting.

7. The method of claim 1, further comprising generating a data forwarding procedure.

8. The method of claim 7, wherein generating a data forwarding procedure comprises:

a source node receiving a route reply (RREP) packet from a destination to which it is trying to connect;

setting the source to be a current hop;

transmitting, from the current hop node a request to send packet;

identifying a next hop node by way of a distributed procedure, wherein each of the one or more nodes that receives the packet and that can be used to forward data towards a destination uses information contained in the packet to contend to be the next hop node;

selecting one of the one or more potential next hop nodes to be the next hop;

sending data meant for the destination from the current hop to the next hop;

setting the selected next hop to be the current hop; and

repeating the steps until the destination is reached.

9. The method of claim 8, wherein using the packet to contend to be the next hop node comprises computing a suitable metric and performing a backoff procedure.

10. The method of claim 1, further comprising generating a route recovery procedure.

11. The method of claim 10, wherein generating a route recovery procedure comprises finding a new set of one or more active nodes to remedy a condition wherein a node is not able to find a next hop to further forward data towards a destination node.

12. The method of claim 10, wherein generating a route recovery procedure comprises broadcasting a message to inform one or more surrounding nodes that a route is no longer value, and enabling a source node to decide how to proceed.

13. A computer program product comprising a computer readable medium having computer readable program code for routing data from a source to a destination in a wireless network, said computer program product including:

computer readable program code for broadcasting one or more messages in a network to identify a set of one or more nodes that can be used to forward data towards a destination;

computer readable program code for routing data from a source to the destination by way of a sequence of one or more data transmissions involving the one or more identified nodes, wherein each data transmission comprises a node that has data addressed to the destination to trigger a distributed procedure among the one or more identified nodes to select a relaying node; and

computer readable program code for sending the data to the selected relaying node until the destination is reached.

14. The computer program product of claim 13, further comprising computer readable program code for generating one or more forward route construction procedures.

15. The computer program product of claim 13, further comprising computer readable program code for generating one or more backward route construction procedures.

16. The computer program product of claim 13, further comprising computer readable program code for using information gathered during forward route construction and backward route construction to guarantee converge-casting.

17. The computer program product of claim 13, further comprising computer readable program code for generating a data forwarding procedure.

18. The computer program product of claim 13, further comprising computer readable program code for generating a route recovery procedure.

19. An apparatus for routing data from a source to a destination in a wireless network, comprising:

a memory; and

at least one processor coupled to said memory and operative to;

broadcast one or more messages in a network to identify a set of one or more nodes that can be used to forward data towards a destination;

route data from a source to the destination by way of a sequence of one or more data transmissions involving the one or more identified nodes, wherein each data transmission comprises a node that has data addressed to the destination to trigger a distributed procedure among the one or more identified nodes to select a relaying node; and

send the data to the selected relaying node until the destination is reached.

20. The apparatus of claim 19, wherein the at least one processor coupled to said memory is further operative to generate one or more forward route construction procedures.

21. The apparatus of claim 19, wherein the at least one processor coupled to said memory is further operative to generate one or more backward route construction procedures.

22. The apparatus of claim 19, wherein the at least one processor coupled to said memory is further operative to use information gathered during forward route construction and backward route construction to guarantee converge-casting.

23. The apparatus of claim 19, wherein the at least one processor coupled to said memory is further operative to generate a data forwarding procedure.

24. The apparatus of claim 19, wherein the at least one processor coupled to said memory is further operative to generate a route recovery procedure.

25. An apparatus for routing data from a source to a destination in a wireless network, said apparatus comprising:

means for broadcasting one or more messages in a network to identify a set of one or more nodes that can be used to forward data towards a destination;

means for routing data from a source to the destination by way of a sequence of one or more data transmissions involving the one or more identified nodes, wherein each data transmission comprises a node that has data addressed to the destination to trigger a distributed procedure among the one or more identified nodes to select a relaying node; and

means for sending the data to the selected relaying node until the destination is reached.