From da9122a2fb2a31b0756b79a8cf7e24aadc9636dd Mon Sep 17 00:00:00 2001 From: Richard Whitehouse Date: Fri, 20 May 2011 09:07:25 +0100 Subject: [PATCH] Corrections --- conclusion.tex | 4 ++-- evaluation.tex | 12 ++++++------ implementation.tex | 12 ++++++------ preparation.tex | 8 ++++---- proforma.tex | 4 ++-- 5 files changed, 20 insertions(+), 20 deletions(-) diff --git a/conclusion.tex b/conclusion.tex index c350bf0..052f77a 100644 --- a/conclusion.tex +++ b/conclusion.tex @@ -6,7 +6,7 @@ Based on the work outlined in this dissertation, there are a number of areas of \subsection{Dynamic Routing} -At the moment this dissertation relies on static routing, based on a each switch being told of its neighbours. While in some situations this is a possiblity, by directly managing the switch, it would be realistic to have the switches dynamically configure themselves. +At the moment this dissertation relies on static routing, based on a each switch being told of its neighbours. While in some situations this is a possibility, by directly managing the switch, it would be realistic to have the switches dynamically configure themselves. In terms of Ethernet, this would be done by implementing the Rapid Spanning Tree Protocol described in \cite{ieee802-1d}. @@ -18,7 +18,7 @@ By using the link state data further, it would be possible for the MOOSE protoco \section{Summary} -In this dissertation I have succesfully created working implementations of MOOSE, and Ethernet for a modern network simulator, ns3. This has involved teaching myself a large number of technologies: MOOSE, the workings behind ns3 and the build system it uses, the detailed implementation of Ethernet, to support knowledge I have learned elsewhere in the Tripos, such as in Principles of Communication. I have expanded on my knowledge of using C++ to create a system of significant size which can be used by other people for research in the future. +In this dissertation I have successfully created working implementations of MOOSE, and Ethernet for a modern network simulator, ns3. This has involved teaching myself a large number of technologies: MOOSE, the workings behind ns3 and the build system it uses, the detailed implementation of Ethernet, to support knowledge I have learned elsewhere in the Tripos, such as in Principles of Communication. I have expanded on my knowledge of using C++ to create a system of significant size which can be used by other people for research in the future. The MOOSE implementation is fully functional, maintaining state information, rewriting packets, including ARP requests and responses. I have designed experiments to show that my switch works under a variety of conditions and have included information to show the differences between the protocols. These included data on the different properties of the routing protocols, with MOOSE outperforming Ethernet in terms of unicast routing, while Ethernet performs better than MOOSE under broadcast. diff --git a/evaluation.tex b/evaluation.tex index 8af70e1..b243025 100644 --- a/evaluation.tex +++ b/evaluation.tex @@ -29,13 +29,13 @@ The second test provides further evidence that the switches are operating correc Evidence of the effect of the different forwarding systems can be found in the third test, where Host 4 sends a packet to Host 6. In the case of Ethernet, this travels via Switch 2, Switch 0, Switch 1 and then Switch 3, before arriving at Host 6, and the reverse for 6 to 4. This is because the spanning tree protocol turns the graph into a tree by disabling the link between Switch 2 and Switch 5. In the case of MOOSE however, it travels from Host 4, to Switch 2 then Switch 3 then Host 6, and the reverse for 6 to 4, as MOOSE uses a more advanced forwarding protocol. For the unicast packet this results in a considerable increase in the number of Ethernet datagrams required. -\subsection{Efficency of Packet Forwarding} +\subsection{Efficiency of Packet Forwarding} -In this test, we are looking at the efficency of the packet forwarding system. +In this test, we are looking at the efficiency of the packet forwarding system. -We can measure this by counting the total number of Ethernet frames for a packet to go between two hosts. With a ineffficent forwarding system it will require more frames than in an efficent forwarding system. +We can measure this by counting the total number of Ethernet frames for a packet to go between two hosts. With a inefficient forwarding system it will require more frames than in an efficient forwarding system. -I will use this to compare Ethernet's system, where the forwarding protocol keeps a state table storing which host is off which port, which is used with the spanning trree to forward packets, to the MOOSE system, which uses a Link State routing protocol to keep track of switches, as well as learning the address of local hosts. +I will use this to compare Ethernet's system, where the forwarding protocol keeps a state table storing which host is off which port, which is used with the spanning tree to forward packets, to the MOOSE system, which uses a Link State routing protocol to keep track of switches, as well as learning the address of local hosts. We need to look at two different types of addressing as well. Packets in Ethernet can either be broadcast, or unicast, so both mechanisms will be studied. @@ -78,9 +78,9 @@ Here we have a mesh network topology with 25 switches in the mesh, shown in Figu MOOSE performs poorly when packets are broadcast. This is due to the selection of Reverse Path Forwarding to prevent broadcast storms. Broadcast storms are scenarios in which packets that have been set as broadcast loop around a series of links, causing network saturation, reducing the effective utility of the network. In order to prevent this, some mechanism must be used to prevent this happening by culling duplicate frames. -Reverse Path Forwarding works by detecting that a frame did not come from the most efficent route from source, and thus it is a duplicate, which allows it to be safely discarded. In MOOSE this works by looking at the source and port combination with which a frame arrives at the switch and checking in the switch that a frame sent to that switch would be sent on the same port. If it is, then the frame is flooded on all other ports, in the case of broadcast, otherwise it is dropped. This means that each frame is forwarded to one hop more than it would if a spanning tree existed, as it is only detected as a inefficent route on arrival at a switch, not before it is flooded. +Reverse Path Forwarding works by detecting that a frame did not come from the most efficient route from source, and thus it is a duplicate, which allows it to be safely discarded. In MOOSE this works by looking at the source and port combination with which a frame arrives at the switch and checking in the switch that a frame sent to that switch would be sent on the same port. If it is, then the frame is flooded on all other ports, in the case of broadcast, otherwise it is dropped. This means that each frame is forwarded to one hop more than it would if a spanning tree existed, as it is only detected as a inefficient route on arrival at a switch, not before it is flooded. -In a fully connected mesh network, this causes poor broadcast performance, as after the first switch floods the frame to all other ports, each switch which recieves it will have received it on the most efficent port and will flood the frame again. However, all of the switches to which it floods the frame will already have recieved the frame and thus it will be a duplicate. +In a fully connected mesh network, this causes poor broadcast performance, as after the first switch floods the frame to all other ports, each switch which recieves it will have received it on the most efficient port and will flood the frame again. However, all of the switches to which it floods the frame will already have recieved the frame and thus it will be a duplicate. As a result of this, the MOOSE protocol performs especially badly here, requiring 1156 broadcast frames to perform the simulation, 578 from each transmission. One frame is from the host to the switch, then 24 frames to each of the connected switches, followed by each of those switches sending another 24 frames, plus an additional frame from one switch to the host. diff --git a/implementation.tex b/implementation.tex index c65540f..1ba748c 100644 --- a/implementation.tex +++ b/implementation.tex @@ -47,19 +47,19 @@ First it creates a node to represent each of the hosts and bridges in the topolo Once it has done this, it configures the routing. Early in the project, I decided to allow two different forms of routing, static and dynamic. -Static routing is done at setup time by running an algorithm across all the ndoes to determine the network map. In the case of Ethernet it runs a static spanning tree algorithm, whereas in MOOSE it runs a all pairs shortest path algorithm by running Dijkstra's algorithm on each node. It can do this more efficently than running Johnson's algorithm as all the path costs are known to be positive. This is implemented using the Boost Graph library implementation of Dijkstra's algorithm \cite{boostgraph}. +Static routing is done at setup time by running an algorithm across all the nodes to determine the network map. In the case of Ethernet it runs a static spanning tree algorithm, whereas in MOOSE it runs a all pairs shortest path algorithm by running Dijkstra's algorithm on each node. It can do this more efficiently than running Johnson's algorithm as all the path costs are known to be positive. This is implemented using the Boost Graph library implementation of Dijkstra's algorithm \cite{boostgraph}. Dynamic routing on the other hand relies on the interchange of BPDU - Bridge Protocol Data Units for Ethernet as outlined in \cite{ieee802-1d} for the Rapid Spanning Tree protocol. MOOSE however can use a routing protocol - OSPFM (Open Shortest Path First for MOOSE), an implementation of OSPF \cite{rfc2328}, is suggested in \cite{dwh}. This happens during the running of the simulation. -Once the routing has been configured, the Link Layer Helper initalises a BridgeNetDevice on each bridge node in the case of Ethernet, or a MooseBridgeNetDevice in the case of MOOSE. This represents a switch and contains the implementation of the Link Layer protocol on the switch. The BridgeNetDevice and MooseBridgeNetDevice objects are created through the use of another factory class, BridgeNetDeviceHelper and MooseBridgeNetDeviceHelper respectively. These are responsible for creating the bridge and ports on the bridge. +Once the routing has been configured, the Link Layer Helper initialises a BridgeNetDevice on each bridge node in the case of Ethernet, or a MooseBridgeNetDevice in the case of MOOSE. This represents a switch and contains the implementation of the Link Layer protocol on the switch. The BridgeNetDevice and MooseBridgeNetDevice objects are created through the use of another factory class, BridgeNetDeviceHelper and MooseBridgeNetDeviceHelper respectively. These are responsible for creating the bridge and ports on the bridge. -A pre-existing BridgeNetDevice implementation existed in ns3 for Ethernet; it was incomplete, with no support for RSTP (Rapid Spanning Tree Protocol). It also had no limit on the size of the state table, and was implemented in a single class. I decided to split it up into several different classes to separate the different concerns. It now uses a BridgeNetDevice, with each port on the Bridge represented as a number of BridgePortNetDevice objects which controls the reception and transmission of packets on each port, and a BridgeState class which holds the state table for the Bridge. By performing this separation of concerns, the implementation ensures that each concern is handled efficently. +A pre-existing BridgeNetDevice implementation existed in ns3 for Ethernet; it was incomplete, with no support for RSTP (Rapid Spanning Tree Protocol). It also had no limit on the size of the state table, and was implemented in a single class. I decided to split it up into several different classes to separate the different concerns. It now uses a BridgeNetDevice, with each port on the Bridge represented as a number of BridgePortNetDevice objects which controls the reception and transmission of packets on each port, and a BridgeState class which holds the state table for the Bridge. By performing this separation of concerns, the implementation ensures that each concern is handled efficiently. A similar approach was taken to implementing the MooseBridgeNetDevice, which again has a number of MooseBridgePortNetDevice objects to represent each port on the bridge, and a MooseBridgeState object to hold the bridge's state. Along side these core classes, a number of different types were created to hold the MOOSE data required. These were MooseAddress, MoosePrefixAddress and MooseSuffixAddress, which hold the MOOSE Address components required to implement MOOSE. The former can readily be convered to and from a Mac48Address, ns3's implementation of a MAC Address, which allows it to be used to interogate MAC addresses. MooseAddress gives three types of MAC Address, HOST which is used for a globally administered MAC Address, which is used by normal Ethernet devices, MOOSE which represents an address assigned by a MOOSE switch and MULTICAST which is a MAC address used for multicast/broadcast, and thus not translated to a MOOSE address. -The final stage of network setup is to initalise the hosts. Each hosts is given a standard IPv4 stack, complete with IP, ARP, ICMP, UDP and TCP/IP. This is the base from which we simulate packets across the network +The final stage of network setup is to initialise the hosts. Each hosts is given a standard IPv4 stack, complete with IP, ARP, ICMP, UDP and TCP/IP. This is the base from which we simulate packets across the network \subsubsection{Data} @@ -89,7 +89,7 @@ Finally, once the setup is complete and the trace files are connected to the cor In order to get useful data, the files emitted from the simulation stage must be analysed and compared. The primary resource for this stage is the CSMA ASCII trace file which lists each time a packet is enqueued onto a Ethernet transmission queue, when it is dequeued, if it is dropped and when it is received by a node. It lists the time of each action, the node it was operated on and the packet headers for the packet in question. -By analysing this file we can gain an insight into how efficent the routing protocols are, how long each packet took to traverse the network and other simulation metrics. +By analysing this file we can gain an insight into how efficient the routing protocols are, how long each packet took to traverse the network and other simulation metrics. The analysis program parses the CSMA file and collects statistics on the packets observed before outputting them to a file. These include the number enqueued, dequeued, recieved and dropped. The packets are classified into ARP requests, ARP responses and UDP packets. Counts are also kept for unicast and broadcast packets, as well as a total. It also looks at the state table, and counts the number of entries for each table, for each bridge. @@ -165,7 +165,7 @@ The algorithm executes in the following way. \end{enumerate} -The algorithm assumes that all the nodes are connected, and that all links are bidrectional, which is the case is the networks I am testing. In the case I am testing the priority queue is also replacable by a normal queue under the condition that all the links have equal cost traversal, which is also the case. +The algorithm assumes that all the nodes are connected, and that all links are bidrectional, which is the case is the networks I am testing. In the case I am testing the priority queue is also replaceable by a normal queue under the condition that all the links have equal cost traversal, which is also the case. %\subsection{Rapid Spanning Tree} diff --git a/preparation.tex b/preparation.tex index 0210e3c..7a4cf25 100644 --- a/preparation.tex +++ b/preparation.tex @@ -40,7 +40,7 @@ As Ethernet addresses contain no routing information, unlike IP addresses in whi Current trends in data centres, with large numbers of machines in a dense configuration \cite{facebook}, with each machine able to contain multiple hosts via virtualisation software such as Xen \cite{xen}, giving each host a virtual Ethernet controller, it is increasingly likely that this limit will be exceeded \cite{moose1}. This will cause any host whose state isn'tstored in the switch to have their frames entering the switch to be flooded as a new frame on every port. As such the overall traffic on the network will increase, decreasing the utilisation and increasing the delay per packet. -Another limitation is that when the spanning tree protocol converts the network to a tree from the inital graph topology, it disables the number of available links. By doing this, it reduces the available network bandwidth. With a better routing protocol, these links could be put to use to decrease the shortest path between two hosts, as well as being used for multipath routing. +Another limitation is that when the spanning tree protocol converts the network to a tree from the initial graph topology, it disables the number of available links. By doing this, it reduces the available network bandwidth. With a better routing protocol, these links could be put to use to decrease the shortest path between two hosts, as well as being used for multipath routing. \subsection{MOOSE} @@ -94,11 +94,11 @@ Tcl, Tool Command Language, is a scripting language specifically designed for cu ns3 is a complete rewrite of the ns network simulator, again in C++, with Python bindings instead of Tcl. It began in 2006 as a new software development effort intended to focus on improving the software design, architecture, integration and modularity of the existing ns codebase. It was designed as a four year project to produce the next version of ns. It was based on the design of GTNets and is built using the Python based waf build program. -ns3 includes a representative implemention of Ethernet. It includes the necessary support structures to resemble both LLC, Logical Link Control, and DIX, DEC, Intel and Xerox, the three major participants in the design, Ethernet frame types. However, it is only a CSMA, Carrier Sense Multiple Access implementation, as it provides no modelling of the physical layer. As I will be simulating fully switched networks using full duplex links, the lack of Collision Detection will not affect the results I collect. +ns3 includes a representative implementation of Ethernet. It includes the necessary support structures to resemble both LLC, Logical Link Control, and DIX, DEC, Intel and Xerox, the three major participants in the design, Ethernet frame types. However, it is only a CSMA, Carrier Sense Multiple Access implementation, as it provides no modelling of the physical layer. As I will be simulating fully switched networks using full duplex links, the lack of Collision Detection will not affect the results I collect. ns3 includes a sample Ethernet Bridge implementation, however this is not 802.1D compliant as it is lacking support for a Spanning Tree protocol, it simply filters and floods packets. -ns3 allows the use of Python to control the simulation. However in ns3 Python is desigined as a optional part of the interface to ns3, and it is perfectly possible to run large simulations written entirely in C++. By solely using C++, writing applications which link with libns3, the application can scale to far more hosts, and doesn't need a heavy binding which is required when using Python, or when using Tcl with ns2. +ns3 allows the use of Python to control the simulation. However in ns3 Python is designed as a optional part of the interface to ns3, and it is perfectly possible to run large simulations written entirely in C++. By solely using C++, writing applications which link with libns3, the application can scale to far more hosts, and doesn't need a heavy binding which is required when using Python, or when using Tcl with ns2. Unlike ns2, ns3 is in active development and is considered the natural successor to ns2, once the remaining protocols have been implemented for ns3. @@ -120,4 +120,4 @@ I decided to use a iterative development method, in order to maintain quality of In order to version and backup my code, I used a distributed version control system, Git. Git allowed me to maintain multiple copies of my code, review changes and manage the code effectively. My git repository was held on both my desktop and a laptop, and a copy of the repository was pushed to my server hosted offsite, and a commercial service GitHub \cite{github} which provides hosting for Git repositories. It also provides a good interface to view changes between different branches of the code. -In addition to my code, documentation and test routines were held in separate git repositories, which were again held in multiple places to protect against failiure. +In addition to my code, documentation and test routines were held in separate git repositories, which were again held in multiple places to protect against failure. diff --git a/proforma.tex b/proforma.tex index 9be0086..ebb11f2 100644 --- a/proforma.tex +++ b/proforma.tex @@ -4,7 +4,7 @@ \begin{tabular}{ll} Name: & \bf Richard Whitehouse \\ College: & \bf Homerton College \\ -Project Title: & \bf Implementation of Data Link Layer Protocols for a Network Simulator \\ +Project Title: & \bf Implementation of Data Link Layer \\ & \bf Protocols for a Network Simulator \\ Examination: & \bf Part II, Computer Science Tripos, July 2011 \\ Word Count: & \bf 10000 \\ Project Originator: & Malcolm Scott \\ @@ -14,7 +14,7 @@ Supervisor: & Malcolm Scott \\ \section*{Original Aims of the Project} -To write a implementation of MOOSE for a modern network simulator which functions correctly with respect to the protocol, in that it rewrites packets, and performs correctly in a network of other simulated MOOSE and Ethernet switches. To form network topologies which seek to show the differences between MOOSE and Ethernet. To evaluate said topologies by showing the difference under different metrics. To collect said metrics showing the efficency of the routing, the size of the state table and the amount of overhead. +To write a implementation of MOOSE for a modern network simulator which functions correctly with respect to the protocol, in that it rewrites packets, and performs correctly in a network of other simulated MOOSE and Ethernet switches. To form network topologies which seek to show the differences between MOOSE and Ethernet. To evaluate said topologies by showing the difference under different metrics. To collect said metrics showing the efficiency of the routing, the size of the state table and the amount of overhead. \section*{Work Completed} -- 2.34.1