Systems and methods for providing resource allocation meeting communication constraints for multi-hop network data flows

Priority claim

This patent application was filed on July 15, 2009 and has been assigned to the assignee of this patent application, the disclosure of which is expressly incorporated herein by reference, "Slot Allocation at Nodes for Meeting". It claims the benefit of US Patent Application No. 61 / 225,599 entitled "Quality of Service Constraints in Multihop Ultra Wideband Networks and Resource Allocation and Scheduling with Quality of Service and Fairness Requirements in TDMA Based Multihop Wireless Networks."

The present disclosure relates generally to network communication, and more specifically to resource allocation for network communication.

Information and communications provided by various forms of networks are widespread today almost everywhere in the world. A network of nodes communicating using wireless and wired links can carry many types of data payloads, such as voice data, multimedia data, alphanumeric data, and graphic data. Used to carry data packets. Thus, nodes in such networks can include computers, personal digital assistants (PDAs), telephones, servers, routers, switches, multiplexers, modems, radios, access points, base stations, and the like. Data packet flow is established between network nodes to provide the desired network communication, and end-to-end data communication for any particular communication session utilizes multiple hops (ie, one or more). It can be routed through multiple intermediate network nodes). Any number of network nodes may be competing for network communication resources to provide such a flow at any particular point in time.

Transmissions between a pair of network nodes (eg, wireless network nodes) interfere with the communication of one or more other network nodes if they overlap in the time, frequency, and space regions. Can cause (eg, interfere with another transmission between different pairs of network nodes). Therefore, the success of such transmissions may only be guaranteed if such transmissions are separated in at least one of the aforementioned regions. Several technologies for providing resource allocation for shared access to network communication links, such as Frequency Division Multiple Access (FDMA), Time Division Multiple Access (TDMA), and Spatial Separation / Isolation, make network communication. It can be done to facilitate. For example, in a TDMA system where the frequency domain is not utilized to provide communication orthogonality, the time domain and spatial domain are investigated for various transmissions in providing resource allocation to avoid communication conflicts (eg,). TDMA operation and spatial reuse options can be investigated (to avoid interference).

