Parametric model of switched Ethernet in the form of a colored Petri net is presented. The model is invariant regarding the structure of the network; it has fixed number of nodes for any given tree-like network. Special measuring fragments, which accomplish the model, provide the evaluation of the network throughput and the frame delivery time directly in the process of simulation. The anomaly of Ethernet switches' mutual blocking has been revealed.
At present Ethernet technology dominates the sector of local area networks. Moreover, 1Gb and 10Gb standards allow positioning Ethernet as a universal networking technology, because providers widely apply «Ethernet over DWDM» solutions in backbone networks. Design of effective local and backbone networks requires reliable estimations of throughput and the quality of service. Recently the model driven development of telecommunication networks and devices becomes prospective. It is based on express-evaluations of characteristics obtained in the shortest time for new project decisions that determine the relevance of the present research.
Colored Petri Nets [1] and CPN Tools [2] are successfully used for modeling Ethernet [3-5], TCP/IP and MPLS [6], wireless Bluetooth [7] networks. Colored Petri Nets allow not only the modeling of telecommunication networks, but also the estimation of their characteristics via special measuring fragments [4,8] during the process of simulation.
The mentioned papers are based mainly on the modular approach to the telecommunication networks models construction: a model of a network is composed of DTE (workstation, server) and DCE (switch, router) submodels, which were built earlier. The essential disadvantages of this approach are the following: the necessity of the model rebuilding for each new structural scheme of the network, great number of used Petri net elements that considerably delay the processes of models construction and analysis.
The parametric model of switched Ethernet presented in [5] has a fixed structure for an arbitrary tree-like network; its elements are switches, workstations and servers. The definite structure of a network is an input in the form of packed matrices as the marking of corresponding Petri net places. However, in [5] only the principles of a parametric Petri models construction were studied and the questions about the evaluation of the modeled networks characteristics were not considered.
The goal of the present work is constructing the measuring fragments for parametric model of switched Ethernet for the evaluation of throughput (traffic), the quality of service (frame delivery time), the size of the switches internal buffers. Moreover, for the confirmation of the built models adequacy, the technique for the mentioned characteristics measuring on real-life networks was developed.
The model presented in [5] was refined in the following way: the expressions in the transitions guards were simplified via variables superposition; the limitations of the switches internal buffer size were added; the places, which describe the dump of frames for the following calculation of characteristics, were added.
The model is represented in Fig. 1; the declarations of colors (color), variables (var) and functions (fun) used in the model and measuring fragments are represented in Fig. 2. The peculiarity of the parametric model is the special tags added to frames, which contain switch and port numbers and provide the frames reentrance. The model has a fixed structure and contains 14 places and 8 transitions of Petri net for an arbitrary tree-like structure. The components of the model are switches, workstations and servers. The left part of Petri net models all the Ethernet switches (the names of the elements names do not have any suffix), the right upper part – all the workstations (the names of the elements have WS suffix), the left lower part – all the servers (the names of the elements have S suffix); the pair of places inPorts, outPorts model all segments. Names “in/out” are chosen with respect to the switches; they model the full-duplex mode of work. Additional places received, sent model the frames dump by DTE, places inSW, outSW model the frames dump by switches. Additional names rcvd, snd, inSWITCH, outSWITCH are used for the connection with model pages, which calculate characteristics described in the next section.
A definite structure of modeled network is specified by the marking of places swtab, SwichLink, Attach. The place swtab contains the switching tables of all the switches. The switching tables are represented by corteges swi (destination address, port, switch). The place SwichLink describes the connections of switches (uplinks), which are represented by corteges swl (switch1, port1, switch2, port2). The place Attach describes the DTE connection, which is represented by corteges swi (address, port, switch). In Fig. 1 the marking of the places corresponds to the Railway dispatcher center LAN represented in Fig. 3.
outSW
outSWITCH buflimit
(sw,bcur)
received
rcvd
(src,dst,nf,cT())
avail(sw,p)
mac2s (src,dst,nf,cT())
dst
1`1++1`2++1`3++
1`4++1`5++1`7
ownWS
mac
1`avail(
Attach 1`(
AttachWS 11``((35,,32,,12))++++11``((46,,13,,22))++++ 1`(
sendWS (src,dst,nf+1)@+Delay() rqWS
avail(sw,p) (src,dst,nf) mac2
bufLoad
buflimit 1`(
(sw,bcur) (sw,blim) swtab
swi
1`(
swl
(dst,p2,sw)
(src,dst,p2,sw,nf)
f(src,dst,p2,sw2,nf)
[bcur<blim]
get f(src,dst,p1,sw,nf) inPorts
@+2 avail(sw,p1) seg
1`avail(
Attach (src,dst,nf)
swAittachS 111```(((531,,,231,,,211)))++++++111```(((642,,,312,,,221)))++++++ execS avail(sw,p) (src,p1(,ss`wr(c7),,d2s,t3,n)+f)+1re`p(l8y,S3,3)frNasmeend@()+`D(desxte,scr(c),nf) 1`6++1`8
ownS (src,dst,nf,cT()) inSW inSWITCH buflimit snd sent
mac2s
Fig. 1. Parametric model of switched network
Moreover, the model contains the following parameters: workstations addresses ownWS, servers addresses ownS, matrix of workstations requests to servers rqWS, switch buffer size limit bufLim. Random functions Delay(), Dexec(), Nsend() define the periodicity of workstations requests, the duration of the workstation request execution by server and number of the servers response frames correspondingly.
In the model, the time delays are represented in MTU (Model Time Unit), the sizes – in frames, which have maximal length. Time and date size scaling was considered in [4]. In the model represented in Fig.1, the time delay corresponds to 100 Mbps Ethernet, 1MTU=10 ms, the maximal frame size is 12304 bit. Delays of the sending transitions sendWS, sendS contain the time of frames transmission through segment, delays of the receiving transitions receiveWS, receiveS contain only the delays, which correspond to the devices performance (Ethernet adapters, switches). Frequency of workstations requests is 10-20 µc; the time of requests execution by server is 1-2 µc; requests length is 1 frame, servers answers length is 10-20 frames.
The model represented in Fig.1 describes the work of all the switches with obligatory frames buffering and all the ports having the same transmission speed. For frames buffers of switches and servers, the random choice discipline was realized. In the evaluation of real-life networks characteristics more complicated variants of models are used. Queues with FIFO discipline are realized for buffers. The transition Direct is added for direct forwarding of received frame into the output port (if the queue is empty and the destination port is free). Delay matrices are used for modeling different ports transmission speeds.
The description of model elements which are added for posterior evaluation of characteristics using measuring fragments should be considered in detail. Additional elements model the processes of the frames dump studied in Section 5. At the instant of the frame transmission by a terminal device into a segment via transitions sendWS, the copy of its header containing sender address scr, destination address dst, ordinal number of frame for the device nf, and also the time stamp of current model time obtained by function cT() are saved into the place sent. In the similar way at the instant of the frame receiving by a terminal device via transitions receiveWS, receiveS, the copy of its header is saved into the place received. Moreover, the dump is executed at the receiving/transmitting frames by switches into places inSW, outSW that model the work of switches statistical subsystem or external packets analyzers attached to the corresponding ports. In the present research such information as switch number sw and the current size of switch buffer bcur for each input/output frame are saved. colset mac=int with 1..8; colset portnum=int with 1..4; colset swch=int with 1..3; colset nfrm=INT; colset mac2=product mac*mac*nfrm timed; colset mac2s=product mac*mac*nfrm*INT timed; colset sfrm=product mac*mac*nfrm*INT timed; colset frm=product mac*mac*portnum*swch*nfrm timed; colset nseg=product swch*portnum; colset seg=union f:frm+avail:nseg timed; colset swi=product mac*portnum*swch; colset swf=product mac*mac*portnum*swch*nfrm timed; colset frame=product mac*mac*nfrm timed; colset swl=product swch*portnum*swch*portnum; colset buflimit = product swch * INT; colset pairch=product mac*mac*INT; colset zero=int with 0..0; colset pairch0=product mac*mac*zero; colset dex= int with 100..200; colset nse = int with 10..20; colset Delta= int with 1000..2000; var src,dst: mac; var sw,sw1,sw2:swch; var p,p1,p2: portnum; var i,t,t1,t2,q,mt,dt,mx,s,pt,m,a,av : INT; var blim, bcur, bmax: INT; var nf,nf1: nfrm; val bitms=12304*10; fun Dexec()=dex.ran(); fun Nsend()=nse.ran(); fun Delay()=Delta.ran(); fun cT()=IntInf.toInt(!CPN'Time.model_time)
The technique of measuring fragments was earlier presented and studied in [4] for nonparametric models. Its main idea consists in the following: as a colored Petri net is a universal algorithmic system, the algorithms of the characteristics calculation may be described by additional fragments of Petri net named by measuring fragments (MF). The model accomplished with measuring fragments implements the calculation of telecommunication network characteristics directly during the process of simulation. The measuring fragments of parametric model for evaluation of traffic, frames delivery time and the size of switches internal buffers are constructed further. Measuring fragments are drawn in red color.
The evaluation of traffic is implemented on the basis of delivered frames dump within terminal devices. It should be noticed that the evaluation might also be implemented on the basis of sent frames dump and the percentage of dropped frames might be obtained. As in the parametric model represented in Fig. 1 the frames dropping process is not modeled, both mentioned evaluations coincide.
The measuring fragment for traffics evaluation is shown in Fig. 4. The fusion place newFrame receives the dump of the regular frame received by the terminal device from the network model (Fig. 1). Transition procFrame saves its copy into the place newDbl for the delivery time evaluation MF and starts the recalculating of characteristics which are stored into places nFrm, nFrmAll, trafficAll, traffic. Note that, the formulae of recalculation are represented by the inscriptions of corresponding arcs.
nFrm pairch pairch0.all()
The place traffic stores the traffic matrix for each pair of MAC-addresses represented with corteges in the form (addr1, addr2, traffic). That allows the evaluation of asymmetrical traffic as the cortege defines the direction of transmission. For the calculation of traffic, the place nFrm is used that stores the matrix of transmitted frames quantity in the form (addr1, addr2, quantity). Each firing of the transition procFrame increases the quantity of received frames for each pair of addresses: (src, dst, q+1). Traffic is calculated via the division of received frames number by the current model time; the constant bitms is used for the reduction of dimension to bit/ms. The simplest formula used for traffic calculation is the following:
traffic = n dt , where n is the amount of delivered information, dt – the timed interval of measuring.
As in the majority of cases the traffic between each pair of devices is a too detailed characteristic, the calculation of an integral characteristic such as the total network traffic represented with the place trafficAll is provided. For its calculation 0 INT the place nFrmAll is added that stores the total number of frames received by all the terminal devices.
The evaluation of frame delivery time is implemented on the basis of calculating the difference between time stamps of the receiving and sending frame for each pair of interacting terminal devices. For the identification of a frame its ordinal number nf is used that is unique for each transmitting terminal device.
MF for evaluation of frames delivery time is represented in Fig. 5. Transition culcDT calculates frame delivery time dt. Transition culcAVR starts the recalculation of characteristics stored into places sumPair, sumAll, averPair, averAll, maxAll, maxPair, quantAll, quantPair.
sumPair
Places sumPair and quanPair store the sum of delivery times and the quantity of delivered frames for each pair of terminal devices correspondingly. They are used for the calculation of the average averPair and the maximal maxPair frame delivery times for each pair of devices. Note that, at the calculation of averages the information about a newly arrived frame is used: ((t+dt) div (q+1)). The following formula is used for the average delivery time calculation: adt = (dt1 + dt2 + ... + dtq ) q where dti is the delivery time of i-th frame, q – total number of delivered frames. Places sumAll and quantAll store the sum of delivery times and the total number of all the delivered frames correspondingly. They are used for calculation of the average averAll and maximal maxAll delivery times for all the frames transmitted within the network.
During the equipment choice and also during the telecommunication networks devices design, the task of determining the devices optimal characteristics is solved. For switches with the given transmission speed on the ports (for instance: 100Mbps, 1Gbps) such characteristics are the average time of frame switching which may be implicitly evaluated on the base of producer information about the number of frames processed in the unit of time [4] and also the size of switch internal buffer of frames.
In Fig. 6 the measuring fragment for the evaluation of switch internal buffer size is
represented. Parametric model (Fig. 1) allows the assigning of buffer size limit into
place bufLim and implements the dump of frames received and sent by switches.
1`(
buflimit
inSWI (sw,i)
inSWITCH buflimit
(sw,if i+1>bmax then i+1 else bmax)
1`(
(sw,bmax)
buflimit
in
(sw,a)
(sw,cT())
(sw,pt)
(sw,m)
1`(
buflimit
1`(
On receiving a frame by switch, the number of the switch and the current size of its buffer are stored into the place inSWI. The same information is stored into the place outSWI at the transmitting of a frame by switch. MF calculates the maximal actual size of the buffer in the place maximum and also the average size of the buffer in the place average. Auxiliary places sum and prevCT serve for the storing the sum of products and the value of the previous time instant of the size measurement for each switch. Let us consider the formula of average buffer size calculation in detail: a = (i1 ⋅ dt1 + i2 ⋅ dt2 + ... + ik ⋅ dtk ) ,
dt where i j is the size of the buffer on the time interval dt j , dt – the total interval of time measurement. As the measurement starts from the zero instant of time, the length of the total time interval equals to the current model time cT(). For calculating the current interval dt j , values of the last measurement time instant pt stored into the place prevCT for each switch are used: dt j = cT () − pt . The sum of the products represented in the numerator is accumulated into the place sum for each switch separately.
The construction of other measuring fragments is also possible, for instance, for the evaluation of collisions percentage at hubs usage, evaluation of application systems response times etc. In [4] the measuring fragments (for nonparametric Ethernet models) for the evaluation of application system GID-Ural VNIIZT response time which includes network delivery times and time of request processing by server were presented. Such an integral characteristic is the basic one during real-time systems design.
For obtaining reliable evaluations of telecommunication networks characteristics, the special organization of computational experiments with the model was implemented. As the processes of requests generation and processing into clientserver system are represented with random functions, their interaction with the communication equipment defines a stochastic process. That is why the statistical approach based on calculating the average of distribution and central statistical moments is applied. In the majority of cases two magnitudes: the average of distribution and dispersion are used.
The simulation of the net dynamics was implemented on rather prolonged intervals of model time that correspond to a few minutes of real time. At first, the existence of state stable mode of the model behavior was studied. Then the evaluation of characteristics in state stable mode was implemented.
For each time interval dti not less than twenty individual experiments were implemented. Then average adti and dispersion σ dti were calculated for each characteristic on the chosen interval. Measurements and calculations were repeated for doubled time interval and so on. If the averages and dispersion coincided adti = adti+1 ,σ dti = σ dti+1 then the decision about a state stable mode existence was adopted. It should be noticed that the absence of a state stable mode might be easily observed, for instance, in case of the increase of requests frequency by factor of 100.
However, the mentioned observance is not concerned with the telecommunication equipment, but with the increase of average numbers of unsent frames into terminal equipment. Telecommunication equipment work normally providing the delivery of frames under peak load due to the modeling flow control facilities stipulated by the standards. Examples of the tables which illustrate the growth of queues in non state stable mode are shown in [8].
Further, in the state stable mode the evaluations of characteristics for various parameters combinations of hardware and software such as the requests frequency, the time duration of processing and the size of switch internal buffer were implemented. In Fig. 7 the current marking of MF for delivery time calculation (Fig. 5) obtained on time interval 168009MTU=1,68 s is represented.
Thus, the average frame delivery time equals to 36 MTU=0,36 µs; maximal delivery time equals to 415 MTU=4,15 µs. From the matrix of delivery times maxPair, it might be seen that the maximal delivery time is reached at the delivery of frames sent by the server S1 (MAC=6) to workstation WS3 (MAC=3). The shown fragments of matrices acknowledge that the transmission of the frame among the pairs of workstations as well as among the pairs of servers does not take place (corresponding values are zero).
INT INT (src,dst,mt) Int.max(mx,Int.max(mt,dt)) maxPair 64
Let us consider the dump of frames. The first column contains the intervals in milliseconds between the frames entries, then the IP-address and the port number of the sender and receiver follow. After the colon, the fields of packet header are written, such as the first and the last number of passed bytes, packet length in parenthesis, the number of confirmed byte and the window length. In the above example, 192.168.0.158 is the IP-address of the workstation; 192.168.0.130 is the IP-address of the server. Port number 139 corresponds to MS NetBIOS TCP service, port number 1172 is a randomly selected port number of client software.
Time synchronization and the frames dumps comparison in all the terminal devices allow identifying the frames and calculating their delivery times using simple software. The obtained information is a primary one for the calculation of QoS and throughput characteristics of networks. It is significant that the measuring in DTE gives us objective information about actually delivered frames. Moreover, measurements may be implemented in network devices.
Modern Ethernet switches give us wide spectrum of possibilities for the traffic measurement and analysis. For example, CISCO corporation switches, like the series Catalist 4000, 4900 (4948-10GE, ME 4924-10GE) realize the following monitoring services: the check up of the ports condition and possibilities; the analysis of the ports data Switch TopN, the system of statistics collection RMON, the ports analyzer SPAN (Switched Port Analyzer). Usually the switch has the port for immediate connection to console; moreover, it also stipulates the remote access with Telnet and Web-interface for the input of commands. Testing the state of a switch port is implemented with the following command:
show port [port_number] Testing the port resources is implemented with the command:
show port capabilities [port_number] Port statistics gathering TopN is started by the command: show top [port_number] show top report [report_number] Displaying the collected statistics is implemented with the following command: The service TopN provides the accumulation of such information as: port capacity, the quantity of sent and received bytes, the number of errors and the quantity of buffers repletion. RMON system is started with the command:
set snmp rmon enable RMON system accumulates the information about the quantity of sent bytes, received bytes and the number of errors for each port. Moreover, the supplementary possibilities are provided for alarms generation on special events.
SPAN service gives the possibility to redirect the traffic of selected port to another switch port for analysis. For example, the command:
set span [nport1] [nport2] redirects the nport1 port traffic into nport2 port. The device, which saves the frames into some file or analyzes them, can be connected to the corresponding port. In this way, it is possible to receive the information similar to the damp of frames obtained with TCPDump program.
For testing the model adequacy, the frames dump was started on terminal devices (workstations and servers) in the local area network of Railway dispatcher center (Fig. 3), equipped with GID Ural-VNIIZT system. The frames receiving time is measured, it is accumulated in the dump for a time interval, which equals to one shift (about 12 hours). The comparison of these results and the results obtained via modeling allows the following conclusion: the average error of delivery time evaluation via modeling amounts to no more than 5%. It is a good enough result that acknowledges the adequacy of the built models.
Simple evaluations of throughput and frames delivery time on the basis of maximal transmission speed of the chosen technology (100Mbps, 1, 10Gbps) are not realistic even at single switch usage because of asymmetry, pulsation and other peculiarities of realistic traffic. So, for instance, for a switch with n ports of 100Mbps technology the maximal throughput close to n ⋅100Mbps can be provided only in full duplex mode and upon even n merely at transmission of 100Mbps flows among the pairs of terminal devices.
In case of the asymmetry of traffic, the destination port of the frame arrived into the switch may be already busy with the transmission of some other frame that leads to either the storing of frame into the switch buffer or the suppression of transmitting device activity with flow control facilities and repeated transmission; as the result the delivery time is increased. Moreover, compulsory idleness of other ports leads to reduction of actual throughput.
The usage of tree-like structure of a few switches (Fig. 3) complicates the described processes and hampers its analytical evaluation. Thus, the usage of simulation models, that adequately describe the processes of frames switching according to the technologies standards and peculiarities of the traffic generating, is a prospective direction of research.
The traditional incremental way of solving telecommunication networks problems is a simple passage to the next level of technology, for instance, from 100Mbps to 1Gbps. But such solutions might be too expensive in the scale of the whole company. Moreover, a new level of transmission speed might appear insufficient for network bottlenecks.
In the present section the results of parametric model (Fig. 1) studied with the help of measuring fragments (Fig. 4, 5, 6) are presented for railway dispatcher centre LAN (Fig. 3) under the choice of various types of switches and Ethernet adapters. The topics of model parameters calculation on the characteristics of real-life equipment were studied in [8]. In Fig. 9 the dependencies of network characteristics on chosen equipment technology are shown.
It should be noticed, that in the regular mode the network should provide the transmission of the whole traffic of servers and workstations. In the considered example of the network each workstation generates two flows of average intensity of 1 frame in 15 ms; in the response to the request each of the servers generates 12 flows (2x6) of 15 frames 15 ms each. Thus, the rough evaluation of the total traffic may be represented as:
traffic = (12 ⋅16 ⋅12304) 0,015 = 157491200bps ≈ 157Mbps
Starting from the standard transmission speed of the chosen technology and the maximal frame length, the possible minimal (ideal) frame delivery time equals to: 1,23 µs for 10Mbps, 123 ms for 100Mbps, 12,3 ms for 1Gbps and 1,23 ms for 10Gbps. Even at a single switch usage that provides cutting-through transmission without complete buffering, the minimal delivery time is increased. After receiving the frame header, the switch requires definite time for the header analysis and determining the destination port according to the switching table. This time may be estimated on the basis of either declared performance of the switch that is measured in frames per second or the performance of the switch internal bus. So, for instance, declared performance of Intel SS101TX4EU switch equals approximately to 10000 frames per second which corresponds to the frame processing time of about 100 ms; notice that real-life delay may exceed mentioned delay because of the parallel work of ports. For switch Cisco ME 4924 only the performance of internal bus 49 Gbps was declared that corresponds to 251 ns delay. Moreover, real-life performance of Ethernet adapters is distinguished from the maximal transmission speed of the chosen technology. So, for instance, Ethernet adapter Intel Ether Express PRO/100 provides maximal transmission speed 92,1Mbps that corresponds to the frame transmission delay of 144 ms.
From Fig. 9a) it can be seen that 10Mbps technology does not provide the transmission of all the generated flows of frames; the state stable mode is not reached in the system containing networking and terminal equipment that is acknowledged by the growth of the queues length into the place replyS. More fast technologies provide the transmission of all the flows; throughputs differ in the bounds of dispersion. But delivery times (Fig. 9b) differ considerably; note that, different units of delivery time measurement were used for different technologies. The total tendency is that the maximal delivery time exceeds the average merely tenfold. The decrease of maximal delivery time for 10Mbps technology may be explained by the considerable fall of throughput. During the study of the mentioned characteristics for various performance of Ethernet adapters and switches and also buffer sizes of chosen switches, only minor variation of characteristics was revealed merely in the bound of dispersion. Thus, for the considered traffic generated with periodical requests of workstations to servers, only the choice of technology is essential; the differences in the equipment performance actually do not affect the characteristics of the network. Note that, the maximal delivery time (Fig. 5, place maxALL) can be used as an estimation of guaranteed delivery time for real-time systems with hard timed bounds. For systems with soft timed bounds, average delivery time (Fig. 5, place averALL) can be used in estimations.
Network capacity Delivery time
During the study of the model under the small sizes of switch internal buffer of frames, an anomaly leading to mutual blocking of all the switches work was revealed. The mentioned anomaly might take place at arbitrary buffer sizes and specific peculiarities of traffic but with the increase of the buffer size its probability reduces considerably. Fig. 10 shows the simplest variant of switches mutual blocking in a network consisting of two switches with the buffers size equaling to 2 frames (value 1 for the model).
Suppose that two frames have arrived into Switch1 with the destination address of Switch2 terminal devices and at the same time two frames have arrived into Switch2 with the destination address of Switch1 terminal devices. Suppose each of the switches started the transmission of its first frame. As, the frame cannot be located into the buffer, each of the switches suppresses the transmission of the frame using flow control facilities. The mutual blocking of the switches occurs. The considered clinch does not occur in case of using cut-through switches that work without compulsory buffering. In this case Frame1 of Switch1 is directly forwarded by Switch2 to the corresponding port of destination terminal device. Moreover, in reallife switches the operation of the frames dropping is implemented for the frames the storing time of which exceeds the limits. Thus, the clinch is eliminated but the performance of the switch falls dramatically due to the inevitable dropping of the frames.
Thus, in the present work the refined parametric model of switched Ethernet was presented that is invariant with respect to network structure and the quantity of attached communication and terminal devices. The model was accomplished by measuring fragments providing the evaluation of throughput, frame delivery time and switches buffer sizes during the process of simulation.
The adequacy of the model has been confirmed by real-life networks characteristics measurements; the analysis of modeling results was implemented for various types of used equipment. The area of obtained results application is the design of telecommunication networks and devices close to optimal.