《信息网络协议基础》课程教学资源（参考书籍）High Performance Switches and Routers（H. JONATHAN CHAO and BIN LIU）.pdf_P36-P40

22 INTRODUCTION outputs to be independent,thereby creating the possibility of exploring different scheduling schemes individually to maximize the overall performance. Chapter 12 describes Clos-network switches.This structure was proposed by Charles Clos for making a scalable telephone circuit switch.It has been used in packet switch fabrics because of its regular interconnections and scalability.Multiple switch modules are interconnected in a Clos-type structure.Each switch module's size is usually determined by the input/output pin count of a chip or the connectors of a printed circuit board.Each switch module can be a crossbar switch with or without buffers.If without buffers,a global contention resolution scheme is required.If with buffers,the contention can be done within the switch modules in a distributed manner.As the switch grows larger and larger,it is more practical to resolve the contention in a distributed manner.However,because of multiple possible paths between each input and each output pair,the challenge becomes choosing a switch module in the center stage.If not carefully chosen,the load is not balanced among the switch modules in the center stage,causing some center modules to be more congested than others.In addition,due to various delays of the multiple paths between an input/output pair,maintaining the order of the packets in the same flow becomes very challenging. Chapter 13 describes a practical multi-plane,multi-stage buffered switch,called True- Way.It has the features of scalability,high-speed operations,high-performance,and multicasting.It resolves the issues of:(1)How to efficiently allocate and share the lim- ited on-chip memories;(2)How to intelligently schedule packets on multiple paths while maximizing memory utilization and system performance;(3)How to minimize link conges- tion and prevent buffer overflow (i.e.,stage-to-stage flow control);and (4)How to maintain packet order if the packets are delivered over multiple paths(i.e.,port-to-port flow control). A small-scale True Way switch has been prototyped using field programmable gate array (FPGA)and SERDES chips with signals running at 3.125 Gbps at the backplane. Chapter 14 describes load-balanced switches.The idea of this type of switch is very interesting.Packets from each input are temporarily and evenly distributed to all other output ports.They are then forwarded to their final destinations.By doing this,the switch fabrics can operate in a cyclic-shifting configuration at each time slot and still achieve 100 percent throughput.One challenging issue of this kind of switch is to maintain packet order.The difference of several proposed schemes lies in the way of resolving the packet out-of-order issue.Since the packets traverse from the input to a temporary output and then from that port to the final output port,one either needs to use two separate switch fabrics or have one switch fabric running at twice the speed of the input.People will argue that the 100 percent throughput is achieved because of the speedup factor of 2.However,the biggest incentive for this kind of switch is that there is no need for an arbitrator to resolve packet contention. Chapter 15 describes optical packet switches.Depending on whether the contended packets are stored in the optical or in the electrical domain,these switch architectures are classified into opto-electronic packet switches and all-optical packet switches.In either case,contention resolution among the arriving packets is handled electronically.It is very challenging to store contending packets in an optical buffer,which is usually implemented by an optical delay line.The storage size and the time that a packet can be stored are quite limited when using optical delay lines.Another challenging issue is to align the optical packets before storing them on the optical delay lines.It requires tremendous effort to align them when traversing different distances from different sources.Until there is a major breakthrough in optical buffering technology,it will remain very difficult to implement all-optical packet switches

