Link Layer Services and data link layer services provided to network layer and link layer services in computer networks
EECS 489 Computer Networks
Z. Morley Mao
Wednesday Feb 14, 2007
Acknowledgement: Some slides taken from Kurose&Ross and Katz&Stoica
Homework 2 is posted
- Problems from the book
- You can either use Turnin program or turn in the
homework on paper to my office.
- Due date: next Tuesday 2/20
Midterm 1 is in class on Wednesday March 7
- Please let us know if you prefer to take it early
- Material: Chapter 1-4
- Including half of today’s lecture
- You can have one sheet of notes for the midterm.
Pairs of routers (BGP peers) exchange routing info over semi-
permanent TCP conctns: BGP sessions
Note that BGP sessions do not correspond to physical links.
When AS2 advertises a prefix to AS1, AS2 is promising it will
forward any datagrams destined to that prefix towards the prefix.
- AS2 can aggregate prefixes in its advertisement
Distributing reachability info
With eBGP session between 3a and 1c, AS3 sends prefix reachability
info to AS1.
1c can then use iBGP do distribute this new prefix reach info to all
routers in AS1
1b can then re-advertise the new reach info to AS2 over the 1b-to-2a
When router learns about a new prefix, it creates an entry for the prefix
in its forwarding table.
Path attributes & BGP routes
When advertising a prefix, advert includes BGP
- prefix + attributes = “route”
Two important attributes:
- AS-PATH: contains the ASs through which the advert
for the prefix passed: AS 67 AS 17
- NEXT-HOP: Indicates the specific internal-AS router to
next-hop AS. (There may be multiple links from current
AS to next-hop-AS.)
When gateway router receives route advert, uses
import policy to accept/decline.
BGP route selection
Router may learn about more than 1 route to
some prefix. Router must select route.
1. Local preference value attribute: policy decision
2. Shortest AS-PATH
3. Closest NEXT-HOP router: hot potato routing
4. Additional criteria
BGP messages exchanged using TCP.
- OPEN: opens TCP connection to peer and authenticates sender
- UPDATE: advertises new path (or withdraws old)
- KEEPALIVE keeps connection alive in absence of UPDATES;
also ACKs OPEN request
- NOTIFICATION: reports errors in previous msg; also used to
Mao W07BGP routing policy
Figure 4.5-BGPnew: a simple BGP scenario
A,B,C are provider networks
X,W,Y are customer (of provider networks)
X is dual-homed: attached to two networks
X does not want to route from B via X to C
.. so X will not advertise to B a route to C
Mao W07BGP routing policy (2)
Figure 4.5-BGPnew: a simple BGP scenario
A advertises to B the path AW
B advertises to X the path BAW
Should B advertise to C the path BAW?
No way B gets no “revenue” for routing CBAW since
neither W nor C are B’s customers
B wants to force C to route to w via A
B wants to route only to/from its customers
Intra- and Inter-AS routing ?
Inter-AS: admin wants control over how its traffic routed,
who routes through its net.
Intra-AS: single admin, so no policy decisions needed,
exception: VPN networks.
hierarchical routing saves table size, reduced update
Intra-AS: can focus on performance
Inter-AS: policy may dominate over performance
Mao W07Broadcast routing
Source-duplication versus in-network duplication.
(a) source duplication, (b) in-network duplication
How to get rid of duplicates?
- Broadcast sequence
- Source node address
Only forward if packet
arrived on the link on
Reverse path forwarding
its own shortest
unicast path back to
Spanning tree to the rescue
- A tree containing every node, no cycles
(b) Broadcast initiated at D
(a) Broadcast initiated at A
Broadcast along a spanning tree
How to construct a spanning tree?
F E E
(a) Stepwise construction (b) Constructed spanning
of spanning tree tree
Center-based construction of a spanning tree
E is the center of the tree
Is this a minimum spanning tree?
Mao W07How is BGP relevant to the us?
Mao W07Level 3 depeers with Cogent
Mao W07Botnet of 100,000 PCs crushed
Up Until Now.....
Short-term contention is loss-less
- main resource (link bandwidth) is controlled by router
- router deals with short-term contention by queuing packets
- switch algorithms and router buffers ensure no packets are
dropped due to short-term contention
We have focused on long-term contention
- queuing schemes (FQ, FIFO, RED, etc.)
- end-to-end congestion control (TCP)
What’s New in This Lecture?
Short-term contention leads to loss
Lecture deals with networking over shared media
- long-range radio
- short-range radio
Also known as “multiple-access”
- don’t go through central router to get access to link
- instead, multiple users can access shared medium
Medium Access Protocols
- Divide channel into smaller “pieces” (e.g., time slots,
- Allocate a piece to node for exclusive use
- Allow collisions
- “recover” from collisions
- Tightly coordinate shared access to avoid collisions