Video sensor networks operate on stringent requirements
of latency. Packets have a deadline within which they have
to be delivered. Violation of the deadline causes a packet to be
treated as lost and the loss of packets ultimately affects the quality
of the application. Network latency is typically a function of many
interacting components. In this paper, we propose ways of reducing
the forwarding latency of a packet at intermediate nodes. The
forwarding latency is caused by a combination of processing delay
and queueing delay. The former is incurred in order to determine the
next hop in dynamic routing. We show that unless link failures in a
very specific and unlikely pattern, a vast majority of these lookups
are redundant. To counter this we propose source routing as the
routing strategy. However, source routing suffers from issues related
to scalability and being impervious to network dynamics. We propose
solutions to counter these and show that source routing is definitely
a viable option in practical sized video networks. We also propose a
fast and fair packet scheduling algorithm that reduces queueing delay
at the nodes. We support our claims through extensive simulation on
realistic topologies with practical traffic loads and failure patterns.
[1] "http://www.airport-int.com/categories/surveillancesolutions/
peoplemover-project-brings-21st-century-surveillance-system-
to-dallas-airport.asp."
[2] "http://www.tropos.com/pdf/case studies/tropos casestudy new orleans.pdf."
[3] A. Demers, S. Keshav, and S. Shenker, "Analysis and simulation of a
fair queuing algorithm," in SIGCOMM, 1989.
[4] J. B. H. and Zhang, "Wf2q : Worst case fair weighted fair queuing," in
INFOCOM, 1996.
[5] M. Shreedhar and G. Varghese, "Efficient fair queuing using deficit
round robin," in SIGCOMM, 1995.
[6] N. Figueira and J. Pasquale, "Leave-in-time: A new service discipline
for real-time communications in a packet-switching network," in SIGCOMM,
1995.
[7] S. Golestani, "A self-clocked fair queueing scheme for broadband
applications," in INFOCOM, 1994.
[8] G. Chuanxiong, "An o(1) time complexity packet scheduler for flows in
multi-service packet networks," in SIGCOMM, 2001.
[9] R. Braden, D. Clark, and S. Shenker, "Integrated services in the internet
architecture: an overview," Internet RFC 1633, June 1994.
[10] S. Blake, D. Black, M. Carlson, E. Davies, Z. Wang, and W. Weiss, "An
architecture for differentiated services," Internet RFC 2475, December
1998.
[11] E. Rosen, A. Viswanathan, and R. Callon, "Multiprotocol label switching
architecture," Internet draft ¡draft-ietf-mpls-arch-01.txt¿, March 1998.
[12] X. Xipeng and L. Ni, "Internet qos: a big picture," IEEE Network, March
1999.
[13] A. Parekh and R. Gallager, "A generalized processor sharing approach
to flow control in integrated services networks: The single node case,"
IEEE/ACM Transactions on Networking, vol. 1, 1993.
[14] J. Xu and R. Lipton, "On fundamental tradeoffs between delay bounds
and computational complexity in packet scheduling algorithms," in
SIGCOMM, 2002.
[15] L. Lenzini, E. Mingozzi, and G. Stea, "Aliquem: A novel drr implementation
to achieve better latency and fairness at o(1) complexity," in
IWQoS, 2002.
[16] S. .Cheung and C. Pencea, "Bsfq: Bin sort fair queuing," in INFOCOM,
2002.
[17] S. Ramabhadran and J. Pasquale, "The stratified round robin scheduler:
design, analysis and implementation," IEEE/ACM Transactions on
Networking (TON), vol. 14, no. 6, December 2006.
[18] T. Fuhrmann, "The use of scalable source routing for sensor networks,"
in 2nd IEEE workshop on Embedded Sensor Networks, 2005.
[19] V. Hadimani and R. Hansdah, "An efficient distributed scheme for
source routing protocol in communication networks," Lecture notes in
Computer Science, vol. 3347, November 2005.
[20] C. Glass and L. Ni, "The turn model for adaptive routing," in ISCA,
1992.
[21] "Moving picture experts group, october 2006
http://www.chiariglione.org/mpeg."
[22] "Dolby laborotories inc. www.dolby.com."
[23] A. Markopoulou, G.Iannaccone, S.Bhattacharyya, C.N.Chuah, Y.Ganjali,
and C.Diot, "Characterization of failures in an operational ip backbone
network," IEEE Trans. on Networking, vol. 16, October 2008.
[24] D. J. Watts and S. H. Strogatz, "Collective dynamics of small world
networks," Nature, vol. 393, no. 6684, pp. 440-442, June 1992.
[25] "http://www.caida.org/research/topology/as core network/."
[26] M. et al., Phys. Rev. E, vol. 64, no. 026118, 2001.
[27] A. Fronczak, P. Fronczak, and J. A. Holyst, "Average path length in
random networks," Phys. Rev. E, 2002.
[28] M. Stumpf and C. Wiuf, "Sampling properties of random graphs: The
degree distribution," Phys. Rev. E, vol. 72, 2005.
[29] H. Seyed-allaei, B. Ginestra, and M. Marsili, "Scale-free networks with
an exponent less than two," Phys. Rev. E, vol. 73, 2005.
[30] R. Cohen and S. Havlin, "Scale-free networks are ultrasmall," Phys. Rev.
E, vol. 90, 2003.
[31] M. Ishizuka and M. Aida, "The reliability performance of wireless
sensor networks configured by power-law and other forms of stochastic
node placement," IEICE Trans. on Communications, vol. E87-B, no. 9,
pp. 2511-2520, September 2004.
[32] J. Davidson, M. Bhatia, S. Kalidindi, S. Mukherjee, and J. Peters, VoIP:
An In-Depth Analysis. Cisco Press, 2006.
[33] P. Lieshout, M. Mandjes, and S. Borst, "Gps scheduling:selection of
optimal weights and comparison with strict priorities," in ACM SIGMETRICS
Performance Evaluation Review, 2006.
[34] A. Ghosh and T. Givargis, "A software architecture for accessing data
in sensor networks," in INSS, 2008.
[35] R. Jain, The Art of Computer Performance Analysis. Wiley, 1991.
[1] "http://www.airport-int.com/categories/surveillancesolutions/
peoplemover-project-brings-21st-century-surveillance-system-
to-dallas-airport.asp."
[2] "http://www.tropos.com/pdf/case studies/tropos casestudy new orleans.pdf."
[3] A. Demers, S. Keshav, and S. Shenker, "Analysis and simulation of a
fair queuing algorithm," in SIGCOMM, 1989.
[4] J. B. H. and Zhang, "Wf2q : Worst case fair weighted fair queuing," in
INFOCOM, 1996.
[5] M. Shreedhar and G. Varghese, "Efficient fair queuing using deficit
round robin," in SIGCOMM, 1995.
[6] N. Figueira and J. Pasquale, "Leave-in-time: A new service discipline
for real-time communications in a packet-switching network," in SIGCOMM,
1995.
[7] S. Golestani, "A self-clocked fair queueing scheme for broadband
applications," in INFOCOM, 1994.
[8] G. Chuanxiong, "An o(1) time complexity packet scheduler for flows in
multi-service packet networks," in SIGCOMM, 2001.
[9] R. Braden, D. Clark, and S. Shenker, "Integrated services in the internet
architecture: an overview," Internet RFC 1633, June 1994.
[10] S. Blake, D. Black, M. Carlson, E. Davies, Z. Wang, and W. Weiss, "An
architecture for differentiated services," Internet RFC 2475, December
1998.
[11] E. Rosen, A. Viswanathan, and R. Callon, "Multiprotocol label switching
architecture," Internet draft ¡draft-ietf-mpls-arch-01.txt¿, March 1998.
[12] X. Xipeng and L. Ni, "Internet qos: a big picture," IEEE Network, March
1999.
[13] A. Parekh and R. Gallager, "A generalized processor sharing approach
to flow control in integrated services networks: The single node case,"
IEEE/ACM Transactions on Networking, vol. 1, 1993.
[14] J. Xu and R. Lipton, "On fundamental tradeoffs between delay bounds
and computational complexity in packet scheduling algorithms," in
SIGCOMM, 2002.
[15] L. Lenzini, E. Mingozzi, and G. Stea, "Aliquem: A novel drr implementation
to achieve better latency and fairness at o(1) complexity," in
IWQoS, 2002.
[16] S. .Cheung and C. Pencea, "Bsfq: Bin sort fair queuing," in INFOCOM,
2002.
[17] S. Ramabhadran and J. Pasquale, "The stratified round robin scheduler:
design, analysis and implementation," IEEE/ACM Transactions on
Networking (TON), vol. 14, no. 6, December 2006.
[18] T. Fuhrmann, "The use of scalable source routing for sensor networks,"
in 2nd IEEE workshop on Embedded Sensor Networks, 2005.
[19] V. Hadimani and R. Hansdah, "An efficient distributed scheme for
source routing protocol in communication networks," Lecture notes in
Computer Science, vol. 3347, November 2005.
[20] C. Glass and L. Ni, "The turn model for adaptive routing," in ISCA,
1992.
[21] "Moving picture experts group, october 2006
http://www.chiariglione.org/mpeg."
[22] "Dolby laborotories inc. www.dolby.com."
[23] A. Markopoulou, G.Iannaccone, S.Bhattacharyya, C.N.Chuah, Y.Ganjali,
and C.Diot, "Characterization of failures in an operational ip backbone
network," IEEE Trans. on Networking, vol. 16, October 2008.
[24] D. J. Watts and S. H. Strogatz, "Collective dynamics of small world
networks," Nature, vol. 393, no. 6684, pp. 440-442, June 1992.
[25] "http://www.caida.org/research/topology/as core network/."
[26] M. et al., Phys. Rev. E, vol. 64, no. 026118, 2001.
[27] A. Fronczak, P. Fronczak, and J. A. Holyst, "Average path length in
random networks," Phys. Rev. E, 2002.
[28] M. Stumpf and C. Wiuf, "Sampling properties of random graphs: The
degree distribution," Phys. Rev. E, vol. 72, 2005.
[29] H. Seyed-allaei, B. Ginestra, and M. Marsili, "Scale-free networks with
an exponent less than two," Phys. Rev. E, vol. 73, 2005.
[30] R. Cohen and S. Havlin, "Scale-free networks are ultrasmall," Phys. Rev.
E, vol. 90, 2003.
[31] M. Ishizuka and M. Aida, "The reliability performance of wireless
sensor networks configured by power-law and other forms of stochastic
node placement," IEICE Trans. on Communications, vol. E87-B, no. 9,
pp. 2511-2520, September 2004.
[32] J. Davidson, M. Bhatia, S. Kalidindi, S. Mukherjee, and J. Peters, VoIP:
An In-Depth Analysis. Cisco Press, 2006.
[33] P. Lieshout, M. Mandjes, and S. Borst, "Gps scheduling:selection of
optimal weights and comparison with strict priorities," in ACM SIGMETRICS
Performance Evaluation Review, 2006.
[34] A. Ghosh and T. Givargis, "A software architecture for accessing data
in sensor networks," in INSS, 2008.
[35] R. Jain, The Art of Computer Performance Analysis. Wiley, 1991.
@article{"International Journal of Information, Control and Computer Sciences:50669", author = "Arijit Ghosh and Tony Givargis", title = "Improving Packet Latency of Video Sensor Networks", abstract = "Video sensor networks operate on stringent requirements
of latency. Packets have a deadline within which they have
to be delivered. Violation of the deadline causes a packet to be
treated as lost and the loss of packets ultimately affects the quality
of the application. Network latency is typically a function of many
interacting components. In this paper, we propose ways of reducing
the forwarding latency of a packet at intermediate nodes. The
forwarding latency is caused by a combination of processing delay
and queueing delay. The former is incurred in order to determine the
next hop in dynamic routing. We show that unless link failures in a
very specific and unlikely pattern, a vast majority of these lookups
are redundant. To counter this we propose source routing as the
routing strategy. However, source routing suffers from issues related
to scalability and being impervious to network dynamics. We propose
solutions to counter these and show that source routing is definitely
a viable option in practical sized video networks. We also propose a
fast and fair packet scheduling algorithm that reduces queueing delay
at the nodes. We support our claims through extensive simulation on
realistic topologies with practical traffic loads and failure patterns.", keywords = "Sensor networks, Packet latency, Network design, Networkperformance.", volume = "3", number = "4", pages = "903-14", }
