A Video Streaming System for Mobile Phones: Practice and Experience

This paper presents a case of video streaming system for mobile phone which has actually been implemented and deployed for commercial services in CDMA2000 1X cellular phone networks. As the computing environment and the network connection of cellular phones are significantly different from the wired desktop environment, the traditional desktop streaming method is not applicable. Therefore, a new architecture is required to suit the successfully streaming in the mobile phone environment. We have developed a very lightweight video player for use in mobile phone and the related authoring tool for the player. The streaming server has carefully been designed to provide high efficiency, reliability and scalability. Based on a specifically-designed suite of streaming protocol, the server employs an adaptive rate control mechanism which transmits the media packets appropriately into the network according to the change in network bandwidth.Hojung Cha is currently a professor in computer science at Yonsei University, Seoul, Korea. His research interests include multimedia computing system, multimedia communication networks, wireless and mobile communication systems and embedded system software. He received his B.S. and M.S. in computer engineering from Seoul National University, Korea, in 1985 and 1987, respectively. He received his Ph.D. in computer science from the University of Manchester, England, in 1991.Jongmin Lee is a Ph.D. candidiate in computer science at Yonsei University, Seoul, Korea. His research interests include wireless multimedia system, QoS architecture, multimedia communication networks. He received his B.S. and M.S. in computer science from Kwangwoon University in 1999 and 2001, respectively.Jongho Nang is a professor in the Department of Computer Science at Sogang University. He received his B.S. degree from Sogang University, Korea, in 1986 and M.S. and Ph.D. degree from KAIST, in 1988 and in 1992, respectively. His research interests are in the field of multimedia systems, digital video library, and Internet technologies. He is a member of KISS, ACM, and IEEE.Sung-Yong Park is an associate professor in the Department of Computer Science at Sogang University, Seoul, Korea. He received his B.S. degree in computer science from Sogang University, and both the M.S. and Ph.D. degrees in computer science from Syracuse University. From 1987 to 1992, he worked for LG Electronics, Korea, as a research engineer. From 1998 to 1999, he was a research scientist at Telcordia Technologies (formerly Bellcore) where he developed network management software for optical switches. His research interests include high performance distributed computing and systems, operating systems, and multimedia.Jin-Hwan Jeong received the B.S. and M.S. degrees in computer science from Korea University, Seoul, Korea, in 1997, and 1999, respectively. He is currently in Ph.D. course at Korea University. His research interests include video processing for thin devices, multimedia streaming and operating systems.Chuck Yoo received the B.S. degree in electronics engineering from Seoul National University, Seoul, Korea and the M.S. and Ph.D. in computer science in University of Michigan. He worked as a researcher in Sun Microsystems Lab. from 1990 to 1995. He joined the Computer Science and Enginnering Department, Korea University, Seoul, Korea in 1995, where he is currently a professor. His research interests include high performance network, multimedia streaming, and operating systems.Jin-Young Choi received the B.S. degree from Seoul National University, Seoul, Korea, in 1982, the M.S. degree from Drexel University in 1986, and the Ph.D. degree from University of Pennsylvania, in 1993. He is currently a professor of Computer Science and Engineering Department, Korea University, Seoul, Korea. His current research interests are in real-time computing, formal methods, programming languages, process algebras, security, software engineering, and protocol engineering.     

Throughput Scalability of Wireless Hybrid Networks over a Random Geometric Graph