Book1099 — “c01” — 2007/2/16 — 18:26 — page 22 — #22 22 INTRODUCTION outputs to be independent, thereby creating the possibility of exploring different scheduling schemes individually to maximize the overall performance. Chapter 12 describes Clos-network switches. This structure was proposed by Charles Clos for making a scalable telephone circuit switch. It has been used in packet switch fabrics because of its regular interconnections and scalability. Multiple switch modules are interconnected in a Clos-type structure. Each switch module’s size is usually determined by the input/output pin count of a chip or the connectors of a printed circuit board. Each switch module can be a crossbar switch with or without buffers. If without buffers, a global contention resolution scheme is required. If with buffers, the contention can be done within the switch modules in a distributed manner. As the switch grows larger and larger, it is more practical to resolve the contention in a distributed manner. However, because of multiple possible paths between each input and each output pair, the challenge becomes choosing a switch module in the center stage. If not carefully chosen, the load is not balanced among the switch modules in the center stage, causing some center modules to be more congested than others. In addition, due to various delays of the multiple paths between an input/output pair, maintaining the order of the packets in the same flow becomes very challenging. Chapter 13 describes a practical multi-plane, multi-stage buffered switch, called TrueWay. It has the features of scalability, high-speed operations, high-performance, and multicasting. It resolves the issues of: (1) How to efficiently allocate and share the limited on-chip memories; (2) How to intelligently schedule packets on multiple paths while maximizing memory utilization and system performance; (3) How to minimize link congestion and prevent buffer overflow (i.e., stage-to-stage flow control); and (4) How to maintain packet order if the packets are delivered over multiple paths (i.e., port-to-port flow control). A small-scale TrueWay switch has been prototyped using field programmable gate array (FPGA) and SERDES chips with signals running at 3.125 Gbps at the backplane. Chapter 14 describes load-balanced switches. The idea of this type of switch is very interesting. Packets from each input are temporarily and evenly distributed to all other output ports. They are then forwarded to their final destinations. By doing this, the switch fabrics can operate in a cyclic-shifting configuration at each time slot and still achieve 100 percent throughput. One challenging issue of this kind of switch is to maintain packet order. The difference of several proposed schemes lies in the way of resolving the packet out-of-order issue. Since the packets traverse from the input to a temporary output and then from that port to the final output port, one either needs to use two separate switch fabrics or have one switch fabric running at twice the speed of the input. People will argue that the 100 percent throughput is achieved because of the speedup factor of 2. However, the biggest incentive for this kind of switch is that there is no need for an arbitrator to resolve packet contention. Chapter 15 describes optical packet switches. Depending on whether the contended packets are stored in the optical or in the electrical domain, these switch architectures are classified into opto-electronic packet switches and all-optical packet switches. In either case, contention resolution among the arriving packets is handled electronically. It is very challenging to store contending packets in an optical buffer, which is usually implemented by an optical delay line. The storage size and the time that a packet can be stored are quite limited when using optical delay lines. Another challenging issue is to align the optical packets before storing them on the optical delay lines. It requires tremendous effort to align them when traversing different distances from different sources. Until there is a major breakthrough in optical buffering technology, it will remain very difficult to implement all-optical packet switches

REFERENCES 23 Chapter 16 describes high-speed router chip sets.This is the most unique section of the book.Up to this point,emphasis has been on learning the background information necessary to implement a high-performance router,including IP address lookup,packet classification, traffic management,and various techniques to build large-scale.high-speed switch fabrics. This section describes practical commercial chips that are used to implement all the above. Thus,it paves a way for tightly combining theory with practice.These chips include:(1) Network processors for flexible packet processing;(2)Co-processors for route lookup and packet classification;(3)Traffic managers;and(4)Switch fabrics. REFERENCES [1]G.Vareille,F.Pitel,and J.F.Marcerou,3-Tbit/s (300 x 11.6 Gbit/s)transmission over 7380km using C+L band with 25 GHz channel spacing and NRZ format,'in Proc.Opti- cal Fiber Communication Conference and Exhibit,Anaheim,California,vol.4,pp.PD22-1-3 (Mar.2001). [2]R.Ryf et al.,'1296-port MEMS transparent optical crossconnect with 2.07 petabit/s switch capacity:in Proc.Optical Fiber Communication Conference and Exhibit,Anaheim,California, vol.4,pp.PD28-P1 (Mar.2001). [3]N.Spring.R.Mahajan,and D.Wetherall,'Measuring ISP topologies with rocketfuel,'in Proc. ACM SIGCOMM,Pittsburgh,Pennsylvania,pp.133-145(Aug.2002). [4]N.Mckeown,'A fast switched backplane for a gigabit switched router,'Business Communica- tions Review.vol.27.no.12 (Dec.1997). [5]C.Partridge et al.,A fifty gigabit per second IP router,'IEEE/ACM Transactions on Networking,vol.6,no.3.pp.237-248 (June 1998). [6]VIT10:10G transponder and VSC8173/75:physical layer multiplexer/demultiplexer,Vitesse. [Online].Available at:http://www.vitesse.com [7]CA16:2.5 Gbit/s DWDM with 16-channel 155 Mb/s multiplexer and demultiplexer and TB64: Uncoded 10 Gbit/s transponder with 16-channel 622 Mbit/s Multiplexer and Demultiplexer Agere.[Online].Available at:http://www.agere.com [8]M.C.Chow,Understanding SONET/SDH:Standards and Applications,Andan Publisher,1995. [9]A.Romanow and R.Oskouy,'A performance enhancement for packetized ABR and VBR+ data,'ATM Forum 94-0295,Mar.1994.[Online].Available at:http://www.mfaforum.org [10]S.Floyd and V.Jacobson,Random early detection gateways for congestion avoidance,' IEEE/ACM Transactions on Networking,vol.2,no.4,pp.397-413 (Aug.1993). [11]Quality of Service(QoS)Networking,Cisco System,June 1999,white paper. [12]G.Armitage and K.Adams,'Package reassembly during cell loss,'IEEE Network,vol.7,no.5, pp.26-34(Sept.1993). [13]D.Stiliadis and A.Varma,'A general methodology for design efficient traffic scheduling and shaping algortihms,'in Proc.IEEE INFOCOM'97,Kobe,Japan,pp.326-335(Apr.1997). [14]J.C.R.Bennett and H.Zhang.'Hierarchical packet fair queuing algorithms,'IEEE/ACM Transactions on Networking,vol.5,no.5,pp.675-689 (Oct.1997). [15]H.J.Chao and X.Guo,Quality of Service Control in High-Speed Networks,John Wiley Sons, Inc..Sept.2001. [16]'Juniper networks t-series core platforms,'Juniper Inc.[Online].Available at: http://www.juniper.net/products/tseries/ [17]R.Sudan and W.Mukai,Introduction to the Cisco CRS-I Carrier Routing System,Cisco Systems,Inc.Jan.1994

