2009 Annual Report of Advanced Networked Environment Division, Cybermedia Center, Osaka University, Japan

This web page is the 2009 annual report of Advanced Networked Environment Division, Cybermedia Center, Osaka University (Ubiquitous Network Laboratory, Graduate School of Information Science and Technology, Osaka University / Nakano Laboratory).

Japanese version of this web page is here.

Table of contents

  1. Members
    1. Laboratory staffs
    2. Joint researcher
    3. Students
  2. Achievements
    1. Research on communications in ubiquitous network environments
      1. Detection of characteristics of pedestrians with compound-eye binary sensors
      2. Object tracking based on scenario-type hypothesis tracking
      3. Detection of characteristics of pedestrians in video sequences
      4. Detecting optical flow for estimating number of pedestrians passing through virtual gate in video sequences
      5. Time slot assignment algorithms for reducing transmission latency in IEEE 802.16j relay networks
      6. Improving coverage area quality using physical topology information in IEEE 802.16j relay networks
      7. Node repositioning for performance improvement in IEEE 802.16j relay networks
      8. Performance evaluation of IEEE 802.16j relay networks considering radio wave blocking by obstacles
      9. Time slot assignment algorithms for reducing transmission latency in IEEE 802.16j camera relay networks
      10. Proposal and evaluation of an interference model based on SNR
    2. Research on architecture of transport layer for next-generation high-speed network
      1. Reduction of inter-ISP transit cost caused by overlay routing
      2. Proactive recovery from multiple failures utilizing overlay networking technique
      3. Scalable and density-aware measurement strategies for overlay networks
      4. Congestion control mechanisms for alleviating TCP unfairness in wireless LAN environment
      5. Increasing robustness to environmental changes for congestion control mechanisms
      6. Improving interactive user experience on thin clients
      7. Performance evaluation of distributed computing environment considering power consumption
  3. Publications
    1. Journal papers
    2. International conference papers
    3. Theses
      1. Masters' Theses
      2. Bachelors' Theses

1. Members

1.1. Laboratory staffs

Hirotaka Nakano
Hirotaka Nakano
Professor
Go Hasegawa
Go Hasegawa
Associate Professor
Yoshiaki Taniguchi
Yoshiaki Taniguchi
Assistant Professor
Takako Inakagi
Takako Inakagi
Secretary

1.2. Joint researcher

Masayuki Murata
Masayuki Murata
Osaka University
Graduate School of IST
Professor

1.3. Students

Shoji Kurakake
Shoji Kurakake
Doctoral Course 2nd
Yasuhiro Ogiri
Yasuhiro Ogiri
Doctoral Course 1st
Rintaro Ishii
Rintaro Ishii
Master Course 2nd
Sayaka Kuriyama
Sayaka Kuriyama
Master Course 2nd
Masafumi Hashimoto
Masafumi Hashimoto
Master Course 2nd
Takuro Horie
Takuro Horie
Master Course 2nd
Kazuhito Matsuda
Kazuhito Matsuda
Master Course 2nd
Masakazu Murata
Masakazu Murata
Master Course 2nd
Gyeong-Yeon Kang
Gyeong-Yeon Kang
Master Course 1st
Shoichi Takemori
Shoichi Takemori
Master Course 1st
Shinpei Tanaka
Shimpei Tanaka
Master Course 1st
Erika Ashikaga
Erika Ashikaga
Bachelor Course 4th
Yuki Ise
Yuuki Ise
Bachelor Course 4th
Takafumi Shigefuji
Takafumi Shigefuji
Bachelor Course 4th
Xun Shao
Xun Shao
Research Student

2. Achievements

2.1. Research on communications in ubiquitous network environments

With the development of computer and communication technologies, ubiquitous computing environments where everything have communication device with unique identifier, have attracted much attention. In our research group, we study networking and communication issues in ubiquitous computing environments. We propose and evaluate communication methods for various applications in ubiquitous computer environments.

2.1.1. Detection of characteristics of pedestrians with compound-eye binary sensors

Photo of experiment
Fig: Photo of experiment.

Recently, object tracking with sensor networks has attracted the attention of many researchers and developers. In our research group, we have proposed an object tracking method. In our proposed object tracking method, a sensor is assumed to be able to detect characteristics of moving objects such as direction. In this research, we think compound-eye binary sensors to realize the sensors of our proposed object tracking method. The compound-eye binary sensors consists of closely located multiple binary sensors which generate 1 bit information regarding objects' presence or absence within its sensing region. We propose a method to detect the moving direction and the velocity by using the compound-eye binary sensors. Through simulation evaluations, we confirm the fundamental characteristics of the compound-eye binary sensors and show that the distance between binary sensors should be carefully configured to achieve high detection ratio. Furthermore, we implement our method using off-the-shelf sensor nodes with passive infrared sensors and verify its practicality.

[Related papers]

  1. Yoshiaki Taniguchi, Yukihiro Gouda, Go Hasegawa, and Hirotaka Nakano, ``Detection of movement characteristics of objects with compound-eye binary sensors,'' IEICE Technical Report (IN2009-71), pp.17-22, Nov. 2009. (in Japanese) [paper]

2.1.2. Object tracking based on scenario-type hypothesis tracking

