Table of Contents
Chapter
1 – Introduction................................................................ 1
1.1. Background.......................................................................................................... 2
1.2. What is a protocol?............................................................................................... 5
1.2.1. Communication as state concurrence.......................................................... 7
1.3. The need for a new model..................................................................................... 7
1.4. What has changed?............................................................................................... 9
1.4.1. Change in the use of memory..................................................................... 14
1.5. Model goals.......................................................................................................... 15
1.6. Preview................................................................................................................. 15
Chapter 2 – The Mirage model........................................................ 17
2.1. Assumptions......................................................................................................... 18
2.1.1. Initial description of channel utilization...................................................... 18
2.1.1.1. Phases........................................................................................... 19
2.1.1.2. Channel utilization: linear case...................................................... 20
2.1.1.3. Channel utilization: sender-based anticipation............................... 21
2.1.1.3.1. An example for illustration- the turtle........................... 21
2.1.1.3.2. Branching streams utilization....................................... 22
2.1.2. Conclusions of the branching model.......................................................... 27
2.1.3. Some reality checks.................................................................................... 27
2.1.4. Some common sense.................................................................................. 29
2.2. The Mirage model................................................................................................. 30
2.2.1. More definitions......................................................................................... 31
2.2.2. A description of the model......................................................................... 32
2.2.2.1. Time.............................................................................................. 34
2.2.2.2. Receive......................................................................................... 35
2.2.2.3. Transmit........................................................................................ 35
2.2.3. Implications of the model........................................................................... 36
2.2.3.1. Lag and stability............................................................................ 36
2.2.3.2. Communicability........................................................................... 37
2.2.3.3. Guarded messages........................................................................ 39
2.2.3.4. Isopotent sets................................................................................ 40
2.3. Discussion............................................................................................................ 41
2.3.1. A channel with imprecision........................................................................ 41
2.3.2. Looking into the structure of the stream..................................................... 42
2.3.3. Implementations......................................................................................... 43
2.3.3.1. Projections.................................................................................... 43
2.3.3.2. Granularity.................................................................................... 44
2.4. Insights................................................................................................................. 45
2.4.1. Kinds of information.................................................................................. 45
2.4.2. Error and latency as conjugates.................................................................. 45
2.4.3. Entropy...................................................................................................... 46
2.4.4. Constraints................................................................................................. 46
2.4.5. Contrasts & comparisons........................................................................... 46
Chapter 3 – Prior Work.................................................................. 48
3.1. Prior models of communication............................................................................ 49
3.1.1. The models................................................................................................. 49
3.1.1.1. ShannonÕs model of communication............................................. 50
3.1.1.2. Communicating finite state machines............................................ 51
3.1.1.3. Petri Nets...................................................................................... 51
3.1.1.4. Estelle / LOTOS........................................................................... 51
3.1.2. Partitioning the state space......................................................................... 51
3.1.2.1. Partitions....................................................................................... 52
3.1.2.2. Factoring....................................................................................... 52
3.1.2.3. Projections / imaging.................................................................... 53
3.1.2.4. Powerdomains.............................................................................. 53
3.2. Protocol optimizations.......................................................................................... 53
3.2.1. Universal Receiver Protocol....................................................................... 54
3.2.2. VMTP........................................................................................................ 55
3.2.3. XTP........................................................................................................... 55
3.2.4. TCP............................................................................................................ 56
3.2.5. NetBlt......................................................................................................... 56
3.2.6. ÔCross Product ProtocolsÕ.......................................................................... 57
3.2.7. Delta-t........................................................................................................ 58
3.2.8. Virtual Clock.............................................................................................. 58
3.2.9. SNR (leaky bucket).................................................................................... 59
3.2.10. TP++........................................................................................................ 60
3.3. Communicability................................................................................................... 61
3.3.1. Cybernetics and control theory................................................................... 61
3.3.2. Time........................................................................................................... 62
3.3.2.1. Real time systems......................................................................... 63
3.3.2.2. Aging variables............................................................................. 63
3.3.2.3. Timers........................................................................................... 63
3.3.3. Constraints................................................................................................. 64
3.4. Anticipation.......................................................................................................... 64
3.4.1. Operating systems...................................................................................... 65
3.4.1.1. Concurrent execution.................................................................... 65
3.4.1.2. Time Warp.................................................................................... 66
3.4.2. Congestion control..................................................................................... 66
3.4.2.1. Anticipatory congestion control.................................................... 66
3.4.2.2. Timer-based congestion control.................................................... 67
3.4.2.3. Feedback congestion control......................................................... 67
3.4.2.4. Combination control..................................................................... 68
3.4.3. Other forms of anticipation........................................................................ 68
3.4.3.1. Client / server extensions.............................................................. 68
3.4.3.2. Recent protocol discussions.......................................................... 69
3.5. Physics analogs.................................................................................................... 70
3.5.1. Truth Maintenance Systems....................................................................... 70
3.5.2. Physics in protocols................................................................................... 70
Chapter 4 – A Mirage of NTP......................................................... 72
4.1. An overview of NTP............................................................................................ 73
4.1.1. How NTP reads a clock............................................................................. 75
4.1.2. NTP background........................................................................................ 77
4.2. Casting NTP into Mirage...................................................................................... 78
4.3. Resolution of domain differences......................................................................... 79
4.3.1. Analysis of delay and offset measurements............................................... 82
4.4. Description of NTP in Mirage.............................................................................. 88
4.4.1. State space.................................................................................................. 89
4.4.2. Transformations......................................................................................... 90
4.4.2.1. Time.............................................................................................. 90
4.4.2.2. Send.............................................................................................. 92
4.4.2.3. Receive......................................................................................... 93
4.4.3. Partitioning of the state space..................................................................... 96
4.4.4. NTP degenerates to a clock pulse............................................................... 97
4.4.5. Constraints................................................................................................. 98
4.5. Observations......................................................................................................... 98
4.5.1. Gains.......................................................................................................... 99
4.5.2. Prior work.................................................................................................. 100
4.5.3. Conclusions............................................................................................... 101
Chapter 5 – m-Net........................................................................... 102
5.1. Preface to Chapters 5 and 6.................................................................................. 102
5.2. Introduction.......................................................................................................... 104
5.2.1. The Domain - the processor / memory interface......................................... 106
5.2.2. Description of current architectures............................................................ 106
5.2.3. Effect of latency on existing architectures.................................................. 111
5.3. m‑Net.................................................................................................................... 114
5.3.1. Time transformations................................................................................. 115
5.3.2. Receive transformations............................................................................. 116
5.3.3. Send transformations................................................................................. 116
5.3.4. Guarded messages..................................................................................... 118
5.3.5. Partitioning the state space (stability)......................................................... 119
5.3.6. Isopotent sets............................................................................................. 119
5.4. m‑Net -
Design...................................................................................................... 120
5.4.1. The Code Pump......................................................................................... 120
5.4.2. The Filter Cache......................................................................................... 121
5.4.3. Degrees of design...................................................................................... 122
5.5. Elaboration of degrees of design........................................................................... 125
5.5.1. No opcodes anticipated (Null implementation)........................................... 126
5.5.2. Unit Linear opcodes anticipated................................................................. 127
5.5.3. Linear opcodes anticipated......................................................................... 129
5.5.4. Recursion and Linear anticipation.............................................................. 130
5.5.5. Branching and Linear anticipation.............................................................. 131
5.5.6. Combining Recursion and Branching anticipation..................................... 135
5.5.6.1. The TreeStack............................................................................... 136
5.5.6.2. The Total implementation of m‑Net............................................... 137
5.6. Implications.......................................................................................................... 141
5.7. Conclusions.......................................................................................................... 147
Chapter 6 – m-Net
under a m-Scope................................................. 148
6.1. Performance gains................................................................................................ 150
6.2. On the feasibility of implementations as architectures........................................... 157
6.3. Observations......................................................................................................... 166
6.3.1. Kinds of instructions.................................................................................. 166
6.3.1.1. Regular opcodes (OTHER) and JUMPs...................................... 166
6.3.1.2. BRANCHES................................................................................ 167
6.3.1.3. INDIRECT................................................................................... 167
6.3.1.4. CALL and RETURN.................................................................... 168
6.3.2. Other observations..................................................................................... 169
6.4. Relation to prior work........................................................................................... 169
6.4.1. Instruction Issue Logic (Code Pumping)................................................... 170
6.4.1.1. Fairchild F8.................................................................................. 170
6.4.1.2. Distributed Logic Instruction Issue............................................... 172
6.4.1.3. The Sustained Performance Architecture...................................... 174
6.4.2. Cache issues............................................................................................... 176
6.4.2.1. Prediction/prefetching................................................................... 176
6.4.2.2. Wide lines..................................................................................... 177
6.4.2.3. Software....................................................................................... 177
6.4.2.4. Prefetching vs. cacheing............................................................... 178
6.4.2.5. Prefetch v.s pre-reply.................................................................... 179
6.4.2.6. Guarded messages........................................................................ 179
6.4.3. Other related architectures.......................................................................... 180
6.4.3.1. IBM Stretch (7030) - one of the first prefetch.............................. 180
6.4.3.2. IBM 360/91 - dual prefetch.......................................................... 181
6.4.3.3. Rope multiple prefetch.................................................................. 182
6.4.3.4. Access / execute architectures....................................................... 183
6.4.3.5. IBM RS/6000............................................................................... 184
6.4.4. Remote Evaluation..................................................................................... 184
6.4.5. Multiple alternates...................................................................................... 185
6.5. Conclusions.......................................................................................................... 185
6.5.1. Notes for designers.................................................................................... 186
6.5.2. Notes for researchers................................................................................. 187
6.5.2.1. Memory management................................................................... 187
6.5.2.2. Opcode anticipation AmdahlÕs Law.............................................. 188
6.5.2.3. FlynnÕs taxonomy......................................................................... 188
Chapter 7 – Conclusions.................................................................. 190
7.1. Review.................................................................................................................. 190
7.1.1. New questions........................................................................................... 191
7.1.2. The model.................................................................................................. 191
7.1.3. Existing protocols...................................................................................... 192
7.1.4. New protocols............................................................................................ 192
7.2. Evaluation............................................................................................................. 193
7.2.1. And the answer is...................................................................................... 193
7.2.2. Is Mirage useful?....................................................................................... 195
7.3. Future Directions.................................................................................................. 195
7.3.1. Abstract studies.......................................................................................... 195
7.3.2. Protocol studies (analysis)......................................................................... 196
7.3.3. Implementation studies (design)................................................................. 196
Chapter 8 – Bibliography................................................................ 197
Appendix A – Mirage & Shannon................................................... 207
A.1. The channel.......................................................................................................... 207
A.2. State transformations........................................................................................... 208
A.3. Levels of communication..................................................................................... 209
A.3.1. Extensions for time................................................................................... 210
A.3.2. Time vs. error............................................................................................ 211
A.4. Observations........................................................................................................ 212
Appendix B – Mirage & Physics...................................................... 213
B.1. Origins of the analogy.......................................................................................... 213
B.1.1. Field interaction as communication............................................................ 214
B.1.1.1. Four physical forces..................................................................... 215
B.1.1.2. Communication forces................................................................. 215
B.1.2. Further references...................................................................................... 215
B.2. Existing analogies from physics........................................................................... 216
B.2.1. Entropy...................................................................................................... 216
B.2.2. Uncertainty................................................................................................ 217
B.2.3. Hamiltonian function................................................................................. 217
B.3. Quantum analogies............................................................................................... 218
B.3.1. State sets / multiple worlds........................................................................ 218
B.3.2. State set collapse........................................................................................ 219
B.3.3. Virtual pairs............................................................................................... 220
B.3.4. Feynman path integrals.............................................................................. 220
B.4. Observations from the analogy............................................................................ 221
B.4.1. Error and latency as conjugates................................................................. 221
B.4.2. Stability..................................................................................................... 221
Appendix C – Upper Bound............................................................ 224
Appendix D – The Liouville Theorem.............................................. 226
Appendix E – Mirage in Set Notation.............................................. 228
E.1. Definitions............................................................................................................ 228
E.2. Time Transform.................................................................................................... 229
E.3. Receive Transform............................................................................................... 231
E.4. Send Transform.................................................................................................... 232
E.5. Observations........................................................................................................ 232
Appendix F – Mirage & Petri Nets.................................................. 233
F.1. Petri Net Analogs................................................................................................. 233
F.1.1 Communication channel.............................................................................. 236
F.1.1.1 Basic block.................................................................................... 237
F.1.1.2 Virtual tokens................................................................................ 238
F.1.2 Equivalences to Mirage transformations..................................................... 240
F.1.2.1 Time.............................................................................................. 240
F.1.2.2 Send.............................................................................................. 241
F.1.2.3 Receive.......................................................................................... 242
F.2. Capacity in a PN................................................................................................... 242
Appendix G – The TreeStack.......................................................... 244
G.1. Components......................................................................................................... 244
G.2. Operations........................................................................................................... 245
G.2.1. Push.......................................................................................................... 245
G.2.2. Pop............................................................................................................ 246
G.2.3. Branch....................................................................................................... 246
G.2.4. Select subtree............................................................................................ 247
G.2.5. Equivalence transforms - Twinning and UnTwinning.............................. 248
G.2.6. Canonical forms........................................................................................ 248
G.2.6.1. Twinned TreeStack...................................................................... 249
G.2.6.2. UnTwinned TreeStack................................................................. 249
G.2.7. The Graft transform.................................................................................. 250
Appendix H – m‑Scope
Methods...................................................... 254
H.1. Existing Tools...................................................................................................... 254
H.2. The method.......................................................................................................... 257
H.3. Observations........................................................................................................ 259
H.4. AWK scripts and C-language code listings......................................................... 260
H.4.1. MSCOPE.h - C-language ÔincludeÕ file.................................................... 260
H.4.2. INSERT_SYMBOLS - AWK, inserts signals in SPARC
assembler....... 260
H.4.3. INSERT_OPCODES - AWK, signals become SPARC assembler.......... 264
H.4.4. MSCOPE.c code - output desired statistics............................................... 265
H.4.5. STATIC_COUNT - get static SPARC opcode distributions.................... 267
List of Tables
Chapter
1 – Introduction................................................................ 1
Table 1.1: Network size and speed equivalences.............................................................. 12
Table 1.2: Network and node characteristics.................................................................... 14
Chapter 2 – The Mirage model........................................................ 17
Chapter 3 – Prior Work.................................................................. 48
Chapter 4 – A Mirage of NTP......................................................... 72
Table 4.1: NTP versions and components........................................................................ 78
Table 4.2: Mirage interpretation of the state variables of NTP......................................... 89
Chapter 5 – m-Net........................................................................... 102
Table 5.1: Opcode time transformations........................................................................... 117
Table 5.2: Degrees of implementation, and the implications of
each................................ 123
Table 5.3: Null Filter send actions.................................................................................... 126
Table 5.4: Null Filter receive actions................................................................................ 126
Table 5.5: Null Converger actions.................................................................................... 127
Table 5.6: Null Diverger actions...................................................................................... 127
Table 5.7: Unit Linear Filter send actions......................................................................... 128
Table 5.8: Unit Linear Diverger actions........................................................................... 128
Table 5.9: Linear Filter send actions................................................................................. 129
Table 5.10: Linear Diverger actions................................................................................. 130
Table 5.11: Recursion Filter send actions......................................................................... 130
Table 5.12: Recursion Diverger actions........................................................................... 131
Table 5.13: Branching Filter send actions........................................................................ 133
Table 5.14: Branching Filter receive actions..................................................................... 133
Table 5.15: Branching Converger actions........................................................................ 134
Table 5.16: Branching Diverger actions........................................................................... 134
Table 5.17: Total Filter send actions................................................................................. 138
Table 5.18: Total Filter receive actions (same as Branching
filter)................................... 139
Table 5.19: Total Converger actions................................................................................. 139
Table 5.20: Total Diverger actions................................................................................... 140
Table 5.21: CPI (EXEC) values of common CISC and RISC CPUs............................... 146
Chapter 6 – m-Net
under a m-Scope................................................. 148
Table 6.1: Approximate dynamic opcode distribution...................................................... 152
Table 6.2: Approximate speedup in various degrees of
implementation........................... 153
Table 6.3: m‑Net
implementations and cache equivalents (no branch assumption)........... 154
Table 6.4: m‑Net
implementations & cache equivalents (equiprobable branching)........... 155
Table 6.5: Adjusted dynamic opcode distributions (approx. a
cache miss stream)........... 155
Table 6.6: Performance increases where latency dominates
design parameters................ 156
Table 6.7: Mean and median limb lengths for m‑Nets implementing branching............... 162
Chapter 7 – Conclusions.................................................................. 190
Chapter 8 – Bibliography................................................................ 197
Appendix A – Mirage & Shannon................................................... 207
Table A.1: WeaverÕs 3 levels of communication.............................................................. 210
Table A.2: MirageÕs 2 levels of latency............................................................................ 212
Appendix B – Mirage & Physics...................................................... 213
Table B.1: Physics analogs of protocol components........................................................ 214
Appendix C – Upper Bound............................................................ 224
Appendix D – The Liouville Theorem.............................................. 226
Appendix E – Mirage in Set Notation.............................................. 228
Appendix F – Mirage & Petri Nets.................................................. 233
Appendix G – The TreeStack.......................................................... 244
Appendix H – m‑Scope
Methods...................................................... 254
List of Illustrations
Chapter
1 – Introduction................................................................ 1
Figure 1.1: Network rate.................................................................................................. 9
Figure 1.2: Increased rate as bit foreshortening................................................................ 10
Figure 1.3: Figure 1.1, as it appears to the bits in transit.................................................. 10
Figure 1.4: Network size and speed equivalences............................................................ 12
Figure 1.5: Node buffer size (memory) vs. information
separation (bit -latency)............. 13
Chapter 2 – The Mirage model........................................................ 17
Figure 2.1: Kinds of protocol lookahead / branching....................................................... 19
Figure 2.2: Utilization as latency increases (linear lookahead)......................................... 20
Figure 2.3: Tree levels...................................................................................................... 24
Figure 2.4: Utilization of branching lookahead (P=5, D=2, L=4)................................... 25
Figure 2.5: Channel utilization (relative to lnear)
(P=5,D=2,L=4)................................... 26
Figure 2.6: Utilization vs. branch arm length (geometric)................................................ 28
Figure 2.7: Utilization vs. branch degree (geometric)....................................................... 28
Figure 2.8: Mirage communication channel..................................................................... 31
Figure 2.9: ShannonÕs model........................................................................................... 33
Figure 2.10: Visualization of state space volume
transformations.................................... 34
Figure 2.11: Control space evolution............................................................................... 37
Figure 2.12: Entire space affected by unguarded message............................................... 40
Figure 2.13: Guarded messages affecting partitions only................................................. 40
Figure 2.14: Bit foreshortening and its effect on lookahead /
utilization........................... 42
Figure 2.15: Bit
foreshortening and branching effecting utilization................................. 43
Chapter 3 – Prior Work.................................................................. 48
Chapter 4 – A Mirage of NTP......................................................... 72
Figure 4.1: NTP message format..................................................................................... 74
Figure 4.2: NTP message exchange................................................................................. 75
Figure 4.3: Exchange slid forward (maximum offset)...................................................... 77
Figure 4.4: Exchange slid backward (minimum offset).................................................... 77
Figure 4.5: Unidirectional delay as a Poisson pdf............................................................ 80
Figure 4.6: Bidirectional delay is the convolution of
unidirectional delays....................... 80
Figure 4.7: Measured offset is unidirectional delay convolved
with its reverse............... 80
Figure 4.8: Bidirectional delay as Erlangian (N=2).......................................................... 81
Figure 4.9: Measured offset as pseudo-Gaussian............................................................ 81
Figure 4.10: Probability vs. [delay, offset] pairs, density
plot.......................................... 81
Figure 4.11: Tuesday offset values (off-peak)................................................................. 82
Figure 4.12: Friday offset values (peak).......................................................................... 82
Figure 4.13: Tuesday delay values (off-peak).................................................................. 83
Figure 4.14: Friday delay values (peak)........................................................................... 83
Figure 4.15: Delay v.s offset, time-repetition density
(off-peak)...................................... 84
Figure 4.16: Delay vs. offset, time-repetition density (peak)............................................ 84
Figure 4.17: Delay vs. offset vs. probability, time-series
(off-peak)................................ 85
Figure 4.18: Fixed (black) and variable (gray) delay in
message exchange...................... 86
Figure 4.19: Exchange maximum offset, variable delay................................................... 86
Figure 4.20: Exchange minimum offset, variable delay.................................................... 86
Figure 4.21: Delay vs. offset, entire ensemble (all strata)................................................. 87
Figure 4.22: Stratum 1 ensemble...................................................................................... 88
Figure 4.23: Stratum 2 ensemble...................................................................................... 88
Figure 4.24: Stratum 3 ensemble...................................................................................... 88
Figure 4.25: Stratum 4 ensemble...................................................................................... 88
Figure 4.26: Clock value is a function of time.................................................................. 91
Figure 4.27: Clock interval as fixed expansion centered on
time function........................ 91
Figure 4.28: Transformation of a perception due to a sent NTP
message........................ 92
Figure 4.29: Transformation of a perception due to a received
NTP message.................. 94
Figure 4.30: Receive transformation, accommodating transit
time effects.........
