WO2002039631A1

WO2002039631A1 - Method for prioritization of network resources in networks

Info

Publication number: WO2002039631A1
Application number: PCT/SE2001/002464
Authority: WO
Inventors: Olof Hagsand; Kjell Hansson
Original assignee: Dynarc AB
Current assignee: Dynarc AB
Priority date: 2000-11-10
Filing date: 2001-11-07
Publication date: 2002-05-16
Anticipated expiration: 2003-05-10
Also published as: AU2002214461A1

Abstract

The method of prioritizing network resources in a network comprises providing the network with a high priority channel and a low priority channel. The high priority channel has insufficient bandwidth resources to transmit a message on the high priority channel. The high priority channel reserves bandwidth resources from a local free list. If this is insufficient, the high priority channel preempts bandwidth resources of the low priority channel. If this is insufficient to send the message, the high priority channel obtains bandwidth resources from the nodes in the network so the message can be send on the high priority channel.

Description

METHOD FOR PRIORITIZATION OF NETWORK RESOURCES IN NETWORKS

Technical Field The present invention relates to a method for prioritization and allocation of network resources in networks such as DTM networks .

Background Information and Summary of the Invention If is often difficult to prioritize the limited available network resources in a network. For example, low priority channels may take up valuable bandwidth resources that could be better used in high priority channels. The nodes in a network may also have bandwidth resources that should be available to high priority channels. There is a need for a method for effectively allocating the bandwidth resources in networks so that the use of the bandwidth resources may be allocated according to the priority of the network channels requiring additional bandwidth resources.

The method of the present invention provides a solution to the above described problems. More particularly, the method of prioritizing network resources in a network comprises providing the network with a high priority channel and a low priority channel. The high priority channel has insufficient bandwidth resources to transmit a message on the high priority channel . The high priority channel reserves bandwidth resources from a local free list. If this is insufficient, the high priority channel preempts bandwidth resources of the low priority channel. If this is insufficient to send the message, the high priority channel obtains bandwidth resources from the nodes in the network so the message can be send on the high priority channel. Brief Description of the Drawings

Fig. 1 is a schematic flow diagram of the prioritization and allocation system of the present invention.

Detailed Description

With reference to Fig. 1, the present invention is a prioritization and allocation system 10 for effectively prioritizing and allocating resources in a network, such as a dynamic transfer mode (DTM) network. When a channel is established in, for example, a DTM topology, it is sometimes necessary reallocate resources from low priority traffic channels to higher priority channels to ensure that the information in the high priority channels may be properly set-up and transmitted. For example, when the resources of a channel are insufficient or repleted, i.e., the channel has insufficient bandwidth or ^'DMA channels, it may be necessary to obtain resources from other channels or nodes. The bandwidth may be represented by a plurality of slots of the channel.

Preemption of channels has the function of making network resources available for high priority traffic. As is explained in detail below, high priority channels may preempt the bandwidth capacity of lower priority channels which may mean that the resources of the lower priority are reduced or even closed. If necessary, a channel may preempt several lower priority channels. The protocol may be designed so that the lowest priority channels cannot preempt other channels and the highest priority channels can never be preempted.

Channels may be preempted because there is not enough bandwidth available or because there is not enough per-channel resources available such as dma channels. As is detailed below, the channel preemption procedure may be initiated if a channel cannot allocate a sufficient amount of resources available to the sender node from a free list. As indicated above, the channels of the present invention may be prioritized. For example, a specification of the channels may include a priority field to indicate the priority levels of the channels. More particularly, filters may be used to set the various priorities to classes of traffic communication and a filtering matching mechanism may be use to prioritize channels. The present invention may be applied to a variety of channel types such as dynamic, switched, unicast, multicast and broadcast channel types. A high priority channel that requires extra bandwidth may reserve bandwidth resources from a local free list, preempt bandwidth from lower priority channels and borrow bandwidth capacity from other nodes in the network. For example, the channel may retrieve blocks from the free list. The blocks of slots may be preempted only if a token return time is greater than zero. The token return time may be interpreted to mean the time a token stays on the free list before the token is returned to the node that owns the token. If the token return time is set to zero, the blocks, after the use of the blocks is completed, are immediately returned to the node that owns the token without being stored on the free list and the blocks are no longer available for other channels via the free list. The method may be designed so that the borrowed slots are only returned after the token return time has expired if the owner node requests the borrowed slots to be returned. In this way, the borrowed slots are only returned to the owner node of the slots if the owner node needs the slots. If necessary, the same slots may be simultaneously used over disjointed segments, i.e., node segments, so that the same slots can be reused by several channels.