In this paper, we consider the transport capacity of ad hoc networks with a random flat topology under the present support of an infinite capacity infrastructure network. Such a network architecture allows ad hoc nodes to communicate with each other by purely using the remaining ad hoc nodes as their relays. In addition, ad hoc nodes can also utilize the existing infrastructure fully or partially by reaching any access point (or gateway) of the infrastructure network in a single or multi-hop fashion. Using the same tools as in [9], we show that the per source node capacity of Θ(W/log(N)) can be achieved in a random network scenario with the following assumptions: (i) The number of ad hoc nodes per access point is bounded above, (ii) each wireless node, including the access points, is able to transmit at W bits/sec using a fixed transmission range, and (iii) N ad hoc nodes, excluding the access points, constitute a connected topology graph. This is a significant improvement over the capacity of random ad hoc networks with no infrastructure support which is found as in [9]. We also show that even when less stringent requirements are imposed on topology connectivity, a per source node capacity figure that is arbitrarily close to Θ(1) cannot be obtained. Nevertheless, under these weak conditions, we can further improve per node throughput significantly. We also provide a limited extension on our results when the number of ad hoc nodes per access point is not bounded.Ulaş C. Kozat was born in 1975, in Adana, Turkey. He received his B.Sc. degree in Electrical and Electronics Engineering from Bilkent University, Ankara, Turkey and his M.Sc. in Electrical Engineering from The George Washington University, Washington D.C. in 1997 and 1999 respectively. He has received his Ph.D. degree in May 2004 from the Department of Electrical and Computer Engineering at University of Maryland, College Park. He has conducted research under the Institute for Systems Research (ISR) and Center for Hybrid and Satellite Networks (CSHCN) at the same university. He worked at HRL Laboratories and Telcordia Technologies Applied Research as a research intern. His current research interests primarily focus on wireless and hybrid networks that span multiple communication layers and networking technologies. Mathematical modelling, resource discovery and allocation, vertical integration of wireless systems and communication layers, performance analysis, architecture and protocol development are the main emphasis of his work. E-mail: kozat@isr.umd.eduLeandros Tassiulas (S′89, M′91) was born in 1965, in Katerini, Greece. He obtained the Diploma in Electrical Engineering from the Aristotelian University of Thessaloniki, Thessaloniki, Greece in 1987, and the M.S. and Ph.D. degrees in Electrical Engineering from the University of Maryland, College Park in 1989 and 1991 respectively.He is Professor in the Dept. of Computer and Telecommunications Engineering, University of Thessaly, Greece and Research Professor in the Dept. of Electrical and Computer Eng and the Institute for Systems Research, University of Maryland College Park since 2001. He has held positions as Assistant Professor at Polytechnic University New York (1991–95), Assistant and Associate Professor University of Maryland College Park (1995–2001) and Professor University of Ioannina Greece (1999–2001).His research interests are in the field of computer and communication networks with emphasis on fundamental mathematical models, architectures and protocols of wireless systems, sensor networks, high-speed internet and satellite communications.Dr. Tassiulas received a National Science Foundation (NSF) Research Initiation Award in 1992, an NSF CAREER Award in 1995 an Office of Naval Research, Young Investigator Award in 1997 and a Bodosaki Foundation award in 1999 and the INFOCOM′94 best paper award. E-mail: leandros@isr.umd.edu     

DAWL: A Delayed-ACK Scheme for MAC-Level Performance Enhancement of Wireless LANs

The IEEE 802.11 MAC protocol provides a reliable link layer using Stop & Wait ARQ. The cost for high reliability is the overhead due to acknowledgement packets in the direction opposite to the actual data flow. In this paper, the design of a new protocol as an enhancement of IEEE 802.11 is proposed, with the aim of reducing supplementary traffic overhead and increasing the bandwidth available for actual data transmission. The performance of the proposed protocol is evaluated through comparison with IEEE 802.11 as well as with a SSCOP-based protocol. Results underline significant advantages of the proposed protocol against existing ones, thus confirming the value and potentiality of the approach.Dzmitry Kliazovich received his Masters degree in telecommunication science from Belarusian State University of Informatics and Radioelectronics in 2002. He is currently working towards the Ph.D. degree in University of Trento, Italy. His main research interest lies in wireless networking field with a focus on performance optimization and cross-layer design.Fabrizio Granelli was born in Genoa in 1972. He received the “Laurea” (M.Sc.) degree in Electronic Engineering from the University of Genoa, Italy, in 1997, with a thesis on video coding, awarded with the TELECOM Italy prize, and the Ph.D. degree in Electronic Engineering and Computer Science from the same university in 2001. Since 2000 he is carrying on his teaching activity as Assistant Professor at the Dept. of Information and Communication Technologies (DIT) of the University of Trento (Italy) within the B.Sc. and M.Sc. Degrees in Telecommunications Engineering.The research interests of Dr. Granelli are mainly focused on networking, with particular attention to network modeling and performance evaluation, wireless networks, access control, and next-generation telecommunication networks.He is author of more than 30 refereed papers, published in several international journals and conferences.Dr. Granelli is member of the IEEE Committee on “Communication Systems Integration and Modeling” (CSIM) and of the Technical Programme Committee of the “QoS and Performance Evaluation Symposium” of the International Conference on Communications (ICC 2003 and ICC 2004).     

