Simulation of congestion avoidance and routing in packet switching networks

The development of a flexible computer simulation package for packet switching computer networks that enables the evaluation of different congestion avoidance methods and routing strategies is discussed. The package is presented in terms of the factors involved, the operations required, and the simulation execution considerations. Use of the package for the evaluation of congestion avoidance methods and routing strategies is described. The congestion avoidance methods considered include isarithmic methods with static and dynamic control. In addition, static and dynamic routing strategies are taken into account. The relative differences between the various methods and strategies considered are presented. It has been found that the results obtained agree with previous results, and this confirms the suitability of the package for future investigation. The package would be useful to students and researchers in the field, especially since it uses the widely known computer language Pascal, and is run on an IBM PC(AT).     

Cernet packet routing method

The routing method used in Cernet, a local high-speed packet switching network on the European Organization for Nuclear Research (Cern) site, is presented. The method is based on a decentralized procedure for updating routing tables. The tables adapt to changes in the network topology, but not to variations in the packet traffic load. The method is claimed to be simple and robust, permitting a fairly small and efficient emplementation.     

Quality-of-Service routing with path information aggregation

Most of the research proposals on Quality-of-Service (QoS) mechanisms have focused on providing guarantees in a single domain. Supporting QoS guarantees in the interdomain setting has been receiving more research attention recently. Most of the proposals for interdomain QoS routing has focused on a link-state protocol and/or a single QoS metric. Our proposal differs from the existing work in the literature in three major ways: (1) our approach is based on a distance-vector protocol, similar to BGP; the de facto interdomain routing protocol in the Internet, (2) we consider both bandwidth and delay simultaneously unlike the other studies which either considered one metric or made the decision on only one of metrics even when they disseminated more than one metric, and (3) we use a line segment to represent the domain level QoS information. To the best of our knowledge, our study is the first proposal in the literature that models the domains by a line segment for inter-domain QoS routing purposes under a distance-vector routing protocol to find a path that satisfy both bandwidth and delay requirements.     

Enhanced packet routing queuing model in optical burst switching network using queue-based dynamic optical route scheduling

Optical Burst Switching (OBS) for all future optical network technology signatures. In OBS, the IP packet is known as a large explosion of data that is assembled in the input packets. The pre-assembly burst is sent to its intended location for offset time. It has shown that there are some security issues, but they do not resolve the node's ability to separate them. When they have suffered great losses to ensure that they are indispensable. If they are not safe, it may not waste resources on the optimal path.Current communication paradigms such as broadcast and multicast. Therefore, in optical networks, it is necessary to support these paradigms. Implementation of IP QoS policies does not apply to Optical Burst Switching (OBS) networks. These QoS requirements include controversy, optical signal quality, reliability, and delay.This work recommends the use of shared encryption for secure message traffic on OBS networks. The information is divided into as many strands as possible, and then it transmits at different times between pair of nodes and the different paths or routes. The proposed method to analyze the three strategies likely traffic analysis and route scheduling, packet header analysis,and authentication key verification.This proposed method,Queue-Based Dynamic Optical Route Scheduling (QDORS), provides flexible and efficient integrated packet-based traffic in OBS functions and Internet-based networks. It considered exploding a valid huge amount of data plans to reduce better channel usage, higher efficiency, and blocking probability.     

Providing multiple hard latency and throughput guarantees for packet switching networks on chip

In many-core architectures different distributed applications are executed in parallel. The applications may need hard guarantees for communication with respect to latency and throughput to cope with their constraints. Networks on Chip (NoC) are the most promising approach to handle these requirements in architectures with a large number of cores. Dynamic reservation of communication resources in virtual channel NoCs is used to enable quality of service for concurrent communication. This paper presents a router design supporting best effort and connection-oriented guaranteed service communication. The communication resources are shared dynamically between the two communication schemes. The key contribution is a concept for virtual channel reservation supporting different bandwidth and latency guarantees for simultaneous guaranteed service communication flows. Different to state-of-the-art, the used scheduling approach allows to give hard guarantees regarding throughput and latency. The concept enables to adjust the bandwidth and latency requirements of connections at run-time to cope with dynamically changing application requirements. Due to its distributed reservation process and resource allocation it offers good scalability for many-core architectures. The implementation of a router and the required extension of a network interface to support the proposed concept are presented. The software perspective is discussed. An algorithm is presented that is used to establish guaranteed service connections according to the applications bandwidth requirements. Simulation results are compared to state-of-the-art arbitration schemes and show significant improvements of latency and throughput, e.g. for an MPEG4 application. Synthesis results expose the low area overhead and impact on energy consumption which makes the concepts highly attractive for QoS-constraint many-core architectures.     

