nach oben

Queueing Systems

Erschienen in:

01.12.2012

Towards a queueing-based framework for in-network function computation

verfasst von: Siddhartha Banerjee, Piyush Gupta, Sanjay Shakkottai

Erschienen in: Queueing Systems | Ausgabe 3-4/2012

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

We seek to develop network algorithms for function computation in sensor networks. Specifically, we want dynamic joint aggregation, routing, and scheduling algorithms that have analytically provable performance benefits due to in-network computation as compared to simple data forwarding. To this end, we define a class of functions, the Fully-Multiplexible functions, which includes several functions such as parity, MAX, and kth-order statistics. For such functions we characterize the maximum achievable refresh rate of the network in terms of an underlying graph primitive, the min-mincut. In acyclic wireline networks we show that the maximum refresh rate is achievable by a simple algorithm that is dynamic, distributed, and only dependent on local information. In the case of wireless networks we provide a MaxWeight-like algorithm with dynamic flow-splitting, which is shown to be throughput-optimal.

Vorheriger Artikel On distributed scheduling with heterogeneously delayed network-state information

Nächster Artikel Controlled mobility in stochastic and dynamic wireless networks

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Nur mit Berechtigung zugänglich

By stability, we refer to the standard notion of the existence of a stationary regime for the queueing process [13, 22].

Note that this assumption is not the most general possible restriction on the input process but one that we choose for convenience of exposition. For more general conditions on the arrival process, refer to [13].

Note that such an optimal rate point exists as the min-mincut is a continuous function of the rates which lie in a compact set \(\mathcal {CH}(\varGamma)\).

Giridhar, A., Kumar, P.R.: Computing and communicating functions over sensor networks. IEEE J. Sel. Areas Commun. 23(4), 755–764 (2005) CrossRef

Gupta, P., Kumar, P.R.: The capacity of wireless networks. IEEE Trans. Inf. Theory 46(2), 388–404 (2000) CrossRef

Orlitsky, A., Roche, J.R.: Coding for computing. IEEE Trans. Inf. Theory 47(3), 903–917 (2001) CrossRef

Ma, N., Ishwar, P., Gupta, P.: Information-theoretic bounds for multiround function computation in collocated networks. CoRR (2009). arXiv:0901.2356

Kowshik, H., Kumar, P.R.: Optimal computation of symmetric boolean functions in tree networks. In: IEEE International Symposium on Information Theory—ISIT 2010, Austin, July. IEEE Conference Proceedings (2010)

Appuswamy, R., Franceschetti, M., Karamchandani, N., Zeger, K.: Network coding for computing part I: Cut-set bounds. CoRR (2009). arXiv:0912.2820

Moscibroda, T.: The worst-case capacity of wireless sensor networks. In: Internat. Workshop on Inform. Processing in Sensor Networks (IPSN), pp. 1–10 (2007)

Krishnamachari, B., Estrin, D., Wicker, S.B.: The impact of data aggregation in wireless sensor networks. In: Proc. the 26th IEEE Internat. Conf. Distributed Computing Systems (ICDCS), pp. 575–578 (2002)

Karamchandani, N., Keller, L., Fragouli, C., Franceschetti, M.: Function computation via subspace coding. In: Proc. IEEE Int. Symp. Information Theory (ISIT), Austin, July. IEEE Conference Proceedings (2010)

10.

Baek, S.J., de Veciana, G., Su, X.: Minimizing energy consumption in large-scale sensor networks through distributed data compression and hierarchical aggregation. IEEE J. Sel. Areas Commun. 22(6), 1130–1140 (2004) CrossRef

11.

Sharma, A., Golubchik, L., Govindan, R., Neely, M.J.: Dynamic data compression in multi-hop wireless networks. In: Proc. Ann. ACM SIGMETRICS/Performance Conf., pp. 145–156 (2009)

12.

Tassiulas, L., Ephremides, A.: Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks. IEEE Trans. Autom. Control 4, 1936–1948 (1992) CrossRef

13.

Andrews, M., Kumaran, K., Ramanan, K., Stolyar, A.L., Vijayakumar, R., Whiting, P.: Scheduling in a queueing system with asynchronously varying service rates. Probab. Eng. Inf. Sci. 14, 191–217 (2004)

14.

Bui, L., Srikant, R., Stolyar, A.L.: Novel architectures and algorithms for delay reduction in back-pressure scheduling and routing. In: Proc. IEEE Infocom, pp. 2936–2940 (2009)

