Protocol specification for message-initiated constraint-based routing

• US 20040246904A1
• Filed: 06/03/2003
• Published: 12/09/2004
• Est. Priority Date: 06/03/2003
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Palo Alto Research Center, Inc. (Xerox Holdings Corp.)
• Inventors: Zhang, Ying, Crawford, Lara S., Fromherz, Markus P.J., Shang, Yi
• Granted Patent: US 7,577,107 B2
• Time in Patent Office: Days
• US Class Current: 370/252
• 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/124 using a combination of metrics
• CPC Class Codes: H04W 40/10 based on available power or energy
• CPC Class Codes: H04W 40/12 based on transmission quality or channel quality
• CPC Class Codes: H04W 40/20 based on geographic position or location
• CPC Class Codes: H04W 40/246 Connectivity information discovery
• CPC Class Codes: H04W 40/248 Connectivity information update
• CPC Class Codes: H04W 40/26 for hybrid routing by combining proactive and reactive routing
• CPC Class Codes: Y10S 370/913 Wireless or radio

Abstract

A method is presented for message-initiated constraint-based routing for digital message communication among nodes in an ad-hoc network, in which each node includes attributes having attribute values. The method includes determining local attributes for each of the nodes in the ad-hoc network and defining constraints on the attributes. Each node is provided access to the attributes of each neighboring node, with a neighboring node being a node that is one hop away. Each message transmitted over the ad-hoc network has a message type, which includes a destination specification, route specification, and objective specification. Constraint checking and cost estimation checking are performed for each message type. The message that is routed within the network includes the address of a sending node, the address of the source node, route and destination constraints, the number of route constraints, the number of destination constraints, message identification number, sequence identification number, and routing objectives.

Claims

1. A method of message-initiated constraint-based routing for digital message communication among nodes in an ad-hoc network, wherein each node includes a plurality of attributes having attribute values, comprising:

determining local attributes for each of the nodes in the ad-hoc network;

providing access to the attributes of each neighboring node, wherein said neighboring node is a node one hop away from a current node within the ad-hoc network;

estimating the minimum and maximum values of at least one attribute within the plurality of attributes;

defining constraints on the plurality of attributes;

performing constraint checking for each message type, wherein a message type includes a destination specification, route specification, and objective specification;

performing cost estimation checking for each said message type, wherein cost is defined as the total value of an attribute along a message path; and

routing a message within the ad-hoc network, said message including the address of a sending node, the address of the source node, route and destination constraints, the number of route constraints, the number of destination constraints, message identification number, sequence identification number, and routing objectives.

2. The method of message-initiated constraint-based routing according to claim 1, wherein determining local attributes comprises reading said local attributes.

3. The method of message-initiated constraint-based routing according to claim 1, wherein determining local attributes comprises computing said local attributes.

4. The method of message-initiated constraint-based routing according to claim 1, wherein determining local attributes further comprises:

determining whether significant changes have occurred to said local attributes;

providing local attributes to neighbor nodes if at least one significant change has occurred; and

providing local attributes to neighbor nodes if triggered by a timer.

5. The method of message-initiated constraint-based routing according to claim 1, wherein providing access to the attributes of each neighboring node comprises:

receiving the attributes of at least one neighbor node, wherein said neighbor node is identified from its address;

updating said attributes of said at least one neighbor node within the database of said first node;

increasing the message count from said neighbor node by one; and

performing a message count review, wherein said message count review checks the number of messages received between triggers of an expire timer.

6. The method of message-initiated constraint-based routing according to claim 5, wherein performing the message count review comprises:

checking the number of messages received since the previous trigger event;

setting the neighbor node as inactive and then as zero if the message count is less than a threshold value; and

resetting the neighbor node as zero if the message count in not less than said threshold value.

7. The method of message-initiated constraint-based routing according to claim 1, wherein said message further comprises a routing strategy identification number for identifying a routing strategy type.

8. The method of message-initiated constraint-based routing according to claim 1, wherein said destination constraints route a message communicated among nodes within the ad-hoc network to not less than one node location.

9. The method of message-initiated constraint-based routing according to claim 1, wherein said destination constraints route a message communicated among nodes within the ad-hoc network to a plurality of nodes within the ad-hoc network.

10. The method of message-initiated constraint-based routing according to claim 1, wherein said route constraints permit a message to be routed only via a specified subset of nodes within the ad-hoc network.

11. The method of message-initiated constraint-based routing according to claim 7, wherein said routing strategy type comprises a flooding-based routing strategy.

12. The method of message-initiated constraint-based routing according to claim 7, wherein said routing strategy type comprises a search-based routing strategy.

13. The method of message-initiated constraint-based routing according to claim 1, wherein said message identification number identifies the source of not less than one forward message.

14. The method of message-initiated constraint-based routing according to claim 13, wherein said message identification number further comprises identifying components of said forward message.

15. The method of message-initiated constraint-based routing according to claim 11, wherein said flooding-based routing strategy comprises:

receiving not less than one forward message from not less than one source node within the ad-hoc network;

determining whether said forward message is of a new type;

identifying an appropriate entry for said forward message type;

reviewing the destination of said forward message and processing said forward message if said destination has been reached; and

