Many applications and services have been developed over the Internet, and it becomes increasingly important to provide highly stable, available, and scalable service as the Internet has become a fundamental infrastructure for modern society and industry in this couple of decades, Therefore, Internet-wide distributed systems such as overlay networks and peer-to-peer (P2P) systems have been proposed to achieve higher stability, availability, and scalability. However, there exists a gap between the application layer and the network layer (a.k.a. layer 3) in network operations and management such as traffic engineering because these Internet-wide distributed systems construct their own structures at the application layer over the network layer. Unlike the traditional client-server model with the end-to-end architecture, these distributed systems override the routing policies at the layer 3 network by relaying and routing traffic at the application layer. This makes them difficult to detect, monitor, and control the traffic of distributed systems by layer 3 operators. The underlying cause of the problem with this gap is that the routing functionality is provided at both the application layer and the network layer in distributed systems, while each layer is independent of each other according to the layer separation architecture of the OSI reference model unless two different layers provide an identical functionality. Thus, it is a crucial challenge to bridge the gap between the application layer and the network layer to achieve network operator-friendly Internet-wide distributed systems. In this thesis, we highlight two types of gap between the application layer and the network layer in network operations and management; lack of underlay network information such as topology, link capacity, and cost information for the optimization of the overlay structures at the application layer, and insufficient and immature technologies in operations and management at the network layer for Internet-wide distributed systems such as traffic engineering and anomaly detection at the network layer.

Regarding the former type of gap, distributed systems such as P2P applications frequently utilize a large amount of network resources and cost more from the layer 3 core network operators' viewpoint because they do not take into account the routing policies and economics at the network layer. Moreover, they may utilize a detoured path that is disallowed or unexpected by layer 3 network providers. The Application-Layer Traffic Optimization working group in the Internet Engineering Task Force has worked on the standardization of an application-layer traffic optimization service that provides applications with information to perform better-than-random initial peer selection of P2P systems and node selection of other applications such as content delivery networks. However, the working group does not focus on the cost configuration between different administrative domains, i.e., autonomous systems (ASes), responding to the complex inter-AS policies. Therefore, we propose an AS relationships estimation method to provide applications with the inter-AS cost information Most network providers cannot disclose their relationships because the interconnections are established by their commercial contracts. The proposed method estimates AS relationships from publicly available AS-level topology datasets according to a simple traffic exchange model. Unlike the approach of the existing methods to infer AS relationships using AS paths, we adopt the simple traffic exchange model because the exchanged traffic volume is the fundamental basis of the AS relationships that the relationships between interconnections ASes are determined by the (a)symmetricity of the exchanged traffic volume. In this thesis, we demonstrate the proposed method outperforms the existing AS relationships inference methods, especially in peering links. We also discuss the advantages of the proposed method over the existing methods in the application-layer traffic optimization that the proposed method enables to estimate the relationships of invisible links not contained in the set of AS paths in publicly available datasets.

Network operators have employed traffic classifiers and anomaly detectors in their networks to bridge the latter type of gap and to improve operations and management at the network layer for Internet-wide distributed systems. However, many traffic classifiers and anomaly detectors rely on deep packet inspection, and consequently, they are not tolerant to the encryption of application data and they have some privacy issues raised by packet inspection. Moreover, maintaining the up-to-date signatures for each application takes a huge effort though various network applications including distributed systems run on the Internet. Thus, these existing tools do not capture the characteristics of Internet-wide distributed systems and they are not sufficient and mature for these systems. In this thesis, we develop an application traffic profiling method with traffic causality graphs (TCGs) that focuses on the temporal and spatial causality of flows of network applications to capture the characteristics of the distributed systems without inspecting packet payload. A key idea of TCGs is to focus on the causality of individual flows composed of different application protocols rather than a set of host flows. This idea enables us to analyze temporal interactions between flows, such as the temporal manner of flow generation by identical application programs and interactions between incoming and outgoing flows. In order to achieve automated profiling with TCGs, we adopt a graph mining approach to extract discriminative patterns in TCGs, and a similarity measure to identify the application of a TCG. We demonstrate the effectiveness of TCGs for profiling network applications in case studies and the automated profiling results with ground truth datasets.

