Apparatus, and associated method, for routing packet data in an ad hoc, wireless communication system

• US 6,775,258 B1
• Filed: 03/17/2000
• Issued: 08/10/2004
• Est. Priority Date: 03/17/2000
• Status: Expired due to Term

• Current Assignee: CommWorks Solutions, LLC (IP Investments Group LLC)
• Original Assignee: Nokia Corporation
• Inventors: Palomar, Marc Solsona, van Valkenburg, Sander
• Primary Examiner(s): Pham, Chi
• Assistant Examiner(s): HOANG, THAI D
• Application Number:
  US09/527,786
• Time in Patent Office: 1,607 Days
• Field of Search: 370/320, 370/335, 370/338, 370/342, 370/349, 370/389-390, 370/392-393, 370/400-404, 370/475, 455/507, 455/517, 455/524, 455/525, 455/95
• US Class Current: 370/338
• 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/44 Distributed routing
• CPC Class Codes: H04L 67/04 specially adapted for terminals or networks with limited capabilities; specially adapted for terminal portability
• CPC Class Codes: H04L 69/16 Implementation or adaptation of Internet protocol [IP], of transmission control protocol [TCP] or of user datagram protocol [UDP]
• CPC Class Codes: H04L 69/161 Implementation details of TCP/IP or UDP/IP stack architecture; Specification of modified or new header fields
• CPC Class Codes: H04L 69/167 Adaptation for transition between two IP versions, e.g. between IPv4 and IPv6 translation of Internet protocol [IP] addresses H04L61/2503
• CPC Class Codes: H04L 69/22 Parsing or analysis of headers
• CPC Class Codes: H04W 40/02 Communication route or path selection, e.g. power-based or shortest path routing
• CPC Class Codes: H04W 8/087 for preserving data network PoA address despite hand-offs
• CPC Class Codes: H04W 84/20 Master-slave selection or change arrangements
• CPC Class Codes: H04W 88/04 adapted for relaying to or from another terminal or user

Abstract

Apparatus, and an associated method, by which to route packets of data between a data source node and a data destination node in an ad hoc, wireless network, such as a Bluetooth scatternet. Data routing tables are provided to each node, and header information extracted from a packet header is used by such tables. Routing of a packet of data is effectuated in a hop-by-hop manner to effectuate the communication of the packet from the data source node to the data destination node.

Claims

1. In a multinode, ad hoc, wireless communication system having at least a data source node and a data destination node, and the communication system selectably and dynamically formed of a first piconet at which the data source node is positioned and a second piconet at which a data destination node is positioned, each of the first and at least second piconets having a master node and at least one slave node, the at least one slave node capable of communication of the packets of data only to an associated master node, the data source node forming a selected one of a slave node and a master node of the first piconet and the data destination node a selected one of a slave node and a master node of the second piconet, an improvement of apparatus for facilitating routing of packets of data between the data source node and the data destination node by way of a communication path, the communication path having at least one node, inclusive of the data destination node, said apparatus comprising:

at least one first routing table embodied at each of the at least one node of the communication path and having an incoming data ledger and an outgoing data ledger, said first routing table for facilitating mapping an incoming data packet to an outgoing data packet, said first routing table populated with values extracted from header information of the packets, the packets routed in a first manner using values of the at least one first routing table when the node at which said at least one first routing table is embodied forms a slave node and the packets routed in a second manner using values of the at least one first routing table when the node at which said at least one first routing table is embodied forms a master node.

2. The apparatus of claim 1 wherein the communication path includes a first node and at least a second node, and wherein a first routing table of said at least one first routing table is embodied at the first node and another first routing table of said at least one first routing table is embodied at the second node.

3. The apparatus of claim 2 wherein the first node comprises the data source node and the at least the second node comprises an intermediary node, positioned along the communication path between the data source node and the data destination node, wherein the incoming data ledger of the first routing table located at the data source node includes an indication of an identifier identifying the data source node, and an indication of an identifier identifying the packet of data to be communicated by the data source node.

4. The apparatus of claim 3 wherein the outgoing data ledger of the first routing table located at the data source node includes an indication of an identifier identifying the data source node and an indication of the identifier identifying the packet of data to be communicated by the data source node, incremented by an incrementation value.

5. The apparatus of claim 4 wherein the first routing table located at the intermediary node includes an incoming data ledger and an outgoing data ledger, the incoming data ledger thereof including an indication of an identifier identifying the data source node and an indication of an identifier identifying the packet of data communicated by the data source node to the intermediary node, and the outgoing data ledger thereof including an indication of an identifier identifying the intermediary node in the communication path and an indication of an identifier identifying the packet of data to be communicated by the intermediary node to a subsequent.

6. The apparatus of claim 5 wherein the subsequent node comprises the data destination node, the data destination node further having a first routing table, said first routing table further having an incoming data ledger and an outgoing data ledger, the incoming data ledger including an indication of an identifier identifying the intermediary node and an identifier identifying the packet data incremented by the incrementation value and the outgoing data ledger thereof including an indication of an identifier identifying the data destination node.

