[Network week2] Forwarding, Routing table, Address Aggregation, Longest Prefix Matching

• Router at Home
  
  : Connect mobiles and notebooks to Internet
  : Implement NAT and DHCP functions
  

• Router in backbone
  
  : 35 interface card
  : 35 different network addresses are available

• What does a router do?
  
  : Connect two or more networks
  Has two or more network interfaces and IP addresses

• Functions in Network Layer
  
  -- Main objective of network layer
  : Transport packets from source to destination
  -- Two mechanisms are used in network layer
  : Forwarding and routing

• Forwarding and Routing

  1) Forwarding

  : Mechanism to determine an interface each packet should be sent to reach its destination
  : Move packets from router's input to appropriate router output by looking up the routing table

  2) Routing : control plane

  : Mechanism that distributes to all routers information to build their routing tables
  : Each router computes paths packets will follow
  : Routers talking amonst themselves
  : Based on sharing information individual router creates a routing table

Forwarding

• Efficient look-up to a routing table
• A format and size of a routing table matter

Route vs. Next-hop (win)

: Not specify an entire route (path) to destination in the routing table
--> Only next-hop host toward destination

Host-specific vs Network-specific (win)

: Too many hosts in Internet to remember
--> A, B, C and D can be summarized in network N2

Direct against Indirect Delivery

• Direct delivery for hosts inside networks
  : Using host address
• Indirect delivery for hosts outside networks
  : Using network address

Default Method

• Further decrease the size of routing table by default method
  : Specify all known networks in the table and rest of the networks is included in a default

Common Fields in Routing Table

• Forwarding based on destination
• Network-specific routing table
  : Forwarding table is searched based on network address
  : Destination address in the packets gives no clue about the network address
• When a host has a packet to send or a router has received a packet to be forwarded
  : It looks a routing(forwarding) table to find the next-hop IP address to deliver the packet to
  : compare destination IP address with each entry in the routing table to find a match
  

Sample Routing Table in Linux

Example

Address Aggregation

• For classful, a single entry for each site in the table
• For classless, it is likely that the number of forwarding table entries will increase
  : Division of whole address space into blocks
  : Each blocks needs to be in the table

Longest Prefix Matching

• Org. 4 cannot be connected to R1 for some reasons
• A packet arrives at R2 with DST 140.24.7.200

Example

-> Routing Table for R1

Hierarchical Routing

• A regional ISP is granted 16,384 addresses starting from 120.14.64.0/18
  : The regional ISP has decided to divide this block into four subblocks, each with 4096 addresses
  : 01111000 00001110 01000000 00000000
  : Three of these subblocks are assigned to three local ISPs.
  : Second subblock is reserved for future use

Example

• The first local ISP has divided its assigned subblock into 8 smaller blocks and assigned each to a small ISP
  : 4096= 2^12 -> 2^12/2^3 = 512
  : 01111000 00001110 01000000 00000000 / 120.14.64.0
  : 01111000 00001110 01001000 00000000 / 120.14.72.0
• The second local ISP has divided its block into 4 blocks and has assigned the addresses to four large organizations
• The third local ISP has divided its block into 16 blocks and assigned each block to a small organization. Each small organization has 256 addresses, and the mask is /24.
• There is a sense of hierarchy in this configuration
  : All routers in the Internet send a packet with destination address 120.14.64.0 to 120.14.127.255 to the border router in the regional ISP

Geographical Routing

• Divide entire address psace into a few large blcks
  : Assign a block to America, a block to Europe and so on
• Router of ISPs outside of Europe will have only single entry for packets to Euripe in their forwarding table