清华大学：域内路由选择（PPT课件讲稿）Intra-domain routing

Intra-domain routing Dan li CS Department, Tsinghua University 2021/2/8

Intra-domain routing 2021/2/8 1 Dan LI CS Department, Tsinghua University

Today's Lecture Routing Model Intra-domain Routing 2021/2/8

Today’s Lecture  Routing Model  Intra-domain Routing 2021/2/8 2

Notion of an Internet protocol How is it possible to send bits across incompatible LANs and wans? Solution: protocol software running on each host and router smooths out differences between different networks Implements an internet protocol(i.e, set of rules that governs how hosts and routers should cooperate when they transfer data from network to network TCP /IP is protocol (family) for global P Internet

Notion of an Internet Protocol How is it possible to send bits across incompatible LANs and WANs? Solution: protocol software running on each host and router smooths out differences between different networks Implements an internet protocol (i.e., set of rules) that governs how hosts and routers should cooperate when they transfer data from network to network • TCP/IP is protocol (family) for global IP Internet

What does an Internet protocol do? Provides naming scheme k Defines uniform format for host addresses Each host (and router) is assigned at least one internet address that uniquely identifies it Provides delivery mechanism An internet protocol defines a standard transfer unit packet) Packet consists of header and payload Header: contains info such as packet size source and destination addresses Payload: contains data bits sent from source host Encapsulation- key to network messages

What Does an Internet Protocol Do?  Provides naming scheme  Defines uniform format for host addresses  Each host (and router) is assigned at least one internet address that uniquely identifies it  Provides delivery mechanism  An internet protocol defines a standard transfer unit (packet)  Packet consists of header and payload  Header: contains info such as packet size, source and destination addresses  Payload: contains data bits sent from source host  Encapsulation - key to network messages

Transferring Data via Internet Host a Host B client server (1)data (8) data protocol protocol intenetpacket software software (2) dataPH (7) dataPH ant LAN2 Frame adapter Router adapter (3)data PH FH1 LAN2 ) data PH FH2 LAN1 LAN1 adapter adapter LAN2 frame LAN2 data PH! FH1 data PH FH2(5) protocol software

Transferring Data via Internet protocol software client LAN1 adapter Host A data data PH FH1 data PH data PH FH2 LAN1 LAN2 data data PH data PH FH2 (1) (2) (3) (4) (5) (6) (7) (8) internet packet LAN2 frame protocol software LAN1 adapter LAN2 adapter Router FH1 data PH protocol software server LAN2 adapter Host B Frame

But ■■■ how do routers know where to forward frames? * How do routers learn when the network topology changes? That' s what routing protocol does

But…  How do routers know where to forward frames?  How do routers learn when the network topology changes?  That’s what routing protocol does…

Routing Goal: determine good"path sequence of routers through network from source to destination * good path” typically means minimum cost path other definitions also possible 2021/2/8

Routing  Goal: determine “good” path (sequence of routers) through network from source to destination  “good path”  Typically means minimum cost path  Other definitions also possible 2021/2/8 7

Dynamic Routing P traffic can be very bursty Dynamic adjustments in routing typicall operate more slowly than fluctuations in traffic load Dynamically adapting routing to account for traffic load can lead to wild unstable oscillations of routing system Usually, IP routing protocols do not dynamically route around network congestion 2021/2/8

Dynamic Routing  IP traffic can be very bursty  Dynamic adjustments in routing typically operate more slowly than fluctuations in traffic load  Dynamically adapting routing to account for traffic load can lead to wild, unstable oscillations of routing system Usually, IP routing protocols do not dynamically route around network congestion. 2021/2/8 8

Graph Model Represent each router as node Direct link between routers represented by edge Symmetric links undirected graph Edge cost cx,y) denotes measure of difficulty of using link delay, s cost, or congestion level Task Determine least cost path from every node to every other node Path cost d(x, y)=sum of link costs 2021/2/8

Graph Model  Represent each router as node  Direct link between routers represented by edge  Symmetric links  undirected graph  Edge “cost” c(x,y) denotes measure of difficulty of using link  delay, $ cost, or congestion level  Task  Determine least cost path from every node to every other node  Path cost d(x,y) = sum of link costs 2021/2/8 9

A Simple Model(Cont 6 D B 2021/2/8

A Simple Model (Cont.) 2021/2/8 10 A E F C D B 2 3 6 4 1 1 1 3