Book1099 — “c01” — 2007/2/16 — 18:26 — page 23 — #23 REFERENCES 23 Chapter 16 describes high-speed router chip sets. This is the most unique section of the book. Up to this point, emphasis has been on learning the background information necessary to implement a high-performance router, including IP address lookup, packet classification, traffic management, and various techniques to build large-scale, high-speed switch fabrics. This section describes practical commercial chips that are used to implement all the above. Thus, it paves a way for tightly combining theory with practice. These chips include: (1) Network processors for flexible packet processing; (2) Co-processors for route lookup and packet classification; (3) Traffic managers; and (4) Switch fabrics. REFERENCES [1] G. Vareille, F. Pitel, and J. F. Marcerou, ‘3-Tbit/s (300 × 11.6 Gbit/s) transmission over 7380 km using C + L band with 25 GHz channel spacing and NRZ format,’ in Proc. Optical Fiber Communication Conference and Exhibit, Anaheim, California, vol. 4, pp. PD22-1-3 (Mar. 2001). [2] R. Ryf et al., ‘1296-port MEMS transparent optical crossconnect with 2.07 petabit/s switch capacity,’ in Proc. Optical Fiber Communication Conference and Exhibit, Anaheim, California, vol. 4, pp. PD28-P1 (Mar. 2001). [3] N. Spring, R. Mahajan, and D. Wetherall, ‘Measuring ISP topologies with rocketfuel,’ in Proc. ACM SIGCOMM, Pittsburgh, Pennsylvania, pp. 133–145 (Aug. 2002). [4] N. Mckeown, ‘A fast switched backplane for a gigabit switched router,’ Business Communications Review, vol. 27, no. 12 (Dec. 1997). [5] C. Partridge et al., ‘A fifty gigabit per second IP router,’ IEEE/ACM Transactions on Networking, vol. 6, no. 3. pp. 237–248 (June 1998). [6] VIT10: 10G transponder and VSC8173/75: physical layer multiplexer/demultiplexer, Vitesse. [Online]. Available at: http://www.vitesse.com [7] CA16: 2.5 Gbit/s DWDM with 16-channel 155 Mb/s multiplexer and demultiplexer and TB64: Uncoded 10 Gbit/s transponder with 16-channel 622 Mbit/s Multiplexer and Demultiplexer, Agere. [Online]. Available at: http://www.agere.com [8] M. C. Chow, Understanding SONET/SDH: Standards and Applications, Andan Publisher, 1995. [9] A. Romanow and R. Oskouy, ‘A performance enhancement for packetized ABR and VBR + data,’ ATM Forum 94-0295, Mar. 1994. [Online]. Available at: http://www.mfaforum.org [10] S. Floyd and V. Jacobson, ‘Random early detection gateways for congestion avoidance,’ IEEE/ACM Transactions on Networking, vol. 2, no. 4, pp. 397–413 (Aug. 1993). [11] Quality of Service (QoS) Networking, Cisco System, June 1999, white paper. [12] G. Armitage and K. Adams, ‘Package reassembly during cell loss,’IEEE Network, vol. 7, no. 5, pp. 26–34 (Sept. 1993). [13] D. Stiliadis and A. Varma, ‘A general methodology for design efficient traffic scheduling and shaping algortihms,’ in Proc. IEEE INFOCOM’97, Kobe, Japan, pp. 326–335 (Apr. 1997). [14] J. C. R. Bennett and H. Zhang, ‘Hierarchical packet fair queuing algorithms,’ IEEE/ACM Transactions on Networking, vol. 5, no. 5, pp. 675–689 (Oct. 1997). [15] H. J. Chao and X. Guo, Quality of Service Control in High-Speed Networks, John Wiley & Sons, Inc., Sept. 2001. [16] ‘Juniper networks t-series core platforms,’ Juniper Inc. [Online]. Available at: http://www.juniper.net/products/tseries/ [17] R. Sudan and W. Mukai, Introduction to the Cisco CRS-1 Carrier Routing System, Cisco Systems, Inc, Jan. 1994

