Broacast Routing

JMU

Broacast Routing
An Introduction

Prof. David Bernstein
James Madison University

Computer Science Department

bernstdh@jmu.edu

Overview

Unicast:
- One sender and one receiver
Broadcast:
- One sender and all receivers
Multicast:
- One sender and a group of receivers

Uncontrolled Flooding

Approach:
- Source sends a copy of the packet to all of its neighbors
- Each node does the same
Problems:
- A cycle in the network causes the process to continue forever
- When a node is connected to more than two others it will create and forward multiple copies causing a broadcast storm

Controlled Flooding

Sequence Number Control:
- The source includes its address and a sequence number in the packet
- Each node keeps track of packets and doesn't re-broadcast
Reverse Path Forwarding (RPF):
- The source includes its address
- If the incoming link is on its shortest path back to the source then a node transmits the packet on all other links

Spanning Tree Broadcast

Definitions:
- A spanning tree is a tree that contains every node in the graph
- A minimal spanning tree is a spanning tree that has minimum total link costs/weights
Broadcasting:
- Each node knows the spanning tree
- Each node broadcasts only to those links that are in the spanning tree