idnits 2.17.1 draft-ietf-roll-trickle-08.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- No issues found here. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document date (January 10, 2011) is 4827 days in the past. Is this intentional? Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) == Missing Reference: 'Imin' is mentioned on line 227, but not defined == Missing Reference: 'Imax' is mentioned on line 227, but not defined == Outdated reference: A later version (-19) exists of draft-ietf-roll-rpl-17 Summary: 0 errors (**), 0 flaws (~~), 4 warnings (==), 1 comment (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Networking Working Group P. Levis 3 Internet-Draft Stanford University 4 Intended status: Standards Track T. Clausen 5 Expires: July 14, 2011 LIX, Ecole Polytechnique 6 J. Hui 7 Arch Rock Corporation 8 O. Gnawali 9 Stanford University 10 J. Ko 11 Johns Hopkins University 12 January 10, 2011 14 The Trickle Algorithm 15 draft-ietf-roll-trickle-08 17 Abstract 19 The Trickle algorithm allows nodes in a lossy shared medium (e.g., 20 low power and lossy networks) to exchange information in a highly 21 robust, energy efficient, simple, and scalable manner. Dynamically 22 adjusting transmission windows allows Trickle to spread new 23 information on the scale of link-layer transmission times while 24 sending only a few messages per hour when information does not 25 change. A simple suppression mechanism and transmission point 26 selection allows Trickle's communication rate to scale 27 logarithmically with density. This document describes the Trickle 28 algorithm and considerations in its use. 30 Status of this Memo 32 This Internet-Draft is submitted in full conformance with the 33 provisions of BCP 78 and BCP 79. 35 Internet-Drafts are working documents of the Internet Engineering 36 Task Force (IETF). Note that other groups may also distribute 37 working documents as Internet-Drafts. The list of current Internet- 38 Drafts is at http://datatracker.ietf.org/drafts/current/. 40 Internet-Drafts are draft documents valid for a maximum of six months 41 and may be updated, replaced, or obsoleted by other documents at any 42 time. It is inappropriate to use Internet-Drafts as reference 43 material or to cite them other than as "work in progress." 45 This Internet-Draft will expire on July 14, 2011. 47 Copyright Notice 48 Copyright (c) 2011 IETF Trust and the persons identified as the 49 document authors. All rights reserved. 51 This document is subject to BCP 78 and the IETF Trust's Legal 52 Provisions Relating to IETF Documents 53 (http://trustee.ietf.org/license-info) in effect on the date of 54 publication of this document. Please review these documents 55 carefully, as they describe your rights and restrictions with respect 56 to this document. Code Components extracted from this document must 57 include Simplified BSD License text as described in Section 4.e of 58 the Trust Legal Provisions and are provided without warranty as 59 described in the Simplified BSD License. 61 Table of Contents 63 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 64 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 3 65 3. Trickle Algorithm Overview . . . . . . . . . . . . . . . . . . 4 66 4. Trickle Algorithm . . . . . . . . . . . . . . . . . . . . . . 5 67 4.1. Parameters and Variables . . . . . . . . . . . . . . . . . 5 68 4.2. Algorithm Description . . . . . . . . . . . . . . . . . . 5 69 5. Using Trickle . . . . . . . . . . . . . . . . . . . . . . . . 6 70 6. Operational Considerations . . . . . . . . . . . . . . . . . . 7 71 6.1. Mismatched Redundancy Constants . . . . . . . . . . . . . 7 72 6.2. Mismatched Imin . . . . . . . . . . . . . . . . . . . . . 7 73 6.3. Mismatched Imax . . . . . . . . . . . . . . . . . . . . . 8 74 6.4. Mismatched Definitions . . . . . . . . . . . . . . . . . . 8 75 6.5. Specifying the Constant k . . . . . . . . . . . . . . . . 8 76 6.6. Relationship Between k and Imin . . . . . . . . . . . . . 9 77 6.7. Tweaks and Improvements to Trickle . . . . . . . . . . . . 9 78 6.8. Uses of Trickle . . . . . . . . . . . . . . . . . . . . . 9 79 7. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 10 80 8. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 10 81 9. Security Considerations . . . . . . . . . . . . . . . . . . . 10 82 10. References . . . . . . . . . . . . . . . . . . . . . . . . . . 11 83 10.1. Normative References . . . . . . . . . . . . . . . . . . . 11 84 10.2. Informative References . . . . . . . . . . . . . . . . . . 11 85 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 12 87 1. Introduction 89 The Trickle algorithm establishes a density-aware local communication 90 primitive with an underlying consistency model that guides when a 91 node transmits. When a node's data does not agree with its 92 neighbors, that node communicates quickly to resolve the 93 inconsistency (e.g., in milliseconds). When nodes agree, they slow 94 their communication rate exponentially, such that nodes send packets 95 very infrequently (e.g., a few packets per hour). Instead of 96 flooding a network with packets, the algorithm controls the send rate 97 so each node hears a small trickle of packets, just enough to stay 98 consistent. Furthermore, by relying only on local communication 99 (e.g., broadcast or local multicast), Trickle handles network re- 100 population, is robust to network transience, loss, and disconnection, 101 is simple to implement, and requires very little state. Current 102 implementations use 4-11 bytes of RAM and are 50-200 lines of C 103 code[Levis08]. 105 While Trickle was originally designed for reprogramming protocols 106 (where the data is the code of the program being updated), experience 107 has shown it to be a powerful mechanism that can be applied to wide 108 range of protocol design problems, including control traffic timing, 109 multicast propagation, and route discovery. This flexibility stems 110 from being able to define, on a case-by-case basis, what constitutes 111 "agreement" or an "inconsistency;" Section 6.8 presents a few 112 examples of how the algorithm can be used. 114 This document describes the Trickle algorithm and provides guidelines 115 for its use. It also states requirements for protocol specifications 116 that use Trickle. This document does not provide results on 117 Trickle's performance or behavior, nor does it explain the 118 algorithm's design in detail: interested readers should refer to 119 [Levis04] and [Levis08]. 121 2. Terminology 123 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 124 "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and 125 "OPTIONAL" in this document are to be interpreted as described in RFC 126 2119 [RFC2119]. 128 Additionally, this document introduces the following terminology: 130 Trickle communication rate: the sum of the number of messages sent 131 or received by the Trickle algorithm in an interval. 133 Trickle transmission rate: the sum of the number of messages sent by 134 the Trickle algorithm in an interval. 136 3. Trickle Algorithm Overview 138 Trickle's basic primitive is simple: every so often, a node transmits 139 data unless it hears a few other transmissions whose data suggest its 140 own transmission is redundant. Examples of such data include routing 141 state, software update versions, and the last heard multicast packet. 142 This primitive allows Trickle to scale to thousand-fold variations in 143 network density, quickly propagate updates, distribute transmission 144 load evenly, be robust to transient disconnections, handle network 145 repopulations, and impose a very low maintenance overhead: one 146 example use, routing beacons in the CTP protocol [Gnawali09], 147 requires sending on the order of a few packets per hour yet can 148 respond in milliseconds. 150 Trickle sends all messages to a local communication address. The 151 exact address used can depend on both the underlying IP protocol as 152 well as how the higher layer protocol uses Trickle. In IPv6, for 153 example, it can be the link-local multicast address or another local 154 multicast address, while in IPv4 it can be the broadcast address 155 (255.255.255.255). 157 There are two possible results to a Trickle message: either every 158 node that hears the message finds the message data is consistent with 159 its own state, or a recipient detects an inconsistency. Detection 160 can be the result of either an out-of-date node hearing something 161 new, or an updated node hearing something old. As long as every node 162 communicates somehow - either receives or transmits - some node will 163 detect the need for an update. 165 For example, consider a simple case where "up to date" is defined by 166 version numbers (e.g., network configuration). If node A transmits 167 that it has version V, but B has version V+1, then B knows that A 168 needs an update. Similarly, if B transmits that it has version V+1, 169 A knows that it needs an update. If B broadcasts or multicasts 170 updates, then all of its neighbors can receive them without having to 171 advertise their need. Some of these recipients might not have even 172 heard A's transmission. In this example, it does not matter who 173 first transmits, A or B; either case will detect the inconsistency. 175 The fact that Trickle communication can be either transmission or 176 reception enables the Trickle algorithm to operate in sparse as well 177 as dense networks. A single, disconnected node must transmit at the 178 Trickle communication rate. In a lossless, single-hop network of 179 size n, the Trickle communication rate at each node equals the sum of 180 the Trickle transmission rates across all nodes. The Trickle 181 algorithm balances the load in such a scenario, as each node's 182 Trickle transmission rate is 1/nth of the Trickle communication rate. 183 Sparser networks require more transmissions per node, but the 184 utilization of a given broadcast domain (e.g., radio channel over 185 space, shared medium) will not increase. This is an important 186 property in wireless networks and other shared media, where the 187 channel is a valuable shared resource. Additionally, reducing 188 transmissions in dense networks conserves system energy. 190 4. Trickle Algorithm 192 This section describes the Trickle algorithm. 194 4.1. Parameters and Variables 196 A Trickle timer runs for a defined interval and has three 197 configuration parameters: the minimum interval size Imin, the maximum 198 interval size Imax, and a redundancy constant k: 200 o The minimum interval size, Imin, is defined in units of time 201 (e.g., milliseconds, seconds). For example, a protocol might 202 define the minimum interval as 100 milliseconds. 204 o The maximum interval size, Imax, is described as a number of 205 doublings of the minimum interval size (the base-2 log(max/min)). 206 For example, a protocol might define Imax as 16. If the minimum 207 interval is 100ms, then the amount of time specified by Imax is 208 100ms * 65536, 6,553.6 seconds, or approximately 109 minutes. 210 o The redundancy constant is a natural number (an integer greater 211 than zero). 213 In addition to these three parameters, Trickle maintains three 214 variables: 216 o I, the current interval size 218 o t, a time within the current interval, and 220 o c, a counter. 222 4.2. Algorithm Description 224 The Trickle algorithm has six rules: 226 1. When the algorithm starts execution, it sets I to a value in the 227 range of [Imin, Imax], that is, greater than or equal to Imin and 228 less then or equal to Imax. The algorithm then begins the first 229 interval. 231 2. When an interval begins, Trickle resets c to 0 and sets t to a 232 random point in the interval, taken from the range [I/2, I), that 233 is, values greater than or equal to I/2 and less than I. The 234 interval ends at I. 236 3. Whenever Trickle hears a transmission that is "consistent," it 237 increments the counter c. 239 4. At time t, Trickle transmits if and only if the counter c is less 240 than the redundancy constant k. 242 5. When the interval I expires, Trickle doubles the interval length. 243 If this new interval length would be longer than the time 244 specified by Imax, Trickle sets the interval length I to be the 245 time specified by Imax. 247 6. If Trickle hears a transmission that is "inconsistent" and I is 248 greater than Imin, it resets the Trickle timer. To reset the 249 timer, Trickle sets I to Imin and starts a new interval as in 250 step 2. If I is equal to Imin when Trickle hears an 251 "inconsistent" transmission, Trickle does nothing. Trickle can 252 also reset its timer in response to external "events." 254 The terms consistent, inconsistent and event are in quotes because 255 their meaning depends on how a protocol uses Trickle. 257 The only time the Trickle algorithm transmits is at step 3 of the 258 above algorithm. This means there is an inherent delay between 259 detecting an inconsistency (shrinking I to Imin) and responding to 260 that inconsistency (transmitting at time t in the new interval). 261 This is intentional. Immediately responding to detecting an 262 inconsistency can cause a broadcast storm, where many nodes respond 263 at once and in a synchronized fashion. By making responses follow 264 the Trickle algorithm (with the minimal interval size), a protocol 265 can benefit from Trickle's suppression mechanism and scale across a 266 huge range of node densities. 268 5. Using Trickle 270 A protocol specification that uses Trickle MUST specify: 272 o Default values for Imin, Imax, and k. Because link layers can 273 vary widely in their properties, the default value of Imin SHOULD 274 be specified in terms of the worst-case latency of a link layer 275 transmission. For example, a specification should say "the 276 default value of Imin is 4 times the worst case link layer 277 latency" and should not say "the default value of Imin is 500 278 milliseconds." Worst case latency is approximately time until the 279 first link-layer transmission of the frame assuming an idle 280 channel (does not include backoff, virtual carrier sense, etc.). 282 o What constitutes a "consistent" transmission. 284 o What constitutes an "inconsistent" transmission. 286 o What "events," if any, besides inconsistent transmissions that 287 reset the Trickle timer. 289 o What information a node transmits in Trickle messages. 291 o What actions outside the algorithm the protocol takes, if any, 292 when it detects an inconsistency. 294 6. Operational Considerations 296 It is RECOMMENDED that a protocol which uses Trickle includes 297 mechanisms to inform nodes of configuration parameters at runtime. 298 However, it is not always possible to do so. In the cases where 299 different nodes have different configuration parameters, Trickle may 300 have unintended behaviors. This section outlines some of those 301 behaviors and operational considerations as educational exercises. 303 6.1. Mismatched Redundancy Constants 305 If nodes do not agree on the redundancy constant k, then nodes with 306 higher values of k will transmit more often than nodes with lower 307 values of k. In some cases, this increased load can be independent 308 of the density. For example, consider a network where all nodes but 309 one have k=1, and this one node has k=2. The different node can end 310 up transmitting on every interval: it is maintaining a Trickle 311 communication rate of 2 with only itself. Hence, the danger of 312 mismatched k values is uneven transmission load that can deplete the 313 energy of some nodes in a low power network. 315 6.2. Mismatched Imin 317 If nodes do not agree on Imin, then some nodes, on hearing 318 inconsistent messages, will transmit sooner than others. These 319 faster nodes will have their intervals grow to similar size as the 320 slower nodes within a single slow interval time, but in that period 321 may suppress the slower nodes. However, such suppression will end 322 after the first slow interval, when the nodes generally agree on the 323 interval size. Hence, mismatched Imin values are usually not a 324 significant concern. Note that mismatched Imin values and matching 325 Imax doubling constants will lead to mismatched maximum interval 326 lengths. 328 6.3. Mismatched Imax 330 If nodes do not agree on Imax, then this can cause long-term problems 331 with transmission load. Nodes with small Imax values will transmit 332 faster, suppressing those with larger Imax values. The nodes with 333 larger Imax values, always suppressed, will never transmit. In the 334 base case, when the network is consistent, this can cause long-term 335 inequities in energy cost. 337 6.4. Mismatched Definitions 339 If nodes do not agree on what constitutes a consistent or 340 inconsistent transmission, then Trickle may fail to operate properly. 341 For example, if a receiver thinks a transmission is consistent, but 342 the transmitter (if in the receivers situation) would have thought it 343 inconsistent, then the receiver will not respond properly and inform 344 the transmitter. This can lead the network to not reach a consistent 345 state. For this reason, unlike the configuration constants k, Imin, 346 and Imax, consistency definitions MUST be clearly stated in the 347 protocol and SHOULD NOT be configured at runtime. 349 6.5. Specifying the Constant k 351 There are some edge cases where a protocol may wish to use Trickle 352 with its suppression disabled (k is set to infinity). In general, 353 this approach is highly dangerous and it is NOT RECOMMENDED. 354 Disabling suppression means that every node will always send on every 355 interval, and can lead to congestion in dense networks. This 356 approach is especially dangerous if many nodes reset their intervals 357 at the same time. In general, it is much more desirable to set k to 358 a high value (e.g., 5 or 10) than infinity. Typical values for k are 359 1-5: these achieve a good balance between redundancy and low 360 cost[Levis08]. 362 Nevertheless, there are situations where a protocol may wish to turn 363 off Trickle suppression. Because k is a natural number 364 (Section 4.1), k=0 has no useful meaning. If a protocol allows k to 365 be dynamically configured, a value of 0 remains unused. For ease of 366 debugging and packet inspection, having the parameter describe k-1 367 rather than k can be confusing. Instead, it is RECOMMENDED that 368 protocols which require turning off suppression reserve k=0 to mean 369 k=infinity. 371 6.6. Relationship Between k and Imin 373 Finally, a protocol SHOULD set k and Imin such that Imin is at least 374 two to three times as long as it takes to transmit k packets. 375 Otherwise, if more than k nodes reset their intervals to Imin, the 376 resulting communication will lead to congestion and significant 377 packet loss. Experimental results have shown that packet losses from 378 congestion reduce Trickle's efficiency [Levis04]. 380 6.7. Tweaks and Improvements to Trickle 382 Trickle is based on a small number of simple, tightly integrated 383 mechanisms that are highly robust to challenging network 384 environments. In our experiences using Trickle, attempts to tweak 385 its behavior are typically not worth the cost. As written, the 386 algorithm is already highly efficient: further reductions in 387 transmissions or response time come at the cost of failures in edge 388 cases. Based on our experiences, we urge protocol designers to 389 suppress the instinct to tweak or improve Trickle without a great 390 deal of experimental evidence that the change does not violate its 391 assumptions and break the algorithm in edge cases. 393 This warning in mind, Trickle is far from perfect. For example, 394 Trickle suppression typically leads sparser nodes to transmit more 395 than denser ones; it is far from the optimal computation of a minimum 396 cover. However, in dynamic network environments such as wireless and 397 low-power, lossy networks, the coordination needed to compute the 398 optimal set of transmissions is typically much greater than the 399 benefits it provides. One of the benefits of Trickle is that it is 400 so simple to implement and requires so little state yet operates so 401 efficiently. Efforts to improve it should be weighed against the 402 cost of increased complexity. 404 6.8. Uses of Trickle 406 The Trickle algorithm has been used in a variety of protocols, both 407 in operational as well as academic settings. Giving a brief overview 408 of some of these uses provides useful examples of how and when it can 409 be used. These examples should not be considered exhaustive. 411 Reliable flooding/dissemination: A protocol uses Trickle to 412 periodically advertise the most recent data it has received, 413 typically through a version number. An inconsistency is when a node 414 hears a newer version number or receives new data. A consistency is 415 when a node hears an older or equal version number. When hearing an 416 older version number, rather than reset its own Trickle timer, it 417 sends an update. Nodes with old version numbers that receive the 418 update will then reset their own timers, leading to fast propagation 419 of the new data. Examples of this use include multicast[Hui08a], 420 network configuration[Lin08][Dang09], and installing new application 421 programs[Hui04][Levis04]. 423 Routing control traffic: A protocol uses Trickle to control when it 424 sends beacons which contain routing state. An inconsistency is when 425 the routing topology changes in a way that could lead to loops or 426 significant stretch: examples include when the routing layer detects 427 a routing loop or when a node's routing cost changes significantly. 428 Consistency is when the routing topology is operating well and is 429 delivering packets successfully. Using the Trickle algorithm in this 430 way allows a routing protocol to react very quickly to problems (Imin 431 is small) but send very few beacons when the topology is stable. 432 Examples of this use include RPL[I-D.ietf-roll-rpl], CTP[Gnawali09], 433 and some current commericial IPv6 routing layers[Hui08b]. 435 7. Acknowledgements 437 The authors would like to acknowledge the guidance and input provided 438 by the ROLL chairs, David Culler and JP Vasseur. 440 The authors would also like to acknowledge the helpful comments of 441 Yoav Ben-Yehezkel, Alexandru Petrescu, and Ulrich Herberg, which 442 greatly improved the document. 444 8. IANA Considerations 446 This document has no IANA considerations. 448 9. Security Considerations 450 As it is an algorithm, Trickle itself does not have any specific 451 security considerations. However, two security concerns can arise 452 when Trickle is used in a protocol. The first is that an adversary 453 can force nodes to send many more packets than needed by forcing 454 Trickle timer resets. In low power networks this increase in traffic 455 can harm system lifetime. The second concern is that an adversary 456 can prevent nodes from reaching consistency. 458 Protocols can prevent adversarial Trickle resets by carefully 459 selecting what can cause a reset and protecting these events and 460 messages with proper security mechanisms. For example, if a node can 461 reset nearby Trickle timers by sending a certain packet, this packet 462 should be authenticated such that an adversary cannot forge one. 464 An adversary can possibly prevent nodes from reaching consistency by 465 suppressing transmissions with "consistent" messages. For example, 466 imagine node A detects an inconsistency and resets its Trickle timer. 467 If an adversary can prevent A from sending messages that inform 468 nearby nodes of the inconsistency in order to repair it, then A may 469 remain inconsistent indefinitely. Depending on the security model of 470 the network, authenticated messages, or a transitive notion of 471 consistency can prevent this problem. E.g., if messages that are 472 consistent with A and so suppress its transmissions are by definition 473 inconsistent with what A heard, then an adversary cannot 474 simultaneously prevent A from notifying neighbors and not notify the 475 neighbors itself (recall Trickle operates on shared, broadcast 476 media). Note that this means Trickle should filter unicast messages. 478 10. References 480 10.1. Normative References 482 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 483 Requirement Levels", BCP 14, RFC 2119, March 1997. 485 10.2. Informative References 487 [Dang09] Dang, T., Bulusu, N., Feng, W., and S. Park, "DHV: A Code 488 Consistency Maintenance Protocol for Multi-hop Wireless 489 Networks", Wireless Sensor Networks: 6th European 490 Conference Proceedings EWSN 2009 Cork, February 2009, 491 . 493 [Gnawali09] 494 Gnawali, O., Fonseca, R., Jamieson, K., Moss, D., and P. 495 Levis, "Collection Tree Protocol", Proceedings of the 7th 496 ACM Conference on Embedded Networked Systems SenSys 2009, 497 November 2009, 498 . 500 [Hui04] Hui, J. and D. Culler, "The dynamic behavior of a data 501 dissemination protocol for network programming at scale", 502 Proceedings of the 2nd ACM Conference on Embedded 503 Networked Systems SenSys 2004, November 2004, 504 . 506 [Hui08a] Hui, J., "An Extended Internet Architecture for Low-Power 507 Wireless Networks - Design and Implementation", UC 508 Berkeley Technical Report EECS-2008-116, September 2008, 509 . 511 [Hui08b] Hui, J. and D. Culler, "IP is dead, long live IP for 512 wireless sensor networks", Proceedings of the 6th ACM 513 Conference on Embedded Networked Systems SenSys 2008, 514 November 2008, 515 . 517 [I-D.ietf-roll-rpl] 518 Winter, T., Thubert, P., Brandt, A., Clausen, T., Hui, J., 519 Kelsey, R., Levis, P., Pister, K., Struik, R., and J. 520 Vasseur, "RPL: IPv6 Routing Protocol for Low power and 521 Lossy Networks", draft-ietf-roll-rpl-17 (work in 522 progress), December 2010. 524 [Levis04] Levis, P., Patel, N., Culler, D., and S. Shenker, 525 "Trickle: A Self-Regulating Algorithm for Code Propagation 526 and Maintenance in Wireless Sensor Networks"", Proceedings 527 of the First USENIX/ACM Symposium on Networked Systems 528 Design and Implementation NSDI 2004, March 2004, 529 . 531 [Levis08] Levis, P., Brewer, E., Culler, D., Gay, D., Madden, S., 532 Patel, N., Polastre, J., Shenker, S., Szewczyk, R., and A. 533 Woo, "The Emergence of a Networking Primitive in Wireless 534 Sensor Networks", Communications of the ACM, v.51 n.7, 535 July 2008, 536 . 538 [Lin08] Lin, K. and P. Levis, "Data Discovery and Dissemination 539 with DIP", Proceedings of the 7th international conference 540 on Information processing in sensor networks IPSN 2008, 541 April 2008, 542 . 544 Authors' Addresses 546 Philip Levis 547 Stanford University 548 358 Gates Hall, Stanford University 549 Stanford, CA 94305 550 USA 552 Phone: +1 650 725 9064 553 Email: pal@cs.stanford.edu 555 Thomas Heide Clausen 556 LIX, Ecole Polytechnique 558 Phone: +33 6 6058 9349 559 Email: T.Clausen@computer.org 561 Jonathan Hui 562 Arch Rock Corporation 563 501 Snd St., Suite 410 564 San Francisco, CA 94107 565 USA 567 Email: jhui@archrock.com 569 Omprakash Gnawali 570 Stanford University 571 S255 Clark Center, 318 Campus Drive 572 Stanford, CA 94305 573 USA 575 Phone: +1 650 725 6086 576 Email: gnawali@cs.stanford.edu 578 JeongGil Ko 579 Johns Hopkins University 580 3400 N. Charles St., 224 New Engineering Building 581 Baltimore, MD 21218 582 USA 584 Phone: +1 410 516 4312 585 Email: jgko@cs.jhu.edu