|
Abstract : |
Admission control problems arise in very fast networks whenever there is a request to send a large amount of data from one node in the network to another node. The challenge is to decide (on-line) whether or not the network can or should accomodate the request. In this work we provide randomized algorithms for general networks and for the case where each request asks for the entire bandwidth of the virtual circuit(s) that are possible to be granted. Let L be the length of the longest simple path in the network,and k(G), (G) the vertex and edge connectivity of G. Admission control has been previously considered in a variety of contexts (see e.g. [ABFR,94],[AGLR,94]). The problem was formulated in [GG,92]. Competitive algorithms for general networks were provided in [AAP,93],but with the restriction that every virtual circuit requests at, |