Providing resource allocation (eg, time slot allocation and / or data path routing in the TDMA system example described above) to facilitate network communication is generally specified on any one network link. Determining if sufficient data capacity is available to use when communicating data on a node is not as easy. Applications for which data communication is provided (eg, streaming and / or high definition multimedia services in WiMedia-based ultra-wideband (UWB) networks, incorporated herein by reference, ECMA-368, "High. Rate Ultra Wideband PHY and MAC Standard, 2nd Edition, December 2007) can be bandwidth intensive and delay sensitive, and is therefore strict. Quality of service (QoS) service) Have requirements. Therefore, a datapath with sufficient available resources at each node on the datapath supports the QoS requirements of a data flow across multiple hops of the network to guarantee QoS across the end-to-end datapath. Is needed for.

Traditional solutions have proposed a centralized implementation of the TDMA scheduling scheme that is not suitable for distributed medium access control (MAC) protocols, such as WiMedia-based UWB network protocols. While some such traditional solutions are variants of QoS aware routing protocols, other such traditional solutions have the problem of supporting the desired flow. I've been using integer linear programming in an attempt to solve this problem.

The present disclosure identifies a system and a multi-hop network data path that has sufficient resources available at each node on the data path to facilitate the desired end-to-end communication (end-to-end data flow). Target the method. The embodiment functions to identify resource constraints to meet QoS or other communication requirements at each node of the multi-hop data path. Accordingly, embodiments of the present disclosure determine whether resource availability at each node of the end-to-end data path can meet the communication requirements of the end-to-end data flow. For example, in a TDMA system configuration, communication requirements, such as QoS requirements, can determine the minimum throughput metric that imposes a time slot (resource) constraint to be imposed on each node used in a particular multihop data path. The operation according to the embodiments of the present disclosure identifies a multi-hop data path having sufficient available time slots at each node on the data path to accommodate end-to-end data flow.

An embodiment of the present disclosure is a decentralized method for determining whether resource availability at each node of an end-to-end data path can meet the communication requirements of an end-to-end data flow. Works with. Therefore, embodiments propagate resource constraint information, such as QoS information, within the network for use in identifying suitable data paths to support the desired end-to-end data flow. Such embodiments are suitable for use with respect to distributed MAC protocols, such as WiMedia-based UWB network protocols.

A multi-hop data communication link includes one or more intermediate network nodes that utilize the corresponding uplink and downlink to complete an end-to-end data path. In some cases, resource requirements may not be met for uplinks or downlinks at each intermediate node, or at the same time for uplinks and downlinks. Such a scenario results in a data path identified as not supporting the desired end-to-end data flow according to the embodiments of the present disclosure. In other cases, resource requirements are met for uplinks and downlinks at each intermediate node, and even for both links at the same time, but any resource allocation between uplinks and downlinks at each intermediate node , May not meet the QoS requirements of the link or other communication requirements. Accordingly, embodiments of the present disclosure include resource allocation algorithms that can operate to allocate resources to achieve end-to-end data flow that meets communication requirements. The resource allocation algorithm of the embodiment is for the efficiency of available resources so that the desired conditions are met when the resource requirements are met for uplinks and downlinks at each intermediate node, and even for both links at the same time. It works to ensure proper use.

For example, all intermediate nodes in an end-to-end data path have been determined to have sufficient resource availability for the desired end-to-end data flow in a TDMA system configuration, and therefore that data path is desired. May be identified as supporting an end-to-end flow. However, communication requirements may not be met as a result of arbitrary allocation of time slots on the uplink and downlink associated with these intermediate nodes. Therefore, the time slot allocation algorithm of the embodiments of the present disclosure can function to allocate time slots to achieve an end-to-end data flow that meets the communication requirements.

The embodiments of the present disclosure are used in connection with or as part of a communication requirement-aware routing protocol, such as a QoS-aware routing protocol. Accordingly, embodiments of the present disclosure can function to determine the best available end-to-end datapath for which multiple datapaths meet resource constraints or other communication requirements.

In the above, the features and technical advantages of the present disclosure have been outlined fairly extensively so that the detailed description of the present disclosure below can be better understood. The following describes additional features and advantages of the present disclosure that form the subject of the claims. It will be appreciated by those skilled in the art that the disclosed concepts and specific embodiments can be readily utilized as the basis for modifying or designing other structures that serve the same purpose of the invention. It will also be appreciated by those skilled in the art that such equivalent structures do not deviate from the gist and scope of the present disclosure set forth in the appended claims. The novel features that are believed to be characteristic of the present disclosure are better from the following description, along with additional objectives and advantages, when considered in connection with the accompanying figures, both in terms of their configuration and manner of operation. Will be understood. However, it should be clearly understood that each figure is provided for purposes of illustration and illustration only and is not intended as a definition of the limitations of this disclosure.

For a more complete understanding of the present disclosure, we then refer to the following description, which is construed in conjunction with the accompanying drawings.

<figref num="1">The schematic which shows the network adapted for the operation by embodiment of this disclosure.</figref><figref num="2">A high level of operation according to an embodiment of the present disclosure that identifies a multi-hop network data path with sufficient available resources at each node on the data path to facilitate the desired end-to-end data flow. flow diagram.</figref><figref num="3">The figure which shows the relationship between the required bandwidth, the PHY rate, and the data flow frame and the slot duration of a TDMA system configuration.</figref><figref num="4">The figure which shows the data packet structure about the I-ACK communication technology.</figref><figref num="5">The figure which shows the data packet structure about the B-ACK communication technology.</figref><figref num="6">The flow chart which shows the resource allocation by embodiment of this disclosure.</figref><figref num="7">The figure which shows the processor-based system adapted by the embodiment of this disclosure.</figref>

To aid in understanding the concepts of the present disclosure, embodiments are described below in connection with WiMedia-based UWB network configurations, WiMedia MAC, and / or TDMA system configurations. However, it should be understood that the concepts of this disclosure are applicable to a variety of network configurations, protocols, and resource allocation techniques. For example, embodiments of the present disclosure can be provided in connection with any distributed TDMA MAC.

FIG. 1 shows a schematic diagram of a network 100 adapted for operation according to an embodiment of the present disclosure. Network 100 includes various network configurations such as personal area network (PAN), local area network (LAN), metropolitan area network (MAN), wide area network (WAN), intranet, extranet, Internet, wireless network, and wired network. Can be provided. The network 100 of the illustrated embodiment includes a network portion 101 composed of network nodes N0 to N5 in a communication state through links L1 to L5. Network nodes N0 to N5 can have the same or different node configurations, for example computers, personal digital assistants (PDAs), telephones, servers, routers, gateways, switches, multiplexers, modems, radios, access points, bases. It can be equipped with various things such as stations. Network links L1 to L5 can utilize a variety of media such as copper wire, fiber optic wire, air interfaces (eg, radio frequency, infrared light, etc.), and / or similar. Therefore, the links L1 to L5 can include a wired link, a wireless link, and a combination thereof.

Given that network node N0 is in data communication with network node N5, end-to-end data paths are provided by links L1 through L5. Therefore, the resulting end-to-end data flow is a multi-hop data flow. Network nodes N1 to N4 include intermediate network nodes in the multi-hop data flow described above.

Although specific links are shown that provide end-to-end data paths, it should be understood that other links and / or end-to-end data paths can also be provided in the networks shown. For example, various additional links (not shown) in Network 100 are used between certain network nodes, such as between network nodes N0 and N2, between N1 and N3, between N3 and N5, and so on. It can be possible. In addition, various additional network nodes (also not shown) that can be used to provide additional links (not shown) can exist within network 100. However, to simplify the description of the concepts in this disclosure, FIG. 1 shows a single end-to-end data path for network nodes N0 and N5.

Figure 2 shows the high degree of operation of identifying a multi-hop network data path with sufficient resources available at each node on the data path to facilitate the desired end-to-end data flow according to one embodiment. The level flow diagram is shown. In block 201 of the indicated embodiment, resource constraint information is propagated within the network for use in identifying suitable data paths to support the desired end-to-end data flow. For example, QoS information can be propagated to various network nodes (for example, network nodes N0 to N5) throughout the network by a QoS-aware routing protocol. The QoS information propagated to the network node can include, but is not limited to, the required application throughput, delay limit, jitter, acceptable residual packet loss rate, and the like. Propagation of such resource constraint information according to embodiments of the present disclosure determines whether resource availability at each node of the end-to-end data path can meet the communication requirements of the end-to-end data flow. To facilitate the operation of distributed methods.

In block 202 of the indicated embodiment, it is determined whether the resource availability at each node of the end-to-end data path can meet the communication requirements of the end-to-end data flow. One or more sets of network nodes, along with their corresponding links, are identified as end-to-end data flows providing an end-to-end data path between the desired source and destination for it. Can be done. Resource availability at each node in such a set of network nodes means that resource availability at each node in that particular end-to-end data path meets the desired end-to-end data flow communication requirements. To determine if this is possible, it can be analyzed with respect to resource constraint information about the desired end-to-end data flow. For example, in a TDMA system configuration, communication requirements, such as QoS requirements, can determine the minimum throughput metric that imposes a time slot (resource) constraint to be imposed on each node used in a particular multihop data path. The embodiment analyzes such information to identify resource constraints that meet QoS or other communication requirements at each node of the multi-hop data path. For example, embodiments of the present disclosure function to select a particular multi-hop data path with sufficient available time slots at each node on the data path to accommodate end-to-end data flow.

The above analysis of resource availability at each node in a set of network nodes is based on each node (or at least a network node) in each set of network nodes that provides an end-to-end data path between the source and destination. Resource availability in a plurality of sets of) is repeated according to embodiments to determine if it is possible to meet the desired end-to-end data flow communication requirements. Therefore, the operation by block 202 of the embodiments of the present disclosure can determine that a plurality of end-to-end paths meet the end-to-end data flow communication requirements.