Overview of proposed tracking method
Fig: Overview of proposed tracking method

In recent years, wireless communication technologies such as ZigBee have been developed. By constructing wireless sensor networks from infrared sensors with those wireless technologies, it is possible to track objects in a wide monitoring region. In this research, we proposed an object tracking method called Scenario-type Hypothesis Tracking. In our proposed method, a wide monitoring region is divided into multiple closed micro cells, and pairs of infrared sensors are placed at borders of micro cells to detect objects and their moving directions. The sensor information is gathered to a tracking server through wireless networks, and the tracking server maintains virtual micro cells and virtual objects which indicate a variety of hypotheses of object trajectories. Virtual objects are generated, moved, and deleted in virtual micro cells appropriately according to sensor information and behavior of other virtual objects. To prevent failure of object tracking, virtual objects are also generated when the tracking server estimates losses of sensor information due to packet loss, failure of sensing, and functional limitation of sensors. When the tracking server receives departure event information of object to outside of monitoring region, the trajectory of the most appropriate virtual object is selected as the trajectory of the departure object. Through simulation experiments, we confirmed that the number of successful object tracking is improved up to 23% higher by making virtual objects when they cross each other. In addition, the number of successful object tracking is improved up to 6% by making virtual objects when the tracking server estimates losses of sensor information.

[Related papers]

  1. Masakazu Murata, Yoshiaki Taniguchi, Go Hasegawa, and Hirotaka Nakano, ``Improvement and evaluation of scenario-type hypothesis object tracking,'' in Proceedings of the 2nd International Workshop on Sensor Networks and Ambient Intelligence (SeNAmI 2009), Dec. 2009. [paper]
  2. Masakazu Murata, ``Scenario-type hypothesis object tracking with indoor sensor networks,'' Master’s Thesis, Graduate School of Information Science and Technology, Osaka University, Feb. 2010.
  3. Masakazu Murata, Yoshiaki Taniguchi, Go Hasegawa, and Hirotaka Nakano, ``An object tracking method based on Scenario-type Hypothesis Tracking in segmented multiple regions,'' in Proceedings of the 6th International Conference on Networking and Services (ICNS 2010), pp.200-205, Mar. 2010. [paper]

2.1.3. Detection of characteristics of pedestrians in video sequences

Overview of system
Fig: Overview of system

Recently, with the rapid development of the networking technologies and mobile and sensor devices, the ubiquitous network society, where many kinds of services are provided by using information which exists ubiquitously, is becoming a reality. In the ubiquitous network society, we should provide networking environments by which many kinds of mobile nodes such as human, mobile phones, and electric appliances can communicate with each other to collect and spread various information. To construct appropriate networking environments for each service, the knowledge of the mobile nodes such as location, sojourn time and existing distribution in the target area is important. However, in general, it is difficult to collect such information of the mobile nodes with high mobility, such as pedestrians and vehicles.

In this research, we propose a method to estimate the number of mobile nodes in video sequences from a stationary camera in real time. We assume that the pedestrians in the target area correspond to the mobile nodes. The proposed method extracts moving regions from video sequences based on the background difference method and the frame difference, and estimates the number of pedestrians from the size of the extracted region, using a conversion function constructed from the prior-learned statistical data. The occlusion effect, which multiple objects overlap each other in the picture, affects the relation between the size of the extracted region and the number of pedestrians. The larger the overlap between pedestrians in video sequences is, the smaller the size of the extracted region is.

However, if we utilize the conversion function constructed in an ad-hoc manner, there is concern that the estimation accuracy decreases in the environment differed from the prior-learning environment. In this research, we introduce the simple model for the relationships between the moving region size and the number of pedestrians in the region, and construct the conversion function from the model. We evaluate the effectiveness of the proposed approach by comparison the estimated values with the true values and find that the proposed method in this research can decrease the mean squared error by up to 32%. One of the advantages of our method is that the proposed method can be executed in a real-time with recent PCs. Therefore, our method can be used with various applications such as adaptive wireless network configuration, location-based information services, determination of wireless access points and investigation of congestion degree of commercial facilities.

The effectiveness of the proposed method also depends on the accuracy of the extraction of pedestrians in the video sequences. In this research, we consider the filtering method that emphasizes the specific shape by emphasizing the specific frequency in the spatial frequency domain using the Fourier transform. Pedestrians have much the same shape in the head and the chest, but the large difference in the limbs. Therefore we find that the filter is not effective for increasing the estimation accuracy.

[Related papers]

  1. Sayaka Kuriyama, Go Hasegawa, and Hirotaka Nakano, ``Real-time estimation method of the number of pedestrians in video sequences,'' in Proceedings of the 4th International Conference on Digital Telecommunications (ICDT 2009), pp.65-70, July 2009. [paper]
  2. Sayaka Kuriyama, ``Detection method of moving characteristics of pedestrians in video sequences,'' Master's Thesis, Graduate School of Information Science and Technology, Osaka University, Feb. 2010. (in Japanese)

2.1.4. Detecting optical flow for estimating number of pedestrians passing through virtual gate in video sequences

Snapshot of developed software
Fig: Snapshot of developed software

