Chapter 5 - Network Layer (Control Plane) Flashcards
What is fowarding?
move packets from router input port to appropriate output port
what is routing?
determine route taken by packets from source to destination
two approaches for network control plane
- per router (traditional)
- logically centralized control
logically centralized control plane?
Remote controller interacts with local control agents (CAs) in routers to compute fowarding tables
Per-router system?
- routing algorithm components in EVERY ROUTER to compute fowarding tables
What is the cost of an edge?
- physical length
- link speed
- monetary cost
centralized routing algortihm?
- has complete topology (link cost info)
- “link state” algorithms
Decentralized routing algorithm
- router knows physically-connected neighbours and link cost for these
- iterative process to exchange info with neighbours
- “distance vector” algorithms
Static routing algorithms
- routes change slowly over time
- usually requires human intervention
dynamic routing algorithm
- routes change more quickly
- periodic update
- in response to link cost changes
What does distributed mean for the distance vector algorithm
- each node receives some info from one or more of its DIRECTLY ATTACHED neighbours
- performs a calculation
- distributes the results of its calculation back to its neighbours
what does “iterative” mean with the distance vector algorithm
continues until no more info is exchanged between neighbours
what does asynchronous mean with distance vector algorithm
- it does not require all nodes to operate in lockstep with each other
Comparing LS and DV algorithms
Message complexity:
LS - with n nodes, E links, O(nE) messages sent
DV - exchange between neighbours only
Speed of convergence:
LS - O(n^2) algorithm requires O(nE) messages (could have oscillations)
DV - convergence time varies (routing loops or count to infinity)
Robustness (router malfunctions?):
LS - advertise incorrect link cost
each node only computes only its own table
DV - can advertise incorrect path cost
intra-AS routing
- routing between routers in same network
- routers must run SAME intra-domain protocol
- routers in different AS (autonomous systems) can run different AS protocols
- gateway router: edge of AS. has links to routers in other AS
inter-AS routing
- routing amoung different AS
- gateways performs inter-domain routing (and intra-domain routing)
Hierarchy of OSPF
- each area runs its own OSPF link-state rotuing algorithm
- each router broadcasts link state to all other routers in area
- area border routers:
summarize distances to nets in own area and advertise to other area border routers - backbone routers:
run OSPF routing - boundary routers:
connect to other AS
Open shortest path first (OSPF)
- publically available
- uses link state
- router will flood OSPF link-state to all routers in AS
- messages carried directly over IP rahter than TCP or UDP
Border gateway protocol (BGP)
-inter domain protocol
- determines good routes based on reachability and policy
eBGP
obtain subnet reachability info from neighbouring AS
iBGP
propagate reachability info to all AS-internal routers
Hot potato routing
choose local gateway that has least intra domain cost. Dont worry about inter-domain cost
BGP route selection
1.) local preference (policy)
2.) shortest AS-path
3.) closest next-hop router (hot potato)
4.) additional criteria
Why different intra-, inter-AS routing?
Policy:
inter - admin wants to control how traffic routed and who routes through its net
intra - single admin, so no policy decisions
scale:
- heriarchical routing saves table size, reduced update traffic
performance:
intra - can focus on performance
inter - policy can dominate over performance
What is broadcast routing?
- deliver packets from source to all other nodes
- send separate copy to each destination using unicast routing
- inefficient because packet traverses same link multiple times
What is uncontrolled flooding?
-source sends copy of packet to all neighbours
- when node received packet, will duplicate and foward to all neighbours except one that sent it
- issues are cycles and broadcast storm
What is controlled flooding?
- chooses when to flood a packet and when to not. (ie do not flood id packet was already received and flooded)
- using sequence numbers: unique identifier plus broadcast sequence number, each node maintains list, does not forward packets it has already received.
What is Reverse Path Fowarding (RPF)?
- only foward packet if it arrived on shortest path between node and source
- router knows it has or will receive packet from shortest path link to sender
- does not use unicast routing to deliver packet
What is multicast routing?
- packets delivered to each and every node in network
- multicast packet is delivered to only a subset of network nodes
Problems with multicast routing
- how to identify receivers of multicast packet
- how to address a packet sent to these receivers
What is address indirection?
- single identifier is used for the group of receivers
- a copy of packet is delivered to all of the multicast receivers associated with that group
what is a multicast group?
- a group of receivers associated with a class D address
What is the Internet Group Management Protocol (IGMP)
- Operates between a host and its directly attached router
- allows host to inform its attached router that it wants to join a specific multicast group
What does the IGMP message “membership_query” mean?
- sent by router to all hosts on attached interface
- determines the set of all multicast groups that have been joined by the hosts on that interface
What does the IGMP message “membership_report” mean?
- host indicates group membership to router
What does the IGMP message “leave_group” mean?
- optional message
- soft-state internet protocol
