Renata Teixeira
email: teixeira@cs.ucsd.edu

Jennifer Rexford

A Measurement Framework for Pin-Pointing Routing Changes

Keywords: C.2.2 [Network Protocols]: Routing Protocols; C.2.3 [Computer-Communication Networks]: Network Operations Management, Measurement, Design, Reliability, Performance Network troubleshooting, root cause analysis, BGP, IGP

Changes in the end-to-end path between two hosts can lead to sudden changes in the round-trip time and available bandwidth, or even the complete loss of connectivity. Determining the reason for the routing change is crucial for diagnosing and fixing the problem, and for holding a particular domain accountable for the disruption. Active measurement tools like traceroute can infer the current path between two end-points, but not where and why the path changed. Analyzing BGP data from multiple vantage points seems like a promising way to infer the root cause of routing changes. In this paper, we explain the inherent limitations of using BGP data alone and argue for a distributed approach to troubleshooting routing problems. We propose a solution where each AS continuously maintains a view of routing changes in its own network, without requiring additional support from the underlying routers. Then, we describe how to query the measurement servers along the AS-level forwarding path from the source to the destination to uncover the location and the reason for the routing change.

INTRODUCTION

The end-to-end path between two hosts may change for various reasons, such as equipment failures and configuration changes. In addition to transient disruptions during routing convergence, the new path may have a larger round-trip time, lower available bandwidth, smaller maximum transmission unit, more aggressive packet filtering policies, or a forwarding loop or blackhole that drops packets. When multiple destinations experience routing changes at the same time, the large shift in traffic may overload one or more links in an IP backbone network. Knowing why the routing change happened is necessary for network administrators to diagnose and fix persistent reachability problems, or to tune the configuration of the routing protocols to rebalance the traffic load. Determining where the routing change originated is crucial for having greater accountability for service disruptions in the Internet. Such accountability is important for compensating end users for violations of service-level agreements and for helping network administrators select good upstream providers and peers. In this paper, we propose a measurement framework for pin-pointing the causes of routing changes.

Active measurement tools such as traceroute [START_REF] Jacobson | Traceroute[END_REF] seem like the most natural way to diagnose a routing change. However, traceroute returns inconsistent results for paths that are changing during the measurement process; in addition, some routers do not send ICMP replies and many firewalls discard the probe packets. Also, identifying the Autonomous System (AS) associated with each hop in the path is surprisingly difficult [START_REF] Mao | Towards an accurate AS-level traceroute tool[END_REF]. The future deployment of more sophisticated router-level support for active measurement (e.g., the IP Measurement Protocol [START_REF] Mcgregor | IP measurement protocol (IPMP)[END_REF][START_REF] Bennett | The case for an Internet Measurement Protocol[END_REF]) may resolve some of these issues. However, active measurement provides a view of a path only at the time the probes are sent, requiring a high probe rate to track routing changes. More importantly, active measurements alone only reveal what part of a path has changed and where packet delay, loss, or reordering occur [START_REF] Feamster | Measuring the effects of Internet path faults on reactive routing[END_REF][START_REF] Mahajan | User-level Internet path diagnosis[END_REF], but not necessarily what caused the route to change and where the change originated.

An alternate approach is to exploit publicly-available passive measurements of routing changes in the Border Gateway Protocol (BGP). Each RouteViews [START_REF]Route Views[END_REF] and RIPE-NCC [START_REF]RIPE NCC RIS[END_REF] feed logs the advertisement and withdrawal messages received via an external BGP (eBGP) session with one router in a participating AS. Recent studies have proposed looking for patterns across AS paths, destinations, and time to pin-point the location and cause of routing changes [START_REF] Chang | The temporal and topological characteristics of BGP path changes[END_REF][START_REF] Caesar | Towards localizing root causes of BGP dynamics[END_REF][START_REF] Feldmann | Locating Internet Routing Instabilities[END_REF]. However, a single topology or configuration change can lead to numerous patterns of updates, and multiple events could lead to the same sequence of routing messages [START_REF] Griffin | What is the sound of one route flapping?[END_REF]. Combining data from multiple vantage points reduces the uncertainty but the approach is still fraught with difficulty because some routing changes are not visible in BGP and others can lead to misleading BGP messages. One of the main contributions of this paper is to identify these problems and derive guidelines for diagnosing routing changes, as discussed in Section 2.

We argue that it is possible to use passive measurements for diagnosing routing problems if each AS contributes by solving its part of the puzzle. In Section 3, we present a strawman proposal where each AS constructs a view of its part of the routing system based on data readily available from today's routers-router configuration state, BGP update messages from border routers, the up/down status of BGP sessions, and intradomain routing messages. The AS uses the information to determine whether a routing change was triggered by an internal or external cause. Rather than sending raw data to a central repository, an AS accepts queries from neighboring domains about past routing changes. To diagnose external routing changes, an AS may forward a query to the next AS in either the old or the new forwarding path. Our proposed scheme can be viewed as an approach to the "Why problem" articulated in [START_REF] Clark | A knowledge plane for the Internet[END_REF] or to the "automatic error reporting" scenario in [START_REF] Bennett | The case for an Internet Measurement Protocol[END_REF]. In particular, we show how to answer questions like "why did the forwarding path to destination ✁ change?" The paper concludes in Section 4 with discussion of future research directions.

PUBLIC BGP DATA IS NOT ENOUGH

This section highlights the challenges of finding the root cause of routing changes through analysis of BGP update data alone. We discuss why some plausible assumptions do not hold under certain scenarios. In particular, we show that (i) many routing changes are not visible in the BGP data and (ii) a partial view of the BGP data may lead to inaccurate conclusions, and derive principles that guide our approach in the next section.

Routing Changes Not Visible in eBGP

ASes in the core of the Internet usually connect to multiple neighboring ASes, and two ASes may connect in multiple physical locations. Routers at the border of a network learn how to reach external prefixes by speaking external BGP (eBGP) with routers in neighboring ASes. Upon selecting an externally-learned route, the border router uses internal BGP (iBGP) to distribute the route to the other routers inside the AS. BGP is responsible for (i) determining the AS-level route to reach a destination prefix and (ii) for each router in an AS, selecting the best egress point for forwarding traffic toward that destination prefix. The internal path from the ingress point to the egress point is determined by an Interior Gateway Protocol (IGP), such as OSPF or IS-IS. In this subsection, we discuss three "myths" that relate to how routing changes inside an AS may impact the forwarding path without being visible via an eBGP monitoring session.

MYTH: The BGP updates from a single router accurately represent the AS.

The routers ✂ and ✄ in Figure 1 learn how to reach destination prefix ✁ through eBGP and propagate that information via iBGP to all other routers in AS 1. A router invokes the BGP decision process [START_REF]A Border Gateway Protocol 4 (BGP-4)[END_REF] to select a single best route for the prefix. The first few steps of the decision process compare the BGP attributes, such as local preference and AS path length, of the candidate routes. Next, the router prefers an eBGP-learned route over any iBGP-learned routes. Still, multiple equally-good choices may remain. For example, in Figure 1, the routes from ✂ and ✄ look equally attractive to router ☎ . ☎ breaks the tie by selecting the BGP route with the closest egress point-the router with the smallest IGP path cost (i.e., router ✄ with cost of ✆ ). Such a routing decision is commonly called hot-potato routing.

Hot-potato routing implies that different routers in an AS may pick different BGP-level routes. For example, ✄ picks the eBGP route through AS 3. Router ✂ learns two equally-good eBGP routes and chooses (say) the one via AS 2 based on an arbitrary tie break, such as the router id. Based on hot-potato routing, router ☎ selects the route through ✄ and router ✝ selects the route through ✂ . As such, BGP data collected from ☎ would only reveal the route via AS 3. Now suppose that a failure occurs on the link connecting router ✂ to AS 2. Then, both ✂ and ✝ would switch to the route via AS 3, which may lead to a change in the properties of the endto-end paths for traffic entering AS 1 at router ✝ . However, the link failure does not cause a change in the BGP route at ☎ and, as such, the change is not visible to the measurement system. IMPLICATION 1. The measurement system needs to capture the BGP routing changes from all of the border routers. IGP and iBGP changes may have a significant influence on endto-end performance without causing any eBGP-visible routing change. In Figure 1, router ☎ has three internal paths to reach ✁ -two via egress point ✄ (with IGP costs of ✆ and ✞ , respectively) and one via egress point ✂ (with cost ✟ ✡✠ ). Due to hot-potato routing, ☎ selects the route through ✄ with cost ✆ . Even if a link fails on the shortest path, ☎ continues to use egress point ✄ , though packet forwarding shifts to the path with cost ✞ . This does not cause an iBGP routing change, let alone an eBGP-visible change. Yet, if the path with cost ✞ has low available bandwidth or a high round-trip time, the effects on user performance might be significant.

Suppose now that a link failure makes all paths from ☎ to ✄ have an IGP cost higher than ✟ ✡✠ . Then, router ☎ switches to the BGP route with egress point ✂ . However, this iBGP routing change may or may not be visible in eBGP. If ✂ were routing traffic via AS 3, then ☎ 's new best BGP route would have the same AS path as the old one. Under the common practice of non-transitive attribute filtering, router ☎ would not send a new eBGP advertisement to its neighbors. However, if ✂ were routing traffic via AS 2, router ☎ would need to send an eBGP update to its neighbors upon switching egress points. Either way, the traffic entering the AS at ☎ may experience a noticeable change in performance properties.

