Internetworking
Internetworking
Internetworking
Topics covered:
Basic terminology. Principles of internetworking. Types of internetworking devices. Repeaters,
hubs, bridges, routers, switches and gateways. Transparent and source-routing bridges.
Multilayer switches. VLANs. Routing strategies. Addressing.
2.1 Terminology
Internetworking stands for connectivity and communication between two or more networks.
- Intermediate System (IS): a device that connects two or more networks (e.g., switch,
router). It is called sometimes an IWU (Internetworking Unit) or a relay.
1. Provide a link between networks. At minimum, a physical and link control connection is
needed.
2. Provide for the routing and delivery of data between processes on different networks.
3. Provide an accounting service that keeps track of the use of the various networks and
routers and maintains status information.
4. Provide the services just listed without requiring modifications to the networking
architecture of constituent networks. This means accommodating the following
differences:
o Different status reporting: how and whether this information can be shared.
Some of the above mentioned issues are dealt with in the IWUs.
It may be desirable for an internetwork service not to depend on the characteristics of individual
networks.
- The use of multiple networks allows for network isolation when needed. This is critical to
network performance as failure is contained within one network. Also, a network can be
shielded from intrusion (Security).
- Contain the amount of traffic sent between the networks (e.g., Routing domains)
- Wide Area Networks (WANs): distant campuses connected together usually through
connection providers such as a telephone company.
- Remote connections: linking branch offices and mobile users to a corporate campus.
They are generally dial-up links or low bandwidth dedicated WAN links.
• Overcomes restrictions caused by single segment usage such as number of users, cable
length.
• Provides simple connection between adjacent LANs at the expense of increased network
congestion.
The bridge was designed for interconnection of LANs that use identical protocols at the MAC
layer (i.e., layer 2). However, there are bridges capable of mapping between different MAC
protocols (e.g., Ethernet and Token Ring).
A bridge main function is forwarding frames from one network to another. A bridge does the
following:
• Does not inspect or modify the network layer packets inside frames.
• Security: Types of traffic with different security needs are kept on physically separate
media.
• The routing decision may not always be a simple one. If we add bridge B7 between
LAN-A and LAN-E.
• B7 may fail.
- Fixed routing
- Source routing
- A route is selected for each source-destination pair of LANs. If more are available, the
one with the least number of hops is selected.
- A central routing matrix is created. It shows the identity of the first bridge on the route.
Advantages:
• Simplicity
• Minimal processing requirements
Disadvantages:
• Bridges can be dynamically added and failures may occur, so tables must change.
- It is intended to interconnect LANs that satisfy any of the MAC standards without end
stations being aware of its existence (i.e., transparent)
The bridge must map the content of the incoming frame into an outbound frame that conforms to
the frame format for the outbound LAN, because MAC formats for the various LANs differ.
A bridge maintains a filtering database. This information can be preloaded into the bridge (i.e.,
static routing).
1.
2.
3.
4.
5.
6.
7.
Problem:
1.
2.
3.
4.
5.
Problem:
In graph theory: for any connected graph, consisting of nodes and edges connecting pairs of
nodes, there is a spanning tree of edges that maintains the connectivity of the graph but contains
no closed loops.
Algorithm:
LAN 2
C = 10 C=5
P= 1 P= 1
B3 (45) B4 (57)
C = 10
P= 2 P= 2 P= 2
C = 10 C=5
B1 (42)
P= 1 LAN 5
C = 10 C=5
P= 2
B5 (83)
P= 1
C=5
LAN 1
C = 10
P= 2
B2 (97)
C=5 P= 1 P= 3 C=5
LAN 3 LAN 4
1. Determine the root bridge (RB) that is the bridge with the lowest id.
¾ The root path cost (rpc) is the cost of the path to the root bridge with minimum cost.
3. Determine the designated port (D) on each LAN. This is the port with the minimum rpc.
If more bridges have the same rpc, the one with the highest priority is chosen as
designated bridge (i.e., lowest-numbered bridge identifier).
¾ The designated bridge is the bridge that provides the minimum cost path to the root
bridge.
4. Ports which are neither (R) nor (D) are Blocking (B).
BPDUs (Bridge Protocol Data Units) are used to exchange information between bridges.
• BPDUs are sent by all the bridges each claiming to be the root bridge. B1 is elected as the
root bridge.
• All other bridges determine the root port (R) and root path cost (rpc).
• Example: On LAN-5: B3, B4 and B5 send BPDUs claiming to be the designated bridge.
B4 and B5 have the lowest RPC. B4 has a higher priority. B4 becomes the designated
bridge (D).
Forwarding Forwarding
timer expires timer expires
The following is a table summarizing the actions taken by a bridge in each state.
Disabled
Blocking
Listening
Learning
Forwarding
The sending station determines the route to be followed by a frame and includes routing
information with this frame.
- Nonbroadcast: the frame includes a single route using LANs and bridges.
- All-routes broadcast: the frame will reach each LAN (and the destination station) by all
possible routes.
To avoid looping:
- Single-route broadcast: the frame will appear once on each LAN. The frame is forwarded
to bridges on the spanning tree with source node as root. The spanning tree is built
automatically or manually. The destination receives one copy.
All-routes broadcast and Single-route broadcast types of routing are used to discover
route to destination. They are also used for group and all-stations addressing.
1.
o Source station transmits an all-routes request to destination.
o Destination sends back a nonbroadcast response on each discovered route.
o Source uses one of these to send subsequent frames.
o Problems:
2.
o Source station transmits a single-route request.
o Destination responds with an all-routes response.
o Source chooses one for subsequent transmissions.
Transparency
Topology knowledge
Frame format
Frame forwarding
Bridge mode
Link utilization
Configuration (LAN
numbering, bridge numbering,
spanning tree, etc)
Performance
Routing
A key problem is that both (transparent and source routing bridges) are incompatible. To allow
the interconnections of LANs using a mixture of transparent and source routing bridges, a new
standard was developed by the IEEE 802.5 committee, and that is the Source Routing
Transparent (SRT) technique.
To contain/reduce broadcast traffic, we need to reduce the size of the network (i.e., LAN).
2.3.3.2 Characteristics
• A router separates traffic of different networks. It does not flood packets.
• Routers “learn” their routing table entries by communicating with their routing peers.
• Routing protocols are used to implement routing (RIP, OSPF, BGP, PNNI)
• Routers perform routing decisions on the basis of the Network ID part of the destination
IP address.
• The Host ID part of the destination address is used by the destination router to determine
the destination station.
Class A:
0 Network ID Host ID
7 bits 24 bits
Class B:
10 Network ID Host ID
14 bits 16 bits
Class C:
110 Network ID Host ID
21 bits 8 bits
Class D:
1110 Multicast address
28 bits
Class E:
11110 Reserved for future use
27 bits
In RFC 1918, several IP addresses have been allocated for private addressing. An organization
can use these addresses if they are not registered with the Internet. Systems are available that
translate private, unregistered addresses to public, registered addresses.
¾ One problem is how to store, maintain and access many network addresses in one routing
table. Æ The Internet establishes a scheme whereby multiple networks are identified by one
address entry in the routing table.
Address aggregation:
This subnet address is 128.1.16.0/20 (with 16 bits Network ID, 4 bits Subnet ID, and 12 bits Host
ID).
It permits networks to be grouped together logically, and to use one entry in a routing table for
multiple class C networks.
Problem:
2.3.3.4.2 Flooding
A packet is sent by a source node to every one of its neighbors and each node retransmits it again
to its neighbors (similar to “all-routes broadcast” in source routing bridges). The flooding
technique has three properties:
o All possible routes are tried, and there is always a backup route (good for emergency
messages)
o One copy of the packet will reach destination by following a minimum-hop route (can
be use to setup virtual circuits)
o All nodes are visisted (disseminate information to all nodes)
Problem:
Problem:
Problems:
o More complex routing decision.
o Information exchanged is itself a load
o Reaction to changes can be too quick or too slow.
However:
o Adaptive routing can improve performance from the user perspective.
o Adaptive routing can aid in congestion control, because it tends to balance load.
2.3.3.5 Definitions
¾ Autonomous System (AS):
• Consists of a group of routers exchanging info via a common routing protocol.
• A set of routers and networks managed by a single organization.
• Is connected (i.e., a path exists between any 2 nodes) except in time of failure.
RIP is:
o An IRP
o A distance-vector protocol
o A widely used protocol because of its simplicity and ease of use
o Based on the number of intermediate hops to destination
o Based on Bellman-Ford algorithm
o A distributed adaptive algorithm
o Maximum number of hops between a source and destination is 15
o Routing information is sent every 30 seconds to all adjacent routers using broadcast
frames.
OSPF:
o Is an IRP
o Is a link-state routing protocol
o Is based on Dijkstra’s algorithm
o Is a distributive adaptive algorithm
o Routers send link state packets (LSPs) that include information about the cost of each
of its links/interfaces
o Relies on two mechanisms:
¾ Reliable flooding: the newest information must be flooded to all nodes as
quickly as possible, while old information must be removed from the network.
¾ Route Calculation: Each node gets a copy of the LSP from all nodes and
computes a complete map for the network topology. Then, it decides the best
route to each destination.
o Uses flexible routing metrics: distance, delay, cost, etc.
o Allows for scalability
o Uses multiple paths to allow for load balancing
o Supports security measures
¾ BGP:
o Is a replacement for EGP (Exterior Gateway Protocol). EGP had limitations that
include forcing a tree-like topology onto the network.
o Provides inter-domain routing.
o Is more concerned with reachability than optimality.
o Is the routing protocol employed on the Internet.
¾ Challenges:
o Lot of routing information to pass (~90,000 prefixes/routes in BGP routing tables.)
o Autonomous nature of the domains (different than IRPs). Cost metrics are not the
same and don’t have the same meaning across ASes.
o Trust between different providers (e.g., wrong configuration in an AS, competitors,
etc.)
¾ BGP prevents the establishment of looping paths (because it uses the complete AS path)
¾ BGP uses policy-based metrics. (RFC 1655: BGP policy-based architecture). Policies include
various routing preferences and constraints, such as economic, security, or political
considerations. (e.g., preference of internal routes over external routes).
Whatever we have said about bridges apply to switches (i.e., a switch is a bridge is a switch).
Sometime the difference between a bridge and a switch is looked at as a marketing distinction
rather than a technical one.
It can be said that a switch is a high-speed multi-port bridge. A large switch can have more than
100 interfaces.
¾ Switches: operate at layer 2. They leverage transparent bridging. Typically one port
provides a high speed uplink to the backbone.
¾ Layer-3 switches (i.e., multilayer switches): include properties of layer-2 switches and
some layer-3 capabilities (i.e., routing capabilities). They use the philosophy of “Switch
(bridge) where you can, route where you must”.
¾ Layer-4 switches: It does not implement layer-4 functionality, but it prioritizes certain
classes of application traffic. Applications are identified using TCP port number.
¾ “Store-and-forward” switches:
o Buffer data.
o Check for CRC (Cyclic Redundancy Check) errors.
o Filter out frames
Problem:
¾ “Cut-through” switches:
o Frame header is read.
o Data is switched without being buffered.
o Only works if both the input and output ports operate at the same data rate.
Problems:
Comparison:
Parameters in switches:
¾ Backplane speed: Internal capacity of a switch. It must exceed the summation of all
ports capacities, otherwise blocking and frame dropping will occur.
¾ Memory: Used for buffering data. If it is not enough, then frames dropping will occur.
Switch features:
¾ Filtering: Switches, in contrast to traditional bridges, can filter traffic (i.e., forward
traffic conditionally) by interpreting the frame beyond the SA (Source Address) and DA
(Destination Address). E.g., layer-3 switches.
¾ Oversubscription: where aggregate bandwidth at the leaves exceeds that of the trunk.
(See the internetworking product timeline in table 4.1 of “The Switch Book”.)
Operation:
The switch architecture can be optimized for functions that must be performed in real-time, for
the majority of packets, known as the fast path of the flow.
• Fast path:
A layer-3 switch needs to implement only this fast path in hardware, e.g., implement hardware-
based routing for IP.
• Because
¾ Subnet mask represented using 5 bits: used for high-speed routing table lookup
operations.
¾ VLANs enable the creation of logical groups of network devices across a network.
¾ User Mobility: VLANs allow for more flexibility in the positioning of end stations and
servers, and reduce the effort of adds, moves, and changes:
o They can be placed physically anywhere in the building and still remain in the
same logical LAN (i.e., VLAN).
o They can be placed physically in the same location but move to a new logical
LAN.
¾ VLANs are used to partition a flat bridged network using of these techniques:
¾ Gateways: more complex as they interface between two dissimilar networks (operates
above layer-3). They are necessary when two networks do not share the same network
layer protocol.
2.4 References
1. "Data and Computer Communications" by William Stallings, 6th Edition, Prentice Hall, 2000
3. "Local & Metropolitan Area Networks" by William Stallings, 6th Edition, Prentice Hall, 2000
4. “The Switch Book” by Rich Seifert. John Wiley & Sons Inc., 2000.
6. “LAN Technologies Explained” by Philip Miller and Michael Cummins. Digital Press, 2000