用於表徵基於分組的網絡的端對端路徑的方法和設備的製作方法

2024-02-16 20:57:15

專利名稱:用於表徵基於分組的網絡的端對端路徑的方法和設備的製作方法
技術領域：
本發明涉及網絡領域，特別是涉及一種用於評價基於分組網絡的端對端路徑的方法和設備。
背景技術：
在基於分組的網絡中，經常需要檢測網絡上兩個具體節點之間的通信。該檢測一般可以通過從多個節點中的第一節點請求其他節點環回(loop-back)該第一節點發送的檢測分組來進行。所述第一節點基於收到的回來的檢測分組，從而不僅可以確定與其他節點通信，而且還可以確定分組的往返行程時間。
網絡之間的協議，例如ARPA網際協議(IP，Internet Protocol)，也可提供使用環回檢測分組確定可達性和往返行程時間的功能。因此，在IP網絡中，網間控制報文協議(ICMP，Internet Control Message Protocol)允許控制消息和信息消息(包括回顯請求(echo request)消息和回顯答覆(echo reply)消息)在IP數據報的數據部分中在不同主機的IP軟體和網關之間傳送。ICMP允許的其他消息包括時間戳請求消息和時間戳答覆消息，這些消息使得可以在通行的兩個方向上進行通行時間估算。某些計算機作業系統允許用戶使用名為「ping」的命令發送ICMP回顯請求，用戶能夠指定要確定往返行程時間的檢測分組的數量和大小。
還應注意，在ARPA傳輸控制協議(TCP，Transmission ControlProtocol)中，不斷地進行類似的測量作為傳輸控制進程的一部分。更具體地說，測量分組傳輸與收到從終點節點回來的確認之間的往返行程時間；該往返行程時間不斷地平均為平滑的往返行程時間估算值，然後使用該估算值來控制回傳超時參數(RTO，Retransmissions Time-out Parameter)。
美國專利第5,477,531號提供了用來檢測基於分組的網絡的方法和設備。這種方法檢測基於分組的網絡以確定該網絡上第一節點和第二節點之間的分組傳輸的特性，所述方法包括以下步驟在這些節點之間傳輸分組，在一個節點接收分組，以及使分組的傳輸和接收相關聯以獲得表示傳輸特性的相關數據，其特徵在於，這些分組作為序列傳輸，其中這些分組利用對於該序列變化的一個參數而使得相互之間具有預定關係。獲得的相關數據對這種預定關係是敏感的，使得能夠確定從單個分組的流通中不能觀測到的傳輸特性。
美國專利申請第2002/0080726號提供了用於確定網絡吞吐率(throughput rate)和數據流利用率的系統和方法。通過網絡選擇性地發送和接收多個網絡評估信號(或者說校驗用檢測分組)。響應於這些評估信號，選擇性地確定和存儲網絡評估參數。響應於這些參數，排隊理論分析確定網絡的響應時間和吞吐量特性，包括數據流的容量、利用率和性能。具體地說，這種方法使用不同大小的ICMP Echo分組的均勻脈衝串，這些脈衝串被發送到去往期望終點的網絡路徑上的各主機。隨後對ICMPEcho Reply響應進行分析，該分析對分組如何被操作並且經歷網絡路徑進行了一些假設，具體地說，要求分組沒有丟失並且以與傳輸順序相同的順序到達。
上述美國專利和美國專利申請都傳輸ICMP分組來表徵網絡路徑。處理這種類型的分組可能與其他協議不同，這是由於，例如ICMP速率限制、協議專用路由與阻塞、以及反分布式拒絕服務(DDOS，DistributedDenial of Service)措施。此外，尋址處於源與終點之間的中間主機的傳輸分組經常採用與該終點的路徑相當的另選路由，於是導致源-終點路徑的表徵錯誤。另外，這些形式的評估技術對網絡路徑中的非對稱性敏感。
一種用於表徵網絡的算法是分組對技術，該技術旨在根據連續發送的兩個大小相同的探測分組之間的離差(dispersion)估算出網絡路徑的容量。例如，這種技術旨在估算沿網絡路徑的帶寬和瓶頸的存在。所述方法估算兩個分組之間的相對間隔並且對收集的這種指標進行統計分析。這種技術廣為人知，它源自於Robert Crovella和Mark Crovella所著的「Measuring Bottleneck Link Speed in Packet-Switched Networks」，Performance Evaluation，(「測量分組交換網絡中的瓶頸連結速率」，性能計算)，第27-8卷，第297-318頁，1996年10月出版。然而，因為分組對離差技術的精度低，尤其是存在背景流量(cross traffic)時，因而它們受到了批評。
另一種能夠用於網絡分析的算法是基於分組列車(packet-train based)的算法。具體地，基於分組列車的工具關注分組列車內的分組離差，具有減少了統計方差的優點。此外，它們通過對網絡進行加載並分析對該裝載的阻力確定背景流量。基於分組列車的算法測量每個車廂(其是所述列車的子組件，包括多個分組)的到達時間，而不測量各單個分組的到達時間(在利用分組對離差的例子中是要計算的)。基於分組列車的算法能夠調整車廂的大小以適應與高速網絡相關聯的系統時間解析度或者定時器解析度，而基於分組對離差的算法通常依賴於它們能夠以怎樣的精度測量在網絡上發送的單個分組的時序。美國專利申請第2002/0080726描述了一種基於分組列車的方法。
第三種截然不同的算法採用一種被稱為隨尾(tailgating)的方法，其中通常在大的分組之後立即發送小的分組，這兩個分組作為一對發送。已知由於較大的分組在每一個轉發節點上需要較長的串行化時間，因而大分組通常限制隨後的較小分組的傳輸。在沿到達終點的網絡路徑的一些點上，去除較大分組(通常使用生存時間(TTL，Time To Live)終止的機制)，而較小的分組將單獨完成其旅程。這種方法應用在現有技術中，例如Kevin Lai和Mary Baker在Measuring Link Bandwidths Using ADeterministic Model Of Packet Delay，SIGCOMM(使用確定的分組延遲模型計算鏈路帶寬，美國計算機協會數據通信專業組)，283-294，2000中研究與公開的，並且用被稱為「網絡計時器(nettimer)」的原型手段表述。這種技術的優點是通常消耗較小的網絡帶寬，不依賴於與處理ICMP分組的路由器的行為一致性，並且不依賴於確認的及時遞送。然而，據知這種技術具有較低的精度。
分組列車與分組對離差衍生出的混合方法在Attila Pasztor和DarrylVeitch所著的Active Probing using Packet Quartets，Proceeding of theInternet Measurement Workshop 2002 (使用四重分組的活動探測，Internet計量工作室學報2002)，ACM SIGCOMM中公開。這種混合方法也提供了一種手段用於IP網絡的採樣。在該方法中，TTL終止用來終止「四重分組(packet quartet)」序列中的分組，從而提供了一種獲得與中間路徑跳(hop)相關的統計的方法。這種方法使用了兩對隨尾分組，使得可以從較大分組終止之後剩餘的兩個分組之間的分組對離差中獲益。為了產生這些帶寬特性，獲得最大帶寬和延遲變化分析技術的分析焦點明確地優先集中在延遲最小值方案上。因此，為了確定可適用的分析，該技術分析了特定行為的延遲分布，從而潛在地導致需要多種分析方法。這種估算技術的缺點是高速測量被認為是一個問題。
因此，需要用來表徵IP網絡端對端路徑的新的方法和設備，並具有克服與現有技術有關的問題的能力。
提供上述背景信息的目的是給出申請人認為的、可能與本發明有關的已知信息。不應認為，也不應解釋為，承認前述的任何信息構成了相對於本發明的現有技術。