In recent years, the demand for automatically counting pedestrians in event sites, buildings, or streets has been increased. Our research group has proposed a real-time counting method of pedestrians from video sequences where the target region is crowded and pedestrians are overlapping. In our method, the video sequences are retrieved from a stationary camera, and a liner virtual gate is set at appropriate location in the video sequences. When there is a difference of pixel value between the current frame and the background image at a pixel on the virtual gate, an optical flow whose origin is the pixel is detected. Detected optical flows are clustered based on their direction, size, and location. Then, the number of pedestrians passing through virtual gate is estimated for each cluster based on the size of cluster.

In this research, we proposed a detection method of optical flow as the fundamental step of our counting method. We use block matching algorithm to detect an optical flow from video sequences. By limiting the area of search to surrounding the virtual gate, the calculation amount can be decreased and detailed detection can be accomplished in real time. Through evaluations based on actual video sequences, we confirmed that calculation amount of detecting optical flows is decreased one over two-thousands and one-hundred, by comparing proposal method with traditional block matching method, and 92% of optical flows can be detected successfully in real time.

[Related papers]

  1. Erika Ashikaga, ``Detecting optical flow for estimating number of pedestrians passing through virtual gate in video sequences,'' Bachelor's Thesis, School of Engineering Science, Osaka University, Feb. 2010. (in Japanese)
  2. Erika Ashikaga, Yoshiaki Taniguchi, Go Hasegawa, and Hirotaka Nakano, ``Estimating number of people passing through virtual gate in video sequences,'' Reports of the 250rd Technical Conference of the IIEEJ, pp.129-136, Mar. 2010. (in Japanese)

2.1.5. Time slot assignment algorithms for reducing transmission latency in IEEE 802.16j relay networks

Example of time slot assignment
Fig: Example of time slot assignment

IEEE 802.16j multi-hop relay networks have attracted much attention as cost-effective broadband wireless access networks. Relay networks consists of two kind of fixed stations, base stations and relay stations, and relay stations construct a tree topology whose root is a base station and communicate with the base station by using wireless multi-hop path. Under the wireless multi-hop communications, two stations that exist in the transmission range of each other cannot transmit packets simultaneously due to the radio interference. To avoid this interference, IEEE 802.16j uses time division scheduling mechanism that schedules interfering stations to transmit in different timing by assigns different time slots to the links which interfere with each other as transmission opportunities. This time division scheduling mechanism causes scheduling delay which is the period of time between the arrival of a packet at a relay station and the departure of the packet at the scheduled time slot for the relay station. So, in such wireless multi-hop communications based on IEEE 802.16j, end-to-end transmission latency between a relay station and a base station can be increased by accumulating the scheduling delay at each hop on the path between the user station and the base station.

In this research, we proposed assignment algorithms of time slots for wireless links to reduce the transmission latency between relay stations and base stations. Our proposed algorithm is based on the existing method which aims better network throughput and small frame length, and it changes the order of time slot assignment to decrease the transmission latency without increasing the frame length. The proposed method also accommodates the weighted time slot assignment, which is consistent with IEEE 802.16j specifications. Performance evaluations are conducted through both of simulation experiments and numerical calculations. The evaluation results exhibit that the proposed algorithm can decrease the transmission latency by up to 25% in downward transmission and up to 20% in upward transmission compared with the random assignment algorithm in IEEE 802.16j in case of high traffic load. It also shows that the proposed algorithm can provide a time slot assignment with smaller transmission latency in shorter calculation time.

[Related papers]

  1. Rintaro Ishii, ``Time slot assignment algorithms for reducing transmission latency in IEEE 802.16j multi-hop relay networks,'' Master’s Thesis, Graduate School of Information Science and Technology, Osaka University, Feb. 2010.
  2. Rintaro Ishii, Go Hasegawa, Yoshiaki Taniguchi, and Hirotaka Nakano, ``Time slot assignment algorithms in IEEE 802.16 multi-hop relay networks,'' in Proceedings of the 6th International Conference on Networking and Services (ICNS 2010), pp.265-270, Mar. 2010. [paper]

2.1.6. Improving coverage area quality using physical topology information in IEEE 802.16j relay networks

Estimation of the distance of the nearest neighbor
Fig: Estimation of the distance of the nearest neighbor

In wireless relay networks based on IEEE 802.16j, each relay node has its own service area that provides wireless Internet access service to the client terminal. The performance of such networks is heavily affected by how each relay node determines its service area size. In order to determine the service area size for each relay node, it is important to use the location information of other neighboring nodes and their service area sizes. However, in general, such information is completely unknown or only partially known. In this research, we introduce three methods by which to determine the service area size, each of which assumes a different level of the knowledge regarding neighboring nodes. We conduct extensive simulation experiments to evaluate the performance of these three methods in terms of coverage ratio, service area overlap characteristics, energy consumption, and utilization efficiency of wireless network resources. We confirm the trade-off relationships between the knowledge level and performance for these three methods.

[Related papers]

  1. Shoichi Takemori, Go Hasegawa, Yoshiaki Taniguchi, and Hirotaka Nakano, ``Improving coverage area quality using physical topology information in IEEE 802.16 mesh networks,'' in Proceedings of the 3rd International Conference on Mobile Ubiquitous Computing, Systems, Services and Technologies (UBICOMM 2009), pp.163-168, Oct. 2009. (Best Paper Award) [paper]

