Creating random wired topology for given arbitrary

问题:

I want to create and simulate a wired topology using NS2. Trying to write a tcl and positioning the nodes and links using rand() . My solution was:

### Create a simulator object
set ns [new Simulator]
set num_node 10
set num_flow 5
set x_dim 150
set y_dim 150

### Define different colors for data flows (for NAM)
$ns color 1 Blue
$ns color 2 Red

### Open the NAM trace file
set nf [open out.nam w]
$ns namtrace-all $nf
set tracefd [open out.tr w]
$ns trace-all $tracefd

### set up topography object
set topo [new Topography];            # This is needed for wireless
$topo load_flatgrid $x_dim $y_dim;    # Setting a 2D space for the nodes

### Define a 'finish' procedure
proc finish {} {
    global ns nf tracefd
    $ns flush-trace
    ### Close the NAM trace file
    close $nf
    close $tracefd
    ### Execute NAM on the trace file
    exec nam out.nam &
    exit 0
}

#Create four nodes
for {set i 0} {$i < [expr $num_node]} {incr i} {
    set n($i) [$ns node]
    puts "Created node $i"
}

### Create links between the nodes
for {set i 0} {$i < [expr $num_node + 1]} {incr i} {
    set s_node [expr int($num_node*rand())];     # src node
    set d_node $s_node
    while {$d_node==$s_node} { ;                 # while the random pair are same node
        set d_node [expr int($num_node*rand())]; # dest node
    }
    $ns duplex-link $n($s_node) $n($d_node) 2Mb 10ms DropTail
    $ns queue-limit $n($s_node) $n($d_node) 50
    puts "Linking $s_node and $d_node"
}

### Give node position (for NAM)
set i 0
while {$i < $num_node } {
    ### Set random position for nodes
    set x_pos [expr int($x_dim*rand())];   # random settings
    set y_pos [expr int($y_dim*rand())];   # random settings

    $n($i) set X_ $x_pos
    $n($i) set Y_ $y_pos
    $n($i) set Z_ 0.0
    puts "Put $i to ($x_pos , $y_pos)"

    #puts -nonewline $topofile "$i x: [$node_($i) set X_] y: [$node_($i) set Y_] \n"
    incr i;
}; 

### Setup UDP connections
for {set i 0} {$i < [expr $num_flow]} {incr i} {
    set s_node [expr int($num_node*rand())];     # src node
    set d_node $s_node
    while {$d_node==$s_node} {;                  # while the random pair are same node
        set d_node [expr int($num_node*rand())]; # dest node
    }
    set udp($i) [new Agent/UDP]
    $udp($i) set class_ $i
    $ns attach-agent $n($s_node) $udp($i)
    set null($i) [new Agent/Null]
    $ns attach-agent $n($d_node) $null($i)
    $ns connect $udp($i) $null($i)
    $udp($i) set fid_ $i
    puts "Flow $s_node - $d_node"
}

### Setup a CBR over UDP connections
for {set i 0} {$i < [expr $num_flow]} {incr i} {
    set cbr($i) [new Application/Traffic/CBR]
    $cbr($i) attach-agent $udp($i)
    $cbr($i) set type_ CBR
    $cbr($i) set packet_size_ 1000
    $cbr($i) set rate_ 1mb
    $cbr($i) set random_ false
    puts "setting cbr for $i"
}

### Schedule events for the CBR and FTP agents
for {set i 0} {$i < [expr $num_flow]} {incr i} {
    $ns at 0.1 "$cbr($i) start"
}

for {set i 0} {$i < [expr $num_flow]} {incr i} {
    $ns at 4.5 "$cbr($i) stop"
}

for {set i 0} {$i < [expr $num_node]  } { incr i} {
    $ns initial_node_pos $n($i) 4
}

### Run the simulation
$ns run

But the randomization is often creating erroneous links and thus problem in simulation and getting this error :

--- Classfier::no-slot{} default handler (tcl/lib/ns-lib.tcl) ---
    _o28: no target for slot 4294967295
    _o28 type: Classifier/Hash/Dest
content dump:
classifier _o28
    0 offset
    0 shift
    1073741823 mask
    1 slots
        slot 5: _o268 (Classifier/Port)
    -1 default
