Article Preview
TopIntroduction
In recent years, the massive increase in IP (Internet Protocol) traffic has led carriers to consider expanding IP-based networks into metropolitan (metro) areas (Autenrieth et al., 2007).
Several trends have been driving this development. First, Ethernet services such as Virtual Private LAN Service (VPLS) and point-to-point Ethernet Virtual Circuits (EVCs) are increasingly being used to replace traditional telecommunications services, such as private line, ATM and Frame Relay. VPLS enables customer LANs in different locations to be interconnected and appear as one large private LAN to the customer, even if the locations are in different metro areas. EVCs can be used to replace many metro private-line services currently provided by Time Division Multiplexing (TDM) technologies.
Additionally, EVCs can also be used to provide links (often referred to as wireless backhaul) between cellular base stations and Mobile Telephone Switching Offices (MTSOs). With the continued growth in cellular telephone traffic (both voice and data), upgrading the speed and reliability of wireless backhaul represents a critical need for carriers.
In addition, as consumer broadband networks migrate from providing basic broadcast television service to more data-intensive internet applications, carriers will need to route increasing amounts of IP traffic to/from homes and neighborhoods within the metro area.
Since these metro area IP-based networks can be used to consolidate various legacy access networks (i.e., ATM, Frame Relay and TDM technologies), they are sometimes referred to as IP aggregation networks. The rapid deployment of these networks requires the development of new network planning and design tools (Wang, et al., 2010).
In particular, an engineer planning a network for a given metropolitan area typically must create many different designs for that single area. These designs correspond to various scenarios, such as different demand forecasts, different numbers and locations of backbone and access routers, or different cost projections. The availability of computer-based tools for creating these designs would be advantageous in reducing both the time and cost of network deployment.
In this paper, we describe a heuristic for designing an IP link topology (i.e., the set of router-to-router links) for IP-based metro area networks, and routing these links over an underlying physical network of optical fibers. It is able to provide efficient designs quickly and can readily be used within the setting of an interactive tool.
An IP network (within a metro area, or otherwise) consists of a number of routers that are interconnected by a set of communication links. Packets of data are then transmitted over these router-to-router links between various origin-destination router pairs. Since not every pair of routers is directly connected, some router pairs must send packets over a series of router-to-router links in order to exchange traffic.
Typically, IP networks have a hierarchical structure, in which a “backbone” or “core” network interconnects various “access” or “edge” networks. The routers that comprise the backbone network are referred to as “backbone routers.” In this paper, we focus on the design of the backbone IP network within a metro area.
Deciding on a backbone IP link topology is one of the most difficult decisions that engineers face when designing an IP network. It represents a complicated combinatorial problem. It is especially complicated when it is also necessary to decide how to route these various IP links over an underlying physical network. These decisions determine both the cost and performance of the IP network.
The underlying physical network consists of nodes interconnected by optical fibers. Each optical fiber connection (which we term a “physical link”) can carry multiple optical wavelengths. The communication links (or circuits) between router pairs are established using wavelengths routed over this physical network. A set of circuits between the same pair of routers constitutes an IP-layer link, or, simply, an IP link. (In the literature, this is also sometimes referred to as an IP link bundle.)