Thus, we have worked to bridge the gap between the application layer and the network layer in network operations and management in the existing dirty slate architecture. There is another conceivable approach to solve the cross-layer problem by redesigning a clean slate networking architecture as several architectures such as content-centric network and named data networking have been proposed. However, it takes a lot of time and effort to replace the existing architecture with them. Therefore, we focus on solutions in the existing dirty slate architecture. In addition to the focus on the existing dirty slate architecture, we do not adopt a cross-layer dependent approach but a rough approach based on better-than-nothing principles to bridge the gap. This is because the cross-layer dependent approach has a difficulty in deployment and it requires an operation-related informational standard as well as a protocol specification standard. We illustrate the problem with the cross-layer dependent approach by domain name system (DNS) delegation relationships analysis in the IPv4 and IPv6 coexisting Internet. The domain name resolution procedure following the DNS delegation structure depends on the underlay protocol (i.e., IP), and consequently, an operation-related informational standard is required to support the coexistence of multiple underlay protocols. Since the DNS is a key infrastructure on the Internet, which is a tree-structured directory service to look up resources, such as corresponding IP addresses, from domain names and many services and systems, such as Web services and E-mail systems, deeply rely on DNS, there is an operation-related informational standard to guarantee the domain name resolution in in the IPv4 and IPv6 coexisting Internet; RFC4472 defines that every zone should provide at least one IPv4-enabled authoritative servers, domain name resolution with IPv4 is guaranteed as long as authoritative servers are operated according to RFC4472. Note that RFC4472 does not define IPv6-related configurations in terms of the connectivity of authoritative servers. Therefore, domain name resolution with IPv6 is not guaranteed, and it depends on the operating policy and configurations of each zone. In this thesis, we employ the DNS lookup graph that represents the domain name lookup procedure as a labeled directed graph to illustrate the difficulty in the deployment of a new underlay protocol in the cross-layer dependent approach by showing trends of the DNS lookup path in resolving A and AAAA records with IPv4 and IPv6 transport protocols using the datasets measured before, during, and after World IPv6 Day, and after World IPv6 Launch. Note that World IPv6 Day and World IPv6 Launch are worldwide IPv6 events to test and deploy IPv6 on the real Internet environment in 2011 and 2012.

In summary, this thesis consists of three parts: 1) inter-AS economics (i.e., AS relationships) estimation on the AS-level Internet topology to provide applications with the underlay cross-domain cost, 2) Internet application traffic profiling with a graph mining approach from the causality of flows to improve the operations and management at the network layer, and 3) DNS delegation relationships analysis to shed light on the problem with the cross-layer dependent approach and to support the approach based on better-than-nothing principles.

本論文は「Analysis and Management of the Internet based on Data Flow Profiling(データフロープロファイリングに基づいたインターネットの解析と制御)」と題し,英文で記されており,5章から成る.分散システムの構成するオーバーレイネットワークをIPネットワーク運用者の視点から効率的に運用・制御することを目的として,インターネット上で流通するデータフローに注目し複雑化するインターネットの構造およびトラフィックを解析する技術を提案したものである.分散システムはIPネットワーク上に独自のネットワークを構成するため,IPネットワークと分散システムの構成するオーバーレイネットワークとの間で経路・トラフィック制御ポリシーの不整合が発生している.また,分散システムは複雑なトラフィックを生成するためネットワーク運用を困難にしている. IPレイヤーと分散システムの異なるレイヤー間の協調経路制御を実現するためのメトリックが不足している問題および既存のネットワーク運用技術が複雑な分散システムに対応していない問題に対し,インターネット上でのデータフローに注目し実インターネットの構造およびトラフィックを解析する技術を提案し,その解析結果を用いて効率的なネットワーク運用および制御を実現するという方針を取っている.