reviewing the destination of said forward message and updating said forward message with identification of the intermediate node through which said forward message has passed and broadcasting said forward message to at least one next node if said destination has not been reached.

16. The method of message-initiated constraint-based routing according to claim 15, further comprising estimating cost of said forward message, wherein cost is defined as total value of at least one attribute along a message path.

17. The method of message-initiated constraint-based routing according to claim 15, further comprising sending a confirmation message to said source node.

18. The method of message-initiated constraint-based routing according to claim 12, wherein said search-based routing strategy comprises:

receiving not less than one forward message from not less than one source node within the ad-hoc network;

determining whether said forward message is of a new type;

identifying an appropriate entry for said forward message type;

estimating a cost for transmission of said forward message;

reviewing the destination of said forward message and processing said forward message if said destination has been reached; and

reviewing the destination of said forward message and selecting a next node for receipt of said forward message, updating said forward message with identification of the intermediate node through which said forward message has passed, and transmitting said forward message to said next node if said destination has not been reached.

19. The method of message-initiated constraint-based routing according to claim 18, further comprising sending a destination confirmation to said source node.

20. The method of message-initiated constraint-based routing according to claim 1, further comprising estimating the minimum and maximum changes in at least one attribute among a plurality of nodes.

21. A system of message-initiated constraint-based routing for digital message communication among nodes in an ad-hoc network, wherein each node includes a plurality of attributes having attribute values, comprising:

local attribute module means for determining local attributes for each of the nodes in the ad-hoc network;

remote attribute module means for providing access to the attributes of each neighboring node, wherein said neighboring node is a node one hop away from a current node within the ad-hoc network;

timer module for providing a time trigger function for said local attribute module and said remote attribute module;

broadcast module for providing a send function for said local attribute module and a receive function for said remote attribute module;

attribute property module for estimating the minimum and maximum values of at least one attribute within the plurality of attributes;

constraint module for defining constraints on the plurality of attributes, performing constraint checking for each message type, wherein a message type includes a destination specification, route specification, and objective specification, and performing cost estimation checking for each said message type, wherein cost is defined as the total value of at least one attribute along a message path; and

routing module for routing a message within the ad-hoc network, said message including the address of a sending node, the address of the source node, route and destination constraints, the number of route constraints, the number of destination constraints, message identification number, sequence identification number, and routing objectives.

22. The system for message-initiated constraint-based routing according to claim 21, wherein said local attribute module comprises:

means for reading or computing local attributes under direction of an update timer;

means for determining significant changes to local attributes; and

means for broadcasting said significant changes to nodes within the ad-hoc network.

23. The system for message-initiated constraint-based routing according to claim 21, wherein said remote attribute module comprises:

means for receiving said set of remote attributes of not less than one neighbor node;

means for identifying each of said neighbor nodes that is the source of said received set of remote attributes;

means for updating said attributes of said neighbor nodes within a database of a receiving node; and

means for increasing the message count for messages received from each said neighbor nodes.

24. The system for message-initiated constraint-based routing according to claim 23, further comprising:

means for determining if said message count for each neighbor node is less than a threshold value;

means for identifying a neighbor node as inactive if said message count is less than said threshold value;

means for setting a neighbor node message count to zero if said received message count is greater than said threshold value; and

means for setting a neighbor node message count to zero if said neighbor node has been identified as inactive.

25. The system for message-initiated constraint-based routing according to claim 21, wherein said message further comprises a routing strategy identification number for identifying a routing strategy type.

26. The system for message-initiated constraint-based routing according to claim 21, wherein said destination constraints route a message communicated among nodes within the ad-hoc network to not less than one node location.

27. The system for message-initiated constraint-based routing according to claim 21, wherein said destination constraints route a message communicated among nodes within the ad-hoc network to a plurality of nodes within the ad-hoc network.

28. The system for message-initiated constraint-based routing according to claim 21, wherein said route constraints permit a message to be routed only via a specified subset of nodes within the ad-hoc network.

29. The system for message-initiated constraint-based routing according to claim 25, wherein said routing strategy type comprises a flooding-based routing strategy.

30. The system for message-initiated constraint-based routing according to claim 25, wherein said routing strategy type comprises a search-based routing strategy.

31. The system for message-initiated constraint-based routing according to claim 21, further comprising means for estimating the minimum and maximum changes in at least one attribute among a plurality of nodes within the ad-hoc network.

32. An article of manufacture comprising a computer usable medium having computer readable program code embodied in said medium which, when said program code is executed by said computer causes said computer to perform method steps for message-initiated constraint-based routing for digital message communication among nodes in an ad-hoc network, wherein each node includes a plurality of attributes having attribute values, the method comprising:

determining local attributes for each of the nodes in the ad-hoc network;

providing access to the attributes of each neighboring node, wherein said neighboring node is a node one hop away from a current node within the ad-hoc network;

estimating the minimum and maximum values of at least one attribute within the plurality of attributes;

defining constraints on the plurality of attributes;

performing constraint checking for each message type, wherein a message type includes a destination specification, route specification, and objective specification;

performing cost estimation checking for each said message type, wherein cost is defined as the total value of an attribute along a message path; and

routing a message within the ad-hoc network, said message including the address of a sending node, the address of the source node, route and destination constraints, the number of route constraints, the number of destination constraints, message identification number, sequence identification number, and routing objectives.