TCP/IP Essentials A Lab-Based Approach Chapter 4 Static

TCP/IP Essentials A Lab-Based Approach Chapter 4 Static

TCP/IP Essentials A Lab-Based Approach Chapter 4 Static and Dynamic Routing Shivendra Panwar, Shiwen Mao Jeong-dong Ryoo, and Yihan Li Routing Transfer packets from a source to a destination using network layer protocol information. Two activities: Determine optimal routing paths Transport packets through an internetwork Routing table

records optimal routes. Is consulted when a forwarding decision is to be made. Can be set manually, updated by an ICMP message received, or by using dynamic routing protocols. Panwar, Mao, Ryoo, Li: TCP/IP Essentials 2 Next-hop Routing Direct delivery: send datagram directly when the source and the destination are on the same network. Indirect delivery: not on the same network Send datagram to a router. Consult the routing table to determine the next hop router. Only one hop on the path is listed in the routing table.

Panwar, Mao, Ryoo, Li: TCP/IP Essentials 3 Routing Table Flags: U: route is up G: route is to a gateway (router); if flag is not set, destination is directly connected H: route is to a host, I.e., destination address is the complete host address; if flag is not set, route is to a network and destination address is netID or subnetID

D: route created by redirect M: route modified by redirect Destination IP address The IP address of the next-hop router, or of a directly connected network. The hosts network interface For each IP packet, there is one routing table lookup. Find matching host address 2. Find matching network address 3. Find default entry 1. Panwar, Mao, Ryoo, Li: TCP/IP Essentials 4 Statically Setting IP Routing Tables There are several ways for setting IP routing tables without a routing protocol (Static Routing) Automatic creation of entry during initialization of a local interface (with ifconfig) During bootstrap with route command

Via ICMP redirect messages Via ICMP router advertisement/router discovery messages Panwar, Mao, Ryoo, Li: TCP/IP Essentials 5 ICMP Redirect Based on routing data in host, it does an arp for router 1 and sends packet to router 1 When router 1 detects that an IP datagram should have gone to a different router, the router: forwards the IP datagram to the correct router sends an ICMP redirect message to the host Host uses ICMP message to update its routing table (1) IP datagram (3) ICMP Redirect

(2) IP datagram RouterLi: 1 TCP/IP Essentials Panwar, Mao, Ryoo, Router 2 6 ICMP Router Discovery Configure the default route for a host when it bootstraps. After bootstrapping a host broadcasts an ICMP router solicitation message. In response, routers send an ICMP router advertisement message Also, routers periodically broadcast ICMP router advertisement Panwar, Mao, Ryoo, Li: TCP/IP Essentials 7 Dynamic Routing

Dynamic routing is used to eliminate loops in paths, and react to changes in the network topology. Autonomous System Panwar, Mao, Ryoo, Li: TCP/IP Essentials 8 Autonomous Systems An autonomous system is a region of the Internet that is administered by a single entity. Examples of autonomous regions are: Polys campus network MCIs backbone network

Regional Internet Service Provider Routing is done differently within an autonomous system (intradomain routing) and between autonomous system (interdomain routing). Panwar, Mao, Ryoo, Li: TCP/IP Essentials 9 Autonomous Systems (AS) Ethernet Autonomous System 1 Ethernet Router Ethernet Router Router Router Ethernet

Router Autonomous System 2 Ethernet Router Ethernet Panwar, Mao, Ryoo, Li: TCP/IP Essentials 10 Interdomain and Intradomain Routing Intradomain Routing Routing within an AS Ignores the Internet outside the AS

Protocols for Intradomain routing are also called Interior Gateway Protocols or IGPs. Popular protocols are RIP (simple, old) OSPF (better) Interdomain Routing Routing between ASs Assumes that the Internet consists of a collection of interconnected ASs Normally, there is one dedicated router in each AS that handles interdomain traffic. Protocols for interdomain routing are also called Exterior Gateway Protocols or EGPs. Routing protocols:

