The design of a routing protocol must be based on the characteristics of its target networks. The diversity of wireless networks motivates the design of different routing metrics, capturing different aspects of wireless communications. The design of routing metrics, however, is not arbitrary since it has a great impact on the proper operation of routing protocols. Combining a wrong type of routing metrics with a routing protocol may result in routing loops and suboptimal paths. We thoroughly study the relationship between routing metrics and routing protocols. Our work provides important guidelines for designing routing metrics and identifies the specific properties that a routing metric must have in order to be combined with certain type of routing protocols.

This paper presents a theoretical study on distributed contention window control algorithms for achieving arbitrary bandwidth allocation policies and efficient channel utilization. By modeling different bandwidth allocation policies as an optimal contention window assignment problem, we design a general and fully distributed contention window control algorithm, called GCA (general contention window adaptation), and prove that it converges to the solution of the contention window assignment problem. By examining the stability of GCA, we identify the optimal stable point that maximizes channel utilization and provide solutions to control the stable point of GCA near the optimal point. Due to the generality of GCA, our work provides a theoretical foundation to analyze existing and design new contention window control algorithms.

To enable end-to-end quality-of-service (QoS) guarantees in the Internet, based on the border gateway protocol (BGP), interdomain QoS information advertising, and routing are important. However, little research has been done in this area so far. Two major challenges, scalability and heterogeneity, make the QoS extension to BGP difficult. In the existing routing schemes, static and instantaneous QoS metrics, such as link capacity and available bandwidth, are used to represent QoS routing information, but neither of them can solve the two challenges well. In this paper, BGP is extended to advertise available bandwidth and delay information of routes, but, instead of using the traditional deterministic metrics, a series of statistical metrics, available bandwidth index (ABI), delay index (DI), available bandwidth histogram (ABH), and delay histogram (DH), are defined and applied to QoS information advertising and routing. Two major contributions of the proposed statistical metrics are: 1) QoS information is abstracted into one or several probability intervals and, thus, the heterogeneous and dynamic QoS information can be represented more flexibly and precisely and 2) by capturing the statistical property of the detailed distribution of QoS information, these new metrics are efficient and they can highly decrease the message overhead in routing, thereby making the QoS advertising and routing scalable. Our extensive simulations confirm both contributions of the QoS extension to BGP very well. Moreover, besides BGP, these statistical metrics can be applied to other networks and protocols to represent QoS information in a more scalable and precise way.

When supporting source-specific heterogeneous-receiver multimedia applications, a multicast tree is built among a source and the receivers such that the path from the source to each receiver satisfies the delay and bandwidth constraints. To optimize the network usage, it is desirable to find a multicast tree that minimizes the total bandwidth used while satisfying the different delay and bandwidth requirements of the receivers. For scalability reasons, the desired protocol should require little or minimum storage in the sender and other on-tree routers. Moreover, to allow dynamic member joining or leaving, a receiver-initiated approach is more appropriate. We describe our receiver-initiated QoS multicast protocol that aims at reducing the bandwidth used in building a multicast tree for heterogeneous receivers by actively identifying better sub-optimal paths. Our protocol does not require additional information to be stored in the on-tree routers, and it is able to construct a better sub-optimal tree than existing protocols.

When supporting source-specific heterogeneous-receiver multimedia applications, a multicast tree is built among a source and the receivers such that the path from the source to each receiver satisfies the delay and bandwidth constraints. To optimize the network usage, it is desirable to find a multicast tree that minimizes the total bandwidth used while satisfying the different delay and bandwidth requirements of the receivers. For scalability reason, the desired protocol should require little or minimum storage in the sender and other on-tree routers. Moreover, to allow dynamic member join or leave, a receiver-initiated approach is more appropriate. In this paper, we describe our receiver-initiated QoS multicast protocol that aims at reducing the bandwidth used in building a multicast tree for heterogeneous receivers by actively identifying better sub-optimal paths. Our protocol does not require additional information to be stored in the on-tree routers, and it is able to construct a better sub-optimal tree than existing protocols.

This paper studies the problem of finding optimal routes for premium class traffic in the DiffServ network such that (1) loop-freedom is guaranteed in the entire network under hop-by-hop routing assumption; and (2) the maximum relative congestion among all links is minimized. This problem is called the extended optimal premium routing (eOPR) problem, which is proven to be NP-hard. We use the integer programming method to mathematically formulate the eOPR problem and find the optimal solutions for small scale networks. we also study heuristic algorithms in order to handle large scale networks. Simulation results are compared to handle large scale networks. Simulation results are compared with the optimal solutions obtained by solving the integer programming models. The results show that the bandwidth-inversion shortest path (BSP) algorithm can be a good candidate to route premium traffic in DiffServ networks.

In the conventional internal border gateway protocol (IBGO), the BGP sessions between all BGP speakers in a single autonomous system (AS) form a full mesh. For scalability reasons, route reflection is proposed as an alternative to the full mesh inside an AS. The selection of route reflectors and their clients determines the path used by IGBP route advertising. Thus, the design of the route reflection graph is an important issue for improving IBGP operating efficiency and reliability. This paper focuses on the topology optimization for the route reflection graph, i.e., the selection of the reflectors and the interconnections between reflectors and clients. We propose the optimum reflection graph (ORG) problem to find the best topology for IBGP reflection according to the efficiency or reliability metrics. We give the solvability conditions for the problem and present solution based on the integer programming model. Our approach is also highly flexible. Human decisions or constraints can be easily incorporated to find a topology which satisfies AS administrator's manual configurations.