IMPLICATION 2. The measurement system needs to capture IGP and iBGP routing changes inside an AS.

MYTH: BGP data from a router accurately represents routing changes on that router.

Network operators often configure their BGP-speaking routers to limit the scope of advertisements for subnets of larger address blocks, in order to limit the size of the BGP routing tables [START_REF] Chen | A Framework for Inter-Domain Route Aggregation[END_REF]. In Figure 2, router ✂ is an access router that connects to several customer networks that have been assigned address blocks out of the larger prefix ✟ ☞☛ ✍✌ ✎✟ ✏✌ ✠ ✑✌ ✠ ✓✒ ✍✟ ✡✔ . For example, ✂ may have a static route directing traffic for ✟ ✡☛ ✕✌ ✖✟ ✗✌ ✖✟ ✗✌ ✠ ✗✒ ✗☛ ✙✘ through the access link to a specific customer. Router ✂ does not need to advertise the ✟ ☞☛ ✕✌ ✖✟ ✏✌ ✎✟ ✏✌ ✠ ✓✒ ✗☛ ☞✘ route to any other routers inside the AS, or to routers in other domains; instead, ✂ simply advertises reachability to the supernet ✟ ☞☛ ✍✌ ✖✟ ✗✌ ✠ ✑✌ ✠ ✓✒ ✍✟ ✡✔ . Even a BGP feed collected directly from router ✂ would not reveal the existence of the ✟ ☞☛ ✍✌ ✖✟ ✗✌ ✖✟ ✗✌ ✠ ✓✒ ✏☛ ✙✘ subnet or any chang ✚ es in the reachability of this subnet. For example, following a failure of the customer's access link, the forwarding path of traffic destined to addresses in ✟ ☞☛ ✍✌ ✖✟ ✗✌ ✖✟ ✗✌ ✠ ✓✒ ✏☛ ✙✘ would terminate at ✂ . Yet, the BGP monitoring system would not observe any routing change. 2, other prefixes may be invisible due to the BGP export policies applied on the monitoring session. For example, an AS may export customer-learned routes to a public monitoring system but not the routes learned from private peers; often the exact details of which routes an AS exports to the RouteViews and RIPE-NCC monitors are unknown. IMPLICATION 3. The measurement system needs to know all routes the router knows, even if they are not normally visible in eBGP.

Misleading BGP Changes

Recent studies [START_REF] Chang | The temporal and topological characteristics of BGP path changes[END_REF][START_REF] Caesar | Towards localizing root causes of BGP dynamics[END_REF][START_REF] Feldmann | Locating Internet Routing Instabilities[END_REF] propose techniques for analyzing patterns in the BGP updates from multiple vantage points to infer the location and cause of routing changes. The algorithms cluster the data by time, prefix, and AS path to discover common explanations for a set of BGP updates. The accuracy of these techniques depends on the completeness of the input data. In this subsection, we discuss how partial BGP data can lead to incorrect diagnosis of a routing change.

MYTH:The AS responsible for a BGP routing change appears in the old or the new AS path [START_REF] Chang | The temporal and topological characteristics of BGP path changes[END_REF][START_REF] Caesar | Towards localizing root causes of BGP dynamics[END_REF][START_REF] Feldmann | Locating Internet Routing Instabilities[END_REF].

The inference algorithms build on the assumption that the AS responsible for a routing change appears in either the old path, the new path, or both. However, this may not hold when some of the ASes in the forwarding path do not contribute BGP feeds. In the example in Figure 3, suppose that the sideways links between these ASes are private peering links, where each AS exports only the BGP routes learned from its downstream customers [START_REF] Huston | Interconnection, peering, and settlements[END_REF]. All other links in the system correspond to provider-customer relationships where each AS exports its best route for each prefix. For simplicity, assume that each AS selects the BGP route with the shortest AS path, among the choices learned from the neighbors. In Figure 3(a), ASes ✟ , ☛ , and ✛ all choose the path through AS ☛ ; in particular, AS ✟ prefers the path through AS 2 over the longer path via AS 4. Now, suppose that AS 11 becomes a customer of AS 3, as shown in Figure 3(b). In response to this event, AS 3 now selects the new shorter AS path through AS 11 and announces the new path to AS 2. AS 2 prefers the new path over the old path through AS 8 and starts directing traffic via AS 3. This causes AS 2 to withdraw the BGP route it had advertised earlier to AS 1. Note that AS 2 does not advertise the new route to AS 1 because of the export policy (i.e., "do not export a route learned from one peer to another"). This causes AS 1 to switch to the longer customer-learned route via AS 4, as shown in Figure 3(b). Based only on BGP data from ASes 1, 4, 5, 6, and 7, the inference algorithm would only see the withdrawal of the BGP route via AS 2. From AS 1's vantage point, the AS path changes from "1 2 8 9 10" to "1 4 5 6 7 10"-ASes 3 This hot-potato routing change could be misleading to an external observer. If AS 4 originates multiple destinations, the BGP update stream from ✝ would show many routes changing AS paths from "1 2 4" to "1 3 4". This would suggest that one of the four ASes is involved. By looking across all prefixes, the observer would see that all destinations originated by AS 4 shift at the same time, and those originated by ASes 2 and 3 do not change. This could lead to the incorrect inference that AS 4 (or the link between AS 4 and AS 2) is responsible for the change. Large hot-potato routing changes (such as reported in [START_REF] Teixeira | Dynamics of hot-potato routing in IP networks[END_REF]) may also be mistakenly associated with a BGP session reset in one of the links in the AS path. Analysis of changes in the BGP AS paths does not necessarily shed light on the changes in the forwarding path because the two paths do not necessarily match [START_REF] Mao | Towards an accurate AS-level traceroute tool[END_REF]. For example, route aggregation may result in a BGP AS path that does not include the AS(es) at the end of the forwarding path. In addition, the iBGP configuration inside an AS may lead to packet deflections where one router forwards a packet to another router that has a different AS path for the same prefix [START_REF] Griffin | On the correctness of IBGP configuration[END_REF]. These deflections may in fact be the root cause of a routing anomaly, making it important to have an accurate view of the real forwarding path. Finally, configuration mistakes (whether accidental or intentional) can lead to an incorrect BGP AS path. For example, an operator may configure a router to perform AS prepending (the common practice of adding artificial hops in the BGP AS path) with the wrong AS number. This can lead to a BGP AS path that bears little resemblance to the actual AS-level forwarding path. These mismatches between the two paths can lead to faulty conclusions. For example, real changes in the forwarding path might not be visible as BGP routing changes, and vice versa. Fortunately, each AS has enough internal information to know the next-hop AS in the AS-level forwarding path.

IMPLICATION 6. Troubleshooting of routing changes needs to propagate hop-by-hop along the AS-level forwarding path.

The accuracy of identifying the root cause of routing changes using public BGP data depends on how often these myths are violated and how much coverage is need to get accurate results. Validating these hypothesis requires further research, using exactly the ASlevel measurements that we propose in the next section.

PIN-POINTING ROUTING CHANGES

We draw on the insights learned from the previous section to sketch a distributed troubleshooting service. Implications 1 and 3 imply that we need a better source of data that represents the ASlevel BGP routing decisions (an "AS-level forwarding table", if you will), and Implication 2 suggests that we also need to keep track of internal changes. In this section, we propose that each AS have an Omni server that constructs a comprehensive view of its part of the routing system 1 . Implications 4 and 5 imply the need for cooperation of the ASes involved in a routing change. Thus, the Omni in one AS may need to contact Omni servers in other ASes. Implication 6 suggests that the query resolution should follow the forwarding path; hence the Omni may launch a query to the next AS in the old or new forwarding path to the destination. After describing how the Omni server constructs the AS-level forwarding table and maintains the local routing state of the AS, we discuss the hop-by-hop propagation of queries. We end this section with a brief discussion of directions for future research.

AS-level Forwarding Table

We define an "AS-level forwarding table" as a mapping from prefixes to egress sets, where an egress set is the set of outgoing links that the border routers in the AS use to reach the prefix. The Omni needs to build an AS-level forwarding table to: (i) identify routing changes at the edge of the AS and (ii) determine which neighboring ASes to query about routing changes caused by external events. For example, in Figure 1, the Omni for AS 1 would compute the egress set ✢ ✍✣ ✤✂ ✦✥ ✧✂ ✩★ ✪☛ ✏✫ ✬✥ ☞✣ ✤✄ ✭✥ ✮✂ ✯★ ✰✛ ✓✫ ✧✱ for destination ✁ prior to the ✲ The name Omni is meant to capture the fact that the server is omniscient about the routing state in the domain.

failure of the link to AS 2. After the failure, the set would change to ✢ ✕✣ ✤✂ ✦✥ ✳✂ ✯★ ✪✛ ✗✫ ✬✥ ✡✣ ✤✄ ✴✥ ✧✂ ✯★ ✵✛ ✗✫ ✧✱ . Instead of keeping all BGP update messages, the Omni only maintains a log of changes to the egress set. For example, the Omni would not need to retain information about BGP updates that change a downstream AS in the AS path or other route attributes.

To compute egress set changes, the Omni collects iBGP updates from all border routers 2 . Then, the Omni gathers the best routes for each border router to determine the egress set for each destination prefix. The AS-level forwarding table includes all prefixes known at the router, in order to avoid the kinds of problems depicted in Figure 2. This is accomplished by configuring the iBGP session to the Omni server to inject all routes that a router learns, including static routes (which might not normally be injected in to BGP) and subnets that would normally have limited scope.