A Routing Algorithm with Candidate Shortest Path

An improved algorithm based on the next node routing principle is proposed in this paper.In this algorithm there is a column added to the classical routing table, in which the candidateshortest distance to the destination node is the entry. When a link fails, the new shortest path inthe nodes connected directly with the failure link can be found immediately (it is just thecandidate shortest path before failure). For all other nodes in which routing tables should bechanged, the required number of control messages and time for convergence are also less thanTajibnapis' algorithm and Predecessor algorithm. The message looping problem does not existin duplex loop networks and is radically improved in mesh networks. These statements areproved by the analysis and simulation in this paper. From the simulation results of a 30-nodemesh network, when one link goes down, the total number of control messages generatedduring convergence with this algorithm on the average is about 30% of Tajibnapis' algorithm.The iterations required is 50% of Tajibnapis' algorithm. The memory space required andcomputation complexity in nodes are almost the same as the two algorithms mentioned aboveand the algorithm implementation is as easy as well.     

Distributed packet switching queueing network design

An overall design of a distributed packet switching communication network with many clusters of users, several host-computers, intermediate processors and concentrators is described. The proposed approach takes into account such factors as nonlinearity of cost functions, reliability requirements of every cluster, provides least-cost network configuration by an appropriate selection of flow routing strategies, and capacities of all links with their acceptable delays. This is achieved by three major modules of the algorithm: preparation of tables, multiple usage of recursive subroutines, and finally, via parametric search. Recent computer experiments demonstrate startling agreement with the theoretically predicted polynomial time- and space-complexities of those proposed in the paper.     

Energy-aware IP traffic engineering with shortest path routing

Internet energy consumption is rapidly becoming a critical issue due to the exponential traffic growth and the rapid expansion of communication infrastructures worldwide. We address the problem of energy-aware intra-domain traffic engineering in networks operated with a shortest path routing protocol. We consider the problem of switching off (putting in sleep mode) network elements (links and routers) and of adjusting the link weights so as to minimize the energy consumption as well as a network congestion measure. To tackle this multi-objective optimization problem with priority (first minimize the energy consumption and then the network congestion), we propose a Mixed Integer Linear Programming based algorithm for Energy-aware Weights Optimization (MILP-EWO). Our heuristic exploits the Interior Gateway Protocol Weight Optimization (IGP-WO) algorithm for optimizing the OSPF link weights so as to minimize the total cost of link utilization. The computational results obtained for eight real network topologies and different types of traffic matrices show that it is possible to switch off a substantial number of nodes and links during low and moderate traffic periods, while guaranteeing that network congestion is low enough to ensure service quality. The proposed approach is also validated on two networks of emulated Linux routers.     

Flit-serial packet routing on meshes and tori

In this paper we consider theflit-serial packet-routing problem, where each packet consists of a sequence ofk flits and is, thus, called asnake. Based on the properties of the snake during the routing, we give a formal definition of three different packet-routing models, namely, thestore-and-forward model, thecut-through model, and thecut-through with partial cuts model. Surprisingly, all previous work has focused on the store-and-forward model. We also introduce therestricted cut-through model, which is unrealistic, but is proved to be a very powerful tool in the effort to bound the time required by a routing problem. We study the cut-through with partial cuts model which is most commonly used in practice. We present the first algorithms, deterministic and probabilistic, based on this model for the permutation routing problem on a chain, on a square mesh, and on a square torus.     

用Torus网络构建可扩展分组交换结构的设计方案

提出了一种采用Torus网络技术的模块化交换子网结构--可配置单板(CB),给出了应用CB模块构建可扩展交换结构的具体设计方案,并讨论了关键设计参数的取值.该方案支持交换端口数与交换容量数百倍的平滑扩展.仿真实验结果验证了该方案的可行性.     

A simple livelock-free algorithm for packet switching

Store-and-forward deadlock (SFD) occurs in packet switched computer networks when, among some cycle of packets buffered by the communication system, each packet in the cycle waits for the use of the buffer currently occupied by the next packet in the cycle. In this paper, a deadlock-free algorithm as well as a livelock-free algorithm for packet switching is obtained using the strategy of the banker's algorithm. Furthermore, the solution obtained is interpreted for the hyper-fast banker's problem.     

