What Is This? ------------- This is a detailed Ethernet simulator written by Wayne Hayes and Mart Molle with the aid of the network simulation program _The Smurph Protocol Modelling Environment_. Smurph is available for free from Pawel Gburzynski , while the protocols included in this package include a standard Ethernet node, and the BLAM protocol by Mart Molle (mart@csri.utoronto.ca). As an added bonus ("don't touch that dial! If you act RIGHT NOW...") it also includes a yet-to-be published two-node Ethernet protocol by one of Mart's students (wayne@csri.utoronto.ca, the guy who's writing this document). You will not be able to run any of this without Smurph version 1.12 (an out-of-date version of Smurph that is included in this directory). File Manifest: -------------- README - "anybody not here, put up your hand" smurph.112b.Z - a copy of version 1.12 of the Smurph package. It is included as a Unix "tar" archive that has been run through the Unix "compress" utility. smurph.112b.tgz - same as above, but the more-efficient "gzip" utility has been used to compress it. boggs_dist.c - a C program to generate a topology as input to SMURPH in accordance with a paper by Boggs et al (see below) main.cc - the main SMURPH program, which #includes... bimodal.cc - file to generate bimodal packet distribution for SMURPH iTraffic.cc - input (TRACE) driven traffic generator for SMURPH gizmo-buckets.c - a file for taking LRU statistics. protocols: ether.cc - the standard ethernet protocol include file for SMURPH blam.cc - the BLAM protocol include file for SMURPH magic.cc - a skeleton file for a stepping-stone to BLAM, no longer supported. wayne.cc - a prototype of a two-node ethernet protocol, as a free bonus. Getting Started --------------- First you need Smurph v1.12. It is a large C++ program designed to make the design and testing of communications network protocols easy. It handles such things as the time, propagation delay (topology), clock inaccuracies, BIG integer types, and allows for easy topology definition, and the simple building, storage, and transport of packets. Further, your simulator is compiled to C++ which then runs very quickly (well, more quickly than if it was interpreted). Smurph is highly recommended as a network simulator. The documentation is also tops; we have not found any inaccuracies or omissions. We have no affiliation to Smurph other than being satisfied users. If you're lucky and you got Smurph v1.12 from us, just gunzip and untar the SMURPH112.tar.gz file. Take a look at MANUAL/REPORT/report.dvi for a short introduction to Smurph. MANUAL/manual.dvi contains a longer reference manual. The next thing to note is that if you have multiple people using Smurph, you do NOT need to untar the entire copy for each project. Use scopy to make symbolic links to the required files, to save disk space. The LIB directory will contain runtime libraries specific to each project (kinda; read manual for details). You should really read the docs to get started, but it amounts to compiling "maker" in the SOURCES directory, which is a bootstrap program to build "mks" in the SOURCES directory. Ideally you need only run "maker" once. It builds "mks", which is an executable which you run whenever you want to build a simulator. There is no Makefile for your simulator; "mks" does the thinking about what needs to be recompiled. Once you have "mks" built, run it with the "-h" option to see the options. Then try to build one of Smurph's example simulators (it includes a simplified Ethernet simulator), or if you're brave try and build the BLAM simulator right off. The options this author swears by (once the simulator is *debugged*) are mks -a -f -v -m -n -i -t -q -o ether along with the default -b 2. Note that -a turns off "assert" but not "Assert". If you're paranoid you do asserts with a capital 'A'. Using the Ethernet and BLAM simulators -------------------------------------- The main program, main.cc ------------------------- The top file of the Ethernet simulator is called main.cc. Don't look at it yet, it might scare you away. Its main purpose is to initialize the protocols, initialize the zillions of statistics variables we use to measure performance, and finally output these zillions of statistics using hordes of ugly normalizations. Most input times are in bit-times, most output times are in milliseconds (assuming a bitrate of 10Mb/s). The "experimenter's time unit", or ETU, is set to 1 bit-time (== TTime). OK, you can look at main.cc now. It's probably not the first place you want to start changing things. But just in case you do, here's a brief overview of its internals. You should probably pop up the source in another window and follow along as you read, because there are comments in the code that I'm not going to repeat here. This simulator has tons of compile-time options (ie #defines), and even more runtime options. We designed it to be able to easily use arbitrary traffic patterns. Our first "pattern" is the artificial pattern used by the paper "Ethernet: Myths and Reality" by Boggs, Mogul, and Kent, in which every node has an infinite supply of packets, simulating a vastly overloaded network. Define "BOGGS 1" to have this pattern, else 0. (Incidentally, we have reproduced the experiments in that paper and got results almost exactly the same, which is one of the first pieces of evidence we had to bolster confidence in this simulator.) If 0, the traffic pattern is decided at run time to be either a single global Poisson process with traffic distributed equally across hosts, or traffic generated on stdin (so you can generate your own favourite pattern of inter-arrival times, size, source, and destination). This option was programmed because we have hundreds of megabytes of packet traces from a local undergrad computing facility which we use to imitate "real" network traffic. More details below. There is also a BIMODAL traffic pattern, but it is set up to only work with 2 nodes. It does, however, provide a simple example of how to generate your own traffic pattern without resorting to input driven traffic. ITRAFFIC is just a macro that let's us know if you're using input-driven traffic at all (the input-driven traffic code for Smurph is in iTraffic.cc). You can independently choose (at run time) to use any, all, or none of the input (but the input always needs all 4 columns). TraceArrivals is a boolean meaning we should use the input traffic for interarrival times; TraceSizes is a similar boolean (input sizes should be in bytes); and TraceWho a boolean saying you want the source/dest pair to be from the input traffic. If none are true, then no input traffic is needed. All input is done using C routines and all output using C++ routines, because we needed to use fread() in C (and I didn't know enough C++ to know the equivalent in C++), and C's fread() messed up the C++ input routines. Thus CReadInt() and CReadFloat() are similar to Smurph's overloaded readIn(). PROFILE is a cheap kluge for profiling states in the state machine. Ignore it until you need it, then figure it out yourself (it's not hard, see the comments). TOO_LONG_NETWORK: apparently some people want to know how BLAM works if some bonehead improperly wires his Ethernet to be too long. See other places in the protocols files this appears to see how it works. Leave it off (0) if you don't care. ASCII: is the input driven traffic 4-column ASCII, or our own binary encoding? (binary makes the input come in MUCH faster, since translating from ASCII input to binary took almost half of our CPU, much to our surprise -- ie using atoi() or scanf() to generate each packet takes too much CPU time.) DELAY_HISTOGRAM: another rarely used feature. Ignore unless interested. MaxMessageQ: by default, Smurph dynamically grows packet queues at each node. This is fine until you add a bug/feature to your protocol that grows the simulator until it eats up all the memory on your workstation, simulating millions of waiting packets in simulated queues. When your simulator is compiled with '-q', Smurph allows you to limit the number of packets queued at each host. 1000 should be big enough that a network well below overload never discards packets due to overflow, and small enough that simulating a drastically overloaded network won't beat your swap partition to a pulp. runLenCount: a ``run'' of is a sequence of successfully transmitted packets from the same host, even if there were some collisions in between. runLenCount keeps track of who is currently transmitting and how long they've been hogging the medium. (This is a simulation variable, not an input parameter.) That's pretty much the end of the compile-time parameters. The next significant milestone in the code is the PacketStat() function. This function is called by the transmitting node at the end of every successful packet transmission. Most of it is (hopefully) self-explanatory, if a bit messy. The most important things to note are that the qDelay includes the time from when the packet was generated until the time it gets to the front of the queue (ie, starts to contend for the medium), and servTime includes the time from getting to the front of the queue until the end of successful transmission. The total time in system is the sum of these two. Note also the difference between CCounter and RealCollisions: with the BLAM protocol, CCounter may not actually be the number of collisions, so we also record the actual number. The next big slop of code is the "Root" process. Every Smurph simulator needs a Root process; it's analagous to the main() program in C, and it should have 2 states, Start (in which the world is initialized and the simulation starts), and Stop (that gets executed when the world ends, presumably to output interesting statistics). Most of the code in there is best understood by reading the Smurph manual. I'll just explain the input parameters expected (you can find the input commands by searching for the string "CRead"), that are all read at run-time on stdin. Here's the input that's expected on stdin, in order: maxPackets: the maximum # of packets to simulate; 0 of no limit. maxTime: maximum number of simulated seconds to simulate. 0 for no limit. maxCPU: maximum number of CPU seconds to take. 0 for no limit. [note: of course, at least one of these should be non-zero] otherMaxCCounter: only used for the two-node protocol. Enter your favourite number, it won't make a whit of difference unless you try the two-node protocol. ThinkTime: used to simulate slow workstations, this is the number of bit-times to wait after successfully transmitting a packet, before going to get a new one. For example, the Boggs paper needs a 1000 bit ThinkTime because their workstations needed 100us for interrupt delays. mle: mean message length, in bits (yes, bits). Only used for the Poisson traffic pattern, but it's a good idea to also input an estimated mle for input-driven traffic. offered_load: again only for Poisson, but it's good to estimate it... TraceArrival, TraceSize, TraceWho: booleans, as described above. NNodes: an integer, the number of nodes in your network. They will be numbered from 0 to NNodes-1 inclusive. Let's call this N for brevity in this document. Then you need to input N integers representing the type of (ie, protocol to run at) each node. 0=std_ether, 1=two-node "smart" guy (ignore unless you try the two-node protocol), 2="magic", also ignore, 3=BLAM node. You're probably only interested in nodes of type 0 and 3. Finally, you need to input the N(N-1)/2 half-array of "distances" (actually propagation delays), in bit-times. For example, the C program "boggs_dist.c" will generate a Boggs, Mogul, and Kent topology for you, in which N hosts are distributed evenly among 4 single-point connections called DELNIs. CReadInt() and CReadFloat() echo all their input to stdout. The rest of the Start state in the Root process is copious initialization of statistics and simulation variables. You should probably at least glance over these. The Stop state is where all the output happens. Now would be a good time to look up RVariables in the Smurph manual. Most of the remaining code in main.cc is straightforward, just a bit messy with details. Note that the output delay column labelled "Real Q Size" (just before "and via Little") is only non-zero when Input driven traffic is used, because that's the only time the user (ie, you and me) have access to code that can keep track of queue sizes. Smurph does not provide this statistic for its builtin traffic patterns. The Protocols ------------- Finally, look in the "protocols" directory. The ones you're probably interested in are std_ether.cc and blam.cc. I won't try to explain BLAM; you should have a copy of Mart Molle's paper for that. I'll go through a quick tutorial on the standard ethernet protocol. Fire up your editor on std_ether.cc. This'll be much easier going than main.cc, I promise (assuming you already understand the standard Ethernet protocol). Every protocol must define a "station" data type (it's a C++ class, but this isn't a C++ tutorial). This one is called Ether_node. At a node, we have a "connection" to the Ethernet which is a Port called "Bus", and a Packet Buffer which holds the packet we're trying to transmit right now. The setup() function is called once for each station that is created. Our stations have two processes, called Ether_Xmitter and Ether_Receiver. Look at the Receiver process (at the bottom of the file) first, it's much simpler. It has it's own pointer to the "Bus" connection, which is just a copy of the pointer owned by the station this process belongs to (S is a short form that Smurph allows you to use, meaning "my station"). The Receiver has two states, Wait, and Recieved. In Wait, we ask the Bus to inform us when we receive a packet (EMP == "end of my packet"), in which case we go to the state "Rcvd". It's just a simple finite state machine. Rcvd just tells the Client (you can think of it as the OS on the machine that has the Ethernet card installed) to take the packet, and then it goes back to the Wait state. Now back up to the transmit process. It has alot more variables and states. The setup() function's purpose is almost solely to translate all the global bit-time input parameters into internal "time" format, plus zeroing some variables. The backoff function should look familiar. Note that when the backoff counter wraps around, we delay a "ThinkTime". This is to simulate the transmitter telling the OS, "hey, the transmission failed", and the OS responding, "OK, just keep trying". The transmitter process starts in the state NPacket, in which it is waiting for a packet to transmit. If we're running a BOGGS experiment, then there is no queue, and I have to fill the packet Buffer manually. [NOTE: Buffer->TTime has nothing to do with the global variable TTime. The former is the "Top Time" of the packet, ie the time the packet got to the front of the queue; the latter is "Transmission Time" for one bit, in ITUs. The Smurph manual calls this TRate, but it's not a rate and I got tired of being confused with it being called a rate. This was before I had heard of Buffer->TTime. Oh well.] I won't go through the rest of the state machine. Just note a few things: - a process goes to sleep only when execution falls off the bottom of a state or when an explicit "sleep" command is seen. - commands such as "Timer->wait (PSpace - IPeriod, Xmit);" do NOT put the process to sleep immediately; it just adds this event to a list of events "I'm interested in", that should cause this process to change states at some time in the future. The first event that happens causes the corresponding state to be entered (in this case, when the inter-packet gap has been satisfied, we go to the Xmit state). This list of "interesting" events is erased and must be rebuilt at every new state. Testing your simulator ---------------------- Once you have built our simulator using the command mks -f -v -m -n -i -t -q -o ether main.cc test it on the input "test.in". After a few seconds (unless you're running on a Sun 3) you should get output exactly the same as test.out, except for the date on the very first line and probably the "CPU time" field. If not, something may be wrong (unless Smurph somehow chooses different default random number seeds for some reason, which I don't think it should). That's it! Happy simulating!