Book1099 — “c02” — 2007/2/15 — 10:31 — page 25 — #1 CHAPTER 2 IP ADDRESS LOOKUP 2.1 OVERVIEW The primary role of routers is to forward packets toward their final destinations. To this purpose, a router must decide for each incoming packet where to send it next, that is, finding the address of the next-hop router as well as the egress port through which the packet should be sent. This forwarding information is stored in a forwarding table that the router computes based on the information gathered by routing protocols. To consult the forwarding table, the router uses the packet’s destination address as a key – this operation is called address lookup [1]. Once the forwarding information is retrieved, the router can transfer the packet from the incoming link to the appropriate outgoing link. Classful Addressing Scheme. IPv4 IP addresses are 32 bits in length and are divided into 4 octets. Each octet has 8 bits that are separated by dots. For example, the address 10000010 01010110 00010000 01000010 corresponds in dotted-decimal notation to 130.86.16.66. The bits in an IP address are ordered as shown in Figure 2.1, where the 1st bit is the most significant bit (MSB) that lies in the leftmost position. The 32nd bit is the least significant bit (LSB) and it lies in the rightmost position. The IP address consists of two parts. The first part contains the IP addresses for networks and the second part contains the IP addresses for hosts. The network part corresponds to the first bits of the IP address, called the address prefix. We will write prefixes as bit strings of up to 32 bits in IPv4 followed by an asterisk(*). For example, the prefix 10000010 01010110* represents all the 216 addresses that begin with the bit pattern 10000010 01010110. Alternatively, prefixes can be indicated using the dotted-decimal notation, so the same prefix can be written as 130.86/16, where the number after the slash indicates the length of the prefix. High Performance Switches and Routers, by H. Jonathan Chao and Bin Liu Copyright © 2007 John Wiley & Sons, Inc. 25

