Akio KAWABATA Bijoy CHAND CHATTERJEE Eiji OKI
This paper proposes a network design model, considering data consistency for a delay-sensitive distributed processing system. The data consistency is determined by collating the own state and the states of slave servers. If the state is mismatched with other servers, the rollback process is initiated to modify the state to guarantee data consistency. In the proposed model, the selected servers and the master-slave server pairs are determined to minimize the end-to-end delay and the delay for data consistency. We formulate the proposed model as an integer linear programming problem. We evaluate the delay performance and computation time. We evaluate the proposed model in two network models with two, three, and four slave servers. The proposed model reduces the delay for data consistency by up to 31 percent compared to that of a typical model that collates the status of all servers at one master server. The computation time is a few seconds, which is an acceptable time for network design before service launch. These results indicate that the proposed model is effective for delay-sensitive applications.
In this paper, we investigate the evolution of an optical network architecture and discuss the future direction of research on optical network design and control. We review existing research on optical network design and control and present some open challenges. One of the important open challenges lies in multilayer resource optimization including IT and optical network resources. We propose an adaptive joint optimization method of IT resources and optical spectrum under time-varying traffic demand in optical networks while avoiding an increase in operation cost. We formulate the problem as mixed integer linear programming and then quantitatively evaluate the trade-off relationship between the optimality of reconfiguration and operation cost. We demonstrate that we can achieve sufficient network performance through the adaptive joint optimization while suppressing an increase in operation cost.
Akio KAWABATA Bijoy CHAND CHATTERJEE Eiji OKI
When mission-critical applications are provided over a network, high availability is required in addition to a low delay. This paper proposes a multi-homing network design model, named MHND, that achieves low delay, high availability, and the order guarantee of events. MHND maintains the event occurrence order with a multi-homing configuration using conservative synchronization. We formulate MHND as an integer linear programming problem to minimize the delay. We prove that the distributed server allocation problem with MHND is NP-complete. Numerical results indicate that, as a multi-homing number, which is the number of servers to which each user belongs, increases, the availability increases while increasing the delay. Noteworthy, two or more multi-homing can achieve approximately an order of magnitude higher availability compared to that of conventional single-homing at the expense of a delay increase up to two times. By using MHND, flexible network design is achieved based on the acceptable delay in service and the required availability.
Akio KAWABATA Takuya TOJO Bijoy CHAND CHATTERJEE Eiji OKI
Mission-critical monitoring services, such as finding criminals with a monitoring camera, require rapid detection of newly updated data, where suppressing delay is desirable. Taking this direction, this paper proposes a network design scheme to minimize this delay for monitoring services that consist of Internet-of-Things (IoT) devices located at terminal endpoints (TEs), databases (DB), and applications (APLs). The proposed scheme determines the allocation of DB and APLs and the selection of the server to which TE belongs. DB and APL are allocated on an optimal server from multiple servers in the network. We formulate the proposed network design scheme as an integer linear programming problem. The delay reduction effect of the proposed scheme is evaluated under two network topologies and a monitoring camera system network. In the two network topologies, the delays of the proposed scheme are 78 and 80 percent, compared to that of the conventional scheme. In the monitoring camera system network, the delay of the proposed scheme is 77 percent compared to that of the conventional scheme. These results indicate that the proposed scheme reduces the delay compared to the conventional scheme where APLs are located near TEs. The computation time of the proposed scheme is acceptable for the design phase before the service is launched. The proposed scheme can contribute to a network design that detects newly added objects quickly in the monitoring services.
Yoshihiro MURASHIMA Taishin NAKAMURA Hisashi YAMAMOTO Xiao XIAO
In a network topology design problem, it is important to analyze the reliability and construction cost of complex network systems. This paper addresses a topological optimization problem of minimizing the total cost of a network system with separate subsystems under a reliability constraint. To solve this problem, we develop three algorithms. The first algorithm finds an exact solution. The second one finds an exact solution, specialized for a system with identical subsystems. The third one is a heuristic algorithm, which finds an approximate solution when a network system has several identical subsystems. We also conduct numerical experiments and demonstrate the efficacy and efficiency of the developed algorithms.
Keisuke KAYANO Yojiro MORI Hiroshi HASEGAWA Ken-ichi SATO Shoichiro ODA Setsuo YOSHIDA Takeshi HOSHIDA
The spectral efficiency of photonic networks can be enhanced by the use of higher modulation orders and narrower channel bandwidth. Unfortunately, these solutions are precluded by the margins required to offset uncertainties in system performance. Furthermore, as recently highlighted, the disaggregation of optical transport systems increases the required margin. We propose here highly spectrally efficient networks, whose margins are minimized by transmission-quality-aware adaptive modulation-order/channel-bandwidth assignment enabled by optical performance monitoring (OPM). Their effectiveness is confirmed by experiments on 400-Gbps dual-polarization quadrature phase shift keying (DP-QPSK) and 16-ary quadrature amplitude modulation (DP-16QAM) signals with the application of recently developed Q-factor-based OPM. Four-subcarrier 32-Gbaud DP-QPSK signals within 150/162.5/175GHz and two-subcarrier 32-Gbaud DP-16QAM signals within 75/87.5/100GHz are experimentally analyzed. Numerical network simulations in conjunction with the experimental results demonstrate that the proposed scheme can drastically improve network spectral efficiency.
Yuma ABE Masaki OGURA Hiroyuki TSUJI Amane MIURA Shuichi ADACHI
Satellite communications (SATCOM) systems play important roles in wireless communication systems. In the future, they will be required to accommodate rapidly increasing communication requests from various types of users. Therefore, we propose a framework for efficient resource management in large-scale SATCOM systems that integrate multiple satellites. Such systems contain hundreds of thousands of communication satellites, user terminals, and gateway stations; thus, our proposed framework enables simpler and more reliable communication between users and satellites. To manage and control this system efficiently, we formulate an optimization problem that designs the network structure and allocates communication resources for a large-scale SATCOM system. In this mixed integer programming problem, we allow the cost function to be a combination of various factors so that SATCOM operators can design the network according to their individual management strategies. These factors include the total allocated bandwidth to users, the number of satellites and gateway stations to be used, and the number of total satellite handovers. Our numerical simulations show that the proposed management strategy outperforms a conventional strategy in which a user can connect to only one specific satellite determined in advance. Furthermore, we determine the effect of the number of satellites in the system on overall system performance.
Ryo HAMAMOTO Chisa TAKANO Hiroyasu OBATA Kenji ISHIDA
Wireless Local Area Networks (WLANs) based on the IEEE 802.11 standard have been increasingly used. Access Points (APs) are being established in various public places, such as railway stations and airports, as well as private residences. Moreover, the rate of public WLAN services continues to increase. Throughput prediction of an AP in a multi-rate environment, i.e., predicting the amount of receipt data (including retransmission packets at an AP), is an important issue for wireless network design. Moreover, it is important to solve AP placement and selection problems. To realize the throughput prediction, we have proposed an AP throughput prediction method that considers terminal distribution. We compared the predicted throughput of the proposed method with a method that uses linear order computation and confirmed the performance of the proposed method, not by a network simulator but by the numerical computation. However, it is necessary to consider the impact of CSMA/CA in the MAC layer, because throughput is greatly influenced by frame collision. In this paper, we derive an effective transmission rate considering CSMA/CA and frame collision. We then compare the throughput obtained using the network simulator NS2 with a prediction value calculated by the proposed method. Simulation results show that the maximum relative error of the proposed method is approximately 6% and 15% for UDP and TCP, respectively, while that is approximately 17% and 21% in existing method.
Designing a backbone IP network, especially to support both unicast and multicast traffic under delay constraints, is a difficult problem. Real network design must consider cost, performance and reliability. Therefore, a simulator can help a network designer to test the functionality of the network before the implementation. This paper proposes a heuristic design algorithm called D-MENTOR, and the algorithm was developed by programming based on Mesh Network Topological Optimization and Routing Version 2 (MENTOR-II) to integrate as a new module of DElite tool. The simulation results show that, in almost all test cases, the proposed algorithm yields lower installation cost.
Daisuke SATOH Hiromichi KAWANO Yoshiyuki CHIBA
We demonstrated that load balancing using actual subscriber extension numbers was practical and effective against traffic congestion after a disaster based on actual data. We investigated the ratios of the same subscriber extension numbers in each prefecture and found that most of them were located almost evenly all over the country without being concentrated in a particular area. The ratio of every number except for the fourth-last digit in the last group of four numbers in a telephone number was used almost equally and located almost evenly all over the country. Tolerance against overload in the last, second-, and third-last single digits stays close to that in the ideal situation if we assume that each session initiation protocol server has a capacity in accordance with the ratio of each number on every single digit in the last group of four numbers in Japan. Although tolerance against overload in double-, triple-, and quadruple-digit numbers does not stay close to that in the ideal situation, it still remains sufficiently high in the case of double- and triple-digit numbers. Although tolerance against overload in the quadruple-digit numbers becomes low, disaster congestion is still not likely to occur in almost half of the area of Japan (23 out of 47 prefectures).
Takafumi TANAKA Masahiko JINNO
Many detailed studies ranging from networking to hardware as well as standardization activities over the last few years have advanced the performance of the elastic optical network. Thanks to these intensive works, the elastic optical network has been becoming feasible. This paper reviews the recent advances in the elastic optical network from the aspects of networking technology and hardware design. For the former, we focus on the efficient elastic network design technology related to routing and spectrum assignment (RSA) of elastic optical paths including network optimization or standardization activities, and for the latter, two key enabling technologies are discussed: elastic transponders/regenerators and gridless optical switches. Making closely-dependent networking and hardware technologies work synergistically is the key factor in implementing truly effective elastic optical networks.
Tatsumi TAKAGI Hiroshi HASEGAWA Ken-ichi SATO Yoshiaki SONE Akira HIRANO Masahiko JINNO
We propose optical path routing and frequency slot assignment algorithms that can make the best use of elastic optical paths and the capabilities of distance adaptive modulation. Due to the computational difficulty of the assignment problem, we develop algorithms for 1+1 dedicated/1:1 shared protected ring networks and unprotected mesh networks to that fully utilize the characteristics of the topologies. Numerical experiments elucidate that the introduction of path elasticity and distance adaptive modulation significantly reduce the occupied bandwidth.
Daisuke SATOH Kyoko ASHITAGAWA
We present a session initiation protocol (SIP) network design for a voice-over-IP network to prevent congestion caused by people calling friends and family after a disaster. The design increases the capacity of SIP servers in a network by using all of the SIP servers equally. It takes advantage of the fact that equipment for voice data packets is different from equipment for signaling packets in SIP networks. Furthermore, the design achieves simple routing on the basis of telephone numbers. We evaluated the performance of our design in preventing congestion through simulation. We showed that the proposed design has roughly 20 times more capacity, which is 57 times the normal load, than the conventional design if a disaster were to occur in Niigata Prefecture struck by the Chuetsu earthquake in 2004.
The transport network paradigm is changing as evidenced by IP convergence and the divergence of architectures and technologies. Harnessing the full power of light will spur the creation of new broadband and ubiquitous services networks. To attain this, however, not only must photonic technologies be optimized, but they must also be coordinated with complementary electrical technologies. With regard to photonic network design technologies, further developments are necessary including very large scale network design, quasi-dynamic network design, and multi-layer optical path network design.
Takuro FUKUNAGA Hiroshi NAGAMOCHI
We consider a problem for constructing a minimum cost r-edge-connected multigraph in which degree d(v) of each vertex v ∈ V is specified. In this paper, we propose a 3-approximation algorithm for this problem under the assumption that edge cost is metric, r(u,v) ∈ {1,2} for each u,v ∈ V, and d(v) ≥ 2 for each v ∈ V. This problem is a generalization of metric TSP. We also propose an approximation algorithm for the digraph version of the problem.
Tomonori TAKEDA Ryuichi MATSUZAKI Ichiro INOUE Shigeo URUSHIDANI
This paper proposes a network design scheme for Virtual Private Network (VPN) services. Traditionally, network design to compute required amount of resource is based on static point-to-point resource demand. This scheme is effective for traditional private line services. However, since VPN services allow multi-site connectivity for customers, it may not be appropriate to design a network based on static point-to-point resource demand. In particular, this scheme is not effective when the traffic pattern changes over time. Therefore, network design for VPN services introduces a new challenge in order to comply with traffic flexibility. There are conventional studies tackling this issue. In those studies, by defining a resource demand model considering flexibility, and designing the network based on this model, amount of resource required can be computed. However, there are some deficiencies in those studies. This paper proposes a new network design scheme, consisting of two components. The first one is a new resource demand model, created by extending conventional resource demand models, that can specify resource demand more precisely. The second one is a new network design algorithm for this resource demand model. Simulations are conducted to evaluate the performance of the proposed network design scheme, and the results show significant performance improvement against conventional schemes. In addition, deployment considerations of the proposed scheme are analyzed.
The optical network represents a promising approach to achieve a scalable backbone network. In backbone networks, survivability is important because high volumes of traffic are prone to be damaged by faulty equipment. Various design methods for survivable optical networks have been proposed, although none considering the simultaneous maintenance of multiple transmission lines has been proposed to our knowledge. This paper proposes a design method for survivable optical networks where multiple transmission lines sharing common transmission equipment may suffer simultaneous damage, due to failure in the transmission equipment. Moreover, two transmission lines can be maintained simultaneously. A mathematical programming model to obtain the optimum lightpath arrangement is presented assuming three kinds of lightpath recovery schemes. The relation between the required transmission line capacity and the combination pattern of two transmission lines that undergo maintenance is clarified using the proposed design method.
Genetic Algorithm (GA) and other Evolutionary Algorithms (EAs) have been successfully applied to solve constrained minimum spanning tree (MST) problems of the communication network design and also have been used extensively in a wide variety of communication network design problems. Choosing an appropriate representation of candidate solutions to the problem is the essential issue for applying GAs to solve real world network design problems, since the encoding and the interaction of the encoding with the crossover and mutation operators have strongly influence on the success of GAs. In this paper, we investigate a new encoding crossover and mutation operators on the performance of GAs to design of minimum spanning tree problem. Based on the performance analysis of these encoding methods in GAs, we improve predecessor-based encoding, in which initialization depends on an underlying random spanning-tree algorithm. The proposed crossover and mutation operators offer locality, heritability, and computational efficiency. We compare with the approach to others that encode candidate spanning trees via the Pr?fer number-based encoding, edge set-based encoding, and demonstrate better results on larger instances for the communication spanning tree design problems.
Hiroyuki YOKOYAMA Hajime NAKAMURA Shinichi NOMOTO
This paper proposes a bandwidth allocation algorithm and a demand accommodation algorithm guaranteeing utility max-min fairness under bandwidth constraints. We prove that the proposed algorithms can fairly split network resources among connections and achieve call admission control considering the fairness among different types of applications. We then formulate three different network design problems to maximize the total utility of all customers, the number of users accommodated in the network, and the average utility of the customers accommodated in the network. To solve the problems, we extend the conventional network design algorithms considering utility max-min fair share, and numerically evaluate and compare their performance. Finally, we summarize the best algorithms to design the utility max-min fair share networks considering the operation policy of network providers.
Takanori NOMURA Keita KAWANO Kazuhiko KINOSHITA Koso MURAKAMI
As various mobile communication systems have developed, dramatically integrated wireless network, where users can communicate seamlessly via several wireless access systems, have become expected. At present, there are many studies of integrated wireless network, but no study of a network design method. Therefore, in this paper, we discuss a network design method for integrated wireless networks. Because of the handover procedure, the network design where adjacent base stations are connected to the same router, regardless of radio system type, is simply considered. However, in such a design, where mobile users crowd into a particular area and users' access to the base stations located there increases, the load of these accesses is centralized to the single router. To overcome this problem, we propose a new network design wherein the base stations of heterogeneous wireless communication systems, the service areas of which overlap, are connected to a different router. In the proposed network design, although users' accesses are concentrated on the base stations located in a particular area, users in that area can be assigned bandwidth of several upper links according to the access conditions of the base stations in neighboring areas. Finally, we show the excellent performance of the proposed design by simulation experiments.