Thread Links Date Links
Thread Prev Thread Next Thread Index Date Prev Date Next Date Index

Re: [RE] On worst-case latency for Ethernet networks and alternat ive shaping concept

Hi Kelvin,

Indeed, I recognize all issues you mentioned with occupation map. It is a raw idea and needs work to hash out details and realize all limitations. My general feeling, not supported by any research so far, is that if we limit number of latency-bound streams to a manageable number it could work.

I would be very interested to peek into ATM designs - this is a new area for me. I would hate spending my time on inventing yet another bicycle :)

Can you recommend some good references to read on ATM?

Thanks in advance,

"Gross, Kevin" <kevin.gross@CIRRUS.COM>

09/27/2005 01:21 PM
Please respond to
"Gross, Kevin" <kevin.gross@CIRRUS.COM>

Re: [RE] On worst-case latency for Ethernet networks and alternat ive shaping concept

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.

From: Max Azarov [mailto:Max.Azarov@SMSC.COM]
Monday, September 26, 2005 9:27 AM
[RE] On worst-case latency for Ethernet networks and alternative shaping concept



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.

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.


1) No changes are need in traffic routing algorithms. All burden of arbitration is distributed to end-points.

2) Deterministic latency guarantees are possible.


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