Implementing Link State Routing in NS

[Mingzhou Sun <sunmin@networks.ecse.rpi.edu>]

gxu@eng.ua.edu said:
>  I am a new user to ns. I try to understand how ns implement the 
> routing so that I can write my own protocol. I finished the ns 
> Documentation about routing. However, I am still lost. Can anyone 
> give me some advises on where and how to begin? Your help will be 
> highly appreciated! 

I've got some link state routing working for ns. Not surprisingly, I name it 
rtProto/LS, as I started out mimicking rtProto/DV. Kannan is obviously the 
authority on this subject, so I would just share with you what I did as it 
happened. I am sure there are better ways of doing it. 

Step 1. Read the relavent program files till I was sure what they did and how. 
	rtProtoDV.cc rtProtoDV.h packet.cc packet.h
   under tcl/lib: ns-lib.tcl ns-packet.tcl ns-route.tcl
   under tcl/rtglib: route-proto.tcl dynamics.tcl

Step 2. Put in a new routing proto agent rtProto/LS that was the same as 
rtProto/DV except the name. This involved
	2.a. Duplicating whatever was related to rtProto/DV and change DV to LS . :) 
Specifically, 
		creating rtProtoLS.cc and rtProtoLS.h after DV
		extending route-proto.tcl for Agent/rtProto/LS
	2.b. Incorporating rtProtoLS header in NS, Specially, added in packet.h

$ diff packet.h packet.h.old

61,62d60
< #ifdef NSLS
< #define PT_RTPROTO_LS  18
65,72d62
<       "rtProtoDV", "CtrMcast_Encap", "CtrMcast_Decap", "SRM" \
<       , "ntype" , "rtProtoLS"
< 
< #endif /* ifdef NSLS */
< 
< #ifndef NSLS
< #define PT_NAMES "tcp", "telnet", "cbr", "audio", "video", "ack", \
<       "start", "stop", "prune", "graft", "message", "rtcp", "rtp", \
74d63
< #endif /* ifndef NSLS */
77a67
> 
 	and in ns-packet.tcl 

%diff ns-packet.tcl ns-packet.tcl.old 
57d56
<               { rtProtoLS off_LS_ }

	2.c. Put the following in ns-default.tcl
	# as in lib/ns-default.tcl
Agent/rtProto/LS set preference_        120
Agent/rtProto/LS set INFINITY            [Agent set ttl_]
Agent/rtProto/LS set advertInterval       2

	2.d Recompiled ns.
        Step 2 above gave me a new routing protocol called rtProto/LS that did 
the very same thing as rtProto/DV.

Step 3. Changed the implementation to do link state routing
	3.a I chose to implement the algorithm in C++. So I tested the link state 
routing stuff in C++ and made sure they were working.
	3.b I then modified the rtProtoLS.{h,cc} to incorporate the link state 
routing, and consult the tcl part for node, link and peer information. Also 
use rtProtoLS to send protocol messages.
 	3.c Modified tcl codes to supply initialization information, intfChange 
notification to the C++ part, and consult the C++ codes when looking up routes

As of now, rtProtoLS works well for small topologies, but occationally crashes 
on larger ones. I am still working on it. 

Mingzhou Sun
RPI