Weitere Artikel dieser Ausgabe durch Wischen aufrufen
The author declares that he has no competing interests.
Mustafa Arisoylu received the PhD degree from University of California San Diego (UCSD), in Electrical and Computer Engineering in 2006. He received his MS and BS degrees from Bilkent University, Turkey, both in Electrical Engineering in 1999 and 2001, respectively. Dr. Arisoylu conducted research on resource allocation and performance optimization in communication networks and authored several publications. In 2004, he was a visiting researcher at Los Alamos National Laboratory, (LANL). Dr. Arisoylu worked as a researcher at Cal-IT2 (California Institute for Telecommunications and Information Technology), designing and architecting advanced multi-hop wireless mesh networks for emergency response applications. Dr. Arisoylu joined a startup spinoff company from Cal-IT2 / UCSD, at its seed stage where he served as Research Scientist and Vice President of Research and Development. He later joined the systems design group at Ericsson Inc. Research and Development Center in Boulder, Colorado. Currently, he is serving as a Senior Engineering Manager R&D at system architecture group at Ericsson Silicon Valley Research and Development Center in San Jose, CA.
In this paper, we promote the packet function (e.g., packet size) -aware extension of the Dijkstra algorithm (i.e., PFA_SPF) as a base algorithm where any routing protocol can evolve it and integrate it with appropriate routing metrics. In particular, we propose a generic algorithm for packet function-aware path setup for multi-hop networks. The algorithm is based on a generic and novel extension of the classical Dijkstra algorithm in which the cost of each link is a non-negative-valued function of packet parameter(s) (e.g., packet size) rather than a scalar value. The algorithm minimizes the sum of the cost functions (e.g., total transmission delay or total energy consumption) experienced by each packet (e.g., maximizing the throughput) from the source to the destination node. We did initial analysis based on simulation of the algorithm for various random multi-hop wireless networks (e.g., 802.11), utilizing realistic link delay models. Finally, we demonstrate the initial significant potential performance improvements of our algorithm over the existing prior art.
X Wu, W Li, F Liu, H Yu, in IEEE International Conference on Wavelet Active Media Technology and Information Processing (ICWAMTIP). Packet size distribution of typical Internet applications, (2012).
C Fraleigh, S Moon, B Lyles, C Cotton, M Khan, D Moll, R Rockell, T Seely, C Diot, Packet-level traffic measurements from the Sprint IP backcone. IEEE Network. 17(6), 6–16 (2003). CrossRef
R Sinha, C Papadopulos, J Heidemann, Internet packet size distributions: some observations, ISI-TR-2007-643. USC/Information Sciences Institute Technical Report, (2007).
Y Cheng, V Ravindran, A Leon-Garcia, in 26th IEEE International Conference on Computer Communications, INFOCOM. Internet traffic characterization using packet-pair probing, (2007).
J Downey, Understanding VoIP packet sizing and traffic engineering, in SCRE Cable-tec Expo, White Paper, (June 2005).
K Thompson, G Miller, R Wilder, Wide-area internet traffic patterns and characteristics. IEEE Network. 11(6), 10–23 (1997). CrossRef
A Mena, J Heidemann, in Nineteenth Annual Joint Conference of the IEEE Computer and Communications Societies, INFOCOM. An empirical study of real audio traffic, (2000).
Sun, Jun, Y Wen, L Zheng, in Proceedings IEEE International Conference on Computer Communications, INFOCOM. On file-based content distribution over wireless networks via multiple paths: coding and delay trade-off, (2011).
JW Byers, M Luby, M Mitzenmacher, A digital fountain approach to asynchronous reliable multicast. IEEE Journal on Selected Areas in Communications, JSAC. 20(8), 1528–1540 (2002). CrossRef
JW Byers, M Lubyy, M Mitzenmacher, A Rege, in Proc. Special Interest Group on Data Communications Conference ACM SIGCOMM. A digital fountain approach to reliable distribution of bulk data, (1998).
S Floyd, et al., in Proceedings of Special Interest Group on Data Communications Conference, ACM SIGCOMM. Equation-based congestion control for unicast applications (SwedenStockholm, 2000), pp. 43–56.
J Padhye, D Kurose, R Towsley, in Proc. Int’l. Wksp. Network and Op. Sys. Support for Digital Audio and Video, NOSSDAV. A model based TCP-friendly rate control protocol, (1999).
S Cen, PC Cosman, GM Voelker, End-to-end differentiation of congestion and wireless losses. Netw. IEEE/ACM Trans. 11(5), 703–717 (2003). CrossRef
M Arisoylu, T Javidi, RL Cruz, in IEEE International Conference on Communications, ICC. End-to-end and MAC-layer fair rate assignment in interference-limited wireless access networks, (2006).
C Kim, Y Ko, NH Vaidya, in IEEE Military Communications Conference, MILCOM. Link-state routing protocol for multi-channel multi-interface wireless networks, (2008).
M Heusse, F Rousseau, GB Sabbatel, A Duda, in Twenty-Second Annual Joint Conference of the IEEE Computer and Communications, INFOCOM. Performance anomaly of 802.11b, (2003).
P Liu, Z Tao, S Panwar, in IEEE International Conference on Communications, ICC. A cooperative MAC protocol for wireless local area networks, (2005).
T Korakis, S Narayanan, A Bagri, S Panwar, in IEEE International Conference on Communications, ICC. Implementing a cooperative MAC protocol for wireless LANs, (2006).
J Dunn, M Neufeld, A Sheth, D Grunwald, J Bennett, in IEEE First International Conference on Broadband Networks, BroadNets. A practical cross-layer mechanism for fairness in 802.11 networks, (2004).
DSJ De Couto, D Aguayo, J Bicket, R Morris, A high throughput path metric for multi-hop wireless routing. Journal Wireless Networks - Special issue: Selected papers from ACM MobiCom 2003. 11(4), 419–434 (2005). CrossRef
M Arisoylu, S Ergut, RL Cruz, R Rao, in IEEE Consumer Communications and Networking Conference, CCNC. Packet size aware path setup for wireless networks, (2008).
C Pepin, UC Kozat, AS Ramprashad, in 4th International Symposium on Modeling and Optimization in Mobile, Ad Hoc and Wireless Networks, IEEE WiOpt. A joint traffic shaping and routing approach to improve the performance of 802.11 mesh networks, (2006).
B Awerbuch, D Holmer, H Rubens, High throughput route selection in multi-rate ad hoc wireless networks, Wireless On-demand Network Systems (WONS), (2004).
DHB Awerbuch, H Rubens, The medium time metric: High throughput route selection in multirate ad hoc wireless networks. Mobile Networks and Applications. 11(2), 253–266 (2006). CrossRef
M Arisoylu, RL Cruz, T Javidi, in Proceedings of the Allerton Conference on Communications, Control, and Computing. Rate assignment in micro-buffered high speed networks, (2005).
R Perlman, Interconnections: bridges, routers, switches and Internet-working protocols, 2nd Ed (Addison Wesley, 1999).
D Bertsekas, R Gallager, Data Networks, 2nd edn. (Prentice Hall, Englewood Cliffs, New Jersey, 1992). MATH
J Moy, OSPF version 2, RFC 2328 (1998) http://ietf.org/rfc/rfc2328.txt.
T Clausen, P Jacquet, A Laouiti, P Minet, P Muhlethaler, A Qayyum, L Viennot (Optimized link state routing protocol, draft MANET-IETF, 2002. http://www.ietf.org/internet-drafts/draft-ietfmanet-olsr-07.txt.
D Oran, OSI IS-IS Intra-domain routing protocol, RFC 1142 (1990) http://ietf.org/rfc/rfc1142.txt.
J Moy, OSPF, Anatomy of an Internet Routing Protocol (AddisonWesley, Boston, 1998).
R Murty, J Padhye, R Chandra, A Wolman, B Zill, in NSDI ’08: 5th USENIX Symposium on Networked Systems Design and Implementation. Designing high performance enterprise Wi-Fi networks, (2008).
A Raniwala, T Chiueh, in IEEE International Conference on Computer Communications INFOCOM. Architecture and algorithms for an IEEE 802.11-based multi-channel wireless mesh network (Miami, FL, 2005).
KN Ramachandran, EM Belding, KC Almeroth, MM Buddhikot, in IEEE International Conference on Computer Communications INFOCOM. Interference-aware channel assignment in multi-radio wireless mesh networks, (2006).
R Sivakumar, P Sinha, V Bharghavan, CEDAR: a core-extraction distributed ad hoc routing algorithm. IEE J. Selected Areas Commun. 17(8), 1454–1465 (1999). CrossRef
A Raha, SS Babu, MK Naskar, O Alfandi, Hogrefe D, in IEEE 5th International Conference on Advanced Networks and Telecommunication Systems (ANTS). Trust integrated link state routing protocol for wireless sensor networks (TILSRP), (2011).
A Sendonaris, E Erkip, B Aazhang, User cooperation diversity—Part I: system description. IEEE Trans. Commun. 51(11), 1927–1938 (2003). CrossRef
A Sendonaris, E Erkip, B Aazhang, User cooperation diversity—Part II: implementation aspects and performance analysis. IEEE Trans. Commun. 51(11), 1939–1948 (2003). CrossRef
DSJD Couto, D Aguayo, J Bicket, R Morris, in 9th annual international conference on mobile computing and networking (ACM MobiCom 03). A high-throughput path metric for multi-hop wireless networks, (2003).
D Aguayo, J Bicket, S Biswas, G Judd, R Morris, in Proceedings of Special Interest Group on Data Communications Conference, ACM SIGCOMM. Link-level measurements from an 802.11b mesh network, (2004).
R Draves, J Padhye, B Zill, in Proceedings of Special Interest Group on Data Communications Conference, ACM SIGCOMM. Comparison of routing metrics for static multi-hop wireless networks, (2004).
A Adya, P Bahl, J Padhye, A Wolman, L Zhou, in IEEE International Conference on Broadband Networks, BroadNets. A multi-radio unification protocol for ieee 802.11 wireless networks, (2004).
S Keshav, in Proceedings of Special Interest Group on Data Communications Conference, ACM SIGCOMM. A control-theoretic approach to flow control, (1991).
R Draves, J Padhye, B Zill, in annual international conference on mobile computing and networking in ACM MobiCom. Routing in multi-radio, multi-hop wireless mesh networks, (2004).
R Karrer, A Sabharwal, E Knightly, in ACM Workshop on Hot Topics in Networks (HotNets). Enabling large-scale wireless broadband: the case for TAPs, (2003).
D Aguayo, J Bicket, S Biswas, DD Couto, in annual international conference on mobile computing and networking MobiCom Poster. MIT roofnet: construction of a production quality ad-hoc network, (2003).
K Ramachandran, I Sheriff, E Belding, K Almeroth, in PAM’07 Proceedings of the 8th international conference on Passive and active network measurement. Routing stability in static wireless mesh networks, (2007).
K Fall, in Proceedings of Special Interest Group on Data Communications Conference, ACM SIGCOMM. A delay-tolerant network architecture for challenged Internets, (2003).
Y Zeng, et al., Directional routing and scheduling for green vehicular delay tolerant networks. Wireless Netw. 19(2), 161–173 (2013). CrossRef
T Spyropoulos, et al., Routing for disruption tolerant networks: taxonomy and design. Wireless Netw. 16(8), 2349–2370 (2010). CrossRef
A Vasilakos, et al., Delay tolerant networks: Protocols and applications (CRC Press, Boca Raton, 2012).
A Dvir, et al., Backpressure-based routing protocol for DTNs. ACM SIGCOMM Comput. Commun. Rev. 41(4), 405–406 (2011). MathSciNet
Li Peng, et al., in IEEE International Conference on Computer Communications INFOCOM. CodePipe: an opportunistic feeding and routing protocol for reliable multicast with pipelined network coding, (2012).
Li Peng, et al., Reliable multicast with pipelined network coding using opportunistic feeding and routing. IEEE Trans. Parallel Distributed Syst. 25(12), 3264–3273 (2014). CrossRef
L Liu, et al., Physarum Optimization: A biology-inspired algorithm for the Steiner tree problem in networks. IEEE Trans. Comput. 64(3), 819–832 (2015). MathSciNet
Y Liu, et al., Multi-layer clustering routing algorithm for wireless vehicular sensor networks. IET Commun. 4(7), 810–816.
T Meng, et al., Spatial reusability-aware routing in multi-hop wireless networks. IEEE TMC (2015). doi: 10.1109/TC.2015.2417543.
Y-S Yen, et al., Flooding-limited and multi-constrained QoS multicast routing based on the genetic algorithm for MANETs. Math. Comput. Modell. 53(11-12), 2238–2250 (2011). CrossRef
M Youssef, et al., Routing metrics of cognitive radio networks: a survey. IEEE Commun. Surv. Tutorials. 16(1), 92–109 (2014). CrossRef
I Woungang, SK Dhurandher, A Athanasios, V Vasilakos, Routing in opportunistic networks (Springer, 2013).
XM Zhang, et al., Interference-based topology control algorithm for delay-constrained mobile ad hoc networks. IEEE Trans. Mobile Comput. 14(4), 742–754 (2015). CrossRef
A Attar, et al., A survey of security challenges in cognitive radio networks: solutions and future research directions. Proc. IEEE. 12:, 3172–3186 (2012). CrossRef
AV Vasilakos, et al., Information centric network: research challenges and opportunities. J. Netw. Comput. Appl. 52:, 1–10 (2015). CrossRef
Marwaha S, et al., in Congress on Evolutionary Computation, CEC, 2. Evolutionary fuzzy multi-objective routing for wireless mobile ad hoc networks, (2004), pp. 1964–1971.
A Vasilakos, et al., Optimizing QoS routing in hierarchical ATM networks using computational intelligence techniques. IEEE Transactions on Systems, Man, and Cybernetics, Part C: Applications and Reviews, (2003).
W Quan, C Xu, AV Vasilakos, J Guan, H Zhang, LA Grieco, in IFIP Networking Conference. TB2F: Tree-bitmap and bloom-filter for a scalable and efficient name lookup in content-centric networking, (2014).
K Liu, et al., A cooperative MAC protocol with rapid relay selection for wireless ad hoc networks. Comput. Netw. 91:, 262–282 (2015). CrossRef
L Xiang, et al., in 8th Annual IEEE Communications Society Conference on Sensor, Mesh and Ad Hoc Communications and Networks (SECON). Compressed data aggregation for energy efficient wireless sensor networks, (2011).
C Perkins, Royer E, in Second IEEE Workshop on Mobile Computing Systems and Applications, WMCSA. Ad hoc on-demand distance vector routing, (1999).
DB Johnson, DA Maltz, Dynamic source routing in Ad-hoc Wireless Networks. Mobile Computing, pages 153–181. Kluwer Academic Publishers (1996).
- An initial analysis of packet function-aware extension to Dijkstra algorithm for wireless networks
- Springer International Publishing
EURASIP Journal on Wireless Communications and Networking
Elektronische ISSN: 1687-1499
Neuer Inhalt/© ITandMEDIA