Laboratory Notes: 'Gossiping' Networks

Devavrat Shah
Laboratory for Information and Decision Systems

Algorithms, the building blocks of any network architecture, are highly constrained in modern networks; yet a lot is required of them in terms of performance. To operate at very high speed (> 10Gbps) or to utilize minimal resources in energy constrained networks, they have to be extremely simple; they need to be distributed so as to be scalable and robust in terms of network node mobility and/or failures; and the algorithms should be agile in performance adaptation with respect to available resources.

We propose message-passing or intelligent rumor spreading (in other words, constructive ‘gossiping’) as a paradigm to realize such network algorithmic architecture. We have demonstrated a design of high-performance message-passing algorithms for three important questions: first, scheduling transfer of packets across a switch fabric in a cross-bar switch (e.g. Cisco’s high-speed routers); second, scheduling of sub-carriers for transmission in an OFDMA-based communication (e.g. in IEEE 802.16 standard); and third, scheduling in a wireless LAN network operating with CSMA communication (e.g., in IEEE 802.11 standard).

Key features of our algorithms are lightweight data-structures, use of a few simple logical operations (additions and subtractions), tunable performance by trading-off resources through a kind of ‘parametric knob’ and provable performance guarantees. Our algorithms are based on ideas borrowed from extremal Properties of distributions known in probability theory, iterative algorithms such as belief propagation that have emerged from statistical physics and artificial intelligence and randomization.

Leave a Reply

Replies which add to the content of this article in the EECS Newsletter are welcome. The Department reserves the right to moderate all comments. If you would like to provide any updated information please send an email to