III) Theory of Simulation

To facilitate simulation of a packet routed indirect MPP topologies I assumed that all links in a topology were generic and thus capable of transmitting an equal number of packets in the same time frame. To further abstract from hardware, I also assumed that each node is functional and has sufficient buffer size and routing speed to enqueue all incoming packets and dequeue outgoing packets at the speed of the outgoing links. This assumption allows the simulation to focus more on the physical characteristics of link interconnection and routing methods, and less on the implementation of node hardware. This also simplifies the chore of memory allocation by allowing a centralized packet heap for each topology instance.
This approach of simulation will be able to indicate problems with both packet livelock and deadlock in an IN by performing simulation runs involving many routing cycles. This is because the simulator is designed never to drop packets, so packets which are livelocked will hop around the network incrementing their hops counter and packets which are deadlocked will sit in the pkts[] heap accumulating their wait counter. When the simulation has injected the requested number of packets, all new network traffic will cease and eventually the network will drain and all packets must be routed to destination before the simulation completes. Since each packet is logged for number of hops and wait cycles it encountered, it would be a simple matter to flag livelocked packets as those with unusually high hops and deadlocked packets as those with excessive cycles waited. This does limit the simulator capabilities, however, since it keeps track of every packet in a centralized packet heap and there is currently no mechanism to suppress nodes from injecting new packets into a congested network. Therefore in extreme congestion the simulator can experience large growth in memory allocation and processor utilization per each simulation cycle. A maximum memory to allocate limit is specified in config.h of the simulator code files, if this threshold is breached the traffic generator will cease injecting packets and continue to route out all remaining packets in the pkt[] heap.
Presently there is no log in a simulation packet to locate which nodes each packet hopped to or waited at, but from analysis of packets with similar routes and data for each node link including the number busy cycles, it should be apparent when any links become bottle necks.