2.1.7. Node repositioning for performance improvement in IEEE 802.16j relay networks

The movement range of a node
Fig: The movement range of a node

The network based on IEEE 802.16j standard is getting attention as a technology which provides a wireless broadband service for the area where the construction of the wired network is difficult or metropolitan region by the features of the network such as high-speed data transmission, wide-range transmission region, easiness of construction and adaptation to mobile communication system. In IEEE 802.16j, the problem of radio interferences between links is solved by adopting the scheduling scheme called Orthogonal Frequency Division Multiple Access (OFDMA) which combines the time-division system and frequency division system. The time-division system divides channel into the unit of frames for a fixed time, and each link communicates by using the time slot into which the frame is divided for a fixed time. Avoiding radio interferences by assigning different time slots to links with radio interferences enables efficient communication.

In the wireless relay network using the time-division system, frame length, which depends on number of time slots to enable all links in the network to communicate without radio interferences are increased, when radio interferences occur between links which demand huge amounts of traffic and between many links. At this time, repositioning relay nodes in the network may be able to resolve or reduce radio interferences to decrease number of time slots needed in the network. Thus, node repositioning may improve the network throughput. However, there is no example of having examined the throughput improvement by node repositioning in the wireless relay network.

In this research, we evaluate the influence that repositioning relay nodes gives to the communication performance in the IEEE 802.16j relay network. First of all, we define the movement condition of a relay node, and then evaluate the change of the frame length by repositioning relay nodes in networks with various number of nodes, maximum transmission distance and interference ratio. As a result, we show that it is possible to reduce the frame length of about the maximum 16% by repositioning one node and to reduce the frame length of the maximum 22% by repositioning more relay nodes one by one.

[Related papers]

  1. Takafumi Shigefuji, ``Node repositioning for performance improvement in IEEE 802.16j relay networks,'' Bachelor's Thesis, School of Engineering Science, Osaka University, Feb. 2010.

2.1.8. Performance evaluation of IEEE 802.16j relay networks considering radio wave blocking by obstacles

Relay network with obstacles
Fig: Relay network with obstacles

Nowadays, mobile communication terminals are rapidly widespread and people have accessed Internet all over the world. Wireless radio communications are essential to enable the access. IEEE 802.16j multi hop relay network is attracting attention very much. It is different from star network using by IEEE 802.11. In IEEE 802.16j, nodes configure tree-based network with wireless links and provide communication over the wide range by means of multi hop communication between mesh nodes.

Until now, a network model which defined transmission range and interference range of transmission node as a circle is used when evaluation network throughput or service area of IEEE 802.16j multi hop relay network. In existing evaluation of relay network using the model, it is not assumed obstacles and does not consider the influence of radio waves by obstacles. Typically, radio waves are blocked, reected, or diffracted by obstacles. Therefore, it is possible that network performance decrease because obstacles blocked radio waves of nodes. The influence of interference by nearby nodes becomes small, and then the connection and interference of nodes in relay network may change. The change of connection and interference affect the network throughput because IEEE 802.16j supports Time Division Multiple Access (TDMA). Considering obstacles, some node become isolated nodes which cannot transmit any nodes. It in uences service area which relay network provide to client terminals. Consequently, evaluation of relay network considering obstacles is important in order to examine the possible application of relay network in real world.

This research investigates the performance of IEEE 802.16j relay network considering the in uence of radio waves by obstacles. Specfically, obstacles which only block radio waves set in the existing network model. This research evaluates the service area of the relay network, frame size and path length from gateway node to relay node with simulation using this network model. After simulation, it reveals that service area does not decrease so much when the number of obstacles is comparatively little, and then increase the service area in little increase of frame size by adding relay nodes. This research also evaluates network performance using a model supposed architectural design in Toyonaka campus of Osaka university. It clears up the association of network parameter by comparing to an evaluation result of a model which set obstacle randomly.

[Related papers]

  1. Yuki Ise, ``Performance evaluation of IEEE 802.16j relay networks considering radio wave blocking by obstacles,'' Bachelor's Thesis, School of Engineering Science, Osaka University, Feb. 2010.

2.1.9. Time slot assignment algorithms for reducing transmission latency in IEEE 802.16j camera relay networks

A highly-developed street view
Fig: A highly-developed street view

Street view is new function of Google Map and it enables that users can view scenery of street from viewpoints of human. In this research, we consider a highly-developed street view that users can view current scenery of street. In the highly-developed street view, many cameras are assumed to be attached on electric pole, street lamp, buildings, and so on. Cameras have wireless communication capability, and we assume that IEEE 802.16j multi-hop relay network is used among cameras. A data center collects video data from cameras through base stations, deposits the video data to its buffer, and provides it to users.

Although many issues should be discussed to realize the highly-developed street view, we focus wireless networks among cameras and a base station. In this research, we propose a time slot assignment algorithm for reducing transmission latency, and evaluate it though simulation experiments.

2.1.10. Proposal and evaluation of an interference model based on SNR

Protocol model and SNR model
Fig: Protocol model and SNR model