The Omni can then do an on-line pre-processing of this more complete BGP update streams to compute the egress set for each prefix and store changes to this set with a timestamp. This dataset represents the AS-level view of external routing changes and could conceivably serve as an improved feed to public BGP repositories such as RouteViews or RIPE-NCC. Currently, RouteViews and RIPE-NCC receive an eBGP update stream from an individual router in the AS. Today, these eBGP streams exclude prefixes that are not injected into BGP. In addition, there is no differentiation between internally and externally learned routes, and no information about routing changes that are subject to non-transitive attribute filtering.

Identifying Local Routing Changes

The Omni server also needs to keep track of local routing statethe egress point selected by each router for each prefix, the forwarding path through the AS, and the routing changes caused by this AS. We define a subpath as the part of the forwarding path from the ingress router to the outgoing edge link connecting to the next AS. The Omni is responsible for determining whether a subpath has changed (local effect) and whether the AS was responsible for this change (local cause).

Upon detecting a performance or reachability problem, the source asks its local Omni if a routing change has occurred. In particular, the source ✶ asks the Omni if ingress router ✷ had any routing change to destination address ✁ around time ✸ . The Omni determines if the subpath for (✷ , ✁ ) changed and whether the cause was local or not, using the decision tree presented in Figure 5. First, the Omni searches for a change in the egress set for ✁ close to time ✸ . Upon detecting an egress-set change, the Omni determines that the routing change had local cause if there was either a policy change or an edge change (i.e., an eBGP session failure or a change for a subnet not normally injected in BGP) consistent with the routing change. Otherwise, the routing change has an external cause. If the egress set for ✁ has not changed, the Omni determines whether the subpath from ✷ to ✁ has changed by examining both iBGP and IGP routing information for local causes.

The decision tree depends on the kinds of measurement data that are routinely collected for network management purposes: ✹ Policy changes: The Omni extracts the AS's policies from snapshots of the router's configuration state every time there is a change. In practice, changes occur infrequently. ✹ BGP session status: The status of BGP sessions can be obtained ✺ Routers do not need to forward routes learned via iBGP, since the Omni learns these routes directly. That is, the Omni should be configured as an iBGP "peer" of each border router, rather than a route-reflector client. This substantially reduces the number of BGP updates received by the Omni. by either SNMP data or the vendor-specific "syslog." The status of iBGP sessions is used to determine the propagation of BGP routes inside the AS, whereas the status of eBGP sessions is used to identify "edge" changes.

✹ IGP changes: An IGP routing monitor [START_REF] Shaikh | OSPF monitoring: Architecture, design, and deployment experience[END_REF] can continuously track the topology (routers and links) and the IGP parameters (such as link weights). This enables the Omni to learn about changes in the forwarding paths between pairs of routers inside the AS, as well as the IGP path costs that influence the BGPlevel routing decisions. The Omni ignores messages, such as refresh and duplicate IGP messages, that do not indicate a routing change.

The Omni can use the egress sets, iBGP session status, and IGP data to compute the subpath for each ingress router and destination prefix, using the model presented in [START_REF] Feamster | A model of BGP routing for network engineering[END_REF][START_REF] Feldmann | NetScope: Traffic engineering for IP networks[END_REF].

Inter-AS Coordination

Imagine that source ✶ in Figure 6 is communicating with destination ✁ when the link between ASes 3 and 4 fails. Source ✶ asks 3 Omni 1 if the ingress router ✷ had any routing change to destination ✁ around time ✸ . Following the decision tree in Figure 5, Omni 1 determines that the egress set changed because the BGP route through AS 3 was withdrawn. Recognizing that the local routing change had an external cause, Omni 1 queries Omni 3 for the reason of router ✻ 's change to destination ✁ at the time it learned of the egress set change. Omni 3 uses its own data to determine that the failure of the eBGP session to AS 4 caused the routing change, and responds to Omni 1, which in turn responds to ✶ .

The Omni decides how to respond to a query by identifying (i) whether the subpath changes (local effect) and (ii) whether the AS is responsible for the change (local cause): If the query reaches the AS responsible for the destination IP address, the Omni for that AS could optionally initiate a reverse query toward ✶ to determine whether a routing change occurred on the path from ✁ to ✶ . In [START_REF] Bennett | The case for an Internet Measurement Protocol[END_REF], Bennett describes a scenario for automatic network error correction that resembles the behavior described here. Using IPMP, a user identifies the last working AS in the forwarding path and issues a trouble report to that AS. In this scenario, the responsibility of diagnosing the problem falls to the AS where the effect of the problem is observed, not the one that caused the routing change. This AS does not necessarily have enough information to diagnose the problem. In our approach, queries are propagated via Omni servers in the ASes along the forwarding path, rather than through the forwarding-plane itself. Our approach avoids the expense of placing new functionality in the forwarding plane and allows the queries to access a wider range of information about the old and new forwarding paths to pin-point the location and cause of a routing change.

Challenges for Distributed Diagnosis

Our troubleshooting scheme raises several important practical issues that warrant further discussion and investigation:

Reachability of Omni servers: We envision that each end host would know the name or IP address of the Omni servers in its own domain, and that each Omni server would know the IP addresses of the Omnis in neighboring ASes; we do not expect that this information would need to change often. For simplicity, the border routers in one AS could be configured with static routes to direct packets sent to an Omni via the edge links connecting to the neighboring AS. We envision that an AS would have multiple Omnis in different locations to reduce the likelihood that the very failure that causes a routing problem for end users compromises access to the troubleshooting service.

Scalability of Omni servers: An Omni could be overwhelmed by attack traffic or even legitimate queries. An AS can install packet filters on its edge links that discard all packets destined to the Omni that do not have a source address corresponding to an Omni in the neighboring domain. To prevent excessive queries, the edge links could impose a rate limit on traffic from each sender. In some cases, a high query rate may be indicative of a legitimate routing problem affecting multiple users. An Omni could coalesce related queries or return cached results without contacting the next AS in the path. In fact, the large number of (related) queries might provide valuable hints about the scope of a routing problem.

Time interval of a routing change:

The initiator of a query can provide a time interval when a routing change may have occurred. An Omni along the query path may refine the time interval based on its own measurement data. The measurements may reveal that multiple ✽ routing changes occur close together in time (e.g., during BGP path exploration during delayed convergence [START_REF] Labovitz | Delayed Internet routing convergence[END_REF]). We envision that the Omni would answer queries about changes from one stable route to another, rather than reporting the short-lived routes during the transition. The Omni also needs to keep track of prefixes with routes that flap continuously to respond to queries about these destinations.

Incentives for ASes to participate: Our troubleshooting service depends on the participation of many, if not all, of the ASes in the core of the Internet. The cooperation of stub ASes would be valuable, too, to diagnose routing problems originating inside these networks. We believe ISPs would want to provide a troubleshooting service to their customers as part of a service-level agreement (SLA). These ISPs would need to have similar arrangements with their peers and upstream providers to ensure accountability for network disruptions. In fact, a collection of ASes (e.g., run by one company or consortium) could provide an SLA only for IP traffic that stays within the group of ASes, allowing for a partial deployment of Omnis. In a competitive environment, separate mechanisms are necessary to prevent ASes from providing inaccurate responses to queries. An AS could use its own BGP update data to validate the responses sent by a neighbor's Omni. More generally, third parties could use traceroute or BGP update data to detect persistently suspicious responses.

CONCLUSIONS

Identifying the location and cause of routing changes is crucial for troubleshooting performance and reachability problems. Currently available measurement data, such as traceroute probes and public BGP update feeds, are not sufficient. Instead, we believe that the infrastructure should have direct support for the diagnosis of routing problems. We argue that each AS should have an Omni server that constructs a network-wide view of its part of the Internet routing system and answers (and forwards) queries about possible routing changes. The Omni could also store information about the MTU size and packet filter for each link to diagnose other kinds of reachability problems. In addition, with traffic measurements from the edge links, the Omni server could detect shifts in incoming traffic and query the preceding domain about the change.

Although our solution does not rely on special support from the network, extensions to the routers such as proposed in IPMP would make the problem easier to solve. Ideally, each router would have a special monitoring session that provides a view of all of the routes it learns (including alternate BGP routes as well as routes not injected into BGP), the dynamic status of its routing protocol adjacencies (e.g., for OSPF adjacencies and BGP sessions), and an explanation for local routing changes (e.g., local policy change, withdrawal of best route by a neighbor, etc.). More generally, we believe that extending the routing protocols to reveal the underlying reason for a routing change is a promising avenue for future work.

Figure 1 :

 1 Figure 1: BGP changes are not detected at data collection point. MYTH: Routing changes visible in eBGP have greater end-toend impact than changes with local scope.

Figure 2 :

 2 Figure 2: Subnet 12.1.1.0/24 at router ✂ is not visible in BGP In addition to the example in Figure2, other prefixes may be invisible due to the BGP export policies applied on the monitoring session. For example, an AS may export customer-learned routes to a public monitoring system but not the routes learned from private peers; often the exact details of which routes an AS exports to the RouteViews and RIPE-NCC monitors are unknown.

Figure 3 :IMPLICATION 4 .Figure 4 :

 344 Figure 3: AS causing the routing change is not in the old or new AS paths

IMPLICATION 5 .

 5 The ASes involved in the routing change should cooperate to pin-point the reason for the routing change.MYTH: The BGP signaling path is an accurate representation of the AS-le ✜ vel forwarding path.

Figure 5 : 3 Figure 6 :

 536 Figure 5: Omni decision tree for classifying changes in a subpath

