William Stallings Data and Computer …

1 data and Computer Communications InterNetwork Operation Internetwork Operation Historically IP nets gave best-effort datagram delivery to all services Now want variety of QoS in IP networks Explore some new network services / functionsMulticasting Sending packet to addresses referring to group of hosts on one or more networks Multimedia (transmission to multiple users) Teleconferencing (forming a multicast group) Database (all copies are updated) Distributed computing (sending results to all) Real time workgroups (files exchange between active group) Have design issues in addressing / routingLAN Multicast LAN multicast is easy Send to IEEE 802 multicast MAC address Since broadcast all stations will see packet Those in multicast group will accept it Only single copy of packet is needed But much harder in internetworkMulticasting in Internetworks Broadcast packet to each network server does not know members of the MC group Send multiple unicast packets each net with members in multicast group receives a copy Use true multicast send single packets over any link duplicating as needed to reach destination netsL1: 1L2: 0L3: 1L4: 2N1: 4N4: 2N2: 0N3: 1N5: 1N6.

2 1------13 MCG={N3, N5, N6}S=N1 Does not acceptBroadcast packet to each network- server does not know members of the MC groupL1: 0L2: 0L3: 1L4: 2N1: 3N4: 2N2: 0N3: 1N5: 1N6: 1------11 MCG={N3, N5, N6}S=N1N3,N5 & N6 Send multiple unicast packets- each net with members in multicast group receives a copyTrue Multicast Determine least cost path to each network that has host in group This results in a spanning tree of just those nets with members in MCG Transmit single packet along spanning tree Routers replicate packets at branch points of spanning treeTrue Multicast using Spanning TreeMake sure you know how to generate the SPOnly 8 packets Lower link utilization!True Multicast using Spanning Tree Alternative Spanning TreeRequirements for Multicasting Router may have to forward more than one copy of packet Need convention to identify multicast addresses (IPv4 Class D or IPv6 prefix) Node translate between IP multicast addresses and list of networks containing group members Router must translate between IP multicast address and LAN multicast address (IP 48 bit MAC-level multicast address)

3 A mechanism is required for hosts to join and leave multicast group Routers must exchange info which networks include members of given group sufficient info to work out shortest path to each network Routing algorithm to work out shortest path Routers must determine routing paths based on source and destination addressesAvoid unnecessary duplications and finding the shortest path! Operation of Internet Group Management Protocol (IGMP) Allows exchanging multicast group membership information over the LAN Who has joined; who is leaving IGMPv1and IGMPv2 operational model: receivers have to subscribe to groups sources do not have to subscribe to groups any host can send traffic to any multicast group problems: spamming of multicast groups waste of resources establishment of distribution trees is problematic finding globally unique multicast addresses difficult many multicast groups with the same multicast addressOperation of Internet Group Management Protocol (IGMP) V3 Addresses weaknesses: allows hosts to specify list from which they want to receive traffic.

4 RX(N1)={N3, N5} traffic from other hosts blocked at routers allows hosts to block packets from sources that send unwanted trafficIGMP Operation Joining IGMP host wants to make itself known as group member to other hosts and routers on LAN IGMPv3 can signal group membership with filtering capabilities with respect to sources EXCLUDE mode all members except those listed I receive packet from anyone sending to MCG EXCEPT INCLUDE mode only from group members listed I ONLY receive packet from .. sending Pkt. to MCG To join send IGMP membership report message address field multicast address of group (MCG) sent in IP datagram current group members receive & learn new member routers listen to all IP multicast addresses to hear all reportsIP PacketDest.

5 MCG1 Refer to your notesIGMP Operation Keeping Lists Valid routers periodically issue IGMP general query message in datagram with all-hosts multicast address hosts must read such datagrams hosts respond with report message router don t know every host in a group needs to know at least one group member still active each host in group sets timer with random delay host hearing another report cancels own if timer expires, host sends report only one member of each group reports to routerIGMP Operation - Leaving host leaves group by sending leave group message to all-routers static multicast address sends a membership report message with EXCLUDE option and null list of source addresses router determines if have any remaining group members using group-specific query messageRouting Protocols Basic Idea in Packet Routing Routers receive and forward packets Make decisions based on knowledge of topology and traffic/delay conditions Use dynamic routing algorithm Routing decisions are based on.

6 Routing information - about topology & delays Routing algorithm - that makes routing decisions based on informationAutonomous Systems (AS) Is a group of routers and networks managed by single organization Which exchange information via a common routing protocol Form a connected network at least one path between any pair of nodes except in times of failureInterior Router Protocol & Exterior Routing Protocol Interior router protocol (IRP) passes routing information between routers within AS Exterior router protocol (ERP) passes routing information between routers in different ASs supports summary information on AS reachabilityGathering and Using Routing Information Remember: Routing decisions are based on: Routing information - about topology & delays Routing algorithm - that makes routing decisions based on information Three approaches Distance-vector routing Link-state routing Path-vector routing Approaches to Routing Distance-vector Each node (router or host) exchanges information with neighboring nodes Used for first generation routing algorithm for ARPANET eg.

7 Used by Routing Information Protocol (RIP) Each node maintains vector of link costs for each directly attached network and distance and next- hop vectors for each destination Requires transmission of lots of information between routers distance vector & estimated path costs to all network Changes take long time to to Routing Link-state Designed to overcome drawbacks of distance-vector Each router determines link cost on each interface Advertises set of link costs to all other routers in topology (floods) If link costs change, router advertises new values Each router constructs topology of entire configuration can calculate shortest path to each dest use to construct routing table with first hop to each dest Does not use distributed routing algorithm, but any suitable alg to determine shortest paths, eg.

8 Dijkstra's algorithm Open Shortest Path First (OSPF) is a link-state to Routing Link-state (Router A)What Exterior Routing Protocols are not link-state and distance-vector not effective for exterior router protocol distance-vector assumes routers share common distance metric but different ASs may have different priorities & needs but have no info on AS s visited along route link-state different ASs may use different metrics and have different restrictions flooding of link state information to all routers unmanageableExterior Router Protocols Path-vector Alternative path-vector routing protocol provides info about which networks can be reached by a given router and ASs crossed to get there does not include distance or cost estimate Have list of all ASs

9 Visited on a route - what is reachable Enables router to perform policy routing eg. avoid path to avoid transiting particular AS eg. link speed, capacity, tendency to become congested, and overall quality of operation, security eg. minimizing number of transit ASsBorder Gateway Protocol (BGP) Developed for use with TCP/IP internets is preferred Exterior routing protocol of the Internet uses messages sent over TCP connection functional procedures neighbor acquisition - when agree to exchange info What to talk? Uses OPEN and Keep alive (accept) messages neighbor reachability - to maintain relationship Want to be my friend and stay in touch? Keep alive message network reachability - to update database of routes Let me tell you about my network Update message (broadcasted) BGP Messages Open Update Keep alive NotificationBGP Routing Information ExchangeR1 and R5 Implement BGPR1 talks to R5 on behalf of R2 (network )R2 talks to R1 using IRPBGP Routing Information ExchangeBGP allows exchange of routing information between ASsR1 and R5 Implement BGPOpen Shortest Path First IGP of Internet Replaced Routing Information Protocol (RIP)

10 Use Link State Routing Algorithm each router keeps list of state of local links to network transmits update state info little traffic as messages are small and not sent often Uses least cost based on user cost metric Topology stored as directed graph vertices or nodes (router, transit or stub network) edges (between routers or router to network)Example OSPF ASDirected Graph of ASSPF Tree for Router 6