The data flow between the source and destination at the intermediate node of the end-to-end data path utilizes the corresponding uplink and downlink. Therefore, it is possible that the desired end-to-end data flow resource requirements may not be met for uplinks or downlinks at each intermediate node, or for uplinks and downlinks at the same time. Such a scenario results in a data path that is determined by the operation in block 202 of the embodiments of the present disclosure to not support the desired end-to-end data flow. If the desired end-to-end data flow resource requirements are met for uplinks and downlinks at each intermediate node, and even for both links at the same time, the operation in block 202 of the embodiments of the present disclosure is data. Determine that the path supports the desired end-to-end data flow.

In block 203 of the indicated embodiment, an end-to-end data path capable of meeting the communication requirements of the end-to-end data flow is selected, the network nodes of the end-to-end data path, and their associated links. Resources are allocated for. At block 202, it is determined that multiple end-to-end data paths (eg, different sets of network nodes) have resource availability at each node capable of meeting the communication requirements of the end-to-end data flow. If so, the behavior at block 203 is such an end-to-end data path to select the best end-to-end data path to use in providing the desired end-to-end data flow. Can analyze possible resource allocations for. For example, possible resource allocation for end-to-end data flow minimizes the total number of resources (eg, time slots) used for end-to-end data flow (eg, QoS requirements are met). Leave the maximum number of resources (eg, time slots) on virtually every node in the end-to-end data path (to increase the likelihood that new flows will be accepted by the network). It can be analyzed to determine the combination of end-to-end data paths and resource allocation. Additional or alternative analysis, such as the available power at the network nodes of the end-to-end data path, may also be utilized when selecting a particular end-to-end data path (eg, other). To ensure route availability over a longer period of time in the absence of factors).

The embodiments of the present disclosure can function to select multiple end-to-end data paths for use with respect to the desired end-to-end data flow. For example, rather than choosing a single "best" end-to-end data path, disclosure embodiments are desired, for example to provide robust routing, such as for communication fault tolerance. You can select two or more end-to-end data paths that can meet the communication requirements of the end-to-end data flow.

Any resource allocation between the uplink and downlink at each intermediate node may not meet the QoS or other communication requirements of the link. Therefore, the operation in block 203 according to the embodiment of the present disclosure allocates resources so as to achieve an end-to-end data flow that meets the communication requirements, such as by using a resource allocation algorithm.

For example, it is determined that all intermediate nodes of the end-to-end data path have sufficient resource availability for the desired end-to-end data flow in the TDMA system configuration, and therefore the data path is desired. May be identified as supporting end-to-end data flow. However, arbitrary allocation of time slots on the uplink and downlink can result in unmet communication requirements. Therefore, the time slot allocation algorithm of the embodiments of the present disclosure can function to allocate time slots to achieve an end-to-end data flow that meets the communication requirements.

From the above, the operations in block 203 of the embodiment are available so that the desired conditions are met when the resource requirements are met for the uplink and downlink, and also for both links at the same time at each intermediate node. It can be seen that it ensures efficient use of resources. Accordingly, embodiments of the present disclosure are utilized in connection with, or as part of, communication requirements-aware routing protocols, such as QoS-aware routing protocols.

It should be understood that the above description of FIG. 2 illustrates the operation according to the embodiments of the present disclosure at a high level. Further details regarding providing the operation according to the concept of the present disclosure are given below.

In providing an operation according to an embodiment of the present invention that determines whether resource availability at each node of an end-to-end data path can meet the communication requirements of an end-to-end data flow, N. Let n be the number of nodes in the end-to-end data path from source to destination (for example, N = 6 in the end-to-end data path shown in Figure 1), and n (L) as end-to-end data. The number of links in the path (for example, in the end-to-end data path shown in Figure 1, n (L) = 5). Therefore,<maths num="1"><img id="000002" he="20" wi="159" file="JP5774672B2_D0001.tif" img-format="tif" img-content="drawing" /></maths>

L_ij, Node N_iAnd N_jAs a link between and R_appLet R be the required bandwidth (per link)_ij, Link L_ijThe physical layer (PHY) rate that can be supported with respect to p_ij, Link L_ijThe corresponding physical layer packet error rate (PER) for.

Figure 3 shows the required bandwidth (R) of a TDMA system configuration, such as that available for WiMedia UWB networks._app) And the PHY rate (R)_ij) And the data flow frame and slot duration are illustrated. In Figure 3, T_{science fiction}Is the WiMedia Superframe duration and T_dIs the total duration of the reservation and is therefore determined by the number of media access slots (MAS).

