Network Layer; Location Management; Mobile IPAcknowledgement: slides borrowed from Richard Y. Yang @ Yale.Recap: Wireless Link Layer• The basic services of the link layer– link access• interference, hidden terminal• quality of service (and fairness) control– framing, link reliability, etc• Guided by network layer– transmit to which neighbor at what quality2BASEFHJDCGIKMNLNetwork Layer Services• Transport packets from source to dest• Network layer protocol in every host, routerBasic functions:• Control plane– compute routing from sources to destinations• Data plane: forwarding– move packets from input interface to appropriate output interface(s)3BAS1ED2S2JD1CGIKMNLNetwork Layer: API• API (provided to upper layer)– transmit( info, src, dest, …);• A key decision in network layer design is how to represent destinations?– we refer to how applications specify destinations as the addressing scheme– the supported addressing scheme(s) can have profound impacts on usability, flexibility, and scalability4Discussion: How to Specify a Destination?5BASEFHJDCGIKMNLTwo Basic Approaches for Identifying Destinations• Locators– encode locations on network topology• Identifiers (ID)– independent of network topology 6AEDCBFAddressing Scheme: Sensornet Example• Destination: message to a sensor (e.g., who detected fire)– <ID = D>– <Lat=37.3169; Long=-121.8740>– <temperature = highest>7BASEDFJDCGIKMNLAddressing Scheme: Telephone• Very first scheme: connection by operators to business– ID or locator?• The telephone numbering scheme: – invented in 1888 by Almon Strowger, an undertaker: “No longer will my competitor steal all my business just because his wife is a BELL operator.”8Telephone Addressing Scheme• E.164: Maximum 15 digits• Hierarchical addressing scheme: country code + national destination code (optional) + subscriber number)– e.g., +1-203-432-6400• Why hierarchical addressing scheme?– 203-432 uniquely determines the switch upon which the telephone is attached to• Issues of such a scheme?9BASEDFJDCGIKMNLAddressing Scheme: Internet• How to specify the destination which is the color printer on the 4thfloor of AKW– Internet domain name: lw4c.cs.yale.edu– Internet protocol (IP) address: 128.36.231.8– [building = AKW; floor=4; entity = printer; quality = color]1011Addressing Scheme: IP IP address: 32-bit identifier for an interface An IP address is associated with an interface%/sbin/ifconfig -a223.1.1.1223.1.1.2223.1.1.3223.1.1.4223.1.2.9223.1.2.2223.1.2.1223.1.3.2223.1.3.1223.1.3.27223.1.3.2 = 11011111 00000001 00000011 000000102231 23IP Addressing• Hierarchical scheme:– network part (high order bits)– host part (low order bits) • What’s a network? (from IP address perspective)– device interfaces with same network part of IP address– link layer can reach each other12223.1.1.1223.1.1.3223.1.1.4223.1.2.2223.1.2.1223.1.2.6223.1.3.2223.1.3.1223.1.3.27223.1.1.2223.1.7.0223.1.7.1223.1.8.0223.1.8.1223.1.9.1223.1.9.2Why Hierarchy?• The hierarchy is important for the scalability of Internet routing• The routing system handles only the number of networks– 275,280 networks on Jan. 3 2009; – 625 mil hosts in Jan. 2009)13223.1.1.1223.1.1.3223.1.1.4223.1.2.2223.1.2.1223.1.2.6223.1.3.2223.1.3.1223.1.3.27223.1.1.2223.1.7.0223.1.7.1223.1.8.0223.1.8.1223.1.9.1223.1.9.2http://ftp.isc.org/www/survey/reports/current/Routing in IP/Telephone Networks• Represent network as a graph• Determine a pathto each destination on the graph– Q: what does a nodein the graph represent?14AEDCBF2213112535Key Problems• Location management– due to user mobility (roaming), hierarchical routing (address aggregation) may cause user devices to be not attached to their networks/switches• need forwarding/location management• Dynamic routing– due to node mobility/wireless connectivity, link connectivity/quality can be highly dynamic• need to design routing protocols that are effective in handling dynamic topologies• Broadcast wireless– there can be interference among links and paths (need good link performance metrics or scheduling)15AEDCBFNext• Location management in cellular networks16Routing in Cellular Networks• Cellular networks face the location management problem: – a phone may be out of its home switch• How GSM handles out-of-switch phones:– a global home location register (HLR) database for each carrier– each base transceiver station (BTS) has a visitor location register (VLR)17AEDCBF18BSCRadio SubsystemBSCGSMMS (mobile station)BSC (base station controller)BTS (base transceiver station)MSC (mobile switching center)GMSC (gateway MSC)fixed networkMSC MSCGMSCNetwork &Switching Subsystemand OperationSubsystemMSMSMSMSMSMSBTSBTSBTSBTSBTSVLRVLRVLRVLRVLRHLRTwo Primitives for Cellular Location Management• Mobile station: reports to the network of the cell it is in– called update– uses the uplink channel• Network: queries different cells to locate a mobile station– called paging– uses the downlink channel19Performance of the Two Primitives• A city with 3M users• During busy hour (11 am - noon)• Assume each paging message is 100 bits• Update only– update messages: 25.84 millions– Q: why so many update messages?• Paging only– paging traffic: 1433 calls/sec – Q: how many bits?20Location Management Through Location Areas (LA)• A hybrid of paging and update• Used in the current cellularnetworks such as GSM• Partitions the cells into location areas (LA)– e.g., around 10 cells in diameter in current systems• Each cell (BTS) periodicallyannounces its LA id• If a mobile station arrives at a new location area, it updates the base station about its presence• When locating a MS, the network pages the cells in an LA21How to Decide the LAs: A Simple Model• Assume the cells are given• Cell i has on average Niusers in it during one unit time; each user receives c calls per unit time• There are Nijusers move from cell i to cell j in a unit of time22Cell 1Cell 2N1N2N12N21How to Decide the LAs: A Simple Scenario• Separate LAs for cells 1 and 2– update cost: N12+ N21– paging cost: c (N1+ N2)• Merge cells 1 and 2 into a single LA– update cost: 0– paging cost: 2 c (N1+ N2)• When to merge and when to separate?23Cell 1Cell 2N1N2N12N21Discussions• The LA design should consider– call pattern: when (how often) does a mobile station receive a call?– mobility