EGP BGP (more recent) Panwar, Mao, Ryoo, Li: TCP/IP Essentials 11 Distance Vector Routing Each node knows the distance (=cost) to its directly connected neighbors A node sends a list to its neighbors with the current distances to all nodes. If all nodes update their distances, the routing tables eventually converge Panwar, Mao, Ryoo, Li: TCP/IP Essentials 12 Link State Routing

Each node knows the distance to its neighbors The distance information (=link state) is broadcast to all nodes in the network Each node calculates the routing tables independently Panwar, Mao, Ryoo, Li: TCP/IP Essentials 13 Routing Algorithms Goal: Given a network where each link between two nodes i and j is assigned a cost. Find the path with the least cost between nodes s and d. Parameters: dij Cost of link between node i and node j;

dij = , if nodes i and j are not connected; dii = 0. N Set of nodes. Panwar, Mao, Ryoo, Li: TCP/IP Essentials 14 Example 5 2 3 3 5 2 1 3 1 2 1

6 2 4 Panwar, Mao, Ryoo, Li: TCP/IP Essentials 1 d56 = 2 5 15 Distance Vector Each node maintains two tables: Distance Table: Cost to each node via each outgoing link. Routing Table: Minimum cost to each node and next hop node. Nodes exchange messages that contain information on the

cost of a route Reception of messages triggers recalculation of routing table Panwar, Mao, Ryoo, Li: TCP/IP Essentials 16 Discussion of Distance Vector Routing Entries of routing tables can change while a packet is being transmitted. This can lead to a single datagram visiting the same node more than once (Looping). If the period for updating the routing tables is too short, routing table entries are changed before convergence (from the previous updates) is achieved. Example: ARPANET used a Distance Vector algorithm with an update period of <1 sec. This resulted in instability of routing.

Panwar, Mao, Ryoo, Li: TCP/IP Essentials 17 Link State Route Calculations Calculate shortest path for node s Dijkstras Algorithm: s source node. Dn cost of the least-cost path from node s to node n M = {s}; for each n M Dn = dsn; while (M all nodes) do Find w M for which Dw = min{Dj ; j M}; Add w to M; for each n M Dn = minw [ Dn, Dw + dwn ]; Update route; Panwar, Mao,enddo Ryoo, Li: TCP/IP Essentials 18 Example (at node 1)

Dijkstras algorithm 0 1 2 3 4 M {1} {1,4} {1,4,2,5} {1,4,2,5,3} {1,4,2,5,3,6} D1 0 0 0 0 0 Panwar, Mao, Ryoo, Li: TCP/IP Essentials D2 2 2

2 2 2 D3 5 4 3 3 3 D4 1 1 1 1 1 D5 inf 2 2 2 2 D6 inf

inf 4 4 4 19 Resulting Routing Tree 2 2 3 1 1 1 4 1 5 6 2

The tree is translated into a routing table at node 1: Destination 2 3 4 5 6 Panwar, Mao, Ryoo, Li: TCP/IP Essentials Next Hop 2 4 4 4 4 20 Link State Discussion

Each node requires complete topology information. Link state information must be flooded to all nodes. Guaranteed to converge. Each node must maintain a global database. Convergence of the algorithm is guaranteed. Panwar, Mao, Ryoo, Li: TCP/IP Essentials 21 RIP - Routing Information Protocol A simple intradomain protocol Straightforward implementation of Distance Vector Routing Each router advertises its distance vector every 30 seconds (or whenever its routing table changes)

RIP always uses the hop-count as link metric. Maximum hop count is 15, with 16 equal to . Routes timeout after 3 minutes if they are not updated. Route metric is set to (16) and marked for deletion Panwar, Mao, Ryoo, Li: TCP/IP Essentials 22 RIP Packet Format IP header 1: request 2: reply 3, 4: unused 5: poll 6: poll entry addr. family: 2 for IP RIP Message UDP header 0 7 8 15 16