15.

Neely, M.J.: Delay analysis for maximal scheduling with flow control in wireless networks with bursty traffic. IEEE/ACM Trans. Netw. 17(4), 1146–1159 (2009) CrossRef

16.

Lin, X., Shroff, N., Srikant, R.: A tutorial on cross-layer optimization in wireless networks. IEEE J. Sel. Areas Commun. 24(8), 1452–1463 (2006) CrossRef

17.

Bui, L., Srikant, R., Stolyar, A.L.: Optimal resource allocation for multicast flows in multihop wireless networks. In: Proc. Ann. ACM SIGMETRICS/Performance Evaluation Review Conf, vol. 35(3), p. 43 (2007)

18.

Lin, L., Shroff, N.B., Srikant, R.: Energy-aware routing in sensor networks: a large system approach. Ad Hoc Netw. 5(6), 818–831 (2007) CrossRef

19.

Ying, L., Shakkottai, S., Reddy, A.: On combining shortest-path and back-pressure routing over multihop wireless networks. In: Proc. IEEE Infocom, pp. 1674–1682 (2009)

20.

Stolyar, A.L.: Maximizing queueing network utility subject to stability: greedy primal–dual algorithm. Queueing Syst. 50(4), 401–457 (2005) CrossRef

21.

Jiang, L., Shah, D., Shin, J., Walrand, J.C.: Distributed random access algorithm: scheduling and congestion control. CoRR (2009). arXiv:0907.1266

22.

Georgiadis, L., Neely, M.J., Tassiulas, L.: Resource allocation and cross-layer control in wireless networks. Found. Trends Netw. 1, 1–144 (2006) CrossRef

23.

Akyol, U., Andrews, M., Gupta, P., Hobby, J.D., Saniee, I., Stolyar, A.L.: Joint scheduling and congestion control in mobile ad hoc networks. In: Proc. IEEE Infocom, pp. 619–627 (2008)

24.

Ryu, J., Bhargava, V., Paine, N., Shakkottai, S.: Design, implementation and evaluation of back-pressure routing/rate control for intermittently connected networks. In: ACM Int. Conf. on Mobile Computing and Networking (MobiCom) (2011)

25.

Moeller, S., Sridharan, A., Krishnamachari, B., Gnawali, O.: Routing without routes: the backpressure collection protocol. In: Internat. Workshop on Inform. Processing in Sensor Networks (IPSN), pp. 279–290 (2010)

26.

Zhao, H., Xia, C.H., Liu, Z., Towsley, D.: A unified modeling framework for distributed resource allocation of general fork and join processing networks. In: Proc. Ann. ACM SIGMETRICS Conf. (2010)

27.

Jiang, L., Walrand, J.C.: Stable and utility-maximizing scheduling for stochastic processing networks. In: Proc. Allerton Conf. Communication, Control, and Computing (2009)

28.

Massoulié, L., Twigg, A., Gkantsidis, C., Rodriguez, P.: Randomized decentralized broadcasting algorithms. In: Proc. IEEE Infocom, pp. 1073–1081 (2007)

29.

Kowshik, H., Kumar, P.R.: Zero-error function computation in sensor networks. In: Proc. Conf. on Decision and Control, pp. 3787–3792 (2009)

30.

Madden, S., Franklin, M.J., Hellerstein, J.M., Hong, W.: TAG: a Tiny AGgregation service for ad hoc sensor networks. In: SIGOPS Oper. Syst. Rev, vol. 36, pp. 131–146 (2002)

31.

Edmonds, J.: Edge-Disjoint Branchings. Combinatorial Algorithms (1972)

Titel: Towards a queueing-based framework for in-network function computation
verfasst von: Siddhartha Banerjee
Piyush Gupta
Sanjay Shakkottai
Publikationsdatum: 01.12.2012
Verlag: Springer US
Erschienen in: Queueing Systems / Ausgabe 3-4/2012
Print ISSN: 0257-0130
Elektronische ISSN: 1572-9443
DOI: https://doi.org/10.1007/s11134-012-9296-8

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 3-4/2012

Controlled mobility in stochastic and dynamic wireless networks

Editorial introduction

On distributed scheduling with heterogeneously delayed network-state information

Scheduling with pairwise XORing of packets under statistical overhearing information and feedback

Distributed caching over heterogeneous mobile networks

Asymptotically tight steady-state queue length bounds implied by drift conditions

Premium Partner