(12) United States Patent
`US 6,775,258 B1
`(45) Date of Patent:
`Aug. 10, 2004
`van Valkenburg et al.
`
`(10) Patent N0.:
`
`IJSOO6775258B1
`
`(54)
`
`APPARATUS, AND ASSOCIATED METHOD,
`FOR ROUTING PACKET DATA IN AN AD
`HOC, WIRELESS COMMUNICATION
`SYSTEM
`
`6,535,498 B1 *
`6,557,044 B1 *
`6,587,457 B1 *
`
`3/2003 Larsson et a1.
`............. 370/338
`
`4/2003 Cain et a1. ........... 709/242
`7/2003 Mikkonen ................... 370/356
`
`FOREIGN PATENT DOCUMENTS
`
`(75)
`
`Inventors: Sander van Valkenburg, Helsinki (Fl);
`Marc Solsona Palomar, Helsinki (Fl)
`
`(73)
`
`Assignee: Nokia Corporation, Espoo (Fl)
`
`(*)
`
`Notice:
`
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 0 days.
`
`(21)
`
`(22)
`
`(51)
`(52)
`(58)
`
`(56)
`
`Appl. No.: 09/527,786
`
`Filed:
`
`Mar. 17, 2000
`
`Int. Cl.7 .................................................. H04Q 7/24
`US. Cl.
`........................ 370/338; 370/349; 455/507
`Field of Search ................................. 370/320, 335,
`370/338, 342, 349, 389—390, 392—393,
`400—404, 475; 455/507, 517, 524, 525,
`95
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`5,371,734 A
`12/1994 Fischer ........................ 370/18
`5,412,654 A *
`5/1995 Perkins
`..... 370/312
`
`5,572,528 A
`11/1996 Shuen .................. 370/85
`
`
`5,875,186 A
`..... 370/331
`2/1999 Belanger et a1.
`5,926,468 A *
`..... 370/328
`7/1999 Chapman et al.
`
`5,964,841 A
`10/1999 Rekhter ................... 709/242
`5,987,011 A * 11/1999 Toh ..................... 370/331
`
`5,996,021 A
`11/1999 Civanlar et al.
`..... 709/238
`6,304,556 B1 * 10/2001 Haas ................... 370/254
`6,307,843 B1 * 10/2001 Okanoue .................... 370/312
`
`EP
`W0
`
`0 768 777 A2
`WO 99/05829
`
`4/1997
`2/1999
`
`OTHER PUBLICATIONS
`
`D. Groten and J .R. Schmidt; “Bluetooth—based Mobile Ad
`Hoc Networks: Opportunities and Challenges for a Tele-
`communications Operator”; Vehicular Technology Confer-
`ence on May 6—9, 2001; IEEE VTS 53rd, vol. 2, pp.
`1134—1138.*
`
`Y. Liu, M.J. Lee and TN. Saadawi; “A Bluetooth scattern-
`et—route structure for multihop ad hoc networks”; IEEE
`Journal on Selected Areas in Communications; vol. 21,
`Issue: 2, Feb. 2003; pp. 229—239.*
`
`(List continued on next page.)
`
`Primary Examiner—Chi Pham
`Assistant Examiner—Thai Hoang
`
`(57)
`
`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 com-
`munication of the packet from the data source node to the
`data destination node.
`
`17 Claims, 7 Drawing Sheets
`
`
`
`APPLE1040
`
`APPLE 1040
`
`1
`
`

`

`US 6,775,258 B1
`Page 2
`
`OTHER PUBLICATIONS
`
`M. Albrecht, M. Frank, P. Martini; M. Schetelig, A. Vila-
`Vaara and A. Wenzel; “IP Services over Bluetooth: Leading
`the Way to a New Mobility”; Conference on Oct. 18—20,
`1999; Local Computer Networks, 1999; pp. 2—11.*
`P. Bhagwat and A. Segall;“A Routing Vector Method (RVM)
`for Routing in Bluetooth Scatternets”; Mobile Multimedia
`Communications, 1999. (MoMuC ’99) 1999 IEEE Interna-
`tional Workshop on Nov. 15—17, 1999; pp. 375—379.*
`Broch, Josh, et al.; “A Performance Comparison of Multi—
`Hop Wireless Ad Hoc Network Routing Protocols”;
`XP—002199757; Proceedings of the Fourth Annual ACM/
`
`IEEE International Conference Mobile Computing and Net-
`working (MobiCom ’98), Oct. 25—20, 1998, Dallas, Texas,
`USA.; pp. 1—13.
`Broch, Josh, et al.; “The Dynamic Source Routing Protocol
`for Mobile Ad Hoc Networks”; XP—002199758;
`IETF
`Manet Working Group—Internet Draft; Mar. 13, 1998; pp.
`1—38.
`
`Perkins, Charles E., et al.; “Highly Dynamic Destination—
`Sequenced Distance—Vector Routing (DSDV) for Mobile
`Computers”; 8282 Computer Communication ReView Oct.
`24, (1994), No. 4, New York, US; pp. 234—244.
`
`* cited by examiner
`
`2
`
`

`