Command Version (1-6) (1) address family 32-bit address 20 bytes long 31 Set to 00...0 Set to 00.00 IP address for which a route is requested Unused (Set to 00...0) Unused (Set to 00...0) metric (1-16) Up to 24 more routes (each 20 bytes) Panwar, Mao, Ryoo, Li: TCP/IP Essentials 23

Routing with RIP This is the operation of RIP in routed. Dedicated port for RIP is UDP port 520. Initialization: Broadcast a request packet (command = 1, metric=16; address family=0, metric=16) on the interfaces requesting current routing tables from routers. Request received: Routers that receive above request send their entire routing table. Response received: Update the routing table (see distance vector algorithm). Regular routing updates: Every 30 seconds, send all or part of the routing tables to every neighbor. Triggered Updates: Whenever the metric for a route changes, send data that has changed.

Panwar, Mao, Ryoo, Li: TCP/IP Essentials 24 RIPv2 IP header RIPv2 Message UDP header Process ID of routing daemon Command Version (1-6) (=2) address family 32-bit address Subnet Mask (32 bits) routing domain route tag Support of EGP and BGP

Subnet Mask of IP address (RIP version 1 is not aware of subnet masks) Next-Hop IP address (32 bits) Metric (1-16) Identifies next hop; value of 0 means packets Identifies next hop: value of 0 means packets should be should be sent to node sending this RIP message sent to node sending this RIP message Up to 24 more routes (each 20 bytes) RIPv2 also supports multicast and provides authentication Panwar, Mao, Ryoo, Li: TCP/IP Essentials 25 OSPF Open Developed

by IETF IGP working group, RFC2328 SPF Each router floods link-state information through its neighbors to other routers Based on the flooded link-state information, each router maintains a complete link-state database Based on the link-state database, a routing table is constructed using SPF (e.g., Dijkstras) algorithm Runs over IP directly, protocol number 89 Panwar, Mao, Ryoo, Li: TCP/IP Essentials 26 Features of OSPF

Use flexible metrics instead of only hop count Supports variable-length subnetting Allows load balancing among equal-cost paths Supports multiple routes; one for each IP type of service (ToS) Authenticates route exchanges Quick convergence Uses multicast rather than broadcast of its messages to reduce network load Panwar, Mao, Ryoo, Li: TCP/IP Essentials 27 Hierarchical OSPF AS is organized as two-level hierarchy AS is partitioned into self-contained areas Areas are interconnected by a backbone area Areas are identified by a 32-bit area ID 0.0.0.0 is reserved for the backbone area

Four types of routers Internal router, area border router, backbone router, autonomous system boundary router (ASBR) Panwar, Mao, Ryoo, Li: TCP/IP Essentials 28 OSPF AS organized into a 2-level hierarchy Within each area, border router responsible for routing outside the area Backbon e area contains all area border routers and possibly others

Panwar, Mao, Ryoo, Li: TCP/IP Essentials (ASBR) Exactly one area is backbone area 29 OSPF packets Five types of OSPF packets Hello(1) Database description(2) Link-State Request(3)/Update(4)/Acknowledgement(5) OSPF common header Version Type (1-5) Packet Length Router ID Area ID Checksum

Authentication Type Authentication Authentication Panwar, Mao, Ryoo, Li: TCP/IP Essentials 30 OSPF common header fields Version number: 2 Type: Type of OSPF packet Packet length: in bytes, includes OSPF header Router ID: 32-bit number assigned to each OSPF running router uniquely identifies router within AS Area ID: any four-byte number (0.0.0.0 reserved for backbone area) Checksum: error detection

Three Authentication related fields: to authenticate OSPF packets Panwar, Mao, Ryoo, Li: TCP/IP Essentials 31 Hello packet Network mask Hello interval Options Priority Dead interval Designated router Backup designated router Neighbor 1 Neighbor n Panwar, Mao, Ryoo, Li: TCP/IP Essentials 32 Hello packet fields