✹

  Local effects and local cause:When the AS is responsible for ✼ For instance, ISPs could provide a Web interface for customers to initiate troubleshooting requests. the routing change, the Omni responds directly to the query with an explanation.✹Local effects and non-local cause:When the local routing change has an external cause, the Omni examines the egress-set change to determine which neighboring ASes to query-the neighbor in the old subpath, the new subpath, or both. In the earlier example in Figure3in Section 2.2, the Omni in AS 1 would query the Omni AS 2 (along the old path, which has disappeared) which would, in turn, query the Omni in AS 3 which could explain the routing change.✹No local effects: If the Omni observes no local routing change, then the change must have an external cause. The Omni simply directs the query to the next AS in the forwarding path; since the local subpath has not changed, both the "old" and the "new" neighbor ASes are the same.

Acknowledgments

We would like to thank Jay Borkenhagen for his invaluable insights about the challenges of diagnosing routing problems in production networks. Thanks also to Christophe Diot, Geoff Voelker, and the anonymous reviewers for their helpful comments. Renata Teixeira was supported by a fellowship from Capes/Brazil and by AT&T's support for the UCSD Center for Networked Systems.


Renata Teixeira
email: teixeira@cs.ucsd.edu

Nick Duffield
email: duffield@research.att.com

Jennifer Rexford

Matthew Roughan
email: matthew.roughan@adelaide.edu.au

Traffic Matrix Reloaded: Impact of Routing Changes

come

Introduction

The design and operation of IP networks depends on a good understanding of the offered traffic. Internet Service Providers (ISPs) usually represent the traffic as a matrix of load from each ingress point to each egress point over a particular time interval. Although well-provisioned networks are designed to tolerate some fluctuation in the traffic matrix, large variations break the assumptions used in most designs. In this paper, we investigate the causes of the traffic matrix variations. Identifying the reasons for these disruptions is an essential step toward predicting and planning for their occurrence, reacting to them more effectively, or avoiding them entirely.

The traffic matrix is the composition of the traffic demands and the egress point selection. We represent the traffic demands during a time interval t as a matrix V (•, •, t), where each element V (i, p, t) represents the volume of traffic entering at ingress router i and headed toward a destination prefix p. Each ingress router selects the egress point for each destination prefix using the Border Gateway Protocol (BGP). We represent the BGP routing choice as a mapping ε from a prefix to an egress point, where ε(i, p, t) represents the egress router chosen by ingress router i for sending traffic toward destination p. At time t each element of the traffic matrix T M is defined as: T M (i, e, t) = p∈P :ε(i,p,t)=e V (i, p, t).

(

) 1
where P is the set of all destination prefixes. Figure 1 presents a simple network with one ingress router i, two egress routers e and e ′ , and two external destination prefixes p 1 and p 2 . Given traffic demands V (i, p 1 , t) and V (i, p 2 , t) and a prefix-to-egress mapping ε(i, p 1 , t) = ε(i, p 2 , t) = e, the traffic matrix for this network is T M (i, e, t) = V (i, p 1 , t) + V (i, p 2 , t) and T M (i, e ′ , t) = 0.

e i e' p1 V(i,p2,t) V(i,p1,t) p2 V(i,p1,t) + V(i,p2,t) TM(i,e,t) = Fluctuations in the traffic demands and changes in the prefix-to-egress mapping cause the traffic matrix to vary. This paper considers the natural question: what are the causes of large variations in the traffic matrix?

Most previous work on measuring [START_REF] Cao | Time-varying network tomography[END_REF][START_REF] Medina | Traffic matrix estimation: Existing techniques and new directions[END_REF][START_REF] Zhang | Fast, accurate computation of largescale IP traffic matrices from link loads[END_REF][START_REF] Zhang | An information-theoretic approach to traffic matrix estimation[END_REF] and analyzing traffic matrices [START_REF] Lakhina | Structural analysis of network traffic flows[END_REF][START_REF] Lakhina | Characterization of Network-Wide Anomalies in Traffic Flows[END_REF] has assumed that the prefix-to-egress mapping ε is stable. However, relying on periodic snapshots of routing data runs the risk of associating some traffic measurements with the wrong elements in the traffic matrix, obscuring real variations in the traffic. In this paper, we study how changes in ε impact the traffic matrix. A previous analysis of five traces of 6-22 hours in duration on the Sprint network [START_REF] Agarwal | Impact of BGP dynamics on intradomain traffic[END_REF] shows that most BGP routing changes do not lead to large traffic shifts. However, given that large traffic variations are infrequent (yet significant) events, we believe that longer traces are necessary to draw meaningful conclusions. Our previous work [START_REF] Teixeira | Dynamics of hot-potato routing in IP networks[END_REF] shows that internal routing can cause ε to change for a large number of prefixes at the same time, which can potentially cause a large traffic shift. Neither [START_REF] Agarwal | Impact of BGP dynamics on intradomain traffic[END_REF] nor [START_REF] Teixeira | Dynamics of hot-potato routing in IP networks[END_REF] study the significance of traffic shifts caused by routing relative to regular traffic fluctuations, which is the topic of this paper.

In this paper, we study the impact of routing changes on the traffic matrix over a seven-month period in a tier-1 ISP network. Using Cisco's Sampled Netflow feature [START_REF]Sampled Netflow[END_REF] and feeds of internal BGP (iBGP) messages, we compute the traffic demands V and the prefix-to-egress mapping ε for eight ingress routers. Joining these two datasets allows us to construct a detailed view of the variation of the traffic matrix over time. We also collect measurements of the intradomain routing protocol [START_REF] Shaikh | OSPF monitoring: Architecture, design, and deployment experience[END_REF] in order to identify the changes in ε that were caused by internal network events, using the algorithm described in [START_REF] Teixeira | Dynamics of hot-potato routing in IP networks[END_REF]. Our analysis shows that:

1. Although the likelihood of large traffic fluctuations is small, big changes do sometimes occur. In any given ten-minute time interval, less than 0.02% of the traffic matrix elements studied have a traffic variation of more than 4 times the normal traffic variations. However, some elements vary by more than 4 times the normal variations several times a week. 2. Most routing changes do not cause much variation in the traffic matrix. Previous studies [START_REF] Agarwal | Impact of BGP dynamics on intradomain traffic[END_REF][START_REF] Rexford | BGP routing stability of popular destinations[END_REF] have shown that routing changes typically do not cause large traffic shifts; most BGP routing changes affect destination prefixes that receive very little traffic. 3. Routing changes are responsible for many of the large traffic shifts: 58.6%

of instances where a traffic matrix element fluctuated by more than 10 times the normal variation for that element could be explained by a BGP routing change.

Although routing changes usually do not affect much of the traffic, many of the large traffic shifts are triggered by routing changes. Large traffic shifts caused by routing are rare, but important events. After introducing our measurement methodology in Section 2, we identify the causes of the big variations in Section 3. Section 4 discusses the implications of our results on other studies of traffic matrices. Section 5 concludes the paper.

Measuring Traffi c Matrix Variation

Studying the variation of traffic matrix elements over time requires collecting finegrained measurements of traffic and routing. We analyze data collected from a tier-1 ISP network for 173 days from March to September 2004. We collect data from eight aggregation routers that receive traffic from customers destined to peers and other customers. The eight routers are located in major Points of Presence (PoPs) that are spread throughout the United States.

We compute eight rows of the traffic matrix, considering all traffic from these eight ingress aggregation routers to all of the egress PoPs. This section describes how we compute the prefix-to-egress mapping ε(i, p, t) from the BGP data and the traffic demands V (i, p, t) from the Netflow data. Once we have computed ε and V , we use Equation 1 to compute the elements of the traffic matrix TM (i, e, t). The BGP monitor and the Netflow collection servers are NTP-synchronized, allowing us to use the timestamps to join the two datasets.

Prefix-to-Egress Mapping

A BGP monitor collects internal BGP update messages directly from each vantage point. Configured as a route-reflector client of each vantage point, the BGP monitor receives updates reporting any change in the best BGP route at each router for each destination prefix. The monitor records each BGP update with a timestamp at the onesecond granularity.

A single network event, such as a failure or policy change, can lead to a burst of BGP updates messages as the routers explore alternate paths. Rather than studying the details of routing convergence, our analysis focuses on the changes from one stable route to another. Similar to previous studies [START_REF] Teixeira | Dynamics of hot-potato routing in IP networks[END_REF][START_REF] Rexford | BGP routing stability of popular destinations[END_REF], we group the BGP updates for the same destination prefix that have an interarrival time of 70 seconds or less. Our analysis considers the stable route that existed before the flurry of updates and the new stable route that exists at the end.

Based on an initial BGP table dump and a sequence of BGP updates, we generate the prefix-to-egress mapping ε(i, p, t) for any given time. The egress point corresponds to a PoP rather than a specific router. We associate each egress router with a PoP based on the router name and configuration data.

Traffic Demands

Every vantage point has the Cisco's Sampled Netflow feature [START_REF]Sampled Netflow[END_REF] enabled on all links that connect to access routers and exports flow records to a collection server at the same location. The collection server samples the flow records using the technique presented in [START_REF] Duffield | Estimating flow distributions from sampled flow statistics[END_REF] in order to reduce processing overhead, and computes 10-minute aggregated traffic volumes for each destination prefix. We use these aggregated reports to extract V (i, p, t) for each vantage point i and destination prefix p at every 10-minute interval. Consequently, a reference to a time t indicates the end of a 10-minute interval.