In the internal border gateway protocol (IBGP), route reflection is widely used as an alternative to full mesh IBGP sessions inside an AS for scalability reason. However, some important issues, such as the impact of route reflection on the reliability of IBGP and the construction of reliable reflection topology with unreliable routers or links, have not been well investigated. This paper addresses the problem of finding reliable route reflection topologies for IBGP networks, which is of great importance to increase the robustness of IBGP operations. We first present a novel reliability model and two new metrics (IBGP expected lifetime and expected session loss) to evaluate the reliability of reflection topologies, and further to investigate the design problem. After studying the solvability conditions under the router capacity constraints, we prove the NP-hardness of the problem, and then design and implement three heuristic solutions using randomization techniques: heuristic selection, greedy search and simulated annealing. Our extensive computational experiments show that the reliability of IBGP reflection network can be significantly improved by our solutions.

The delay-constrained least-cost routing problem is to find the least cost path which satisfies a given delay constraint. There are two major difficulties to solve in this problem. The first difficulty is the NP-completeness of this routing problem. The second difficulty is that the networking information used for routing may be imprecise. The ticket-based routing (TBR) algorithm, aiming to find a sub-optimal solution, provides a heuristic approach to overcome the above difficulties and solve the routing problem. Although TBR proposes a detailed ticket forwarding method based on imprecise end-to-end information, it does not optimize the ticket probing process so as to find better paths. This paper proposes an enhanced ticket-based routing (ETBR) algorithm. The ETBR improves the effectiveness of ticket probing by two techniques. The first technique uses color-based ticket distribution for tickets of different colors. The tracing information of green tickets and yellow tickets is kept separately to avoid unnecessary ticket dropping. The second technique uses historical probing results to optimize ticket probing, so that redundant probing paths are eliminated. Through extensive simulations, we demonstrate that the ETBR can find paths which have much lower cost than TBR, without decreasing the success ratio or increasing the message overhead.

To enable the end-to-end quality of service (QoS) guarantees in the Internet, based on the border gateway protocol (BGP), inter-domain QoS advertising and routing are important. However, little research has been done in this area so far. Two major challenges, scalability and heterogeneity, make the QoS extension to BGP difficult. Two existing approaches, link capacity routing (LCR) and available bandwidth routing (ABR), address QoS advertising and routing in BGP with respect to the bandwidth metric, but neither of them can solve the two challenges well. We extend BGP to advertise bandwidth information, but, instead of using link capacities or instantaneous available bandwidth values, a novel QoS metric, available bandwidth index (ABI), is defined and used to perform bandwidth advertising and routing. The two major contributions of ABI are: (1) ABI dynamically abstracts available bandwidth into a probability interval, therefore, it is very flexible to represent heterogenous and dynamic bandwidth values; (2) by capturing the statistical property of the detailed available bandwidth distribution, ABI is so efficient that it can highly decrease the message overhead in routing, thereby making the QoS advertising and routing very scalable. Our extensive simulations confirm both contributions of the ABI extension to BGP very well.

For the provision of quality of service (QoS) in the Internet, differentiated service (DiffServ) has been proposed as a cost-effective solution. Traffic is classified into several service classes with different priorities, premium class traffic being the highest. The routing algorithm used by the premium class service has significant effects on the traffic of all other classes as well as its own. Shortest hop-count routing used in the current Internet is no longer sufficient in DiffServ networks. Based on hop-by-hop routing, an optimal routing algorithm must be found for premium class traffic such that (1) it works correctly and efficiently for premium traffic; (2) it reduces negative influences (such as bandwidth starvation, excessive delay jitter, etc.) to other traffic classes. This problem, the optimal premium-class routing (OPR) problem, is NP-complete. To handle the OPR problem, first, we analyze the strength and weaknesses of two existing algorithms (widest-shortest-path algorithm and bandwidth-inversion shortest-path algorithm). Second, we apply to the OPR problem a novel heuristic algorithm, called the enhanced bandwidth-inversion shortest-path (EBSP) algorithm. We prove theoretically the correctness of the EBSP algorithm, i.e., it is a consistent and loop-free hop-by-hop routing algorithm. Our extensive simulations in different network environments show clearly that the EBSP algorithm performs better for premium class traffic in complex, heterogeneous networks than the other two hop-by-hop routing algorithms.

With up-coming quality of service (QoS) requirements raised by a wide range of communication-intensive, real-time multimedia applications, resource reservation is one of the approaches to satisfy requested QoS. The Resource ReSerVation Protocol (RSVP) is a well-known signaling protocol for bandwidth reservation in the Internet. However, the current reservation protocols like RSVP do not present the maximum flow acceptance rate solution. The problem of finding the maximum reserved flow acceptance rate and minimizing the effects of crank-back procedure is called the New Killer Reservation Problem (NKR). We study the NKR problem and answer two questions: (1) under what scenarios does the NKR problem become a serious problem; and (2) how can we solve this problem. We introduce the marginable bandwidth reservation protocol (MBR) as a solution to the NKR problem. The results show that MBR protocol yields the desired improvement of the flow acceptance rate at a low cost.