Introduction to Computer Networks CMPE 150 Fall 2005 Lecture 23 CMPE 150 Introduction to Computer Networks 1 Announcements Homework 4 due on Wed 11 23 05 No class on Friday 11 25 05 We will have a real lab next week CMPE 150 Introduction to Computer Networks 2 Last Class Routing cont d Finished DV Link State Hierarchical routing CMPE 150 Introduction to Computer Networks 3 Today Finish routing Many to many routing Broadcast Multicast Internetworking CMPE 150 Introduction to Computer Networks 4 Many to Many Routing Support many to many communication Example applications multi point data distribution multi party teleconferencing CMPE 150 Introduction to Computer Networks 5 Broadcasting Send to ALL destinations Several possible routing mechanisms to broadcasting Simplistic approach send separate packet to each destination Simple but expensive Source needs to know about all destinations Flooding May generate too many duplicates depending on node connectivity CMPE 150 Introduction to Computer Networks 6 Multidestination Routing Packet contains list of destinations Router checks destinations and determines on which interfaces it will forward packet Router generates new copy of packet for each output line and includes in packet only the appropriate set of destinations Eventually packets will only carry 1 destination CMPE 150 Introduction to Computer Networks 7 Spanning Tree Routing Use spanning tree sink tree rooted at broadcast initiator No need for destination list Each on spanning tree forwards packets on all lines on the spanning tree except the one the packet arrived on Efficient but needs to generate the spanning tree and routers must have that information CMPE 150 Introduction to Computer Networks 8 Reverse Path Forwarding Routers don t have to know spanning tree Router checks whether broadcast packet arrived on interface used to send packets to source of broadcast If so it s likely that it followed best route and thus not a duplicate router forwards packet on all lines If not packet discarded as likely duplicate CMPE 150 Introduction to Computer Networks 9 Broadcast Routing Reverse path forwarding a A subnet b a Sink tree c The tree built by reverse path forwarding CMPE 150 Introduction to Computer Networks 10 Multicasting Special form of broadcasting Instead of sending messages to all nodes send messages to a group of nodes Multicast group management Creating deleting joining leaving group Group management protocols communicate group membership to appropriate routers CMPE 150 Introduction to Computer Networks 11 Multicast Routing Each router computes spanning tree covering all other participating routers Tree is pruned by removing branches that do not contain any group members 2 1 1 2 1 2 2 1 2 2 1 1 CMPE 150 Introduction to Computer Networks 2 1 1 1 1 2 1 2 1 1 1 2 2 1 2 2 2 2 12 Shared Tree Multicasting Source rooted tree approaches don t scale well 1 tree per source per group Routers must keep state for m n trees where m is number of sources in a group and n is number of groups Core based trees single tree per group Host unicast message to core where message is multicast along shared tree Routes may not be optimal for all sources State storage savings in routers CMPE 150 Introduction to Computer Networks 13 Internetworking CMPE 150 Introduction to Computer Networks 14 Internetworking What is it Connecting networks together forming a single internet CMPE 150 Introduction to Computer Networks 15 Connecting Networks A collection of interconnected networks CMPE 150 Introduction to Computer Networks 16 How Networks Differ 5 43 CMPE 150 Introduction to Computer Networks 17 How Networks Can Be Connected a Two Ethernets connected by a switch b Two Ethernets connected by routers CMPE 150 Introduction to Computer Networks 18 How to Internet Connection oriented versus connectionless internetworking Connection oriented internetworking Based on VC concatenation Connectionless internetworking follows the datagram model CMPE 150 Introduction to Computer Networks 19 Concatenated Virtual Circuits Gateway Builds VC crossing the different networks Use of gateways to perform necessary conversions CMPE 150 Introduction to Computer Networks 20 Connectionless Internetworking Follows datagram model Packets from Host X to Host Y may follow different routes Gateways make routing decisions and perform translations CMPE 150 Introduction to Computer Networks 21 Translating versus Gluing Translation converting between different protocols Hard Alternative gluing I e using the same network layer protocol everywhere That s what IP does CMPE 150 Introduction to Computer Networks 22 Tunneling Interconnecting source and destination on separate networks but of the same type S D CMPE 150 Introduction to Computer Networks 23 Tunneling Analogy CMPE 150 Introduction to Computer Networks 24 More Tunneling CMPE 150 Introduction to Computer Networks 25 Internetwork Routing Example a An internetwork b A graph of the internetwork CMPE 150 Introduction to Computer Networks 26 Internetwork Routing Inherently hierarchical Routing within each network interior gateway protocol IGP Routing between networks exterior gateway protocol EGP Within each network different routing algorithms can be used Each network is autonomously managed and independent of others autonomous system AS CMPE 150 Introduction to Computer Networks 27 Internetwork Routing Cont d Typically packet starts in its LAN Gateway receives it broadcast on LAN to unknown destination Gateway sends packet to gateway on the destination network using its routing table If it can use the packet s native protocol sends packet directly Otherwise tunnels it CMPE 150 Introduction to Computer Networks 28 Fragmentation Happens when internetworking Network specific maximum packet size Width of TDM slot OS buffer limitations Protocol number of bits in packet length field Maximum payloads range from 48 bytes ATM cells to 64Kbytes IP packets CMPE 150 Introduction to Computer Networks 29 Problem What happens when large packet wants to travel through network with smaller maximum packet size Fragmentation Gateways break packets into fragments each sent as separate packet Gateway on the other side have to reassemble fragments into original packet 2 kinds of fragmentation transparent and nontransparent CMPE 150 Introduction to Computer Networks 30 Types of Fragmentation a Transparent fragmentation Nontransparent fragmentation CMPE 150 Introduction to Computer Networks b 31
View Full Document
Unlocking...