---------- Finished standard no-slot{} default handler ----------

But this is also random and does not occur always. When it does not occur , the nam file shows that there have been duplicate definition of nodes. Can someone please just give me some guidance about how to create a random wired topology with random valid links?

回答1:

Your file "random-wired.tcl" is working OK here ... PCLinuxOS 2017.04 - x86_64.

$ ns235-64-orig random-wired.tcl
Created node 0
Created node 1
Created node 2
Created node 3
Created node 4
Created node 5
Created node 6
Created node 7
Created node 8
Created node 9
Linking 9 and 0
Linking 9 and 8
Linking 5 and 8
Linking 1 and 6
Linking 9 and 6
Linking 8 and 0
Linking 1 and 4
Linking 3 and 7
Linking 8 and 7
Linking 1 and 2
Linking 9 and 0
Put 0 to (139 , 71)
Put 1 to (107 , 146)
Put 2 to (14 , 9)
Put 3 to (16 , 23)
Put 4 to (89 , 30)
Put 5 to (26 , 65)
Put 6 to (46 , 76)
Put 7 to (87 , 31)
Put 8 to (12 , 105)
Put 9 to (89 , 56)
Flow 6 - 4
Flow 0 - 1
Flow 2 - 8
Flow 5 - 2
Flow 2 - 3
setting cbr for 0
setting cbr for 1
setting cbr for 2
setting cbr for 3
setting cbr for 4

The files out.nam 3.3MB, out.tr 1.4MB are created. And nam : Some nodes show activity.

--- Classfier::no-slot{} default handler (tcl/lib/ns-lib.tcl) ---

... is an known error with some simulations / some Linux OS´s. Another ns2 friendly OS is CentOS 7 - 64bit : Your file runs OK. The not so good news : Fails with Ubuntu 16.04 - 64 and Ubuntu 17.04 - 64. Actually Ubuntu isn't the first choice for ns2. Not very ns2 friendly with it's "different" patching of e.g. libc6.

Examples, rand() : aodv18.tcl, aodv_802_15_4.tcl, AODV-Jenova.tcl, aodv-Soumia.tcl, AODV-testcode-rand.tcl → https://drive.google.com/file/d/0B7S255p3kFXNMXRfTTlEcm5KUW8/view?usp=sharing

---

EDIT, May26 2017:

--- Classfier::no-slot{} default handler

I think a solution was found http://www.linuxquestions.org/questions/linux-software-2/ns2-2-35-antnet-4175532576/#14 (post #14 @newthink) → Add $ns multicast :

set ns [ new Simulator ]
$ns multicast

Works perfect with the problematic Antnet simulations.

回答2:

$ns multicast didn't work me at times. I found this post which says that this error occurs when there the generated graph is disconnected.

So i kept a check that the graph never turns out to be disconnected and every node has at least one link.

#nodeFlag_ keeps of which nodes has at least one link
for {set i 0} {$i < $num_node} {incr i} {
        set nodeFlag_($i) 0
    }
    ### Create links between the nodes
    for {set i 0} {$i < [expr $num_node + 1]} {incr i} {
        set s_node [expr int($num_node*rand())];     # src node
        set d_node $s_node
        while {$d_node==$s_node} { ;                 # while the random pair are same node
            set d_node [expr int($num_node*rand())]; # dest node
        }
        $ns duplex-link $node_($s_node) $node_($d_node) 2Mb 10ms DropTail
        set nodeFlag_($s_node) 1
        set nodeFlag_($d_node) 1
        $ns queue-limit $node_($s_node) $node_($d_node) 50
        puts "Linking $s_node and $d_node"
    }
    for {set i 0} {$i < $num_node} {incr i} {
            #see here
            if {$nodeFlag_($i) == 0} {
            set random [expr int($num_node*rand())]
            $ns duplex-link $node_($i) $node_($random) 2Mb 10ms DropTail
            puts "left link $i and $random"
        }
        puts "$nodeFlag_($i)"
    }

Hope this helps.

EDIT : I was wrong. The error still shows up in some simulations.

回答3:

Although your last edit makes sure that every node has at least one link, it does not assure to have a fully connected graph among all the nodes. In other words, you might still end up having multiple isolated groups of nodes that can not be reached from other nodes.