Because of sampling, the volumes V (i, p, t) are random quantities that depend on the sampling outcomes. Through a renormalization applied to the bytes reported in sampled flow records, the quantities V (i, p, t) are actually unbiased estimators of the volumes of the original traffic from which they were sampled, i.e., their average over all possible sampling outcomes is the original volume. The standard error associated with an aggregate of size V is bounded above by k/V for some constant k that depends on the sampling parameters [START_REF] Duffield | Estimating flow distributions from sampled flow statistics[END_REF]. For the parameters employed in the current case, k < 21MB. Note that the standard error bound decreases as the size of the aggregate increases. This property aligns well with our focus on the largest changes in traffic rates: these are the most reliably estimated. As an example, for a 10-minute aggregate of traffic at a rate of 10 MB per second, the standard error due to sampling is no more than 6%.

Even though the traffic data is divided into 10-minute intervals, our 70-second grouping of BGP updates is important for cases when path exploration crosses the boundary between two ten-minute intervals. This ensures that we focus our analysis on stable changes of ε. If the mapping ε(i, p, t) changes more than once in a 10-minute interval, then we cannot distinguish the volume of traffic affected by each of them individually. Therefore, we exclude those cases from our analysis by ignoring intervals with prefixes that have more than one stable routing changes in that bin; this excludes 0.05% of the (i, e, t) tuples from our study. We also exclude all traffic for the small number of flows that had no matching destination prefix in the BGP routing tables or update messages; we verified that these flows corresponded to an infinitesimal fraction of the traffic.

Causes of Large Traffi c Variations

In this section, we explore the contributions of changes in the traffic demands V and prefix-to-egress mapping ε to the variations in the traffic matrix elements TM. Our analysis shows that, although most changes in ε have a small effect on the traffic matrix, many of the large variations in the traffic matrix are caused by changes in ε. Also, we show that, while most changes in ε are caused by external routing events, the small number of internal routing events are more likely to cause larger shifts in traffic.

Definition of Traffic Variations

Figure 2 shows an example of how two traffic matrix elements (with the same ingress point i) change over the course of a day. The total traffic entering at the ingress point varies throughout the day, following a typical diurnal cycle. For the most part, the traffic TM (i, e 1 , t) has the same pattern, keeping the proportion of traffic destined to e 1 relatively constant. For most of the day, no traffic travels from ingress i to egress point e 2 . The most significant change in the two traffic matrix elements occurs near the end of the graph. The traffic leaving via egress point e 1 suddenly decreases and, at the same time, traffic leaving via egress point e 2 increases. This shift occurred because a routing change caused most of the traffic with egress point e 1 to shift to egress point e 2 . The egress point e 2 also starts receiving traffic that had previously used other egress points (not shown in the graph), resulting in an increase for e 2 that exceeds the decrease for e 1 . In the meantime, the total traffic entering the network at ingress i remained nearly constant.

The traffic experiences other relatively large downward spikes (labeled as load variation). These spikes may very well be associated with a routing change in another AS in the Internet that caused traffic to enter at a different PoP (this kind of traffic variation was called an "ingress-shift anomaly" in [START_REF] Lakhina | Characterization of Network-Wide Anomalies in Traffic Flows[END_REF]). In this paper, we analyze traffic shifts caused by routing changes experienced by our network. Finding a signature of routinginduced traffic variations for one network is an important first step to infer other traffic variations that are caused by routing changes in other networks.

To analyze these kinds of traffic fluctuations, we define the variation of a traffic matrix element at an interval t as: ∆TM (i, e, t) = TM (i, e, t) -TM (i, e, t -1).

Changes in Traffic Demands vs. Egress Points

The variation of a traffic matrix element (∆TM ) is composed of the load variation (∆L), which represents volume fluctuations on the traffic demands V , and the routing shifts (∆R), which accounts for changes in the prefix-to-egress mapping ε:

∆TM (i, e, t) = ∆L(i, e, t) + ∆R(i, e, t)
∆L(i, e, t) represents the change in the volume of traffic for all destination prefixes that did not change their egress point from the previous time interval (i.e., ε(i, p, t) = ε(i, p, t -1) = e):

∆L(i, e, t) =

p ∈ P : ε(i, p, t) = e ε(i, p, t -1) = e V (i, p, t) -V (i, p, t -1)
Fluctuations in the traffic demands may occur for a variety of reasons, such as changes in user or application behavior, adaptations caused by end-to-end congestion control, or even routing changes in other domains.

The routing variation ∆R(i, e, t) considers the destination prefixes that shifted to egress point e during time interval t or shifted from e to another egress point in t:

∆R(i, e, t) = p ∈ P : ε(i, p, t) = e ε(i, p, t -1) = e V (i, p, t) - p ∈ P : ε(i, p, t) = e ε(i, p, t -1) = e V (i, p, t -1)
Note that if a routing change occurs within the time interval t, we associate all of the traffic associated with that prefix in that time interval with the new egress point.

Not all traffic matrix elements carry the same volume of traffic, and the volume of traffic from an ingress to an egress PoP varies over time. How do we judge if a change in the traffic is "large"? There is no absolute standard: one approach might be to judge the size of the change in traffic matrix element relative to the average traffic for that element. However, this is not useful here, because the traffic process itself is non-stationary. It has daily and weekly cycles, as well as level shifts resulting from routing changes. The relative change ∆TM (i, e, t)/TM (i, e, t) (or ∆TM (i, e, t)/ max(TM (i, e, t), TM (i, e, t-1))) seems appealing. However, this metric places too much emphasis on large relative changes to small values; for example, a traffic matrix element with 1 kbit/sec might easily experience a 50% relative change in traffic without having any significant effect on the network. An alternative metric would be the absolute change ∆TM (i, e, t). However, a shift of (say) 10 MB/sec may be significant for one ingress point but not for another. Another option would be to normalize the value of ∆TM (i, e, t) by the total traffic entering ingress point i at time t, which would capture changes in the fraction of the incoming traffic that uses a particular egress point. However, this metric depends on the "current" traffic demand at ingress i (which could be low at certain times) and may not accurately reflect the strain imposed on the network by the traffic change. Another extreme approach would be to consider the capacity of the network, and define as large any traffic shift that causes a link to be overloaded. Besides being difficult to compute, this metric is too closely tied to the current design of the network, and is not useful for most typical applications of the traffic matrix such as capacity planning or anomaly detection. Instead, we want a metric that captures properties of the traffic matrix itself, such as how large the traffic changes are relative to the normal variations of traffic matrix elements.

For that, we should consider what type of process we observe, namely, a difference process. Over short time periods, we can approximate the traffic with a linear process y t = α + βt + x t , where x t is a zero-mean stochastic process, with variance σ 2 . We observe the differences ∆y t = y t -y t-1 , which will form a stationary process, with mean β and variance 2σ 2 . Thus we can approximate the difference process by a stationary process, and measure deviations from the mean, relative to the standard deviation of this process. We measure 2σ(i, e) 2 on the traffic variation process ∆L(i, e, •) (using the standard statistical estimator), and use this to normalize the traffic variations, i.e. we then observe ∆ L(i, e, t) = ∆L(i, e, t)/ √ 2σ(i, e), and ∆ R(i, e, t) = ∆R(i, e, t)/ √ 2σ(i, e).

If the variance of the process x t was time dependent, it might make sense to use a moving average to estimate the process variance at each point in time, i.e. σ(i, e, t) 2 , and use this to normalize the traffic variations. We tried such an approach, but it made little difference to the results, and so we use the simpler approach described above. Figure 3 presents a scatter plot of ∆ T M (i, e, t) versus ∆ R(i, e, t) for all the valid measurement intervals t. The high density of points close to zero shows that large traffic variations are not very frequent (99.88% of the traffic variations are in the [-4, 4] range). Points along the horizontal line with ∆ R(i, e, t) = 0 correspond to traffic variations that are not caused by routing changes, whereas points along the diagonal line correspond to variations caused almost exclusively by routing changes. Points in the middle are caused by a mixture of routing changes and load variation. Figure 3 shows that both load and routing are responsible for some big variations. Routing changes, however, are responsible for the largest traffic shifts. Indeed, one egress-point change made a traffic matrix element vary more than 70 times the standard deviation.

Internal vs. External Routing Changes

The prefix-to-egress mapping ε may change because of either internal or external routing events. External routing changes represent any changes in the set of egress points that an AS uses to reach a destination prefix. For example, in Figure 1, the neighbor AS might withdraw the route for p2 from the router e, resulting in a change in ε. External routing changes may be caused by a variety of events, such as an internal routing change in another domain, a modification to the local BGP routing policy, or a failure at the edge of the network. In contrast, internal routing changes stem from changes in the routing inside the AS, due to equipment failures, planned maintenance, or traffic engineering. These events affect the prefix-to-egress mapping because the intradomain path costs play a role in the BGP decision process through the common practice of hot-potato routing.

When selecting a best BGP route, a router first considers BGP attributes such as local preference, AS path length, origin type, and the multiple exit discriminator. If multiple "equally good" routes remain, the router selects the route with the "closest" egress point, based on the intradomain path costs. Since large ISPs typically peer with each other in multiple locations, the hot-potato tie-breaking step almost always drives the final routing decision for destinations learned from peers, although this is much less common for destinations advertised by customers. In the example in Figure 1, an internal link failure might make router i's intradomain path cost to e suddenly larger than the path to e ′ . This would change the prefix-to-egress mapping for p2, causing a shift in traffic from egress point e to e ′ . Using the methodology described in [START_REF] Teixeira | Dynamics of hot-potato routing in IP networks[END_REF], we identified which changes in ε were caused by internal events.

