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




Geoff,

in fact I used your results to validate my formula. Proof should help to put to rest questions about how "worst" is the delay your formula expresses. As appears, it is "worst" indeed!

Max.



Geoffrey Garner <gmgarner@COMCAST.NET>

09/27/2005 06:24 PM
Please respond to
gmgarner@COMCAST.NET

To
STDS-802-3-RE@LISTSERV.IEEE.ORG
cc
Subject
[RE] On worst-case latency for Ethernet networks and alternat ive shaping concept





Max,
 
Thank you for your paper.  You have supplied a rigorous proof of the "rules of thumb" for delay and delay variation in the presentation:
 
http://www.ieee802.org/3/re_study/material/garner-050822-sim-multi-hop.pdf
 
which I presented in one of the calls in August.  The only difference is that I have an additional transmission delay (your quantity tau) added, as I have a final link after the last switch to the end device (it was assumed there was no contention for this link).
 
Best regards,
 
Geoff
-----------------------------------------
Geoffrey M. Garner
Samsung (Consultant)
 
----- Original Message -----
From: Gross, Kevin
To: STDS-802-3-RE@listserv.ieee.org
Sent: Tuesday, September 27, 2005 1:21 PM
Subject: Re: [RE] On worst-case latency for Ethernet networks and alternat ive shaping concept

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 wi! th 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 pat h 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 synchr! onization (probably within 10s of microseconds) has to occur before la tency-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 an! d even life TV would be good candidates.


Feedback on both paper and "orchestra" concept would be greatly appreciated!

Max Azarov
SMSC