Aun HAIDER Harsha SIRISENA Krzysztof PAWLIKOWSKI
Using the Proportional Integral Derivative (PID) principle of classical feedback control theory, this paper develops two general congestion control algorithms for routers implementing Active Queue Management (AQM) while supporting TCP/IP traffic flows. The general designs of non-interacting (N-PID) and interacting (I-PID) congestion control algorithms are tailored for practical network scenarios using the Ziegler-Nichols guidelines for tuning such controllers. Discrete event simulations using ns are performed to evaluate the performance of an existing F-PID and new N-PID and I-PID algorithms. The performance of N-PID and I-PID is compared mutually as well as with the F-PID algorithm. It reveals that N-PID and I-PID have higher speed of response but lower stability margins than F-PID. In general the accurate following of the target queue size by the PID principle congestion control algorithms, while providing high link utilization, low loss rate and low queuing delays, is also demonstrated.
Michihiro AOKI Miki HIRANO Nobuaki MATSUURA Takashi KURIMOTO Takashi MIYAMURA Masahiro GOSHIMA Keisuke KABASHIMA Shigeo URUSHIDANI
The growth in the volume of Internet traffic and the increasing variety of Internet applications require Internet backbone networks to be scalable and provided sophisticated quality of service (QoS) capabilities. Internet backbone routers have evolved to achieve sub-Tbps switching capacity in a single unit, but their switch architectures have limited scalability, causing QoS to degrade as the switches get bigger. Hence, we propose a large-scale IP and lambda integrated router architecture with scalable switches. We first describe the system architecture of our proposed backbone router and clarify the requirements for its switching capabilities to meet near-future demands. The new switch architecture, using crossbar-based switching fabrics and optical interconnection devices, meets the requirements for a backbone router to scale up to 82 Tbps and enable light path switching as well as packet switching. The routing tag and its usage algorithm in the switch, and packaging issues, including the quantity of hardware required for expansion, are also discussed.
Jiping LIU Hongbing FAN Dinah de PORTO Yu-Liang WU
A Hyper-Universal Switch Box (HUSB) [1]-[3] can yield a feasible (detailed) routing solution for any given routing requirement of multi-pin nets or multi-point connections of surrounding terminals. This flexible routing structure obviously possesses multiple potential applications for re-configurable systems such as FPGAs and communication switching networks [4],[5]. Based on the same decomposition theory developed in the design scheme of such powerful switching structure, a simple routing algorithm can also be developed. The router is exact in terms of its assured capability in finding a routing solution, and it is efficient due to the divide and conquer nature and simple mapping scheme for pre-analyzed routing patterns saved in data base.
Peh Chiong TEH Benn C. THOMSEN Morten IBSEN David J. RICHARDSON
We demonstrate a multi-wavelength (40WDM 10Gbit/s) optical packet router capable of processing 4 Gigapackets/s based on all-optical label generation and recognition using 16-bit, 20Gbit/s four-level phase coding superstructure fibre Bragg gratings. Error free operation is obtained for the switched packets when all 40 channels are transmitting simultaneously.
Katsuya MINAMI Hideki TODE Koso MURAKAMI
As multimedia and high-speed traffic become more popular on the Internet, the various traffic requiring different qualities of service (QoS) must co-exist. In addition, classified services based on Diff-Serv (Differentiated Service), MPLS (Multi-Protocol Label Switching), etc., have come into wide use. Today's Internet environment requires routers to perform control mechanisms in order to guarantee various QoSs. In this paper, we propose a smart buffer management scheme for the Internet router that uses hierarchical priority control with port class and flow level. Furthermore, since the proposed scheme must operate at very high speed, we first propose several design policy for high speed operation and the hardware implementation is performed in VHDL code. Implementation results show that the proposed scheme can scale with high-speed link, achieving the maximum rate of 4.0 Gbps by using the 3.5 µm CMOS technology.
Masanori UGA Masaaki OMOTANI Kohei SHIOMOTO
This paper proposes a novel packet classification method using ternary content-addressable memory (TCAM), which can store very wide policy rules despite the limited width of TCAM. For IP version 6, policy rules could be 304 bits wide. This method enables us to use commercially available TCAM for packet classification and thus builds an ultra high-speed policy based packet forwarding engine for differentiated services on the Internet.
In an Multi-Protocol Label Switching (MPLS) network domain, Asynchronous Transfer Mode--Label Switch Routers (ATM-LSRs) are considered the best candidate for providing the highest forwarding capability. ATM-LSRs implement a VC-merging scheme that allows many IP routes to be mapped into the same VPI/VCI label, hence supporting scalability. The VC-merging requires reassembly buffers to reconstruct an original packet from its segmented but interleaved AAL-5 cells. In this paper, we analyze the performance of an ATM-LSR with partial VC-merging capability and investigate the impact of VC-merging on the requirement of the reassembly and output buffer. The numerical computation complexity of the mathematical analysis can be reduced from O(M4) to O(M2), where M is the total number of ON-OFF sources. We also propose a closed-form equation, which approximates the distribution of the output buffer with satisfactory accuracy. Numerical results show that when incoming cells are severely interleaved, the VC-merging needs the reassembly buffer size to be of the same order as the output buffer size, which cannot be ignored.
Shogo NAKAZAWA Hitomi TAMURA Kenji KAWAHARA Yuji OIE
LSR (Label Switching Router)s in MPLS (Multiprotocol Label Switching) networks map arriving IP flows into some labels on Layer 2 switching fabric and establish LSP (Label Switching Path)s. By using LSPs, LSRs not only transmit IP datagrams fast by cut-through mechanism, but also solve traffic engineering issue to optimize the delay of some IP datagram flows. So far, we have analyzed the performance of LSR focusing only on the maximum number of LSPs which can be set on Layer 2. In this paper, we will also consider the bandwidth allocated to each LSP and analyze the IP datagram transmission delay and the cut-through rate of LSR. We suppose the label mapping method as the data-driven scheme in the analytical model, so that the physical bandwidth of LSR is shared by both the default LSP for hop-by-hop transmission and the cut-through LSPs. Thus, we will investigate the impact of the bandwidth allocation among these LSPs on the performance.
Katsuya MINAMI Hideki TODE Koso MURAKAMI
Recently, as multimedia and high-speed traffic become more popular on the Internet, the various traffic requiring different qualities of service (QoS) will co-exist. In addition, classified service based on Diff-Serv (Differentiated Service), MPLS (Multi-Protocol Label Switching),etc., have come into wide use. Today's Internet environment requires routers to perform control mechanisms in order to guarantee various QoSs. In this paper, we propose a buffer management scheme for the Internet router that uses class-based priority control. This paper focuses on per-flow queueing, and evaluates the performance of the proposed buffer management scheme. Realization of differentiated services and dissolution of buffer occupation by specific flow is expected by the proposed control.
Norio YAMAGAKI Katsuya MINAMI Hideki TODE Koso MURAKAMI
In the future Internet, various kinds of services will rapidly increase its volume and require different qualities. Thus, it is main technical problem to guarantee various QoS to each connection. However, in the current IP networks where most applications use TCP as transport protocol, most typical packet discarding scheme, RED (Random Early Detection), causes unfairness such as the difference of bandwidth sharing among flows traversing the same router. To dissolve this problem, we consider that two viewpoints are important associated with flow-base fairness. One is instantaneous flow condition and the other is historical flow condition. In this paper, we propose the packet discarding scheme considering both instantaneous and historical use of network resources for the purpose of dissolving unfairness of each flow and improving the flow-base QoS. We call this proposal method "Random Early Drop with Dual-fairness metrics (DRED). " DRED can improve whole throughput and transfer completion time of information such as a file, etc.
Using Available Bit Rate (ABR) service of Asynchronous Transfer Mode (ATM) at a backbone link will provide a lossless network. It, however, causes congestion at an edge-router and is reported to show poor end-to-end TCP performance. We consider how to improve the performance of TCP over a backbone ABR network. By using ABR feedback information (ACR) at edge-routers, we can adjust intervals of TCP Acknowledgement packets. This adjustment couples the ABR rate-based control loop and the TCP window-based control loop. Based on this scheme, we can achieve a good end-to-end TCP performance as well as good ATM layer performance over backbone ABR. This paper describes comprehensive study on the proposed mechanism.
We propose a fast and compact longest match table look-up method for very long network addresses like IP version 6. This method uses two ideas for a routing-table arranged in a tree-structure. The first idea is to make table look-up fast by caching pointers to intermediate nodes in the tree, reducing the number of node traversals. The second idea is to reduce the memory size required for each node in the tree by one-third by eliminating common parts of addresses of adjacent nodes. Evaluating the performance of this method by using actual routing table data of an IP backbone network, we found it was five to ten times faster than a conventional method.
Hideki TODE Shinpei YOTSUI Hiromasa IKEDA
In the future Internet, hierarchically classified Quality of Service (QOS) controls will be effective because various connections requiring different QOS are mixed. However, even in such an environment, among the same class connections, performance protection to harmful impact from the other connections and quality differentiation between connections will be required furthermore. In this paper, from this point of view, we focus on the active connections succession time (age of active connections) as a new dimensional criterion for buffer controls. To be concrete, the packet discarding control of congested router's buffer based on active connections is proposed. Moreover, its performance is evaluated through TCP/IP level simulation from the viewpoint of file transfer time. Conventional Internet can be regarded as the environment where only one class traffic exists (unit class environment). The proposed control scheme can provide powerful differentiation capability to avoid the performance disruption of total connections even in the conventional Internet.
Hideyuki SOTOBAYASHI Ken-ichi KITAYAMA
This paper describes an all-optical label swapping for the photonic label switching router (LSR). The optical code routing photonic LSR in which label is mapped onto an optical code is one of the most promising photonic network technologies. It utilizes such unique features of optical code division multiplexing (OCDM) as asynchronous transmission, tell-and-go access protocol, and high degree of scalability. In practical photonic LSRs, all optical code conversion will play an important role. All-optical code conversion of 10 Gbit/s binary phase-shift keying (BPSK) codes by use of cross-phase modulation (XPM) in an optical fiber without wavelength-shift is proposed for the photonic LSR and experimentally demonstrated.
Tadahiko YASUI Kumio KASAHARA Yoshiaki NAKANO
Wavelength Assignment Photonic Switching System (WAPS) provides a wavelength for an end-to-end communication. In this way the features of wavelength can be fully utilized by users. We will give an architectural proposal in which two types of connections over WAPS network are provided and are adaptively used according to service demand by customers. One is a connection established semi-permanently between edge routers and relay-routers and the other is a connection established on flow-by-flow basis between edge routers. We will compare with conventional router networks in terms of data-transfer time. Pre-processing time is a crucial issue in connection-oriented networks, and this is very much reduced thanks to the WAPS network structure.
On the Internet, a Quality of Service (QoS) guaranteed services are increasingly being demanded, and the Internet Engineering Task Force (IETF) is developing the specification documents for the QoS services intensively. This overview details the technical rationales underlining the contents of the specification documents developed by the IETF for Differentiated Services (DiffServ)--to provide QoS guarantee services in the large IP networks-- and Policy Framework--to manage DiffServ compliant networks. The IP networks with DiffServ consist of boundary routers and interior routers. These routers are composed of packet classifiers and marker, shaper, and policing function. Many vendors have developed DiffServ-compliant routers with gigabit interfaces. An example of an implementation of a DiffServ-compliant router and a demonstration of a QoS service using this router are presented here. The Policy Framework is expected to be one of the promising management solutions to co-operate with and manage many DiffServ-compliant routers. An experiment that adopts the Policy Framework to a DiffServ compliant network is also outlined.
Future high-speed switches and routers will be expected to support a large number of ports at high line rates carrying traffic with diverse statistical properties. Accordingly, scheduling mechanisms will be required to handle Tbit/sec aggregated capacity while providing quality of service (QoS) guarantees. In this paper a novel high-capacity switching scheme for ATM/WDM networks is presented. The proposed architecture is contention-free, scalable, easy to implement and requires no internal "speedup. " Non-uniform destination distribution and bursty cell arrivals are examined when studying the switching performance. Simulation results show that at an aggregated throughput of 1 Tbit/sec, low latency is achieved, yielding a powerful solution for high-performance packet-switch networks.
Atsushi KAMOSHIDA Shuji TSUKIYAMA
A parallel detailed router based on the area division is one of important tools to overcome the increase of CPU time required for routing of a very large multilayer SOG. In order to conduct routing in each divided area independently, fictitious terminals are introduced on the border of each divided area, and routes connected to the fictitious terminals are concatenated to complete the final detailed routes. In this paper, we consider a problem how to position such fictitious terminals on borders, so as to make each detailed routing in a divided area easy. We formulate this problem as a minimum cost assignment problem, and propose an iterative improvement algorithm. We also give some experimental results which indicate the effectiveness of the algorithm.
Kenichi NAGAMI Hiroshi ESAKI Noritoshi DEMIZU
Label switching technology enables high performance and flexible layer-3 packet forwarding using the fixed length label information mapped to the corresponding layer-3 packet stream. A Label Switching Router (LSR), applying label switching technology, forwards layer-3 packets either by their layer-3 address information or by their label information mapped to the layer-3 address information. In order to apply label switching technology to ATM links, we have introduced a new identifier called a Virtual Connection ID (VCID). The VCID value is shared between the neighboring LSR nodes. This paper proposes a VCID notification procedure and evaluates the performance of LSP (Label Switching Path) establishment with the VCID notification procedure. The prototype system can establish 142.9 LSPs in one second with PVC operation, and 10.53 LSPs in one second with SVC operation. Of the entire LSP establishment procedure, the VCID notification procedure contributes only 3 ms, corresponding to only 3% of the entire LSP establishment procedure with SVC operation. Evaluation using a real traffic trace between Japan and the U. S. shows that the required maximum number for LSP establishment is 17 per second. With SVC operation, the prototype system will not be able to achieve sufficient performance with regard to LSP establishment. Since the contribution by the ATM signaling is large, i. e. , 88 ms (= 92.6%), we need to improve the performance of ATM signaling with SVC operation.
Takumi WATANABE Yusuke OHTOMO Kimihiro YAMAKOSHI Yuichiro TAKEI
This paper presents a routing methodology and a routing algorithm used in designing Gb/s LSIs with deep-submicron technology. A routing method for controlling wire width and spacing is adopted for net groups classified according to wire length and maximum-allowable-delay constraints. A high-performance router using this method has been developed and can handle variable wire widths, variable spacing, wire shape control, and low-delay routing. For multi-terminal net routing, a modification of variable-cost maze routing (GVMR) is effective for reducing wire capacitance (net length) and decreasing net delay. The methodology described here has been used to design an ATM-switch LSI using 0. 25-µm CMOS/SIMOX technology. The LSI has a throughput of 40 Gb/s (2. 5 Gbps/pin) and an internal clock frequency of 312 MHz.