From the above,<maths num="2"><img id="000003" he="17" wi="159" file="JP5774672B2_D0001.tif" img-format="tif" img-content="drawing" /></maths>

However, η is the link L_ijMAC efficiency with respect to (ie, the percentage of payload transmission time). T_dSolving for gives:<maths num="3"><img id="000004" he="17" wi="159" file="JP5774672B2_D0001.tif" img-format="tif" img-content="drawing" /></maths>

Therefore, link L_ijThe number of MAS required for is given by the following equation.<maths num="4"><img id="000005" he="18" wi="159" file="JP5774672B2_D0001.tif" img-format="tif" img-content="drawing" /></maths>

Above, T_{science fiction}= 256T_MASIs assumed to be. Equation (4) gives a formula that indicates the number of slots required for each intermediate network node in the end-to-end data path to support that hop of the desired end-to-end data flow. I want to be understood.

Two examples are considered below to estimate the MAC efficiency η. The first example considers the MAC efficiency associated with the flow using intermediate acknowledge (I-ACK) communication technology, and the second example blocks as it can be done in a WiMedia UWB network. Consider the MAC efficiency associated with flows that use block acknowledgment (B-ACK) communication technology.

Figure 4 shows the data transaction sequence for the I-ACK acknowledgment policy. The data packet structure in Figure 4 is the first physical layer convergence protocol (PLCP) preamble, the first PLCP header, the payload frame, and the short inter-frame space (SIFS). ), A second (ACK) PLCP preamble, a second (ACK) PLCP header, and a second (ACK) SIFS. If the PLCP preamble has a duration of 9.375us, the PLCP header has a duration of 3.75us, and the SIFS has a duration of 10us (WiMedia). As is possible with UWB network configurations), the total overhead for the data packet structure in Figure 4 is 46.25us. Therefore, assuming 4096 octet physical layer service data unit (PSDU) transmission at 480 Mbps, the transfer duration is 69.375us and the MAC efficiency η is 0.6. Assuming 512 octet PSDU transmission at 53.3 Mbps, the transfer duration is 76.875us and the MAC efficiency η is 0.624.

Then refer to Figure 5 for the data transaction sequence for the B-ACK acknowledgment policy. The data packet structure of FIG. 5 consists of a first PLCP preamble, a first PLCP header, a payload frame, a plurality of minimum frame intervals (MIFS), a plurality of burst preambles, a plurality of PLCP headers, and a plurality of PLCP headers. It includes a payload frame, SIFS, a second (B-ACK) PLCP preamble, a second (B-ACK) PLCP header, a second (B-ACK) SIFS, and a B-ACK body. For example, consider the case where burst mode is used with a burst preamble and eight bursts. After the first PLCP preamble, PLCP header, and payload frame, MIFS, burst preamble, PLCP header, payload frame, SIFS, ACK PLCP preamble, ACK PLCP header, and ACK, respectively. Seven bursts of SIFS follow. The first PLCP preamble has a duration of 9.375us, the second to eighth PLCP preambles each have a duration of 5.625us, the eight PLCP headers each have a duration of 3.75us, and the MIFS has a duration of 1.875 each. If us has a duration of us, SIFS has a duration of 10 us, and B-ACK has a duration of 1.875 us (as is possible in a WiMedia UWB network configuration), the sum for the data packet structure in Figure 4. The overhead of is 126.875us. Therefore, assuming 4096 octet PSDU transmission at 480 Mbps, the transfer duration is 555us and the MAC efficiency η is 0.814.

From the above, the following can be seen for most scenarios.<maths num="5"><img id="000006" he="15" wi="159" file="JP5774672B2_D0001.tif" img-format="tif" img-content="drawing" /></maths>

Taking a conservative estimate of the average MAC efficiency η = 0.7 and using this average MAC efficiency value to solve equation (4),<maths num="6"><img id="000007" he="28" wi="140" file="JP5774672B2_D0001.tif" img-format="tif" img-content="drawing" /></maths>

Is obtained.<maths num="7"><img id="000008" he="21" wi="159" file="JP5774672B2_D0001.tif" img-format="tif" img-content="drawing" /></maths>

Assuming that<maths num="8"><img id="000009" he="18" wi="159" file="JP5774672B2_D0001.tif" img-format="tif" img-content="drawing" /></maths>

Is.

Equations (6) and (8) indicate that resource availability at each node of each set of network nodes that provides an end-to-end data path between the source and destination is end-to-end. If it is possible to meet the communication requirements of the data flow, it should be met for each hop of the end-to-end path.

x_{i, k}Represents the kth MAS availability of node i. Therefore,<maths num="9"><img id="000010" he="20" wi="159" file="JP5774672B2_D0001.tif" img-format="tif" img-content="drawing" /></maths>

Similarly, x_{j, k}Represents the MAS availability of the kth node j.

S_{ij, k}Is the link L between node i and node j_ijIt shall represent the kth MAS availability with respect to. Therefore,<maths num="10"><img id="000011" he="20" wi="159" file="JP5774672B2_D0001.tif" img-format="tif" img-content="drawing" /></maths>

Is.

The following formula<maths num="11"><img id="000012" he="19" wi="80" file="JP5774672B2_D0001.tif" img-format="tif" img-content="drawing" /></maths>

But the link L on both node i and node j_ijSuppose it represents the number of MAS available for. Therefore,<maths num="12"><img id="000013" he="24" wi="124" file="JP5774672B2_D0001.tif" img-format="tif" img-content="drawing" /></maths>