`US. Patent
`
`Aug. 10, 2004
`
`Sheet 1 0f 7
`
`US 6,775,258 B1
`
`1 1
`
`l9.
`
`, ’ ’
`
`x
`, slave 1
`l 7‘
`$2 8
`
`slave 3 ~
`..
`'9 ég
`:
`E
`
`I
`
`\
`I x\
`
`x
`
`l
`
`__ ‘
`
`’
`
`’
`
`II
`I
`24’
`l
`‘25
`‘
`\\
`
`‘\
`II
`:'
`[3,7 ‘
`I
`. master A
`master B
`é
`------l"""
`"
`"'----..|.
`.9
`|
`slave4
`’1..."
`l
`‘
`I,
`Z Z-
`\\
`
`00...
`
`I 6
`
`I
`
`v.14
`\ \
`\
`\
`
`\\
`‘
`I
`1815—.
`é I
`I
`
`\
`
`\
`
`\ \
`
`slavez 18~L
`\
`
`\
`
`\
`
`I
`
`slave 5
`
`\\/l
`I \
`I
`~ ‘ ~ _ — ’ ’
`
`I
`
`1’
`
`I
`
`§ ‘
`
`’ ’
`
`3
`
`

`

`US. Patent
`
`Aug. 10, 2004
`
`Sheet 2 0f 7
`
`US 6,775,258 B1
`
`10_.___
`
`——-
`
`'
`
`~~
`
`/
`
`I ’ ’
`
`v!
`
`15
`
`11 ’l 26:,
`\J
`31
`ll
`slave1
`
`slave3
`@R
`
`I
`
`,1
`
`18.1
`7.x!
`'L"
`
`2
`
`.
`
`.
`:
`5
`-'
`masterA
`
`I
`
`I
`
`I
`
`\\
`\
`\— _ —
`I823,” \
`/
`
`\
`
`\
`
`~‘
`slave6
`\
`.on \\
`\
`.°
`~
`'8 é \f‘ [L/
`"
`‘
`slave 4 I master B
`3 n n n . n n hn n .
`"W91
`
`‘_——
`
`~
`
`l
`
`’3'3
`
`@‘T‘
`
`slaves
`I.
`
`z
`
`/
`
`/
`‘ J. - — ’ ’
`I
`l
`
`I . n I I I’—:"‘ ' I ' a u I I n I I a I . I I l I
`lb
`\
`‘8'?
`
`U:
`
`32
`
`‘
`
`‘
`
`\
`
`\
`
`\
`
`\
`
`\
`
`\
`
`x
`
`\
`
`.0
`oo.0
`
`’
`
`®A
`slave2
`
`\
`
`\
`
`x
`
`\ ‘ ~
`
`’ ’ I
`
`I
`
`I
`
`4
`
`

`

`US. Patent
`
`Aug. 10, 2004
`
`Sheet 3 0f 7
`
`US 6,775,258 B1
`
`3
`
`
`
`
`3e,
`8
`”2’ m4
`
`5
`1516 45
`W)
`6 78
`3 4
`Local .0 E—El
`
`Destination Address
`
`23 24
`Sequence Number
`
`
`
`
`
`
`5
`
`

`

`US. Patent
`
`Aug. 10, 2004
`
`Sheet 4 0f 7
`
`US 6,775,258 B1
`
`Local ID
`
`Bluetooth Device Address
`
`AM_ADDR (3 bit)
`
`BD_ADDR (48 bit)
`
`6
`
`

`

`US. Patent
`
`Aug. 10, 2004
`
`Sheet 5 0f 7
`
`US 6,775,258 B1
`
`
`
`7
`
`

`

`US. Patent
`
`Aug. 10, 2004
`
`Sheet 6 0f 7
`
`US 6,775,258 B1
`
`
`
`\\
`5: J "\ I Z
`slahzgklgxzy
`
`F/(r,%§
`
`8
`
`

`

`US. Patent
`
`Aug. 10, 2004
`
`Sheet 7 0f 7
`
`US 6,775,258 B1
`
`
`Destination
`
`
`-ort number
`
`
`
`11?.
`
`9
`
`

`

`US 6,775,258 B1
`
`1
`
`APPARATUS, AND ASSOCIATED METHOD,
`FOR ROUTING PACKET DATA IN AN AD
`HOC, WIRELESS COMMUNICATION
`SYSTEM
`
`The present invention relates generally to a manner by
`which to communicate packet data in an ad hoc, wireless
`communication system, such as a Bluetooth scatternet. More
`particularly, the present invention relates to apparatus, and
`an associated method, by which to facilitate routing of
`packet-formatted data pursuant to a communication session
`in the Bluetooth scatternet, or other ad hoc, wireless com-
`munication system. A new packet header is provided to
`facilitate routing of the packet-formatted data so-formed.
`And, new tables are provided for each node in a communi-
`cation path utilized during a communication session to
`facilitate the routing of the packet data pursuant to a hop-
`by-hop communication scheme.
`
`BACKGROUND OF THE INVENTION
`
`Technological advancements in communication technolo-
`gies have permitted the introduction, and popularization of
`usage, of new types of communication systems. Communi-
`cation devices of both increased processing capacities and of
`smaller sizes are able to be utilized in applications and in
`situations not previously possible or practical.
`New wireless communication systems, and communica-
`tion devices operable therein, have been made possible as a
`result of such advancements. A cellular communication
`
`system capable of communicating packet data is exemplary
`of a new wireless communication system made possible as
`a result of technological advancements. A Cellular commu-
`nication system includes a network infrastructure which is
`installed in a geographical area and affixed in position.
`Mobile terminals operable in a cellular communication
`system communicate by way of the network infrastructure.
`Additional types of communication systems have been
`proposed which also take advantage of the advancements in
`communication technologies. For instance, ad hoc,
`i.e.,
`infrastructure-free, communication systems have been pro-
`posed. The Bluetooth standard sets forth an ad hoc, com-
`munication system which provides for wireless connectivity
`of a large number of different devices. Bluetooth devices are
`connectable in an ad hoc manner by way of short-distance
`radio links,
`thereby to permit data to be communicated
`between such Bluetooth devices. Each Bluetooth device
`
`forms a node in the Bluetooth system, sometimes referred to
`as a Bluetooth scatternet. But, because a Bluetooth system,
`unlike a cellular communication system, does not have a
`fixed infrastructure, effectuating communications there-
`through is made more difficult.
`The Bluetooth devices are potentially mobile, and move-
`ment of the Bluetooth devices necessitates corresponding
`link changes as a result of such movement. The Bluetooth
`standard defines piconets formed of a master and slave
`relationship between one Bluetooth device forming a master
`and up to seven Bluetooth devices forming slaves to the
`master. A master of one piconet might also be a slave in
`another piconet, and the piconets together define a scatter-
`net. Communications are effectuable between Bluetooth
`
`devices positioned within different piconets. Random access
`by a Bluetooth device to communicate in the Bluetooth
`scatternet is not permitted as the master Bluetooth device of
`each piconet controls the access to the system. Instead, to
`form a connection by which to effectuate a communication
`session, the Bluetooth devices must register with each other
`
`2
`in order to set up a connection in which of the devices, i.e.,
`the master, controls the connection.
`Existing routing protocols by which to communicate
`packet data do not adequately take into account the unique
`aspects of an ad hoc network. Routing protocols developed
`for fixed networks are not suitable as such protocols are not
`able to adapt to link changes which occur in a Bluetooth
`scatternet, or other ad hoc, network. And, while other
`routing protocols have been developed for general ad hoc
`networks, the unique features and limitations of a system
`implemented pursuant to the Bluetooth standard limit the
`usefulness of such existing routing protocols to effectuate
`communications in a Bluetooth scatternet. A routing proto-
`col for a Bluetooth scatternet must exhibit an appropriate
`trade-off between relieving nodes in a communication path
`formed pursuant to a communication session of processing,
`routing, and other overhead, information while also keeping
`track of the routes forming communication paths even in
`lieu in changing network topologies.
`If a manner could be provided by which better to route
`packet data in an ad hoc, wireless network, such as a
`Bluetooth scatternet,
`improved communications therein
`would be possible.
`It is in light of this background information related to ad
`hoc, wireless networks that the significant improvements of
`the present invention have evolved.
`SUMMARY OF THE INVENTION
`
`The present invention, accordingly, advantageously pro-
`vides apparatus, and an associated method, by which to
`facilitate routing of packet-formatted data and in an ad hoc,
`wireless communication system. Through operation of an
`embodiment of the present invention, routing of packet data
`between any pair of nodes within a Bluetooth scatternet is
`made possible.
`The routing protocol provided pursuant to an embodiment
`of the present invention is compatible with existing IPv4 and
`IPv6 protocols. Additionally, higher-layer protocols, such as
`TCP (Transport Control Protocol) or UDP, are overlayable
`upon the routing protocol, thereby to be transparent to users.
`In one aspect of the present invention, a new packet
`header structure is provided. The packet header structure is
`shorter,
`relative to conventional
`IP headers.
`In one
`implementation, the packet header structure, herein referred
`to as a PicoIPv4 packet structure, replaces existing IPv4
`packet headers. In another implementation, a new packet
`header structure, referred to herein by PicoIPv6, replaces
`conventional IPv6 packet headers. The type of header struc-
`ture utilized, for instance, is dependent upon the version of
`IP expected by a higher layer of protocol, such as the TCP
`or UDP layer.
`In another aspect of the present invention, new tables are
`defined for each Bluetooth device which forms a node in a
`
`communication path, inclusive of a Bluetooth data source
`node and a Bluetooth data destination node. Each Bluetooth,
`or other ad hoc, device is capable of forming a master device
`or a slave device, and each of the Bluetooth devices includes
`a mapping table for mapping incoming packets to outgoing
`packets received at, and forwarded on, by a communication
`node. Also, each of the devices includes an IP routing table
`for mapping IP addresses to a subsequent hop address
`defining a subsequent node in the communication path. And,
`each of the Bluetooth devices also includes a table that maps
`a currently-allocated local identifier and the device’s asso-
`ciated master’s identifier. Information utilized to fill the
`
`tables is obtained from packet header information contained
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`10
`
`10
`
`

`

`US 6,775,258 B1
`
`3
`in the packet header structure of packet data applied to each
`node in the communication path. By storing the information
`in the tables provided to each of the nodes, routing infor-
`mation thereby becomes stored at the tables of the nodes in
`the communication path.
`invention, datagram
`In another aspect of the present
`communication is provided to communicate packet data
`between a data source node and a data destination node
`
`within a piconet, within the Bluetooth scatternet, or between
`a node of the scatternet and a node of a fixed network, e.g.,
`the Internet, to which a Bluetooth device is coupled. Hop-
`by-hop routing of the packet data is utilized in which every
`node involved in the communication path from the data
`source node to the data destination node determines, based
`upon information stored at the tables of the respective nodes,
`to which next hop,
`i.e., node,
`the packet data is to be
`transported. Hop-by-hop routing is permitted as the routing
`information about all ongoing connections in a communi-
`cation path in the scatternet are contained in routing tables
`maintained by each node involved in the communication
`session or connection. Each packet is sent from hop to hop,
`i.e., from node to subsequent node, and must
`therefore
`contain an identifier for the subsequent hop and also the final
`destination, i.e., the data destination node. For the destina-
`tion node, the IP address thereof suffices, for the data source
`node, the local identifier thereof is utilized. Each packet is
`further identified to indicate the connection, that is, com-
`munication session. A sequence number is utilized to iden-
`tify packets. Each node that communicates a packet to a
`subsequent hop, i.e., node, identifies a packet belonging to
`a certain connection with a certain destination with a unique
`sequence number. The sequence number is assigned when
`setting up the connection.
`Due to the inherent mobility of at least some Bluetooth
`devices, their movement affects the routing tables contained
`at each of the devices. When a Bluetooth device moves, the
`location thereof within the Bluetooth scatternet changes, or,
`the Bluetooth device moves out of communication range of
`the scatternet. The tables provided to the Bluetooth devices
`pursuant to an embodiment of the present invention contain
`information in such tables to facilitate appropriate route
`setup, and rerouting, to take into account the movement of
`such Bluetooth devices.
`
`In these and other aspects, therefore, apparatus, and an
`associated method,
`is provided for facilitating routing of
`packets of data between a data source node and a data
`destination node by way of a communication path formed in
`a multinode, ad hoc, wireless communication system. The
`communication path has at least one node, inclusive of the
`data destination node. The apparatus comprises at least one
`first routing table having an incoming data ledger and an
`outgoing data ledger in which the first routing table maps an
`incoming data packet into an outgoing data packet.
`A more complete appreciation of the present invention
`and the scope thereof can be obtained from the accompa-
`nying drawings which are briefly summarized below, the
`following detailed description of the presently-preferred
`embodiments of the present invention, and the appended
`claims.
`
`BRIEF DESCRIPTION OF THE DRAWING
`
`FIG. 1 illustrates a functional representation of an exem-
`plary Bluetooth scatternet, exemplary of an ad hoc, wireless
`network in which an embodiment of he present invention is
`operable.
`FIG. 2 illustrates a functional representation, similar to
`that shown in FIG. 1, of a Bluetooth scatternet, also exem-
`
`4
`plary of an ad hoc network in which an embodiment of the
`present invention is operable.
`FIG. 3 illustrates a representation of the format of a packet
`header structure provided pursuant to an embodiment of the
`present invention of a packet of data.
`FIG. 4 illustrates a representation of a routing table
`positioned at each Bluetooth device of the scatternets shown
`in FIGS. 1 and 2 pursuant to an embodiment of the present
`invention.
`
`FIG. 5 illustrates a representation of another routing table,
`also provided to each Bluetooth device of the scatternets
`shown in FIGS. 1 and 2.
`
`FIG. 6 illustrates a representation of an address mapping
`table also provided to each Bluetooth device of the Blue-
`tooth scatternets shown in FIGS. 1 and 2 pursuant to an
`embodiment of the present invention.
`FIG. 7 illustrates a communication path formed in a
`Bluetooth scatternet and pursuant to which an embodiment
`of the present invention is operable.
`FIG. 8 illustrates a communication path formed in a
`Bluetooth scatternet, here further coupled to a fixed packet
`data network, and pursuant to which an embodiment of the
`present invention is operable.
`FIG. 9 illustrates a representation of an agent routing
`table, also utilized pursuant to an embodiment of the present
`invention.
`
`DETAILED DESCRIPTION OF THE
`PREFERRED EMBODIMENT
`
`Referring first to FIG. 1, a representative portion of an
`exemplary Bluetooth scatternet, shown generally at 10,
`provides for packet communications between Bluetooth
`devices operable therein. While the following description of
`the present invention shall be described with respect to a
`Bluetooth system, such a system is representative of an ad
`hoc, wireless communication network.
`In other
`implementations, various embodiments of the present inven-
`tion are operable therein. And, operation of various embodi-
`ments of the present invention can similarly be described
`with respect to such other ad hoc, wireless communication
`networks.
`The Bluetooth scatternet 10 shown in FIG. 1 includes two
`
`piconets, a first piconet 12 and a second piconet 14. Each
`piconet of the scatternet is defined by a master Bluetooth
`device and up to seven slave Bluetooth devices. Here, the
`first piconet 12 is defined by a master Bluetooth device 16
`and four slave Bluetooth devices 18, here referenced by
`18-1, 18-2, 18-3, and 18-4. And, the second piconet 14 is
`defined by a master Bluetooth device 22 and two slave
`devices 18, here referenced by 18-4 and 18-5.
`FIG. 2 also illustrates a representative portion of the
`Bluetooth scatternet 10. Again,
`the portion illustrated
`includes the first piconet 12 and the second piconet 14
`wherein the first piconet is defined by a master device 16 and
`four slave devices 18-1, 18-2, 18-3, and 18-4. Here, though,
`the second piconet 14 is defined by a master device which
`is a slave device to the master device 16 of the first piconet.
`The device forming both a slave and a master is referenced
`by 18-4/22.
`The devices which form the Bluetooth scatternet are
`mobile and form, on an ad hoc basis, the network of the
`Bluetooth scatternet. Through movement of the devices
`which form the scatternet,
`the various piconets of the
`scatternet are redefinable, as appropriate, and the Bluetooth
`devices of the scatternet are variously slave devices and
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`11
`
`11
`
`

`

`US 6,775,258 B1
`
`5
`master devices, sometimes, and as indicated by the device
`18-4/22, shown in FIG. 2, form both a slave and a master
`device in separate piconets. Because of the ad hoc nature of
`the Bluetooth scatternet, routing of packet data between a
`sending station and a receiving station, of which any of the
`Bluetooth devices of the scatternet can be formed, conven-
`tional routing of packet-formatted data are not readily adapt-
`able for use in an ad hoc network. The routing protocol, and
`associated data structures utilized pursuant to an embodi-
`ment of the present invention overcome the limitations of
`the existing art by which packet data is conventionally
`communicated. More particularly, in an embodiment of the
`present
`invention, each of the Bluetooth devices of the
`scatternet 10 are provided with additional data structures
`which store data utilized to route a packet of data from
`device-to-device between a sending device and a receiving
`device. The Bluetooth devices shall herein also be referred
`
`to as nodes in which a sending device forms a data source
`node and a receiving device forms a data destination node.
`One or more other devices might be positioned between the
`data source and data destination nodes and such devices
`
`shall herein, at times, be referred to as intermediary nodes.
`Pursuant to an embodiment of the present invention, each
`Bluetooth device includes a storage element 24 at which
`tables 26, 28, and 32 are defined. FIG. 2 illustrates the
`storage element 24 and the tables 26—32 of the master device
`16 and the slave device 18-1. Each of the other devices of
`
`the scatternet also include the storage element 24 and have
`the tables 26—32 defined therein.
`
`Also pursuant to an embodiment of the present invention,
`a new packet header structure is defined. The packet header
`structure is formatted to form the header portion of each
`packet of data communicated between a data source node
`and a data destination node. FIG. 3 illustrates the format of
`
`the header structure of an exemplary header, shown at 36,
`provided pursuant to an embodiment of the present inven-
`tion. The header 36 shall also herein, at times, be referred to
`as a piconet header. The header 36 is used in substitution of
`a conventional, IP header of conventional, IP-formatted
`data.
`
`The packet header 36 is here shown to include six fields,
`here fields 38, 42, 44, 46, 48, and 52, and an address 54. The
`fields 38—52 together are of four octets (thirty-two bits), and
`the address 54 is selectably of thirty-two bits or one hundred
`twenty-eight bits, depending upon whether a transport layer/
`user assumes IPv4 or IPv6 operation.
`The field 38 is a version field which provides coexistence
`with an IPv4 or IPv6 stack. Different ones of the nodes of the
`
`scatternet may have different interfaces, and the IPv4 and
`IPv6 may be the default networking protocols thereat. The
`header 36 can be based upon IPv4 and IPv6 and such
`alternate derivatives of IPv4 and IPv6 are indicated by
`different versions at the version field 38.
`
`The field 42 forms a local ID field, here a three-bit
`AMiADDR address currently assigned to the sending node,
`either the data source node or an intermediary,
`i.e.,
`forwarding, node in a piconet. If the sender is the master
`device of the piconet, in the exemplary implementation, the
`zero-identifier is utilized, ‘000’.
`The field 44 forms a single-bit broadcast flag. If the
`broadcast flag is set,
`the packet to which the header is
`associated forms a broadcast packet to be broadcast by every
`forwarding master.
`The field 46 forms a next-header field which corresponds
`to the next-header field specified in IPv6. When the header
`36 replaces an IPv4 header, instead, the next-header field 46
`takes on the functionality of the protocol field of IPv4.
`
`6
`The field 48 forms a single-bit reply flag. When a packet
`of data is communicated from a data source node to a data
`
`destination node, the flag is set to be of a zero value, and
`when the packet is communicated from a destination node
`back to the source node, e.g., a reply to the original packet,
`the reply flag is set to a one value. As shall be noted below,
`the value of the reply flag indicates to which side of the table
`26 should be checked during operation of communication of
`a packet of data pursuant to an embodiment of the present
`invention.
`
`The field forms a sequence number field. The sequence
`number field identifies each packet uniquely in a piconet,
`together with the local ID field 42.
`The address 54 is of values to identify the IP destination
`address of a first packet between two end points. The length
`of the address field 54 is dependent upon which of the IPv4
`or IPv6 protocols is assumed by the transport layer.
`Comparison of the header 36 with a conventional IP
`header (not shown) indicates that a link field, conventionally
`contained in a conventional IP header, does not form a
`portion of the header 36. Information about the link field is
`taken from an underlying layer, e.g., a L2CAP layer.
`FIG. 4 illustrates the table 26 which forms a portion of the
`storage element 24 of each of the Bluetooth devices of the
`Bluetooth scatternet 10 shown in FIG. 1 and 2. The table 26
`
`forms a PicoIP routing table. The table 26 defines a mapping
`table operable to map incoming packets to outgoing packets.
`Notification that incoming and outgoing is defined for the
`uplink, wherein the direction of the uplink is defined by a
`value of the reply-bit field 48 of the header 36. If the value
`of the reply-bit is zero,
`the packet is reverted as going
`uplink, i.e., from a source node to a destination node. And,
`if the reply-bit is of a value of one, the packet is regarding
`as going downlink. The Figure illustrates the table 26 to
`include an incoming ledger 58 and an outgoing ledger 62.
`The incoming ledger 58 includes values of the local ID, here
`indicated at 64, and a sequence number, here indicated at 66.
`Values for the elements 64 and 66 are obtained from the
`
`fields 42 and 52 of the packet header 36. The outgoing ledger
`62 is also shown to be formed of a local ID value, here
`indicated at 68, and a new sequence number, here indicated
`at 72.
`
`FIG. 5 illustrates the table 28 which also forms a portion
`of the storage element 24 of each of the Bluetooth devices
`forming the scatternet 10 shown in FIGS. 1 and 2. The table
`28 here forms an IP routing table for mapping IP addresses
`to next-hop address of a subsequent node in a communica-
`tion path formed between a data source node and data
`destination node. As shown in the Figure,
`the table 28
`includes an IP address ledger 74 and a next-hop ledger 76.
`IP addresses are stored in the ledger 74 and next-hop
`addresses, identified by local IDs, are stored in the next-hop
`ledger 76. The table 28 also includes a master flag value (M)
`formed in the column ledger 78. The value of the master flag
`indicates the difference between an all-zero broadcast
`address and the local ID to indicate a master.
`
`FIG. 6 illustrates the table 32 which forms a portion of the
`storage element 24 of each of the Bluetooth devices of the
`scatternet 10 shown in FIGS. 1 and 2. The table 32 maps a
`currently-allocated value of AMiADDRs to the same
`devices’ BDiADDRs. When the Bluetooth device forms a
`slave device rather than a master device,
`the table 32
`contains only the address of the master, the BDiADDR
`value, or possibly, multiple masters’ addresses. As all Blue-
`tooth devices are operable as a master device or a slave
`device depending upon the function of the device in a
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`12
`
`12
`
`

`

`US 6,775,258 B1
`
`7
`piconet, the tables 26, 28, and 32 are common to each of the
`Bluetooth devices irrespective of the operation of the respec-
`tive device as a master device or a slave device.
`
`In operation, when a Bluetooth device is to initiate a
`communication session, the Bluetooth device generates and
`sends a PicoIP header 36 to which a PicoIP route setup
`packet is appended to form the body of the packet of data.
`The packet is sent to the destination, i.e., the data destination
`node. When the packet is received at the destination node,
`the destination node responds with a packet formed of a
`PicoIP header 36 without a body portion. The header of the
`reply packet contains values in the fields thereof correspond-
`ing to the header 36 initially generated by the data source
`node but with a different setting of the reply bit in the reply
`field 48. The sending of the route setup packet, and the return
`of the reply responsive thereto, causes the tables of all
`intermediary nodes to have data entered therein. Subsequent
`packets of data pursuant to the communication session shall
`contain the same header, followed by a transport layered
`data that is to be sent by the data source node. A time out is
`further associated with the route setup, and, when expired,
`a new route setup packet is sent out. The procedure is
`repeated for a selected number of times.
`FIG. 7 again illustrates another representative portion of
`a Bluetooth scatternet 10. Here, again, the illustrated portion
`of the scatternet includes a first piconet 12 and a second
`piconet 14. Here, the first piconet 12 is defined by a master
`device and two slaves. The slaves are designated by 18-1 and
`18-2. The second piconet is defined by a master 22 and
`includes four slaves. One of the slaves of the master 22 in
`
`the piconet 14 is also the master of the piconet 12, and such
`Bluetooth devices designated by 16/18-3. The other slaves
`are designated by 18-4, 18-5, and 18-6. Operation of an
`embodiment of the present invention shall be described with
`respect to an implementation in which the slave device 18-1
`initiates a communication session with the slave device
`
`18-6. The communication path is represented by the arrow
`92. A packet of data originated at the slave device 18-1
`passes through two intermediary nodes, nodes 16/18-3 and
`node 22 prior to delivery to the data destination node, the
`slave 18-6. As noted above, to initiate the session, a PicoIP
`route setup packet is communicated by the device 18-1. The
`information contained in the packet, and the tables 26, 28,
`and 32 of the device 18-1 is as follows:
`
`PicoIP routing table 26 {Local ID, Sequence Number,
`Local ID, Sequence Numbernew}={0, 0; 1, SNlm+1}
`IP routing table 28 is {IP address, next hop,
`M}={destination address, 0, 1}.
`Packet header 36 {Local ID; broadcast flag, next header;
`reply fiag}={1, 0, PicoIP Route Setup Packet (xx) 0}.
`The Sequence Number is the sequence number used for
`the last route set up (indicated by SNlm), incremented by
`one. The IP address as contained in the packet header is the
`IP address of the data destination node 18-6. This address is
`
`retained in the header for each hop to the destination.
`The packet is first provided to the device 16/18-3. Such
`device records the local ID and sequence number, contained
`in the packet header, and stores the extracted information
`into the PicoIP routing table 26 of the device 16/18-3. The
`device 16/18-3 then transmits two packets, a first of the
`packets is broadcast to all the slaves of the first piconet, in
`which ‘000’ is the destination in the baseband packet. And,
`a second of the packets is forwarded to the node 22, the
`master of the second piconet. New sequence numbers are
`assigned to every packet in the same way as the manner in
`which a sequence number is assigned to the packet at the
`
`8
`source node 18-1, that is to say,
`number is incremented by one.
`The information contained in the packet header 36 and in
`the tables 26—32 of the device 16/18-3 is as follows:
`
`the last used sequence
`
`Broadcast packet header {Local ID, broadcast flag, next
`header; reply flag, Sequence Number}={0, 0, xx, 0,
`SNW}
`Packet header for packet to master B {Local ID, broadcast
`flag, next header; reply flag, Sequence Number}={3, 0,
`xx, 0, SNslaVe+1}’
`PicoIP routing table {Local ID, Sequence Number, Local
`last
`ID, Sequence Numbernew}={1, SNslaVe 1; 0, SN +1};
`{1’ SNslaVe 1; 3’ SNla5t+2}’
`IP routing table is {IP address, next hop, M}={destination
`address, 0, 0}; {dest. address, 0, 1}.
`Each slave in the piconet 12 then receives the packet, and
`each slave discards the packet unless the slave is the
`destination node, or participating on another piconet. If the
`IP routing table thereof indicates that the sender of the
`packet is the next hop to the destination, the packet will be
`discarded. For instance, slave device 18-1 discards the
`packet on the basis that the node 16/18-3 is the next hop to
`the destination node 18-6. The node 22 also receives the
`
`packet. As the node 22 is participating only in the piconet 14,
`the node 22 broadcasts the received packet to all of its
`slaves, slaves 18-3, 18-4, 18-5, and 18-6.
`The information contained in the packet header 36 in
`tables 26—32 of the node 22 is as follows:
`
`Broadcast packet header {Local Id, broadcast flag, next
`header; reply flag, Sequence Number}={0, 0, xx, 0,
`SNxszex}‘
`PicoIP routing table {Local ID, Sequence Number; Local
`slave 3’
`ID, Sequence Numbernew}={3, SN
`' 0, SNslaVe x}.
`IP routing table is {IP address, next hop, M}={destination
`address, 0, 0}; {des