ns-route.tcl

跑leach需要的

#
# Copyright (c) 1996 Regents of the University of California.
# All rights reserved.
# 
# Redistribution and use in source and binary forms, with or without
# modification, are permitted provided that the following conditions
# are met:
# 1. Redistributions of source code must retain the above copyright
#    notice, this list of conditions and the following disclaimer.
# 2. Redistributions in binary form must reproduce the above copyright
#    notice, this list of conditions and the following disclaimer in the
#    documentation and/or other materials provided with the distribution.
# 3. All advertising materials mentioning features or use of this software
#    must display the following acknowledgement:
# 	This product includes software developed by the MASH Research
# 	Group at the University of California Berkeley.
# 4. Neither the name of the University nor of the Research Group may be
#    used to endorse or promote products derived from this software without
#    specific prior written permission.
# 
# THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
# ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
# IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
# ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
# FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
# DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
# OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
# HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
# LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
# OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
# SUCH DAMAGE.
#
# @(#) $Header: /nfs/jade/vint/CVSROOT/ns-2/tcl/lib/ns-route.tcl,v 1.37 2002/04/05 05:43:40 ddutta Exp $
#

RouteLogic instproc register {proto args} {
	$self instvar rtprotos_ node_rtprotos_ default_node_rtprotos_
	if [info exists rtprotos_($proto)] {
		eval lappend rtprotos_($proto) $args
	} else {
		set rtprotos_($proto) $args
	}
	if { [Agent/rtProto/$proto info procs pre-init-all] != "" } {
		Agent/rtProto/$proto pre-init-all $args
	}
}

RouteLogic instproc configure {} {
	$self instvar rtprotos_
	if [info exists rtprotos_] {
		foreach proto [array names rtprotos_] {
			eval Agent/rtProto/$proto init-all $rtprotos_($proto)
		}
	} else {
		Agent/rtProto/Static init-all
	}
}

RouteLogic instproc lookup { nodeid destid } {
	if { $nodeid == $destid } {
		return $nodeid
	}

	set ns [Simulator instance]
	set node [$ns get-node-by-id $nodeid]

	if [Simulator hier-addr?] {
		set dest [$ns get-node-by-id $destid]
		set nh [$self hier-lookup [$node node-addr] [$dest node-addr]]
		return [$ns get-node-id-by-addr $nh]
	}
	set rtobj [$node rtObject?]
	if { $rtobj != "" } {
		$rtobj lookup [$ns get-node-by-id $destid]
	} else {
		$self cmd lookup $nodeid $destid
	} 
}

RouteLogic instproc notify {} {
	$self instvar rtprotos_
	foreach i [array names rtprotos_] {
		Agent/rtProto/$i compute-all
	}

	foreach i [CtrMcastComp info instances] {
		$i notify
	}
	if { [rtObject info instances] == ""} {
		foreach node [[Simulator instance] all-nodes-list] {
			# XXX using dummy 0 for 'changes'
			$node notify-mcast 0
		}
	}
}

#
# routine to create address for hier-route-lookup at each level
# i.e at level 2, address to lookup should be 0.1 and not just 1
#
RouteLogic instproc append-addr {level addrstr} {
	if {$level != 0} {
		set str [lindex $addrstr 0]
		for {set i 1} {$i < $level} {incr i} {
			append str . [lindex $addrstr [expr $i]]
		}
		return $str
	}
}

#
# debugging method to dump table (see route.cc for C++ methods)
#
RouteLogic instproc dump nn {
	set i 0
	while { $i < $nn } {
		set j 0
		while { $j < $nn } {
			puts "$i -> $j via [$self lookup $i $j]"
			incr j
		}
		incr i
	}
}

Simulator instproc rtproto {proto args} {
    $self instvar routingTable_
    if {$proto == "Algorithmic"} {
	set routingTable_ [new RouteLogic/Algorithmic]
    }
    eval [$self get-routelogic] register $proto $args
}

Simulator instproc get-routelogic {} {
	$self instvar routingTable_
	if ![info exists routingTable_] {
		set routingTable_ [new RouteLogic]
	}
	return $routingTable_
}

# Debo
Simulator instproc dump-approx-sim-data {} {

	$self instvar routingTable_ Node_ link_
    
#        if ![info exists routingTable_] {
#	    puts "error: routing table is not computed yet!"
#	    return 0
#	}

	set r [$self get-routelogic]	
	$self cmd get-routelogic $r  ;# propagate rl in C++
	# populate the route logic 
	foreach ln [array names link_] {
		set L [split $ln :]
		set srcID [lindex $L 0]
		set dstID [lindex $L 1]
		if { [$link_($ln) up?] == "up" } {
			$r insert $srcID $dstID [$link_($ln) cost?]
		} else {
			$r reset $srcID $dstID
		}
	}
	# now compute routes
	$r compute

	puts "# Dumping Approx-Sim Data"  

	set n [Node set nn_]
	puts "m [Link set nl_] "
        foreach qn [array names link_] {
                set l $link_($qn)
	        set q [$l queue]
	        set t [$q info class]
	    if {[lindex [split $t "/"] 1] == "DropTail"} {
                puts "link [expr [$l set id_] + 1] [expr [$l bw] / 8000] [expr [$l bw] / 8000] [$l delay] [$l qsize] $t"
	    }
	    if {[lindex [split $t "/"] 1] == "RED"} {
                puts "link [expr [$l set id_] + 1] [expr [$l bw] / 8000] [expr [$l bw] / 8000] [$l delay] [$l qsize] RED [$q set thresh_] 0 [$q set maxthresh_] [expr 1.0 / [$q set linterm_] ]"
	    }
        }

	puts ""
	puts "n $nconn_"
	
	for { set i 0 } { $i < $nconn_ } { incr i } {

		set len 0
		set str ""

		set list [split $conn_($i) ":"] 
		set srcid [lindex $list 0]
		set dstid [lindex $list 1]

		while { $srcid != $dstid } {
			incr len
			# shortened nexthop to nh, to fit add-route in
			# a single line
			set nh [$r lookup $srcid $dstid]
			# print the route 
			append str " " [expr [$link_($srcid:$nh) id] + 1] 
			set srcid  $nh
		}
		
		puts "route [expr $i + 1] $len $str"
		
	}
}