In many research work of wireless multi-hop networks, interference range of wireless transmission is just assumed as a circle (this interference model is called protocol model). By using protocol model, the results of graph theory can be used to the problem of wireless multi-hop networks, however, the model can not handle detailed behavior of actual wireless signals, e.g. fading of wireless signals, capture effect, and so on. On the other hand, based on signal to noise ratio (SNR), detailed behavior of wireless signals can be handled, however, results of graph theory can not be used enymore.

In this research, we propose new interference model by combining protocol model and SNR model. The new interference model can handle detailed behavior of wireless signals, while results of graph theory can be used. We evaluate wireless multi-hop networks with/without our interference model, and show its effectiveness through simulation evaluations.

2.2. Research on architecture of transport layer for next-generation high-speed network

The key technology for achieving high-speed and efficient transfer of data between end hosts is transport protocol technology. In TCP, which is the protocol used by the Internet, an end host can autonomously detect the state of congestion in the network and decide on a transfer rate accordingly. This capability lies at the heart of the end-to-end principle, which, as mentioned earlier, is the basic idea behind the Internet. Here, the possibility is also high that increasing the processing speed of an end host can raise its level of adaptability. Although a control process that assumes end-host adaptability must be considered for routers in the network, such control, if it can be achieved, should enable the construction of a high-performance network rich in autonomy and adaptability. This research is concerned with high-speed transport protocol of this type and with transport architecture in overlay networks that aim to provide special services such as a contents distribution network (CDN) or data grid on top of the IP network.

2.2.1. Reduction of inter-ISP transit cost caused by overlay routing

ISP transit cost
Fig: ISP transit cost

Overlay routing is an application-level routing mechanism on overlay networks. Existing researches on overlay routing revealed that it can improve user-perceived performance by choosing a path based on network performance metrics such as end-to-end latency and available bandwidth. On the other hand, overlay routing may harm ISPs' cost structure because of the policy mismatch between IP routing and overlay routing. IP routing provided by ISPs is generally configured based on the monetary cost of links interconnecting to neighboring ISPs. On the other hand, the overlay routing selects the path based on end-to-end network performance. Consequently, the overlay routing may utilize paths which traverse additional transit links between ISPs, which requires additional inter-ISP transit cost. One possible solution to this problem is to limit the overlay routing not to utilize paths which increase inter-ISP transit cost largely.

In this research, the author proposes a method to reduce inter-ISP transit cost caused by overlay routing. For this purpose, the number of inter-ISP transit links on a path is utilized as a metric of transit cost and the overlay path is chosen to decrease the transit cost while keeping the effectiveness of overlay routing itself. Since there is no public information on the number of transit links on a path, and since it cannot be obtained by simple end-to-end measurement methods, the author builds up a method to estimate the number of transit links on a path from end-to-end network performance values which can be measured easily by overlay nodes. Through the multiple regression analysis of end-to-end network performance values, the regression equation to estimate the number of transit links is obtained.

To confirm the effectiveness of the proposed method, the author first assesses the estimation accuracy of the regression equation and then evaluates the performance of limited overlay routing which suppresses the number of transit links determined by the proposed estimation method. Through extensive evaluations using measurement results in the actual network environment, the author confirms that the absolute underestimation error in the number of transit links on overlay-level paths is smaller than one in almost 80\% of overlay paths, and that the overlay routing with the proposed method can achieve almost the same degree of improvement as that without limitation, while decreasing the number of the transit links traversed by overlay-routed paths.

[Related papers]

  1. Go Hasegawa, Yuichiro Hiraoka, and Masayuki Murata, ``Effectiveness of overlay routing based on delay and bandwidth information,'' IEICE Transactions on Communications, vol.E92-B, no.4, pp.1222-1232, Apr. 2009. [paper]
  2. Go Hasegawa, Yuichiro Hiraoka, and Masayuki Murata, ``Evaluation of free-riding traffic problem in overlay routing and its mitigation method,'' in Proceedings of the 5th International Conference on Networking and Services (ICNS 2009), pp.210-215, Apr. 2009. [paper]
  3. Go Hasegawa, Yuichiro Hiraoka, and Masayuki Murata, ``Evaluation of free-riding traffic problem in overlay routing and its mitigation method,'' IEICE Transactions on Communications, vol.E92-B, no.12, pp.3774-3783, Dec. 2009. (Best Paper Award) [paper]
  4. Kazuhito Matsuda, Go Hasegawa, and Masayuki Murata, ``Decreasing ISP transit cost in overlay routing based on multiple regression analysis,'' in Proceedings of the International Conference on Information Networking 2010 (ICOIN 2010), Jan. 2010.
  5. Kazuhito Matsuda, ``A study on reduction of inter-ISP transit cost caused by overlay routing,'' Master’s Thesis, Graduate School of Information Science and Technology, Osaka University, Feb. 2010.

2.2.2. Proactive recovery from multiple failures utilizing overlay networking technique

Multiple simultaneous failures of overlay network
Fig: Multiple simultaneous failures of overlay network