Network mask: Subnet mask of the interface the packet is sent on Hello interval: Number of seconds between Hello packets Options: optional capabilities supported by the router Priority: of the router used in election of designated router Dead interval: Number of seconds before declaring a nonresponding neighbor down Designated router/Backup: Every broadcast network with at least two routers has a designated router. This sends network LSAs for the broadcast network. This field is 0.0.0.0 if there is no designated router Neighbors: Router ID of each neighbor from whom Hello packets have recently been received Panwar, Mao, Ryoo, Li: TCP/IP Essentials 33 Database description packet

Database description packet Interface MTU Options Zero I M M S Database description sequence number LSA header(s) LSA header LSA: Link State Advertisement Link-state age

Options Link-state type Link-state ID Advertising router Link-state sequence number Link-state checksum Panwar, Mao, Ryoo, Li: TCP/IP Essentials Length 34 Database description packet fields Interface MTU: MTU of the associated interface Options: optional capabilities supported by the router I bit: Init bit set to 1 if this packet is the first in the sequence

of database description packets M bit: More bit is set to 1 if more database description packets are to follow MS bit: Master/Slave bit Database description seq. no.: identifies the packet number sequentially so that a receiver can detect a missing packet Panwar, Mao, Ryoo, Li: TCP/IP Essentials 35 LSA header fields Link-state age: time since LSA generation Options: optional capabilities supported by the router Link-state type: router LSA, network LSA, summary LSA for IP

networks, summary LSA for ASB routers, AS-external LSAs Link-state ID: describes routing domain for the LSA; depends on LSA type Advertising router: router ID of the router that generated the LSA Link-state sequence number: Numbers LSAs sequentially to identify old and duplicate LSAs Link-state checksum: entire contents of LSA except link-state age Length: in bytes of LSA including LSA header Panwar, Mao, Ryoo, Li: TCP/IP Essentials 36 Link-state Request/Update/ Acknowledgement Link-state Request Link-state type Link-state ID Advertising router (above 3 fields repeated for each link) Link-state Update

Number of LSAs LSA 1 LSA n Link-state Acknowledgement Panwar, Mao, Ryoo, Li: TCP/IP Essentials 37 Router LSA 32 bits LSA header 0 V EB Type 0 #links #TOS

per-link fields Metric Link ID Link Data Repeat per-link fields for each link Panwar, Mao, Ryoo, Li: TCP/IP Essentials 38 LSA fields bit V (Virtual): 1 when router is a virtual link endpoint bit E (External): 1 when router is an ASBR bit B (Border): 1 when router is an area border router # links: # of links described in this LSA Per link:

Type: Point-to-point connection to another router: 1 Connection to a transit network: 2 Connection to a stub network: 3 Virtual link: 4 Panwar, Mao, Ryoo, Li: TCP/IP Essentials 39 LSA fields contd. Per-link: #TOS: number of TOS metrics other than the required link metric given to this link; if none, 0 Link ID: Identifies the type of node connected to this link

Link Data: depends upon type of link If type 1, Neighboring router's Router ID If type 2, IP address of Designated Router If type 3, IP network/subnet number If type 4, Neighboring router's Router ID For links to stub networks: Network's IP address mask For point-to-point links: the interface's MIB-II ifIndex value. For the other link types: the router interface's IP address. Metric: cost of using this link Panwar, Mao, Ryoo, Li: TCP/IP Essentials 40 Link state updates

Each Link State Update packet carries a set of new link state advertisements (LSAs) one hop further away from their point of origination. A single Link State Update packet may contain the LSAs of several routers. Each LSA is tagged with the ID of the originating router and a checksum of its link state contents. Panwar, Mao, Ryoo, Li: TCP/IP Essentials 41 OSPF operations Hello protocol Database synchronization Propagation of link-state information Building of routing table Panwar, Mao, Ryoo, Li: TCP/IP Essentials 42 Hello Protocol

