Source: https://patents.google.com/patent/US7474664B2/en
Timestamp: 2018-12-11 23:45:45
Document Index: 172212488

Matched Legal Cases: ['§ 119', 'Application No. 10', 'Application No. 10', 'Application No. 10', 'art 62', 'art 64', 'art 60', 'art 62', 'art 64', 'art 62', 'art 62', 'art 1']

US7474664B2 - ATM switch for ensuring cell sequence - Google Patents
ATM switch for ensuring cell sequence Download PDF
US7474664B2
US7474664B2 US10971524 US97152404A US7474664B2 US 7474664 B2 US7474664 B2 US 7474664B2 US 10971524 US10971524 US 10971524 US 97152404 A US97152404 A US 97152404A US 7474664 B2 US7474664 B2 US 7474664B2
US10971524
US20050053067A1 (en )
Seisho Yasukawa
Masayoshi Nabeshima
An ATM switch includes a first stage, a second stage and a third stage each of which stages includes at least one basic switch, wherein the first stage, the second stage and the third stage are connected. The basic switch includes a part which refers to time information written in a header of an input cell and switches cells to an output port in an ascending order of the time information. In addition, the ATM switch includes a cell distribution part in the basic switch of the first stage. The cell distribution part determines a routes of a cell to be transferred such that loads of routes within the ATM switch are balanced. The ATM switch further includes an adding part which adds arriving time information to an arriving cell as the time information.
This application claims the benefit and priority of and is a division of U.S. patent application Ser. No. 09/376,904, filed Aug. 18, 1999 now U.S. Pat. No. 7,136,391, which claims foreign priority benefits under 35 U.S.C. § 119 of Japanese Patent Application No. 10-235957, filed Aug. 21, 1998; Japanese Patent Application No. 10-266802, filed Sep. 21, 1998 and Japanese Patent Application No. 10-266930, filed Sep. 21, 1998, all of which are incorporated herein by reference.
A conventional multi stage switch will be described with reference to FIG. 1. FIG. 1 is a block diagram showing the conventional multi stage ATM switch. The first stage has n n×m switches, the second stage has m n×n switches, and the third stage has n m×n switches. Conventionally, it has been known that a cross architecture in which three stages of basic switches are connected is effective for expanding the switch size.
Moreover, another method for preventing the cell sequence disorder is proposed in M. Collivignarelli et al., “System and Performance Design of the ATM Node UT-XC,” IEEE ISS '94, pp.613-618, in which maximum delay time is added.
Moreover, it is a problem to accommodate a large number of input/output lines in such a high-speed ATM switch. FIG. 7 shows an example of an ATM switch of a 16×16 switch size. For example, when realizing the ATM switch which has the 16×16 switch size and 160-Gbit/s switching throughput (the highway speed is 10-Gbit/s which is 622 Mbit/s×20) and the number of high-speed input/output lines of an LSI chip for the ATM switch is limited to 300 pins at the maximum, an LSI chip of a 4×2 ((4+2)×2×20=240, with 50 control lines) can be realized when inputting high speed signal in parallel to the ATM switch. Therefor, 32 chips are necessary in order to realize a 160-G bit/s cross-point switch.
FIG. 8 shows an LSI chip configuration when transferring cells by splitting cells spatially. As shown in FIG. 8, when cells are split spatially by using a bit slicing technique, 160G/3 throughput can be realized by one chip (16×2×(20/3)≈230, with 50 control lines). Therefore, a 160-G bits/s throughput can be realized with 3 chips at the minimum. In addition, hardware logic in the chip is used effectively since high speed lines for interconnecting between chips can be eliminated.
Accordingly, it is a general object of the present invention to provide an ATM switch which can carry out cell resequencing in each basic switch in a decentralized autonomous manner without sorting a large number of cells to be sent through many routes.
a second comparing part which compares bit information of the short cells which are output from the switches, the short cells having a delay time of t±τ, τ being an acceptable fluctuation time.
FIG. 7 shows an example of an implementation of a 16×16 ATM switch;
FIG. 34 shows an example of an implementation of a 256×256 ATM switch which is configured by 4 switches which include. interconnected 16×16 basic switches;
First, the general outline of a first embodiment of the present invention for cell resequencing in an ATM switch will be described. FIG. 11 shows a block diagram of the ATM switch according to the first embodiment of the present invention. As shown in FIG. 11, the ATM switch includes m basic switches ISW#1-ISW#m at a first stage, m basic switches TSW#1-TSW#m at a second stage and m basic switches OSW#1-OSW#m at a third stage, each of the basic switches having m input lines and m output lines and each of the basic switches of a stage being connected to basic switches of a next stage, thereby forming an m×m input and m×m output ATM switch.
Next, a switching process of a cell input to the ATM switch will be described in chronological order. First, the cell which is input to the ATM switch is input to one of the cell splitting parts SA1-SA4. The cell splitting part splits the input cell spatially, generating short cells which can be sent with a low number of parallel signals for transmission. FIG. 25 shows an example of a cell format of 64-byte length on the assumption that the cells are transmitted in parallel on 16 highways. FIG. 26 shows an example of the short cell. In this example, as shown in the FIGS. 25 and 26, a cell of 16 bits×32 words is split into a short cell of 8bits×32 words.
FIG. 34 shows an example of a 256×256 ATM switch which is configured by 4 switches which include interconnected 16×16 basic switches. The ATM switch switches 4 split short cells. It can be recognized from the example that the switch scale can be expanded by a simple configuration.
FIG. 44 shows a modification of the third embodiment of the present invention. As shown in the figure, the ATM switch has a delay time inferring part 62 instead of the counter 50 0-50 N−1, and a comparing part 64 instead of the comparing part 60. The delay time inferring part 62 obtains an inferred delay time t of the switches 40 0-40 N−1, and the comparing part 64 compares bit information of short cells output from the switches 40 0-40 N−1 within a delay time t±τ. In addition, the delay time inferring part 62 compares between an input time of a timing cell which is a specific cell input to the switches and an output time of the timing cell output from the switches so as to obtain the inferred delay time t. In addition, the delay time inferring part 62 sends the timing cell periodically.
FIG. 46 shows a mechanism for accepting the short cell fluctuation. In the mechanism, τ represents the fluctuation time which can be compensated for and the short cells which arrive within TAT±τ are candidates to be assembled.
FIG. 53 is a block diagram for explaining a concept of the cell distribution. As shown in the figure, a configuration which has n n×n basic switches forming a multi stage switch is taken as an example.
In order to carry out the cell distribution to avoid blocking in the switch, a scheduling algorithm in consideration of destinations of all n×n input cells is necessary. However, such a scheduling algorithm may have problem of scalability for a large-scale switch. Therefore, the fifth embodiment of the present invention proposes to provide a cell distribution algorithm in each of the n input switches dispersively. Accordingly, since the cell distribution can be carried out in an n×n basic switch, the scalability can be obtained and a large scale switch can be realized.
As shown in FIG. 55, the maximum L is n×1.0. Therefore, the maximum load distributed to each link is smaller than or equal to 1.0. Thus, load concentration to any output link in the switch can be prevented so as to realize a non-blocking switch.
As shown in FIG. 56, when a cell arrives at the ATM switch in step 1, the cell distribution part determines a destination group of the switch in step 2. Here, the destination group represents an output basic switch of the third stage. Therefore, there are the same number of groups as that of the basic switches of the third stage. For example, there are N groups in a three-stage ATM switch using N N×N basic switches in a stage. For example;, cells for output ports 1-N are grouped into group 1, cells for output ports N+1-2N are grouped into group 2, . . . , cells for output ports N2−N-N2 are grouped into group N. FIG. 56 shows a cell for the output port 2 which is grouped into group 1.
wherein said assembling means includes means which assembles said short cells with the same bit information according to the comparison of said comparing means.
US10971524 1998-08-21 2004-10-22 ATM switch for ensuring cell sequence Expired - Fee Related US7474664B2 (en)
JP23595798 1998-08-21
JP26693098 1998-09-21
JP10-266930 1998-09-21
JP10-266802 1998-09-21
JP10-235957 1998-09-21
JP26680298 1998-09-21
US09376904 US7136391B1 (en) 1998-08-21 1999-08-18 ATM switch
US10971524 US7474664B2 (en) 1998-08-21 2004-10-22 ATM switch for ensuring cell sequence
US09376904 Division US7136391B1 (en) 1998-08-21 1999-08-18 ATM switch
US20050053067A1 true US20050053067A1 (en) 2005-03-10
US7474664B2 true US7474664B2 (en) 2009-01-06
ID=27332322
US09376904 Expired - Fee Related US7136391B1 (en) 1998-08-21 1999-08-18 ATM switch
US10972175 Expired - Fee Related US7292576B2 (en) 1998-08-21 2004-10-22 ATM switch having output buffers
US10971676 Expired - Fee Related US7339935B2 (en) 1998-08-21 2004-10-22 ATM switch for distributing cells to avoid blocking in the ATM switch
US10971524 Expired - Fee Related US7474664B2 (en) 1998-08-21 2004-10-22 ATM switch for ensuring cell sequence
US (4) US7136391B1 (en)
EP (1) EP0982970B1 (en)
CA (1) CA2280580C (en)
US20110243130A1 (en) * 2008-12-19 2011-10-06 Panasonic Corporation Transmitter terminal and receiver terminal
KR20000074195A (en) * 1999-05-19 2000-12-15 강병호 Apparatus and method for resequencing cell of multipath atm switch
US6985501B2 (en) 2000-04-07 2006-01-10 Ntt Docomo, Inc. Device and method for reducing delay jitter in data transmission
US7171117B1 (en) 2000-08-25 2007-01-30 Lucent Technologies Inc. Optical router
GB2413919A (en) * 2003-03-03 2005-11-09 Xyratex Tech Ltd Apparatus and method for switching data packets
US7584248B2 (en) * 2004-02-27 2009-09-01 Alcatel-Lucent Usa Inc. Apparatus and method for fair message exchanges in distributed multi-player games
JP5781762B2 (en) * 2007-08-10 2015-09-24 プロテリックス、インク Library of Universal iii type fibronectin binding domain
US8680019B2 (en) * 2007-08-10 2014-03-25 Protelica, Inc. Universal fibronectin Type III binding-domain libraries
JP6281516B2 (en) * 2015-03-27 2018-02-21 日本電気株式会社 Network authentication system, a network authentication method and the authentication server
JP2016212475A (en) * 2015-04-30 2016-12-15 富士通株式会社 Storage control device, storage control program and storage system
JPH02195758A (en) 1989-01-24 1990-08-02 Nippon Telegr & Teleph Corp <Ntt> Sequential control method for cell of self-routing switch
EP0471380A1 (en) 1990-08-17 1992-02-19 Hitachi, Ltd. ATM switch
JPH04252632A (en) 1991-01-29 1992-09-08 Fujitsu Ltd Cell exchanging method and cell exchanging system of this method
EP0553798A2 (en) 1992-01-27 1993-08-04 Nec Corporation Low delay ATM switching system using stamped idle cells
JPH0677984A (en) 1992-08-28 1994-03-18 Fujitsu Ltd Cell read control system for atm switch
JPH06252948A (en) 1993-02-23 1994-09-09 Nec Corp Packet switching system
US5485457A (en) * 1991-10-31 1996-01-16 Nec Corporation Packet switching system capable of reducing a delay time for each packet
EP0821506A1 (en) * 1995-12-25 1998-01-28 Ntt Mobile Communications Network Inc. Multiplex transmitter for micro-frame
EP0833480A2 (en) 1996-09-25 1998-04-01 Nippon Telegraph And Telephone Corporation Contention control circuit
US5822321A (en) * 1996-04-10 1998-10-13 Telefonaktiebolaget Lm Ericsson Minicell segmentation and reassembly
WO1999033314A1 (en) * 1997-12-19 1999-07-01 Telefonaktiebolaget Lm Ericsson (Publ) Asynchronous transfer mode system handling differing aal protocols
US6160805A (en) 1996-09-30 2000-12-12 Motorola, Inc. Method for synchronizing a session timer
US6647017B1 (en) 1997-07-14 2003-11-11 Nokia Corporation Switching fabric arrangement with time stamp function
US677984A (en) * 1901-02-25 1901-07-09 John G Herbst Hinge.
US2195758A (en) * 1936-10-01 1940-04-02 Rysick Arno Sound recording machine
US4252632A (en) * 1976-04-29 1981-02-24 Atlantic Richfield Company Catalyst and process for conversion of hydrocarbons
WO1990010984A1 (en) * 1989-03-14 1990-09-20 Alcatel N.V. Communication switching system
JP3421359B2 (en) * 1992-03-13 2003-06-30 三洋電機株式会社 Telephone notepad device
EP0576856A3 (en) * 1992-06-30 1996-07-03 Siemens Ag Method and circuit for transmission of a continuous atm bitstream
US5207062A (en) * 1992-07-28 1993-05-04 Allied-Signal Inc. Center valve master cylinder with adjustable caged primary spring
KR100262682B1 (en) * 1995-04-15 2000-08-01 최병석 Multicast atm switch and its multicast contention resolution
EP0748086A1 (en) * 1995-06-09 1996-12-11 Siemens Aktiengesellschaft Method for scheduling message cells leaving an ATM node
JPH05207062A (en) 1992-01-27 1993-08-13 Nec Corp Packet switching system
US5337308A (en) 1992-01-27 1994-08-09 Nec Corporation Low delay ATM switching system using idle cells stamped with reference time
US5953341A (en) 1996-09-25 1999-09-14 Nippon Telegraph And Telephone Corporation Contention control circuit
Akihiko Takase et al. "Datapath architecture and technology for large scale ATM switching systems" Global Telecommunications Conference, 1996. Globecom '96. Communications: The Key to Global Prosperity London, UK Nov. 18-22, 1996, New York, NY, USA, IEEE, US, Nov. 18, 1996, pp. 1395-1399.
Balboni et al., "From transport backbone to service platform: facing the broadband switch evolution," ISS '95, World Telecommunications Congress Advanced Switching Technologies for Universal Telecommunications at the beginning of the 21st Century 1995;1:216-220.
Chaney et al., "Design of a gigabit ATM switch," INFOCOM '97, Sixteenth Annual Joint Conference of the IEEE Computer and Communications Societies, Proceedings IEEE Apr. 1997;1:2-11.
Collivignarelli et al., "System and performance design of the ATM node UT-XC," Supercomm/ICC '94, Conference Record, Serving Humanity Through Communications, IEEE International Conference on Communications May 1994;1:613-618.
de Prycker, Asynchronous Transfer Mode Solution for Broadband ISDN, 2nd ed. 1993; pp. 152-203.
European Search Report, issued Jan. 13, 2005.
Henrion et al., "Technology, distributed control and performance of a multipath self-routing switch," ISS '92, Proceeding of the International Switching Symposium, Oct. 1992; 2:2-6.
Hitoshi Obara "Design of a Multistage Self-Routing Switch with a Distributed Cell Sequence Control" Electronics & Communications in Japan, Part I-Communications, Scripta Technica. New York, US, vol. 73, No. 10, Oct. 1, 1990, pp. 14-27.
Oki et al., "A scalable distributed arbitration in high-speed ATM switches," IEICE General Conference 1997;41 (w/ English language translation).
P.C. Wong et al. "Pipeline banyan-a parallel fast packet switch architecture" Discovering a New World of Communications. Chicago, Jun. 14-18, 1992. Bound Together With B0190700, vol. 3, Proceedings of the International Conference on Communications, New York, IEEE, US, vol. 4, Jun. 14, 1992, pp. 882-887.
Ryozo Kishimoto et al. "Self-Routing Benes Network Distributively Controlled by Dynamic Load Balance" Electronics & Communications in Japan, Part I-Communications, Scripta Technica. New York, US, vol. 73, No. 9 Part 1, Sep. 1, 1990, pp. 1-11.
Subbiah, B et al., "ATM Adaptation Layer 2 (AAL2) for Low Bit Rate Speech and Data: Issues and Challenges," IEEE ATM Workshop Proceedings. May 26-29, 1998. pp. 225-233. *
Sying-Jyan Wang "Load-Balancing in Multistage Interconnection Networks under Multiple-Pass Routing" Journal of Parallel and Distributed Computing, Academic Press, Duluth, MN, US, vol. 36, No. 2, Aug. 1, 1996, pp. 189-194.
Turner et al., "Architectural choices in large scale ATM switches," IEICE Transactions in Communications Feb. 1998;E81-B(2):120-137.
Yasukawa et al., "Multi-route ATM switch which conserve cell sequence in tournament manner," IEICE General Conference 1998:19 (w/ English language translation).
US8711695B2 (en) * 2008-12-19 2014-04-29 Panasonic Corporation Transmitter and receiver for streaming media including packet padding
US20050053067A1 (en) 2005-03-10 application
EP0982970A3 (en) 2005-03-02 application
CA2280580C (en) 2007-03-13 grant
US20050083939A1 (en) 2005-04-21 application
US7292576B2 (en) 2007-11-06 grant
US20050053096A1 (en) 2005-03-10 application
CA2280580A1 (en) 2000-02-21 application
US7136391B1 (en) 2006-11-14 grant
EP0982970B1 (en) 2006-10-04 grant
US7339935B2 (en) 2008-03-04 grant
EP0982970A2 (en) 2000-03-01 application
US7304944B2 (en) 2007-12-04 Unified scheduling and queueing architecture for a multiservice switch
2013-01-06 LAPS Lapse for failure to pay maintenance fees