Enforcing in-order packet delivery in system area networks with adaptive routing

Adaptive routing, which dynamically selects the route of packets, has been widely studied for interconnection networks in massively parallel computers and system area networks. Although adaptive routing has the advantage of providing high bandwidth, it may deliver packets out-of-order, which some message passing libraries do not accept. In this paper, we propose two mechanisms called (1) FIFO transmission and (2) couple limitation to guarantee in-order packet delivery in adaptive routing. Both of them limit packet injection at source hosts. The FIFO transmission completely avoids packet sorting at destination hosts, while the couple limitation uses a few buffers to sort packets at destination hosts. Evaluation results show that the FIFO transmission and the couple limitation achieve a similar throughput to that of a method equipped with huge (infinite) buffers enough to store all out-of-order packets at destination hosts under both synthetic traffic and NAS Parallel Benchmarks.     

The British Post Office and packet switching

The history and development of the British Post Office Experimental Packet Switched Service are described. Details of the hardware and software are given, and the problems encountered while setting up the network are outlined. Although the emergence of X.25 has ensured that the EPSS will not become a national service, the Post Office have learned some valuable lessons, and these are discussed together with the lessons learned by the data-communications users.     

An asynchronous, high-speed packet switching component

The authors discuss the requirements for integrated switching components in a broadband packet-switched telecommunication network. They describe a practical implementation of the resulting complex functionality over a wide range of frequencies within one VLSI chip. After presenting a pragmatic test approach for their highly asynchronous design, their work concludes with test results from a working silicon implementation     

Robust algorithms for packet routing in a mesh

This paper considers the problem of permutation packet routing on a n×n mesh-connected array of processors. Each node in the array is assumed to be independently faulty with a probability bounded above by a valuep. This paper gives a routing algorithm which, ifp 0.29, will with very high probability route every packet that can be routed inO(n logn) steps with queue lengths that areO(log² n). Extensions to higher-dimensional meshes are given.     

Two packet routing algorithms on a mesh-connected computer

We give two algorithms for the 1-1 routing problems on a mesh-connected computer. The first algorithm, with queue size 28, solves the 1-1 routing problem on an n×n mesh-connected computer in 2n+O(1) steps. This improves the previous queue size of 75. The second algorithm solves the 1-1 routing problem in 2n-2 steps with queue size 12 t_s/s where t_s is the time for sorting an s×s mesh into a row major order for all s⩾1. This result improves the previous queue size 18.67 t_s/s     

k-重传机制增强电力线通信中继路径

分析了电力线载波通信中集中式路由的瓶颈现象,为缓解这一现象,提出了k-重传机制.通过构建k-重传机制的模型,分析证实了在集中式路由策略中引入该机制能够有效提高路径可靠性和降低主节点期望等待时间.     

基于分组交换网络的B-Reno性能研究*

通过仿真实验的方法,研究了B-Reno协议在分组交换网络中的性能。实验使用了不同的网络拓扑和链路参数,全面考察了B-Reno的吞吐率和TCP友好性,并将实验结果与其他TCP协议版本相比较。实验结果显示,B-Reno在分组交换网络中能取得高出Reno和New-Reno10%以上的吞吐率,达到与Sack相当的水平;同时,当与Reno（传统TCP）竞争共享信道时,B-Reno也具有良好的TCP友好性。实验结果表明B-Reno在分组交换网络中也能取得良好的性能。     

Access protocols for circuit/packet switching networks

This paper discusses two possible designs of access protocols for integrated computer networks with combined circuit and packet switching capabilities. The special features of these protocols are examined. Existing segregated protocols, i.e. pure circuit or packet protocols, are evaluated with future integration in mind.     

Privacy preserving shortest path routing with an application to navigation

Mobile navigation is a frequently used application, especially with the increasing proliferation of online geographical data. However, the origin and destination are often private information closely tied to a user’s personal life. Sharing those with an online map provider greatly increases the chance of the user being profiled. Contrary to existing location privacy problems, the origin and the destination are essential for finding the shortest path in a realtime traffic setting. In this paper, we show that the problem can be solved with Private Information Retrieval (PIR) techniques without disclosing the origin or the destination. We analyze the cost associated with this approach and propose a practical solution with the assumption of a semi-honest third party to improve the efficiency. The proposed practical solution only introduces encryption overhead over the plain scenario where the path is returned by knowing the origin and destination.