26 IP ADDRESS LOOKUP MSB LSB 2 3 0 31 32 Figure 2.1 IP address bit positions Since routing occurs at the network level to locate the destination network,routers only forward packets based on network level IP addresses.Thus,all hosts attached to the network can be stored in the router's forwarding table by a single network IP address,known as address aggregation.A group of addresses are represented by prefixes.An example of a router's forwarding table is shown in Table 2.1.Each entry in the forwarding table contains a prefix,next-hop IP address,and output interface number.The forwarding information is located by searching for the prefix of the destination address. The Internet addressing architecture was first designed using an allocation scheme known as classful addressing.Classful addressing defines three different sized networks of classes: A,B,or C(Fig.2.2).The classes are based on the amount of IP addresses contained in the network partition.With the IPv4 address space of 32 bits,Class A has a network size of 8 bits and a host size of 24 bits.Class B has a network size of 16bits and a host size of 16 bits.Class C has a network size of 24 bits and a host size of 8 bits.Class D is for multicasting applications. The classful addressing scheme created very few class A networks.Their address space contains 50 percent of the total IPv4 address space (231 addresses out of a total of 232). Class B address space contains 16.384(214)networks with up to65,534 hosts per network. Class Caddress space contains 2,097,152(221)networks with up to 256 hosts per network. Classless Inter-Domain Routing(CIDR)Addressing Scheme.The evolution and growth of the Internet in recent years has proven that the classful address scheme is inflexible and wasteful.For most organizations,class C is too small while class B is too large.The three choices resulted in address space being exhausted very rapidly,even though only a small fraction of the addresses allocated were actually in use.The lack of a network class of a size that is appropriate for mid-sized organizations results in the exhaustion of the class B network address space.In order to use the address space efficiently,bundles of class C addresses were given out instead of class B addresses.This causes a massive growth of forwarding table entries. CIDR [2]was introduced to remedy the inefficiencies of classful addressing.The Inter- net Engineering Task Force (IETF)began implementing CIDR in the early 1990s [2,3]. With CIDR,IP address space is better conserved through arbitrary aggregation of network TABLE 2.1 Router's Forwarding Table Structure [1] Destination Address Prefix Next Hop IP Address Output Interface 24.40.32/20 192.41.177.148 2 130.86/16 192.41.177.181 6 208.12.16/20 192.41.177.241 4 208.12.21/24 192.41.177.196 1 167.24.103/24 192.41.177.3 4

Book1099 — “c02” — 2007/2/15 — 10:31 — page 26 — #2 26 IP ADDRESS LOOKUP Figure 2.1 IP address bit positions. Since routing occurs at the network level to locate the destination network, routers only forward packets based on network level IP addresses. Thus, all hosts attached to the network can be stored in the router’s forwarding table by a single network IP address, known as address aggregation. A group of addresses are represented by prefixes. An example of a router’s forwarding table is shown in Table 2.1. Each entry in the forwarding table contains a prefix, next-hop IP address, and output interface number. The forwarding information is located by searching for the prefix of the destination address. The Internet addressing architecture was first designed using an allocation scheme known as classful addressing. Classful addressing defines three different sized networks of classes: A, B, or C (Fig. 2.2). The classes are based on the amount of IP addresses contained in the network partition. With the IPv4 address space of 32 bits, Class A has a network size of 8 bits and a host size of 24 bits. Class B has a network size of 16 bits and a host size of 16 bits. Class C has a network size of 24 bits and a host size of 8 bits. Class D is for multicasting applications. The classful addressing scheme created very few class A networks. Their address space contains 50 percent of the total IPv4 address space (231 addresses out of a total of 232). Class B address space contains 16,384 (214) networks with up to 65,534 hosts per network. Class C address space contains 2,097,152 (221) networks with up to 256 hosts per network. Classless Inter-Domain Routing (CIDR) Addressing Scheme. The evolution and growth of the Internet in recent years has proven that the classful address scheme is inflexible and wasteful. For most organizations, class C is too small while class B is too large. The three choices resulted in address space being exhausted very rapidly, even though only a small fraction of the addresses allocated were actually in use. The lack of a network class of a size that is appropriate for mid-sized organizations results in the exhaustion of the class B network address space. In order to use the address space efficiently, bundles of class C addresses were given out instead of class B addresses. This causes a massive growth of forwarding table entries. CIDR [2] was introduced to remedy the inefficiencies of classful addressing. The Internet Engineering Task Force (IETF) began implementing CIDR in the early 1990s [2, 3]. With CIDR, IP address space is better conserved through arbitrary aggregation of network TABLE 2.1 Router’s Forwarding Table Structure [1] Destination Address Prefix Next Hop IP Address Output Interface 24.40.32/20 192.41.177.148 2 130.86/16 192.41.177.181 6 208.12.16/20 192.41.177.241 4 208.12.21/24 192.41.177.196 1 167.24.103/24 192.41.177.3 4