Wireless LANs: From WarChalking to Open Access Networks

This work discusses the evolution of W-LANs from their current status of wireless termination of LAN services to a possible global infrastructure where the access networks become open to multiple operators and a vehicle of a win-win scenario, where both users and operators benefit from the new network architecture. The idea of Open Access Networks (OANs) can go beyond wireless HotSpots and be generalized to a generic shared access infrastructure that fosters service operators competition and drastically reduces the cost of last mile coverage.The general concept of Open Access Networks is detailed, highlighting its difference with the more traditional model of vertical integration of the access network into the global service. About the OANs development, it is shown how to support the quick and smooth evolution of the infrastructure toward a widespread and reliable communication support.Business models are discussed by mentioning the different actors, the market organization and the different organization forms.The final part of the paper is devoted to technical challenges such as access control, security, privacy, roaming, resource exploitation and service differentiation. As an example of how to tackle these problems, we discuss a pricing technique devoted to resource management and billing support.In addition we present a simulation on how the OAN concept can speed-up the deployment of broadband access in a real case.A preliminary version of this paper with the title “Global Growth of Open Access Networks: from WarChalking and Connection Sharing to Sustainable Business” was presented at WMASH 2003. Roberto Battiti received the Laurea degree from the University of Trento, Italy, in 1985 and the Ph.D. degree from the California Institute of Technology (Caltech), USA, in 1990. He has been a consultant in the area of parallel computing and pattern recognition and since 1991 he has been a faculty member at the University of Trento, where he is now full professor of Computer Networks. His main research interests are heuristic algorithms for optimization problems, in particular reactive search algorithms for maximum clique, maximum satisfiability, graph coloring, networks and massively parallel architectures, code assignment in wireless and cellular networks, protocols for pricing and Quality of Service in wireless networks.Prof. R. Battiti is currently Dean of the international Graduate School in Information and Communication Technologies at Trento, Deputy Dean at the Faculty of Science, member of the advisory committee for the future Telecommunications Plan of the Autonomous Province of Trento. Prof. R. Battiti is associate editor of various scientific journals. He is the author of more than fifty scientific publications, including special issues dedicated to experimental algorithmics and wireless on-demand networks.R. Battiti is a member of IEEE Computer Society and ACM Sigmobile. Renato Lo Cigno is Associate Professor at the Department of Computer Science and Telecommunications (DIT) of the University of Trento, Italy. He received a Dr. Ing. degree in Electronic Engineering from Politecnico di Torino in 1988. From 1989 to 2002 has been with the Telecommunication Research Group of the Electronics Department of Politecnico di Torino.From June 1998 to February 1999, he was at the CS Department at UCLA as Visiting Scholar under grant CNR 203.15.8. He is coauthor of more than 90 journal and conference papers in the area of communication networks and systems. His curent research interests are in performance evaluation of wired and wireless networks, modeling and simulation techniques, flow and congestion control, as well as network management and architecture. Renato Lo Cigno is member of the IEEE Communication Society and ACM Sigcomm. Mikalai Sabel received his master degree in radio physics from Belorussian State University in 2002. He is now pursuing his Ph.D. at the international Graduate School of Information and Communication Technologies at University of Trento, Italy. His research interest include wireless LANs, pricing and incentive engineering, IEEE802.11 MAC protocol. His current research is focused on optimization algorithms that can provide stability and maximum global welfare in a non-cooperative environment where singles tries to maximize their own benefit function. Experimentation of such schemes to pricing techniques and micro-payments in TLC networks provides the application environment of the fundamental research. Fredrik Orava is associate professor at KTH, Stockholm, Sweden. He conducts research into scalable (in terms of cost, capacity, number of users and devices etc.) communication system architectures and technologies. He has a MSc in engineering physics from Uppsala University and a PhD in computer systems also from Uppsala University. He previously held positions as researcher at the Swedish Institute for Computer Science (SICS); senior lecturer and manager of the telecommunications systems laboratory at the department for teleinformatics, KTH; acting professor in telecomunication systems at KTH; director for the Swedish Centre for Internet Technologies; and vice president of Dynarc AB with world wide responsibility for product management. Dynarc AB develops, manufactures and sells IP routers for optical IP networks. Bjorn Pehrson is a professor of telecommunication systems at KTH, the Royal Institute of Technology in Stockholm, since 1992, where he has also served as a department chairman and vice dean. He had his PhD from Uppsala University 1975 where he also served as senior lecturer and established a research group in computer and communication technology. During the period 1985-1992 he participated in the establishment of the Swedish Institute of Computer Science. Björn Pehrson research interests are currently focussed on open network topologies allowing different actors forming new value chains to build networks together based on different, sometimes very local business models. The results are applied in testbeds, especially in rural areas and in developing countries.This revised version was published online in August 2005 with a corrected cover date.     