More particularly, in a setting device 12, the bandwidth parameter bw may be set to the min_bw paramete . The parameter bw may stand for the remaining bandwidth to be required and, therefore, required in each collection step. The min_bw parameter may be the required extra bandwidth that the channel needs from other resources whether the resources are obtained from the free list, other preemptable channels or other nodes. Before the prioritization method is initiated, the parameters dc_resvbw and dc_waitbw are, preferably, set to zero . The parameter dc_resvbw may represent the amount of reserved bandwidth capacity on the local free list. The parameter dc_waitbw may represent the amount of bandwidth capacity that has already been preempted or borrowed from other resources. A priority counter is also set so that the parameter pre_jprio may be set to the lowest priority (n) .

The setting device 12 may then send a comparison signal 14 to a comparison unit 16 that determines if the parameter bw is greater than zero. If the parameter bw is not greater than zero, then there is no need for obtaining extra bandwidth and the unit 16 sends a no- signal 18 to an end device 20 that ends the bandwidth allocation procedure and the channel may be set up to start sending payload information or any other type of information into the network topology.

If the parameter bw is greater than zero, the unit 16 may send a yes-signal 22 to a request unit 24. Depending upon the block distribution algorithm that is used and the token return time, a channel may reserve both blocks that is owned by the sender node and blocks that have been borrowed from other nodes. The unit 24 receives the signal 22 and transmits a request signal 26 to a comparison unit 28. The unit 28 determines if there is available bandwidth on the free list by checking if a parameter bw_fl is greater than zero which means that there is free available bandwidth on the free list. If there is available bandwidth capacity on the free list, the unit 28 may send a yes-signal 30 to a reservation unit 32 that reserves the bandwidth bw_fl to increase the parameter dc resvbw. All the available bandwidth is reserved if the channel needs all the bandwidth capacity available on the free list. Of course, the unit 32 may reserve less than the value of the parameter bw_fl if the value of the parameter bw_fl is greater than the parameter min_bw which may represent the bandwidth requirements of the channel . When the available bandwidth capacity on the local free list has been reserved, the unit 32 sends a comparison signal 34 to a comparison unit 36 to determine if the parameter bw is still greater than zero. This means that the channel requires more bandwidth capacity and it is necessary to invoke the channel preemption procedure of lower priority channels. Similarly, if there is no bandwidth capacity available on the free list, i.e., the parameter bw_fl is not greater than zero, the comparison unit 28 sends a no-signal 38 to the comparison unit 36 so that the preemption procedure may be initiated without going through the step of reserving bandwidth capacity on the free list.

The comparison unit 36 determines if the parameter bw is still greater than zero so that it may be necessary to preempt bandwidth capacity from a lower priority channel. If the parameter bw is not greater than zero, the unit 36 sends a no-signal 40 to an end unit 42 to end the procedure of obtaining additional bandwidth capacity because the channel does not need more bandwidth capacity. The channel may now be started to send payload information and other information to the nodes of the network.

If the parameter bw is greater than zero, the unit 36 sends a yes-signal 44 to an initiation unit 46 to start the channel bandwidth preemption procedure. There are many ways to identify suitable low priority channels to preempt. For example, the low priority channels may be scanned in the preemption procedure in the order of priority and the search may return either a selected channel or a no found message if no suitable channel is found. The method may search for reusable bandwidth in the lower priority channels as represented by a parameter bw_chan. The amount of requested bandwidth to be obtained in the preemption procedure may be represented by a parameter bw_req. The procedure may scan a list of channels until a valid outgoing channel is found that has the parameter bw_chan being greater than zero. The channel that is to be preempted must be valid for the preempting channel i.e., the preempted channel must extend over the nodes that correspond to the requirements of the preempting channel . The selected channel may then immediately be returned to the preemption list, as represented by a parameter pre_list . The total amount of bandwidth of the preempted channel is not necessarily considered. Instead of just searching for the first matching channel, the procedure may search primarily for a channel that has a bw_chan parameter that is equal to or greater than the parameter bw_req and the preempted channel must extend over the nodes that include the nodes of the preempting nodes. The matching procedure minimizes the number of channels that are preempted. The preempted channel is then immediately returned to the preemption list as indicated by the parameter pre_list. If no such channel may be found, the procedure may scan through the entire list and select the channel with the largest bw_chan parameter. If may also select the channel with the second largest bw_chan parameter for preemption. It is not necessary to consider the total amount of bandwidth capacity, whether reusable or non-reusable, of the preempted channel.

The procedure may also search for a channel that has a bw_chan parameter that is the same as the parameter bw_req. If no such channel is found, the procedure searches all the channels and selects the channel that has a bw_chan parameter that is the closest to the parameter bw_req to minimize the difference between the two parameter values . It may be necessary to go up in the priority level to find a suitable channel to preempt .