Recent network applications require high network availability for maintaining continuous connectivity. However, most of existing routing protocols in the current Internet have problems in recovering from multiple simultaneous failures, where they require a long time for routing convergence after detecting such failures since the network equipment has to detect the failures, re-calculate routing configurations, and propagate the configurations throughout the network. For example, BGP requires considerable time, which is from a few minutes to several days, to converge routing configurations, especially for large-scale failures or certain types of network topologies. Essentially, the routing convergence time in BGP has no theoretical upper bound, and there are many situations in which the routing convergence time increases significantly, as in the count-to-infinity problem. Accordingly, various methods to improve the routing convergence time in BGP have been proposed, however, most of them require modifications to BGP itself. Therefore, they cannot be applied to the current Internet environment in short time due to difficulties in interoperability and the need for the standardization process.

In this research, the author proposes a proactive recovery method against multiple simultaneous failures for large-scale packet switching networks. The proposed method exploits the overlay networking technique to realize fast and effective recovery from failures, since it is implemented at application layer. Specifically, it constructs multiple logical network topologies assuming various failure patterns in advance. When a failure is detected, the proposed method can immediately recover from the failure by utilizing the appropriate topology to the failure, without waiting routing convergence in the underlay network. Furthermore, the proposed method considers the correlation among overlay links in terms of utilizing underlay link to construct the effective topologies for recovering from multiple simultaneous failures. The proposed method also could construct the topologies for failure recovery at each overlay node in a distributed fashion.

Through numerical evaluations in terms of the overlay reachability and the average path length after failure recovery, the author shows that the proposed method improves the overlay network reachability from 51% to 97%, while keeping the path length to be enough small, when 25% underlay links are down simultaneously.

[Related papers]

  1. Takuro Horie, Go Hasegawa, Satoshi Kamei, and Masayuki Murata, ``A new method of proactive recovery mechanism for large-scale network failures,'' in Proceedings of the IEEE 23rd International Conference on Advanced Information Networking and Applications (AINA-09), pp.951-958, May 2009. [paper]
  2. Takuro Horie, Go Hasegawa, Satoshi Kamei, and Masayuki Murata, ``On network traffic concentration and updating interval for proactive recovery method against large-scale network failures,'' in Proceedings of the 2009 Australasian Telecommunications Networks and Applications Conference (ATNAC 2009), Nov. 2009. [paper]
  3. Takuro Horie, ``Proactive recovery from multiple failures utilizing overlay networking technique,'' Master’s Thesis, Graduate School of Information Science and Technology, Osaka University, Feb. 2010.

2.2.3. Scalable and density-aware measurement strategies for overlay networks

Density-aware measurement strategies for overlay networks
Fig: Density-aware measurement strategies for overlay networks

In overlay networks, when we consider the effective and accurate measurement of the underlay IP network between overlay nodes, it is important to take care the density of the overlay nodes to the number of routers in the network. In this research, we propose the density-aware measurement strategies for overlay networks. Our method can reduce the number of measurements required for obtaining the full-mesh measurement results by 1/50–1/100. We also confirm that the overlay node density highly affects the path overlap frequency, which is important factor when the overlay node can recognize the path overlapping in the network.

[Related papers]

  1. Go Hasegawa and Masayuki Murata, ``Scalable and density-aware measurement strategies for overlay networks,'' in Proceedings of the 4th International Conference on Internet Monitoring and Protection (ICIMP 2009), pp.21-26, May 2009. [paper]

2.2.4. Congestion control mechanisms for alleviating TCP unfairness in wireless LAN environment

Experimental environment
Fig: Experimental environment

Per-flow unfairness among TCP flows in IEEE 802.11 wireless LAN environment has been reported in past literature. Many researchers have proposed various solutions for alleviating the unfairness. These solutions diminish TCP throughput unfairness by mostly modifying MAC protocol or queue management mechanisms at access points based on detailed information in wireless LAN such as the number of coexisting stations, flow types, and flow rates. However, MAC protocols of wireless access points are generally implemented in hardware, so it takes large cost to change them. Moreover, collecting the detailed information of the network increase the network complexity.

In this research, the author proposes a simple modification to TCP congestion control mechanisms to alleviate the unfairness, which activates the congestion control when detecting TCP ACK packet losses. As an evaluation metric of fairness among users in above unfairness problems, Jain’s fairness index has been generally utilized. Some solutions which addressed bandwidth sharing among coexisting flows (users) would alleviate the unfairness while degrading the total bandwidth utilization. Since Jain’s fairness index depends only on the variation of allocated values to users, the index cannot evaluate such trade-off relationships between fairness and throughput accurately. Therefore, in this research, the author proposes a new metric, which can evaluate the trade-off relationships between per-flow fairness and bandwidth utilization at the network bottleneck.

Through experimental evaluations using real wireless LAN environments, the author presents that the proposed method is significantly effective not only for TCP fairness among upstream flows but also for fairness between upstream and downstream flows, and that it can take quite better trade-off between fairness and bandwidth utilization regardless of vendor implementations of access points and wireless interface cards.

[Related papers]

  1. Masafumi Hashimoto, ``Congestion control mechanisms for alleviating TCP unfairness in wireless LAN environment,'' Master’s Thesis, Graduate School of Information Science and Technology, Osaka University, Feb. 2010.

2.2.5. Increasing robustness to environmental changes for congestion control mechanisms

Addition of self-induced oscillation
Fig: Addition of self-induced oscillation

