TI Network Resource Negotiation and Flexible Knapsack Problem 

AV ftp thorhild.cs.ualberta.ca:pubTR91-05.ps.Z 

AV mail britta@cs.ualberta.ca  

OR ALBRT 

LT TR 91-05 

AU S. Deng 

AU U.M. Maydell 

MN March 

YR 1991 

AB This report proposes a new integrated access control and
bandwidth allocation scheme for connection-oriented services for
future telecommunications networks.  Also proposed in this
document is a new knapsack problem, the flexible knapsack
problem, which differs from the conventional knapsack problems in
allowing different packing forms for the objects from the same
class. The first chapter introduces some key concepts and an
overview of future telecommunication networks.  Next, we outline
the proposed resource negotiation and allocation scheme, called
flexible access control technique (FACT), and its prospective
applications.  This new scheme can be generalized for resource
allocation in many other areas such as data compression and
archiving, merchandise inventory management and so on.  The third
chapter is a specification of the flexible knapsack problem
arising from the new resource allocation scheme.  The flexible
knapsack provides a more general model than the conventional
knapsack.  The fourth chaptediscusses approaches to solving the
flexible knapsack problems.  Both some exact solution approaches
and a heuristic solution approach are presented.  The results of
an empirical study are reported in the fifth chapter.  The
results show that the new scheme, FACT, can outperform the
conventional schemes up to 60

 for broadband traffic.  The heuristic algorithm was proved to be
very close to the optimum and significantly faster than the exact
solution, especially when the network bandwidth capacity is very
large or the carried traffic consists of a considerable amount of
narrowband calls.  A list of acronyms and references complete
this report.