The procedure may be designed so that the size of the channels is considered to make sure that unnecessarily large channels are not preempted with respect to the reusable bandwidth capacity. The search procedure may also be adapted so that only channels in the same account or group are considered for preemption. The procedure may also be set so that only dynamic channels that have a bandwidth that is greater than the minimum requirement may be preempted.

When the unit 46 receives the yes-signal 44 to start the preemption procedure, the unit 46 may send a comparison signal 48 to a comparison unit 50. The unit 50 determines if the priority of the channel is greater than the lowest priority (n) of the channel to be preempted by comparing if the parameter dc_prio is greater than the parameter pre_prio (n) of the channel to be preempted. The parameter dc_prio may stand for the priority level of the channel requesting the extra bandwidth resources .

If the parameter dc_prio is greater than the parameter pre_prio(n) then the unit 50 sends a yes-signal 52 to a comparison unit 54. The unit 54 determines if the channel to be preempted has any available bandwidth capacity by determining if the parameter bw(n) is greater than zero. The parameter bw(n) may represent the available bandwidth of the channels at the priority level (n) . If there is no bandwidth available at the priority level (n) , i.e., the parameter bw(n) is not greater than zero, then the unit 54 sends a no-signal 56 to a setting unit 58 that increases the priority level from the level (n) to a level (n+1) so that the system will look for available bandwidth capacity in channels at the priority level (n+1) . The unit 58 sends an iteration signal 60 back to the unit 50 to determine if the parameter dc__jprio is greater than the parameter pre_prio (n+1) . This iteration continues as long as there is a need for extra bandwidth capacity and there is a priority level of the preempted channels that is lower than the priority level of the channel that needs the bandwidth. If the parameter bw(n) is greater than zero, the unit 54 sends a yes-signal 62 to a setting unit 64 that determines the remaining size of the bandwidth parameter bw by deducting the amount of bandwidth that is represented by the bandwidth parameter bw(n) of the preempted channel from the value of the required bandwidth parameter bw_old which represent the bandwidth requirement prior to the channel preemption procedure or the bandwidth requirement from the prior iteration at a lower priority level . The unit 64 sends a posting signal 66 to a posting unit 68 that adds the preempted channel or channels and the amount of bandwidth preempted to a preemption list, as represented by a parameter pre_list. One advantage of posting the preempted channels on the preemption list is that the preempted channels are not unnecessarily terminated in case the preempting channel can not find sufficient bandwidth in the various steps of preempting or borrowing bandwidth capacity from other channels or nodes, respectively.

The unit 68 then transmits a comparison signal 70 to a comparison unit 71 that determines if the parameter bw is still greater than zero which means that it may be necessary to preempt channel at a higher priority level than the priority level (n) . If the parameter bw is not greater than zero, the unit 71 may send an end signal 73 to an end unit 75 to end the preemption procedure and the channel may be started to send pay load information. If the parameter bw is greater than zero, the unit 71 may send a yes-signal 77 back to the setting unit 58 to increase the priority level to the priority (n+1) and to continue the search for channels to preempt at the priority level (n+1) . This iteration may continue as long as the parameter bw is greater than zero and the parameter dc_prio is greater than the parameter pre_prio.

However, if the comparison unit 50 determines that the parameter dc_prio is not greater than prejprio then the unit 50 may send a no-signal 79 to a comparison unit 72. If the parameter bw is still greater than zero although the preemption procedure has exhausted the available bandwidth resources from lower priority channel, it may be necessary to borrow bandwidth capacity from another node or several nodes.

If the parameter bw is not greater than zero, the unit 72 sends a no-signal 74 to an end unit 76 to end the search for additional bandwidth capacity because the requesting node has sufficient bandwidth capacity. On the other hand, if the parameter bw is greater than zero, the unit 72 sends a yes-signal 78 to a select unit 80 that selects a suitable node to borrow bandwidth capacity from. The unit 80 sends request signal 82 to a request unit 84 that requests bandwidth capacity from the selected node. The unit 84 sends a comparison signal 86 to a comparison unit 88 that determines if the amount of the requested bandwidth capacity (i) is less than a maximum borrow capacity of the node from which the bandwidth capacity is to be borrowed. The maximum bandwidth capacity that may be borrowed from a node may be set according to a local slot protection limit that refers to the amount of slots that a node is willing to lend to other nodes. However, the node often requires a minimum number of slots to function properly. The node is therefore only willing to lend out slots to other nodes as long as the node has the minimum amount of slots available for its own use.

