Abstract:
In one aspect, a method includes receiving, at a first node in a network, a resource reservation request from a second node in the network, determining, at the first node, if there is another node in the network that can be used to reach a destination and meet the resource reservation request and notifying the second node a result of the determining.

Description:
BACKGROUND 
     A communication network includes multiple routers. The routers are located at subnet boundaries that are located between a sender and a receiver. The routers transfer data packets originating from the sender to the intended receiver. Often a communication network has multiple possible paths between the sender and the receiver, but only one single path is chosen to send data between the sender and the receiver. 
     SUMMARY 
     In one aspect, a method includes receiving, at a first node in a network, a resource reservation request from a second node in the network, determining, at the first node, if there is another node in the network that can be used to reach a destination and meet the resource reservation request and notifying the second node a result of the determining. 
     In another aspect, a first node in a network includes electronic hardware circuitry configured to receive a resource reservation request from a second node in the network, determine if there is another node in the network that can be used to reach a destination and meet the resource reservation request and notify the second node a result of the determining. 
     In a further aspect, an article includes a non-transitory computer-readable medium that stores computer-executable instructions. The instructions cause a machine to receive, at a first node in a network, a resource reservation request from a second node in the network, determine, at the first node, if there is another node in the network that can be used to reach a destination and meet the resource reservation request and notify the second node a result of the determining. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIG. 1A  is a block diagram of an example of a network. 
         FIG. 1B  is a block diagram of an example of a node in the network of  FIG. 1A . 
         FIG. 2  is a flowchart of an example of a process to perform resource allocation. 
         FIG. 3  is a flowchart of an example of a process to manage resource allocation after a detected link failure or detected degradation. 
         FIG. 4  is a flowchart of an example of a process to perform a re-evaluation of a resource allocation. 
         FIG. 5  is a block diagram of an example of a resource allocator of the node in  FIG. 1B  on which any or part of the processes of  FIGS. 2 to 4  may be implemented. 
     
    
    
     DETAILED DESCRIPTION 
     Described herein are techniques to allocate resources at a node in a network to accomplish an objective (e.g., a mission). For example, the bandwidth of a node in the network is allocated to accomplish an objective. Also described herein are techniques to modify a resource allocation due to a detected link failure or link degradation and to perform a resource re-evaluation. Using these techniques, if the nodes in the network are aerial platforms that are deployed, any changes due to link failure or link degradation between the nodes may be adjusted in real-time while the nodes are still deployed without a need to recall these nodes thereby saving time and money. 
     Referring to  FIG. 1A , a network  100  used for communications includes nodes  102   a - 102   e . The node  102   a  is coupled to the node  102   b  by a link  104   a , is coupled to the node  102   c  by a link  104   b  and is coupled to the node  102   d  by the link  104   c . The node  102   b  is coupled to the node  102   c  by a link  104   d  and is coupled to the node  102   e  by a link  104   f . The node  102   c  is coupled to the node  102   d  by a link  104   e  and is coupled to the node  102   e  by a link  104   g . The node  102   d  is coupled to the node  102   e  by a link  104   h . Each of the links  104   a - 104   h  may be one of wired links, fiber optic links, wireless links or a combination of the three (or any other media that can carry IP or other digitally encoded data traffic). In some examples, the nodes  102   a - 102   e  form a multi-layered hierarchical mobile ad-hoc network (MANET). Although MANET can potentially offer multiple routes for each given source and destination pair, each network node selects an “appropriate” communications path which can satisfy the mission requirements, such as jitter, latency, and minimum bandwidth. As can be observed in  FIG. 1A , there are a number of paths between the nodes  102   a  and  102   e  that data packets can travel. 
     Referring to  FIG. 1B , a node  102  is an example of one or more of the nodes  102   a - 102   e . The node  102  includes a router  110  and a resource allocator  112 . In some examples, the router  110  provides link updates and resource requests. In some examples, the router  110  performs packet forwarding according to the packet&#39;s destination address and enforces the Quality of Service (QoS) policies at the egress interfaces. In some examples, the resource allocator  112  manages resource (e.g., bandwidth) allocation for the router  110 , monitors quality of links for the router and if needed performs resource redistribution. In one example, a node  102  is an aerial platform (e.g., an unmanned aerial vehicle). In one particular example, one or more nodes  102   a - 102   e  in the network  100  is (are) unmanned aerial vehicles. 
     Referring to  FIG. 2 , a process  200  is an example of a process to perform resource allocation and in particular, performing bandwidth allocation. For example, process  200  is performed by nodes along a communications path (sometimes referred to herein as a route). In one particular example, node  102   a  is a source node and node  102   e  is the destination node. Node  102   c  is chosen by the node  102   a  using the process  200  so that the communications path is from node  102   a  to node  102   c  to node  102   e . With respect to node  102   c , the node  102   a  would be its predecessor node and with respect to node  102   a , the node  102   c  would be its successor node. 
     After receiving a resource reservation request, process  200  determines if a destination node is directly connected ( 202 ) and if the destination node is directly connected, process  200  sends a success notification to the predecessor node ( 204 ), for example, including the latest offered rate, to the sender of the resource reservation request. The offered rate is defined to be the bandwidth which all the eligible nodes in the path will reserve for a mission. Initially, the offered rate is set to be the desired bandwidth of the mission. The offered rate can be modified during the route selection process. A node is an eligible node if it can reach the destination node directly or indirectly and satisfy the resource constraints (e.g., jitter, latency, security) of the mission and bandwidth requirements of the mission. 
     If the destination node is not directly connected, process  200  stores the resource constraints of the mission ( 206 ), in a database (e.g., data  518  in  FIG. 5 ), for example. For example, the resource constraints may include latency, minimum bandwidth requirement, security, jitter, and other constraints as defined by the mission requirements. In one example, the resource constraints are included in the reservation request. 
     Process  200  generates a list of eligible nodes ( 208 ). For example, process  200  generates a list of neighbors (e.g., eligible nodes that are one hop away) to forward the resource reservation request that meet the resource constraints. For example, if process  200  is being executed at the node  102   a , the eligible nodes may include nodes  102   b - 102   d.    
     Process  200  determines if the list is empty ( 210 ) and if the list is empty, process  200  deletes the constraints and releases reserved bandwidth if it exists ( 212 ). Process  200  rejects the resource reservation request ( 214 ) and sends a notification to the predecessor node ( 216 ) (i.e., the predecessor node is the node that sent the resource reservation request). 
     If the list is not empty, process  200  selects the node with the largest reserved bandwidth ( 220 ). Process  200  determines if the reserved bandwidth is less than the minimum required bandwidth ( 222 ). If the reserved bandwidth is less than the minimum required bandwidth, process  200  performs processing blocks  212 ,  214  and  216 . 
     If the reserved bandwidth is not less than the minimum required bandwidth process  200 , process  200  sets the reserved bandwidth to be the minimum of reserved bandwidth and (current) offered rate ( 224 ) and sets the offered rate of the request equal to the reserved bandwidth ( 226 ). Process  200  forwards a resource reservation request to the selected node ( 228 ) and waits for notification ( 230 ). 
     Process  200  determines if the resource reservation request is successful (e.g., a notification is received from the selected node that the bandwidth is reserved) ( 232 ). If not successful, process  200  restores the originally offered rate ( 234 ) and removes the selected node from the list ( 236 ) and repeats processing block  208 . 
     If successful, process  200  determines if the offered rate is less than the reserved bandwidth ( 238 ). If the offered rate is less than the reserved bandwidth, process  200  sets the reserved bandwidth equal to the offered rate ( 240 ) and performs processing block  216 . If the offered rate is not changed, process  200  performs processing block  216 . 
     Once process  200  is completed successfully by each node in the selected path, the nodes in the selected path guarantee a bandwidth to this mission regardless of its priority level. Bandwidth reallocation occurs when the link situation changes, such as link failure or quality degradation (e.g., process  300  ( FIG. 3 )). Process  200  both helps the communication networks serve the missions better, i.e., select a path to match the resource requirements the best, and improves the network utilization (e.g., reduce the packet drops due to the insufficient bandwidth). 
     Although beneficial to the mission, process  200  is not mandatory. Missions are allowed to deliver traffic without performing process  200  in advance. A node can still forward the traffic received as long as there is unused bandwidth available. However, the priority is given to the missions that have completed process  200 . Missions that do not complete process  200  compete for the remaining unclaimed bandwidth. Without knowing the mission bandwidth requirement, a node performs the route selection based on the destination address if standard routing protocols, such as Open Shortest Path First (OSPF), Enhanced Interior Gateway Routing Protocol (EIGRP), Border Gateway Protocol (BGP), for example, are used. Combining a traditional routing process with the process  200  enables a mission-requirements-based decision as to whether or not the resulting path may or may not meet the mission&#39;s bandwidth requirement. 
     Referring to  FIG. 3 , a process  300  is an example of a process to manage resource allocation after a detected link failure or detected degradation. For example, the resource allocator  112  in  FIG. 1B  monitors the link conditions and senses that the link quality no longer supports the existing mission requirements or that there is a link failure. After a link failure or link degradation process  300  is performed. 
     Process  300  performs a resource re-evaluation ( 302 ) and determines if a new alternate route be chosen ( 304 ). For example, a process  400  ( FIG. 4 ) is performed to re-evaluate whether there is adequate bandwidth at the node. 
     If a new route should be chosen, process  300  determines if alternate routes are available ( 306 ). For each alternative link being considered, both the data on the failed or saturated link and the data on the alternative link are assessed. The total capability should at least satisfy the sum of the minimum bandwidth requirement of all traffic flows which go through this link. 
     If alternate routes are not available, process  300  cancels the bandwidth reservation ( 308 ) and sends a notification to its predecessor nodes and its successor nodes ( 310 ). If alternate routes are available, process  300  performs a bandwidth reallocation ( 316 ) and sends a notification to its predecessor nodes and its successor nodes ( 310 ). 
     For example, after the reevaluation, if a node determines that it can no longer satisfy the minimum bandwidth requirement of a mission, then it will cancel its bandwidth reservation, i.e., release the bandwidth reserved for this mission, remove the corresponding mission requirements information from its local database, and send a cancellation notification to its predecessor and successor nodes in the path. 
     Upon receiving a reservation cancellation from its predecessor node in the path, a node will release the bandwidth reserved for this mission, remove the corresponding mission requirements information from its local database, and send a cancellation notification to its successor nodes in the path. 
     Upon receiving a reservation cancellation from its successor node in the path, a node will search alternative eligible neighbors based on link quality, present mission constraints, and bandwidth requirements. If at least one eligible neighboring node can satisfy the mission requirements, this mission will continue. The node selects the link with the highest offered bandwidth and sends a reservation request to the selected neighbor on behalf of the source to establish a new path. If none of the eligible neighbors can satisfy the mission requirements, then this mission will be cancelled. 
     If a new route need not be chosen, process  300  determines if bandwidth should be reduced ( 312 ) and, if bandwidth should be reduced, process  300  performs bandwidth reallocation ( 316 ) and sends a notification to its predecessor nodes and its successor nodes ( 310 ). 
     To avoid the packet delivery interruption due to the path change and save the path reestablishment time, the preferred choice is to reduce the reserved bandwidth in order to keep the traffic flow on the same link. For each mission, the revised bandwidth reservation should still meet the mission&#39;s minimum bandwidth requirement. The actual value is dependent on the current link capacity, sum of bandwidth requirements from all the missions which have completed the resource reservation, and the mission&#39;s priority. Note that if multiple missions are involved in the re-evaluation process, then the missions with the strict priority will be served first and then others after that, according to their priority setting. If no sufficient bandwidth is available for a mission, then the mission data will be rerouted. Under this situation, the minimum bandwidth requirement specified in a mission profile is allocated to a mission initially. If there is remaining bandwidth available after the allocation, then the mission data will be distributed to other missions according to their weight and need. 
     Referring to  FIG. 4 , a process  400  is an example of a process to perform a re-evaluation of resource allocation. For example, after being notified of a link failure or degradation, the process  400  is performed to re-evaluate the resource allocation. 
     Process  400  determines if there is sufficient bandwidth to support the existing missions ( 402 ) and if there is sufficient bandwidth process  400  continues the mission without any change ( 404 ). If process  400  determines there is not sufficient bandwidth, process  400  determines if a lower bandwidth reservation will be acceptable ( 406 ). 
     If a lower bandwidth reservation is acceptable, process  400  continues mission with reduced bandwidth ( 408 ). If a lower bandwidth reservation is not acceptable, process  400  seeks alternate routes ( 410 ). 
     Referring to  FIG. 5 , an example of the resource allocator  112  is the resource allocator  500 . The resource allocator  500  includes a processor  502 , a volatile memory  504 , a non-volatile memory  506  (e.g., hard disk) and the user interface (UI)  508  (e.g., a graphical user interface, a mouse, a keyboard, a display, touch screen and so forth). The non-volatile memory  506  stores computer instructions  512 , an operating system  516  and data  518 . In one example, the computer instructions  512  are executed by the processor  502  out of volatile memory  504  to perform all or part of the processes described herein (e.g., processes  200 ,  300  and  400 ). 
     The processes described herein (e.g., processes  200 ,  300  and  400 ) are not limited to use with the hardware and software of  FIG. 5 ; they may find applicability in any computing or processing environment and with any type of machine or set of machines that is capable of running a computer program. The processes described herein may be implemented in hardware, software, or a combination of the two. The processes described herein may be implemented in computer programs executed on programmable computers/machines that each includes a processor, a non-transitory machine-readable medium or other article of manufacture that is readable by the processor (including volatile and non-volatile memory and/or storage elements), at least one input device, and one or more output devices. Program code may be applied to data entered using an input device to perform any of the processes described herein and to generate output information. 
     The system may be implemented, at least in part, via a computer program product, (e.g., in a non-transitory machine-readable storage medium such as, for example, a non-transitory computer-readable medium), for execution by, or to control the operation of, data processing apparatus (e.g., a programmable processor, a computer, or multiple computers). Each such program may be implemented in a high level procedural or object-oriented programming language to work with the rest of the computer-based system. However, the programs may be implemented in assembly, machine language, or Hardware Description Language. The language may be a compiled or an interpreted language and it may be deployed in any form, including as a stand-alone program or as a module, component, subroutine, or other unit suitable for use in a computing environment. A computer program may be deployed to be executed on one computer or on multiple computers at one site or distributed across multiple sites and interconnected by a communication network. A computer program may be stored on a non-transitory machine-readable medium that is readable by a general or special purpose programmable computer for configuring and operating the computer when the non-transitory machine-readable medium is read by the computer to perform the processes described herein. For example, the processes described herein may also be implemented as a non-transitory machine-readable storage medium, configured with a computer program, where upon execution, instructions in the computer program cause the computer to operate in accordance with the processes. A non-transitory machine-readable medium may include but is not limited to a hard drive, compact disc, flash memory, non-volatile memory, volatile memory, magnetic diskette and so forth but does not include a transitory signal per se. 
     The processes described herein are not limited to the specific examples described. For example, the processes  200 ,  300  and  400  are not limited to the specific processing order of  FIGS. 2 to 4  respectively. Rather, any of the processing blocks of  FIGS. 2 to 4  may be re-ordered, combined or removed, performed in parallel or in serial, as necessary, to achieve the results set forth above. 
     In some examples, multiple routing tables may be combined in to a single routing table. In these examples, value-to-route associations are incorporated (directly or indirectly) into the combined routing table thereby enabling the appropriate route selection to be made. 
     The processing blocks (for example, in the processes  200 ,  300  and  400 ) associated with implementing the system may be performed by one or more programmable processors executing one or more computer programs to perform the functions of the system. All or part of the system may be implemented as, special purpose logic circuitry (e.g., an FPGA (field-programmable gate array) and/or an ASIC (application-specific integrated circuit)). All or part of the system may be implemented using electronic hardware circuitry that include electronic devices such as, for example, at least one of a processor, a memory, programmable logic devices or logic gates. 
     Elements of different embodiments described herein may be combined to form other embodiments not specifically set forth above. Various elements, which are described in the context of a single embodiment, may also be provided separately or in any suitable subcombination. Other embodiments not specifically described herein are also within the scope of the following claims.