Simulator instproc dump-routelogic-nh {} {
	$self instvar routingTable_ Node_ link_
	if ![info exists routingTable_] {
	    puts "error: routing table is not computed yet!"
	    return 0
	}

	puts "Dumping Routing Table: Next Hop Information"
	set n [Node set nn_]
	set i 0
	puts -nonewline "\t"
	while { $i < $n } {
	    if ![info exists Node_($i)] {
		incr i
		continue
	    }
	    puts -nonewline "$i\t"
	    incr i
	}
	set i 0
	while { $i < $n } {
		if ![info exists Node_($i)] {
		    incr i
		    continue
		}
		puts -nonewline "\n$i\t"
		set n1 $Node_($i)
		set j 0
		while { $j < $n } {
			if { $i != $j } {
				# shortened nexthop to nh, to fit add-route in
				# a single line
				set nh [$routingTable_ lookup $i $j]
				if { $nh >= 0 } {
				    puts -nonewline "$nh\t"
				}
			} else {
				puts -nonewline "--\t"
			}
			incr j
		}
		incr i
	}
	puts ""
}

Simulator instproc dump-routelogic-distance {} {
	$self instvar routingTable_ Node_ link_
	if ![info exists routingTable_] {
	    puts "error: routing table is not computed yet!"
	    return 0
	}

	# puts "Dumping Routing Table: Distance Information"
	set n [Node set nn_]
	set i 0
	puts -nonewline "\t"
	while { $i < $n } {
	    if ![info exists Node_($i)] {
		incr i
		continue
	    }
	    puts -nonewline "$i\t"
	    incr i
	}

	for {set i 0} {$i < $n} {incr i} {
		if ![info exists Node_($i)] {
		    continue
		}
		puts -nonewline "\n$i\t"
		set n1 $Node_($i)
		for {set j 0} {$j < $n} {incr j} {
			if { $i == $j } {
				puts -nonewline "0\t"
				continue
			}
			set nh [$routingTable_ lookup $i $j]
			if { $nh < 0 } {
				puts -nonewline "0\t"
				continue
			}
			set distance 0
			set tmpfrom $i
			set tmpto $j
			while {$tmpfrom != $tmpto} {
				set tmpnext [$routingTable_ lookup \
					$tmpfrom $tmpto]
				set distance [expr $distance + \
					[$link_($tmpfrom:$tmpnext) cost?]]
				set tmpfrom $tmpnext
			}
			puts -nonewline "$distance\t"
		}
	}
	puts ""
}

# Only used by static routing protocols, namely: static and session.
Simulator instproc compute-routes {} {
	#
	# call hierarchical routing, if applicable
	#
	if [Simulator hier-addr?] {
		$self compute-hier-routes 
	} else {
		$self compute-flat-routes
	}
}

Simulator instproc compute-flat-routes {} {
	$self instvar Node_ link_
	#
	# Compute all the routes using the route-logic helper object.
	#
        if { [ Simulator set nix-routing] } {
            puts "Using NixVector routing, skipping route computations"
            return
        }
	#puts "Starting to read link_ array..\
		time: [clock format [clock seconds] -format %X]"
	
	set r [$self get-routelogic]
	$self cmd get-routelogic $r  ;# propagate rl in C++
	
	foreach ln [array names link_] {
		set L [split $ln :]
		set srcID [lindex $L 0]
		set dstID [lindex $L 1]
		if { [$link_($ln) up?] == "up" } {
			$r insert $srcID $dstID [$link_($ln) cost?]
		} else {
			$r reset $srcID $dstID
		}
	}
	#puts "Completed reading link_ array.."
	#puts " and starting route-compute at \
		time: [clock format [clock seconds] -format %X]"

	$r compute

	#puts "completed route-compute"
	#puts "and starting to populate classifiers at \
		time: [clock format [clock seconds] -format %X]"
	set n [Node set nn_]
	
	# classifier-population part moved to C++: this results in > 50% 
        # improvement of simulation run time.
	
	$self populate-flat-classifiers $n
	

	# Set up each classifer (aka node) to act as a router.
	# Point each classifer table to the link object that
	# in turns points to the right node.
	#
	#set i 0
	#set n [Node set nn_]
	#while { $i < $n } {
	#	if ![info exists Node_($i)] {
	#	    incr i
	#	    continue
	#	}
	#	set n1 $Node_($i)
	#	set j 0
	#	while { $j < $n } {
	#	    if { $i != $j } {
			# shortened nexthop to nh, to fit add-route in
			# a single line
	#		set nh [$r lookup $i $j]
	#		if { $nh >= 0 } {
	#		    $n1 sp-add-route $j [$link_($i:$nh) head]
	#		}
	#	    } 
	#	    incr j
	#	}
	#	incr i