互聯網主機的物理位置是許多新位置感知服務的關鍵推動因素。在本文中，我們介紹了一個基于網絡測量來定位現實世界中互聯網主機的新穎綜合框架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框架能夠應用于因特網上的噪音和沖突的測量。

如果互聯網上的延遲與現實世界中的距離成正比，那麼地理定位問題就會大大簡化。三個因素使互聯網延遲測量複雜化。首先，互聯網由傳輸和處理速度差異很大的異構鍊路，主機和路由器組成。第二，在最後一跳發生的非彈性延遲可能引入額外的延遲，打破往返時間與物理距離之間的相關關系。最後，數據包從源到目的地的經常沿着間接的，迂回的路徑傳輸，使得地表兩點間的大圓弧估計不準确。 在接下來的三個部分中，我們依次讨論這些問題。

然而，延遲測量和實際距離之間的相關性通常比基于光速的約束更好和更緊。 圖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提供基于光速施加的限制，從凸包的侵略性估計平穩過渡到保守約束。

時延到距離的映射要遠比額外的排隊、處理、與最後一跳相關聯的傳輸延遲複雜。對于家庭用戶來說，這些最後一跳延遲可歸因于通常供應不足的有線和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向下移動。這為确保數據包在最後一跳中花費時間的至少一小部分不會偏離導出的約束條件提供了一個原則的基礎。

Octant通過執行分段定位來處理間接路由，即将從基準點到目标節點網絡路徑上的路由依次定位，其中使用上一步定位的路由作為次基準點。如圖6所示，這種方法比僅使用端到端的時延得到更好的結果。由于Octant可以僅基于往返時間執行定位，因此定位路由器不需要部署任何其他代碼。

圖6：使用路由器作為次基準點進行定位

使用中間路由器作為次基準點可以顯著提高定位精度。Octant首先會确定路由器的估計位置區域。在可能的情況下，Octant會根據路由器所在的路由器的DNS名稱（UNDNS）提取基于城市的位置估算。這是針對印第安納波利斯和休斯頓展示的，其中點代表位于該城市的每個郵政編碼的中心。 對于布法羅和堪薩斯城，路由器的位置使用沒有UNDNS信息的Octant來計算。 為了清楚起見，省略了布法羅和伊薩卡周圍的圓環。

Octant使用的權重系統随着延遲的增加而呈指數下降，從而在存在較低等待時間的基準點時減輕高延遲基準點的影響。基于始發基準點和目标節點之間的等待時間，權重與每個約束相關聯。當兩個區域重疊時，權重被加在一起。在沒有權重的情況下，可以通過聯合和交集操作來組合區域，導緻位置估計的離散解決方案 - 節點位于一個區域内或外部。權重的引入會改變實施。當兩個區域重疊時，Octant通過交叉點确定所有可能産生的區域，并将相關聯的權重分配給每個區域。最終估計的位置區域是通過采用由權重排序的所有區域的并集計算的，使得它們超過期望的權重或區域阈值大小。

權重使Octant能夠将有問題的真實性的限制整合到系統中。回想一下，當産生的區域是空集合時，返回并找到導緻不可行解決方案的最小約束集是NP完整的問題。權重允許将有沖突的信息引入系統，而不必過度約束最終系統并降低其有效性；來自延遲測量的過度限制，來自WHOIS的不正确的郵政編碼或者undns中的錯誤的路由器不會将解決方案提交給空集。如果沒有補償因素，嚴重的約束可能會影響精度，但是權重使得Octant可以将概率測量與節點可能在其中的空間區域相關聯。

Octant計算一個最終的估計定位區域，該區域包含了系統對目标節點所在位置的最佳估計。一些應用程序可以直接使用這種區域估計。例如，諸如房地産這種的Web應用程序基于浏覽者可能位于的郵政編碼來生成内容。Octant可以将該區域作為貝塞爾曲線的有界曲面或有序的坐标列表提供給這些應用。然而，許多傳統的應用程序以及過去的工作（如GeoPing和GeoTrack）将目标定位到單個點。為了支持傳統的應用程序并提供與一種和以前工作比較的方式，Octant使用蒙特卡羅算法來選擇代表目标位置的最佳估計值的單個點。該系統最初選擇數千個位于估計區域内的随機點。每個點被分配一個基于其距離到其他所選點的總和的權重。經過一些試驗之後，選擇最小權重的點作為目标位置的最佳估計值。這個點保證在估計的位置區域内，即使該區域由不相交的區域組成。理想情況下，Octant的單點選擇接口隻是為支持傳統應用程序的過渡遷移方案。我們希望未來的應用程序能夠充分利用Octant估計面積中的額外信息。

圖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使得網絡運營商能夠僅通過簡單的延遲測量來有把握地确定節點的位置，從而實現新的位置感知服務。