Hello packets are transmitted to all interfaces periodically Discover neighbors, establish and maintain neighbor adjacency relationships Elect Designated Router (DR) if there are multiple routers in a broadcast network Panwar, Mao, Ryoo, Li: TCP/IP Essentials 43 Database synchronization Two neighboring routers exchange database description packets to synchronize their linkstate databases. Database description includes only a list of LSA headers. New or more up-to-date LSAs will be requested later Packets sent by master are acknowledged by slave Panwar, Mao, Ryoo, Li: TCP/IP Essentials 44 Propagation of link-state information

Link-state request sent When a router wants to update parts of its link-state database Link-state update sent When a link state is requested, or When a link-state changes, or Periodically Link-state acknowledgement sent in response to a linkstate update Link-state updates retransmitted periodically until acknowledged Panwar, Mao, Ryoo, Li: TCP/IP Essentials 45

Flooding LSAs A node receiving a link-state update selectively first installs each LSA in the update into its LSA database Then it decides on which of its other links to flood the LSA it may decide not to flood an LSA out a particular interface if there is a high probability that the attached neighbors have already received the LSA. Panwar, Mao, Ryoo, Li: TCP/IP Essentials 46 Building of routing table Router S has knowledge of the entire area topology (complete link-state database) Some algorithm such as Dijkstras is used to generate shortest path tree, rooted at router S Only the next hop will be used in the

routing table Panwar, Mao, Ryoo, Li: TCP/IP Essentials 47 Example AREA 1 192.1.2 N1 3 RT1 N3 192.1.1 N2 3 RT2 Backbone Assume that all RT3

area interfaces have 3 as their host ID 1 RT4 18.10.0.6 1 RT3 192.1.3 8 2 N4 192.1.4 6 RT6 This is the link metric - note NOT hostID Construct Router LSA for RT3 Panwar, Mao, Ryoo, Li: TCP/IP Essentials

48 RT3s router-LSA for Area 1 LS age = 0; true on origination Options =; LS type = 1; indicates router-LSA Link State ID = 192.1.1.3; RT3's Router ID Advertising Router = 192.1.1.3; RT3's Router ID bit E = 0; not an AS boundary router bit B = 1; area border router #links = 2 Link to N3: [COMMENT]

Link to N4: [COMMENT] Link ID = 192.1.4.0 ; IP Network number Link Data = 0xffffff00; Network mask Type = 3; connects to stub network # TOS metrics = 0 metric = 2 Link ID = 192.1.1.4 ; IP address of Desig. Rtr. Link Data = 192.1.1.3; RT3's IP interface to net Type = 2; connects to transit network # TOS metrics = 0 metric = 1 Panwar, Mao, Ryoo, Li: TCP/IP Essentials 49

RT3's router-LSA for the backbone LS age = 0; always true on origination Options = ; LS type = 1; indicates router-LSA Link State ID = 192.1.1.3; RT3's router ID Advertising Router = 192.1.1.3; RT3's router ID bit E = 0; not an AS boundary router bit B = 1; area border router #links = 1 Link to RT6

Link ID = 18.10.0.6; Neighbor's Router ID Link Data = 0.0.0.3; MIB-II ifIndex of P-P link Type = 1; connects to router # TOS metrics = 0 metric = 8 Panwar, Mao, Ryoo, Li: TCP/IP Essentials 50 Classless Interdomain Routing (CIDR) Routing table are getting longer with the exponential growth of the Internet. CIDR uses supernetting to summarize multiple routing entries into a smaller number of entries. CIDR is supported in almost all new routing. Panwar, Mao, Ryoo, Li: TCP/IP Essentials 51

CIDR-type Address IP address in CIDR Not classified into classes Two components of an IP address Network prefix ranging from 13 to 27 bits Host ID using the remaining bits Slashed-notation A dotted-decimal IP address + / + Number of bits used for the network prefix Network address are assigned in a hierarchical manner. In the core network, routing entries for networks with the

