Interconnection Networks and ClustersOutlineInterconnection NetworksSlide 4Interconnection MediaNetwork Topology- Centralized SwitchingNetwork Topology - Switch BoxesSlide 8Slide 9Network Topology- Distributed SwitchingSlide 11Network Topology - HypercubesSlide 13Network Topology - Real WorldSlide 15Cluster vs. MultiprocessorsSlide 17Case Study - GoogleSlide 19Google- How It Works?Cluster Project at UCFReferencesInterconnection Networks and ClustersbyOnur OzyerSchool of Electrical Engineering and Computer Science University of Central FloridaOutline•Interconnection Networks•Network Topology–Centralized Switching–Distributed Switching•Clusters–Case Study: Google –Case Study: Cluster Project at UCF•ReferencesInterconnection Networks•Connection of components within a computer.•Connecting computers to build information network.Interconnection NetworkEnd UsersInterconnection NetworkEnd UsersInternetworkingInterconnection NetworksMessageBandwidth = Propagation rate to the link Transmission Delay = Message Size / BandwidthPropagation Delay: Time to propagate over the linkTotal Delay = Processing Delay + Transmission Delay + Propagation DelayHeader Data Check SumInterconnection Media•Twisted Pair wires –Level 3 ~ 10 Mbit/s–Level 5 ~ 100 Mbit/s–Cat 5 ~ 1000 Mbit/s•Coaxial cable ~ 10 Mbit/s•Fiber optics ~100 Mbit/s – 1Gbit/s (one way)–Light Source, laser diode or LED–Fiber optic cable –Light detectorNetwork Topology- Centralized SwitchingA) Crossbar Topology: Any node connected to any node. (Fully connected)•n2 switches. •Low Contention.a) Source Routingb) Destination Routing P0P1P2P3Network Topology - Switch BoxesStraightSwap Lower BroadcastUpper BroadcastNetwork Topology- Centralized SwitchingB) Omega Network: Nodes connected to switch boxes. Each switch box has 4 switches.•Less switch (n/2 lgn)•More contention (blocking)P0P1P2P3Network Topology- Centralized SwitchingC) Fat Tree: Nodes and switches form a tree. Bandwidth is added higher in the tree.•Multiple paths (load balance, failure recovery)•Doubling nodes need one more level of switchesSwitchesEnd UsersNetwork Topology- Distributed SwitchingDistributed Switching: Each node has own switch Ring Network: Sequence of nodes connected together. •Average message delay: n/2 switches.•Simultaneous message transfer on the ring.•Token ringsNetwork Topology- Distributed Switching2D Grid3D Cube•d-dimensional array–n = kd-1 X ...X kO nodes–described by d-vector of coordinates (id-1, ..., iO)•d-dimensional k-ary mesh: N = kd–k = dN–described by d-vector of radix k coordinate •d-dimensional k-ary torus (or k-ary d-cube)?2D TorusNetwork Topology - Hypercubes•Also called binary n-cubes. # of nodes = N = 2d.•O(logN) Hops•Good bisection BW•Complexity–Out degree is dBisection BW: The bandwidth between two equal logical subparts.0-D 1-D 2-D 3-D4-D5-D !Network Topology- Distributed SwitchingTopology Degree Diameter Ave Dist Bisection BW1D Array 2 N-1 N / 3 11D Ring 2 N/2 N/4 22D Mesh 4 2 (N1/2 - 1) 2/3 N1/2N1/22D Torus 4 N1/21/2 N1/22N1/2k-ary n-cube 2n nk/2 nk/4 nk/4Hypercube n =log N n n/2Network Topology - Real WorldNetwork Topology- Distributed Switching Problems•2d mapping of 3d topologies.•Internal speed of the switch is constant, •Bandwidth can be bottleneckCluster vs. MultiprocessorsA Cluster is coordinated use of interconnected computers in a machine room.Challenges for Clustering• I/O Bus is slower and has more conflicts than memory bus.•Administration problems•Low memory usage efficiency …but memory cost is going down.Cluster vs. MultiprocessorsAdvantages•Fault Isolation , easy to replace failures •Scalability, expandability without stopping the application•Low cost, large scale multiprocessors cost more•Increasing communications bandwidth•Separate address space limits contamination error.–Hotmail, Google Inktomi, Aol, Amazon, Yahoo using clustered computers.Case Study - Google•Stores and indexes Web combining more than 15 000 commodity-class PC’s in 1 petabyte (=1 000 000 GB) disk storage.•1 query =100 MB data+ 106 CPU cycle.•About 1000 query/s at peak time.•Crawls web and updates indexes every 4 weeks•3 collocation sites ( 2 California + 1 Virginia)•Service time < 0.5 secCase Study - Google•Each site has 2488 Mbit/sec connection to Internet. •Sites linked to sister sites for emergencies.•Each site has 2 switches of 128 1 Gbit/s Ethernet link. Switches are connected to racks.• 40 Racks at each site and each rack has 80 PCs’.•PC range from Celeron5300 to 1.4 GHz Intel Pentium III with 80 Gbyte hard disk running Linux.Google- How It Works? 1.Search QueryGoogle ClusterGWS GWS GWSGWS GWSGoogle Web Server(GWS)Index ServersDocument Servers2.3.5Spell CheckerAd Server4Cluster Project at UCFParts Ordered Costs(135) AMD T-Bird 900MHz Processors $24,975.00(135) ASUS -A7V Motherboards $20,925.00.(15) Asante Interstack 8000 Switch, Hub, Card. $12,880.25(15) Asante Interstack 8000 Switch, Hub, $12,778.00(144) HD's, (5) RAID controllers $15,881.48(128) ATI Rage Pro AGP video cards $4,480.00(150) Netgear 10/100 NICs $2,589.00(135) PC133 DIMM 256MB $15,120.00CasesSelection PendingMisc.(Racks,cables, UPS,etc.)$2,000.00References•J. L. Hennessy and D. A. Patterson. Computer Architecture: A Quantitative Approach. Morgan Kaufmann, San Mateo, CA, 2001.•J. F. Kurose and K. W. Ross, Computer Networks: A Top-Down Approach Featuring the Internet, 2nd edition. Addison Wesley, 2002.•A. DeCegama: Technology of Parallel Processing, 1989.•L. A. Barraso, J. Dean and U. Holzle. Web Search For A Planet: The Google Cluster Architecture. IEEE icro.