7. The apparatus of claim 1 further comprising a packet header generator coupled to receive data to be communicated by the data source node, said packet header generator for generating a packet header to be combined with a portion of the data to be communicated to by the data source node to form packet data, the packet header generated by said packet header generator including a local identification field indicating a local address by which the data source node is identified, a broadcast flag field identifying whether the packet data forms a broadcast packet, a next-header field indicating a next-header value, a sequence number field indicating a packet identifier, and a destination address field indicating an address of a node in the communication path.

8. The apparatus of claim 7 wherein information contained in the packet header is extracted to be stored at the incoming data ledger and the outgoing data ledger of said at least one routing table.

9. In a multinode, ad hoc, wireless communication system having at least a data source node and a data destination node, and the communication system selectably and dynamically formed of a first piconet at which the data source node is positioned and a second piconet at which a data destination node is positioned, each of the first and at least second piconets having a master node and at least one slave node, the at least one slave node capable of communication of the packets of data only to an associated master node, a selected one of a slave node and a master node of the first piconet, and the data destination node a selected one of a slave node and a master node of the second piconet, an improvement of apparatus for facilitating routing of packets of data between the data source node and the data destination node by way of a communication path, the communication path having at least one node, inclusive of the data destination node, said apparatus comprising:

at least one first routing table embodied at each of the at least one node of the communication path and having an incoming data ledger and an outgoing data ledger, said first routing table for facilitating mapping an incoming data packet to an outgoing data packet; and

at least one second routing table embodied at each of the at least one node of the communication path, said second routing table for mapping an IP address to an address of a subsequent node in the communication path extending between the data source node and the data destination node, the packets routed in a first manner using values of the at least one first routing table and of the at least one second routing table when the node at which the first and second routing tables, respectively, are embodied forms a slave node and the packets routed in a second manner using values of the at least one second routing table when the node at which the first and second routing tables are embodied forms a master node.

10. The apparatus of claim 9 wherein the communication path includes a first node and at least a second node, and wherein said at least one second routing table comprises a second routing table of said at least one second routing table located at the first node and another a second routing table of said at least one second routing table located at the second node.

11. The apparatus of claim 9 wherein the multinode, ad hoc, communication system comprises a Bluetooth scatternet, wherein the data source node and the data destination node each comprise mobile Bluetooth terminals, the Bluetooth scatternet defining at least one node in the communication path to be a master node and at least one node in the communication path to be a slave node, said apparatus further comprising at least one third mapping table, said third mapping table having a local identifier ledger and a globally-unique identifier ledger, said third mapping table for mapping a currently-allocated local identifier to a globally-unique identifier.

12. A method for facilitating routing of packets of data upon a multinodal communication path including at least a data source node and a data destination node in an ad hoc, wireless communication system, and the communication system selectably and dynamically formed of a first piconet at which the data source node is positioned and a second piconet at which the data destination is positioned each of the first and at least second piconets having a master node and at least one slave node, the at least one slave node capable of communication of the packets of data only to an associated master node, the data source node forming a selected one of a slave node and a master node of the first piconet and the data destination node a selected one of a slave node and a master node of the second piconet, said method comprising:

forming at least a first routing table at each node of the communication path, the first routing table having an incoming data ledger and an outgoing data ledger;

routing the packet data upon the communication path, the packets routed in a first manner using values of the at least the first routing table when the node at which the at least one first routing table is embodied forms a slave node and the packets routed in a second manner using values of the at least one first routing table when the node at which the at least one first routing table is embodied forms a master node; and

as the packet data is routed to each node of the communication path, extracting first selected information from the packet data and inserting the information into the incoming data ledger and of the first routing table, selectably amending the packet data, and inserting second selected information into the outgoing data ledger of the first routing table.

13. The method of claim 12 wherein the first selected information inserted into the incoming data ledger at each node includes an indication of an identifier of a prior node through which the packet data is routed and an indication of an identifier identifying the packet data to be communicated through the communication path.

14. The method of claim 13 wherein the second selected information inserted into the outgoing ledger at each node includes an identifier identifying the node at which each respective first routing table is located.

15. The method of claim 12 further comprising the additional operation of forming a second routing table at each node of the communication path, each second routing table for mapping an IP address to an address of a subsequent node in the communication path.

16. The method of claim 15 wherein the ad hoc, wireless communication system comprises a Bluetooth scatternet, wherein the data source node and the data destination node each comprise Bluetooth terminals, said method comprising the further operation of forming a third mapping table at each node, the third mapping table having a local identifier ledger and a identifier ledger, each third mapping table for mapping a currently-allocated local identifier to an identifier.

17. The method of claim 16 further comprising the operation of generating a packet header for each data packet of the packet data.