Enhancement of a WLAN-Based Internet Service

A wireless LAN (WLAN)-based Internet service, called NESPOT, of Korea Telecom (KT), the biggest telecommunication and Internet service company in Korea, has been operational since early 2002. As the numbers of subscribers and deployed access points (APs) increase, KT has been endeavoring to improve its service quality as well as the network management. In this paper, we introduce a joint effort between Seoul National University (SNU) and KT to achieve it. We have been addressing two major issues as part of the joint project thus far: (1) a unified WLAN management/maintenance tool; and (2) real-time traffic support enhancement. We present our on-going efforts as well as some preliminary results. Some issues, which need further attention for the future NESPOT service enhancement, are also introduced.The work reported in this paper was financed and supported by KT. Any opinions, findings, and conclusions or recommendations expressed in this publication are those of the authors and do not necessarily reflect the views of KT. Youngkyu Choi is an M.S. candidate in the department of electrical engineering at Seoul National University (SNU), Seoul, Korea. He received his B.S. with honors in electrical engineering from SNU in 2002. He has a lot of project experiences related with system software development. His current research interests are the design of MAC layer from distributed system to centralized cellular system, resource management in next-generation (4G) cellular system, and mathematical analysis of system performance. He had served in the Korean Army for 3 years from 1998. Sekyu Park is a research staff at the Multimedia & Wireless Networking Lab. (MWNL), Seoul National University (SNU), Seoul, Korea. Before joining MWNL in September 2003, he was with MMC Technology, Seoul, Korea as a Research Staff for five years. His current research interests are in the area of wireless/mobile networks and embedded OS. Sunghyun Choi is an assistant professor at the School of Electrical Engineering, Seoul National University (SNU), Seoul, Korea. Before joining SNU in September 2002, he was with Philips Research USA, Briarcliff Manor, New York, USA as a Senior Member Research Staff and a project leader for three years. He received his B.S. (summa cum laude) and M.S. degrees in electrical engineering from Korea Advanced Institute of Science and Technology (KAIST) in 1992 and 1994, respectively, and received Ph.D. at the Department of Electrical Engineering and Computer Science, The University of Michigan, Ann Arbor in September, 1999. His current research interests are in the area of wireless/mobile networks with emphasis on the QoS guarantee and adaptation, resource management, wireless LAN and PAN, next-generation mobile networks, data link layer protocols, and connection and mobility management. He authored/coauthored over 45 technical papers and book chapters in the areas of wireless/mobile networks and communications. He is the technical program co-chair for ACM International Workshop on Wireless Mobile Applications and Services on WLAN Hotspots (WMASH’2004). He is currently serving on program committees of a number of leading wireless and networking conferences including IEEE INFOCOM, IEEE GLOBECOM, and IEEE VTC. He is also a guest co-editor for a special issue on “Emerging WLAN Applications and Technologies” of Wiley Wireless Communications and Mobile Computing Journal. He is an active participant and contributor of the IEEE 802.11 WLAN standardization committee. Dr. Choi was a recipient of the Korea Foundation for Advanced Studies Scholarship and the Korean Government Overseas Scholarship during 1997–1999 and 1994–1997, respectively. Go Woon Lee is a researcher at Service Development Laboratory, Korea Telecom (KT), Seoul, Korea. She received her B.S. degrees in computer science and material engineering from Korea Advanced Institute of Science and Technology (KAIST) in 1995. She was with Microsoft Korea R&D Group as a research staff in 1995. She received M.S. degree in information & communication from Kwang-Ju Institute of Science and Technology (K-JIST) in 1998. Her current research interests are in the area of wireless/mobile networks with emphasis on data link layer protocols, remote diagnosis, and wireless service management. Jaehwan Lee is a researcher at Korea Telecom (KT), Seoul, Korea. He received his B.S. and M.S. degrees in electrical engineering from Seoul National University (SNU) in 1998 and 2000, respectively. His master’s research was about estimation theory related to Global Positioning System (GPS) and image processing in robot soccer. His current research interest is to analyze and enhance the performance of wireless/mobile networks (IEEE 802.11, sensor networks and mobile ad-hoc networks) regarding QoS, energy-efficiency and high-throughput considering hand-off and inter-networking with heterogeneous networks. Before joining wireless LAN group in KT, he developed the Web-GIS (Geographical Information System) client-server system from 2000 to 2001. Hanwook Jung, Ph.D joined KT in 1985 and got his Ph.D degree with the company finalcial scholarship of KT from 1991 to 1996 at SUNY at Buffalo. His thesis is about “Wireless signal transmission over Fiber by subcarrier multiplexing” which is current heavily utilized for PCS and cellular repeater line. From 1985 to 1991, he had developed a Videotex service which is now known as Hitel. From 1996 to 1999, he developed 26GHz broadband wireless local loop system and contributed to get the license from the government. Since 1999, he has led a business model and service with wireless LAN. The KT Wi-Fi public service, “NESPOT” has 300,000 subscribers and 10,000 public hotspots. In 2003 he was promoted as an assistant vice president leading NESPOT research team to enhance KT’s broadband with 5,000,000 subscribers. His vision regarding next generation communications service is believed to be true by combining the broadband access and wireless technology including WiFi wireless LAN, UWB, and bluetooth in those areas such as wireless home-networking, device-to-device communications, and ubiqutous networking.This revised version was published online in August 2005 with a corrected cover date.     

