Analyzing History Quality for Routing Purposes in Opportunistic Network Using Max-Flow

Muhammad Arshad Islam, Marcel Waldvogel

Distributed Systems Laboratory, University of Konstanz, Konstanz, Germany.
Faculty of Computer Sciences and Engineering, GIK Institute, Topi, Pakistan.

DOI: 10.4236/wet.2012.33020                

Abstract

Most of the existing opportunistic network routing protocols are based on some type of utility function that is directly or indirectly dependent on the past behavior of devices. The past behavior or history of a device is usually referred to as contacts that the device had in the past. Whatever may be the metric of history, most of these routing protocols work on the realistic premise that node mobility is not truly random. In contrast, there are several oracles based methods where such oracles assist these methods to gain access to information that is unrealistic in the real world. Although, such oracles are unrealistic, they can help to understand the nature and behavior of underlying networks. In this paper, we have analyzed the gap between these two extremes. We have performed max-flow computations on three different opportunistic networks and then compared the results by performing max-flow computations on history generated by the respective networks. We have found that the correctness of the history based prediction of history is dependent on the dense nature of the underlying network. Moreover, the history based prediction can deliver correct paths but cannot guarantee their absolute reliability.

Keywords

Opportunistic Networks; Delay Tolerant Networks; Routing Protocols; Max-Flow; Simulation; Modified Dijk-Stra Algorithm

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	I. Bisio and M. Marchese, “Congestion Aware Routing Strategies for dtn-Based Interplanetary Networks,” Proceedings of the Global Communi-cations Conference, New Orleans, 30 November-4 December 2008, pp. 1-5.
[2]	S. Guo, M. Derakhshani, M. H. Falaki, U. Ismail, R. Luk, E. A. Oliver, S. U. Rahman, A. Seth, M. A. Zaharia and S. Keshav, “Design and Implementation of the Kiosknet System,” Computer Networks, Vol. 55, No. 1, 2011, pp. 264-281. doi:10.1016/j.comnet.2010.08.001
[3]	A. Keranen and J. Ott, “Increasing Reality for dtn Protocol Simulations,” Helsinki University of Technology, Helsinki, 2007.
[4]	J. Burgess, B. Gallagher, D. Jensen and B. Levine, “Maxprop: Routing for Vehicle-Based Disruption-Tolerant Networking,” Proceedings of IEEE Infocom, Barcelona, 23-29 April 2006.
[5]	M. Islam and M. Waldvogel, “Optimizing Message Delivery in Mobile-Opportunistic Networks,” Internet Communications, 2011 Baltic Congress on Future, Riga, 17 February 2011, pp. 134-141. doi:10.1109/BCFIC-RIGA.2011.5733212
[6]	X. Zhuo, Q. Li, W. Gao, G. Cao and Y. Dai, “Contact Duration Aware Data Replication in Delay Tolerant Networks,” IEEE International Conference on Network Protocols, Vancouver, 17-20 October 2011, pp. 236-245.
[7]	S. Jain, K. Fall and R. Patra, “Routing in a Delay Tolerant Network,” Proceedings of SIGCOMM 2004, ACM Press, New York, 2004, pp. 145-158. doi:10.1145/1015467.1015484
[8]	M. A. Islam and M. Waldvogel, “Questioning Flooding as a Routing Benchmark in Opportunistic Networks,” 2011 Baltic Congress on Future Internet Communications, Riga, 17 February 2011, pp. 128-133. doi:10.1109/BCFIC-RIGA.2011.5733215
[9]	L. Lilien, Z. H. Kamal and A. Gupta, “Opportunistic Networks: Challenges in Specializing the p2p Paradigm,” International Workshop on Database and Expert Systems Applications, Krakow, 4-8 September 2006, pp. 722-726.
[10]	J. Z. J. Liu and H. G. Gong, “Preference Location-Based Routing in Delay Tolerant Networks,” International Journal of Digital Content Technology and its Applications, Vol. 5, No. 4, 2011, pp. 468-474.
[11]	B. Burns, O. Brock and B. N. Levine, “Mv Routing and Capacity Building in Disruption Tolerant Networks,” Proceedings of IEEE Infocom, Miami, 13-17 March 2005.
[12]	A. Lindgren, A. Doria, J. Lindblom and M. Ek, “Networking in the Land of Northern Lights: Two Years of Experiences from dtn System Deployments,” Proceedings of the 2008 ACM Workshop on Wireless Networks and Systems for Developing Regions, ACM, New York, 2008, pp. 1-8. doi:10.1109/TMC.2007.1016
[13]	E. P. C. Jones, L. Li and J. K. Schmidtke, “Practical Routing in Delay-Tolerant Networks,” IEEE Transactions on Mobile Computing, Vol. 6, No. 8, 2007, pp. 943-959.
[14]	Y. Wang, S. Jain, M. Martonosi and K. Fall, “Erasure-Coding Based Routing for Opportunistic Networks,” ACM Workshop on Delay Tolerant Networking, Philadelphia, 26 August 2005.
[15]	P. Costa, C. Mascolo, M. Musolesi and G. P. Picco, “Socially-Aware Routing for Publish-Subscribe in Delay-Tolerant Mobile Ad Hoc Networks,” IEEE Journal on Selected Areas in Communications, Vol. 26, No. 5, 2008, pp. 748-760. doi:10.1109/JSAC.2008.080602
[16]	A. Seraghiti, S. Delpriori, E. Lattanzi and A. Bogliolo, “Self-Adapting Maxflow Routing Algorithm for wsns: Practical Issues and Simulation-Based Assessment,” Proceedings of the 5th International Conference on Soft Computing as Transdisciplinary Science and Technology, Ser, ACM, New York, 2008, pp. 688-693.
[17]	X. Huang, J. Wang and Y. Fang, “Achieving Maximum Flow in Interference-Aware Wireless Sensor Networks with Smart Antennas,” Ad Hoc Networks, Vol. 5, No. 6, 2007, pp. 885-896. doi:10.1016/j.adhoc.2007.02.003
[18]	T. X. Brown, H. N. Gabow and Q. Zhang, “Maximum Flow-Life Curve for a Wireless Ad Hoc Network,” Proceedings of the 2nd ACM International Symposium on Mobile Ad Hoc Networking & Computing, ACM, New York, 2001, pp. 128-136.
[19]	S. K. Dandapat, B. Mitra, N. Ganguly and R. R. Choudhury, “Fair Bandwidth Allocation in Wireless Network Using Max-Flow,” SIGCOMM—Computer Communication Review, Vol. 41, No. 4, 2010, pp. 22-24.
[20]	R. K. Ahuja, T. L. Magnanti and J. B. Orlin, “Network Flows: Theory, Algorithms, and Applications,” Prentice Hall, Upper Saddle River, 1993.
[21]	N. Eagle and A. S. Pentland, “CRAWDAD Data Set Mit/Reality (v. 2005-07-01),” 2005. http://crawdad.cs.dartmouth.edu/mit/reality
[22]	M. Balazinska and P. Castro, “CRAWDAD Data Set IBM/Watson (v. 2003-02-19),” 2003. http://crawdad.cs.dartmouth.edu/ibm/watson
[23]	A. Chaintreau, P. Hui, J. Crowcroft, C. Diot, R. Gass and J. Scott, “Impact of Human Mobility on the Design of Opportunistic Forwarding Algorithms,” Proceedings of IEEE Infocom, Barcelona, 23-29 April 2006.
[24]	D. R. F. Ford, “Maximal Flow through a Network,” Canadian Jounral of Mathematics, Vol. 8, 1956, pp. 399-404. doi:10.4153/CJM-1956-045-5
[25]	J. S. S. Syed-Abdul, et al., “Study on the Potential for Delay Tolerant Networks by Health Workers in Low Resource Settings,” Computer Methods and Programs in Biomedicine, 2011, in Press. doi:10.1016/j.cmpb.2011.11.004