Figure 4 shows the cumulative distribution functions of ∆ R caused by hot-potato routing and by external BGP changes. For comparison, we also present the cumulative distribution function (CDF) of a normal distribution, which is drawn from randomly generated Gaussian data with standard deviation equal 1, because ∆ R has been normalized to have standard deviation equal 1. Although the routing events are rare (only 0.66% of non-zero ∆ T M are caused by eBGP changes and 0.1% by hot-potato changes), this result shows that there are significant cases where these events are big, to very big. In particular, approximately 5% of traffic shifts caused by hot-potato routing are at least one order of magnitude bigger than normal variations. A single internal change is more likely to affect a large number of destination prefixes [START_REF] Teixeira | Dynamics of hot-potato routing in IP networks[END_REF], including the popular destinations receiving large amounts of traffic. We analyzed the source of traffic variation for individual traffic matrix elements, and saw that the likelihood of changes in the prefix-to-egress mappings can vary significantly from one ingress router to another. Figures 6 and5 present the same data as in Figure 3 for two sample traffic matrix elements (Note that the axis are different across the two graphs.). Some traffic matrix elements have no traffic variation caused by routing changes (Figure 5), whereas other have few very large egress shifts (Figure 6). We computed the percent of the traffic matrix elements (i, e) that have large to very large traffic shifts. We define large as more than 4 times the normal traffic variations for (i, e) and very large more than 10 times. Approximately 25% of ingress-egress pairs (i, e) in our study have no large traffic variation, and the vast majority of them (85.7%) have no very large traffic variation. The differences across the traffic matrix elements have two main explanations:

-Size of traffic matrix element. Some traffic matrix elements carry little traffic.

Most of the traffic from an ingress router exits the network at few egress PoPs, because of hot-potato routing. For instance, most of the traffic entering in San Diego is likely to stay in the west cost. Therefore, the traffic element San Diego to New York carries very little traffic at any time. -Impact of internal events. The likelihood of hot-potato routing changes varies significantly from one ingress point to the other [START_REF] Teixeira | Dynamics of hot-potato routing in IP networks[END_REF], depending on the location in the network and the proximity to the various egress points. For our eight ingress points, the fraction of BGP routing changes caused by internal events varies from 1% to 40%. As a result, the likelihood of large traffic shifts caused by hot-potato routing varies significantly from one traffic matrix element to another.

Out of the traffic matrix elements that do experience large traffic variations 15% have an average of more than one large traffic variation per week. The small percentage of elements that experience large traffic variations combined with the low frequency large shifts per element may lead to the incorrect conclusion that these events are irrelevant. However, if we consider the network-wide frequency of large traffic shifts, these events happen fairly often. To show this, we have counted the number of 10-minute measurement intervals for which at least one of our eight vantage points experienced a large traffic variation. On average, the network experiences a large traffic variation every four and half hours. Large traffic variations caused by routing changes happen every 2.3 days, and very large routing-induced traffic variations happen every 5.9 days. If our analysis considered all of the PoPs in the network, the overall frequency of large traffic variations would be even higher.

Implication for Traffi c Matrix Studies

Our analysis on traffic matrix variations has important implications for the results of previous measurement studies.

Differences across vantage points: The results in Section 3 show that the likelihood of changes in the prefix-to-egress mappings can vary significantly from one ingress router to another. In particular, some ingress points may be much more susceptible to hot-potato routing changes than others [START_REF] Teixeira | Dynamics of hot-potato routing in IP networks[END_REF], making analysis of routing stability very dependent on where the data are collected. For example, the study in [START_REF] Rexford | BGP routing stability of popular destinations[END_REF] showed that popular destination prefixes do not experience BGP routing changes for days or weeks at a time. In addition to studying RouteViews and RIPE BGP feeds, the analysis included iBGP data from two of the eight routers used in our current study. In our analysis, these two routers did not experience many hot-potato routing changes. Had the analysis in [START_REF] Rexford | BGP routing stability of popular destinations[END_REF] analyzed a router that experiences several hot-potato routing changes a day, the conclusions might have been quite different. In fact, hot-potato routing changes can affect a large number of prefixes [START_REF] Teixeira | Dynamics of hot-potato routing in IP networks[END_REF], both popular and not, so we might reasonably expect popular destinations to experience changes in their egress points. A preliminary analysis across all eight vantage points confirms that popular destination prefixes have more BGP instabilities from vantage points that experience more hot-potato routing changes.

Choice of metrics in studying unlikely events: The analysis in Section 3 shows that large changes in the traffic matrix elements occur relatively infrequently. In addition, most changes in the prefix-to-egress mapping do not lead to large traffic shifts, consistent with the results in [START_REF] Agarwal | Impact of BGP dynamics on intradomain traffic[END_REF]. Yet, these two results do not imply that routing changes are not a significant contributor to large changes in the traffic matrix elements. In fact, the opposite is true. A small number of routing changes are indeed responsible for a relatively large fraction of the (few) large traffic shifts. In addition, long traces are nec- essary to draw conclusions about infrequent (yet significant) events. The study in [START_REF] Agarwal | Impact of BGP dynamics on intradomain traffic[END_REF] draws on five traces of 6-22 hours in duration, outside of the maintenance periods where operators made planned changes to the internal network, making it difficult to conclude definitively if large traffic shifts occur and whether routing contributes to them.

Errors from ignoring egress changes in traffic matrix analysis: Previous work on measuring and analyzing traffic matrices has assumed that routing is stable, in part because fine-grained routing data is sometimes difficult to collect. Most of the work on traffic matrix estimation [START_REF] Cao | Time-varying network tomography[END_REF][START_REF] Medina | Traffic matrix estimation: Existing techniques and new directions[END_REF][START_REF] Zhang | An information-theoretic approach to traffic matrix estimation[END_REF] assumes that there are no changes in the prefix-toegress mapping or the intradomain paths between the ingress and egress points. Even work on direct measurement of the traffic demands [START_REF] Lakhina | Structural analysis of network traffic flows[END_REF][START_REF] Feldmann | Deriving traffic demands for operational IP networks: Methodology and experience[END_REF] has used only daily routing snapshots, although the work in [START_REF] Agarwal | Impact of BGP dynamics on intradomain traffic[END_REF] is a notable exception. Using out-of-date routing information runs the risk of associating some traffic measurements with the wrong elements in the traffic matrix. In some cases, the routing changes might lead to secondorder effects on the traffic (e.g., by causing congestion or increasing the round-trip time) that may appear in the data, but the primary affect of the traffic moving to a different egress point is obscured-as is the reason for the variation in the traffic. In addition, changes in the prefix-to-egress mapping may cause large fluctuations in multiple traffic matrix elements at the same time, which would be obscured if the traffic matrix is com-puted or analyzed without regard for routing changes. In our ongoing work, we plan to quantify the errors in the traffic matrix computed using daily snapshots, similar to the approach in [START_REF] Agarwal | Impact of BGP dynamics on intradomain traffic[END_REF] but focusing specifically on routing changes that have a large affect on multiple traffic matrix elements.

Dependence on network design, traffic, and goals: The results of any traffic matrix analysis, including ours, depend on the details of the network under study. For example, large ISP networks handle high volumes of aggregated traffic, which may experience much smaller statistical fluctuations in the traffic. In addition, a large ISP network connects to its peers and many of its customers in multiple locations in the network, increasing the likelihood that destination prefixes are reachable via multiple egress points. This makes an ISP network much more likely to experience changes in the prefix-to-egress mapping over time. Together, these two factors tend to make routing changes have a larger relative influence on the traffic matrix in ISP networks than in other kinds of networks. Even within a single network, the fluctuations in the traffic matrix may vary from one ingress point to another, due to hot-potato routing changes or the particular senders and receivers connected to that router. Identifying metrics that isolate each of these effects would be very helpful in deepening our fundamental understanding of what causes fluctuations in traffic matrices.

Conclusion

Our study shows that large traffic variations, while unusual, do sometimes happen. Although most routing changes typically do not affect much traffic, routing is usually a major contributor to large traffic variations. This implies that network operators need to design the network to tolerate traffic variations that are much larger than typical statistical fluctuations in the incoming traffic. In addition, research on traffic engineering and anomaly detection should take into account the impact of routing on the traffic matrix. Since both the traffic demands V and the prefix-to-egress mapping ε are necessary to compute an accurate traffic matrix, we believe it is more accurate to operate on V and ε directly, rather than simply on T M. This work has implications for both the research and network operations communities. Researchers should consider the impact of changes in the prefix-to-egress mapping when analyzing the traffic matrix. Ignoring these changes might lead to wrong conclusions about traffic matrix stability. Operators need to provision for traffic variations that are much larger than normal traffic fluctuations. In addition, operators often need to diagnose the cause of a large surge in traffic. Our work shows that the routing system is one important place they should look for explanations.

As future work we plan to quantify the inaccuracies introduced in studies of routing and traffic stability when changes in ε are ignored. We are also studying the duration of the traffic shifts. If traffic shifts are short-lived, then network operators should just over-provision to tolerate them. If they are long-lived, however, adapting the routing protocol configuration may be a better approach for alleviating congestion.

Fig. 1 .

 1 Fig. 1. Example of traffic matrix.

Fig. 2 .

 2 Fig. 2. Sample traffic volume from one ingress to two egresses.