We have proposed a bandwidth-based TCP congestion control mechanism with an inline network measurement technique. The proposed method, named as TCP Symbiosis, controls the window size based on the bandwidth information unlike the standard TCP and the recent works on loss-based, delay-based and hybrid congestion control mechanisms. TCP Symbiosis has the effectiveness in terms of average throughput, scalability to the bandwidth-delay product, convergence time, stability, and fairness among connections. However, the performance of TCP Symbiosis highly depends on the measurement results of available bandwidth and environmental changes. In this research, we redesign TCP Symbiosis to deal with the measurement error and environmental change. First, we propose the dynamic parameter setting algorithm based on the variance of the measured available bandwidth. Second, for the purpose of absorbing the ill-effect of environmental change, we intensionally add self-induced oscillation to the congestion window size of TCP connection. We confirm that the proposed method has the effectiveness without change in the basic nature of TCP Symbiosis.

[Related papers]

  1. Mizuho Kodama, Go Hasegawa, and Masayuki Murata, “Bandwidth-based congestion control for TCP: measurement noise-aware parameter settings and self-induced oscillation,” in Proceedings of the 2nd International Workshop on the Network of the Future (Future-Network'09), June 2009. [paper]

2.2.6. Improving interactive user experience on thin clients

Think-client system
Fig: Thin-client system

Return network traffic (from servers to clients) in thin-client systems is modeled as a mixture of interactive data flows corresponding to keystrokes and bulk data flows related to screen updates. Users are very sensitive to delay and jitter of the former flows. Thus our goal is to minimize the latency of interactive data transfer without increasing latency of bulk data transfer. Through simulation experiments, we determine that the main factors causing end-to-end delay in the interactive data transfer are queuing delay in the router and buffering delay in the server. When we apply two techniques: priority queuing of interactive data flows at the router and using TCP SACK option, the average end-to-end delay can be reduced. However, several servers could take more than a second to send large bulk data flows; this delays the transmission of following interactive data flows. We then develop TCP optimization mechanisms: modifying recalculation of the retransmission timeout value and temporarily turning off the TCP SACK control, and demonstrate that they can overcome the negative effects of the existing techniques.

[Related papers]

  1. Yukio Ogawa, Go Hasegawa, and Masayuki Murata, ``A transport layer approach for improving interactive user experience on thin clients,'' in Proceedings of the 2009 Australasian Telecommunications Networks and Applications Conference (ATNAC 2009), Nov. 2009. [paper]

2.2.7. Performance evaluation of distributed computing environment considering power consumption

Distributed computing environment
Fig: Distributed computing environment

When information systems are consolidated in a large data center, a huge amount of energy is consumed for transferring massive amounts of data to the data center through a wide area network. Our approach is to reduce the network power consumption by distributing servers capable of reducing or localizing traffic across the network. In this research, we develop the models of applications, their traffic and a network system for transferring the traffic. We also introduce the models of router's and server's energy consumption, and formulate the power consumption caused by the traffic. Then, we evaluate the power consumption reduction as a result of traffic reduction by the distributed servers. Numerical evaluation results show that the whole power consumption reduces by about 20 percent when the more servers are added to the network; it increases due to the server power consumption when a lot of servers are added to the network.

[Related papers]

  1. Yukio Ogawa, Go Hasegawa, Masayuki Murata, Shinji Nishimura, ``Performance evaluation of distributed computing environment considering power consumption,'' IEICE Technical Report, (IN2009-172), pp.169-174, Mar. 2010. (in Japanese) [paper]

3. Publications

3.1. Journal papers

  1. Go Hasegawa, Yuichiro Hiraoka, and Masayuki Murata, ``Effectiveness of overlay routing based on delay and bandwidth information,'' IEICE Transactions on Communications, vol.E92-B, no.4, pp.1222-1232, Apr. 2009. [paper]
  2. Go Hasegawa, Yuichiro Hiraoka, and Masayuki Murata, ``Evaluation of free-riding traffic problem in overlay routing and its mitigation method,'' IEICE Transactions on Communications, vol.E92-B, no.12, pp.3774-3783, Dec. 2009. (Best Paper Award) [paper]
  3. Hiroshi Tokito, Masahiro Sasabe, Go Hasegawa, and Hirotaka Nakano, ``Load-balanced and interference-aware spanning tree construction algorithm for TDMA-based wireless mesh networks,'' IEICE Transactions on Communications, vol.E93-B, no.1, pp.99-110, Jan. 2010. [paper]

3.2. International conference papers

  1. Yoshiaki Taniguchi, Tomoya Kitani, and Kenji Leibnitz, ``An airdrop deployment method for sensor nodes with coordinated gliding and falling,'' in Proceedings of the Workshop on Sensor Networks for Earth and Space Science Applications (ESSA 2009), pp.48-48, Apr. 2009.
  2. Go Hasegawa, Yuichiro Hiraoka, and Masayuki Murata, ``Evaluation of free-riding traffic problem in overlay routing and its mitigation method,'' in Proceedings of the 5th International Conference on Networking and Services (ICNS 2009), pp.210-215, Apr. 2009. [paper]
  3. Go Hasegawa and Masayuki Murata, ``Scalable and density-aware measurement strategies for overlay networks,'' in Proceedings of the 4th International Conference on Internet Monitoring and Protection (ICIMP 2009), pp.21-26, May 2009. [paper]
  4. Takuro Horie, Go Hasegawa, Satoshi Kamei, and Masayuki Murata, ``A new method of proactive recovery mechanism for large-scale network failures,'' in Proceedings of the IEEE 23rd International Conference on Advanced Information Networking and Applications (AINA-09), pp.951-958, May 2009. [paper]
  5. Mizuho Kodama, Go Hasegawa, and Masayuki Murata, ``Bandwidth-based congestion control for TCP: measurement noise-aware parameter settings and self-induced oscillation,'' in Proceedings of the 2nd International Workshop on the Network of the Future (Future-Network'09), June 2009. [paper]
  6. Sayaka Kuriyama, Go Hasegawa, and Hirotaka Nakano, ``Real-time estimation method of the number of pedestrians in video sequences,'' in Proceedings of the 4th International Conference on Digital Telecommunications (ICDT 2009), pp.65-70, July 2009. [paper]
  7. Shoichi Takemori, Go Hasegawa, Yoshiaki Taniguchi, and Hirotaka Nakano, ``Improving coverage area quality using physical topology information in IEEE 802.16 mesh networks,'' in Proceedings of the 3rd International Conference on Mobile Ubiquitous Computing, Systems, Services and Technologies (UBICOMM 2009), pp.163-168, Oct. 2009. (Best Paper Award) [paper]
  8. Takuro Horie, Go Hasegawa, Satoshi Kamei, and Masayuki Murata, ``On network traffic concentration and updating interval for proactive recovery method against large-scale network failures,'' in Proceedings of the 2009 Australasian Telecommunications Networks and Applications Conference (ATNAC 2009), Nov. 2009. [paper]
  9. Yukio Ogawa, Go Hasegawa, and Masayuki Murata, ``A transport layer approach for improving interactive user experience on thin clients,'' in Proceedings of the 2009 Australasian Telecommunications Networks and Applications Conference (ATNAC 2009), Nov. 2009. [paper]
  10. Masakazu Murata, Yoshiaki Taniguchi, Go Hasegawa, and Hirotaka Nakano, ``Improvement and evaluation of scenario-type hypothesis object tracking,'' in Proceedings of the 2nd International Workshop on Sensor Networks and Ambient Intelligence (SeNAmI 2009), Dec. 2009. [paper]
  11. Kazuhito Matsuda, Go Hasegawa, and Masayuki Murata, ``Decreasing ISP transit cost in overlay routing based on multiple regression analysis,'' in Proceedings of the International Conference on Information Networking 2010 (ICOIN 2010), Jan. 2010.
  12. Masakazu Murata, Yoshiaki Taniguchi, Go Hasegawa, and Hirotaka Nakano, ``An object tracking method based on Scenario-type Hypothesis Tracking in segmented multiple regions,'' in Proceedings of the 6th International Conference on Networking and Services (ICNS 2010), pp.200-205, Mar. 2010. [paper]
  13. Rintaro Ishii, Go Hasegawa, Yoshiaki Taniguchi, and Hirotaka Nakano, ``Time slot assignment algorithms in IEEE 802.16 multi-hop relay networks,'' in Proceedings of the 6th International Conference on Networking and Services (ICNS 2010), pp.265-270, Mar. 2010. [paper]

3.3. Theses

3.3.1. Masters' Theses

  1. Rintaro Ishii, ``Time slot assignment algorithms for reducing transmission latency in IEEE 802.16j multi-hop relay networks,'' Master's Thesis, Graduate School of Information Science and Technology, Osaka University, Feb. 2010.
  2. Sayaka Kuriyama, ``Detection method of moving characteristics of pedestrians in video sequences,'' Master's Thesis, Graduate School of Information Science and Technology, Osaka University, Feb. 2010. (in Japanese)
  3. Masafumi Hashimoto, ``Congestion control mechanisms for alleviating TCP unfairness in wireless LAN environment,'' Master's Thesis, Graduate School of Information Science and Technology, Osaka University, Feb. 2010.
  4. Takuro Horie, ``Proactive recovery from multiple failures utilizing overlay networking technique,'' Master's Thesis, Graduate School of Information Science and Technology, Osaka University, Feb. 2010.
  5. Kazuhito Matsuda, ``A study on reduction of inter-ISP transit cost caused by overlay routing,'' Master's Thesis, Graduate School of Information Science and Technology, Osaka University, Feb. 2010.
  6. Masakazu Murata, ``Scenario-type hypothesis object tracking with indoor sensor networks,'' Master's Thesis, Graduate School of Information Science and Technology, Osaka University, Feb. 2010.

3.3.2. Bachelors' Theses

  1. Erika Ashikaga, ``Detecting optical flow for estimating number of pedestrians passing through virtual gate in video sequences,'' Bachelor's Thesis, School of Engineering Science, Osaka University, Feb. 2010. (in Japanese)
  2. Yuki Ise, ``Performance evaluation of IEEE 802.16j relay networks considering radio wave blocking by obstacles,'' Bachelor's Thesis, School of Engineering Science, Osaka University, Feb. 2010. (in Japanese)
  3. Takafumi Shigefuji, ``Node repositioning for performance improvement in IEEE 802.16j relay networks,'' Bachelor's Thesis, School of Engineering Science, Osaka University, Feb. 2010. (in Japanese)