Is.

All network nodes in the end-to-end data path, except source and destination network nodes, should support two simultaneous reservations. Specifically, these network nodes should support one reservation as a reservation target and another reservation as a reservation owner at the same time. Therefore, the L between node i and node j_ij, And L between node j and node h_jhConsidering the two links,<maths num="13"><img id="000014" he="21" wi="159" file="JP5774672B2_D0001.tif" img-format="tif" img-content="drawing" /></maths>

Is.

The total number of MAS available at intermediate node j must meet the following:<maths num="14"><img id="000015" he="18" wi="159" file="JP5774672B2_D0001.tif" img-format="tif" img-content="drawing" /></maths>

The MAS considered for the first booking is not available for the second booking. Therefore, the MAS at each link do not interfere with each other.

Equations (11), (12), and (13) should be satisfied for each intermediate network node in the end-to-end data flow if the desired end-to-end data flow is to be supported. Represents a set of resource constraints. Therefore, in addition to satisfying equations (6) and (8) above, equations (11), (12), and (13) are, respectively, desired to support both bookings. Must be satisfied at intermediate node j to support end-to-end data flow. If only one of equations (11) and (12) is satisfied, it means that only one reservation can be supported and the other reservation is not. If both equations (11) and (12) are satisfied, but equation (13) is not satisfied, then both reservations can be supported on a stand-alone basis, but two simultaneous reservations Therefore, the desired end-to-end data flow cannot be supported. If node i and / or node h is also an intermediate node, the same feasibility check will also be performed on those nodes.

Upon operation according to the embodiment, the network node sends a list of MAS that it considers available to the network node itself within a two-hop neighborhood. For example, in operation according to the ECMA-368 specification, the Distributed Reservation Protocol (DRP) Availability Information Element (IE) presents MAS by sending a list of available MAS in DRP Availability IE in a beacon frame. Can be used by a network node to indicate its use of. Using such information, network nodes in the end-to-end data path evaluate whether resource constraints (eg, as shown in equations (11), (12), and (13)) are met. It is possible to do.

Even when all three equations (11), (12), and (13) are individually satisfied, L_ijAbove and L_jhAny allocation of slots between the above two reservations may not meet the requirements of both reservations. The resource allocation method shown in FIG. 6 is L._ijAbove and L_jhUsed to ensure that the slot allocation between the above two reservations meets the requirements of both reservations.

In block 601 of the embodiment shown in FIG. 6, an intermediate network node of the end-to-end data path identified as having sufficient resources available to support the desired end-to-end data flow. , Selected for resource allocation. In block 602, set S_ij-S_ij S_jhThe slot from is the link L of the selected network node_ijAssigned to. At block 603, link L_ijIf it is determined that the communication requirements for are met by the slots allocated in block 602, then link L_ijAllocation to is complete and processing according to the indicated embodiment proceeds to block 605. But in block 603, link L_ijIf it is determined that the communication requirements for are not met by the slots allocated in block 602, the action is link L._ijProceed to block 604 for further slot allocation to. At block 604, link L_ijThe remaining slots for set S_ij S_jhAssigned from.

In block 605, set S_jh-S_ij S_jhThe slot from is the link L of the selected network node_jhAssigned to. At block 606, link L_jhIf it is determined that the communication requirements for are met by the slots allocated in block 605, then link L_jhAllocation to is complete and processing according to the indicated embodiment proceeds to block 608. But in block 606, link L_jhIf it is determined that the communication requirements for are not met by the slots allocated in block 605, the action is link L._jhProceed to block 607 for further slot allocation to. In block 607, link L_jhThe remaining slots for set S_ij S_jhAssigned from.

At block 608, a determination is made as to whether additional intermediate network nodes exist in the end-to-end data path for resource allocation. If additional intermediate network nodes are present, the processing according to the indicated embodiment returns to block 601 for the selection of another intermediate network node. If no additional intermediate network nodes are present, processing according to the indicated embodiment proceeds to block 609, ending resource allocation for the end-to-end data path.

To further explain the operation by the above, N_{MAS, ij}= 10, N_{MAS, jh}= 8, n (S_ij) = 12, n (S)_jh) = 8, and n (S)_ij S_jh) = 2. Therefore, n (S)_ijS_jh) = 12 + 8-2 = 18. Each of equations (11), (12), and (13) is satisfied. But link L_ij10 slots for, 1 or 2 slots S_ij S_jhLink L if assigned to be from_jhSlot requirements for cannot be met. The slot allocation method shown in FIG. 6 increases the likelihood of achieving the desired end-to-end data flow goal, and / or the slot allocation method shown in FIG. 6 is the desired end-to-end data flow. To be used in providing the desired end-to-end data flow when multiple end-to-end data paths can provide resource availability at each node to meet the communication requirements of the data flow. It can be used to select a particular end-to-end data path.

In the embodiments of the present disclosure, minimizing the total number of MAS is equivalent to minimizing the air time, so that the minimum total number across all links in the end-to-end data path. Acts additionally or as an alternative to select a particular end-to-end data path from multiple end-to-end data paths that have resource allocations that meet the communication requirements of utilizing MAS. Total number of MAS across all links, N_TotalIs given by:<maths num="15"><img id="000016" he="23" wi="159" file="JP5774672B2_D0001.tif" img-format="tif" img-content="drawing" /></maths>

Assuming the same MAC efficiency across all links, the following equation should be minimized.<maths num="16"><img id="000017" he="19" wi="124" file="JP5774672B2_D0001.tif" img-format="tif" img-content="drawing" /></maths>

