SE Designing Future Networking Systems
| Semester: | Wintersemester 2006/2007 |
| Art: | Seminar, 2 SWS |
| LV-Nr.: | 043 L 729 |
| Zeit: | DI. 10-12 Uhr; ab 24.10 |
| Raum: | FR 0028 |
| Dozent: | Martin Roth |
| Bemerkung: | Vertiefungsveranstaltung im Hauptstudium (KI, BKS, WI) |
Beschreibung
Principles of future internet design will be introduced in several hands-on projects. Of primary concern are issues in mobile wireless networks, where protocols originally designed for the wired internet no longer perform. Such networks are often characterized by unstable multihop communications links and high node mobility. The routing, transport, and application layers are discussed, presenting cutting edge ideas to solve the most pressing problems. Protocols and design are reviewed in substantial detail. Students are encouraged to develop their own solutions, with an opportunity to expand their projects to a diplomarbeit.
Introduction to Course
Service placement using XenoSpread
This project will investigate algorithms and mechanisms for improving the placement and spread of services in a cluster or a network. Given a set of available servers, their properties, a service with certain resource requirements, and a set of users of that service, XenoSpread will be able to place the aforementioned service on the "best possible" set of servers.
Service placement is a crucial parameter to the success of service and content delivery systems (see Akamai, www.akamai.com); placing services near users can help overcome network latency, long-haul network charges, and jitter.
www.cl.cam.ac.uk/Research/SRG/netos/papers/2003-xenosearch.pdf
The most important parameters for determining what is best will be a) availability of the required resources, b) the location of the users of the service to be placed, and c) the cost of these resources. XenoSpread will be able to find servers that are a) available, b) as close as possible to the users of the service, and c) not charging too much for the resources they provide.
Objectives:
- An algorithm that suggests the best possible set of servers to run a service
- A practical system that implements the above algorithm as an add-on to the XenoServer software. The result of this project will be a facility similar to google's "i feel lucky", which would run a given service on whichever set of servers ServerFinder considers best
- Experimental evaluation to determine that the system performs and scales well
Host Identification Protocol (HIP)
In this project, the aim is to firstly survey existing publicly available experimental HIP implementations and secondly gain unique hands-on experiences in setting up HIP in heterogeneous networks environments.
You will be given a unique opportunity to setup a test-bed environment capable of seamlessly switching an incoming music streams between any IP enabled devices using different access technologies.
Next Generation Active Queue Management (AQM) Algorithms
AQM provides a mechanism by which a link (router) sends congestion notification to the users. In particular, an AQM algorithm uses the queue length information to either mark or drop packets. Recently, Alpcan et al., has proposed a novel approach to address this problem. This approach is based on Markov modeling of communication networks via Hidden Markov Models (HMM) and optimal control of their complex dynamics using Markov Decision Process (MDP). Initial numerical analysis of the algorithms developed is very promising. However, these novel AQM schemes need further testing and verification via realistic packet-level simulations. The students in this project will have a chance to participate in this exciting, cutting-edge research that is being conducted as part of an international collaboration with the faculty of University of Illinois at Urbana-Champaign, USA.
The main task of the students joining this project is to simulate some existing but very novel AQM algorithms on various network topologies using the NS-2 network simulator (see link below). The students do not have to have a detailed knowledge regarding the theoretical aspects of these algorithms to simulate them, but are welcome to study them more if they want. The project provides a great opportunity for learning about networking protocols and algorithms and getting first-hand experience.
Significant assistance will be provided during all stages of the project through examples and clear directions.
Objectives:
- Basic introduction to NS-2 network simulator (advisor will provide significant assistance).
- Short introduction to the AQM problem and the novel approach.
- Combination of existing freely available software scripts to implement a foundation for implementing the AQM algorithm.
- Investigation of the AQM algorithms via NS-2 simulations on various topologies and scenarios.
Relevant links:
- NS-2 simulator homepage: www.isi.edu/nsnam/ns/
- NS-2 tutorial: www.isi.edu/nsnam/ns/tutorial/index.html
- Python homepage: www.python.org, www.python.org/doc/current/ext/embedding.html
- Some links to existing HMM, MDP python scripts on the web: pbil.univ-lyon1.fr/software/sarment/, aima.cs.berkeley.edu/python/readme.html, http://www.logilab.org/projects/hmm/documentation
Link-layer adaptation based TCP throughput optimization in Wireless Networks: Cross-Layer Architecture and Implementation Specifications
Almost a decade long research on the performance of TCP in wireless networks has resulted in many proposals and solutions to the problem of TCP throughput degradation. Several of these measures, however, have their share of drawbacks. With the continuing emergence of wireless technologies ever since the work on TCP performance over wireless began, smart link-layer mechanisms like adaptive modulation and coding, power control, and incremental redundancy have been designed and deployed. The work in [1], [2] outlines a cross-layer optimization framework based on the congestion control dynamics of a bulk transfer TCP flow and presents its application to networks which offer adaptive link-layer measures. The essence behind the optimization approach is to protect the segments in a TCP window when it has a size smaller that the bandwidth delay product of the network. The protection is rendered by ensuring a high segment success probability (via robust modulation and coding, greater transmission power, etc.). The farther the window size from filling the bandwidth-delay product of the network, the greater the protection offered to it.
Objectives:
- Functionality: Transport to Link Layer Tunnel: A TCP session stamps information pertaining to cycle [1, 2] and round number [1, 2] in the segments. The information is tunneled down to the link-layer.
- Functionality: TCP dynamics aware link adaptation: The wireless link layer parses the information from TCP segments and chooses transmission modes for the link-layer frames.
- Scenario: Mobile terminal as the TCP sender: Information for each TCP session is tunneled down to the link layer which performs link adaptation accordingly.
- Scenario: Mobile terminal as the TCP receiver: TCP session originating at a server in the Internet tunnels transport layer information to the link layer. This information traverses the Internet and is used by the link layer at the network point of attachment to perform link adaptation.
Inferring TCP dynamics information at the BS/AP for downlink transfer: Since creation of a tunnel at every Internet server may not be feasible, the TCP dynamics information cannot be always obtained at the network point of attachment. However, the link-layer functionality at the AP/BS can be enhanced to infer the level of protection that the TCP segments warrant for downlink transfer to the mobile terminal. It is an open problem to delineate these inference measures.
References:
[1] J. P. Singh, “High Performance Wireless Networking: Adaptation of the Networking Stack to Radio Conditions,†Ph.D. dissertation, Stanford University, Stanford, CA, 2005. [Online]. Available: www.stanford.edu/~jatinder/PhDThesis.pdf
[2] J.P. Singh, Y. Li, N. Bambos, A. Bahai, B. Xu, and G. Zimmerman, “TCP Performance Dynamics and Link-layer Adaptation based Optimization Methods for Wireless Networks,†under review, IEEE Transactions on Wireless Communications.
[Online]. Available: http://www.stanford.edu/~jatinder/linkAdaptation.pdf
Scheduling for Heterogeneous Access Networks
Several emerging wireless technologies today are envisioned to co-exist synergistically for enabling ubiquitous and broadband wireless access. The heterogeneity in the merits offered by 3G, Wi-Fi and WiMAX technologies, makes it attractive to investigate their integration for the design of fixed and mobile wireless systems. A multi-interface system is equipped with wireless interfaces on which data can be simultaneously transmitted. Scheduling on multiple wireless interfaces is a crucial aspect of an efficient system design. Conventionally, the research on wireless scheduling has focused heavily on packet fair queuing algorithms for multiple input traffic flows. Packet scheduling for data stripping on to output wireless interfaces has recently been investigated [1], [2] from an implementation viewpoint.
Objectives:
- Scheduling scenario: The client device communicates via multiple output wireless interfaces that provide connectivity to base stations and access points belonging to different radio networks. The Internet data from the client are aggregated at the client inbuilt proxy and transmitted on the output interfaces. The base stations and access points receive the data and send them to a server proxy that routes them to their respective destinations in the Internet. The server proxy also collects the data generated by hosts in Internet for the client. It schedules this data to be transmitted to the client via the base stations and access points having wireless connectivity with the client. The user-side proxy delivers to the user device, the incoming Internet data. The challenge lies in the efficient scheduling of packets for uplink transmission on different interfaces of client device and for downlink transmission from different base stations and access points to the client.
- Application: Multi-radio devices have emerged in the wireless market today. However, these usually incorporate independently functioning radios, and are provided wireless access via a single interface at a time. In the event of user migration to an area where the coverage provided by an interface is lost, wireless connectivity for the device is switched to another interface which is in its zone of coverage. In regions when multiple interfaces are simultaneously capable of communication, the user is provided access via the higher data rate interface. This access methodology clearly does not leverage efficiently the presence of multiple wireless interfaces. The integrated operation of multi-radio devices has been investigated from an implementation viewpoint in [5], [7]. However, efficient scheduling measures have remained uninvestigated. Internet access in moving trains constitutes another challenging scenario for multi-interface wireless access. As the bandwidth required for serving several users in the train is high, wireless connectivity via multiple radio access networks needs to be provisioned. The internal train scenario comprises of users having Internet access via Bluetooth and IEEE 802.11a/b/g based devices. The user devices communicate with access points at the input of a train gateway. The gateway has multiple output wireless interfaces that provide connectivity to base stations and access points belonging to different radio networks. The uplink and downlink data scheduling is of significant merit in this scenario.
- Implementation: Assembly of a client device with multiple interfaces
- Implementation: Connectivity to multiple access networks
- Implementation: Set-up of server proxy functionality
Uplink and downlink scheduling policies for different traffic types (web, real-time) is of interest. It is desired to put to implementation the work on modeling and analysis of packet scheduling disciplines presented in [3] where Markov modeling techniques and simulation appraisals have been employed to demonstrate that a channel aware scheduling can achieve reduction in buffer lengths, packet delays, multi-user interference and device energy consumption.
References:
[1] P. Rodriguez, R. Chakravorty, J. Chesterfield, I. Pratt, and S. Banerjee, “MAR: A commuter router infrastructure for the mobile Internet,†in Proc. of the 2nd international conference on Mobile systems, applications, and services (MobiSys 2004), 2004, pp. 217–230.
[2] A. Adya, P. Bahl, J. Padhye, A. Wolman, and L. Zhou, “A multi-radio unification protocol for IEEE 802.11 wireless networks,†in Proc. of the First International Conference on Broadband Networks (BROADNETS 2004), 2004, pp. 344–354.
[3] J. P. Singh, “High Performance Wireless Networking: Adaptation of the Networking Stack to Radio Conditions,†Ph.D. dissertation, Stanford University, Stanford, CA, 2005. [Online]. Available: http://www.stanford.edu/~jatinder/PhDThesis.pdf
Routing Layer: Termite
New applications for wireless networks have also brought new problems. Mesh and ad-hoc networks are a class of applications in which nodes are deployed in an unplanned manner, and act as routers as well as end-devices. Due to the unregulated placement and use of such devices, their connectivity is highly variable, including temporary, yet complete, disconnection from the network. Such a volatile networking environment produces new challanges for routing protocols. Oftentimes flexibility and adaptivity become more important than pure performance. Probabilistic routing protocols have been developed to provide performance with the necessary flexibility for such difficult networking environments. Packets are routed randomly through the network based on estimates of route quality. Route quality estimates are based on probes sent through the network, or from overheard packets. In this way, when one route fails, the next best route is automatically used.
Unfortunately such routing protocols are governed by a large set of interacting parameters. Local changes result in global changes in routing performance as well, though it is not known how to predict beforehand what influences what parameters will have. The objectives of this project will be to simulate a probabilistic routing protocol in a software network simulator and find how the various parameters are related, and to what conditions they are best suited. Of special interest is the creation of a model to help predict how local parameters affect gloabl routing behavior.
Open Routers
This project is concerned with the implementation and evaluation of a system for enabling cross-layer interactions in a wireless access router system. It will involve the implementation of the primitives of interaction between the link-layer and the network-layer (such as events, actions and statistics), namely between the access point (Wireless Termination Point –WTP) and the access router (also known as access controller –AC). Time permitted, the system will be deployed and evaluated on the Magnets Mesh and measurements will be conducted to assess the feasibility and efficiency of obtaining network “weather†information in the presence of unreliable, dynamic links.
Objectives:
- Implementation of the router agent part of the framework in OpenWRT, using open source drivers for wireless LAN cards (madwifi for Atheros, or hostAP for Prism2.5). Alternatively on the Click router framework.
- Implementation of the protocol for cross-layer interaction at the router core, using the eXtensible Open Router Platform (XORP: www.xorp.org) -Measurements and evaluation of the system -The software that will be developed, will be released as open source
References:
1) “DIRAC: A Software-based Wireless Router Systemâ€, P. Zerfos et. al., In Proceedings of ACM Mobicom 2003, www.cs.ucla.edu/wing/publication/papers/Zerfos.Mobicom03.ps
2) “Architecture Taxonomy for Control And Provisioning of Wireless Access Pointsâ€, Lily L. Yang, Petros Zerfos, Emek Sadot, Internet Engineering Task Force, RFC 4118, Jun. 2005
www.rfc-editor.org/cgi-bin/rfcdoctype.pl
Voraussetzungen
Abgeschlossenes Vordiplom in Informatik oder einer verwandten Studienrichtung
Prüfungsmodalitäten, Anforderungen
Diese Lehrveranstaltung kann in eine Prüfung in den Bereichen KI, BKS und WVA eingebracht werden.
Copyright TU Berlin 2007