第1章「The Internet and Internet-wide Distributed Systems」では,インターネット上に展開された分散システムの構成するオーバーレイネットワークの経路制御ポリシーがIPネットワークとは異なるために引き起こされる問題点を提起し,その問題に対する方針を概説している.本論文では,解決すべき課題として次の二つを挙げている.一つ目は,オーバーレイネットワークを構成する分散システムにIPレイヤーにおける単位ドメインである自律システム(AS: Autonomous System)間の経済関係の情報を提供することである.二つ目は,分散システムの複雑なトラフィックに対応したアプリケーショントラフィックの分類を実現することである.

第2章「AS Relationships Estimation based on Traffic Exchange Model」では,第1章で挙げた一つ目の課題について,実ネットワークへ展開可能なAS間の経済関係の推定手法を提案している.AS間の経済関係はトラフィックエンジニアリングなどに応用可能であり有用な情報であるが,契約情報であるため非公開でありその応用が困難であった.本論文では,従来には無かったトラフィック流量モデルに基づく手法を提案しており,提案手法により従来手法よりも高精度な推定を実現でき,また従来手法では不可能であった不可視なリンクに対する推定も実現可能と評価している.

第3章「Internet Application Traffic Profiling」では,第1章で挙げた二つ目の課題について,複雑な通信パターンのアプリケーションの挙動を把握することを実現するアプリケーショントラフィック分類手法を提案し,その性能を評価している.分散システムでは複数のノードが通信するため,その通信パターンはネットワーク運用者にとって,把握することが困難であるため不正検知やトラフィック制御が困難であるという問題があったが,提案手法により複雑な通信パターンを有効グラフとして抽象化することができ,また,グラフマイニング手法を応用することにより特徴的な通信パターンを自動的に発見することを可能としている.本論文では,実ネットワークにおいて採集したトラフィックに対する分類事例を挙げることでネットワーク運用に非常に有用であることを評価している.また,従来の技術では困難であったアプリケーションの同定においても90%と非常に高い精度を実現しており,提案手法の優位性を定量的に示している.

第2章および第3章では,分散システムと協調動作可能な新しいネットワークアーキテクチャを提案するのではなく,既存のアーキテクチャ上に展開可能な運用・制御技術を提案する方針を取った.第4章では,この方針の根拠を示すために,既存のシステムを維持したまま新しいアーキテクチャを展開することが困難であることを明らかにしている.具体的には,新しいインターネットプロトコルであるIPv6の展開において,インターネット上での基盤システムの一つであるDNSの委譲構造を分析し,IPv6のDNSへの展開がレイヤー間で依存している点で進行していないと評価している.すなわち,多種多様なアプリケーションが存在するインターネットでは,レイヤー間で協調動作可能な新しいアーキテクチャを考案するよりも,現状のアーキテクチャを発展させていく本論文の方針が有効であることを示している.

第5章「Conclusion」では,本論文全体の果たす貢献についてまとめるとともに,第2章および第3章で提案したインターネットの構造解析およびトラフィック制御技術の結論および第4章で評価した本論文の方針の根拠を総括している.また,提案した解析手法を応用することで,新しいアーキテクチャの設計にも応用可能であることをまとめている.

以上を要するに,本論文は,複雑化するインターネットを効率的に運用・制御するために必要不可欠な技術を考察し,従来技術では実現不可能であった課題に対して新しいアプローチにより,IPネットワークの運用者にとって有用な技術を提案し,全ての提案について実ネットワーク上で計測したデータを用いた評価を行うことで,実ネットワークへの展開が実現可能であることを示している. これは実データに基づいたモデル化とその実践適用の可能性をしめしており,インターネットにおけるトラフィックの解析をその応用に関して先駆的な貢献と認められ,情報理工学における創造的実践の観点で価値が認められる.

よって本論文は博士(情報理工学)の学位請求論文として合格と認められる。