Extensive studies have shown that the peer-to-peer (P2P) traffic has already become the dominant traffic in the current Internet. The current P2P streaming user base is still undergoing stunning growth in China although its user scale already reached 158 million in 2010, 68% of Chinese web users. Hence, a comprehensive understanding of the P2P streaming network traffic characterization is essential to Internet Service Providers (ISPs) in terms of network planning and resource allocation. In this paper, based on the massive data collected with a passive network monitoring equipment placed in the Internet backbone, we provide an in-depth view of the current P2P streaming traffic in the current Internet of China. In particular, we statistically study the P2P streaming traffic in both wired (ADSL in this paper) and wireless (CDMA) networks, and characterize the traffic from both flow-level and packet-level aspects. Our study uncovers the significant impact of the P2P streaming traffic on the underlying network due to its unique characteristics and the bandwidth intensive nature of the corresponding applications. In addition, the result reveals the significant difference between the characterizations of the P2P streaming traffic in wired and wireless networks due to their respective intrinsic environmental characteristics.

Network traffic monitoring and traffic characterization are essential for network management and optimization. Extensive researches have been conducted in the past to characterize the network traffic. However, due to the increasing number of ADSL and CDMA users and the rapid development of new services in China, the results are out-of-dated and a deep understanding of the traffic pattern in both networks is required. In this paper, we analyze the traffic trace collected from both ADSL and CDMA network from the perspective of protocol distributions, flow-level metrics as well as distinct traffic characteristics caused by user preferences and new services. These discoveries could be used by the ISPs to optimize their network performance and to provide satisfactory Quality of Service (QoS) to users.

Few works have been reported to address the issue of updating link state information in order to effectively facilitate quality-of-service (QoS) routing. The idea of modeling the QoS link state information as random variables has been reported, but none of the existing works have provided a comprehensive probabilistic approach to link state update that takes the probability density functions of both the user's QoS requirements and the network's QoS measurements into account. We propose the routing-oriented update scheme (ROSE) that utilizes the knowledge of the history of network operations and user's QoS requirements to improve the efficiency of link state update without increasing the network overhead. ROSE is a new class-based link state update scheme which intelligently determines class sizes to minimize the impact of inaccurate link state information. Through theoretical analysis and extensive simulations, we demonstrate that ROSE outperforms other class- based link state update policies.

Many works have been reported to address the issue of updating link state information in order to effectively facilitate Quality-of-Service (QoS) routing. However, most of them, if not all, only consider concave metrics, e.g., bandwidth. In this paper, we first observe that due to the inherently different nature of additive and concave QoS metrics, directly applying existing link state update policies cannot provide satisfactory performance. As such, it is essential to consider the additive metrics of link state update for the purpose of reducing the protocol overhead and improving the accuracy of link state information. By applying the central limit theorem, the additive QoS constraint imposed on each link can be modeled as a normal random variable. Then, based on our previous proposal, ROSE, we present a high performance link state update policy, ROSE II. Via theoretical analysis and extensive simulations, we show that ROSE II greatly outperforms the state of the arts in terms of protocol overhead and the accuracy of the link state information for additive metrics.

Finding a least-cost path subject to a delay constraint in a network is an NP-complete problem and has been extensively studied. Many works reported in the literature tackle this problem by using /spl epsiv/-approximation schemes and scaling techniques, i.e., by mapping link costs into integers or at least discrete numbers, a solution which satisfies the delay constraint and has a cost within a factor of the optimal one, that can be computed with pseudopolynomial computational complexity. In this paper, having observed that the computational complexities of the /spl epsiv/-approximation algorithms using the linear scaling technique are linearly proportional to the linear scaling factor, we investigate the issue of finding the optimal (the smallest) linear scaling factor to reduce the computational complexities, and propose two algorithms, the optimal linear scaling algorithm (OLSA) and the transformed OLSA. We analytically show that the computational complexities of our proposed algorithms are very low, as compared with those of /spl epsiv/-approximation algorithms. Therefore, incorporating the two algorithms can enhance the /spl epsiv/-approximation algorithms by granting them a practically important capability: self-adaptively picking the optimal linear scaling factors in different networks. As such, /spl epsiv/-approximation algorithms become more flexible and efficient.

Core-stateless scheduling algorithms have been proposed in the literature to overcome the scalability problem of the stateful approach. Instead of maintaining per-How information or performing per-packet How classification at core routers, packets are scheduled according to the information (time stamps) carried in their headers. They can hence provision quality of service (QoS) and achieve high scalability. In this paper, which came from our observation that it is more convenient to evaluate a packet's delay in a core-stateless network with reference to its time stamp than to the real time, we propose a new traffic model and derive its properties. Based on this model, a novel time-stamp encoding scheme, which is theoretically proven to be able to minimize the end-to-end worst case delay in a core-stateless network, is presented. With our proposed traffic model, performance analysis in core-stateless networks becomes straightforward.

