互联网主机的物理位置是许多新位置感知服务的关键推动因素。在本文中，我们介绍了一个基于网络测量来定位现实世界中互联网主机的新颖综合框架Octant。该框架的关键点是提出把地理定位问题中误差最小化正式地作为满足约束条件之一，以几何方式解决从网络测量中积极推导出约束系统，以在目标驻留区产生估计区域。这种方法通过利用正负约束来获得其精确度，即分别在节点可能和不可能所在的位置限制。约束使用由贝塞尔曲线界定的区域来表示，允许精确约束表示和低成本几何运算。为了能够优雅地应对约束系统中包含的错误该框架可能会存在不确定性。使用PlanetLab节点和公共traceroute服务器对Octant的评估显示，Octant可以定位到22英里以内，是其他方法定位精度的三倍。
确定互联网主机的物理位置是多种网络服务的关键推动因素。例如，通过将网络节点定位到地球上某个位置，可以在网络上提供个性化定制内容，简化大型设施中的网络管理，且可帮助进行网络诊断。然而，仅仅基于网络测量精确地定位现实世界中节点的位置却存在许多挑战。准确和精确地理定位的关键障碍有三个方面：如何表示节点的网络位置，如何提取节点可能位于或可能不位于何处的约束，以及如何组合这些约束以产生节点良好的位置估计。
图1：Octant中的定位区域表示
Octant用一组贝塞尔曲线界定的区域表示估计的目标位置。曲线a，b，c分别由P0、P1、P2、P3共四个控制点组成，其中P0和P3分别作为起点和终点，P1和P2作为控制点，用于控制曲线。这个图示仅需要9个控制点即可做到精确定义。贝塞尔曲线提供了一种简洁的方式来精确地表示大而复杂的区域。贝塞尔曲线还允许高效的交集，并集和差集运算。
因此，可扩展的Octant实现可以决定以简单的边界圆逼近特定复杂度的βk，以便限制每个区域的曲线数量，从而以适度误差为代价获得可扩展性。图3阐明了主要和次要基准点的正负约束推导。
图2：在Octant中综合运用正负限制
（a）具有精确位置估计的主基准点及其相关约束。 （b）正约束是通过估计区域中所有圆的并集来计算的。距离d内的节点必须位于用黑色外线标记的区域内。 为了清楚起见，仅显示圆的子样本。（c）通过取估计区域中的所有圆的交集来计算负约束。距离d以外的节点不能在标有虚线的区域内。（d）一个次要基准点，其位置不准确。请注意，由于Octant以保守的方式混合这些结果会导致更大的环带。 为了效率，具体实现可以用有界圆替代复杂的贝塞尔区域。
给定一个正约束集合Ω和对目标节点i的位置负约束集合 Φ，目标的估计位置区域由下式给出：
这个方程式是精确的，并且使之转变为高效优雅的几何解决方案。图2说明了Octant如何组合约束以产生目标的精确估计位置区域。
图3：在Octant中正负约束来计算的目标节点的估计位置区域
Octant通过延迟测量提供的可用的正负约束来计算目标节点的估计位置区域，所得到的位置估计由权重分隔的非凸的不相交的区域组成。
然而，在这种方法可以用于互联网上的实际地理定位之前，有很多问题需要解决。在上述一般公式中，所有约束均等加权，解是离散的； 一个点是或者不是解决方案空间的一部分。离散的解决方案策略导致系统的脆弱性，因为单个错误的约束会将估计的位置区域缩小到空集合。一种策略是仅使用来自光速的高度保守的正约束，并避免所有负面约束。我们稍后表示，这样一个保守的策略并没有达到很好的准确性。在下一节中，我们将详细介绍优化，使基本的Octant框架能够应用于因特网上的噪音和冲突的测量。
如果互联网上的延迟与现实世界中的距离成正比，那么地理定位问题就会大大简化。三个因素使互联网延迟测量复杂化。首先，互联网由传输和处理速度差异很大的异构链路，主机和路由器组成。第二，在最后一跳发生的非弹性延迟可能引入额外的延迟，打破往返时间与物理距离之间的相关关系。最后，数据包从源到目的地的经常沿着间接的，迂回的路径传输，使得地表两点间的大圆弧估计不准确。 在接下来的三个部分中，我们依次讨论这些问题。
1.1时延与物理距离的映射然而，延迟测量和实际距离之间的相关性通常比基于光速的约束更好和更紧。 图4是从我们研究中的主基准点（planetlab1.cs.rochester.edu）到所有其他主基准点的物理距离的网络延迟与物理距离的关系。该图清晰表明物理距离之间松散的相关性，并说明了光束边界的速度过于保守。此外，右下角的空白区域表明，几乎没有明显拥挤的连接；物理上接近的节点通常可在短时间内到达。这为希望积极提取约束的制度提供了一个机会，该制度有时会冒着过分激进的要求，既收紧正约束的界限，又引入了负约束。
图4：基准点的延迟-距离图
图4是从基准点（planetlab1.cs.rochester.edu）对其它进行测量得到的延迟-距离图。阴影区域表示由光纤中的光的传播延迟时间界定的有效点位置。 数据点周围的凸包作为节点的正负约束。对于给定的延迟时间，凸包的顶部和底部分别表示约束环的外部和内部半径。随着距离的增加，展示节点数量减少，导致凸包的绘制过于激进。 垂直线表示第50和第75百分位数的截止值，此处凸包被切割，并且当代表性节点不足时，保守的正负约束被替换上去。
实际上，当有足够的基准点，基准点之间测量值接近于基准点到目标的测量时，这种方法可以产生良好的效果。在目标具有通向基准点的直接且无阻塞的路径的情况下，它可能超出RL(d)，对于rL(d)也一样。虽然我们稍后讨论的Octant的扩展可以补偿偶尔的错误，但是当只有不足的基准点来得出统计学上有效的结论时，r和R估计可能会出现系统上的错误。因此，Octant引入了延迟的截止值 ρ，使得基准点的可调百分位数位于 ρ的左边，并抛弃位于右边的凸包的部分。也就是说，只考虑了可以获得足够的数据点的凸包的部分。 Octant然后使用rL（x）= rL（ ρ），∀x ≥ ρ， RL（x）=m（x-ρ） RL（ρ），m =（yz -RL（ρ））/（xz-ρ），其中放置在远处的虚拟哨兵数据点z提供基于光速施加的限制，从凸包的侵略性估计平稳过渡到保守约束。
1.2最后一跳时延时延到距离的映射要远比额外的排队、处理、与最后一跳相关联的传输延迟复杂。对于家庭用户来说，这些最后一跳延迟可归因于通常供应不足的有线和DSL连接。即使在广泛的领域，服务器的处理开销也额外地增加了延迟测量的时间，这可能会蒙蔽传输延迟。例如，在重载的Planetlab节点上，即使仔细使用内核时间戳(kernel timestamp)，测量的延迟也会显著增加。因此，实现更准确和更健壮的定位结果要求我们隔离(isolate)非弹性延迟分量，非弹性延迟分量即人为造成的延迟测量膨胀，这会混淆时延与距离之间的相关性。
在理想情况下，地理定位系统将检索所有节点间路径上的所有路由器，隔离每个节点上每个路径上存在的路由器，并将这些路由器的排队和传输延迟以及节点的平均处理延迟与节点的非弹性分量相关联。由于这种方法是不切实际的，我们需要一种可行的方法来近似延迟测量的最后一跳延迟。
问题的三个属性激发了端对端方法测量和表示最后一跳延迟。首先，定位需要在没有目标主机配合的情况下快速完成。这排除了使用精确定时硬件 (precise timing hardware) 进行数据包扩展 (packet dilation)，以及需要在目标上预安装处理代码的软件方法。第二，需要很大的开销，还没有为动态定位所需的时间表提供答案。第三，Octant具有适应约束的不确定性的机制（第3.4节），因此可以接受其最后一跳时延估计的不准确性。这些属性驱使我们使用一种简单的度量标准，我们称之为高度(height)——一种快速、低开销的端到端方法来从给定主机的探测结果中采集到最后一跳延迟。
Octant从基准点之间成对的延迟测量中得到高度估计值。取a、b、c三个主基准点测量他们之间的延迟，标记为[a,b]、[a,c]、[b,c]。时延的测量是往返时间，它将两个链路方向上的最后一跳延迟计算在内。由于主基准点的位置已知，可以计算基准点之间的大圆弧长距离，从中可以得到相应的传输延迟的估计，标记为(a,b)、(a,c)和(b,c)。这提供了任何两个基准点之间的最后一跳延迟的估计；例如，基准点a和b之间最后一跳延迟是[a,b]-(a,b)。Octant通过求解以下一组方程式来确定可以将多少延迟归因于每个基准点，表示为 a'，b'，c'
类似地，对于目标t，Octant可以通过求解以下的方程式来计算t'以及经度和纬度，即tlong和tlat的估计：
其中(a,t)可以按照along，alat，tlong，tlat来计算。 然后，我们可以得到使残差最小化的t', tlong, tlat的解。 计算的tlong和tlat结果与分配的合成坐标类似，具有较高的误差，在后期没有使用。目标节点本身不需要将其高度参数计入结果中，除了响应基准点的ping之外。图5显示了我们的PlanetLab数据集中基准点的高度。
图5：PL数据集张基准点的高度
用于得到不同位置分布的基准点的网络路径上的最后一跳的延迟。 垂直的柱表示基准点，其位置对应于其实际物理位置，而柱的长度对应于其高度值。
鉴于目标节点和基准点的高度， 如果目标节点的高度小于其他基准点的高度，则每个基准点可以将其R L向上移动，如果目标节点的高度大于其他基准点的高度，则将其r L向下移动。这为确保数据包在最后一跳中花费时间的至少一小部分不会偏离导出的约束条件提供了一个原则的基础。
1.3间接路由Octant通过执行分段定位来处理间接路由，即将从基准点到目标节点网络路径上的路由依次定位，其中使用上一步定位的路由作为次基准点。如图6所示，这种方法比仅使用端到端的时延得到更好的结果。由于Octant可以仅基于往返时间执行定位，因此定位路由器不需要部署任何其他代码。
图6：使用路由器作为次基准点进行定位
使用中间路由器作为次基准点可以显著提高定位精度。Octant首先会确定路由器的估计位置区域。在可能的情况下，Octant会根据路由器所在的路由器的DNS名称（UNDNS）提取基于城市的位置估算。这是针对印第安纳波利斯和休斯顿展示的，其中点代表位于该城市的每个邮政编码的中心。 对于布法罗和堪萨斯城，路由器的位置使用没有UNDNS信息的Octant来计算。 为了清楚起见，省略了布法罗和伊萨卡周围的圆环。
1.4处理不确定性Octant使用的权重系统随着延迟的增加而呈指数下降，从而在存在较低等待时间的基准点时减轻高延迟基准点的影响。基于始发基准点和目标节点之间的等待时间，权重与每个约束相关联。当两个区域重叠时，权重被加在一起。在没有权重的情况下，可以通过联合和交集操作来组合区域，导致位置估计的离散解决方案 - 节点位于一个区域内或外部。权重的引入会改变实施。当两个区域重叠时，Octant通过交叉点确定所有可能产生的区域，并将相关联的权重分配给每个区域。最终估计的位置区域是通过采用由权重排序的所有区域的并集计算的，使得它们超过期望的权重或区域阈值大小。
权重使Octant能够将有问题的真实性的限制整合到系统中。回想一下，当产生的区域是空集合时，返回并找到导致不可行解决方案的最小约束集是NP完整的问题。权重允许将有冲突的信息引入系统，而不必过度约束最终系统并降低其有效性；来自延迟测量的过度限制，来自WHOIS的不正确的邮政编码或者undns中的错误的路由器不会将解决方案提交给空集。如果没有补偿因素，严重的约束可能会影响精度，但是权重使得Octant可以将概率测量与节点可能在其中的空间区域相关联。
1.4选择点Octant计算一个最终的估计定位区域，该区域包含了系统对目标节点所在位置的最佳估计。一些应用程序可以直接使用这种区域估计。例如，诸如房地产这种的Web应用程序基于浏览者可能位于的邮政编码来生成内容。Octant可以将该区域作为贝塞尔曲线的有界曲面或有序的坐标列表提供给这些应用。然而，许多传统的应用程序以及过去的工作（如GeoPing和GeoTrack）将目标定位到单个点。为了支持传统的应用程序并提供与一种和以前工作比较的方式，Octant使用蒙特卡罗算法来选择代表目标位置的最佳估计值的单个点。该系统最初选择数千个位于估计区域内的随机点。每个点被分配一个基于其距离到其他所选点的总和的权重。经过一些试验之后，选择最小权重的点作为目标位置的最佳估计值。这个点保证在估计的位置区域内，即使该区域由不相交的区域组成。理想情况下，Octant的单点选择接口只是为支持传统应用程序的过渡迁移方案。我们希望未来的应用程序能够充分利用Octant估计面积中的额外信息。
2、评价
图7：不同定位技术的准确性比较
Octant实现了比以前的工作显著更高的精度，定位结果更加接近目标的实际位置。
图8：Otant VS GeoLim 误差距离
由于Octant处理个别基准点定位估算的不确定性机制，使得Octant定位估算值中的目标百分比明显高于GeoLim。
图9：Otant VS GeoLim 估算面积
在所有测试的基准点中，Octant的定位估算面积明显小于GeoLim的面积。
图10：单点估计之间的平均距离
在所有的定位技术中，Octant能够仅通过数量较少的基准点实现高精度定位。
图11：Octant中使用的单个优化对地理定位精度的贡献
在Octant中使用的单个优化对地理定位精度的贡献中，中间节点的使用提供了对系统精度的最大改进。
图12：Octant、各种未优化的Octant和GeoLim的目标在估计位置区域内的平均百分比
图13：具有人口和地理限制的Octant位置估算区域
这些外部约束的使用大大减少了估计面积的大小。
图14：在traceroute服务器数据集上的定位准确性
公共traceroute服务器数据集上的不同定位技术的准确性显示出与PlanetLab数据集非常相似的结果，其中Octant点估计值更接近于目标的实际位置。
总结确定互联网主机的地理位置是一个本质上有用的基本组件。由于没有现有的用于发现端点(endpoints)的物理位置的标准化协议，我们必须依靠可以从网络测量中提取位置信息的技术。
在本文中，我们概述了一个广泛的综合框架Octant，用于表示节点的网络位置，提取节点可能位于或可能不位于何处的约束，并结合这些约束来计算目标节点的更可能所处位置的小区域定位估计。Octant使用可接受任何种类约束的贝塞尔有界区域来精确表示节点位置和区域，利用正负约束激进地减少估计的区域大小，并且可以在存在不确定性和错误约束的情况下有效地推理出来。它利用多种技术从因特网上的端到端延迟测量中提取细粒度信息。
我们已经使用PlanetLab主机和公共traceroute服务器的测量来评估我们的系统，并发现Octant是非常准确和有效的。该框架可以将节点定位在其实际位置22英里内（中值）。评估还表明，Octant可以将目标节点定位到小于先前方法大小的一半的区域，并且比较大区域更高概率的包含目标。Octant使得网络运营商能够仅通过简单的延迟测量来有把握地确定节点的位置，从而实现新的位置感知服务。
,