Fig. 3 .

 3 Fig. 3. Scatter plot of ∆ T M versus ∆ R for all traffic matrix elements over the seven-month period.

Fig. 4 .

 4 Fig. 4. Cumulative distribution function of ∆ R caused by hot-potato routing and eBGP.

Fig. 5 .

 5 Fig. 5. Scatter plot of ∆ T M versus ∆ R for a traffic matrix element that have no routing-induced traffic variations over the seven-month period.

Fig. 6 .

 6 Fig. 6. Scatter plot of ∆ T M versus ∆ R for a traffic matrix element that has few very large routing-induced traffic shifts over the seven-month period. One traffic shift was over 70 times normal traffic variations!


Guochao Gu
email: guochao.gu@gmail.com

Raphaël Pesci
email: braphael.pesci@ensam.eu

Eric Becker
email: ceric.becker@ensam.eu

Laurent Langlois
email: laurent.langlois@ensam

Régis Bigot
email: eregis.bigot@ensam.eu

In Situ Microstructure Observation Of Steel Grades In The Semi-Solid State For Thixoforging Process By Using Confoncal Laser Scanning Microscopy

Keywords: steel grades, semi-solid, microstructure evolution, CLSM

The microstructure plays a crucial role for steel semi-solid forming process, and particularly for the steel thixoforging process, since it determines the thixotropic flow behavior of materials in the semi-solid state. Therefore, it is necessary to well understand the microstructure evolution during high speed heating and forming. Classically, it is investigated on a solid material quenched from semi-solid state by 2D characterization techniques. However, the semi-solid microstructure could probably not be preserved in the solid state by quenching due to complicated phase transformations or high diffusion rate of alloying elements during cooling, especially at low liquid fractions. In order to avoid this, a new in situ technique -high temperature Confocal Laser Scanning Microscopy (CLSM) -was developed and used for studying the microstructure evolution directly at high temperature. The present study aims at providing an experimental investigation of the microstructure evolution on several steel grades (M2, 100Cr6 and C38LTT) during heating from the as-received state to the semi-solid state (heating rate: ~200°C/min) and finally cooled to the solid state (cooling rate: ~200°C/min). It has been found that the temperature sensitivity of liquid fraction (∆T/ ∆fl) of these grades is much different. In addition, during cooling, there is a significant difference in diffusion rate of alloying elements between these grades. In M2, thanks to the high content of alloying elements and their low diffusion rate, the semi-solid temperature range is greater and its microstructure in the semi-solid state could be preserved by quenching process or even at a low cooling rate. On the contrary, the microstructure of other steel grades 100Cr6 and C38LTT in semi-solid state can only be revealed by CLSM at high temperature, because of the lower volume fraction of alloying elements and their high diffusion rate. It is very interesting to use high temperature CLSM to in situ investigate the microstructure evolution in the semi-solid state, especially at low liquid fraction. Since the microstructure of M2 in the semi-solid state can be reserved after cooling, it is possible to identify liquid area by the post-mortem examination. Therefore, the material flow behavior of thixoforged parts could be investigated.

Introduction

Taking advantage of the thixotropic properties, the metal slurries can be processed to produce complex parts with good mechanical properties by semi-solid forming. The thixotropic behavior is determined by the non-dendritic microstructure which consists of spheroidal grains in a liquid matrix. [1] Thixoforming is one of semi-solid forming route, in which a billet is heated until reaches the required semi-solid state with proper microstructure and then formed in the die. This technology has been applied in alloys with low melting temperature, such as magnesium and aluminum alloys [START_REF] Kirkwood | Semi-solid Processing of Alloys[END_REF]. Several collaborative activates on thixoforming were performed worldwide. The extensive effort was mainly concentrated on the industrialization of the steel thixoforming process to overcome the major obstacles. However, in these projects, the interested liquid fraction range was (0.3 < fl< 0.6) [START_REF] Atkinson | [END_REF]. In our study, we are interested in low liquid fractions (0.1 < fl < 0.3).

The required microstructure for semi-solid forming process can be obtained by several routes, which have been summarized in Ref. [4]. The recrystallization and partial melting (RAP) [5] and strain-induced melt-activated (SIMA) [6] are the more established solid state feedstock preparation routes. Recently, it was shown that tool steel X210CrW12 and M2 [7], stainless steel with a peritectic reaction [8], 100Cr6 [9] and C38 [10] could be subjected to a direct partial re-melting route, from their as-received conditions, to obtain a thixoformable microstructure. The volume fraction of solid phase and its distribution are important microstructure parameters that remain to be investigated, especially at low liquid fractions, because they crucially influence the rheological behavior [11] and therefore the flow behavior of a material during its forming [12]. Due to the high diffusion rate of elements and phase transformation behavior of steel during quenching, it is difficult to characterize the microstructure at low liquid fractions by conventional 2D quantitative metallography on quenched samples.

In situ techniques, such as synchrotron X-ray microtomography [13], Environmental Scanning Electron Microscopy (ESEM) [14] and Confocal Laser Scanning Microscope (CLSM) [15] have been developed and employed for real-time microstructure investigations.

In this study, C38LTT (low temperature for thixoforging), 100Cr6 and M2, were investigated considering the industrial applications and suitability of the thixoforging process, in particular to study the microstructure evolution during heating from the solid state to the semi-solid state by using in situ (CLSM) and ex situ techniques. In addition, a 3D semi-solid microstructure was reconstructed to show the solid skeleton and its distribution.

Experimental procedure

Materials. The materials used in this work were C38LTT, bearing steel 100Cr6 and high speed tool steel M2. C38LTT was specially manufactured for the thixoforming process by ASCOMETAL. The 100Cr6 was supplied after hot rolling process. After experiencing the hot rolling at a temperature of ~1100 °C, quenching and subsequently three times annealing for 1 h at 540 °C, the M2 was received from the supplier ThyssenKrupp. The chemical composition of the starting materials is given in Table 1. C38LTT and 100Cr6 were investigated for the reason of industrial applications, while M2 was chosen for its high content of alloying elements for 3D characterizations. Differential Scanning Calorimetry (DSC) measurements. DSC analyses were performed to estimate solidus and liquidus temperatures and the liquid fraction as a function of temperature of these materials. The measurement was performed in ASCOMETAL CREAS [12] for the C38LTT and 100Cr6 with heating rate of 20°C/min. M2 was tested by using a NETZSCH 404C Pegasus® at the heating rate of 20°C/min. Samples (Ø3mm * 1.5mm) were machined from several billets in various positions in order to minimize the possibility of getting non-representative results due to possible variations of local composition caused by the segregation in longitudinal direction. Alumina with the same weight as the sample was used as a reference and Argon was applied during heating in order to prevent oxidation.

In situ microstructure observation by Confocal Laser Scanning Microscopy (CLSM).

A Lasertec TM 1LM21H-SVF17SP CLSM combined with a heating stage was used to perform the in situ investigations of microstructure evolution at high temperature. The sample (Ø5 * 3mm) was heated in a high purity argon atmosphere. In addition, titanium foils were placed near the sample surface to consume the oxygen during heating. Thus the oxidation phenomenon could be avoided. During the real-time investigations, various material samples experienced similar heating route but different maximum temperature according to the DSC results: 1450°C for C38LTT, 1400°C for 100Cr6 and 1340°C for M2. The sample was heated at a rate of 50°C/min from room temperature to 300°C with a 50s holding time at 300°C; and then at 200°C/min to the maximum temperature without holding time. It was then cooled at 200°C/min to room temperature. The heating stage was calibrated, showing that temperature difference between the reading temperature and the real temperature did not exceed ±15°C. Before the investigations, all samples were polished down to 1µm and etched to reveal the microstructure as well as adjust the focus and the magnification of the CLSM. After in situ ivestigations, the samples were prepared and observed at room temperature by optical microscopes and Scanning Electron Microscope (SEM).

Image analyses. In order to study the microstructure in the semi-solid state, billets with a diameter of 38mm was partially induction heated. After quenching, the billets were subsequently ground, polished and etched using Nital 2% to reveal their microstructures. Microstructure observation and analysis were conducted by using an optical microscope and a JEOL 7001FLV SEM equipped with an EDS system. In addition, a 3D microstructure was constructed to show the solid skeleton and the liquid distribution. Starting materials. As shown in Fig. 1, the microstructure on transversal and longitudinal sections of materials were obtained by optical microscope and SEM. In addition, the inclusions of the materials were identified by EDS analyses. The results showed that the ferritic pearlitic steel C38LTT contained MnS and TiCN inclusions (Fig. 1a); 100Cr6 steel showed a pearlitic microstructure (Fig. 1c). As for the as-received M2 steel, the SEM-EDS observation found whiter carbides (M 6 C-type carbides which are rich in tungsten and molybdenum) and darker ones (MC-type carbides which are rich in vanadium, tungsten and molybdenum) (Fig. 1d ande). Moreover, the segregation banding along the longitudinal direction of the materials were also observed, which is related to the rolling process during manufacturing route. By using mean lineal intercept image analyses method, the average grain size of the materials is similar ~10µm.

Results and discussions