Here, in order to select the best end-to-end data path from multiple end-to-end data paths that meet the desired end-to-end data flow communication requirements, R'_ij= R_ij× (1-p_ij).

The methods described herein can be implemented by various components depending on the application. For example, these methods can be implemented in hardware, firmware, software, or any combination thereof. For hardware implementations, the processing unit is one or more application-specific integrated circuits (ASICs), digital signal processors (DSPs), digital signal processing devices (DSPDs), programmable logic devices (PLDs), and field programmable gate arrays. (FPGA), processors, controllers, microcontrollers, microprocessors, electronic devices, other electronic units designed to perform the functions described herein, or combinations thereof. ..

For firmware and / or software implementations, the method can be implemented using modules (eg, procedures, functions, etc.) that perform the functions described herein. Any machine-readable medium that materializes the instruction can be used in implementing the methods described herein. For example, software code can be stored in memory and executed by a processor unit. The memory can be implemented inside the processor unit or outside the processor unit. As used herein, the term "memory" refers to any type of long-term, short-term, volatile, non-volatile, or other memory, any particular type of memory, any particular number of memories. , Or memory is not limited to any particular type of medium in which it is stored.

When implemented in firmware and / or software, features can be stored as one or more instructions or codes on a computer-readable medium. Examples include computer-readable media encoded by data structures and computer-readable media encoded by computer programs. Computer-readable media include physical computer storage media. The storage medium can be any available medium that can be accessed by a computer. As an example, but not limited to, such computer-readable media include random access memory (RAM), read-only memory (ROM), electrically erasable programmable read-only memory (EEPROM), and compact disk read-only memory (compact disk read-only memory). Can be used to store desired program code in the form of CD-ROM) or other optical disc storage, magnetic disk storage or other magnetic storage devices, or instructions or data structures and is accessed by a computer. It is possible to include any other medium capable of, and the discs and discs used herein include compact discs (CDs), laser discs (registered trademarks), optical discs, and optical discs. Includes digital versatile discs (DVDs), floppy (registered trademark) discs, and Blu-ray discs, where discs typically play data magnetically, whereas discs ) Optically reproduces the data using a laser. The above combinations are also included in the range of computer-readable media.

In addition to storage on a computer-readable medium, instructions and / or data can also be provided as signals on a transmission medium included in the communication device. For example, a communication device can include a transceiver that has signals indicating instructions and data. Instructions and data are configured to allow one or more processors to perform the functions outlined in the claims.

FIG. 7 shows a processor-based system 700 adapted in accordance with the present disclosure to provide the operations described herein under the control of the code segments described above. The processor-based system 700 can include a network node such as any of the network nodes N0 to N5 in FIG. 1, or a system coupled to one or more network nodes. Processor 701 is coupled to system bus 702. Processor 701 is Intel Corporation (Intel) It can be equipped with a general purpose central processing unit (CPU) such as a PENTIUM® processor available from Corporation, or a dedicated processor such as an application specific integrated circuit (ASIC) or programmable gate array (PGA). .. However, the present disclosure is not limited by the architecture of the processor 701 as long as the processor 701 supports the operations of the invention described herein. Bus 702 is coupled to memory 703, which can be equipped with any suitable computer-readable medium such as RAM, ROM, flash memory, optical memory, magnetic memory. The memory 703 stores user data, system data, resource constraint information, program code, and the like in order to facilitate the operations described herein. Bus 702 is also coupled to input / output (I / O) interface 704 and network interface 705. The I / O interface 704 provides interfacing of various peripherals, components, devices, etc. that can be equipped with keyboards, keypads, pointing devices, display devices, and the like. Therefore, the I / O interface 704 can include a plurality of individual interfaces, interface protocols, and the like. The network interface 705 can provide interfacing with one or more network links, such as one or more wired links, wireless links, fiber optic links, and the like. Thus, the network interface 705 can include a single network interface or a plurality of network interfaces that operate according to one or more network protocols.

