From 8bbfe247b42fe3c548dd7b4f01232a058d90bf41 Mon Sep 17 00:00:00 2001 From: Richard Whitehouse Date: Fri, 20 May 2011 01:35:25 +0100 Subject: [PATCH] Corrections based on mas90's comments --- conclusion.tex | 18 ++++++++++-------- evaluation.tex | 34 ++++++++++++++++++---------------- 2 files changed, 28 insertions(+), 24 deletions(-) diff --git a/conclusion.tex b/conclusion.tex index 44ab529..c350bf0 100644 --- a/conclusion.tex +++ b/conclusion.tex @@ -2,25 +2,27 @@ \section{Future Work} -Based on the work outlined in this dissertation, there are a number of areas of possible enhancement. +Based on the work outlined in this dissertation, there are a number of areas of possible enhancement to the implementation described here. -\section{Dynamic Routing} +\subsection{Dynamic Routing} -At the moment this dissertation relies on static routing, based on a each switch being told of it's neighbours. While in some situations this is a possibly, by directly managing the switch, it would be useful 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 possiblity, by directly managing the switch, it would be realistic to have the switches dynamically configure themselves. -By incorporating the SAMI protocol outlined in \cite{dwh}, and the Rapid Spanning Tree Protocol \cite{ieee802-1d}, it would be advisable to create a Bridge Protocol Data Unit, BPDU, based protocol to provide for this. Once specified, this could be incorporated into the simulation to provide additional metrics for comparison. +In terms of Ethernet, this would be done by implementing the Rapid Spanning Tree Protocol described in \cite{ieee802-1d}. -\section{Spanning Tree for MOOSE} +For MOOSE, I would suggest that this should be done by implementing the SAMI protocol outlined in \cite{dwh}. Once specified, this could be incorporated into the simulation to provide additional metrics for comparison. + +\subsection{Spanning Tree for MOOSE} By using the link state data further, it would be possible for the MOOSE protocol to be smarter about how it forwards broadcast packets. Currently these are handled by using Reverse Path Forwarding, having, as shown in the evaluation this causes additional traffic, that does not occur under RSTP, as in RSTP, each broadcast packet is sent along more links than are necessary. However, the MOOSE switches could potentially use a spanning tree of the switches to provide for a minimum spanning tree implementation. \section{Summary} -In this dissertation I have succesfully implemented a working implementation 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, the waf build system, 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 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. -The MOOSE implementation is fully functional, remembering 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. +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. -I have also shown how the different protocols cause different sizes of forwarding tables in the routers, with MOOSE performing drastically better than Ethernet under some situations, while Ethernet performs marginally better than MOOSE in others. +I have also shown how the different protocols cause different sizes of forwarding tables in the switches, with MOOSE performing drastically better than Ethernet under some situations, while Ethernet performs marginally better than MOOSE in others. I have also made suggestions for how the MOOSE protocol may aim to overcome some of the limitations identified, by extending the routing protocol to improve broadcast performance. diff --git a/evaluation.tex b/evaluation.tex index 7d27962..17abb1e 100644 --- a/evaluation.tex +++ b/evaluation.tex @@ -27,7 +27,7 @@ The second test provides further evidence that the switches are operating correc \subsubsection{Forwarding protocol} -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 is forced to travel via Switch 2, Switch 0, Switch 1 and then Switch 3, before arriving at Host 6, and the reverse for 6 to 4. 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. For the unicast packet this results in a large increase in the number of Ethernet datagrams required. +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} @@ -45,12 +45,12 @@ Here we have a ring network topology, shown in Figure~\ref{fig-ring1} with 25 sw \begin{figure} \centering -\includegraphics[width=6cm]{simulation-4} +\includegraphics[width=11cm]{simulation-4} \caption{Unicast Routing Network} \label{fig-ring1} \end{figure} -The network has been designed to demonstrate the defficencies of the Ethernet protocol. This has been done by constructing the spanning tree such that the the hosts are at the bottom of different branches of the tree, as shown in Figure~\ref{fig-ring2}. As such, the direct link between switches 12 and 13 is disabled, and the packets must traverse the entire ring. While this is unlikely, it is a possible scenario, as if all hosts on a ring are communicating with each other, occasionally the worst case will be hit. +The network has been designed to demonstrate the deficiencies of the Ethernet protocol. This has been done by constructing the spanning tree such that the the hosts are at the bottom of different branches of the tree, as shown in Figure~\ref{fig-ring2}. As such, the direct link between switches 12 and 13 is disabled by the spanning tree protocol, and the packets must traverse the entire ring. While this is unlikely, it is a possible scenario, as if all hosts on a ring are communicating with each other, occasionally the worst case will be hit. \begin{figure} \centering @@ -71,28 +71,30 @@ Here we have a mesh network topology with 25 switches in the mesh, shown in Figu \begin{figure} \centering -\includegraphics[width=10cm]{simulation-5} +\includegraphics[width=11cm]{simulation-5} \caption{Broadcast Network} \label{fig-mesh} \end{figure} 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 that a frame arrives at the switch with and checking 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 destination 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 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. 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. 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. -In comparison, Ethernet, using the Rapid Spanning Tree Protocol (RSTP), uses only 52 broadcast frames, which is minimal. This is 26 frames for each broadcast of a ARP request, with one from the host to the nearest switch, 24 switch to switch and then one to destination host. +In comparison, Ethernet, using the Rapid Spanning Tree Protocol (RSTP), uses only 52 broadcast frames, which is far lower. This is 26 frames for each broadcast of a ARP request, with one from the host to the nearest switch, 24 switch to switch and then one to destination host. \subsection{State Table Size} -One of the major advantage of the MOOSE protocol is that of reduced state table sizes. Here I will show two different cases which show the difference between MOOSE and Ethernet. +One of the major predicted advantage of the MOOSE protocol is that of reduced state table sizes. Here I will show two different cases which show the difference between MOOSE and Ethernet. \subsubsection{Ethernet} -Ethernet performs better when a limited number of hosts are connected by a series of switches. In this situation 15 switches have been connected in a row, with a single host connected to the first and last switch. +Ethernet performs better than MOOSE when the majority of switches have no connected hosts. This is because Ethernet only holds state for hosts, whereas MOOSE holds state for each switch and each local host. + +In this situation 15 switches have been connected in a row, with a single host connected to the first and last switch. %\begin{figure} %\includegraphics[height=10cm]{simulation-6} @@ -104,11 +106,11 @@ Here the Ethernet protocol gives a state table size of 2 in the first and last s MOOSE performs much better than Ethernet when the hosts are distributed across a number of switches. -To demonstrate this, in this scenario, I have used a tree topology. Each tree has three layers of switches, with one switch on the node, and then branching out to $n$ switches on the layer below, with $n^2$ on the final layer. Each of the final layer of switches has 24 hosts directly attached. +To demonstrate this, in this scenario, I have used a series of tree topologies. Each tree has three layers of switches, with one switch on the node, and then branching out to $n$ switches on the layer below, with $n^2$ on the final layer. Each of the final layer of switches has 24 hosts directly attached. -The first host is designated as a sink, while each of the other hosts send two packets to the sink. This ensures that each host broadcasts an ARP query, which will ensure that all the state tables contain the relevant data. +The first host is designated as a sink, while each of the other hosts send two packets to the sink. This ensures that each host broadcasts an ARP query, which will ensure that all the state tables contain the relevant data. Sending a broadcast packet, which causes a hosts address and location to be stored in every Ethernet switch is likely due to the usage of ARP. ARP, which resolves IP addresses to Ethernet addresses, is required to communicate using the IP layer on a local area network. ARP entries expire, and when they have, and a packet is attempted to be sent to the host, they must be refetched by performing a broadcast query. -As $n$ increases, the size of the Ethernet state table grows at the same speed as $n$, while the MOOSE state table grows as the number of switches grow, which a much lower state of growth. In Figure~\ref{graph-1}, the rate of growth of the Ethernet state table is clearly demonstrated. Here the amount of memory required to realise the same topology is greatly increased. +As $n$ increases, the size of the Ethernet state table grows at the same speed as $n$, while the MOOSE state table grows as the number of switches grow, which a much lower state of growth. In Figure~\ref{graph-1}, the different rate of growth of the largest state tables is clearly demonstrated. Here the amount of memory required to realise the same topology is greatly increased. \begin{figure} \centering @@ -116,17 +118,17 @@ As $n$ increases, the size of the Ethernet state table grows at the same speed a \caption{Rate of growth of state tables} \end{figure} -\section{Limitations of the Simulation} +\section{Limitations of the Simulations Performed} -The topologies tested are not representative of existing data centres, or other networks. As such the figures gathered only represent the extreme end of the differences betwen the two protocols. +The topoloigies used in the above dissertation have been generated for the purpose of demonstrating certain phonemena. They are uniform - they have all links set to produce the same delay and same data rate. As such they should not be taken to represent the conditions found in a data center, or other network, however, they do provide a useful benchmark for comparing the two protocols and exploring how MOOSE might be deployed advantageously. -The traces used to test the topologies are very simplistic. While it is expected that this shouldn't have an impact on the evaluation made here, it is worth bearing in mind that this only demonstrates a small snapshot of the possible scenarios. +The traces used for testing the topologies are very simplistic. They are designed to demonstrate certain phonemena without incurring a high simulation overhead caused by further complexity. While this won't have any effect on the observations made here, it is worth noting that interactions between the observations made and application specific traffic should be explored further. \section{Possible Improvements} -Testing against real world traces, and incorporating dynamic versions of the routing protocols, and implementing the SAMI protocol \cite{dwh} would increase the use of the data presented here. +Testing against real world traces, and incorporating dynamic versions of the routing protocols, and implementing the SAMI protocol \cite{dwh} would increase the use of the data presented here. The SAMI protocol includes the ability to dynamically assign MOOSE addresses, and adding host mobility would cause additional overhead in the use of MOOSE. \section{MOOSE} -The developers of MOOSE should seriously consider adding a Spanning Tree Protocol instead of relying on Reverse Path Forwarding, as this simulation has shown that it performs poorly under broadcast, especially in well connected networks. +I propose that MOOSE should be modified to incorporate a spanning tree protocol instead off relying on Reverse Path Forwarding, as this simulation has shown that it performs poorly under broadcast, especially in well connected networks. This would require the link state information to be interpreted in order to perform this, however it should provide little further overhead. -- 2.34.1