In this paper, we show that routing without considering the staleness of link state information introduced by update policies may generate significant percentage of false routing. Hence, we introduce and investigate the issue of minimizing the impact of stale link state information on the performance of QoS routing without stochastic link state knowledge. Under the assumption that trigger-based link state policies are adopted for updating link state information, we theoretically decouple the problem of finding the most probable feasible path (without link state stochastic knowledge) to the problems of finding the multiple additively constrained path (MACP) and finding the least cost multiple additively constrained path (LCMACP), respectively, and propose a framework for minimizing the impact of stale link state information on the performance of QoS routing. We show by theoretical analysis and extensive simulations that our proposed framework is effective in minimizing the undesirable effect of the staleness of link state information.

Many works reported in the literature tackle the problem of delay constrained least cost path selection (DCLC) by using /spl epsi/-approximation schemes and scaling techniques, i.e., by mapping link costs into integers or, at least, discrete numbers, a solution that satisfies the delay constraint and has a cost within a factor of (1 + /spl epsi/) of the optimal one can be computed with pseudo polynomial computational complexity. In this paper, having observed that the computational complexities of the /spl epsi/-approximation algorithms using the linear scaling technique are linearly proportional to the linear scaling factors, we investigate the issue of finding the optimal (the smallest) linear scaling factor to reduce the computational complexities and propose a theoretical framework.

We introduce an iterative all hops k-shortest paths (IAHKP) algorithm that is capable of iteratively computing all hops k-shortest path (AHKP) from a source to a destination. Based on IAHKP, a high performance algorithm, dual iterative all hops k-shortest paths (DIAHKP) algorithm, is proposed. It can achieve 100% success ratio in finding the delay constrained least cost (DCLC) path with very low average computational complexity. The underlying concept is that since DIAHKP is a k-shortest-paths-based solution to DCLC, implying that its computational complexity increases with k, we can minimize its computational complexity by adaptively minimizing k, while achieving 100% success ratio in finding the optimal feasible path. Through extensive analysis and simulations, we show that DIAHKP is highly effective and flexible. By setting a very small upper bound to k (k=1,2), DIAHKP still can achieve very satisfactory performance. With only an average computational complexity of twice that of the standard Bellman-Ford algorithm, DIAHKP achieves 100% success ratio in finding the optimal feasible path in the typical 32-node network.

Proportional fair queuing is to ensure that a flow passing through the network only consumes a fair share of the network resource that is proportional to its committed rate or other service level agreement (SLA). It is of great importance in Differentiated Services (DiffServ) networks as well as other price incentive network services. In this paper, we propose a simple core-stateless proportional fair queuing algorithm (CSPFQ) for the assured forward (AF) traffic in DiffServ networks. We first develop our algorithm based on a fluid model analysis and then extend it to a realizable packet level algorithm. We prove analytically and instantiate through simulations that our algorithm can achieve proportional fair bandwidth allocation among competing flows without requiring routers to estimate flows' fair share rates. Our simulation results also demonstrate that our algorithm outperforms the weighted core-stateless fair queuing (WC-SFQ) in terms of proportional fairness.

We investigate the problem of finding the delay constrained least cost path (DCLC) in a network, which is NP-complete and has been extensively studied. Many proposed algorithms tackle this problem by transforming it into the shortest path selection problem or the k-shortest paths selection problem, which are NP-complete, with an integrated weight function that maps the delay and cost for each link into a single weight. However, they suffer from either high computational complexity or low success ratio in finding the optimal paths (the least cost path satisfying a given delay constraint). Based on the extended Bellman-Ford (EB) algorithm, we propose a high performance algorithm, dual extended Bellman-Ford (DEB) algorithm, which achieves a high success ratio in finding the least cost path subject to a delay constraint with low computational complexity. Extensive simulations show that DEB outperforms its contender on: the worst-case computational complexity; average cost of the solutions; the success ratio in finding the delay constrained least cost path.

Core-stateless scheduling algorithms can provide a similar level of guaranteed services as the stateful approach, while they do not need per-flow management. They hence possess both the properties of quality-of-service (QoS) provisioning and high scalability. In this paper, by showing the current existing traffic models are not applicable to core-stateless networks, a new and efficient traffic model for characterizing traffic in a core-stateless network is proposed, and its properties are presented.

Finding a feasible path subject to multiple constraints in a network is an NP-complete problem and has been extensively studied. Many proposed source routing algorithms tackle this problem by transforming it into the shortest path selection problem, which is P-complete, with an integrated cost function that maps the multi-constraints of each link into a single cost. However, how to select an appropriate cost function is an important issue that has a rarely been addressed in literature. In this paper, we provide a theoretical framework for picking a cost function that can improve the performance of source routing in terms of complexity, convergence, and probability of finding a feasible path.

We present features of next generation SONET, focusing particularly on path management. Factors such as QoS metrics and path protection are keys to realize automatic and dynamic path management. Two algorithms (the sequential algorithm and the parallel algorithm) to provide QoS and protection path in SONET are proposed and discussed in detail. They balance the network load by circumventing heavily loaded links, and reduce the network resource consumption by selecting the shortest paths. Simulation results demonstrate that they are practical solutions for path management of next generation SONET.