If the requested bandwidth capacity (i) is not less than the maximum borrow capacity of the selected node, the unit 88 sends a no-signal 90 to a select unit 92 that selects a new node. The unit 92 sends a counter signal 94 to a counter 96 that counts the amount of node that have been selected to ensure that each node is only requested once. However, it may be possible to request bandwidth capacity from the same node more than once . The counter 96 then sends a request signal 98 to the request unit 84 that requests the required capacity from the newly selected node. This iteration continues until a sufficient amount of bandwidth capacity has been borrowed or until the counter 96 has reached a maximum allowed number that stops the iteration. If the requested bandwidth capacity (i) is less than the maximum amount of bandwidth capacity that may be borrowed from the selected node, the unit 88 sends a yes- signal 100 to a setting unit 102. The unit 102 determines the amount of remaining bandwidth capacity that is required by deducting the amount of borrow bandwidth capacity bw_b from the old bandwidth parameter value bw_old to calculate a new value for the parameter bw. The parameter bw_old may represent the required extra bandwidth that was required prior to step of borrowing bandwidth capacity from the node.

The unit 102 then sends a comparison signal 104 to a comparison unit 106 that determines if the parameter bw is greater than zero. If the parameter bw is not greater than zero, the unit 106 sends a no-signal 108 to an end unit 110 than ends the search for additional bandwidth capacity because the requesting channel has a sufficient amount of bandwidth capacity to carry out and start operation of channel. If the unit 106 determines that the parameter bw is still greater than zero, the unit 106 sends a yes-signal 112 to a close unit 114 that closes down the channel because not sufficient bandwidth capacity could be found despite the search for available bandwidth capacity in the free-list, lower priority channels and other nodes. It may also be necessary to release channel-specific resources for higher priority traffic such as DMA channels. The bandwidth reservation described above may take place locally but provides no guarantee that connection request replies are successfully returned although the link capacity, through the extra bandwidth allocation, is guaranteed. For example, the receiver node may lack channel resources, such as dma channels, and must thus reject the connection request. Similarly, the sender node may not be able to connect to other nodes due to insufficient or no dma channel resources.

In order to provide the necessary dma resources to a high priority channel, lower priority traffic channels may be preempted regardless of the available bandwidth resources and whether the channel is an outgoing or an incoming channel. However, it may be possible to design the dma preemption method to consider the available bandwidth resources of the preempted channel also before the lower priority channel is preempted to minimize the damage to the capacity of the entire network. The dma preemption method may also be designed to consider how often or how much the low priority channels are being used so that the least used low priority channel is selected for dma preemption.

The high priority channel can only dma preempt lower priority channels. All the resources of the low priority channels, except certain blocks, may be released immediately at the time of preemption so that the dma resources can be immediately used by the preempting high priority channel. If the preempted channel does not have an available dma channel, the higher priority channel may reject the preempted channel. While the present invention has been described in accordance with preferred compositions and embodiments, it is to be understood that certain substitutions and alterations may be made thereto without departing from the spirit and scope of the following claims.

Claims

We claim :

1. A method of prioritizing network resources in a network, comprising: (a) providing a network of nodes having a high priority channel and a low priority channel , the low priority channel having bandwidth resources, the high priority channel having insufficient bandwidth resources to transmit a message on the high priority channel; (b) the high priority channel reserving bandwidth resources from a local free list of the network, the free list comprising available bandwidth capacity on the network;

(c) the high priority channel preempting bandwidth resources of the low priority channel when the free list has insufficient bandwidth resources to send the message; and

(d) the high priority channel obtaining bandwidth resources from the nodes of the network when the low priority channel has insufficient bandwidth resources to send the message.

2. The method according to claim 1 wherein the method further comprises providing the bandwidth resources with a block of slots.

3. The method according to claim 2 wherein the method further comprises the high priority channel preempting bandwidth resources from the free list only when the block of slots have a token return time greater than zero .

4. The method according to claim 1 wherein the method further comprises the high priority channel returning bandwidth resources to the nodes when a token return time is zero.

5. The method according to claim 1 wherein the method further comprises determining whether the high priority channel has sufficient bandwidth to send the message on the high priority channel .

6. The method according to claim 1 wherein the method further comprises determining whether the free list has available bandwidth resources.

7. The method according to claim 1 wherein the method further comprises the high priority channel obtaining a portion of a total bandwidth requirement from the low priority channel to send the message.

8. The method according to claim 1 wherein the method further comprises the high priority channel obtaining a portion of a total bandwidth requirement from the nodes to send the message .

9. The method according to claim 1 wherein the method further comprises the high priority channel obtaining a portion of a total bandwidth requirement from the free list to send the message.

10. The method according to claim 1 wherein the method further comprises adding preempted bandwidth resources to a preemption list.