×

Transport schemes for topology-transparent scheduling. (English) Zbl 1146.90339

Summary: Transport protocols provide reliable, end-to-end communication between a source and a destination in a network. The Transmission Control Protocol (TCP) uses backward error correction, where the destination explicitly returns feedback to the source. Forward error correction (FEC) can also be used for transport; here the source includes enough redundancy in the encoding symbols to allow the destination to decode the message. In this paper, we compare the performance of two transport schemes, TCP and LT, a scheme based on rateless FEC codes, in a wireless ad hoc network when topology-transparent scheduling is used for channel access. These schedules are derived from cover-free families, a type of combinatorial design. They provide a mechanism to guarantee collision-free communication between any two nodes provided that each of the \(N\) nodes of the network has at most a specified number \(D\) of active (transmitting) neighbours. We find that LT outperforms TCP in more strenuous network conditions.

MSC:

90B06 Transportation, logistics and supply chain management
90B10 Deterministic network models in operations research
90B35 Deterministic scheduling theory in operations research
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bloemer J, Kalfane M, Karpinski M, Karp R, Luby M, Zuckerman D (1995) An XOR-based erasure-resilient coding scheme. Technical report TR-95-048, ICSI, August 1995
[2] Chlamtac I, Faragó A (1994) Making transmission schedules immune to topology changes in multi-hop packet radio networks. IEEE/ACM Trans Netw 2(1):23–29 · doi:10.1109/90.282605
[3] Chlamtac I, Pinter S (1987) Distributed node organization algorithm for channel access in a multi-hop packet radio network. IEEE Trans Comput 36(6):728–737 · doi:10.1109/TC.1987.1676965
[4] Chu W, Colbourn CJ, Syrotiuk VR (2004) Topology transparent scheduling, synchronization and maximum delay. In: Proceedings of the 18th international parallel and distributed processing symposium (IPDPS’04), April 2004, pp 223–228
[5] Chu W, Colbourn CJ, Syrotiuk VR (2006a) Slot synchronized topology-transparent scheduling for sensor networks. Comput Commun 29(4):421–428 · Zbl 05396307 · doi:10.1016/j.comcom.2004.12.026
[6] Chu W, Colbourn CJ, Syrotiuk VR (2006b) The effects of synchronization on topology-transparent scheduling. Wirel Netw 12:681–690 · Zbl 05075919 · doi:10.1007/s11276-006-6528-z
[7] Colbourn CJ, Syrotiuk VR (2005) Cover-free families and topology-transparency. Bayreuther Math Schr 73:86–106
[8] Colbourn CJ, Dinitz JH, Stinson DR (1999) Applications of combinatorial designs to communications, cryptography, and networking. In: Lamb JD, Preece DA (eds) Surveys in Combinatorics. Cambridge University Press, Cambridge, pp 37–100 · Zbl 0972.94052
[9] Colbourn CJ, Syrotiuk VR, Ling ACH (2003) Steiner systems for topology-transparent access control in MANETs. In: Proceedings of the second international conference on ad hoc networks and wireless (Ad hoc Now’03), October 2003, pp 247–258
[10] Colbourn CJ, Ling ACH, Syrotiuk VR (2004) Cover-free families and topology-transparent scheduling for MANETs. Des Codes Cryptogr 32(1–3):65–96 · Zbl 1053.94024 · doi:10.1023/B:DESI.0000029213.74879.e0
[11] Digital Fountain (2004) Breakthrough reliable transport technology for data and live streaming delivery over imperfect networks. Technology licensing white paper. Available at http://www.digitalfountain.com
[12] Du DZ, Hwang FK (2000) Combinatorial group testing and its applications. 2nd edn. World Scientific, Singapore
[13] Dukes PJ, Colbourn CJ, Syrotiuk VR (2006) Topology-transparent schedules for energy limited ad hoc networks. In: Proceedings of the IEEE international workshop on foundations and algorithms for wireless networking (FAWN’06), March 2006, pp 85–90
[14] Dukes PJ, Colbourn CJ, Syrotiuk VR (2007) Directed complete bipartite graph decompositions: indirect constructions. Discret Math (to appear)
[15] D’yachkov A, Vilenkin P, Macula A, Torney D (2002) Families of finite sets in which no intersection of sets is covered by the union of s others. J Comb Theory Ser A 99:195–218 · Zbl 1020.94027 · doi:10.1006/jcta.2002.3257
[16] Erdös P, Frankl P, Füredi Z (1985) Families of finite sets in which no set is covered by the union of r others. Israel J Math 51:79–89 · Zbl 0587.05021 · doi:10.1007/BF02772959
[17] Hedayat AS, Sloane NJA, Stufken J (1999) Orthogonal arrays, theory and applications. Springer, Berlin · Zbl 0935.05001
[18] IEEE Standards Committee (1996) Wireless LAN medium access control (MAC) and physical layer (PHY) specifications. In: IEEE 802.11 standard. IEEE, New York, ISBN 1-55937-935-9
[19] Jacobson V (1988) Congestion avoidance and control. In: Proceedings SIGCOMM, August 1988, pp 314–329
[20] Johnson D, Maltz D (1996) Dynamic source routing in ad hoc wireless networks. In: Imelinsky T, Korth H (eds) Mobile computing. Kluwer Academic, Dordrecht, pp 153–181
[21] Ju J-H, Li VOK (1998) An optimal topology-transparent scheduling method in multihop packet radio networks. IEEE/ACM Trans Netw 6(3):298–306 · doi:10.1109/90.700893
[22] Luby MG (2002) LT codes. In: Proceedings of the 43rd symposium on foundations of computer science (FOCS’02), November 2002, pp 271–280
[23] Postel JB (1981) RFC 793: Transmission control protocol. ftp://ds.internic.net/rfc/rfc793.txt . September 1981
[24] Rizzo L (1997) Effective erasure codes for reliable computer communication protocols. Comput Commun Rev 27(2):24–36 · doi:10.1145/263876.263881
[25] Ruszinkó M (1994) On the upper bound of the size of the r-cover-free families. J Comb Theory Ser A 66:302–310 · Zbl 0798.05071 · doi:10.1016/0097-3165(94)90067-1
[26] Stinson DR, Wei R, Zhu L (2000) Some new bounds for cover-free families. J Comb Theory Ser A 90:224–234 · Zbl 0948.05055 · doi:10.1006/jcta.1999.3036
[27] Syrotiuk VR, Colbourn CJ, Ling ACH (2003) Topology-transparent scheduling for MANETs using orthogonal arrays. In: Proceedings of the DIALM-POMC joint workshop on foundations of mobile computing, September 2003, pp 43–49
[28] The Virtual InterNetwork Testbed (VINT) Project (1995) The network simulator–ns-2. http://www.isi.edu/nsnam/vint/index.html
[29] Zhu C, Corson S (1998) A five-phase reservation protocol (FPRP) for mobile ad hoc networks. In: Proceedings of 17th annual joint conference of the IEEE computer and communication societies (Infocom’98), March–April 1998, pp 315–321 · Zbl 0972.68777
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.