参考论文：[大规模网络拓扑测量与分析研究_张宇]

网络拓扑是指网络中各种物理或逻辑元素的配置方式、形式或结构，一般表示为图，其中，元素为点，元素间互连关系为边。

Internet，意为“网络的网络”，由上万个被称为自治系统（Autonomous
system, AS）的网络互联而成，每个 AS 又由一组路由器互联而成。这两个层次的互联结构分别称为网络的 AS 级拓扑和 IP 级拓扑。

AS级拓扑

在 BGP（Border Gateway Protocol， 边 界 网 关 协 议 ） 中 ，AS
（Autonomous System，自治域）为点，对等体间的互连（peering）关系为边。

AS 级拓扑作为 Internet 宏观结构的抽象，是由多个独立运营商根据其政治、经济利益而自组织形成的。每个 AS由上百到上万台路由器所组成，并在一个政治或经济实体的管理下运行。

IP级拓扑

在 IP（Internet Protocol，网际协议）中，路由器等报文交换设备上
接口的 IP 地址为点，相邻接口间的跳（hop）为边。

IP 级拓扑模型是对数据包实际经过的前向路径所构成结构的一种表达，反映了电信运营商对通信基础设施的设计规划，以及
在多目标优化下的技术与工程的交互。

traceroute

介绍：traceroute是用来检测发出数据包的主机到目标主机之间所经过的网关数量的工具。

Traceroute是Linux和Mac OS等系统默认提供的路由追踪小程序，Tracert是Windows系统默认提供的路由追踪小程序。二者的功能相同，都能探测数据包从源地址到目的地址经过的路由器的IP地址。

Traceroute/Tracert的实现都借助了TTL（IP头部TTL域）：通过向目的地址发送一系列的探测包(3个数据包包括：源地址，目的地址和包发出的时间标签)，设置探测包的TTL初始值分别为1,2,3…，根据返回的超时通知（ICMP Time Exceeded Message）得到源地址与目的地址之间的每一跳路由信息。

原理：程序是利用增加存活时间（TTL）值来实现其功能的。
首先它发送一份TTL字段为1的IP数据包给目的主机，处理这个数据包的第一个路由器将TTL值减1，然后丢弃该数据报，并给源主机发送一个ICMP报文（“超时”信息，这个报文包含了路由器的IP地址，这样就得到了第一个路由器的地址）。
然后traceroute发送一个TTL为2的数据报来得到第二个路由器的IP地址，继续这个过程，直至这个数据报到达目的主机。

实现过程：

1. 从源地址发出一个UDP探测包到目的地址，并将TTL设置为1；

2. 到达路由器时，将TTL减1；

3. 当TTL变为0时，包被丢弃，路由器向源地址发回一个ICMP超时通知（ICMP Time Exceeded Message），内含发送IP包的源地址，IP包的所有内容及路由器的IP地址；

4. 当源地址收到该ICMP包时，显示这一跳路由信息；

5. 重复1～5，并每次设置TTL加1；

6. 直至目标地址收到探测数据包，并返回端口不可达通知（ICMP Port Unreachable）；

7. 当源地址收到ICMP Port Unreachable包时停止traceroute。
   
   实现过程参考链接

PS：并不是所有网关都会如实返回 ICMP 超时报文。
出于安全性考虑，大多数防火墙以及启用了防火墙功能的路由器缺省配置为不返回各种 ICMP 报文，其余路由器或交换机也可被管理员主动修改配置变为不返回 ICMP 报文。
因此 Traceroute 程序不一定能拿全所有的沿途网关地址。
所以当某个 TTL 值的数据包得不到响应时，并不能停止这一追踪过程，程序仍然会把 TTL 递增而发出下一个数据包。一直达到默认或用参数指定的追踪限制（maximum_hops）才结束追踪。

IP级拓扑测量技术与实践

1.类traceroute的IP路径发现技术

利用 ICMP（Internet Control Message Protocol） 协议中 IP 头部TTL（Time to Live）域超时后返回不可达包的原理，从监测点向目标发送一组 TTL 域值逐一递增的探测包，发现从监测点到目标的前向路径上一组顺序
相连路由器的接口 IP 地址。

2.路由器接口别名解析（alias resolution，或称接口合并）技术

发现一台路由器上多个接口的 IP 地址到同一路由器的映射。

具体包括两项技术：一是利用 ICMP 协议中 UDP 端口不可达消息的接口 IP 地址发现；二是利用 IP 头部 ID 域连续计数的空扫描（null scan）技术。

通过前者可获得 IP 级拓扑，再通过后者可将 IP 级拓扑映射为
路由器级拓扑。

3. 一种测量工具skitter

1998 年，CAIDA（Cooperative Association for Internet Data Analysis）开发了测量工具 skitter，通过 18 个（2004 年底达到 25 个）分布在世界各地的监测点，测量全球 150 万个目标。

Skitter 是目前正在进行的最持久的测量项目，积累了很有价值的历史数据，已成为事实上的主动测量的标准数据源。

AS级拓扑测量技术与实践

AS 间互连关系作为一种商业协议，如果被公开，可能会影响 ISP 的市场竞争力。在无法直接获得 AS 图的情况下，研究人员使用三类收集 AS 互连信息的间接测量方法。

0.BGP协议