Throughput Analysis and Admission Control for IEEE 802.11a

We propose a new Markov model for the distributed coordination function (DCF) of IEEE 802.11. The model incorporates carrier sense, non-saturated traffic and SNR, for both basic and RTS/CTS access mechanisms. Analysis of the model shows that the throughput first increases, and then decreases with the number of active stations, suggesting the need for an admission control mechanism.We introduce such a mechanism, which tries to maximize the throughput while maintaining a fair allocation. The maximum achievable throughput is tracked by the mechanism as the number of active stations increases. An extensive performance analysis shows that the mechanism provides significant improvements.Mustafa Ergen received the B.S. degree in electrical engineering from Middle East Technical University (METU) and was the METU Valedictorian in 2000. He received the M.S. and Ph.D. degrees in electrical engineering in 2002 and 2004, the MOT certificate of HAAS Business School in 2003, and the M.A. degree in International and Area Studies in 2004 from the University of California, Berkeley.Dr. Ergen has been conducting research in wireless communication networks with an emphasis on sensor networks, wireless LAN and OFDM systems and is the author of many works in the field, including the book (with A.R.S. Bahai and B.R. Saltzberg) Multi-Carrier Digital Communications: Theory and Applications of OFDM (New York: Springer, 2004).He is National Semiconductor Post Doctoral Fellow and was awarded eight times Bulent Kerim Altay Award by department of electrical engineering in METU and received Best Student Paper Award in IEEE ISCC 2003 and has an invited paper in IEEE GLOBECOM CAMAD 200.Pravin Varaiya is Nortel Networks Distinguished Professor in the Department of Electrical Engineering and Computer Sciences at the University of California, Berkeley. From 1975 to 1992, he was also Professor of Economics at Berkeley. His research is concerned with communication networks, transportation, and hybrid systems. He has taught at MIT and the Federal University of Rio de Janeiro, Varaiya has held a Guggenheim Fellowship and a Miller Research Professorship. He received an Honorary Doctorate from L’Institut National Polytechnique de Toulouse, and the Field Medal of the IEEE Control Systems Society. He is a Fellow of IEEE and a member of the National Academy of Engineering. He is on the editorial board of several journals, including “Discrete Event Dynamical Systems” and “Transportation Research-C.” He has co-authored three books and more than 250 technical papers. The second edition of “High-Performance Communication Networks” (with Jean Walrand) was published by Morgan-Kaufmann in 2000. “Structure and interpretation of signals and systems” (with Edward Lee) was published in 2002 by Addison-Wesley.     