same higher level prefix can be summarized into one entry. The longest-prefix-matching rule is used in table lookups. Panwar, Mao, Ryoo, Li: TCP/IP Essentials 52 Multi-Protocol Label Switching (MPLS) MPLS is a virtual-circuit packet switching technology overlaid on the datagram packet-switched Internet. Attach short labels to network packets that describe how to forward them through the network. Located after the layer two header and before the IP header. Used to make forwarding decisions Independent of any routing protocol.

provides a mechanism for engineering network traffic patterns. Panwar, Mao, Ryoo, Li: TCP/IP Essentials 53 MPLS Traffic Engineering (TE) OSPF always chooses the shortest path, which may be over used and congested. MPLS TE Label Switched Path (LSP) Allows path selection without adjusting link OSPF cost, so that flows can be moved from congested links to alternate links with larger costs. Creates paths for each traffic type. Allows network service provider to set up IP tunnels for virtual private networks (VPNs). Panwar, Mao, Ryoo, Li: TCP/IP Essentials 54

Traceroute Helps determine all the routers in an end-to-end path Uses the Time-to-Live (TTL) field in the IP header and the ICMP protocol. Traceroute operation: Panwar, Mao, Ryoo, Li: TCP/IP Essentials 55

Recently Viewed Presentations

  • HEALTHY EATING!!! RICH OR HEALTHY? One in every

    HEALTHY EATING!!! RICH OR HEALTHY? One in every

    I think that healthy foods should be made more appealing to kids and really unhealthy foods should be made more expensive so that people don't want to waste their money on it. I think that celebrities should start advertising healthier...
  • Ideal-n Plenary Session

    Ideal-n Plenary Session

    Global Research Council - gender equity in STEM research was one of the agenda items for research funding agencies at the 2016 meeting . ADVANCE attended the Americas regional in preparation. ADVANCE invited to present at International Gender Summits. NSF...
  • Tasakaal ja pinged Hiina meditsiinis Keha tasakaalustamine ja

    Tasakaal ja pinged Hiina meditsiinis Keha tasakaalustamine ja

    Wei- qi - kaitsev . qi. liigub keha, soonte ja organite pinnal. Tekib . ... Sha ji, astelpaju. Jiao gu lan, viieleheline eluväät. ... ei saa kunagi piisavalt sooja, ta jume on kahvatu, käed-jalad külmetavad, kergesti tekib külm higi.
  • Creating Tessellating Art - Ms. Pence&#x27;s Classroom

    Creating Tessellating Art - Ms. Pence's Classroom

    Typically, the shapes making up a tessellation are simple similar regular shapes, such as the square. Tessellations * He was born Maurits Cornelis Escher in 1898, in Leeuwarden, Holland. M.C. Escher developed the tessellating shape as an art form *Escher...
  • Digestive System - Weebly

    Digestive System - Weebly

    The Digestive System The digestive system is the group of organs that break food down into molecules that are small enough to be absorbed by and transported throughout the body. The Mouth Digestion begins in the mouth as your teeth...
  • Presenters - University of Nevada, Reno

    Presenters - University of Nevada, Reno

    The Worst PowerPointever made!!! And how to fix yours. Use good fonts and colors. Avoid: Ccursive fonts. Distracing fonts. Elaborate Fonts. ... who really wants to sit and read through a PowerPoint slide presentation with lots and lots and lots...
  • Outline for 4/2

    Outline for 4/2

    Outline Logistics Bayes Nets joint probability distribution, conditional independence graphical representation inference (deduction & diagnosis) Review
  • The Tudors Contents  The birth of the nation

    The Tudors Contents The birth of the nation

    The Tudors Contents The birth of the nation state England and her neighbours Government and society The birth of the nation state The new monarchy The Reformation The Protestant-Catholic struggle England and her neighbours The new foreign policy The new...