Abstract:
A system and method for enabling a node, such as a mobile user terminal, in a wireless communications network to route data packets to other nodes in the network based on the information contained in the data packets. The system and method employs a node, adapted for use in a wireless communications network, which comprises a controller that is adapted to examine a content of a data packet addressed to a destination node, that can have an Internet protocol (IP) address to which the data packet is addressed. Based on the content of the data packet, the controller selects a routing path including at least one of a plurality of other nodes in the network via which the data packet is to be routed to the destination node. The controller can compare the content of the data packet to routing information stored in a memory, and select the routing path based on the comparison. Depending on the whether the content is voice, video, file transfer protocol or bulk file transfer type data, to name a few, the controller can select as the routing path a routing path via which the data packet is deliverable from the node to the destination node with low latency, low bit error rate, or in a best effort manner.

Description:
BACKGROUND OF THE INVENTION 
     1. Field of the Invention 
     The present invention relates to a system and method for enabling a node, such as a mobile user terminal, in a wireless communications network to route data packets to other nodes in the network based on the information contained in the data packets. More particularly, the present invention relates to a system and method for enabling a node in an ad-hoc packet-switched communications network to examine the contents of data packets to be transmitted by the node, and to designate a routing path including other nodes in the network via which the data packets are routed to a destination node based on the type of data contained in the data packets, to thus meet desired security parameters or packet delivery quality of service (QOS) parameters, such as low bit error rate (BER) or low latency, most suitable for the type of data contained in the data packets. 
     2. Description of the Related Art 
     In recent years, a type of mobile communications network known as an “ad-hoc” network has been developed for use by the military. In this type of network, each user terminal (hereinafter “mobile node”) is capable of operating as a base station or router for the other mobile nodes, thus eliminating the need for a fixed infrastructure of base stations. Accordingly, data packets being sent from a source mobile node to a destination mobile node are typically routed through a number of intermediate mobile nodes before reaching the destination mobile node. Details of an ad-hoc network are set forth in U.S. Pat. No. 5,943,322 to Mayor, the entire content of which is incorporated herein by reference. 
     More sophisticated ad-hoc networks are also being developed which, in addition to enabling mobile nodes to communicate with each other as in a conventional ad-hoc network, further enable the mobile nodes to access a fixed network and thus communicate with other types of user terminals, such as those on the public switched telephone network (PSTN) and on other networks such as the Internet. Details of these types of ad-hoc networks are described in U.S. patent application Ser. No. 09/897,790 entitled “Ad Hoc Peer-to-Peer Mobile Radio Access System Interfaced to the PSTN and Cellular Networks”, filed on Jun. 29, 2001, in U.S. patent application Ser. No. 09/815,157 entitled “Time Division Protocol for an Ad-Hoc, Peer-to-Peer Radio Network Having Coordinating Channel Access to Shared Parallel Data Channels with Separate Reservation Channel”, filed on Mar. 22, 2001, and in U.S. patent application Ser. No. 09/815,164 entitled “Prioritized-Routing for an Ad-Hoc, Peer-to-Peer, Mobile Radio Access System”, filed on Mar. 22, 2001, the entire content of each of said patent applications being incorporated herein by reference. 
     In these types of ad-hoc networks, the algorithms that are used to determine the path of intermediate nodes via which the data packets are routed between source and destination nodes are typically based on the shortest distance between the source and destination nodes or, assuming that the data packet transport medium is wireless, the least power required to perform the routing. However, such algorithms do not necessarily produce a predictable delivery of data packets. For example, routing of data packets can be delayed due to congestion in intermediate nodes. Also, delivery failure of data packets can occur on noisy radio links between nodes. 
     Accordingly, a need exists for a system and method for improving the manner in which data packets are delivered between nodes in an ad-hoc communications network. 
     SUMMARY OF THE INVENTION 
     An object of the present invention is to provide a system and method for improving the manner in which data packets are delivered between nodes in an ad-hoc communications network. 
     Another object of the present invention is to provide a system and method for enabling a node, such as a mobile user terminal, in a wireless communications network to route data packets to other nodes in the network based on the information contained in the data packets. 
     A further object of the present invention it to provide a system and method for achieving the most suitable routing path for the type of data contained in the data packets by enabling a node in an ad-hoc packet-switched communications network to designate a routing path based on desired security parameters or QOS parameters, such as low BER or low latency. 
     These and other objects are substantially achieved by providing a system and method employing a node, adapted for use in a wireless communications network, which comprises a controller that is adapted to examine a content of a data packet addressed to a destination node, that can have an Internet protocol (IP) address to which the data packet is addressed. Based on the content of the data packet, the controller selects a routing path including at least one of a plurality of other nodes in the network via which the data packet is to be routed to the destination node. The controller can compare the content of the data packet to routing information stored in a memory, and select the routing path based on the comparison. The routing information can include routing information pertaining to an ability of at least one of the nodes to route said data packet to another one of the nodes in the network. Specifically, when the controller determines that the content includes data requiring low latency, such as voice data, the controller selects as the routing path a routing path via which the data packet is deliverable from the node to the destination node in a period of time which is less than a predetermined duration of time. When the controller determines that the content includes data requiring low BER, such as video data, the controller selects as the routing path a routing path via which the data packet is deliverable from the node to the destination node with a bit error rate less than a predetermined bit error rate. However, when the controller determines that the content includes data suitable for best effort routing, such as certain types of bulk file transfer data, the controller selects as the routing path substantially any available routing path via which the data packet is deliverable from the node to the destination node. The node can further include a transceiver which is controllable by the controller to transmit the data packet to the at least one node in the selected routing path. Also, the nodes along the routing path can examine the contents of the data packets and change the routing as necessary to compensate for changes in conditions along the routing path, such as the unavailability of one or more nodes along the routing path or a change in the characteristics of the link between certain nodes, to maintain desired security parameters or QOS parameters for the type of data in the data packets. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     These and other objects, advantages and novel features of the invention will be more readily appreciated from the following detailed description when read in conjunction with the accompanying drawings, in which: 
     FIG. 1 is a block diagram of an example of an ad-hoc packet-switched wireless communications network employing a system and method for enabling a node, such as a mobile user terminal, in the network to route data packets to other nodes in the network based on the information contained in the data packets according to an embodiment of the present invention; 
     FIG. 2 is a block diagram illustrating an example of a user terminal employed in the network shown in FIG. 1; 
     FIG. 3 is a conceptual diagram illustrating examples of routing paths that can be selected by a node in the network shown in FIG. 1 based on the type of data in the data pickets being sent by the node to a destination node; and 
     FIG. 4 is a flowchart illustrating an example of operations performed by a node to designate a particular route shown in FIG. 3 via which data packets are routed to a destination node. 
    
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS 
     FIG. 1 is a block diagram illustrating an example of an ad-hoc packet-switched wireless communications network  100  employing an embodiment of the present invention. Specifically, the network  100  includes a plurality of mobile wireless user terminals  102 - 1  through  102 -n (referred to generally as nodes  102 ), and a fixed network  104  having a plurality of access points  106 - 1 ,  106 - 2 , . . . ,  106 -n, for providing the nodes  102  with access to the fixed network  104 . The fixed network  104  includes, for example, a core local access network (LAN), and a plurality of servers and gateway routers, to thus provide the nodes  102  with access to other networks, such as the public switched telephone network (PSTN) and the Internet. 
     As can be appreciated by one skilled in the art, the nodes  102  are capable of communicating with each other directly, or via one or more other nodes  102  operating as a router or routers for data packets being sent between nodes  102 , as described in U.S. Pat. No. 5,943,322 to Mayor and in U.S. patent application Ser. Nos. 09/897,790, 09/815,157 and 09/815,164, referenced above. Specifically, as shown in FIG. 2, each node  102  includes a transceiver  108  which is coupled to an antenna  110  and is capable of receiving and transmitting signals, such as packetized data signals, to and from the node  102 , under the control of a controller  112 . The packetized data signals can include, for example, voice, data or multimedia. 
     Each node  102  further includes a memory  114 , such as a random access memory (RAM), that is capable of storing, among other things, routing information pertaining to itself and other nodes  102  in the network  100 . The nodes  102  exchange their respective routing information, referred to as routing advertisements or routing table information, with each other via a broadcasting mechanism periodically, for example, when a new node  102  enters the network  100 , or when existing nodes  102  in the network  100  move. A node  102  will broadcast its routing table updates, and nearby nodes  102  will only receive the broadcast routing table updates if within radio frequency (RF) range of the broadcasting node  102 . For example, assuming that nodes  102 - 1 ,  102 - 2  and  102 - 7  are within the RF broadcast range of node  102 - 6 , when node  102 - 6  broadcasts its routing table information, that information is received by nodes  102 - 1 ,  102 - 2  and  102 - 7 . However, if nodes  102 - 3 ,  102 - 4  and  102 - 5  through  102 -n are out of the broadcast range, none of those nodes will receive the broadcast routing table information from node  102 - 6 . 
     Each of the nodes  102 - 1 ,  102 - 2  and  102 - 7  that receive the routing table information from node  102 - 2  can store all or a relevant portion of that routing table information in their respective memory  114 . Typically, each node  102  will perform a pruning operation to reduce the amount of routing table information that it stores in its memory  114  as can be appreciated by one skilled in the art. 
     It is also noted that when a node  102  broadcasts the routing table information to its neighboring nodes  102 , the node  102  can include routing table information pertaining to some or all of its neighboring nodes  102  that it has previously received from them and has stored in its memory  108 . Accordingly, a node  102  receiving the broadcast routing table information from another node  102  also receives some information pertaining to the routing capabilities of the neighbors of that other node  102 . For example, when node  102 - 2  broadcasts its routing table information, assuming that nodes  102 - 1  and  102 - 3  through  102 - 7  are within the RF range, those node will receive the routing table information from node  102 - 2  and update their routing tables accordingly. This routing table information can include information pertaining to, for example, nodes  102 - 1 ,  102 - 6  and  102 - 7 , which are out of RF range of some nodes, such as node  102 - 3 . Hence, node  102 - 3  can receive routing information pertaining to nodes  102 - 1 ,  102 - 6  and  102 - 7  via the routing table information broadcast by node  102 - 2 . In this event, a node  102  can store in its memory  114  routing table information pertaining to nodes  102  that are several hops away. 
     An example of the manner in which a node  102  can communicate data packets to another node  102  in accordance with an embodiment of the present invention will now be described with reference to FIGS. 1-4. Specifically, the controller  112  of a node  102  can determine the intermediate nodes  102  through which to route data packets to a destination node  102  based on the content of the data packets or, in other words, the type of data included in the data packets. The destination node  102  can be the final destination for the data packets or, in other words, the node  102  having the Internet Protocol (IP) address to which the data packets are addressed. 
     Alternatively, the destination node  102  can itself be the last node along a particular routing path for which node  102 - 1  has routing table information. In other words, node  102 - 1  may not have any routing information for nodes  102  that are more hops away than a particular destination node  102 , in which event node  102 - 1  will perform the operations discussed below to select the appropriate route to send the data packets to this destination node  102 . The destination node  102  will in turn become a source node and perform similar operations to further route the data packets along an appropriate route to another destination node, which may or may not be the final destination to which the data packets are addressed. The process is then repeated until the data packets ultimately reach their final destination node. Also, the destination node can be an IAP  106  which can route the data packets through the fixed network  104  to other nodes  102  in the network  100  or to user terminals on other networks such as the Internet or PSTN. 
     The typical types of data packet content can be generally categorized as voice, video and data, with each type of data packet content having a particular delivery criteria. While there are numerous data types and delivery options that can be described, they generally fall between the two extremes of minimum latency and maximum reliability. For purposes of this discussion, voice content, such as real time voice and streaming audio, can be categorized as “Type 1” content which requires minimum latency or, in other words, a minimum amount of delivery time between the source node and the destination node. That is, the voice content should be transmitted between nodes with as little delay as possible so that the users do not experience significant delays or gaps in the audio signals. Also, the maximum allowed latency permitted need not be fixed, but rather, can be configurable based on the desired quality of service (QOS) of the network  100 . 
     On the other hand, video content, such as real time video and video streaming, can be categorized as “Type 2” content which requires the lowest bit error rate (BER) without excessive latency. That is, the video content should be transmitted between nodes with the lowest BER (maximum reliability) so that the users do not experience a degradation in video quality. 
     Other types of data which do not necessarily require minimal latency or low BER, such as certain types of bulk file transfers, can be categorized as “Type 3” content. This type of data packet content merely requires a “best effort” delivery between nodes. 
     FIG. 3 is a conceptual diagram illustrating an example of potential routing paths that node  102 - 1  can consider using to route data packets to node  102 - 5 . According to an embodiment of the present invention, the node  102 - 1  which is sending the data packets determines the route of intermediate nodes by which the data packets are to be sent to a destination node  102 - 5  based on the routing information that it has received and stored in its memory  114 . The routing information collected and stored by node  1  should include the number of nodes that make up the potential route, the link level interference or noise between each node, and the congestion level of each intermediate node. The noise level will typically be the primary determination of the likelihood of Bit Error Rate (BER) due to interference, although congested nodes may also impact data errors if they are so overloaded that they fail to deliver the data packets. 
     The number of hops required between the source node  102 - 1  and destination node  102 - 5  will be one factor that the controller  112  of node  102 - 1  can use in determining latency or delay. That is, each additional hop will increase the delay by at least the processing delay necessary for a node  102  to relay the data packet to another node  102 . The congestion level of a node  102  will also increase this delay, and thus, is another factor that the controller  112  of node  102 - 1  will take into account in determining latency of a particular route. 
     As discussed above, each node  102  can provide this information to its neighboring nodes  102  via broadcast routing table information updates, or in any other suitable manner. Accordingly, node  102 - 1  can receive and store this information in its memory  114 , and use this information in determining a suitable routing path for data packets based on their content. Tables 1 through 3 below illustrate examples of the routing information received and stored by node  102 - 1  pertaining to the ability of the nodes  102 - 1  through  102 - 7  to route data packets for three different potential routing paths. 
     
       
         
               
             
               
               
             
           
               
                 TABLE 1 
               
             
             
               
                   
               
               
                 Routing Path From Node 102-1 to Node 102-5 
               
               
                 Using Intermediate Nodes 102-6 and 102-7 
               
             
          
           
               
                 LINK 
                 CHARACTERISTICS 
               
               
                   
               
               
                 Node 102-1 to Node 102-6 
                 low BER, low latency 
               
               
                 Node 102-6 to Node 102-7 
                 low BER, Node 102-7 congested (high 
               
               
                   
                 latency) 
               
               
                 Node 102-7 to Node 102-5 
                 low BER 
               
               
                   
               
             
          
         
       
     
     
       
         
               
             
               
               
               
             
           
               
                 TABLE 2 
               
             
             
               
                   
               
               
                 Routing Path From Node 102-1 to Node 102-5 
               
               
                 Using Intermediate Nodes 102-2 and 102-3 
               
             
          
           
               
                   
                 LINK 
                 CHARACTERISTICS 
               
               
                   
                   
               
               
                   
                 Node 102-1 to Node 102-2 
                 low latency, high BER 
               
               
                   
                 Node 102-2 to Node 102-3 
                 low latency, low BER 
               
               
                   
                 Node 102-3 to Node 102-5 
                 low latency, low BER 
               
               
                   
                   
               
             
          
         
       
     
     
       
         
               
             
               
               
               
             
           
               
                 TABLE 3 
               
             
             
               
                   
               
               
                 Routing Path From Node 102-1 to Node 102-5 
               
               
                 Using Intermediate Nodes 102-4 and 102-3 
               
             
          
           
               
                   
                 LINK 
                 CHARACTERISTICS 
               
               
                   
                   
               
               
                   
                 Node 102-1 to Node 102-4 
                 low BER, medium latency 
               
               
                   
                 Node 102-4 to Node 102-3 
                 medium latency, low BER 
               
               
                   
                 Node 102-3 to Node 102-5 
                 low latency, low BER 
               
               
                   
                   
               
             
          
         
       
     
     The controller  112  of node  102 - 1  can therefore use the above routing table information to determine which route to use to send a data packet to node  102 - 5  based on the content of the data packet. For example, as shown in the flowchart of FIG. 4, when the node  102 - 1  either generates a data packet or receives a data packet for further routing in step  1000 , the controller  112  of node  102 - 1  examines the content of the data packet in step  1010 . Beginning at step  1020 , the controller  112  of node  102 - 1  determines and specifies a service delivery parameter for the data packet. Specifically, in step  1020 , the controller  112  determines whether the data packet includes data requiring low latency. As discussed above, voice content (Type 1 content) requires the use of a routing path that has very low latency or delay. Therefore, if the node  102 - 1  is sending a data packet including voice content to node  102 - 5 , the routing algorithm performed by controller  112  should avoid using nodes that are congested, such as node  102 - 7 . 
     Accordingly, in step  1030 , the controller  112  of node  102 - 1  can send a data packet including Type 1 content to node  102 - 5  using the route consisting of nodes  102 - 1 ,  102 - 2 ,  102 - 3  and  102 - 5  (Table 2), which delivers the data packet with the least latency of all the three potential routes. Specifically, the controller  112  of node  102 - 1  will attach routing addresses to the data packet in the form of a header or in any other suitable manner, and control the transceiver  108  of node  102 - 1  to transmit the data packet to the next neighboring node (node  102 - 2 ) in the selected route. When the transceiver  108  of node  102 - 2  receives the data packet, the controller  112  of node  102 - 2  will control its transceiver  108  to transmit the data packet to the next node in the route (node  102 - 3 ). Likewise, when then the transceiver  108  of node  102 - 3  receives the data packet, the controller  112  of node  102 - 3  will control its transceiver  108  to transmit the data packet to the destination node  102 - 5 . 
     On the other hand, if the controller  112  of node  102 - 1  determines in step  1020  that the content is not voice content, the processing proceeds to step  1040  where the controller  112  determines if the content is content requiring low BER. As discussed above, video content (Type 2 content) requires low BER. Therefore, if the node  102 - 1  is sending a data packet including video content to node  102 - 5 , the routing algorithm performed by controller  112  should avoid using links between nodes that experience high BER, such as the links between nodes  102 - 1  and  102 - 2 . Accordingly, in step  1050 , the controller  112  can control node  102 - 1  to send a data packet including Type 2 content to node  102 - 5  using the route consisting of nodes  102 - 1 ,  102 - 6 ,  102 - 7  and  102 - 5  (Table 1), which delivers the data packet with low BER. 
     In this event, the controller  112  of node  102 - 1  will attach routing addresses to the data packet in the form of a header or in any other suitable manner, and control the transceiver  108  of node  102 - 1  to transmit the data packet to the next neighboring node (node  102 - 6 ) in the selected route. When the transceiver  108  of node  102 - 6  receives the data packet, the controller  112  of node  102 - 6  will control its transceiver  108  to transmit the data packet to the next node in the route (node  102 - 7 ). Likewise, when then the transceiver  108  of node  102 - 7  receives the data packet, the controller  112  of node  102 - 7  will control its transceiver  108  to transmit the data packet to the destination node  102 - 5 . 
     However, if the controller  112  determines in step  1040  that the content of the data packet is not video data, then the processing proceeds to step  1060  in which the controller  112  can determine whether that the data packet includes data which can tolerate best effort delivery, such as web page data (Type 3 content). The controller  112  can control node  102 - 1  in step  1070  to send a data packet including Type 3 content to node  102 - 5  using the route consisting of nodes  102 - 1 ,  102 - 4 ,  102 - 3  and  102 - 5  which, in this example, delivers the data packet with low BER and low to medium latency. 
     In this event, the controller  112  of node  102 - 1  will attach routing addresses to the data packet in the form of a header or in any other suitable manner, and control the transceiver  108  of node  102 - 1  to transmit the data packet to the next neighboring node (node  102 - 4 ) in the selected route. When the transceiver  108  of node  102 - 4  receives the data packet, the controller  112  of node  102 - 4  will control its transceiver  108  to transmit the data packet to the next node in the route (node  102 - 3 ). Likewise, when then the transceiver  108  of node  102 - 3  receives the data packet, the controller  112  of node  102 - 3  will control its transceiver  108  to transmit the data packet to the destination node  102 - 5 . 
     It is noted that the above decision steps  1020 ,  1040  and  1060  and their associated routing path selection steps  1030 ,  1050  and  1070 , respectively, can be performed by the controller  112  in any desired order. For example, the controller  102  of node  102 - 1  can first determine whether the data packet content is video data or bulk transfer type data, and perform the necessary transmission or further decision making steps accordingly. In addition, as discussed above, the destination node  102 - 5  can be the final destination to which the data packet is addressed, or can be an IAP  106  or intermediate node along a larger routing path. If node  102 - 5  is an intermediate node in a larger routing path, node  102 - 5  then becomes the source node for the further routing, and performs the processes described above to route the data packet to another destination node, which may or may not be the final destination node having the IP address to which the data packet is addressed. 
     It is further noted that other types of content can require different delivery criteria or QOS parameters. For example, file transfer protocol (FTP) can tolerate high latency but preferably no packet loss, Web browsing can tolerate reasonable latency and low packet loss, email can tolerate high latency and low packet loss, and streaming audio and video can tolerate reasonable latency but need low packet loss. Furthermore, for security purposes, it may be necessary to avoid sending certain types of data via certain routing paths including nodes that are not deemed to satisfy desired security requirements. For example, it may be necessary to route certain types of data packets via closed groups of nodes. Accordingly, the routing algorithms performed by controller  112  can select the appropriate data packet delivery routes to meet any of these types of security or QOS parameters. 
     In addition, consistent with the operations and functionality of an ad-hoc network as discussed above, each node  102  along a routing path can examine the contents of the data packets and change their routing as necessary to compensate for changes in conditions along the routing path, such as the unavailability of one or more nodes along the routing path or a change in the characteristics of the link between certain nodes, to maintain desired security parameters or QOS parameters for the type of data in the data packets. This is necessary because the node establishing the routing path (e.g., node  102 - 1  as discussed above) may do this without knowing all the details of the underlying network or, at best, based on only an instantaneous view of the network. As the packet transitions through the network  100 , the network characteristics may change due to terminal mobility, radio interference, congestion and other factors. Thus the desired route and/or delivery parameters may not be achievable. Accordingly, if the intermediate nodes  102  along the delivery path can examine the packet contents, they can use their more accurate and up to date information about the network  100  to decide if the current route is appropriate or if a better, or at least acceptable, alternative can be found. 
     For example, assume that node  102 - 1  has designated the delivery path shown in Table 1 above, which uses nodes  102 - 6  and  102 - 7  as intermediate nodes to route a data packet to destination node  102 - 5 . When the data packets have been received by node  102 - 6 , the controller  112  of node  102 - 6  can examine the contents of the data packets and determine whether the link between node  102 - 6  and  102 - 7  still meets the desired criteria to achieve the security or QOS parameters designated by the controller  112  of node  102 - 1 . If so, then node  102 - 6  can send the data packets to node  102 - 7 . 
     However, if node  102 - 7  is no longer available, or if the conditions of the link between nodes  102 - 6  and  102 - 7  have changed so that the desired security or QOS parameters cannot be maintained, the controller  112  of node  102 - 6  can determine based on the content of the data packets and, for example, routing table information stored in the memory  114  of node  102 - 6 , whether the data packets should be sent to another node, such as node  102 - 2 , in order to meet the desired parameters. Also, even if node  102 - 7  is available, the controller  112  of node  102 - 6  can determine, based on the contents of the data packets and the routing table parameters, whether another route would be more suitable to achieve the desired security or QOS parameters. 
     If the controller  112  of node  102 - 6  determines that node  102 - 2  is more suitable for any of the reasons discussed above, then the controller  112  of node  102 - 6  can control the transceiver  108  of node  102 - 6  to send the data packets to node  102 - 2 . Upon receiving the data packets, the controller  112  of node  102 - 2  can perform a similar examination of the contents of the data packets in view of the routing table information stored in memory  114  of node  102 - 2  to determine the best manner to route the data packets to destination node  102 - 5  in order to maintain the desired security or QOS parameters designated by node  102 - 1 . These processes can be performed by all the nodes  102  that receive the data packets to assure that the delivery parameters are maintained. 
     Although only a few exemplary embodiments of the present invention have been described in detail above, those skilled in the art will readily appreciate that many modifications are possible in the exemplary embodiments without materially departing from the novel teachings and advantages of this invention. Accordingly, all such modifications are intended to be included within the scope of this invention as defined in the following claims.