Liquid fraction curve. Liquid fraction curves as a function of temperature obtained from DSC tests for the steel grades are shown in Fig. 2. It can be observed from these curves that the special manufactured C38LTT has a narrow semi-solid interval (~100°C) for the heating rate of 20°C/min, while M2 and 100Cr6 show larger semi-solid intervals (~190°C and 160°C, respectively). Additionally, the solidus temperature varies with alloying elements contents: ~1410°C for C38LTT, 1330°C for 100Cr6 and ~1250°C for M2. Moreover, the liquid fraction curve of M2 exhibits the complex melting behavior of M2 which may be caused by the dissolution of the carbides (MC and M 6 C). Considering the DSC results, the materials (C38LTT, 100Cr6 and M2) were investigated in the liquid fraction range between 10% and 30%, which corresponds to the temperature interval of (~1420°C -~1460°C) for C38LTT, (~1370°C -~1400°C) for 100Cr6 and (~1250°C -~134°C). Metallography and image analyses. In order to study the microstructure evolution during heating, the materials were investigated by quenching experiments and in situ CLSM tests.

Quenching experiments were carried out on the steel grades at their temperature ranges. Fig. 3 shows the microstructure of the steel grades quenched from the semi-solid state. For C38LTT and 100Cr6, martensitic structure was observed with barely evidence of former liquid phase after quenching (Fig. 3 a andb). It is thought that the diffusion rate of the alloying elements during quenching was very fast that the cooling rate could not preserve the microstructure in the semi-solid state. As a result, the former liquid zones can not be identified from the microstructure quenched from the semi-solid state to room temperature. In comparison, the structures with spheroidal grains surrounded by interconnected carbides were observed for M2 (Fig. 3 c). The new carbides was formed from the liquid phase since the liquid was rich in alloying elements at high temperature. In situ CLSM observations were first performed on C38LTT and 100Cr6 in order to study their microstructures at high temperature because it was difficult to retrieve their microstructures in the semi-solid state by the conventional quenching experiments. The microstructure evolution of M2 was also real-time observed by CLSM.

CLSM Micrographs of C38LTT at different temperatures were presented in Fig. 4. As shown in Fig. 4, the microstructure of C38LTT remained the ferritic and perlitic with the presence of small inclusions (Fig. 4 (a)) until ~740°C, at which the austenization transformation occurred -the ferrite and perlite transformed to austenite. When entering the semi-solid zone, the liquid films appeared at the grain boundaries and the MnS inclusions were still remaining in the matrix and along the grain boundaries (Fig. 4 (b)). The liquid content increased with temperature. However, the liquid phase distribution was not uniform, as shown in Fig. 4 (c). The MnS inclusions changed a little even at higher temperature (Fig. 4 (c)). After cooling, the austenite grains and liquid phase transformed to perlite and ferrite. The CLSM samples were also investigated post mortem. By comparing the micrograph of CLSM sample with and without etching (Fig. 4 (e) and (f)), it was found that the former liquid phase corresponded to the ferrite grain boundaries, but not all the ferrite grain boundaries were the former liquid. Due to the insufficient cooling rate, the microstructure in the semi-solid state could not be identified by the microstructure at room temperature. For 100Cr6, the microstructure evolution is shown in Fig. 5. After the austenization transformation (perlite to austenite) at ~750°C during heating, the liquid appeared along the grain boundaries. There was a significant increase in liquid content with a small temperature increase (~20°C), as compared between Fig. 5 (b) and (c). During cooling, the austenite and liquid experienced several phase transformations and finally transformed to perlite, as shown in Fig. 5 (d). By comparing Fig. 5 (e) and (f), the pearlite was well observed by optical microscope on the CLSM investigated samples. However, it is difficult to correlate the final microstructure at room temperature with that in the semi-solid state.

For M2, the microstructure with small grain size and isolated carbides before reaching the austenization temperature (~880°C) was observed as shown in Fig. 6 (a). When reaching the austenization temperature, the alloying elements started diffusing into austenite (Fig. 6 (c)). However, the alloying elements content was too high to be totally dissolved. Furthermore, according to the phase diagram of M2, the M 6 C and MC carbides dissolve in the semi-solid range, but at different start dissolving temperature. The MC carbides dissolve first, while M 6 C dissolves later. Upon entering the semi-solid state, liquid appeared along the grain boundaries and the alloying elements diffused into the liquid phase and penetrated the grain boundaries. In addition, some small liquid droplets were observed inside the grains (Fig. 6 (d) and (e)) because of local small carbides particles. Kleiner et al. [16] described this phenomenon as self-blocking. During cooling, the liquid phase became new carbides since liquid was rich in alloying elements. It was also found that the new carbides have the same size and distribution as that of liquid phase in the semi-solid state (Fig. 6 (f)). After several solid-solid transformations (Fig. 6 (g) and (h)), the martensite matrix with inter-connected carbides were obtained confirmed by SEM observations (Fig. 6 (i)). As mentioned before, a proper microstructure with a suitable amount of liquid is necessary for successful thixoforming process. Generally, the liquid fraction as a function of temperature for steel grades depends on the chemical compositions and their distributions. Liquid fraction could be evaluated by DSC/DTA methods. For some steel grades, whose microstructure in the semi-solid state can be preserved by quenching, the liquid fraction could be determined by quantitative image analysis. However, as shown in Fig. 3, the microstructure of C38LTT and 100Cr6 at low liquid fraction could not be frozen by quenching. Thus the liquid fraction can not be evaluated by quenching experiments. Meanwhile, the microstructure evolution during heating is influenced by the manufacturing route, the distribution of chemical compositions as well as thermal history. For a given steel grade, the microstructure evolution could be investigated by CLSM. It could be seen that the liquid initiated in the grain boundaries during heating the grades. Although it was difficult to quantify the liquid fraction as a function of temperature due to the small field of view, it could be seen obviously that the liquid contents increased with temperature. However, the semi-solid range of C38LTT and 100Cr6 was relatively small as compared to that of M2. That means a higher precision should be required in temperature control for C38LTT and 100Cr6 during thixoforming. Considering the DSC results, the processing temperature ranges for C38LTT, 100Cr6 and M2 are (~1420 -~1450°C), (~1360 -~1410°C) and (~1290 -~1340°C), respectively. Besides the liquid fraction, the morphology in the semi-solid state affects the thixoforging process significantly. Although the microstructure of the grades in the semi-solid state was not the classical one for thixoforging process, but is composed of equiaxed solid grains surrounded by liquid matrix. A structure with more spheroidal grains could be obtained with holding time. However, considering the industrial conditions, the long holding time was not used. By comparing the grain size of the steel grades in the semi-solid state, it was found that the average grain size of M2 was much smaller than that of C38LTT and 10Cr6, caused by the pinning ability of the carbides. From the CLSM results, it was found that the microstructure of M2 in the semi-solid could be preserved even by a low cooling rate. Meanwhile, it made the X-ray microtomography on M2 for 3D microstructure characterization possible because of its high content of alloying elements. A detail reconstruction of 3D stacks of M2 was explained in Ref. [15]. The solid skeleton of M2 in the semi-solid state could be observed as shown in Fig. 7. The solid skeleton is useful to support the sample and prevent it from collapsing prior to forming process.

Conclusions

The microstructure evolution of C38LTT, 100Cr6 and M2 has been investigated by different techniques. The CLSM provides a possibility to directly investigate the microstructure at high temperature. Depending on the chemical composition and manufacturing process, the melting behavior of each grade was described. Combining the DSC, the CLSM results confirm that the temperature sensitivity of C38LTT and 100Cr6 is much higher which brings a difficulty in the temperature control for thixoforging. Beside 2D observation, the 3D microstructure of M2 was investigated. The solid skeleton was observed at low liquid fraction. It is used to support the billet and prevent it from collapsing prior to the thixoforging process.

Fig. 1 .

 1 Fig. 1. Micrographs of as-received samples. C38LTT in (a) longitudinal direction (optical) and (b) transversal direction (SEM); 100Cr6 in (c) transversal direction; M2 in (d) transversal direction (SEM) and (e) longitudinal direction (SEM). P: pearlite; F: ferrite.

Fig. 2 .

 2 Fig. 2. Liquid fraction as a function of temperature obtained by DSC (20°C/min).

Fig. 3 .

 3 Fig. 3. Microstructure of steel grades quenched from semi-solid state.

Fig. 4 .

 4 Fig. 4. (a)-(f) CLSM snapshots for the sequence of partial remelting of C38LTT during heating at 200°C/min until 1420°C and the subsequent cooling. (e) Sample surface after cycle and (f) optical micrograph of the material shown in (e).

Fig. 5 .Fig. 6 .

 56 Fig. 5. (a). SEM micrograph of 100Cr6 in the as-received state. (b)-(d). HT-CLSM snapshots for the sequence of partial remelting of 100Cr6 during heating at 200°C/min to a peak temperature of 1400°C and the subsequent cooling, (e) sample surface after cycling and (f) optical micrograph of the material shown in (e).

Fig. 7 .

 7 Fig. 7. 3D stack of M2 in the semi-solid state obtained by X-ray microtomography.

Table 1 . Chemical composition of the steel grades. Chemical composition (wt 10 -3 %)

 1

		C	Si	Mn	S	P	Ni	Cr	Mo	Cu	Al	Sn	As	B*	V	Ti	Nb Ca* N*	W
	C38LTT 399 596 1424 83	77	91	130	29	114	3	9	9	4	89	15	0	10	0
	100Cr6 988 230 326	6	7	210 1428 82	194	31	13	10	2	4	3	1	2	109	0
	M2	850 35	250 ≤40 ≤40 200 4100 5000 100					1900			6400

Acknowledgements

The authors acknowledge the helpful discussions with Joris Van Dyck and Muxing Guo at the Catholic University of Leuven. They also warmly thank Marc Wary (Arts et Me ´tiers ParisTech CER Metz) for his technical support and advice.