發明內容本發明的目的是提供用於表徵基於分組的網絡的端對端路徑的方法和設備。依據本發明的一方面，提供了一種用於表徵基於分組的網絡的端對端路徑的方法，所述方法包括如下步驟生成一個或更多個有序分組組，每一個有序分組組包括兩個或更多個標記分組和一個或更多個載荷分組，所有所述分組都設置成沿由源主機和終點主機限定的共用端對端路徑傳輸，其中所述一個或更多個載荷分組設置成經過所述端對端路逕到預定節點，所述預定節點為沿所述端對端路徑的任何節點；從所述源主機沿所述共用端對端路徑傳輸所述一個或更多個有序分組組；收集與所述一個或更多個有序分組組的傳輸有關的數據；以及分析所述數據，從而顯現所述端對端路徑的特性。
依據本發明的另一方面，提供了一種用於表徵基於分組的網絡的端對端路徑的設備，所述設備包括用於生成一個或更多個有序分組組的裝置，每一個有序分組組包括兩個或更多個標記分組和一個或更多個載荷分組，所有所述分組都設置成沿由源主機和終點主機限定的共用端對端路徑傳輸，其中所述一個或更多個載荷分組設置成經過所述端對端路逕到預定節點，所述預定節點為沿所述端對端路徑的任何節點；用於從所述源主機沿所述共用端對端路徑傳輸所述一個或更多個有序分組組的裝置；用於收集與所述一個或更多個有序分組組的傳輸有關的數據的裝置；以及用於分析所述數據從而顯現所述端對端路徑的特性的裝置。
依據本發明的又一方面，提供了一種電腦程式產品，包括計算機可讀介質，一種電腦程式產品，包括計算機可讀介質，所述計算機可讀介質上記錄有電腦程式，所述電腦程式是用來執行一種用於表徵基於分組的網絡的端對端路徑的方法，所述方法包括如下步驟生成一個或更多個有序分組組，每一個有序分組組包括兩個或更多個標記分組和一個或更多個載荷分組，所有所述分組都設置成沿由源主機和終點主機限定的共用端對端路徑傳輸，其中所述一個或更多個載荷分組設置成經過所述端對端路逕到預定節點，所述預定節點為沿所述端對端路徑的任何節點；從所述源主機沿所述共用端對端路徑傳輸所述一個或更多個有序分組組；收集與所述一個或更多個有序分組組的傳輸有關的數據；以及分析所述數據，從而顯現所述端對端路徑的特性。
圖1為起點與終點之間的網絡路徑的示意圖，起點與終點之間包括許多第3層設備，例如路由器或者網關。
圖2為根據本發明一個實施例所述的限定組件的網絡路徑的示意圖。
圖3為根據本發明一個實施例所述的有序分組組的示意圖。
圖4為根據本發明另一個實施例所述的有序分組組的示意圖。
圖5為根據本發明一個實施例所述的有序分組組沿網絡路徑從源主機傳輸到終點主機並且信息傳送到接收主機的示意圖。
圖6為Van Jacobson圖表，表示如何按照分組通過的段的容量變化改變分組的時間分布。
圖7為Van Jacobson圖表，表示標記分組的間隔如何反映沿網絡路徑直至並包括載荷分組終止處的節點的瓶頸或阻力的影響。
圖8圖示了標記分組和載荷分組有序組，表示了根據本發明一個實施例所述的每一個分組識別器。
圖9為示意圖，顯示了有序分組組中第四分組的往返行程時間(RTT)與行程總時間(TTT)之間的差。
圖10為示意圖，顯示了計算到跳h的IP網絡的單向比特率需要的數據，該數據具有相關載荷和標記以及它們的傳輸和接收計時。
圖11為示例柱狀圖，顯示了使用本發明的採樣步驟確定的往返行程時間(RTT)，其中的變化取決於被監測的分組所經受的背景流量。該示例柱狀圖包括該示例的RTT的最小值、平均值與標準偏差的近似識別。
圖12a為當沒有背景流量時在網絡的特定區域中的最大可用比特率的示例的示意圖。
圖12b為當存在背景流量時在相同網絡區域中的可用傳輸比特率的示例的示意圖。
具體實施方式定義術語「源主機(source host)」用來定義分組傳輸始發的網絡位置或節點，以表徵網絡路徑的起點。
術語「終點主機(destination host)」用來定義這樣的網絡位置或節點，該網絡位置或節點相對於特定的源主機定義了端對端路徑。
術語「目標主機(target host)」用來定義將收集與其有關的特徵的網絡位置或節點。目標主機可以處於源主機與終點主機之間，並且任選地可以是終點主機。
術語「接收主機(sink host)」用來定義在該處收集的有關於所傳輸的分組的狀態的信息的網絡位置或節點。該接收主機可以是網絡中的任何節點，包括源主機、終點主機、目標主機或者不在該將被表徵的路徑上的節點。
術語「分組(packet)」用來定義在基於分組的網絡上傳輸的信息。取決於許多標準(包括例如網絡容量和大小實用性)，分組的大小可以有很大的變化。分組為在網際網路或者任何其他分組交換網絡上起點與終點之間路由的單位數據。例如，當一個文件或者其他類型的信息在分組交換網絡上傳輸時，該文件可以被分解成「數據塊」或者分組，該「數據塊」或者分組的大小對於在網絡中路由是有效率的。
術語「載荷分組(load packet)」和「載荷(load)」可互換地用來定義在網絡上傳輸的分組，所述分組提供了對網絡加載以便產生某種響應的手段。載荷分組可以在沿通向指定終點主機的路徑的預定數目的節點阻礙(node traverse)或「跳」之後終止。
術語「標記分組(marker packets)」和「標記(markers)」可互換地用來定義在網絡上傳輸的分組，用於標誌或標記與其一起傳輸的載荷。標記分組用來標記網絡對與其關聯的載荷的傳輸的響應。標記分組對預定的終點主機進行尋址。標記分組可以到達終點主機，或者任選地，如果最初與之關聯的載荷分組已經在之前終止，那麼標記分組可在達到預定的跳數之後終止。
術語「第三層(layer 3)」用來定義提供路由信息、尋址以及使信息能夠在IP網絡上傳輸的其他相關服務的通信模型的網絡層。例如，在普遍參考的稱為開放式系統互聯(OSI，Open Systems Interconnection)的多層通信模型中，第三層是例如與獲知網絡中的鄰近節點的地址、選擇路由、服務質量、以及識別輸入消息並將其從本地主機域轉發到傳輸層(第四層)相關的，其中傳輸層確保了消息的安全到達並且提供了可選的錯誤檢查機制和數據流控制。雖然應注意第三層可能專用於具體的協議，但假定還可以用第三層的定義來定義在任何另外的基於分組的通信模型中的可比操作層。
術語「第三層設備(layer 3 device)」用來定義在被稱為網絡層的基於分組的通信模型的第三層上運行的設備。第三層設備例如可以包括路由器，或者本領域所屬技術人員容易理解的其他與網絡層相適應的設備。
術語「段(segment)」用來定義在第三層上作出響應的鄰近主機之間的網絡路徑部分，其中所述主機可以是源主機、目標主機、接收主機或者終點主機。段進一步包括一臺能夠當作段的開始或者末尾的主機。
短語「高速網絡(high seed network)」用來定義一種能夠以超過10/100Mbps的速率運行的分組交換網絡，或者更一般地說，能夠以超過目前普通區域網路(LAN)的速率運行的分組交換網絡。
除另有定義外，這裡使用的所有科技術語都具有與本發明所屬的技術領域：
的普通技術人員一般理解相同的含義。
本發明提供了一種裝置，用於在獨立地操作終端主機時，實時地、非侵入式地表徵分組交換網絡的端對端路徑以及端與端之間的所有段，並且不需要為操作而遠距離部署代理。本發明可以被有效地描述為一種不用滿載網絡容量或測量返迴路徑的單端技術或有效的單向測量技術。它可以在一定條件範圍內靈活地運行，或者在存在速率限制和反DDOS(分布式拒絕服務)機制時運行。本發明還可以表徵網絡路徑在非ICMP(網間控制報文協議)協議(比如UDP(用戶數據報協議)和TCP(傳輸控制協議))，以及協議/應用專用行為識別方面的效果，例如傳輸成形和速率限制。本發明還是可以升級的，使其能夠表徵高速網絡的傳輸路徑。
本發明提供了一種用來表徵源主機與終點主機之間的路徑的方法和設備，包括表徵源主機與終點主機之間網絡路徑的每一個響應段。本發明包括第一階段數據採集，其中通過發送和接收大小、數量和協議可能改變的專用有序分組組實現網絡路徑的採樣，其中所有分組都從源主機發出並且都尋址終點主機。這些有序分組組包括有策略地排列的標記分組和載荷分組，其中所述載荷分組通常在源主機與終點主機之間的預定節點處終止。在特定有序分組組的載荷分組終止之後，與之相關聯的標記分組提供了捕捉與直到這些載荷分組終止的網絡特性有關的信息的手段。與這些有序分組組和網絡的相互作用有關的信息在接收主機處被收集，該接收主機可以是也可以不是沿源主機與終點主機之間的網絡路徑的節點。對所收集信息的隨後分析能夠表徵沿源主機與終點主機之間網絡路徑的每一段。通過在有序分組組的特徵與所收集的信息之間進行相關，本發明可以併入對所收集信息的進一步分析，從而使能了這樣的手段，該手段在採樣過程中對所使用的有序分組組的特性進行調節，該調節可以使採樣和對網絡路徑的表徵最佳化。本發明提供了一種利用多種協議的手段，從而提供了一種手段，用於選擇對特定協議的網絡響應，同時提供了一種用於跟隨有序分組組並評估網絡對有序分組組的響應的手段。
參照圖1，圖1示出了起點10與終點30之間的可能網絡路徑，其中該路徑可以通過多個第三層設備(例如路由器20)分成許多段。針對本發明，圖2示出了源主機50與終點主機60之間的路徑，其中在源主機與終點主機之間有多個第三層設備或者目標主機70。本發明還併入了接收主機80，其中接收主機可以是沿網絡路徑上的任何一臺主機或者可以是所評價的路徑之外的節點。根據本發明，有序分組組開始於源主機50並尋址終點主機60。這些有序分組組的配置和它們與網絡的相互作用使得能夠沿著從源主機到終點主機的網絡路徑，確定有關於每一臺目標主機70的特性。與採樣會話期間有序分組組的傳輸有關的信息在接收主機80處接收，用於分析。
與網絡連接的是一個或更多個用來沿路徑發送有序分組組並在它們已經經過該路徑後接收該有序分組組或對其響應的裝置。在一個實施例中，有序分組組由分組定序器始發，沿著路徑傳輸到反射點，然後再回傳至分組定序器，並且在這個實施例中，分組定序器可以位於源主機。在另選實施例中，分組定序器位於源主機，用來收集傳輸檢測數據，而另一個分組定序器可以位於接收主機，用來收集與有序分組組或對其響應的接收有關的信息。分組定序器能夠記錄有關於發送分組的時間的信息和收到返回的分組時間的信息。分組定序器還能夠收集例如有關於傳輸的分組類型和收到的分組類型的信息。採樣階段所收集的全部信息都看作是檢測數據。
另外，與網絡連接的還有分析系統，該分析系統用來接收檢測數據並執行期望的分析，如果需要，還包括採樣分析的調整和修改。該分析系統可以包括經編程的計算機，也可以以硬體配置，或者是本領域所屬技術人員容易理解的其他計算系統的形式。分析系統可以與分組定序器寄存於相同的設備，或者位於相同的位置，或者任選地，在物理上與分組定序器分立。例如，分析系統和分組定序器都可以位於源主機，其中該源主機還可以起到接收主機的作用。分組定序器和分析系統的位置由選擇的源主機和接收主機決定。
採樣階段採樣技術結合了「載荷和標記」的使用，其中某些分組起到「加載」網絡以產生某一響應的作用，而其他分組起到「標記」該響應並返回接收主機用來分析的作用。可能有多種載荷和標記的圖案(pattern)配置，其中改變配置可以針對特定的特性來對網絡路徑進行採樣。如圖3所示，最普通的配置包括散布有標記分組110的載荷分組100的有序組。雖然圖3示出了相鄰標記之間載荷的數量是相等的，但這不應當認為是一種限制，而僅僅是有序分組組的較普通配置的一個實施例。某些特性可以使載荷與標記相區分，比如報頭值、協議和大小，其中標記的數量和位置取決於具體實現。所述標記使得可以跟蹤整個有序分組組的位置和行為，而不會導致需要系統開銷和需要跟蹤每一個所傳輸的分組的缺點。此外，可以注意到，在很多實例中，引起來自網絡路徑的響應和觀測該響應都是不能實現的。例如，如果沿網絡路徑發送的所有分組都為ICMPEcho配置，那麼相對於其他協議，沿網絡路徑的速率限制機制將可能改變該路徑的響應。然而，發送其他協議，可能難於觀測期望的響應。因此，為了產生所需響應，通過在所需協議的有序分組組內嵌入產生可容易地觀測響應的分組，可以在期望條件下觀測網絡路徑的功能，然後表徵其功能性。
參照圖4，在本發明的一個實施例中，有序分組組的第一種配置包括跟隨著一系列載荷分組110的第一標記分組100A和最後的第二標記分組100B。在該配置中，在前的標記分組和隨後的標記分組提供了一種標記網絡路徑對其間的載荷分組的響應的手段。
在本發明的一個實施例中，標記分組與載荷分組的大小相同，但是，例如為了確定在期望的採樣會話期間使用的標記大小的最佳選擇，可以調整該配置。標記分組通常為ICMP Echo分組，然而，它們同樣可以使用其他協議(比如UDP或者TCP)來定義，其中可以基於網絡路徑的實現和期望的特性決定協議的選擇。標記通常尋址終點主機，然而也可以選擇沿網絡路徑的其他節點作為標記的期望終點。此外，標記還可以在終點之前的某一節點處終止，然而在這種情況下中，載荷分組在前一節點終止。例如，這種行為可能引起來自標記分組終止處的節點的一些響應。另外，為了識別用於接收有關於該有序分組組的傳輸的信息(例如ICMPEcho答覆分組)的期望位置，還可以對標記進行配置。在本發明中，該期望位置為接收主機，其中接收主機可以是沿正被表徵的網絡路徑的節點或者在該網絡路徑的外部。
在本發明的一個實施例中，載荷分組的大小相同並且通常被創建為從源主機到鄰近目標主機的局部路徑或者段所允許的最大大小MTU(最大傳輸單位)。可使用任何協議(例如ICMP，UDP或者TCP)配置該載荷，然而在本發明的一個實施例中，使用UDP配置載荷。在載荷的配置過程中，它們尋址終點主機，然而在某種條件下，沿路徑的其他節點也可能選作該參數。另外，為了使載荷可以在沿正在表徵的網絡路徑的特定第三層節點或者目標主機處終止，載荷在它們的IP報頭配置有賦予特定數值的TTL(存活時間)值。例如，配置有TTL＝1的載荷將終止在第一跳或者第三層設備阻礙(device traverse)，而配置有TTL＝2的載荷分組將終止在第二跳。一旦載荷在預定跳處終止，有關該載荷與直至該跳的網絡路徑的相互作用的信息將隨後傳送到接收主機。非常重要並需要注意的是，兩個特定標記分組之間的一個或更多個載荷分組配置有相同的TTL數值。
在本發明的一個實施例中，採樣階段開始於對沿通向所選的終點主機的網絡路徑上的各第三層節點進行識別。該識別過程可以使用例如第三層跟蹤路由機制，以確定所識別的終點的可達性和其間節點的數量。隨後，包含載荷和標記的一系列分組發送到終點主機，載荷上設置了TTLExpiry(TTL終止)，以使它們在不同的目標主機上終止。在一個實施例中，載荷可以包括任何優選協議(例如UDP)的分組，並且標記可以包括ICMPEcho分組。終止載荷能夠致使發生終止處的目標主機生成ICMP TTLExpiry消息，然後將這些消息轉發到預先指定的接收主機。例如，如果使用ICMP生成這些標記，則這些標記將繼續到達終點主機，並導致ICMPEcho答覆分組回送到接收主機。任選地，所述標記可能在載荷終止的下一個節點處終止，然後有關標記的TTL Expiry消息回送到接收主機。通過對與有序分組組的傳輸開始時間相關的信息、以及與接收主機所得消息和答覆的接收時間相關的信息進行收集和分析，可以評估出源主機與終點主機之間網絡路徑的每一段的特性。在一個實施例中，源主機還可以是接收主機，而在另選實施例中，終點主機是接收主機。如果不是這種情況，標記和載荷可以被設定以確定一個用於消息和答覆分組傳輸的另外的接收主機。在這種情況下，考慮基於該另外的接收主機位置的消息和答覆分組的傳輸時間的時間增加和減小，還需要例如使用全球定位系統(GPS，Global Positioning System)使傳送和接收定時同步，以獲得等同的精度。
在另一實施例中，為了從終點主機生成錯誤響應，通過以其他協議對標記進行編排可以實現用於獲得對標記分組的響應的等同機制。例如，標記可以使用UDP協議編排並被設置為使用終點主機上的非活動埠。該UDP標記分組可以生成ICMP Port Unreachable(ICMP埠不可達)響應。然而，在任何實施例中，都應當注意，對載荷分組的協議的選擇獨立於對標記分組的協議的選擇。
圖5示出了根據本發明生成的有序分組組的傳輸的示例。有序分組組150在源主機50處創建，並且尋址終點主機60，其中載荷分組設置為TTL等於2，而標記分組位於載荷分組的前後。該有序分組組穿過第一目標主機70A(在該處，分組的TTL減量)，然後沿著第二段到達第二目標主機，在這裡載荷分組終止，並且有關它們沿網絡路徑的傳輸的信息170被發送到用於收集並繼而進行分析的預定接收主機80。作為示例，該信息可以是來自第二個目標主機70B的ICMP TTL Expiry消息的形式。與初始發送的有序分組組相關聯的標記分組繼續沿網絡路逕到達終點主機60，在這裡它們被反射到用於收集並繼而進行分析的預定接收主機80。作為示例，該信息可以以ICMP Echo答覆分組的形式返回到起點的主機。在該示例中，這些標記分組提供與有序分組組和網絡之間直至並且包括第二個目標主機70B的相互作用有關的信息，第三目標主機70C可以不影響返回信息的計時與間隔測量，因為該目標主機不會導致兩個標記分組之間間隔的變化。在載荷分組終止之後，如果這些標記分組中的一個在網絡內經歷了背景流量，而其他標記分組保持原樣，那麼標記分組之間的間隔可能改變。
隨著載荷分組通過網絡路徑，它們受到所經過或者穿過的網絡設備以及與網絡相關的其他方面的影響。例如，網絡路徑中的帶寬收縮、反向通信以及各種變化能夠幹擾載荷，並因而幹擾與之關聯的標記。例如，針對載荷數、分組大小、往返行程時間、行程總時間、分組丟失、間隔以及排序，相對於來自源主機的原始分組，測量TTL Expiry分組和EchoReply分組返回接收主機的定時分布。該數據能夠提供一種評價上述這些方面的效果和其他網絡特性的手段。
圖6示出了低容量段對之前沿較高容量段傳輸的標記分組與載荷分組的間隔的影響。該影響以Van Jacobson圖的形式表述。分組之間的間隔可以在路徑上出現帶寬收縮之處引入。如圖6所示，有序分組組在到達低容量段210之前的高容量段200內間隔緊密。一旦到達低容量區域，分組傳輸速率就會降低，從而致使相鄰分組之間間隔增加。一旦到達隨後的高容量段220，該分組通常不能減小在穿過低容量段過程中產生的間隔，因此分組之間的間隔表示了網絡路徑兩個不同段的傳輸速度之間的相互關係。然而，在沿網絡經歷了背景流量的情況下，分組之間的間隔可能改變，其中，如果這種因素僅影響了有序分組組中的一些分組而不是全部分組，那麼該因素可能減小這些分組之間的間隔，其中背景流量可以導致受影響分組的延遲增加。可以檢測背景流量的存在及其對分組的影響，使得可以將受到背景流量影響的分組與沒有遇到背景流量的分組相區分。
圖7示出了載荷分組穿過低容量段210之後終止後的標記110的可感知間隔，以及與終止有關的消息170的產生。以這種方式，標記110之間的間隔能夠表示例如沿到終點主機的網絡路徑直至並包括與有序分組組關聯的載荷分組終止處的節點的瓶頸的影響。
如果載荷分組終止處的目標主機為瓶頸或者在其後，那麼從載荷所終止的點開始，標記分組可保持其間的間隔，同時繼續到達終點主機。在某種情況下，標記分組可以使到達終點主機的行程均衡而不受任何其他現象(例如隨後的瓶頸和背景流量)的影響。從終點主機反射回來的標記分組同樣可以使到達接收主機的行程不受其他現象的影響。在標記沒有遇到其他可感知的影響的情況下，標記答覆能夠以代表載荷終止處的節點的分組間間隔到達接收主機，從而提供一種表徵網絡路徑段的手段。在標記分組的間隔足夠大的情況中，載荷分組終止後穿過的低容量段不能影響標記分組的間隔。在這種情況中，第一標記分組在低容量段傳輸速度的減小不能導致第二標記分組的進一步延遲，因而標記分組之間的間隔在載荷分組終止之後能夠保持恆定。標記分組之間的間隔通常不會減小，然而，如果例如背景流量與其中一個標記分組相互作用而不與另一個作用，那麼標記分組之間的間隔可能發生減小。
作為示例，在標記答覆的分布中，由於在隊列中彼此相遇而進行通信競爭並被延遲了的標記與標記答覆，或者已經丟棄的標記與標記答覆可以與那些已返回的、沒有受到網絡路徑進一步影響的標記答覆相隔離。在一個實施例中，當收到了與終止的載荷有關的所有答覆，並且標記處於它們在原始傳輸中的順序時，將基於具有最小行程總時間(TTT)的標記，來選擇用於最大比特率分析的來自網絡的響應。其他分析可能具有其他的數據選擇要求。為了顯示有關網絡路徑的更寬範圍的特性，可以維持並分析針對載荷和標記的答覆分組的分布。這些特性可以基於比如分組大小、分組計數、協議和TTL等參數，這些參數在有序分組組初始傳輸時已經設定。通過對有關初始傳輸的標記答覆的分布、有關傳輸的信息以及有關載荷的終止和終止消息接收的分析，從源主機到預定終點主機之間的端對端網絡路徑可以逐「跳」或者逐段地表徵。該網絡路徑的特性包括這樣的指標，該指標包括單向最大比特率、單向傳輸延遲、單向延遲變量和單向可用比特率。
根據以上所述，清楚了基於分組的網絡的速率容量不會影響本發明採樣階段收集用於隨後分析的相關信息的能力，從而使得即使對高速網絡也能表徵整個網絡路徑。一個典型的限制因素是有序分組組可以安全地放置在網絡路徑上的精度，其中所述因素取決於源主機的網絡接口卡(NIC，Network Interface Card)。為了提供期望的特性水平，必須能夠對NIC進行充分控制，以便收集的有關響應的傳輸和接收的時間的數據具有足夠的精度。
實現表徵的分析階段可以根據預定的一系列有關於網絡路徑能力和以所需方式在網絡上布置所需分組的能力的假設，來限定實現表徵的分析階段。因此對於這種分析，可以假定存在一種用於分組製備和傳輸的機制，能夠降低作業系統和其他限制進程對傳輸速率的影響，從而作為鄰近系列的一部分被發送的分組在時間上分開得最小。因此，來自源主機的有序分組組的傳輸速率主要由源主機的NIC的最大傳輸容量限制。該參數例如由第二層規格(例如對於高速乙太網為100Mbps)以及可能存在於IP網絡的任何第三層影響來限定。
儘管下面執行分析的程序採用了傳送特定的有序分組組，但是本領域所屬技術人員容易理解如何使用另選設置的有序分組組擴展所提供的步驟順序來確定所需的指標，因而同樣被認為在本發明的範圍之內。
在本發明的一個實施例中，圖8示出了一個有序分組組，該有序分組組將用來對網絡進行採樣並且提供了對網絡路徑進行期望分析所需的原始數據，其中識別了有序分組組中的每一個分組的身份。被稱為載荷分組Li的連續傳輸的分組系列(其中i為此系列中的指數並且等於1～n之間的整數)被設置為當以源主機NIC的最大傳輸容量傳輸時，這些分組之間的間隔最小。該有序分組組還包括兩個附加的分組，其中一個在載荷分組之前另一個在載荷分組之後，並且這兩個附加分組被分別稱為標記分組M0和M1。相對於載荷，這些標記同樣連續傳輸，其中標記分組與鄰近的載荷分組之間的間隔被最小化。
可以經由受評估的網絡發送各分組，將終點主機指定為從源主機可訪問的具體IP位址，將源主機指定為接收主機。與兩個標記分組關聯的TTL參數可以設置為最大允許值，例如TTL＝255，而與各載荷分組關聯的TTL參數例如設置為整數值h(0＜h＜256)。雖然載荷分組通常在源主機與終點主機之間的目標主機終止，但這種結構通常允許標記分組到達終點主機。在特定的有序分組組中，每一個載荷分組的TTL值都賦予相同的數值，然而與其他有序分組組中的載荷分組關聯的TTL值是經變化的，因此應當把它看作對應不同目標主機的變量。當h值小於源主機與終點主機之間路徑上的第三層跳數目時，載荷分組Li將會終止，並且由目標主機將「TTL終止」信息發送到接收主機，從而針對每一個終止的載荷分組發送一條消息。在本實施例中，源主機與接收主機是相同的，然而這可能不是實際情況，因而需要糾正所收集的信息來考慮另選的配置。與特定有序分組組關聯的標記分組將傳送到終點主機而不管關聯的載荷分組是否終止。一旦到達了終點主機，該終點主機將向接收主機發送響應分組(例如以Echo Reply分組的形式)，其中對於每一個標記分組都發送一個Echo Reply。在另選的實施例中，標記分組可以向終點主機請求ICMP埠不可達分組，或者標記分組可以向終點主機之前的一些節點請求TTL Expiry分組。
在一個實施例中，使用一種特性化了的針對UDP協議的協議限定載荷分組，並且該載荷分組具有相同的大小SL。標記分組為ICMP Echo分組，並且都具有相同的大小SM，該大小可能與載荷分組的大小SL不同。從載荷分組終止處的目標主機發送到接收主機的ICMP TTL Expiry分組可具有另一大小SE，該大小可能比較小，例如64位元組。從終點主機發送到接收主機的ICMP Echo答覆分組與原始ICMP Echo標記分組具有相同的大小SM。
在另選的實施例中，各標記分組可能具有不同的大小，致使ICMPEcho答覆標記分組從終點主機發送到接收主機，並與它們各自的原始ICMP Echo標記分組的大小相同。在另外的實施例中，標記分組可能為某一其他的協議(比如UDP)，並且不管它們的原始大小都可以生成從終點主機到接收主機的ICMP埠不可達分組，該分組大小比較小，例如64位元組。
在一個實施例中，為了實現端對端採樣和網絡路徑分析以及為了實現逐段地表徵所選的基於分組的網絡路徑，下面提供了以下的步驟順序。選擇目標主機，可選地，可以確定第三層跳的數目H以及源主機與終點主機之間的所有可見第三層跳的相應IP位址，從而識別源主機與終點主機之間的所有目標主機。隨後，多個序列的相鄰的載荷分組和標記分組的有序組被發送到目標主機的IP位址。與不同的有序分組組的載荷分組關聯的終止變量TTL可以設置為在1～H範圍內的某值，從而使得可以收集來自源主機與終點主機之間直至並包括終點主機的所有目標主機的數據。所有分組的傳輸時間都針對各探測分組記錄在源主機上，而每一個收到的終止或答覆分組的返回分組時間都記錄在接收主機上，其中將有關發送分組和從其返回的所得返回信息的各定時聯繫起來以進行分析。對於特定TTL值，對分組序列內的每一個分組的定時進行統計，並且對於每一個TTL值，一旦記錄了足夠的統計，該統計就可以用來獲得與特定TTL值識別的目標主機相關聯的指標的範圍。該過程可以導致針對每一個單獨跳確定的指標。
根據本發明的網絡路徑採樣階段的結果包括統計值的收集，該統計值歸結於所採樣的端對端網絡路徑內的每一個所選的目標主機。與採樣階段中所傳輸的載荷分組關聯的TTL值提供了一種使收集的信息與特定目標主機具有相關性的手段。因此，各目標主機都能夠與TTT的統計數值相關聯，所述TTT可以定義為從源主機開始傳送序列中的第一個分組直到接收主機完成對該序列的特定分組的確認接收為止的時間。另外，每一個目標主機都能夠與來自TTT分布的結論相關聯，比如丟失和重新排序。
單個分組的定時可以基於在傳輸的源主機上當分組完全離開網絡接口時的本地時間與在接收主機上當完全收到確認分組時的本地時間之間的差異。在一個實施例中，定時是相對於所發送和接收的分組的「尾沿」。該測量值可以被稱為RTT(往返行程時間)並且與TTT有關，其中RTT等於TTT減去第一個分組傳輸直到相關分組所需的時間。圖9在一張標準時間表中示出了序列組中第四個分組的TTT與RTT之間的關係，其中時間沿圖的縱軸增加。
在採樣階段中，根據收集的信息確定了表1中每一個標識出的符號代表的值。表1介紹了描述應用於所採樣的分組統計的分析所需要的術語。每一個指標採取適當過濾並應用到分組定時的分布上，以便僅挑選出符合條件的樣本。例如，在前標記和在後標記的TTT最小值可以要求兩個數值來自相同的有序分組組。表1中定義的數值能夠評估有關基於分組的網絡的段的特性，包括單向最大比特率、單向傳輸延遲、單向延遲變量和單向可用比特率。
下面，考慮以下假設，提供了以下根據一個實施例獲得這些特性的過程。接收主機與源主機是相同的。當載荷分組為UDP並且它們的TTL設置為使限定的目標主機比終點主機遠時(例如與載荷分組關聯的TTL值大於源主機與終點主機之間的跳數)，終點主機將產生ICMP埠不可達確認分組。返迴路徑的等待時間與網絡路徑的邊界部分相稱，並且為使各目標主機收集的信息具有統計顯著性，已經對網絡進行了足夠的採樣。假定一旦載荷分組終止，標記分組就相互獨立，因此它們不會在網絡路徑上的第三層設備隊列中相遇，或者，即使它們相遇，該情況可以被探測到並且受影響的分組也會被正確地分析。
表1
單向比特率正如本領域所屬技術人員容易理解的那樣，單向比特率可以認為是比特在起點與終點之間單向傳輸的最大速率。如圖6所示，當有序分組組中的所有分組到達比特率瓶頸(例如低容量段)時，鄰近分組尾沿之間的時間間隔將會增大。在沒有任何其他影響(例如隨後的網絡容量減少或者背景流量)的情況下，該特性的間隔將持續。後面的收縮(例如進一步減小網絡容量)可能帶來分組之間更大的間隔。一旦與特定有序分組組關聯的載荷終止，與之關聯的兩個標記分組尾沿之間的相對間隔就會保持固定並且代表載荷終止時刻存在載荷。因此，例如假定載荷分組終止後標記分組之間有充分的間隔並且不存在背景流量對其中一個標記分組的影響，則所述標記的間隔可以作為網絡路逕到達但不超過所關聯的載荷的終止點的性質的殘餘指示(residual indication)。
可以增加或減少標記之間的間隔的情況同樣增加了有關標記分組響應的傳輸與接收之間的總時間。通過選擇最小時間Λ0和Λ1，端對端傳輸並且沒有遇到任何其他通信的分組最可能用來評估單向比特率。收集充足的統計樣本可以確保這些分組中的至少一對的最小時間代表該特性作為第一序列評估。網絡對其他參數(例如分組大小、載荷數目和協議)的敏感性可以進一步改善網絡路徑的表徵。
例如，參照圖10，圖10示出了計算單向比特率所需數據的示意性表述。與該有序分組組的載荷分組有關的TTL被設置為h，因此它們在穿過目標主機h後終止，並且TTL Expiry分組105被發送到指定的接收主機。直到載荷終止的點的數據被傳輸的速率(單向比特率Bmax)可以被計算為兩個標記(包括標記的尾沿之間的所有標記的部分)之間的比特總數，並且定義如下 單向傳輸延遲正如本領域所屬技術人員容易理解的那樣，單向傳輸延遲可以定義為在IP網絡中假想的零字節分組從源主機傳輸到終點主機所用的時間。對於本發明，TTL Expiry的確認從目標主機返回的最小RTT代表了分組完成從源主機到目標主機並且返回的往返行程的傳輸時間。分組在各中間節點串行化的時間包括在這些RTT時間中，其中串行化時間是分組大小的函數。在一些情況下，發送的分組的大小可能與收到的分組的大小不同。對於一個零字節的分組，從源主機到目標主機的傳輸時間可以是該零字節分組的RTT的一半，這是因為由於該分組大小為零字節並且假設返迴路徑對稱，沒有考慮有關串行化的時間。
在一個實施例中，假設載荷分組按順序到達目標主機，第一載荷分組L1的第一最小時間α1應該是最小的。該值包含第一標記分組M0和第一載荷分組L1傳輸到目標主機的時間，加上與L1終止相關聯的TTLExpiry分組返回到接收主機的時間，其中α1可以如下地確定1=t1-wayprop+tser(S(M0))+tser(S(Li))+t1-wayprop+tser(S(L1-expiry))---(2)]]>=2tprop+tser(SL+SM+SE)---(3)]]>其中tprop為單向傳輸時間，tser(Sx)為SX大小的分組的單向串行化時間。
因此，通過改變載荷分組的大小SL，或者標記分組大小SM，在採樣階段中可以產生RTT最小值α1的數值範圍。假設α1與分組大小SX線性相關，對於零字節大小的分組SX＝0，它的α1的映射數值可以通過下列公式計算，接下來單向傳輸可以估計為α1(0)/2。
α1(0)＝α1(Slarge)-Slarge×[(α1(Slarge)-α1(Ssmall))/(Slarge-Ssmall) (4)其中α1(SX)為值SX＝SL+SM+SE的最小TTT，並且SL與SM二者具有不同的大小，因而Slarge＞＞Ssmall。
單向延遲變量正如本領域所屬技術人員容易理解的那樣，單向延遲變量可以定義為分組沿特定路徑的傳輸時間範圍，並且可能與系統中出現的「抖動」有關。該指標代表分組延遲的分布。例如，在繁忙的網絡中，隨著背景流量的水平在網絡中動態變化，各分組可能表現出獨特的延遲。在本發明的情況下中，單向延遲變量定義為分組從源主機傳輸到目標主機的所用時間的變化，因為它可以從一系列的有序分組組中的特定分組隨時間的TTT分布中推斷。
在本發明採樣階段提取的載荷的TTT值τi可以表示其分布的關鍵指標。圖11示出了在簡化的單個分組的情況下(在這種情況下，RTT等於τ0，僅包含一個分組的有序分組組的TTT值)RTT的典型分布，其中x軸代表RTT，單位毫秒(ms)，而y軸代表特定RTT的出現頻率。另外，還示意性地表示了該典型分布的最小時間300、平均時間310和標準偏差320。該RTT分布可以是例如分組大小或者分組類型的函數。有序分組組的TTT值τi的分布在本質上是相似的，並且可以從單獨的RTT分布中導出。
代表單向延遲變量整體分布的近似單值表達可以等於變量係數CoV，該變量係數定義如下 其中所選的標準偏差和平均值通常針對第一個載荷分組或者最後一個載荷分組的TTT而言。
該單向延遲變量還可相對於所發送載荷分組的大小或者數量來表示。然而，TTT平均值的使用包括了對有關返迴路徑性質的假定，即它與邊境路徑在等待時間上是對稱的，並且限制作用(比如反向通信或者協議專用速率限制)在返迴路徑上可以忽略。
單向可用比特率單向可用比特率可以用來描述應用中可用的最大比特率Bmax的百分比。在背景流量和其他隨時間變化的限制作用存在時，可用比特率通常隨時間變化。可用比特率的任何指標表示隨時間的粗略打磨(coarse-graining)或者平均。本發明所考慮的可用比特率的值表示在進行統計採樣的整個過程中可用比特率的平均值。可用比特率的平均值Ai(T)可以定義如下
Ai(T)=BmaxT0T(1-(t))dt---(6)]]>其中λ(t)為關於時間的連續函數，表示背景流量佔據總容量的分數。
應當注意，網絡通信實際上是離散的，因為在給定的任何時刻分組都不能部分地佔據網絡鏈路。當在時刻t路徑無競爭的背景流量時，函數λ(t)賦值為0，而當路徑包含背景流量時，賦值為1。當該粗略打磨的周期T遠大於任何分組沿網絡路徑傳遞到給定點所需的時間時，可以有效地近似認為λ(t)是連續的。
假定特定的端對端路徑提供了從源主機到目標主機的單向比特率Bmax(推導的Bmax)，則第一個標記分組M0的尾沿與最後一個標記分組M1的尾沿之間的時間可以涉及該最大比特率。如果假定可用比特率為最大比特率的簡分數x×Bmax，那麼分數x將決定從源主機到目標主機傳遞相同量的數據所需總時間的增加，並且定義如下發送的比特總數＝Bmax×(t1-t0)＝Bavail×(t2-t0) Bavail＝Bmax×x (7)其中可以用最小TTT(α)和平均TTT(τ)來表達分數x＝(t1-t0)/(t2-t0)，因此x＝α/τ。
作為示例，圖12示出了可用比特率和最大比特率之間比較的示意圖。具體地，當在一部分網絡中不存在背景流量時，可用比特率將是最大比特率，並且如圖12(a)所示，第一個標記分組的尾沿與最後一個標記分組的尾沿之間的時間表示為t1-t0。如圖12(b)所示，在存在背景流量時，可用比特率為最大比特率的分數，第一個標記分組的尾沿與最後一個標記分組的尾沿之間的時間表示為t2-t0。可以注意到，t2大於t1，因此，在存在背景流量時，相同量信息的傳遞時間將增加。
取決於採取的假設以及包含的網絡影響，可用比特率Bavail可以用有序分組組中載荷的第一個分組和最後一個分組來定義，或者用標記分組來定義。因為反向通信或者其他限制作用都潛在地對傳輸分組的傳遞敏感，所以載荷的第一個分組可能是最具代表性的。任選地，可以假定載荷的存在可以使反向通信的變化率穩定並且最後一個載荷分組的使用是合理的。使用標記分組需要一些關於經過目標主機的限制作用的假設，因為標記的平均TTT與最小RTT不同，可能包括一些沿網絡路徑的在載荷終止之後的附加的瞬時延遲。應當注意，使用平均TTT意味著有關相對於邊境路徑的返迴路徑性質的假設可適用於給定的情況。
自適應採樣和測試流程正如本領域所屬技術人員容易理解的那樣，基於分組的網絡路徑的性質可以是略微變化的。可能針對表徵過程所佔用的時間優化路徑和其元素的表徵。根據本發明的一個實施例，通過使用自適應採樣和相關分析的應用，可以最優化採樣過程。這種自適應採樣過程從評估預定的指示器開始，這可以通過使用非最佳採樣技術產生。隨後，為了改進採樣技術，進行一個或更多個自適應操作。最後，為了確定是否已經進行了充分的採樣以將被評價的網絡路徑表徵到期望的精度水平，使用了收斂過程。
在一個實施例中，自適應過程檢查原始分組定時以及次最佳採樣技術的圖案的丟失值，其中這些圖案稱為指示器。從採樣的觀點出發，這些指示器使得能夠決定另選的採樣技術(測試的網絡路徑將以一種改進的方式響應該技術)。該自適應過程可以反覆地對採樣技術進行更替或者自適應，直到可以確定對測試的網絡路徑最有效的採樣技術。另外，可以針對與測試的網絡路徑的一個跳，與其他跳隔絕地進行自適應過程，或者可以任選地基於網絡路徑跳的整個序列或子序列進行自適應過程。
在一個實施例中，採樣結果中存在指示器可以表示已經使用了次最佳採樣技術。可替換地，在採樣結果中的零指示器可以表示採樣技術對測試的網絡路徑的表徵是有效的。在特定採樣結果中還可能有多個指示器，多個指示器可以表示多重次最佳採樣技術的參數，或者多個指示器可以表示單一的更專用的次最佳採樣技術的參數。
在一個實施例中，自適應操作限定了對採樣技術及其參數的變化，其中每一操作都可以設計為對特定網絡環境組的調節和補償。單一操作或者多個操作可以運用於採樣技術。此外，例如一項操作可以重複地使用，或者交替地逆向使用，其中此操作的效果被取消以產生相反的作用，從而例如提供了一種從測試的網絡中展現所需效果的手段。
在一個實施例中，存在於特定採樣技術的採樣結果的特定組中的一個或更多個指示器的組可以決定用於產生更加有效的採樣技術的操作。例如，基於上述指示器，一項操作或者多項操作可以應用於當前的採樣技術參數。例如，自適應過程可以繼續監視次最佳採樣技術指示器的採樣結果，並隨後對該採樣技術反覆地進行操作，直到發現最有效的技術。在一個實施例中，僅當充足的證據表明該自適應將產生更精確的結果時，才對採樣技術進行自適應。
在一個實施例中，執行了收斂性過程，其中這種過程是一種自適應分析，該分析可以檢查為了精確確定網絡性能特性所需的穩定性而收集的樣本。該收斂性過程可以確定已經收集的測試樣本的數量是否足以獲得穩定性，並且如果不能獲得，該收斂性過程可以指示大約還需要多少測試樣本以獲得穩定性。
在本發明的一個實施例中，在自適應過程中，可以保持過去的自適應的歷史記錄，並且在自適應過程中，該歷史記錄可以在對採樣技術參數作出變化之前查閱。在一些情況中，被設計用來影響的採樣技術參數的自適應可能不會對隨後的採樣產生期望的作用。當指示器以及隨後的一項或多項自適應操作不產生期望的作用時，該自適應過程可以限制對其執行自適應的指示器的重要性。以這種方式，該自適應過程降低所選指示器的影響，該指示器在過去對於受評價的特定網絡路徑已經失效。
指示器指示器是採樣結果中不理想的特性或者圖案，代表了一種或更多種次最佳採樣技術。採樣結果中的零指示器可以表示該採樣技術對測試的網絡路徑的表徵是有效的。然而，採樣結果中的零指示器僅表示該採樣技術僅對限定的指示器表示的特徵組有效，也就是說沒有不理想的特徵。
在一個實施例中，次最佳採樣技術參數或者網絡壓力的幾個指示器可能來自原始分組定時和丟失的值，所述網絡壓力或者是有意的網絡安全機制或者是無意的網絡缺陷。這些指示器包括，但不是全部包括標記重排、標記壓縮、載荷重排、標記丟失率、載荷丟失率、報告的網絡錯誤、慢的端主機以及這些條件的特定組合。
下面提供一種從採樣過程中收集的數據確定這些指示器的方法，然而容易理解，可以獲得每一個指示器的替換的定義。
當網絡傳輸過程中隨尾標記通過引導標記時，標記重排發生。因此，通過比較引導標記分組和隨尾標記分組的接收時間可以提供標記重排指示器，其中較小隨尾標記的接收時間表示網絡傳輸過程中標記改變的位置。
標記壓縮是標記重排的較緩和形式，其中標記分組被壓縮，即使得其相互更接近，但是不改變接收次序。將引導標記和隨尾標記在傳輸時間上的差異與這些相同分組之間在接收時間上的差異進行比較，可以提供標記壓縮指示器。在預定的閾值內較小接收時間的變化量，可以表示與隨尾標記相比，引導標記在網絡傳輸過程中被不相稱地延遲了。
在網絡傳輸過程中，當載荷分組改變次序時，發生載荷重排。載荷重排指示器可以被認為是與標記重排指示器同義，只不過是基於載荷分組定時。
標記分組丟失指示器可以是一個或更多個標記分組中丟失的觀測結果，而載荷丟失指示器可以是一個或更多個載荷分組中丟失的觀測結果。
此外，報告的網絡條件可以是來自網絡設備或者第三層設備的關於網絡錯誤或者網絡壓力的明白指示。這些報告的網絡條件指示器在基於分組的網絡中通常但不限於採用ICMP消息的形式。
慢的端主機指示器可以定義為隨尾標記分組與引導標記分組TTT之差，與最後載荷分組與最前載荷分組TTT之差的比，其中比值充分大於1時可以表示慢的端主機。
在一個實施例中，對於基於分組丟失的指示器，當從初始發送分組直到經過合理量的時間而沒有收到確認答覆分組時，認為分組丟失。在將分組分類為丟失之前的合理量時間的界定可以由測試的網絡路徑決定，並且可以在普通基於分組的網絡情況中極大地變化。本領域所屬技術人員容易理解，有一些眾所周知的用於確定所期望分組經過時間的機制，這些機制可以用來定義合理量的時間。在另選實施例中，否定確認可以用來判斷分組的丟失。
自適應操作在一個實施例中，利用自適應操作來優化活動的採樣技術，並且自適應操作可以有以下的調整，該調整例如包括改變載荷數、改變載荷大小、改變標記大小、逐漸改變標記大小、逐漸改變載荷大小、改變載荷分組參數、改變標記分組參數以及改變迭代數量。
在本發明的一個實施例中，自適應操作定義為1)通過在一定限度內增加或者減少載荷數目的方式改變載荷數目，而可以改變對測試的網絡路徑的需求。增加載荷數將產生對網絡和目標主機的更多需求，而減少載荷數具有相反的效果。2)通過在一定限度內增加或者減少載荷大小來改變載荷大小，可以避免一些類型的分組過濾和避免幹擾採樣過程的網絡缺陷狀況。3)通過在一定限度內增加或者減少標記大小來改變標記大小，可以改變對測試的網絡路徑和終點主機的需求。例如，增加標記大小對端主機和將端主機連接到其餘網絡路徑的網絡產生更多需求。4)逐漸改變標記分組大小可以要求獨立地改變引導標記和隨尾標記的大小，以在引導標記小於隨尾標記時引起向前的斜率，或者在引導標記大於隨尾標記時引起向後斜率。以這種方式改變標記分組大小可獨立改變各標記分組的生存性以及定時特性。5)逐漸改變載荷分組大小可以在載荷組內對所有的分組引起向前或向後的斜率。以這種方式改變載荷分組大小可以改變載荷分組作為一個整體的生存性以及定時特性。6)改變載荷分組參數可以在運用各種探測分組設置時探究網絡特性。可以改變的載荷分組參數包括，例如網絡協議和網絡服務類型等。具有不同分組參數的載荷分組可能使用到達相同主機的不同網絡路徑，可能具有不同的響應定時和丟失特性，還可能應用了不同的網絡策略。7)改變標記分組參數可以在運用各種探測分組設置時與端主機的響應配合探究網絡特性。可以調節的標記參數包括，例如網絡協議、生存時間以及協議專用參數(比如埠號)。具有不同分組參數的標記分組可使用到達目標主機的不同網絡路徑，可能具有不同的目標主機響應定時和丟失特性，還可能應用了不同的網絡策略。8)改變所執行的、用以計算高層網絡指標(例如可用帶寬、單向比特率和單向傳輸延遲)的迭代數量和/或樣本數量。在對網絡進行採樣時，同樣不需要對網絡進行過度採樣，此時需要該自適應操作。例如，過多採樣可能將遠程影響併入性能測量值以及不必要的檢測時間和網絡通信。相反的是，過少的樣本數量不可能獲得網絡真實的性能，導致網絡性能評估的精確度低。
下表描述了依據本發明實施例的指示器、所需的預設條件和自適應過程的響應。在本發明的一個實施例中，在沒有滿足所需的預設條件時，可以有針對存在於採樣結果中的特定指示器的已定義的響應。在這種情況下，自適應過程的歷史記錄可以用來確定最有效的次最佳檢測方法，例如可以用來表徵正在評估的網絡。
表2
收斂在一個實施例中，與自適應過程關聯的收斂過程提供了一個或更多個有關於精確網絡性能表徵所需的採樣數量的評估量，並且還可以確定是否進行了足夠的採樣。例如，網絡採樣過度或網絡採樣不足都是不期望的。例如，如果進行了過多的採樣，採樣處理可能無意中獲得可能影響網絡性能指標的遠程影響並且不必要地增加了檢測時間和網絡負荷。相反的是，如果進行了過少的採樣，從這些樣本中獲得的網絡性能表徵將會有較大的置信區間，降低了計算結果的有效性，即它的精度。
在一個實施例中，收斂過程可以估算採樣期間與其自身有關的收斂指示器。在一個實施例中，有三個與網絡性能表徵有關的收斂指示器，每一個收斂指示器可以捕捉非瞬時特性、瞬時特性或者診斷特性之一的穩定性，其中非瞬時特性或者指標不隨時間改變，瞬時特性或者指標隨時間變化，而診斷特性可以形成有關網絡功能異常的推斷基礎。
在本發明的一個實施例中，在設定一些合理的漸近值之前，可以監視收斂指示器接近它均衡值的速率。為了確定所選收斂指示器相對於採樣速率的變化速率，本發明在此方面的實現是基於收斂指示器的當前統計值與以前值的比較。例如，如果系列中特定分組的最小傳輸時間對於最後的x次採樣沒有變化，那麼基於這些最小值的任何測量都將認為相對於預期值是穩定的。
在一個實施例中，這三個收斂指示器是單獨基於分組定時和丟失分布的，並且不需要更高層信息或者訪問大量歷史記錄信息。上述瞬時網絡特性指示器是所選分組(通常為最後的載荷分組或隨尾標記分組)的RTT或TTT的平均值。上述非瞬時網絡特性指示器是一個分組或者混合分組(通常為標記分組)的最小分組的TTT變化量。上述診斷網絡特性指示器是特定樣本中分組系列的各載荷分組和標記分組的分組丟失分布。
在一個實施例中，收斂過程包括五個階段，其中對每一個新樣本調用前三個階段，而剩餘的兩個階段周期性的或者根據要求調用。以這種方式劃分階段能夠允許具有更高計算要求的函數被以更低頻率調度，從而降低對收斂分析的整體計算要求。具體地，針對相對於累積樣本的穩定性，收斂過程在整個採樣期間檢查收斂指示器。當累積的樣本的分布精確地估算出總體分布時，該樣本分布被認為已經收斂。因此，當樣本分布已經收斂時，增加新樣本到該分布將不能明顯改變該分布。
在本發明的一個實施例中，收斂的五個階段是1)百分比變化函數；2)二進位串編碼器；3)熵編碼器；4)熵分析函數；以及5)收斂指示器穩定性函數。
收斂的第一階段是由百分比變化函數提供的，該百分比變化函數比較樣本與存在的收集樣本結合前後的收斂指示器。此外，可以組合一個或更多個百分比變化函數以形成用於收斂的這一階段的綜合百分比變化函數。例如，針對非瞬時網絡特性的樣本百分比變化的實現可以包括計算引導標記和隨尾標記的最快TTT時間之間的百分比變化，和可以作為整體百分比變化函數的兩個收斂指示器之間的最大百分比變化。
收斂的第二階段是由二進位串函數(該二進位串函數對0和1的串進行編碼)提供的，把單個的數位添加到用於所收集的各樣本的串中。當特定樣本的百分比變化函數結果大於預定的閾值時，該函數添加1，否則添加0。
收斂的第三階段是由熵編碼器提供的，該熵編碼器從二進位串中刪除冗餘信息以產生熵串。當進行採樣時，二進位串為使用遊程長度編碼方法形式編制的熵。任選地，可以用任何熵編碼器來代替遊程長度編碼器。在另一個實施例中，採樣實現熵編碼器不需要逆向轉換，於是在執行收斂過程中可以改進時間和空間要求。
收斂的第四階段是由熵分析函數提供的，該熵分析函數比較包含在熵串較早部分中的熵的量，確定包含在熵串較晚部分中的熵的量。通過檢測在熵編碼的串中的這些部分的長度可以估計在串不同部分中的熵的量。相對於輸入的串長度，較長的熵串表示了較多的熵，而較短的串則表示了較少的熵。例如，當全部樣本穩定時，串的末端包含較少的熵。
收斂的最後階段是通過評估收斂指示器穩定性(檢測在二進位串末端的相對於串剩餘部分的熵)提供的。
在一個實施例中，收斂指示器穩定性評估的樣本實現將串分成最小的熵串和剩餘串。該最小熵串通過在熵串中搜尋包含最後二進位數位並且包含最少量的熵的子串而發現。剩餘字符串與最小熵串的熵值之比構成熵比。熵比可以任選地映射到函數上，該函數將熵比轉換成適當比例百分比收斂值。在該實現中，該比值可以映射到如下形式的二次函數上 在另選實施例中，收斂指示器穩定性的樣本實現計算出遊程長度編碼串數值的第一統計矩和第二統計矩，也就是遊程長度矩(run-lengthmoment)。最後遊程長度值與遊程長度矩的正3-sigma值之比構成了熵比。然後該熵比映射到如下形式的函數上(9)比值＝收斂％測試流程邏輯在本發明的一個實施例中，測試流程可以修改為自適應採樣過程的反饋過程的一部分，其中採樣階段的結果可能更改隨後選擇的採樣參數以及以後採樣對象的選擇。
該測試流程邏輯能夠控制對自適應操作所述的機制和收斂。這種邏輯還可以識別並消除測量過程的冗餘、條件、選項或其他不適宜實現測試目的的情況。
在一個實施例中，測試流程邏輯需要在完成測試平衡之前估算源主機與終點主機之間的連通性。關於參數化，因為超過了路徑MTU的分組通常丟失，因而從源主機到終點主機的路徑MTU的測量值建立了可以有效地被使用的最大分組大小。例如，在複雜的實現中，針對分組丟失圖案，可探測並識別網絡路徑中的速率限制，因而採樣階段自適應以避免或者考慮所探測到的速率限制的影響。另外，例如採樣階段中一個或更多個指示器的緩慢收斂或者沒有收斂可能引起選擇最佳採樣模式的自適應循環。
變型例應該理解，雖然出於說明的目的在此描述了本發明具體的實施例，但是在不脫離本發明的精神和範圍內可以進行各種變化。具體地說，提供用於根據本發明的方法控制計算機的操作和/或構成本發明系統的組件的電腦程式產品或程序元件，或存儲機器可讀的信號的程序存儲器或存儲裝置(比如固體或流體傳送介質、磁芯纜或光纜、帶或盤等)，都在本發明的範圍內。
此外，該方法的各步驟可以在任何通用計算機(比如PC機、伺服器等上)執行，並且與由任何程式語言(比如C++、Java、Pl/l等)生成的一個或更多個程序單元、模塊或對象(或其一部分)相對應。另外，每一步，或者完成所述步驟的文件或對象等，可以由為此目的設計的專用硬體或者電路模塊執行。
如此描述了本發明的實施例，很明顯這些實施例可以以多種方式變化。這些變型不應被認為脫離了本發明的精神和範圍，並且所有對本領域所屬技術人員來說顯而易見的改變都包括在所附權利要求
的範圍內。
權利要求
1.一種用於表徵基於分組的網絡的端對端路徑的方法，所述端對端路徑包括兩個或更多個節點，所述方法包括如下步驟a)生成一個或更多個有序分組組，每一個有序分組組包括兩個或更多個標記分組和一個或更多個載荷分組，所有所述分組都設置成沿由源主機和終點主機限定的共用端對端路徑傳輸，其中所述一個或更多個載荷分組設置成經過所述端對端路逕到預定節點，所述預定節點為沿端對端路徑的任何節點；b)從所述源主機沿所述共用端對端路徑傳輸所述一個或更多個有序分組組；c)收集與所述一個或更多個有序分組組的傳輸有關的數據；以及d)分析所述數據，從而顯現所述端對端路徑的特性。
2.如權利要求
1所述的方法，其特徵在於，所述收集數據的步驟在接收主機進行。
3.如權利要求
2所述的方法，其特徵在於，所述接收主機是源主機。
4.如權利要求
2所述的方法，其特徵在於，所述接收主機是所述端對端路徑外的節點。
5.如權利要求
1所述的方法，其特徵在於，所述生成一個或更多個有序分組組的步驟包括用生存時間值配置所述一個或更多個載荷分組。
6.如權利要求
1所述的方法，其特徵在於，所述生成一個或更多個有序分組組的步驟包括配置所述一個或更多個載荷分組，以產生來自所述預定節點的埠不可到達響應。
7.如權利要求
5所述的方法，其特徵在於，所述端對端路徑包括位於所述源主機和所述終點主機之間的一個或更多個目標主機，並且設置所述生存時間值，以使所述一個或更多個載荷在所述一個或更多個目標主機中的一個主機上終止。
8.如權利要求
1所述的方法，其特徵在於，所述生成一個或更多個有序分組組的步驟包括使用選自ICMP、UDP和TCP的協議配置所述一個或更多個載荷分組和所述兩個或更多個標記分組。
9.如權利要求
1所述的方法，其特徵在於，所述生成一個或更多個有序分組組的步驟包括用生存時間值配置所述兩個或更多個標記分組，以使所述兩個或更多個標記分組在到達所述終點主機之前終止，其中所述兩個或更多個標記分組的終止發生在所述標記分組穿過預定節點之後。
10.如權利要求
1所述的方法，其特徵在於，所述收集數據的步驟包括收集與所述一個或更多個有序分組組從所述源主機傳輸有關的時間數據，以及在接收主機處與對所述有序分組組的答覆的接收有關的時間數據。
11.如權利要求
10所述的方法，其特徵在於，在收集了統計顯著性量的時間數據之前一直執行收集數據的步驟。
12.如權利要求
10所述的方法，其特徵在於，所述分析所述數據的步驟包括評估所述兩個或更多個標記分組和所述一個或更多個載荷分組中的一個或更多個分組的行程總時間、最小行程總時間、最大行程總時間、平均行程總時間、行程總時間的標準偏差以及丟失率中的一個或更多個。
13.如權利要求
1所述的方法，其特徵在於，所述一個或更多個有序分組組包括第一個標記分組，隨後是一個或更多個載荷分組，再後是第二個標記分組。
14.如權利要求
13所述的方法，其特徵在於，所述分析所述數據的步驟包括確定單向比特率。
15.如權利要求
13所述的方法，其特徵在於，所述分析所述數據的步驟包括確定單向傳輸延遲。
16.如權利要求
13所述的方法，其特徵在於，所述分析所述數據的步驟包括確定單向延遲變量。
17.如權利要求
13所述的方法，其特徵在於，所述分析所述數據的步驟包括確定單向可用比特率。
18.如權利要求
14所述的方法，其特徵在於，所述單向比特率Bmax基本上被確定如下Bmax＝(n×SL+SM+)/(Λ1-Λ0)其中n是載荷分組的數目，SL是一個載荷分組的大小，SM是一個標記分組的大小，Λ1是所述第二個標記分組的最小行程總時間，以及Λ0是所述第一個標記分組的最小行程總時間。
19.如權利要求
16所述的方法，其特徵在於，所述單向延遲變量基本上通過評估標準偏差的變量係數和第一個載荷分組或最後一個載荷分組的行程總時間的平均值確定。
20.如權利要求
18所述的方法，其特徵在於，所述單向可用比特率Bavail基本上被確定如下Bavail＝Bmax×[(t1-t0)/(t2-t0)]其中(t1-t0)為在最大比特率時所述第一個標記分組的尾沿與最後一個標記分組的尾沿之間的時間，(t2-t0)為在可用比特率時所述第一個標記分組的尾沿與最後一個標記分組的尾沿之間的時間。
21.如權利要求
1所述的方法，其特徵在於，修改步驟包括確定一個或更多個指示器，並且基於所述一個或更多個指示器修改所述一個或更多個有序分組組的一個或更多個參數。
22.如權利要求
21所述的方法，其特徵在於，修改所述參數的步驟是從包括改變載荷分組數目、改變載荷分組大小、改變標記分組大小、逐漸改變標記分組大小、逐漸改變載荷分組大小、改變載荷分組協議、改變標記分組協議以及改變終點主機的組中選擇的。
23.如權利要求
21所述的方法，其特徵在於，修改所述參數的步驟以迭代方式執行，以獲得最佳的採樣過程。
24.如權利要求
1所述的方法，還包括評估所收集的數據的收斂性的步驟。
25.如權利要求
24所述的方法，其特徵在於，評估收斂性的步驟包括如下步驟百分比變化函數評估、二進位串函數評估、熵編碼、熵分析函數評估以及收斂指示器穩定性評估。
26.一種用於表徵基於分組的網絡的端對端路徑的設備，所述設備包括a)用於生成一個或更多個有序分組組的裝置，每一個有序分組組包括兩個或更多個標記分組和一個或更多個載荷分組，所有所述分組都設置成沿由源主機和終點主機限定的共用端對端路徑傳輸，其中所述一個或更多個載荷分組設置成經過端對端路逕到預定節點，所述預定節點為沿端對所述端路徑的任何節點；b)用於從所述源主機沿所述共用端對端路徑傳輸所述一個或更多個有序分組組的裝置；c)用於收集與所述一個或更多個有序分組組的傳輸有關的數據的裝置；以及d)用於分析所述數據從而顯現所述端對端路徑的特性的裝置。
27.如權利要求
26所述的設備，還包括一種用於基於所收集的數據自適應修改所述一個或更多個有序分組組的生成的裝置，所述用於自適應修改的裝置用來優化所述端對端路徑的特性。
28.如權利要求
26所述的設備，還包括一種用於評估所收集的數據的收斂性的裝置。
29.一種電腦程式產品，包括其上記錄有電腦程式的計算機可讀介質，所述電腦程式用來執行一種用於表徵基於分組的網絡的端對端路徑的方法，所述方法包括如下步驟a)生成一個或更多個有序分組組，每一個有序分組組包括兩個或更多個標記分組和一個或更多個載荷分組，所有所述分組都設置成沿由源主機和終點主機限定的共用端對端路徑傳輸，其中所述一個或更多個載荷分組設置成經過所述端對端路逕到預定節點，所述預定節點為沿端對端路徑的任何節點；b)從所述源主機沿所述共用端對端路徑傳輸所述一個或更多個有序分組組；c)收集與所述一個或更多個有序分組組的傳輸有關的數據；以及d)分析所述數據，從而顯現所述端對端路徑的特性。
專利摘要
本發明提供一種表徵源主機與終點主機之間每一段網絡路徑的方法和設備。本發明包括通過發送和接收特定的預定有序分組組來收集數據，該有序分組組是可以改變大小、數量和協議的，該分組從源主機發送並尋址終點節點。這些分組組包括策略排列的標記分組和載荷分組。載荷分組通常在預定節點終止，而標記分組完成到達終點的傳輸。在載荷分組終止後，標記分組提供了一種捕獲能夠對直到這些載荷分組終止的各段進行表徵的信息的手段。此外，分析收集的信息使得能夠調節分組組的特性，從而使網絡路徑的採樣和表徵最優化。
文檔編號H04L12/28GK1998186SQ20058000810
公開日2007年7月11日 申請日期2005年2月4日
發明者洛基·喬根森, 克里斯多福·R·諾裡斯 申請人:阿派倫特網絡股份有限公司導出引文BiBTeX, EndNote, RefMan