Routing and capacity allocation in networks with trunk reservation

F.P. Kelly

Mathematics of Operations Research 15 (1990) 771-793


In this paper we extend recent work on routing and capacity allocation in circuit-switched networks to include the possible use of trunk reservation. Trunk reservation is an easily implemented control mechanism which allows priority to be given to chosen traffic streams. It has the potential to be an extremely efficient control mechanism, but its use on any single link of a network has ramifications which may extend throughout the network, and it is important to take this into account. Using a simplified analytical model of a circuit-switched network incorporating trunk reservation, we show that there exist implied costs associated with the priority and nonpriority calls routed through a link, and shadow prices associated with the capacity for priority and nonpriority traffic through a link. Mathematically, this involves calculating derivatives of an implicitly defined function, and expressing these derivatives as simple functions of certain variables. These variables, the implied costs and shadow prices, are determined as solutions to a set of linear equations possessing a local or decentralized character, and can be used as a basis for routing and capacity allocation strategies.

AMS 1980 subject classification. Primary: 90B15. Secondary: 60K30.

IAOR 1973 subject classification. Main: Allocation/Resources. Cross references: Networks/Communications.

OR/MS Index 1978 subject classification. Primary: 489 Networks/Theory.

Key words. Network flow, alternate routing, dynamic routing, fixed point approximation, optimization, implied cost.


Frank Kelly's papers