Inferring Queue Sizes in Access Networks by Active Measurement

[前言]

        隨著網路的發展,目前核心網路(core network)的頻寬(bandwidth)也越來越大,而這卻使得端點到端點(end-to-end)的瓶頸(bottleneck)會發生在最後(last mile),簡單的說,就是從家(Home)ISP這段路徑,而目前在家中的使用者要跟網際網路(Internet)相連接所採用的方法為DSLCable這兩種方式。在(1)的這篇論文中,作者想要去瞭解目前HomeISP中的那個路由器(Router)是如何設定其佇列大小(queue limit),所以提出了一個非常簡單的方法(Qfind),用來大約估算出佇列大小,作者藉由simulationemulation、和measurement來驗證Qfind。若是有興趣的讀者,可以下載讀看看。而筆者寫這一份報告,最主要的目的就是筆者試著把文章中作者的模擬環境試著做了一下,發現結果非常的類似,因此把結果跟大家分享一下。

 

[Qfind原理]

1.      假設 (Assumption)

a.Each access link has a relatively small queue size. (e.g. 10-100 packets)

b.Maximum queue size is independent of link capacity or other link characteristics.

c.Maximum queue size is constant and independent of incoming traffic load.

d.Last mile router is the bottleneck.

 

2.      方法 (Methodology)

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 


3.     計算queue size

 

Max Queue Size  

 

 

其中,

qp: Queue size in packets                        T: Throughput (Bps)

Dt: Total delay (sec.) (Max ping)             s: packet size (bytes)

Dl:: Latency (sec.) (Min ping)        

 

[Simulation Code]

set ns [new Simulator]

 

#Open a trace file

set nf [open out.nam w]

$ns namtrace-all $nf

 

set nd [open out.tr w]

$ns trace-all $nd

 

# min: Ping所的得最短時間; max: Ping所的得最長時間

set min 1000

set max 0

 

#模擬時間

set end_time 120.0

 

#設定路由器的queue limit

set queue_limit 10

 

#Define a 'finish' procedure

proc finish {} {

        global ns nf nd min max tcp0 end_time

        

        #取出收到的ack

        set ack [$tcp0 set ack_]  

        #取出packet的大小           

        set pktsize [$tcp0 set packetSize_]    

        set thr [expr ($ack * $pktsize)/$end_time]

        #throughput=((ack個數 * packet size) / (起始時間-結束時間)) = Bytes/sec

        set iqs [expr ($max - $min) /1000 * $thr / $pktsize]

        set thr1 [expr ($thr * 8.0)/1000.0]

        #puts "throughput: $thr1 kbps"

        puts "min: $min ms ; max: $max ms ; inferred quese size: $iqs in packets"

        #exec nam out.nam &

        $ns flush-trace

        close $nf

        close $nd

        exit 0

}

 

#Define a 'recv' function for the class 'Agent/Ping'

Agent/Ping instproc recv {from rtt} {

        global min max

        $self instvar node_

        #puts "node [$node_ id] received ping answer from \

        #      $from with round-trip-time $rtt ms."

       

        if { $min > $rtt} {

                set min $rtt

        }

       

        if { $max < $rtt} {

                set max $rtt

        }

}

 

proc send_ping {} {

  global ns p0

  set time 0.2

  set now [$ns now]

  $p0 send

   

  #Re-schedule the procedure

  $ns at [expr $now+$time] "send_ping"

}

 

 

set hn [$ns node]

set r [$ns node]

set ds [$ns node]

set dns [$ns node]

 

$ns simplex-link $hn $r 192kb  5ms DropTail

$ns simplex-link $r $hn 768kb  5ms DropTail

$ns duplex-link  $r $ds  10Mb 20ms DropTail

$ns duplex-link  $r $dns 10Mb  5ms DropTail

 

$ns queue-limit $r $hn $queue_limit

$ns queue-limit $hn $r $queue_limit

 

set p0 [new Agent/Ping]

$ns attach-agent $hn $p0

set p1 [new Agent/Ping]

$ns attach-agent $dns $p1

$ns connect $p0 $p1

 

set tcp0 [new Agent/TCP/Reno]

$ns attach-agent $ds $tcp0

$tcp0 set packetSize_ 1500

$tcp0 set window_ 150

set ftp [new Application/FTP]

$ftp attach-agent $tcp0

set sink0 [new Agent/TCPSink]

$ns attach-agent $hn $sink0

$ns connect $tcp0 $sink0

 

$ns at 0.0 "send_ping"

$ns at 0.0 "$ftp start"

$ns at $end_time "finish"

$ns run

 

測試結果:

a. queue limit10的時候

min: 23.4 ms ; max: 167.8 ms ; inferred quese size: 8.7843333333333327 in packets

 

b. queue limit50的時候

min: 23.4 ms ; max: 777.4 ms ; inferred quese size: 46.012849999999993 in packets

 

c. queue limit100的時候

min: 23.4 ms ; max: 1576.1 ms ; inferred quese size: 93.808958333333308 in packets

 

[參考文件]

1. Mark Claypool, Robert Kinicki, Mingzhe Li, James Nichols, and Huahui Wu, “Inferring Queue Sizes in Access Networks by Active Measurement”, In Proceedings of the 5th Passive and Active Measurement Workshop (PAM), Antibes Juan-les-Pins, France, April 19-20, 2004