Review❒ The Internet (IP) Protocol❍ Datagram format❍ IP fragmentation❍ ICMP: Internet Control Message Protocol❍ NAT: Network Address Translation❒ Routing in the Internet❍ Intra-AS routing: RIP and OSPF❍ Inter-AS routing: BGPSome slides are in courtesy of J. Kurose and K. RossIP datagram formatverlength32 bitsdata (variable length,typically a TCP or UDP segment)16-bit identifierInternetchecksumtime tolive32 bit source IP addressIP protocol versionnumberheader length(bytes)max numberremaining hops(decremented at each router)forfragmentation/reassemblytotal datagramlength (bytes)upper layer protocolto deliver payload tohead.lentype ofservice“type” of data flgsfragmentoffsetupperlayer32 bit destination IP addressOptions (if any)E.g. timestamp,record routetaken, specifylist of routers to visit.how much overhead with TCP?❒ 20 bytes of TCP❒ 20 bytes of IP❒ = 40 bytes + app layer overheadWhy different Intra- and Inter-AS routing ?Policy:❒ Inter-AS: admin wants control over how its traffic routed, who routes through its net. ❒ Intra-AS: single admin, so no policy decisions neededScale:❒ hierarchical routing saves table size, reduced update trafficPerformance:❒ Intra-AS: can focus on performance❒ Inter-AS: policy may dominate over performanceOverview❒ Multicast Routing❒ Data Link Layer ServicesSome slides are in courtesy of J. Kurose and K. RossMulticast: one sender to many receivers❒ Multicast: act of sending datagram to multiple receivers with single “transmit” operation❍ analogy: one teacher to many students❒ Question: how to achieve multicastMulticast via unicast❒ source sends N unicast datagrams, one addressed to each of N receiversmulticast receiver (red)not a multicast receiver (red)routersforward unicastdatagramsMulticast: one sender to many receivers❒ Multicast: act of sending datagram to multiple receivers with single “transmit” operation❍ analogy: one teacher to many students❒ Question: how to achieve multicastNetwork multicast❒ Router actively participate in multicast, making copies of packets as needed and forwarding towards multicast receiversMulticastrouters (red) duplicate and forward multicast datagramsMulticast: one sender to many receivers❒ Multicast: act of sending datagram to multiple receivers with single “transmit” operation❍ analogy: one teacher to many students❒ Question: how to achieve multicastApplication-layer multicast❒ end systems involved in multicast copy and forward unicast datagrams among themselvesInternet Multicast Service Modelmulticast group concept: use of indirection❍ hosts addresses IP datagram to multicast group❍ routers forward multicast datagrams to hosts that have “joined” that multicast group128.119.40.186128.59.16.12128.34.108.63128.34.108.60multicast group226.17.30.197Multicast groups class D Internet addresses reserved for multicast: host group semantics:o anyone can “join” (receive) multicast groupo anyone can send to multicast groupo no network-layer identification to hosts of membersneeded:infrastructure to deliver mcast-addressed datagrams to all hosts that have joined that multicast groupJoining a mcast group: two-step process❒local:host informs local mcast router of desire to join group: IGMP (Internet Group Management Protocol)❒wide area:local router interacts with other routers to receive mcast datagram flow❍ many protocols (e.g., DVMRP, MOSPF, PIM)IGMPIGMPIGMPwide-areamulticast routingMulticast Routing: Problem Statement❒Goal:find a tree (or trees) connecting routers having local mcast group members ❍tree:not all paths between routers used❍source-based:different tree from each sender to rcvrs❍shared-tree:same tree used by all group membersShared treeSource-based treesApproaches for building mcast treesApproaches:❒ source-based tree: one tree per source❍ shortest path trees❍ reverse path forwarding❒ group-shared tree: group uses one tree❍ minimal spanning (Steiner) ❍ center-based treesShortest Path Tree❒ mcast forwarding tree: tree of shortest path routes from source to all receivers❍ Dijkstra’s algorithmR1R2R3R4R5R6R7216345irouter with attachedgroup memberrouter with no attachedgroup memberlink used for forwarding,i indicates order linkadded by algorithmLEGENDS: sourceReverse Path Forwardingif (mcast datagram received on incoming link on shortest path back to center)thenflood datagram onto all outgoing linkselseignore datagram rely on router’s knowledge of unicast shortest path from it to sender each router has simple forwarding behavior:Reverse Path Forwarding: example• result is a source-specific reverseSPT– may be a bad choice with asymmetric linksR1R2R3R4R5R6R7router with attachedgroup memberrouter with no attachedgroup memberdatagram will be forwardedLEGENDS: sourcedatagram will not be forwardedReverse Path Forwarding: pruning❒ forwarding tree contains subtrees with no mcast group members❍ no need to forward datagrams down subtree❍ “prune” msgs sent upstream by router with no downstream group membersR1R2R3R4R5R6R7router with attachedgroup memberrouter with no attachedgroup memberprune messageLEGENDS: sourcelinks with multicastforwardingPPPShared-Tree: Steiner Tree❒ Steiner Tree: minimum cost tree connecting all routers with attached group members❒ problem is NP-complete❒ excellent heuristics exists❒ not used in practice:❍ computational complexity❍ information about entire network needed❍ monolithic: rerun whenever a router needs to join/leaveCenter-based trees❒ single delivery tree shared by all❒ one router identified as “center”of tree❒ to join:❍ edge router sends unicast join-msgaddressed to center router❍join-msg “processed” by intermediate routers and forwarded towards center❍join-msgeither hits existing tree branch for this center, or arrives at center❍ path taken by join-msgbecomes new branch of tree for this routerCenter-based trees: an exampleSuppose R6 chosen as center:R1R2R3R4R5R6R7router with attachedgroup memberrouter with no attachedgroup memberpath order in which join messages generatedLEGEND2131Overview❒ Multicast Routing❒ Data Link Layer ServicesSome slides are in courtesy of J. Kurose and K. RossLink Layer: IntroductionSome terminology:❒ hosts and routers are nodes(bridges and switches too)❒ communication channels that connect adjacent nodes along communication path are links❍ wired links❍ wireless links❍