Max,
Thanks for your contributions. Your proof
on worst case latency appears to be sound. Subtracting best case from worst
case latency gives us a measure of latency variation (dv). My algebraic derivation
of that is dv=(n-1)Nt. Latency variation is an important metric that tells us
how much buffering is required at receivers.
You occupation map is an interesting idea.
I’m sure we all recognize that the synchronization accuracy requirement dictates
special hardware to time transmissions. One con with this scheme that you’ve
not mentioned is that the dynamic nature of the occupation map problem needs to
be considered. It’s fine to examine the map and time your transmissions
appropriately. Once begun, your own transmissions will alter the occupation map
in ways that may be difficult to predict. This effect has the potential to turn
this into a recursive problem with potential stability issues. Furthermore you’ll
probably need to reevaluate your transmission timing whenever the occupation
map changes – i.e. anyone else stops or starts transmitting. In the time
between the changes and your response to them, network performance will suffer
and data may be lost.
If we want to continue down this road on
pacing and traffic shaping, I suggest the group spend some time reviewing the
history of ATM development and deployment. We’re trying to solve the same
problems here in the same general way.
Kevin
From: Max Azarov
[mailto:Max.Azarov@SMSC.COM]
Sent: Monday, September 26, 2005
9:27 AM
To:
STDS-802-3-RE@listserv.ieee.org
Subject: [RE] On worst-case
latency for Ethernet networks and alternative shaping concept
Gents,
on
our previous call somebody (I believe it was Geoff) have expressed a desire to
have an exact worst-case latency formula. Since I couldn't find anything
readily available on the topic, I've took up on an exercise in algebra and
formal logic to come up with the formula. Please see the link to the document
with formula and the proof.
http://public.wpanther.fast-mail.org/WorstCaseLatency.pdf
I
also sensed the general agreement that it would be beneficial to come up
with alternatives to "shaping" as it is proposed at the moment.
While
studying the subject it would appear that such solution is possible to get. In
particular I would suggest a synchronized network access, which can also be
called "orchestra"-concept.
In
essence idea is that all nodes use precisely synchronized wall clock to
orchestrate a predictable network access, thus making is possible to reduce
latencies to the levels well below suggested in the attached paper. Very
similar to orchestra which has to tune for the same frequency and tempo in
order to play a piece, end-nodes and routers "tune" onto the same
time/schedule before than can play a melody... well, provide predictable
propagation delay in our case.
When
reserving a path end node would look at the topology and "occupation
map" along the communication route to determine latency it can be
expecting. This "occupation map" would essentially consist of
time-slots and number of streams passing through this output port at this slot.
Each router/output port has such map and client can access it. Using this
information client can determine its own transmission schedule producing the
least latency (most empty slots) and decide whether this is satisfactory for
its purposes.
Essentially
this is a fusion between a conventional isochronous access arbitration and
conventional best-effort absence of arbitration with compromises made to
achieve a simple router design. Obviously number of details need to be worked
out, such as interaction between streams occupying the same time slot on given
the switch/output port and between neighboring slots.
Pros:
1)
No changes are need in traffic routing algorithms. All burden of arbitration is
distributed to end-points.
2)
Deterministic latency guarantees are possible.
Cons:
1)
Limited scalability. Here we need to acknowledge that scalability for ResE is
not a prime target. We have to sacrifice something to get a cheap router.
2)
Relatively precise time synchronization (probably within 10s of microseconds) has
to occur before latency-bound traffic is possible.
This is another
compromise that has to be made. I think that it may be acceptable to expect
real-time traffic service hick-ups when backbone configuration changes (i.e.
clock-master is disconnected). Even local buses such as IEE1394 require bus
reset under certain topology changes.
3)
Assumes that routers have high degree of determinism in routing traffic (SW
routers will not do).
In
addition, we could use lower 802.1 priority for traffic which is not overly
sensitive to the latency, i.e. traffic which is OK with worst-case figures. I'd
imagine that stored video playback and even life TV would be good candidates.
Feedback
on both paper and "orchestra" concept would be greatly appreciated!
Max
Azarov
SMSC