Browse Prior Art Database

Topology Aware Microeconomics Based BW Allocation Algorithm

IP.com Disclosure Number: IPCOM000078093D
Original Publication Date: 2005-Feb-25
Included in the Prior Art Database: 2005-Feb-25
Document File: 6 page(s) / 525K

Publishing Venue

Motorola

Related People

Fumika Gotoh: AUTHOR

Abstract

A complicated multi-hop packet network is proposed. It is assumed that each user has an associated piecewise linear utility function which describes the benefit that a user obtains from a bandwidth allocation, admission control and resource allocation algorithm.

This text was extracted from a Microsoft Word document.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 53% of the total text.

Topology Aware Microeconomics Based BW Allocation Algorithm

Fumika Gotoh

Abstract

A complicated multi-hop packet network is proposed.  It is assumed that each user has an associated piecewise linear utility function which describes the benefit that a user obtains from a bandwidth allocation, admission control and resource allocation algorithm.

Problems to be solved

When network’s topology becomes complicated, such as multi-hop, there are problems in fairness and efficiency. For an example, in the Maximum Segmental Slop microeconomic spot market resource allocation algorithm [1], some users with high utility function get much bandwidth but the whole of the allocated bandwidth is not fully utilized (over booking). In Figure 1, Flow1 and Flow2 each get 2 units but either uses only 1 unit. Therefore as the result, Access Router 2 (AR2) has 1unit to be un-used and AR4 has 3 units to be un-used. On the other hand, at the same time, users with low utility function are blocked due to "lack of bandwidth", although actually the network is not in congestion and has some unused resources. In the same figure, Flow6 is blocked due to “lack of bandwidth”. And at the same time, AR2 and AR4 each have remaining bandwidth (BW) to be un-used. If the remaining BW can be allocated to Flow6, there is no any bad effect to Flow1-Flow4 with high utility function. Furthermore, network or service operator may have more utility (e.g., much revenue) with the un-used resource allocated.

Embodiment

In order to solve the problems, following method is proposed. In this method, there are five important entities: Caller, Callee, and their access router or point (erAR, eeAR), and QoS server or broker (QS).

Each caller's utility is expressed via a piecewise linear utility function. A utility function expresses the maximum price that a user is willing to pay (in money/second) for possible amount of throughput which his traffic flow could be allocated (in bandwidth/sec).

This method consists of the following algorithm:

1.      QoS server receives resource allocation request from caller or caller’s AR called erAR.

2.      QoS server generates this new flow’s entry called fi which has the information of its caller's access router (fi_erAR), and callee's access router (fi_eeAR).

3.      From 2, QS generates a list of the existing flows that need to be re-allocated due to fi’s joining. It is called fi_re_flow_list. This list is made of flows that are passing fi_erAR or fi_eeAR, therefore fi_re_flow_list can be divided into fi_erAR_re_flow_list (for example, it includes flow_a, flow_b, flow_c, …) and fi_eeAR_re_flow_list (for example, it includes flow_x, flow_y, flow_z, …).

4.      QS allocates fi_erAR’s bandwidth (fi_erAR_total_bw) to flow fi and the flows in fi_erAR_re_flow_list (flow_a, flow_b, flow_c, …) based on MSS algorithm.

5.      fi gets fi_er_alloc(bandwidth/sec), and the flows in fi_erAR_re_flow_list gets Σfi_erAR_re_flow_list_temp_alloc, which is the sum of each flow...