I. Traffic Modeling & link Allocation
- Traffic Modeling & Link Allocation
- Traffic Engineering for QoS in MPLS Networks
The final objective of this work is to provide a solution to the bandwidth allocation problem for Internet links on service provider core networks and high throughput metro networks. To solve the problem, we need validated statistical models for packet traffic on such links, packet arrival times and packet sizes, capable of generating synthetic packet traffic that reproduces the statistical properties of the live packet traffic.
We will couch the allocation problem
as follows. Suppose we have traffic whose bitrate is x mbps. What is the
lowest link speed in bits/sec that can attain specific quality of service
criteria. For example, suppose the criteria are a maximum delay in ms and
an allowable packet loss in percent of packets dropped. The traffic rate
divided by the minimum link speed is the QoS utilization. (We can also formulate
the problem as finding the minimum link speed in bits/sec that achieves the
criteria for a fixed traffic rate.)
The bandwidth allocation problem
has received wide attention in the network mathematics literature under widely
varying assumptions about the nature of the traffic. Much in the way of understanding
has resulted, but for Internet communications links, the problem has not
yet been solved. Here is the reason. The solution depends heavily on the
statistical characteristics of the packet traffic, the arrivals and sizes,
but there has not been so far a satisfactory model for the arrival-size process
that applies to a wide range of traffic rates, say 5 mbps and above. Without
an empirically-validated traffic model there can be no validated solution.
But recent results, both empirical and theoretical have set the stage for
just such a validated model.
A solution to the bandwidth allocation is critical to engineering the Internet in service provider core networks and high throughput metro networks. First, it is the most fundamental issue of traffic engineering: what is the maximum amount of traffic that can go on each of the links of a network and maintain QoS criteria. Such information is the input to path provisioning algorithms that optimize overall throughput, for example, the algorithm developed in Part II of this project. Second, it provides critical information for the fundamental architecture employed on core and metro networks.
In this project we will produce
a validated model and use it to solve the allocation problem.
Packet Traffic Modeling
We are developing new statistical
models for Internet packet traffic (arrivals and sizes); we call them FSD
models. To our knowledge, these are the first models that closely fit the
open-loop statistical properties of live arrivals and sizes for a wide range
of traffic rates, about 5 mbps and above in our case. We accomplished this
by drawing on the theory of marked point processes and by analyzing thousands
of traces from Internet links with speeds ranging from 100 mpbs to 2.5 gbps.
The FSD models depend on only a
few parameters that change with the traffic rate.We are now developing models
for the parameters as a function of the rate, so overall, our traffic models
are hierarchical.
An engineer wanting to use the models
to generate synthetic traffic for a study will need to specify only a traffic
rate. The rate can be specified as the number of simultaneous active connections,
the packet rate, or the bit rate. We will supply C code for the generation.
Bandwidth Allocation
We are carrying out now our study
of the bandwidth allocation problem for one set of QoS criteria.
We are doing an open-loop first-in,
first-out queueing simulation for live traces and for matching synthetic
traces from our FSD statistical models. For each trace we will set a link
utilization to a fraction u by feeding the trace into a first-in, first-out
queue with an output speed of 1/u times the bit rate of the trace, and with
an infinite buffer. We compute the queue height
at the time of arrival of each packet.
To study utilization, we fix a maximum
time delay for a packet in the queue, and we fix a packet loss. Here, we
use five values of max delay, d --- 1ms, 5 ms, 10 ms, and 100 ms --- and
3 loss rates, r --- 0.1%, 0.5%, and 1%. For each of the 15 combinations of
delay and loss, we find the utilization such that the percent of the queue-height
distribution greater than d is r. The achieved utilization is the QoS bandwidth.
Our study is open-loop, ignoring
the effect of TCP feedback. However, the open-loop study provides an adequate
approximation because we consider very small packet loss rates, so TCP feedback
is negligible. The small rates are consistent with a view of a core and metro
Internet architecture that loses very few packets. In effect, we suppose
the bottleneck link is elsewhere, a reasonable assumption for metro and core
networks.
Our use of a combination of synthetic
and live traces allows us to evaluate the suitability of the synthetic traces
in place of the live traces to study the bandwidth allocation problem. If
the live and synthetic results agree, we can use the models for traffic bit
rates higher than those of our live traces, which go up to about 300 mbps.
_________________________________________________________________________________________________________________
In the past, rapid growth in traffic demands over the Internet, together with big fluctuations, had led service providers to over-build their networks. There are several possible explanations, including a benign financial market and uncertainty in traffic projections. Going forward, conditions will be different: traffic growth is expected to be gradual and stable, financial markets will demand cost containment, customers will demand more differentiated and reliable services, and service providers will want to utilize their networks more efficiently. These conditions argue strongly for increased traffic engineering.
MultiProtocol Label Switching (MPLS) networks provide new capabilities for traffic engineering and QoS support. The explicit label-switched paths (LSPs) can be set up to follow certain routes and allocated certain capacity to meet required quality of service (QoS). To provide resiliency against link/node failures, protection LSPs can be setup to provide certain grades of protection. The basic MPLS traffic engineering capabilities, however, have not been fully taken advantages of. Our study show that routing LSPs based on variants of shortest path, as has been proposed in industry and academia, will be inefficient to meet increasing multi-service demands since these schemes do not provide the capabilities for global network optimization and load balancing. Our initial study show that considerable increase in network capacity and utilization and better control of QoS can potentially be achieved if routing and bandwidth allocations are based on careful network optimization. In addition, the cost of providing network resiliency can be optimized if protection plans are carefully integrated with traffic engineering design.
MPLS Traffic engineering and QoS support methods can be generally classified as offline or online methods, as described in the IETF traffic engineering working group framework document [IETF-TE], of which we are co-authors. In offline methods, routing, bandwidth allocation and protection plans for all or segments of the network are optimized to support demands for QoS and grade of protection. The traffic demand matrix can be obtained from customer subscriptions, historical information or measurements. The traffic demand volume supported depends on the quality of the solution of the optimization method. Offline methods can be complemented with online methods, where routing plans are adapted to the current state of the network in a relatively short time scale. Online methods have the benefit of information on variations in actual traffic (i.e., perturbations from regular variations due to link failures, concentrated traffic surges due to suddenly popular web sites, etc.) that cannot be predicted using historical information [IETF-TE]. One important example of online methods is adaptive load balancing, in which traffic is shifted away from failed or congested links and routed through a less congested segment of the network.
There have been major concerns in the networking community in the past about the difficulties of using methods similar to the above offline and online methods. The major concern about offline traffic engineering has been the computational cost associated with large optimization problems. These large multi-commodity flow problems typically arise at the network core, which interconnects many edge networks, and where MPLS is being deployed and traffic engineering is most beneficial. The major concerns about online methods are the stability and convergence of adaptive load balancing and the accuracy of real-time measurements.
In this research proposal we plan to provide a methodology for offline and online traffic engineering systems, and demonstrate their practical feasibility and performance benefits. We will bring to bear our expertise in solving large optimization problems, simulation methodology, traffic modeling, performance analysis and networking protocols.
Offline Traffic Engineering:
We have developed new methods for the fast solution of large optimization problems arising in traffic engineering of resilient multi-service MPLS core networks. These multi-commodity flow optimization methods are based on “epsilon approximations” that provide a trade-off between accuracy and speed. Most importantly, a small (epsilon) relaxation in accuracy leads to a vast reduction in the computational complexity. The allowed inaccuracy can be naturally tied to the required QoS; for example, to small loss probability that some services allow. Our initial experiments with large service provider network topology, supporting thousands of traffic demands of different bandwidth requirements, show that the capacity of the network based on our optimized routing solution is 30% greater than designs based on constrained shortest path routing (considered current state of the art.)
Our methods are being extended to provide joint optimization design of routing and resiliency. Protection LSPs are designed to provide various levels of protection. Shared protection, a method in which protection LSPs for different working LSPs share common links, can considerably reduce the cost of building resilient networks.
We plan to build a traffic engineering software system which will incorporate our optimization techniques. As QoS requirements are typically represented in terms of multiple parameters, the system will also make use of previously developed software for translating QoS requirements (e.g. loss and delay) into network requirements.
Online Adaptive Traffic Engineering:
For effective traffic engineering an offline traffic engineering system needs to be supplemented by an online system, which adapts the routing plans to the current state of the network on a relatively fast time scale. The current state of the network provides additional information on variations in actual traffic (i.e., perturbations from regular variations) that cannot be predicted using historical information [IETF-TE].
In our previous work, we proposed a state-dependent traffic engineering mechanism called Multipath Adaptive Traffic Engineering (MATE) [MATE]. MATE assumes that a system an offline system has already setup multiple LSPs between an ingress-egress pair. The multiple paths may be setup to provide load balance across the network or for routing diversity. The goal of the MATE ingress Label Switched Router (LSR) is to distribute the traffic across the LSPs so that the loads are balanced and congestion is minimized. The basic idea of MATE is as follows. The ingress LSR of each LSP periodically sends probe or router-alert packets to estimate a congestion measure on the forward LSP from ingress to egress LSRs. The congestion measure can be delay, loss rate, or other performance metrics. The ingress LSR then routes incoming traffic onto the available LSPs to the egress LSR in a way that equalizes the marginal congestion measure (their derivatives). That is, traffic will be shifted from LSPs with higher marginals to LSPs with lower marginals. Traffic shifting is done at the flow level, so as to minimize the reordering of out-of-sequence packets. In equilibrium all LSPs that carry any flow will have minimum and equal marginals of congestion measures. Some of the desired properties of our proposed system include:
To this end, we have developed an analytical model, derived a class of MATE algorithms, and proved their convergence. We have only performed a limited amount of experiments with fixed topology in the previous work.
- distributed adaptive load-balancing algorithm,
- end-to-end control between ingress and egress nodes,
- no new hardware or protocol requirement in intermediate nodes,
- no knowledge of traffic demand is required,
- no assumption on the scheduling or buffer management schemes at a node,
- optimization decision based on path congestion measure,
- minimal packet reordering, and
- no clock synchronization between two nodes.
We intend to leverage our previous results in several directions. In the near term, we intend to build a comprehensive simulation platform that is capable of dealing with (1) very high-speed networks, (2) arbitrary and complex topologies, (3) several advanced measurement techniques based on router alert and probing, (4) packet hashing and (5) real traffic traces. Some innovative claims include bootstrap technique to determine the optimal number of probes that is required, new usage of router alert packets which is intended to be extensible for future advanced measurement requirements, and load balancing in the presence of multiple classes of service..
We will also explore extensions on the theoretical front with respect to different QoS classes and different resiliency requirements. In the longer term (not part of this project), our intention is to construct an MPLS test-bed controlled by MATE.
The project deliverables (presentations, publications, code etc.) are listed here.
Point-of-Contact: Bill Cleveland, wsc@research.bell-labs.com
, Ph: 908-582-6861
Anwar Walid, anwar@research.bell-labs.com
, Ph: 908-582-7589
Admin Point-of-Contact: Bill Cleveland,wsc@research.bell-labs.com
, Ph: 908-582-6861
Last modified: July. 28, 2003, by Karun (karun@research.bell-labs.com)