边界网关协议BGP（Border Gateway Protocol）是一种实现自治系统AS（Autonomous System）之间的路由可达并选择最佳路由的距离矢量路由协议。

简而言之，BGP是自治系统路由协议，用于AS间交换路由信息。

自治系统AS(Autonomous System)：AS是指在一个实体管辖下的拥有相同选路策略的IP网络。

ISP是一段互联网IP地址的管理者（互联网服务提供者）。

自治系统内，管理者可以自主决定路由的所有操作；自治系统之间的访问，需要通过BGP等外部路由协议交换信息。

提供互联网服务的ISP必须经过注册并分配AS号，该AS号全网唯一（BGP网络中的每个AS都被分配一个唯一的AS号）。

BGP按照运行方式分为EBGP（External/Exterior BGP）和IBGP（Internal/Interior BGP）。

运行于同一AS内部的BGP称为IBGP。运行于不同AS之间的BGP称为EBGP。

图片来源

BGP连接是一对一连接，建立BGP连接的双方称为对等体。

对等体通过AS号进行识别，相同AS号的称内部对等体，使用IBGP协议；不同AS号的称外部对等体，使用EBGP。

1.基于 BGP 的方法

收集 BGP 路由表或更新消息中向目标前缀推进流量所需经过的 AS 号路径。

主要的 BGP 路由测量设备是 BGP 采集器（collector）。

BGP 信息来源还包括路由器服务器（router server）和网络窥镜（looking glass）。前者是提供公开访问的路由器，与采集器相比，只能提供快照时刻的路由表，不提供路由更新消息和历史数据存档。后者提供 web 接口在同一个 ISP 的多台路由器上运行一组有限的命令，部分窥镜允许查看 BGP 路由概要，但不提供整个路由表或路由更新。

PS:全球BGP路由表的查看方法

2.基于 traceroute 的方法

利用将 IP 地址映射到 AS 号的 IP2AS 技术，将 IP级拓扑映射为 AS 级拓扑。

此方法主动发现数据包经过的“实际”路径,而非路由表中的“计划”路径。

该方法的关键在于 IP2AS 技术，通常方法是从 BGP 路由表中得到一个目的前缀与声明该前缀的起源 AS 号的对应数据，再将 traceroute 测量结果中的 IP 地址映射为 AS 号，从而得到 AS 的前向路径。

3.基于 IRR（Internet Routing Registry）的方法

收集路由策略数据库中包含用 RPSL（Routing Policy Specification Language）描述的 AS 与其对等体之间的路由策略。

网络拓扑特征化

节点度分布幂律

节点度：和该节点相关联的边的条数，又称关联度。

实际 Internet 拓扑的一个基本特征―――节点度分布幂律（power law）作为一种重尾分布，表明节点度是高可变的，节点度方差随网络规模增长呈发散趋势。

节点度幂律的发现将 Internet 与其他生物、社会网络联系在一起，使之成为同年由 Barab′asi 和 Albert 共同提出的“无尺度”（scale–free）网络的一个实例，在 Internet 拓扑研究与复杂网络研究之间架起了一道桥梁。

这里，无尺度是指节点度分布不存在有限的衡量分布范围的特征尺度，即方差。

小世界现象

包括 Internet 在内，许多现实网络所具有的另一个重要特征是“小世界”（small–world）现象，即大多数节点只经过少量的边就能到达其他
节点。

描述小世界现象的两个度量：平均路径长度，也称为特征路径长度
（Characteristic Path Length，CPL），等于图中节点两两之间距离的平均值；
聚集系数（Clustering Coefficient，CC），等于所有节点聚集系数的均值。
一个节点的聚集系数等于邻居间实际边数除以可能的最大边数。

若现实世界网络具有较小的 平均路径长度CPL 和较高的聚集系数 CC，则认为该网络具有小世界现象。

RC现象

不同节点度之间的相关性，是影响 AS 级拓扑特征的主要度量。最自然的方法是考察一条边所连两个节点度间的相关性（correlation）。

富翁俱乐部连通性（Rich-Club Connectivity, RCC），实际上是一种高度节点之间的聚集系数。Internet AS 级拓扑的 RCC 较高意味着高度节点间聚集性强，称其表现出“RC 现象”。

最短路径的介数

是分析节点中心性、估计其承载流量的一个重要度量。

网络对随机故障和蓄意攻击的容忍性和鲁棒性

鲁棒性：是指控制系统在一定（结构，大小）的参数摄动下，维持其它某些性能的特性。

鲁棒性是在异常和危险情况下系统生存的关键。

比如说，计算机软件在输入错误、磁盘故障、网络过载或有意攻击情况下，能否不死机、不崩溃，就是该软件的鲁棒性。

通过随机和蓄意删除节点和边，可以发现无尺度网络对随机故障是鲁棒的，但对蓄意攻击是脆弱的。

AS级拓扑演化机理

AS 的节点度与其包含的路由器数量呈正相关。

商业利益影响了互连决策过程。

AS 间商业关系大致分为三种：
提供商—客户（provider–to–client,p2c）
对等（peer–to–peer, p2p）
兄弟（slibing–to–slibing, s2s）

度分布幂律与解释其成因的 BA 模型构成了网络拓扑研究中的一个完整的“闭环过程”。