Although this disclosure and its advantages have been described in detail, various changes, substitutions, and amendments may be made herein without departing from the spirit and scope of the disclosure as defined by the appended claims. I want you to understand. Furthermore, the scope of the present application is not intended to be limited to specific embodiments of the processes, machines, manufactures, composition of substances, means, methods, and steps described herein. As will be readily appreciated by those skilled in the art from the disclosure of the present invention, performing substantially the same functions as the corresponding embodiments described herein, or achieving substantially the same results. Existing or later developed processes, machines, manufactures, composition of substances, means, methods, or steps can be utilized in accordance with the present invention. Therefore, the appended claims are intended to include such processes, machines, manufactures, composition of substances, means, methods, or steps within the scope.<u style="single"> The inventions described in the claims of the original application of the present application are described below.</u><u style="single">[C1]</u><u style="single"> A method of choosing an end-to-end data path in a distributed multi-hop time division multiple access (TDMA) network, said end-to-end data path is a plurality of resources having sufficient available resources at each node. A selection from end-to-end data paths thereby guaranteeing quality of service (QoS) for the desired end-to-end data flow, said method.</u><u style="single"> Minimizing the total number of slots used for the desired end-to-end data flow,</u><u style="single"> It leaves the maximum number of slots on virtually all nodes in the selected end-to-end data path, thereby allowing new data flows to be accepted into the network with their QoS satisfied. And</u><u style="single"> To minimize the power consumption of intermediate network nodes in the selected end-to-end data path, thereby ensuring route availability over a longer period of time in the absence of other factors.</u><u style="single">A method comprising selecting at least one end-to-end data path for the desired end-to-end data flow, at least in part based on at least one of them.</u><u style="single">[C2]</u><u style="single"> The method according to [C1], wherein the selection comprises selecting multiple end-to-end data paths for robust routing.</u><u style="single">[C3]</u><u style="single"> At least one end-to-end, further comprising analyzing slot allocations for the plurality of end-to-end data paths to determine the total number of slots used for the desired end-to-end data flow. The selection of the data path selects an end-to-end data path having the minimum total number of slots used for the desired end-to-end data flow determined by the analysis. The method described in C1].</u><u style="single">[C4]</u><u style="single"> The number of slots remaining on a node in the end-to-end data path when used for the desired end-to-end data flow by analyzing the slot allocation for the multiple end-to-end data paths. The selection of at least one end-to-end data path further comprises determining the end-to-end data path that leaves the maximum number of slots on virtually all nodes, [C1]. The method described in.</u><u style="single">[C5]</u><u style="single"> Further comprising allocating slots between uplinks and downlinks at each intermediate node of the selected end-to-end data path to meet the desired end-to-end data flow QoS requirements. The method described in C1].</u><u style="single">[C6]</u><u style="single"> End-to-end data with the desired communication attributes in the network using at least one end-to-end data path with resource availability at each network node to meet the desired communication attributes. A way to provide a flow,</u><u style="single"> Propagating resource constraint information to the nodes of the network,</u><u style="single"> Using the resource constraint information, is it possible for resource availability at each network node of the at least one end-to-end data path to meet the desired communication attributes of the end-to-end data flow? To decide whether or not,</u><u style="single"> The at least one end-to-end determined to have resource availability at each network node to meet the desired communication attributes for use in providing the end-to-end data flow. Select an end-to-end data path from the data paths, and</u><u style="single"> A method comprising allocating communication resources to each network node of the selected end-to-end data path to provide the end-to-end data flow that meets the desired communication attributes.</u><u style="single">[C7]</u><u style="single"> The method according to [C6], wherein the desired communication attribute comprises a desired quality of service (QoS).</u><u style="single">[C8]</u><u style="single"> The selection of the end-to-end data path is</u><u style="single"> Minimizing the total number of communication resources used for the desired end-to-end data flow,</u><u style="single"> Leaving the maximum number of communication resources on virtually all nodes in the selected end-to-end data path, and</u><u style="single"> To minimize the power consumption of the network nodes of the selected end-to-end data path,</u><u style="single">The method described in [C6], which makes a selection based at least in part on at least one of them.</u><u style="single">[C9]</u><u style="single"> The method according to [C8], wherein the communication resource comprises a time slot of a time division multiple access (TDMA) network communication protocol.</u><u style="single">[C10]</u><u style="single"> The method according to [C6], wherein the selection of the end-to-end data path comprises selecting a plurality of end-to-end data paths for providing the end-to-end data flow.</u><u style="single">[C11]</u><u style="single"> The selection of the end-to-end data path is</u><u style="single"> Analyzing the communication resource allocation for at least one end-to-end data path to determine the total number of communication resources used for the desired end-to-end data flow, and the desired end. The method described in [C6], comprising selecting a resource allocation and end-to-end data path with the minimum total number of communication resources used for two-end data flow.</u><u style="single">[C12]</u><u style="single"> The selection of the end-to-end data path is</u><u style="single"> Communication resource allocation is analyzed for the at least one end-to-end data path and the communication that remains on the node in the at least one end-to-end data path when used for the end-to-end data flow. The method described in [C6], comprising determining the number of resources and choosing an end-to-end data path and resource allocation that leaves the maximum number of slots on virtually all nodes.</u><u style="single">[C13]</u><u style="single"> Allocating the communication resource</u><u style="single"> It comprises allocating communication resources between uplinks and downlinks at each intermediate node of the selected end-to-end data path to satisfy the communication attributes of the end-to-end data flow [C6]. The method described in.</u><u style="single">[C14]</u><u style="single"> Allocating the communication resource</u><u style="single"> With respect to the intermediate network node of the selected end-to-end data path</u><u style="single"> Allocating communication resources to the uplink associated with the intermediate network node from a set of communication resources available to the intermediate network node and the uplink network node that are not available on the downlink network node.</u><u style="single"> If the uplink requirements remain unmet by the allocation, from the set of communication resources available to the intermediate network node, the uplink network node, and the downlink network node to the uplink associated with the intermediate network node. Allocating communication resources,</u><u style="single"> Allocating communication resources from a set of communication resources available to the intermediate network node and the downlink network node that are not available to the uplink network node to the downlink associated with the intermediate network node, and</u><u style="single"> If the downlink requirement remains unmet by the allocation, from the set of communication resources available to the intermediate network node, the uplink network node, and the downlink network node to the downlink associated with the intermediate network node. The method described in [C6], which comprises allocating communication resources.</u><u style="single">[C15]</u><u style="single"> End-to-end data with the desired communication attributes in the network using at least one end-to-end data path with resource availability at each network node to meet the desired communication attributes. A system for providing a flow, the system said.</u><u style="single"> The memory comprises a network node having a memory and a processor, the memory stores resource constraint information about the adjacent network node, and the adjacent network node has an uplink network node regarding an end-to-end data path and the end-to-end data. With a downlink network node for the path, the memory further uses network resource availability at the network node using the resource constraint information for the uplink and downlink network nodes of the end-to-end data path. Stores code that defines the behavior of the processor that can operate to determine whether it meets the communication requirements of the desired end-to-end data flow, and the memory further meets the communication requirements. A system that stores code that defines the behavior of the processor capable of allocating resources at the network node to achieve the desired end-to-end data flow.</u><u style="single">[C16]</u><u style="single"> The system according to [C15], wherein the allocated resource comprises a time slot of a time division multiple access (TDMA) network protocol.</u><u style="single">[C17]</u><u style="single"> The network node comprises a node configuration selected from the group consisting of computers, personal digital assistants (PDAs), telephones, servers, routers, gateways, switches, multiplexers, modems, radios, access points, and base stations. The system described in C15].</u><u style="single">[C18]</u><u style="single"> It comprises a plurality of network nodes having a memory and a processor, the memory stores resource constraint information about an adjacent network node, and the memory further uses the resource constraint information to network in the corresponding network node. The memory stores code that defines the behavior of the processor capable of operating to determine whether resource availability meets the communication requirements of the desired end-to-end data flow, and the memory further comprises said communication. [C15], which stores code defining the behavior of the processor capable of allocating resources at the corresponding network node to achieve the desired end-to-end data flow that meets the requirements. system.</u><u style="single">[C19]</u><u style="single"> End-to-end data with the desired communication attributes in the network using at least one end-to-end data path with resource availability at each network node to meet the desired communication attributes. A system for providing flow</u><u style="single"> Using the resource constraint information about the nodes of the network, the resource availability at each network node of the at least one end-to-end data path satisfies the desired communication attribute of the end-to-end data flow. A means to determine if it is possible,</u><u style="single"> The at least one end-to-end determined to have resource availability at each network node to meet the desired communication attributes for use in providing the end-to-end data flow. -Means for selecting an end-to-end data path among data paths,</u><u style="single"> A system comprising means for allocating communication resources to each network node of the selected end-to-end data path to provide the end-to-end data flow satisfying the desired communication attributes.</u><u style="single">[C20]</u><u style="single"> The system according to [C19], further comprising means for propagating the resource constraint information to the nodes of the network.</u><u style="single">[C21]</u><u style="single"> The system according to [C19], wherein the communication resource includes a time slot of a time division multiple access (TDMA) network communication protocol, and the resource constraint information includes information regarding the availability of a time slot of the TDMA communication protocol. ..</u><u style="single">[C22]</u><u style="single"> End-to-end data with the desired communication attributes in the network using at least one end-to-end data path with resource availability at each network node to meet the desired communication attributes. A computer program product for providing a flow, said computer program product.</u><u style="single"> A computer-readable medium for storing computer executable code is provided, and the computer executable code is a computer-readable medium.</u><u style="single"> Using the resource constraint information about the nodes of the network, the resource availability at each network node of the at least one end-to-end data path satisfies the desired communication attribute of the end-to-end data flow. Code to determine if it is possible,</u><u style="single"> The at least one end-to-end determined to have resource availability at each network node to meet the desired communication attributes for use in providing the end-to-end data flow. -Code for selecting an end-to-end data path from the data paths, and</u><u style="single"> A computer program product, comprising code for allocating communication resources to each network node of the selected end-to-end data path to provide the end-to-end data flow that meets the desired communication attributes.</u><u style="single">[C23]</u><u style="single"> The code for selecting an end-to-end data path minimizes the total number of communication resources used for the desired end-to-end data flow, said end-to-end data flow selected. Leaving the maximum number of communication resources on virtually all nodes in the data path, and at least partial to at least one of the available power at the network nodes in the selected end-to-end data path. A computer program product described in [C22] that is capable of acting to make selections based on.</u><u style="single">[C24]</u><u style="single"> The code for selecting an end-to-end data path is</u><u style="single"> Code for analyzing communication resource allocation for at least one end-to-end data path,</u><u style="single"> A code for determining the total number of communication resources used for the desired end-to-end data flow, at least in part based on the information from the code for analysis.</u><u style="single"> [C22], which comprises a code for selecting an end-to-end data path and resource allocation with the minimum total number of communication resources used for the desired end-to-end data flow. Computer program product.</u><u style="single">[C25]</u><u style="single"> The code for selecting an end-to-end data path is</u><u style="single"> The code for analyzing communication resource allocation for at least one end-to-end data path,</u><u style="single"> Of the communication resources that remain on a node in the at least one end-to-end data path when used for the end-to-end data flow, at least in part based on the information from the code for analysis. The code to determine the number and</u><u style="single"> The computer program product described in [C22], which comprises code for selecting end-to-end data paths and resource allocations that leave the maximum number of slots on virtually all nodes.</u><u style="single">[C26]</u><u style="single"> The code for allocating communication resources</u><u style="single"> A code for allocating communication resources to the uplink associated with the intermediate network node from a set of communication resources available to the intermediate network node and the uplink network node that are not available on the downlink network node, and the uplink requirement is If the allocation of resources to the uplink remains unfulfilled, the code for allocation is from the set of communication resources available to the intermediate network node, the uplink network node, and the downlink network node. The code that allocates communication resources to the uplink associated with the intermediate network node,</u><u style="single"> A code for allocating communication resources from a set of communication resources available to the intermediate network node and the downlink network node, which are not available in the uplink network node, to the downlink associated with the intermediate network node, and downlink. If the requirement of is not met by the allocation of resources to the downlink, the code for allocation is a set of communication resources available to the intermediate network node, the uplink network node, and the downlink network node. The computer program product according to [C22], comprising a code that allocates communication resources to the downlink associated with the intermediate network node.</u>