Journal of System Software, 1995Resource Allocation for Multiparty ConnectionsC. Edward Chow1Department of Computer ScienceUniversity of Colorado at Colorado SpringsColorado Springs, CO 80933-7150Phone: (719) 593-3110Email: [email protected] paper addresses the problems of specifying complex multimedia multipartyconnections and allocating resources to set up multimedia multipoint connections, whileefficiently using network resources, in a network that includes signal converters to resolvethe heterogeneity of customer/network equipments and information mixers for conferenceservices. A notation called logical connection is proposed to capture the special resourcesand connectivity requirements. Given a connection request and a physical network, weconsider the general resource allocation problem where the allocation costs of specialresources and links are comparable so that neither can be neglected. The problem is shownto be NP-hard. A resource allocation software system which integrates an optimal algorithm,several heuristic algorithms, and a distributed algorithm was implemented, and theperformance result of these algorithms is presented.Keywords: Resource Allocation, Multimedia, Multiparty Communication, BroadbandNetworks, Optimal Algorithm, Heuristic Algorithm, Distributed Algorithm.1. IntroductionRapid advances in switch and transmission technologies have made it possible to providemultimedia multiparty communication services to customers with different physical interfaces. Highspeed switch fabrics with tremendous bandwidth capacity and multicast capability are beingdesigned. Signal converters that resolve the physical interface differences are being designed andimplemented. Conference circuits that merge several video/audio streams are available, althoughmuch work remains to be done on digital bridging for both audio and video. Networks offering audio/visual connection services will contain these communication equipments [Addeo, Gelman, andMassa, 1987][Albanese et al, 1991][Arango et al, 1993][Bussey, Porter, and Raitz, 1989][Gelman1. Some of this research was done while the author was with Bell Communications Research2 of 23RAMCand Halfin, 1990][Giacopelli, Littlewood, and Sincoskie, 1990][Hardt-Kornacki and Ness, 1991][Lee 1988][Root 1988][Sakata 1990][Turner 1986].Unlike the traditional resource allocation problem which deals only with links or trunk groupsallocation [Akselrod and Langholz, 1985][Weinrib and Gopal, 1991], to set up a multimediamultiparty connection among customers with different terminal equipments in a given network, itmay be required to reserve special resources from the network, such as the signal converters or theconference bridging circuits, and to reserve bandwidth in the links of the network which provide thetransport for the information streams transmitted among special network resources and customerpremise equipments. In this paper, links, trunk groups, converters, and conference circuits are allconsidered network resources. The converters and conference circuits are referred as specialresources. This work minimizes costs over both types of resources.There may be many special resources in the network that can satisfy the requirement of acomplex connection. The allocation cost will be one of the important factors for selecting a particularspecial resource rather than an equivalent one in a different location. The other factor for selecting aspecial resource is the cost of links among the selected special resources and out to the user accessinterface. In this paper we consider the general case of the Resource Allocation problem formultimedia Multiparty Connections, abbreviated as the RAMC problem, where the allocation costof special resources and links are close and can not be neglected. The problem is difficult because theselection of one special resource for the connection will affect the cost of the links that connect thisspecial resource to other required special resources, and therefore the selection decision for otherspecial resources in the same connection. How to efficiently allocate special resources and links for amultimedia multiparty connection becomes a challenging research issue. To set up or modify connections in this environment, the requests expressed in terms of thesignalling protocol [Minzer 1991] will first be analyzed by the call processing elements in thenetworks to determine resource requirements, and then required resources will be allocated accordingto an efficient resource allocation algorithm. To implement the salient feature of the new signallingsystem, which hides the heterogeneity of the networks and physical interfaces of the users, specialresources such as signal converters or conference circuits may be added to the resource requirementsduring the resource analysis phase. The available special resources and the connecting links will thenbe located and reserved, and connections will be setup between the access interfaces of the involvedparties and the reserved resources. We propose a notation called logical connection to capture the resource requirements of acomplex multimedia multiparty connection. It is based on an augmented directed graph. It serves asan intermediate language for the call processing and is used to encode the result of the resourceanalysis phase for a user-network signalling request. The result of the resource analysis phasecontains additional information such as the location of the special resources and trunk groups used tosupport the connectivity. The notion of a multicast edge is introduced to enable the utilization of themulticast capability in broadband (or other) networks. Letus consider the RAMC problem in three different circumstances. First is the case where allthe resources and parties of a given logical connection are located in the same network. Although thiscase is the simplest one, the efficient allocation of resources could still be very difficult to achieve,since there may be many ways to allocate available special resources and the allocation sequence mayaffect the available bandwidth on the connecting links within the network. In the case wherebandwidth is heavily utilized, some allocation sequence may not be able to find enough bandwidth to3 of 23RAMCsatisfy the connectivity requirement of a given logical connection. It will be shown that the problem isNP-hard and no general polynomial solution can be found. The second case is that for which all the parties are