DOC PREVIEW
Berkeley ELENG 228A - Routing Overview

This preview shows page 1-2-3-4-26-27-28-54-55-56-57 out of 57 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 57 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 57 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 57 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 57 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 57 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 57 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 57 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 57 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 57 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 57 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 57 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 57 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Routing OverviewEECS 228Abhay [email protected] 7, 2002October 7, 2002Abhay K. Parekh: Topics in Routing2What is Routing?Routing is the core function of a networkIt ensures thatT information accepted for transfer T at a source node T is delivered to the correctT set of destination nodes, T at reasonable levels of performance.October 7, 2002Abhay K. Parekh: Topics in Routing3Routing in the Internet is really about Scaling Range and Number!T Hosts: Number, Mobile, Virtual, P2PT Traffic: Growth in volume, rates and session types (e.g. unicast, multicast, anycast, voice, video, transactional, bulk)T Networks: Peering, Information Hiding, Policies, Ad-hoc etc.T All this and must be “backward compatible” as well!Size of core internet router tables v/s timeOctober 7, 2002Abhay K. Parekh: Topics in Routing4Why study routing?T Routing struggles to Y operate correctly as users, networks and traffic rates increase in range and number whileT maintaining the distributed, federated nature of the internetT providing “acceptable” performanceT Studying routing in the context of this struggle provides rich insights into how current networks work, and how to build better onesOctober 7, 2002Abhay K. Parekh: Topics in Routing5Our ApproachT Lay out the hard issues which are often architecturalT Try to gain insight into the issues via simplified modelsT Shoot for insight into the general problem of routing and not spend too much time on the specifics of any one protocol or systemOctober 7, 2002Abhay K. Parekh: Topics in Routing6TodayT First part:Y What are basic sub functions of routing?Y How should we think about them?T Second part:Y How does routing relate to other network functionsY Path computation - CentralizedOctober 7, 2002Abhay K. Parekh: Topics in Routing7Routing Sub-FunctionsT Addressing: Uniquely identify the nodes Y host IP address, group address, attributesY set is dynamic!T Topology Update:Y Discover topologyY Measure “distance” metric(s)Y Dynamically provision (on slower timescale)T Destination Discovery: Find node identifiers of the destination setT Route Computation: Pick the tree (path)Y Kind of path: Multicast, UnicastY Centralized or Distributed AlgorithmY MetricsY Hierarchy/PolicyT Switching: Forward the packets at each node6785431212101311October 7, 2002Abhay K. Parekh: Topics in Routing8Routing ProtocolsT Addressing: Uniquely identify the nodes Y host IP address, group address, attributesY set is dynamic!T Topology Update: Characterize and maintain connectivityY Discover topologyY Measure “distance” (one or more metric)Y Dynamically provision (on slower timescale)T Destination Discovery: Find node identifiers of the destination setT Route Computation: Pick the tree (path)Y Kind of path: Multicast, UnicastY Centralized or Distributed AlgorithmY PolicyY HierarchyT Switching: Forward the packets at each nodeOctober 7, 2002Abhay K. Parekh: Topics in Routing9Routing is a distributed functionT Topology changes can be detected by nearby nodesT These changes must be reflected in the routesT Need a mechanism and a protocolT Changes must be disseminated: Three mechanismsY Link State: Communicate the names and costs of neighbors. Each node maintains the entire topology. E.g. used in OSPFY Distance Vector: Communicate current distance estimates of node to every other node. E.g. used in RIPY Path Vector: Communicate current estimates of preferred pathsfrom node to every other node. E.g. used in BGPT Dissemination protocol may react strangely to network conditionsY Most routing problems are triggered by this…October 7, 2002Abhay K. Parekh: Topics in Routing10Colloquial RoutingT Addressing: Uniquely identify the nodes Y host IP address, group address, attributesY set is dynamic!T Topology Update: Characterize and maintain connectivityY Discover topologyY Measure “distance” metric(s)Y Dynamically provision (on slower timescale)T Destination Discovery: Find node identifiers of the destination setT Route Computation: Pick the tree (path)Y Kind of path: Multicast, UnicastY Global or Distributed AlgorithmY PolicyY HierarchyT Switching: Forward the packets at each nodeOctober 7, 2002Abhay K. Parekh: Topics in Routing11Many Kinds of RoutingDriven by…T Destination setY IP point-to-pointY MulticastT Physical CharacteristicsY OpticalY Ad-hocY Diffusion (sensor networks)Y Interconnection network routingY Geographic (wireless)T Network FunctionY P2PY Content Distribution NetworksOctober 7, 2002Abhay K. Parekh: Topics in Routing12Kinds of Route ComputationT Centralized v/s Distributed T Hierarchical v/s FlatT Datagram v/s Virtual CircuitT Single Path v/s MultipathT Unicast v/s MulticastT Shortest Path v/s Policy and DeflectionOctober 7, 2002Abhay K. Parekh: Topics in Routing13Datagram v/s Virtual CircuitT Datagram routingY Each packet to be forwarded independentlyY More sensitive to current network conditionsT Virtual CircuitY Each packet from same o-d uses same routeY More state (pick the “right” granularity)Y Less sensitive to network conditionsT QoS sensitive networks use VC’s and signalingY Find a route that has the resources available for the connection. Y “Reserve” the resources before sending data packetsOctober 7, 2002Abhay K. Parekh: Topics in Routing14The reservation process: Sender ADB ENew session to ESignalingprotocol findssatisfactorypathUpdate RoutersADB ENew session to ET Ability to guarantee e2e delay helps in signaling and resource reservationT Service disciplines and other network QoS mechanisms affect the routes that are chosenT Signaling is hard in peered networksOctober 7, 2002Abhay K. Parekh: Topics in Routing15The reservation process: ReceiverT Ability to guarantee e2e delay helps in signaling and resource reservationT Service disciplines and other network QoS mechanisms affect the routes that are chosenT Signaling is hard in peered networksADB ENew receiver wants to be part of groupSignalingprotocol findssatisfactorypathUpdate RoutersADB EIn progressOctober 7, 2002Abhay K. Parekh: Topics in Routing16Mostly Ignored…T Addressing: Uniquely identify the nodes Y host IP address, group address, attributesY set is dynamic!T Topology Update: Characterize and maintain connectivityY Discover topologyY Measure “distance” metric(s)Y Dynamically provision (on slower timescale)T Destination Discovery: Find node identifiers of the destination setT Route Computation: Pick the tree (path)Y Kind of path: Multicast, UnicastY Global or


View Full Document

Berkeley ELENG 228A - Routing Overview

Documents in this Course
FAST TCP

FAST TCP

57 pages

Load more
Download Routing Overview
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Routing Overview and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Routing Overview 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?