This work was supported by the National Science Foundation
under grant number ANI-99-77544
A NixVector (Neighbor-Index Vector) is a form of source
routing that can retain and use a complete routing path from a source to a
destination is a very compact form. The
inclusion of NixVector routing in ns allows for the bypassing of the route
computations step of the ns setup, with the resulting memory and execution
savings.
Instead of computing all-pairs routes, a NixVector is
computed from a source to a destination on demand, when a packet is generated
at the source. The NixVector is
included in the packet as it traverses through the network, and contains enough
information for routers to make routing decisions without using routing
tables. The NixVectors are cached at
each source for later re-use as more packets are generated between the same
source and destination pair.
The NixVector routing method has the advantages of the ns hierarchical
routing, without the necessity of a structured topology, and with no additional
effort on the part of the ns user.
NixVector routing is enabled by a single line of code, which
must be executed BEFORE any nodes or links are created:
$ns
set-nix-routing
Is
NixVector routing appropriate for all existing NS scripts?
No. Since NSNV does not
compute routing tables, any simulation which
uses the routing tables for anything other than unicast packet
forwarding
will likely not work. In
particular, multicast flows cannot use NixVector routing.
How do I
know if NixVector routing is appropriate for my simulation?
The short answer is if you don't know what a "slot" is in
NS terminology,
and you don’t use multicast, your simulation will probably work.
Since
NixVector routing is not appropriate for all simulation scenarios, what is it
good for?
Any simulation that is concerned with end-to-end unicast flows
under a fairly large
topology can benefit from NixVector routing.
What
changes do I need to my ns script to use NVNS?
To enable NixVector routing in NVNS, just include a single ns
command:
(this command must be executed PRIOR TO creating any nodes)
$ns set-nix-routing
Does the
inclusion of the NixVector modifications to ns break anything?
No, with the NixVector modification included, all ns validation
tests produce
the same results as the original ns.
What is a
NixVector anyway?
NixVector routing is described in detail in two research papers:
http://www.cc.gatech.edu/~riley/papers/nsnv.ps.gz
http://www.cc.gatech.edu/~riley/papers/nixvec.ps.gz
How much
memory reduction will I see using NVNS?
It depends. If your
simulation has a large number of nodes (1000 or more)
and a smaller number of connections (100 or so), your savings will
be
substantial. If you only
have a small number of nodes, your savings will be
negligible or negative.
Where can
I get the code for NVNS?
http://www.cc.gatech.edu/computing/compass/nvns/index.html
We have a working version of ns with NixVector routing which
you can download below. It has been
tested on Sparc Solaris 5.7, Intel Solaris 5.7, and RedHat Linux 6.2 on
Intel. We have run simulations as large
as 16,000 nodes on a single Linux box using NixVector routing.
All of the modifications to existing ns code and newly added ns code are in nvns-added-2.1b7.tar.gz. The modifications apply to release 2.1b7 ONLY! (released 18 October 2000). Be sure you are starting with this release. The nvns-added tar file contains replacements for the following ns modules:
ns-2.1b7/Makefile.in
ns-2.1b7/node.cc
ns-2.1b7/node.h
ns-2.1b7/agent.cc
ns-2.1b7/tcl/lib/ns-lib.tcl
ns-2.1b7/tcl/lib/ns-route.tcl
ns-2.1b7/tcl/lib/ns-rtmodule.tcl
diff files are provided for each of the above if you prefer to patch in the changes.
First, un-zip and un-tar the baseline ns software:
gunzip -c ns-allinone-2.1b7.tar.gz | tar -xvf –
Then, un-zip and un-tar the nsnv-added-2.1b7.tar.gz file.
gunzip -c nvns-added-2.1b7.tar.gz | tar -xvf -
Then configure and build the ns release normally. Note that the ns-added tar contains a revised Makefile.in, so the configure script MUST be run to build a correctly modified Makefile.
A sample ns script is included on the ns-added tar as testnvns/testnvns.tcl. This makes a two dimensional planar topology (the size in the x and y planes are specified as command line parameters), and specifies NixVector routing. To run this script, use:
cd ns-allinone-2.1b7/testnvns
../ns-2.1b7/ns testnvns.tcl 5 5
This script creates a 5 by 5 square of nodes, and flows from one corner node to all other edge nodes. A nam file is created that you can use to visually observe the proper flow of packets.
Please email George Riley with any questions or comments.