Joint Traffic Engineering for IP over WDM Networks
Jinhan Song and Saewoong Bahk
School of Electrical Engineering, SeoulNationalUniversity, Seoul, Korea
The architecture of next generation high speed networks is expected to consist of IP and WDM layers. IP layer runs packet switching while WDM layer uses circuit switching. While they have the similar goal of efficient use of network resources, they lack harmony due to different traffic engineering capabilities. To this end, we introduce a combined cost to quantitatively analyze the effectiveness of traffic engineering for the two layers. First, we model an edge router and devise a traffic engineering mechanism to minimize the combined cost over a single path. We show that both the explicit price which characterizes the traffic engineering cost, and the implicit price which determines the network congestion cost, play a key role in wavelength allocation. We consider wavelength granularity that significantly affects overall performance when the number of wavelengths in a link is small. To solve this granularity problem we propose an approximation algorithm that finds an integer solution from the real solution. Through simulations, we verify that our proposed algorithm achieves near-optimal performance with greatly reduced complexity and guarantees the feasibility of solutions.
OCIS codes:060.4250
1. Introduction
The universality of IP (Internet Protocol) places the Internet at the core of network convergence. As Internet traffic volume increases explosively, WDM (Wavelength Division Multiplexing) is spotlighted as the first and foremost candidate to meet the bandwidth demand since it increases the network capacity by orders of magnitude. As a consequence, IP over WDM is expected to be the dominant architecture in future Internet backbone networks.Fig. 1 shows the IP over WDM network architecture considered in the IPO WG (IP over Optical Working Group) of the IETF (Internet Engineering Task Force) [1], [2]. Router networks use optical subnetworks as a means for transporting data. So the router networks set up lightpaths for communications across optical networks. A lightpath works like a circuit formed by cascading multiple wavelength channels.
Traffic engineering is concerned with “performance optimization of operational networks” [5]. In the IP layer, it is necessary to overcome the limitations of current IP routing protocols, which typically select a shortest path, i.e., minimum-hop path and often produce hot spots [5]. To avoid these limitations, traffic engineering tries to use diverse routes based on metrics other than hop count and distributes the traffic load throughout the network. Explicit routing implemented in MPLS (Multi Protocol Label Switching) seems a viable solution to this end and MPS (Multi Protocol Lambda Switching) is an approach to introduce MPLS into the optical domain [6]. In the WDM layer, the need for traffic engineering capability grows as the number of wavelengths available increases. By using the greatly increased wavelengths in number, we can allocate multiple wavelengths for a lightpath or form a virtual topology with denser connectivity.Typical traffic engineering methods include virtual topology construction, traffic grooming, and dynamic RWA (Routing and Wavelength Assignment) [3], [4].
A natural question arises as to whether existing traffic engineering techniques for IP over WDM networks accomplish their goals as desired. The use of contradictory assumptions by the various methods presents a problem. In IP traffic engineering, it is usually assumed that the topology is predetermined and given.In WDM traffic engineering such as RWA, lightpaths are given as a part of the input.Hence, before IP and WDM traffic engineering techniques are applied, the set of lightpaths is determined in advance.The lightpath determination is the core of the joint traffic engineering and deals with the problems of 1) decidingthe number of allocated wavelengths for eachlightpath and 2) selecting the set oflightpaths among the feasible ones. Specifically, we focus on the former one, computing the optimal number of wavelengths for each lightpath by considering the combined costs of the two layers.The latter can be classified as aproblem of virtual topology construction which will be addressedin a separate paper.
Our joint traffic engineering framework for IP over WDM networks starts with characterizing and modeling an IP over WDM network. Then we define an objective function considering both IP and WDM layers, i.e., their combined cost. Our motivation of using the combined cost comes from the contradictory objectives of IP and WDM layers though they have the same design goals of efficient use of network resource such as minimizing the network configuration cost and maximizing profit. The combined cost is represented as the sum of the costs incurred by the two layers to transport a given traffic. We present a mathematical formulation for a general case and provide its solution. In our previous work, we obtained some basic results on this topic [7], [8]. However, the analysis was for a simple system model and the formulation was confined to a single hop network. In this paper, we complete our work to deal with general multi hop networks, and explore previously uncovered aspects of traffic engineering for IP over WDM networks.
The rest of the paper is organized as follows. We present the basis for the quantitative analysis in Section 2, and provide the formulation and its solution. We describe and explicate the properties of the multi-hop model defined in Section 3. We discuss granularity issues in Section 4, followed by concluding remarks in Section 5.
2. Combined Cost Concept
In an IP over WDM network, the IP layer runs on top of the WDM layer. To model this network, we start by characterizing both layers. We present a model of an edge router in router networks that interfaces with optical networks. Then, we introduce the combined cost concept.
2.A. IP and WDM layers
The IP network uses packet switching and generates elastic traffic, which adapts to the network state and often results in the burst of IP packets. In contrast, the WDM network employs circuit switching to form lightpaths that consist of one or more wavelengths. As wavelengths are allocated in integer units, there arisesa granularity problem. In this paper, we assume that wavelength conversion is possible at each node.
2.B. Edge routers
An edge router is placed in router networks and interfaces with optical networks. It is equipped with signaling capability and an IP and WDM protocol stack. Through the signaling protocol, it requests the setup and release of a lightpath. Before doing this, it calculates the number of wavelengths that are needed. We will deal with the decision process in the next section.
Fig. 2 shows the structure of the edge router where is the packet arrival rate and is the average packet service rate which is the inverse of unit transmission speed of a wavelength. When a packet arrives at the edge router, the Classifier examines the packet header and determines the session it belongs to. We will use the term “session” to refer to a lightpath between a source-destination edge router pair. As a lightpath can require multiple wavelengths, the Distributor determines which wavelength to use for forwarding the incoming packet. Depending on the distribution algorithm, the wavelength selection may be different.
In Fig. 2, session 1 identified by forwarding equivalence class (FEC) 1 uses two wavelengths (k=2). The distribution algorithm chooses one of these two for forwarding each packet for FEC 1. Session N does not need a distribution algorithm for wavelength selection because it has only one wavelength (k=1). We consider two distribution algorithms:randomization and metering [9]. While the randomization algorithm distributes an incoming packet over the allocated wavelengths for the corresponding session in a random manner, the metering algorithm directs an incoming packet to the wavelength with the least queue length. The queues shown in Fig. 2 store incoming packets to convert their format for the optical network. The packets are then transmitted over the allocated wavelengths. Our considered distribution algorithms cannot guarantee in-order delivery, so end-hosts need to execute the reordering process. If in-order packet delivery is in need, we have to adopt some other distribution algorithms such as 802.3ad link aggregation algorithm. The purpose of our work is in providing a framework for traffic engineering which can be modeled simply, instead of designing a detailed traffic engineeringalgorithm.
We can view IP traffic engineering as a modulation mechanism of incoming packets that selectsan appropriate delivery route, and WDM traffic engineering as a control scheme of the total service rate that adjusts the number of allocated wavelengths. For ease of analysis, we fix the total packet arrival rate, and manipulate only the number of wavelengths allocated by WDM traffic engineering. To determine the number of allocated wavelengths, we need to consider a couple of factors. First, more wavelengths are required for bursty traffic than for smooth traffic since bursty traffic experiences higher packet loss. Second, the resource allocation process should be fair and efficient. To quantitatively analyze the costs involved in the decision process, we propose a combined cost next.
2.C. Combined cost
Both the IP and WDM layers have their own traffic engineering algorithms and corresponding goals. A natural question is how to harmonize them. We can achieve our goal by minimizing the detrimental interference between the independent but functionally overlapping capabilities of the two layers. Therefore our previous work proposed the notion of a combined cost that quantifies the costs at both layers for transporting user traffic [7], [8].
The cost in the IP layer increases as the queue builds up. This is because delay and loss probability of packets increase as the queue grows. The cost in the WDM layer can be characterized by the number of allocated wavelengths since the wavelength is a premium commodity. So we define the combined cost as the sum of the costs in the IP layer and in the WDM layer laid out to handle the given traffic. We represent the combined cost C as
,(1)
where is the number of buffered packets, is the number of allocated wavelengths ,is the unit price per buffered packet and is the unit price per allocated wavelength. and have different scales and they are consolidated by using and thatarereferredas the explicit prices. This motivated us to introduce the cost concept.
The price in the IP layer is proportional to the queue length and the price in the WDM layer is proportional to the number of allocated wavelengths. These quantities influence each other since the queue length closely depends on the number of allocated wavelengths. In particular, they exhibit a tradeoff relationship. That is, given the explicit price, decreasing results in an increase of , and increasing (i.e., allowing larger) in smaller . This is an intuitive relationship which will be explained next.
2.D. Analytic modeling
Different distribution algorithms result in different queue behaviors. To model the bursty nature of IP traffic, we use a bulk arrival model, [10]. B is the bulk size and characterizes the burstiness of traffic. The larger B implies the burstier traffic.
The system that employs randomization is equivalent to k independent queues [9]. When k wavelengths are allocated for a session with the offered load r, each wavelength is responsible for serving the offered load of . Assuming an exponentially distributed service time, the average queue length is given by . The total number of buffered packets for a session is . With , we get the combined cost . It can be easily shown that the combined cost has the global minimum at where .
p determines which layer plays the key role in handling the traffic. By varying p, we can check the tradeoff relation between IP and WDM layers. The system with metering is equivalent to a queue with k servers. To simplify the analysis, we approximate this to a queue with a server of k times the unit speed. The approximation is valid since we can observe that the number of wavelengths minimizing the combined cost in the approximated and the original models are about the same [9]. Table 1 summarizes the analytic results. As B increases, the minimum combined cost and the number of required wavelengths also increase as expected. Engineering the bursty traffic requires more resources and higher cost.
2.E. Total combined cost
Now we extend the above definition for multiple sessions to represent the sum of individual combined costs of all the sessions in the network. Assuming that the individual combined costs are summable, we write the total cost as follows.
.(2)
is the combined cost for session f and F is the set of all the sessions under consideration.
3. Minimization of the total combined cost
Minimizing the total combined cost is not so simple because some session requests may be blocked due to limited network capacity. Some other sessions may not receive as many wavelengths as they request. In this case, wavelengths should be shared among the sessions. Here we solve the problem of determining the number of wavelengths to minimize the total combined cost. We assume that the wavelength conversion is possible at each node.
3.A. Formulation
We formulate the problem of finding the optimal number of wavelengths by minimizing the total combined cost. It is given as follows.
Objective
Minimize (3)
Subject to
for all links ,(4)
for all sessions,(5)
: integer,(6)
: constant.(7)
L is the set of optical links, is the set of sessions that pass link l and is the number of wavelengths on link l. We assume that the load offered to session f is given and normalized by the transmission rate of a wavelength. (4) states that the sum of allocated wavelengths for each session, , should not exceed the number of wavelengths of each link. (5) means that should exceed for stability. This constraint prevents the cost of IP layer from diverging to infinity. (6) and (7) state that is an integer number and that the explicit prices are constant .
As the objective function is nonlinear, we need to apply nonlinear programming techniques. Since nonlinear programming with integer constraints is computationally hard, we ignore the integer constraints for the time being. Without the integer constraints, the number of allocated wavelengths becomes a positive real variable.and are the functions depending on . To find the solution, we first derive the dual version of the problem, and then apply the Kuhn Tucker theorem and the gradient projection technique [9], [11]. The resulting iterative equations are as follows.
<Gradient Projection
for every ,
(8)
.(9)
<Kuhn Tucker condition>
for every,
(10)
.(11)
GP (Gradient Projection) decides the feedback information from the optical links and the KT (Kuhn Tucker) condition determines the behavior at edge routers [11]. (8) and (9) are obtained by applying the gradient projection method to the dual form of the original formulation. In (8) and (9), is the Lagrange multiplier, is the step size, and is the objective function of the dual formulation. (8) and (9) describe the procedures to update the Lagrange multiplier from the given wavelength allocations, ’s. In (10), is the set of links that a given session f passes through, and is the sum of the Lagrange multipliers for those links. The Lagrange multiplier is positive if the constraint is active, i.e., equality holds in (4). If the constraint is inactive, or the strong inequality holds, the Lagrange multiplier is zero. This means that as the link is congested and becomes a bottleneck, the Lagrange multiplier value increases. This property of the Lagrange multiplier makes it translatable as price [12][13]. (11) shows that , the sum of the Lagrange multipliers for bottleneck links, determines the number of allocated wavelengths. We call the implicit price. The implicit price and the explicit price are closely related. To investigate this relation, we consider a session f and apply partial derivation to (2),
.(12)
From the KT condition (11)
.(13)
Combining the above yields,
.(14)
(14)states that the number of allocated wavelengths is determined by the sum of the explicit price of the WDM layer and the implicit price scaled by the explicit price of the IP layer. The implicit price as well as the explicit price significantly influences wavelength allocation.
Now we discuss the implications and properties of these prices. First, the implicit price is compatible with the explicit price and they have the same unit. An increase in the implicit price is equivalent to an increase in or the wavelength price. Thus increase in the implicit price discourages wavelength allocation.
Second, increase in the implicit price causes increase of the IP layer cost and less wavelength allocation, resulting in more buffer usage. The implicit price is not the actual wavelength price but reflects the relative wavelength value, so it is not directly included in the calculation of WDM layer cost.
Third, the implicit price reflects network congestion. As stated before, the Lagrange multiplier of a link is positive when wavelength requests to the link exceed the link capacity. Thus the positive Lagrange multiplier indicates that the link is congested. The session with the positive implicit price goes through some congested links.
Fourth, the implicit price represents social penalty. As a session that passes through more congested links causes even more congestion of the network, it is given a higher implicit price which discourages the wavelength allocation. The session passing through congested links will get the penalty of fewer wavelengths.
Fifth, the implicit price conforms to the economic law of demand, stating that an increase in price results in a decrease of demand. This applies to the case of the implicit price.
Sixth, the implicit price enforces fairness. As wavelengths are still a scarce resource, they need to be shared among sessions. From (14), we see that the implicit price encourages link sharing. Sessions that pass through a certain congested link have the same Lagrange multiplier. We call this “the price fairness.”