1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
|
<html>
<body bgcolor="white">
<!-- $Id: Doc.html,v 1.2 1999/10/11 05:25:18 fgouget Exp $ -->
<p>infos on bing: mailing list
<h2>1. Introduction</h2>
<p>This document is a complement to the Readme file. The intent is to provide a more
detailed analysis of the mathematics behind bing and the algorithms that are used.
<p>This document may sometimes sound a bit authoritative but in its current state it
really is not. This is an early version which is still quite incoplete and chances
are that it contains errors so if you think you have found one send an email to me,
<a href="mailto:fgouget@multimania.com">fgouget@multimania.com</a>, or to the
bing mailing list.
<h2>2. Features, Bugs, Roadmap, etc.</h2>
<h3>2.1. Current features</h3>
<ul>
<li>Bing will perform the traceroute to the specified host(s).
Various forms of traceroute are supported: from a host to
another, only the specified hosts... See the manpage for
more details.
<li>Bing will measure the bandwidth of symetric links using the
echo request/echo reply method. It will provide various
statistics on the hosts and on the links.
<li>This version will analyze the measured rtts and perform
consistency checks on them. Then it will perform the linear
regressions and use them to indicate which measures can be
considered reliable and which are not. Then it will first
redo the probes that it found to be inconsistent and those
that don't fit the linear regressions well in an attempt to
produce the maximum measure improvement per packet sent.
</ul>
<h3>2.2. Bugs and other issues</h3>
<ul>
<li>The code badly needs a cleanup. I tried to do somtehing
clean and then switched to a mode where I just tried to
experiment till it worked.
<li>If there is traffic on the link attached to your computer
it seems that bing will pick up on that traffic. I'm not
sure whether this causes problems in the measures or if it's
just annoying messages because for now all the experiments I
do go through a modem so I can control all the traffic. This
is something I hope to solve when I rewrite the backend.
<li>There is a lot of messages that are just debug messages
and that pollute the display, especially on the case above.
<li>Error handling is incomplete, inexistant or incorrect
although there are some cases where it works.
<li>When you interrupt bing via Ctrl-C it should ecompute
everything using the latest values available and print it
before exiting.
</ul>
<h3>2.2. Roadmap</h3>
<p>Here is the plan as to what I will try to dewvelop next. Of
course if someone contributes code on some other aspect it will
be integrated even if I planned to work on it much later.
<ul>
<li>Remove stuff from the main function. Some of it really does
not belong there and it would make it simpler to write
graphical versions of bing if they were separate. But this
has to be done in a way that makes sense, if the methods are
too much tied to this particular implementation of bing it's
not so interesting.
<li>Rewrite the backend. I call the backend all the code that
sends the probes, receives the answers, measures the rtt and
interprets the probe answers. Currently it only supports ICMP
echo request/reply and I want it to support other methods as
well including 100% UDP based ones. So the goal is to provide
a flexible backend API where I can just plug a new module and
do the probes using the UDP echo port for instance.
<li>Once this API is written I'll try to implement three modules.
The ICMP echo request/reply will be the first one, the one I
use to develop the new architecture. Then there will be a UDP/ICMP
invalid port module. This module will be used in further
developments to measure asymetric links. The last module will be a
UDP echo port module. The idea is to be able to go through
firewalls that block ICMP, although they are likely to also block
the echo port, and also to see if methods involving a regular server,
rather than the kernel, can work. As I do this I'll try to solve
the backend bugs as far as unexpected packets go.
<li>Then I'll try to implement the asymetric links handling. First
using only the host level regressions and then trying to provide
link level error estimates and probe scheduling that fits asymetric
links.
</ul>
<h3>2.3. Other features</h3>
<ul>
<li>When trying to answer questions like 'which measure is wrong' or 'why can't
I get reliable measures for this link' what would really be needed is a way to
dump all the measures done by bing and graph them. I would be interested in
seing the graph of the rtt differences between two hosts, I did it for a few
cases on my HP28 and this told me that doing a linear regression on the rtt
difference is definitely useful. Another graph that may be interesting is a
graph of al the rtts collected for a given host and size. So the idea would be
to modify bing so that it can dump all its measures in some format (XML based?).
Then what we need is a number of scripts that transform these logs into usefull
statistics and graphics using something like gnuplot.
<li>If the UDP echo port module works well then it would be interesting to
develop a module based on one of the UDP time services since it would allow us
to have both fixed and variable return size UDP modules.
<li>Source routing (loose or not) is not supported and might be useful to measure
links that are not 'in a direct line of sight' from your computer.
<li>Introduce support for asynchronous probing, i.e. bing sends probes at regular
intervals, e.g. 0.1 seconds or as fast as answers arrive, and when an answer
arrives deduce the rtt and updates the appropriate host/size record. This might
speed up the measurements for far away links with high rtts. On the other hand
the risks of probes being delayed or bing retrieving the probe too late may be
higher too.
<li>Making a version for cursor addressable displays (a la top) or GUIs (Gnome
and/or Windows) would be nice. This is in particular true for packet sending
strategies that don't do things linearly or if packet sending is node asynchronously.
But I don't expect to undertake one of these projects since I don't know curses,
the mfc or gtk.
<li>Many other options of bing 1.0 are missing. Note that all should not be
reintroduced, for instance route recording and ICMP flooding do not belong
to bing.
</ul>
<h2>4. Assumptions and limitations</h2>
<p>Bing makes a number of assumptions to compute a link's raw bandwidth. If any of these is broken then bing will return erroneous results. How much the results will be affected ? It depends on the link, the assumption that has been broken,...
<ul>
<li>Packets take the same route on their way up and on their way down.
<br>This is more or less important, it depends on the probe method. If you use a method that allows you to measure the bandwidth of asymetric links the up bandwidth computed by bing should be correct. This is because these methods elicit a fixed size return packet so that the actual speed of the down link does not affect the measurment of the up link.
<br>But you will not be able to measure the bandwidth of the down link. First because the packets do not go through this link. But even so the down results are very likely not to be meaningful at all. That's because there will probably not be the same number of hosts on the way down as on the way up. So eaThis means that you will not be ab
<li>Packets always take the same route (coupled modems,)
<li>no bridge/repeater/switches (ethernet repeater)
<li>The link bandwidth does not vary with time.
<br>This may seem obvious but it's not always the case. One counter example is modern modems. Any V34+ or faster modem will monitor the line clarity and adapt the transmission speed accordingly. So if the line quality degrades suddenly the bing results will no longer reflect the line speed and some results may be corrupted. If your link's bandwidth keeps changing the only thing that makes sense is a mesurement of its bandwidth at a given time. But bing needs some time to compute the bandwidth so you'll have to know whether the bandwidth will have significantly changed during the time bing takes to mesure it. Also bing will not give you an average raw bandwidth. That's because bing uses minimum rtt and not average rtt. Average rtt is not usable because it varies too much based on many random factors. Only minimum rtt is significant. But if the link bandwidth slows down, bing will never notice, it will only ignore the new longer rtts.
<br>If this happens during the first probe of a host, this host will get a bad correlation and the link that leads to it will appear to be slower than it really is. The case where the line suddenly gets better is not as bad. The rtt should get smaller and bing will reflect that.
<li>it takes the same time to route a packet as to answer a packet (not nt4)
<li>this time is constant (does not vary with size) or negligible
<li>time does not go slower or faster (no NTP, don't change time while bing works)
</ul>
<h2>5. Other tools</h2>
<ul>
<li>bing 1.1
<li>echoping
<li>pathchar
</ul>
<p> where to find them, how do they compare
<h2>5. How does it work</h2>
<h3>5.1. Performing a traceroute</h3>
<h3>5.2. Mesuring a regular link</h3>
<h3>5.3. Mesuring an asymetric link</h3>
<h3>5.4. Packet sending strategies</h3>
<ul>
<li>sequential
<li>based on correlation
<li>based on linear regression precision and its impact on bandwidth estimation
<li>based on worst rtt error accros hosts
<li>based on worst rtt error per host
</ul>
<h3>5.5. Windows limitations</h3>
<h3>5.6. Calculating bandwidth</h3>
<h3>5.7. Delays</h3>
Ci=1-(1-p0)*(1-p1)*(1-p2)...
<h3>5.8. imprecision et effet sur la bande passante</h3>
<p>Consider a string of hosts and links h<sub>0</sub> - l<sub>1</sub> - h<sub>2</sub> - l<sub>2</sub> - ... - l<sub>n</sub> - h<sub>n</sub>
<p>If the probablility that each host h<sub>i</sub> delays the transmission of a packet,
what is the probability that the packet be delayed by the time in its round-trip ?
<p>The probability for the packet not to be delayed by host
h<sub>i</sub> is 1-p<sub>i</sub>, and the only way for the packet not to be delayed at
all is that it is not delayed by any host. That is this probability is
(1-p<sub>0</sub>)*(1-p<sub>1</sub>)*...*(1-p<sub>n</sub>). In all other cases the
packet is delayed. Thus the probability C<sub>n</sub> that the packet is not delayed
at all is:
<dd>C<sub>n</sub>=1-(1-p<sub>0</sub>)*(1-p<sub>1</sub>)*...*(1-p<sub>n</sub>)
<p>If that probability is the same for all intermediate hosts (or can be bounded between
a min and a max) we get:
<dd>1-p<sub>min</sub><sup>n</sup> < C<sub>n</sub> < 1-p<sub>max</sub><sup>n</sup>
<p>What this tells us is that the probability that the packet is not delayed decreases
exponentially with the number of hosts. But note that this does not necessarily mean that
we cannot measure far away links. You will probably be able to measure a modem link which
is many hops away because the delays will probably be small compared to the rtt difference
at the two ends of this modem link. But it does put a limit on our chances to get a good
measurement of relatively fast and far away links.
<h3>5.9. routers, hubs, switches,..</h3>
<h3>5.10. things that don't work</h3>
<p>aggregated pipes: shotgun modems ?, modem aggregation, aggregated fast-ethernet to a switch
<p>determining half-duplex/full duplex
<p>fixed bandwidth may be wrong for modems
<p>fixed latency may be wrong for satellite links
<h2>6. The maths and physics being Bing</h2>
<p>This section describes how Bing computes the link characteristics such as the bandwidth. It first describes how we modelize the network <i>(the phiysics)</i>, then the algorithms <i>(the maths)</i> and then gives a word of caution about how to interpret the results and why the assumptions we have made may be wrong.
<h3>6.1. Network link modelisation</h3>
<p>Bing attempts to determine the characterics of the the links that connect TCP/IP hosts. That these links be point to point links or buses does not matter. What is important is that each <b>network link forms a direct connection</b> between the two (or more) hosts, i.e. the TCP/IP packets are not stored and forwarded at any point between the two hosts.
<p>So for instance the in the figure below A-B is a network link but not A-C. This is because a hub does not store and forward IP packets, it starts retransmitting IP packets from the segment 1 to the segment 2 as soon as the first byte is received <i>(in fact it operates at the physical level and does not even know what a byte is)</i>. So between A and B a TCP/IP packet is never stored and then forwarded. In contrast the router has to first receive the full TCP/IP packet from segment 2 before it can before it can retransmit it on the segment 3. So by the definition above A-C and B-C are not network links.
<pre>
Ethernet Ethernet Ethernet
Segment 1 Segment 2 Segment 3
A ----------- Hub -----+----- Router ----------- C
|
B
</pre>
<p>When we attempt to characterize a network link we will be at one end of it. We will then say that packets leaving our computer are going "up" while packets comming to our computer are going "down" <i>(which keeps with the tradition of uploads and downloads)</i>. Each network link can then be split in two: an "uplink" and a "downlink".
<p>Of course in some cases the uplink and downlink are in fact exactly the same link, this is the case in particular of ethernet over a coaxial cable. In other cases they may have the same characteristics, this is the case for instance of ethernet over an RJ45 conenction. But there are also a number of situations where the uplink and the downlink have different characteristics, examples are given in a later section.
<p>Then we characterize each half of the link by the following properties:
<ul>
<li><b>b</b>: the link bandwidth, i.e. the number of bytes that can be transmitted per second. This bandwidth is assumed to be constant in time <i>(at least while we are making our measurement)</i> and independent from the amount of data sent, from the nature of the data sent and from the number of packets sent.
<li><b>l</b>: the link latency, i.e. a delay that is incurred every time that data is sent from one end of the link to the other. We assume that this delay is constant in time <i>(again, at least while we are making our measures)</i> and independent from the amount of data sent.
</ul>
<p>It follows that the time <code>t</code> it takes to send s bytes <i>(in s we include all the protocal overhead)</i> from one host on the link to the other is:
<dd>(1) <code>t = s / b + l</code>
<p>Determining the characteristics of such a network link is then equivalent to determining the values of <code>b</code> and <code>l</code>.
<p>(!!)From there is is trivial to generalize the foNow generalizing the formula above from just one network link to a chain of n+1 hosts <i>(h<sub>0</sub>..h<sub>n</sub>)</i> connected via <code>n</code> network linksthe round-trip-time will be of the form:
<dd> (2) <code>rtt = (1/b<sub>u,1</sub>+1/b<sub>u,2</sub>+...+1/b<sub>u,n</sub>+1/b<sub>d,n</sub>+1/b<sub>d,n-1</sub>+...+1/b<sub>d,1</sub>)*s+l<sub>u,1</sub>+l<sub>u,2</sub>+...+l<sub>u,n</sub>+l<sub>d,n</sub>+l<sub>d,n-1</sub>+...+l<sub>d,1</sub></code>
<p>where b<sub>u,i</sub> and l<sub>u,i</sub> are respectively the bandwidth and the latency of the uplink connecting the host i-1 to the host i and b<sub>d,i</sub> and l<sub>d,i</sub> are respectively the bandwidth and the latency of the downlink connecting the host i to the host i-1.
<p>Finally we can derive from expression (2) that the round-trip-time is an affine function of the packet size, that is, it is of the form:
<dd>(3) <code>rtt=a*s+b</code>
<p>where <code>a</code> and <code>b</code> are constants determined by the bandwidth and latency of the intervening network links.
<h3>6.2. Intrisic limits and validity of this modelisation</h3>
<p>Before we go on to see how we are going to measure the network link's bandwidth let's review the assumptions made by the network link modelisation.
<p>We assume the bandwidth is constant in time. This is not always the case. For instance modems using protocols like V34 or V90 constantly monitor the line quality and adjust their bit rate accordingly. Comes a storm and the bandwidth falls ! The same may happen if your neighbor picks up the phone and the cross-over phenomenon starts perturbing your communication <i>(when two cables are parallel and close to each over for some distance part of the signal on one cable can "cross-over" and appear as a weak perturbation on the over cable)</i>. This is the only case I know where the bandwidth is not necessarily constant in time. Even then the bandwidth is not very likely to change during the typical duration of a bing measurement.
<p>We also assume that the bandwidth is independent from the nature of the data sent. Again, modems usually compress the data before sending it which then violates this assumption. The workaround is to send random data which is then incompressible. But this only a partial solution because we can only randomize the packet payload, not its TCP/IP header. So for small packets, where the ratio header size / payload size is high, the bandwidth will be slightly different than for big packets.
<p>We assume that the bandwidth does not depend on the amount of packets sent. This is incorrect if the network link is an aggregate of multiple links. Take for instance a server with four fast ethernet network cards will all the same IP address. Such a server is usually connected to a fast ethernet switch which does load balancing of the traffic on the four server's network cards. In such a situation packets individually "travel" at 100Mbps but we can have four of them travelling at once which makes the aggregate bandwidth 400Mbps. Since the server has a single IP address we see this type of link as a single network link with a 400Mbps bandwidth.
<br>As another example consider the case of a linux box configured as a gateway to the internet by aggregating the bandwidth of two or more modems. In this case too the resulting aggregate link is capable of sending more than one packet simultaneously which results in an aggregate bandwidth which is higher than the rate at which each packet is being transmitted. And in this case all links may not have the same speed. One may be a 19.2kpbs modem while the other may be a 56kbps modem resulting, in addition, in changes in the rate at which a packet is being sent depending on which modem it goes through. (!!) do the boxes have the same IP address on both modems in such a case ?
<br>Finally we can contrast the cases above with that of "shotgun" modems.As far as I understand, these modems aggregate two phone lines together but do so at the bit level which means that a TCP/IP packet is being sent on both lines simultaneously. So in this case the assumption that the bandwidth does not depend on the number of packets is valid.
<p>The assumption that the latency does not depend on time must be true in all but the most extreme cases. A non negligible component of the latency is the length of the network link. The data travels approximately at the speed of light so the longer the distance the higher the latency. One sample case where it may change over time is if the network link actually goes through a low orbit satellite. In such a case the distance sender-satellite-receiver may change a lot as the satellite orbits around the earth. But such network links are currently very rare.
<h3>6.3. Measurement methodology</h3>
<p>First we must notice that we cannot measure the round-trip-time as defined above and even less the time it takes for a network packet to go from one host to another. In both cases we would need hardware network probe.
<p>What we can do though is measure the time it elapsed between when our software called the method to send the packet and when our software received the packet on the other side. But even this is not practical since we would have to install our software on all the hosts.
<p>So instead we measure the rtt.
<h3>6.4. Measurement pitfalls</h3>
<h4>6.4.1. Routing problems</h4>
<h4>6.4.2. latency/delays</h4>
<h4>6.4.3. Buses, bridges and switches</h4>
<p>It is quite likely that there will be devices and intermediaries between two hosts.
Some are internal to the computer and others are network devices which are usually used
to extend the reach of a network. All these intermediaries can be split into three
categories.
<h5>Immediate retransmission, same bandwidth</h5>
<p>This kind of device starts retransmitting a network frame as soon as a fixed amount of
data has been received. One such kind of device are devices that don't even know what a
frame is. Modems are one such kind of device. They only know about bytes and start
retransmitting those bytes as soon as they have filled they transmit buffer. Another kind
of device that follows this kind of rule is the network hub like ethernet repeaters. As
soon as they have received the start of an ethernet frame they start retransmitting it on
the other ports. Since this works both ways if a collision occurs the frame will be
dropped the and the initiator will retransmit.
<p>How does this kind of device affect the bing measures?
<p>Let's call d the number of bytes the device must receive before it starts
retransmitting the frame on the other side of the link. The device will have to wait until
it has received d bytes before it can start retransmitting data. Then the time it takes to
retransmit the data is overlapped with the time it takes to receive it. So the
one-way trip time is:
<dd>ott=s/b+d/b
<p>So such a device is not going to affect our measure of the bandwidth. The only thing we
will notice is a slightly increased link latency.
<h5>Immediate retransmission, different bandwidth</h5>
<p>This kind of device bridges two links of different bandwidths. We further assume that
it is bridging a slow link to a faster link. The reverse case is in fact equivalent to the
previous type of device. What this device does is that it first waits until it has
bufferized enough data to start transmitting to the faster link without running out.
Should the frame on the slow link turnout to be invalid, due to a collision or a link
failure, it would reproduce a similar condition on the other link so that the data is
ignored anyway.
<p>How does this kind of device affect the bing measures?
<p>Let's call respectively b<sub>s</sub> and b<sub>f</sub> the bandwidth of the slow and
fast links. The device can start retransmitting data only once the time it takes to
transmit all the data on the fast link plus some buffer delay of d bytes is the same as
the time it takes to receive the remainder of the data from the slow link.
<p>So the total transmission time will be the same as the time it takes to receive all of
the data at the slow link speed plus the time to build the buffer and the time to
retransmit it on the fast link.
<dd>ott=s/b<sub>s</sub>+d/b<sub>f</sub>
<p>So we essentially have the same result as in the previous case except that the latency
is slightly lower.
<h5>Store and forward</h5>
<p>This kind of device, by far the most common, waits until it has received all the data
from the first link and then retransmits it on the other link. This is what any router and
probably most switches do. But this is also how your network card works. It waits until it
has received all the data via the PCI/ISA bus and then retransmits it on the second link,
the ethernet or fast ethernet link.
<p>How does this kind of device affect the bing measures?
<p>Let's call b<sub>1</sub> and b<sub>2</sub> the bandwidth of the two links. The device
will also introduce some delay but this time it is better described in terms of time
rather than in terms of bytes, so let's call it l. There is absolutely no overlap between
the receive phase and the transmit phase so the one-way trip time is:
<dd>ott=s/b<sub>1</sub>+l+s/b<sub>2</sub>
<p>This means that the bandwidth measured by bing is going to be:
<dd>b=b<sub>1</sub>*b<sub>2</sub>/(b<sub>1</sub>+b<sub>2</sub>)
<p>In other words, bing is going to measure the geometric mean of the links bandwidths.
<p>Some examples:
<ul>
<li>Take an old Ethernet card, an 8bit ISA card in a 8MHz ISA bus (PC-AT
standard). These cards normally operate in half duplex mode (it's usually
even worse) but what is more important to us is that, like their more modern
couterparts, you first have to transfer the packet to the card buffer before
it is sent on the ethernet. So such cards operate in "Store and Forward" mode.
So applying the rules described above the badwidth that will be measured by
bing will be, at most, the geometric mean of the bandwidth of the ISA bus and
the ethernet. Since the ISA bus described above has a maximum bandwidth of 72Mbps
this gives us a maximum of about 8.8MBps. Note that this is a theoretical
maximum. If the card imposes some overhead for transfering data to its buffers
you will not take benefit of the the full bandwidth of the ISA bus and the
resulting bing measurement will be even lower.
<li>Let's do the same exercise in a more modern setting. Let's take a 32bits 66MHz
PCI bus and a fast ehternet card. The PCI bus bandwidth is 2014Mbps and the fast
ehternet bandwidth is 100Mbps so the maximum bing will ever see is about 95Mbps.
Now replacing if you replace the fast ethernet card by a gigabit ethernet card it
gets even worse: bing will only measure 668Mbps.
<li>Let's consider a fast ethernet network composed of PCs with 32bits 66MHz PCI
network cards. Let's further assume that each PC is connected to an ethernet
switch operating under the "Store and forward" principle. Will be the result
returned by bing? Bing will think there is just one network link since it has only
two IP addresses: that of the localhst and that of the other PC. But in fact the
packet goes through 4 links: a PCI bus, a fast ethernet segment, another fast
ethernet segment and another PCI bus. So the maximum bandwidth returned by bing
will be the geometric mean of all these which gives 47Mbps.
</ul>
<p>Are these results significant?
<p>It depends on the combined ability of the hardware and your application to overlap
data transfers.<br>
In the first example it is very unlikely that the network card will let you tranfer a
packet to its buffer while it is sending the content of another buffer to the network.
This means the hardware prevents you from overlapping transfers from memory to the card
and from the card to the network. This means you will not be able to send data faster than
what big tells you.<br>
In the example involving the network switch you can in fact transfer data on the first
network segment while the previous packet is being transfered on the second segment. But
this depends on your application. An RPC based client/server application that has to wait
until it gets the result of an RPC before it can do more work and issue the next one will
be limited by the presence of the switch because the switch doubles the latency. Not only
is the 'b' factor of the linear regression probably the double of what it would be with a
direct connection but the bandwidth as measured by bing too is just half of what it would
be without the switch. So the performance of RPC based applications should closely match
the results of bing.<br>
On the other hand the performance of applications like ftp will not be accurately predicted
by bing's results because they can overlap multiple data transfers. Modern fast ethernet
PCI cards are very likely able to transfer data to or from memory while sending or receiving
data to or from the network. So in the switch example above we could have up to four
packets in flight at any time. In such cases the bandwidth is limited by the slowest link,
the fast ethernet link, ad the ability of the networking protocol implementation to
efficiently use it (and that is not a given).
<h2>7. The architecture</h2>
<h2>9. References</h2>
<p>Other bandwidth measuring related links:
<ul>
<li>Bing 1.0 of course. It allows you to measure the bandwidth of a specific network link.
<br><a href="http://web.cnam.fr/reseau/bing.html">http://web.cnam.fr/reseau/bing.html</a>
<br><a href="ftp://ftp.lip6.fr/pub/networking/bing-1.0.4.tar.gz">ftp://ftp.lip6.fr/pub/networking/bing-1.0.4.tar.gz</a>
<br><a href="http://www.multimania.com/fgouget/bing/">http://www.multimania.com/fgouget/bing/</a>
<li>Van Jacobson has done some work on network bandwidth measurements. There is a nice paper
on the subject that he has given at the MSRI. The files claim that the source will be
available soon, as soon as the code has been cleaned up, but actually I did not see
any status chane in the last two years.
<br>The MSRI paper in <a href="ftp://ftp.ee.lbl.gov/pathchar/msri-talk.ps.gz">Postscript</a> and <a href="ftp://ftp.ee.lbl.gov/pathchar/msri-talk.pdf">PDF</a>
<br><a href="ftp://ftp.ee.lbl.gov/pathchar/">ftp://ftp.ee.lbl.gov/pathchar/</a>: the binaries
<br><a href="http://www.caida.org/Pathchar/pathcharnotes.html">http://www.caida.org/Pathchar/pathcharnotes.html</a>: Usage notes (the binary packages don't contain a man page)
<li>There is is a nice paper by Kevin Lai and Mary Baker describing a smart technique for efficiently measuring the bottleneck bandwidth of a complete network path. They call their technique "Receiver Only Packet Pair".
<a href="http://mosquitonet.stanford.edu/~laik/projects/nettimer/publications/infocom1999/html/">http://mosquitonet.stanford.edu/~laik/projects/nettimer/publications/infocom1999/html/</a>
<li>Nettimer is a project to do passive end-to-end network performance measurement. Passive means it uses existing traffic to take measurements and end-to-end that it does not need special information from the network. It measures the bottleneck bandwidth, the latency and the available bandwidth. This tool is at least partly based on the "Packet Pair" technique described above.
<br><a href="http://mosquitonet.stanford.edu/~laik/projects/nettimer/">http://mosquitonet.stanford.edu/~laik/projects/nettimer/</a>
<li>Bprobe and cprobe use packet dispersion techniques, similar to the Packet Pair technique, to measure network bandwidth. bprobe measures the bottleneck badwidth while cprobe measures the available bandwidth by sending a short burst of packets.
<br><a href="http://www.cs.bu.edu/students/grads/carter/tools/Tools.html">http://www.cs.bu.edu/students/grads/carter/tools/Tools.html</a>
</ul>
<p>Ping tools:
<ul>
<li>ping: There are tons of ping tools available. I will only cite one, the one I wrote as an excercise to learn how to use the Windows icmp dll. Note that it's not the most sophisticated nor the most featureful ping around (although it does have one or to features that the standard Windows ping does not have).
<br><a href="http://www.multimania.com/fgouget/bing/">http://www.multimania.com/fgouget/bing/</a>
<li>fping: fping allows you to efficiently ping many hosts typically to determine whether they are up or not. Using fping is more efficient than using a script which would ping the hosts in a round-robin fashion because the script would have to wait for one RTT for each host. For 1000 hosts and more this can take a while. Also fping is made to be used in scripts and its output is easy to parse which may be a reason to use it even for only a few hosts.
<br><a href="http://www.stanford.edu/~schemers/docs/fping/fping.html">http://www.stanford.edu/~schemers/docs/fping/fping.html</a>
<br><a href="ftp://ftp.lip6.fr/pub/networking/fping-2.0.tar.gz">ftp://ftp.lip6.fr/pub/networking/fping-2.0.tar.gz</a>
<li>echoping: This tool by Stephane Bortzmeyer is designed to approximately evaluate the performance of a remote host by sending it TCP "echo" (or other protocol) packets. Unlike the ICMP echo packets, the packets sent by echoping actually require that a server process answer so that one can more easily detect if the remote host is completely overloaded or partly out of order.
<br><a href="http://www.ensta.fr/internet/unix/sys_admin/echoping.html">http://www.ensta.fr/internet/unix/sys_admin/echoping.html</a>
<br><a href="ftp://ftp.internatif.org/pub/unix/echoping/echoping-2.2.0.tar.gz">ftp://ftp.internatif.org/pub/unix/echoping/echoping-2.2.0.tar.gz</a>
<li>traceroute: not quite a ping tool but I did not want to create a new section. You will find the sources at the URL indicated below.
<br><a href="ftp://ee.lbl.gov/traceroute-1.4a5.tar.Z">ftp://ee.lbl.gov/traceroute-1.4a5.tar.Z</a>
</ul>
<p>You can find a more complete and very good taxonomy of network measurement tools at the following URL: <a href="http://www.caida.org/Tools/taxonomy.html">http://www.caida.org/Tools/taxonomy.html</a>.
<p>Libpcap is a library which provides a system-independent interface for packet capture.
<br><a href="ftp://ee.lbl.gov/libpcap-0.4.tar.Z">ftp://ee.lbl.gov/libpcap-0.4.tar.Z</a>
Found this in the Wine list (by gerard patel <g.patel@wanadoo.fr>):
#ifdef __i386__
typedef unsigned long long u64;
inline u64
gettick() {
u64 ticks;
asm volatile ("rdtsc" : "=A"(ticks));
return ticks;
}
u64 u1, u2;
#endif
Might be interesting if I could change it to milliseconds. Does this require to be root ?
</body>
</html>
|