A branch and cut algorithm for hub location problems with single assignment

The hub location problem with single assignment is the problem of locating hubs and assigning the terminal nodes to hubs in order to minimize the cost of hub installation and the cost of routing the traffic in the network. There may also be capacity restrictions on the amount of traffic that can transit by hubs. The aim of this paper is to investigate polyhedral properties of these problems and to develop a branch and cut algorithm based on these results.Acknowledgement The research of the first author was partially supported by the Banque Nationale de Belgique. The research of the second author was supported by France Telecom R&D under contract no. 99 1B 774. Their support is gratefully acknowledged.     

Locating Active Sensors on Traffic Networks

Sensors are used to monitor traffic in networks. For example, in transportation networks, they may be used to measure traffic volumes on given arcs and paths of the network. This paper refers to an active sensor when it reads identifications of vehicles, including their routes in the network, that the vehicles actively provide when they use the network. On the other hand, the conventional inductance loop detectors are passive sensors that mostly count vehicles at points in a network to obtain traffic volumes (e.g., vehicles per hour) on a lane or road of the network.This paper introduces a new set of network location problems that determine where to locate active sensors in order to monitor or manage particular classes of identified traffic streams. In particular, it focuses on the development of two generic locational decision models for active sensors, which seek to answer these questions: (1) “How many and where should such sensors be located to obtain sufficient information on flow volumes on specified paths?”, and (2) “Given that the traffic management planners have already located count detectors on some network arcs, how many and where should active sensors be located to get the maximum information on flow volumes on specified paths?”The problem is formulated and analyzed for three different scenarios depending on whether there are already count detectors on arcs and if so, whether all the arcs or a fraction of them have them. Location of an active sensor results in a set of linear equations in path flow variables, whose solution provide the path flows. The general problem, which is related to the set-covering problem, is shown to be NP-Hard, but special cases are devised, where an arc may carry only two routes, that are shown to be polynomially solvable. New graph theoretic models and theorems are obtained for the latter cases, including the introduction of the generalized edge-covering by nodes problem on the path intersection graph for these special cases. An exact algorithm for the special cases and an approximate one for the general case are presented.     

A Continuous Location-Allocation Problem with Zone-Dependent Fixed Cost

A zone-dependent fixed cost is introduced within the framework of minisum location of facilities in the continuous space. An efficient algorithm for determining the optimal solution for the single facility location problem is put forward, and its properties are validated. A hypothetical example is given to illustrate the algorithm. Some heuristic procedures are proposed for the multi-facility case with encouraging results.