Lecture 8 - Routing

Routers

Direct packets of data where they need to go, hop by hop

Routing

The action of selecting paths along which to send data

Every ISP forms a …

Domain, called an Autonomounous System (AS). Has Inter-As and Intra-AS.

Cruicial Features of Routing

1. Addressing

2. Routing

   1.  Forwarding

IP Address

Internet Protocol Access, Decimal numbers separated by dots

IP Address Length

IPv4: 32 bits (8 bits a number)

IPv6: 128 bits

IP Prefix

Indicates the device’s subnet, denoted with a forward slash  

Host Indentifier

Indicates host within subnet, comes after the prefix

DHCP

Dynamic Host Configuration Protocol, keeps track of which addresses are unused, typically in a local network. After finite time, address is either renewed or released.

NAT

Network Address Translation Router, translates back and forth.

Address in local network that may be different than address in public Internet.

Intra-AS

Metric based, find shortest path. Uses Routing Information Protocol (RIP)

Open Shortest Path First (OSPF)

Inter-AS

Policy based, go through cheapest ISPs. Border Gateway Protocol (BGP)

Forwarding Method

Implements the routing policy one hop at a time..Whe

n a packet arrives at a router’s input port…

It examines the destination IP and then the routing table tells it which port to send the packet out.

Shortest Path Problem

Trying to find the path with the smallest cost from one node to another.

Bellman-Ford

Used to find the shortest cost path and is iterative, used in the original ARPANET

Message Passing

Short, local interaction: neighbor to neighbor. Local view: each router only knows next hop, nothing beyond that.